An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods

Abstract

In this paper, we revisit and improve the convergence of policy gradient (PG), natural PG (NPG) methods, and their variance-reduced variants, under general smooth policy parametrizations. More specifically, with the Fisher information matrix of the policy being positive definite: i) we show that a state-of-the-art variance-reduced PG method, which has only been shown to converge to stationary points, converges to the globally optimal value up to some inherent function approximation error due to policy parametrization; ii) we show that NPG enjoys a lower sample complexity; iii) we propose SRVR-NPG, which incorporates variance-reduction into the NPG update. Our improvements follow from an observation that the convergence of (variance-reduced) PG and NPG methods can improve each other: the stationary convergence analysis of PG can be applied to NPG as well, and the global convergence analysis of NPG can help to establish the global convergence of (variance-reduced) PG methods. Our analysis carefully integrates the advantages of these two lines of works. Thanks to this improvement, we have also made variance-reduction for NPG possible, with both global convergence and an efficient finite-sample complexity.

arXiv commentNeurIPS 2020 (improve the proof of Lemma B.1 and Proposition G.1.)

References in corpus (7)

• Trust Region Policy Optimization
• Benchmarking Deep Reinforcement Learning for Continuous Control
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• An Analysis of Reinforcement Learning with Function Approximation
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic

Cited by in corpus (11)

• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• A general sample complexity analysis of vanilla policy gradient
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• Bregman Gradient Policy Optimization
• A learning-based approach to stochastic optimal control under reach-avoid constraint
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• A nearly Blackwell-optimal policy gradient method