mlsanityData to 14 Oct 2026

An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient

arXiv 1905.12615 ↗First posted 29 May 2019cs.LG cs.AI math.OCcited by 59

Not on the map. Why?

Cited by 21 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

We revisit the stochastic variance-reduced policy gradient (SVRPG) method proposed by Papini et al. (2018) for reinforcement learning. We provide an improved convergence analysis of SVRPG and show that it can find an ε-approximate stationary point of the performance function within O(1/ε5/3) trajectories. This sample complexity improves upon the best known result O(1/ε2) by a factor of O(1/ε1/3). At the core of our analysis is (i) a tighter upper bound for the variance of importance sampling weights, where we prove that the variance can be controlled by the parameter distance between different policies; and (ii) a fine-grained analysis of the epoch length and batch size parameters such that we can significantly reduce the number of trajectories required in each iteration of SVRPG. We also empirically demonstrate the effectiveness of our theoretical claims of batch sizes on reinforcement learning benchmark tasks.

Key facts. Cited by 59 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 11; 2022: 12; 2023: 10; 2024: 14; 2025: 6; 2026: 5.

59 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  2. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  3. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  4. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  5. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  6. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 54
  7. 2022Efficient Risk-Averse Reinforcement Learningcited by 43
  8. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  9. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 28
  10. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  11. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  12. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 24
38 more
  1. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  2. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  3. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  4. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  5. 2021Bregman Gradient Policy Optimizationcited by 17
  6. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17
  7. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 13
  8. 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12
  9. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 12
  10. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  11. 2024Policy Gradient with Active Importance Samplingcited by 10
  12. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  13. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 8
  14. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  15. 2020Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Ratecited by 7
  16. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  17. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysiscited by 6
  18. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  19. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
  20. 2024On Divergence Measures for Training GFlowNetscited by 6
  21. 2021Smoothed functional-based gradient algorithms for off-policy reinforcement learning: A non-asymptotic viewpointcited by 5
  22. 2021On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correctioncited by 5
  23. 2022Variance Reduction for Policy-Gradient Methods via Empirical Variance Minimizationcited by 4
  24. 2024Streaming Bayes GFlowNetscited by 4
  25. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  26. 2023Policy Gradient with Tree Expansioncited by 3
  27. 2024On the Convergence of Single-Timescale Actor-Criticcited by 3
  28. 2023Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approachcited by 2
  29. 2023Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimizationcited by 2
  30. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  31. 2024Decentralized Federated Policy Gradient with Byzantine Fault-Tolerance and Provably Fast Convergencecited by 2
  32. 2026Rank-1 Approximation of Inverse Fisher for Natural Policy Gradients in Deep Reinforcement Learningcited by 2
  33. 2021Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learningcited by 1
  34. 2022Optimal Estimation of Off-Policy Policy Gradient via Double Fitted Iterationcited by 1
  35. 2022Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Criticcited by 1
  36. 2022SoftTreeMax: Policy Gradient with Tree Searchcited by 1
  37. 2023Efficiently Escaping Saddle Points for Policy Optimizationcited by 1
  38. 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimizationcited by 1

50 most cited of 59 All 59 (JSON)