Foundations and Trends® in Machine Learning > Vol 5 > Issue 1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

By Sébastien Bubeck, Department of Operations Research and Financial Engineering, Princeton University, USA, sbubeck@princeton.edu | Nicolò Cesa-Bianchi, Dipartimento di Informatica, Università degli Studi di Milano, Italy, nicolo.cesa-bianchi@unimi.it

 
Suggested Citation
Sébastien Bubeck and Nicolò Cesa-Bianchi (2012), "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems", Foundations and Trends® in Machine Learning: Vol. 5: No. 1, pp 1-122. http://dx.doi.org/10.1561/2200000024

Publication Date: 12 Dec 2012
© 2012 S. Bubeck and N. Cesa-Bianchi
 
Subjects
Learning and statistical methods,  Game theoretic learning,  Online learning,  Optimization,  Reinforcement learning
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Stochastic Bandits: Fundamental Results 
3 Adversarial Bandits: Fundamental Results 
4 Contextual Bandits 
5 Linear Bandits 
6 Nonlinear Bandits 
7 Variants 
Acknowledgments 
References 

Abstract

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 monograph, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model.

DOI:10.1561/2200000024
ISBN: 978-1-60198-626-9
127 pp. $90.00
Buy book (pb)
 
ISBN: 978-1-60198-627-6
127 pp. $110.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: Stochastic bandits: fundamental results
3: Adversarial bandits: fundamental results
4: Contextual Bandits
5: Linear bandits
6: Nonlinear bandits
7: Variants
Acknowledgements
References

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

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.

 
MAL-024