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

Kaiqing Zhang, Zhuoran Yang, Tamer Basar

Introduction

Reinforcement Learning (RL) has driven some of the most spectacular AI breakthroughs in recent years, mastering complex games like Go and StarCraft II. Much of this success relies on Policy Optimization (PO), a paradigm where agents iteratively update their strategies to maximize rewards. While the theoretical foundations of PO are well-understood for single-agent environments, the mathematics becomes notoriously complex in multi-agent, "zero-sum" games.

In these adversarial settings, one agent’s gain is strictly another’s loss, creating a non-stationary "moving target" problem. Mathematically, this manifests as a non-convex-non-concave saddle-point problem. In such treacherous optimization landscapes, standard gradient-based methods often get stuck, cycle infinitely, or fail to find the Nash Equilibrium (NE)—the stable state where neither player can improve by unilaterally changing their strategy.

This paper bridges a critical theoretical gap by providing the first rigorous guarantee that policy optimization provably converges to the Nash Equilibrium in zero-sum Linear Quadratic (LQ) games, a foundational class of problems in control theory and multi-agent RL.

The Optimization Landscape: A Surprising Discovery

The most significant breakthrough of this work lies in its analysis of the optimization landscape. The authors prove that despite the non-convex and non-concave nature of the policy space in zero-sum LQ games, the landscape possesses a remarkably favorable property: any stationary point of the objective function (where the gradient is zero) constitutes the global Nash Equilibrium.

This "aha moment" provides the theoretical justification for why gradient-based RL algorithms can succeed in these seemingly hostile multi-agent environments.

Methodology: Projected Nested-Gradient Methods

To exploit this landscape, the authors propose three Projected Nested-Gradient (NG) methods:

  1. Projected Nested-Gradient: Utilizes standard gradient updates.
  2. Projected Natural Nested-Gradient: Leverages the underlying geometry of the policy space to find steeper, more efficient descent directions.
  3. Projected Gauss-Newton Nested-Gradient: Incorporates second-order information to accelerate convergence.

The core innovation of these algorithms is their double-loop (nested) structure. The inner loop solves for the minimizing agent's best response—essentially solving a standard Linear Quadratic Regulator (LQR) problem—while the outer loop updates the maximizing agent's strategy. By solving the inner loop to a stationary point, the outer loop faces a much more manageable optimization task, effectively mitigating the inherent non-stationarity of the game.

Additionally, the algorithms employ a projection step onto a convex set ($\Omega$). This ensures that the system remains stable throughout the learning process, preventing the state variables from diverging to infinity.

Key Results and Convergence Guarantees

The authors provide robust theoretical guarantees for their proposed methods, supported by empirical simulations:

  • Global Sublinear Convergence: All three nested-gradient methods are proven to converge to the Nash Equilibrium from any stabilizing initial policy at a sublinear rate of $O(1/t)$.
  • Local Linear Convergence: The authors identify that LQ games satisfy a one-sided Polyak-Łojasiewicz (PŁ) condition. This "secret sauce" allows the algorithms to accelerate to a linear convergence rate (an exponential-like closing of the optimality gap) once the policies enter a local neighborhood of the equilibrium.
  • Empirical Robustness: The algorithms were evaluated in simulated zero-sum LQ game environments. They were tested both under strict theoretical assumptions (Case 1) and in relaxed conditions where a unique NE is not guaranteed (Case 2). The simulations demonstrated robust convergence even in the relaxed scenarios. Interestingly, the projection step—while mathematically necessary for the proofs—was often unneeded in practice, suggesting the algorithms possess a natural stability beyond what the theory strictly requires.

Limitations and Future Directions

While this work marks a vital initial step toward understanding policy-based RL in Markov games, the authors note several avenues for future research:

  • Projection Dependency: The current theoretical proofs rely heavily on the projection operator to guarantee stability. Developing "projection-free" proofs is a crucial next step, as practical RL implementations rarely use such strict constraints.
  • Beyond Zero-Sum: The guarantees are currently limited to strictly zero-sum games. Extending these proofs to general-sum games, where agents may have partially aligned interests, remains a formidable open challenge.
  • Model-Free Implementations: The primary proofs assume exact access to system gradients (model-based). While this lays the groundwork for model-free RL, future work must establish high-probability convergence guarantees for purely sample-based, model-free versions of these nested-gradient algorithms.

Ultimately, this paper demystifies the success of policy optimization in adversarial settings, providing a rigorous mathematical foundation that will guide the design of more stable and efficient multi-agent RL algorithms.

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 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 NE. 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