Learning Graphon Mean Field Games and Approximate Nash Equilibria

Kai Cui, Heinz Koeppl

Abstract

Recent advances at the intersection of dense large graph limits and mean field games have begun to enable the scalable analysis of a broad class of dynamical sequential games with large numbers of agents. We propose a novel discrete-time formulation for graphon mean field games as the limit of non-linear dense graph Markov games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution in sufficiently large systems. On the practical side, we provide general learning schemes for graphon mean field equilibria by either introducing agent equivalence classes or reformulating the graphon mean field system as a classical mean field system. Empirically, we demonstrate on a number of examples that the finite-agent behavior comes increasingly close to the mean field behavior for our computed equilibria as the graph size grows.

Introduction: Scaling Multi-Agent Reinforcement Learning

Multi-agent reinforcement learning (MARL) is notoriously difficult to scale. As the number of agents grows, the environment becomes highly non-stationary, and computing a Nash equilibrium becomes computationally infeasible due to the "curse of dimensionality."

A popular workaround is Mean Field Games (MFGs), which assume "weak interaction"—meaning agents react to the average distribution of the crowd rather than tracking every individual agent. However, traditional MFGs assume uniform interaction among all agents. In reality, agents interact on complex networks like social networks or power grids. This paper addresses this by utilizing Graphon MFGs, which model network structures using "graphons"—continuous mathematical limits of dense graphs. While previously studied in continuous-time mathematical settings, this work bridges the gap by providing practical, discrete-time learning algorithms.

Methods: From Finite Graphs to Graphon Equilibria

The authors propose a discrete-time formulation for GMFGs and prove that solving the infinite-agent GMFG provides an $\epsilon$-Nash equilibrium for the finite $N$-agent game.

The framework transitions from a finite graph (a) to a continuous graphon representation (b), where an agent's interaction is determined by its position in the network (c).

To compute these equilibria, two practical learning schemes are introduced:

  1. Equivalence Classes Method: This approach discretizes the continuous graphon index $\alpha$ (representing an agent's network position) into $M$ buckets. It solves the optimal control problem for each class using dynamic programming and updates the mean field recursively.
  2. Direct Reinforcement Learning: The GMFG is reformulated as a classical MFG with an extended state space (physical state + graphon index $\alpha$). Standard RL algorithms, specifically Proximal Policy Optimization (PPO), are applied in conjunction with sequential Monte Carlo methods to simulate neighborhood mean fields.

Experimental Setup

The methods were evaluated on simulated multi-agent environments using three synthetic graph structures: Uniform attachment, Ranked attachment, and Erdős–Rényi (ER) random graphs. Two custom game scenarios were tested:

  • SIS-Graphon: An epidemic game where agents decide whether to take costly precautions based on their infected neighbors.
  • Investment-Graphon: A competition game where firms invest in quality, but profits are cannibalized by high-quality neighbors.

Key Results and Insights

The research demonstrates that network position dictates optimal behavior. For instance, in the epidemic game, highly connected agents learn to take more precautions than isolated ones. In the investment game, highly connected firms invest less due to increased local competition.

Equilibrium trajectories for different graphons, showing how agent behavior ($\pi_t$) and state distribution ($\mu_t$) depend on network position $\alpha$.

Key empirical findings include:

  • Theoretical Validation: In experiments scaling up to $N=100$ agents, the maximum deviation between the $N$-agent objective and the mean field objective decreased at a rate of $\mathcal{O}(1/\sqrt{N})$, verifying the theoretical proofs.
  • Low Exploitability: Both learning methods successfully converged to plausible equilibria with low exploitability ($\epsilon \approx 2$), significantly outperforming naive MARL approaches like MAPPO, which failed to converge due to non-stationarity.

Conclusion and Future Work

While this framework provides a powerful bridge for large-scale MARL on dense graphs, it currently assumes a dense graph structure. Future work will focus on extending the theory to sparse graphs, where edge probability approaches zero, and integrating active graphon estimation for real-world deployment where agent indices are not pre-defined.

Summary updated

Abstract

Recent advances at the intersection of dense large graph limits and mean field games have begun to enable the scalable analysis of a broad class of dynamical sequential games with large numbers of agents. So far, results have been largely limited to graphon mean field systems with continuous-time diffusive or jump dynamics, typically without control and with little focus on computational methods. We propose a novel discrete-time formulation for graphon mean field games as the limit of non-linear dense graph Markov games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution in sufficiently large systems. On the practical side, we provide general learning schemes for graphon mean field equilibria by either introducing agent equivalence classes or reformulating the graphon mean field system as a classical mean field system. By repeatedly finding a regularized optimal control solution and its generated mean field, we successfully obtain plausible approximate Nash equilibria in otherwise infeasible large dense graph games with many agents. Empirically, we are able to demonstrate on a number of examples that the finite-agent behavior comes increasingly close to the mean field behavior for our computed equilibria as the graph or system size grows, verifying our theory. More generally, we successfully apply policy gradient reinforcement learning in conjunction with sequential Monte Carlo methods.
BibTeX
@inproceedings{cui2022learning,
  author = {Kai Cui and Heinz Koeppl},
  title = {{Learning Graphon Mean Field Games and Approximate Nash Equilibria}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=0sgntlpKDOz},
}
Figure