# What should be observed for optimal reward in POMDPs?

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 29 references that are in the map.
- First posted on arXiv 17 May 2024.

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

- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Parameter Synthesis for Markov Models: Covering the Parameter Space](https://mlsanity.com/paper/1903.07993/) (2019)
- [Synthesis in pMDPs: A Tale of 1001 Parameters](https://mlsanity.com/paper/1803.02884/) (2018)
- [Parameter Synthesis in Markov Models: A Gentle Survey](https://mlsanity.com/paper/2207.06801/) (2022)
- [Sensor Synthesis for POMDPs with Reachability Objectives](https://mlsanity.com/paper/1710.00675/) (2017)

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

- [Robustness Analysis of POMDP Policies to Observation Perturbations](https://mlsanity.com/paper/2604.21256/) (2026)
- [Scaling Observation-aware Planning in Uncertain Domains](https://mlsanity.com/paper/2605.22364/) (2026)

## Abstract (arXiv)

Partially observable Markov Decision Processes (POMDPs) are a standard model for agents making decisions in uncertain environments. Most work on POMDPs focuses on synthesizing strategies based on the available capabilities. However, system designers can often control an agent's observation capabilities, e.g. by placing or selecting sensors. This raises the question of how one should select an agent's sensors cost-effectively such that it achieves the desired goals. In this paper, we study the novel optimal observability problem OOP: Given a POMDP M, how should one change M's observation capabilities within a fixed budget such that its (minimal) expected reward remains below a given threshold? We show that the problem is undecidable in general and decidable when considering positional strategies only. We present two algorithms for a decidable fragment of the OOP: one based on optimal strategies of M's underlying Markov decision process and one based on parameter synthesis with SMT. We report promising results for variants of typical examples from the POMDP literature.