Abstract
Although the field of multi-agent reinforcement learning (MARL) has made considerable progress in the last years, solving systems with a large number of agents remains a hard challenge. Graphon mean field games (GMFGs) enable the scalable analysis of MARL problems that are otherwise intractable. By the mathematical structure of graphons, this approach is limited to dense graphs which are insufficient to describe many real-world networks such as power law graphs. Our paper introduces a novel formulation of GMFGs, called LPGMFGs, which leverages the graph theoretical concept of $L^p$ graphons and provides a machine learning tool to efficiently and accurately approximate solutions for sparse network problems. This especially includes power law networks which are empirically observed in various application areas and cannot be captured by standard graphons. We derive theoretical existence and convergence guarantees and give empirical examples that demonstrate the accuracy of our learning approach for systems with many agents. Furthermore, we extend the Online Mirror Descent (OMD) learning algorithm to our setup to accelerate learning speed, empirically show its capabilities, and conduct a theoretical analysis using the novel concept of smoothed step graphons. In general, we provide a scalable, mathematically well-founded machine learning approach to a large class of otherwise intractable problems of great relevance in numerous research fields.
Introduction: Scaling MARL to Sparse Networks
In Multi-Agent Reinforcement Learning (MARL), the complexity of finding an equilibrium—where no agent has an incentive to deviate from their strategy—explodes as the number of agents ($N$) grows. Mean Field Games (MFGs) address this by treating the population as a continuum, where agents interact with the "average" state of the collective. While Graphon Mean Field Games (GMFGs) introduced non-uniform interactions based on graph structures, they were mathematically restricted to dense graphs, where the number of edges grows quadratically with the number of nodes.
However, real-world networks—such as social networks, the internet, or biological systems—are typically sparse and follow power-law distributions. In these networks, a few "hubs" possess many connections while most nodes have very few. Standard GMFGs fail to capture these structures because they assume individual influence is diluted to zero in the limit. This paper introduces LPGMFGs ($L^p$ Graphon Mean Field Games), a framework designed to scale MARL to massive systems interacting over sparse, realistic networks.
Methodology: $L^p$ Graphons and LPGMFGs
The authors combine graph theory with game theory through several key innovations:
- $L^p$ Graphons: Unlike standard graphons, $L^p$ graphons are mathematical limits of sparse graph sequences. They represent networks where the average degree grows slowly relative to the total population.
- LPGMFG Formulation: A new Mean Field Game limit is defined where an agent's "neighborhood" is governed by the $L^p$ graphon. The authors prove that finite games converge to this continuous limit as the number of agents increases.
- Equivalence Class Discretization: To make learning tractable, the infinite agent space is partitioned into $M$ "equivalence classes" based on connectivity profiles.
- Online Mirror Descent (OMD): The authors adapt the OMD algorithm to learn equilibrium policies. They introduce "smoothed step graphons" to ensure the mathematical stability of sparse, discontinuous graph structures during optimization.
Empirical Motivation: From Dense to Power-Law Graphs
The necessity of $L^p$ graphons is highlighted by comparing traditional random graphs with real-world data.
The paper utilizes the Facebook Page-Page Dataset, consisting of mutual likes between verified pages, to demonstrate that real networks are indeed sparse and power-law-like. Synthetic power-law graphons are then used to generate test environments, such as Cyber Security and Beach Bar models, to evaluate agent decision-making under these constraints.
Key Insights and Results
- Sparsity and Influence: In dense graphs, individual influence vanishes. In sparse power-law graphs, "hubs" maintain significant influence over their neighbors even as the population scales.
- Normalization Trick: A core technical contribution is a normalization factor ($\rho_N$) based on edge density, preventing neighborhood influence from vanishing or exploding as the network scales.
- Theoretical Guarantees: The authors prove the existence of an equilibrium in LPGMFGs and show that solutions found in the infinite-agent limit are $(\epsilon, p)$-Markov-Nash Equilibria for finite $N$-agent systems.
- Accuracy and Scalability: In Cyber Security simulations, high-connectivity hubs learned more aggressive defensive strategies due to their higher infection risk—a behavior missed by dense-graph models. Empirical results show the error between finite-agent distributions and the mean-field limit decreases at a rate of $O(1/\sqrt{N})$.
Conclusion and Future Directions
While LPGMFGs significantly expand the scope of MARL, challenges remain. The current theory covers graphs where the average degree tends to infinity (even if slowly), but does not yet extend to "ultra-sparse" graphs with constant degrees. Future work may also explore continuous state/action spaces and the inclusion of "common noise" to better model financial or epidemic systems.
Summary updated