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

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 O(H squared/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 O ((1-1 over rho) t) for a problem-dependent constant 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 at least 2, attains this same geometric rate.