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

arXiv cs.LG Papers
reinforcement-learning natural-policy-gradient finite-horizon mdps convergence-analysis theoretical-analysis

Summary

This paper provides the first finite-time convergence guarantees for the Natural Policy Gradient algorithm in finite-horizon Markov Decision Processes, proving sublinear and linear convergence rates under different step size regimes.

arXiv:2607.22982v1 Announce Type: new Abstract: 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 $\eta_t=\eta$, we prove that NPG converges sublinearly with a rate of $\mathcal{O}(H^{2}/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 $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_\rho}\right)^t\right)$ for a problem-dependent constant $\vartheta_\rho > 1$, and the horizon-only robust schedule of the form $\eta_t=\eta_0(H/(H-1))^t$ where $\eta_0>0$ and $H \geq 2$, attains this same geometric rate.
Original Article
View Cached Full Text

Cached at: 07/28/26, 06:23 AM 

# Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
Source: [https://arxiv.org/abs/2607.22982](https://arxiv.org/abs/2607.22982)
[View PDF](https://arxiv.org/pdf/2607.22982)

> Abstract: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 $\\eta\_t=\\eta$, we prove that NPG converges sublinearly with a rate of $\\mathcal\{O\}\(H^\{2\}/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 $\\mathcal\{O\}\\left\(\\left\(1\-\\frac\{1\}\{\\vartheta\_\\rho\}\\right\)^t\\right\)$ for a problem\-dependent constant $\\vartheta\_\\rho \> 1$, and the horizon\-only robust schedule of the form $\\eta\_t=\\eta\_0\(H/\(H\-1\)\)^t$ where $\\eta\_0\>0$ and $H \\geq 2$, attains this same geometric rate\.

## Submission history

From: Asha Barua \[[view email](https://arxiv.org/show-email/53c802de/2607.22982)\] **\[v1\]**Sat, 25 Jul 2026 01:37:26 UTC \(47 KB\)

Similar Articles

Metric-Gradient Projection for Stable Multi-Agent Policy Learning

arXiv cs.LG

Introduces HPML, a method that projects the joint update field of multi-agent systems onto a metric-gradient component to stabilize and improve multi-agent reinforcement learning. It provides theoretical guarantees and shows improved stability and returns on CTDE benchmarks.

Gradient Extrapolation-Based Policy Optimization

arXiv cs.LG

The article introduces Gradient Extrapolation-Based Policy Optimization (GXPO), a method that approximates multi-step lookahead in RL training for LLMs using only three backward passes. It demonstrates improved reasoning performance on math benchmarks over standard GRPO while maintaining fixed active-phase costs.

Differentially Private Natural Gradient Descent

arXiv cs.LG

This paper introduces DP-NGD, a practical framework that integrates natural gradient descent with differential privacy by decoupling curvature estimation from private data and reconciling isotropic DP constraints with anisotropic second-order optimization, achieving state-of-the-art accuracy and up to 10x convergence speedup under the same privacy budget.