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

arXiv:2605.05020v1 Announce Type: new Abstract: System Neural Diversity (SND) measures behavioral heterogeneity in multi-agent reinforcement learning by averaging pairwise distances over all inom{n}{2} 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=K_n 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/sqrt{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 widetilde{O}(D_{max}/sqrt{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 10imes, and frozen-policy GPU timing up to n=500 follows the predicted inom{n}{2}/|E| speedup. Random d-regular expanders empirically achieve SND_{G}^{u}/SND in [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 {sim}9.5imes. 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.

Source: arXiv cs.LG | 2026-05-07