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
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 GMFS, a Graphon Mean-Field Subsampling 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 poly(κ) and optimality gap O(1/κ). We verify our theory with numerical simulations in robotic coordination, showing that GMFS achieves near-optimal performance.
Figures & tables
Figure 1: Graphon mean-field systems with distance-decay interactions . (a) Warehouse robots collaborate to transport a payload, where robot i uses κ=8 subsampled neighbors with interaction strength W(xi,xj) indicated by line thickness. (b) Traffic vehicles coordinate using graphon-weighted aggregates gi of the population, where interaction strength decays with distance in latent position space α∈[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 {αi}i=1n⊂[0,1] induces a complete weighted interaction graph on n agents with edge weights wij=W(αi,αj) and wii=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 κ=5 ) according to the normalized weights wˉij .
Figure 3: Performance-scalability tradeoff of GMFS. (Left) GMFS rapidly achieves near-optimal performance in the robotics coordination task starting from around κ=8 , approaching the full graphon mean-field baseline at κ=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 Zκ , grows polynomially in κ .
Figure 4: Perception time‑evolution comparison for the focal agent (center of the 5×5 grid) under the radial graphon. Rows correspond to κ∈{2,8,24} , while columns correspond to time horizons t∈{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 κ 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.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
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 (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 O(1/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.
Emile Anand, Ishani Karmarkar
Georgia Institute of Technology, Atlanta, GA · Stanford University, Palo Alto, CA
In this paper, we study cooperative multi-agent reinforcement learning (MARL) where the joint reward exhibits submodularity, which is a natural property capturing diminishing marginal returns when adding agents to a team. Unlike standard MARL with additive rewards, submodular rewards model realistic scenarios where agent contributions overlap (e.g., multi-drone surveillance, collaborative exploration). We provide the first formal framework for this setting and develop algorithms with provable guarantees on sample efficiency and regret bound. For known dynamics, our greedy policy optimization achieves a 1/2-approximation with polynomial complexity in the number of agents K, overcoming the exponential curse of dimensionality inherent in joint policy optimization. For unknown dynamics, we propose a UCB-based learning algorithm achieving a 1/2-regret of O(H2KSAT) over T episodes.
Wenjing Chen, Chengyuan Qian, Shuo Xing +2
Department of Computer Science and Engineering, Texas A&M University
Scaling cooperative multi-agent reinforcement learning (MARL) is fundamentally limited by cross-agent noise. When agents share a common reward, each agent's learning signal is computed from a shared return that depends on all agents, so the stochasticity of the other agents enters the signal as cross-agent noise that grows with N. Many engineering systems, such as cloud computing and power systems, have differentiable analytical models that prescribe efficient system states, providing a new reference beyond noisy shared returns. In this work, we propose Descent-Guided Policy Gradient (DG-PG), a framework that augments policy-gradient updates with a low-noise descent signal toward this reference. We prove that DG-PG reduces policy-gradient estimator variance from O(N) to O(1), preserves the stationary points of the cooperative objective, and achieves agent-independent sample complexity O(1/ε3). We evaluate DG-PG on cloud resource scheduling and power dispatch tasks, which involve discrete and continuous decisions, respectively. In both tasks, DG-PG converges within 10 episodes on average at every scale up to 1500 heterogeneous agents.