# Optimal Cost Almost-sure Reachability in POMDPs

arXiv: https://arxiv.org/abs/1411.3880 · HTML: https://mlsanity.com/paper/1411.3880/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2014.

## Built on by (most cited first, 12 of 12)

- [The Wasserstein Believer: Learning Belief Updates for Partially Observable Environments through Reliable Latent Space Models](https://mlsanity.com/paper/2303.03284/) (2023)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Pessimistic Iterative Planning with RNNs for Robust POMDPs](https://mlsanity.com/paper/2408.08770/) (2024)
- [Under-Approximating Expected Total Rewards in POMDPs](https://mlsanity.com/paper/2201.08772/) (2022)
- [Discrete-Event Controller Synthesis for Autonomous Systems with Deep-Learning Perception Components](https://mlsanity.com/paper/2202.03360/) (2022)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Shielding in Resource-Constrained Goal POMDPs](https://mlsanity.com/paper/2211.15349/) (2022)
- [A Finite-State Controller Based Offline Solver for Deterministic POMDPs](https://mlsanity.com/paper/2505.00596/) (2025)
- [Finite-State Controllers for (Hidden-Model) POMDPs using Deep Reinforcement Learning](https://mlsanity.com/paper/2602.08734/) (2026)
- [On the Verification of Belief Programs](https://mlsanity.com/paper/2204.12562/) (2022)
- [Explainable Representation of Finite-Memory Policies for POMDPs using Decision Trees](https://mlsanity.com/paper/2411.13365/) (2024)
- [Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs](https://mlsanity.com/paper/2605.12262/) (2026)

## Abstract (arXiv)

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.