Stochastic Bandits: Foundations and Current Perspectives
summary
Covers concrete algorithms and guarantees: explains UCB (upper confidence bound) and Thompson Sampling, shows how UCB uses concentration bounds to get logarithmic instance-dependent regret (and how KL‑UCB tightens constants), and how Thompson uses beta/Gaussian posteriors to simulate Bayesian sampling while achieving comparable bounds. Gives the worst-case square-root regret scaling, discusses when priors or conjugate updates are practical, and notes Thompson’s empirical robustness and easier tuning versus carefully calibrated UCB variants.
AI-written summary · about
chapters (10)
- 0:00Welcome and introduction
- 2:04Introduction to multi-arm bandits
- 3:46Exploration vs. exploitation
- 6:34Problem formulation and regret
- 8:54Bayesian vs. frequentist models
- 14:01Algorithmic techniques
- 22:00UCB algorithm and proof
- 30:58Worst-case regret bounds
- 37:16Thompson sampling
- 48:39Theory and practical insights
related talks
48mAdaptivity and Confounding in Multi-armed Bandit Experiments
46mDynamic Regret Minimization for Bandits without Prior Knowledge
27mOn the Complexity of Best Arm Identification in Multi-Armed Bandit Models
30mFast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
41mKeynote: Personalization, Bandits, and Causal inference
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
29mPure Exploration Problems
Bandits and Agents: How to Incentivize Exploration?