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

📄 arXiv: 2605.05020v1 📥 PDF

作者: Shawn Ray

分类: cs.LG, cs.MA

发布日期: 2026-05-06

备注: 22 pages, 12 figures, 7 tables

💡 一句话要点

提出Graph-SND以解决多智能体强化学习中的行为多样性问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多智能体强化学习 行为多样性 图神经网络 稀疏聚合 性能优化

📋 核心要点

  1. 现有的SND方法在计算复杂度上存在瓶颈，尤其是在智能体数量较多时，导致效率低下。
  2. Graph-SND通过引入加权平均和稀疏图结构，降低了计算复杂度，同时保持了多样性度量的准确性。
  3. 实验结果显示，Graph-SND在500次迭代中将每次调用的时间成本降低约10倍，并在多样性控制中表现出色。

📝 摘要（中文）

系统神经多样性（SND）通过对所有智能体对的成对距离进行平均来衡量多智能体强化学习中的行为异质性，导致每次调用的计算复杂度为二次。本文提出Graph-SND，用加权平均替代完整图的平均，降低了计算复杂度。通过三种不同的图结构，Graph-SND实现了在保持SND语义不变的情况下，显著提高了计算效率。实验结果表明，Graph-SND在多个场景中能够有效跟踪SND，同时减少每次调用的时间成本，支持多样性控制。

🔬 方法详解

问题定义：本文旨在解决多智能体强化学习中行为多样性度量的计算复杂度问题。现有的SND方法在智能体数量增加时，计算复杂度呈二次增长，导致效率低下。

核心思路：提出Graph-SND，通过在任意图结构上进行加权平均，替代传统的完整图平均，从而降低计算复杂度，同时保持多样性度量的语义一致性。

技术框架：Graph-SND的整体架构包括三个主要阶段：1) 选择图结构G；2) 计算加权平均；3) 进行多样性度量和控制。不同的图结构（如稀疏图和随机图）对应不同的计算效率和多样性度量。

关键创新：Graph-SND的主要创新在于引入了稀疏图和随机边采样的方法，使得在保持SND语义的前提下，显著降低了计算复杂度，支持更大规模的智能体系统。

关键设计：在设计中，采用了Bernoulli-$0.1$的随机边采样策略，并在固定稀疏图上证明了转发索引失真界限，确保了在不同图结构下的多样性度量的有效性。实验中还验证了在不同规模下的时间复杂度和性能表现。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在500次迭代的PPO运行中，Graph-SND在跟踪完整SND的同时，将每次调用的时间成本降低约10倍。实验还显示，在多样性控制中，Graph-SND能够有效保持设定点跟踪，且与零的奖励差异不可区分，证明了其在实际应用中的有效性。

🎯 应用场景

Graph-SND在多智能体系统中具有广泛的应用潜力，尤其是在需要实时决策和控制的场景，如机器人群体协作、智能交通系统和分布式控制等。通过提高多样性度量的效率，能够更好地支持复杂系统的优化与控制，推动相关领域的发展。

📄 摘要（原文）

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.