Optimal cost almost-sure reachability in POMDPs Conference Paper

Author(s): Chatterjee, Krishnendu; Chmelík, Martin; Gupta, Raghav; Kanodia, Ayush
Title: Optimal cost almost-sure reachability in POMDPs
Title Series: Artifical Intelligence
Affiliation IST Austria
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 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.
Keywords: approximation algorithms; POMDPs; Reachability objectives; Total cost
Conference Title: IAAI: Innovative Applications of Artificial Intelligence
Volume: 234
Conference Dates: January 25 - 30, 2015
Conference Location: Austin, TX, USA
ISBN: 978-157735700-1
Publisher: AAAI Press  
Date Published: 2016-05-01
Start Page: 26
End Page: 48
Sponsor: 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.
DOI: 10.1016/j.artint.2016.01.007
Open access: yes (repository)
IST Austria Authors
  1. Martin Chmelik
    23 Chmelik
Related IST Austria Work