# Enforcing Almost-Sure Reachability in POMDPs

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

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

- [Safe Reinforcement Learning via Shielding under Partial Observability](https://mlsanity.com/paper/2204.00755/) (2022)
- [Safe Reinforcement Learning via Probabilistic Logic Shields](https://mlsanity.com/paper/2303.03226/) (2023)
- [COOL-MC: A Comprehensive Tool for Reinforcement Learning and Model Checking](https://mlsanity.com/paper/2209.07133/) (2022)
- [Safe POMDP Online Planning via Shielding](https://mlsanity.com/paper/2309.10216/) (2023)
- [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)
- [Shielding in Resource-Constrained Goal POMDPs](https://mlsanity.com/paper/2211.15349/) (2022)
- [Task-Guided Inverse Reinforcement Learning Under Partial Information](https://mlsanity.com/paper/2105.14073/) (2021)
- [Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives](https://mlsanity.com/paper/2412.12063/) (2024)
- [Compositional shield synthesis for safe reinforcement learning in partial observability](https://mlsanity.com/paper/2509.12085/) (2025)
- [Task-Guided IRL in POMDPs that Scales](https://mlsanity.com/paper/2301.01219/) (2022)
- [Explainable Representation of Finite-Memory Policies for POMDPs using Decision Trees](https://mlsanity.com/paper/2411.13365/) (2024)
- [Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives](https://mlsanity.com/paper/2605.12581/) (2026)
- [Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning](https://mlsanity.com/paper/2605.14440/) (2026)

## Abstract (arXiv)

Partially-Observable Markov Decision Processes (POMDPs) are a well-known stochastic model for sequential decision making under limited information. We consider the EXPTIME-hard problem of synthesising policies that almost-surely reach some goal state without ever visiting a bad state. In particular, we are interested in computing the winning region, that is, the set of system configurations from which a policy exists that satisfies the reachability specification. A direct application of such a winning region is the safe exploration of POMDPs by, for instance, restricting the behavior of a reinforcement learning agent to the region. We present two algorithms: A novel SAT-based iterative approach and a decision-diagram based alternative. The empirical evaluation demonstrates the feasibility and efficacy of the approaches.