On the Linear convergence of Natural Policy Gradient Algorithm
This work provides theoretical guarantees for a foundational algorithm in reinforcement learning, which is incremental but important for optimizing policy-based methods used in applications like robotics and game playing.
The paper improves the convergence analysis of the Natural Policy Gradient algorithm in reinforcement learning, showing it achieves geometric (linear) asymptotic convergence and introducing an adaptive step-size variant for better performance.
Markov Decision Processes are classically solved using Value Iteration and Policy Iteration algorithms. Recent interest in Reinforcement Learning has motivated the study of methods inspired by optimization, such as gradient ascent. Among these, a popular algorithm is the Natural Policy Gradient, which is a mirror descent variant for MDPs. This algorithm forms the basis of several popular Reinforcement Learning algorithms such as Natural actor-critic, TRPO, PPO, etc, and so is being studied with growing interest. It has been shown that Natural Policy Gradient with constant step size converges with a sublinear rate of O(1/k) to the global optimal. In this paper, we present improved finite time convergence bounds, and show that this algorithm has geometric (also known as linear) asymptotic convergence rate. We further improve this convergence result by introducing a variant of Natural Policy Gradient with adaptive step sizes. Finally, we compare different variants of policy gradient methods experimentally.