mlsanityData to 7 Oct 2026

An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods

arXiv 2211.07937 ↗First posted 15 Nov 2022cs.LGcited by 63

Not on the map. Why?

Abstract (arXiv)

In this paper, we revisit and improve the convergence of policy gradient (PG), natural PG (NPG) methods, and their variance-reduced variants, under general smooth policy parametrizations. More specifically, with the Fisher information matrix of the policy being positive definite: i) we show that a state-of-the-art variance-reduced PG method, which has only been shown to converge to stationary points, converges to the globally optimal value up to some inherent function approximation error due to policy parametrization; ii) we show that NPG enjoys a lower sample complexity; iii) we propose SRVR-NPG, which incorporates variance-reduction into the NPG update. Our improvements follow from an observation that the convergence of (variance-reduced) PG and NPG methods can improve each other: the stationary convergence analysis of PG can be applied to NPG as well, and the global convergence analysis of NPG can help to establish the global convergence of (variance-reduced) PG methods. Our analysis carefully integrates the advantages of these two lines of works. Thanks to this improvement, we have also made variance-reduction for NPG possible, with both global convergence and an efficient finite-sample complexity.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). Builds on 33 of its 62 references that are in the map. First posted on arXiv 15 Nov 2022.

Builds on

33 of 62 references.

References · 33

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2015Continuous control with deep reinforcement learningcited by 3,279
  4. 2015Trust Region Policy Optimizationcited by 2,503
  5. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  6. 2014New insights and perspectives on the natural gradient methodcited by 435
  7. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  8. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  11. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  12. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
21 more
  1. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  2. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  3. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  4. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  6. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  7. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  8. 2014A Stochastic Quasi-Newton Method for Large-Scale Optimizationcited by 68
  9. 2018Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselinescited by 65
  10. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  11. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  12. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  13. 2015A Linearly-Convergent Stochastic L-BFGS Algorithmcited by 39
  14. 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
  15. 2020Momentum-Based Policy Gradient Methodscited by 28
  16. 2016Stochastic Block BFGS: Squeezing More Curvature out of Datacited by 24
  17. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 22
  18. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 17
  19. 2020Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithmscited by 14
  20. 2017Stochastic Variance Reduction for Policy Gradient Estimationcited by 6
  21. 2019Acceleration of SVRG and Katyusha X by Inexact Preconditioningcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 20; 2024: 18; 2025: 12; 2026: 12.

63 papers.

Sort:

By area:

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  2. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  3. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  4. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  5. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  6. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 20
  7. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  8. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  9. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  10. 2023PPO-Clip Attains Global Optimality: Towards Deeper Understandings of Clippingcited by 17
  11. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  12. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
38 more
  1. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  2. 2023A safe exploration approach to constrained Markov decision processescited by 10
  3. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 10
  4. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  5. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  6. 2023Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global Statecited by 8
  7. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  8. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  9. 2024Recurrent Natural Policy Gradient for POMDPscited by 8
  10. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  11. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 7
  12. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  13. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
  14. 2024Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradientcited by 6
  15. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  16. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  17. 2023On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrizationcited by 5
  18. 2023Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulatorscited by 4
  19. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  20. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  21. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  22. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  23. 2023Policy Gradient with Tree Expansioncited by 3
  24. 2023Accelerating Large Batch Training via Gradient Signal to Noise Ratio (GSNR)cited by 3
  25. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  26. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  27. 2023Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learningcited by 2
  28. 2024A learning-based approach to stochastic optimal control under reach-avoid constraintcited by 2
  29. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  30. 2025Non-Asymptotic Global Convergence of PPO-Clipcited by 2
  31. 2026Rank-1 Approximation of Inverse Fisher for Natural Policy Gradients in Deep Reinforcement Learningcited by 2
  32. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
  33. 2022Coordinate Ascent for Off-Policy RL with Global Convergence Guaranteescited by 1
  34. 2023Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approachcited by 1
  35. 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimizationcited by 1
  36. 2024Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularizationcited by 1
  37. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  38. 2026Post-Training with Policy Gradients: Optimality and the Base Model Barriercited by 1

50 most cited of 63 All 63 (JSON)