跳转至

No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding

会议: AAAI 2026
arXiv: 2511.12083
代码: https://github.com/PhilEnchan/EmbeddingCFR
领域: LLM/NLP
关键词: 博弈论, CFR, 信息集抽象, 嵌入空间, 扑克AI

一句话总结

提出 Embedding CFR 算法，将不完美信息博弈中的信息集映射到连续低维嵌入空间（而非离散聚类），在相同空间开销下实现更快的可利用性收敛和更高质量的策略求解。

研究背景与动机

在无限注德州扑克等大规模不完美信息博弈中，信息集数量巨大（\(\approx 10^{13}\)），直接用 CFR（反事实遗憾最小化）求解 Nash 均衡在空间上完全不可行。主流方法采用"抽象-求解-翻译"范式：先将相似信息集聚类到离散等价类中，在抽象博弈上求解，再映射回原博弈。

现有聚类方法的核心问题：硬分类带来二元性困境。例如两手牌 9♠A♠ 和 T♠A♠ 在翻牌后虽然都是对子，但后者可组成顺子同花而前者只能组成同花。将它们放入同一聚类会忽略关键差异，分开则浪费了共享策略的潜力。这种离散分类不可逆地丢失了信息集之间的细微区别。

切入角度：受 NLP 中词嵌入的启发——词嵌入用连续向量表示词的语义关系，类似地，可以将每个信息集映射到低维连续空间中的概率分布向量，既保留相似信息集间的策略相关性，又保持细微差异。

方法详解

整体框架

Embedding CFR 分两步：（1）预训练一个嵌入网络（HandEbdNet）将每手牌映射为 m 维概率分布向量（嵌入坐标）；（2）在嵌入空间中运行类似 CFR 的遗憾累积和策略更新，最终通过嵌入矩阵映射回原空间。

关键设计

  1. 扩展信息集抽象（Extended Information Set Abstraction）
  2. 引入"顾问（advisor）"概念：每个 info-block 关联 m 个顾问，每个顾问维护一个统一策略
  3. 信息集 \(I_q\) 的策略由所有顾问策略的加权聚合给出：\(\sigma(I_q, a) = \sum_p \phi_{p,q} \cdot \sigma(e_p, a)\)
  4. 权重 \(\phi_{p,q}\) 就是嵌入坐标，形成嵌入矩阵 \(\Phi\)
  5. 空间复杂度从 \(O(n \cdot |A|)\) 降到 \(O(m \cdot |A|)\)（\(m \ll n\)）

  6. 与传统抽象的统一关系：当每个信息集只信任一个顾问（\(\phi_{p,q} \in \{0,1\}\)）时退化为传统离散聚类

  7. 嵌入空间中的遗憾驱动机制

  8. 原空间的即时反事实遗憾通过 \(\Phi\) 投影到嵌入空间：\(r^T(\mathbf{E}, a) = \Phi \cdot r^T(\mathbf{J}, a)\)
  9. 在嵌入空间中用 regret matching 更新顾问策略
  10. 通过 \(\Phi^\top\) 映射回原空间的策略：\(\sigma_i^T(\mathbf{J}, a) = \Phi^\top \sigma_i^T(\mathbf{E}, a)\)

  11. 采样机制：每次迭代只激活一个子集的信息集，保持实际空间复杂度为 \(O(m)\)

  12. HandEbdNet 嵌入网络

  13. 输入：手牌张量（编码花色、点数、所属轮次）
  14. 输出：手牌强度张量（各轮次的胜率分布）
  15. 中间层：手牌特征编码器 → m 维向量 → softmax → 概率分布作为嵌入坐标
  16. 核心洞察：牌力相似的手牌自然获得相近的嵌入坐标，从而在策略更新中相互影响
  17. 训练方式：用手牌强度（胜率分布）作为监督信号预训练，训练完成后固定参数，在策略求解阶段作为查询器使用

损失函数 / 训练策略

HandEbdNet 用手牌强度（胜率分布）作为监督信号训练。策略求解阶段无额外损失函数，靠遗憾最小化机制驱动收敛。理论分析证明单个顾问独立作用时，其嵌入累积遗憾满足递减性质。

实验关键数据

主实验（Numeral211 Hold'em）

方法 1024轮迭代后可利用性 (mb/g) 特点
EHS ~较高 经典期望手牌强度聚类
PaEmd (Libratus使用) ~较高 势感知聚类，SOTA
KrwEmd ~较高 基于历史轨迹的聚类
Embedding CFR 显著最低 连续嵌入空间策略求解

关键发现

  • 在相同空间开销下，Embedding CFR 的可利用性收敛速度显著优于所有聚类方法（EHS、PaEmd、KrwEmd 性能相当但明显逊于 Embedding CFR）
  • 三种聚类方法虽然策略不同，但在抽象粒度相同时表现相近——说明瓶颈在于离散聚类范式本身，而非具体聚类算法
  • 嵌入坐标的概率分布表示使得相似手牌的策略自然相近，无需硬边界
  • 在 1024 轮迭代后，Embedding CFR 的可利用性约为聚类方法的 60-70%，差距随迭代数增加持续扩大
  • 采样+查询机制在 m=50 维嵌入下，每轮迭代的实际空间开销仅为 \(O(50 \cdot |A|)\)，与聚类方法的 50 个桶等价但策略质量显著更高

亮点与洞察

  • NLP 词嵌入思想迁移到博弈论：词嵌入解决了词的离散表示问题，Embedding CFR 解决了信息集的离散聚类问题，这个类比非常优雅
  • 采样+查询机制保持低空间复杂度：不需要存储完整嵌入矩阵，而是通过神经网络动态生成嵌入坐标，巧妙解决了大规模博弈的存储瓶颈
  • Info-block 按非机会动作分区：利用扑克的完美回忆性质，使得共享相同非机会动作序列的 info-block 可以复用同一嵌入矩阵

局限性 / 可改进方向

  • 收敛性分析仅证明了单个顾问独立作用时的遗憾递减，多顾问相互耦合时的收敛保证仍是开放问题
  • 实验仅在 Numeral211 Hold'em（简化变体）上验证，未扩展到完整的无限注德州扑克
  • 嵌入维度 m 的选择对性能的影响未做系统消融
  • HandEbdNet 依赖领域知识（手牌强度）作为监督信号，能否无监督学习嵌入？
  • 目前仅在两人零和博弈中验证，多人非零和博弈中的适用性未知
  • 嵌入坐标的稀疏性是否可以利用？从信息论角度分析嵌入的最优维度是有价值的后续工作

相关工作与启发

  • vs PaEmd (Libratus)：PaEmd 是 Libratus 使用的 SOTA 聚类方法，但受限于离散聚类的信息丢失；Embedding CFR 在相同资源下策略质量显著更优
  • vs Deep CFR (Brown 2019)：Deep CFR 用神经网络估计遗憾值但需要与环境交互学习；Embedding CFR 利用预训练嵌入+领域知识，在已知模型场景下更高效
  • vs RL-CFR：RL-CFR 用强化学习做在线动作抽象；Embedding CFR 做的是信息集抽象，两者互补
  • 启发：嵌入方法可推广到其他需要抽象的博弈场景，如拍卖设计、安全博弈等

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 将嵌入思想引入博弈论信息集抽象是全新的范式突破
  • 实验充分度: ⭐⭐⭐ 仅在简化扑克上验证，未扩展到完整规模博弈
  • 写作质量: ⭐⭐⭐⭐ 数学推导严谨，图示清晰直观
  • 价值: ⭐⭐⭐⭐ 为大规模不完美信息博弈的求解开辟了新方向

补充说明

  • 该工作的方法论和实验设计对相关领域有参考价值
  • 后续工作可在更多场景和更大规模上验证方法的泛化性和可扩展性
  • 与近期相关工作的结合（如与 RL/MCTS/多模态方法的交叉）有潜在研究价值