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 1 by 9.8±4.1 chips per game. It's a successful application of neural CFR in large games.
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.
It 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.
Unlike 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.
In “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
each information set is not equal. You may need to discuss this.
The 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.
Experiments:
1. 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
experiment of “Individual network”, as this experiment is important to show that
DNCFR is comparable to tabular CFR and the bias is acceptable.
2. The paper didn’t show what the learned regret and average strategy looks. If they are
showed, it would be helpful to understand the bias in the bootstrap learning.
3. 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).
4. 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
information sets that trained before.
5. In the part “How well does DNCFR on larger games”, the DNCFR is limited to 100
iterations while is allow to run for 1000 iterations in other experiments. 100 iterations
are too few to show the effectiveness of DNCFR on these games.
6. 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
these games.
7. It is not clear how to combine the blueprint strategy trained by DNCFR with
DeepStack, 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.
8. 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.