mlsanityData to 7 Oct 2026

Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies

arXiv 2210.01400 ↗First posted 4 Oct 2022cs.LG cs.AI math.OCcited by 44

Not on the map. Why?

Abstract (arXiv)

We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy class. Using the compatible function approximation framework, both methods with log-linear policies can be written as inexact versions of the policy mirror descent (PMD) method. We show that both methods attain linear convergence rates and tildeO(1/ε2) sample complexities using a simple, non-adaptive geometrically increasing step size, without resorting to entropy or other strongly convex regularization. Lastly, as a byproduct, we obtain sublinear convergence rates for both methods with arbitrary constant step size.

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). Builds on 48 of its 92 references that are in the map. First posted on arXiv 4 Oct 2022.

Builds on

48 of 92 references.

References · 48

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2015Continuous control with deep reinforcement learningcited by 3,279
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  5. 2014New insights and perspectives on the natural gradient methodcited by 435
  6. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  8. 2019A Theory of Regularized Markov Decision Processescited by 279
  9. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  10. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  12. 2017A unified view of entropy-regularized Markov decision processescited by 174
36 more
  1. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  2. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  3. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  4. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  5. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  6. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  7. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  8. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  9. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  10. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  11. 2020Mirror Descent Policy Optimizationcited by 102
  12. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  13. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  14. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  15. 2014A Stochastic Quasi-Newton Method for Large-Scale Optimizationcited by 68
  16. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  17. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  18. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  19. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  20. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  21. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  22. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  23. 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
  24. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  25. 2020Momentum-Based Policy Gradient Methodscited by 28
  26. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  27. 2016Stochastic Block BFGS: Squeezing More Curvature out of Datacited by 24
  28. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  29. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  30. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  31. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  32. 2021A general class of surrogate functions for stable and efficient reinforcement learningcited by 16
  33. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  34. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  35. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
  36. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13

Built on by

Cited by year (2026 to 7 Oct)

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

44 papers.

Sort:

By area:

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  2. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  3. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  4. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  5. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  6. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  7. 2024Elementary Analysis of Policy Gradient Methodscited by 17
  8. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  9. 2022Geometry and convergence of natural policy gradient methodscited by 12
  10. 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
  11. 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignmentcited by 9
  12. 2024Understanding Stochastic Natural Gradient Variational Inferencecited by 8
32 more
  1. 2024Policy Mirror Descent with Lookaheadcited by 6
  2. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  3. 2023On the Second-Order Convergence of Biased Policy Gradient Algorithmscited by 5
  4. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
  5. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  6. 2026Why GRPO Needs Normalization: A Local-Curvature Perspective on Adaptive Gradientscited by 4
  7. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  8. 2024Functional Acceleration for Policy Mirror Descentcited by 3
  9. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  10. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  11. 2023Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimalitycited by 2
  12. 2024Fast Convergence of Softmax Policy Mirror Ascentcited by 2
  13. 2024A learning-based approach to stochastic optimal control under reach-avoid constraintcited by 2
  14. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  15. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  16. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  17. 2024Learning mirror maps in policy mirror descentcited by 1
  18. 2024Dual Approximation Policy Optimizationcited by 1
  19. 2024Convex Regularization and Convergence of Policy Gradient Flows under Safety Constraintscited by 1
  20. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  21. 2025Ordering-based Conditions for Global Convergence of Policy Gradient Methodscited by 1
  22. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learningcited by 1
  23. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  24. 2026Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradientscited by 1
  25. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 1
  26. 2023Acceleration in Policy Optimizationcited by 0
  27. 2025Convergence Properties of Natural Gradient Descent for Minimizing KL Divergencecited by 0
  28. 2026Approximation of Log-Partition Function in Policy Mirror Descent Induces Implicit Regularization for LLM Post-Trainingcited by 0
  29. 2026Beyond State-Wise Mirror Descent: Offline Policy Optimization with Parametric Policiescited by 0
  30. 2026Cross-Domain Policy Optimization via Bellman Consistency and Hybrid Criticscited by 0
  31. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Frameworkcited by 0
  32. 2026An analysis of Mirror-Descent Soft Actor-Criticcited by 0