Introduction to Multi-Armed Bandits

By Aleksandrs Slivkins. Found. Trends Mach. Learn., 2019

1,282 citations recorded by the source corpus.

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. The chapters are as follows: stochastic bandits, lower bounds; Bayesian bandits and Thompson Sampling; Lipschitz Bandits; full Feedback and adversarial costs; adversarial bandits; linear costs and semi-bandits; contextual Bandits; bandits and games; bandits with knapsacks; bandits and incentives.

View Paper: https://www.semanticscholar.org/paper/4c7730d6227f8b90735ba4de7864551cb8928d92

How researchers see this paper

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

Citations in the corpus

Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “This framework is a variant of the widely-studied multi-armed bandit (MAB) setting [Auer et al., 2002; Slivkins, 2019; Lattimore and Szepesvári, 2020], where rather than receive rewards, the learner obtains preference-based feedback information.”
Bandit Algorithms (2020, methodology): “For a good account on the history of contextual bandits see the article by Tewari and Murphy [2017]. The Exp4 algorithm was introduced by Auer et al.”
Theory of Mind and Preference Learning at the Interface of Cognitive Science, Neuroscience, and AI: A Review (2022, background): “…assume that humans’ preferences are ﬁxed, Chan et al. (2019) model humans as learning their preferences, using an assistive multi-armed bandit setting (Slivkins, 2019) in which humans repeatedly choose one of several arms of diﬀerent slot machines with unknown reward distributions to pull.”
Reinforcement Learning based Recommender Systems: A Survey (2021, background): “In particular, in bandits, similar to an RL problem, the agent should learn to maximize a numerical reward through interaction with the environment and solving the exploration vs exploitation dilemma [26, 27].”
Effective Diversity in Population-Based Reinforcement Learning (2020, background): “This provides us with a principled means to trade-off reward vs. diversity through the lens of multi-armed bandits (Slivkins, 2019).”