Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games
Game Theory;Imperfect Information Games;Counterfactual Regret Minimization;Poker;Machine Learning
Yes
No ethics review needed.
- L300 "each neural network receives a feature describing the information set" --- What exactly comprises the feature? The value of an infoset is not uniquely defined without the context of ranges for a public state. Is this information included?
- Can you please add results where the time limit is increased, up to 2 and 20 seconds, and against DeepStack, for a time budget?
- For the heads-up results, how many matches have been played? Have you considered using AIVAT to reduce variance?
- A simple idea that should be easy to implement and can be generally incorporated into many algorithms, as it mainly concerns a general structural aspect of IIGs.
- Strong performance on poker games.
This paper introduces a method called EVPA, for online pruning and abstraction of imperfect-information games (IIGs) based on an evaluation of information sets, which is trained offline, in a preparation of an online play.
The evaluation is done by a collection of neural networks, to which the same information set is used as input.
The collected values serve as an estimate of minimum, maximum, and average values that can encountered for that information set in online play, when solving a subgame.
By employing a minimax-like pruning, a subgame can be reduced in size, in advance of solving that subgame, which reduces the time needed for the online solving.
This contrasts with algorithms like CFR, for which pruning has been done in prior work. CFR prunes the tree only dynamically, based on the current state of the algorithm, and still requires full subgame at the first iteration. 
Additionally, if the estimates of values for structurally-compatible information sets are similar, they can be merged together. This is similar to bucketing done in prior work.
Finally, EVPA is used for large variants of Poker and its performance is measured empirically against other prior strong algorithms. EVPA can find strong strategies while requiring substantially smaller time to do so.
- The paper offers only empirical results. It makes very little evaluations on choices needed for the offline preparation, and only considers the online parameters like time budget. However, a practitioner has to decide a number of choices for the offline preparation: the number of neural networks, the size of training set, a choice of the delta parameter. It is not clear how the approach is robust to these. While I understand this is computationally expensive, it can be done for some (limited) choices, while not making the budget too high. Looking at appendix, DeepStack (which has been replicated in the paper) training time is 569 days, while EVPA is 74. Spending up to 7x budget on more evaluations thus seems reasonable.

- Establishing theoretical bounds based on the choice of delta and EV estimate errors should not be difficult, but is not present in the paper. However, the approach does seem sound.

- The text is a bit repetitive. Instead, I would appreciate more involved discussion of prior abstraction literature and how this work differs.
Yes
No ethics review needed.
**Detailed questions and comments.** For the three techniques this paper proposes, I have several concerns and questions.

1. Expected value estimation of information sets: How does it compare with the one used in DeepStack? How do you compute Nash of subgame? Is it exact?  One problem of DeepStack is it generates subgames by random sampling, which may not cover the most essential ones. A more advanced one is used in Student of Games which estimates values by considering those encounter during CFR iteration recursively. Have you tried these alternative.


2. Min-max pruning. I don't think min-max pruning is correct in imperfect information games unless you transform the game into public belief tree representation, which you should include public belief states into the value function. However as far as I see the value function you are using are information-set value function, which is incorrect to use min-max pruning because the opponent can change the reach probabilities by changing its action prior to the current information set. However, it you were use min-max pruning for public-belief tree, it will be much more computationally expensive.

3. Abstraction: How often is the abstraction criterion met? How does it compare with previous abstraction techniques such as nested subgame solving in [Brown & Sandholm '17]
The presentation is clear.
***Summary of paper** This paper proposes three techniques to improve CFR: (i) expected value estimation of information sets (ii)expected value-based pruning and (iii)information abstraction for subgames. The authors also gave experimental evaluation against an implementation of DeepStack and SlumBot.
Some technical points are not sound.
Yes
No ethics review needed.
* Can the authors please comment on the quality of Deepstack's replication? How does it perform against local best response (LBR)?

* In the experiments in Table 2, what happens with longer solving times?

* How do we ensure pruning does not severely impact the quality of the final strategy?

* How do we know the method for information abstraction is more applicable to games with large information sets? Or do we specifically mean only Omaha here?
* Pruning and abstraction in the context of scaling CFR is highly relevant to the community. Current methods simply do not scale well beyond some of the traditional applications.
* Significant portions of the game tree are successfully pruned, though it's unclear what that means for correctness.
* The overall approach seems to have gained an order of magnitude speedup over DeepStack in both training and online solving time. This suggests that it could be useful in applications that are more time-sensitive than poker.
The authors introduce EVPA, which is an algorithm for approximating Nash equilibria in two-player zero-sum games based on Counterfactual Regret Minimization. EVPA seeks to improve the runtime efficiency of CFR by pruning sub-optimal actions and abstracting information online. This leads to much faster, high-quality approximations of Nash equilibria compared to a replication of DeepStack in Heads-up no-limit Texas Hold 'em poker.
* The claim that the method for information abstraction reduces "the computational overhead of information abstraction from months to less than 1 second" seems false. The method for information abstraction depends on the expected value of an information set according to an approximation of the equilibrium strategy. This expected value presumably takes a large portion of the 74 training days reported in the appendix. Would it be more correct to rephrase this to explain the algorithm finds new abstractions online in seconds, given estimates of information set EV?

* No theoretical guarantees. It seems that by pruning and abstracting information using the methods presented in this paper, the approach loses the convergence guarantees of DeepStack. Do the authors believe there is a promising avenue to obtain some similar bounds? The empirical results certainly show that EVPA computes strong strategies in this domain, but are there situations where pruning or abstraction like this can have catastrophic effects on performance?

* Application to a domain that has limited room for further progress. Though the speedup and performance are impressive (see comment above), the application to HUNL has the potential to have less impact on the community than if it were applied to new, more challenging domains, where super-human performance has not already been achieved. Can the authors share some insight on what other sorts of domain this approach could have a significant impact? It seems a game with a higher branching factor could be a good candidate.
Yes
No ethics review needed.
* What is the training time for DeepStack’s replication? Table 4 in the appendix shows that DeepStack takes 569 days, while EVPA takes 74 days. Does this 74 days include the training time for DeepStack’s replication, given that EVPA’s expected value estimation relies on the networks in DeepStack’s replication?
* What is the element of a subgame $S$? Line 227 states that $S$ is a set of histories. Line 285 states that an information set $I_p$ is in $S$. Line 368 states that a public state $s(I_p')$ is in $S$. 
* Can you explain the condition 2 in Lines 387-388? Where is $I'$? Why is the condition "$\mathcal{P}(I \cdots a_1 \dots a_i) \ne \mathcal{P}(I)$" needed? 
* Why is the significance function in Lines 421-422 needed? The importance of an information set should increase with the size of the pot, but in the function $f(g(s), n)$ , it decreases instead.
* What are the confidence intervals in Table 1 and Figure 3?
* (Line 545) How EVPA is used for any initial chip count? EVPA is based on DeepStack which relies on specific assumptions about players’ initial chips.
* Will the code be released to assist research in the field?
* The method is intuitive in thought but effective in practice. It achieves a cropping rate of about 75% and allows decisions to be made in less than one second.
* The paper provides good experimental results demonstrating improved performance over Deepstack's replication and Slumbot.
The paper introduces an online pruning and abstraction method for the iterates of CFR. It trains a network to evalute the expected value of information sets under the Nash equilibrium. The network is then used to prune actions with low expected values and to cluster information sets with similar expected values using k-means++ during the online execuration of CFR. The trained agent defeats DeepStack's replication and Slumbot with little solving time.
* The papar lacks experimental comparisons with other pruning and abstraction methods. 
* The method relies on evaluating the expected value of all informaion sets, in contrast to DeepStack, which evalutes the information sets at the end of each round. So it requies collecting "at least 10 billion samples" (Lines 302-303), compared to the milliones of samples needed by Deepstack. This should take a long time. 
* The performance gains from information set abstraction are marginal, and this leads to exploitability not decreasing in the later iterations.
@inproceedings{
anonymous2024efficient,
title={Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=MTcgsz1SHr},
note={under review}
}
Efficiently computing approximate equilibrium strategies in large-scale Imperfect Information Extensive-Form Games (IIEFGs) poses significant challenges due to the vast size of the game trees. Pruning and abstraction methods effectively reduce the size of the game tree and enhance computational efficiency. However, seamlessly integrating pruning techniques with variants of Counterfactual Regret Minimization (CFR), a leading method for solving IIEFGs, remains a complex task. Furthermore, existing information abstraction methods often involve high computational costs and may require months of offline pre-computation, limiting their practical applicability. In this paper, we introduce Expected-Value Pruning and Abstraction (EVPA), an online approach that improves efficiency by leveraging expected value estimation within information sets. EVPA consists of three core components: expected value estimation of information sets, expected value-based pruning, and information abstraction for subgames. It estimates the expected value of information sets using Nash equilibrium strategies, employing these estimations for both pruning and abstraction. By integrating Minimax pruning with CFR, EVPA streamlines decision-making by permanently eliminating sub-optimal actions from the game tree prior to CFR application. Additionally, EVPA features an advanced information abstraction mechanism that merges information sets based on both current and future expected values in the subgame, achieving efficient information abstraction within just $1$ second. Experiments on HUNL demonstrate that EVPA outperforms DeepStack's replication and Slumbot, with win-rates of $202\pm 31$ and $96\pm 43$ mbb/h, respectively. Remarkably, EVPA requires only $1$\%-$2$\% of the solving time to reach an approximate Nash equilibrium compared to DeepStack's replication.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Game Theory Imperfect Information Games Counterfactual Regret Minimization Poker Machine Learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/b820614539e0123833f4dda65f0e4700943bc8e1.pdf
other topics in machine learning (i.e., none of the above)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission