Dynamic Discounted Counterfactual Regret Minimization
Authors: Hang Xu
Kai Li
Haobo Fu
QIANG FU
Junliang Xing
Jian Cheng
Venue: ICLR 2024 spotlight (2024)
Keywords: imperfect-information games
regret minimization
Nash equilibrium
Primary area: general machine learning (i.e., none of the above)

Abstract: Counterfactual regret minimization (CFR) is a family of iterative algorithms showing promising results in solving imperfect-information games. Recent novel CFR variants (e.g., CFR+, DCFR) have significantly improved the convergence rate of the vanilla CFR. The key to these CFR variants’ performance is weighting each iteration non-uniformly, i.e., discounting earlier iterations. However, these algorithms use a fixed, manually-specified scheme to weight each iteration, which enormously limits their potential. In this work, we propose Dynamic Discounted CFR (DDCFR), the first equilibrium-finding framework that discounts prior iterations using a dynamic, automatically-learned scheme. We formalize CFR’s iteration process as a carefully designed Markov decision process and transform the discounting scheme learning problem into a policy optimization problem within it. The learned discounting scheme dynamically weights each iteration on the fly using information available at runtime. Experimental results across multiple games demonstrate that DDCFR’s dynamic discounting scheme has a strong generalization ability and leads to faster convergence with improved performance. The code is  available at https://github.com/rpSebastian/DDCFR.

Published as a conference paper at ICLR 2024
DYNAMIC DISCOUNTED COUNTERFACTUAL REGRET MINIMIZATION
Hang X2 Kai Li2.2.t. Haobo Fu Qiang Fu Junliang Xing Jian Cheng 133,1
Institute of Automation, Chinese Academy of Sciences
Schooo of Artificial Intelligence, University of Chinese Academy of Sciences SScoool of Future Technology, University of Chinese Academy of Sciences STsinghua University Tencent AI Lab
"AiRiA
(xuhang2C20, kai. 1i, jian cheng) (ia. en, (hacbofu,
com, ilxinget sigghus. edu. en
ABSTRACT
Counterfactual regret minimization (CFR) is a family of iterative algorithms show- ing promising results in solving imperfect-informattii variants (e.g., CFR+, DCFR) have significantly improved the convergence rate of the vanilla CFR. The key to these CFR variants' performance weighting each iteration non-uniformly, i.e., discounting earlier iterations. However, these algorithms use fixed, coonully-sppecffiee
games. Recent novel CFR
scheme weight each iteration, which enormously limits their potential. In this work, we propose Dynamic Discounted CFR (DDCFR), the first cquilibrium-findee framework that discounts prior iter- ations using a dynamic, ation process as a carefully designed Markov decision process and transform the discounting scheme learning problem into a policy optimization problem within it. The learned discounting scheme dynamically weights each iteration on the fly us- ing information available at runtime. Extensive experimental results demonstrate that DDCFR's dynamic discounting scheme has a strong generalization ability and leads to faster convergence with improved performance. The code is available https: / htthtbtthhhhhggggggg/ http://c/ooopppeattaaiaaaa////a http:::///gthhb...
ciloomutically-learnee scheme. We formalize CFR's s iter-
INTRODUCTION
Imperfect-informatior games (IIGs) model strategic interactions between players with hidden in- formation. Solving such games challenging since it requires reasoning under uncertainty about the opponents' private information. The hidden information is omnipresent in real-world decision- making problems, making the research on IIGs theoretically and practically crucial.
In this work, we focus on solving two-player zero-sum IIGs. For these games, the typical goal is to find an (approximate) Nash equilibrium (Nash] 1950) strategy profile in which player can improve their utilities by unilaterally switching to a different strategy. One of the most successful ap- proaches to computing Nash equilibrium in IIGs the family of counterfactual regret minimization (CFR) algorithms (Zinkevich et al. 2007). CFR iteratively minimizes both players' regrets so that the time-averaged strategy profile gradually approaches the Nash equilibrium. Due to the sound the- oretical guarantee and strong empirical performance, CFR-type -ypp algorithms are the basis of several
breakthroughs (Bowling et al. 2015 Moravčík et al. 2017 Brown Sandholm 2018 2019a).
Over the past decade, researchers have proposed various novel CFR variants (Tammelin 2014 Brown Sandholm 2019b Xu et al. 2022) with faster convergence rates. particular, the de- milestone least an order of magnitude faster than
velopment of CFR+ Tammelin 2014) the vanilla CFR in practice, which was the key to solving the heads-up limit Texas Hold' em poker. The recently proposed Discounted CFR (DCFR) (Brown & Sandholm, 2019b) is one of the most efficient qquiibriummfindin algorithms, outperforming other CFR variants in a diverse set of IIGs.
"Equal contribution. Corresponding authors.

---

Published as a conference paper at ICLR 2024
Unlike the vanilla CFR, which assigns equal weights to every iteration, the key to the performance of these new CFR variants is that they use different discounting schemes to weight each iteration non-uniformly. For example, CFR+ uses linear discounting scheme in which iteration f's contribu- tion to the average strategy is proportional to t. DCFR is a family of algorithms that discounts prior iterations when determining both regrets and average strategy, i.e., assigning smaller weights ear- lier iterations using three hyperparameters (a, 8. and y). Although these CFR variants have shown that faster convergence is achievable by discounting, they all rely on a fixed and manually-speciffed discounting scheme, which significantly limits their potential. Specifically, since there are a limitless number of discounting schemes in theory, is impractical and even impossible to manually find one that performs well in most games, which leads to the manually- seeeiii-- scheme being suboptimal. Additionally, the fixed discounting scheme is pre-determined before the start of the iteration process, which is excessively restrictive. It is desirable to design more flexible scheme that can dynamically weight each iteration on the fly using the information available at runtime.
To this end, we propose a novel Dynamic Discounted CFR (DDCFR) framework that weights each iteration using a dynamic, automatically-leammed discounting scheme. We formulate CFR's 's iteration process Markov decision process (MDP) and transform the discounting scheme learning prob- lem into a policy optimization problem within it. Specifically, we regard the dynamic discounting scheme an agent interacting with the MDP. The agent receives the current state of the iteration process and outputs an action consisting of the discounting weights for the next iteration. The agent's goal is to find an approximate Nash equilibrium promptly by choosing appropriate weights.
Our ultimate goal is to learn discounting policy that generalizes across many different IIGs, not limited to some particular games. To this end, we carefully design the training games, the MDP, and the training algorithm. Specifically, we train the discounting policy on a diverse set of IIGs to improve its generalization ability. We design a game-agnostic state space for the MDP, so the trained policy naturally applies to different games. We further exploit highly scalable training algorithm to optimize the discounting policy based on evolution strategies (Salimans et al., 2017). We evaluate the learned dynamic discounting scheme on new games not seen during training. including large- scale games, such as heads-up no-limit Texas hold' em (HUNL) subgames. The results demonstrate that it has strong generalization ability and outperforms the fixed, manually-speciff discounting scheme on both training and testing games.
This paper makes three novel contributions: (i) We propose DDCFR, the first equilibrium-findd framework that discounts prior iterations using a dynamic, automatically-Ieama formulate CFR's 's' iteration process as an MDP and transform the discounting scheme learning prob- lem into a policy optimization problem in this MDP. (iii) We design an effective training algorithm to optimize the discounting policy. The learned discounting scheme exhibits strong generalization ability, achieving competitive performance on new games not seen during training.
scheme. (ii) We
2
PRELIMINARY
2.1 NOTATIONS
Extensive- form games (Osborne & Rubinstein 1994) are a tree-based formalism commonly used to describe IIGs. In these games, there is a finite set N of players and unique player e called chance with a fixed, known stochastic strategy. History h consists of all actions taken by players, including private knowledge known to only a subset of players. All possible histories in the game tree form the set H. Players take turn to take actions and, A(h)= (( ha E H. denotes the actions available at given history h. Z C H are terminal histories for which no actions are available. Each player i E N has a utility function u,(2):Z-> (Umin: ] CRR, and A -= - mmin is the range of utilities.
In IIGs, the lack of information is represented by information sets I, for each player i E N. If h, h are in the same information set I E I, player i cannot distinguish between them. For example, in poker, all histories within an information set differ only in the private cards of other players. Thus, A(T)= = A(h) for arbitrary h E J. We define [ Eiex Z and |A| = maxieN maxıez, (A(T))-
A strategy (f) assigns a probability distribution over the actions available for acting player in an information set I. Specifically, (l, denotes the probability of player i taking action a. Since all histories in an information set belonging to player are indistinguishable for that player, the strategies in each must be identical. Therefore, for any h h2 E I, we have (I) (x( o, (h2). A strategy profile a = {ayla, E Σ. i E NN is a specification of strategies for all players, where E, denotes the set of all possible strategies for player and a-; refers to the strategies of all
2

---

Published as a conference paper at ICLR 2024
players other than player i. u,(or, 0-1) represents the expected utility for player if player i plays according to o, and the others play according to d---
2.2 BEST RESPONSE AND NASH EQUILIBRIUM
The best response a-s any strategy BR(a_:) that maximizes player i's expected utiiliyy, such that u, (BR(o-i),, --))= m o-1)) The Nash equilibrium is a strategy profile o'=(0i, o²,) in which every player plays best response to the other players' strategies. Formally, vi N, ",(0), o².) = maxaçex, u,(o', d²2)) The exploitability of strategy o; a measure of how far that strategy is from optimal. is defined as eq ( (a o".) - (o, (R(o))). )). In an e-Nash equilibrium, no player has exploitability higher than e. The exploitability of strategy profile is e(o) EiEN ei (o.)//VV) We can interpret it as the approximation error to the Nash equilibrium.
2.3 COUNTERFACTUAL REGRET MINIMIZATION
Counterfactual Regret Minimization (CFR) is one of the most popular equilibrium- -induunn--iiigg-- algo- rithms for solving extensive-form IIGs (Zinkevich et al. (007). The algorithm iteratively refines the players' average strategies by minimizing regrets. CFR frequently uses counterfactual value ug (7), which is the expected utility of a information set / E I for player under a given strategy profile a, assuming that the player tries to reach it. The counterfactual value of a specific action a is of (4, a). The rigorous definitions of 2g (4) and (1, a) can be found in Appendix A
CFR typically proceeds with uniform random strategy o², On each iteration t, CFR first recursively traverses the game tree using the current strategy of to calculate the instantaneous regret (I, of not choosing action a an information set / for player i, which is defined as:
rT, a)) = =0g² (I,a) o. (T).
CFR then calculates the cumulative regret (I, the next iteration using regret-matchin (Hart& & Mas Colell 2000; [Csa Biaaabi & Lugosi 2006):
r (I.a) and computes a strategy for
Mas-Colel]
(1,a+ Edeeac (1aa)) [((T)
if EEEEan R (I,a)) >0 otherwise,
of (T,
where 1R. (1 max (1, In two-player zero-sum IIGs, if both players use CFR on each iteration, their average strategies o² will converge to an e-Nash equilibrium in O ( iterations (Zinkevich et al. 2007). The average strategy of calculated as:
(L,,a)
() = (T
o((1,))= (( EmeAA CT(
(L,))
where oं (T) is information set I's reach probability (Appendix A and C (I, is player i's cu- mulative strategy for action a in information set iteration
2.4 THE DISCOUNTING VARIANTS CFR
Since the birth of CFR, many new CFR variants have been proposed and greatly improved the con- vergence rate of the vanilla CFR. CFR+ (Tammelin) 2014) is like CFR with three small but effective modifications and converges order of magnitude faster than CFR. First, CFR+ uses linear dis- counting scheme that weights iteration by 1 rather than using a uniformly average strategy as in CFR. Second, to immediately reuse action when it shows promise of performing well in- stead of waiting for the cumulative regret to become positive, CFR+ sets any action with negative cumulative regret to zero on each iteration. Finally, CFR+ the alternating-updates technique.
The recently proposed DCFR (Brown & Sandholm 2019b) algorithm investigates the discounting schemes in regret minimization algorithms more systematically. DCFR is family of algorithms that discounts cumulative regrets and the cumulative strategy, dramatically accelcrating the convergence rate. Specifically, on each iteration t. DCFR multiplies positive cumulative regrets by (t-1)²
(1-1)=41>
(t-1)² (t (1-1)41+ and the cumulative strategy by (²=1)² Formally,
negative cumulative regrets by
OT {
RC (I, ( 1-11+1 (I, if (I,,)0
(t-I))
(3)
R (I, 11-1) (I, otherwise.
((-1)
3

---

Published as a conference paper at ICLR 2024
t - ( + m
-
(1)).
(4)
The three hyperparameters (a, 8, 7) determine DCFR's discounting scheme. For example, we can recover the linear discounting scheme by setting 1, 3 and y 1. Although there are limitless number of discounting schemes that converge in theory, DCFR's s authors empirically set 1.5, 5 0, and y since they found this setting performs the best in the games they tested.
3 LEARNING DYNAMIC DISCOUNTING SCHEME
3.1 THE DDCER FRAMEWORK
As mentioned earlier, the existing discounting CFR variants have obtained remarkable performance in solving IIGs. However, they all exploit a fixed and manually-specified discounting scheme. These pre-determined schemes are not flexible enough, thus inevitably limiting the convergence perfor- mance. We argue that an ideal discounting schema should fulfill two criteria. First, the scheme should be automatically learned rather than manually designed. For example, DCFR, designing the discounting scheme by manually setting the values of a, 8, and is unscalable and suboptimal since finding one setting that can efficienlly solve wide variety of IIGs is challenging. Second, the scheme should be able to adjust the weights dynamically instead of using fixed weights. For regret minimization algorithms, the discounting weights often need to change dynamically during learn- ing. This is particularly important in solving different types of IIGs, where the distribution of regret values and the cost of taking suboptimal actions vary significantly during the iteration process.
To achieve this goal, propose novel Dynamic Discounted CFR (DDCFR) framework that weights each iteration using dynamic, automatically- discounting scheme. DDCFR learns to adjust the discounting weights dynamically using information available at runtime, such as iter- ations and exploitability. By adapting to changing conditions in real time, we believe that DDCFR can lead to more efficient and effective learning.
The high-level idea of DDCER is to encap- sulate CFR's iteration process into an envi- ronment and regard the discounting scheme as an agent interacting with it. Specifically, the agent receives the current state (i.e., the current status of CFR's iteration process) and outputs an action consisting of the dis- counting weights for the next iteration. This process continues until the maximum num- ber of iterations. The agent's 's goal is to find optimal discounting policy that can dy- namically choose suitable weights for each iteration and thus minimize the exploitability of the ob- tained average strategies. Formally, the interaction process between the agent and the environment in game G constitutes a Markov decision process (MDP), represented as (G, A, PG 1().
Enviroements
Normalized Iteraticn
Gamte
State
Current Strategy
Nommalized F? Exploitability
Traverse the Gamte Thee
Instaniancous Regrets (Len
8r.8%
Agoer
Action
(iddate Camularive Reprets (Fig
Duration
Matching
New Strategy (Eçn 2)
Reward
Ra
Update Average Stratery (Ein
Figure 1: The DDCFR framework.
The game G. Each game G represents a different environment. Our ultimate goal is to train an agent whose discounting policy performs well on the training games and generalizes new games.
The state space S. The state E S contains information that the agent observes at each iteration t in game G. s, should contain much general and transferable information as possible, helping the agent make good decisions on choosing discounting weights for each iteration and making the learned scheme applicable different games. We propose a game-agnostic state representation that meets these requirements, i.e., 8, consisting of two parts: 1) the normalized iteration i, which is the ratio of the current iteration i to the total number of iterations; 2) the normalized exploitability E which is calculated as (log E - log /m (log Ef log Emin) where Ef and E are the exploitability of the average strategies in game G at iteration 1 and 1, respectively, and Emin is the minimum reachable exploitability set to 10 12, The logarithmic operation results in a more even distribution of normalized exploitability, thereby facilitating agent training (Appendix[].
The action space A. The agent's action à, E A at iteration t consists of four numbers, i.e., à [or, Be, Th, Te]. Similar to DCFR in Equations and 4 Ot Bt, 7t are used to determine the
4

---

Published as a conference paper at ICLR 2024
discounting weights, Le., (t-1)==4I* ((-1)=++1' and (7²1 7t for positive cumulative regrets, nega- tive cumulative regrets, and the cumulative strategy, respectively. The key difference between our DDCFR and DCFR is that DCFR uses a pre-determined discounting scheme, i.e., DCFR empirically sets o=1.5, 8=0, and 2=2. which is fixed not only during the iteration process but also in different games. In contrast, our proposed DDCFR can utilize å dynamically adjust the discount weights at runtime and adaptively control its iteration process for each game. represents the duration for how long to use these discounting weights. Incorporating Tı enhances the interpretability of the learned scheme, indicating whether the hyperparameters need to be adjusted frequently.
(t-1))
(t-1)%
The state transition pc, pG : S A + S describes how the state changes during the iteration process of DDCFR in game G. Specifically, the agent observes the current state at each iteration t and outputs an action âz DDCFR uses the discounting weights calculated by at, 3r, and y for Ti iterations, and finally, the state transitions to the next state Sttt, This process allows for the consecutive use of each set of discounting weights for a certain number of iterations.
The reward function R.C RC evaluates the agent's performance and guides DDCFR's s iteration process. Since the agent's ultimate goal is to find strategy profile with the lowest exploitability, we use the sparse reward setting where the agent only receives a reward at the end of the iteration log EY, where Ey is the exploitability of the average strategies in game G the maximum number of iterations T.
process. Specifically, the reward is f = log E -
The agent is typically represented by a neural network with parameters 0, i.e., Te : S - A. Figure shows DDCFR's 's overall iteration process. Given game G, at iteration t, the agent receives the cur- rent state s, and outputs an action å, (ar, 5t, Ye. Te) = (T()). DDCFR then uses the discounting weights calculated by att, 3,, and 7/ to update cumulative regrets and the average strategy for To iterations. This process continues until the maximum number of iterations, and the agent eventually receives reward R In each game G, the objective is to maximize the final reward Re represented as fa)()) RC DDCFR's overall objective is to maximize the average sum of the rewards across the training games G, i.e., f0) = ল EGeg (0). By optimizing f(),, our ultimate goal is to learn generalizable discounting policy that applies to new games.
3.2 THEORETICAL ANALYSIS
Although DDCFR's dynamic discounting scheme is highly flexible, a question arises regarding its convergence properties. Here we theoretically demonstrate that DDCFR is guaranteed to converge to Nash equilibrium as long as at, 3r, T/2 are within a certain range.
Theorem 1. Assume that conduct DDCFR T iterations in two-player zero-sum game. If DDCFR selects hyperparameters as follows: 04 (0, for b< and or ElE(1, for (,E((5,0)) 5).
the weighted average strategy profile is a G|I A (SVIA) + ( ///VV-Nas equilibrium.
The proof is in the Appendix B mainly rescaling inequalities based the range of ar,, Be, 7 follow- ing DCFR's s proof. This theorem signifies that numerous dynamic discounting schemes converge in theory. We then describe how to efficiently optimize To to find werl-peeforming scheme in practice.
3.3 OPTIMIZATION THROUGH EVOLUTION STRATEGIES
When training the discounting policy Te, we encounter the challenges of sparse reward (the agent receives reward at the end of the iteration), long time horizons (CFR requires thousands of iter- ations), and multi-task learning (the agent maximizes rewards across various games). Off- Off-the-shelf reinforcement learning (RL) algorithms like DQN (Mnih al.) 2015) and PPO (Schulman et al., 2017) struggle to cope with these challenges, requiring the integration of more sophisticated compo- nents. Additionally, RI. notably sensitive to hyperparameters. Evolution Strategies (ES) (Wierstra) al. 2014:) [alimans et al.) 2017) has demonstrated its efficacy scalable alternative RL in tackling these challenges. As a black box optimization technique, ES is indifferent to the distribution of rewards and tolerant of arbitrarily long time horizons. Besides, ES is easy implement and is highly scalable and efficient to use on distributed hardware.
Inspired by the effectiveness of ES in optimizing complex objective functions and addressing RL- related problems, we design an ES- ba-based algorithm to train the discounting policy Ty- The ES ap- proach proposed in (Salimans et al. 2017) states that for objective function f(0) over network
5

---

Published as a conference paper at ICLR 2024
Algorithm 1: DDCFR's training procedure.
Input: Trainig games G, epochs M, learning rate Ir, population size standard deviation Randomly initialize the agent's parameters 01:
for m to .M do
Initialize population IP with an empty list;
for ...,, N do
Sample E (O,
Add c,. -4 to the population P:;
foreach E do
foreach G E G do
Compute (0 (AAgorithhm 2
((0m+88) < G] Ecec f (0mm +8E)
10
Compute +5cc using Eqn. 5 Ir f +ôE)E
11
gm+1 9T +
5.N
Output: The trained agent Tga++1
Algorithm 2: The calculation process of (0).
Input: Training game G. agent To, total itertations T
x-11 1;
while t < 7 do
[ot, Sr, Yo, Ti] = å, = TT(
Use (a,, Se, 7el to calculate discounting weights and perform 7, numbers of CFR iterations;
t +-+++0 T2;
Compute exploitability E E Output: (0) +- log E log FGG
parameterized by its gradient estimation can be obtained by applying Gaussian perturbations O, ie., Vo ToEe-stoonn,((0+be and (0, I) is Gaussian distribution with mean 0 and covariance I. This gradient estimation can be approximated with samples. Specifically, we generate population of perturbed network parameters at each epoch and evaluate the resulting parameters under all training games. We then combine the results to calculate the gradient and update the original parameter using stochastic gradient ascent.
(oe +ōe)e,, where 8 denotes the noise standard deviation,
To improve the efficiency of the training process, we employ three acceleration techniques: anti- thetic estimator, fitness shaping, and parallel evaluation. Algorithm [outlines the complete training procedure of the discounting policy. (i) We use the antithetic estimator (Nesterov & Spokoiny 2017) to reduce variance. an unbiased estimator using control variates (Liu et al. 2019). given by the
symmetric difference, i.e.. Vol..~N\0.11 ff (0 + 5e) 1 Ee-A(()) [f(O + de) f(O de)] (ii) We apply fitness shaping (Wierstra et al. 2014) by performing a rank transformation on the objec-
tive function f()) before computing the gradient. For parameter O₂ with the kth largest value in the population of size N, the shaped result is as follows:
max (0, log ( + +1 - llo((k))
(0xx)
(5)
EP max (0. log ( + +1) log(i)
N
This approach makes the gradient only relevant to the relative ordering of parameters' fitness values rather than their absolute magnitudes. By doing so, our algorithm becomes more robust to variations in the original fitness values. (iii) To further speed up training, evaluate the performance of each perturbed parameter under each game in parallel.
3.4 ADDITIONAL COMPUTATION COST ANALYSIS
Compared with DCFR, DDCFR introduces additional computation costs, which mainly includes three parts: feature calculations, network inference, and policy training. However, these additional

---

Published as a conference paper at ICLR 2024
time costs are very small compared the overall time costs. (i) Feature calculations. The state representation requires the iteration number and the exploitability. The iteration number is effort- lessly obtainable. Since the exploitability calculation and the instantaneous regret calculation are completely independent, multiprocessing can be used to concurrently execute both processes with- out increasing the wall-clock time (Appendix C). (ii) Network inference. The time overhead of is negligible compared to the overall iteration time. To support this claim, we compare the wall-clock time between DCFR and DDCFR in Appendix D DDCFR exhibits only a 0.22% increase in time on average. (iii) Policy training. The effort put into training is worthwhile, as the trained discounting policy can be directly applied to numerous new games without modification. This means that the additional work during training is amortized across the various games to which the policy is applied.
4 EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Training and testing games: We use several commonly used IIGs in the research community. Here, we provide brief descriptions of these games; please refer to the Appendix [ for more details. Kuhn Poker (Kuhn 1950) a simplified form of poker with three cards in deck and one chance to bet for each player. Ledue Poker (Southey et al.) (005) is a larger game with 6-card deck and two rounds. Big Ledue Poker uses a deck of twenty- -our cards with twelve ranks, allowing a maximum of six raises per round. In Liar's Dice-x (Lisy et al. 2015), each player has an zidided dice, which they roll at the start. Players then take turns placing bets on the outcome. Goofspiel-x (Ross) 197T) is a card game where each player has cards and tries to score the most points by making sealed bids in a rounds. In Battleship-x (Farina et al. 2019), players secretly place a x 2 ship on separate 2 x x grids and then take turns firing at the opponent's 's ship three times. HUNL Subgame-x is HUNL subgame generated by the top poker agent Libratus.
We select eight relatively large IIGs testing games, Le., Battleshi--. Battleshi--,, Goofspiel-4, Liar's Dice-4, Leduc Poker, Big Leduc Poker, HUNI. Subgame-3, and HUNI. Subgame-4. These games are diverse in size and challenging solve, making them suitable for testing the learned discounting scheme's generalization performance.
The training games should be relatively small to speed up the training process while still exhibit- ing the typical characteristics of the testing games. We select four training games: Kuhn Poker, Goofspiel-3, Liar's Dice-3, and Small Matrix. The first three games are simplified versions of the testing games, while Small Matrix simulats common situations in games where irrational actions lead to large losses. Our training games have varying rules and scales, exhibiting a strong diversity, crucial for improving generalization ability.
Training details:
We set a fixed noise standard deviation of 8=0.5 and population size of --100. We distribute the evaluation of perturbed parameters across 200 CPU cores. For the action space, we set the range of a and y to [0, 5). 3 to 5, OJ following Theorem and choose r in [1, 2, 5, 10, 20). We employ a network consisting of three fully-connected layers with 64 units and ELU activation functions to represent the discounting policy πe. The network takes the current state of the environ- ment as input and outputs values for a. 8, 7, and the probability of selecting each r. We use Adam with a learning rate ir of 0.01 to optimize the network and trained the agent for M = 1000 epochs, which took roughly 24 hours. We set the number of CFR iterations T to 1000, typically sufficient for convergence to a small exploitability. All CFR variants used the alternating-upoee technique.
4.2 COMPARISON TO DISCOUNTING CFR VARIANTS
In Figures 2 and we compare DDCFR's learned discounting scheme with two discounting CFR variants, i.e., CFR+ and DCFR. Since the iteration process of DDCFR is deterministic (AppendixF). we only test it once in each game. Due to the rapid decline in exploitability in the early iterations of different CFR algorithms, their differences are primarily manifested in the later iterations. For a bet- ter comparison of the algorithms, we focus on their performance in the later iterations, i.e., from 500 to 1000. Please refer to Appendix for all iterations. As shown in Figure 2 to a lower exploitability on the training games, which is expected since we are optimizing DDCFR's performance these games. However, even in unseen testing games shown in Figure 3 DDCER still achieves competitive performance against the other CFR variants due to the fact that DDCFR is designed with generalization in mind. Specifically, it yields an average reduction in exploitability
DDCFR converges faster
7

---

Published as a conference paper at ICLR 2024
231
Small Matris
Kohn Poker
Gosdogial-3
Explobaatts
CFS+
10
DCFR
10
10
10:00
500
750
875
1000
500
625
1000
500
625
750 Btrstions
875
1000
20m0
500
625
250
1000
Figure 2: Comparison of DDCFR against two discounting CFR variants on four training games.
10"
Bottleship
Buttehipp
Gootspiol4
10
Liue's Dice-d
Engleltakiity
CPF+ DCFR DD/
10
1000
500
625
1000
Berrations
(taradlion
Storations
10"
Lacter: Poloee
Ledue Poker
1015
MUNI Subgemed
HUNI, Subgumm
Expl atplatshiing
10
500
62.5
750
875
1000
500
625
750
875
1000
500
625
750
876
1000
10
500
625
750
875
1000
Itorations
Berotions
Dtorations
Figure 3: Comparison of DDCER against two discounting CFR variants on eight testing games.
of 42% compared to DCFR, which is remarkable given DCFR's already strong performance. Unlike CFR+ and DCFR with fixed and manually-specifiel discounting schemes, our DDCFR achieves bet- ter performance on all games thanks to the learned dynamic discounting scheme's ability to adjust the discounting weights the fly using information available at runtime.
Greedy Weights (Zhang et al., 2022) is recently proposed algorithm specifically designed for normal-form games by greedily weighing iterates based on regrets observed at runtime. Although it can be adapted for extensive-form games as well, we find that its performance is notably inferior to that of DDCFR which is designed explicitly for extensive- form games (Appendix G We sus- pect that when faced with a large number of information sets, the computed weights might not be appropriate, resulting in poor performance in extensive-fome games.
To further understand the behaviors of the learned dynamic discounting scheme me. we visualize its actions (i.e., Okt, 3t; Th, Tτ) during the iteration process. Figure 4 shows that the actions outputted by Ta have different values in different games but exhibit a similar trend. Specifically, aN increases with iterations in all games while Be and "t decrease. Compared with DCFR's fixed discounting scheme (i.e., a=1.5, 2=2), the learned scheme is more aggressive in earlier iterations. Smaller a and bigger y lead to smaller weights (1-1)- (t-1)=+I and (T=1)² when discounting positive cumulative regrets and the cumulative strategy. This may be because the optimal strategy based on the opponent's strategy frequently changes in earlier iterations; thus, carlier iterations need to be given smaller weights. As the iteration progresses, the scheme becomes more moderate, which may aid in the convergence of the average strategy. Additionally, the scheme consistently uses more aggressive strategies when discounting negative cumulative regrets. This is beneficial allows for more rapid reuse of promising actions instead of waiting for cumulative regrets to become positive. The change 7, suggests that discounting weights should be adjusted more frequently earlier iterations.
A
1000
5:00
750
1000
250
500
750
1000
250
500
DDCFR (Small Matria)
DDCFR (Liar's Di
DDCFR (Butthshipp3)
DDCFR (Big Leduc Pokur)
DCFR (A3l gumas?
Figure 4: The learned discounting scheme behaves differently in various games yet exhibits a similar trend. Compared with DCFR's 's fixed discounting scheme (we view DCFR special case of
DDCFR, where a = 1.5,3, 3 = O, 7 = 2, and the duration T₁ = 20), it is more aggressive in the earlier iterations and becomes more moderate the iteration progresses.
8

---

Published as a conference paper at ICLR 2024
4.3 ABLATION STUDIES
To verify the effectiveness of DDCFR's components, we conduct extensive ablation studies and report the results Table The results of each column are obtained by replacing one component of DDCFR, and the rest remains unchanged. We use the exploitability on three testing games to compare the learned discounting schemes' performance.
The number of training games. We first investigate how the number of training games affects the learned discounting scheme. DDCFR-2 means using the first x training games from Kuhn Poker, Goofspiel-3, Liar's Dice-3, and Small Matrix. DDCFR-1 performs relatively poorly since the learned discounting scheme is prone to overfitting using only one training game. DDCFR-2 and DDCFR- 3 obtain better results because they need balance their performance under multiple games and improve the gencralization ability of the learned discounting schemes. With the addition of Small Matrix, DDCFR achieves much lower exploitability in HUNL Subgame-3, probably because both games exhibit the same property of having high-loss actions.
The state representation. We consider how the state representation affects DDCFR's final per- formance. DDCFR-it and DDCFR-ex only use the normalized iteration and the normalized ex- ploitability the state representation, respectively. As shown in Table DDCFR-it achieves better performance than DDCFR-ex, indicating iterations provide the agent with more information for mecision-making. However, both algorithms perform worse than DDCFR, showing that these two state features are complementary and that using them together can obtain the best performance.
The action space design. DDCER adopts a continuous action space design, i.e., and Y are con- tinuous values between 0 and 5, ,9 is continuous value between -5 and O. In contrast, DDCFR-di uses a discrete action space design, i.e., discretizes the range of a, 3, to consecutive integers. The results in Table 1 show that continuous actions help the learned dynamic discounting scheme perform more fine-graine control and obtain better performance.
The optimization algorithm. We compare DDCFR's optimizing algorithm ES with RL. DDCFR-rl uses PPO to optimize the discounting policy, underperforming in all testing games. We attribute this outcome several factors commonly encountered during training, such as sparse rewards, long time horizons, and muli-task learning.
Table 1: Ablation analyses of DDCFR.
DDCFR-1
DDCFR-2
DDCFR-3
DDCFR-it
DDCFR-cx
DDCFR-dis
DDCFR-rl
DDCFR
LeduePoker
1.566e-4
1.490c-4
1.213e-4
1.249c-4
1,289c-4
1.156e-4
1.229e-4
1.198e-4
Suhgame-3
2.533e-3
2,481e-3
2.393e-3
2.292e-3
5.320e-3
5.795e-3
4.987e-3
1.963e-3
Subgame-4
2.517e-3
2.175e-3
2.122e:3
2.714e-3
3.804e-3
5.803e-3
5.198e-3
2.005e-3
4.4
COMBINATION WITH OTHER CFR VARIANTS
Our proposed dynamic discounted regret minimization is general framework that be uni- versally applied in any CFR variants that employ fixed and manually specified discounting rules. The DDCFR is just example application of this framework to DCFR. The predictive CFR+ (PCFR+) FFrrina et al. 2021) is a recently proposed state-of-the-art CFR variant based on pre- dictive Blackwell approachability. Nonetheless, also uses fixed quadratic discounting scheme. To showcase the generalizability of our framework, we apply it to PCFR+, resulting in the Dynamic Predictive CFR+ (DPCFR+). We find that DPCFR+ can further unlock the potentials of PCFR+ and enhance its performance (Appendix Hj. These results demonstrate the general applicability of our dynamic discounting framework. It can be regarded as a performance booster that can be applied in a plug-an plug-anddpue and-play manner to various CFR variants that employ fixed discounting rules.
5 CONCLUSION
We present DDCFR, the first equilibrium-findd finding framework that discounts prior iterations using an automatically-leared dynamic scheme. We first formulate CFR's iteration process as a carefully designed MDP and transform the discounting scheme learning problem into a policy optimization problem. We then design scalable ES-based algorithm optimize the discounting policy effi- ciently. The learned discounting policy exhibits strong generalization ability, achieving competitive performance on both training games and new testing games.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work is supported part by the National Science and Technology Major Project (202200116401); the Natural Science Foundation of China under Grant 62076238, Grant 62222606, and Grant 61902402; the Jiangsu Key Research and Development Plan (No. BE2023016); and the China Computer Federation -ennent Open Fund.
REFERENCES
James Bergstra and Yoshua Bengio. Random search for hyper-paranan optimization. Journal of Machine Learning Research, 13(2):81-305, 2012.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold em poker is solved. Science, 1475
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 35966374)4418-444, 2018.
Noam Brown and Tuomas Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456): 885-890, 2019a.
Noam Brown and Tuomas Sandholm. Solving imperfect-inforration games via discounted regret minimization. In AAA/ Conference on Artificial Intelligence, pp. 1829-1836, 2019b.
Nicolo press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation in extensive-form games: Saddle-poin formulation and benchmarks. In Advances in Neural Information Processing Systems, pp. 9229-9239, 2019.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive black- well approachability: Connecting regret matching and mirror descent. In AAAI Conference on Artificial Intelligence, pp.
2021.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 6865):1 2000.
Harold W Kuhn. simplified two-person poker. Contributions to the Theory of Games, 1:97-103, 1950.
Viliam Lisý, Mare Lanctot, and Michael H Bowling. Online monte carlo counterfactual regret mini- mization for search in imperfect information games. In International Conference on Autonomous Agents and Multiagent Systems, pp. 27-36, 2015.
Hao Liu, Richard Socher, and Caiming Xiong. Taming maml: Efficient unbiased meta--eiinforremmett learning. In International Conference Machine Learning, pp. 4061-4071 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51 518(7540):529-533 2015.
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 arti- ficial intelligence in heads-up no-limit poker. Science, 356(6337):50855 513, 2017.
Jr John F Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1) (:48):48 49, 1950.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex functions. Foundations of Computational Mathematics, 17(2)527-566, 2017.
Martin Oshome and Ariel Rubinstein. course in game theory. MIT press, 1994.
10

---

Published as a conference paper at ICLR 2024
Sheldon M Ross. Goofspiel the game of pure strategy. Journal of Applied Probability, 8(3): 621-625, 1971.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative reinforcement learning. arXiv preprint arXiv:1703.0386+ 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 170.006777 2017.
Jasper Snock, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems, pp. 2951-2959, 2012.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Conference on Uncertainty in Artificial Intelligence, pp. 550-558, 2005.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint MoXiv:1407.5042 2014.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research, 15(1):949 9800 2014.
Hang Xu, Kai Li, Haobo Fu, Qiang Fu, and Junliang Xing. Autocfr: Learning to design counter- factual regret minimization algorithms. In AAAI Conference on Artificial Intelligence, pp. 5244- 5251, 2022.
Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-gradient reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2396-2407, 2018.
Tong Yu and Hong Zhu, Hyper-parameter optimization: A review of algorithms and applications. arXiv preprint arXiv:2033.05689 2020.
Hugh Zhang, Adam Lerer, and Noam Brown. Equilibrium finding in normal-form games via greedy regret minimization. In AAAI Conference on Artificial Intelligence, pp. 9484-9492, 2022.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems, pp. 1729-1736, 2007.

---

Published as a conference paper at ICLR 2024
A RIGOROUS DEFINITIONS OF REACH PROBABILITIES AND COUNTERFACTUAL VALUES
The history reach probability of history h is the joint probability of reaching that history if all players play according to a, denoted by x² (h) = Iwag "p(w)(h', where the relationship E h indicates that is equal to or prefix of h, and P(h) is the unique player who takes action that history h. can be decomposed into each player's contribution, iee, x (h) = x3 (h)=,, where (h) refers to player i's contribution, and x (h) denotes all players' contributions ex- cept player i. We define the information set reach probability as (1)= Ener x" (1)), and the interval history reach probability from history h' h as T (h', (WW',)--' (1)= (h)/ if h'Ch. Ty (I,, (T), x5 (h, h'), (h, h²) are defined similarly.
For player i an information set E I, under given strategy profile o, the counterfactual value of I is of (I) = (= Eeez (I (h, (2)) The counterfactual value of specific action in is of (T,a) = Ener(T Exez (T (ha, (=).
B PROOF OF THEOREM 1
Proof. Since the lowest amount of instantaneous regret on any iteration is - A and DDCFR multi- on iteration t, the regret for any action at any
(t-1)% plies negative regrets by (t-1)c41 S ((-1ア+1
(2-1)0
point is greater than -24.
Consider the weighted sequence of iterates 0²1 T where ol is identical to o², but weighted by
wa, - 11)1²²² 7* rather than w, -1/--++1 (8- 1y- The regret of action a in information
(k-1)ak
set I on iteration of this new sequence is R² (I,
From Lemma 5 we know that R² (I, S $ AAVIAVV VA for player i for action in information set I. Since Wa,t is an increasing sequence, we can apply Lemmal I Juiing weight Wa,t for iteration /
with 2 DAAVAAAT and == -2A This yields 18T
(I,a) S [SAVIAIVT + 22) As the
weights sum is Σi=1 Wa,t 2 EE T (k-1)²
ΣT t
(2T 2 6
bo (T,( S 6A
1
127
the weighted average regret R.u.T maX Σ Wadd
6
//V. Applying
Theorem 3 in CFR (Zinkevich al. 2007). we get overall weighted average regret for player i is at /VT. Since [Z,| + [Tp] |Z], the weighted average strategies form
most 64/Zz/
VIAl
2
3
VT
6A/Z|
2 VT
/VT -Nash equilibrium after T iterations.
Lemma 1. (Brown & Sandholm 20196 Lemma 1) Call sequence 21, ,1....,,TT of bounded real values BC-plausible if B > 0, C S 0. Ek=1 In C' for all t S. T. and Σ It
B. For any BC-plausible sequence and any sequence of non-decreasing weights we 2 O, (wer)) S WT (Pr(B-C (C-)).
Lemma 2. Given a set of actions A, any sequence of rewards v², and any sequence of weights w such that Σt= Wi Do and (a)(a) - v² (b)) S forr all t and all a, A, after playing a sequence of strategies determined by regret matching but every reward vf is weighted by the weight w', the Et= (w))
is bounded by R, AVIA E of
weighted average regret RTTTT max.EA
Σl w²
2 Proof. The proof is identical to that of Theorem 2.8 in (Cesa-Bianchi & Lugosi 2006), with for the polynomially weighted average forecaster.
0
Lemma (Brown& & Sandholm 2019b Lemma 2) Given sequence of strategies of TT.
each defining probability distribution over a set of actions A, consider any definition for Q²(() satisfying the following conditions:
1. (a) =
2. Q*(a) = (a) (2)()) (()))
12

---

Published as a conference paper at ICLR 2024
3. 0 Q'(a) 2 (a) r'(a)) (())
The regret-like value (a) is then upper bound the regret (a) and Q²(a) Qa) > r'(a) = (a) - R² (a).
Lemma 3) Given a set of actions and any sequence of rewards V² such that (a) db] A for all t and all a,b A. after playing sequence of strategies determined by regret matching but using the regret-like value (a(a) in place of R' (a),
Lemma 4. (Brown & Sandholm 2019b
(a) S /AIT for all A.
Lemma 5. Assume that player conducts T iterations of DDCFR. Then the weighted regret for the player is at most A [Zel VIANT and the weighted average regret for the player is at most A88 AAII VAA/VT.
Proof. The weight of iteration t is wi
II 1- 1)024 and wr 1. Thus, Wt S
(k-1)at
(k-1)) k= 11+1 - for all and therefore Σt= wi ST
Additionally, Wt 2 II II
(k-1)' for T t t T and wT 1. Thus, E We
Σigg ii E T (
T +1) + S..
AVIIVVET, w2
SAVIAIV 31
Applying Lemma and 4 we see that T (1,a) V
Applying
E Wh
Theorem 3 in CFR Zinkevich et al. 2007), we see that Q. I
82 I
VAVT
Since R.
37
QU so Ree.T BAIZyyAAV
C FEATURE CALCULATIONS IN DDCER
The features in DDCFR contain the normalized iteration and the normalized exploitability EC 1- The iteration number is effortlessly obtainable. The normalized exploitability calculation can be done with the instantaneous regret calculation in parallel. We provide a detailed explanation below.
On each iteration I, our DDCFR first recursively traverses the game tree using the strategy a² to compute the instantaneous regret r'. Then, DDCFR updates the cumulative regrets Rt, the average strategy of, and the new strategy gf+1 using the weights (at, Be, Ys) generated by the discounting policy (8t).. Specifically, ot, 3t, 7t no (s:) (o EE-)), where î the normalization of iteration and E is the normalized exploitability of the average strategy 5--l at iteration t 1.
Calculating E requires traversing the game tree using the average strategy g²-1, which leads to additional time overhead under naive implementation. However, it's crucial to note that culate E and compute the instantancous regret r' in parallel since these two processes depend on two different strategies, σ²-l and o², each requires traversing the game once. Consequently, there is no additional wall-clock time overhead associated with the calculation exploitability in our parallel implementation.
cal-
D RUNNING TIME COMPARISON BETWEEN DCFR AND DDCER
To further support claim in Section 3.4, we compare the running time between DCFR and DDCFR. Since the running time is influenced by the available hardware resources the system, we execute the algorithms on various games one bye one, but distributed across multiple servers. In addition, to mitgate the time overhead associated with writing to disk. we remove the logging module and only print the final running time. Table 2 presents the running time of the two algorithms on eight testing games. For example, completing 1000 iterations of DCFR on Battleship-2 takes roughly 14 minutes, 54 seconds, and 558 milliseconds. In comparison to DCFR, DDCFR exhibits only 0.22% increase in time on average. Therefore, the additional computation time incurred by DDCFR is negligible compared to the overall iteration time.
13

---

Published as a conference paper at ICLR 2024
Table 2: Running time comparsion between DCFR and DDCFR.
Game
DCFR_time
DDCFR_time
(DDCFR_time DCFR_time) DCFR_time
Battleship-2
0:14:54.558
0:14:55.814
0.140%
Battleship-3
11:10:46.895
11:12:05. 156
0.194%
Goofspiel-4
00:01:03.259
00:01:03.518
0.409%
Liar's Dice-4
0:06:57.896
0:06:58.577
0.163%
Ledue Poker
0:08:13.140
0:08:13.921
0.158%
Big Ledue Poker
14:35:48.347
14:58:07.357
0.259%
HUNL Subgame-3
0:02:54.634
0:02:55.024
0.223%
HUNI, Subgame-4
0:02:14.379
0:02:14.648
0.200%
E ALL ITERATIONS OF DDCFR AND DISCOUNTING CFR VARIANTS
Due to the rapid decline in exploitability in the early iterations of different CFR algorithms, their differences are primarily manifested in the later iterations. Consequently, for a better comparison of the algorithms, we focus on the later iterations in the main paper. For the sake completeness, we show the all iterations of DDCER and discounting CFR variants in Figures and
Small Matrit
Kirhn Pokker
30
Goodepiel-3
301
Liar's Dion-3
CFR
DCER DDCFR
Explotaniiy
201
10
10
12:11
10-11
10
2:50
500
750
1000
10
250
500
7500
1000
10
250
5:00
750
1.000
250
560
750
1000
Bersiiona
Ramiiiom
Figure 5: All iterations of DDCFR and discounting CFR variants on four training games.
307
Buttleship22
Buttioship-
10a
Goofspiel-4
127
Liue's Dicu-4
CFR DCFR DDCFR
13
20
20-1
10
1014
10
5
1000
250
1000
250
1000
500 [tenstion
Iberations
Berrttione
397
Lidlec Polowr
Laduu Poleur
HUNL Subgwems
HUNI Sub-gumed
22"
Eaplonsaury
10
1000
500
Figure 6: All iterations of DDCFR and discounting CFR variants on eight testing games.
F DETERMINISTIC NATURE OF DDCER's S ITERATION PROCESS
We use ES to learn the discounting policy and select one of the best performing policy on the training games for testing. It is worth noting that there is randomness throughout the iteration process of DDCER when using the learned discounting policy on the testing games. Specifically, DDCFR always initializes with the uniform random average strategy, and the policy network consistently
14

---

Published as a conference paper at ICLR 2024
produces the same fixed action when inputs determined. Put simply, each run of DDCFR with the learned model consistently generates the same exploitability curve.
G COMPARISON WITH GREEDY WEIGHTS
We conduct experimental evaluations comparing DDCFR and Greedy Weights (Zhang et al. 2022) on extensive-form games. We integrate Greedy Weights with CFR by extending upon the officially released code for random norm-form games. We run grid search within the range of 0.1, 0.5, 1.0, 2.0, 5.0 to tune the hyperparameter "weight floor" for each game. The experimental results shown in Figure 7 demonstrate that DDCFR consistently converges faster lower exploitabil- ity on four extensive- form games. While Greedy Weights is designed to efficiently solve normal- form games and shows promising results extensive-form games, DDCFR designed explicitly for extensive-form games outperforms
Weights significantly. One key distinction between normal-form games and extensive-form games lies in the quantity of information sets. We suspect that when faced with large number of information sets, the computed weights in Greedy Weights might not be appropriate, resulting in poor performance in extensive-form games.
21'
Bettlshhip-2
Liar's Dooa-4
Kuhn Pokic
Lodae
CreedyWelighss
Expottaiing
10
10
500
1000
12"
500
625
1000
10"*
6225
700 Iertttons
1000
10
622
700
Iterations
Iberations
[terations
Figure 7: Performance comparison between DDCFR and Greedy Weights extensive-form games.
H COMPARISON AND COMBINATION WITH PREDICTIVE CFR+
The predictive CFR+ (PCFR+) Farina et al. 2021 is recently proposed state-of-the-art CFR vari- ant based on predictive Blackwell approachability. However, it not a consistently perl-perf algorithm. The authors of PCFR+ have already found in their paper that PCFR+ is faster than DCFR on non-poker games, whereas on poker games DCFR is the fastest. We present comparison be- tween our DDCFR and PCFR in Figure 8 The experimental results align with expectations, i.e., PCFR+ converges faster in non-pot non-poker games while DDCFR outperforms PCFR+ in poker games, given that our DDCFR is built upon DCFR. Nonetheless, DDCFR can improve the performance of DCFR to narrow the gap with PCFR+ on non-poker games, while amplifying the advantage over PCFR+ poker games.
10
Loduc Polce
Leduc Polerr
10-2
Geatspiel
10-1
Liar's
POPR4
DDCFR
Explotacitt
10-1
10-7
30
500
62.
755 lberations
805
1000
32
500
625
750
875
1000
12Ta
500
R25
750
875
1000
10"1
500
625
750
875
1000
Berstiin
[tenslime
Figure 8: Performance comparison between DDCFR and PCFR+ on four testing games.
It is worth emphasizing that our main contribution is not to propose specific algorithm, but to pro- pose a general dynamic and trainable discounting regret minimization framework. This framework can be universally applied in any CFR variants that employ fixed and manually specified discounting rules. The DDCFR algorithm presented in the paper is just an example application our framework to the DCFR algorithm.
15

---

Published as a conference paper at ICLR 2024
PCFR+ also uses fixed quadratic discounting scheme, formalized (イ)1)7, where gamma is set to in PCFR+ We apply our framework to learn dynamic discoumting averaging strategy, resulting in the Dynamic Predictive CFR+ (DPCFR+) algorithm. Figure Higusteiilussrates that this integration can further unlock PCFR+'s potential for solving non-poker games without sacrificing its performance on poker games.
10
Lodii Poleee
32-2
Big Ledua Poker
Confeplee-4
PCFR+
OFCER+
30n4
10
500
625
7:00 Iteratons
875
1000
11
500
625
750 Berratons
875
1000
10
500
025
750
875
1000
500
625
750
875
1000
Horrtt.005
Iterations
Figure 9: Performance comparison between DPCFR+ and PCFR+ on four testing games.
Besides PCFR+, we consider another algorithm PDCFR in the PCFR+ paper, which can be seen as combination of PCFR+ and DCFR. PDCFR also uses fixed discounting scheme and performs well on both pon-poker and poker games, benefiting from the characteristics inherited from PCFR+ and DCFR. We aim enhance PDCFR using our framework, resulting in the Predictive Dynamic Discounted CFR (PDDCFR) algorithm. As illustrated in Figure I0 our framework significantly enhances PDCFR's performance both non- non-poker and poker games.
10
Lodit Polcer
Leduo Poker
Gonfeggee-
Lite's Dised
POCFR PODCFR
Eiplotacitty
20
10
10
10"1
500
1000
12
1000
700
1000
750 Iterations
Iteratons
Ieerations
Iteratioos
Figure 10: Performance comparison between PDDCFR and PDCFR on four testing games.
All of the above results demonstrate the general applicability of our dynamic discounting framework. Our framework can be regarded as a performance booster that can be applied plug-and-play manner to various CFR variants that employ fixed discounting rules.
I ABOUT LOGARITHMIC OPERATION
The state in DDCFR consists of the normalized iteration and the normalized exploitability. When calculating the normalized exploitability, we employ logarithmic operation. We use Kuhn Poker as an example to demonstrate how normalized exploitability changes with the number of iterations. We compare three different normalization methods in T
Table 3: Normalized exploitability variation in Kuhn Poker with three normalization methods.
1
10
20
100
500
1000
E, (log E, log Emian/ (log En log Fmin)
4.583e-1 I
3.302e-2
1.599e-2
1.767e-3
1.699e-4
4.021e-5
1.000
0.902
0.875
0.793
0.706
0.652
(VE, (Emin) // (VEi / /Emin)
1.000
0.268
0.187
0.062
0.019
0.009
(E, Emin)/ bn Emin)
1.000
0.072
0.034
0.004
0.000
0.000
CFR variants have an upper bound on the regret values at a square root scale, but they converge much faster in practice. To capitalize this characteristic, adopt logarithmic normalization, which
16

---

Published as a conference paper at ICLR 2024
results in more even distribution of the normalized exploitability. This normalization technique facilitates neural network training, allowing the agent to make better decisions at each iteration.
J DESCRIPTION OF THE GAMES
Kuhn Poker is a simplified version of poker proposed by Harold W. Kuhn (Kuhn] 1950). It uses a deck of three cards (J, Q. K), and players begin by betting one chip into the pot and receiving private card from the shuffled deck. In the game, players can take four different actions: 1) fold, in which they forfeit the current game, and the other player wins the pot, 2) call, in which they match the other player's 's bet, 3) bet, in which they add more chips to the pot, and 4) check, in which they decline to place bet when not facing one from the other player. In Kuhn Poker, each player has chance to bet one chip. If neither player folds, both players reveal their cards, and the player with the higher card takes all chips in the pot. The utility for each player is determined by the difference in the number of chips they possess before and after playing.
Leduc Poker is a larger poker game first introduced in (Southey et al. 2005). It uses six cards divided into two suits, each with three ranks (Js, Qs, Ks, Jh, Qh, Kh). Similar lar to Kuhn Poker, each player starts by betting one chip, receiving a private card, and has the same action options. In Leduc Poker, there are two betting rounds. During the first round, each player has the opportunity to bet two chips, and in the second round, they can bet four chips. After the first round, one public card is revealed. If player's 's private card matches the public card, that player wins the game. Otherwise, the player with the highest private card wins the game.
Big Ledue Poker is more complex version of poker. It has rules similar to Leduc Poker but uses twenty-four cards divided into twelve ranks. In addition to the increased number of cards, it also allows maximum of six raises per round instead of the two raises allowed in Leduc Poker.
HUNL Subgame-x is a heads-up up no-limit Texas hold' em(NLL) sub- game generated and solved in real-time by the ofte-offthheart poker agent Libratus (Brown & Sandholm | In HUNL, the two players, P1 and P2, start each hand with $20,000 and are dealt two private cards from a standard 52-card deck. P1 places $100 in the pot, and P2 places $50 in the pot. P2 starts the first round of betting, and players take turns choosing to fold, call, check or raise. A round ends when a player calls if both players have acted. After the first round, three community cards are dealt face-up for all players to observe, and P1 starts a similar betting round. In the third and fourth rounds, one additional community card is dealt, and betting starts again with PI. Unless a player has folded, the player with the best five-card poker hand, constructed from their two private cards and the five community cards, wins the pot. In the case of a tie, the pot is split evenly. HUNL Subgame-3 begins at the start of the final betting round with $500 in the pot, and HUNL Subgume-4 begins at the start of the final betting round with $3,750 in the pot. In the first betting round, we use bet sizes of 0.5x, Ix the size of the pot, and an all-in bet. In other betting rounds, use Lx the pot and all-in.
Liar's Dice-x (Lisy et al., 2015) is a dice game where each player receives an x-sided dice and a cup used for concealment. At the start of the game, each player rolls the dice under their cup and examines the dice secretly. The first player starts by bidding on the form p-q, announcing that there at least dices with the number of q under both cups. The highest dice numbered x can be treated as any number. Players then have two choices during their turn: 1) bidding of the form p-q, with p or q being greater than the previous player's 's bidding, 2) calling 'Liar', ending the game immediately and revealing all the dices. If the last bid is not satisfied, the player called 'Liar' wins the game. The winner's utility is 1, and the loser's -1.
Goofspiel-x (Ross 1971) is bidding card game where players start with æ cards numbered 1... rr. A shuffled point card deck, also numbered 1 1r. is used in the game. The game proceeds in x rounds. Players select a card from their hand in each round to make sealed bid for the top revealed point card. When both players have chosen their cards, they show their cards simultaneously. The player who makes the highest bid wins the point card. If the bids are equal, the point card will be discarded. The game concludes after & rounds. The player who holds the most point cards wins the game and receives a utility of 1, while the losing player has a utility of -1. We use fixed deck of decreasing points and an imperfect information variant where players are only informed whether they have won or lost the bid, not the card played by the other player.
https:/ thub. wwt.:/ooo.cccooee. htt.:htw.ww.o.moooooootottttttta
17

---

Published as a conference paper at ICLR 2024
Battleship-x (Farina al. 2019) is classic board game where players secretly place a ship their separate grids size 2 x x at the start the game. Each ship x 2 in size and has a value of 2. Players take turns shooting at their opponent's 's ship, and the ship that has been hit at all its cells is considered sunk. The game ends when one player's ship is sunk or when each player has completed three shots. The utility for each player is calculated the of the values of the opponent's sunk ship minus the sum of the values of their own lost ship.
Small Matrix is a game where player I can choose five actions, i.e., rock, paper, scissors, AI, and A2, while player can only choose rock, paper, and scissors. When both players choose rock, paper, and scissors, the game is modified pock-pape--scisonn game where the winner receives two points when either player chooses scissors; otherwise, the winner receives one point. However, when player chooses the last two actions, i.e,, A A1/A2, player will lose 10,000/20,000.
We measure the sizes of the games in many dimensions and report the results in Table 4 In the table, #Histories measures the number of histories in the game tree. #infosets measures the number of information sets in the game tree. #Terminal histories measures the number of terminal histories in the game tree. Depth measures the depth of the game tree, i.e., the maximum number of actions in one history. Max size of infosels measures the maximum number of histories that belong to the same information set.
Table 4: Sizes of the games.
Game
#Histories
#Infosets
#Terminal histories
Depth
Max size of infosets
Small Matrix
21
15
3
5
Kuhn Poker
58
12
30
6
2
Goofspiel-3
67
16
36
5
4
Liar's s Dice-3
1,147
192
567
10
3
Battleship-2
10,069
3,286
5,568
9
4
Battleship-3
732,607
81,027
552,132
9
7
Goofspiel-4
1,077
162
576
7
Liar's Dice-4
8,181
1024
4,080
12
4
Ledue Poker
9,457
936
5,520
12
5
Big Ledue Poker
6,178,561
100,800
3,953,424
20
23
HUNL Subgame-3
398,112,843
69,184
261.126.360
10
1,980
244,005,483
43,240
158,388, 120
8
1,980
K RELATED WORK
DDCFR is closely related to hyperparameter optimization since regard the discounting weights as hyperparameters of the CFR algorithm. Hyperparameter optimization YYu & Zhu 2020) widely studied topic in machine learning, which aims find the optimal hyperparame- ters for a learning algorithm. Perhaps the most popular hyperparameter optimizer is grid/random search (Bergstra & Bengio 2012). More sophisticated techniques, such as Bayesian optimiza- tion (Snock et al.) 2012). have also proven effective on many different tasks. However, these ex- isting methods sufter from major problem, i.e., they only estimate the best fixed hyperparameter values that are used throughout the model learning. In contrast, DDCFR's 's discounting scheme can dynamically adjust the discounting weights online, not just find the best fixed value. The recently proposed techniques, such as meta-gradients (Xu et al. 2018), can dynamically tune hyperparam- eters on the fly by computing the gradients the objective function with respect to the hyperpa- rameters directly. However, in setting, computing the gradients of cxploitability with respect to discounting policy's ' parameters directly using backpropagation is challenging since the forward pass contains many CFR iterations which involve complex tree-based recursive computations, To our knowledge, Greedy Weights Zhang et af.] (022) is the only dynamic discounted regret mini- mization algorithm. However, focuses solving normal-form games, while DDCFR is designed explicitly for extensive-form games.
18


Reviews:
[{"review_id": "t3i5OvkdPM", "reviewer": "Reviewer_f8hB", "summary": "The paper introduces a Reinforcement Learning framework to manage the decaying parameters of Discounted CFR dynamically. In order to do so, the paper proposes a game-agnostic neural policy that receives as input the iteration and current exploitability and outputs DCFR's parameters and a time window for which those parameters will be used.\nThe proposed algorithm is proven to maintain the same (ignoring constants) regret guarantees than CFR, and experiments validate the approach of training a general policy in simple games and then evaluating it on a suite including much larger games. Ablations are provided, showing the value of each piece of the algorithm presented.", "questions": "* in section 3.4, you say that the exploitability computation can be done in parallel. I'm not conviced about this, since to run a CFR computation you need the parameters, which depend on the explotability of the average strategy **after** the latest iteration. Am I missing something? The only parallelizable step is the computation of the gradient in the ES subroutine\n* what happens in the first 500 iterations of DDCFR? Why are those hidden?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* simple idea. The whole paper is built on an initial observation and a single concept. This makes the paper follow a linear and clear structure\n* clear presentation. The paper is well written and answers almost all the questions one may have on the topic.\n* clear and sound experimentation framework. Experiments answer all the questions.\n* good empirical results. The results are encouraging and worth of publication", "weaknesses": "* the tradeoff between computational power and significance of the results is arguable, While I agree on the amortized costs of training on small games and use the same policy on larger instances, the computation of accurate exploitability is a hard constraint of the technique as presented in the paper. While I think that this is the largest weakness on the scalability of the technique, I do not think that such a constraint should be circumvented in this paper.\n* the comparison with RL algorithms could be explored a bit more. I'm convinced that PPO is a bad choice in the given setting due to long horizons and sparse rewards, but I'm not convinced on the multi-task nature of the RL challenge at hand. In my view, the task is identical and there is just stochasticity induced by the distribution over games during training. I'd expect a multi-task problem to explicitly pass to the policy the task as observation in order to condition the policy. My suggestion is to expand a bit more on the topic in the paper.(e.g. why wouldn't sset gamma=1 solve the long horizon problem?)\n\nMinor suggestions:\n* Is equation 4 wrongy formatted? Especially the parentheses and the $\\ast$ symbols\n* add the default DCFR parameters as a constant line in the plots in Figure 4", "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": "9RhNXkn0Lz", "reviewer": "Reviewer_u3Qf", "summary": "The paper introduces a dynamic weighting scheme for iterates of CFR, employing an MDP to determine optimal weights based on the algorithm's state. The empirical results support the effectiveness of this approach. Their scheme/framework is modular and can be applied to state-of-the-art CFR variants including DCFR and PCFR$^+$.", "questions": "I would suggest using a log-scale on the x-axis and start the x-axis at the first iteration. This allows easy comparison of the algorithms being compared and makes clear both short-term performance and long-term performance. It is confusing that the exploitability starts at small values at the beginning of the graph and then doesn't seem to change much in Kuhn, for example.\n\nCould you note the actual amount of time required to training the policy in Section 3.4? Additionally, I would suggest ordering \"(i)\", \"(ii)\", and \"(iii)\", in the same order you state them in Line 264.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "I reviewed a previous version of this paper.\n\nThe reviewers have adequately addressed the concerns brought up by the reviewers in this version of the paper. This includes applying their framework to PCFR$^+$ and comparing DDCFR directly to PCFR$^+$, as well as comparing to Greedy Weights.  Additionally, they provide a convergence analysis of their algorithm.", "weaknesses": "The algorithms' numerical performances are depicted starting at 500 iterations. It would be nice to show the performance of the algorithms in early iterations. \n\nWhile the paper notes that the time spent training the network to be used for the dynamic weight calculation is amortized by the number of times the policy computed is applied in application of the framework to equilibrium computation in different games, it never explicitly states how much time was spent training the network.", "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": "6cQuk0ko0q", "reviewer": "Reviewer_ffQX", "summary": "The paper offers an interesting extension to counterfactual regret minimization inspired by reinforcement learning for learning the Nash equilibrium in imperfect information games. Specifically, the paper proposes an MDP formulation of adjusting the discount rate in DCFR algorithms, a provable guarantee for the proposed RL approach, empirical tips and tricks for speeding up the convergence of the RL algorithm, and simulation studies on incomplete information games.", "questions": "1. Shouldn't there be (at the very least) some mild assumptions on boundedness of $\\tau$? In the degenerate case, suppose the initial policy always select $τ \\to \\infty$ and some really poor choice of discount rate. Will the algorithm still converge at the rate provided in Theorem 1?\n2. Purely out of curiosity, why should we directly \"jump\" to RL which, as the paper points out, \"notably sensitive to hyperparameters\". Does it make sense to consider a bandit-based approach for optimizing the discount rates?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem studied by the paper is an interesting one and the approach taken is intriguing.\n2. The paper provides the learned models in the supplemental materials, which make the results easier to verify.\n3. The paper offers a comprehensive overview of the problem setting and discusses well its contributions in context of existing works.\n4. The set of games considered in the experiments is comprehensive.", "weaknesses": "1. The paper could be better organized. Admittedly the problem studied here is a challenging one and necessitates heavy notations, as well as a collection of specific terminologies in both AGT and RL. However, some concepts are not used (or at least used explicitly), causing the paper to appear to be overwhelmingly dense at a first read. Assuming that the paper is targeted at audience with a game theory background, perhaps it would make more sense to spend some time describing and motivating the key algorithmic contributions from the RL angle. For instance, it might be useful to defer the mathematically rigorous definitions of *information set reach probability* or *interval history reach probability* to the appendix, and keep in the main body only an intuitive description of these concepts, as the paper's key contribution lies in the MDP-based approach proposed later. This takes up space and takes attention away from more important concepts such as exploitability $e$ and \"realized\" exploitability $E$.\n2. On are related note, there are some overloaded notations that make the paper harder to parse. For instance, the letter $a$ refers both to the actions taken by the agents in the \"Game Theory\" part of the paper and the action taken by the learner in the \"Reinforcement Learning\" part of the paper.\n3. For the experiments, it would be nice if the authors could provide the wall-clock times for DDCFR. DCFR has an added benefit that the algorithm requires little computation complexity at each round (the discount rates are specified beforehand) and it would be a fairer comparison to consider the computational aspect as well. (I am convinced by the arguments in Section 3.4, but adding these results will better validate the claims in Section 3.4 empirically.)\n4. Theorem 1 requires the action space to be discretized, yet this is not stated explicitly (also see the following section for question on boundedness of $\\tau_t$.\n5. It appears that experiments are only run once, yet multiple runs are required to demonstrate that the proposed approach convincingly outperform DCFR, and the figures in the paper are not due to luck alone.", "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": "6emmtxogRs", "reviewer": "Reviewer_ESsF", "summary": "This paper studies the CFR framework in the setting of incomplete information games, and proposes a modification that allows for equilibrium finding using a dynamic, automatically-learned scheme. To do so, the authors formulate CFR’s iteration process as an MDP and give a transformation that frames the (CFR) discount scheme as a policy optimization problem wherein the dynamic discounting scheme is an agent that interacts with the MDP. The primary motivation of this framework is to be able to learn discounting policies that can generalize over different IIGs, rather than having to be carefully designed for specific games. In this direction, the authors design a training algorithm based on evolution strategies that can generalize well, even to games that are not seen in the training process.", "questions": "- How does the DDCFR technique compare to deep methods like Deep CFR when it comes to larger scale games? \n- How does DDCFR empirically scale to games with more players? In principle, it seems to me that it would provide similar benefits compared to current CFR methods in multiagent settings but I’m curious if this is something the authors have explored.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The core idea of the paper, namely the dynamic policy optimization procedure for learning discount schemes, is conceptually important since it allows generalization to unseen games, circumventing the need for suboptimal fixed discounting schemes. Moreover, the experiments prevented are convincing, showing not just benchmarking against current state of the art but also ablation studies which gives a stronger idea of what aspects of DDCFR makes the most improvement over standard CFR approaches. The DDCFR methodology is also shown to be effective in modifying other CFR variants, which is a useful property to have. Moreover, the paper is well written in the way that motivations are clear, and any potential concerns are discussed in fair detail (for instance, the discussion about the potential additional computational costs).", "weaknesses": "The framework introduced seems to be useful in practice and effectively stitches together several well-established ideas. A minor weakness would be that there isn’t much technical novelty, since all the results and techniques used are taken from prior works. However, this doesn’t diminish the quality of the results greatly to me. Another minor weakness is that currently the explanations in the ablation studies section feel quite vague and handwavy. My suggestion to the authors would be to highlight several key results in the table and provide a more substantiated explanation for each. It would also have been nice to see running time comparisons in the experiments to properly verify the authors’ claims about additional computational costs not causing major increases in running time.", "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 (spotlight)