POMDPs under Probabilistic Semantics
Krishnendu Chatterjee, Martin Chmelik
Abstract:
We consider partially observable Markov decision processes (POMDPs) with limitaverage payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the longrun average of the rewards. We consider two types of path constraints: (i) quantitative constraint defines the set of paths where the payoff is at least a given threshold lambda_1 in (0,1]; and (ii) qualitative constraint which is a special case of quantitative constraint with lambda_1=1. We consider the computation of the almostsure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraint are as follows: (i) the problem of deciding the existence of a finitememory controller is EXPTIMEcomplete; and (ii) the problem of deciding the existence of an infinitememory controller is undecidable. For quantitative path constraint we show that the problem of deciding the existence of a finitememory controller is undecidable.
Keywords:
Pages: 142151
PS Link:
PDF Link: /papers/13/p142chatterjee.pdf
BibTex:
@INPROCEEDINGS{Chatterjee13,
AUTHOR = "Krishnendu Chatterjee
and Martin Chmelik",
TITLE = "POMDPs under Probabilistic Semantics",
BOOKTITLE = "Proceedings of the TwentyNinth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "142151"
}

