POMDPs under Probabilistic Semantics

Krishnendu Chatterjee, Martin Chmelík
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:65-74, 2013.

Abstract

We consider partially observable Markov decision processes (POMDPs) with limit- average payoff, where a reward value in the interval [0, 1] is associated to every transi- tion, and the payoffof an infinite path is the long-run average of the rewards. We con- sider two types of path constraints: (i) quan- titative constraint defines the set of paths where the payoffis at least a given thresh- old $\lambda$1 $\in$(0, 1]; and (ii) qualitative constraint which is a special case of quantitative con- straint with $\lambda$1 = 1. We consider the compu- tation 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 constraint 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 constraint we show that the problem of deciding the existence of a finite-memory controller is undecidable.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-chatterjee13a, title = {POMDPs under Probabilistic Semantics}, author = {Chatterjee, Krishnendu and Chmel{\'i}k, Martin}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {65--74}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/chatterjee13a/chatterjee13a.pdf}, url = {https://proceedings.mlr.press/r11/chatterjee13a.html}, abstract = {We consider partially observable Markov decision processes (POMDPs) with limit- average payoff, where a reward value in the interval [0, 1] is associated to every transi- tion, and the payoffof an infinite path is the long-run average of the rewards. We con- sider two types of path constraints: (i) quan- titative constraint defines the set of paths where the payoffis at least a given thresh- old $\lambda$1 $\in$(0, 1]; and (ii) qualitative constraint which is a special case of quantitative con- straint with $\lambda$1 = 1. We consider the compu- tation 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 constraint 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 constraint we show that the problem of deciding the existence of a finite-memory controller is undecidable.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T POMDPs under Probabilistic Semantics %A Krishnendu Chatterjee %A Martin Chmelík %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-chatterjee13a %I PMLR %P 65--74 %U https://proceedings.mlr.press/r11/chatterjee13a.html %V R11 %X We consider partially observable Markov decision processes (POMDPs) with limit- average payoff, where a reward value in the interval [0, 1] is associated to every transi- tion, and the payoffof an infinite path is the long-run average of the rewards. We con- sider two types of path constraints: (i) quan- titative constraint defines the set of paths where the payoffis at least a given thresh- old $\lambda$1 $\in$(0, 1]; and (ii) qualitative constraint which is a special case of quantitative con- straint with $\lambda$1 = 1. We consider the compu- tation 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 constraint 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 constraint we show that the problem of deciding the existence of a finite-memory controller is undecidable. %Z Reissued by PMLR on 04 October 2026.
APA
Chatterjee, K. & Chmelík, M.. (2013). POMDPs under Probabilistic Semantics. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:65-74 Available from https://proceedings.mlr.press/r11/chatterjee13a.html. Reissued by PMLR on 04 October 2026.

Related Material