Robust PAC Learning of Concurrent Stochastic Games¶

会议: NeurIPS 2026
arXiv: 2609.04189
OpenReview: https://openreview.net/forum?id=A36NpIVJiV
代码: https://github.com/7angel4/prism-games/tree/csg-learning
领域: 学习理论
关键词: 并发随机博弈, PAC学习, 鲁棒MDP, 纳什均衡存在性, 样本复杂度

一句话总结¶

针对转移概率未知的双人一般和并发随机博弈，提出首个具备纳什均衡存在性可靠判定的 PAC 学习框架 PAC-CSG，结合 $L^1$ 置信集与探索性鲁棒 MDP 机制实现 $\widetilde{\mathcal{O}}(R_{\max}^2 H^4 |S|^2 |A| / (p_{\text{reach}} \varepsilon^2))$ 多项式样本复杂度。

研究背景与动机¶

在多智能体随机环境中学习最优协同或博弈策略时，真实物理或交互系统的状态转移核往往是未知的。并发随机博弈（Concurrent Stochastic Games, CSGs）作为多智能体决策的核心数学模型，刻画了各博弈方在无法预先观察对手动作的前提下同时选择动作的交互过程。然而，现有关于并发随机博弈的均衡计算理论绝大多数建立在转移概率精确已知的强假设下；而在统计不确定性存在时，微小的模型估计偏差不仅会导致标称最优策略偏离真实均衡，甚至可能使系统陷入剧烈的非均衡不稳定状态。

将经典单智能体及轮流博弈中的概率近似正确（PAC）学习范式推广至一般和并发随机博弈面临两大根本障碍。其一是均衡存在性与鲁棒性的内在矛盾：与有限状态轮流博弈不同，并发博弈即使在确定模型下也可能不存在精确的稳态纯策略或混合纳什均衡（如著名的 Hide-or-Run 逃逸博弈）；而在模型不确定性下，即便真实博弈存在纳什均衡，覆盖真实核的不确定性集合整体也往往不具备鲁棒纳什均衡。其二是集中探索中的联合覆盖瓶颈：在无生成模型（Generative Model）的在线交互轨迹中，没有任何单一智能体能独立支配联合动作的演化，加之转移核未知，如何高效引导轨迹覆盖所有未充分探索的状态-动作对构成严峻的统计学挑战。

本文打破了鲁棒规划依赖先验不确定性集与 PAC 学习回避博弈均衡非存在性的壁垒，从统计置信集与博弈灵敏度分析切入，提出了定量刻画策略偏离度的纳什边界（Nash Margin）概念。核心 idea：构建基于数据驱动 $L^1$ 置信球的经验鲁棒并发随机博弈，将未充分访问插槽的联合覆盖重构为辅助探索鲁棒 MDP 的最坏情况可达性控制，并借助纳什边界转移引理，在多项式样本复杂度下要么输出 $\varepsilon$-社会福利最优的 $\varepsilon$-纳什均衡，要么给出真实博弈不存在精确纳什均衡的可靠证明。

方法详解¶

整体框架¶

PAC-CSG 算法由集中式学习器协调运行，面向双人有限一般和并发随机博弈 $\mathcal{G}^\star$。学习流程按幕（Episode）推进：在每一幕 $t$ 开始时，算法根据历史轨迹的访问计数更新各非终止状态-动作对（Slot）的经验转移概率与 Weissman $L^1$ 置信半径，构成经验鲁棒并发随机博弈 $\mathcal{G}_t$；随后计算模型不确定度指标 $\Delta_t$ 并检验终止条件 $\Delta_t \le \varepsilon/4$。若不确定度未达标，算法构造一个以未知插槽为吸收目标的辅助探索鲁棒 MDP $\mathcal{G}_t^e$，求解使最坏情况可达概率最大化的探索策略 $\sigma_t^e$，并在真实环境中自适应采样多条轨迹以扩充数据集；一旦不确定度降至阈值以内，黑盒求解器在经验模型上求解鲁棒社会福利最优 $\varepsilon$-纳什均衡（$\varepsilon$-RSWNE），若求解成功则输出近似均衡，若求解器判定无解则触发可靠的非存在性证书。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入博弈结构与超参数<br/>(S, A, &Gamma;, r), Supp(P*), &epsilon;, &delta;"] --> B["数据驱动L1置信集构建<br/>统计访问计数并计算经验核与置信半径"]
    B --> C["模型误差与灵敏度评估<br/>计算全局最大转移偏差 &Delta;<sub>t</sub>"]
    C --> D{"收敛判定<br/>&Delta;<sub>t</sub> &le; &epsilon;/4 ?"}
    D -->|是| E["纳什边界判定与鲁棒均衡求解<br/>黑盒调用L1-CSG求解器"]
    E -->|found=true| F["输出：&epsilon;-社会福利最优&epsilon;-NE"]
    E -->|found=false| G["输出：非存在性可靠证书<br/>&mu;*未定义或&mu;* < 0"]
    D -->|否| H["辅助探索RMDP构建与求解<br/>将未知插槽设为吸收态并最大化最坏可达率"]
    H --> I["真实环境自适应轨迹采样<br/>执行探索策略更新插槽访问统计"]
    I --> B

关键设计¶

1. 数据驱动的 $L^1$ 置信集构建与灵敏度界：控制转移扰动对策略价值的传播偏差

针对转移概率未知导致策略评估产生不可控误差的难题，算法利用 Weissman 经验测度集中不等式构建矩形不确定性集合。对于每个非终止状态-动作对 $(s,a) \in \mathcal{X}_{\text{nt}}$，在累积访问次数 $n := N_t(s,a)$ 下，真实转移分布 $P_{sa}^\star$ 以至少 $1 - \delta_{sa,n}^{\text{cont}}$ 的高概率落入以经验频率 $\widehat{P}_{sa,t}$ 为中心的 $L^1$ 范数置信球内，其半径定义为： $$\alpha_t(s,a) := \sqrt{\frac{2}{n} \ln\left( \frac{2^{|S|} - 2}{\delta_{sa,n}^{\text{cont}}} \right)}$$ 为限制该局部偏差在有限时域 $H$ 上的复利传播，算法推导出基于全状态边际分布的敏感度引理（Sensitivity Lemma）。对于任意固定策略概型 $\sigma$、玩家 $i$ 与起始状态 $s_0$，经验模型与任一置信转移核诱导的期望累计回报差异被严格控制在： $$|u_i(\sigma, P \mid s_0) - u_i(\sigma, \widehat{P} \mid s_0)| \le \Delta_t := \frac{1}{2} R_{\max} H^2 \max_{(s,a) \in \mathcal{X}_{\text{nt}}} \sup_{p \in \mathcal{P}_t(s,a)} \|p - \widehat{P}_{sa}\|_1$$ 由于在单步转移中边际分布的 $L^1$ 扰动以步数线性积累，累加求和后呈现二次时域因子 $\frac{1}{2} H^2$，从而为后续策略价值的跨模型迁移奠定了严格的上界。

2. 纳什边界判定与鲁棒均衡迁移：平衡近似均衡求解与非存在性可靠证书

针对并发博弈中稳态纳什均衡可能不存在以及经验模型与真实模型均衡错位的痛点，本文提出了纳什边界（Nash Margin）这一形式化度量。对于策略概型 $\sigma$ 与转移核 $P$，纳什边界量化了所有玩家在所有状态下单方偏离的最大潜在收益亏损： $$\mu(\sigma, P) := \min_{i \in N} \min_{s \in S} \inf_{\sigma'_i \in \Sigma_i} \left[ u_i(\sigma, P \mid s) - u_i(\sigma_{-i}[\sigma'_i], P \mid s) \right]$$ 显然，$\mu(\sigma, P) \ge 0$ 当且仅当 $\sigma$ 是核 $P$ 下的精确纳什均衡，而全局最优边界 $\bar{\mu} := \max_{\sigma \in \Sigma} \mu(\sigma, P^\star)$ 满足 $\bar{\mu} \ge 0$ 充要对应于真实博弈存在精确纳什均衡。算法确立了均衡迁移理论：若真实博弈存在边际为 $\mu^\star$ 的社会福利最优纳什均衡，则其在置信集 $\mathcal{P}_t$ 下必然构成一个 $(4\Delta_t - \mu^\star)$-鲁棒纳什均衡。由此，当黑盒求解器在置信集上无法找到 $\varepsilon$-RNE 时，可反推出 $\mu^\star < 4\Delta_t - \varepsilon$。一旦算法在 $\Delta_t \le \varepsilon/4$ 时终止且求解失败，即得到严格不等式 $\mu^\star < 0$，从而为真实博弈不存在精确纳什均衡提供了完备可靠（Sound）的数学凭证。

3. 基于辅助探索 RMDP 的集中式覆盖机制：将未知状态-动作对探索转化为鲁棒可达性优化

针对在线轨迹中无法通过单智能体动作确保冷启动状态-动作对覆盖的困境，算法将未知插槽的覆盖构造成单智能体形式的辅助探索鲁棒 MDP（Exploration RMDP）$\mathcal{G}_t^e$。在该模型中，双人联合动作被折叠为统一控制动作 $A^e := A_1 \times A_2$。对于已知访问达标集 $\mathcal{K}_t$ 之外的未知插槽 $\mathcal{U}_t := \mathcal{X}_{\text{nt}} \setminus \mathcal{K}_t$，模型将其转移强制替换为指向单一人工吸收态 $z$ 的确定性跃迁，并赋予转移奖励 $r^e_t(s,a) = \mathbf{1}[(s,a) \in \mathcal{U}_t]$。探索策略求解旨在最大化面对任意可能转移核时的最坏情况击中概率： $$\sigma_t^e \in \arg\max_{\sigma \in \Sigma} \inf_{P \in \mathcal{P}_t^e} \mathbb{P}^{\sigma, P}\left[\text{reach } \mathcal{U}_t\right]$$ 在博弈图支撑集非退化（最小可达概率 $p_{\text{reach}} > 0$）的假设下，这种悲观鲁棒设计确保了探索策略在真实未知环境 $P^\star$ 中的单幕覆盖概率下界始终满足 $p_t^e(P^\star) \ge p_{\text{reach}}$。相比之下，传统的乐观探索（Optimism-in-the-face-of-uncertainty）在不确定转移集下可能高估虚假路径的可达性，无法在真实环境中提供该保证。

4. 鞅差集中不等式驱动的全局样本复杂度收敛：从单幕条件概率到全局高概率界

由于未知集合 $\mathcal{U}_t$ 的收缩与探索策略 $\sigma_t^e$ 的更新深度依赖于历史采样轨迹，各幕之间的插槽命中事件存在复杂的历史自适应相关性。为打破统计依赖，算法定义事件指示变量 $X_t := \mathbf{1}[\text{第 } t \text{ 幕采样轨迹至少命中一次 } \mathcal{U}_t]$，并将基于 $p_{\text{reach}}$ 的单幕条件概率下界通过 Freedman 鞅差不等式进行跨幕累加。同时，算法将失败概率预算平摊至各幕 $\delta_t^{\text{cov}} := \delta^{\text{cov}} / (t(t+1))$，每幕自适应采集 $N_t^\pi = \lceil -(1/p_{\text{reach}}) \log \delta_t^{\text{cov}} \rceil$ 条轨迹。这一机制将所有插槽访问次数推升至充分覆盖阈值 $n_{\min} = \widetilde{\mathcal{O}}(R_{\max}^2 H^4 |S| / \varepsilon^2)$ 所需的总幕数严格约束在多项式量级，最终导出全局样本复杂度定理： $$T^\star = \widetilde{\mathcal{O}}\left( \frac{R_{\max}^2 H^4 |S|^2 |A|}{\varepsilon^2 p_{\text{reach}}} \right)$$

损失函数 / 训练策略¶

PAC-CSG 采用基于模型置信界的主动交互循环。总体置信度失效率平分为模型包含失效率 $\delta^{\text{cont}} = \delta/2$ 与覆盖失效率 $\delta^{\text{cov}} = \delta/2$。在无限时域概率可达与随机最短路径（SSP）目标下，博弈在目标状态集几乎必然终止的假设下存在有效时域 $H_{\text{eff}} \le |S|/p_T$（其中 $p_T$ 为从任意状态在 $|S|$ 步内到达目标集的最小最坏情况概率），将 $H$ 替换为 $H_{\text{eff}}$ 即可自然平移全部收敛保证。停止准则 $\Delta_t \le \varepsilon/4$ 纯粹由置信球半径驱动，无需先验预设采样总步数，实现了根据真实环境复杂度的自适应早停。

实验关键数据¶

主实验¶

实验基于 PRISM-games 扩展实现，在六个具有不同博弈特征的典型 CSG 基准上进行评估，所有案例均设置 $\varepsilon = 0.1, \delta = 0.05$。对比基准为 PRISM-games 提供的精确 CSG Oracle 求解器。

测试基准案例	博弈属性与目标公式	$\varepsilon$-NE 解出?	精确 NE 存在?	Oracle 真实值 $V^\star$	价值估计偏差 $V^\star - \widehat{V}$
Cyclic Preferences	循环偏好无限时域奖励累加	✗	✗	– (无解)	– (成功给出非存在证书)
Delayed Coordination	延迟协同多步有限时域奖励	✓	✓	3.240	$(1.573 \pm 0.069) \times 10^{-3}$
Hide-or-Run (极限博弈)	逃逸博弈无界时域可达概率	✓	✗	0.999 (极限值)	$(0.000 \pm 0.000) \times 10^{-3}$
Hide-or-Run (截断博弈)	逃逸博弈步数受限可达概率	✓	✓	0.800	$(0.000 \pm 0.000) \times 10^{-3}$
Mixed NE	协同博弈混合策略均衡可达	✓	✓	1.000	$(3.083 \pm 0.000) \times 10^{-3}$
Safe vs. Risky	风险敏感并发博弈可达概率	✓	✓	1.000	$(1.743 \pm 0.000) \times 10^{-3}$
Safe vs. Risky (无界)	吸收环路自激奖励无穷大	✓	✓ ($\infty$)	$\infty$	– (正确识别无界奖励)
Traffic Merge	交通合流避撞安全性验证	✓	✓	1.000	$(0.000 \pm 0.000) \times 10^{-3}$

消融实验¶

在相同 PAC 循环框架、停止条件 $\Delta_t \le \varepsilon/4$ 与失败预算分配下，对比本文悲观鲁棒 RMDP 探索器与乐观探索（Optimistic）、轮询探索（Round-robin）及均匀随机探索（Uniform-random）在收敛轨迹样本量（单位：百万条）与估计偏差上的表现。

探索机制	Safe vs. Risky 样本数	Safe vs. Risky 偏差	Traffic Merge 样本数	Traffic Merge 偏差	Delayed Coord. 样本数	Delayed Coord. 偏差
鲁棒探索 (本文)	5.90 ± 0.00	0.005 ± 0.000	6.90 ± 0.00	0.000 ± 0.000	42.95 ± 0.00	0.000 ± 0.000
乐观探索 (Optimistic)	5.90 ± 0.00	0.005 ± 0.000	6.90 ± 0.00	0.000 ± 0.000	43.15 ± 0.87	0.060 ± 0.097
轮询探索 (Round-robin)	6.09 ± 0.09	0.005 ± 0.000	16.22 ± 0.00	0.000 ± 0.000	44.92 ± 0.83	0.060 ± 0.097
均匀随机 (Uniform)	11.61 ± 0.01	0.005 ± 0.000	7.02 ± 0.00	0.000 ± 0.000	730.09 ± 0.28	0.180 ± 0.063

关键发现¶

非存在性可靠判定验证：在 Cyclic Preferences 博弈中，由于玩家收益存在非传递性循环导致固定点不存在，算法在全部 10 次独立随机运行中 100% 返回 NOT_FOUND，准确给出了不存在稳态纳什均衡的可靠证书；而在 Hide-or-Run 极限博弈中，算法返回了逼近极限均衡的近似策略（以 0.999 概率躲避），符合可靠但不完备（Sound but incomplete）的理论预期。
探索机制的鲁棒性增益：在稀疏奖励与瓶颈状态显著的 Delayed Coordination 博弈中，均匀随机探索耗费了多达 $17\times$ 的采样轨迹；乐观探索虽样本量接近鲁棒探索，但因内部最大化诱导了高方差的有偏轨迹，估计偏差达到 0.060，而本文悲观鲁棒探索实现了 $0.000$ 的零偏差精确收敛。
参数标度律符合理论预期：对状态数 $|S|$、联合动作数 $|A|$、时域 $H$ 及精度倒数 $1/\varepsilon$ 进行单变量扫描，经验拟合得到的对数对数斜率分别为 $|S|^{1.44}$、$|A|^{0.89}$、$H^{3.94}$ 以及 $(1/\varepsilon)^{2.11}$。实际增长显著优于或吻合最坏情况理论界限 $|S|^2 |A| H^4 / \varepsilon^2$。

亮点与洞察¶

博弈论与统计不确定性的解耦桥梁：首次将不确定性下的博弈求解与 PAC 样本复杂度闭环结合，通过纳什边界的单调灵敏度传递，证明了在经验模型上计算鲁棒均衡能以可控误差泛化到真实博弈。
将多智能体协作探索归约为单智能体鲁棒控制：创造性地构建了辅助吸收态探索 RMDP，将原本因动作耦合极难探索的并发博弈联合覆盖问题，转化为具有严格最坏情况可达概率保证的经典单智能体鲁棒动态规划。
数据驱动的非存在性证书设计：传统学习算法往往预设解必定存在而在无解问题上陷入振荡，PAC-CSG 建立了依据统计误差下界判定均衡非存在性的判定范式，为安全关键系统的模型检验与策略验证提供了新工具。

局限与展望¶

集中式探索假设的约束：算法依赖中央协调器在数据采集阶段统一指定联合动作分布，在完全去中心化且智能体间存在通信隔离的对战场景中难以直接套用。
对图支撑集先验的依赖：推导可达概率下界 $p_{\text{reach}} > 0$ 时假设博弈转移图的拓扑连通支撑集已知，若环境存在未知的连通拓扑陷阱，初始化阶需引入额外的拓扑发现协议。
最坏情况误差指标的保守性：停止准则 $\Delta_t$ 取决于全空间单个最难访问插槽的最大置信半径，在非决策关键分支存在孤立瓶颈状态时容易产生过度采样阶梯现象，未来可探索基于值函数导向（Value-aware）的不确定性压缩。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立转移未知并发随机博弈的 PAC 学习理论并引入纳什边界判定。
实验充分度: ⭐⭐⭐⭐☆ 在经典博弈基准与 PRISM-games 形式化求解器上进行了严谨的真值对照与维度标度验证。
写作质量: ⭐⭐⭐⭐⭐ 理论脉络清晰，引理层层递进，附录构造性证明完备详实。
价值: ⭐⭐⭐⭐⭐ 为多智能体强化学习基础理论、形式化验证及鲁棒博弈论提供了标杆性的分析工具。