Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play

Authors: ju  qi
hei  falin
feng  ting
yi  dengbing
fang  zhemei
luo  yunfeng
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:43:29

Abstract: Counterfactual Regret Minimization (CFR) and its variants are widely recognized as effective algorithms for solving extensive-form imperfect information games. Recently, many improvements have been focused on enhancing the convergence speed of the CFR algorithm. However, most of these variants are not applicable under Monte Carlo (MC) conditions, making them unsuitable for training in large-scale games. We introduce a new MC-based algorithm for solving extensive-form imperfect information games, called MCCFVFP (Monte Carlo Counterfactual Value-Based Fictitious Play). MCCFVFP combines CFR’s counterfactual value calculations with fictitious play’s best response strategy, leveraging the strengths of fictitious play to gain significant advantages in games with a high proportion of dominated strategies. Experimental results show that MCCFVFP achieved convergence speeds approximately 20\%$\sim$50\% faster than the most advanced MCCFR variants in games like poker and other test games.

Main paper: 
 introduction: 
 Game theory investigates mathematical models of strategic interactions among rational agents, aiming to identify a Nash Equilibrium (NE) where no participant can gain by deviating from the established strategy. For complete information games, it is possible to segment the game into smaller sub-games and apply backward induction to determine the equilibrium. In contrast, in incomplete information games, the inability to directly apply sub-game payoffs in the backward induction algorithm significantly increases the complexity of finding an equilibrium.The Counterfactual Regret Minimization (CFR) algorithm Zinkevich et al. [2007] is crucial for solving extensive-form games with incomplete information. CFR has numerous variants, such as CFR+ Tammelin [2014] , Lazy CFR Zhou et al. [2018] , PCFR Farina et al. [2021] , DCFR Brown and Sandholm [2019a] , and PDCFR Xu et al. [2024] . Nevertheless, these variants typically require a full traversal of the entire game tree, which is impractical for real-world applications. In contrast, games like no-limit Texas hold'em, DouDizhu, and Mahjong have 10 162 Moravík et al. [2017] , 10 83 Zha et al. [2021] , and 10 121 Li et al. [2020] information sets, respectively, making full traversal infeasible.To address this, Lanctot et al. Lanctot et al. [2010] proposed Monte Carlo CFR (MCCFR), which reduces the number of game tree nodes visited in each iteration through sampling. This makes MCCFR the preferred algorithm for training large-scale games. However, most CFR variants cannot improve the convergence speed in the case of MCCFR. Only a few variants, such as Discount MCCFR Brown and Sandholm [2019a] and VR-MCCFR Schmid et al. [2019] , are currently suitable for MCCFR. Therefore, it is crucial to study the characteristics of large-scale games and how to leverage these characteristics to accelerate the convergence of MC-based game learning algorithms.We believe that the Fictitious Play (FP) algorithm is highly suitable for addressing large-scale incomplete information games, due to the characteristics of using the best response (BR) strategy. FP was first introduced in Brown's 1951 article Berger [2007] ; Brown [1951] . The treatise The Theory of Learning in Games Fudenberg and Levine [1998] consolidated prior research, setting a standardized framework for FP . Generalized Weakened Fictitious Play (GWFP) Leslie and Collins [2006] further established that under specific perturbations and errors, convergence to NE is attainable in a manner consistent with FP . Hendon et al. Hendon et al. [1996] expanded FP to the domain of extensive-form games. The development of the Full-Width Extensive-Form Fictitious Play (XFP) algorithm Heinrich et al. [2015] , predicated on GWFP, has facilitated faster convergence in these games.Our algorithm, Monte Carlo Counterfactual Value-Based Fictitious Play (MCCFVFP), optimizes FP in extensive-form games by incorporating counterfactual value into the BR strategy calculations. We have theoretically proven that MCCFVFP can converge to a NE, and experimentally demonstrated that in large-scale games, MCCFVFP fully leverages the high proportion of dominated strategies to achieve faster convergence speeds than MCCFR. Our code can be found at GitHub.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: I believe that the abstract and introduction accurately reflect the contribution and scope of the paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
notation and preliminaries: 
 2.1 Game TheoryThe normal-form game serves as the foundational model in Game Theory. Let N = 1, 2, . . . , i, . . . represent the set of players, where each player i has a finite action set A i . Player i's strategy, denoted σ i , is a probability distribution over A i and is represented by a (|A i | -1)-dimensional simplex. Here, | • | indicates the cardinality of the set, and σ i (a ′ ) denotes the probability with which player i selects action a ′ . Let Σ i denote the strategy set for player i, such that σ i ∈ Σ i . A strategy profile, σ = i∈N σ i , represents the collection of strategies for all players, while σ -i = (σ 1 , . . . , σ i-1 , σ i+1 , . . . ) includes all strategies in σ except for that of player i. The entire set of strategy profiles is denoted by Σ = i∈N Σ i , where σ ∈ Σ. The payoff function for player i, defined as u i : Σ → R, is finite. The notation u i (σ i , σ -i ) indicates the expected payoff to player i when they select the pure strategy σ i and all other players follow the strategy profile σ -i . Finally, define the payoff interval of the game as L = max σ∈Σ,i∈N u i (σ) -min σ∈Σ,i∈N u i (σ).In extensive-form games, typically represented as game trees, the player set is N = 1, 2, . . .. Each node s represents a possible state in the game, forming a set S, with terminal states represented by leaf nodes z ∈ Z. At each state s ∈ S, the action set A(s) includes all possible actions available to a player or chance. The player function P : S → N ∪ c assigns each state an acting party, with c indicating a chance event. Information sets I ∈ I i group states that player i cannot distinguish among, reflecting their uncertainty. The payoff function R : Z → R |N | maps each terminal state to a payoff vector for the players. For each information set I ∈ I i , the behavioral strategy σ i (I) ∈ R |A(I)| defines a probability distribution over available actions.The BR strategy of player i to their opponents' strategiesEQUATIONalthough a mixed strategy may also become a BR strategy, it is much easier to find a pure BR strategy than a mixed BR strategy in engineering implementation, so the BR strategies discussed in this article are all pure BR strategies. If there are multiple BR strategies at the same time, one of them will be returned randomly. Define the exploitability ϵ i of player i in strategy profile σ as:EQUATIONand total exploitability as ϵ = i∈N ϵ i . A Nash equilibrium is a strategy profile σ such that ϵ = 0.During iterations, if the strategy's exploitability satisfies ϵ ∝ T -1 2 , the convergence rate of the algorithm is O T -1 2 . Additionally, the time complexity within one iteration is a critical factor affecting the convergence rate. We use O(•) to describe the time complexity needed for one iteration.In game theory, strategic dominance occurs when one action (or strategy) is better than another action (or strategy) for one player, regardless of the opponents' actions. A classic example is the Prisoner's Dilemma, where choosing to testify always yields a higher payoff than staying silent, regardless of the opponent's decision. Here, staying silent is a dominated strategy. Formally, For player i, if there is a pure strategy a i * and a strategy σ i * ∈ Σ i satisfies:EQUATIONthen the pure strategy a i * is a dominated strategy of player i. Rational players will invariably avoid choosing a dominated strategy, allowing the elimination of dominated strategy from the action set A i without impacting the game's NE Samuelson [1992] .In our analysis, the proportion of dominated strategies in a game is crucial, significantly impacting the convergence speed of various algorithms. We categorize games into two distinct types based on this factor. Games where the number of dominated strategies is less than |A| are classified as clear games. This term captures a strategic landscape where the preferable choices are evident, owing to the relatively few dominated strategies. On the other hand, tangled games are defined by having a number of dominated strategies greater than |A|, reflecting a more complex and nuanced strategic environment with less obvious choices. The reason for defining these categories in this way can be found in Appendix B.3. Such classification aids in comprehending a game's nature and assessing the effectiveness of different algorithmic approaches.In normal-form games, let σ i t be the strategy used by player i on round t. The regret of player i's action a i at time T is:EQUATIONThe new strategy is produced by:EQUATIONwhere R i,+ T (a) = max R i T (a), 0 . Since the probability of selecting action σ i t+1 (a) is proportional to the non-negative regret value R i,+ T (a) for this action, this algorithm is referred to as the regret matching algorithm. Define the average strategy as σT = 1 T T t=1 σ t , which converges to the NE as T → ∞, with a convergence rate of O L |A|/T . In each iteration, RM requires a matrix multiplication operation, resulting in an iteration time complexity of O |A| 2 .CFR is a variant of RM specifically adapted for extensive-form games. The counterfactual value u(I, σ) is defined as the expected payoff assuming that information set I is reached and all players follow strategy σ, with the exception that player i acts specifically to reach I. For each action a ∈ A i (I), let σ| I→a represent a strategy profile identical to σ except that player i consistently chooses action a within information set I. The counterfactual regret is then given by:EQUATIONwhere π -i σt (I) is the probability of information set I occurring if all players (including chance, except i) choose actions according to σ t . Let R i,+ T (I, a) = max R i T (I, a), 0 , the strategy at time T + 1 is:σ i T +1 (I, a) =    R i,+ T (I,a) a∈A(I) R i,+ T (I,a) if a∈A i R i,+ T (I, a) > 0 1 |A(I)| otherwise. (7)The average strategy σi T for an information set I on iteration T is:EQUATIONEventually, σT will converge to NE with T → ∞, the convergence rate of CFR is O L|I| |A|/T and the time complexity of one iteration of the CFR algorithm is O (|A||I|).There are many forms of sampling MCCFR, but the most common is external sampling MCCFR (ES-MCCFR) Brown [2020] because of its simplicity and powerful performance. In ES-MCCFR, some players are designated as traversers and others are samplers during an iteration. Traversers follow the CFR algorithm to update the regret and the average strategy of the experienced information set. On the rest of the sampler's nodes and the chance node, only one action is explored (sampled according to the player's strategy for that iteration on the information set), and the regret and the average strategy are not updated.FP assuming all players start with random strategy profile σt=1 , the strategy profile is updated following the iterative function:EQUATIONwhere in vanilla FP α t = 1/(t + 1), σ t+1 = b(σ t ). The convergence rate of vanilla FP in a two-player zero-sum game may be O √ T Daskalakis and Pan [2014] , and the time complexity of one iteration of the vanilla FP algorithm is O |A| 2 . To speed up iteration, define the average Q-value of player i's action a i at time T as:EQUATION)If the game is a two-player game, or if u i is an affine function (e.g., in a potential game), we have:EQUATIONtherefore, we can conclude that b i (σ -i ) = maxEQUATIONIn 2.1.3, it is noted that BR strategy σ i t in FP is a pure strategy. As a result, calculating u i (a i , σ -i t ) involves simply selecting a row (or column) from the payoff matrix, eliminating the need for matrix multiplication as required in RM. Consequently, the time complexity of each iteration in the FP algorithm decreases to O(|A|), representing a significant improvement over the O(|A| 2 ) complexity in RM.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: At the end of the paper we pointed out that our algorithm needs larger-scale experiments and is combined with more CFR variants.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
motivation of cfvfp: 
 Currently, the mainstream approach for large-scale games is a combination of "pre-trained blueprint strategy + real-time search." For example, Pluribus initially employs the MCCFR algorithm to establish a blueprint strategy, which it applies in the early stages of the game, and then transitions to real-time search as the game progresses Brown and Sandholm [2019b] . Similarly, in the game of Go, AlphaGo primarily used reinforcement learning to train its policy and value networks, incorporating a limited number of MCTS rollouts during training. However, in actual matches against human experts, AlphaGo significantly increased the number of MCTS rollouts to enhance its real-time decisionmaking Silver et al. [2016 Silver et al. [ , 2017]] . This phenomenon can be understood from two perspectives:1. The complexity of real-world games is so high that it is impossible for any single strategy (even with deep networks) to perfectly handle all game scenarios. Due to this extreme complexity, only sampling-based training methods are feasible. Many current improvements to CFR, such as CFR+ and Predictive CFR, are designed for full traversal of the game tree. While these methods accelerate convergence, they are unsuitable for sampling-based approaches because the inexact payoffs introduced by sampling significantly disrupt the convergence direction of each strategy update.2. Training a blueprint strategy usually starts with sampling from the initial nodes, resulting in a higher probability of exploring early game nodes compared to leaf nodes. Consequently, while the blueprint strategy might be less effective in the later stages of the game, it often rapidly converges towards the optimal solution in the early stages due to thorough exploration.After clarifying the specific ideas for training large-scale game AI. Next, we need to think about the characteristics of large-scale games and how to design corresponding MC-type solving algorithms based on these characteristics.One prominent characteristic of large-scale games is that the majority of strategies are dominated. For instance, in chess and Go, top AI systems and human experts often opt for fixed openings.Similarly, professional poker players tend to fold most hands in the early rounds. Theoretically, DeepMind likens game strategies to a spinning top Czarnecki et al. [2020] , implying that only a limited subset of strategies can be considered non-dominated. MCCFR experiments show that up to 96% of strategies can be pruned in certain games Lanctot et al. [2010] . Likewise, the supplementary materials of Pluribus Brown and Sandholm [2019c] reveal that around 50% of information sets are never encountered during training (indicating that unplayed strategies are almost certainly dominated, with many traversed ones also being dominated). In other words, while it cannot be proven with absolute certainty, the choices of professional players and the experimental outcomes from current advanced AIs suggest that the larger the game, the higher the likelihood that it can be classified as a "clear game."Additionally, our toy experiment clearly demonstrates that the FP algorithm is more effective for clear games compared to the RM algorithm 1. We attribute this advantage to the fact that FP employs the BR strategy rather than the RM strategy during iterations, which is why we aim to incorporate this feature into the iterations of CFR. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: The code we provide can ensure that the results of this paper are reproduced, but this paper relies on the assumption that large-scale games are a clear game, which is not necessarily 100% certain in large-scale games.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
counterfactual value fictitious play implementation: 
 Our method can be easily adapted from CFR. First, there is no need to compute the counterfactual regret; instead, we define the counterfactual value:EQUATIONSecond, the strategy in the next iteration is a BR strategy rather than RM strategy:EQUATIONThe main distinction between Q i t and R i t is that Q i t omits the average payoff term u i (I, σ t ), as this term does not affect identifying the maximum value of Q i t . This omission leads to a significant reduction in computation time. Since arg max selects the action with the highest counterfactual value, the resulting strategy in each iteration is a pure strategy, similar to the FP algorithm. Thus, we refer to this algorithm as Counterfactual Value-Based Fictitious Play. Additionally, the time complexity of calculating the BR strategy is notably lower than that required for computing the RM strategy.Finally, since the update σ i t+1 is a pure strategy, π -i σt (I) is either 0 or 1. This significantly increases the likelihood of triggering naive pruning. From equation 6, we see that if π -i σt (I) = 0, it is unnecessary to enter the sub-game tree to calculate Q i t (I, a). Similarly, equation 8 shows that if π i σt (I) = 0, it is unnecessary to update the average strategy σi t (I). This pruning greatly enhances the algorithm's efficiency.CFVFP employs a simple yet effective approach by using BR strategy instead of regret-matching strategy for next iteration. The convergence of CFVFP can be easily proven. First, FP's convergence to a NE classifies it as a regret minimizer Abernethy et al. [2011] , which also implies that FP satisfies Blackwell approachability Blackwell [1956] . The CFR framework shows that if an algorithm satisfies Blackwell approachability, its counterfactual regrets will converge to zero Zinkevich et al. [2007] . Therefore, CFVFP inherently adheres to Blackwell approachability. Moreover, we can directly begin with the definition of Blackwell approachability and prove that FP fulfills this criterion. The convergence rate is O L|A|T -1 2 , and the detailed proof can be found in B.1. The pseudocode for the CFVFP algorithm is provided in Appendix C.1.Since CFVFP follows Blackwell approachability, it is fully compatible with various CFR variants, including MCCFR, CFR+, and different averaging schemes Brown and Sandholm [2019a] , resulting in a range of CFVFP variants. Consequently, we conducted a series of experiments to examine the convergence rates of these CFVFP variants. As detailed in Appendix B, the vanilla-weighted MCCFVFP, a combination of MCCFR and CFVFP, shows the fastest convergence among the variants. The pseudocode for the MCCFVFP algorithm is provided in Appendix C.2.We discuss the advantages of the MCCFVFP algorithm in terms of the computing resources required per information set and the algorithm's pruning efficiency.The MCCFVFP algorithm is highly efficient in conserving computing resources. For example, if an information set has |A(I)| = x possible actions, MCCFVFP only requires 2x + 1 additions to process this information set, whereas MCCFR needs 6x -2 additions and 3x multiplications to complete the same calculation. This means that, for a single information set, MCCFVFP requires only about 2/9 of the computational time compared to MCCFR. Considering that a Blueprint training typically traverses at least 1 billion nodes, MCCFVFP offers significant advantages over MCCFR in terms of engineering implementation. For a detailed proof, refer to Appendix E.1.Additionally, CFVFP is highly efficient in game tree pruning. Pruning is a common optimization technique used in all tree search algorithms. For instance, the Alpha-Beta algorithm in completeinformation extensive-form games is a pruned version of the Min-Max algorithm, and it was a key factor in Deep Blue's success Hsu [2002] . Naive pruning is the simplest pruning method in CFR. In naive pruning, if no player has a probability of reaching the current state s (∀i, π -i σt (s) = 0), the entire subtree at that state can be pruned for the current iteration without affecting regret calculations.By analyzing the frequency of different node types in the game tree, we theoretically prove that CFVFP can significantly reduce the number of nodes that need to be processed. Compared to CFR, which must traverse all O (|S|) nodes, CFVFP only needs to traverse O |N | |S| nodes. This is especially beneficial in multiplayer games, where it greatly improves the efficiency of algorithm iterations. For detailed proof, please refer to Appendix E.2. 
description of the game and experimental settings: 
 We employed various game models, such as Kuhn-extension poker, Leduc-extension poker, the princess and monster game Lanctot et al. [2010] , and Texas Hold'em, to evaluate the performance of different algorithms. These games are widely used benchmarks for comparing algorithmic convergence rates. Kuhn-extension poker, an expanded version of the classic Kuhn poker Kuhn [1950] , features an increased card count of x, a broader range of betting actions with y options, and up to z raising opportunities. Similarly, Leduc-extension poker is an advanced version of the original Leduc poker Shi and Littman [2002] , allowing for flexible scaling. The princess and monster game represents a classic pursuit-evasion problem. Texas Hold'em, one of the most popular poker games in the world, was also included in our analysis.In Kuhn, Leduc, and princess and monster games, we use a random distribution as the initial strategy to initialize all algorithms. In each iteration, the strategies and regrets of all players are updated simultaneously. In MCCFR, when R i,max t = 0, the next stage strategy is set to a random pure strategy. In addition, the settings in our comparison experiment are consistent with those in previous groundbreaking works, including MCCFR Lanctot et al. [2010] , DCFR+ Brown and Sandholm [2019a] , and PCFR Farina et al. [2021] . For engineering implementation, any node with a probability less than 10 -20 during iteration will be pruned. Our Texas Hold'em experiments employed a variant of the multivalued state technique Brown et al. [2018] , with an experimental setup closely mirroring that of Pluribus Brown and Sandholm [2019b] . The Texas Hold'em experiments were run on a 32-core, 128GB memory server, while the other experiments were conducted on a single core. It is important to note that all times mentioned below have been converted to reflect execution on a single CPU core.For a comprehensive exposition of these games and additional experimental findings, please refer to Appendix F. In Appendix G, we compare time, number of iterations, and nodes touched as an indicator. Finally, we use nodes touched and time as an indicator.As shown in the Figure 2 , we can demonstrate the core findings of our paper:• In small-scale problems like vanilla Kuhn, algorithms such as DCFR, PCFR, and CFR+ may outperform MCCFR and MCCFVFP. However, as the game scale increases, the convergence speed of sampling-based algorithms (MCCFR/MCCFVFP) gradually surpasses that of full-traversal algorithms (DCFR/PCFR/CFR+).• In our experiments, MCCFVFP consistently converged faster than MCCFR. While theoretically, our algorithm might be less effective than MCCFR in tangled games, the acceleration in its implementation and the tendency of large-scale games to be clear games have led to MCCFVFP outperforming MCCFR in all tested scenarios. Specifically, when using the number of nodes touched as a metric, MCCFVFP demonstrates a slightly faster convergence rate compared to ES-MCCFR. However, in terms of processing the same number of nodes, MCCFVFP's computation time is only about 2/9 of MCCFR's (the underlying reasons are discussed in Section E.1). As a result, when factoring in the time required for game simulation, MCCFVFP achieves approximately 50% time savings compared to ES-MCCFR for similar levels of exploitability in these games.As previously noted, algorithms such as CFR+, PCFR, and DCFR are not well-suited for large-scale games due to their reliance on full traversal, which is impractical in complex settings like Texas Hold'em. Therefore, in our Texas Hold'em experiments, we focused on comparing the performance of our algorithm specifically against the traditional MCCFR method, excluding these full-traversal algorithms from testing.In our experiments, we used 2, 3, and 6-player Texas Hold'em game setups, where each player started with 25 Big Blinds (BB) in chips. We assumed that all players would check from the start of the game through to the river stage, simulating a conservative gameplay scenario to examine strategic strengths under limited betting dynamics.In the two-player Texas Hold'em game, convergence speed can be directly measured using exploitability. The results are shown in Table 1 . The public cards in the experiment were 5d2s9d2c7c, and after abstracting the hands, there were 69 hand strength ranks. This sub-game contains approximately 89k information sets, with exploitability measured in BB/100. Compared to MCCFR, MCCFVFP achieved a 20-30% faster convergence speed within the same time frame in the two-player Texas Hold'em game. In multiplayer situations, the exploitability cannot be directly calculated. Therefore, we use the method of mutual battles to measure the strength of different algorithms. As shown in Table 2 , in the competition 1, MCCFVFP AI is randomly set as player i, and all other players except player i are set as MCCFR AI. Define r 1 as the rewards of the MCCFVFP AI player at competition 1. The second setting is exactly the opposite. Player i is randomly set as MCCFR AI, and the remaining players are set as MCCFVFP AI. Define r 2 as the rewards of the MCCFR AI player at competition 2. By comparing r 1 and r 2 , we can roughly compare the convergence speeds of different algorithms.In these scenarios, the MCCFVFP AI, trained for the same duration, significantly outperforms the MCCFR algorithm across all aspects. The 30 to 40 seconds training experiment is particularly important, as it closely mirrors the setup of the Pluribus experiment. In the 6-player Pluribus experiment, the AI trained with MCCFR gained an average of 3.2 BB/100 per game, with a standard error of 1.5 BB/100. In our experiment, using community cards KsQsJs3h2h, MCCFVFP gained an average of 0.932 BB/100 compared to MCCFR-a substantial improvement, especially considering Pluribus gained 3.2 BB/100 against human players. 
conclusion: 
 This paper introduces a novel method for solving large-scale incomplete information zero-sum games: Monte Carlo Counterfactual Value-Based Fictitious Play (MCCFVFP). By implementing the BR strategy in place of the regret-matching strategy, MCCFVFP achieved convergence speeds approximately 20% to 50% faster than the most advanced MCCFR variants.In future research, we aim to evaluate the scalability of our method and its compatibility with different CFR variants, including those incorporating deep networks Brown et al. [2019] . Furthermore, given MCCFVFP's efficacy in clear games, we envision developing a warm start algorithm. This approach would initially use MCCFVFP to eliminate dominated strategies and then switch to algorithms that can further accelerate convergence in the later stages of training.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [No] Justification: Our Texas Hold'em experiments were conducted using a commercial solver, so we are unable to share this part of the code. However, the experiments on smaller-scale games have been made publicly available.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: All our experiments are labeled with confidence intervals.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our work is very theoretical and there is no need to discuss social implications. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Our research does not cover this aspect. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: In training, RM and its variants do not perform well in the clear games, which we attribute to excessive exploration of dominated strategies by RM. For instance, consider the rock-paper-scissors (RPS) game, where an additional action, Leaky Rock (LR), is introduced for player 1. Set the payoff of action LR to be 0.1 less than that of action Rock (R) (making LR a dominated strategy that no rational player would choose):EQUATIONAssuming that player 1 starts with an average strategy and player2 takes scissors in the first round, player 1's payoff isu 1 = 0.225. The regret value is R 1 (R) = 1 -0.225 = 0.775, R 1 (S) = 0 -0.225 = -0.225, R 1 (P) = -1 -0.225 = -1.225, R 1 (LR) = 0.9 -0.225 = 0.675, Under the RM algorithm, the probability of selecting Rock in the next iteration becomes: σ 1 (R) ≈ 0.534, and for the Leaky Rock action: σ 1 (LR) ≈ 0.466. Despite LR being a dominated strategy, RM still assigns it nearly half the selection probability, arguably wasting nearly half the computational resources. However, in Fictitious Play (FP), the LR action would never be chosen.Definition 1 A Blackwell approachability game in normal-form two-player games can be described as a tuple (Σ, u, S 1 , S 2 ), where Σ is a strategy profile, u is the payoff function, andS i = R |A i | ≤0 is a closed convex target cone. The Player i's regret vector of the strategy profile σ is R i (σ) ∈ R |A i | , for each component R i (σ)(a x ) = u i a x , σ -i -u i (σ) , a x ∈ A ithe average regret vector for players i to take actions at T time a is RiEQUATIONAt each time t, the two players interact in this order:• Player 1 chooses a strategy σ 1 t ∈ Σ 1 ; • Player 2 chooses an action σ 2 t ∈ Σ 2 , which can depend adversarially on all the σ t output so far;• Player 1 gets the vector value payoff R 1 (σ t ) ∈ R l 1 .The goal of Player 1 is to select actions σ 1 1 , σ 1 2 , . . . ∈ Σ 1 such that no matter what actions σ 2 1 , σ 2 2 , . . . ∈ Σ 2 played by Player 2, the average payoff vector converges to the target set S 1 .EQUATIONBefore explaining how to choose the action σ t to ensure this goal achieve, we first need to define the forceable half-space:Definition 2 Let H ⊆ R d as half-space, that is, for some a ∈ R d , b ∈ R, H = x ∈ R d : a ⊤ x ≤ b .In Blackwell approachability games, the halfspace H is said to be forceable if there exists a strategy σ i * ∈ Σ i of Player i that guarantees that the regret vector R i (σ) is in H no matter the strategy played by Player -i, such thatR i σ i * , σ-i ∈ H ∀σ -i ∈ Σ -i (18)And σ i * is forcing action for H.Blackwell's approachability theorem states the following. The relationship between Blackwell approachability and no-regret learning is:Theorem 2 Any strategy (algorithm) that achieves Blackwell approachability can be converted into an algorithm that achieves no-regret, and vice versa Abernethy et al. [2011] Let σi T be the average strategy of player i:EQUATIONIn a two-player zero-sum game, the exploitability of the average strategy σi T at time T of player i is ϵ i T = max a ′ ∈A i Ri T (a ′ ) Brown [2020] . Obviously, the regret value is always greater than the exploitability: limEQUATIONSo, if the algorithm achieves Blackwell approachability, the average strategy σi T will converge to equilibrium with T → ∞. The rate of convergence isϵ i T ≤ Ri T ≤ L |A|/ √ T .We first prove that FP achieves Blackwell approachability in a two-player zero-sum game. Define Ri,max H P t = z ∈ R l -i : ( Ri t -ψ t ) ⊤ z ≤ ( Ri t -ψ t ) ⊤ ψ t (21)Because Ri t -ψ t = Ri,max t , ( Ri t -ψ t ) ⊤ ψ t = 0, therefore:H P t = z ∈ R l -i : Ri,max t , z ≤ 0 (22)For any point s ′ ∈ S i there is Ri,max t , s ′ ≤ 0. Then we need to prove that a forcing action for H P t indeed exists. According to Definition 2, we need to find a σ i * t+1 ∈ Σ i that achievesR i σ i * t+1 , σ-i t+1 ∈ H i,P t+1 for any σ-i t+1 ∈ Σ -i . For simplicity, let ℓ = [u i a 1 , σ -i , . . . ] ⊤ ∈ R |A i | ,we rewrite the regret vector as R i σ i * t+1 , σ-i t+1 = ℓℓ, σ i * t+1 1, we are looking for a σ i * t+1 ∈ Σ i such that:EQUATIONWe obtain the strategyσ i * t+1 = Ri,max t ∥ Ri,max t ∥ 1that guarantees H P t+1 to be forceable half space. And the action with the highest regret value is actually the BR strategy Brown [2020] , so FP achieves Blackwell approachability. Figure 3 shows the difference in forceable half spaces for BR and RM strategies in the two-dimensional plane. According to 2, BR strategy is also a regret minimizer in normal-form game. Therefore, replacing the RM strategy with the BR strategy in CFR does not affect the convergence of the algorithm.However, it is important to note that the convergence point of FP differs from that of RM . Specifically, the convergence point for FP is ψ t = Ri t -Ri,max T .In Section 3, we have analyzed that the RM strategy may select a dominated strategy, whereas FP will not. Therefore, representing the complexity of the problem using |A| for FP is inaccurate. If an action a ′ is a dominated strategy, then it cannot be the best response, i.e., b(σ) ̸ = a ′ . Hence, in FP, we can replace |A| with And, where A i nd ⊆ A i is the set of non-dominated strategies in the game. This adjustment leads to the FP convergence rate being O L|A nd |/ √ T .We now define a "clear game" as follows: when the number of non-dominated strategies in a game satisfies |A nd | ≤ |A|, the game is considered a clear game. In Figure 1 , the square root of 100 is 10, aligning with theoretical expectations. In clear games, even when the number of iterations is used as a measure, the convergence speed of FP will outperform that of RM.The pseudocode 1 here does not join the rest of the variants, nor does it consider cases other than two-player zero-sum.Since MCCFVFP will directly sample actions on opportunity nodes, the efficiency of the MCCFVFP algorithm will be higher than CFVFP. The pseudocode of MCCFVFP is shown in pseudocode 2.Algorithm 1 CFVFP(s, π, π c )1: if π 1 = π 2 = 0 or π c = 0 then 2: return [0, 0] 3: end if 4: if s ∈ Z then 5:return u 1 (s)π 2 π c , u 2 (s)π 1 π c 6: end if 7: Define I as the information set to which s belongs 8: r = [0, 0] 9: if P (s) = c then r ′ = CFVFP(s + a, π, π c ) 40: Q ps t (I, a) = Q ps t-1 (I, a) + r ′ (p s ) 41: r(p o ) = r(p o ) + r ′ (p o ) 42: r(p s ) = r(p s ) + r ′ (p s )σ ps t (I,We integrated CFVFP with RM+ and MC variants, resulting in four distinct combinations: CFVFP, CFVFP+, MCCFVFP, and MCCFVFP+. Figure 4 clearly illustrates that MCCFVFP and MCCFVFP+ consistently outperform CFVFP and CFVFP+ in terms of results. However, the performance of Algorithm 2 MCCFVFP(s, π)1: if π 1 = π 2 = 0 then 2: return [0, 0] 3: end if 4: if s ∈ Z then 5:return u 1 (s)π 2 , u 2 (s)π 1 6: end if 7: Define I as the information set to which s belongs 8: r = [0, 0] 9: if P (s) = c then π s , π o = π 2 , π 1 19: p s , p o = p 2 , p 1 20: end if 21: if π o = 0 then 22: r ′ = MCCFVFP(s + σ t (I), π) 23: r(p o ) = r ′ (p o ) 24: σps t (I) = ((t -1)σ ps t-1 (I) + σ ps t (I))/t 25: else if π s = 0 then 26:for a ∈ A(I) do 27:r ′ = MCCFVFP(s + a, π)28:Q ps t (I, a) = Q ps t-1 (I, a) + r ′ (p s ) 29:if a = σ ps (I) then end if 45: end if 46: return r MCCFVFP and MCCFVFP+ varies across different problem sets. Based on these observations, we ultimately selected the more conservative MCCFVFP method.Different weights of CFVFP will also have a significant impact on the results. The weight w t is introduced into Q i t (I): The calculations required for CFVFP in one information set are: 6. Get regret matching strategy, this step x multiplications; 7. Update the RM strategy to the average strategy, this step needs x additions; A total of 6x -2 additions and 3x multiplications. It can be seen that in one information set, CFVFP only takes 2/9 of the time of CFR .EQUATION)In a deterministic game tree with h levels and g actions per node (no chance nodes), such as a g = 3, h = 4 scenario depicted in Figure 6 , nodes are categorized into four distinct types (s all = (s r , s g , s b , s y )).• The probability of all players reaching this node is 1 (red node s r );• The probability of all players reaching this node is 0 (green node s g ), and these nodes can be pruned;• The probability of the current player reaching this node is 1, and the probability of other players is 0 (blue node s b );• The probability that the current player reaches this node is 0, and the probability of other players is 1 (yellow node s y );We define the nodes that must be touched as s pass=(sr,sb,sy) . The figure shows that each level has a single red node, with yellow and green nodes following a blue node, which is derived from red and yellow nodes. The function F h (s x ) quantifies the count of each node type across layers 1 to h.EQUATIONthe general term formula for blue node s b in the h layer is:EQUATIONafter simplification:EQUATION)The number of nodes that need to be touched s pass in the h level game tree is:EQUATIONEQUATIONThe number of node s all of the entire h level game tree is:EQUATIONIn a two-player game, it can be approximately considered that F h (s all ) ∝ F h (s pass ), so CFVFP F.1 Description of the gameWe have made improvements to Kuhn and Leduc Poker:1. The original Leduc and Kuhn poker types are 3 cards, and in the improved game the types are x ≥ 3 cards;2. The original Leduc and Kuhn can only raise one fixed chip, but in the improved game it is allowed to raise y ≥ 1 chips of various sizes. The Bet Action raise size here adopts an equal proportional sequence in multiples of 2. For example, when the blind bet is 1 and y = 4, the allowed raise action is [1, 2, 4, 8];Princess and monster (PAM) is a game in which two players chase and escape in a dungeon with obstacles (a 4-connected grid diagram of m × n). The game rule is:• The two players are monster and princess, and each player knows the structure of the dungeon and which rooms can be accessed. • They can only exist in one particular dungeon at a time, and they all know the number of their current dungeon (grid). • The monster's goal is to find and capture the princess as soon as possible.• The princess's goal is to escape the monster as much as possible.The actions they can choose are:• In the initial stage, monster and princess can choose any birth room to start the game; • In the following process, monster and princess can choose to move one space per step in four directions, up, down, left and right, or stay in place. When moving, they cannot exceed the dungeon boundary or enter impassable rooms.Result of the game:• At the same time, if the monster and princess appear in the same dungeon, the game ends.The princess survives the n round and gets n utilities, and the corresponding monster gets -n utilities. • If the monster does not capture the princess within a certain number of steps (such as N move), the game ends directly. The princess earns N utilities and the monster earns -N utilities.Figure 7 : The structure of the dungeon.As shown in Figure 7 , we set the dungeon to a 3×3 grid, with inaccessible rooms in the upper left and right corners.We measured the number of information sets and the number of nodes in different games in Table 3 , and there are rest of the experimental results in Figure 8 .In previous papers, many convergence analyses were performed based on the number of iterations T , which is obviously unfair to the sampling CFR/CFVFP algorithm. For sampling algorithms, many studies have used the number of nodes to analyze the convergence of the algorithm, but these studies have ignored the inconsistent calculation time of different nodes and the inconsistent number of information sets that have passed through the same node. The cost of an iteration in CFR/CFVFP is divided into two parts: the game tree traversal cost and the RM/BR strategy cost calculated on the information set:• On each information set: It is necessary to calculate the RM/BR strategy and update the average strategy for the passed information set. These costs have been detailed in Section E.1.Information set Number of nodes • There are three types of nodes on each game tree node, all of which need to get the counterfactual utility of each player. The difference is:-On the player node, the counterfactual utility needs to be obtained on this type of node u i (s, σ t | I→a ) and multiplied by the strategy return. -On opportunity nodes, in this type of node need to get virtual utility u i (I, σ t | I→a ) and multiplied by opportunity node probability. -On the end point node, it is necessary to solve the final income according to the node on this type of node.When passing through the same number of nodes, different algorithms do not pass through the same number of information sets. For example, when using the CFR algorithm to train vanilla Kuhn poker (assuming no pruning), one iteration passes through 55 nodes (24 player nodes, 1 random node, 30 leaf nodes), and calculate regret matching strategies on 12 information sets, at this time, the ratio of information set calculation and node calculation is 12:55. While using MCCFR the calculation passes through 10 nodes (4 player nodes, 1 random node, 5 leaf nodes), and calculate regret matching strategies on 4 information sets, the ratio of information set calculation and node calculation is 4:10. And the computing time is different at different decision, opportunity, and end point nodes. Therefore, measuring the performance of the algorithm by the number of nodes passed does not objectively reflect the ability of the algorithm.NeurIPS Paper ChecklistThe original Leduc and Kuhn can only raise once in a round. After one player raises, the rest of the players can only choose to call or fold, and cannot raise a larger bet. In the improved game, it can be raised up to z times. 


Decision: The paper introduces a new algorithm for solving extensive-form imperfect information games. The algorithm combines, in a novel way, Monte Carlo counterfactual regret minimization and fictitious play, achieving faster convergence to Nash Equilibrium in the experiments. The experimental results are justified by theoretical analysis of the algorithm. All reviewers agreed that the proposed algorithm is novel and interesting, and the results are promissing. 

That said, most reviewers expressed concerns about writing and presentation, providing recommendations and guidelines about improvements. Also, some reviewers were concerned that comprehending the paper requires a non-trivial background in the literature on game theory and state of the art algorithms in the field. 

The authors provided detailed feedback on the reviewers' concerns, and suggested constructive ways for preparing the paper for publications, and the reviewers appeared to be convinced by the authors' feedback. Based on the expressed concerns and proposed improvement and corrections, I recommend acceptance as a poster.

Reviews: review: paper_summary: paper_summary: The paper introduces a new algorithm called Monte Carlo Counterfactual Value-Based Fictitious Play (MCCFVFP) for solving extensive-form imperfect information games. This algorithm combines the counterfactual value calculations of Counterfactual Regret Minimization (CFR) with the best response strategy of Fictitious Play (FP). The authors demonstrate that MCCFVFP accelerates convergence to Nash Equilibrium (NE) significantly faster than existing Monte Carlo CFR (MCCFR) variants, especially in games with a high proportion of dominated strategies. They highlight its superior performance in large-scale settings, such as two-player limit short deck Texas Hold’em poker, where the blueprint strategy developed by MCCFVFP outperforms that developed by MCCFR.
strength_weakness: strength_weakness: I believe the biggest drawback of this paper is its writing. Only readers with a deep understanding of CFR can comprehend the content of the article relatively smoothly. I think the author needs to include more background information in the main text, especially since it is currently only 8 pages long, and NeurIPS allows up to 9 pages.

The article contains numerous undefined symbols and typos, which greatly hinder the reader's understanding. It gives the impression that it was written in haste and requires thorough proofreading.

Line 58: ****

Line 72: u^i has never been defined.

Line 107: L has never been defined.

Line 157: R_i^i

Line 175: The same sentence appears twice.

Line 192: 6x−Ittakes2

Line 279: Table 1 liner

...
questions: questions: 1）In Figure 2, the author only compared CFR+. I believe DCFR and PCFR should also be compared.

2）How sensitive is MCCFVFP to the proportion of dominated strategies in a game? Is there a clear threshold where it starts to outperform MCCFR?

3）Have you investigated how MCCFVFP performs in multi-player games beyond two players?
limitations: limitations: Yes
paper_summary: paper_summary: The paper proposes a new algorithm for solving extensive-form imperfect information games that relies on Monte Carlo (MC) simulations. The method abbreviated MCCFVFP combines MC settings with Counterfactual Regret Minimization (CFR) and the best response strategy of fictious play. Experimental evaluation demonstrate its speed advantage over the state-of-the-art competitors, in particular in clear games (i.e. games in which the vast majority of strategies are dominated ones).
strength_weakness: strength_weakness: 1. The paper has not been carefully revised before submission and there are certain issues that hinder is smooth reading and understanding. For instance, $u^i$ is not explicitly defined in the paper (I assume it is the payoff of player $i$) and in some cases is a one-argument function, in other case a two-argument one (cf. eq. 2). Similarly, $R_{T}^{i,+}$ in eq. 5.

2. A discussion in section 5.2.1. is rather accidental. Some plots in Fig. 2 are addressed while the other are not mentioned (e.g. Princess and Monster plots).

3. RM is not explicitly defined in the paper – it is only defined in the appendix
questions: questions: -- See points 1 and 2 in weaknesses
-- The results for tangeled games are not so strong as for the clear games. At the same time tangeled games are intuitively much more complex than clear games, which shows certain limitations of the proposed method. Please comment on that.

-- Random games with 21845 nodes do not seem to be challenging. Would the conclusions hold for much larger random games?
-- In section 5.3. the numbers of stored information sets of both methods are equal. Is it really the case or there is a mistake there?
limitations: limitations: The limitations are not explicitly specified.
paper_summary: paper_summary: The paper introduces a novel algorithm, Monte Carlo Counterfactual Value-Based Fictitious Play (MCCFVFP). This algorithm aims to accelerate the convergence of Nash Equilibria in extensive-form imperfect information games. MCCFVFP combines the counterfactual value calculations from Counterfactual Regret Minimization (CFR) with the best response strategy from Fictitious Play (FP). The authors claim that MCCFVFP achieves up to three times faster convergence compared to advanced MCCFR variants and significantly outperforms them in large-scale games with a high proportion of dominated strategies.
strength_weakness: strength_weakness: The paper could provide a more detailed comparison with a broader range of existing algorithms beyond MCCFR variants to establish a more comprehensive performance baseline.
questions: questions: Can the authors describe a bit about the comparison between MCCFVFP with reinforcement learning approaches for extensive form imperfect information games?
limitations: limitations: yes

Comments: comment: Thank the authors for the rebuttal. I have no further questions.
If you have any new questions or still have doubts about our current answers, please feel free to communicate with us at any time. We will try our best to answer any questions you may have.
If you have any new questions or still have doubts about our current answers, please feel free to communicate with us at any time. We will try our best to answer any questions you may have.
In Table 2 of the PDF, the JsQsJs3h2h in the third row should be KsQsJs3h2h. This is hereby corrected.
Thank you for your response! We appreciate your constructive and positive feedback regarding our paper.
Thank you for your answers. I've read the other reviews and the rebuttal. I raised my score.