Research map / Bandits and online learning / Multi-armed bandits
Optimal stochastic bandit algorithms
Characterize regret-optimal algorithms for stochastic, batched, and combinatorial bandits.
124 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Multi-armed bandits, keyword cluster “multi armed · armed bandit · stochastic”
State History Tried Checklist 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.
21 papers in 2023–24 and 37 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 19.8% to 29.6%.
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 · Algorithms for Differentially Private Multi-Armed Bandits (AAAI 2016 · 78 citations)
- 2017 · Minimal Exploration in Structured Stochastic Bandits (NeurIPS 2017 · 79 citations)
- 2018 · Efficient-UCBV: An Almost Optimal Algorithm Using Variance Estimates (AAAI 2018 · 57 citations)
- 2019 · Batched Multi-armed Bandits Problem (NeurIPS 2019 · 41 citations)
- 2020 · A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits (AAAI 2020 · 19 citations)
- 2021 · Regret Bounds for Batched Bandits (AAAI 2021 · 23 citations)
- 2022 · On Kernelized Multi-Armed Bandits with Constraints (NeurIPS 2022 · 11 citations)
- 2023 · Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets (AAAI 2023 · 10 citations)
- 2024 · Multiobjective Lipschitz Bandits under Lexicographic Ordering (AAAI 2024 · 4 citations)
- 2025 · Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits (AAAI 2025 · 1 citation)
- 2026 · Improved Algorithms for Nash Welfare in Linear Bandits (ICML 2026 · 0 citations)
Earliest papers here
- Algorithms for Differentially Private Multi-Armed Bandits (AAAI 2016 · 78 citations)
- Combinatorial Multi-Armed Bandit with General Reward Functions (NeurIPS 2016 · 75 citations)
- On Explore-Then-Commit strategies (NeurIPS 2016 · 57 citations)
What has been tried
90 papers here report 500 measured changes (a component added, removed or swapped, compared with a baseline): helped 66%, no clear effect 11%, hurt 16%, 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 |
|---|---|---|---|---|
| Set ε to 0.2 or 0.5 instead of ε⋆ | Online social influence maximization, k=8 · cumulative regret | Hurt | Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · 3 citations) | |
| Increase the trade-off parameter from λ=0.2 to λ=2 | Third objective · general regret | Helped | Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits (AAAI 2025 · 1 citation) | |
| Use EnsembleAdaptiveEfficient instead of EnsembleAdaptive | Synthetic MAB benchmarks · averaged pseudo-regret | Mixed | Batch Ensemble for Variance Dependent Regret in Stochastic Bandits (AAAI 2025 · 0 citations) | |
| Increase the exploration parameter α | AutoML tasks, small budgets · performance | Hurt | Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning (NeurIPS 2025 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 28 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- UCB · 2 of 28 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 58 papers; from OpenAlex and the papers' affiliations).
- Google · 4 papers
- City University of Hong Kong · 3 papers
- Carnegie Mellon University · 3 papers
- University of Washington · 2 papers
- Indian Institute of Science · 2 papers
- Purdue University · 2 papers
- King Abdullah University of Science and Technology · 2 papers
- Iowa State University · 2 papers
- The City University of Hong Kong Shenzhen Research Institute · 2 papers
- Tel Aviv University · 2 papers
Use it
Download BibTeX of 40 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
- Non-stationary and structured-reward bandits (140 papers)
- Multi-agent bandits (42 papers)
- Bandit formulations for ML problems (42 papers)
Elsewhere in the topic
- Best-arm identification in linear bandits (57 papers)
- Pure exploration algorithms (57 papers)
- Fixed-confidence versus fixed-budget identification (35 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).