License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2013.165
URN: urn:nbn:de:0030-drops-41962
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4196/
Go to the corresponding LIPIcs Volume Portal

Chatterjee, Krishnendu ; Chmelik, Martin ; Tracol, Mathieu

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

pdf-format:
16.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{chatterjee_et_al:LIPIcs:2013:4196,
  author =	{Krishnendu Chatterjee and Martin Chmelik and Mathieu Tracol},
  title =	{{What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{165--180},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Simona Ronchi Della Rocca},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4196},
  URN =		{urn:nbn:de:0030-drops-41962},
  doi =		{10.4230/LIPIcs.CSL.2013.165},
  annote =	{Keywords: POMDPs, Omega-regular objectives, Parity objectives, Qualitative analysis}
}

Keywords: POMDPs, Omega-regular objectives, Parity objectives, Qualitative analysis
Collection: Computer Science Logic 2013 (CSL 2013)
Issue Date: 2013
Date of publication: 02.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI