Multi-Armed Bandits: Theory and Applications to Online Learning in Networks

Description

Multi-armed bandit problems pertain to optimal sequential decision making and learning in unknown environments. Since the first bandit problem posed by Thompson in 1933 for the application of clinical trials, bandit problems have enjoyed lasting attention from multiple research communities and have found a wide range of applications across diverse domains. This book covers classic results and recent development on both Bayesian and frequentist bandit problems. We start in Chapter 1 with a brief overview on the history of bandit problems, contrasting the two schools—Bayesian and frequentis —of approaches and highlighting foundational results and key applications. Chapters 2 and 4 cover, respectively, the canonical Bayesian and frequentist bandit models. In Chapters 3 and 5, we discuss major variants of the canonical bandit models that lead to new directions, bring in new techniques, and broaden the applications of this classical problem. In Chapter 6, we present several representative application examples in communication networks and social-economic systems, aiming to illuminate the connections between the Bayesian and the frequentist formulations of bandit problems and how structural results pertaining to one may be leveraged to obtain solutions under the other. Preface Acknowledgments Introduction Multi-Armed Bandit Problems An Essential Conflict: Exploration vs. Exploitation Two Formulations: Bayesian and Frequentist The Bayesian Framework The Frequentist Framework Notation Bayesian Bandit Model and Gittins Index Markov Decision Processes Policy and the Value of a Policy Optimality Equation and Dynamic Programming The Bayesian Bandit Model Gittins Index Gittins Index and Forward Induction Interpretations of Gittins Index The Index Process, Lower Envelop, and Monotonicity of the Stopping Sets Optimality of the Gittins Index Policy Computing Gittins Index Offline Computation Online Computation Semi-Markov Bandit Processes Variants of the Bayesian Bandit Model Necessary Assumptions for the Index Theorem Modeling Assumptions on the Action Space Modeling Assumptions on the System Dynamics Modeling Assumptions on the Reward Structure Modeling Assumptions on the Performance Measure Variations in the Action Space Multitasking: The Bandit Superprocess Model Bandits with Precedence Constraints Open Bandit Processes Variations in the System Dynamics The Restless Bandit Model Indexability and Whittle Index Optimality of Whittle Index Policy Computational Approaches to Restless Bandits Variations in the Reward Structure Bandits with Rewards under Passivity Bandits with Switching Cost and Switching Delay Variations in Performance Measure Stochastic Shortest Path Bandit Average-Reward and Sensitive-Discount Criteria Finite-Horizon Criterion: Bandits with Deadlines Frequentist Bandit Model Basic Formulations and Regret Measures Uniform Dominance vs. Minimax Problem-Specific Regret and Worst-Case Regret Reward Distribution Families and Admissible Policy Classes Lower Bounds on Regret The Problem-Specific Regret The Minimax Regret Online Learning Algorithms Asymptotically Optimal Policies Order-Optimal Policies Connections between Bayesian and Frequentist Bandit Models Frequentist Approaches to Bayesian Bandits Bayesian Approaches to Frequentist Bandits Variants of the Frequentist Bandit Model Variations in the Reward Model Rested Markov Reward Processes Restless Markov Reward Processes Nonstationary Reward Processes Nonstochastic Reward Processes: Adversarial Bandits Variations in the Action Space Large-Scale Bandits with Structured Action Space Constrained Action Space Variations in the Observation Model Full-Information Feedback: The Expert Setting Graph-Structured Feedback: Bandits with Side Observations Constrained and Controlled Feedback: Label-Efficient Bandits Comparative Feedback: Dueling Bandits Variations in the Performance Measure Risk-Averse Bandits Pure-Exploration Bandits: Active Inference Learning in Context: Bandits with Side Information Learning under Competition: Bandits with Multiple Players Centralized Learning Distributed Learning Application Examples Communication and Computer Networks Dynamic Multichannel Access Adaptive Routing under Unknown Link States Heavy Hitter and Hierarchical Heavy Hitter Detection Social-Economic Networks Dynamic Pricing and the Pursuit of Complete Learning Web Search, Ads Display, and Recommendation Systems: Learning to Rank Bibliography Author's Biography Blank Page