LIPIcs.CSL.2013.165.pdf
- Filesize: 0.52 MB
- 16 pages
Document
What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives
Authors
-
Part of:
Volume:
Computer Science Logic 2013 (CSL 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2013-09-02
Cite As Get 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.
Subject Classification
Keywords
- POMDPs
- Omega-regular objectives
- Parity objectives
- Qualitative analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads