Posterior-Deterministic POMDPs Enable Reachability Approximation

Researchers have introduced posterior-deterministic partially observable Markov decision processes (POMDPs), a new class of models that overcomes a fundamental limitation of standard POMDPs. While the seminal result of Madani et al. (2003) proved that computing or approximating the maximal reachability probability in general POMDPs is impossible, the new class allows approximation up to arbitrary precision. This contrasts with fully observable MDPs, where reachability is polynomial-time solvable. The work focuses on the theoretical contribution of defining posterior-deterministic POMDPs and proving their approximability, with implications for verification and synthesis under uncertainty.