Skip to content

Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper characterizes the long-run behavior of stochastic follow-the-regularized-leader (FTRL) dynamics in continuous multi-player games under persistent noise, proving a sharp dichotomy: null-monotone games (e.g., bilinear zero-sum) cause learning trajectories to drift away from equilibrium with no invariant distribution, while strongly monotone games (e.g., Kelly auctions, Cournot) yield trajectories that concentrate in an O(σ)-neighborhood of equilibrium with a unique invariant measure. Results are established in both continuous time (SDE/Itô diffusion) and discrete time (constant learning rate).

Problem

Standard convergence theory for FTRL assumes either full information (no noise) or vanishing learning rates, neither of which reflects practical multi-agent training. Under persistent, non-vanishing noise—endogenous or exogenous—the long-run distributional properties of constant-rate FTRL were essentially unknown. Prior work gave mean-distance bounds but not invariant-measure structure or hitting-time estimates for the constant step-size regime.

Method

The authors model stochastic FTRL (S-FTRL) in continuous time as an SDE perturbed by a general Itô martingale (colored, correlated noise), and in discrete time as FTRL with a stochastic first-order oracle and constant step size γ. Analysis uses the Fenchel coupling F(x*, Y(t)) as a Lyapunov/energy function—a primal-dual generalization of squared Euclidean distance compatible with arbitrary mirror maps. Continuous-time proofs apply Dynkin's formula and compactification of Y's sublevel sets; for positive recurrence in the strongly monotone case, they work with the score process Y(t) (whose generator is uniformly elliptic after a quotient reduction) and push forward via Q to X. Discrete-time proofs establish Lebesgue irreducibility, minorization, and positive Harris recurrence via a regeneration/coupling argument.

Key Contributions

  • Theorems 1 & 2 (continuous time): In null-monotone games, S-FTRL escapes to infinity in mean square and requires infinite expected time to return (𝔼[τ_ε⁻] = ∞); no invariant distribution exists. In α-strongly monotone games, 𝔼[τ_r] ≤ (F₀/α)/(r² − r_σ²) with r_σ = σ_max/√(2Kα), and the long-run fraction of time in 𝔹_r(x*) is ≥ 1 − r_σ²/r².
  • Theorems 3 & 4 (discrete time): Null-monotone: lim 𝔼[F_t] = ∞. Strongly monotone: explicit hitting-time upper bound; unique invariant distribution with convergence in total variation; occupation measure concentration bound (24) around x*.
  • First distributional characterization of constant-step-size stochastic FTRL in multi-agent games.
  • Poincaré-recurrence analog: in strongly monotone games, trajectories return arbitrarily close to their starting point infinitely often (a.s.), but expected return times can be unbounded.

Results

  • Continuous-time strongly monotone (Theorem 2): 𝔼[τ_r] ≤ F₀/(α(r² − r_σ²)) for r > r_σ; occupation measure satisfies μ_t(𝔹_r(x*)) → ≥ 1 − r_σ²/r² as t → ∞; bound is tight (matches Ornstein–Uhlenbeck special case from Proposition 2).
  • Discrete-time strongly monotone (Theorem 4): 𝔼[τ_r] ≤ F₀/(α γ(r² − r_σ²)) (outside ball) or 1/(αγ(r² − r_σ²)) (inside ball), with r_σ = √(γ(σ² + β²)/(αK)); same 1 − r_σ²/r² concentration bound on time-average.
  • Null-monotone (Theorems 1 & 3): finite expected time to move ε farther from equilibrium (bounded by 2ε/κσ²_min), infinite expected time to get ε closer; no invariant measure.
  • Validated numerically on bilinear vs. quadratic min-max over [0,1]² with entropic FTRL (Fig. 1), confirming drift to boundary vs. concentration near equilibrium.

Limitations

  • Merely monotone games (α = 0, not null-monotone) are not fully analyzed; authors conjecture intermediate behavior but defer to future work.
  • Discrete-time hitting-time bounds for the null-monotone case are incomplete: no tight estimates on 𝔼[τ_ε±], left as open conjecture.
  • Results require the noise to have a non-degenerate absolutely continuous component (σ_min > 0 or analogous density condition)—purely deterministic or singular noise is excluded.
  • Quantitative bounds depend on problem-specific constants (α, K, σ_max, β) that may be hard to estimate in practice.
  • Extension to merely monotone or weakly quasi-monotone games is noted but not done.

Relevance to Agentic AI / LLM Agents

Multi-agent RL and LLM agent populations commonly use constant learning rates under stochastic gradient feedback—precisely the setting this paper formalizes. The null- vs. strongly-monotone dichotomy directly predicts when agent populations will cycle or diverge (e.g., adversarial/zero-sum settings like GAN training or debate agents) versus concentrate near equilibrium (e.g., cooperative resource allocation). The invariant-measure characterization and hitting-time bounds provide a theoretical basis for understanding why constant-rate training of agent populations fails to converge pointwise yet remains "close" to equilibrium on average—a key distinction for evaluating deployed multi-agent systems. This work complements empirical observations of non-convergence in multi-agent RL by giving rigorous geometric and distributional explanations.