Earlier Version

Optimal cost almost-sure reachability in POMDPs

1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Optimal Cost Almost-Sure Reachability in POMDPs, IST Austria, 2014.

Download
OA IST-2014-307-v1+1_main.pdf 2.73 MB
Restricted IST-2014-307-v1+2_authors.txt
Technical Report | Published | English

Scopus indexed
Author
Anonymous, 1; Anonymous, 2; Anonymous, 3; Anonymous, 4
Series Title
IST Austria Technical Report
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 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.
Publishing Year
Date Published
2014-09-09
Page
22
ISSN
IST-REx-ID

Cite this

Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Optimal Cost Almost-Sure Reachability in POMDPs. IST Austria; 2014.
Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2014). Optimal cost almost-sure reachability in POMDPs. IST Austria.
Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Optimal Cost Almost-Sure Reachability in POMDPs. IST Austria, 2014.
1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Optimal cost almost-sure reachability in POMDPs. IST Austria, 2014.
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2014. Optimal cost almost-sure reachability in POMDPs, IST Austria, 22p.
Anonymous, 1, et al. Optimal Cost Almost-Sure Reachability in POMDPs. IST Austria, 2014.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
b9668a70d53c550b3cd64f0c77451c3d
File Name
IST-2014-307-v1+2_authors.txt 117 bytes
Access Level
Restricted Closed Access
Date Uploaded
2019-04-16
MD5 Checksum
808ada1dddecc48ca041526fcc6a9efd


Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar