On Linear Convergence of Policy Gradient Methods for Finite MDPs

2020/07/21 by Bhandari, Jalaj, Russo, Daniel · 3 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2007.11120

Abstract

We revisit the finite time analysis of policy gradient methods in the one of the simplest settings: finite state and action MDPs with a policy class consisting of all stochastic policies and with exact gradient evaluations. There has been some recent work viewing this setting as an instance of smooth non-linear optimization problems and showing sub-linear convergence rates with small step-sizes. Here, we take a different perspective based on connections with policy iteration and show that many variants of policy gradient methods succeed with large step-sizes and attain a linear rate of convergence.

Cited by

• On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation
• Imitate Optimal Policy: Prevail and Induce Action Collapse in Policy Gradient
• Statistical and Algorithmic Foundations of Reinforcement Learning

Related

• On the Convergence Rates of Policy Gradient Methods
• On the Linear convergence of Natural Policy Gradient Algorithm
• Strongly-polynomial time and validation analysis of policy gradient methods
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
• Elementary Analysis of Policy Gradient Methods