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

Kaiqing Zhang, Zhuoran Yang, Tamer Basar

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.

Introduction

In single-agent reinforcement learning (RL), policy gradient methods have a robust theoretical foundation. However, extending these successes to multi-agent reinforcement learning (MARL) introduces significant complexity. When multiple agents—such as a minimizer and a maximizer in a zero-sum game—learn simultaneously, the environment becomes non-stationary from the perspective of any individual agent.

Mathematically, this interaction manifests as a non-convex-non-concave saddle-point problem. In such landscapes, standard gradient-based methods frequently fail, often becoming trapped in local optima, oscillating between states, or entering limit cycles. This paper addresses these challenges within the framework of Zero-Sum Linear Quadratic (LQ) games, a cornerstone of control theory. While LQ games can be solved using Riccati equations, this research asks a more fundamental question for modern AI: Can iterative, RL-style policy optimization methods provably find these equilibria?

The Optimization Landscape of LQ Games

The primary obstacle in LQ games is the "nightmare" optimization landscape. Because the objective function is neither globally convex nor concave with respect to the policies, traditional optimization theory does not immediately guarantee that gradient descent-ascent will reach a global optimum.

A central contribution of this work is the characterization of this landscape. The authors prove that despite the lack of convexity/concavity, any stationary point (where the gradients with respect to both players' policies are zero) is a global Nash Equilibrium. This finding is critical because it implies that there are no "bad" local optima to get stuck in, provided the algorithm can successfully navigate to a stationary point.

Proposed Methodology: Nested-Gradient Framework

To achieve stable convergence, the authors move away from simultaneous updates and propose a Nested-Gradient (NG) framework. This approach decomposes the problem into two distinct loops to mitigate the instability caused by non-stationarity:

  1. Inner Loop (Minimizer): For a fixed maximizer policy ($L$), the minimizer ($K$) solves a standard Linear Quadratic Regulator (LQR) problem using policy gradients until convergence.
  2. Outer Loop (Maximizer): The maximizer then updates their policy ($L$) based on the "nested" gradient—the gradient of the objective function calculated under the assumption that the minimizer will always respond optimally.

Within this framework, three algorithmic variants are introduced:

  • Projected Nested-Gradient: Utilizes standard gradient ascent for the outer loop.
  • Projected Natural Nested-Gradient: Employs the natural gradient to better account for the underlying geometry of the policy space.
  • Projected Gauss-Newton Nested-Gradient: An approximate second-order method designed for accelerated convergence.

All three methods include a projection step to ensure that policies remain within the set of "stabilizing" policies, preventing the system state from diverging to infinity during the learning process.

Theoretical and Empirical Results

The paper provides the first global convergence guarantees for policy optimization in this setting. The key theoretical findings include:

  • Global Convergence: All three proposed algorithms are guaranteed to converge to the unique Nash Equilibrium from any initial stabilizing policy.
  • Convergence Rates: The methods exhibit a global sublinear convergence rate of $O(1/t)$, which is consistent with the best-known rates for non-convex optimization. However, once the policies are sufficiently close to the equilibrium, the convergence accelerates to a linear rate (exponential decay of error).
  • Robustness: While the theory relies on specific assumptions and a projection step, synthetic simulations (Case 1 and Case 2) demonstrate that the algorithms are empirically robust. They often converge even when theoretical assumptions are relaxed or when the explicit projection step is omitted.

Conclusion and Future Work

This work serves as a foundational step in understanding policy-based RL for Markov games. By proving that stationary points in LQ games are Nash Equilibria and providing convergent nested-gradient algorithms, the authors bridge the gap between classical control and modern multi-agent RL.

Future research directions include extending these results to general-sum games, where agents are not in direct opposition, and moving beyond the linear-quadratic restriction to accommodate non-linear dynamics. Additionally, while this work focuses on model-based settings, further analysis is needed to provide finite-sample complexity bounds for purely model-free implementations.

Summary updated

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.
BibTeX
@inproceedings{zhang2019policy,
  author = {Kaiqing Zhang and Zhuoran Yang and Tamer Basar},
  title = {{Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=hDfE5yh0yo},
}
Figure