Qualitative analysis of partially-observable Markov decision processes

DOI10.1007/978-3-642-15155-2_24zbMATH Open1287.68104arXiv0909.1645OpenAlexW1734951714MaRDI QIDQ3586089FDOQ3586089

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)

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.

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

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

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)

Cited In (17)

• 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
• Partial-Observation Stochastic Games
• CEGAR for compositional analysis of qualitative properties in Markov decision processes
• Title not available (Why is that?)
• Graph Games and Reactive Synthesis
• POMDPs under probabilistic semantics
• On almost-sure intention deception planning that exploits imperfect observers
• Parameter-Independent Strategies for pMDPs via POMDPs
• Under-approximating expected total rewards in POMDPs
• Title not available (Why is that?)
• A survey of partial-observation stochastic parity games
• Further improvements of determinization methods for fuzzy finite automata

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)