Policy Gradient: Optimal Estimation, Convergence, and Generalization beyond Cumulative Rewards

on YouTube ↗45m

" summary

Shows that policy gradients obey a policy-gradient Bellman equation and uses a practical double fitted iteration (regression over Q and its gradient) to get a minimax‑optimal off‑policy estimator whose error is governed by a covariance term and a new F‑restricted chi‑squared divergence between batch and target occupancy. Extends to concave utilities via a Fenchel dual min‑max solved by stochastic primal‑dual methods, yields estimation errors independent of state dimension and sample complexity O(1/epsilon^2) (iteration O(1/epsilon)).

AI-written summary · about

" chapters (18)

1. 0:00Introduction
2. 1:55Open Questions
3. 6:52Policy Gradients Bellman Equation
4. 12:01Estimation Error Bound Analysis
5. 17:45General Objective Functions
6. 19:30General Utility Functions
7. 21:04Prior Examples
8. 22:55Cumulative Rewards
9. 28:16Multicolor sampling
10. 29:51Estimation error bound
11. 30:54Optimization problem
12. 31:40convex optimization problem
13. 33:46Further analysis
14. 34:38Analysis
15. 35:18Intuition
16. 36:01Estimation and Convergence
17. 37:56Summary
18. 40:02Questions

" related talks

• 35mOn the Global Convergence and Approximation Benefits of Policy Gradient MethodsDaniel Russo · Mathematics of Online Decision Making 2020
• 55mOptimality and Approximation with Policy Gradient Methods in Markov Decision ProcessesAlekh Agarwal · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 53mOff-policy Policy OptimizationDale Schuurmans · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 12mLearning In The Presence Of Strategic Agents: Dynamics, Equilibria, And ConvergenceEric Mazumdar · Meet the Fellows Welcome Event
• 44mBeyond Worst-Case: Instance-Dependent Optimality in Reinforcement LearningMartin Wainwright · Reinforcement Learning from Batch Data and Simulation
• 28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement LearningAngela Zhou · Algorithmic Aspects of Causal Inference 2022
• 28mGradient-Descent for Randomized Controllers under Partial ObservabilitySebastian Junges, Joost-Pieter Katoen, Jip Spel, Linus Heck, Joshua Moerman · VMCAI 2022
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity