Heuristic Search Value Iteration for POMDPs

2012/07/11 by Trey Smith, Smith, Trey, Reid Simmons +1 · 11 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.1207.4166

openalex publication_date 2012/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a novel POMDP planning algorithm called heuristic search value iteration (HSVI).HSVI is an anytime algorithm that returns a policy and a provable bound on its regret with respect to the optimal policy. HSVI gets its power by combining two well-known techniques: attention-focusing search heuristics and piecewise linear convex representations of the value function. HSVI's soundness and convergence have been proven. On some benchmark problems from the literature, HSVI displays speedups of greater than 100 with respect to other state-of-the-art POMDP value iteration algorithms. We also apply HSVI to a new rover exploration problem 10 times larger than most POMDP problems in the literature.

Cited by

• Learning to Trust: Bayesian Adaptation to Varying Suggester Reliability in Sequential Decision Making
• Neural Value Iteration
• Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability
• GammaZero: Learning To Guide POMDP Belief Space Search With Graph Representations
• Reinforcement Learning with Action-Triggered Observations
• Compositional shield synthesis for safe reinforcement learning in partial observability
• Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling
• Benchmarking Partial Observability in Reinforcement Learning with a Suite of Memory-Improvable Domains
• Partially Observable Monte-Carlo Graph Search
• Feature-Based Belief Aggregation for Partially Observable Markov Decision Problems
• Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions

Related

• Solving POMDPs by Searching in Policy Space
• Point-Based POMDP Algorithms: Improved Analysis and Implementation
• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives
• Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions
• Online POMDP Planning with Anytime Deterministic Optimality Guarantees