用稀疏图替代全连接计算行为多样性，速度提升10倍且结果准确。
Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning
- 用任意图的边加权平均代替全连接对距离求平均，降低计算复杂度。
- 在100智能体场景下，单次调用耗时减少约10倍，结果与完整计算几乎一致。
- 适用于大规模多智能体系统的行为测量与闭环控制，适合需要高效评估的场景。
系统神经多样性（SND）通过所有智能体对间的成对距离平均来衡量多智能体强化学习中的行为异质性，每次调用的时间复杂度为团队规模的平方。本文提出图-SND（Graph-SND），将该完全图平均替换为任意图 $G$ 上边的加权平均。三种情形：$G=K_n$ 时精确恢复 SND；固定稀疏 $G$ 使度量局部化，成本降至 $O(|E|)$；随机采样边可得无偏霍尔维茨-汤普森估计量，样本均值以 $O(1/ ext{sqrt}{m})$ 速率集中于采样边数 $m$。对固定稀疏图，证明了膨胀图的前向索引失真界及低秩距离结构下的谱优化；对随机 $d$-正则图，给出无条件概率 $ ilde{ ext{O}}(D_{ ext{max}}/ ext{sqrt}{n})$ 界。在 VMAS 上验证了恢复性、无偏性、集中性和墙钟时间缩放性，PettingZoo TVD 面板显示非高斯迁移特性。在 $n=100$ 的500次迭代PPO运行中，伯努利-$0.1$ 图-SND 跟踪完整SND，单次调用时间减少约10倍；冻结策略的GPU计时支持至 $n=500$，符合预测的 $inom{n}{2}/|E|$ 加速比。随机 $d$-正则膨胀图在 $\Theta(n \log n)$ 条边下实现 $ ext{SND}_G^u / ext{SND} \in [0.9987, 1.0013]$。在 $n=50$ 的DiCo多样性控制中，伯努利-$0.1$ 图-SND 在九组匹配单元中保持设定点跟踪，配对奖励差异不可区分，同时将单次调用成本降低约9.5倍。结果表明，可通过稀疏图替代消除SND聚合瓶颈，无需改变语义，提供可直接替换的高效扩展方案，支持被动测量与闭环多样性控制。
原文摘要 · Abstract (English)
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 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\times$, and frozen-policy GPU timing up to $n=500$ follows the predicted $\binom{n}{2}/|E|$ speedup. Random $d$-regular expanders empirically achieve $\mathrm{SND}_{G}^{\mathrm{u}}/\mathrm{SND} \in [0.9987, 1.0013]$ at $Θ(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.5\times$. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。