Scaling Mean Field Games by Online Mirror Descent

Julien Pérolat (DeepMind), Sarah Perrin (University Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRIStAL), Romuald Elie (DeepMind), Mathieu Laurière (Google Research), Georgios Piliouras (Singapore University of Technology and Design), Matthieu Geist (Google Research), Karl Tuyls (DeepMind), Olivier Pietquin (Google Research)

Abstract

We address the scaling of equilibrium computation in Mean Field Games (MFGs) by 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. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play. We empirically show that OMD scales and converges significantly faster than Fictitious Play by solving, for the first time to our knowledge, examples of MFGs with hundreds of billions states.