💻 computer science

Distributionally Robust Markov Games with Average Reward

本文在平均奖励准则下，针对不可约及弱通信设置下的分布鲁棒马尔可夫博弈，建立了平稳纳什均衡的理论存在性，并提出了收敛算法及其通过折扣对应物进行的近似演示。

原作者： Zachary Roch, Yue Wang

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Zachary Roch, Yue Wang

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

想象一群朋友正试图一起通过一个迷宫。在理想世界中，他们确切地知道每一面墙在哪里，以及每一扇门通向何处。但在现实世界中，他们手中的地图可能略有偏差。也许是一面墙移动了，或者一扇门卡住了。这就是**模型失配（model mismatch）**的问题：他们制定的计划与他们实际身处的现实并不相符。

这篇论文介绍了一种新的决策方式，即使在地图错误且需要进行长时间（而不只是短距离冲刺）游戏的情况下，这种方式依然有效。

以下是使用简单类比对他们解决方案的拆解：

1. 问题所在：“如果地图错了怎么办？”

通常，当人们教计算机玩游戏或做决策时（比如仓库里的机器人或高速公路上的汽车），他们假设规则是固定的。但现实情况是事物会发生变化。

旧方法： 大多数以往的方法侧重于短期目标（比如“在10步之内到达出口”）或使用“折扣”（认为今天的奖励比明天的更值钱）。这就像短跑运动员进行短距离比赛；他们并不关心鞋子的长期磨损。
新挑战： 作者想要解决的是**平均奖励（Average Reward）*问题。这就像马拉松选手，需要保持稳定、可持续的节奏。他们关心的是整个比赛过程中的平均*速度，而不仅仅是第一英里。
转折点： 他们还希望具有分布鲁棒性（Distributionally Robust）。这意味着玩家假设地图处于“最坏情况”。他们不只是希望地图是正确的；他们按照一个试图不断改变墙壁位置以让生活变得尽可能艰难的“恶作剧小精灵”来制定计划。

2. 重大障碍：“迷宫太复杂了”

作者解释说，将“长期平均目标”与“最坏情况规划”结合起来是非常困难的。

类比： 想象你在寻找一条迷宫中的最佳路径，每当你走一步，墙壁就会移动一次，而且你必须永远走下去。在更简单的游戏中（短距离比赛），你可以从终点线向后推导。但在一场无止境的马拉松中，没有终点线可以让你向后推导。
发现： 他们证明了如果没有某些规则（例如迷宫是“连通的”，即你可以从任何房间到达任何其他房间），那么完美的、稳定的策略甚至可能不存在。这就像是在一个规则变化如此剧烈以至于没有任何动作是真正安全的比赛中，试图寻找一条“最佳路径”。

3. 解决方案：寻找“稳定的协议”

论文证明，如果环境是“高度连通”的（你最终可以到达任何地方），那么就确实存在一个纳什均衡（Nash Equilibrium）。

什么是纳什均衡？ 想想它是一个“稳定的停战协议”。这是一套策略，在这种策略下，假设其他人都坚持自己的计划，单个玩家无法通过改变自己的计划来提高自己的平均得分。即使面对最坏情况下的地图变化，大家也会就一个策略达成共识，即在混乱中能达到的最佳方案。
突破点： 作者展示了如何从数学上证明这种协议的存在，即使“小精灵”试图破坏游戏。他们通过创建一个特殊的方程（“贝尔曼方程”），平衡了即时奖励与长期平均值，并考虑了最坏情况下的地图变化。

4. 工具：两种新算法

为了实际找到这个“稳定的停战协议”，作者构建了两个新工具（算法）：

工具 A：鲁棒纳什迭代（Robust Nash-Iteration，即“迭代式谈判”）
- 运作方式： 想象玩家们围坐在桌旁。他们轮流说：“如果你们都坚持目前的计划，这是对我最好的选择。”他们根据他人的做法不断更新自己的计划。
- 代价： 这种方法虽然完美，但在每一步都需要一台“超级计算机”来解决一个复杂的数学难题。这就像每走一步都需要一位天才数学家去解一个数独谜题。
工具 B：鲁棒 TD 下降（Robust TD Descent，即“平滑攀爬”）
- 运作方式： 这是一种更聪明、更实用的方法。与其每次都解决难题，不如让玩家沿着“幸福之丘”向下走小步。他们测量当前计划有多“错”（误差），并轻轻调整策略以减少这种误差。
- 技巧： 由于数学逻辑是锯齿状且凹凸不平的（由于最坏情况的规划），他们先将“山丘”进行了“平滑处理”，就像打磨一块粗糙的木头一样。这使得他们能够顺着坡度滑向最佳解，而不会被突起卡住。这种方法更快，且不需要超级计算机。

5. 桥梁：连接短期与长期

最后，作者展示了一个聪明的捷径。

类比： 他们证明了，如果你在玩游戏时使用“折扣”（即稍微更看重现在而非未来），但让这个折扣因子极其接近 1（意味着你对未来的重视程度几乎等同于对现在的重视程度），你得到的结果几乎与完美的长期平均计划一致。
为什么重要： 这意味着我们可以利用现有的、设计用于短期游戏的成熟工具，来近似解决这些复杂的、长期的、最坏情况下的场景。这就像如果你稍微调整一下指针，就可以使用标准的指南针来导航马拉松。

总结

简而言之，这篇论文为群体智能体（如机器人或 AI）提供了一个数学保证和一个实用的工具包，使它们能够在不知道确切规则且预期环境会试图欺骗它们的情况下，实现长期有效的协作或竞争。他们证明了稳定解的存在，并提供了两种寻找它的方法：一种精确但沉重，另一种实用且平滑。

技术摘要：平均奖励分布鲁棒马尔可夫博弈

问题表述

本文研究了在具有模型不确定性和长运营周期环境下的多智能体决策挑战。虽然马尔可夫博弈（Markov Games, MGs）为竞争性多智能体系统提供了框架，但标准表述往往无法应对“仿真到现实”（Sim-to-Real）的差距，即由于非平稳性、建模误差或对抗性扰动，假设的转移模型与真实环境发生偏离。

为了缓解这一问题，作者研究了分布鲁棒马尔可夫博弈（DR-MGs），其中智能体针对预定义的转移核不确定集优化其最差情况下的表现。至关重要的是，这项工作关注的是平均奖励准则，而非更常见的有限时界或折扣奖励设置。平均奖励准则对于在无限长时间内运行的系统（如仓库机器人、通信网络）至关重要，但也带来了显著的理论障碍：

最小-最大对偶性的失效： 在鲁棒设置中，一个智能体的最差情况转移核可能与另一个智能体的不同，即使在零和博弈中也会破坏鞍点结构。
结构复杂性： 与折扣设置不同，在平均奖励设置中，如果没有严格的结构假设，平稳策略与状态-动作频率之间的对应关系会发生断裂。
缺乏现有解决方案： 现有的针对折扣 DR-MGs 或非鲁棒平均奖励 MGs 的方法无法直接扩展到鲁棒平均奖励设置，因为这涉及到 Bellman 算子的非收缩性以及解的不唯一性问题。

本文证明，如果没有结构性假设，平均奖励 DR-MG 可能不存在平稳纳什均衡（NE），作者通过构建一个双人零和博弈的反例展示了这一点。

方法论

1. 理论基础：均衡的存在性

作者在两种不同的结构假设下，确立了平稳鲁棒纳什均衡的存在性：

不可约设置（Irreducible Setting）： 假设对于任何平稳联合策略和任何容许的核，诱导的马尔可夫链是不可约的（所有状态属于单个循环类）。
- 作者推导了最优策略与鲁棒 Bellman 方程解之间的对应关系。
- 他们证明了鲁棒 Bellman 方程在增益（gain）和偏差（bias）方面存在唯一解（除常数向量外）。
- 利用这些结果，他们证明了最优响应映射是非空、凸且上半连续的。通过应用 Kakutani 不动点定理，他们证明了平稳鲁棒 NE 的存在性。
弱通信设置（Weakly Communicating Setting）： 一个更广泛的设置，其中状态空间可以分解为瞬态状态和若干循环类的并集。
- 在此设置中，策略与 Bellman 解之间的直接对应关系失效。
- 作者基于常数增益最优鲁棒 Bellman 算子构建了一个代理集合值映射（proxy set-valued map）。
- 他们证明该代理映射是真实最优响应映射的一个子集，并满足 Kakutani 不动点定理的条件，从而在该更广泛的语境下确立了平稳鲁棒 NE 的存在性。

2. 算法解决方案

论文提出了两种计算鲁棒 NE 的算法：

鲁棒纳什迭代（Robust Nash-Iteration）： 标准纳什值迭代的扩展。它维护偏差估计，并在每一步求解由鲁棒 Q 值定义的阶段博弈的纳什均衡。
- 收敛性： 在不可约假设以及关于阶段博弈均衡选择（例如全局最优性或鞍点选择）的附加假设下，证明其收敛至鲁部件鲁棒 NE。
- 局限性： 需要一个能够计算阶段博弈 NE 的预言机（oracle），而在一般博弈设置中，这属于 PPAD 完全问题。
鲁棒 TD 下降法（Robust TD Descent）： 一种双时间尺度（two-time-scale）演员-评论家（actor-critic）算法，旨在绕过对 NE 预言机的需求。
- 机制： 它通过最小化**全局鲁棒时序差分（TD）间隙（gap）**来刻画鲁棒 NE。该算法使用 Moreau 包络对该间隙进行平滑处理，以处理非光滑性。
- 收敛性： 证明该算法弱收敛于平滑目标的驻点。虽然在没有进一步假设（如局部梯度支配）的情况下，它不能保证收敛到精确的 NE，但它提供了第一个无需依赖 NE 预言机的、具有可证明收敛性的平均奖励 DR-MG 方法。

3. 与折扣均衡的联系

作者建立了平均奖励与折扣 DR-MG 之间的理论桥梁。他们证明，当折扣因子 $\gamma \to 1$ 时，折扣博弈的鲁棒 NE 会收敛到平均奖励博弈的鲁棒 NE。这使得利用更易处理的折扣 formulations 来近似具有挑战性的平均奖励问题成为可能。

关键结果

NE 的存在性： 论文证明了在不可约和弱通信假设下，平均奖励 DR-MG 存在平稳鲁棒纳什均衡，解决了先前文献中留下的基本可解性问题。
鲁棒 Bellman 方程的可解性： 作者提供了关于平均奖励 MDP 鲁棒 Bellman 方程的可解性和唯一性（除常数外）的基础性结果，修正了以往文献中的空白。
收敛算法： 引入了两种算法。鲁棒纳什迭代在特定结构假设下提供收敛性，而鲁棒 TD 下降法提供了一种实用的、无预言机的、具有驻点收敛保证的方法。
通过折扣进行近似： 论文验证了通过具有足够大折扣因子的折扣均衡可以有效地近似平均奖励均衡，从而提供了一条实用的计算路径。

意义与主张

本文声称为复杂、不确定且长期运行的多玩家环境下的决策提供了全面的理论和算法基础。具体而言：

它解决了在平均奖励多智能体设置中是否存在鲁棒均衡的基本问题，而在该问题中标准技术会失效。
它引入了第一个具有可证明收敛保证的求解平均奖励 DR-MG 的算法，超越了折扣或有限时界近似的限制。
它强调了结构性假设（不可约性或弱通信）对于平稳均衡存在性的必要性，并通过反例证明了这些假设不仅是技术性的，而且是本质性的。

作者指出，虽然其框架提供了坚实的基础，但在一般博弈中寻找精确均衡仍然具有挑战性，且其基于 TD 的算法收敛于驻点，这可以作为寻找精确鲁棒 NE 的必要第一步。未来的工作建议探索局部梯度支配以获得更强的收敛保证，并将框架扩展到 $(s, a)$ -矩形不确定集之外。