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

CardsList
  1. Multi-Environment POMDPs with Finite-Horizon Objectives

    May 8, 2026Léonard Brice, Filip Cano, Krishnendu Chatterjee +2Belief-Space PlanningMarkov Models

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

    Aug 25, 2026Durgam Latha, Dion Reji, S. Akshay +2Robust Markov Decision ProcessesPartially Observable Stochastic Games

  3. Quasipolynomial-Time Planning for Decodable POMDPs

    Nov 6, 2026Oliver Dobson, Varun Jog, Chun Hei Michael ShiuPartially Observable Markov Decision Processes