AiPaper
论文状态:已完成

Dynamic Discounted Counterfactual Regret Minimization (CFR) is a family of iterative algorithms showing promising results in solving imperfect-information games. Recent novel CFR variants (e.g., CFR+, DCFR) have significantly improved the convergence rate of the vanilla CFR. The key to these CFR variants’ performance is weighting each iteration non-uniformly, i.e., discounting earlier iterations. However, these algorithms use a fixed, manually-specified scheme to weight each iteration, which eno

原文链接
价格:0.10
已有 3 人读过
本分析由 AI 生成,可能不完全准确,请以原文为准。

TL;DR 精炼摘要

本文提出了动态折扣反事实遗憾最小化(DDCFR),这是首个通过动态学习方法对迭代进行折扣的框架。通过将CFR迭代过程形式化为马尔可夫决策过程,DDCFR实现了更快的收敛速度和更高的性能,具备强大的泛化能力,显著提升了解决不完全信息博弈的效率和潜力。

摘要

Hang Xu, Kai Li, Haobo Fu, Qiang Fu, Junliang Xing, Jian Cheng Counterfactual regret minimization (CFR) is a family of iterative algorithms showing promising results in solving imperfect-information games. Recent novel CFR variants (e.g., CFR+, DCFR) have significantly improved the convergence rate of the vanilla CFR. The key to these CFR variants’ performance is weighting each iteration non-uniformly, i.e., discounting earlier iterations. However, these algorithms use a fixed, manually-specified scheme to weight each iteration, which enormously limits their potential. In this work, we propose Dynamic Discounted CFR (DDCFR), the first equilibrium-finding framework that discounts prior iterations using a dynamic, automatically-learned scheme. We formalize CFR’s iteration process as a carefully designed Markov decision process and transform the discounting scheme learning problem into a policy optimization problem within it. The learned discounting scheme dynamically weights each iteration on the fly using information available at runtime. Extensive experimental results demonstrate that DDCFR’s dynamic discounting scheme has a strong generalization ability and leads to faster convergence with improved performance. The code is available at https://github.com/rpSebastian/DDCFR.

思维导图

论文精读

中文精读

1. 论文基本信息

1.1. 标题

动态折扣反事实遗憾最小化 (Dynamic Discounted Counterfactual Regret Minimization, DDCFR)

1.2. 作者

Hang Xu, Kai Li, Haobo Fu, Qiang Fu, Junliang Xing, Jian Cheng

他们的研究背景和隶属机构包括:

  • 中国科学院自动化研究所 (Institute of Automation, Chinese Academy of Sciences)
  • 中国科学院大学人工智能学院 (School of Artificial Intelligence, University of Chinese Academy of Sciences)
  • 中国科学院大学未来技术学院 (School of Future Technology, University of Chinese Academy of Sciences)
  • AiRiA
  • 清华大学 (Tsinghua University)
  • 腾讯人工智能实验室 (Tencent AI Lab)

1.3. 发表期刊/会议

论文的摘要和参考文献中未明确指出具体的发表期刊或会议,但从其引用了多篇 AAAI Conference on Artificial Intelligence 的论文(例如 Xu et al., 2022Farina et al., 2021),可以推断这篇论文很可能是在一个顶级的国际人工智能会议(如 AAAI)上发表或提交。

1.4. 发表年份

论文中未明确给出发表年份,但其参考文献列表中的最近年份是 Xu et al., 2022Zhang et al., 2022,这表明该工作是一项非常新的研究,很可能发表于 2022年或2023年

1.5. 摘要

反事实遗憾最小化 (Counterfactual Regret Minimization, CFR) 是一系列在解决不完全信息博弈 (imperfect-information games) 中展现出良好性能的迭代算法。近期涌现的 CFR 变体(例如 CFR+CFR+DCFR)显著提升了 Vanilla CFR 的收敛速度。这些 CFR 变体性能提升的关键在于对每次迭代进行非均匀加权,即对早期迭代进行折扣(discounting)。然而,这些算法都采用固定的、手动指定的方案来加权每次迭代,这极大地限制了它们的潜力。本文提出了动态折扣 CFR (Dynamic Discounted CFR, DDCFR),这是首个通过动态、自动学习的方案对先前迭代进行折扣的均衡求解框架。作者将 CFR 的迭代过程形式化为一个精心设计的马尔可夫决策过程 (Markov Decision Process, MDP),并将折扣方案学习问题转化为其中的策略优化问题。学习到的折扣方案能够利用运行时可用的信息,动态地加权每次迭代。广泛的实验结果表明,DDCFR 的动态折扣方案具有强大的泛化能力,并能带来更快的收敛速度和更高的性能。代码已在 https://github.com/rpSebastian/DDCFR 开源。

1.6. 原文链接

/files/papers/6913f6f32db53125aacc49fd/paper.pdf

2. 整体概括

2.1. 研究背景与动机

2.1.1. 核心问题:不完全信息博弈的求解挑战

不完全信息博弈 (Imperfect-Information Games, IIGs) 模拟了玩家之间存在隐藏信息的战略互动。这类博弈的求解极具挑战性,因为它要求玩家在不确定对手私有信息的情况下进行推理。由于隐藏信息在现实世界的决策问题中无处不在,因此 IIGs 的研究在理论和实践上都至关重要。本文专注于解决两人零和 IIGs,其典型目标是找到一个(近似)纳什均衡 (Nash equilibrium)。

2.1.2. CFR 及其变体的局限性

反事实遗憾最小化 (Counterfactual Regret Minimization, CFR) 算法家族是计算 IIGs 中纳什均衡最成功的方法之一。CFR 通过迭代地最小化玩家的遗憾,使时间平均策略配置文件逐渐接近纳什均衡。在过去十年中,研究人员提出了各种新颖的 CFR 变体(如 CFR+CFR+DCFR),它们显著提高了 Vanilla CFR 的收敛速度。这些 CFR 变体性能提升的关键在于它们采用不同的折扣方案,对每次迭代进行非均匀加权,即给早期迭代分配较小的权重。

然而,现有的 CFR 变体(如 CFR+CFR+DCFR)都依赖于固定的、手动指定的折扣方案

  • 局限一:次优性 (Suboptimality):理论上存在无限多的折扣方案,手动寻找一个在大多数博弈中都表现良好的方案是不切实际甚至不可能的,这导致手动指定的方案通常是次优的。
  • 局限二:缺乏灵活性 (Lack of Flexibility):固定的折扣方案在迭代过程开始前就已经确定,这过于限制。理想的方案应该能够利用运行时可用的信息,动态地调整每次迭代的权重。例如,在遗憾最小化算法中,折扣权重往往需要在学习过程中动态变化,这对于解决不同类型的 IIGs 尤为重要,因为遗憾值分布和采取次优行动的成本在迭代过程中会发生显著变化。

2.1.3. 本文的创新切入点

为了解决上述局限性,本文提出了一个核心思想:设计一个动态的、自动学习的折扣方案,使 CFR 算法能够根据运行时信息(如迭代次数和可利用性 exploitability)动态调整折扣权重,从而实现更高效、更有效的学习。

2.2. 核心贡献/主要发现

本文提出了 Dynamic Discounted CFR (DDCFR) 框架,其主要贡献和发现可以总结如下:

  • 提出了首个动态、自动学习的折扣框架 (Novel Framework)DDCFR 是第一个通过动态、自动学习的方案对先前迭代进行折扣的均衡求解框架。它解决了现有 CFR 变体使用固定、手动指定折扣方案的局限性。
  • CFR 迭代过程形式化为 MDP (Novel Formulation):作者将 CFR 的迭代过程抽象为一个精心设计的马尔可夫决策过程 (Markov Decision Process, MDP),从而将折扣方案的学习问题转化为该 MDP 中的策略优化问题。
  • 设计了高效的训练算法 (Effective Training Algorithm):为了优化折扣策略,作者设计了一种基于演化策略 (Evolution Strategies, ES) 的可扩展训练算法,以应对稀疏奖励、长时程和多任务学习等挑战。
  • 强大的泛化能力和性能提升 (Strong Generalization and Improved Performance):学习到的动态折扣方案在未参与训练的新博弈(包括大规模博弈,如德州扑克子博弈)上展现出强大的泛化能力。实验结果表明,DDCFR 实现了更快的收敛速度和改进的性能,在测试博弈上平均比 DCFR 减少了 42% 的可利用性。
  • 框架的通用性 (General Applicability)DDCFR 框架是通用的,可以作为性能增强器,以即插即用的方式应用于其他采用固定折扣规则的 CFR 变体,例如将其应用于 Predictive CFR+ (PCFR+) 产生了 Dynamic Predictive CFR+ (DPCFR+),进一步提升了性能。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 扩展式博弈 (Extensive-form games)

扩展式博弈 (Extensive-form games) 是一种常用的树状形式化方法,用于描述不完全信息博弈 (Imperfect-Information Games, IIGs)。在这种博弈中,有一个有限的玩家集合 N\mathcal{N},以及一个特殊的玩家 cc 称为机会玩家 (Chance Player),其具有固定且已知的随机策略。

  • 历史 (History) hh:由玩家采取的所有行动组成,包括只有部分玩家知道的私人信息。所有可能的历史构成了博弈树中的集合 H\mathcal{H}
  • 行动 (Actions) A(h)\mathcal{A}(h):在给定历史 hh 下可用的行动集合。
  • 终止历史 (Terminal Histories) ZH\mathcal{Z} \subseteq \mathcal{H}:没有更多行动可用的历史。
  • 效用函数 (Utility Function) ui(z)u_i(z):每个玩家 iNi \in \mathcal{N} 的效用函数,定义了在终止历史 zz 时的收益。效用范围为 [umin,umax]R[u_{\min}, u_{\max}] \subset \mathbb{R}Δ=umaxumin\Delta = u_{\max} - u_{\min} 是效用范围。

3.1.2. 信息集 (Information Sets)

IIGs 中,信息缺失通过每个玩家 iNi \in \mathcal{N} 的信息集 Ii\mathcal{I}_i 来表示。如果两个历史 h, h' 属于同一个信息集 IIiI \in \mathcal{I}_i,则玩家 ii 无法区分它们。例如,在扑克中,一个信息集内的所有历史只在其他玩家的私有牌上有所不同。因此,对于任意 hIh \in IA(I)=A(h)\mathcal{A}(I) = \mathcal{A}(h)

3.1.3. 策略 (Strategy)

玩家 ii 在信息集 II 中的策略 (strategy) σi(I)\sigma_i(I) 为可用行动分配一个概率分布。σi(I,a)\sigma_i(I, a) 表示玩家 ii 采取行动 aa 的概率。由于玩家 ii 无法区分同一信息集内的历史,因此该信息集内的策略必须相同。

  • 策略配置文件 (Strategy Profile) σ={σiσiΣi,iN}\sigma = \{\sigma_i | \sigma_i \in \Sigma_i, i \in \mathcal{N}\}:所有玩家策略的集合,其中 Σi\Sigma_i 是玩家 ii 所有可能策略的集合。σi\sigma_{-i} 指除玩家 ii 之外所有玩家的策略。
  • 预期效用 (Expected Utility) ui(σi,σi)u_i(\sigma_i, \sigma_{-i}):玩家 ii 按照 σi\sigma_i 玩,其他玩家按照 σi\sigma_{-i} 玩时,玩家 ii 的预期效用。

3.1.4. 最优响应 (Best Response) 与 纳什均衡 (Nash Equilibrium)

  • 最优响应 (Best Response) BR(σi)\mathrm{BR}(\sigma_{-i}):相对于其他玩家策略 σi\sigma_{-i} 的最优响应是任何能最大化玩家 ii 预期效用的策略,即 ui(BR(σi),σi)=maxσiΣiui(σi,σi)u_i(\mathrm{BR}(\sigma_{-i}), \sigma_{-i}) = \max_{\sigma_i' \in \Sigma_i} u_i(\sigma_i', \sigma_{-i})
  • 纳什均衡 (Nash Equilibrium) σ=(σi,σi)\sigma^* = (\sigma_i^*, \sigma_{-i}^*):一个策略配置文件,其中每个玩家都对其他玩家的策略采取最优响应。形式上,iN,ui(σi,σi)=maxσiΣiui(σi,σi)\forall i \in \mathcal{N}, u_i(\sigma_i^*, \sigma_{-i}^*) = \max_{\sigma_i' \in \Sigma_i} u_i(\sigma_i', \sigma_{-i}^*)
  • 可利用性 (Exploitability) ei(σi)e_i(\sigma_i):衡量策略 σi\sigma_i 偏离最优响应的程度。定义为 ei(σi)=ui(σi,σi)ui(σi,BR(σi))e_i(\sigma_i) = u_i(\sigma_i^*, \sigma_{-i}^*) - u_i(\sigma_i, \mathrm{BR}(\sigma_i))。在 ϵ\epsilon-纳什均衡 (epsilon-Nash equilibrium) 中,没有玩家的可利用性高于 ϵ\epsilon
  • 策略配置文件的可利用性 (Exploitability of a strategy profile)e(σˉ)=iNei(σˉi)/Ne(\bar{\sigma}) = \sum_{i \in \mathcal{N}} e_i(\bar{\sigma}_i) / |\mathcal{N}|。这可以解释为对纳什均衡的近似误差。

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

CFR 是解决扩展式 IIGs 最流行的均衡求解算法之一。该算法通过最小化玩家的遗憾来迭代地细化玩家的平均策略。

  • 反事实价值 (Counterfactual Value) viσ(I)v_i^\sigma(I):在给定策略配置文件 σ\sigma 下,玩家 ii 在信息集 IIiI \in \mathcal{I}_i 的预期效用,假设玩家试图到达该信息集。特定行动 aaII 中的反事实价值为 viσ(I,a)v_i^\sigma(I, a)
  • 瞬时遗憾 (Instantaneous Regret) rit(I,a)r_i^t(I, a):在第 tt 次迭代中,玩家 ii 在信息集 II 中未选择行动 aa 的遗憾,定义为: rit(I,a)=viσt(I,a)viσt(I) r_i^t(I, a) = v_i^{\sigma^t}(I, a) - v_i^{\sigma^t}(I) 其中,viσt(I,a)v_i^{\sigma^t}(I, a) 是在当前策略 σt\sigma^t 下选择行动 aa 的反事实价值,viσt(I)v_i^{\sigma^t}(I) 是在当前策略下在信息集 II 中的平均反事实价值。
  • 累积遗憾 (Cumulative Regret) Rit(I,a)R_i^t(I, a):在第 tt 次迭代时,对行动 aa 的累积遗憾,定义为 Rit(I,a)=k=1trik(I,a)R_i^t(I, a) = \sum_{k=1}^t r_i^k(I, a)
  • 策略更新 (Strategy Update)CFR 使用遗憾匹配 (regret-matching) 算法计算下一迭代的策略: σit+1(I,a)={Rit,+(I,a)aA(I)Rit,+(I,a),if aA(I)Rit,+(I,a)>01A(I),otherwise, \sigma_i^{t+1}(I, a) = \begin{cases} \frac{R_i^{t,+}(I, a)}{\sum_{a' \in \mathcal{A}(I)} R_i^{t,+}(I, a')}, & \mathrm{if~} \sum_{a' \in \mathcal{A}(I)} R_i^{t,+}(I, a') > 0 \\ \frac{1}{|\mathcal{A}(I)|}, & \mathrm{otherwise}, \end{cases} 其中 Rit,+(I,a)=max(Rit(I,a),0)R_i^{t,+}(I, a) = \max\left(R_i^t(I, a), 0\right) 表示正向累积遗憾。
  • 平均策略 (Average Strategy) σˉt\bar{\sigma}^tCFR 的核心是在多次迭代后,平均策略 σˉt\bar{\sigma}^t 会收敛到纳什均衡。平均策略的计算如下: Cit(I,a)=k=1t(πiσk(I)σik(I,a)), σˉit(I,a)=Cit(I,a)aA(I)Cit(I,a), C_i^t(I, a) = \sum_{k=1}^t \left( \pi_i^{\sigma^k}(I) \sigma_i^k(I, a) \right), ~ \bar{\sigma}_i^t(I, a) = \frac{C_i^t(I, a)}{\sum_{a' \in \mathcal{A}(I)} C_i^t(I, a')}, 其中 πiσk(I)\pi_i^{\sigma^k}(I) 是信息集 II 的可达概率 (reach probability),Cit(I,a)C_i^t(I, a) 是玩家 ii 在信息集 II 中行动 aa 的累积策略 (cumulative strategy) 在第 tt 次迭代时的值。

3.2. 前人工作

3.2.1. CFR+CFR+ (Tammelin, 2014)

CFR+CFR+CFR 的一个里程碑式变体,实践中比 Vanilla CFR 快一个数量级。它主要有三个改进:

  1. 线性折扣 (Linear Discounting)CFR+CFR+ 采用线性折扣方案,迭代 tt 对平均策略的贡献与 tt 成正比,而非 Vanilla CFR 的均匀加权。
  2. 负遗憾归零 (Negative Regret Reset):将任何负的累积遗憾设置为零,以便在行动显示出良好前景时立即重用,而不是等待累积遗憾变为正。
  3. 交替更新 (Alternating Updates):使用交替更新技术。

3.2.2. Discounted CFR (DCFR) (Brown & Sandholm, 2019b)

DCFR 算法更系统地研究了遗憾最小化算法中的折扣方案。它是一个算法家族,通过折扣累积遗憾和累积策略来显著加速收敛。 在迭代 tt 时,DCFR 通过乘以特定的因子来折扣正向累积遗憾、负向累积遗憾和累积策略:

  • 正向累积遗憾更新Rit(I,a)=Rit1(I,a)(t1)α(t1)α+1+rit(I,a),if Rit1(I,a)>0 R_i^t(I, a) = R_i^{t-1}(I, a) \frac{(t-1)^\alpha}{(t-1)^\alpha + 1} + r_i^t(I, a), \quad \mathrm{if~} R_i^{t-1}(I, a) > 0
  • 负向累积遗憾更新Rit(I,a)=Rit1(I,a)(t1)β(t1)β+1+rit(I,a),otherwise, R_i^t(I, a) = R_i^{t-1}(I, a) \frac{(t-1)^\beta}{(t-1)^\beta + 1} + r_i^t(I, a), \quad \mathrm{otherwise},
  • 累积策略更新Cit(I,a)=Cit1(I,a)(t1t)γ+πiσt(I)σit(I,a). C_i^t(I, a) = C_i^{t-1}(I, a) \left( \frac{t-1}{t} \right)^\gamma + \pi_i^{\sigma^t}(I) \sigma_i^t(I, a) . 其中 (α,β,γ)(\alpha, \beta, \gamma) 是三个超参数,它们决定了 DCFR 的折扣方案。例如,当 α=1,β=1,γ=1\alpha=1, \beta=1, \gamma=1 时,可以恢复线性折扣方案。DCFR 的作者经验性地将 α=1.5,β=0,γ=2\alpha=1.5, \beta=0, \gamma=2 设置为在他们测试的博弈中表现最佳的方案。

3.2.3. Greedy Weights (Zhang et al., 2022)

Greedy Weights 是一种最近提出的算法,专门为一般形式博弈 (normal-form games) 设计,通过根据运行时观察到的遗憾来贪婪地加权迭代。虽然它可以适用于扩展形式博弈,但作者发现在扩展形式博弈中其性能不如 DDCFR,这可能是因为它在面对大量信息集时计算的权重可能不合适。

3.2.4. Predictive CFR+ (PCFR+) (Farina et al., 2021)

PCFR+PCFR+ 是一种基于预测 Blackwell 可达性 (predictive Blackwell approachability) 的最先进 CFR 变体。它也使用固定的二次折扣方案,形式化为 (t1t)γ\left(\frac{t-1}{t}\right)^\gamma,其中 γ\gamma 通常设置为 2

3.2.5. PDCFR

PCFR+PCFR+ 论文中提出的 PDCFR 可以看作是 PCFR+PCFR+DCFR 的结合。PDCFR 也使用固定的折扣方案,并且在非扑克和扑克博弈中都表现良好,受益于从 PCFR+PCFR+DCFR 继承的特性。

3.3. 技术演进与差异化分析

CFR 算法在不完全信息博弈求解领域取得了巨大成功,其技术演进可以概括为从基础理论到性能优化,再到智能自动化。

  1. Vanilla CFR (Zinkevich et al., 2007):奠定了通过迭代最小化遗憾来求解纳什均衡的基础,但收敛速度相对较慢。
  2. CFR+CFR+ (Tammelin, 2014):引入了线性和负遗憾归零等概念,显著提升了实践中的收敛速度,是性能优化的一个重要里程碑。
  3. DCFR (Brown & Sandholm, 2019b):系统性地探索了折扣方案,通过引入超参数 α,β,γ\alpha, \beta, \gamma 来对累积遗憾和策略进行更精细的折扣,实现了目前最快的收敛速度之一。然而,CFR+CFR+DCFR 都依赖于固定的、手动指定的折扣方案。这些方案虽然有效,但其超参数需要人工调优,且在不同博弈中可能不是最优的,缺乏灵活性。

本文 DDCFR 的核心创新和差异化在于:

  • 动态学习而非固定指定DDCFR 突破了手动指定固定折扣方案的限制,首次提出了一个框架,能够通过机器学习自动学习动态调整折扣权重。

  • 运行时信息感知DDCFR 的折扣方案能够利用迭代次数和可利用性等运行时信息,在算法执行过程中实时调整折扣策略,使其更具适应性。

  • 通用框架DDCFR 不仅是一个具体的算法,更是一个通用的框架。它可以作为“性能增强器”应用于现有的多种 CFR 变体(如 PCFR+PCFR+PDCFR),提升它们的性能。

  • MDPES 优化:通过将 CFR 迭代过程建模为 MDP,并将折扣方案学习转化为策略优化问题,并利用演化策略 ES 进行优化,DDCFR 提供了一个全新的范式来设计和改进博弈求解算法。

    简而言之,之前的变体回答了“如何通过折扣来加速 CFR”,而 DDCFR 则更进一步,回答了“如何自动且动态地学习最优的折扣策略”。

4. 方法论

4.1. 方法原理

DDCFR 的核心思想是将 CFR 的迭代过程视为一个环境,将动态折扣方案视为一个与该环境交互的智能体 (agent)。智能体在每个迭代步骤接收当前状态(即 CFR 迭代过程的当前状态),并输出一个行动,该行动包含用于下一次迭代的折扣权重。这个过程一直持续到达到最大迭代次数。智能体的目标是找到一个最优的折扣策略 (discounting policy),该策略能够动态地为每次迭代选择合适的权重,从而最大限度地降低最终获得的平均策略的可利用性 (exploitability)。

通过这种方式,DDCFR 将折扣方案的学习问题转化为了一个强化学习 (Reinforcement Learning) 中的策略优化问题,并使用演化策略 (Evolution Strategies, ES) 进行求解。

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

DDCFR 框架将 CFR 的迭代过程形式化为一个马尔可夫决策过程 (Markov Decision Process, MDP),表示为 (G,S,A,PG,R^G)(G, S, A, P^G, \hat{R}^G)

4.2.1. 马尔可夫决策过程 (MDP) 的组成部分

  1. 博弈 (Game) GG:

    • DDCFR 框架中的每个博弈 GG 都代表一个不同的环境。
    • 最终目标是训练一个智能体,其折扣策略不仅在训练博弈中表现良好,还能泛化到新的、未见过的博弈中。
  2. 状态空间 (State Space) SS:

    • 在博弈 GG 的每个迭代 tt 中,智能体观察到的状态为 stSs_t \in S
    • sts_t 被设计为包含尽可能多的通用和可迁移信息,以帮助智能体在选择每次迭代的折扣权重时做出良好决策,并使学习到的方案适用于不同的博弈。
    • 作者提出了一个博弈无关 (game-agnostic) 的状态表示,它包含两个部分:
      • 归一化迭代次数 (Normalized Iteration) t^\hat{t}:当前迭代次数 tt 与总迭代次数 TT 的比值,即 t^=t/T\hat{t} = t/T
      • 归一化可利用性 (Normalized Exploitability) E^t1G\hat{E}_{t-1}^G:这是对前一迭代 t-1 时博弈 GG 中平均策略的可利用性 Et1GE_{t-1}^G 进行归一化的结果。计算公式为: E^t1G=logEt1GlogEminlogE1GlogEmin \hat{E}_{t-1}^G = \frac{\log E_{t-1}^G - \log E_{\min}}{\log E_1^G - \log E_{\min}} 其中:
        • E1GE_1^G 是博弈 GG 在第一次迭代时的可利用性。
        • Et1GE_{t-1}^G 是博弈 GG 在第 t-1 次迭代时的可利用性。
        • EminE_{\min} 是设定的最小可达可利用性,通常设为一个很小的值,例如 101210^{-12},以避免对数运算中的零值问题。
        • 采用对数操作是为了使归一化可利用性的分布更加均匀,从而有助于智能体的训练。
  3. 行动空间 (Action Space) AA:

    • 智能体在迭代 tt 时的行动 a^tA\hat{a}_t \in A 由四个数字组成:a^t=[αt,βt,γt,τt]\hat{a}_t = [\alpha_t, \beta_t, \gamma_t, \tau_t]
    • αt,βt,γt\alpha_t, \beta_t, \gamma_t:这些参数用于确定折扣权重,类似于 DCFR 中的超参数。
      • 折扣正向累积遗憾的权重:(t1)αt(t1)αt+1\frac{(t-1)^{\alpha_t}}{(t-1)^{\alpha_t} + 1}
      • 折扣负向累积遗憾的权重:(t1)βt(t1)βt+1\frac{(t-1)^{\beta_t}}{(t-1)^{\beta_t} + 1}
      • 折扣累积策略的权重:(t1t)γt\left(\frac{t-1}{t}\right)^{\gamma_t}
    • τt\tau_t:表示使用这些折扣权重进行 CFR 迭代的持续时长。引入 τt\tau_t 可以提高学习方案的可解释性,表明超参数是否需要频繁调整。
    • DCFR 的关键区别在于,DDCFR 可以利用 a^t\hat{a}_t 在运行时动态调整折扣权重,并自适应地控制每个博弈的迭代过程,而 DCFR 使用固定的预设值。
  4. 状态转移 (State Transition) PGP^G:

    • PG:S×ASP^G: S \times A \to S 描述了在博弈 GGDDCFR 迭代过程中状态如何变化。
    • 具体来说,智能体在迭代 tt 时观察当前状态 sts_t,并输出行动 a^t\hat{a}_t
    • DDCFR 然后使用由 αt,βt,γt\alpha_t, \beta_t, \gamma_t 计算出的折扣权重进行 τt\tau_t 次迭代。
    • 最终,状态转移到下一个状态 st+τts_{t+\tau_t}。这个过程允许连续使用每组折扣权重进行一定数量的迭代。
  5. 奖励函数 (Reward Function) R^G\hat{R}^G:

    • R^G\hat{R}^G 用于评估智能体的性能并指导 DDCFR 的迭代过程。

    • 由于智能体的最终目标是找到一个可利用性最低的策略配置文件,因此作者采用了稀疏奖励 (sparse reward) 设置,即智能体只在迭代过程结束时收到奖励。

    • 具体地,奖励定义为: R^G=logE1GlogETG \hat{R}^G = \log E_1^G - \log E_T^G 其中 E1GE_1^G 是博弈 GG 在第一次迭代时的可利用性,ETGE_T^G 是在最大迭代次数 TT 时博弈 GG 中平均策略的可利用性。

    • 智能体通常由一个参数为 θ\pmb{\theta} 的神经网络 πθ:SA\pi_{\pmb{\theta}}: S \to A 表示。

    • 在每个博弈 GG 中,目标是最大化最终奖励 R^G\hat{R}^G,表示为 fG(θ)=R^Gf^G(\pmb{\theta}) = \hat{R}^G

    • DDCFR 的总目标是最大化所有训练博弈 G\mathbb{G} 上的平均奖励,即: f(θ)=1GGGfG(θ) f(\pmb{\theta}) = \frac{1}{|\mathbb{G}|} \sum_{G \in \mathbb{G}} f^G(\pmb{\theta})

    • 通过优化 f(θ)f(\pmb{\theta}),最终目标是学习一个能够泛化到新博弈的折扣策略。

      下图(原文 Figure 1)展示了 DDCFR 框架的整体迭代过程:

      Figure 1: The DDCFR framework. 该图像是示意图,展示了动态折扣反事实遗憾最小化(DDCFR)框架的工作原理。图中包含多个组件,如迭代归一化、状态、动作、以及环境中的博弈 GG。各部分颜色编码表示了当前策略、瞬时遗憾、累积遗憾更新、策略匹配等关键步骤,以及奖励信号的反馈机制。整体框架表明如何动态调整策略以提高收敛速度和性能。

4.2.2. 理论分析 (Theoretical Analysis)

尽管 DDCFR 的动态折扣方案高度灵活,但其收敛性是一个关键问题。作者理论上证明了只要 αt,βt,γt\alpha_t, \beta_t, \gamma_t 在特定范围内,DDCFR 就能保证收敛到纳什均衡。

定理 1 (Theorem 1): 假设在两人零和博弈中进行 TTDDCFR 迭代。如果 DDCFR 按照以下方式选择超参数:

  • t<T2t < \frac{T}{2}αt[0,5]\alpha_t \in [0, 5]

  • tT2t \geq \frac{T}{2}αt[1,5]\alpha_t \in [1, 5]

  • βt[5,0]\beta_t \in [-5, 0]

  • γt[0,5]\gamma_t \in [0, 5]

    那么,加权平均策略将收敛到 O(I2AΔ2/ϵ2)\mathcal{O}\left( {|\mathcal{I}|^2 |\mathcal{A}| \Delta^2 } / {\epsilon^2} \right) 的纳什均衡,其中可利用性为 6TΔ(83A+2T)/T\begin{array} { r } { 6 | \mathcal { T } | \Delta \left( \frac { 8 } { 3 } \sqrt { | \mathcal { A } | } + \frac { 2 } { \sqrt { T } } \right) / \sqrt { T } } \end{array}

  • 证明:证明主要基于 DCFR 的证明,通过重新缩放基于 αt,βt,γt\alpha_t, \beta_t, \gamma_t 范围的不等式。

  • 意义:该定理表明,理论上存在大量动态折扣方案能够收敛。

4.2.3. 通过演化策略 (Evolution Strategies) 进行优化

在训练折扣策略 πθ\pi_{\pmb{\theta}} 时,DDCFR 面临以下挑战:

  • 稀疏奖励 (Sparse Reward):智能体只在迭代过程结束时才收到奖励。

  • 长时程 (Long Time Horizons)CFR 需要数千次迭代。

  • 多任务学习 (Multi-task Learning):智能体需要在各种博弈中最大化奖励。

    传统的强化学习 (Reinforcement Learning, RL) 算法(如 DQNPPO)在应对这些挑战时可能表现不佳。演化策略 (Evolution Strategies, ES) (Wierstra et al., 2014; Salimans et al., 2017) 作为 RL 的一种可扩展替代方案,已在解决这些问题上展现出其有效性。ES 作为一种黑盒优化技术,对奖励分布不敏感,并能容忍任意长的时程。此外,ES 易于实现,并且在分布式硬件上具有高度可扩展性和效率。

ES 在优化复杂目标函数和解决 RL 相关问题方面的有效性启发,作者设计了一个基于 ES 的算法来训练折扣策略 πθ\pi_{\pmb{\theta}}

Salimans et al., 2017 中提出的 ES 方法指出,对于网络参数为 θ\pmb{\theta} 的目标函数 f(θ)f(\pmb{\theta}),其梯度估计可以通过对 θ\pmb{\theta} 应用高斯扰动获得: θEϵN(0,I)fˉ(θ+δϵ)=1δEϵN(0,I)f(θ+δϵ)ϵ \nabla_{\pmb{\theta}} \mathbb{E}_{\epsilon \sim \mathcal{N}(0,I)} \bar{f}(\pmb{\theta} + \delta\epsilon) = \frac{1}{\delta} \mathbb{E}_{\epsilon \sim \mathcal{N}(0,I)} f(\pmb{\theta} + \delta\epsilon) \epsilon 其中:

  • δ\delta 表示噪声标准差。

  • N(0,I)\mathcal{N}(0,I) 是均值为 0、协方差为 II 的高斯分布。

  • 这个梯度估计可以通过采样进行近似。在每个 epoch 中,生成一组扰动网络参数,并在所有训练博弈下评估其性能,然后结合结果计算梯度并使用随机梯度上升 (stochastic gradient ascent) 更新原始参数。

    为了提高训练过程的效率,作者采用了三种加速技术:

  1. 对偶估计器 (Antithetic Estimator):用于减少方差。这是一个无偏估计器,通过对称差分给出: θEϵN(0,I)f(θ+δϵ)=12δEϵN(0,I)[f(θ+δϵ)f(θδϵ)]ϵ˙ \nabla_{\theta} \mathbb{E}_{\epsilon \sim \mathcal{N}(0,I)} f\big(\theta + \delta\epsilon\big) = \frac{1}{2\delta} \mathbb{E}_{\epsilon \sim \mathcal{N}(0,I)} \left[ f\big(\theta + \delta\epsilon\big) - f\big(\theta - \delta\epsilon\big) \right] \dot{\epsilon}

  2. 适应度塑形 (Fitness Shaping):通过在计算梯度之前对目标函数 f(θ)f(\pmb{\theta}) 进行秩变换 (rank transformation) 来应用适应度塑形。对于在大小为 NN 的种群中具有第 kk 大值的参数 θk\theta_k,塑形后的结果如下: f(θk)=max(0,log(N2+1)log(k))j=1Pmax(0,log(N2+1)log(j))1N. f^\prime(\theta_k) = \frac{\operatorname{max}\left(0, \log\left(\frac{N}{2} + 1\right) - \log(k)\right)}{\sum_{j=1}^{P} \operatorname{max}\left(0, \log\left(\frac{N}{2} + 1\right) - \log(j)\right)} - \frac{1}{N} . 这种方法使梯度只与参数适应度值的相对排序相关,而非其绝对大小,从而使算法对原始适应度值的变化更具鲁棒性。

  3. 并行评估 (Parallel Evaluation):为了进一步加速训练,在并行环境下评估每个扰动参数在每个博弈中的性能。

    以下是 DDCFR 训练过程的算法 (Algorithm 1):

算法 1:DDCFR 的训练过程

  • 输入: 训练博弈集合 G\mathbb{G}, 轮次 MM, 学习率 lr, 种群大小 NN, 标准差 δ\delta
  1. 随机初始化智能体参数 θˇ1\check{\pmb{\theta}}^1
  2. for m=1m = 1 to MM do
  3.  初始化种群 P\mathbb{P} 为空列表;
    
  4.  **for** i=1,,N2i = 1, \ldots, \frac{N}{2} **do**
    
  5. N(0,I)\mathcal{N}(0, I) 中采样 ϵi\epsilon_i
  6. ϵi,ϵi\epsilon_i, -\epsilon_i 添加到种群 P\mathbb{P}
  7.  **foreach** ϵP\epsilon \in \mathbb{P} **do**
    
  8.      **foreach** GGG \in \mathbb{G} **do**
    
  9.          计算 fG(θm+δϵ)f^G({\pmb{\theta}}^m + \delta {\pmb{\epsilon}}) (算法 2);
    
  10.     f(θm+δϵ)1GGGfG(θm+δϵ)f({\pmb{\theta}}^m + \delta {\pmb{\epsilon}}) \gets \frac{1}{|\mathbb{G}|} \sum_{G \in \mathbb{G}} f^G({\pmb{\theta}}^m + \delta {\pmb{\epsilon}})
  11. 使用等式 5 计算 f(θm+δϵ)f'({\pmb{\theta}}^m + \delta {\pmb{\epsilon}})
  12. θm+1θm+lrδNϵPf(θm+δϵ)ϵ{\pmb{\theta}}^{m+1} \gets {\pmb{\theta}}^m + \frac{lr}{\delta \cdot N} \sum_{\epsilon \in \mathbb{P}} f'({\pmb{\theta}}^m + \delta {\pmb{\epsilon}}) {\pmb{\epsilon}}
    
  • 输出: 训练好的智能体 πθM+1\pi_{{\pmb{\theta}}^{M+1}}

    以下是 fG(θ)f^G(\pmb{\theta}) 计算过程的算法 (Algorithm 2):

算法 2:fG(θ)f^G(\pmb{\theta}) 的计算过程

  • 输入: 训练博弈 GG, 智能体 πθ\pi_{\theta}, 总迭代次数 TT
  1. t1t \gets 1
  2. while tTt \leq T do
  3.  [αt,βt,γt,τt]=a^t=πθ(st)[\alpha_t, \beta_t, \gamma_t, \tau_t] = \hat{a}_t = \pi_{\pmb{\theta}}(s_t)
  4.  使用 [αt,βt,γt][\alpha_t, \beta_t, \gamma_t] 计算折扣权重并执行 τt\tau_t 次 `CFR` 迭代;
    
  5.  tt+τtt \gets t + \tau_t
  6. 计算可利用性 E1G,ETGE_1^G, E_T^G
  • 输出: fG(θ)=logE1GlogETGf^G({\pmb{\theta}}) = \log E_1^G - \log E_T^G

4.2.4. 额外计算成本分析 (Additional Computation Cost Analysis)

DCFR 相比,DDCFR 引入了额外的计算成本,主要包括三个部分:

  1. 特征计算 (Feature Calculations):状态表示需要迭代次数和可利用性。迭代次数容易获得。可利用性计算和瞬时遗憾计算是完全独立的,可以使用多进程并发执行,而不会增加实际运行时间 (wall-clock time)。
  2. 网络推理 (Network Inference):策略网络 πθ\pi_{\pmb{\theta}} 的时间开销相对于整体迭代时间可以忽略不计。实验结果表明,DDCFR 平均只增加了 0.22% 的时间。
  3. 策略训练 (Policy Training):训练所付出的努力是值得的,因为训练好的折扣策略可以直接应用于大量新博弈而无需修改。这意味着训练期间的额外工作可以在策略应用于各种博弈时得到分摊。

5. 实验设置

5.1. 数据集

实验使用了研究社区中几种常用的不完全信息博弈 (IIGs)。

5.1.1. 训练博弈

为了加速训练过程,同时确保训练博弈能展现测试博弈的典型特征,作者选择了以下四种相对较小的训练博弈:

  • Kuhn Poker (Kuhn, 1950):简化版扑克,三张牌,每个玩家一次下注机会。
  • Goofspiel-3 (Ross, 1971):纸牌游戏,每个玩家有3张牌,进行3轮秘密出价。
  • Liar's Dice-3 (Lisy et al., 2015):吹牛骰子,每个玩家有一个3面骰子。
  • Small Matrix:一个小型矩阵博弈,玩家1有五种行动,玩家2有三种行动,包含高损失行动。它模拟了博弈中非理性行动导致巨大损失的常见情况。 这些训练博弈在规则和规模上具有多样性,这对于提高泛化能力至关重要。

5.1.2. 测试博弈

作者选择了八个相对较大的 IIGs 作为测试博弈。这些博弈在规模上具有多样性且求解具有挑战性,适合测试学习到的折扣方案的泛化性能。

  • Battleship-2 (Farina et al., 2019):战舰游戏,玩家在 2×22 \times 2 网格上放置 1×21 \times 2 船只。
  • Battleship-3:战舰游戏,玩家在 2×32 \times 3 网格上放置 1×21 \times 2 船只。
  • Goofspiel-4:纸牌游戏,每个玩家有4张牌,进行4轮秘密出价。
  • Liar's Dice-4:吹牛骰子,每个玩家有一个4面骰子。
  • Leduc Poker (Southey et al., 2005):较大的扑克游戏,6张牌,两轮下注。
  • Big Leduc Poker:更复杂的扑克版本,24张牌,12个等级,每轮最多6次加注。
  • HUNL Subgame-3:由顶尖扑克智能体 Libratus 生成的无限注德州扑克 (Heads-Up No-Limit Texas Hold'em, HUNL) 子博弈,从最后一轮下注开始,底池为 500。
  • HUNL Subgame-4HUNL 子博弈,从最后一轮下注开始,底池为 3,750。

5.1.3. 博弈规模

下表(原文 Table 4)衡量了这些博弈在多个维度的规模:

  • #Histories 衡量博弈树中的历史数量。

  • #Infosets 衡量博弈树中的信息集数量。

  • #Terminal histories 衡量博弈树中的终止历史数量。

  • Depth 衡量博弈树的深度,即一个历史中最大行动数量。

  • Max size of infosets 衡量属于同一信息集的历史最大数量。

    以下是原文 Table 4 的结果:

    Game #Histories #Infosets #Terminal histories Depth Max size of infosets
    Small Matrix 21 2 15 3 5
    Kuhn Poker 58 12 30 6 2
    Goofspiel-3 67 16 36 5 4
    Liar's Dice-3 1,147 192 567 10 3
    Battleship-2 10,069 3,286 5,568 9 4
    Battleship-3 732,607 81,027 552,132 9 7
    Goofspiel-4 1,077 162 576 7 14
    Liar's Dice-4 8,181 1024 4,080 12 4
    Leduc Poker 9,457 936 5,520 12 5
    Big Leduc Poker 6,178,561 100,800 3,953,424 20 23
    HUNL Subgame-3 398,112,843 69,184 261,126,360 10 1,980
    HUNL Subgame-4 244,005,483 43,240 158,388,120 8 1,980

5.2. 评估指标

本文的核心评估指标是可利用性 (Exploitability)

  1. 概念定义 (Conceptual Definition): 可利用性是衡量一个策略配置文件 (σ\sigma) 距离纳什均衡 (Nash Equilibrium) 有多远的度量。它量化了如果一个玩家知道其他玩家的策略,并可以单方面地改变自己的策略以最大化其效用,那么该玩家可以获得的额外收益。如果一个策略配置文件的可利用性接近零,则意味着该策略配置文件是一个近似纳什均衡,因为任何玩家都很难通过单方面改变策略来获得显著优势。在两人零和博弈中,可利用性通常是衡量算法性能和收敛程度的关键指标。
  2. 数学公式 (Mathematical Formula): 策略配置文件 σ\sigma 的可利用性 e(σˉ)e(\bar{\sigma}) 计算公式如下: e(σˉ)=1NiNei(σˉi) e(\bar{\sigma}) = \frac{1}{|\mathcal{N}|} \sum_{i \in \mathcal{N}} e_i(\bar{\sigma}_i) 其中,每个玩家 ii 的可利用性 ei(σi)e_i(\sigma_i) 定义为: ei(σi)=ui(σi,σi)ui(σi,BR(σi)) e_i(\sigma_i) = u_i(\sigma_i^*, \sigma_{-i}^*) - u_i(\sigma_i, \mathrm{BR}(\sigma_i)) 在实际计算中,通常简化为衡量当前策略与最优响应策略之间的差距: ei(σˉi)=maxσiΣiui(σi,σˉi)ui(σˉi,σˉi) e_i(\bar{\sigma}_i) = \max_{\sigma_i' \in \Sigma_i} u_i(\sigma_i', \bar{\sigma}_{-i}) - u_i(\bar{\sigma}_i, \bar{\sigma}_{-i}) 最终的 exploitability 则是所有玩家 exploitability 的平均值。
  3. 符号解释 (Symbol Explanation)
    • e(σˉ)e(\bar{\sigma}):策略配置文件 σˉ\bar{\sigma} 的总可利用性。
    • N|\mathcal{N}|:博弈中的玩家数量。
    • ei(σˉi)e_i(\bar{\sigma}_i):玩家 ii 的策略 σˉi\bar{\sigma}_i 的可利用性。
    • σˉ\bar{\sigma}:当前的平均策略配置文件。
    • σˉi\bar{\sigma}_i:玩家 ii 在策略配置文件 σˉ\bar{\sigma} 中的策略。
    • σˉi\bar{\sigma}_{-i}:除玩家 ii 之外的其他玩家在策略配置文件 σˉ\bar{\sigma} 中的策略。
    • ui(,)u_i(\cdot, \cdot):玩家 ii 的预期效用函数。
    • maxσiΣiui(σi,σˉi)\max_{\sigma_i' \in \Sigma_i} u_i(\sigma_i', \bar{\sigma}_{-i}):当其他玩家遵循 σˉi\bar{\sigma}_{-i} 时,玩家 ii 可以通过选择最优策略 σi\sigma_i' 获得的最大效用。这实际上就是玩家 iiσˉi\bar{\sigma}_{-i} 的最优响应的效用。
    • ui(σˉi,σˉi)u_i(\bar{\sigma}_i, \bar{\sigma}_{-i}):当所有玩家都遵循当前平均策略 σˉ\bar{\sigma} 时,玩家 ii 获得的效用。

5.3. 对比基线

论文将 DDCFR 与以下多种 CFR 变体和相关算法进行了比较:

  • CFR+CFR+ (Tammelin, 2014):一个重要的 CFR 变体,通过线性折扣和负遗憾归零等改进显著加速收敛。
  • DCFR (Brown & Sandholm, 2019b):一个更系统地探索折扣方案的 CFR 家族算法,使用固定超参数 (α=1.5,β=0,γ=2)(\alpha=1.5, \beta=0, \gamma=2),在多种 IIGs 中表现优异。
  • Greedy Weights (Zhang et al., 2022):一种为一般形式博弈设计的动态加权算法,也尝试根据运行时遗憾调整权重。作者将其改编用于扩展形式博弈。
  • Predictive CFR+ (PCFR+) (Farina et al., 2021):基于预测 Blackwell 可达性的最先进 CFR 变体,使用固定二次折扣方案。
  • PDCFR (Farina et al., 2021)PCFR+PCFR+DCFR 的结合,旨在在不同类型的博弈中都表现良好。

5.4. 训练细节

  • 噪声标准差 (Noise Standard Deviation):固定设置为 δ=0.5\delta = 0.5
  • 种群大小 (Population Size)N=100N = 100
  • 计算资源 (Computational Resources):扰动参数的评估分布在 200 个 CPU 核心上并行进行。
  • 行动空间 (Action Space) 范围
    • α\alphaγ\gamma 的范围设置为 [0, 5]
    • β\beta 的范围设置为 [5,0][-5, 0],这遵循了定理 1 中给出的理论收敛范围。
    • τ\tau(折扣权重的使用时长)的选择范围为 {1,2,5,10,20}\{1, 2, 5, 10, 20\}
  • 策略网络架构 (Policy Network Architecture)
    • 智能体 (agent) 的折扣策略 πθ\pi_{\pmb{\theta}} 由一个包含三层全连接层 (fully-connected layers) 的神经网络表示。
    • 每层包含 64 个单元 (units)。
    • 激活函数使用 ELU
    • 网络以环境的当前状态作为输入,输出 α,β,γ\alpha, \beta, \gamma 的值,以及选择每个 τ\tau 值的概率。
  • 优化器 (Optimizer):使用 Adam 优化器。
  • 学习率 (Learning Rate)lr=0.01lr = 0.01
  • 训练轮次 (Epochs):智能体训练了 M=1000M = 1000epochs,大约耗时 24 小时。
  • CFR 迭代次数 (CFR Iterations)CFR 迭代的总次数 TT 设置为 1000,这通常足以使算法收敛到较小的可利用性。
  • 更新技术 (Update Technique):所有使用的 CFR 变体都采用了交替更新 (alternating-updates) 技术。

6. 实验结果与分析

6.1. 核心结果分析

6.1.1. 与折扣 CFR 变体的比较

作者在训练博弈和测试博弈上比较了 DDCFRCFR+CFR+DCFR 的性能。由于 CFR 算法在早期迭代中可利用性会迅速下降,因此算法之间的差异主要体现在后期迭代中。为了更好地比较,主要关注 500 到 1000 次迭代的表现。

下图(原文 Figure 2)展示了 DDCFR 在四个训练博弈上的表现:

Figure 3: Comparison of DDCFR against two discounting CFR variants on eight testing games. 该图像是图表,展示了DDCFR与两个折扣CFR变体在八个测试游戏中的可利用性(exploitability)对比。图中包含不同算法在迭代次数(Iterations)变化下的表现,强调了DDCFR在速度和性能上的优势。

  • 训练博弈表现:如上图所示,DDCFR 在训练博弈上收敛得更快,并达到更低的可利用性。这是预期结果,因为 DDCFR 就是针对这些博弈进行优化的。

    下图(原文 Figure 3)展示了 DDCFR 在八个测试博弈上的表现:

    Figure 4: The learned discounting scheme behaves differently in various games yet exhibits a similar trend. Compared with DCFR's fixed discounting scheme (we can view DCFR as a special case of DDCFR,… 该图像是图表,展示了动态折扣CFR (DDCFR) 中不同参数 αt\alpha_tβt\beta_tγt\gamma_tτt\tau_t 的值随迭代次数变化的趋势。各条线代表不同游戏(如“小矩阵”、“谎言骰子3”、“战舰3”、“大Leduc扑克”以及“所有游戏”)中的表现。与固定折扣方案DCFR相比,DDCFR在早期迭代时表现出更激进的折扣策略,随着迭代的进行变得更加温和。

  • 测试博弈泛化能力:即使在未见过的测试博弈中,DDCFR 仍然能与 CFR+CFR+DCFR 等其他 CFR 变体取得具有竞争力的性能。这表明 DDCFR 具有很强的泛化能力,因为它在设计时就考虑了泛化。

  • 性能提升:与 DCFR 相比,DDCFR 的可利用性平均降低了 42%,考虑到 DCFR 本身已经非常强大,这一提升是显著的。

  • 动态调整优势:与使用固定手动指定折扣方案的 CFR+CFR+DCFR 不同,DDCFR 通过学习到的动态折扣方案,能够利用运行时信息动态调整折扣权重,从而在所有博弈中取得更好的性能。

    在附录中,作者也展示了所有迭代的性能曲线。 下图(原文 Figure 5)展示了 DDCFR 和折扣 CFR 变体在四个训练博弈中的所有迭代结果:

Figure 6: All iterations of DDCFR and discounting CFR variants on eight testing games. 该图像是一个展示不同CFR算法在八个测试游戏上的可利用性(Exploitability)变化的图表。图中展示了CFR+、DCFR和DDCFR的迭代过程,横轴为迭代次数,纵轴为可利用性。DDCFR的动态折扣方案显著改善了收敛速度。

下图(原文 Figure 6)展示了 DDCFR 和折扣 CFR 变体在八个测试博弈中的所有迭代结果:

Figure 7: Performance comparison between DDCFR and GreedyWeights on extensive-form games. 该图像是图表,展示了DDCFR与GreedyWeights在四种扩展形式游戏(Battleship-2, Liar's Dice-4, Kuhn Poker, Leduc Poker)中的表现对比。横坐标为迭代次数,纵坐标为可利用性(Exploitability)。可以看到DDCFR在迭代过程中可利用性逐渐降低,表现优于GreedyWeights。

6.1.2. 学习到的动态折扣方案行为分析

为了进一步理解学习到的动态折扣方案 πθ\pi_{\pmb{\theta}} 的行为,作者可视化了其在迭代过程中的行动(即 αt,βt,γt,τt\alpha_t, \beta_t, \gamma_t, \tau_t)。 下图(原文 Figure 4)展示了学习到的折扣方案在不同博弈中的行为:

Figure 5: All iterations of DDCFR and discounting CFR variants on four training games. 该图像是一个图表,展示了在四个训练游戏上,DCFR和不同折扣CFR变体的所有迭代结果。图中横轴为迭代次数,纵轴为可利用性,分别显示了CFR+、DCFR和DDCFR在小矩阵、Kuhn扑克、Goofspiel-3和Liar's Dice-3中的性能表现。

  • 参数趋势:上图显示,πθ\pi_{\pmb{\theta}} 输出的行动在不同博弈中具有不同的值,但呈现出相似的趋势。具体来说,αt\alpha_t 随迭代次数增加,而 βt\beta_tγt\gamma_t 则随迭代次数减少。
  • DCFR 比较:与 DCFR 的固定折扣方案(可视为 DDCFR 的特例,其中 α1=1.5,β1=0,γ1=2\alpha_1=1.5, \beta_1=0, \gamma_1=2,持续时间 τ1=\tau_1=\infty)相比,学习到的方案在早期迭代中更具侵略性。
    • 较小的 α\alpha 和较大的 γ\gamma 会导致正向累积遗憾和累积策略的权重更小,这意味着对早期迭代的折扣更强。
    • 这可能是因为在早期迭代中,基于对手策略的最佳策略频繁变化,因此需要给予早期迭代更小的权重。
  • 后期迭代行为:随着迭代的进行,该方案变得更加温和,这可能有助于平均策略的收敛。
  • 负遗憾折扣:该方案在折扣负向累积遗憾时始终使用更具侵略性的策略(即更小的 β\beta 值)。这有利于更快地重用有前景的行动,而不是等待累积遗憾变为正。
  • τt\tau_t 变化τt\tau_t 的变化表明,在早期迭代中折扣权重需要更频繁地调整。

6.1.3. 与 Greedy Weights 的比较

作者将 DDCFRGreedy Weights (Zhang et al., 2022) 在扩展形式博弈中进行了比较。 下图(原文 Figure 7)展示了 DDCFRGreedy Weights 在扩展形式博弈中的性能比较:

Figure 8: Performance comparison between DDCFR and \(\\mathrm { P C F R + }\) on four testing games. 该图像是图表,展示了DDCFR与PCFR+在四个测试游戏(Leduc Poker、Big Leduc Poker、Goofspiel-4和Liar's Dice-4)中的表现比较。图中显示了随着迭代次数的增加,两个算法的可利用性(Exploitability)变化趋势。

  • DDCFR 显著优于 Greedy Weights:如上图所示,DDCFR 在四个扩展形式博弈中始终收敛得更快,并达到更低的可利用性。
  • 原因分析:尽管 Greedy Weights 旨在高效解决一般形式博弈,并且在扩展形式博弈中也显示出潜力,但专门为扩展形式博弈设计的 DDCFR 表现显著优于它。作者推测,当面对大量信息集时,Greedy Weights 中计算的权重可能不合适,导致在扩展形式博弈中表现不佳。

6.1.4. 与其他 CFR 变体的组合

DDCFR 提出的动态折扣框架具有通用性,可以应用于任何采用固定手动指定折扣规则的 CFR 变体。

  • PCFR+PCFR+ 结合 (DPCFR+DPCFR+)

    • PCFR+PCFR+ (Farina et al., 2021) 是一种最先进的 CFR 变体,但其性能并非始终如一。研究发现 PCFR+PCFR+ 在非扑克博弈上比 DCFR 快,但在扑克博弈上 DCFR 最快。

    • 下图(原文 Figure 8)展示了 DDCFRPCFR+PCFR+ 在四个测试博弈中的性能比较:

      Figure 9: Performance comparison between DPCFR \(^ +\) and \(\\mathrm { P C F R + }\) on four testing games. 该图像是一个图表,展示了DPCFR +^+ 和 PCFR+ 在四个测试游戏中的性能比较。图中标示了每次迭代的可利用性(Exploitability)变化,数据点分别来自Leduc Poker、Big Leduc Poker、Goofspiel-4 和 Liar's Dice-4。

    • 结果符合预期,PCFR+PCFR+ 在非扑克博弈(如 Goofspiel-4Liar's Dice-4)中收敛更快,而 DDCFR 在扑克博弈(如 Leduc PokerBig Leduc Poker)中表现更优,这与 DDCFR 基于 DCFR 构建的事实一致。

    • DDCFR 能够提升 DCFR 的性能,缩小与 PCFR+PCFR+ 在非扑克博弈上的差距,同时扩大在扑克博弈上的优势。

    • PCFR+PCFR+ 也使用固定的二次折扣方案 (t1t)γ\left(\frac{t-1}{t}\right)^\gamma,其中 γ\gamma 设为 2。将 DDCFR 框架应用于 PCFR+PCFR+ 产生了 动态预测 CFR+ (Dynamic Predictive CFR+, DPCFR+) 算法。

    • 下图(原文 Figure 9)展示了 DPCFR+DPCFR+PCFR+PCFR+ 在四个测试博弈中的性能比较:

      Figure 10: Performance comparison between PDDCFR and PDCFR on four testing games. 该图像是一个比较图表,展示了在四个测试游戏(Leduc Poker、Big Leduc Poker、Goofspiel-4、Liar's Dice-4)中,PDDCFR与PDCFR算法在迭代过程中的可利用性(Exploitability)变化情况。图中可以看到,PDDCFR在多个迭代次数下表现出更低的可利用性。

    • 上图表明,这种结合可以进一步释放 PCFR+PCFR+ 在解决非扑克博弈方面的潜力,同时不牺牲其在扑克博弈上的性能。

  • PDCFR 结合 (PDDCFR)

    • PDCFR 可以视为 PCFR+PCFR+DCFR 的结合,它也使用固定折扣方案,并在非扑克和扑克博弈中都表现良好。

    • DDCFR 框架应用于 PDCFR 产生了 预测动态折扣 CFR (Predictive Dynamic Discounted CFR, PDDCFR) 算法。

    • 下图(原文 Figure 10)展示了 PDDCFRPDCFR 在四个测试博弈中的性能比较:

      Figure 2: Comparison of DDCFR against two discounting CFR variants on four training games. 该图像是一个图表,展示了DDCFR与两种折扣CFR变体在四个训练游戏中的可剥离性表现。图中比较了CFR+、DCFR和DDCFR在不同迭代次数下的结果,包括小矩阵、Kuhn扑克牌、Goofspiel-3和Liar's Dice-3。

    • 如上图所示,DDCFR 框架显著增强了 PDCFR 在非扑克和扑克博弈中的性能。

  • 通用性结论:所有上述结果都证明了 DDCFR 动态折扣框架的通用适用性。它可以被视为一个性能增强器,以即插即用 (plug-and-play) 的方式应用于各种采用固定折扣规则的 CFR 变体。

6.2. 数据呈现 (表格)

6.2.1. 运行时间比较

为了支持 DDCFR 额外计算成本可忽略的声明,作者比较了 DCFRDDCFR 的运行时间。以下是原文 Table 2 的结果:

Game DCFR_time DDCFR_time (DDCFR_time -DCFR_time) / DCFR_time
Battleship-2 0:14:54.558 0:14:55.814 0.140%
Battleship-3 11:10:46.895 11:12:05.156 0.194%
Goofspiel-4 00:01:03.259 00:01:03.518 0.409%
Liar's Dice-4 0:06:57.896 0:06:58.577 0.163%
Leduc Poker 0:08:13.140 0:08:13.921 0.158%
Big Leduc Poker 14:55:48.347 14:58:07.357 0.259%
HUNL Subgame-3 0:02:54.634 0:02:55.024 0.223%
HUNL Subgame-4 0:02:14.379 0:02:14.648 0.200%
  • 结果分析:如上表所示,DDCFR 的平均时间增幅仅为 0.22%。这验证了 DDCFR 引入的额外计算时间相对于整体迭代时间可以忽略不计。

6.2.2. 对数操作的有效性

作者通过库恩扑克 (Kuhn Poker) 示例展示了归一化可利用性随迭代次数的变化,并比较了三种不同的归一化方法。以下是原文 Table 3 的结果:

t 1 10 20 100 500 1000
Et 4.583e-1 3.302e-2 1.599e-2 1.767e-3 1.699e-4 4.021e-5
(log Et − log Emin)/(log E1 − log Emin) 1.000 0.902 0.875 0.793 0.706 0.652
(√Et − √Emin)/(√E1 − √Emin) 1.000 0.268 0.187 0.062 0.019 0.009
(Et − Emin)/(E1 − Emin) 1.000 0.072 0.034 0.004 0.000 0.000
  • 结果分析CFR 变体在实践中收敛速度远快于其理论上的遗憾值平方根尺度上限。为了利用这一特性,作者采用了对数归一化 (logarithmic normalization)。如上表所示,对数归一化使得归一化可利用性分布更加均匀,这有助于神经网络训练,使智能体在每次迭代中做出更好的决策。相比之下,平方根归一化和线性归一化在早期就迅速接近0,导致智能体在后期迭代中难以区分状态。

6.3. 消融实验/参数分析

为了验证 DDCFR 各组件的有效性,作者进行了广泛的消融实验。以下是原文 Table 1 的结果:

DDCFR-1 DDCFR-2 DDCFR-3 DDCFR-it DDCFR-ex DDCFR-dis DDCFR-rl DDCFR
LeducPoker 1.566e-4 1.490e-4 1.213e-4 1.249e-4 1.289e-4 1.156e-4 1.229e-4 1.198e-4
Subgame-3 2.533e-3 2.481e-3 2.393e-3 2.292e-3 5.320e-3 5.795e-3 4.987e-3 1.963e-3
Subgame-4 2.517e-3 2.175e-3 2.122e-3 2.714e-3 3.804e-3 5.803e-3 5.198e-3 2.005e-3
  • 消融实验设置:每列结果通过替换 DDCFR 的一个组件获得,其余保持不变。使用三个测试博弈上的可利用性来比较学习到的折扣方案的性能。

6.3.1. 训练博弈数量的影响

  • DDCFR-x:表示使用 Kuhn Poker, Goofspiel-3, Liar's Dice-3, Small Matrix 中的前 xx 个训练博弈进行训练。
  • DDCFR-1:性能相对较差,因为仅使用一个训练博弈容易过拟合。
  • DDCFR-2DDCFR-3:获得了更好的结果,表明在多个博弈之间平衡性能可以提高学习到的折扣方案的泛化能力。
  • Small Matrix 的影响:加入 Small Matrix 后,DDCFRHUNL Subgame-3 中的可利用性显著降低,这可能是因为这两个博弈都具有高损失行动的特性。

6.3.2. 状态表示的影响

  • DDCFR-it:仅使用归一化迭代次数作为状态表示。
  • DDCFR-ex:仅使用归一化可利用性作为状态表示。
  • 结果DDCFR-it 表现优于 DDCFR-ex,表明迭代次数为智能体决策提供了更多信息。然而,两者都逊于完整的 DDCFR,这表明这两个状态特征是互补的,结合使用可以获得最佳性能。

6.3.3. 行动空间设计的影响

  • DDCFR:采用连续行动空间设计,即 α\alphaγ\gamma[0, 5] 之间连续取值,β\beta[5,0][-5, 0] 之间连续取值。
  • DDCFR-dis:使用离散行动空间设计,将 α,β,γ\alpha, \beta, \gamma 的范围离散化为连续整数。
  • 结果:连续行动有助于学习到的动态折扣方案进行更细粒度的控制,从而获得更好的性能。

6.3.4. 优化算法的影响

  • DDCFR-rl:使用 PPO(一种强化学习算法)来优化折扣策略。
  • 结果DDCFR-rl 在所有测试博弈中表现不佳。作者将此归因于训练过程中常见的挑战,如稀疏奖励、长时程和多任务学习,这些是 ES 在设计时就考虑到的优势。

7. 总结与思考

7.1. 结论总结

本文提出了 动态折扣反事实遗憾最小化 (Dynamic Discounted CFR, DDCFR) 框架,这是首个通过自动学习的动态方案对先前迭代进行折扣的均衡求解框架。

  • 核心创新:将 CFR 的迭代过程形式化为一个精心设计的马尔可夫决策过程 (MDP),并将折扣方案学习问题转化为策略优化问题。
  • 优化方法:设计了一种可扩展的基于演化策略 (ES) 的算法来高效优化折扣策略。
  • 性能和泛化:学习到的折扣策略展现出强大的泛化能力,在训练博弈和未见过的测试博弈上均取得了具有竞争力的性能,尤其是在测试博弈中比 DCFR 平均减少了 42% 的可利用性。
  • 通用性:该框架是通用的,可以作为即插即用的性能增强器应用于其他采用固定折扣规则的 CFR 变体,进一步提升它们的潜力。

7.2. 局限性与未来工作

论文明确指出了其框架的优势和贡献,但作为严谨的学术研究,也存在一些潜在的局限性:

  • 计算成本:尽管论文声称 DDCFR 的额外计算成本相对于整体迭代时间可以忽略不计,但这主要指运行时(inference)成本。训练阶段需要大量的计算资源(如 200 个 CPU 核心和 24 小时训练时间),这对于资源受限的研究者来说可能是一个挑战。
  • 超参数范围:定理 1 中给出的超参数 αt,βt,γt\alpha_t, \beta_t, \gamma_t 的范围虽然保证了收敛,但这些范围是预设的。是否存在一种机制可以动态地或自适应地调整这些范围本身,以达到更优的性能?
  • ES 的选择:虽然 ES 在处理稀疏奖励和长时程问题上具有优势,但它在样本效率方面可能不如一些基于梯度的 RL 算法。未来的工作可以探索将 DDCFR 框架与更先进的 RL 算法结合,或者开发更高效的梯度估计方法,特别是当 CFR 迭代过程的梯度难以计算时。
  • 状态和行动空间设计:尽管作者设计了博弈无关的状态表示,但状态空间和行动空间的设计仍然是手工进行的。未来的工作可以探索如何自动学习更优的状态表示和更复杂的行动空间结构,例如,允许行动参数之间存在更复杂的依赖关系,或者探索非参数化的折扣函数。
  • 理论收敛速度:虽然定理 1 保证了收敛,但其收敛速度的理论界限仍是基于 DCFR 的框架。探索 DDCFR 动态折扣方案是否能理论上超越现有固定方案的收敛速度界限,将是重要的理论贡献。
  • 仅限于两人零和博弈:目前的理论和实验主要集中在两人零和博弈。将 DDCFR 扩展到多人或非零和博弈将是更具挑战性的未来方向。

7.3. 个人启发与批判

这篇论文提供了一个非常重要的启发:算法的超参数不必是固定的,它们本身也可以被学习和动态调整。

  • 超参数的动态学习:传统的机器学习和强化学习中,超参数优化是一个耗时且关键的步骤。DDCFR 展示了如何将算法内部的“超参数”视为一个可学习的策略,并根据算法运行时的状态进行动态调整。这种元学习 (meta-learning) 的思想可以推广到其他迭代算法和优化过程中,例如,动态调整梯度下降的学习率、优化器参数、正则化强度等,而不仅仅是 CFR 中的折扣权重。

  • 强化学习在算法设计中的潜力:将算法设计(此处特指折扣方案设计)视为一个强化学习问题,并通过智能体与环境的交互来学习,这为自动化算法设计开辟了新的途径。这比手动设计启发式规则或进行网格搜索更具灵活性和适应性。

  • 博弈无关学习:设计 game-agnostic 的状态表示,使得学习到的策略能够泛化到未见过的博弈,这对于构建通用的博弈 AI 尤为重要。这种思想也可以应用于其他跨领域或跨任务的元学习场景。

    潜在问题与可以改进的地方

  • 解释性挑战:尽管 DDCFR 学习到的动态折扣方案表现出色,但其背后的决策逻辑(即为什么在特定状态下选择特定的 αt,βt,γt,τt\alpha_t, \beta_t, \gamma_t, \tau_t)可能不如手动设计的固定方案那样直观和易于解释。未来的工作可以探索可解释的 AI (Explainable AI, XAI) 技术,以更好地理解智能体的决策过程。

  • 计算效率和可扩展性:虽然 ES 在分布式训练中表现良好,但对于超大规模的博弈或更复杂的折扣策略网络,训练成本可能仍然很高。探索更高效的 ES 变体、神经架构搜索 (Neural Architecture Search, NAS) 或其他元学习技术,以进一步优化训练效率和可扩展性,将是有价值的。

  • 理论泛化保证:尽管实验结果显示了强大的泛化能力,但缺乏严格的理论泛化保证。在未来的工作中,可以尝试为 DDCFR 在未见过的博弈上的泛化性能提供更严格的理论分析。

  • 智能体的鲁棒性:智能体是在有限的训练博弈集上学习的。当遇到训练集之外的、具有高度异常特性的博弈时,其性能是否仍能保持鲁棒性?对 DDCFR 在更多样化、更具挑战性的博弈(如不对称博弈、超大规模博弈)上的鲁棒性进行评估将很重要。

  • 行动空间离散化与连续性:消融实验表明连续行动空间优于离散空间,但离散的 τt\tau_t 仍然存在。探索完全连续的行动空间,或者自适应地确定 τt\tau_t 的值,可能带来进一步的性能提升。

    总而言之,DDCFR 是在博弈 AI 领域的一个重要进展,它将机器学习的力量引入到核心算法的设计中,预示着一个更加智能和自适应的算法优化范式。

相似论文推荐

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

暂时没有找到相似论文。