Research map / Bandits and online learning / Multi-armed bandits
Fixed Confidence Best Arm Identification in the Bayesian Setting
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.
Studies fixed-confidence best arm identification under a known Gaussian prior, showing frequentist-optimal algorithms (track-and-stop, top-two) have diverging expected stopping time, deriving a lower bound Omega(L(H)^2/delta), and proposing an elimination algorithm with early stopping matching it up to log factors.
Problem
Fixed-confidence best arm identification when the bandit model is drawn from a known prior, where frequentist-optimal stopping rules can have unbounded expected sample size.
Approach
Relaxes δ-correctness to Bayesian δ-correctness (expected misidentification probability over the prior) and adds an indifference-zone early stopping rule to successive elimination, with the threshold Δ0 = δ/(4L(H)) derived from the prior's volume constant L(H).
Key results
- In a k=2 standard Gaussian prior setting (delta=0.1), the proposed algorithm averages 1.06e4 samples versus 1.56e5 for TTTS and 1.95e5 for TTUCB, with max stopping times of 2.35e5 vs about 1e8 for the top-two methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Successive Elimination with Early-Stopping instead of TTTS | Bayesian FC-BAI · 2-arm Gaussian prior, δ=0.1 | Avg stopping time: $1.56\times 10^5$ -> $1.06 \times 10^4$ | Helped |
| Use Successive Elimination with Early-Stopping instead of TTUCB | Bayesian FC-BAI · 2-arm Gaussian prior, δ=0.1 | Avg stopping time: $1.95\times 10^5$ -> $1.06 \times 10^4$ | Helped |
| Add arm elimination (ablation) | Successive Elimination with Early-Stopping · 10-arm Gaussian prior, δ=0.01 | Avg stopping time: $1.29\times 10^6$ -> $2.69\times 10^5$ | Helped |
| Add arm elimination (ablation) | Successive Elimination with Early-Stopping · 10-arm Gaussian prior, δ=0.01 | Error: 0% -> 0.6% | Hurt |
Surprising findings
- Frequentist delta-correct algorithms have infinite expected stopping time under any prior, since marginalizing the sample complexity over the prior diverges.
Limitations
- Upper bound matches lower bound only up to a log(L(H)/delta) factor and a (max sigma/min sigma)^2 gap
- Analysis restricted to Gaussian bandits with known variances and a correctly specified prior
- Track-and-stop was not simulated due to per-round optimization cost
Experimental setup
Benchmarks: simulated two-armed and ten-armed Gaussian Bayesian FC-BAI instances
Metrics: average stopping time maximum stopping time misidentification error ratio computation time
Baselines: Top-two Thompson sampling (TTTS) Top-two UCB (TTUCB) NoElim variant of the proposed algorithm
Builds on: track-and-stop top-two Thompson sampling successive elimination PAC-(epsilon,delta) identification
Closest papers by meaning
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.92)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.90)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
- Near Optimal Best Arm Identification for Clustered Bandits (ICML 2025 · similarity 0.89)
- On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs (AAAI 2025 · similarity 0.89)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.89)
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.