What Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?

on YouTube ↗55m

" summary

Assumes linear Q realizability and spectral coverage and then proves an information-theoretic lower bound: any offline algorithm can require about D^{H/2} samples to evaluate a known policy. Construction uses a tiny deterministic MDP (roughly D·H states, two actions) where fitted-backup least-squares yields an exact equality that unfolds into a product-of-matrices and causes exponential variance, verified by experiments. Avoids blowup only under stronger conditions like policy completeness or very small distribution shift; confidence intervals merely detect failure.

AI-written summary · about

" chapters (26)

1. 0:00Intro
2. 1:20What is offline reinforcement learning
3. 2:48Intuition
4. 4:07Realizability
5. 6:00Sequential Decision Making
6. 6:57Standard Approach
7. 7:48Coverage
8. 9:22Limits
9. 9:50Policy Evaluation
10. 11:15Setting
11. 12:17Feature Mapping
12. 15:31Upper Limits
13. 17:53Lower Limits
14. 19:16Observations
15. 22:50Upper Bounds
16. 24:43Inequality
17. 27:30Simulation
18. 29:22Summary
19. 32:05Sufficient Conditions
20. 34:06Possible Results
21. 38:30Intuition and Construction
22. 42:59Practical Considerations
23. 45:39Follow Up
24. 47:08Experiments
25. 49:26Other Experiments
26. 51:15Model vs Feature

" related talks

• 54mOn the Hardness of Reinforcement Learning With Value-function ApproximationNan Jiang · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 34mUniform Offline Policy Evaluation (OPE) and Offline Learning in Tabular RLYu-Xiang Wang · Reinforcement Learning from Batch Data and Simulation
• 48mOffline Reinforcement Learning With Only RealizabilityJason Lee · Adversarial Approaches in Machine Learning 2022
• 52mWhen Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?Csaba Szepesvári · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 54mGeneralization and Robustness in Offline Reinforcement LearningWen Sun · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 35mOnline Learning with A Lot of Batch DataShie Mannor · Reinforcement Learning from Batch Data and Simulation
• 11mLinear Predictors in Reinforcement Learning: ...Andrea Zanette · Meet the Fellows Welcome Event
• 31mLearning to Control Unknown SystemsRahul Jain · Societal Networks 2018