mlsanityData to 7 Oct 2026

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

arXiv 2209.15382 ↗First posted 30 Sep 2022cs.LG math.OC math.STcited by 17

Not on the map. Why?

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.

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

Builds on

23 of 30 references.

References · 23

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2014Convex Optimization: Algorithms and Complexitycited by 569
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  6. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  8. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  9. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  12. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
11 more
  1. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  2. 2013The Information Geometry of Mirror Descentcited by 53
  3. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  4. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  5. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  6. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  7. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  8. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  9. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  10. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  11. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 7; 2024: 2; 2025: 4; 2026: 2.

17 papers.

Sort:

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  2. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  3. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  4. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  5. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  6. 2022Geometry and convergence of natural policy gradient methodscited by 12
  7. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  8. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
  9. 2024Fast Convergence of Softmax Policy Mirror Ascentcited by 2
  10. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  11. 2023Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifoldscited by 1
  12. 2025Ordering-based Conditions for Global Convergence of Policy Gradient Methodscited by 1
5 more
  1. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learningcited by 1
  2. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  3. 2023Acceleration in Policy Optimizationcited by 0
  4. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Frameworkcited by 0
  5. 2026Fast Regularized Policy Mirror Descent with One-Step TD Updatescited by 0