🤖 machine learning

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

本文通过提出能够在各种信息结构下使去中心化玩家独立就联合动作离散化达成一致的算法，解决了连续动作空间且利普希茨常数未知的协作式多智能体多臂老虎机问题，从而在无需后学习通信的情况下实现了最优遗憾保证。

原作者： Ricardo Parada, Chenzhang Zhao, William Chang

发布于 2026-08-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Ricardo Parada, Chenzhang Zhao, William Chang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，一群朋友正试图在一个巨大的、大雾弥漫的公园里寻找一个最好的地点来举行野餐。一旦游戏开始，他们就不能互相交谈了，而且他们也没有地图。他们只知道一个地点的“好坏”程度是平滑变化的：如果你只是向旁边迈出一小步，下一个地点可能依然和现在一样好；但如果你走得太远，那里可能会变得糟糕透顶。这种平滑性是数学家们称之为“利普希茨连续性”（Lipschitz continuity）的概念。同时，他们还在玩一种叫做“多臂土匪”（Multi-Armed Bandits）的游戏，这是一个专门描述必须在“尝试新事物（探索）以了解公园情况”与“坚持目前认为最好的选择（利用）以获得最多食物”之间进行平衡的术语。棘手之处在于，他们并不知道这个公园到底有多“平滑”。是一个小步长代表微小的变化，还是代表巨大的变化？如果不了解这个“平滑度常数”，他们就无法决定检查地面的频率。如果检查得太稀疏，他们会错过最好的地点；如果检查得太密集，他们又会浪费时间。这篇论文探讨了这样一个混乱的场景：多名试图在没有交谈的情况下，在不了解地形规则的情况下，协同寻找最佳位置的智能体（就像我们的这些朋友）。

研究人员 Ricardo Parada、Chenzhang Zhao 和 William Chang 致力于解决一个特定的谜题：当一群智能体（如我们的朋友）试图在一个连续且平滑的世界中寻找最佳行动，且他们不知道这个世界的“平滑度”，也无法在游戏开始后进行交谈时，该如何进行协作？他们探索了三种不同的信息共享方式（或缺乏共享的方式）。在第一种情景中，每个人看到的奖励都是一样的（就像每个人都品尝了同一个野餐篮里的食物），但他们看不见其他人站在哪里。在第二种情景中，每个人都能看到其他人的位置，但只能品尝到自己的食物。在第三种，也是最难的情景中，他们既看不见彼此的行为，也只能品尝到自己的食物。

团队设计了一种聪明的策略，称为“mECAB”。它通过一个两阶段的游戏来运作。首先，朋友们进行“粗略探索”。他们事先商定好一个大致的网格点进行检查。他们采样这些点来估算“平滑度常数”（即奖励变化的快慢）。基于这个估算值，他们决定搜索网格的精细程度。然后，他们转向“利用”阶段，使用一种标准算法在这一新确定的网格上寻找最佳位置。这篇论文的魔力在于，他们如何确保在不交谈的情况下，所有人都能对网格大小达成一致。

在第一种情景（共同奖励）中，这种一致性是自然达成的。因为每个人尝到的食物是一样的，所以他们的数据是完全相同的，因此他们会计算出相同的平滑度估算值，并选择相同的网格。这就像如果每个人在野餐时都尝到了同样的汤，他们无需一言不发，就能对是否需要加盐达成共识。

在第二种情景（可观测行为，独立奖励）中，朋友们虽然尝不到彼此的食物，但能看到每个人站的位置。作者发现了一个巧妙的变通方法：玩家可以通过在特定位置的最后一次移动来向他人“传递”其数据。通过稍微调整位置，使其编码一个数字，他们可以广播自己的发现。这使得小组能够汇总数据，使他们对平滑度的估算比独自工作时要精准、准确得多。

第三种情景（不可观测行为，独立奖励）是最棘手的。没有人能看到其他人的位置，也没有人分享食物。如果每个人仅根据自己有限的数据来猜测平滑度，他们可能会得出略有不同的数字。一位朋友可能会决定每隔一英寸检查一次，而另一位可能每隔一英尺检查一次，这样他们永远无法在同一个位置汇合。为了解决这个问题，作者引入了“抖动量化”（dithered quantization）技巧。在游戏开始前，朋友们事先商定一个共享的随机数（比如一起掷一个秘密骰子）。当他们计算平滑度估算值时，会在将其四舍五入为整数之前，先加上这个随机数。这种随机的“抖动”确保了即使他们的原始猜测略有不同，最终用于行动的四舍五入后的数字几乎总是相同的。这就像是大家约定将身高精确到英寸，但先在每个人的身高上加上一个随机的小数，这样即使初始测量值略有差异，大家最后也会舍入到同一个数值。

论文从数学上证明，在所有这三种情况下，团队都能实现一个“遗憾值”（Regret，衡量如果一开始就知道答案，原本可以做得多好的指标），该值随着游戏的进行增长得非常缓慢。模拟实验证实，这种自适应方法（先猜测平滑度，然后再细化网格）优于预先固定网格大小的静态方法。如果公园非常崎岖（具有高平滑度常数），固定的网格可能过于粗糙，导致团队错过最佳位置。然而，自适应方法会根据地形调整其网格，从而确保无论公园是平滑还是崎岖，都能高效地找到最佳位置。作者展示了，即使在信息最匮乏的最难情景下，协调的成本也非常小，以至于不会影响他们的长期整体表现。

技术摘要：协调多智能体老虎机中未知的 Lipschitz 常数

问题陈述
本文探讨了在连续动作空间中，当平均奖励函数是 Lipschitz 连续但其 Lipschitz 常数 $L$ 未知时，协作式多智能体多臂老虎机（MAB）所面临的挑战。在去中心化场景（例如无线信道接入、分布式传感）中，多个智能体必须在无需显式通信的情况下进行协调，以最大化累积奖励。

核心难点在于需要将连续的联合动作空间离散化，以便应用标准的离散老虎机算法。这种离散化的最优分辨率取决于 $L$ 。由于智能体在学习过程中无法进行通信，它们必须根据各自的观测结果独立估计 $L$ 。如果这些估计值出现分歧，智能体会构建出不同的网格，从而破坏协作协调所需的共同离散问题假设。本文研究了关于智能体可观测内容的三种特定信息结构：

问题 A： 观测不到动作，共同奖励。
问题 B： 观测得到动作，独立奖励。
问题 C： 观测不到动作，独立奖励。

方法论
作者提出了一种元算法 mECAB，该算法分为两个阶段运行：

探索阶段： 智能体在每个维度上均匀地探索包含 $m$ 个箱体（bins）的粗糙网格。它们基于相邻箱体之间经验平均奖励的差异，来估计 $L$ 的置信上界（记作 $\hat{L}$ ）。
利用阶段： 利用估计出的 $\hat{L}$ ，智能体确定一个更精细的离散化水平（ $\hat{m}$ ），并在由此产生的有限联合动作集上运行标准的协作式多智能体 MAB 子程序（例如 m-UCB）。

其核心创新在于用于确保所有智能体都能得出相同的 $\hat{L}$ 并进而获得相同网格的一致性机制（agreement mechanism），尽管它们的信息结构不同：

在问题 A 中： 由于奖励是共同的且探索方案是预先约定的，所有智能体都会观测到每个箱体完全相同的经验均值。因此，它们能自然地计算出完全相同的 $\hat{L}$ ，无需额外的协调。
在问题 B 中： 虽然奖励是独立的，但动作是可观测的。智能体利用每个箱体的最后一个样本向其他智能体“发送信号”，传达其经验均值。这使得智能体能够汇聚数据，从而有效地将每个箱体的样本量扩大为 $M$ 倍（ $M$ 为玩家数量），进而获得更精确的 $L$ 估计。
在问题 C 中： 这是最困难的情况，因为既没有共享奖励，也没有共享动作。为了防止估计分歧，作者引入了抖动量化（dithered quantization）。智能体预先约定一个共享随机变量（抖动项） $U \sim \text{Unif}[0, 1)$ 。它们通过将原始估计值 $X_i + U$ 四舍五入到最近的整数来进行量化。这种随机化确保了两个智能体在量化值上产生分歧的概率与真实的实例 $L$ 无关，从而使分歧概率可以被界定和控制。

关键结果与遗憾界限（Regret Bounds）
论文为所有三种信息结构提供了遗憾保证。设 $T$ 为时间跨度， $d$ 为动作空间的维度， $M$ 为玩家数量。联合动作空间的维度为 $Md$。

问题 A（共同奖励）： 遗憾度规模为 $O(T^{(Md+1)/(Md+2)})$ 。共同奖励结构强制了相同的箱体均值，确保了完美的网格对齐。动作的不对称性除了维度缩放带来的成本外，不会产生额外代价。
问题 B（观测得到动作）： 遗憾度同样规模为 $O(T^{(Md+1)/(Md+2)})$ 。通过动作进行信号传递的能力允许数据汇聚，这改善了 Lipschitz 估计的收敛性（将样本量 $E$ 替换为 $ME$），使得相比于问题 A，其误差界限中的常数项更紧凑。
问题 C（无共享信息）： 遗憾界限包含一个与网格分歧概率相关的附加项。然而，通过设置足够大的探索预算，该项与主导项处于同一数量级。具体而言，抖动量化确保了协调的“成本”不会出现在遗憾度的领先阶项中，使得其性能在常数项意义上与问题 A 和 B 匹配。

意义与主张
本文声称是首个解决多智能体环境下具有未知 Lipschitz 常数的 Lipschitz 老虎机问题的研究。其主要贡献在于证明了在严苛的信息约束下，协调（即对离散化网格的一致性）是可以实现的：

免费达成一致： 在存在共同奖励（问题 A）或可观测动作（问题 B）的情况下，实现共享网格所需的必要一致性是通过“免费”方式或高效的信号传递实现的。
最坏情况下的无成本协调： 即使在两者皆不存在的情况下（问题 C），作者展示了通过抖动量化可以“购买”一致性，且对遗憾度的领先阶项没有成本影响。这解决了去中心化估计与对共享离散结构的需求之间的根本矛盾。

这项工作将单智能体 Lipschitz 老虎机文献（特别是来自文献 [8] 的估计器）扩展到了多智能体领域，强调了约束条件从估计精度转向了离散化策略的同步。仿真证实，自适应离散化（Est-L）优于非自适应方法（No-L），尤其是在真实的 Lipschitz 常数较大时，并且信息结构会显著影响遗憾度的方差和收敛性。

技术摘要：协调多智能体老虎机中未知的 Lipschitz 常数

类似论文