Introduction to Multi-Armed Bandits

Multi-armed bandits is a rich, multi-disciplinary area that has been studied since 1933, with a surge of activity in the past 10-15 years. This is the first monograph to provide a textbook like treatment of the subject. The work on multi-armed bandits can be partitioned into a dozen or so directions. Each chapter tackles one line of work, providing a self-contained introduction and pointers for further reading. Introduction to Multi-Armed Bandits concentrates on fundamental ideas and elementary, teachable proofs over the strongest possible results. It emphasizes accessibility of the material; while exposure to machine learning and probability/statistics would certainly help, a standard undergraduate course on algorithms should suffice for background. The first four chapters are devoted IID rewards with adversarial rewards being covered in the next 3 chapters. Contextual bandits are discussed in a separate chapter before the monograph concludes with connections to economics. Each chapter contains a section on bibliographic notes and further directions. Many of the chapters conclude with some exercises. Introduction to Multi-Armed Bandits provides an accessible treatment for students of a topic that has gained importance in the last decade. Lecturers can use it as a text for an introductory course on the subject.