Extensive-Form Game Solving via Blackwell Approachability on Treeplexes
<|reference_start|>Extensive-Form Game Solving via Blackwell Approachability on Treeplexes: 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/\sqrt{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.<|reference_end|>
@article{chakrabarti2024extensive-form,
    title={Extensive-Form Game Solving via Blackwell Approachability on Treeplexes},
    author={Darshan Chakrabarti, Julien Grand-Cl'ement, Christian Kroer},
    journal={arXiv preprint arXiv:2403.04680},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04680},
    primaryClass={cs.GT}
}