Bandit Algorithms

Decision-making in the face of uncertainty is a significant challenge in machine learning, and the multi-armed bandit model is a commonly used framework to address it. This comprehensive and rigorous introduction to the multi-armed bandit problem examines all the major settings, including stochastic, adversarial, and Bayesian frameworks. A focus on both mathematical intuition and carefully worked proofs makes this an excellent reference for established researchers and a helpful resource for graduate students in computer science, engineering, statistics, applied mathematics and economics. Linear bandits receive special attention as one of the most useful models in applications, while other chapters are dedicated to combinatorial bandits, ranking, non-stationary problems, Thompson sampling and pure exploration. The book ends with a peek into the world beyond bandits with an introduction to partial monitoring and learning in Markov decision processes.

Review

‘This year marks the 68th anniversary of ‘multi-armed bandits’ introduced by Herbert Robbins in 1952, and the 35th anniversary of his 1985 paper with me that advanced multi-armed bandit theory in new directions via the concept of ‘regret’ and a sharp asymptotic lower bound for the regret. This vibrant subject has attracted important multidisciplinary developments and applications. Bandit Algorithms gives it a comprehensive and up-to-date treatment, and meets the need for such books in instruction and research in the subject, as in a new course on contextual bandits and recommendation technology that I am developing at Stanford.’ Tze L. Lai, Stanford University

‘This is a timely book on the theory of multi-armed bandits, covering a very broad range of basic and advanced topics. The rigorous treatment combined with intuition makes it an ideal resource for anyone interested in the mathematical and algorithmic foundations of a fascinating and rapidly growing field of research.’ Nicolò Cesa-Bianchi, University of Milan

‘The field of bandit algorithms, in its modern form, and driven by prominent new applications, has been taking off in multiple directions. The book by Lattimore and Szepesvári is a timely contribution that will become a standard reference on the subject. The book offers a thorough exposition of an enormous amount of material, neatly organized in digestible pieces. It is mathematically rigorous, but also pleasant to read, rich in intuition and historical notes, and without superfluous details. Highly recommended.’ John Tsitsiklis, Massachusetts Institute of Technology

Table of Contents

Part I Bandits, Probability and Concentration

1 Introduction

2 Foundations of Probability

3 Stochastic Processes and Markov Chains

4 Stochastic Bandits

5 Concentration of Measure

Part II Stochastic Bandits with Finitely Many Arms

6 The Explore-Then-Commit Algorithm

7 The Upper Confidence Bound Algorithm

8 The Upper Confidence Bound Algorithm: Asymptotic Optimality

9 The Upper Confidence Bound Algorithm: Minimax Optimality

10 The Upper Confidence Bound Algorithm: Bernoulli Noise

Part Ill Adversarial Bandits with Finitely Many Arms

11 The Exp3 Algorithm

12 The Exp3-IX Algorithm

Part IV Lower Bounds for Bandits with Finitely Many Arms

13 Lower Bounds: Basic Ideas

14 Foundations of Information Theory

15 Minimax Lower Bounds

16 Instance-Dependent Lower Bounds

17 High-Probability Lower Bounds

Part V Contextual and Linear Bandits

18 Contextual Bandits

19 Stochastic Linear Bandits

20 Confidence Bounds for Least Squares Estimators

21 Optimal Design for Least Squares Estimators

22 Stochastic Linear Bandits with Finitely Many Arms

23 Stochastic Linear Bandits with Sparsity

24 Minimax Lower Bounds for Stochastic Linear Bandits

25 Asymptotic Lower Bounds for Stochastic Linear Bandits

Part VI Adversarial Linear Bandits

26 Foundations of Convex Analysis

27 Exp3 for Adversarial Linear Bandits

28 Follow-the-regularised-Leader and Mirror Descent

29 The Relation between Adversarial and Stochastic Linear Bandits

Part VII Other Topics

30 Combinatorial Bandits

31 Non-stationary Bandits

32 Ranking

33 Pure Exploration

34 Foundations of Bayesian Learning

35 Bayesian Bandits

36 Thompson Sampling

Part VIII Beyond Bandits

37 Partial Monitoring

38 Markov Decision Processes

Book Description

A comprehensive and rigorous introduction for graduate students and researchers, with applications in sequential decision-making problems.

About the Authors

Tor Lattimore is a research scientist at DeepMind. His research is focused on decision making in the face of uncertainty, including bandit algorithms and reinforcement learning. Before joining DeepMind he was an assistant professor at Indiana University and a postdoctoral fellow at the University of Alberta.

Csaba Szepesvári is a Professor in the Department of Computing Science at the University of Alberta and a Principal Investigator of the Alberta Machine Intelligence Institute. He also leads the ‘Foundations’ team at DeepMind. He has co-authored a book on nonlinear approximate adaptive controllers and authored a book on reinforcement learning, in addition to publishing over 200 journal and conference papers. He is an action editor of the Journal of Machine Learning Research.