In a perfect-information game like Chess or Go, the current state of the board tells you everything you need to know to make an optimal decision. Algorithms can look ahead, simulate future trajectories, and evaluate positions directly.
But when information is hidden—whether due to a poker opponent's private cards, noisy physical sensors on a robot, or a stealthy cyber-attack on a drone—this foundational assumption crumbles. In these imperfect-information environments, an agent cannot evaluate a single state because they do not know exactly which state they are in. Decisions depend on the entire history of observations, leading to a combinatorial explosion that makes standard search and planning algorithms unusable.
To solve this, a powerful shared insight has emerged across game theory, formal verification, and artificial intelligence: we can convert an imperfect-information problem into a perfect-information problem by lifting the state space into an epistemic (knowledge-based) space. Instead of tracking where the system is, we track what the agent knows.
The Core Mechanism: Epistemic State Lifting
The fundamental trick of epistemic state lifting is to shift our perspective from the physical world to the observer's mind.
Imagine an agent navigating an environment with imperfect sensors. At any moment, based on its history of actions and observations, the agent cannot pinpoint its exact physical state $s$. Instead, it knows it must be in one of several possible states: $\{s_1, s_2, s_3\}$.
This set of possible states is called a knowledge set or a belief state. The breakthrough realization is that while the physical state transitions are hidden, the transitions between these knowledge sets are completely public and deterministic.
[Physical World: Hidden Transitions]
State s1 ----(Action a)----> State s1' (Hidden)
State s2 ----(Action a)----> State s2' (Hidden)
[Epistemic World: Fully Observable Transitions]
Belief State {s1, s2} ----(Action a + Observation o)----> Belief State {s1'}
When the agent takes an action and receives a new observation, the set of possible states updates in a predictable way. By treating each set of states as a single macro-state in a larger, synthesized game graph, we create a new game. In this lifted game, the agent always knows exactly which macro-state it is in.
As shown by Jean-François Raskin et al. in Algorithms for Omega-Regular Games with Imperfect Information, this knowledge-based subset construction successfully reduces imperfect-information games to perfect-information games. This transformation allows researchers to apply standard symbolic fixed-point iterations and safety game solvers to systems that initially seemed unmanageable.
From Sets to Probabilities: Public Belief States
While tracking sets of possibilities works well for qualitative objectives (like guaranteeing a system never enters an unsafe state), it falls short when games involve probabilities, mixed strategies, or adversarial deception. In a game like Texas Hold'em, you don't just need to know what cards your opponent might have; you need to know the probability distribution over those cards.
To handle this, the concept of a knowledge set is expanded into a Public Belief State (PBS). A PBS is a joint probability distribution over all players' private information, conditioned on the public history of the game (such as actions and shared observations).
In Combining Deep Reinforcement Learning and Search for Imperfect-Information Games, Noam Brown et al. demonstrated that an imperfect-information game can be modeled as a continuous-state perfect-information game using PBSs. Because the PBS evolves deterministically based on public actions, it can be treated exactly like a board state in Chess. This allowed their framework, ReBeL, to run look-ahead search and self-play reinforcement learning directly on top of poker beliefs, achieving superhuman performance without relying on domain-specific abstractions.
Similarly, Michal Šustr et al. in Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games generalized public states into augmented information sets, proving that this abstraction allows agents to compute sound online strategies locally during gameplay, rather than solving the entire massive game tree in advance.
Applications Across Diverse Domains
The power of this reduction is its generality. Across different fields, researchers use variations of epistemic lifting to make intractable problems solvable by off-the-shelf tools.
1. Controller Synthesis and Verification
When designing controllers for real-time or probabilistic systems, sensors are often limited to save costs or power. In Controllers with Minimal Observation Power (Application to Timed Systems), Peter Bulychev et al. transformed imperfect-information timed games into perfect-information safety games by tracking beliefs. This allowed them to synthesize controllers that guarantee safety using the cheapest possible sensor configurations. For probabilistic components, Laurent Doyen et al. in The Complexity of Synthesis from Probabilistic Components used a similar reduction to map partial-observation scenarios onto fully observable models, enabling the use of efficient parity game solvers.
2. Autonomous System Security
In security contexts, an attacker's actions or state might be hidden from a defender. Mahmoud Elfar et al. tackled this in Security-Aware Synthesis Using Delayed-Action Games. By restructuring the game timeline to delay adversarial actions, they reduced hidden-information games to perfect-information structures. This allowed them to use mature, off-the-shelf model checkers to synthesize secure control strategies for autonomous vehicles under cyber-attacks.
3. Generalized Planning
AI planning under partial observability is notoriously difficult. Giuseppe De Giacomo et al. showed in Imperfect-Information Games and Generalized Planning that by constructing belief states that map to physically realizable trajectories, complex planning problems can be reduced to perfect-information games. This preserves soundness and completeness while opening the door to standard game-theoretic solvers.
The Computational Trade-Off
If reducing imperfect information to perfect information is so effective, why don't we use it for everything? The answer lies in a fundamental computational trade-off: we exchange structural uncertainty for state-space explosion.
When we lift a game to its epistemic level, the new state space is exponentially larger than the original. If a game has $n$ physical states, its power set contains $2^n$ possible knowledge sets. If we are tracking continuous probability distributions (PBSs), the state space becomes infinite.
To make this practical, modern research focuses on compact representations and localized approximations:
- Antichains: Jean-François Raskin et al. utilized lattices of antichains to represent knowledge sets compactly, avoiding the explicit enumeration of the exponential state space.
- Subgame Resolving: Instead of computing the belief space for the entire game, Ondrej Kubicek et al. in Look-ahead Search on Top of Policy Networks in Imperfect Information Games showed that agents can use constraint satisfaction to reconstruct hidden states locally, initiating look-ahead search only when a specific subgame is reached.
- Windowing: In Looking at Mean-Payoff through Foggy Windows, Guillermo Perez et al. proved that while infinite-horizon partial-observation games are often undecidable, bounding the objective to a local sliding window keeps the tracking of weights and belief states computationally bounded and decidable.
By understanding that uncertainty can be packaged into a deterministic state variable, these diverse lines of research demonstrate that the wall separating imperfect and perfect information is highly permeable. Lifting the problem to the level of knowledge remains our most reliable tool for seeing through the fog of partial observability.
Key Foundational Work
Algorithms for Omega-Regular Games with Imperfect Information (2007) — contributed 2 concept elements to this direction.
Timed Control with Observation Based and Stuttering Invariant Strategies (2007) — contributed 2 concept elements to this direction.
Representing Kriegspiel States with Metapositions (2007) — contributed 1 concept elements to this direction.