# Under-Approximating Expected Total Rewards in POMDPs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 53 references that are in the map.
- First posted on arXiv 21 Jan 2022.

## Builds on (most cited first, 13 of 13)

- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Enforcing Almost-Sure Reachability in POMDPs](https://mlsanity.com/paper/2007.00085/) (2020)
- [Optimal Cost Almost-sure Reachability in POMDPs](https://mlsanity.com/paper/1411.3880/) (2014)
- [Verification of indefinite-horizon POMDPs](https://mlsanity.com/paper/2007.00102/) (2020)
- [A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs](https://mlsanity.com/paper/1511.08456/) (2015)
- [Sound Value Iteration](https://mlsanity.com/paper/1804.05001/) (2018)
- [Counterexample-Guided Strategy Improvement for POMDPs Using Recurrent Neural Networks](https://mlsanity.com/paper/1903.08428/) (2019)
- [Bounded Model Checking for Probabilistic Programs](https://mlsanity.com/paper/1605.04477/) (2016)
- [Bounded Policy Synthesis for POMDPs with Safe-Reachability Objectives](https://mlsanity.com/paper/1801.09780/) (2018)
- [Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method](https://mlsanity.com/paper/1301.7417/) (2013)
- [Continuous-Time Markov Decisions based on Partial Exploration](https://mlsanity.com/paper/1807.09641/) (2018)

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

- [Learning Explainable and Better Performing Representations of POMDP Strategies](https://mlsanity.com/paper/2401.07656/) (2024)
- [Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives](https://mlsanity.com/paper/2406.02871/) (2024)
- [On the Verification of Belief Programs](https://mlsanity.com/paper/2204.12562/) (2022)
- [Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning](https://mlsanity.com/paper/2605.14440/) (2026)
- [Scaling Observation-aware Planning in Uncertain Domains](https://mlsanity.com/paper/2605.22364/) (2026)

## Abstract (arXiv)

We consider the problem: is the optimal expected total reward to reach a goal state in a partially observable Markov decision process (POMDP) below a given threshold? We tackle this -- generally undecidable -- problem by computing under-approximations on these total expected rewards. This is done by abstracting finite unfoldings of the infinite belief MDP of the POMDP. The key issue is to find a suitable under-approximation of the value function. We provide two techniques: a simple (cut-off) technique that uses a good policy on the POMDP, and a more advanced technique (belief clipping) that uses minimal shifts of probabilities between beliefs. We use mixed-integer linear programming (MILP) to find such minimal probability shifts and experimentally show that our techniques scale quite well while providing tight lower bounds on the expected total reward.