Introduction to Multi-Armed Bandits

Abstract

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.