Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann
29th Annual Conference on Learning Theory, PMLR 49:998-1027, 2016.

Abstract

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the ‘Track-and-Stop’ strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-garivier16a, title = {Optimal Best Arm Identification with Fixed Confidence}, author = {Garivier, Aurélien and Kaufmann, Emilie}, booktitle = {29th Annual Conference on Learning Theory}, pages = {998--1027}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/garivier16a.pdf}, url = {https://proceedings.mlr.press/v49/garivier16a.html}, abstract = {We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the ‘Track-and-Stop’ strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.} }
Endnote
%0 Conference Paper %T Optimal Best Arm Identification with Fixed Confidence %A Aurélien Garivier %A Emilie Kaufmann %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-garivier16a %I PMLR %P 998--1027 %U https://proceedings.mlr.press/v49/garivier16a.html %V 49 %X We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the ‘Track-and-Stop’ strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.
RIS
TY - CPAPER TI - Optimal Best Arm Identification with Fixed Confidence AU - Aurélien Garivier AU - Emilie Kaufmann BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-garivier16a PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 998 EP - 1027 L1 - http://proceedings.mlr.press/v49/garivier16a.pdf UR - https://proceedings.mlr.press/v49/garivier16a.html AB - We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the ‘Track-and-Stop’ strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis. ER -
APA
Garivier, A. & Kaufmann, E.. (2016). Optimal Best Arm Identification with Fixed Confidence. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:998-1027 Available from https://proceedings.mlr.press/v49/garivier16a.html.

Related Material