Graph-snd: Sparse Aggregation For Behavioral Diversity In Multi-agent Reinforcement Learning

Abstract

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 \(\binom\{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\{\mathcal\{O\}\}(D_\{\max\}/\sqrt\{n\})\) bound. On VMAS we verify

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyray2026graph

Related papers

• System Neural Diversity: Measuring Behavioral Heterogeneity In Multi-agent Learning (2023)0.00
• Structured Diversity Control: A Dual-level Framework For Group-aware Multi-agent Coordination (2025)0.00
• The Impact Of Behavioral Diversity In Multi-agent Reinforcement Learning (2024)0.00
• Federated Stochastic Approximation Under Markov Noise And Heterogeneity: Applications In Reinforcement Learning (2022)0.00
• Unifying Behavioral And Response Diversity For Open-ended Learning In Zero-sum Games (2021)0.00
• Social Diversity And Social Preferences In Mixed-motive Reinforcement Learning (2020)0.00
• Selection-expansion: A Unifying Framework For Motion-planning And Diversity Search Algorithms (2021)0.00
• Harnessing Distribution Ratio Estimators For Learning Agents With Quality And Diversity (2020)0.00