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

Asha Barua; Sajad Khodadadian

cs.LGJul 25, 2026

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

Authors: Asha Barua, Sajad Khodadadian

Organizations: Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061, USA.

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 $η_t=η$ , 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_ρ}\right)^t\right)$ 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 \geq 2$ , attains this same geometric rate.

Explore similar work

May 11, 2026cs.LG

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework

In this work, we show that natural policy gradient, a core algorithm in reinforcement learning, admits an exact formulation as a smoothed and averaged form of policy iteration. Specifically, we introduce doubly smoothed policy iteration (DSPI), a Bellman-operator framework in which each policy is obtained by applying a regularized greedy step to a weighted average of past

Q

-functions. DSPI includes policy iteration, dual-averaged policy iteration, natural policy gradient, and more general policy dual averaging methods as special cases. Using only monotonicity and contraction of smoothed Bellman operators, we prove distribution-free global geometric convergence of DSPI. Consequently, standard natural policy gradient and policy dual averaging achieve an iteration complexity of

\mathcal{O}((1-γ)^{-1}\log((1-γ)^{-1}ε^{-1}))

for computing an

ε

-optimal policy, without modifying the MDP, adding regularization beyond the mirror map inherent in the update, or using adaptive, trajectory-dependent stepsizes. For the unregularized greedy case, corresponding to dual-averaged policy iteration, we also prove finite termination. The same Bellman-operator framework further extends to discounted MDPs with linear function approximation and stochastic shortest path problems.

Phalguni Nanda, Zaiwei Chen

Policy Gradient Bellman Equation Relative Policy Optimization

Ask PDF

May 12, 2026cs.LG

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes (CMDPs). While existing theoretical guarantees typically hold for the mixture policy, deploying such a policy is computationally and memory intensive. This leads to a practical mismatch where a single (last-iterate) policy must be deployed. Recent theoretical works have thus focused on proving last-iterate convergence, but are largely limited to the tabular setting or to algorithmic variants that are rarely used in practice. To address this, we use the classic inexact augmented Lagrangian (

\texttt{AL}

) method from constrained optimization, and propose a general framework with provable last-iterate convergence for CMDPs. We first focus on the tabular setting and propose to solve the

\texttt{AL}

sub-problem with projected Q-ascent (

\texttt{PQA}

). Combining the theoretical guarantees of

\texttt{PQA}

and the standard

\texttt{AL}

analysis enables us to establish global last-iterate convergence. We generalize these results to handle log-linear policies, and demonstrate that an efficient, projected variant of

\texttt{PQA}

can achieve last-iterate convergence with comparable guarantees as prior work. Finally, we demonstrate that our framework scales to complex non-linear policies, and evaluate it on continuous control tasks.

Michael Lu, Max Qiushi Lin, Mo Chen +1

Markov Decision Processes Finite Planning Horizon Policy Optimization Constrained Optimization Optimization Convergence Analysis Lagrangian Methods

Ask PDF

Jun 3, 2026cs.LG

Policy Gradient for Continuous-Time Robust Markov Decision Processes

The framework of robust Markov decision processes (RMDPs) allows the design of reinforcement learning agents that satisfy performance guarantees under worst-case transition dynamics. Traditional RMDPs consider discrete-time dynamics and recently, sample-efficient policy gradient algorithms have been considered in this context. This paper investigates policy gradient algorithms within a continuous-time RMDP framework. Policy gradients and adversarial gradients are derived using pathwise and adjoint-based formulas for stochastic and ordinary differential equations. We propose double-loop optimisers to obtain linear convergence in the oracle-based setting and an

\tilde{\mathcal{O}}(\frac{1}{ε^2})

sample complexity in the sample-based setting in an analysis which also derives novel tools for the framework of undiscounted total cost MDPs. Additionally, we propose mean-field optimisers as distributional optimisers with an

\tilde{\mathcal{O}}(\frac{1}{K})

oracle-based convergence rate and an

\tilde{\mathcal{O}}(\frac{N^2}ε)

sample complexity under

N

-particle approximation. The effectiveness of continuous-time policy gradient algorithms is confirmed for both optimisers on continuous-time RMDPs with neural ordinary differential equation dynamics.

Tanya Veeravalli, David M. Bossens, Atsushi Nitanda

Markov Decision Processes Policy Gradient Worst-Case Sensitivity

Ask PDF