From the archives

Optimal Best Arm Identification with Fixed Confidence

Historical material. Affiliations, schedules and roles on this page describe their original context.

ConferenceName:  Conference On Learning Theory

url:  Conference On Learning Theory (archive lookup)

Edition Number:  29

Date:  June, 2016

Place:  New York, USA

PageStart:  998

PageEnd:  1 027

Authors:  Aurélien GarivierEmilie Kaufmann

Abstract: 

Julia code of the simulations on github
We provide 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 is proved 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.
COLT presentation on youtube (with some unfortunate sound recording problems)

Direct link:  In: Proceedings of of Machine Learning Research vol. 49

Arxiv Number:  1602.04589

Hal Number:  01273838

Keywords: