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

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