On the Complexity of Best Arm Identification with Fixed Confidence

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