From the archives
On the Complexity of Best Arm Identification with Fixed Confidence
Historical material. Affiliations, schedules and roles on this page describe their original context.
We consider the problem of finding the highest mean among a set of probability distributions that can be sampled sequentially. We provide a complete characterization of the complexity of this task in simple parametric settings: we give a tight lower bound on the sample complexity, and we propose the 'Track-and-Stop' strategy, which we prove to be asymptotically optimal. This algorithm 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.
Slides: 20170920_Garivier_UT1.pdf Date: September, 2017