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
| CREATOR | Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez, Pierre Vandenhove |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 128 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07473