Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games

• URL: http://arxiv.org/abs/2505.07642v1
• Date: Mon, 12 May 2025 15:12:27 GMT
• Title: Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games
• Authors: Yulong Lu, Pierre Monmarché,
• Abstract summary: Mixed Nash equilibria (MNE) for zero-sum games with mean-field interacting players has recently raised much interest in machine learning.<n>We propose a mean-field descent gradient dynamics for finding the MNE of zero-sum games involving $K$ players with $Kgeq 2$.<n>Unlike previous two-scale approaches for finding the MNE, our approach treats all player types on the same time scale.
• Score: 4.910937238451485
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The approximation of mixed Nash equilibria (MNE) for zero-sum games with mean-field interacting players has recently raised much interest in machine learning. In this paper we propose a mean-field gradient descent dynamics for finding the MNE of zero-sum games involving $K$ players with $K\geq 2$. The evolution of the players' strategy distributions follows coupled mean-field gradient descent flows with momentum, incorporating an exponentially discounted time-averaging of gradients. First, in the case of a fixed entropic regularization, we prove an exponential convergence rate for the mean-field dynamics to the mixed Nash equilibrium with respect to the total variation metric. This improves a previous polynomial convergence rate for a similar time-averaged dynamics with different averaging factors. Moreover, unlike previous two-scale approaches for finding the MNE, our approach treats all player types on the same time scale. We also show that with a suitable choice of decreasing temperature, a simulated annealing version of the mean-field dynamics converges to an MNE of the initial unregularized problem.

Related papers

• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  Non-ergodic convergence of learning dynamics in games is widely studied because of its importance in both theory and practice.<n>Recent work showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update, can exhibit arbitrarily slow last-iterate convergence.<n>We show that OMWU achieves an $O(T-1/6)$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games.
  arXiv  Detail & Related papers  (2025-03-04T17:49:24Z)
• Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspective [11.603515105957461]
  We address Reinforcement Learning (RL) among agents that are grouped into teams such that there is cooperation within each team but general-sum competition across different teams.
  arXiv  Detail & Related papers  (2024-03-17T21:11:55Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• 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)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective [5.025654873456756]
  Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous game is an important and challenging problem in machine learning. We first study the convergence of a two-scale Mean-Field GDA dynamics for finding the MNE of the entropy-regularized objective.
  arXiv  Detail & Related papers  (2022-12-17T03:44:35Z)
• Asynchronous Gradient Play in Zero-Sum Multi-agent Games [25.690033495071923]
  We study asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks. To the best of our knowledge, this work is the first that aims to understand asynchronous gradient play in zero-sum polymatrix games.
  arXiv  Detail & Related papers  (2022-11-16T15:37:23Z)
• Provably convergent quasistatic dynamics for mean-field two-player zero-sum games [10.39511271647025]
  We consider a quasistatic Wasserstein gradient flow dynamics in which one probability distribution follows the Wasserstein gradient flow, while the other one is always at the equilibrium. Inspired by the continuous dynamics of probability distributions, we derive a quasistatic Langevin gradient descent method with inner-outer iterations.
  arXiv  Detail & Related papers  (2022-02-15T20:19:42Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• 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)
• A mean-field analysis of two-player zero-sum games [46.8148496944294]
  Mixed Nash equilibria exist in greater generality and may be found using mirror descent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
  arXiv  Detail & Related papers  (2020-02-14T22:46:35Z)

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.