Multi-agent learning under uncertainty: Recurrence vs. concentration

• URL: http://arxiv.org/abs/2512.08132v1
• Date: Tue, 09 Dec 2025 00:18:19 GMT
• Title: Multi-agent learning under uncertainty: Recurrence vs. concentration
• Authors: Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, Jose Blanchet,
• Abstract summary: We show that in strongly monotone games, the dynamics of regularized learning may wander away from equilibrium infinitely often.<n>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.
• Score: 25.372363445606265
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Asymptotic Behavior of Random Time-Inhomogeneous Markovian Quantum Dynamics [0.0]
  We study continuous-time, time-inhomogeneous Markovian quantum dynamics in a random environment.<n> normalized evolution converges almost surely to a stationary family of full-rank states.<n> convergences occur at exponential rates that may depend on the disorder.
  arXiv  Detail & Related papers  (2025-09-10T18:35:52Z)
• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  We examine the long-run behavior of regularized, no-regret learning in finite games. We obtain an equivalence between strategic and dynamic stability. We show that methods based on entropic regularization converge at a geometric rate.
  arXiv  Detail & Related papers  (2023-11-04T14:07:33Z)
• Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations [98.5802673062712]
  We introduce temporally-coupled perturbations, presenting a novel challenge for existing robust reinforcement learning methods. We propose GRAD, a novel game-theoretic approach that treats the temporally-coupled robust RL problem as a partially observable two-player zero-sum game.
  arXiv  Detail & Related papers  (2023-07-22T12:10:04Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  We develop a flexible approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite) The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, exponential/multiplicative weights for learning in finite games, optimistic and bandit variants of the above, etc.
  arXiv  Detail & Related papers  (2022-06-08T14:30:38Z)
• Online Learning in Periodic Zero-Sum Games [27.510231246176033]
  We show that Poincar'e recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
  arXiv  Detail & Related papers  (2021-11-05T10:36:16Z)
• Learning in nonatomic games, Part I: Finite action spaces and population games [22.812059396480656]
  We examine the long-run behavior of a wide range of dynamics for learning in nonatomic games, in both discrete and continuous time. We focus exclusively on games with finite action spaces; nonatomic games with continuous action spaces are treated in detail in Part II of this paper.
  arXiv  Detail & Related papers  (2021-07-04T11:20:45Z)
• Contrastive learning of strong-mixing continuous-time stochastic processes [53.82893653745542]
  Contrastive learning is a family of self-supervised methods where a model is trained to solve a classification task constructed from unlabeled data. We show that a properly constructed contrastive learning task can be used to estimate the transition kernel for small-to-mid-range intervals in the diffusion case.
  arXiv  Detail & Related papers  (2021-03-03T23:06:47Z)
• Learning Temporal Dynamics from Cycles in Narrated Video [85.89096034281694]
  We propose a self-supervised solution to the problem of learning to model how the world changes as time elapses. Our model learns modality-agnostic functions to predict forward and backward in time, which must undo each other when composed. We apply the learned dynamics model without further training to various tasks, such as predicting future action and temporally ordering sets of images.
  arXiv  Detail & Related papers  (2021-01-07T02:41:32Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
  arXiv  Detail & Related papers  (2020-05-28T13:47:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.