有时需要随机性来实现协调

# 协调有时需要随机性

来源：https://arxiv.org/html/2605.06825
Rohan Patil∗ Jai Malegaonkar Henrik I\. Christensen 加州大学圣地亚哥分校计算机科学与工程系 加利福尼亚州圣地亚哥，邮编 92093 \{rpatil, jmalegaonkar, hichristensen\}@ucsd\.edu

###### 摘要

在全参数共享是合作式多智能体强化学习（MARL）中同质智能体的标准做法。然而，在置换对称观测下，共享的确定性策略会为每个智能体输出相同的动作分布，使得角色分化成为不可能。理论上，可以通过匿名同质处理器之间的对称性破缺来解决这一失败，而这需要随机性。我们提出了 Diamond Attention（钻石注意力），这是一种交叉注意力架构，其中每个智能体在每个时间步采样一个标量随机数，从而诱导出一个瞬时的排名顺序，该顺序对低排名同伴进行智能体间注意力掩码，同时保持任务注意力完全无掩码。这在一个广播轮次中实现了基于随机位的协调协议，并且基于集合的注意力机制使得策略能够零样本部署到不同规模的团队中。我们在三个隔离了结构化随机性重要性的场景中进行评估。在完全对称的 XOR 游戏中，我们的方法实现了 1.0 的成功率，而所有确定性基线均停滞在 0.5 附近。在控制协调任务中，在 N=4 上训练的策略能够零样本泛化到 N∈[2,8]。在 SMACLite 跨场景迁移中，我们实现了基线因结构限制而无法完成的零样本迁移。此外，用标准的基于 dropout 的随机性替换结构化掩码会导致胜率为 0%，证实了协议空间的结构而非随机噪声才是关键要素。https://anonymous.4open.science/r/randomness-137A/

## 1 引言

合作式多智能体强化学习（MARL）中广泛采用的设计选择是全参数共享，其中所有同质智能体执行单个学习策略的副本 Gupta et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib9)); Terry et al\. (2020 (https://arxiv.org/html/2605.06825#bib.bib26))。结合集中式训练与去中心化执行（CTDE）范式 Lowe et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib15)) 以及诸如 VD Sunehag et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib25)) 和 QMIX Rashid et al\. (2020 (https://arxiv.org/html/2605.06825#bib.bib21)) 等价值分解方法，这种方法减少了样本复杂度，简化了训练基础设施，并随着团队规模的增加自然扩展。它已成为合作式 MARL 的默认基础 Sunehag et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib25)); Rashid et al\. (2020 (https://arxiv.org/html/2605.06825#bib.bib21)); Gronauer & Diepold (2022 (https://arxiv.org/html/2605.06825#bib.bib8)); Oroojlooy & Hajinezhad (2023 (https://arxiv.org/html/2605.06825#bib.bib18))。这种默认设置在具有多模态奖励结构的任务中会失效，在这些任务中存在多个同等最优的联合策略。在此类条件下，当观测在结构上相同时，所有智能体产生的动作分布相同，使得角色分化变得不可能。Fu et al\. (2022 (https://arxiv.org/html/2605.06825#bib.bib7)) 使用 XOR 游戏——两个智能体必须选择相反的动作才能获得任何奖励——来表明共享的确定性策略会为两个智能体输出相同的动作，无论训练时间多长都保证零奖励，从而说明这并非可以通过更好优化解决的实证病理现象。

Angluin (1980 (https://arxiv.org/html/2605.06825#bib.bib1)) 证明了在匿名处理器之间进行确定性对称性破缺是不可能的；Case et al\. (2005 (https://arxiv.org/html/2605.06825#bib.bib4)) 将这一结论扩展到合作游戏，确立了当智能体缺乏唯一标识符时，访问共享随机位对于协调是*必要的*，而不仅仅是有益的。第 2 节 (https://arxiv.org/html/2605.06825#S2) 发展了这些理论基础，并回顾了先前工作在每个维度上的不足。

现有方法在两个轴向上解决这一问题，但没有一种先前方法能同时满足这两个条件。修改参数共享或优化动态的方法提高了对称设置中的协调性，但在执行时仍然是确定性的，未能满足理论上的随机性要求。通过顺序执行实现对称性破缺的方法解决了符号问题，但需要 O\(N\) 推理轮次和外部强加的执行顺序——这在真正去中心化的同质环境中本身就是对称性破缺问题。

我们将 Case et al\. (2005 (https://arxiv.org/html/2605.06825#bib.bib4)) 的理论处方转化为实用的 MARL 架构。我们提出的*Diamond Attention*是一种智能体嵌入和任务嵌入之间的交叉注意力机制，其中包含结构化随机掩码。在每个时间步，每个智能体采样一个标量随机数，并通过单次广播轮次与团队共享。这些标量在智能体之间诱导严格的排名顺序，在智能体维度上生成不对称的注意力掩码：每个智能体掩码所有排名低于它的智能体，仅关注排名等于或高于它的智能体。掩码仅应用于智能体间的注意力；任务注意力保持完全无掩码。由此产生的不对称性创建了一个动态的、每步的层次结构，其中高排名智能体关注少数同伴并主要独立行动，而低排名智能体则根据其高层级同伴的行为调整自己的行为。由于 Diamond Attention 在智能体和任务嵌入的集合上运行，因此该架构无需修改即可接受任意数量的智能体和任意数量的任务：在一个团队规模上训练的策略可以零样本泛化到其他规模，这是计算变长序列注意力的固有属性。

我们的贡献如下：

- • 理论。我们形式化了 XOR 协调与随机位共享之间的等价性，提供了激励 Diamond Attention 每个架构组件的理论桥梁，并将结构化掩码建立在 Case et al\. (2005) 的必要性结果之上。
- • 架构。我们提出了 Diamond Attention，它通过单次广播轮次中的结构化随机掩码实现了这一协议，同时保留了标准交叉注意力的基于集合的可扩展性。该架构不需要顺序执行，也不需要外部智能体标识符。
- • 实证验证。我们在三个领域进行了验证：Diamond Attention 是唯一在 XOR 游戏中实现 1.0 成功的方法，而所有确定性基线都停滞在随机动作地板上；在 VMAS 连续协调任务中，在 N=4 上训练的策略可以零样本泛化到 N∈[2,8]；并且该架构实现了从较容易到较难的 SMACLite 场景的零样本迁移，而所有基线和消融实验均完全失败。

## 2 相关工作

参数共享（PS）已成为合作式 MARL 的主导范式 Gupta et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib9)); Terry et al\. (2020 (https://arxiv.org/html/2605.06825#bib.bib26))，特别是当与 CTDE 框架 Lowe et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib15)) 以及诸如 VD Sunehag et al\. (2017 (https://arxiv.org/html/2605.06825#bib.bib25)) 和 QMIX Rashid et al\. (2020 (https://arxiv.org/html/2605.06825#bib.bib21)) 等价值分解方法结合使用时。在对称观测下，共享的确定性策略会为所有智能体产生相同的输出，改善一个智能体策略的梯度更新会以相同方式影响所有其他智能体 Fu et al\. (2022 (https://arxiv.org/html/2605.06825#bib.bib7))，将系统困在对称平衡中。最近的工作在保持 PS 效率的同时缓解了这一问题：Kaleidoscope Li et al\. (2024 (https://arxiv.org/html/2605.06825#bib.bib12)) 引入了可学习的稀疏掩码以在训练时诱导每个智能体的异质性，GradPS Qin et al\. (2025 (https://arxiv.org/html/2605.06825#bib.bib19)) 解决了由相反更新信号引起的梯度冲突，pH-MARL Sebastián et al\. (2025 (https://arxiv.org/html/2605.06825#bib.bib23)) 利用端口-哈密顿几何先验来强制有效的分布式协调结构。然而，Kaleidoscope 的学习掩码在训练后是确定性的；GradPS 在优化期间解决梯度冲突，但在执行时不产生智能体间的差异化；pH-MARL 的几何先验强制协调结构而不引入理论所需的随机性。这些方法解决的是对称性问题的症状，而非其理论根源。

一个相关的挑战是零样本可扩展性：在不重新训练的情况下将训练好的策略部署到规模不同的团队 Liu et al\. (2024 (https://arxiv.org/html/2605.06825#bib.bib13))。UPDeT Hu et al\. (2021 (https://arxiv.org/html/2605.06825#bib.bib10)) 通过将每个智能体的观测视为变长序列的一部分来实现可扩展性，但智能体从独立观测同时行动，未解决多模态奖励设置中的对称性破缺。自回归模型 MAT Wen et al\. (2022 (https://arxiv.org/html/2605.06825#bib.bib28)) 和 Sable Mahjoub et al\. (2024 (https://arxiv.org/html/2605.06825#bib.bib16)) 通过顺序执行在结构上实现对称性破缺，但代价是 O\(N\) 推理延迟和外部强加的执行顺序——建立这一顺序需要一种协调机制，而在真正去中心化的同质环境中，就谁先执行达成一致等同于解决对称性破缺问题，这使得该方法循环依赖于它无法提供的假设。我们并不声称在外部可用固定排序的情况下具有更优的协调质量；我们的贡献是正交的，解决了 UPDeT 和 MAT 在不同轴向上各自留下的空白。

我们方法的理论基础追溯至分布式计算。Angluin (1980 (https://arxiv.org/html/2605.06825#bib.bib1)) 证明了在匿名网络中确定性对称性破缺是不可能的。Fischer et al\. (1985 (https://arxiv.org/html/2605.06825#bib.bib6)) 确立了即使在单个故障情况下，异步系统中的共识也无法实现，强化了即使在中度对抗条件下确定性协调协议也是脆弱的这一观点。Case et al\. (2005 (https://arxiv.org/html/2605.06825#bib.bib4)) 表明共享随机位解决了合作游戏中的这一不可能性，使得在有界失败概率下协调成为可能。MP-MAB 文献 Liu & Zhao (2010 (https://arxiv.org/html/2605.06825#bib.bib14)); Shi & Shen (2021 (https://arxiv.org/html/2605.06825#bib.bib24)) 通过结构与多模态 MARL 中的协调失败相同的碰撞模型得出了相同的结论：被分配给相同臂的智能体和选择相同动作的智能体面临相同的正交化问题，在这两种情况下，确定性策略都无法逃脱。

诸如 UPDeT 等基于注意力的方法实现了跨不同团队规模的零样本可扩展性，但未解决多模态奖励设置中的对称性破缺。诸如 MAT 和 Sable 等自回归方法在结构上实现了对称性破缺，但需要 O\(N\) 顺序轮次和外部强加的执行顺序。Diamond Attention 解决了这一交集：基于 Case et al\. (2005 (https://arxiv.org/html/2605.06825#bib.bib4)) 确立的理论必要性的结构化随机性，使得在单次广播轮次中实现协调成为可能，同时保留了标准交叉注意力的基于集合的可扩展性。没有先前的 MARL 架构将这一协议作为架构原语实现。

## 3 动机与模型架构

我们首先形式化激励我们方法的核心局限性。

###### 定义 3.1（对称性破缺）。

在具有 n 个同质智能体共享单一策略 $\pi_\theta$ 的合作式多智能体系统中，*对称性破缺*是指智能体尽管接收到结构相同的观测，仍能产生差异化动作分布的能力。形式上，如果智能体 $i$ 和 $j$ 的观测 $o_i$ 和 $o_j$ 在智能体索引的置换下相等，则根据参数共享，$\pi_\theta(o_i) = \pi_\theta(o_j)$，因此差异化行为必须源于差异化内部状态，而非策略本身。

接下来我们详细介绍 XOR 游戏，它为我们的架构提供了理论基础，并推导结果协议的每个组件如何在 Diamond Attention 机制中实现。

### 3.1 XOR 游戏

XOR 游戏 Fu et al\. (2022 (https://arxiv.org/html/2605.06825#bib.bib7)) 是一个单步合作游戏，其中两名玩家各自从两个动作中选择一个；如果他们的动作不同，两人都获得奖励 1，否则为 0（表 1 (https://arxiv.org/html/2605.06825#S3.T1)）。将其推广到 n 名玩家和 k 个动作（$n \leq k$）仅在所有玩家选择不同的动作时产生奖励，这与多智能体多臂老虎机文献中的碰撞模型类似 Liu & Zhao (2010 (https://arxiv.org/html/2605.06825#bib.bib14))。

|   | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |

表 1：2 玩家 XOR 游戏的支付矩阵。虽然自回归方法可以通过让智能体顺序行动并基于前驱者的动作进行条件判断来解决 XOR Fu et al\. (2022 (https://arxiv.org/html/2605.06825#bib.bib7))，但所需的通信轮次随团队规模线性增长。更根本的是，在真正去中心化的同质环境中，建立执行顺序本身需要随机位，这等同于解决广义 XOR 游戏。

Case et al\. (2005 (https://arxiv.org/html/2605.06825#bib.bib4)) 证明，诸如 XOR 之类的协调游戏可以通过在单次通信轮次中共享随机位在异构环境中解决：每个玩家生成一串位，并以有界概率所有串都是唯一的，从而通过对位串的任何固定全序实现协调。没有随机性，智能体在真正去中心化的设置中必然无法获得最优支付。为了形式化这一点，我们将玩家建模为与 Inexhaustible Interactive Turing Machine 框架一致的状态机 Küsters et al\. (2013 (https://arxiv.org/html/2605.06825#bib.bib11))。在我们的公式中，机器不进行点对点通信，而是广播消息。$^{111}$Küsters et al\. (2013 (https://arxiv.org/html/2605.06825#bib.bib11)) 具有点对点通信。虽然广播的来源无法区分，但智能体可以确定有多少台机器正在广播相同的输入——这可以通过频率调制接收器实现，其中信号强度指示广播机器的数量。

###### 定义 3.2（玩家）。

玩家是一台用有限输入初始化的机器，可以执行四种例程，并根据输入在它们之间转换：Compute（在当前磁带上运行任何终止图灵机，其最终状态成为新输入）；Broadcast（将输入的一部分传输给其他智能体）；Receive（将传入的广播附加到输入中）；以及 Sample（将新采样的均匀随机位附加到输入中）。每个非计算例程返回到 Compute。停机时的最终输入状态是玩家的输出。

###### 定义 3.3（同质性）。

如果对于任何输入 I 和任何随机