# Extensive-Form Game Solving via Blackwell Approachability on Treeplexes

arXiv: https://arxiv.org/abs/2403.04680 · HTML: https://mlsanity.com/paper/2403.04680/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2024.

## Built on by (most cited first, 6 of 6)

- [Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games](https://mlsanity.com/paper/2510.04407/) (2025)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Scale-Invariant Fast Convergence in Games](https://mlsanity.com/paper/2602.11857/) (2026)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)
- [Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information](https://mlsanity.com/paper/2607.09993/) (2026)
- [IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence](https://mlsanity.com/paper/2610.19016/) (2026)

## Abstract (arXiv)

In this paper, we introduce the first algorithmic framework for Blackwell approachability on the sequence-form polytope, the class of convex polytopes capturing the strategies of players in extensive-form games (EFGs). This leads to a new class of regret-minimization algorithms that are stepsize-invariant, in the same sense as the Regret Matching and Regret Matching^+ algorithms for the simplex. Our modular framework can be combined with any existing regret minimizer over cones to compute a Nash equilibrium in two-player zero-sum EFGs with perfect recall, through the self-play framework. Leveraging predictive online mirror descent, we introduce Predictive Treeplex Blackwell^+ (PTB^+), and show a O(1/√T) convergence rate to Nash equilibrium in self-play. We then show how to stabilize PTB^+ with a stepsize, resulting in an algorithm with a state-of-the-art O(1/T) convergence rate. We provide an extensive set of experiments to compare our framework with several algorithmic benchmarks, including CFR^+ and its predictive variant, and we highlight interesting connections between practical performance and the stepsize-dependence or stepsize-invariance properties of classical algorithms.