---
res:
bibo_abstract:
- 'We consider partially observable Markov decision processes (POMDPs) with a set
of target states and an integer cost associated with every transition. The optimization
objective we study asks to minimize the expected total cost of reaching a state
in the target set, while ensuring that the target set is reached almost surely
(with probability 1). We show that for integer costs approximating the optimal
cost is undecidable. For positive costs, our results are as follows: (i) we establish
matching lower and upper bounds for the optimal cost, both double exponential
in the POMDP state space size; (ii) we show that the problem of approximating
the optimal cost is decidable and present approximation algorithms developing
on the existing algorithms for POMDPs with finite-horizon objectives. While the
worst-case running time of our algorithm is double exponential, we also present
efficient stopping criteria for the algorithm and show experimentally that it
performs well in many examples of interest.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Martin
foaf_name: Chmelik, Martin
foaf_surname: Chmelik
foaf_workInfoHomepage: http://www.librecat.org/personId=3624234E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Raghav
foaf_name: Gupta, Raghav
foaf_surname: Gupta
- foaf_Person:
foaf_givenName: Ayush
foaf_name: Kanodia, Ayush
foaf_surname: Kanodia
bibo_doi: 10.1016/j.artint.2016.01.007
bibo_volume: 234
dct_date: 2016^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: Optimal cost almost-sure reachability in POMDPs@
...