Research map / Bandits and online learning / Multi-armed bandits
Near Optimal Non-asymptotic Sample Complexity of 1-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 SEE, a sequential explore-exploit algorithm for 1-identification (deciding whether an arm exceeds a known threshold or outputting None) that gets non-asymptotic sample complexity bounds nearly matching lower bounds on both positive and negative instances.
Problem
Fixed-confidence 1-identification in multi-armed bandits: decide whether some arm's mean is at least a known threshold mu_0 (return that arm) or return None, with error probability at most delta, while minimizing expected pulls; prior results were asymptotic or only near-optimal in one case.
Approach
SEE alternates phases of an LUCB-style exploration (with a shrinking tolerance delta_k, a widened LCB radius C>1, and a temporary container to reuse samples) and an independent exploitation phase that confirms a candidate arm against mu_0 at level delta, trusting a None answer only once delta_k < delta/3.
Key results
- Upper bound on E[tau] for positive instances O(H log(1/delta) + H_1^pos log(K/Delta_{0,1})), and for negative instances O(H_1^neg (log(1/delta) + log H_1^neg)), matching lower bounds up to polylog factors.
- In the All Worse (negative) group SEE outperforms all benchmarks, with advantage growing in K.
- Adapted-TaS and adapted-MS beat SEE for K<=50 in several positive groups, but SEE beats them when K=200 in One Quarter, Half Good and All Good.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SEE instead of the benchmark algorithms | 1-identification · All Worse | empirical stopping time | Helped |
| use SEE instead of adapted-TaS and adapted-MS | 1-identification · One Quarter, Half Good, All Good (K=200) | empirical stopping time | Helped |
| use SEE instead of adapted-TaS and adapted-MS | 1-identification · One Quarter, Half Good, All Good (K≤50) | empirical stopping time | Hurt |
| use SEE instead of adapted-TaS and adapted-MS | 1-identification · Unique Qualified | empirical stopping time | Hurt |
| use SEE instead of HDoC, lilHDoC, and LUCB_G | 1-identification · Most synthetic instances | empirical stopping time | Helped |
| use SEE instead of HDoC, lilHDoC, and LUCB_G | 1-identification · Unique Qualified (K=10, 20) | empirical stopping time | Hurt |
| decrease δ | SEE relative to HDoC, lilHDoC, and LUCB_G · Synthetic instances | relative empirical stopping time | Helped |
| increase the proportion of qualified arms | SEE · Positive synthetic instances | empirical stopping time | Helped |
Surprising findings
- Adapted Track-and-Stop and Murphy Sampling, despite having no non-trivial guarantees, outperform SEE empirically for small K on several positive instance groups.
- HDoC, lilHDoC and APGAI are shown not to be (Delta,delta)-PAC, since E[tau] can be infinite on a simple two-arm positive instance.
Limitations
- Upper and lower bounds differ by polylog factors, and the delta-independent term is not tight when multiple arms exceed the threshold.
- Adapted baselines (MS, TaS with GLR) lack theoretical guarantees, so comparisons are heuristic.
- Lower bound for arms below threshold holds only for small Delta_{0,1}, so the log(1/Delta) term is not shown to be necessary in general.
Experimental setup
Benchmarks: synthetic Gaussian bandit instances (All Worse, Unique Qualified, One Quarter, Half Good, All Good, Linear)
Metrics: expected number of arm pulls (sample complexity)
Baselines: HDoC lilHDoC LUCB_G Murphy Sampling (adapted) Track-and-Stop (adapted)
Builds on: LUCB Track-and-Stop HDoC APGAI lilHDoC
Closest papers by meaning
- Asymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits (NeurIPS 2023 · similarity 0.91)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.90)
- Fast Pure Exploration via Frank-Wolfe (NeurIPS 2021 · similarity 0.89)
- Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits (NeurIPS 2026 · similarity 0.89)
- Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap (AAAI 2025 · similarity 0.88)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.87)
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.