On the Convergence Rates of Policy Gradient Methods
This work provides theoretical guarantees for policy optimization algorithms, which is important for researchers and practitioners in reinforcement learning, though it is incremental as it builds on existing convergence analysis.
The paper analyzes the convergence rates of policy gradient and policy mirror descent methods in infinite-horizon discounted Markov decision processes, proving sharper sublinear rates for projected policy gradient and linear rates for mirror descent methods with geometric step sizes, without requiring strong convexity.
We consider infinite-horizon discounted Markov decision problems with finite state and action spaces and study the convergence rates of the projected policy gradient method and a general class of policy mirror descent methods, all with direct parametrization in the policy space. First, we develop a theory of weak gradient-mapping dominance and use it to prove sharper sublinear convergence rate of the projected policy gradient method. Then we show that with geometrically increasing step sizes, a general class of policy mirror descent methods, including the natural policy gradient method and a projected Q-descent method, all enjoy a linear rate of convergence without relying on entropy or other strongly convex regularization. Finally, we also analyze the convergence rate of an inexact policy mirror descent method and estimate its sample complexity under a simple generative model.