Research map / Bandits and online learning / Multi-armed bandits
On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs
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.
Analyzes the asymptotic (delta to 0) sample complexity and termination pull fractions of the LUCB algorithm, introduces LUCB Greedy, and shows both are within a constant factor of the instance-dependent lower bound for fixed-confidence best arm identification.
Problem
Fixed-confidence best arm identification in stochastic multi-armed bandits: confidence-interval based algorithms have loose sample complexity upper bounds that cannot be directly compared with information-theoretic lower bounds, so their asymptotic optimality is unknown.
Approach
Derives asymptotic (as delta goes to 0) characterizations of stopping time and termination pull fractions for LUCB (with forced exploration and a non-forced-exploration clock), and proposes LUCB Greedy, which pulls only one of the top/challenger arms (the less-pulled one), obtaining asymptotic upper bounds within constant factors of the lower bound.
Key results
- Expected stopping time of LUCB satisfies limsup E(t)/log(1/delta) <= 4 alpha / M^2 (Theorem 3), within a constant factor 6 alpha of the lower bound for Gaussian instances (Corollary 3.1).
- LUCB Greedy satisfies limsup E(t)/log(1/delta) <= 2 alpha M_g (Theorem 5), giving a bound 4 alpha times the lower bound, and this bound is tight for 2-armed instances (Corollary 5.1).
- In simulations, LUCB outperforms LUCB Greedy on a 10-arm instance with equal suboptimal means, while LUCB Greedy outperforms LUCB on a second 10-arm instance; empirical gaps to the lower bound are smaller than the theoretical 4 alpha factor (alpha = 1.2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LUCB Greedy's one-arm-at-a-time sampling rule instead of sampling both the top and challenger arms | LUCB · MAB instances (asymptotic sample complexity) | sample complexity | Mixed |
| Use LUCB Greedy's one-arm-at-a-time sampling rule instead of sampling both the top and challenger arms | LUCB · µ1µ1µ1, 10-arm Gaussian instance | sample complexity | Hurt |
| Use LUCB Greedy's one-arm-at-a-time sampling rule instead of sampling both the top and challenger arms | LUCB · µ2µ2µ2, 10-arm Gaussian instance | sample complexity | Helped |
| Use LUCB Greedy's one-arm-at-a-time sampling rule instead of sampling both the top and challenger arms | LUCB · µ1µ1µ1, 10-arm Gaussian instance | best-arm termination pull fraction relative to optimal | Mixed |
Surprising findings
- Neither LUCB nor LUCB Greedy dominates the other; which is better depends on the bandit instance.
- The upper bound for LUCB Greedy is tight for 2-armed instances, matching the lower bound up to the alpha factor.
Limitations
- Theoretical bounds on LUCB and LUCB Greedy are upper bounds with constant factors (6 alpha and 4 alpha) that are not tight.
- Analysis uses a modified LUCB with forced exploration and a non-forced-exploration clock, not the exact classical algorithm.
- Asymptotic results are for 1-Gaussian bandits in the expected-sample-complexity comparison with the lower bound.
Experimental setup
Benchmarks: simulated 10-arm 1-Gaussian bandit instances
Metrics: expected sample complexity pull fractions at termination ratio to information-theoretic lower bound
Baselines: LUCB Track & Stop lower bound (T*(mu))
Builds on: LUCB Track & Stop Lower bound of Garivier and Kaufmann 2016
Closest papers by meaning
- Optimal Estimation of the Best Mean in Multi-Armed Bandits (NeurIPS 2025 · similarity 0.91)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.89)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.89)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.88)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.88)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.88)
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.