Title: DOUBLE NEURAL COUNTERFACTUAL REGRET MINIMIZATION

Abstract: Counterfactual Regret Minimization (CRF) is a fundamental and effective technique for solving Imperfect Information Games (IIG). However, the original CRF algorithm only works for discrete state 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 and continuing to improve from a poor strategy profile. In this paper, we propose a double neural representation for the imperfect information games, where one neural network represents the cumulative regret, and the other represents the average strategy. Furthermore, we adopt the counterfactual regret minimization algorithm to optimize this double neural representation. To make neural learning efficient, we also developed several novel techniques including a robust sampling method, mini-batch Monte Carlo Counterfactual Regret Minimization (MCCFR) and Monte Carlo Counterfactual Regret Minimization Plus (MCCFR+) which may be of independent interests. Experimentally, we demonstrate that the proposed double neural algorithm converges significantly better than the reinforcement learning counterpart.

1. INTRODUCTION:

In Imperfect Information Games (IIG), a player only has partial access to the knowledge of her opponents before making a decision. This is similar to real-world scenarios, such as trading, traffic routing, and public auction. Thus designing methods for solving IIG is of great economic and societal benefits. Due to the hidden information, a player has to reason under the uncertainty about her opponents' information, and she also needs to act so as to take advantage of her opponents' uncertainty about her own information.

Nash equilibrium is a typical solution concept for a two-player extensive-form game. Many algorithms have been designed over years to approximately find Nash equilibrium for large games. One of the most effective approaches is CFR (Zinkevich et al., 2007) . In this algorithm, the authors proposed to minimize overall counterfactual regret and prove that the average of the strategies in all iterations would converge to a Nash equilibrium. However, the original CFR only works for discrete state 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 and continuing to improve if starting from a poor strategy profile.

To alleviate CFR's large memory requirement in large games such as heads-up no-limit Texas Hold'em, Moravcik et al. (2017) proposed a seminal approach called DeepStack which uses fully connected neural networks to represent players counterfactual values and obtain a strategy online as requested. However, the strategy is still represented as a tabular form and the quality of this solution depends a lot on the initial quality of the counterfactual network. Furthermore, the counterfactual network is estimated separately, and it is not easy to continue improving both counterfactual network and the tabular strategy profile in an end-to-end optimization framework. Heinrich et al. (2015) ; Heinrich & Silver (2016) proposed end-to-end fictitious self-play approaches (XFP and NFSP respectively) to learn the approximate Nash equilibrium with deep reinforcement learning. In a fictitious play model, strategies are represented as neural networks and the strategies are updated by selecting the best responses to their opponents' average strategies. This approach is advantageous in the sense that the approach does not rely on abstracting the game, and in theory, the strategy should continually improve as the algorithm iterates more steps. However, these methods do not explicitly take into account the hidden information in a game, because they are optimized based on the transition memory and the reward of the intermediate node is the utility of the game rather than the counterfactual value which consider the distribution of hidden variables (opponent's private information). In experiments for games such as Leduc Hold'em, these methods converge slower than tabular based counterfactual regret minimization algorithms. Waugh et al. (2015) used handcraft features of the information sets to estimates the counterfactual regret. However, it need traverse the full game tree which is infeasible in large games.

Thus it remains an open question whether the purely neural-based end-to-end approach can achieve comparable performance to tabular based CFR approach. In the paper, we partially resolve this open question by designing a double neural counterfactual regret minimization algorithm which can match the performance of tabular based counterfactual regret minimization algorithm. We employed two neural networks, one for the cumulative regret, and the other for the average strategy. We show that careful algorithm design allows these two networks to track the cumulative regret and average strategy respectively, resulting in a converging neural strategy. Furthermore, in order to improve the convergence of the neural algorithm, we also developed a new sampling technique which has lower variance than the outcome sampling, while being more memory efficient than the external sampling. In experiments with One-card poker and a large Leduc Hold'em containing more than 10 7 nodes, we showed that the proposed double neural algorithm has a strong generalization and compression ability even though only a small proportion of nodes are visited in each iteration. In addition, this method can converge to comparable results produced by its tabular counterpart while performing much better than deep reinforcement learning method. The current results open up the possibility for a purely neural approach to directly solve large IIG.

2. BACKGROUND:

In this section, we will introduce some background on IIG and existing approaches to solve them.

2.1. REPRESENTATION OF EXTENSIVE-FORM GAME:

We define the components of an extensive-form game following Osborne & Ariel (1994) (page 200 ∼ 201) . A finite set N = {0, 1, ..., n -1} of players. Define h v i as the hidden variable of player i in IIG, e.g., in poker game h v i refers to the private cards of player i. H refers to a finite set of histories. Each member h = (h v i ) i=0,1,...,n-1 (a l ) l=0,...,L-1 = h v 0 h v 1 ...h v n-1 a 0 a 1 ...a L-1 of H denotes a possible history (or state), which consists of each player's hidden variable and L actions taken by players including chance. For player i, h also can be denoted as h v i h v -i a 0 a 1 ...a L-1 , where h v -i refers to the opponent's hidden variables. The empty sequence ∅ is a member of H. h j h denotes h j is a prefix of h, where h j = (h v i ) i=0,1,...,n-1 (a l ) l=1,...,L -1 and 0 < L < L. Z ⊆ H denotes the terminal histories and any member z ∈ Z is not a prefix of any other sequences. A(h) = {a : ha ∈ H} is the set of available actions after non-terminal history h ∈ H \ Z. A player function P assigns a member of N ∪ {c} to each non-terminal history, where c denotes the chance player id, which usually is -1. P (h) is the player who takes an action after history h. I i of a history {h ∈ H : P (h) = i} is an information partition of player i. A set I i ∈ I i is an information set of player i and I i (h) refers to information set I i at state h. Generally, I i could only remember the information observed by player i including player i s hidden variable and public actions. Therefore I i indicates a sequence in IIG, i.e., h v i a 0 a 2 ...a L-1 . For I i ∈ I i we denote by A(I i ) the set A(h) and by P (I i ) the player P (h) for any h ∈ I i . For each player i ∈ N a utility function u i (z) define the payoff of the terminal state z. A more detailed explanation of these notations and definitions is presented in section B.

2.2. STRATEGY AND NASH EQUILIBRIUM:

A strategy profile σ = {σ i |σ i ∈ Σ i , i ∈ N } is a collection of strategies for all players, where Σ i is the set of all possible strategies for player i. σ -i refers to strategy of all players other than player i. For play i ∈ N the strategy σ i (I i ) is a function, which assigns an action distribution over A(I i ) to information set I i . σ i (a|h) denotes the probability of action a taken by player i ∈ N ∪ {c} at state h. In IIG, ∀h 1 , h 2 ∈ I i , we have

I i = I i (h 1 ) = I i (h 2 ), σ i (I i ) = σ i (h 1 ) = σ i (h 2 ), σ i (a|I i ) = σ i (a|h 1 ) = σ i (a|h 2 ).

For iterative method such as CFR, σ t refers to the strategy profile at t-th iteration. The state reach probability of history h is denoted by π σ (h) if players take actions according to σ. For an empty sequence π σ (∅) = 1. The reach probability can be decomposed into

π σ (h) = i∈N ∪{c} π σ i (h) = π σ i (h)π σ -i (h) according to each player's contribution, where π σ i (h) = h a h,P (h )=P (h) σ i (a|h ) and π σ -i (h) = h a h,P (h ) =P (h) σ -i (a|h ). The information set reach probability of I i is defined as π σ (I i ) = h∈Ii π σ (h). If h h, the interval state reach probability from state h to h is defined as π σ (h , h), then we have π σ (h , h) = π σ (h)/π σ (h ). π σ i (I i ), π σ -i (I i ), π σ i (h , h

), and π σ -i (h , h) are defined similarly.

2.3. COUNTERFACTUAL REGRET MINIMIZATION:

In large and zero-sum IIG, CFR is proved to be an efficient method to compute Nash equilibrium (Zinkevich et al., 2007; Brown & Sandholm, 2017) . We present some key ideas of this method as follows.

Lemma 1: The state reach probability of one player is proportional to posterior probability of the opponent's hidden variable, i.e., p(h v -i |I i ) ∝ π σ -i (h), where h v i and I i indicate a particular h. (see the proof in section G.1) For player i and strategy profile σ, the counterfactual value (CFV) v σ i (h) at state h is define as

EQUATION

where

u i (z) = π σ -i (z)u i (z)

is the expected reward of player i with respective to the approximated posterior distribution of the opponent's hidden variable. The action counterfactual value of taking action a is v σ i (a|h) = v σ i (ha) and the regret of taking this action is

r σ i (a|h) = v σ i (a|h) -v σ i (h). Similarly, the CFV of information set I i is v σ i (I i ) = h∈Ii v σ i (h) and the regret is r σ i (a|I i ) = z∈Z,ha z,h∈Ii π σ i (ha, z)u i (z) -z∈Z,h z,h∈Ii π σ i (h, z)u i (z).

Then the cumulative regret of action a after T iterations is

EQUATION

where

R 0 i (a|I i ) = 0. Define R T,+ i (a|I i ) = max(R T i (a|I i ), 0

), the current strategy (or behavior strategy) at T + 1 iteration will be updated by

σ T +1 i (a|I i ) =    R T ,+ i (a|Ii) a∈A(I i ) R T ,+ i (a|Ii) if a∈A(Ii) R T,+ i (a|I i ) > 0 1 |A(Ii)|

otherwise.

(3)

The average strategy σi T from iteration 1 to T is defined as:

EQUATION

)

where π σ t i (I i ) denotes the information set reach probability of I i at t-th iteration and is used to weight the corresponding current strategy σ t i (a|I i ). Define s t i (a|I i ) = π σ t i (I i )σ t i (a|I i ) as the additional numerator in iteration t, then the cumulative numerator can be defined as

EQUATION

where S 0 (a|I i ) = 0.

2.4. MONTE CARLO CFR:

When solving a game, CFR needs to traverse the entire game tree in each iteration, which will prevent it from handling large games with limited memory. To address this challenge, Lanctot et al. (2009) proposed a Monte Carlo CFR to minimize counterfactual regret. Their method can compute an unbiased estimation of counterfactual value and avoid traversing the entire game tree. Since only subsets of all information sets are visited in each iteration, this approach requires less memory than standard CFR.

Define Q = {Q 1 , Q 2 , ..., Q m }

, where Q j ∈ Z is a block of sampling terminal histories in each iteration, such that Q j spans the set Z. Generally, different Q j may have an overlap according to the specify sampling schema. Specifically, in the external sampling and outcome sampling, each block Q j ∈ Q is a partition of Z. Define q Qj as the probability of considering block Q j , where m j=1 q Qj = 1. Define q(z) = j:z∈Qj q Qj as the probability of considering a particular terminal history z. Specifically, vanilla CFR is a special case of MCCFR, where Q = {Z} only contain one block and q Q1 = 1. In outcome sampling, only one trajectory will be sampled, such that ∀Q j ∈ Q,

|Q j | = 1 and |Q j | = |Z|. For information set I i , a sample estimate of counterfactual value is ṽσ i (I i |Q j ) = h∈Ii,z∈Qj ,h z 1 q(z) π σ -i (z)π σ i (h, z)u i (z)

. Lemma 2: The sampling counterfactual value in MCCFR is the unbiased estimation of actual counterfactual value in CFR. Lanctot et al. (2009) .) Define σ rs as sampling strategy profile, where σ rs i is the sampling strategy for player i and σ rs -i are the sampling strategies for players expect i. Particularly, for both external sampling and outcome sampling proposed by (Lanctot et al., 2009) , σ rs -i = σ -i . The regret of the sampled action a ∈ A(I i ) is defined as

E j∼q Q j [ṽ σ i (I i |Q j )] = v σ i (I i ) (Lemma 1,

EQUATION

)

where In this section, we will explain our double neural CFR algorithm, where we employ two neural networks, one for the cumulative regret, and the other for the average strategy. As shown in Figure 1 (A), standard CFR-family methods such as CFR (Zinkevich et al., 2007) , outcome-sampling MCCFR, external sampling MCCFR (Lanctot et al., 2009) , and CFR+ (Tammelin, 2014) need to use two large tabular-based memories M R and M S to record the cumulative regret and average strategy for all information sets. Such tabular representation makes these methods difficult to apply to large extensive-form games with limited time and space (Burch, 2017) .

u rs i (z) = ui(z) π σ rs i (z)

In contrast, we will use two deep neural networks to compute approximate Nash equilibrium of IIG as shown in Figure 1 (B) . Different from NFSP, our method is based on the theory of CFR, where the first network is used to learn the cumulative regret and the other is to learn the cumulative numerator of the average strategy profile. With the help of these two networks, we do not need to use two large tabular-based memories; instead, we rely on the generalization ability of the compact neural network to produce the cumulative regret and the average strategy. In practice, the proposed double neural method can achieve a lower exploitability with fewer iterations than NFSP. In addition, we present experimentally that our double neural CFR can also continually improve after initialization from a poor tabular strategy.

3.1. OVERALL FRAMEWORK:

The iterative updates of the CFR algorithm maintain two strategies: the current strategy σ t i (a|I i ), and the average strategy σt i (a|I i ) for ∀i ∈ N, ∀I i ∈ I i , ∀a ∈ A(I i ), ∀t ∈ {1, . . . , T }. Thus, our two neural networks are designed to maintain these two strategies in iterative fashion. More specifically,

• Current strategy. According to Eq. ( 3), current strategy σ t+1 (a|I i ) is computed by the cumulative regret R t (a|I i ). We only need to track the numerator in Eq. ( 3) since the normalization in the denominator can easily be computed when the strategy is used. Given information set I i and action a, we design a neural network RegretSumNetwork(RSN) R(a, I i |θ t R ) to learn R t (a|I i ), where θ t R is the parameter in the network at t-th iteration. As shown Figure 1 

(b), define memory M R = {(I i , rσ t i ((a|I i )|Q j ))|∀i ∈ N, ∀a ∈ A(I i ), h ∈ I i , h z, z ∈ Q j }.

Each member of M R is the visited information set I i and the corresponding regret rσ t i ((a|I i )|Q j ), where Q j is the sampled block in t-th iteration. According to Eq. ( 2), we can estimate R(a, I i |θ t+1 R ) using the following optimization:

EQUATION

• Average Strategy. According to Eq. ( 4), the approximate Nash equilibrium is the weighted average of all previous strategies over T iterations. Similar to the cumulative regret, we employ another deep neural network AvgStrategyNetwork(ASN) to learn the numerator of the average strategy. Define

M S = {(I i , π σ t i (I i )σ t i (a|I i ))|∀i ∈ N, ∀a ∈ A(I i ), h ∈ I i , h z, z ∈ Q j }.

Each member of M S is the visited information set I i and the value of

π σ t i (I i )σ t i (a|I i )

, where Q j is the sampled block in t-th iteration. Then the parameter θ t+1 S can estimated by the following optimization:

EQUATION

)

Remark 1: In each iteration, only a small subset of information sets are sampled, which may lead to the neural networks forgetting values for those unobserved information sets. To address this problem, we will use the neural network parameters from the previous iteration as the initialization, which gives an online learning/adaptation flavor to the updates. Furthermore, due to the generalization ability of the neural networks, even samples from a small number of information sets are used to update the new neural networks, the newly updated neural networks can produce very good value for the cumulative regret and the average strategy.

Remark 2: As we increase the number of iterations t, the value of R t i (a|I i ) will become increasingly large, which may make neural network difficult to learn. To address this problem, we will normalize the cumulative regret by a factor of √ t to make its range more stable. This can be understood from the regret bound of online learning. More specifically, let ∆ = max Ii,a,t |R t (a|I i ) -R t-1 (a|I i )|, ∀I i ∈ I, a ∈ A(I i ), t ∈ {1, . . . , T }. We have R t i (a|I i ) ≤ ∆ |A|t according to the Theorem 6 in (Burch, 2017) , where |A| = max Ii∈I |A(I i )|. In practice, we can use the neural network to track Rt i (a|I i ) = R t i (a|I i )/ √ t, and update it by

EQUATION

)

Remark 3: The optimization problem for the double neural networks is different from that in DQN (Mnih et al., 2015) . In DQN, the Q-value for the greedy action is used in the update, while in our setting, we do not use greedy actions. Algorithm E gives further details on how to optimize the objectives in Eq. ( 7) and Eq. ( 8).

Relation between CFR, MCCFR and our double neural method. As shown in Figure 1 , these three methods are based on the CFR framework. The CFR computes counterfactual value and regret by traversing the entire tree in each iteration, which makes it computationally intensive to be applied to large games directly. MCCFR samples a subset of information sets and will need less computation than CFR in each iteration. However, both CFR and MCCFR need two large tabular memories to save the cumulative regrets and the numerators of the average strategy for all information sets, which prevents these two methods to be used in large games directly. The proposed neural method keeps the benefit of MCCFR yet without the need for two large tabular memories.

3.2. RECURRENT NEURAL NETWORK REPRESENTATION FOR INFORMATION SET:

In order to define our R and S network, we need to represent the information set I i ∈ I in extensive-form games. In such games, players take action in alternating fashion and each player makes a decision according to the observed history. Because the action sequences vary in length, in this paper, we model them with a recurrent neural network and each action in the sequence corresponds to a cell in 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 2 (A) provides an illustration of the proposed deep sequential neural network representation for information sets. Besides the vanilla RNN, there are several variants of more expressive RNNs, such as the GRU (Cho et al., 2014) and LSTM (Hochreiter & Schmidhuber, 1997) . In our later experiments, we will compare these different neural architectures as well as a fully connected network representation.

Furthermore, different position in the sequence may contribute differently to the decision making, we will add an attention mechanism (Desimone & Duncan, 1995; Cho et al., 2015) to the RNN architecture to enhance the representation. For example, the player may need to take a more aggressive strategy after beneficial public cards are revealed. Thus the information, after the public cards are revealed may be more important. In practice, we find that the attention mechanism can help the double neural CFR obtain a better convergence rate. In section D, we will provide more details on neural network architectures.

3.3. CONTINUAL IMPROVEMENT:

With the proposed framework of double neural CFR, it is easy to initialize the neural networks from an existing strategy profile based on the tabular representation or neural representation. For information set I i and action a, in an existing strategy profile, define R i (a|I i ) as the cumulative regret and S (a|I i ) as the cumulative numerator of average strategy. We can clone the cumulative regret for all information sets and actions by optimizing

EQUATION

)

Similarly, the parameters θ * S for cloning the cumulative numerator of average strategy can be optimized in the same way. Based on the learned θ * R and θ * S , we can warm start the double neural networks and continually improve beyond the tabular strategy profile.

Remark: In the large extensive game, the initial strategy is obtained from an abstracted game which has a manageable number of information sets. The abstracted game is generated by domain knowledge, such as clustering similar hand strength cards into the same buckets. Once the strategy of this abstract game is solved, it can be clone according to Eq. ( 10) and improved continuously using our double neural CFR framework.

3.4. OVERALL ALGORITHM:

Algorithm 1 provides a summary of the proposed double neural counterfactual regret minimization algorithm. In the first iteration, if the system warm starts from tabular based CFR or MCCFR methods, the techniques in section 3.3 will be used to clone the cumulative regrets and strategy. If there is no warm start initialization, we can start our algorithm by randomly initializing the parameters in RSN and ASN at iteration t = 1. Then sampling methods will return the counterfactual regret and the numerator of average strategy for the sampled information sets in this iteration, and they will be saved in memories M R and M S respectively. Then these samples will be used by the NeuralAgent algorithm from Algorithm 2 to optimize RSN and ASN. Further details for the sampling methods and the NeuralAgent fitting algorithm will be discussed in the next section. sum aggregate the value in M R by information set.

For t = 1 to T do if t =

according to the Lemma 5 and Equation 12remove duplicated records in M S .

θ t R ← NeuralAgent(R(•|θ t-1 R ), M R , θ t-1 R , β * R ) update θ t R using Algorithm2 θ t S ← NeuralAgent(S(•|θ t-1 S ), M S , θ t-1 S , β * S ) update θ t S using Algorithm2 return θ t R , θ t S

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-based methods.

4.1. ROBUST SAMPLING TECHNIQUES:

In this paper, we proposed a new robust sampling technique which has lower variance than outcome sampling, while being more memory efficient than the external sampling. In this robust sampling method, the sampling profile is defined as σ rs(k) = (σ

rs(k) i , σ -i ),

where player i will randomly select k actions according to sampling strategy σ rs(k) i (I i ) for each information set I i and other players will randomly select one action according to strategy σ -i . Specifically, if player i randomly selects min(k, |A(I i )|) actions according to discrete uniform distribution unif (0, |A(I i )|) at information set I i , i.e., σ rs(k) i

EQUATION

and the weighted utility u rs(k) i

(z) will be a constant number in each iteration, which has a low variance. In addition, because the weighted utility no longer requires explicit knowledge of the opponent's strategy, we can use this sampling method for online regret minimization. For simplicity, k = max refers to k = max Ii∈I |A(I i )| in the following sections.

Lemma 3: If k = max and ∀i ∈ N, ∀I i ∈ I i , ∀a ∈ A(I i ), σ rs(k) i (a|I i ) ∼ unif (0, |A(I i )|)

, then robust sampling is the same as external sampling.

Lemma 4: If k = 1 and σ rs(k) i = σ i , then robust sampling is the same as outcome sampling.

Lemma 3 and Lemma 4 provide the relationship between outcome sampling, external sampling, and the proposed robust sampling algorithm. The detailed theoretical analysis are presented in Appendix G.2.

4.2. MINI-BATCH TECHNIQUES:

Mini-batch MCCFR: Traditional outcome sampling and external sampling only sample one block in an iteration and provide an unbiased estimator of origin CFV according to Lemma 2. In this paper, we present a mini-batch Monte Carlo technique and randomly sample b blocks in one iteration. Let Q j denote a block of terminals sampled according to the scheme in section 4.1 at j-th time, then mini-batch CFV with b mini-batches for information set I i can be defined as

EQUATION

Under review as a conference paper at ICLR 2019 Furthermore, we can show that ṽσ i (I i |b) is an unbiased estimator of the counterfactual value of I i : Lemma 5:

E Q j ∼Robust Sampling [ṽ σ i (I i |b)] = v σ i (I i ).

(see the proof in section G.3) Similarly, the cumulative mini-batch regret of action a is

EQUATION

where R0 i ((a|I i )|b) = 0. In practice, mini-batch technique can sample b blocks in parallel and help MCCFR to converge faster.

Mini-Batch MCCFR+: When optimizing counterfactual regret, CFR+ (Tammelin, 2014) substitutes the regret-matching algorithm (Hart & Mas-Colell, 2000) with regret-matching+ and can converge faster than CFR. However, Burch (2017) showed that MCCFR+ actually converge slower than MCCFR when mini-batch is not used. In our paper, we derive mini-batch version of MCCFR+ which updates cumulative mini-batch regret RT,+ ((a|I i )|b) up to iteration T by

EQUATION

where (x) + = max(x, 0). In practice, we find that mini-batch MCCFR+ converges faster than mini-batch MCCFR when specifying a suitable mini-batch size.

5. EXPERIMENT:

The proposed double neural CFR algorithm will be evaluated in the One-Card-Poker game with 5 cards and a large No-Limit Leduc Hold'em (NLLH) with stack size 5, 10, and 15. The largest NLLH in our experiment has over 2 × 10 7 states and 3.7 × 10 6 information sets. We will compare it with tabular CFR and deep reinforcement learning based method such as NFSP. The experiments show that the proposed double neural algorithm can converge to comparable results produced by its tabular counterpart while performing much better than deep reinforcement learning method. With the help of neural networks, our method has a strong generalization ability to converge to an approximate Nash equilibrium by using fewer parameters than the number of information sets. The current results open up the possibility for a purely neural approach to directly solve large IIG. Due to space limit, we present experimental results for One-Card-Poker and the analysis in section C. The hyperparameters and setting about the neural networks can be found in section E.

Settings. To simplify the expression, the abbreviations of different methods are defined as follows.

XFP refers to the full-width extensive-form fictitious play method. NFSP refers to the reinforcement learning based fictitious self-play method. RS-MCCFR refers to the proposed robust sampling MCCFR. This method with regret matching+ acceleration technique is denoted by RS-MCCFR+.

These methods only containing one neural network are denoted by RS-MCCFR+-RSN and RS-MCCFR+-ASN respectively. RS-MCCFR+-RSN-ASN refers to the proposed double neural MCCFR. According to Lemma 3, if k = max, ES-MCCFR is the same with RS-MCCFR. More specifically, we investigated the following questions.

Is mini-batch sampling helpful? Figure 3 (A) presents the convergence curves of the proposed robust sampling method with k = max under different mini-batch sizes (b=1, 1000, 5000, 10000 respectively). The experimental results show that larger batch sizes generally lead to better strategy profiles. Furthermore, the convergence for b = 5000 is as good as b = 10000. Thus in the later experiments, we set the mini-batch size equal to 5000.

Is robust sampling helpful? Figure 3 (B) and (C) presents convergence curves for outcome sampling, external sampling(k = max) 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 and 5 have a similar trend with k = max, which demonstrates that the proposed robust sampling achieves similar strategy profile but requires less memory than the external sampling. We choose k = 3 for the later experiments in Leduc Hold'em Poker. Figure 3 (C) presents the results in a different way and displays the relation between exploitability and the cumulative number of touched nodes. The robust sampling with small k is just as good as the external sampling while being more memory efficient on the condition that each algorithm touches the same number of nodes. How does double neural CRF compare to the tabular counterpart, XFP, and NFSP? To obtain an approximation of Nash equilibrium, Figure 4 (A) demonstrates that NFSP needs 10 6 iterations to reach a 0.06-Nash equilibrium, and requires 2 × 10 5 state-action pair samples and 2 × 10 6 samples for supervised learning respectively. The XFP needs 10 3 iterations to obtain the same exploitability, however, this method is the precursor of NFSP and updated by a tabular based full-width fictitious play. Our proposed neural method only needs 200 iterations to achieve the same performance which shows that the proposed double neural algorithm converges significantly better than the reinforcement learning counterpart. In practice, our double neural method can achieve an exploitability of 0.02 after 1000 iterations, which is similar to the tabular method.

What is the individual effect of RSN and ASN? Figure 4 (B) presents ablation study of the effects of RSN and ASN network respectively. Both MCCFR+-RSN and MCCFR+-ASN, which only employ one neural network, perform only slightly better than the double neural method. All the proposed neural methods can match the performance of the tabular based method.

How well does continual improvement work? In practice, we usually want to continually improve our strategy profile from an existing checkpoint (Brown & Sandholm, 2016) . In the framework of the proposed neural counterfactual regret minimization algorithm, warm starting is easy and friendly. Firstly, we employ two neural networks to clone the existing tabular based cumulative Do the neural networks generalize to unseen information sets? To investigate the generalization ability, we perform the neural CFR with small mini-batch sizes (b=50, 100, 500), where only 3.08%, 5.59%, and 13.06% information sets are observed in each iteration. In all these settings, the double neural can still converge and arrive at exploitability less than 0.1 within only 1000 iterations (Figure 5(A) ).

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 in NLLH(5), both of which are much less than the tabular memory (more than 10 4 number here). Note that both these two embedding sizes still leads to a converging strategy profile as shown in Figure 5(B) .

Does neural method converge in the larger game? Figure 5 (C) presents the log-log convergence curve of NLLH with different stack size (5, 10 and 15 respectively). The largest game size contains over 2 × 10 7 states and 3.7 × 106 information sets. Let mini-batch size be 500, there are 13.06%, 2.39% and 0.53% information sets that are observed respectively in each iteration. Even though only a small subset of nodes are sampled, the double neural method can still converge.

Is attention in the neural architecture helpful? Figure 5 (D) presents the convergence curves of several different deep neural architectures, such as a fully connected deep neural network(FC), LSTM, LSTM plus attention, original RNN plus attention, and GRU plus attention. The recurrent neural network plus attention helps us obtain better strategies rate than other architectures after hundreds of iterations.

APPENDIX A GAME RULES:

Leduc Hold'em a two-players IIG of poker, which was first introduced in (Southey et al., 2012) . In Leduc Hold'em, there is a deck of 6 cards comprising two suits of three ranks. The cards are often denoted by king, queen, and jack. In No-Limit Leduc Hold'em(NLLH), the player may wager any amount of chips up to a maximum of that player's remaining stack. There is also no limit on the number of raises or bets in 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, a community (or public) card is revealed from a deck of the remaining 4 cards. In this paper, we use NLLH(x) refer to the No-Limit Leduc Hold'em, whose stack size is x.

One-Card Poker is a two-players IIG of poker described by (Gordon, 2005) . The game rules are defined as follows. Each player is dealt one card from a deck of X cards. 

B.1 ADDITIONAL DEFINITIONS:

For player i, the expected game utility u σ i = z∈Z π σ (z)u i (z) of σ is the expected payoff of all possible terminal nodes. Given a fixed strategy profile σ -i , any strategy σ * i = max σ i ∈Σi u

(σ i ,σ-i) i

of player i that achieves maximize payoff against π σ -i is a best response. For two players' extensive-form games, a Nash equilibrium is a strategy profile σ * = (σ * 0 , σ * 1 ) such that each player's strategy is a best response to the opponent. An -Nash equilibrium is an approximation of a Nash equilibrium, whose strategy profile σ * satisfies: ∀i ∈ N , u

σ * i i + ≥ max σ i ∈Σi u (σ i ,σ-i) i . Exploitability of a strategy σ i is defined as i (σ i ) = u σ * i -u (σi,σ * -i ) i . A strategy is unexploitable if i (σ i ) = 0.

In large two player zero-sum games such poker, u σ * i is intractable to compute. However, if the players alternate their positions, the value of a pair of games is zeros, i.e., u σ * 0 + u σ * 1 = 0 . We define the exploitability of strategy profile σ as (σ) = (u

(σ0,σ * 1 ) 1 + u (σ * 0 ,σ1) 0 )/2.

B.2 EXPLANATION BY EXAMPLE:

To provide a more detailed explanation, Figure 6 presents an illustration of a partial game tree in One-Card 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. z i denotes terminal node and h i denotes non-terminal node. There are 19 distinct nodes, corresponding 9 non-terminal nodes including chance h 0 and 10 terminal nodes in the left tree. The trajectory from the root to each node is a history of actions. In an extensive-form game, h i refers to this history. For example, h 3 consists of actions 0:Q, 1:J and P.

Under review as a conference paper at ICLR 2019 h 7 consists of actions 0:Q, 1:J, P and B. h 8 consists of actions 0:Q, 1:K, P and B. We have h 3 h 7 , A(h 7 ) = {P, B} and P (h 3 ) = 1

In IIG, the private card of player 1 is invisible to player 0, therefore h 7 and h 8 are actually the same for player 0. We use information set to denote the set of these undistinguished states. Similarly, h 1 and h 2 are in the same information set. For the right tree of Figure 6 , h 3 and h 5 are in the same information set. h 4 and h 6 are in the same information set.

Generally, any I i ∈ I could only remember the information observed by player i including player i s hidden variable and public actions. For example, the information set of h 7 and h 8 indicates a sequence of 0:Q, P, and B. Because h 7 and h 8 are undistinguished by player 0 in IIG, all the states have a same strategy. For example, I 0 is the information set of h 7 and h 8 , we have

I 0 = I 0 (h 7 ) = I 0 (h 8 ), σ 0 (I 0 ) = σ 0 (h 7 ) = σ 0 (h 8 ), σ 0 (a|I 0 ) = σ 0 (a|h 7 ) = σ 0 (a|h 8 ).

APPENDIX C ADDITIONAL EXPERIMENT DETAILS C.1 FEATURE ENCODING OF POKER GAMES:

The feature is encoded as following. As shown in the figure 2 (A) , for a history h and player P (h), we use one-hot encoding (Harris & Harris) to represent the observed actions including chance player. For example, the input feature x l for l-th cell is 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, where the value in the existing position is 1 and the others are 0. If there are no public cards, the respective position will be filled with 0. Because the action taking by chance is also a cell in the proposed sequential model. Thus in a No-Limit poker, such as Leduc Hold'em, action a could be any element in {fold, cumulative spent}∪ {public cards} , where cumulative spent denotes the total chips after making a call or raise. The length of the encoding vector of action a is the quantities of public cards plus 2, where cumulative spent is normalized by the stack size. Figure 7 (B) demonstrates that the convergence rate for different sampling methods including outcome sampling and robust sampling under k = 1, 2. The conclusion is that RS-MCCFR+ converges significantly faster than OS-MCCFR+ after touching the same number of nodes. Experiment results show that k = 1 has a similar trend with k = 2 (external sampling). Because only one trajectory is sampled, the proposed RS-MCCFR+ will require less memory than the external sampling.

C.2 ADDITIONAL EXPERIMENT RESULTS:



A B C:

Figure 7 (C) compares the performance between the tabular method and the double neural method.

Experimental results demonstrate that RS-MCCFR+-RSN-ASN can achieve an exploitability of less than 0.0004 in One-Card Poker, which matches the performance of the tabular method. For RSN and ASN, we set neural batch size 4, hidden size 32 and learning rate 0.001.

APPENDIX D DETAILS OF RECURRENT NEURAL NETWORK:

In order to define our R and S network, we need to represent the information set I i ∈ I in extensive-form games. In such games, players take action in alternating fashion and each player makes a decision according to the observed history. In this paper, we model the behavior sequence as a recurrent neural network and each action in the sequence corresponds to a cell in RNN.

Figure 2 (A) provides an illustration of the proposed deep sequential neural network representation for information sets.

In standard RNN, the recurrent cell will have a very simple structure, such as a single tanh or sigmoid layer. Hochreiter & Schmidhuber (1997) proposed a long short-term memory method (LSTM) with the gating mechanism, which outperforms the standard version and is capable of learning long-term dependencies. Thus we will use LSTM for the representation. Furthermore, different position in the sequence may contribute differently to the decision making, we will add an attention mechanism (Desimone & Duncan, 1995; Cho et al., 2015) to the LSTM architecture to enhance the representation. For example, the player may need to take a more aggressive strategy after beneficial public cards are revealed. Thus the information, after the public cards are revealed may be more important.

More specifically, for l-th cell, define x l as the input vector (which can be either player or chance actions), e l as the hidden layer embedding, φ * as a general nonlinear function. Each action is represented by a LSTM cell, which has the ability to remove or add information to the cell state with three different gates. Define the notation • as element-wise product. The first forgetting gate layer is defined as g f l = φ f (w f [x l , e l-1 ]), where [x l , e l-1 ] denotes the concatenation of x l and e l-1 . The second input gate layer decides which values to update and is defined as g i l = φ i (w i [x l , e l-1 ]). A nonlinear layer output a vector of new candidate values Cl = φ c (w l [x l , e l-1 ]) to decide what can be added to the state. After the forgetting gate and the input gate, the new cell state is updated by

C l = g f l • C l-1 + g i l •

Cl . The third output gate is defined as g o l = φ o (w o [x l , e l-1 ]). Finally, the updated hidden embedding is e l = g o l • φ e (C l ). As shown in Figure 2 (A), for each LSTM cell j, the vector of attention weight is learned by an attention network. Each member in this vector is a scalar α j = φ a (w a e j ). The attention embedding of l-th cell is then defined as e a l = l j=1 α j • e j , which is the summation of the hidden embedding e j and the learned attention weight α j . The final output of the network is predicted by a value network, which is defined as

EQUATION

)

where θ is the parameters in the defined sequential neural networks. return θ T sets of hyperparameters in RSN and ASN respectively. According to our experiments, we find a carefully designed optimization method can help us obtain a relatively higher convergence rate of exploitability. Algorithm 2 presents the details of how to optimize the proposed neural networks.

{x (i) , y (i) } m i=1 ∼ M sampling a mini-batch from M batch loss ← 1 m m i=1 (f (x (i) |θ T -1 ) + y (i) -f (x (i) |θ T ))

Both R(a, I i |θ t+1 R ) and S(a, I i |θ t S ) are optimized by mini-batch stochastic gradient descent method. In this paper, we use Adam optimizer (Kingma & Ba, 2014) with both momentum and adaptive learning rate. Some other optimizers such as Nadam, RMSprop, Nadam from (Ruder, 2017) are also tried in our experiments, however, they do not achieve better experimental results. In practice, existing optimizers may not return a relatively low enough loss because of potential saddle point or local minima. To obtain a relatively higher accuracy and lower optimization loss, we use a carefully designed scheduler to reduce the learning rate when the loss has stopped decrease. Specifically, the scheduler reads a metrics quantity, e.g, mean squared error, and if no improvement is seen for a 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 decrease in β re epochs. Gradient clipping mechanism is used to limit the magnitude of the parameter gradient and make optimizer behave better in the vicinity of steep cliffs. After each epoch, the best parameter will be updated. Early stopping mechanism is used once the lowest loss is less than the specified criteria β loss .

In experiments, we set the network hyperparameters as follow. For RSN, we set the hyperparameters as follows: neural batch size is 256 and learning rate β lr = 0.001. A scheduler, who will reduce the learning rate based on the number of epochs and the convergence rate of loss, help the neural agent to obtain a high accuracy. The learning rate will be reduced by 0.5 when loss has stopped improving after 10 epochs. The lower bound on the learning rate of all parameters in this scheduler is 10 -6 . To avoid the algorithm converging to potential local minima or saddle point, we will reset the learning rate to 0.001 and help the optimizer to learn a better performance. θ T best is the best parameters to achieve the lowest loss after T epochs. If average loss for epoch t is less than the specified criteria β loss =10 -4 , we will early stop the optimizer. We set β epoch = 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. Other hyperparameters in ASN are similar to RSN.

v i (a|h) ←MCCFR-NN(t, ha, i, π i σ i (a|I i ), π rs i σ rs(k) i (a|I i )) 22 v i (h) ← v i (h) + v i (a|h)σ i (a|I i ) update counterfactual value For a ∈ A rs(k) (I i ) do 24 r i (a|I i ) ← v i (a|h) -v i (h) update cumulative regret 25 s i (a|I i ) ← π σ i (I i )σ i (a|I i ) update average strategy numerator Store updated cumulative regret tuple (I i , r i (•|I i )) in M R Store updated current strategy dictionary (I i , s i (•|I i )) in M S else R-i (•|I i ) ← R(•, I i |θ t R ) if t > 1 else - → 0 inference cumulative regret σ -i (I i ) ←CalculateStrategy( R-i (•|I i ), I i ) calculate current strategy a ∼ σ -i (I i ) Sample an action from σ-i(Ii) return MCCFR-NN(t, ha, i, π i , π rs(k) i ) Function CalculateStrategy(R i (•|I i ), I i ): sum ← a∈A(Ii) max(R i (a|I i ), 0) For a ∈ A(I i ) do σ i (a|I i ) = max(Ri(a|Ii),0) sum if sum > 0 else 1 |A(Ii)| return σ i (I i )

Algorithm 3 presents one application scenario of the proposed double neural method, which is based on the proposed mini-batch robust sampling method. The function MCCFR-NN will traverse the game tree like tabular MCCFR, which starts from the root history h = ∅. Define I i as the information set of h. Suppose that player i will sample k actions according to the robust sampling. Then the function can be defined as follows.

(1) If the history is terminal, the function returns the weighted utility.

(2) If the history is the chance player, one action a ∈ A(I i ) will be sampled according to the strategy σ -i (I i ). Then this action will be added to the history, i.e., h ← ha.

(3) If P (I i ) = i, the current strategy can be updated by the cumulative regret predicted by RSN. Then we sample k actions according the specified sampling strategy profile σ rs(k) i

. After a recursive updating, we can obtain the counterfactual value and regret of each action at I i . For the visited node, their counterfactual regrets and numerators of the corresponding average strategy will be stored in M R and M S respectively. (4) If P (I i ) is the opponent, only one action will be sampled according the strategy σ -i (I i ).

The function Mini-Batch-MCCFR-NN presents a mini-batch sampling method, where b blocks will be sampled in parallel. This mini-batch method can help the MCCFR to achieve a more accurate estimation of CFV. The parallel sampling makes this method efficient in practice.

APPENDIX G THEORETICAL ANALYSIS G.1 REACH PROBABILITY AND POSTERIOR PROBABILITY:

Lemma 1: The state reach probability of one player is proportional to posterior probability of the opponent's hidden variable, i.e., p(h v -i |I i ) ∝ π σ -i (h). Proof: For player i at information set I i and fixed i s strategy profile σ i , i.e., ∀h ∈ I i , π σ i (h) is constant. Based on the defination of extensive-form game in Section 2.1, the cominbation of I i and opponent's hidden state h v -i can indicate a particular history h = h v i h v -i a 0 a 1 ...a L-1 . With Bayes' Theorem, we can inference the posterior probability of opponent's private cards with Equation16 For robust sampling, given strategy profile σ and the sampled block Q j according to sampling profile σ rs(k) = (σ rs(k) i , σ -i ), then q(z) = π σ rs(k) i (z)π σ -i (z), and the regret of action a ∈ A rs(k) (I i ) is 

EQUATION

rσ i ((a|I i )|Q j ) = ṽσ i ((a|I i )|Q j ) -ṽσ i (I i |Q j ) = z∈Qj ,ha z,h∈Ii 1 q(z) π σ -i (z)π σ i (ha, z)u i (z) - z∈Qj ,h z 1 q(z) π σ -i (z)π σ i (h, z)u i (z)

For a ∈ A rs(k) (I i ), the regret will be rσ i ((a|h)|j) = 0 -ṽσ i (h|j). Therefore, robust sampling is same with outcome sampling when k = 1 and σ rs(k) i = σ i .

• if k = 1, and player i randomly selects one action according to discrete uniform distribution unif (0, |A(I i )|) at information set I i , then u 

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

G.3 MINI-BATCH MCCFR GIVES AN UNBIASED ESTIMATION OF COUNTERFACTUAL VALUE:

Lemma 5: E Q j ∼Robust Sampling [ṽ σ i (I i |b)] = v σ i (I i ).

Proof: 

E Q j ∼Robust

EQUATION

:

CONCLUSION AND FUTURE WORKIn this paper, we present a novel double neural counterfactual regret minimization method to solve large imperfect information game, which has a strong generalization and compression ability and can match the performance of tabular based CFR approach. We also developed a new sampling technique which has lower variance than the outcome sampling, while being more memory efficient than the external sampling. In the future, we plan to explore much more flexible methods and apply the double neural method to larger games, such as No-Limit Texas Hold'em.

Figures and Tables:

Figure 1: (A) tabular based CRF and (B) our double neural based CRF framework.

Figure 2: (A) the key architecture of the sequential neural networks. (B) an overview of the novel double neural counterfactual regret minimization method.

Counterfactual Regret Minimization with Two Deep Neural Networks Function Agent(T , b):

Figure 3: Comparison of different CFR-family methods in Leduc Hold'em. (A) Performance of robust sampling with different batch size. (B) Performance of robust sampling with different parameter k by iteration. (C) Performance by the number of touched node.A B C

Figure 5: Performance analysis from different perspectives: (A) Generalization: by observed nodes. (B) Compression: by embedding size. (C) Large Game: by game size. (D) Architecture: by attention or not.

Figure 7: Comparison of different CFR-family methods and neural network methods in One-Card-Poker. (A) Comparison of the robust sampling with different mini-batch size. (B) Comparison of the outcome sampling and the robust sampling with different sample actions k. (C) Comparison of tabular based RS-MCCFR+ and the double neural method.

Figure 7 (A) presents the convergence rate for the proposed robust sampling method of different mini-batch size b = (1, 100, 500, 1000). The experimental results are similar to Leduc Hold'em poker, larger mini-batch size indicates a better exploitability.

ROBUST SAMPLING, OUTCOME SAMPLING AND EXTERNAL SAMPLING Lemma 3: If k = max Ii∈I |A(I i )| and ∀i ∈ N, ∀I i ∈ I i , ∀a ∈ A(I i ), σ rs(k) i (a|I i ) ∼ unif (0, |A(I i )|), then robust sampling is same with external sampling. (see the proof in section G.2) Lemma 4: If k = 1 and σ rs(k) i = σ i , then robust sampling is same with outcome sampling. (see the proof in section G.2)

i (z) = ui(z) π σ rs(k) i (z)is the weighted utility according to reach probability π σ rs(k) i (z). Because the weighted utility no long requires explicit knowledge of the opponent's strategy, we can use this sampling method for online regret minimization.Generally, if player i randomly selects min(k, |A(I i )|) actions according to discrete uniform distribution unif (0, |A(I i )|) at information set I i , i.e., σ rs(k) i(a|I i ) = min(k,|A(Ii)|) h,h a h,h ∈I i min(k, |A(I i )|) |A(I i )|(18)and u rs i (z) is a constant number when given the sampling profile σ rs(k) . Specifically,• if k = max Ii∈I |A(I i )|, then σ rs(k) i (I i ) = 1, u rs(k) i (z) = u i (z),andrσ i ((a|I i )|Q j ) = z∈Qj ,h z,h∈Ii u i (z)(π σ i (ha, z) -π σ i (h, z))(19)Therefore, robust sampling is same with external sampling when k = max Ii∈I |A(I i )|.• if k = 1 and σ rs(k) i = σ i , only one history z is sampled in this case,then u ) , ∃h ∈ I i , for a ∈ A rs(k) (I i ) rσ i ((a|I i )|Q j ) = rσ i ((a|h)|Q j ) =

, ∃h ∈ I i , for a ∈ A rs(k) (I i ) rσ i ((a|I i )|Q j ) =

Sampling [ṽ σ i (I i |b)] = E b ∼unif(0,b) [ṽ σ i (I i |b )] = E b ∼unif(0, b)

is a new utility weighted by . The sample estimate for cumulative regret of action a after T iterations is RT i ((a|I i )|Q j ) = RT -1

Table content: <table><tr><td colspan="8">R0 i ((a|I i )|Q j ) = 0.</td><td/><td/><td/><td/><td/><td/><td colspan="2">1 π σ rs i</td><td colspan="2">(z) i</td><td>((a|I i )|Q j ) + rσ T i ((a|I i )|Q j ) with</td></tr><tr><td colspan="18">3 DOUBLE NEURAL COUNTERFACTUAL REGRET MINIMIZATION</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>Regret Matching</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>Regret Matching</td></tr><tr><td>𝑎3</td><td>𝐼2</td><td>𝑎1 𝑎4</td><td>𝐼 1</td><td>𝑎2 𝑎5</td><td>𝐼3</td><td>𝑎6</td><td colspan="3">𝑅 𝑖 𝑡-1 (𝑎|𝐼𝑖) + 𝑅 𝑖 𝑡 (𝑎|𝐼𝑖) 𝑆 𝑖 𝑡-1 (𝑎|𝐼𝑖) 𝜎 𝑡 ((𝑎|𝐼𝑖)|𝑄𝑗) 𝑟 𝑖</td><td>𝑞𝑢𝑒𝑟𝑦 𝑞𝑢𝑒𝑟𝑦 all 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑠𝑒𝑡𝑠</td><td>𝑎3</td><td>𝐼2</td><td>𝑎4 𝑎1</td><td>𝐼 1</td><td colspan="2">𝑎5 𝑎2</td><td>𝐼3</td><td>𝑎6</td><td>+ RegretSumNetwork 𝑞𝑢𝑒𝑟𝑦 descent 𝑠𝑎𝑚𝑝𝑙𝑒𝑑 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑠𝑒𝑡𝑠 gradient 𝜎 𝑡 ((𝑎|𝐼𝑖)|𝑄𝑗) 𝑟 𝑖</td></tr><tr><td>𝑧1</td><td/><td>𝐼4</td><td/><td>𝑧2</td><td/><td>𝑧3</td><td>𝑠 𝑖 𝑡 (𝑎|𝐼𝑖)</td><td>+</td><td>𝑆 𝑖 𝑡 (𝑎|𝐼𝑖)</td><td/><td>𝑧1</td><td/><td>𝐼4</td><td/><td colspan="2">𝑧2</td><td>𝑧3</td><td>𝑠 𝑖 𝑡 (𝑎|𝐼𝑖)</td><td>AvgStrategyNetwork</td></tr><tr><td/><td colspan="2">𝑧4 𝑎7</td><td>𝑧5 𝑎8</td><td/><td/><td/><td colspan="3">Tabular Method</td><td>all 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑠𝑒𝑡𝑠</td><td/><td colspan="2">𝑧4 𝑎7</td><td>𝑧5 𝑎8</td><td/><td/><td>Neural Method 𝑠𝑎𝑚𝑝𝑙𝑒𝑑 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑠𝑒𝑡𝑠</td><td>+</td><td>gradient descent</td></tr></table>

1 and using warm starting then R , M S ← sampling methods for CFV and average strategy.

Table content: <table><tr><td>4</td><td>initialize θ t R and θ t S from an existing checkpoint</td><td/></tr><tr><td>5</td><td>t ← t + 1</td><td>skip cold starting</td></tr><tr><td/><td>else</td><td/></tr><tr><td/><td>initialize θ t R and θ t S randomly.</td><td/></tr><tr><td/><td/><td>such as Algorithm3</td></tr></table>

The first player can pass or bet, If the first player bet, the second player can call or fold. If the first player pass, the second player can pass or bet. If second player bet, the first player can fold or call. The game ends with two pass, call, fold. The fold player will lose 1 chips. If the game ended with two passes, the player with higher card win 1 chips, If the game end with call, the player with higher card win 2 chips.

Table content: <table><tr><td colspan="12">APPENDIX B DEFINITION OF EXTENSIVE-FORM GAMES</td><td/><td/><td/><td/></tr><tr><td colspan="2">player 0 player 1</td><td/><td>𝒉 𝟎</td><td/><td/><td/><td/><td/><td/><td/><td>𝒉 𝟎</td><td/><td/><td/><td/></tr><tr><td colspan="2">chance</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>𝒉 𝟏</td><td/><td/><td/><td>𝒉 𝟐</td><td/><td/><td/><td>𝒉′ 𝟏</td><td/><td/><td/><td>𝒉′ 𝟐</td><td/><td/></tr><tr><td/><td>P</td><td>B</td><td/><td/><td>P</td><td>B</td><td/><td colspan="2">P</td><td>B</td><td/><td/><td>P</td><td>B</td><td/></tr><tr><td>ℎ 3</td><td/><td>ℎ 4</td><td/><td>𝒉 𝟓</td><td/><td>𝒉 𝟔</td><td/><td>𝒉′ 𝟑</td><td/><td>𝒉′ 𝟒</td><td/><td>𝒉′ 𝟓</td><td/><td>𝒉′ 𝟔</td><td/></tr><tr><td>P</td><td>B</td><td>F</td><td>C</td><td>P</td><td>B</td><td>F</td><td>C</td><td>P</td><td>B</td><td>F</td><td>C</td><td>P</td><td>B</td><td>F</td><td>C</td></tr><tr><td>𝒛 𝟏</td><td>𝒉 𝟕</td><td>𝒛 𝟐</td><td>𝒛 𝟑</td><td>𝒛 𝟒</td><td>𝒉 𝟖</td><td>𝒛 𝟓</td><td>𝒛 𝟔</td><td>𝒛′ 𝟏</td><td>𝒉′ 𝟕</td><td>𝒛′ 𝟐</td><td>𝒛′ 𝟑</td><td>𝒛′ 𝟒</td><td>𝒉′ 𝟖</td><td>𝒛′ 𝟓</td><td>𝒛′ 𝟔</td></tr><tr><td>F</td><td>C</td><td/><td/><td>F</td><td>C</td><td/><td/><td>F</td><td>C</td><td/><td/><td>F</td><td>C</td><td/><td/></tr><tr><td>𝒛 𝟕</td><td>𝒛 𝟖</td><td/><td/><td>𝒛 𝟗</td><td>𝒛 𝟏𝟎</td><td/><td/><td>𝒛′ 𝟕</td><td>𝒛′ 𝟖</td><td/><td/><td>𝒛′ 𝟗</td><td>𝒛′</td><td/><td/></tr></table>

Specifically, φ f , φ i , φ o are sigmoid functions. φ c and φ e are hyperbolic tangent functions. φ a and φ v are rectified linear functions. The proposed RSN and ASN share the same neural architecture, but use different parameters. That is R(a,I i |θ t R ) = f (a, I i |θ t R ) and S(a, I i |θ t S ) = f (a, I i |θ t S ). R(•, I i |θ t R ) and S(•, I i |θ t S )denote two vectors of inference value for all a ∈ A(I i ).APPENDIX E NEURAL AGENT FOR OPTIMIZING NEURAL REPRESENTATIONDefine β epoch as training epoch, β lr as learning rate, β loss as the criteria for early stopping, β re as the upper bound for the number of iterations from getting the minimal loss last time, θ t-1 as the parameter to optimize, f (•|θ t-1 ) as the neural network, M as the training sample consisting information set and the corresponding target. To simplify notations, we use β * to denote the set of hyperparameters in the proposed deep neural networks. β * R and β * S refer to the θ T ← θ T -1 , l best ← ∞, t best ← 0 warm starting from the checkpoint of the last iteration

Table content: <table><tr><td>4</td><td>For t = 1 to β epoch do</td><td/></tr><tr><td>5</td><td>loss ← []</td><td>initialize loss as an empty list</td></tr><tr><td>6</td><td>For each training epoch do</td><td/></tr><tr><td>7</td><td/><td/></tr></table>

loss is small enough, using early stopping mechanism. else if avg(loss) < l best then l best = avg(loss), t best ← t, θ T best ← θ T if t -t best > β re then lr ← β lr reset learning rate to escape from potential saddle point or local minima.

Table content: <table><tr><td/><td/><td>2</td></tr><tr><td>9</td><td colspan="2">back propagation batch loss with learning rate lr</td></tr><tr><td/><td>clip gradient of θ T to [-, ] d</td><td>d is the dimension of θ T</td></tr><tr><td/><td>optimizer(batch loss)</td></tr><tr><td/><td>loss.append(batch loss)</td></tr><tr><td/><td>lr ← sheduler(lr)</td><td>reduce learning rate adaptively when loss has stopped improving</td></tr><tr><td/><td>if avg(loss) &lt; β loss then</td></tr><tr><td/><td>θ T best ← θ T , early stopping.</td></tr></table>

Peer review (iclr2019):
 ========= Summary ========= The authors propose "Double Neural CFR", which uses neural network function approximation in place of the tabular update in CFR. CFR is the leading method for finding equilibria in imperfect information games. However it is typically employed with a tabular policy, limiting its applicability large games. Typically, hand-crafted abstractions are employed for games that are too large for exact tabular solutions. Function approximation could remove the necessity for hand-crafted abstractions and allow CFR to scale to larger problems. The DN-CFR algorithm roughly consists of: - start with an arbitrary vmodel_0, smodel_0 for t = 0,1,2,3: - collect a "batch" of (infoset I, immediate counterfactual value v_I) samples by traversal against vmodel_t (as well as I, strategy samples) - train a new network vmodel_{t+1} on this "batch" with y=(v_I + vmodel_t(I)) and MSE loss - similarly for (I, strategy) - return smodel_t The authors also propose a novel MC samping strategy this is a mixture between outcome and external sampling. DN-CFR is evaluated on two games: a variant of Leduc hold-em with stack size 5, and one-card poker with 5 cards. If I understand correctly, these games have <10,000 and <100 infosets, respectively. The authors show that DN-CFR achieves similar convergence rates to tabular CFR, and outperform NFSP variants. ========== Comments ======== The authors are exploring an important problem that is of great interest to the IIG community. Their application of NN function approximation is reasonable and mostly theoretically well-grounded (but see below), I think it*s on the right track. However, the games that are used for evaluation are very small, in fact I believe they have fewer states than the number of parameters in their network (the number of network parameters is not provided but I assume >1000). As a result, the NN is not providing any compression or generalization, and I would expect that the network can memorize the training set data exactly, i.e. predict the exact mean counterfactual value for each infoset over the data. If that*s true, then DN-CFR is essentially exactly replicating tabular CFR (the approximation serves no purpose). As a result, in my opinion this work fails to address the important challenges for function approximation in CFR, namely: - Can function approximation allow for *generalization across infosets* in order to reduce sample complexity of CFR (i.e. an unsupervised abstraction)? Are specific network architectures required for good generalization? - The magnitude of counterfactual regrets in the support of the equilibrium decays to zero relative to dominated actions. Are NN models capable to estimating the regrets accurately enough to converge to a good strategy? - Are optimization methods able to deal with the high variance in large IIGs? - Since each successive approximation is being trained from the previous NN, does this cause errors to accumulate? - How do approximation errors accumulate across CFR iterations? - Is minimizing MSE loss sufficient to approximate the strategy well? (since the mapping from regrets -> strategy is non-linear) I believe there is also a theoretical problem with this algorithm. In Eq. 8, they minimize the loss of CF value predictions *over the distribution of infosets in the last CFR step ("batch")*. However, this distribution may change between CFR iterations, for example if the strat_t folds 2-3 on the preflop then flop infosets with 2-3 hole cards will never be observed on iteration t+1. As a result, the NN loss will only be minimized over infosets observed in the last iteration - so the network will "forget" the regrets for all other infosets. I think this issue does not arise in these toy games because all infosets are observed at each iteration, but this is certainly not the case in real games. There are a number of ways that this issue could be addressed (e.g. train on historical infosets rather than the current batch, etc.) These would need to be explored. I would recommend that the authors evaluate on more complex games to answer the important questions stated above and resubmit. I think this would also make an excellent workshop submission in its current state as it contains many interesting ideas. Detailed comments: "... the original CFR only works for discrete stand and action spaces...": Are the authors implying that DN-CFR addresses this limitation? "Moravk" -> "Moravcik" "...these methods do not explicitly take into account the hidden information in a game..." Could you clarify? Is your point that these methods operate on the normal form rather than extensive form game? "care algorithm design" -> "careful algorithm design" The paragraph starting "In standard RNN..." should be reduced or moved to appendix. The exact NN architecture is not central to the ideas, and there are no experimental comparison with other architectures so we have no evidence that the architecture is relevant.