mlsanityData to 14 Oct 2026

Multi-agent learning under uncertainty: Recurrence vs. concentration

arXiv 2512.08132 ↗First posted 9 Dec 2025cs.GT cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we examine the convergence landscape of multi-agent learning under uncertainty. Specifically, we analyze two stochastic models of regularized learning in continuous games -- one in continuous and one in discrete time with the aim of characterizing the long-run behavior of the induced sequence of play. In stark contrast to deterministic, full-information models of learning (or models with a vanishing learning rate), we show that the resulting dynamics do not converge in general. In lieu of this, we ask instead which actions are played more often in the long run, and by how much. We show that, in strongly monotone games, the dynamics of regularized learning may wander away from equilibrium infinitely often, but they always return to its vicinity in finite time (which we estimate), and their long-run distribution is sharply concentrated around a neighborhood thereof. We quantify the degree of this concentration, and we show that these favorable properties may all break down if the underlying game is not strongly monotone -- underscoring in this way the limits of regularized learning in the presence of persistent randomness and uncertainty.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 81 references that are in the map. First posted on arXiv 9 Dec 2025.

Builds on

21 of 81 references.

References · 21

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  3. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  4. 2017Cycles in adversarial regularized learningcited by 124
  5. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  6. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  7. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  8. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 48
  9. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  10. 2022A unified stochastic approximation framework for learning in gamescited by 23
  11. 2024What is the long-run distribution of stochastic gradient descent? A large deviations analysiscited by 17
  12. 2021New First-Order Algorithms for Stochastic Variational Inequalitiescited by 8
9 more
  1. 2025The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviationscited by 8
  2. 2014On the robustness of learning in games with stochastically perturbed payoff observationscited by 7
  3. 2016On the convergence of gradient-like flows with noisy gradient inputcited by 7
  4. 2016Distributed stochastic optimization via matrix exponential learningcited by 6
  5. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
  6. 2017Stochastic mirror descent dynamics and their convergence in monotone variational inequalitiescited by 5
  7. 2021Stochastic Multiplicative Weights Updates in Zero-Sum Gamescited by 4
  8. 2014Imitation Dynamics with Payoff Shockscited by 2
  9. 2025The impact of uncertainty on regularized learning in gamescited by 2

Built on by

Not cited yet.