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: The Scalability Challenge in MARL
Multi-agent reinforcement learning (MARL) faces a significant computational hurdle as the number of agents ($N$) increases. Traditional methods struggle with the exponential growth of the state-action space. Mean Field Games (MFGs) offer a solution by approximating interactions: instead of tracking every individual connection, agents interact with the "average" state of the population.
However, standard MFGs typically assume "weak interaction," which mathematically translates to a dense graph where every agent is connected to a significant fraction of the population. While Graphon Mean Field Games (GMFGs) formalized this using graphons (the limit of dense graph sequences), they remain restricted to these dense regimes and fail to capture the nuances of real-world connectivity.
Beyond Dense Graphs: The Need for $L^p$ Graphons
Real-world networks—ranging from social media connections to the human brain—are rarely dense. Instead, they are typically sparse and often follow a power-law distribution, where a few "hub" nodes have many connections while most have very few. Standard graphon models fail to capture these heavy-tailed structures because they are mathematically restricted to dense regimes.
As shown in the figure above, the degree distribution of a real Facebook graph and a power-law graph differs significantly from the narrow distribution of a standard Erdős-Rényi (ER) graph. This paper introduces LPGMFGs, a framework leveraging $L^p$ graphons to model these sparse, realistic network structures.
Methodology: LPGMFGs and Smoothed Step Graphons
The core of the LPGMFG framework is the use of $L^p$ graphons—symmetric integrable functions that represent the limits of sparse graph sequences. This allows for modeling interactions where the number of edges grows much slower than $N^2$.
Key Technical Contributions:
- LPGMFG Formulation: A Mean Field Game where agent-population interactions are weighted by an $L^p$ graphon.
- Smoothed Step Graphons: A novel mathematical technique that approximates discontinuous graphons with Lipschitz continuous ones, ensuring the underlying mathematics remains tractable for convergence proofs.
- Online Mirror Descent (OMD): The authors adapt the OMD algorithm to the LPGMFG setting, allowing agents to iteratively update their policies toward a Graphon Mean Field Equilibrium (GMFE).
- Equivalence Class Method: To enable computation, the continuous agent space is discretized into $M$ equivalence classes, treating agents within each class as identical.
Empirical Validation and Key Results
The framework was tested on synthetic power-law benchmarks and a real-world Facebook Page-Page Network (3,892 nodes, ~17,500 edges).
Key Findings:
- Theoretical Convergence: The authors proved that as $N \to \infty$, the finite game's Nash Equilibrium converges to the LPGMFG solution.
- Algorithmic Efficiency: In "Cyber Security" and "Beach Bar" simulations, exploitability—a measure of deviation from equilibrium—decreased exponentially with OMD iterations.
- Qualitative Realism: In the Cyber Security scenario, "hub" agents (those with high connectivity) learned more aggressive defensive strategies due to their higher risk of infection, a behavior not captured by dense-graph models.
- Scalability: The $L^1$ error between the empirical distribution and the theoretical limit followed the predicted $O(1/\sqrt{N})$ rate, confirming the model's accuracy for large systems.
Conclusion and Future Directions
LPGMFGs provide a mathematically rigorous and scalable approach to MARL on sparse networks. By moving beyond the dense-graph limitation, this work opens the door to modeling complex real-world systems more accurately.
Future work includes addressing ultra-sparse graphs (where average degree is constant), relaxing Lipschitz continuity assumptions for more general graphons, and extending the model to dynamic networks where the underlying structure evolves over time.
Summary updated