An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond
Authors: Marc Jourdan
Rémy Degenne
Emilie Kaufmann
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandits
pure-exploration
epsilon best arm identification
Top Two algorithm
anytime
TL;DR: We have studied approximate best arm identification in multi-armed bandits, in the fixed-confidence, fixed-budget and anytime settings.

Abstract: We propose EB-TC$\varepsilon$, a novel sampling rule for $\varepsilon$-best arm identification in stochastic bandits.
	It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC$\varepsilon$ is an *anytime* sampling rule that can therefore be employed without modification for fixed confidence or fixed budget identification (without prior knowledge of the budget).
	We provide three types of theoretical guarantees for EB-TC$\varepsilon$.
	First, we prove bounds on its expected sample complexity in the fixed confidence setting, notably showing its asymptotic optimality in combination with an adaptive tuning of its exploration parameter.
	We complement these findings with upper bounds on its probability of error at any time and for any slack parameter, which further yield upper bounds on its simple regret at any time.
	Finally, we show through numerical simulations that EB-TC$\varepsilon$ performs favorably compared to existing algorithms for different approximate best arm identification tasks.

An E-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond
Mare Jourdan
Rémy Degenne
marc. jourdng inria. fr
Emilie Kaufmann
emi Miieiee.o am..ie..aaffann@uuiii. www.ffaannnuiii--illlle
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRISIAL, F-59000 Lille, France
Abstract
We propose EB-TC,, novel sampling rule for e-best arm identification in stochas- tie bandits. is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC, is an anytime sampling rule that can therefore be employed without modification for fixed confidence or fixed budget identification (without prior knowledge of the budget). We provide three types of theoretical guarantees for EB-TC, First, we prove bounds on its expected sample complex- ity in the fixed confidence setting, notably showing its asymptotic optimality in combination with an adaptive tuning of its exploration parameter. We complement these findings with upper bounds its probability of error at any time and for any error parameter, which further yield upper bounds on its simple regret at any time. Finally, show through numerical simulations that EB-TC, performs favorably compared to existing algorithms, in different settings.
Introduction
In pure exploration problems, the goal is to answer a question about a set of unknown distributions (modelling for example the efficacy of a treatment) from which we can collect samples (measure its effect), and to provide guarantees pre-defined constraints, e.g. the maximal budget might be fixed advance or the error made should be smaller than fixed admissible error. However, in many cases, fixing such constraints in advance can be challenging since a "good" choice typically depends on unknown quantities. Moreover, while decide to
the candidate answer. Practitioners might have different
the budget is limited in clinical trials, it is often not fixed beforehand. The physicians stop earlier or might obtain additional fundings for their experiments. In light of those real-world constraints, regardless of its primal objective any strategy for choosing the next treatment should ideally come with guarantees on its current candidate answer that hold at any time.
We formalize our investigations in the well-studied stochastic bandit model [4, 29], in which learner interacts sequentially with an environment composed of K arms, which are unknown distributions (и))εT with finite means (μ4)εTи)- At each stage E N, the learner chooses an arm I, E [K] based on the samples previously observed and receives sample X,, random variable with conditional distribution Vr, given 7,- It then proceeds to the next stage. An algorithm for the learner in this interaction is specified by sampling rule, a procedure that determines 7, based on previously observed samples. Formally, the sampling rule defines for all E a function from ([K) n1 to the probability distribution on [K]. which is measurable with respect to the o-algebra F, == heee---) We call that o-algebra history before n.
Identification tasks We focus on best arm identification (BAI). In that task, the goal of the algorithm is to find which of the arms has the largest mean, and to do so with small probability of error, as
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

quickly as possible, If several arms have means very close to the maximum, finding the one with the highest mean might be difficult. However practice we are often satisfied by any good enough arm, in the sense that its mean is greater than M4 where 14, = [ 14. This is the e-BAI task. Our results can also be adapted to the multiplicative e-BAI task, in which all means are non-negative and we want to find an arm with mean ,4; 2 (1 e),,, [19] (see Appendix for details).
Now that we have a (for now informal) goal, we need to complement the sampling rule with a recommendation rule that specifies which arm is the candidate returned by the algorithm for the best arm. We follow [5] and define that rule for all stages: for all n E N, we denote by in this Fn-measurable function from ([K) IR)"=1 1 to [K]. We call algorithm the combination of sampling and recommendation rule.
There are several ways to evaluate the performance of an algorithm for 8-BAI. Let (u) = (i E [K] μ4 2 u4+ - }) be the set of 6-good arms. The probubility of e-eroo or the recommendation at n is defined as (a & (u)). Introduced in [1], the expected simple regret is defined as [y, - [,,,,]; and is independent of any parameter e. Based on those notions, several setting are studied in the bandit identification literature.
Performance criteria
Fixed confidence: we augment the algorithm with a stopping rule, stopping time Te.s with respect the history of samples and we impose that the algorithm should be (e, PPAC. That is, its probability of e-error at T2,5 must satisfy (T < +00, fTu. & Ie (w)) S d. The parameter is known to the algorithm. An algorithm is judged based on its expected sample complexity &l the expected number of samples it needs to collect before it can stop and return a good arm with the required confidence.
Fixed budget: we run the algorithm until predefined time T and we evaluate it based on the probability of error at T. This setting has been mostly studied for E = 0 [1, 25], but [41] present the first bounds for e > 0 for algorithm that is actually agnostic to this value.
Simple regret minimization: we evaluate the expected simple regret at T' [5, 41].
Simple regret is typically studied in an anytime setting: [5] contains upper bounds on the simple regret at time for any E N Similarly, [23] propose the anytime exploration setting, in which they control the error probability IP (fn ii.) for exact best arm identification. Interestingly, the authors build depends on the risk parameter 6, which they replace by a sequence 6n. The algorithm that we study in this paper, motivated by the fixed-confidence e- -BAll problem, will already be anytime, which means that it does not depend on a given final time T or a confidence level 6. We shall analyze its sample complexity in the fixed confidence setting but thanks to the anytime property will also be able to prove guarantees on its probability of c-error for every & 2 0 and its simple regret at any time.
algorithm for the fixed-confidence setting, LUCB [24], whose sampling rule
Additional notation and assumption We denote by D a set to which the distributions of the arms are known to belong. We suppose that all distributions in D are L-sub-Gaussie
distribution vo is usub-Gaussian if it satisfies Ex [c>(X (X-xRXxxxa -Rx [X]] < e²²/2 for all À E R. For example, all distributions bounded in |-1, 1] are 1-sub-Gaussinn Gaussian. Let us denote by i" (p) = arg | (4, the
set of arms with largest mean (i.e. i" (()) Io(P)). Let A; == ,4, 14; denote the sub-optimality gap of arm i. We denote by Ax C I K the simplex of dimension K -
eoxeddconfidence e-best-arm identification Let 2 0 and 8 e (0, 1) be fixed error and confidence parameters. In the fixedccofidence E-BAI setting [31, 13, 35, 16), the probability of error of an algorithm is required to be less than 8 for all instances v E DDK" That requirement leads to an asymptotic lower bound on the expected sample complexity on any instance.
Lemma 1 ([10), For all ()PC) algorithms and all instances v4 =N(u,, 1) with μ E RK, ET|Tc
lim infg-v log(1/8) 2 Te (p) where Te (1) = min (x) min Te,s(H, i) with
1 114 -1 +)2
Te,,(u, i)=== max min WEAR. jf1
(I)
1/3 + 1/w;
We say that an algorithm is asymptotically (resp. 3-)optimal if its sample complexity matches that B.
lower bound, that is if lim sup log(1/8)
< (r) (resp. (1))(1) min:ez,()) Te,s(,, i)). Note
2

---

that the expected sample complexity of an asymptotically 1/2-optimal algorithm is at worst twice higher than that of any asymptotically optimal algorithm since Te T2,1/2(H) S 2T (4) [34].
The asymptotic characteristic time Tú (p) ) is of order Σn= min{= 2. It is computed as min- imum over all s-good arms i Ie (p) of an arm-specific characteristic time, which can be interpreted as the time required to verify that is s-good. Each of the times m00.) ( i) correspond to the complexity of a BAI instance (i.e. e-BAI with & 0) in which the mean of arm increased by (Lemma 9). Let we,3 (1, i) be the maximizer of (1). In [16], they show that Te (p) = (x (H, and (1)) = (1,,, (*), where E i" (p) and (3* (i*) = arg min (E(0,)) (1,
8*). For E = 0,
similar lower bound to Lemma holds for all [15]. Lower bounds of order Σx= A,2 log log A, (independent of 6, but with stronger dependence in the gaps) were also shown [17, 6, 38, 7J. Note that the characteristic time for e-sub-Gaussian distributions (which does not have a form as "explicit" as (1)) is always smaller than the ones for Gaussian having the same means and variance o².
good algorithm should have an expected sample complexity as close as possible to these lower bounds. Several algorithms for (c-)BAl are based on modifications of the UCB algorithm [24, 17, 14]. Others compute approximate solutions to the lower bound maximization problem and sample arms in order to approach the solution [15, 11, 39]. Our method belongs to the family of Top Two algorithms [34, 36, 21J, which select at each time two arms called leader and challenger, and sample among them. It is the first Top Two algorithm for the E e-BAI problem (for > 0).
Any time and uniform e-error bound In addition to the fixed-confidence guarantees, we will prove bound the probability of error for any time and any error é, similarly the results of [41]. That is. we bound Pp (6, & Ie (μ)) for all n and all E. This gives bound on the probability of error E-BAL, and a bound on the simple regret of the sampling rule by integrating: [,, [i, PP,(t, & (x))
The literature mostly focuses on the fixed budget setting, where the time T at which evaluate the error probability is known and can be used as a parameter of the algorithm. Notable algorithms are successive rejects (SR, [1]) and sequential halving (SH, [25]). These algorithms can be extended to not depend on T by using a doubling trick [23, 41J. That trick considers a sequence of algorithms that run with budgets (Tk)), with T&+1 27); and Ti 2K [log2 K1. Past observations are dropped
when reaching T3. and the obtained recommendation is used until the budget Ts+1 is reached.
1.1 Contributions
We propose the EB- EB-TC2, algorithm for identification in bandits, with slack parameter Eu 0, originally motivated by Eu- BAI We study its combination with a stopping rule for fixed confidence e- -BAI (possibly with Eu =) and also its probability of eиror and simple regret at any time.
EB-TCe, performs well empirically compared to existing methods, both for the expected sample complexity criterion in fixed confidence e B-AAI and for the anytime simple regret criterion. addition easy to implement and computationally inexpensive our regime.
We prove upper bounds on the sample complexity of EB-TCz, in fixed confidence e-BAI with sub-Gaussian distributions, both asymptotically (Theorem 1) - and for any ó (Theorem 2). In particular, EB-TC, with E > 0 is asymptotically optimal for e-BAI with Gaussian distributions.
We prove a uniform e-error bound valid for any time for EB-TC,, This gives in particular a fixed budget error bound and a control of the expected simple regret of the algorithm (Theorem 3 and Corollary I).
2 Anytime Top Two sampling rule
We propose an anytime Top Two algorithm, named EB- EB-TC,, and summarized in Figure
Recommendation rule Let Nn.s Ete(a-1 1 (I i) be the number of pulls of arm before time n, and Mun ;= N.. Eie ij X (I, = i) be its empirical mean. At time n > K, we recom- mend the Empirical Best (EB) arm in E arg max KK Mn, (where ties are broken arbitrarily).
3

---

1: Input: slack EO > 0. proportion 3 E (0, 1) (only for fixed proportions).
2: Set in E arg [ Mn, i. B, = in and Cn arg BB. Ho -30.
VI/Nn, a...B,+1//0 +1/Nn,
3: Set 8 (B Cx) (T, (B,: C., Cn) + Br /T
/T/TT++i n+1 BB Cn) with [fixed]
(i, = 3 or [IDS] (i = N + Nnn) and Tu+1 (Bn, Cn) = (Bn Cp) +
4: Set In = Cn if No.C, S (1 - 3n+1 (Bn, Cn)) (Bn, Cn), otherwise set I = Bn
5: Output: next arm to sample 7, and next recommendation in-
Figure 1: EB-TC,, algorithm with fixed IDS proportions.
2.1 Anytime Top Two sampling rule
We start by sampling each arm once. At time n > K, a Top Two sampling rule defines a leader Ba E [K] and challenger Cn * BB. It then chooses the arm to pull among them. For the leader/challenger pair, we consider the Empirical Best (EB) leader B in and, given a slack Eo > O, the Transportation Cost (TCz.) challenger
Pn Mn. + Eu
CTCE E arg min is D
(2)
//NN..BW + 1/Nn,
The algorithm then needs to choose between B, and Cn. In order to do so, we use a so-called
tracking procedure [15]. We define one tracking procedure per pair of leader/chhllengerr (i.j) E [K]a such that * j. hence we have K(K 1) independent tracking procedures. For each pair (i. of leader and challenger, the associated tracking procedure will ensure that the proportion of times the
algorithm pulled the leader i remains close to target average proportion (i. (0, 1). At each round n, only one tracking rule considered, i.c. the one of the pair (i.j) = (Bn, C.)).
We define two variants of the algorithm that differ in the way they set the proportions (i. j). Fixed proportions set (i. = B for all j) fixed beforehand.
[K]² where B 10, is
ciermation-Directer Selection (IDS) [40] defines Bi, = / -
Nn.) and sets (i, == (i,), Exgin in 1 ((B,, C.) = (i,j)) Be where (i, = Eie(n-1) 11 ((B,, Ct) (i.5) is the selection count of arms (i. as leader/challenger.
Let N%. = Eie(n-1 1 ((B,, Ct) = (i.j), 1 = j) be the number of pulls of arm j at rounds in which i was the leader. We set In Cn if C.C. S (1 Bn- (B,,, Cx)) (Bn, C.) and I, B, otherwise. Using Theorem 6 in [12] for each tracking procedure (i.e. each pair (i,j)) yields
Lemma 2 (proved in Appendix H).
Lemma 2. For all > K, i E [K], i, we have -1/2 S Ni. (1 (1- 111-Bp(i (i.
1
The TC., challenger seeks to minimize an empirical version of a quantity that appears in the lower bound for En- -Bl (Lemma 1). As such, it is natural extension of the TC challenger used in the T3C algorithm [36] for Eo 0. In earlier works on Top Two methods [34, 32, 36), the choice between leader and challenger is randomized: given fixed proportion / E (0. 1), set 7 Bn with probability 3, otherwise I, = C,. [20] replaced randomization by tracking, and [40] proposed IDS to define adaptive proportions 3,, (B,,, Cx)) E (0, 1). In this work we study both fixed proportions with 3 1/2 and adaptive proportions with IDS. Empirically, we observe slightly better performances when using IDS (e.g. Figure 7 in Appendix J.2. While [20] tracked the leader with K procedures, we consider K(K- 1) independent tracking procedures depending on the current leader/challengerr pair.
Choosing Eo [21] shows that EB-TC (i.c. EB-TCa, with slack Eo = 0) suffers from poor empirical performance for moderate d in BAI (see Appendix D.3 in [21] for detailed discussion). Therefore, the choice of the slack En > 0 is critical since it acts regularizer which naturally induces sufficient exploration. By setting Eo too small, the EB-TC,, algorithm will become as greedy as EB-TC and perform poorly. Having Eg too large will flatten differences between sub-optimal arms, hence it will behave more uniformly. We observe from the theoretical guarantees and from our experiments that it is best to take en = e for e-BAI, but the empirical performance is only degrading slowly for en > e. Taking en < & leads to very poor performance. We discuss this trade-off in more details in our experiments (e.g. Figures 5, and 7 in Appendix 1.2.1). When tackling BAI, the limitation of EB-TC can be solved by adding implicit exploration mechanism in the choice of the leader/challenger

---

pair. For the choice of leader, we can use randomization (TS leader [34, 32, 36]) or optimism (UCB
leader [20]). For the choice of the challenger, we can use randomization (RS challenger [34] or penalization (TCI challenger [21], KKT challenger [40] or El challenger [32]).
Anytime sampling rule EB-TC is independent of budget of samples T or a confidence pa- rameter 8. This anytime sampling rule be regarded as stream of empirical means/counts (which could trigger stopping) and a stream of recommendations 8, = i (J(n)) These streams can be used by agents with different kinds of objectives. The fixed-confidence setting couples with stopping rule to be (e, 6)-PAC. It can also be used to get an e-good recommendation with large probability at any given time n..
2.2 Stopping rule for fixed-confidence e-best-arm identification
In addition to the sampling and recommendation rules, the fixed-confidence setting requires stopping rule. Given an error/confidence pair, the GLR, stopping rule [15] prescribes to stop at the time
Te.6 inf K|
Un. Mn,i E VI/Nn... 1/Nn, iffin
min
22cnn 1,6) with in i" (px)
where : Nx (0, 1) - R+ is threshold function. Lemma 3 gives threshold ensuring that the GLR,; stopping rule is (E, 6)-PAC for all E 2 0 and ò (0, 1), independently of the sampling rule.
Lemma 3 ([27)). Let s 2 0 and 8 E (), Given any sampling rule, using the threshold
c(n, 6) (log((( 1)/8)/2) + 4loo(( + 1og(n/2))
(4)
with the stopping rule (3) with error/confidence pair (e, 8) yields a (s, 6)-PAC algorithm for sub- Gaussian distributions. The function Cg is defined in (23). satisfies Ca se r + log(x).
3
Fixed-confidence theoretical guarantees
To study z-BAI in the fixed-confidence setting, we couple EB-TC2, with the GLR, stopping rule (3) using error O, confidence 5 E (0, 1) and threshold (4). The resulting algorithm is (c, 0) by Lemma 3. We derive upper bounds on the expected sample complexity E, [Te both in the asymptotic regime of 8 - (Theorem 1) and for finite confidence when en (Theorem 2).
Theorem Let 2 0, Eo > 0 and (3,5) (0, 1)2. Combined with GLRg stopping (3), the EB-TC algorithm is (c, 8)-PAC and it satisfies that, for all v E 'DK with mean μ such that l [(²( = 1,
IDS] lisssiuup Ey, (T.66 8-4
Ey(Te,s
S Too (e) and [fixed Iim sup
log(1/8) S
(1),
log(1/8)
8-40
μi While Theorem holds for all Lub-Gaussian distributions, it is particularly interesting for Gaussian ones, in light of Lemma 1. When choosing = = Eo (i.c. Dev.so (p) = 1). Theorem shows that EB- TC2, is asymptotically optimal for Gaussian bandits when using IDS proportions and asymptotically 3-optimal when using fixed proportions B. We also note that Theorem is not conflicting with the lower bound of Lemma 1, shown in Lemma 11 in Appendix C. Empirically we observe that the empirical stopping time can be drastically worse when taking En < e, and close to the optimal one when en e (Figures 6 and 7 in Appendix J.2.1).
where De.co (1) = (1 maxiz - -4 +
Until recently [40], proving asymptotic optimality of Top Two algorithms with adaptive choice was open problem in BAI. In this work, we prove that their choice of IDS proportions also yield asymptotically optimal algorithms for s-BAL. While the proof of Theorem assumes the existence of unique best arm, it holds for instances having sub-optimal arms with the same mean. This is an improvement compared to existing asymptotic guarantees on Top Two algorithms which rely on the assumption that the means of all arms different [32, 36, 21]. The improvement is possible thanks to the regularization induced by the slack ED > 0.
While asymptotic optimality in the e-BAI setting was already achieved for various algorithms (e.g. e-Track-and-Stonn (TaS) [16], Sticky TaS [10] or L:BAI [19]), none of them obtained non- asymptotic guarantees. Despite their theoretical interest, asympiotic results provide guarantee on the performance for moderate d. Furthermore, asymptotic results on Top Two algorithms require unique best arm regardless of the considered eπror reaching asymptotic (3-)optimality implicitly
5

---

means that the algorithm eventually allocates samples in an optimal way that depends on the identity of the unique best arm, and that requires the unique best arm to be identified. As our focus is s-BAI, our guarantees should only require that one of the e-good arms is identified and should hold for instances having multiple best arms, The upper bound should scale with sg instead of A when Amin is small. Theorem 2 satisfies these requirements.
Theorem 2. Let 5 E (0,1) and Eu > O. Combined with GLR stopping (3). the EB-TC,, algorithm with fixe 3 1/2 is (Eu,8)-Ph)) and satisfies that, for all D with mean μ..
EulTe,,ol - inf max {T (6, + 1, Suee (8)) + +2K2 sE[0,eo]
where Tm.eo () and S uu.eo (5) are defined by
Tu.so (6, = su n 1--12 15 2(1 + 7)2
Σ
Te
1,6) + )
(EI:(u)
Sy.co hi [16(1+ H (8),
(1 + (1 +1
apico (8)
am,co (8)
au.50 (5) = min) T (
min
W 120,2/2(H11))
Eiere()) ( i) (E
where y E (0, 1/2 is an analysis parameter and h h1 2) = 2 t log(( (z + log(y)) as in Lemma 51.
T 3/2 i) and 2/0.1/2 (1, i) are defined in (1) and
(x0)
p,o0 (8)2 + Hp.eo (E) = (E) + ((Ze(M) \ (1)))
Σ
max (8), v2A,13? v2,, (5)
(EIx(H)
with (E) minkgTa (1) AS and C,,5o max (2ax (t) E _0 :0
The upper bound on [T..]] involves Sallivessaddeeeee 5-dependent term T u.oo (6 and ö-independent term Sp.eo (f). The choice of é influences the compromise between those, and the infimum over means that our algorithm benefits from the best possible trade-off. In the asymptotic regime, we take E 0 and y - 0 and we obtain lim Ex (T log(1 1/)) S 2/d" (y))
When j (xx) = 1, we recover the asymptotic result of Theorem 1 up multiplicative factor 2. For multiple best arms, the asymptotic sample complexity is at most factor 2/²² (14) from the 3-optimal one.
Given finite confidence, the dominant term will be Sp.5o (E). For ē 0, we show that Hy.co (0) O(K min(Aming } )), hence we should consider È > 0 to avoid the dependency in Amin. For
Eg. there exists instances such that max (1) 1/2,1/2(1, i) is arbitrarily large, hence Sy.eo (E))
will be very large as well. The best trade-off attained in the interior of the interval (0, so). For
E = 5o/2. Lemma 10 shows that T 1/2 (1, i) = (K/=z)) for all E Zen/((u) and Hy.so (Sa/2)
(K/EE)) Therefore, we obtain an upper bound ((Z)),/(4)) logg
Likewise, Lemma 10 shows that minj We, 1/2.112(41 (n, f)5- 2 (16(K- 2) + 2) for all 220/2((). While the dependency in aueso (2o/2) is milder in E e-BAI than in BAI (as it is bounded away from 0), we can improve it by using a refined analysis (see Appendix E). Introduced in [20], this method allows to clip minjæi 1/2,1/2 i)5 by a fixed value E [0, (K 1>-' 'I for all i E (x)..
Comparison with existing upper bounds The LUCB algorithm [24] has a structure similar to Top Two algorithm, with the differences that LUCB samples both the leader and the challenger and that it stops when the gap between the UCB and LCB indices is smaller than Eo. As LUCB satisfies E, [Fro.s] < H (n) log(H,, (14)/8) + 16 where H.o (P) E. (max (A,, 20 it enjoys better scaling than EB-TCz, for finite confidence. However, since the empirical allocation of LUCB is not converging towards W (R). it not asymptotically 1/2-mptimal. While LUCB has better moderate confidence guarantees, there is no hope to prove anytime performance bounds since LUCB indices depends on 6. In contrast, EB-TC,, enjoys such guarantees (see Section 4).
Key technical tool for the non-asymptotic analysis We want to ensure that EB- EB-TC,, eventually selects only e-good arms as leader, for any error & 2 0. Our proof strategy is to show that the leader is not an s-good arm and empirical means do not deviate too much from the true means, then either the current leader or the current challenger was selected as leader or challenger less than a given quantity. We obtain a bound on the total number of times that can happen.

---

Lemma 4. Let 8 E (0.1) and n K. E= + Tu(i. be the number of times arm i was selected in the leader/challenger pair. Assume there exists a sequence of events (Ar(n, m221> and positive reals (Di(n, se) such that, for all E {K + ,,,,,,, n}, under the event (n,
Die E [K], T((e)) S (n, and Tot1( Tr(i)+1)
(6)
Then, we have - 1 (A, 6)) S EiE[K] Di(n,
To control the deviation of the empirical means and empirical gaps to their true value, we use sequence of concentration events (En,6)n>7 defined in Lemma 45 (Appendix G.2) such that P. < K2ôn where s 2 and 8 E (0, 1]. For the EB-TCe, algorithm with fixed / = 1/2. we prove that, under &n,5. ( (B58 & [1)) is a "bad" event satisfying the assumption of Lemma 4. This yields Lemma 5, which essentially says that the leader is e-good arm except for logarithmic number of rounds.
Lemma 5. Let å E (0, K and & 2 0. Under the event En,5, we have
Σ Σ (n. 2 - 8H (e) (2) 8) 3K² iET. (1)
where f2(n, 8) = log(1/0) + (2 + s) logn and Hp is defined in (5).
Noticeably, Lemma 5 holds for any 2 0 even when there multiple best arms. As ex- pected the number of times the leader is not among the Eu-good arms depends on H H..eo (Eo) =
(K/Eg)) The number of times the leader is not among the best arms depends on Hp.co (0) = O(K(min (min(miin: -2)
Time-varying slack Theorem 1 shows the asymptotic optimality of the EB-TCe, algorithm with IDS for BB- (where Eg > 0). To obtain optimality for BAI, we consider aare-vayyigg slacks (E,)n. where (en)n. is decreasing, E, > 0 and En + 0. A direct adaptation of our asymptotic analysis on Ey [Toss] (see Appendix D). regardless of the choice of (ew)ns one can show that using GLR,, stopping, the (B-TC algorithm with IDS is (0, PPC and is asymptotically optimal in BAL Its empirical performance is however very sensitive to the choice of (Ea)n (Appendix J.2.3).
4 Beyond fixed-confidence guarantees
Could an algorithm analyzed in the fixed-cofiidenc setting be used for the Exedebudget or even anytime setting? This question is especially natural for EB-TC which does not depend on the confidence parameter 8. Yet its answer is not obvious, as it is known that algorithms that have optimal asymptotic guarantees in the fixed-confidence setting be sub-optimal in terms of error probability. Indeed [28] prove in their Appendix C that for any asymptotically optimal (exact) BAI algorithm, there exists instances in which the error probability cannot decay exponentially with the horizon, which makes them worse than the (minimax optimal) uniform sampling strategy [5].
Their argument also applies 8-optimal algorithms, hence EB-TC, with 8 1/2. However, whenever Eg is positive, Theorem 3 reveals that the error probability of EB-TCE, always decays exponentially, which redcems the of optimal fixed-confidence algorithms for relaxed BAI problem in the anytime setting. Going further, this result provides an anytime bound on the probability to recommend an that is not e-optimal, for any error 5 2 0. This bound involves instance- dependent complexities depending solely on the gaps in J.. To state it, we define Cp = H/s E
[K]) as the number of distinct arm means in μ and let C, (6) == (k E [K] μ. 144 A.) be the set of arms having mean gap A, where the gaps are sorted by increasing order 0 = Ai < A2 <
Ac,. For all S 2 let (e) if [ 1)) (with the convention Ac,+1 +00). Theorem shows that the exponential decrease of Py (in (p)) is linear.
Theorem 3. (see Theorem 6 in Appendix F) Let eg > O. The EB-TCc, algorithm with fixed proportions / 112 satisfies that, for all E DK with mean μ1, for all 2 0, for all n > 5K2/2
5K2/2 (8H (=(8H,,c0000))))
Py (Rn $ (x)) S K2e2 logn) n)² exp
where p(z) x - loggæ and (H, (H, are such that H1 HI K K(2 -1 + 35 -2
and K/ 2 11 < Hi(H, < K minjejj max 22, max j+1 2 A//5ot1
A + +30 1 1 for all 1.
7

---

This bound can be compared with the following uniform E-error bound of the strategy using uniform sampling and recommending the empirical best arm:
exp A 4
n2 K
P ( $ Ie(l)) S
Σ iE
- exp
4KA 3, (c)+1
Recalling that the quantity H, Hz( in Theorem is always bounded from below by 2K 2K 1+1 get that our upper bound is larger than the probability of error of the uniform strategy, but the two should be quite close. For example for O, we have
Py (Bn & (e(()) S exp (-0
K K(A min + teu 11)))) (=+()
P. (th ( S exp (-0
KA
-2
Even if they provide a nice sanity-check for the use of a sampling rule with optimal fixed-confidence guarantees for eB-BAI in the anytime regime, we acknowledge that these guarantees far from optimal. Indeed, the work of [41] provides tighter anytime uniform s-error probability bounds for two algorithms: an anytime version of Sequential Halving [25] using doubling trick (called DSH), and an algorithm called Bracketting Sequential Halving, that is designed to tackle a very large with H(e) ste/2j max(29(e)+1 A7 where g(e) (i [K] p 2 p² e}|. Therefore, they can be much smaller than KA, (c(+++1'
number of arms. Their upper bounds are of the form Py (bp & (x)) I exp cxp (n/nn(((e)))))
The BUCB algorithm of [26] is also analyzed for any level of error E, but in a different fashion. The authors provide bounds on its (e, 8) -lvveriifeelle sample complexity, defined the expectation of the smallest stopping time 7 satisfying P(Vt 2 f.in E (p)) 2 1 5. This notion is different from the sample complexity we use in this paper, which is sometimes called verifiable since it is the time at which the algorithm can guarantee that its error probability is less than 5. Interestingly, to prove Theorem 3 first prove a bound on the unverifiable sample complexity of EB-TCc, which valid for all (c, 6), neither of which are parameters of the algorithm. More precisely, we prove that Po (Vn > (e,,(,),((
in E (x)) 2 Olog 1og(1/5)). As this statement is valid for 8 (0, 1), applying for each to 6, such that (e),,, (H, Eo)
for U2, E0) =6-0 SH Ea) log(1/6) -
obtain Theorem 3. We remark that such trick cannot be applied to BUCB to get uniform E-crror bounds for any time, as the algorithm does depend on 6.
Simple regret As already noted by [41], uniform E-error bounds easily yield simple regret bounds. We state in Corollary the one obtained for EB-TC.,. As motivation to derive simple regret bounds, we observe that they readily translate to bounds on the cumulative regret for an agent observing the stream of recommendations (2,) and playing arm én An exponentially decaying simple regret leads to a constant cumulative regret in this decoupled exploration//eplootaiio setting [2, 33].
Corollary 1. Let Eo O. Let p(x) and (H; (o)))E(C,-1) be defined in Theorem 3. The EB-TC
algorithm with fixed B 1/2 satisfies that, for all E DDK with mean ps, for all >>>> 5K2 /2,
(A141 A.) exp (-p n 5K2/2 ))
Eplp. us.. s e22e((2 1og
811;(1,
-
Following the discussion above, this bound is not expected to be sfate-of-the-art, it rather justifies that EB-TC;, with Eo > 0 not too much worse than the uniform sampling strategy. Yet, as we shall see in our experiments, the practical story is different. In Section 5, we compare the simple regret of EB-TC,, to that of DSH in synthetic experiments with a moderate number of arms, revealing the superior performance of EB-TC2g.
Experiments
We assess the performance of the BB-TC,, algorithm on Gaussian instances both in terms of its empirical stopping time and its empirical simple regret, and we show that it perform favorably compared to existing algorithms in both settings. For the sake of space, we only show the results for large sets of arms and for specific instance with j:" (w) 2.
8

---

10
0.15
<-3C
DSR
-EB-TCI
DSH
10
<TTUCB
P. M
Unnffrmm
LUCB
Uniform
0.10
Ex/T
10
E.lu*
0.05
10
10
10 K
10
0.00
0
500
1000
1500
200C
π
Figure 2: (a) Empirical stopping time on "a 0.3" instances for varying K and stopping rule (3)
using (e, 6) = (0.1, 0.01). The BAI algorithms T3C, EB-TCI and TTUCB are modified to be s-BAI ones. (b) Empirical simple regret on instance μ (0.6, 0.6, 0.55, 0.45, 0.3, 0.2), in which EB-TC.,
with slack Ep 0.1 and fixed 3 = 1/2 is used.
Empirical stopping time We study the impact of large sets of arms (up to K 1000) in e-BAI for (e, 5) (0.1, 0.01) on the "a 0.3" scenario of [18] which sets μ4; = ((i ()/(K))])) 1)) for all i E [K]. EB-TC with IDS and slack Eo = E is compared to existing c-BAl algorithms having low computational cost. This precludes algorithms such as e-Track-and-Stop (TaS) [16], Sticky TaS [10] or e-BAI adaptation of FWS [39] and DKM [11]. In Appendix J.2.2, we compare EB-TC, to those algorithms on benchmarks with smaller number arms. We show that EB-TC, performs on par with E- E-TaS and E-FWS, but outperforms E- e-DKM. As Top Two benchmarks with fixed = 1/2, we consider T3C [36]. EB-TCI [21] and TTUCB [20]. To provide a fair comparison, we adapt them to tackle =- BAI by using the stopping rule (3) and by adapting their sampling rule to the TC= challenger from (2) (with penalization log N,,; for EB- BCITC.). We use the heuristic threshold c(n, 5) log(
log n) (8). While it is too small to ensure the (c, 5PC property, it still yields an empirical error which is several orders of magnitude lower than 8. Finally, we compare with LUCB [24] and uniform sampling. For a fair comparison, LUCB uses / 2c(nn 1,6)/Nn, as bonus, which also small yield valid confidence intervals. Our results averaged over 100 runs, and the standard deviations are displayed. In Figure 2a)), we see that EB-TC, performs on par with the 8- e-T3C heuristic, and significantly outperforms the other algorithms. While the scaling in K of e-EB-TCI and LUCB appears to be close to the one of EB-TC,, e-TTUCB and uniform sampling obtain worse one. Figure 2(a) also reveals that the regularization ensured by the TCs challenger is sufficient to ensure enough exploration, hence other exploration mechanisms are superfluous (TS/UCB leader or TCI challenger).
Anytime empirical simple regret The EB-TC,, algorithm with fixed / = 1/2 and Eo = 0.1 is compared to existing algorithms on the instance μ (0.6, 0.6, 0.55, 0.45, 0.3, 0.2) from [16], which has two best arms. As benchmark, we consider Doubling Successive Reject (DSR) and Doubling Sequential Halving (DSH), which are adaptations of the elimination based algorithms SR [1] and SH [25]. SR eliminates one arm with the worst empirical mean at the end of each phase, and SH eliminated half of them but drops past observations between each phase. These doubling- based algorithms have empirical error decreasing by steps: they change their recommendation only before they restart. In Figure 2(b), we plot the average of the simple regret over 10000 runs and the standard deviation of that average (which is too small to see clearly). We observe that EB-TC.,, outperforms uniform sampling, as well as DSR and DSH, which both perform worse due to the dropped observations. The favorable performance of EB-TC is confirmed on other instances from [16], and for "two-groups" instances with varying i (u)) (see Figures 10 and 12).
Supplementary experiments Extensive experiments and implementation details are available in Appendix J. Appendix J.2.1, we compare the performance of EB-TC with different slacks eo for IDS and fixed / = 1/2. In Appendix J.2.2, we demonstrate the good empirical performance of EB-TC,, compared to state-of-the art methods the fixed-confidence e e-BAI setting, compared to DSR and DSH for the empirical simple regret, and compared to SR and SH for the probability of O-error in the fixed- fixed-budget setting (Figure 13). We consider a wide range of instances: random ones, benchmarks from the literature [18, 16] and "two-groups" instances with varying li* (u)).

---

6 Perspectives
We have proposed the EB-TC:, algorithm, which is casy to understand and implement. EB-TC,, is the first algorithm to simultaneously asymptotically optimal the fixed-confidence Bo-BAI setting (Theorem 1), have finite-confidence guarantees (Theorem 2), and have also anytime guarantees on the probability of error any level E (Theorem 3). hence on the simple regret (Corollary 1). Furthermore, we have demonstrated that the EB-TCa, algorithm achieves superior performance compared to other algorithms, in benchmarks where the number of arms is moderate to large. In future work, we will investigate its possible adaptation to the data-poot regime of [41] in which the number of arms is so large that any algorithm sampling each arm once is doomed to failure.
While results hold for general sub-Gaussian distributions, the EB-TCco algorithm with IDS and slack So > 0 only achieves asymptotic optimality for en with Gaussian bandits. Even though IDS has been introduced by [40] for general single-parameter exponential families, it is still an open problem to show asymptotic optimality for distributions other than Gaussians. While our non-asymptotic guarantees on E, [Te..6] and [M, Hi.1 were obtained for the EB-TCe, algorithm with fixed / = 1/2. we observed empirically better performance when using IDS. Deriving similar (or better) mon-symptotii guarantees for IDS is interesting avenue for future work.
Finally, the EB-TC,, algorithm is a promising method to tackle structured bandits. Despite the exis- tence of heuristics for settings such as Top-k identification [40], it is still open problem to efficiently adapt Top Two approaches to cope for other structures such as s-BAI in linear bandits.
Acknowledgments and Disclosure of Funding
Experiments presented in this paper were carried out using the Grid'5000 5000 testbed, supported by scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https//www.grid50000.. by the THIA ANR program "AI PhD@ Lille". The authors acknowledge the funding of the French National Research Agency under the project BOLD (ANR-19-CFF23-0026--) and the project FATE (ANR22-CE23-0016-))
This work has been partially supported
References
[1] J.-Y. Audibert, S. Bubeck, and R. Munos. Best Arm Identification in Multi-armed Bandits, In Conference on Learning Theory, 2010.
[2] O. Avner, S. Mannor, and O. Shamir. Decoupling exploration and exploitation in multi-armed bandits. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1107-1114, 2012.
[3] A. Barrier, A. Garivier, and T. Kocák. A non-asymptotic approach to best-arm identification for gaussian bandits. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 2022.
[4] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Fondations and Trends in Machine Learning, 5(1):1-122, 2012.
[5] S. Bubeck, R. Munos, and G. Stoltz. Pure Exploration in Finitely Armed and Continuous Armed Bandits. Theoretical Computer Science 412, 1832- 1852, 412:1832-1852, 2011.
[6] L. Chen, J. Li, and M. Qiao. Towards instance optimal bounds for best arm identification. Conference on Learning Theory, 2017.
[7] L. Chen, J. Li, and M. Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics, 2017.
[8] Y. Chen and O. Ryzhov. Balancing optimal large deviations in sequential selection. Manage- ment Science, 696)):347733473, 2023.
[9] R. Degenne, Impact of structure on the design and analysis of bandit algorithms. PhD thesis, Université de Paris, 2019.
10

---

[10] R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[11] R. Degenne, W. M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[12] R. Degenne, H. Shao, and W. M. Koolen. Structure adaptive algorithms for stochastic bandits. In International Conference on Machine Learning (ICML), 2020.
[13] E. Even-Dar, S. Mannor, and Y. Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research, 7:1079-1105, 2006.
[14] V. Gabillon, M. Ghavamzadch, and A. Lazaric. Best Arm Identification: Unified Approach to Fixed Budget and Fixed Confidence. In Advances in Neural Information Processing Systems, 2012.
[15] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Proceedings of the 29th Conference On Learning Theory, 2016.
[16] A. Garivier and E. Kaufmann. Non-asymptotic sequential tests for overlapping hypotheses and application near optimal arm identification in bandit models. Sequential Analysis, 40(1): 61-96, 2021.
[17] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. UiIUCB: an Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of the 27th Conference on Learning Theory, 2014.
[18] K. G. Jamieson and R. D. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In Conference on Information Sciences and Systems (CISS), 2014.
[19] M. Jourdan and R. Degenne. Choosing answers in e-best-answer identification for linear bandits. In International Conference Machine Learning (ICML), 2022.
[20] M. Jourdan and R. Degenne. Non-asymptotic analysis of ucb-based top two algorithm. arXiv preprint arXiv:2210.05433 2022.
[21] M. Jourdan, R. Degenne, D. Baudry, R. De Heide, and E. Kaufmann. Top two algorithms revisited. Advances in Neural Information Processing Systems, 2022.
[22] M. Jourdan, R. Degenne, and E. Kaufmann. Dealing with unknown variances in best-arm identification. International Conference on Algorithmic Learning Theory, 2023.
[23] K.-W. Jun and R. Nowak. Anytime exploration for multi-armed bandits using confidence information. In International Conference on Machine Learning (ICML), 2016.
[24] S. Kalyanakrishnan, A. Tewari, P. Auer, and Stone. PAC subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning (ICML), 2012.
[25] Z. Karnin, T. Koren, and O. Somekh. Almost optimal Exploration in multi-armed bandits. In International Conference on Machine Learning (ICML), 2013.
[26] J. Katz-Samuels and K. Jamieson. The true sample complexity of identifying good arms. In International Conference on Artificial Intelligence and Statistics, 2020.
[27] E. Kaufmann and W. M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246): 1-44, 2021.
[28] Komiyama, Tsuchiya, and J. Honda. Minimax optimal algorithms for fixed- -aed-budget best arm identification. In Advances in Neural Information Processing Systems, 2022.
[29] T. Lattimore and C. Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
[30] A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. In International Conference Machine Learning (ICML), 2016.
11

---

[31] S. Mannor and J. Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. Journal of Machine Learning Research, pages 023-648, 2004.
[32] C. Qin, D. Klabjan, and D. Russo. Improving the expected improvement algorithm. In Advances in Neural Information Processing Systems 30 (NIPS), 2017.
[33] C. Rouyer and Y. Seldin. Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits. In Conference on Learning Theory, pages 3227-3249. PMLR, 2020.
[34] D. Russo. Simple Bayesian algorithms for best arm identification. Proceedings of the 29th Conference on Learning Theory (COLT), 2016.
[35] Sabato. Epsilon-best-army identification in pay-per-rewart multi-armer bandits. Advances in Neural Information Processing Systems, 32, 2019.
[36] X. Shang. R. de Heide, E. Kaufmann, P. Ménard, and M. Valko. Fixed-confidence guarantees for bayesian best-arm identification. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[37] D. Shin, M. Broadie, and A. Zeevi. Tractable sampling strategies for ordinal optimization. Operations Research, (000::193--7710 2018.
[38] M. Simchowitz, K. Jamieson, and B. Recht, The simulator: Understanding adaptive sampling in the moderate-confidencc regime. In Conference on Learning Theory, 2017.
[39] P.-. Wang, R.-C. Tzeng, and Proutiere. Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems, 2021.
[40] W. You, C. Qin, Z. Wang, and S. Yang. Information-directed selection for top-two algorithms. The Thirty Sixth Annual Conference on Learning Theory. pages 2850-2851. PMLR, 2023.
[41] Y. Zhao, C. J. Stephens, C. Szepesvári, and K.-S. Jun. Revisiting simple regret: Fast rates for returning good arm. In 40th International Conference Machine Learning (ICML), 2023.
12

---

A Outline
The appendices are organized as follows:
Notation are summarized Appendix B.
In Appendix C, show how the characteristic times and optimal allocations for e-BAI can reduced to the ones of a BAI problem with modified instances (Lemma 9).
The asymptotic upper bound on the expected sample complexity the EB-TCa, algorithm when combined with the stopping rule (4) is proven in Appendix D (Theorem 1).
The non-asymptotic upper bound on the expected sample complexity the EB-TC,,, algorithm when combined with the stopping rule (4) is proven in Appendix E (Theorem 5).
The upper bound on the probability of error and on the simple regret of the EB-TC,, algorithm is proven in Appendix F (Theorem 6), as well as the upper bound on its unverifiable expected sample complexity (Theorem 7).
Appendix G gathers concentration results used for the calibration of the stopping rule (Lemma 3) and control the empirical means and gaps.
Appendix H gathers existing and new technical results which are used for our proofs.
In Appendix I, we discuss the multiplicative notion of e-goodness, propose the EB-TCB al- gorithm and show asymptotic guarantees the expected sample complexity when combined with the appropriate GLR stopping rule (Theorem 8).
Implementation details and additional experiments are presented in Appendix J.
Table 1: Notation for the setting.
Notation
Type
Description
K
N
Number of arms
D
Sub-Gaussian distribution of arm i E [K]
DK
Vector of sub-Gaussian distributions, ;== (ui)sE(K)
R
Mean of arm i [K]
RK
Vector of means, μt := (μ:)iE(K]
Largest mean, μr, : max (4
A;
R
Gap of arm i, A;
μ4, 14
Ex (H)
K
Best arms, i ((4) == arg [[x] 14
R
Additive error of e-good arms
In)
K]
e-Good arms, [=) == (i [K] A, S E)
Te(n), (T)) (H,
R
Asymptotic (8- (B-Jcchaacterrisic time for e-BAI
We (1),, ws (1)), We ae (H, (i)
A
Asymptotic (3-)optimal allocation for e-BAI
K
Number equivalence classes, Cp :=
{1: i [K]H
K
Equivalence class, (i) = [K E [K] H. MI A.}
B Notation
We recall some commonly used notation: the set of integers [n] = (1.-... .n), the complement x and interior X of set X, the indicator function 1 (X) of an event, the probability P, and the expectation E, under distribution v. Landau's notation o, O, Ω and O, the (K 1)ddimensional
probability simplex ÂK { E R w 2 0, ΣiE(K] w; } The functions Ca and go
defined in (23), W_n Lemma 49, h in Lemma 51, is the Riemann function. While Table gathers problem-specific notation, Table 2 groups notation for the algorithms.
13

---

Table 2: Notation for algorithms.
Notation
Type
Description
Bu B
(EB) Leader time
On. CTè
K
(TC Challenger at time n
In
K
Arm sampled at time n
X nn.,,
I
Sample observed at the end of time n, i.e. Nn,, ~ VI
Fn
History before time n, i.e. Fn := a(I,, X1, In X Xnd.)
in
Arm recommended before time
Te,8
N
Sample complexity (stopping time)
c(n, 0)
N
(0, 1)
R
Stopping threshold function Number of pulls of arm before time n
Nu.
N
I
Empirical mean of arm before time Counts of (B,, C+) = (i.j) before time n
(t.
N N
(1)
Counts of E [Br C₂} before time
N
N
Counts of (B,, C, 4,) = j..j. before time n
3
(0,
Fixed proportion
(1,
(0,1)
IDS proportions
(1.5)
(0,1)
Averaged IDS proportions
C Characteristic Times
In Appendix C, we first recall properties satisfied by the ($-)characteristic times and (3-)optimal allocation for the BAI setting with Gaussian bandits. Then, we show how E-BAI problem can be reduced BAI one on modified (and easier) instance.
BAI setting Let E DD with mean IR The (3- ($-)characterriticc times for the fixed-confidence BAI setting with Gaussian bandits N(p, 1) are defined as
max min (#4- 14,
(n))
min (1) with 2Tz(4)= DEAR. 85 1/3 + 1/wn; (E((0.))
see [15, 34] for example. Let denote by (z) and w (1)) their maximizer, which will refer to as (3-)optimal allocations. Note that (T)),, T3 (1)) = (To(4), To,)(1)) and (w" (w), wz(4)) (wo(n), (1))
We recall in the following some fundamental results those quantities (8- >characteristic times and (8-)optimal allocations. Lemma 6 proves that the (3-)optimal allocations are unique, have strictly positive elements, and shows worst-case inequality ( & 27 (n). Lemma 6 also holds for any single-paramett exponential family of distributions and for the non-paraettric family of bounded distributions [21].
Lemma ([15, 34, 21J). (p)) is a singleton and B E (0, 1), then w² (1)) and w (p) are singletons, i.e. the optimal allocations are unique, and w* (μ); > 0 and w (p); > 0 for all i E [K]. Moreover we huve T T (1) < 2T' (μ)) and with 3* = (n)). Additionally, we have H(u) < T (μ) S (H)
where H(p)= = 2 AT2 where A;- = Amin-
For Gaussian bandits, Lemma shows that the (Baaactractiiiiticc times and (3-)optimal allocations be obtained by solving a simpler optimization problem, which is amenable to faster implementation (e.g. Newton's iterates). It also provides upper and lower bound on the optimal allocation of the best arm, and gives hints that tighter worst-case inequality (1)2(4)) < Tr&T (11) might hold.
Lemma 7 ([3, 20]). Assume that (t)) = {i*). Let r(u) and re(μ) be the solution of ()) = and (r) with, for all (1/ mingy (1x- - us)² +00),
(r(r) 3942 (r(u-- 14)2 - 1)2
Σ
1
and pu.(()) = Σ
1 -
T(p p2)²
3
i
14

---

Then, Vy and Pp.8 are convex and decreasing. Moreover,
2r(p)
and Tz(n)= 2r
(n) 1+ Eifi r(ulppr -1
1
For K = 2, Additionally, for all i + it, we have Bwz(H)) = BT3 (1)) - 11) 1.
w² (1) = (0.5, 0.5) and T (1²) = (1)2(1)) 8(11 - -12)2. For K K2 3, we have
1/(VK-1 1) w (N); s 1
Letrx= = 2K/(1 + VK - 1)² E arg min P4 - 13 and x E RR such that x;
P. -yy
Then, we have Tī (1) (p) (p) = (2xx) (i.e. independent of pa- and ps My--) and
Q(1x-2) rk and v.0(1k-2) = 0K-2
Lemma 8 gathers necessary conditions on the (3-)optimal allocations at the equilibrium such as equality of the transportation costs, and link between the squared allocation which was refered as overall balance in [40].
Lemma ([3, 40)). Assume that it (p) = } and (0, Then, for all + ii,
(Hi: - 11)2
and (T) (p.- - p2;)
2T 2T' (μ)
(/Wi( + 1//w((/)))))))))
1/8 + 1/ u// (4)s
Moreover, we have
w² wn()
w" (m))
Reduction of an s-BAI problem to a BAI problem Lemma gives a reduction of a s-BAl problem BAI one on modified instance, which easier. Thanks to Lemma 9, it is possible leverage existing results on T (1)), T3 (J)), w² (H)), w (m) (such as Lemmas 6, 7 and 8) in order to study T. (1), (n), Te, (1, i), We (u), (e))(H) and (e,
Lemma 9. Let p E R E 0 and E [0 and B E (0, 1). For all E Iz(H), we define (e( as (e)) = M1 E for all j # and (=(i); = pl Then, for all i Ix(p), (,, T7 (i)) and Wo,n(11, ()((H(()). Moreover, for all E (p).
Te(w) = (m+((tt) and Te,a(m) (Me(
Moreover, we have (w) Ei (m) wn (i)( and we,)(p) Unerrt (z((E((')).
Proof. For = 0, the result is direct by definition. Let E > and ē E [0, The first part is obtained by definition of Th (M, i), w² 1). Let i" (1) and me (e((t) defined above, hence (it)) {i*}. For all i Ie (H) \ 8 (M), let us denote by X (e the instance such that (( 144 and 11 2.j = 14 - e for all j & i. If p4p- 14 = & then 1 (A ") (1) O (n) \ (i*), otherwise it l () = {i}. We consider the permutation that swaps arm with arm it, By
Moreover, we have that the gaps of (2((" are all strictly smaller than the gaps of Me since 2 A, > 0. Therefore, Lemma 11 of Barrier et al (2022) yields that T (a
symmetry, we have T
(2
(e' ") T (o((
(e" "))
T* (Mee). We have proved that
Vi (x),,,,, ("e(((")) < min (*(6 SET. (M)V)(()))
By symmetry T (ue((t)) is constant for all it E (p)) hence we have shown that
i T:(μ) = T (pe(tt)
It also shows that (u) = UnErm w² w (i)()*)) The same reasoning yields the result for Te.s (p) and we (u).
15

---

e-BAI problems cannot be arbitrarily difficult Lemma 10 shows that, for all i E Ie/2(1), TF,1/2(p, i) cannot be arbitrarily large and min 1/n.1/2 (H, j) cannot be arbitrarily small. The proof relies on Lemma and existing results for BAI.
Lemma 10. Let E > and μ E IR* Then, for all E Le/2((), we have T2,1/((1)) S 32K/2² and minj4 (,,1/2((.0) d); 2 (16(K 2) +
-))+2 2) !
Proof. Let i [1), hence pi z μr 8/2. Let (i) as in Lemma which satisfies that i" (t)) (8). Let is 14 My and A pi m Mg. Then, we have
T1.1/2(14,)) i) (T))(p=(1)) S 27 (1) S 8
Σ (Aij +) E) < (4, +
jE[K]
jE[K]
where we used Lemma 6 for the two first inequality and i E (u) for the last one. Since Aj 2 0, we conclude that (1, i) < 32K/E². Moreover, using Lemma 6, we have T2,/2(1, i) (M= (ue (1)) 2 T" (ps (1)) 2 2 Σ (Ais + +
jE(K]
Likewise, using Lemma 9 and Lemma 7, obtain that, for all j + i,
W2.1/2(177² /2 (()))(())) (M))((e(())(( Pú + +
14 Ui + E ) 14: - μi + 8
2
2
Σ
+1
(g(
where the last inequality uses what we proved above. When μs S μッj the ratio is smaller than one. When uk > Mj, we have u4x 2 us
> 11 2 p4x 8/2, hence μ* 11g S 8/2 and
H4 Hi + 1 + 11. b4 + e/2 2
E/2
14 P4 +
Therefore, we obtain we, 1/.1/2 (w), /2 < 8(K - 2) + 1, which concludes the result.
Lemma 11 links the characteristic times for 8-BAI where E {Eo, E1}.
Lemma 11. Let E TRK such that (1)) 1. Let Eo > E1. Then, for all B (0, we have Te, (Ami 2 2 Te, (p) and (p),A(n) + 2 (x)
Let EO < E1. Then,
Tea (Amax (om)x+Eo)) 2 Ts, (1) max and Temee())(mmxtee))) 2 Te, (Am
Proof. Let it (1) = } Let > E1. Using Lemma 9, we have
(H) (1))))-((AA) (A + = max min Ay(;)
WEAK 1/W,, +/wy with A,(E) 14 14 +e
Amin +
To conclude the first part of the first result, a sufficient condition is to show that Âς(E1) 2 (5())) for all j A it. Direct manipulations show that, for all j + i+,
(x() 2 (y(E))
+
1
Eg E1
2 1
Eg -1
+
p. Mj 2 Amin
μ..
μi + Eg
Amin +
hence the result holds. The same proof can be used to obtain the second part of the first result.
Let Eg < E1. Using Lemma 9, we have
A,(s)²
Mi +
2T (T) (A + =e) = max min WEAK f 1/W,. 1/my with , Amax +
To conclude the first part of the second result, sufficient condition show that Λy(ε1) 2 (E() for all j * it. Direct manipulations show that, for all j # i",
, ( (Eo) =
1 +
2 2
êτ A + ED
p. 14-44 A max
μ4, M1 + Eo
hence the result holds. The same proof can be used to obtain the second part of the second result.
16

---

D Asymptotic analysis
Let Eo 0, 3 E 10 and E (0, 1). In this section, we provide an asymptotic analysis of EB-TCs, slack Eo > 0 combined with the stopping rule (3) with parameters (eo, d). First, we detail IDS proportions in Appendix D.I. Then, we sketch the proof for fixed proportions B in Appendix D.2.
In the following, we consider nab-Gaussian bandit with distribution D having mean parameter E I with unique best arm, i.e. i* (p) = } We restate Theorem below.
Theorem 4 (Theorem 1). Let eo > ε1 and (0, Using the threshold (4) in the stopping rule (3) with slack E1, the EB-TCe, algorithm is (e1, PPCC.. For IDS proportions, it satisfies that, for all E DK such that [i (1¹) 1,
lim sup
Ev (TL.ol
S To (m)
(1
max ViLi"
6o 18-8
2
6-40
(1/6)
μi + E1
Let B (0, 1). For fixed proportions it satisfies that, for all
DD such that lit (n) 1,
litn sup
EulTen log(1/8)
S Ten.
(1
max
Eo E1
2
8-50
14 + E1 if1
Theorem 1 provides asymptotic upper bound on the expected sample complexity of the EB-TCa.. Eo and for Gaussian distributions, combining Lemma and Theorem shows that the EB-TC,, algorithm is asymptotically optimal for BB- when using IDS proportions and asymptotically B-optimal for BB- when using fixed proportions 3. Until recently [40], proving asymptotic optimality of Top Two algorithms with adaptive choice 3 an open problem in the BAI literature. Our work extends their analysis to tackle the e-BAl setting. Compared to previous work, we removed the assumption that sub-optimal arms should have distinct means.
algorithm when combined with the stopping rule (3). When
Considering E * Eg can be interesting when the practitioner decides to tackle e-BAI with an error E which is different from the slack Eo used by the EB-TC,, algorithm. Those situations occur when the practitioner is observing the data collected by the EB-TC algorithm without having control over Theorem show that the resulting sequential hypothesis testing has still asymptotic guarantees the expected sample complexity. Quite naturally, those guarantees are not asymptotically optimal even for Gaussian distributions. The sub-optimality multiplicative gap of IDS proportions (that is, the ratio of the upper bound in Theorem and the characteristic time for -BAI, Te, (p)) is
Teo (11) (Amin + E0)2 Te, (1) (Amin + + 2
Tro (1) (Amax + E0)
when Eo > E1 otherwise
Te, (4) (Amax + =2 21,
where the inequalities comes from Lemma 11 and justify that there is no contradiction with the asymptotic lower bound the expected sample complexity (Lemma 1). The same reasoning applies to fixed proportions 3 by replacing T- (r))) by (T.)(
Concentration result For both proofs, we use the following concentration result of the empirical mean for nab-Gaussian observations (Lemma 12). This is standard tool for the asymptotic analysis of Top Two algorithms (e.g. Lemma in [32], Lemma in [36] or Lemma 14 in [21]), hence we omit the proof.
Lemma 12. There exists sub-Gaussian random variable W, such that almost surely, for all [K]
and all n such that Nn. 2 1,
log(e + Nn.a)
|Pn, - p4l S W
Nn.i
In particular, any random variable which is polynomial in Wy u has finite expectation.
D.1 IDS proportions
Using Lemma 9, the optimal allocation for -BI are defined as
(pi= 14 + )0
Weo (p) = arg max min
WEAK 1711 1/w,- 1/w;
17

---

Since 1 (1)) = 1, let Men = (i) where (i")
( as in Lemma 9. Since we have Teo (p) = T (Meo)
and Weo (p) w² ) 6 and yield that wro (11 {w*) is singleton with unique element Lemma denotes by w" which satisfies that min w/ >> 0,
= 1,
(8)
and
(15+ - μi + EO)
Vi E [K] (
2T (1)
(9)
1/w7. + 1/w5
[40] refers to (8) as the overall balance equation. The key novelty of their analysis is to show that asymptotically the empirical proportions satisfy the same equation, referred to the empirical overall balance, when using IDS proportions with sampling to choose among the leader and the challenger. The key novelty in work lies in proving that the empirical overall balance equation is also satisfied when using IDS proportions with K K(K 1) tracking procedures to select between the leader and the challenger (see Appendix 1.1.2).
Convergence time We follow an asymptotic analysis similar to the ones used in [32, 36, 21] with the improvement from [40]. Let > Let us define the convergence time Teo.y. which a random variable quantifies the number of samples required for the empirical allocations (Nn,s/Nn,)) lop to be y-close to (wt / /w0g- i
Nn, Nn,5*
wi W
Teo,y = inf T 2 Vn 2 T, max
(10)
Lemma 13 gives a sufficient condition to prove Theorem for IDS proportions. The case 8o = &1 is direct consequence of combining Theorem 13 and Proposition 14 in [40]. The proof is inspired by existing methods, e.g. Theorem 2 in [21] or Theorem
[32].
Lemma 13. Let En > 0, E 2 0 and 8 E (0,1), 1). Assume that there exists 71 (u) > 0 such that for all v E (0, 7h (1)], [TTo]]]] < +00. Using the threshold (4) in the stopping rule (3) with slack 1
yields an algorithm such that, for all u E DD such that li (p)l =1,
lim Ep(Te,,6]
(M) (1+ (1+ max ED E1 ifi Pi: p4 + 81
6-40 log (1/8)
Proof. Let > O. Let us define by
Nn
In.00 = inf T
Vn 2 T,
w²
s?
n n-1
Using that
Σ
w
and
Σ
Nu
n n-1 1 Nn
1.
W
w7.
Nu
cnfir
it is direct to see that for all n 2 T
Nn.5*
w7-
n
1
Nn.i
W. <
n
S T(KK- 11),
n - 1
N Nr
N Nn
W
Nn.i
Nn
1
n -
Nn.i
w
w/
= wij
+
n-
wi
Nn
No
W
1
n -
+
Nn.
wi
I STK.
w7.
Nn.s
Nn.
w
Therefore, for all 7 E (0, 11 (p)/K]] ET +00.
Let Mro as in Lemma 9. Since we have Ta (1)) T (Meo) and wro (11) = w (Meo) ), we can leverage existing results from the BAT literature, e.g. Theorem [21] or Theorem [32]. The sole criterion on the stopping threshold is to be asymptotically tight (Definition l).
18

---

Definition 1. A threshold e X [0.1] + RR is said to be asymptoticalty tight if there exists (0,1), 60 E (0, 11, functions f.T: (0, + R2 and C independent of 5 satisfying: for all 5 E (0, do] and n 2 T5), then c(n,6) 8) S f()) Cn (2) limsups-o ((6) (og(1/5) S and (3)
lim sups / (16) =0.
Since CG defined in (23) satisfies Cg R x + log(()), it is direct to see that
dn, 2Co { log (K5 (K-1))
K
)) + 4 log 4 + log 21)
5
asymptotically tight, cgg. by taking (a, do. C) = (1/2, 1, 4), f(6) = 2Cg log (k)1)) and
(6)) = 1.
Based on continuity arguments and using that E, ETTTeo.>l < too, the proof of Theorem 2 in [21] yields that
Eg [8l]
(ce+ - 14 + 01)
P4a - 14s + Eu
lim 8-+
min if
Teo (P) max i7tt
log (1/8)
2 (1/u7. + 1/w,))
M4: l4 + E1
where the equality uses the condition at the equilibrium (9). This concludes the proof.
Using Lemma 13, the proof of Theorem for IDS proportions boils down to showing that E, (e... < +oo. As in [32, 36, 21, 40], the proof is divided in several steps. First, show that all the arms are sufficient explored for n large enough (Appendix D.1.I). Second, we prove that the empirical overall balance equation approximately holds for large enough (Appendix D.1.2). Finally, we show convergence of the empirical ratio of proportions towards the ratio of optimal allocation, i.e. [T < +oc (Appendix 1.1.3).
D.1.1 Sufficient exploration
To upper bound the expected convergence time, as prior work we first establish sufficient exploration. Given an arbitrary threshold T. E R_, we define the sampled enough set and its arms with highest mean (when not empty)
8% = li [K] Nnç 2 L} and I arg max #4; vE
(11)
In all generality Σ, is a set, yet we obtain I = {i²}} as soon as it E S. We define the highly and the mildly under-sampled sets
U = (ie [K]] No,; < VLJ and : (ie [K] No,, < 13/4).
(12)
[21] identifies the properties that the leader and the challenger should satisfy to ensure sufficient exploration. We improve on their analysis by removing the need for the distinct means assumption, and supporting IDS instead of fixed allocation B.
Lemma 14 shows that the transportation cost is strictly positive and increases linearly. Compared to previous results, the key improvement lies in the fact that the lower bound holds for (i.j) E Iç x St instead of (i, j) E I₁ x (5% \ IT). This is due to the én regularization, which removes the need to assume that the means are distinet.
Lemma 14. Let Sh; and I as in (11). There exists Lo with (L,(()))]] < +o0 for all a > 0 such that if L 2 for all n such that Sk + 0. for all (i,j) In x Sh such that + j. we have
pn, Mn, + Eu
2 VI Eu
VI/N., n, + 1/Nn.
2
Proof.
Using Lemma 12 and min NN No.s 2 L. we obtain
logle + Nn.))
log(e + Nn.)) Nn.
Pn. - Pn.j 2 p4 14- -y--W Wn
+
Nn.
log(e + L)
Ep
2 22 v
>
L
2
19

---

where the last inequality is obtained for L 2 Lo L1 - e which is defined as
L1 = sup f I < 16W log( / + - - h1 (16W,,/60.
The last inequality is obtained by using Lemma 51, and we recall that in is defined in Lemma 51. Since hn ea)e)) ~x-+to0 log x; have By (y)))))))) < +oo for all (polynomial in W.). Then, we have
by using Lemma 12
Mn.i Mn.j + t VI/Nn,5 + 1/Nos
VI/Nn,i 1/Nn, 2 VT. VT, 60
eo/2
2/2
Lemma 15 gives an upper bound on the transportation costs between sampled enough arm and an under-sampled one.
Lemma 15. Let Sh in (11). There exists Tn with [T to0 all a > O such that for all I, bn and all n E N,
Mni Un, t WVL(D++4W,)
v(i,j) E S x SL
VI/Nn, + 1/Nn.i
where D1 > O a problem dependent constant and W is the random variables defined in Lemma 12.
Proof. Using Lemma 12 and Nn, 2 L2 Nnj 2 1, we obtain
Mn.i Un. + ED S v Nn.jMnn VI/Nas + 1/Nni
Mnn pnjj + col
(1 Nn.
/loglee
+ Nn.)
llogle + Na.)) ))
V |m4 115 +eal W
+ VV
Nus
VL (Ips H4 + + 2w, log(le +
S v VL(D, + ,W,),
for D1 max wM - my + Eol.
Lemma 16 shows the desired property for the EB leader. Since it corresponds Lemma 17 in [21], we omit the proof.
Lemma 16 (Lemma 17 in [21]). There exists L2 with ((L2) +oo for all a > 0 such that if
L L L2 for all n (at most polynomial L) such that S # B E St implies B E I
Lemma 17 show that the desired property for the TC challenger. Compared to existing result, improve by remove the assumption that all arms have distinct means thanks to the regularization Eo 0.
Lemma 17. There exists Lg with E., [Ta) < 400 such that if 2 Lag, for all n (at most polynomial in L.) such that Uh + 0, BEB & V. implies C.Cco E V.L.
Proof. In the following, we consider U * 0 (hence VL * 0) and BEB & V.L.
Let J,
arg max pi and L2 in Lemma 16. Then, for L > L we have BBB E Jū.
Let Lg and (L1, D1) as Lemmas and 15. Then, for all L 2 max 4/3 L L7).
BRR E T
V(I,)) J. x VT. s.t. s. i
Pa.i Pn.j + Eo
13/8 Eo 2 (1, + 4W,)
V1/Nn,t + 1/Nn.j
v(i.) E Th U.
Pn.i Pn.j + Eo
VI/Nn,i + 1/Nn.j
20

---

4/3 L. Since In S V - U for all L 2 L3 max 4/3 ,L1
(2v2 50
(Di + 4WW,)) + +1} we have
(( E J. U V s.t. i.
Mn, Mo.j Eo
Pn. Mn,k + Eo
VI/Nn, + 1/Nn.
VI/Nn, + +1/Nn.
As B The the definition Ch yields that Ch E V. Otherwise the above strict inequality would wield a contradiction. Using Lemma 12, we show
(
2v2 (2v2 (D1 + +WWW))
EF L3] S EF
+
+ (F((L)) [ EF((L)) ((x())))+++((()))]] < to0,
hence this concludes the proof.
Lemma 18 shows that all arms are sufficiently explored and that the leader is the unique best arm for large enough.
Lemma 18. There exist N1 with [x[ < +oo such that for all n 2 N1 and all e [K]. Nn, 2 Vn/K K and B =
Proof. Let L2 and L3 in Lemmas 16 and 17, Therefore, for L 2 L4 == max L2(3,, J. for all such that U. * 0, BEB E Vi or C E V.L. We have [Ta] < +00. There exists deterministic Ls such that for all L 2 Ls, [L] 2 KI33/4 Let I 2 max LL. L4].
Suppose towards contradiction that U .K.j is not empty. Then, for any S t Σ [KJ, U. and Vi are non empty as well. Using the pigeonhole principle, there exists some E [K] such that
NIL 2 1,3/4, Thus, we have [z] S K - 1. Our goal is to show that V S 2. A
sufficient condition is that one arm in Viz is pulled at least 1/3/4 times between [L] and [2L] 1. If we have
21
Σ
(1B
c c v,,y) 2 KL3/4
t- [-]
then, using that V₂! S V- we obtain
[26]-]
22
Σ 11 (I V [=[4]
Σ 1 (LEV,))
Σ
1 (BThh C
C.CSo
S V.!) KT33/4
[=[4]
[=
Therefore, there exists i E V(2 which is sampled L times between [L] and [2L] 1. In the following, we assume that
[2L]-1
Σ 1 (B C.C. CV KL3/4
[=|4]
Since B. E V. or C.C E V, we have
[2LJ-1
Σ (1 B (1 e v., of & v.²) + 1 (BThh & &V E vv:)) > [2L] - [4] - 3/3/
[=[4]
Therefore, we have
121 -1
Case 1:
Σ
BBB E v.L.c.m v.4) > (|2L) - |7] KI3/1) 12,
- [T,]
122| Σ
or Case 2:
BEB & V.l.C.
ciTCco v.4) > (127) [T] KT3M1 12.
==|4]
21

---

Since B((1.5) = (N + +N,,s), we obtain
if B V. C & V. if B & V C E V.
1/2 <
1 BB C)
This lower bound will be crucial argue that the challenger is sampled enough in case 2 and the leader is sampled enough in case 1.
Case 1. Using Lemma 46 and the above, we obtain
1
124--1
Σ 1=|4|
(1.VV/1))
EE Σ
1
1
(BF ciC (1.3)
LEV iti
t= |=|4
[2r] -1
Σ
Σ
Σ
Be (B, , Ct C..Co) = (1.3)) - K22
LEVLL j#i t= t=]
|2L|-1
Σ
BB c(.C BB E Vi, ctcico & v.!) - K²
|
2 (22] [T]] KTT/A) /4- K2 2 KT,3/44
where the last inequality is obtained for L 2 Ls + 1 with
LB = sup { LENI (22 - [L] - KI3/1) /4 K2 KI3//1
Therefore, there exists E V12L which is sampled L times between [L] and [2L] - 1.
Case 2. Using Lemma 46 and the above, we obtain
[2.]-] -1
[26]-1 1
Σ 1 (I.VV())
N Σ
11 (1= j. (BFT, c((co) = (2.5))
[=|]]
JEVL
[=||]
[2L|-1
Σ
Σ
Σ (L-,((i))) (BBE. CIC = (1.5)) K22
SEV [1]
if [=|T]]
|2 -1
Σ
(1 - 1- CC:CE.))
BER & V., c.cco E v.¹) - -K2
[4]
2 [2L] - |L] - -KL3)) /4-
where the last inequality is obtained for L 2 L6 + 1. Therefore, there exists i E Víž which is sampled L 3/4 times between [L] and [2L]
Summary. We have shown [ [1]]
K 2. By induction, for any 1 1 k < K, we have |ikL S
K kc and finally [ for all L 2 L, max Log L,, Lo 1). Defining No K KL,,
have [No] < -0. For all n 2 No. we let L = n/K, hence we have / = [KL] = 0. This concludes the proof of sufficient exploration.
Leader is best arm. Using Lemma 12, we obtain that for all n 2 No.
log(e + Nna)
log(e + Vn/K)
Vi H pao S M4 + W
S pc
SMi + W
Nn.i
Vn/K
log(e + Nn,s))
log(e + Vn/K) Vn/K
po S pi. Wm
S pm
Wwy
Nn
22

---

Therefore, we have B = 1* for all n 2 N1 == max No. (Xo -0)2 + 1 where
Xo sup { x x>>1
16W
16W
log(2) + of s hi mine (fke u;)2 e
ming (1i- - p4)²
where the last inequality is obtained by using Lemma with hn defined therein. Since (1,,)) e) tootoo x log 2, we have
[N[N1] < [No]]] [K(( - e)2 +
This concludes the proof.
D.1.2 Empirical overall balance
As in [40], the key to obtain asymptotic optimality is to show that the empirical proportion satisfy the empirical overall balance equation. Compared to them, the novelty of Lemma 19 is that we use IDS proportions with K(K 1) tracking procedures select between the leader and the challenger instead of sampling.
Lemma 19. Let 7 > 0. There exists N2 with [N[]]] < +oo such that for all 2 N2
N N
2
2
Sy.
n
n2
19f1
Proof. Let N1 as in Lemma 18. Then, we have for all n Ni
Nn.5 Nr
Eigrr Ny
Nu
No¹ n,
Ejji N Ni.
n-1 +
n-1
7-
n-1
n
n1 n-
(1 (i ,1) Tn ()
R-1
TN, (i', n 1
Σ
1 = () -B(1,, ,)) + +11-BN (i", ())
n-1
n2 n
N=
E. 5)
To (x(
1
Σ
Bii C.) + Σ (N ,))
(i,,)
n n-1
n-1
N=
Chaining the inequalities with Lemma 46, we obtain that
K
No.i.
1
2N + K Belit,Ci)
n
n
1
n
Nn
2N + n n-1
1 (C, = ()(1))1) (1- -B((i, <
N=
Using that a² - 1/2 = (a- - (i)(a + b) < 2(a
b) for (a, b) E 1), we obtain
2
K
Nn.
1
2N +K
2
Σ
<
1
1
n-1
t=
2 n
1
Nr
Σ
() -1000))))
<
2N +1
n
n
For all n > N1. let us denote by
G = Σ
B,(1t, B((T.C)))
-
Σ
1
- 1GG
((C=))([-B0000))
N1
john
N=
Therefore, we have
N1 +1
Nn,5 2
Nn.; 2
Gn
N₁ + K n -
4K
<
<4
n 1
n -
n -
(n 1)2
23

---

Direct manipulations yield that
/ [Gnt+ -G) = Bi C.) Σ C,)
-1- Ba(1,, C.))
Σ (C, C.) (1) 3e C.))
L=
+ Br, C.) - 1/2.
Therefore, we obtain by using the above inequalities that
GGn+1 GGn) S Bn(i", C,).N. (1 - BBi(i,, CCNT),,),,,,.C + + K +K+3// +3/2
= =N + K + 3/2,
(Gn+1 - GGn) 2 ,,((",,))Nnn Cn)Nn, - -(1 - -11-Bn(i" (A)(",C))NN,.C, - 2N - K - -3/2
= - K -3/22,
where we used that Bx(i", Cn.. = (11 Cn),,,,,,,, since Bn Cx) = N Nn NNo Summing those inequalities, we obtain
No
R-1
Gn = Σ (G++1 - -Gt) GNI+1 S (4N1 2K + +)(( N1) +1
N=
2 2 + 2K + +3 11 Ni) 1
where we used that GNy+1 = 23N, (8*, CN2) -1 [-1,1]. Combining everything together, we have shown that
N n
2
N n
2
N1 + K
(4N, 2K + +1 +1
+1
<
n
1
n
1
n
(n (n=
Ni +1 > 4K
(4N + 2K + +)(n - 1 1N) +1
n-1
(n-1)2
Therefore, we have shown the desired results for 2 N2 defined as
+1
(4N: + 2K + 3n -1 Ni) +1
N₂ inf 4K
5
(n 1)2
which satisfies [,, < to0 since a linear function of Ni.
As in [40], using Lemma 19 allows to bound the empirical proportion allocated to the unique best arm Nn (n - 1) away from 0 (Lemma 20).
Lemma 20. There exists N3 with E. [Na] +00 such that for all Na
1
Nn 3 n 4
4 2/2(K- 1)
Proof. Let No in Lemma 19 for 7 = 1/2. Using Lemma 19, obtain
Nn.t n-1
since
Nn
No.i - -(1- Nn.
2
N Nn..
1/2 >
>
2
1.
n
n
Let N2 as in Lemma 19 for y 32(K -1)
Similarly by using Lemma 19, we obtain
Nn n-1
2
1 since
122(K-)
Nn
Nn.
1
Nn.s.
2 32(K 1)
>
1
n
12
32(K K - 1)
K
32(K K - 1)
Taking N3 max[N2, N2) yields the result.
24

---

Lemma 21 is rescaled version of the empirical overall balance equation which is proven by simply combining Lemma 19 and Lemma 20.
Lemma 21. Let > 0. There exists N4 with [Na] < +00 such that for all n 2 N4
N Nn,
SY
ig
Proof. Let N2 as in Lemma 19 for 32( 1) 13- that, for all N4 max N2, Nah.
Let N3 as in Lemma 20. Direct manipulation shows
1- Σ
Nua Nn.r"
2
Nn
2
Σ
Nn.
2
332(K - 32(K -1)
7
7
Nn
n
n-
igii"
This concludes the result.
D.1.3 Convergence towards optimal ratio of allocation
As in [40], we show that a challenger will not be sampled next when the ratio of its empirical propor- tion compared to the one of i" overshoots the ratio of the optimal allocations (Lemma 22).
Lemma 22. Let > 0. There exists Ns with [Ns] < +oo such that for all n 2 Ns and all i + it
No.i Nn,r*
2 w
+
C.Cco # i.
Proof. y Let # 8t such that
Nn
wi
+7
Nn.5
w
Suppose towards contradiction that
Nn.
Vj i",
Na
w
Let 7 > 0. Let N4 as in Lemma 21 for 7. then using Lemma 21 and yields that, for all n 2 No.
Σ
Naa 2
W
2
= 7 (7+ w
+
Nn.5*
w
w
w
Joh
Therefore, we have a contradiction we take ÿ small enough (e.g. 7 < 22), that, for all N4.
hence we have shown
Nu.ó Nn.
w
No.. Nn,
wj
+ 7
Bj $ (i*
w
w
Let N, as in Lemma that
18. Using that B. = i* for all n 2 N₁ and the definition of CTCaa, we known
Mn. Un,i Eo
Un.ir Mn.j Eo
CTCC +
VI/N,, 1/Nn,i
VI/Nn. + 1/Nn.5
To conclude the proof, it is sufficient to show that the ratio of the two quantities is strictly larger than one. For all n 2 Ma, Nı), we obtain
Mn,s Mn,i +
1 + Nn.a /Nu.
Pn,i* Mn, + so
+ / + (wi/ /we. + +2)
Pn,i" Mnyj + Eo
Na.i /Nn,
Pn,i" pn,j + Eo
25

---

Let ÿ > O. Using Lemmas 12 and 18, we have, for all n 2 N1 and all & o 8",
pn,j Mn,,k + E0
W
Looge + Nu.)), Nux
logle Nn.a)) Nns-
S P4
+
Pir + Eu
14 +
2
log(e + vn/K)
39
mig (14- Ne EO)
Vn/K
for n 2 No K(o - -e)² + which is defined
4W2
Xo = sup
x 2 1
4
log x +
22
mink
Ma + Eo)
4W2 1
$ h1
72 min (M+ Pe + 20)
where the last inequality is obtained by using Lemma 51 with hi defined therein. Since h1 y) ~o-++o I log we have Ey[NN]] < to0 since it polynomial in Wa (by using Lemma 12).
Let O. We have shown that, for all n 2 max(N11 No. No).
Pn, un, + ED
1 Nn,3" /Nn.
N4. 14 +
1 1 +
1 - 7
Pn,i pnj + Eo V
1 1 Nn.i. /Nn,
He. Mj Eu V
1 1 (w//wt. + 7)
+ w
1 -
1 + (w//ww + + 1+
where the equality uses that the transportation costs are equal the equilibrium, i.e. (9). Taking small enough, we have that shown that, for all n 2 max N4. No).
Nn.s Nn,
Un,s* An,i + Eo
1 1 Nu.a /Na.
TCro + i.
>
Pn, Unn +
1 1 Nn. /N
This concludes the proof.
Lemma 23 shows sub-optte sub-optimal arm is overshooting the ratio of its optimal allocation for n large enough.
Lemma 23. Let > 0. There exists No with [Ns] < +oo such that for all n 2 No and all i + it,
No.i Nn w
< w
+7
Proof. Let 7 >
Let N1 as in Lemma 18. Let N3 and Ns as in Lem- max{Ni Ns, N1 and wi
mas 20 and 22. Let M 2
M. Let (n,(7)
max {M, {M, max { E {M, ,n 1}
No. Ne,.
we +/2 for all i + it. In particular, using
Lemma 22, for all n > M
No.i
w + 7/2 hence + CiCco
Vt (ns(7),
N₂.-
w
and
M, ( w
No,. S max
7/2
Then, we have for all n 2 M,
NA, = Non.(r))d + 1l (i Ienalt)) +
Σ
wi +2/2)
< max M,
Nen
N
+1.
26

---

Using that (1, I NN,,, No, 2 212(K-1] that
n-1
(Lemma 20) and max b} S a + b, we obtain
Nu.i No
1MM+1)/2(X n
wi 7/2 -
+
+ +
W
where the last inequality holds for 2 N7 8(M
2(K - 11/7 2)
1. Taking No
max(N3, Ns, N1, N7) yields the result since [No] < +00.
Finally, Lemma 24 shows that the sufficient condition (see Lemma 13) to obtain the asymptotic upper bound on the expected sample complexity satisfied.
Lemma 24. Let Eo > 0, 7 > 0 and Teom as in (10), Under the EB-TCe, sampling rule with IDS proportions, we have Ev [To..]] < +00.
Proof. Let y > and 5. Let N4 and N8 as Lemmas and for 7. Then, using Lemmas 21 and 23, we have for all 2 max NN,
Nn.s N
Nn.j 2 Nn
Σ
21 21
-
jE(1,))
2 1
Σ
Wjj.
+
2
-
W
2
(K (K-
2)7 +2
+1
W
jE( }
where the equality uses (9). Therefore, we have shown that for all n 2 max(N1,
No.i
- W:+- w "
2 (K (K- 2)9 (K- +
Σ
W
+1
W W
7
Nn.5*
w
jK(i,
}
where the last inequality holds for y small enough as a function of y and w". Therefore, we obtained
N
wi
ST.
1f1"
Nn
wT.
which concludes the proof, i.e. E [T,]] <
+00.
Combining Lemmas 13 and 24 concludes the first part of Theorem
1, i.e.
lim sup 8-
E, (T log(1/6 (100)
< Too (w)
(1 max Vi1
Eu -
2
Mi + E1 Pi:
D.2 Fixed proportions
Using Lemma 9, the B-optimal allocation for so -BI defined as
(Ju: 14 + 80)
Weo. (1) arg max min WE igi"
1/3 + 1/w,,
Since (x)) 1, let Meo (i*) where (i( in Lemma 9. Since we have Te)
T33 (Mez) and Weo.s(()) = w² (Mec), Lemma 6 and 8 yield that Wen (14) = {w3) } is a singleton with unique element denotes by w which satisfies that minje[k] w > 0 and
(EG. 14 E0)2 1/3 + 1/13g
vi [K] {
2T 2T)
(13)
When considering fixed proportions 3, the proof strategy is the same as in Appendix D.I. The sole difference lies in the fact that the empirical allocation the unique best arm converging towards fixed B.
27

---

Convergence time Let y > 0. Let us define the convergence time Tea,8.7. which is random variable quantifies the number of samples required for the empirical allocations N, be y-close to wrg:
To,,8, inf {
Nn
vn T,
w
(14)
00
Lemma 25 gives sufficient condition for asymptotic 8-optimality. The case Eg is direct consequence of existing methods, e.g. Theorem in [21] or Theorem 3 in [32].
Lemma 25. Let Eo > 0, E1 2 0 and å (0, 1). Assume that there exists (n) > 0 such that for all E (0, 7i (n)], (o +oo. Using the threshold (4) in the stopping rule (3) with slack E
yields an algorithm such that, for all E DD such that li (p) 1,
Ey (e S (H)) (1
lim sup 5-+0
(1+ max Ef1' Mi
log (1/0)
M4 + E1
Proof. The proof is the same of the ones Lemma 13. The sole difference is that we have w by definition.
Sufficient exploration Lemma 26 shows that all arms are sufficiently explored and that the leader the unique best arm for n large enough.
Lemma 26. There exist N1 with E,[N]] < +oo such that for all N1 and all [K]. Nn, 2 vn/K K and BEB 1*
Proof. Since Lemmas 16 and 17 holds, we can use the intermediate results of Lemma 18. It is direct see that the proof can be conducted similarly by noting that, for all i o j.
min 1- (i.j)) m (3, 1, B} > 0.
Convergence towards optimal allocation [20] yields Lemma 27. Lemma 27. Let > 0. There exists N2 with Ey < +00 such that for all n 2 N₂.
Combining Lemma 26 with the proof of Lemma F.8 in
Nn.5*
g ST.
Combining Lemmas 26 and 27 with the proof of Lemma F.9 in [20] yields Lemma 28.
Lemma 28. Let 7 > 0. There exists Ns. with [Ns) < +oo such that for all 2 Ns and all i + i*,
Nn. 2 Ug. +
TCro ti.
Combining Lemmas 27 and 28 with the proof of Lemma F.10 in [20] yields Lemma 29.
Lemma 29. Let 0. There exists No with E, [No] < +oo such that for all 2 No.
N
w/
<T.
Lemma 30 is direct corollary of Lemma 29.
Lemma 30. Let Eo > 0, (),1). >> 0 and Te,.9.7 in (14), Under the EB-TCe, sampling rule with fixed proportions B, we have E. < to0.
Combining Lemmas 25 and 30 concludes the second part of Theorem 1, i.e.
2
lim sup 8-40
$ TH)
(1+
max iff
Eo E1
log(1/8)
Pi:
14; +
28

---

E Non-asymptotic analysis
Let En > 0, 3 E (0,1) and E 1). In this section, we provide a non-asymptotic analysis of EB-TCco with fixed proportions and slack Eg > 0 when combined with the stopping rule (3) with parameters (Eo. 8). In practice, we will mostly be interested the case 3 = 1/2. First, we prove Lemma 5 in Appendix E.I. Then, detail the proof of Theorem in Appendix E.2.
In the following, we consider sub-Gaussian bandit with distribution y E D having mean parameter J RRKK In particular, our analysis holds when several arms have the largest mean μ4x.
E.1 Proof of Lemma
Let 2 O. For all K and ā E (0, 1], let En,o = En, n En with (En,s)n> and (En,6)n> as in (24) and (25), i.e.
2fi(n, 0)
8,6
yk [kE[K], VE S n. |pEk pal <
[K],
Ne. S
11 sn,, 1ue,i - (s,,k) (1i -ma)l < (252(n,))
((i,k) E [K]2 s... k
VI/No, + 1/N1,
where f2(x,, 6) (1/(1 + (1 + s) log(>) and f2(2, 8) log(1/8) (2 + s) log(x))
Lemma 31 shows that when there are arms with strictly higher true mean than the one of the leader, then at least one of those arms is undersampled.
Lemma 31. Under E, for all I. E [m] \ [K] let B k. Then,
8fi (n, 8) (Mi 12)
Vi Vi k. 1l (m pk) (Ne New
Proof.
Under E, for all E [n] \ [K], let BEB k. Then, for all + k, we have
(2, 5)
2f (n, 8)
2f, 5) Nr.
14 - V min Ne,ke No,1] S 14
S Pe, S Mr S me +
N₂.i
2f, 8)
S 14 +
min( (Nen
Re-ordering the above equations for such that b4g >> p4 yields the result.
Lemma 32. Let E 2 Ap(E) minagI,()) As and (p.so()) max (ax)())
En }
Let Aco.e.i 2/ (c)) for all E i" (p), Azo,ex = Cu.5 for all E Ie( (n), otherwise Acpeed mmx CH.eo (s), 2/}). For all n >> K, under event En,8, for all E [m] [K] such that BLa & (H). there exists [K] such that
4f2(n, 8)
Ti(i)) min [3, B}
Aso + +3(K - 1)/2 and Tet1( = Te(le) +1.
Proof. Let A, = 14, (4; and Amax = max A. When e 2 Amax we have I [=()) = 0. hence the above result holds trivially since the event B & (n) cannot happen. Let E [0, Amax), i.e. I- C + 0. We will consider in two distinct cases since
[B. [x)) = (B. & Iz(,,, C, E (P)) & Ix)), C. (1))
Case Let t E [m] [K] such that (B CTCCa (i.j) with i $ (p) and j E (1). Using Lemmas 46 and 31, we obtain
8fi
8f2 8)
min B, 1 - 3) (min (T.(), 3(K 1)/2) < min No.1
<
A?
A
29

---

which can be rewritten as
min (Tn, - 812(n,))
( + +3(K - 11/2.
Let us define (E) (i) 4R. and
Vi $ (I),, Dr,i 2/4 and Vi ( = = 2/=
The above shows that there exists K E Ig (n) ( such that (f,
(kkk)) - min (,, 3} De.k. k. 3(K 1)/2 and Tet((k)) Ti(kk)) 1.
Case Let [m] [K] such that (B,R, C( (i,j) with i & [x( and j & ())). Let in E i" (n). Using the TC challenger, we obtain
6o A,
(2f2(n,8) M4,1 - M4.30 + Eo
He,i H4.j + Eo
VI/Na, 1/N
VI/Na + 1/N1.0
VI/Ne, 1/Nes
2 cov min No. 1/2
Using Lemma 31, we obtain
(11 1/N,,, + 1/N I min No,oo S
A - 812(n,8)
A
By distinguishing between En > 6n A;
A and ED S A, and using that A, > 0, we have
VI + 1/Nr,5 222 8) S max (250/ 1, 1) 2f2(n, 6).
Using Lemma 46 to lower bound min Ne,,, No,} } and reordering, we have shown that
min (T), S max (
2 1
2
4f2(n, 6)
min 10,1--33-000 + +3(K 1)/2.
A,
80
Let us define C,.so (E) = max (1) 8" (n) such that
-0
.50
12.
The above shows that, there exists ke &
4f2 5)
(2(ks) S
min 3} Cp.co (c) + 3(K - 1)/2 and Tkti = Te(ks) + 1.
Summary. Let us define (AEo)) as in the statement of Lemma 32, Under En,s, we have show that, when B. & Ie()), there exists it E [K] such that
4f2(n,8)
Ta(ka) min(B, 38) Ac,coi + +(K 1)/2 and Teti =T((k)) + +1
For all n > K, under event En,s, combining Lemma 4 and 32 for Ar(n, LL.. Ie (1)) and (f,
Di 8) = mnn((3,1-8] 83 Acoie, 3(K - 11)/2 yields that
4.2(n1,) 8)
Σ 1BB & (H)) < 1nin 1 3} H Hp.co (E)+ + 3K(K - 1)/2.
t= R+1+
where used that Ejelg] Aro.e. Hp (E) where Hn (E) is defined in (5). To conclude the proof of Lemma use that
n
Σ
1 (B $ (I)) = 11
IIn(t))
SEI,(A)
Let (n, 8) and Fe(n. 8) defined as in (26) and (28). Using Lemma 50, we have f (n, 8) S fz(n, 8). Therefore, it is direct to that Lemma 33 can be proven with the same proof for Lemma based on the concentration event En, En 5 n En with (Eus)n>k k and (E%,)n> k as in (27) and (29).
30

---

Lemma 33. Let E (0, & 2 0 and p.,eo (E) as in (5). For all n > K, under the event En,
2n Σ Σ 2 VET, (10)
min 3] f2 0) + +3K(K - - -1)/2)
E.2 Proof of Theorem 2
Let s > 1. For all n > K, let En = En, n E7 with (,n,)nss and (Eh,))>> as in (24) and (25).
Using Lemma 45, we know that Σn>k (v() < 2
KiK+1] (()).
Let En 0, E1 2 co and E (0, 1). Since & 2 co. and using the definition of the stopping rule (3), is direct to see that Ex(Te,, S Bu (T
Suppose that we have constructed time T(ő) > K be such that for 2 T()), & C (Toodd S n}
Then, Lemma 47 yields
(T.. $ T()) K(K +
((s).
2
We will construct infinite number of times (T(6, u) Jueu such that the above property holds, hence taking the infimum yields
Eg [To.s] I inf T( u) K(K + ((s)
weul
2
This proof strategy is the one used to prove Theorem 5. Theorem is corollary of Theorem 5. Note that the notation of both theorems differ slightly since we provide shorter statement in the main content. The key difference lies in the refined analysis used to clip min // i); by fixed value x E [0, (K - 1) for all i (14).
Theorem 5. Let Eo > 0, E1 2 Eo and 8 E (0, 1). Using the threshold (4) in the stopping rule (3) with error E,, the EB-TCeo algorithm with fixed proportions 3 = 1/2 is (E1, 8)-AC and satisfies that, all v E DK ET(Ter,o) S Ey [Te.8] and
max (T (6,5,z) + 1, S (e,o() + ((s) K(K + 1)
ET S
inf (x00)((0ss0/00000K--1)1
where
( T (5, sup { n - 15
2(1 7) Σ EiEI,()) To0,1/((1,
(1 - x))eic (c,0)
(Ve(n- - 1, + / (2+ log
Sp = (((2+ 8) +1
(3k / 1)
Al ()) ag (c, x. (s)
+ +1)
ap.co (c, x) Up (e)
minie (1) T 1/2 1/2
(H,
(E)
EiEro()) Teo Teo.1 2 (1,
(5, = min (1 - x) (2:0) max min W We0.1/2(H, i)s, x/2}. jf1 d), = max (x, with dp (z, = 148 # W W20.1/2(H1, f)5 < x/2211 iEle(H)
iEIe(H)
are analysis parameters. Teo. 1/0.1/2(11, i) and Wzo. 120.1/2(11 are defined (1), Husg(e) (E) in (5), Ç is the Riemann Ç function and h (z, y) =W (log(z) + w/2) is defined in Lemma 51 and satisfies that hy ha(2, y) RJ x log(z) + log(log( + w/2).
where 7 E 10,1/2) and
Proof. Let E [0, be an analysis parameter, and I. = [T)) Let v e Å. defined as
T (H,
Vi e (I),
Ut ESET(()) (w) Teo,1/2(1,3) hence
min (EI,(M)
= (p..a(E).
The main technical result which our proof relies on is Lemma 34, which will prove afterwards.
31

---

Lemma 34. There exist Do > 0 and Tμ 0 such that all n 2 T2 such that En n fn < &e,,6) holds true, there exists io E Ig (1)) and S n with B ig. which satisfies
1/N 1.00
1/N t, U4o (n (n - (1/3 1/00g(00)
Do
(15)
Before proving Lemma 34, we show how it be used to conclude. Based on Lemma 34, let Do Tμ > 0, > Tp such that &n n {n < Tel.5) holds true, in and S such that as B in and
Do
1/Nts, + 1/N2 1,0,
I
Gig (n -0-1 1) (1/B + (10)
Using the stopping rule (3) with error Eo. S < TeL.d, BrT = it io and the definition of the TC challenger (2) with slack Ep, we obtain
22 1,8) min PL. - Ha,i + EO
V1/Ne,.o + 1//Neii 1710
Mio - Pctcco EE
12(2 + 8) log
1/N + 1/N
1/8 + (3) Cicso
2T (11, 22(22 + s) log
1/N + 1/N2o L.
2(n
22(2 s)
Do ΣiEr (u) Tea,s(u,
The third inequality is obtained since En holds. The fourth inequality is obtained since Nř 2 Nr for all E [K] and by using Lemmas 8 and 9. The last inequality is obtained by Lemma 34 and using the definition of Uig.
Let's define T(5, Do) == sup(n > K n n 1 I
< Do Di Tea. () 1,6) +
((2 8) log 2.) Therefore, we have E,, n (n < Tea.8) 0 (i.c en c (Tew. I n)) for all [T Do), Tr + 1}. This concludes the construction.
To conclude the proof, we will show that Lemma 34 for many choices of Do and Tμ.
4H1 4Hf,.gg (c) [8.1 18.1-85- (2 + 5) log + 3K 1)/2. Using
Vanilla Proof of Lemma 34. Let (n) Lemma 5, under the event En,
Σ ET. -n (n) (ET,(M)
Therefore, the pigeonhole principle yields that there exists in E I (H) such that
(n 2 (n (n))
The crux of the problem to relate Nic, (t - 1) and w (1o) (10) regg To do so, we use the approach of [20] that builds on the idea behind the proof for APT from [30]: consider arm being over-sampled and study the last time this arm was pulled.
By the pigeonhole principle, at time n, there is an index kn * in such that
W (10)
Noo n.
Σ Nío
(16)
3
3710
and we take such ki. Let sup (1 < (Br, Ct) (io, ki) be the last time at which in was the leader and kj was the challenger. If Le, Bd, then No
No n.k, otherwise No
Ne.kk -o
1.
32

---

In both cases, we have t2, 2 No. n.k1 and 0ip I L, we obtain
-1. Combined with the above and using that (0)())) 11-B
Wgg (10)
k 2 N n,ki
12
No nj
1-
jii
K -
2 wz(())
Σ (iv
- 1
2(1 3)
K +1 1
2 w306)) Usg (n - 1) - -
2
2 (10) ky Vig (n - 1) - 11)--((1)) ()())))))))))))))))))))))
with (n) = 4(1 - 3) H ( (E)
K +1
3} fa(n) + (1 - 333KKK - 1)/2
min
2
Let wig.- 0 be lower bound on (3((1)) ( e.g. Wig.- mini wz) For instances μ such that wz (b))a, is small, the equation (16) can be satisfied the very beginning, hence t might be
sublinear in n. Due the missing link between i and n. we use the following inequality
1/N 61.00 + 1/N b2 Uso 1)
1/3+ + Vio (n (n-1)
Nr.
+1 +1).
N12.
which is suboptimal step which artificially introduces 1/3. Let 7 (0, 1/2]. It remains to control both terms. First, we obtain
1/B + Vig (n - 1)
I 1/BB+
S (1+ (1/8111////////
w
(m)
Veg (n-)n
for all n > C1 (W Unico (c)). The last inequality is obtained by definition of
he (n) wv (1 (1+7-1)
Cw v) == sup n 2 1 n
(17)
which ensures that, for all >> Ci (1 11ico (e)), the last condition of the equivalence
1e (n)
(n(
(1)) Vi (n - 1) 2 (1 + 7) w3
n 1-12
(1
71+
0% (10)
satisfied since (10)k; 2 Wip.- Vig 2 Un (e) and n > Ci (w 01.50 (e)).
Second, using Lemma 46,
show that
3 Noo
1
hi 2 Tr, ki) NiA BT,, (1o, ki)) 1 1 B
1- B
Then, re-ordering the above and using that No. 2 w3((1)); nio (n - - -h (n). we obtain
-1
Nio t1
+15 1-3 (1 (1- 3) (w3 (w3 (60)s; via (n 1) - ho (n)
+15
Nio
for all n C2(W Up (e)). The last inequality obtained by definition of
1 (h((n) + 7 1+1--
C2(w, v) sup N n 1
(18)
we
By
which ensures that, for all > C2( un.so (E)), the last condition of the equivalence
-1
3
+1 (1+7)/8
1 3 3 (1 (1-3) (w3(1o)) vio 11) -ne))))))))))
By
5
w3 (1))) Vio (n 1) (1((1))
+ + 8
1
hn(n)) + 7 + 1 B
n 12
w (ko))) Uio
By
33

---

is satisfied since (bo)) 2 Who Vig 2 U. and n > C2 -1 pp. (E)).
Let TN 2 [2 C (min,eT.()) (1) wi,-; " (E)) and Do = (1 + /33//. In summary, we have shown that for all n > T. there exists in E (M) and 1 S n with B,, io and such that (15) holds.
For 3 = 1/2, using that K 2 222111+ obtain that
<1+>"
and 5/2 +2 - 3(1 + + 1 (since y E (0, (/2),
n 2 1 1 1 (4(2 5) H| 1 (8) logn + 3K /4 + 11}
max C,(w,)) sup ie(2]
W/
4 s) + + h1
(1+ + (3+2 +1)
H (e)
wv
we
where the last inequality uses Lemma 51 and h (z, defined therein.
Using Wis.- minigio (to); and / 1/2, the first part of Theorem (i.e. x = 0) obtained by taking the infimum over (e, x) E [0, so] x {0}.
Refined Proof of Lemma 34. When considering large K or instances with unbalanced 3-optimal allocation, m (e) minizto (ā)( can become arbitrarily small, hence dependence in its inverse is undesired. Thanks to the refined analysis from [20], we can clip it with value of our
choosing which is away from zero.
Let E (0, 1/(K- - 1)] be allocation threshold and (x, == 10i E [K] \ ( | w)(1))
(1 - 3)z} for all E Is (p). The equation (16) is only informative when (1) wz((t)) (fo)s; (1 B)x
or (2) w3(())) < (1 - B) and nnkk 2 x Ejttio Nio The problematic case occurs when (3)
())())) < 8)æ and N.
x <xEfti N
When w (1o) 2 (1 B)x, we can use the above computations by considering W max 3)x, minezio w3
When wz (to)e, < (1 - B)x and No. n.A, 2 x >
it Ni.- the above proof can be conducted by using
(1 - f)z instead of (i)): since we will obtain that
Nou kg 2 (1 D) (n - hr(n) and 1/3 + (1 (1- 3)x < 1/B 1/v0
Then, we can likewise consider Wio. = max - B)æ, minefio (10); to conclude.
When (f)) < (1 - B)x and Noo n,k1 < x Ejtto Nog, as in (16), the pigeonhole principle yields
that there exists h2 [K]] \ fio, k1} such that
w7 (60)
No. (1=))wz((ol))
N 1 (0) (f0.)))))
Σ
N
1
Based on ky the same dichotomy as for k1 happens: either we can conclude the proof when we are in case 1 or 2 or we cannot since we are in case 3. If case occurs also for k2, i.e. (f))) < (1 f)x
and kg < x Eje((o.h)) N2... we should also ignore it since it is non informative and construct a third arm k33
The main idea is then to peel off arms that are not informative, till we find an informative one. By induction, we construct a sequence (kg, Ma)aejd of such arms, where ka is the first arm for which either No
(1) wi (ia)k, 2 (1 - 3) or (2) w (i0)a, < (1 - B) and Noo
n.ks 2 x (oo 1], we have w < <1 -)xx and
holds. This means that for all a [d
Σ
No.
Using the pigeonhole principle for [K] \ (fio) (lichae(- yields that ka satisfies
Noo n
2
Σ
Noo
1-
3 > Docla-1] w3(0))
o je( (kk
34

---

Using simple recurrence on the arms {ke Ine(d-11) 1), we obtain that
N 2 (1 - x)d d-1 Σ
n.
jæ (Ho (H
Let ta sup (t< < n (B,, Ct) (io, ka)). Since the arm ha satisfies case I 2, we can conclude similarly above with an extra multiplicative factor (1-x)=-1
To remove the dependency in the random variable d. we consider the worst case scenario where {ka Jael--1 {i E [K] \\ { (1o); < - (1-8)z); i.c. d 1-1 S (1, io). In words, it means that we had to enumerate over all arms with small allocation, such that case 2 didn't 't hold, before finding arm with large allocation, i.e. satisfying case 1. Let ( max d,( i). Using that
(1 - x))= 2 (1 x))alloro)) 2 (1 x) )))l))))) Wio.- (1 ==))a((o)))) max B)x, min w/ (in)it)
ig
we can conclude the proof by taking Tμ 2 maX CA (min;ez, (n) ti Un.eo (e)) and Do (1+>)²
_(1=x)" In other words, we have shown that n > T3e there exists in E (u) and tu S n with Br, = io and such that (15) holds. Using = 1/2, the second part of Theorem 5 is obtained by taking the infimum over (e,z) [0] x (0, 1/(K 1)].
E.2.1 Consequence of tighter concentration
is direct to see that the proof of Theorem 5 will also work when using the concentration event ε, = śτ n 82 with (É) () and (E),) as in (27) and (29). Let us define
(m) 1 -2s log n + 2 2ogg(2 + logn) + 2),
fa(n) = -W-1 (s log n + 2 (2 + log n) + 2)
Using Lemma 50, we know that (n) s fe(n). Then, we will be able to show
[T| S (c.a))00.0)/(0001(KKK4
inf
max { (,, + 1, Sp
(e, 3)) + <())K(K + 1)/2,
where
2(1 + 77)² )+>>) ΣiEI,()) T/0,1/2(H1,)
T, (8, = sup n n 1-
(1 - ((iciclle.))
2
(ven- (con-1,0)+
1,5)+ + v fa(m))
Ap.eo (E, x7) U (e) + 13K + +1)
4(1 4(1+7-1)
(e, =h
with h2(2,8) > sup n n < f2( + 3.. Using Lemma 49, we obtain that
n 2 =fz(n)++ +
n
-lg(nn n - y) 2 s slog n + 2 log (2 + log n) + 2 - log =
11
log
2 loog(1 + 5) + 8 s+1
log z +
1
(2 (2 + log + + 2
2(1 + Therefore, we can consider h (z, y) 2 2(1 8) ,)22(2, y) with
=(1 + 8)
1+ s
2
h2(2,v) sup x log x
log Dog(log== +2+ log[=(1 + 8))) C(2,
1 s
where C(2,g) [म+ + - log log(1 + s) + T Therefore, we will obtain mulitplicative factor (1 + 8) instead of (2 + 8) in front of H (e). This improvement is rather mild, hence we don't "on'ten elaborate on it further.
35

---

F Probability of error and simple regret
Let > 0 and B E (0, 1). In Appendix F, provide analysis on the probability of error and the simple regret of EB-TC with fixed proportions 3 and slack eo > 0 (Theorem 6 proved in Appendix F. In Appendix F.2, we provide upper bound on the unverifiable expected sample complexity of EB-TCe. (Theorem 7). Then, by using Theorem 6, we prove that the policy pulling arm at time has constant induced regret (Corollary 2 proved in Appendix E.3). In practice, will mostly be interested in the case 3 = 1/2.
Theorem and Corollary is a corollary of Theorem up to some additional computations on the complexities (H, (eC,)E 1], which we will detail below. Theorem 6 provides upper bound on IP,, (%n $ Ig (1)) holding for any time n and any error 0, and upper bound on E,, Ms,. holding for any time n2.
Theorem 6. Let En > 0. For all 2 0, in(()) = if E 4.41) and i E [C 11, otherwise in(E) Cy. For all E [C₂, 11. let C.(Eo) 24, - Eu and Cig(Eo) = 2 2 3,- + 350 For
all i E [C₂- 1}, let ()( == minzeli m (1, (o), (u, where
Hi)(u, = (1)) max (22zt11 Ch+ls(Eo) }
2
C₁
+ max max (C)+)(50), C
Σ (k))++++++++
Σ
(c((k))]
k=++1
Σ
(k((k max { (C+z(E0), C541)(E0), v22=") }"
kmj+1
His(1,00) = 2/r"(x]
+ max (00+) sT Σ (Cn(k)] + 2 (())
+1
(Ai+1 4,)²
k=
C₂ +
Σ k=j+1
(c,(()
max {C 12
The EB-TC algorithm with fixed proportions B = 1/2 satisfies that, for all E DK and all 2 D if the algorithm has not stopped yet, then
K(K +1
n- 5K2/2
VE 2 0, P. (2n $ I=())) S 1 (E A max
e2
2
(c),,,))(HH,
E. j4+ pr.] K(K +1)
n n 5k2 1 (H; Eo)
(2 + l)
Σ
(Ai+1 - A:)p
2
iE|C,
where p(z) = x exp((2) and D = 8H EH, (o)) 5K2/2 with h2 defined in Lemma 51.
5K2 /2,2 log (K(K + 1)/2))
Hardness of BAI We have C2(Ea) 21-1 min cp and C2.1 = 24-1 min + +35²1 Then, we
obtain Hi (1( HI, (4, so) = K(2A min + +5 1y2 since
Cn
(p)1 min + Σ (k)) max (Co(eo). v2A_ 50) 4
k=2
This corresponds to the complexity of the two-groups instances which are defined as DA == {V E DK CN = 2, A2 = }} where A >> 0. More importantly, it corresponds to the complexity of identifying one of the best arms, i.e. taking
yields
Po (In (x)) < K(K + 1)
- 5K2
2 log logn)'p
8K min + 3E 1/2
36

---

Hardness of e-BAI Let >>> 1 and E [6]. We have (e) = 2 A -1
-,,1-A, 3 Cjo1
24 -50- < 24
2
i+1 and v S 2 jt1 for all k 2 + 1. Direct manipulations show that,
for all i >> 1 and all j E [i]. we have
A5 +1
+ 35 {
max(He,((H Hes (n) s K max 2 j+1: 2
A1+1 - A
Therefore, we have
Ay/50 +1
+ +300" }
Eo) & K min max jeli
22
A+t1 - -j
Taking j and then j 2, we see that, for all illi>> 1,
H,(p,,)) Eu) S K max { {2A -1 3 + 24 141 |²
2 H2(())
24g 1 2 Amin +1
S K max { Amin/ + + 30
2
H,( < K max
3E0
Ai+1 Amin
A3 Amin
where the last inequality uses that A3 I A++1 for all i>> 1.
Similarly, we can derive lower bound on H, H,, so) by noting that H1, so) 2 minje(H] Hes For all j E [i], we have that v2A -1 j+1 2 v24 Cs+1lEu) 2 2A Eo and C:+1,((0) Z 2 + 36 hence we obtain
Hi(u, 2 min (4, 2 2KA jE[i]
Three-groups instances The three-groups instances are defined
DA.A
{ ED |K| C.= 3,=3,22 A, }} where A > O andd A > A. Above results yield
H2(1,60) S K A/50 +1 A + +3551
K
=
min (A A, A, }
E1 Proof of Theorem 6
In the following, we consider sub-Gaussian bandit with distribution v IR having mean parameter a R In particular, our analysis holds when several arms have the largest mean Ja,
Let Amax = max P. - Fg. Let E be an analysis parameter (i.e. not the error parameter from
the stopping rule (3)). When 1 > A Amax, we have Ie, ( 0. hence (2n & Ie, (p)) 0. In the
following, we consider E E [0, A Amax).
For all n > K and 8 E (0, 1), let En,5 = Eh,0 n Eh with (E),))a and (8% as in (27) and (29) for = i.c.
2f( 8)
E1
Vk E [K], Vt S |Pex ukl <V
Ne.
VI sn, 1 - (1,x)) (wi -pw)l
62
((i,k) E
(2
n,
VI/Ne, + +/NN,
where
1 W_ 1 (2 (oggl11///// + log(2 + log m) + +2),
f1
2 f2 5) = W-1 (log (1/5) + 2 log (2 + log n) + 2)
Using Lemma 50, we know that fi $ fe(n, 5). Using Lemmas 42 and 44, we obtain that Py(E < K(K+1) 8.
37

---

Suppose that we have constructed a time Te, (6) > K such that En,o S {&n E Ie, (n)} for > (6).
Then, using Lemma 48, we obtain
K(K + 1)
(6n & (1)(
(6 n> T,,
2
We will construct an infinite number of times hence taking the infimum yields
(Te, (d, EEE(0.. such that the above property holds,
K(K+1) inf(6 n
(u $ Is, -
inf ec(0,5]]
Ta {),
2
This proof strategy the one used to prove Theorem
Let E E [0, Since in = B our goal is to construct a time Te, (6, such that
Vn > Tap (6, E); En, [ & Iz, (1)) = 0.
Error due to undersampled arms which are not gi-good, i.e.
Let us denote by (e,),)(n,)) the of undersampled arms
UE,E,,(n, = Is (w) nill N₁. S (C with Ce. == min (1) (1) A
Lemma 35 shows that, for n large enough, a necessary condition for an error to occur is to have an undersampled leader.
Lemma 35. Let E1 > and E0, Let (e)s(()) as in Lemma 5 and define
2[Ix(1))
== Hp (E) min (. -.)
(19)
Let us define
4H (p, Se,e = sup n min(B, 3}
(3/2 (332++1))
For all n > Se,e1,om)))), under the event En,,, we have B & (M) implies that BEB E (n,
Proof. Let (H)) = Le and ge,eo () 18 1H (e)
min( 13.1--3--41 Fe 8) + 3K(K - 1)/2. Using Lemma
and the pigeonhole principle, there exists i0 E Ie(u)) such that
Σ Tn(io. 2 (n 1 g5.ea (n, 8)) /1g
Therefore, we have
Nn,io 2 3 Σ Th (io, (K 1) (n Ie,co 8)) /T= (K -1).
Let Sc.er.co.p1 (8) defined as in the statement of Lemma 35. Direct manipulations shows that
I B (f, 5) max Ce. Ce.s K x1)}
Se, 2 sup n n 1 15 Ir.eo (n, 5) +
igZe, (M)
Therefore, we have Nn.ia > fn, d) max (u) Cs.; for all n S,,EL.oo.()).
Let n. (o)) Suppose that BEB = i Ic, (n). Using Lemma 31, under the event En,8, we obtain that
min,N No.io) < (f,
S 4Cc,sf((n,))
(Jin 11,)
Suppose towards contradiction that S = Nn.to then we have Nn., 4Cenfe(n, 8). This direct contradiction with Nz..o 4f2(n, maxiez, (N) Ce, since n > Se.e (8). Therefore, we have shown that min (Na,, Nn.io) = Nn.i, hence Ue (n, 6). This concludes the proof.
38

---

No remaining undersampled arms Lemma 36 shows that, if there are still undersampled arms which are not Egooo,, then either the leader or the challenger was not often selected leader or challenger.
Lemma 36. Let 61
0 and E [0, Let A)(E)
minggI, Ak.
(1,6( = 2 m (4) (n) (A) + 0 and Cp,o(() = 2/)
A,/ent1
E. Let Agsn max(CH,eo(E) (n for all E (I,(M) (()) U ([K) Ie)(1)), and otherwise Ae,en.out = max{Cp,ee Ceeo (2, for all E (1) \ (I(().. For all n > K,
max (E)) Cuso(E, for all i E (w)), As,
under event En for all & E [n] \ [K] such that (n, + D, there exists is E [K] such that
4f2(n, 6)
Te(()) S
(in 1 B} Ascr,oo + +(KK - 1)/2 and T = T +1.
Proof. We will be interested in three distinct cases since
(Uecr,(n, 8) * 6) (U, n ( B C. #0}
u (Ueene( (n. 6) * 0, (n, 8) n ( (B cTC] = 0, B & I [1))
U ( 6) # 0, Un 8) n (D,e0 , cCC] = 0, B E I [x)]
Case 1. Let E [x] \ [K] such that { Ct CTC) n U (n, 8) + 0. Let hy E (BF n an, 8). For this kt & Te, (1), we have T2+1 (kt) = (k+) + and, by combining Lemma 31 and Nr, S kc fn 5), we obtain that
No. Ti(k)) S min 33 3}
3(K - 1)
Ce,k, + 3(K 1)/2.
2 min 1 3}
Case 2. Let E [n] \ [K] such that (n, 6) # 0, Un.,,,(n, 5) n {BFR C. = and BEB & I (n).. Let (e) and Ci.Eo (e) defined as in the statement of Lemma 36. Let DEo.E. = ( for all E i (M)), Dea.E.i = Cy.co(e) for all i E [p) \ ("),,, otherwise Deo,e,á max ( 2/42]. Using Lemma 32, there exists k. [K] such that
4f2(n,8) 8) D De.co. + +3(K- - 1)/2 and T = (ke) +1. Tx():) < min 1 1-3}
Case 3. Let E [n]] \ [K] such that U Us (n, 5) + 0, U (n, 8) n BBBB CFC = 0 and B e (p).. Let jo E (n,..,((, 8) \ {BFTh CTT) ). which is possible since U Un,n, 5) n (B FR C. and (n, 6) & 0. Let denote by (DEB CTC) = (i.j) with E (x) and j # jo- Using the TC challenger, under the event En,s, we obtain
#4 1i0 tou + (2fe(n,0) M4, - Me.jo + ED VINNo, 1/NeJo
M4,5 Ma, + Eu V1/NI, 1/Ne.j
V1/Ne, + 1/No.oo
2 BOv min(Ne,, Ne. N/.
Since (4; Pijo +o 2 Eo 0. we have
1/ Mi0 + Eo
I / /NNis - Mi0 + Eu) + 22f2(n.
VI/N,,i 1/Ne.jo
14 M3j + minneeT. (n) - M5o0) +1) v 2222(n,6)
2
Using Lemma 31 to lower bound min( (Ne,,, No.) and br Pio I Ajo for all i E I (p), direct manipulation yields that
4f2(n, 8)
min( <
min 33 Cunoles + +3K - 1)/2.
39

---

where (5,EE) is defined as in the statement of Lemma 36, It is direct to see that Cp,co (E, max (1/50, max, (m) C. and C..s 2 2/4 for all i & I, (1)). The above shows that there exists & E [K] such that
(n, (k(k+) min [3, 1 33 ( + 3(K 1)/2 and T (k(kk)) +1.
Summary. Let us define (Ae as in the statement of Lemma 36, Under En,o, have show that, when Un,,,,(,, 8) + 0. there exists is [K] such that 4f2(n, 8)
Te(4)) v
min B, B} Ac + 3(K - 11/2 and Te+1(1)) = TT(()) +1.
Lemma shows that, for n large enough, there is no undersampled arms which are not E1- good.
Lemma 37. Let 81 and [0, Ler (e), Cn.co (5, and Cu.so (6) as in Lemma 36 and He (1, = [((( max/ (E) EE)
+ (I) \ (T))) U ([K) \ Ie, (P)) max ()))(E ma (5), CL (I, v20,112
Σ
(20)
ET,,, (T)()))))))
Let us define
Te,1150.aa - sup {nl 4Hc.e, (p,
min min [2(n, 333 2//K///
For all n > T Te,e1,Fo.u (8), under the event En,g, we have U Ue, (n, 8)
Proof. aor n > K, under event En,o, combining Lemma 4 and 36 for Ae(n, 8) (Ue,s, +
0} and Di(n, min -B] Ac.eivo. +3(K 1)/2 yields that
4)
4f, 5)
Σ (U +1)) min - 3} K++
He,e (H, Eo) 3K(K- - 11/22.
where we used that EvE[K] Ac.en He,e, (H) where He,e, (H,, Eu) is defined in (20).
For all $ Ie, (m), let us define
tx(n, d) = max (t E [n] \ [K] i
By definition, for all & Ir,(H), (u), have E (n 8) for all I (K, (K,4(n,0) 8)) and i Ueee.a(,,6) 8) for all E 0)(n,0),n) Therefore, for all E (K, maxigI, (w) 4(n ()]. we have Ueer,(n, 8) + A and (n. 5) = 0 for all tllt> maxieT (w) (n, 5), hence
max (t:(1, K) = Σ kgI, (w)
11 (U (n, t=k+1
min 3} He,e, (0, +
- -K(K21)/2
Let Te.e (6) defined as in the statement of Lemma 37. Direct manipulations show that
4f2(n,
Te,e (0) 2 sup n n Ks
min(8,1- He,e, (p, + +K(( - 11)2
Let T Te.en.o.u (8). Then, we have
(n, 5)
K min B, 33 He.e, (H,e,( (H, + 3K(K - 1)/2 2 max (t,(n, 5) K), igI,, (H)
hence > max (u) (n, 8). This conclude the proof that Us.si.m (n, 8) 0.
40

---

Upper bound probability of error Let Se,a (6) and Te.e, eo. (6) as in Lemmas 35 and 37. For 3 1/2. direct manipulations show that m 50, (6), (. S E,, (6) with
Bes = suu {n n S 8 max (e Eo),
Eo); Ha, (1, (2)) +
Combining Lemmas 35 and 37, for all n >> Ee (0), we proved that
En, n fin $ Ie, (1)) = En,o n (B $ Ie, (4) S En,o n
0} = 0,
hence ( $ Is, (4)) [ En,
Using Lemma 48, Po( I K(K + 1)6/2 and taking the infimum over [0, yields
Pl $ Iz, (1)) - K(K+ +1) inf(d n (e,
where we used Lemma 52 and inf sej,ss) Be (0) Bes,com (6) with
Es (0) = sup n 8 inf cE(0,a1)
max (u, EO), Hes,e (1, (u. (2)) +5k2/2 +
Using Lemma 52, we obtain that
Py (In Ie, (p)) S (c,) K(K + 1) e2 + l)
8infee(a.eu) max H 5K2
Eo), He,e, (H. (H.
where p(x) x (eex((xx))
More explicit complexity In order to obtain a more interpretable result, we notice that the depen- dence in (1) of He,e, (j, sn) and He.es (u, is only with respect to its position in the ordered means. In the following, will replace the dependency in (c, by dependency in such in- dices.
Let E R.K, Let us denote by C₁ = Has lie E [K]]] the number of different arm means in For all i E [Cn], denote the set of arms having mean gap A; by (i) (k: [K] 14 1 where the gaps are sorted by increasing order
A.)
0 Ai <2 < Ac.
In particular, we have (1) i (1²) and Ac, Amax. Let us denote by
if (AAAA)) with i 1]
VE 0, i,(ee) 1c Cp if Ac,
(21)
direct see that (e) = max E CC)), (I)) for O. For all E [C,, - 1), let us define Hz(,, Eo) = minje(1) max He, (H, Eo), Hi, (M, so)) with (u,( and Hi En) as
in Theorem 6. Let 1 2 and E [0, E1]. Then, we have by direct manipulations that
inf max{ Hs,e, (u, Eo), He,e, (o)) (,) sE(0.e.)
since He, (H. 5o) (e) Eo) and He (1, = (H This concludes the first part of Theorem 6, i.e.
K(K +
n 5-5K2/2 8H, 8HH,,(e)((4,
Prn & Iz, (1)) S (8) Amax
2 2 log
2
41

---

Simple regret
Since μ., Mi., is positive random variable, we obtain that
+oc Pulu+ Min @I)dEi
-a-= [ Polin (w))dds
Bulu+ [.s.]]
=1=0
As function of E, our upper bound on Pu & Ie, (1)) is piecewise constant on [A,, A+t1) for all i [C,, and has null value for E 2 max. Our upper informative, i.e. smaller than 1, for all
2 Dr where
D2 = 8 (11, Eo) h2 (8H 6o). oo) 5k2 / 2, - log (K(K + 1)/2)) + 5 (), log (2 log 2)) + log (K(K + 1)/2)) 5 5K2/22
sup {a
where the inequality is obtained by using Lemma 51, and h22 is defined therein. Therefore, we obtain that, for all Dyr
Eolus - p K(K + 1 e2 logn))
7n-5k' 70-5K2/2
Σ
(Ai+1 A:)
2
8H,((1,
iE IE
which concludes the second part of Theorem 6.
F.2
Unverifiable sample complexity
The (e, -unveriiffeel sample complexity defined as the expectation of the smallest stopping time i satisfying P(VL 2 i, (x)) 2 5. Theorem 7 gives an upper bound the unverifiable
expected sample complexity of the EB-TCr, algorithm with fixed proportions 3 = 1/2.
Theorem 7. Let > O and ô E (0, 1). The EB- algorithm with fixed proportions 3 = 1/2
satisfies that, for all v DK with mean for all 2
Pv (Vn > ( (H), eo); in E [e()) 2 1
The times (1, Ea) are the (e,6)-unverinn 8)-uveerifiaale sample complexity of EB-TC defined as
vi E [c,, E1, = l12 (log(1/6), (11111,),H(H,,,, 8H; (H, (p,, EO) log (K(K + 1)/2) + 5K2
(22)
with (H((H, defined in Theorem 6. 2AW 1 log(1/0) + 2A + log(2A)) satisfies that hz2log(1/6)) A, B) =8-10 A Alog(1/5)
The function h2 A,
Oloo lo)(1
Proof. In Appendix F.I, we consider the concentration event En,s that involved tighter concentration results with thresholds fi (n, o) and [2 8). Let n >> K and 5 E (0, 1). It direct to see that the same argument holds for the concentration events En,s = Eh n E with (E% ()sk) and (E k>>)
as in (24) and (25) for s i.e.
2f((n, 8)
E
Vk [K], V n. |PE.
mul <
Ne. S
E9 ((i,k) [K]2 S. vi sn 1(u,i - Me,x)) ((i-mi) mn) 2f22(n,
VI/No, + 1/Ne,
where (n 8) = log(1/8) + log + log (K(K + 1)/2) and f2(n, = log( (18))) + 2 log log (K (K(K K + 1)/2), which satisfy fi fi I fz(n, 8). Using Lemmas 40 and 41, we obtain that (E
n,5 <
In the following, we the notation the gaps introduced in Appendix F.1, the complexities (o),,,,))se,,e defined in Theorem 6 and the function (s) defined in (21). To prove Theorem 6, we obtain as an intermediary step that: for all Es (in Iz, (μ)) C eC where
sE(O,s.] ( = sup n n 88 inf max He (M, 5n). (4. + 5K 2/2
= =sup {n < 811 tel,,,, + =
42

---

where the equality holds by using the rewriting of the complexities done in the end of Appendix F.1.
Let A (e()) and B (,.) log (K(K + 1)/2) 5K2/2. Using a proof similar to Lemma 51, applying Lemma 49 yields that
(e1)
(0, + n
2A n + log +
log
n
1
log (0/1))) +
B
1og(2A))
2A
24
2
2A
2AW -1
log(1/6)
B
1og((2))
2A
Let us define h2 (100)o((1)))000 A, B) = 2AW -1 log + 21 define
+ +log(2A)) and, for all i E [G, -1],
(1,((1,50) = hu (log(1 (1)() 8 (1,, (1, log (K(K + 1)/2) +2 Therefore, we have shown that, for all E 2 0.
Fn > (,,,(:)),((4 so), in $ Ic (1)) _ cC n,
Using that (E S we can conclude that, for all s 2 0,
Py (Vn (p) in E Ie, (4)) 5.
F3
Cumulative regret of induced policy
Given a stream of recommendations (G,)m k. an external agent aiming at minimizing its cumulative regret simply pull the arm i, at time Since the EB-TCa algorithm has anytime guarantees the simple regret of this recommendation, the regret of the induced policy is constant (Corollary 2).
Corollary 2. Let EO > O. Let (in)>> be the recommendations of the EB-TCoo algoritlu with fixed
proportions 3 1/2. An agent pulling &n
at time n has constant induced regret, i.e.
AA E DK VT > K,
Σ
pt..] p=, =0 Ey 1u+
K max
(log
K
minn ( co}s
min A min: }
R= R=K+1
Proof. Using that H1(14, Eu) = maxie Hi((,, a direct upper bound based on Corollary
yields that, for all n 2 Dur
5K3 811, (14 E0) Let c > 0. Let f(c, x) = (c (x)(x))xxxx(())) for all x 2 1. Let
Eylu. mn,1 K(K 11) (2 + +lg n)² Amax (H1(H
5K5K222
exp
0, > 0. By integration,
for all C' > A+ B, we obtain
T
Σ
fle, (n B)/A) Bm)
< A /. f(c,I)dæ= = A + +cC1 + C2)
where C. = 51 log(z)" exp(-x)d < too for all a 0. For n 2 5K2, we have n I 2(n 5K2/2) Recall that Dμ = 87, (H, Sn)h22 (8H, (1,, e0,, with h2 defined in Lemma 51. For all n < 5K2 /2+ + D,,, we have trivially that Ey [u. [a..] Amax. Therefore, we obtain
log (K(K + 1)/2)) + 5K
K(K + 11)
Σ Eyle, pi.. /5K a,))
e² Amax
T Σ
1 (2+ log (16H (1,,
n- 5K2/2
8H (1,,6)
n=5 (p.50)
K(K + 1)
< (5K2/2 2 D2)
2
E
Ammx
max
8H1 (4,))) (22 log (H,))) + 20 (2 + log (16H, (H, + C2)
43

---

Studying the function (2, 2), it direct to see that (2 y; -oト+o ([log(z))) for all a > 0, hence , is dominated by the other term. Therefore, by studying the dominating term when min (Ami, {o} -> 0, our upper bound scales as
K A max
O (K'A (log H1(44 (14 -
log
min Amiu+ $o}²
min Amin Eo}
where we used that H1 En) = K(2 min + 3) =
min (min(Amian Amin:o)
The idea of decoupling exploration and exploitation when minimizing the regret in the multi-armed bandits literature was introduced by [2]. At each round, the agent is allowed to choose one arm to explore and one arm to exploit at every round. While the agent suffers the loss from the exploited arm, it observes the one of the explored arm without cost. In the stochastic regime for instances having unique best arm, the Decoupled-Tsallln Tsallis-INF algorithm [33] achieves a constant regret O K/ Amiu). Therefore, in this setting, constant regret in Corollary does have the best achievable scaling in K and Amin.
Beyond synchronized policy When the external agent plays at time n, it is said to be synchro- nized with the recommendation rule. In all generality, one could pull arm ic(n)) at time n, where L: N- + N is non-decreasing function, and obtain similar guarantees as Corollary The agent can be slower than the recommendation rule (e.g. offline hyper-parameter optimization) hence L can be rapidly increasing, e.g. [(n) Bn K where B > The recommendation rule can be slower than the agent (c.g. pulling the same arm multiple times) hence L can be piecewise constant with small steps. c.g. C(n) /n + K. The communication between the agent and the recommendation rule can happen infrequently (c.g. paying to access the recommendation) hence L can be piecewise constant with large steps, c.g. [(n) ([n/B])a K where a
G Concentration results
The proof of Lemma 3 is given in Appendix G.I. Appendix G.2 gathers concentration results to control the empirical means and gaps.
G.1 Proof of Lemma 3
Proving that GLR stopping rule ensures the algorithm to be (E1, P is done by leveraging concentration results. In particular, we build upon Theorem 9 of [27] which is restated below. While Theorem 9 was only stated for Gaussian distributions. it is direct to notice that the result also holds for sub-Gaussian distributions with variance proxy o² = 1 (as the authors mentioned).
Lemma 38 (Theorem of [27]). Consider a sub-Gaut Gaussian bandit v with means μ E R.K. Let S C [K] and x > O.
Py En E N.
Σ Nm,
(Mm,k 12)2
Σ
2log (4 log (Nv, + |S|Co
I |S]
S
Se
2
KES
KES
where Ca is defined in [27] by Ca(x) minxe]1/2.11 go and
gG(A) 2A 22log(44) log log.loo(() ((2A)
log(1 A),
(23)
where Ç is the Riemann finction and Co(x) x + log(2:).
Since in i" (pn), standard manipulations yield that for all # in
(Hm,2, Mn,s + +1)² inf (Nn,a, (Mriin - u)² + N,. (1 - u e1)?)
1/Nn,i, 1/Nn,i WER
inf 920+61
(Nn,i, (prisn x)² + Nn,s(Mnntt v)
44

---

Let 1" = (p). Using the stopping rule (3) and the above manipulations, we obtain
P2 (Tan < +00,7,, 8ee $ Ie (n))
- Pv (Em N, Bi & Le, (1); i = i" (pmns
min inf (Nv,s, (nnin - x)² + Nn, - w)9) 2 20(n 1, 1.6)
kift 12ate1
< P., (3m N, 3i $ Izy (1L), i == ir (pn);
Nn (Un, -m,)2 Nn (Ha,e 12x))2 cccn
c(n cc(n-116)
P. (3n Nu (Un,i - 11)) -1:)² + Nn.i* (1bm,e p&r 2 c(n 1,,), (Wn,i-1a))
Σ
iET, (H)
where the second inequality is obtained with (k,
x., v) = (i", Mig pix) since i & Izg (w), and the third
by union bound. By concavity of x + log(4 + log(x)) and Nn + No, S ΣxE[K] Nn, = n 1,
we obtain
vi ş (1)) log(4 + log N,,, - log(4 + log N,, & 2 log + log((n - 1)/2))
Combining the above with Lemma 38 for all Iz, (1) and using that [Ie, (w)l 1 K 1, obtain
Po (TB < t $ Iz (1)) S
Σ
K - 58.
T (1))
G.2 Sequence of concentration events
Lemma 39 is standard concentration result for sub-Gaussian distribution, hence we omit the proof.
Lemma 39. Let X be an observation from a nub-Gaussian distribution with mean and variance proxy o². Then, for all ō E (0,
Fx [X] 2 2 56.
Lemma 40 gives a sequence concentration events under which the empirical means are close to their true values.
Lemma 40. Let 8 E (0, 1] and s 2 0. For all K. let (I, -og((16)) + (1 s) log x and
(f, 8)
wk [K] S n, MMex Mxl <V
(24)
No,
Then, for all n > K. (,(( <
Kg n
Proof. Let (Xx) be i.i.d. observations from one nab-Gaussian distribution with mean 0 and variance proxy o² 1. Then, E X, is sub-Gaussian with mean and variance proxy x² = 1/m. By union bound over [K] and over m E [n]. we obtain
(n, Nr,
P
3k E
[K], n, 1 mkl
2f (n. 5) m
Σ
P
Σ X₂
ke me m)]
sE(m]
< 8
Σ
Σ
n (1+s)
Kôn -8
kE|K] mEIn]
where we used that Pr,k 14 No. Σt 1 (1g k) Xs. and concentration results for sub-
Gaussian observations (Lemma 39).
45

---

Lemma 41 gives a sequence of concentration events under which the empirical gaps are close to their true values.
Lemma 41. Lerd E (0, and 2 O. For all n > K, let fe(1, 6) = log(1/))
1/))+ + (2
log(z) and
En = { (((,A) E [K] s.L. sLiik, Vt
- me,k) 104,5-
(14 [u=)]
< <V2f2(n, () (25)
VT/NG + 1/Ne.
Then, for all n> K, Po((E 9) =
-(K- 2n
Proof. Let (Xe)sEjn) and (Ya) be two streams of ii.d. observations from two sub-Gaussian distributions with mean and variance proxy o² 1. Then, my E X; Gaussian with mean 0 and variance proxy o² 1 + By union bound, we obtain
ma Ei=1 Y; is sub-
(Mti 14,1)) (14 -mx)
(4x))
P B(i,h) [K] sLiik k. 31 S n,
S {V2f2(n,6)
VINNi + 1/N2,
mi
m2
E
S
() +1/m2)
mi
m2
(s.A)E[K]3 befk (m Eln]
K(K - 1)
Σ
Σ
(2+6)
2 ōn ōn=
(K.))E[ i (m)(m))
where we used that (Mu,a- )4-) - (Mi. - pk)
No 1
11,= =
X
1 N,A E.= 1 (I, = k) Ns,k and concentration results for sub-Gaussian observations (Lemma 39).
Tighter concentration Lemma 42 provides concentration results on the empirical means, which tighter than the obtained in Lemma 40.
Lemma 42. Let 8 E (0, 1] and 2 0. Let W defined in Lemma 49, For all n. > K, let
f(,,o) 0) = 2
W (2 /0) + 2s log n + 2ogg(2 + log n.) + 2),
(26)
and
2h(n, 5) No,
E1,
wk E [K], < MALK mal <
(27)
Then, for all n > K, ((E n,6 )
Kb n
Proof. Let (Xs) be i.i.d. observations from one sub-Gaussian distribution with mean 0 and variance proxy 0² = 1. Let S, = EeElo X,. To derived concentration result, we use peeling.
log(n) 1. For all E [D], let N; (1 (1+ - For all E [D], we Let > 0, 0 and D = [log(1+7)
define the family of priors (N.,(2)
nN, 2x
exp (-*²gM) with weights w; D and process
M(t)
Σ wi (x) EE[D]
xS. - -ott) dx,
which satisfies (0) = 1. It is direct to see that (t) = exp (xS, - is non-negative supermartingale since sub-Gaut Gaussian distributions with mean and variance proxy o² = 1 satisfy
E Ex(exp(sX)] & exp(X2/22
By Tonelli's theorem, then M(t) is also non-negative supermartingale of unit initial value.
46

---

Let i E [D] and consider t E [N,, Ne+1). For all æ,
N (x) 2 V F
[ty())
V1+ fen(z) (1)
Direct computations shows that
1 xx7t) de + / (1)(() exp x. - 10-277)
S 2(1 + 7/6
exp
Minoring (t) by one of the positive term of its sum, we obtain
S 2(1 7)t
M(t) Z D +1++++)+++) exp
Using Ville's maximal inequality for non-negative supermartingale, we have that with probability greater than 1 6, log (t) S log (1/6). Therefore, with probability greater than 1 6, for all i EE [D] and t E [N; N4+1),
S 1
(1+ 5 l2g (1/0) + log D + log(1 (ee(1+>~1)) log(1 + 1))
Since this upper bound is independent of we can optimize and choose y as Lemma 43.
Lemma 43 (Lemma A.3 in 19]). For a, b 2 1, the minimal value of f(n) = (1 + n) + log(b + 4)) attained at 17 such that f(n") s
W 1 + b). Ifb 1, then there is equality.
Therefore, with probability greater than 1 8, for all i E [D] and t E (Nt)).
S2 -1 (1 + 2og (1/6) + 2og + log(1 + n))
t
W W-1 (1 + 2oo (1/8) + 2og (log(1 + 1) + log n) - 2 log log(1 + 7) + +log(1 + n))
W (2log (1/6) 2log (2 1) + 3 2lgg
The second incquality is obtained since D S 1+ Tog(1 The last equality is obtained for the choice '7" e2 - 1, which minimizes 1) log(1 7) 2 log (log(1 n))) Since [n] Uie[D) [Nr N441) and Ne, m4x) ExE[N [.. X,,k (unit-variance), this yields
log
P
3m S
X
W (2log(1/8) 2 log(2 log(n)) + - 2 log 88.
m s=1
Since 3 2og
and W -1 increasing, taking ön - yields
3t < / Now |Me, uul 2 (2 < 8dn-
Py
Doing a union bound over arms yields the result.
Lemma 44 provides concentration results on the empirical gaps, which are tighter than the ones obtained Lemma 41.
Lemma 44. Let 8 E (0, 1] and s 2 0. Ler W defined in Lemma 49, For all n > K, let
fe(n, 8) = W (log (1/0) + log + 2 log (2 + log + 2)
(28)
and
1(4, mr,)) (m4 -mx))
E0, = V(I,K) E [K]2 s Vt VSn,
V2fa(n,
(29)
VI/Nsi + 1/Ne.
Then, for all n K, (.((E
K(K-1
5
2
47

---

Proof. Without loss of generality, we show the result for arms ki, = (1,2). Let (X,)se(n) and (Y)).e[n) be i..d. observations from two sub-Gaussian distribution with mean 0 and variance proxy o² = 1. Let St.A = Exela 1 (I, = k) X, for all l E {1,2}. To derived concentration result, we use peeling as in Lemma 42.
Let > 0, 0 and D = log(n) 1. For all E [D], let N; (1 + +n) For all E [D], we log(1+n) define the family of priors (N,,(2) /
N 2
exp (- with weights wN D and process
Ak E (1,2), M&(t) = Σ ws / (2) tE[D]
(aS.. x² JeNN.. dr
which satisfies M (0) for all l E (1, As in the proof of Lemma 42, obtain that M and (t) non-negative supermartingale such that
S D V(L+ exp 2(1 + N)
vk: (1,2), M&(t)
where we used (11, E [D] and consider N1, E [N N1+11 ) for all k E {1,2}. Let us define M(L) = (1 Then, we have that M() is non-negative supermartingale such that
1 M(t) D ( exp
$
2(1
N
(1,2)
Using Ville's maximal inequality for non-negative supermartingale, we have that with probability greater than 1 - 8, log (t) log (1/0). Therefore, with probability greater than 1 - 8, for all (in 12) E DD and No.1 E [N N;.+1) for all E (1,
S
s 2(1 >) (log (1/6) + 2 log + log(1 + + + log(1 + n))
NE. (1())2)
Since this upper bound is independent of t, we can optimize and choose y as Lemma 43. Therefore, with probability greater than 1 - ô, for all (i1,22 E [D] and Nr,x E [N New+1) + for all k E (1,2).
S
Σ
2W -1 (log (1/6) 2og D log(1 17) +
N..
(E(12)
2W -1 (log (1/6) 2og (2 log n) + +
The second incquality is obtained as in Lemma 42 by using that D < 1+ Tog(1+>) taking 17* = e² - and using 3 - 2log < 2.
log
W increasing.
Since [n]] C Ulepp NN,, N.. S and Ne, pk)) = S. (unit-variance), this yields
No. (14, mx) 2 W - (log (1/6) + 2 2log (2 + log 2) < 5.
P
31 < n,
2
kE (1,2)
Let Cn,, 8) == W- (log (1/8) + 2og (2 + log n) + 2).. In the following, we consider that we are under the event,
Ni. 2
(pe, uu)² C(n,
En (1,2) = vt 1
kE(L.2)
which has probability at least (Pr.2 (2) is upper bounded by
8. Since it satisfies the above constraint, the quantity μ4,1 #1
max {Mr.1 12.2 I1 x2) nERa
subject to
Σ
No. 2
(14,5 - =x)25 C(n,
kE
48

---

Introducing a Lagrange multiplier the above optimization problem is equivalent to
min max a20 ZER
Pt,1 - Mr.2 - + + C(n,8)-
E
No.
(ue xx)
kE
Solving for by cancelling the derivative yields that 21 Therefore, we obtain as solution
Hl, aN111
and 22 = Me. oNe,2
min a0
aC(n, 8)
Σ kE(1,2)
2C(n,
E No,
2a
Ni.
kE(1,2)
where the last equality is obtained by solving the optimization since the derivative is null at a V ExE(L.) 20(n,6)N1..' By symmetry, we obtain the same result to upper bound Mr,2 (42 (Pr.1
11). Therefore, under 6,, 2), we have shown that
|4.1 111 (H422 p2)l
V 2W (log (1/6) + 2 log (2 + logn) 2)
1/Nr,1 1/N,,2
The same argument as above can applied for all (i, [K]² such that + direct union bound yields
Σ P. (in K(K -1) 8
()((
n
(B.
where we used the inclusion proven above for (n, 8/n²). This concludes the proof.
Global events Lemma 45 combines the above sequences of concentration events.
Lemma 45. Let 8 > 1. Let (Eu,)n>> and (E2,))>>k as in (24) and (25). Let (&) (n and (ER m as in (27) and (29). Let us define En,5 En,6 O Eh and En,s En n En for all
K. Then,
K(K +1)
K(K + 1)
and EP < ((s)
(())
2
2
asK
Proof. It is direct that
K8
K(K - 1)8
K(K + 1)
Σ PE Σ
((8)6
2n
KSK
B>K
RSK
The proof be applied to upper bound Σnsk (EC
H Technicalities
Appendix H gathers existing and new technical results which are used for our proofs.
Key technical result Lemma is the key technical ingredient on which our proofs rely on. It builds on sequence of "bad" events such that, under each "bad" event, either the leader or the challenger was not often selected as leader or challenger, and shows that the number of times those "bad" events occur small.
Lemma (Lemma 4). Let E (0, 1] and n > K. Let (Ar,s(n, 8)) R be sequence of events and (Di(n,))) be positive thresholds satisfying that, for all L [n) [K), under the event Ar, 8),
Di [K], Te(i)) S Ds. () and Te42(1)) = Te(i)) +1.
Then, we have Σi=kal (A,,(n, 8)) < Eie[K] Di(n, 8).
49

---

Proof. Using the inclusion of events given by the assumption on (A, 0)] we obtain
Σ I=++1
(A2 (1,
(3 E [K], T.(k+) & (n, 6), T (ka) = T<(ke)) +1)
t=K+1
ΣΣ (7.(0) & Di(,,)), T+t( T.(1) +1) Σ di kc|K] [=K+1
<c[K]
The second inequality is obtained by union bound. The third inequality is direct since the number of times one can increase by one quantity that is positive and bounded by (n 5) is at most Di(n, 8).
Tracking Lemma 46 provide general results for the K(K - 1) tracking procedures both for IDS and fixed proportions, which includes the ones of Lemma 2. The main theoretical argument behind those results is based on applying Theorem 6 in [12].
Lemma 46. For all > K, E [K]. j + i, we have
-1/2 S No - (1- (i. () 2 i.e. (In.)) - 1/2
and
No - (K 11/2
N + K minjzi (i,
En((ss)
maxj Bi(i,))
3#1
Let 3 E (0, 1). For fixed proportions B, we have
3(K - 1)
Nn. 2 min B} (Ta(t)
2
Proof. We have K(K- - 1) independent two-arms C-Tracking between the challenger and the leader. Theorem in [12] yields the result. The second inequality is a simple re-ordering.
To obtain the second part, direct manipulations yield that
Σ (i,j,) No. +1 & Est((Ta(i,)) - + jtL
(n(1.
minjzi (1,5)
which allows to conclude since No = EEtts No.)). The lower bound is obtained similarly.
The third is a direct consequence of the first part since
Nn,i (T. No..) + Σ NO
Σ
+ Σ + +3( 1)/2 }
n
2
Σ
Tn((,)) + 3) Σ
(n(j. 3(K - -1122
2f1
jfi
Having shown
Nn. B (T
3) Σ ET.(..))
max
< <3(K - 1)/2
(E[K]
is direct to conclude.
Methodology Lemma 47 is standard result to upper bound the expected sample complexity of an algorithm, e.g. see Lemma in [11]. This is a key method extensively used in the literature.
Lemma 47. Let (En)n> K be a sequence of events and T(5) > K be such that for n 2 T()),
E, C (To I n). Then, [r] & T()) + Σn>x (E)).
50

---

Proof. Since the random variable Tá is positive and {To > n2} C Ey for all 2 T()), we have
Ey [Tal= = Σ
PA( > T()) + Σ Po(E)))
n20
m27(6)
which concludes the proof by adding positive terms.
Lemma 48 is a key method to upper bound the probability of error of an algorithm.
Lemma 48. Let & 2 and (En, K, 1, be a sequence of events such that P, .) I C8 with
C 0. Suppose that Tg (ō) > K is such that for n > Te (6), &,, S fin E I. Then,
Pu(ia $ (n)) S C' n > (o))))
Proof. Using the assumption, we have (b & Ie(p)) s P n. & C8 for all n > Te()). Taking the infimum yields the result.
Inversion results Lemma 49 gathers properties on the function W-1, which is used in the literature to obtain concentration results.
Lemma 49 ((22)). Ler W -1()) = - 1-1e-e-) for all x 2 1, where W-1 is the negative branch of the Lambert W function. The function W W1 is increasing on (20) and strictly concave on
(Lo) In particular, W' -1(z)=
W (6))
for all x > Then, for all y 2 1 and 2
W W-1 S x
y S x - log(z).
Moreover, for all x >>> 1,
+ log(r) < W- (1)) S + log(x) min
2
Lemma 50 provides an ordering on the thresholds for tighter concentration results. It leverages properties W-1- Lemma 50. Let 2 Let W - defined Lemma 49, For all 5 (0, 1] and 2 1, let us denote by
1 W -1 (2 + 2s log(2 log n) + 2),
(i
2
fe 8) = W- (log (1/0) + slog + 2og (2 + log n) + +2)
Then, we have (n, 8) S (2(
Proof. Let > 0 and b 1. Let define f(x) = W -1 + b). Using Lemma 49, we have
f'(x) = x²
W (ax + b) - 1- W (ax + b)
ax
Therefore, we obtain f((x) S if and only W -1(ar + b) 2 az + 1. Since W -1rr +b) 2 or +b and 2 1, the function f(x) is decreasing for all 2 1. Therefore, 2 W - (2x + b) I <a + b). Applying this result with a log (1/8) + s log n and b = 2 log(2 logn) 2 2 for all 2 we obtain Í (n, 8) 6).
Lemma 51 is an inversion result to upper bound a time which implicitly defined. a direct consequence of Lemma 49.
Lemma 51. Let W defined in Lemma 49. Let A > 0, B > such that B/A + log A > 1 and
C(A, B) = sup {x
x < A x + B}
C(A, B, D) sup {x x AW - (2 log (2 + log x) + D) + B}
Then, C(A, B) < (A, B) with (2. = zW - (u/= log 2) and C(A, B) < Ahz (A, B,
B where
h2(2, y, 2) inf {2 log 2 log (2 log( ru + v)) 2 2}
51

---

Proof. Since B/A+ + log A > 1, we have C(A, B) 2 A, hence
C(A, = =sup {a x < Aog((2)
B) sup {x 2 x < Alog(z) B}
Using Lemma 49 yields that
B
= x AW -1 / B + log 1
x 2 log x B =
log
2
log
A
By changing the variable, we obtain
C(A, B, D) = B + A sup {y < W -1 (2 log (2 + log Ay + B)) + D)}
Likewise, Lemma 49 yields that
y 2 W -1 log (2 log(Ay + B)) + D) y log log (2 log Ayy + B)) N D.
Lemma 52 is an inversion result to upper bound probability which is implicitly defined based on times that are implicitly defined.
Lemma 52. Ler W -1 defined in Lemma 49. Let A > 0, B > 0, C > 0, E > a 3 > 0 and
DA,B,C(0) = sup x I A(log(1/6) + Clog x) + B}
(A = sup { x .W
A W -1 (a (log(1/6) C' Colo((3 + log x) + E]) B
a
Then,
inf 1 x> DA,,,c(O)) <x exp
- B A
[nf(ō|=>> DAB.C....(()) SB
x
B
)
1/a
(3 + log 2) -
exp
(- B
A
Proof. Direct manipulations yield that
- B
<> (A, = > A(log(1/8) + C'log)) +B = 8 < x exp
A
Likewise, using Lemma 49, we obtain
B
x > DA..C..EE,((.)
a
W
(a (log(1/8) + Cloo(B3 + log x) + E))
A
- B
I - B
log
a
log(1/6) + C'log(B (B + log + E
A
A
8 <
E
x
B
1/a
(B + 1 exp (- (---
A (
B
A
Multiplicative setting
Let DDK' with mean parameters I (Rt)*. Compared to the additive setting, only consider strictly positive mean parameters. In many applications, this assumption is natural. In other applications, there is known lower bound the value of the true mean parameters, hence can simply translate the problem by adding this lower bound. We also note that the problem identifying which arms are above the threshold () the thresholding bandit problem, which has been extensively studied in the literature. Overall, while this assumption might seem restrictive, we think it is rather mild. Since the means strictly smaller than 1. Given a multiplicative error & E [0, 1). the set of multiplicative e-good arms are denoted by T.mul (μ)) == {i E [K] A; < p.E). We will refer to this problem as multiplicative e-BAI.
strictly positive, the multiplicative error has also to be positive and
First, we discuss the characteristic times involved in the fixed-confidence multiplicative s-BAI (Appendix 1.. Second, for en E (0, 1). we present the EB-TC= with IDS or fixed 3 proportions (Appendix 1.2). Finally, we prove that EB-TC= asymptotically (resp. {-)optimal when using IDS (resp. fixed 3) when combined with the appropriate GLR stopping rule (Appendix I.3).
52

---

L11
Characteristic times
Let v E DD with mean parameters μ E (R unique best arm, i.e. (p) {i*}. Let E 1). The (B-jcharacteristie times for the fixed confidence multiplicative E-BAl setting with Gaussian bandits (u, 1) are defined T (u)
) We assume in the following that there exists
(B) Tgp (v. i) and Tipe (p) min T23 (p, i) where
max min (4: (1 8) 1)12 2T (u))"(((00) wEAK, j 1/3 + (1 e)2/113
(30)
We denote by w (p, i) and wgg (n, i) their maximizer, which we refer as the (3- (3-)optimal allocation for multiplicative e-BAI.
Even though the multiplicatiie c-BAI is less studied, it is direct to see that it has similar properties as To(.). Due to the factor (1 - =)² in the denominator, it is not possible to simply
reduction to
BAI problem as we did for the additive s-BAI problem (see Lemma 9). Since the properties listed in Appendix C are obtained by studying the optimization problem defining To(,), we will have the
same properties for T (H) by accounting for the extra multiplicative factor (1 =)?. We list here the properties on which our proof relies:
T (4) (0.) T (u, it) and 1 (n) T meaning the unique best arm corresponds to the arm which is the easiest to verify multiplicative e-BAI.
w [w=")} and will (4) {wr }, meaning there is unique (3-)optimal alloca- tion which satisfies minse[K] (wmmll); ) > 0 and minse[k] (wo 0.
There is equality at the equilibrium the transportation costs, meaning for all i + i*
(Hi- (1 - =)) (wmnu)) (1 8)² ( 21 (p) and
(ps - (1 - =)
21 my -1
(1)-1
B-1 + (1 8)² (w
(31)
and the multiplicative overall balance equation is satisfied
(wemil))
= (1- (0)
(32)
(wnnnl); )--
For the sake of space, we omit the proofs and defer the reader to Appendix C for ideas on how to prove them.
1.2
Anytime Top Two algorithm
Let Eo E (0, 1). The EB-TCa, algorithm, detailed Figure 3, has the same structure as EB-TC There are two differences. First, the IDS proportions are 3n, (i. = Nn., - =00) when considering multiplicative e-BAI. Second, the challenger will be based on transportation costs for multiplicative c-BAI, namely
2 + Nn.;)
TC
Mn, - (1-Ea))mm.
C E arg min
(33)
B
V//N,,Be B + (1 - -00 ///N.
Stopping rule for fixed-confidence multiplicative s- BAA requires a stopping rule, which will be different since we tackle multiplicative =-BA Given an error/confidence pair (e, E (0. x (0, 1), the GLR, stopping rule [15] prescribes to stop at the time
Similarly, the fixed-confidence setting
min Pn,.. (1 - 6) 2 220(n 1,5)
mul = inf T2.5
n > K
(34)
VI/Nn.. + + 8))//Nn,
where e: N x (0, 1) +
R4 is threshold function. Lemma 53 gives threshold ensuring that the GL... stopping rule is (c, P)CC for all 10,1) and (0, 1), independently of the sampling rule.
53

---

Figure 3: EB-TCa, algorithm with fixed IDS proportions.
1: Input: slack 6n E (0, 1), proportion 8 E (0, 1) (only for fixed proportions). an solana
2: Set in E arg [ Mn,d, B in and _
E arg + v 1/NN n. on +01 /o)
3: Set [fixed] (1.j(
or [IDS] (a( Nn.j/((1 -o) N,, + Nn.) and update
(i,1(
TC
to S (1 -1- B Cn TC "TTnnt(BB Cn Cn otherwise set if N
th
4: Set In
On
n.C,
In B
5: Output: next arm to sample Ln and next recommendation 8n.
Lemma 53. LetE [0, and 8 (0, Given any sampling rule, using the threshold (4) with the stopping rule (34) with error/confidence pair (s, yields a (E,6)-PAC algorithm for sub-Gaussian distributions.
Proof. The proof of Lemma 53 actually almost identical the one of Lemma 3. The only change is at the beginning of the proof. Since i, = i (Hm)) standard manipulations yield that for all i # in
(nn,3, (1 (1-E)) =)
inf {Nnis (Hn,en -w² + Nn,ilpnn u/(l - - 1/Nn, + - s)3 wER
inf y22/(1-e)
{Nris, (Uno, x)² + Na.(Un,i y)²
Let i" = (H).. Using the stopping rule (34) and the above manipulations, we obtain
Pv mmn +00, byg & I ITmul(()) (1))
S P. (3n E N. Ii & Tamul
(Hm),
min
inf kift (1=)(
(Nn (Mrir - x)2 Nn.(uni 4) 2 2c(n -,,0)
< P. (3n E N, Di $ Ie (4), i == (Hn),
Nu (Mn,i - 14)22 + Nu
(Ha,s )1:))² c(n c(n=
2
2
Nas
Nu.i (Ma,r 11:0)2 c(n c 1,6))
Σ
Pe 3n EN
(pm. 11) 2
2
TgT (1)
where the second inequality obtained with (k, x, 4) = (i* P pG-) since i & (mmul(p). and the third by union bound. Then, can conclude as in Appendix G.I that
Po
mml Te.
+00, 2.
T.mmll( (w)) 58.
Asymptotic expected sample complexity While Theorem 8 holds for all sub-Gaussian distri- butions, it is particularly interesting for Gaussian ones, in light of Lemma I. It shows that, for multiplicative e-BAI, EB-TCM, is asymptotically optimal for Gaussian bandits when using IDS proportions and asymptotically (8optimal when using fixed proportions B.
Theorem 8. Let Eo E (0. 1). 3 E (0, 1) and E (0, Using the threshold (4) in the stopping rule (34) with error/confidence (Eo, 8), the EB-TCH algorithm (Eo, PPC and it satisfies that, for all D such that l (n) 1
Ey (ea. < Tmmul (n) and [fixed 3] log (1/)
Eg (To.6])
[DS]]
simsup 6-10
lim sup 8-30
I Tmmal (1)
log (1/8)
54

---

1.3 Proof of Theorem 8
The proof is very similar to the one of Theorem hence we will only highlight key differences. We defer the reader to Appendix D for detailed discussion the proof method and intuition on the different steps of the proof, see also [36, 21, 40].
In the following, we consider a slack eo for EB-TC which matches the error e considered by the G stopping rule (34), i.c. Eo For conciseness, we denote w" wind and w uul.
Let 0. Let define the convergence times Teary and Te,, as in (10) and (14), L..
Nn.
wi
Too == inf
T
Vn
T, max 1p1
7
Na
{
N
1
Tea,d,y inf T T vA 2T,
w S 5
Lemma 54 gives sufficient condition for asymptotic optimality and asymptotic /-optimality. The proof is the same as for Lemmas 13 and 25, hence we omit it.
Lemma 54. Let E 10. and 5 E (). Assume that there exists 7 (1z > O such that for all Y E (0, ' (n)), [Tool +oo. Using the threshold (4) in the stopping rule (3) with error Eo yields an algorithm such that, for all E DDK such that li* (p)) =1,
lim sup Ey
5-+0
log (1/6)
Assume that there exists 7/1 (1) > such that for all y E (0, 72 (H)), Ey (Ta.3... < +o0. Using the threshold (4) in the stopping rule (3) with error Eo yields an algorithm such that, for all D
such that j (p)]
Eyl [Eo.s)
lim sup 6-0 log (1/5)
L3.1 Sufficient exploration
Lemma 55 shows that the transportation cost is strictly positive and increases linearly, it bares similarity with Lemma 14.
Lemma 55, Let Sh and In as in (11). There exists Lo with [T,(([a))]] < too for all a > 0 such
that if L 2 Lo, for all n such that Sh + V., for all (i, E Iy x 5% such that i + j. we have
Pn.
pn
VLD,,
V/Na,, + (1 ea)² NNn.
where D2 > 0 is problem dependent constant.
Proof. Using Lemma 12 and min (Nn,s, Nu. 2 L, we obtain
(Vlogle
log(e Nn.))
llg(l + Nn.) Nns
Pn, - (1 - Eo)Mnss 2 14 24-(1 -1-00) - Wn
+ +1 (10-
Nn.s
2 En min μ4 - Eo) (o log(e + L) KE[K]
L 80 min 12/2, KE(K)
where the last inequality is obtained for L Lo L which is defined
4(2 - 2 W
4(2 - cn) 2
L sup x
2 min m log(x) +e hi
c min m2?
The last inequality is obtained by using Lemma 51, and we recall that h is defined in Lemma 51. Since h1 (x, e) ~x-4400 x log x, we have (Lo)( < too for all a > by using Lemma 12 (polynomial in W,,). Then, we have
Un.i (1 en)
En min 14/2
milliei]] ii
VI
I/No,i + +(1 //)
VI/N + 1-50)//N
2 2
5
55

---

Setting D,. Eo min IN yields the result.
2 (1-eo)
Lemma 56 gives an upper bound on the transportation costs between sampled enough arm and an under-samples one bares similarity with Lemma 15.
Lemma 56. Let Sh as in (11). There exists L1 with [,[(L,) < too for all a > O such that for all L Li and all N.
Mnii (1-
VL 1- (D1 + wW);
vi,s) E S x Sh,
VI/Nn, + (1- Eo)
where Dj > 0 a problem dependent constant and W, y. is the random variables defined in Lemma 12.
Proof. Using Lemma 12 and Nn,² 2 122 Nas= 2 1, we obtain
Mn,i (1 Eo)]un.
vNi /No.j
<
Mn,t - (1 -Eo))mn..
1/Nn,i (600))//NN.
1 - Eo
VL
114-(1 - -60))ug W
log(e + Nn.))
+11 +11-
log(e + Nn.)) Nn.
1 1-60 Eo
Nn,
$ 1
VL
(I4- - -60)ps) + - (2-Eo) Tog(e+1))
5 1 ED
VL
(Di + 4W,),
for D1 = maxişi 1 - - s
Lemma 57 show that the desired property for the TC challenger, we omit the proof since is the same as for Lemma 17.
Lemma 57. There exists L1 with E,, [La] < too such that if 2 for all n (at most polynomial in L) such that U.! * 0, TTth & V implies C TC, E V.
Combining Lemma 16 and Lemma 57 yields Lemma 58. Importantly, Lemma 58 holds for the EB-TC,, algorithm with fixed proportions 3 (0, 1) and IDS proportions. Since the proof the same as for Lemmas 18 and 26, we omit it.
Lemma 58. There exist N₁ with [N[N]] too such that for all Nn, 2 Vn/K and B i².
Ni and all i [K].
I.3.2 Empirical overall balance
As in [40], the key to obtain asymptotic optimality is to show that the empirical proportion satisfy the empirical overall balance equation. Compared to them, the novelty of Lemma 59 is that we use IDS proportions with K(K 1) tracking procedures select between the leader and the challenger instead of sampling. The proof of Lemma 59 is highly similar to the one of Lemma 19.
Lemma 59. Let 7 > 0. There exists N2 with E, [N2]] < +o0 such that for all 2 N2
N Nn
Nusi
Nu.
Σ
ST
n 1
1 Eo
Proof. Let N₁ as in Lemma 58. We proceed as in Lemma 19. Let us define
n-1
n-1
Gn
Σ B0..)))
Σ jz
(C. = () -
E0
t=
Direct manipulations yield that
} GG =n)==B(B
= B,, (T*,,C C..) Σ
3,(1,,C,
1 1- L-B Cn)
Σ
(1-
(1 EO)
N=
N=
1
+ 3,",," 2
(1 -ix 22
(1 E0)
56

---

Using that B C,), =1- C.))NN,.c./l - -Eu)² since (i",", C.) = Nn.c./((1
80)² a + C,, and the inequalities proven in Lemma 19, we can exhibit deterministic constants
B, B. > 0 (depending on K and En) such that
|G,+1 G. I AN1 + B hence |G.| S (n - 1 - NiN + B) + (1 (0)=
where the second inequality is obtained by telescopic sum (as in Lemma 19) and using that GN1+1 = 3N, (i", CN (1 3x, (i", CN, C)2)) 2) so)
As in Lemma 19, it is possible to exhibit deterministic constants C, > (depending on K and En)
such that
No
Σ
No
Gn
CN1 +D
1
En
(n 1)2
$
Combining both results, we can show
N
2
Σ
Eo (1=
Nus
2 )
(A+C) + B B+B D
E0)
n2
n
(n 1)2
Therefore, we have shown the desired result for n 2 N2 defined as
N₂ = inf n > 21 (A+ N1 + B D
60)
S 5 + (n- 1)2
n n-
which satisfies E, [2. < +oo since it is a linear function of N1.
As in [40], using Lemma 59 allows to bound the empirical proportion allocated to the unique best arm Nn.- 1) away from (Lemma 60).
Lemma 60. There exists N₂ with [N[ < +oo such that for all n 2 N3
Nn S n-1
(1 - s0)2/2+1 +1
1 1 CU
S cC where cu
and
(1 Eu) 2 +1
(1-E0) ( 2(( 1)
-
Proof. Let N2 in Lemma 59 for (I-co)t.
Using Lemma 59, we obtain for all N2
N Nn
Nn 2
Nn
2
Nn 2
7 2 - (1=
Σ
2 (1 - (0))
-
-
n2 nー
n
Nn.i
2
Nn.
= ((1 - 60) -1)
+ 2
n2
N Nn
2
2 ((1- - =0)2 + 1)
-.
71
where we used that Na. x-1
1. Taking 7 (1 50)?/2 /2 yields the upper bound.
7 1)(1 Using Lemma 59, we obtain for all n 2 max N2, max(NN, No) Let Nr as in Lemma 59 for (K- (
Nn.i 1
Nn.i
- (K - 1)(1 =00
(K (K-11
n1
N Nu
Nn.
2
S(K 1)(1 =20)2
1
n
n
Nn, 1
(K - 1)(1 =
2²
Taking 7 = -1-ow) 22 /2 yields the lower bound. Note that
1 1 (1 )2 // +1
- 2 +1 (2(K 1)(1 - )1) 2 -1)( - Eu) + +1).
CL S CU
where the last condition is trivially true. Taking N3- max(NV2,Nee) yields the result.
57

---

Lemma 61 is rescaled version of the empirical overall balance equation which is proven by simply combining Lemma 59 and Lemma 60. Lemma 61. Let 7 > 0. There exists N4 with Egy [Na] < +00 such that for all n 2 No
2
Nu.i Nn,5
(1 =0)=
S7.
Proof. Let N3 and er, as in Lemma 60. Let N2 as in Lemma 59 for 7ct/(1 - so)?. manipulation shows that, for all n 2 Ni max (2, Ns).
Direct
Nu. Eo Nn.
n
N n.i-
1- iF
Nu.-
1 Eo
7
(1 ED)
L
This concludes the result.
I.3.3 Convergence towards optimal allocation
As in [40], show that challenger will not be sampled next when the ratio of its empirical propor- tion compared to the one of i* overshoots the ratio of the optimal allocations (Lemma 62).
Lemma 62. Let y > O. There exists No with [Ns]] < too such that for all No and all i + it,
Nu.i
w
+
On
IC
ti.
No.5*
w
Proof. yetr>> 0. Let i # i such that
No.i
w
+ 7
No.5
wxt-
Let N4 in Lemma 61. As in Lemma 22, we show for all 2 Na
Noj.
s w
Fj & ()
No w
TCP
Let N1 in Lemma 18. Using that E for all n 2 N1 and the definition of Cn we known that
Pn, (1- Eo)
Pn.s* (11--p0 Eu)
IC Gn
* i.
V V//N, (1- -0)
VI/Na.5. (1-e6) /o)
To conclude the proof, sufficient to show that the ratio of the two quantities is strictly larger than one. For all n 2 max ( (N1, N4), we obtain
Pn,i - (1 80)
1+ (1 2011-6)22 2n
ni /N 60)2
Mn,s (1 Ea) Mn)
1+ (1 - 02 22,, n,,5 NNns
Mn,i (1 - so)Hmm.
(1 11--0) E0) /W
Mn (1 - Eo)
1 + (1 - =0)2 (w, / /w:. + 7)
Let 5 > O. Using Lemmas 12 and 18, we have, for all n 2 N2 and all k + it,
Wp (11 (11-0) -0) / Jogle+N + V N...
log(e=N No..1 No.e
Pn,it - (1 Eo)Hkn,
<
p4. (1 - -E0)
Mi. -EO)pu
(2 W.
log(e + /n/K) Vn/K
57
mingge (144 - (1 - -
58

---

alr n 1226 No ((x - -c)² + which is defined as
(2-Eo)
No = sup
x 2 1 x <
log x +
22 min (14-
=u)puR?
(2 Eo) W
< h1
7/2 min (M
=o))
where the last inequality is obtained by using Lemma 51 with hn defined therein. Since hi (I., y) Nx-tox x logx, x; have [N6] < +00 since it polynomial in W (by using Lemma 12).
Let x >> O. We have shown that, for all n 2 [Nx Noh.
pn (1 - Eom
1 + (1 2 2 /Nn.j
Un, (1 =n)
1+ (1 ED)² Nn /N
Mir (1 E0)
1 (1- 200 /wj 1-
M4. (1 Eu)Hu
+ - (1-20) (w / + 7) +
1 + (1 50) 2u. /wt
1 -
(1 s0)² (w, /w: + +7)
where the equality uses that the transportation costs are equal at the equilibrium, i.c. (31). Taking ? small enough, we have that shown that, for all max Na, No).
Nn. Nn
W. w
Pn.s" - (1 8o)lkni
+ (1 2o)2Nn, /Nn.s >> 1,
2
Pn,i (1 Su)lins
1+ (1 20 /Nu,i
hence On + i. This concludes the proof.
Lemma 63 is obtained with the same proof Lemma 23.
Lemma 63. Letry > 0. There exists No with [No] < too such that for all n 2 Ng and all + i*
No.i Nn,5*
I w
+7.
w
Lemma 64 is obtained with the same proof as Lemma 24.
Lemma 64. Let Eo (0, 1), y > and Teory introduced before (adaptation of(1)). Under the EB-TCM, 5o sampling rule with IDS proportions, we have [Te..n] < +00.
Combining Lemmas 54 and 64 yields the first of Theorem 8.
L3.4 Convergence towards 3-optimal allocation Combining Lemmas 58 and 27 with the proof of Lemma F.9 in [20] yields Lemma 65.
Lemma 65. Let 7 > 0. There exists Nş with [Ns] < +oo such that for all Ns and all + i*,
Nn.s
TC +
3g. +
Lemma 66 is obtained with the same proof Lemmas 29 and 30.
Lemma 66. Let Eo E (0,1), 3 (0, 1), 7 > and and Teo.9.7 introduced before (adaptation of (14)).
Under the EB-TC" sampling rule with fixed proportions
have E, (Te, < +00.
Combining Lemmas 54 and 66 yields the second part of Theorem 8.
J Implementation details and additional experiments
After presenting the implementations details Appendix J.1, we display supplementary experiments in Appendix J.2.
59

---

J.1 Implementation details
Top Two sampling rules Given a fixed B, most Top Two algorithms use randomization to select In E {B,, }. namely they sample B, with probability B, otherwise sample Cn. Instead of randomization, TTUCB [20] uses K tracking procedures to select I E (n, Namely, they choose I = B, if N a.B. I 8E B., Ta+1 (,,,)) i), and I, = C, otherwise. In comparison, EB-TC relies on K(K 1) tracking procedures both for fixed proportion 8 and IDS proportions [40]. In [40], they consider IDS proportions to define 3n adaptively. For Gaussian with known homoscedastic variance, their update mechanism is
BR, dxL (Nn,Ba, Bn, Un BBy Cn))
Nn,C. Nn. + Nn.C..
Bn Nn, der, (Mo, P.,, un (Bn, Cv)) + Nn,C, dki (,n,Ca, Un (Bn, C.)) where the second equality is obtained by direct computations which uses that
Un (1. inf (Mm,, 27) + Nu.gdkk (Mm, Nn.lnn + Nn.Hlnnj.. =ER
Nu. + NNng
[8] proposed a new methodology called Balancing Optimal Large Deviations (BOLD) select In E {B,, Cn adaptively. While their approach aims at minimizing the probability of incorrect selection (i.e. fixed-budget setting), it is possible to adapt their idea to minimize the expected sample complexity (i.e. fixed-confidence setting) by "swapping" the arguments of the KI. divergence. Namely, the BOLD procedure can be rewritten in our setting as selecting I, B,
dkL, un Bnn i)) dKL(Hnn Un (B,, i)) 1,
Σ es Bn
and In = Cn otherwise, For Gaussian with known homoscedastic variance, their approach recovers the heuristic "adaptive Welch divergence" algorithm of proposed in [37], i.c. L, B, if N², < E, N2. and I, = Cn otherwise. The analysis [8] is focused on asymptotic guarantees in probability. is an interesting direction for future research to show that the BOLD procedure also yields asymptotically optimal algorithms.
TTTS [34] uses TS (Thompson Sampling) leader and a RS (Re-Sampling) challenger based on sam- pler IT,, For Gaussian bandits, the sampler II, is the posterior distribution X W(nn, i/,,,)) given the improper prior T = (N(00++00)) + The TS leader is BTS E arg [|K] 0g where 0~ ~ 1l. The RS challenger samples vector of realizations 0 E II, until B,, & arg max 0;, then is defined CRS arg ma 0g for this specific vector of realization. When the posterior II and the leader B,, have almost converged towards the Dirac distribution on μ and the best arm i (u) respectively, the event Bn & arg māx 0; becomes very rare. The experiments in [21] reveals that computing the RS challenger can require more than millions re-sampling steps. Therefore, the RS challenger can become computationally intractable even for Gaussian distribution where sampling from II, can be done more efficiently.
T3C [36] combines the TS leader and the TC challenger. EB-TCI [21] combines the EB leader with the TCI challenger defined as
(Mn.R, Hm,i) + log((N,,)) C arg min 1 (Hn,B, (n,)) 2(I/Nn.B, + 1/N,,i) BB
TTUCB [20] combined the TC challenger with UCB leader which is defined as
B ICB
arg max + / (o(n//N..). =E[K]
where vg(n)/Nn. is a bonus coping for uncertainty. TS-KKT [40] uses the TS leader and a challenger based transportation costs with different penalization than the used in [21], namely
(Un.B, un,;)² L log (1/No, + +1/Nna)
C₂) E Erg min B, 2(1/Nn,,B. + 1/N,.)) n
where / a parameter that needs to selected beforehand. The authors highlight that the choice of has important impact the empirical performance.
60

---

While the above Top Two algorithms are BAI algorithms, we can adapt them straightforwardly to tackle the E-BAI setting by (I) using the stopping rule as in (3) and (2) using transportation costs for e-BAI, i.e. the ones in (2). The modification (1) is inspired by [19] and the modification (2) by [22]. As an example, the modified TCI challenger can be written as
C = arg min 1 B, (o.s) B,n.B, Un, + t)2 BrB
log((Nn.))
2(1/Nn.B. + 1/Nn,))
Fixed-confidence BAI algorithms At each time n, Track-and-Stop (TaS) [15] computes the optimal allocation for the current empirical mean, W/, = w² (H))). Given wn, E Ax. it uses a tracking procedure to obtain an arm l, to sample. On top of this tracking forced exploration is used to enforce convergence towards the optimal allocation for the true unknown parameters. The optimization problem defining w*(w) can be rewritten solving an equation (r) where
Vr E (1/ min(u-- ps)² +00), wu(() 121
E iF1 (r(ws- n.) 1)²
The function t/e is decreasing, and satisfies limp-+00 (1)
-1 and limy-+1/ yi (H,. -m, (v) = +o0. For the practical implementation of the optimal al- location, we use the approach of [15] and perform binary searches to compute the unique solution of (r) = 0. A faster implementation based on Newton's iterates was proposed by [3] after proving that 2/ is convex. While this improvement holds only for Gaussian distributions, the binary searches can be used for more general distributions. Similarly, one can adapt TaS to tackle e- e-BAI as done in [16], i.c. by tracking W we (Pn). Using Lemma 9, it is direct to see that one use the same implementation to compute it efficiently.
min-max game between the learner and the nature, and design saddle- point algorithms to solve it sequentially. At each time n, learner outputs an allocation Wn, which used by the nature to compute the worst alternative mean parameter A, Then, the learner is updated based on optimistic gains based on A, Similarly, one can adapt DKM to tackle s-BAI by using a modified alternative mean parameter. This coincides with the L=BAI algorithm [19] when used on unstructured multi-armed bandits.
DKM [11] view T ((4)-1
FWS [39] alternates between forced exploration and Frank Wolfe (FW) updates. Similarly, FWS can be adapted tackle B-BAI
LUCB [24] samples and stops based on upper/lower confidence indices for a bonus function g. For Gaussian distributions, it rewrites for all E [K] as
2c(n 1, 8)
2c(n 1,6)
Un,1 = pn,s +
and Ln,i = Mn,s
Nn.
Nn.
At each time n, it samples in and arg ma Un... For E-BAI, LUCB stops when Ln,i, + E max Un
Fixed-budget BAI algorithms We consider Successive Reject (SR) [1] and Sequential Halving (SH) [25]. SR eliminates one arm with the worst empirical mean at the end of each phase, and SH eliminated half of them but drops past observations between each phase. Within each phase, both algorithms use a round-robin uniform sampling rule on the remaining active arms. to convert the fixed- budget SH algorithm into anytime algorithm by using the doubling trick. It considers a sequences of algorithms that are run with increasing budgets (Tk)k21. with T&+1 = 27, and Ti 2K [lgg, KJ,, 1, and recommend the answer outputted by the last instance that has finished to run. It is well know that the "cost" of doubling is to have a multiplicative factor 4 in front of the hardness constant, The first two-factor is due to the fact that forget half the observations. The second two-factor is due to the fact that we use the recommendation from the last instance of SH that has finished. The doubling version of SR and SH are named Doubling SR (DSR) and Doubling SH (DSH).
possible
Reproducibility Our code implemented Julia la 1.9. 1.9.0. O, and the plots are generated with the StatsPl ots.............. ji package. Other dependencies are listed in the Rea dme.. .md. The Readme. mdd file also provides detailed julia instructions to reproduce our experiments, as well as scri script.. sh to run them all at once. The general structure of the code (and some functions) is taken from the
61

---

tidnabbil library. This library was created by [11], see https:://ittbueeee .ww.eeeetttttrooooooooo werg//mkooeenn tidnabbil. 1. No license were available on the repository, but we obtained the authorization from the authors. Our experiments are conducted on an institutional cluster with 4 Intel Xeon Gold 5218R CPU with 20 cores per CPU and x86_ 64 architecture.
J.2 Supplementary experiments
For the sake of space, only presented a small subset of our experiments in Section 5, hence provide additional empirical evidence below. In Appendix J.2.1, we assess the impact of the choice of the slack Eu the empirical performance of EB-TCeo with IDS with fixed proportion 3 1/2. Appendix J.2.2 complements Section by providing more comparison between EB-TCe, and existing algorithms. In Appendix J.2.3, study the BAI problem and show the empirical performance of the (B-TC Jas with fixed proportion 3 = 1/2 and using varying slack parameters (En)n (as described in Sections 3 and 4). As in Section 5, consider d 0.01 and use the heuristic threshold c(n, 5) = log((1 + log /6), which yields an empirical error which is several orders of magnitude lower than 8.
J.2.1 Numerical simulations on EB-TC
Appendix J.2.1 is meant to be sensitivity analysis of the EB-TCc, algorithm. It will allow to numerically substantiate our recommendation to the practitioner on how to set the slack ep, and why using IDS yields better empirical performance. For slacks 6o E {0.15, 0.1, 0.05J, we will consider the EB-TC,, algorithms with IDS proportions and fixed proportions 3 = 1/2.
C-EB-TC
C-LB-TCH
C-EB-TCUA
10a
EB-RC
EB TC
F.
EB-TGE
10
10a
10
10
10
K
CEBTC.. CEB-C
C-EB-TC
C-EB-TC
CEB
C-EB-TCUu
EB-T
EB-TCom
10
TC
EB
EB-TGg
10
EB-TO
E.
10a
10a
10
10 number of arms K
10a
10a
10
K
Figure 4: Empirical stopping time with stopping rule (3) using (c, (0.1.0.01) on (a)" "sparse" instances", (b) 0.3" instances and (c) "a 0.6" instances. "c-" denotes fixed | 1/2, without refers to IDS.
Large sets of arms First, we evaluate the impact of larger number arms (up to K = 1000). The "a = 0.6" scenario of [18] sets μ4 = 1- (((i-1)) (1)(((1))/(K - 1))) for all E [K]. The "sparse" scenario [18] sets μn = 1/4 and μæ- = 0 otherwise. We average on 100 runs, and the standard deviations displayed.
In Figure 4, we see that all instances of EB-TC,, with IDs or fixed B 1/2 have the same scaling with the dimension K. Figure 4 also reveals that using IDS instead of fixed 3 = 1/2 consistently yields smaller empirical stopping time. Therefore, IDS should preferred to choosing fixed 3 = 1/2. Finally, Figure 4 shows that better empirical performance are obtained when using slack eo which matches the error e, i.e. choosing &g to tackle e-BAI. While choosing En > E only slightly damage the empirical performance, taking Eo is clearly detrimental to the empirical performance.
62

---

characteristic times Te(u) and Te.1/2 2 50x100
1.50x10
20x10d
50x10
1.00x10*
00x10
5.00x 10'
5.00x10
4 0x100
2.50x10"
3,0x10
2.00x10'
1.50x10
2.0x10
1.00x10*
1.0k10'
5.00x10
25 7a
89 NCu
188 Ra
86
cestcu
4 4.0x10''
6.0x10'
3.0x10
4.0x10*
2.0x10
2x010
10x10
17am
Figure 5: Empirical stopping time random instances with stopping rule (3) using (left) (e (0.05, 0.01) and (right) () = (0.1, 0.01) with (top) K = 5, (middle) K 10 and (bottom)
K 20. "c-" denotes fixed 3 1/2,, without refers IDS.
Random instances We further investigate the phenomenon described above on random instances.
For {0.05, 0.1}, we assess the performance on 1000 random Gaussian instances with K =
(resp. 10 and K 10) such that μr 1, f4 4([1 E, 1]) for E (2) (resp.
{2.3)
and {2, 3, 4)) and μ4 4{(0, 1 E)) for i 2 3 (resp. 2 4 and i 2 6). hence Ig (p) [2]
(resp. I. (p) 3 and I (μ) (5)). We display the boxplots the empirical stopping time on 1000 runs.
In Figure 5, the tendencies glimpsed by inspecting Figure that better empirical performance are obtained when using slack 6o which matches the error e, i.e. choosing Eq to tackle eBAI We also see that the empirical gain taking so is increasing with the dimension K. Figure 5 shows that > E slightly damage the empirical performance: the larger the missmatch Eg is, the worse the performances are. Moreover, Figure highlights how choosing < is highly detrimental to the empirical performance. Finally, we see that there is mild advantage in using IDS over fixed
apparent. Figure shows
1/2. Note that the mild empirical gain of adaptive proportions is known phenomenon which was studied empirically in [20]. and larger gains can be observed for "two-groups" instances. Intuitively, are very close to each other on average, and the difference is the largest when all the sub-optimal arms have the same mean. Therefore, on average, using IDS has mild gain compared to using fixed 1/2. This worst-case scenario of the "two-groups" instances is studied in Figure 7,
63

---

Table 3: Specific instances from [16] with corresponding
Instance
ITe
Arms
1
2
3
6
0.1
A4
0.7
0.55
0.5
0.4
0.2
0.15
P2
0.8
0.75
0.7
0.6
0.5
0.4
0.1
0.6
0.6
0.55
0.45
0.3
0.2
Specific instances We continue the experimental validation of our the phenomenon described above by considering the three specific instances from the experimental section of [16] which are described in Table 3. Instance μı3 corresponds the specific instances studied in Section 5. particularly interesting since it has two best arms, third E-good arm which is equally distant from e than the bad arm with largest mean, and has additional bad arms, Instance #2 has also three E-good arms, which are equally spaced, and three bad arms. Instance μl has only one e-good arm, and four bad arms. We display the boxplots of the empirical stopping time on 1000 runs, and the empirical simple regret on 10000 runs (with associated standard deviation).
1.20x10'
EB-TC
0.20
1.00x10*
TC
BB-TCL
8.00x10
0.15
TC
6.00x10
Eulp*
0.10
4.00x10
0.05
2.00x10
100
200
300
400
500
T1
1.50x10'
0.175
CED TCu
FB-TC
0.150
C-EB-TCuuo EB-TC.u
0.125
1.00x10*
0.100
0.075
0000100
0.050
0.025
0
250
500
750
1000
16
0.15
C-EB-TC,,
2.00x10 10
C-BB-TC,.
E34T
1.50x10"
0.10
E3 TGgs
E.lu**
100010
0.05
5.00x10
0.00
500
1000
1500
2000
Figure (Left) Empirical stopping time for the stopping rule (3) using 8 0.01 and (right) empirical simple regret on instances (top) yy with 0.1, (middle) μ22 with = 0.15 and (bottom) μa with E 0.1. "c-" denotes fixed [ 1/2, without refers to IDS.
The left column of Figure confirms our previous observations: taking 6 = En yields the best perfor- mance, taking Eo slightly damage performance and taking < hhghly damage performance.
64

---

Figure 6(middle left) shows that the the larger the missmatch Eo is, the worse the performances are.
The right column of Figure 6 reveals that the choice of has few impact on the empirical simple regret, at least for reasonably chosen Eo. Likewise, there is few differences between IDS proportions and fixed B 1/2. The good empirical performance of IDS proportions regards the simple regret hints that EB-TC with IDS has (most likely) similar theoretical guarantees as the ones obtained in Section 4 for EB-TC2, with fixed 3 1/2 (Theorem 3 and Corollary 1). This is interesting open problem that we leave for future work.
Two-groups instances We conclude our sensitivity analysis on EB-TC,, by considering the "two- groups" instances μ {0.6, 0.4) for varying number of best arms, i.e. J (n)] [8]. Our aim is to assess the impact of having multiple best arms on the empirical stopping time. We average on 1000 runs, and the standard deviations displayed.
C-EB-TCum
C-EB-TC
3.0x10
C-EB-TCRu
EB TGus
FB-TCa1
EB-TCros
E T
2.0x10
1.0x10
0
2
6
8
1 (a((
Figure Empirical stopping time with stopping rule (3) using (s, = (0.1, 0.01) on instances {0.6, 0.4] for varying ji* (1)). "c-" denotes fixed = 1/2, without refers to IDS.
On this specific instances where the number of arms is fixed, would be intuitive to think that the problem is easier when there are more best arms. However, this is actually the opposite since there less bad arms (which were easy to detect) and more good arms which need to be estimated well when taking ED
enough. While Figure 7 shows how poor the performances the impact having multiple best arms rather mild for slacks Eu 2 E. We will see in Figure 12 that EB EB-TC,, is the most resilient algorithm with respect to multiple arms, meaning that its slope is the smallest.
also shows that
"Two-groups" instances are interesting since they are the instances for which the ratio (2))/2(1)/ (n) is the largest. Using Lemma 9 and the theoretical results of [20] (see their Lemma C.6), we conjecture that (1) < Tx (f) with тк = 2K/(1 + VK - 1)² and that the equality occurs for "two- groups" instances. Since 710 5/4, using fixed 3 = 1/2 should be roughly 25% slower than using IDS. While Figure confirms that using IDS yields better empirical performance than using fixed 3 = 1/2, the empirical ratio between their performance is lower than the one suggested by the theory.
Table 4: Comparison between the original sampling rule and the modified sampling rule for BAI algorithms when combined with the GLR, stopping rule (3) using (e, 8) (0.1, 0.01). We display the empirical stopping time (and standard deviation) on random instances with K E (5, 10, 20}.
K
T3C
E-T3C
EB-TCI
E-EB-TCI
5
9138 (+7988)
2259 (#:2443
22505 (+66624)
2290 (+120
10
17418 (+9726)
3793 (+1524)
58086 (+135555)
3975 (=1509)
20
30771 (+13038)
6631 (199
115861 (+195797)
6905 (=1879)
65

---

J.2.2 Comparison with modified BAI algorithms
Appendix J.2.2 is meant provide further empirical evidence that EB-TCe, outperforms its petitors on different tasks and for different types of instances. Overall, we will use the same instances used in Appendix J.2.1 since they provide wide range of interesting problems. Throughout this section, we will be using EB-TCr, with slack 6 0.1. While IDS proportions are used for the exper- iments the empirical stopping time, fixed 1/2 for the empirical simple regret.
10
TBC
T3C
10
10
Uniform
B.lTcd
E.(T
10a
10
10
10
10
10
10
10
10
Figure 8: Empirical stopping time (a) "a 0.6" instances and (b) "sparse" instances for varying
K and stopping rule (3) using (e, 6) = (0.1,0.00 0.01). The BAI algorithms T3C, EB-TCI and TTÜCE modified to be e-BAl ones.
5.0x1c
1.20x10'
4.0w10
1.00100*
3.0x10
8 8.00x10
6 6.00x10²
2.0x10
4 400010
1x10d
20x00
HEICE JB8 wiNes
<02
-OON
00x10
2.50x10
2 2.00x10
7.50x10'
1.50x10'
3.00x10'
2.50x10
3000200
<T6
68
-00
-99
DON
LUCK UNWWY
2.00x10
5,0x10
4,0x10
1.50x
3.0x10f
1.00x10
2.0x10
60x10
10x10
137C
+126
488 0..1 1008 -00
.008 LSE8
Uxfere
-120 400
10.20 0100
Figure 9: Empirical stopping time random instances with stopping rule (3) using (left) (e, 8) (0.05, 0.01) and (right) (s, 8) = (0.1, 0.01) with (top) K 5. (middle) K = 10 and (bottom) K 20. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS. DKM are modified for e-BA..
66

---

As benchmarks we consider modified BAI which are tailored to tackle e- e-BAI, and we combine them with the GLR, stopping rule. One can still wonder whether the unmodified sampling rule would perform well for e-BAI when combined with the GI.,, stopping rule. While we could hope that modifying the stopping rule enough, our experiments reveal that not the case. If don't 't adapt the sampling rule as well, Table shows that the empirical stopping time can be more than ten times larger than their modified version.
Large sets of arms To complement Figure 2(a), we consider the "a 0.6" instances and "sparse" instances for varying K. We average on 100 runs, and the standard deviations are displayed.
Figure confirms the observations made in Figure 2(a). We see that EB-TC, performs on par with the e-T3C, and outperforms the other algorithms. It also highlights that the regularization ensured by the TC= challenger is sufficient to ensure enough exploration. As consequence, other exploration mechanism are superfluous when using Top Two algorithms for e-BAI (e.g. using TS/UCB leader or TCI challenger).
Random instances For E E {0.05, 0.13. we assess the performance on 1000 random Gaussian instances with K E (5, 10, 20) as described above. We display the boxplots of the empirical stopping time on 1000 runs.
Figure 9 confirms that EB-TC,, performs on par with the state-of-the-at BAB algorithms and greatly outperform e- D-KM, LUCB and uniform sampling. Interestingly, for larger sets of arms (K = 20), EB-TC appears to be more robust than its competitors, closely followed by e-T3C and EEBB-TCI. The performance e-TTUCB, e-TaS and c-FWS is slighlty worse, while the cDDKM is greatly impacted. LUCB seems relatively robust to larger sets of arms, but it is still significantly worse than EB-TC It is even the best when considering slack eo in the bottom row of Figure 9. The slightly worse (but still competitive) empirical performance of EB-TC,,. in the top row of Figure considered in the GLR, stopping rule.
of
explained by the slack Eo 0.1 which differs from the error 0.05
Specific instances To complement Figure 2(b), we consider the two other instances from Table 3. We display the boxplots of the empirical stopping time 1000 runs, and the empirical simple regret on 10000 runs (with associated standard deviation).
The left column of Figure 10 validates the previous conclusions as regards the good empirical
performance of EB-TC;, compare to existing s- s-BAI algorithmss We also see that it seems to perform even better when there are multiple e-good arms and multiple best arms, i.e. (x)] > 1. The right column of Figure 10 corroborates the observations made in Figure 2(b): EB-TC2, outperforms uniform sampling, as well as DSR and DSH.
Two groups We consider the "two-groups" instances μ E (0.6, 0.4) for varying number of best arms, i.e. (i*(()) E [8]. We average 1000 runs, and the standard deviations are displayed.
Figure/ 11 reveals that EB-TC., is the most robust to increased number of best arms, i.c. its slope is the smallest. The good performance of EB-TC is closely followed by other Top Two algorithms. This confirms that additional regularization mechanisms (e.g. TS/UCB leader or TCI challenger) are superfluous since the TC= challenger enough to ensure sufficient exploration. e- e-TaS and FWFWS have slightly worse slope, and the one of DDDM seems to become less steep after large initial increase. The highest slope achieved by LUCB. Quite surprisingly, uniform sampling seems to reach a plateau after which it is scaling better than EB-TCo, (in terms of slope), while still having worse empirical performance. would be interesting to quantify theoretically the good scaling of EB-TCco with respect to increased number of best arms.
67

---

EB-TC,
0.20
1000
Uniiform
0.15
4000
B
E,laa
0.10
0.05
100
200
300
400
500
GBTC.
0.175
6B-TC,
0.150
DSH
6000
Unniform
0.125
4000
0.100
0.075
2000
0.050
0.025
250
500
750
1000
.000 .muDE
.005
Uniom
0.15
1.50x10
1:00
DSR DSH Uniffrmm
0.10
1,00x10'
F.ll*
0.05
5.00x10'
0.00
2PCC -E3-TE1-7TLC
085
.015 0309
L0C3 Un born
Figure 10: (Left) Empirical stopping time for the stopping rule (3) using g 0.01 and (right) empirical simple regret on instances (top) ja with & = 0.1, (middle) with s = 0.15 and (bottom) μ4 with & 0.1. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM modified to be E- --BAI ones.
EB-TC,
2.50x10*
+T3C
-EB-TCII
-TTUCB
2.00x10
=TaS
E &.
s-FWS
5-DKM
1.50x104
LUCB
Uniform
1.00x104
5.00x10
(()(
Figure 11: Empirical stopping time with stopping rule (3) using (s, 8) = (0.1,0.01 on instances
I E [0.6, 0.4) for varying (7* (n)) The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are modified to be c-BAl ones.
68

---

EB-TC,
EB-TC,
0.16
DSR
0.15
-Uniform
Uniffrr
0.14
00.12
0.12
0.09
E.ja
0.10
E.aa
0.06
0.08
0.06
0.03
250
500
750
100C
250
500
750
1000
7
EB-TC,
0.12
EB-TC,
0.125
DSR
DSH
0.10
DSH Uniffor
-Uniform
0.100
0.08
0.075
0.06
E.lae
E.Ip
0.04
0.025
0.02
0.00
250
500
750
100C
250
500
750
1000
0,100
TB
TC,
DSR
0.08
DSR
DSH
DSH Unifarm
UUniform
0.075
0.06
E,
0.050
E.ln*
0.04
0.025
0.02
0.000
0.00
250
1000
Figure 12:
Empirical simple regret on instances μ (0.6, for (xa) E [6]. i.e. (top left) j (a)) and (bottom right) 1 [n)] = 6.
Figure 12 provides additional empirical validation that EB-TC,,, outperforms uniform sampling as well as DSR and DSH in terms of empirical simple regret. While the empirical stopping time increased with the number of best arms, Figure 12 confirms the intuition that the problem gets easier with respect to the simple regret. First, the range of empirical simple regret becomes smaller with increased number of best arms. This was expected as we have more chances to recommend one the observe
best arms early stage even though this recommendation close to random. Second, steeper decrease of the empirical simple regret with increased number of best arms. Likewise, this is natural phenomenon since the collected data will reveal that there multiple good options very fast.
Quite surprisingly, EB- EB-TC,, is still better than DSH when the number of best arms increases. To understand why is surprising, we recall that the exponential decrease of DSH's probability of error is linear with rate proportional to hardness constant HDSH(P) By definition, HDSH(1) (1) gets small when there are multiple best arms, hence we would expect to observe lower empirical simple regret (i.e. "speed-up"".
contrast, our hardness constant H [ EO) K K22 + 3 ')2 does not enjoy such property. Therefore, we would expect that DSH will outperform EB-TC,, when the number of best arms increases. Theoretically proving that EB-TC... has better scaling than the one given in Theorem is still open problem. Solving it would allow to better understand its good empirical performance on this task.
Fixed-budgel performance In addition, we compare the performance of EB-TC with Ep and 3=12 1/2 to the one SR and SH. Since SR and SH are fixed-budget algorithms, we ran different instance for each budget T'. Therefore, this comparison gives unfair advantage to the fixed fixed-budget
69

---

algorithms which fully leverage the knowledge of T but have no theoretical guarantees at time n * T (even time T + 1). As result, the empirical performances of SR and SH are better than the ones of DSR and DSH. We consider the instances from Table 3, as well as "two-groups" instances.
0.12
FB-TC,
FB-IC
0.10
SH
0.6
SH Uniform
Uniform
0.08
3..5
0.06
0.04
0.2
0.02
0.1
0.00
500
1000 Budget T
1500
2000
500
1000 Budget T
1500
2000
0.14
0.8
SA Unilom
0.12
Uniform
0.7
0.10
0.08
0.6
0.06
0.02
0
250
500
750
1000
250
500
750
1000
Budget
Budget
0.20
TB
0.8
EB TC,
St
SH
0.15
-Unffrmm
0.6
Unioom
0.10
0.2
0.00
750
1000
750
1000
Budget T
Budget T
0.175
SR
SR Uniform
0.150
Uniffmm
0.8
0.125
0.6
E,la
0.100
0.075
0.4
0.050
0.2
250
500
750
1000
0
250
500
750
1000
Budget
Budget
0.8
ES-TC,
EU-IC,
0.12
5R
0.10
SH
1iyy [p]]
0.6
0.08
0.4
0.06
0.04
0.2
0.02
0.00
500
750
Budget T
Budget T
Figure 13: (Left) Empirical simple regret and (right) empirical error on instances (top to bottom) #3 (0.6, 0.6, 0.55, 0.45, 0.3, 0.2), μ2 (0.8, 0.75, 0.7, 0.6, 0.5, 0.4), µı (0.7, 0.55, 0.5, 0.4, 0.2) and E {0.6, 0.4] with (+)) E 31, Average over 200 runs. We ran different instance of SR and SH for each budget T.
70

---

Overall, according to Figure 13, EB-TC,, seems to perform on par with SR and SH in all instances considered, and outperform SH for some instances. In our experiments, we consider SH which the samples are dropped between each phase, as analyzed theoretically in [1]. This loss of information explains why SR has better empirical performance than SH. the best of our knowledge, there no theoretical analysis for the heuristic SH where all the samples are preserved, even though it has better empirical performance.
J.2.3 Varying slack parameter
In Appendix J.2.3, study the BAI problem. Those experiments have two goals: (1) sensitivity analysis of EB-TC(e.). described in Section 3 and (2) performance assessment of EB- BB-TCoo on BAI problems. We consider fixed proportions 5 = 1/2, and use En = 0.1 for EB-TC For the rate of decrease of (En) will be considering two archetypal choices: (a) polynomial by taking& e n n and (b) polylogarithmic by taking e log(n) -a/2, We compare empirically those two rates of decrease for different choices of a, namely a E {0.05, 0.1, 0.5). To tackle BAI, consider the GLR, stopping rule (3) with (c, (0, 0.01) and the heuristic threshold c(n,5) 5) log((1 (1 + log (0) Even though this choice is not sufficient to prove (0, 0)-PAC, it yields an empirical error which is several orders of magnitude lower than 8. As benchmark, use the unmodified BAI algorithms.
Random instances We assess the performance on 1000 random Gaussian instances with K {5, 10, 20} such that = and μ4 ~ u([0.5, 08)) for + 1. We display the boxplots of the empirical stopping time on 1000 runs.
2.00x10*
8000
1.50x10'
6000
0030
4000
1000x1
2000
5 5000100
3.50x10'
3.00x10
2.50x10'
2.00x10*
1.50x1d
1.00x10'
5.00x10
Figure 14: Empirical stopping time for the stopping rule (3) using (c,5) = (0, 00,0. on random
instances with (a) K = 5, (b) K = 10 and (c) K = 20. "T" denotes En = log(n) aa/2 "p" denotes En = n a/2 "a."" refers to a e {0.5, 0.1, 0.053.
The most stricking feature of Figure 14 is that it reveals how poor the performance of EB CB-TC(Ca)) can be for many choices of (s,).. For the considered a, we observe that polynomial decrease is always bad since yields roughly the same empirical performance as uniform sampling. This can be explained by the fact that this decrease is too fast, hence EB-TC will ressemble EB-TC, which know to have poor empirical performance [21]. For the considered a, we see that polylogarithmic decrease is often bad, except for 0.5. In that case, it performs par with TaS, slightly worse than standard Top Two algorithms for BAI and better than LUCB and uniform sampling. This can be explained by the fact that EB- EB-TC is similar to uniform sampling when the decrease is too slow. The above sensitivity analysis truly shows how difficult it is to choose (Ex),, beforchand. The
71

---

best "trade-off" between slow decrease (yet not too slow) highly depends on the complexity of the unknown instance. While EB- (B-TC reaches asymptotic optimality for BAI, we recommend the practitioner to use other Top Two algorithms which enjoy the same theoretical guarantees and better empirical performance. When one needs to have deterministic algorithms, EB-TCI seems be the best. Without the deterministic constraint, T3C has great performance.
In Figure 14, we also see that, when combined with the GLR, stopping rule, EB-TC;, has good empirical performance for BAI It outperforms EB-TC h. performs on par with TaS and is only slightly worse than standard Top Two algorithms for BAL. Experiments conducted in Appendix J.2.1 already provide experimentally confirmation that EB-TC, has still good empirical performance on e-BAl problems when Eo 2 E. Theoretically, Theorem provide some intuition on why this is true. It shows that the gap between the asymptotic lower bound To( and the asymptotic upper bound of EB-TCoo is bounded by
Te0.1/2(1) To(m)
1
Eo A min
Eijo (A, +
(1
Eo Amin
2
[4 (4
if Amia i Amin
S 4
Σ Σigio A,²
where we used Lemmas 6, 9 and 7.
Specific instances We consider the two instances μ4l and #22 from Table with e 0. Since most theoretical guarantees on BAI algorithms assume that there is a unique best arm, we don't 't study μgz. We display the boxplots of the empirical stopping time on 1000 runs.
3.0x10
2.00x10
2,0x10
1.50x10
Edrel
1.00x10
1.0x10'
5,00x10*
Figure 15: Empirical stopping time for the stopping rule (3) usingg (c, (0, 0.01) on instances (a) ji and (b) p2. "I" denotes log(n) "p" denotes En aa/2.
Figure 15 confirms the empirical observations from Figure 14. Overall, EB- EB-TC (c.... performs poorly and EBTTC,, has good empirical performance for BAI.
72


Reviews:
[{"review_id": "S5r7OX2MyO", "reviewer": "Reviewer_B3zV", "summary": "In this paper, the authors proposed EB-TC_epsilon, a novel sampling rule for epsilon-best arm identification. While the proposed algorithm is analyzed for approximate best arm identification, it is also an anytime sampling rule that can be used for fixed confidence, fixed budget, or anytime settings. The algorithm is analyzed for those settings and is empirically evaluated with numerical simulations.", "questions": "What is the motivation for proposing one algorithm that works for approximate best arm identification and works, without modification, for fixed confidence, fixed budget, or anytime settings? There are other algorithms proposed specifically for different settings, and one might choose an algorithm based on the setting. It would be nice to see some discussion on this.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed algorithm is simple and easy to implement. Without modification, it works for approximate best arm identification, fixed confidence, fixed budget, or anytime settings.\n\n2. The proposed algorithm is theoretically analyzed and empirically evaluated with numerical simulations. The results show that the proposed algorithm can achieve competitive performance compared to other methods.", "weaknesses": "1. The presentation of this paper can be improved. I found it hard to follow this paper in its current form, and I can not discuss its contribution with confidence. \n   (a) The main results and theoretical discussions are mixed with related works. While it is nice to relate the proposed algorithms with previous works, it is hard to see the difference/improvement without clearly presenting previous results -- many of the previous algorithms are only cited by name and without further explanation. \n   (b) Many of the high-level discussions and insights are also mixed with mathematical derivations, which makes it hard to follow. It would be nice to focus more on the main results and insights and present the details in the appendix.\n\n2. The algorithm presentation is not well organized. The algorithm is introduced in line 120 and a crucial quantity $\\bar \\beta_{n+1}$ is not defined until line 140. It would be nice to define all the quantities before or when introducing the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the feedback and questions. We hope to address them in the following.\n\nWe first answer the points raised in the “weaknesses” section.\n\n**Presentation of the results.**\nWe choose to intertwine the presentation of our results and some related work in order to better contextualize our contributions and compare them with existing work. While Theorem 2 is already followed with a precise comparison with existing bounds (l. 230-237), after Theorem 1 we will remind the reader of other algorithms that are asymptotically optimal for $\\varepsilon$-BAI in Gaussian bandits, emphasizing that none of them have non asymptotic guarantees of any kind. And after Theorem 3 we will explicitly state the expression of $H(\\varepsilon)$ featured in the bound of [39].  \n\n**Presentation of the algorithm.**\nWe will add the definition of $\\bar{beta}_{n+1}(i,j)$ explicitly in Figure 1. Figure 1 serves as a brief summary of the sampling rule. More details on the algorithms is given in Section 2, including the notation used in Figure 1.\n\nWe now answer your other question.\n\n**Motivation for an $\\varepsilon$-BAI algorithm having guarantees in fixed confidence, fixed budget, or anytime settings simultaneously.**\nTypical applications of (approximate) best arm identification are in A/B/n testing: identify a promising treatment in a clinical trial by giving treatments to patients, or a version of a website that generates sufficient revenue on a marketing platform. In case we opt for a fixed-confidence algorithm but for some practical reasons (no more funding to include more patients, company decision that the new version has to be deployed now) the test has to be stopped before the stopping condition is reached, it is desirable to still have guarantees for the recommended arm (treatment, webpage). Our anytime guarantees in that case say that despite stopping early, our error probability cannot be much worse than the error that would have been obtained using uniform sampling with that budget –and uniform sampling is still a common practical choice for A/B testing. In case we opt for a fixed-budget algorithm, state-of-the-art algorithms (SH,SR) are very sensitive to the budget T, which is used to decide the size of their different phases. These algorithms come with no guarantees on the error probability if early stopping occurs. If on the contrary we are given an additional testing budget (new funding secured due to promising results, more time before deploying the new version) it is not clear how to make good use of it, besides restarting these elimination-based algorithms. Our algorithm, conversely, would have guarantees whatever the budget ends up being, and we could even decide to couple it with a fixed-confidence stopping rule, for any confidence level $\\delta$. We think that it is valuable to have a  simple sampling rule which is robust to some changes in the setting tackled, and also performs very well empirically in fixed-confidence, fixed-budget and anytime settings. While EB-TC$_\\varepsilon$ is optimal in the asymptotic fixed-confidence setting when combined with an appropriate stopping rule, we acknowledge that we did not prove that it is state-of-the-art in the anytime (fixed-budget) setting, as the simple regret bound proved for Doubling SH is smaller. However, the practical story seems different, and Doubling SH comes with no guarantees in the fixed-confidence setting.\n"}, {"review_id": "AgCavXuT5s", "reviewer": "Reviewer_6z6m", "summary": "The paper considers the epsilon-BAI problem in the multi-armed bandit setting with sub-gaussian arm distributions. It proposes a top2 algorithm for the problem that works across different performace criteria: fixed-confidence, fixed-budget, as well as simple-regret. The proposed algorithm is asymptotically optimal (as delta-> 0) for the fixed confidence setting for gaussian bandits, where delta is the bound on probability of errors. The paper also provides finite delta analysis of the upper bound on the sample complexity in the fixed confidence setting. Another novel feature of the proposed algorithm is that it can be used in the fixed-budget setting, without a prior knowledge of the budget. The theoretical results are accompanied with extensive simulations and numerical studies. ", "questions": "1. Could you clarify the definition of simple regret in the epsilon-BAI framework? In line 47, should there also be an indicator on chosen arm not being epsilon-best? In line 97-98, is Delta_{\\hat{i}_n} missing in the integration? \n\n2. The lower bound in Lemma 1 is specifically for Gaussian bandits. How does it compare with sub-Gaussian bandits? Is there some monotonicity? It will be good to add a discussion around this. If not, including an example (if known) could help.\n\n3. In Figure 1 (EP-TC_eps algorithm with fixed or IDS) line 3, it will be good to refer to the equation for updating \\bar{beta}_{n+1}(i,j) in the main text. \n\n4. It will be helpful if the discussion in lines 150-151 could be elaborated. What are the K(K-1) different tracking rules?  Are these the different choices of beta that are maintained for each leader/challenger pair? \n\n5. How should one choose epsilon_0 in practice? \n\n6.  In lines 201-203, is that a requirement for asymp. optimality, or is it a requirement for proofs to work? Can one show that if number of optimal arms is greater than 1, then the algorithm doesn't converge (may be b/c of some discontinuity)?\n\n7. Lines 235-237: Would using any-delta methods to construct UCB and LCB indexes in LUCB help in this regard?\n\n8. In Lemma 9, Line 530, could you clarify what j is in mu_eps(i)_j ?\n\n9. Is Lemma 12 a standard result? Adding a citation or proof would help.\n\n10. What are the challenges in generalizing the proofs to beyond gaussian arms to exponential families? What specific properties of Gaussians are used in analysis that may not hold for exponential families? Can one pin down to the level that if we can prove this, this, and this about KL (for example) or other functions in exponential families, then we should get the bound? \n\nMinor:\n1. Line 207 satisfies these ...\n2. Line 587: eeror --> error\n\n", "limitations": "Na", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe that the results of this work are novel. The proposed sampling rule, when coupled with either stopping rule or recommendation rule (or both) works across different BAI settings: fixed-confidence, fixed-budget, simple regret. The paper also discusses well and brings out the comparison with existing works and techniques for each of these problems. I especially like the discussions that are included after each result. I believe that the literature review is also thorough. The extensive numerical studies undertaken definitely add value to the theoretical work.  ", "weaknesses": "I believe that the paper is dense and too long for a conference submission with many details in the appendix. But this may be because of the space constraints. \n\nPlots in Figures 6, 10, and 12 are very light. Also the legends are too small to read for most of the plots. In general, it will help to spread out the plots for readability. Since the plots are already in appendix, space isn't an issue. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the feedback and questions. We will follow your suggestion and improve the presentation of the plots in the appendix. \n\n**1) Simple regret in $\\varepsilon$-BAI.**\nThe simple regret considered in this work is the standard simple regret introduced by [5] in the pure exploration literature, which does not depend on any parameter. $\\varepsilon$ from $\\varepsilon$-BAI is only meaningful when considering probabilistic performance metrics, e.g. the probability of marking an $\\varepsilon$-error. The simple regret is an aggregated performance metric (lines 97-98). Therefore, there is no missing indicator in line 47. \nThere is no missing $\\Delta$ in the formula in l. 97-98, which follows from integrating a positive function.\n\n**2) Lower bound in Lemma 1 for more general distributions than Gaussians.**\nLet $\\nu$ be a $\\sigma$-sub-Gaussian instance with means $\\mu$. On $\\nu$, Theorem 1 shows that there exists an algorithm (EB-TC$\\varepsilon$) with asymptotic expected sample complexity upper bounded by $T_{\\varepsilon}(\\mu)$. Therefore, the characteristic time for the class of sub-Gaussian distributions (which does not have a form as “explicit” as (1)) is always smaller than the ones for Gaussian having the same means and variance $\\sigma^2$.\n\n**4) Tracking procedures.**\nWe define one tracking procedure per pair of leader/challenger $(i,j) \\in [K]^2$ such that $i \\ne j$, hence we have $K(K-1)$ tracking procedures. For the tracking associated with $(i,j)$, we maintain one average value $\\bar \\beta_{n}(i,j)$ of proportions. For fixed $\\beta$, we have $\\beta_{t}(i,j) = \\beta$, hence $\\bar \\beta_{n}(i,j) = \\beta$. When using IDS proportions, each tracking procedure has a different target. For example, the tracking procedure of pair $(i,j)$ targets the average proportions $\\bar \\beta_n (i,j)$ for the counters $N_{n,j}^{i}$ and $T_{n}(i,j)$. Those counters are independent of each other, meaning one cannot increment the counters of pair $(i,j)$ when using a different pair. At each round $n$, only one tracking rule is considered, i.e. the one of the pair $(i,j) = (B_n, C_n)$.\n\n**5) Choice of $\\varepsilon_{0}$.**\nWe discuss the choice of $\\varepsilon_0$ between line 152 and 161, and perform experiments to support our claims (e.g. Figures 5, 6 and 7 in Appendix J.2.1). One should take $\\varepsilon_0 = \\varepsilon$ when considering fixed-confidence $\\varepsilon$-BAI if $\\varepsilon > 0$. As regards the simple regret, we recommend choosing $\\varepsilon_0$ not too small. Of course for every instance $\\mu$ there exists an optimal value of $\\varepsilon_0$ minimizing the simple regret at some target time $T$, that depends on both $\\mu$ and $T$. We did not investigate the scaling of this “oracle” value of $\\varepsilon_0$ as it is not relevant in practice. Instead in our experiments we mostly used the value $\\varepsilon_0 = 0.1$ across different benchmarks with means in $[0,1]$. For example Figure 6 reveals that the empirical simple regret stays similar when taking $\\varepsilon_0 \\in \\{0.05,0.1,0.15\\}$.\n\n**6) Unique best arm assumption.**\nWe did not prove that the algorithm is not asymptotically optimal when the number of optimal arms is greater than 1, but we observed empirically that the leader in the sampling rule can oscillate between the multiple best arms. Due to this oscillating behavior, it is not clear whether the empirical proportion will converge towards one of the (multiple) vectors of optimal weights. We note that only a few algorithms in the literature manage to attain asymptotic optimality on instances for which there are multiple optimal allocations. We note that it follows from Theorem 2 that the asymptotic sample complexity is at most a factor 2|i_\\star(\\mu)| from the optimal one.\n\n**7) Using any-delta methods to construct UCB and LCB indexes in LUCB.**\nIf by “any-delta” methods, you mean using UCB and LCB that are independent of $\\delta$ (such as the one used in regret minimizing algorithms, only depending on the current time step $t$), no algorithm of this kind has ever been proved to be ($\\varepsilon,\\delta$)-PAC for best arm identification. In confidence-based BAI algorithms, the confidence intervals are calibrated such that the probability that there exists some $t$ and some arm $i$ such that $\\mu_i$ is not in $[LCB_i(t),UCB_i(t)]$ is smaller than $\\delta$. As such, the confidence bounds have to depend on $\\delta$. \n\n**8) Lemma 9.**\nTypo in line 530: for all $j \\ne i$, we have $\\mu_j$ - $\\epsilon$ = $\\mu_{\\epsilon} $(i)j, and $\\mu_{i}$ = $\\mu_{\\varepsilon}(i)_{i}$.\n\n**9)  Lemma 12.**\nWe will add that Lemma 12 was used by previous asymptotic analysis of Top Two algorithms, e.g. Lemma 3 in [31], Lemma 5 in [35] or Lemma 14 in [20]. \n\n**10) Generalizing the proofs to exponential families.**\nIt is possible to adapt the EB-TC$\\varepsilon$ algorithm to a given single-parameter exponential family, by using the corresponding expression of the transportation cost [21] and the adaptive proportions given by IDS [38]. Obtaining asymptotic $\\beta$-optimality in $\\varepsilon$-BAI for more general exponential families should be doable (up to technicalities) by adapting the existing proofs for BAI, see e.g. [20]. However, even for $\\epsilon=0$, it is still an open problem to (1) show asymptotic optimality with IDS and (2) obtain finite-confidence guarantees for distributions other than Gaussians. Our proofs leverage Gaussian-specific properties for the transportation costs: they can be expressed as the product between a function of the gap and a function of the allocation.\nRegarding the results presented in Section 4 (Theorem 3 and Corollary 1), it is actually not clear to what extent our theoretical/empirical results can be improved by adapting the algorithm to take into account the family of sub-Gaussian distributions itself. The simplicity of EB-TC$_{\\varepsilon}$ is a key element that allows us to control the probability of error for all $\\epsilon$ and all time $n$.\n"}, {"review_id": "Gwcxq1MeLX", "reviewer": "Reviewer_KTru", "summary": "This paper proposes an anytime $\\epsilon$-best-arm identification algorithm for multi-armed bandits that can be employed in both fixed-confidence and fixed-budget setting. The algorithm is analyzed in asymptotic fixed-confidence, non-asymptotic fixed-confidence and fixed-budget settings. Meanwhile, the paper also provides empirical results in many different settings.", "questions": "- How does the proposed algorithm perform, compared with uniform sampling, SH and SR, in fixed-budget BAI ($\\epsilon=0$) problem?\n- Based on Theorem 1, the proposed algorithm is asymptotically optimal for 0-BAI when taking $\\epsilon_0=0$. However, based on Theorem 2, it seems the expected stopping time just explode when taking $\\epsilon_0=0$ with positive $\\delta>0$. Is this a contradiction? Did I misunderstand anything? How does the algorithm perform in 0-BAI with finite $\\delta>0$?", "limitations": "The limitations are addressed well in this paper.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- The proposed algorithm is anytime in nature and thus widely applicable.\n- The analysis for fixed $\\beta$ is thorough and covers all asymptotic fixed-confidence, non-asymptotic fixed-confidence and fixed-budget settings.\n- The empirical experiments are extensive.", "weaknesses": "- The analysis for the IDS variant is limited.\n- This may be just due to my misunderstanding, but it seems the expected stopping time of the proposed algorithm with finite confidence $\\delta>0$ will explode for BAI ($\\epsilon=0$) problem.\n\n### Suggestions on Writing\n- It may be better to also give the formula of $\\bar{\\beta}_{n+1}(i, j)$ under the IDS variant in the algorithm summary.\n- Do we simply have $T_{\\epsilon_0, \\beta}(\\mu)=\\min_{i\\in\\mathcal{I}\\_{\\epsilon_0}(\\mu)}T_{\\epsilon_0, \\beta}(\\mu, i)$ in the statement of Theorem 1? It seems this quantity is not formally defined in the main paper.\n- It seems the statement of Theorem 1 does not mention that the result for IDS variant only holds for Gaussian distribution.\n- If possible, it may be better to present results in the main paper more in terms of big-$\\mathcal{O}$ instead of exact formula.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. We hope to address them in the following.\n\nWe first answer the points raised in the “weaknesses” section.\n\n**Limited analysis of IDS.**\nExtending our other results (Theorems 2 and 3) to EB-TC$_{\\varepsilon}$ with IDS proportions is an interesting direction for future research that we are exploring. Our experiments suggest that this algorithm enjoys smaller empirical stopping time and similar empirical simple regret. It would be valuable to quantify those improvements theoretically.\n\n**Theorem 1 holding for sub-Gaussian distributions.**\nTheorem 1 holds for all $\\nu \\in \\mathcal D^{K}$ with mean $\\mu$ such that $|i^\\star(\\mu)|=1$, where $\\mathcal D$ is the set of $1$-sub-Gaussian distribution, also for its IDS version. As mentioned in lines 184-187, the results are only asymptotically ($\\beta$-)optimal in the family of Gaussian distributions. For more general sub-Gaussian distributions, our asymptotic upper bound still holds, yet it is suboptimal compared to the best achievable lower bound.\n\nWe now answer your other questions.\n\n**Expected stopping time for $\\varepsilon_{0} = 0$.**\nTheorem 1 does not allow $\\varepsilon_0 = 0$. With $\\varepsilon_0 = 0$ we recover the EB-TC algorithm for BAI (see [20]), which is asymptotically $\\beta$-optimal if all arms have distinct means, but can be arbitrarily bad if that’s not the case (see Appendix  D.3 in [20]). Compared to existing asymptotic results on Top Two algorithms, Theorem 1 is the first one removing the assumption that all arms have distinct means. The regularization of the $\\varepsilon_0$ parameter allowed us to remove it with little modification to the original proof. To remove this assumption in BAI (i.e. $\\varepsilon = 0$), we would require an additional mechanism to ensure sufficient exploration. While we conjecture that the TS or UCB leader and the TCI challenger would be enough, we are certain that EB-TC can get stuck for instances having all sub-optimal arms with the same mean. Intuitively, it cannot recover from unlucky first draws and the leader/challenger will alternate among the sub-optimal arms. \nTheorem 2 does not allow $\\varepsilon_0 = 0$. In Theorem 2, the sample complexity indeed explodes when $\\varepsilon_0 \\to 0$. When the arms have distinct means, we emphasize the Theorem 2 and the asymptotic optimality of EB-TC are proved using very different tools, so that the fact that Theorem 2 cannot be used to prove asymptotic optimality when letting $\\delta$ go to zero is not a contradiction. The theoretical intuition and empirical studies made in [20] are abounding towards the same observation: EB-TC can truly get stuck in a finite-confidence regime, hence have dramatically poor empirical performance. \n\n**Empirical performance in the fixed-budget setting.**\nEB-TC$\\varepsilon$, uniform sampling, DSR and DSH are all anytime algorithms. The fixed-budget performance of an anytime algorithm is the same as its anytime performance. Therefore, our experiments provide empirical evidence of the superior performance of EB-TC$\\varepsilon$ compared to uniform sampling, DSR and DSH as regards the simple regret (see Figures 2(b), 6, 10, 12). We displayed the simple regret metric since it is an aggregated metric with a more practical meaning. \nComparing an anytime algorithm with a fixed-budget algorithm with budget $T$ gives an unfair advantage to the fixed-budget algorithms which fully leverage the knowledge of $T$ but have no theoretical guarantees at time $n \\ne T$ (even at time $T \\pm 1$). Nevertheless, we performed additional experiments to answer your question. In the separate pdf available in the “global” response, we compared EB-TC$\\varepsilon$ with SR and SH on different instances. For SR and SH, we emphasize that each point corresponds to a different instance which leverages the knowledge of the budget $T$. As a result, the empirical performances of SR and SH are better than the ones of DSR and DSH. Overall, EB-TC$\\varepsilon$ seems to perform on par with SR and SH in all instances considered, and to outperform SH for some instances. In our experiments, we consider SH in which the samples are dropped between each phase, as analyzed theoretically in [1]. This loss of information explains why SR has better empirical performance than SH. To the best of our knowledge, there is no theoretical analysis for the heuristic SH where all the samples are preserved, even though it has better empirical performance.\n\n**Miscellaneous.** Thank you for your suggestions. We will add the reference to the update of $\\bar \\beta_{n+1}(i,j)$ in Figure 1 and the formal definition of $T_{\\epsilon, \\beta}(\\mu) = \\min_{i \\in \\mathcal I_{\\varepsilon}(\\mu)} T_{\\epsilon, \\beta}(\\mu, i)$. "}, {"review_id": "N8au1YJxic", "reviewer": "Reviewer_PH2Y", "summary": "This work proposed the EB-TC algorithm for $\\varepsilon$-best arm identification in stochastic bandits. \nEB-TC is a BAI algorithm that does not require the knowledge of confidence or horizon, and hence it can be applied in both fixed-confidence and fixed-budget settings. Beyond theoretical guarantees, this work also provided numerical experiments to evaluate the performance of EB-TC.\n\n\n\n==========================\n\nThanks for the response. I would like to keep the score.", "questions": "As mentioned in the Weakness section: what is the key obstacle such that EB-TC cannot work well for the identification of the optimal arm? I appreciate some explanation of this point. A (possibly) suboptimal theoretical bound is even better.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally easy to follow.\n2. EB-TC seems to be a nice BAI algorithm that does not need to know confidence or horizon as priori knowledge, which can be applied in both fixed-confidence and fixed-budget settings.\n3. EB-TC can be viewed as a generalization of the Top Two Sampling rule which was designed in an earlier work.\n4. The paper provides a clear comparison to existing works.", "weaknesses": "As discussed in Section 2.1, the EB-TC algorithm may not perform well to identify the optimal arm. Can this issue be solved?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and question. We hope to address it in the following.\n\n**Performance of EB-TC$_{0}$ in BAI.**\nIt is well known from prior work that EB-TC empirically performs poorly to identify the optimal arm for moderate $\\delta$. This issue can be solved by adding an implicit exploration mechanism in the choice of the leader/challenger pair. For the choice of leader, we can use randomization (TS leader [33,31,35]) or optimism (UCB leader [19]). For the choice of the challenger, we can use randomization (RS challenger [33]) or penalization (TCI challenger [20], KKT challenger [38] or EI challenger [31]). A contribution of our work is precisely to show that for $\\epsilon_0$-BAI with $\\epsilon_0>0$, there is no need for an additional exploration mechanism since the slack $\\varepsilon_0$ used by EB-TC$_{\\epsilon_0}$ naturally induces sufficient exploration. Our experiments highlight that the extra exploration mechanisms discussed above are indeed superfluous for approximate best arm identification (see lines 343-345). \n\n**Understanding the lack of robustness of EB-TC$_{0}$.**\nTo better understand the lack of robustness of EB-TC in BAI, let us consider 3-arms bandits with means $\\mu = (x, 0, 0)$ where $x > 0$. For those instances, we call “unlucky first draws” any situation where after gathering a couple of samples $n_{0}$, we have $\\mu_{n_{0},1} << 0$ and $\\mu_{n_{0},2}$ $\\approx$ $\\mu_{n_{0},3} >> 0$. The probability of this event depends on $n_0$ and $x$, yet it is fixed and bounded away from $0$. Confronted with this situation, EB-TC will choose its leader/challenger pair among the two sub-optimal arms, and never sample the best arm. Since $\\mu_{n_{0},1} << 0 = \\mu_{2} = \\mu_{3}$, the situation will not change after both sub-optimal arms have converged to their true value: (1) one of them will be leader and (2) the second one will be the challenger since the mean gap tends to $0$. \nNow, let’s consider a slightly modified $3$-arms bandit with mean parameter $\\mu = (x, 0, -\\kappa)$ where $x >> \\kappa > 0$. Similarly as above, under the “unlucky first draws” event, EB-TC will choose its leader/challenger pair among the two sub-optimal arms, without sampling the best arm for a long time. In contrast to the above example, this instance has distinct means hence there is a different behavior after the convergence of the empirical means of the two suboptimal arms. After a very large number of samples, the leader will be the second arm and the challenger will be the first arm. Compared to above, the third arm cannot be the challenger since its TC will be roughly equal to $n \\kappa^2/2$ which is larger than the TC of the first arm which is roughly $n_{0} \\mu_{n_{0},1}^2$. By comparison between both TC, we see that the time necessary for the algorithm to stop being stuck and start sampling the arm $1$ is proportional to $1/\\kappa^2$. Therefore, we conjecture it is possible to show a probabilistic lower bound on the sample complexity of EB-TC that involve the minimal gap between arms $\\Delta_{\\min} = \\min_{i \\ne j} |\\mu_{i} - \\mu_{j}|$ with a dependency of the order of $O(1/\\Delta_{\\min}^2)$.\nThe above discussion explains why EB-TC is asymptotic optimality for BAI under the distinct mean assumption, but has very poor performance in the finite-confidence performance. For more details on the limitations of EB-TC, we refer to Appendix D.3 [20] in which the algorithm is introduced and where its lack of robustness is discussed. \n"}, {"review_id": "APkI4lgDZH", "reviewer": "Reviewer_kKhf", "summary": "The paper gives a new epsilon-best arm identification algorithm which is simple and anytime, just amounting to balancing between the empirical best arm and roughly speaking, the arm with the best chance to be superior to it by epsilon. Its performance is analyzed mainly for fixed confidence, and it also attains decent (not particularly optimal) bounds for fixed budget. The results assume a unique best arm but allow repeated mean values among the other arms.\n\n", "questions": "Maybe ``\\beta-optimal'' could be defined more carefully, and the ratio bound of T_{\\eps} vs T_{\\eps,\\beta} could be stated near the definitions. \n\nJust before line 200, it would be nice to cite a few of these other works on Top Two algorithms. \n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The fixed confidence bounds are very good (sharp for Gaussians) and the algorithm is nice and simple. The epsilon parameter can be mismatched, though this degrades the bounds a bit. ", "weaknesses": "No new minimax regret bounds are obtained. As I understand it the paper is basically giving a simpler algorithm with some nice guarantees. Which is fine but not the most revolutionary.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. We hope to address them in the following.\n\nWe first answer the points raised in the “weaknesses” section.\n\n**Minimax regret bounds.**\nGiven that we are considering the $\\varepsilon$-BAI setting, we are not sure to understand what the reviewer meant by “minimax regret bounds” as those bounds are only meaningful in the regret minimization literature. In this work, we consider pure exploration and focus on problem-dependent bounds. A (nearly) minimax optimal algorithm for minimizing simple regret is uniform sampling as proved in [5] so there is not much more to say in this setting. We consider the fixed-confidence setting, in which we compare ourselves to the tight asymptotic problem-dependent lower bound given in Lemma 1, and we compare ourselves to known problem-dependent results in the finite-confidence and anytime regimes. \n\n**Simple algorithm with nice guarantees: revolutionary or not ?**\nWe truly believe that it is a valuable contribution to study simple algorithms that are (1) easy to understand and implement, (2) empirically competitive (3) robust to different formulations of the pure exploration task (see also our answer to reviewer B3zV). Our work is the first to propose a single algorithm that is simultaneously asymptotically optimal in the fixed-confidence $\\varepsilon$-BAI setting (Theorem 1), has finite-confidence guarantees (Theorem 2), and has also anytime guarantees on the probability of error at any level $\\varepsilon$ (Theorem 3), hence on the simple regret (Corollary 1). Such simple and versatile algorithms are the ones that will be most likely useful by practitioners. While we don’t claim to be revolutionary, we still consider it to be a significant contribution to the pure exploration literature.  \n\nWe now answer your other questions.\n\n**Definition $\\beta$-optimality.**\nWe will add explicitly the definition of ($\\beta-$)optimal below Lemma 1 and add the worst-case inequality $T_{\\epsilon,1/2}(\\mu) \\le 2 T_{\\varepsilon}(\\mu)$ there as well.\n\n**Citing other Top Two algorithms.**\nWe provided multiple references to other works on Top Two algorithms throughout the paper (e.g. in Section 2.1). For the sake of completeness, we will add more references just before line 200.\n"}]

Author rebuttal:
We attach additional experiments to better answer the questions of the reviewer 6z6m.

Meta-review: Reviewers are very positive after rebuttal. A very novel contribution to epsilon best arm identification and algorithm is versatile and applicable to fixed confidence, fixed budget and anytime settings. This is a solid technical contribution to the bandit literature.
Decision: Accept (poster)