Introduction to multi-armed bandits
From MaRDI portal
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to probability theory (60-01) Stopping times; optimal stopping problems; gambling theory (60G40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Multistage and repeated games (91A20) Rationality and learning in game theory (91A26) Probabilistic games; gambling (91A60)
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.
Recommendations
Cited in
(59)- Which one should I imitate?
- Bayesian adversarial multi-node bandit for optimal smart grid protection against cyber attacks
- Multi-armed bandit with sub-exponential rewards
- Multi-round cooperative search games with multiple players
- Ballooning multi-armed bandits
- Maximizing revenue for publishers using header bidding and ad exchange auctions
- Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models
- Quantum greedy algorithms for multi-armed bandits
- Online learning methods for networking
- Reinforcement Learning Based Interactive Agent for Personalized Mathematical Skill Enhancement
- Dynamic learning and market making in spread betting markets with informed bettors
- Bayesian exploration: incentivizing exploration in Bayesian games
- Multiplayer Bandits Without Observing Collision Information
- Online resource allocation with personalized learning
- Bandit algorithms
- Achieving fairness in the stochastic multi-armed bandit problem
- Multi-Armed Bandits: Theory and Applications to Online Learning in Networks
- Learning in repeated auctions
- Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability
- Optimal activation of halting multi‐armed bandit models
- Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems
- Online learning of network bottlenecks via minimax paths
- Multi-armed bandits with censored consumption of resources
- A central limit theorem, loss aversion and multi-armed bandits
- Convergence rate analysis for optimal computing budget allocation algorithms
- Semi-Supervised Node Classification via Semi-Global Graph Transformer Based on Homogeneity Augmentation
- Universal regression with adversarial responses
- Control-data separation and logical condition propagation for efficient inference on probabilistic programs
- Efficient and generalizable tuning strategies for stochastic gradient MCMC
- Improving Hoeffding's inequality using higher moments information
- A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees
- Understanding the stochastic dynamics of sequential decision-making processes: a path-integral analysis of multi-armed bandits
- Adversarial bandits with knapsacks
- A natural adaptive process for collective decision-making
- Thompson sampling for networked control over unknown channels
- Tracking the mean of a piecewise stationary sequence
- Certified multifidelity zeroth-order optimization
- Risk preferences of learning algorithms
- An \(\alpha \)-regret analysis of adversarial bilateral trade
- Integrating multi-armed bandit with local search for MaxSAT
- Tracking the mean of a piecewise stationary sequence
- Near-linear MIR algorithms for stochastically-ordered priors
- Adaptive maximization of social welfare
- Adaptive smooth nonstationary bandits
- Two-armed bandit bootstrap for model-free equivalent rank test
- Multi-armed bandit for the cyclic minimum sitting arrangement problem
- Online order acceptance and scheduling in a single machine environment
- Complexity analysis of a countable-armed bandit problem
- Thompson sampling for adversarial bit prediction
- Addressing maximization bias in reinforcement learning with two-sample testing
- Efficient and optimal algorithms for contextual dueling bandits under realizability
- Scale-free adversarial multi armed bandits
- Multivariate tie-breaker designs
- Weak aggregating algorithm for prediction with expert advice and adversarial bandit frameworks
- Quantum spatial best-arm identification on a complete bipartite graph
- A review of causal decision making
- Managing persuasion robustly: the optimality of quota rules
- The role of transparency in repeated first-price auctions with unknown valuations
- Multi-armed bandits with episode context
This page was built for publication: Introduction to multi-armed bandits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5213200)
