Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications

• URL: http://arxiv.org/abs/2007.03458v2
• Date: Mon, 26 Oct 2020 11:18:44 GMT
• Title: Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications
• Authors: Sarah Perrin, Julien Perolat, Mathieu Lauri\`ere, Matthieu Geist, Romuald Elie, Olivier Pietquin
• Abstract summary: We first present a theoretical convergence analysis of the continuous time Fictitious Play process and prove that the induced exploitability decreases at a rate $O(frac1t)$. We provide hereby for the first time converging learning dynamics for Mean Field Games in the presence of common noise.
• Score: 36.76207130435722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we deepen the analysis of continuous time Fictitious Play learning algorithm to the consideration of various finite state Mean Field Game settings (finite horizon, $\gamma$-discounted), allowing in particular for the introduction of an additional common noise. We first present a theoretical convergence analysis of the continuous time Fictitious Play process and prove that the induced exploitability decreases at a rate $O(\frac{1}{t})$. Such analysis emphasizes the use of exploitability as a relevant metric for evaluating the convergence towards a Nash equilibrium in the context of Mean Field Games. These theoretical contributions are supported by numerical experiments provided in either model-based or model-free settings. We provide hereby for the first time converging learning dynamics for Mean Field Games in the presence of common noise.

Related papers

• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  We develop learning dynamics that are payoff-based, convergent, rational, and symmetric between the two players. In the matrix game setting, the results imply a complexity of $O(epsilon-1)$ to find the Nash distribution. In the game setting, the results also imply a complexity of $O(epsilon-8)$ to find a Nash equilibrium.
  arXiv  Detail & Related papers  (2024-09-02T20:07:25Z)
• Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games [31.989723099872638]
  Last-iterate behaviors of learning algorithms in two-player zero-sum games have been extensively studied. Most existing results establish these properties under the assumption that the game is time-independent. In this paper, we investigate the last-iterate behaviors of optimistic and extra-gradient methods in the constrained periodic games.
  arXiv  Detail & Related papers  (2024-06-15T11:50:36Z)
• Graphon Mean Field Games with a Representative Player: Analysis and Learning Algorithm [14.647775453098513]
  We prove the existence and uniqueness of the graphon equilibrium with mild assumptions, and show that this equilibrium can be used to construct an approximate solution for finite player game on networks. An online oracle-free learning algorithm is developed to solve the equilibrium numerically, and sample complexity analysis is provided for its convergence.
  arXiv  Detail & Related papers  (2024-05-08T04:44:16Z)
• Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations [98.5802673062712]
  We introduce temporally-coupled perturbations, presenting a novel challenge for existing robust reinforcement learning methods. We propose GRAD, a novel game-theoretic approach that treats the temporally-coupled robust RL problem as a partially observable two-player zero-sum game.
  arXiv  Detail & Related papers  (2023-07-22T12:10:04Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  We develop a flexible approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite) The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, exponential/multiplicative weights for learning in finite games, optimistic and bandit variants of the above, etc.
  arXiv  Detail & Related papers  (2022-06-08T14:30:38Z)
• Scaling up Mean Field Games with Online Mirror Descent [55.36153467919289]
  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)
  arXiv  Detail & Related papers  (2021-02-28T21:28:36Z)
• Provable Fictitious Play for General Mean-Field Games [111.44976345867005]
  We propose a reinforcement learning algorithm for stationary mean-field games. The goal is to learn a pair of mean-field state and stationary policy that constitutes the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-10-08T18:46:48Z)

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.