Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Top Cited Papers
Open Access
- 12 December 2012
- journal article
- research article
- Published by Emerald Publishing in Foundations and Trends in Machine Learning
- Vol. 5 (1) , 1-122
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 payoffs 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.Keywords
All Related Versions
This publication has 60 references indexed in Scilit:
- Multi‐Armed Bandit Allocation Indices2011
- UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problemPeriodica Mathematica Hungarica, 2010
- Regret bounds for sleeping experts and banditsMachine Learning, 2010
- Learning Permutations with Exponential Weights2007
- The Shortest Path Problem Under Partial Monitoring2006
- Recursive Aggregation of Estimators by the Mirror Descent Algorithm with AveragingProblems of Information Transmission, 2005
- Arbitrary side observations in bandit problemsAdvances in Applied Mathematics, 2005
- Lower Bounds on the Sample Complexity of Exploration in the Multi-armed Bandit ProblemLecture Notes in Computer Science, 2003
- Path Kernels and Multiplicative UpdatesLecture Notes in Computer Science, 2002
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985