Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator

Abstract

Direct policy gradient methods for reinforcement learning and continuous control problems are a popular approach for a variety of reasons: 1) they are easy to implement without explicit knowledge of the underlying model 2) they are an "end-to-end" approach, directly optimizing the performance metric of interest 3) they inherently allow for richly parameterized policies. A notable drawback is that even in the most basic continuous control problem (that of linear quadratic regulators), these methods must solve a non-convex optimization problem, where little is understood about their efficiency from both computational and statistical perspectives. In contrast, system identification and model based planning in optimal control theory have a much more solid theoretical footing, where much is known with regards to their computational and statistical properties. This work bridges this gap showing that (model free) policy gradient methods globally converge to the optimal solution and are efficient (polynomially so in relevant problem dependent quantities) with regards to their sample and computational complexities.

Cited by in corpus (112)

• Game-Theoretic Multiagent Reinforcement Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• On the Sample Complexity of the Linear Quadratic Regulator
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Efficient Off-Policy Q-Learning for Data-Based Discrete-Time LQR Problems
• Improper Learning for Non-Stochastic Control
• Learning the Globally Optimal Distributed LQ Regulator
• Certainty Equivalence is Efficient for Linear Quadratic Control
• Variance-reduced $Q$-learning is minimax optimal
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Linear-Quadratic Mean-Field Reinforcement Learning: Convergence of Policy Gradient Methods
• Logarithmic Regret for Adversarial Online Control
• Naive Exploration is Optimal for Online LQR
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Is Q-learning Provably Efficient?
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
• Near-Optimal Design of Safe Output Feedback Controllers from Noisy Data
• Online Linear Quadratic Control
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Observational Overfitting in Reinforcement Learning
• Provably Efficient Exploration in Policy Optimization
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• On Regularizability and its Application to Online Control of Unstable LTI Systems
• First Order Methods For Globally Optimal Distributed Controllers Beyond Quadratic Invariance
• From self-tuning regulators to reinforcement learning and back again
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Adaptive Regret for Control of Time-Varying Dynamics
• CAQL: Continuous Action Q-Learning
• Invariant Policy Optimization: Towards Stronger Generalization in Reinforcement Learning
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Stabilizing Dynamical Systems via Policy Gradient Methods
• Entropy Regularization for Mean Field Games with Learning
• The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint
• Path Length Bounds for Gradient Descent and Flow
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon
• Policy Gradient-based Algorithms for Continuous-time Linear Quadratic Control
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees
• Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon
• Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Optimization Landscape of Gradient Descent for Discrete-time Static Output Feedback
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• Cooperative Multi-Agent Reinforcement Learning with Partial Observations
• Policy Gradient in Partially Observable Environments: Approximation and Convergence
• The Power of Predictions in Online Control
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent
• A general sample complexity analysis of vanilla policy gradient
• Data-Driven System Level Synthesis
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Global Convergence of Policy Gradient Primal-dual Methods for Risk-constrained LQRs
• Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
• A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning
• Sample Complexity of Data-Driven Stochastic LQR with Multiplicative Uncertainty
• Policy Optimization for Markovian Jump Linear Quadratic Control: Gradient-Based Methods and Global Convergence
• On the Analysis of Model-free Methods for the Linear Quadratic Regulator
• Policy Learning of MDPs with Mixed Continuous/Discrete Variables: A Case Study on Model-Free Control of Markovian Jump Systems
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control
• Primal-dual Learning for the Model-free Risk-constrained Linear Quadratic Regulator
• Neural optimal feedback control with local learning rules
• Online Optimal Control with Affine Constraints
• A fast randomized incremental gradient method for decentralized non-convex optimization
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• Using Echo State Networks to Approximate Value Functions for Control
• Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems
• Distributed Online Linear Quadratic Control for Linear Time-invariant Systems
• A Crash Course on Reinforcement Learning
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Accelerating Reinforcement Learning with a Directional-Gaussian-Smoothing Evolution Strategy
• Reward Learning for Efficient Reinforcement Learning in Extractive Document Summarisation
• Global Convergence Using Policy Gradient Methods for Model-free Markovian Jump Linear Quadratic Control
• On the Regret Analysis of Online LQR Control with Predictions
• Robust Spectral Filtering and Anomaly Detection
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Model-Free Design of Stochastic LQR Controller from Reinforcement Learning and Primal-Dual Optimization Perspective
• Exact Asymptotics for Linear Quadratic Adaptive Control
• Potential-Based Advice for Stochastic Policy Learning
• Small errors in random zeroth-order optimization are imaginary
• Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with $\sqrt{T}$ Regret
• On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure
• Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games
• Sample Complexity of the Robust LQG Regulator with Coprime Factors Uncertainty
• Learning Expected Reward for Switched Linear Control Systems: A Non-Asymptotic View
• Score-Aware Policy-Gradient and Performance Guarantees using Local Lyapunov Stability
• On the Effectiveness of Iterative Learning Control
• Minimal Expected Regret in Linear Quadratic Control
• Online Algorithms and Policies Using Adaptive and Machine Learning Approaches
• A Meta-Learning Control Algorithm with Provable Finite-Time Guarantees
• Meta-Learning Guarantees for Online Receding Horizon Learning Control
• Safe non-smooth black-box optimization with application to policy search
• Gradient and Hessian approximations in Derivative Free Optimization
• Model-Free $\mu$ Synthesis via Adversarial Reinforcement Learning
• Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds
• Learning Distributed Stabilizing Controllers for Multi-Agent Systems
• Model-Free Optimal Control of Linear Multi-Agent Systems via Decomposition and Hierarchical Approximation
• Approximate Midpoint Policy Iteration for Linear Quadratic Control