技术摘要：Graph-SND：多智能体强化学习中的行为多样性稀疏聚合

1. 问题陈述

在多智能体强化学习（MARL）中，系统神经多样性（SND） 是一种通过平均智能体动作分布之间的成对 Wasserstein 距离来衡量智能体间行为异质性的指标。虽然 SND 能够实现多样性控制（例如通过 DiCo 算法），但其计算存在严重的可扩展性瓶颈。计算完整的 SND 需要评估所有 $\binom{n}{2}$ 个智能体对，导致关于智能体数量 $n$ 的二次 $O(n^2)$ 复杂度。这种聚合成本对于大规模团队而言变得难以承受，限制了多样性感知训练和控制的实际应用。该论文将“子群到系统的聚合”步骤确定为主要的开放挑战，指出现有指标将全对平均视为固定的、不可协商的要求。

2. 方法论：Graph-SND

作者引入了 Graph-SND，这是 SND 的一种推广，用任意图 $G = (A, E, w)$ 边上的加权平均替代了完全图平均。

定义

设 $d(i, j)$ 为智能体 $i$ 和 $j$ 之间的蒙特卡洛行为距离。Graph-SND 定义为：
$$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$$
其中 $W(G) = \sum_{\{i,j\} \in E} w_{ij}$ 是总边权重。

三种运行模式

该框架根据图 $G$ 的选择支持三种不同的模式：

1. 精确恢复（$G = K_n$）： 当 $G$ 是单位权重的完全图时，Graph-SND 精确恢复原始 SND。
2. 局部化多样性（固定稀疏图）： 当 $G$ 是固定稀疏图（例如 $k$-近邻、通信拓扑）时，该指标仅测量与任务相关的交互中的多样性。这将计算成本降低至 $O(|E|)$。
3. 稀疏估计（随机图）： 当边被随机采样（例如伯努利采样）时，Graph-SND 充当完整 SND 的稀疏估计量。
   • 无偏估计： 使用 Horvitz-Thompson 权重（$w_{ij} = 1/p$），该估计量是无条件无偏的。
   • 集中性： 归一化样本均值（均匀权重）满足 Hoeffding 型集中界限，以 $O(1/\sqrt{m})$ 的速率收敛到真实 SND，其中 $m$ 是采样的边数。

理论界限

• 确定性失真： 对于固定的连通图，论文利用 边转发指数 $\pi(G)$ 推导了 $\text{SND}_G$ 与 $\text{SND}$ 之间的界限。具体而言，$|\text{SND}_G - \text{SND}|$ 受涉及 $\pi(G)$ 的因子限制。
• 扩张图： 对于随机 $d$-正则扩张图，转发指数按 $O(n \log n / d)$ 缩放。作者证明，当 $d = \Theta(\log n)$ 时，最坏情况下的相对失真为 $O(\log n)$。
• 谱细化： 在低秩距离结构（受控的归一化核范数）下，扩张图的误差界限改进为 $O(\rho^*/\sqrt{d})$，解释了经验中接近 1 的比率。
• 概率界限： 对于随机 $d$-正则图，建立了 $\tilde{O}(D_{\max}/\sqrt{n})$ 的无条件概率界限。

3. 主要贡献

1. Graph-SND 的定义： 一个稀疏聚合层，在完全图上恢复 SND，并在预计算图上具有 $O(|E|)$ 的成本。
2. 理论保证： 证明了恢复性、非负性、图自同构不变性、Horvitz-Thompson 无偏性以及集中不等式（Hoeffding/Serfling）。论文还建立了固定图的确定性失真界限和随机正则图的无条件概率界限。
3. 实证验证：
   • 恢复与无偏性： 在 VMAS 环境中进行了验证，显示在 $K_4$ 上实现了精确恢复，并在 $n=8$ 时证明了 Horvitz-Thompson 估计量的无偏性。
   • 扩展性： 展示了与 $1/p$（采样概率）成线性比例的实时加速，直至 $n=500$。
   • 闭环控制： 将 Graph-SND 集成到 DiCo 多样性控制器中。在 $n=50$ 时，伯努利 -0.1 Graph-SND 以小于 1% 的相对误差跟踪设定点，并且与完整 SND 相比产生的奖励差异无法区分（接近零），同时将每次调用的指标成本降低了约 $9.5$ 倍。
   • 扩张图性能： 随机 $d$-正则扩张图在 $\Theta(n \log n)$ 条边处实现了 $\text{SND}_G/\text{SND} \in [0.9987, 1.0013]$，在失真与成本比率方面显著优于其他稀疏基线。

4. 结果

• 效率： 在 $n=100$ 的 500 次迭代 PPO 运行中，伯努利 -0.1 Graph-SND 跟踪了完整 SND，同时将每次调用的指标时间减少了约 $10$ 倍。
• 可扩展性： 高达 $n=500$ 的固定策略 GPU 计时确认了预测的 $\binom{n}{2}/|E|$ 加速比，在 $n=500$ 且边密度为 10% 时，将指标时间从约 15.5 秒减少到约 1.5 秒。
• 控制稳定性： 在 $n=50$ 的 DiCo 实验中，稀疏控制器保持了设定点跟踪，并在九个匹配单元中产生了以零为中心的成对奖励差异，平均奖励差异为 $-6.2 \times 10^{-4}$。
• 鲁棒性： 该方法迁移到了非高斯设置（具有分类策略和总变分距离的 PettingZoo MPE），保持了较小的偏差和成本降低。

5. 意义与主张

该论文声称，Graph-SND 成功消除了 SND 的聚合瓶颈，同时不改变指标的语义，也不需要更改策略架构或训练算法。

• 即插即用替代方案： 它提供了一种“即插即用的稀疏替代方案”，可扩展至完全图 SND 之外，支持被动测量和闭环多样性控制。
• 语义灵活性： 图 $G$ 被呈现为一种 deliberate 的选择，决定了测量目标，而非一个 nuisance 参数：
  • 使用 伯努利采样 来估计完整系统的多样性。
  • 使用 固定局部图（例如通信、$k$-NN）来测量与特定交互结构相关的多样性。
  • 使用 扩张图 以获得具有强最坏情况结构保证的确定性、近线性稀疏代理。
• 适度的局限性： 作者承认，虽然扩张图的理论界限为 $O(\log n)$，但观察到的接近 1 的比率是数据依赖的，并且部分由 MARL 距离矩阵的谱性质解释。他们还指出，当前实验集中于独立 PPO，集中式评论家算法留待未来工作。

总之，Graph-SND 将多样性聚合重新定义为图选择问题，提供了一个统一的框架，在 MARL 的行为多样性中平衡了计算效率与理论保证。