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

1 Introduction

• Policy optimization is used in zero-sum Markov games, but theoretical understanding of these methods—especially in that setting—lags behind.The paper notes that prior policy-optimization work for zero-sum Markov games is empirical without guarantees or limited to tabular settings.Source: §1 · pp. 1–3
• Simultaneous actions make each player’s problem non-stationary, while parametrized policies yield a generally nonconvex-nonconcave search for Nash equilibria.The introduction also notes that vanilla gradient methods may cycle and fail to converge to an equilibrium.Source: §1 · p. 2
• Zero-sum LQ games model linear dynamics controlled by two players with costs quadratic in states and joint actions, and apply to robust and risk-sensitive control.The passage also describes linearization around an operating point as a way to study continuous control with adversarial disturbances or opponents.Source: §1 · p. 2
• Prior LQR policy-gradient convergence results concern a single-player problem, whereas LQ games add nonconcavity for the maximizing player.The paper frames its results as an initial step toward theory for policy-based methods in zero-sum Markov games.Source: §1 · pp. 3–4
• The paper shows that stationary points in the feedback-policy space constitute Nash equilibria, despite the objective’s nonconvexity and nonconcavity.It develops projected nested-gradient methods that converge to equilibria with globally sublinear and locally linear rates.Source: §1 · pp. 3–4

2 Background

• The two players control a linear system and respectively minimize and maximize an infinite-horizon value with quadratic state and joint-control costs.The initial state is drawn from a distribution, and the cost matrices are positive definite.Source: §2 · p. 4
• Assumption 2.1 requires a positive-definite solution to the generalized algebraic Riccati equation with specified matrix inequalities.The first condition is a standard sufficient condition for existence of the game value; the second gives the saddle-point property.Source: §2 · p. 5
• Under the stated conditions, the value exists and the stabilizing feedback-gain pair constitutes the unique Nash equilibrium.The equilibrium gains are given by the Riccati solution, and the paper proposes searching for them in matrix space.Source: §2 · p. 5

3 Policy Gradient and Landscape

• The players’ state-feedback policies use gains K and L, with stabilizing pairs satisfying ρ(A − BK − CL) < 1.The passage identifies the corresponding expected cost as the policy objective.Source: §3 · p. 6
• For a stabilizing pair, the matrix P_K,L is defined by a Lyapunov equation whose terms include the state and control costs and closed-loop dynamics.The equation is P_K,L = Q + K^⊤R_uK − L^⊤R_vL + (A − BK − CL)^⊤P_K,L(A − BK − CL).Source: §3 · p. 6
• The objective is to find the Nash equilibrium by solving a minimax problem over the policy gains.The section identifies Σ_K,L as the state-correlation matrix.Source: §3 · p. 6

L C(K,L) (3.2)

• For some fixed opponent policies, the minimizing player’s problem is nonconvex and the maximizing player’s problem is nonconcave.The paper identifies this nonconvexity-nonconcavity as a challenge for designing equilibrium-seeking algorithms.Source: L C(K,L) (3.2) · p. 6
• A stabilizing pair is an equilibrium if both policy gradients vanish, the state-correlation matrix is full-rank, the specified matrix is invertible, and P_K,L is positive definite.The paper notes that a full-rank state-correlation matrix can be ensured by a non-degenerate initial-state covariance.Source: L C(K,L) (3.2) · p. 7
• Under those conditions, stationary points of the objective characterize the game’s Nash equilibrium rather than merely a surrogate stationary solution.The claim concerns stabilizing control pairs.Source: L C(K,L) (3.2) · pp. 6–7

4 Policy Optimization Algorithms

• The methods solve the maximin problem by finding an inner stationary policy K(L), then updating L with the nested gradient.The paper favors this formulation because projecting L can guarantee stability along outer updates, unlike the direct minimax update considered.Source: §4 · pp. 7–8
• For fixed L, the inner problem is an LQR with equivalent cost matrix Q − L^⊤RvL and state transition matrix A − CL.The stationary point is sought because, under specified conditions, it suffices to be the global optimum.Source: §4 · p. 7
• Inner updates can use policy gradient, natural policy gradient, or Gauss-Newton steps to find the stationary solution K(L).The natural policy gradient uses approximate second-order information; the paper also gives model-free versions of projected policy-gradient and natural-gradient updates, but not Gauss-Newton.Source: §4 · pp. 7–9
• At a converged outer update, inner and outer gradients both vanish, so the resulting control pair is a Nash equilibrium.The inner condition holds by the definition of K(L); the paper uses the outer stationary condition to establish the other condition.Source: §4 · p. 8
• Projection constrains L to a convex, compact set containing the equilibrium, supporting stability without excluding convergence to it.The projection is mainly for theoretical analysis and is not necessarily used in practice; simulations show convergence without it in many cases.Source: §4 · pp. 8–9
• Model-free versions approximate the inner stationary point with zeroth-order optimization before applying projected outer updates.Only projected policy-gradient and natural-policy-gradient updates are converted to model-free versions, since Gauss-Newton cannot be estimated via sampling.Source: §4 · p. 9

5 Convergence Results

• For fixed L, inner policy-gradient updates preserve stability and converge linearly in cost to the inner optimum with a suitable constant stepsize.The inner LQR solution exists with positive-definite P_K(L),L and a stabilizing control pair.Source: §5 · pp. 9–10
• With proper outer stepsizes, all three projected nested-gradient updates converge to the Nash equilibrium at O(1/t), while their control pairs remain stabilizing regardless of outer stepsize.The theorem assumes the stated initial control and game conditions; at each outer iteration, the inner updates converge linearly to K(Lt).Source: §5 · p. 10
• Although these LQ games satisfy a one-sided PŁ condition, their objective's lack of smoothness is identified as a main challenge.For fixed L, the inner problem is an LQR, which supports the one-sided PŁ argument.Source: §5 · p. 10
• Near the Nash equilibrium, all three projected nested-gradient updates converge linearly in both cost value and squared nested-gradient norm.The paper attributes the local rate improvement from global sublinear convergence to the game's PŁ property.Source: §5 · p. 11
• If Assumption 2.1(ii) fails, a projection set of the specified form may not contain the equilibrium, potentially invalidating the local convergence result.The stated global convergence results still hold in the sense of gradient mappings.Source: §5 · p. 11

6.1 Auxiliary Lemmas

• The cost-difference lemma relates changes in value and advantage across stabilizing policies, and a separate lemma characterizes the projected updates’ operator properties.Source: §6.1 · pp. 12–13
• For any L ∈ Ω, the inner Riccati equation has a positive-definite solution, (K(L), L) is stabilizing, and K(L) minimizes cost over K.The proof also bounds P*_L relative to the game solution and bounds W_L for L in Ω.Source: §6.1 · pp. 13–14
• The auxiliary results establish continuity of P*_L in L and continuity of Σ_{K,L} and P_{K,L} in stabilizing gains K and L.Source: §6.1 · p. 14

6.2 Proof of Proposition 5.1

• For Gauss–Newton updates, every stepsize α ∈ [0, 1/2] preserves stability and yields a monotone sequence P_{Kτ,L} ≥ P_{Kτ+1,L} ≥ P_{K(L),L}.The natural policy-gradient stability argument uses a stepsize upper bound 1/∥R_u + B⊤P_{K,L}B∥; gradient updates require a separate stability argument because only cost monotonicity is shown.Source: §6.2 · p. 17

6.3 Proof of Theorem 5.2

• The projected nested updates keep the outer control pairs stabilizing for any stepsize, while their inner-loop updates converge linearly to K(L_t).The proof also introduces a value-difference bound between pairs (K(L), L) and (K(L′), L′) for L, L′ ∈ Ω.Source: §6.3 · p. 17
• The projected Gauss-Newton, projected natural, and projected nested-gradient methods each achieve O(1/t) global convergence.The proof establishes this rate for the corresponding gradient-mapping or iterate sequences.Source: §6.3 · pp. 20, 22, 23, 24, §6.4 · p. 27

6.4 Proof of Theorem 5.3

• The projected Gauss-Newton nested-gradient method has locally linear convergence of both its objective values and squared gradient norms.The proof establishes this rate once the iterates are sufficiently close to the equilibrium and the stepsize meets the stated bound.Source: §6.4 · p. 26
• The projected natural nested-gradient method has locally linear convergence of its objective values and squared gradient norms.The proof derives the rate under a sufficiently small stepsize.Source: §6.4 · p. 27
• The projected nested-gradient method has locally linear convergence of both its objective values and squared gradient norms for a stepsize satisfying the stated conditions.The proof gives a stepsize that guarantees both rates.Source: §6.4 · p. 28

7 Simulation Results

• 0.8739 is the smallest eigenvalue for Case 1, satisfying Assumption 2.1(ii); −0.0011 is the value for Case 2, which fails it.The simulations use these cases to examine convergence with and without Assumption 2.1(ii).Source: §7 · p. 29
• The comparison includes nested-gradient methods, alternating-gradient variants with finitely many inner-loop updates, and simultaneous gradient descent-ascent methods.The alternating-gradient variants do not solve the inner optimization to its exact solution at each outer iteration.Source: §7 · p. 29
• In Case 1, the nested-gradient methods converge globally to the Nash equilibrium, with monotonically increasing cost and linearly converging gradient-mapping norm square.The smallest eigenvalue remains positive along the iterations, so the projection is not effective in this case.Source: §7 · pp. 29–30, Figure 1 · p. 29
• All evaluated policy-optimization methods converge to the Nash equilibrium in Case 2, although their cost sequences are not monotone.Figure 2 shows the NG, AG, and GDA methods, respectively.Source: §7 · pp. 29–30, Figure 2 · p. 30

8 Concluding Remarks

• Projected nested-gradient methods converge to zero-sum LQ-game Nash equilibria with globally sublinear and locally linear rates.Simulations demonstrate convergence properties, including for projection-free algorithms and simultaneous gradient-descent-ascent updates under a relaxed assumption.Source: §8 · p. 30

A Pseudocode for Model-Free Nested-Gradient Algorithms

• Algorithm 1 estimates the inner policy gradient and correlation matrix from sampled trajectories, using zeroth-order perturbations of K.It samples perturbed policies, simulates trajectories, and estimates costs and correlation matrices.Source: A Pseudocode for Model-Free… · p. 37
• The model-free inner loop uses policy-gradient or natural policy-gradient updates; only these two updates among the proposed options are converted to model-free versions.The estimates of the gradient and correlation matrix come from the sampling procedure in Algorithm 1.Source: A Pseudocode for Model-Free… · p. 37, Algorithm 3 Outer-NG: Model-Free… · p. 38

Algorithm 3 Outer-NG: Model-Free Nested-Gradient Algorithms

• The outer loop uses an approximate inner solution from finitely many updates in its projected nested-gradient update, with sampled perturbations of the outer policy.The pseudocode simulates the estimated policy pair and returns the outer iterate after finitely many projected updates.Source: Algorithm 3 Outer-NG: Model-Free… · p. 38

B Supplementary Proofs

• The appendix supplies supplementary proofs for results stated in the paper or used in earlier proofs.Source: B Supplementary Proofs · p. 39

• The assumed stabilizing solution establishes that the game value exists and is uniquely represented by P∗.The proof invokes observability and cited results on the game value and uniqueness of the stabilizing solution.Source: §B.1 · p. 39
• The two control sequences achieve the upper and lower values, so together they form a saddle point and Nash equilibrium.Source: §B.1 · p. 39
• The candidate control pair (K∗, L∗) is stabilizing, and non-stabilizing minimizing-player control sequences have infinite cost under the stated positivity condition.Source: §B.1 · p. 39

B.2 Proof of Lemma 3.1

• For fixed opposing policies, the stabilizing-policy feasible sets are nonconvex, making the minimizing problem nonconvex and the maximizing problem nonconcave.The proof uses a counterexample construction to establish nonconvexity of each stabilizing-policy set.Source: §B.2 · p. 39

B.3 Proof of Lemma 3.2

• The gradient derivation tracks the dependence of the cost expression on K, uses induction for the second equation, and obtains the gradient with respect to L similarly.Source: §B.3 · p. 40

B.4 Proof of Lemma 3.3

• Under the stated assumptions, a stable policy pair satisfying the stationary conditions coincides with the Nash-equilibrium pair.The proof compares the stationary equations with the generalized algebraic Riccati equation and uses uniqueness of its stabilizing solution.Source: §B.4 · p. 40

B.5 Proof of Lemma 4.1

• The set Ω is convex and compact, as shown by a convexity argument and a closed, bounded level-set characterization.Source: §B.5 · p. 41

B.6 Proof of Lemma 6.3

• The proof uses the projected natural nested-gradient operator as its example and states that the other two operator proofs are similar.Source: §B.6 · p. 41

B.7 Proof of Lemma 6.4

• The proof establishes that P∗_L varies continuously with L, using the implicit function theorem to obtain continuous differentiability locally.It argues that the relevant derivative is invertible for L in Ω and applies the theorem around each such L.Source: §B.7 · pp. 42, 44

B.8 Proof of Lemma 6.8

• The proof develops perturbation results for P*_L and K(L), and a bound on an induced operator norm over the compact policy set.The proof assumes Assumption 2.1 throughout.Source: §B.8 · pp. 44, 47, 48

C Simulation Details

• AG and GDA methods are reported to converge to the Nash equilibrium in both simulation settings.The figures track expected cost, gradient-mapping norm square, and the smallest eigenvalue of the modified cost matrix.Source: C Simulation Details · p. 51, Algorithm 5 Gradient-Descent-Ascent… · p. 52

Algorithm 4 Alternating-Gradient (AG) Methods

• AG methods use a finite number of inner-loop updates at each outer iteration rather than solving exactly for K(L_t).Algorithm 4 takes a stabilizing initial policy pair and returns its final iterate.Source: C Simulation Details · p. 51, Algorithm 4 Alternating-Gradient (AG)… · p. 51

Algorithm 5 Gradient-Descent-Ascent (GDA) Methods

• GDA methods update the minimizer by policy-gradient descent and the maximizer by ascent.The simulations show the expected cost converging monotonically toward the NE cost in both Assumption 2.1 settings.Source: Algorithm 5 Gradient-Descent-Ascent… · p. 52, Figure 5 · p. 53, Figure 6 · p. 53