Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition

Speaker: Vincent Y. F. Tan, National University of Singapore

Algorithms, Theoretical Machine Learning

28 August 2026
SSB 334 (AM Turing Hall), CSE Dept.
3:30 PM

Abstract

We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to an abstention budget α, we analyze the probability of undetected error—the risk of recommending a suboptimal arm without abstaining. Our central finding is that abstention induces a phase transition: without abstention, the error probability decays polynomially in the sampling budget T; in contrast, introducing any small positive abstention budget shifts this to an exponential decay. For Gaussian priors and rewards, in the regime T → ∞ followed by α ↓ 0, we establish exact matching information-theoretic lower bounds and algorithmic upper bounds on the optimal error exponent, which takes the form exp(−α²T/(8κ²ν)). The hardness parameter κν represents the prior density of the top-two gap at zero, highlighting that nearly tied instances drive the fundamental error. We introduce an adaptive algorithm, PGWS, that successfully achieves this optimal exponent by expending its abstention budget on statistically ambiguous instances. We further demonstrate that this polynomial-to-exponential improvement is exclusively a Bayesian phenomenon—in the frequentist setting, abstention only affects lower-order exponent terms. We also extend our results beyond the Gaussian model.

About the Speaker

Vincent Y. F. Tan is a Professor in the Departments of Mathematics and Electrical and Computer Engineering at the National University of Singapore (NUS). His research lies at the intersection of information theory, machine learning, and sequential decision making, with current interests in reinforcement learning, large language models, and statistical learning. He received his Ph.D. from MIT and B.A. and M.Eng. degrees from the University of Cambridge, and has received several awards for excellence in both research and teaching.

Image: Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan. “Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition” [preprint]. https://doi.org/10.48550/arXiv.2606.29203