Source-linked AI summary
Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings
Benjamin Chasnov, Lillian J. Ratliff, Eric Mazumdar, Samuel A. Burden
TL;DR
Coupled learning in games is difficult to analyze because its dynamics need not behave like single-agent gradient descent, and learning rates also shape learning paths and outcomes. The paper derives deterministic and stochastic convergence guarantees for continuous games with uniform or non-uniform rates. It finds that unequal rates distort the vector field and can alter convergence behavior and attraction regions.
Problem
Coupled game dynamics can have non-symmetric Jacobians and non-equilibrium limiting behavior, while error bounds, convergence rates, and the effects of learning rates on learning paths and limiting behavior remain questions of interest.
Source: §1 · p. 2Method
The paper analyzes myopic gradient-based learning in continuous games, using oracle gradients or unbiased estimators and considering uniform and non-uniform learning rates.
Source: §1 · p. 2, §6 · p. 19Results
Non-uniform learning rates distort the vector field and can change convergence rates and attraction regions, with different rates allowing identical initial conditions to converge to different equilibria.
Source: §1 · p. 3, §6 · p. 19Takeaways & Limitations
The analysis provides deterministic convergence rates and stochastic high-probability finite-time guarantees for convergence to a neighborhood of a Nash equilibrium.
Source: §1 · p. 2The stated results concern continuous games with Euclidean strategy spaces; a local stochastic guarantee may also require initialization in an attraction region, which is difficult to ensure in practice.
Source: §4.2.1 · p. 11, §6 · p. 19
Abstract
from arXiv · showhide
Considering a class of gradient-based multi-agent learning algorithms in non-cooperative settings, we provide local convergence guarantees to a neighborhood of a stable local Nash equilibrium. In particular, we consider continuous games where agents learn in (i) deterministic settings with oracle access to their gradient and (ii) stochastic settings with an unbiased estimator of their gradient. Utilizing the minimum and maximum singular values of the game Jacobian, we provide finite-time convergence guarantees in the deterministic case. On the other hand, in the stochastic case, we provide concentration bounds guaranteeing that with high probability agents will converge to a neighborhood of a stable local Nash equilibrium in finite time. Different than other works in this vein, we also study the effects of non-uniform learning rates on the learning dynamics and convergence rates. We find that much like preconditioning in optimization, non-uniform learning rates cause a distortion in the vector field which can, in turn, change the rate of convergence and the shape of the region of attraction. The analysis is supported by numerical examples that illustrate different aspects of the theory. We conclude with discussion of the results and open questions.
1. Introduction
The paper addresses why convergence analysis from single-agent optimization does not straightforwardly extend to coupled learning in games, where agents’ costs and dynamics interact. It develops convergence guarantees for deterministic and stochastic gradient-based learning and examines how unequal learning rates affect outcomes.
Background
- Game-theoretic models are increasingly used to study interactions among learning algorithms, while some learning dynamics exhibit periodic or chaotic limiting behavior rather than equilibrium convergence.The introduction cites machine-learning applications and examples of such dynamics.Source: §1 · pp. 1–2
Motivation
- Unlike single-agent gradient flows, coupled game dynamics can have non-symmetric Jacobians, periodic orbits, and cases where a player’s cost increases despite following its own gradient.The coupling can also allow agents to converge to local maxima of their own costs.Source: §1 · p. 2
- The analysis responds to open questions about error bounds, convergence rates, and how learning rates affect learning paths, limiting behavior, and accumulated cost.These questions matter for guarantees on collective behavior and subsequent control or incentive-policy synthesis.Source: §1 · p. 2
Contributions
- The paper derives deterministic convergence rates and stochastic convergence guarantees for gradient-based multi-agent learning, covering oracle gradients, unbiased estimators, and uniform or non-uniform learning rates.The deterministic results concern differential Nash equilibria; stochastic results include high-probability finite-time convergence to a neighborhood of a Nash equilibrium.Source: §1 · p. 2
Learning rates
- Different learning rates can lead the joint action to a point with lower cost for the slower player than uniform rates from the same initialization.The paper attributes this to distortion of the vector field, whose coordinates minimize different players’ costs.Source: §1 · p. 3
2. Preliminaries
The preliminaries model each player as minimizing an individual cost while updating only its own action, with other players’ actions entering through the coupled game. They define the game’s critical points and equilibrium conditions, then relate differential Nash equilibria to local stability.
Game and learning model
- Players choose actions in product strategy spaces and update their own action using their cost gradient or an unbiased estimator, while treating other players’ actions as given.The costs are assumed sufficiently smooth, and the game vector field is Lipschitz.Source: §2 · p. 3
Game Jacobian
- The game Jacobian contains own-player second derivatives and cross-player derivatives, and is generally non-symmetric even though each own-player Hessian is symmetric.This non-symmetry makes the analysis differ from typical stochastic gradient-descent analysis.Source: §2 · p. 3
Equilibria
- A local Nash equilibrium requires each player’s cost to be locally minimized against unilateral changes while the other players’ actions are fixed.Strict inequalities in the local conditions define a strict local Nash equilibrium.Source: §2 · p. 3
- A critical point has zero game vector field; a differential Nash equilibrium additionally has positive own-player second derivatives, while local Nash equilibria satisfy the corresponding nonnegative conditions.The stated strict second-derivative conditions also suffice for local Nash equilibrium.Source: §2 · p. 4
Stability
- A differential Nash equilibrium with non-degenerate game Jacobian is isolated and strict, and it is attracting when the Jacobian spectrum lies strictly in the right half-plane.The paper notes that non-degenerate differential Nash equilibria are generic among local Nash equilibria and structurally stable.Source: §2 · p. 4
3. Deterministic Setting
With oracle access to individual gradients, agents update their actions using constant uniform or non-uniform learning rates. The section establishes local convergence guarantees for both choices, including finite-time results and conditions under which non-uniform rates converge.
3.1 Uniform Learning Rates
- With uniform rates below the stated threshold, Proposition 2 guarantees exponential convergence from initial points in a ball within the equilibrium’s region of attraction.Source: §3.1 · p. 5
- For uniform rates, Theorem 1 guarantees finite-time entry into an ε-neighborhood of a stable differential Nash equilibrium from an initial point in the specified ball, assuming α < β.Source: §3.1 · p. 5
- The uniform-rate choice minimizes a worst-case 2-norm contraction bound, but games’ nonsymmetric Jacobians allow faster contraction than that bound suggests.Source: §3.1 · p. 6
3.2 Non-Uniform Learning Rates
- For non-uniform rates, convergence to a stable differential Nash equilibrium follows when ρ(I − ΓJ(x)) < 1 throughout its region of attraction.Source: §3.2 · p. 6
- For non-uniform rates, Theorem 2 gives finite-time convergence to an ε-neighborhood under its stated conditions on the learning rates and equilibrium neighborhood.Source: §3.2 · p. 7
- Non-uniform rates scale the rows of the game Jacobian, distorting its eigenstructure; unlike a designed preconditioner, agents’ rates are not chosen by the analyst.Source: §3.2 · p. 8
4. Stochastic Setting
For stochastic gradient learning, the paper establishes high-probability convergence results with uniform and non-uniform learning rates. The non-uniform analysis treats the updates as a two-timescale process and gives both asymptotic and finite-time guarantees under stated conditions.
4. Stochastic Setting
- Unbiased gradient estimators yield stochastic updates whose convergence is analyzed by connecting the discrete learning rules to limiting continuous-time dynamics.Source: §4 · p. 8
4.2 Non-Uniform Learning Rates
- For non-uniform rates, the analysis extends to individual agent step sizes by adding assumptions and using two-timescale techniques.Source: §4 · p. 8, §4.2 · p. 10
4.1 Uniform Learning Rates
- With uniform learning rates, stochastic gradient learning reaches an ε-neighborhood of a stable differential Nash equilibrium in finite time with high probability.The stated burn-in scales as O(log(1/ε)), while the reciprocal learning rate must scale as O(1/ε).Source: §4.1 · p. 9
4.2.1 ASYMPTOTIC CONVERGENCE IN THE NON-UNIFORM LEARNING RATE SETTING
- When the faster player's dynamics have a globally asymptotically stable equilibrium for each fixed slower-player state, the slower player's path asymptotically tracks its limiting flow.Source: §4.2.1 · pp. 10–11
- If the limiting dynamics have only isolated equilibria, as can occur in potential games, iterates converge almost surely to a stationary point, which need not be Nash.The stationary-point set contains stable Nash equilibria, but the paper notes that stable non-Nash points are also possible.Source: §4.2.1 · p. 11
4.2.2 HIGH-PROBABILITY, FINITE-SAMPLE GUARANTEES WITH NON-UNIFORM LEARNING RATES
- With γ2,k = o(γ1,k), the iterates lock into an ε-neighborhood with high probability when initialized in the specified local region and the theorem's conditions hold.Source: §4.2.2 · p. 12
5. Numerical Examples
The numerical examples illustrate convergence guarantees and show that non-uniform learning rates can reshape trajectories and change which equilibrium agents reach. Across the examples, the effects range from stretching a vector field to selecting different equilibria in a multi-agent control problem.
5. Numerical Examples
- The examples are presented as numerical validation of convergence guarantees for deterministic and stochastic gradient updates with uniform and non-uniform learning rates.The linear-quadratic example uses oracle gradients; the stochastic example uses an unbiased gradient estimator.Source: §5 · p. 13, §5.1 · pp. 13–14, §5.3 · p. 17
5.1 Deterministic Policy Gradient in Linear Quadratic Dynamic Games
- In the linear-quadratic game, gradient updates converge to the known Nash policies, and a larger learning rate empirically converges faster than the theorem’s selected rate.The theorem’s iteration bound is illustrated by the dashed curve in Figure 1b.Source: §5.1 · p. 14
5.2 Benchmark: matching pennies
- In matching pennies, the fixed points remain unchanged while the gradient flow stretches along the faster agent’s coordinate.The Jacobian at the mixed Nash equilibrium has purely imaginary eigenvalues, and the dynamics admit a limit cycle.Source: §5.2 · p. 15, Figure 2 · p. 15
5.3 Exploring the Effects of Non-uniform Learning Rates on the Learning Path
- With equal learning rates, both highlighted paths reach (−1.063, 1.014), but different rates can change both the path and destination equilibrium.The example has two stable differential Nash equilibria; its attraction regions are warped under different learning rates.Source: §5.3 · pp. 16–17, Figure 3 · p. 16
5.4 Multi-agent control and collision avoidance
- In the collision-avoidance game, changing agents’ relative learning rates changes which equilibrium the four-agent controller reaches.The examples show different equilibria when the red agent learns slower versus when the blue agent learns quicker.Source: §5.4 · p. 18, Figure 4 · p. 18
6. Discussion and Future Work
The discussion summarizes convergence analysis for myopic agents using their own gradients, including oracle-gradient and unbiased-estimator settings. It emphasizes that relative learning rates can alter stability and attraction regions, while identifying broader update rules and strategy spaces as directions for extension.
6. Discussion and Future Work
- The analysis covers myopic updates using each agent’s own gradient, with either oracle access or an unbiased estimator, and studies non-uniform learning rates.The guarantees use dynamical-systems theory and stochastic approximation.Source: §6 · p. 19
- Preconditioning by the diagonal learning-rate matrix can alter fixed-point properties and attraction regions; numerically, slowing an agent can destabilize a stable differential Nash equilibrium and prevent convergence to Nash.Different rates can also send agents from the same initial condition to different equilibria.Source: §6 · p. 19
- The stated results apply to continuous games with Euclidean strategy spaces; constrained sets and Riemannian manifolds would require modified update rules.The discussion points to proximal maps for constrained sets and retractions for manifolds.Source: §6 · p. 19
- The update framework may also cover other myopic rules of the form xk+1 = xk − Γg(xk), including stochastic variants of multi-agent Q-learning.The paper’s considered special case sets g to the collection of agents’ individual gradients.Source: §6 · p. 19
- Attracting critical points need not be Nash equilibria; stable limit cycles and stable local non-Nash critical points are also possible attractors.The discussion notes that the set of critical points includes more than local Nash equilibria.Source: §6 · p. 19
A.1 Deterministic Setting
The deterministic appendix proves a local finite-time convergence bound by establishing contraction around the equilibrium. It also notes that the contraction argument can be extended under a spectral-radius condition.
A.1 Deterministic Setting
- The proof chooses a neighborhood where ∥I − ΓDω(x)∥ is uniformly bounded below one, then iterates the resulting contraction estimate.It uses a smaller radius within the region where the bound holds.Source: §A.1 · p. 20
- Under the local contraction condition, iterates enter Bε(x*) by T = ⌈δ^-1 log(r*/ε)⌉ and remain there thereafter.The proof constructs nested contraction bounds with 0 < 1 − δ < 1.Source: §A.1 · p. 20
- A similar result holds when the spectral radius ρ(I − ΓDω(x)) is below one throughout the neighborhood, using a suitable norm.The proof chooses a norm that makes the operator norm less than one.Source: §A.1 · p. 20
A.2 Stochastic Setting
The stochastic appendix compares interpolated stochastic-approximation trajectories with limiting differential-equation flows to derive high-probability convergence guarantees. Its two-timescale argument first tracks the fast player’s response to the slow player, then bounds the slow player’s trajectory.
A.2 Stochastic Setting
- Alekseev’s formula bounds the difference between interpolated iterates and their limiting flows, and a union bound over later intervals yields a concentration bound.The argument is applied first to the fast player and then to the slow player.Source: §A.2 · pp. 20–21
- The proof analyzes the fast player with the slow player fixed, then the slow player along the fast player’s response map, using local Lyapunov and stability bounds.The fast trajectory tracks λ(x2,k), where D1f1(x1,k, x2,k) = 0.Source: §A.2 · pp. 21–22
- With high probability, the sequence defined by the fast player’s best response tracks the fast player’s dynamics, with the two asymptotically contracting toward each other.The Taylor-expansion remainder is bounded by a constant times the squared change in the slow player’s iterate.Source: §A.2 · p. 22
- The appendix obtains the desired guarantees for both players by combining the intermediate lemmas.The slow-player bound uses a linear system with Jacobian J2 and an exponential bound on its fundamental solution.Source: §A.2 · pp. 22–23
Appendix B. Additional Examples
Appendix B adds examples and information about examples in the main text.
Appendix B. Additional Examples
- Appendix B contains additional examples and information about examples presented in the main text.Source: Appendix B · p. 23
B.1 LQ game system parameters
This section reports constants used in the LQ game and the resulting value of γ.
B.1 LQ game system parameters
- The LQ game constants are given as α = 19.4 and 2.90 × 105, yielding γ = 1.52 × 10−5.Source: §B.1 · p. 23
B.2 Coupled Riccati equations
The section presents an iterative Lyapunov algorithm for finding the Nash equilibrium of an LQ game. It assumes stabilizability-detectability for at least one player’s specified triple and outlines initialization, updates, and convergence.
B.2 Coupled Riccati equations
- The algorithm assumes either (A, B1, √Q1) or (A, B2, √Q2) is stabilizable-detectable, and proceeds without loss of generality using the first triple.Source: §B.2 · p. 23
- The iterative Lyapunov algorithm initializes P1(0) as the unique positive definite solution to a Riccati equation and computes both players’ corresponding gain matrices.The algorithm is presented as a method for finding the Nash equilibrium of the linear quadratic game.Source: §B.2 · pp. 23–24
- At each iteration, the feedback gains and cost-to-go matrices are updated using gain rules and Lyapunov equations, respectively.Source: §B.2 · p. 24
- The iteration repeats until the gains converge; the authors describe extension to n players as fairly straightforward and refer to for details.Source: §B.2 · p. 24