  We consider the classic problem of $(\epsilon,\delta)$-PAC learning a best
arm where the goal is to identify with confidence $1-\delta$ an arm whose mean
is an $\epsilon$-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
$(\epsilon,\delta)$-PAC learning a best arm. This approach leads to an
algorithm whose sample complexity converges to \emph{exactly} the optimal
sample complexity of $(\epsilon,\delta)$-learning the mean of $n$ arms
separately and we complement this result with a conditional matching lower
bound. More specifically:

Machine Learning;Machine Learning