Bayesian method optimizes decision time with error and abstention limits

Bayesian Fixed-Confidence Best-Arm Identification with Abstention

Machine Learning

Summary

The paper looks at how to quickly and confidently find the best option among many uncertain choices while allowing the option to opt out sometimes. The authors introduce a new approach called Screen-and-Confirm (S&C) and analyze how long it takes to decide on the best choice given limits on error and how often one can abstain. They find exact formulas for the minimal time any method needs to meet these limits, especially when the differences between options are small and uncertain. Their method improves on previous work by removing extra delays in decision time when no abstention is allowed.

What this means in practice

  • For clinical trial designers: Determine the best treatment more efficiently while allowing some trials to be inconclusive within a set budget of abstentions.
  • For marketing analysts: Identify the top-performing product variations quickly with a controlled chance to abstain when uncertain, optimizing data collection resources.

A theory result. No direct application yet.

Authors

Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan

Abstract

We study the Bayesian fixed-confidence best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to a target error probability $δ$ and an abstention budget $α$, we propose Screen-and-Confirm (S&C) and analyze its expected stopping time. We further derive the minimum expected stopping time for any algorithm that satisfies these constraints. For Gaussian priors and rewards, as $(δ,α)\downarrow(0,0)$, we establish matching upper and lower bounds up to multiplicative constants, with rate $κ_ν^2[1+\log((α+δ)/δ)]/(α+δ)$, where $κ_ν$ is the prior density of the top-two gap at zero, highlighting that nearly tied instances govern the sampling cost. When abstention is disallowed ($α=0$), S&C yields the optimal $Θ(1/δ)$ dependence for fixed model parameters, removing the additional $\log(1/δ)$ factor in the upper bound of Jang et al. (2024) under our Gaussian assumptions. We further characterize the exact multiplicative constant of the minimum expected stopping time for practical regimes including (i) fixed $α\in (0,1)$ and (ii) $α/δ\to\infty$, which are also achieved by S&C.