Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification

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.

I am still not convinced about the importance of the problem of heavy-tailed stopping time distributions in fixed-confidence BAI ... ?

A light-tailed distribution offers several benefits:

1. 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.

2. 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.

3. The algorithms that provide a light tailed guarantee can be easily adapted as anytime algorithms.

Furthermore, 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.

While I understand the point of disentangling correctness and sample complexity, I disagree with the following claim ... ?

That 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.

The computational efficiency of FC-DSH’s is not worse (orderwise) than other algorithms .... ?

The computational complexity we have mentioned here is not sample complexity. It is just processor time needed for algorithm implementation

Table 1: LUCB has an upper bound in high probability on the sample complexity (their Corollary 7)

Thanks for pointing it out. We will correct it in the final version.

Isn’t it better to get a polynomial bound on the stopping time or a non-asymptotic bound on the expected stopping time ..... ?

This 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.

Furthermore 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.

Could you perform the same kind of experiments ... ?

We 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.

Can you compare computationally speaking the cost of FC-DSH compared to other algorithms from the literature?

We 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.

We’d be more than happy to address any other questions and concerns.

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.

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.

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.

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.

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.

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.

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.

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).

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.

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.

We thank the reviewer for understanding our theoretical contribution and your interest in additional empirical studies. We address your comments below.

Regarding 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).

Additional empirical studies

Anonymous link for empirical results: https://zenodo.org/records/15117826

We 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.

We 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.

Figure 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.

Moreover, 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.

We’d be more than happy to address any other questions and concerns.

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.

1. 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.

2. 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.

3. Thank you for the reference "Fast Pure Exploration via Frank-Wolfe." We will incorporate it into our paper.

4. 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.

5. 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.

6. 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.

Regarding your questions

On 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$,

$

\mathbb{P}\left( \tau \geq T \right) \leq \exp\left(-\frac{T}{\kappa \cdot \log^b(T)}\right)

$

where $b$ is any positive integer. By setting the right-hand side to be less than $\delta$, we obtain

$

\frac{T}{\log^b(T)} > \kappa \log(1/\delta).

$

Determining 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)$, $T \le c \log^b(T)$

$\leftrightarrow T^{1/b} \le c^{1/b} \log(T)$

$\leftrightarrow T^{1/b} \le b c^{1/b} \log(T^{1/b})$

$\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)$

\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$}

$\leftrightarrow T^{1/b} \le 2 b c^{1/b} \left(\log(2 b c^{1/b}) - 1\right)$

$\leftrightarrow T \le c \left(2 b \left(\log(2 b c^{1/b}) - 1\right)\right)^b$

Thus $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.

In 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.

On 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.