Research map / Bandits and online learning / Online convex optimization and games
Extensive-Form Game Solving via Blackwell Approachability on Treeplexes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Blackwell approachability-based regret minimizers over treeplexes (sequence-form polytopes) via cone reformulation, yielding stepsize-invariant PTBP, O(1/T) SmoothPTBP, and AdaTBP for solving two-player zero-sum EFGs.
Problem
Solving two-player zero-sum extensive-form games via regret minimization over treeplexes; existing CFR+ variants are stepsize invariant but first-order methods with O(1/T) rates depend on stepsizes, and no Blackwell-approachability method operates on the full treeplex with state-of-the-art rates.
Approach
Run any regret minimizer over the conic hull cone(T) against losses f(x,l)=l - <x,l>a, with x_t = R_t/<R_t,a>, giving a regret minimizer over the treeplex with hyperplane forcing; instantiate with predictive OMD (PTBP, treeplex stepsize invariant), a stable variant restricted to C_>= (SmoothPTBP, O(1/T)), and AdaGrad/Adam (AdaTBP).
Key results
- SmoothPTBP achieves O(1/T) convergence to Nash equilibrium in self-play, the first Blackwell-approachability EFG solver with the state-of-the-art rate.
- PTBP is treeplex stepsize invariant with O(1/sqrt(T)) rate, but in experiments it often converges slower than CFR+ and predictive CFR+ (PCFR+ outperforms all others on average iterates).
- Projection onto cone(T) computable in O(d n log(l+m)) operations, making the framework practical.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Predictive Treeplex Blackwell+ (PTBP) instead of Smooth PTBP or AdaTBP | Treeplex Blackwell framework · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | convergence to Nash equilibrium | Helped |
| use Predictive CFR+ (PCFR+) instead of PTBP | EFG solving with average iterates · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | average-iterate convergence to Nash equilibrium | Helped |
| use Predictive CFR+ instead of CFR+ or single-call predictive OMD | EFG solving with average iterates · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | average-iterate convergence to Nash equilibrium | Helped |
| use PTBP instead of CFR+ and PCFR+ | EFG solving · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | convergence to Nash equilibrium | Hurt |
| use Smooth PTBP instead of PTBP (ablation) | Treeplex Blackwell framework · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | convergence to Nash equilibrium | Hurt |
| use AdaTBP instead of PTBP (ablation) | Treeplex Blackwell framework · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | convergence to Nash equilibrium | Hurt |
| use AdamTBP instead of PTBP (ablation) | Treeplex Blackwell framework · some benchmark games | convergence to Nash equilibrium | Hurt |
| remove predictions from PTBP (use Treeplex Blackwell+) (ablation) | PTBP · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | convergence to Nash equilibrium | Mixed |
| use PCFR+ instead of PTBP | EFG solving with last iterates · Kuhn poker, Leduc poker, Liar's Dice, Goofspiel, Battleship | last-iterate convergence to Nash equilibrium | Mixed |
Surprising findings
- PTBP, despite treeplex stepsize invariance, often converges slower than CFR+ and predictive CFR+, ruling out stepsize invariance as the sole explanation for CFR+ performance.
- Predictive CFR+ outperforms the theoretically faster SCPOMD (O(1/T)) in average-iterate performance.
Limitations
- PTBP has only O(1/sqrt(T)) guarantee and empirically lags CFR+ variants.
- Last-iterate convergence is not established; no algorithm consistently wins on last iterates.
- Adam-based variant (AdaTBP with Adam) diverges on some games and lacks regret guarantees.
Experimental setup
Datasets: Kuhn poker Leduc poker Liar's Dice Goofspiel Battleship
Benchmarks: Kuhn poker Leduc poker Liar's Dice Goofspiel Battleship
Metrics: exploitability (average iterate) exploitability (last iterate)
Baselines: CFR+ Predictive CFR+ predictive OMD Excessive Gap Technique Mirror Prox Optimistic OMD with single projection
Builds on: Blackwell approachability Regret Matching+ CFR predictive OMD AdaGrad
Closest papers by meaning
- Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent (AAAI 2021 · similarity 0.94)
- Efficient Learning in Polyhedral Games via Best-Response Oracles (AAAI 2024 · similarity 0.90)
- Thresholds for sensitive optimality and Blackwell optimality in stochastic games (NeurIPS 2025 · similarity 0.88)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.88)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.