2026-08-10T11:49:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4196 2024-03-06T10:34:52Z ddc:004 open_access

What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives Chatterjee, Krishnendu Chmelik, Martin Tracol, Mathieu POMDPs Omega-regular objectives Parity objectives Qualitative analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Krishnendu Chatterjee and Martin Chmelik and Mathieu Tracol 2013 Is Part Of LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2013.165 urn:nbn:de:0030-drops-41962 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.165 eng https://creativecommons.org/licenses/by/3.0/legalcode