Sparse Tree Search Optimality Guarantees in POMDPs with Continuous Observation Spaces

Michael H. Lim, Claire J. Tomlin, Zachary N. Sunberg

Abstract

Partially observable Markov decision processes (POMDPs) with continuous state and observation spaces have powerful flexibility for representing real-world decision and control problems but are notoriously difficult to solve. Recent online sampling-based algorithms that use observation likelihood weighting have shown unprecedented effectiveness in domains with continuous observation spaces. However, there has been no formal theoretical justification for this technique. This work offers such a justification, proving that a simplified algorithm, partially observable weighted sparse sampling (POWSS), will estimate Q-values accurately with high probability and can be made to perform arbitrarily near the optimal solution by increasing computational power.

Introduction: The Challenge of Continuous Observations

Partially Observable Markov Decision Processes (POMDPs) are the mathematical framework for modeling decision-making under uncertainty. While they are highly expressive, solving them in continuous state and observation spaces—such as a robot navigating via precise GPS coordinates—is computationally daunting.

Traditional online solvers like POMCP or DESPOT rely on building search trees of future outcomes. In discrete spaces, these algorithms use rejection sampling to filter state particles that match observed outcomes. However, in continuous spaces, the probability of an exact match is zero. This leads to "particle depletion," where the solver loses its representation of uncertainty and collapses into a QMDP approximation. This approximation assumes all uncertainty will vanish after the first step, often leading to suboptimal, "greedy" behavior that fails to gather necessary information.

Methodology: From POSS to POWSS

To address this, the authors analyze two variations of sparse sampling algorithms:

  1. POSS (Partially Observable Sparse Sampling): A naive extension of classic sparse sampling. In continuous spaces, it can only match a single state particle to a unique observation, effectively ignoring the underlying belief distribution and behaving like a QMDP solver.
  2. POWSS (Partially Observable Weighted Sparse Sampling): The primary contribution of this work. Instead of filtering particles to match an observation, POWSS retains all particles and assigns them importance weights based on the likelihood of the observation given the state.
Comparison of POSS (left) and POWSS (right) tree structures. POWSS uses importance weighting (indicated by varying dot sizes) to maintain a rich belief distribution, whereas POSS (left) suffers from particle depletion in continuous spaces.

By using Self-Normalized Importance Sampling, POWSS preserves the probability distribution over states even when observations are continuous. The authors prove that if the Rényi Divergence ($d_\infty$) between the sampling and target distributions is bounded, the error in Q-value estimates at the root of the tree decreases as the "width" (number of samples per node) increases.

Empirical Evaluation: The Continuous Observation Tiger

The theoretical findings were validated using a new benchmark: Continuous Observation Tiger (CO-tiger). In this problem, an agent receives a noisy continuous signal to determine the tiger's location. This setup specifically penalizes QMDP-style approximations that fail to value information-gathering actions like "Listen."

Convergence of Q-value estimates in the CO-tiger problem. POWSS (solid black line) converges to the true optimal value (red dashed line) as tree width increases, while the unweighted POSS (dotted line) significantly overestimates values due to the QMDP trap.

As shown in the results, POSS consistently overvalued actions because its QMDP-like estimate assumed perfect future knowledge. In contrast, POWSS correctly identified "Listen" as the optimal action, with its value estimates converging to the analytical optimum as computational resources (tree width $C$) increased. Practical solvers like POMCPOW, which use similar weighting heuristics, also showed convergence, validating the theoretical soundness of their underlying mechanisms.

Conclusion and Future Work

This paper provides the first formal proof that importance weighting in online tree search can achieve global optimality in continuous observation POMDPs. While POWSS is a "brute force" algorithm intended for theoretical analysis rather than real-time deployment, it bridges the gap between empirical success and mathematical rigor. Future work remains to prove convergence for more efficient heuristics, such as Double Progressive Widening, and to refine the divergence assumptions for scenarios with perfectly accurate sensors.

Summary updated

Abstract

Partially observable Markov decision processes (POMDPs) with continuous state and observation spaces have powerful flexibility for representing real-world decision and control problems but are notoriously difficult to solve. Recent online sampling-based algorithms that use observation likelihood weighting have shown unprecedented effectiveness in domains with continuous observation spaces. However there has been no formal theoretical justification for this technique. This work offers such a justification, proving that a simplified algorithm, partially observable weighted sparse sampling (POWSS), will estimate Q-values accurately with high probability and can be made to perform arbitrarily near the optimal solution by increasing computational power.
BibTeX
@inproceedings{lim2020sparse,
  author = {Michael H. Lim and Claire J. Tomlin and Zachary N. Sunberg},
  title = {{Sparse Tree Search Optimality Guarantees in POMDPs with Continuous Observation Spaces}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=0TuYmTJNzP},
}

Loading related content...

Figure