Source-linked AI summary
Solving Imperfect-Information Games via Discounted Regret Minimization
Noam Brown, Tuomas Sandholm
TL;DR
Large imperfect-information games need practical iterative methods for approximate equilibrium computation, and CFR is widely used for this purpose. The paper develops CFR variants that discount and reweight iterations, alter regret minimization, and use optimistic regret matching. These variants substantially improve performance, with DCFR 3/2,0,2 matching or outperforming CFR+ in all settings and offering broader compatibility with pruning and sampling techniques.
Problem
Existing CFR methods are widely used for large imperfect-information games, but CFR+ performs relatively poorly when some actions are very costly mistakes.
Source: Introduction · p. 1Method
The paper develops CFR variants that discount earlier regrets, reweight iterations, use alternative regret minimizers, and apply optimistic regret matching.
Source: Introduction · p. 1, Regret Discounting for CFR and Its… · p. 3, Optimistic CFR Variants · p. 6Results
DCFR 3/2,0,2 matched or outperformed CFR+ in all settings.
Source: Conclusions · p. 7Takeaways & Limitations
One variant outperformed CFR+ in every game tested, while several new variants remained compatible with pruning techniques and one was compatible with game-tree sampling.
Source: Introduction · p. 1For β ≤ 0, suboptimal actions' regrets no longer approach −∞, reducing compatibility with pruning methods; NormalHedge also makes each iteration five times longer in the reported implementation.
Source: Regret Discounting for CFR and Its… · p. 4, NormalHedge for CFR Variants · p. 6
Abstract
from arXiv · showhide
Counterfactual regret minimization (CFR) is a family of iterative algorithms that are the most popular and, in practice, fastest approach to approximately solving large imperfect-information games. In this paper we introduce novel CFR variants that 1) discount regrets from earlier iterations in various ways (in some cases differently for positive and negative regrets), 2) reweight iterations in various ways to obtain the output strategies, 3) use a non-standard regret minimizer and/or 4) leverage "optimistic regret matching". They lead to dramatically improved performance in many settings. For one, we introduce a variant that outperforms CFR+, the prior state-of-the-art algorithm, in every game tested, including large-scale realistic settings. CFR+ is a formidable benchmark: no other algorithm has been able to outperform it. Finally, we show that, unlike CFR+, many of the important new variants are compatible with modern imperfect-information-game pruning techniques and one is also compatible with sampling in the game tree.
Introduction
Imperfect-information games require approximate equilibrium methods at large scale, where CFR variants are widely used. The paper introduces discounted and reweighted CFR variants, including one that outperforms CFR+ in every tested game.
- Imperfect-information games model strategic interactions with hidden information, including negotiations, cybersecurity, and auctions.Source: Introduction · p. 1
- Large games that cannot fit manageable linear programs are typically solved with iterative equilibrium-approximation algorithms.Source: Introduction · p. 1
- CFR variants are among the most popular iterative algorithms, while CFR+ marked a key practical breakthrough.Source: Introduction · p. 1
- The paper shows that discounting earlier iterations addresses CFR+'s weakness in games where some actions are very costly mistakes.Source: Introduction · p. 1
- One proposed variant outperforms CFR+ in every game tested, including large-scale realistic settings.Source: Introduction · p. 1
Notation and Background
The paper formalizes imperfect-information extensive-form games, strategies, payoffs, regret, and equilibrium concepts. CFR uses regret minimization to construct strategies whose averages approach equilibrium, while CFR+ modifies regret updates and averaging for faster practical convergence.
- An imperfect-information extensive-form game is a finite tree-form interaction with players, chance, hidden states, actions, terminal payoffs, and payoff range Δ.Source: Notation and Background · p. 1
- Information sets group states that are indistinguishable to a player, requiring identical action strategies across those states.Source: Notation and Background · p. 2
- A strategy assigns action probabilities at each information set, and a strategy profile specifies one strategy for every player.Source: Notation and Background · p. 2
- CFR computes instantaneous action regret from the value difference between choosing an action and following the current strategy, then accumulates regret over iterations.Source: Notation and Background · p. 2
- In two-player zero-sum games, CFR's average strategies provide an anytime approach to finding an ϵ-Nash equilibrium.Source: Notation and Background · p. 2
- CFR+ floors negative regret-like values at zero and weights iteration T by T in its average strategy, typically improving practical convergence despite a worse bound by a constant factor of 2.Source: Notation and Background · p. 2
Weighted Averaging Schemes for CFR+
CFR+ traditionally uses linear averaging, but the paper analyzes broader non-decreasing iteration weights. Empirically, quadratic weighting was faster and was used for CFR+ and its variants.
- CFR+ traditionally uses linear averaging, weighting iteration t proportionally to t.Source: Weighted Averaging Schemes for CFR+ · p. 3
- The convergence theorem covers any positive non-decreasing weights wt, with wi ≤ wj for earlier iteration i and later iteration j.Source: Weighted Averaging Schemes for CFR+ · p. 3
- The resulting convergence bound is never lower than vanilla CFR's bound with uniformly equal iteration weights.Source: Weighted Averaging Schemes for CFR+ · p. 3
- Empirically, weighting iteration t by t^2 made CFR+ converge faster than weighting it by t, so the paper uses t^2 throughout its experiments.Source: Weighted Averaging Schemes for CFR+ · p. 3
Regret Discounting for CFR and Its Variants
The paper discounts earlier iterations in CFR, using linear and more flexible schemes that reweight regrets and average strategies. These variants can improve practical convergence while retaining theoretical convergence guarantees, but parameter choices affect compatibility with pruning.
Motivation
- Discounting gives earlier iterations less influence on regret updates and differs from discounting used to compute the average strategy.The paper treats these as separate, orthogonal design choices.Source: Regret Discounting for CFR and Its… · p. 3
Linear CFR
- LCFR weights iteration t linearly, reducing the first iteration’s regret weight after T iterations relative to CFR and CFR+.The paper uses an equivalent multiplicative implementation to reduce numerical-instability risk.Source: Regret Discounting for CFR and Its… · p. 3
- LCFR selects the better action after 970 iterations in the motivating example, whereas CFR+ requires 471,407 iterations.Its theoretical regret-convergence bound is only larger than vanilla CFR by a factor of 2.Source: Regret Discounting for CFR and Its… · p. 3
Discounted CFR
- DCFR independently discounts positive regrets, negative regrets, and average-strategy contributions using parameters α, β, and γ.LCFR corresponds to DCFR1,1,1, while CFR+ corresponds to DCFR∞,−∞,2.Source: Regret Discounting for CFR and Its… · pp. 3–4
- The parameter setting α = 3/2, β = 0, and γ = 2 consistently outperformed CFR+ in preliminary experiments, despite game-dependent optimal parameters.Theorem 2 states that DCFR’s convergence bound differs from CFR only by a constant factor.Source: Regret Discounting for CFR and Its… · p. 4
Pruning compatibility
- Setting β ≤ 0 prevents suboptimal actions’ regrets from approaching −∞, making DCFR less compatible with pruning negative-regret actions.Setting β > 0 better facilitates pruning, which can reduce computational and space requirements by more than an order of magnitude in some games.Source: Regret Discounting for CFR and Its… · p. 4
Experimental setup
Experiments evaluate regret-discounting variants on HUNL poker subgames and a five-card Goofspiel variant. The setup uses realistic poker subgames with differing mistake penalties alongside a smaller imperfect-information benchmark.
HUNL poker
- The experiments use HUNL poker subgames, a primary benchmark for imperfect-information game solving.HUNL has two players, four betting rounds, and fold, call, or raise actions on each round.Source: Description of heads-up no-limit Texas… · p. 4
- The HUNL subgames are generated from real-time-solving settings and use a small number of available bet sizes.The full HUNL game tree is too large to traverse completely without sampling.Source: Description of heads-up no-limit Texas… · p. 4
- Subgame 1 starts on the third betting round and is hardest for AIs because its remaining tree is largest.Its $500 pot can expose players to losses up to $20,000, creating high-penalty mistake actions.Source: Description of heads-up no-limit Texas… · p. 4
Goofspiel
- The additional benchmark is a five-card Goofspiel variant with hidden cards ranked A through 5 and a fixed reveal order.Players’ payoffs equal the difference between their prize-card totals and their opponents’ totals.Source: Description of Goofspiel · pp. 4–5
Weighted Averaging
The experiments compare weighted-averaging variants using exploitability on HUNL subgames and Goofspiel. DCFR3/2,0,2 generally matches or outperforms CFR+, while LCFR’s gains depend on games containing severe mistakes.
Evaluation
- The experiments run for 32,768 iterations on HUNL subgames and 8,192 iterations on Goofspiel, measuring average exploitability.The paper notes that practical termination often occurs after 100–1,000 iterations.Source: Weighted Averaging · p. 5
LCFR
- LCFR dramatically improves over CFR+ in some games but performs worse asymptotically in practice and does poorly in Goofspiel.Its strongest results occur in HUNL subgames 1 and 3, which contain more severe mistake actions.Source: Weighted Averaging · p. 5
DCFR
- DCFR3/2,0,2 matches or outperforms CFR+ across the board, usually by a factor of 2 or 3.The paper recommends DCFR3/2,0,2 generally, while noting DCFR3/2,1/2,2 may suit pruning settings.Source: Weighted Averaging · p. 5
- DCFR3/2,0,2 has essentially identical performance to CFR+ in the reported experiments.This result is stated separately from the broader across-the-board comparison.Source: Weighted Averaging · p. 5
Negative-regret handling
- Setting negative regrets to zero can match strong performance but may produce rare exploitability spikes that require many iterations to recover.The alternative DCFR3/2,−∞,2 is therefore generally not recommended despite its occasional strength.Source: Weighted Averaging · p. 5
- DCFR3/2,1/2,2 performs similarly to DCFR3/2,0,2 in HUNL but noticeably worse in Goofspiel.The paper connects the β choice to whether pruning negative-regret actions may be used.Source: Weighted Averaging · p. 5
NormalHedge for CFR Variants
The paper investigates NormalHedge as an alternative regret minimizer within CFR variants. NormalHedge can preserve CFR-compatible properties, but its computational cost and performance vary across games and discounting schemes.
Using NormalHedge
- NormalHedge replaces regret matching in selected DCFR and LCFR variants to test whether a non-standard regret minimizer improves convergence.The experiments use NormalHedge with DCFR 3/2,0,2 and LCFR.Source: NormalHedge for CFR Variants · pp. 5–6
NormalHedge properties
- NormalHedge assigns zero probability to actions with negative regret and requires no parameters, retaining properties useful for CFR and CFR+.Its operation is more expensive because it uses exponentiation and a line search.Source: NormalHedge for CFR Variants · p. 6
Results
- NormalHedge outperforms regret matching in HUNL subgames when combined with DCFR 3/2,0,2, but performs worse in other HUNL subgames.The two subgames where it performs better have the largest mistake actions.Source: NormalHedge for CFR Variants · p. 6
- NormalHedge’s advantages are concentrated in games with large mistake actions rather than appearing uniformly across the tested HUNL subgames.This pattern is reported for both NormalHedge with DCFR and the comparison across HUNL subgames.Source: NormalHedge for CFR Variants · p. 6
Computational cost
- NormalHedge iterations take five times longer in the experiments because of exponentiation and line-search operations, slowing practical convergence.It may still be preferable when memory access, rather than computation, is the bottleneck.Source: NormalHedge for CFR Variants · p. 6
Optimistic CFR Variants
The paper evaluates optimistic regret minimization in CFR by counting the latest iteration twice when computing the next strategy. Optimistic performance is mixed: it helps LCFR in some HUNL subgames but hurts it in others.
Optimistic regret matching
- Optimistic Regret Matching counts the last iteration twice when determining the strategy for the next iteration.This modification is applied through a modified cumulative regret in the regret-matching strategy calculation.Source: Optimistic CFR Variants · p. 6
Optimistic LCFR
- Optimistic LCFR outperforms LCFR in two HUNL subgames but performs worse in two others.The subgames benefiting from optimism have the largest mistake actions.Source: Optimistic CFR Variants · p. 6
Optimistic DCFR
- Optimistic DCFR 3/2,0,2 performs worse than DCFR 3/2,0,2 in all HUNL subgames tested.The paper omits those results because of this consistent underperformance.Source: Optimistic CFR Variants · p. 6
Implication
- The results suggest using Optimistic LCFR in settings where LCFR is preferable, particularly when large mistake actions are present.This recommendation follows the observed subgame pattern rather than a uniform advantage.Source: Optimistic CFR Variants · p. 6
Discounted Monte Carlo CFR
Monte Carlo CFR samples actions or chance outcomes and is widely used as a benchmark. Discounting accumulated regrets and average-strategy contributions improves vanilla MCCFR performance in HUNL, especially in the subgame with the largest mistake actions.
MCCFR
- MCCFR samples certain player actions or chance outcomes, while external-sampling MCCFR traverses all actions for the updating player.External-sampling MCCFR samples opponent and chance actions according to their probabilities and is simple and widely used.Source: Discounted Monte Carlo CFR · pp. 6–7
Discounted MCCFR
- Discounted MCCFR multiplies accumulated regrets and average-strategy contributions by n/(n+1) after each period of 10^7 nodes touched.Nodes touched is an implementation-independent and hardware-independent proxy for time.Source: Discounted Monte Carlo CFR · p. 7
Results
- Discounted MCCFR achieves superior performance in HUNL compared to vanilla MCCFR across the reported subgames.The improvement is particularly noticeable in Subgame 3, which features the largest mistake actions.Source: Discounted Monte Carlo CFR · p. 7
Variants
- Initial Discount MCCFR applies a one-time factor of 1/10 after the first period and then continues with vanilla MCCFR.The displayed results average 100 different runs.Source: Discounted Monte Carlo CFR · p. 7
Conclusions
The paper introduces CFR variants that discount prior iterations and reports stronger performance than CFR+, particularly when games contain large mistakes. DCFR 3/2,0,2 matched or outperformed CFR+ in all tested settings.
Conclusions
- Discounting prior iterations yields stronger performance than the prior state-of-the-art CFR+, particularly in settings involving large mistakes.The paper presents this as the main conclusion about its discounted CFR variants.Source: Conclusions · p. 7
- DCFR 3/2,0,2 matched or outperformed CFR+ in all settings.Source: Conclusions · p. 7
Appendix
The appendix develops regret bounds for weighted iterates and regret-like updates used by discounted CFR variants. It then applies these lemmas to derive weighted regret and convergence guarantees for DCFR variants.
Weighted iterates
- Weighted iterates replace each strategy σ_t with an identically valued iterate weighted by w_t or w_a,t.The resulting regret is defined on this weighted sequence of iterates.Source: Proof of Theorem 1 · p. 10, Proof Theorem 2 · p. 10
Regret lemmas
- For non-decreasing weights, weighted sums of bounded sequences are bounded by the final weight times the admissible range.The appendix formalizes this through the BC-plausible sequence lemma.Source: Proof Theorem 2 · p. 10
Regret-like updates
- The regret-like value Q_t(a) upper-bounds regret while preserving a lower bound on its incremental change.This supports using Q_t(a) in place of ordinary regret in regret matching.Source: Proof Theorem 2 · p. 10
DCFR guarantees
- Lemma 4 bounds DCFR weighted regret by Δ|I_i|/T and weighted average regret by 2Δ|I_i|/T.Source: Proof Theorem 2 · p. 10
Convergence theorems
- The appendix also states convergence results for DCFR 3/2,0,2 and DCFR 3/2,1/2,2 in two-player zero-sum games.The supplied theorem fragments connect these variants to weighted average strategy profiles and regret bounds.Source: Correctness of DCFR(3/2, 1/2, 2) · p. 11