# Robust Finite-State Controllers for Uncertain POMDPs

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

## Key facts

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

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

- [Safe Reinforcement Learning via Shielding under Partial Observability](https://mlsanity.com/paper/2204.00755/) (2022)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Robust Anytime Learning of Markov Decision Processes](https://mlsanity.com/paper/2205.15827/) (2022)
- [Robust Gymnasium: A Unified Modular Benchmark for Robust Reinforcement Learning](https://mlsanity.com/paper/2502.19652/) (2025)
- [Safe Policy Improvement for POMDPs via Finite-State Controllers](https://mlsanity.com/paper/2301.04939/) (2023)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [More for Less: Safe Policy Improvement With Stronger Performance Guarantees](https://mlsanity.com/paper/2305.07958/) (2023)
- [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)
- [Abstraction-Refinement for Hierarchical Probabilistic Models](https://mlsanity.com/paper/2206.02653/) (2022)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Policy Learning for Robust Markov Decision Process with a Mismatched Generative Model](https://mlsanity.com/paper/2203.06587/) (2022)
- [Learning Explainable and Better Performing Representations of POMDP Strategies](https://mlsanity.com/paper/2401.07656/) (2024)
- [Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability](https://mlsanity.com/paper/2510.23744/) (2025)
- [Constrained and Robust Policy Synthesis with Satisfiability-Modulo-Probabilistic-Model-Checking](https://mlsanity.com/paper/2511.08078/) (2025)
- [Robust Active Measuring under Model Uncertainty](https://mlsanity.com/paper/2312.11227/) (2023)
- [Finite-State Controllers for (Hidden-Model) POMDPs using Deep Reinforcement Learning](https://mlsanity.com/paper/2602.08734/) (2026)
- [Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning](https://mlsanity.com/paper/2105.01225/) (2021)
- [Capacity-Constrained Continual Learning](https://mlsanity.com/paper/2507.21479/) (2025)
- [Robustness Analysis of POMDP Policies to Observation Perturbations](https://mlsanity.com/paper/2604.21256/) (2026)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)
- [On the Complexity Gap Between POMDPs and Multi-Environment POMDPs](https://mlsanity.com/paper/2610.15010/) (2026)

## Abstract (arXiv)

Uncertain partially observable Markov decision processes (uPOMDPs) allow the probabilistic transition and observation functions of standard POMDPs to belong to a so-called uncertainty set. Such uncertainty, referred to as epistemic uncertainty, captures uncountable sets of probability distributions caused by, for instance, a lack of data available. We develop an algorithm to compute finite-memory policies for uPOMDPs that robustly satisfy specifications against any admissible distribution. In general, computing such policies is theoretically and practically intractable. We provide an efficient solution to this problem in four steps. (1) We state the underlying problem as a nonconvex optimization problem with infinitely many constraints. (2) A dedicated dualization scheme yields a dual problem that is still nonconvex but has finitely many constraints. (3) We linearize this dual problem and (4) solve the resulting finite linear program to obtain locally optimal solutions to the original problem. The resulting problem formulation is exponentially smaller than those resulting from existing methods. We demonstrate the applicability of our algorithm using large instances of an aircraft collision-avoidance scenario and a novel spacecraft motion planning case study.