Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games

Abstract

We study the global convergence of policy optimization for finding the Nash equilibria (NE) in zero-sum linear quadratic (LQ) games. To this end, we first investigate the landscape of LQ games, viewing it as a nonconvex-nonconcave saddle-point problem in the policy space. Specifically, we show that despite its nonconvexity and nonconcavity, zero-sum LQ games have the property that the stationary point of the objective function with respect to the linear feedback control policies constitutes the NE of the game. Building upon this, we develop three projected nested-gradient methods that are guaranteed to converge to the NE of the game. Moreover, we show that all of these algorithms enjoy both globally sublinear and locally linear convergence rates. Simulation results are also provided to illustrate the satisfactory convergence properties of the algorithms. To the best of our knowledge, this work appears to be the first one to investigate the optimization landscape of LQ games, and provably show the convergence of policy optimization methods to the Nash equilibria. Our work serves as an initial step toward understanding the theoretical aspects of policy-based reinforcement learning algorithms for zero-sum Markov games in general.

Fixed some typos, addressed some comments from NeurIPS reviews

Cited by in corpus (25)

• Game-Theoretic Multiagent Reinforcement Learning
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Games
• GANs May Have No Nash Equilibria
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• Entropy Regularization for Mean Field Games with Learning
• Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Decentralized Q-Learning in Zero-sum Markov Games
• Global Convergence of Policy Gradient Primal-dual Methods for Risk-constrained LQRs
• Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field Control/Game in Continuous Time
• Primal-dual Learning for the Model-free Risk-constrained Linear Quadratic Regulator
• On Characterizing GAN Convergence Through Proximal Duality Gap
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• A Game-Theoretic Approach to Multi-Agent Trust Region Optimization
• Independent Learning in Stochastic Games
• Gradient play in stochastic games: stationary points, convergence, and sample complexity
• Mechanism Design for Demand Management in Energy Communities
• Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games
• Learning Meta Representations for Agents in Multi-Agent Reinforcement Learning
• Policy Optimization for Linear-Quadratic Zero-Sum Mean-Field Type Games
• Approximate Midpoint Policy Iteration for Linear Quadratic Control