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: https://drops.dagstuhl.de/opus/volltexte/2013/4196/
Chatterjee, Krishnendu ; Chmelik, Martin ; Tracol, Mathieu
What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives
| pdf-format: |
|
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 | |
| Seminar: | Computer Science Logic 2013 (CSL 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 02.09.2013 |
