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

arXiv: https://arxiv.org/abs/2602.16196 · HTML: https://mlsanity.com/paper/2602.16196/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 56 of its 86 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 30 of 56)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising](https://mlsanity.com/paper/1802.09756/) (2018)
- [Learning in Mean Field Games: A Survey](https://mlsanity.com/paper/2205.12944/) (2022)
- [Model-Free Mean-Field Reinforcement Learning: Mean-Field MDP and Mean-Field Q-Learning](https://mlsanity.com/paper/1910.12802/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.11454/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Multi-Agent Reinforcement Learning Based Resource Allocation for UAV Networks](https://mlsanity.com/paper/1810.10408/) (2018)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Stochastic blockmodel approximation of a graphon: Theory and consistent estimation](https://mlsanity.com/paper/1311.1731/) (2013)
- [Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning](https://mlsanity.com/paper/2107.04050/) (2021)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Active Sampling for Min-Max Fairness](https://mlsanity.com/paper/2006.06879/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)](https://mlsanity.com/paper/2109.04024/) (2021)
- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Learning Graphon Mean Field Games and Approximate Nash Equilibria](https://mlsanity.com/paper/2112.01280/) (2021)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning](https://mlsanity.com/paper/1806.01584/) (2018)

## Built on by (most cited first, 1 of 1)

- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)

## Abstract (arXiv)

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 textttGMFS, a Graphon Mean-Field Subsampling framework for scalable cooperative MARL with heterogeneous agent interactions. By subsampling kappa agents according to interaction strength, we approximate the graphon-weighted mean-field and learn a policy with sample complexity poly(kappa) and optimality gap O(1/√kappa). We verify our theory with numerical simulations in robotic coordination, showing that textttGMFS achieves near-optimal performance.