Double Neural Counterfactual Regret Minimization

Hui Li 1 Kailiang Hu 1 Yuan Qi 1 Le Song 1 2

Abstract
Counterfactual Regret minimization (CFR) is afundamental and effective technique for solving
Imperfect Information Games (IIG). However, theoriginal CRF algorithm only works for discrete
states and action spaces, and the resulting strategy
is maintained as a tabular representation. Suchtabular representation limits the method frombeing directly applied to large games. In thispaper, we propose a double neural representation
for the IIGs, where one neural network represents
the cumulative regret, and the other represents
the average strategy. Such neural representations
allow us to avoid manual game abstraction andcarry out end-to-end optimization. To make thelearning efficient, we also developed several novel
techniques including a robust sampling method
and a mini-batch Monte Carlo Counterfactual Regret Minimization (MCCFR) method, which may
be of independent interests. Empirically, on games
tractable to tabular approaches, neural strategies
trained with our algorithm converge comparably
to their tabular counterparts, and achieve much
lower exploitability than those based on deep
reinforcement learning. On larger games, ourapproach achieved strategy profiles comparable
to DeepStack’s results while using hundreds oftimes less memory than the tabular CFR.

1. Introduction
While significant advance has been made in addressing large
perfect information games, such as Go (Silver et al., 2016),
solving imperfect information games remains a challenging
task. For IIGs, a player has only partial knowledge about her
opponents before making a decision, so that she has to reason
under the uncertainty about her opponents’ information
while exploiting the opponents’ uncertainty about herself.
Thus, IIGs provide more realistic modeling than perfect
information games for many real-world applications, suchas trading, traffic routing, and politics.
1
Ant Financial, China 2 Georgia Institute of Technology,
USA. Correspondence to: Hui Li <lihuiknight@google.com,
ken.lh@antfin.com>.
Real-World Sequential Decision Making workshop at the 36 thInternational Conference on Machine Learning, 2019. Copyright2019 by the author(s).

Nash equilibrium is a typical solution concept for a
two-player perfect-recall IIG. One of the most effective
approaches is CFR (Zinkevich et al., 2007), which minimizes
the overall counterfactual regret so that the average strategies
converge to a Nash equilibrium. However, the original CFR
only works for discrete states and action spaces, and theresulting strategy is maintained as a tabular representation.
Such tabular representation limits the method from being
directly applied to large games. To tackle this challenge, one
can simplify the game by grouping similar states together
to solve the simplified (abstracted) game approximately via
tabular CFR (Zinkevich et al., 2007; Lanctot et al., 2009).
Constructing an effective abstraction, however, demands
rich domain knowledge and its solution may be a coarse
approximation of true equilibrium.
Function approximation can be used to replace the tabular
representation. Waugh et al. (2015) combines regression
tree function approximation with CFR based on handcraftedfeatures. However, since their approach uses full traversals of
the game tree, it is still impractical for large games. Moravcik
et al. (2017) propose a seminal approach DeepStackwhich uses fully connected neural networks to represent
players’ counterfactual values, tabular CFR however wasused in the subgame solving. Jin et al. (2017) use deep
reinforcement learning to solve regret minimization problem
for single-agent settings, which is different from two-player
perfect-recall IIGs.
To learn approximate Nash equilibrium for IIGs in an
end-to-end manner, Heinrich et al. (2015) and Heinrich& Silver (2016) propose eXtensive-form Fictitious Play
(XFP) and Neural Fictitious Self-Play (NFSP), respectively,
based on deep reinforcement learning. In a NFSP model, theneural strategies are updated by selecting the best responses
to their opponents’ average strategies. These approaches
are advantageous in the sense that they do not rely on
abstracting the game, and accordingly their strategies canimprove continuously with more optimization iterations.
However, fictitious play empirically converges much slower
than CFR-based approaches. Srinivasan et al. (2018) use
actor-critic policy optimization methods to minimize regret.
However, the performance of such reinforcement learning
methods is not competitive with CFR.
Thus it remains an open question whether purely neural-

Double Neural Counterfactual Regret Minimization

based end-to-end approach can achieve comparable
performance to tabular based CFR approach. In thepaper, we partially solve this open question by designing adouble neural counterfactual regret minimization (DNCFR)
algorithm which can match the performance of tabular based
counterfactual regret minimization algorithm.
player 0

Algorithm 1: CFR Algorithm
2
1tchance

ℎ2

ℎ1

t

F

P

ℎ5

infosetCttriσ (a|Ii ) = viσ (a|Ii )−viσ (Ii ).
Rit (a|Ii ) = Rit−1 (a|Ii )+riσ (a|Ii ).
 1PRt,+ (a|Ii ) = 0
if |A(Ii )| a∈A(Ii ) it,+
σit+1 (a|Ii ) =Ri (a|Ii )otherwise.
Pt,+Ri (a|Ii )

𝑣0𝜎 𝐼0= 𝑣0𝜎 𝑃 𝐼0 𝜎0 𝑃 𝐼0𝑡
+ 𝑣0𝜎 (𝐵|𝐼0 )𝜎0 (𝐵|𝐼0 )𝑟0𝜎 (𝐵|𝐼0 )=𝑣0𝜎 𝐵 𝐼0 − 𝑣0𝜎 (𝐼0 )

B

B

P

t

t

infosetℎ4tσπiσ (h,z)π−i(z)ui (z).

PB

𝑣0𝜎 (𝑃|𝐼0 )
B

ℎ6
F

(1)

h∈Ii ,hvz,z∈Z

ℎ0

ℎ3

X

viσ (Ii ) =player 1

P

For t = 1 to T do

(2)
(3)

(4)

a∈A(Ii )𝑣0𝜎 (𝐵|𝐼0 )t

S (a|Ii ) = S

C

t−1

t

(a|Ii )+πiσ (Ii )σit (a|Ii ).

(5)

3

𝑧1

𝑧2

ℎ7
F

C

𝑧7

𝑧8

𝑧3

𝑧4

𝑧5

ℎ8
F

C

𝑧9

𝑧10

𝑧6

Figure 1: Extensive-Form IIG and Information Set

2. Background• Notation. We define the components of an extensive-form
IIG following (Osborne & Rubinstein, 1994). Figure 1 illustrates an extensive game for a finite set N = {0,1,...,n−1}
of n players. Define xvi as the hidden information of player
i in IIG. xv−i refers to hidden variables of all players otherthan i. H refers to a finite set of histories. h ∈ H denotes apossible history (or state), which consists of each player’s
hidden variable and actions taken by all players including
chance. The empty sequence ∅ is a member of H. hj v hdenotes hj is a prefix of h. Z ⊆ H denotes the terminal
histories and any member z ∈ Z is not a prefix of any othersequences. A(h) = {a : ha ∈ H} is the set of available actions
after non-terminal history h ∈ H \Z. A player function P
assigns a member of N ∪ {c} to each non-terminal history,
where c is the chance ( we set c = −1). P (h) is the player who
takes an action after history h. For each player i, imperfect
information is denoted by information set (infoset) Ii . All
states h ∈ Ii are indistinguishable to i. Ii refers to the set of
infosets of i. The utility function ui (z) defines the payoffof i at state z. See appendix B.1 for more details.
A strategy profile σ = {σi |σi ∈ Σi ,i ∈ N } is a collection ofstrategies for all players, where Σi is the set of all possible
strategies for player i. σ−i refers to strategy of all players
other than player i. For play i ∈ N , the strategy σi (Ii ) isa function, which assigns an action distribution over A(Ii )to infoset Ii . σi (a|h) denotes the probability of action ataken by player i at state h. In IIG, ∀h1 ,h2 ∈ Ii , we haveσi (Ii ) = σi (h1 ) = σi (h2 ). For iterative method such as
CFR, σ t refers to the strategy profile at t-th iteration. The
state reach probability of history h is denoted by π σ (h) if

σ̄i T (a|Ii ) = P

S T (a|Ii ).
Ta∈A(Ii ) S (a|Ii )(6)

players take actions according to σ. Similarly, πiσ (h) refersσto those for player i while π−i(h) refers to those for otherplayers expect i. For an empty sequence π σ (∅) = 1. One
can also show that the reach probability of the opponent is
proportional to posterior probability of the opponent’s hidden
σvariable, i.e.,p(xv−i |Ii ) ∝ π−i(h), where xvi and Ii indicate
a particular h (proof in Appendix D.1). Finally,
P the infosetσσreach probability of Ii is defined
as
π
(I
)
=
i
h∈Ii π (h).
Pσσσ
Similarly,
we have πi (Ii ) = h∈Ii πi (h) and π−i (Ii ) =Pσh∈Ii π−i (h). More details can be found in Appendix B.3.
• Counterfactual Regret Minimization. CFR is an
iterative method for finding a Nash equilibrium for zero-sum
perfect-recall IIGs (Zinkevich et al., 2007) (Algorithm 1 andFigure 2(a)). Given strategy profile σ, the counterfactual
value (CFV) viσ (Ii ) at infoset Ii is defined by Eq. (1). The
action CFV of taking action a is viσ (a|Ii ) and its regret isdefined by Eq. (2). Then the cumulative regret of action
a after T iterations is Eq. (3), where Ri0 (a|Ii ) = 0. Define
Rit,+ (a|Ii ) = max(Rit (a|Ii ), 0), the current strategy (orbehavior strategy) at t + 1 iteration will be updated byt
Eq. (4). Define sti (a|Ii ) = πiσ (Ii )σit (a|Ii ) as the additional
strategy in iteration t, then the cumulative strategy canbe defined as Eq. (5), where S 0 (a|Ii ) = 0. The average
strategy σ̄i t after t iterations is defined by Eq. (6), whichapproaches a Nash equilibrium after enough iterations.
• Monte Carlo CFR. (Lanctot et al., 2009) proposed a
Monte Carlo CFR (MCCFR) to compute the unbiased
estimation of counterfactual value by sampling subsets
of infosets in each iteration. Although MCCFR stillneeds two tabular storages for saving cumulative regret
and strategy as CFR does, it needs much less working
memory than the standard CFR (Zinkevich et al., 2007).
This is because MCCFR needs only to maintain values

Double Neural Counterfactual Regret Minimization

(a)

(b)

Regret Matching

𝑅𝑖𝑡−1 (𝑎|𝐼𝑖 )
𝐼1

𝐼2
𝑎3

𝑎5

𝑎7

𝑎6

𝑞𝑢𝑒𝑟𝑦

𝐼2
𝑎3

𝑎5

𝑎7

gradient
descent

𝑠𝑎𝑚𝑝𝑙𝑒𝑑 𝑖𝑛𝑓𝑜𝑠𝑒𝑡𝑠+

𝑎6

AvgStrategyNetwork𝑠𝑖𝑡 (𝑎|𝐼𝑖 )𝐼4
𝑎𝑙𝑙 𝑖𝑛𝑓𝑜𝑠𝑒𝑡𝑠𝑟𝑖 ((𝑎|𝐼𝑖 )|𝑄𝑗 )
𝐼3

𝑎4

+

𝑎8

𝜎𝑡

𝑎2

𝑎1
𝑎𝑙𝑙 𝑖𝑛𝑓𝑜𝑠𝑒𝑡𝑠

𝑆𝑖𝑡−1 (𝑎|𝐼𝑖 )𝑠𝑖𝑡 (𝑎|𝐼𝑖 )𝐼4

𝐼1

𝑟𝑖 ((𝑎|𝐼𝑖 )|𝑄𝑗 ) +𝐼3𝑎4𝑞𝑢𝑒𝑟𝑦 RegretSumNetwork

𝑞𝑢𝑒𝑟𝑦

𝜎𝑡

𝑎2

𝑎1

Regret Matching𝑎8

gradient
descent

𝑠𝑎𝑚𝑝𝑙𝑒𝑑 𝑖𝑛𝑓𝑜𝑠𝑒𝑡𝑠

Neural Method

Tabular Method+tFigure 2: (a) tabular CFR and (b) our double neural CFR framework. r̃iσ ((a|Ii )|Qj ) is the estimated regret in MCCFR, Rit−1 (a|Ii )is the cumulative regret, sti (a|Ii ) is the weighted additional strategy and Sit−1 (a|Ii ) is the cumulative behavior strategy. In tabular CFR,
cumulative regret and strategy are stored in the tabular memory, which limits it to solve large games. In DNCFR, we use double deepneural networks to approximate these two values. DNCFR needs less memory than tabular methods because of its generalization.

for those visited nodes into working memory; Define
Q = {Q1 , Q2 , ..., Qm }, where Qj ∈ Z is a set (block) of
sampled terminal histories in each iteration, such that Qj
spans the set Z. Define
considering
Pm qQj as the probability ofP
block Qj , where j=1 qQj = 1. Define q(z) = j:z∈Qj qQj
as the probability of considering a particular terminal history
z. For infoset IiP, an estimate of sampled counterfactual value
1σis ṽiσ (Ii |Qj ) = h∈Ii ,z∈Qj ,hvz q(z)π−i(z)πiσ (h,z)ui (z).
Lemma 1 ((Lanctot et al., 2009)) The sampled counterfactual value in MCCFR is the unbiased estimation of actual
counterfactual value in CFR. Ej∼qQj [ṽiσ (Ii |Qj )] = viσ (Ii ).
Define σ rs as sampled strategy profile, where σirs is the samrs
pled strategy of player i and σ−iare those for other players
expect i. The regret of P
the sampled action a ∈ A(Ii ) is definedby r̃iσ ((a|Ii )|Qj ) = z∈Qj ,havz,h∈Ii πiσ (ha, z)urs
i (z) −Pui (z)σrs
rsz∈Qj ,hvz,h∈Ii πi (h,z)ui (z), where ui (z) = π σrs (z) isia new utility weighted by πσrs1 (z) . The sampled estimationifor cumulative regret of action a after t iterations istR̃it ((a|Ii )|Qj ) = R̃it−1 ((a|Ii )|Qj )+ r̃iσ ((a|Ii )|Qj ), whereR̃i0 ((a|Ii )|Qj ) = 0.

3. Double Neural CFR
Double neural CFR algorithm will employ two neuralnetworks, one for the cumulative regret R, and the other forthe average strategy S shown in Figure 2(b).
3.1. Recurrent Neural Network Representation
The iterative updates of CFR algorithm maintain the regret
sum Rt (a|Ii ) and the average strategy σ̄it (a|Ii ). Thus, ourtwo neural networks are designed accordingly• RegretSumNetwork(RSN): according to Eq. (4), current
strategy σ t+1 (a|Ii ) is computed by the cumulative regret
Rt (a|Ii ). We only need to track the numerator in Eq. (4)since the normalization in the denominator can becomputed easily when the strategy is used. Given infosett
Ii and action a, we design a neural network R(a,Ii |θR)tt
to track R (a|Ii ), where θR are the network parameters.
• AvgStrategyNetwork(ASN): according to Eq. (6), theapproximate Nash equilibrium is the weighted averageof all previous behavior strategies up to t iterations, whichis computed by the normalization of cumulative strategy
S t (a|Ii ). Similar to the cumulative regret, we employ
another deep neural network S(a|θSt ) with network
parameter θSt to track the cumulative strategy.
In order to define our R and S networks, we need to represent
the infoset in extensive-form games. In such games, players
take actions in an alternating fashion and each player makes
a decision according to the observed history. Because theaction sequences vary in length, in this paper, we model
them with recurrent neural networks and each action in thesequence corresponds to a cell in RNN. This architecture isdifferent from the one in DeepStack (Moravcik et al., 2017),
which used a fully connected deep neural network to estimate
counterfactual value. Figure 3(a) provides an illustration of
the proposed deep sequential neural network representation
for infosets. Besides the vanilla RNN, there are several
variants of more expressive RNNs, such as the GRU (Choet al., 2014) and LSTM (Hochreiter & Schmidhuber, 1997).
In our later experiments, we will compare these different
neural architectures as well as a fully connected network
representation.
Furthermore, different position in the sequence may
contribute differently to the decision making, we will add anattention mechanism (Desimone & Duncan, 1995; Cho et al.,2015) to the RNN architecture to enhance the representation.
For example, the player may need to take a more aggressive
strategy after beneficial public cards are revealed in a poker
game. Thus the information after the public cards are
revealed may be more important. In practice, we find thatthe attention mechanism can help DNCFR obtain a better
convergence rate. See Appendix E for more details on thearchitectures.
3.2. Optimization Method
The parameters in the two neural networks are optimized
via stochastic gradient descent in a stage-wise fashion,interleaving with CFR iterations. More specifically,

Double Neural Counterfactual Regret Minimization
Mini-batch Robust Sampling
Sequential Representation

player 0

player 1

𝛼1
c1

RSN

ASN

chance𝛼2[𝛼1 , 𝛼2 , … , 𝛼6 ]

+
𝛼3

c2

c3

10

10

𝛼4

𝛼5

Attention
Network

…

𝛼6
c6

c5

c4

ASN

50

20

RSN

Figure 3: (a) recurrent neural network architecture with attention for extensive games. Both RSN and ASN are based on this architecture
but with different parameters (θR and θS respectively). (b) an overview of the proposed robust sampling and mini-batch techniques. The
trajectories marked by red arrows are the samples produced by robust sampling (k = 2 here).

We use MtR =• Optimizing Current Strategy.
σt{(Ii , r̃i ((a|Ii )|Qj ))|for all sampled Ii } to store the samt
pled Ii and the corresponding regret r̃iσ ((a|Ii )|Qj )) forall players in t-th iteration, where Qj is the sampled block(shown in Figure 2(b)). These samples are produced by our
proposed robust sampling and mini-batch MCCFR methods, which will be discussed in Section 4. According
to Eq. (3), we can optimize the cumulative regret neural nett+1
work R(a,Ii |θR) using the following loss function L(R)

2

t+1
t
σt

R(·|θ
)+
r̃
(·|Q
)−R(·|θ
)

j
i
R
X
R

2

t+1
t
i∈N,  R(·|θR)+0−R(·|θR)
I ∈I ,
i

if Ii in MtRotherwise,ia∈A(Ii )
t

(7)

t
t
where R((a|Ii )|θR
) refers to R(·|θR), r̃iσ ((a|Ii )|Qj )t+1
σttrefers to r̃i (·|Qj ), θR refers to the old parameters and θR
is the new parameters we need to optimize. Note that, Eq. (7)is minimized based on the samples of all the players rather
than a particular player i. In standard MCCFR, if the infoset
is not sampled, the corresponding regret is set to 0, whichleads to unbiased estimation according to Lemma 1. The design of the loss function in Eq. (7) follows the same intuition.
Techniques in Schmid et al. (2018) can be used to reduce thevariance.

Sampling unobserved infosets? In theory, to optimize
Eq. (7), we need to collect both observed and unobserved
infosets. This approach requires us to design a suitable sampling method to select additional training samples from large
numbers of unobserved infosets, which will need a lot ofmemory and computation. Clearly, this is intractable on large
games, such as Heads-Up No-Limit Texas Hold’em (HUNL).
In practice, we find that minimizing loss only based on theobserved samples can help us achieve a converged strategy.
Learning without forgetting? Another concern is that, ineach iteration, only a small proportion of infosets are sampled
due to mini-batch training, which may result in the neuralnetworks forgetting values for those unobserved infosets. To
address this challenge, we will use the neural network param-

eters from the previous iteration as the initialization, which
gives us an online learning/adaptation flavor to the updates.
Experimentally, on large games, due to the generalization
ability of the neural networks, even a small proportion of
infosets are used to update the neural networks, our double
neural approach can still converge to an approximate Nashequilibrium. See Appendix F for more details on implementation.
Scaling regret for stable training? According to Theotremp 6 in Burch (2017), the cumulative regret Ri (a|Ii ) ≤∆ |A|T , where |A| = maxIi ∈I |A(Ii )| and ∆ =maxIi ,a,t |Rt (a|Ii )−Rt−1 (a|Ii )|. It indicates that Rit (a|Ii )will become increasingly large.√In practice, we scale thecumulative regret by a factor of t to make its range√ morestable. For example, define R̂it (a|Ii ) = Rit (a|Ii )/ t, we
can update the cumulative regret Eq. (3) by R̂it (a|Ii ) =√√t( t−1R̂it−1 (a|Ii )+riσ (a|Ii ))/ t, where R̂i0 (a|Ii ) = 0.
• Optimizing Average Strategy. Another memory MtS ={(Ii , sti (a|Ii )|for all sampled Ii } will store the sampled Ii
and the weighted additional behavior strategy sti (a|Ii ) in t-th
iteration. Similarly, the loss function L(S) of ASN is defined
by:

2

t+1
t
t

S(·|θ
)+s
(a|I
)−S(·|θ
)

i
i
S
X
S

2

i∈N, 
 S(·|θSt )+0−S(·|θSt+1 )I ∈I ,
i

if Ii in MtS(8)otherwise.

ia∈A(Ii )where S(·|θSt ) refers to S(a,Ii |θSt ), θSt refers to the old parameters and θSt+1 is the new parameters we need to optimize.
According to Algorithm 1, cumulative regret is used to generate behavior strategy in the next iteration while cumulative
strategy is the summation of the weighted behavior strategy.
In theory, if we have all the MtS in each iteration, we canachieve the final average strategy directly. Based on thisconcept, we don’t need to optimize the average strategy network (ASN) S(·|θSt ) in each iteration. However, saving all
such values into a huge memory is very expensive on large
games. A compromise is that we can save such values within

Double Neural Counterfactual Regret Minimization

multiple iterations into a memory, when this memory is large
enough, the incremental value within multiple iterations canbe learned by optimizing Eq. (8).

Algorithm 2: DNCFR Algorithm
Function Agent(T , b):
For t = 1 to T do
3
if t = 1 and using warm starting thent
4
Initialize θRand θSt from a checkpoint t ← t+1
5
else
t
6
Initialize θRand θSt randomly.
7
MtR ,MtS ← sampling methods.
8
Sum aggregate value in MR by infoset.
9Remove duplicated records in MS .
t−1
t−1 ∗
t
10
θR
← NeuralAgent(R(·|θR),MtR ,θR
,βR )
t−1
t−1 ∗
t
t
11
θS ← NeuralAgent(S(·|θS ),MS ,θS ,βS )12Minimum squared loss versus maximum likelihood? The
average strategy is a distribution over actions, which implies
that we can use maximum likelihood method to directly
optimize this average strategy. The maximum likelihood
method should base on the whole samples up to t-th iteration
rather than only the additional samples, so that this method isvery memory-expensive. To address this limitation, we canuse uniform reservoir sampling method (Osborne et al., 2014)treturn θR,θSt
to obtain the unbiased estimation of each strategy. In practice, 12
we find this maximum likelihood method has high varianceand cannot approach a less exploitable Nash equilibrium.
4. Efficient Training
Experimentally, optimization by minimizing squared loss
In this section, we will propose two techniques to improvehelps us obtain a fast convergent average strategy profile andthe efficiency of the double neural method. These techniques
uses much less memory than maximum likelihood method.
can also be used separately in other CFR variants.
3.3. Continual Improvement
When solving large IIGs, current methods such as Libratus (Brown & Sandholm, 2017) and DeepStack (Moravcik
et al., 2017) are based on the abstracted HUNL which has amanageable number of infosets. The abstraction techniques
are usually based on domain knowledge, such as clustering
similar hand-strength cards into the same buckets or only
taking discrete actions (e.g., fold, call, one-pot raise andall in). DNCFR is not limited by the specified abstracted
cards or actions. For example, we can use the continuous variable to represent bet money rather than encode it
by discrete action. In practice, DNCFR can clone an existing tabular representation or neural representation andthen continually improve the strategy from the initialized
point. More specifically, for infoset Ii and action a, define
Ri0 (a|Ii ) as the cumulative regret . We can use behavior
cloning technique to learn the cumulative regret by optimiz2
P0∗
ing θR← argminθR Ii ∈Ii R(·|θR ) − R (·|Ii ) . Similarly, the cumulative strategy can be cloned in the same way.
Based on the learned parameters, we can warm start DNCFRand continually improve beyond the tabular strategy profile.
3.4. Overall Algorithm
Algorithm 2 provides a summary of the proposed double neural counterfactual regret minimization approach. In the first
iteration, if the system warm starts from tabular-based methods, the techniques in Section 3.3 will be used to clone thecumulative regrets and strategies. If there is no warm start initialization, we can start our algorithm by randomly initializing the parameters in RSN and ASN. Then sampling methods
will return the sampled infosets and values, which are saved inmemories MtR and MtS respectively. These samples will be
used by the NeuralAgent algorithm from Algorithm 3 to optimize RSN and ASN. Further details for the sampling methods
will be discussed in the next section. Due to space limitation,
we present NeuralAgent fitting algorithm in Appendix F.

4.1. Robust Sampling TechniqueIn the robust sampling method, the sampled profile is ders(k)fined by σ rs(k) = (σi,σ−i ), where player i will randomlyrs(k)select k actions according to sampled strategy σi(Ii )for each infoset Ii and other players will randomly select one action according to strategy σ−i . Specifically, if
player i randomly selects min(k,|A(Ii )|) actions according
to discrete uniform distribution unif (0,|A(Ii )|) at infoset
rs(k)
rs(k)
i )|)
Ii , i.e., σi(a|Ii ) = min(k,|A(I, then πiσ(Ii ) =|A(Ii )|Q
min(k,|A(Ii0 )|)and the weighted utilh∈Ii ,h0 vh,h0 avh,h0 ∈I 0
|A(I 0 )|
i

i

rs(k)

ity ui(z) will be a constant number in each iteration,
which has a low variance. In addition, because the weighted
utility no longer requires explicit knowledge of the opponent’s strategy, we can use this sampling method for online
regret minimization. For simplicity, k = max refers to selecting all actions in one infoset in the following sections.
Theorem 1 If k = maxIi ∈I |A(Ii )| and for each actionrs(k)σi(a|Ii ) = 1, then robust sampling becomes externalrs(k)sampling; If k = 1, σi= σi and q(z) ≥ δ > 0, then robust
sampling becomes outcome sampling.
See Appendix D.2 for proof. The Theorem 1 shows thatrobust sampling technique has lower variance than theoutcome sampling while being more memory-efficient thanthe external sampling.
4.2. Mini-batch Technique
Traditional MCCFR only samples one block in an iteration and provides an unbiased estimation of origin
CFV. In this paper, we present a mini-batch Monte
Carlo technique and randomly sample b blocks in one
iteration. Let Qj denote a block of terminals sampledaccording to the scheme in Section 4.1, then minibatch CFV with mini-batch size b will be ṽiσ (Ii |b) =
Pb P
σ
σ
j=1
h∈Ii ,hvz,z∈Qj π−i (z)πi (h,z)ui (z)/(bq(z)).

Double Neural Counterfactual Regret Minimization

Theorem 2 EQj ∼Robust Sampling [ṽiσ (Ii |b)] = viσ (Ii ).
We prove that ṽiσ (Ii |b) is an unbiased estimation of CFV
in Appendix D.3. Following the similar ideas of CFR and
CFR+, if we replace the regret matching by regret matchingplus (Tammelin, 2014), we obtain a mini-batch MCCFR+
algorithm. Our mini-batch technique empirically cansample b blocks in parallel and converges faster than original
MCCFR when performing on multi-core machines.

5. Experiment
To understand the contributions of various components in
DNCFR algorithm, we will first conduct a set of ablation
studies. Then we will compare DNCFR with tabular CFR
and deep reinforcement learning based method such as NFSP.
At last, we conduct experiments in large scale problems toshow the scalability of DNCFR algorithm.
Settings. We will perform experiments in three Leduc
Hold’em instances with stack size 5, 10, and 15, which
are denoted by Leduc(5), Leduc(10), and Leduc(15) respectively (Schmid et al., 2018), as well as four different HUNL
subgame instances generated by DeepStack. The rules forsuch games are given in Appendix A. The experiment results are evaluated by exploitability, which is defined inAppendix B. Lower exploitability indicates better performance (Johanson et al., 2011). The exploitability is computedon each game instance.
Ablation studies. We first conduct a set of ablation studies
related to the mini-batch training, robust sampling, the choiceof neural architecture.
• Is mini-batch sampling helpful? we present the convergence curves of the proposed robust sampling methodwith k = max(|A(Ii )|) under different mini-batch sizes(b=1, 1000, 5000, 10000 respectively) in Figure 7(a) at
Appendix C. The experimental results show that larger
batch sizes generally lead to better strategy profiles.
• Is robust sampling helpful? Figure 4 (a) presents
convergence curves for outcome sampling, external
sampling(k = max(|A(Ii )|)) and the proposed robust sampling method under the different number of sampled actions. The outcome sampling cannot converge to a low
exploitability( smaller than 0.1 after 1000 iterations). The
proposed robust sampling algorithm with k = 1, which
only samples one trajectory like the outcome sampling,
can achieve a better strategy profile after the same numberof iterations. With an increasing k, the robust sampling
method achieves an even better convergence rate. Experiment results show k = 3 and 5 have a similar trend withk = max(|A(Ii )|), which demonstrates that the proposedrobust sampling achieves similar performance but requires
less memory than the external sampling. We choose k = 3
for the later experiments in Leduc Hold’em.

• Is attention in the neural architecture helpful? Figure 4(b) shows that all the neural architectures achieved
similar results while LSTM with attention achievedslightly better performance with a large number of iterations. We select LSTM plus attention as the default
architectures in the later experiments.
• Do the neural networks just memorize but not generalize? One indication that the neural networks are generalizing is that they use much fewer parameters than theirtabular counterparts. We experimented with LSTM plus
attention networks, and embedding size of 8 and 16 respectively. These architectures contain 1048 and 2608
parameters respectively, both of which are much less than
the tabular memory (more than 11083 here) and can lead toa converging strategy profile as shown in Figure 4(c). We
select embedding size 16 as the default parameters in thelater experiments. Other parameters of neural networks
and optimizers are presented in Appendix F.
• Do the neural networks generalize to unseen infosets?
To investigate the generalization ability, we perform the
DNCFR with small mini-batch sizes (b=50, 100, 500),
where only 3.08%, 5.59%, and 13.06% infosets are observed in each iteration. In all these settings, DNCFR
can still converge and arrive at exploitability less than 0.1
within only 1000 iterations as shown in Figure 4(d). In thelater experiments, we set b=100 as the default mini-batchsize.
• What is the individual effect of RSN and ASN? Figure 5(a) presents ablation study of the effects of RSN and
ASN network respectively. Specifically, the method RSN
denotes that we only employ RSN to learn the cumulative
regret while the cumulative strategy is stored in a tabular
memory. Similarly, the method ASN only employ ASN
to learn the cumulative strategy. Both these single neural
methods perform only slightly better than the DNCFR.
• How well does continual improvement work? As
shown in Figure 5(b), warm starting from either full-width
based or sampling based CFR can lead to continual improvements. Specifically, the first 10 iterations are learnedby tabular based CFR and RS-MCCFR+. After the behavior cloning in Section 3.3, the remaining iterations arecontinually improved by DNCFR.
How does DNCFR compare to the tabular counterpart,
XFP, and NFSP? To obtain an approximation of Nash equilibrium, Figure 5(c) demonstrates that NFSP needs 106 iterations to reach a 0.06-Nash equilibrium, and requires twomemories to store 2 × 105 state-action pair samples and2 × 106 samples for supervised learning respectively. The
XFP needs 103 iterations to obtain the same exploitability,
however, this method is the precursor of NFSP and updated
by a tabular based full-width fictitious play. Our DNCFR only
needs 200 iterations to achieve the same performance andconverges significantly better than the reinforcement learn-

Double Neural Counterfactual Regret Minimization(a) Sampling methods(b) Neural architectures(c) Number of parameters(d) Sampling proportion

Figure 4: Log-log performance on Leduc(5). (a) different sampling methods, k refers to the number of sampling action for the proposedrobust sampling method in each infoset. (b) neural architectures. (c) number of parameters. (d) proportion of observed infosets. Higher
proportion indicates more working memory.

(a) Individual network(b) Warm starting(c) DNCFR vs NFSP(d) Large Leduc Hold’em

Figure 5: Log-log performance. (a) Individual effect of RSN and ASN. RS-MCCFR+ refers to the tabular mini-batch MCCFR+ methodwith the proposed robust sampling. RS-MCCFR+-RSN only uses one neural network RSN to learn cumulative regret while uses a tableto save cumulative strategy. RS-MCCFR+-ASN only use one neural network ASN. RS-MCCFR+-RSN-ASN refers to DNCFR with both
RSN and ASN. (b) Warm start from tabular CFR and RS-MCCFR+. (c) DNCFR vs XFP vs NFSP. (d) Large Leduc(10) and Leduc(15).
ing counterpart. The DNCFR can achieve an exploitability of
0.02 after 1k iterations, which is similar to the tabular method
as shown in Figure 4(d). In each iteration, NFSP generated
the 128 samples (it needs 200k memory to save samples in
multiple iterations, larger than #infosets) while DNCFR generated 620 samples (5.59% of the total infosets) by robust
sampling with k=3. Although DNCFR used slightly more
samples in each iteration, it achieved a better strategy profile
with much fewer iterations.
Table 1: Summary. #infoset is the number of infosets. #state is
the number of states. %observed is the ratio of observed infosets
in each iteration. #emd and #param are the embedding size and thenumber of parameters in DNCFR. Both tabular CFR and DNCFR
achieve the same exploitability on these game instances.
Game#infoset#state %observed #emd #param
Leduc(5)1×104 6×105
5.59%
16
2608
Leduc(10)3×105 2×106
2.39%
32
7424
Leduc(15)3×106 2×107
0.53%
64 23360
River(0.5%) 1×105 1×108
0.5%
256 10450
River(1%)
1×105 1×1081%
256 10450
River(10%) 1×105 1×10810%
256 10450
Turn(10%)
3×107 4×1010
10% 1024 465920

Convergence in large games. Table 1 shows that eventhough a small proportion of nodes are observed, DNCFR canstill converge because of its generalization ability. DNCFR
needs much less memory to achieve the same exploitability(0.01 of the games’ stack sizes) with the tabular CFR on large
games. Figure 5(d) presents the convergence of DNCFR on
large Leduc Hold’em.
Space and time trade-off. In this experiment, we investigate the time and space needed for DNCFR to achieve certain
exploitability relative to tabular CFR algorithm across all
experimented games as listed in Table 1. It’s clear that the
number of infosets is much more than the number of parameters used in DNCFR. For example, on Leduc(15), tabular
CFR needs 128 times more memory than DNCFR. We compare their runtime and memory in Figure 6. In the figure, we
use the ratio between the runtime of DNCFR and CFR ashorizontal axis, and the sampling(observed) infosets ratios
of DNCFR and full-width tabular CFR as vertical axis. Note
that, the larger the sampling ratio, the more memory will beneeded to save the sampled values. Clearly, it can be seen
there is a trade-off between the relative runtime and relative

Double Neural Counterfactual Regret Minimization

Figure 6: Observed ratio and runtime.
memory in DNCFR: the longer the relative runtime, the lessthe relative memory needed for DNCFR. It is reasonable to expect that a useful method should lead to “fair” trade between
space and time. That is onefold increase in relative runtime
should lead onefold decreases in relative memory (the dashedline in Figure 6, slope -1). Interestingly, DNCFR achieves amuch better trade-off between relative runtime and memory:for onefold increases in relative runtime, DNCFR may leadto fivefold decreases in relative memory consumption (redline, slope -5). We believe this is due to the generalization
ability of the learned neural networks in DNCFR.

6. Conclusions
We proposed a novel double neural counterfactual regret
minimization approach to solve IIGs. It uses two coupleddeep neural networks to learn the strategy profiles directlyfrom data—without domain-specific game abstraction, we
have also developed new sampling methods for IIGs withproven variance and memory reduction. Experimental
results verified the effectiveness of our DNCFR approach.

Double Neural Counterfactual Regret Minimization

References
Brown, N. and Sandholm, T. Superhuman AI for heads-up
no-limit poker: Libratus beats top professionals. Science,
pp. eaao1733, 2017.
Burch, N. Time and Space: Why Imperfect Information
Games are Hard. PhD thesis, 2017.
Cho, K., Van Merriënboer, B., Gulcehre, C., Bahdanau,D., Bougares, F., Schwenk, H., and Bengio, Y. Learningphrase representations using RNN encoder-decoder
for statistical machine translation.
arXiv preprint
arXiv:1406.1078, 2014.
Cho, K., Courville, A., and Bengio, Y. Describing Multimedia Content using Attention-based EncoderDecoder
Networks. arXiv preprint arXiv:1507.01053, 2015.
Desimone, R. and Duncan, J. Neural mechanisms of
selective visual attention. Number 18, pp. 193–222.
Annual review of neuroscience, 1995.
Gibson, R. G. Regret minimization in games and the development of champion multiplayer computer poker-playing
agents. 2014.
Gordon, G. J. No-regret algorithms for structured prediction
problems. Number CMU-CALD-05-112. CARNEGIEMELLON UNIV PITTSBURGH PA SCHOOL OFCOMPUTER SCIENCE, 2005.
Harris, D. and Harris, S. Digital design and computerarchitecture (2nd ed.), volume ISBN 978-0-12-394424-5.
San Francisco, Calif.: Morgan Kaufmann.
Heinrich, J. and Silver, D. Deep reinforcement learning fromself-play in imperfect-information games. arXiv preprint
arXiv:1603.01121, 2016.
Heinrich, J., Lanctot, M., and Silver, D. Fictitious self-playin extensive-form games. pp. 805–813. International
Conference on Machine Learning, 2015.
Hochreiter, S. and Schmidhuber, J. Long short-term memory.
Number 8, pp. 1735–1780. Neural computation, 1997.
Jin, P., Keutzer, K., and Levine, S. Regret minimization forpartially observable deep reinforcement learning. arXiv
preprint arXiv:1710.11424, 2017.
Johanson, M. Measuring the size of large no-limit poker
games. arXiv preprint arXiv:1302.7008, 2013.
Johanson, M., Waugh, K., Bowling, M., and Zinkevich, M.
Accelerating best response calculation in large extensive
games. In Twenty-Second International Joint Conferenceon Artificial Intelligence, 2011.

Kingma, D. P. and Ba, J. Adam: A method for stochastic
optimization. arXiv preprint arXiv:1412.6980, 2014.
Lanctot, M., Kevin, W., Martin, Z., and Bowling, M. Monte
Carlo sampling for regret minimization in extensive
games. In Advances in neural information processing
systems, 2009.
Moravcik, M., Martin, S., Neil, B., Viliam, L., Morrill, D.,
Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelligence inheads-up no-limit poker. Science, (6337):508–513, 2017.
Osborne, M., Lall, A., and Van Durme, B. Exponential
reservoir sampling for streaming language models.
In Proceedings of the 52nd Annual Meeting of the
Association for Computational Linguistics (Volume 2:
Short Papers), volume 2, pp. 687–692, 2014.
Osborne, M. J. and Rubinstein, A. A course in game theory,
volume 1. MIT Press, 1994.
Ruder, S. An overview of gradient descent optimization
algorithms. arXiv preprint arXiv:1609.04747, 2017.
Schmid, M., Burch, N., Lanctot, M., Moravcik, M., Kadlec,
R., and Bowling, M. Variance Reduction in Monte Carlo
Counterfactual Regret Minimization (VR-MCCFR) for
Extensive Form Games using Baselines. arXiv preprint
arXiv:1809.03057, 2018.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.,
Driessche, G. V. D., and et al., J. S. Mastering the gameof Go with deep neural networks and tree search. Nature,(7587), 2016.
Southey, F., Bowling, M. P., Larson, B., Piccione, C., Burch,N., Billings, D., and Rayner, C. Bayes’ bluff: Opponent
modelling in poker. arXiv preprint arXiv:1207.1411,
2012.
Srinivasan, S., Lanctot, M., Zambaldi, V., Pérolat, J.,
Tuyls, K., Munos, R., and Bowling, M. Actor-critic
policy optimization in partially observable multiagent
environments. In Advances in Neural Information
Processing Systems, pp. 3422–3435, 2018.
Tammelin, O. Solving large imperfect information games
using CFR+. arXiv preprint, 2014.
Waugh, K., Morrill, D., Bagnell, J. A., and Bowling, M.
Solving Games with Functional Regret Estimation. In
AAAI, volume 15, pp. 2138–2144, 2015.
Zinkevich, M., Michael, J., Michael, B., and Piccione, C. Regret minimization in games with incomplete information.
Advances in neural information processing systems, 2007.

Double Neural Counterfactual Regret Minimization

A. Game Rules
A.1. One-Card Poker
One-Card Poker is a two-players IIG of poker described by Gordon (2005). The game rules are defined as follows. Each
player is dealt one card from a deck of X cards. The first player can pass or bet, If the first player bet, the second player cancall or fold. If the first player pass, the second player can pass or bet. If the second player bet, the first player can fold orcall. The game ends with two pass, call, fold. The fold player will lose 1 chip. If the game ends with two passes, the player
with higher card wins 1 chip, If the game ends with call, the player with higher card wins 2 chips.
A.2. Leduc Hold’em
Leduc Hold’em a two-players IIG of poker, which was first introduced in Southey et al. (2012). In Leduc Hold’em, there isa deck of 6 cards comprising two suits of three ranks. The cards are often denoted by king, queen, and jack. In Leduc Hold’em,
the player may wager any amount of chips up to a maximum of that player’s remaining stack. There is also no limit on thenumber of raises or bets in each betting round. There are two rounds. In the first betting round, each player is dealt one cardfrom a deck of 6 cards. In the second betting round, a community (or public) card is revealed from a deck of the remaining
4 cards. In this paper, we use Leduc(x) refer to the Leduc Hold’em with stack size is x.
A.3. Heads-Up No-Limit Texas Hold’em
Heads-Up No-Limit Texas hold’em (HUNL) has at most four betting rounds if neither of two players fold during playing.
The four betting rounds are preflop, flop, turn, river respectively. The rules are defined as follows. In Annual Computer Poker
Competition (ACPC), initially, two players each have 20000 chips. One player at the position of small blind, firstly puts
50 chips in the pot, while the other player at the big blind then puts 100 chips in the pot. After that, the first round of betting
is followed. If the preflop betting round ends without a player folding, then three public cards are revealed face-up on thetable and the flop betting round occurs. After this round, one more public card is dealt (called the turn) and the third roundof betting takes place, followed by a fifth public card (called the river ) and a final round of betting begins. In no-limit poker
player can take fold, call and bet actions and bet number is from one big blind to a number of chips a player has left in his stack.

Double Neural Counterfactual Regret Minimization

B. Definition of Extensive-Form Games
B.1. Detailed Definitions and Notations
We define the components of an extensive-form game following (Osborne & Rubinstein, 1994) (page 200 ∼ 201).
A finite set N = {0, 1, ..., n − 1} of players. Define xvi as the hidden variable of player i in IIG, e.g., inpoker game xvi refers to the private cards of player i. H refers to a finite set of histories. Each memberh = (xvi )i=0,1,...,n−1 (al )l=0,...,L−1 = xv0 xv1 ...xvn−1 a0 a1 ...aL−1 of H denotes a possible history (or state), which
consists of each player’s hidden variable and L actions taken by players including chance. For player i, h also can be denoted
as xvi xv−i a0 a1 ...aL−1 , where xv−i refers to the opponent’s hidden variables. The empty sequence ∅ is a member of H. hj v hdenotes hj is a prefix of h, where hj = (xvi )i=0,1,...,n−1 (al )l=1,...,L0 −1 and 0 < L0 < L. Z ⊆ H denotes the terminal histories
and any member z ∈ Z is not a prefix of any other sequences. A(h) = {a : ha ∈ H} is the set of available actions after
non-terminal history h ∈ H \Z. A player function P assigns a member of N ∪{c} to each non-terminal history, where cdenotes the chance player id, which usually is -1. P (h) is the player who takes an action after history h.
Ii of a history {h ∈ H : P (h) = i} is an information partition of player i. A set Ii ∈ Ii is an information set (infoset) ofplayer i and Ii (h) refers to infoset Ii at state h. Generally, Ii could only remember the information observed by player i
including player i0 s hidden variable and public actions. Therefore Ii indicates a sequence in IIG, i.e., xvi a0 a2 ...aL−1 . For
Ii ∈ Ii we denote by A(Ii ) the set A(h) and by P (Ii ) the player P (h) for any h ∈ Ii . For each player i ∈ N a utility functionui (z) define the payoff of the terminal state z.
P
For player i, the expected game utility uσi = z∈Z π σ (z)ui (z) of σ is the expected payoff of all possible terminal nodes.
(σ 0 ,σ)Given a fixed strategy profile σ−i , any strategy σi∗ = argmaxσi0 ∈Σi ui i −i of player i that achieves maximize payoff
σagainst π−i
is a best response. For two players’ extensive-form games, a Nash equilibrium is a strategy profile σ ∗ = (σ0∗ ,σ1∗ )such that each player’s strategy is a best response to the opponent. An -Nash equilibrium is an approximation of a Nashσ∗(σ 0 ,σ )equilibrium, whose strategy profile σ ∗ satisfies: ∀i ∈ N , ui i +  ≥ maxσi0 ∈Σi ui i −i . Exploitability of a strategy σi is∗(σi ,σ ∗ )−idefined as i (σi ) = uσi −ui. A strategy is unexploitable if i (σi ) = 0. In large two player zero-sum games such poker,σ∗ui is intractable to compute. However, if the players alternate their positions, the value of a pair of games is zeros, i.e.,∗∗(σ ,σ ∗ )(σ ∗ ,σ )uσ0 +uσ1 = 0 . We define the exploitability of strategy profile σ as (σ) = (u1 0 1 +u0 0 1 )/2.

B.2. Explanation by Example
To provide a more detailed explanation, Figure 1 presents an illustration of a partial game tree in One-Card Poker. In thefirst tree, two players are dealt (queen, jack) as shown in the left subtree and (queen, king) as shown in the right subtree. zi
denotes terminal node and hi denotes non-terminal node. There are 19 distinct nodes, corresponding 9 non-terminal nodes
including chance h0 and 10 terminal nodes in the left tree. The trajectory from the root to each node is a history of actions.
In an extensive-form game, hi refers to this history. For example, h3 consists of actions 0:Q, 1:J and P. h7 consists of actions
0:Q, 1:J, P and B. h8 consists of actions 0:Q, 1:K, P and B. We have h3 v h7 , A(h3 ) = {P,B} and P (h3 ) = 1.
In IIG, the private card of player 1 is invisible to player 0, therefore h7 and h8 are actually the same for player 0. We use
infoset to denote the set of these undistinguished states. Similarly, h1 and h2 are in the same infoset. For the right tree of
Figure 1, h03 and h05 are in the same infoset. h04 and h06 are in the same infoset.
Generally, any Ii ∈ I could only remember the information observed by player i including player i0 s hidden variableand public actions. For example, the infoset of h7 and h8 indicates a sequence of 0:Q, P, and B. Because h7 and h8 areundistinguished by player 0 in IIG, all the states have a same strategy. For example, I0 is the infoset of h7 and h8 , we have
I0 = I0 (h7 ) = I0 (h8 ), σ0 (I0 ) = σ0 (h7 ) = σ0 (h8 ), σ0 (a|I0 ) = σ0 (a|h7 ) = σ0 (a|h8 ).
B.3. Detailed Definition about Strategy and Nash Equilibrium
A strategy profile σ = {σi |σi ∈ Σi ,i ∈ N } is a collection of strategies for all players, where Σi is the set of all possible
strategies for player i. σ−i refers to strategy of all players other than player i. For play i ∈ N the strategy σi (Ii ) isa function, which assigns an action distribution over A(Ii ) to infoset Ii . σi (a|h) denotes the probability of action ataken by player i ∈ N ∪ {c} at state h. In IIG, ∀h1 ,h2 ∈ Ii , we have Ii = Ii (h1 ) = Ii (h2 ), σi (Ii ) = σi (h1 ) = σi (h2 ),σi (a|Ii ) = σi (a|h1 ) = σi (a|h2 ). For iterative method such as CFR, σ t refers to the strategy profile at t-th iteration.
The state reach probability of history h is denoted by π σ (h) if players take actions according to σ. For an empty sequenceDouble Neural Counterfactual Regret MinimizationQσπ σ (∅) = 1. The reach probability can be decomposed into π σ (h) = i∈N ∪{c} πiσ (h) = πiσ (h)π−i(h) according to each
Q
Q
σ
0
σ
player’s contribution, where πi (h) = h0 avh,P (h0 )=P (h) σi (a|h ) and π−i (h) = h0 avh,P (h0 )6=P (h) σ−i (a|h0 ).
P
The infoset reach probability of Ii is defined as π σ (Ii ) = h∈Ii π σ (h). If h0 v h, the interval state reach probability fromσσstate h0 to h is defined as π σ (h0 ,h), then we have π σ (h0 ,h) = π σ (h)/π σ (h0 ). πiσ (Ii ), π−i(Ii ), πiσ (h0 ,h), and π−i(h0 ,h) aredefined similarly.

Double Neural Counterfactual Regret Minimization

C. Additional Experiment Results
Figure 7(a) shows that the robust sampling with a larger batch size indicates better performance. It’s reasonable because alarger batch size will lead to more sampled infosets in each iteration and costs more memory to store such values. If b = 1, only
one block is sampled in each iteration. The results demonstrate that the larger batch size generally leads to faster convergence.
Because it’s easy to sample the mini-batch samples by parallel fashion on a large-scale distributed system, this method isvery efficient. In practice, we can specify a suitable mini-batch size according to computation and memory size.
In Figure 7(b), we compared the proposed robust sampling against Average Strategy (AS) sampling (Gibson, 2014) on
Leduc Holdem (stack=5). Set the mini-batch size of MCCFR as b = 100, k = 2 in robust sampling. The parameters in average
strategy sampling are set by  = k/|A(I)|, τ = 0, and β = 0. After 1000 iterations, the performance of our robust sampling
is better than AS. More specifically, if k=1, the exploitability of our robust sampling is 0.5035 while AS is 0.5781. If k=2,
the exploitability of our robust sampling is 0.2791 while AS is 0.3238. Robust sampling samples a min(k,|A(I)|) player
i’s actions while AS samples a random number of player i’s actions. Note that, if ρ is small or the number of actions is small,it has a possibility that the generated random number between 0 and 1 is larger than ρ for all actions, then the AS will sample
zero action. Therefore, AS has a higher variance than our robust sampling. In addition, according to Gibson (2014), theparameter scopes of AS are  ∈ (0,1], τ ∈ [1,∞), β ∈ [0,∞) respectively. They didnt analyze the experiment results for τ < 1.

100
Exploitability

Exploitability

100

10 1

10 2 100

RS-MCCFR+(b=1)
RS-MCCFR+(b=1000)
RS-MCCFR+(b=5000)
RS-MCCFR+(b=10000)
101
102
Iteration(a) Mini-batch size103

10 1 100

strategy sampling(k=1)
strategy sampling(k=2)
robust sampling(k=1)
robust sampling(k=2)
101
102
Iteration

103(b) Mini-batch size

Figure 7: Comparison of different CFR-family methods on Leduc Hold’em. (a) Performance of robust sampling with different
batch size. (b) Robust sampling vs strategy sampling.

Double Neural Counterfactual Regret Minimization

D. Theoretical Analysis
D.1. Reach Probability and Posterior Probability
Lemma 2 The reach probability of the opponent is proportional to posterior probability of the opponent’s hidden variable,
σi.e.,p(xv−i |Ii ) ∝ π−i(h), where xvi and Ii indicate a particular h.
Proof
For player i at infoset Ii and fixed i0 s strategy profile σi , i.e., ∀h ∈ Ii ,πiσ (h) is constant. Based on the defination of extensiveform game, the cominbation of Ii and opponent’s hidden state xv−i can indicate a particular history h = xvi xv−i a0 a1 ...aL−1 .
With Bayes’ Theorem, we can inference the posterior probability of opponent’s private cards with Equation9.
p(xv−i ,Ii ) p(h)=∝ p(h)p(Ii )p(Ii )LY∝ p(xvi )p(xv−i ) σP (xvi xv−i a0 a1 ...al−1 ) (al |xvi xv−i a0 a1 ...al−1 )p(xv−i |Ii ) =

(9)

l=1
σ
∝ π σ (h) = πiσ (h)π−i(h)σ∝ π−i (h)D.2. Robust Sampling, Outcome Sampling and External Samplingrs(k)(a|Ii ) = 1, then robust sampling becomes external sampling;
Theorem 1 If k = maxIi ∈I |A(Ii )| and for each action σirs(k)If k = 1, σi= σi and q(z) ≥ δ > 0, then robust sampling becomes outcome sampling.
Proof
rs(k)

For robust sampling, given strategy profile σ and the sampled block Qj according to sampled profile σ rs(k) = (σirs(k)σ
then q(z) = πiσ(z)π−i(z), and the regret of action a ∈ Ars(k) (Ii ) isr̃iσ ((a|Ii )|Qj ) = ṽiσ ((a|Ii )|Qj )−ṽiσ (Ii |Qj )X
1 σπ (z)πiσ (ha,z)ui (z)−=q(z) −iz∈Qj ,havz,h∈Ii

Xz∈Qj ,hvz

1 σ
π (z)πiσ (h,z)ui (z)q(z) −iXui (z)ui (z)σ=π(ha,z)−πiσ (h,z)
i
rs(k)
rs(k)
σ
σ
π
π
(z)
(z)
i
i
z∈Qj ,havz,h∈Iiz∈Qj ,hvz,h∈Ii
X
X
σ
rs
=
πi (ha,z)ui (z)−πiσ (h,z)urs
i (z),Xz∈Qj ,havz,h∈Ii

where ursi (z) =πiσui (z)rs(k)(z),σ−i ),(10)z∈Qj ,hvz,h∈Ii

is the weighted utility according to reach probability πiσrs(k)(z). Because the weighted utility nolong requires explicit knowledge of the opponent’s strategy, we can use this sampling method for online regret minimization.
Generally, if player i randomly selects min(k,|A(Ii )|) actions according to discrete uniform distribution unif (0,|A(Ii )|)
rs(k)
i )|)
at infoset Ii , i.e., σi(a|Ii ) = min(k,|A(I, then|A(Ii )|
πiσ

rs(k)

(Ii ) =Y

min(k,|A(Ii0 )|)|A(Ii0 )|0h∈Ii ,h0 vh,h0 avh,h0 ∈Iirs(k)and urs.
i (z) is a constant number when given the sampled profile σ(11)Double Neural Counterfactual Regret Minimization

Specifically,rs(k)• if k = maxIi ∈I |A(Ii )|, then σiXr̃iσ ((a|Ii )|Qj ) =rs(k)(Ii ) = 1, ui(z) = ui (z), andui (z)(πiσ (ha,z)−πiσ (h,z))(12)z∈Qj ,hvz,h∈Ii

Therefore, robust sampling is same with external sampling when k = maxIi ∈I |A(Ii )|. For large game, because
one player should take all actions in her infosets, it’s intractable for external sampling. The robust sampling is more
flexible and memory-efficient than external sampling. In practice, we can specify a suitable k according our memory.
Experimentally, the smaller k can achieve a similar convergence rate to the external sampling.

rs(k)• if k = 1 and σi

rs(k)= σi , only one history z is sampled in this case,then uir̃iσ ((a|Ii )|Qj ) = r̃iσ ((a|h)|Qj )X=
πiσ (ha,z)urs
i (z)−z∈Qj ,havz

X(z) = πuσii(z), ∃h ∈ Ii , for a ∈ Ars(k) (Ii )(z)iπiσ (h,z)ursi (z)z∈Qj ,hvz(13)(1−σi (a|h))ui (z)=πiσ (ha)For a 6∈ Ars(k) (Ii ), the regret will be r̃iσ ((a|h)|j) = 0−ṽiσ (h|j). If we add exploration and guarantee q(z) ≥ δ > 0, thenrs(k)robust sampling is same with outcome sampling when k = 1 and σi= σi .

• if k = 1, and player i randomly selects one action according to discrete uniform distribution unif (0,|A(Ii )|) at infosetrs(1)ui (z)
Ii , then ui(z) = σrs(k)is a constant, ∃h ∈ Ii , for a ∈ Ars(k) (Ii )
πi
(z)
X
X
r̃iσ ((a|Ii )|Qj ) =πiσ (ha,z)urs
πiσ (h,z)urs
i (z)−i (z)z∈Qj ,havz,h∈Iiz∈Qj ,hvz,h∈Ii
(14)
rs(1)

= (1−σi (a|h))πiσ (ha,z)ui(z)

if action a is not sampled at state h, the regret is r̃iσ ((a|h)|j) = 0 − ṽiσ (h|j). Compared to outcome sampling, thers(1)robust sampling in that case have a lower variance because of the constant ui(z).

D.3. Unbiased Mini-Batch MCCFR
Theorem 2 EQj ∼Robust Sampling [ṽiσ (Ii |b)] = viσ (Ii ).
In this section, we prove that mini-Batch MCCFR gives an unbiased estimation of counterfactual value.
ProofDouble Neural Counterfactual Regret Minimization

EQj ∼Robust Sampling [ṽiσ (Ii |b)] = Eb0 ∼unif(0,b) [ṽiσ (Ii |b0 )]
 0
b
X
X

0
= Eb ∼unif(0, b)σπ−i(z)πiσ (h,z)ui (z)

0
q(z)b
j
j=1 h∈Ii ,z∈Q ,hvz


b0
X
1
= Eb0 ∼unif(0, b)  0ṽ σ (Ii |Qj )
b j=1 ibb0
1 X 1 X σṽ (Ii |Qj )
=b 0
b0 j=1 i
b =1


b
b0
1 X 1 X=
E(ṽiσ (Ii |Qj ))b 0
b0 j=1
b =1


b
b0
X
X
1
1
v σ (Ii )
=b 0
b0 j=1 ib =1= viσ (Ii )(15)

Double Neural Counterfactual Regret Minimization

E. Sequential Representation and Recurrent Neural Network with Attention
In order to define our R and S network, we need to represent the infoset Ii ∈ I in extensive-form games. In such games,
players take action in an alternating fashion and each player makes a decision according to the observed history. In this paper,
we model the behavior sequence as a recurrent neural network and each action in the sequence corresponds to a cell in RNN.
Figure 3 (a) provides an illustration of the proposed deep sequential neural network representation for infosets.
In standard RNN, the recurrent cell will have a very simple structure, such as a single tanh or sigmoid layer. Hochreiter &Schmidhuber (1997) proposed a long short-term memory method (LSTM) with the gating mechanism, which outperforms
the standard version and is capable of learning long-term dependencies. Thus we will use LSTM for the representation.
Furthermore, different position in the sequence may contribute differently to the decision making, we will add an attention
mechanism (Desimone & Duncan, 1995; Cho et al., 2015) to the LSTM architecture to enhance the representation. For
example, the player may need to take a more aggressive strategy after beneficial public cards are revealed in a poker game.
Thus the information, after the public cards are revealed may be more important.
More specifically, for l-th cell, define xl as the input vector, which can be either player or chance actions. Define el as
the hidden layer embedding, φ∗ as a general nonlinear function. Each action is represented by a LSTM cell, which has
the ability to remove or add information to the cell state with three different gates. Define the notation · as element-wiseproduct. The first forgetting gate layer is defined as glf = φf (wf [xl ,el−1 ]), where [xl ,el−1 ] denotes the concatenation ofxl and el−1 . The second input gate layer decides which values to update and is defined as gli = φi (wi [xl ,el−1 ]). A nonlinear
layer outputs a vector of new candidate values C̃l = φc (wl [xl ,el−1 ]), which decides what can be added to the state. After theforgetting gate and the input gate, the new cell state is updated by Cl = glf ·Cl−1 +gli · C̃l . The third output gate is defined as
glo = φo (wo [xl ,el−1 ]). Finally, the updated hidden embedding is el = glo ·φe (Cl ). As shown in Figure 3 (a), for each LSTM cellj, the vector of attention weight is learned by an attention network. Each member in this vector is a scalar αj = φa (wa ej ).
Pl
The attention embedding of l-th cell is then defined as eal = j=1 αj ·ej , which is the summation of the hidden embedding
ej and the learned attention weight αj . The final output of the network is predicted by a value network, which is defined aslXỹl := f (a,Ii |θ) = wy φv (eal ) = wy φv  φa (wa ej )·ej ,
(16)
j=1

where θ refers to the parameters in the defined sequential neural networks. Specifically, φf , φi , φo are sigmoid functions.
φc and φe are hyperbolic tangent functions. φa and φv are rectified linear functions.
t)=Remark. The proposed RSN and ASN share the same neural architecture, but use different parameters. That is R(a,Ii |θR
t
t
t
t
t
f (a,Ii |θR ) and S(a,Ii |θS ) = f (a,Ii |θS ). R(·,Ii |θR ) and S(·,Ii |θS ) denote two vectors of predicted value for all a ∈ A(Ii ).

Double Neural Counterfactual Regret Minimization

F. Optimizing Neural Representation and Implementation
F.1. Code for DNCFR Framework
Algorithm 2 provides a summary of the proposed double neural counterfactual regret minimization method. Specifically,in the first iteration, if we start the optimization from tabular-based methods, the techniques in Section 3.3 should be used
to clone the cumulative regrets and strategy, which is used to initialize RSN and ASN respectively. If there is no warm start
initialization, we can start our algorithm by randomly initializing the parameters in RSN and ASN. After these two kindsof initialization, we use sampling method, such as the proposed robust sampling, to collect the training samples (include
infosets and the corresponding values), which are saved in memories MtR and MtS respectively. These samples will be usedby the NeuralAgent algorithm from Algorithm 3 to optimize RSN and ASN. Algorithm 4 provides the implementation of the
proposed mini-batch robust sampling MCCFR. Note that, with the help of the proposed mini-batch techniques in Section 4, we
can collect training samples parallelly on multi-processors or distributed systems, which also leads to the unbiased estimationaccording to the proved Theorem 2. The acceleration training and distribution implementation is beyond the scope of thispaper. To compare the performance of DNCFR and tabular CFR, all of our experiments are running on a single processor.
F.2. Code for Neural Networks
Algorithm 3: Optimization of Deep Neural Network
Function NeuralAgent(f (·|θT −1 ), M, θT −1 , β ∗ ):2
initialize optimizer, scheduler
3θT ← θT −1 ,lbest ← ∞,tbest ← 0
4
For t = 1 to βepoch do
5loss ← []6
For each training epoch do
7{x(i) ,y (i) }m
M
i=1 ∼ Pm
1(i) T −18batch loss ← m)+y (i) −f (x(i) |θT ))2
i=1 (f (x |θ9back propagation batch loss with learning rate lr
10clip gradient of θT to [−,]d11
optimizer(batch loss)
12
loss.append(batch loss)
1

13
14
15
16
17
18
19
20

lr ← sheduler(lr)if avg(loss) < βloss thenT
θbest
← θT , early stopping.
else if avg(loss) < lbest thenTlbest = avg(loss), tbest ← t, θbest← θT
if t−tbest > βre thenlr ← βlr
return θT
Notations in Neural Networks. Define βepoch as training epoch, βlr as learning rate, βloss as the criteria for early stopping,
βre as the upper bound for the number of iterations from getting the minimal loss last time, θt−1 as the old parameter learnedin t−1 iteration, f (·|θt−1 ) as the neural network, M as the training samples including infosets and the corresponding targets.
∗
To simplify notations, we use β ∗ to denote the set of hyperparameters in the proposed deep neural networks. βR
and βS∗
refer to the sets of hyperparameters in RSN and ASN respectively.
Optimize Neural Networks. Algorithm 3 provides the implementation of the optimization technique for both RSN andt+1
ASN. Both R(a,Ii |θR) and S(a,Ii |θSt ) are optimized by mini-batch stochastic gradient descent method. In this paper, we
use Adam optimizer (Kingma & Ba, 2014) with both momentum and adaptive learning rate techniques. We also replace
Adam by other optimizers such as Nadam, RMSprop, Nadam Ruder (2017) in our experiments, however, such optimizers do
not achieve better experimental results. In practice, existing optimizers (Ruder, 2017) may not return a relatively low enoughloss because of potential saddle points or local minima. To obtain a relatively higher accuracy and lower optimization loss,
we design a novel scheduler to reduce the learning rate when the loss has stopped decrease. Specifically, the scheduler reads
a metrics quantity, e.g, mean squared error. If no improvement is seen for a number of epochs, the learning rate is reduced

Double Neural Counterfactual Regret Minimization

by a factor. In addition, we will reset the learning rate in both optimizer and scheduler once loss stops decreasing within
βre epochs. Gradient clipping mechanism is used to limit the magnitude of the parameter gradient and make optimizer behave
better in the vicinity of steep cliffs. After each epoch, the best parameters, which lead to the minimum loss, will replace
the old parameters. Early stopping mechanism is used once the lowest loss is less than the specified criteria βloss .
The feature is encoded as following. As shown in the figure 3 (a), for a history h and player P (h), we use vectors to
represent the observed actions including chance player. For example, on Leduc Hold’em, the input feature xl for l-th cellis the concatenation of three one-hot features including the given private cards, the revealed public cards and current action
a. Both the private cards and public cards are encoded by one-hot technique (Harris & Harris), where the value in the existing
position is 1 and the others are 0. If there are no public cards, the respective position will be filled with 0. The betting chips
in the encoded vector will be represented by the normalized cumulative spent, which is the cumulative chips dividing the stacksize. For HUNL, The actions used to build subgames include Fold(F ), Call(C), 0.5 Pot Raise ( 12 P ), 1 Pot Raise(P ), 2 Pot
Raise(2P ), and All-in(A). Each card is encoded by a vector with length 17: 13 for ranking embedding and 4 for suit embedding.
Actions F , C and A is represented by one-hot and the raise action is also represented by the normalized cumulative spent.

Double Neural Counterfactual Regret Minimization

F.3. Code for Mini-Batch Robust Sampling MCCFR
Algorithm 4: Mini-Batch RS-MCCFR with Double Neural Networks
Function Mini-Batch-MCCFR-NN(t):MtR ← ∅, MtS ← ∅3
For all i = 1 to b do in parallel then
4
MCCFR-NN(t,∅,0,1,1)
5
MCCFR-NN(t,∅,1,1,1)
1
2

6

return MtR ,MtS

7

rs(k)

Function MCCFR-NN(t, h, i, πi , πi
9Ii ← Ii (h) if h ∈ Z theni (h)10return urs(k)
8

):

πi

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

else if P (h) = −1 thena ∼ σ−i (Ii )rs(k)return MCCFR-NN(t,ha,i,πi ,πi)else if P (h) = i then→−tR̂i (·|Ii ) ← R(·,Ii |θR) if t > 1 else 0
σi (Ii ) ←CalculateStrategy(R̂i (·|Ii ),Ii )vi (h) ← 0,ri (·|Ii ) ← ~0,si (·|Ii ) ← ~0rs(k)Ars(k) (Ii ) ← sampling k different actions according to σi
For a ∈ Ars(k) (Ii ) dors(k)vi (a|h) ←MCCFR-NN(t,ha,i,πi σi (a|Ii ),πirs σi(a|Ii ))vi (h) ← vi (h)+vi (a|h)σi (a|Ii )For a ∈ Ars(k) (Ii ) dori (a|Ii ) ← vi (a|h)−vi (h)si (a|Ii ) ← πiσ (Ii )σi (a|Ii )Store updated cumulative regret tuple (Ii ,ri (·|Ii )) in MtRStore updated current strategy dictionary (Ii ,si (·|Ii )) in MtS
return vi (h)
else
→
−
t
R̂−i (·|Ii ) ← R(·,Ii |θR) if t > 1 else 0
σ−i (Ii ) ←CalculateStrategy(R̂−i (·|Ii ),Ii )a ∼ σ−i (Ii )rs(k)return MCCFR-NN(t,ha,i,πi ,πi)Function CalculateStrategy(Ri (·|Ii ),Ii ):P
sum ← a∈A(Ii ) max(Ri (a|Ii ),0)35
For a ∈ A(Ii ) do
1i (a|Ii ),0)36
σi (a|Ii ) = max(Rsum
if sum > 0 else |A(I
i )|
33
34

37

return σi (Ii )Algorithm 4 presents one application scenario of the proposed mini-batch robust sampling method. The function MCCFR-NN
will traverse the game tree like tabular MCCFR, which starts from the root h = ∅. Define Ii as the infoset of h. Suppose that
player i will sample k actions according to the robust sampling. Algorithm 4 is defined as follows.
• If the history is terminal, the function returns the weighted utility.
• If the history is the chance player, one action a ∈ A(Ii ) will be sampled according to the strategy σ−i (Ii ). Then this action
will be added to the history, i.e., h ← ha.

Double Neural Counterfactual Regret Minimization• If P (Ii ) = i, the current strategy can be updated by the cumulative regret predicted by RSN. Then we sample k actionsrs(k)according the specified sampled strategy profile σi. After a recursive updating, we can obtain the counterfactual value
and regret of each action at Ii . For the observed nodes, their counterfactual regrets and numerators of the corresponding
average strategy will be stored in MtR and MtS respectively.
• If P (Ii ) is the opponent, only one action will be sampled according the strategy σ−i (Ii ).
The function Mini-Batch-MCCFR-NN presents a mini-batch sampling method, where b blocks will be sampled in parallel.
This mini-batch method can help the MCCFR to achieve an unbiased estimation of CFV. The parallel implementation makes
this method efficient in practice.
F.4. Hyperparameters
In experiments, we set the network hyperparameters as following.
Hyperparameters on Leduc Hold’em. The Leduc(5), Leduc(10) and Leduc(15) in our experiments have 1.1×104 infosets(6×104 states), 3×105 (1.5×106 states) and 3×106 (2×107 states) infosets respectively. We set k = 3 as the default parameterin the provable robust sampling method on all such games. For the small Leduc(5), we select b = 100 as the default parameterin the mini-batch MCCFR ??, which only samples 5.59% infosets in each iteration. For the larger Leduc(10) and Leduc(15),
we select default b = 500, which visit (observe) only 2.39% and 0.53% infosets in each iteration. To train RSN and ASN, we
set the default embedding size for both neural networks as 16, 32, and 64 for Leduc(5), Leduc(10), and Leduc(15) respectively.
There are 256 samples will be used to update the gradients of parameters by mini-batch stochastic gradient descent technique.
We select Adam (Kingma & Ba, 2014) as the default optimizer and LSTM with attention as the default neural architecture in all
the experiments. The neural networks only have 2608, 7424, and 23360 parameters respectively, which are much less than thenumber of infosets. The default learning rate of Adam is βlr = 0.001. A scheduler, who will reduce the learning rate based on
the number of epochs and the convergence rate of loss, help the neural agent to obtain a high accuracy. The learning rate will be
reduced by 0.5 when loss has stopped improving after 10 epochs. The lower bound on the learning rate of all parameters in thisscheduler is 10−6 . To avoid the algorithm converging to potential local minima or saddle points, we will reset the learning rate toT
0.001 and help the optimizer to obtain a better performance. θbestis the best parameters to achieve the lowest loss after T epochs.
If average loss for epoch t is less than the specified criteria βloss =10−4 for RSN (set this parameter as 10−5 for RSN), we
will early stop the optimizer. We set βepoch = 2000 and update the optimizer 2000 maximum epochs. For ASN, we set the lossof early stopping criteria as 10−5 . The learning rate will be reduced by 0.7 when loss has stopped improving after 15 epochs.
For NFSP in our experiment, we set the hyperparameters according to its original paper (Heinrich & Silver, 2016). The
neural network in NFSP had 1 hidden layer of 64 neurons and rectified linear activation. The reinforcement and supervised
learning rates were set to 0.1 and 0.005. Both neural networks were optimized by vanilla stochastic gradient descent forevery 128 steps in the game. The mini-batch sizes for both neural networks were 128. The sizes of memories were 200k
and 2m for reinforcement learning and supervised learning respectively. we set the anticipatory parameter in NFSP to 0.1.
The exploration in -greedy policies started at 0.06 and decayed to 0.
Hyperparameters on HUNL. The river and turn subgame instances of HUNL in our experiments are generated by DeepStack.
The betting sizes of the root node are 100 for all such games. The reach probability and boards are randomly generated by
DeepStack. To evaluate the largest subgames based on such settings, we select the subgames whose starting pot sizes are
100 as our data sets. Note that, 100 is the smallest pot size for turn and river subgame instances. The three river subgame
instances contain 105 infosets and 108 states. To compare the generalization of DNCFR under different observed (sampling)ratios, set k = 1, we sample 0.5%, 1% and 10% infosets in each iteration. The turn subgame instance contains more than
3×107 infosets and 4×1010 states. DNCFR observes only 10% infosets in each iteration. The embedding size for river andturn subgames are 256 and 1024 respectively. Other hyperparameters in neural networks and optimizers for such subgames
are set to be the same with Leduc(15).

Double Neural Counterfactual Regret Minimization

G. DeepStack, Double Neural CFR and HUNL
Preflop Loss of Auxiliary Network
Training Sample
Validation Sample

0.0012

Flop Loss of Deep Counterfactual Network
Training Sample
0.08
Validation Sample

0.0010Turn Loss of Deep Counterfactual Network
Training Sample
Validation Sample
0.08
0.09

0.07

0.00060.0004

Huber Loss

Huber Loss

Huber Loss

0.07

0.06

0.0008

0.05
0.04

0.03

0.02

0.02

0.01

0

20

40

60

Iteration

80

100

120

(a) Preflop loss of CFV Network

0.05
0.04

0.03

0.0002

0.06

0

100

200

300

Iteration

400

500

(b) Flop loss of CFV Network

0

200

400

600

Iteration

800

1000

1200

(c) Turn loss of CFV Network

Figure 8: Huber loss of three counterfactual value network in our implemented DeepStack. (a) Huber loss of auxiliary
network on preflop subgame, the training loss is 0.0000789 and the validation loss is 0.0000776 while they are 0.000053 and
0.000055 in original DeepStack. (b) Huber loss of deep counterfactual value network on flop subgame, the training sample
is 0.008 and the validation sample is 0.019 while they are 0.008 and 0.034 in original DeepStack. (c) Huber loss of deepcounterfactual value network on turn subgame (contains last two rounds of HUNL), the training sample is 0.016 and thevalidation sample is 0.035 while they are 0.016 and 0.026 in original DeepStack. Specifically, the learning rate is decayed in200th iteration(iteration is equal to epoch here), therefore the huber loss in (b) and (c) decreased. To balance the performanceof both training and validation samples, we finally select the checkpoints that have the lowest validation loss.
The game size of imperfect information HUNL is compared with Go (Silver et al., 2016) and her partial observable property
makes it very difficult. The article (Burch, 2017) gives a detailed analysis of this problem from the perspective of bothcomputational time and space complexity. To evaluate the proposed method, we reimplement DeepStack (Moravcik et al.,2017), which is an expert-level artificial intelligence in Heads-up No-Limit Texas Hold’em. DeepStack defeated professional
poker players. The decision points of Heads-up No-Limit Texas Hold’em exceed 10161 (Johanson, 2013). We provide thegame rules of Texas holdem in Appendix A.3.
In this section, we provided some details about our implementation, compared our agent with the original DeepStack toguarantee the correctness of the implementation, and applied our double neural method on the subgame of DeepStack.
G.1. Details about Our Implementation of DeepStack
Because Alberta university didn’t release the source code of DeepStack for No-Limit Texas Hold’em, we implemented thisalgorithm according to the original article (Moravcik et al., 2017). It should be noted that the released example code 1 on
Leduc Hold’em cannot directly be used on Heads-up No-Limit Texas Hold’em for at least three reasons: (1) The tony game
Leduc Hold’em only has 2 rounds, 6 cards with default stack size 5, which is running on a single desktop, while HUNL has
four rounds, 52 cards and stack size 20000 according to ACPC game rules. (2) Specifically, there are 55,627,620,048,000
possible public and private card combinations for two players on HUNL (Johanson, 2013) and the whole game contains
about 10161 infosets, which makes the program should be implemented and run on a large-scale distributed computing cluster.
(3) The example code doesn’t contain the necessary acceleration techniques and parallel algorithm for Texas Hold’em.
Our implementation follows the key ideas presented in the original DeepStack article by using the same hyperparameters andtraining samples. To optimize the counterfactual value network on turn subgame (this subgame looks ahead two rounds andcontains both turn and river), we generate nine million samples. Because each sample is generated by traversing 1000 iterations
using CFR+ algorithm based on a random reach probability, these huge samples are computation-expensive and cost 1500 nodes
cluster (each node contains 32 CPU cores and 60GB memory) more than 60 days. To optimize the counterfactual value networkon flop subgame (this subgame only looks ahead one round), we generate two million samples, which costs about one week byusing the similar computation resource. The auxiliary network on preflop subgame is optimized based on ten million samples
1

https://github.com/lifrordi/DeepStack-LeducDouble Neural Counterfactual Regret Minimizationand costs 2 days. The whole implementation of DeepStack costs us several months and hundreds of thousands of lines of codes.
G.2. Verify the Correctness of Our Implementation
The overall DeepStack algorithm contains three ingredients: (1) computing strategy for the current public state, (2)depth-limited Lookahead to the end of subgame rather than the end of the full game and using counterfactual value network
to inference the value of the leaf node in the subgame, (3) using action abstraction technique to reduce the size of game tree.
To evaluate the strategy of imperfect information game, exploitability is usually used as the metric to evaluate the distance
between the strategy and Nash equilibrium in two-player zero-sum game. However, in the large game, such as Heads-Up
No-Limit Texas Holdem, computation of exploitability is expensive because of its 10161 searching space.
We verified the correctness of our implementation from three different aspects: First, the logs of DeepStack against
professional poker players are released on the official website, which contains more than 40000 hand histories. From theselogs, we counted the frequency of each action taken by DeepStack under different private cards and used the normalized
frequency as the estimated strategy of DeepStack. We compared this estimated strategy with our reimplemented DeepStack.
Figure 9 in Appendix G provided the comparison results and demonstrated that our implementation leads to policies very
close to what the original DeepStack does. Second, we compared the huber loss of three deep counterfactual value networks.
Clearly, our implementation achieved a loss similar to the original paper. Third, our agent also played against an enhanced
version of HITSZ LMW 2pn, whose previous version won the third prize of the 2018 Annual Computer Poker Competition(ACPC). Our implementation can win HITSZ LMW 2pn 120 mbb/g.

Double Neural Counterfactual Regret Minimization

A K Q

J

T 9 8 7 6 5 4 3 2

J Q K A

Alberta DeepStack Take Call Probability

1.0

2 3 4 5 6 7 8 9 T

0.8
0.6
0.4
0.2

A K Q

J

T 9 8 7 6 5 4 3 2

J Q K A

Alberta DeepStack Take Half Pot Raise Probability

0.0
1.0

2 3 4 5 6 7 8 9 T

0.8
0.6
0.4
0.2

A K Q

J

T 9 8 7 6 5 4 3 2

J Q K A

Alberta DeepStack Take One Pot Raise Probability

0.0
1.0

2 3 4 5 6 7 8 9 T

0.8
0.6
0.4
0.2

A K Q

J

T 9 8 7 6 5 4 3 2

0.0

J Q K A
2 3 4 5 6 7 8 9 T

0.0

0.2

A K Q

J

T 9 8 7 6 5 4 3 2

Our Agent Take Call Probability
J Q K A

0.2

0.4

0.0
1.0
0.8

2 3 4 5 6 7 8 9 T

0.4

0.6

0.6
0.4
0.2

A K Q

J

T 9 8 7 6 5 4 3 2

0.0

Our Agent Take Half Pot Raise Probability
J Q K A

0.6

1.0
0.8

0.5
0.4

2 3 4 5 6 7 8 9 T

2 3 4 5 6 7 8 9 T

0.8

Our Agent Take Fold Probability

0.3
0.2
0.1
A K Q

J

T 9 8 7 6 5 4 3 2

Our Agent Take One Pot Raise Probability
J Q K A

1.0

0.0
1.0
0.8

2 3 4 5 6 7 8 9 T

J Q K A

Alberta DeepStack Take Fold Probability

0.6
0.4
0.2

A K Q

J

T 9 8 7 6 5 4 3 2

0.0

Figure 9: Comparison of action probability between Alberta’s DeepStack (Moravcik et al., 2017) (the left column) and ourreimplemented DeepStack (the right column).