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

Durgam Latha; Dion Reji; S. Akshay; Đorđe Žikelić; Shankaranarayanan Krishna

cs.AIAug 25, 2026

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

Authors: Durgam Latha, Dion Reji, S. Akshay, Đorđe Žikelić, Shankaranarayanan Krishna

Organizations: Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore

Abstract

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.

Figures & tables

	Sure Winning (Table 1)			Almost Sure Winning (Table 3)
	RMDP	1s RPOMDP	RPOMDP	RMDP	1s RPOMDP	RPOMDP
Safe	Linear-time	EXPTIME-c	EXPTIME-c	Linear-time	EXPTIME-c	EXPTIME-c
Reach	Linear-time	EXPTIME-c	EXPTIME-c	Linear-time	EXPTIME-c	Open
Büchi	Quad-time	EXPTIME-c	EXPTIME-c	Quad-time	EXPTIME-c	Open
co-Büchi	Quad-time	EXPTIME-c	EXPTIME-c	Quad-time	Undecidable	Undecidable
$\omega$ -regular	NP $\cap$ coNP	EXPTIME-c	EXPTIME-c	NP $\cap$ coNP	Undecidable	Undecidable

Table 1 : Summary of complexity results that follow from our equivalence of RPOMDPs and POSGs under

\omega

-regular objectives. We show results both for general

\omega

-regular objectives as well as for special instances of objectives (reachability, safety, Büchi, co-Büchi) for which more efficient algorithms are known. The ’-c’ suffix denotes completeness, otherwise shown results denote upper complexity bounds. The red colored entries are our novel results that were previously unknown and that follow from our equivalence result with POSGs ( Chatterjee et al., 2013 ) . The table considers RMDPs (full observability for both the agent and the environment), 1s RPOMDPs (partial observability for the agent only), and two-sided RPOMDPs (partial observability for both). The blue colored entries remain open problems since the decidability and complexity of solving POSGs under almost sure winning reachability and Büchi objectives is a well-known open problem ( Chatterjee et al., 2013 ) . The table numbers correspond to the tables in ( Chatterjee et al., 2013 ) from which the respective complexity results on POSGs were obtained. Turn-based quantitative stochastic parity games complexity results, from which we infer complexity results for quantitative analysis of RMDPs, were also derived in ( Chatterjee et al., 2004 ) .

Explore similar work

Multi-Environment POMDPs with Finite-Horizon Objectives
May 8, 2026Léonard Brice, Filip Cano, Krishnendu Chatterjee +2Partially Observable Markov Decision Process Markov Decision Processes
Institute of Science and Technology Austria
Robustness Analysis of POMDP Policies to Observation Perturbations
Apr 23, 2026Benjamin Kraske, Qi Heng Ho, Federico Rossi +2Partially Observable Markov Decision Process Non-Stationarity
University of Colorado Boulder, Boulder, Colorado, USA · Virginia Tech, Blacksburg, Virginia, USA · Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, USA
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Oct 1, 2026Han Zhong, Yinyu YeMarkov Decision Processes Linear Programming
Shanghai Jiao Tong University · Shanghai Jiao Tong University, SIMIS, and Stanford University

May 8, 2026, cs.AIJ/K move · Enter open · S save

Multi-Environment POMDPs with Finite-Horizon Objectives

Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger+1

Institute of Science and Technology Austria

Partially Observable Markov Decision Process Markov Decision Processes Objectives

Open paper AskPDF arXiv

Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.

Abstract

Explore similar work

Multi-Environment POMDPs with Finite-Horizon Objectives

Robustness Analysis of POMDP Policies to Observation Perturbations

Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes