mlsanityData to 7 Oct 2026

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift

arXiv 1908.00261 ↗First posted 1 Aug 2019cs.LG stat.MLcited by 174

Not on the map. Why?

Abstract (arXiv)

Policy gradient methods are among the most effective methods in challenging reinforcement learning problems with large state and/or action spaces. However, little is known about even their most basic theoretical convergence properties, including: if and how fast they converge to a globally optimal solution or how they cope with approximation error due to using a restricted class of parametric policies. This work provides provable characterizations of the computational, approximation, and sample size properties of policy gradient methods in the context of discounted Markov Decision Processes (MDPs). We focus on both: "tabular" policy parameterizations, where the optimal policy is contained in the class and where we show global convergence to the optimal policy; and parametric policy classes (considering both log-linear and neural policy classes), which may not contain the optimal policy and where we provide agnostic learning results. One central contribution of this work is in providing approximation guarantees that are average case -- which avoid explicit worst-case dependencies on the size of state space -- by making a formal connection to supervised learning under distribution shift. This characterization shows an important interplay between estimation error, approximation error, and exploration (as characterized through a precisely defined condition number).

Key facts. Cited by 174 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Aug 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 5; 2021: 57; 2022: 34; 2023: 35; 2024: 22; 2025: 14; 2026: 7.

174 papers.

Sort:

By area:

  1. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,406
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2023ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Modelscited by 184
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  5. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  7. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  8. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  9. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  10. 2021Reward is enough for convex MDPscited by 82
  11. 2020Provably Good Batch Reinforcement Learning Without Great Explorationcited by 77
  12. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
38 more
  1. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  2. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  3. 2023Learning to Generate Better Than Your LLMcited by 49
  4. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  5. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  6. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  7. 2021Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challengescited by 40
  8. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  9. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  10. 2021State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewardscited by 37
  11. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  12. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  13. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  14. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  15. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  16. 2021On-Policy Deep Reinforcement Learning for the Average-Reward Criterioncited by 29
  17. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  18. 2021Online Apprenticeship Learningcited by 28
  19. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  20. 2021Multi-Agent Reinforcement Learning with Temporal Logic Specificationscited by 27
  21. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  22. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  23. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  24. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  25. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  26. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparisoncited by 22
  27. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  28. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  29. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  30. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 20
  31. 2022Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regimecited by 20
  32. 2024SAIL: Self-Improving Efficient Online Alignment of Large Language Modelscited by 20
  33. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  34. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  35. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  36. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  37. 2021Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimizationcited by 18
  38. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18

50 most cited of 174 All 174 (JSON)