Perfect Information Reductions for Imperfect Information Games

This direction is split into other directions: epistemic state lifting. Its last version stays readable and citable here.

Version 1 of 133 papers39 conceptsfrozen 2026-10-04

In the classic taxonomy of games, a sharp line divides "perfect information" games like Chess and Go from "imperfect information" games like Poker or Kriegspiel. In the former, the state is fully observable, and the game possesses an optimal substructure that allows for recursive solving via Bellman’s optimality principle. In the latter, the hidden state traditionally breaks this substructure, forcing researchers to rely on complex, global equilibrium concepts like Counterfactual Regret Minimization.

However, a recurring breakthrough across game theory and reinforcement learning has emerged: imperfect information games can be reduced to perfect information games by shifting the perspective from the physical state to the "belief state." By treating a probability distribution over possible worlds as a single, observable state, we can restore the recursive properties of perfect information and apply powerful search and optimization tools to hidden-information environments.

The Belief State as a Perfect Information State

The core intuition behind this research direction is that while a player may not know the exact state of the world, they do know their own history of observations and actions. This history defines a "belief"—a set or probability distribution of all possible states the game could currently be in.

As Noam Brown and Adam Lerer demonstrate in Recursive Belief-based Learning (ReBeL), if we define the "state" as this public belief, the game becomes a continuous-state perfect-information game. This transformation allows agents to use the same look-ahead search and value iteration techniques that powered AlphaZero. Instead of searching through a tree of moves, the agent searches through a tree of belief updates.

Collapsing Possibilities into Metapositions

In games with massive state spaces, tracking every possible world is computationally impossible. To solve this, researchers use "metapositions" or "occupancy spaces" to collapse billions of potential states into a single, manageable representation.

  • Metapositions: In the "blindfold" chess game Kriegspiel, Paolo Ciancarini and Gian Piero Favini used metapositions to represent all potential opponent locations on a single board. This allowed their engine, Darkboard, to use traditional minimax search on a "pseudo-perfect" information state.
  • Occupancy Markov Games: Olivier Buffet and Jilles Dibangoye formalized this in On Bellman's Optimality Principle for zs-POSGs. They proved that zero-sum partially observable stochastic games (zs-POSGs) can be mapped to "occupancy-based" games. This mapping ensures that the value function remains continuous and piece-wise linear, making it solvable via Heuristic Search Value Iteration (HSVI).

Policy Announcement and Regularization

A significant hurdle in these reductions is the "non-correspondence" problem: in competitive games, your optimal strategy depends on what your opponent thinks you know. Samuel Sokota and J Zico Kolter addressed this by abstracting imperfect information away through policy announcements.

By requiring players to publicly commit to a distribution of actions (a policy) rather than just a single action, the private information is effectively "priced into" the public state. When combined with entropy-based regularization, this transformation allows complex games like Poker to be solved using backward induction, a technique previously reserved for games with no hidden secrets.

Applications in Verification and Security

This reduction isn't just for games; it is a vital tool for synthesizing safe controllers in uncertain environments. By transforming partially observable MDPs (POMDPs) into two-player games where "uncertainty" acts as an adversarial opponent, researchers like Nils Jansen can synthesize strategies with formal safety guarantees. Similarly, Delayed-Action Games allow researchers to use off-the-shelf "perfect information" model checkers to solve security-aware synthesis problems, effectively bypassing the complexity of hidden-state reasoning by restructuring the game's timeline.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_perfect_information_reductions_for_imper_a9a88efe,
  title = {Perfect Information Reductions for Imperfect Information Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/perfect-information-reductions-for-imperfect-information-games/rdr_a9a88efee298412fbb1fb973654c401d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_perfect_information_reductions_for_imper_a9a88efe_v1,
  title = {Perfect Information Reductions for Imperfect Information Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/perfect-information-reductions-for-imperfect-information-games/rdr_a9a88efee298412fbb1fb973654c401d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}