---
res:
bibo_abstract:
- ' We consider partially observable Markov decision processes (POMDPs) with a set
of target states and every transition is associated with an integer cost. The
optimization objective we study asks to minimize the expected total cost till
the target set is reached, 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 and the bound is double exponential;
(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: '1'
foaf_name: Anonymous, 1
foaf_surname: Anonymous
- foaf_Person:
foaf_givenName: '2'
foaf_name: Anonymous, 2
foaf_surname: Anonymous
- foaf_Person:
foaf_givenName: '3'
foaf_name: Anonymous, 3
foaf_surname: Anonymous
- foaf_Person:
foaf_givenName: '4'
foaf_name: Anonymous, 4
foaf_surname: Anonymous
dct_date: 2014^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2664-1690
dct_language: eng
dct_publisher: IST Austria@
dct_title: Optimal cost almost-sure reachability in POMDPs@
...