# Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 6 May 2026.

## Builds on (most cited first, 14 of 14)

- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [ROMA: Multi-Agent Reinforcement Learning with Emergent Roles](https://mlsanity.com/paper/2003.08039/) (2020)
- [RODE: Learning Roles to Decompose Multi-Agent Tasks](https://mlsanity.com/paper/2010.01523/) (2020)
- [Effective Diversity in Population Based Reinforcement Learning](https://mlsanity.com/paper/2002.00632/) (2020)
- [VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning](https://mlsanity.com/paper/2207.03530/) (2022)
- [Heterogeneous Multi-Robot Reinforcement Learning](https://mlsanity.com/paper/2301.07137/) (2023)
- [The Emergence of Adversarial Communication in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2008.02616/) (2020)
- [Quantifying the effects of environment and population diversity in multi-agent reinforcement learning](https://mlsanity.com/paper/2102.08370/) (2021)
- [System Neural Diversity: Measuring Behavioral Heterogeneity in Multi-Agent Learning](https://mlsanity.com/paper/2305.02128/) (2023)
- [Policy Diagnosis via Measuring Role Diversity in Cooperative Multi-agent RL](https://mlsanity.com/paper/2207.05683/) (2022)
- [Controlling Behavioral Diversity in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2405.15054/) (2024)
- [HyperMARL: Adaptive Hypernetworks for Multi-Agent RL](https://mlsanity.com/paper/2412.04233/) (2024)
- [The impact of behavioral diversity in multi-agent reinforcement learning](https://mlsanity.com/paper/2412.16244/) (2024)
- [When Is Diversity Rewarded in Cooperative Multi-Agent Learning?](https://mlsanity.com/paper/2506.09434/) (2025)

## Abstract (arXiv)

System Neural Diversity (SND) measures behavioral heterogeneity in multi-agent reinforcement learning by averaging pairwise distances over all binomn2 agent pairs, making each call quadratic in team size. We introduce Graph-SND, which replaces this complete-graph average with a weighted average over the edges of an arbitrary graph G. Three regimes follow: G=Kn recovers SND exactly; a fixed sparse G defines a localized diversity measure at O(|E|) cost; and random edge samples yield an unbiased Horvitz-Thompson estimator and a normalized sample mean with O(1/√m) concentration in the sampled edge count m. For fixed sparse graphs we prove forwarding-index distortion bounds for expanders and a spectral refinement under low-rank distance structure; for random d-regular graphs we prove an unconditional probabilistic widetildeO(Dmax/√n) bound. On VMAS we verify recovery, unbiasedness, concentration, and wall-clock scaling, with a PettingZoo TVD panel checking non-Gaussian transfer. In a 500-iteration n=100 PPO run, Bernoulli-0.1 Graph-SND tracks full SND while reducing per-call metric time by about 10×, and frozen-policy GPU timing up to n=500 follows the predicted binomn2/|E| speedup. Random d-regular expanders empirically achieve SNDGu/SND ∈ [0.9987, 1.0013] at Theta(n log n) edges. In DiCo diversity control at n=50, Bernoulli-0.1 Graph-SND preserves set-point tracking with paired reward differences indistinguishable from zero across nine matched cells while cutting per-call metric cost by ~9.5×. Together, these results show that the SND aggregation bottleneck can be removed without changing the metric's semantics, yielding a drop-in sparse alternative that scales beyond complete-graph SND and supports both passive measurement and closed-loop diversity control.