On The Linear Convergence Of Natural Policy Gradient Algorithm

Abstract

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 metho

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykhodadadian2021on

Related papers

• On The Theory Of Policy Gradient Methods: Optimality, Approximation, And Distribution Shift (2019)0.00
• Global Convergence Of Policy Gradient Methods In Reinforcement Learning, Games And Control (2023)0.00
• Elementary Analysis Of Policy Gradient Methods (2024)0.00
• Symmetric (optimistic) Natural Policy Gradient For Multi-agent Learning With Parameter Convergence (2022)0.00
• Linear Convergence Of A Policy Gradient Method For Some Finite Horizon Continuous Time Control Problems (2022)0.00
• Natural Policy Gradients In Reinforcement Learning Explained (2022)0.00
• Fast Global Convergence Of Natural Policy Gradient Methods With Entropy Regularization (2020)0.00
• Linear-quadratic Mean-field Reinforcement Learning: Convergence Of Policy Gradient Methods (2019)0.00