Best Arm Identification with Fixed Budget: A Large Deviation Perspective
Authors: Po-An Wang
Ruo-Chun Tzeng
Alexandre Proutiere
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Best arm identification
Large deviation

Abstract: 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 \cite{audibert2010best}, and (ii) to devise and analyze new algorithms. In particular, we present CR (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 CR enjoys better performance guarantees than existing algorithms, including SR. Extensive numerical experiments confirm this observation.

Best Arm Identification with Fixed Budget: A Large Deviation Perspective
Po-An Wang
Ruo-Chun Tzeng EECS KTH, Stockholm, Sweden rct kth. se
EECS
KTH, Stockholm, Sweden wang90kch.se
Alexandre Proutiere
EECS and Digital Futures KTH, Stockholm, Sweden alepro@kth.se
Abstract
We consider the problem of identifying the best arm in stochastic Multi-Armed Bandits (MABs) using 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 static sampling strategy, the error probability decays exponentially with the number of samples a rate that can 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 (Audibert et al., 2010), and (ii) to devise and analyze new algorithms. In particular, we present CR (Continuous Rejects), a truly adaptive algorithm that can reject arms in any round based the observed empirical gaps between the rewards of various arms. Applying our Large Deviation results, we prove that CR enjoys better performance guarantees than existing algorithms, including SR. Extensive numerical experiments confirm this observation.
(Successive Rejects) algorithm
Introduction
We study the problem of best-arm identification in stochastic bandits in the fixed budget setting, In this problem, abbreviated by BAI-FB, learner faces K distributions or arms v1..... characterized by their unknown means μ (M1.... ... ............. _K) (we restrict our attention distributions taken from one- mee-paraetter exponential family). She sequentially pulls arms and observes samples of the corresponding distributions. More precisely, in round 2 1, she pulls an arm A, k selected depending on previous observations and observes X₁. (t) sample of a vi -e-dittributed random variable. (1, 2 1, k E [K]) are assumed to be independent over rounds and arms. After T arm draws, the learner returns an estimate of the best arm 1(μ) arg max; A4g- We assume that the best arm is unique, and denote by the set of parameters such that this assumption holds. The objective is to devise adaptive sampling algorithm minimizing the error probability P Pa li & 1(x)). This learning task is one of the most important problems in stochastic bandits, and despite recent research efforts, it remains largely open (Qin, 2022). In particular, researchers have so far failed
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

at characterizing the minimal instance-specific error probability. This contrasts with other basic learning tasks in stochastic bandits such as regret minimization (Lai and Robbins, 1985) and BAI with fixed confidence (Garivier and Kaufmann, 2016), for which indeed, asymptotic instance-specific performance limits and matching algorithms have been derived. In BAI-FB, the error probability typically decreases exponentially with the sample budget T, i.e., it scales as exp(- R())T) where the instance-specific rate R(μ) depends on the sampling algorithm. Maximizing this rate over the set of adaptive algorithms is open problem.
Instance-speciffe error probability lower bound. To guess the maximal rate at which the error probability decays, one may apply the same strategy as that used in regret minimization or BAI in the fixed confidence setting: (i) derive instance-specific lower bound for the error probability for some notion of uniformly good algorithms; (ii) devise a sampling strategy mimicking the optimal proportions of arm draws identified in the lower bound. Here the notion of uniformly good algorithms that of consistent algorithms. Under such an algorithm, for any μ E A, IP [ [[x)] - 1 as T - oc. (Garivier and Kaufmann, 2016) conjectures the following asymptotic lower bound satisfied by any consistent algorithm (refer to Appendix J for details): as T - 00,
T log
S max inf w), WE AEAI(())
(Ag, pk),, Alt(p) = (A e A 1(n) & ]())} is the set of confusing parameters (those for which 1(4) is not the best arm), and d(z, y) denotes the KL divergence between two distributions of parameters x and y. Interestingly, the solution w* E Σ of the optimization problem max x T (A, w) provides the best static proportions of arm draws. More precisely, an algorithm selecting arms according to the allocation w", i.e., selecting arm ls W times and returning the best empirical arm after 7 samples, has an error rate matching the lower bound (1). This is a direct consequence of the fact that, under a static algorithm with allocation w. the empirical reward process {ū(()):21 satisfies LDP with rate function À + v w), see (Glynn and Juneja, 2004) and refer to Section 3 for more details.
where E the (K --ddimensional simplex, T ( w) w
k Ex=
Adaptive sampling algorithms and their analysis. The optimal allocation wn depends on the instance je and is initially unknown. We may devise an adaptive sampling algorithm that (i) estimates wn and (ii) tracks this estimated optimal allocation. In the BAI with fixed confidence, such tracking scheme exhibits asymptotically optimal performance (Garivier and Kaufmann, 2016). Here however, the error made estimating w* would inevitably impact the overall error probability of the algorithm. To quantify this impact or more generally to analyze the performance of adaptive algorithms. one would need to understand the connection between the statistical properties of the arm selection process and the asymptotic statistics of the estimated expected rewards.
To be more specific, any adaptive algorithm generates stochastic process {Z(1)) ((w(t) ((()))ee1 (()) =
represents the allocation realized by the algorithm up to round & (wx(1)= Nu (1)/t and (t)(t) denotes the number of times arm k: has been selected up to round (). (a(l)= = (1), fig (4)) denotes the empirical average rewards of the various arms up to round f. Now assuming that at the end of round T, the algorithm returns the arm with the highest empirical reward, the eттor probability is Puli + 1(z) = P (T) E Alt(H)). Assessing the error probability at least asymptotically requires understanding the asymptotic behavior of ((t) as grows large. Ideally, one would wish to establish the Large Deviation properties of the process (2()) This task is easy for algorithms using static allocations (Glynn and Juneja, 2004), but becomes challenging and open for adaptive algorithms. Addressing this challenge is the main objective of this paper.
Contributions. In this paper, we develop and leverage tools towards the analysis of adaptive sampling algorithms for the BAI-FB problem. More precisely, our contributions are as follows.
(a) We establish a connection between the LDP satisfied by the empirical proportions of arm draws (w)t)) and that satisfied by the empirical arm rewards. This connection holds for any adaptive algorithm. Specifically, we show that the rate function of (w) is lower bounded by w + Iw),, then that of (fz()))22 is also lower bounded by X - minwex max V (A,A)) w), T(w)). This result has interesting interpretations and implies the following asymptotic upper bound on the error probability of the algorithm considered: as T 00,
log
inf max (V)() I(w))
T
7
1 1(4)
(EAL))
2

---

The above formula, when compared to the lower bound (I), quantifies the price of not knowing w' initially, and relates the error probability to the asymptotic statistics of the sampling process used by the algorithm.
(b) We show that by simply applying our generic Large Deviation result, we may improve the error probability upper bounds of some existing algorithms, such as the celebrated SR algorithm (Audibert al., 2010). Our result further opens up opportunities devise and analyze new algorithms with higher level of adaptiveness. In particular, we present CR (Continuous Rejects), an algorithm that, unlike SR, can eliminate arms in each round. This sequential elimination process is performed by comparing the empirical rewards of the various candidate arms using continuously updated thresholds. Leveraging the LDP tools developed in (a). we establish that CR enjoys better performance guaranteess than SR. Hence CR becomes the algorithm with the lowest instance-specifee and guaranteed error probability. We illustrate our results via numerical experiments, and compare CR to other BAI algorithms.
2
Related Work
We distinguish two main classes of algorithms to solve the best arm identification problem in the fixed budget setting. Algorithms from the first class, e.g. Successive Rejects (SR) (Audibert et al., 2010) and Sequential Halving (SH) (Karnin et al., 2013), split the sampling budget into phases of fixed durations, and discard arms at the end of each phase. Algorithms from the second class, e.g. UCB-E (Audibert et al., 2010) and UGapE (Gabillon al., 2012) sequentially sample arms based on confidence bounds of their empirical rewards. It is worth mentioning that algorithms from the second class usually require some prior knowledge about the problem, for example, an upper bound of H = E ((4) (Pace)-aa3 Without this knowledge, the parameters can be chosen in a heuristic way, but the performance gets worse.
Algorithms from the first class exhibit better performance numerically and are also those with the best instance-specific error probability guarantees. SR had actually the best performance guarantees so far: for example, when the reward distributions are supported on [0, 1]. the error probability of SR satisfies:
lim inf + log P.] Z H2 H2 K. where H₂ max{ş1(w)) (Pum) -p yr this
paper, we strictly improve this guarantee (see Section 3.4). Recently, (Barrier et al., 2022) also refined and extended the analysis of (Audibert et al., 2010) by replacing, in the analysis, Hoeffding's inequality by large deviation result involving KL-divergences. Again here, we further improve this new guarantee. We also devise CR, an algorithm with error probability provably lower than our improved guarantees for SR.
Fundamental limits on the error probability have also been investigated. In the minimax set- ting, (Carpentier and Locatelli, 2016) established that for any algorithm, there exists problem within the class of instances with given complexity H such that the error probability is greater than 4007 exp(- lf log K 2 exp( Wa log K Up to universal constant (here 400), SR is hence minimax optimal. This lower bound was also recently revisited in (Ariu et al., 2021; Degenne, 2023; Wang et al., 2023) to prove that the instance-specifie lower bound (1) cannot be achieved on all instances by single algorithm. Deriving tight instance-specifee lower bounds remains open (Qin, 2022).
4007'
We conclude this section by mentioning two interesting algorithms. In (Komiyama et al., 2022), the authors propose DOT, an algorithm trying to match minimax error probability lower bounds. To this aim, the algorithm requires periodically call an oracle able to determine an optimal allocation, solution of an optimization problem with high and unknown complexity. DOT has minimax guarantees but is computationally challenging if not infeasible (numerically, the authors cannot go beyond simple instances with 3 arms). Finally, researchers have also looked at the best arm identification problem from a Bayesian perspective. For example, (Russo, 2016) devise variants of the celebrated Thompson Sampling algorithm, that could potentially work well in practice. Nevertheless, as discussed in (Komiyama, 2022), Bayesian algorithms cannot be analyzed nor provably perform well in the frequentist setting.
3

---

3 Large Deviation Analysis of Adaptive Sampling Algorithms
In this section, we first recall key concepts in Large Deviations (refer to the classical textbooks (Budhiraja and Dupuis, 2019; Dembo and Zeitouni, 2009; Dupuis and Ellis, 2011; Varadhan, 2016) for more detailed exposition). We then apply these concepts to the performance analysis of adaptive sampling algorithms. Finally, we exemplify the analysis and apply it to improve existing performance guarantees for the SR algorithm (Audibert et al., 2010).
3.1 Large Deviation Principles
Consider the stochastic process (Y(0) with values in a separable complete metric space (i.e., Polish space) y. Large Deviations are concerned with the probabilities of rare events related to h12)2 that decay exponentially in the parameter t. The asymptotic decay rate is characterized by the rate function I y + I defined so that essentially - log P (() E B] converges to minzen B T(x) for any Borel set B. We provide more rigorous definition below.
Definition 1. [Large Deviation Principle (LDP)) The stochastic process {Y (t))) satisfies LDP with rate function I if:
(i) I is lower semicontinuous, and Vs E 10, oo), the set K., = {u E/ I(y) < 8) is compuct; (ii for every closed (resp. open) set C y (resp. O C),,
1
lim +-0
log
2 inf T(y), E P[Y())
(3)
t
P[Y(t)
yEC
lim
log
inf S
(()).
LDPs have been derived earlier in stochastic bandit literature. (Glynn and Juneja, 2004) have used Gärtner-Ellis Theorem (Ellis, 1984; Gärtner, 1977) to establish that under static sampling algorithm with allocation w E Σ (i.c., each arm is selected W times up to round Z'), the process (T(T)) satisfies an LDP with rate function X + v ( w) = Ek= wrd()n (ax) Our objective in the next subsection is to investigate how to extend this result to the case of adaptive sampling algorithms.
3.2 Analysis of adaptive sampling algorithms
An adaptive sampling algorithm generates a stochastic process {Z(1))21 = [(w(t, (()))
When the sampling budget T' is exhausted, should the algorithm returns the arm with the highest empirical reward, the error probability is P la * [(+) = P,, (T) E Alt(z))). To assess the rate at which this probability decays with the budget, we may try to establish a LDP for the empirical reward process h(z))) Due to the intricate dependence between the sampling and the empirical reward processes, deriving such an I.P very challenging. Instead, we establish connection between the LDPs satisfied by these processes. This connection will be enough for us to derive tight upper bounds on the error probability. We present our main result in the following theorem.
Theorem 1. Assume that under some adaptive sampling algorithm, (w)()) satisfies the LDP upper bound (3) with rate function T. Then (f((t) satisfies the LDP upper bound (3) with rate function X minwex max & (x, w), [(w)). Moreover, have: for any bounded Borel subset S of IR and any Borel subset W of Σ,
lim (+00
log
inf max [(w()),[(w))
P (i((t) E &S, W
wEd((W)
where Fs(w) == inf inf (AA, w), and cl(S) denotes the closure of S.
Before proving the above theorem, we make the following remarks and provide simple corollary that will lead to improved upper bound on the error probability of the SR algorithm.
(a) Not a complete LDP. To upper bound the error probability of given algorithm, we do not actually need to establish that ((2))) satisfies a complete LDP. Instead, deriving LDP upper bound enough. Theorem provides such an upper bound, but does not yield complete LDP. We conjecture (1)))) satisfies an LDP with rate function T, {f((t)} satisfies an L.PP with rate function A + infwew max (A, w), [w)). The conjecture holds for static sampling algorithms as shown

---

below. If it holds for adaptive algorithms, we show, in Appendix I, that when K > 3, no algorithm can attain the spelacc--ppeciicc lower bound (I) for all parameters.
(b) Theorem is tight for static sampling algorithms. When the sampling rule is static, namely w(t) = E Σ, then (w)))) satisfies LDP with rate function I defined T(w) 0 and co elsewhere. Theorem I with W = D states that [i(()))) satisfies the LDP upper bound (3) with rate function F's. In fact, as shown by (Glynn and Juneja, 2004), {f(()) satisfies complete LDP with this rate function.
(c) useful corollary. From Theorem 1, we have:
lim
log PA (t()) E w(t W
inf Fs(w). wee((W)
From there, we will be able to improve the performance guarantee for SR.
3.3 Proof of Theorem
Proof. Observe that when S or W is empty, the result holds. Now recall that Fs(.) inf xed(s))) V (x. is the infimum of family of linear functions compact set, E, hence it upper bounded. Denote u > 0 such an upper bound. Fs(.) is also continuous (see Appendix F for details). For each integer N E N, we define a collection of closed sets:
W E cl(w): u(n 1) S FF(w)) S un } An [N].
W.
N S
(5)
N
We observe that:
N PulA(t) E S,w(() E W] S
Σ ==1
p. Pula(t) S, w() e W.N
N max P (i((t)) E (,)(t) e w. REIN]
Taking the logarithm on both sides and dividing them by -t yields that
1 log Pn (i((()) E (()((() E w]
1
1 log Pr (((()) E s,w(l) Wi]
lim + i
lim min t00 NE[N] 7
min lim
log
nE[N] t-000 t
F (ā(t) E S,w(t) E WM
[u(n - 1)
2 min max
inf I(w)
(6)
N
N
weWN
where the last inequality follows from Lemma 1. Since for all n E [N].
u(n - 1)
[(w)]
u(nn 1)
I(w))
max
inf
inf max wEWN
N
WEWN
N
the r.h.s. of (6) is equal to
(u(n- 1)
1(w)]
min inf
max
2 min inf max [Fs(w) (w), [[w]] u/N we[M = inf max(F{(())I(())) u/N, w)d(()
WEIN WEWN
N
where the first inequality is due to (5). can taken arbitrarily large, we conclude this theorem.
Lemma 1. For any N N, ne (N),
Ju(n -
lim log Pa(l((t) ES, E W
max
inf WEWN
I(w)
5

---

Proof. Recall Fs(-) inf (nfe))(s)) (A -). We deduce that
F. [i((t) E S, (t) E ] - PM [X 2 (Fs(w(()) w()) E w
where denotes (f((t) (t)) for short. Let a E (0, 1), Markov's inequality implies that
F [X tFy w W P, ((w(t) W., Jeat Jea((- (FF(((()) 2
1 [w](1) Wi Je Jen(x- (F(((()))
s S [I(w(t) WN, Jeat]
ou(n-1)
(7)
where the last inequality uses the definition of W (see (5)). By applying Hölder's inequality with p.g. where [L, 1/a) and p/(p1) on r..ss of (7), deduce that log [io(t) S, w(t) e w is at most
au(n 1)
(log Ex [)px])/p= (log (w(l(w(()) E W WN H1//
N
As op E 1). Lemma 2 Appendix shows that the first term above o(t). Using definition of rate function, (3) with C = W on the second term yields that liml log F.l lower bounded by
(1/4) inf I(w) + au(n- 1) = (1- WEWN
inf I(w) + au(n 1) WEWN
N
N
As p can be arbitrarily close to 1/a, get the lower bound (1 - [-][(w + aa(n-1) choosing a close to either or O, the proof is completed.
Further
3.4 Improved analysis of the Successive Rejects algorithm
In SR, the set of candidate arms is initialized Cr [K]. The budget of samples is partitioned into K 1 phases, and at the end of each phase, SR discards the empirical worst arm from the candidate set. In each phase, SR uniformly samples the arms in candidate set. The lengths of phases are set as follows. Define log/ := 1/ + >x E. The candidate set is denoted by C2 when it has j > 2 arms. In the corresponding phase, (i) each arm in Cj is sampled until the round when minsec, (t) reaches T/(jlogK) (recall that (t) the number of times arm has been sampled up round f); (ii) the empirical worst arm, denoted by f,. is then discarded, i.c., Cy-1 C₁ \ } During the last phase, the algorithm equally samples the two remaining arms and finally recommends the arm with higher empirical mean in Cz. The pseudo code is presented in Algorithm 1.
Algorithm 1: SR
initialization CK + [K], t- K;
for = 1...., .....,TT T) T)do do
[j 2 and minkec, (t) 2 jlngk then
l + argminkec, Px (t) (tie broken arbitrarily), C5-1 + C2 (E)), and j + - -1;
end
sample At + argmin (t) (tie broken arbitrarily), update (f)xee, and p((t):
end
la < arg minkec, (T)) and return +- arg maxkec, (T') (tie broken arbitrarily).
We apply the corollary (c) in Section 3.2 improve the existing performance guarantees of SR. To simplify the presentation, we assume wlog that ln > u2 2 2 μK. For j = 2,..., K, define
I3 min inf JEJ
Ed(Ae. AE R KEJ
M min Ag REJ
(8)
where J = (J C [K] =

---

Theorem 2. Let fe E A. Under SR, we have: for = 2...., K, lim 1 log Pull,=1] plogk'
1 2 r
T
r,
Hence, the error probability of SR is upper bounded by lim 7 log FnliiiI 2 minsø1 slogk'
Proof of Theorem 2. Fix j E (....., KJ. Observe that
PA 16, = 1 Σ
F |6, = C, = J| s J max
[2g 1, = J],
JEJ
JEJ
which implies that
1
lim T- T
log
2 min lim JEJ T-400 T
log
(9)
Pg
[2y
=]
P Pule, 1, Cj
as |J| oc.
Since ł is selected at the 8T round' where 0 (1+ +1+ Sk=jt1 k the event {e, 1, Cj J} implies that (ix(TT) E S, w(T) E W}. where
1 Vk E J
S S= ==(EER=
V Ak. vk J) and W w w:
8jlogk
In other words, Pullz = C3 = J ( E S, w(TT) E W). Applying (c) in Section 3.2 with the above S and W yields that -im का log Pa (. is larger than
inf inf ((A, 2 BjlogK NEW SEcI(S)
inf Σ d(As, A S min AB kej
(10)
8jlogk'
KEJ
where the first inequality uses the fact that KL-divergence and the components of w are nonnegative. and the second one is due to the definition (8) of J, Combining (9) and (10) completes the proof.[
The upper bound derived Theorem is tighter than those recently derived in (Barrier et al., 2022). Indeed, for any J E J, since [J] = J. can find at least one index in J at least larger than j. say kj. Hence.
T min inf JEJ AER Stc, d()1, + d(Akgs (k,))
inf AERR Si
d(A,,1)) + d(Aj,
The r.h.s. in the previous inequality corresponds the upper bounds derived by (Barrier et al., 2022).
To simplify the presentation and avoid rather intricate computations involving the KL-divergences, in the remaining of the paper, restrict attention specific classes of reward distributions.
Assumption 1. The rewards are bounded with values in (0, 1). The reward distributions Vi..... VK are Bernoulli distributions such that Va is of mean a, and for any a + b, d(a, b) 2 2(a - b)² (this a consequence of Pinsker's 's inequality as rewards are in (0, 1)).
Under Assumption we have T 2 26, (a direct consequence of Proposition 3 in Appendix D.1), where for j = -.....KK" K,
E inf X
(AR -=)====)220 ; < min AE k=
)
We give an explicit expression of & in Proposition 1, presented in Appendix D.I. More- over, 25, is clearly larger than 2 inf {(A1 += - 11) (p) - Hz)2, and hence minjz1 T3/ (jlogK) 2 minzz1 (M1 - 12,)² /jllog).. This implies that error probability upper bound is better than that derived in (Audibert et al., 2010).
Example 1. To illustrate the improvement brought by Theorem 2 on the performance guarantees of SR, consider the simple example with 3 Bernoulli arms and μ1 = (0.9, 0.1, 0.1). Then min (14 4,)² (j]og3) = 0.16 for the upper bound presented in (Audibert et al., 2010). From Proposition 1, instead we get min;z1 25,/ (flog3) = 0.21.
'To simplify the presentation, ignore cases where 01' is not integer. Refer to Appendix E for details.
7

---

4 Continuous Rejects Algorithms
In this section, we present CR, a truly adaptive algorithm that can discard an arm in any round. We propose two variants of the algorithm, CR-C using a conservative criterion to discard arms and CR-A discarding arms more aggressively. Using the Large Deviation results of Theorem 1, we establish emror probability upper bounds for both CR-C and CR-A.
4.1 The CR-C and CR-A algorithms
As SR, CR initializes its candidate set as Ck [K]. For 2 2, C. denotes the candidate set when it is reduced to arms. When j > 2, the algorithm samples arms in the candidate set C uniformly until a discarding condition is met. The algorithm then discards the empirically worst arm Ej E Cj. i.e. Cj-1 Cj {G}). More precisely, in round t, if there are candidate arms remaining and if {(L) denotes the empirically worst candidate arm, the discarding condition is (t) > maxxec, (t),),, (Ak C,, (t) (t)())) and
ENEC, Na(t)logí T T-Exec, Na(t)
for CR-C:
min (x(t)= Pr()) (t) 2G kEC)))A(())
(11)
ExEC, (tx(t)
(1) G ExEc, (t(tologj Exec, N&(t)
for CR-A:
(12)
j-1
where G(B) = 1/vB- - for all B > O. The idea behind (11) is to keep the probability of discarding the best arm at most smaller than that of SR while using less budget. Note that (12) is easier to achieve than (11). CR-A is hence faster, but at the expense of a higher risk. After discarding Ez. CR will sample the arms in C2 evenly, and recommend the empirical best arm in C2 when the budget is exhausted. The pseudo-code of CR is presented in Algorithm 2.
aggressive than CR-C, and reduces the set of arms to C2
Algorithm 2: CR-C and CR-A
Input: 8g E (0, logK n independent of ' (can be chosen as small one wishes)
initialization
CK + [K], j +- K, sample each arm & [K] once, update (Ne((t)RECC and fi());; for t K ....., [],T] do
sample A + argmin kec, (t) (tie broken arbitrarily), update (t) and p(t);
end
for
[0oT] + I....,T) do {(t) + argminkec, (t) (tie broken arbitrarily); if > 2, (t) > maxsec, (t)t). (vk E Cj. (t) = Nt)))). and (11) (resp. (12)) holds for CR-C (resp. CR-A) then
Ej 5 {(t), Cj-1 CC ( ---1 sample A, + argminkec, (t) (tie broken arbitrarily), update (Na and fu(t);
end
l2 - ((T); return i + argmaxtec, Pu (T) (tie broken arbitrarily).
4.2 Analysis of CR-C and CR-A
As in Section 3.4, μ1 > #2 2 ... 2 μK is assumed wlog and we further define μK+1 = 0. We introduce the following instance-specific quantities needed to state our error probability upper bounds. For j E (2....,K) K), define
j 1 El 14 j
2
5- j
j-1 (m) 111
E Mitt ) j-1
1/
(1
Jy
C = 15+11
j-1
This condition is only imposed simplify analysis. It may be removed.
8

---

Pe j
K
1j+1, and E = inf Σ
(A - ux)² X E [0, 1 A S
min
Ak
k= 1j+1
Here we remark E 2 Eg and by 2 V. These inequalities are proven in Proposition 3 and Proposition 5 in Appendix D.
Theorem 3. Let E [0, 1jk. Under CR-C, limy 00 T log (F is larger than
G 1)(1 (0 E Es
min max
logj
2 min j 2,..,K
jlogK
where 0z E IR is the real number such that 25,(1-a,) = [((1 + Sj) (++))oR(++)) )+}² ,loR)
Theorem 4. Let ça E 10. Under CR-A, lim, 000 T log [+ is larger than
min v, log(l 1)(1- (32M) .4/9. 45²
logi
min j=2....KK K
jlogK
where aj I is the real number such that ( + (2)) Vaj
(+1]]og(1+1) ++1
flogg
Note that Theorem 3 implies that CR-C enjoys better performance guarantees than SR, and hence has for now the best known error probability upper bounds.
Proof sketch. The complete proof of Theorems 3 and 4 are given in Appendices C.I and C.2. We sketch that of Theorem 3. The proof consists in upper bounding F [,, = 1] for E ( KJ. We focus here on the most challenging case where j E {3..... K - 1] (the analysis is simpler when j K, since the only possible allocation is uniform, and when j = 2, since the only possible round deciding &2 is the last round).
To upper bound [ulei 1] using Theorem 1, we will show that it is enough to study the large deviations of the process h(T) for any fixed 0 E [Bu. 1] and to define set S S [0, 1] under which E ((TT)= 1. We first observe that E, = {(TT) restricts the possible values of w(T):: (IT) X2 == f E Σ: 3o E [K] s.t. 2a(1) = .... =.....a.. Zo(i) > Ia(++1) > ... > To(K) > 0}. We can hence just derive the LDP satisfied by (w(OT) on Xj. This is done in Appendix E, and we identify by la rate function leading to an LDP upper bound. By defining
X2)
x E xx : (xoo)lll
0
Σ Io(k)) j. Vi (i. (i...., K}, k=it1
As it is shown in Appendix E.1 that Io(x) xo if x E X2,((0) for j. we may further restrict to X3
Next, we explain how to apply Theorem 1 to upper bound P, pylle, = 1]. J= [J [K] |J
j, 1 E J} as defined in Section 3.4. For all 8, 0 E (0, 1] and J E J, we introduce the sets
Sy(B) X (0, 1].
min d - A 2 ] KEJ.K11
0 Σ KEJ 24 logi
8) z E X2 U (,, (Ak E J, 24 = max 2w),
B
KE[K]
1 0 Enes= 2/
Assume that in round t, l, = f(t) 1,C, and let EnEJ Nx(() < be the number of times arms outside are pulled. While wl1) & X2y(1/T), we have B (t- (l-r) E (0, 1). Using the criteria (11), we observe that
T-T
Σ KK+IJJJ
Σ
4 ((t) = 1,C, = w,w(t) E X3 \ UK Ky. (
ΣΣΣ Pp (a(t) E S, (1 -T)ooog
T
T- w,)(t) E E2 L (1 (o-r))ogj
T -
t=1 TSM.

---

To upper bound the r.h.s. in the above inequality, we combine the results of Theorem 1 and partitioning technique (presented in Appendix G). This gives:
lim T-
log F (A(TT) W(BT) ()(0,3)
0 inf max (xx [o))]
The proof is completed by providing lower bounds of 0 (1)) with various Such bounds are derived in Appendix D. and E. respectively.
(z) and (z) for a fixed E (0,
Example 2. To conclude this section, we just illustrate through simple example the gain in terms of performance guarantees brought by CR compared to SR. Assume we have 50 Bernoulli arms with J1 0.95, f22 = 0.85, 4a 0.2, and jé 0 for l = 4, ..... 50. For SR, Theorem 2 states that with a budget of 5000 samples, the error probability same budget. Theorems 3 and 4 state that the enror probabilities of CR-C and CR-A do not exceed 6.40 x 10 and 6.36 x 10 respectively.
SR does not exceed 1.93 x 10-3, With the
We note that in general, we cannot say that one of our two algorithms,, CR- or CR- A. has better guarantees than the other. This is demonstrated in the problem instances presented in Appendix K. and K.4.
5 Numerical Experiments
We consider various problem instances to numerically evaluate the performance of CR. In these instances, we vary the number of arms from 5 55; the shape of the arm-to-reward mapping. For each instance, we compare CR to SR, SH, and UGapE.
Bernoulli distributed rewards, and vary
Most of our numerical experiments are presented in Appendix K. Due to space constraints, we just provide an example of these results below. In this example, we have 55 arms with comver arm-to-reward mapping. The mapping has 10 steps, and the m-th step consists of m arms with same average reward, equal to & 3 in, Table presents the error probabilities averaged over 40, 000 independent runs. Observe that CR A performs better than CR- C (being aggressive when discarding arms has some benefits), and both versions of CR perform better than SR and all other algorithms.
Table 1: Error probability (in %).
T 3, 000
T
4, 000
5,
000
UGapE
(Gabillon et al., 2012)
24.7
21.3
18.9
SH
Karnin et al. (2013)
10.2
5.9
3.2
SR
Audibert et al. (2010)
5.5
2.8
1.3
CR C
(this paper)
7.1
2.6
1.1
CR-A
(this paper)
4.7
1.6
0.6
6 Conclusion
In this paper, we have established, in MAB problems, a connection between the LDP satisfied by the sampling process (under any adaptive algorithm) and that satisfied by the empirical average rewards of the various arms. This connection has allowed us to improve the performance analysis of existing best arm identification algorithms, and to devise and analyze new algorithms with an increased level of adaptiveness. We show that one of these algorithms CR-C has better performance guarantees than existing algorithms and that it performs also better in practice in most cases.
Future research directions include: (i) developing algorithms with further improved performance guarantees can the discarding conditions of CR be further optimized? (ii) Enhancing the Large Deviation analysis of adaptive algorithms under which conditions, can we establish a complete LDP of the process h2(t) {ww()) (((t)) Answering this question would constitute a strong step towards characterizing the minimal instance-specific error probability for best arm identification with fixed budget. (iii) Extending our approach to other pure exploration tasks: top-m arm identification problems (Bubeck et al., 2013), best arm identification in structured bandits (Yang and Tan, 2022; Azizi et al., 2022), best policy identification in reinforeement learning.
10

---

Acknowledgements
The authors would like to express their gratitude Guo-Jhen Wu for his invaluable discussion during the initial stages of this project. R.-C Tzeng's 's research is supported by the ERC Advanced Grant REBOUND (834862), A. Proutiere is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, and Digital Futures.
References
Ariu, K., Kato, M., Komiyama, McAlinn, K., and Qin, C. (2021). Policy choice and best arm identification: Asymptotic analysis of exploration sampling.
Audibert, J.-Y. Bubeck, S., and Munos, R. (2010). Best arm identification in multi-armed bandits. In COLT, pages 41-53. Citeseer.
Azizi, M., Kveton, B., and Ghavamzadeh, M. (2022). Fixed-budged best-arm identification in structured bandits. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IICAI-22, pages 2798-2804.
Barrier, A., Garivier, A., and Stoltz, G. (2022). On best-arm identification with a fixed budget in non-parametric multi-armed bandits. arXiv preprint arXiv:2210.00895.
Berge, C. (1997). Topological Spaces: including treatment of multi-valued functions, vector spaces, and convexity. Courier Corporation.
Boyd, S., Boyd, S. P., and Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
Bubeck, S., Wang, T., and Viswanathan, N. (2013). Multiple identifications in multi-armed bandits. In International Conference on Machine Learning, pages 258-265. PMLR.
Budhiraja, A. and Dupuis, P. (2019). Analysis and approximation of rare events. Representations and Weak Convergence Methods. Series Prob. Theory and Stoch. Modelling. 94.
Carpentier, A. and Locatelli, A. (2016). Tight (lower) bounds for the fixed budget best arm identifica- tion bandit problem. In Conference on Learning Theory, pages 590-604. PMLR.
Combes, R., Magureanu, S., and Proutiere, A. (2017). Minimal exploration in structured stochastic bandits. In Proc. of NeurIPS.
Degenne, R. (2023). On the existence of a complexity in fixed budget bandit identification. In Proc. of COLT.
Degenne, R. and Koolen, W. M. (2019). Pure exploration with multiple correct answers. In Proc, of NeurIPS.
Dembo, A. and Zeitouni, O. (2009). Large deviations techniques and applications, volume 38. Springer Science & Business Media.
Dupuis, P. and Ellis, R. S. (2011). A weak convergence approach the theory of large deviations. John Wiley & Sons.
Ellis, R. S. (1984). Large deviations for a general class of random vectors. The Annals of Probability, 12(1):1-12.
Gabillon, V., Ghavamzadeh, M., and Lazaric, (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25.
Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Proc. of COLT.
Garivier, A., Ménard, P., and Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2)3377-399

---

Gärtner, J. (1977). On large deviations from the invariant measure. Theory of Probability & Its Applications, 22(1):24-39.
Glynn, P. and Juneja, (2004). large deviations perspective on ordinal optimization. In Proceedings of the 2004 Winter Simulation Conference, 2004., volume 1. IEEE.
Karnin, Z.,, Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR.
Kaufmann, E., Cappé, O., and Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. JMLR.
Kaufmann, E. and Koolen, W. (2018). Mixture martingales revisited with applications sequential tests and confidence intervals. arXiv preprint arXiv:
Komiyama, J. (2022). Bayes optimal algorithm is suboptimal in frequentist best arm identification. arXiv preprint arXiv:2202.05/93.
Komiyama, J., Tsuchiya, T., and Honda, J. (2022). Minimax optimal algorithms for fixed-budget best arm identification. In Advances in Neural Information Processing Systems.
Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics.
Magureanu, S., Combes, R., and Proutiere, A. (2014). Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999. PMLR.
Qin, C. (2022). Open problem: Optimal best arm identification with fixed-budget. Conference on Learning Theory, pages 5650-5654. PMLR.
Russo, D. (2016). Simple bayesian algorithms for best arm identification. In Annual Conference Learning Theory. PMLR.
Varadhan, S. S. (2016). Large deviations, volume 27. American Mathematical Soc.
Wang. P.-A., Ariu, K., and Proutiere, A. (2023). On uniformly optimal algorithmss for best arm identification in two-armed bandits with fixed budget. arXiv preprint arXiv:2308.12000
Wang, P.-A., Tzeng, R.-.,, and Proutiere, A. (2021). Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems, 34.
Yang, J. and Tan, V. (2022). Minimax optimal fixed-budget best arm identification in linear bandits. Advances in Neural Information Processing Systems, 35:12253-12266
12


Reviews:
[{"review_id": "nUDo2gFXOH", "reviewer": "Reviewer_vyXZ", "summary": "This paper contributes an important tool geared towards closing the performance gap for best arm identification problems under the fixed budget setting, a well-known open problem in the area. In particular, the result is a large deviation bound on the sample means of the arm rewards as a function of any large deviation bound on the empirical means of the number of times each of the arms is pulled under a fixed policy (which could very well be adaptive). Since for popular policies such as successive rejects, the latter bound could be easier to specify due to their structure (batched pulls, etc.), the result can be used to derive tighter upper bounds on the probabilities of misidentification under such policies. The paper illustrates this power by deriving a tighter upper bound on the probability of misidentification for the successive rejects (SR) policy and derives a new policy called continuous rejects (CR) that achieves a smaller probability of error.", "questions": "Hasn't it been shown, as stated in the open problem paper by Chao Qin, that the conjecture in Equation (1) is false? Am I missing something? ", "limitations": "The paper addresses a specific problem in bandits that does not seem to have any more nefarious use cases than typical optimization models.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "-  While it doesn't seem surprising that such a result would hold, I think this is a solid result that I anticipate being of importance not only for the best arm-identification problem but as a general tool in the bandit analysis toolkit.\n- The paper is very well written.", "weaknesses": "- I don't think there are any major weaknesses except stating that the considered problem is the \"last fundamental open problem in MABs\" is quite presumptuous. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and positive feedback.\n\n1. About \n> I don't think there are any major weaknesses except stating that the considered problem is the \"last fundamental open problem in MABs\" is quite presumptuous.\n\nWe agree and we will rephrase.\n\n2. About \n> Hasn't it been shown, as stated in the open problem paper by Chao Qin, that the conjecture in Equation (1) is false? Am I missing something?\n\n(1) is the lower bound conjectured by Kaufmann and Garivier in [17] (references are from the supplementary material). No one has proven yet whether (1) is a correct lower bound or not (as far as we are aware). Now the conjecture stated by Chao Qin in [28] (Conjecture 2 in [28]) is whether there exists a single algorithm with error rate matching the r.h.s. of (1) for *all* instances. This last conjecture does not hold as mentioned in [28] – this is a consequence of results from [1]. Recently, Degenne [12] (published in COLT 2023) also proved that the conjecture was false for 2-arm bandit problems with Bernoulli rewards.\n"}, {"review_id": "2DzAmOpabs", "reviewer": "Reviewer_zb7g", "summary": "This paper considers the problem of best arm identification with fixed budget, where the learner pulls an arm in each round for $T$ rounds, then outputs a candidate for the arm with the largest mean. The objective is to minimize the probability of mis-identification. Characterizing the instance specific complexity for this problem is an open question. The authors present a more refined analysis based on large deviation principles resulting on a refined upper bound for the successive rejects (SR) algorithm. Further, the authors present two algorithms based on the previous analysis where arms elimination is done following conditions rather than at pre-specified rounds as in SR. ", "questions": "Minor comment/question: line 147, about returning the arm with the highest empirical reward: can't we have a scenario in SR algorithm where the at the end (when the budget is exhausted), the empirical mean of the wining arm is smaller than the empirical mean of the first eliminated arm (which was computed only during the first epoch) ?  If true, the latter statement is not valid.", "limitations": "  ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized, and the discussions are interesting. Using LDP for best arm identification appears to be novel.", "weaknesses": "The presented bounds are not easy to read (especially in Section 4). It would be nicer to provide a more detailed discussion about the comparisons with bounds in the literature.\n\nSome theorem statements (Proposition and Theorem 1) don't clearly state the assumptions made.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and positive feedback.\n\n1.\tAbout \n> The presented bounds are not easy to read (especially in Section 4). It would be nicer to provide a more detailed discussion about the comparisons with bounds in the literature.\n\nThanks for this remark. We will add a more detailed discussion to compare our bounds to those of the literature (using the extra space allowed in the final version of the paper). From the results of Theorem 3, we can conclude that CR-C has better performance guarantees than SR, the state-of-the-art algorithm. Indeed, one can readily see that the bound derived in Theorem 3 for CR-C is higher than $2\\xi_j/j\\overline{\\log}K$, which is the improved bound for SR presented in Section 3. We will make this clear in the paper. \n\nIn general, we cannot say that one of our two algorithms, CR-A or CR-C, is better than the other. We illustrate this below for the instances presented in Appendix J.1 and J.4. For the instances in J.1, we can easily prove that the performance guarantees for CR-C is better than that those for CR-A. On the contrary, for the instances in J.4, CR-A has better performance guarantees than CR-C. We will add the above discussion to the paper.\n\n\n \n2. About \n> Minor comment/question: line 147, about returning the arm with the highest empirical reward: can't we have a scenario in SR algorithm where the at the end (when the budget is exhausted), the empirical mean of the wining arm is smaller than the empirical mean of the first eliminated arm (which was computed only during the first epoch) ? If true, the latter statement is not valid. \n\nYes, you are right. More precisely, in Line 147, we state that *if* the algorithm returns the arm with the highest empirical reward, then the error probability is $P_{\\mu}[\\hat{\\imath}\\neq 1(\\mu)]=P_{\\mu}[\\hat{\\mu}(T)\\in Alt(\\mu)]$. As you noticed, algorithms (SR, SH, or CR) may not always return the best empirical arm, but we accounted for this possibility in our analysis. To understand why, please refer to the proof of Theorem 2 for example: the analysis consists in upper bounding the probability of eliminating the best arm in each phase of the algorithm. This probability is first connected to an event related to the empirical rewards of the arms, and then the probability of this event is bounded using Theorem 1 (our Large Deviation result).    \n"}, {"review_id": "6MmutJziij", "reviewer": "Reviewer_64fe", "summary": "This paper studies the problem of best arm identification (BAI) with fixed budget (FB), with bandit feedback on K arms. The asymptotically optimal sample complexity for this problem has been of significant interest recently and has proved surprisingly difficult to understand compared to the fixed confidence problem. \n\nThis paper gives a new upper bound on the failure probability of a given algorithm, and uses it to study specific algorithms: successive rejects and continuous rejects. \n\n", "questions": "I didn't see the relevant Polish spaces specified anywhere.\n\nI suggest using i_* instead of \\hat i, since it is hard to see the latter.\n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper achieves new large deviation bounds for the failure probability of specific algorithms using a new LDP bound, and shows their superior empirical performance at minimizing failure probability. The analysis of the successive rejects algorithm is nice and improves over previous results. The required analyses for the continuous rejections (in the appendix) seem to be quite involved, but show even better performance guarantees.\n\nThe writing is pretty good too.", "weaknesses": "The result seem a little incremental as they most concern specific algorithms; the paper does not seem like it will help much toward an eventual solution to  the general FB-BAI problem. But getting better non-sharp bounds is still nice (and a general solution might be abstract enough not to subsume them).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and positive feedback.\n\n1. About \n> The result seems a little incremental as they most concern specific algorithms; the paper does not seem like it will help much toward an eventual solution to the general FB-BAI problem. But getting better non-sharp bounds is still nice (and a general solution might be abstract enough not to subsume them).\n\nWe believe that our general LDP result (Theorem 1) is not incremental, for it allows us to analyze in a simple way various algorithms and to design new algorithms with improved performance. It allows us to analyze truly adaptive algorithms, and we plan to search for even more adaptive algorithms than CR. Now, solving the general FB-BAI problem (finding a problem-specific lower bound of the error rate and a matching algorithm) seems actually very hard if not impossible. This was recently discussed in Degenne [12] (reference is from the supplementary material).\n\n2. About \n> I didn't see the relevant Polish spaces specified anywhere.\n\nWe mentioned Polish spaces (separable and complete metric spaces) because this is the traditional (and the most general) framework to define and work with Large Deviation principles (see the book [30]). Here, you are right, we just work with Euclidian spaces; we will clarify this.\n"}, {"review_id": "UOzx6eg5ug", "reviewer": "Reviewer_ooBf", "summary": "The authors study the problem of best arm identification with fixed budget in the $K$-arm bandit problem. Using tools from the large deviation literature, they propose a new methodology to analyse algorithms for this problem. They apply this method to a state of the art algorithm and obtain sharper asymptotical bounds on the error probability of this algorithm. They propose two new algorithms and establish bounds on their error probability, showing that one of them is asymptotically better that existing algorithms. Finally, they illustrate the good performances of their algorithms by extensive numerical simulations.", "questions": "Could you please discuss more the theoretical guarantees of the two algorithms? Is there settings where one would perform better than the other, and vice-versa?\n\nCould you perhaps add an introduction to your Appendix, to present its content and the different aspects of the problem that have been postponed there?", "limitations": "The authors adequately address the limitations of their work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Clarity : This article is very well written and enjoyable to read. The literature review is complete and well presented. Methods and results are clearly introduced and discussed, and the sketches of proofs are insightful. The level of detail in the evidence greatly helps the reader, and the authors' efforts to make this article self-contained are commendable.\n\nQuality : This article introduces important new methodological tools and theoretical results, that are supported by rigorous proofs.\n\nOriginality : The authors study a central problem in the bandit literature from a new perspective, leveraging tools from large deviation literature to obtain sharper results and develop new algorithms.\n\nSignificance : The error bounds in this paper improve over existing results on a central question, and the methodology used to obtain them could be applied to study other related problems.", "weaknesses": "Why the authors discuss the motivations behind the two algorithms they introduce, they do not compare their theoretical guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and positive feedback.\n1. About \n> Could you please discuss more the theoretical guarantees of the two algorithms? Is there settings where one would perform better than the other, and vice-versa?\n \nIn general, we cannot say that one of our two algorithms, CR-A or CR-C, is better than the other. We illustrate this below for the instances presented in Appendix J.1 and J.4. For the instances in J.1, we can easily prove that the performance guarantees for CR-C is better than that those for CR-A. On the contrary, for the instances in J.4, CR-A has better performance guarantees than CR-C. We will add the above discussion to the paper. We introduced these two algorithms, CR-A and CR-C, because we wanted to design algorithms that discard arms with different levels of aggressivity. \n\n2. About \n> Could you perhaps add an introduction to your Appendix, to present its content and the different aspects of the problem that have been postponed there?\n\n\nThanks for this suggestion. We agree that it could be nice to have a summary of the appendices. We will add an introduction before the appendices to state the role and content of each of them.\n\n"}]

Author rebuttal:

Meta-review: The reviewers came to consensus that this paper makes a good progress on the problem of fixed-budget best arm identification. I agree with these opinions and please polish the manuscript addressing the minor concerns raised by the reviewers (mostly on presentation).
Decision: Accept (spotlight)