Research map / Bandits and online learning / Multi-armed bandits
Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids
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.
Proposes instance-sensitive successive elimination (IS-SE) and instance-sensitive RAGE (IS-RAGE) for fixed-confidence batched best arm identification in MAB and linear bandits, using adaptive batch grids that break the log(1/Δ2) batch barrier while keeping near-optimal sample complexity.
Problem
Batched best arm identification in multi-armed and linear bandits under the adaptive-grid model: minimize both sample and batch complexity; prior methods need Theta(log(1/Δ2)) batches.
Approach
Augment successive elimination/RAGE's geometric batch-size growth with an extra per-arm budget equal to the estimated instance complexity of already-eliminated arms, spread uniformly over remaining arms, so batch sizes adapt to the instance and batch count is bounded by an instance-dependent R_I (≤ alpha + log(H_I/n)).
Key results
- On synthetic instances B1(n) and B2(n), IS-SE attains O(1) batches versus Theta(log n) for SE, at comparable sample complexity.
- On instance B3(n), IS-SE and SE perform nearly identically, consistent with the theory that R_I = O(log n) there.
- IS-SE consistently outperforms SE on the MovieLens-25M sample-batch tradeoff.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Instance-Sensitive Successive Elimination (IS-SE) instead of SE | MAB · Synthetic B1(n) and B2(n) | batch complexity | Helped |
| Use Instance-Sensitive RAGE (IS-RAGE) instead of RAGE | Linear bandits · Synthetic B1(n) and B2(n) | batch complexity | Helped |
| Use IS-SE instead of SE | MAB · Synthetic B3(n) | sample-batch tradeoff | No clear effect |
| Use IS-RAGE instead of RAGE | Linear bandits · Synthetic B3(n) | sample-batch tradeoff | No clear effect |
| Use IS-SE instead of SE | MAB · MovieLens25M | sample-batch tradeoff | Helped |
Surprising findings
- On the third synthetic instance the proposed method gives no batch advantage over SE, which the authors attribute to the instance structure.
Limitations
- Sample complexity carries an extra log n * min{log n, log(1/Δ2)} factor over the optimal H_I.
- Batch advantage is instance-dependent and vanishes on some instances (e.g., B3), where it matches SE.
- Experiments are limited to small synthetic instances and a single real dataset with truncated ratings.
Experimental setup
Datasets: MovieLens-25M (top 1,000 movies, first 50 ratings each)
Benchmarks: synthetic bandit instances B1, B2, B3 MovieLens-25M bandit
Metrics: number of batches sample complexity
Baselines: successive elimination (SE) RAGE
Builds on: successive elimination RAGE
Closest papers by meaning
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.92)
- Optimal Batched Best Arm Identification (NeurIPS 2024 · similarity 0.92)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.92)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.91)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.91)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · 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.