Scaling up Mean Field Games with Online Mirror Descent

• URL: http://arxiv.org/abs/2103.00623v1
• Date: Sun, 28 Feb 2021 21:28:36 GMT
• Title: Scaling up Mean Field Games with Online Mirror Descent
• Authors: Julien Perolat, Sarah Perrin, Romuald Elie, Mathieu Lauri\`ere, Georgios Piliouras, Matthieu Geist, Karl Tuyls, Olivier Pietquin
• Abstract summary: 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. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play (FP)
• Score: 55.36153467919289
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [5.778024594615575]
  This paper proposes an online mean-field reinforcement learning algorithm for computing Nash equilibria of sequential games. MFOML is the first fully approximate multi-agent reinforcement learning algorithm for provably solving Nash equilibria. As a byproduct, we also obtain the first tractable globally convergent computational for approximate computing of monotone mean-field games.
  arXiv  Detail & Related papers  (2024-05-01T02:19:31Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Population-aware Online Mirror Descent for Mean-Field Games by Deep Reinforcement Learning [43.004209289015975]
  Mean Field Games (MFGs) have the ability to handle large-scale multi-agent systems. We propose a deep reinforcement learning (DRL) algorithm that achieves population-dependent Nash equilibrium.
  arXiv  Detail & Related papers  (2024-03-06T08:55:34Z)
• Learning Discrete-Time Major-Minor Mean Field Games [61.09249862334384]
  We propose a novel discrete time version of major-minor MFGs (M3FGs) and a learning algorithm based on fictitious play and partitioning the probability simplex. M3FGs generalize MFGs with common noise and can handle not only random exogeneous environment states but also major players.
  arXiv  Detail & Related papers  (2023-12-17T18:22:08Z)
• Regularization of the policy updates for stabilizing Mean Field Games [0.2348805691644085]
  This work studies non-cooperative Multi-Agent Reinforcement Learning (MARL) MARL where multiple agents interact in the same environment and whose goal is to maximize the individual returns. We name our algorithm Mean Field Proximal Policy Optimization (MF-PPO), and we empirically show the effectiveness of our method in the OpenSpiel framework.
  arXiv  Detail & Related papers  (2023-04-04T05:45:42Z)
• 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)
• On the Convergence of Fictitious Play: A Decomposition Approach [17.607284715519587]
  We extend the convergence results of Fictitious Play (FP) to the combinations of such games and beyond. We develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. We analyze a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge.
  arXiv  Detail & Related papers  (2022-05-03T13:04:09Z)
• Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice [62.58588499193303]
  Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. We extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and hand perfect equilibrium refinements.
  arXiv  Detail & Related papers  (2021-02-09T18:20:50Z)
• 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.