Research map / Learning theory and algorithms / Sample complexity
Optimal Batched 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.
Proposes Tri-BBAI, a three-batch best-arm-identification algorithm achieving asymptotically optimal sample complexity, and Opt-BBAI, which adds a best-arm-elimination check to get near-optimal non-asymptotic sample and O(log(1/Δ2)) batch complexity.
Problem
Batched best arm identification with fixed confidence: identify the best arm with probability 1-δ while minimizing both total arm pulls and number of batches, in both asymptotic (δ→0) and finite-confidence regimes.
Approach
Tri-BBAI uses a few batches of exploration with allocations from the optimal-allocation solver (w*, T*) evaluated at confidence-shifted empirical means, followed by a Chernoff stopping test; Opt-BBAI replaces the final stage with successive elimination plus a procedure that re-pulls arms to check whether the best arm was wrongly eliminated, so complexity does not depend on that low-probability eve
Key results
- Tri-BBAI achieves asymptotically optimal sample complexity (limsup E[N]/log(1/δ) ≤ α T*(μ)) with 3 expected batches as δ→0.
- Opt-BBAI achieves E[N] ≤ C Σ_{i>1} Δ_i^{-2} log(n log Δ_i^{-1}) with C log(1/Δ2) expected batches for finite δ.
- Opt-BBAI keeps asymptotic optimality and 3 expected batches as δ→0, and its complexity does not depend on the event that the best arm is returned.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Tri-BBAI instead of a fully sequential best-arm identification algorithm | BBAI · BBAI, asymptotic (δ→0) | batch complexity | Helped |
| use Opt-BBAI with successive elimination and best-arm-elimination checking | BBAI · BBAI, finite confidence | sample complexity | Helped |
| use Opt-BBAI with successive elimination and best-arm-elimination checking | BBAI · BBAI, finite confidence | batch complexity | Helped |
| use Tri-BBAI instead of Track-and-Stop | BBAI · various problem instances | batch complexity | Helped |
| use Tri-BBAI instead of Track-and-Stop | BBAI · various problem instances | sample complexity | Mixed |
| use Opt-BBAI instead of earlier elimination-based batched algorithms | BBAI · finite confidence | sample complexity | Helped |
Surprising findings
- Tri-BBAI's sample complexity does not match Track-and-Stop in experiments, although it uses far fewer batches.
- Prior batched elimination algorithms can have unbounded expected sample and batch complexity conditioned on wrongly eliminating the best arm (illustrated by an example with tied suboptimal arms).
Limitations
- Tri-BBAI's empirical sample complexity is worse than Track-and-Stop's.
- Non-asymptotic guarantees hold only up to universal constants and log factors (near-optimal, not exactly optimal).
- Assumes a unique best arm and one-parameter exponential family rewards bounded in [0,1].
Experimental setup
Metrics: sample complexity batch complexity probability of correct identification
Baselines: Track-and-Stop Top-k δ-Elimination
Builds on: Track-and-Stop Successive Elimination Chernoff stopping rule
Closest papers by meaning
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.92)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.90)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.88)
- Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback (NeurIPS 2026 · similarity 0.88)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · 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.