Scaling up Mean Field Games with Online Mirror Descent
arXiv:2103.00623
Abstract
We address scaling up equilibrium computation in Mean Field Games (MFGs) using Online Mirror Descent (OMD). We show that continuous-time OMD provably converges to a Nash equilibrium under a natural and well-motivated set of monotonicity assumptions. This theoretical result nicely extends to multi-population games and to settings involving common noise. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play (FP). We empirically show that OMD scales up and converges significantly faster than FP by solving, for the first time to our knowledge, examples of MFGs with hundreds of billions states. This study establishes the state-of-the-art for learning in large-scale multi-agent and multi-population games.
References in corpus (8)
- Adapting a Kidney Exchange Algorithm to Align with Human Values
- Pattern formations driven by cyclic interactions: a brief review of recent developments
- Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
- Spirals and heteroclinic cycles in a spatially extended Rock-Paper-Scissors model of cyclic dominance
- Solving Nonlinear and High-Dimensional Partial Differential Equations via Deep Learning
- Learning in anonymous nonatomic games with applications to first-order mean field games
- Provable Fictitious Play for General Mean-Field Games
- The route to chaos in routing games: When is Price of Anarchy too optimistic?