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

Chatterjee, Krishnendu and Chmelík, Martin and Tracol, Mathieu (2013) What is decidable about partially observable Markov decision processes with omega-regular objectives. In: CSL: Computer Science Logic, September 2-5, 2013, Torino, Italy.

[img] Text
2.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2017-756-v1+1]
Download (337Kb)
Official URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2013.i

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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: POMDPs, Omega-regular objectives, Parity objectives, Qualitative analysis
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
Research Group: Chatterjee Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 20 Feb 2017 08:10
Last Modified: 05 Sep 2017 14:16
URI: https://repository.ist.ac.at/id/eprint/756

Actions (login required)

View Item View Item