Bandit Algorithms

id: 639168 not VIP Open in MaM

By Csaba Szepesvari, Tor Lattimore

Language: English

Category: Ebook - Computer/Internet

Categories: Computer/Internet

Size: 13 MiB pdf Files: 1

Uploader: draino

Uploaded At: 2020-07-10 01:24:19

Cambridge University Press; 2020, Bandit Algorithms, Computer Algorithms, Pattern Recognition and Machine Learning, Control Systems and Optimisation

Description


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.


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 III - 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

Other Torrents