Research map / Bandits and online learning / Multi-armed bandits
Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that standard fixed-confidence BAI algorithms (Successive Elimination, KL-LUCB) can fail to stop with constant probability, then proposes FC-DSH and a meta-algorithm BrakeBooster that achieve exponential-tailed stopping times with near-optimal high-probability sample complexity.
Problem
Fixed-confidence best arm identification guarantees (high-probability or expected sample complexity) say nothing about the tail of the stopping time; standard algorithms may heavy-tail or never stop.
Approach
Introduce a fixed-confidence variant of Doubling Sequential Halving with a confidence-bound stopping rule, and a meta-algorithm (BrakeBooster) that uses a two-dimensional doubling schedule over trial counts and per-trial budgets with majority voting and forced termination to turn any high-probability BAI algorithm into one with an exponential stopping tail.
Key results
- Successive Elimination and KL-LUCB fail to stop with constant probability on a three-arm Gaussian instance (lower bound Omega(delta^118) for SE).
- FC-DSH achieves an (H_2 log(1/delta), H_2 polylog)-exponential stopping tail and is delta-correct.
- BrakeBooster applied to Successive Elimination yields a (H_1 ln(1/delta), H_1)-exponential stopping tail, with the CDF catching up to bare SE quickly in simulations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FC-DSH: double the Sequential Halving phase budget and stop when confidence bounds separate | Fixed-confidence best-arm identification · Fixed-confidence best-arm identification | stopping-time tail: $(\tilde{\Theta}(H_2\log(1/\delta)),~\tilde{\mathcal{O}}(H_2))$-exponential stopping tail | Helped |
| Wrap a base algorithm in repeated budgeted trials with majority voting and a two-dimensional doubling schedule | Any $\delta_0$-correct fixed-confidence algorithm with a sample-complexity guarantee · Fixed-confidence best-arm identification | stopping-time tail: $(\tilde{\Theta}(T^*_{\delta_0}(\mathcal{A})\ln(1/\delta)),T^*_{\delta_0}(\mathcal{A}))$-exponential stopping tail | Helped |
| Apply BrakeBooster to Successive Elimination | Successive Elimination · Fixed-confidence best-arm identification | stopping-time tail: $(\tilde{\Theta}(H_1\ln(1/\delta)), \tilde{\mathcal{O}}(H_1))$-exponential stopping tail | Helped |
| Use Successive Elimination without BrakeBooster | Successive Elimination · Fixed-confidence best-arm identification | probability of never stopping: $\Omega\del{\delta^{118}}$ | Hurt |
| Use KL-LUCB without a mechanism that guarantees eventual stopping | KL-LUCB · Fixed-confidence best-arm identification | probability of never stopping: constant probability | Hurt |
| Use uniform sampling with a suitable stopping condition | Fixed-confidence best-arm identification · Fixed-confidence best-arm identification | sample complexity: $\tcO(K\Delta_2^{-2}\ln(1/\delta))$ vs. $\tcO(H_1\ln(1/\delta))$ | Hurt |
Surprising findings
- Successive Elimination and KL-LUCB never stop with constant probability on some instances, despite having high-probability guarantees.
- An epsilon-slack stopping condition yields only a weaker, uniform-sampling-like exponential tail.
Limitations
- Both algorithms add constant or logarithmic factors over optimal instance-dependent sample complexity.
- BrakeBooster's exponent includes a polylog(T) term.
- The resetting mechanism is less practical.
Experimental setup
Metrics: stopping time distribution CDF of stopping time fraction of non-stopping trials high-probability sample complexity
Baselines: Successive Elimination KL-LUCB LUCB1 uniform sampling AT-LUCB
Builds on: Sequential Halving Successive Elimination KL-LUCB Doubling Sequential Halving
Closest papers by meaning
- Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback (NeurIPS 2026 · similarity 0.89)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.89)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.89)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.88)
- Optimal Batched Best Arm Identification (NeurIPS 2024 · similarity 0.88)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.