Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification
Authors: Kapilan Balagopalan
Ngo Tuan Nguyen
Yao Zhao
Kwang-Sung Jun
Venue: ICML 2025 poster (2025)
Keywords: Multi-Armed Bandits
Pure Exploration
Learning Theory
Primary area: theory->online_learning_and_bandits
TL;DR: We report a novel theoretical criterion called 'exponential stopping tail', which is strictly stronger than prior ones. We propose two algorithms that can achieve such a tail bound and prove that some existing algorithms cannot satisfy our criterion.

Abstract: The best arm identification problem requires identifying the best alternative (i.e., arm) in active experimentation using the smallest number of experiments (i.e., arm pulls), which is crucial for cost-efficient and timely decision-making processes. In the fixed confidence setting, an algorithm must stop data-dependently and return the estimated best arm with a correctness guarantee. Since this stopping time is random, we desire its distribution to have light tails. Unfortunately, many existing studies focus on high probability or in expectation bounds on the stopping time, which allow heavy tails and, for high probability bounds, even not stopping at all. We first prove that this never-stopping event can indeed happen for some popular algorithms. Motivated by this, we propose algorithms that provably enjoy an exponential-tailed stopping time, which improves upon the polynomial tail bound reported by Kalyanakrishnan et al. (2012). The first algorithm is based on a fixed budget algorithm called Sequential Halving along with a doubling trick. The second algorithm is a meta algorithm that takes in any fixed confidence algorithm with a high probability stopping guarantee and turns it into one that enjoys an exponential-tailed stopping time. Our results imply that there is much more to be desired for contemporary fixed confidence algorithms.

Fixing the Loose Brake: Exponential-Tailes Stopping Time in Best Arm
Identification
Kapilan Balagopalan 11
Tuan Ngo Nguyen 11
Yao Zhao 11
Kwang-Sung Jun'
Abstract
1. Introduction
The multi-armed bandit model serves a foundational frame- work for studying sequential decision-making under un- certainty. In this framework, a learner interacts with an environment by sequentially selecting among multiple alter- natives (arms) and observing stochastic rewards, allowing for the rigorous analysis of fundamental trade-offs inher- ent in sequential decision-making. A core problem within this theoretical landscape is best arm identification, which focuses on identifying the arm associated with the highest mean reward, either with a pre-specified confidence level or within pre-specified sampling budget, known as the fixed confidence setting and fixed budget setting, respectively.
The best arm identification problem requires iden- tifying the best alternative (i.e., arm) in active ex- perimentation using the smallest number of exper- iments (i.e., arm pulls), which is crucial for cost- efficient and timely decision-making processes. We consider the fixed confidence setting where an algorithm repeatedly selects arms until it decides to stop and then returns the estimated best arm with a correctness guarantee. Since this stopping time is random, we desire its distribution to have light tails. Unfortunately, many existing studies focus on guarantees that hide the issue of allow- ing heavy tails even not stopping at all. Indeed, we show that the never-stopping event can indeed happen for standard algorithms. Motivated by this, we make two theoretical contributions. First, show that there exists algorithm that attains desirable exponential-tailes stopping time guar- antee that is strictly better than the polynomial tail bound Kalyanakrishnan et al. (2012) and the exponential guarantee obtained by uniform sampling. Our guarantee is more fundamental than existing ones in the sense that our guarantee implies that it achieves existing optimal guaran- up to logarithmic factors. Second, we show that there exists a meta algorithm that takes in any fixed confidence algorithm with a high probabil- ity stopping guarantee and turns it into one that enjoys an exponential-tailee stopping time with matching instance-depende logarithmic factors. Our results imply that there might be much more to be desired for contempo- rary fixed confidence algorithms.
While the fixed confidence setting has conceptual connec- tions to applications such as A/B/../K testing, the focus of this work lies in the more general and theoretical side, adap- tive fixed confidence best arm identification setting, where pulls assigned adaptively based the outcomes of previous pulls. The advantage of adaptive assignment is that it often results in significantly lower sample complexity compared to non-adaptive assignment.
Therefore, many works have proposed algorithms and proved bounds on how many samples they use until stop- ping (i.c., sample complexity) either with high probability or expectation (Even-Dar et al., 2006; Karnin et al., 2013; Jamieson al., 2014). However, most existing sample com- plexity guarantees do not sufficiently describe the behavior of the stopping time. For instance, an algorithm might be guaranteed stop before T" samples with probability at least 1 - 5, but with probability up to 6, the algorithm may never stop or stop only after very long time, much larger than T* Algorithms with expected sample complex- ity guarantees will stop. but the tail of the distribution of the stopping time can be very thick. Thus, the realized stopping time can be significantly larger than the expected one, which is undesirable. These issues have been under-explored in the literature.
complexity up to
To address this gap, we push the limits of attainable guaran- tees for the tail decaying rate of stopping time distribution of fixed confidence best arm identification algorithms. To the best of our knowledge, aside from LUCB by (Kalyanakr- ishnan et al., 2012) with polynomial-tain -aiieed stopping time bound, there has been no significant study on the tail the
'Equal contribution 'Unieersity of Arizona. Correspondence to: Kwang-Sung Sunngg-Sunggga Jun <kjun arizzoaa..duu
Proceedingy of the 4 International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fixing the Loose Brake: Exponential-Tre -ailee Stopping Time in Best Arm Identification
stopping time distribution." ! In particular, there are no re- sults in the literature reporting an exponential tail bound for the stopping distribution except for the uniform sampling. However, uniform sampling is widely regarded as naive due to its inability adaptively assign arm pulls.
2. Problem Definition and Preliminaries
We consider the standard K-armed bandit setting, where learner sequentially selects one of K arms where each arm i E [K] ís associated with reward distribution that is
(known) with mean (4; (unknown). We assume that there exists a unique best arm, which stan- dard (Audibert et al., 2010). Without loss of generality, we assume that the arms are ordered in decreasing order of their mean rewards, i.e., /41 > 1/2 2 ... 2 =KK- At each time step t, the learner selects an arm A, E [K] := 21. K)), then observes reward r2 VA,-- We consider the fixed con- fidence setting, where the learner aims to identify the best arm with a pre-specified confidence level 5 E (0, 1) that is also called failure rate. The goal is to design an algorithm A that includes a sampling rule choosing A,, stopping rule that determines when to stop, and a recommendation rule that outputs the estimated best arm ((A when stop- ping. We denote by r(A) the (random) stopping time of the algorithm A, which is the arm pulls that A makes before the algorithm stops. We often omit the dependence on the algorithm A and use T and J when the algorithm being used is clear from context.
In this paper, we make several key contributions towards strengthening guarantees for the stopping time distribution, which we summarize as follows:
Theoretical Evidence of Limitation in Existing High-Probabillity Guarantees: We demonstrate that both Successive Elimination (Even-Dar et al., 2006) and KL-LUCB (Tanczos et al., 2017), despite enjoying high-probability guarantees, they will not stop at all with constant probability. To ourknowledge, this is the first such evidence in the literature for fixed confidence algorithms.
First Theoretical Work Establishing the Possibility of an Exponential-Tailed Stopping Time: We present fxed-confidence variant of Double Sequential Halv- ing (FC-DSH), an algorithm that combines the Sequen- tial Halving approach with the doubling trick and carefully designed stopping rule. Our analysis shows that FC-DSH achieves an exponential-tailee stopping time with a matching instance-dependens complexity up to logarithmic factors. To our knowledge, this is the first such guarantee in the literature.
An algorithm for the fixed confidence setting is required to satisfy the following correctness result.
Definition 2.1 (б-correct). A fixed confidence algorithm is said to be 5-correct it takes 6 as input and satisfies
Introducing Brake A Meta-Algorithm for Achieving Exponential-Tailld Stopping Time: Mo- tivated by our success with FC-DSH, we take a step further and propose novel meta-algorithm approach. This approach takes in any fixed confidence algorithm that meets mild conditions and and turns it into an algorithm with an exponential tail guarantee for the stopping time.
IP(T < 0o, + 1) S 8
We call such an algorithm 5-correct. Note that the condition ((A) < above is necessary since J, (A) is undefined otherwise.
Furthermore, we desire the algorithm to stop as early as possible in addition to being d-correct. There are two cri- teria that have been popular in the literature: asymptotic expected sample complexity and high probability sample complexity.
Table 1 presents comparison of popular FC-BAI algo- rithms, highlighting our theoretical contributions to the FC- DSH and BrakeBooster algorithms in achieving exponential- tail stopping time. We want to clarify that our objective is not to improve the computational complexity practical performance of existing FC-BAI algorithms. Instead, our work demonstrates that an exponentially decaying tail with matching mestance-dependens complexity (up to logarith- mic factors) for the stopping time distribution is achiev- able. Also, we focus on FC-DSH due to its simplicity and widespread adoption in practice (e.g.. in Hyperband (Li et al., 2018)). The computational efficiency of FC-DSH's is not worse (orderwise) than other algorithms.
The asymptotic expected sample complexity (Chernoff, 1959; Garivier & Kaufmann, 2016; Shang et al., 2020; Qin et al., 2017) characterizes the asymptotic behavior of the stopping time as goes to 0 as follows:
Definition 2.2 (Asymptotic expected sample complexity). A fixed confidence algorithm is said to have an asymptotic expected (AE) sample complexity of T if it satisfies
E[T]
lim inf 6-0 In(1/8)
S T5
where - depends on 8.
While AT-LUCB (Jun& & Nowak, 2016) showed a tail bound that decays exponentially, the bound exponential in /t rather than I. which does not fit Definition I. Furthermore, the correctness questionable, specifically, the paper's Lemma 7 and 8 is likely to be false.
The optimal guarantee has been well-understood for expo- nential family reward models (Garivier & Kaufmann, 2016). For example, Track-and-She (Garivier & Kaufmann, 2016)
'Recently, Jourdan & Degenne (2023) analyzed the non- asymptotic expected sample complexity.
2

---

However, the AE sample complexity has two limitations. First, the AE sample complexity does not tell us anything about the tail of r. In fact, can still be heavy-tailed as empirically observed by Jourdan et al. (2022, Figure 4, EB- TC) despite having a near-optimal AE sample complexity. Second, the AE sample complexity hides potentially bad behaviors of the algorithm in the con-asymptotic regime or with moderately small 5. That is, the AE sample complexity hinges on the behavior of the algorithm when ô close enough to O, in which case the algorithm would be running for a very long time. Indeed, one can observe that if [B[r] R A (1(6/) + B for some A and B that not dependent Fixing the Loose Brake: Exponential-Taiee Stopping Time in Best Arm Identification
Table I. Comparison of guarantees.
Exponential-tailed stopping time
High probability sample complexity
Asymptotic expected sample complexity
Meta
algorithm
Successive Elimination
X
x
(Even-Dar et al., 2006)
LUCB
Unknown
X
(Kalyanakrishnan et al., 2012)
Track-and- -nd-Sp
Unknown
Unknown
x
(Garivier & Kaufmann, 2016)
Top Two algorithms
Unknown
Unknown
/
X
(Jourdan et al., 2022)
TTUCB
Unknown
Unknown
/ X
(Jourdan & Degenne, 2023)
FC-DSH (our work)
x
BrakeBooster (our work)
achieves the optimal asymptotic expected sample complex- ity.
target failure rate with which we bound the sample complexity. In practice, one may desire to be loose on the correctness (large 8) yet want to ensure that the stopping time is small with very high confidence (small 8). We speculate that the high probability sample com- plexity is mere byproduct of easy analysis.
Second, more importantly. the guarantee above does tell us about the shape of the tail of the stopping time. In particular, the high probability sample com- plexity guarantee does not exclude the possibility of never stopping even the problem at hand is easy, which is serious issue as it would imply that the prac- titioner will have to wait forever or forcefully stop the active experimentation procedure (See Figure 1). It also follows that the expected stopping time E[r] does exist.
B[]] will be independent of B the value of lim inf lm(1/8] even if is very large.
To further demonstrate the issue of having extremely bad tail for the stopping time distribution, we provide lower bound for the Successive Elimination algorithm (Even-Da et al., 2006). Hereafter, all the proofs are deferred to the appendix unless stated otherwise.
On the other hand, high probability sample complexity guar- antee (Even-Dar al., 2006; Karnin et al., 2013; Jamieson et al., 2014; Jun et al., 2016; Tanczos et al., 2017), defined below, does not rely on the asymptotic behavior of the algo- rithm.
Theorem 2.4. For Successive Elimination, there exists an instance with unique best arm where the algorithu never stops with non-negligible probability of St (8118).
Definition 2.3 (High probability sample complexity). A fixed confidence algorithm is said to have a sample com- plexity of T5 if it takes 5 E (0, 1) as input and satisfies (P 2 T 5.
Although the probability bound established in Theorem 2.4 appears to be very small, it is just the looseness of the analysis, and fact, the fraction that does not stop is quite nontrivial over wide range of values of 5. See Figure 2.
For example, Successive Elimination (Even-Dar et al., 2006) achieves high probability sample complexity of O(H, (n(6))) where H1 Σ A characterizes the instance dependent complexity of the problem and Ô omits logarithmic factors except for (166) Despite being non- asymptotic, we find the high probability sample complexity weak and rather unnatural for the following reasons:
We show that the same is true for KL-LLUB (Tanczos et al., 2017).
Theorem 2.5. For KL-LUCB, there exists an instance with a unique best arm where the algorithm never stops with a constant probability.
First, we find it unnatural that 8, the failure rate re- garding the correctness of the output J, also the
Remark 2.6. One way to stop the algorithm from infinitely running allow g-slack in the stopping condition as done
3

---

Fixing the Loose Brake: Exponential- Taiiled Stopping Time in Best Arm Identification
uniform sampling). In this paper, we focus on the best arm identification to keep the discussion concise.
70
Meanwhile, the seminal work by Kalyanakrishnan et al. (2012) has proposed algorithm called LUCBI that satis- fies the following polynomial tail guarantee on the stopping time, which is adapted for the best arm identification prob- lem rather than the s-optimal arm identification.
60-
Number Trials
50
40
Theorem 2.7 (Adapted from Kalyanakrishnan et al. (2012)).
30
Let T 146H, In ( ( )
For every T 2 T", the probability that LUCBI has not terminated after T samples is at most 46
20
10
This makes us wonder if it is possible to achieve an exponentially-decaying tail bound for the stopping time т, which we believe is important in practice as well. We formalize the desired property in the following definition where polylog(T)) means x S a log" log"(T) + for some absolute and positive constants a, b, and c.
0
0
5000
10000
15000
20000 25000 30000
Stopping time
Figure 1. Historgram of stopping times of Successive Elimina- tion (Even-Dar al., 2006) of 1000 independent trials three arms with mean rewards of {1.0, 0.9, 0.9} and Gaussian noise (0, 1). We forcefully terminated the runs that do not stop until 30,000 time steps (6- = 0.01). We have observed that all these runs have already eliminated the best arm, and thus expect that many of them will never stop.
Definition 2.8 (TTo, -exponeentii stopping tail). A fixed confidence algorithm is said to have (To, -)-expnnential stopping tail if there exists a time step T3 and a problem- dependent constant & (but not dependent on 7) such that for all T To.
T
P 2 T) S exp
(1)
polylog (T)
8.5
SE
This property requires a tail bound for every large enough T, which reveals detailed information about the distribution function of r. Perhaps not surprising, this requirement is strictly stronger than the high probability sample complexity above and implies a few desirable properties regarding the stopping time T as we summarize below.
Percentage of failed trials (in %)
7.6
Proposition 2.9. If a fixed confudence algorithm has (To, expponennill stopping tail, then the following hold true:
4.4
(i) P (T 2 Ts +1l1)/()/)) polylog(*In(1/0)) S 56. (ii) E S To + + polyyoogg(s)
3.2
10"-5
10"-4
10"-3
10"-2
10"-1
Delta
(iii) P(T < x)== 1.
Figure 2. Percentages of trials that fails to terminate a function of varying values over the range [10-5, ...., 10-1). Results from 100K trials of Successive Elimination algorithm
Proof. For (i), find T that would make the RHS of (1)
below 5. For (ii), use the identity B[X] -x= P(X
x). For (iii), use the Borel-Cantelli lemma.
in, e.g., Kalyanakrishnan et al. (2012). However, one can also extend the arguments in Theorem 2.4 and 2.5 to show that the stopping time can be as large ((K/e²) even if the guaranteed high probability sample complexity is sig- nificantly smaller than @ @(K/s²), and this gap can be made arbitrarity large. Furthermore, we conducted experiments (see Appendix D). compare the stopping time distribution before and after introducing E-slack stopping condition for Successive Elimination (Even-Dar et al., 2006). The e-slack variant achieves a weaker exponential-tai (similar to naive
While the guarantees above can be individually satisfied by specific criterion such as high probability or expected sample complexity, Proposition 2.9 shows that enjoying an exponential tail guarantee implies all three desirable properties simultaneously.
One can show that the naive uniform sampling algorithm that chooses arm A, = 1 + ((t - 1) mod K) at time with a suitable stopping condition results in (Ts, exponential stopping tail with T3 = θ(KA,² ln(1/8) 1I(A,)
4

---

Fixing the Loose Brake: Exponential-Tee Tailed Stopping Time in Best Arm Identification
Algorithm 1 FC-DSH
The DSH algorithm combines the Sequential Halving (SH) procedure (Karnin et al., 2013) with the doubling trick. It proceeds in iterative phases, with each phase running an independent instance SH. The budget allocation follows a doubling schedule, starting with budget Ti K (ogg(K)) for phase and doubling for subsequent phases, i.c., Tm 2n Ti, for phase m 2 2.
Input: A set of K arms, 5
Ti = [ logg K]
Tm = T:2"=1,,v 1mmm 2 2
// the sampling budget as-
signed to phase m
L = [lgg(K))
// the last stage in each phase
for m 1,2,.... .2...... do
// p/hase m
FC-DSH fundamentally differs from its fixed-budget coun- terpart (FB-DSH) in how termination is handled. FB-DSH is provided with a pre-specified budget and terminates once this budget is exhausted. Conversely, FC-DSH operates with a given confidence level 5 E (0, 1) and terminates once carefully designed stopping rule is satisfied. Our stopping rule is designed to ensure both 8-correctness and the desired (To, R) expponennt stopping tail guarantees. In what fol- lows, we introduce additional notation and formally define our stopping rule.
Reset A1 = [
for { = 1, .,..., L do
// stagee f
Sample each arm i E As for ((m,)) times where
Tm
N(m
K2- E+1 1log (K)
Let Ac+1 be the set of [As/2] arms in A with the largest empirical means computed using samples from this stage only. end for
During the phase m, for any arm E [K]. let l, denote the stage at which arm is eliminated, At this point, arm i has been sampled ((m.f)) times and has received rewards
Select Jm as the only arm in AL. // stopping rule
{r(3)) (m)) Nimm.5))
Based on these rewards, we define the
J==1
if L (m) Jm max (m) then
empirical mean of arm as:
J..
Stop and output Jn.
(m)
end if end for
((m.)
rin
and its confidence width as:
and = ((KA))) However, by Proposition 2.9, this guarantee is converted to a high probability sample com- plexity of Ō(KA² ln(1/6)), which is much worse than O(H, (n(1 achieved by Successive Elimination.
2 (m
6K [Kog m²
log
The complexity of a best-arm identification problem is of- ten characterized by instance-dependens quantities, such as H, : > A and H2 = max iA, (Audibert et al., 2010). These two quantities are equivalent up to logarithmic factor, as captured by the inequality:
Using these quantities, we define the upper and lower confi- dence bounds for arm as: U!!T) == p. (!) + b((²) and L.(²) == pm( ((m)
+b(-))
At the end of phase m. the corresponding SH instance se- lects an arm, denoted by Jm. We formally define the stop- ping rule as:
H2 S H1 < 1og(2K)H2.
(2)
(m)) max U!!!). (f
We thereby ask if it is possible to achieve (Ō(H, ln(1/))), Ō(H -(xxoniexlon stopping tail, or perhaps a looser form ln(16)), ((H)). We
The rule ensures that, with high probability, the selected arm Jm is statistically significantly better than all other arms. The full algorithm is presented in Algorithm 1.
answer this question in the affirmative by proposing two algorithms in the following two sections.
The following theorems show that DSH satisfies the correct- ness guarantee and enjoys an exponential stopping tail. Theorem 3.1 (Correctness). FC-DSH runs with confidence level is d-correct.
3. Fixee-Confidence Doubling Sequential Halving (FC-DSH)
In this section, we introduce FC-DSH, a fixed-confidence variant of the Doubling Sequential Halving (DSH) al- gorithm, motivated by its fixed-budget counterpart (FB- DSH) proposed by Zhao et al. (2023). We show that FC- DSH satisfies the correctness guarantee and achieves an (Ó(H, HH 1))(1/))) O(Hz)) expoonnlxlollttaall stopping tail.
Theorem 3.2 (Exponential stopping tail). FC-DSH enjoys (Ó log ((Ha)))exponeniia stopping tail.
Theorem 3.2 establishes the existence of fixed- confidence best-arm identification (FC-BAI) algorithm with an exponential stopping tail, characterized by (Ô(Hz log(1/6)), O(H2)). While this bound is not tight,
5

---

Fixing the Loose Brake: Exponential-Ton Tailed Stopping Time in Best Arm Identification
marks the first step toward demonstrating that such an exponential stopping tail is indeed achievable.
Algorithm 2 BrakeBooster
Input: base trial count L1, base budget T1, algorithm A, base failure rate du for r = 1, 2, do
The formal proofs are deferred to Appendix B.1 and B.2 respectively. Here, we highlight the key ideas underlying the proof of Theorem 3.2. The main objective is to bound the probability that, for all phase m such that Tm 2 To, FC- DSH fails to satisfy the stopping rule given by Equation (3). This event can be decomposed based on whether the selected arm Jm is optimal:
for c == 1. 2.. do
Lr.c r 20 L1, Tr (T
Jr.e = Budgetedlddemtffiationn Lr,,, Tre 80)
if Jn + 0 then
return Jr.c end if end for end for
(m))
max U.!T) 4f
TP
Im
P
Jm
(m)
< max U. Jmn +1 if
The key idea of BrakeBooster is to repeatedly invoke our key subroutine Budgettedddnntfficttoon (Algorithm 3) with increasing trial count L,,e and budget Tr until a stopping criterion is met where (r; e) is an index of each invoca- tion (called stage) with r E N+ and E [r]. We defer the explanation on how we schedule Lr.e and T,e to the next paragraph. In stage (r, we are given the number L = Lr.e of trials, the sampling budget T Tr,c, and the base failure rate 60 and run A(do) repeatedly L times with a sampling budget of T. Since A itself may not stop before T time steps, we ensure the budget constraint by forcing A to stop (forced-termination) when it does not stop by itself (self terminatmm))) after exhausting T samples. For each trial E [L]. we collect the returned arm index Jr. which is set to 0 if AA was forced-terminatted If at least half of the trials were forced-terminated, then we have Other- failed we return 0 from Budgetedldentiffcatio
(m) Jm
< max Ul
P
Im =1
if
The first term implies the event where FC-DSH fails to identify the optimal arm; bounding this event, IP (Jm # 1), is well-studied in BAI literature.
The second term, where the stopping rule is not met despite the optimal arm is being selected, is more challenging and requires a finer-graines analysis. To handle this case, we ex- amine how long suboptimal arms survive in the elimination process during phase m.
Recall that, for any arm i E [K]. & denotes the actual stage at which arm i is eliminated. We define the expected elimination stage f to be the largest stage index satisfying A, S 1 y 2 4,11. If no such f exists, it implies that A, Ag. indicating that arm i has a sufficiently large suboptimal gap and should be climinated early. For arms with a valid f we further partition the analysis based on whether the actual elimination stage 4 is greater than less than fj. These cases highlight the core technical contributions of our proof beyond standard BAI analysis. We provide detailed bounds for each case in Lemmas B.2, B.3, and B.4, respectively.
wise, we declare success and return the majority vote over {Je : E [L], 7 0} (i.e., majority votes over nonzero votes). In the latter case, BrakeBooster stops and outputs the majority vote as the final output J. J-MM). In the former case, we continue to the next stage with trial count L,yte and Tre where (r', ()) = (r.c + 1) if e S r - 1 and
(r', ".,'''=( (r cf
The key in our algorithm is the particular scheduling of Tay, and Tr.., which is inspired by Li et al. (2018) and can be viewed as a -oo-dimensional doubling trick. We visualize the schedule in Figure 4. Each dot in the figure represents the stage (r, c). and the label below each dot represents the number of trials (Ir,e) and the budget assigned to each trial (Ty,c). For a fixed row r, each stage spends the same sampling budget of Ly,TTr.c = r2- L,T However, the assignment of Lr,c halves with increasing and Tre doubles with increasing c. For a fixed column c, as the row index increases, the total budget for each stage Ly.cTr,c doubles in fact slightly more than double due to a technical reason that will become clear in the proof of Theorem 4.1. Both the number of trials and budget increase row-wise, mean- while different combinations of trial size and budget are employed aallunn-wise keeping the effective total samples used constant throughout the same row.
4. BrakeBooster: A meta algorithm approach
In this section, we propose a novel algorithm called Brake- Booster. This is meta algorithm in the sense that it takes any fixed confidence best arm identification algorithm (de- noted by A) equipped with the standard guarantees on the correctness and stopping time as an input and converts it into one that enjoys an exponential stopping tail.
We denote by A(do) as algorithm A run with target failure rate of dg- We assume that A(d)) is 50-correct (Defini- tion 2.1) and has sample complexity guarantee of 77, (A) (Definition 2.3). Note that BrakeBooster will not require T% as input, but only the existence.
Given such an algorithm A, we are ready to describe Brake- Booster whose full pseudocode can be found in Algorithm 2.
6

---

Fixing the Loose Brake: Exponential- Tailed Stopping Time in Best Arm Identification
Algorithm 3 Budgetteddennification
namely r2". This multiplicative factor of r in the exponent is crucial, as it enables the use of converging geometrie series in the analysis. However, this doubling trick only adds a logarithmic term in the final sample complexity. In summary, 1) the progression of trial counts L along with the majority voting scheme ensures an exponentially decay- ing stopping time distribution, and 2) the per-trial budget schedule guarantees that the dg-correctness condition the black-box subroutine is satisfied at some point, when the budget exceeds the unknown T5 (A).
Input: algorithm A. the number of trials L, sampling budget per trial T, base failure rate dn
for 8= 1,2... do
Run algorithm until it self-terminates or exhausts the sampling budget T.
if A has self-terminated then
J2- = (AA)
else Je end if
Importantly, our framework permits the use of any black- box algorithm with relatively large 6g. and allows one to tune the initial budget parameter In to obtain significantly stronger d-correct guarantee.
end for
Count the votes:
Vi E
K}.0
Ee [J+=
if vb
1 +1 then return 0 // failure
Furthermore, BrakeBooster enjoys an exponential stopping tail.
else
Theorem 4.2 (Exponential stopping tail). Let algorithu A be bo-correc and have a sample complexity of (A). Suppose we run BrakeBooster (Algorithm 2) with input A.
return arg maX 2 end if
success
8, L1 log Ic40
10 1, Ti 2 1, and óg S (2) Then, there
Our 2D doubling trick extends the vanilla doubling trick introduced in DSH. The vanilla doubling trick works by iterating through an input parameter (e.g., budget in DSH) at an exponentially growing rate to eventually reach the op- timal value with only a logarithmic cost. Similarly, our 2D doubling trick in Algorithm 2 requires two input parame- ters, necessitating the design of a doubling scheme for both. While the budget doubling mirrors DSH, the voting scheme enhances confidence through the independence of repeated trials. Additionally, our choice of L1 ensures the minimal number of repeated trials needed to achieve a confidence certificate of 6, as presented in the following theorem.
exists To ( (A) + Ti) In(1/8)) such that
T (Ti; (A) Ollog T)
VT To, P (T((M( 2 S exp
That is, if is an absolute constant, then BrakeBooster en- joys a (0(Tg, (A) (A))(())))) ())( -xpoonenntlt stopping tail.
The theorem above literally delivers the promised guarantee it takes in an algorithm with a high probability sample complexity guarantee T% (AA and turns it into the one that enjoys exponential stopping tail without losing the same high probability sample complexity guarantee due to Propo- sition 2.9(i), up to polylog(T)) factors. For example, one can use Successive Elimination (Even-Dar et al., 2006) to obtain the following guarantee.
Theoretical analysis. We first show that BrakeBooster is d-correct.
Theorem 4.1 (Correctness). Let an algorithm A be 80- correct and have a sample complexity Tf (A), Suppose we run BrakeBooster (Algorithm 2) denoted by M with imput A, 8, Ta =
Corollary 4.3. Suppose we take Successive Elimination algorithm (Even-Dar et al., 2006) as A and run Brake-
(1)
Ti 2 1, and do S (20
log
Booster algorithm with L1 = +log((+ Ti >
Then,
log seag
P (P((M) < < 0o, J(M) # 1) 5..
1, and d0 = =( Then, BrakeBooster enjoys a (Ô (H, In (1/5))
exxponennnt stopping tail.
The proof is provided in the Appendix. We briefly outline the key ideas underlying the approach. The main novelty in the proof of Theorem 4.1 lies in establishing a d-correct guar- antee by repeatedly invoking ón-correct algorithm within a suting-based framework. A central component of this argument is Lemma C.2, which demonstrates that the voting mechanism induces an exponentially decaying failure prob- ability, provided that do is not too large-for for instance, when 60 > (2e]z- Another notable aspect of our analysis is the design of the trial budget schedule Ly,e. Instead of doubling the sample size in each round as in standard schemes (e.g., using 2"), we apply a slightly more aggressive growth rule,
Figure 3 shows that applying BrakeBooster on Successive Elimination helps to stop all the trials without sacrificing too many samples (the CDF curve of BrakeBooster++EE catches up with that of SE very fast because the crossover point is at the stopping time of ~ 0.05 x 10%).
5. Related Work
While research on best arm identification can be traced back to the seminal work of Chernoff (1959), algorithms with fixed confidence with the correctness and the sample com-
7

---

Fixing the Loose Brake: Exponential-Ton Tailed Stopping Time in Best Arm Identification
1.0 based Top Two algorithm (TTUCB) which provides both asymptotic and non-asymptotic upper bounds expected sample complexity. More recently, Jourdan et al. (2023) extend the Top Two framework with EB-TC where the objective is identify an arm within Eo of the optimal arm. This algorithm achieves both asymptotically optimal and non-asymptotic guarantee in the eo-FC-BAI setting. How- ever, notably, all these results focus on the expected or high-probability sample complexity, rather than the stop- ping time distribution. Therefore, these algorithms do not (yet) have a guarantee showing a light tail for the stopping time distribution, which does not exclude the possibility of running for long time before stopping with a non-trivial probability.
400
SE
SE_ with BrakeBooster
350
0.8
Number Trials
300
0.6
250
200
-0.4
150-
100
0.2
50-
0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Moreover, the fixed budget algorithm, in contrast, must return the best arm within a pre-specified budget. Audib- ert et al. (2010) propose the first fixed budget algorithm called Successive Rejects. They show that the probability of misidentifying the best arm scales with a problem-dependdet quantity, H2 max d. Karnin et al. (2013) later im- prove this result by logarithmic factor with an improved algorithm called Sequential Halving, which has been widely adopted in many applications including hyperparameter op- timization (Li et al., 2018). A recent work by Zhao et al. (2023) builds upon Sequential Halving, addressing how to measure if the algorithm's 's output is good enough for any suboptimality gap E. while is free be chosen after the algorithm finishes. Additionally, this work extends Sequen- tial Halving to the challenging data-poor regime, where the number of samples is even smaller than the number of arms, While we leverage some fixed budget algorithms such as Sequential Halving, the main focus of this paper is the fixed confidence setting.
Stopping time
1e6
Figure 3. Historgram of stopping times of BrakeBooster applied on Successive Elimination (Even-Dar al., 2006) vs bare Successive Elimination: Out of 1000 independent trials on four arms with mean rewards of (1.0, 0.9, 0.9, 0.9) and Gaussian noise (00 1). We forcefully terminated the runs that do not stop until 1 M time steps. (6 0.01). CDF of stopping times are shaded with respec- tive colors. (In this experiment, we employ a 1.2x growth factor for both the per-trial budget and the number of trials, contrast to the conventional doubling scheme.) )
plexity guarantees first appeared in Even-Dar et al. (2006) where the authors proposed two influential algorithms: Me-
dian Elimination and Successive Elimination. The former shows a deterministic sample complexity of O go log } for finding an arm that is close to the best arm with prob- ability of at least 1 - 8. This worst-case result is optimal up to a constant factor. The second algorithm, Successive Elim- ination, shows that, with a probability of at least 1 5, the sample complexity of identifying the best arm scales with an instance-dependent quantity H1 ΣK A. where A, is the gap between the best arm and the i-th best arm. This result has had a significant influence on subsequent research on best arm identification. Since then, many algorithms have been proposed to improve the sample complexity of best arm identification in the fixed confidence setting. For instance, Kalyanakrishnan et al. (2012) propose the LUCB algorithm that extends Even-Dar et al. (2006) to the scenario where the algorithm is required to return the best m arms in- stead of just the best arm. Karnin et al. (2013) and Jamieson et al. (2014) then propose algorithms with improved guar- antees that turn problem-dependee doubly-logarithmic ones. Chen et al. (2017) have further improved both lower and upper bound guarantees on the high probability sample complexity. Garivier Kaufmann (2016) propose the Track-and-Stop algorithm and Jourdan et al. (2022) propose Top Two algorithms that asymptoti- cally matches the asymptotic lower bound for its sample complexity. Jourdan & Degenne (2023) propose a UCB-
6. Conclusion
We have provided a new theoretical perspective the be- havior of the stopping time for the fixed confidence best arm identification algorithms, which inspires numerous open problems. First, both of our proposed algorithms intro- duce nontrivial extra constant logarithmic factors in their sample complexity compared to the well-known optimal instance-dependent sample complexity that is achieved by existing algorithms (Garivier & Kaufmann, 2016). It would be interesting to investigate whether it is possible to develop novel algorithms that obtain instance-dependent optimality while attaining exponentially decaying tail bounds for the stopping time distribution. Second, Broke algorithm incurs polylog(T)) term within the exponent. It would be interesting to investigate whether this term can be eliminated or, alternatively, to establish lower bound that matches this dependence. Third, the resetting mechanism employed by our algorithms tends to be less practical. It would be inter- esting to investigate whether there exists a simple and/or elegant algorithm that can avoid the resetting mechanism
logarithmic factors into
8

---

Fixing the Loose Brake: Exponential- Taileed Stopping Time in Best Arm Identification
(1,1)
LT, Ti
(2,
(2,
2 2L m
2 2T.
(3, 1)
(3,2)
(3.3)
8-4L,, T
3 3-21, 27,
3-4,,47
(r,1)
(r,2)
(r,3)
(r.c) c)
(r.r)
r2 L,,
r2 L,, 22
r2 L1,
12
r Ly 21,22-11
rL, 2T
Figure 4. diagram showing the progression of the stages in Algorithm 2 where each stage c) has different trial count Le.e
r2" L1 and per-trial budget T., = 2T)
and exhibit practical numerical performance. In particular, studying whether or not the recently proposed practical al- gorithms in Jourdan et (2022) achieve exponential tail bounds and, if not, developing remedies for them would be an interesting avenue of research. Finally, it would be interesting to attain similar exponential tail bounds for more complex settings such as combinatorial bandits or Markov decision processes.
bounds for best arm identification. In Conference Learning Theory, pp. 535-592. PMLR, 2017.
Cherooff, H. Sequential design of experiments. The Annals of Mathematical Statistics, 30()):55-777,, 1959.
Das, S. A brief note estimates of binomial coefficients. URL: http://page. mi. fu-berlin. defshhggmik/notes/iinnni als. pdf. 2016.
Impact Statement
Even- DDrr E., Mannor, S., and Mansour, Y. Action Elim- ination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research, 7:1079-1105, 2006.
This work is theoretical and not tied to particular applica- tion that would have immediate negative impact.
Garivier, A. and Kaufmann, E. Optimal best arm identi- fication with fixed confidence. In Proceedings of the Conference on Learning Theory (COLT), pp. 998-1027, 2016. Jamieson, K.. Malloy, M., Nowak, R., and Bubeck, S. lil' UCB An Optimal Exploration Algorithm for Multi- Armed Bandits. Proceedings of the Conference on Learning Theory (COLT), pp. 423 439, 2014.
Acknowledgments
Kapilan Balagopalan, Tuan Ngo Nguyen, Yao Zhao, Kwang- Sung Jun were supported in part by the National Science Foundation under grant CCF-2327013 and Meta Platforms, Inc. We thank Emilie Kaufmano, Mare Jourdan, and Rémy Degenne for the discussion that sparked this project.
References
Jourdan, M. and Degenne, Non-asymptotic analysis of ueb-based top two algorithm. Advances in Neural Information Processing Systems (NeurIPS), 2023.
Abramowitz, M. and Stegun, I. A. Handbook of mathemat- ical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1968.
Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. Top two algorithms revisited. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best Arm Iden- tification in Multi-Armed Bandits. In Proceedings of the Conference on Learning Theory (COLT), 2010.
Jourdan, M., Degenne, R., and Kaufmann, E. An e-best-arm identification algorithm for coeedconfieecce and beyond.
Chen, L., Li, J., and Qiao, M. Towards instance optimal

---

Fixing the Loose Brake: Exponential-Taie Taiiled Stopping Time in Best Arm Identification
Advances in Neural Information Processing Systems, 36: 16578-16649, 2023.
Jun, K.-S. and Nowak, R. Anytime exploration for multi- armed bandits using confidence information. In Pro- ceedings of the International Conference on Machine Learning (ICML), volume 48, pp. 974-982, 2016. ISBN 9781510829008.
Jun, K.-S., Jamieson, K., Nowak, R., and Zhu, X. Top arm identification in multi-armed bandits with batch arm pulls. In Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS), 2016.
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. PAC subset selection in stochastic multi-armed bandits. In ICML, volume 12, pp. 655-662, 2012.
Karnin, Z. Koren, T., and Somekh, O. Almost optimal exploration in multi-armed bandits. In International con- Serence on machine learning, pp. 1238-1246. PMLR, 2013.
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, A. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, -11185)1-52,20000
Qin, C., Klabjan, D., and Russo, D. Improving the Ex- pected Improvement Algorithm. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Shang, X. de Heide, R., Menard, P., Kaufmann, E., and Valko, M. Fixed-confidence guarantees for Bayesian best-arm identification. fional Conference Artificial Intelligence and Statistics (AISTATS), pp. 1823-1832, 2020.
Proceedings of the Interna-
Tanczos, E., Nowak, R., and Mankoff, B. A kl-lucb bandit algorithm for large-scale crowdsourcing. In Proceedings of the 31 International Conference on Neural Informa- tion Processing Systems, pp. 1896-5905, 2017.
Zhao. Y., Stephens, C., Szepesvári, C., and Jun, K.-S. Re- visiting simple regret: Fast rates for returning good arm. In International Conference Machine Learning, pp. 421 10 42158. PMLR, 2023.
10

---

Fixing the Loose Brake: Exponential- Taileed Stopping Time in Best Arm Identification
Appendix
Table of Contents
Lower bounds
Doubling Sequential Halving with fixed confidence (FC-DSH)
Proof FC-DSHIss Correctness
B.2 Proof of FC-DSH's Exponential Stopping Tail
C
BrakeBooster
32
C.I Proof of BrakeBoosterr' Correctness
................................
32
C.2 Proof of BrakeBooster's Exponential Stopping Tail
33
C.3 Utility Lemmas
35
D Empirical studies
39
D.1 Empirical Evaluation of Successive Elimination (SE)
39
D.2 Empirical Evaluation of SE with Brakebooster
40
D.3 Empirical Evaluation of LUCBI, TS-TCL, and FC-DSH
40
A. Lower bounds
Algorithm Successive Elimination (Even-Dar et al., 2006)
Input: 8
Initialize = S [K]. A. 0 for Vi E [K]
Sample each arm E S once
while () > 1 do
Sample each arm e S once and update P
Set S = \) : maxjes ji jas 2 v 21 (3.3312/88
++1 end while
Theorem 2.4 (Lower bound). For Successive Elimination, there exists an instance with a unique best arm where the algorithm never stops with a constant probability.
Proof. Consider an instance with = 3 arms following Gaussian distributions A11,, 1), (0.9. and (0.9,, 1). The lower bound we show here a consequence of the potential misbehave of the algorithm after pulls each arm for once. Since all of the arms have same variance, we simply denote the any confidence width, with a probability ö, of the sample mean after being pulled for / times bo.t Inf (33333(//)) by Theorem A.2. We define the following events:
E := {pr,1 S 422 3-8.1}-
Eg [VL 0, f22 (12 bs,t, u1 ba.e) }
E=:= = 14 > O, fuzt (us bs.t, uz + baie) }.

---

Fixing the Loose Brake:
Exponential- Tailed Stopping Time in Best Arm Identification
We first note that the event Ej n Eg n Eg implies that the algorithm eliminates the best arm after it pulls each for and never stops. To see this, we have
11, S μ22
-bs,11
22
-bs,1
2b,,1 S f2,1 2b8,1.
This implies that
11,1 18,1
12211
b8,1,
which is the condition for the algorithm eliminate the best arm. Next we lower bound the probabilities of the events Fr. E2, and Eg. For the event E,, by Theorem A.
IP (E1)
(f1.1 5 p/2 3b8,1)
(1z M1,1
D2 3b6,1)
1
7 (A2 + (33.1)
exp
8 8V
2
7 (4b6,1)
exp
(b8,1 ~ 1.94 A2 for 8 S 1/2)
8/ π
2
5
118
8/ π
3.3
By Theorem A.2, we have for $ 1/2,
P (E2 (()
-0)
Thus, we have
118
P
32 π
3.3
Thus with a constant probability, the algorithm never stops.
Lemma A.1 (Anti-concentration inequality (Abramowitz & Stegun, 1968)). For Gaussian random variable X NN and any > O, we have
72
P (IX - p1
20)
4
exp
2
Lemma A.2 (Naive anytime confidence bound). For Gaussian random variable X NN,, the sample mean pao satisfies
Vt 0, in E 1 1-1 202 In (3.31218) 20 In (3.312/8) /8)
p +
2 1 6.
t
Algorithm 5 KL-LUCB (Tanczos et al., 2017), adapted and simplified for distribution
Input: 5
Define: L; (T) = f. ba.7,() and U, () = f4 + bs.T.(0)
Initialize: Sample each arm once
while T4p- (T:- (1), < maxi U+(T.(1), do
Sample the following two arms:
i' = arg m A4 i' arg max (t)
Update sample mean and confidence interval
+- / 2
end while
12

---

Fixing the Loose Brake: Exponential- -ailled Stopping Time in Best Arm Identification
Theorem 2.5. For KL-LUCB (Algorithm 5), there exists instance with unique best where the algorithm never stops with constant probability..
Proof. The proof follows the same line as the proof of Theorem 2.4. We consider an instance with K 3 arms following Gaussian distributions. (V1, (0.9,, 1), and (0.9, 1). We define the following events:
Ej = { S - 1
Eg Vt > P2. (P2 6s,r, U2 + bo.t) }.
E3 Vt vt> > O. #3,t (ws bs.r, Mz + bo.t)
We first note that the event E1 n E2 n E' implies that the algorithm will never pull the best arm after pulls each arm for once and never stops. To see this, we first show that the best arm has lowest sample mean among the three arms given Ej n E2 Ez. We take the second arm an example, but same argument for the third arm,
1n, S #22 366,1
P2 6 26,,1 I P221 2b,,1 < P2211-
Thereby the algorithm will take arg max;-2 2.3 Ar as the best arm and pull both of arm 2 and the next round. Given the event Eg 0 E3, the confidence interval for arm and keep shrinking, while the confidence interval for arm keeps still. Thus arm will never be pulled again. Also given Eg n E3, the confidence interval for arm 2 and 3 will always overlap, thus the algorithm will never stop.
The lower bound of the probabilities of the events Ej O Ea E3 is same the proof of Theorem 2.4.
13

---

Fixing the Loose Brake: Exponential-Tane -ailed Stopping Time in Best Arm Identification
B. Doubling Sequential Halving with fixed confidence (FC-DSH)
Throughout this section, acute readers will notice that we may talk about events that happen in phase m without having condition that the algorithm has not stopped before. To deal with this without notational overload, take the model where the algorithm has already been run for all phases without stopping, and the user of the algorithm only reveals what happened already and stop when the stopping condition is met. This way, we can talk about events in any phase without adding conditions on whether the algorithm has stopped or not (and this is valid because the samples are independent between phases).
B.1. Proof of FC-DSH's Correctness
Theorem 3.1 (Correctness). FC-DSH runs with confidence level ò is 8-correct.
Proof. Following the definition of ò-correction in 2.1, we need prove that
PP T < 0o, 1) S.
For each phase E f1,2.... in FC-DSH, for each stage l E [|ogg [10g2(K)]] (K)]). for each arm E [K], recall the confidence width
6(m))
2
log
6K [log m²
(m,,t))
6
and define the following events:
== ViE [K], Vm E (1.2....}, A4 E [1og2(K)]] | (mm))) - u4/ s (/mee)
and
G -== E [K], 3m E (1,2,.... 3E E [1o82(K]]] [m(mm)) mi (m))) }
We first claim that the probability of event G happens at most 8. The proof is as follows
(G))
[K)
[mmme0) usl
2 em(m.e)
6K [log (K)]
m²
log
(use union bound)
8
m=1
2
(m(.))
6K (K)) m²
N mymma log
[og
2 exp
(use Hoeffding's 's inequality)
m=1
i=l
[K]
20
28
6K [log (K) m²
[K)]
3K
log, (K) m²
1=1
1=1
8
3m?
14

---

Fixing the Loose Brake: Exponential- -aiiled Stopping Time in Best Arm Identification
π²
8
6 3 (use geometric sum
Σ m== m
n²
<6. 6.
Secondly, we claim that under the event G, FC-DSH never outputs a suboptimal arm, formally, P 1, G) We prove this claim by contradiction.
Suppose FC-DSH outputs arm # I. From the stopping condition yT max; U(())
ym 2 max U
+ (m) 2 U(m)
- pJ
z ii
(m)
+ 6 ((m)
Under event G, we have jul 2 p/mr)
(m) and p1
(m) f(m)
z pr. which implies
p (m)
mmm) P1
(m)
+ mm)) 2 it
pJ
Therefore, we have μuy 2 μ1 which is contradiction.
Finally, we combine both claims to show
( 1)
= F[T< # 1, G9) 10
$ +(G)))P(( G)
<6+0=ô
B.2. Proof FC-DSH's Exponential Stopping Tail
Theorem (Exponential stopping tail). Let T3 4096H2 logg(K) log for all T 2 27,, FC-DSH satisfies
66 log,(K)
and x 4096//₂ (Kgg Then,
T
( 2 T) < exp
2k
Proof. To avoid redundancy and for the sake of readability, from now on, we assume K is of power of 2. Hence [log [K] = log, (K). easy to verify the result for any K.
Denote by m, = min m 2 1: 1/
ž max (m()) the stopping phase of FC-DSH. Then, corresponds to the total
J
number of samples at the end of stopping phase m..
It suffices to show for all phase m such that Tm 2 Ts. Pr Tm) S exp
(-
Tm (x)) Then, we can apply Lemma B. to
obtain for all T 2 2T,, (T 2 7) < exp
Recall the stopping condition: at the end of phase m, FC-DSH outputs an arm Jm. and FC-DSH will stop if condition (m)
2 max U.! (m) is satisfied.
Jm
Let be any phase such that T,, 2 Tg. We start off by decomposing probability bound according to the stopping condition (T 2 Tm)
P (phase m' failed to stop)
m'=1
< (phase m failed stop)
15

---

Fixing the Loose Brake: Exponential- -ailee Stopping Time in Best Arm Identification
PP
(m) Jm
max m!!T) 4f
1.) JJm
max U.!)) Jm # #1 Jm
T.Im)
< max U.mi) Im = if
<
+
< IP
Jm
(m)
max (m)) Im + 1) 1m
+
P
(m) Im
< U!!m Im = =1)
i
For the first term, obtain the following probability bound
P
L (m)
max (mm) if
Im # 1
$ (Jm 1)
T'm
- exp
(use Lemma B.5)
512H2 logg (K)
In phase m, for each i E [K], we denote by & the stage at which arm i eliminated. We define & to the largest stage & such that A S { 2-0,11 We observe that there are arms that have no such & and there are arms that E exists. For the former case, if an arm i has no such E,, implies A; > A g. We further split the second term accordingly
Σ P
L [yml
<.!m) Jm =1)
41
P (m)))) < u,!mm Im =1)+
Σ
P
(m) < (Liml
u,(m),
Jm -1)
1f E
A.SA +
exists
IP (m)m)) < < Jm =1)
ASSA
Σ
P P (m) ul(m) Jm = 1, 24 212 + (P(1)m) < Jm = -1,
1
exists
For the first subterm, for all arm that satisfies 1, Ai > A x we apply Lemma B.2 obtain the following probability bound
P (Z\Te < U(()) Jm =1) S exp 512H2 log. (K)
Tm
For the second and third subterms, for all arm i that satisfies i o and & exists, we apply Lemma B.3 to obtain the following probability bound
TP (m)) U!!) la 2 E2 Jm = exp (-
Tm
1024Hz log, (K)
and we apply Lemma B.4 to obtain the following probability bound
Tm P(, C; Jm 1) S exp 2048/z log (K)
Hence, for the second term, we obtain the following probability bound
[ (m)
(m) l, f Jm 1) + P < f,, Jm 1)
P
1
(m)) < U!!)) Jm =1)
S
1
A
16

---

Fixing the Loose Brake: Exponential- -ailled Stopping Time in Best Arm Identification
Σ
p (L/m
(m)) < <Ui,, Jm = 1, li (2) + +P (I
(m) < <U,T, Im = 1, es la<4% <t:)
i=1: fy exists
Tm 512Hz 1ogo (K)
exp
Tm 1024Hz logg(K) K)
Tm (2448Hz loga K)
exp
exp
i+1:
t exists
Tm 2048 2 loga (K)
2 Σ
exp
Tm
2(K
1) exp
2 log, (K)
Finally, we combine two terms and obtain the probability bound
P
L (m) Jm
max (m)) +
Jm # +1)
+ Σ P
(m)
< U(()) Jm = =1)
if1
T
I'm
exp
+ +((K - exexp
512H2 log (K)
2048H2 log2
Tm
2K exp
2048H2 loga (K)
exp
2048Hz (K) + log((K)
[6K (o) implies that
The condition Tm 2 T3 = 4096H2 (ogg(K) log
6K log (K)
Tm 2 4,96HH, loga
K log
8
Tm 2 4096H, logg KK
log (2K)
(use 8 $ 1)
T
+ log (2K) <
4096Hz log (K)
Tm
Tm
+ log (2K) <
2048/12 log, (K)
4096/1, logz
Therefore,
Tm 2048Hz (K)
+log(2K)
exp
Tm 4096H2 log, (K)
I exp
which concludes the proof of our theorem.
Lemma B.1. Suppose for all phase m such that Tm Ts 4096//2 log, (Kg log
[6 (K)
) for a constant c, FC-DSII
achieves
Tm
P ( Tm) exp
"cHz log (K)
then, for all T 2 2T', FC-DSH achieves
T
PP ( 2 T) & exp
2cH2 log
17

---

Fixing the Loose Brake: Exponential-Tane Tailed Stopping Time in Best Arm Identification
Proof. Let T 2Tg. Then, there exists such that
Tm S T mm+1-
By the FC-DSH setup, 2Im Tm+1, thus T Tm+1= 2mm
Then,
(T T)
$ P Tm)
(use T 2 Tm)
T
$ exp
cH2 loga K)
T
$ exp
(use T 2m
2cHl2 logg (K)
Lemma B.2. Let be any arm that satisfies u 1, Au >
A For all phase such that Tm 2 Tg
4096H2 logg( (K) log 6K log.(K)).
), we obtain
P (m)) <((m), Im =1) exp
Tm
512H₂ log (K)
Proof. In the following proof, we abbreviate log(.) log
[6K (Kg,(K)mm) for clarity.
We have
(m))
< <U(m), Jm =1)
P
P
P1
(m)
(m,,t log(-) < p!!"m) + (m..e.) log(-); Jm =
2
2
(by the definition of (m) and U (m)
PP
11
(m)
plm)
N(m.aa
2 log(.) + V N(m log(-), Im =1
2
TP
(m)
(ml))
2 ((m.f.)) log(-), Jm =1
(since Jm = 1, N7(m6)) > -V(m.e))
(m)
pm()) + t < Au 2 (m,,e.) log(-), Jm =1)
2
IP
p1
Lemma B.6 states that for all arm u such that u + A. 1 K. for all phase m such that Tm 2 Tò, N(m.t))
32
log
6K (og,(K)m² This inequality implies that
A7
(mm.ta)
32
6K loga (K) )m²
log
A
8
32
6K log, (K] )m²
log
(m,.C.))
8
6K log (k)m²
A 2 / N(m.fa)
log
5
6K log, (K) )m²
An
3
A, +2
log
5
2
18

---

Fixing the Loose Brake: Exponential- -ailee Stopping Time in Best Arm Identification
Hence,
IP
11
(m)
141
(1() + pa
-Au +2 (m,,te
2
log
6K log2 )m²
Im =1
8
(1 - IP
(m)
11 p!! + Pa <
Au
Jm =1)
2
Au
P
(1
(m)
M1 p((
Muu
Lu 2, Jm =1)
A
exp
(use Hoeffding's inequality)
2=1
N(m.))
+ a(mm
(2
Σ
exp
(use L 2 1 and 2 2 1)
A
Tm
(by def N
exp
16
logo (K)
K To (K)
A K
Tm
(use A, > 1
exp
64
K logg (K)
L
A
Σ
K
Tm
exp
K
256 logg K)
Tm
Σ
exp
(by the definition H2 max; i
H2
256 loga (K)
L
Tim
Σ exp
256H2 loga K3)
T'm
< logg (K) exp
25 log (K)
Tim
exp
+ log(log2(K)))
256HHz loga(K)) (K)
The condition Tm Ts 4096/12 logy(K) log
6K log, implies that
66 1ogg(()
Tm 2 4096Hz log, (K) log
T > 512/22 log (K) log (log, (K))
(use 8 S 1)
Tm
log (logg (K)) <
512H2 log, (K)
Tm
Tm
log (logo (K)) S 512Hz logg(K) K))
256Hz logo K)
Therefore,
T
exp
log(log,(
256H, log,
T
S exp
512Hz logo (K)
19

---

Fixing the Loose Brake: Exponential- -aileed Stopping Time in Best Arm Identification
Lemma B.3. Let u. + 1 be any non-optimal arm. For all phase m such that Tm. 2 To = 4096H2 log2 log 66 loga(K)
assuming E exists, we obtain
P (L)m)) (m(m) U lu Eu. Im =1) I exp (-
T, 1024Hz log, (K)
Proof. Recall that Ey is defined to be the largest stage l such that A.. S 1 N 2-+11 In the following proof, we abbreviate
log()) () = log
6K (og,(K)) (m)m²) for brevity.
We have
P
1 [m)
< (7(m)
Lu 2 Ey Jm =1)
P
P1
(m)
2
log(-) < p!(m)
2 log(-), by Eus Jm =1
N(m.ti)
(m,,6.)
(by the definition of I, (m) and U((m)
P
11
(m)
N(m.e))
2
log(.) < p(m) +
(m,,tt
2
log(-), lu 2 Ey Jm =1
(use l, 2 Et
(m)
2 log(.) ((m,6) log(.), lu 2 Eyp Jm =
P
<
((m,et)
P
11 (m)
p!m)) < 1 N(m,ey)) log(-), lu 2 lu Jm =
(since Jm = 1, N(m.4)) 2 (((m.))
(m)
f1 p!m) + < A. + +2 A(m.et) log(-), lu 2 Eu. Jm =1)
2
P
Lemma B.7 states that for any arm such that + and ty exists, for all phase such that Tm 2 Ts. N(m.E.)
32 log
6K log,(K) log,(K)m²) This inequality implies that
32
6K log, )m²
((m.
2
log
A
8
32
6K log,
(K )m
log
N (m..)
8
2
66K logz K mm
A 24 N(m.a))
log
6K log, (K)m²
An
3 Au + 2
log
N (m,,))
2
Hence,
P
P1
(m)
11
pi(m)
+ Mu A
2
2 N(m.e.)
log
6K log, (ess((K)r (K)²²
e. > Cg Jm =1
P
11
(m)
11 ((())
+ thu <
A
ly > 60 Jm =1
2
Au
IP
[1] (m)
11 (m))
phu
l 2, Jm =1
(L logg (K))
==
20

---

Fixing the Loose Brake: Exponential- -ailled Stopping Time in Best Arm Identification
cxp
(use Hoeffding's 's inequality)
2
Nim. +
N(m,a)
exp
(use L 2 E. and 2 w
16
A
Tm
(by def' ((m.f))
Tu 5 log (K)
exp
16
2 +1
K logz (K)
There are two cases: (1) 2 c 2 1 and (2) 2 fu < 1.
In the first case: by the definition of ty, we have A x.2 2- D.. Thus, we have
A
Tm
exp
16
2 22
K logo(k) (K)
2
T 42-
I'm
exp
64
2 2-t
K logz (K)
A 22
Tm
exp
2 22-6 e
512 logz (K)
Tm
< exp
(by the definition H₂ max; iA,3)
H2
512 logg (K)
Tm
exp
512Hz logg (K)
In the second case 2 f
1, we have
2 6
i
exp
16
2 P
K loga (K)
A
Tm
exp
128
K 2-
loga (K)
A
T
(use K2 fh < 1)
exp
128
logz (K)
A
T'm
exp
(use u 2 1)
128 logg
ufm
exp
(by the definition H2 = max; iA,3)
H₂
128 loga (K)
T
-exp
128 Hz loga (K)
TH
S exp
512/2/ log2 (K)
In both cases, we have
A2
T
exp
16
2
F2 +1 K log K)
21

---

Fixing the Loose Brake: Exponential-Tee Tailed
Tailed Stopping Time in Best Arm Identification
Tm
< exp
512Hz log, K)
Therefore,
A7
T m K 1ogg (K)
Σ exp
16
2 2u +
x=
Tw
exp
512Hz log, ())
==f:
Tm 512Hz log (K)
I logg (K) exp
Ti (-512Hz (K)
< exp
log (og(log((K)
The condition Tm 2 Tg = 4096H2 logz log
6K (ogg(K) (K)
implies that
6K (K)
Tm 2 4096H2 log2 (K) log
Tm 2 1024Hz logz (K) log (logz (K))
(use ô S 1)
Tm
+ log (log2 (K)) - 1024H/2 (K)
Tm
Tm
512Hz (K) + log (logy(K)) 5
1024Hz loga (K)
Therefore,
Tm
exp
+ +log(log>
512Hz (K)
T...
exp
1024/1/ logo (K)
Lemma B.4. Let * 1 be any arm non-optimal.
For all phase such that T. 2 TB
4096H, logg(K) log 6K (k) assuming f, exists, we obtain
Tm
P Pl. ( S exp
(2048Hz log (K)
Proof. Recall that t to be the largest stage such that A, S 1 k-2-1+1 We denote by A the set of arms at stage f. In the event arm does not survive until stage e We have
P (en, ( PEL - 11]: A As)
(u & Aeti,
(use union bound)
Σ
Σ
P us Ae, Ae= ar)
(use the law of total probability)
1=1
K]]
WEnE:
14//=K-2-641
22

---

Fixing the Loose Brake: Exponential- Tailed Stopping Time in Best Arm Identification
Σ krC
P(u & A4T1, u A Ar= (e) ae).
uEag |ac|=KK2 211
By the setup of the FC-DSH, stage f, the event arm u is in set Ae but is eliminated next around means that there exists set A C AA that half the size of A such that vi E A, Paa I fág. Formally,
P(u Act1, u A A = az) P(A:= = a
KEaz.
|0c| K2
P(3AC Ae, s.t. |A| Ac,
Ael
vi E A, Po S A at P(A. as)
2
MEng:
|ar|= [r|=K2 1+1
P BA ag, s.t.AA|
lael
vi e A, ia S pi Ar - az p(A== at).
2
1=1
KrC
MEdg
|ag|=K2 K2
Let A C. ag be a set as described in P(.) above. We denote by Boty (A) a set of arms with | - j lowest means in A. Formally, Bot, (A) satisfies that (A) S (A) = |A| - j. and Vx (A), Vy E A Ao,o (A), ps= S My
We denote pa (A) be mean of the arm indexed within the set A. Also to make it clear, we denote (4;(K] to be mean of the arm indexed within the whole set [K]. i.e., (4((K) μ4
We set j ||| leel
we obtain the following properties
|Bot (A)
A 2
lmsl 4.
E Bot, b S (IA)
(A) S MIA1 ([K)) - Mayl ([K])= S Maal The first inequality from the setup of (ot,
2
The second inequality uses the fact that if A S [K], hence Vi, (A(A) S (x(())
Within stage l < f - and set ag E [K] such that u E ag and lael = K2- E+1, we focus on the probability
arl
P 3A C ag, s.t. AAI|A||
Vi E A, Pa S ps As at)
2
lael
S P 3A C ag. s.t. |A| =
Vi E (A), io S is Ar at
(use Bot, C A)
Within the condition A/ C az, s.t. |A| = 2
Lael
Vi E Bot, we have
Auu S م.i
+ fuu Huu fb + pi S pu + ui
7 Pru Hu i4 + p4 pm We
(use the property l4 S Med
e fbu
Pu f4 + 14 S A. - A [oa
7 ihu Pu i0 + 14 S
2
A
52 4:11
A wd
(by the definition A, S A x2 111
1
* Br Pa P. + p4
2
A
K2
111
Auuel
(since ( < t.)
1
6 f40 pm p4 p4
A
(use |az| K2-(+1)
2
3 fk - Pm i4 + μ4
<
A
2
23

---

Fixing the Loose Brake: Exponential- -ailled Stopping Time in Best Arm Identification
Thus, have
ael
P
3E C ag, S.t./A|
Vi E (A), Pu S i4 Ae = 0t)
2
acl
$
P
AE C dg, S.t/A|
Vi E (A), Pu Mu p4 Ms - - [u A at
2
ad
Vi (A), (Bw. Mu S -
(i μr 2 A
A =
P
C de, s.t.
2
fh Ma S - -
< P
1. at
loel
P
]A C de, s.t. s.t.|A|
vi E Bot,(A), i4 Mi 2 A | Ae Ae az
(use union bound)
2
ii Ma S A
|apl
1A at
1
Σ
P
Vi Bot, is pi + 1 A0gl A
ACar |A| 1d
A2
A2
N(m.e)
N(m.e)
mel
S exp
+
Σ
exp
-|Bot,(A)
(use Hoeffding's 's inequality)
2
16
2
16
ACos
| |A|=|
(m,.e)
2
Las
(m,
2
[ogl
exp
4
+
exp
4
(use property (Bot((A) = (nc))
2
16
4
2
16
ACes
|A| |A|=!eel
2
2
(
[y
[ael ad
lael (mm.e)
exp
+
exp
2
16
2
16
Apy
A
(m,
leyl
|ag| N (m,
I exp
+ (2c)
exp
(use Lemma B.9)
2
16
2
16
A
A
(mm.))
lag
(m,,))
aae
exp
+ exp
log(2e)
2
16
4
16
2
We apply Lemma B.8 that shows for all phase m such that Tm To, (m,
2
log (2e). This inequality also means
A²
that
256
log (2e) (m,.e)
2
(m,.))
ml
+ 8 8log (2e)
<
2
16
A
[rl (m,))
[,
* lael log (2c)
8
16
2
lael
ar (m,
[yy
log (2e)
<
2
8
2
16
24

---

Fixing the Loose Brake: Exponential- Taileed Stopping Time in Best Arm Identification
2
2
lael ((m,))
Lae
|az|
((m,6))
+
log (2e)
4
16
8
16
Thus,
2
4 Tool
(m,e)
loel
|ao|
(m,,e)
lad (2g)
cxp
+ exp
+
2
16
4
2
16
2
A
A
N
lael (m,,)
uel
Σ exp
+ exp
2
16
8
2
16
A2
A
(mm.))
[yy
1 (m,e)
S exp
+ exp
(use arl 2 1)
8
2
16
2
(ma,))
exp
256
2
2 2-1+1 (m,.)
exp
(use |azl = K2-(+)
256
By the definition (mm.f)
T
we further have
2-1+1 K logg(K) (K)*
A
k2-4+1
Tm
exp
256
2 1-1 (K)
2
K 2- e41
T'm
2 exp
K 22-8-1 4
8-1
1024 logg ( K))
Tm
< exp
(by the definition Hz max; i
H₂
1024 log 2og)(K) (K) I'm
exp
H0 log, (K))
To summarize, we have obtained the following probability bound
lael 2
T 1024Hz log K)
F 3 C ag, s.t. |||
Wi A, im. S i. Ar
at
S 2exp
Therefore, from the beginning derivation, we obtain the following probability bound
(C.
(
-1
Σ
Σ
& u u A = TP = az)
t=1
uEdr.
loz| Oel=K.J K.2
T 1024Hz log, K)
Σ
exp
P (Ae at)
Oe CI]::
HEO |a 1/ -441
1
Tw -1024H/2 loga K)
2 2exp
1=1
25

---

Fixing the Loose Brake: Exponential- -ailled Stopping Time in Best Arm Identification
Tm
2 logg (K)
exp
(use Ey S (K))(K))
(024Hz2 logg K)
Tm 1024Hz logg (K)
= exp
+ log(2 logg (K))
The condition Tm Ts 4096//2 logg(K) log
6K (K)
implies that
6K (K)
Tm 2 4096HH loga ( log
Tm 2 2048/1 logg (K) log (2 logz (K))
(use d 5 1)
T'm
log (2 (og) - 2048Hz logg(K)
Tm 1024Hz (
Tm
log (2 logz (K))
2048H2 logg (K)
Therefore,
T 1024Hz loga (K)
log(2 log, (K))
exp
Tm 2048Hz 1og2
I exp
which concludes the proof of the Lemma.
Lemma B.S. For all phase such that Tm 2 Ta 4096Hz logz log to oulput arm at the end of phase m satisfies
6K 1og;(K))
)
the probability that FC-DSH fails
Tm
PP (Jm * 1) S exp
512H, logz (K)
Proof. While one can directly use the proof of Karnin et al. (2013), we present here an alternative proof that has an pedagogical value - this proof shows more fine-grained control of events that reveals that the bottleneck of the guarantee the bad behavior of the best arm rather than the bad behavior of the bad arms.
We denote by A the set of surviving arms at stage f. We denote by & the stage at which arm eliminated. The event that Jm * implies that arm 1 does not survive until the last stage L, i.e., & < We have
P (ei < L) P( S L -
1:14 11:11:
A Ae)
P(1 A4H1 1E
(use union bound)
Σ
PP LE, A
(use the law of total probability)
a<C[K]:
lear.
|e<|=K-2 K-2 211
Σ
Σ
( A P(A ae))
C|C
1eag. |ad|=K-2-
By the setup of the FC-DSH, at stage f, the event where arm set Ar but eliminated next around means that there
26

---

Fixing the Loose Brake: Exponential-Talled Stopping Time in Best Arm Identification
exists set A C Ae that half the size of Ae such that Vi A, Pu S jug Formally,
Σ
Σ
P(u 1 A - ar) P(A. - =as)
LEaS. |ar|= [r|=K2-" K2-
Σ
P 3AC Ar, S
Ad
Vi A, in SmI ar
1 ( - az)
2
[K] lear,
| |= K2 K2-1+1
Σ K
P 3A ag, s.t. |A|
ag
vi E A, P SAi al P (AAe P(Ac= at).
t=1
1Ear. |0c|=K2" K2-1+1
Let A C dg be set as described inside P... above. We denote by (A) be a set of arms with AA| - lowest means in A.
Formally, Bot, (A) satisfies that (A) [ A., [B)) = |AA j. and Vo E (ot, Vy E A Bott (A), Ps S My.
We denote μ4 (A) be mean of the arm indexed within the set Also to make it clear, we denote μ4 ([]]) to be mean of the arm indexed within the whole set [K], i.e., (4([K] p4-
We set j = [ lael I
we obtain the following properties
(Bot,(A) ا lesl Vi E Boty 14 S may
(A) (A) S magi ((K) = Mare ([K]) Σ Maal- The first inequality from the definition of (A), The second inequality uses the fact that if A S [K], hence Vi, ma(A) (x((K]
Within stage l < L - 1 and set a₂ S [K], 1 E az lasl = K2 ++1, we focus on the probability
arl
P
34 C az, s.t/AA/
Vi E A, Ar S i4 Ae =
2
arl
< P
AE C ag, s.t.AA
Vi
(A), ia S ju A
2
ag
P
AE C ag, s.t/A|
Vi Bot, ia 1n1 ia + 14 S -11 + p4 Ar =
2
ag
< P
34 C ag, S.L
Vi
A1 -1-11- iu M4 - + Mayl Bot,
Ae ae
2
(use the property br S Mlao
arl
3E C ag, /.t.AA|
Vi (A), A - -1111 -11--4 +
S - A uool A = at
2
|
1 - ) v (4:
1 u4 2
2 A1ny)) )
S
3A C ag, s.t.
|A|
Vi E (A), (A1 (01-11 u1 S
| = at
2
2
1
S
(1 - M1 S 1- 1 A = at
= lael
+ IP
3A C ae, s.t. |A|
ViE (A), -4-4 11: - A = at
(use union bound)
1
S (1 - 11 S -
-
2 |ecl A = at
Σ P e Bot, (A), As 2 p4 + 1 /
+
Ar = as
ACas |AI=|% [2d
27

---

Fixing the Loose Brake: Exponential- Tailed Stopping Time in Best Arm Identification
A
4 x
N)m,e)
N(m.e)
I cxp
+
Σ
exp
(Bot((A)
(use Hoeffding's 's inequality)
2
4
ACRE
|A|=|oal
2
A
(m,,t)
m
lael
(m,,)
(use property |ot,, (A)) (
exp
+
exp
4
ACa::
|A|
|A|=
A
A
N
Loel
aael
(mm,e)
exp
+
exp
2
4
4
2
A
A
((m.t)
ledl
|ar|
(mm.))
$ exp
+ (2e)
exp
(use Lemma B.9)
4
A2
A
()
lasl (mm.e)
|us|
exp
+ exp
log (2c)
2
4
2
We apply Lemma B.8 that shows for all phase m such that Tm 2 TT, (mm.e)
2
256
log (2e). This inequality also means
A²
that
256
log (2e) (mm.ee
2
2
(m,.)
++ 32 log (2e) 5
2
4
lae (m,e)
Tuel
+ 4|arl log (2e)
5
2
4
2
lael
[rr
(m,
leel
log (2e)
2
8
A
A2
lael (m,,))
Inel
lael
|ad|
(m,.)
+
log(2e) 5
4
8
Thus,
2
2
(m,
lael
(m,,)
lasl log(2e)
exp
+ exp
2
4
4
2
2
2
2
fm,
Teal
lasl (m,.)
Tcel
< exp
+ exp
2
4
8
2
4
2
2
em,
leel
(m,.e)
A exp
+ exp
(use aael 2 1)
2
4
8
2
4
(m,,)
<2exp
64
28

---

Fixing the Loose Brake: Exponential- -ailee Stopping Time in Best Arm Identification
A
22 e(1a))
= 2exp
(use (ax] = K2 k2-
64
By the definition N(m.0)
Tm -- (K))
further have
A 2--6-1
Tm
exp
64
2-(+1 K logg (K)
2
1 2-2411
Tm
exp
2-
256 log2
1
1
T'
< exp
(by the definition H₂ = max; iA,3)
H2
256 logg (K)
Tm
exp
256 log2 ( (K)
To summarize, we have obtained the following probability bound
odl 2
Tm 256Hz log2 K))
IP 3 ae, s.t. s.t. |A|
ViE A, A S A. A =
< exx
Therefore, from the beginning derivation, we obtain the following probability bound
(lu < L)
L-1
Σ
P(u E Ae41, W AeAe A :as= P (Ac az)
8=1
1Ear.
|a MollKK' K-2-
Tw
Σ
2 2xxp
P(A: oz)
256H, log, (K)
K
LERE.
|a=|=K-2-<4+
Tm
2exp
256H2 log K))
T
< 2 loog (K) exp
(use L logg(K))
256/12 logg (K)
T
log(2 ( log (K))
(K))
exp
225HH logg (K)
The condition Tm 2 T3 = 4096H, (og log
6K (oKoo
implies that
6K (Kg
Tm 4096/z log, (K) log
8
+ Tm 2 2048H2 Jog, (K) log (2log2 (K))
(use 8 S 1)
= T. 2 512H, logg K) log (2 log, (K)
Tm
log (2log, < 512Hz (K)
Tm = 256Hz (K)
T
+ log (2loga (K)) S 512H, loga (K)
Therefore,
T
log(2 logg
exp
256Hz log, (K)
29

---

Fixing the Loose Brake: Exponential- Tailed -aileed Stopping Time in Best Arm Identification
T'
exp
512H2 log2 (K)
which concludes the proof of the Lemma.
Lemma B.6. Let # 1 be any non-optimal that satisfies A. > A For all phase such that Tm 2 T3
4096/1, logg(K) log (ogg(K)) the number of samples used at stage Lu when arm is eliminated, satisfies
((m..t)) 2 log
32
6K (Kgg(K)m²
A
8
Proof. We start from the condition T.. 4096H2 log2 (K) log
6K log,(K) and obtain the inequality follows
6K logz (Bz2(K)) m)²
Tm 2 4096Hz (K) log
K 1og2(K) log
6K log2 (K) m)²
7 Tm 2 1024
(by the definition H₂ max;22 iA,
A
2-
6K loge K m
3 Tm 2 1024
log2 (K) (K) log
(use 1 2 2-(u)
A
5
x
T
128
6K log (K) )m
4 K2 f.+1 +1 1og2 KK)
log
A
$
128
6K log, ( )m²
(m,f.)))
log
(by the definition of ((m.e)
A
128
6K log (K) m
N
log
(use A. > A
412
32
6K logg (ogg(K)mi) (m)²
+ (m,.fa)
z
log
A
5
Lemma B.7. Let u. + 1. be any non-optimal arm. For all phase m such that Tm. T's 4096/1² logg(K) log assuming t exists, the number of samples used at stage t satisfies
6K log, (K)
(( 2 log
32
6K logg(K)m
A
Proof. Recall that t is defined to be the largest stage e such that A. < A 2 2-1- For any arm u E [2, K], since it survives until stage c. by the definition, it satisfies 1 A A S S A
We start from the condition Tm 2 4096/1, (K) log
6K (K) and obtain the inequality as follows
6K log, K m2
Tm 2 40 log, (K) log
K -
6K log, KS )m²
Tm > 1024
lKgz(K) log
(by the definition H₂ maxx22 i
A
6
k 4
30

---

Fixing the Loose Brake:
Exponential-Tailes Stopping Time in Best Arm Identification
Tm
128
6K log2 (1H2(KK)n K)mm
log
K2
log2 (K)
A K x-2-tt
128
6K logz (K)=²
+ *N(m))
log
(by the definition of ((m,))
A 4-2
128
6K logz (K) (K)m²
log
(use A. 2 22Ag.2-0
4
(
32
6K logz ( m
log
) the number of samples used at Lemma B.8. For all phase m such that T Ta 4096Hz logg log
6K log,(K)
stage where ael K2 -2-t+1, 1+1,
satisfies
256
log (2e).
A
hy
Proof. We start from the condition Tm 2 4096H2 log, (K) log
6K (Kg
and obtain the incquality as follows
8
Tm 2 4096H2 log (K) log [6K log2(K)
8
= Tm 2 1024Hz log, K log (2e)
(since 5 S 1)
K
2-1+1
+ Tm 2 1024
4
logg (K) log (2e)
(by the definition H₂ max22 iA,3)
2
2-
T
256
<> 12-4+1 logg
2 log (2e)
K)
$ 2+1
256
<> N((,E))
2
log (2e)
(by the definition of (m,)))
2
A
4 2-1+1
256
+ (mmm))
log (2e).
(acl (2-++1)
md
Lemma B.9 (Stirling's formula (Das, 2016)). Let k. be two positive integers such that n, then,
k
en
<
31

---

Fixing the Loose Brake: Exponential- Tailed Stopping Time in Best Arm Identification
C. BrakeBooster
C.1. Proof of BrakeBooster's Correctness
Theorem 4.1 (Correctness). Let an algorithm be do-correct and have sample complexity of TV (A). Suppose we run $)
BrakeBooster (Algorithm 2) denoted by M with input A, 6, L1
[ (Alog(1+
1.
Ti Z 1, and do S [26]2. Then,
log 1ehu
(T((M) oo, J(M) +)
In this proof, acute readers will notice that we often talk about events that happen in stage (r, c) without having a condition that the algorithm has not stopped before. To deal with this without notational overload, we take the model where the algorithm has already been run for all stages without stopping, and the user of the algorithm only reveals what happened already and stops when the stopping condition is met. This way, we can talk about events in any stage without adding conditions on whether the algorithm has stopped or not (and this is valid because the samples are independent between stages).
Define
Qr. = {e E [L,cd E-th trial
self-terminates and output incorrect arm).
Note that
P (T((M) < 00, #1)
&2) (Jre & (0,1))
(Jr (0,1)).
==1==1
where, E1, &g are shorthand for
ε = (Au E [r- E [u], Ju, = 0},
& (Aw e [c 1], Jr.w = 0}.
stage outputting an incorrect arm index means that
1. More than half of the trials of A has self-terminated; i.e., up S [br,o/2] and thus Eie[K] v Lnn - [mne/2].
2. The majority vote of those terminated trials an incorrect arm index; i.e., Eie [2 us 2 1/2 Eie(k) vi
Thus, we have
1
Lrve
1Qnel=
Σ
2
1 (Lno Lbme/2)) 2
4
ie K)
which implies that
Tange
Σ
(Jra & (0,
< ΣΣ>>
Orsel 2
4
Algorithm A being dy corrett implies,
P( trial self seff-terminats and outputs an incorrect arm)
6g.
Hence by Lemma C.3 in the appendix with d = do whose requirement &g < a is satisfied by the assumption of the theorem,
Lrc
ΣΣP P
10rcl
32

---

Fixing the Loose Brake: Exponential- Tailed Stopping Time in Best Arm Identification
Line
exp
log(
4edo
8
r. ((.2(1-)) L1
1
exp
log 4ed0
00
p=l
2 L1
Σ
exp
log(
4
4ed0
==
[ing(1+))]
322 by evaluating an infinite sum (see Lemma C.2), we conclude the proof:
Since I
lox 4000
r. 2-2 log( Acdo
exp
k=0
3
-r -rlog(1 [1 + 55)
exp
2
r=
3
exp
(- -loog(1 1 + 1))
(geometric sum)
2
exp ( loogoll + 4))
3
I 8.
One can see from above the reason why we set Lyye to be x r2"-1 rather than x 2n-1 in the algorithm without the extra factor of r, the sum of will not be controlled.
C.2. Proof of Broke Exponential Stopping Tail
prove a slightly more general version Theorem 4.2.
Theorem C.1 (Exponential stopping tail; full version). Let an algorithm A be ôn-correct and have high probability
sample complexity Th, (A). Suppose we run BrakeBooster (Algorithm 2) with input A, L
44ogg 2) Ti and
log I00g
50 (1)) Lei To = 2 1 1
166 In where T =T%, (A) V Ti. Then,
T
1
VT To: (T( 2 T) < exp 768T7, (A) logg T In
80
Proof. Letr" minfr r N4, Tr. 2 T7, (A)). Let Tre be the total amount samples consumed up to and including stage (r, Define R, = {e E [Lr.cl E-th trial does not self-terminate }.
Let > r". Then,
(T((M) 2 Fr.o) P
Note that the fact that a stage returns 0 implies that more than a half of the trials did not self-terminate. Thus
P(Jr-1r- = 0) S P (3 at least (LLr-1,r' /2] + 1) trials that do not self-terminate
s P R 1,- 2 1
Since the trials in stage - 1, r*) use samples more than Thi (A), by the sample complexity guarantee of A and Lemma C.3, we have
-y-1,r'
L, Ly-1.r'
1
IP [
< exp
log
2
2
2e00
1-r'-r'
(r
1)L1
< exp
In
(vop S +
2
%o
33

---

Fixing the Loose Brake: Exponential- -aileed Stopping Time in Best Arm Identification
2r-1-r
(r
1)L
= exp
In
4
80
Note that by Lemma C.5, we have, Vr 2 2,
T T1
Tre
Tr. 2
1 1927 -T1122"
=
r S
log2
2
T
Then,
2r-r' -1 L1
1
P ((T(M) 2 Tr,0) = exp
(r
1)
In
4
80
2r-r"
$ exp
In
-222--13
8
00
2 L
= exp
2 r
In
50
2 TT 2r
= exp
8 2
50
Tr.o/3 In
N exp
(Theorem C.5)
8Tr - 2n
00
T, Ty.e/3
N exp
In 50
(Theorem C.4; T := =T, (A) VT)
8Tr 7i
l In
1
exp
64r T* 50
$ exp
Tro/3
In
1
(r 2,r S log2
T L,T.
S log T,
647 loga Tr,e
5n
Hence,
T,e log,
V* Ve P(r(M) 2 Tr.o S exp
In
1927'
The
80
Next, in order to obtain an exponential stopping tail guarantee, we need to upper bound (P( 2 T) for every T that is sufficiently large instead of those particular T Tye's. 's.
Let T 2 T--41.1- We consider two cases.
Case 1. T [Tre, Trec1) for some r > r" and Cr 1. In this case, we have
Tr,c-1 = Tre + T/
T Tr,t1
Ti 21 i7
= +
Tre
T,e
< 1
(Tree 2 Tiks . 22-1,12 2
Tiln 2
2
2
1
(8)
< 2
(122++122)
34

---

Fixing the Loose Brake: Exponential- -aileed Stopping Time in Best Arm Identification
This implies The ST < 2T Then,
(T((M) &P)( T.,))
T
1
S exp
1927 log2
Tr.e
60
T
S exp
In
(The ST < <2I,,)
3847 logz
60
Case 2. T (Trr 1r+1,1 for some r r". In this case,
Tr41,1 Tr. + 2
Te+11
+ (r+1
Ter
Trr
$ 1 + Ti
(T, 2 TiLı 22-1, 2
T1L1 .p2
1 + +(r
p2
4
(r
Thus, we have Tyr ST < 4T,r and
P(T(M) S P (T(M) 2 {
Irr)
Tr.
S exp
In
1927 loga Tr.
60
T
S exp
In
Frr ST < <TTr,)
768T loga T
50
Therefore, in either case, we have
T
1
T T2T P (T(M) 2 T) S exp
(778T+ logz T
In
d0
We conclude the proof by working out an explicit upper bound on 7,-+1,1 as follows:
T,-41.1 S +,,+1,+++
< 2" 3(r" +
1,
(Theorem C.5)
87
167
.3logz
ya
In Ti
(Theorem C.4)
Tj
Tj
167
< 247 logg
Li
Ti
C.3. Utility Lemmas
In(1+3)
Lemma C.2. Let 3 >
0, 0, 0, (), and du E (0.1). If.
L1 2
then
In( G00
11
2 In(n + )
Σ
exp
-a
ln
<
exp
-a
360
2
35

---

Fixing the Loose Brake: Exponential- -aileed Stopping Time in Best Arm Identification
Proof.
50
2
L1
Σ
exp
In
350
L
1
2
4h
exp
In
exp
In
+ exp
In
360
[300
3ó0
L1
1
2
3L1
exp
+
exp
In
+ exp
In
+
3d0
[300]
360
exp
L1
In
Boo
(geometric sum)
exp
-0
La
In
al1(1+)))
Let 11 2
Then,
Iu
860
Lı
exp(-aln (1+
exe
exp
a
In
a
350
1
(1 + 2)
1
21
(a 2
(1 ())
1
(6
(1+
2
3
Thus,
exp
aa
a
In
300
(-a-In
In(1 + 2))
2
exp
1 exp
-a
Li In
350
which completes the proof.
36

---

Fixing the Loose Brake: Exponential- -aileed Stopping Time in Best Arm Identification
1. Let N be the number of Lemma C.3. Let & be an event from random trial such that P(E) S 8. Let satisfy trials where & holds true out of L independent trials. Then.
P(N 2 aL) S exp
(aaLlog
ed
Proof. Recall the standard KL divergence based concentration inequality where ün is the sample mean of n Bernoulli i.idd random variables with head probability ja:
Ve 2 0, P(n, la S e) S exp(-nKL(p + + E,
Note that N/L. can be viewed as the sample mean of Bernoulli trials with == TP(E). Then,
P(N aL) P 2 a)
N
P( μ 2 a
S exp(
- (K,
(a> m)
a an
= exp
11
+
/1
(a)
a - aa
(
exp
14
exp
- Taalnn
In(
ep
where (a) is by the following derivation:
1 1 0
1- 1
a) In
-(1 a) ln
1 a
- a) ln
1 1+ 1-a a
21 a)
(Ve, (n(1) 5x)
1-6 a
-(a n))
2 aa
Hence,
PPN 2 aT. < exp
(Taaln(
exp
(-Ta In( @
(p= (P())
Lemma C.4. Let Tr,r 1T, for some
and define T = T Ti. Define r* minfr N. Tr, T*)
Then,
87
< logg
T
Proof. Consider two cases:
r* 2 2: In this case,
T
TT--1,p--1
22'-TT
47
x* < logz!
(ii) r* $1: Nothing to do here.
37

---

Fixing the Loose Brake: Exponential- Taileed Stopping Time in Best Arm Identification
Together, have r* < logg 4 < V V logg loga( 14g)(47))) (T)) 2 2.0. 0.
y 7i
log2
8T Ti
where the fact that Va, b 2 0,a a and
Lemma C.5. Let Tr.e be the total number of samples used in Algorithm 2 up to and including stage (r.c). ffr 2 2, then
Tr.c
<
33
22
T1
Proof. For the upper bound,
Tr S T S
11 2" LIT
==1 c=1
-r222-1 r22+1
- -3)-"-3)L1II
22 6
3r2
(6 2r
For the lower bound,
r-1
Tr.c
TL 20-1 + Σ ---1-
u L1
2u-1 + -Til 2-
T:41
2 2 4r+ +6 6)
-3
+Tih 2--
2 TiL
2
2 4r +6
+TiL1 2
Tihn
2--1
( 3r +0) -
Ti
2r-1
2r 6r + +12 -
2
Ti
2" ,
T T1
2" (,2 6r + 12)
2
TiL 2- 1 +
Ti
2--1 (72 6r +9 9)
(r
ThI .2' 1²
T T4
2
11((
(r - 3)
2
T1I1 2" -1 ,
38

---

Fixing the Loose Brake: Exponential- Tailed Stopping Time in Best Arm Identification
D. Empirical studies
D.1. Empirical Evaluation Successive Elimination (SE)
In this section we present the study of stopping time distribution of Successive Elimination (SE) (Even-Dau et al., 2006)
algorithm.
Experimental setup: We implemented SE in two different configurations, 1) Original version 2) Version with e-slack added to the stopping condition. We set the number arms 3, with mean rewards (1.0, 0.9, 0.9). Noise follows (O0 1). We set ò 0.01. We conduct 1000 trials and observe the stopping times of those trials. We forcefully terminated the trials that do not stop until 30,000 time steps 1,000,000 time steps. In Figure 5, 6 we have plotted the histograms of observed stopping times for all the trials.
eps 0.03
60
100
eps 0.01
eps 0.05
Number of Thials
50
Number Trials
80
40
30
40
20
20
10
0
10000
15000
20000
25000
10000 15000
25000
30000
Stopping time
Stopping time
(a) Original version of SE
(b) SE with s-slack added to the stopping condition
Figure Histogram of stopping times (force stop after 30K rounds)
200
eps 0.03
175
800
eps 0.01
150
eps 0.05
Number hhals
Number of Trials
600
125
100
400
75
50
200
25
0.0
0.2
0.4
0.6
0.8
1.0
100000 200000 300000 400000 500000 600000 Stopping time
Stopping time
(a) Original version of SE
(b) SE with e-slack added to the stopping condition
Figure 6. Histogram of stopping times (force stop after 1M rounds)
Observations: In the case of original version of SE, considerable number of trials have not been terminated even after 00,000 time steps (Figure 5a). We have observed that all these trials have already eliminated the best arm, and thus we expect that many of them will never stop. This also confirmed by Figure 6a where most the trials that did not stop after 30,000 time steps are still running after 1, 000, 000 time steps. This shows that a high probability stopping time bound does not guarantee that all the trials will stop.
In the case of SE with slakack added to the stopping condition, first, we can see that for 0.01, 0.03, still some of the
39

---

Fixing the Loose Brake: Exponential-Tune Tailed Stopping Time in Best Arm Identification
trials not terminated even after 30,000 time steps. It takes up to 600, 000 time steps for all the trials to terminate. This significantly higher discussed in the main part of the paper.
Moreover, once the best arm is eliminated, the rest of the procedure can be considered as uniform sampling when A = E. Hence, as we have discussed in the main part this paper, the stopping time distribution will follow (Ts, -)xxxpnnenti stopping tail with TB- = ((KE ((KK==I(L188)
ln(1/5)) and A = ((KE")) ). The same goes for more general cases as well. However our proposed algorithms achieve a better (0(H, In(1/6)), expponettaa stopping tail.
D.2. Empirical Evaluation of SE with Brakebooster
In this section, we examine the impact of incorporating the Brakebooster algorithm into the Successive Elimination (SE) framework, where Brakebooster operates by taking SE as its input.
Experimental Setup: We consider bandit problem with four arms, each associated with mean rewards of {1.0,0. 0.6, 0.6, 0.6). The reward noise is drawn from a normal distribution (N,01), The confidence parameter is set to 5 = 0.01. We perform 1000 independent trials and record the stopping times for each. Trials that do not terminate within 1,000,000 time steps forcefully stopped that point. Figures 7a and 7b present histograms of the stopping times observed across all trials for SE and SE augmented with BrakeBooster, respectively. Additionally, Figure 7c shows comparative cumulative distribution function (CDF), scaled over 1000 trials, for both SE and SE with BrakeBooster. We also conduct the same set of experiments using a four-arm bandit problem with mean rewards { {1.0, 0.9, 0.9, 0.9}. Furthermore, In these experiments, we employ 1.2x growth factor for both the per-trial budget and the number of trials, in contrast the conventional doubling scheme, speculating that the exponential guarantee will still be preserved. The corresponding results are presented in Figure 8.
The results show that the BrakeBooster mechanism ensures that all the instances stop. Furthermore Figure 7c and & shows that applying BrakeBooster on Successive Elimination helps stop all the trials without sacrificing too many samples (the CDF curve of Brase catches up with that of SE very fast because the crossover point is at the stopping time of ~ x 10 for Figure 7c and ~ 0.05 x 10 for Figure 8c).
Observations:
1.0
300
SE
70
SE
SE with BrokeBooster
with, BrakeBooster
0.8
82-
250
Number Taa
50-
60-
130
Nimbbrr
150
30-
100
20-
90
10
20000
40000
Slapping time
60000
30300
100000
10000 20000 30000 40000 50000 60030 70500 0
Stopping time
20000
4000n
Stopping time
60000
80000
100000
(a) Successive Elimination (SE): Some trials fail to stop.
(b) BrakeBooster + SE: All trials successfully stop.
(c) Both plots with CDF of stopping times shaded with respective colors
Figure 7. Histogram of stopping times for problem instance A 0.6, 0.6) (force stop after 0.IM samples). Results from IK trials.
D.3. Empirical Evaluation of LUCB1, TS-TCI, and FC-DSH
In this section, we analyze the stopping times of LUCBB (Kalyanakrishnan et al., 2012), TS-TCI (Jourdan et al., 2022), and FC-DSH (ours).
For the implementation of FC-DSH algorithm, we deviate from the theoretical version presented in the paper by reusing samples across rounds. We opt to implement this practical version to reflect a more efficient use of data in empirical settings. We remark that the theoretical analysis can still be done by taking union bound over the arms just like how Successive Rejects (Audibert et al., 2010) analysis can be done with sample reuse. Furthermore, instead of doubling the budget after each phase, we generalize the growth schedule by introducing a scaling parameter b, such that Tm = bm-11, for phase m 2 2. While our analysis focuses on the case = 2, we speculate that the exponential guarantee may hold for any value of b. In our experiments, we 1.01 to allow for finer budget increment. Additionally, we adopt
Experimental Sctup:
40

---

Fixing the Loose Brake: Exponential- -ailed Stopping Time in Best Arm Identification
200
SE
SE
400-
SE. with BrakeBooster
250
with Broker
Numberal Tell
300
Namber maals
300
250
250-
200
75
150
150
50
100-
100
25
50-
Stmpping time
0.6
0.8
1.0
50000
100000
150000 200000 250000 Stoppin time
Stuppi ng Lime
0.4
0.5
0.8
1.0
(a) Successive Elimination (SE): Some trials (b) BrakeBooster + SE: All trials successfully fail to stop.
(c) Both plots with CDF of stopping times shaded with respective colors
stop.
Figure 8. Histogram of stopping times for problem instance {1.0, 0.9, 0.9, 0.9) (force stop after 1M samples). Results from 1K trials.
the stopping rule proposed by (Jourdan et al., 2022) across all algorithms to ensure fair comparison.
In this experiment, consider multiple bandit instances with varying number of arms K {4, 8, 16). For each instance, the mean reward of the optimal arm is set to 1.0, while all sub-optimal arms have mean rewards of 0.6. For instance, 4-armed bandit instance is associated with mean rewards of (1.0, 0.6, 0.6, 0.63. The reward noise is drawn from a normal distribution (0, 1). The confidence parameter is set to 5 0.05. We perform 1000 independent trials and record the stopping times for each. Trials that do not terminate within 1,000,000 time steps are forcefully stopped after that time step. Figure 9, 10, and 11 illustrate the histograms and cumulative distribution functions (CDFs) of the stopping times observed for LUCBI, I, TS-TCI, and FC-DSH across instances with K E {4, 16).
LUCB1
LUCB1
TS-TCI
TS-TCI
60
FC-DSH
0.8
FC-DSH
50
40
30
0.4
10
500
1000
1500
2000
2500
3000
3500
4000
500
1000
1500
2000
2500
3000
35:00
4000
Stopping time
Stopping time
(a) Histogram
(b) CDF
Figure 9. Histogram and CDF of stopping time of LUCB1, TS-TCI, and FC-DSH on the instance with K = 4.
First, the plots confirm that LUCBI, TS-TCI, and FC-DSH all successfully stops, in contrast to the Successive Elimination (SE), which may fail to stop (Figure 7a). Secondly, unsurprisingly, the stopping time increase as the number of K grows. Among the methods, TS-TCI exhibits the best performance, for = 8 and = 16, whereas FC-DSH yields the longest stopping times.
Observations:
To further investigate the tail behavior of the stopping time distribution, we conduct an additional experiment focusing on the tail probability P(X > x) as shown in Figure 12. Anticipating that the tail behavior would become more apparent with significantly larger number of trials, we increase the number of trials from 1000 to 1,000,000. The experiment is performed on 4-armed bandit instance with mean rewards of {1.0, 0.6, 0.6, 0.63 with all other settings remain identical to those described earlier in this section.
Additional Experimental Sctup:
Observations: Figure 12 confirms that FC-DSH exhibits a exponential tail stopping time. Unexpectedly, it does not provide evidence that LUCB1 exhibits polynomial tail. If LUCB1 follows polynomial tail, we would expect to observe linear

---

Fixing the Loose Brake: Exponential-Tee -aiiled Stopping Time in Best Arm Identification
LUCB1
TS-TCI FC-DSH
50-
0.8
40
30-
0.4
LUCB1
TS-TCI
FC-DSH
3000
4000
5000
6000
7000
8000
9000
10000
3000
4000
5000
6000
7000
8000
9000
10000
Stopping
Stopping time
(a) Histogram
(b) CDF
Figure 10. Histogram and CDF of stopping time of LUCBI, TS-TCI, and FC-DSH the instance with K 8.
LUCB1 TS-TCI
1.0
50-
FC-DSH
40
0.6
Number of
30
LUCB1
0.2
TS-TCI
FC-
7500 10000 12500 15000
17500 20000 22500 25000 Stopping time
7500 10000 12500
15000 17500
20000 22500 25000
Stopping time
(a) Histogram
(b) CDF
Figure/ 11. Histograms and CDFs of stopping times of LUCBI, TS-TCI, and FC-DSH on the instance with K 16.
decay trend the plot: however, such a pattern does not emerge. There are two plausible interpretations: (i) LUCBI may exhibit exponential tail, suggesting that existing theoretical guarantees are loose and warrant tighter analysis, (ii) LUCBI indeed has a polynomial tail, but a much larger number of trials may be required to empirically verify it.
Furthermore, TS-TCI shows intriguing behavior. In the regime where stopping times fall between approximately 2,500 and 10,000, TS-TSC exhibits roughly linear decay in log( P(X z)). We conjecture that trade-off exists: the aggressive sampling approach of TS-TCI likely results in heavier-tailes stopping time distributions. In addition, the more aggressive in sampling strategy, the faster the algorithm enters the linear decay regime. Obtaining a positive/negative answer to this phenomenon is left as future work.
42

---

Fixing the Loose Brake: Exponential- -ailed Stopping Time in Best Arm Identification
0-
WCBB1
TS-TCI
FC-DSH
-6
log
-12-
5000
10000
Stopping time
Figure 12. Log tail probability log(P(X > 2)) curve instance Results from 1,000,000 trials.
43


Reviews:
[{"review_id": "Bj9AQ3nDPi", "reviewer": "Reviewer_mZ4M", "summary": "This paper address the best arm identification problem under fixed confidence, emphasizing the importance of exponential-tailed stopping time guarantees. Unlike existing algorithms prone to heavy tails or indefinite stopping, the authors propose two novel theoretical results: (1) an algorithm with exponential-tailed stopping time superior to prior methods, and (2) a meta-algorithm transforming any high-probability stopping algorithm into one with exponential-tailed guarantees, highlighting room for improvement in current methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the significance and broader impact of our work in identifying an intriguing problem. We address your comments below. Please see empirical results in rebuttal to 94Yb.\n\n1. Our goal was to highlight a surprisingly overlooked issue in the bandit literature and provide theoretical evidence demonstrating that an exponentially decaying tail bound is indeed achievable. Before us, no one even realized it was possible. We do not claim empirical contributions but offer an initial theoretical exploration, hoping to stimulate further discussion in this direction.\n\n2. When comparing our method to track-and-stop or top-two algorithms, we acknowledge that it is less efficient in terms of sample complexity. As demonstrated in the paper, using BrakeBooster results in additional sample complexity, up to logarithmic factors. However, our contribution lies not in minimizing sample complexity but in providing an additional safeguard. By sacrificing a logarithmic factor in sample complexity, our method ensures that the algorithm does not run indefinitely.\n\n3. Thank you for the reference \"Fast Pure Exploration via Frank-Wolfe.\" We will incorporate it into our paper.\n\n4. On weakness 2, we clarify that being $\\delta$-correct does not necessarily imply an exponential tail. For instance, Successive Elimination is $\\delta$-correct yet lacks an exponential tail. Thus, it remains meaningful to explore this property even when an algorithm is $\\delta$-correct.\n\n5. On weakness 3, we agree that simply placing a checkmark in the “asymptotic expected sample complexity” column without proving optimality is not a fair comparison. We will revise this to ensure our contribution is not misleading.\n\n6. On weakness 4, we agree that the statement could be misleading and is somewhat irrelevant. We will remove it from our revision. Thank you for pointing this out.\n\n**Regarding your questions**\n\nOn question 1: We would like to clarify that we do not claim BrakeBooster provides a guarantee of asymptotic expected sample complexity. On your comment mentioning \"enhanced with BrakeBooster\", we did not intend to imply an improvement in this aspect. Instead, our goal is to highlight that BrakeBooster addresses the often-overlooked issue of stopping tail behavior while aiming to preserve sample complexity as much as possible. For high-probability sample complexity, the Successive Elimination algorithm without BrakeBooster yields a sample complexity of $\\mathcal{O}\\left(\\tau_{\\text{SE}}:=\\sum_{i=2}^{K} \\frac{\\ln\\left(\\frac{K}{\\delta\\Delta_i}\\right)}{\\Delta_i^2}\\right)$. With BrakeBooster, this shifts to $\\mathcal{O}(\\tau_{\\text{SE}}\\log^2(\\tau_{\\text{SE}}))$. More broadly, regarding the polylog term in Proposition 2.9, as long as an algorithm conforms to the specific form outlined in Definition 2.8 for its exponential tail, we can always address it with the following general approach. Suppose an algorithm satisfies, for all $T \\geq T_\\delta$,\n\n\\begin{align}\n\\mathbb{P}\\left( \\tau \\geq T \\right) \\leq \\exp\\left(-\\frac{T}{\\kappa \\cdot \\log^b(T)}\\right)\n\\end{align}\nwhere $b$ is any positive integer. By setting the right-hand side to be less than $\\delta$, we obtain\n\\begin{align}\n\\frac{T}{\\log^b(T)} > \\kappa \\log(1/\\delta).\n\\end{align}\nDetermining a sufficient condition to ensure this inequality holds can be intricate, but it is always feasible to solve for $T$ using the following. Our objective is to establish a high-probability bound through contraposition. To do so, we explore a necessary condition for $T$, such as $T \\leq c \\log^b(T)$, \n$$ T \\le c \\log^b(T) $$\n\n$$ \\leftrightarrow T^{1/b} \\le c^{1/b} \\log(T) $$\n\n$$ \\leftrightarrow T^{1/b} \\le b c^{1/b} \\log(T^{1/b}) $$\n\n$$ \\leftrightarrow T^{1/b} \\le b c^{1/b} \\log\\left(\\frac{T^{1/b}}{2 b c^{1/b}} 2 b c^{1/b}\\right) $$\n\n$$ \\rightarrow T^{1/b} \\le b c^{1/b} \\left(\\frac{T^{1/b}}{2 b c^{1/b}} - 1 + \\log(2 b c^{1/b})\\right) \\tag*{$\\ln(T) \\le T - 1$} $$\n\n$$ \\leftrightarrow T^{1/b} \\le 2 b c^{1/b} \\left(\\log(2 b c^{1/b}) - 1\\right) $$\n\n$$ \\leftrightarrow T \\le c \\left(2 b \\left(\\log(2 b c^{1/b}) - 1\\right)\\right)^b $$\n\nThus $T> c(2b(\\log(2bc^{1/b})-1))^b$ is a sufficient condition to say $T> c\\log^b(T)$ and we therefore solve the polylog factors.\n\nIn comparing FC-DSH and DSH, FC-DSH is a refined version of DSH, enhanced with a stopping condition. DSH, an anytime algorithm, can theoretically run indefinitely without such a limit.\n\nOn question 2: Conceptually, setting $T_1 = 1$ throughout does not impact the core results. Our theorems demonstrate that the findings hold for all $T_1 \\geq 1$. Including $T_1$ as a parameter provides flexibility in certain cases, as a meaningful minimum number of samples is necessary to run the algorithm effectively. Typically, we require the sample size to exceed the number of arms. On the other hand, if we happen to know the base algorithm's high probability stopping time, we can just set it as $T_1$ directly, as an efficient start of BrakeBooster.", "claims_and_evidence": "I do not identify the claims of the paper as problematic.", "methods_and_evaluation_criteria": "The evaluation criteria is the comparison of the theoretical upperbound. I did identify any big problem in the theoretical criteria. However, It would be better to explicitly write down the theoretical comparison; see in Q1 of \"Questions For Authors\"\n\nUpdate a typo; sorry for any inconvenience. \"I did not identify any big problem  in the theoretical criteria\"", "theoretical_claims": "I did not check the correctness of any proofs", "experimental_designs_or_analyses": "There is no experimental design for proposed Algorithm 1 and 2.", "relation_to_broader_scientific_literature": "The research problem is very interesting and has a broader imact in the literature. It has been ignored by the community that the family of successful elimination algorithms are not $\\delta$-correct. This paper aims to fix this problem.", "essential_references_not_discussed": "Some non-aymtotic upper bounds in the family of track-and-stop algorihtms needs to be compared. For example, theorem 2 of \"Fast Pure Exploration via Frank-Wolfe, NeurIPS 2021\".", "other_strengths_and_weaknesses": "## Strengths: \nThe research problem addressed in this paper is significant and has broader implications in the existing literature. Specifically, the observation that successful elimination algorithms are not guaranteed to be $\\delta$-correct has largely been overlooked by the community. This paper addresses this gap by proposing a general algorithm to resolve this issue.\n\n## Weaknesses:\n1. The paper lacks experimental validation for the proposed Algorithms 1 and 2, even on synthetic datasets. Compared to existing methods such as the track-and-stop and top-two algorithms, the proposed algorihtms may be dramatically less efficient in simluations, because the proposed algorithms require significantly more arm pulls to maintain tail-bound guarantees. Providing empirical justification for the effectiveness of these algorithms through experiments would significantly strengthen the paper. Please clarify if this understanding is incorrect.\n\n2.  I am not satisfied with the information that Table 1 conveys. For example, the column indicating whether an algorithm has exponential-tailed behavior appears not meaningful if the algorithms are already guaranteed to be $\\delta$-correct. \n\n3. Similarly to 2, the track-and-stop and top two algorithms are asymptotically optimal, while the proposed FC-DSH and brakebookster are not. Hence, it is not a fair comparison to just give a tick mark in the column of “asymptotic expected sample complexity” without demonstrating the optimality.\n\n4. The statement on line 131, \"the value of $\\liminf_{\\delta \\to 0} E[\\tau]\\/ \\ln(1/\\delta)$ will be independent of $B$ even if $B$ is very large,\" is not accurate. For any asymptotically optimal algorithm (such as track-and-stop), it must hold that:  $\\liminf_{\\delta \\to 0} E[\\tau] \\/ \\ln(1/\\delta)=\\limsup_{\\delta \\to 0} E[\\tau] \\/ \\ln(1/\\delta) = \\text{a instance-depedent constant}$", "other_comments_or_suggestions": "See in \"Other Strengths And Weaknesses\" and \"Questions For Authors\"", "questions_for_authors": "1. Could the authors explicitly state the high-probability sample complexity and asymptotic expected sample complexity for the Successive Elimination algorithm enhanced with Brakebooster? Specifically, it would be helpful to specify the \"polylog\" term mentioned in Proposition 2.9 and explicitly compare the high-probability sample complexities of algorithms with and without Brakebooster. Similarly, an explicit comparison between FC-DSH and DSH would be beneficial.\n\n2. Regarding Algorithm 2, what are the considerations involved in selecting the parameter $T_1$? Could the authors justify why $T_1$ is introduced as a parameter rather than fixing it to $T_1 = 1$?\n\nOverall, for the valueable research problem and interesting results introduced in this paper, I currently recommend \"weak acceptance\".  I remain open to increasing or decreasing the rating in the discussion stage.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zcIdVPk97p", "reviewer": "Reviewer_94Yb", "summary": "This paper considers the distribution of the stopping time in the fixed confidence BAI problem. It discovers that while most existing algorithms only have stopping time bounds in expectation or in high probability, which fail to achieve exponential decreasing rate (in time step $T$) for the misidentification probability.\n\nTo address this, the authors propose FC-DSH, an algorithm that guarantees an exponential-tailed stopping time. Additionally, a meta algorithm BrakeBooster is introduced, which can transform any fixed confidence BAI algorithm into one with an exponentially decaying stopping time.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for understanding our theoretical contribution and your interest in additional empirical studies. We address your comments below.\n\nRegarding the reviewer's comment that \"FC-DSH is a lot like the algorithm in Zhao et al. (2023), with just a change to the stopping rule,\" we would like to clarify that, while FC-DSH shares some design similarities, its novelty lies in the analysis. Since bounding the tail probability is, in general, a nontrivial task, we had to prove statements that were not necessary when developing a fixed budget guarantee for FB-DSH. For example, we had to bound the probability that DSH fails to satisfy the stopping condition even if the best arm is chosen as the estimated best arm (i.e., $\\mathbb{P}(\\exists i\\neq 1: L_1^{(m)} \\le U_i^{(m)}, J_m = 1)$). To bound this, we need to bound the probability of a suboptimal arm $i$ reaching the expected-to-reach stage $\\ell_i^*$ (defined in Lemma 4), i.e., $\\mathbb{P}(L_1^{(m)} \\le U_i^{(m)}, \\ell_i \\ge \\ell_i^*, J_m = 1)$ and $\\mathbb{P}(\\ell_i < \\ell_i^*)$ presented in Lemma 4 and Lemma 5, respectively. Proofs for these require a careful division of the events that is not found in prior work, to our knowledge. In contrast, the guarantee of FB-DSH requires analyzing just the probability of the optimal arm failing to reach the final stage $\\mathbb{P}(J_m \\ne 1)$, which can be done by our Lemma 6 or by existing proofs from Karnin et al. (2013) or Zhao et al. (2023). \n\n**Additional empirical studies**\n\nAnonymous link for empirical results: https://zenodo.org/records/15117826\n\nWe sincerely thank the reviewer for your interest in additional empirical studies. In response, we have conducted and will include the following experiments in the final version of the paper: (1) a study demonstrating that our FC-DSH algorithm (Algorithm 1) consistently terminates, exhibits light-tailed stopping-time behavior, and performs comparably to two widely used fixed-confidence best-arm identification (FC-BAI) algorithms - LUCB1 (Kalyanakrishnan et al., 2012) and TS-TCI (Jourdan et al., 2022) - as presented in Table 1; and (2) an empirical validation of the proposed meta-algorithm, BrakeBooster, confirming its ability to mitigate the stopping-time issues encountered by the Successive Elimination (SE) algorithm.\n\nWe implement a similar experimental setup as in our paper, but introduce a variation with 4 arms having of mean rewards of {1.0, 0.6, 0.6, 0.6}. We set the confidence level to $\\delta = 0.05$ across all experiments. We conduct 1,000 trials and record the stopping times for each. Trials that did not terminate within $1$ million steps were forcefully stopped. Although this setup features a larger reward gap - making it an easier problem instance - the Successive Elimination (SE) algorithm still fails to stop in a significant number of trials (92 out of 1000 trials), as shown in Figure 1a.\n\nFigure 1b shows that our FC-DSH algorithm consistently stops, alongside two other fixed-confidence best-arm identification (FC-BAI) algorithms: LUCB1 and TS-TCI. As the reviewer noted, the use of the doubling trick may degrade practice performance. To mitigate this issue, we modify our FC-DSH to reuse all samples collected in previous phases and stages. The modified FC-DSH outperforms LUCB1 and performs comparably to TS-TCI as shown in Figure 1b and Figure 2 (Left). This modified version highlights the practical potential of FC-DSH, and we believe that developing a theoretical understanding of sample reuse would be an interesting direction for future work. To highlight the differences in tail behavior, Figure 2 (Right) presents the empirical CDF of the stopping times. As expected, LUCB1 exhibits a slightly heavier tail - consistent with its theoretical polynomial tail guarantee discussed in the paper. \n\nMoreover, we apply BrakeBooster on top of the Successive Elimination (SE) algorithm and, as expected, observe that all trial runs successfully terminate within 350K rounds, as illustrated in Figure 3b - a clear contrast to the behavior of SE alone. While BrakeBooster is not yet optimized for efficiency, it serves as an important first step toward developing a general-purpose meta-algorithm. Its primary value lies in demonstrating the feasibility of such an approach, which has the potential to extend exponential tail stopping-time guarantees to a broad class of base algorithms.\n\nWe’d be more than happy to address any other questions and concerns.", "claims_and_evidence": "Yes, the authors provide theoretical proofs in section 2 to indicate the some current algorithms cannot stop with a constant probability. The proposed FC-DSH and the meta algorithm BrakeBooster are introduced in section 3 and 4 respectively, accompanied by theoretical guarantees.", "methods_and_evaluation_criteria": "The paper is mainly on the theoretical side of the existing BAI algorithms.\n\nThe proposed methods make sense from the theoretical standpoint. It makes use of and develops the doubling trick in the bandits literature to get the exponential stopping tail.\n\nWhile the authors emphasize the theoretical contributions, the empirical performance of the proposed algorithms is not presented. Although the use of doubling trick can be beneficial in terms of theoretical analysis, the empirical performance of the algorithms with doubling trick usually have poor performance. It is expected that the authors can provide more discussions regarding this issue.", "theoretical_claims": "I skimmed through the analysis and the proofs look reasonable to me.", "experimental_designs_or_analyses": "This paper focuses on the theoretical side.\nOnly one experiment about successive elimination is provided. No empirical experiments are provided to illustrate the proposed algorithms.", "relation_to_broader_scientific_literature": "This paper lies in the field of Bandits Algorithms, in particular, it is related to Best Arm Identification with fixed confidence in Bandits. It identifies the flaws in previous algorithms and propose two algorithms to fix the problem.", "essential_references_not_discussed": "The references look good to me.", "other_strengths_and_weaknesses": "**Strengths**\n\nThis paper further develops the doubling trick to a “two-dimensional” case and proposes the meta algorithm BrakeBooster. The choices of the hyper parameters are also well explained.\n\n**Weaknesses**:\n\nThe proposed FC-DSH shares a similar design as the algorithm in Zhao et al. (2023) and the only modification is only the stopping rule.", "other_comments_or_suggestions": "As said in previous sections, it would be great if the authors can provide some empirical results on the performance, even if the results may not be as good as those algorithm without exponentially decaying error probability.\n\nIn particular, empirical comparisons between the proposed works and the existing works listed in Table 1 is suggested.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None."}}, {"review_id": "7nMf7aSUlD", "reviewer": "Reviewer_H9DE", "summary": "This paper studies the fixed-confidence best-arm identification problem for $1$-sub-Gaussian distributions. The authors remark that asymptotic guarantees on the expected sample complexity doesn’t prevent a large tail of the empirical stopping time. Worse, high probability guarantees of the sample complexity doesn’t prevent the algorithm from never stopping with a nonnegligible probability. The latter statement is highlighted both theoretically (Theorems 2.4 and 2.5) and empirically (Figure 1 and Appendix D). Therefore, the authors introduce the $(T_{\\delta}, \\kappa)$-exponential stopping tail property (Definition 2.8), which captures the fact that the tail of the stopping time is exponentially decreasing for large enough time. This condition is sufficient to prove both high probability bound and expected sample complexity bounds (Proposition 2.9). The authors introduce FC-DSH. This is a variant of the anytime algorithm DSH, which is an anytime version of the fixed-budget algorithm Sequential Halving. The algorithm proceeds in phases whose length doubles. Within each phase, SH runs for the current budget, i.e., uniform sampling on the set of active arms which is halved at the end of each of the $\\log_2 K$ stages, and a gap-based stopping rule is evaluated at the end of the phase. The observations between phases $m$ and stages $l$ are not shared. FC-DSH is $\\delta$-correct  (Theorem 3.1) and satisfies an exponential stopping tail property (Theorem 3.2). The authors propose the BrakeBooster meta-algorithm, which runs a base algorithm with a 2D doubling trick, both on the budget and on the number of independent runs for each base algorithms. The observations between phases $(r,c)$ and runs $l$ are not shared. Given a $\\delta_0$-correct base algorithm that have high probability upper bound on its sample complexity, BrakeBooster is $\\delta$-correct (Theorem 4.1) and satisfies an exponential stopping tail property (Theorem 4.2).\n\n**## update after rebuttal**\nThe discussions between the authors and the different reviewers provided a more detailed and nuanced perspective on the research question tackled in this paper. Including those insightful discussions will improve the paper in its revised version. Two primary practical concerns remains for me: (1) the degradation of the empirical performance when using BrakeBooster and (2) the probability of non-termination might be negligible in modern BAI algorithms. However, I recognize the theoretical contributions of the paper that study more sophisticated guarantees on the stopping time. Personally, I would be excited to see more works on this direction, e.g., matching lower/upper bounds on the higher moments (i.e., variance) of the stopping time. Therefore, I decided to raise my score to weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the value of our proposed exponential stopping tail property and finding it helpful. Please see empirical results in rebuttal to 94Yb. The maximum characters limit our rebuttal content, will add more in discussion.\n\n**On Theorems 2.4 / 2.5**: We agree that the lower bound $\\Omega(\\delta^{118})$ is not an absolute constant. However, the exponent $\\delta^{118}$ can be regarded as a constant in the sense that it is independent of $H_1$, $K$, and $T$. Since $\\delta$ is a user-specified input, it is reasonable to expect this bound to reflect a small constant probability relative to $\\delta$. We will clarify this in our final version.\n\n**On Theorem 2.7 / 2.5**: Algorithm 5, lil-KLUCB (Tanczos et al., 2017), and LUCB1 share similar sampling and stopping rules but differ in confidence bound construction. Algorithm 5 uses a simplified bound, $\\log(t^2/\\delta)$, aligning with Algorithm 4. In contrast, lil-KLUCB employs $\\log(\\log_2(t)/\\delta)$ with a refined $\\delta$, while LUCB1 uses $\\log(t^4/\\delta)$, achieving a polynomial tail guarantee. We chose the simpler bound for analysis, but both lil-KLUCB and Algorithm 5 can fail to stop with a small, non-negligible probability, unlike LUCB1. We believe LUCB1’s polynomial tail lower bound is provable, yet our algorithms and non-stopping results reveal overlooked issues, showing that LUCB1’s guarantee is not the strongest possible.\n\n**Base algorithms**: Our algorithm doesn’t need a sample complexity bound as input; it works with any $\\delta$-correct algorithm and improves if the base algorithm does. Feel free to pair it with $\\delta$-correct algorithms boasting asymptotic sample guarantees-likely have strong finite-time guarantees too, though they may be tough to analyze (eg, TS-TCI/EB-TCI). The meta-algorithm’s strength is enabling exponential stopping times by leveraging existing algorithms with weaker guarantees. These base algorithms balance sample complexity and adaptive sampling rounds differently: elimination algorithms need few adaptive decisions, suiting batch sampling or limited adaptivity, while fully adaptive settings favor TS-TCI. Thanks for suggesting adaptation to the best algorithm—it’s a promising direction to explore.\n\n**Discarding samples**: We recognize the practical downside of discarding samples. However, our meta-algorithm’s key contribution is demonstrating, for the first time in the literature, a strategy that transforms a base algorithm with a weak guarantee into one with a stronger guarantee. While avoiding speculation, we think it’s feasible to refine the approach to eliminate or greatly reduce sample discarding. For insight, see Minsker (2023), “U-statistics of growing order and sub-Gaussian mean estimators with sharp constants,” where the author eliminated sample abandonment in the median-of-means algorithm, improving performance bounds using U-statistics.\n\n**On Lemma B.1**: We believe the reviewer may have misread this section of our proof. From Lines 884–886, we apply Lemma B.1’s assumption that FC-DSH satisfies $\\mathbb{P}(\\tau \\geq T_m) \\leq \\exp\\left(-\\frac{T_m}{cH_2\\log_2(K)}\\right)$. Then, from Lines 886–888, we rely on the property $T < T_m$, established in Line 880.\n\n**App D / Fig 1**: We set $\\delta$ to 0.05. In our experience, empirical failure rates are typically several times lower than the chosen $\\delta$, even with stringent stopping conditions (e.g., from the track-and-stop paper). This pattern isn’t unique to our work but is common across fixed-confidence studies.\n\n**Theorem 4.1**: Many algorithms lack an exponentially decaying stopping time tail due to hard elimination steps that may discard the optimal arm without recovery. FC-DSH Novelty: The innovation lies in its tail probability analysis, a complex task not required for FB-DSH’s fixed-budget guarantee. These proofs involve event divisions absent in prior work, unlike FB-DSH’s simpler analysis (Karnin et al. 2013, Zhao et al. 2023).\n\n**Q1**:This falls outside our scope, but to our knowledge, the accelerated rate from Zhao et al. (2023) is unlikely to apply in the fixed-confidence setting. Fixed-confidence requires decision correctness, necessitating hypothesis testing. For your second point: Analyzing DSH without discarding samples is feasible—it swaps a $\\log\\log K$ factor in sample complexity for $\\log K$. This involves a union bound over $K$ arms, as in the successive reject algorithm, which avoids sample discarding. We discarded samples to streamline the analysis.\n\n**Q2**: If you’re referring to improving sample complexity, our aggregation approach is generally optimal, barring constant or logarithmic factors, as further improvement would contradict established lower bounds. Reducing the number of voters while maintaining the same effect is a potential avenue, though its feasibility remains uncertain to us. Still, your suggestion could trim logarithmic or constant factors, and we’re keen to explore it in future work.", "claims_and_evidence": "**On Theorems 2.4 and 2.5.** As currently stated in the main, I would argue that Theorems 2.4 and 2.5 are misleading/false given what is proven in Appendix A. On the specific considered instance, the probability that the algorithms never stop is lower bounded by $\\Omega(\\delta^{118})$. Therefore, it is far from being an absolute constant bounded away from $0$ for all $\\delta$: it goes fast to $0$ when $\\delta \\to 0$.\n\n**On Theorem 2.5.** Algorithm 5 seems quite far from lil-KL-LUCB of Tanczos et al., (2017). Could the authors precisely describe what is meant by “adapted and simplified for sub-Gaussian distribution” ? In particular, why those differences are not introducing undesirable behavior compared to the original algorithm ?\n\n**On Theorem 2.7 and Theorem 2.5.** Theorem 2.7 shows that LUCB1 has a polynomial tail guarantee. Given the proof of Theorem 2.5, I am not sure to understand why a similar result cannot be shown for LUCB1, even though it would seem to contradict Theorem 2.7. Could the authors discuss the differences between Algorithm 5 and LUCB1 ? They seem awfully close. Is it solely a difference of the bonuses ? If so, it doesn’t alter the argument in the proof of Theorem 2.5 since it only controls the bad event that the initial draw of the best arm is not a good one, then argue that it will never be sample again. The same phenomenon hold for LUCB1 as it pulls both the empirical best arm and a distinct arm with the largest UCB.\n\n**Targeted base algorithms for BrakeBooster.** BrakeBooster is tailored to improve the guarantees of algorithms that are $\\delta$-correct and achieve high probability sample complexity guarantees. However, the authors themselves argue that “the high probability sample complexity [are] weak and rather unnatural”. Therefore, it seems unclear what is the benefit of constructing a meta-algorithm to “boost” the guarantees of algorithms with weak guarantee that suffers from large tail of stopping time. It would have been great if BrakeBooster was adaptive to improved theoretical guarantees of base algorithms. For example, when given a base algorithm with asymptotic guarantees, it could (1) show exponential stopping tail or (2) obtain non-asymptotic upper bound on the expected sample complexity. In other words, designing a meta-algorithm to improve the “best” known algorithms seems more promising than a meta-algorithm that improves algorithms with “poor” guarantees or performance. \n\n**Discarding samples in BrakeBooster.** Crucially, BrakeBooster doesn’t share the observations across the different runs of the base algorithms. While this independence is key to derive theoretical guarantees, it seems wasteful in terms of sample complexity. This phenomenon is most likely blown out of proportion due to the large number of independent runs before stopping. Therefore, it seems legitimate to conjecture that the “lighter” tail of the empirical stopping time comes at a cost of a significant increase of the average empirical stopping time. If this conjecture is true, it would be a significant limitation of the usefulness of BrakeBooster. An empirical study of BrakeBooster seems necessary to understand the impact of this contribution.\n\n**On FC-DSH.** While shown to be $\\delta$-correct and having exponential stopping tail, an empirical study of FC-DSH seems necessary to understand whether it is a practical algorithm that performs well compared to existing algorithms.", "methods_and_evaluation_criteria": "See “Experimental Designs Or Analyses” section for details on the empirical evaluation.", "theoretical_claims": "I checked the correctness of the theoretical claims. To the best of my understanding, there is no major issue.\n\n**On Lemma B.1.** There seems to be a minor error. The statement in Line 872 should read as “for all $T \\ge 2T_{\\delta}$”. In the current proof, the author requires that $T_m > T_{\\delta}$ in Line 886 in order to use the assumption from the Lemma. However, this condition is not true, yet it could be shown if $T \\ge 2T_{\\delta}$”.", "experimental_designs_or_analyses": "**Empirical results for FC-DSH.** At the moment, there is no empirical evaluation of the performance of FC-DSH. In particular, it would be interesting to understand what is the empirical impact for FC-DSH of keeping the observations between each phase $m$ or/and each stage $l$. Given the rich literature in terms of sampling rules for BAI, it would be also relevant to understand what is the impact of using uniform sampling rule within each phase/stage by comparing FC-DSH to more adaptive sampling rules. It would allow comparing the proven exponential tail bound of FC-DSH with the empirical tail behavior of other algorithms, hence allowing to conjecture which other sampling rules might enjoy this property.\n\n**Empirical results for BrakeBooster.** BrakeBooster is specifically designed for algorithms such as SE, i.e. $\\delta$-correct and high probability upper bound on the sample complexity. Figure 1 and Appendix D show the limitation of SE. Those limitations are supposed to be solved by using BrakeBooster on top of SE. Therefore, it seems rather natural to empirically confirm the usefulness of BrakeBooster when applied to SE, especially since the authors state Corollary 4.3 for SE explicitly. Without empirical evidence of the benefits of using BrakeBooster, it seems rather unclear that BrakeBooster is actually helpful in practice. \n\n**Appendix D and Figure 1.** To the best of my reading, the value of the $\\delta$ parameter used in the experiments is missing. What is this value ? It is difficult to understand how “bad” are the “stopping failure” without putting them into perspective with the confidence level that is being targeted. \n\n**Suggestions on the current setup.**\n- It would be interesting to compare the targeted confidence $\\delta$ with the empirical proportions of runs for which there is a “stopping failure”. Inherently, it should be smaller, since those algorithms are $\\delta$-correct. Is it of the same order of magnitude or several order of magnitudes lower ?\n- It would be interesting to add a line in the plots to give a proxy for the lower bound, e.g., $H_1 \\log(1/\\delta)$.", "relation_to_broader_scientific_literature": "To the best of my understanding, the authors discuss relevant literature adequately.", "essential_references_not_discussed": "To the best of my knowledge, there is no essential reference that is missing.", "other_strengths_and_weaknesses": "**Theorem 4.1.** The proof of $\\delta$-correctness appears convoluted and doesn’t provide lots of insights despite taking almost one page of the main content. It would be better to allocate space to understand the theoretical novelty in the analysis of FC-DSH or BrakeBooster.\n\n**Seemingly loose upper bounds.** In the Appendices, the proofs seem to use loose upper bounding in order to swallow the second-order terms in the first-order term by worsening its dependency. This is obfuscated by the use of $O(\\cdot)$ notation in the final results. It would be interesting to write a tighter analysis with a smaller first-order term, and only argue in the end that the second-order term can be “removed” with the $O(\\cdot)$ notation.", "other_comments_or_suggestions": "**Theorem 3.2.** In the main, it would be better to write the explicit statement proved in Appendix B.2. This gives a better understanding of the actual dependency in $K$, $H_2$ and multiplicative constants.\n\n**Theorem 4.2.** In the main, it would be better to write the explicit statement proved in Appendix C.1. This gives a better understanding of the actual dependency in $\\delta$, $\\delta_0$ and $T^\\star_{\\delta_0}(\\mathcal A)$. For example, the term $\\log(1/\\delta_0)$ should be left in the upper bound instead of being swallowed by the $O(\\log (T))$ notation. When $\\delta_0\\to 0$, it allows seeing that the $\\log(1/\\delta_0)$ term “cancels out” the dependency in $\\delta_0$ from $T^\\star_{\\delta_0}(\\mathcal A)$, which is likely also in  $\\log(1/\\delta_0)$.\n\n- Appendix A uses the notation $\\perp$ to denote the probability. To be consistent with the rest of the paper, it would be better to use $\\mathbb P$.\n\n- Lines 342-345. The event $E_1$ and $E_2$ are introduced, but there are not used.\n\n- Lines 268-270. “The complexity of best-arm identification problems is often characterized by an instance-dependent quantity $H_2$”. I would argue that this sentence is slightly incorrect. $H_2$ is an instance-dependent quantity that appears in the analysis of fixed-budget BAI. However, for fixed-confidence BAI, the instance-dependent quantity $H_1$ is closer to the true characteristic time $T^\\star$ for the asymptotic regime, i.e., $H_1 \\le T^\\star \\le 2 H_1$. As highlighted by equation (2), the quantity $H_2$ seems to be sub-optimal by a multiplicator factor $\\log_2 K$, which gets looser for larger instances.", "questions_for_authors": "1. **Improved analysis of FC-DSH.** Could the authors discuss whether their analysis of FC-DSH can be adapted to account for the recent improved analysis of FB-DSH ? For example, Zhao et al. (2023) show an improved rate compared to the rate $H_2$ used in this paper. Moreover, Kone et al. (2024, Bandit pareto set identification: the fixed budget setting) show that it is possible to keep past observations instead of discarding them at the end of each phase. It would be especially interesting to allow for keeping the samples, since it is known to have a large impact on the empirical performance of DSH.\n\n2. **Majority voting.** Is it clear that majority voting is the best aggregation strategy based on $L$ independent runs of a given algorithm ? Would it be possible to define an aggregation strategy that leverage additional information on the independent runs, such as the empirical stopping time, to reweight each vote ?\n\n3. Could the authors highlight precisely what are the theoretical novelties in the analysis of FC-DSH or BrakeBooster ?\n\nSeveral other questions have been asked in the previous sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s1Wvay1mal", "reviewer": "Reviewer_YUrK", "summary": "This paper is related to the best arm identification (BAI) problem in multi-armed bandits, where the objective is to recommend the (unique) arm with highest expected reward at a fixed error rate $\\delta$ ($\\delta$-correctness property) after collecting as few observations as possible.  The stopping time of a run of a best arm identification bandit algorithm is the number of observations collected up to the recommendation time. This paper focuses on the problem of guaranteeing that the distribution of stopping times is light-tailed and emphasizes on the fact that few papers from the literature try to tackle the problem of sometimes very long or infinitely long runs, even though the authors show that some of the most well-known algorithms from prior works exhibit such an undesirable behavior. The authors advocate for a stronger type of guarantee on the sample complexity than what is proposed in the literature so far, named exponential tail stopping time. The authors introduce a $\\delta$-correct algorithm named FC-DSH which exhibits an exponential tail stopping time, and a meta-algorithm called BrakeBooster which takes as input any $\\delta_0$-correct algorithm with weaker guarantees on the stopping time and returns a $\\delta$-algorithm with exponential-tail stopping time.\n\n## update after rebuttal\n\nI keep the score to 3. The problem of non-terminating runs seems limited to older algorithms, so I am still on the fence regarding the significance of the problem. But the strengths of the paper still hold so I would suggest acceptance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the significance of our problem, its novelty in bandit literature, and the strength of an exponentially decaying stopping time over high-probability bounds. The detailed description and anonymous link of the additional experiments we did are in **Additional empirical evidences** section from the rebuttal for reviewer **94Yb**. Please take a look. We address the comments below. \n\n**I am still not convinced about the importance of the problem of heavy-tailed stopping time distributions in fixed-confidence BAI ... ?**\n\nA light-tailed distribution offers several benefits:\n\n1) Even-though the event of non stopping happens with a low probability, it leads to an unknown expected stopping time, rendering the user clueless. We think, a little bit of inflation in the expected stopping time is better than a totally unknown expected stopping time in an implementation perspective.\n\n2) High probability stopping time can be considered as a single point guarantee. In contrast our results provide a broader guarantee, where we can predict what happens to the stopping time when the requirements are modified.\n\n3) The algorithms that provide a light tailed guarantee can be easily adapted as anytime algorithms. \n\n\n\nFurthermore, we think our contribution is theoretical, that is, we want to prove that it is possible to obtain a exponentially decaying distribution of stopping time theoretically, rather than proposing a practically efficient algorithm. Moreover, our work is a first step of showing that it is possible. There is no evidence we are aware of that indicates that achieving exponential stopping time necessarily will inherently sacrifice the performance.\n\n\n**While I understand the point of disentangling correctness and sample complexity, I disagree with the following claim ... ?**\n\nThat is good a point. If we be less rigorous and consider the fixed budget settings have $\\delta$-correctness ($\\delta$ specified) and $0$-stopping time (stopping time = budget and $\\delta = 0$ here) and anytime settings have $\\delta$-correctness ($\\delta$ non-specified) and $0$-stopping time (stopping time = whenever the user stops and $\\delta = 0$ here), even then we do not have the full freedom to choose different $\\delta$. Hence, even though this is a good strategy, it does not exactly serve our intentions.\n\n**The computational efficiency of FC-DSH’s is not worse (orderwise) than other algorithms ....  ?**\n\nThe computational complexity we have mentioned here is not sample complexity. It is just processor time needed for algorithm implementation\n\n\n**Table 1: LUCB has an upper bound in high probability on the sample complexity (their Corollary 7)**\n\nThanks for pointing it out. We will correct it in the final version.\n\n**Isn’t it better to get a polynomial bound on the stopping time or a non-asymptotic bound on the expected stopping time ..... ?**\n\nThis is an important topic for discussion. We do not view the exponential tail as an exclusive guarantee such that to achieve it, we always have to incur some inflation in the sample complexity. There could be some algorithms (TS-TCI could be a strong candidate) which can achieve the best of both worlds. Our paper prevails as the early attempt to introduce the importance of exponential tail and taking a first step to achieve it. This will lead to more imminent research to come up with algorithms that can achieve the best of both worlds. \n\nFurthermore the experiments (Figure 1b and 2b) we have done indicates that LUCB1 which achieves polynomial tail exhibits a worse performance compared to our FC-DSH which achieves an exponential tail.\n\n**Could you perform the same kind of experiments ... ?**\n\nWe did some additional experiments comparing FC-DSH to TS-TCI, LUCB1 and SE (Figure 1 and 2). Also analyzing the effect of Brakebooster on SE (Figure 3b). The detailed description and anonymous link are in Additional empirical evidences section from the rebuttal for reviewer 94Yb. Please take a look.\n\n**Can you compare computationally speaking the cost of FC-DSH compared to other algorithms from the literature?**\n\nWe could do that. However we have observed that orderwise there is no difference in the computational cost of our algorithm and the other algorithms in the literature. We also speculate that, since the trials can be implemented in parallel ($L_{r,c}$ trials used for voting are independent, hence can be parallelized), computational cost can even be improved.\n\nWe’d be more than happy to address any other questions and concerns.", "claims_and_evidence": "Most of the theoretical and practical claims are convincing and clear. However:\n- While I understand the point of disentangling correctness and sample complexity, I disagree with the following claim: Lines 153-155, Page 3 “In practice, one may desire to be loose on the correctness (large δ) yet want to ensure that the stopping time is small with very high confidence (small δ).” If this were true, then one would usually turn to fixed-budget or anytime settings (where an error bound is provided at each sampling time) rather than to a fixed-confidence setting.\n- Lines 98-99, Page 2 “The computational efficiency of FC-DSH’s is not worse (orderwise) than other algorithms.” As there are no experiments comparing the performance of FC-DSH and other fixed-confidence BAI algorithms, and as there is an increasing sampling budget for phases, it is unclear to me if this sentence is true.\n- I am still not convinced about the importance of the problem of heavy-tailed stopping time distributions in fixed-confidence BAI. As demonstrated by experiments (Figures 1 and 3-4), not stopping at all or long stopping times are extremely rare events, even in carefully crafted bandit instances such as the one used in Theorems 2.4-2.5 (e.g., $1/(8\\sqrt{\\pi})(\\delta/3.3)^ 118 \\approx 10^{-99}$ for $\\delta=0.5$ from Theorem 2.4). Moreover, in practice, one actually performs somehow the approach of BrakeBooster: stop the bandit algorithm after some time ($10^ 6$ for instance) and restart the algorithm with a new random seed for synthetic data / with new observations for real-life data (discarding prior observations in the process). But I agree that this approach only allows for correctness to hold and does not provide very strong guarantees on the stopping time. But is it worth it to sacrifice global performance for an event of small probability?\n- Table 1: LUCB has an upper bound in high probability on the sample complexity (their Corollary 7).", "methods_and_evaluation_criteria": "The authors focus on a single aspect of multi-armed bandits for fixed-confidence BAI, which is the tail of the distribution of stopping times, whereas most papers from the literature focus on the performance in high probability or in (asymptotic) expectation (as shown in Table 1). As such, especially as there is no experiments comparing to baselines (both in terms of quality of the recommendation, average stopping time or even a comparison of the distribution of stopping times of FC-DSH compared to the ones plotted for Successive Elimination in Figures 3-4, or better, more recent algorithms as those listed in Table 1), it makes the assessment of the theoretical improvement incurred by this paper difficult.", "theoretical_claims": "I have checked the supplementary material for the correctness and exponential tail stopping time guarantees for FC-DSH and BrakeBooster (not the technical lemmas in Section C.2) and they seem all correct to me.", "experimental_designs_or_analyses": "The experiments of counting the number of forcefully terminated runs in Successive Elimination look correct. However, no code is provided (supplementary zip file or anonymous code repository) to check the reproducibility of the results.", "relation_to_broader_scientific_literature": "The authors propose a new type of guarantee on the sample complexity of a bandit algorithm, which diverges from traditional approaches (high probability upper bound [1], upper bound in expectation [2]). The algorithmic contributions are based on the doubling trick (which “almost” doubles the sampling budget in a trial) which is very used in the bandit literature [3] and on a well-known fixed-budget algorithm named Sequential Halving [4-5]. The technical tools (concentration inequalities, correctness analysis by contradiction) are standard in the bandit literature (see prior citations).\n\n[1] Kalyanakrishnan, S., Tewari, A., Auer, P., & Stone, P. (2012, June). PAC subset selection in stochastic multi-armed bandits. In ICML (Vol. 12, pp. 655-662).\n\n[2] Garivier, A., & Kaufmann, E. (2016, June). Optimal best arm identification with fixed confidence. In Conference on Learning Theory (pp. 998-1027). PMLR.\n\n[3] Besson, L., & Kaufmann, E. (2018). What doubling tricks can and can't do for multi-armed bandits. arXiv preprint arXiv:1803.06971.\n\n[4] Karnin, Z., Koren, T., & Somekh, O. (2013, May). Almost optimal exploration in multi-armed bandits. In International conference on machine learning (pp. 1238-1246). PMLR.\n\n[5] Zhao, Y., Stephens, C., Szepesvári, C., & Jun, K. S. (2023, July). Revisiting simple regret: Fast rates for returning a good arm. In International Conference on Machine Learning (pp. 42110-42158). PMLR.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths\n- The idea of a meta-algorithm converting any “base” fixed-confidence BAI algorithm into an algorithm with stronger guarantees on the stopping time is interesting and well-executed.\n- The paper is well-written and attracts attention on a not-so-investigated problem in the BAI literature.\n- Disentangling correctness and stopping time probabilities is a good idea.\n\nWeaknesses\n- The importance of the problem is not obvious to me.", "other_comments_or_suggestions": "- Caption of Figure 1: “Historgram” should be “histogram”.\n- Throughout Section A in Appendix: “⊥” instead of the symbol for probability.\n- Experiments in the supplementary material (Section D): the exact number of forcefully stopped runs should be given for Figures 3-4, it is hard to estimate the proportion of these runs among the 1,000 trials from the histograms alone.", "questions_for_authors": "The main weakness of this paper and the reason why I rated it 3 is because I am not convinced by the importance of getting an exponential-tail stopping time, especially as logarithmic factors and large constants are present in the analysis of the algorithmic contributions (as mentioned in the discussion). To clarify this:\n- Isn’t it better to get a polynomial bound on the stopping time or a non-asymptotic bound on the expected stopping time and stronger guarantees on the sample complexity in high probability than to get an exponential-tail stopping time and a less good “recommendation performance” constant (derived from fixed-budget algorithms, where it is unclear whether such constants would match (even with logarithmic factors) the lower bounds on the minimal sample complexity for $\\delta$-correct algorithms [1-2])?\n[1] Kaufmann, E., Cappé, O., & Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1), 1-42.\n[2] Degenne, R. (2023, July). On the existence of a complexity in fixed budget bandit identification. In The Thirty Sixth Annual Conference on Learning Theory (pp. 1131-1154). PMLR.\n- Could you perform the same kind of experiments run on Successive Elimination on FC-DSH or on BrakeBooster with Successive Elimination?\n- Can you compare computationally speaking the cost of FC-DSH compared to other algorithms from the literature?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the best arm identification problem in the fixed confidence setting. The main contribution is a meditation on the standard delta-PAC correct stopping time, focusing on the idea that it may have heavy tails, indicating that standard results may be misleading. The paper desires exponential tails for the stopping time and demonstrates a framework to achieve successful results for any input algorithm under standard conditions. During the review process, there was a vibrant discussion about the practicality of the approach that left some reviewers wanting. However, all agreed the paper was well executed otherwise and provided a clear technical contribution to the best arm identification literature.
Decision: Accept (poster)