Neural Policy Gradient Methods: Global Optimality and Rates of Convergence

Abstract

Policy gradient methods with actor-critic schemes demonstrate tremendous empirical successes, especially when the actors and critics are parameterized by neural networks. However, it remains less clear whether such "neural" policy gradient methods converge to globally optimal policies and whether they even converge at all. We answer both the questions affirmatively in the overparameterized regime. In detail, we prove that neural natural policy gradient converges to a globally optimal policy at a sublinear rate. Also, we show that neural vanilla policy gradient converges sublinearly to a stationary point. Meanwhile, by relating the suboptimality of the stationary points to the representation power of neural actor and critic classes, we prove the global optimality of all stationary points under mild regularity conditions. Particularly, we show that a key to the global optimality and convergence is the "compatibility" between the actor and critic, which is ensured by sharing neural architectures and random initializations across the actor and critic. To the best of our knowledge, our analysis establishes the first global optimality and convergence guarantees for neural policy gradient methods.

arXiv comment71 pages. The first two authors contribute equally

References in corpus (31)

• Trust Region Policy Optimization
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
• Deep Neural Networks as Gaussian Processes
• Deep Reinforcement Learning: An Overview
• Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• A Theoretical Analysis of Deep Q-Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• LQR through the Lens of First Order Methods: Discrete-time Case
• SGD Learns the Conjugate Kernel Class of the Network
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Information-Theoretic Considerations in Batch Reinforcement Learning
• A Selective Overview of Deep Learning
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Expressiveness of Rectifier Networks
• Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient
• Stochastic Variance-Reduced Policy Gradient
• The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint
• On the Performance Bounds of some Policy Search Dynamic Programming Algorithms

Cited by in corpus (41)

• A Theoretical Analysis of Deep Q-Learning
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Mathematical Models of Overparameterized Neural Networks
• Is Pessimism Provably Efficient for Offline RL?
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Provably Efficient Exploration in Policy Optimization
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• A Primal-Dual Approach to Constrained Markov Decision Processes
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Policy Gradient in Partially Observable Environments: Approximation and Convergence
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Policy-Aware Model Learning for Policy Gradient Methods
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
• Towards General Function Approximation in Zero-Sum Markov Games
• Deep reinforced learning enables solving rich discrete-choice life cycle models to analyze social security reforms
• Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process
• Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPs
• Actor-critic is implicitly biased towards high entropy optimal policies
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning
• Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Global optimality of softmax policy gradient with single hidden layer neural networks in the mean-field regime