Computing the Reachability Value of Posterior-Deterministic POMDPs

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

Read Computing the Reachability Value of Posterior-Deterministic POMDPs by Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez, Pierre Vandenhove (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-07473.txt.

Description

Partially observable Markov decision processes model choices under uncertainty, but computing optimal reachability probabilities for them is known to be impossible in general. Nathanaël Fijalkow and four co-authors carve out a tractable class: posterior-deterministic POMDPs.

For that class, the best chance of reaching a target set can be estimated to any precision, in sharp contrast to the general no-method result. Verification and synthesis teams get a new island of solvable cases in POMDP theory, with a precise setting marking where estimates become possible. The new class thus opens checking problems that were out of reach before for partly observable systems.

Catalog record

CREATORNathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez, Pierre Vandenhove
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE128 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07473

Browse the full library · About the Tower of Babel