Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks

想象一个这样的世界：机器人团队、自动驾驶汽车甚至 AI 助手协同工作，共同解决重大问题，比如交付包裹或管理电网。在理想的世界里，团队中的每个成员都完美地执行计划。但在现实中，事情总会出错。有时是机器人发生故障，更糟的是，一个“叛徒”潜入了团队。在计算机科学中，我们称这些叛徒为“拜占庭”（Byzantine）代理。把他们想象成间谍电影里的间谍，他们不仅没有退出，反而留在房间里，假装在提供帮助，却在指令执行前的最后一刻秘密篡改了团队的指令。如果一队无人机计划绕圈飞行，间谍可能会对其中一架无人机耳语：“实际上，直接撞墙吧，”于是那架无人机就真的去了，导致了坠毁。可怕之处在于，其他团队成员并不知道间谍的存在，也看不见改变计划的那个秘密耳语。他们只看到了最终的结果：一场坠毁。

这篇论文探讨了一个棘手的问题：当团队不知道间谍是谁，甚至不知道间谍在做什么时，如何学习协同工作以确保安全。这就像是在尝试学习一段舞蹈动作，而有人一直在偷偷改变你的舞伴的动作。研究人员想知道：团队是否可以学习一种即使在间谍竭尽全力破坏一切的最坏情况下，依然能有效运作的策略？他们正在寻找一种“安全保证”——即无论间谍如何破坏计划，团队都能表现得还不错。这篇论文不仅仅是在猜测；它利用深奥的数学来证明什么是可能的，什么是不可行的，从而展示了当你看不见敌人的手时，学习的极限在哪里。

机器中的间谍

故事始于一群试图学习协作游戏的代理。他们有一个计划，但有一个陷阱：一群隐藏的“拜占庭”代理（即间谍）可以看到团队的计划，并在计划发生前秘密覆盖掉他们自己的部分。想象一群朋友在策划一场劫案。他们商定了一条路线。但其中一个朋友其实是间谍，他看到了路线，并决定改变自己的行动来破坏整个团队。其余的成员只看到了他们以为制定的计划和最终的结果（是拿到了宝藏还是没拿到？），但他们永远看不到间谍的秘密修改，也看不到间谍实际采取的行动。

研究人员问道：团队能否学会保持安全？他们将“安全性”定义为：尽可能做得比间谍能做出的最坏情况都要好。如果团队学习到的策略能够保证即便在间谍拼尽全力破坏的情况下也能获得高分，那就是胜利。

间谍的秘密力量

论文发现了一个关于间谍力量的迷人现象：这完全取决于间谍知道什么。

如果间谍能在计划被更改之前看到团队的计划（就像间谍在团队出发前读了地图一样），这个问题就变成了一种特定的数学谜题，叫做 (s, a)-矩形鲁棒 MDP。用通俗的话说，这意味着间谍可以为团队制定的每一个特定计划挑选最坏的结果。这就像一场游戏，对于你做的每一个动作，间谍都可以针对该动作挑选一个最坏的应对动作。

然而，如果间谍是“盲目”的，必须在没看到计划的情况下进行猜测（就像一个间谍必须在团队写下计划之前就大声喊出改变方案），那么数学模型就会发生变化。问题变成了 s-矩形模型。在这种情况下，间谍必须选择一个能同时对抗所有可能计划的策略，这对团队来说其实更容易处理，因为间谍无法针对每一个具体的计划来量身定制破坏行为。

不可避免的盲点

这里是最令人惊讶的部分。研究人员证明，仅仅通过观察结果，对于团队所能学到的东西存在一个根本性的限制。

想象两个不同的世界。在世界 A 中，间谍很差劲，团队表现出色。在世界 B 中，间谍是个天才，团队表现糟糕。研究人员证明，可以设置这两个世界，使得团队看到的结果完全相同。他们看到的计划、奖励和结果都是一样的。因为数据看起来是一模一样的，团队无法分辨自己处于哪个世界。

这引出了一个残酷的事实：你无法仅仅通过观察结果来判断间谍到底有多“坏”。 团队可能会想：“嘿，我们表现得很好，所以间谍一定很弱！”但实际上，他们可能只是运气好，间谍那天没有选择那个最坏的动作。论文将“实际发生了什么”与“可能发生的坏事”之间的差距称为响应差距（response gap）。

作者证明了这种差距是不可避免的。无论学习算法多么聪明，只要间谍被允许是不可预测的，团队就永远无法 100% 确定自己是安全的。他们只能确定自己是针对间谍的实际动作表现良好，而不一定是针对间谍的最坏可能动作表现良好。

新的学习策略

那么，如果我们无法完美地识别间谍，该如何学习呢？论文介绍了一种新的学习方法，称为阶段绑定鲁棒估计决策学习器（stage-tied robust estimation-to-decisions learner）。

这就像是一个不试图直接抓捕间谍的侦探。相反，侦探为游戏的每个阶段都建立了一个“安全网”。

1. 安全网： 学习者并不试图猜测间谍的身份或其秘密行动，而是建立一个包含所有可能“坏结果”的模型。
2. 阶段绑定的技巧： 通常，学习算法必须分别检查每一个状态和动作，这就像是一个一个检查巨大地板上的每一块瓷砖一样。这既慢又不高效。新方法通过“阶段”（或时间步）对这些检查进行分组。这就像是通过沿着行走来检查整个地板，而不是逐一检查每块瓷砖。这使得学习过程更快、更高效。
3. 结果： 团队学习到了一种保证表现良好的策略。论文证明，随着游戏的进行，团队的“遗憾值”（即他们表现得比完美安全策略差多少）增长得非常缓慢。具体来说，误差以与游戏次数平方根相关的速率增长，这在学习算法领域是一个非常好的结果。

总结

这篇论文不仅仅是在说：“这是一个很酷的新算法。”它划定了一条清晰的界限。它证明了虽然我们可以学习如何对隐藏的叛徒保持鲁棒性，但我们永远无法完全消除“间谍在某一天表现得有多坏”这种不确定性。“响应差距”是这场游戏的一个永久特征。

然而，论文也给了我们希望。通过使用这种新的“阶段绑定”方法，我们可以学习到在不知道间谍是谁或他们在做什么的情况下，依然能证明是安全且高效的策略。这是构建能够抵御背叛的团队的蓝图，确保即使间谍试图破坏计划，团队仍能取得成功。数学是严密的，证明是严谨的，结论也是明确的：我们可以学习如何获得安全，但我们必须接受我们永远无法完全看透间谍的手。