Toward Online Robust Zero-Sum Markov Games with Function Approximation¶

会议: NeurIPS 2026
arXiv: 2610.26286
领域: 强化学习
关键词: 鲁棒强化学习、零和马尔可夫博弈、函数逼近、对偶鲁棒贝尔曼拟合、贝尔曼-埃卢德复杂度

一句话总结¶

本文提出乐观对偶鲁棒贝尔曼（ODRB）框架，通过对偶贝尔曼算子拟合、后向验证置信集与剥削者混合数据采集，首次为带函数逼近的在线鲁棒零和马尔可夫博弈建立了可分离探索、算子学习、博弈求解误差与模型误配的次线性遗憾界。

研究背景与动机¶

鲁棒强化学习致力于解决智能体在名义训练环境与实际测试环境之间的动态分布漂移问题。在多智能体交互场景中，这种环境漂移与博弈双方的策略交互深度交织：状态转移不仅由双人联合动作决定，鲁棒性定义也直接锚定于对抗博弈的极小化极大（minimax）行为，导致学习者必须仅依靠名义转移数据去推断和抵抗最坏情况转移。近年来，单智能体在线鲁棒 MDP 已经在通用函数逼近理论上取得了重要突破，但在双人零和马尔可夫博弈中，将函数逼近与鲁棒性结合仍面临着多重理论壁垒。

这一困难的核心矛盾体现在三个层面：其一，鲁棒贝尔曼算子同时耦合了分布鲁棒性对偶优化与阶段博弈的极小化极大鞍点计算，算子闭包性与统计估计必须在极小化极大回退下同时建立；其二，策略覆盖度极其脆弱，决定遗憾界的状态-动作占用测度是由最坏情况转移核诱导的极小化极大轨迹，而用于拟合鲁棒算子的样本则由在线自适应交互产生，两者存在本质的多智能体覆盖度鸿沟；其三，现有的非鲁棒大状态博弈理论无法直接处理不确定转移算子的统计学习，而既有的鲁棒博弈研究多局限于表格型、生成模型或无算子学习视角的特殊设置。

面对算子学习与博弈求解在最坏分布下的深度耦合，本文转换了分析视角：不必在整个函数空间内全局精确恢复鲁棒算子，而是将探索复杂度与统计检验聚焦于由候选价值类诱导的鲁棒贝尔曼残差类 $(I - \mathcal{T}^\sigma)\mathcal{F}$。核心 idea：构建乐观对偶鲁棒贝尔曼（ODRB）框架，将鲁棒极小化极大算子转化为名义数据上的经验对偶拟合，结合分周期交叉验证置信集与单边最佳响应（剥削者混合）探索，从理论上将多智能体探索复杂度、对偶算子拟合误差、阶段博弈逼近误差和函数逼近偏置完全解耦。

方法详解¶

整体框架¶

ODRB 旨在解决情景式双人零和鲁棒马尔可夫博弈 $\mathcal{M}=(\mathcal{S}, \mathcal{A}, \mathcal{B}, H, \{r_h\}, \{P_h^0\}, \{\mathcal{U}_h\})$ 的在线学习问题。在每个阶段 $h$，面对转移核不确定集 $\mathcal{U}_h(s,a,b) = \{P: D(P, P_h^0(\cdot\mid s,a,b)) \leqslant \sigma\}$，玩家 1 旨在最大化回报，而对手和环境扰动共同极小化回报。整体算法采用分周期（epochwise）和交叉拟合（cross-fitting）机制推进：在周期起点，利用历史名义交互数据通过对偶经验风险极小化拟合鲁棒贝尔曼算子；在候选价值函数类 $\mathcal{F}$ 上构建基于后向贝尔曼残差的全局置信集，挑选乐观价值函数并求解阶段矩阵博弈以提取极小化极大策略；最后在环境交互中引入剥削者混合（exploiter-mix）分支，以确保覆盖单边策略偏离所诱导的状态分布。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["名义交互缓冲区<br/>D_h 样本集"] --> B["对偶鲁棒贝尔曼拟合<br/>经验对偶 ERM 拟合冻结算子"]
    B --> C["后向验证置信集<br/>跨折检验贝尔曼残差筛选候选函数"]
    C --> D["乐观极小化极大规划<br/>置信集内最大化初态价值并解阶段博弈"]
    D --> E["剥削者混合数据采集<br/>执行目标策略与单边最佳响应分支"]
    E -->|收集新轨迹并填充缓冲| A

关键设计¶

1. 对偶鲁棒贝尔曼拟合：规避最坏转移核显式优化的经验对偶回归

鲁棒反向递推的目标是在阶段 $h$ 计算最坏情况期望 $(\mathcal{T}_h^\sigma f_{h+1})(s,a,b) = r_h(s,a,b) + \inf_{P \in \mathcal{U}_h(s,a,b)} \mathbb{E}_{s' \sim P}[V_{f,h+1}(s')]$，其中 $V_{f,h+1}(s')$ 是后续阶段矩阵博弈的值。直接在无穷维概率测度集合上极小化无法用名义数据估计。基于 $\phi$-散度对偶表示，引入对偶变量 $g = (g_\eta, g_\nu) \in \mathcal{G}_h$ 及共轭函数 $\phi^\star$，将内部下确界转化为对偶损失的期望，即鲁棒转移价值等价于 $-\inf_g \mathbb{E}_{P_h^0}[\ell_\phi(f_{h+1}; s,a,b,s'; g)]$。该损失定义为： $$ \ell_\phi(f_{h+1}; s,a,b,s'; g) = g_\eta(s,a,b)\sigma - g_\nu(s,a,b) + g_\eta(s,a,b)\phi^\star\left(\frac{g_\nu(s,a,b) - V_{f,h+1}(s')}{g_\eta(s,a,b)}\right) $$ 通过在历史名义样本缓冲池上求解经验风险极小化 $g_{h,f} \in \arg\min_{g \in \mathcal{G}_h} \widehat{\mathcal{L}}_h(g; f)$，得到即插即用（plug-in）的经验鲁棒贝尔曼算子 $\widehat{\mathcal{T}}_{h,f}^\sigma$，从而将算子学习的统计误差孤立为对偶逼近误差与经验浓度项。

2. 后向验证置信集与乐观规划：约束候选价值函数以驱动有效探索

算法通过后向一致性验证来构造阶段价值函数的全局置信空间 $\mathfrak{F} := \{f \in \mathcal{F} : \widehat{\mathrm{BV}}_h(f) \leqslant \beta_h, \forall h\}$。为了阻断自适应更新造成的过拟合，算法采用周期冻结与交叉拟合：在当前周期 $e$ 开始时，先利用前序样本固定对偶算子 $\widehat{\mathcal{T}}_{h,f}^{\sigma,(e)}$，随后在周期内新鲜的验证折数据上计算经验平方残差统计量： $$ \widehat{\mathrm{BV}}{h,e}(f) := \sum} \frac{1}{n_{h,j}} \sum_{(s,a,b) \in \mathcal{Dh^{(j)}} \left[ f_h(s,a,b) - (\widehat{\mathcal{T}})(s,a,b) \right]^2 $$ 只要阈值 }^{\sigma,(e)} f_{h+1$\beta_{h,e}$ 设置得当，真实的极小化极大贝尔曼不动点便以高概率始终留在置信集中。此时，学习者在 $\mathfrak{F}_e$ 中挑出初态价值最大的函数 $f^e \in \arg\max_{f \in \mathfrak{F}_e} V_{f,1}(s_1)$ 实现乐观探索，并对每个状态求解由 $f_h^e(s, \cdot, \cdot)$ 构成的矩阵博弈鞍点，得到部署策略对 $(\pi_h^e, \nu_h^e)$。

3. 剥削者混合数据采集：借助单边最佳响应填补多智能体覆盖鸿沟

在博弈环境中，仅执行当前计算出的策略对 $(\pi^k, \nu^k)$ 会陷入认知盲区：若对手偏离均衡，最坏情况转移所诱导的状态可能完全无法被名义轨迹覆盖。为此，ODRB 引入了基于当前估计博弈的剥削者分支。定义两名玩家关于冻结价值函数的拟合最佳响应 $\mathrm{BR}_1^k \in \arg\max_{\pi} \widehat{V}_1^k(\pi, \nu^k)$ 与 $\mathrm{BR}_2^k \in \arg\min_{\nu} \widehat{V}_1^k(\pi^k, \nu)$。在每一轮决策时，环境按照混合分布采样执行分支： - 以 $1-p$ 的主概率执行当前乐观策略对 $(\pi^k, \nu^k)$； - 分别以 $p/2$ 的概率执行单边偏离对 $(\mathrm{BR}_1^k, \nu^k)$ 与 $(\pi^k, \mathrm{BR}_2^k)$。

这种混合机制主动探测单边偏离可达的状态-动作空间，为协方差矩阵和状态占据率转移提供了下界支撑，从根本上保证了经验数据对最坏转移核测度的支撑覆盖条件 $\mu_h^k \ll \bar{\eta}_{h,k}$。

损失函数 / 训练策略¶

在具体的线性/核函数实例化中，算法采用对偶岭回归（Ridge Regression）进行参数闭式拟合，避免了非凸优化求解；在线性混合 MDP 条件下，后向验证置信集转化为针对残差特征权重的自规范化椭球置信球。在线更新周期 $E_e$ 采用几何递增的时间表切分，兼顾样本量积累与计算效率。

实验关键数据¶

主实验¶

实验在合成的线性混合博弈环境（$d=8, 16, 32$）及带有动作偏离诱导转移的支撑偏移（support-shift）基准上进行评估，主要对比不加鲁棒对偶调整的基线 Sigma0、无剥削者分支消融模型 NoEx 以及不同置信半径 $\beta$、探索超参 $\tau$ 下的 ODRB。主结果对比聚焦于名义代理回报（Proxy）、真实最坏情况部署回报（Deploy）和代理泛化差距（Proxy gap）：

场景与配置 ($d=8, K=5000$)	评估指标 (Mean $\pm$ 95% CI)	ODRB ($\beta=0.30, \tau=0.02$)	Sigma0 (非鲁棒基线)	优势/变化说明
线性混合环境	代理回报 Proxy Return $\uparrow$	$0.204 \pm 0.069$	$0.230 \pm 0.088$	鲁棒校准容忍适度名义回报代价
线性混合环境	部署最坏回报 Deploy Return $\uparrow$	$0.239 \pm 0.089$	$0.230 \pm 0.088$	配对检验差值 $0.0094$ ($p=0.0469$)
线性混合环境	评估差距 Proxy Gap $\downarrow$	$0.0072 \pm 0.0074$	$0.0080 \pm 0.0047$	保持低泛化断层与高一致性
重设计支撑偏移 ($m=0.10$)	部署最坏回报 Deploy Return $\uparrow$	$0.5742$ ($\beta=0.10$)	$0.4983$	提升 $+0.0759$ (显著偏向保守安全动作)
重设计支撑偏移 ($m=0.15$)	部署最坏回报 Deploy Return $\uparrow$	$0.5912$ ($\beta=0.10$)	$0.4600$	提升 $+0.1312$ (抵抗严重转移扰动)

消融实验¶

消融实验围绕剥削者探索分支（NoEx）及超参数 $(\beta, \tau)$ 展开，重点考察剥削者探索对策略占用熵（Entropy）及最坏情况部署稳定性的影响：

配置 ($d=8$)	部署回报 (Deploy Return)	泛化差距 (Proxy Gap)	占用状态熵 (Entropy)	机制说明
ODRB ($\beta=0.30, \tau=0.02$)	$0.239 \pm 0.089$	$0.0073 \pm 0.0074$	$5.076 \pm 0.192$	完整模型：高状态覆盖度与极低泛化差距
ODRB ($\beta=0.20, \tau=0.02$)	$0.236 \pm 0.089$	$0.0068 \pm 0.0065$	$5.067 \pm 0.197$	诊断低 Gap 最优校准点
ODRB ($\beta=0.30, \tau=0$)	$0.288 \pm 0.115$	$0.0624 \pm 0.0669$	$3.781 \pm 0.209$	去除正则探索：名义激进但泛化断层飙升
NoEx ($\beta=0.30$) 无剥削者分支	$0.288 \pm 0.115$	$0.0644 \pm 0.0687$	- (欠覆盖)	缺失最佳响应探测，严重产生未见转移盲区

关键发现¶

剥削者探索决定战略覆盖：去掉剥削者探索分支（NoEx 或 $\tau=0$）后，虽然在训练回放名义值上显得更激进，但状态-动作占用熵骤降（$5.076 \to 3.781$），导致其在最坏分布下的评估差距扩大近 9 倍（$0.0073 \to 0.0644$），验证了单边偏离分支在闭合多智能体覆盖鸿沟上的理论必要性。
鲁棒校准与名义价值的客观权衡：在表格型防御博弈中，Sigma0 名义回报达 4.077 但测试时崩溃至 2.008，而 ODRB 名义回报为 1.154，最坏情况下仍保持 1.080，表明算法通过主动收缩激进决策换取了分布漂移下的高抗跌性。
诱导策略的质变：在支撑偏移基准测试中，Sigma0 在 5/5 种子中均选择激进动作导致环境惩罚，而 ODRB 在绝大多数测试中学习并锁定了安全动作（Safe Action），证明了其性能收益源自于学到了更稳健的防御策略而非拟合偏置。

亮点与洞察¶

算子级残差分解的理论简化：将分析焦点从全空间的鲁棒贝尔曼算子恢复，严格收缩到由候选价值类自身诱导的残差类 $(I - \mathcal{T}^\sigma)\mathcal{F}$，从而在不依赖强遍历性假设下，通过贝尔曼-埃卢德复杂度刻画样本效率。
对偶形式将鲁棒极小化转化为凸经验风险拟合：利用 $\phi$-散度共轭把内部下确界转化为名义分布下的凸优化，使得传统强化学习中的值拟合工具（如岭回归、核截断）可以直接跨领域复用。
剥削者混合采样填补多智能体覆盖缺陷：不仅理论上保证了马尔可夫决策过程中的特征激励下界，在实践中也作为通用的数据增强采样策略，有效防止多智能体算法在未见偏离动作下发生分布外崩溃。

局限与展望¶

单边单向价值遗憾界与纳什均衡收敛的差距：当前理论建立的是以极小化极大值为基准的单边值比较差，未直接证明学习轨迹能收敛到双边两端无悔的近似纳什均衡。
共享回报假设的局限：模型要求两玩家与自然环境处于同一零和标量回报定义下，无法直接推广到每个玩家各自拥有主观稳健收益的一般和（general-sum）鲁棒博弈。
超参数静态设置依赖：当前的预烧期（burn-in）与剥削概率依赖未知的覆盖常数，尚缺乏自适应调整探索概率与置信椭球半径的在线参数调节方案。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立带通用函数逼近与对偶算子拟合的在线鲁棒零和马尔可夫博弈理论框架。
实验充分度: ⭐⭐⭐⭐☆ 理论驱动的合成环境与支撑漂移实验设计精细，充分验证了理论预测，但受限于理论验证性质缺少大规模高维基准测试。
写作质量: ⭐⭐⭐⭐⭐ 结构清晰，从决定性分解到统计界限层层递进，对理论边界与假设解释十分坦诚透彻。
价值: ⭐⭐⭐⭐⭐ 为安全强化学习、多智能体鲁棒控制与博弈论交叉领域提供了极具开创性的理论基石。

场景与配置 (\(d=8, K=5000\))	评估指标 (Mean \(\pm\) 95% CI)	ODRB (\(\beta=0.30, \tau=0.02\))	Sigma0 (非鲁棒基线)	优势/变化说明
线性混合环境	代理回报 Proxy Return \(\uparrow\)	\(0.204 \pm 0.069\)	\(0.230 \pm 0.088\)	鲁棒校准容忍适度名义回报代价
线性混合环境	部署最坏回报 Deploy Return \(\uparrow\)	\(0.239 \pm 0.089\)	\(0.230 \pm 0.088\)	配对检验差值 \(0.0094\) (\(p=0.0469\))
线性混合环境	评估差距 Proxy Gap \(\downarrow\)	\(0.0072 \pm 0.0074\)	\(0.0080 \pm 0.0047\)	保持低泛化断层与高一致性
重设计支撑偏移 (\(m=0.10\))	部署最坏回报 Deploy Return \(\uparrow\)	\(0.5742\) (\(\beta=0.10\))	\(0.4983\)	提升 \(+0.0759\) (显著偏向保守安全动作)
重设计支撑偏移 (\(m=0.15\))	部署最坏回报 Deploy Return \(\uparrow\)	\(0.5912\) (\(\beta=0.10\))	\(0.4600\)	提升 \(+0.1312\) (抵抗严重转移扰动)

配置 (\(d=8\))	部署回报 (Deploy Return)	泛化差距 (Proxy Gap)	占用状态熵 (Entropy)	机制说明
ODRB (\(\beta=0.30, \tau=0.02\))	\(0.239 \pm 0.089\)	\(0.0073 \pm 0.0074\)	\(5.076 \pm 0.192\)	完整模型：高状态覆盖度与极低泛化差距
ODRB (\(\beta=0.20, \tau=0.02\))	\(0.236 \pm 0.089\)	\(0.0068 \pm 0.0065\)	\(5.067 \pm 0.197\)	诊断低 Gap 最优校准点
ODRB (\(\beta=0.30, \tau=0\))	\(0.288 \pm 0.115\)	\(0.0624 \pm 0.0669\)	\(3.781 \pm 0.209\)	去除正则探索：名义激进但泛化断层飙升
NoEx (\(\beta=0.30\)) 无剥削者分支	\(0.288 \pm 0.115\)	\(0.0644 \pm 0.0687\)	- (欠覆盖)	缺失最佳响应探测，严重产生未见转移盲区