Non-Asymptotic Analysis of a UCB-based Top Two Algorithm
Authors: Marc Jourdan
Rémy Degenne
Venue: NeurIPS 2023 spotlight (2023)
Keywords: multi-armed bandits
best-arm identification
Gaussian bandits
Top Two algorithm
fixed confidence
finite confidence
TL;DR: We have studied fixed-confidence best arm identification in multi-armed bandits and provide the first non-asymptotic analysis of a Top Two algorithm.

Abstract: A Top Two sampling rule for bandit identification is a method which selects the next arm to sample from among two candidate arms, a *leader* and a *challenger*. Due to their simplicity and good empirical performance, they have received increased attention in recent years. However, for fixed-confidence best arm identification, theoretical guarantees for Top Two methods have only been obtained in the asymptotic regime, when the error level vanishes. In this paper, we derive the first non-asymptotic upper bound on the expected sample complexity of a Top Two algorithm, which holds for any error level. Our analysis highlights sufficient properties for a regret minimization algorithm to be used as leader. These properties are satisfied by the UCB algorithm, and our proposed UCB-based Top Two algorithm simultaneously enjoys non-asymptotic guarantees and competitive empirical performance.

Non-Asymptotic Analysis of a UCB-based Top Two Algorithm
Mare Jourdan marc. jour dan@ inria. frr
Rémy Degenne
r remy, . dew.edeemeniiii...r.
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRISIAL, F-59000 Lille, France
Abstract
A Top Two sampling rule for bandit identification a method which selects the next arm to sample from among two candidate arms, a leader and a challenger. Due their simplicity and good empirical performance, they have received increased attention in recent years. However, for fixed-confidence best arm identification, theoretical guarantees for Top Two methods have only been obtained in the asymp- totic regime, when the error level vanishes. In this paper, we derive the first non-asymptotic upper bound on the expected sample complexity of Top Two algorithm, which holds for any error level. Our analysis highlights sufficient prop- ertics for regret minimization algorithm to be used as leader. These properties are satisfied by the UCB algorithm, and proposed UCB-based Top Two algo- rithm simultaneously enjoys non-asymptotic guarantees and competitive empirical performance.
Introduction
Faced with collection of items ("arms") with unknown probability distributions, a question that arises in many applications is to find the distribution with the largest mean, which is referred as the best arm. Different approaches have been considered depending on the data collection process. encompasses situations where there no control on the collected samples. Experimental design 7 35 aims at choosing the data collection scheme priori. In the multi-armed bandit 4 20 and the ranking and selection (18) literature, an algorithm chooses sequentially the distribution from which it will collect an additional sample based on past data.
Sequential hypothesis testing [10 37
In order to have theoretical guarantees for this identification problem, one should adopt statistical model on the underlying distributions. While parametric models are reasonable for applications such as A/B testing (28), they are unrealistic other fields such agriculture (2T). Despite the restricted scope of its applications, studying the identification task for Gaussian distributions is a natural first step. Hopefully the insights gained will then be generalized to wider classes of distributions.
In the fixed confidence identification problem, an algorithm aims at identifying the best arm with an error of at most 8 (0, 1) while using as few samples as possible. Since each sample has cost, those algorithms should provide an upper bound on the expected number of samples used by the algorithm before stopping. For those guarantees be useful in practice, they should hold for any which is referred to as the non-asympiotic (or moderate) regime. In contrast, the asymptotic regime considers vanishing error level, i.e. 8 0. For Gaussian distributions, Top Two algorithms [36] 39
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

have only been studied in the asymptotic regime. We show the first non non-annnnnnnn aammmmttttiicc guaranty for Top Two algorithm holding for any instance with a unique best arm.
1.1 Setting and related work
Gaussian bandit problem is described by K arms whose probability distributions belongs to the set D of Gaussian distributions with known variance o². By rescaling, assume of for all i [K]. Since an element of D is uniquely characterized by its mean, the vector μ IR refers to K-arms Gaussian bandit. Let 4 C R K be the (K di-dmnnsio simplex.
A best arm identification (BAI) algorithm aims at identifying an arm with highest mean parameter, iee. an arm belonging to the set i* (n) arg [[]] Hi. At each time n E N, the algorithm (1) chooses an arm I, based on previous observations, (2) observes a sample Xn.J, ~ N (Jr,, 1), and (3) decides whether it should stop and return an arm in or continue sampling. We consider the fixed confidence identification setting. in which the probability of eπror of an algorithm is required to be less than given 8 (0, 1) on all instances μ. The sample complexity of algorithm corresponds to its stopping time T5. which counts the number of rounds before termination. An algorithm is said to be 8-correct on D if P.,, (T& to0, 8,, & i (p)) for all μ E D [14] We aim at designing 5-correct algorithms minimizing E[rs]-
As done in all the literature on fixedccofidence BAI, we assume that there is a unique best arm and we denote it by i" (J)) or when μ is clear from the context. To ensure d-correctness on D an algorithm has to be able to distinguish the unknown μ from any instance having a different best arm, hence needs to estimates the gaps between arms. Lemma 1.I ggiess a lower bound on the expected sample complexity which is known to be tight in the asymptotic regime, i.e. when ò goes to zero.
Lemma 1.1 (177). An algorithum which is 6-correct on all problems in D satisfies that for all R E [Ta] T (n) log(11 where (4) = min (1) and, for all B E (0. 1).
(1i. (x) 14:)2
Tz(m)-
=
max w WE MEAAgio (1)
min (1) (1/3 B
1/wx)
When considering the sub-class of algorithms allocating a fraction / of their sample to the best arm, we obtain lower bound as in Lemma 1.1 with T3 (1) instead of T (H²). An algorithm is said to be asymptotically optimal (resp. B-optimal) its sample complexity matches that lower bound asymp- totically, that is if lim sups-n (og(/))) < (M) (resp. T7 (P)). (38 showed the worst-case inequality (1) S (4) for any single-parametee exponential families. Therefore, the expected sample complexity of an asymptotically 8-optimal algorithm with 1/2 worst twice higher than that of any asymptotically optimal algorithm. Leveraging the symmetry of Gaussian distribu- tions, a tighter worst-case inequality can be derived (Lemma C.6). The allocations (p)) and w (u) realizing T (H) and Tī (p) are known to be unique, and satisty min min (w" (m),, w (m)) >
[6] showed that 2 < w" (H)). S - 1 for Gaussian distributions (Lemma C.4
Related work The first BAI algorithms were introduced and studied under the assumption that the observation have bounded support, with known upper bound [15] 24 19). The sample complexity bounds proved for these algorithms scale as the sum of squared inverse gap, i.e. H(u)= == 2A -2 min Edsr. 2(14- - p4)) where Amin := minlya- (μ:- (u:). which satisfies H (14) S (u) S 2/1 (n) 17 Following their work, a rich literature designed asymptotically optimal algorithms in the fixed-confidence setting for parametric distributions, such as single-paramete exponential families, and non- parameeriii distributions such as bounded ones. Those algorithms build on two main ideas. The Tracking approach computes at each round the optimal allocation for the empirical estimator, and then tracks it [7]. To achieve lower computational cost, Game- based algorithms [12] view T (H) as min-max game between the learner and the nature, and design saddle-point algorithms to solve it sequentially.
Top Two algorithms arose as an identification strategy based on the Thompson Sampling algorithm for regret minimization [41] 38 introduced Top Two Probability Sampling (TTPS) and Top Two Thompson Sampling (TTTS). Adopting Bayesian viewpoint, Russo studied the convergence rate of the posterior probability that is not the best arm, under some conditions on the prior. For Gaussian bandits, other Bayesian Top Two algorithms with frequentist components have been shown to be

---

asympiotically 3-optimal: Top Two Expected Improvement (TTEI, (36) and Top Two Transportation Cost (T3C, (39). 21 introduces fully frequentist Top Two algorithms. Their analysis proves asymptotic B-optimalityy for several Top Two algorithms and distribution classes, beyond Gaussian. exponential families, at the price of adding forced exploration. 44 proposes an algorithm to tackle the top-k identification problem and introduces information-directed selection (IDS) to choose 3 in an adaptive manner, which differs from the one proposed in [33] In addition to their success in the fixed-confidence setting, Top Two algorithms have also been studied for fixed-budget problems (2]. in which guarantees on the error probability should be given after T samples. While existing Top Two sampling rules differ by how they choose the leader and the challenger, they all sample the leader with probability 3. By design, Top Two algorithms with fixed B can reach 3-optimality at best, and cannot be optimal on all instances μ.
34 provides guarantees for
Shortcomings of the asymptotic regime While the literature provides a detailed understanding of the asymptotic regime, many interesting questions are unanswered the non-asymptotic regime. have shown that the sample complexity is affected by strong moderate confidence terms (independent of 8). The analysis of [2I] applies to their 3-EB-TC algorithm whose empirical stopping times is order of magnitude larger than its competitors for å 0.01. Since the proof of asymptotic 3-optimality hides design flaws, non-asym -anaympttttic guarantees should derived to understand which Top Two algorithms will perform well in practice for any reasonable choice of 8.
Recent works [9] 40
32 31
1.2
Contributions
Our main contribution is to propose the first non-asymptotic analysis of Top Two algorithms. We identify sufficient properties of the leader (seen as a regret-minimization algorithm) for it to hold. This solves two open problems: obtaining holds for any d) and (2) holds for all instances having a unique best arm (i.e. sub-optimal arms can have the same mean, which was not allowed in the analyzes of existing Top Two algorithms). As consequence, we propose the TTUCB (Top Two UCB) algorithm which builds on the UCB algorithm.
upper bound which (1) is non-asymplotic (Theorem [2.
By using tracking instead of sampling to choose between the leader and the challenger. TTUCB is the first Top Two algorithm which is asymptotically 8-optimal (Theorem (.3) and has non-asymptotic guarantees (Theorem 2.4p. Our experiments reveal that TTUCB performs on par with existing Top Two algorithms, which are only proven be asymptotically /--pptmal, even for large sets of arms. Numerically, we show that considering adaptive proportions compared to fixed / 1/2 yields a significant speed-up on hard instances, and to a moderate improvement on random instances.
2 UCB-based Top Two algorithm
We propose a fully deterministic Top Two algorithm based on UCB [5] named TTUCB and detailed in Algorithm We prove non-asymptotic upper bound on the expected sample complexity holding for any instance having a unique best arm.
Stopping and recommendation rules The a allgeerr F,, == (fI,, Xt,1, Xieihnen-1 hrefn-1) 11) encompasses all the information available to the agent before time n. Let No,; : Eie(n-1] 11 (Ir = i) be the number of pulls of arm i before time n, and its empirical mean by Mn,i N... Exem-1 X (1. i).
The algorithm stops as soon the generalized likelihood ratio exceeds threshold c(n 6), i.c.
Hn.in Pn.s 22e(n- 107n-11,1 1,
min 17t VI/Nu.. + 1/Nn,
where we recommend in = arg maxie[k] Mn,i at time n. Lemma 2.1 provides an explicit threshold ensuring Ó-correctness, which relies on concentration inequalities derived in (27).
Lemma 2.1. Let Ca defined in 16) s. Ca(x) ~ x + log(z). Given any sampling rule, taking
c(n, 8) = (logl - 1)/8)/2) + 4 log(4 + log(n:/2))
(2)
in the stopping rule I ensures for Gaussian distributions.
3

---

Algorithm TTUCB
Input: (3,8) E (0, 1)², threshold c: N x (0, - IR+ and function g: N RR. Pull once each arm E [K];
for n > K do
Set 8n2 arg [ Mn,si
If minssii VI/Na.a +1/Nma
Mn.ty -ant
2 v 220nn 1,6) then return in. else;
Set BLCB arg ma { (nn + Nu..
g(n]
and CRC arg 1 (nn knn))+
=B Observe Xnde by pulling In = BUCB if N Bue end for
I
else I, = CTC, CTc
n. BucB
Sampling rule We initialize by sampling each arms once. At time K, Top Two sampling
rule defines a leader B, E [K] and a challenger C, * B,, and chooses I, = =B, or I,, = Cn based on fixed allocation B. In prior work this choice was done random, which means that the leader was sampled with probability 3. We replace randomization by tracking, and show similar theoretical and numerical results (see Figure in Appendix G.2 For fixed B. we recommend to without prior knowledge on the unknown mean parameters (see Section 3.44 for adaptive proportions). This recommendation is supported theoretically by the fact that w (w)) S 1/2 (Lemma C.4 and that (1)2(H)/ (p) is significantly smaller than 2 for most instances (Lemma C.6 and Figure 2
1/2
Let L, E)e(n-1) 1 (B, i) be the number of time arm i was the leader, and N
EiEn-11 ((Br, (i) be the number of pulls of arm j at rounds in which was the leader. We use K independent tracking procedures. convert sequence of allocations over arms into sequence of arms, which ensures that the empirical proportions are close to the averaged allocation over arms. For each leader, we track the allocation (8, 1 - 3) between the leader and the challenger. Formally, we set In = Bn if N B. n.B. S LL else I, C,. Using Theorem in [3] for each tracking procedure yields Lemma 2.2
tracking procedure is a deterministic method to
Lemma 2.2. For all > K and all i E [K], we have -1 112 < Ni, BL., S 1.
Using tracking over randomization is motivated by practical and theoretical reasons. First, in some specific applications, the practitioner might be only willing to use deterministic algorithm. Second, in the analysis, it is easier to control deterministic counts since it removes the need for martingales arguments to bound the deviations of the samples. Therefore, tracking simplifies the non-asymptotic analysis. Third, Lemma 2.2 shows that the speed of convergence is at least ((1/n) for tracking, while we would obtain a speed of O(1/vT) for randomization.
At time n. the UCB leader is defined as
BUCB arg max + / (9(n)/Nn..). aE[K]
where / /g(n)//nn. is a bonus coping for uncertainty. Let > 1 and s > 1 be two concentration parameters. The choice of g(n) should ensure that we have an upper confidence bound on μás holding with high probability: with probability 1 Knn for all t [n|//, nn] and all arms E [K], μ4 e [Pr.: + Vg(l)/Ne,) For Gaussian observations, a function g which is sufficient for the purpose of our proof can be obtained by union bound over time, giving 9r. (n) 20x(1 + s) log We can improve on 9n. with mixtures of martingales, yielding 9m (n) = W -1 (2so log(n) + 2 log(2 a log n) + 2) with (z) - (-i for all x: 2 1, where W-1 is the negative branch of the Lambert W function, and W (x) x + (z). A UCB leader with (n) = O recovers the Empirical Best (EB) leader 21. Choosing g is central for empirical performance and non-asymptotic guarantees, but not for asymptotic ones. The lowest will yield better empirical performance since larger means more conservative confidence bounds. In our experiments where a = 8 -1.2, we will consider gm since 9m (1)) S (n) for 2 50.
Given leader Bn the TC challenger is defined as
arg min (Rn,B, Um,i)+ BB VI/Nn,B. + 1/Nas
TC
(4)

---

where 24 maxfx, 0}. [39 introduced the TC challenger as computationally efficient approxi- mation of the challenger in ITTS [38], which uses re-sampling till an unlikely event occurs. Both T3C and TTTS use the TS leader which takes the best arm of a vector of realization drawn from sampler, e.g. 0g ~ (H (, 1/Nn,;) for Gaussian distributions with unit variance.
Computational cost Computing the stopping rule I and the UCB leader (3) can be done in OKK). At time n where B, coincides with in computing the TC challenger f is done as a by-product of the computation of the stopping rule, without additional cost. When B, * ins we draw at random an arm with larger empirical mean. The per-round computational and memory cost of TTUCB is ((K)
2.1 Sample complexity upper bound
Leveraging the unified analysis of Top Two algorithms proposed by 121. we obtain the asymptotic
3-optimality of TTUCB (Theorem 2.3 After showing the required properties for the UCB leader, we proved that tracking Top Two algorithms have similar properties as their sampling- based counterparts.
Theorem 2.3. Let (6, 8) E (0, 1)2, 8 and a > 1. Using the threshold (2) in ① and gu (or gm) in B3. the TTUCB algorithm is 5-correct and asymptotically B-optimal for all pa R such that mingz |14 M4 > 0, i.e. it satisfies lim sup Ep / log((10) S TTz (p).
Theorem 2.3 and guarantees for other Top Two algorithms hold only for arms having distinct means. Moreover, an asymptotic result provides no guarantees on the performance in moderate regime of 8. We address those two limitations.
Non-asymptotic upper bound Theorem 2.4 gives an upper bound on the expected sample com- plexity holding for any 8 and any instance having unique best arm. It is direct corollary of more general result holding for any B E 1). > and 1 (Theorem D.4).
Theorem 2.4. Let E (0, 1). Using the threshold ( in ① and gu in 3 with $ = a = 1.2, the TTUCB algorithm with 9 = 1/2 satisfies that, for all μ R such that (p]==1, 1,
[ya(ra] wo wo
inf -1)-1 max (To wo), C12 Co(()) (2/e)12) + +2K,
where C₁ h1 (2)) Co(wo) = 2/ (wo)) + with (0, 1]. To(ō, wo) = sup(n n S 2T/ +) wo) - di (wo) ( (Ve(n c(n 1,6) + (100))/44lgg /4log
with a (wo) (1 (1-
( (mmo) max maax/min,,yvv / (p); 22 and (wo) = Ki # i"
|
wi, / (H); < wo/2]1 The function (z) == zW (log(r) + 2+2K) is positive, increasing for 2 2 2K, and satisfies h (x()) æ(log log x).
The TTUCB sampling rule using 9m in satisfies similar upper bound (Corollary D.5) Since Theorem 2.4 holds for any instance having a unique best arm, we corroborate the intuition that assuming min |14 #gl > 0 is an artifact of the existing proof to obtain asymptotic 3-optimality.
The upper bound [Ta involves several terms. The 8-dependent term is (ō). In the asymptotic regime, we can show that sumsuu (6)) lo//(//))))))))/ I 2T) (1) by taking Wh = and letting & go to 7ero. While there is (sub-optimal) factor 2 in (d), Theorem 2.3 shows that TTUCE is asymptotically 1/2-optimal. This factor a price we paid to obtain more explicit non- -sympttti terms, and removing it would require more sophisticated arguments in order to control the convergence of the empirical proportions N,/ 1) towards w (1))
In the regime where (μ) + +o0, the upper bound is dominated by the o-independent term C122 (when = 1.2) with satisfies C₁ = (()) log (H)). Compared to the best known upper and lower bounds in this regime (see discussion below). our non-as aonmyotmio term has a sub-optimal scaling in ((H (p) log (H))²)) with a > 1. While taking z would mitigate this sub-optimality it would yield a larger dependency in (o )a/(a_1) Empirically, Figures (b) and (Appendix G.2 hints that the empirical performance of TTUCB has better scaling with H (p)) than (u)).
For instances such that min w (H); is arbitrarily small, taking wy = 0 yields an arbitrarily large Co (0). By clipping with w we circumvent this pitfall and ensure that Co(wo) OKKe).
5

---

Table 1: Upper bound on the sample complexity in probability (8) or in expectation (i). The
notation O displays the dominating term when + 0 for the asymptotic regime, and when (())
+oo (or A; - 0) for the finite-confidence one. The notation Ô hides polylogarithmic factors. (*)
Upper bound on E [T&I] (E)] where P[E*] - 7. (**) The asymptotic upper bound holds for instances
having all distinct means, while the non-asymplotic one doesn't It require this assumption.
Algorithm
Asymptotic behavior
Finite-confidence behavior
LUCBIf
24
(H) (1)()
0 (H log H (())
Exp-Gap$
25
(H) (1/8)
0 inti* 4
log log A
lil UCB$
19
(((()))og(1/))))
O Eip A
log log A 1
DKM
Ô (KT (2)2)
Peace
26
((T"(u))og((1]))
O (H()) log A min))
FWSt
42
0 (e H(1)
EBSt 6
log(1//)(16) + o(1)
(H( //au)///mmn)))
TTUCB +*
(3(1) + Olloglog( 16))
(H())) log H())) with a
Since it yields a larger (o))), we are trading-off asymptotic terms for improved non-asymptotic ones. We illustrate this with two archetypal instances. For the "1-sparse" instance, in which fa > 0 and (4s = 0 for all i + 1, we have by symmetry that 20 / (1), = 1/(K - 1) for all i o 1. Therefore, we have Co (wr)
O (K/e) since dy (w)) = 0 for all wi E [0. 1/(K 1)]. The "almost dense" instance is such that [4g = 1, μK = 0 and μ, = 1 - 7 for all i & {1, By symmetry, there exists function h : [0, 1) - [0, (K 1)- with lomy h(7) O, such that ( h(7) and / = (1 h(1))/(KK 2) for all $ {1. While lim Co( = to0, we obtain lim,- Co = (KK/s) by taking wo = (1- (()))(((( - 2) since d, (wo) = 1.
Comparison with existing upper bounds Table I summarizes the asymptotic and non non-asymptotic scalings of the upper bound on the sample complexity of existing BAT algorithms. Among the class of asymptotically (B-)optimal algorithmss, very few of them also enjoy non-asymptotic guarantees, e.g. the analyses of and-top and Top Two algorithms are asymptotic. The gamification approach of [12) is the first attempt to provide both. Their non-asymptotic upper bound on E,, [Tx]] involves an implicit time (6) which scales with KT (11) and is only valid for (og(1/8) 2 (T) (see Lemma 2, with constants in Appendix D.7). Let TV == T* (#)) log(1/)). As a first order approximation, they obtain (5) 2 Tū + O (VTī Tū) and we obtain (d) w e (T + log T (Lemma D.13). 42) were the first to obtain an upper bound on Eg.[Ts] of the form O + log (18)) While they improved the second-orde d-dependent term, the 6-independent term scales with ex exH(n H(1)1997 19/2 (see their Theorem 2 for g-1 2 (w), with constants given by Appendix N). The algorithm proposed by 6 has a non-asymptotic upper bound on [T8 Il (E) of the form (1+))Tz+J[H,, 5) which is valid for log(1/6) Z wm? K/A K/Amin. where& & is such that IP, (EE) < y. Since 0(,,)) =6-0 o(1), they obtain a better d-dependency. However, [(,, 8) is arbitrarily large when Wmin min;eej [K]] w= (μ)) is arbitrarily small since it scales with K (H) 4 //w Therefore, they suffer from the pitfall which we avoided by clipping. In light of Table TTUCB enjoys the best scaling when H (μ)) + +oc in the class of asymptotically (8- (8-)optimal BAT algorithms.
The LUCBI algorithm 24 has a structure similar a Top Two algorithm, with the difference that LUCB samples both the leader and the challenger instead of choosing one. As LUCBI I satisfies [T S 292H(() (p) log(H(M) /5) + 16, enjoys better scaling when H (p) -> too than TTUCB Since the empirical allocation of LUCBI is not converging towards / (11). it is not asymptotically
1 1/2-optimal. The Peace algorithm (26) has a non-asymptotic upper bound on 73 of the form ((TT + 7 (44) (K/ Amin)) holding with probability 1 - ò. The term 7*(n) is a Gaussian-width which originates from concentration on the suprema of Gaussian processes and satisfies y (H)) = ((H()))
Another class of BAI algorithms focus on the dependency in the gaps A Ms. 14. and derive non- asymptotic upper bound on Tş holding with high probability. 25
19
8 gives 8-PAC algorithms
with an upper bound of the form O(H (μ) log(1/8) + Engs A log log A ) and [1 shows that
6

---

for two arms the dependency A 2 -og log A is optimal when A - 0. While those algorithms obtain the best scaling when H (14) +00, they are not asymptotically (3- (3-)optimal.
3 Non-asymptotic analysis
3.1 Proof sketch of Theorem 2.4
Existing analyses of Top Two algorithms are asymptotic in nature and requires much control on the empirical means and proportions to yield any meaningful information in the finite-confidence regime. Therefore,
adopt a different approach which ressembles the non-asymptotic analysis of [12]. We first define concentration events to control the deviations of the random variables used in the UCB leader and the TC challenger. For n >> K, let E,, := [LE[K] (aex)eafto Dee(ne/e (n](E), f n E2,) where
== : (VNe pal < /6log and E2 := (Ju,1 14,)) (u.. -4), > - /ogtt) VI/Ns,5 +1/N,,
Using Lemmas D.8 and E.6 the proof boils down to constructing time T(o) after which En, C (Ta I n for n (6) since it would yield that Ey[ra] I T()) + 12K.
Let > such that &n (n < rH} holds true, and E [n5/6, n] such that BUCB 1*. Using that t S n < Tg. under Niyi- Et the stopping condition yields that
V2c(n 1, 2 (( - HCT)) (1/N) + 1/N (e -1/2 v 8 l)g
Let wi/2 be the unique element of 2 (1)). Lemma 3.1 links the empirical proportions N - -1)
21/2 x for i E fir, C. It the key technical challenge of our von-asymptotic proof strategy.
Lemma 3.1. Let E (0, 1]. There exist Tn > 0 such that for all n > T, such that E, n {n < T8}
holds true, there exists & E [/ .n] with BUCB = i*, which satisfies
(n - 1)( + 1/N(, S (1 + e2 + 1/1 ///
Before proving Lemma 3.1 we conclude the proof of Theorem 2.4
E Tu and f as in Lemma 3.1 n < (n) + e) (V c(n 1,0) + /4log n /3.. For all
and T())= == su
(Z,, we have vc(n - 1, + Alogg 2 v 1 (1) +) Therefore, mT,
we have proved that E,, n (n < }o} 0 for all
This concludes the proof.
Provided that B, 1", the above only used the stopping condition and the TC challenger, and no other properties of the leader. Lemma 3.2 shows that BLCC = i", except for a sublinear number of times. Section (3. exhibits sufficient conditions on regret minimization algorithm to obtain non-asymptotic upper bound.
Lemma 3.2. Under the event MKε[K]] (ne[nere,n) Et we have Lu 2 n 2 1- log 2K.
The key technical challenge is to link N / 1) with "1/2, cte. We adopt the approach used analyze of APT (30]: consider an arm being over-sampled and study the last time this arm was pulled. By the pigeonhole principle, at time n,
Proof sketch of Lemma 3.1
3kg # i", s.t.
Nr. 2 2(Ln, Nº n ).
(5)
n, Using Lemmas 2.2 and 3.2 we show that Ni¹ A. ž wi/2,,, (n 1), hence t1 2 n//0 for large enough
Let 01 be the last time at which BUCB = and CTe ki, hence 11 2 N'*
(see Appendix D.2h. Then, we need to link N to (n 1)/2. When w//.k4 is small, ( can be
true at 4 = 576 hence there is no hope to show that 4 = n - o(n). To circumvent this problem,
we link Ni, to 2,,6, thanks to Lemma 2.2 and use that
n2
n 1
2
Ni NJ
+
< 2(1 + e)2 11/1i
N
No M
No Ki
7

---

for n > (w- with Tu (www)= S max (2/(sw-) + 1). (2 (Lemmas D.10 and D.11). where w- min /1,,,; > lower bounds W This concludes the proof for wi
The (sub-optimal) multiplicative factor 2 in (o) comes from the inequality (6). To remove it, we need to control the deviation between the empirical proportion of arm and wi/2, for all [K].
Nevertheless, TTUCB is asymptotically 1/2-optimal (Theorem 2.3
For we E (0, (K 1) we clip minige w1/2. by wo/2 (see Appendix D Our method can be used to analyze other algorithms, and it improves existing results on APT.
Refined analysis
3.2 Beyond Gaussian distributions
Theorems 2.3 and 2.4 hold for sub-Gaussian r.v. thanks to direct adaptations of concentration results (Lemmas
E.2 and E.5). The situation is akin to the regret bound of UCB: it holds for any sub-Gaussian, but it is close to optimality in a distribution-dependenn sense only for Gaussians. However, if the focus is on asymptotically 3-optimal algorithms, then it is challenging to express the characteristic time T (j²) for the non- non-parametric class of Gab-Gausiin distributions.
The TTUCB algorrthm can also be defined for more general distributions such as single-parameter exponential families or bounded distributions. It is only matter of adapting the definition of the UCB leader and the TC challenger. For bounded distributions, the UCB leader was studied in 1 and the TC challenger was analyzed in 21 Leveraging their unified analysis of Top Two algorithms with our show asymptotic 3-optimality of TTUCB for bounded distributions
tracking- based results, and single-paramete exponential families with sub-exponential tails. We believe that non-asy -symmpttto guaranties could be obtained for more general distributions, but it will come the price of more technical arguments and less explicit non -symmtoti terms.
3.3 Generic regret minimizing leader
Our non-asymptotic analysis highlights that any regret minimization algorithm that selects the arm it except for a sublinear number of times (Property D can be used as leader with the TC challenger.
Property 1. There exists (En), with EnPPLe some y E (0, 1) such that under event En, T.,.i- 2 1 h(n).
too and function h with h(n) O(n") for
For asymptotic guarantees, the sufficient properties on the leader from 21 are weaker since they are even satisfied by the greedy choice B₁ in While Top Two algorithms were introduced by (38) to adapt Thompson Sampling to BAI, we have shown that other regret minimization algorithms can be used: the Top Two method is a generic wrapper convert any regret minimization algorithm into best arm identification strategy.
The regret of algorithm at time n. R., = Ex A,N,, is almost always studied through its expectation E [. This is however not sufficient for our application. We need to prove that with high probability, Nn.5 is small for all arm A it. Such guarantees are known for UCB 3 and ETC [29]. but are yet unknown for Thompson Sampling. We cannot in general obtain good enough bound on Nn.s from a bound on E[R.). However, we can if have high probability bounds on R.,. Suppose that a regret minimization algorithm Alg, satisfies Property 12 and is independent of the horizon n.
Property 2. There exists > 1, 7 E (0, 1), (E,,))(r,s) with Σ,, P. .I < too and function h with h(n, n =) = Onn)) such that under event En,o, Rr S h(n,6).
Let Alg, be the algorithm Alg, used in Top Two procedure, but which uses only the observations obtained at times n such that In Bn, and discards the rest. Let &n En,n - and Amin ming A, Then, under En, Alg, satisfies Eigt- Ni., & h(n, n "))a")AAmnn and Lemma 2.2 yields No,, 2 8(n - 1) - h(n, n n="))"")aa// Amia + K/2+1) + 1)/B. Given a specific algorithm, a finer analysis could avoid discarding information by using Alg, with every observations.
K/2. Therefore, Property holds for &, and h(n)
8

---

3.4 Adaptive proportions
Given fixed allocation B, any Top Two algorithm can at best be asymptotically 3-optimal. Since the optimal allocation 8* arg me0.) T3 (a) is unknown, it should be learned from the observations
by Top Two algorithm using an adaptive proportion In at time n. Recently, [44] proposes IDS to choose Pn in an adaptive manner. For BAI with Gaussian observations, IDS yields 3, = C., Let PA L... -i 3,1 (B, i) be the average proportion when Nn.c./ (N,,,
arm i was the leader before time n. Tracking with IDS requires to use B instead of Using the analysis of [44). it is reasonable to believe that one could obtain asymptotic optimality of TTUCB with IDS. However is not clear how adapt the non-asymptotic analysis since heavily relies on being fixed and bounded away from {0, 1}. Experiments with IDS are available in Appendix G.2.1
Experiments
In the moderate regime (6 = 0.1), we assess the empirical performance of TTUCB with bonus Im and concentration parameters 8 = a = 1.2. As benchmarks, we compare our algorithm with three sampling-basel Top Two algorithms: TTTS, T3C and 3-EB-TCI. In addition, we consider Track-and-Stop (TaS) [17], FWS [42), DKM [12), LUCB (24] and uniform sampling. At time n, the LUCB algorithm computes leader and challenger, then sample them both (see Appendix G.I). To provide a clear comparison with Top Two algorithms, we define a new 3-LUCB algorithm which sample the leader with probability 3, else sample the challenger. At the exception of LUCB and 3-LUCB which have their own stopping rule, all algorithms uses the stopping rule ( with the heuristic threshold c(n, 5) log(( + log /)) Even though this choice is not sufficient to prove 5-correctness, yields an empirical error which several orders of magnitude lower than d. Top Two algorithms and 8-LUCB use 3 1/2. To allow for fair numerical comparison, LUCB and 3-LUCB use /2((n 1, 8), bonus, which is tight yield valid confidence intervals. Supplementary experiments are available in Appendix G
Random instances We assess the performance on 5000 random Gaussian instances with K 10 such that 141 = 0.6 and [4; ~ u( [0.2, 0.5]) for all í + 1. Numerically, we observe w" (p))= s 1/3 + 0.02 (mean std). In Figure [a). we see that TTUCB performs on par with existing Top Two algorithms, and slightly outperforms TaS and FWS. Our algorithm achieves significantly better result than DKM, LUCB, 1 1/2-LUCB and uniform sampling. The CPU running time is reported in Table 4 and the observed empirical errors before stopping is displayed in Figure (Appendix G.2).
Larger sets of arms We evaluate the impact of larger number of arms. The "1 "1-sparse" scenario of 20 sets (41 = 1/4 and 14; = 0 for all / * 1, i.e. H(u) = 32 K - 1) (see Appendix G.2 for other instances). We consider algorithms with low computational cost. In Figure [Tb)), all algorithms have the same linear scaling K (i.e. in (f)). Faced with an increase in the number arms, the TS leader used in T3C appears be more robust than the UCB leader in [TUCB] This common feature of UCB algorithms which have to overcome the bonus of sub-optimal arms.
4.0x10
105
EB
TTUCB
T3C
3x0x
LUCB
1/2-LUCB
Uniform
20x100
10
10x10
10a
10
10
1008
BBHC)
130
1115
45
H4b
Figure Empirical stopping time on (a) random instances (K 10) and (b) "1-Sparse" instances.

---

Conclusion
In this paper, we have shown the first non-asymptotic upper bound on the expected sample complexity of a Top Two algorithm, which holds for any error level and for any instance having a unique best arm. Furthermore, we have demonstrated that the TTUCB algorithm achieves competitive empirical performance compared to other algorithms, including Top Two methods.
While our guarantees hold for fixed proportion / allocated the leader, 44 recently introduced IDS to define an adaptive proportion 3, at time n and show asymptotic optimality for Gaussian distributions. Deriving guarantees for IDS for ungle-parameter exponential families a challenging open problem. Finally, Top Two algorithms are a promising method to tackle complex settings. While heuristics exist for some structured bandits such as Top-k, it would be interesting to efficiently adapt Top Two methods to deal with sophisticated structure, e.g. linear bandits.
Acknowledgments and Disclosure of Funding
Experiments presented in this paper were carried out using the Grid' 5000 testbed, supported by scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see by the THIA ANR program "AI @ Lille". The authors acknowledge the funding of the French National Research Agency under the project FATE KANR22-CE23-0016000
This work has been partially supported
References
[1] S. Agrawal, S. K. Juneja, and W. M. Koolen. Regret minimization in heavy-tailed bandits. In Conference on Learning Theory, 2021.
[2] K. Ariu, M. Kato, J. Komiyama, K. McAlinn, and C. Qin. Policy choice and best arm identification: Asymptotic analysis of exploration sampling under posterior weighted policy regret. arXiv preprint (i.iv:2219.08220 2021.
[3] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration-explootttinn trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19), 2009.
[4] J.-Y. Audibert, S. Bubeck, and R. Munos. Best Arm Identification in Multi-armer Bandits. In Conference on Learning Theory, 2010.
[5] P. Auer, N. Desa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235-256, 2002.
[6] 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.
[7] K. Chaloner and I. Verdinelli. Bayesian experimental design: A review. Statistical Science, 1995.
[8] L. Chen, J. Li, and M. Qiao. Towards instance optimal bounds for best arm identification. Conference on Learning Theory, 2017.
[9] L. Chen, J. Li, and M. Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics, 2017.
[10] H. Chernoff. Sequential design of Experiments. The Annals of Mathematical Statistics, 30(3): 755-770, 1959.
[11] R. Degenne, Impact of structure on the design and analysis of bandit algorithms. PhD thesis, Université de Paris, 2019.
[12] R. Degenne, M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
10

---

[13] R. Degenne, H. Shao, and W. M. Koolen. Structure adaptive algorithms for stochastic bandits. In International Conference on Machine Learning (ICML), 2020.
[14] E. Even-Dar, S. Mannor, and Y. Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, 2002.
[15] 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.
[16] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence. In Advances in Neural Information Processing Systems, 2012.
[17] A. Garivier and E. Kaufmmann Optimal best arm identification with fixed confidence. In Proceedings of the 29th Conference On Learning Theory, 2016.
[18] L. Hong, W. Fan, and J. Luo. Review on ranking and selection: A new perspective. Frontiers of Engineering Management, 8:321-343, 2021.
[19] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. LiI'UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of the 27th Conference on Learning Theory, 2014.
[20] 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.
[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. Kalyanakrishman, A. Tewari, P. Auer, and P. 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 (ICMI), 2013.
[26] J. Katz-Samuels, L. Jain, K. G. Jamieson, et al. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Informa- tion Processing Systems, 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] E. Kaufmann, O. Cappé, and A. Garivier. On the Complexity of A/B Testing. Proceedings of the 27th Conference On Learning Theory, 2014.
[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 on Machine Learning (ICML), 2016.
[31] A. A. Marjani, T. Kocák, and A. Garivier. On the complexity of all e-best arms identification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2022.
[32] B. Mason, L. Jain, A. Tripathy, and R. Nowak. Finding all E-good arms in stochastic bandits. Advances Neural Information Processing Systems, 2020.
[33] A. Mukherjee and A. Tajer. Best arm identification in stochastic bandits: Beyond 8-optimality. arXiv preprint
2023.

---

[34] A. Mukherreee and A. Tajer. Sprt-based efficient best arm identification in stochastic bandits. IEEE Journal on Selected Areas in Information Theory, 2023.
[35] Pukelsheim. Optimal design of experiments. SIAM, 2006.
[36] C. Qin, D. Klabjan, and D. Russo. Improving the expected improvement algorithm. In Advances in Neural Information Processing Systems 30 (NIPS), 2017.
[37] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[38] D. Russo. Simple Bayesian algorithms for best amm identification. In Proceedings of the 29th Conference on Learning Theory (COLT), 2016.
[39] 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.
[40] M. Simchowitz, K. Jamieson, and B. Recht. The simulator: Understanding adaptive sampling in the moderate--onffdeecce regime. In Conference Learning Theory, 2017.
[41] W. Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25:285-294, 1933.
[42] P.-. Wang, R.-C. Tzeng, and A. Proutiere. Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems, 2021.
[43] E. B. Wilson. Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association, 22(158):209-212, 1927.
[44] W. You, C. Qin, Z. Wang, and S. Yang. infommationdirrette selection for top-two algorithms. The Thirty Sixth Annual Conference on Learning Theory, pages 2850-2851. PMLR, 2023.
12

---

A
Outline
The appendices are organized as follows:
Appendix
B gathers notation used in this work.
In Appendix C
study the link between (") and (1) for Gaussian distributions.
The detailed analysis of our non-asymptotic upper bound (Theorem
sketched in
Section
is detailed in Appendix D We also give a non-asymptotic upper bound on the
TTCCB using 9m in (3) (Corollary D.5p. and on uniform sampling (Theorem D.6).
We show the asymptotic optimality of our algorithm (Theorem 2.3 in Appendix
Appendix E gathers concentration results used by the stopping rule (Lemmaa) 2.1 and the
sampling rule.
Implementation details and supplementary experiments are detailed in Appendix G
Table 2: Notation for the setting.
Notation
Type
Description
K μ4 μ 8* T T3 w" ("),,, wz(u) = (iTT))
N
Number of arms
R
Mean of arm E [K]
Vector of means, p ((G)EE(K)
R
[K]
Best arm operator, i (m) arg max;e[K] pi
Ri
Asymptotic ( (f-)characteristii time
Asymptotic (8-)optimal allocation
B
Notation
We recall some commonly used notation: the set of integers [n] == {1, ....... ,n), the complement x-C and interior X of set X, Landau's notation o, O, and O, the (K dimennsioaal probability
simplex 4 := w RK w 2 0, Σee(K] w; } While Table gathers problem-specific
notation, Table 3 groups notation for the algorithms. We emphasize that Ni where we pulled arm leader before time
n, is the number times
Table 3: Notation for algorithms.
Notation
Type
Description
B
K
Leader at time n Challenger time n
Cn
K
T
K
Arm sampled at time Proportion parameter
B
10,1)
X
R
Sample observed at the end of time n, i.e. Nn,s, ~ N(u,, 1)
Fn
History before time n, i.e. F, == (I,, X ". Ins (,) Arm recommended before time n, i.e. in E arg [a Mnzi
in
[K]
T5
N
Sample complexity (stopping time of the algorithm) Arm recommended by the algorithm Stopping threshold function
i
[
c(n, 8)
R
Nn.
N
Number of pulls of arm before time n, Nn,1 := Etenn1 1l (1+ =)
Pa,
I
Empirical mean of arm before time n. Pn,i = N.,; EiE(n-1 X (Ie =i)
Lud
N
Counts of B, before time Ln,s == Etejn-1 (B, =
N
Counts of (Br, It) (i,j) before time No. Ele(n11) 1 (Brr =(i,))
13

---

C
Characteristic times
Let j E DDK such that i" (n) {i*). Let 8 E (0, and w3 be the unique allocation 3-optimal allocation satisfying Wp, > 0 for all i [K] (Lemma C.2 i.e. wz(()) {wz} } where
w((H))== = arg max min (#4. 14)2
H4. 14
arg max min WEAK =B
WEAKME = 170 2(1/3 1/ws)
VI/B + 1/w5
We restate without proof two fundamental results on the characteristic time and the associated
allocation, which were first shown in [38]. Lemma C.1 gives an upper bound on T (p.) (pp)/TT T (1) and
Lemma C.2 shows that the (3- (3-)optimal allocation is unique with strictly positive values. [38] shows that these two results hold for any single-parameter parameter exponential families. [21] extended their proof for the non-parametric family of bounded distributions. Moreover, they argue that these results should hold for more general distributions provided some regularity assumptions are satisfied.
Lemma C.1 (38]
T1)2(1) < 2T (n) and with B wº. (μ))
(u)
1r 1 1-
(n) S max
3 1--33
Lemma C.2 (38) (f((()) singleton and B E (0, 1), then w" (p) and w3 are singletons, i.e.
the optimal allocations are unique, and (1)) and (z(();; for all [K].
Gaussian distributions Since Lemma C.1 is worst-case inequality holding for general distribu- tions, we expect that tighter inequality can be achieved for Gaussian distributions by leveraging their symmetry. This intuition is fueled by recent results of [6]. Using rewriting of the optimization prob- lem underlying (1) (Lemma C,3 they provide a better understanding of characteristic times and their optimal allocations (Lemma C.4). In particular, for Gaussian distributions, Lemma C.4 shows that the optimal allocation of arm 1 is never above 1/2 and is larger than 1/(VK - 1 1+ 1) 2 1/K.
Lemma C.3 (Proposition 8 in (6)) Let μ RK be K-arms Gaussian bandits and r(u) be the solution of (r) = O, where
Vr E (1/min// min(ue iff
pi)3, +00), wp(r) Σ
ig (r(p:- pz) 1)2
and vi is convex and decreasing. Then,
2r(u)
(n) 1+ i4 Mu)Ku=uuss--
Lemma C.4 (Proposition
10 in 6 Let E RK be K-arms Gaussian bandits. For K = 2,
w (w) = (0.5, 0.5) and T (μ) = 8(11 - 22)
For K 2 3, we have
V[VK-I++H S w (H); s 1/2,
and
8
VK -K- (T) 52 (1 VK VK- I)2 1)2
max
min (14- - 14)2
A
min (Pir 11,)2
where 2 K-T Eiggr (Hi 2.)2 In particular, the equalities w (M);, 1/(VK - + 1) and
T T*)x)
miniger (f. -p. are reached if and only if μts = maxi4i 14 for all i fi*. i*:
2(1+K-1)²
By inspecting the proof of Proposition 8 in 66, we obtain directly the following rewriting of (p))). Lemma C.5. Let u R be K-arms Gaussian bandits and (T( be the solution of Pu.s (r) 0. where
1 1-3 3
E (1/ min(u4- - pi)2, +00), (p.o(r) = Σ 871
r(ur- 11)) -
3
and Pp,3 is convex and decreasing. Then,
(p) = 2n²(w)
3
14

---

1.03
1000
102
2.04
5
x1
Figure 2: Ratio of characteristic times (xx)) (x)2(x)TTT( for K (left) and 4 (right).
The dashed blue line is r2 61 + v2)² (left), and the blue point is 13 8/(1 + v3)² (right).
Proof. Using the proof of Proposition 8 in 6. we obtain directly that
27 (1) C²(u)
where Cp(n) the solution $ (C, = where
@ (C) = Σ 171 B(u -1pp:-1))330 -
The idea behind the above result is that the equilibrium, i.e. w", all the transportation costs are equal to C. Then, the implicit equation defining C/ is obtained by using the constraints that Eiee W
3. To conclude, simply use - 3/C.
Since is the sum of K - convex and decreasing functions, Pp,88 is also convex and decreasing.
Lemma C.6 aims at improving the worst-case inequality between (1)) and (*) in the Gaussian setting. For K 2, those two quantities are equal. For K 2 3, we showed that max (1)]=1 (1 (H))(t))TTTMM (n) is at least TK. which is achieved when all sub-optimal arms have the same mean. As the gradient of the ratio is the null vector for those instances, conjecture this is the maximum, i.e. 2 S TT (J)). Our conjecture is supported by numerical simulations for K 3. In Figure [ plot the ratio of characteristic times 2(x) = =T//2//)TTT (μ) for K {3, 4). We observed that our conjecture is validated empirically, and that (1)2())/TT) (p) often close
Lemma C.6. For K = 2, have (M) (H). For K let FK 2K/(1 + VK 1)?.. P.--4 2 for all = 12xx) where x, P.. P3-
Tiz(()) T*(A)
Then, for all such that (1) is unique, we have
i & (ir (",""} with j* arg argminjz4 pe Hy. In other words, Tip(a)) is independent from p4, and T'k)
minj uo Hj. Moreover, we have
Q(1x=2) = =rk and V, = -
Proof. Using Lemma C.4 we have (1)2(()) = T (1) directly for K 2.
we denote by Amin (4) = minayr (Ju- p.)², it is easy to see that (1) = ( when Amin(u) Amin (ū). Likewise, this ratio is invariant by translation of all means by same quantity. Therefore, consider without restriction an instance such that Amin (14) = and with
For 2 3, we want to upper bound (u)
= 0 P22 = - T2 2 ... 2 2pK = -IK
where = and x; 2 for all > 3.
First, we can rewrite
2 1 1/q
1
(T)(())-
max min
max
min f22
4 qEAK-1
gEAx-1
1 1/4 4K
15

---

where the inequality is an equality if and only 2; for all i 22 2. Using Lemma C.4
we know that
(x) 2 + K 1)
and only a = 1 for all i 2 2. Therefore, we have exhibited an instance such that
T1/2(1) (#) (1+VK
2K
Applying Lemma C.5 for 3 3= =1/2, we obtain T1/2(x) = 4x))) where C(x) is the implicit solution of the equation
1
(æ C(x)) =0
where (xxx
1.
C
Cr. -
123
Using Lemma know that
2r(x))
T (')x)
r(z)- + Eis3 r(z)=--1
where r(z) is the implicit solution of the equation
1
(x, r())) = 0 where (2xr)) =
1.
(r 1)2
(rz² 1)2
123
Therefore, we obtain that
1 (T/2(()) 2(x) 2 (x)
C(x) r(x)-1 r(x) (r(s),]
C(x)
and our goal is to show that the above quantity is maximum if and only x; = 1 for all 2 2. One way of doing this is by computing the gradient and showing is negative, which would imply that the function is decreasing. Let 2 3. Using the implicit differentiation theorem, we obtain
ae (x, C(x))
2C(x) (C(x))) 1y2
aC (x) dr,
dz,
ac dz,
20((1x22) K-1
and
(1x-2)
ac (x, C(x))
ag
Σ 123 (c(x)=-11)
(y 1y
and
dr
ibb dzy
[z, r()))
(r(*)2 -1) 1)
2r(xz
and dr (IK-2) 22(1 dx,
(x)
dx; Oe (x,r(x))
113 Σ Ei23 (r(m)a 1
K K-1
Direct computations yield that
à
C(x)
ac Say
(z)(((x) - 1) -C(x) Dr Bay
(x)
θ C(x) (C(())
1 2C(1x-2)
dr, r((x) (((x)-1)
and
(r(x)- - 1
dx, r(x) -1 x=lk-2
K - (r((K-22 - 1)2
and
Oc dzz
(=)(())((())))) C(x) or (x) (2r(x)a -) 20(x)r(z)32
0
C(x) (())((())a) 1)
oz
(1)
0
C(x)
1 -KK-1-1 -1)
2C(1k-2)
(())(r())a)))) 1)
K K-
(r(1x-2) - 1)2
z=lk-2
and, for i 2 3 i #
dz, (W))))(())))))))) ăz, (x) (2r(z) -1)
0 C(x)
((z)(r(z) - 11
dz,
(r(m)(((o)u)-1)) 1))
0
C(x)
1 2C(1x-2)
dz, ((()(((()) - -1)
K-1 ( -1/3
z=lx-
16

---

Then, plugging everything together, we obtained that
an 2C((x-2) 1 1
dzy (1k-2)= (r(1x-2) (r(1xx2) - 1)2 K-1
1+
Σ
0.
K -
i23,4jj
Therefore, we have shown that vQ((K-2) = 0K-2-
D Non-asymptotic analysis
In Appendix D.1
we state and prove one key result for each one of the three main components of the TTUCE sampling rule: the UCB leader (Lemma D.I., the TC challenger (Lemma D.2) and
the tracking (Lemma D.3). The proof of Theorem 2.4 detailed in Appendix D.2, which uses the stopping rule T and a proof method from 30 It is a direct consequence of more general result (Theorem [D.4). Appendix D.3] we prove a non-asympto upper bound for the [TUCB
when using 9m instead of y/u (Corollary D.5). We compare our results with uniform sampling in Appendix D.4 (Theorem D.6). Other technicalities are gathered in Appendix D.5
D.1 Key properties
Before delving in the proof of Theorem D.4jitself, we present the key properties of each component of the TTUCB sampling rule under some concentration event.
Let a > 1 and > 1. Let (Ex)ssk be the sequence of concentration events defined as En :=
Enn n 2 for all K where E1,1 and Ez are defined in (17) and (99)
gu(t) Nr,
Ein=
Ak [K], Vt [n m]. |Mc, 14l VV
(1 +
Egm = wk + i", it, E [nt//a, n], (pi,3 pt,k) - (pi pake) > 2 s)g((()
NN..-
Ne.
with (n) = 2a(1 + s) logn. In Lemma E.6 it is shown that Σn>k P(E s 12(ss)
UCB leader Lemma D.T shows that the UCB leader is different from i* for only sublinear number of times under certain concentration event. It is slightly more general than Lemma 3.2 presented in Section [ which follows from H1 (11) < (1) + 24 min H()).
Lemma D.1. Let (E and as in Lemma E.2 Let H Hi( = Eipirt -.. For all
K, under the event E1,
Vt I [/a n).
Lu, 2 - (t)g K/3,
(6)
Let (Es,a)n and Im as in Lemma
E.3
Under the event E, 66 holds by using 9m instead of 9a.
Proof. Suppose that at time E [/ ml. the UCB leader is different from i", i.c. B, = k # i
Using the event ε and the definition of B, yields
gu(t) No.--
(t( Ne.
4g
14: S M4.5* +
S Pe, +
S uh +
Ne,
We get that if 2 n 1/a, then No, S (Me [N 1 Therefore, we obtain the following upper bound on the number of times the leader is different from it up to time t
4gu(t)
K
K-1
1 (#z- - 24)
4gu(t)
K-1
L-1-L
Σ
LoNS
Σ N
N
S
3
23
23
23
kfis
where we used Lemma D.3 for the second inequality and N S NO k for the third. This concludes the proof for 9u. The same reasoning be applied for gm.
17

---

ТC challenger Lemma D.2 shows a lower bound on the "transportation" costs used by the TC challenger provided certain concentration holds. This lower bound depends only on the empirical counts when the best arm is the leader.
Lemma D.2. For all n > K, under the event Ez, for all t E [n)//,, ml] such that B = i*
V
PL. Pe.k
14.
22x + 8) log
VI/N,B. 1/N2,
VI/NE. 1/NEE
Proof. Under Eg using B, = yields
PL.
Me,
p4: Pk
/20(2 sogg
Pe.
pk
V2a log
BI/NI,B. + 1/N2,
VI/NE5 1/NE,
VINEE + 1/NE
where the second inequality uses that N1, 2 NI, for all *
Tracking Lemma D.3 shows the key property satisfied by the K independent tracking procedures sampling rule. It slightly more general than Lemma 2.2 presented Section
used by the sampling It is a simple corollary of Theorem 6 in [13
Lemma D.3. For all n > K and E [K] we have - -1/2 S No, Blm S and for all l: # i,
3
1
N
2
Ni
3
n,k
21-1 - B
Proof. We can rewrite the tracking condition
B. I 333 as
N.. n.B. - 3L.+1.B. S (Ln+1,8. No, (1 B)
For all E [K]. this corresponds to a two-arms C-Tracking between the leader k and the challengers with wn = (8, - 3) for all n such that B, = k. The leader's pulling count N and the challengers' pulling count is Lat1.B. NB. We recall that C-Tracking was defined as n.B."
T, = arg min Nn, Eleta Wi.k-
Theorem 6 in 13 yields for all > K, - R.B. BL,,B. S 1. The K parallel tracking procedures are independent since they are considering counts partitioned on the considered leader. Therefore, the above results holds for all i [K]. This concludes the first part of the proof.
Direct manipulations yield the second part of the result, namely
1 + Lm,
3
1
Nr.6 S Ln,i NR., S (1 B)L..i 2 and N 2
2
(Nr 8 n.k
2
2
The choice of K independent tracking procedures was made for two reasons. First, independent procedures are simpler analyze for theoretical purpose. Second, independent procedures yields better empirical performance since it avoids over-sampling sub-optimal arm when it is mistakenly chosen as leader. To understand the second argument, let's look at another design with one tracking procedure. Namely we set I, = B,, if Nn,B, Bn, else In Cn. When Bn + it, then it will (almost always) take I, = B, since N,,B, is lower than 3n. On the other hand, when B, & with K independent tracking procedures, both B... and Ln,B, are small, hence it is less systematic.
D.2 Proof of Theorem 2.4
Theorem 2.4 is a direct corollary of Theorem D.4, which holds for any 3 E (0, 1),1 1 and a > 1. and > Using the threshold (2) in and 9u in (3)
Theorem D.4. Let () (0, 1),
the TTUCB algorithm satisfies that, for all p E IR such that ((²(1) 1,
Eu(Ts] S max {To(6), Cg. -o , . C2.
18

---

where
To(o) = =sup n n K n 10--155 13
(1 + E)²
3(1 - wo) (l))d (V c(n 1,6) + a 8) log
2
CN 11 (4a²(1+ H)H(1) Co Eap(wsg +1, C1 11=1/(3)), C2 (2K 1))((s) + +1,
ax(wo) = (1 - wo) (w))dx(u)) max min wz(H); (1 -1- B)wo3, d
= f [K] ((r(H)) I wz(H), < (1 - B)woll,
(M)
with e E (0, 11, wo E 10, 1/K/ 1)] and Ç is the Riemann & function. For all > 0, the function hn (x) = xW- 1 (log(x) + 2+K/#) is positive, increasing for x 2 2 + K13, and satisfies h1 (x) = (log x + log log
Let n K such that e, holds true and the algorithm has stop yet, i.e. &n {n 78). Let t e [n such that B, = i*. Let c(n, 5) as in (2) which satisfies that n c(n 6) is increasing.
Using the stopping rule (I) and t S n < To. we obtain
22e(n- - 1,6) 2 2c(t 1,
min 171
Ma. M4. min BB
(H,,B, 11,+)+ VI/N., + I/N,, VI/N., 1/Ne,c.
(P..8, - -1..))+
VI/N,, + 1/NN,
The last inequality is an equality when B, = b, and trivially true when B, * & since a positive term
is higher than zero (already null when taking = 4)). Using Lemma D.2 we obtain
PrB Mr,C
Pe. P...
22a(2 + s) log
V/N,,B. +1/Ne0.
1/N -1/Ni..
1/B+ 1/ min 6f1"
v 22x + 8) log
1/N - -1/NE,C
v1/3 - 1/W7,,
1/B + 1/8+1/00.00 I/N I/NE..,
M
22z /20(2 + log
where the second inequality is obtained by artificially making appear 1/3 1/w3,0, and taking the minimum of i + i*, The last inequality simply uses the definition of w/""
While combining Lemma D.1 and Lemma D.3 links NE. ((t ((t-t) 1) with 3, we need another argument to compare the empirical allocation Ni,c,/( 1) of the sub-optimal arm C. with its 3-optimal allocation w Before delving into this key argument, we conclude the proof under an assumption that will be shown to hold later: there exists D, and Tμ > such that for all n > T₁. there exists a well chosen E [n///e, .n] with B, = it, which satisfies
Do
1/NE, + I/Nic. n --1 (1/3+ (1/3+1/u4 1/W3,c.)
Let's define
T(5, Do) == sup n > K n - 111 1,0) + v va + 8) log
For all n > max (Tr, T(1, Do)). the lower bound on
VI/N,, +l/N,c, positive, hence we can use that it is upper bounded by / 2e(n - 1,8). Putting everything together, we have shown that
PL.B, PI.C.
Vn > mT,
n - 1 (D (vdn- (,6)= + va(2 - +)) logn
2
Therefore, we have &, n {n < т = 0 (i.e. en C (Ts < n)) for all >
max (7 Da), T(1, Do). Tn) + 1. Using that 8 + T(5, Do) an decreasing function (since CG is increasing), we obtain that T(8, Do) max(T To,,
19

---

Combining Lemmas D.8 and
E.6 yields
[u[Ta] & max Do), T,
+ Σ n21
P (P(()) S má Do), I + +1+ (2K - 1))(s).
At this stage, the proof of Theorem D.4 boils down to exhibiting Dg > 0 and TN > 0 such that: for all Ti. there exists well chosen / [n n]] with B, i and such that 7 holds. As mentioned above, the crux of the problem to relate Ni,, 1) and w².c. To do so, we will build 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 K1 # it such that 5 holds, i.c.
N 2 W
- B (Ln N and we take such ky. Let t1 := sup ft < n (Be, Ct)
be the last time at which i* was
the leader and hy was the challenger. If 1, B1, then t1 = =N else NE = N n.k.
1. In
n,k1*
both cases, we have No" we obtain
k2 2 No 1. Let fi as in 14). Combined the above with Lemma D.9
W3 (Tm No - "3,,, (n 1) - (n))
NE C1
Nr 2,
Let w- > 0 be lower bound on u3 for example consider w- min w3ga. Let
(n2/a + f((m)))
Co(w_) sup 1 n 1 w_
(8)
Since t1 - 1 2 h,, 2 w3 (n - 1) - fi (n), we obtain that f 2 n//a for all n > No(w-).
For instances f such that W3,k, is small, the equation (5) can be satisfied at the very beginning, hence 4 might be sublinear in n. Therefore, while combining Lemma and Lemma y yields Ni 2 B(t - 1), it is not possible to obtain N 2 3(n - 1). Due to the missing link between and n, we use the following inequality
n- NE
N N
+1 +1)-
1/N 1/N
S
n2 1
1/3 +
which is suboptimal step which artificially introduces 1/3, and responsible for the multiplicative factor 1/3 in Theorem D.4 Improving on this suboptimal step is an interesting question, whose answer still eludes us. One idea would be to leverage the information of the sampled arm at time t
since we have N S 33 when = B, = Ie, else NE, 2 BL++15..
Let E (0, 1). It remains control both terms. First, obtain
1/3 n-
< 1/8+
W (n))/(nn1 S (1++) (1/3 1/w3,
for all n>> (w-).. The last inequality is obtained by definition of
(i(w)) sup 1 fi (1+
}
(9)
w-
which ensures that, for all > Ci (w-) ), the last condition the equivalence
f1
1 1 1
W3en - fi(n)/(n 1) 2 (1 (1+ =
1
is satisfied since wa,,, 2 and n Ci(w)). Second, using Lemma Wo (n- - 1) f1(),, we obtain
D.3 with No"
>
-1
N Kr
8
1
+ 1
+ +15 (1
No. N
1-8
2(1 11-3) 3)
kg (n 1) - si(m)) (33,e
20

---

for all n > C2(w-). The last inequality is obtained by definition of
[(((m)+ 1- 1
C2(w-) sup n E In-N n-1< w
(10)
23
which ensures that, for all >> C2(w-), the last condition of the equivalence
B
+1 +15
1 2(1 - B) Wp (n - -1) -i((m)
1
2,38
1
f1(n++
1 + e
1 (n 1) fi(n) _ 1 +E
n - 12
2,3z
satisfied since w 2 w- and n > C2(ww)) ). By comparison between
8 and 10
we notice that
max (Co(w=), (2(ww)} & max (o((o-),
(1 -1-
1 8
2,36
Putting everything together, have shown that taking Do (1 +))3/B, we have for all max K, Co(w-), Ci (w- ). (2(w-)), there exists & [n1/a n] with B,, i" and such that holds. Let hi defined in (15). Since & I 1, using Lemmas D.10 and D.11 with the above yields
(oax( Ci (w-), C2(w))) < max { hi (4a2(1 +8)H(H))
(_2 +1
Ew-- (22+1)
1/(a-1)
B8
Using w- minizi w3z yields the first part of Theorem D.4 the special case of wp 0.
Refined non-asymptotic upper bound When considering large K or instances with unbalanced 8-optimal allocation, min Wy,, can become arbitrarily small. Therefore, the dependency in the is undesired, and we would like to clip it with a value of our choosing which
inverse of min;yr wyz à is away from zero.
Let wg E (0, 1/(K 1)] be an allocation threshold and (ww) == Ii E [K] {+
(1 - 3) | be the number of arms having a B-optimal allocation strictly smaller than (1 B B)wo-
As discussed above, for instances μ such that W3,A, (defined above) is small, the equation (5) can be
satisfied at the very beginning for small empirical allocation Nä* "n,yy To provide a more meaningful result, one needs to have sub-optimal arm k such that either:
Case 1: Wā.kk is not too small, i.c w3 2 (1 B)wp.
Case 2: W3, too small but N k, is large enough. i... Wa < (1 -8)wo and n,K, 2 wol (Lm,,
N n,in).
In case 1, we can conduct the same manipulations above simply by using w- max((1 B)w, min w3.i} instead w_ = min W3,; since it is lower bound for w².K1
In case the above proof also be applied by conducting the same algebraic manipulations with (1 - 33)og instead of W and using w. = (1 - 3) = max ((1 wo: min w3,)- To slightly detail the argument, can show similarly that NY, 2 (1 3)mn 1) S1 [1)). where fi in (4) since we have (1 B)wb < B. Then, for all n > Ci ((1 B)wo))
1/8
S (1++) (1/3+ (1 - (1-3)wo) 3)m 41
(1 (1) (1/3 1/w3,a,
The problematic situation happens when we are neither case nor in case 2:
Case 3: both W2 and Nir wo(Ln,i No n,k, are too small, i.e. wa.n, < (1 - 9)wp and N
21

---

In case 3 it is not possible to conclude the proof with the arm h without paying the price of an inverse of min W.. To overcome this price, we need to find another arm k such that either case I or case 2 happens. Since N and W3,a are small, we will ignore arm kn and use the pigeonhole principle on all arm i E [K] \ {ir, k1). As in (5), obtain that there exists bg such that
WBK (Ln - N n.z- N (1 wo wo) (Ln,i- - No
N n, 2 1 - 3 - 13
1-
where the last inequality is obtained by using 33 > 0 and N wo (Ln,i" N Based on 2 the same dichotomy happens: either we can conclude the proof when we are in case I or 2 or we cannot since we are in case 3. If case occurs also for k2 i.e. Wh,a2 < (1 9)mc and n N n.kk), ). we should also ignore it since is non informative.
N n,,22 <wo,n,, No.
The main idea is then to peel off arms that are not informative, till we find an informative onc. By induction, we construct sequence (ka) (Ka)aeld) of such arms, where ka is the first arm for which either case or case 2 holds. This means that for all E [d - 1J. we have WaRk. (1 B)wo and
N No
<
wo(Ln, - Nor n, Σ
N No,Ko)
BE
lala-11
The construction, which rely on the pigeonhole principle for i E [K] ((it) U (Ka) Jajjaaja)))) yields that li satisfies
(1 wa) - 13 (Ln, No
N n,ka
1 1-3 Eoe(a-1) W3.
(Ln
1,6+
No
1-
aE|d-1]
where the last inequality is obtained since Eaeld-1) W3, 0 and by simple recurrence on the arms (ea)e 1j. Since the arm kn satisfies case or case we can conclude similarly as above. Let ta == sup {t n (Be, Ce) = (i*, ka)}.
When w3 2 (1 - B)wo. the above proof can also be applied by conducting the same algebraic manipulations with (1 (1- wo)dd-- wpp and using
(1 - wo) w d-1 max ( - -B)wo, mintyr w ka 2 (1 - wp) ) - 3, (n 1) - fi (n)), where fi as in (4
In more details, we can show that Nia
since we have (1 (ondd-1wj... <1 B. Then, for all > (ww
1/B + n n-1
1
1+ (1 wn)d-1 (1/8+1/u3,0)
< (1 e)
1/3+ (1 wo) d w U3gka
N ka
This allow conclude the result with Do 3(1 8(-wo))-T:: d- hence paying multiplicative factor of 1/(1 wo)dd1
(1+e)²
When W3 < -1-3)wy F)wp and N n.k, 2 Wo([m, NE n.j. -ue(d-1] Not n.k, ), we conclude my d- 3)uro
similarly by manipulating (1 w B)wo. and using w_
(1-w)) d-1 m1 B)wn, min wz,) First, have Ni 2 (1-wp) d un (n 1) - fi (n)).
where f as in (1) since we have (1 B1 woo--lwo wo < 1 B. Then, for all n > (w
1/3 +
n
< (1 (1+ (1/8+ (1 )d d- B)wb
1
S 1te
+ 1/1 (1 wo)d (
No K
(1te)²
This allow to conclude the result with Do 31-wo))--
To remove the dependency in the random variable d, we consider the worst case scenario where (ka Jaeje-1] (i E [K] {i*} } wp,, < (1- B)wa), i.e. d - S d, (w)). In words, it means that we had enumerate over all arms with small allocation, such that case 2 didn't hold, before finding an arm with large allocation, i.e. satisfying case 1.
In all the cases considered above, the parameters always satisfied w. 2 (1 - wo) (w max (1
3)wo, min 33.3} and Do V 8(1-mo) (acoo) This yields the second part of Theorem D.4 i.e. for wo E 1/ 1)].
(1+t))
22

---

D.3 Tighter UCB leader
While Theorem 2.3 holds for the TTUCB sampling rule using Im and gu. Theorem D.4 is formulated solely for Iu- Experiments highlight that using leads to worse performances than when using Jm- This is not surprising since 9m smaller than Ju-
is direct to see that the proof of Theorem D.4 also holds for Im up to additional technicalities which detail below. As the obtained non-asymptotic upper bound is less explicit, chose not to include in Theorem 2.3
Let and > 1. Let (En) be the sequence of concentration events defined as E, := E3,n 2 for n > K where Es,n is defined (18) as
Im (t)
En
Ak [K], Vt [n ml), Me, Mal V
N
Im (m) W- (2scz log(n) + log(2 log 2)
where (xx) - - W-1(- for all x 2 1, with W-1 is the negative branch of the Lambert W function.
Let n K such that E, holds true and the algorithm has not stop yet. i.c. E {n < TT). Using the second part of Lemma the vast majority of the proof is unchanged. Modifying the definition of fi (14) of Lemma D.9 account for Jm. we define (2(n) == 2H (H)gm(n)/8 + K/S + 2 for all K.
In light of the proofs of the technical Lemmas D.10 and D.II
we can define
Cp = sup fo E N"
x < f2(x")},
and obtain directly Corollary D.5 with the same proof as in Appendix D.2
Corollary D.S. Let (ō, B) E (0, 1)2, E (0. 11. s 1, a > wo 10, 1/(K -1)]. Combining the
stopping rule (T) with threshold (2) and the TTUCB sampling rule using in 33 yields a 8-correct
algorithu such that, for all μ E RK with [1) 1
Em(Ta] max (To(8), Cos Co Co ,,. C2,
where (ō))), Co. Ci and C2 are defined Theorem and
C := sup for E 1" < 2H (1)))m(==)) K/BBBKK/B-0 K/B
(1I)
Explicit upper bound Since Im is itself a non-standard function (like logarithm), it straight- forward to obtain an explicit upper bound on (11). For Ju, it was done in Lemma D.10 10 by using
Lemma D.7
Using Lemma D.7 we obtain that
x (H( (x (x²) K/3 +
x co log
x- Co
2sa log(x) 2og((2 + a²
a22 log xr)
cp
log(t) 2
log(2 + a²
aaaaalooo logæ) + Co
+ saa + 1/2
sa?
log C₁ + C1
801 1/2
2c,
- x 2 h2(Cuu,))
where we used define
c, (2sc C1 logg2saa + 1) sa"+1/2 Cp 2H) co K/B + 2 and
(-o sa² + 1/2
h2(2,z) = z(2sa² + 1)W
ssa2 log
co + log(2 + a log x)) + 01 2=
(12)
For both equivalences above, we used that we are interested in larger values of z, hence used that 2-c6 2 1, on (2sa2+1)
i 2 1, 2sa log(z) + 2ogg(2 + a² log r) + 2 2 1 and
4p
23

---

s02+1/2 ssa logc, cu + ca_ + 1og(2 + a² log + c1 2 Since those conditions are implied by h2((y,,)) 1), those conditions are neither restrictive informative.
26p
Therefore, have shown that C₁ defined in [1] satisfies
Ö S sup (ar N x < h2 (2H()),
where hz) is defined in is such that hg(2. = 2z 221og(2 + a² log and h2(2, x)) R2 2sa²2 log 2.
D.4 Uniform sampling
While the shortcomings of uniform sampling are well known for general bandit instances, is also clear that uniform sampling perform well for highly symmetric instances such that w" (4) R 1x/K Therefore, we derive non-asymptotic upper bound for uniform sampling (Theorem D.6). which allow a clear comparison with Theorem D.4 (and Corollary D.5p.
Theorem D.6. Let ô (0,1). Combining the stopping rule ①T with threshold 2 and the uniform
sampling rule yields d-correct algorithm such thut, for all μ E I&K with 1 (u) 1,
Ey(Ta| & max {
(T)(), hs (mingge (1+- p1)
80 + 8)
)}
+1 1 (2K - 1)((s),
(13)
where hz(x)) xW -1 ([og(()))fee for all 2 e and ha(x) x for all e) and
(6()) = sup { K n 15 min (14- n1)²
4K
2 ]
(Vc(m-L,)+ + v a2 s) log
Proof. Let n > K such that &, holds true and the algorithm has not stop yet, i.e. &, n (n < 78). Let := sup {t E [ne/a, nl (t - 1)/K E N, i =i=). }² Using the stopping rule [ and t S < T8.
we obtain
22 - 1, 2 20(t - 1,8) 2 min iff..
Pe.. PLi
Me, Me.
VI/Na, + I/NO, VI/NNA. + L/N1,
where Ky arg min VI/Ne, +1/NN,, Since sample uniformly, for all time such that
Ho. -ks
(t - 1)/K E N, we have N₁, = (t - 1)/K for all E [K]. Combining the above with Lemma D.2
obtain
22c(n - 1, + 22(2 + log
pa-
min (pg- - 144)
I/N 1/NE.
2K
where the last inequality is obtained by taking the minimum over i [K]. To conclude the proof, simply have to link t with n. More precisely, we will show that n S K -1 and &g = it for n large enough. By concentration, we have
K (t) = pi
(t(t) No. S pa, S4sssm 14t
gt(()
K Kgu(t (t)
#4
p4
No,
t
Therefore, we have Me > maxi Me,s0 i.e. ie ir, for all > N₂ where
(n) := = sup { n1 E n - 15 ming (pr m1)
which means that we have at worse n n < -1 For 2 N₂ + K, we obtain 2 n (K-(K-1) N3.
(aK(1++) Let Cμ min (pg - and = 12/ Assume that cμ 2 e. Using the definition of gu and
Lemma D.7 direct manipulations yields
4K (n))
>
mingee (1i 2²,)2 = x - -log(x)) > log(CH) F > W (loggg(()))
24

---

where the last inequality uses that log(c,) 2 and 2 1, which is not restrictive (or informative) since it is implied by x > W (log(CH)): When Cp < which means that the problem is easy, we have directly that x - log (x)
log(cu) for x > 1. Therefore, the condition becomes x > 1, i.c. n 2 Cu. Defining hr(x) = x w -1 (log x)) for all x 2 e and hz(2)) x for all æ E (0, c), we have
Sa (1 + s)
Na S ha
min;zi (147- 11,)²
Using similar argument as the one in Appendix D.2 which rely on D.8 and the definition of Ti T1))). we can conclude the proof.
The structure of the non-asymptotic upper bound of uniform sampling in (3) is similar to the one for the TTUCB sampling rule in Theorem D.4 Therefore, we can compare the dominating terms for both the asymptotic and the non-asymptotic regime.
First, we look the asymptotic dominant term, namely we compare To( and T1(8). Taking w 1x/ / instead of w" (H) in the definition of T (μ)). is direct see that 7 (1) S min,gp:* (p. -M.
4K
Using Lemma C.1 we have (N) S T* (1) max 88' 1-3"
g 1-3 J where 3 w (n)). Therefore, while
can't say that (1)) 3(1 6(1-wa))k(10 S min (p [4 for all instances μs, empirical evidences
(1+e)²
4K
suggest that the gap is significant for reasonable instances. It even possible to design instances
where the gap between both notion of complexity explodes.
Second, we examine the dominating š-independent term. Using Lemma D.7 we obtain by concavity that for all
2 (log(x)) = (1 (1- ) W (log(z)))
1
0 < h1sz)) S 2W
which yields that lim h1 (x) h2(2)) s While those two functions diverges when - +oc, their difference remains bounded by finite quantity. Therefore, hn and h3 are qualitatively similar. It direct to see that minige (My, -, < (1))= S minggs (p.. -4)² Therefore, while we can't say that 2K
(H(
S
for all instances μu, the gap can become significant for some instances.
minsges (e =
D.5
Technicalities
Lemma D.7
gathers properties on the function W-1 which we used in this work.
Lemma D.7 ((22). Let W -1(x) = W (--e-") f all 2 1, where W-1 is the negative branch of the Lambert W function. The function W -1 is increasing on (1, +20) and strictly concave on (Lo). particular, W' -=(x)) (1
W_((w) (1-wi(()
for all x > Then, for all y 2 1 and 2
W w-1 S
y S x - llg(z)-
Moreover, for all x > 1,
{1
x + log(z) I (-1(x>= s x log(x) + min
2 Vx
Lemma D.8 is standard result to upper bound the expected sample complexity of an algorithm.
Lemma D.S. Let (En)n>K be a sequence of events and T(ő) > K be such that for 2 T()),
E, C. (TB & n). Then, EylTs] < T(8) Σn>k P.(E))
Proof.
E [m([T]]
Σ P nn)
Σ
Pa(T8> > n))
Σ
P.(E)) & T(())
Σ PP a
n<T(
n2T
25

---

Technical results Lemma D.9 shows that a linear lower bound on the number of samples allocated
to the challenger. i.c. Ln N E (1 - (n - 1).
Lemma D.9. Let w E (0, - B) and (E1,n)n as in 17 For all n. E N', under E
w
(In.s- - N n, ) -1 (n 1) fi(n),
- 3
where
[i(m) = 2H()) K/3+2. +2.
(14)
Proof. Using Lemma D.3
obtain that, under Ei,
whng 1-8 w(n 1) 21 ( K/3 2. where the last inequality uses Lemma D.1 for t = n and E (0, 1 B).
(Ln..
Ni.s.)
I-8 3
Lemma D.10 gives an explicit upper bound on the constant Co(w-) defined implicitly in Ap- pendix D.2
Lemma D.10. Let w- > 0 and Co(w-) as in Then, we have
1/(a-1)
Co(w-) S max { (iu (1+++++))))))) (1)+))))))))))
(2 +1 w-
where hy IR4 - R2 is increasing function for 2 2 K/B defined
(1(2) = (log(s) 2 + K/B
(15)
Proof. Using the definition of and Lemma D.7 direct manipulations yields
n 1/a 2 (n) = 1/aa 2 cu log(nn///// + 2 K/B = log(()) 2 dr = x W-
where = n// /cp. dn log(cu) + (2 + k/B)/cu and c₂ 4a (H) For the last equivalence we used that we are only interested in x 2 1 (small values are not relevant for upper bounds). Since W-1 (dn) 2 1, this condition is neither restrictive nor informative as we obtain the final condition x 2 W - (dz). Moreover, we can show
ca (log((e)) - 1) 2 - (2 K/B) = (log((())) 1) -1, where the last part is true since 2 K/B 2 and min x(log(x)) -1) = -1 by direct computations. Therefore, for all n 2 h1 have
2
a/(a-1)
1 nn (n + - 1 w-
2 n1 1/a
2 +1
= 12
= 2
Given the definition of Co(w=) as in Since - W- (z1 is a positive and increasing function, i.e. W ( > 0 and W -1 (x) > 0,
S). this concludes the proof.
sufficient condition for h to be increasing is to have f : x - llo((z) + 2+ increasing since
W - -(f()) > W (f((x)) > 0and f' (=m 2 0.
Since f'(x) = 1- 2+K/3 we have that hn is increasing for 2 2 + K/3.
Lemma D.11
gives an explicit upper bound on the constant (w defined implicitly in Ap-
pendix D.2
Lemma D.11. Let w. > 0 and Ci (w as in 9 Then, we have
1/(a-1) 1)
(1+ w-
Ci(w=) max h1 s1)
+1
26

---

Proof. Using manipulations conducted in Lemma D.10 h1 s)) (2)33)²
we obtain that,
for
all n
fi(m) 71 12
(1+
1-12 1 1/e 1/a
(++ w
a/la-1)
+1)
w
W
Given the definition of C₁ (w-) as in D. this concludes the proof.
Lemma D.12 gives an asymptotic upper bound for times that are defined implicitly. For example, can be used with To (d) and Ti (6) defined in Theorem D.4 and Theorem D.6
Lemma D.12. Let C > 0, D > O, c(n, 6) as in
and
T()) = sup
NO n n-150 Vdn- 1,8) + D log
Then, we have lim sups-0
T(6.C) [1/6] S C.
Proof. Let 7 > 0. Direct manipulations yield that
n --150 V c(n 1,8) + vD 2
1
K K-1
(vn logn
4log (4 4 log 2/) s 2CCG
2
log
(
20
K (x-1)
n
Co
log
(88)
for n > Ny
1 7
2
where N, sup {
E N*
VCDllgnn 4log (4 log 2) > (1 + 7m). There-
fore, we have
2C
Co (5 log
(KT²))
K
C(,,C) S N, +1
1+7
Using that Ca(x) so x + log(x) (Lemma E.1 we obtain directly that, for all y > 0,
C)6,C) lim log(1/5)
C
6-+0
1+7¹
which yields the result by letting Y go to zero.
Lemma D.13 gives a non-asymptotic upper bound for times that are defined implicitly. For example,
when considering the idealized choice c(n.0 5) log(1 (1/5), it can be used as first order approximation of To)) and Ti (8) defined in Theorem D.4 and Theorem D.6
Lemma D.13. Let C > O, > and T()) = sup fn N n 1 & C'log(16)) + D logn) Then, we have
T(ő) < DW -1 C D
log(1/5) + 1/D + log D)
for log(l/)))) 2
D-Dlog(D)-1 else T(8) < D.
C
Proof. Direct manipulations yield that
- log(1/0) + cD + n> DW
C
(C log(1/8) cD
CC
12 C'log(18)) + Dlog > y y- y-logy'
where y - n/D and cD = 1/D+ log D. For the last equivalence, we used that C log( 1/0) + 21 if and only if loog 8 - cp) D-Dlog(D)-1 When & log(1/0) + cD < which means
C. that the å parameter is large, we have directly that y - log > $ (og((188 (18)) + ep for y 2 Therefore, the condition becomes D.
27

---

E
Concentration
The proof of Lemma 2.1 is given in Appendix [.1 In Appendix H.2 show concentration results for the UCB leader (both with Iu and Jm) and the TC challenger.
E.1 Proof of Lemma 2.1
Proving 5- e-correctness of GLR stopping rule is done by leveraging concentration results. In particular, we build upon Theorem of (27), which restated below. Lemma E.1. Consider Gaussian bandits with means E RRK and unit variance. Let S S [K] and
O.
Nn,k (un.k 2x) Σ
(15)
Pe B Σ
2log (4 + log (Nv,,)) + |S|Co
[5)
KES
where CG is defined in 127 by Ca(xr) = minxe]1/2.11 (A)+ and
20 gc(A) = 2X 22 + log ((2A)
log(1 - x)
(16)
where Ç the Riemann function and Cx( + log(2r).
Since in (Wa), standard manipulations yield that for all l: + in
(Mm,s. k2, inf (Nu,,, (Mn,i. u)² Nn,k(Hn, u)²) inf (Nn,a (Pazo - x)²² Nu - -y)
Nu.in No,k
WER
y2z
Let (H). Using the stopping rule ① and the above manipulations, we obtain
Pg (Ta < +00, iro # it)
PM In N, 3i + i", i == (Mn),
min inf (Nn,(umn,t - xx)² + Nn, - -1)²) 2 2c(n 1,
ke w22
Nui
(Mmns u:)² + Nn.² 2
< Py 3n E, 3i + i = i (pm))
(Um,s -mx.)² c(n 1,6)
2
Pμ 3n N, Nua (um, 1s)2
Nn.
(Mn,i" 11r) c(n - 1,
where the second inequality obtained with (k, x. v) = (i* Mi, (bs and the third by union bound. By concavity of + log(4 + log(z)) and Nn, + Nn.i S [ Nn
1, we obtain
Vi * r" log(4 + log Nn,;-) + log(4 + log Nn.)) I 2 log(4 log((n 1)/2))
Combining the above with Lemma E.1 for all i + it, we obtain PA (7a < +00, i =-) z
Σie
K- K-- 0
E.2 Sampling rule
In Lemmas and we prove that the UCB leader using Iu and Im is truly an upper confidence bounds for the unknown mean parameters, when certain concentration event occurs. Then, when another concentration event occurs, we show a lower bound on the "transportation" costs used by the TC challenger in Lemma E.5 Lemma E.6 upper bounds the probability of not being in the intersection of the two above sequence concentration events.
UCB Leader Lemma E.2 proves that the bonus fa is sufficient to have upper confidence bounds on the unknown mean y for Gaussian observations. The proof uses a simple union bound argument over the time.
Lemma E.2. Let 1 lnd s L. For all n > K, let gu gn(n)) 22(1 + (ng(n) and
Ju (t)
Ein := wk E [t] e in 1/a n], |PL. - Hkl <
(17)
N₁
Then, for all n > K, P(E S Kn
28

---

Proof. Let (X))sejn) be Gaussian observations from one distribution with unit variance. By union bound over [K] and using that n S t", we obtain
2a(1 log((t)
IP
3k E [K], 31 E [nt// ml], IoL -uxl 2
Nr,
2(1 8) log(n)
Σ kE[K]
P
E [nt/a, nl], I - unl 2
Nr.
2(1 + 8) log(n)
Σ kE[K]
P
3m E [n|]
X
m +E(m)
m
1
2(1 + 8) log(n)
P
X
m
[ me(n)
sE mmmm
(1+s) Kn
k
mE(n]
where we used that Pr,k pi observations.
Ni E.e 1 (L, k) X and concentration results for Gaussian
Lemma proves that the bonus Im is sufficient to have upper confidence bounds on the unknown mean 1 for Gaussian observations. The proof uses a more sophisticated argument based on mixture of martingales.
Lemma E.3. Let a > and > 1. For all x 2 1, let W -1)) = W-1(-e-") where W-1 is the negative branch of the Lambert W function. For all K, let gm(())
W -1 (2sa 2 log(2 a logn) + 2) and
Eg == -Yyk [K] E // n], M - -uel <
Im (t)
(18)
N
Then, for all n K, P(EE.)) Kn
Proof. Let (Xx)se(() the observations from a standard normal distributions and denote S Eeery X,. To derived concentration result, we use peeling.
Le > 0 and D log(n) 1. For all E [D]. let 7: [og[1+n)
0 and N; (1 r)) For all i [D],
define the family of priors fN. (I) v N.N4 exp
with weights w; 1 and process (-=2g 2
M(1) = Σ wi f INNN (x) (x) KE(D]
1 JS:; 2
_ dx,
which satisfies M(O) 1. It is direct to see that Mtt exp (xS; 2222)) is nen-negative martingale. By Tonelli's 's theorem, then (t) is also non- non-negative martingale of unit initial value. Let i E [D] and consider / E [Ni, Ne+1). For all x;
/ N
(x) 2 V 2 (1)())) V1+1 A Senv(()
Direct computations shows that
/ Jen (x) exp (xS, -
1 _121 dx
S 2(1 + x1)t
exp
V1+7
29

---

Minoring (t) by one of the positive term of its sum, we obtain
1 JN
S 2(1 + 7:)t
M(t) 2 D 71 exp
Using Ville's maximal inequality, have that with probability greater than 1 - 6, log M(t 1 log (1/8). Therefore, with probability greater than 1 6, for all [D] and t E [N,,NN+1)
St S (1 (1) (2log (1/6) + 2 log D log(1 + 1) + log(1 + +
Since this upper bound is independent of t, optimize it and choose % in Lemma E.4 for all i E [D].
Lemma E.4 (Lemma A.3 11) For a, b 2 1, the minimal value of [(n) = (I ))) attained at rt" such that f(n)) s 1 - b W 1 + b). Ifb 1, then there is equality.
Therefore, with probability greater than 1 - 8, for all i E [D] and Ne41),
W-1 -1 (1 + 2lo (1/6) + 2log D log(1 17))
$ -1 (1 + 2 2og (1/6) + 2og (Iog(1 + 7) + log n) - log log(1 + 17) + +og((1 + 7))
W log (1/6) + log (2 + log m) + 2)
The second inequality is obtained since D) + loz
Tog(I+9) The last equality is obtained for the choice
17t =² - 1, which minimizes log(1 + 17) 2 log (log(1 n)). Since [n]] S USe[D)][A [N, N441) and Ne,KMMER mk) Exe(Neal X,,k (unit-variance), this yields
31 n2 Σ X, V W-1 (2lgg(1/)) 2og log(n)) - -2logg) S8.
Since 3 log s 2 and W is increasing, taking - and restricting [n n) yields
3m e |n ml), //. |mm, pal 2 W - (2s (og())(m) + 22 log(n)) + +2) S
Using n < m and doing a union bound over arms yield the result.
TC challenger Lemma E.5 lower bounds the difference between the empirical gap and the unknown gap.
Lemma E.5. Let > and s 1. For all n > K, let
(N1,- + Nox
E2,1 =
4k tt it, [nt/a,n) n), (pe,5 me,x) - (pir (4)) > -V 2a(2+ + 8) log(t)
Ner
(19)
Then, for all n K, P( S (K 1)n
Proof. Let (X.) Ke)sejn) and (Y,) (Y))am()) be Gaussian observations from two distributions with unit vari- 1. m2
ance. Then Dm X;
bi Y, is Gaussian with variance 1_ + ma By union bound and
me
30

---

using that n2 I t", we obtain
P 3k # i", At E [nt/a, nl, (pr.s- - -1.k)) - -K) S - 22 + 8) log(t)
VI/Ne, + 11/N18
(W4,5- - MeNN - (p1- (0:---A -MK)
D1 E (n ml..
S 12(222222 (0(0(())
VI/N2, + +1/Nek
1. E X, 1 E Y
3(m1 |n|?,
< -22(22 + 5) log(n)
V//m + 1/m2
kydht
Σ
P
X;
Y - 8) log(n) (1/m1 + 1/m2)
m1
m2
leghis E[[n]
i=1
i=1
Σ
n (2+6)
=KK- 1)n
light* mm)]//))
where
we used that (M4.5 )4+) - (Me, 1k)
1 E.=1 1(, it) X
N
1 N1A E. 1 (I, = Xs,k and concentration results for Gaussian observations.
Using mixture of martingale arguments, we could improve on Lemma E.5 similarly as Iu improved on Im- This will impact second order terms of our non-asymptotic theoretical guarantees, at the price of less explicit non -symmtyptooiic terms.
Concentration event events.
Lemma E.6 upper bounds the summed probabilities of the complementary
Lemma E.6. Let [ the Riemann Ç. function. Let K, (E2,))n2 and (E3,n)n2K as in and (18 For all n >> K, let En = Ei,n E2,0 and En = Es,n n E2, Then,
max Σ
P(E)),
Σ P(ER)) n>K
< (2K 1){(s)
nz K
Proof. Using Lemmas E.2 and B.5
direct union bound yields
Σ
PPEE)
P.E - PE S
Σ
C(2
1)n=* (2K 1)((s).
BEN
n
nEN-
The same proof trivially holds for En by using Lemmas
E.3
and
E.S
F Asymptotic analysis
Based solely Theorem D.4 it is not possible to obtain asymptotic 8-optimality due to the multiplicative factor 1/3. Building on the unified analysis proposed in [2I), we prove Theorem 2.3
Our main technical contribution for this proof lies in the use of tracking instead of sampling. Given that the cumulative probability being sampled is the expectation of the random empirical counts, it is not surprising that rrakkig-baseed Top Two algorithms enjoy the same theoretical guarantees as their sampling counterpart. As we will see, the analysis to obtain similar result is even simpler (Lemmas [.6
F.8 and F.10). Apart from this technical subtlety, the proof of Theorem 2.3 boils down to showing that the UCB Teader satisfies the two sufficient properties highlighted by previous work (Lemmas F4 and F.7)
Using the fact that x + /2. is increasing, is direct to see that the TC challenger coincides with the definition used by 33 21) i.c.
arg min (Kn.B,, (n.i)+ min (Mm, (nn)) (Mn,B, Pm,s)² B,
TC
VI/Nn,B. + 1/Na,
2(1/Nn,B, 1/Nn.))
31

---

F1 Proof of Theorem 2.3
Let μ DK such that min, mM; Hy and let i" (p) be the unique best arm. Let 3 E (0, 1) and wa be the unique allocation 3-optimal allocation satisfying wp, > 0 for all i E [K]
(Lemma C.2 i.e. wz(u)= = {w3) where
wz(u)= = arg max mil
(H:. 14) 2(1/B 1/ws)
Imi =EAK
arg Max
H4. 14
VTBB + 1/ws
WE Mo mg
Let >> O. Following 36 39 21,. we aim at upper bounding the expectation of the convergence time T3. which random variable quantifies the number samples required for the empirical
allocations Nn/(n - 1) to be s-close to wz:
T inf { T ( TT
Nn n
W/
S {EJ
(20)
Lemma F.1 shows that a sufficient condition for asymptotic 8-optimality is show E [1']]] +o0 for all small enough.
Lemma F.1. Let (8,3) 8) E (0, Assume that there exists (μ) > O such that for all (0,e(())
[T3] < +00. Combining the stopping rule ①1) with threshold as ② yields an algorithm such
that, for all p E TRK with li (1x)
[T(
lim sup 8-0
log (1/5) S Tz(u).
Proof. While the first result in the spirit of Lemma F.1 was derived by [36 for Gaussian distributions, proof holding for more general distributions is given by Theorem 2 in 21 The sole criterion the stopping threshold is to be asymptotically tight (Definition F22)
Definition F.2. A threshold e N x (0. 1] R,, is said be asymptotically tight if there exists
00, 1). &0 E (0, 11. functions S,T: (0, 1] + R and C' independent of 8 satisfying: (1) for all 8E E (0, do] and
(5)), then c(n,8) S [(0) + Cn (2) lim sup ((6)/ (06(1 S and (3)
lim sup5 / log(1/0) 0.
Since CG defined (16) satisfies CG R x + log(x), ) it direct to see that
{ log
(+5 8 (K-1)
K
)) + 4log (4 + log 7/)
c(, = 2Cg
is asymptotically tight, e.g. by taking (a, do, C) (1/2, 1, 4), f(8) 2Cg log (krl)) and
T(6)= = 1. This concludes the proof.
Throughout the proof, we will use concentration result of the empirical mean (Lemmal F33 Since this is standard result for Gaussian observations (see Lemma of (36)), we omit the proof. Lemma F.3. There exists a sub- nab-Gaussian random variable W, such that almost surely, for all i E [K] and all n such that No.i 2 1,
logle NN.i)
|nn Hul S. W
Nn.i
In particular, any random variable which is polynomial in W p has finite expectation.
Sufficient exploration To upper bound the expected convergence time, as prior work we first establish sufficient exploration. Given an arbitrary threshold L E IR, we define the sampled enough set and its arms with highest mean (when not empty) as
s = (i E [K] No. 2 L} and Is = arg max 14
(21)
ie SE
32

---

Since min 114 Myl > 0, I, is singleton. We define the highly and the mildly under-sampled sets
U = (i E [K] N < VT. and V (i [K] NA.; < 1.94).
(22)
21 identifies the properties that the leader and the challenger should satisfy to ensure sufficient exploration. Lemma F.4 show that the desired property for the UCB leader defined in with bonus Iu (n) = 20x(1 + 8) log or
gm(n) = W-1 (2scr log(n) + 2 2og(( + a log + +
Lemma E4. There exists Lo with E Loo) 9] n {at most polynomial in L) such that S + BucB E Sh implies BUCB E In and BUCB arg max pn...
< +oo for all a > such that if L 2 Lo. for all
Proof. Let O and Aii minsys 1i4 Myl. Let denote either 9n. 9m Let 2 Lo. where Lo will be specified later, and (at most polynomial in L) such that S # 0. Then, there exists polynomial function P such that n S P(L). By considering arms that are sampled more than I, we can show that for all l E S% I
g(n)
log(e + Nn.k),
+ g(P(L)) I.
log(e + L) 1 I.
g(P(L))
pank +
Nu,k S pu
W
us + W
+
pu + 28,
Nn,
where the last inequality is obtained for L Lo with
Lo sup LENT Way
log(e +
g(P(L))
1+L
L
Since W -1(()) x log(x)) both Iu and Im have logarithmic behavior, hence (P(()) = (L). Since To is polynomial in W Lemma F.3 yields [,)o()))))) < +oo for all a > 0. Moreover, for all h E In
Pn,k + g(n) Nn, 2 us - WMY w
log(e + Nn.k) Nn, 2 pk W
log(e e L)
2 1ik -
+
Assume that BUCB Sh and that B Т. Since BUCB = arg max
Mn,k
N.,a
g(a)
taking e < Aman/3 the above yields a direct contradiction.
We the proof of (1 to obtain Lemma H.5 While their result accounts for the randomization of the sampling procedure, the argument is direct for tracking since it removes the need for a concentration argument.
Lemma F.5 (Lemma 19 in (21). Let J+ arg maxieve ps There exists L1 with [L][ < +00
such that if L 2 L, for all n. (at most polynomial in L) such that U + 0, BUCB & V implies CHT E V U (Ir (BBCB)),
sampling rule. It builds on the same reasoning than the one used in the proofs introduced by 39 and generalized by [21].
Lemma F.6 proves sufficient exploration for the TTUCB
Lemma F.6. Assume minj |p: Ht > 0. Under the TTUCE sampling rule, there exist No with [No] < +o0 such that for all n 2 No and all i [K], N..i 2 Vn/K.
Proof. Let Lo and L1 as in Lemmas F.4 and Therefore, for 2 L2 = max L1, Lg 4/3 for all n such that U. + 0, BUCB E V.L or C. E Vi since [Jt = implied by minj ini - W >
We have E,, [2] < +oo. There exists deterministic L₃ such that for all L > Ls, L > K 3/4
Let L L2, L1).
Suppose towards contradiction that UL KT.j is not empty. Then, for any S S [KL]. U. and v are empty well. Using the pigeonhole principle, there exists some [K] such that
33

---

MaJ, L3/4, Thus, we have //2/ K Our goal is show that V [26]
K 2. A
sufficient condition is that one arm in Viz is pulled at least 1,3/4 times between [L.] and [2L_] 1.
L3/4 Case 1. Suppose there exists E [2] such that 1161,1-11111 2 3. +3/(23). Using Lemma D.3. we obtain
No 22, Mig 2 [[112_], - 1. 1. -3/2 1,3/1
hence is sampled L times between [7] and [2L] - 1.
Case 2. Suppose that, for all E Vit. I 1222, L.b,, 1./4
3/8)) Then,
3
L//4
Σ
- 2 (12L) - -[1] K
{ B
+ (23)
(2)
Using Lemma D.3
we obtain
Σ
(N 111 B B Σ (Llra [(1a))
53(K -1//2.
FEVE
Combining all the above, obtain
Σ (Lrazsa - [(oja)
Σ
(N¹ 221, ((bja)
2 (1-B) Σ (L LLAJa) 3(K 1)/2
(EV(22)
- (LJ)- K L3/4
(1- ([2b)-[4)
+3/(23)) - 3(K 11/22 KLM/4,
where the last inequality is obtained for T.5 with
Ls = sup LENIC (1 (1-B) B) (122
- LJ) K
(1/) + +3/(23)) ))
1.3/4
3(K 11/2 < KT3/4
The Lh.s, summation is exactly the number of times where arm E sampled, hence
L was leader but wasn't
[2L]
Σ 1 B
E Vi 4 = =C=C 2 KL3/4
[=
For any [L] I t 1 [2L] - 1, U. is non-empty, hence we have BUCB E [L] S V77 implies Therefore, we have shown that
CHC E VL Vi.-
221-1
122|-1
Σ (IEVV))
Σ 1 (BUCB
E V I, = cTC) > KI33/4
[=|+
1=|
Therefore, there is at least one arm in 1 that is sampled 3/4 times between [L] and [2L] 1.
In summary, we have shown [2L] < K - 2. By induction, for any S k S K, we have
Viky s K - k. and finally UL
0 for all L. 2 Lg. This concludes the proof.
[KL]
Convergence towards B-optimal allocation Provided sufficient exploration holds (Lemma F.6).
[21] identifies the properties that the leader and the challenger should satisfy to obtain convergence towards the B-optimal allocation w Lemma F.7 show that the desired property for the UCB leader
defined in
S with bonus gu (n) = 2a + s) log n or
gm (n) W (2sa log + 2 2oog(2 + a logn) 2)
34

---

Lemma E.7. There exists N1 with E < +oo such that for all n 2 N1. _ (1)
Proof. Let A = minger lap. pul. Let denote either Iu or Im. Let No as in Lemma N2 (to be specified later), we obtain for all k + it
F.6 For all
g(n) Nn,
log(c + Nn.k) Nn.
+ K/44
g(n) Vn
log(e + T K4/4
g(n) Vn
Kn +
S ps Way
I mr + W
I pr
22
1+ V
where the last inequality is obtained for n 2 N1 where
N1 = 1 sup E No W log(e V V
g(n)
E, K1/4
Vn
Since W-1(2) (x) re x + log(z), both Iu and Im have a logarithmic behavior, hence g(n) =n-+00 yields ((N))))) < +oc for all a > 0.
o( o(yn). Since N1 is polynomial in W. Lemma
F3
Moreover
Pmis + g(n)
log(e + Nn.)))
log(e + / K
2 p4: W
2 p4
2 p.: - 8
Nu
1 Nn,
1 1
K
Therefore, taking < A/3, yields the result that BUCB it.
Combining Lemma F.7 with tracking properties (Lemma D.3), we obtain convergence towards the 3-optimal allocation for the best arm (Lemma F.8)
Lemma F.8. Let 0. Under the TTUCB sampling rule. there exists N2 with [N,[ < +oo such that for all n 2 N2.
N (n)
Se.
n
Proof. Let No as Lemma F.6 and C1 as in Lemma F.7 For all max{N1, No). have
Bn i* Let M 2 max No Then, we have Lnni' M and Extr No. M 1 for
all M + L. Using Lemma D.3 we have
Nn.
3
|N n-
+
Lm.i" n n-1
No
2(n - + B
1
2(M 1)
n1
Taking N2 max(/N, 1/2420(M-1) + 1} yields the result.
We can use the proof of (1 to obtain Lemma F9 While their result accounts for the randomization of the sampling procedure, the argument is direct for tracking since it removes the need for concentration argument.
Lemma E9 (Lemma 20 in (21)). Lete > O. Under the TTUCB sampling rule, there exists N₃ with E, [Na] < too such that for all n 2 N2 and + (n),
Nn.i 2 w3, +e
C +i.
Combining Lemma E9 with tracking properties (Lemmaa D.3). obtain convergence towards the 3-optimal allocation for all arms (Lemma F.10).
Lemma F.1. Let e > O. Under the TTUCB sampling rule, there exists N4 with [N[] < +oo such that for all n 2 N4.
Nn.t
Vi [K],
w3. S E.
n
35

---

Proof. Let No. C1. N₂ and N3 as in Lemmas
F.6
F77
F.8
and
F9
For all
2
max(NN, N1, N2, Ns), we have BUCB 1* N
B
S and for it.
Nn Nn-1
w3, +
C + i.
Let M 2 max Ni. N2,, N33 and n Ns
max ا=w + 1, M.
Let tn-1,((E)
max {t S n-1 I w3.; + J. Since
N
No F
fort S n, we have --I
No.
Nn,
M 1
<
+
Σ t=M
1 (B = =i, =,,,,"" ,.C = i, Ie =1)
n-1 1
6 +
S W3g, t (BUCB = ,, = I 1=
n -
t=M
N (o)
< +
< w + 2E.
π
As similar upper bound shown in the proof of Lemma F88 we obtain No. x-1 S wg. 2e for all i [K] and all 2 N4 == max N1, N2, N3. No.. Since and w sum obtain for all 2 N4 and E [K].
N n-1
N 2 = n
Σ kedt
(wp.r + 22) = W3g - 2(K 1)s.
kept
Therefore, for all 2 N4 and all i E [K].
N
w
$ 2((K 1)e. Since [p < to0 and
we showed the result for all E, this concludes the proof.
Lemma F.11 shows that E., < +oc, it is a direct consequence Lemma F.10
Lemma F.1. Let 0 and T as (0)). Under the TTUCB sampling rule, we have E. [T)] +00.
Theorem 2.3 direct consequence of Lemma F.I and Lemma
G
Implementation details and additional experiments
The implementations details and supplementary experiments are detailed in Appendix Appendix G.2
G. and
G.1
Implementation details
Top Two sampling rules choose between the leader B,, and the challenger Cn, namely sample B, with probability B, else sample C,,. The difference lies in the choice of the leader and the challenger themselves.
Existing Top Two algorithms are based on a sampling procedure to
TTTS 38 uses a TS (Thompson Sampling) leader and a RS (Re-Sampling) challenger based on sam- pler IT,, For Gaussian bandits, the sampler IT, is the posterior distribution XLe(k) ((nn, 1/N,,i)
given the improper prior I1; (AV(0,+ +oo)) The TS leader is BTS E: argmaxielk 0, where 0 II, The RS challenger samples vector of realizations 0 E II, until B,, arg ma 0g, then is defined as CRS arg max 0g for this specific vector of realization. When the posterior T, and the leader B, have almost converged towards the Dirac distribution on μ and the best arm i" (m() respectively, the event B, & arg max 0 becomes very rare. The experiments in (2 reveals that computing the RS challenger can require more than millions of re-sampling steps. Therefore, the RS challenger can become computationally intractable even for Gaussian distribution where sampling from II, can be done more efficiently.
36

---

T3C [39] combines the TS leader and the TC challenger. B-EB-TCI [2] combines the EB leader with the TCI challenger defined as
arg min B, (n.a) (Un.B. kn,i)² 2(1/Nn.B, + 1/N
C
log((Nn,)).
Br
Since the TC and TCI challenger can re-use computations from the stopping rule, those two chal- lengers have no additional computational cost which makes it very attractive for larger sets of arms.
Each tracking procedure has a computational and memory cost in O(1), hence total cost of ((K)
for the K independent procedures. Each UCB index has computational and memory cost in (11), hence total cost of O to compute BUCB as in 3 Fach TC index (or stopping rule index) has
computational and memory cost in ((),, hence total cost of O(K) compute C as in
Therefore, the per-round computational and memory cost of TTUCB is in O(K).
Other sampling rules At each time πt, Track-and-Stop (TaS) computes the optimal allocation for the current empirical mean, Win = == (Ux)) Given wn, E AA.. it uses a tracking procedure to obtain arm In to sample. On top of this tracking forced exploration is used enforce convergence towards the optimal allocation for the true unknown parameters. The optimization problem defining w" (n)) can be rewritten solving equation 4by (r) O, where
Vr E (1/minn(e min(py ma) t00), () = Σ 1727
igt (r(ws u.)² 1)²
and limy-+1/ min (u:=-au) (v) +o0. For the practical implementation of the optimal al- location, we use the approach of and perform binary searches compute the unique solution of (r) = 0. A faster implementation based on Newton's iterates was proposed by [6] after proving that / convex. While this improvement holds only for Gaussian distributions, the binary searches can be used for more general distributions.
The function the is decreasing, and satisfies 1im (r)
min game between the learner and the nature, and design saddle- point algorithms to solve it sequentially. At each time n, a learner outputs an allocation Wn. which is used by the nature to compute the worst alternative mean parameter X, Then, the learner updated based on optimistic gains based on An-
DKM 12 view (+))
FWS 42 alternates between forced exploration and Frank-Wolfe (FW) updates.
LUCB 2 samples and stops based on upper/lower confidence indices for bonus function g. For Gaussian distributions, it rewrites for all E [K] as
2c(n - 1, Nn.i
2c(n 1,8) Nn.1
Un,i Bai +
and Ln,i Mni
At each time n, it samples in and arg max; Un, and stops when Lnni, 2 max Un. The 3-LUCB algorithm samples i, with probability B, else it samples arg max;ys, Un. The stopping time is the same as for LUCB.
Adaptive proportions optimality conditions for the problem underlying T* (J)). For Gaussian with known homoscedastic variance, IDS can be written as
44 propose IDS, wheih is an update mechanism for 3 based on the
NR.B, dKL (Hn,B., (n Cn))
Nn.C.
Bn Nn.B., dKL (Mn.B., un (B,, Cn)) + Nn,c, dKL (pn.C,, un (B, Cn)) Nn,B,, + Nn.C.
where the second equality is obtained by direct computations which uses that
u, (i.j)= inf (KL, (H,,,15 + Nn. NK. (pm,s Nn.ppnnt + Nn.sttnn PER
Nu. + Nng
37

---

Reproducibility Our code is implemented in Julia 1.7.2. and the plots are generated with the StatsPlots, j1 package. Other dependencies are listed the Readme md. The Readme file also provides detailed julia instructions to reproduce our experiments, as well as script. sh to run EB TCI
them all at once. The general structure the code (and some functions) taken from the tidnabbil l
Table 4: CPU running time in seconds on random Gaussian instances (K' = 10).
TTUCB
EB-TCI
T3C
TTTS
TaS
FWS
DKM
LUCB
Uniform
Average Std
0.14
0.10
0.06
0.82
78.38
7.10
0.40
0.06
0.14
0.11
0.30
0.05
0.65
50.34
9.6
0.30
0.09
0.10
0.6
ITUC3
13C
0.5
ITTS
Ta5
0.4
FWS
DKM
LUCB
00.
LUCB
Uniform
0.2
0.1
0.0
200
400
600
800 1000 1200 1400
Figure 3: Empirical emrors time n < Ty on random Gaussian instances (K = 10).
G.2
Supplementary experiments
Running time The CPU running time corresponding to the experiment displayed in Figure I are reported in Table They match our discussion on computational cost detailed in Appendix G.I The slowest algorithm is TaS, followed closely by FWS and TTTS, All remaining algorithms have similar computational cost: TTUCB, 3-EB-TCI T3C, LUCB and uniform sampling. It slightly higher for DKM.
We emphasize that this is coarse empirical comparison of the CPU running time in order to grasp the different orders of magnitude. More efficient implementation could (and should) be used by practitioners. As an example, the computational cost of TaS can be improved for Gaussian distributions by using the algorithm from (6) based on Newton's 's iterates. However, we doubt that the faster implementation of TaS will match the computational cost of DKM FWS.
Empirical errors before stopping At the exception of LUCB, all the considered algorithms are anytime algorithms (see (3 for a definition) since they are not using 5 in their sampling rule. While all those algorithms are 8-correct, none enjoy theoretical guarantees on the probability of error before stopping, i.e. upper bounds on P Pr f (*))) for 7g. In Figure 3 we display their averaged empirical errors at time n < TJ (i.e. 1l (2, # i")) corresponding to the experiment displayed in Figure Ta [a), with their associated Wilson Score Intervals [43]. To avoid an unfair comparison between a algorithms having different stopping time, we restrict our plots to the median of the observed
empirical stopping time. Therefore, even the fastest algorithm will average empirical errors on at least 2500 instances.
Based on Fi we that uniform sampling and DKM perform the worst in terms of empirical error. At all times, the smallest empirical errors are achieved by 3-EB-TCI, TTTS and LUCB. While iT first bad FWS, its empirical error tends to match the one of the best algorithms for larger time. For TaS and T3C, the trend is reversed.
'This library was created by [2]. see https://bibuccktt.or www.ck/trrgwommooooooii/naaaaaaa No license were available on the repository, but obtained the authorization from the authors.
38

---

3.0x10*
2,0x10*
TONNENE 06
Edhrd
1.0x10*
5-1000
13C
Figure 4: Empirical stopping time random Gaussian instances (K 10): tracking (T-) versus sampling (S-).
Tracking versus sampling The TTUCB sampling rule uses tracking instead of sampling. Since both approaches aim at doing the same with either a deterministic or a randomized approach, it is interesting assess whether they lead different empirical performance. Therefore, compare both approaches for four Top Two sampling rules. Figure 4 reveals that the algorithmic choice of tracking or sampling has negligible impact on the empirical stopping time.
In light this experiment, the choice of tracking or sampling is mostly a question of theoretical analysis. Since the analysis of randomized sampling requires control of the randomness of the allocation, we choose a deterministic tracking for analytical simplicity. Moreover, this choice is natural when both the leader and challenger are deterministic.
10
TTUCB
TTUCB
WUBB
10
LUCB
1/2-LUCB Uniferm
E
Uniform
10
104
10
102 K
10
10
10
K
Figure 5: Influence of the dimension K on the average empirical stopping time (# standard deviation) for the Gaussian benchmark (a) "a 0.3" and (b) "a 0.6".
Larger sets of arms In addition to the results presented in Section we also evaluate the perfor- mance of our algorithm the two other benchmarks used in (20). The "a 0.3" scenarios consider
H4 = 1 for all i E [K], with hardness H(u) 2 3K. The "a 0.6" scenarios consider
for all E [K], with hardness H()) 12K The observations from Figure are consistent with the ones in Figure [b). Overall, T3C performs the best for larger sets of arms.
14
G.2.1 Adaptive proportions
The ratio (1) seems to reach its highest value тк 2K/(1+ VK- for "equal means" instances (Lemma C.6). i.e. ,4 f4- A for all i + i* with A > 0. To best observe differences berween Top Two algorithms with 3 = 1/2 and their adaptive version, we consider such instances with K = 35 (rx & 3/2).
that adaptive proportions yield better empirical performance, with an empirical speed-up close to rk As 3/2. We also compare them with three asymptotically optimal BAI algorithms (TaS, FWS and DKM). Even on those hard instances, Top
39

---

10000
6000
4000
Eb7CI AED-C
T3C
ATC
TRCC
A-TUCS
PM5
DIC
10000
10000
6000
6000
4000
2000
2000
[GRCI AEBRCI
T3C
TRUC0 ATTUCC
PV5
DEM
1640: AE5RC
T3C
ThlO ARTUCA
DKM
Figure 6: Empirical stopping time on "equal means" instances (K, p4r A) = (35, O, 0.5) for (top) 5 = 0.1 and (bottom) {0.01, 0.001]: constant 1/2 and adaptive (A-).
Two algorithms with fixed 3 1/2 are outperforming the asymptotically optimal algorithms for all the values {0.1, 0.01, 0.001}. While being only 1/2 asymptotically optimal, Top Two algorithms (with fixed = 1/2) can obtain significantly better empirical performances compared to existing asymptotically optimal in the finite-coffidence regime. The gap between the empirical performance of the adaptive and the fixed 8 Top Two algorithms is increasing with 8 decreasing. Interestingly, TTUCB appears to be slightly more robust to decreasing confidence 5 compared to other Top Two algorithms.
also compare Top Two algorithms using a fixed proportion 1/2 with their adaptive counterpart using 3n = Nn,C../ (Nn.B, + Nn,c,,) at time random instances.
30x100
2.0x10'
100110
Figure 7: Empirical stopping time on random Gaussian instances (K" 100): constant 3 = 1/2 and adaptive (A-).
Experiments are conducted on 5000 random Gaussian instances with 10 such that μı 0.6 and μ4 ~ (((.22 0.5]) for all of Figure shows that their performances are highly similar, with slim advantage for adaptive algorithms. For instances with multiple close competitors, the same phenomenon appears (see Figure 8 below). This is expected as T (p)/T* TT* (μ) is close to one when
sub-optimal arms have significantly distinct means (see Figure
40

---

4000
3000
3000
2000
Nil
Kird
1000
TTCCE 1670
TDC
1T75
35
TW5
D00
TUC
ATTUCD
AEBRC
13C
1775
APT75
Figure Empirical stopping time on random Gaussian instances (K 10) with multiple close competitors.
Then, assess the performance 5000 random Gaussian instances with K 10 such that 995
106 for all i E {2, 4,5, 5, 6} 995 + 100 for all E (7,8,9) 9, 10] with U(0 1]). Numerically, we observe and A; TO T000
#1 0.6 and = μ41 - A; for * where A, 20 loud
+
"" (n)) R 0.28276 = 0.0003 (mean + std). Both plots in Figure 8 show the same phenomena than
the ones observed Figures b) and
41


Reviews:
[{"review_id": "XLc7ZIyrB4", "reviewer": "Reviewer_WPkC", "summary": "The authors consider the problem of best-arm identification in the unstructured multi-armed bandit problem. More precisely, they study the problem in the fixed-budget setting in the moderate confidence regime. They propose a top two algorithm based on UCB which they call TTUCB and establish that the algorithm is asymptotically $\\beta$-optimal. Here, by $\\beta$-optimal, the authors mean that the algorithm samples sub-optimal arms optimally under the constraint that the best arm is sampled a proportion of times that is fixed at $\\beta$. More importantly, they also provide a non-asymptotic guarantee for their algorithm that is valide for all confidence levels. The authors complement their theoretical findings with empirical results.      \n", "questions": "- In Lemma 3.1, the definition of $D_0$ is not given which, according to Appendix D.2, is equal to $(1+\\varepsilon^2)/\\beta^2$. My first comment is that this needs to be precised in the statement of Lemma 3.1. Secondly, if you were to adaptively seek to achieve the optimal allocation with $\\beta^\\star$, then $D_0$ is not anymore a universal constant and might depend in a non-trivial way on the problem instance $\\mu$, in which case, your proof might not work to obtain a non-asymptotic guarantee. Would this be a limitation of your proof techniques when trying to attain the optimal constant $T_\\star$? I am not sure using IDS might work either. Can you comment on this? \n-  The result of Lemma 3.1, appear to be very specific to the Gaussian case, can the author comment on how can this generalize to the general case?\n-  The authors mention that $ T_{1/2}^\\star(\\mu)\\le  2T^\\star(\\mu)$ in the worst case, can you comment on how tight is this bound? Also according to your experiment it seems TTUCB outperform asymptotically optimal algorithms like track-and-stop and FWS. Does this mean that in the experiment you considered,  $T_{1/2}^\\star(\\mu)$ and $T^\\star(\\mu)$ are roughly the same? Can you run your experiments on a more challenging example where $T_{1/2}^\\star(\\mu)\\approx 2 T^\\star(\\mu)$?\n-  In the experiments section, the authors present plots in a scenario where $\\delta=0.1$. Why is this value of $\\delta$ considered to be in the moderate regime? Is there a clear definition if what we refer to as moderate regime? shouldn't this depend on  the number of arms $K$?", "limitations": "I believe the authors have discussed the limitations of their work accordingly.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Overall, the paper is well written and easy to follow. The related work is well discussed and the proofs appear to be sound to the best of my knowledge.\n- The non-asymptotic study of best arm identification in the fixed confidence setting is a fascinating problem and remains largely unexplored. The authors provide a non-trivial contribution to this problem by shedding some  insight into the non-asymptotic behaviour of a UCB-based TOP TWO algorithm. \n-  The proposed algorithm TTUCB seems to enjoy the best non-asymptotic guarantee up to universal constants universal constants.", "weaknesses": "- The theoretical results are limited to the case of Gaussian arms with known variances. Moreover, The authors only provide a algorithm that is asymptotically $\\beta$-optimal but not asymptotically optimal. This is somewhat unsatisfactory!\n- The authors address the non-asymptotic behaviour of best-arm identification but do not provide any non-asymptotic lower bound. As such it is unclear to me what is the best non-asymptotic bound. In fact, when the authors compare the different bounds, I believe they should also clarify (in the table) that TTUCB has an additional linear dependence on the number of arms $K$ at the finite confidence behaviour. \n-  The authors could provide experiments which exhibit more the finite confidence behaviour of their algorithm in contrast with other algorithms. For instance, experiments that show how the sample complexity varies as $\\delta$ varies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and questions. We hope to address them in the following.\n\n**Only for Gaussian arms with known variances.**\nAll our results hold for sub-Gaussian distributions as discussed in section 3.2. The algorithm can be said to be $\\beta$-optimal in the distribution-dependent sense only for Gaussian distributions, but its sample complexity is bounded for all sub-Gaussians. We discuss distribution-dependent extension of the asymptotic analysis for single-parameter exponential families or bounded distributions in section 3.2.\n\n**Only asymptotically $\\beta$-optimal.**\nAs discussed in Section 3.4, achieving asymptotic optimality with TTUCB is possible by replacing the fixed $\\beta$ by an adaptive choice (e.g. IDS [44]). \n\n**No non-asymptotic lower bound.**\nThe lack of tight non-asymptotic lower bound is one of the main open problems in fixed confidence identification. We don’t solve it in this work.\n\n**Experiments on finite-confidence behavior and varying $\\delta$.**\nOur choice of $\\delta = 0.1$ was made to showcase the performance of the algorithm in the finite-confidence regime. We performed additional experiments for $\\delta \\in \\{0.1, 0.01, 0.001\\}$ on the “equal means'' instances with $(K, \\mu^\\star, \\Delta) = (35,0,0.5)$, see the plots in the  “global” response. We compare three asymptotically optimal BAI algorithms (TaS, FWS and DKM) with three Top Two algorithms (EB-TCI, T3C and TTUCB) for fixed $\\beta=1/2$ or adaptive proportions with IDS. Overall, most algorithms have the same scaling with the confidence $\\delta$. The gap between the empirical performance of the adaptive and the fixed $\\beta$ Top Two algorithms is increasing with $\\delta$ decreasing. Interestingly, TTUCB appears to be slightly more robust to decreasing confidence $\\delta$ compared to other Top Two algorithms. \n\n**Extension of Lemma 3.1 to adaptive choice of $\\beta$, e.g. IDS.**\nWhen seeking to achieve asymptotic optimality with an adaptive choice of $\\beta$ like IDS [44], it is harder to obtain a finite-confidence equivalent to Lemma 3.1. If we were to write the asymptotic analysis of TTUCB with IDS, we would obtain convergence towards the optimal allocation. While this result is stronger than Lemma 3.1, it only holds asymptotically. Obtaining a non-asymptotic result would require controlling the rate of convergence of the empirical allocation towards the optimal allocation. For fixed $\\beta$, tracking yields a $\\mathcal O(1/n)$ convergence of $N_{n,i^\\star} / (n-1)$ towards $\\beta$. Intuitively, having a fixed $\\beta$ allows us to have an anchor and finite-confidence guarantees can then be obtained by reasoning only about the sub-optimal arms.\n\n**Extension of Lemma 3.1 beyond Gaussian distributions.**\nOur proof relies on the specificity of Gaussian distributions. In particular, we use the fact that the transportation costs can be written as the product of a function of the mean gap and a function of the arm allocations. This Gaussian-specific property allows us to decouple the concentration of the mean and the control of the empirical counts. Adapting our proof strategy to other distributions is an interesting direction for future work.\n\n**Tightness to the worst-case inequality for using $\\beta = 1/2$.**\nIn Appendix C, we provide a detailed discussion on the tightness of the inequality $T^\\star_{1/2}(\\mu) \\le 2 T^\\star(\\mu)$ for Gaussian distributions. Lemma C.6 shows that the function $\\mu \\to T^\\star_{1/2}(\\mu) / T^\\star(\\mu)$ has gradient 0 when all the sub-optimal arms have the same mean (which we call “1-sparse” instances). At those points the ratio is $r_{K} = 2K/(1+ \\sqrt{K-1})^2$. Therefore, we conjecture that $T^\\star_{1/2}(\\mu) \\le r_{K} T^\\star(\\mu)$ for Gaussian distributions. In Figure 2 of Appendix C, this conjecture is numerically validated for $K=3$ and $K=4$.\n$r_{K}$ is greatly smaller than $2$ for a small number of arms $K$. For example $r_{5} \\approx 1.1$, $r_{20}\\approx 1.4$, $r_{100} \\approx 1.7$.\nFigure 2 also suggests that the ratio $T^\\star_{1/2}(\\mu) / T^\\star(\\mu)$  is close to $1$ when all the means are different. On the random instances ($K=10$) considered in Figure 1(a), we observed empirically a small ratio $T^\\star_{1/2}(\\mu) / T^\\star(\\mu)$. This explains why TTUCB can perform on par with or outperform asymptotically optimal algorithms such as TaS and FWS. Figures 7 and 8 in Appendix G.2.1 shows that the benefit of choosing $\\beta$ adaptively (i.e. IDS) is mild on those random instances.\nIn Figure 6 in Appendix G.2.1, we show that using IDS yields better empirical performance than using a fixed $\\beta$ for “equal means'' instances. Taking $K=35$ (i.e. $r_{K} \\approx 3/2$), we empirically observe a similar ratio between the empirical stopping time of the Top Two algorithms. We performed additional experiments on this “equal means'' instance with $(K, \\mu^\\star, \\Delta) = (35,0,0.5)$, see the plots in the  “global” response. We compare three asymptotically optimal BAI algorithms (TaS, FWS and DKM) with three Top Two algorithms (EB-TCI, T3C and TTUCB) with either fixed $\\beta=1/2$ or adaptive proportions with IDS. Even on those hard instances, Top Two algorithms with fixed $\\beta = 1/2$ are outperforming the asymptotically optimal algorithms for all the values $\\delta \\in \\{0.1,0.01,0.001\\}$. While being only $1/2$ asymptotically optimal, Top Two algorithms (with fixed $\\beta=1/2$) can obtain significantly better empirical performances compared to existing asymptotically optimal in the finite-confidence regime. \n\n**The moderate regime definition.**\nThe finite-confidence or moderate regime has no formal mathematical definition. Such a definition should indeed depend on $K$ and other problem-dependent quantities. It describes a regime where the $\\delta$-independent term is not dominated by $T^\\star \\log(1/\\delta)$.\nWe took $\\delta = 0.1$ to highlight the performance when $\\delta$ was not too small. \n\n**Miscellaneous.**\nWe will add the definition of $D_{0}$ in lemma 3.1."}, {"review_id": "LVfYgioeg4", "reviewer": "Reviewer_4xLs", "summary": "The main objective of the paper is to establish the first non-asymptotic bound on the expected sample complexity for a Top two sampling policy in the context of best arm identification. To achieve this, the paper introduces a novel algorithm called TTUCB, which is proven to be $\\beta$-optimal in asymptotic scenarios and also satisfies a non-asymptotic upper bound. This upper bound is compared with the existing upper bounds of established non-Top two algorithms. The paper supports its claims with synthetic simulation experiments.\n\nOne notable contribution of the paper is the development of a generic framework that enables regret minimization algorithms to effectively tackle the best arm identification problem while providing optimal guarantees. Additionally, the paper offers guidelines on how other regret minimization algorithms can be adapted to choose a leader at each round. Overall, the paper provides significant insights into the problem of best-arm identification and presents a promising algorithmic solution along with empirical evidence to support its efficacy.", "questions": "1) Could you provide more details on the challenges encountered within the proof technique that led to the decision of adopting a tracking approach instead of randomization in TTUCB? It would be helpful to understand the specific difficulties that arose and how they influenced this decision.\n\n2) Additionally, has there been any simulation-based evidence to demonstrate the comparative performance of TTUCB using tracking versus a randomization-based approach? It would be valuable to assess the effectiveness of TTUCB in comparison to algorithms utilizing random", "limitations": "The authors talk about the limitations and places of potential improvement of the work. Societal impact is not discussed. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper demonstrates exceptional writing, with clear claims and well-defined objectives. It successfully fills a significant gap in the literature by addressing the challenge of providing non-asymptotic guarantees for Top-two algorithms, resulting in original and valuable contributions to the broader bandit literature.\n\nThe problem formulation is thoroughly justified, establishing a solid foundation for the subsequent theoretical results. The discussions on the theoretical guarantees of the proposed TTUCB algorithm are insightful and comprehensive, effectively identifying areas for potential improvement. Additionally, the paper highlights the low computational complexity of the approach, enhancing its practical applicability.\n\nThe upper bounds achieved by the proposed algorithm are comparable to those of well-established methods in the field, as discussed aptly within the paper. By providing relevant comparisons, the paper strengthens the credibility and applicability of its results.\n\nFurthermore, the paper successfully contextualizes its work within the broader scope of the bandit literature, illustrating the connections between the theoretical analysis and the use of regret-minimizing algorithms in the best arm identification problem. This contextualization is particularly valuable as it addresses a scenario that differs from the traditional exploitation-exploration trade-off associated with regret minimization.\n\nOverall, the paper stands out for its clarity, strong theoretical discussions, well-justified approach, and relevant connections, making it a valuable contribution to the field of bandit problems.", "weaknesses": "One potential weakness is the tightness of the upper bound provided in the paper. The proposed upper bound incorporates various parameters and constants. While there is a comparison with the upper bounds of other algorithms, it remains uncertain whether this upper bound represents the best achievable result for TTUCB or Top-two algorithms in general. Further exploration into the tightness of the upper bound would contribute to a more comprehensive understanding of the algorithm's performance.\n\nAnother concern is the exclusive use of synthetic data in the experimental setup, without considering real-world datasets. It would be beneficial to address the potential challenges and limitations of applying the proposed approach to real-world datasets. Discussing any potential issues related to data collection, noise, or other factors specific to real-world settings would enhance the paper's practical applicability and broaden its impact.", "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**Tightness of the upper bound.**\nOur asymptotic bound is the best achievable for an algorithm that samples the leader with a fixed proportion $\\beta$. Using the adaptive choice of $\\beta$ named IDS [44] instead of fixed $\\beta$ will yield an asymptotically optimal algorithm.\nIn the finite-confidence regime. the $H(\\mu)^\\alpha$ dependency stems from the way we define our upper confidence indices. We doubt that better guarantees (with $\\alpha = 1$) can be obtained for TTUCB. This is likely due to the shape of the optimistic index of the UCB part. Designing a TTUCB variant which does not suffer from this limitation is an interesting question for future work.\nAbout other Top Two algorithms, we can say that an algorithm that does not enforce extra exploration like EB-TC will not get good non-asymptotic bounds and has bad stopping time in some experiments. Top Two algorithms can add exploration in various ways: in the leader with a UCB method (ours) or using Thompson Sampling (T3C), or in the challenger like EB-TCI. Since T3C is the same as TTUCB but with UCB replaced by TS, we think based on the general bandit literature that the theoretical guarantees we could prove should be similar.\nWe hope that the tools we are developing will allow us to investigate the non-asymptotic performance of these variants. \n  \n**Synthetic vs real data.**\nOur results hold for sub-Gaussian random variables, hence in particular for bounded distributions, although they imply the strong instance-dependent property of $\\beta$-optimality only for Gaussians.  Therefore, we could assess the performance of TTUCB on benchmarks that don’t use Gaussian rewards. However, since the main focus of our paper is a new theoretical analysis and since the performance guarantees we derive are more expressive for Gaussian distributions, we chose to use this in our experiments. We seek to understand Top Two algorithms in this admittedly restricted setting before generalizing to more real world settings.\n\nWe now answer your other questions.\n\n**Tracking vs Randomization**\nIt is easier to deal with the arm counts coming from a tracking procedure than with their random counterpart. It removes the need for martingales arguments to bound the deviations of the samples, hence it simplifies the analysis. \nTracking also has a better convergence to the target compared to the randomization approach. Lemma 2.2 shows that the speed of convergence is at least $O(1/n)$ for tracking, while we would obtain a speed of $O(1/\\sqrt{n})$ for randomization. In a related field, worse convergence rate for random approaches compared to tracking approaches has been observed empirically in section 7 of Mutný et al (2023, Active Exploration via Experiment Design in Markov Chains).\nIt is not clear however whether this faster convergence is really useful, since the noise in the observations of the algorithm can be the dominant source of uncertainty.\nFor all the experiments presented in Section 4 and Appendix G.2, we compared tracking vs sampling even though we didn’t include the plot. There is no significant difference for the stopping time.\nOverall, tracking or sampling makes no difference experimentally and no significant difference in the theoretical results we can obtain, and using tracking allows us to skip the step of relating the random counts to their mean.\n"}, {"review_id": "wdjBeQ7VO6", "reviewer": "Reviewer_nKF8", "summary": "This paper presents a non-asymptotic upper bound on the expected sample complexity of a TT sampling rule-based algorithm for any error level. Numerical results also verify the performance of TTUCB. This is nice work", "questions": "1. Any comments on how to choose the function $g_u(n)$? Are there any required properties?\n2. Can you provide any suggestions on how to choose $\\beta$ in practice?\"", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and organized. The insights behind the main results are well-presented.\n2. The tracking rule is simple and easy to implement.\n3. I appreciate that the authors include several simulations.", "weaknesses": "One weakness is that there is still room for further improvement in the bound.", "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\n**Further improvement in the finite-confidence upper bound of Theorem 2.4.**\nCompared to our asymptotically $\\beta$-optimal result in Theorem 2.3, we only managed to get within a factor $2$ of the $\\beta$-characteristic time $T^\\star_{\\beta}(\\mu)$ in our non-asymptotic bound (Theorem 2.4). There is definitely room for improvement here, but our result is the first non-asymptotic bound for any top-two algorithm and we had to introduce a new proof technique to obtain it. That technique will surely be refined in the future. While Theorem 2.3 assumes that the means are distinct, Theorem 2.4 is the first guarantee on the expected sample complexity of a Top Two algorithm which doesn’t make this assumption.\nAs regards the finite-confidence regime, we provide a detailed discussion on each term (lines 186-200) and compare them with existing upper bounds and lower bounds (lines 201-229). While there is still room for further improvements in future work, Table 1 shows that we achieve the best known finite-confidence upper bounds among the class of asymptotically ($\\beta$-)optimal algorithms. The lack of a tight non-asymptotic lower bound is one of the main open problems in fixed-confidence best-arm identification.\n\n**Choice of $g(n)$ in the bonus defining the UCB leader in (3).**\nThe only constraint on $g(n)$ is that it should yield valid confidence intervals. Mathematically, we need to have a property similar to Lemmas E.2 and E.3 in Appendix E, for all $t \\in [n^{1/\\alpha}, n]$ and all arms $i \\in [K]$, $\\mu_{i} \\in [\\mu_{t,i} \\pm \\sqrt{g(t)/ N_{t,i}}]$. Therefore, the choice of $g(n)$ is constrained by the concentration results used to control the deviation of the empirical mean to its expected value. $g_{u}(n)$ was obtained with a union bound over time (Lemma E.2 in Appendix E), $g_{m}(n)$ relies on a mixture of martingales (Lemma E.3).\nGiven two theoretically validated choices (e.g. $g_{u}(n)$ and $g_{m}(n)$), the lowest $g(n)$ will yield better empirical performance since larger $g(n)$ means more conservative UCB. That is the reason why we conduct our experiments with $g_{m}(n)$ instead of $g_{u}(n)$ since it is possible to show that $g_{m}(n) \\le g_{u}(n)$ for $n \\ge 50$ when choosing $s=\\alpha =1.2$. Intuitively, $g(n)$ should be chosen small enough, but not too small. For example, in addition to not yielding valid confidence intervals, taking $g(n) = 0$ recovers the EB-TC algorithm which suffers from poor finite-time performances.\n\n**Choice of the fixed proportion $\\beta$.**\nFor fixed $\\beta$, we highly recommend to use $\\beta = 1/2$ without prior knowledge on the unknown mean parameters. This recommendation is supported theoretically with the worst-case inequality $T^\\star_{1/2}(\\mu) \\le 2 T^\\star(\\mu)$, which shows that the expected sample complexity of an asymptotically $1/2$-optimal algorithm is at worst twice higher than that of any asymptotically optimal algorithm. In Appendix C, we show that the ratio $T^\\star_{1/2}(\\mu) / T^\\star(\\mu)$ is significantly smaller than $2$ for most instances. Based on Lemma C.6, we conjecture that the ratio reaches its maximum $r_{K} = 2K/(1+ \\sqrt{K-1})^2$ for “equal means'' instances (all suboptimal arms having the same mean), i.e. $T^\\star_{1/2}(\\mu) \\le r_{K} T^\\star(\\mu)$. This conjecture is validated empirically for $K=3$ and $K=4$ in Figure 2, and has a partial theoretical proof (see Lemma C.6).\nIdeally, we would choose $\\beta$ adaptively (e.g. IDS [44]). While this would yield asymptotic optimality, the “price” lies in the fact that finite-confidence guarantees are harder to derive for these fully adaptive algorithms. Deriving them is an interesting direction for future research.\n"}, {"review_id": "vKwRtad37X", "reviewer": "Reviewer_YhuH", "summary": "In this paper, the authors proposed a new UCB-based Top-Two algorithm (TTUCB) for the best-arm identification problem (BAI) and derived a non-asymptotic upper bound on the expected sample complexity holding for any instance having a unique best arm. The authors also demonstrated that the TTUCB algorithm achieves competitive empirical performance compared to other algorithms, including some existing Top-Two methods.", "questions": "+ Why don't you compare the performance of TTUCB with the non-asymptotic upper bound in Theorem 2.4 to check whether this bound is tight or not at different values of $\\delta$?\n+  From my second comment in the Originality section, what is the motivation for developing TTUCB for non-vanishing $\\delta$? Why don't we perform non-asymptotic analysis for the existing top-two algorithms? Did you mean that you would like to develop a new top-two algorithm (more specifically, TTUCB) such that the non-asymptotic analysis for the upper bound can be performed easier than the others?\n+ What is the main challenge when changing an asymptotic upper bound to a non-asymptotic one? More specifically, why is Theorem 2.3 optimal, but Theorem 2.4 not optimal as $\\delta \\to 0$?", "limitations": "This is a theoretical work. The authors already finished the checklist as well as stated the limitations of theorems and results. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "There have been some existing works that proposed top-two algorithms and analyzed the expected sample complexity for vanishing error level $\\delta$, i.e., $\\delta \\to 0$ (asymptotic upper bound). However, this work proposed a new top-two algorithm (TTUCB) and provided a non-asymptotic upper bound on the sample complexity, i.e., a bound that holds for any error level $\\delta$. The main (and new) contribution of this paper is to provide analytical techniques to obtain a non-asymptotic bound for the expected sample complexity for the TTUCB. ", "weaknesses": "However, this paper contains quite many weaknesses as follows.\n\n+  The tightness of this bound is not verified in this paper, especially for non-vanishing $\\delta$. \n+  The obtained non-asymptotic upper bound in Theorem 2.4. does not match the lower bound (Lemma 1.1) as $\\delta \\to 0$, which shows that the non-asymptotic upper bound is not tight enough at small $\\delta$.  Note that Theorem 2.3 shows that TTUCB is $\\beta$-optimal as $\\delta \\to 0$. \n+  In the moderate regime $(\\delta=0.1)$, the experiment (see Fig. 1) shows that the TTUCB algorithm can be better or worse than other existing ones. For example, in Fig. 1a, TTUCB looks worse than T3C although it is better than the others.  Hence, it seems to me that although other existing algorithms are developed for $\\delta \\to 0$, they can be better than your algorithm (i.e., TTUCB) as moderate $\\delta$. \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**Tightness of the finite-confidence upper bound of Theorem 2.4.**\nThe lack of a tight non-asymptotic lower bound is the main open problem in fixed-confidence best-arm identification. Unfortunately, we don’t solve this open problem in this work. Given the lack of a tight lower bound, we did the best we could, which is to compare to many other existing upper bounds as well as existing lower bounds. Those comparisons are discussed extensively in Section 2.1 and Table 1.\n\n**Asymptotic behavior of the finite-confidence upper bound of Theorem 2.4.**\nWe only managed to get within a factor 2 of the asymptotically optimal constant in the non-asymptotic bound. There is definitely room for improvement here, but our result is the first non-asymptotic bound for any top-two algorithm and we had to introduce a new proof technique to obtain it. That technique will surely be refined in the future. While Theorem 2.3 assumes that the means are distinct, Theorem 2.4 is the first guarantee on the expected sample complexity of a Top Two algorithm which doesn’t make this assumption.\n\n**Empirical performance of TTUCB compared to other Top Two algorithms.**\nThe objective of this work was not to propose a new algorithm that beat every other Top-Two method. We would have been happy with a non-asymptotic bound for T3C for example. TTUCB is very similar to T3C (it only swaps a TS leader for a UCB leader) and it is expected to have similar empirical performance. However, by replacing a TS leader with a UCB leader and using tracking instead of sampling, we obtained a deterministic algorithm amenable to finite-confidence analysis. Deriving finite-confidence guarantees for randomized Top Two algorithms such as T3C is an interesting direction for future research.\n\nWe now answer your other questions.\n\n**Motivation behind introducing TTUCB and analyzing it in the finite-confidence regime.**\nOur motivation is to analyze the family of Top-Two algorithms in general in a non-asymptotic regime. We would love to understand all of them, in particular the variants with the best empirical performance such as T3C. For some of them like EB-TC, experiments suggest that no good non-asymptotic bound is possible. Before our work, none of them had any non-asymptotic guarantees. We managed to prove a sample complexity upper bound for TTUCB. Since TTUCB is very similar to T3C (only the regret minimization algorithm used for the leader changes), we believe that our results are informative for other Top Two algorithms.\n\n**Conversion of an asymptotic upper bound towards a finite-confidence one.**\nWe would like to emphasize that our main contribution is the analysis of Top Two algorithms in a new way, which is very different from the asymptotic analysis. Therefore, we are not converting the existing asymptotic analysis into a non-asymptotic one, instead we provide new tools to analyze this class of algorithm. Theorem 2.4 is asymptotically suboptimal compared to Theorem 2.3 by a multiplicative factor $2$ because it is a different proof technique and there is one technical difficulty that we could not overcome (see lines 263-265 in Section 3, and lines 629-632 in Appendix D.2).\nThe main goal of existing asymptotic analyses is to exhibit a $\\delta$-independent time $T_{\\mu}$ after which the empirical proportions $N_{n}/(n-1)$ will stay $\\epsilon$-close to the ($\\beta$-)optimal allocation $w^{\\star}(\\mu)$. Intuitively, this property can only hold after a long time. If we were to express the dependencies of $T_{\\mu}$ in terms of gaps and $K$, we would obtain highly suboptimal terms which are significantly larger than the ones obtained in Theorem 2.4. As $T_{\\mu}/\\log(1/\\delta) \\to 0$, an asymptotic analysis can disregard such terms since they are simply describing the complexity of a transitory regime. However, the transitory regime is precisely what matters for a finite-confidence upper bound. Inherently, the asymptotic analysis requires too much control on the empirical means and proportions to yield any meaningful information in the finite-confidence regime. As a consequence, we had to derive a new proof strategy to obtain an insightful finite-confidence upper bound.  \n\n**Comparison between empirical performance and theoretical upper bound.**\nComparisons between the empirical performance of the theoretical upper bound show that there is still room for improvement (as is the case for all the bounds of the algorithms we compare to). Our proof method gave a first non-asymptotic bound, but we expect that it could be refined in the future to catch finer details of the algorithm behavior. Our experiments on large sets of arms provide some insights on whether our finite-confidence upper bound is tight. Empirically, Figure 1(b) and Figure 5 in Appendix G.2 hints that the empirical performance of TTUCB scales linearly with $H(\\mu)$ and not in $H(\\mu)^{\\alpha}$ as suggested by Theorem 2.4. Therefore, we are hopeful that better finite-time confidence guarantees can be shown.\n"}]

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

Meta-review: This paper has two novelties: (i) novel algorithm and (ii) novel analysis (finite-time analysis of a top-two-style algorithm for the first time). While it is not clear if the analysis is tight, these are meaningful contributions and worth being known in the NeurIPS community.
Decision: Accept (spotlight)