When Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?
summary
Linear function approximation can be query‑efficient only under tight structural assumptions: with TensorPlan (a variant of optimistic constraint propagation) and V-realizability, constant action MDPs with local simulator resets yield polynomial sample complexity; with global access and both V and Q realizability one can also get polynomial queries but not polynomial computation. Hard lower bounds show a necessary sqrt(d) blowup* of uniform approximation error and that exponentially many actions (in min(d,H)) break feasibility, so most general cases are negative.
AI-written summary · about
chapters (12)
- 0:00Start
- 11:27MDPs and Bellman equations
- 14:43Optimistic Constraint Propagation Deterministic MDPs
- 19:34Sample Complexity
- 19:478 years later..
- 25:24Strong Weak function approximation
- 29:22Many actions
- 33:11Simulator access models
- 35:20Few actions
- 44:16What's the role of optimism?
- 46:39Summary
- 49:41Some open problems
related talks
55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
54mOn the Hardness of Reinforcement Learning With Value-function Approximation
52mThe Simplex and Policy-Iteration Methods are Strongly Polynomial...
48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from Samples
01h 17mRobust Optimization and Generalization
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
31mLearning to Control Unknown Systems
34mPandora's Box with Correlations: Learning and Approximation