On the Complexity of Learning Good Policies With and Without Rewards

on YouTube ↗31m

" summary

Proposes a model-based UCB algorithm called RF-UCRL that estimates transitions from visit counts and drives exploration by maximizing a data-dependent upper bound on Q-value error, proving it is PAC for reward-free exploration with sample complexity O(H^4 S A / ε^2 log(1/δ)) summarized as H^4 S A / ε^2 log(1/δ), shows a matching lower bound for best-policy identification of order H^3, demonstrates an empirical order-of-magnitude speedup on a double-chain benchmark.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:50Many RL problems
3. 3:22Setting: Episodic Markov Decision Process
4. 6:19Online episodic algorithm
5. 9:42Reward-Free Exploration (RFE)
6. 13:37Reward-Free UCRL
7. 16:57Proof
8. 18:14The algorithm
9. 19:33Theoretical guarantees
10. 21:27Outline
11. 23:32Building on Regret Minimizing algorithm
12. 25:34An alternative: BPI-UCRL
13. 26:45Sample complexity of BPI-UCRL
14. 27:07RF-UCRL versus BPI-UCRL
15. 27:43Summary
16. 30:01References

" related talks

• 56mA Tutorial on Reinforcement Learning IIEmma Brunskill · Foundations of Machine Learning Boot Camp 2017
• 28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement LearningAngela Zhou · Algorithmic Aspects of Causal Inference 2022
• 01h 01mA Tutorial on Reinforcement Learning IEmma Brunskill · Foundations of Machine Learning Boot Camp 2017
• 53mOff-policy Policy OptimizationDale Schuurmans · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 31mStable Reinforcement Learning with Unbounded State SpaceQiaomin Xie · Reinforcement Learning from Batch Data and Simulation
• 48mPractical Model-based Algorithms for Reinforcement Learning and Imitation Learning, with...Tengyu Ma · Frontiers of Deep Learning 2019
• 31mLearning to Control Unknown SystemsRahul Jain · Societal Networks 2018
• 01h 05mFoundations of RLRayadurgam Srikant · Data-Driven Decision Processes Boot Camp 2022