mlsanityData to 14 Oct 2026

A general sample complexity analysis of vanilla policy gradient

arXiv 2107.11433 ↗First posted 23 Jul 2021cs.LG math.OC stat.MLcited by 76

Not on the map. Why?

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

Abstract (arXiv)

We adapt recent tools developed for the analysis of Stochastic Gradient Descent (SGD) in non-convex optimization to obtain convergence and sample complexity guarantees for the vanilla policy gradient (PG). Our only assumptions are that the expected return is smooth w.r.t. the policy parameters, that its H-step truncated gradient is close to the exact gradient, and a certain ABC assumption. This assumption requires the second moment of the estimated gradient to be bounded by A≥ 0 times the suboptimality gap, B ≥ 0 times the norm of the full batch gradient and an additive constant C ≥ 0, or any combination of aforementioned. We show that the ABC assumption is more general than the commonly used assumptions on the policy space to prove convergence to a stationary point. We provide a single convergence theorem that recovers the widetildeO(ε-4) sample complexity of PG to a stationary point. Our results also affords greater flexibility in the choice of hyper parameters such as the step size and the batch size m, including the single trajectory case (i.e., m=1). When an additional relaxed weak gradient domination assumption is available, we establish a novel global optimum convergence theory of PG with widetildeO(ε-3) sample complexity. We then instantiate our theorems in different settings, where we both recover existing results and obtain improved sample complexity, e.g., widetildeO(ε-3) sample complexity for the convergence to the global optimum for Fisher-non-degenerated parametrized policies.

Key facts. Cited by 76 papers in the map (data through 14 Oct 2026). Builds on 35 of its 107 references that are in the map. First posted on arXiv 23 Jul 2021.

Builds on

35 of 107 references.

References · 35

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  6. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  7. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  8. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  9. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  11. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 182
  12. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
23 more
  1. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  2. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  3. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  4. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  5. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  6. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  7. 2020Mirror Descent Policy Optimizationcited by 106
  8. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 86
  9. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  10. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  11. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  12. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  13. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  14. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  15. 2019Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptionscited by 48
  16. 2019The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descentcited by 46
  17. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  18. 2020Momentum-Based Policy Gradient Methodscited by 30
  19. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  20. 2019Smoothing Policies and Safe Policy Gradientscited by 21
  21. 2019Policy Optimization with Stochastic Mirror Descentcited by 18
  22. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 18
  23. 2021Bregman Gradient Policy Optimizationcited by 17

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 13; 2024: 24; 2025: 16; 2026: 15.

76 papers.

Sort:

By area:

  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  2. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  3. 2023Fine-Tuning Language Models with Advantage-Induced Policy Alignmentcited by 48
  4. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  5. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  6. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  7. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  8. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  9. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  10. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  11. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  12. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
38 more
  1. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 17
  2. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 12
  3. 2024FedRLHF: A Convergence-Guaranteed Federated Framework for Privacy-Preserving and Personalized RLHFcited by 12
  4. 2025Iterative Distillation for Reward-Guided Fine-Tuning of Diffusion Models in Biomolecular Designcited by 11
  5. 2025TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedbackcited by 11
  6. 2023A safe exploration approach to constrained Markov decision processescited by 10
  7. 2024Stochastic Gradient Succeeds for Banditscited by 10
  8. 2024Policy Gradient with Active Importance Samplingcited by 10
  9. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  10. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  11. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 8
  12. 2026Why Pass@k Optimization Can Degrade Pass@1: Prompt Interference in LLM Post-trainingcited by 8
  13. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPscited by 7
  14. 2024Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theorycited by 7
  15. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  16. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 6
  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. 2025Performative Policy Gradient: Optimality in Performative Reinforcement Learningcited by 6
  20. 2022From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descentcited by 5
  21. 2023On the Second-Order Convergence of Biased Policy Gradient Algorithmscited by 5
  22. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  23. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learningcited by 4
  24. 2025Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning ratescited by 4
  25. 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrizationcited by 3
  26. 2023Decision-Aware Actor-Critic with Function Approximation and Theoretical Guaranteescited by 3
  27. 2024On the Convergence of Single-Timescale Actor-Criticcited by 3
  28. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
  29. 2024A learning-based approach to stochastic optimal control under reach-avoid constraintcited by 3
  30. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  31. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  32. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 3
  33. 2023On the Linear Convergence of Policy Gradient under Hadamard Parameterizationcited by 2
  34. 2024On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Conditioncited by 2
  35. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  36. 2024Stochastic Gradient Descent with Adaptive Datacited by 2
  37. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  38. 2025Non-Asymptotic Global Convergence of PPO-Clipcited by 2

50 most cited of 76 All 76 (JSON)