On the Hardness of Reinforcement Learning With Value-function Approximation
summary
Asserts that having a realizable value-function class plus exploratory batch data is not enough for sample-efficient RL: a constructed MDP family yields a lower bound that is exponential in the horizon despite |F| being small, and a simple FQI-style bootstrap example shows errors can blow up via adversarial tie-breaking so realizability alone insufficient. Requires both a coverage parameter C (density ratio) and stronger representation conditions; examples that work include low-rank MDPs and deterministic MDPs where Bellman-error minimization succeeds.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:39Reinforcement Learning (RL) Applications
- 2:01Value-function Approximation
- 4:30Comparison between SL and RL
- 9:38Markov Decision Process (MDP)
- 16:02Batch learning in MDPS
- 19:27Example: Video game playing
- 20:29Batch learning in large MDPS
- 32:01Assumption on data (?)
- 33:24Assumption on data & MDP dynamics
- 38:20Algorithm for batch RL
- 42:07How things go wrong (w/ restricted class)
- 46:13Fix using a strong assumption ("completeness")
- 46:44Realizability alone is insufficient?
- 47:11Proving the conjecture: Attempt 1
- 48:44Checklist for a plausible construction
- 49:00Importance of the conjecture
- 51:30Importance of the construction
related talks
55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
11mLinear Predictors in Reinforcement Learning: ...
31mBatch Value-function Approximation with Only Realizability
48mOffline Reinforcement Learning With Only Realizability
52mWhen Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?
01h 05mFoundations of RL
54mGeneralization and Robustness in Offline Reinforcement Learning
36mModel-Based Reinforcement Learning with Value-Targeted Regression