# Introduction to Multi-Armed Bandits

arXiv: https://arxiv.org/abs/1904.07272 · HTML: https://mlsanity.com/paper/1904.07272/

## Key facts

- Cited by 481 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2019.

## Built on by (most cited first, 30 of 481)

- [Can large language models explore in-context?](https://mlsanity.com/paper/2403.15371/) (2024)
- [POPGym: Benchmarking Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2303.01859/) (2023)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Off-Policy Evaluation for Large Action Spaces via Embeddings](https://mlsanity.com/paper/2202.06317/) (2022)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [LLMs are Greedy Agents: Effects of RL Fine-tuning on Decision-Making Abilities](https://mlsanity.com/paper/2504.16078/) (2025)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [M-RAG: Reinforcing Large Language Model Performance through Retrieval-Augmented Generation with Multiple Partitions](https://mlsanity.com/paper/2405.16420/) (2024)
- [Memory, Benchmark & Robots: A Benchmark for Solving Complex Tasks with Reinforcement Learning](https://mlsanity.com/paper/2502.10550/) (2025)
- [MAT-Agent: Adaptive Multi-Agent Training Optimization](https://mlsanity.com/paper/2510.17845/) (2025)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)
- [EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration](https://mlsanity.com/paper/2410.06238/) (2024)
- [Meta-Reasoner: Dynamic Guidance for Optimized Inference-time Reasoning in Large Language Models](https://mlsanity.com/paper/2502.19918/) (2025)
- [Speculative Decoding via Early-exiting for Faster LLM Inference with Thompson Sampling Control Mechanism](https://mlsanity.com/paper/2406.03853/) (2024)
- [Training a Generally Curious Agent](https://mlsanity.com/paper/2502.17543/) (2025)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimization](https://mlsanity.com/paper/2501.17974/) (2025)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Designing Decision Support Systems Using Counterfactual Prediction Sets](https://mlsanity.com/paper/2306.03928/) (2023)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Causal Decision Making and Causal Effect Estimation Are Not the Same... and Why It Matters](https://mlsanity.com/paper/2104.04103/) (2021)
- [Reinforce-Ada: An Adaptive Sampling Framework under Non-linear RL Objectives](https://mlsanity.com/paper/2510.04996/) (2025)

## 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.