---
_id: '1529'
abstract:
- lang: eng
text: '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.'
acknowledgement: 'We thank Blai Bonet for helping us with RTDP-Bel. The research was
partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant
No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty
fellows award.'
article_processing_charge: No
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
- first_name: Raghav
full_name: Gupta, Raghav
last_name: Gupta
- first_name: Ayush
full_name: Kanodia, Ayush
last_name: Kanodia
citation:
ama: Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability
in POMDPs. Artificial Intelligence. 2016;234:26-48. doi:10.1016/j.artint.2016.01.007
apa: Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2016). Optimal cost
almost-sure reachability in POMDPs. Artificial Intelligence. Elsevier.
https://doi.org/10.1016/j.artint.2016.01.007
chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia.
“Optimal Cost Almost-Sure Reachability in POMDPs.” Artificial Intelligence.
Elsevier, 2016. https://doi.org/10.1016/j.artint.2016.01.007.
ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure
reachability in POMDPs,” Artificial Intelligence, vol. 234. Elsevier, pp.
26–48, 2016.
ista: Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2016. Optimal cost almost-sure
reachability in POMDPs. Artificial Intelligence. 234, 26–48.
mla: Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.”
Artificial Intelligence, vol. 234, Elsevier, 2016, pp. 26–48, doi:10.1016/j.artint.2016.01.007.
short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Artificial Intelligence
234 (2016) 26–48.
date_created: 2018-12-11T11:52:33Z
date_published: 2016-05-01T00:00:00Z
date_updated: 2023-02-23T12:25:49Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.artint.2016.01.007
ec_funded: 1
external_id:
arxiv:
- '1411.3880'
intvolume: ' 234'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1411.3880
month: '05'
oa: 1
oa_version: Preprint
page: 26 - 48
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Artificial Intelligence
publication_status: published
publisher: Elsevier
publist_id: '5642'
quality_controlled: '1'
related_material:
record:
- id: '1820'
relation: earlier_version
status: public
- id: '5425'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Optimal cost almost-sure reachability in POMDPs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 234
year: '2016'
...