Research map / Multi-agent systems and games / Games and equilibria
Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes stochastic regularized learning (FTRL) in continuous games under uncertainty in continuous and discrete time, showing null-monotone games drift away from equilibrium while strongly monotone games return to a near-equilibrium region and concentrate there.
Problem
Long-run behavior and distributional properties (recurrence, concentration, invariant distributions) of regularized learning (FTRL) with noisy gradient feedback in continuous games, with contrasting null-monotone and strongly monotone regimes.
Approach
Models FTRL under uncertainty as a stochastic differential equation driven by general martingale noise (continuous time) and as constant step-size FTRL with stochastic first-order feedback (discrete time); uses the Fenchel coupling as a mean energy function to derive hitting-time bounds and concentration of the occupation measure, showing a dichotomy between null-monotone and strongly monotone gam
Key results
- In strongly monotone games, the continuous-time stochastic dynamics satisfy E[tau_radius] <= (K^-1 init_fench)/(radius^2 - radius_sigma^2) and their occupation measure concentrates in a ball of radius O(sigma_max) around equilibrium with lim occupation >= 1 - radius_sigma^2/radius^2.
- In null-monotone games with interior equilibrium, the continuous-time dynamics do not admit an invariant distribution and the expected hitting time to decrease Fenchel coupling is infinite.
- In discrete time, for null-monotone games with unbounded action space, the expected Fenchel coupling diverges, so FTRL drifts away to infinity on average.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add persistent Brownian noise to gradient dynamics | Bilinear saddle · Bilinear saddle, continuous time | mean squared distance to equilibrium: lim_{t→∞} E[||X(t)||²] = ∞ | Hurt |
| Add persistent Brownian noise to gradient dynamics | Bilinear saddle · Bilinear saddle, continuous time | mean return time to equilibrium: E[τ_r] = ∞ | Hurt |
| Add persistent Brownian noise to gradient dynamics | Quadratic saddle · Quadratic saddle, continuous time | mean squared distance to equilibrium: lim_{t→∞} E[||X(t)||²] = σ² | Mixed |
| Use a null-monotone game rather than a strongly monotone game | Stochastic regularized learning · Null-monotone games, continuous time | long-run concentration around equilibrium | Hurt |
| Use a strongly monotone game rather than a null-monotone game | Stochastic regularized learning · Strongly monotone games, continuous time | long-run occupation probability within equilibrium ball: ≥ 1 − r_σ² / r² | Helped |
| Use a null-monotone game rather than a strongly monotone game | Constant-step stochastic FTRL · Null-monotone games, discrete time | expected Fenchel coupling: lim_{n→∞} E[F_n] = ∞ | Hurt |
| Use a strongly monotone game rather than a null-monotone game | Constant-step stochastic FTRL · Strongly monotone games, discrete time | long-run fraction of iterates within equilibrium ball: ≥ 1 − r_σ² / r² | Helped |
Surprising findings
- Strongly monotone dynamics return arbitrarily close to their starting point infinitely often with probability one, reminiscent of Poincaré recurrence, although returns can be exceedingly far apart.
Limitations
- Discrete-time null-monotone result is qualitative; hitting-time bounds are only conjectured.
- Analysis restricted to monotone (strongly or null) games; mixed cases left to future work.
- Discrete-time strongly monotone bounds require treating initialization inside vs outside the ball separately.
Experimental setup
Builds on: follow-the-regularized-leader stochastic approximation Hedge
Closest papers by meaning
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.92)
- Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos (AAAI 2024 · similarity 0.90)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.90)
- Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.89)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.89)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.