# Introduction to Multi-Armed Bandits

**Authors:** Aleksandrs Slivkins  
**arXiv:** [1904.07272](https://arxiv.org/abs/1904.07272)  
**Date:** 2019-04-15  
**Summary page:** https://www.summarizepaper.com/en/paper/1904.07272v1/

## Key points

- "Introduction to Multi-Armed Bandits" by Aleksandrs Slivkins is a comprehensive introduction to the framework of multi-armed bandits.
- The framework is used for algorithms that make decisions over time under uncertainty.
- The book covers several topics related to multi-armed bandits, with each chapter tackling a particular line of work.
- Chapter 1 covers stochastic bandits, which are the simplest form of multi-armed bandits where rewards are generated randomly according to some unknown probability distribution.
- Chapter 2 discusses lower bounds on the performance of any algorithm for multi-armed bandit problems.
- Chapter 3 delves into Bayesian Bandits and Thompson Sampling, which is a popular algorithm used for solving multi-armed bandit problems.
- Chapter 4 focuses on Lipschitz Bandits, which are a class of multi-armed bandit problems where rewards depend on some underlying metric space.
- Chapter 5 covers Full Feedback and Adversarial Costs, where feedback is given after every round but can be adversarial.
- Chapter 6 discusses Adversarial Bandits, where rewards can be chosen adversarially at every round.
- Chapter 7 deals with Linear Costs and Semi-bandits, which are extensions of traditional multi-armed bandit problems that allow for linear costs or partial feedback.
- Chapter 8 covers Contextual Bandits, which are another extension that allows for contextual information to be incorporated into decision-making.
- Chapter 9 explores the connection between Multi-Armed Bandits and Zero-Sum Games while chapter 10 focuses on Bandits with Knapsacks.
- Finally, the eleventh and last planned chapter will cover Incentivized Exploration and Connections to Mechanism Design when it is added in the coming months.
- The book provides readers with a self-contained technical introduction to each topic covered as well as a review of more advanced results making it an invaluable resource for anyone looking to learn about Multi Armed bandits from scratch or gain further insight into existing knowledge around this field.

## Summary

The book "Introduction to Multi-Armed Bandits" by Aleksandrs Slivkins provides a comprehensive introduction to the simple yet powerful framework of multi-armed bandits. This framework is used for algorithms that make decisions over time under uncertainty, and an enormous body of work has accumulated over the years, covered in several books and surveys. Slivkins' book offers a more introductory, textbook-like treatment of the subject, with each chapter tackling a particular line of work. The first chapter covers stochastic bandits, which are the simplest form of multi-armed bandits where rewards are generated randomly according to some unknown probability distribution. The second chapter discusses lower bounds on the performance of any algorithm for multi-armed bandit problems. The third chapter delves into Bayesian Bandits and Thompson Sampling, which is a popular algorithm used for solving multi-armed bandit problems. The fourth chapter focuses on Lipschitz Bandits, which are a class of multi-armed bandit problems where rewards depend on some underlying metric space. The fifth chapter covers Full Feedback and Adversarial Costs, where feedback is given after every round but can be adversarial. The sixth chapter discusses Adversarial Bandits, where rewards can be chosen adversarially at every round. The seventh chapter deals with Linear Costs and Semi-bandits, which are extensions of traditional multi-armed bandit problems that allow for linear costs or partial feedback. The eighth chapter covers Contextual Bandits, which are another extension that allows for contextual information to be incorporated into decision-making. The ninth chapter explores the connection between Multi-Armed Bandits and Zero-Sum Games while the tenth chapter focuses on Bandits with Knapsacks. Finally, the eleventh and last planned chapter will cover Incentivized Exploration and Connections to Mechanism Design when it is added in the coming months. Overall this book provides readers with a self-contained technical introduction to each topic covered as well as a review of more advanced results making it an invaluable resource for anyone looking to learn about Multi Armed bandits from scratch or gain further insight into existing knowledge around this field.