mlsanityData to 7 Oct 2026

On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method

arXiv 2102.08607 ↗First posted 17 Feb 2021cs.LG stat.MLcited by 67

Not on the map. Why?

Abstract (arXiv)

Policy gradient (PG) gives rise to a rich class of reinforcement learning (RL) methods. Recently, there has been an emerging trend to accelerate the existing PG methods such as REINFORCE by the variance reduction techniques. However, all existing variance-reduced PG methods heavily rely on an uncheckable importance weight assumption made for every single iteration of the algorithms. In this paper, a simple gradient truncation mechanism is proposed to address this issue. Moreover, we design a Truncated Stochastic Incremental Variance-Reduced Policy Gradient (TSIVR-PG) method, which is able to maximize not only a cumulative sum of rewards but also a general utility function over a policy's long-term visiting distribution. We show an tildeO(ε-3) sample complexity for TSIVR-PG to find an ε-stationary policy. By assuming the overparameterizaiton of policy and exploiting the hidden convexity of the problem, we further show that TSIVR-PG converges to global ε-optimal policy with tildeO(ε-2) samples.

Key facts. Cited by 67 papers in the map (data through 7 Oct 2026). Builds on 38 of its 59 references that are in the map. First posted on arXiv 17 Feb 2021.

Builds on

38 of 59 references.

References · 38

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  4. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  5. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  8. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  9. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  10. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  11. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  12. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
26 more
  1. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  2. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  3. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  4. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  5. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  6. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  7. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  8. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  9. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 85
  10. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  11. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  12. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  13. 2019Reinforcement Learning with Convex Constraintscited by 57
  14. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  15. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  16. 2016Accelerating Stochastic Composition Optimizationcited by 46
  17. 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
  18. 2019A Stochastic Composite Gradient Method with Incremental Variance Reductioncited by 26
  19. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  20. 2020Cautious Reinforcement Learning via Distributional Risk in the Dual Domaincited by 18
  21. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 17
  22. 2016Finite-sum Composition Optimization via Variance Reduced Gradient Descentcited by 15
  23. 2017Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularizationcited by 13
  24. 2018Scalable Bilinear π Learning Using State and Action Featurescited by 10
  25. 2016Fast Incremental Method for Nonconvex Optimizationcited by 9
  26. 2019A Stochastic Trust-Region Framework for Policy Optimizationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 10; 2023: 14; 2024: 15; 2025: 8; 2026: 10.

67 papers.

Sort:

By area:

  1. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  2. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  3. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  4. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  5. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  6. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  7. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  8. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  9. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  10. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  11. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  12. 2023Instruction Tuned Models are Quick Learnerscited by 21
38 more
  1. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  2. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  3. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  4. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  5. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  6. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  7. 2021Bregman Gradient Policy Optimizationcited by 15
  8. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 15
  9. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  10. 2024Transformer-based Model Predictive Control: Trajectory Optimization via Sequence Modelingcited by 15
  11. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  12. 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12
  13. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  14. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  15. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  16. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  17. 2024Stochastic Gradient Succeeds for Banditscited by 10
  18. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  19. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  20. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  21. 2021MDPGT: Momentum-based Decentralized Policy Gradient Trackingcited by 6
  22. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  23. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  24. 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settingscited by 5
  25. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  26. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  27. 2025Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning ratescited by 4
  28. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  29. 2023Policy Gradient with Tree Expansioncited by 3
  30. 2025Multilinear Tensor Low-Rank Approximation for Policy-Gradient Methods in Reinforcement Learningcited by 3
  31. 2022On the Reuse Bias in Off-Policy Reinforcement Learningcited by 2
  32. 2022Variance-Reduced Conservative Policy Iterationcited by 2
  33. 2023Scalable Multi-Agent Reinforcement Learning with General Utilitiescited by 2
  34. 2025Robo-taxi Fleet Coordination at Scale via Reinforcement Learningcited by 2
  35. 2025Non-Asymptotic Global Convergence of PPO-Clipcited by 2
  36. 2026Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilitiescited by 2
  37. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
  38. 2022Optimal Estimation of Off-Policy Policy Gradient via Double Fitted Iterationcited by 1

50 most cited of 67 All 67 (JSON)