论文：《Combining Deep Reinforcement Learning and Search for Imperfect-Information Games》
地址：https://arxiv.org/abs/2007.13544v2
代码：https://github.com/facebookresearch/rebel
材料：

• BV1gt4y1k77C（1小时12分钟）
• BV1hM4y1D7SW（35分钟）

论文的贡献：

1. 一种应用在不完美信息二人零和博弈中的 RL+Search 算法；（ReBel、定理2）
2. 为安全搜索算法提供了一种新的选择；（定理3）
3. 使用 CFR-AVG 分解子博弈；
4. 揭示了 PBS 梯度与 infostates value 之间的联系；（定理1）
5. 一种新的虚拟博弈算法：虚拟线性乐观博弈算法（Fictitious Linear Optimistic Play, FLOP）

一些概念

• $w\in \mathcal{W}$，世界状态（World State），游戏中的一个状态；
• $\mathcal{A}={\mathcal{A}}_1\times {\mathcal{A}}_2\times \cdots {\mathcal{A}}_N$，N 个 agent 联合行为的空间；
• $a=(a_1,a_2,\cdots ,a_N)\in \mathcal{A}$，N 个 agent 的一种联合行为；
• $\mathcal{T}(w,a)\in \Delta \mathcal{W}$，输运函数，它是一个概率分布，在当前的世界状态 w 下选定 a 之后，负责决定下一个世界状态 w’；
• ${\mathcal{R}}_i(w,a)$，agent i 的在 (w,a) 时获得的奖励；
• ${\mathcal{O}}_{priv(i)}(w,a,w^{\prime })$，agent i 在 a 的作用下从 w 转至 w’ 后获得的私人观测（Private Observation）；
• ${\mathcal{O}}_{pub}(w,a,w^{\prime })$，所有 agent 获得的公共观测（Public Observation）;
• $h=(w^0,a^0,w^1,a^1,\cdots ,w^t)$，历史（History），合理行为与世界状态的一个有限序列；
• $s_i=(O_i^0,a_i^0,O_i^1,a_i^1,\cdots ,O_i^t)$，infostate，agent i 的观测与行为的序列，

  其中，$O_i^k=(O_{priv}(w^{k-1},a^{k-1},w^k),O_{pub}(w^{k-1},a^{k-1},w^k))$

• $s_i(h)$ 是在 h 下 agent i 唯一的 infostate，$\mathcal{H}(s_i)$，是 agent i 的 infostate 的所有 h 的集合；
• $s_{pub}=(O_{pub}^0,O_{pub}^1,\cdots ,O_{pub}^t)$，公共状态（Public State），是公共观测的序列；
• $s_{pub}(h)$ 是 h 的公共状态，$s_{pub}(s_i)$ 是 $s_i$ 的公共状态，$\mathcal{H}(s_{pub})$ 是与 $s_{pub}$ 相匹配的历史的集合，
• $\pi =({\pi }_1,{\pi }_2,\cdots ,{\pi }_N)$，策略配置（Policy Profile），概率分布的序列，${\pi }_i$ 是一个将 infostate 映射为行为上的概率分布的函数；
• 纳什均衡（Nash Equilibrium） ${\pi }^{\ast }$：$v_i({\pi }^{\ast })={\max }_{{\pi }_i}{v}_i({\pi }_i,{\pi }_{-i}^{\ast })$（对所有 i 均成立）；
  • $ϵ-\text{Nash Equilibrium}$ ${\pi }^{\ast }$：$\exists ϵ>0,s.t.v_i({\pi }^{\ast })+ϵ\ge {\max }_{{\pi }_i}{v}_i({\pi }_i,{\pi }_{-i}^{\ast })$（对所有 i 均成立）；
• $2p0s$：二人零和博弈；
• PBS $\beta =(\Delta S_1(s_{pub}),\Delta S_2(s_{pub}),\cdots ,\Delta S_N(s_{pub}))$，其中 $S_i(s_{pub})$ 是给定 $s_{pub}$ 时 agent i 的 infostate 的集合，$\Delta S_1(s_{pub})$ 是 $S_i(s_{pub})$ 上的联合概率分布；
• $V_i^{\pi }(\beta )={\Sigma }_{h\in \mathcal{H}(s_{pub}(\beta ))}p(h|\beta )v_i^{\pi }(h)$，当所有选手使用 $\pi$ 时，agent i 在 $\beta$ 上的 value;
• 在 2p0s 中，如果二人均使用纳什均衡策略，则每人在每个 PBS $\beta$ 上的 value 是唯一的，且 $V_1(\beta )=-V_2(\beta )$；
• $v_i^{{\pi }^{\ast }}(s_i|\beta )={\max }_{{\pi }_i}{\Sigma }_{h\in \mathcal{H}(s_i)}p(h|s_i,{\beta }_{-i})v_i^{<{\pi }_i,{\pi }_{-i}^{\ast }>}(h)$，在 2p0s 中是指以 $\beta$ 为子博弈的根，二人采用纳什均衡策略 ${\pi }^{\ast }$ 时，第 i 人的 infostate $s_i$ 的 value。

Discrete Representation 与 Belief Representation

52 张牌，二人博弈。每人在每个回合中有三种选择：翻牌、叫牌与加牌。

Discrete Representation	Belief Representation
两人知道自己的牌不知道对方的牌，并据此采取下一步动作	两人不知道自己和对方的牌，裁判知道每个人的牌。裁判依据二人分别声明的牌的对应行为的概率分布在二人的牌中进行操作。二人根据裁判的行为推测自己与对方的牌，然后调整对应动作的概率分布

---

ReBel__47">ReBel 算法

f u n c t i o n  REBEL-LINEAR-CFR-D  ( β r , θ v , θ π , D v , D π )     #  β r  是当前的 PBS     while !IsTerminal ( β r )  do          G ← ConstructSubgame ( β r )          π ˉ , π t w a r m ← InitializePolicy ( G , θ π )     # 如果没有 warm start ，则 ： t w a r m = 0 , π 0  是均匀分布          G ← SetLeafValues ( β r , π t w a r m , θ v )          v ( β r ) ← ComputeEV ( G , π t w a r m )          t s a m p l e ∼ linear { t w a r m + 1 , T }     # 迭代 t 的采样概率与 t 成正比         for  t = ( t w a r m + 1 ) . . T  do             if  t = t s a m p l e  then                  β r ′ ← SampleLeaf ( G , π t − 1 )     # 采样一个或多个叶 PBS              π t ← UpdatePolicy ( G , π t − 1 )              π ˉ ← t t + 1 π ˉ + 1 t + 1 π t              G ← SetLeafValues ( β r , π t , θ v )              v ( β r ) ← t t + 1 v ( β r ) + 1 t + 1 ComputeEV ( G , π t )         Add  { β r , v ( β r ) }  to  D v     # 添加到训练值网络的数据中         for  β ∈ G  do    # 遍历 G 中每个公共状态的 PBS             Add  { β , π ˉ ( β ) }  to  D π     # 添加到训练策略网络的数据中（可选）          β r ← β r ′ − − − − − − − − − − − − − − − − − − f u n c t i o n  SetLeafValues ( β , π , θ v )     if IsLeaf ( β )  then         for  s i ∈ β  do    # 对与  β  相关的每个内部状态 s i              v ( s i ) = v ^ ( s i ∣ β , θ v )     else         for  a ∈ A ( β )  do             SetLeafValues ( T ( β , π , a ) , π , θ v ) − − − − − − − − − − − − − − − − − − f u n c t i o n  SampleLeaf ( G , π )      i ∗ ∼ unif { 1 , N } , h ∼ β r     # 从根 PBS 中随机选取一个历史及一位玩家     while !IsLeaf ( h )  do          c ∼ unif [ 0 , 1 ]         for  i = 1.. N  do              if  i = = i ∗  and  c < ϵ  then    # 训练时设置  ϵ = 0.25 ，测试时设置  ϵ = 0                 sample an action  a i  uniform random             else                 sample an action  a i  according to  π i ( s i ( h ) )          h ∼ τ ( h , a )     return  β h     # 返回与叶节点 h 相关的 PBS \begin{aligned} &\pmb{function}\text{ REBEL-LINEAR-CFR-D }(\beta_r,\theta^v,\theta^\pi,D^v,D^\pi) \ \ \ \ \text{\# }\beta_r\text{ 是当前的 PBS}\\ &\ \ \ \ \text{while !IsTerminal}(\beta_r)\text{ do} \\ & \ \ \ \ \ \ \ \ G\leftarrow \text{ConstructSubgame}(\beta_r) \\ & \ \ \ \ \ \ \ \ \bar{\pi},\pi^{t_{warm}}\leftarrow \text{InitializePolicy}(G,\theta^\pi) \ \ \ \ \text{\# 如果没有 warm start ，则 ：}t_{warm}=0, \pi^0\text{ 是均匀分布}\\ & \ \ \ \ \ \ \ \ G\leftarrow \text{SetLeafValues}(\beta_r,\pi^{t_{warm}},\theta^v) \\ & \ \ \ \ \ \ \ \ v(\beta_r)\leftarrow \text{ComputeEV}(G,\pi^{t_{warm}}) \\ & \ \ \ \ \ \ \ \ t_{sample}\sim \text{linear}\{t_{warm}+1,T\} \ \ \ \ \text{\# 迭代 t 的采样概率与 t 成正比}\\ & \ \ \ \ \ \ \ \ \text{for }t=(t_{warm}+1)..T\text{ do} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \text{if }t=t_{sample}\text{ then} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \beta'_r\leftarrow \text{SampleLeaf}(G,\pi^{t-1}) \ \ \ \ \text{\# 采样一个或多个叶 PBS}\\ & \ \ \ \ \ \ \ \ \ \ \ \ \pi^t\leftarrow\text{UpdatePolicy}(G,\pi^{t-1}) \\ & \ \ \ \ \ \ \ \ \ \ \ \ \bar{\pi}\leftarrow\frac{t}{t+1}\bar{\pi}+\frac{1}{t+1}\pi^t \\ & \ \ \ \ \ \ \ \ \ \ \ \ G\leftarrow\text{SetLeafValues}(\beta_r,\pi^t,\theta^v) \\ & \ \ \ \ \ \ \ \ \ \ \ \ v(\beta_r)\leftarrow\frac{t}{t+1}v(\beta_r)+\frac{1}{t+1}\text{ComputeEV}(G,\pi^t) \\ & \ \ \ \ \ \ \ \ \text{Add }\{\beta_r,v(\beta_r)\}\text{ to }D^v \ \ \ \ \text{\# 添加到训练值网络的数据中}\\ & \ \ \ \ \ \ \ \ \text{for }\beta\in G\text{ do} \ \ \ \ \text{\# 遍历 G 中每个公共状态的 PBS}\\ & \ \ \ \ \ \ \ \ \ \ \ \ \text{Add }\{\beta,\bar{\pi}(\beta)\}\text{ to }D^\pi \ \ \ \ \text{\# 添加到训练策略网络的数据中（可选）}\\ & \ \ \ \ \ \ \ \ \beta_r\leftarrow\beta'_r \\ &------------------\\ &\pmb{function}\text{ SetLeafValues}(\beta,\pi,\theta^v) \\ &\ \ \ \ \text{if IsLeaf}(\beta)\text{ then} \\ &\ \ \ \ \ \ \ \ \text{for }s_i\in\beta\text{ do} \ \ \ \ \text{\# 对与 }\beta\text{ 相关的每个内部状态} s_i\\ &\ \ \ \ \ \ \ \ \ \ \ \ v(s_i)=\hat{v}(s_i|\beta,\theta^v) \\ &\ \ \ \ \text{else} \\ &\ \ \ \ \ \ \ \ \text{for }a\in\mathcal{A}(\beta)\text{ do} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \text{SetLeafValues}(\mathcal{T}(\beta,\pi,a),\pi,\theta^v) \\ &------------------ \\ &\pmb{function}\text{ SampleLeaf}(G,\pi) \\ &\ \ \ \ i^*\sim\text{unif}\{1,N\},h\sim\beta_r \ \ \ \ \text{\# 从根 PBS 中随机选取一个历史及一位玩家}\\ &\ \ \ \ \text{while !IsLeaf}(h)\text{ do} \\ &\ \ \ \ \ \ \ \ c\sim\text{unif}[0,1] \\ &\ \ \ \ \ \ \ \ \text{for }i=1..N\text{ do} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \text{ if }i==i^*\text{ and }c<\epsilon\text{ then} \ \ \ \ \text{\# 训练时设置 }\epsilon=0.25\text{，测试时设置 }\epsilon=0\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{sample an action }a_i\text{ uniform random} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \text{else} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{sample an action }a_i\text{ according to }\pi_i(s_i(h)) \\ &\ \ \ \ \ \ \ \ h\sim \tau(h,a) \\ &\ \ \ \ \text{return }\beta_h \ \ \ \ \text{\# 返回与叶节点 h 相关的 PBS}\\ \end{aligned} ​function REBEL-LINEAR-CFR-D (βr​,θv,θπ,Dv,Dπ)    # βr​ 是当前的 PBS    while !IsTerminal(βr​) do        G←ConstructSubgame(βr​)        πˉ,πtwarm​←InitializePolicy(G,θπ)    # 如果没有 warm start ，则 ：twarm​=0,π0 是均匀分布        G←SetLeafValues(βr​,πtwarm​,θv)        v(βr​)←ComputeEV(G,πtwarm​)        tsample​∼linear{twarm​+1,T}    # 迭代 t 的采样概率与 t 成正比        for t=(twarm​+1)..T do            if t=tsample​ then                βr′​←SampleLeaf(G,πt−1)    # 采样一个或多个叶 PBS            πt←UpdatePolicy(G,πt−1)            πˉ←t+1t​πˉ+t+11​πt            G←SetLeafValues(βr​,πt,θv)            v(βr​)←t+1t​v(βr​)+t+11​ComputeEV(G,πt)        Add {βr​,v(βr​)} to Dv    # 添加到训练值网络的数据中        for β∈G do    # 遍历 G 中每个公共状态的 PBS            Add {β,πˉ(β)} to Dπ    # 添加到训练策略网络的数据中（可选）        βr​←βr′​−−−−−−−−−−−−−−−−−−function SetLeafValues(β,π,θv)    if IsLeaf(β) then        for si​∈β do    # 对与 β 相关的每个内部状态si​            v(si​)=v^(si​∣β,θv)    else        for a∈A(β) do            SetLeafValues(T(β,π,a),π,θv)−−−−−−−−−−−−−−−−−−function SampleLeaf(G,π)    i∗∼unif{1,N},h∼βr​    # 从根 PBS 中随机选取一个历史及一位玩家    while !IsLeaf(h) do        c∼unif[0,1]        for i=1..N do             if i==i∗ and c<ϵ then    # 训练时设置 ϵ=0.25，测试时设置 ϵ=0                sample an action ai​ uniform random            else                sample an action ai​ according to πi​(si​(h))        h∼τ(h,a)    return βh​    # 返回与叶节点 h 相关的 PBS​

• 其中，${\theta }^v$ 与 ${\theta }^{\pi }$ 分别是策略网络与值函数网络的参数，这两个网络都用 MLP+GELU+LayerNorm 实现。

  • 前者的输入是 agent 的索引+公共状态的表征+infostate 的概率分布，输出是每个infostate对应的value构成的向量。
  • 后者（仅用于德州扑克）的输入额外增加 agent 的 pot size 分数与当前是否存在赌注的 flag，输出是每个infostate的所有合法行为的概率分布。

• 算法求解以 ${\beta }_r$ 为根的子博弈。求解过程中会随机采样新的叶子 PBS（确保值函数网络的准确性），生成新的子博弈后再次求解。

• 子博弈是一个不完美信息博弈，采用 CFR-D 进行求解。CFR-D 会迭代 T 次，每次都会选择一个新的策略，然后更新子博弈叶子上的 value（用值函数网络更新）。CRF-D 会返回当前子博弈的期待策略与期待值。

• CFR-D 得到的 { β r , v ( β r ) } \{\beta_r,v(\beta_r)\} {βr​,v(βr​)} 与 { β r , π ˉ ( β r ) } \{\beta_r,\bar{\pi}(\beta_r)\} {βr​,πˉ(βr​)} 会被用于训练值函数网络与策略网络。

• 策略的均值被定义为一个新策略：$\pi (s_i)=\frac{(x_i^{{\pi }_1}(s_i)\alpha ){\pi }_1(s_i)+(x_i^{{\pi }_2}(s_i)(1-\alpha )){\pi }_2(s_i)}{x_i^{{\pi }_1}(s_i)\alpha +x_i^{{\pi }_2}(s_i)(1-\alpha )}$，这里 $x_i^{{\pi }_1}(s_i)={\Pi }_{t}p(a_i^t)$。

• 算法整体是一个 自我博弈 的过程，定理2表明算法经过迭代之后会得到一个误差不超过 $\frac{C}{\sqrt{T}}$ 的值函数网络。

• $\bar{\pi }$ 会收敛到纳什均衡。

---

定理

定理一，PBS 与 infostate value 之间的联系：
在二人零和博弈中，对任意 PBS $\beta =({\beta }_1,{\beta }_2)$ 和以 $\beta$ 为根的子博弈的任意纳什均衡 ${\pi }^{\ast }$，有：
$$v_1^{{\pi }^{\ast }}(s_1|\beta )=V_1(\beta )+\bar{g}\cdot {\hat{s}}_1$$
其中 $\bar{g}$ 是 $V_1(\beta )$ 扩展到非归一化信念分布的超梯度，${\hat{s}}_1$ 是 $s_1$ 方向上的单位向量。

二人零和博弈中，使用一个值函数网络生成 $V_1(\beta )$ 即可。
证明：
在引理1 与引理2 的基础上，计算 ${\nabla }_{{\beta }_1}{V}_1^{{\pi }^{\ast }}(s_{pub},{\beta }_1,{\beta }_2)$ （$V_1$ 的超梯度）并应用 $V_1$ 的定义即可。

利用 ${\tilde{V}}_1^{{\pi }^{\ast }}(s_{pub},{\beta }_1,{\beta }_2)=V_1^{{\pi }^{\ast }}(s_{pub},{\beta }_1/|{\beta }_1{|}_1,{\beta }_2)$，其中 $|{\beta }_1{|}_1=1$
$$\begin{array}{rl}\text{Lemma 1. }& \text{Let }{V}_1^{{\pi }_2}(\beta )\text{ be player 1’s value at }\beta \text{ assuming that player 2 plays }{\pi }_2\text{ in a 2p0s game. }\\ & V_1^{{\pi }_2}(\beta )\text{ is linear in }{\beta }_1.\\ \text{Lemma 2. }& V_1(\beta )=\underset{{\pi }_2}{\min }{V}_1^{{\pi }_2}(\beta )\text{, and the set of }{\pi }_2\text{ that attain }{V}_1(\beta )\text{ at }{\beta }_0\text{ are precisely the Nash equilibrium policies at }{\beta }_0\text{.}\\ & \text{ This also implies that }{V}_1(\beta )\text{ is concave.}\end{array}$$

定理二， ReBel算法能够收敛到纳什均衡：
理想的值函数逼近器：为被采样的 PBS 返回 value 的最新样本，其他情况返回0。
在运行算法 1 时用到了 CFR 算法，该算法会迭代 T 次，子博弈借此为遇到的所有任意 PBS 构建出一个值函数逼近器，逼近器的误差不超过 $\frac{C}{\sqrt{T}}$，对应的策略为 $\frac{C}{\sqrt{T}}$-纳什均衡，其中 C 是一个与博弈相关的常数。

证明：
只需要证明引理3 即可：
$$\begin{array}{rl}& \text{Lemma 3}\text{. Running Algorithm 1 for }N\to \infty \text{ times in a depth-limited subgame rooted at PBS }{\beta }_r\text{ will compute an infostate value}\\ & \text{ vector }{v}_i^{{\pi }^{\ast }}({\beta }_r)\text{ corresponding to the values of the infostates when }{\pi }^{\ast }\text{ is played in the (not depth-limited) subgame rooted at }{\beta }_r\text{, }\\ & \text{where }{\pi }^{\ast }\text{ is a }\frac{C}{\sqrt{T}}\text{-Nash equilibrium for some constant }C.\end{array}$$
当算法一不使用随机采样并且用递归的CFR-D算法取代神经网络时，与 CFR-D 算法是相似的。
设以 ${\beta }_r$ 为根的子博弈一直延伸到总博弈的结尾，且不再使用神经网络，则 CFR 算法已经被证明可以达到 $\frac{C}{\sqrt{T}}$-纳什均衡 ${\pi }^{\ast }$，而算法一也确实可计算得到值向量 $v_i^{{\pi }^{\ast }}({\beta }_r)$，也就是说引理3 的基本情况是成立的。
假设：1、子博弈以 ${\beta }_r$ 为根且其深度是有限的；2、在迭代 $t\le T$ 的每一个叶子 PBS ${\beta }_z^{{\pi }^t}$ 上，我们已经计算出一个 infostate value 向量 $v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^t})$；3、引理 3 在所有叶子 PBS ${\beta }_z^{{\pi }^{T+1}}$ 上成立。

$v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^t})$：在以 ${\beta }_z^{{\pi }^t}$ 为根的子博弈上采用纳什均衡策略获得的 Infostate Value。

• 对于那些拥有正的抵达概率却没有玩家抵达的叶子 PBS，它们的 value 并不会对 CFR 或者为根 infostate 计算的 value 产生影响，这是因为 CFR 是用玩家抵达的概率对 PBS 上的 value 进行加权的。
• 现在我们考虑一个叶子 PBS ${\beta }_z^{{\pi }^{T+1}}$，其上被一些玩家以正的概率到达。
  后面只需要证明，如果 $v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^t})$ 能被计算出来，那么 $v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^{(}T+1)})$ 也能被计算出来，并且前者对应的纳什均衡策略不会被破坏。
  因为 $v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^t})$ 已经被计算出来，并且我们正在运行的算法是已经被确定的。所以 $v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^t})$ 不会在算法一的后续调用中发生改变。（这里的后续调用指的是在每个 ${\beta }_z^{{\pi }^t}$ 上的调用，其中 $t\le T$）。
  也就是说，${\pi }^t$ 对所有 $t\le T$ 是相同的。
  因为算法一对随机 CFR 的迭代进行了采样，并且当采样到迭代 T+1 的时候，为某些玩家采样叶子 PBS ${\beta }_z^{{\pi }^{T+1}}$ 的概率是正的。所以 算法会在 ${\beta }_z^{{\pi }^{T+1}}$ 上采样 N’ 次，当 $N\to \infty$ 时 $N^{\prime }\to \infty$。
  又因为引理3 在 ${\beta }_z^{{\pi }^{T+1}}$ 上是成立的，$v_i^{{\pi }^{\ast }}({\beta }_z^{{\pi }^{T+1}})$ 会在算法中被计算出来，
  根据 CFR-D 论文中的结论，引理3 在所有 ${\beta }_r$ 上成立。

定理三，ReBel算法被直接用于测试时具有可靠性：
如果算法 1 在测试阶段没有其他外部策略，价值网络在任意叶 PBS 上的误差不超过 $\delta$，子博弈用 CFR 的 T 次迭代求解，那么该算法可以获得 $(\delta C_1+\frac{\delta C_2}{\sqrt{T}})$-纳什均衡，其中 C1、C2 是与博弈相关的常数。

首先，考虑一个接近博弈结尾的没有叶节点的子博弈，显然 ${\pi }^{\ast }$ 是 $\frac{k_1}{\sqrt{T}}$-纳什均衡。（${\pi }^{\ast }$ 是在算法一中CFR期望使用的策略）
除所有T次迭代后得到的均值策略 ${\bar{\pi }}^T$ 外，在 t ∼ u n i f o r m { 1 , T } t\sim uniform\{1,T\} t∼uniform{1,T} 中采样一个 t 的策略 ${\pi }^t$ 也是一个 $\frac{k_1}{\sqrt{T}}$-纳什均衡。
接下来考虑深度有限的子博弈 G，如果根据 tabular CFR-D 计算 G 的策略，那么根据 CFR-D 论文中的定理2，所有迭代上的平均策略是 $k_2\delta +\frac{k_3}{\sqrt{T}}$-纳什均衡。
像前面一样，不仅均值策略，对于随机采样得到的 t 的策略 ${\pi }^t$ 也是 $k_2\delta +\frac{k_3}{\sqrt{T}}$-纳什均衡。
因为博弈的回合数是有限的，所以算法一在测试中是按照$C_1\delta +\frac{C_2}{\sqrt{T}}$-纳什均衡进行博弈的。