POMDPs under probabilistic semantics

K. Chatterjee, M. Chmelik, Artificial Intelligence 221 (2015) 46–72.


Journal Article | Published | English
Department
Abstract
We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ1ε(0,1]; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples.
Publishing Year
Date Published
2015-04-01
Journal Title
Artificial Intelligence
Volume
221
Page
46 - 72
IST-REx-ID

Cite this

Chatterjee K, Chmelik M. POMDPs under probabilistic semantics. Artificial Intelligence. 2015;221:46-72. doi:10.1016/j.artint.2014.12.009
Chatterjee, K., & Chmelik, M. (2015). POMDPs under probabilistic semantics. Artificial Intelligence, 221, 46–72. https://doi.org/10.1016/j.artint.2014.12.009
Chatterjee, Krishnendu, and Martin Chmelik. “POMDPs under Probabilistic Semantics.” Artificial Intelligence 221 (2015): 46–72. https://doi.org/10.1016/j.artint.2014.12.009.
K. Chatterjee and M. Chmelik, “POMDPs under probabilistic semantics,” Artificial Intelligence, vol. 221, pp. 46–72, 2015.
Chatterjee K, Chmelik M. 2015. POMDPs under probabilistic semantics. Artificial Intelligence. 221, 46–72.
Chatterjee, Krishnendu, and Martin Chmelik. “POMDPs under Probabilistic Semantics.” Artificial Intelligence, vol. 221, Elsevier, 2015, pp. 46–72, doi:10.1016/j.artint.2014.12.009.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1408.2058

Search this title in

Google Scholar