cs.AIFeb 7, 2026

Approximating the Reachability Value of Posterior-Deterministic POMDPs

Authors: Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez, Pierre Vandenhove

Organizations: LaBRI, CNRS, University of Bordeaux, France · University of Antwerp – Flanders Make, Belgium · UMONS – Universite de Mons, Belgium

Abstract

We introduce posterior-deterministic POMDPs, and we show that for this class of POMDPs, the maximal probability of reaching a given set of states can be approximated up to arbitrary precision. A POMDP is posterior-deterministic if the next state can be uniquely determined by the current state, the action taken, and the observation received. In particular, once the current state is known, it remains known forever. The class contains, for instance, multiple-environment MDPs equipped with a prior distribution over the environments, quasi-deterministic POMDPs, and the episodic version of the classical Tiger POMDP (Kaelbling et al. 1998).

Figures & tables

Explore similar work

May 8, 2026

Multi-Environment POMDPs with Finite-Horizon Objectives

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. The extension is nontrivial: MEPOMDPs require reasoning about beliefs and payoffs across environments, and deterministic policies are no longer enough for optimal payoff. While the lower bound transfers immediately, the upper bound requires new techniques: we prove that mixtures of at most nn deterministic policies suffice for nn environments and show how to explore them without storing exponential-size policy descriptions. 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.
Aug 25, 2026

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.
Nov 6, 2026

Quasipolynomial-Time Planning for Decodable POMDPs

We study planning for finite-horizon partially observable Markov decision processes (POMDPs) with finite state, action, and observation spaces. Both exact and approximate planning are known to be computationally hard in this setting, so prior work has explored natural assumptions that make planning easier. Recent work [Golowich et al., 2022] gave quasipolynomial-time approximate planning algorithms for observable POMDPs. These are POMDPs whose observation channels satisfy an ℓ1\ell_1-observability condition, but notably, no assumptions are required on the transition dynamics. In a similar vein, for every fixed ρ>0ρ>0, we give quasipolynomial-time approximate planning algorithms for ρρ-decodable POMDPs. We show that decodability is implied by both ℓ1\ell_1- and ℓ2\ell_2-observability and is strictly weaker than observability. Moreover, we show that the optimal decodability constant can be computed in polynomial time, whereas computing the optimal ℓ1\ell_1-observability constant is NP-hard in the worst case. We also show that the fast filter-forgetting guarantee underlying the approach of [Golowich et al., 2022] does not extend directly from ℓ1\ell_1-observability to constant ℓ2\ell_2-observability. Thus, decodability is an easy-to-check, unifying assumption under which quasipolynomial-time approximate planning for POMDPs is possible.