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

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.