We give a complete characterization of the complexity of best-arm\nidentification in one-parameter bandit problems. We prove a new, tight lower\nbound on the sample complexity. We propose the `Track-and-Stop' strategy, which\nwe prove to be asymptotically optimal. It consists in a new sampling rule\n(which tracks the optimal proportions of arm draws highlighted by the lower\nbound) and in a stopping rule named after Chernoff, for which we give a new\nanalysis.\n