AiPaper
论文状态:已完成

Stable-Predictive Optimistic Counterfactual Regret Minimization

发表:2019/02/14
原文链接PDF 下载
价格:0.10
价格:0.10
已有 2 人读过
本分析由 AI 生成,可能不完全准确,请以原文为准。

TL;DR 精炼摘要

本文提出了一种新型的反事实遗憾最小化(CFR)变体,显著提高了大规模扩展形式博弈(Nash均衡)的收敛速率,达到了$O(T^{-3/4})$。通过结合预测性和稳定性遗憾最小化的进展,引入"稳定-预测性"概念,为决策树中的每个最小化器设置了稳定性,使算法表现优于传统CFR。

摘要

The CFR framework has been a powerful tool for solving large-scale extensive-form games in practice. However, the theoretical rate at which past CFR-based algorithms converge to the Nash equilibrium is on the order of O(T1/2)O(T^{-1/2}), where TT is the number of iterations. In contrast, first-order methods can be used to achieve a O(T1)O(T^{-1}) dependence on iterations, yet these methods have been less successful in practice. In this work we present the first CFR variant that breaks the square-root dependence on iterations. By combining and extending recent advances on predictive and stable regret minimizers for the matrix-game setting we show that it is possible to leverage "optimistic" regret minimizers to achieve a O(T3/4)O(T^{-3/4}) convergence rate within CFR. This is achieved by introducing a new notion of stable-predictivity, and by setting the stability of each counterfactual regret minimizer relative to its location in the decision tree. Experiments show that this method is faster than the original CFR algorithm, although not as fast as newer variants, in spite of their worst-case O(T1/2)O(T^{-1/2}) dependence on iterations.

思维导图

论文精读

中文精读

1. 论文基本信息

1.1. 标题

稳定-预测性乐观反事实遗憾最小化 (Stable-Predictive Optimistic Counterfactual Regret Minimization)

1.2. 作者

  • Gabriele Farina (卡内基梅隆大学计算机科学系)
  • Christian Kroer (哥伦比亚大学工业工程与运筹学系)
  • Noam Brown (卡内基梅隆大学计算机科学系)
  • Tuomas Sandholm (卡内基梅隆大学计算机科学系)

1.3. 发表期刊/会议

该论文以预印本 (Arxiv Preprint) 的形式发布,表明其研究成果在提交正式期刊/会议审稿前已经公开。在人工智能和机器学习领域,arXiv 预印本是研究成果快速传播和交流的重要平台。

1.4. 发表年份

2019年2月14日发布于 arXiv。

1.5. 摘要

反事实遗憾最小化 (Counterfactual Regret Minimization, CFR) 框架在实践中一直是解决大规模扩展形式博弈 (extensive-form games, EFGs) 的强大工具。然而,过去基于 CFR 的算法收敛到纳什均衡 (Nash equilibrium) 的理论速率约为 O(T1/2)O(T^{-1/2}),其中 TT 是迭代次数。相比之下,一阶方法 (first-order methods) 可以实现 O(T1)O(T^{-1}) 的迭代依赖性,但这些方法在实践中并不那么成功。在这项工作中,我们提出了第一个打破迭代平方根依赖的 CFR 变体。通过结合并扩展矩阵博弈设置中预测性 (predictive) 和稳定 (stable) 遗憾最小化器 (regret minimizers) 的最新进展,我们展示了利用“乐观 (optimistic)”遗憾最小化器可以在 CFR 框架内实现 O(T3/4)O(T^{-3/4}) 的收敛速率。这通过引入一个名为 stable-predictivity 的新概念,并根据每个反事实遗憾最小化器在决策树中的位置来设置其稳定性来实现。实验结果表明,尽管该方法不如新变体快(尽管它们的理论最差收敛速率为 O(T1/2)O(T^{-1/2})),但它比原始的 CFR 算法更快。

1.6. 原文链接

2. 整体概括

2.1. 研究背景与动机

论文试图解决的核心问题是什么? 论文主要关注的是反事实遗憾最小化 (CFR) 框架在解决大规模扩展形式博弈 (EFGs) 时的理论收敛速率问题。尽管 CFR 及其变体(如 CFR+CFR+Discounted CFR)在实践中非常成功,尤其是在扑克等基准领域,但其理论最差收敛速率仅为 O(T1/2)O(T^{-1/2}),其中 TT 是迭代次数。相比之下,一些一阶方法 (first-order methods) 可以在理论上达到更快的 O(T1)O(T^{-1}) 收敛速率,但这些方法在实践中往往表现不佳。这在理论和实践之间造成了一个显著的差距。

为什么这个问题在当前领域是重要的?现有研究存在哪些具体的挑战或空白 (Gap)?

  1. 理论与实践的鸿沟: CFR 算法在实践中的出色表现(例如,在扑克领域战胜人类顶尖玩家的 AI Libratus)与其较慢的理论收敛速率形成鲜明对比。这种鸿沟使得研究人员难以完全理解其成功的原因,也限制了理论指导实践的潜力。
  2. 加速大规模博弈求解: 扩展形式博弈,尤其是像无限注德州扑克 (no-limit Texas hold'em poker) 这样具有巨大状态空间的博弈,求解纳什均衡 (Nash equilibrium) 是一个计算密集型任务。提高收敛速率意味着可以在更短的时间内找到更高质量的近似均衡策略,这对于现实世界的应用(如 AI 训练和部署)至关重要。
  3. 预测性学习的潜力: 近年来,在矩阵博弈 (matrix games) 设置中,乐观学习 (optimistic learning)预测性遗憾最小化 (predictive regret minimization) 的思想被证明可以显著加速收敛,达到 O(T1)O(T^{-1}) 甚至更好的理论速率。将这些高级的遗憾最小化技术引入到 CFR 框架中,有望打破 CFR 固有的收敛瓶颈。

这篇论文的切入点或创新思路是什么? 论文的创新切入点在于,它首次将矩阵博弈中 预测性 (predictive)稳定 (stable) 遗憾最小化器的概念,严格地扩展并集成到 CFR 框架中,以期提高其理论收敛速率。具体来说,它通过以下方式实现了这一目标:

  1. 引入 stable-predictivity 定义了一个新的遗憾最小化器类别,该类别不仅要求预测误差对遗憾影响小,而且要求决策迭代之间的变化缓慢(稳定性)。
  2. 构建 乐观反事实遗憾最小化器乐观跟随正则化领导者 (Optimistic Follow-the-Regularized-Leader, OFTRL) 等乐观遗憾最小化器作为 CFR 框架中每个信息集 (information set) 的局部遗憾最小化器。
  3. 分层稳定性设置: 关键在于,根据每个局部遗憾最小化器在决策树中的位置(深度)来设置其稳定性参数,从而在整个扩展形式博弈的策略空间中保持预测性和稳定性。

2.2. 核心贡献/主要发现

论文最主要的贡献是什么?

  1. 打破 CFR 固有收敛障碍: 首次提出了一个 CFR 变体,其理论收敛速率优于传统的 O(T1/2)O(T^{-1/2}),达到了 O(T3/4)O(T^{-3/4})。这是该领域的一个重要理论突破,缩小了 CFR 与一阶方法在理论速率上的差距。
  2. 引入 stable-predictivity 新概念: 定义了一种新的遗憾最小化器特性,结合了预测性和稳定性,并证明了 OFTRL 算法满足这一特性。
  3. 分层稳定性的设计: 提出了一种在扩展形式博弈的决策树结构中,根据节点位置设置局部遗憾最小化器稳定性参数的机制,这对于在复杂的树状结构中保持整体算法的加速收敛至关重要。
  4. 连接矩阵博弈与扩展形式博弈: 成功地将矩阵博弈中先进的乐观遗憾最小化理论与 CFR 框架相结合,为在更复杂的博弈形式中应用这些技术奠定了基础。

论文得出了哪些关键的结论或发现?这些发现解决了什么具体问题?

  1. 理论收敛速率提升: 论文通过数学证明,证实了提出的 Stable-Predictive Optimistic Counterfactual Regret Minimization 算法可以达到 O(T3/4)O(T^{-3/4}) 的纳什均衡近似速率。这解决了 CFR 理论速率慢于一阶方法的长期问题。
  2. 实践表现: 实验表明,尽管在理论上优于原始 CFR,但在 Libratus AI 使用的无限注德州扑克子博弈中,该方法(尤其是经过理论推导的步长参数设置)在某些情况下不如 Discounted CFR (DCFR)。这凸显了理论最差情况分析与实际启发式算法在实践中表现之间的差异,也暗示了在实际应用中,步长参数调优的重要性。在某些子博弈中,经过调优的 OFTRL 变体能够显著优于 CFR
  3. 对未来研究的启示: 论文为理解和设计更快收敛的 CFR 算法提供了新的理论基础和方向。它明确指出了一个挑战:如何在实践中找到既能保持理论保证又能达到更优性能的算法变体。

3. 预备知识与相关工作

本节将为理解论文的核心概念和技术演进提供必要的背景知识。

3.1. 基础概念

3.1.1. 扩展形式博弈 (Extensive-Form Games, EFGs)

扩展形式博弈 (EFGs) 是一种用于建模序列决策和不完全信息 (imperfect information) 博弈的数学框架。它通常用一棵树来表示,其中每个节点代表一个博弈状态,边代表玩家的行动。

  • 决策节点 (Decision Nodes): 玩家在此处做出选择。
  • 观察节点 (Observation Nodes): 玩家在此处接收来自环境的信号或观察结果。
  • 不完全信息 (Imperfect Information): 玩家在做决策时,可能无法完全了解博弈的全部历史或对手的私有信息(例如,扑克中的手牌)。这通过将多个决策节点分组到同一个 信息集 (information set) 来表示,这意味着玩家在这些节点时无法区分它们。
  • 完美回忆 (Perfect Recall): 玩家不会忘记过去的行动或观察结果。

3.1.2. 纳什均衡 (Nash Equilibrium)

在博弈论中,纳什均衡 (Nash Equilibrium) 是一个策略组合,其中每个玩家的策略都是在给定其他玩家策略的情况下,对自己最优的响应。这意味着,如果所有其他玩家都坚持其纳什均衡策略,任何玩家都没有动机单方面改变自己的策略。在零和博弈 (zero-sum games) 中,纳什均衡通常对应于博弈的值 (value of the game)。

3.1.3. 遗憾最小化 (Regret Minimization)

遗憾最小化 (Regret Minimization) 是一类在线学习算法的目标,旨在使代理 (agent) 的累积遗憾 (cumulative regret) 随时间增长得尽可能慢。累积遗憾定义为代理所遭受的累积损失与如果它在所有时间步都选择了最好的固定策略所能遭受的最小累积损失之间的差异。 形式上,对于一个决策序列 x1,,xTx^1, \dots, x^T 和损失序列 1,,T\ell^1, \dots, \ell^T,累积遗憾 RTR^T 为: RT:=t=1Tt,xtminx~X{t=1Tt,x~} R^T := \sum_{t=1}^T \langle \ell^t, x^t \rangle - \min_{\tilde{x} \in \mathcal{X}} \left\{ \sum_{t=1}^T \langle \ell^t, \tilde{x} \rangle \right\} 其中 xtx^t 是在时间 tt 做出的决策,t\ell^t 是相应的损失向量,X\mathcal{X} 是可行决策空间,x~\tilde{x} 是在所有时间步都选择的最好的固定决策。

3.1.4. 收敛速率 (Convergence Rate)

收敛速率 (Convergence Rate) 描述了算法如何快速地接近其最优解。在遗憾最小化和博弈论求解中,它通常表示为累积遗憾或鞍点残差 (saddle-point residual) 随迭代次数 TT 增长的渐近上限。

  • O(T1/2)O(T^{-1/2}):表示遗憾或残差以 1/T1/\sqrt{T} 的速度收敛,是许多经典在线学习算法的典型速率。
  • O(T1)O(T^{-1}):表示遗憾或残差以 1/T1/T 的速度收敛,通常被称为“快速收敛”,在凸优化中可以由一阶方法达到。
  • O(T3/4)O(T^{-3/4}):介于 O(T1/2)O(T^{-1/2})O(T1)O(T^{-1}) 之间,比前者快,但比后者慢。本文旨在达到这一速率。

3.1.5. 一阶方法 (First-Order Methods)

一阶方法 (First-Order Methods) 是一类优化算法,它们主要利用目标函数的一阶导数(梯度)信息来迭代更新决策变量。它们通常适用于大规模问题,因为每次迭代的计算成本相对较低。

  • 过度间隙技术 (Excessive Gap Technique) (Nesterov, 2005):一种用于非光滑凸优化的加速方法。
  • 镜像近端算法 (Mirror Prox) (Nemirovski, 2004):一种求解变分不等式和光滑凸凹鞍点问题的有效算法,也常用于求解博弈论问题。

3.1.6. 在线凸优化 (Online Convex Optimization, OCO)

在线凸优化 (OCO) 是一个通用的在线学习框架,其中学习者在每个时间步做出一个决策,然后观察到一个凸损失函数并遭受损失。学习者的目标是最小化累积遗憾。本文的 预测性遗憾最小化OCO 的一个子主题。

3.1.7. 预测性/乐观遗憾最小化 (Predictive/Optimistic Regret Minimization)

预测性遗憾最小化 (Predictive Regret Minimization)(也常称为 乐观遗憾最小化 (Optimistic Regret Minimization))是 OCO 的一个变体,其中决策者在做出当前决策之前,可以获得下一个损失向量的预测。这些预测不必是完美的,但它们的质量会影响最终的遗憾界限。通过利用这些预测,算法可以实现比没有预测的算法更快的收敛速率。

3.1.8. 双线性鞍点问题 (Bilinear Saddle-Point Problem, BSPP)

双线性鞍点问题 (BSPP) 是一种优化问题,形式如下: minxXmaxyYxAy \operatorname*{min}_{x \in \mathcal{X}} \operatorname*{max}_{y \in \mathcal{Y}} x^\top A y 其中 X\mathcal{X}Y\mathcal{Y} 是凸紧集,AA 是矩阵。在零和扩展形式博弈中,求解纳什均衡可以被建模为一个 BSPP,其中 X\mathcal{X}Y\mathcal{Y} 是玩家的 序列形式策略空间AA 编码了博弈的收益。

3.1.9. 序列形式 (Sequence Form)

序列形式 (Sequence Form) 是一种在扩展形式博弈中表示策略和收益的替代方法,它能够将非线性的预期收益转化为线性的形式,从而可以使用线性规划 (linear programming) 或一阶方法 (first-order methods) 来求解。

  • 核心思想: 不再直接表示每个决策点的条件概率,而是表示从博弈开始到某个特定行动序列 (sequence of actions) 发生的总概率。
  • 优点: 在这种表示下,玩家的策略空间是凸紧集,并且预期损失是策略的线性函数,这使得优化问题更易处理。

3.2. 前人工作

3.2.1. 反事实遗憾最小化 (Counterfactual Regret Minimization, CFR)

CFR (Zinkevich et al., 2007) 是求解大规模零和扩展形式博弈的基石算法。其核心思想是将整个博弈的遗憾分解为每个信息集 (information set) 上的局部反事实遗憾 (counterfactual regret)。玩家在每个信息集独立地最小化这些局部遗憾,然后这些局部策略组合成一个全局策略。

  • Monte-Carlo CFR (Lanctot et al., 2009): CFR 的一个变体,通过蒙特卡洛采样来估计反事实值,从而处理更大的博弈。
  • CFR+CFR+ (Tammelin et al., 2015): CFR 的一个改进版本,通过裁剪负遗憾 (negative regrets) 和采用平均策略 (average strategy) 来加速收敛。在实践中表现非常出色,收敛速度往往远超理论预测的 O(T1/2)O(T^{-1/2})
  • Discounted CFR (DCFR) (Brown & Sandholm, 2019): CFR+CFR+ 的进一步改进,通过对过去的遗憾进行折扣,进一步加速了实践中的收敛。这也是目前最先进的实践算法之一。

3.2.2. 乐观学习与矩阵博弈

  • Rakhlin & Sridharan (2013a;b):在在线学习中引入了 乐观镜像下降 (Optimistic Mirror Descent, OMD) 算法。他们通过利用损失序列的预测性(例如,将上一步的损失作为下一步的预测),展示了在矩阵博弈中可以实现 O(T1)O(T^{-1}) 的收敛速率,这得益于乐观更新中出现的抵消项 (cancellations)。
  • Syrgkanis et al. (2015):在 Rakhlin & Sridharan 的工作基础上,提出了 乐观跟随正则化领导者 (Optimistic Follow-the-Regularized-Leader, OFTRL) 算法。他们引入了 由效用变化界定的遗憾 (Regret bounded by Variation in Utilities, RVU) 属性,并证明了即使玩家不使用相同的算法,只要每个算法都满足一个稳定性标准并利用损失输入的预测性,就可以达到 O(T3/4)O(T^{-3/4}) 的速率。本文的工作正是建立在 Syrgkanis et al. (2015) 的这一推广之上。

3.2.3. CFR 框架外的 O(T1)O(T^{-1}) 一阶方法

  • Hoda et al. (2010), Kroer et al. (2015; 2018b):这些工作将 Nesterov过度间隙技术 (Excessive Gap Technique)Nemirovski镜像近端算法 (Mirror Prox) 与稀疏距离生成函数 (dilated distance-generating function) 结合,用于求解扩展形式博弈的纳什均衡,并实现了理论上 O(T1)O(T^{-1}) 的收敛速率。然而,这些方法在实践中的表现往往不如 CFR+CFR+DCFR 等 CFR 变体。

3.2.4. 尝试将乐观遗憾最小化引入 CFR 的早期工作

  • Burch (2017):尝试在 O(T1)O(T^{-1}) 一阶方法和遗憾最小化器的背景下实现类似 CFR 的特性。

  • Brown & Sandholm (2019):在 CFR 中实验性地尝试了乐观变体的遗憾最小化器。

    重要提示: 论文强调,上述早期工作仅限于实验性尝试,而本文是第一个严格地将乐观遗憾最小化纳入 CFR 框架,并首次实现理论加速的研究。

3.3. 技术演进

该领域的技术演进大致可以概括为以下几个阶段:

  1. 早期阶段 (2000s): CFR (Zinkevich et al., 2007) 的提出,为求解大型不完全信息博弈奠定了基础,但理论收敛速率为 O(T1/2)O(T^{-1/2})
  2. 实践加速阶段 (2009-2015): Monte-Carlo CFRCFR+CFR+ 的出现,显著提升了 CFR 在实践中的性能,使得 AI 在扑克等领域达到了超人水平,但其理论最差收敛速率仍保持 O(T1/2)O(T^{-1/2})
  3. 理论加速探索阶段 (2010s): Hoda et al., Kroer et al. 等人将一阶方法引入扩展形式博弈,并在理论上达到了 O(T1)O(T^{-1}) 的收敛速率,但其在实践中表现不如 CFR+CFR+。同时,Rakhlin & Sridharan, Syrgkanis et al. 等人在矩阵博弈的在线学习中发展了乐观遗憾最小化理论,实现了 O(T1)O(T^{-1})O(T3/4)O(T^{-3/4}) 的加速。
  4. 理论与实践融合的尝试 (近年): 研究人员开始探索如何将乐观遗憾最小化等先进的理论技术引入到 CFR 框架中,以弥合理论与实践之间的鸿沟。本文正是这一探索的里程碑式工作。

3.4. 差异化分析

本文的方法与相关工作中的主要方法相比,核心区别和创新点如下:

  • 与传统 CFR 的区别: 传统 CFR 使用非预测性遗憾最小化器,导致 O(T1/2)O(T^{-1/2}) 的收敛速率。本文则将每个信息集的局部遗憾最小化器替换为稳定-预测性乐观遗憾最小化器,并精心设计了其稳定性参数,从而在理论上将整体收敛速率提升到 O(T3/4)O(T^{-3/4})。这是首次在 CFR 框架内实现理论速率的突破。
  • CFR+CFR+/DCFR 的区别: CFR+CFR+DCFR 是通过启发式方法(如裁剪负遗憾、折扣历史遗憾)在实践中显著加速 CFR 的变体。尽管它们在实践中可能表现出比本文方法更快的收敛速度,但它们的理论最差收敛速率仍然是 O(T1/2)O(T^{-1/2})。本文的贡献在于理论上的突破,它提供了第一个在 CFR 框架内具有更好理论速率的算法。
  • 与矩阵博弈中乐观学习的区别: Rakhlin & Sridharan 等人的工作在矩阵博弈中实现了 O(T1)O(T^{-1}) 甚至更好的收敛速率。但这些结果通常依赖于所有玩家都使用相同的算法,并利用了特定抵消项。在扩展形式博弈的复杂树状结构中,这种全局的抵消项难以实现。本文通过引入新的 stable-predictivity 定义,并根据决策树结构分层设置稳定性参数,成功地将乐观学习的思想推广到 CFR 的局部更新中,从而实现了 O(T3/4)O(T^{-3/4}) 的收敛速率,而不是完全的 O(T1)O(T^{-1})
  • O(T1)O(T^{-1}) 一阶方法 (FOMs) 的区别: FOMs(如 Excessive Gap Technique, Mirror Prox)在理论上可以达到 O(T1)O(T^{-1}),但它们通常在实践中不如 CFR 算法有效。本文的工作是在 CFR 框架内部进行改进,旨在结合 CFR 框架的实践优势与乐观学习的理论加速潜力,而不是完全替代 CFR 框架。

4. 方法论

本节将深入探讨 Stable-Predictive Optimistic Counterfactual Regret Minimization 算法的方法原理、核心组件以及它们如何协同工作以实现理论上的收敛加速。

4.1. 方法原理

本文的核心思想是将矩阵博弈中 预测性 (predictive)稳定 (stable) 遗憾最小化器 (regret minimizers) 的概念引入到 CFR 框架中。传统 CFR 将求解扩展形式博弈的全局纳什均衡问题分解为在每个信息集 (information set) 上求解局部反事实遗憾最小化问题。本文将每个信息集上的局部遗憾最小化器替换为一种新型的 稳定-预测性 遗憾最小化器。

其基本直觉是:

  1. 预测性: 如果遗憾最小化器能够接收并利用对未来损失的预测,它就可以更“聪明”地做出当前决策,从而减少累积遗憾。

  2. 稳定性: 遗憾最小化器生成的决策序列应该“缓慢变化”,即连续迭代之间的决策差异不应太大。这种稳定性有助于控制算法的整体行为,并与预测性一起促成更快的收敛。

  3. 层次分解: CFR 的核心是遗憾分解。通过在决策树的每个节点(信息集)使用满足 stable-predictivity 的局部遗憾最小化器,并巧妙地设置这些局部最小化器的稳定性参数,使得决策树深处的节点具有更高的稳定性需求,从而在整个树结构中保持算法的加速收敛特性。

    最终,通过这种方式,算法能够将 双线性鞍点问题 (BSPP) 的鞍点残差收敛速率从传统的 O(T1/2)O(T^{-1/2}) 提升到 O(T3/4)O(T^{-3/4})

4.2. 核心方法详解 (逐层深入)

4.2.1. 稳定-预测性遗憾最小化器 (Stable-Predictive Regret Minimizers)

本文引入了一个新的遗憾最小化器类别,称之为 (κ,α,β)stablepredictive。一个预测性遗憾最小化器如果是(\kappa, \alpha, \beta)`-stable-predictive`\text{。} \text{一个预测性遗憾最小化器如果是}(\kappa, \alpha, \beta)-stable-predictive,需满足以下两个条件:

  1. 稳定性 (Stability): 产生的决策变化缓慢。 xt+1xtκt1(5) \|x^{t+1} - x^t\| \leq \kappa \quad \forall t \geq 1 \quad \text{(5)} 这里,xtx^t 是在时间 tt 产生的决策,\|\cdot\| 是选择的范数,κ\kappa 是一个正的稳定性参数。这个条件要求连续两个决策之间的距离(变化量)不超过 κ\kappa

  2. 预测界限 (Prediction bound): 累积遗憾被限制在一个常数项和预测质量度量的和。 RTακ+βκt=1Ttmt2(6) R^T \leq \frac{\alpha}{\kappa} + \beta \kappa \sum_{t=1}^T \|\ell^t - m^t\|_*^2 \quad \text{(6)} 这里,RTR^T 是时间 TT 的累积遗憾,t\ell^t 是在时间 tt 观察到的损失向量,mtm^t 是在时间 tt 对损失向量的预测,\|\cdot\|_* 是与 \|\cdot\| 对偶的范数,α,β\alpha, \beta 是正常数。 这个条件表明,如果预测 mtm^t 完美匹配实际损失 t\ell^t,那么累积遗憾将渐近地趋于一个常数 α/κ\alpha/\kappa。预测误差 tmt2\|\ell^t - m^t\|_*^2 对遗憾的贡献由 βκ\beta \kappa 因子控制。注意到这里的系数 α/κ\alpha/\kappaβκ\beta \kappa 是相互关联的,这与 Syrgkanis et al. (2015)RVU 属性有所不同,后者没有强制这种反比关系。

4.2.2. 与双线性鞍点问题 (BSPP) 的关系

本文展示了如何使用 稳定-预测性遗憾最小化器 来解决双线性鞍点问题 (BSPP),从而求解零和扩展形式博弈的纳什均衡。 一个鞍点 (xˉ,yˉ)( \bar{x}, \bar{y} ) 的鞍点残差 (saddle-point residual) ξ\xi 定义为: ξ:=maxy^YxˉAy^minx^Xx^Ayˉ(7) \xi := \operatorname*{max}_{\hat{y} \in \mathcal{Y}} \bar{x}^\top A \hat{y} - \operatorname*{min}_{\hat{x} \in \mathcal{X}} \hat{x}^\top A \bar{y} \quad \text{(7)} 它衡量了当前点距离鞍点有多近。

根据一个“民间定理 (folk theorem)” (Cesa-Bianchi & Lugosi, 2006),低遗憾 (low regret) 与低残差 (low residual) 紧密相关。通过设置两个遗憾最小化器(一个用于玩家 X\mathcal{X},一个用于玩家 Y\mathcal{Y}),它们分别观察损失向量 Xt:=Ayt\ell_{\mathcal{X}}^t := -A y^tYt:=Axt\ell_{\mathcal{Y}}^t := A^\top x^t,那么平均决策 (1Tt=1Txt,1Tt=1Tyt)X×Y(8) \left( \frac{1}{T} \sum_{t=1}^T x^t, \frac{1}{T} \sum_{t=1}^T y^t \right) \in \mathcal{X} \times \mathcal{Y} \quad \text{(8)} 的残差 ξ\xi 上界为: ξ1T(RXT+RYT)(9) \xi \leq \frac{1}{T} (R_{\mathcal{X}}^T + R_{\mathcal{Y}}^T) \quad \text{(9)} 其中 RXTR_{\mathcal{X}}^TRYTR_{\mathcal{Y}}^T 分别是两个玩家的累积遗憾。 如果这两个遗憾最小化器是 (\kappa, \alpha, \beta)`-stable-predictive`\text{,并且使用} $m_χ^t := \ell_χ^{t-1}, m_y^t := \ell_y^{t-1}$ \text{作为预测,那么残差} $\xi$ \text{可以被进一步约束:} \begin{array}{r l} & T\xi \leq \displaystyle \frac{2\alpha}{\kappa} + \beta\kappa \sum_{t=1}^T |-A y^t + A y^{t-1}|*^2 \ & \qquad + \beta\kappa \displaystyle \sum{t=1}^T |A^\top x^t - A^\top x^{t-1}|*^2 \ & \leq \displaystyle \frac{2\alpha}{\kappa} + \beta |A|{\mathrm{op}}^2 \kappa \left( \displaystyle \sum_{t=1}^T |x^t - x^{t-1}|^2 + \displaystyle \sum_{t=1}^T |y^t - y^{t-1}|^2 \right) \ & \leq \displaystyle \frac{2\alpha}{\kappa} + 2\beta T |A|_{\mathrm{op}}^2 \kappa^3, \end{array}

其中 Aop\|A\|_{\mathrm{op}} 是矩阵 AA 的算子范数 (operator norm)。
-   第一个不等式由 `stable-predictivity` 的预测界限 (6) 得到。
-   第二个不等式使用了算子范数的性质 AzAopz\|Az\|_* \leq \|A\|_{\mathrm{op}} \|z\|。
-   第三个不等式由稳定性条件 (5) 得到,即 xtxt1κ\|x^t - x^{t-1}\| \leq \kappa。
    通过选择稳定性参数 κ=Θ(T1/4)\kappa = \Theta(T^{-1/4}),可以得到鞍点残差 ξ=O(T3/4)\xi = O(T^{-3/4}),这比传统非预测性遗憾最小化器的 O(T1/2)O(T^{-1/2}) 更快。

### 4.2.3. 乐观跟随正则化领导者 (Optimistic Follow the Regularized Leader, OFTRL)
`OFTRL` 是一种满足 `stable-predictivity` 属性的遗憾最小化器。在每个时间步 tt,`OFTRL` 输出的决策 xtx^t 为:

x^t = \underset{\tilde{x} \in \mathcal{X}}{\mathrm{argmin}} \left. \left. \langle \tilde{x}, m^t + \sum_{\tau=1}^{t-1} \ell^\tau \rangle + \frac{1}{\eta} R(\tilde{x}) \right. \right. \quad \text{(10)}

其中 η>0\eta > 0 是一个步长参数,R()R(\cdot) 是一个关于范数 \|\cdot\| 的 `1-强凸正则化项 (1-strongly convex regularizer)`。
-   `Theorem 1` 证明了 `OFTRL` 是一个 3Δ(η,ΔR,1)3\Delta_\ell(\eta, \Delta_R, 1)-stable-predictive 遗憾最小化器。其中 ΔR:=maxx,yX{R(x)R(y)}\Delta_R := \operatorname*{max}_{x,y \in \mathcal{X}} \{R(x) - R(y)\}RR 值域的直径,Δ:=maxtmax{t,mt}\Delta_\ell := \operatorname*{max}_t \operatorname*{max} \{\|\ell^t\|_*, \|m^t\|_*\} 是损失向量或其预测的最大对偶范数。

    其证明依赖于 `argmin` 函数的 Lipschitz 连续性,这由 `Lemma 5` 给出:
**Lemma 5.** 函数 x~:LargminxX{x,L+1ηR(x)}\tilde{x}: L \mapsto \operatorname*{argmin}_{x \in \mathcal{X}} \{ \langle x, L \rangle + \frac{1}{\eta} R(x) \} 关于对偶范数是 η\eta-Lipschitz 连续的,即:

|\tilde{x}(L) - \tilde{x}(L')| \leq \eta |L - L'|_* \quad \text{(25)} \text{该引理的证明步骤如下:} 1. \text{根据} $\tilde{x}(L)$ \text{的最优性变分不等式} (variational inequality) \text{为:} \langle L + \frac{1}{\eta} \nabla R(\tilde{x}(L)), \tilde{x}(L') - \tilde{x}(L) \rangle \geq 0 \quad \text{(26)} 2.同理,对于2. \text{同理,对于} \tilde{x}(L'),有:\text{,有:} \langle L' + \frac{1}{\eta} \nabla R(\tilde{x}(L')), \tilde{x}(L) - \tilde{x}(L') \rangle \geq 0 \quad \text{(27)}

3.  将 (26) 和 (27) 相加,得到:
\frac{1}{\eta} \langle \nabla R(\tilde{x}(L)) - \nabla R(\tilde{x}(L')), \tilde{x}(L) - \tilde{x}(L') \rangle \leq \langle L' - L, \tilde{x}(L) - \tilde{x}(L') \rangle \quad \text{(28)}
4.  \text{利用} $R(\cdot)$ \text{的强凸性} (strong convexity) (`1`-\text{强凸意味着} $\langle \nabla R(x) - \nabla R(y), x - y \rangle \geq \|x - y\|^2$) \text{和广义} Cauchy-Schwarz \text{不等式} (generalized Cauchy-Schwarz inequality) ($\langle u, v \rangle \leq \|u\|_* \|v\|$):
\frac{1}{\eta} \|\tilde{x}(L) - \tilde{x}(L')\|^2 \leq \|\tilde{x}(L) - \tilde{x}(L')\| \|L - L'\|_* \quad \text{(29)}
5.  除以 x~(L)x~(L)\|\tilde{x}(L) - \tilde{x}(L')\| 即可得到 Lipschitz 连续性。

    基于 `Lemma 5`,`Corollary 2` 给出了 `OFTRL` 决策的稳定性:
**Corollary 2.** 在每个时间步 tt,`OFTRL` 产生的迭代满足 xtxt13ηΔ\|x^t - x^{t-1}\| \leq 3\eta\Delta_\ell。
证明:

\begin{array}{c} |x^t - x^{t-1}| = \left|\tilde{x}(L^{t-1} + m^t) - \tilde{x}(L^{t-2} + m^{t-1})\right| \ \leq \eta |\ell^{t-1} + m^t - m^{t-1}|* \leq 3\eta\Delta\ell, \end{array}

其中第一个不等式由 `Lemma 5` 得到,第二个不等式由 Δ\Delta_\ell 的定义和三角不等式得到。

### 4.2.4. CFR 作为遗憾分解 (CFR as Regret Decomposition)
`CFR` 的核心思想是将全局遗憾分解为局部反事实遗憾。对于每个决策点 jIj \in \mathcal{I},`CFR` 构造一个线性反事实损失函数 ^jt,:ΔnjR\hat{\ell}_j^{t,\circ}: \Delta^{n_j} \to \mathbb{R},它衡量了代理在决策点 jj 仅改变策略 xjx_j 而其他地方保持策略 x,tx^{\triangle,t} 所遭受的损失。
形式上,反事实损失函数定义为:

\hat{\ell}j^{t,\circ} : x_j = (x{ja_1}, \ldots x_{ja_{n_j}}) \mapsto \langle [\ell^{\triangle,t}]j, x_j \rangle + \sum{a \in A_j} \left( x_{ja} \sum_{j' \in \mathcal{C}{ja}} \langle [\ell^{\triangle,t}]{\downarrow j'}, [x^{\triangle,t}]_{\downarrow j'} \rangle \right) \quad \text{(11)}

由于这是一个线性函数,可以表示为一个向量与策略的点积:

\hat{\ell}_j^{t,\circ}(x_j) = \langle \hat{\ell}_j^t, x_j \rangle \quad \forall x_j \in \Delta^{n_j} \quad \text{(12)} \text{其中} $\hat{\ell}_j^t$ \text{是对应的反事实损失向量。} \text{基于此,每个决策点} $j \in \mathcal{I}$ \text{都有一个局部反事实遗憾} $\hat{R}_j^T$: \hat{R}j^T := \sum{t=1}^T \langle \hat{\ell}_j^t, \hat{x}j^t \rangle - \operatorname*{min}{\tilde{x}j \in \Delta^{n_j}} \sum{t=1}^T \langle \hat{\ell}_j^t, \tilde{x}_j \rangle \quad \text{(13)}

`CFR` 通过为每个决策点 jIj \in \mathcal{I} 实例化一个局部遗憾最小化器 R^j\hat{\mathcal{R}}_j 来工作。这些局部最小化器在局部策略空间 Δnj\Delta^{n_j} 上运行,并观察各自的反事实损失向量 ^jt\hat{\ell}_j^t。整个算法 R\mathcal{R}^{\triangle} 的策略 x,tx^{\triangle,t} 是由这些局部决策 x^jt\hat{x}_j^t 归纳组合而成的。

**序列形式策略空间 (Sequence Form Strategy Space)**
为了处理扩展形式博弈的策略空间,本文使用了 `序列形式 (sequence form)` 表示。
-   **观察节点 kKk \in \mathcal{K}:**
X_k^\triangle := X_{j_1}^\triangle \times X_{j_2}^\triangle \times \cdots \times X_{j_{n_k}}^\triangle \quad \text{(12, 原文中为 12)}
\text{其中} $\{j_1, j_2, \ldots, j_{n_k}\} = \mathcal{C}_k$ \text{是} $k$ \text{的子决策点。}
-   **\text{决策节点} $j \in \mathcal{I}$\text{:}**
X_j^\triangle := \left\{ \left( \begin{array}{c} \lambda_1 \\ \vdots \\ \frac{\lambda_{n_j}}{\lambda_1 x_{k_1}} \\ \vdots \\ \lambda_{n_j} x_{k_{n_j}} \end{array} \right) : \left( \lambda_1, \ldots, \lambda_n \right) \in \Delta^{n_j}, x_{k_1} \in X_{k_1}^\triangle, x_{k_2} \in X_{k_2}^\triangle, \ldots, x_{k_{n_j}} \in X_{k_{n_j}}^\triangle \right\} , \quad \text{(13, 原文中为 13)}
其中 {λ1,,λnj}\{\lambda_1, \ldots, \lambda_{n_j}\} 是在决策点 jj 的局部策略, {k1,k2,,knj}=Cj\{k_1, k_2, \ldots, k_{n_j}\} = \mathcal{C}_jjj 的子观察点。
    注意原文公式中似乎存在印刷错误,分母中不应出现 xk1x_{k_1} 等,这与序列形式的定义不符。序列形式的定义是,每个序列的概率是路径上所有行动概率的乘积。这里原文的表达可能是一个概括性或抽象的符号,但它应该代表了序列形式策略的结构。在序列形式中,一个决策点 jj 的策略 xjx_j^\triangle 是由当前局部动作概率 x^j\hat{x}_j 和其子树的序列策略组合而成的。
    更常见的序列形式表示是:对于某个序列 ss 的概率 xsx_s 及其扩展 `sa`,则 xsa=xsp(as)x_{sa} = x_s \cdot p(a|s),其中 p(as)p(a|s) 是在序列 ss 之后采取动作 aa 的条件概率。

`Lemma 1` 和 `Lemma 2` 描述了遗憾在树结构中的分解关系:
**Lemma 1.** 设 kKk \in \mathcal{K} 是一个观察节点。那么,Rk,T=jCkRj,TR_k^{\triangle,T} = \sum_{j \in \mathcal{C}_k} R_j^{\triangle,T}。
**证明:** 通过将 Rk,TR_k^{\triangle,T} 的定义和 (12)、(11) 结合,可以将点积和最小化问题分解为独立的部分,每个 jCkj \in \mathcal{C}_k 一个。

**Lemma 2.** 设 jIj \in \mathcal{I} 是一个决策节点。那么,Rj,TR^jT+maxkCjRk,TR_j^{\triangle,T} \leq \hat{R}_j^T + \operatorname*{max}_{k \in \mathcal{C}_j} R_k^{\triangle,T}。
**证明:** 同样通过将 Rj,TR_j^{\triangle,T} 的定义和 (13)、(11) 结合,并将最小化问题分解,得到局部反事实遗憾 R^jT\hat{R}_j^T 和子树遗憾的最大值。

这两个引理是 CFR 算法遗憾分解的基础,并且对局部遗憾最小化器的性质(是否预测性或稳定-预测性)不作假设,因此适用于本文提出的新变体。

### 4.2.5. 稳定-预测性反事实遗憾最小化 (Stable-Predictive Counterfactual Regret Minimization)
本文提出的算法与 `CFR` 行为完全相同,但关键区别在于:
1.  **局部遗憾最小化器:** 每个决策点 jIj \in \mathcal{I} 的局部遗憾最小化器 R^j\hat{\mathcal{R}}_j 是 `稳定-预测性` 的。
2.  **稳定性参数选择:** 局部遗憾最小化器的稳定性参数是根据其在决策树中的位置(深度)来选择的。
3.  **预测生成:** 为每个局部遗憾最小化器生成特定的反事实预测向量 m^jt\hat{m}_j^t。

**稳定性参数的选择 (Choice of Stability Parameters)**
为每个节点 vIKv \in \mathcal{I} \cup \mathcal{K} 关联一个标量 γv\gamma_v。
-   根决策节点 rrγr\gamma_r 设置为期望的全局稳定性参数 κ\kappa^*。
-   其他节点 vvγv\gamma_v 相对于其父节点 uu 的值设置:
\gamma_v := \left\{ \begin{array}{ll} \displaystyle \frac{\gamma_u}{2\sqrt{n_u}} & \mathrm{if~} u \in \mathcal{I} \\ \displaystyle \frac{\gamma_u}{\sqrt{n_u}} & \mathrm{if~} u \in \mathcal{K}. \end{array} \right. \quad \text{(14)}
\text{其中} $n_u$ \text{是节点} $u$ \text{的子节点数量。}
\text{每个决策点} $j \in \mathcal{I}$ \text{的稳定性参数} $\kappa_j$ \text{选择为:}

\kappa_j := \frac{\gamma_j}{2\sqrt{n_j} B_j} \quad \text{(15)} \text{其中} $B_j$ \text{是} $X_j^\triangle$ \text{直径的一个上界} (an upper bound on the diameter of $X_j^\triangle$)\text{。}$B_j$ \text{的值可以通过以下递归规则找到:} - \text{对于所有观察点} $k \in \mathcal{K}$\text{:} B_k = \displaystyle \sqrt{\sum_{j \in \mathcal{C}k} B_j^2} - \text{对于所有决策点} $j \in \mathcal{I}$\text{:} B_j = \displaystyle \sqrt{1 + \displaystyle \operatorname*{max}{k \in \mathcal{C}_j} B_k^2}

**注意:** 原文中给出的 B_j 公式可能存在印刷错误或简化,通常序列形式策略空间的直径定义与正则化项相关。这里的 BjB_j 可能是为了在归纳证明中控制范数大小而引入的辅助变量。
通过适当选择步长参数 η\eta (例如,对于 `OFTRL`,可以设 η=κj\eta = \kappa_j),可以确保局部 `OFTRL` 遗憾最小化器满足上述稳定性参数。

**反事实损失向量的预测 (Prediction of Counterfactual Loss Vectors)**
设 m,tm^{\triangle,t}R\mathcal{R}^{\triangle} 接收到的关于未来损失向量 ,t\ell^{\triangle,t} 的预测。
对于每个决策点 jIj \in \mathcal{I},反事实预测函数 m^jt,:ΔnjR\hat{m}_j^{t,\circ}: \Delta^{n_j} \to \mathbb{R} 定义为:

\hat{m}j^{t,\circ} : x_j = (x{ja_1}, \ldots, x_{ja_{n_j}}) \mapsto \langle [m^{\triangle,t}]j, x_j \rangle + \sum{a \in A_j} \left( x_{ja} \sum_{j' \in \mathcal{C}{ja}} \langle [m^{\triangle,t}]{\downarrow j'}, [x^{\triangle,t}]_{\downarrow j'} \rangle \right) \quad \text{(17)} \text{这个预测函数依赖于时间} $t$ \text{在子树中产生的决策} $x^{\triangle,t}$\text{。} \text{与反事实损失函数类似,反事实损失预测向量} $\hat{m}_j^t$ \text{是} $\mathbb{R}^{n_j}$ \text{中唯一的向量,使得:} \hat{m}_j^{t,\circ}(x_j) = \langle \hat{m}j^t, x_j \rangle \quad \forall x_j \in \Delta^{n_j} \quad \text{(18)} <strong>\text{正确性证明} (Proof of Correctness)</strong> \text{通过对决策树结构进行归纳证明,本文展示了所选择的稳定性参数} (14) \text{和反事实损失预测} (17) \text{能够保证} $\mathcal{R}^{\triangle}$ \text{是一个} $(\kappa^*, O(1), O(1))$-stable-predictive \text{遗憾最小化器。} \text{归纳步骤分为观察节点和决策节点:} **Lemma 3.** \text{设} $k \in \mathcal{K}$ \text{是一个观察节点,并假设对于每个} $j \in \mathcal{C}_k$\text{,}$\mathcal{R}_j^\triangle$ \text{是一个在} $X_j^\triangle$ \text{上的} $(\gamma_j, O(1), O(1))$-stable-predictive \text{遗憾最小化器。那么,}$\mathcal{R}_k^\triangle$ \text{是一个在} $X_k^\triangle$ \text{上的} $(\gamma_k, O(1), O(1))$-stable-predictive \text{遗憾最小化器。} **\text{证明概述:}** 1. **\text{预测界限:}** \text{由假设,每个子节点} $j \in \mathcal{C}_k$ \text{满足:} R_j^{\triangle,T} \leq \frac{O(1)}{\gamma_j} + O(1) \gamma_j \sum{t=1}^T |\ell_j^{\triangle,t} - m_j^{\triangle,t}|_2^2 \quad \text{(19)}

\|x_j^{\triangle,t} - x_j^{\triangle,t-1}\|_2 \leq \gamma_j \quad \text{(20)}
将 (19) 代入 `Lemma 1` (Rk,T=jCkRj,TR_k^{\triangle,T} = \sum_{j \in \mathcal{C}_k} R_j^{\triangle,T}),并利用 γj=γk/nk\gamma_j = \gamma_k / \sqrt{n_k} (根据 (14)),得到:
\begin{array}{r l}
& \displaystyle R_k^{\triangle,T} \leq O(1) \sum_{j \in \mathcal{C}_k} \frac{1}{\gamma_j} + O(1) \sum_{j \in \mathcal{C}_k} \sum_{t=1}^T \gamma_j \|\ell_j^{\triangle,t} - m_j^{\triangle,t}\|_2^2 \\
& \qquad \leq O(1) \frac{n_k^{3/2}}{\gamma_k} + O(1) \frac{\gamma_k}{\sqrt{n_k}} \sum_{t=1}^T \displaystyle \sum_{j \in \mathcal{C}_k} \|\ell_j^{\triangle,t} - m_j^{\triangle,t}\|_2^2 \\
& \qquad = \displaystyle \frac{O(1)}{\gamma_k} + O(1) \gamma_k \displaystyle \sum_{t=1}^T \|\ell_k^{\triangle,t} - m_k^{\triangle,t}\|_2^2
\end{array} \quad \text{(21)}
这满足了 `stable-predictivity` 的预测界限。
2.  **稳定性:**
    利用 (12) 和 (20) 以及 γj=γk/nk\gamma_j = \gamma_k / \sqrt{n_k},得到:
\|x_k^{\triangle,t} - x_k^{\triangle,t-1}\|_2 = \sqrt{\sum_{j \in \mathcal{C}_k} \|x_j^{\triangle,t} - x_j^{\triangle,t-1}\|_2^2} \leq \sqrt{\sum_{j \in \mathcal{C}_k} \gamma_j^2} = \gamma_k \quad \text{(22)}
\text{这表明} $\mathcal{R}_k^\triangle$ \text{是} $\gamma_k$-\text{稳定的。}

**Lemma 4.** \text{设} $j \in \mathcal{I}$ \text{是一个决策节点,并假设对于每个} $k \in \mathcal{C}_j$\text{,}$\mathcal{R}_k^\triangle$ \text{是一个在} $X_k^\triangle$ \text{上的} $(\gamma_k, O(1), O(1))$-stable-predictive \text{遗憾最小化器。再假设} $\hat{\mathcal{R}}_j$ \text{是一个在} $\Delta^{n_j}$ \text{上的} $(\kappa_j, O(1), O(1))$-stable-predictive \text{遗憾最小化器。那么,}$\mathcal{R}_j^\triangle$ \text{是一个在} $X_j^\triangle$ \text{上的} $(\gamma_j, O(1), O(1))$-stable-predictive \text{遗憾最小化器。}
**\text{证明概述:}**
1.  **\text{预测界限:}**
    \text{根据假设,每个子节点} $k \in \mathcal{C}_j$ \text{满足:}
R_k^{\triangle,T} \leq \frac{O(1)}{\gamma_k} + O(1) \gamma_k \sum_{t=1}^T \|\ell_k^{\triangle,t} - m_k^{\triangle,t}\|_2^2 \quad \text{(23)}
\|x_k^{\triangle,t} - x_k^{\triangle,t-1}\|_2 \leq \gamma_k \quad \text{(24)}
将 (23) 代入 `Lemma 2`,并注意到子树的损失向量和预测是从父节点转发的,得到:
R_{\triangle_j}^T \leq \hat{R}_j^T + \frac{O(1)}{\gamma_k} + O(1) \gamma_k \sum_{t=1}^T \|\ell_j^{\triangle,t} - m_j^{\triangle,t}\|_2^2 \quad \text{(25)}
由于\text{由于} \hat{\mathcal{R}}_j也是一个 \text{也是一个}(\kappa_j, O(1), O(1))`-stable-predictive` 遗憾最小化器,它的遗憾满足:
R^jTO(1)κj+O(1)κjt=1T^jtm^jt22=O(1)γj+O(1)γjt=1Tj,tmj,t22,(26)
    \begin{array}{c}
    \displaystyle \hat{R}_j^T \le \frac{O(1)}{\kappa_j} + O(1) \kappa_j \sum_{t=1}^T \|\hat{\ell}_j^t - \hat{m}_j^t\|_2^2 \\
    \displaystyle = \frac{O(1)}{\gamma_j} + O(1) \gamma_j \sum_{t=1}^T \|\ell_j^{\triangle,t} - m_j^{\triangle,t}\|_2^2,
    \end{array} \quad \text{(26)}
    
其中等式是根据 κj\kappa_j 的定义 (15) 以及以下关系:
^jtm^jt22kCjxk,t22k,tmk,t22j,tmj,t22kCjBk2=O(1)j,tmj,t22.(27)
    \begin{array}{r l}
    \|\hat{\ell}_j^t - \hat{m}_j^t\|_2^2 \leq \displaystyle \sum_{k \in \mathcal{C}_j} \|x_k^{\triangle,t}\|_2^2 \cdot \|\ell_k^{\triangle,t} - m_k^{\triangle,t}\|_2^2 & \\
    \leq \|\ell_j^{\triangle,t} - m_j^{\triangle,t}\|_2^2 \displaystyle \sum_{k \in \mathcal{C}_j} B_k^2 & \\
    = O(1) \|\ell_j^{\triangle,t} - m_j^{\triangle,t}\|_2^2. &
    \end{array} \quad \text{(27)}
    
将 (26) 代入 (25),并注意到 γk=O(1)γj\gamma_k = O(1)\gamma_j,即可得到 Rj\mathcal{R}_j^\triangle 的预测界限。
  1. 稳定性: 利用 (13),(24) 和 R^j\hat{\mathcal{R}}_j 的稳定性 (x^jtx^jt122κj2=γj2/(4njBj2)\|\hat{x}_j^t - \hat{x}_j^{t-1}\|_2^2 \leq \kappa_j^2 = \gamma_j^2 / (4 n_j B_j^2)),通过 Cauchy-Schwarz 不等式和 BjB_j 的定义 (16),最终得到: xj,txj,t12γj(28) \|x_j^{\triangle,t} - x_j^{\triangle,t-1}\|_2 \leq \gamma_j \quad \text{(28)} 这表明 Rj\mathcal{R}_j^\triangle 具有稳定性参数 γj\gamma_j

Corollary 1. 结合 Lemma 3Lemma 4,通过对顺序决策过程结构进行归纳,可以得出:如果每个局部遗憾最小化器 R^j\hat{\mathcal{R}}_j(\kappa_j, O(1), O(1))`-stable-predictive`\text{,并观察相应的反事实损失} $\hat{\ell}_j^t$ \text{和预测} $\hat{m}_j^t$\text{,那么整个算法} $\mathcal{R}^{\triangle}$ \text{将是一个}(\kappa^*, O(1), O(1))-stable-predictive 遗憾最小化器。 最终,通过将此结果与第 3.1 节的论证结合,本文得出结论:通过为每个玩家构建两个

(\Theta(T^{-1/4}), O(1), O(1))`-stable-predictive` 遗憾最小化器,该算法可以在两玩家零和博弈中以 O(T3/4)O(T^{-3/4}) 的速率近似纳什均衡。

# 5. 实验设置

## 5.1. 数据集
实验在 `无限注德州扑克 (Heads-Up No-Limit Texas Hold'em, HUNL)` 的子博弈 (subgames) 上进行。`HUNL` 是一种两人零和博弈,玩家轮流行动,可以选择 `弃牌 (fold)`、`跟注 (call)` 或 `加注 (raise)`。

**HUNL 博弈规则概述:**
-   **起始筹码:** 两位玩家 P1P_1P2P_2 各有 `20,000 美元`。
-   **位置切换:** 每手牌后玩家位置互换。
-   **盲注 (Blinds):** P1P_1 先放 `100 美元` 到底池 (`大盲注`),P2P_2 放 `50 美元` (`小盲注`)。
-   **发牌:** 每位玩家发两张私牌(只有自己可见),从 52 张牌的牌组中抽取。
-   **下注轮 (Betting Rounds):**
    1.  **第一轮:** P2P_2 先行动。
    2.  **后续轮:** P1P_1 先行动。
    3.  **公共牌:** 第一轮下注结束后发三张公共牌 (`翻牌`);第二轮下注结束后发一张公共牌 (`转牌`);第三轮下注结束后再发一张公共牌 (`河牌`),共五张公共牌。
-   **行动:**
    -   `弃牌 (Fold)`:玩家输掉这手牌,底池归对手。
    -   `跟注 (Call)`:下注与对手相同数量的筹码。
    -   `加注 (Raise)`:下注比对手更多的筹码。
        -   加注不能超过起始筹码 `20,000 美元`。
        -   每次加注至少 `100 美元`,且至少与该轮前一次加注额相同。
-   **轮结束:** 当两位玩家都至少行动过一次,并且最近行动的玩家选择 `跟注 (call)` 时,该轮结束。
-   **摊牌 (Showdown):** 如果没有玩家弃牌,则进行摊牌,持有最佳五张牌牌型的玩家(结合私牌和五张公共牌)赢得底池。平局则平分底池。

**Libratus AI 的子博弈:**
实验在 `Libratus AI` (Brown & Sandholm, 2017b) 实时求解的四个开源子博弈上进行。`Libratus` 在与人类顶尖扑克玩家的比赛中,实时求解从第三轮下注开始的剩余 `HUNL` 部分。
-   **下注大小 (Bet Sizes):**
    -   每轮的第一次下注:底池大小的 0.5×0.5 \times、底池大小的 1×1 \times、`all-in` (全押)。
    -   同一轮的后续下注:底池大小的 1×1 \times、`all-in`。
-   **子博弈描述:**
    -   **子博弈 1 (Subgame 1):** 发生在第三和第四下注轮。开始时底池有 `500 美元`。
    -   **子博弈 2 (Subgame 2):** 发生在第三和第四下注轮。开始时底池有 `4,780 美元`。
    -   **子博弈 3 (Subgame 3):** 仅发生在第四下注轮。开始时底池有 `500 美元`。
    -   **子博弈 4 (Subgame 4):** 仅发生在第四下注轮。开始时底池有 `3,750 美元`。

## 5.2. 评估指标
**可利用性 (Exploitability)**
-   **概念定义:** `可利用性 (Exploitability)` 是衡量一个玩家策略距离纳什均衡有多远的标准指标。在一个零和博弈中,如果一个玩家的策略是非均衡的,那么对手可以通过针对性地调整自己的策略来“利用”这个非均衡策略,从而获得正的预期收益。`可利用性` 就是衡量对手能够从这个非均衡策略中榨取多少预期收益的最大值。一个策略的 `可利用性` 为零,意味着它是一个纳什均衡策略。
-   **数学公式:** 在二人零和博弈中,给定玩家 1 的策略 σ1\sigma_1 和玩家 2 的策略 σ2\sigma_2,博弈的鞍点残差(或可利用性)可以定义为:
\xi(\sigma_1, \sigma_2) = \max_{\sigma_2' \in \Sigma_2} U_1(\sigma_1, \sigma_2') - \min_{\sigma_1' \in \Sigma_1} U_1(\sigma_1', \sigma_2)
\$\$
其中 U1(,)U_1(\cdot, \cdot) 是玩家 1 的预期收益,Σ1\Sigma_1Σ2\Sigma_2 分别是玩家 1 和玩家 2 的策略空间。如果算法的目标是近似纳什均衡,通常计算的是当前平均策略对所有可能对手策略的最大可利用性。
  • 符号解释:
    • ξ(σ1,σ2)\xi(\sigma_1, \sigma_2): 给定玩家 1 策略 σ1\sigma_1 和玩家 2 策略 σ2\sigma_2 的鞍点残差或可利用性。
    • σ1\sigma_1: 玩家 1 的策略。
    • σ2\sigma_2: 玩家 2 的策略。
    • Σ1\Sigma_1: 玩家 1 的所有可能策略集合。
    • Σ2\Sigma_2: 玩家 2 的所有可能策略集合。
    • σ1\sigma_1': 玩家 1 的任意策略。
    • σ2\sigma_2': 玩家 2 的任意策略。
    • maxσ2Σ2U1(σ1,σ2)\max_{\sigma_2' \in \Sigma_2} U_1(\sigma_1, \sigma_2'): 在玩家 1 采用 σ1\sigma_1 的情况下,玩家 2 能够实现的最大收益(对玩家 1 来说是最大损失)。
    • minσ1Σ1U1(σ1,σ2)\min_{\sigma_1' \in \Sigma_1} U_1(\sigma_1', \sigma_2): 在玩家 2 采用 σ2\sigma_2 的情况下,玩家 1 能够实现的最小损失(对玩家 1 来说是最小收益)。
    • 当策略接近纳什均衡时,可利用性 趋近于零。
  • 单位: milli big blinds per game (mbb/g)。这是扑克领域衡量胜率的标准单位。
    • big blind (bb):指 P1 对底池的原始贡献(在 HUNL 中通常是 100 美元)。
    • mbb/g:每手扑克损失的 big blind 数量乘以 1,000。数值越低越好,0 表示纳什均衡。

5.3. 对比基线

论文将自己的方法与以下三种算法进行了比较:

  1. 香草 CFR (Vanilla CFR): 即使用 遗憾匹配 (regret matching) 的原始 CFR 算法。在图中标记为 CFR。这是一个基础且广泛使用的基线。
  2. 折扣 CFR (Discounted CFR, DCFR): Brown & Sandholm (2019) 提出的算法,是目前实践中最先进的算法之一。在图中标记为 DCFR
  3. 稳定-预测性 CFR 变体 (Stable-Predictive CFR variant with OFTRL): 本文提出的方法,在每个决策点使用 乐观跟随正则化领导者 (OFTRL) 算法。在图中标记为 OFTRL

5.4. 实验细节

  • 步长选择:
    • OFTRL theory 严格按照理论建议设置步长。
    • OFTRL tuned 对于子博弈 1 和 2,由于理论步长过于保守,通过将理论步长除以 10、100 和 1000 来手动调整参数,并选择其中最好的一个。
  • 更新方式:
    • 同步更新 (Simultaneous Updates): 所有算法在每个迭代中同时更新所有玩家的策略。这是 CFR 传统的更新方式。
    • 交替更新 (Alternating Updates): 玩家轮流更新策略。这是一种实践中常用于提高性能的改变。

6. 实验结果与分析

论文通过一系列图表展示了在不同 HUNL 子博弈中,CFRDCFROFTRL 算法的收敛速率,以可利用性 (mbb/g) 衡量,并比较了同步更新和交替更新两种模式。

6.1. 核心结果分析

6.1.1. 同步更新 (Simultaneous Updates)

以下是原文 Figure 2 的结果,展示了子博弈 2 和 4 在同步更新下的收敛速率:

Figure 2. Convergence rate with iterations on the \(\\mathbf { X }\) ai, and the exploitability in mbb. All algorithms use simultaneous updates.
该图像是图表,展示了在同时更新的情况下,两个子游戏中不同算法的鞍点差距随着迭代次数的变化。左侧是子游戏2,右侧是子游戏4。CFR、DCFR和其他算法在不同迭代下的表现被比较,显示了各自的收敛速度。

Figure 2. Convergence rate with iterations on the X\mathbf { X } ai, and the exploitability in mbb. All algorithms use simultaneous updates.

以下是原文 Figure 3 的结果,展示了子博弈 1 和 3 在同步更新下的收敛速率:

Figure 3. Convergence rate with iterations on the \(\\mathbf { X }\) axis, and the exploitability in mbb. All algorithms use simultaneous updates.
该图像是图表,展示了在子游戏1和子游戏3的迭代过程中,CFR和DCFR算法的鞍点间隙(mbb/g)随迭代次数的变化。横轴为迭代次数,纵轴为鞍点间隙,所有算法均采用同时更新。

Figure 3. Convergence rate with iterations on the X\mathbf { X } axis, and the exploitability in mbb. All algorithms use simultaneous updates.

分析:

  • 子博弈 3 和 4 (较小规模):
    • OFTRL theory (使用理论建议的步长) 在这些较小的子博弈中表现优于 CFR。在子博弈 4 中,它几乎立即且显著地优于 CFR;在子博弈 3 中,大约在 800 次迭代后开始表现出优势。
    • 这表明在相对简单的博弈中,本文提出的理论方法确实能够带来收敛速度的提升。
  • 子博弈 1 和 2 (较大规模):
    • OFTRL theory 在这些较大的子博弈中表现不佳,收敛速度非常慢,在给定的迭代次数内几乎没有进展。这可能是因为理论上推导的步长参数过于保守,导致更新幅度太小。
    • 通过手动调整步长 ( OFTRL tuned ),OFTRL 的性能显著改善,并优于 CFR。这强调了在实践中,理论步长可能需要进行经验性调整以获得更好的性能。
  • DCFR 的表现:
    • 在所有同步更新的子博弈中,DCFR 的表现都优于 OFTRLCFR
    • DCFR 的实际收敛速度显著快于其理论最差情况 O(T1/2)O(T^{-1/2}) 预测。这与之前对 CFR+CFR+DCFR 的观察一致,即它们在许多实际博弈中表现优异,远超其理论最差情况的界限。

6.1.2. 交替更新 (Alternating Updates)

以下是原文 Figure 4 的结果,展示了子博弈 2 和 4 在交替更新下的收敛速率:

该图像是两幅图表,分别展示了在不同子游戏下的鞍点间隙随迭代次数变化的情况。左侧为子游戏 2,右侧为子游戏 4。图中展示了 CFR、DCFR 及 OFTRL 理论的鞍点间隙变化趋势,其中 CFR 的性能在迭代过程中有所改善,但仍低于 OFTRL 的表现。
该图像是两幅图表,分别展示了在不同子游戏下的鞍点间隙随迭代次数变化的情况。左侧为子游戏 2,右侧为子游戏 4。图中展示了 CFR、DCFR 及 OFTRL 理论的鞍点间隙变化趋势,其中 CFR 的性能在迭代过程中有所改善,但仍低于 OFTRL 的表现。

ure. Convergence rate wit iteraions te X\mathbf { X } updates.

以下是原文 Figure 5 的结果,展示了子博弈 1 和 3 在交替更新下的收敛速率:

该图像是一个比较不同算法在子博弈1和子博弈3中收敛速度的图表,展示了在迭代次数下鞍点间隙的变化。其中,CFR和DCFR的表现被对比,曲线显示出随着迭代次数的增加,CFR和DCFR的鞍点间隙逐渐减小。数据依赖于公式 \(O(T^{-3/4})\) 收敛速率的可视化。
该图像是一个比较不同算法在子博弈1和子博弈3中收敛速度的图表,展示了在迭代次数下鞍点间隙的变化。其中,CFR和DCFR的表现被对比,曲线显示出随着迭代次数的增加,CFR和DCFR的鞍点间隙逐渐减小。数据依赖于公式 O(T3/4)O(T^{-3/4}) 收敛速率的可视化。

ure . Convergence rate wit iterations te X\mathbf { X } updates.

分析:

  • OFTRL 相对于 CFRDCFR 的表现下降:
    • 在交替更新设置下,OFTRL 的性能相对于 CFRDCFR 普遍变差。
    • 在子博弈 1 中,OFTRL theory 略微优于 CFR,但在子博弈 2 中,两者性能几乎相同。
    • 在子博弈 3 和 4 中,即使是 OFTRL tuned 的版本也比 CFR 差。作者猜测,这可能是由于步长参数的选择不佳,可以通过更好的步长选择来改进。
  • DCFR 的主导地位:
    • 在交替更新设置中,DCFR 的表现明显优于所有其他算法,进一步巩固了其作为当前实践中最先进算法的地位。

总结性观察:

  • 本文提出的 OFTRL 变体在理论上打破了 CFR O(T1/2)O(T^{-1/2}) 的收敛瓶颈,达到了 O(T3/4)O(T^{-3/4})。在较小的子博弈中,其理论步长表现优于 CFR
  • 然而,在较大的子博弈中,OFTRL 的理论步长过于保守,需要手动调优才能超越 CFR
  • 最重要的是,在所有测试场景中,DCFR 的实践性能都明显优于 OFTRL,尽管 DCFR 的理论最差收敛速率仍为 O(T1/2)O(T^{-1/2})。这再次印证了理论最差情况界限与实践性能之间存在显著差异。许多启发式方法(如 CFR+CFR+DCFR)在实践中常常能超越理论预测的性能。

6.2. 数据呈现 (表格)

原文中未提供表格数据,所有实验结果均以图表形式呈现。图表已在上方章节中引用和分析。

6.3. 消融实验/参数分析

论文主要关注理论收敛速率的突破,没有进行独立的消融实验来验证模型各组件的有效性。然而,关于步长参数的分析(OFTRL theoryOFTRL tuned 的对比)可以视为一种参数敏感性分析。

  • 参数影响: 步长参数的选择对于 OFTRL 的实践性能至关重要。理论推导的步长在某些情况下过于保守,导致算法收敛缓慢。通过手动调优(例如将步长除以 10、100 或 1000),可以显著改善 OFTRL 在大规模子博弈中的性能。这表明,尽管理论提供了收敛保证,但在实践中,超参数调优仍然是获得良好性能的关键。

7. 总结与思考

7.1. 结论总结

本文提出了第一个在理论上打破了传统 反事实遗憾最小化 (CFR) 框架 O(T1/2)O(T^{-1/2}) 收敛速率限制的变体。通过将矩阵博弈中 预测性 (predictive)稳定 (stable) 遗憾最小化器的概念,以及新引入的 stable-predictivity 概念,巧妙地集成到 CFR 框架中,算法实现了 O(T3/4)O(T^{-3/4}) 的收敛速率。这通过为每个局部反事实遗憾最小化器设定与其在决策树中位置相关的稳定性参数来实现。这项工作是弥合 CFR 理论收敛速率与一阶方法 O(T1)O(T^{-1}) 理论速率之间差距的重要一步。 实验结果表明,在某些较小的无限注德州扑克子博弈中,本文提出的 OFTRL 变体使用理论推导的步长时,性能优于原始 CFR。然而,在较大的子博弈中,理论步长过于保守,需要手动调优才能超越 CFR。尽管如此,在所有测试场景中,目前最先进的实践算法 Discounted CFR (DCFR) 的性能都优于 OFTRL,即使 DCFR 的理论最差收敛速率仍为 O(T1/2)O(T^{-1/2})

7.2. 局限性与未来工作

论文作者指出的局限性:

  1. 实践性能不如启发式算法: 尽管在理论上实现了加速,但在实践中,本文提出的 OFTRL 变体在扑克子博弈上的表现不如 DCFR 等更新的、但理论最差收敛速率仍为 O(T1/2)O(T^{-1/2}) 的启发式算法。这反映了理论最差情况分析与实际启发式算法在特定博弈中表现之间的差距。
  2. 步长选择的重要性: 实验表明,理论上正确的步长在较大规模的博弈中可能过于保守,需要进行经验性调优才能获得较好的性能。这增加了算法在实际应用中的复杂性。

作者提出的未来研究方向:

  • 寻找能够同时满足理论保证并在实践中表现更佳的算法变体。这意味着需要探索新的参数选择策略,或者对 stable-predictive 框架进行进一步的修改,使其更适应实际博弈的特性。

7.3. 个人启发与批判

个人启发:

  1. 理论与实践的永恒张力: 这篇论文生动地展现了理论研究和实践应用之间的有趣张力。一个在理论上具有更优收敛速率的算法,在实际复杂问题中可能因为各种原因(如常数因子、参数敏感性、特定博弈结构)而不如理论较弱但高度优化的启发式算法。这提醒我们,在评估算法时,需要同时关注理论保证和实际性能。
  2. 模块化设计的重要性: CFR 框架将全局博弈分解为局部遗憾最小化问题,这种模块化设计使得研究人员可以独立改进局部组件,并利用遗憾分解的性质推导全局结果。本文正是这种思想的成功应用,通过替换局部遗憾最小化器,实现了全局加速。
  3. 预测性学习的潜力: 乐观学习或预测性学习的思想在在线优化中具有巨大潜力。本文将其推广到复杂的树状博弈结构中,为未来在更广泛的序贯决策问题中应用预测性方法提供了范例。理解和利用环境的预测信息,即使这些预测不完美,也能显著提升学习效率。
  4. 分层稳定性的精妙: 针对扩展形式博弈的树状结构,分层设定稳定性参数是一个非常精妙的设计。它反映了不同决策点在全局策略中的影响力和敏感性,深层节点需要更高的稳定性来防止局部扰动传播到整个博弈中,从而有效控制全局遗憾。

批判或可以改进的地方:

  1. 理论步长与实践的差距: 论文虽然指出理论步长可能过于保守,但并未深入探讨导致这种保守性的具体原因,也未给出更具普适性的调优策略。未来的工作可以研究如何自适应地调整步长,或设计对步长参数不那么敏感的 stable-predictive 算法。
  2. DCFR 性能差距的深层原因: DCFR 的成功可能不仅在于其折扣机制,还在于其对负遗憾的处理方式 (CFR+CFR+)。本文的 OFTRL 变体未明确提及如何处理负遗憾。未来的研究可以尝试将 stable-predictivity 的思想与 CFR+CFR+DCFR 的启发式机制结合,以期在实践中也实现超越。
  3. 计算复杂度: 论文主要关注收敛速率,但对每一步迭代的计算复杂度未做详细分析。OFTRL 的更新可能比简单的遗憾匹配更复杂,这也会影响其实际运行时间。在评估算法时,需要综合考虑时间和空间复杂度。
  4. 范数选择的影响: 论文在证明中使用 2-范数,并指出“所有范数在有限维向量空间上都是等价的”。虽然理论上如此,但在实际算法中,选择不同的范数(如 1\ell_1\ell_\infty)可能会对正则化项、梯度计算和实际性能产生显著影响。未来的工作可以探索不同范数对 OFTRLCFR 框架下表现的影响。

相似论文推荐

基于向量语义检索推荐的相关论文。

暂时没有找到相似论文。