Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent

1 Introduction

Imperfect-information games (IIGs) model strategic interactions between players with hidden information. Solving such games is challenging since players must reason under uncertainty about opponents' private information. The hidden information plays an essential role in real-world situations such as medical treatment [Sandholm, 2015], negotiation [Gratch et al., 2016], and security [Lisy et al., 2016], making the research on IIGs theoretically and practically crucial.

∗Corresponding authors.

The full version is at https://arxiv.org/abs/2404.13891.

In this work, we focus on solving two-player zero-sum (2p0s) IIGs. The typical goal in these games is to find an (approximate) Nash equilibrium (NE) in which no player can benefit from deviating unilaterally from the equilibrium. The common iterative approach minimizes total regrets of both players so that their average strategies over time converge to a NE. The family of counterfactual regret minimization (CFR) algorithms [Zinkevich et al., 2007] decomposes the total regret into the sum of counterfactual regrets associated with decision nodes. Then it employs a local regret minimization algorithm, such as Regret Matching (RM) [Hart and Mas-Colell, 2000] or its variant RM+ [Tammelin, 2014], at each decision node to effectively minimize counterfactual regret. Due to the sound theoretical guarantee and strong empirical performance, CFR and its variants have enabled several major breakthroughs in this field [Bowling et al., 2015; Moravˇc´ık et al., 2017; Brown and Sandholm, 2018; Brown and Sandholm, 2019b].

Besides CFR, Online Mirror Descent (OMD) [Beck and Teboulle, 2003] stands out as a prominent and general regret minimization algorithm. It has promising theoretical results but remains less competitive than CFRs when directly applied to solving IIGs. Recently, researchers have tried to build connections between CFR and OMD [Farina et al., 2021; Liu et al., 2022]. The study by [Farina et al. ] demonstrates that RM+ is essentially a specialized form of OMD when employed to minimize counterfactual regret at each decision node. This connection inspires an optimistic variant of RM+, named Predictive RM+ (PRM+), seeking to benefit from the predictability of slowly-changing counterfactual losses over time. Its extension Predictive CFR+ (PCFR+) exhibits extremely fast convergence on non-poker IIGs.

Despite the notable success of PCFR+, a limitation arises from its practice of assigning uniform weights to each iteration when determining regrets. The algorithm becomes particularly challenging when dealing with dominated actions, leading to high regrets for other actions and requiring a substantial number of iterations to mitigate this negative impact 1 . Assigning more weights to recent iterations has shown to be important for fast convergence [Tammelin, 2014; Brown and Sandholm, 2019a; Grand-Cl´ement and Kroer, 2023]. Notably, Discounted CFR (DCFR) [Brown and Sandholm, 2019a] is a family of algorithms that discounts prior iterations when determining both regrets and average strategy. Thus, it is desirable to design a CFR variant that not only allocates more weights to recent iteration, thereby alleviating high regrets from earlier iterations, but also leverages predictions to accelerate convergence.

To this end, we delve into minimizing weighted counterfactual regret with OMD and optimistic variant:

• We demonstrate that by directly employing OMD to minimize weighted counterfactual regret, we obtain a CFR variant, DCFR+, which incorporates regret discounting similar to DCFR and clips negative regrets akin to CFR+. Remarkably, the CFR variant previously discovered through evolutionary search [Hang et al., 2022] is a special case of DCFR+, showcasing faster convergence than DCFR.
• Furthermore, by applying optimistic OMD, we derive a novel CFR variant, PDCFR+, which leverages predicted regrets to compute new strategy like PCFR+, while updating regrets similar to DCFR+. It swiftly mitigates negative effects of dominated actions and consistently leverages predictions to speed up convergence.
• We observe that the updating rule of OMD with increasing weighted loss is equivalent to OMD with an increasing learning rate or a decreasing regularization term. This observation offers a partial explanation for the superior performance of DCFR.
• We theoretically prove that DCFR+ and PDCFR+ converge to a NE under distinct weighting schemes for regrets and average strategies, requiring the weighting scheme for regrets to be more aggressive than that for average strategies.
• Finally, we conduct extensive experimental evaluations of CFR variants on commonly used IIGs in the research community. We find that PDCFR+ outperforms other CFR variants by 4-8 orders of magnitude on non-poker games and small poker games, while DCFR+ converges fastest on large-scale poker games.

2 Preliminaries

In this section, we present the notations for formulating IIGs, introduce typical regret minimization algorithms, and discuss the vanilla CFR algorithm along with its variants.

2.1 Sequential Decision Process

Sequential decision process [Farina et al., 2019a] is a tree-based formalism for describing each player's decisionmaking in IIGs, consisting of two types of nodes: decision nodes and observation nodes. At each decision node j ∈ J , the player selects an action based on a local strategy xj ∈ ∆nj , where ∆nj is a simplex over the action set Aj ⊆ A of size nj. After taking the action a, the player proceeds to an observation node k = ρ(j, a). At each observation node k ∈ K, the player receives a signal s ∈ Sk and then reaches another decision node j ′ = ρ(k, s). The set Cj,a = {ρ(ρ(j, a), s) : s ∈ Sρ(j,a)} denotes all decision nodes that are earliest reachable after taking action a at j. We introduce a dummy root decision node o with one action to ensure a unique root. An illustration is given in Appendix A.

1 We provide a motivating example in section 3.

For a local strategy set {xj}j∈J , we can construct a sequence-form strategy ˙x represented as a vector indexed over {(j, a) : j ∈ J , a ∈ Aj}. Each entry in the vector corresponds to a pair (j, a), with the value representing the product of probabilities of all actions along the path from the root to (j, a). The sequence-form strategy space is denoted by X .

In a 2p0s IIG, where player 1 and player 2 have sequencefrom strategy space X and Y, and the set of decision nodes are Jx and Jy , the problem of finding a NE can be formulated as a bilinear saddle point problem

where A is a sparse payoff matrix encoding the losses for player 1. For a strategy profile ( ˙x, ˙y), let δ1( ˙x, ˙y) denote the incentive for player 1 to unilaterally choose another strategy: δ1( ˙x, ˙y) = ˙x⊤A ˙y -min ˙x′∈X ˙x′⊤A ˙y. Similarly, δ2( ˙x, ˙y) = max ˙y′∈Y ˙x⊤A ˙y′ - ˙x⊤A ˙y. An ϵ-NE satisfies δi( ˙x, ˙y) ≤ ϵ, ∀i ∈ {1, 2}. The exploitability of ( ˙x, ˙y) measures its distance from equilibrium and is defined by e( ˙x, ˙y) = ∑i∈{1,2} δi( ˙x, ˙y)/2.

2.2 Regret Minimization

A regret minimization algorithm [Zinkevich, 2003] repeatedly plays against an unknown environment and starts with a decision x1 ∈ D ⊆ Rn , where D is the decision space. In each iteration t, it observes a loss ℓt ∈ Rn from the environment and computes its next decision xt+1 based on past decisions x1 , . . . , xt and previous losses ℓ1 , . . . , ℓt . The objective of the algorithm is to minimize the total regret

Online Mirror Descent (OMD) [Beck and Teboulle, 2003] stands out as a famous regret minimization algorithm compatible with arbitrary decision spaces. It updates the decision according to x1 = argminx′∈D ψ(x′ ), and

where ψ : D → R is a regularizer, Bψ(x′ || x) = ψ(x′ ) - ψ(x) - ⟨∇ψ(x), x′ - x⟩ is the Bregman divergence associated with ψ, and η > 0 is an arbitrary step size. Optimistic OMD [Syrgkanis et al., 2015] seeks to benefit from the predictability of slowly-changing loss ℓt . In iteration t, it predicts the next iteration's loss ℓt+1 as mt+1 and updates the decision according to x1 = z0 = argminx′∈D ψ(x′ ), and

Regret Matching (RM) [Hart and Mas-Colell, 2000] and Regret Matching+ (RM+) [Tammelin, 2014] are two regret minimization algorithms operating on the simplex ∆n . RM typically starts with a uniform random strategy x1 . On each iteration t, RM calculates the instantaneous regret rt = ⟨xt , ℓt ⟩1 - ℓt and then accumulates it to obtain the cumulative regret Rt = ∑tk=1 rk . The next strategy is proportional to the positive cumulative regret, i.e., xt+1 = [Rt ]+ / ∥∥∥[Rt ]+∥∥∥1 , where [·]+ = max{·, 0}. For convenience, we define 0/0 as the uniform distribution. RM+ is a straightforward variant of RM. It sets any action with negative cumulative regret to zero in each iteration so that it promptly reuses an action showing promise of performing well. Formally, Rt = [Rt-1 +rt ]+ and xt+1 = Rt / ∥Rt ∥1 .

2.3 Counterfactual Regret Minimization

Counterfactual Regret Minimization (CFR) [Zinkevich et al., 2007] is one of the most popular equilibrium-finding algorithms for solving IIGs. It operates as a regret minimization algorithm within the sequence-form strategy space. Given a sequence-form strategy ˙xt ∈ X and a loss ˙ ℓt = A ˙yt , the key concept involves constructing a counterfactual loss

CFR then employs RM to minimize the total counterfactual regret RT j = maxx′j ∈∆nj ∑Tt=1 〈ℓtj , xtj -x′j 〉 at each decision node with respect to counterfactual loss. It is guaranteed that the total regret RT is bounded by the sum of the total counterfactual regrets under each decision node, i.e., RT ≤ ∑j∈J [RT j ]+.

The computational procedure of CFR on each iteration t is summarized as follows: (1) decomposes the sequence-form strategy ˙xt into local strategies xtj for each decision node j ∈ J ; (2) recursively traverses the game tree to calculate the counterfactual loss ℓtj ; (3) accumulates the instantaneous counterfactual regret rt j = 〈xtj , ℓtj 〉 1-ℓtj to obtain the cumulative counterfactual regret Rtj = Rt-1 j + rt j ; (4) computes the new local strategy xt+1 j = [Rtj ]+ / ∥∥∥[Rtj ]+∥∥∥1 for the next iteration; (5) constructs ˙xt+1 based on local strategies; (6) computes the average strategy ¯xt = Xt /∥Xt ∥1 , where Xt =Xt-1 + ˙xt is the cumulative strategy. If both players employ CFR, the average strategy profile 〈 ¯xT , ¯ yT 〉 converges to a ∆(|Jx| + |Jy|)√|A|/√T-NE after T iterations, where ∆ is the range of losses.

2.4 CFRVariants

Since the birth of CFR, researchers have proposed many novel CFR variants, greatly improving the convergence rate of the vanilla CFR. CFR+ [Tammelin, 2014; Bowling et al., 2015] incorporates three small yet effective modifications, resulting in an order of magnitude faster convergence compared to CFR. (1) CFR+ employs RM+ instead of RM, i.e., Rtj = [Rt-1 j +rt j ]+. (2) CFR+ adopts a linearly weighted average strategy where iteration t is weighted by t, i.e., Xt = Xt-1+t ˙xt . (3) CFR+ uses the alternating-updates technique.

DCFR [Brown and Sandholm, 2019a] is a family of algorithms which discounts prior iterations' cumulative regrets and dramatically accelerates convergence especially in games where some actions are very costly mistakes. Specifically,

Linear CFR [Brown and Sandholm, 2019a] is a special case of DCFR where iteration t's contribution to cumulative regrets and cumulative strategy is proportional to t.

2.5 The Predictive CFRVariant

Recently, [Farina et al., 2021] demonstrates that a general regret minimization algorithm can be adapted for constructing a regret minimization algorithm tailored to a simplex. To illustrate, let us focus on the objective of minimizing the total counterfactual regret RT j at a decision node j. Additionally, we have a general regret minimization algorithm A, which we apply to a decision space Rnj ≥0 . At each iteration t, upon obtaining the counterfactual loss ℓtj , we initially compute a modified loss ˜ ℓtj = -rt j = ℓtj - 〈ℓtj , xtj 〉 1. It is then fed into A, and we receive its next decision ˜xt+1 j ∈ Rnj ≥0 . Finally, we obtain the next strategy as xt+1 j = ˜xt+1 j / ∥∥˜xt+1 j ∥∥1 .

Based on the construction, [Farina et al., 2021] illustrates that employing OMD with ψ = 12 ∥·∥22 as the algorithm A yields the same strategy as RM+ in each iteration. Additionally, by using Optimistic OMD with ψ = 12 ∥·∥22 and mt+1 = -vt+1 j , where vt+1 j = 〈mt+1 j , xtj 〉 1 -mt+1 j is the prediction of rt+1 j and mt+1 j = ℓtj is the prediction of ℓt+1 j , Predictive RM+ (PRM+) is obtained, i.e.,

Moreover, [Farina et al., 2021] introduces Predictive CFR+ (PCFR+), which uses PRM+ as the regret minimization algorithm in each decision node and incorporates a quadratic weighted average strategy, defined as Xt = Xt-1 + t2 ˙xt . We summarized CFR and typical variants in Table 1.

3 Performance Decline of PCFR+ in the Presence of Dominated Actions

Although PCFR+ successfully employs prediction to significantly accelerate convergence, we show that its performance deteriorates notably when facing dominated actions. Consider a 2 × 2 zero-sum normal-form game NFG (2), represented by maxx∈∆2 miny∈∆2 xT Uy, where U = ((1, 0) , (0, 2)) is Iterations (×103)

Iterations (×103)

Figure 1: Convergence results of four CFR variants on two games.

player 1's utility matrix. As shown in the left plot of Figure 1, PCFR+ converges extremely faster than other CFR variants, benefiting from prediction during strategy updates. However, when we introduce a dominated action for each player, resulting in NFG (3), where U = ((1, 0, 5) , (0, 2, 0) , (0, 0, 100)), PCFR+'s performance declines greatly as depicted in the right plot. For player 2, action 3 is dominated by action 1, allowing its elimination. Thus, player 1's action 3 can also be eliminated. Consequently, NFG (3) reduces to NFG (2), with the NE x = y = ( 2 3 , 13 , 0). After the first iteration of PCFR+, player 2 has cumulative regrets R1 = ( 100 3 , 100 3 , 0). The substantial loss of action 3 leads to high cumulative regrets for player 2's actions 1 and 2, making it challenging to distinguish between these two actions. Due to the small instantaneous regrets per iteration, PCFR+ requires about 1500 iterations to achieve a 2:1 cumulative regrets for actions 1 and 2, producing an approximate NE.

While LinearCFR and DCFR initially converge faster than PCFR+ in NFG (3) by assigning more weights to recent iterations and alleviating high regrets from earlier iterations, PCFR+ leverages predictions to surpass them after 2000 iterations. It will be a best-of-both-worlds algorithm if we design a CFR variant that not only allocates more weights to recent iterations but also employs predictions to compute a new strategy, therefore greatly speeding up convergence.

4 MinimizingWeighted Counterfactual Regret with OMD and Optimistic Variant

In various situations, it makes sense to consider recent iterations as more crucial than earlier ones. Take equilibriumfinding algorithms as an example, earlier iterations are prone to selecting incorrect actions, resulting in substantial losses and causing significant regrets [Brown and Sandholm, 2019a]. Additionally, it is typical for recent iterations to generate strategies that are closer to a NE [Perolat et al., 2021]. Therefore, assigning more weights to recent iterations is a natural choice, potentially leading to fast convergence [Abernethy et al., 2018; Wang and Abernethy, 2018].

Moreover, it is a prevalent practice to permit distinct weighting sequences for regrets and average strategies to facilitate fast convergence. For instance, CFR+ adopts a linearly weighted average strategy while employing a uniform weighting sequence for regrets. Besides, DCFR takes this approach a step further by using distinct weighting sequences for both regrets and average strategy.

In a weighted regret minimization algorithm applied to the sequence-form strategy space, the loss ˙ ℓt incurred at iteration

Input: game G, total iterations T, general regret minimization algorithm A, weighting sequences w and τ . 1 for j ∈ J do 2 Aj ← instantiate Awith D = Rnj ≥0 ; 3 x1j ←Aj.first decision(); 4 construct ˙x1 by {x1j | j ∈ J }; 5 for t = 1 → T do 6 decompose ˙xt into {xtj | j ∈ J }; 7 calculate the counterfactual loss {ℓtj | j ∈ J } based on the loss ˙ ℓt = A ˙yt ; 8 for j ∈ J do 9 rt j ← 〈ℓtj , xtj 〉 1 - ℓtj ; 10 ˜ ℓtj ← -wtrt j ; 11 Aj.observe loss(˜ ℓtj ); 12 ˜xt+1 j ←Aj.next decision(); 13 xt+1 j ← ˜xt+1 j / ∥∥˜xt+1 j ∥∥1 ; 14 construct ˙xt+1 by {xt+1 j | j ∈ J }; 15 Xt ←Xt-1 + τ t ˙xt ; 16 ¯xt ← Xt / ∥Xt ∥1 ; Output: The final average strategy ¯xT .

t is scaled by the weight wt, forming a sequence of weights denoted as w. The total weighted regret by the sequence w is

Moreover, define ¯xtτ to be the weighted average strategy scaled by the weighting sequence τ :

To minimize the total weighted regret RTw , we first decompose it into the sum of the total weighted counterfactual regrets RT j,w under each decision node by constructing the counterfactual loss ℓtj at each iteration t, where

so that we have the guarantee RTw ≤ ∑j∈J [RT j,w ]+ and transform the objective to minimize the total weighted counterfactual regret RT j,w at each decision node.

To develop an algorithm for minimizing weighted counterfactual regret by leveraging a general regret minimization algorithm, we propose a construction method similar to the one described in [Farina et al., 2021], but with a modified loss ˜ ℓtj = -wtrt j . A concise summary of this approach is presented in Algorithm 1.

As demonstrated in Theorem 1 (all proofs of the theorems are in Appendix C), when employing OMD with ψ = 1 2 ∥·∥22 as the algorithmA, it simplifies to the WCFR+ algorithm:

Similarly, when employing optimistic OMD with ψ = 1 2 ∥·∥22 , it reduces to the PWCFR+ algorithm:

Theorem 1. For all η > 0, when employing OMD and optimistic OMD with ψ = 1 2 ∥·∥22 as the algorithmA, they reduce to WCFR+ and PWCFR+, respectively.

As illustrated in Theorem 2, when both players employ a weighted regret minimization algorithm in a 2p0s IIG, the weighted average strategy profile converges to a NE.

Theorem2. Assuming both players employ aweighted regret minimization algorithm with the weighting sequence τ for the average strategy in a 2p0s IIG, and given that the two players have total weighted regrets RT τ,x and RT τ,y respectively, the weighted average strategy profile (¯xTτ , ¯ yT τ ) after T iterations forms a RT τ,x+RT τ ,y

Although WCFR+ and PWCFR+ algorithms aim to minimize the total weight regret RTw , we show that they also minimize the total weighted regret RT τ as long as the weighting sequence w is more aggressive than τ .

Theorem 3. Assuming both players employ the WCFR+ algorithm with the weighting sequence w for loss and τ for the average strategy in a 2p0s IIG, and { τt wt }t≤T is a positive non-increasing sequence, the weighted average strategy profile (¯xTτ , ¯ yT τ ) after T iterations forms a

Theorem 4. Assuming both players employ the PWCFR+ algorithm with the weighting sequence w for loss and τ for the average strategy in a 2p0s IIG, and { τt wt }t≤T is a positive non-increasing sequence, the weighted average strategy profile (¯xTτ , ¯ yT τ ) after T iterations forms a (∑j∈Jx∪Jy √2 τ 1 w1 ∑Tt=1 τ twt ∥∥rt j - vt j ∥∥22) / ∑Tt=1 τ t -NE.

A question remains regarding the selection of suitable weighting sequences in practical applications. Inspired by DCFR [Brown and Sandholm, 2019a] and to avoid potential numerical issues, we adopt a similar less-aggressive discounting sequence, resulting in a specific algorithm DCFR+:

DCFR+ integrates features from both CFR+ and DCFR in a principled manner. It discounts cumulative regrets, assigning more weights to recent instantaneous regrets. Additionally, it clips the negative part of cumulative regrets, allowing for quick reuse of promising actions. Notably, the CFR variant discovered through evolutionary search [Hang et al., 2022] emerges as a special case of DCFR+ where α = 1.5 and γ = 4, showcasing faster convergence than DCFR.

We adopt a similar weighting sequence for PWCFR+, resulting in the PDCFR+ algorithm. PDCFR+ utilizes predicted cumulative regrets to compute new strategy akin to PCFR+, while updating cumulative regrets similar to DCFR+:

Interestingly, our connection between OMD and WCFR+ also provides a new perspective to understand the increasing weight wt in DCFR and DCFR+. When employing OMD with ψ = 12 ∥·∥22 as the algorithm A, it updates the decision ˜xt+1 j , corresponding to the cumulative regretsRtj inWCFR+:

It can be equivalently written as:

We can interpret the increasing weight wt in two ways: an increasing learning rate ηt = ηwt or a decreasing regularization term 1 wt . As a result, during the early iterations, cumulative regretsRtj , i.e., ˜xt+1 j , are learned at a gradual pace or regularized by a substantial strength. This interpretation aligns with our intuition, as we aim to control cumulative regrets from growing excessively large in the initial stages.

5 Experiments

In this section, we briefly describe testing games, compare PDCFR+ with other CFR variants, and analyze PDCFR+'s superior performance on normal-form games.

5.1 Testing Games

We use several commonly used IIGs in the research community and provide brief descriptions below. For more details, please refer to the Appendix B. Kuhn Poker [Kuhn, 1950] is a simplified poker with a three-card deck and one chance to bet for each player. Leduc Poker [Southey et al., 2005] is a larger game with a 6-card deck and two betting rounds. In Liar's Dice (x) (x=4, 5) [Lis`y et al., 2015], each player gets an xsided dice, which they roll at the start and take turn placing bets on the outcome. Goofspiel (x) (x=4, 5) [Ross, 1971] is a card game where each player has x cards and aims to score points by bidding simultaneously in x rounds. GoofspielImp

(x) (x=4, 5) is a imperfect variant of Goofspiel (x), where bid cards remain unrevealed. In Battleship (x) (x=2, 3) [Farina et al., 2019b], players secretly position a 1 × 2 ship on separate 2 × x grids and take turns firing at the opponent's ship three times. HUNL Subgame (x) (x=3, 4) is a heads-up no-limit Texas hold'em (HUNL) subgame generated by the top poker agent Libratus [Brown and Sandholm, 2018].

The testing games selected exhibit diverse structures and considerable game sizes, presenting a nontrivial challenge to solve. However, their complexity remains manageable for an algorithm to complete within two weeks, rendering them highly suitable for evaluating algorithmic performance. When extending to larger games, we can capitalize on a variety of well-established techniques, such as abstraction, decomposition [Burch et al., 2014], and subgame-solving [Brown and Sandholm, 2017; Brown et al., 2018]. These approaches effectively mitigate the increased complexity associated with scaling up the size of the games.

5.2 Convergence Results

We compare PDCFR+ with CFR+, LinearCFR, DCFR, PCFR+ and DCFR+ across twelve games. For DCFR, we adopt the hyperparameters suggested by the authors, specifically α = 1.5, β = 0, and γ = 2. Regarding DCFR+ and PDCFR+, according to Theorems 3 and 4, α and γ must ensure that { τt wt }t≤T forms a positive, non-increasing sequence. However, in practice, we find that the range of values for α and γ can be larger, and they generally yield good convergence results. Based on these observations, for DCFR+, we set α = 1.5 and γ = 4 following [Hang et al., 2022], which is automatically set by an evolutionary search algorithm. We perform a coarse grid search to fine-tune the hyperparameters for PDCFR+, and the best one, i.e., α = 2.3 and γ = 5, is then used across all games. All algorithms utilize the alternating-updates technique.

We run each algorithm for 20,000 iterations in each testing game to observe their long-term behavior, with Figure 2 displaying exploitability curves. We set a minimum reachable exploitability of 10-12 , denoting the point where the average strategy profile is considered sufficiently converged to a NE. Across non-poker games (Goofspiel, Battleship, Liar's Dice), PDCFR+ outperforms others by 4-8 orders of magnitude, taking 2,000-12,000 iterations to achieve the minimum reachable exploitability. For poker games, PDCFR+ excels in Kuhn Poker. In Leduc Poker, PDCFR+ initially lags behind DCFR and CFR+ up to 10,000 iterations but exhibits faster convergence thereafter. In the large-scale poker game HUNL Subgame, PDCFR+ performs comparably to CFR+ and PCFR+, while DCFR+ emerges as the fastest algorithm. In summary, PDCFR+ stands as an improved version of PCFR+, with a similar property for excellence in non-poker games.

PDCFR+ employs γ = 5 in the computation of average strategies, while PCFR+ utilizes quadratic averaging, equivalent to γ = 2 in PDCFR+. In order to assess whether PDCFR+'s improved performance is solely attributable to its specific averaging of strategies, we present the performance of PCFR+ (5), which employs γ = 5, in Figure 2. PCFR+ (5) outperforms PCFR+ with quadratic averaging in nine games. PDCFR+ performs similarly to PCFR+ (5) in six games but Iterations (×103)

Iterations (×103)

Iterations (×103)

Iterations (×103)

Figure 3: The top plots illustrate the convergence results of four CFR variants on two games. The bottom plots show that PDCFR+ quickly learns stable cumulative regrets in NFG (3).

exhibits significantly faster convergence in five games. Particularly in GoofSpiel (5) and Liar's Dice (5), PDCFR+ surpasses PCFR+ (5) by 5-7 orders of magnitude. Thus, we conclude that the acceleration observed in PDCFR+ is not solely a result of using a more aggressive weighting scheme for determining average strategies but is also attributed to the weighting scheme employed in determining regrets.

To further comprehend the enhanced performance of PDCFR+, consider the normal-form games NFG (2) and NFG

(3) discussed in section 3. Top plots of Figure 3 show that PDCFR+ converges extremely fast on both games, not affected by the dominated actions. After the first iteration of PDCFR+ in NFG (3), player 2 has high cumulative regrets R1 = ( 100 3 , 100 3 , 0) due to the dominated action 3. As shown in the bottom-right plot of Figure 3, PDCFR+ rapidly discounts cumulative regrets, and at around the 200th iteration, it has already learned stable 2:1 cumulative regrets for actions 1 and 2, producing an approximate NE. In contrast, PCFR+ is still struggling with fluctuations and requires much more iterations to approach a NE. This highlights PDCFR+'s ability to swiftly mitigate the negative effects of dominated actions and consistently leverage predictions to accelerate convergence.

6 Conclusions and Future Research

This work proposes to minimize weighted counterfactual regret with OMD and optimistic variant. It provides a new perspective to understand DCFR's superior performance and derives a novel CFR variant PDCFR+. PDCFR+ discounts cumulative regrets from early iterations to mitigate the negative effects of dominated actions and consistently leverages predictions to accelerate convergence. Experimental results demonstrate that PDCFR+ achieves competitive results compared with other CFR variants. Recent work [Farina et al., 2023] proposes two fixes for PRM+, achieving O(1/T) convergence in normal-form games. It is worthwhile to investigate whether our algorithm can achieve similar convergence by introducing a specific weighting sequence. Besides, combining PDCFR+ with function approximations [Brown et al., 2019] and integrating it with the dynamic discounting framework [Hang et al., 2024] are also promising future works.

Acknowledgments

This work is supported in part by the National Science and Technology Major Project (2022ZD0116401); 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 (CCF)-Tencent Open Fund.