From the archives

Optimal Best Arm Identification with Fixed Confidence

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

Context:  New York

Resume: 

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.

Slides:  COLT20160624_long.pdf

Date:  June, 2016

Event url:  COLT 2016 (archive lookup)videolectures

Keywords: