Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions
Tobias Schmidt, Kai Cui · 2026
Read Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions by Tobias Schmidt, Kai Cui (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21477.txt.
Introduction
Tobias Schmidt and Kai Cui extend mean-field control to agents linked by sparse networks. Mean-field methods tame huge multi-agent systems by treating the crowd as a smooth average. Classic versions assume every agent interacts with every other, which real networks rarely do.
The authors build a framework for large sparse graphs, where each agent has only a few neighbors. They connect local limit theory to graph neural networks through the statistics of each neighborhood. That bridge lets control methods scale to road networks, power grids, and robot swarms, where links are few but the system is vast.
Catalog record
| CREATOR | Tobias Schmidt, Kai Cui |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-21477
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions Tobias Schmidt, Kai Cui Abstract Mean-field control (MFC) offers a scalable solution to the curse of dimensionality in multi-agent systems but traditionally hinges on the restrictive assumption of exchangeability via dense, all-to-all interactions. In this work, we bridge the gap to real-world network structures by proposing a rigorous framework for MFC on large sparse graphs. We redefine the system state as a probability measure over decorated rooted neighborhoods , effectively capturing local heterogeneity. Our central contribution is a theoretical foundation for scalable reinforcement learning in this setting. We prove horizon-dependent locality : for finite-horizon problems, an agent’s optimal policy at time t t depends strictly on its ( T − t ) (T-t) -hop neighborhood. This result renders the infinite-dimensional control problem tractable and underpins a novel Dynamic Programming Principle (DPP) on the lifted space of neighborhood distributions. Furthermore, we formally and experimentally justify the use of Graph Neural Networks (GNNs) for actor-critic algorithms in this context. Our framework naturally recovers classical MFC as a degenerate case while enabling efficient, theoretically grounded control on complex sparse topologies. 1 Introduction The theory of mean-field games and control ( 1 ; 3 ) has emerged as a cornerstone for the study of large-scale multi-agent systems ( 29 ; 23 ; 8 ; 30 ) . By considering the limit as the number of agents N\to\infty , these frameworks circumvent the curse of dimensionality inherent in multi-agent reinforcement learning (MARL) problems ( 7 ; 15 ) . The core assumption is that agents are exchangeable and interact with the collective through a tractable aggregate statistic – the empirical distribution of states, or "mean field" (MF). A critical implicit assumption is that the interaction graph is the complete graph. While all-to-all interaction is reasonable for systems with long-range, homogeneous interactions, it fails to capture a vast array of real-world systems with local interactions. Examples include social networks ( 24 ) , power grids ( 11 ) , biological swarms ( 40 ) , and robotic networks ( 5 ) . The challenge of sparse graphs is profound: The local environment of each agent is distinct and stochastic, breaking symmetry that underpins classical MF theory. Recent work has begun to tackle this challenge by studying MF learning on random graphs ( 6 ; 10 ; 12 ; 44 ; 13 ; 45 ; 14 ) , showing that a MF limit can still be obtained. However, the limiting MF is no longer a simple state distribution but is related to the structure of the graph itself. This paper builds on these insights to construct a rigorous framework for reinforcement learning (RL) on sparse graphs. The central idea is to redefine the state of the system. Instead of a measure \mu\in\mathcal{P}(\mathcal{X}) on the agent’s state space \mathcal{X} , the state is a measure \bm{\mu}\in\mathcal{P}(\mathcal{G}_{*}^{\mathcal{X}}) on the space of decorated rooted graphs . This object, \bm{\mu} , describes the probability of observing any given local neighborhood structure, with each node in that neighborhood "decorated" by its state. For a finite T -horizon problem, we obtain and apply a crucial locality result: an agent’s optimal policy at time t depends only on the distribution of its (T-t) -hop neighborhood, providing a direct link between the problem horizon and the required locality of information. As a result, we have a Markov decision process (MDP) as a more tractable single-agent RL problem, and are able to design appropriate RL algorithms using GNNs with strong theoretical justification. 1.1 Related Work A large body of work studies how to compute equilibria and optimal controls in MFG/MFC using RL and deep learning ( 36 ; 17 ; 30 ) . In the finite-state/discrete-time setting, foundational RL approaches for MFGs include Q-learning-style algorithms that couple best responses with the MF fixed point ( 20 ) , and scalable deep RL variants that target large state spaces ( 31 ) . Complementary learning paradigms include fictitious play and extensions (e.g., common noise), with convergence analyses and practical implementations ( 36 ; 31 ) and generalization viewpoints ( 35 ) . For mean-field control (cooperative) rather than games, various policy-gradient methods have also been developed ( 16 ; 18 ; 9 ; 19 ) . A second related strand addresses many-agent RL by replacing interactions with a mean-field (average-neighbor) surrogate, yielding mean-field Q-learning / actor–critic algorithms with strong empirical performance in large populations ( 42 ; 17 ) . These methods typically assume that the relevant aggregate seen by an agent is an empirical average (often over neighbors), but they do not build a graph-local limiting distribution over rooted neighborhoods, and use a separate set of assumptions. Large graph theory and mean fields. To incorporate network heterogeneity, several works adopt dense graph limits via graphons, leading to graphon MFG/MFC and learning algorithms when interactions vary by latent graphon index ( 10 ; 22 ; 44 ; 45 ) . More recently, various graphon variants have been proposed to better capture sparsity (e.g. L^{p} -graphons) beyond dense graphons ( 12 ; 13 ) . On the probability/theory side, interacting processes on sparse graphs have a limiting description governed by local weak (Benjamini–Schramm) convergence, where the natural object is the law of a rooted neighborhood process; continuity of the dynamics with respect to local weak convergence is established in general frameworks ( 28 ) and successfully to MFC via heuristic algorithms ( 14 ) . Our contribution differs in emphasis and structure: we turn the local-weak-limit viewpoint into a dynamic programming framework for control by taking the system state to be a distribution over decorated rooted neighborhoods, proving a horizon-dependent locality principle that identifies the minimal radius required at each time step, and theoretically justifies the use of Graph Neural Networks as local policy approximators with approximate optimality. Our results show the limits of the heuristic but successful approach in ( 14 ) , contributing a rigorous solution and theoretical basis for algorithms. MARL on graphs Finally, our algorithmic blueprint connects to extensive MARL literature on graph-structured environments and GNN-based policies/value functions ( 25 ; 39 ; 37 ) , but these works typically proceed from a finite- N training objective rather than from an explicit sparse-graph mean-field limit. Our work provides separate motivation for architecture choices such as GNN especially in large sparse graphs where neighborhoods are of interest up to isomorphism. In contrast to classical MFC and learning, where the MF is a distribution over agent states and interaction structure is implicit (typically all-to-all), our framework replaces the mean field by a distribution over decorated rooted neighborhoods arising from the local weak limit of sparse graphs as shown in Fig. 1 . This shift preserves classical MFC as a special case while enabling a dynamic programming formulation that remains valid when interactions are local and the population is no longer exchangeable. i Finite System ( G_{N} ) Agent i observes local neighborhood ((G_{N},i),\mathbf{x})_{k} N\to\infty Local Weak Limit \bm{\mu}_{t} \rho System State \bm{\mu}_{t}\in\mathcal{P}(\mathcal{G}_{*}^{\mathcal{X}}) Distribution over decorated rooted graphs Sparse MF Limit Dynamics T_{t}(\bm{\mu}_{t},\pi) evolve MF of neighborhoods Time t t=0 Large Radius k=T t Medium Radius k=T-t t=T Local Only k=0 Theorem 2: Horizon-Dependent