POMDPs under probabilistic semantics
From MaRDI portal
Abstract: We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) quantitative constraint defines the set of paths where the payoff is at least a given threshold lambda_1 in (0,1]; and (ii) qualitative constraint which is a special case of quantitative constraint with lambda_1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraint are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraint we show that the problem of deciding the existence of a finite-memory controller is undecidable.
Recommendations
- What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
- Qualitative analysis of partially-observable Markov decision processes
- Finite-memory strategies in POMDPs with long-run average objectives
- What is decidable about partially observable Markov decision processes with omega-regular objectives
- Optimal cost almost-sure reachability in POMDPs
Cites work
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 1216123 (Why is no real title available?)
- scientific article; zbMATH DE number 1263212 (Why is no real title available?)
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 765034 (Why is no real title available?)
- scientific article; zbMATH DE number 3240812 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- Algorithms for Omega-Regular Games with Imperfect Information
- Automated analysis of real-time scheduling using graph games
- Biological Sequence Analysis
- Complexity of finite-horizon Markov decision process problems
- Finding Shortest Witnesses to the Nonemptiness of Automata on Infinite Words
- On the undecidability of probabilistic planning and related stochastic optimization problems
- Optimal control of diffusion processes with reflection
- Planning and acting in partially observable stochastic domains
- Probabilistic automata
- Probabilistic automata on finite words: decidable and undecidable problems
- Qualitative analysis of partially-observable Markov decision processes
- Randomness for free
- Symbolic Feedback Control for Navigation
- The Complexity of Markov Decision Processes
- The complexity of two-player games of incomplete information
- Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
Cited in
(19)- Optimal cost almost-sure reachability in POMDPs
- Enforcing almost-sure reachability in POMDPs
- Elaboration Tolerant Representation of Markov Decision Process via Decision-Theoretic Extension of Probabilistic Action Language +
- What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
- Minimal disclosure in partially observable Markov decision processes
- Verification of Indefinite-Horizon POMDPs
- Analyzing generalized planning under nondeterminism
- Path-constrained Markov decision processes: bridging the gap between probabilistic model-checking and decision-theoretic planning
- Multiple-environment Markov decision processes
- Qualitative analysis of partially-observable Markov decision processes
- What is decidable about partially observable Markov decision processes with omega-regular objectives
- CEGAR for compositional analysis of qualitative properties in Markov decision processes
- Finite-memory strategies in POMDPs with long-run average objectives
- Randomness for free
- Stochastic games with lexicographic objectives
- Optimality guarantees for particle belief approximation of POMDPs
- Parameter-Independent Strategies for pMDPs via POMDPs
- Under-approximating expected total rewards in POMDPs
- Further improvements of determinization methods for fuzzy finite automata
This page was built for publication: POMDPs under probabilistic semantics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344358)
