Introduction to Multi-Armed Bandits
Aleksandrs Slivkins
Synthesizes the theoretical foundations and algorithms of multi-armed bandits into a self-contained pedagogical resource, connecting classic stochastic and adversarial settings with modern extensions in contextual learning and economic incentives.
Modern digital platforms and sequential decision systems—such as recommendation engines, dynamic pricing algorithms, clinical trial planners, and network routers—frequently make decisions over time under uncertainty. In these settings, a decision-maker chooses an action (an "arm") from a set of alternatives and observes an immediate reward only for the selected choice, while remaining blind to the outcomes of unselected options. Addressing this fundamental exploration-versus-exploitation dilemma is essential to maximizing long-term performance without incurring heavy near-term losses from suboptimal choices.
The article provides a systematic, foundational framework for evaluating multi-armed bandit models, characterizing theoretical performance limits, and deriving optimal decision-making algorithms across discrete, continuous, and structured action spaces. It establishes both upper and lower performance bounds, measured via cumulative regret—the expected revenue or reward lost relative to playing the optimal action from the start.
The investigation combines rigorous mathematical analysis, probability theory (notably concentration inequalities), and information theory (such as Kullback-Leibler divergence) to evaluate and design sequential policies. It evaluates non-adaptive methods (Explore-First, Epsilon-Greedy), adaptive confidence-bound policies (Successive Elimination, Upper Confidence Bound/UCB1), Bayesian formulations (Thompson Sampling), and metric-space adaptations (fixed discretization and the adaptive "zooming" algorithm for continuum and Lipschitz bandits).
The article demonstrates several key findings. First, non-adaptive exploration is fundamentally limited, suffering an inferior worst-case regret rate of order T^(2/3) after T rounds. Second, adaptive strategies such as UCB1, Successive Elimination, and Thompson Sampling achieve a substantially improved, near-optimal worst-case regret of order square-root of (KT log T) across K discrete arms, alongside an instance-dependent logarithmic regret rate proportional to log(T). Third, information-theoretic lower bounds prove that no bandit algorithm can outperform order square-root of (KT) in the worst case or order log(T) on specific instances, confirming that adaptive methods reach the fundamental limits of learning. Finally, for continuous or large metric spaces obeying Lipschitz continuity, uniform discretization achieves an optimal worst-case regret of order T^((d+1)/(d+2)) (where d represents the covering dimension), while adaptive zooming algorithms further accelerate convergence by focusing exploration primarily on high-performing regions.
These insights demonstrate that operational systems must move away from rigid, static A/B testing or fixed exploration schedules in favor of adaptive algorithms that dynamically prune suboptimal choices. Implementing adaptive methods like UCB or Thompson Sampling directly reduces the risk, time, and revenue lost during active experimentation in large-scale commercial deployments.
Organizations deploying automated decision-making systems should adopt adaptive exploration policies tailored to their operational constraints. For standard catalog or ad-selection domains with discrete choices, Thompson Sampling and UCB-based policies provide theoretically sound and computationally viable implementations. When action spaces are large or continuous—such as in dynamic pricing or parameter tuning—practitioners should implement adaptive discretization or metric-aware bandit architectures to avoid the curse of dimensionality.
While the theoretical guarantees are strong and mathematically tight, decision-makers must note that standard stochastic bandit guarantees rely on stationary reward distributions and well-specified metric or prior assumptions. In dynamic, highly volatile, or strategic environments, models must be adapted to account for adversarial shifts, resource constraints, or non-stationary customer behavior.
- Paper: Finite-time Analysis of the Multiarmed Bandit Problem, Peter Auer et al. (2002). This foundational paper establishes the finite-time regret analysis of Upper Confidence Bound (UCB) algorithms for stochastic bandits that underpins the introductory chapters of the source book.
- Paper: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Sébastien Bubeck et al. (2012). This comprehensive survey provides the essential mathematical framework for stochastic, adversarial, and contextual bandit regret bounds that the source textbook synthesizes into pedagogical chapters.
- Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). This work introduces self-normalized martingale concentration and the OFUL algorithm, providing the core theoretical machinery used in the source's treatment of linear stochastic bandits.
- Paper: Using Confidence Bounds for Exploitation-Exploration Trade-offs, Peter Auer (2003). This seminal paper develops confidence-bound techniques for non-stationary adversarial bandits and linear contextual models that directly inform the structured bandit chapters in the book.
- Paper: A contextual-bandit approach to personalized news article recommendation, Lihong Li et al. (2010). This influential paper introduces the LinUCB algorithm for contextual bandits with linear payoff functions, which serves as a central algorithmic prototype for Chapter 8 of the book.
- Paper: An Empirical Evaluation of Thompson Sampling, Olivier Chapelle et al. (2011). This empirical study revived Bayesian Thompson Sampling for contextual and multi-armed bandits, offering essential intuition for the Bayesian bandit sections of the textbook.
- Paper: Best Arm Identification in Multi-Armed Bandits, Jean-Yves Audibert et al. (2010). This work establishes the fundamental complexity metrics and elimination strategies for pure exploration and best-arm identification discussed in the stochastic bandit literature.
- Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). This foundational paper introduces the multiplicative weights update and Hedge algorithm, which constitute the primary basis for the adversarial bandit and full-feedback chapters in the book.
- Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). This text details online convex optimization algorithms and regret bounds, providing theoretical tools directly adapted in the adversarial and structured bandit chapters.
- Paper: Counterfactual Risk Minimization: Learning from Logged Bandit Feedback, Adith Swaminathan et al. (2015). This work formulates batch learning from logged bandit feedback and counterfactual risk minimization, serving as a key reference point for offline evaluation in contextual bandit problems.
- Paper: Time-uniform, nonparametric, nonasymptotic confidence sequences, Steven R. Howard et al. (2021). This monograph extends the sequential concentration tools and confidence intervals used in bandit analysis into fully time-uniform, nonparametric confidence sequences for continuous experimentation.
- Paper: Reinforcement Learning: An Overview, Kevin P. Murphy (2024). This comprehensive overview generalizes the fundamental exploration-exploitation trade-offs learned in bandit settings to full Markov Decision Processes and modern deep reinforcement learning paradigms.
- Paper: A Tutorial Introduction to Reinforcement Learning, Mathukumalli Vidyasagar (2023). This tutorial builds upon the sequential decision principles of bandits by presenting the stochastic approximation theory needed to solve multi-state Markov decision processes.
