  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~$\epsilon$-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/\epsilon)$ 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~$\widetilde{\mathcal{O}}(\epsilon^{-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.
