Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games
This work addresses the challenge of efficiently finding equilibria in complex multi-agent games, which is incremental as it builds on prior dynamics but offers improved convergence and unified time scales.
The authors tackled the problem of approximating mixed Nash equilibria in continuous multi-player zero-sum games with mean-field interactions by proposing a mean-field gradient descent dynamics with momentum and exponential time-averaging, achieving an exponential convergence rate to the equilibrium in the regularized case, which improves upon previous polynomial rates.
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.