mlsanityData to 14 Oct 2026

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

arXiv 2608.24986 ↗First posted 25 Aug 2026cs.AIcited by 0

Not on the map. Why?

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.

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

21 of 50 references.

References · 21

  1. 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 174
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  3. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  4. 2016Safe Policy Improvement by Minimizing Robust Baseline Regretcited by 53
  5. 2017Reinforcement Learning under Model Mismatchcited by 52
  6. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 50
  7. 2020Robust Finite-State Controllers for Uncertain POMDPscited by 24
  8. 2023Robust Average-Reward Markov Decision Processescited by 22
  9. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meetcited by 18
  10. 2019Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguitycited by 15
  11. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  12. 2023Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimalitycited by 13
9 more
  1. 2020Solving Zero-Sum One-Sided Partially Observable Stochastic Gamescited by 12
  2. 2024Solving Robust Markov Decision Processes: Generic, Reliable, Efficientcited by 11
  3. 2023Solving Long-run Average Reward Robust MDPs via Stochastic Gamescited by 10
  4. 2024Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPscited by 7
  5. 2024Pessimistic Iterative Planning with RNNs for Robust POMDPscited by 7
  6. 2020Robust Policy Synthesis for Uncertain POMDPs via Convex Optimizationcited by 5
  7. 2025Robust Finite-Memory Policy Gradients for Hidden-Model POMDPscited by 5
  8. 2026Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPscited by 5
  9. 2025Qualitative Analysis of ω-Regular Objectives on Robust MDPscited by 2

Built on by

Not cited yet.