Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives

Qi Heng Ho, Martin S. Feather, Federico Rossi, Zachary N Sunberg, Morteza Lahijanian

Abstract

This paper introduces HSVI-RP, a novel algorithm designed to solve the Maximal Reachability Probability Problem (MRPP) in Partially Observable Markov Decision Processes (POMDPs). Unlike traditional discounted solvers, HSVI-RP addresses the undiscounted nature of reachability objectives by combining trial-based heuristic search on a belief graph with periodic global value iteration. This approach provides sound two-sided bounds and guaranteed convergence, overcoming the limitations of local update rules in the presence of loops and infinite horizons.

Introduction

Planning in uncertain environments often requires agents to maximize the probability of reaching a target state, a task known as the Maximal Reachability Probability Problem (MRPP). While POMDPs provide a robust framework for modeling such environments, solving MRPPs is computationally intensive due to the "curse of dimensionality" in belief space and the undiscounted nature of the objective.

Standard POMDP solvers often rely on a discount factor $\gamma < 1$ to ensure convergence, but this leads to mathematically incorrect results for reachability tasks. Furthermore, local Bellman updates can fail to converge to the correct upper bound in the presence of zero-reward loops. HSVI-RP addresses these challenges by maintaining sound, two-sided bounds within a graph-based search framework.

The HSVI-RP Algorithm

HSVI-RP (Heuristic Search Value Iteration for Reachability Probabilities) extends the HSVI2 framework to handle undiscounted reachability. The algorithm's core innovation lies in its use of a belief graph rather than a tree, and a hybrid update mechanism that combines local and global information.

Overview of the HSVI-RP algorithm cycles, including search, Bellman backup, graph updates, and periodic global upper bound value iteration.

As illustrated in the figure above, the algorithm operates in a loop consisting of four main phases:

  • Search: A trial-based search explores the belief space, guided by two-sided bounds and UCB-inspired heuristics to prevent getting stuck in loops.
  • Bellman Backup: Local updates propagate value estimates back up the explored paths.
  • Updated Graph: The algorithm maintains a graph structure to recognize revisited beliefs, which is essential for handling loops in undiscounted settings.
  • Upper Bound Value Iteration: Periodically, the algorithm performs global value iteration over the entire explored subgraph. This "pulls down" upper bounds from the frontier, ensuring convergence toward the true optimal value (the least fixed point).
Example of a belief graph structure where nodes represent probability distributions over states (beliefs) and edges represent actions and observations.

Key Insights and Results

A critical finding of this work is that discounting is an insufficient proxy for reachability; any $\gamma < 1$ results in a strict under-approximation of the true probability. HSVI-RP avoids this by treating the unexplored frontier as a target set during its global VI phase.

The algorithm was evaluated on standard benchmarks including grid navigation (Grid-av), drone obstacle avoidance, and resource management (Refuel). Key results include:

  • Superior Accuracy: HSVI-RP consistently produced tighter two-sided bounds than state-of-the-art tools like PRISM and STORM, often being the only algorithm to converge to the exact optimal value.
  • Efficiency and Scalability: On the "Refuel20" benchmark, HSVI-RP found a near-optimal policy in 22 minutes, while other methods timed out. Its depth-first approach expands orders of magnitude fewer nodes than breadth-first methods, making it highly memory-efficient.

Conclusion

HSVI-RP represents a significant advancement in solving undiscounted POMDPs with reachability objectives. By integrating global value iteration with heuristic search on a belief graph, it provides a sound and efficient framework for safety-critical planning. Future work will explore extending this methodology to Stochastic Shortest Path (SSP) problems.

Summary updated

Abstract

Partially Observable Markov Decision Processes (POMDPs) are powerful models for sequential decision making under transition and observation uncertainties. This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem (MRPP), where the goal is to maximize the probability of reaching some target states. This is also a core problem in model checking with logical specifications and is naturally undiscounted (discount factor is one). Inspired by the success of point-based methods developed for discounted problems, we study their extensions to MRPP. Specifically, we focus on trial-based heuristic search value iteration techniques and present a novel algorithm that leverages the strengths of these techniques for efficient exploration of the belief space (informed search via value bounds) while addressing their drawbacks in handling loops for indefinite-horizon problems. The algorithm produces policies with two-sided bounds on optimal reachability probabilities. We prove convergence to an optimal policy from below under certain conditions. Experimental evaluations on a suite of benchmarks show that our algorithm outperforms existing methods in almost all cases in both probability guarantees and computation time.
BibTeX
@inproceedings{ho2024sound,
  author = {Qi Heng Ho and Martin S. Feather and Federico Rossi and Zachary N Sunberg and Morteza Lahijanian},
  title = {{Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=3zSiuXYtqf},
}
Figure