Sparse tree search optimality guarantees in POMDPs with continuous observation spaces
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.
Code (1)
Similar Papers 제목 키워드 기반
Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
This article presents the state-of-the-art in optimal solution methods for decentralized partially observable Markov decision processes (Dec-POMDPs), which are general models for collaborative multiagent planning under u…
ClusteringVoronoi Progressive Widening: Efficient Online Solvers for Continuous State, Action, and Observation POMDPs
This paper introduces Voronoi Progressive Widening (VPW), a generalization of Voronoi optimistic optimization (VOO) and action progressive widening to partially observable Markov decision processes (POMDPs). Tree search …
Optimality Guarantees for Particle Belief Approximation of POMDPs
Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. However, POMDPs are notoriously difficult to solve, especially when the state and ob…
Online POMDP Planning with Anytime Deterministic Optimality Guarantees
Decision-making under uncertainty is a critical aspect of many practical autonomous systems due to incomplete information. Partially Observable Markov Decision Processes (POMDPs) offer a mathematically principled framewo…
Decision MakingDecision Making Under UncertaintyLeveraging the Value of Information in POMDP Planning
Partially observable Markov decision processes (POMDPs) offer a principled formalism for planning under state and transition uncertainty. Despite advances made towards solving large POMDPs, obtaining performant policies …