并发随机博弈的鲁棒 PAC 学习

Robust PAC Learning of Concurrent Stochastic Games

arXiv: 2609.04189v1

论文信息

标题: Robust PAC Learning of Concurrent Stochastic Games

作者: Angel Y. He, David Parker

发布日期: 2026-09-03

arXiv ID: 2609.04189v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：在未知转移概率的两人一般和并发随机博弈中，如何用有限环境交互 PAC 地学到一个近似最优纳什均衡，并在游戏根本不存在精确静态纳什均衡时给出可靠提示。
  • 核心方法：用 L1L^1 置信集合刻画转移不确定性，在每轮构造并求解鲁棒并发随机博弈；同时用一个辅助鲁棒 MDP 指导联合状态-动作探索，保证覆盖率。
  • 关键结果：在最小可达性假设下，算法以高概率在 O~(Rmax⁡2H4∣S∣2∣A∣ε2preach)\widetilde{\mathcal{O}}\left(\frac{R_{\max}^2 H^4 |S|^2 |A|}{\varepsilon^2 p_{\mathrm{reach}}}\right) 条轨迹样本内终止，并输出 ε\varepsilon-NE 或非存在证书。
  • 主要局限：依赖集中式探索、已知转移支撑和可达性假设；非存在证书并不完整，即某些没有精确 NE 的游戏可能仍返回 ε\varepsilon-NE。
  • 适合读者：多智能体强化学习、形式化验证、鲁棒决策与控制方向的研究者，尤其是关心均衡存在性和样本复杂度的人。

论文背景和研究动机

并发随机博弈（CSG）是多智能体随机决策的经典模型：多个玩家在每一状态同时选择动作，彼此不能观察对方的选择。与回合制博弈不同，并发性让均衡存在性问题变得更困难。对于任何 ε>0\varepsilon>0，有限 CSG 总存在 ε\varepsilon-NE，但精确的静态纳什均衡可能不存在；Bouyer 等人的工作已经给出不存在任何静态 NE 的并发终端收益游戏例子。

另一方面，许多已有方法假设转移核已知。鲁棒规划通常给定不确定性集合，PAC 学习虽然能处理未知动力学，但大多只做单智能体或回合制博弈。本文关注的是一个尚未被充分覆盖的交叉问题：在转移核未知的 general-sum 并发博弈中，如何同时做到高置信近似均衡学习、社会福利接近最优，以及有原则地处理 “精确 NE 不存在” 这一情况。

这个问题的实际意义在于，多智能体系统的均衡常常被视为稳定运行点。如果真实游戏没有静态均衡，却仍然强行部署一个名义上的均衡策略，系统可能表现为不稳定或不可预测。作者由此提出 PAC-CSG 框架，要求输出要么是 ε\varepsilon-近似 NE，要么是 “无精确 NE” 的可靠证书。

核心方法和技术细节

算法按轮次运行。每轮开始时，根据历史轨迹数据为每个状态-动作对的转移核构造 L1L^1 置信球，并组合成矩形不确定性集合 Pt\mathcal{P}_t。置信半径来自 Weissman 不等式，并采用可求和失败概率安排，保证在联合事件 Econt\mathcal{E}^{\text{cont}} 上，真实转移核 P⋆P^\star 始终位于 Pt\mathcal{P}_t 内（见论文附录 B 的 Corollary 10）。

随后算法构造经验鲁棒 CSG，并调用 RCSG 求解器寻找 ε\varepsilon-鲁棒社会福祉最优纳什均衡。为了把经验模型中的鲁棒均衡迁移到真实游戏，论文定义了一个敏感度量

Δt=12Rmax⁡H2max⁡(s,a)∈Xnt∥Psa⋆−P^sa∥1.\Delta_t=\frac12 R_{\max}H^2 \max_{(s,a)\in\mathcal{X}_{\mathrm{nt}}} \|P_{sa}^\star-\hat{P}_{sa}\|_1.

引理 2 表明，对任意 P∈PtP\in\mathcal{P}_t 和任意策略，单个玩家价值相对经验模型的偏差不超过 Δt\Delta_t。因此，当 Δt≤ε/4\Delta_t\le\varepsilon/4 时，经验鲁棒均衡就足以转移到真实游戏（见论文第 4.1 节）。

为处理均衡存在性，论文引入 Nash margin：对策略 σ\sigma 和转移核 PP，定义

μ(σ,P)=min⁡i∈Nmin⁡s∈Sinf⁡σi′[ui(σ,P∣s)−ui(σ−i[σi′],P∣s)].\mu(\sigma,P)=\min_{i\in N}\min_{s\in S}\inf_{\sigma_i'}\left[u_i(\sigma,P\mid s)-u_i(\sigma_{-i}[\sigma_i'],P\mid s)\right].

μ(σ,P)≥0\mu(\sigma,P)\ge0 当且仅当 σ\sigma 是 NE。若在当前不确定性集合内没有 ε\varepsilon-鲁棒 NE，求解器返回 NOT_FOUND；命题 4 说明，这不是简单失败，而意味着真实游戏的最优 Nash margin 小于 4Δt−ε4\Delta_t-\varepsilon。当 Δt\Delta_t 足够小时，NOT_FOUND 就能构成可靠的 “无精确 NE” 证书。

探索方面，由于并发博弈中没有单个玩家可以控制联合状态-动作访问，论文构造了一个辅助探索 RMDP。每个未知状态-动作对会被替换为到吸收态 zz 的确定性转移，并给予奖励 1；已知状态-动作对则沿用当前置信集合。求解该 RMDP 等价于最大化最坏情况下到达未知状态-动作对的概率。在最小可达性条件

preach=min⁡(s,a)∈Xntmax⁡σinf⁡P∈PSuppPσ,P[到达 (s,a) 再进入 ST]>0p_{\mathrm{reach}}=\min_{(s,a)\in\mathcal{X}_{\mathrm{nt}}}\max_{\sigma}\inf_{P\in\mathcal{P}_{\mathrm{Supp}}}\mathbb{P}^{\sigma,P}[\text{到达 }(s,a)\text{ 再进入 }S_T]>0

下，每一轮探索成功访问某个未知状态-动作对的概率至少为 preachp_{\mathrm{reach}}（引理 6）。作者用 Freedman 鞅不等式处理轮间依赖事件，得到总轮数和样本复杂度上界。

创新点和贡献

本文的第一个贡献是提出了一般和并发随机博弈中首个 PAC 学习框架 PAC-CSG。它同时考虑转移不确定性、鲁棒均衡和社会福祉最优性，并能输出非存在证据。

第二个贡献是 Nash margin 的引入。该量把 “是否存在 NE” 从离散判断转化为可分析的数值边界，使求解器失败可以被解释为对 non-existence 的统计证据，而不是简单的算法失败。命题 8 明确联系了全局 Nash margin 和最优 NE 的存在性。

第三个贡献是鲁棒 RMDP 探索机制。由于并发博弈中联合动作覆盖率无法由单个玩家直接控制，作者把覆盖问题重新表述为鲁棒到达性规划，并用悲观目标保证对真实转移核具有下界。这一设计是样本复杂度保证的关键。

此外，论文覆盖有限时域和无限时域的多种目标，包括概率到达、累积收益、无限时域到达奖励等，这比常见折扣奖励更接近验证与规划场景。定理 7 给出高概率终止的

O~(Rmax⁡2H4∣S∣2∣A∣ε2preach)\widetilde{\mathcal{O}}\left(\frac{R_{\max}^2 H^4 |S|^2 |A|}{\varepsilon^2 p_{\mathrm{reach}}}\right)

轨迹样本上界。

实验结果分析

实验在 PRISM-games 中实现，使用六个小型基准 CSG。作者设置了三个研究问题：正确性、探索策略对比和样本复杂度扩展。

在 RQ1 的正确性实验中，对存在精确 NE 的示例，学习策略在真实游戏中达到与 oracle 相同的价值；鲁棒值估计差距 V⋆−V^V^\star-\hat{V} 在表 1 的有限值案例中保持在 10−310^{-3} 量级，例如 Mixed NE 为 3.083×10−33.083\times10^{-3}。这说明终止条件 Δt≤ε/4\Delta_t\le\varepsilon/4 在这些实例上能保持近似最优性。

在均衡非存在检测上，Cyclic Preferences 在 10 次运行中均返回 NOT_FOUND，符合该基准没有静态 NE 的性质。Hide-or-Run 则展示出不完整性：它没有静态最优 profile，但算法仍返回趋近极限均衡的 ε\varepsilon-NE，而非非存在证书。论文明确将这一现象解释为分支 2 是 sound 但不 complete。

在 RQ2 中，鲁棒探索在表 2 的多数基准上消耗样本最少。尤其是在 Delayed Coordination 上，鲁棒探索约 42.95 百万条轨迹，均匀随机为约 730.09 百万条；同时乐观探索的值估计偏差为 0.060，而鲁棒探索为 0.000。在该实验设置下，鲁棒目标比乐观目标给出更稳定估计。

RQ3 的 log-log 拟合显示：状态指数 1.44，动作指数 0.89，时域指数 3.94，精度倒数指数 2.11，与定理 7 的 ∣S∣2∣A∣H4/ε2|S|^2|A|H^4/\varepsilon^2 上界一致。论文没有据此宣称紧的渐近速率，只说明在所测实例上变化趋势与理论一致。

实践建议

对于需要构建多智能体决策系统的团队，本文给出几条可操作建议。

第一，部署前不应只使用点估计转移模型。作者在实验设置下显示，用 L1L^1 置信集合做鲁棒均衡求解，可以缓解小估计误差带来的均衡破坏。实际问题中，若转移概率来自日志或仿真，建议保留置信区间并在鲁棒策略上做评估。

第二，可以把 Nash margin 作为系统稳定性指标。若计算得到的最优 margin 接近 0 或为负，说明当前模型缺乏良好的静态均衡，此时继续按 “均衡策略” 部署可能不稳定。应触发额外探索，或启用带回退规则的在线机制。

第三，多智能体探索中若只有共享历史而无法直接控制所有智能体，可借鉴论文的辅助 RMDP 思路：把状态-动作覆盖抽象为到达某个 “未知区域” 的鲁棒到达性问题，并用悲观目标替代乐观目标。至少在本文评测的 Delayed Coordination 中，鲁棒目标给出的估计更稳定（表 2）。

第四，系统应显式支持 NOT_FOUND 分支。如果均衡存在性无法保证，不应强行返回一个名义均衡。论文的框架提供了 sound 的证据：当求解器返回 NOT_FOUND 且 Δt\Delta_t 足够小时，可以判定无精确静态 NE；但如果系统允许 ε\varepsilon-NE 作为可接受运行点，也可以像 Hide-or-Run 那样返回近似策略，但要明确这是近似稳定，而不是精确均衡。