On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost

Abstract

Despite the empirical success of the actor-critic algorithm, its theoretical understanding lags behind. In a broader context, actor-critic can be viewed as an online alternating update algorithm for bilevel optimization, whose convergence is known to be fragile. To understand the instability of actor-critic, we focus on its application to linear quadratic regulators, a simple yet fundamental setting of reinforcement learning. We establish a nonasymptotic convergence analysis of actor-critic in this setting. In particular, we prove that actor-critic finds a globally optimal pair of actor (policy) and critic (action-value function) at a linear rate of convergence. Our analysis may serve as a preliminary step towards a complete theoretical understanding of bilevel optimization with nonconvex subproblems, which is NP-hard in the worst case and is often solved using heuristics.

arXiv comment41 pages

References in corpus (13)

• Certifying Some Distributional Robustness with Principled Adversarial Training
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Reproducibility of Benchmarked Deep Reinforcement Learning Tasks for Continuous Control
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• On the Sample Complexity of the Linear Quadratic Regulator
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• A Tour of Reinforcement Learning: The View from Continuous Control
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• Training Generative Adversarial Networks via Primal-Dual Subgradient Methods: A Lagrangian Perspective on GAN

Cited by in corpus (14)

• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Combining Model-Based and Model-Free Methods for Nonlinear Control: A Provably Convergent Policy Gradient Approach
• Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator
• Policy Optimization for Markovian Jump Linear Quadratic Control: Gradient-Based Methods and Global Convergence
• Analyzing the Variance of Policy Gradient Estimators 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
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Model-Free $\mu$ Synthesis via Adversarial Reinforcement Learning