🤖 machine learning

Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

本文针对重尾回报以及三种不同的信息不对称机制下的多智能体多臂老虎机问题，提出了鲁棒的去中心化算法，在实现了几乎达到中心化速率的遗憾保证的同时，通过在帕累托分布环境下的实验验证了其性能。

原作者： Daphne Feng, Ricardo Parada, Lily Jiang, Sophia Yi, William Chang

发布于 2026-08-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Daphne Feng, Ricardo Parada, Lily Jiang, Sophia Yi, William Chang

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

想象一下，你是一支探险队的一员，正试图在一片广袤、大雾弥漫的森林中寻找最好的隐藏宝藏。一旦游戏开始，你们就无法互相交谈，也看不见队友在做什么。每当你选择一个地点挖掘，你都会得到一份奖励，但有时这份奖励只是一颗小石子，而有时却是一块巨大的、不可预测的巨石，会将你撞翻。这就是“多臂老虎机”（Multi-Armed Bandits）的世界——一个计算机科学和数学中著名的谜题，其中学习者必须在尝试新事物（探索）与坚持看似不错的事物（利用）之间取得平衡。通常，科学家们假设这些奖励是可预测的，就像掷出一个公平的骰子。但在现实世界中——想想股市崩盘、病毒式传播的网络帖子或突发的网络流量峰值——奖励可能是狂野的、重尾分布的，且充满了极端的惊喜。这个研究课题要解决的核心问题是：当奖励是混乱的，且团队成员无法交谈，甚至可能看不见彼此的行为时，一群聪明的智能体如何能够共同学习并找到最好的宝藏？

来自加州大学洛杉矶分校（UCLA）和加州大学河滨分校（UC Riverside）的研究团队致力于解决这个更接近现实世界、更混乱版本的寻宝问题。他们不仅研究了一种场景，还测试了三种不同程度的“信息不对称”——这是一个表达“你知道多少关于队友的信息”的专业说法。在第一种场景中，每个人都看到同一个宝箱开启（共同奖励），但看不见谁选了哪把锁（未观察到的动作）；在第二种场景中，每个人都能看到谁选了哪把锁，但每个人得到的是各自独立的宝箱（独立奖励）；在第三种，也是最难的一种场景中，没有人能看到关于其他人的任何信息；每个人对团队的行为都是盲目的，并且会得到各自随机的战利品。

该团队发明了三种新的“去中心化算法”——本质上就是代理人如何在不交谈的情况下行为的规则手册。针对前两种场景，他们创建了名为 mRUCB-A 和 mRUCB-Intervals 的方法。这些聪明的策略使用一种“鲁棒”的方法来计算平均值，这种方法会忽略那些疯狂、巨大的离群值（即那些巨石），以免团队产生困惑。他们发现，即使在无法交谈的情况下，只要团队能够看到共享的奖励或者看到彼此的动作，他们就能学得几乎和大家都在同一个房间里一样快。针对第三种情况，mHT-DSEE 算法处理了最困难的情况，即每个人都对彼此完全盲目。在这种情况下，智能体必须遵循一个严格的、预先商定的时间表来轮流进行探索，这种方法可行，但速度稍慢。

当他们在计算机模拟中使用“帕累托分布”（一种模仿那些由少数极端事件主导的狂野、重尾分布奖励的数学模型）进行测试时，他们发现这些理论是站得住脚的。这些算法成功找到了最好的宝藏，证明了即使没有完美的沟通或冷静、可预测的奖励，团队协作依然可以奏效。然而，实验也显示了一个权衡：依赖于观察彼此动作的方法（问题 B）起步较慢，因为它需要更多的数据来确保准确，但一旦掌握了规律，它就会完全停止犯错。完全盲目的方法（问题 C）启动成本较低，但探索的时间比实际需要的稍长。最终，这篇论文表明，即使在一个充满混沌、噪声且队友互为陌生人的世界里，通过聪明的、协调一致的策略，仍然可以引导团队走向最好的结果，尽管由于“不同步”而付出的代价，很大程度上取决于你们所能共享的微小信息量。

技术摘要：具有重尾奖励与信息不对称性的鲁棒多智能体多臂老虎机问题

问题定义
本研究探讨了在去中心化、多智能体环境下，且奖励分布呈现重尾特征的多臂老虎机（MAB）问题。不同于通常假设奖励为亚高斯分布的现有文献，本文考虑的是满足 $(1+\epsilon)$ 阶矩有限（即 $E[|X - \mu|^{1+\epsilon}] \le v$ ）但方差可能无穷大的分布。研究重点在于 $M$ 个玩家如何在没有在线通信的情况下进行协作，以最大化联合奖励。作者定义了三种不同的信息不对称情景：

问题 A（共同奖励，动作不可观测）： 所有玩家观察到针对某一联合动作的相同奖励实现，但无法看到其他玩家选择的具体个体动作。
问题 B（独立奖励，动作可观测）： 玩家可以观察到小组采取的联合动作，但接收到的是独立的、独立同分布（i.i.d.）的奖励样本。
问题 C（独立奖励，动作不可观测）： 玩家既无法观察到其他人的动作，也无法观察到共同奖励；每位玩家仅接收到属于自己的独立样本。

方法论与算法
作者针对每种情景提出了鲁棒的去中心化算法，将鲁棒均值估计器（特别是截断均值）应用于多智能体语境。

问题 A (mRUCB-A)： 由于奖励是共享的，如果所有玩家遵循确定性规则，他们将维持相同的统计估计。该算法采用鲁棒置信上限（RUCB）指数。玩家约定一种字典序排列以保持一致的平局处理。由于估计值保持同步，该问题实际上简化为单个智能体在联合动作空间上的重尾老虎机问题，不会因动作不对称而产生额外成本。
问题 B (mRUCB-Intervals)： 在动作可观测但奖励独立的条件下，玩家的估计值会发生分歧。为了防止协调失误，作者使用轮询消除策略取代了指数最大化。玩家为每个臂维护置信区间。如果一名玩家针对某一臂的区间严格低于另一名玩家，他们通过偏离预定的联合动作（即拉动另一个个体臂）来发出信号。由于动作是可观测的，这种偏差充当了一个 1 比特的隐式通信信道，使得所有玩家能够同时消除次优臂。信号传递阶段会丢弃部分奖励以保持统计对齐。
问题 C (mHT-DSEE)： 在完全不对称的情景下，既没有共享奖励，也无法通过观察动作进行隐式信号传递或同步估计。作者利用了确定性探索与利用调度（DSEE）。玩家遵循预先约定的循环探索计划，持续时间由函数 $w(t)$ （例如 $\lceil \log t \rceil$ ）决定。一旦达到探索预算，玩家将基于仅由探索样本计算出的自身 RUCB 指数切换至利用阶段。由于该调度仅依赖于轮次索引 $t$ ，因此实现了同步。

核心贡献与理论结果
本文推导出的遗憾界限（regret bounds）在各情景下几乎达到了中心化重尾算法的速率：

问题 A： 期望遗憾为 $O(\log T \sum \Delta_a^{-1/\epsilon})$ 。去中心化智能体相对于中心化学习者不会产生额外的成本，因为共享奖励确保了完美的同步。
问题 B： 遗憾界限为 $O(\log T \sum \Delta_a^{-1/\epsilon})$ 加上与 $T$ 无关的常数项。该机制利用动作偏差作为隐式信号信道；信号传递的成本被限制在 $(K^M - 1)\Delta_{\max}$ 以内，该成本不随时间跨度 $T$ 或玩家数量 $M$ 的增加而增长。
问题 C： 遗憾界限为 $O(K^M \log^2 T)$ 。该情景需要一个预先承诺的随时调度（anytime schedule），导致其比其他两个情景多出一个 $\log T$ 的因子。作者指出，这一因子源于缺乏共享信息来协调从探索到利用的切换。

实验验证
实验针对 $M=2$ 名玩家、每名玩家 $K=2$ 个臂以及帕累托分布（形状参数为 2，确保均值有限但方差无穷大）的奖励进行了测试。

结果： 三种算法均表现出亚线性遗憾增长，证实了它们在重尾噪声下识别最优臂的能力。
权衡： 虽然 mRUCB-A 和 mHT-DSEE 的初始遗憾较低，但 mRUCB-Intervals（问题 B）在活跃集合坍缩后最终实现了零遗憾增长，而其他两者仍在继续探索。实验强调，尽管渐近速率不同，但与协调机制相关的常数（例如区间分离度的 4 倍与 2 倍之比）会对中等时间跨度下的性能产生显著影响。

意义与主张
作者声称，即使在存在显著信息不对称和非亚高斯噪声的情况下，有效的去中心化学习也是可以实现的。

共享奖励实现了无成本的同步。
观察到的动作提供了一个足够的隐式信号信道，以补偿失去共享奖励带来的影响，且信号传递成本不随时间跨度或智能体数量而扩展。
完全不对称则必须使用预先承诺的调度，从而引入额外的 $\log T$ 成本，这凸显了即便极少量的可观测性也具有重要价值。

论文总结道，尽管所提出的算法具有鲁棒性，但它们假设已知尾部参数 $(\epsilon, v)$ 。未来的工作建议解决如何适应未知的尾部特征，并为完全不对称情况推导更紧致的下界。

类似论文