Rethinking Formal Models of Partially Observable Multiagent Decision Making (Extended Abstract)

Vojtech Kovarík, Martin Schmid, Neil Burch, Michael Bowling, Viliam Lisý

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:

  1. Private observations: Information unique to a specific agent.
  2. Public observations: Information guaranteed to be seen by all agents simultaneously.
The relationship between FOSGs, POSGs, and EFGs. FOSGs act as a bridge, where EFGs can be seen as "unrolled" versions of the underlying stochastic game.

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.

Different perspectives of Kuhn Poker enabled by FOSGs: the public tree used for decomposition (left) and the full EFG with factored information (right).

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

Abstract

Multiagent decision-making in partially observable environments is usually modelled as either an extensive-form game (EFG) in game theory or a partially observable stochastic game (POSG) in multiagent reinforcement learning (MARL). One issue with the current situation is that while most practical problems can be modelled in both formalisms, the relationship of the two models is unclear, which hinders the transfer of ideas between the two communities. A second issue is that while EFGs have recently seen significant algorithmic progress, their classical formalization is unsuitable for efficient presentation of the underlying ideas, such as those around decomposition. To solve the first issue, we introduce factored-observation stochastic games (FOSGs), a minor modification of the POSG formalism which distinguishes between private and public observation and thereby greatly simplifies decomposition. To remedy the second issue, we show that FOSGs and POSGs are naturally connected to EFGs: by "unrolling" a FOSG into its tree form, we obtain an EFG. Conversely, any perfect-recall timeable EFG corresponds to some underlying FOSG in this manner. Moreover, this relationship justifies several minor modifications to the classical EFG formalization that recently appeared as an implicit response to the model's issues with decomposition. Finally, we illustrate the transfer of ideas between EFGs and MARL by presenting three key EFG techniques -- counterfactual regret minimization, sequence form, and decomposition -- in the FOSG framework.
BibTeX
@inproceedings{kovarik2023rethinking,
  author = {Vojtech Kovarík and Martin Schmid and Neil Burch and Michael Bowling and Viliam Lisý},
  title = {{Rethinking Formal Models of Partially Observable Multiagent Decision Making (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/783},
}
Figure