Optimal Cost Almost-sure Reachability in POMDPs
  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.
