Posterior-deterministische POMDPs: Erreichbarkeitswerte jetzt approximierbar

Partially observable Markov‑Decision‑Processes (POMDPs) bilden ein zentrales Modell für Entscheidungen unter Unsicherheit. Trotz ihrer Bedeutung bleiben viele Fragen zur Verifikation und Synthese für POMDPs unlösbar oder praktisch unhandhabbar. Insbesondere zeigte die Arbeit von Madani und Kollegen (2003), dass es keinen Algorithmus gibt, der die maximale Wahrscheinlichkeit, ein Zielzustand zu erreichen, berechnen oder sogar sinnvoll approximieren kann.

In einer neuen Veröffentlichung wird ein bislang unbekannter POMDP‑Typ vorgestellt: die posterior‑deterministischen POMDPs. Hier lässt sich der nächste Zustand eindeutig bestimmen, sobald man den aktuellen Zustand, die ausgeführte Aktion und die erhaltene Beobachtung kennt. Das bedeutet, dass der wahre Zustand, sobald er einmal bekannt ist, dauerhaft bekannt bleibt.

Der zentrale Beitrag der Studie ist die Beweisführung, dass für diese Klasse von POMDPs die maximale Erreichbarkeitswahrscheinlichkeit beliebig genau approximiert werden kann. Das ist ein bedeutender Fortschritt, denn für allgemeine POMDPs gilt das Gegenteil.

Die neue Klasse ist bemerkenswert breit: Sie umfasst sämtliche klassischen MDPs und bekannte Beispiele wie das Tiger‑POMDP. Damit stellt sie die größte bekannte Gruppe von POMDPs dar, für die die Erreichbarkeitswerte zuverlässig berechnet werden können.