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