Stochastic Bandits: Foundations and Current Perspectives

on YouTube ↗01h 01m

" summary

Covers algorithms and precise guarantees for stochastic bandits with feature vectors: a linear contextual model where contexts are seen before choice, are oblivious, and rewards equal x_t·μ plus sub-Gaussian noise with a common unknown μ. Extends UCB via a confidence-ball UCB (least‑squares estimator + B_t norm) to get regret ~Õ(d √T) independent of the number of arms, information-theoretic lower bound ~Ω(√(dT)), and a Thompson‑sampling variant with an extra √d factor; also addresses assortment optimization and vector rewards with convex objectives and budget/fairness constraints.

AI-written summary · about

" chapters (17)

1. 0:00Introduction to extensions
2. 2:04Contextual bandits concept
3. 3:44Linear bandit model
4. 6:18Linear bandit regret
5. 8:44UCB for linear bandits
6. 12:22Context assumptions
7. 15:24UCB algorithm details
8. 20:32Linear bandit analysis
9. 24:35Proof sketch
10. 30:56Information gain analysis
11. 35:32Technical Q&A
12. 40:49Thompson sampling
13. 44:33Further generalizations
14. 46:44Assortment optimization
15. 50:58Parametric model selection
16. 53:43Constraints and objectives
17. 1:00:12Conclusion and next steps

" related talks

• 46mDynamic Regret Minimization for Bandits without Prior KnowledgeChen-Yu Wei · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 48mAdaptivity and Confounding in Multi-armed Bandit ExperimentsDaniel Russo · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 30mFast Rates for Bandit Optimization with Upper-Confidence Frank-WolfeQuentin Berthet · Optimization, Statistics and Uncertainty
• 22mOnline Learning and Bandits with Queried HintsAditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala · ITCS 2023
• 27mOn the Complexity of Best Arm Identification in Multi-Armed Bandit ModelsAurélien Garivier · Information Theory, Learning and Big Data (Simons Institute, 2015)
• Bandits and Agents: How to Incentivize Exploration?Aleksandrs Slivkins · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 32mRevisiting the Exploration-Exploitation Trade-Off in Bandit ModelsEmilie Kaufmann · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 30mPractical Multi Armed BanditsBenjamin Bengfort · PyData Virginia 2025