Introduction
In the field of multiagent artificial intelligence, researchers typically rely on two distinct formalisms to describe decision-making problems: Extensive-Form Games (EFGs) from game theory and Partially Observable Stochastic Games (POSGs) from reinforcement learning. While both models are capable of representing imperfect-information environments like Poker or autonomous driving, a significant conceptual gap exists between them.
Standard EFGs group indistinguishable states into "information sets," but they often discard the underlying structure of how information is received. Specifically, they lose track of whether an observation was private (e.g., a player's hidden cards) or public (e.g., community cards on the table). This lack of explicit "publicness" complicates the implementation of modern "superhuman" AI algorithms, such as DeepStack or Libratus, which rely on subgame decomposition to break massive games into manageable parts. Currently, researchers must often resort to domain-specific hacks to re-introduce this missing structure.
The FOSG Formalism
To address this disconnect, we introduce Factored-Observation Stochastic Games (FOSGs). This model serves as a bridge between the compact representations used in RL and the computation-friendly trees used in game theory. The core innovation lies in a modified observation function that explicitly factors information into two components:
- Private observations: Information unique to a specific agent.
- Public observations: Information guaranteed to be seen by all agents simultaneously.
By making this distinction a first-class citizen of the formal model, FOSGs allow for a cleaner, more general implementation of search and decomposition algorithms. As shown in the figure above, a FOSG can be "unrolled" into an augmented EFG that preserves public information, whereas historical EFG definitions are "lossy" because they forget non-acting and public information.
The Public Tree and Subgame Decomposition
A primary advantage of the FOSG framework is the natural construction of a public tree. This structure groups sequences of public observations, providing a mathematically rigorous way to define where a subgame begins and ends. This is the fundamental requirement for efficient subgame solving.
Using Kuhn Poker—a simplified three-card poker game—as an illustrative example, we can see how FOSGs represent different perspectives. The model allows us to distinguish between the full game tree, a specific player's private view, and the public tree used for decomposition.
Theoretical Results
We provide several theoretical proofs to validate the utility of the FOSG model:
- Equivalence: We prove that FOSGs and POSGs are essentially equivalent; any result for one can be applied to the other by either "forgetting" or "adding" the factorization of information.
- Completeness: We demonstrate that every "well-behaved" (timeable and perfect-recall) EFG has a corresponding FOSG representation.
- Algorithmic Portability: We show that the three pillars of modern EFG research—Counterfactual Regret Minimization (CFR), Sequence Form, and Decomposition—can be elegantly reformulated within the FOSG framework without game-specific modifications.
Conclusion and Future Work
FOSGs resolve the formalization issues that have previously required ad-hoc solutions in multiagent AI research. While this work focuses on "well-behaved" games with perfect recall, it lays the groundwork for a unified algorithmic framework. Future research will extend these concepts to environments with continuous action spaces and scenarios where the "public" nature of information is less certain, moving toward general-purpose solvers for any multiagent environment.
Summary updated