thesis
Optimal cost almost-sure reachability in POMDPs
IST Austria Technical Report
published
1
Anonymous
author
2
Anonymous
author
3
Anonymous
author
4
Anonymous
author
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.
https://research-explorer.app.ist.ac.at/download/5425/5478/IST-2014-307-v1+1_main.pdf
application/pdfno
https://research-explorer.app.ist.ac.at/download/5425/6322/IST-2014-307-v1+2_authors.txt
text/plain
IST Austria2014
eng
2664-1690
22
https://research-explorer.app.ist.ac.at/record/1529
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. <i>Optimal Cost Almost-Sure Reachability in POMDPs</i>. IST Austria; 2014.
Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2014). <i>Optimal cost almost-sure reachability in POMDPs</i>. IST Austria.
Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. <i>Optimal Cost Almost-Sure Reachability in POMDPs</i>. IST Austria, 2014.
Anonymous, 1, et al. <i>Optimal Cost Almost-Sure Reachability in POMDPs</i>. IST Austria, 2014.
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2014. Optimal cost almost-sure reachability in POMDPs, IST Austria, 22p.
1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Optimal Cost Almost-Sure Reachability in POMDPs, IST Austria, 2014.
1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, <i>Optimal cost almost-sure reachability in POMDPs</i>. IST Austria, 2014.
54252018-12-12T11:39:15Z2021-01-12T08:02:08Z