REVIEW 6 cited by
Introduction to Multi-Armed Bandits
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 6 Pith papers
-
Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
An explore-exploit algorithm achieves O(OPT^{2/3}) regret when combining multiple MTS heuristics with bandit access, and this is tight up to log factors.
-
Real-time adaptive quantum error correction by model-free multi-agent learning
Adaptive quantum error correction: multi-agent RL discovers QEC circuits offline; a bandit-controlled variational layer retrains online, cutting logical infidelity about 18x (qubit) and 3x (qutrit) under drifting bit/...
-
Optimism as a Vulnerability: Deceptive Stackelberg Control of UCB Bandit Followers
Under targetability and exploitability, a two-phase honeypot-then-trap leader strictly exceeds the classical SSE utility ceiling against a UCB follower at O(sqrt(T ln T)) signaling cost.
-
Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
Quantum algorithms for bandits with knapsacks achieve improved regret and time complexity by replacing classical sampling with quantum Monte Carlo and approximate quantum LP solving.
-
Test-Time Scaling of Diffusion Models via Noise Trajectory Search
An epsilon-greedy search over per-step noise trajectories improves proxy rewards in diffusion image generation without retraining.
-
Algorithmic Approaches to Sequential Decision-Making and Social Epistemology
For improving multi-armed bandits, randomized algorithms achieve a near-tight Θ~(√k) worst-case competitive ratio, and polynomially many historical instances suffice to tune a curvature parameter; pessimism traps and ...
Discussion (0). Sign in to comment.