Qualitative analysis of partially-observable Markov decision processes

DOI10.1007/978-3-642-15155-2_24MaRDI QIDQ3586089zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger

Publication date 3 September 2010

Published in Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.1645

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Specification and verification (program logics, model checking, etc.) (68Q60) Markov and semi-Markov decision processes (90C40)

Abstract: We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observations. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability~1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDP s with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDP s with parity objectives and its subclasses.

Recommendations

• What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
• What is decidable about partially observable Markov decision processes with omega-regular objectives
• Partial-observation stochastic reachability and parity games
• POMDPs under probabilistic semantics
• The complexity of partial-observation stochastic parity games with finite-memory strategies

Cited in

(21)

• Enforcing almost-sure reachability in POMDPs
• What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
• Quantile Markov Decision Processes
• Minimal disclosure in partially observable Markov decision processes
• Probabilistic opacity for Markov decision processes
• Reachability analysis of quantum Markov decision processes
• Probabilistic disclosure: maximisation vs. minimisation
• Parity objectives in countable MDPs
• 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
• Graph Games and Reactive Synthesis
• POMDPs under probabilistic semantics
• On almost-sure intention deception planning that exploits imperfect observers
• Partial-observation stochastic games, how to win when belief fails
• Parameter-Independent Strategies for pMDPs via POMDPs
• Under-approximating expected total rewards in POMDPs
• A survey of partial-observation stochastic parity games
• Distribution-based objectives for Markov decision processes
• Further improvements of determinization methods for fuzzy finite automata
• Probabilistic timed automata with one clock and initialised clock-dependent probabilities

Describes a project that uses

Uses Software

• POMDPS

This page was built for publication: Qualitative analysis of partially-observable Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586089)