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.
To compute these equilibria, two practical learning schemes are introduced:
- 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.
- 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.
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