Research map / Bandits and online learning / Multi-armed bandits
Best-arm identification in linear bandits
Identify the best arm with optimal sample complexity for linear and fixed-budget settings.
57 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Multi-armed bandits, keyword cluster “identification · best arm · pure exploration”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
14 papers in 2023–24 and 11 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 13.2% to 8.8%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Refined Lower Bounds for Adversarial Bandits (NeurIPS 2016 · 55 citations)
- 2017 · PAC Identification of a Bandit Arm Relative to a Reward Quantile (AAAI 2017 · 19 citations)
- 2018 · Best Arm Identification in Linear Bandits with Linear Dimension Dependency (ICML 2018 · 32 citations)
- 2019 · Optimal Best Markovian Arm Identification with Fixed Confidence (NeurIPS 2019 · 11 citations)
- 2020 · Optimal Best-arm Identification in Linear Bandits (NeurIPS 2020 · 21 citations)
- 2021 · Optimal Best-Arm Identification Methods for Tail-Risk Measures (NeurIPS 2021 · 7 citations)
- 2022 · Instance-optimal PAC Algorithms for Contextual Bandits (NeurIPS 2022 · 2 citations)
- 2023 · Adaptive Algorithms for Relaxed Pareto Set Identification (NeurIPS 2023 · 3 citations)
- 2024 · Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · 1 citation)
- 2025 · Linear Streaming Bandit: Regret Minimization and Fixed-Budget Epsilon-Best Arm Identification (AAAI 2025 · 0 citations)
- 2026 · The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits (NeurIPS 2026 · 0 citations)
Earliest papers here
- Refined Lower Bounds for Adversarial Bandits (NeurIPS 2016 · 55 citations)
- Verification Based Solution for Structured MAB Problems (NeurIPS 2016)
- PAC Identification of a Bandit Arm Relative to a Reward Quantile (AAAI 2017 · 19 citations)
What has been tried
46 papers here report 291 measured changes (a component added, removed or swapped, compared with a baseline): helped 64%, no clear effect 10%, hurt 19%, mixed 7%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| use Max-Det collections to exploit the linear structure of arm means | Synthetic linear BAI · best-arm identification success rate | Helped | Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · 1 citation) | |
| use tighter law-of-the-iterated-logarithm confidence bonuses | Constrained PSI experiments · sample complexity | Helped | Constrained Pareto Set Identification with Bandit Feedback (ICML 2025 · 0 citations) | |
| vary exploration parameter a across {a*/50, a*/10, a*, 10a*, 50a*} | Synthetic Gaussian SRB, T ≤ 185 · empirical error probability | Mixed | Best Arm Identification for Stochastic Rising Bandits (ICML 2024 · 0 citations) | |
| Misspecify Lmax slightly | PSLB synthetic instance · sample complexity | No clear effect | Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 25 papers; from OpenAlex and the papers' affiliations).
- KTH Royal Institute of Technology · 5 papers
- National University of Singapore · 3 papers
- CNRS · 3 papers
- Tsinghua University · 2 papers
- Université de Lille · 2 papers
- Inria · 2 papers
- INRAE · 2 papers
Use it
Download BibTeX of 34 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Pure exploration algorithms (57 papers)
- Fixed-confidence versus fixed-budget identification (35 papers)
Elsewhere in the topic
- Non-stationary and structured-reward bandits (140 papers)
- Optimal stochastic bandit algorithms (124 papers)
- Multi-agent bandits (42 papers)
- Bandit formulations for ML problems (42 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).