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.

通过大偏差原理，我们在适应性算法中建立了样本抽取比例与样本奖励之间的联系，从而改进了现有算法并设计了新算法，我们证明了新算法的性能优于现有算法，包括对众多抽样的广泛实验证实了这一观察结果。