Optimal Best Arm Identification with Fixed Confidence
This work provides a foundational solution for efficiently identifying the best arm in bandit problems with fixed confidence, impacting areas like clinical trials and online advertising.
The paper tackles the problem of best-arm identification in one-parameter bandit problems by proving a tight lower bound on sample complexity and proposing the asymptotically optimal 'Track-and-Stop' strategy, which includes a new sampling rule and a Chernoff-based stopping rule.
We give 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 we prove 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.