What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives

Chatterjee, Krishnendu and Chmelík, Martin and Mathieu, Tracol (2013) What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. Technical Report. IST Austria.

[img] Text
What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives.pdf - Published Version
Available under License All rights reserved.
[IST-2013-109-v1+1]
Download (337Kb)

Abstract

We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied 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 complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives.

Item Type: Monograph (Technical Report)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Research Group: Chatterjee Group
Depositing User: Martin Chmelik
Date Deposited: 20 Feb 2013 14:05
Last Modified: 19 Jul 2019 17:53
URI: https://repository.ist.ac.at/id/eprint/109

Actions (login required)

View Item View Item