mlsanityData to 7 Oct 2026

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

arXiv 2607.22982 ↗First posted 25 Jul 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size ηt=η, we prove that NPG converges sublinearly with a rate of O(H2/t) after t iterations, where H is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of Oleft(left(1-frac1varthetaρright)tright) for a problem-dependent constant varthetaρ > 1, and the horizon-only robust schedule of the form ηt=η0(H/(H-1))t where η0>0 and H ≥ 2, attains this same geometric rate.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 25 references that are in the map. First posted on arXiv 25 Jul 2026.

Builds on

17 of 25 references.

References · 17

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,634
  4. 2015Trust Region Policy Optimizationcited by 2,503
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  7. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  8. 2025A Survey of Reinforcement Learning for Large Reasoning Modelscited by 175
  9. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  10. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  11. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  12. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
5 more
  1. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  2. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  3. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  4. 2024Elementary Analysis of Policy Gradient Methodscited by 17
  5. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9

Built on by

Not cited yet.