# Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence

arXiv: https://arxiv.org/abs/2309.04272 · HTML: https://mlsanity.com/paper/2309.04272/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 65 references that are in the map.
- First posted on arXiv 8 Sep 2023.

## Builds on (most cited first, 27 of 27)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon](https://mlsanity.com/paper/2011.10300/) (2020)
- [Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergence](https://mlsanity.com/paper/1910.09496/) (2019)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games](https://mlsanity.com/paper/1906.00729/) (2019)
- [Distributed Reinforcement Learning for Decentralized Linear Quadratic Control: A Derivative-Free Policy Optimization Approach](https://mlsanity.com/paper/1912.09135/) (2019)
- [Linear-Quadratic Mean-Field Reinforcement Learning: Convergence of Policy Gradient Methods](https://mlsanity.com/paper/1910.04295/) (2019)
- [Optimizing Static Linear Feedback: Gradient Method](https://mlsanity.com/paper/2004.09875/) (2020)
- [Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games](https://mlsanity.com/paper/2107.13090/) (2021)
- [Learning the Globally Optimal Distributed LQ Regulator](https://mlsanity.com/paper/1912.08774/) (2019)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games](https://mlsanity.com/paper/1907.03712/) (2019)
- [Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Games](https://mlsanity.com/paper/1911.04672/) (2019)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost](https://mlsanity.com/paper/1907.06246/) (2019)
- [Revisiting LQR Control from the Perspective of Receding-Horizon Policy Gradient](https://mlsanity.com/paper/2302.13144/) (2023)
- [Global Convergence of Direct Policy Search for State-Feedback H_∞ Robust Control: A Revisit of Nonsmooth Synthesis with Goldstein Subdifferential](https://mlsanity.com/paper/2210.11577/) (2022)
- [Linear-Quadratic Zero-Sum Mean-Field Type Games: Optimality Conditions and Policy Optimization](https://mlsanity.com/paper/2009.00578/) (2020)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Globally Convergent Policy Gradient Methods for Linear Quadratic Control of Partially Observed Systems](https://mlsanity.com/paper/2211.04051/) (2022)
- [Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulators](https://mlsanity.com/paper/2303.08431/) (2023)
- [First Order Methods For Globally Optimal Distributed Controllers Beyond Quadratic Invariance](https://mlsanity.com/paper/1909.10999/) (2019)
- [Global Convergence of Policy Gradient Algorithms for Indefinite Least Squares Stationary Optimal Control](https://mlsanity.com/paper/2002.05023/) (2020)

## Built on by (most cited first, 4 of 4)

- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Interacting Particle Systems for Fast Linear Quadratic RL](https://mlsanity.com/paper/2406.11057/) (2024)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)

## Abstract (arXiv)

Zero-sum Linear Quadratic (LQ) games are fundamental in optimal control and can be used (i)~as a dynamic game formulation for risk-sensitive or robust control and (ii)~as a benchmark setting for multi-agent reinforcement learning with two competing agents in continuous state-control spaces. In contrast to the well-studied single-agent linear quadratic regulator problem, zero-sum LQ games entail solving a challenging nonconvex-nonconcave min-max problem with an objective function that lacks coercivity. Recently, Zhang et al. showed that an~ε-Nash equilibrium (NE) of finite horizon zero-sum LQ games can be learned via nested model-free Natural Policy Gradient (NPG) algorithms with poly(1/ε) sample complexity. In this work, we propose a simpler nested Zeroth-Order (ZO) algorithm improving sample complexity by several orders of magnitude and guaranteeing convergence of the last iterate. Our main results are two-fold: (i) in the deterministic setting, we establish the first global last-iterate linear convergence result for the nested algorithm that seeks NE of zero-sum LQ games; (ii) in the model-free setting, we establish a~widetildeO(ε-2) sample complexity using a single-point ZO estimator. For our last-iterate convergence results, our analysis leverages the Implicit Regularization (IR) property and a new gradient domination condition for the primal function. Our key improvements in the sample complexity rely on a more sample-efficient nested algorithm design and a finer control of the ZO natural gradient estimation error utilizing the structure endowed by the finite-horizon setting.