mlsanityData to 7 Oct 2026

Introduction to Multi-Armed Bandits

arXiv 1904.07272 ↗First posted 15 Apr 2019cs.LG cs.AI cs.DScited by 475

Not on the map. Why?

Abstract (arXiv)

Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a particular line of work, providing a self-contained, teachable technical introduction and a brief review of the further developments; many of the chapters conclude with exercises. The book is structured as follows. The first four chapters are on IID rewards, from the basic model to impossibility results to Bayesian priors to Lipschitz rewards. The next three chapters cover adversarial rewards, from the full-feedback version to adversarial bandits to extensions with linear rewards and combinatorially structured actions. Chapter 8 is on contextual bandits, a middle ground between IID and adversarial bandits in which the change in reward distributions is completely explained by observable contexts. The last three chapters cover connections to economics, from learning in repeated games to bandits with supply/budget constraints to exploration in the presence of incentives. The appendix provides sufficient background on concentration and KL-divergence. The chapters on "bandits with similarity information", "bandits with knapsacks" and "bandits and agents" can also be consumed as standalone surveys on the respective topics.

Key facts. Cited by 475 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 72; 2022: 86; 2023: 88; 2024: 86; 2025: 96; 2026: 47.

475 papers.

Sort:

By area:

  1. 2024Can large language models explore in-context?cited by 75
  2. 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 59
  3. 2022Off-Policy Evaluation for Large Action Spaces via Embeddingscited by 53
  4. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  5. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  6. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  7. 2021Fairness of Exposure in Stochastic Banditscited by 42
  8. 2024M-RAG: Reinforcing Large Language Model Performance through Retrieval-Augmented Generation with Multiple Partitionscited by 38
  9. 2024Cost-Effective Online Multi-LLM Selection with Versatile Reward Modelscited by 36
  10. 2025LLMs are Greedy Agents: Effects of RL Fine-tuning on Decision-Making Abilitiescited by 36
  11. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  12. 2025Memory, Benchmark & Robots: A Benchmark for Solving Complex Tasks with Reinforcement Learningcited by 34
38 more
  1. 2025MAT-Agent: Adaptive Multi-Agent Training Optimizationcited by 34
  2. 2024EVOLvE: Evaluating and Optimizing LLMs For In-Context Explorationcited by 33
  3. 2025Meta-Reasoner: Dynamic Guidance for Optimized Inference-time Reasoning in Large Language Modelscited by 33
  4. 2024Speculative Decoding via Early-exiting for Faster LLM Inference with Thompson Sampling Control Mechanismcited by 31
  5. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  6. 2021Beyond log2(T) Regret for Decentralized Bandits in Matching Marketscited by 29
  7. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  8. 2021Bilateral Trade: A Regret Minimization Perspectivecited by 29
  9. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  10. 2025Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimizationcited by 29
  11. 2025Training a Generally Curious Agentcited by 29
  12. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  13. 2023Designing Decision Support Systems Using Counterfactual Prediction Setscited by 26
  14. 2021Stochastic Bandits for Multi-platform Budget Optimization in Online Advertisingcited by 25
  15. 2021Causal Decision Making and Causal Effect Estimation Are Not the Same... and Why It Matterscited by 25
  16. 2022Hindsight Learning for MDPs with Exogenous Inputscited by 25
  17. 2023On the Sublinear Regret of GP-UCBcited by 25
  18. 2025Reinforce-Ada: An Adaptive Sampling Framework under Non-linear RL Objectivescited by 23
  19. 2021Survival of the strictest: Stable and unstable equilibria under regularized learning with partial informationcited by 22
  20. 2021Batched Neural Banditscited by 22
  21. 2022Replicable Banditscited by 22
  22. 2024Contracting with a Learning Agentcited by 22
  23. 2025Speculative Decoding and Beyond: An In-Depth Survey of Techniquescited by 22
  24. 2025OptimAI: Optimization from Natural Language Using LLM-Powered AI Agentscited by 22
  25. 2024Adaptive Memory Replay for Continual Learningcited by 21
  26. 2021Parallelizing Thompson Samplingcited by 20
  27. 2023Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamicscited by 20
  28. 2021A Regret Analysis of Bilateral Tradecited by 19
  29. 2022BayesFormer: Transformer with Uncertainty Estimationcited by 19
  30. 2023A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedbackcited by 19
  31. 2022A survey on multi-player banditscited by 18
  32. 2022Fairness and Welfare Quantification for Regret in Multi-Armed Banditscited by 17
  33. 2023Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delaycited by 17
  34. 2023No-Regret Learning in Bilateral Trade via Global Budget Balancecited by 17
  35. 2022Online Prediction in Sub-linear Spacecited by 16
  36. 2022An α-regret analysis of Adversarial Bilateral Tradecited by 16
  37. 2024UCB algorithms for multi-armed bandits: Precise regret and adaptive inferencecited by 16
  38. 2021A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounderscited by 15

50 most cited of 475 All 475 (JSON)