Open Problem: Optimal Best Arm Identification with Fixed-Budget

Chao Qin
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:5650-5654, 2022.

Abstract

Best arm identification or pure exploration problems have received much attention in the COLT community since Bubeck et al. (2009) and Audibert et al. (2010). For any bandit instance with a unique best arm, its asymptotic complexity in the so-called fixed-confidence setting has been completely characterized in Garivier and Kaufmann (2016) and Chernoff (1959), while little is known about the asymptotic complexity in its “dual” setting called fixed-budget setting. This note discusses the open problems and conjectures about the instance-dependent asymptotic complexity in the fixed-budget setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-open-problem-qin22a, title = {Open Problem: Optimal Best Arm Identification with Fixed-Budget}, author = {Qin, Chao}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {5650--5654}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/open-problem-qin22a/open-problem-qin22a.pdf}, url = {https://proceedings.mlr.press/v178/open-problem-qin22a.html}, abstract = {Best arm identification or pure exploration problems have received much attention in the COLT community since Bubeck et al. (2009) and Audibert et al. (2010). For any bandit instance with a unique best arm, its asymptotic complexity in the so-called fixed-confidence setting has been completely characterized in Garivier and Kaufmann (2016) and Chernoff (1959), while little is known about the asymptotic complexity in its “dual” setting called fixed-budget setting. This note discusses the open problems and conjectures about the instance-dependent asymptotic complexity in the fixed-budget setting.} }
Endnote
%0 Conference Paper %T Open Problem: Optimal Best Arm Identification with Fixed-Budget %A Chao Qin %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-open-problem-qin22a %I PMLR %P 5650--5654 %U https://proceedings.mlr.press/v178/open-problem-qin22a.html %V 178 %X Best arm identification or pure exploration problems have received much attention in the COLT community since Bubeck et al. (2009) and Audibert et al. (2010). For any bandit instance with a unique best arm, its asymptotic complexity in the so-called fixed-confidence setting has been completely characterized in Garivier and Kaufmann (2016) and Chernoff (1959), while little is known about the asymptotic complexity in its “dual” setting called fixed-budget setting. This note discusses the open problems and conjectures about the instance-dependent asymptotic complexity in the fixed-budget setting.
APA
Qin, C.. (2022). Open Problem: Optimal Best Arm Identification with Fixed-Budget. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5650-5654 Available from https://proceedings.mlr.press/v178/open-problem-qin22a.html.

Related Material