Learning Discrete-Time Major-Minor Mean Field Games
- URL: http://arxiv.org/abs/2312.10787v1
- Date: Sun, 17 Dec 2023 18:22:08 GMT
- Title: Learning Discrete-Time Major-Minor Mean Field Games
- Authors: Kai Cui, G\"ok\c{c}e Dayan{\i}kl{\i}, Mathieu Lauri\`ere, Matthieu
Geist, Olivier Pietquin, Heinz Koeppl
- Abstract summary: 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.
- Score: 61.09249862334384
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent techniques based on Mean Field Games (MFGs) allow the scalable
analysis of multi-player games with many similar, rational agents. However,
standard MFGs remain limited to homogeneous players that weakly influence each
other, and cannot model major players that strongly influence other players,
severely limiting the class of problems that can be handled. We propose a novel
discrete time version of major-minor MFGs (M3FGs), along with a learning
algorithm based on fictitious play and partitioning the probability simplex.
Importantly, M3FGs generalize MFGs with common noise and can handle not only
random exogeneous environment states but also major players. A key challenge is
that the mean field is stochastic and not deterministic as in standard MFGs.
Our theoretical investigation verifies both the M3FG model and its algorithmic
solution, showing firstly the well-posedness of the M3FG model starting from a
finite game of interest, and secondly convergence and approximation guarantees
of the fictitious play algorithm. Then, we empirically verify the obtained
theoretical results, ablating some of the theoretical assumptions made, and
show successful equilibrium learning in three example problems. Overall, we
establish a learning framework for a novel and broad class of tractable games.
Related papers
- Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning [19.543995541149897]
We provide a methodology to extend any finite-player, possibly asymmetric, game to an "induced MFG"
First, we prove that $N$-player dynamic games can be symmetrized and smoothly extended to the infinite-player continuum via explicit Kirszbraun extensions.
For certain games satisfying monotonicity, we prove a sample complexity of $widetildemathcalO(varepsilon-6)$ for the $N$-agent game to learn an $varepsilon$-Nash up to symmetrization bias.
arXiv Detail & Related papers (2024-08-27T16:11:20Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
We consider the problem of decentralized multi-agent reinforcement learning in Markov games.
We show that no algorithm attains no-regret in general-sum games when executed independently by all players.
We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
arXiv Detail & Related papers (2023-03-22T03:28:12Z) - Mean Field Games on Weighted and Directed Graphs via Colored Digraphons [26.405495663998828]
Graphon mean field games (GMFGs) provide a scalable and mathematically well-founded approach to learning problems.
Our paper introduces colored digraphon mean field games (CDMFGs) which allow for weighted and directed links between agents.
arXiv Detail & Related papers (2022-09-08T15:45:20Z) - 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) - Learning in Mean Field Games: A Survey [44.93300994923148]
Mean Field Games (MFGs) rely on a mean-field approximation to allow the number of players to grow to infinity.
Recent literature on Reinforcement Learning methods to learnlibria and social optima in MFGs.
We present a general framework for classical iterative methods to solve MFGs in an exact way.
arXiv Detail & Related papers (2022-05-25T17:49:37Z) - Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the
Gap Between Learning in Extensive-Form and Normal-Form Games [76.21916750766277]
We show that the Optimistic Multiplicative Weights Update (OMWU) algorithm can be simulated on the normal-form equivalent of an EFG in linear time per iteration in the game tree size using a kernel trick.
Specifically, KOMWU gives the first algorithm that guarantees at the same time last-iterate convergence.
arXiv Detail & Related papers (2022-02-01T06:28:51Z) - Signatured Deep Fictitious Play for Mean Field Games with Common Noise [0.0]
Existing deep learning methods for solving mean-field games (MFGs) with common noise fix the sampling common noise paths and then solve the corresponding MFGs.
We propose a novel single-loop algorithm, named signatured deep fictitious play, by which we can work with the unfixed common noise setup to avoid the nested-loop structure.
The proposed algorithm can accurately capture the effect of common uncertainty changes on mean-field equilibria without further training of neural networks.
arXiv Detail & Related papers (2021-06-06T23:09:46Z) - 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)
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.