Source-linked AI summary
Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
Eric Mazumdar, Lillian J. Ratliff, Michael I. Jordan, S. Shankar Sastry
TL;DR
The paper addresses the limited theoretical understanding of policy-gradient in multi-agent settings by analyzing gradient-play in general-sum LQ games. It finds that such games can have Nash equilibria that policy-gradient avoids, with numerical experiments also showing limit cycles.
Problem
The convergence and sample complexity of policy-gradient are understood less in multi-agent settings than in the classic LQR setting, despite the use of these methods in continuous-state and action problems.
Source: §1 · p. 2Method
Results
0% to 25% of randomly sampled LQ games had Nash equilibria that were strict saddle points, and the authors observed limit cycles that can occur even with arbitrarily small step sizes.
Source: §5.2 · p. 10, §6 · p. 13Takeaways & Limitations
Policy-gradient in general-sum LQ games has no guarantee of local convergence to Nash equilibria, even from a small neighborhood of an equilibrium.
Source: §6 · p. 11The analysis directly treats deterministic policy-gradient, although the authors state that the same problems extend to unbiased gradient estimates and actor-critic methods.
Source: §6 · p. 13
Abstract
from arXiv · showhide
We show by counterexample that policy-gradient algorithms have no guarantees of even local convergence to Nash equilibria in continuous action and state space multi-agent settings. To do so, we analyze gradient-play in N-player general-sum linear quadratic games, a classic game setting which is recently emerging as a benchmark in the field of multi-agent learning. In such games the state and action spaces are continuous and global Nash equilibria can be found be solving coupled Ricatti equations. Further, gradient-play in LQ games is equivalent to multi agent policy-gradient. We first show that these games are surprisingly not convex games. Despite this, we are still able to show that the only critical points of the gradient dynamics are global Nash equilibria. We then give sufficient conditions under which policy-gradient will avoid the Nash equilibria, and generate a large number of general-sum linear quadratic games that satisfy these conditions. In such games we empirically observe the players converging to limit cycles for which the time average does not coincide with a Nash equilibrium. The existence of such games indicates that one of the most popular approaches to solving reinforcement learning problems in the classic reinforcement learning setting has no local guarantee of convergence in multi-agent settings. Further, the ease with which we can generate these counterexamples suggests that such situations are not mere edge cases and are in fact quite common.
1. Introduction
The paper addresses the lack of theoretical understanding of policy-gradient methods in multi-agent settings by studying general-sum linear-quadratic games. It shows that policy-gradient can avoid Nash equilibria in such games, despite the benchmark’s tractable structure.
Motivation
- Multi-agent policy-gradient has seen successes in continuous state and action spaces, but its theoretical behavior in multi-agent settings remains poorly understood.LQ games offer a tractable yet sufficiently complex setting for studying these algorithms.Source: §1 · pp. 1–2
- LQ games provide a natural benchmark because global Nash equilibria in linear feedback policies can be found by solving coupled Riccati equations.The games involve multiple agents controlling shared linear dynamics while minimizing separate quadratic costs.Source: §1 · p. 2
Contributions
- Policy-gradient in general-sum LQ games lacks even local convergence guarantees; random initialization can almost surely avoid Nash equilibrium in some games.Numerical experiments indicate such games may be common, and players that fail to converge to Nash equilibria empirically converge to stable limit cycles.Source: §1 · p. 2
Motivation
- The paper situates its result as a new example of non-convergence and cycling in multi-agent reinforcement learning with continuous state and action spaces.The authors connect a better theoretical understanding of these behaviors to developing more efficient and theoretically sound multi-agent learning algorithms.Source: §1 · pp. 2–3
2. Preliminaries
The paper studies discrete-time N-player LQ games in which players use linear feedback policies and simultaneously descend their own costs’ gradients. The setup assumes positive-definite state and control costs and conditions that support stabilization and Nash-equilibrium analysis.
Game setup
- Each player uses a linear feedback policy, ui(t) = −Ki z(t), to minimize a quadratic loss in the shared dynamical system.Under suitable cost assumptions, Nash equilibria in linear policies exist when the coupled Riccati equations have a solution, though uniqueness is not generally assured.Source: §2 · pp. 3–4
- For each player, the loss is quadratic in state and control, with Qi and Ri denoting the respective cost matrices.The players’ objectives are distinct, so the best they can hope to achieve is a Nash equilibrium.Source: §2 · pp. 3–4
Assumptions
- The model assumes positive-definite state and control cost matrices, and at least one player’s dynamics pair is stabilizable.Finite player costs require the closed-loop system to be asymptotically stable.Source: §2 · pp. 3–4
Policy-gradient dynamics
- Players randomly initialize strategies and simultaneously perform gradient descent on their individual costs with respect to their control inputs.The update uses each player’s own cost gradient and step size; n indexes policy-gradient iterations, while t indexes system time.Source: §2 · p. 3
3. Analyzing the Optimization Landscape of LQ Games
The section establishes that general-sum LQ games are not convex, yet their gradient dynamics have no critical points other than Nash equilibria. It then develops the setting for showing that policy-gradient can nevertheless avoid Nash equilibria.
Non-convexity
- There are N-player LQ games satisfying the stated assumptions that are not convex games.The proof uses the non-convexity of the stabilizing-policy set in single-agent LQR: fixing other players’ actions leaves a player facing an LQR problem.Source: §3 · p. 5
Critical points and Nash equilibria
- In general-sum LQ games, a strategy collection is a critical point of policy-gradient dynamics if and only if it is a Nash equilibrium.This result holds despite the games’ lack of convexity; it rules out non-Nash critical points, not non-convergent trajectories.Source: §3 · p. 5
- When the coupled Riccati equations have a unique solution and the stated assumptions hold, a full-rank initial-state covariance yields a unique critical point.The section notes that the covariance condition can be met by choosing a full-rank initial-state distribution.Source: §3 · p. 6
Avoiding Nash equilibria
- The section seeks sufficient conditions for avoiding Nash equilibria by identifying games where gradient-play diverges from neighborhoods of equilibria.The LQ setting does not satisfy the smoothness assumptions needed to directly invoke the cited general-game result, and costs are infinite for destabilizing strategies.Source: §3 · p. 6
- Even with arbitrarily small step sizes, policy-gradient in LQ games may diverge from neighborhoods of a Nash equilibrium.The stabilizing-policy set is non-convex, and the costs are non-smooth and infinite when strategies fail to stabilize the dynamics.Source: §3 · p. 6
4. Sufficient Conditions for Policy-Gradient to Avoids Nash
The section gives sufficient conditions under which policy-gradient avoids Nash equilibria in general-sum LQ games. If an equilibrium is a saddle point with Jacobian eigenvalues having both negative and positive real parts, convergence within a neighborhood occurs only from a measure-zero set of initializations.
Sufficient conditions
- With Σ0 > 0 and Assumptions 1 and 2, if a Nash equilibrium has Jacobian eigenvalues with both negative and positive real parts, policy-gradient converges only on a measure-zero set in some neighborhood.The equilibrium must be a saddle point of the policy-gradient dynamics.Source: §4 · p. 7
Proof
- The proof combines local smoothness of the policy-gradient vector field, a diffeomorphic update map, and the stable manifold theorem to establish the measure-zero convergence result.The vector field is twice continuously differentiable on the set of stabilizing policies.Source: §4 · p. 7
Random initialization
- When each player's random initial strategy distribution has support in the neighborhood, the players almost surely avoid a saddle-point Nash equilibrium.The result follows because the initializations that converge to the equilibrium form a measure-zero set there.Source: §4 · p. 8
Implications
- These sufficient conditions show that general-sum LQ games lack local convergence guarantees, unlike the cited single-player LQR and zero-sum LQ settings.The paper states that the theoretical and numerical results imply no local, and consequently no global, convergence guarantee for general-sum LQ games.Source: §4 · p. 9
5. Generating Counterexamples
The authors search randomly generated LQ games for Nash equilibria that policy-gradient avoids, then test the resulting games numerically. Across tested parameter values, such games occur in up to 25% of samples, and policy-gradient trajectories can approach limit cycles whose time-averaged outcomes do not match Nash.
5.1 Experimental setup
- The search fixes B1, Q1, and R1, varies B2, Q2, and R2 through b, q, and r, and samples 1000 dynamics matrices A for each parameter setting.For each game, the authors find an equilibrium by Lyapunov iterations and numerically approximate the gradient-dynamics Jacobian to check whether the equilibrium is a strict saddle.Source: §5.1 · p. 9, §5 · p. 9
5.2 Numerical results
- Up to 25% of sampled LQ games had Nash equilibria that are strict saddle points of the gradient dynamics; with b = 0, at least 5% did so for every tested q and r.Figure 1 summarizes frequencies across the parameter sweeps; near r = 0.35, b = 0, and q = 0.01, about 250 of 1000 sampled games were counterexamples.Source: §5.2 · p. 10, Figure 1 · p. 10
- No counterexamples were found when b varied in (−0.5, 0.5) with q = 0.01 and r = 0.1, suggesting that stronger convergence guarantees may depend on system structure.Source: §5.2 · p. 10
- In two generated counterexample games, players initialized near Nash and using step size 0.05 diverged from it and converged to limit cycles.The players’ time-averaged strategies and, in some cases, average payoffs did not converge to their Nash values.Source: §5.2 · pp. 10–11, Figure 2 · p. 11
6. Discussion
In N-player LQ games, policy-gradient has no guarantee of local convergence to Nash, even from policies initialized near equilibrium. The experiments show limit cycles, while the authors argue these findings motivate caution and further work on game-theoretic approaches.
6. Discussion
- Policy-gradient in N-player LQ games has no guarantee of local, and therefore global, convergence to Nash—even when initial policies are randomly drawn near equilibrium.Because Nash equilibria are the only critical points of the gradient dynamics, the authors say these algorithms may not converge to any set of stationary policies in this game class.Source: §6 · p. 11
- In the illustrated games, players converge to the same cycle from different initializations, and their time-average strategies do not converge to Nash.The figures show parameter trajectories with time represented by progressive darkening.Source: Figure 3 · p. 12, Figure 4 · p. 12
- The analysis covers deterministic policy-gradient, while the authors say the findings extend to unbiased gradient estimates and actor-critic methods tracking the same limiting continuous-time dynamics.The authors believe non-convergence issues are likely to appear in more complex settings with more complex dynamics and policy parameterizations.Source: §6 · pp. 12–13
- The reported limit cycles can occur even with arbitrarily small step sizes, and the time average of players’ strategies does not coincide with Nash.The authors note there is no obvious link between these cycles and the Nash equilibrium, and suggest the equilibrium’s saddle-point character may be relevant; they say this warrants further investigation.Source: §6 · p. 13
- The authors suggest that policy-gradient algorithms could be improved by leveraging underlying game-theoretic structure.They frame this as a need for methods that retain policy-gradient’s scalability and ease of implementation while offering convergence guarantees and performance in competitive settings.Source: §6 · p. 13
Appendix A. Proofs of Auxiliary Results
The auxiliary proof establishes that the map ω is twice continuously differentiable on its stated domain. It does so by showing that the covariance matrix ΣK and the Bellman-equation solutions Pi vary continuously differentiably with stabilizing policies.
Appendix A. Proofs of Auxiliary Results
- Proposition 5 establishes that the map ω is twice continuously differentiable on Smd.The proof reduces this regularity claim to the regularity of ΣK and each Pi with respect to the policy matrices.Source: Appendix A · p. 13
- For stabilizing policy matrices, ΣK is defined as the unique solution of a discrete-time Lyapunov equation.The proof vectorizes the equation and defines F so that F implicitly defines ΣK.Source: Appendix A · pp. 13–14
- The implicit function theorem yields continuous differentiability of ΣK and each Pi with respect to the policy matrices.For stabilizing policies, the relevant matrix is an isomorphism because the spectrum of the closed-loop matrix lies inside the unit circle; the proof for Pi is analogous.Source: Appendix A · p. 14
Appendix B. Additional Mathematical Preliminaries and Results
The stable manifold theorem is used to analyze avoidance of saddle-point equilibria in the dynamics. It associates a local stable-center manifold with the stable and center eigenspaces of a fixed point.
Appendix B. Additional Mathematical Preliminaries and Results
- The stable manifold theorem is used to show avoidance of saddle-point equilibria of the dynamics.It associates a local invariant stable-center manifold with the stable and center eigenspaces; the stated result says points whose forward iterates stay in a neighborhood belong to that manifold.Source: Appendix B · p. 14