---
_id: '1873'
abstract:
- lang: eng
text: '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.'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
citation:
ama: Chatterjee K, Chmelik M. POMDPs under probabilistic semantics. Artificial
Intelligence. 2015;221:46-72. doi:10.1016/j.artint.2014.12.009
apa: Chatterjee, K., & Chmelik, M. (2015). POMDPs under probabilistic semantics.
Artificial Intelligence. Elsevier. https://doi.org/10.1016/j.artint.2014.12.009
chicago: Chatterjee, Krishnendu, and Martin Chmelik. “POMDPs under Probabilistic
Semantics.” Artificial Intelligence. Elsevier, 2015. https://doi.org/10.1016/j.artint.2014.12.009.
ieee: K. Chatterjee and M. Chmelik, “POMDPs under probabilistic semantics,” Artificial
Intelligence, vol. 221. Elsevier, pp. 46–72, 2015.
ista: Chatterjee K, Chmelik M. 2015. POMDPs under probabilistic semantics. Artificial
Intelligence. 221, 46–72.
mla: 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.
short: K. Chatterjee, M. Chmelik, Artificial Intelligence 221 (2015) 46–72.
date_created: 2018-12-11T11:54:28Z
date_published: 2015-04-01T00:00:00Z
date_updated: 2021-01-12T06:53:46Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.artint.2014.12.009
external_id:
arxiv:
- '1408.2058'
intvolume: ' 221'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1408.2058
month: '04'
oa: 1
oa_version: Preprint
page: 46 - 72
publication: Artificial Intelligence
publication_status: published
publisher: Elsevier
publist_id: '5224'
quality_controlled: '1'
scopus_import: 1
status: public
title: POMDPs under probabilistic semantics
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2015'
...