并行化反事实遗憾最小化

# 并行化反事实遗憾最小化
来源：https://arxiv.org/html/2605.14277
Juho Kim 计算机科学系 卡内基梅隆大学 juhok@cs\.cmu\.edu  & Tuomas Sandholm 计算机科学系，卡内基梅隆大学 Strategic Machine，Inc\. Strategy Robot，Inc\. Optimized Markets，Inc\. sandholm@cs\.cmu\.edu

###### 摘要

并行化在人工智能（AI）领域发挥了关键作用，大幅缩短了训练和评估大型AI模型所需的时间。然而，与并行化在AI广泛领域中的影响形成鲜明对比的是，它在计算博弈求解中的应用相对较少被探索，尽管其潜力巨大。在本文中，我们并行化了反事实遗憾最小化（CFR）算法家族，该算法是解决大规模不完美信息博弈的重要突破的核心。我们提出了一个通用的并行化框架，将CFR重新表述为一系列线性代数运算。然后，可以将现有的并行化线性代数运算技术应用于加速CFR。我们还描述了如何将该技术应用于CFR算法家族中的其他表格型成员，包括最先进的变体，如CFR+、折扣CFR和预测性CFR变体。实验表明，我们在GPU上的CFR实现比Google DeepMind OpenSpiel在CPU上的CFR实现快了高达四个数量级。

## 1 引言

从历史上看，并行化是人工智能（AI）领域的关键推动力[9 (https://arxiv.org/html/2605.14277#bib.bib52),16 (https://arxiv.org/html/2605.14277#bib.bib53),30 (https://arxiv.org/html/2605.14277#bib.bib54)]，它通过将问题拆分为更小的子问题并发求解，大幅减少了研究人员在大型数据集上训练大型AI模型所需的时间。与串行执行相比，这种训练时间的大幅缩减也加速了假设检验的速度。事后看来，如果没有并行化，AI模型在众多实际应用中性能和能力的爆炸式增长将是不可能的。

与并行化在AI领域的广泛影响形成鲜明对比的是，它在计算博弈求解领域的探索相对较少，尽管并行化的必要性在解决大型博弈的过去里程碑式工作中已经得到充分证明，例如Cepheus[31 (https://arxiv.org/html/2605.14277#bib.bib17)]、Libratus[5 (https://arxiv.org/html/2605.14277#bib.bib47)]和Pluribus[6 (https://arxiv.org/html/2605.14277#bib.bib18)]都利用了某种形式的并行化。由于所涉博弈的规模庞大，如果没有并行化，开发这些AI智能体将是不现实的。此外，即使在更常规的博弈求解任务中，也有充分的理由应用并行化。实际上，我们将在后面展示，许多博弈，甚至那些常用作博弈求解算法基准的博弈，都提供了大量的并行化空间，利用它可以实现数个数量级的加速。因此，利用这一点将使该领域的研究人员能够更快地测试其理论结果、假设或超参数设置。

在计算博弈理论中，反事实遗憾最小化（CFR）算法家族[37 (https://arxiv.org/html/2605.14277#bib.bib1)]已被用于开发大规模不完美信息博弈的AI智能体，最著名的是扑克[31 (https://arxiv.org/html/2605.14277#bib.bib17),25 (https://arxiv.org/html/2605.14277#bib.bib20),6 (https://arxiv.org/html/2605.14277#bib.bib18),8 (https://arxiv.org/html/2605.14277#bib.bib19)]。此后，研究人员提出了CFR的各种变体，以改进其收敛速度[32 (https://arxiv.org/html/2605.14277#bib.bib2),7 (https://arxiv.org/html/2605.14277#bib.bib4),12 (https://arxiv.org/html/2605.14277#bib.bib38),34 (https://arxiv.org/html/2605.14277#bib.bib5),35 (https://arxiv.org/html/2605.14277#bib.bib57),36 (https://arxiv.org/html/2605.14277#bib.bib56)]、利用蒙特卡洛展开[23 (https://arxiv.org/html/2605.14277#bib.bib16)]，以及融入深度学习[3 (https://arxiv.org/html/2605.14277#bib.bib28),24 (https://arxiv.org/html/2605.14277#bib.bib29)]。在本文中，我们提出了一个通用的并行化框架，将CFR及其变体重新视为一系列线性代数运算。然后，我们可以应用标准的线性代数并行化技术来并行化CFR及其变体。虽然我们的框架不一定能增加可求解博弈的规模，但实验表明，它可以显著加快在这些博弈中找到最优解的速度。我们的实验涉及七个不同规模的博弈，结果显示，我们在GPU上的并行化实现分别比Google DeepMind OpenSpiel在CPU上的Python和C++实现快高达约18,889倍和3,413倍。加速比随着所求解博弈规模的增大而变得更加显著。

## 2 符号与背景

本节定义本文使用的符号，并回顾CFR。

### 2.1 序列形式CFR

在本文中，我们考虑并行化序列形式[33 (https://arxiv.org/html/2605.14277#bib.bib43),20 (https://arxiv.org/html/2605.14277#bib.bib42),10 (https://arxiv.org/html/2605.14277#bib.bib31)]的CFR，而不是其经典版本[37 (https://arxiv.org/html/2605.14277#bib.bib1)]。注意，经典CFR和序列形式CFR是等价的，因为它们产生相同的迭代结果，因此并行化序列形式CFR也间接地并行化了经典CFR。关于这一选择，我们将在后面的讨论中给出更多细节。

在序列形式版本中，每个玩家运行CFR来最小化其对应的树形序贯决策过程（TFSDP）的反事实遗憾，该过程源自博弈树。在TFSDP中，每个节点p∈P要么是决策点集J，要么是观测点集K，要么是决策过程的终点⊥。在决策点j处，可以采取可用动作a∈A_j，并用ρ(j,a)表示在j处应用a所到达的子节点。类似地，在观测点k处可以观察到信号s∈S_k，对应的子节点表示为ρ(k,s)。

在每个决策点j处，一个局部遗憾最小化器R_j混合可用动作集A_j。理论上，任何在概率单纯形上操作的遗憾最小化算法都可以用作遗憾最小化器。局部上，CFR使用了遗憾匹配（RM）[17 (https://arxiv.org/html/2605.14277#bib.bib8)]，它在每次迭代中将L1归一化的取底遗憾输出为概率。其他流行的选择包括RM+（用于CFR+[32 (https://arxiv.org/html/2605.14277#bib.bib2)]）、折扣RM（用于折扣CFR (DCFR)[7 (https://arxiv.org/html/2605.14277#bib.bib4)]）以及预测性RM (PRM)（分别对应PRM+，用于预测性CFR (PCFR)（分别对应PCFR+）[12 (https://arxiv.org/html/2605.14277#bib.bib38)]）。

令Σ^+ = {(j,a): ∀j∈J, a∈A_j} 为非空序列的集合，Σ = Σ^+ ∪ {∅} 为（可能为空的）序列的集合。这里，我们用∅表示空序列。设p_j为决策点j的父序列，则可以定义序列形式多面体如下：

X = {x→ ∈ R≥0^Σ: x→[∅]=1, ∀j∈J: ∑_{a∈A_j} x→[(j,a)] = x→[p_j]}.

CFR算法家族是一类在序列形式多面体上操作的遗憾最小化器。在每次迭代t，CFR从其局部遗憾最小化器的输出构建一个行为策略b→_j^(t) ∈ Δ(A_j) ∀j∈J，然后将其转换为序列形式策略x→^(t) ∈ X，再返回。我们将这个过程称为NextStrategy。然后，CFR观察效用u→^(t) ∈ R^Σ，该效用被转换为反事实效用u→_j^(t) ∈ R^{A_j} ∀j∈J，并传递给其局部遗憾最小化器。下文中，我们将此过程称为ObserveUtility。序列形式CFR的完整伪代码描述见算法1 (https://arxiv.org/html/2605.14277#algorithm1)。在算法1 (https://arxiv.org/html/2605.14277#algorithm1)的第1行，我们假定当‖(r→_j^(t-1))^+‖_1 = 0时，标量除法 (//) 产生一个任意策略。

一个玩家实例的序列形式CFR的每迭代时间复杂度相对于该玩家对应TFSDP的大小是线性的。这与经典CFR[37 (https://arxiv.org/html/2605.14277#bib.bib1)]的每迭代时间复杂度不同：经典CFR相对于博弈树的大小是线性的。博弈树中的节点数通常（但并非总是）大于其所有玩家TFSDP中的节点总数，因此序列形式CFR的树遍历部分通常比经典CFR更高效。

也就是说，与经典CFR不同，序列形式CFR需要额外一步，即在每次迭代中计算每个玩家的效用，其最坏情况时间复杂度相对于博弈树的大小是线性的。然而，在双人设置中，可以通过稀疏矩阵-向量乘法（或在多人设置中通过张量运算）来实现这一目的，这在实践中具有较小的常数因子，并且易于并行化。因此，在实践中，序列形式CFR往往比经典CFR实现产生性能改进。

### 2.2 并行化博弈求解器

Reis [28 (https://arxiv.org/html/2605.14277#bib.bib24)] 和 Rudolf [29 (https://arxiv.org/html/2605.14277#bib.bib25)] 未发表的工作在CUDA上并行化了CFR，并发现了数量级的加速。然而，在Rudolf的工作中，线程被分配给每个节点，然后线程向上遍历树；在最坏情况下，这会导致二次时间的工作量。这与CFR的线性时间复杂度形成对比。Reis的工作存在几个可重复性问题（例如，代码库无法访问，代码片段包含语法错误）。两种实现都要求每个线程执行“大量控制流语句”[28 (https://arxiv.org/html/2605.14277#bib.bib24)]和通用内核指令。

相反，我们在框架中将CFR重新表述为线性代数运算。并行化线性代数运算在系统领域是一个研究充分的问题，并且经常可以利用优化的操作码。由于我们的方法独立于平台，它也比上述方法更通用。此外，与Reis的方法不同，我们的实现是开源的，并且兼容OpenSpiel[22 (https://arxiv.org/html/2605.14277#bib.bib6)]中的博弈，OpenSpiel是一个流行的博弈论原语软件库。

另一个值得注意的博弈求解算法是用于求解扩展形式博弈的过度间隙技术（EGT）[26 (https://arxiv.org/html/2605.14277#bib.bib48)]的改编版[14 (https://arxiv.org/html/2605.14277#bib.bib49)]。Hoda等人[18 (https://arxiv.org/html/2605.14277#bib.bib50)]将内存占用减少为原来的平方根，而Gilpin和Sandholm [15 (https://arxiv.org/html/2605.14277#bib.bib51)]引入采样以加速。两者都并行化了期望效用计算中的矩阵-向量乘积以实现加速（这类似于计算传递给序列形式CFR的效用）。此外，Kroer等人[21 (https://arxiv.org/html/2605.14277#bib.bib41)]引入了EGT的GPU实现，但他们利用扑克TFSDP的独特拓扑结构，仅跨TFSDP根节点的直接子节点进行并行化，这可能会限制一般的并行性，尤其是在根节点子节点很少的情况下。

并行化在多次不完美信息博弈求解的突破中发挥了关键作用，包括Libratus[6 (https://arxiv.org/html/2605.14277#bib.bib18)]和Cepheus[31 (https://arxiv.org/html/2605.14277#bib.bib17)]——超人级或近乎最优的头对头德州扑克智能体。我们首先讨论Libratus中使用的架构。在其蓝图策略计算期间，Libratus的工作负载（通常）分布在1 + 195个计算节点上，具体取决于牌局展开。然而，Libratus使用的CFR变体——蒙特卡洛CFR (MCCFR)[23 (https://arxiv.org/html/2605.14277#bib.bib16)]是一个随机遗憾最小化器[11 (https://arxiv.org/html/2605.14277#bib.bib40)]。由于它在随机遗憾最小化设置下运行，其并行化方案不能直接适用于CFR或其表格型变体。

相比之下，Cepheus的工程涉及并行化CFR+，这是表格型的。在博弈求解过程中，Cepheus将头对头有限注德州扑克在第二个下注轮之后分割为一个主干和多个子博弈。然后，子树被分配给唯一的计算节点。在每次迭代中，主干节点将概率发送给子树计算节点，子树节点再将值返回给主干节点，以便主干完成其计算。这里，子树节点等待主干节点发送概率，而主干节点挂起直到子树计算完成。我们的并行化方案与Cepheus的主要不同之处在于：a) 我们在每个深度上有效地分割博弈，从而可能获得更高的并行度；b) 我们提供了一个领域无关的并行化框架。最重要的是，我们的贡献与Cepheus的架构并不互斥：可以将我们的技术增强到Cepheus中以实现进一步的并行化。

## 3 并行化CFR及其表格型变体

---
1 输入一个TFSDP。

21ex NextStrategy()():
//计算行为策略
3 for *每个决策点 j∈J* do
4 Δ(A_j) ∋ b→_j^(t) ≔ (r→_j^(t-1))^+ / ‖(r→_j^(t-1))^+‖_1;
5
//转换为序列形式
6 x→^(t)[∅] ≔ 1;
7 for *每个决策点 j∈J, 自顶向下* do
8 for *每个动作 a∈A_j* do
9 x→^(t)[(j,a)] ≔ x→^(t)[p_j] ⋅ b→_j^(t)[a];
10
11 返回 x→^(t) ∈ X;
12
131ex ObserveUtility(u→^(t) ∈ R^Σ):
//记忆化反事实效用
14 v→^(t) ≔ 0→ ∈ R^P;
15 for *每个节点 p∈P, 自底向上* do
16 if J ∋ j ≔ p then
17 v→^(t)[j] ≔ ∑_{a∈A_j} b_j^(t)[a] ⋅ (u→^(t)[(j,a)] + v→^(t)[ρ(j,a)]);