PaperlayerView exact revision on arXiv

Source-linked AI summary

On Gradient-Based Learning in Continuous Games

Eric Mazumdar, Lillian J. Ratliff, S. Shankar Sastry

arXiv:1804.05464v3cs.LGstat.ML

TL;DR

Competitive gradient-based learning is difficult to characterize in continuous games because its coupled dynamics need not be gradient flows. The paper develops a general dynamical-systems framework to analyze these algorithms, showing that some Nash equilibria are almost surely avoided while non-Nash attractors can occur. Empirical results further show that 0%–25% of sampled linear quadratic games can contain global Nash equilibria that are strict saddle points of the gradient dynamics.

  • Problem

    The limiting behavior of widely used gradient-based learning algorithms in general continuous games remains insufficiently understood, including whether learning attractors and game-relevant equilibria coincide.

  • Method

    The paper formulates a broad framework for competitive gradient-based learning and analyzes its deterministic and stochastic continuous-time dynamics using dynamical systems theory.

  • Results

    0%–25% of randomly sampled linear quadratic games had a global Nash equilibrium that was a strict saddle point of the gradient dynamics, with at least 5% for every tested parameter configuration.

  • Takeaways & Limitations

    Gradient-based learning can avoid a non-negligible subset of Nash equilibria and converge to attracting non-Nash strategies that may arise solely from the algorithm.

  • Takeaways & Limitations

    Gradient-play can exhibit other limiting behaviors, such as limit cycles, that are not addressed by the stated convergence result.

Abstract

from arXiv · show

We formulate a general framework for competitive gradient-based learning that encompasses a wide breadth of multi-agent learning algorithms, and analyze the limiting behavior of competitive gradient-based learning algorithms using dynamical systems theory. For both general-sum and potential games, we characterize a non-negligible subset of the local Nash equilibria that will be avoided if each agent employs a gradient-based learning algorithm. We also shed light on the issue of convergence to non-Nash strategies in general- and zero-sum games, which may have no relevance to the underlying game, and arise solely due to the choice of algorithm. The existence and frequency of such strategies may explain some of the difficulties encountered when using gradient descent in zero-sum games as, e.g., in the training of generative adversarial networks. To reinforce the theoretical contributions, we provide empirical results that highlight the frequency of linear quadratic dynamic games (a benchmark for multi-agent reinforcement learning) that admit global Nash equilibria that are almost surely avoided by policy gradient.

1. Introduction

The paper studies limiting behaviors of competitive gradient-based learning in continuous games, where the coupled dynamics need not be gradient flows. It shows that learning can approach non-Nash attractors, avoid some Nash equilibria, and exhibit nontrivial limiting behavior.

  • Motivation: Gradient-based learning in general continuous games remains insufficiently understood despite its widespread use in multi-agent settings.The paper frames this gap through the questions of whether learning attractors are game-relevant equilibria and whether relevant equilibria attract learning dynamics.
  • Approach: The framework analyzes competitive gradient-based algorithms through continuous-time dynamical systems, covering deterministic and stochastic learning settings.This approach leverages dynamical systems theory and stochastic approximation to study limiting behavior.
  • Key dynamical distinction: Unlike single-agent gradient flows, coupled game dynamics can admit periodic orbits and other nontrivial limiting behaviors.The difference arises because the combined dynamics of players’ gradients do not necessarily form a gradient flow.
  • Main contributions: The analysis constructs general-sum and zero-sum games with attracting non-Nash equilibria that can be artifacts of the players’ algorithms.At such points, at least one player has a unilateral direction that would decrease its cost.
  • Main contributions: Gradient-based learning almost surely avoids a subset of local Nash equilibria in general-sum and potential games.The result applies in both full-information settings with random initialization and partial-information settings with unbiased gradient estimates.
  • Conclusions: The paper gives negative answers to both equilibrium-attractor questions for n-player general-sum games and identifies related nuances in zero-sum and potential games.It also establishes that a nontrivial set of games admits Nash equilibria almost surely avoided by gradient-play.

2. Preliminaries

The paper models continuous games through agents’ individual strategy spaces and cost functions, then studies simultaneous deterministic or stochastic gradient-based updates. It relates the resulting learning dynamics to local Nash equilibria and their limiting behavior.

  • Game model: Each agent has a finite-dimensional strategy space and a cost function depending on its own action and the other agents’ actions.The joint strategy space is the Cartesian product of the agents’ individual spaces.
  • Learning dynamics: Agents update their strategies simultaneously using gradient-based learning algorithms with agent-specific step sizes.The update rule is parameterized by γ_i,t, the step size for agent i at iteration t.
  • Learning settings: The analysis considers deterministic learning with oracle gradients and stochastic learning with unbiased gradient estimators.The stochastic estimator adds a zero-mean, finite-variance noise process to each agent’s gradient.
  • Analysis target: The paper studies the limiting behavior of the agents’ strategies under these gradient-based algorithms using Nash-equilibrium concepts.It distinguishes deterministic and stochastic gradient-based learning before introducing local Nash equilibria.
  • Equilibrium notion: Local Nash equilibria are defined by each agent locally minimizing its cost while the other agents’ actions remain fixed.Strict local Nash equilibria require the corresponding local inequalities to be strict.
  • Scope: Because the cost functions have limited structural assumptions, the game may have one, many, or no local or global Nash equilibria.When each local neighborhood equals the full strategy space, a local Nash equilibrium is global.

3. Linking Games and Dynamical Systems

The paper links game-theoretic equilibria to the stability properties of gradient dynamics, showing that these relationships differ across general-sum, zero-sum, and potential games. It also identifies attracting non-Nash equilibria and Nash equilibria that gradient-based learning almost surely avoids.

  • General framework: Gradient-based learning is analyzed through the continuous-time dynamics ˙x = −ω(x), connecting stationary points and their stability to game-theoretic equilibrium notions.Stationary points satisfy ω(x)=0, and the Jacobian of ω characterizes stability under the dynamics.
  • General framework: NDDNE(G) ⊂ SSP(ω) ∪ LASE(ω): every non-degenerate differential Nash equilibrium is either a strict saddle or locally asymptotically stable.This classification underlies the paper’s analysis of which Nash equilibria attract or repel gradient-based trajectories.
  • General-sum games: In general-sum games, a continuum of games admits locally asymptotically stable equilibria that are neither differential Nash nor local Nash equilibria.These attracting critical points can therefore be non-Nash and potentially irrelevant to the underlying game.
  • Zero-sum games: In zero-sum games, every differential Nash equilibrium is locally asymptotically stable, yet a continuum of games also has locally asymptotically stable equilibria that are not Nash.Thus all local Nash equilibria attract under gradient dynamics, while some additional attracting equilibria are non-Nash.
  • Potential games: In potential games, every locally asymptotically stable equilibrium is a non-degenerate differential Nash equilibrium, but some local Nash equilibria are strict saddles of the dynamics.Therefore, potential games exclude attracting non-Nash equilibria while still permitting Nash equilibria that gradient-based learning avoids.
  • Avoidance: Local Nash equilibria that are also strict saddles are almost surely avoided by gradient-based algorithms in deterministic and stochastic settings.Such equilibria exist in both potential and general-sum games, ruling out a positive answer to Q1 for those classes.

4. Convergence of Gradient-Based Learning

The analysis characterizes when deterministic and stochastic competitive gradient-based learning avoids strict saddles and unstable cycles, including Nash equilibria that are dynamically unstable. It also identifies convergence guarantees in potential games alongside non-Nash limiting behavior and broader game classes with restricted attractors.

  • Deterministic setting: Competitive gradient-based learning converges to strict saddle points only from a measure-zero set of initial conditions under the stated deterministic assumptions.The result applies when g(X) ⊂ X and includes oracle-gradient learning.
  • Deterministic setting: Local Nash equilibria can be strict saddles of the gradient dynamics, so gradient-play almost surely avoids a subset of Nash equilibria, including some global equilibria in linear quadratic dynamic games.This avoidance persists with random initialization in arbitrarily small neighborhoods and may cause policy-gradient failure in sampled LQ games.
  • Potential games: In potential games, competitive gradient-based learning converges almost surely to non-degenerate differential Nash equilibria that are generically local Nash equilibria.The converged equilibrium is also a local minimizer of the potential function, even though agents need not know or optimize that potential directly.
  • Potential games: Gradient-play in potential games cannot exhibit limit cycles or chaos, although it still avoids a subset of the games’ Nash equilibria.Avoiding strict-saddle Nash equilibria can instead lead to local minimizers of the potential, which are local Nash equilibria.
  • General- and zero-sum games: In zero-sum and general-sum games, convergence to a critical point implies local asymptotic stability, but such stable limiting points can be non-Nash.Thus, the dynamics may converge to strategies that are unrelated to game equilibria.
  • Stochastic setting: Stochastic competitive gradient-based learning preserves the deterministic saddle-avoidance result and avoids linearly unstable limit cycles on measure-zero sets under analogous assumptions.The stochastic framework covers multiple common multi-agent learning algorithms, while the limit-cycle guarantees require additional formalism.
  • Further convergence results: Morse-Smale games restrict learning to linearly stable cycles or equilibria, but players may still converge to non-Nash equilibria and avoid some Nash equilibria.This class generalizes potential games through Morse-Smale combined gradient dynamics.

5. Saddle Point LNE in LQ Dynamic Games

The paper evaluates whether policy gradient avoids global Nash equilibria in two-player linear-quadratic dynamic games. Across tested parameter settings, a non-negligible fraction of randomly sampled games had global Nash equilibria that were strict saddle points of the gradient dynamics.

  • LQ game setup: LQ games combine linear dynamics, linear feedback policies, and quadratic costs, making gradient-play a policy-gradient benchmark for multi-agent reinforcement learning.Global Nash equilibria can be computed through coupled Riccati equations, while the players are coupled through the shared state dynamics.
  • Experimental setup: The experiment samples 1000 random dynamics matrices for each parameter configuration, computes global Nash feedback matrices, and checks the eigenvalues of the gradient-dynamics Jacobian.The setup varies q and r while fixing other matrices, then uses Lyapunov iterations and automatic differentiation.
  • Empirical results: 0%–25% of sampled LQ games had a global Nash equilibrium that was a strict saddle point of the gradient dynamics.The reported range covers the tested combinations of q and r.
  • Empirical results: At least 5% of the games exhibited this strict-saddle global Nash equilibrium for every tested q and r value.The worst tested configurations reached approximately 25%.
  • Implication: These results imply that multi-agent policy gradient lacks guarantees of convergence to global Nash equilibria in a non-negligible number of linear-quadratic games.The conclusion is drawn even under linear dynamics, linear policies, and quadratic costs.

6. Discussion and Future Directions

The discussion answers two questions about whether learning attractors are game-relevant and whether game-relevant equilibria attract learning dynamics. It concludes that gradient-based learning can avoid some Nash equilibria and converge to non-Nash or cyclic behavior, while several structural questions remain open.

  • Main questions: The paper studies whether all learning attractors are relevant equilibria and whether all game-relevant equilibria attract gradient-based learning.These questions are addressed across general-sum, zero-sum, and potential games.
  • Main findings: Without special game structure, gradient-based dynamics are not gradient flows, allowing non-game-relevant attractors and avoided Nash equilibria.The analysis applies under regularity conditions on cost functions and covers several commonly used multi-agent learning methods.
  • Consequences: In zero-sum and general-sum games, convergent learning may reach points with no game-theoretic relevance, while limit cycles can persist under stochastic updates.The discussion connects these behaviors to multi-agent reinforcement learning, bandits, generative adversarial networks, and online optimization.
  • Future directions: Which game classes make all Nash equilibria attracting or exclude non-Nash equilibria remains open.The paper also identifies designing algorithms whose attracting equilibria are all game-theoretically relevant as an important direction.

Appendix A. Proofs of the Main Results

The appendix contains the full proofs supporting the paper’s main results.

  • The appendix provides the full proofs of the results presented in the paper.

A.1 Proofs on Links Between Dynamical Systems and Games

The proofs connect local game-theoretic conditions to the stability structure of gradient dynamics. They show that differential Nash equilibria can be stable or strict saddles, with additional stability results for zero-sum and potential games.

  • General correspondence: A non-degenerate differential Nash equilibrium is either a locally asymptotically stable equilibrium or a strict saddle point of the gradient dynamics.It is neither strictly unstable nor strictly marginally stable.
  • Eigenvalue argument: The trace and determinant conditions imply that a non-degenerate differential Nash equilibrium has at least one eigenvalue with strictly positive real part in the relevant proof step.
  • Strict-saddle construction: Choosing game parameters so that ad < cb makes one Jacobian eigenvalue negative and the other positive, producing a strict saddle differential Nash equilibrium.The construction uses a two-player game on R × R with parameters a, b, c, and d.
  • Zero-sum games: In two-player zero-sum games, every differential Nash equilibrium is a non-degenerate differential Nash equilibrium and locally asymptotically stable under the gradient dynamics.The proof uses positive definiteness of the game Jacobian derived from the players’ second derivatives.
  • Potential games: In potential games, the Jacobian of the gradient dynamics equals the Hessian of the potential function.This follows from the shared potential-gradient representation of the players’ costs.

A.2 Proofs for Deterministic Setting

The deterministic proofs establish diffeomorphism of the learning map and use stable-manifold arguments to show that strict saddles attract only a measure-zero set of initial points. In potential games, symmetry further rules out cycles and supports convergence to stable equilibria under the stated existence assumption.

  • Stable-manifold argument: The stable manifold theorem identifies a local stable-center manifold around each critical point and constrains trajectories that remain nearby.The manifold is associated with the eigenspaces whose eigenvalues have absolute value at most one.
  • Diffeomorphism of the learning map: The proof first shows that the update map g is a diffeomorphism under bounded Jacobian and sufficiently small learning rates.Injectivity follows from Lipschitz control, while invertibility of Dg and the implicit function theorem establish local diffeomorphism; smoothness of the inverse completes the argument.
  • Stable-manifold argument: The set of initial points whose gradient-based learning converges to a strict saddle has Lebesgue measure zero.A countable cover of critical-point neighborhoods and repeated inverse images under the diffeomorphism preserve null sets, yielding the measure-zero conclusion.
  • Potential games: In potential games, symmetry of the differential game form makes all periodic orbits equilibria, so the dynamics have no limit cycles.The same symmetry implies that strict-saddle basins have measure zero.
  • Potential games: Assuming every trajectory has a limit, stable critical points of the potential-game dynamics are equilibria to which the remaining trajectories can converge.The cited proof combines exclusion of limit cycles with measure-zero avoidance of strict saddles.

A.3 Classical Results from Dynamical Systems

The appendix introduces a stochastic-approximation framework and states conditions for excluding unstable critical points under noisy gradient-based updates.

  • Stochastic approximation: The stochastic approximation framework models updates as x_t+1 = x_t + γ_t h(x_t) + ϵ_t, with h mapping the state space to its tangent space.The framework assumes a twice-continuously differentiable drift and explicitly accommodates stochastic perturbations.
  • Stochastic approximation: Pemantle’s theorem requires a linearly unstable critical point, suitably decaying step sizes, and a conditional-noise excitation condition.The stated step-size range is c1/t^η ≤ γ_t ≤ c2/t^η with η ∈ (1/2, 1].

Appendix B. Expanded Results in the Stochastic Setting

The stochastic appendix extends the main analysis and introduces a broader game class with stronger convergence guarantees than general-sum continuous games.

  • Expanded stochastic results: The appendix provides extended stochastic-setting results that require more mathematical formalism than the main body.It also introduces a new class of games generalizing potential games.
  • Expanded stochastic results: The newly introduced game class is described as having stronger convergence guarantees than the broader class of general-sum continuous games.The passage presents this as an additional contribution of the appendix.

B.1 Avoidance of Repelling Sets

The stochastic analysis compares noisy iterates with the flow generated by the game dynamics and derives avoidance results for unstable cycles under compactness and noise assumptions.

  • Stochastic setting: The stochastic process remains in a smooth, compact, boundaryless decision space, enabling comparison with the flow generated by the game dynamics.The iterates are treated as a noisy approximation to the differential equation ˙x = −ω(x).
  • Cycle definitions: A non-stationary periodic orbit is defined as a cycle, with hyperbolicity determined by its characteristic multipliers.A cycle is linearly stable when its characteristic multipliers lie strictly inside the unit circle and unstable when at least one lies outside.
  • Avoidance of repelling sets: Under the stated compactness, stochastic-gradient, and noise conditions, competitive stochastic gradient-based learning converges to linearly unstable cycles only on a restricted set.The theorem applies when each agent’s decision space is a smooth compact manifold without boundary and the iterates remain in the joint space.
  • Avoidance of repelling sets: Periodic orbits are not automatically excluded from gradient-based learning in games, but linearly unstable cycles are avoided almost surely under the cited stochastic-approximation conditions.The latter conclusion follows from the theorem stating that the probability of convergence to a hyperbolic linearly unstable cycle is zero.

B.2 Morse-Smale Games

Morse-Smale games provide a structurally stable class in which stochastic competitive gradient-based learning has restricted limiting behavior. In potential games, the absence of periodic cycles strengthens this result to almost-sure convergence to non-degenerate differential Nash equilibria, while strict-saddle local Nash equilibria can still be avoided.

  • Morse-Smale structure: Morse-Smale games require hyperbolic periodic orbits, transverse stable–unstable manifold intersections, periodic omega-limit sets, and a global attractor.These conditions imply finitely many periodic orbits and constrain the game’s long-run dynamics.
  • Stochastic learning limits: With probability one, stochastic competitive gradient-based learning converges to attractors of ˙x = −ω(x), including equilibria and cycles.Any attractor realized with positive probability must be linearly stable.
  • Stochastic learning limits: Equilibrium attractors with positive limiting probability are either non-degenerate differential Nash equilibria, generically local Nash equilibria, or non-Nash locally asymptotically stable equilibria.Saddle points are excluded from the equilibrium attractors identified by the theorem.
  • Potential games: Potential games yield almost-sure convergence to non-degenerate differential Nash equilibria because their gradient flows admit no periodic cycles.Non-degenerate differential Nash equilibria are generically local Nash equilibria.
  • Potential games: Potential games can still contain local Nash equilibria that are strict saddle points, creating a fundamental problem for gradient-based learning despite convergence to a local Nash equilibrium.The convergence guarantee does not imply that every local Nash equilibrium is reached.

C.1 Online Optimization: Gradient Play in Non-Cooperative Games

The competitive gradient-based learning framework includes full-information gradient play, gradient-free online optimization, and policy gradient in multi-agent settings. Its relevance extends to GAN training, where gradient dynamics can be complex and admit limit cycles.

  • Online optimization: Full-information online optimization fits the framework as gradient play, with each agent minimizing its cost while responding to the other agents’ current iterates.The framework allows agents’ costs to depend on the current iterates of other players.
  • Online optimization: Gradient-free online optimization estimates an update direction by querying the cost at a randomly perturbed action and multiplying the result by the sampled unit vector.The update uses xi,t+1 = xi,t −γifi(xi + δiu, x−i)u.
  • Generative adversarial networks: GAN training applies stochastic gradient descent to a generator–discriminator zero-sum game whose equilibrium is generally a saddle point and whose dynamics can admit limit cycles.Wasserstein GAN uses a 1-Lipschitz discriminator and corresponding gradient updates for discriminator and generator parameters.
  • Multi-agent reinforcement learning: In multi-agent reinforcement learning, each agent minimizes the negative expected cumulative reward of its parameterized policy while other agents’ actions remain unrestricted.The resulting loss is fi(xi, x−i) = −Ji(πi(xi), π−i).
  • Multi-agent reinforcement learning: Policy gradient in multi-agent reinforcement learning conforms to the competitive gradient-based learning framework using policy parameters as continuous-game actions.Agents can construct gradient estimators from trajectories, rewards, states, and their own actions without knowing other agents’ policies or the environment dynamics.
Loading 1804.05464v3…