Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games
Authors: Boning Li
Longbo Huang
Venue: ICLR 2025 Poster (2025)
Keywords: Game Theory
Imperfect Information Games
Counterfactual Regret Minimization
Poker
Machine Learning
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Efficiently computing approximate equilibrium strategies in large Imperfect Information Extensive-Form Games (IIEFGs) poses significant challenges due to the game tree's exponential growth. While pruning and abstraction techniques are essential for complexity reduction, existing methods face two key limitations: (i) Seamless integration of pruning with Counterfactual Regret Minimization (CFR) is nontrivial, and (ii) Pruning and abstraction approaches incur prohibitive computational costs, hindering real-world deployment. We propose Expected-Value Pruning and Abstraction (EVPA), a novel online framework that addresses these challenges through three synergistic components: (i) Expected value estimation using approximate Nash equilibrium strategies to quantify information set utilities, (ii) Minimax pruning before CFR to eliminate a large number of sub-optimal actions permanently, and (iii) Dynamic online information abstraction merging information sets based on their current and future expected values in subgames. Experiments on Heads-up No-Limit Texas Hold'em (HUNL) show EVPA outperforms DeepStack's replication and Slumbot with significant win-rate margins in multiple settings. Remarkably, EVPA requires only $1$\%-$2$\% of the solving time to reach an approximate Nash equilibrium compared to DeepStack's replication.

Published as a conference paper at ICLR 2025
EFFICIENT ONLINE PRUNING AND ABSTRACTION FOR IMPERFECT INFORMATION EXTENSIVE- GAMES
Boning Li
Institute for Interdisciplinary Information Sciences, Tsinghua University 11 1i-bn222maii l...aassssssssssu.........
tsiiguu....... edu.
Longbo Huang
Institute for Interdisciplinary Information Sciences, Tsinghua University longbohuangget tinghuu. edu. on
ABSTRACT
Efficiently computing approximate equilibrium strategies large Imperfect In- formation Extensive-Fome Games (IEFGG)) poses significant challenges due to the game tree's exponential growth. While pruning and abstraction techniques are essential for complexity reduction, existing methods face two key limitations: (i) Seamless integration of pruning with Counterfactual Regret Minimization (CFR) is nontrivial, and (ii) Pruning and abstraction approaches incur prohibitive com- putational costs, hindering real-world deployment. We propose Expected- Value Pruning and Abstraction (EVPA), novel online framework that addresses these challenges through three synergistic components: (i) Expected value estimation using approximate Nash equilibrium strategies quantify information set utili- ties, (ii) Minimax pruning before CFR to eliminate a large number of sub-optimal actions permanently, and (iii) Dynamic online information abstraction merging information sets based on their current and future expected values in subgames. Experiments on Heads-up No-Limit Texas Hold's em (HUNI.) show EVPA outper- forms DeepStack's 's replication and Slumbot with significant win-rate margins in multiple settings. Remarkably, EVPA requires only 1%-2% of the solving time to reach approximate Nash equilibrium compared to DeepStack's replication.
INTRODUCTION
Imperfect Information Extensive-Form Games (IEEFGs) provide a robust framework for analyzing sequential games with hidden information and multiple players. This framework is applicable across various domains, such as Poker (Brown & Sandholm/ 2019a), Mahjong (Li et al. 2020), and Strat- ego (Perolat al., 2022). Counterfactual Regret Mınimization (CFR) and its variants (Zinkevich let al.) 2007b] Lanctot et al. 2009] Tammelin 20144, Brown et al. 2019 Brown & Sandholm 2019b] Xu 2024) stand
the leading approaches for solving HEFGS. However, the computational overhead of CFR scales with the size of the game tree, making it challenging to compute approx- imate equilibrium strategies for large IIEFGs, particularly in games such Hcads-Up No-Limit Texas Hold' em (HUNL), which features a game tree with roughly 10165 states (Johanson) 2013).
Reducing the size of the game tree is essential for making equilibrium computation feasible (Sand- holm, 2010p. Pruning techniques (Blair et al. 1996) eliminate sub-optimal branches, speeding up CFR convergence and reducing computational overhead (Brown & Sandholm 2015a). Similarly, abstraction techniques (Sandholm) 2015) group similar information sets into buckets, significantly shrinking the game tree size. Combining pruning and abstraction methods can substantially reduce the game tree size, making CFR more practical for large IIEFGs (Brown & Sandholm, 2016b) 2018).
Despite their utility, current pruning and information abstraction techniques have limitations. Exist- ing pruning methods often depend on intermediate computed values during CFR iterations (Lanctot et al. 2009 Brown & Sandholm, 2015a 2017a), leading to dynamic and tentative pruning. This
"Corresponding author.

---

Published as a conference paper at ICLR 2025
complexity requires tailored adjustments based on the specific CFR variant employed. More im- portantly, when using generic techniques such as depth-limited solving (Moravčík et al., (017) or MCCFR (Lanctot al. 2009). the computational overhead of these intermediate values may even greatly exceed the original overhead of the iteration. Moreover, during early CFR iterations, the game tree size remains unchanged, resulting in no reduction in memory usage.
Information abstraction methods can be broadly categorized into expectation expectation-based abstraction (Gilpin & Sandholm] 2007] Zinkevich al. 2007a) and potential-aware abstraction (Gilpin al. 2007 2008; Ganzfried & Sandholm 2014). Expectation-based abstraction often neglects the future evolution of information sets, making less effective (Gilpin & Sandholm, 2008 Johanson al. 2013). While potential-aware abstraction is more comprehensive, it requires extensive simulation and clustering, leading to significant computational overhead that can extend for months (Sand- Brown et al. 2015), making it impractical for online computation. Furthermore, when utilizing subgame solving techniques (Ganzfried Sandholm 2015) Brown & Sandholm (2017c), previous methods often use the same pre-calculated abstraction across different subgames, which can be sub-optimal? [ Additionally, many methods focus solely on the strength of information sets, overlooking blocking effects (Sandholm 2010
To address these challenges, we propose Expected- Vareeted-VVlue Value Pruning and Abstraction (EVPA), a novel online method that integrates expected value estimation into pruning and abstraction processes. The goal is to significantly reduce the solving time required to reach an e-Nash equilibrium. EVPA consists of three
components: expected value estimation of information sets, expected value- based pruning, and information abstraction for subgames. Figure | illustrates how EVPA method operates in a HUNL subgame example.
Flop: ks9d5d
kdkh
5z5h
JdTd
KeQs
KhCas
3h3c
2h2c
7dch
5c45
So4th
5h3h
8d2h
7d2h
Subgome Root
Actioio Fhhhlahhahhtt
Player 1's Action
Check
Bet 165
500
Kalkh -103
5s5h V970
JdTc -316
KoCas -314
Khaa -314
3h3c
Kdlkh +1222
5a5h 1957
Jdid +017
KcQa
Kiras +114
3h3c
Kalkh -100
Sabhh -113
Jdlid -310
KcOs -313
KhQs -113
3h3c -12
Sods
7dsh
5h3hh
Player Action
Fold
995
Call
Hand
Information
Kalkch km3
5w5h +:.0
JdTT 47/00
KoDa 1240
KirOss uhap
Kdlth -OVEN
Sk5h VI801
JdTd -ak3
KcOs
KhCs
Kalch +10
SaSh -1000
JdTd -1oV
KcOr +1.0
KhOs
Hand
Pruned Information Set
7d6hh
5:4a
Ss4h
Sh3h
5h3h
7dlh
Public
Player Action
Told
Call
Raise 3485
Pruned Public State
Kdkh
5w5h
JaTa
KcGa
KtOs
KdKch -2015
5t:5h -2040
JdTd
KcCa
KHOH
Kdkh
5+5h +2012
JdTd -12a
KcQs -21
KhCs
-2641
5oth
5h3h
Subgame
Figure 1: In the HUNL. example with 200 big blinds (20, 000 chips), the player in the small blind (Player 1) raises to 250 chips, and the player in the big blind (Player 2) calls during the pre-flop stage. The flop reveals Ks9d5d, after which Player checks, making it Player I's turn to act. The figure illustrates a portion of the current subgame constructed by EVPA. First, EVPA estimates the expected value of each information set within the subgame. It then prunes branches with signif- icantly lower expected values, as indicated by gray blocks representing pruned information sets. Finally, EVPA clusters the remaining information sets based on their current and future expected values. Information sets of the same color in the figure are grouped into the same bucket, where "bucket" refers to a collection of information sets that share the same strategy within the subgame.
For example, in HUNL, holding bottom pair may he advantageous if both players check to the river, but can weaker significant pot increases oceur before the river.
For instance, in HUNL, when the public cards the river are KsTs9d665s, holding As3h and holding Ac3h have equal strength, but is less likely for the opponent to hold the nuts (the strongest hand) with As3h,
2

---

Published as a conference paper at ICLR 2025
The first component, expected value estimation of information sets, generates expected value estima- tions for each information set in the subgame, based on the approximate Nash equilibrium strategy- EVPA's estimation does not rely on the probability distributions of information sets, allowing it to efficiently sample data and avoid the overhead of probability distribution calculations typically re- quired during CFR iterations (Kroer & Sandholm, 2015: [Brown al. 2018). The innovation of EVPA lies in its ability to effectively harness these expected value estimations specifically for both pruning and information abstraction before the CFR process begins. This capability optimizes the Decision-making process, enhancing computational efficiency while maintaining strategic depth.
The second component, expected value-based pruning, employs Minimax pruning (Blair al., 1996) based on the expected value estimation of information sets. By permanently and correctly eliminat- ing sub-optimal branches before the CFR begins, EVPA enables the CFR to concentrate on the most important branches, leading to substantial increase in convergence speed. Notably, EVPA's prun- ing efficient and does not require real-time computation of intermediate values, unlike previous methods (Brown& & Sandholm 2015a 2017a Brown et al. 2017). Additionally, it can be seamlessly
integrated with various CFR variants (Lanctot et al. 2009 Brown & Sandholm 2019b).
The third component, information abstraction for subgames, introduces novel online algorithm that merges information sets based on both current and future expected values. Compared to previous methods (Gilpin & Sandholm 2007 Ganzfried & SSndholm 2014), EVPA's information abstraction considers relative strength, blocking effects, and potential strength of the information sets, while achieving efficient abstraction in under 1 second. EVPA's abstraction is effective in online CFR solving and is scalable to larger IIEGGs such as Omaha (Farha & Reback (007)). Furthermore, the flexibility in selecting bucket sizes allows EVPA balance solving time and abstraction granularity.
We evaluate EVPA using Heads-up No-Limit Texas Hold' em (HUNL) poker and compare its perfor- mance against DtepStack's replication (Moravčík et al., 2017) and strong open-source AI Slumbot (Jackson 2013). EVPA shows significant improvements, including reductions in game tree sizes ranging from 42.67% to 79.51% across different abstraction settings and subgames. Notably, EVPA reduces the solving time required to reach an E-Nash equilibrium to just 1%-2% of the time needed for DeepStack's 's replication. EVPA also outperformed the DeepStack's replication with win-rates of 930 23, 202 31, 82 + 60 mbb/h when the information set is touched 1 x 10?. 1 10 and 1 x 10 times, respectively, Additionally, EVPA beats Slumbot with win-rates of 10 + 26, 96 + 43, 100 + 68 mbb/h under 0.02, 0.2 and 2 seconds of the solving time limits, respectively.
The main contributions of our work are as follows:
Novel Expected malued-Based Pruning. We introduce highly effective pruning technique that permanently and correctly eliminates sub-optimal actions from the game tree before the CFR process begins. This approach achieves up to 98.6% reduction in exploitability in HUNL subgames, enabling us to avoid traversing unnecessary paths. Notably, this pruning method does not require complex computations and exhibits excellent scalability.
Advanced Information Abstraction for Subgames. Our information abstraction method pro- vides efficient abstractions that consider both current and future expected values, enabling tailored online abstractions for different subgames with minimal computational overhead. This abstraction method accelerates convergence significantly in HUNL subgames, and has the potential to be applied to more complex games than HUNL.
Super Performance on HUNL. EVPA effectively integrates the core techniques from pre- vious superhuman performance HUNL AIs, such as Libratus (Brown & Sandholm 2018) and DeepStack. Experiments with limited solving time on HUNL demonstrate that EVPA surpasses both DeepStack's 's replication and strong bot Slumbot with significant win-rate margins, indicating that EVPA can achieve super performance with minimal solving time.
RELATED WORK
Value Estimation in IEFGSs Value estimation is predominantly used to substitute leaf node values in depth- -imth-- solving. DeepStack (Moravřík al. 2017) achieved superhuman performance in HUNL through probability distribution-based value estimation during CFR iterations. Subsequent works like Supremus (Zarick et al. 2020) and ReBel. (Brown et al. 2020), further validated the
3

---

Published as a conference paper at ICLR 2025
reliability of this approach. Another method for estimating leaf node values involves selecting the highest value from multiple strategies (Brown et al.) 2018). Beyond depth-limitee solving, value estimation has applications in various IIFGG techniques, including Deep CFR (Brown et al. 2019), action abstraction (Li et al. 2024) and variance reduction (Burch et al. 2018).
Pruning with CFR. In CFR, the value and reach probability of an information set change with each iteration. This dynamic nature means that most previous pruning methods rely on temporary prun- ing using intermediate computed values. For instance, regret-based pruning (Brown & Sandholm, 2013a) avoids traversing a path if either player takes actions leading to that path with zero proba- bility. Furthermore, best-response pruning (Brown & Sandholm, 2017a) allows for the temporary pruning of poorly performing actions. Additionally, partial pruning (Lanctot et al. (200)) and dy- namic thresholding pruning (Brown et al., (017) enable the pruning actions with low probability. A more detailed description of pruning methods in IIFFGs can be found in Appendix G
Information Abstraction in IEFGSs Information abstraction can be categorized into expectation-
based abstraction and potential- abstraction (Gilpin & Sandholm, 2008). Expectation-basse abstraction methods (Gilpin & Sandholm] 2007; Zinkevich et al. 2007a) classify information sets based their current strength of expectation, while potential-aware abstraction methods (Gilpin jet al.) 2007 2008) consider the performance of information sets across different future scenarios. The imperfect-recttd technique (Waugh et al., 2009 Ganztried & Sandholm 2014) allows players to intentionally forget certain information, significantly reducing the size of the game tree. A more detailed description of the abstraction can be found in Appendix
BACKGROUND AND NOTATION
In an Imperfect Information Extensive-Form Game (IEFG), there is a finite set of players N (1..... N]. A state, also known as history h, represents the sequence of all historical actions taken from the initial state Ø. Performing an action in a non-terminating state h transitions to a new state N1, denoted as h a- = h1, where performing sequence of actions, then h is an ancestor of h'. We use the notation h C h to mean an ancestor of N', and c N1' to mean h is a strict ancestor of hi. A terminal state z one where no further actions are available, and up(2) (2) represents the payoff for player p at terminal state z. The acting player at a non-terminal state h is denoted by P(h) E NN W {c), where e represents the "chance player," indicating events beyond the control of players in N.
the parent of ht. If state lí' can be reached from h by
For each player E N, imperfect information is represented by an information set Ip- All states h, h' Ip indistinguishable p. If p is the acting player, the information set Ip can be simply denoted as J. The set of information sets is denoted by I. A strategy (7)) is probability distribution over the available actions within information set T. The probability of choosing action a information set I is denoted as (I, a). The strategy for player in all information sets where they act is denoted as Tp. while the strategies for all other players are denoted as a-p. A strategy profile = (Op)PeN is a collection of strategies, one for each player. The expected value (EV) of an information set I, under strategy profile a is denoted EVG
The best response for player to J-p is a strategy that maximizes player p's payoff. Math- ematically, BR(a-p) = arg max "p(("".-pp)) A Nash equilibrium o" is a strategy profile where each player's strategy is best response to the strategies of the other players. That is, Vp, "p(o", ,=",)) = max,; Up "p(a", p)))). The exploitability e(ap) of a strategy op in two-player vero-sum game measures how much worse the strategy performs compared to a best response against ( BR(o))) (p BR(o,)). )). A strategy profile is an e-Nash equilibrium if no player has an exploitability greater than under
a Nash equilibrium strategy. Formally, e(ap)
subgame is a continuous portion of a game tree. Formally, subgame is a set of states such that Ah E S, if h E Ip and h E Ip then h E S, and Vx, E S, if x C y C 2 then y S. A public state (or node) s contains the information known to all players. The unique public state corresponding to state h and information set I, is denoted as s(h) and s(4p), respectively. If state h E S has no descendants within S, it is called a leaf state, and the information sets and nodes containing called leaf information sets and leaf nodes. Conversely, if h e S has ancestors within S. it is called a root state, and the information sets and nodes containing h are called root information sets and root nodes. The root node of S is denoted as S,
4

---

Published as a conference paper at ICLR 2025
4 EVPA ALGORITHM
In this section, we present the Expected-Valle Value Pruning and Abstraction (EVPA) algorithm. The EVPA algorithm is composed of three core components: (i) expected value estimation of informa- tion sets (Section 4.1). which calculates the expected value of each information set to serve as a foundation for subsequent operations: (ii) expected ailue-based pruning (Section 4.2), where sub- optimal branches are permanently removed from the game tree before CFR using the estimated expected values; and (iii) information abstraction for subgames (Section 4.3) which groups similar information sets based on their current and future expected values in subgames to reduce complexity. Figure visually depicts the operation of these three components in depth-limited subgame.
Information Sets
History Actions
Root Node
1. EEpected Value Estimation
2.Pruning
Min,Max Values
Depth-Limited
Expected Value Networks
Subgame
3. 3.Abstraction
Features
Original Game Tree
Player 1's Information Set
Unsolved Subgames
Player Information Set
Game Tree Node
Framework of EVPA. We begin by estimating the maximum, minimum, and average expected values of each information set in the subgame using expected value networks. Next, we prune the game tree based the maximum and minimum values. Finally, utilize the average values as features for information abstraction.
Figure 2:
4.1 EXPECTED VALUE ESTIMATION OF INFORMATION SETS
In this subsection, we detail the expected value estimation process of information sets within the EVPA algorithm. We begin by using a framework similar to DeepStack's (Moravčík et al., (017)) for computing depth-limited subgame equilibrium strategies (further implementation details avail- able in Appendix D) This framework is trained using a large dataset game states and actions from wide variety of IIFG scenarios. Once the training process is completed, leverage this trained framework to estimate the expected values of approximate Nash equilibrium strategies for various information sets in IEFGS.
Our method involves sampling diverse subgames and calculating approximate Nash equilibrium expected values for information sets within these subgames. The sampling process is outlined in Algorithm [ We start by generating a depth-limited subgame S from a random initial public state. To ensure comprehensive action coverage, game construction. We then compute the Nash equilibrium strategy for this subgame, calculate the expected value for each information set, and incorporate these values into our training data. The process continues by sampling leaf node of the subgame S. If s is not a terminal node, we then solve the subgame rooted at 8. We emphasize that, unlike DeepStack, the information set features in EVPA contain only public information and player's private hand information, and do not include range information of both players.
utilize randomized action abstractions during sub-
Once we have collected sufficient data through the sampling process outlined in Algorithm I proceed to train neural networks for the purpose of expected value estimation. We train M inde- pendent neural networks (with M 10) using the Huber Loss (Huber 1964) our loss function. Each neural network receives a feature vector describing the information set, and outputs a scalar representing the expected value (relative the pot size) of that information set.
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: Algorithm for Sampling of Nash Equilibrium Expected Value of Information Sets.
Data < 0, <
RandoonlniPPublccsttt()/// Randomly mnitializatin
while (s)) * 0 do
while ((s) = do
TaakcChancess)// Process a random chance event
- - Build a depth-limited subgame with
randomi zed action abstractions
o² --ttraegySollvnn(5)) // Compute Nash equilibrium strategies
for I E do FVV. (Tp) <=CalullaeFxpeeeeeWalllS...
Add (Tp, EVV- to Data
SampleLeaf((,, o²) // Randomly sampling a leaf
Output: Data
The network architecture consists of 6 layers of Multi-Layee Perceptrons (MLPs), each with 1, 536 hidden units and ReLU activation functions (Glorot al. 2011). Each network is trained on least 10 billion samples using the Adam optimizer (Kingma & Ba 2013). Each sample provides values for all information sets within subgame S, resulting in a samplngg size that is millions of times larger than the one used by DeepStack within the same sampling time. Training the DeepStack replication requires 70 days, with sampling time being the primary overhead. contrast, training the expected value network in EVPA takes only 4 days, with 1 day of sampling time.
Upon completing the training, we obtain M expected value estimation networks. For each infor- mation set Ip. the expected value estimation from the i-th network is denoted (Vp) We calculate the average expected value estimation as EV
+ ΣM (I) Additionally, we determine the maximum and minimum expected value estimations across the M networks as (V)) max max(FVV (T)) (T))) and mi (T)) = min (FVV (Tp).... FVM (Tp)), re- spectively. The computed average, maximum, and minimum expected values will serve crucial inputs for the pruning and abstraction steps, allowing us to make informed decisions on which parts of the game tree prune abstract. The true innovation of EVPA lies in its effective use of these expected value insights, enabling smarter decision-making and more efficient exploration of the game tree. This ultimately enhances the overall performance of the algorithm.
4.2 EXPECTED VALUE-BASED PRUNING
In this subsection, introduce the Expected Value-based Pruning component of the EVPA algo- rithm, which is a crucial part of our approach to reduce the computational complexity of IIEFGs. This pruning technique uses the expected value estimates from our previously trained networks to make informed decisions about which parts of the game tree can be safely pruned.
The EVPA pruning method introduces novel approach inspired by Minimax pruning (Blair al., 1996), based on the principle that an optimal player will not select an action for an information if another action has a higher expected value. For instance, Aces pre-flop is clearly sub-optimal compared to calling or raising, which yield higher expected values. Formally, for an information set I, an action a, and Nash equilibrium strategy a*, EV,- (I--(I-0) < EV, W (T), then o² (I, (I.a) a) = 0. Furthermore, if there exists another action a' such that EV, (I- < EV,- (I-((Iaa) a'), then o² (I, a) 0.
HUNL, discarding pair of
However, accurately calculating exactly expected value under Nash equilibrium can be computation- ally prohibitive. To address this challenge, the EVPA method leverages estimates from M expected value estimation networks perform pruning efficiently before applying the CFR algorithm. This integration enhances the efffctiiveness of pruning and significantly reduces computational overhead.
The details of the pruning algorithm are outlined in Algorithm 2 The MaximumJudge function evaluates whether the child information set 1 of Ip has the highest expected value for player p. The LegalFromRoot function innovates further by verifying that player p has not taken any sub- optimal actions from the initial state up to Ip. The Pruning function orchestrates the overall pruning process by using queue traverse the information sets and apply the pruning criteria. Ultimately,

---

Published as a conference paper at ICLR 2025
the function returns the necessary information sets to retain, completing the efficient permanent pruning of the game tree before initiating the CFR algorithm.
Algorithm 2: Algorithm for EVPA subgame pruning.
Function Max mummuddee (7p pp)): )
if ((pp) # p then return True// / If the acting player is not p, return true MaxMin in -00 for I E Ip do
i * II EVEin(Ly > Marrinn then MarMin E.Viin
EV mar (1,m0) + Min,MarMMnn Eimia (Ip)) then
return True
return False
F Function LegalFromRoot (Tp):
Parent(Lp) (pp) = 0 then
return True
1 + Pareent([)))) There exists action such that I
return Maximum.Judge(T, Ip) A (egalFromRoot(())
Function Pruning (S):
Troas Iubgaaee (-0
for I, E Sr do
if LegalfromRoo(() 1p) then
Add Ip Iroot // Pruning root information sets I Lqueue: Iaubgame &- Troot while Iquoue + 1 do Ip < TopElemenn((quan for & E Jp a do if (T,)) E E A MaximamJudge I2) then Add In to Io Iqueue Inubgame
Iquene Igqeue
return Lyoot Iubbaame
The parameter is introduced to mitigate enrors generated by sampling data. When is no less than eliminate the error generated by CFR with DeepStack After elimination of emror generated by CFR iterations the sampling process, we can be confident that the sampled data fully reflects the exact expected value of the information set. For the information set 4p. the value estimation of the neural network can be expressed as EVg (4p) + err, where err is the random error generated by the network itself.
the maximum average regret O (+) of CFR, where T is the CFR iterations,
Error Analysis. We consider pruning error to occur when branch pson = I-a with EV (1 EV, (7) is pruned. In the worst-case scenario, all branches of the information set have the same expected value, making incorrect to prune any branch. To analyze the probability of error, we consider the sampling of estimates from M networks. We enumerate each sibling information set Thro of Toow the pruning error occurs in the T branch if all M estimates about 1 are smaller than the other 2M estimates about Ip and the sibling information set Ihmm The probability of selecting exactly the M minimum values out of 3M random values is (a The Ison has |A] siblings,
and the upper bound pruning error probability of 1
LAI-1 (37)
The pruning algorithm estimates the expected values of O(M D- M ZZ) information sets, where M represents the number of expected value estimation networks, D is the current depth of the subgame, SS] is the number of nodes in the subgame, and |Z] denotes the number of distinct information sets per node. Notably, the computational overhead of the pruning algorithm is minimal compared to that of the CFR algorithm, highlighting its practicality and efficiency in large IIEFGs.
Thhe value of 0.01 was chosen hased empirical evidence. We observed that with this value, the error generated by discounted CFR (DCFR) algorithm (Brown Sandholm 2019h) effectively mitigated.

---

Published as a conference paper at ICLR 2025
By directly and correctly eliminating unimportant branches, EVPA's pruning algorithm enables the CFR algorithm to concentrate on more critical branches, significantly enhancing convergence and overall performance. This strategic focus not only accelerates computation but also facilitates more effective exploration of promising areas within the game tree.
4.3 INFORMATION ABSTRACTION FOR SUBGAMES
In this subsection, we describe the Information Abstraction for Subgames component of the EVPA algorithm. This crucial part of our approach aims to simplify the game tree by merging similar information sets, thus reducing computational complexity while maintaining strategic integrity.
EVPA's information abstraction method innovatively clusters both current and future expected val- ues of information sets as features. The core idea behind merging information sets and is to simplify the game tree by grouping similar information sets together. We consider them similar if their current and future expected values are closely aligned. Specifically, we merge two information sets 7 and I' when the following conditions are met: (1) s(T) s(!"), which ensures that the public states of the two information sets are the same, and (2) for any action sequences 01, an (where 0), if Vi < n,, P(1 d1 ......00 a,) * P(I), then EV (I 01 .....a.. an) z EV (1' ..,)).... This second condition checks that for any sequence of actions, the expected values of both information sets remain approximately equal. If these conditions hold, it follows that a* (*(T) o² (I'),, indicating that the strategies for / and will be similar, and hence they can be merged.
This merging approach extends to subgame solving, allowing for the consolidation of root informa- tion sets into K buckets within subgames. For player all information sets bucket k: are denoted as mootbucket. k. All information sets in Inootbuckrr.p. p, adopt the same strategy in the subgame.
The details of the EVPA information abstraction algorithm are outlined in Algorithm 3 The process begins by pruning all root information sets and storing the viable root information sets I
Next, we enumerate each node of the subgame S and predict the expected value of each root information set Ip at that node. To estimate this expected value, we utilize the average output from M expected value estimation networks. This estimated value is then multiplied by significance function (g((s, n) and appended to the features of Ip. Here, g(s) encapsulates various pieces of information about node s, while represents the distance from the root node S, to node In the context of HUNL., we define the significance function as f(((). mox(e)-max((n002)) where (st(s) indicates the number of chips in the pot at node s.
Algorithm 3: Algorithm for EVPA information abstraction.
Function Abstraction (S, K) Trnat Luugaame &- Pruning(S) for Ip E Insot do feature(Lp)
0// Define features for information sets for & E do
01, .., ann SequenceActions(S,..)) 8)// Actions from S, to for I, E Immo do Append (L, ... an) (fg(s))(((((s into feature(Lp)// Append weighted average expected va value the feature vector of Ip
Tronthuchet Tmubganebucker for p E N do
Irootbuckt, for s E S do
Lnootucker.p + (<meanst++((,,
K)
01 On + SeqmenceActtons((S.,)
for :: = to K do
for I, E Imunthuckes.p.. do
if T Add Ipnobbcckrr to Luudggamebucket.... I
On Inubgame then
break/ Exit loop once a match is found
return Irnotbucket Imbggmmehucke
8

---

Published as a conference paper at ICLR 2025
After calculating expected value features, cluster the root information sets for each player using the k-means++ algorithm (Arthur & Vassilvitskii 2007). The clustering process has a time com- plexity of (T K |S| [mww)), where T is the number of iterations of the k-means++ algorithm (set to T = 8), is the number of buckets, |S]] is the number of nodes in the subgame, and [mmel is the number of legitimate information sets at the root node. Remarkably, even for large IEFGSs such as HUNL, the information abstraction process can be completed quickly, making it suitable for real-time applications.
Following the clustering, we retain the original pruning results of the subgame in Zuuhgume- After clustering, we check for buckets where all of their information sets are not in the previously pruned subgame set Imuggame. These buckets are considered unnecessary and can be pruned, further reducing the complexity of the game tree.
A key innovation of EVPA is its ability to provide dynamic, subgame-specific abstractions that effec- tively integrate both current and future expected values. Compared to other information abstraction methods, EVPA's approach not only offers faster processing times (completing in under 1 second on a standard server for HUNL) but also provides more accurate and dynamic abstractions tailored to specific subgames, as it takes into account both current and future expected values. Additionally, the flcxibility in choosing the bucket size K allows for an optimal balance between solving time and abstraction accuracy, further enhancing the algorithm's 's applicability in real-time scenarios.
EXPERIMENTS
We conduct a series of experiments to comprehensively evaluate the performance of the EVPA algo- rithm in the context of large IIFFGs. As in previous studies on large IIEFGs (Moravčík et al. 2017 Brown & Sandholm 2018), we use HUNL (see Appendix A for detailed rules) as our experimental benchmark due to its representativeness and complexity. In our evaluation, players start with 200 big blinds and switch positions every two hands, replicating conditions of the annual computer poker competition (ACPC) (Bard et al.. 2013). All experiments employed the leading DCFR algorithm (Brown & Sandholm 2019b), as outlined in Appendix C To maintain strategy soundness, we uti- lized subgame re-solving techniques (Burch et al.) [2014] Brown & Sandholm 2017c). Additionally, the AIVAT technique (Burch et al. 2018) is applied to reduce variance in heads-up evaluations.
Training and experiments were executed on a server with 4 NVIDIA A100 80GB PCIe GPUs and 112 Intel(R) Xeon(R) Gold 6348 2.60GHz CPUs. For our evaluations, we replicated DeepStack (Moravčík et al.. 2017) as a baseline (BASE) and implemented three Als using the EVPA algo- rithm: fVlA-full (which employs pruning only), EVPA- 169 (pruning combined with 169 buckets for abstraction), and EVPA-30 (pruning combined with 30 buckets for abstraction).
Pruning Effectiveness. We randomly generated at least 10, 000 depth-limited subgames across different stages of HUNL. The pruning rates are summarized in Table EVPA-full achieved pruning rates between 79% and 79.51%. %. EVPA-169 achieved pruning rates between 55.68% and 69.50%, while EVPA-30 achieved pruning rates between 42. 12.67% and 51.58%. These results clearly indicate that EVPA effectively prunes significant portion of the game tree across various settings.
Table 1: Game tree pruning rate of depth-limited subgame each stage of HUNL.
EVPA AIs Pre-flop
Flop
Turn
River
EVPA-full
69.72%
69.87%
77.00%
79.51%
EVPA-169
69.50%
55.68%
63.07%
65.31%
EVPA-30
51.58%
42.67%
49.60%
49.79%
Exploitability Evaluation. In our evaluation of exploitability the river stage subgame, illus- trated in Figure 3 the EVPA AIs demonstrate a marked reduction in exploitability compared to the baseline. Specifically, EVPA-full achieves the lowest exploitability with 1 information set touches, reducing exploitability to approximately 1.4% of the baseline's 's level. Further analysis reveals that EVPA-169 reduces exploitability by 47% relative to EVPA-full with 1 x 10" touches, while EVPA-30 achieves a 54% reduction relative to EVPA-169 with 1 x 106 touches.

---

Published as a conference paper at ICLR 2025
Notably, reach an exploitability of no more than 0.08, the baseline requires around 1 x 10 informa- tion set touches, whereas EVPA-30 achieves this with only 1 x 10 Similarly, for an exploitabil- ity threshold of 0.01, the baseline necessitates over 5 x 10 touches, while EVPA-169 can already achieve this with just x x00 touches. These results underscore that EVPA can attain an E-Nash equi- librium with only 1%-2% of the information set touches required by the baseline, highlighting the significant improvement exploitability reduction achieved by EVPA.
EVFA-100
EVPA-30
FVP3-611
BA5E
0.1
Explotablity
0.001
0,0031
Heads-up Evaluation Against Slumbot. We conducted heads-up evaluations against Slumbot (Jackson 2013). a strong open-source HUNL AI that won the 2018 ACPC. The results presented in Table 2 In the initial trials with a solving time limit of 0.02 seconds, DeepStack's replication suf- fered a significant defeat, recording a win-rate of -573 + 28 mbb/h against Slumbot. In contrast, the EVPA algorihms-EEVPA-tll EVPA-169, and comparable performance levels to Slumbot, with EVPA-169 achieving a win-rate of 10 + 26 mbb/h. When the solving time was increased to 0.2 seconds, DeepStack's replication continued to struggle, showing win-rate of 1 109 + 52 mbb/h. Meanwhile, EVPA-full succeeded in defeating Slumbot with a win-rate of further increased to 2 seconds, DeepStack's replication managed to beat Slumbot with win-rate of 33 = 65 mbb/h, but still fell short of EVPA's performance. Overall, these results show that EVPA algorithms are more competitive against Slumbot, especially under time-constrained scenarios.
1e6
1e? Touched Information Sets
1e8
149
Figure 3: The average exploitability (relative to the current pot size) of various HUNL Als during river subgames is plotted against the number of information sets touched by DCFR.
43 mbb/h. When the solving time was
Table 2: Heads-up results of AIs against Slumbot with solving time limits, measured in mbb/h.
Solving Time Limits
BASE
EVPA-full
EVPA-169
EVPA-30
0.02 seconds
-573 + 28
8 + 25
10 + 26
-4 28
0.2 seconds
-109 + 52
96 +
31 57
2 seconds
33 65
100 + 68
Heads-up Evaluation Against DeepStack's Replication. We further conducted heads-up evalua- tion between DeepStack's 's replication and various EVPA AIs, varying the limits on the number of information set touches, as presented in Table 3 After the CFR algorithm touches the information set 1 x 10" times, the EVPA algorithm significantly outperforms DeepStack's 's replication, demon- strating a win-rate of up to 930 + 23 mbb/h. Even after 1 x 10th touches, EVPA maintained its advantage, defeating DeepStack's ' replication with win-rate of 202 31 mbb/h. When the number of touched information sets came to x 10", DeepStack's replication was still outperformed by EVPA, with recorded win-rate of 82 + 60 mbb/h. These results show that EVPA has significant win-rate against DeepStack's 's replication, regardless of the number of information set touches.
Table 3:
Heads-up results of EVPA AIs against DeepStack's 's replication with different limits on the number of information set touches, measured in mbb/h.
Touched Information Sets
EVPA-full EVPA-169
EVPA-30
10?
844 + 26
930 + 23
865 + 29
1 x 108
202 + 31
125 + 27
x 10"
82 - 60
Overall, the experimental results show that EVPA is a highly effective algorithm for solving large IIBGGs particularly in settings with limited solving time.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was supported by the National Natural Science Foundation of China Grants 52450016 and 52494974.
REFERENCES
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In SODA, pp- 1027-1035. SIAM, 2007.
Anton Bakhtin, David J. Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H. Miller, and Noam Brown. Mastering the game of no-press diplomacy via human- regularized reinforcement learning and planning. In ICLR. OpenReview.net, 2023.
Nolan Bard, John Alexander Hawkin, Jonathan Rubin, and Martin Zinkevich, The annual computer poker competition. A/ Mag., 34(2): 12, 2013.
Nolan Bard, Michael Johanson, and Michael H. Bowling. Asymmetric abstractions for adversarial settings. In AAMAS, pp. 501-508. IFAAMAS/ACM, 2014.
Jean R. S. Blair, David Mutchler, and Michael van Lent. Perfect recall and pruning in games with imperfect information. Comput. Intell., 12:131-154, 1996.
Noam Brown and Tuomas Sandholm. Regret transfer and parameter optimization. In AAAI, pp. 594-601. AAAI Press, 2014.
Noam Brown and Tuomas Sandholm. Regret-based pruning in extensive-form games. In NIPS, pp- 1972-1980, 2015a.
Noam Brown and Tuomas Sandholm. Simultaneous abstraction and equilibrium finding in games. In IJCAI, pp. 489-496. AAAI Press, 2015b.
Noam Brown and Tuomas Sandholm. Strategy-based warm starting for regret minimization in games. In AAAI, pp. 432-438 AAAI Press, 2016a.
Noam Brown and Tuomas Sandholm. Baby tartanian8: Winning agent from the 2016 annual com- puter poker competition. In IJCAI, pp. 4238-4239. ICAA/AAAI Press, 2016b.
Noam Brown and Tuomas Sandholm. Reduced space and faster convergence in imperfect- information games via pruning. In ICML, volume 70 of Proceedings of Machine Learning Re- search, pp. 596-604. PMLR, 2017a.
Noam Brown and Tuomas Sandholm. Libratus: The superhuman Al for no-limit poker. In IJCAI, pp. 5226-5228. ijcai.org, 2017b.
Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect-informaae games. In NIPS, pp. 689-699, 2017c.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-4222 2018.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): eaay2400, 2019a.
Noam Brown and Tuomas Sandholm. Solving poperfect-informatioo games via discounted regret minimization. In AAAI, pp. 1829-1836. AAAI Press, 2019b.
Noam Brown, Sam Ganzfried, and Tuomas Sandholm. Hierarchical abstraction, distributed equi- librium computation, and post-processing, with application champion no-limit texas hold' em agent. In AAAI Workshop: Computer Poker and Imperfect Information, volume WS-15-07 of AAAI Technical Report. AAAI Press, 2015.
Noam Brown, Christian Kroer, and Tuomas Sandholm. Dynamic thresholding and pruning for regret minimization. In AAAI, pp. 421-429. AAAI Press, 2017.

---

Published as a conference paper at ICLR 2025
Noam Brown, Tuomas Sandholm, and Brandon Amos. Depth- Septh-limited solving for imperfect- information games. In NeurlPS, pp. 7674-7685, 2018.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret min- imization. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 793-802. PMIRR 2019.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-information games. In NeurlPS, 2020.
Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In AAAI, pp. 602-608 AAAI Press, 2014.
Neil Burch, Martin Schmid, Matej Moravcik, Dustin Morrill, and Michael Bowling. AIVAT: A new variance reduction technique for agent evaluation in imperfect information games. In AAAI, pp- 949-956 AAAI Press, 2018.
Theo SH Driessen. Cooperative games, solutions and applications, volume Springer Science & Business Media, 2013.
Sam Farha and Storms Reback. Farha on Omaha: Expert strategy for beating cash games and lournaments. Triumph Books, 2007.
Sam Ganzfried and Tuomas Sandholm. Computing equilibria in multiplayer stochastic games of imperfect information. In IJCAI, pp. 140-146, 2009.
Sam Ganzfried and Tuomas Sandholm. Action translation in extensive-form games with large tion spaces: Axioms, paradoxes, and the pseudo-harmonic mapping. In IJCAI, pp. 120-128. UCAAI/AAI, 2013a.
Sam Ganzfried and Tuomas Sandholm. Improving performance in imperfect-informante games with large state and action spaces by solving endgames. In Workshops at the twenty-sevnnth AAAI conference on artificial intelligence, 2013b.
Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-recall abstraction with earth mover's distance in imperricttinnoomaaiion games. In AAAI, pp. 682-690. AAAI Press, 2014.
Sam Ganzfried and Tuomas Sandholm. Endgame solving in large imperfecttinfformatio games. In AAMAS. pp. 37-45. ACM, 2015.
Sam Ganzfried, Tuomas Sandholm, and Kevin Waugh. Strategy purification. In AAMAS, pp. 1111- 1112. IFAAMAS, 2011.
Sam Ganzfried, Tuomas Sandholm, and Kevin Waugh. Strategy purification and thresholding: effec- tive non-equilibrium approaches for playing large games. In AAMAS, pp. 871-878. IFAAMAS, 2012.
Andrew Gilpin and Tuomas Sandholm. Better automated abstraction techniques for imperfect infor- mation games, with application to texas hold' em poker. In AAMAS, pp. 192. IFAAMAS, 2007.
Andrew Gilpin and Tuomas Sandholm. Expectation- versus potential-awee aware automated ab- straction in imperfect information games: An experimental comparison using poker. In AAAI, pp. AAAI Press, 2008.
Andrew Gilpin, Tuomas Sandholm, and Troels Bjerre Sørensen. Potential-aware automated abstrac- tion of sequential games, and holistic equilibrium analysis of texas hold' em poker. In AAAI, pp. 50-57. AAAI Press. 2007.
Andrew Gilpin, Tuomas Sandholm, and Troels Bjerre Sørensen. A heads-up no-limit texas hold 'em poker player: discretized betting models and automatically generated equilibrium -finding pro- grams. In AAMAS (2), pp. 91 911-918. IFAAMAS, 2008
12

---

Location Parameter. The Annals of Mathematical Statistics, Published as a conference paper at ICLR 2025
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Geoffrey J. Gordon, David B. Dunson, and Miroslav Dudik (eds.), Proceedings of the Fourteenth International Conference Artificial Intelligence and Statisties, AISTATS 2011, Fort Lauderdale, USA, April 1 1-13, 201 volume 15 of JMLR Proceedings, pp. 315-323. JMLR.org. 2011.
Peter J. Huber. Robust Estimation of 35(1):73 101, 1964.
Eric Jackson. Slumbot nl: Solving large games with counterfactual regret minimization using sam- pling and distributed processing. In AAAI Workshop Computer Poker and Imperfect Informa- tion, 2013.
Michael Johanson. Measuring the size of large no-limit poker games. CoRR, abs/1302 1es//3007000, 2013.
Michael Johanson, Neil Burch, Richard Anthony Valenzano, and Michael Bowling, Evaluating state-space abstractions in extensive-form games. AAMAS, pp. 271-278. IFAAMAS, 2013.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
Christian Kroer and Tuomas Sandholm. Extensive-form game abstraction with bounds. In EC, pp. 621-638. ACM, 2014.
Christian Kroer and Tuomas Sandholm. Limited lookahead in imperfect-information games. In IJCAI, pp. 575-581. AAAI Press, 2015.
Christian Kroer and Tuomas Sandholm. Imperfect-recall abstractions with bounds in games. In EC, pp. 459-4766 ACM, 2016.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H. Bowling. Monte carlo sampling for regret minimization in extensive games. NIPS, pp. 1078-1086. Curran Associates, Inc., 2009.
Boning Li, Zhixuan Fang, and Longbo Huang. RL-CFR: Improving action abstraction for imper- feet information extensive-form games with reinforcement learning. In Forty-first International Conference on Machine Learning, 2024.
Junjie Li, Sotetsu Koyamada, Qiwei Ye, Guoqing Liu, Chao Wang, Ruihan Yang. Li Zhao, Tao Qin, Tie-Ya Yan Liu, and Hsiao- Hsiao-Wuen Wuen Hon. Suphx: Mastering mahjong with deep reinforcement learning. CoRR, abs/2003. 13590, 2020.
Paul R Milgrom and Robert J Weber. A theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society, pp. 1089-1122, 1982.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, Science, (56(6637)))))88-55111 2017. doi: 10. 16/sciience. aam6960.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623)9990-994) 2022.
Tuomas Sandholm. The state of solving large incompleee-infomant games, and application to poker. Al Mag., 31(4):13 32, 2010.
Tuomas Sandholm. Abstraction for solving large incomplete-informatinn games. In AAAL, pp. 4127-4131. AAAI Press, 2015.
Tuomas Sandholm and Satinder Singh. Lossy stochastic game abstraction with bounds. In EC, pp- 880-897, ACM, 2012.
David Schnizlein, Michael H. Bowling, and Duane Szafron. Probabilistic state translation in exten- sive games with large action sets. In IJCAI, pp. 278-284, 2009.
13

---

Published as a conference paper at ICLR 2025
Arnold Snyder. Poker Tournament Formula. Cardoza Publishing, 2006.
Oskari Tammelin. Solving large imperfect information games using CFR+. CORR, abs/1407.5002, 2014.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em In IJCAI, pp. 645-652. AAAI Press, 2015.
Leigh Thompson. Negotiation behavior and outcomes: Empirical evidence and theoretical issues.
Psychological bulletin, 108(3):515, 1990.
Kevin Waugh, Martin Zinkevich, Michael Johanson, Morgan Kan, David Schnizlein, and Michael H. Bowling, A practical use of imperfect recall. In SARA. AAAI, 2009.
Hang Xu, Kai Li, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng, Dynamic discounted coun- terfactual regret minimization. In ICLR. OpenReview.net 2024.
Ryan Zarick, Bryan Pellegrino, Noam Brown, and Caleb Banister. Unlocking the potential of deep counterfactual value networks. CoRR, abs/2007. 10442, 2020.
Enmin Zhao, Renye Yan, Jinqiu Li, Kai Li, and Junliang Xing. Alphaholdem: high-performance artificial intelligence for heads-up no-limit poker via end-to-end reinforcement learning. AAAI, pp. 4689 4697. AAAI Press, 2022.
Martin Zinkevich, Michael H. Bowling, and Neil Burch, new algorithm for generating equilibria in massive zero-sum games. In AAAI, pp. 788-794. AAAI Press, 2007a.
Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione. Regret mini- mization in games with incomplete information. In NIPS, pp. 1729-1736. Curran Associates, Inc., 2007b.
14

---

Published as a conference paper at ICLR 2025
Appendix
Heads-Up No-Limit Texas Hold'en em Rules
15
Breakthroughs in HUNI Als
15
Counterfactual Regret Minimization
16
D DeepStack's Implementation
17
Conclusion
18
F
Future Directions for Research and Application
18
Pruning with CFR
18
Abstraction for Solving Large LIEFGs
19
A HEADS-UP NO-LIMIT TEXAS HOLD' EM RULES
Heads-up No-Limit Texas Hold' em (HUNL) a two-player variant of Texas Hold' em poker, played over four stages:
1. Pre-flop. Players start by posting a pre-specified number of chips: the "small blind" and the "big blind," with the small blind typically being half the size of the big blind. Each player is dealt two private cards at the beginning.
2. Flop. Three public cards are revealed.
Turn. A fourth public card is revealed.
4. River. The final public card is revealed.
During the pre-flop stage, the small blind player acts first; thereafter, the big blind player acts first in all subsequent stages. Players can fold, check/call, or bet/raise, with bets/raises ranging from the last bet/raise amount to their remaining chips (all-in). If player folds, the other wins the pot. If neither folds by the end of the river stage, the players compare their best five-card hands, which consist of two private cards and the five public cards. The player with the best hand wins the pot. Win-rate and exploitability are measured in milli big blinds per hand (mbb/h). For instance, a win-rate of 0.1 big blind per hand equates to 100 mbb/h.
B BREAKTHROUGHS IN HUNL AIS
Tartanian7 Brown al. 2015). Baby Tartanian8 (Brown & Sandholm 2016b), and Slumbot (Jack-
son 2013) winners of annual computer poker competition (ACPC) (Bard et al. 2013) in 2014,
2016, and 2018, respectively initially computed a blueprint strategy based on a post-abstraction
game tree (Ganztried & Sandholm (rowww & Sandholm (014). followed by the strategy exe-
cution based on the blueprint strategy (Ganzfried et al.] 201 2012)] Ganzfried & Sandholm, 2013a]
Brown & Sandholm 2016a). While this approach is effective for TIEFGs with fewer states, such as limit Texas Hold'en em (Tammelin et al., (2015), struggles in HUNL. significant challenge arises when opponent makes an "off-tree" action, in such cases, the AI must substitute approximation from the blueprint strategy (Schnizlein et al. 2009 Ganzfried & Sandholm 2013a), potentially lead- ing to sub-optimal performance (Ganzfried & Sandholm] [0033]] Bard al. 2014). Additionally, the blueprint strategy often lacks the granularity necessary for effective endgame solving (Ganzfried
& Sandholm 2013b 2015).
15

---

Published as a conference paper at ICLR 2025
Libratus (Brown & Sandholm, 2018) addressed these challenges through safe and nested sub- game solving techmique (Brown & Sandholm (017c) and a self-improver to enhance its blueprint strategy (Brown & Sandholm 2017b), ultimately achieving superhuman performance. However, its substantial computational resource requirements limit its implementation to supercomputers, and only solve for fixed initial chip counts, which is impractical in real poker scenarios where chip counts fluctuate (Burch et al., 2018).
DeepStack (Moravčík al. 2017) achieved superhuman performance through depth-limited sub- game solving (Kroer & Sandholm 2013) and probability distribution-bast value estimation of leaf information sets. Subsequent works, such as ReBeL (Brown et al., (020) and Supremus (Zarick et al. 2020). further demonstrate the reliability of this approach. However, none of these Als have incorporated online pruning and abstraction of depth-limited subgames, suggesting potential areas for improvement. Modicum (Brown et al. 2018) introduced a multiple-value depth-limited solv- ing technique based on pre-calculated blueprint strategy, which allows for minimal training and solving time. Nevertheless, its performance remains constrained by the limitations of the blueprint strategy. AlphaHoldem (Zhao et al. 2022), a reinforcement learning- based method, achieves decent performance with short training and solving times. However, its lack of CFR integration makes it susceptible to exploitation.
Table compares the training and solving time of these AIs and the EVPA algorithm, along with their win-rates against Slumbot or Baby Tartanian8. EVPA demonstrates significant advantages in processing off-tree actions compared blueprint strategy-based Als, achieving higher win-rates than these methods. Additionally, EVPA outperforms other subgame-solving AIs in solving time while maintaining a comparable win-rate. Though it has similar solving times and win-rates to AlphaHoldem, EVPA provides stronger guarantees against exploitability.
Table 4: This table compares various HUNL AIs based estimated training and solving times using 4 NVIDIA 100 80GB PCLe GPUs and 112 Intel(R) Xeon(R) Gold 6348 CPUs. Win-rates indicate performance against Slumbot or Baby Tartanian8, measured in mbb/h. Note that Slumbot is continually improved, so earlier results may not reflect its current performance. X is the training days of the baseline strategy.
HUNL AI Name
Training Time
Solving Time
Win-rate
Tartanian7 (Brown et al.
2015
428 Days
seconds
33 + 16
Baby Tartanian8 (Brown & Sancholm 2016b)
744 Days
0 seconds
36 + 12
Slumbot (Jackson] (013)
93 Days
seconds
0 + 0
DeepStack (Moravčik al.
2017
569 Days
seconds
Libratus (Brown & Sandholm
2018
8, 370 Days
1 66 seconds
63 + 28
Modicum Brown al. 2018)
X + Days
seconds
11 9
ReBeL. (Brown et al. (2020)
926 Days
1 second
45
Supremus (Zarick et al. 2020
351 Days
seconds
176 44
AlphaHoldem (Zhao et al. 2022
6 Days
0.003 seconds
112#16 16
EVPA-ful1-0.2s (Ours)
+ Days
0.2 seconds
96
EVPA--ill-O22--coffusSSttt (Ours)
X + 4 Days
0.2 seconds
187 16
EVPA-169-0.02s (Ours)
+ 4 Days
0.02 seconds
10
C COUNTERFACTUAL REGRET MINIMIZATION
Counterfactual Regret Minimization (CFR) is a prominent algorithm for solving large IEFGs by minimizing regret independently at each information set (Zinkevich et al., 2007b). CFR can find e-Nash equilibrium two-player zero-sum IIFGGs.
*Notably, Supremus AlphaHoldem often make decisions that deviate from Slumbot's blueprint strategy, which may confuse Slumbot. For a fairer comparison with Supremus and AlphaHoldem, we implemented an Al using bet/raise sizes of 0.2. 0.4. 0.8, 1.6 times the pot (EVPA full-0.2s (.s-confuseSlumbbt) The results show that SYPA--ful--.22-coofueel/// mbb/h, surpassing both Supremus and AlphaHoldem.
outperformed Slumbot, achieving win-rate of 187 + 66
16

---

Published as a conference paper at ICLR 2025
(h) is the probability of reaching h if all players act according to strategy =2p(h) is the probability of reaching h if all players expect p act according to strategy o, and the player p act to h. The counterfactual value (CFV) of information set I under strategy profile represents the expected utility to player P(T) if T has been reached, calculated as (T) = (2)))- And the counterfactual value of action is cal- culated as 1 (1, = Ener(T"P(r (h/z) Σnc, (z[h (2))
Ener(="Pin (h)
Let of denote the strategy profile at iteration t. The instantaneous regret for taking an action a at information set I during iteration is given by: r'( vd' (I,a) of (f), where vn' (I.a) is the counterfactual value of taking an action a at I, and 2 (I) is the counterfactual value of the information set I. The accumulated counterfactual regret for taking an action information set after T iterations is: R2 (1,a) = -E r² (1,a). At each iteration t, an action a at information set R2, (J.a)
is selected with probability: (I, E. R2 "1,a")'
where R4 (I,a) max (0, R (I, a)}
Discounted CFR (DCFR) (Brown & Sandholm 2019b) is an advanced variant of CFR designed for large IEFGs. DCFR introduces parameters o, 3 and 7 to adjust the impact of accumulated coun- terfactual regrets over time 6 Specifically, at each iteration i, positive accumulated counterfactual regrets are multiplied by +-+ negative accumulated counterfactual regrets are multiplied by 7+1' and contributions to the average strategy o are weighted by E+1
D DEEPSTACK'S IMPLEMENTATION
Our replication of DtepStack's implementation builds upon several prior works (Moravčkk et al. 2017 Zarick et al. 2020: Brown et al. 2020). At each stage of the game, we construct depth- limited subgame up to the end of that stage and utilize a neural network to estimate the values of the leaf information sets (excluding the river stage).
For the first two levels of the subgame, we employ raising scales of 0.25, 0.5, 1, and times the pot, along with all-in option. For the third level, For subsequent levels, we apply a raising scale of 0.75 times the pot and an all-in option. To enhance sample diversity, we randomly multiply all raising scales (except for all-in) by factor between 0.7 and 1.4. We train 6 neural networks corresponding the following stages: pre-flop stage end, flop stage start, flop stage end, turn stage start, turn stage end, and river stage start. Each network consists of 6 layers of Multi-Layer Perceptrons (MLPs) with ReLU activation functions (Glorot al. 201I). The networks are trained using the Adam optimizer (Kingma & Ba, 2015) and the Huber loss function (Huber 1964). The input layer has 2, 678 dimensions, corresponding the probability of private hands for both players and the public state information. Each hidden layer contains 1, 536 dimen- sions, while the output layer has 2, 652 dimensions, representing the expected value of the private hands.
scales of 0.5 and times the pot, plus all-in.
Training progresses as follows: we first train the river stage network with million randomly gener- ated river subgames, followed by training the turn stage network with 3 million randomly generated turn subgames, the flop stage network with I million randomly generated flop stage subgames, and finally the pre-flop stage network with 100, 000 randomly generated pre-flop scenarios. After this initial training, we regenerate samples from initial states (with initial chips between 50 and 250 big blinds) terminal states for 100 epochs, generating at least 36 million samples in total. After each epoch, we retrain the neural networks using the most recent samples. In the EVPA process for sam- pling and evaluation, we apply the depth-limited subgame building method and leverage the trained neural networks to estimate the values of the leaf information sets.
It is important to note that DeepStack dedicates significant amount of training time computing the information abstraction due to its reliance on offline abstraction methods. To reduce training overhead, our implementation of the DeepStack replica omits this information abstraction step and
$If Ear (T,') = 0, an arbitrary strategy is used.
'In our experimental setup, we use = 1.5, / = 0 and During sample generation, we use the DCFR algorithm (Brown& & Sandholm 2019b) for 1, 000 iterations.
2.
17

---

Published as a conference paper at ICLR 2025
does not fix the initial chip count. Furthermore, inspired by methods such as Supremus (Zarick et al. 2020) and ReBeL (Brown et al. 2020), we incorporate a warm-up phase and then the trained neural network is used to generate subsequent data, allowing for more efficient training process.
E CONCLUSION
In this paper. we propose the Expected- Value Pruning and Abstraction (EVPA) algorithm, which marks significant advancement in solving large imperfect information extensive-form games. EVPA is featured with three core components, namely expected value estimation of information sets, expected value-based pruning, and information abstraction for subgames. Our extensive exper- iments with Heads-up No-Limit Texas Hold' em (HUNL) show that EVPA enhances computational efficiency while ensuring robust strategy development, achieving competitive performance with sig- nificantly reduced solving time compared to existing benchmarks. Its dynamic adaptability positions EVPA as pivotal tool for advancing AI capabilities in complex strategic environments.
F FUTURE DIRECTIONS FOR RESEARCH AND APPLICATION
As EVPA demonstrates significant advancements in solving HUNL, several promising directions for future research emerge.
Generalization to Other IIEFGs. A compelling avenue for future research is to explore the applicability of EVPA across broader spectrum of IIEGGs. While the methodology has been validated in HUNI, expanding its scope to games such as Omaha (Farha & Reback 2007), Mahjong (Li et al. 2020) and Stratego (Perolat et al.) (002) could yield insights into the versatility of the EVPA framework. Understanding how EVPA can efficiently manage diverse information structures and player strategies in these contexts will contribute to more generalized solutions in game theory.
Online Strategy Solving Beyond Board Games. The development of EVPA positions it well for applications beyond board games, particularly in online strategy solving. Many real- world scenarios involve sequential Dacision-making under uncertainty, such as auctions (Milgrom & Weber, 1982) and diplomacy (Bakhtin et al. 2023). Future work could focus on adapting the EVPA framework to these domains, enabling robust online strategy solving that leverages its expected value-based pruning and abstraction techniques. Implementing EVPA in these settings could provide a powerful tool for developing competitive agents capable of navigating complex interactions and dynamic information.
Iniegration with Multi-Agent Systems. EVPA could potentially solve multi-player poker, particularly in tournament settings (Snyder) 2006)] Ganzfried Sandholm (2009), in mere seconds. This capability provides promising entry point for exploring EVPA's application in multi-agent systems. By expanding EVPA's functionalities to operate effectively both collaborative and adversarial environments, involving multiple agents, each with unique strategies and objectives. This exploration will facilitate more sophisticated strategic interactions, proving particularly valuable in domains such as negotiations [Thompson] 1990) and cooperative games (Driessen) 2013).
investigate its adaptability scenarios
By pursuing these research directions, future work can build on the successes of EVPA, enabling the development of robust and adaptable strategies for wide range of sequential decision-making problems beyond poker. This expansion will contribute to the ongoing evolution AI in complex strategic environments, pushing the boundaries of what is achievable in the field of IIEGGs.
G PRUNING WITH CFR
Pruning techniques in CFR help the algorithm avoid exploring suboptimal branches of the game tree, thus improving computational efficiency without sacrificing convergence guarantees (Brown & Sandholm 2015a). One of the most widely used pruning methods is partial pruning (Lanctot et al.) 2009
which reduces unnecessary computations when updating the regret of an information set
Dynamicc thresholding pruning (Brown al. 2017) is similar partial pruning CFR.
18

---

Published as a conference paper at ICLR 2025
belonging one player. Specifically, if the other player has zero probability of reaching any history within an information set, the subgame rooted at that history can be pruned without affecting the overall computation. Formally, for an information set I and the strategy profile of at iteration t, if history h satisfies T- P= (h) O, the subgame rooted at h can be pruned in iteration t. This technique can be combined with EVPA or other pruning methods for even more effective pruning during CFR iterations. However partial pruning techniques are unable to prune the information set belonging to the action player P(T). limiting its pruning rate.
Regret-based pruning (RBP) (Brown & Sandholm 2015a) avoids traversing branches where either player unlikely to take actions with positive probability. the cumulative counterfactual regret R(I,a) S 0 for action in information set I, RBP temporarily prunes the path from / to for -R(L.a)
( iterations,, where UTT a) is the upper bound of u(T, a) and L(T) the lower bound of Althouuhh RBP is efficient for standard CFR, many CFR variants (Brown & Sandholm 2019b; Xu et al., 2024) require more complicated computation of R(I, a). as it is not always a simple cumulative quantity. Additionally, RBP necessitates computing both the upper and lower bounds and recalculating the best response after pruning. These extra computations introduce significant overhead, particularly in real-time solving scenarios.
RespoResponse Pruning (BRP) (Brown & Sandholm, 2017a) is another approach that eliminates suboptimal branches, based the assumption that players will avoid suboptimal actions. For each information set I and action a, BRP computes the best response against the player (1( in a sub- game of non-suboptimal actions. A regret upper bound U for information set I and action with T iterations is derived. If U < O, the path from I to a can be pruned for the next [ itera- tions. While BRP can improve both convergence speed and computational efficiency, it introduces complexity by requiring the computation of the best response each information set during every iteration. This is particularly challenging in depth-limited solving, where best responses calculation costly compared to the depth-limited subgame solving (Moravčík et al. 2017).
Table 5: Comparison of Pruning Methods with CFR.
Pruning Methods
Depth-limited Solving Permanent Pruning
Partial Pruning (Lanctot et al. 2009 RBP BBrwnn & Sandholm
x
2013a
X
XXX
BRP (Brown & Sandholm
2017a
EVPA(Ours)
The comparison of EVPA with previous pruning algorithms summarized in Table 5 ference between EVPA and other pruning methods is that EVPA offers permanent pruning, making it compatible with techniques such as repth-limited solving. Furthermore, EVPA does not require any additional overhead for intermediate value calculations after pruning is completed. This makes EVPA not only more efficient but also more versatile, as it can be seamlessly integrated with various CFR variants. As result, EVPA offers substantial performance improvements without the added computational burden associated with methods like RBP or BRP.
The key dif-
H ABSTRACTION FOR SOLVING LARGE IIEGGS
In large IIEFGs, the size of the game tree often makes it computationally prohibitive to compute an equilibrium. Abstraction algorithms help address this challenge by simplifying the original game into a smaller, abstracted version, which is then solved for equilibrium strategies. While abstraction techniques necessarily sacrifice some accuracy, they are theoretically bounded (Kroer & Sandholm, 2016). However, determining the optimal abstraction remains an NP-complete problem (Sandholm & Singh 2012 Kroer & Sandholm 2014).
Abstraction algorithms typically reduce the complexity of the game tree in the following ways: 1. Information Abstraction GGilpin & Sandholm 2007 Ganzfried & Sandholm] 2014): This method groups similar information sets together, treating them as a single entity with a shared strategy. 2.
Action Abstraction (Brwnn& & Sandholm, 2014 2015b Li et al. 2024): By limiting the available
19

---

Published as a conference paper at ICLR 2025
actions in the game, action abstraction reduces the size of the game tree. 3. Depth-Limited Solving
[rrorr& & Sandholm, 2015 Moravčík et al. 2017: Brown et al. 2018); This approach limits the depth to which the game tree is explored, reducing the computational load. 4. Subgame Solving
(Ganzfried & Sandholm, 2013b; 2015, Brownn & Sandholm 2017c): Instead of solving the entire game tree, subgame solving focuses specific portions of the tree, starting from the current state, to avoid unnecessary computation.
In EVPA, we leverage advanced techniques such action abstraction, depth-limited solving, and subgame solving simultaneously, while also introducing a novel approach to information abstraction. This combination enables us achieve substantial improvements in efficiency and performance. The key advantages of EVPA include: 1. Online Execution: EVPA performs the abstraction in less than second for HUNL subgames, making highly efficient in real-time applications. 2. Efficient Performance: EVPA excels in abstraction quality, providing significant performances in convergence speed and eventual exploitability. When combined with subgame solving techniques, EVPA's abstraction method has more significant advantages over other offline abstraction methods.
20


Reviews:
[{"review_id": "dwQkoZhUi4", "reviewer": "Reviewer_cDdZ", "summary": "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.\nThe evaluation is done by a collection of neural networks, to which the same information set is used as input.\nThe 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.\nBy 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.\nThis 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. \nAdditionally, 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.\nFinally, 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.", "questions": "- 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?\n- Can you please add results where the time limit is increased, up to 2 and 20 seconds, and against DeepStack, for a time budget?\n- For the heads-up results, how many matches have been played? Have you considered using AIVAT to reduce variance?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- 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.\n- Strong performance on poker games.", "weaknesses": "- 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.\n\n- 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.\n\n- The text is a bit repetitive. Instead, I would appreciate more involved discussion of prior abstraction literature and how this work differs.", "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": "", "extra_scores": {}}, {"review_id": "nX4IduPfl0", "reviewer": "Reviewer_Ce7c", "summary": "***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.", "questions": "**Detailed questions and comments.** For the three techniques this paper proposes, I have several concerns and questions.\n\n1. 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.\n\n\n2. 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.\n\n3. 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]", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The presentation is clear.", "weaknesses": "Some technical points are not sound.", "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": "", "extra_scores": {}}, {"review_id": "GeckvcsEpO", "reviewer": "Reviewer_jemo", "summary": "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.", "questions": "* Can the authors please comment on the quality of Deepstack's replication? How does it perform against local best response (LBR)?\n\n* In the experiments in Table 2, what happens with longer solving times?\n\n* How do we ensure pruning does not severely impact the quality of the final strategy?\n\n* 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* 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.\n* Significant portions of the game tree are successfully pruned, though it's unclear what that means for correctness.\n* 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.", "weaknesses": "* 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?\n\n* 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?\n\n* 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.", "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": "", "extra_scores": {}}, {"review_id": "x6UgGD9xMx", "reviewer": "Reviewer_85Xa", "summary": "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.", "questions": "* 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?\n* 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$. \n* 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? \n* 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.\n* What are the confidence intervals in Table 1 and Figure 3?\n* (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.\n* Will the code be released to assist research in the field?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* 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.\n* The paper provides good experimental results demonstrating improved performance over Deepstack's replication and Slumbot.", "weaknesses": "* The papar lacks experimental comparisons with other pruning and abstraction methods. \n* 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. \n* The performance gains from information set abstraction are marginal, and this leads to exploitability not decreasing in the later iterations.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)