Beyond Pessimism: Offline Learning in KL-regularized Games¶

会议: NeurIPS 2026
arXiv: 2604.06738
论文: https://arxiv.org/abs/2604.06738
领域: 学习理论
关键词: 离线博弈学习, KL正则化, 零和博弈, 无悲观算法, 快速收率

一句话总结¶

本文突破离线博弈学习中对悲观值估计的传统依赖，利用KL正则化诱导的最优响应平滑性与零和博弈算子反对称性，提出了首个无需悲观惩罚的离线学习框架，在单侧覆盖条件下将样本复杂度由 $\widetilde{\mathcal{O}}(1/\sqrt{n})$ 大幅提升至 $\widetilde{\mathcal{O}}(1/n)$ 快速率，并给出了具备末轮收敛保证的高效自博弈算法。

研究背景与动机¶

离线强化学习（Offline RL）旨在仅利用预先收集的静态数据集求解最优决策策略，从而规避在线试错在医疗、金融与自动驾驶等高风险领域中高昂的探索成本与安全隐患。然而，离线学习的核心瓶颈在于分布偏移（Distribution Shift）：待评估的目标策略诱导的状态-动作分布往往显著偏离生成数据的行为策略分布，导致对低频或未覆盖样本的外推误差与价值虚高。针对这一问题，单智能体离线强化学习与离线博弈学习在过去几年间几乎完全建立在“悲观主义原则”（Pessimism Principle）之上——通过构建逐点不确定性惩罚项或在置信版本空间中选取最坏情况收益，将缺乏数据支持的动作人为压低。尽管这一思路在理论上提供了收敛保证，但在实践中却带来了沉重的算法复杂度，需要精细调优超参数并求解复杂的辅助优化子问题。

当离线学习拓展至多智能体与博弈论场景时，挑战尤为严峻。多智能体系统不仅面临常规的分布漂移，还面临由单个智能体单侧偏离（Unilateral Deviation）诱发的策略性分布漂移。这一结构是当下大语言模型（LLM）对齐的核心理论基石：例如在人类反馈纳什学习（Nash Learning from Human Feedback, NLHF）中，模型通过对比胜率与显式施加的参考策略KL散度惩罚来优化策略，其本质正是一个带KL正则化的两人零和博弈。以往关于KL正则化离线博弈的理论成果（如 Ye et al., 2024）依然沿袭传统离线马尔可夫博弈的悲观下界构造框架，其样本复杂度被限制在 $\widetilde{\mathcal{O}}(1/\sqrt{n})$ 的慢速收敛阶。这引发了一个悬而未决的基础理论问题：在具有强凸性与平滑几何结构的KL正则化博弈中，我们是否真的必须依赖悲观主义？

本文的研究切入点正是深入挖掘KL散度对博弈几何流形带来的本质改变：KL正则化赋予了最优响应映射全局Lipschitz平滑度，同时零和博弈的收益转移算子具备天然的反对称性（Skew Symmetry）。核心 idea：彻底摒弃显式悲观惩罚与保守值构造，直接在最小二乘收益估计器诱导的经验博弈上求解鞍点；利用KL最优响应的对数几率平滑性与收益算子反对称诱导的二阶项相互抵消，将策略对偶隙完全控制在单侧估计误差的平方项内，首次在单侧覆盖假设下实现无悲观且达到 $\widetilde{\mathcal{O}}(1/n)$ 快速率的离线博弈均衡学习。

方法详解¶

整体框架¶

本文的方法分为理论统计估计框架（Algorithm 1）与高效自博弈策略优化实现（Algorithm 2）两个层次。整个学习流水线输入离线离散/连续上下文数据集 $\mathcal{D} = \{(x_i, a_{i,1}, a_{i,2}, p_i)\}_{i=1}^n$、参考策略 $\pi_{\text{ref}}$、正则化参数 $\eta$ 以及函数逼近假设类 $\mathcal{G}$。在统计层面上，框架首先执行全局最小二乘回归拟合真实收益函数 $g^\star$ 得到经验估计 $\widehat{g}$；随后求解该经验收益诱导的经验KL正则化零和博弈唯一纳什均衡 $\widehat{\pi}$。在计算层面上，为了避免直接求解大规模上下文鞍点问题的计算开销，算法设计了交替迭代的自博弈镜像下降更新机制，通过在固定收益估计下逐步调整两名玩家的行动策略，最终输出具有严格末轮理论保证的策略对 $(\pi_1^{(T)}, \pi_2^{(T)})$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["离线偏好数据集 𝒟 与参考策略 πref"] --> B["最小二乘收益估计<br/>ĝ = argmin Σ (g(x,a₁,a₂) - p)²"]
    B --> C["经验KL正则化零和博弈构建<br/>J(ĝ, π₁, π₂) 目标函数与算子定义"]
    C --> D["反对称稳定性分析<br/>ΔM 反对称消去二阶交叉项，误差定域于单侧偏离"]
    D --> E["双智能体自博弈策略优化<br/>交替镜像下降迭代更新 π₁⁽ᵗ⁺¹⁾, π₂⁽ᵗ⁺¹⁾"]
    E --> F["输出末轮策略对 (π₁⁽ᵀ⁾, π₂⁽ᵀ⁾)<br/>达成无悲观 Õ(1/n) 统计误差 + O(1/√T) 优化误差"]

关键设计¶

1. 最小二乘经验收益估计与无悲观鞍点求解：彻底剥离保守性惩罚与不确定性置信集

传统离线强化学习与博弈算法为了防止外推风险，必须在经验收益上扣减点状或矩阵不确定性奖励（如通过协方差矩阵构造椭球置信集，计算 worst-case payoff），这会导致目标泛化界中残留 $\mathcal{O}(1/\sqrt{n})$ 的均方根置信半径项。本文反其道而行之，完全不引入任何点状或全局保守下界，直接定义经验收益估计器 $\widehat{g}$ 为无正则项的经验平方损失最小化子： $$\widehat{g} \in \arg\min_{g \in \mathcal{G}} \sum_{i=1}^n \left( g(x_i, a_{i,1}, a_{i,2}) - p_i \right)^2$$ 并在整个函数类 $\mathcal{G}$ 满足可实现性假定（即真实收益 $g^\star \in \mathcal{G}$）的前提下，直接基于经验收益 $\widehat{g}$ 定义无偏纳什均衡： $$\widehat{\pi} = (\widehat{\pi}_1, \widehat{\pi}_2) \in \arg\max_{\pi_1 \in \Pi} \arg\min_{\pi_2 \in \Pi} J(\widehat{g}, \pi_1, \pi_2)$$ 其中KL正则化目标函数形式为： $$J(g, \pi_1, \pi_2) := \mathbb{E}_{x \sim \rho} \mathbb{E}_{\substack{a_1 \sim \pi_1(\cdot|x)\\ a_2 \sim \pi_2(\cdot|x)}} \left[ g(x, a_1, a_2) - \eta^{-1} \log \frac{\pi_1(a_1|x)}{\pi_{\text{ref}}(a_1|x)} + \eta^{-1} \log \frac{\pi_2(a_2|x)}{\pi_{\text{ref}}(a_2|x)} \right]$$ 通过这种极简的设计，避免了不确定性估计的超参数调优与复杂约束求解。

2. 算子反对称性与强单调性诱导的纳什均衡局部稳定性：将全策略扰动收敛至单侧偏离误差

通常无悲观算法在离线设定下会崩溃，是因为学习到的策略 $\widehat{\pi}$ 可能访问离线数据集未覆盖的高风险动作，从而产生不可控的泛化漂移。本文克服这一核心困境的关键在于证明了KL正则化博弈在鞍点算子层面的结构性稳定性。将上下文 $x$ 处的离散博弈改写为变分不等式单调算子 $F_{g,x}(\pi_x) := M_{g,x}\pi_x + \eta^{-1}\nabla \text{Reg}(\pi_x)$，其中 $M_{g,x} := \begin{pmatrix} 0 & -G_g(x) \\ G_g(x)^\top & 0 \end{pmatrix}$ 具有天然的反对称性（Skew-Symmetry）。由于KL正则化项在联合 $\ell_1$ 空间具有 $\frac{1}{2\eta}$ 的强凸性，$F_{g,x}$ 具备严格的强单调性： $$\frac{1}{2\eta} \|\widehat{\pi}_x - \pi^\star_x\|_1^2 \leq \left\langle F_{g^\star, x}(\widehat{\pi}_x) - F_{g^\star, x}(\pi^\star_x), \widehat{\pi}_x - \pi^\star_x \right\rangle = \left\langle (M_{g^\star, x} - M_{\widehat{g}, x}) \widehat{\pi}_x, \widehat{\pi}_x - \pi^\star_x \right\rangle$$ 令算子差为 $\Delta M_x := M_{g^\star, x} - M_{\widehat{g}, x}$，将其展开为基准项与扰动项 $\widehat{\pi}_x = \pi^\star_x + (\widehat{\pi}_x - \pi^\star_x)$。由于反对称矩阵的二次型恒等为零，即 $\langle \Delta M_x (\widehat{\pi}_x - \pi^\star_x), \widehat{\pi}_x - \pi^\star_x \rangle = 0$，上式右端原本涉及被估计策略与真实策略交叉偏差的二次项完全消除，精确退化为纯单侧偏离项： $$\frac{1}{2\eta} \|\widehat{\pi}_x - \pi^\star_x\|_1^2 \leq \langle \Delta M_x \pi^\star_x, \widehat{\pi}_x - \pi^\star_x \rangle \leq \|\Delta M_x \pi^\star_x\|_\infty \|\widehat{\pi}_x - \pi^\star_x\|_1$$ 两端消去 $\|\widehat{\pi}_x - \pi^\star_x\|_1$ 即得关键稳定性界 $\|\widehat{\pi}_x - \pi^\star_x\|_1 \leq 2\eta \mathcal{E}(x)$，其中 $\mathcal{E}(x)$ 是严格以纳什策略 $\pi^\star$ 为基准的单侧估计误差（Unilateral Estimation Error）。这意味着学习策略 $\widehat{\pi}$ 的偏差被局域化为仅在真实最优响应方向上的估计误差，无需假定对任意策略的全局一致覆盖。

3. 对数几率平滑性与单侧集中度转化：建立无悲观快速率统计上界

对偶隙可严格拆解为由对偶偏离与单侧估计误差控制的两个间隙 $\text{Gap}_1$ 与 $\text{Gap}_2$。论文证明了KL正则化最优响应具有显式的Softmax形式，其对数几率差被两智能体的策略 $\ell_1$ 距离所控制。借助对数总和指数函数的 1-平滑性，Softmax分布之间的KL散度满足： $$\text{KL}(\text{Softmax}(z) \,\|\, \text{Softmax}(z')) \leq \frac{1}{2} \|z - z'\|_\infty^2$$ 将此平滑几何性质代入对偶隙界，得到 $\text{Gap}_1 + \text{Gap}_2 \leq (2\eta + 10\eta^3) \mathbb{E}_{x \sim \rho}[\mathcal{E}(x)^2]$。结合 $D_\mathcal{G}^2$-散度定义的单侧集中度假设（Unilateral Concentrability $C_{\text{uni}}$）： $$\sup_{\pi_i} \mathbb{E}_{(x, a_1, a_2) \sim \rho \times \pi_i \times \pi_{-i}^\star} \left[ D_\mathcal{G}^2((x, a_1, a_2); \pi_b) \right] \leq C_{\text{uni}}$$ 最小二乘在离线行为数据上的经验均方误差通过伯恩斯坦型快集中不等式以 $\mathcal{O}(\frac{\log(|\mathcal{G}|/\delta)}{n})$ 速率衰减，最终推导出了不含任何平方根因子的全局对偶隙界： $$\text{DualGap}(\widehat{\pi}) \leq \mathcal{O}\left( \frac{(\eta + \eta^3) C_{\text{uni}} \log(|\mathcal{G}|/\delta)}{n} \right)$$

4. 带对数密度比有界约束的在线镜像下降自博弈算法：实现高效迭代优化与末轮收敛

针对实际训练中经验博弈无法解析求解的瓶颈，算法2提出了无须交互的离线自博弈策略优化方案。在第 $t$ 轮迭代中，双方根据对手当前的分布计算预期收益向量 $\widehat{f}_1^{(t)}(x, a) = \mathbb{E}_{a_2 \sim \pi_2^{(t)}}[\widehat{g}(x, a, a_2)]$，并执行对数几率凸组合式的镜像更新： $$\pi_1^{(t+1)}(a|x) \propto \pi_1^{(t)}(a|x)^{1 - \alpha_t \eta^{-1}} \exp\left( \alpha_t \widehat{f}_1^{(t)}(x, a) \right) \pi_{\text{ref}}(a|x)^{\alpha_t \eta^{-1}}$$ 论文证明只要步长满足 $\alpha_t \leq \eta$，所有迭代步及经验均衡均严格处于有界对数密度比空间：$\sup_{x, a} |\log(\pi_i^{(t)}(a|x)/\pi_{\text{ref}}(a|x))| \leq 2\eta$。这确保了对偶隙关于策略扰动的全局Lipschitz连续性（Lipschitz常数为3）。结合时变步长 $\alpha_t = \frac{2\eta}{t+2}$，证明了上下文平均KL散度按 $\frac{16\eta^2}{T+1}$ 单调收敛，使自博弈末轮策略 $\pi^{(T)}$ 的总对偶隙严格收敛至统计误差与 $\mathcal{O}(\eta/\sqrt{T})$ 优化误差之和。

实验关键数据¶

论文为纯理论工作，给出了严格的非渐近收敛阶与复杂度推导，以下汇总核心理论复杂度对比与各阶段参数敏感度分析。

主实验（收敛阶与复杂度理论对比）¶

方法范式	算法机制	悲观惩罚设计	覆盖假设要求	样本复杂度 (对偶隙)	优化算法保证
传统悲观离线博弈 (Ye et al., 2024)	价值下界估计 (LCB / Version Space)	需构造点状/椭球不确定性惩罚项	单侧集中度 $C_{\text{uni}}$	$\widetilde{\mathcal{O}}\left(\sqrt{\frac{C_{\text{uni}}}{n}}\right)$ (慢速率)	需复杂约束优化求解
传统无悲观单智能体 RL (均匀假设)	经验风险最小化 (ERM)	无	全局状态-动作覆盖 (Uniform Coverage)	$\mathcal{O}(1/n)$ (需极强覆盖)	策略迭代 / Q-learning
本文 Minimax 估计器 (Alg. 1)	经验纳什均衡求解	无（完全无悲观、无置信区间）	单侧集中度 $C_{\text{uni}}$	$\mathcal{O}\left(\frac{(\eta + \eta^3) C_{\text{uni}} \log(\\|\mathcal{G}\\|/\delta)}{n}\right)$ (快速率)	经验鞍点直接求解
本文离线自博弈优化 (Alg. 2)	耦合镜像升降步 (Self-Play)	无	单侧集中度 $C_{\text{uni}}$	$\mathcal{O}\left(\frac{\eta}{\sqrt{T+1}} + \frac{(\eta + \eta^3) C_{\text{uni}} \log(\\|\mathcal{G}\\|/\delta)}{n}\right)$	末轮迭代 (Last-Iterate) 收敛

消融实验（理论分析关键组件敏感性与降解分析）¶

理论构造模块	理论依赖项	剥离/替换后的退化后果	机制与数学根源说明
反对称消除项 $\langle \Delta M_x (\widehat{\pi}_x - \pi^\star_x), \widehat{\pi}_x - \pi^\star_x \rangle = 0$	零和博弈斜对称收益矩阵 $M_{g,x}$	估计误差无法限定在单侧偏离，退化为需要全局策略覆盖	失去算子反对称性后，二次交叉扰动项无法消去，迫使引入悲观性以压制未覆盖区域误差
最优响应 Softmax 1-平滑性	对数总和指数函数 $\Phi(z)$ 的Hessian界	KL散度无法被对数几率 $\ell_\infty$ 范数二次控制，速率降级	引理2保证了 $\text{KL} \leq \frac{1}{2}\\|z-z'\\|_\infty^2$，是获得单侧误差平方项 $\mathcal{E}(x)^2$ 的数学基石
对数密度比一致有界性 (引理5)	迭代更新与纳什均衡的有界振幅 $\leq 2\eta$	对偶隙Lipschitz性失效，产生无穷大梯度或极度退化常数	确保无需假定参考策略的最小动作概率下界，即可实现全局Lipschitz迁移
自博弈衰减步长 $\alpha_t = \frac{2\eta}{t+2}$	递减步长时序调度	若固定步长 $\alpha$，自博弈只能收敛到极限振荡环或有偏领域	递减步长使得一阶扰动收缩与二阶误差累积达成精确平衡，保证 $\mathcal{O}(1/\sqrt{T})$ 末轮收敛

关键发现¶

无悲观下的快速率超越：长期以来学术界普遍认为离线策略评估与博弈必须依靠悲观原则来抵抗分布偏移，本文在理论上颠覆了这一固有范式，证明了KL正则化不仅是防止偏离参考策略的启发式手段，更能作为强凸平滑几何诱导项，直接把博弈样本复杂度从 $\widetilde{\mathcal{O}}(1/\sqrt{n})$ 加速至 $\widetilde{\mathcal{O}}(1/n)$。
正则化强度的双刃剑效应：正则化系数 $\eta$ 在样本界中以 $\eta + \eta^3$ 形式出现。当 $\eta \to 0$（强正则化）时，策略被强行锚定在参考策略周围，对偶隙趋近于0；当 $\eta$ 较大（弱正则化）时，常数项呈立方阶快速膨胀，说明弱正则化博弈逼近标准零和博弈时需要更高的数据覆盖质量与样本规模。
单侧覆盖的充要性：证明表明即使不引入悲观设计，单侧集中度假定（Unilateral Concentrability）亦完全足以保证统计可学性，无需进一步苛求全局覆盖假定。

亮点与洞察¶

反对称二次型消去法：利用博弈梯度算子差分 $\Delta M_x$ 的斜对称性，使估计误差与策略扰动的二次型内积严格恒等于零。这一极度巧妙的代数消除机制把策略扰动完全投影到了以真实纳什策略为条件的单侧流形上，省去了构造复杂的点状不确定性置信集。
端到端的末轮自博弈保证：以往博弈优化理论往往只能给出平均策略（Average-Iterate）的时间平均收敛性，而在偏好对齐等实践场景中维护和部署历史平均策略极具挑战。本文通过对数密度比有界性证明了对偶隙局部Lipschitz性，进而为自博弈的最终输出（Last-Iterate）直接确立了统计与优化的双重紧界。
为大模型对齐算法设计解绑沉重约束：在基于人类反馈的纳什对齐（如 NLHF / DPO 变体）实际落地中，工程师常因悲观算法参数繁冗而直接弃用惩罚项。本文从数学上严格论证了这种“工程实践中省去悲观设计”的合理性与最优收敛速率，为极简且具有理论保障的离线对齐提供了坚实支柱。

局限与展望¶

零和博弈与反对称性的强绑定：全文的核心定理高度依赖于零和博弈矩阵的反对称特征（导致二次型消去）。一旦推广到广义和博弈（General-sum Games）或多玩家博弈，算子反对称性将不复存在，如何规避悲观惩罚仍是极具挑战性的开放难题。
函数逼近类的可实现性假设：理论推导依赖于收益函数类存在零近似误差（$g^\star \in \mathcal{G}$），尚未考虑深度神经网络拟合收益时不可避免的模型误设（Model Misspecification）或逼近误差（Approximation Error）。
上下文空间的无偏期望计算开销：自博弈算法中单步收益更新 $\widehat{f}_i^{(t)}(x, a)$ 假设能够对对手策略与转移上下文进行解析积分，在连续动作或高维隐空间中仍需依赖随机小批量采样，需进一步补充随机优化下的噪声扩展分析。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 彻底打破离线博弈必须依赖悲观主义的传统认知，理论推导兼具优雅性与突破性。
实验充分度: ⭐⭐⭐⭐☆ 作为纯理论博弈论文，引理链条严丝合缝、边界完备，但缺乏大规模实证数值验证。
写作质量: ⭐⭐⭐⭐⭐ 逻辑主线极为清晰，符号定义精确，几何直觉与代数技巧阐述透彻。
价值: ⭐⭐⭐⭐⭐ 为离线偏好对齐与博弈决策领域的理论深化与工程去冗余提供了关键的方法论指引。

理论构造模块	理论依赖项	剥离/替换后的退化后果	机制与数学根源说明
反对称消除项 \(\langle \Delta M_x (\widehat{\pi}_x - \pi^\star_x), \widehat{\pi}_x - \pi^\star_x \rangle = 0\)	零和博弈斜对称收益矩阵 \(M_{g,x}\)	估计误差无法限定在单侧偏离，退化为需要全局策略覆盖	失去算子反对称性后，二次交叉扰动项无法消去，迫使引入悲观性以压制未覆盖区域误差
最优响应 Softmax 1-平滑性	对数总和指数函数 \(\Phi(z)\) 的Hessian界	KL散度无法被对数几率 \(\ell_\infty\) 范数二次控制，速率降级	引理2保证了 \(\text{KL} \leq \frac{1}{2}\\|z-z'\\|_\infty^2\)，是获得单侧误差平方项 \(\mathcal{E}(x)^2\) 的数学基石
对数密度比一致有界性 (引理5)	迭代更新与纳什均衡的有界振幅 \(\leq 2\eta\)	对偶隙Lipschitz性失效，产生无穷大梯度或极度退化常数	确保无需假定参考策略的最小动作概率下界，即可实现全局Lipschitz迁移
自博弈衰减步长 \(\alpha_t = \frac{2\eta}{t+2}\)	递减步长时序调度	若固定步长 \(\alpha\)，自博弈只能收敛到极限振荡环或有偏领域	递减步长使得一阶扰动收缩与二阶误差累积达成精确平衡，保证 \(\mathcal{O}(1/\sqrt{T})\) 末轮收敛