Research map / Bandits and online learning / Multi-armed bandits
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models
Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use exploration rate log((log t +1)/delta) instead of log(t/delta) in elimination (ablation) | Elimination algorithm · Gaussian two-armed, difficult model | running time at comparable error: about three times longer | Improved |
| use exploration rate log((log t +1)/delta) instead of log(1/delta) (ablation) | Elimination algorithm · Gaussian two-armed difficult model | empirical error probability vs delta | Improved |
| use SGLRT stopping rule instead of 1/2-Elimination | Bernoulli bandit model 0.2 vs 0.1 · sample complexity | samples | Improved |
| use SGLRT stopping rule instead of 1/2-Elimination | Bernoulli bandit model 0.51 vs 0.5 · sample complexity | samples | No clear effect |
| use fixed-budget instead of fixed-confidence algorithm for same error probability | Two-armed bandits · number of samples | samples: about twice larger | Improved |
Closest papers by meaning
- Bandits with many optimal arms (NeurIPS 2021 · similarity 0.93)
- Constrained Best Arm Identification (NeurIPS 2025 · similarity 0.93)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.92)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.91)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.91)
- Best Arm Identification for Stochastic Rising Bandits (ICML 2024 · similarity 0.91)
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.
