Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy

Abstract

Proximal policy optimization and trust region policy optimization (PPO and TRPO) with actor and critic parametrized by neural networks achieve significant empirical success in deep reinforcement learning. However, due to nonconvexity, the global convergence of PPO and TRPO remains less understood, which separates theory from practice. In this paper, we prove that a variant of PPO and TRPO equipped with overparametrized neural networks converges to the globally optimal policy at a sublinear rate. The key to our analysis is the global convergence of infinite-dimensional mirror descent under a notion of one-point monotonicity, where the gradient and iterate are instantiated by neural networks. In particular, the desirable representation power and optimization geometry induced by the overparametrization of such neural networks allow them to accurately approximate the infinite-dimensional gradient and iterate.

A short version

Cited by in corpus (32)

• A Theoretical Analysis of Deep Q-Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Proximal Policy Optimization-Based Reinforcement Learning Approach for DC-DC Boost Converter Control: A Comparative Evaluation Against Traditional Control Techniques
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Mathematical Models of Overparameterized Neural Networks
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Mirror Descent Policy Optimization
• Provably Efficient Exploration in Policy Optimization
• A hybrid learning method for system identification and optimal control
• A Primal-Dual Approach to Constrained Markov Decision Processes
• Revisiting Design Choices in Proximal Policy Optimization
• Optimistic Policy Optimization with Bandit Feedback
• 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
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Towards General Function Approximation in Zero-Sum Markov Games
• When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence
• On the Privacy Risks of Deploying Recurrent Neural Networks in Machine Learning Models
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Bregman Gradient Policy Optimization
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Analysis and Optimisation of Bellman Residual Errors with Neural Function Approximation