Fixed-Confidence Guarantees for Bayesian Best-Arm Identification

Xuedong Shang, Rianne de Heide, Emilie Kaufmann, Pierre Ménard and Michal Valko

What is this paper about?

This paper studies Bayesian sampling rules for fixed-confidence best-arm identification. It analyses Top-Two Thompson Sampling, introduces the computationally lighter Top-Two Transportation Cost rule, and proves sample-complexity and posterior-convergence results.

Summary

We investigate the sampling rule Top-Two Thompson Sampling (TTTS) and justify its use for fixed-confidence best-arm identification. We propose a computationally lighter variant, Top-Two Transportation Cost (T3C). As the main contribution, we give the first sample-complexity analysis of TTTS and T3C when combined with a natural Bayesian stopping rule for Gaussian bandits, addressing an open question raised by Russo. We also establish new posterior-convergence results for TTTS under Gaussian and Bernoulli reward models with conjugate priors.

Topics

Bandits and pure exploration · Bayesian learning and generalized Bayes

← Research