Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning

Emile Anand; Richard Hoffmann; Sarah Liaw; Adam Wierman

cs.LGFeb 18, 2026

Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning

Authors: Emile Anand, Richard Hoffmann, Sarah Liaw, Adam Wierman

Organizations: School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA · Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA · Kempner Institute, Harvard University, Cambridge, MA, USA

Abstract

Coordinating large populations of interacting agents is a central challenge in multi-agent reinforcement learning (MARL), where the size of the joint state-action space scales exponentially with the number of agents. Mean-field methods alleviate this burden by aggregating agent interactions, but these approaches assume homogeneous interactions. Recent graphon-based frameworks capture heterogeneity, but are computationally expensive as the number of agents grows. Therefore, we introduce $\texttt{GMFS}$ , a $\textbf{G}$ raphon $\textbf{M}$ ean- $\textbf{F}$ ield $\textbf{S}$ ubsampling framework for scalable cooperative MARL with heterogeneous agent interactions. By subsampling $κ$ agents according to interaction strength, we approximate the graphon-weighted mean-field and learn a policy with sample complexity $\mathrm{poly}(κ)$ and optimality gap $O(1/\sqrtκ)$ . We verify our theory with numerical simulations in robotic coordination, showing that $\texttt{GMFS}$ achieves near-optimal performance.

Figures & tables

Panel of Figure 1 — Figure 1: Graphon mean-field systems with distance-decay interactions . (a) Warehouse robots collaborate to transport a payload, where robot $i$ uses $\kappa=8$ subsampled neighbors with interaction strength $W(x_{i},x_{j})$ indicated by line thickness. (b) Traffic vehicles coordinate using graphon-weighted aggregates $g_{i}$ of the population, where interaction strength decays with distance in latent position space $\alpha\in[0,1]$ .

Figure 2: Schematic of Graphon Mean-Field Sampling. (Left) A continuous graphon

W(x,y)

represents the infinite-population limit of non-uniform interactions. (Middle) The graphon with deterministic latent positions

\{\alpha_{i}\}_{i=1}^{n}\subset[0,1]

induces a complete weighted interaction graph on

n

agents with edge weights

w_{ij}=W(\alpha_{i},\alpha_{j})

and

w_{ii}=0

. These weights specify the intensity with which agent

i

aggregates neighbor states into its mean-field features used for learning and control. (Right) Each agent approximates its graphon-weighted neighborhood statistics by sampling a small set of agents (random subsample of

\kappa=5

) according to the normalized weights

\bar{w}_{ij}

\hat{g}_{i}^{(\kappa)}(x)=\frac{1}{\kappa}\sum_{m=1}^{\kappa}\mathbbm{1}\{s_{J_{i}^{(m)}(t)}(t)=x\}.

Algorithm 2 GMFS (Graphon Mean-Field Subsampling): Online Execution

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Performance-scalability tradeoff of GMFS. (Left) GMFS rapidly achieves near-optimal performance in the robotics coordination task starting from around $\kappa=8$ , approaching the full graphon mean-field baseline at $\kappa=24$ (which corresponds to the optimal solution obtained without sampling) ( Hu et al., 2023 ; Fabian et al., 2022 ) . (Right) The computational cost, measured by the number of entries in the discrete neighborhood state space $\mathcal{Z}_{\kappa}$ , grows polynomially in $\kappa$ .

Figure 4: Perception time‑evolution comparison for the focal agent (center of the $5\times 5$ grid) under the radial graphon. Rows correspond to $\kappa\in\{2,8,24\}$ , while columns correspond to time horizons $t\in\{1,30,60,100\}$ . Each panel aggregates the focal agent’s sampled neighbors up to time $t$ , with the dashed circle indicating the true interaction ball. As $\kappa$ increases, the empirical neighborhood density converges faster and more uniformly to the support of the radial graphon.

Figure 5: Visualization of a radial graphon. We note that generative AI was used to refine the aesthetics of this figure.

Hyperparameter	Value
Discount Factor ( $\gamma$ )	0.95
Training Iterations ( $T$ )	250
Subsample Sizes ( $\kappa$ )	$\{1,3,6,9,12,15,18,21,24\}$
Monte Carlo Samples ( $M$ )	50 (per Bellman update)
Learning Rate ( $\alpha$ )	1.0 (Exact Operator Update)
Exploration Rate ( $\epsilon$ )	0.0 (Exhaustive Offline Sweep)

Appendix

Table 1: GMFS Training Configuration

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling
Mar 4, 2026Emile Anand, Ishani KarmarkarReinforcement Learning Cooperative MARL
Georgia Institute of Technology, Atlanta, GA · Stanford University, Palo Alto, CA
Multi-Agent Reinforcement Learning with Submodular Reward
Mar 6, 2026Wenjing Chen, Chengyuan Qian, Shuo Xing +2Cooperative MARL Multi-Agent Reinforcement Learning
Department of Computer Science and Engineering, Texas A&M University
Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning
Feb 23, 2026Shan Yang, Yang LiuCooperative MARL Multi-Agent Reinforcement Learning
National University of Singapore

Mar 4, 2026J/K move · Enter open · S save

Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling

Emile Anand, Ishani Karmarkar

Georgia Institute of Technology, Atlanta, GA · Stanford University, Palo Alto, CA

Reinforcement Learning Cooperative MARL Multi-Agent Coordination Partially Observable RL

Open paper AskPDF arXiv

Many large-scale platforms and networked control systems have a centralized decision maker interacting with a massive population of agents under strict observability constraints. Motivated by such applications, we study a cooperative Markov game with a global agent and

n

homogeneous local agents in a communication-constrained regime, where the global agent only observes a subset of

k

local agent states per time step. We propose an alternating learning framework

(\texttt{ALTERNATING-MARL})

, where the global agent performs subsampled mean-field

Q

-learning against a fixed local policy, and local agents update by optimizing in an induced MDP. We prove that these approximate best-response dynamics converge to an

\widetilde{O}(1/\sqrt{k})

-approximate Nash Equilibrium, while separating the sample complexities between the joint state and action spaces. Finally, we validate our results in numerical simulations for multi-robot control.

Abstract

Reinforcement Learning

Explore similar work

Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling

Multi-Agent Reinforcement Learning with Submodular Reward

Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning