# Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 30 references that are in the map.
- First posted on arXiv 30 Sep 2022.

## Builds on (most cited first, 23 of 23)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [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)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [The Information Geometry of Mirror Descent](https://mlsanity.com/paper/1310.7780/) (2013)
- [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)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)

## Built on by (most cited first, 17 of 17)

- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods](https://mlsanity.com/paper/2310.02671/) (2023)
- [Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients](https://mlsanity.com/paper/2403.19448/) (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)
- [Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifolds](https://mlsanity.com/paper/2309.13915/) (2023)
- [Ordering-based Conditions for Global Convergence of Policy Gradient Methods](https://mlsanity.com/paper/2504.02130/) (2025)
- [Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning](https://mlsanity.com/paper/2507.04406/) (2025)
- [Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning](https://mlsanity.com/paper/2509.24305/) (2025)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)
- [Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework](https://mlsanity.com/paper/2605.10671/) (2026)
- [Fast Regularized Policy Mirror Descent with One-Step TD Updates](https://mlsanity.com/paper/2609.39837/) (2026)

## Abstract (arXiv)

We analyze the convergence rate of the unregularized natural policy gradient algorithm with log-linear policy parametrizations in infinite-horizon discounted Markov decision processes. In the deterministic case, when the Q-value is known and can be approximated by a linear combination of a known feature function up to a bias error, we show that a geometrically-increasing step size yields a linear convergence rate towards an optimal policy. We then consider the sample-based case, when the best representation of the Q- value function among linear combinations of a known feature function is known up to an estimation error. In this setting, we show that the algorithm enjoys the same linear guarantees as in the deterministic case up to an error term that depends on the estimation error, the bias error, and the condition number of the feature covariance matrix. Our results build upon the general framework of policy mirror descent and extend previous findings for the softmax tabular parametrization to the log-linear policy class.