Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms

Vojtěch Kovařík, David Milec, Michal Šustr, Dominik Seitz, Viliam Lisý

Abstract

Recent advancements in algorithms for sequential decision-making under imperfect information have shown remarkable success in large games such as limit- and no-limit poker. These algorithms traditionally formalize the games using the extensive-form game formalism, which, while theoretically sound, is memory-inefficient and computationally intensive in practice. To mitigate these challenges, a popular workaround involves using a specialized representation based on player-specific information-state trees. However, this alternative significantly narrows the set of games that can be represented efficiently. In this study, we identify the set of large games on which modern algorithms have been benchmarked as being naturally represented by Sequential Bayesian Games. We elucidate the critical differences between extensive-form game and sequential Bayesian game representations, both theoretically and empirically. We further argue that the impressive experimental results often cited in the literature may be skewed, as they frequently stem from testing these algorithms only on this restricted class of games. By understanding these nuances, we aim to guide future research in developing more universally applicable and efficient algorithms for sequential decision-making under imperfect information.

The Representation Gap

In multi-agent reinforcement learning, the Extensive-Form Game (EFG) is the standard mathematical language for sequential games with imperfect information. However, the EFG formalism is notoriously memory-hungry because it treats every possible sequence of events (histories) as a distinct node in a massive tree.

Researchers often use "natural" models to factorize game states, but these optimizations are frequently "baked in" to implementations without formal description. This creates a gap: it is unclear if the success of algorithms like Counterfactual Regret Minimization (CFR) in poker is due to the core algorithm or the specific structural shortcuts poker allows.

Comparison of Normal-Form (left) and Extensive-Form (right) representations for Rock-Paper-Scissors.

As shown in the figure above, even a simple game like Rock-Paper-Scissors can be represented as a compact matrix (Normal-Form) or a more complex tree (Extensive-Form). Choosing the "wrong" representation can make a game appear much harder to solve than it actually is.

Formalizing Efficiency: PS-CFR and SBGs

The authors introduce two key concepts to explain current algorithmic efficiency:

  1. Public-State CFR (PS-CFR): Instead of traversing the game tree history-by-history (Vanilla-CFR), PS-CFR traverses at the level of public states. If multiple private scenarios lead to the same public information (e.g., cards on the table), PS-CFR processes them simultaneously using vector operations.
  2. Sequential Bayesian Games (SBGs): This class of games restricts private information (the player's "type") to the start of the game, with all subsequent actions being public. Poker and Liar’s Dice are naturally SBGs.

Using the Factored-Observation Stochastic Game (FOSG) framework, the authors prove that while PS-CFR produces the same mathematical output as Vanilla-CFR, it does so with significantly lower asymptotic complexity.

Empirical Validation: The Poker Benchmark

The authors evaluated these claims on a river subgame of no-limit Texas hold’em, consisting of ~61 million histories and 21,620 decision points. The results demonstrate a massive efficiency gap:

Metric Vanilla-CFR PS-CFR (optimized)
Time for 1,000 iterations ~5.5 hours ~1.4 minutes
Memory Usage 22 GB 526 MB
Speedup 1x ~200x

Even a memory-efficient version of Vanilla-CFR took over 25 hours to complete the same task, highlighting that the speedup of PS-CFR is fundamental, not just a matter of better coding.

The Benchmark Bias

The study suggests that landmark papers may give a skewed impression of algorithmic generalizability. Because most benchmarks use poker-like games (SBGs), researchers may believe CFR is ready for general use when it might actually struggle in "information-scarce" domains like blind chess, where public observations are rare.

Future research should focus on developing algorithms that can exploit properties in these information-scarce domains and move beyond poker to ensure sequential decision-making algorithms are truly universal.

Summary updated

Abstract

Recent advancements in algorithms for sequential decision-making under imperfect information have shown remarkable success in large games such as limit- and no-limit poker. These algorithms traditionally formalize the games using the extensive-form game formalism, which, as we show, while theoretically sound, is memory-inefficient and computationally intensive in practice. To mitigate these challenges, a popular workaround involves using a specialized representation based on player specific information-state trees. However, as we show, this alternative significantly narrows the set of games that can be represented efficiently. In this study, we identify the set of large games on which modern algorithms have been benchmarked as being naturally represented by Sequential Bayesian Games. We elucidate the critical differences between extensive-form game and sequential Bayesian game representations, both theoretically and empirically. We further argue that the impressive experimental results often cited in the literature may be skewed, as they frequently stem from testing these algorithms only on this restricted class of games. By understanding these nuances, we aim to guide future research in developing more universally applicable and efficient algorithms for sequential decision-making under imperfect information.
BibTeX
@misc{kovarik2021revisiting,
  author = {Vojtěch Kovařík and David Milec and Michal Šustr and Dominik Seitz and Viliam Lisý},
  title = {{Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms}},
  year = {2021},
  eprint = {2112.10890},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.10890},
}
Figure