Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint
31/2022

Geometry and convergence of natural policy gradient methods

Guido Montúfar and Johannes Müller

Abstract

We study the convergence of several natural policy gradient (NPG) methods in infinite-horizon discounted Markov decision processes with regular policy parametrizations. For a variety of NPGs and reward functions we show that the trajectories in state-action space are solutions of gradient flows with respect to Hessian geometries, based on which we obtain global convergence guarantees and convergence rates. In particular, we show linear convergence for unregularized and regularized NPG flows with the metrics proposed by Kakade and Morimura and co-authors by observing that these arise from the Hessian geometries of conditional entropy and entropy respectively. Further, we obtain sublinear convergence rates for Hessian geometries arising from other convex functions like log-barriers. Finally, we interpret the discrete-time NPG methods with regularized rewards as inexact Newton methods if the NPG is defined with respect to the Hessian geometry of the regularizer. This yields local quadratic convergence rates of these methods for step size equal to the penalization strength.

Received:
Nov 4, 2022
Published:
Nov 4, 2022
MSC Codes:
90C40, 53B12, 90C53
Keywords:
Markov decision proces, Natural policy gradient, State-action frequency, Hessian geometry, stochastic policy

Related publications

inJournal
2024 Journal Open Access
Johannes Müller and Guido Montúfar

Geometry and convergence of natural policy gradient methods

In: Information geometry, 7 (2024) 1, pp. 485-523