# Multi-agent learning under uncertainty: Recurrence vs. concentration

arXiv: https://arxiv.org/abs/2512.08132 · HTML: https://mlsanity.com/paper/2512.08132/

## 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 (most cited first, 21 of 21)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [A unified stochastic approximation framework for learning in games](https://mlsanity.com/paper/2206.03922/) (2022)
- [What is the long-run distribution of stochastic gradient descent? A large deviations analysis](https://mlsanity.com/paper/2406.09241/) (2024)
- [New First-Order Algorithms for Stochastic Variational Inequalities](https://mlsanity.com/paper/2107.08341/) (2021)
- [The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations](https://mlsanity.com/paper/2503.16398/) (2025)
- [On the robustness of learning in games with stochastically perturbed payoff observations](https://mlsanity.com/paper/1412.6565/) (2014)
- [On the convergence of gradient-like flows with noisy gradient input](https://mlsanity.com/paper/1611.06730/) (2016)
- [Distributed stochastic optimization via matrix exponential learning](https://mlsanity.com/paper/1606.01190/) (2016)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Stochastic mirror descent dynamics and their convergence in monotone variational inequalities](https://mlsanity.com/paper/1710.01551/) (2017)
- [Stochastic Multiplicative Weights Updates in Zero-Sum Games](https://mlsanity.com/paper/2110.02134/) (2021)
- [Imitation Dynamics with Payoff Shocks](https://mlsanity.com/paper/1412.7842/) (2014)
- [The impact of uncertainty on regularized learning in games](https://mlsanity.com/paper/2506.13286/) (2025)

## 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.