Research map / Bandits and online learning / Multi-armed bandits
Pure exploration algorithms
Design efficient pure-exploration and thresholding algorithms with batch and combinatorial structure.
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.
9 papers in 2023–24 and 16 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 8.5% to 12.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 · An optimal algorithm for the Thresholding Bandit Problem (ICML 2016 · 64 citations)
- 2017 · Identifying Best Interventions through Online Importance Sampling (ICML 2017 · 19 citations)
- 2018 · Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors (ICML 2018 · 4 citations)
- 2019 · Pure Exploration with Multiple Correct Answers (NeurIPS 2019 · 35 citations)
- 2020 · Concentration bounds for CVaR estimation: The cases of light-tailed and heavy-tailed distributions (ICML 2020 · 26 citations)
- 2021 · Quantum Exploration Algorithms for Multi-Armed Bandits (AAAI 2021 · 18 citations)
- 2022 · Near-Optimal Collaborative Learning in Bandits (NeurIPS 2022 · 4 citations)
- 2023 · Collaborative Pure Exploration in Kernel Bandit (ICLR 2023 · 0 citations)
- 2024 · Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (AAAI 2024 · 5 citations)
- 2025 · Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap (AAAI 2025 · 1 citation)
- 2026 · Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments (ICML 2026 · 0 citations)
Earliest papers here
- An optimal algorithm for the Thresholding Bandit Problem (ICML 2016 · 64 citations)
- Anytime Exploration for Multi-armed Bandits using Confidence Information (ICML 2016 · 4 citations)
- Identifying Best Interventions through Online Importance Sampling (ICML 2017 · 19 citations)
What has been tried
45 papers here report 260 measured changes (a component added, removed or swapped, compared with a baseline): helped 66%, no clear effect 10%, hurt 18%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use the choice-only estimator with weak-preference design instead of transductive design | Synthetic sphere problem, moderate preference scaling · best-arm identification error | Helped | Enhancing Preference-based Linear Bandits via Human Response Time (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).
- University of Arizona · 3 papers
- Inria · 3 papers
- Microsoft · 2 papers
- Tsinghua University · 2 papers
- Massachusetts Institute of Technology · 2 papers
- University of Washington · 2 papers
- University of Michigan - Ann Arbor · 2 papers
Use it
Download BibTeX of 39 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
- Best-arm identification in linear bandits (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).