Online Reinforcement Learning and Regret

on YouTube ↗01h 17m

" summary

Tutorial compares three interaction models (fully known, generative, and an online episodic model) and gives concrete algorithms and regret bounds: model-based optimistic planning with empirical transitions + bonus exploration achieves minimax √K regret (lower bound √K), with worse H and S,A dependence (practical time/storage HS^2A); model-free Q‑learning with a tailored learning rate gets √K regret but larger H dependence (H5/2 → H2 in follow-ups). Claims hinge on optimism, one‑step advantage decompositions, and Monte‑Carlo/importance sampling estimates; model-based wins empirically but costs compute.

AI-written summary · about

" chapters (10)

1. 0:00Introduction to RL models
2. 1:25Fully known model
3. 3:01Generative model setup
4. 5:06Online learning model
5. 11:07Finite horizon MDPs
6. 16:10Regret and performance
7. 23:18Comparing policies
8. 28:41Policy-based approaches
9. 47:45Value-based approaches
10. 1:05:06Research frontiers and wrap-up

" related talks

• 56mA Tutorial on Reinforcement Learning IIEmma Brunskill · Foundations of Machine Learning Boot Camp 2017
• 49mFast Rates for No-Regret Learning in General GamesNoah Golowich · Adversarial Approaches in Machine Learning 2022
• 35mJe ne regrette rien: Teaching Machine Learning Models Regret AvoidanceLaura Israel · PyData Amsterdam 2024
• 34mOffline Reinforcement Learning and Model-Based OptimizationSergey Levine · Reinforcement Learning from Batch Data and Simulation
• 42mA Regret Minimization Approach to Mutli-Agent Control and RLElad Hazan · Multi-Agent Reinforcement Learning and Bandit Learning
• 36mModel-Based Reinforcement Learning with Value-Targeted RegressionMengdi Wang · Mathematics of Online Decision Making 2020
• 46mDynamic Regret Minimization for Bandits without Prior KnowledgeChen-Yu Wei · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 31mRegret Minimization for Stochastic Shortest PathsYishay Mansour · Mathematics of Online Decision Making 2020