Abstract
Partially Observable Markov Decision Processes (POMDPs) are a well-established and rigorous framework for sequential decision-making under uncertainty. POMDPs are well-known to be intractable to solve exactly, and there has been significant work on finding tractable approximation methods. One well-studied approach is to find a compression of the original POMDP by projecting the belief states to a lower-dimensional space. We present a novel dimensionality reduction method for POMDPs based on locality preserving non-negative matrix factorization. Unlike previous approaches, such as Krylov compression and regular non-negative matrix factorization, our approach preserves the local geometry of the belief space manifold. We present results on standard benchmark POMDPs showing improved performance over previously explored compression algorithms for POMDPs.
Introduction
In artificial intelligence and robotics, the Partially Observable Markov Decision Process (POMDP) is the gold-standard framework for decision-making under uncertainty. For example, a robot navigating an unfamiliar environment maintains a "belief state"—a probability distribution over all possible locations. However, as the state space grows, the dimensionality of the belief space becomes massive, leading to the "curse of dimensionality."
To address this, researchers use belief compression to project high-dimensional belief spaces into lower-dimensional ones. While linear compression techniques like Krylov bases or Orthogonal Non-Negative Matrix Factorization (ONMF) exist, they often ignore the local geometry of the data. If two belief states are nearly identical, a poor compression might separate them in the reduced space, degrading the quality of the AI's decision-making.
Methodology: Locality Preserving NMF
This paper introduces Locality Preserving Non-Negative Matrix Factorization (LPNMF) to create a more "geometry-aware" compression. The method relies on two key pillars:
- Non-Negativity: Since belief states are probability distributions, they are inherently non-negative. NMF ensures the compressed model remains physically intuitive and compatible with standard solvers.
- Locality Constraints: By adding a graph Laplacian regularizer, the algorithm builds a neighborhood graph of sampled belief points. If two points are neighbors in the original space, the algorithm penalizes their separation in the compressed space.
The workflow involves sampling belief points, finding a compression matrix $F$ that respects local geometry, and transforming the original POMDP's rewards and transitions into this reduced space. This allows the use of standard solvers like Point-Based Value Iteration (PBVI) on a much smaller problem.
Key Insights
A critical theoretical insight is that POMDP value functions are Lipschitz continuous. This implies that if two belief states are close, their optimal values are also close. Consequently, a compression method that preserves locality is mathematically incentivized to preserve the integrity of the value function. LPNMF is specifically designed to respect the lower-dimensional "manifold" where belief states typically reside.
Experimental Results
The researchers evaluated LPNMF on classic benchmarks, including Tiger-grid, Hallway, Hallway2, Rock-sample, and the large-scale Tag-avoid problem (870 states).
LPNMF consistently outperformed standard NMF and state-of-the-art ONMF, particularly at high levels of compression (low dimensions). In the tag-avoid benchmark, LPNMF achieved a reward of -9.0 in only 500 seconds, whereas the uncompressed Perseus solver took 2,300 seconds to reach a comparable reward of -6.5. When restricted to the same 500-second window, the uncompressed solver performed significantly worse (-13.0).
Conclusion
LPNMF provides a robust framework for POMDP compression by preserving the local geometry of belief spaces. While the method requires empirical tuning of the locality parameter ($\lambda$), it demonstrates superior performance on complex benchmarks. Future work may explore non-linear manifold learning to further enhance compression quality, potentially scaling to even larger real-world models.
Summary updated