Double Neural Counterfactual Regret Minimization
Authors: Hui Li
Kailiang Hu
Shaohua Zhang
Yuan Qi
Le Song
Venue:  (2020)
Keywords: Counterfactual Regret Minimization
Imperfect Information game
Neural Strategy
Deep Learning
Robust Sampling

Abstract: Counterfactual regret minimization (CFR) is a fundamental and effective technique for solving Imperfect Information Games (IIG). However, the original CFR algorithm only works for discrete states and action spaces, and the resulting strategy is maintained as a tabular representation. Such tabular representation limits the method from being directly applied to large games. In this paper, 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 and carry out end-to-end optimization. To make the learning 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 significantly outperform those based on deep reinforcement learning.  On extremely large games with billions of decision nodes, our approach achieved strong performance while using hundreds of times less memory than the tabular CFR. On head-to-head matches of hands-up no-limit texas hold'em, our neural agent beat the strong agent ABS-CFR by $9.8\pm4.1$ chips per game. It's a successful application of neural CFR in large games.


Published as a conference paper at ICLR 2020
DOUBLE NEURAL COUNTERFACTUAL REGRET MINIMIZATION
Hui Li Kailiang Hu², Shaohua Zhang Yuan Qi Le Song
Ant Financial Services Group Georgia Institute of Technology (ken, 1h, 13251,,1, yachua. zsh, yuan. qi, le seng) Bantfinn com 1song8oc, gatecc..cgttch.ee.
ABSTRACT
Counterfactual regret minimization (CFR) is a fundamental and effective technique for solving Imperfect Information Games (IIG). However, the original CFR algorithm only works for discrete states and action spaces, and the resulting strategy is maintained as a tabular representation. Such tabular representation limits the method from being directly applied to large games. In this paper, 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 and carry out end-to-end optimization. To make the learning 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 significantly outperform those based on deep reinforcement learning. On extremely large games with billions of decision nodes, our approach achieved strong performance while using hundreds of times less memory than the tabular CFR. On head-to-head matches of hands-up no-limit texas hold' em, our neural agent beat the strong agent ABS- application neural CFR in large games.
by 9.8 chips per game. It's successful
INTRODUCTION
While significant advance has been made in addressing large perfect information games, such as Go (Silver iet al.] 22166), solving imperfect information games remains a challenging task. For Imperfect Information Games (IIG), player has only partial knowledge about her opponents before making a decision, 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, such as trading, traffic routing, and politics.
Nash equilibrium is typical solution concept for a two-player perfect-recall IIG. One of the most effective approaches is CFR (Zinkevich et al. (207]). which minimizes the overall counterfactual regret so that the av- erage strategies converge to a Nash equilibrium. However the original CFR only works for discrete states and action spaces, and the resulting strategy is maintained as tabular representation. Such tabular representa- tion 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. [007 [aacctot et al.] 2009). Constructing an effective abstraction, however, demands rich domain knowledge and its solution may be 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 handerafted features, which is called Regression CFR (RCFR). However, since RCFR uses full traversals of the game tree, it is still impractical for large games. Moraveik al. (2017) propose a seminal approach DeepStack, which uses fully connected neural networks to represent players' counterfactual values, tabular CFR however was used in the subgame solving. Jin et al.] (2017) use deep reinforcement learning solve regret minimization problem for single-agent settings, which is different from two-player perfect-recall IIGs.
'The previous versions this work were published AAAI 2019 workshop on RLG and ICML 2019 workshop on RWSDM. It takes more than one year for us to reimplement DeepStack and evaluate our method on large-scale heads-up no-limit Texas Hold' em. Correspondence to: Hui Li, lihuiknight@ wooghtt.oooo.oommmm
ABS-CFR is the advanced version of HITSZ_ LLW 2pn, who won the third prize of the 2018 Annual Computer Poker Competition (ACPC). In our experiment, we chosen its advanced version the benchmark.

---

Published as a conference paper at ICLR 2020
To learn approximate Nash equilibrium for IIGs in end-to-end manner, Heinrich al. (0113) and Heinnich & Silver (2016) propose eXtensive-fom Fictitious Play (XFP) and Neural Fictitious Self-Play (NESP), respectively, based on deep reinforcement learning. In a NFSP model, the neural 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 can improve continuously with more optimization iterations. However fictitious play empirically converges much slower than CFR-based approaches. [Srinvvaaan et al. (2018) use actor-critic policy optimization methods to minimize regret and achieve performance comparable to NFSP.
Thus it remains an open question whether a purely neural-based end-to-end approach can achieve comparable performance to tabular based CFR approach. In the paper, we solve this open question by designing a double neural counterfactual regret minimization (DNCFR) algorithm P] To make a neural representation, we modeled imperfect information game by a novel recurrent neural network with attention. Furthermore, in order to improve the convergence of the neural algorithm, we also developed new sampling technique which converged much more efficient than the outcome sampling, while being more memory efficient than the external sampling. In the experiment, we conducted a set of ablation studies related each novelty, The experiments showed DNCRF converged to comparable results produced by its tabular counterpart while performing much better than NFSP. In addition, we tested DNCFR on extremely large game, heads-up no-limit Texas Hold' em (HUNL.. The experiments showed that DNCFR with only a few number of parameters achieved strong neural strategy and beat ABS-CFR.
player
2 BACKGROUND
playee
Notation.Figure illustrates an extensive game for finite set N 10. 1} of n players. Define au as the hidden information of player i in IIG. x²= refers to hidden variables of all players other than i. H refers to a finite set of histories. h H denotes possible history (or state), which consists of each player's hidden variable and ac- tions taken by all players including chance. The empty sequence 0 is a member of H. h, C h denotes hy is a prefix of h. 7 C H denotes the terminal histories and any member E Z is not prefix of any other sequences. A(h) (a:ha H] is the set of available actions after non-terminal history h E H Z. A player function P assigns a member of NU(c] to each non-terminal history, where e is the chance ( we set c= c==1) 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) I. All states h I are indistinguishable to i. Id refers to the set of infosets of i. The utility function ux(2) defines the payoff of i at state 2. See appendix B.I for more details.
chance
hn
hs
has
Infoset
8g
X3
24
25
7
Figure 1: Extensive-Fomi IIG and Information Set
{a,o, Σ, E N} is collection of strategies for all players, where Σ; is the set of all possible strategies for player i. a-i refers to strategy of all players other than player i. For play i E N, the strategy (14) is function, which assigns an action distribution over A(I,) to
A strategy profile
Algorithm 1: CFR Algorithm
For t- 1 1o do
(I.)=
Σ
(1)
(1(()))) -f (o)))) -u) (1.).
(2)
infoset 4, (a(h) denotes the probability of action a taken by player i at state h. In IIG, h2 E 1; we have o,; = oz (h1)) ) (h2). For iterative method such as CFR, of refers to the strategy profile at 1-th iteration. The state reach probability of history h is denoted by n² (h) if players take actions according to a. The reach probability is also called range in DeepStack (Moraviik et al. 2017). Similarly, nī (h) refers to those for player while n (h) refers to those for other players except for i. For an empty sequence n (0) 1. One can also show that the reach probability of the opponent is proportional to posterior
r((4]T,)= (001))=17] RI. (a/ +rē (a]l.).
(3)
TAIT if Σ (a(1.)=
dEA())
(a(T)
n² (all.)
Σ n. (olt)) otherwise.
(EAU
(4)
('a(l))=s- (a)L)tt (Woi(a)))
(5)
S (a(a))) E.
a. a.(a)T))= "((alI)= E (alt)
(6)
Solving IIGs via function approximation methods an important and challenging problem. In the past year, several concurrent works (Lockhart et al. 2019) [rown et al. 20188] [Steinberger) 2019) have been proposed to address this problem. We will discuss their differences in Section 6
2

---

Published as a conference paper at ICLR 2020
(a)
Regret
(b)
Regret Matching
0sery
B
My refosets
somple mnfoonts
Ris
gradens
St (ell)
s(oll))
3 f sompled Infosecs
M all infosets
Stu.
gradees diacest
Tabular Method
Method
Figure 2: (a) labular CFR and (b) our double neural CFR framework. F2 Iaa (3)) is the estimated regret in MCCFR, "a I,) is the cumulative regret, sa I:) is the weighted additional strategy and S (a[I.) is the cumulative behavior strategy. In tabular CFR, cumulative regret and strategy stored in the tabular memory, which limits it to solve large games. In DNCFR, we double deep neural networks to approximate these two values. DNCFR needs Jess memory than tabular methods because of its generalization.
probability of the opponent's 's hidden variable, i.e..p(x",; 44) (h),, where xf and I, indicate particular (proof in Appendix D.I.. Finally, the infoset reach probability of I, is defined as x (4, = =Lez, x (h). Similarly, we have T. (1)) = Enel, m3 (h) and (T,) = - (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 [ and Figure 2aa). Given strategy profile a, the counterfactual value (CFV) of (74) at infoset I is defined by Eq. The action CFV of taking action is og (a/4) and its regret defined by Eq. (2) Then the cumulative regret of action a after T iterations is Eq. Bp. where R (a)Li) = O. Define (a/Lt)
(
the current strategy
(or behavior strategy) at t ++1 iteration will be updated by Eq. (4). Define (a() = o." (I))a (a)Za) as the additional strategy in iteration 6, then the cumulative strategy can be defined Eq. (5), where (a)]/) 00. The average strategy o," after iterations is defined by Eq. (6). which approaches a Nash equilibrium after enough iterations.
Monte Carlo Lantttt et al. 2009) proposed Monte Carlo CFR (MCCFR) to compute the unbiased estimation of counterfactual value by sampling subsets of infosets in each iteration. Although MCCFR still needs 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 for those visited nodes into working memory; Define Q= Q 10.1QQ...,,... }. where Qj E Z is a set (block) of sampled terminal histories in each iteration, such that 2, spans the set Z. Define ςQ; as the probability of considering block Qj. where Σ}=1 =1. 1. Define o(=)=EE 92, as the probability of considering particular terminal history For infoset I;, an estimate of sampled counterfactual value is ig (I; Q2) LheE,,EE,, g(a) T- (=)m² (h)
Lanctot et al. 2 The sampled counterfactual value in MCCFR is the unbiased estimation of actual counterfactual value in CFR. Ej~go, (1|2,) =f
Lemma 1
Define 6º* as sampled strategy profile, where o: is the sampled strategy of player i and /² are those for other players except for i. The regret of the sampled action a E A(I.) defined by 1 ((a [,) = Eseeq,haCx.eet Ti (ha,
EzEQ, x. (h,z)u?((=), where uz²(z) "?" (z) is new utility weighted by [xj The sampled estimation for cumulative regret of action after t iterations is (((( = in. ((1))));)++7 ((7())))) where (aa(44)))
m=(=)
3
DOUBLE NEURAL COUNTERFACTUAL REGRET MINIMIZATION
Double neural CFR algorithm will employ two neural networks, one for the cumulative regret R. and the other for the average strategy S shown in Figure bb)
3.1
MODELING
The iterative updates of CFR algorithm maintain the regret sum Ht' (a)4i) and the average strategy of (a 4.). Thus, our two neural networks are designed accordingly.
according to Eq. ( the current strategy -f (al [4) is computed from the cumulative regret R (a) L)) We only need to track the numerator in Eq. (4) since the normalization in the denominator can be computed easily when the strategy is used. Given infoset I, and action a, we design a neural network R Ra to track RC (a) Tc). where 0% are the network parameters.
RegretSumNetwourkRRSSM
3

---

Published as a conference paper at ICLR 2020
Mini batch Robust Sampling
ASN
RSN [e Co come
Sequential Representation
Attention Network
player
player A chance
of11
c6
M 3 8880
Mr
8800
RSN
(a) recurrett neural network architecture with attention for extensive games. Both RSN and ASN are based on this architecture but with different parameters (frz and 6s 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).
Figure 3:
according to Eq. (6). the approximate Nash equilibrium is the weighted average of all previous behavior strategies up to iterations, which computed by the normalization of cumulative strategy S* (a) Similar to the cumulative regret, employ the other deep neural network S(al0's) with network parameter f'' to track the cumulative strategy.
Newttrkk
3.2 RECURRENT NECRAL NETWORK REPRESENTATION WITH ATTENTION
In order define our and S networks, we need to represent the infoset in extensive-fome games. In such games, players take actions in an alternating fashion and each player makes a decision according to the observed history. Because the action sequences vary length, we model them with recurrent neural networks and each action in the sequence corresponds to cell in the RNN. This architecture is different 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 (Cho et al. (014) 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 add an attention mechanism (Desimone & Duncan 1995 Cho et al. 2015) to the RNN architecture 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 that the attention mechanism can help DNCFR obtain a better convergence rate. See Appendix
[ for more details on the architectures.
3.3
OPTIMIZATION METHOD
The parameters the neural networks are optimized via stochastic gradient descent in stage-wise fashion interleaving with CFR iterations.
3.3.1 OPTIMIZING CURRENT STRATEGY
) for all sampled 4 to store the sampled I; and the corresponding regret Pp ((a]4))Q2)) for all players in (-th iteration, where Q, is the sampled block (shown in 2 These samples are produced by our proposed robust sampling and mini-batch MCCFR methods, which will be discussed in Section [ According to Eq. (3) optimize the cumulative regret neural network Ia (8x-1) using the following loss function
We use MRR = =[(1o77 ((44))
(((108)) +i9 (((10))((11772)))
if in M'
((R)= Σ
R(-10²) +0- 2
EEN. I.T. of A(T.)
otherwise,
where (o) refers R.-10%)) Pp' ((a)T)))()) refers to p2' (-12;), O refers to the old parameters and 02-1 is the new parameters of all the players rather than a particular player i. In standard MCCFR, if the infoset is not sampled, the
need to optimize. Note that, Eq. 7 is minimized based on the samples
corresponding regret is set to O, which leads to unbiased estimation according to Lemma [ The design of the loss function in Eq. (7) follows the same intuition. Techniques in Schmid et al. (2018) can be used to reduce the variance.
4

---

Published as a conference paper at ICLR 2020
Sampling unobserved infosets? Theoretically, in order 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 of memory and computation. Clearly, this is intractable on large games, such as HUNI. In practice, we find that minimizing loss only based on the observed samples can help us achieve converged strategy.
Learning without forgetting? Another concem is that, only a small proportion of infosets are sampled due to mini-batch training, which may result in the neural networks forgetting values for those unobserved infosets. To address this challenge, we will use the neural network parameters from the previous iteration as the initialization, which gives us an online learning/adaptatiinn 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 Nash equilibrium. See Appendix for more details on implementation.
Burch (017)) ) the cumulative regret (a)])l indicates that (a)i will become increasingly large. In practice, we scale the cumulative regret by can update the cumulative regret Eq. (3) by ([(aa))))((---e))))) -V- (aa (alT:))/ VL. where (a)
Scaling regret for stable training? According to Theorem (a)T,)) S A VAATT where |A| = maxi,ez [A(Ta)l and A = m,.,, |R (a)T,)
factor of vē to make its range more stable. For example, define R[(a [4)= R (a)
3.3.2 OPTIMIZING AVERAGE STRATEGY
(for all sampled 4} will store the sampled 4; and the weighted The other memory M's [(
additional behavior strategy s (a)44) in t-th iteration. Similarly, the loss function L(S) of ASN is defined by:
S
If in M's
((S)= Σ EEN, LET, AEA(T)
(8)
S( 5(18))+0-
otherwise.
where S(-10') refers to (103)) O'' refers the old parameters and 05+11 is the new parameters need to optimize. According to A Algorithm [ 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 M's in each iteration, we can achieve the final average strategy directly. Based on this concept, we don't need optimize the average strategy network (ASN) S(- in each iteration. However, saving all such values into huge memory is very expensive on large games. A compromise is that we can save such values within multiple iterations into a memory, when this memory large enough, the incremental value within multiple iterations can be learned by optimizing Eq.
Minimum squared loss versus maximum likelihood? The average strategy 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 is very memory eeemory-expessive. To address this limitation, we can use uniform reservoir sampling method (Osbome et al. 2014) to obtain the unbiased estimation of each strategy. In practice, we find this maximum likelihood method has high variance and cannot approach a less exploitable Nash equilibrium. Experimentally, optimization by minimizing squared loss helps us obtain fast convergent average strategy profile and uses much less memory than maximum likelihood method.
3.4 CONTINUAL IMPROVEMENT
When solving large IIGs, prior methods such as Libratus (Brown & Sandholm, 2017) and Deep- Stack (Moravcik et al. 2017) are based the abstracted HUNL which has a manageable 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 not raise and all in). DNCFR is not limited by the specified abstracted cards or actions. For example, we can use the continuous variable represent bet money rather than encode by discrete action. In practice, DNCFR can clone an existing tabular representation or neural representation and then continually improve the strategy from the initialized point. More specifically, for infoset 4; and action a, define R² (a(4.) as the cumulative regret. We can use behavior cloning technique to learn the cumulative regret by optimizing 0% argmingg Er,E, (R(- R' (-11a)² 2 Similarly, the cumulative strategy can be cloned in the
5

---

Published as a conference paper at ICLR 2020
same way. Based on the learned parameters, we warm start DNCFR and continually improve beyond the tabular strategy profile.
Algorithm 2: DNCFR Algorithm
3.5 OVERALL ALGORITHM
Function Agent (T, b)
Algorithm 2 provides summary of the proposed
For t- 1-11 to I do
double neural counterfactual regret minimization approach. the first iteration, if the system warm starts from tabular-basee methods, the techniques Section 3.4 will be used to clone the cumulative regrets and strategies. If there is no warm start ini- tialization, 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 saved in memories Mix and M's respectively. These samples will be used by the AeunalAgent algorithm from Algorithm 3 to optimize RSN and ASN, Further details for the sampling methods will be discussed in the next section. Due space limitation, we present NeuralAgent fitting algorithm Appendix [F]
ift= 1 and using warm starting then
Initialize 0z and I''s from checkpoint
1+
else
Initialize 032 and 0's randomly.
M <- sampling methods.
Sum aggregate value in Ma by infoset.
Remove duplicated records in Ms.
0g + NeuralAgent (e 10% ppt-1) M..00 M/- (8k) O's
NeuralAgent(S( 10's Mg 0' (5)
return 0%.0'ss
4 EFFICIENT TRAINING
In this section, we will propose two techniques to improve the efficiency of the double neural method. These techniques can also be used separately in other CFR variants.
4.1 ROBUST SAMPLING TECHNIQUE
In this section, we introduce a robust sampling method (RS), which is a general version of both external sampling and outcome sampling (Lanctot et al. 2009). RS samples & actions in one player's infosets and samples one action in the another player's s inlosets. Specifically, in the robust sampling method, the sampled profile is defined by rrk(k) = (o,=((k] .)_;), where player i will randomly select k actions according to sampled strategy of (a(k) (I:) at I; and other players randomly select one action according to d-j-
We design an efficient sampling policy for robust sampling as follows and discuss the relationship among robust sampling, external sampling and outcome sampling in Appendix D.2 If k = maz (44))
ra(k) (a)[:)= 1, then robust sampling identical with external sampling. k=
and for each action o;
--((k) -a; and ((2) 28 8> 0 (5 is a small positive number), then robust sampling is identical with outcome sampling.
Specifically, if player i randomly selects min(k, [A(I)) actions according to discrete uni- form distribution (0, [A(A)) at It i.e., of (ro())
min(k:]AA(A.I)) then op ratk) (I.)
A(1.)
(k.n(k,)A( and the weighted utility u, ( will be a constant number in [A()]
T each iteration. In many settings, when k= 1, we find such robust sampling schema converges more efficient than outcome sampling. In contrast, our robust sampling achieves comparable convergence with external sampling but using less working memory when specifying a suitable k. It's reasonable because our schema only samples & rather than all actions in player i's infosets, the sampled game tree is smaller than the one by external sampling. In the experiment, we will compare these sampling policies in our ablation studies.
4.2 MINI-BATCH TECHNIQUE
Traditional MCCFR only samples one block in an iteration and provides unbiased estimation of origin CFV. In this paper, we present a mini-batch batch Monte Carlo technique and randomly sample blocks in one iter- ation. Let Q' denote block of terminals sampled according the scheme Section 4.1 then mini-batch CFV with mini-batch size b will be og (T,(6) = E (z) (b)2))
Theorem 1 EqU Equiminn--backk (og (Л]bb] of (I.)-
We prove that @g (T.]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 matching plus (Tammelin] (0014), we obtain a mini-batch MCCFR+ algorithm. Our mini-batch technique empirically can sample blocks in parallel and converges faster than original MCCFR when performing on multi-core machines.

---

Published as a conference paper at ICLR 2020
10
10
Expratabiity
Pegrolabitty
Explotabbity
Explattabiity
outtome samoling
excernal sampligg
DNCFR 5- 05%)
recust 23mplng
Attention
10
DNCFRC1016
DNCFR22026
10
DNCTRB-10055 59%)
D 500013
sampligtio==)
Fully Connected
Tabular NCCFR-11063
MCCFR
10 10 30 10 18t 1o 10' 10
12
10
20
10
10
10
10
10
10
Numberd Mode:
Iteracioo
(a) Sampling methods
(h) Neural architectures
(c) Number of parameters (d) Sampling proportion
Figure 4: Log-log performance on Leduc(5). (a) different sampling methods, & refers to the number of sampling
action for the proposed robust sampling method in each infoset. (b) neural architectures. (c) number of parameters. (d)
proportion of observed infosets. Higher proportion indicates more working memory.
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 method such as NFSP, which is prior leading function approximation method in IIGs. At last, we conduct experiments on heads-up no-limit Texas Hold' em (HUNL) to show the scalability of DNCFR algorithm. The games and key information used in our experiment are listed in Table
Table Summary. #infoset the number of infosets. #state is the number of states. %observed is the ratio of observed infosets in cach iteration. #emd and #param are the embodding size and the number of parameters in DNCFR.
setting
#infoset
#state
%abserved
#emd
#param
action abstraction card abstraction
Leduc(5)
1 1x10"
6 6x10'
5.59%
16
2608
No
No
Leduc(10)
3x 3x
2x10
2.39%
32
7424
No
No
(5)
3x
2x107
0.53%
64
23360
No
No.
HUNL(I)
2x10
3x 10
0.01%
64
19200
Yes
No
HUNL(2)
8x 10
1 "4
0.001%
512
1070592
Yes
No
ABS-CFR
1x
1x
Yes
Yes
HUNL(full)
1x 1x10
1x 10
Yes
No
5.1 SETTINGS AND METRIC
We perform the ablation studies on Leduc Hold'em poker, which is a commonly used poker game in research community (Heinrich & Silver 2016 Schmid al., 2018 Stteineerger 2019 Lockhart et al. 2019). In our experiments, we test DNCFR on three Ledue Hold' em instances with stack size 5, 10, and 15, which are denoted by Leduc(5), Leduc(10), and Leduc(15) respectively.
To test DNCFR's scalability, we develop a neural agent to solve HUNL, which contains about 10 infosets (Johanson 2013) and has served for decades as challenging benchmark and milestones of solving IIGs. The rules for such games are given in Appendix A
The experiments are evaluated by exploitability, which was used a standard win rate measure many key articles (Zinkevich et al., 2007 Lanctot et al. 2009; Michael Bowling 2015 Brown et al. 2018 The units of exploitability in our paper is chips per game. It denotes how many chips one player wins on average per band of poker. The method with lower exploitability is better. The exploitability of Nash equilibrium zero. extremely large game, which is intractable to compute exploitability, we use head-to-head performance measure different agents.
Algorithm 3 Algorithm 4 Appendix F.4 provides the parameters used in experiments. Solving HUNL is
For reproducibility, we present the implementation details of the neural agent in Algorithm? 2
challenging task. Although there are published papers (Moravcik et al. 2017 Brown & Sandholm 2017). it lacks of available open source codes for such solvers. TThe development of HUNL solver not only needs tedious work, but also is difficult to verify the correctness of the implementation, because of its well known high variance and extremely large game size. In Appendix G the correctness of our implementation for HUNL.
we provide several approaches validate
5.2 ABLATION STUDIES
We first conduct set of ablation studies related the mini-batch training, robust sampling, the choice of neural architecture on Ledue Hold'em.
Is mini-batch sampling helpful? present the convergence curves of the proposed robust sampling method with l = max))[A(II)) under different mini-batch sizes in Figure S(a) at Appendix C The experimental results show that larger batch sizes generally lead to better strategy profiles.
7

---

Published as a conference paper at ICLR 2020
10
UP
100
16
peeotouul 2
Explotegiiltg
Exporatiny
50
10
M5-MCOFR
RS MS-MCFFR-RSS -SSK
NFSP
stacke5 stack115
MCGFF++-SSSS
CHR WCCER.
XFP
MCOFR+
16
DNCER
T0P
10
10" 10
10
10
Dirration
Nodes
(a) Individual network
Warm starting
(c) DNCFR vs NESP
(d) Large Leduc Hold' em
Figure 5: Log-log performance. (a) Individual effect of RSN and ASN, RS-MOCFR+ refers to tabular mini-batch MCCFR+ method with the proposed rohust sampling. RS-MCCFR+-RST only uses one neural network RSN to learn cumulative regret while uses a table to save cumulative strategy. RS-MCCER+-ASN only use one neural network ASN. CRN-CCCRR-SSS-ASS refers to DNCFR with both RSN and ASN. (h) Warm start from tabular CFR and RS-MCCER+. (c) DNCFR XFP NFSP. (d) Large Leduc(10) (10) and Leduc(15).
Is robust sampling helpful? Figure 1 (a) presents convergence curves for outcome sampling, external sampling(k: = max (44))) 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 number of iterations. With an increasing k the robust sampling method achieves an even better convergence rate. Experiment results show k ==3 3 and 5 have a similar trend with k max([AA(4)))., which demonstrates that the proposed robust sampling achieves similar performance but requires less memory than the external sampling. We choose 3 for the later experiments in Leduc Hold' em.
Is attention in the neural architecture helpful? Figure 4b) shows that all the neural architectures achieved similar results while LSTM with attention achieved slightly better performance with 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 their tabular 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 them are much less than the tabular memory (more than 1 11083 here) and can lead converging strategy profile as shown Figure 4fc.. We select embedding size 16 as the default parameters. In the later experiments, we will show the similar conclusion on HUNL.
Do the neural networks generalize to unseen infosets? To investigate the generalization ability, we perform the DNCFR with small mini- mini-batch sizes (b=50, 100, 500), where only 3.08%, 5.59%, and 13.06% infosets 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 (dd). In the later experiments,
b=100 as the default mini-batch size. We leam new parameters based the old parameters and subset of observed samples. All infosets share the same parameters, so that the neural network can estimate the values for unseen infosets. Note that, the number of parameters orders of magnitude less than the number of infosets in many settings, which indicates the generalization of our method. Furthermore, Figure 4d) shows that DNCFRs are slightly better than tabular MCCFR, we think it's because of the generalization to unseen infosets.
What is the individual effect RSN and ASN? Figure 31a) presents ablation study of the effects of RSN and ASN network respectively. Specifically, the method RSN denotes that we only employ RSN to Ieam the cumulative regret while the cumulative strategy is stored in a tabular memory. Similarly, the method ASN only employ ASN to leamn 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 leamned by tabular based CFR and RS-MCCFR+, After the behavior cloning in Section 3.4 the remaining iterations are continually improved by DNCFR.
How well does DNCFR on larger games? We test DNCFR on large Leduc(10) and Leduc(15). which contains millions of infosets. Even though only small proportion of nodes are sampled in each iteration, Figure ()d) shows that DNCFR can still converge on these large games.
5.3
COMPARISON AND SPACE- TIME TRADE-OFF
How does DNCFR compare to the tabular counterpart, XFP, and NFSP? NFSP is the prior leading function approximation method for solving IIG, which is based on reinforcement learning and fictitious self-play techniques. In the experiment, NESP requires memories to store 2 10 state-action pair
8

---

Published as a conference paper at ICLR 2020
samples and 2 10th samples for supervised learning respectively. The memory sizes are larger than the number of infosets. Figure (5c) demonstrates that NESP obtains a 0,06-Nash equilibrium after touching 10" infosets. The XFP obtains the same exploitability when touching about 10" nodes. However, this method is the precursor of NESP and updated by a tabular based full-width fictitious play. Our DNCFR achieves the same performance by touching more than 10 nodes, which are much fewer than both NFSP and XFP. The experiment shows that DNCFR converges significantly better than the reinforcement learning counterpart.
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. We compare their runtime and memory in Figure [6] It's clear that the number of infosets is much more than the number of pa- rameters used in DNCFR. For example, on (15) tabular CFR needs 128 times more memory than DNCFR. In the figure, we use the ratio between the runtime of DNCFR and CFR as horizontal axis, and the sampling(ohserve)) infosets ratios of DNCFR and full-width tabular CFR as vertical axis. Note that, the larger the sampling ratio, the more memory will be needed to save the sampled values.
Clearly, there is a trade-off between the relative runtime and relative memory in DNCFR: the longer the relative runtime, the less the relative memory needed for DNCFR. It is reasonable to expect that a useful method should lead "fair" trade between space and time. That is onefold increase in relative runtime should lead
350
Leduuc(51, emdi5, expm1.0
observed ratio (CFRIDNCRe)
300
Leducc51, emd=6, exp-0.5
Laduuc()) wmd-8, exg-0.1
250
Leducii51, emd=10, exp=0.05 0.05
200
Leducct5) cmd-12, exp-0.02 Liblyc(51, emdm16, 16, exg 005 Ledut()10), emd-32, exp-0.001
onefold decreases in relative memory (the dashed line in Figure [ slope-1) Interestingly, DNCFR achieves a much better trade-off between relative runtime and memory: for onefold increases in relative runtime, DNCFR may lead to fivefold decreases in relative memory consumption (red line, slope- -)). We believe this is due to the generalization ability of the learned neural networks in DNCFR.
150
Leduc(115) amd-64, exp-0.01
100
50
50 100 150 200 250 300 350 400 450 running time (DNCFRICFR)
Figure time space trade-off.
To present the time space trade off under a range of exploitability, we set the fixed exploitability as 1.0. 0.5, 1, 0.05, 0.01 and 0.005 and perform both neural and tabular CFR on Ledue Hold'em Figure 6 presents DNCFR achieves a much better time and space trade-off. We believe the research on neural CFR is important for future work and the running time is not the key limitation of our DNCFR. Some recent works (Schmid et al. 2018 Davis et al. 2019) provide strong variance reduction techniques for MCCFR and suggest promising direction for DNCFR. In the future, will combine DNCFR with the latest acceleration techniques and use multiple processes or distributed computation to make it more efficient.
5.4 HEADS-UP LO-LIMIT TEXAS HOLD'EN E'MM
To test the scalability of the DNCFR on extremely large game, we develop neural agent to solve HUNL. However, it's challenging task to directly solve HUNL even with abstraction technique. For example, ABS-CFR uses k-means to cluster similar cards into thousands of clusters. Although it's a rough abstraction of original HUNL, such agent contains about 2 10 infosets and needs 80GB memory to store its strategies. The working memory for training ABS-CFR is even larger (more than about 200GB), because it needs to store cumulative regrets and other essential variables, such as the abstracted mapping. To make it tractable for solving HUNL via deep learning, we assemble the ideas from both DeepStack (Moravcik al., 2017) and Libratus (Brown& & Sandholm) 2017). Firstly, we train flop and turn networks like DeepStack and use these networks to predict counterfactual value when given two players' ranges and the pot size. Specifically, the flop network estimates values after dealing the first three public cards and the tum network estimates values after dealing the fourth public card. After that, we train blueprint strategies like Libratus. In contrast, the blueprint strategies in our settings are learned by DNCFR, Because we have value networks to estimate counterfactual values, there no need for to arrive terminal nodes at the river.
To demonstrate the convergence of DNCFR, firstly, we test it on HUNL(I). Such game has no limited number of actions, contains four actions in each infoset, and ends with the terminals where the first three public cards are dealt. HUNL(I) contains more than x 10 infosets and x 10 states. It's tractable to compute its exploitability within the limited time. We believe this game is suitable to evaluate the scalability and generalization of DNCFR. Figure 77aa) provides the convergence of DNCFR on different embedding size: emd=8, 16, 32, 64, 128. The smallest neural network only contains 608 parameters while the largest one contains 71168 parameters. It's reasonable to expect that larger neural network typically achieves better performance because more parameters typically help neural networks represent more complicated patterns and structures. Figure 7bb) presents the performance of using the different number of stochastic gradient descent (SGD) updates to train neural network on each MCCFR iteration. The results show that the number of SGD updates each iteration affects the asymptotic exploitability of DNCFR. It's

---

Published as a conference paper at ICLR 2020
10
10A
Exploitabiity
Exploitabilty
20
10a
Match-up
Win(chips/h)
emd=8
ABS-CFR
9.8
end=16
Tabular Agent
0.7
emd-32
updates=200
emd-64
updates-2000
emd-128
update==10000
10
10
10
10a
10
16
Iteration
Iteration
(a) embedding size
(b) gradient descent updates
(c) head-to-head win rate.
Figure 7: Performance of DNCFR heads-up no-limit Texas Hold' em. (a) Log-log performance of DNCFR on HUNL(()) under different embedding size. (b) Log-Log performance of DNCFR on HUNL(1) under different numbers of gradient descent updates on each iteration. (c) DNCFR beats ABS-CFR by 9.8 chips per hand and achieves similar performance with its tabular version but using much less memory.
reasonable because the neural network achieves small loss the number of gradient descent updates is increasing.
Finally, we measure the head-to-head performance of our neural agent against its tabular version and ABS- CFR on HUNL. ABS-CFR is a strong HUNL agent, which is the advanced version of the third-place agent in ACPC 2018. Although ABS-CFR used both card and action abstraction techniques, it still needs 80GB memory to store its strategies. More details about ABS-CFR are provided in Appendix [.]] Although abstraction pathologies are well known in extensive games (Waugh al. 2009). typically, finer grained abstraction leads to better strategy in many settings. Following this idea, we use DNCFR to learn blueprint strategies on HUNI.(2), which is similar to HUNL((1) but contains eight actions in each infoset. HUNI.(2) contains 8 x 10 infosets. Such large game size makes it intractable to perform subgame solving (Burch) cct al., 2014) in real-time. For the next rounds, we use continual resolving techniques to compute strategy in real-time. The action size in the aak-dd tree is similar to Table S3 in Moravcik et al. (2017). The tabular agent is similar to our neural agent except for using tabular CFR to learn blueprint strategies. When variance reduction techniques (Burch et al. 2018) beats ABS-CFF by 9.1 chips per game and obtains similar performance 20.7+2.2 chips per game) with its tabular agent. In contrast, our neural only needs store 1070592 parameters, which uses much less memory than both tabular agent and ABS-CFR.
applied ! Figure Z shows that neural agent
RELATED WORKS AND DISCUSSION
Solving IIGs via function approximation methods is an important and challenging problem. Neural Fictitious Self-Play (NFSP) (Heinrich & Silver 2016) is function approximation method based deep reinforcemett learning, which is a prior leading method to solve IIG. However, fictitious play empirically converges slower than CFR-based approaches many settings. Recently, Lockhart al. (2019) propose new framework to directly optimize the final policy against worst-case opponents. However, the authors consider only small games. Regression CFR (RCFR) (Waugh al.) 2015) is a function approximation method based on CFR. However, RCFR needs to traverse the full game tree. Such traversal is intractable in large games. In addition, RCFR uses hand-crafted features and regression tree to estimate cumulative regret rather than learning features from data, Deep learning empirically performs better than regression tree in many areas, such as the Transformer and BERT in natural language models (Ashish Vaswani 2017 Jacob Devlin 2018).
In the past year, concurrent works deep CFR (DCFR) (Brown et al,, 2018) and single deep CFR (SD- CFR) (Steinberger, 2019) have been proposed to address this problem via deep learning. DCFR, SDCFR. RCFR and our DNCFR are based on the framework of counterfactual regret minimization. However, there are many differences in several important aspects, which are listed follows. (1) We represent the extensive-fome game by recurrent neural network. The proposed LSTM with attention performs better than fully connected network (see details in Section 3.2.. (2) DNCFR updates the cumulative regret only based on the additionally collected samples in current iteration rather than using the samples in big reservoir (see details in Section 3.3.T). (3) It's important use squared-loss for the average strategies rather than log loss. Because the log loss is based on the big reservoir samples up to T-th iteration, it is very memory expensive (see details in Section 3.3.2) (4) Another important aspect to make deep learning model work that we divide regret by VT and renormalize the regret, because the cumulative regret can grow unboundedly
3 It's well known that head-to-head evaluation of HUNL is challenging because of its high variance. AIVAT is the state-of of the-art technique reduce evaluation variance poker evaluation.
10

---

Published as a conference paper at ICLR 2020
(5) Also, DNCFR collects data by an efficiently unbiased mini matnhbbachhha robust sampling method, which may be of independent interests to the IIG communities (see details in Section Q
(see details in Section 3.3.1
There are also big differences in the experimental evaluations, In our method, conduct set of ablation studies various settings. We believe that our ablation studies are informative and could have significant impact these kinds of algorithms. Also, evaluate DNCHR extremely large games while RCFR and SDCFR are only evaluated on small toy games.
7
CONCLUSIONS
We proposed novel double neural counterfactual regret minimization approach solve large IIGs by combining many novel techniques, such as recurrent neural representation, attention, robust sampling, and mini-bate MCCFR. We conduct set of ablation studies and the results show that these techniques may be of independent interests. This is successful application of applying deep learning into large IIG, We believe DNCFR and other related neural methods open up a promising direction for future work.
ACKNOWLEDGMENTS
We would like to thank Mare Lanetot, Neil Burch, Noam Brown, Tuomas Sandholm, Richard Gibson, Matej Moravcik. Martin Schmid, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson and Michael Bowling for their helps in the work developing large-scale heads-up no-limit Texas Hold' em. We appreciate the help of Zhibang Ge and Tao Jiang for their early exploration on this difficult project. We thank Lin Wang, Jun Zhou, Yongchao Liu, Yewei Huang, Junping Zhao, Jun Jiang, Jincan Kong. Shaohua Du, Yao Zhang and Changhua He for supporting computation resource. We thank Chuanxiao Zhou, Shuai Xiao, Xiang Li and Yaxi Zhu et.al. for their suggestions and professional testing. At last, would like to thank the anonymous reviewers for their valuable feedback.

---

Published as a conference paper at ICLR 2020
REFERENCES
Ashish Vaswani, Noam Shazeer, U.J.U.L.......... Attention is all you need. arXiv preprint arXiv:1706.03748 2017.
Brown, and Sandholm, Superhuman heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaao1733, 2017.
Brown, N., Leter, A., Gross, S., and Sandholm, T. Deep counterfactual regret minimization. arXiv preprint arXiv:1111.01144 2018.
Burch, N. Time and Space: Why Imperfect Information Games are Hard. PhD thesis, 2017.
Burch, N., Johanson, M., and Bowling, M. Solving imperfect information games using decomposition. In Twenty-Fightl AAAI Conference on Artificial Intelligence, 2014.
Burch, N., Schmid, M., Moravcik, M., Morill, D., and Bowling, M. Aivat: A new variance reduction technique for agent evaluation in imperfect information games. In AAAI, 2018.
Cho, K., Van Merrienboer, B., Gulcehre, C., Bahdanau, D., Bougares, F,, Schwenk, H., and Bengio, Learning phrase representations using RNN encoder-decoder for statistical machine translation. arXiv preprint 440i 1078, 2014.
Cho, K., Courville, A., and Bengio, Y. Describing Multimedia Content using Attention-based En- coder-Decoder Networks. arXiv preprint 150.0005, 2015.
Davis, T., Schmid, M., and Bowling, M. Low-varianes and zero-variance baselines for extensive-form games. arXiv preprint 1907009007009333 2019.
Desimone, R. and Duncan, J. Neural mechanisms of selective visual attention. Number 18, pp. 193-222. Annual review of neuroscience, 1995.
Ganzfried, S. and Sandholm, T. Potential-aware imperfect-recht recall abstraction with earth mover's distance in imperfect-information games. In Tienty-Fighth AAAI Conference Artificial Intelligence, 2014.
Gibson, R. G. Regret minimization in games and the development of champion multiplayer computer poker-playing agents. 2014.
Gilpin, A., Sandholm, T., and Sprensen, T. B. A heads-up no-limit texas hold' em poker player: discretized betting models and automatically generated equilibrium-finte findiing programs. Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems- Volume 2, pp. 911-918. Interattonal Foundation for Autonomous Agents and Multiagent Systems, 2008
Gordon, G. No-regret algorithms for structured prediction problems. Number CMU-CALD-05-112 CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE, 2005.
Harris, D. and Harris, S. Digital design and computer architecture (2nd ed.), volume ISBN 978-0-12- 394424-5. San Francisco, Calif.: Morgan Kaufmann.
Heinrich, J. and Silver, D. Deep reinforcement learning from self-play in imperfect-infoomation games. arXiv preprint arXiv:1603. 01 121, 2016.
Heinrich, J., Lanctot, M., and Silver, D. Fictitious self-play extensive-form games. pp. 805-813. Interaational Conference Machine Learning, 2015.
Hochreiter, S. and Schmidhuber, Long short-term memory. Number 8, pp. 1735-1780. Neural computation, 1997.
Jacob Devlin, Ming- Wei Chang. K. K. T. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18Xiv.1810.04805, 2018.
Jin, P., Keutzer, K., and Levine, S. Regret minimization for partially observable deep reinforcement learning. arXiv preprint arXiv: 11424, 2017.
Johanson, M. Measuring the size of large no-limit poker games. arXiv preprint 102.7003 2013.
12

---

Published as a conference paper at ICLR 2020
Johanson, M., Burch, N., Valenzano, R., and Bowling, M. Evaluating state-space abstractions in extensive- form games. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp. 271-278. Interational Foundation for Autonomous Agents and Multiagent Systems, 2013.
Kingma, D. P. and Ba, Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6960 2014.
Lanctot, M. Monte carlo sampling and regret minimization for equilibrium computation and decision- making in large extensive form games. 2013.
Lanctot, M., Kevin, W., Martin, Z., and Bowling, M. Monte Carlo sampling for regret minimization in extensive games. NIPS, 2009.
Lockhart, E., Lanctot, M., Pérolat, J., Lespiau, J., Morrill, D., Timbers, F, and Tuyls, K. Computing approximate equilibria in sequential adversarial games by exploitability descent. In Proceedings of the Ereenty-Eighthe International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 464-470, 2019.
Michael Bowling, Neil Burch, M. J. O. T. Heads-Up Limit Texas Hold' fold'em is solved. Science, pp. 347(6218) 2015.
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 in heads-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 Amnual Meeting of the Association for Computational Linguistics (Volume Short Papers), volume 2, pp. 687-692, 2014.
Osbome, 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.000 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 1rXiv: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 game of 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., Pé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-3433 2435,, 2018.
Steinberger, E. Single deep counterfactual regret minimization. arXiv preprint drXhv:1901.06621, 2019.
Tammelin, O. Solving large imperfect information games using CFR+. arXiv preprint, 2014.
Waugh, K., Schnizlein, D., Bowling, M., and Szafron, D. Abstraction pathologies in extensive games. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems- Dystems-Volame Volume 2, pp. 781-788, International Foundation for Autonomous Agents and Multiagent Systems, 2009.
Waugh, K., Morrill, D., Bagnell, J. A., and Bowling, M. Solving Games with Functional Regret Estimation. In AAAI, 2015.
Zinkevich, M., Michael, J., Michael, B., and Piccione, C. Regret minimization in games with incomplete information. NIPS, 2007.
13

---

Published as a conference paper at ICLR 2020
A
GAME RULES
A.1 ONE-CARD POKER
One-Card Poker is two-players IIG of poker described by Gordon 2005). The game rules defined as follows. Each player is dealt one card from deck of X cards. The first player can pass or bet, If the first player bet, the second player can call or fold. the first player pass, the second player can pass or bet. the second player bet, the first player can fold or call. The game ends with two pass, call, fold. The fold player will lose chip. the game ends with two passes, the player with higher card wins chip, If the game ends with call, the player with higher card wins 2 chips.
A.2 LEDUC HOLD'E EM
Leduc Hold' em a two-players IIG of poker, which was first introduced in Southey et al. (2012). In Leduc Hold'em, there is deck of 6 cards comprising two suits of three ranks. The cards are often denoted by king, queen, and jack. In Ledue Hold' em, the player may wager any amount of chips up to maximum of that player's remaining stack. There is also no limit on the number of raises or bets each betting round. There are two rounds. In the first betting round, each player is dealt one card from a deck of 6 cards. In the second betting round, community (or public) card is revealed from a deck the remaining 4 cards. In this paper, use Leduc(x) refer the Leduc Hold' em with stack size is
A.3 HEADS-UP UP NO-LIMIT TEXAS HOLD' EM
Upads-Up No-I 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), two players each have 20000 chips initially. One player at the position of small blind, firstly puts 50 chips 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 player folding, then three public cards are revealed face-up on the table and the flop betting round occurs. After this round, one more public card is dealt (called the turn) and the third round of betting takes place, followed by fifth public card (called 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 number of chips player has left in his stack.
14

---

Published as a conference paper at ICLR 2020
B DEFINITION OF EXTENSIVE-FORM GAMES
B.1 DETAILED DEFINITIONS AND NOTATIONS
We define the components of an extensive-fore game following Osborne & Rubinstein (1994) (page 200 ~ 201). A finite set N = {0. .n....... 1} of players. Define zi as the hidden variable of player i in IIG, e.g., in poker game zi refers to the private cards of player i. H refers to a finite set of histories. Each member h = (x:)) )i= 1,..,....,-1(((0 (0..) history (or state), which consists of each player's 's hidden variable and L actions taken by players including chance. For player i, h also can be denoted as x ====00000 - where x"; refers to the opponent's hidden variables. The empty sequence 0 is a member of H. hj E h denotes h2 is a prefix of h. where and 0 < I' < Z S H denotes the terminal histories and any member E Z is not prefix of any other sequences. A(h) {a ha E H is the set of available actions after non-terminal history H H Z. A player function P assigns a member of N [uee) to each non-terminal history, where denotes the chance player id, which usually -1. P(h) is the player who takes an action after history h.
-
of H denotes possible
h = (
I, of a history {h E H: : ii) is an information partition of player i. A set 4 is information set (infoset) of player i and (h)) refers to infoset 4 at state h. Generally, 4; could only remember the information observed by player including player i's hidden variable and public actions. Therefore I indicates a sequence in IIG, i.c., x. ap022..aa-11 1- For I EZz we denote by A(T,) the set A(h) and by P(I,) the player P(h) for any h I,. For each player i E N utility function (z(2) define the payoff of the terminal state z.
For player the expected game utility ug = (z)u(() of is the expected payoff of all possible
terminal nodes. Given a fixed strategy profile o-i, any strategy of = argmax,(Ex, u, (0/.0 s) of player i that achieves maximize payoff against >2; is a best response. For two players' extensive-fom games, Nash equilibrium is a strategy profile o² = (o) such that each player's strategy is a best response to the opponent. An e-Nash equilibriumis an approximation of a Nash equilibrium, whose strategy profile O² satisfies:
u, +e 2 maxoçex, u; (0(,0-)) Exploitability of a strategy o; is defined as
(o,,01)) A strategy is unexploitable (o,))) =0. In large two player zero-sum games G(0,)== -u
such poker, up is intractable to compute. However, if the players alternate their positions, the value of a pair games is zeros, i.c. ug +uq = =0. We define the exploitability of strategy profile a as c(ar (u) (f) + t (1)
B.2 EXPLANATION BY EXAMPLE
To provide more detailed explanation, Figure prgurensseeentss illustration of a partial game tree in One-Can Poker. In the first tree, two players are dealt (queen, jack) as shown in the left subtree and (queen, king) as shown in the right subtree. 2; denotes terminal node and h; denotes non-terminal node. There distinct nodes, corresponding 9 non-terminal nodes including chance ho and 10 terminal nodes in the left tree. The trajectory from the root to each node is history of actions. In an extensive-fone game, h; refers to this history. For example, //3 consists of actions O:Q, 1:J and P. le consists of actions 0:Q, 1:J, P and B. hg consists of actions O:Q, I:K, and B. We have hig ht, A(bs) (P.B) and P(hg)=
19
In IIG, the private card of player is invisible to player O, therefore hy and hg are actually the same for player O. We use infoset to denote the set of these undistinguished states. Similarly, h and h2 are in the same infoset. For the right tree of Figure] [ hty and hig are in the same infoset. h2g and h/g are in the same infoset.
Generally, any I E I could only remember the information observed by player i including player i's hidden variable and public actions. For example, the infoset of h7 and hy indicates a sequence of O:Q. P. and B. Because l and hi are undistinguished by player 0 in IIG, all the states have a same strategy. For example, Tn the infoset of hn and hg, we have To = To(br) = To(hs), ao(To) = (p(h)) = (ns)) (o(a(Lo) = =oo (a//br) (a)ha)))
15

---

Published as a conference paper at ICLR 2020
B.3 DETAILED DEFINITION ABOUT STRATEGY AND NASH EQUILIBRIUM
strategy profile a= {a, E E, is a collection of strategies for all players, where Σ, is the set of all possible strategies for player i. o- refers strategy of all players other than player For play i N the strategy (Ta)) is function, which assigns an action distribution over A(I.) to infoset 1, a,(a)h) we have 0z(a ()= ()) (a)lb))) For iterative method such as CFR, o² refers the strategy profile f-th iteration.
denotes the probability of action taken by player i Nffc at state h. In IIG, 1h1,hg E
1 = (=1))===4444 [ (h2),
The state reach probability of history h is denoted by x" (h) if players take actions according to a. For an empty sequence x" (0) =1. The reach probability can be decomposed into x" (h) = Ilie oH (h)= = Tf (1)) according to each player's contribution, where nद (h) = -I ( (a(ak') and
(h) = -
The infoset reach probability of I is defined n"" (I.) = EhEI, (h). If N E h, the interval state reach probability from state h to h is defined n² (N/ .h). then have n² (V' ,h) x² (h)/77 of (T)), (T.), xz (h'h). h). and x2 =h' Ji) are defined similarly.
16

---

Published as a conference paper at ICLR 2020
C ADDITIONAL EXPERIMENT RESULTS
Figure a) shows that the robust sampling with a larger batch size indicates better performance. It's reasonable because larger batch size will lead more sampled infosets in each iteration and costs more memory to store such values. If 16=1, I, only one block is sampled in each iteration. The results demonstrate that the larger batch size generally leads faster convergence. Because it's easy sample the mini-batch samples by parallel fashion on large-scale distributed system, this method is very efficient. In practice, we can specify a suitable mini-batch size according to computation and memory size.
In Figure(8th b). we compared the proposed robust sampling against Average Strategy (AS) sampling (Gibson 2014) on Ledue Hold' em (stack=5). Set the mini-batch size of MCCFR as b= 100, k= robust sampling. The parameters in average strategy sampling are set by c= A 7=0, and 3=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( (())) player i's actions while AS samples random number of player i's actions. Note that, if p is small or the number of actions is small, has a possibility that the generated random number between and is larger than for all actions, then the AS will sample zero action. Therefore, AS has higher variance than our robust sampling. In addition, according to Gibson (2014), the parameter scopes of AS are E (0.1), T [1,00), & (0,oc) respectively. They didn't I analyze the experiment results for T
109
Exploitabiiity
Exploitabiiity
10-1
RS-MCCFR+(b=11)
strategy sampling
strategy (k=))
(S-MCCFR++D==0000
robust sampling(k=11
(B-MCC)FR+b==10000)
robust sampling(k=2)
10
10-1
10a
10a
102
10a
10a
10a
102
10a
Iteration
Iteration
Mini-batch size
(b) Sampling Strategy
Figure 8: Comparison of different CFR-family methods on Ledue Hold'em. em. (a) Performance of robust sampling with different batch size. (b) Robust sampling vs strategy sampling.
17

---

Published as a conference paper at ICLR 2020
D THEORETICAL ANALYSIS
D.I REACH PROBABILITY AND POSTERIOR PROBABILITY
Lemma 2 The reach probability of the opponent proportional to posterior probability of the opponent's hidden variable, Le..p(=",144)xxrr where x; and 1 indicate a particular h.
Proof
For player i at infoset I; and fixed i's strategy profile o, i.e., th I (h) is constant. Based the defination of extensive-form game, the cominbation of J; and opponent's hidden state x" can indicate particular history h= h=*$==<< (0000000-0000000111110 With Bayes' Theorem, inference the posterior probability of opponent's 's private cards with Equation9
p(²",14)= p(=",,
p(h)
xp(h)
p(4)
p(1.)
x xp 1p(""
1=1
x (h) = (h)="((h)
D.2 ROBUST SAMPLING, OUTCOME SAMPLING AND EXTERNAL SAMPLING
For robust sampling, given strategy profile a and the sampled block Q, according to sampled profile -0 (k(k) .m)), then q(2)= -?? (2)), and the regret of action a E (r)(() is
17 ((a)))())))))) (T))₁)
Σ
9(2) Th ( (ha,))u:(z)-
Σ
= ((t))()))))
(h,))u:(z)
SEQ, ((2) ((2)
Σ
u4(2)
Ti (ha,2)
Σ
2x(2)
Ti (h.z)
(10)
rrak) (2)
=EQ,, To Ag (2)
ha
Σ
T (1a)))(((())
Σ
ho
=EQ, ACxhhl
where (2)
(.(s) u?" *=(A)) (s)
is the weighted utility according to reach probability क. (0() (z). Because the
weighted utility no long requires explicit knowledge of the opponent's strategy, can use this sampling
method for online regret minimization.
Generally, if player randomly selects min(k.,A(I.)) actions according to discrete uniform distribution (mia(0.AA(1))) at infoset I,, i.e., of (a(
ra(k) min(k,]AA(L))) then
min(k, (A.A))))))))))))))))))))))))))))
(I,)
II
A(T)))
(11)
and uz*(z) is constant number when given the sampled profile ro(k)
Specifically,
if (fk=marz,e(A(()) then o; rs(k) (T)) =1, rr(())
(1))
uz and
18

---

Published as a conference paper at ICLR 2020
- =EQg:
Σ
(x(2)<m (ha,z) - (h,=))
(12)
Therefore, robust sampling is same with external sampling when k k=marr,el AA(1)). For large game, because one player should take all actions in her infosets, it's intractable for external sampling. 'hee robust sampling is more flexible and memory-efficient than external sampling. In practice, we can specify a suitable according our memory. Experimentally. the smaller can achieve similar convergence rate to the extemal sampling.
if k k=1 and o, ro(k) os, only one history z is sampled this case,then us (2)
4x(2)
x, (x)
3h E [, for a (T)
Σ
mp (1a,
Σ of (1.2))) =EQ
haa= (1-o(((()))m(()
(13)
n.. (ha)
For & Ara(R) (I.), the regret will be 7. ((a))))) 0 (hb)). If add exploration and guarantee q(z) 2 80 O, then robust sampling is same with outcome sampling when k= 1 and o, ra(k: 0-
if A: = 1, and player randomly selects one action according to discrete uniform distribution ((4))))A((4)) infoset I,, then u: (((())(
mis)
is constant, Bhe for a (rs(k) (I.)
7. (a(
Σ
my (ha,z)u
Σ
zEQ hEQ
=EQ,,
(14)
(2())2)
=
if action is not sampled state h, the regret is i ((a (hlj). Compared to outcome sampling, the robust sampling in that case converges more efficient than outcome sampling. Note that, in our experiment, select this sampling policy as the default robust sampling when k= 1.
D.3 UNBIASED MINI-BATCII MCCFR
Theorem 1 Equ
momini butck (6 (4[66] (4).
In this section, we prove that mini-Batch MCCER gives an unbiased estimation of counterfactual value. Proof
19

---

Published as a conference paper at ICLR 2020
Eqq baini-bach (i (T:[i]] Fig aini
[ig (Ta(6')
6
#_,(2)= (1)z))u(2)
By wunift,,
x(z)l/
J= MC=
8'
1
Ely b)
8
6'
(TAIO)
(15)
==1
Σ
B ((1'))
1
> (4.)
(T)
20

---

Published as a conference paper at ICLR 2020
E SEQUENTIAL REPRESENTATION AND RECURRENT NEURAL NETWORK WITH ATTENTION
In order define our R. and S network, need to represent the infoset EZ 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 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 very simple structure, such as single tanh or sigmoid layer. Hochreiter & Schmidhuber (1997) proposed long short-tern memory method (LSTM) with the gating mechanism, which outperforms the standard version and is capable of learning long-term dependencies. Thus we will use L.TTM for the representation. Furthermore, different position the sequence may contribute differently to the decision making, we will add an attention mechanism (Desimone & Duncan 1995/(hoo et al. (2115) to the LSTM architecture to enhance the representation. For example, the player may need to take 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 1-th cell, define xy the input vector, which can be either player chance actions. Define e as the hidden layer embedding, o. as a general nonlinear function. Each action is represented by a LSTM cell, which has the ability remove add information the cell state with three different gates. Define the notation as element-wise product. The first forgetting gate layer is defined as [z),,, of [1), where [x,,et_1] denotes the concatenation of and 61-1. The second input gate layer decides which values to update and is defined as g o, (w" [x),et)))) A nonlinear layer outputs vector of new candidate values (= [z),e2-1)), which decides what can be added to the state. After the forgetring gate and the input gate, the new cell state is updated by G G= of -C-1 + Cj. The third output gate is defined as of ff (2x"(xx,,e)) Finally, the updated hidden embedding is et = of -o (Cr). As shown in Figure (a), for each LSTM cell j. the vector of attention weight is learned by an attention network. Each member in this vector is scalar a, da (w));). The attention embedding of l-th cell is then defined as ef -j=1ay=- az. which the summation of the hidden embedding e and the learned attention weight aj. The final output of the network predicted by value network, which is defined as
Ur : (a,1(0) -w" wb - w Ed (olau))))
(16)
where refers to the parameters the defined sequential neural networks. Specifically, Φ,, ti., do are sigmoid functions. de and de are hyperbolic tangent functions. 6e and ó are rectified linear functions.
Remark. The proposed RSN and ASN share the same neural architecture, but use different parameters. That is Ra,,4 = f( 1,0x and L(a,4103) f(a,1,00)). R(-110)) and S(-1.10)) denote two vectors of predicted value for all a A(I))
21

---

Published as a conference paper at ICLR 2020
F OPTIMIZING NEURAL REPRESENTATION AND IMPLEMENTATION
F.1 CODE FOR DNCFR FRAMEWORK
Algorithm provides 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.4 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 kinds of 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 M and M's respectively. These samples will be used by the NeuralAgent algorithm from Algorithm to optimize RSN and ASN. Algorithm Algorithm@proovdee provides the implementation of the proposed mini-batch robust sampling MCCFR. Note that, with the help of the proposed mini-batch techniques in Section | we can collect training samples parallelly or distributed systems, which also leads to the unbiased estimation according to the proved Theorem The acceleration training and distribution implementation is beyond the scope of this paper. To compare the performance of DNCFR and tabular CFR, all of our experiments are running on a single processor.
multi-processors
F.2
CODE FOR NEURAL NETWORKS
Algorithm 3: Optimization of Deep Neural Network
Function Neural Agent (f(-100-1)), M, initialize oplimizer, scheduler 8T " 4 t0, +-0
== 3xpoch do loss+
For each training epoch do
{z(0) ())
j==1 M
batch_loss+ lossossstt Ti
1 HE ( )0)
back propagation batch_ loss with learning rate Ir clip gradient of 8T to [-c,
optimizer @bbttch loss)
(batchh
Ir sheduler(tr)
if avg(loss) <,Booss then
thest + early stopping. else if aug(loos) <leest then lbest (log(ooss), liestt + L, best & 0"
if limot > Pre then
Ir + Byr
return gT
Notations in Neural Networks. Define Bepoch as training epoch, 3t, as learning rate, Blose as the criteria for early stopping, Sre as the upper bound for the number of iterations from getting the minimal loss last time, 01 as the old parameter learned in t-1 iteration, f(-10-11) the neural network, M as the training samples including infosets and the corresponding targets. To simplify notations, we use 3 to denote the set of hyperparameters in the proposed deep neural networks. A and 83 refer the sets of hyperparameters in RSN and ASN respectively.
Optimize Neural Networks. Algorithm 3 provides the implementation of the optimization technique for both RSN and ASN. Both R, 10 and S(a. (8))) are optimized by mini-batch stochastic gradient descent method. In this paper, we use Adam optimizer (Kingma Ba (014) with both momentum and adaptive learning rate techniques. We also replace Adam by other optimizers such as Nadam, R.M.propp. 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 enough loss because of potential saddle points or local minima. To obtain a relatively higher accuracy and lower optimization loss, design novel scheduler to reduce the learning rate when the loss has stopped decrease. Specifically,
22

---

Published as a conference paper at ICLR 2020
the scheduler reads metrics quantity, e.g. mean squared enror. If no improvement is seen for number of epochs, the learning rate is reduced by a factor, In addition, we will reset the learning rate in both optimizer and scheduler once loss stops decreasing within Sre 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 Stoes.
The feature is encoded as following, As shown in the figure (a), for history h and player P(h), use vectors to represent the observed actions including chance player. For example, on Leduc Hold' em, the input feature 2ạ for /-th cell 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 the existing position is and the others are O. there are no public cards, the respective position will be filled with O. The betting chips in the encoded vector will represented by the normalized cumulative spent, which the cumulative chips dividing the stack size. For HUNL, each card is encoded by vector with length 17: 13 for ranking embedding and for suit embedding. The actions in public sequences are represented by one-hot and the raise action is also represented by the normalized cumulative spent.
23

---

Published as a conference paper at ICLR 2020
F.3
CODE FOR MINI-BATCH ROBUST SAMPLING MCCER
Algorithm 4: Mini-Batch RS-MCCFR with Double Neural Networks
Function Minn--Batch-MCCFR-
:
Mi 0, .M's 0 For all i= to b do in parallel then
DOCFR-NN((,0.0...
return MRss
Function MCCFR NN (t, h, i, TT. ra(k))
(hh
he Z then
return (4(h)
else if P(h) then
a~v0-1(
return MICCR--NN(.ha.,, (o(k))
else if P(h) =i then
else 0
R,((IT:) < R if |
(([4)=CCalcllateStmaaeyy (R.
(1)
AT*(A) (1+) sampling k different actions according to of (k(k)
For (E) do
For ( do =[(]))) ( (a)))
Store updated cumulative regret tuple (44,r((((T)) in Mr
Store updated current strategy dictionary (-,ss(((IT)) in M's
return (1)
else
(-1:) R(- if else o + CallaaaaaaaaateSSatggggg ((.))) a~oa;((
return MC (k(
Function Calculatesttraeegy (Ra(-14,).4a))
sum+ + max
For dEA(L,) do
a,(a[T,)= maxt (a) if sum else [AU.I
sum
return (T))
Algorithm 4 presents application scenario of the proposed mini-bated robust sampling method. The function MCCFR-NN will traverse the game tree like tabular MCCFR, which starts from the root 0. Define 1; the infoset of h. Suppose that player i will sample k actions according the robust sampling. Algorithm 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 E A(I,) will sampled according to the strategy o (-())). Then this action will be added to the history, i.e., h ha.
24

---

Published as a conference paper at ICLR 2020
If P(I)== ii, the current strategy can be updated by the cumulative regret predicted by RSN. Then sample actions according the specified sampled strategy profile a²((k) After a recursive updating, we can obtain the counterfactual value and regret of each action at 7,. For the observed nodes, their counterfactual regrets and numerators of the corresponding average strategy will be stored in M' and M's respectively.
of P(4) is the opponent, only one action will be sampled according the strategy (I,(
The function Soni-Batch-MCCEE
presents a bini-bbtch sampling method, where 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.
Remark: We update average in the procedure of P(h)= =i, which potentially leads to biased estimate of average strategy. There is a trade-off among unbiased estimate, convergence, and data efficiency on Algorithm 4 A feasible solution is using seehhatticllly-wighhhee averaging (SWA). However, SWA typically leads to a large variance as discussed in Marc's Ph.D. thesis (Lanctot 2013) (p49). The classical external sampling(ES) solves this problem by only updating average strategy for -. Because ES samples k= [=4)) actions for i and only samples one action for i, it's inefficient to collect samples for average Typically, when collecting average strategy samples at i, we need using SWA to maintain unbiased estimate of average strategy. However, because of the high variance of SWA, we find the one without SWA converges more efficient empirically,
strategy at -i in neural CFR. In contrast, we collect samples
F.4 HYPERPARAMETER
In experiments, we set the network hyperparameters as following.
Hyperparameters on Ledue em. The Leduc(5), Leduc(10) and Leduc(15) in our experiments have 1.1 10a infosets (6 x 10a states), 3 x 10s (1.5 10 states) and x 10th (2 x 10" states) infosets 3 as the default parameter in the provable robust sampling method on all such games. For the small Leduc(5), we select b= 100 as the default parameter in the mini-batch MCCFR ??, which only samples 5.59% infosets in each iteration. For the larger Leduc(10) 10) and Leduc(15), we select default 6=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) 155) 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 & Bal 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 the number of infosets. The default learning rate of Adam is 8r = 0.001. A scheduler, who will reduce the learning rate based the number of epochs and the convergence rate of loss, help the neural agent to obtain 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 this scheduler is 10-6. To avoid the algorithm converging to potential local minima or saddle points, we will reset the learning rate to 0.001 and help the optimizer obtain better performance. 0%' Ofest is the best parameters achieve the lowest loss after T epochs, If average loss for epoch t is less than the specified criteria =10 -4 for RSN (set this parameter as 10 for RSN), we will early stop the optimizer. We set Sepoch = 2000 and update the optimizer 2000 maximum epochs. For ASN, we set the loss of early stopping criteria as 10-5 The learning rate will be reduced by 0.7 when loss has stopped improving after 15 epochs.
respectively. We set k: 3
For NFSP our experiment, we set the hyperparameters according its original paper (Heinrich & Silver 2016). The neural network in NESP had 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 for every 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 NESP to 0.1. The exploration in c-greedy policies started at 0.06 and decayed to O.
Hyperparameters on HUNL. To solve HUNL(I) and HUNL(2), we sample 0.01% and 0.001% infosets in each iteration. The batch size of training neural network is set to 100000. We prefer to using large batch size, because gradient descent spends most of running time. Typically, larger batch size indicates less number of gradient decent updates. We perform DNCFR under different number of embedding sizes and the steps of gradient descent updates. The experiment results are presented in Figure Other hyperparameters in neural networks and optimizers are set to be the same with Leduc(15).
25

---

Published as a conference paper at ICLR 2020
G ABS-CFR, DEEPSTACK, DOUBLE NEURAL CFR AND HUNL
Taining Sample
Training Sample
Training Sample
Validation Sample
Validation Sample
Validation Sample
Huberr Loss
Huberr
Hubber
c.mm
143
698
Iteration
Iteration
Iteration
(a) Preflop loss of CFV Network
(b) Flop loss of CFV Network
(c) Tur loss of CFV Network
Figure 9: 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 deep counterfactual value network on turn subgame (contains last two rounds HUNL), the training sample is 0.016 and the validation sample is 0.035 while they are 0.016 and 0.026 in original DeepStack. Specifically, the learning rate is decayed in 200th iteration(iteration is equal to epoch here), therefore the huber loss in (b) and (c) decreased. To balance the performance of 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 (iilerr 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 both computational time and space complexity. To evaluate the proposed method, we reimplement DeepStack (Moravcik et al. (017)), which is an expert-level artificial intelligence in Heads-up No-Limit Texas Hold'en Ho.d'em. DeepStack defeated professional poker players. The decision points of Heads-up No-Limit Texas Hold" em exceed 10 (Johanson, 2013). We provide the game rules of Texas hold' em in Appendix A..3
In this section, we provided some details about our implementation, compared our agent with the original DeepStack to guarantee the correctness of the implementation, and applied our double neural method on the subgame of DeepStack.
G.1 DETAILS ABOUT ABS-CE CBS-CER
ABS-CFR agent is an enhanced version of HITSZ LMW 2pn, whose previous version won the third prize of the 2018 Annual Computer Poker Competition (ACPC) and has 2 10 information sets. The ideas of ABS-CFR agent is first abstract the full HUNL into the smaller abstract game and using CFR to solve the abstracted game. The ABS-CFR using two kind-of abstractions: the first one is action abstraction and the second is card abstraction. The action abstraction is using discretized betting model (Gilpin el al. 2008). which can do fold, call, 0.5x pot raise, 1x pot raise, 2x pot raise, and 4x pot raise and all-in in each decision node. The card abstraction is using domain knowledge that strategically similar states are collapsed into single state. In preflop we use lossless abstraction which has 169 buckets. flop and turn. we use potential-aware imperfect-recal abstraction with earth mover distance (Ganzfried & Sandholm, 2014), which has 10000 and 50000 buckets respectively. In the river, we use opponent cluster hand strength abstraction (Johanson et al. 2013), which has 5000 buckets.
G.2 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 this algorithm according to the original article (Moraveik al. 2017). It should be noted
26

---

Published as a conference paper at ICLR 2020
that the released example code I on Ledue Hold'em em cannot directly be used Heads-up No-Limit Texas Hold' em for at least three reasons: (1) The tony game Ledue Hold' em only has rounds, 6 cards with default stack size 5, which is running size 20000 according to ACPC game rules. (2) Specifically, there are 55,627, (2277,62004888000
single desktop, while HUNL has four rounds, 52 cards and stack possible public and private card combinations for two players on HUNI. (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 '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 and training samples. To optimize the counterfactual value network on turn subgame (this subgame looks ahead two rounds and contains both turn and river), we generate nine million samples. Because each sample is generated by traversing 1000 iterations using CFR+ algorithm based on random reach probability, these huge samples are computation cumputaaion-eepensiive and cost 1500 nodes cluster (each node contains 32 CPU cores and 60GB memory) more than 60 days. To optimize the counterfactual value samples,
network on flop subgame (this subgame only looks ahead one round), we generate two million which costs about one week by using the similar computation resource. The auxiliary network preflop subgame is optimized based on ten million samples and costs days. The whole implementation of DeepStack costs several months and hundreds of thousands of lines of codes.
G.3 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 Heads-Up No-Limit Texas Hold' emm, computation of exploitability is expensive because of its 10 10 searching space.
We verified the correctness of 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 these logs, 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 i0 Appendix DaadiixGPPrvviii 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_ BW___M__22__0 2_p_ 120 mbb/g.
27

---

Published as conference paper at ICLR 2020
Alberta DeepStack Take Fold Probabiliyy
Our Agent Take Fold Probability
0.6
0.8
02
0.2
24
-000
0.0
Alberta DeepStack Take Call Probability
Our Agent Take Call Probabilit ity
0.8
0
0.8
8-
0.2
0.2
Alberta DeepStack
Pot Raise Probability
Agent Raise Probability
0.5
0.8
004
0.2
02
0.1
DeepStack
Probability
Agent Probability
0.8
0.8
0.4
0.4
Figure 10: Comparison action probability between Alberta's DeepStack (Moravcik et al. 2017) (the left
column) and reimplemented DeepStack (the right column).
28


Reviews:
[{"review_id": "ryg_h5Lk9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces two neural networks, one for average regrets and one for average strategy, to (approximately) run CFR algorithm in (large) IIG. New sampling techniques are used to train these networks to represent the resulting strategy.\n\nI remember seeing this paper in the last year's OpenReview for ICLR - I was not reviewing the paper.\nI enjoyed the first version of the paper, but it was missing experiments on larger games and some questions on smaller games were unanswered.\nIn this version, authors clearly spent a large amount of time (including re-implementing DeepStack!) so that they could compare on large games (namely HU no-limit Poker) and overall greatly improved the paper and evaluation.\n\nThe evaluation on small games includes comparison to NFSP/XFP, as well as investigating time/space trade-off.\nFor the large game, I like that the authors evaluated against an ACPC agent.\nPrevious work is well cited, and authors have a good overall map of related work (both older results and new papers).\n\nIssues:\n\n1) One downside of the paper is that it is very close to the \"Deep Counterfactual Regret Minimization\".\nWhile authors devote a full paragraph in section 6 to contrast these, the difference is relatively small.\nI do not think it is fair to dwell too much on this though, since the first version of the paper with this idea originally came *before* DeepCFR publication!\n\n2) Since the approach is so similar to DeepCFR, it would be nice to include it in comparison (not just NFSP/XFP).\n\n\nMinor details:\n\n- Page 9: \"...which has no limited number of actions, ...\" rephrase please, this sounds like the game is infinite.\n\n- Page 9: \", more abstracted action leads to better strategy...\" more abstracted sounds like it is smaller, rephrase please to something like \"finer grained abstraction\".\n\n- Minor frequent grammatical issues, but does not derail from the flow and semantics of the paper.\n\nConclusion:\n\nOverall, the paper introduces method that is interesting to the community, scales to large games and the paper includes comprehensive evaluation section.\nI believe it should be accepted.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJx2eN_6Kr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed a double neural counterfactual regret minimization algorithm (DNCFR) that uses a RegretSumNetwork to approximate cumulative regret and an AvgStrategyNetwork to approximate the average strategy. To help the training, the authors use robust sampling and a mini-batch training methods. The main contributions of the paper are: First, the DNCFR algorithm and the recurrent neural network architecture; Second, an efficient sampling and training method; Third, plenty of experiments that corroborate the effectiveness of DNCFR.\n\nIt is interesting and meaningful to develop neural-based CFR, in order to eliminate the manual abstraction and apply CFR to large-scale imperfect information games. The authors tested their algorithm on a medium scale game HUNL(1) (with 2 * 10 ^ 8 information sets) and trained a blueprint strategy on large scale game HUNL(2), which is combined with value networks from DeepStack and beats ABS-CFR a lot. It is great to see that DNCFR works on large scale games. However, both HUNL(1) and HUNL(2) are one-round games and it not clear how to combine the blueprint strategy trained by DNCFR with DeepStack. What’s more, as DNCFR is only effective on first round as the blueprint strategy trainer when played against ABS-CFR, it is more likely that DeepStack beats ABS-CFR, instead of DNCFR beats it. So the result in Figure 7(c) is not so convincing.\n\nUnlike tabular CFR that save regrets and strategies for all the information sets or other neural-based algorithms that need large reservoir buffers. It only needs to save data sampled from the most recent iterations, which saves much memory. In fact, this is a bootstrap method borrowed from Reinforcement learning. Though the method save memory and has lower variance than methods that use reservoir buffers, it is bias as it trains the new RSN and ASN based on the output of the old networks. It seems good when the game size is small and the CFR iterations is small. It may needs very large CFR batches and very many gradient descent updates when training on large scale games, in order to control the bias. The results in Figure 7(a) and 7(b) are limited in CFR iterations. Experiments using different gradient descent updates and different CFR batch while given more CFR iterations should be tested, in order to show the effect of the bias training.\nIn “Algorithm 4”. The calculation of average strategy seems wrong. Because you are using MCCFR, According to “Monte Carlo sampling and regret minimization for equilibrium computation and decision-making in large extensive form games”, you may need a method call “stochastically-weighted averaging”. It should be noted that the sampling probability of\neach information set is not equal. You may need to discuss this.\n\nThe authors train the network for 2000 updates when the batch size is 256 for Leduc and 100000 for HUNL(1) and HUNL(2) in every CFR iteration (I am not sure how much gradient updates are used in HUNL(2), it is not given). There's quite a lot of updates in every CFR iteration. But it is acceptable when compared to Deep CFR proposed by Brown, which uses 4000 updates and the batch size is 10000.\n\nExperiments:\n1. In the ablation studies, the algorithms are tested on small scale game Leduc(5). It is quite a small game that event the size neural parameters is larger than the size of information sets. It is OK but larger games make more sense. Especially in the\nexperiment of “Individual network”, as this experiment is important to show that\nDNCFR is comparable to tabular CFR and the bias is acceptable.\n2. The paper didn’t show what the learned regret and average strategy looks. If they are\nshowed, it would be helpful to understand the bias in the bootstrap learning.\n3. In the part “Is robust sampling helpful”, the authors want to show that the robust sampling with k=1 is better than outcome sampling. But I didn’t find how they set the exploration parameter in outcome sampling and I am afraid that it doesn’t make sense. Because outcome sampling has a parameter to adjust the exploration. According to \"Monte Carlo sampling and regret minimization for equilibrium computation and decision-making in large extensive form games\", the best exploration parameter is different in different game, but it is almost sure that totally exploration is not the best setting (it is equivalent to the robust sampling with k = 1).\n4. In the part “Do the neural networks generalize to unseen infosets”. The authors claims that it is true. But the experiment only shows that the neural network don’t forget\ninformation sets that trained before.\n5. In the part “How well does DNCFR on larger games”, the DNCFR is limited to 100\niterations while is allow to run for 1000 iterations in other experiments. 100 iterations\nare too few to show the effectiveness of DNCFR on these games.\n6. The algorithm is tested on HUNL(1) and HUNL(2), which are one round and action- abstracted version of HUNL. But the authors should give more detail description of\nthese games.\n7. It is not clear how to combine the blueprint strategy trained by DNCFR with\nDeepStack, as DeepStack uses continual resolving and don’t need any blueprint strategy. And it would be interesting if the head-to-head performance of DNCFR agent on large scale games (for example, the FHP with two rounds and more than 1e^9 information sets) is reported, instead of the performance of the agent that combined with DeepStack.\n8. In section 5.4, “When variance reduction techniques are applied, Figure 7(c)...”. The authors didn’t explain why the variance reduction techniques are needed here, but in order to compare the algorithm directly, some other advanced techniques should not be used here.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Double coúnterfactual regret minimization is an extension of neural counterfactual regret minimization that uses separate policy and regret networks (reminiscent of similar extensions of the basic RL formula in reinforcement learning). Several new algorithmic modifications are added to improve the performance. 

The reviewers agree that this paper is novel, sound, and interesting. One of the reviewers had a set of questions that the authors responded to, seemingly satisfactorily. Given that this seems to be a high-quality paper with no obvious issues, it should be accepted.
Decision: Accept (Poster)