about
Introduction to Multi-Armed Bandits (arxiv.org)
3 points by Anon84 on May 6, 2019 | hide | past | pdf | discuss on HN

In plain words: A textbook introducing multi-armed bandits — algorithms that learn which choice pays off by trying options over time under uncertainty. Eleven self-contained chapters move from simple random rewards to adversarial settings and economics, with exercises and background appendices.

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; many of the chapters conclude with exercises. The book is structured as follows. The first four chapters are on IID rewards, from the basic model to impossibility results to Bayesian priors to Lipschitz rewards. The next three chapters cover adversarial rewards, from the full-feedback version to adversarial bandits to extensions with linear rewards and combinatorially structured actions. Chapter 8 is on contextual bandits, a middle ground between IID and adversarial bandits in which the change in reward distributions is completely explained by observable contexts. The last three chapters cover connections to economics, from learning in repeated games to bandits with supply/budget constraints to exploration in the presence of incentives. The appendix provides sufficient background on concentration and KL-divergence. The chapters on "bandits with similarity information", "bandits with knapsacks" and "bandits and agents" can also be consumed as standalone surveys on the respective topics.

Aleksandrs Slivkins
arXiv:1904.07272 · cs.LG, cs.AI, cs.DS, stat.ML · submitted Apr 15, 2019 · updated Apr 3, 2024
abstract · pdf · html · Published with Foundations and Trends(R) in Machine Learning, November 2019. The present version is a revision of the "Foundations and Trends" publication. It contains numerous edits for presentation and accuracy (based in part on readers' feedback), updated and expanded literature reviews, and some new exercises

add comment on HN
Also discussed: Sep 2025 (143 points, 33 comments) · Feb 2020 (2 points, 0 comments) · Dec 2019 (6 points, 0 comments) · Apr 2019 (4 points, 0 comments) · Apr 2019 (3 points, 0 comments)