Earlier Version

Qualitative analysis of partially-observable Markov decision processes

K. Chatterjee, L. Doyen, T.A. Henzinger, Qualitative Analysis of Partially-Observable Markov Decision Processes, IST Austria, 2009.

Download
OA 342.09 KB

Technical Report | Published | English
Series Title
IST Austria Technical Report
Abstract
We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observa- tions. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability 1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDPs with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDPs with parity objectives and its subclasses.
Publishing Year
Date Published
2009-09-09
Page
20
ISSN
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Henzinger TA. Qualitative Analysis of Partially-Observable Markov Decision Processes. IST Austria; 2009. doi:10.15479/AT:IST-2009-0001
Chatterjee, K., Doyen, L., & Henzinger, T. A. (2009). Qualitative analysis of partially-observable Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2009-0001
Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. Qualitative Analysis of Partially-Observable Markov Decision Processes. IST Austria, 2009. https://doi.org/10.15479/AT:IST-2009-0001.
K. Chatterjee, L. Doyen, and T. A. Henzinger, Qualitative analysis of partially-observable Markov decision processes. IST Austria, 2009.
Chatterjee K, Doyen L, Henzinger TA. 2009. Qualitative analysis of partially-observable Markov decision processes, IST Austria, 20p.
Chatterjee, Krishnendu, et al. Qualitative Analysis of Partially-Observable Markov Decision Processes. IST Austria, 2009, doi:10.15479/AT:IST-2009-0001.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:53:25Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar