  We consider the problem of identifying the best arm in stochastic Multi-Armed
Bandits (MABs) using a fixed sampling budget. Characterizing the minimal
instance-specific error probability for this problem constitutes one of the
important remaining open problems in MABs. When arms are selected using a
static sampling strategy, the error probability decays exponentially with the
number of samples at a rate that can be explicitly derived via Large Deviation
techniques. Analyzing the performance of algorithms with adaptive sampling
strategies is however much more challenging. In this paper, we establish a
connection between the Large Deviation Principle (LDP) satisfied by the
empirical proportions of arm draws and that satisfied by the empirical arm
rewards. This connection holds for any adaptive algorithm, and is leveraged (i)
to improve error probability upper bounds of some existing algorithms, such as
the celebrated \sr (Successive Rejects) algorithm \citep{audibert2010best}, and
(ii) to devise and analyze new algorithms. In particular, we present \sred
(Continuous Rejects), a truly adaptive algorithm that can reject arms in {\it
any} round based on the observed empirical gaps between the rewards of various
arms. Applying our Large Deviation results, we prove that \sred enjoys better
performance guarantees than existing algorithms, including \sr. Extensive
numerical experiments confirm this observation.
