Reevaluating Policy Gradient Methods for Imperfect-Information Games¶

会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=vClBDezZUo
代码: IIG-RL-Benchmark / exp-a-spiel
领域: 强化学习 / 博弈论
关键词: 不完美信息博弈, 策略梯度, 可利用度, 自博弈, PPO

一句话总结¶

作者提出"策略梯度假说"——只要调参得当，PPO、PPG 这类通用策略梯度方法在两人零和不完美信息博弈中并不逊于（甚至优于）基于虚拟博弈/双 oracle/反事实遗憾最小化的专用博弈算法；为验证它，他们首次开源了五个大型博弈的精确可利用度计算工具，跑了史上最大规模（7000+ run）的对比实验，结果一边倒地支持该假说。

研究背景与动机¶

领域现状：在两人零和不完美信息博弈（IIG，如扑克、暗棋）里，衡量一个策略好坏的标准化指标是可利用度（exploitability）——最坏情况对手能从你身上榨取多少收益，可利用度为零即纳什均衡。过去十年主流做法是把有收敛保证的表格算法搬到深度强化学习里：虚拟博弈（FP，代表 NFSP）、双 oracle（DO，代表 PSRO）、反事实遗憾最小化（CFR，代表 ESCHER），以及正则化路线（R-NaD）。

现有痛点：这些专用算法各有硬伤。FP/DO 每一轮迭代都要算一次最佳响应（best response），相当于每轮解一整个 RL 问题，且迭代收敛慢；CFR 搬到无模型 RL 需要对轨迹做重要性采样，反馈方差极高，函数逼近器很难学；三者都不具备末迭代（last-iterate）收敛，得额外从历史平均里"提取"策略，工程上很绕。

核心矛盾：与此同时，最简单的"朴素自博弈"被认为在 IIG 里会灾难性失败——不完美信息诱导出循环的最佳响应动态（石头剪刀布式的克制环），单智能体算法直接自博弈往往不收敛、发散甚至给出最大可利用的策略。于是社区形成了一种信念：通用方法（尤其 PPO）在 IIG 里不管用，必须上博弈论味儿更重的算法。PPO 在文献里长期只作为"陪跑的弱 baseline"出现。

切入角度：但 Sokota et al. (2023) 的 magnetic mirror descent（MMD）打破了这个印象——它本质是个策略梯度算法，却在 IIG 里做到了和 CFR 相当的水平。作者顺着 MMD 拆解：MMD 的更新无非干三件事——最大化期望收益、正则化策略、控制更新步长，而这三件事 TRPO/PPO/PPG 早就都在做。既然 MMD 行，凭什么换成同宗同源的通用 PG 就不行？

核心 idea：作者由此正式提出策略梯度假说——"适当调参、与 MMD 同精神（ethos）的通用策略梯度方法，在两人零和 IIG 中可与基于 FP/DO/CFR 的深度 RL 方法竞争甚至超越它们"，并用一套可信的大规模实验去检验它。这不是提新算法，而是一篇"重估 + 立基准"的实证工作。

方法详解¶

整体框架¶

这篇论文的"方法"不是一个新模型，而是一套为了公正检验假说而搭建的实证基础设施 + 实验协议。核心由三块组成：(1) 把假说讲清楚——通过拆解 MMD 与通用 PG 的同构性，论证"它们本该一样好"；(2) 解决检验的拦路虎——大型 IIG 缺乏可获取的精确可利用度计算，作者亲手实现并开源五个大型博弈的精确可利用度；(3) 设计一套无最大化偏差的两阶段实验协议，公平地把 7 个算法放在同一标尺下比，避免"自己人调好通用 PG、随手调专用算法"的偏袒嫌疑。三块环环相扣：没有第二块就没有可信标尺，没有第三块结论就站不住脚。

关键设计¶

1. 策略梯度假说：把 MMD 拆成"通用 PG 三件套"

作者先把 MMD 的更新规则摆出来，再逐项指认它和 PPO 的对应关系，从而论证"通用 PG 本该一样行"。MMD 的更新为

\[\pi_{t+1} = \arg\max_{\pi}\; \mathbb{E}_{A\sim\pi}\, q(A) \;-\; \alpha\,\mathrm{KL}(\pi,\rho)\;-\;\frac{1}{\eta}\,\mathrm{KL}(\pi,\pi_t),\]

其中 \(q(A)\) 是动作价值，\(\alpha\) 是正则温度，\(\eta\) 是步长，\(\rho\) 是"磁铁"策略。三项分别做三件事：\(\mathbb{E}_{A\sim\pi}q(A)\) 最大化期望收益；\(-\alpha\mathrm{KL}(\pi,\rho)\) 正则化更新后的策略（当 \(\rho\) 取均匀分布时近似于熵奖励）；\(-\frac{1}{\eta}\mathrm{KL}(\pi,\pi_t)\) 约束更新步长。作者指出这三件事 TRPO/PPO/PPG 早都在做（最大化价值 + 鼓励熵 + 控制步长），区别仅在细节：MMD 用反向 KL 控步长，而多数 PG 用梯度裁剪 + 前向 KL；在表格精度要求极高时这点差别要紧，但在深度学习里多项工作表明它未必关键。由此推出：MMD 行而通用 PG 在文献里不行，更可能是调参/确认偏误所致，而非方法本质缺陷——这正是假说的逻辑支点。

2. exp-a-spiel：五个大型博弈的精确可利用度计算

检验假说的最大障碍是——大型 IIG 的精确可利用度几乎没有公开可用的实现，连标准库 OpenSpiel 都缺，逼得研究者退而用"小博弈可利用度"或"互相对打的 head-to-head"这两个都不靠谱的代理指标。小博弈（如 Leduc Hold'em）只考验在少数反复访问的信息态上学到近纳什精确解，和大博弈"在海量从未访问过的信息态上学到够强策略"是两回事；head-to-head 又因 IIG 固有的非传递性（石头克剪刀克布克石头）让强弱难解读，且社区没有统一对手无法跨工作比较。作者为此实现了五个大型博弈的精确可利用度：2D5F Liar's Dice、3×3 Dark Hex、Phantom Tic-Tac-Toe、3×3 Abrupt Dark Hex、Abrupt Phantom Tic-Tac-Toe——它们有数百万到上千万信息态（比常报的 Leduc 大几个数量级）。可利用度定义为

\[\mathrm{expl}(\pi)=\frac{\max_{\pi_1'}J(\pi_1',\pi_2)-\min_{\pi_2'}J(\pi_1,\pi_2')}{2},\]

即一个最坏情况对手轮流扮演双方一半时间所能拿到的期望收益。工程上靠序列形式（sequence-form）表示（比显式博弈树紧凑几个数量级）+ 动态生成收益矩阵（避免显式存储）压内存；对 Liar's Dice 利用"动作公开、机会结果独立且在根部"的结构用动态规划线性时间算各公共态收益；对 3×3 系列在前两步后跨线程分布计算、用 18 个缓冲区避开 81 种开局序列的并发冲突。最终在普通硬件上单次可利用度（或 head-to-head）计算约 30–90 秒，并提供 OpenSpiel 兼容的 Python 绑定，让社区可直接复用、验证假说。

3. 两阶段、无最大化偏差的实验协议

因为作者预先就假设专用算法会输，他们在调参上的角色必须经得起审视，否则会被质疑"故意把对手调差"。为此实验设计成两次 launch。第一次是调参 launch：对 5 博弈 × 7 算法的每个组合，测 50 套超参配置，每套跑 3 个种子、1000 万步；超参通过对默认值乘以独立随机采样的 2 的幂来扰动（对上界为 1 的超参改用指数化），网络结构统一固定为 3 层 512 隐单元全连接 + Adam，熵系数对所有通用 PG 统一取 Sokota et al. (2023) 的值。第二次是评估 launch：取第一次里平均末可利用度最低的 5 套配置，换 10 个全新种子重跑——用新种子重评正是为了消除"在调参集上挑出的最优配置"带来的最大化偏差（selection/maximization bias），避免因为是在同一批种子上选出来的而高估性能。同时报告可利用度与 head-to-head 两套结果（head-to-head 取每配置 10 种子里末可利用度中位数较低的策略，并对照用 discounted CFR 算的近似纳什）。整套实验跨 7000 run、350 套超参配置、逾 34.5 万 CPU 小时，是史上最大规模的 IIG 算法可利用度对比。

实验关键数据¶

主实验¶

七个算法（FP 系的 NFSP、DO 系的 PSRO、CFR 系的 ESCHER、正则化的 R-NaD，以及通用 PG：MMD、PPO、PPG）在五个大型博弈上比末可利用度（越低越好）与 head-to-head 期望收益。

类别	代表算法	可利用度表现	结论
通用 PG	MMD / PPO / PPG	最低且三者大致持平	最强
正则化	R-NaD	个别博弈接近通用 PG，通常更差	偏弱
FP 系	NFSP	偶尔接近，多数落后	偏弱
CFR 系	ESCHER	一致地不具竞争力	最弱之一
DO 系	PSRO	大多不行，仅 DH3 偶有成功	最弱之一

head-to-head 结论与可利用度一致：通用 PG 互相打平、对外则打平或击败其余算法。下表摘自 LD2D5F 的 head-to-head（行算法对列算法、各扮一半先手时的期望收益，正数=行更强）：

行\列	MMD	NFSP	ESCHER	PSRO
MMD	0.00	0.09	0.32	0.49
NFSP	-0.09	0.00	0.27	0.46
ESCHER	-0.32	-0.27	0.00	0.34
PSRO	-0.49	-0.46	-0.34	0.00

博弈规模¶

五个基准的体量（说明它们"够大"，与小博弈基准本质不同）：

博弈	状态数	信息态数	纳什值
LD2D5F	235.9M	15.73M	0.0177
DH3	19.12B	6.07M	1.0000
ADH3	29.31B	27.33M	0.3844
PTTT	19.93B	5.99M	0.6667
APTTT	27.12B	23.31M	0.5502

关键发现¶

结论一边倒：FP/DO/CFR 系算法不仅没赢过通用 PG，连同非标准 PG（R-NaD）一起，大体都"不具竞争力"——这超出作者最初"打平"的预期。
通用 PG 内部互相持平：MMD、PPO、PPG 三者难分高下，说明优势来自"通用 PG 这一类精神"而非某个具体算法的特殊设计；反向 KL 与前向 KL/裁剪之争在深度设定下确实不关键。
大博弈 ≠ 小博弈：作者强调在大博弈上拿好成绩考验的是"对海量未访问信息态的泛化"，而非小博弈那种"少数态上逼近精确纳什"，这解释了为何擅长后者的专用算法在这里反而吃亏。

亮点与洞察¶

"拆解同构性"是最巧的一步：把 MMD 写成"最大化价值 + 正则 + 控步长"，再指认 PPO 早就这么干，一句话就把"为什么 MMD 行而 PPO 不行"的迷思变成可证伪的假说——动机具体、逻辑闭环，不靠玄学。
基础设施即贡献：很多 IIG 工作卡在"无法精确度量"，作者直接把五个大型博弈的精确可利用度算到普通机器 30–90 秒可跑并开源，这件工具本身就能让整个领域的对比从"各说各话"变得可复现可比较。
对"调 baseline 不公"的自我防御：用"调参 launch + 换种子评估 launch"消除最大化偏差，外加公开全部超参与代码，把"你是不是故意把对手调差"这种最致命的质疑提前堵死，这种实验诚信的设计值得迁移到任何"重估旧方法"的工作里。
可迁移的方法论：当一个领域里"某类方法被默认不行"时，先找一个反例（MMD），再把反例与被嫌弃的方法做结构对齐，往往能揭示"不行"其实源于调参/确认偏误而非本质——这套路适用于任何 baseline 被系统性低估的子领域。

局限与展望¶

博弈数量与同质性：只在五个博弈上做，其中四个（暗棋/幻影井字棋的变体）相当同质；作者明确不认为这种相对排名能推广到所有 IIG，甚至这五个之间都不完全一致。
每类算法只取一个代表：FP 只测原版 NFSP、DO 只测原版 PSRO、CFR 只测最新的 ESCHER，而文献里这些算法（尤其 PSRO）有几十个变体，某个变体完全可能带来关键改进、翻盘当前结论。
实验条件特定：结果绑定于他们选的默认超参、扰动方式、调参手段，以及"1000 万步"这个预算。预备实验显示所有算法在 1000 万步后可利用度仍在下降——专用算法也许需要更多步数、或离默认值多个数量级的超参、或不同的类别型超参（本文未调）才能发挥，因此不应被解读为各算法的最优表现。
诚实的克制：作者反复声明"并未证明假说为真"，只是给出强证据——这种克制反而增强了说服力。

评分¶

新颖性: ⭐⭐⭐⭐ 不提新算法，但把"通用 PG 在 IIG 里不行"的领域共识系统性证伪，且配套开源大型博弈精确可利用度，视角与基础设施都有价值
实验充分度: ⭐⭐⭐⭐⭐ 7000+ run、350 套超参、34.5 万 CPU 小时、双阶段无偏协议，是史上最大规模 IIG 可利用度对比
写作质量: ⭐⭐⭐⭐⭐ 假说—检验逻辑清晰，对自身调参角色与局限极其坦诚，自我防御严谨
价值: ⭐⭐⭐⭐⭐ 既可能让从业者改用更简洁的 PG 实现，又给社区留下可复现的评测工具，影响面广