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: