Conference abstracts

Session A7 - Stochastic Computation

July 11, 18:00 ~ 18:25 - Room B2

The Complexity of Best-Arm Identification

Aurélien Garivier

Université de Toulouse, France   -

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.

Joint work with Emilie Kaufmann (CNRS, team CRIStAL, France).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.