Abstract
Many recent results in imperfect information games were only formulated for, or evaluated on, poker and poker-like games such as liar's dice. We argue that sequential Bayesian games constitute a natural class of games for generalizing these results. In particular, this model allows for an elegant formulation of the counterfactual regret minimization algorithm, called public-state CFR (PS-CFR), which naturally lends itself to an efficient implementation. Empirically, solving a poker subgame with 10^7 states by public-state CFR takes 3 minutes and 700 MB while a comparable version of vanilla CFR takes 5.5 hours and 20 GB. Additionally, the public-state formulation of CFR opens up the possibility for exploiting domain-specific assumptions, leading to a quadratic reduction in asymptotic complexity (and a further empirical speedup) over vanilla CFR in poker and other domains. Overall, this suggests that the ability to represent poker as a sequential Bayesian game played a key role in the success of CFR-based methods. Finally, we extend public-state CFR to general extensive-form games, arguing that this extension enjoys some - but not all - of the benefits of the version for sequential Bayesian games.
Introduction
In the field of multi-agent AI, the Extensive-Form Game (EFG) is the standard model for sequential decision-making. However, EFGs are often computationally prohibitive for large-scale applications. While algorithms like Counterfactual Regret Minimization (CFR) have enabled superhuman performance in poker, a significant gap exists between theoretical "Vanilla CFR" and the highly optimized implementations used in practice. This paper argues that these successes rely on a specific game representation—the Sequential Bayesian Game (SBG)—and an associated optimization called Public-State CFR (PS-CFR).
Sequential Bayesian Games and PS-CFR
The authors formalize two critical concepts to bridge this gap:
- Sequential Bayesian Games (SBGs): A class of games where players receive private information (their "type") at the start, and all subsequent actions and observations are public.
- Public-State CFR (PS-CFR): An implementation of CFR that groups histories sharing the same public information. Instead of iterating through every possible sequence of events, PS-CFR updates regrets for all private types simultaneously using efficient vector and matrix operations.
A key theoretical contribution is Proposition 2, which proves that PS-CFR and Vanilla CFR produce identical strategies. Thus, PS-CFR is not a different algorithm but a more efficient implementation tailored to the structural properties of SBGs.
Key Insights: The Importance of Representation
The choice of model significantly impacts computational efficiency. Just as Rock-Paper-Scissors is most naturally represented as a normal-form matrix, games like Poker and Liar's Dice are naturally SBGs. Forcing a game into the wrong representation adds unnecessary overhead.
In poker, PS-CFR exploits the fact that one does not need to calculate the probability of every specific hand an opponent might hold. Instead, knowing the probability that their hand is weaker than yours is sufficient. This domain-specific insight allows PS-CFR to reduce complexity from quadratic to linear relative to the number of possible hands, providing a massive "hidden" speedup.
Empirical Results
The researchers tested their claims on a "river" subgame of no-limit Texas hold’em, involving over 61 million histories but only 21,620 decision points (infosets). They compared Vanilla-CFR against various versions of PS-CFR.
The results were dramatic:
- Speed: An optimized, domain-specific PS-CFR completed 1,000 iterations in just 1.42 minutes, whereas Vanilla-CFR required 5.48 hours—a roughly 200x speedup.
- Memory: Vanilla-CFR consumed 22 GB of RAM, while the optimized PS-CFR used only 526 MB.
- Efficiency: PS-CFR reached target exploitability levels with 100x fewer value updates than the vanilla version.
Discussion and Limitations
The paper suggests that the AI literature's focus on poker and similar games has created a skewed perception of CFR's general efficiency. The massive speedups observed are contingent on abundant public information. In games where private actions remain hidden for long periods (e.g., "blind chess"), PS-CFR offers little advantage, and the computational cost of CFR remains high.
Future work should explore games with scarce public information to develop more universally applicable algorithms. Additionally, the relationship between PS-CFR and "sequence-form" strategy approaches remains an open question for further investigation.
Summary updated