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

作者：

Highlights：

• Decidability of qualitative analysis of parity POMDPs under finite-memory strategies.

• Optimal memory bounds and complexity (EXPTIME-completeness) for the above problem.

• Implementation of our algorithm with several heuristics and experimental results.

摘要

•Decidability of qualitative analysis of parity POMDPs under finite-memory strategies.•Optimal memory bounds and complexity (EXPTIME-completeness) for the above problem.•Implementation of our algorithm with several heuristics and experimental results.

论文关键词：Markov decision processes,Partially observable Markov decision processes (POMDPs),ω-Regular conditions,Parity objectives,Finite-memory strategies

论文评审过程：Received 10 March 2015, Revised 15 December 2015, Accepted 27 February 2016, Available online 8 March 2016, Version of Record 1 April 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.02.009