Research map / Learning theory and algorithms / Sample complexity
Optimal Top-Two Method for Best Arm Identification and Fluid Analysis
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 Anchored Top-2 (AT2) and Improved AT2 (IAT2) for fixed-confidence best arm identification in single-parameter exponential families, choosing between the empirical leader and challenger via an anchor function, and proves asymptotic optimality using fluid ODEs derived via the implicit function theorem.
Problem
Fixed-confidence best arm identification in single-parameter exponential families: top-2 methods use a fixed leader probability beta, but the optimal beta matching the sample-complexity lower bound was unknown, while plug-in track-and-stop methods are computationally expensive.
Approach
An anchor function derived from the first-order optimality conditions of the lower-bound max-min problem decides adaptively between sampling the empirical best arm (when the anchor is positive) and the challenger arm (when non-positive), replacing a fixed beta; the limiting dynamics are analyzed as pasted ODEs via the implicit function theorem.
Key results
- AT2 and IAT2 are proven delta-correct and asymptotically optimal: limsup E[tau_delta]/log(1/delta) <= T*(mu).
- In a 4-armed Gaussian experiment (means [10,8,7,6.5]), (I)AT2 outperforms (I)TCB and beta-EB-(I)TCB for various beta in sample complexity.
- AT2 and IAT2 are reported to be computationally substantially faster than TCB-type baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AT2 instead of β-EB-(I)TCB and TCB | Best-arm identification · 4-armed Gaussian BAI, μ=[10, 8, 7, 6.5] | sample complexity | Helped |
| Use IAT2 instead of AT2, adding log arm count to the challenger index (ablation) | AT2 · Best-arm identification | sample complexity | Helped |
| Remove forced exploration (ablation) | AT2 · BAI with tied suboptimal-arm means | sample complexity | Hurt |
| Remove forced exploration (ablation) | IAT2 · BAI with tied suboptimal-arm means | sample complexity | No clear effect |
Surprising findings
- Without forced exploration, AT2's sample complexity blows up on instances with multiple sub-optimal arms of equal mean, while IAT2 remains optimal.
- Numerically, TCB does not appear to satisfy asymptotic optimality conditions.
Limitations
- Theory covers only single-parameter exponential families; extension to bounded distributions is only numerical.
- Assumes samples are independent and distributions stationary.
- Assumes a unique best arm; the forced exploration parameter is needed for theory, and AT2 may be sub-optimal with tied sub-optimal arms without it.
Experimental setup
Benchmarks: simulated Gaussian bandit instances
Metrics: sample complexity normalized index trajectories computational time
Baselines: track-and-stop beta-EB-TCB TCB ITCB
Builds on: track-and-stop top-2 algorithms transportation cost balancing (TCB) beta-EB-TCB
Closest papers by meaning
- Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits (NeurIPS 2026 · similarity 0.88)
- Optimal Batched Best Arm Identification (NeurIPS 2024 · similarity 0.87)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.86)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.86)
- Optimal Best Arm Identification under Differential Privacy (NeurIPS 2025 · similarity 0.85)
- Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? (NeurIPS 2026 · similarity 0.85)
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.