Optimal Cost Almost-sure Reachability in POMDPs
We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Enforcing Almost-Sure Reachability in POMDPs
Partially-Observable Markov Decision Processes (POMDPs) are a well-known stochastic model for sequential decision making under limited information. We consider the EXPTIME-hard problem of synthesising policies that almos…
Decision Makingreinforcement-learningReinforcement Learning (RL)Safe Exploration+1A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs
POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question i…
Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives
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 POMDP…
Decision MakingEfficient ExplorationHeuristic SearchSequential Decision MakingSensor Synthesis for POMDPs with Reachability Objectives
Partially observable Markov decision processes (POMDPs) are widely used in probabilistic planning problems in which an agent interacts with an environment using noisy and imprecise sensors. We study a setting in which th…
Bounded Policy Synthesis for POMDPs with Safe-Reachability Objectives
Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in man…
valid