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

arXiv: https://arxiv.org/abs/2210.01400 · HTML: https://mlsanity.com/paper/2210.01400/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 92 references that are in the map.
- First posted on arXiv 4 Oct 2022.

## Builds on (most cited first, 30 of 48)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [New insights and perspectives on the natural gradient method](https://mlsanity.com/paper/1412.1193/) (2014)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Mirror Descent Policy Optimization](https://mlsanity.com/paper/2005.09814/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020)

## Built on by (most cited first, 30 of 46)

- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces](https://mlsanity.com/paper/2310.02951/) (2023)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [Rate-Optimal Policy Optimization for Linear Markov Decision Processes](https://mlsanity.com/paper/2308.14642/) (2023)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards](https://mlsanity.com/paper/2306.11455/) (2023)
- [Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignment](https://mlsanity.com/paper/2410.20727/) (2024)
- [Understanding Stochastic Natural Gradient Variational Inference](https://mlsanity.com/paper/2406.01870/) (2024)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients](https://mlsanity.com/paper/2403.19448/) (2024)
- [Why GRPO Needs Normalization: A Local-Curvature Perspective on Adaptive Gradients](https://mlsanity.com/paper/2601.23135/) (2026)
- [Approximate Global Convergence of Independent Learning in Multi-Agent Systems](https://mlsanity.com/paper/2405.19811/) (2024)
- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)
- [A learning-based approach to stochastic optimal control under reach-avoid constraint](https://mlsanity.com/paper/2412.16561/) (2024)
- [Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games](https://mlsanity.com/paper/2502.09780/) (2025)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimality](https://mlsanity.com/paper/2303.12785/) (2023)
- [Dual Approximation Policy Optimization](https://mlsanity.com/paper/2410.01249/) (2024)
- [Fast Convergence of Softmax Policy Mirror Ascent](https://mlsanity.com/paper/2411.12042/) (2024)
- [Convergence of Policy Mirror Descent Beyond Compatible Function Approximation](https://mlsanity.com/paper/2502.11033/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)

## 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.