--- _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' ...