What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives

Authors Krishnendu Chatterjee, Martin Chmelik, Mathieu Tracol



PDF
Thumbnail PDF

File

LIPIcs.CSL.2013.165.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Krishnendu Chatterjee
Martin Chmelik
Mathieu Tracol

Cite AsGet BibTex

Krishnendu Chatterjee, Martin Chmelik, and Mathieu Tracol. What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 165-180, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.CSL.2013.165

Abstract

We consider partially observable Markov decision processes (POMDPs) with omega-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish optimal (exponential) memory bounds.
Keywords
  • POMDPs
  • Omega-regular objectives
  • Parity objectives
  • Qualitative analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail