Learning Mean Field Control on Sparse Graphs
Authors: Christian Fabian
Kai Cui
Heinz Koeppl
Venue: ICML 2025 poster (2025)
Keywords: Mean Field Control
Large Graphs
Sparse Networks
Multi-Agent Reinforcement Learning
Primary area: reinforcement_learning->multiagent

Abstract: Large agent networks are abundant in applications and nature and pose difficult challenges in the field of multi-agent reinforcement learning (MARL) due to their computational and theoretical complexity. While graphon mean field games and their extensions provide efficient learning algorithms for dense and moderately sparse agent networks, the case of realistic sparser graphs remains largely unsolved. Thus, we propose a novel mean field control model inspired by local weak convergence to include sparse graphs such as power law networks with coefficients above two. Besides a theoretical analysis, we design scalable learning algorithms which apply to the challenging class of graph sequences with finite first moment. We compare our model and algorithms for various examples on synthetic and real world networks with mean field algorithms based on Lp graphons and graphexes. As it turns out, our approach outperforms existing methods in many examples and on various networks due to the special design aiming at an important, but so far hard to solve class of MARL problems.

Learning Mean Field Control on Sparse Graphs
Christian Fabian Kai Cui
Heinz Koeppl 12
Abstract
focus of MFC are cooperative scenarios where agents op- timize common goal. The idea of MFC and MFGs is to abstract large, homogeneous crowds of small agents into a single probability distribution, the mean field (MF). While MFC and MFGs have been used in various areas ranging from pedestrian flows (Bagagiolo et al., 2019; Achdou & Laurière, 2020) to finance (Carmona & Delarue, 2018; Car- mona Laurière, 2023) and oil production (Bauso et al., 2016), the assumption of indistinguishable agents is not fulfilled in many applications.
Large agent networks are abundant in applica- tions and nature and pose difficult challenges in the field of multi-agent reinforcement learning (MARL) due to their computational and theo- retical complexity. While graphon mean field games and their extensions provide efficient learn- ing algorithms for dense and moderately sparse agent networks, the case of realistic sparser graphs remains largely unsolved. Thus, we propose a novel mean field control model inspired by local weak convergence to include sparse graphs such as power law networks with coefficients above two. Besides a theoretical analysis, we design scalable learning algorithms which apply to the challenging class of graph sequences with finite first moment. We compare our model and algo- rithms for various examples on synthetic and real world networks with mean field algorithms based on Lp graphons and graphexes. As it turns out, our approach outperforms existing methods in many examples and on various networks due to the special design aiming at an important, but so far hard to solve class of MARL problems.
A particularly important class of MARL problems are those with many connected agents. Initially, these agent networks were modeled by combining the graph theoretical concept of graphons (Lovász, 2012) with MFGs, resulting in graphon MFGs (GMFGs) (Caines & Huang. 2019; 2021; Cui & Koeppl, 2022; Zhang et al., 2024) and graphon MFC (Hu et al., 2023b). Since GMFGs only model often unrealis- tic dense graphs, subsequently mean field models based on Lp graphons (Borgs et al., 2018b; 2019) and graphexes (Veitch & Roy, 2015; Caron & Fox, 2017: Borgs et al., 2018a) were developed, called LPGMFGs and GXMFGs, respectively (Fabian et al., 2023; 2024). While these models facilitate learning algorithms in moderately sparse networks, they exclude sparser topologies. Formally, (LP)GMFGs and GXMFGs are designed exclusively for graphs with ex- pected average degree going to infinity which, for example, excludes power laws with a coefficient above two.
1. Introduction
Despite the rapid developments in the field of multi-agent reinforcement learning (MARL) over the last years, systems with many agents remain hard to solve in general (Canese et al., 2021; Gronauer & Diepold, 2022). Mean field games (MFGs) (Caines al., 2006; Lasry & Lions, 2007) and mean field control (MFC) (Andersson & Djehiche, 2011; Bensoussan et al., 2013) are a promising way model large agent problems in computationally tractable manner and to provide solid theoretical framework at the same time. While MFGs consider competitive agent populations, the
The learning literature contains various approaches to find- ing optimal behavior in MFGs and MFC, see Laurière et al. (2022a) for an overview. For example, Subramanian et al. (2022) develop a decentralized learning algorithm for MFGs where agents independently learn policies, while Guo et al. (2019; 2023) focus on Q-learning methods for general MFGs. Various MFC learning approaches exist (Ruthotto et al., 2020; Carmona et al., 2023; Gu et al., 2023), but we are aware of only one work by Hu al. (2023b) which learns policies for MFC on dense networks, but not sparse ones.
'Department of Electrical Engineering and Information Tech- nology, Technische Universität Darmstadt, Germany Hessian Center for Artificial Intelligence (hessian.Al). Correspondence to: Heinz Keeppl <heinz, @ttu <hein...oeppeuudddsstaaaad... darmstadt.d>>.
Many empirical networks of high practical relevance are considerably sparser than the topologies covered by (LP)GMFGs and GXMFGs. Examples of sparse empirical networks which at least to some extent follow power laws with coefficients between two and three include the inter- net (Vázquez et al., 2002), coauthorship graphs (Goh et al.,
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Mean Field Control on Sparse Graphs
2002) and biological networks (Dorogovtsev & Mendes, 2002). These topologies are particularly challenging to ana- lyze (Dorogovtsev al., 2002), especially in combination with particle dynamies (Lacker et al., 2023). Most important in our context, the high fraction of low degree nodes in these networks renders classical mean field approximations and their LPGMFG and GXMFG extensions highly inaccurate.
set and Ey is the edge set of the corresponding graph Gy- In this paper, focus growing graph sequences where the expected average degree remains finite in the limit while the degree variance may diverge to infinity. To formalize the properties of the graph sequences we are focusing on, we first require a suitable graph convergence concept. We choose local weak convergence in probability which means that local node neighborhoods converge to neighborhoods in a limiting model. The definition below states local weak convergence, for details see e.g. Lacker et al. (2023).
Both LPGMFGs and GXMFGs assume that the average expected degree diverges to infinity ensure that the neigh- borhoods of crucial agents are accurately approximated by a mean field. Since this assumption is inaccurate for various empirical networks, we require a different modeling and learning approach. To learn policies for such very sparse networks, we employ a suitable graph theoretical conver- gence principle, local weak convergence (Van Der Hofstad, 2024). Many established graph theoretical models like the configuration model (Bollobás, 1980), the Barabási-Albert model (Barabási & Albert, 1999) and the Chung-Lu Lu model (Chung & Lu, 2006) can model graph sequences converging in the local weak sense. Most importantly in our context, this includes graph sequences with finite average expected degree and power law networks with coefficient above two, which are neither covered by Lp graphons nor graphexes.
Definition 2.1 (Local weak convergence in probability). sequence of finite graphs (Gx)N converges in probability in the local weak sense to random element G of G if for all continuous and bounded functions f G + R
1 Σ ((C,(Gx))==BI1)) N-0o N
lim
in probability
[EIN]
where Crg (Gx) denotes the connected component of us GN with root by and G is the set of isomorphism classes of connected rooted graphs.
To obtain meaningful theoretical results and hence practical approximations for large graphs in the next sections, we focus on graph sequences converging in the local weak sense, which we formalize with the next assumption.
Leveraging local weak convergence, we formulate our new local weak mean field control (LWMFC) model. LWMFC provides a theoretically motivated framework for learning agent behavior in challenging large empirical networks where the average expected degree finite, but the degree variance may diverge to infinity. On the algorithmic side, we provide two systems approximation for LWMFC and corresponding learning algorithms to approximately learn optimal behaviour in these complex agent networks. Finally, we evaluate our novel LWMFC learning approach for mul- tiple problems on synthetic and real-world networks and compare to different existing methods mentioned above. Overall, our contributions can be summarized as:
Assumption 2.2. The sequence (GN) NEN converges in probability in the local weak sense to some random element G g
The class of random graph sequences fulfilling Assump- tion 2.2 covers many famous graph theoretical frameworks which are frequently used in the literature. We will briefly discuss three particularly important types of these models, namely configuration models, preferential attachment mod- els and Chung-Lu graphs. We point to Van Der Hofstad (2024) for an extensive introduction and theoretical details and for more random graph models converging in the local weak sense.
We introduce LWMFC to model large cooperative agent populations on very sparse graphs with finite expected average degree;
Configuration models. The configuration model (Bender & Canfield, 1978; Bollobás, 1980; Molloy & Reed, 1995; 1998) (CM) is arguably one of the most established ran- dom graph models. The basic mechanism of the CM is to start with a fixed and arbitrary degree sequence. Then, a multigraph is randomly generated with the prescribed de- gree distribution which means that the graph can contain self-edges and double edges between pairs of nodes.
We give rigorous theoretical analysis and motivation for LWMFC;
We provide a two systems approximation and scalable learning algorithms for LWMFC:
We show the capabilities of our LWMFC learning ap- proach on synthetic and real world networks for differ- ent examplary problems.
The CM is known to converge under suitable and moderate assumptions in the local weak sense in probability (Van Der Hofstad, 2024, Theorem 4.1). However, the CM gener- ates multigraphs instead of simple graphs and the number of multiedges increases drastically as the vertex degrees
2. Locally Weak Converging Graphs
In the following, let (Gn) = (VN, Ex)NeN be a grow- ing sequence of random graphs where Vy denotes the vertex
2

---

Learning Mean Field Control on Sparse Graphs
increase (Bollobás, 1998). Consequently, the CM is subopti- mal for generating simple graphs with significant fraction of high degree nodes such as power law networks.
networks, shown in the next sections.
Advantages over graphons and graphexes. Local weak converging graph sequences such those generated by CM, BM or CL can model sparser, and thus often more realistic topologies than those captured by Lp graphons and graphexes. Figure 1 provides an illustration of how Lp graphons, graphexes, and CL. graphs compare to a real world subsampled YouTube network (Mislove, 2009; Kunegis, 2013). Mathematically, both Lp graphons and graphexes are limited to graph sequences were the average degree diverges to infinity. Locally weak converging graph sequences, on the other hand, can capture sparse and often more realis- tic topologies. The usefulness of models like the CM, BA model and CL graphs is reflected in their frequent use in various research areas. However, formulating mean field approach based on these graph theoretical models is chal- lenging due to their high number of low degree nodes.
Preferential attachment models. To model random graphs with power law features, Barabási & Albert (1999) introduced the famous Barebási-Allert (BA) model. The original BA model was subsequently extended in various ways for different applications, see Piva et al. (2021) for overview. The BA model depicts graphs that grow over time by adding new nodes and edges to the topology. Since new nodes are more likely to be connected to highly connected nodes in the current graph, these models are often referred to as preferential attachment models.
Preferential attachment models under suitable conditions converge in the local weak sense in probability, see Van Der Hofstad (2024, Theorem 5.8) for details. The BA model, for example, generates power law networks with a coefficient of exactly three (Bollobás et al., 2001). In many applications, however, it is beneficial to also consider graphs with power law coefficient deviating from three to capture different empirical graph topologies.
3. The Finite Model and Its Limit
Denote by ((t) the set of probability distributions over a finite set X' and define [N] [1....,NN for any N E N.
Chung-Lu graphs. The Chung-Lu (CL) random graph model (Aiello et al., 2000; 2001; Chung & Lu, 2002: 2006) provides an efficient way to model large, sparse networks (Fasino et al., 2021). To generate a random CL graph with N N nodes, first specify a weight vector w IN-N with one weight W/ E R4 for each node i E NN). Then, two nodes i and j are connected with probability uy - w,/W, independently of all other node pairs and with normalization factor v0 == Eisks Wk- Intuitively, a node with high weight is more likely to have many connections than a node with small weight.
Finite model. Assume some finite state space X, fi- nite action space U and finite and discrete time horizon T = (0, (O..... T 1} with terminal time point T are given. Furthermore, there are N E N agents connected by some graph G2 = (Vv. Ex) with vertex set Vx and edge set Ex. Here, the random state of agent E [N] at time E T is denoted by X All agents VI S VN with degree E N share a common policy n. at all time points E T. The empirical k-degree MF is defined as
N₂ Me
1
Σ
ōXM, E P(X)
V
Sequences of CL graphs fulfill Assumption 2.2 under mild technical assumptions, see Van Der Hofstad (2024, Theorem 3.18) for a formal statement. Most importantly, the average expected degree has to converge to a finite limit, which perfectly aligns with our goal to model very sparse networks. Throughout the paper, we use the running example of power law degree distributions with coefficient y > observed in many real world networks to some extent (Newman, 2003; Kaufmann & Zweig, 2009; Newman et al., 2011).
VE[N]:BLEV
for all L E T and k E N. Define the overall empirical MF sequence as UNN" = (u. N.1 , ,,,² " P(x) Each policy T² E P( in the policy ensemble (T ,)....) E P(u) xxxx"xxxx takes into account the cur- rent state of the respective agent i with & neighbors and its neighborhood CN E g = (G E P(X) G.G e N²). Our learning algorithms also apply to other policy types, e.g., in our experiments we consider computationally ef- ficient policies only depending the current agent state. Then, the model dynamics are
Example 1 (Power law). In our work, a power law is zeta distribution with parameter 7 > 2 such that P(dcg(v)= = where ((7) is the Riemann zeta function <(>)= = Σド= J A power law degree distribution has a finite expectation [))e <(> 1)/((r) for y > 2.
=
U. ~ क (IX:)) GNY)
and
Large, sparse power law networks of the above form can be efficiently generated by the CL framework (Fasino et al., 2021). Note that our methods apply to all distributions meet- ing Assumption 2.2 and perform well on many empirical
N ~ P UNN G.
for an agent with degree k, t E T, i.dd initial distribution
No E P(Y), and transition kernel P X x u x P (x) +
3

---

Learning Mean Field Control on Sparse Graphs
Lp graphon greph.
Graphex graph
Chung lu graph
Real YT network
LagiDegrve
logDeerre
LogiCrg
degree
100
Figure I. Four networks, first two generated by Lp graphon and graphex, third is CL graph and fourth is real subsampled YouTube (YT) network (Mislove, 2009; Kunegis. 2013), highly connected nodes are depicted larger. Each network has around 14.5k nodes 13k edges, except graphex has around 16.5k edges; all networks are plotted in the prefuse force directed layoul (software: eytoscape). While the Lp graphon graph lacks sufficiently many high degree nodes, the tail of the graphex degree distribution too heavy. contrast, the CL graph is qualitatively close to the real YT network.
P (X).. Note that the theory and subsequent learning algo- rithms extend to degree dependent transition kernels pa The policies are chosen to maximize the common objective
Theorem 3.1 (MF convergence). Under Assumption 2.2, for any fixed policy ensemble n, the empirical MFs converge to the limiting MFs such that for all k: E M and all t 'T
N.k P4 + pl
in probability for N 00.
J (m) (N)
Σ r(
The MF convergence from Theorem 3.1 enables us to derive a corresponding convergence result for the objective func- tion under a standard continuity assumption on the reward. Assumption 3.2. The reward function r: P(()) R is continuous.
with reward function r P(X) + R. Our model also covers reward functions with actions as inputs by using an extended state space X' (X' x U) and splitting each time step & T into two.
With the above assumption in place, we establish the con- vergence of the objective function in the finite system to the one the limiting LWMFC model.
Limiting LWMFC system. In the limiting LWMFC sys- tem, the MF for each degree evolves according to
Proposition 3.3 (Objective convergence). Under Assump- tions 2.2 and 3.2 and for any fixed policy ensemble n, the common objective in the finite system converges to the limit- ing objective, i.e.
1941 = / P.
= (x)
Σ Pm [G) (M() = G xr = x)
ZEN
GEge
n (u x, G) (- GI,
J (T) + J(T) in probability for N + 00.
NEW
We leverage these findings to show that for a finite set of policy ensembles, the optimal policy for the limiting system in the set is also optimal in all sufficiently large finite sys- tems. Therefore, if one wants to know the optimal ensemble policy for arbitrary, large agent system, it suffices find the optimal ensemble policy in the limiting system once which is formalized by Corollary 3.4.
with i.i.d. initial distribution n E P(X) and where g* the set of k-neighborhood distributions before. As in the finite system, define the limiting MF ensemble μe == (nt ... E ~ and the corresponding reward in the limiting system is J (Tx = r(u)..
.)
Theoretical results. Next, we show the strong theoretical connection between the finite and limiting LWMFC system. The following theoretical results built on the assumption that the underlying graph sequence converges in the local weak sense, formalized by Assumption 2.2. The proofs are in Appendix A. We first state empirical MF convergence to the limiting MFs.
Corollary 3.4 (Optimal policy). Assume some set (Ti...., of M < oo policy ensembles is given and that w.l.o.g. J(T1) J(T:) for all i E [M] with i # 1. Under Assumptions 2.2 and 3.2 for some N N, m is optimal in all finite systems of size N > No such that
JN (MT)) > max J (T:)
sE[M],i51

---

Learning Mean Field Control on Sparse Graphs
4. The Two Systems Approximation
the underlying sparse graph structure. Our two systems approximation consists of system for small degree agents with at most k neighbors and another one for agents with more than k" connections, where k" E NN is some arbitrary, but fixed finite threshold. Define an approximate MF je for each & E [k*] and furthermore summarize all agents with more than k connections into the infinite approximate MF f and define j (f' ..... f. , Based on Heuristic I, we assume that all agents with more than k" neighbors observe the same neighborhood state distribution
In limiting systems on sparse graphs, the state evolution and optimal policy of an agent potentially depend on the entire network (Lacker & Soret, 2022). Calculating Px (G) (14) G 2 = 2) at time t T in the limiting system requires all possible t-hop neighborhood degree- state distributions where t-hop neighborhoods include all agents with distance of at most edges to the initial agent. Unfortunately, by Lemma 4.1 the number of t-hop neigh- borhoods grows at least exponentially with the degree k in important classes of locally weak converging graphs se- quences, such CL graphs with power laws above two.
G 0C (it)
kP(deg(v) = ki) 14;
IE [eg((u)]
A= +1
Lemma 4.1. In the limiting system, the number of possible hop degree-state neighhorhood distributions of agents with degree k I at time 'T in the worst case, e.g. CL power law, is Z (2poly(b)).
h PP(de(()) = =1)a
E E(de(()) v)]
The unified approximate neighhorhood state distribution Gge allows us to state an approximate, simplified version of the MF forward dynamics for high degree agents given by
Just neglecting high degree nodes in the model might appear as reasonable approximation to reduce computational com- plexity. However, the heavy tail of a degree distribution with finite expectation and infinite variance makes this approach highly inaccurate, as Example 2 illustrates.
A == P L.j.
Σ Eap (ul,,0r(0 P [,,,u, u, GF (u')) JrM
Example 2. In power law graph with y = 2.5, around 96% of nodes have degree of at most five. However, these 96% of low degree nodes only account for roughly two thirds of the expected degree, formally Σi= /-->/ /C(>-1) < 0.68. Nodes with a degree of at most ten still only account for around 76% of the expected degree.
where all agents with more than k* connections follow the same policy T. E Txxx)xxXx(Xx and where the sum is over all (a,, u) E X' x U. The approximate neighborhood of an agent with degree & E [R*]] at each time t E T is sampled from G (it) Mult(k, G (it), i.c. ( is multinomial with k trials and probabilities G7 (A) for each x E X. Using Heuristic 1, the approximation yields for each h: E [K*] the MF forward dynamics
Two systems approximation. For the subsequent two systems approximation, we first require a heuristic on the neighbor degree distribution for a given node.
pr.k Pi = 1bg L.
Heuristic 1. For an arbitrary node v' E V the degree distri- bution of its neighbor v E V is approximately
Σ (x) (G:: = G) n. (w| G. (0f(-11,000 Gz,, a.
P(deg(v) = h deg((') = W,, (v', E) k- E-P(deg(v) = k)
where the sum is over all (I, u, G) E X x
2 Ev'ER k" P(deg(u) k")
Extensive approximation. In Appendix B we derive a
second, extensive approximation
Heuristic 1 is good approximation for some sequences of locally weak converging graphs, such as CL graphs (Jackson et al.. 2008, Chapter 4), and thus reasonable in our setup. The idea of Heuristic 1 is the following: one fixes any node o' E V and considers its neighbors, high degree nodes are more likely to be connected to v' than lowly connected ones. Instead of the overall degree distribution, we thus weight each probability by its degree and normalize accordingly. The result is an approximate neighbor degree distribution accounting for the increased probability of highly connected neighbors.
P (Gi+1 (1.) = G, G,I++1=10 =x)
Σ 3
Σ PT (G) (Hr) = == = =x)
G'egt x'EN'
Σ Luel
n*
I',
Σ
II Mult Pa.y (a2i)
( 3 Easedy II. Mult pa (a3.m)
To address the complexity of the limiting system, we provide an approximate limiting system based on Heuristic and
EaseA .)) Ilam Pj (mma)
5

---

Learning Mean Field Control on Sparse Graphs
of the finite agent neighborhoods in the LWMFC model where we use the abbreviated notation Pj.m(a2) (az) (P (deg(v) - m v) E E) nuth (s;)) Here, the idea is to go beyond the previous multinomial assumption G) ~ Mult(k, G3 (f)) and to use state-degree neigh- borhood distributions a2 E AG" c) and state-state- degree neighborhood distributions 03 E ( ,c to capture agents changing from X' to x' E X' at a time step. We provide the extensive approximation derivation and corresponding definitions of sets like (G",, .c) and A5 G", c) in Appendix B. As we will see in the follow- ing, the extensive approximation often shows a moderately higher accuracy than our first approximation. However, the accuracy boost entails a significantly higher computational complexity due to multiple sums over sets like (5" and (G, G", c). Thus, our first approximation is more practical since it combines reasonable accuracy with low computational complexity while the extensive approxima- tion is computationally too expensive for our purposes.
Algorithm 1 LWMFFC Policy Gradient
1:
for iterations n = 2, ......... do for time steps t O..... Bien 1 do Sample LWMFC MDP action n, # ( (4)).
3:
4:
Compute reward r(u)), next MF M441. termina- tion flag de+1 E {0,1).
5:
end for Update policy # on minibatches
6:
C
{(u,, Te, Te, dr+1, (14411414140001 (441) of length bjon-
end for
MARL on real networks. In addition to assuming knowl- edge of the model and computing the limiting MFC MDP equations, we may also directly learn on real network data without such model knowledge in a MARL manner. To do so, still apply policy gradient RL to solve an assumed MFC MDP, but substitute samples from the real network into Fr At the same time, we let each node perform its actions according to the sampled T. ~ #T((T. 1t). This approach is well justified by the previous theory and ap- proximation, as for sufficiently large networks the limiting system and therefore also its limiting policy gradients are well approximated by this procedure.
5. Learning Algorithms
To solve the MARL problem of finding optimal policies for each class of k-degree nodes, we propose two methods based on reducing the otherwise intractable many-agent graphical system to single-agent MFC MDP. The first approach in Algorithm 1 is based on solving the resulting limiting MFC MDP under the parameters of the real graph, using the previously established two systems approximation. The second approach in Algorithm instead directly learns according to single-agent RL that solves the MFC MDP by interacting with the real graph.
Algorithm 2 L.WMFMARI. Policy Gradient
1: for iterations n = 1, 2,.................. do
for time steps t O..... Bee 1 do
3: Sample LWMFC MDP action T, # (TT [1))-
4: for node = 1,..., N do
5: Sample per-node action U₁ with degree K; = oc if K2 > k- end for
Tt k: (Ust Xix)
RL in MFC MDP. The two system approximation re- duces the complexity of otherwise intractable large in- teracting systems on networks to the MFs of each de- gree. The system state at any time is then given by low-degree MFs pt, pi....,," 1 and high-degree MF n briefly n, = (H) uu, u4 ,,(). possible state evolutions depend only on the analogous set of low-degree and high-degree policies at that time, n, = (m), ......, # m)²). Therefore, choosing æ, fully defines the state transition of the overall system, and is thus considered as the high-level action in the MFC MDP. In- troducing a high-level policy º to output ग. ~ (TT 1t) allows us to solve for an optimal set of policies by solving the MFC MDP for optimal म, since the limiting MF dynam- ics are deterministic. Finally, the MFC MDP solved by applying single-agent policy gradient RL, resulting in Algo- rithm 1. In practice, we use proximal policy optimization (Schulman et al., 2017). To lower the complexity of the resulting MDP, we parametrize policies as distributions over actions given the node state, o. E x
6:
7:
Perform actions, observe reward re. next MF p441 termination flag de+1 E 13. end for Update policy *0 minibatches b
C
Given a state pe, the
{(M,, Te, Te, de+1, 1220 of length bien- 10: end for
The approach results in Algorithm 2 and has advantages. Firstly, the algorithm does not assume model knowledge and is therefore a true MARL algorithm, in contrast to solving the limiting MFC MDP. Secondly, the algorithm avoids potential inaccuracies of the two systems approximation, as we will see in Section 7, since it directly interacts with real network of interest. Lastly, in contrast to standard independent and joint learning MARL methods, the method is rigorously justified by single-agent RL theory and avoids exponential complexity in the number of agents respectively.
6

---

Learning Mean Field Control on Sparse Graphs
Table 1. Average expected total variation Aμ = 2 E | Ai ue]l=] E [o, 1] of MF fa and empirical MF juc = Σ. ox; (1 standard deviation, 50 trials), for the four models for four problems on eight real-world networks. Extensive LWMFC* not displayed for last two problems since calculations exceed maximum runtime. Best result for cach network-problem combination in bold.
Average expected total variation Ap in %, standard deviation in brackets
Model
CAIDA
Cities
Digg Friends
Enron
Flixster
Slashdot
Yahoo
YouTube
LPGMFG
24.02 (1.25)
28.16 (0.41)
21.98 (0.26)
24.77 (0.32)
22.48 (0.07)
23.70 (0.43)
10.11 (2.10)
22.94 (0.25)
SIS
GXMFG
9.07 (1.25)
10.90 (0.41)
4.72 (0.26)
4.73 (0.32)
3.78 (0.07)
5.48 (0.43)
9.31 (2.10)
6.43 (0.25)
LWMFC
(1.14)
5.00 (0.40)
3.57 (0.26)
3.39 (0.31)
1.60 (0.07)
2.41 (0.43)
3,59 (1.59)
3.53 (0.25)
LWMFC
(0.90)
4.20 (0.40)
3.02 (0.26)
2.67 (0.31)
0.90 (0.07)
1.70 (0.42)
3.81 (1.70)
2.93 (0.25)
LPGMFG
(1.40)
10.01 (0.34)
(0.31)
9.51 (0.32)
8.99 (0.09)
9.37 (0.38)
4,88 (1.82)
8.90 (0.23)
SIR
GXMPG
2.81 (1.10)
2.63 (0.31)
1.27 (0.29)
0.99 (0.30)
0.99 (0.09)
(0.36)
4.60 (1.71)
1.79 (0.23)
LWMFC
1.31 (0.87)
(0.27)
1,08 (0.28)
0.91 (0.30)
0.58 (0.08)
0.99 (0.33)
2.62 (1.30)
1.07 (0.23)
LWMFC
1.18 (0.82)
1.10 (0.26)
0.80 (0.27)
0.59 (0.28)
0.26
0.71 (0.29)
2.63 (1.30)
0.78 (0.23)
Rumor Color
LPGMFG
38.73
38.59 (0.09)
38.70 (0.04)
39.83 (0.06)
39.55 (0.02)
39.07 (0.06)
34.18 (0.26)
38.52 (0.04)
GXMFG
11.33 (0.13)
7.90 (0.06)
7.85 (0.02)
4.91 (0.03)
6.38 (0.01)
6,81 (0.03)
32.62 (0.24)
8.76 (0.02)
LWMFC
0.70 (0.12)
0.48 (0.05)
0.19
0.36 (0.04)
0.39 (0.02)
0.33 (0.04)
1.05 (0.19)
0.19 (0.03)
LPGMFG
20.03 (2.15)
22.56 (0.50)
18.39 (0.55)
20.27 (0.61)
18.94 (0.16)
19.70 (0.82)
9.68 (3.76)
19.23 (0.47)
GXMFG
6,98 (2.06)
7.49 (0.49)
3.33 (0.54)
2.86 (0.58)
2.65 (0.16)
3.82 (0.79)
9.01 (3.69)
4.79 (0.47)
LWMFC
3.06 (1.59)
4.31 (0.48)
3.00 (0.53)
2.62 (0.57)
1.73 (0.15)
2,41 (0.75)
5.01 (2.21)
3.27 (0.46)
6. Examples
are finitely many colors on a circle and a target color distri- bution is given. Agents stay at their color or costly move to neighboring color. The objective decreases for deviations from the target color distribution and if neighbors of an agent have neighboring colors to the agent's color on the respective color ring.
For general overview of many applications, see Laurière et al. (2022a). We consider four problems briefly described here. Problem details can found Appendix C.
(SIS/SIR).
The classical SIS model (Kermack McKendrick, 1927; Brauer, 2005) is a benchmark in the MF learning litera- ture (Laurière al., 2022b; Zhou et al., 2024). Agents are infected or susceptible, resulting in the state space x' (S, T}. and decide to protect themselves or not. The infection probability increases without protection, and with the number of infected neighbors. Furthermore, there is a constant probability for recovering from an infection. The SIR model (Hethcote, 2000; Doncel et al., 2022) an ex- tension of SIS where agents can also be in recovered state R where they are immune to a reinfection. Consequently, the state space for the SIR model is X == R).
Rumor. In the rumor model (Maki & Thompson, 1973;
Gani, 2000; Cui et al., 2022), agents are either aware of a rumor and are consequently in the aware state A or they have not heard the rumor and are in the ignorant state I. Aware agents decide whether they spread the rumor to their neighbors or keep it themselves. They are awarded for spreading the rumor unaware agents but loose reputation for telling the rumor to already aware agents.
7. Simulation & Results
In this section, we numerically verify the two system ap- proximation as well as the proposed learning algorithms by comparing them with baselines from the literature. The two systems approximation is compared with previous graph ap- proximations such graphex or Lp graphon MF equations, and the learning algorithms are verified against standard scalable independent learning methods such as IPPO (Tan, 1993; Papoudakis et al., 2021), due to the large scale of networks considered here. To generate artificial networks of different sizes we employ CL-based graph sampling algorithm (Chung & Lu, 2002; Miller & Hagberg, 201 from the Python NetworkX package.
Graph coloring (Color). Inspired by graph coloring (Jensen & Toft, 2011; Barenboim & Elkin, 2022), the states
LWV"
LW
GX
Time
Time
Time
Tire
Figure 2. Overall MF evolution on real networks (50 trials, with two std. devs.), for our approx. (LW), our extensive approx. (LW"), graphex (GX), and Lp graphon (LP) models: (a) SIS on Enron, (b) SIR on Slashdot, (c) Color on CAIDA (without LW"). (d) Rumor on Cities (without LW*).
We compare the accuracy of our model on different empiri- cal datasets with Lp graphon and graphex based models and with our extensive approximation LWMFC* where com- putationally feasible, to see how much information is lost
7

---

Learning Mean Field Control on Sparse Graphs
Table (LW)MFF policy gradient, (IW)MFMARI, policy gradient, and IPPO for four problems on synthetic CL. graphs of size N. Best objective after 24 hours of training on 96 CPUs. Best result for each problem graph tuple in bold.
N 167
N
406
N
860
N
1598
Problem
IPPO
MFC
MFMARL
IPPO
MFC
MFMARL
IPPO
MFC
MFMARL
IPPO
MFC
MFMARL
SIS
-0.880
-14.56
-12.50
-21.40
-14.18
-11.64
-19.70
-12,42
-9.11
-22.42
-13.51
-11.13
SIR
-7.45
-7.84
-6.99
-7.18
-7.42
-6.55
-10.64
-6.86
-5.15
-7.73
-7.42
-6.32
Color
-8.20
-6.84
-6.74
-8.05
-7.04
-6,98
-8.48
-7.08
-5.85
-8.15
-6.97
-6,94
Rumor
0.24
1.19
0.27
0.16
1.33
0.19
0.25
1.47
1.35
0.12
1.33
0.17
in the LWMFC approximation. We use eight datasets from the KONECT database (Kunegis, 2013), where we substi- tute directed or weighted edges by simple undirected edges: CAIDA (Leskovec et al., 2007)(N = 26k), Cities (Kunegis, 2013) (N x 14k), Digg Friends (Hogg & Lerman, 2012) (N R 280k), Enron (Klimt & Yang, 2004) (N x 87k), Flixster (Zafarani & Liu, 2009) (N RJ 2.5mm), Slashdot (Gómez et al., 2008) (N = 50k), Yahoo (Kunegis, 2013) (N 653k), and YouTube (Mislove, 2009) (N As 3.2mm). See the references for details on the respective empirical networks.
outperform IPPO for all problems on the two larger graphs with 860 and 1598 nodes, respectively. On the two smaller graphs, LWMFC and LWMFMARL still yield an least competitive performance compared IPPO, where IPPO is only marginally better than LWMFC on two problem in- stances, namely SIR on N = 167 and N = 406. We point out that LWMFC, in contrast to IPPO and LWMEMARL, is not evaluated on the empirical system, but by design on the limiting LWMFC model, which may differ from the true system behavior. These findings are complemented by the corresponding training curves in Figure 3. Finally, Figure 4 depicts how the training curves of our LWMFC and LWMF- MARL algorithms converge on different empirical networks for different problems.
Results. First, establish the usefulness of LWMFC and LWMFC* by comparing their dynamics to those of LPGMFGs and GXMFGs (Fabian et al., 2023; 2024) on eight real-world networks, see Figure 2 for examplary dy- namics over time. As Table shows, our LWMFC approach clearly outperforms the current LPGMFGs and GXMFGs methods for all empirical networks and problems. The ex- tensive approximation LWMFC* moderately outperforms LWMFC across datasets, except Yahoo. Since the extensive approximation is more detailed, it is often more accurate than the LWMFC approximation. However, Table lacks an evaluation for LWMFC* on the Color and Rumor prob- lem because the extensive approximation is computationally too expensive for these problems. Consequently, LWMFC dynamics the more practical choice since they com- putationally tractable and yield good performance across problems and datasets.
1000000
Time Steps
Time Staps -10
Tia Steps +10
Tims Staps -1P
Figure 4. Training curves of LWMFC policy gradient and LWMF- MARL for four different examples: (a) SIS on Enron, (b) SIR on Slashdot, (c) Color on CAIDA, (d) Rumor on Cities.
8. Conclusion
We have introduced the novel LWMFC framework which can depict agent networks with finite expected degree and di- verging variance. After theoretical analysis, we provided a practical two systems approximation which was then lever- aged to design scalable learning algorithms. Finally, we evaluated the performance of our model and learning algo- rithms for different problems on synthetic and real-world datasets and compared them existing methods. For future work, one could extend the LWMFC model to various types of specific mean field models, e.g. to partial observability or agents under bounded rationality. We hope that LWMFC and the corresponding learning approaches prove to be a ver- satile and useful tool for researchers across various applied research areas.
Basa PRO
Basa
Rasa
Eapa PPP
11
8
-33"
x30
Steps Mr
+13
Figure 3. Training curves of LWMFC policy gradient, LWMF- MARI, and IPPO on a random CL. graph with 406 nodes for: (a) SIS, (b) SIR, (c) Color, (d) Rumor.
The second part of our results focuses on our two learning al- gorithms LWMFC and LWMFMARL and compares them to the well-known IPPO algorithm. In Table 2, our algorithms
8

---

Learning Mean Field Control on Sparse Graphs
Acknowledgements
Bensoussan, A., Frehse, J., Yam, P., et al. Mean field games and mean field type control theory, volume 101. Springer, 2013.
This work has been co-funded by the Hessian Ministry of Science and the Arts (HMWK) within the projects "The Third Wave of Artificial Intelligence 3AI and Al, and the LOEWE initiative (Hesse, Germany) within the emergenCITY center. The authors acknowledge the Licht- enberg high performance computing cluster of the TU Darm- stadt for providing computational facilities for the calcula- tions of this research.
Bollobás, B. A probabilistic proof of asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311-311 1980.
Bollobás, B. Random graphs. Springer, 1998.
Bollobás, B., Riordan, O., Spencer, J., and Tusnády, G. The
degree sequence of scale-free random graph process. Random Structures & Algorithmss, 18(3):27--290, 2001.
Impact Statement
This paper presents work whose goal is advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Borgs, C., Chayes, J., Cohn, H., and Holden, N. Sparse ex- changeable graphs and their limits via graphon processes. Journal of Machine Learning Research, 18(210)1171,, 2018a.
References
Borgs, C., Chayes, J., Cohn, H., and Zhao, Y. An Ip theory of sparse graph convergence ii: Ld convergence, quotients and right convergence. The Annals of Probubility, 46(1):
Achdou, Y. and Laurière, M. Mean Field Games and Ap- plications: Numerical Aspects, pp. 249-307. Springer International Publishing, 2020.
337-396, 2018b.
Aiello, W. Chung. F., and Lu, L. random graph model for massive graphs. In Proceedings of the Anmual ACM Symposium Theory of Computing, pp. 171-180, 2000.
Borgs, C., Chayes, J., Cohn, H., and Zhao, Y. An Ip theory of sparse graph convergence i: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 37265):001-3362, 2019.
Aiello, W., Chung, F,, and Lu, L. A random graph model for power law graphs. Experimental Mathematics, 10(1): 53-66, 2001.
Brauer, F. The Kermack-McKendrice epidemic model revis- ited. Mathematical Biosciences, 198(2): 19-131, 2005,
Andersson, D. and Djehiche, B. maximum principle for SDEs of mean-field type. Applied Mathematics & Optimization, 63:341-356, 2011.
Caines, P. E. and Huang, M. Graphon mean field games and the GMFG equations: s-Nash equilibria. In IEEE 58th Conference on Decision and Control (CDC), pp. 286-292. IEEE, 2019.
Bagagiolo, F., Faggian, S., Maggistro, R., and Pesenti, R. Optimal control of the mean field equilibrium for a pedes- trian tourists' flow model. Networks and Spatial Eco- nomics, pp. 1 1-24, 2019.
Caines, P. E. and Huang, M. Graphon mean field games and their equations. SIAM Journal Control and Optimiza- tion, 59()) 2021.
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. Science, 286(5439)5009551, 1999.
Barenboim, I., and Elkin, M. Distributed graph coloring: Fundamentals and recent developments. Springer Nature, 2022.
Caines, E., Huang, M., and Malhamé, R. P. Large popu- lation stochastic dynamic games: closed-loop McKean- Vlasov systems and the Nash certainty equivalence prin- ciple. Communications in Information and Systems, 6(3): 221-252, 2006.
Bauso, D., Tembine, H., and Başar, T. Robust mean field games. Dynamic Games and Applications, 6(3):277-303, 2016.
Canese, L., Cardarilli, G. C., Di Nunzio, L., Fazzolari, R., Giardino, D., Re, M., and Spanò, S. Multi-agent reinforce- ment learning: A review of challenges and applications. Applied Sciences, 11(11):4948, 2021.
Beck, M. and Robins, S. Computing the continuous dis- cretely: Integer-point enumeration in polyhedra, vol- ume 2. Springer, 2007.
Bender, E. A. and Canfield, E. R. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A, 2463)229--377, 1978.
Carmona, R. and Delarue, F. Probabilistic theory of mean field games with applications. i, volume 83 of probability theory and stochastic modelling, 2018.

---

Learning Mean Field Control on Sparse Graphs
Carmona, R. and Laurière, M. Deep learning for field games and mean field control with applications finance. Machine Learning and Data Sciences for Finan- cial Markets: A Guide to Contemporary Practices, pp. 369, 2023.
Gani, J. The Maki-Thompson rumour model: detailed analysis. Environmental Modelling & Soffware, 15(8): 721-725, 2000.
Goh, K.-I, Oh, E., Jeong, H., Kahng, B., and Kim, D. Classification of scale-free networks. Proceedings of the National Academy of Sciences, 99220::25833125588 2002.
Carmona, R., Laurière, M., and Tan, Z. Model-free mean- field reinforcement learning: mean-field MDP and mean- field Q-learning. The Annals of Applied Probability, 33 (6B):5334-53811 2023.
Gómez, V., Kaltenbrunner, A., and López, V. Statistical analysis of the social network and discussion threads in slashdot. In Proceedings of the International Conference on World Wide Web, pp. 645-654, 2008
Caron, F. and Fox, E. B. Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Soci- ety Series Statistical Methodology, 79(5):1295-1) 2017.
Gronauer, S. and Diepold, K. Multi-agent deep reinforce- ment learning: a survey. Artificial Intelligence Review, 55(2):895 943, 2022.
Chung, F, and Lu, L. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125-145, 2002.
Gu, H., Guo, X., Wei, X., and Xu, R. Dynamic program- ming principles for mean-field controls with learning. Operations Research, 71(4):1040-1055 2023.
Chung, and Lu, L. Complex graphs and networks. Amer- ican Mathematical Soc.. 2006.
Guo, X., Hu, A., Xu, R., and Zhang, J. Learning mean- field games. Advances in Neural Information Processing Systems, 32, 2019.
Cui, K. and Koeppl, H. Learning graphon mean field games and approximate Nash equilibria. In International Con- ference Learning Representations (ICLR), 2022.
Guo, X., Hu, A., Xu, R., and Zhang, J. A general frame- work for learning mean-field games. Mathematics of Operations Research, 48(2)x636-686, 2023.
Cui, K., KhudaBukhsh, W. R., and Koeppl, H. Hyper- graphon mean field games. Chaos: An Interdisciplinary Journal of Nonlinear Science, (011)),0022
Hethcote, H. W. The mathematics of infectious diseases. SIAM Review, 42(4):599
Doncel, J.. Gast, N., and Gaujal, B. A mean field game analysis of SIR dynamics with vaccination. Probability in the Engineering and Informational Sciences, 36(2): 482-499. 2022.
2000. 2000.
Hogg, T. and Lerman, K. Social dynamics of digg. EPJ Data Science, 1(1):1-26, 2012.
Dorogovtsev, S. N. and Mendes, F. Evolution of networks. Advances in Physics, 1079)1107-11187, 2002.
Hu, S., Zhong, Y., Gao, M., Wang, W., Dong, H., Liang, X., Li, Z., Chang, X., and Yang, Y. MARLlib: A scalable and efficient library for multi-agent reinforcement learning. JMLR, 24:1-23, 2023a.
Dorogovtsev, S. N., Goltsev, A. V., and Mendes, F.F.R. F. Pseudofractal scale-free web. Physical Review E, 65(6): 066122, 2002.
Hu, Y., Wei, X., Yan, J., and Zhang, H. Graphon mean- field control for cooperative multi-agent reinforcement learning. Journal of the Franklin Institute, 360(18):14473- 14805, 2023b.
Fabian, C., Cui, K., and Koeppl, H. Learning sparse graphon mean field games. In International Conference Artifi- cial Intelligence and Statistics, pp. 4486 4514. PMLR, 2023.
Jackson, M. O. et al. Social and economic networks, vol- ume Princeton University Press, 2008
Fabian, C., Cui, K., and Koeppl, H. Learning mean field games on sparse graphs: A hybrid graphex approach. In International Conference on Learning Representations (ICLR), 2024.
Jensen, T. R. and Toft, B. Graph coloring problems. John Wiley & Sons, 2011.
Kaufimann, M. and Zweig, K. Modeling and designing real- world networks. In Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation, pp. 359- 379. Springer, 2009.
Fasino, D., Tonetto, A., and Tudisco, Generating large scale-free networks with the Chung- random graph model. Networks, 1842)1174-187 2021.
10

---

Learning Mean Field Control on Sparse Graphs
Kermack, W. O. and McKendrick, A. G. A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society of London. Series A, Containing papers of a mathematical and physical character, 115(772):700-22, 1927.
Miller, J. C. and Hagberg, A. Efficient generation of net- works with given expected degrees. In International Workshop on Algorithms and Models for the Web-Graph, pp. 115-126, Springer, 2011.
Mislove, A. E. Online social networks: measurement, anal- ysis, and applications to distributed information systems. Rice University, 2009.
Klimt, B. and Yang, Y. The enron corpus: A new dataset for email classification research. In European Conference on Machine Learning, pp. 217-226. Springer, 2004.
Molloy, M. and Reed, B. A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2-3):161-18))) 1995.
Kunegis, J. Konect:
the Koblenz network collection. In Proceedings of the International Conference World Wide Web, pp. 1343-1350 2013.
Molloy, M. and Reed, B. The size of the giant component of random graph with given degree sequence. Com- binatorics, Probability and Computing, 7(3):295-305, 1998.
Lacker, D. and Soret, A. A case study on stochastic games on large graphs in mean field and sparse regimes. Mathe- matics of Operations Research, 1732):153-1155, 2022.
Lacker, D., Ramanan, K., and Wu, R. Local weak conver- gence for sparse networks of interacting processes. The Annals of Applied P Probability, 33(2):843-888, 2023.
Newman, M. The structure and function of complex net- works. SIAM Review, 45(2):167-256, 2003.
Newman, M., Barabási, A.-L., and Watts, D. J. The structure and dynamics of networks. Princeton University Press, 2011.
Lasry, J.-M. and Lions, P.-L. Mean field games. Japanese Journal of Mathematics, 2(1):229-266) 2007.
Laurière, M., Perrin, S., Geist, M., and Pietquin, O.
Papoudakis, G., Christianos, F., Schäfer, L., and Albrecht, S. V. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
Learning mean field games: survey. arXiv preprint arXiv:2205.12940 2022a.
Laurière, M., Perrin, S., Girgin, S., Muller, P., Jain, A., Cabannes, T., Piliouras, G., Pérolat, J., Elie, R., Pietquin, O., al. Scalable deep reinforcement learning algorithms for mean field games. In International Conference Machine Learning, pp. 12078-1209) PMLR, 2022b.
Piva, G. G., Ribeiro, F. L., and Mata, A. S. Networks with growth and preferential attachment: modelling and ap- plications. Journal of Complex Networks, 9():cnab008, 2021.
Leskovee, J., Kleinberg, J., and Faloutsos, C. Graph evolu- tion: Densification and shrinking diameters. ACM Trans- actions on Knowledge Discovery from Data (TKDD), (1):2-es, es, 2007.
Ruthotto, L., Osher, J., Li, W., Nurbekyan, L., and Fung, S. W. A machine learning framework for solving high- dimensional mean field game and mean field control prob- lems. Proceedings of the National Academy of Sciences, 117(17):918 9193, 2020.
Liang, E., Liaw, R., Nishihara, R., Moritz, P., Fox, R., Gold- berg. K., Gonzalez, J., Jordan, M., and Stoica, I. RLlib: Abstractions for distributed reinforcement learning. In Proc. ICML, pp. 3053-3062, 2018
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. 2017.
Lovász, L. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
arXiv preprint
Subramanian, S. G., Taylor, M. E., Crowley, M., and Poupart, P. Decentralized mean field games. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9439-9447, 2022.
Maki, D. P. and Thompson, M. Mathematical Models and Applications: With Emphasis on the Social, Life, and Management Sciences. Prentice Hall, 1973.
Mann, H. B. and Wald, A. On stochastic limit and order relationships. The Annals of Mathematical Statistics, 14 (3):217-226, 1943.
Tan, M. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the International Conference on Machine Learning (ICML), pp. 330-337, 1993.
Marsaglia, G. and Marsaglia, J. C. A new derivation of Stir- ling's s approximation to n! The American Mathematical Monthly, 97(9)826--5 82928299666688888118812221 1990.
Van Der Hofstad, R. Random graphs and complex networks, volume 54. Cambridge University Press, 2024.

---

Learning Mean Field Control on Sparse Graphs
Van der Vaart, A. W. Asymptotic statistics, volume 3. Cam- bridge University Press, 2000.
Vázquez, A., Pastor-Satorras R., and Vespignani, A. Large- scale topological and dynamical properties of the internet. Physical Review E, 65(6):066130, 2002.
Veitch, V. and Roy, D. M. The class of random graphs aris- ing from exchangeable random measures. arXiv preprint arXiv: 151.033999, 2015.
7afarani, R. and Liu, H. Social computing data repository at ASU, 2009. URL http:://oociaacompptt ing. asu. edu.
Zhang, F., Tan, V. Wang, Z., and Yang, Z. Learning regu- larized monotone graphon mean-field games. Advances in Neural Information Processing Systems, 36, 2024.
Zhou, F., Zhang, C., Chen, X., and Di, X. Graphon mean field games with representative player: Analysis and learning algorithm. In International Conference on Ma- chine Learning (ICML), 2024.
12

---

Learning Mean Field Control on Sparse Graphs
A. Appendix: Proofs for the Theoretical Results
A.1. Proof of Theorem 3.1
Proof. We aim to eventually apply Lacker et al. (2023, Theorem 3.6) and therefore have to check that the respective conditions hold in our model. Keeping in mind Assumption 2.2 and the i.i.d. initial distribution Po. we leverage Lacker et al. (2023, Corollary 2.16) to obtain convergence in probability in the local weak sense of the marked graphs (GN, XGx) the limiting marked graph (G, )
Since the theory in Lacker et al. (2023) is only formulated in terms of particle systems without including actions in the form of policies, we provide a suitable reformulation of our LWMFC model. Thus, define an auxiliary extended state space Xe == X' U (X' x U) which serves as the state space for the extended particle system for some fixed policy ensemble æ. The idea behind the extended state space N, is to define an extended particle system where the state transition in X' and the choice of the next action 1 E l are separated into two different time steps.
Using the notations from Lacker et al. (2023), denote by ( the set of finite unordered sequences of arbitrary length with values in X' and by E= == (x) x ux xxxxxxxXXX the set of possible noise values. Next, specify transition function F : Na x (*x. x E - X for each To = {0) U [2 1] by
(X.N Si, (X
ed S1,7+1 edrr C.. if 7/2 E (0) (X GN
XW a,,++1
FT FT
ON CATT Gedrr SLT+1)
otherwise,
where the neighhorhood in the extended particle system &e,,r corresponds to G.V [[//2] in the original system. Here, the noise terms 1 = (S1,7+1, St +1,++1 depict the used noise depending on whether 7 is an even or odd number. If is an even number, i.c. 7/2 {0] UN, we use c (X e.i, G.v..) which is a U-valuedd random variable with distribution
c 1 G) / (x.
for each neighborhood G and state x E X, where is the degree of agent If r is odd, i.e. we have X E x U, we choose the first, X' vvluueed entry of X.Y,, as the x in the above probability distribution.
The X' valvel noise component +,, is distributed as follows: if is an odd number, the noise term is sampled from
(1 u, G) ~ P (-Ix,u,
where X (z) u). If T is even and thus X.N X, we just choose some arbitrary, but fixed action u' e 2 instead of in the above sampling process.
Now, it remains to check that Lacker et al. (2023, Assumption A) is satisfied by the extended particle system defined above. First, the noise terms E.r are i.i.d. distributed for all agents E [N] and with respect to all time points T E To by construction. Finally, keeping in mind that the respective spaces are discrete, the map F" is continuous for each 7 E Te Therefore, Lacker al. (2023, Theorem 3.6) yields the desired result.
A.2. Proof of Proposition 3.3
Proof. We want to show
J (T) + ((T)
in probability for N 00
which is equivalent to
T
T
Σ
Er(
N + Σ r(p)) in probability for N + 00.
The reward r is a continuous function by Assumption 3.2. Furthermore, by Theorem 3.1 we know that the empirical mean fields converge in probability to the limiting mean fields. Hence, we can apply the continuous mapping theorem (Mann Wald, 1943; Van der Vaart, 2000) obtain the desired result.
13

---

Learning Mean Field Control on Sparse Graphs
A.3. Proof of Corollary 3.4
Proof. Quantify the gap A between the optimal and the second best solution
A = ((T)
((x:) > 0. iE[M]
max
Keeping in mind Proposition 3.3, we know that the objectives of the finite systems eventually converge to the limiting mean field objectives as N approaches infinity. Thus, there exists some N* such that
A
I (TT)) [
max
E M
2
holds for all N > No. Finally, the above considerations allow us to bound the difference of interest
N (
JN (TT))
max 11
(M(T) ((T1 + +(Ta)
max Jd
(T.S)
VE(M],i71
J. (m) [ +(m))
J(ms)
Jm.))
J (M:T)
(i(MM)
iElM)
iE[M)],is1
>-A/2
A
A
A
+ min J(m:) - J (TT;)
0
2
de
M
2
for all >>>>>>> No which implies the desired statement
JN (mT)
(M,
max kE[M],
and therehy concludes the proof.
A.4. Proof of Lemma 4.1
Proof. Since we want to lower bound the number of possible t-hop neighborhoods NG.. we assume for simplicity that I-hop neighbors of the initial agent have at most degree & themselves. Furthermore, we keep in mind the fact (Beck & Robins, 2007, Theorem 2.2) that d-dimensional simplex with edge length E N, the number of integer points contained in the simplex
d 9
(d + e)!
d.e!
Since Lemma 4.1 considers the worst case, suffices to prove the lower bound (2poly(A)) for one class of CL graphs. choose our running example of CL power law graphs with coefficient above two. is well known that these large power law CL graphs are locally tree-like (Van Der Hofstad, 2024, Theorem 3.18) which we tacitly exploit in the following induction proof.
The proof is via induction over t. We start with = 1 and the corresponding 1-hop neighborhood. The neighborhood consists agents where each one has a degree in [k] and a state X. Since the agents themselves are indistinguishable in our model, we focus on the degree-state neighborhood distributions. Then, the set of possible state-degree neighborhood distributions can be seen as the integer points in (I: + | 1) dimmennsiaa simplex with edge length k. Keeping in mind
14

---

Learning Mean Field Control on Sparse Graphs
Equation (1) and the well-known Stirling approximation, see e.g. Marsaglia & Marsaglia (1990), we obtain
+ | - 1+
NG. 2
k + |2| -
(2h + X 1)!
(k + X 1)
2x (2k + | - 1) (2k: + X - 1)24+181-1
Stirling
2T + X - 1)2 (k + | 1)4+121-144
(2k + -
V k
k-
2
V 1
2 1/2:lorg(2ar)) E + (2poly(k)
Now, it remains establish the induction step from t + where we assume that NG. E (2noly(A) holds. Then, instead of looking at the 1)-hop neighborhoods of the initial agent, we can equivalently look his or her 1-hop neighborhoods where each neighbor's "extended state' now consists of the neighbor's t-hop neighborhood, where ignore the edge between the neighbor and initial agent. Thus, the simplex edge length decreases by one from À to k I which is negligible for large k. Leveraging the induction assumption, we obtain
(No.+ - k. ))
Na.+1 =Q
(Na. + k)!
=
K!NG,
(v
No. + k (Ng. + k) Not
Stirling Ω
kNa.
No Rok
(Na, + k)*
Ω
V
kktt
1 (2p0ly(A))
(IA)
Vk
Ω
(2t-poly(A)) (k--0-111/// 1/2) (oRg(() (k)
(2pol)(4)
Ω
which concludes the proof.
B. Extensive Approximation Derivation
The goal of the following section is to establish a detailed approximation of the probability
Pro.u (Gh. (14,) G, G, =
First, we condition on the previous neighborhood distribution and the previous state of the agent at time
Pr.. (G/+ (m)) G,I++1 =x)
= Σ Pa.j (G/+1 (1r)) = G, = I4 = x')
N'EN'
= Σ
Σ Pr.j (Gta (14,) = G. G.G. (H+) = G', -2,0 = x')
G'egk 2'EX
15

---

Learning Mean Field Control on Sparse Graphs
Now, we can decompose the above expression into three separate terms
P (Gef+1 (1₂) = G, G (H,) = Ic+1 = I, I1 = z')
Px (Gr (14) G², x²) Pr.ja (Ie+1 G (14) G², xa)
(1)
(1))
P (G (14) = G G (pt) = G², 2 = 2, 2t =
which allows to handle each term individually. Since require recursive computation of the probability Pr.. (Gf+1 = G. = =)), the first term (I) will not be reformulated any further. The computation of the sec- =
ond term (II) is straight-forward i.c.
PI (I++1 = x2 G. (1) ,²
22 =x)= Σ n (()2))
ucll
Thus, it remains to approximate the third term (III)
Pr.j (Gi+1 (p:) = G G (p.) 0441 11 = =2)
Px, (Gi+1 (1,) - G (v,) G
To ensure reasonable approximation complexity, we make the simplifying assumption that the neighborhood distribution does not (crucially) depend on the current state of the agent of interest, i.c.
PA (Gi+1 (14) G G (1,) = G², =x)) PH. (Gi+1 (n,) G G (n,) G')
Thus, we focus on
Pr. (G (14) G G (1)) = G')
which requires an involved combinatorial argument to be calculated. The main difficulty in the calculation stems from the fact that the neighbors of the initial agent in general have different degrees, different states at time as well as different states time ++ 1. For notational convenience, we denote by time and by degi..... degx- degoc E {l,...,Ke k} the number of neighbors with the respective degree. Also, detine ck (c = (cI,..., , E N 61 +... cx Coo kb} for notational convenience. Then, the above probability can be expressed as
Fx,t the states of the neighbors of the initial agent
Payj (G/+1 (H,)= = G GIG G (H,) = G')
= Σ Parj (Gi+1 (14) = G,degı = CI,..., dega- = Ck., degoo = = G. (11,) = G')
leck
Σ Pa.n (degi .l...., degg- Ck', degoo Coo G. (m4, = G²)
nECk
Pa (G/ (m₁) = G deg, = dega- = Ct., degoo Cocs G/ (M₂) = G¹)
In the remainder of the derivation, we will frequently use for all s e X,m m N. and the approximation
P (x) (eg(()) m. (No, vn) E F) R P (x) = deg(m)) = =m) 1u (s).
(2)
Next, we make an auxiliary calculation to calculate the degree distribution of a (uniformly at random picked) node U1
16

---

Learning Mean Field Control on Sparse Graphs
conditional its state = and that it is neighbor of the initial node vy of interest
P (deg(e1) = m | = = s, (vo, 21) E E)
P (deg(v))
0 2
(vo, v1) E)
P [ = (vo. E E) P (dde((v) = m
(vo, 01)
E E) (1) = 8 deg(()) = m, (vo, v1) E E)
P (deg(w)) > k* nze = 8 (10,
E F.) + Σk=1 k= P (deg(()) = k: k. = 8| (vn, v1) E F)
P (ddeg(11) = m
(vo, 11) E) p."
P (ddeg(v1) K- nz.
(oo. v1) E E) + Σx=1 P (deg(11 (1)
1s n = s (vo. 01) E)
P ((deg(v)) m (vo, v1) E B) 1u (s)
(dde((v))> > k* (1) E B) pz (8) + k= P (deg(vi) = k (vo.vi) E (s)
where we exploit that
P (deg(vi) > 1et nzt = (vo. v1) E B) + P (deg(v)) = k n = s (v0, E E)
P (ddeg(v1) > k. (1) E E) P) (x) deg(v1) > k", (vo. v1) E E)
P (deg((1)) = (vo, 01) E F) P (x) = s |deg(u)) = k, (vo, v1) E E)
(deg(()) k* (vo, E)
Σ P (deg(v)) (vo. v1) E E) (s).
For the running example of power law degree distributions with exponent y E (2, the conditional degree distribution is approximately
P (deg(v1) m x sz. (vo, U1) E E)
n 16 14 (83)
((7-1) - 8 { 1 ($j) + ((7-1) -m==1 h-- - (s;) m 1- 11 (s3)
1
E [- 14 (8j) + Σh (8))
Based on the above probability and by the symmetry of the model, we obtain
Pa (degı = Cl,...,, degg. = Ck-, deg = Coo G (u,) = =G)
Σ P (A2 = a2, degi = =c1,.. -l...., degtt ck- deg Coo GG (H,) = G')
Σ
Pa (A2 = a2 | G. (mt) = G¹)
(GEA)(G),)))
Σ (GE))(G',)))=
I
df
(P (dog((r)) = m xt = -3, (1o, U1) E =0)) me[k-]U(oo)
II
aft..... ajoz
where we neglect dependencies between the nodes in the last line and define the matrix set AZ c) for given G' E k and c E Ch as
AB c) = aaz (4gm)) E Ndx(k
[ +1)
ajm' = = E [d] and Σ
apm Cm, Vm E [b*] U (oc) }
E=1
17

---

Learning Mean Field Control on Sparse Graphs
Therefore, it remains calculate the conditional probability
P Pe (G (14)) G degi -1.-.., -.....,degg- Ck=; degx Coc: G.y (14) =G)
As first step, we define the set of matrices ( G', c) for given triple of vectors G, E g and e E C* as
AG, G) = {as a3 = (asg)))elld)mellliuuue E No Nxxdx(e+1))
aeem' Is and
Σ
Σ
atjm gj.
Vi,j e [d]
m' m'Elk=JUfoo) Em
m' m'Elk=]Ufoc) km1
400 = Cm, Vm E [K 100) [K7U
and
8F=11
where d = |X| is the finite number of states. Intuitively, the matrix set A G', cc) for an agent with degree k contains all of neighbors whose degree is m and current state is 2; and who transition to state zj in the next time step. For notational convenience, let A denote the random variable taking values (G, G) and analogously let A2 the random variable with values in A (G", c). We continue with the reformulation
possible numbers
P (Gi+1 (4L) = G degi = CI..... degs. = Cg., deg = Coas G (1,) G')
Σ Pu (A2 a2 degi CI...., deg.. Ck", degoo Coos G. (M₂) =G')
A
Pr (G/#1 (H+) = =G| = 02 degı = C..... degg- = Ck., deg = Coo: G (HL) = G¹)
Σ
Pa (A2 =1==0 =a2 degi .I...... degs. Cb",
degoc C
Coo, G. (1,) = G')
(2',)(('
PT (G/41 (H,) = G A2 = a2))
Next, we consider the two conditional probabilities separately. We start with
Jr (A2 = 02 degi = C1, degg- = Ck=, deg = Coo: G (1,) = G')
Pa,f s (A2 a2 n dogi = CI,.... dogs. = Cx c d0g = Coo, G (14)) = G')
PT. (deg1 = CI,..., dega- Ck., dega = Coo, Gi (11) = G') PR. (A2 = a2) PR. (degı = C1.... degg. = Cke, degoo Coo: Gf (1₂) = G¹)
Keeping in mind both
d
PR,f (A2 = 02 = (ajm)j.m)
2 II jml me (x))
II
(P(deg(v1) m (vo, 01) E E) n4," (8)))
by neglecting dependencies between the nodes and
Pr Pr. u (degı Ci....,, degt. Ck., degoc Coos G. (H,) G')
Σ
Pai (degi = CI...., dega- = Cb., deg = Coo, G/: (M₂) = G. = =az)
(G'
Σ
Pa (A2 = a2)
(G',e)
Σ
II
II
(Peeg((v1) m (vo. F)) pz0 (s;)) 9mm
18

---

Learning Mean Field Control on Sparse Graphs
obtain
Pr. (A2= = a2 degi Cl,..., degs. = Cj., deg.0 = Coo G3 (H4) G*)
Px, (A2 = a2)
Pa. (degi Cl....... degs. Ch degoo Goo: G/ (14) G²)
IT Jutoc (P (deg(e1) = m (vo, v1) E E) 1e. (sz))
EaseA -1- [mm (P (deg(v)) = m (vo: 01) E3) p 1T (s;)) S
and especially, for the case of a power law degree distribution with r E (2, we have
P7 (A2 a2 degı C1,.... degs- Ck+, deg
Coos G/ (H4) =G"
11 j==1 (s)) 1 2m (m1')1~
9,00
I
m² - (a,)
((7-1)
5(9-1)
EaseAtioro I1;=1 (1r(s;) (1 Em (mr))-
1000
ml ( 3'
Im=l
515-13
((7-1)
II (1p)))) (5(7- -m (m)))²
a5m0
Im
(m- "u (8,) ajm
EaSEA II:=1 (s)) (s(r - Emm= (m²)))))))> 2x
I (m (m= (s))) (s,))
Now, it remains to calculate the second probability term, namely
Prij (G (H,) = G || Ag = =az)
Exploiting the symmetry of the problem, obtain
Pa. (Gi+ (H+) = G A₂ = a1)
(E aijm
Σ II
1 1 ar5m
(1jmm
Odjmm
agEA' (G) [e(k
Pr (Z 24 a Ij, deg(v1) =m)) aesm
Σ II
aijm
1 1 11 aijm =ajm]
@ljms.... Odjmm
asEA' (G.G' j= mE(k-)U(oo)
Raim
Σ
Pa (G (H₂) G 1 =8))
Σ क..h ( (ul P 89. u. G")
uell
where 1 (..)) denotes the indicator function and where we neglect the potential dependencies between the neighbors of the
19

---

Learning Mean Field Control on Sparse Graphs
initial node in the second line. Finally, we arrive
Jr. (Ge+1 (11) -G G degi -I,...,, -C,...,,deg;- Ckt, dego0 Coo, Gf (14) = =G)
E
P (A2 a2 degı CI...., degg. Cki, degoo coo, G. (1t) = G*)
(2',)(G',o)
PT. (G (14) G A2= = a2)
j= [ufoo (P (deg(()) m (vo. 01) ED) PT7 (5;)) )m3m
Σ
EajEAtior .)) m= mm (P (deg(v1) = m (No, U1) v1) E E) 1r (s)))
(
PT.. (G (1)) G A2 a2)
j=1 Imelk+Juad (P (deg(vi) = =m (vo, v1) E E) Pz (8)))
Σ
a0'A)((G' EajeAtior .e) - ImE (P (dog(v1) = m (v,,21) E E) pr (8)))
Ei dijm
Σ
II
II
11 agsm
Oljm:.... Odjm
agE A .0) f= me(ko))(oo)
043m
II
Σ
Pr (G7 (m,) = G" x = =, Σ
m (u 87) P(s 89. u, G")
m
uell
and for the running example of power law graphs we especially obtain
P (Gi+1 (m+) = G deg; = =l...... deg.. = cx-,deg, = Coo, Gk (H,) = G')
- (pp) (1-En-- (m))1-7
ajo I ( mm pf 4pm
((y-1)
Σ
((7-1)
Easestior o) II (1P))))) (1 Emimi (m/))-7)
22 Ihki
("
(m² (m² o'm
(GEA)(G' .)
5(1-1)
c(7-1)
Σ
II
E, Gigm
11 aajm
(ljmm.... a.dm.. Adjm
a:sm
II
Σ Pr (G (H.)) G" 1="==0 = Σ Th. (u [8)) P(; 181, u, G")
TM
well
T==1 (1)) (1- -m (m/))-77
m m
14: (8,)
ajm
5(7-1)
Im=
5(7-1)
Ease II, (1p) (1 Dhz (m/)² 7
'n' m ai
(G.G))
<(--1)
((7-1)
aigi
II
II
(aijm...., adjm
1=1 me (ke (k]))(oo))
aijm
Σ ==1 6"
Pa (G. (H,) = -G" 1==== =8)) Σ well
m (u [5) P (s: 85, u, G")
20

---

Learning Mean Field Control on Sparse Graphs
Resulting Approximation Eventually, we obtain the approximation
P (Gl+1 (1₂) = -, =x)
Σ
Σ
Pa (G) (14, = G², Σ
x (u
G'Egh G'Eghx'EX 2'EX
LuEW
Σ
Σ
II
II Ofls-..; Ju(k))
cEC
(GEAA
P (ddeg(v)) (Vn, v1) E) p((
4jm
P(deg(v1) > k* (v), E E) p (83) Σk=1 P (deg(vi) = (vo, 01) E)) (8())
EasEAf(Gr c) jm jom (P (deg(u1) m U1)
U1) E E) 14 (s;))
E, Aijm
d II
Σ II II
(P (deg(v)) m (vo. 01) E F) pz (81)) (8)))amm )asm
aljm,..... .... Odjm
agEA5 ;= == m (Uoo)
==1
assm
Σ Px (1,) G" o 33) G"Egm
Σ
Th (u (3)) P(: 13, 13, Gm))
NEll
which, for the power law running example, can be reformulated
Pri (G/+1 (n,) = G, = x)
~ Σ Σ
Pru (Gt (1)) = =G" 24 = x')
Σ
nt (u (
G'Egt z'Ex
LuEM
gf C0ji
Σ
II
oee
a.EA j=
m 17 7 (s))
4jm
Σ - p1 14, (sj) + -m=11 h² (1]
me(k-]U[oo}
I (1)) 1 --E (mn')
Im
m= 7 (x;)
aym
Σ
((C-1)
c( 1]
A e) EaleAtio II, (1)) (1- -->''' (ma))
ks*
m ((3
4/
((--1)
5(5-1)
Eiji
II
(ajmm...,, adjm
j=1 [E(k)
II
Σ
Px
cum (1L) = G" 1 = =8)) Σ m (u (5)) P(s 1888 u, G")
well
For notational convenience, define for each E [d] and m E [k*]] U (oo}
P (deg(v))) = m (vo, U1) E E) u()
Pim (deg(())) > kz (No, vn) E E) + Ek= P (deg(())) = k (v) 01) E E) ut
and for each i E [d] and m E [k*] foo}
Pijm P (deg(())) (1)) ml 01) E E) E) (8;)
Σ
Px (GT (n,) G zt =s)
Σ क."" T" (3] P(:: 18, G") uell
mm
21

---

Learning Mean Field Control on Sparse Graphs
Then, the extensive approximation can be rewritten more compactly as
Pa. (G++1 (1e) = G, =x)
Σ
Σ
Pai (G) (H+) = G Σ *t (u Px G*)
G'egk r'Ex
Luell
gj
Σ
II
P jin
ajt. ajzo
CEC² (G',) f0)
me(
EajEAjiG,Gr [T== [m((k)JU(()
Σ, aejm Vijim---00
IT 1==1 Pijm
E EarEAf(Cr I (P (deg((1)) m
(vg. 11) E E) p4 (s;) mm
Furthermore, we introduce
P2.j = (py1, "yk-,Pjoc and 02.j = (azl: agk- azoo)
for every [d] and similarly we define
P3, Pa.jm = (Pijm..... PPaj)) and 03.jm == (a1jm..... Adjm)
for every tuple m) E [d] ((**) (oo)). Then, the extensive approximation can be formulated as
P (Gh+1 (14) G, =x)
Σ Σ
Σ Parm (GH (m,) = G², xt =;
Σ t (u ((l
G'Eg' x'EX ceck
LuEll
EaseAtior II, Multps, (a2.) EaseAtia,or.. II Multps, (as.5m)
EaseAf Ipm Jam (P (dog(u1) = m (Vo, v1) E) pr (s;))
C. Simulation Details
We use MARLlib 1.0.0 (Hu et al., 2023a) building on RLlib 1.8.0 (Apache-2.0 license) (Liang al., 2018) and its PPO implementation (Schulman et al., 2017) for IPPO and our algorithms. For experiments, used around 80 000 core hours on CPUs, and each training run usually took single day of training on up 96 parallel CPU cores. For the policies we used two hidden layers of 256 nodes with tanh activations. We used a discount factor of 7 = 0.99 with GAE À = 1.0, and training and minibatch sizes of 4000 and 1000, performing 5 updates per training batch. The KL coefficient and clip parameter were set to 0.2, with a KL target of 0.03. The learning rate was set to 0.00005. The problem details are found in the following.
Susceptible- suoepptile--nfecced--usspppppppi (SIS). In the SIS model with state space X' = {, agents are either infected (4) or susceptible to a virus (S). At each time step t E T, agents either protect themselves (P) or not (P) which is formalized by the action space Ut = (P, P). As usual, the game terminates at finite terminal time T which can be interpreted as the time when a cure for the virus found. Therefore, it remains to specify the transition dynamics. Susceptible agents who protect themselves time also remain susceptible at time & 1, i.e.
p* S, P.G) and pk S, =0
irrespective of their degree i and neighborhood G. On the other hand, if susceptible agent chooses action P, the transition dynamics are
pk(1 S,P,G) ps G(I) (10))e(xxx(-112 1
2
22

---

Learning Mean Field Control on Sparse Graphs
and (S S,P, = 11 (* S, P, G), correspondingly, and where Pr O fixed infection rate. Apart from that, infected agents recover with some fixed recovery rate 1 2 pn 2 independent of their action and degree, which means that
I = PM (5 P.P.G) = PR
To complete the model, the reward per agent taking action u E 2 in state x E X each time is
r(z, u) -p 1 11((2,
where the cooperative objective is obtained by talking the average reward over all agents and summing up over all time points. Here, cp and ej denote the constant costs of protecting oneself and being infected, respectively. In our experiments from the main text, the chosen parameter values Ho (T( = 0.4, (u(() 0.6, T = 50, p1 = 0.4, pn 0.1, cp 0.5, and C1 1.
Seccepible-nnfeceed-Reeooe (SIR), In the SIR model, we extend the state space from the SIS by the recovered state R and obtain X' == 1, Rt.. As only infected agents can recover, the transition dynamics of the SIS model are modified by
(*(R I,P,G)
I. I.P.G) = PR
and
P*(R R,P.G) (R.P..
to formalize that recovered agents cannot become susceptible or infected again. The rewards and hence objective remain the same as in the SIS model. In the experiments, we set the parameter values (o(T) = 0.1, (o()) 0.9, T = 50, pr 0.1, PR = 0.02, cp = 0.25, and cj = 1.
Graph coloring (Color). In this problem, the state space consists five colors X' = (wi, ( I3, T4, 255) allocated on a circle. Agents can move from the current color to the next color on the left (f), to the next one on the right (r), or stay at their current color (s) such that the action space is l = {e, r, s). The group of agents is also supposed come close to target distribution E P(X). To keep notations manageable, we make the auxiliary definition
G = min(1, Pa exp(-2/X))
where Pa > is constant noise factor. The following three matrices specify the transition dynamies, where the row is the current agent color and the column is the next agent color:
(x1))/
0
0
Gx(mn)/2
1- Gx(22)
Gx(x2)/2
0
0
Gx(z2)/2
(+(.1 ()
(2(xa)/2
1- CR((a))
Galea)/2
Gu(z1)/2
1 Gx((())
(x(44)/2
Ga(us)/2
Gx(ss)/2
and
1 1- Gx(1()
Ge(xn)/2
0
0
Gx(z1)/2
(x(22)/2
1- Gx(22)
Gn(x2)/2
0
((1,,,)))
0
Ga(ra)/2
1- Gx((()))
Gx(x))/2
0
0 (x(2s)/2
Gu(za)/2 0
1 (-Gu()))
(x(z))/2 Gx(ss)
Gx(26)/2
and
Gx(z1)/2
1- Gx(x1)
Gn(z1)/2
0
0
0
Gx(z2)/2
1 1-G
Gx(xz)/2
0 Gx(rs)/2
())
0
0
(x(2))/2
1- Gz(zz)
Gx(x1)/2
0
0
Gx(x1)/2
1- Gx(a
1 1- Ga(zs)
Gx(os)/2
0
Gx(os)
23

---

Learning Mean Field Control on Sparse Graphs
The reward in our graph coloring model is defined
2)),, = -1e(m)) 1.)))) Cm - (G(2)-)) G((z+))) cd Σ (u(a,) - -xzz) cu.
where Cm. Cds Cu are the costs of moving, having neighbors with neighboring colors, and deviating from the target distri- bution V/ respectively. In experiments, choose the parameters μo (1,0,0,0,0), (0.1, 0.2, 0.2 20, 0.9, C. = 0.1, Cd 0.5, and Cy =.
Rumor. The state space X' = {I,A) A in the rumor model consists of the state A where an agent is aware of rumor and state I where the agent does not know the rumor and is therefore ignorant of the rumor. Agents either spread the rumor S or decide not to do so S which results in the action space == {S. S}. Since the rumor spreading probability increases with the number of aware numbers who decide to spread the rumor, we work with the extended state space X' == X U (X U). Then, the transition dynamics are
pk ((A, u)
(A.)
Yu E KeN
meaning that aware agents remain aware, and furthermore
[,, =1 t
and
2 (I+csp(-k/2)-))
(* (I, u, min 1, G((A,S))
ph (I (I, u), u, 1 (A (I, u) u, G).
To complete the rumor model, the reward is given by
r(z, u. G) (z) (rs G)(L,)) +rs G((I,))) cs G((A,S)) - cs G((A,
for each agent, where we obtain the overall objective by averaging over the individual rewards. In our experiments, the parameters chosen as (o(A) 0.1, no (I) 0.9, T 50, PA 0.3, cs 16, and rs 4.
24


Reviews:
[{"review_id": "vcLwxiN2D4", "reviewer": "Reviewer_EQY6", "summary": "The paper proposes a Local Weak Mean Field Control (LWMFC) model to address cooperative control in sparse networks, leveraging a local weak convergence framework to overcome limitations of traditional graph-theoretic methods in scenarios with finite average degree but diverging variance. Experiments demonstrate that LWMFC consistently outperforms baseline methods on both synthetic datasets and real-world networks (e.g., social network topologies).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading our work and the detailed positive comments.\n\nThe answer with respect to the reviewer’s questions on $k^*$ is as follows. In all computational examples we set $k^* = 10$ for the standard LWMFC approximation, and $k^* = 4$ for the extensive LWMFC* approximation due to the considerably higher computational complexity of LWMFC*. In general, the choice of $k^*$ is a trade-off. On the one hand, choosing a higher $k^*$ means that agents with moderately low degrees are depicted more accurately which should enhance the accuracy of the two systems approximation. On the other hand, a higher $k^*$ also entails higher computational costs and an increasing algorithmic runtime as one must sum over more potential neighborhood distributions. While tuning the choice of $k^*$ will likely further improve the performance of our algorithms, we leave it to future work as our initial choice of $k^*$ already outperforms existing methods such as LPGMFGs and GXMFGs in all considered problem-network combinations.", "claims_and_evidence": "The paper asserts LWMFC’s superiority in sparse networks, supported by empirical evidence from comparative analyses of mean-field dynamics and quantitative evaluations of global average rewards.", "methods_and_evaluation_criteria": "Methodological soundness: The two-system approximation reduces computational complexity from O(K) to O(k*+1) by decoupling low-degree and high-degree agents, aligning with sparse network characteristics. Evaluation criteria: Comparisons of mean-field trajectories and global reward metrics provide intuitive and rigorous quantification of cooperative efficiency in complex topologies.", "theoretical_claims": "Theoretical claims are well-supported: The convergence of finite systems to mean-field limits and objective functions is rigorously established under local weak convergence assumptions, ensuring algorithmic validity. Corollaries demonstrate that optimal policies derived from limit systems can be directly applied to large-scale real-world networks.", "experimental_designs_or_analyses": "Experimental design is rigorous: Systematic comparisons with baseline methods validate LWMFC’s performance advantages in sparse networks. The inclusion of independent learning baselines ensures the reliability of evaluation results.", "relation_to_broader_scientific_literature": "The work extends graph mean field games to sparse networks, bridging gaps in existing approaches. Comparisons with decentralized paradigms align with interaction complexity reduction .", "essential_references_not_discussed": "The references cited in the article are basically complete.", "other_strengths_and_weaknesses": "Strengths:\nTheoretical Innovation: First integration of local weak convergence into mean field control, addressing sparse graphs (e.g., power-law networks).\nPractical Algorithm Design: LWMFMARL interacts directly with real-world networks (e.g., YouTube with >3M nodes) without model knowledge.\nComputational Efficiency: Two-system approximation reduces complexity from exponential to polynomial (O(k*+1)), enabling real-time applications.", "other_comments_or_suggestions": "No", "questions_for_authors": "How is k* determined? Is it based on cross-validation or degree distribution inflection points? What is the impact of varying k*? If sensitive, robustness analysis is needed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rKl9X00S0h", "reviewer": "Reviewer_hioZ", "summary": "The main focus of this paper is a variation of mean field control (MFC) problems in which the agents' interactions are encoded by a graph-like structure which is not necessarily uniform, contrary to standard MFC. After studying the foundation of the problems (well-posedness and connection with finite-agent problems), two reinforcement learning algorithms are proposed and tested over several examples.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation and the constructive feedback.\n\nThe reviewer noted that: “While the theoretical analysis of the control problem is interesting, I am not sure if this conference is the best fit. It would be better to develop further the learning aspects.”\nWe agree with the reviewer to the extent that our work is an initial investigation on the topic and that the algorithm performance can likely be improved further. However, the conducted theoretical analysis and our subsequent two systems approximation provide essential insights for the learning algorithm design. As our empirical results indicate, the conceptual insights in the first sections translate into mathematically well-motivated learning algorithms that outperform existing approaches like LPGMFGs, GXMFGs and IPPO. Thus, our framework closes a crucial gap in the existing learning and mean field literature.\n\nThe reviewer also raised the question “Is it possible to analyze the theoretical convergence of the proposed algorithms?” In Algorithm 1, we apply RL methods to the limiting LWMFC such that theoretical results from the corresponding RL literature transfer to our case. For Algorithm 2, a theoretical analysis is challenging due to the direct interaction with the empirical networks. We instead focus on the theoretical motivation for our learning approach and the extensive empirical evaluation in comparison to existing methods.  For future work, a next step could be to mathematically analyze the error of the two systems approximation in terms of the number of agents.", "claims_and_evidence": "It seems fine to me.", "methods_and_evaluation_criteria": "It seems fine to me.", "theoretical_claims": "I had a look at the proofs and they seem fine.", "experimental_designs_or_analyses": "Yes; they seem fine to me.", "relation_to_broader_scientific_literature": "So far there are few papers on RL for MFC and on discrete-time graphon games. The literature provided seems fine.", "essential_references_not_discussed": "The ones cited seem fine.", "other_strengths_and_weaknesses": "Nothing specific beyond the points discussed in the other textboxes.", "other_comments_or_suggestions": "While the theoretical analysis of the control problem is interesting, I am not sure if this conference is the best fit. It would be better to develop further the learning aspects.", "questions_for_authors": "Is it possible to analyze the theoretical convergence of the proposed algorithms? This would strengthen the contributions in terms of machine learning.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9jH5M575vF", "reviewer": "Reviewer_Vx86", "summary": "The paper studies mean field multi-agent methods on sparse graphs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and constructive evaluation of our work. \n\nThe reviewer raised the concern that “[…] in Definition 2.1, it is unclear what the expectation on the right-hand side is defined over. […] the source of randomness needs to be explicitly stated.” Thank you for pointing out the missing clarity in Definition 2.1! The randomness in Definition 2.1 is induced by the randomness in the graph limiting object $G$ which is a random variable over the set of isomorphism classes $\\mathcal{G}^*$ and not just an element of $\\mathcal{G}^*$ as currently stated in Definition 2.1. The expectation is then over the law of this random variable $G$.  We will update Definition 2.1 accordingly to accurately outline the source of randomness. \n\nFurthermore, the reviewer raises the following question: “The reviewer is primarily uncertain about the applicability of the mean-field method in the studied scenarios. Specifically, mean-field theory relies on an assumption that holds when agents are strongly influenced by their neighbors. However, this assumption does not hold in sparse graphs. This raises a fundamental question: What is the rationale for applying mean-field theory in this context? Can it accurately capture the underlying relationships expressed by these graphs?”\n\nFor the many low degree agents, as the reviewer indicates, the standard MF assumption does not hold. However, even for these low degree agents, the same local neighborhood configurations appear very often in large graphs, formalized by local weak convergence. The locally weak converging neighborhoods result in an (almost) deterministic evolution of the finite degree mean fields and entail the rigorous theoretical results we derive in the paper.\n\nThe rationale of applying MF theory in the context of sparse graphs with finite expected average degree and diverging degree variance lies in the structure of the considered graphs. As we discuss in Example 2, these graphs contain a relatively small fraction of high degree nodes which are crucial for the overall system dynamics as they have many neighbors. Thus, we leverage the MF principle to model the important fraction of high degree agents who are close to the standard MF assumptions. Overall, the LWMFC model and our algorithms bridge the gap between rather dense topologies typically considered in MF setups, and ultrasparse graphs where the maximal degree is bounded. As our evaluations indicate, this gap contains many empirical networks which are modeled more accurately by LWMFC than by existing methods.\n\nFinally, the reviewer comments that “[…] error bars are essential for accurately evaluating the performance of the proposed method.” We do not report error bars in Table 2 because our learning approaches consistently outperform the IPPO benchmark on all problem-network combinations.", "claims_and_evidence": "The paper is clearly written, and the reviewer is not aware of any misleading claims. However, some definitions could be improved.  \n\nFor instance, in Definition 2.1, it is unclear what the expectation on the right-hand side is defined over. Since \\( f \\) is a deterministic mapping to the real number space and \\( G \\) is a fixed variable in this definition, the source of randomness needs to be explicitly stated.", "methods_and_evaluation_criteria": "The reviewer is primarily uncertain about the applicability of the mean-field method in the studied scenarios. Specifically, mean-field theory relies on an assumption that holds when agents are strongly influenced by their neighbors. However, this assumption does not hold in sparse graphs.  \n\nThis raises a fundamental question: What is the rationale for applying mean-field theory in this context? Can it accurately capture the underlying relationships expressed by these graphs?", "theoretical_claims": "The reviewer does not find errors in theoretical claims.", "experimental_designs_or_analyses": "The experimental design is well-structured, but error bars are essential for accurately evaluating the performance of the proposed method.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "The paper effectively references related works.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please see the questions mentioned in the above sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the mean field control problem on sparse interaction networks---i.e., a large multi-agent control problem in which agents' interactions are assumed to follow the mean field model. Existing methods of incorporating graph structures into mean-field control problems have often relied on gryphons or graphexes--- however neither of these approaches capture sparse connections often observed in many applications. Thus this paper expands upon these literatures to allow for sparser graph models (which is non trivial since these models start to diverge from the underlying mean-field assumption).  

This paper is rigorous and presents a compelling extension to the mean field control paradigm for a class of practically relevant graphs. Further they propose scalable learning algorithms that outperform existing methods. The reviews for this paper were borderline, but given its contributions I am recommending acceptance.
Decision: Accept (poster)