PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Games

Jingjing Bu, Lillian J. Ratliff, Mehran Mesbahi

arXiv:1911.04672v1eess.SYcs.SYmath.OC

TL;DR

Undiscounted LQ games with potentially unbounded per-stage costs make sequential policy optimization intricate, including the need to keep iterates stabilizing. The paper proposes leader-follower policy algorithms and shows global convergence rates, while clarifying stabilization and indefinite-cost issues.

  • Problem

    Sequential policy optimization for LQ games is challenging because the undiscounted cost may be unbounded per stage and policy iterates must remain in the open set of stabilizing policies.

    Source: §1 · p. 2

  • Method

    The paper proposes sequential leader-follower algorithms in which the leader uses natural-gradient or quasi-Newton updates and the follower may use any first-order-based policy.

    Source: §1 · p. 2

  • Results

    Natural-gradient leadership yields global sublinear and asymptotic linear convergence, while quasi-Newton leadership yields global quadratic convergence to the Nash equilibrium.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis clarifies stabilization and indefinite-cost issues while removing restrictive assumptions and circumventing projection steps.

    Source: §10 · p. 24

    For gradient policy, the analysis lacks a guarantee that updates decrease the value matrix in positive-semidefinite order; its stated remedy assumes the equilibrium follower policy lies in Ω and the corresponding system pair is stabilizable.

    Source: §8 · p. 22

Abstract

from arXiv · show

We propose projection-free sequential algorithms for linear-quadratic dynamics games. These policy gradient based algorithms are akin to Stackelberg leadership model and can be extended to model-free settings. We show that if the leader performs natural gradient descent/ascent, then the proposed algorithm has a global sublinear convergence to the Nash equilibrium. Moreover, if the leader adopts a quasi-Newton policy, the algorithm enjoys a global quadratic convergence. Along the way, we examine and clarify the intricacies of adopting sequential policy updates for LQ games, namely, issues pertaining to stabilization, indefinite cost structure, and circumventing projection steps.

1 Introduction

Sequential policy updates for zero-sum LQ games are difficult because costs may be undiscounted and unbounded per stage, and iterates must remain stabilizing. The paper proposes leader-follower algorithms with convergence guarantees while addressing assumptions, stabilization, and indefinite costs.

1 Introduction

  • A prior sequential direct-policy approach for LQ games used assumptions and a projection step, while undiscounted, potentially unbounded stage costs make policy optimization more intricate than standard LQR.Iterates must jointly remain in the open set of stabilizing policies to prevent the simulator from diverging.Source: §1 · p. 2
  • Natural-gradient leadership gives global sublinear and asymptotic linear convergence, while quasi-Newton leadership gives global quadratic convergence for the proposed leader-follower algorithms.The leader can be either player when the algorithm is initialized appropriately; the follower may use any first-order-based policy.Source: §1 · p. 2
  • Gradient, natural-gradient, and quasi-Newton policies converge globally at linear, linear, and quadratic rates, respectively, even when the state-cost matrix Q is indefinite.This extends standard-LQR results whose analysis assumes Q ≻ 0; the paper notes that this condition is stronger than standard LQR requirements.Source: §1 · p. 2
  • The algorithms remove a nonstandard assumption that the Nash equilibrium satisfies Q − L*ᵀR₂L* ≻ 0, which prior convergence analysis relied on.The earlier analysis also required a priori knowledge of a positive ε defining a set of follower policies.Source: §1 · p. 3
  • The approach permits larger policy-iteration step sizes by analyzing stabilizing policy updates through the corresponding indefinite GARE.Source: §1 · p. 3
  • The convergence analysis clarifies how stabilizability and detectability relate to iterative algorithms for decision problems with embedded dynamics.Source: §1 · p. 3
  • The quasi-Newton policy achieves global quadratic convergence for LQ dynamic games and, to the authors’ knowledge, is the first iterative approach with that rate for discrete-time GARE.The authors note that the GARE result may be independently interesting, including for data-driven settings.Source: §1 · p. 3
  • Either player may be the leader, unlike [ZYB19], which requires the cost-maximizing player to lead.Source: §1 · p. 3

2 Notation and Background

This section sets notation and recalls Riccati and stability results used to analyze LQ control and games. It also highlights how indefinite state costs change the relevant Riccati existence conditions.

2 Notation and Background

  • Positive-semidefinite matrix ordering is denoted by ≺, ⪯, ≻, and ⪰, while stabilizability means some feedback makes A − BK Schur and detectability is defined through the transposed pair.A matrix is Schur when all eigenvalues lie inside the open unit disk; a stabilizing feedback produces a Schur closed-loop matrix.Source: §2 · p. 3
  • For standard LQR, Q ⪰ 0, R ≻ 0, stabilizability, and observability of the relevant spectrum yield a unique maximal DARE solution and a stabilizing optimal feedback.The feedback is characterized by K* = (R + BᵀX+B)⁻¹BᵀX+A.Source: §2 · p. 4
  • The section defines stabilizing and almost-stabilizing Riccati solutions through their feedback gains, and names the parameter-dependent Riccati operator used as gains change.A stabilizing gain is Schur; an almost-stabilizing gain is marginally stabilizing.Source: §2 · pp. 3–4
  • With indefinite Q, existence results instead use stabilizability, invertible symmetric R, and a symmetric solution to a matrix inequality, yielding a maximal solution with R + BᵀX+B ≻ 0.The associated closed-loop eigenvalues lie in the closed unit disk.Source: §2 · p. 4

3 LQ Dynamic Games and some of its Analytic Properties

This section establishes the zero-sum LQ game setup and examines stabilization and analytic properties relevant to sequential policy updates, including an assumption and its implications for stabilizing Nash equilibria. It also considers whether a marginally stable policy pair can solve (5), comparing its solution with that at (K*, L*).

3.1 Zero-sum LQ Dynamic Games

  • The game uses static linear feedback policies over stabilizing gain pairs; player 1 minimizes the quadratic cost and player 2 maximizes it.The cost can remain finite at the stability boundary, so its value is not always a reliable indicator of stability.Source: §3.1 · pp. 5, 7
  • Nash comparisons require stabilizing action pairs, but stabilizing deviations in each player’s projected strategy set do not guarantee that every cross-pair is stabilizing.With indefinite costs, the value may also remain finite for unstable dynamics, complicating stability assessment.Source: §3.1 · pp. 6–7
  • To make equilibrium evaluation independent of initial state, the paper defines a value over a spanning set of initial conditions or a full-rank-covariance sample.This formulation is described as necessary in general for the cost functions to be well defined.Source: §3.1 · p. 6

3.2 Stabilizing Policies in Sequential Zero-Sum LQ Games

  • Sequential play restricts both players to stabilizing-policy projections because player 2 may favor divergence and indefinite costs can place player 1’s best response outside its projection.The paper proposes sequential algorithms that maintain this condition without projection steps.Source: §3.2 · p. 7

3.3 Analytic Properties of the Cost Function

  • The stabilizing-pair set is open and contractible but generally nonconvex, while the value function is real analytic on that set.The cost’s smoothness supports gradient characterization, and its positive-definite matrix Y defines a Riemannian metric for natural gradients.Source: §3.3 · pp. 8–9

3.4 A Key Assumption and its Implications

  • The definiteness conditions are used to extract unique policies from the optimal value matrix and correspond to quasi-Newton directions in the convergence analysis.Condition (a1) designates player L as leader, whereas condition (a2) designates player K.Source: §3.4 · pp. 9–10
  • Under Assumption 1, the system is stabilizable, X* is symmetric and solves the GARE, and X* is unique among almost stabilizing solutions.The assumption requires a stabilizing Nash equilibrium and at least one of two definiteness conditions on the equilibrium value matrix. X* need not be positive semidefinite.Source: §3.4 · pp. 9–10
  • To rule out a boundary solution of (5), the argument compares it with (K*,L*) and derives X*=X from invertibility of K,L ⊗ A*.The boundary pair satisfies ρ(A − B1K − B2L) = 1.Source: §3.4 · p. 10
  • The boundary closed-loop matrix is marginally stable, while A* is stable.Source: §3.4 · p. 10

4 Oracle Models for Sequential LQ Games

The section specifies sequential oracle assumptions for LQ games: the leader can minimize the cost against a fixed follower policy, while the follower uses first-order information. It motivates this asymmetry through the value function for a greedy adversary and updates designed to stay in the follower’s policy domain without projection.

4.1 Motivation

  • Because the objective is generally not convex-concave, identical greedy first-order oracles provide no theoretical guarantee of convergence to Nash equilibrium.The proposed setup assumes the leader can access the minimizer oracle, while the follower can use first-order information.Source: §4 · pp. 10–11

4 Oracle Models for Sequential LQ Games

  • The leader’s oracle returns a cost minimizer for a fixed follower policy; repeated gradient, natural-gradient, or quasi-Newton steps can construct this oracle.The players query their oracles sequentially, with the other player’s policy held fixed during each query.Source: §4 · pp. 10–11

4.1 Motivation

  • The follower’s value function g(L) need not be continuous on its policy domain, but it is differentiable where the leader’s minimizer exists and is unique.A variant of Danskin’s theorem supports this differentiability result despite the leader’s noncompact, policy-dependent feasible set [BR95].Source: §4.1 · p. 11
  • The set {L ∈ dom(g): Q − LᵀR₂L ≻ 0} is contained in the region where g is differentiable, supporting an ascent update under a Lipschitz assumption.The proposed update rules keep follower iterates in Sπ₂ without projection, exploiting the problem structure because the set is nonconvex and not fully described.Source: §4.1 · pp. 11–12

5 Algorithm: Natural Gradient Policy on L

The natural-gradient algorithm updates player L while an oracle selects player K’s stabilizing minimizer; its analysis establishes stabilization and global sublinear convergence under an appropriate initialization and stepsize.

5.1 Algorithm

  • Algorithm 1 initializes L0 to make (A − B1L0, B2) stabilizable and uses an oracle for K’s stabilizing minimizer at each fixed L.Initialization is generally nontrivial; under additional stabilizability, cost, and detectability assumptions, L0 can be chosen as zero.Source: §5.1 · pp. 12–13, §5 · p. 12

5.2 Convergence Analysis

  • With appropriate initialization and stepsizes, each iterate has a unique stabilizing minimizer Kj, and the corresponding pair (Kj,Lj) is stabilizing.The analysis also states that the value matrix at the Nash equilibrium gives local strong convexity of −g(L), supporting a local linear rate for gradient descent.Source: §5.2 · pp. 15, 18
  • An induction argument removes the provisional stabilizability assumption by deriving a contradiction if an iterate loses stabilizability.The proof uses synthesis results that require stabilizability, then establishes that property for the iterates.Source: §5.2 · pp. 15, 17
  • With stepsize ηj = 1/(2λn(Oj−1)), the natural-gradient sequence converges sublinearly to the global maximum, the Nash equilibrium.The theorem also indicates that the gradient vanishes at a sublinear rate.Source: §5.2 · p. 17

6 Algorithm: quasi-Newton Iterations of L

The quasi-Newton policy for L is motivated by a second-order local approximation of g(L). Its convergence analysis establishes bounded monotone value-matrix iterates that converge to the Nash-equilibrium value matrix.

6 Algorithm: quasi-Newton Iterations of L

  • The quasi-Newton policy uses an oracle returning a quasi-Newton direction for L, motivated by a second-order local approximation of g(L).Algorithm 2 requires an appropriately initialized stabilizing pair.Source: §6 · p. 18

6.1 Convergence Analysis

  • With appropriate initialization and stepsizes, each L iterate has a unique minimizing Kj that forms a stabilizing pair (Kj,Lj).The analysis adapts the natural-gradient argument to a Riccati map with the quasi-Newton update.Source: §6.1 · pp. 18–19
  • The value matrices Xj are monotonically nondecreasing and bounded above, and therefore converge to X∗.The analysis uses compactness of the sequence together with a Lipschitz bound to establish the stated convergence rate.Source: §6.1 · p. 19

7 Policy Gradient Algorithms for Solving K ←arg minK f(K,L)

For fixed L, policy-gradient methods must handle a possibly indefinite state cost and cannot rely on coercivity. The paper analyzes stability-preserving updates and reports linear convergence for gradient and natural-gradient methods and quadratic convergence for quasi-Newton iterations.

7 Policy Gradient Algorithms for Solving K ←arg minK f(K,L)

  • Gradient descent, natural-gradient descent, and quasi-Newton iterations converge to the maximal ARE solution at linear, linear, and quadratic rates, respectively, when a maximal stabilizing solution exists.The result concerns the fixed-L problem.Source: §7 · pp. 20, 22
  • Natural-gradient descent converges globally and linearly to the maximal fixed-L ARE solution when that solution is stabilizing.The result does not assume Q is positive definite, although Q − LᵀR2L may be indefinite.Source: §7 · p. 20
  • The sequential game can make Q − LjᵀR2Lj indefinite, so the fixed-L cost is not coercive and iterate stability requires separate analysis.The proof establishes stability of natural-gradient iterates before applying the one-step progression argument; the stability reasoning extends to quasi-Newton iterations.Source: §7 · pp. 20–21
  • The quasi-Newton sequence has a quadratic convergence rate when the fixed-L algebraic Riccati equation has a maximal stabilizing solution.The stability argument for the natural-gradient sequence also applies to quasi-Newton iterations.Source: §7 · p. 21

8 Comments on Adopting Gradient Polices for L

Projecting L onto Ω does not ensure that (A − B2L,B1) is stabilizable, so projection alone cannot guarantee the condition needed by the sequential method.

8 Comments on Adopting Gradient Polices for L

  • Membership in Ω does not guarantee that (A − B2L,B1) is stabilizable, which is the key issue for the proposed approach.The cited projection method uses Ω = {L : Q − LᵀR2L ⪰ 0} to seek stabilizing policies.Source: §8 · p. 22
  • The proposed convergence approach relies on monotonicity of the value matrix, whereas gradient policy updates only guarantee cost decrease.The passage says those gradient updates do not guarantee a decrease in the value matrix under the positive-semidefinite ordering.Source: §8 · p. 22
  • If the Nash-equilibrium L∗ lies in Ω and every iterate remains stabilizable, the approach would give a simpler convergence proof for gradient policies.Source: §8 · p. 22

9 Switching the Leader in the Sequential Algorithms

The section switches the sequential-game leader to player K and develops the corresponding value-function and convergence analysis. Under the stated uniqueness and stability conditions, it gives differentiability and stabilization results for the switched updates.

9 Switching the Leader in the Sequential Algorithms

  • On an open set where each K has a unique maximizer of f(K,L), the value function h is differentiable and its gradient is given by the proposition.The supplied passage does not include the gradient formula.Source: §9 · p. 23
  • For fixed K′, a unique stabilizing maximizer L′ of f(K′,L) satisfies an algebraic Riccati equation after the first-order condition is substituted into the Lyapunov equation.Source: §9 · p. 23
  • The switched update analysis concludes that (Kj,Lj) is a stabilizing pair under the stated stabilizability and unique-maximizer conditions.The assumptions specify that (A − B1Kj, B2) is stabilizable and f(Kj,L) is bounded above over L.Source: §9 · p. 23
  • Algorithm 3’s natural-gradient policy for player K has a sublinear convergence rate.The section also introduces a value function for the player-K leader.Source: §9 · pp. 22–24

10 Concluding Remarks

The concluding remarks summarize global convergence results for mixed-policy algorithms and clarify stabilization, indefinite-cost, and projection issues. The Hessian analysis derives local strong convexity of −g under condition (a1).

10 Concluding Remarks

  • The paper reports global convergence of several mixed-policy algorithms and clarifies stabilization, indefinite-cost, and projection-step issues in LQ games.Source: §10 · p. 24

A Hessian of g(L)

  • The Hessian analysis assumes a unique stabilizing minimizer of f(K,L0) and derives the local curvature of g(L) around L0.The setup denotes the corresponding closed-loop matrix by A0 = A − B1K0 − B2L0.Source: A Hessian of g(L) · p. 25

B GRADIENT POLICY ANALYSIS FOR NONSTANDARD LQR

The analysis addresses gradient-policy stepsizes for nonstandard LQR, where an indefinite cost term prevents estimating needed quantities from current function values. It uses perturbation bounds and stability arguments to establish local curvature and stepsize conditions.

B GRADIENT POLICY ANALYSIS FOR NONSTANDARD LQR

B Gradient Policy Analysis for Nonstandard LQR

C A USEFUL CONTROL THEORETIC OBSERVATION

The control-theoretic observation supports stepsize selection by combining a bound on φ with a stabilizability-set openness result. The analysis establishes that the set of gains yielding a stabilizable pair is open.

C A USEFUL CONTROL THEORETIC OBSERVATION

C A Useful Control Theoretic Observation

Loading 1911.04672v1…