# Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 50 references that are in the map.
- First posted on arXiv 25 Aug 2026.

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

- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Safe Policy Improvement by Minimizing Robust Baseline Regret](https://mlsanity.com/paper/1607.03842/) (2016)
- [Reinforcement Learning under Model Mismatch](https://mlsanity.com/paper/1706.04711/) (2017)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguity](https://mlsanity.com/paper/1906.05988/) (2019)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)
- [Solving Zero-Sum One-Sided Partially Observable Stochastic Games](https://mlsanity.com/paper/2010.11243/) (2020)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Solving Long-run Average Reward Robust MDPs via Stochastic Games](https://mlsanity.com/paper/2312.13912/) (2023)
- [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)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPs](https://mlsanity.com/paper/2601.23229/) (2026)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)

## Abstract (arXiv)

Robust POMDPs (RPOMDPs) generalize classical POMDPs to the setting where exact transition probabilities are not known -- rather, they are only known to belong to some uncertainty set of values. In this work, we study the problem of solving RPOMDPs with general omega-regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under omega-regular objectives can be reduced to solving partially observable stochastic games (POSGs) under omega-regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs. This allows us to derive a range of new computational complexity results, including both upper and lower complexity bounds, on solving RPOMDPs with different omega-regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.