Source-linked AI summary
Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent
Gabriele Farina, Christian Kroer, Tuomas Sandholm
TL;DR
The paper studies how practical regret-matching algorithms relate to FTRL and OMD, widely used methods in online optimization. It derives these connections through Blackwell approachability, develops predictive variants, and reports faster convergence on many benchmark games, with most poker games as an exception.
Problem
FTRL and OMD are prominent online-optimization regret minimizers, while RM and RM+ are preferred in practice for large-scale game solving; their relationship is a subject of study.
Source: §1 · p. 1Method
Results
PCFR+ often converges much faster than CFR+ and prior CFR variants, sometimes by several orders of magnitude, while DCFR is fastest on most poker games.
Source: §1 · p. 2Takeaways & Limitations
The results highlight the need to evaluate extensive-form game algorithms beyond poker, since non-poker benchmarks reverse prior algorithm rankings observed on poker.
Source: §1 · p. 2The authors did not investigate how their predictive perspective applies to Gordon's partially overlapping Lagrangian Hedging construction.
Source: §4 · p. 4
Abstract
from arXiv · showhide
Blackwell approachability is a framework for reasoning about repeated games with vector-valued payoffs. We introduce predictive Blackwell approachability, where an estimate of the next payoff vector is given, and the decision maker tries to achieve better performance based on the accuracy of that estimator. In order to derive algorithms that achieve predictive Blackwell approachability, we start by showing a powerful connection between four well-known algorithms. Follow-the-regularized-leader (FTRL) and online mirror descent (OMD) are the most prevalent regret minimizers in online convex optimization. In spite of this prevalence, the regret matching (RM) and regret matching+ (RM+) algorithms have been preferred in the practice of solving large-scale games (as the local regret minimizers within the counterfactual regret minimization framework). We show that RM and RM+ are the algorithms that result from running FTRL and OMD, respectively, to select the halfspace to force at all times in the underlying Blackwell approachability game. By applying the predictive variants of FTRL or OMD to this connection, we obtain predictive Blackwell approachability algorithms, as well as predictive variants of RM and RM+. In experiments across 18 common zero-sum extensive-form benchmark games, we show that predictive RM+ coupled with counterfactual regret minimization converges vastly faster than the fastest prior algorithms (CFR+, DCFR, LCFR) across all games but two of the poker games, sometimes by two or more orders of magnitude.
1 Introduction
The introduction connects practical regret-matching methods for solving extensive-form games to FTRL and OMD through Blackwell approachability. It then uses predictive variants to develop PRM+ and reports faster convergence on many benchmarks, with poker exceptions.
1 Introduction
- RM and RM+ arise from using FTRL and OMD, respectively, to select the halfspaces forced in Blackwell approachability, for any constant step size.This connects two widely used regret minimizers in extensive-form game solving to prominent online-optimization methods.Source: §1 · p. 2
- RM+ began as a heuristic to avoid accumulating large negative regrets, while FTRL and OMD were developed separately.The paper also notes that RM+ is numerically much faster than RM in this setting, reversing a relationship reported for direct strategy-space applications of FTRL and OMD.Source: §1 · p. 2
- FTRL and OMD require step sizes tied to gradient magnitude, but their induced RM and RM+ halfspace choices are unchanged by any step-size choice.The paper presents parameter-free regret matching as compatible with the step-size parameters of its online-optimization derivation.Source: §1 · p. 2
- Predictive OMD yields predictive regret matching+ (PRM+), whose regret depends on the accuracy of predicted regret vectors; simply counting RM+'s last regret vector twice is only a heuristic.The authors combine PRM+ with counterfactual regret minimization and use alternation and quadratic averaging.Source: §1 · p. 2
- PCFR+ often converges much faster than CFR+ and other prior CFR variants, sometimes by several orders of magnitude, while DCFR is fastest on most poker games.The authors report a new state-of-the-art convergence rate for the remaining games and note that non-poker results reverse prior algorithm rankings observed on poker.Source: §1 · p. 2
2 Online Linear Optimization, Regret Minimizers, and Predictions
The section defines online linear optimization regret minimization, introduces predictions of the next loss, and describes predictive FTRL and OMD. Their regret guarantees extend to closed, unbounded domains.
2 Online Linear Optimization, Regret Minimizers, and Predictions
- An online linear optimization oracle chooses strategies from past decisions and observed losses, then receives the loss vector evaluating its latest strategy.Regret compares cumulative loss with always using a fixed strategy; the paper allows convex, closed, unbounded decision domains.Source: §2 · p. 2
Incorporating Predictions
- Predictive oracles receive an estimate of the next loss and can achieve better regret when predictions are accurate.The section gives an example bound proportional to one plus the sum of squared prediction errors, which stays constant for clairvoyant predictions.Source: Incorporating Predictions · p. 2
FTRL, OMD, and their Predictive Variants
- Predictive FTRL and OMD use a 1-strongly convex regularizer on a convex, closed domain; setting predictions to zero recovers their non-predictive versions.With an appropriate step size such as η = T^-1/2, both guarantee regret O(T^1/2) for all strategies in the domain.Source: FTRL, OMD, and their Predictive Variants · p. 3
3 Blackwell Approachability
Blackwell approachability concerns repeated games with vector-valued payoffs and the goal of bringing average payoffs toward a closed convex target. The paper uses this framework to connect regret minimizers and introduce predictive algorithms.
3 Blackwell Approachability
- In a Blackwell approachability game, players choose actions in sequence and the first player seeks to make average vector payoffs converge to a closed convex target set.The payoff function is biaffine, and both players' action sets are compact and convex.Source: §3 · p. 3
- A halfspace containing the target set is forceable when the first player has an action guaranteeing the payoff lies in that halfspace against every opponent action.Blackwell's theorem states that approachability is attainable if and only if all halfspaces containing the target are forceable.Source: §3 · p. 3
- The paper uses Blackwell approachability to connect FTRL with RM and OMD with RM+, and introduces predictive approachability for developing algorithms for simplex domains and extensive-form games.The games named in the contribution include imperfect-information, zero-sum extensive-form games.Source: §3 · p. 3
4 From Online Linear Optimization to Blackwell Approachability
The section converts an online linear optimization oracle into a Blackwell approachability algorithm by using its decisions to choose forceable halfspaces. The construction extends earlier work by allowing greater flexibility in the oracle's domain.
4 From Online Linear Optimization to Blackwell Approachability
- The authors extend the earlier reduction by allowing more flexibility in the regret minimizer's domain, which is needed to derive RM and RM+ from FTRL and OMD.The earlier construction is recovered when the domain is set to K; deriving RM+ requires setting it to C◦ rather than K.Source: §4 · p. 4
- Algorithm 3 uses the latest online-optimization decision as a halfspace normal, plays a forcing action for that halfspace, and then gives the oracle the negative payoff as its loss.For a cone target C, the oracle's domain may be any closed convex D with C◦∩B_2^n ⊆ D ⊆ C◦.Source: §4 · p. 4
- The predictive perspective was not investigated for Gordon's partially overlapping Lagrangian Hedging construction.The proposition is stated for conic target sets; the authors note that non-conic games can be transformed to conic ones.Source: §4 · p. 4
5 Connecting FTRL, OMD with RM, RM+
The paper formulates simplex regret minimization as a Blackwell approachability game, then shows that choosing the forced halfspace with FTRL or OMD recovers RM or RM+, respectively.
5 Connecting FTRL, OMD with RM, RM+
- The approachability construction chooses a regret minimizer’s decision as the normal vector of a halfspace containing the target cone.For the simplex regret game, the halfspace is forceable using an action derived from that normal vector.Source: §5 · p. 4
- A strategy for the Blackwell game Γ is a regret minimizer over the simplex domain ∆n.The game’s payoff components measure changes in regret relative to always playing each simplex vertex.Source: §5 · pp. 4–5
- FTRL over the nonnegative orthant, used to choose the halfspace to force, produces the same iterates as RM.The equivalence holds for every η > 0 in the stated setup.Source: §5 · p. 5
- OMD over the same domain and approachability game produces the same iterates as RM+.This equivalence also holds for every η > 0 in the stated setup.Source: §5 · p. 5
- The paper relates the RM and RM+ updates to the corresponding FTRL and OMD steps through their halfspace-selection computations.The PRM and PRM+ pseudocode’s intermediate computations align with the minimization, forcing-action, and update steps in the approachability procedure.Source: §5 · p. 5
6 Predictive Blackwell Approachability, and Predictive RM and RM+
The paper extends Blackwell approachability to settings with predictions of future payoffs, using predictive FTRL and OMD to derive predictive regret matching algorithms. The resulting PRM and PRM+ retain regret-minimization guarantees.
6 Predictive Blackwell Approachability, and Predictive RM and RM+
- Predictions of the next payoff vector can be propagated as predictions of the regret minimizer’s next loss in the approachability procedure.The paper states that the approachability guarantee then continues to hold.Source: §6 · p. 5
- Predictive FTRL and predictive OMD in the Blackwell framework yield predictive regret matching (PRM) and predictive regret matching+ (PRM+), respectively.The paper defines the predictive regret minimizers for the simplex domain through this construction.Source: §6 · pp. 5–6
- PRM and PRM+ produce the same iterates as their corresponding predictive FTRL and OMD procedures in the stated setup.The theorem also states regret-minimizer guarantees for both algorithms over the simplex domain.Source: §6 · p. 6
- The paper derives the PRM and PRM+ regret bound by combining the approachability reduction with predictive FTRL and OMD guarantees.The derivation uses the fact that the algorithms’ iterates do not depend on the chosen step size η > 0.Source: §6 · p. 6
7 Experiments
Across the benchmark games, PCFR+ is markedly faster on non-poker games, while DCFR is fastest on poker games. The experiments pair local PRM+ updates with alternating updates and quadratic averaging.
7 Experiments
- The experiments use PRM+ at each CFR decision point, quadratic strategy averaging, and alternating updates to form PCFR+.The comparisons include CFR+, DCFR with recommended parameters, and LCFR.Source: §7 · p. 6
- On Battleship and Pursuit-evasion, PCFR+ is 3–6 orders of magnitude faster after 500 iterations and around 10 orders faster after 2000 iterations.On Goofspiel, the reported speedup is 0.5–1 order of magnitude.Source: §7 · p. 6
- Liar’s Dice is an exception among non-poker games, where PCFR+ performs comparably to DCFR.The appendix reports that quadratic averaging makes CFR+ comparable to DCFR and PCFR+ on Liar’s Dice.Source: §7 · p. 6
- Figure 2 plots Nash gap and average prediction error against iterations, with both y-axes on a log scale.The main text reports seven games, with another eleven in the appendix.Source: §7 · p. 6, Figure 2 · p. 7
- PCFR+ is much faster than CFR+ and DCFR on non-poker games, while DCFR is fastest on poker games.The River endgame is slightly faster than CFR+ but slower than DCFR; on Leduc poker, PCFR+ gives a small speedup over CFR+ while DCFR remains fastest.Source: §7 · pp. 6–7, Figure 2 · p. 7
- PCFR+’s convergence tracks prediction accuracy: prediction errors are reported around 10^-5 on Goofspiel and 10^-3 on the River endgame.The paper reports rapid accuracy gains on Battleship and Pursuit-evasion alongside very fast convergence there.Source: §7 · p. 7
8 Conclusions and Future Research
The paper concludes that its extended approachability reduction connects FTRL and OMD to RM and RM+, and uses predictive variants to construct PCFR+. It identifies prediction guarantees for matrix games and combinations with DCFR as future directions.
8 Conclusions and Future Research
- Extending the approachability-to-regret reduction beyond compact settings supports the equivalences between FTRL and RM, and OMD and RM+.Predictive variants then yield PRM and PRM+, with PCFR+ formed by combining PRM+ with CFR.Source: §8 · p. 7
- The reported PCFR+ experiments show orders-of-magnitude gains over prior state-of-the-art algorithms on non-poker benchmark games.The conclusion limits this reported performance claim to the non-poker games tested.Source: §8 · p. 7
- The paper asks whether PRM+ can guarantee T^-1 convergence on matrix games and whether predictive DCFR or a DCFR–PCFR+ combination can improve performance.The proposed combination could be best of both worlds if its crossover point could be approximated.Source: §8 · p. 7
Additional Bibliographic Remarks
The remarks note an overlap with Gordon’s framework and flag uncertainty about whether Burch’s “optimistic RM+” is the same algorithm as PRM+.
Additional Bibliographic Remarks
- Abernethy, Bartlett, and Hazan’s construction partially overlaps Gordon’s Lagrangian Hedging framework [Gordon 2005, 2007], but the paper does not investigate whether its predictive perspective applies to Gordon’s result.The authors also say Abernethy et al. appeared unaware of Gordon’s results.Source: Additional Bibliographic Remarks · p. 10
- Burch’s “optimistic RM+” is not formally defined, so its identity with PRM+ remains unclear; Brown, Kroer, and Sandholm’s interpretation would make it different.The authors say they intended to check with Burch for the final version.Source: Additional Bibliographic Remarks · p. 10
A Analysis of (Predictive) FTRL
This appendix establishes a regret bound for predictive FTRL and supplies the technical steps used in its proof. It also states a Lipschitz property of the regularized minimizer map.
A Analysis of (Predictive) FTRL
- The map ψ associated with the regularized minimizer is η-Lipschitz continuous with respect to the dual norm.Lemma 2 gives this property under a 1-strongly convex differentiable regularizer.Source: A Analysis of (Predictive) FTRL · p. 10
- Proposition 4 bounds predictive FTRL’s regret against any fixed strategy in the domain for all times T and step sizes η > 0.The bound assumes a 1-strongly convex regularizer and uses the dual norm.Source: A Analysis of (Predictive) FTRL · p. 10
- The proof represents predictive FTRL’s decision as ψ(Lt−1 + mt), introduces wt = ψ(Lt), and bounds the resulting terms using optimality and telescoping sums.The argument also invokes the parallelogram inequality and generalized Cauchy–Schwarz.Source: A Analysis of (Predictive) FTRL · pp. 10–11
B Analysis of (Predictive) OMD
The appendix gives regret guarantees for predictive OMD and derives an approachability guarantee from an online linear optimization regret bound. The OMD proof uses technical lemmas and telescoping divergence terms.
B Analysis of (Predictive) OMD
- The OMD proof uses lemmas to bound its terms, then telescopes divergence differences and applies the triangle inequality.The proof also uses strong convexity and nonnegativity of divergences.Source: B Analysis of (Predictive) OMD · pp. 12–13
- Proposition 5 bounds predictive OMD’s regret against any fixed strategy for all times T and step sizes η > 0.When ∇ϕ(z0) = 0, the proposition yields the stated corollary.Source: B Analysis of (Predictive) OMD · pp. 12–13
C Online Linear Optimization to Approachability
- Proposition 2 bounds the distance of Algorithm 3’s average payoff from the target cone using the regret of its online linear optimization oracle.The oracle regret is measured against a fixed comparator in K.Source: C Online Linear Optimization to… · p. 14
D Connections between FTRL, OMD and RM, RM+
The section connects Blackwell approachability and regret minimization, relating FTRL and OMD to RM and RM+ and describing predictive variants and their use in extensive-form game solving. It also presents River Endgame and Liar’s Dice benchmark instances, including their structures and rules.
D Connections between FTRL, OMD and RM, RM+
- In Γ, FTRL produces RM and OMD produces RM+ for every step size η > 0.Both equivalences use the nonnegative orthant as the domain; positive rescaling leaves the forcing action unchanged.Source: D Connections between FTRL, OMD and… · p. 15
E Predictive Blackwell Approachability and Predictive RM, RM+
- Predictive FTRL and OMD in Γ produce PRM and PRM+, respectively, and both are regret minimizers on the simplex.The theorem states that these algorithms satisfy a regret bound, but the supplied passage does not include its formula.Source: E Predictive Blackwell Approachability… · p. 16
F Extensive-Form Games and Counterfactual Regret Minimization
- An extensive-form game is a sequential decision process, and its Nash equilibrium can be expressed as a bilinear saddle-point problem solved by regret minimizers for both players.A player's sequence-form strategy records the product of action probabilities along paths through the decision tree.Source: F Extensive-Form Games and… · p. 18
Counterfactual Regret Minimization
- CFR combines independent local regret minimizers at each decision point; if each guarantees O(T^1/2) regret, overall regret is O(T^1/2).Each local minimizer receives a loss vector constructed from the loss relative to the player's full sequence-form strategy space.Source: Counterfactual Regret Minimization · p. 18
Counterfactual Loss Predictions
- Counterfactual loss predictions for a decision point use decisions made at time t in its subtrees; experiments set the generic prediction to the previous loss, ℓt−1.Thus, the local prediction uses future subtree decisions relative to the decision point's own choice.Source: Counterfactual Loss Predictions · p. 19
G Description of the Game Instances
- The benchmark descriptions cover Kuhn and Leduc poker as standard EFG-solving benchmarks, popular Goofspiel and its limited-information variant, security-inspired pursuit-evasion, and Battleship, a parametric version of a classic board game.Source: G Description of the Game Instances · pp. 19–20
- The benchmark instances vary game parameters, including card counts in poker, deck sizes in Goofspiel, and move limits in pursuit-evasion.The supplied passages specify Kuhn poker with R = 3 and R = 13, and pursuit-evasion with m = 4, 5, or 6.Source: G Description of the Game Instances · pp. 19–20
- The River Endgame uses a five-card board, conditional hand distributions, pot sizes, and betting abstractions with specified fold, check, bet, call, and raise options.It is subgame 4 from the open-sourced Libratus endgames.Source: G Description of the Game Instances · p. 20
- In Liar’s dice, two players privately roll unbiased six-face dice and take turns making higher bids or challenging the previous bid.A bid is higher if its face value or number of dice is higher.Source: G Description of the Game Instances · p. 20
- A Liar’s dice challenge reveals all dice; the challenger wins +1 if the bid was invalid, while the last bidder wins +1 if it was valid.The losing player receives −1.Source: G Description of the Game Instances · pp. 20–21
H Additional Experimental Results
Additional experiments show PCFR+’s strong performance across most games, examine whether averaging choices explain its speedup, and test predictive variants of discounted CFR. The results also show that game structure does not yet provide a clear rule for when prediction helps.
H Additional Experimental Results
- PCFR+ significantly outperforms the other algorithms by 2–8 orders of magnitude in all games except Leduc 13, where DCFR is faster than PCFR+.CFR+ is equivalent or slightly superior to DCFR except in Leduc 13, where it performs slightly better than CFR+.Source: H Additional Experimental Results · p. 21
- In the Small matrix game, CFR+, LCFR, and DCFR perform similarly and converge slower than T^-1, unlike PCFR+.The authors identify Small matrix as a hard instance for non-predictive methods but not for predictive methods, as previously observed by Farina, Kroer, and Sandholm (2019b).Source: H Additional Experimental Results · p. 21
- Prediction error decreases quickly to extremely small values in all tested game instances, but the authors leave stability guarantees for PCFR+ as future work.The observed errors suggest PCFR+ might enjoy guarantees similar to predictive FTRL and OMD, but this remains a research direction.Source: H Additional Experimental Results · p. 21
- Game size and the amount of private information alone do not reliably distinguish games where predictivity helps from those where it does not.Liar’s Dice and the river endgame have many terminal states relative to decision points, yet predictivity helps substantially in a pursuit-evasion game with an even larger ratio; the authors conjecture that how private information arises may matter, leaving formalization open.Source: H Additional Experimental Results · p. 22
Comparison between Linear and Quadratic Averaging in PCFR+ and CFR+
- PCFR+ with linear averaging beats CFR+ with either averaging in 11 games and loses to both in two; its speedup is attributed mostly to loss predictions.The two losses are the no-limit Texas hold’em river endgame and Leduc poker; PCFR+ with linear averaging performs similarly or slightly better than quadratic averaging in two games.Source: Comparison between Linear and… · pp. 22–23
Predictive Discounted CFR and Quadratic-Average Loss Prediction
- The experiments compare predictive DCFR with and without quadratic-average loss prediction against PCFR+ variants, CFR+, and DCFR.Quadratic-average loss prediction uses the quadratic average of past loss vectors to predict the next loss; the tested discounted-regret variant lacks a proof that it is predictive in the paper’s formal sense.Source: Predictive Discounted CFR and… · p. 25