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 almost-surely reach some goal state without ever visiting a bad state. In particular, we are interested in computing the winning region, that is, the set of system configurations from which a policy exists that satisfies the reachability specification. A direct application of such a winning region is the safe exploration of POMDPs by, for instance, restricting the behavior of a reinforcement learning agent to the region. We present two algorithms: A novel SAT-based iterative approach and a decision-diagram based alternative. The empirical evaluation demonstrates the feasibility and efficacy of the approaches.
Code (1)
Tasks
Decision Makingreinforcement-learningReinforcement Learning (RL)Safe ExplorationSequential Decision MakingSimilar Papers 제목 키워드 기반
A 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…
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 t…
Sensor 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…
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 MakingComputing the Reachability Value of Posterior-Deterministic POMDPs
Partially observable Markov decision processes (POMDPs) are a fundamental model for sequential decision-making under uncertainty. However, many verification and synthesis problems for POMDPs are undecidable or intractabl…