mlsanityData to 7 Oct 2026

Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies

arXiv 2302.01734 ↗First posted 3 Feb 2023cs.LG math.OCcited by 53

Not on the map. Why?

Abstract (arXiv)

Recently, the impressive empirical success of policy gradient (PG) methods has catalyzed the development of their theoretical foundations. Despite the huge efforts directed at the design of efficient stochastic PG-type algorithms, the understanding of their convergence to a globally optimal policy is still limited. In this work, we develop improved global convergence guarantees for a general class of Fisher-non-degenerate parameterized policies which allows to address the case of continuous state action spaces. First, we propose a Normalized Policy Gradient method with Implicit Gradient Transport (N-PG-IGT) and derive a tildeO(varepsilon-2.5) sample complexity of this method for finding a global varepsilon-optimal policy. Improving over the previously known tildeO(varepsilon-3) complexity, this algorithm does not require the use of importance sampling or second-order information and samples only one trajectory per iteration. Second, we further improve this complexity to tilde mathcalO (varepsilon-2) by considering a Hessian-Aided Recursive Policy Gradient ((N)-HARPG) algorithm enhanced with a correction based on a Hessian-vector product. Interestingly, both algorithms are (i) simple and easy to implement: single-loop, do not require large batches of trajectories and sample at most two trajectories per iteration; (ii) computationally and memory efficient: they do not require expensive subroutines at each iteration and can be implemented with memory linear in the dimension of parameters.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). Builds on 50 of its 80 references that are in the map. First posted on arXiv 3 Feb 2023.

Builds on

50 of 80 references.

References · 50

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  6. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  7. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  8. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  9. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  10. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  11. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  12. 2020Momentum Improves Normalized SGDcited by 136
38 more
  1. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  2. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  3. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  4. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  5. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  6. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  7. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 85
  8. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  9. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 75
  10. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  11. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  12. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  13. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  14. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  15. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  16. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  17. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  18. 2016Stochastic Heavy Ballcited by 40
  19. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 39
  20. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  21. 2020Momentum-Based Policy Gradient Methodscited by 28
  22. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  23. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  24. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 22
  25. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  26. 2020Optimizing Static Linear Feedback: Gradient Methodcited by 19
  27. 2022Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequalitycited by 19
  28. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  29. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 17
  30. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  31. 2020Sample Complexity of Policy Gradient Finding Second-Order Stationary Pointscited by 16
  32. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 15
  33. 2021Better SGD using Second-order Momentumcited by 14
  34. 2019Reducing the variance in online optimization by transporting past gradientscited by 12
  35. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  36. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  37. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  38. 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settingscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 19; 2025: 13; 2026: 11.

53 papers.

Sort:

By area:

  1. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  2. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited 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. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  5. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  6. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  7. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  8. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  9. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  10. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  11. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  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. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  5. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  6. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  7. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 7
  8. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 7
  9. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  10. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  11. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  12. 2023Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulatorscited by 4
  13. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  14. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  15. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
  16. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  17. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  18. 2023On the Linear Convergence of Policy Gradient under Hadamard Parameterizationcited by 2
  19. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  20. 2025Non-Asymptotic Global Convergence of PPO-Clipcited by 2
  21. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  22. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
  23. 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimizationcited by 1
  24. 2025Reusing Trajectories in Policy Gradients Enables Fast Convergencecited by 1
  25. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  26. 2025A Communication-Efficient Decentralized Actor-Critic Algorithmcited by 1
  27. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  28. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  29. 2026Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradientscited by 1
  30. 2026Refined Analysis of Entropy-Regularized Actor-Criticcited by 1
  31. 2024Highway Graph to Accelerate Reinforcement Learningcited by 0
  32. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  33. 2025Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learningcited by 0
  34. 2025Predictive Spike Timing Enables Distributed Shortest Path Computation in Spiking Neural Networkscited by 0
  35. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Rewardcited by 0
  36. 2025Improved Convergence in Parameter-Agnostic Error Feedback through Momentumcited by 0
  37. 2026How Log-Barrier Helps Exploration in Policy Optimizationcited by 0
  38. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0

50 most cited of 53 All 53 (JSON)