When an agent operates with perfect information, its decision-making can be modeled as a Markov Decision Process (MDP). In an MDP, the optimal action depends solely on the current, fully known state. But real-world robots and autonomous systems rarely enjoy this luxury. Sensors are noisy, environments are occluded, and key variables remain hidden.
To make decisions under partial observability, the agent must shift from planning over physical states to planning over belief states—probability distributions over all possible physical states. This framework is known as a Partially Observable Markov Decision Process (POMDP).
While mathematically elegant, the belief space introduces a severe computational bottleneck: the curse of dimensionality. If a physical state space contains $N$ discrete states, its corresponding belief space is an $(N-1)$-dimensional continuous simplex. If the environment is described by a set of factored features, the number of physical states $N$ scales exponentially with the number of features, causing the dimensionality of the belief space to explode. Optimizing a policy that maps every point in this uncountably infinite, high-dimensional space to an action quickly becomes intractable.
To make planning and learning practical, researchers have developed methods to compress, factor, and approximate this high-dimensional belief space.
Factoring and Exploiting Mixed Observability
One of the most direct ways to combat the curse of dimensionality is to break the monolithic belief distribution into smaller, independent components. If the correlations between certain environmental variables are weak, we can maintain factored, approximate belief states rather than a full joint distribution. As demonstrated by Andres C. Rodriguez et al. in Reinforcement Learning Using Approximate Belief States, marginalizing out these correlations dramatically reduces the dimensionality of the tracking problem, allowing reinforcement learning agents to find effective policies in minutes rather than hours.
A complementary insight is that partial observability is rarely absolute. In many robotic applications, some state variables are known with near certainty (such as a robot's internal joint configurations or GPS coordinates), while others remain hidden (such as the positions of moving obstacles).
Standard POMDP Belief Space:
[ Fully Observable Vars + Partially Observable Vars ] ---> High-Dimensional Simplex
MOMDP Factored Space:
[ Fully Observable Vars (Discrete/Continuous State) ] x [ Partially Observable Vars (Low-Dim Belief) ]
By exploiting this structure, SM Ong et al. introduced Mixed Observability MDPs (MOMDPs) in POMDPs for robotic tasks with mixed observability. Instead of constructing a massive belief space over the entire state vector, the authors separate the state into fully and partially observable components. The agent only maintains a probability distribution over the hidden variables, drastically shrinking the dimensionality of the remaining belief space and enabling real-time planning on physical hardware.
Projecting onto Low-Dimensional Manifolds
Even when an environment possesses many hidden variables, the belief states that an agent actually encounters during a task rarely span the entire continuous simplex. Physical laws, environmental constraints, and predictable transition dynamics mean that "plausible" beliefs often lie on a much lower-dimensional manifold embedded within the high-dimensional space.
To exploit this property, Nicholas Roy et al. proposed a technique called Exponential Family PCA (E-PCA) in Exponential Family PCA for Belief Compression in POMDPs. By collecting a sample of reachable beliefs and projecting them onto a tiny set of low-dimensional features, the authors allowed a robot to perform its planning updates directly on this compressed manifold. This bypasses the high-dimensional simplex entirely while preserving the statistical information necessary for navigation.
High-Dimensional Belief Simplex (All possible distributions)
|
v [E-PCA / Variational Inference Compression]
Low-Dimensional Manifold (Only plausible, physically reachable distributions)
In modern deep learning applications, this compression is often learned implicitly from data. For instance, in Deep Belief Markov Models for POMDP Inference, Giacomo Arcieri et al. utilize variational inference combined with neural networks to learn compact hidden state distributions directly from raw observation and action histories. This data-driven compression scales to continuous, high-dimensional environments where traditional exact Bayesian updates fail.
Point-Based Approximations and Reachability
Instead of compressing the dimensions of the belief space, another approach changes where we compute the value function. Traditional exact solvers attempt to compute an optimal action for every single point in the continuous belief space. However, because an agent starts from a specific initial belief, the vast majority of possible belief states are completely unreachable.
This realization underpins Point-Based Value Iteration (PBVI), an anytime algorithm introduced by Joelle Pineau et al. in Point-based value iteration: An anytime algorithm for POMDPs.
Continuous Belief Space: [ ∞ uncountably infinite points ]
|
PBVI Sampling: v
[ • • • • • ]
Only a small, discrete set of reachable points
Instead of maintaining value functions over the entire simplex, PBVI selects a discrete, representative set of reachable belief points by simulating trajectories through the environment. Value updates are then performed exclusively at these points. By turning an uncountably infinite planning problem into a discrete optimization problem over a sparse set of points, the authors successfully bypassed the "curse of history" while maintaining provable error bounds on performance.
For continuous state spaces where tracking discrete points is insufficient, particle filters can serve a similar sparsification role. Michael H. Lim et al. formalized this in Optimality Guarantees for Particle Belief Approximation of POMDPs (Abstract Reprint), proving that continuous POMDPs can be mapped to "Particle Belief MDPs." This framework decouples the complexity of the underlying solver from the dimensionality of the state and observation spaces, providing theoretical guarantees for approximate planning in continuous domains.
Collapsing the Observation Tree
A major driver of complexity in belief space planning is the lookahead horizon. When an agent projects its actions into the future, it must branch not only on every possible action but also on every possible observation it might receive. This causes an exponential explosion of the lookahead tree.
One powerful way to mitigate this explosion is to simplify how we reason about future observations. In Belief space planning assuming maximum likelihood observations, Robert Platt Jr. et al. introduced a simplifying assumption: during the planning lookahead, the agent assumes it will only receive the most likely observation at each step.
Standard Lookahead Tree:
(Action) ---> [Obs 1] ---> (Action) ---> [Obs 1a], [Obs 1b]...
---> [Obs 2] ---> (Action) ---> [Obs 2a], [Obs 2b]...
Maximum Likelihood Lookahead:
(Action) ---> [Most Likely Obs] ---> (Action) ---> [Most Likely Obs]...
This assumption collapses the branching observation tree into a single, deterministic path of nominal belief states. By eliminating the observation branching, the authors transformed a notoriously difficult POMDP into a deterministic trajectory optimization problem, enabling standard, highly efficient control tools to solve complex robotic manipulation tasks in real-time.
Alternatively, structural preferences within the task itself can be leveraged to prune the search space. Anthony Stentz developed this concept in PPCP: Efficient Probabilistic Planning with Clear Preferences in Partially-Known Environments. In many navigation tasks, certain outcomes are clearly preferable to others (e.g., finding a path clear is always preferred over finding it blocked). By exploiting these clear preferences, the PPCP algorithm avoids maintaining a full belief distribution over tens of thousands of unknown variables. Instead, it solves a series of fast, deterministic, $A^*$-like searches that assume preferred outcomes until sensors prove otherwise, scaling to massive environments that would paralyze a standard POMDP solver.