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.
I will present a complete characterization of the complexity of best-arm identification in
one-parameter bandit problems.
In other words, we give a new, tight lower bound for the expected number of obervations
required in order to identify, with high probability, the maximum of a discrete function
observed in noise. Furthermore, we propose the 'Track-and-Stop' strategy, which we prove
to be asymptotically optimal. As a conclusion, I will present perspectives of extensions
to continuous optimization.
Joint work with Emilie Kaufmann, accepted at COLT'16. Version arXiv accessible ici: http://arxiv.org/abs/1602.04589
Slides: SPOT20160606.pdf Date: June, 2016 Event url: SPOT (archive lookup) Keywords: