Finding Approximate POMDP solutions Through Belief Compression

Nicholas Roy, Geoffrey J. Gordon, Sebastian ThrunJAIR 2005 · OpenReview

TL;DR

This paper tackles the intractability of solving large Partially Observable Markov Decision Processes (POMDPs) by proposing a novel approach: belief compression. They introduce Exponential Family Principal Components Analysis (E-PCA) to find low-dimensional representations of belief states, enabling planning in a much smaller space and allowing for solutions to POMDPs orders of magnitude larger than previously feasible.

What Problem Does This Paper Address?

Decision-making in robotics and AI often involves dealing with uncertainty about the environment's true state. Partially Observable Markov Decision Processes (POMDPs) are a powerful framework for handling this uncertainty by maintaining a probability distribution over possible states (a "belief"). However, finding optimal policies for POMDPs is notoriously difficult because the belief space can be extremely high-dimensional and continuous. Standard value iteration methods struggle with problems having more than a few hundred states, which is far too small for many real-world applications like robot navigation in complex environments. This paper aims to bridge this gap by making POMDP planning tractable for much larger and more complex problems.

Methods

The core of the paper's contribution lies in belief compression using Exponential Family Principal Components Analysis (E-PCA).

  • Standard PCA vs. E-PCA: Traditional PCA finds a linear projection that preserves data variance. However, the authors found that PCA performs poorly when representing probability distributions, often producing non-physical results (negative probabilities, distributions not summing to 1). E-PCA generalizes PCA by incorporating a link function and a loss function tailored to specific probability distributions.
  • Exponential Family Link Function: For representing beliefs (which are probability distributions), they choose an exponential link function. This choice has two key advantages:
  • It ensures that the reconstructed beliefs are always positive.
  • It naturally penalizes errors in low-probability regions, which is crucial for accurate belief representation. This choice of link function effectively minimizes the unnormalized KL divergence between the original and reconstructed beliefs.

  • E-PCA Algorithm: The paper outlines an iterative algorithm (Table 1) to find the low-dimensional representation (matrix B) and the basis vectors (U) by minimizing the E-PCA loss function.

  • Low-Dimensional Planning: Once the low-dimensional belief space is established, they discretize it and use fitted value iteration (a form of dynamic programming) to compute an approximate value function and policy within this reduced space. This is a departure from standard POMDP value iteration, which relies on convexity that is lost after the non-linear belief transformation.

Datasets

The paper evaluates their approach on:

  • Synthetic Toy Problem: A maze problem with 200 states and 102 observations, designed to be large for POMDP standards and challenging for heuristic policies.
  • Robot Navigation Problems:
    • A simulated "Wean Hall corridor" navigation task.
  • A simulated navigation task in the "Longwood retirement facility" (also used for visualization in Figure 1).
  • A more complex "Finding People" problem, motivated by nursebot domains, involving a larger state space (cross-product of robot and person positions) and multi-modal belief distributions.

Key Insights and Ideas

  • Beliefs live on low-dimensional manifolds: The core insight is that in many real-world POMDPs, the actual beliefs encountered by a controller don't explore the entire high-dimensional belief space but rather lie on a structured, low-dimensional surface. Identifying and exploiting this structure is key to tractability.
  • PCA is not ideal for probability distributions: The paper clearly demonstrates that standard PCA's geometric approach fails to adequately represent probability distributions, leading to non-physical reconstructions and poor performance.
  • E-PCA is a principled way to compress beliefs: By using an exponential family link function and a corresponding loss (KL divergence), E-PCA provides a statistically grounded method for finding low-dimensional representations of beliefs that are physically meaningful.
  • Low-dimensional planning is feasible: Once beliefs are compressed, planning becomes significantly more tractable, allowing for solutions to problems that were previously intractable.
  • The choice of loss function matters: The paper highlights that minimizing squared error (PCA) is not as effective as minimizing KL divergence for probability distributions.

Key Results

  • Significant dimensionality reduction: E-PCA achieved substantial reductions in belief space dimensionality, e.g., from ~800 states down to 5-6 bases for robot navigation, and from ~2000 states down to 6 bases for the "Finding People" problem.
  • Improved policy performance:
    • In the toy maze problem, E-PCA achieved approximately twice the reward of a Maximum-Likelihood heuristic and performed comparably to or better than conventional PCA.
  • In robot navigation, E-PCA significantly outperformed conventional PCA and Maximum-Likelihood heuristics, especially in scenarios with complex belief structures (e.g., multi-modal distributions).
  • In the "Finding People" problem, E-PCA found policies that were significantly more accurate and efficient than PCA, even with a large number of bases for PCA.
  • Scalability: The method enabled solving POMDPs orders of magnitude larger than those solvable by conventional techniques. For example, the E-PCA decomposition was computed for problems with tens of thousands of states.
  • Computational efficiency: While E-PCA computation is iterative, the time to compute the low-dimensional representation was manageable, and subsequent value iteration in the reduced space was very fast (50-100ms).

Limitations and Future Work

  • Local Minima in E-PCA: The E-PCA optimization can be susceptible to local minima, although the authors found this not to be a problem in their experiments. They suggest future work on addressing this for more complex domains.
  • Assumption of a single low-dimensional surface: The current approach assumes all beliefs lie on a single low-dimensional surface. Future work could explore problems where beliefs might lie on multiple distinct surfaces.
  • Model selection for dimensionality: Choosing the appropriate number of bases (dimensionality) is still an open question. While they use reconstruction quality, they suggest evaluating policies for different dimensionalities as an alternative.
  • Extending to other loss functions/link functions: The paper mentions that other loss functions and link functions could be explored, potentially leading to different representations.
  • Improving the value function approximation: While E-PCA finds a good representation of beliefs, the subsequent value function approximation (e.g., using grids) can still be a bottleneck. Exploring more sophisticated function approximators is a direction for future work.
  • Directly computing representation from model parameters: The current method relies on sampled beliefs. Future work could explore computing the low-dimensional representation directly from the POMDP model parameters, similar to Poupart and Boutilier (2002).

Summary updated

Abstract

Standard value function approaches to finding policies for Partially Observable Markov Decision Processes (POMDPs) are generally considered to be intractable for large models. The intractability of these algorithms is to a large extent a consequence of computing an exact, optimal policy over the entire belief space. However, in real-world POMDP problems, computing the optimal policy for the full belief space is often unnecessary for good control even for problems with complicated policy classes. The beliefs experienced by the controller often lie near a structured, low-dimensional subspace embedded in the high-dimensional belief space. Finding a good approximation to the optimal value function for only this subspace can be much easier than computing the full value function. We introduce a new method for solving large-scale POMDPs by reducing the dimensionality of the belief space. We use Exponential family Principal Components Analysis (Collins, Dasgupta & Schapire, 2002) to represent sparse, high-dimensional belief spaces using small sets of learned features of the belief state. We then plan only in terms of the low-dimensional belief features. By planning in this low-dimensional space, we can find policies for POMDP models that are orders of magnitude larger than models that can be handled by conventional techniques. We demonstrate the use of this algorithm on a synthetic problem and on mobile robot navigation tasks.
BibTeX
@article{roy2005finding,
  author = {Nicholas Roy and Geoffrey J. Gordon and Sebastian Thrun},
  title = {{Finding Approximate POMDP solutions Through Belief Compression}},
  journal = {J. Artif. Intell. Res.},
  year = {2005},
  url = {https://openreview.net/forum?id=T6wyfAk42q3},
}
Figure