On the complexity of All $\varepsilon$-Best Arms Identification
  We consider the question introduced by \cite{Mason2020} of identifying all
the $\varepsilon$-optimal arms in a finite stochastic multi-armed bandit with
Gaussian rewards. We give two lower bounds on the sample complexity of any
algorithm solving the problem with a confidence at least $1-\delta$. The first,
unimprovable in the asymptotic regime, motivates the design of a Track-and-Stop
strategy whose average sample complexity is asymptotically optimal when the
risk $\delta$ goes to zero. Notably, we provide an efficient numerical method
to solve the convex max-min program that appears in the lower bound. Our method
is based on a complete characterization of the alternative bandit instances
that the optimal sampling strategy needs to rule out, thus making our bound
tighter than the one provided by \cite{Mason2020}. The second lower bound deals
with the regime of high and moderate values of the risk $\delta$, and
characterizes the behavior of any algorithm in the initial phase. It emphasizes
the linear dependency of the sample complexity in the number of arms. Finally,
we report on numerical simulations demonstrating our algorithm's advantage over
state-of-the-art methods, even for moderate risks.
