Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

By Sébastien Bubeck, Nicolò Cesa-Bianchi. 2012

1,783 citations recorded by the source corpus.

A multi-armed bandit problem - or, simply, a bandit problem - is a sequential allocation problem defined by a set of actions. At each time step, a unit resource is allocated to an action and some observable payoff is obtained. The goal is to maximize the total payoff obtained in a sequence of allocations. The name bandit refers to the colloquial term for a slot machine (a "one-armed bandit" in American slang). In a casino, a sequential allocation problem is obtained when the player is facing many slot machines at once (a "multi-armed bandit"), and must repeatedly choose where to insert the next coin. Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the 1930s, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this book, the focus is on two extreme cases in which the analysis of regret is particularly simple and elegant: independent and identically distributed payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, it also analyzes some of the most important variants and extensions, such as the contextual bandit model. This monograph is an ideal reference for students and researchers with an interest in bandit problems.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning (2016, background): “Maximizing this objective is equivalent to minimizing the cumulative pseudo-regret (Bubeck & Cesa-Bianchi, 2012).”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, background): “There are near-optimal algorithms for multi-armed bandits (Bubeck and Cesa-Bianchi, 2012); the hardness of exploration in Markov Decision Processes (MDPs) is well-understood (Jaksch et al., 2010; Lattimore and Hutter, 2012).”
Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “The pure-exploration multi-armed bandit problem has a long history in the stochastic setting (Bubeck and Cesa-Bianchi, 2012; Even-Dar et al., 2006), and was recently extended to the non-stochastic setting by Jamieson and Talwalkar (2015).”
Balanced Policy Evaluation and Learning (2017, neutral): “Moreover, if ⇡⇤ is such that ⇡⇤ t (x) > 0 () t 2 argmins2[m] μs(x), then b R(⇡) = SAPE(⇡) SAPE(⇡⇤) is the regret of ⇡ [8].”
Automated Curriculum Learning for Neural Networks (2017, methodology): “We view a curriculum containing N tasks as an N -armed bandit (Bubeck and Cesa-Bianchi, 2012), and a syllabus as an adaptive policy which seeks to maximize payoffs from this bandit.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “Many algorithms exist that achieve low regret for bandits, see the survey [19], in particular the MOSS algorithm is known to achieve the optimal regret lower bound, up to constants, [5].”
Fairness in Learning: Classic and Contextual Bandits (2016, background): “fairness) if one does not make data-specific assumptions on an instance [9] It would be possible to state a logarithmic dependence on T in our setting as well while making assumptions on the gaps between arms, but since our fairness constraint manifests itself as a cost that depends on k, we choose ”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, background): “See (Bubeck & Cesa-Bianchi, 2012) for more info.”
Introduction to Online Convex Optimization (2016, background): “The Multi-Armed Bandit problem has history going back more than fifty years to the work of Robbins (90), see the survey of (25) for a much more detailed history.”
Learning to Optimize via Posterior Sampling (2013, background): “Bubeck and Cesa-Bianchi [11] provide a review of work on UCB algorithms and on adversarial bandits.”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “Decoupled meta-solvers are essentially sample-based adversarial bandits [16] applied to games.”
A Study on Overfitting in Deep Reinforcement Learning (2018, methodology): “Algorithms and regret analysis for stochastic (Auer et al., 2002) and adversarial bandits (Auer, 2000; Bubeck & Cesa-Bianchi, 2012), for contextual bandits (Agarwal et al., 2014), contextual decision processes (Jiang et al., 2017) and RL (Jaksch et al., 2010; Azar et al., 2017), as well as Probably…”
Fair Algorithms for Infinite and Contextual Bandits (2016, background): “multi-armed bandit setting (i.e. in the special case in which contexts are unchanging between rounds). A lower bound of R(T) = ( p T) is also known for this setting, even absent a fairness constraint [7]. Since that simpler setting is a special case of the contextual bandit framework, it follows tha”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “Perhaps the most well-known case is the multi-armed bandits problem with many other variants being developed, such as contextual bandits, combinatorial bandits, and more general models such as partial monitoring [10, 11].”