A Unifying View of Optimism in Episodic Reinforcement Learning

on YouTube ↗28m

" summary

Claim: the optimization solved by model‑optimistic RL (optimize p in a confidence set) is the Lagrangian dual of a value‑optimistic dynamic program, so every model‑optimistic algorithm has an equivalent value‑optimistic implementation that just runs backwards recursion with an added uncertainty bonus equal to the conjugate distance d . Proof uses occupancy‑measure LPs, reparameterization, Lagrangian duality and martingale concentration. Consequence: recover UCRL2’s √T regret via the bonus, extend to factored linear MDPs (recovers LSVI‑UCB/Eluder‑style bounds), but an extra √S gap in tabular dependence remains.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:47Episodic RL
3. 1:37Regret in Reinforcement Learning
4. 2:12Finding the optimal Policy - known MDP
5. 4:35Optimism in Bandits
6. 5:12Optimism in Reinforcement Learning
7. 7:37Main result
8. 10:12Corollaries
9. 11:31Framework
10. 14:17Summary
11. 15:22Examples
12. 17:39Factored Linear MDPS
13. 18:54Incorporating Uncertainty
14. 24:43Conclusions

" related talks

• 47mReinforcement Learning via an Optimization LensLihong Li · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 11mLinear Predictors in Reinforcement Learning: ...Andrea Zanette · Meet the Fellows Welcome Event
• 01h 17mOnline Reinforcement Learning and RegretSean Sinclair, Christina Lee Yu · Data-Driven Decision Processes Boot Camp 2022
• 34mOffline Reinforcement Learning and Model-Based OptimizationSergey Levine · Reinforcement Learning from Batch Data and Simulation
• 53mOff-policy Policy OptimizationDale Schuurmans · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty
• 44mBeyond Worst-Case: Instance-Dependent Optimality in Reinforcement LearningMartin Wainwright · Reinforcement Learning from Batch Data and Simulation
• 54mGeneralization and Robustness in Offline Reinforcement LearningWen Sun · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond