[{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Optimal Cost Almost-Sure Reachability in POMDPs.” In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , 5:3496–3502. AAAI Press, 2015.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Optimal cost almost-sure reachability in POMDPs. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . IAAI: Innovative Applications of Artificial Intelligence, Artifical Intelligence, vol. 5, 3496–3502.","mla":"Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.” Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , vol. 5, AAAI Press, 2015, pp. 3496–502.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2015). Optimal cost almost-sure reachability in POMDPs. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (Vol. 5, pp. 3496–3502). Austin, TX, USA: AAAI Press.","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure reachability in POMDPs,” in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , Austin, TX, USA, 2015, vol. 5, pp. 3496–3502.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502."},"dini_type":"doc-type:conferenceObject","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Raghav","last_name":"Gupta"},{"last_name":"Kanodia","first_name":"Ayush"}],"publist_id":"5286","external_id":{"arxiv":[]},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"day":"01","dc":{"date":["2015"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"publisher":["AAAI Press"],"relation":["info:eu-repo/semantics/altIdentifier/arxiv/1411.3880","info:eu-repo/grantAgreement/FWF//P 23499-N23","info:eu-repo/grantAgreement/FWF//S 11407_N23","info:eu-repo/grantAgreement/EC/FP7/279307"],"source":["Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability in POMDPs. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . Vol 5. AAAI Press; 2015:3496-3502."],"description":["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 objec- tive 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 ap- proximation 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 present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples."],"identifier":["https://research-explorer.ista.ac.at/record/1820"],"title":["Optimal cost almost-sure reachability in POMDPs","Artifical Intelligence"],"creator":["Chatterjee, Krishnendu","Chmelik, Martin","Gupta, Raghav","Kanodia, Ayush"],"rights":["info:eu-repo/semantics/openAccess"],"language":["eng"]},"publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence ","date_published":"2015-06-01T00:00:00Z","date_created":"2018-12-11T11:54:11Z","uri_base":"https://research-explorer.ista.ac.at","page":"3496-3502","acknowledgement":" 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.","quality_controlled":"1","oa":1,"creator":{"id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","login":"kschuh"},"date_updated":"2023-02-23T10:02:57Z","department":[{"_id":"KrCh","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"_id":"1820","status":"public","type":"conference","conference":{"name":"IAAI: Innovative Applications of Artificial Intelligence","location":"Austin, TX, USA","end_date":"2015-01-30","start_date":"2015-01-25"},"language":[{}],"publication_status":"published","volume":5,"related_material":{"record":[{"status":"public","id":"1529","relation":"later_version"}]},"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng"}],"month":"06","intvolume":" 5","alternative_title":[],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1411.3880"}]}]