Research map / Bandits and online learning / Multi-armed bandits
Non-stationary and structured-reward bandits
Handle rising, restless, blocking, and recovering reward dynamics in bandit algorithms.
140 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.
30 papers in 2023–24 and 25 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 28.3% to 20.0%.
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 · Conservative Bandits (ICML 2016 · 27 citations)
- 2017 · Rotting Bandits (NeurIPS 2017 · 30 citations)
- 2018 · A Change-Detection Based Framework for Piecewise-Stationary Multi-Armed Bandit Problem (AAAI 2018 · 88 citations)
- 2019 · Incorporating Behavioral Constraints in Online AI Systems (AAAI 2019 · 59 citations)
- 2020 · Achieving Fairness in the Stochastic Multi-Armed Bandit Problem (AAAI 2020 · 64 citations)
- 2021 · Online Multi-Armed Bandits with Adaptive Inference (NeurIPS 2021 · 13 citations)
- 2022 · Modeling Attrition in Recommender Systems with Departing Bandits (AAAI 2022 · 5 citations)
- 2023 · Optimistic Whittle Index Policy: Online Learning for Restless Bandits (AAAI 2023 · 14 citations)
- 2024 · Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonment (NeurIPS 2024 · 8 citations)
- 2025 · Robust Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents (AAAI 2025 · 2 citations)
- 2026 · Provably Efficient Multi-Objective Bandit Algorithms Under Preference-Centric Customization (AAAI 2026 · 1 citation)
Earliest papers here
- Conservative Bandits (ICML 2016 · 27 citations)
- Combinatorial semi-bandit with known covariance (NeurIPS 2016 · 24 citations)
- Threshold Bandits, With and Without Censored Feedback (NeurIPS 2016 · 17 citations)
What has been tried
111 papers here report 699 measured changes (a component added, removed or swapped, compared with a baseline): helped 63%, no clear effect 7%, hurt 22%, mixed 8%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Greedily enforce fairness satisfaction at the beginning of each episode | Simulated environments · accumulated reward regret | Mixed | Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints (AAAI 2024 · 7 citations) | |
| Reduce Shapley estimation samples from 1000 to 100, 10, or 1 | Synthetic data · normalized reward | No clear effect | Global Rewards in Restless Multi-Armed Bandits (NeurIPS 2024 · 2 citations) | |
| Add learned communication instead of training without communication | Synthetic (N=21, B=15), 100% noise · normalized return | 62% -> 75% | Helped | The Bandit Whisperer: Communication Learning for Restless Bandits (AAAI 2025 · 1 citation) |
| Use constant or linear forced-exploration sequences | Stationary Gaussian and Bernoulli rewards · cumulative expected regret | No clear effect | Forced Exploration in Bandit Problems (AAAI 2024 · 1 citation) | |
| Decrease α in EXP3-N-CS | 101-unit network simulation · confidence-sequence width | Mixed | Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference (NeurIPS 2025 · 0 citations) | |
| Add an upper threshold θ_r > 0 for the random walks to stop pulling the best arm early | MAB, tΔ² ∈ ω(1) ∩ n^{o(1)} · mutual information | O\pth{\frac{t\Delta^2\log(t\Delta^2)}{n}}=o(I_t^\star) | Hurt | Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits (NeurIPS 2025 · 0 citations) |
| add on-demand query allocation to BaQue | stable or mildly changing environments in ConFee-nsMAB · dynamic regret | Helped | Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · 0 citations) | |
| Use asymmetric-PE, reusing more advanced reference-arm samples | Known reference arm setting · regret | Helped | Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy (ICLR 2025 · 0 citations) | |
| Use the SEWRST stopping condition N_k \leqslant T/K instead of the additive-C stopping condition | Known attack budget C · realized regret upper bound | O\left( \sqrt{KT\log (KT/\delta)} + KC \right) ; O\left( \sqrt{KT(\log (KT/\delta) + C)} \right) | Mixed | Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 18 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- MovieLens 25M · 2 of 18 papers
Baselines
- UCB1 · 2 of 18 papers
- EXP3 · 2 of 18 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 55 papers; from OpenAlex and the papers' affiliations).
- Google · 8 papers
- Harvard University · 4 papers
- Microsoft · 4 papers
- Polytechnic Institute of Milan · 4 papers
- Politecnico di Milano · 4 papers
- University of Chicago · 3 papers
- Carnegie Mellon University · 3 papers
- University of Maryland, College Park · 2 papers
- University of Oslo · 2 papers
- University of Maryland · 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
- Optimal stochastic bandit algorithms (124 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).