# Robustness Analysis of POMDP Policies to Observation Perturbations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 59 references that are in the map.
- First posted on arXiv 23 Apr 2026.

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

- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [A storm is Coming: A Modern Probabilistic Model Checker](https://mlsanity.com/paper/1702.04311/) (2017)
- [Trust-Aware Decision Making for Human-Robot Collaboration: Model Learning and Planning](https://mlsanity.com/paper/1801.04099/) (2018)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Parameter Synthesis for Markov Models: Covering the Parameter Space](https://mlsanity.com/paper/1903.07993/) (2019)
- [Parameter Synthesis for Markov Models: Faster Than Ever](https://mlsanity.com/paper/1602.05113/) (2016)
- [Parametric Markov Chains: PCTL Complexity and Fraction-free Gaussian Elimination](https://mlsanity.com/paper/1709.02093/) (2017)
- [Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications](https://mlsanity.com/paper/1409.3360/) (2014)
- [Verification of indefinite-horizon POMDPs](https://mlsanity.com/paper/2007.00102/) (2020)
- [Convex Optimization for Parameter Synthesis in MDPs](https://mlsanity.com/paper/2107.00108/) (2021)
- [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)
- [Robust Policy Synthesis for Uncertain POMDPs via Convex Optimization](https://mlsanity.com/paper/2001.08174/) (2020)
- [Intention-Aware Navigation in Crowds with Extended-Space POMDP Planning](https://mlsanity.com/paper/2206.10028/) (2022)
- [Sequential Decision-Making under Uncertainty: A Robust MDPs review](https://mlsanity.com/paper/2404.00940/) (2024)
- [What should be observed for optimal reward in POMDPs?](https://mlsanity.com/paper/2405.10768/) (2024)
- [A Finite-State Controller Based Offline Solver for Deterministic POMDPs](https://mlsanity.com/paper/2505.00596/) (2025)
- [Sensitivity of Filter Kernels and Robustness Bounds to Transition and Measurement Kernel Perturbations in Partially Observable Stochastic Control](https://mlsanity.com/paper/2508.10658/) (2025)
- [Explanation through Reward Model Reconciliation using POMDP Tree Search](https://mlsanity.com/paper/2305.00931/) (2023)
- [Contingency Planning Using Bi-level Markov Decision Processes for Space Missions](https://mlsanity.com/paper/2402.16342/) (2024)

## Abstract (arXiv)

Policies for Partially Observable Markov Decision Processes (POMDPs) are often designed using a nominal system model. In practice, this model can deviate from the true system during deployment due to factors such as calibration drift or sensor degradation, leading to unexpected performance degradation. This work studies policy robustness against deviations in the POMDP observation model. We introduce the Policy Observation Robustness Problem: to determine the maximum tolerable deviation in a POMDP's observation model that guarantees the policy's value remains above a specified threshold. We analyze two variants: the sticky variant, where deviations are dependent on state and actions, and the non-sticky variant, where they can be history-dependent. We show that the Policy Observation Robustness Problem can be formulated as a bi-level optimization problem in which the inner optimization is monotonic in the size of the observation deviation. This enables efficient solutions using root-finding algorithms in the outer optimization. For the non-sticky variant, we show that when policies are represented with finite-state controllers (FSCs) it is sufficient to consider observations which depend on nodes in the FSC rather than full histories. We present Robust Interval Search, an algorithm with soundness and convergence guarantees, for both the sticky and non-sticky variants. We show this algorithm has polynomial time complexity in the non-sticky variant and at most exponential time complexity in the sticky variant. We provide experimental results validating and demonstrating the scalability of implementations of Robust Interval Search to POMDP problems with tens of thousands of states. We also provide case studies from robotics and operations research which demonstrate the practical utility of the problem and algorithms.