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 IST-2009-0001_IST-2009-0001.pdf 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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
04d9cc065cc19598a4e8631c47f1a562


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar