mlsanityData to 7 Oct 2026

Sample Efficient Policy Gradient Methods with Recursive Variance Reduction

arXiv 1909.08610 ↗First posted 18 Sep 2019cs.LG math.OC stat.MLcited by 58

Not on the map. Why?

Abstract (arXiv)

Improving the sample efficiency in reinforcement learning has been a long-standing research problem. In this work, we aim to reduce the sample complexity of existing policy gradient methods. We propose a novel policy gradient algorithm called SRVR-PG, which only requires O(1/ε3/2) episodes to find an ε-approximate stationary point of the nonconcave performance function J(boldsymbolθ) (i.e., boldsymbolθ such that |nabla J(boldsymbolθ)|22≤ε). This sample complexity improves the existing result O(1/ε5/3) for stochastic variance reduced policy gradient algorithms by a factor of O(1/ε1/6). In addition, we also propose a variant of SRVR-PG with parameter exploration, which explores the initial policy parameter from a prior probability distribution. We conduct numerical experiments on classic control problems in reinforcement learning to validate the performance of our proposed algorithms.

Key facts. Cited by 58 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 12; 2022: 9; 2023: 10; 2024: 10; 2025: 8; 2026: 8.

58 papers.

Sort:

By area:

  1. 2023ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Modelscited by 184
  2. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  3. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  4. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  5. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  6. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  7. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  8. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  9. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 27
  10. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  11. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  12. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
38 more
  1. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 20
  2. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  3. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  4. 2021Bregman Gradient Policy Optimizationcited by 15
  5. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 15
  6. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  7. 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12
  8. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  9. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  10. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  11. 2023A safe exploration approach to constrained Markov decision processescited by 10
  12. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 10
  13. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  14. 2024Policy Gradient with Active Importance Samplingcited by 9
  15. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  16. 2020Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Ratecited by 7
  17. 2021Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methodscited by 7
  18. 2023Model-Based Reparameterization Policy Gradient Methods: Theory and Practical Algorithmscited by 7
  19. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 7
  20. 2021MDPGT: Momentum-based Decentralized Policy Gradient Trackingcited by 6
  21. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  22. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  23. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysiscited by 5
  24. 2021On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correctioncited by 4
  25. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  26. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  27. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  28. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  29. 2022Variance-Reduced Conservative Policy Iterationcited by 2
  30. 2025Accelerating RLHF Training with Reward Variance Increasecited by 2
  31. 2026Rank-1 Approximation of Inverse Fisher for Natural Policy Gradients in Deep Reinforcement Learningcited by 2
  32. 2021Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learningcited by 1
  33. 2022Optimal Estimation of Off-Policy Policy Gradient via Double Fitted Iterationcited by 1
  34. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  35. 2023Efficiently Escaping Saddle Points for Policy Optimizationcited by 1
  36. 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimizationcited by 1
  37. 2025Reusing Trajectories in Policy Gradients Enables Fast Convergencecited by 1
  38. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1

50 most cited of 58 All 58 (JSON)