An Optimal Elimination Algorithm for Learning a Best Arm

We consider the classic problem of (ε,δ)-PAC learning a best arm where the goal is to identify with confidence 1-δ an arm whose mean is an ε-approximation to that of the highest mean arm in a multi-armed bandit setting. This problem is one of the most fundamental problems in statistics and learning theory, yet somewhat surprisingly its worst-case sample complexity is not well understood. In this paper, we propose a new approach for (ε,δ)-PAC learning a best arm. This approach leads to an algorithm whose sample complexity converges to exactly the optimal sample complexity of (ε,δ)-learning the mean of n arms separately and we complement this result with a conditional matching lower bound. More specifically: