Fixed-confidence guarantees for Bayesian best-arm identification

Xuedong Shang, Rianne Heide, Pierre Menard, Emilie Kaufmann, Michal Valko
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1823-1832, 2020.

Abstract

We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-shang20a, title = {Fixed-confidence guarantees for Bayesian best-arm identification}, author = {Shang, Xuedong and de Heide, Rianne and Menard, Pierre and Kaufmann, Emilie and Valko, Michal}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1823--1832}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/shang20a/shang20a.pdf}, url = {https://proceedings.mlr.press/v108/shang20a.html}, abstract = {We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.} }
Endnote
%0 Conference Paper %T Fixed-confidence guarantees for Bayesian best-arm identification %A Xuedong Shang %A Rianne Heide %A Pierre Menard %A Emilie Kaufmann %A Michal Valko %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-shang20a %I PMLR %P 1823--1832 %U https://proceedings.mlr.press/v108/shang20a.html %V 108 %X We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.
APA
Shang, X., Heide, R., Menard, P., Kaufmann, E. & Valko, M.. (2020). Fixed-confidence guarantees for Bayesian best-arm identification. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1823-1832 Available from https://proceedings.mlr.press/v108/shang20a.html.

Related Material