# What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2013.

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

- [Beyond Preferences in AI Alignment](https://mlsanity.com/paper/2408.16984/) (2024)
- [The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs](https://mlsanity.com/paper/2110.07409/) (2021)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Compositional Shielding and Reinforcement Learning for Multi-Agent Systems](https://mlsanity.com/paper/2410.10460/) (2024)
- [Learning Explainable and Better Performing Representations of POMDP Strategies](https://mlsanity.com/paper/2401.07656/) (2024)
- [On the Computational Complexity of Ethics: Moral Tractability for Minds and Machines](https://mlsanity.com/paper/2302.04218/) (2023)
- [Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives](https://mlsanity.com/paper/2412.12063/) (2024)
- [Adversarial Intent is a Latent Variable: Stateful Trust Inference for Securing Multimodal Agentic RAG](https://mlsanity.com/paper/2602.21447/) (2026)
- [A Theory of Bounded Inductive Rationality](https://mlsanity.com/paper/2307.05068/) (2023)
- [Computing the Reachability Value of Posterior-Deterministic POMDPs](https://mlsanity.com/paper/2602.07473/) (2026)
- [On the Verification of Belief Programs](https://mlsanity.com/paper/2204.12562/) (2022)
- [Multi-Environment POMDPs with Finite-Horizon Objectives](https://mlsanity.com/paper/2605.07537/) (2026)
- [Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives](https://mlsanity.com/paper/2605.12581/) (2026)
- [REBA: A Revealed Belief Automaton Framework for Online Planning in Continuous POMDPs](https://mlsanity.com/paper/2606.21971/) (2026)

## Abstract (arXiv)

We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives.