What is decidable about partially observable Markov decision processes with omega-regular objectives Conference Paper


Author(s): Chatterjee, Krishnendu; Chmelík, Martin; Tracol, Mathieu
Title: What is decidable about partially observable Markov decision processes with omega-regular objectives
Title Series: LIPIcs
Affiliation IST Austria
Abstract: We consider partially observable Markov decision processes (POMDPs) with ω-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 asymptotically optimal (exponential) memory bounds.
Keywords: POMDPs, Omega-regular objectives, Parity objectives, Qualitative analysis
Conference Title: CSL: Computer Science Logic
Volume: 23
Conference Dates: September 2-5, 2013
Conference Location: Torino, Italy
ISBN: 3-540-45458-6
Publisher: Springer  
Date Published: 2013-08-27
Start Page: 165
End Page: 180
URL:
DOI: 10.4230/LIPIcs.CSL.2013.165
Open access: yes (OA journal)
IST Austria Authors
  1. Mathieu Tracol
    5 Tracol
  2. Martin Chmelik
    23 Chmelik
Related IST Austria Work