In sequential decision-making, the Markov assumption is a powerful luxury. It asserts that the current state of an environment contains all the information necessary to predict the future and choose an optimal action. Under this assumption, algorithms can map a discrete, known state directly to an action or a value estimate.
In the real world, however, this luxury vanishes. Sensors are noisy, tasks contain hidden parameters, and crucial information is frequently obscured. This mismatch creates the partial observability gap: the chasm between algorithms designed for fully observable Markov Decision Processes (MDPs) and the realities of Partially Observable MDPs (POMDPs).
Across reinforcement learning, robotics, and verification, a major research thrust focuses on bridging this gap—taking the mathematical guarantees and computational efficiencies developed for MDPs and adapting them to environments where the true state is hidden.
Why Full-Observability Algorithms Break Down
To understand why partial observability is so disruptive, we must look at how standard reinforcement learning and planning algorithms exploit the Markov property.
The Collapse of Value and Policy Iteration
In a standard MDP, value-based methods like SARSA or policy iteration maintain estimates of how good it is to be in a specific state. For instance, the multi-timescale architecture introduced by Humayoo et al. et al. in Segmenting Action-Value Functions over Time Scales in SARSA via TD(Δ) or the factored linear approximations proposed by Koller et al. et al. in Policy Iteration for Factored MDPs rely on exact state identification to compute Bellman updates.
When the state is partially observable, a single observation can correspond to multiple underlying states with vastly different optimal actions. Attempting to update a value function based purely on immediate observations destroys the contraction mapping guarantees of Bellman equations, leading to severe policy degradation or divergence.
The Exponential Explosion of Tree Search
Online planning algorithms use simulators to look ahead into the future. For example, the foundational work by the authors of A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov and the continuous action-space tree search designed by Auger et al. et al. in Continuous Upper Confidence Trees with Polynomial Exploration - Consistency build look-ahead trees to find near-optimal actions.
MDP Search Tree (State-based):
[Known State] ---> Action A ---> [Next State]
---> Action B ---> [Next State]
POMDP Search Tree (Belief/Observation-based):
[Belief State] ---> Action A ---> Observation 1 ---> [New Belief]
---> Observation 2 ---> [New Belief]
In an MDP, branching occurs only over actions and stochastic state transitions. In a POMDP, because the true state is unknown, the planner must branch over observations. Every action yields a spectrum of possible observations, each generating a new probability distribution over states (a belief state). This causes the search tree's branching factor to explode, rendering standard online sampling algorithms computationally intractable.
The Breakdown of Linear Inference
Efficient inference frameworks, such as the Q-inference method developed by Furmston et al. et al. in Efficient Inference in Markov Control Problems, achieve linear time complexity relative to the planning horizon by exploiting the conditional independence of the Markov property. When states are hidden, computing policy gradients or maximizing expected utility (as explored by Hoffman et al. et al. in Inference and Learning for Active Sensing, Experimental Design and Control) requires integrating over all possible hidden state trajectories. This couples the past to the future, pushing computational complexity from linear back to exponential.
Algorithmic Bridges to Partial Observability
To overcome these limitations, researchers have developed mechanisms that either compress history, approximate the belief space, or decouple exploration from planning.
Memory Compression via Finite-State Controllers
Instead of tracking an infinitely growing history of observations, one elegant solution is to compress history into a structured, internal memory state. Yu leverages this intuition in A Function Approximation Approach to Estimation of Policy Gradient for POMDP with Structured Policies.
By restricting the agent's policy to a finite-state controller, Yu reformulates the policy gradient estimation so that the underlying value function becomes independent of the unobservable hidden state. This mathematical shift allows standard temporal difference (TD) learning methods—originally designed for fully observable environments—to be safely applied to POMDPs.
Point-Based Value Iteration
Rather than calculating exact value functions over the entire continuous simplex of all possible belief states, point-based methods track a discrete set of representative belief points.
In Point-Based Value Iteration for Finite-Horizon POMDPs, Walraven et al. et al. demonstrate that optimizing exclusively for these sampled points provides strong convergence guarantees for finite-horizon tasks without the need for reward discounting. This makes planning practical, though scaling these methods to factored representations remains an open challenge.
Decoupling Exploration and Ambiguity
Another strategy is to treat the partial observability of an environment as a data-collection or meta-learning problem. For instance, in offline meta-reinforcement learning, an agent faces "task ambiguity"—it does not know which specific MDP it is operating in.
Dorfman et al. et al. address this in Offline Meta Learning of Exploration by training a Bayes-optimal exploration policy that treats the unknown task parameter as a hidden state, effectively converting an offline MDP ambiguity problem into a solvable POMDP framework.
From a different angle, Juba bypasses active exploration entirely in Integrated Common Sense Learning and Planning in POMDPs. By using "common sense" knowledge extracted from pre-collected reference policy traces, Juba's framework constructs decision-tree policies that isolate the planning task from the hazards of exploring an unmapped, partially observable space.
High-Level Abstractions and Future Horizons
As reinforcement learning scales to complex cyber-physical systems, researchers are trying to port high-level structural abstractions—such as relational networks, formal logic, and causal inference—into partially observable domains.
- Relational and Structural Models: Graph neural networks like SymNet 2.0, developed by Sharma et al. et al. in SymNet 2.0: Effectively handling Non-Fluents and Actions in Generalized Neural Policies for RDDL Relational MDPs, excel at generalizing policies across massive relational MDPs. However, they lack the internal mechanisms to maintain state representations when key fluents are hidden. Similarly, the task-and-motion planning framework proposed by Zhang et al. et al. in Logic Learning From Demonstrations for Multi-Step Manipulation Tasks in Dynamic Environments requires advanced, observation-driven replanning loops to handle real-world physical disturbances where the environment state is not fully known.
- Formal Verification and Causality: In multi-agent systems, frameworks like HypRL (introduced by Hsu et al. et al. in HypRL: Reinforcement Learning of Control Policies for Hyperproperties) use temporal logics to enforce complex inter-agent dependencies. Meanwhile, the automated root-cause analysis framework designed by Rogale et al. et al. in Efficient Discovery of Actual Causality in Stochastic Systems isolates failures in stochastic systems. Both currently rely on the assumption of full state tracking.
- Automata and Controlled Processes: Spectral learning methods, such as the CH-PRFA algorithm presented by Glaude et al. et al. in PAC learning of Probabilistic Automaton based on the Method of Moments, offer polynomial-time learning bounds for probabilistic automata. However, extending these spectral methods to handle controlled processes—where an agent's actions actively alter the hidden state transitions—remains a vital open challenge.
Whether modeling hidden student proficiencies in intelligent tutoring systems (as discussed in Learning a Skill-Teaching Curriculum with Dynamic Bayes Nets) or deploying autonomous robots into unmapped terrain, the objective remains identical: developing algorithms that do not merely react to immediate observations, but mathematically reason about the information they do not see.
Key Foundational Work
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes (1999) — contributed 1 concept elements to this direction.
Fast Value Iteration for Goal-Directed Markov Decision Processes (1997) — contributed 1 concept elements to this direction.
Learning Hidden Markov Models with Geometrical Constraints (1999) — contributed 1 concept elements to this direction.