Partially observable Markov decision process (kurz POMDP, deutsch etwa „partiell beobachtbarer Markow-Entscheidungsprozess“) bezeichnet ein mathematisches Modell für sequentielle Entscheidungen unter Unsicherheit. Ein POMDP erweitert einen Markow-Entscheidungsprozess um den Fall, dass der tatsächliche Zustand eines Systems nicht direkt beobachtet werden kann.^[1] Stattdessen erhält der handelnde Agent Beobachtungen, die nur probabilistisch mit dem verborgenen Zustand zusammenhängen. POMDPs werden unter anderem in der künstlichen Intelligenz, der Robotik, dem Operations Research und der Entscheidungstheorie verwendet.^[2][3]

Ein frühes allgemeines Modell für die optimale Steuerung von Markow-Prozessen mit unvollständiger Zustandsinformation wurde 1965 von Karl Johan Åström beschrieben.^[4] Edward J. Sondik untersuchte Anfang der 1970er Jahre die optimale Steuerung partiell beobachtbarer Markow-Prozesse und formulierte zentrale Eigenschaften der zugehörigen Wertfunktionen.^[5] Richard D. Smallwood und Sondik behandelten 1973 den endlichen Planungshorizont und zeigten, dass die optimale Wertfunktion in diesem Fall stückweise linear und konvex über dem Wahrscheinlichkeitsraum der Zustände dargestellt werden kann.^[6] Für den unendlichen Planungshorizont mit diskontierten Kosten entwickelte Sondik 1978 eine entsprechende Theorie stationärer Politiken.^[7]

In den 1980er und 1990er Jahren wurden POMDPs verstärkt als allgemeines Modell für Planungsprobleme unter Unsicherheit untersucht. Überblicksarbeiten von Monahan und Lovejoy fassten frühe algorithmische Ansätze zusammen.^[2][8] Eine einflussreiche Darstellung für die künstliche Intelligenz stammt von Leslie Pack Kaelbling, Michael L. Littman und Anthony R. Cassandra aus dem Jahr 1998.^[1]

Ein diskreter POMDP wird häufig als Tupel

${\displaystyle (S,A,T,R,\Omega ,O,\gamma )}$

definiert.^[1] Dabei bezeichnet ${\displaystyle S}$ die Menge der möglichen Zustände, ${\displaystyle A}$ die Menge der möglichen Aktionen, ${\displaystyle T}$ die Übergangswahrscheinlichkeiten, ${\displaystyle R}$ die Belohnungsfunktion, ${\displaystyle \Omega }$ die Menge der möglichen Beobachtungen, ${\displaystyle O}$ das Beobachtungsmodell und ${\displaystyle \gamma }$ einen Diskontfaktor. Je nach Darstellung werden zusätzlich eine Anfangsverteilung über die Zustände und ein endlicher oder unendlicher Planungshorizont angegeben.^[3]

Befindet sich das System in einem Zustand ${\displaystyle s\in S}$ und führt der Agent eine Aktion ${\displaystyle a\in A}$ aus, so geht das System mit der Wahrscheinlichkeit

${\displaystyle T(s'\mid s,a)}$

in einen Folgezustand ${\displaystyle s'}$ über. Anschließend erhält der Agent eine Beobachtung ${\displaystyle o\in \Omega }$, deren Wahrscheinlichkeit durch

${\displaystyle O(o\mid s',a)}$

beschrieben wird. Die Belohnung ${\displaystyle R(s,a)}$ oder ${\displaystyle R(s,a,s')}$ bewertet die ausgeführte Aktion im jeweiligen Zustand.

Da der Zustand nicht direkt beobachtbar ist, verwendet der Agent eine Wahrscheinlichkeitsverteilung über die möglichen Zustände. Diese Verteilung wird als belief state oder Belief-Zustand bezeichnet. Ist ${\displaystyle b(s)}$ die Wahrscheinlichkeit, dass sich das System im Zustand ${\displaystyle s}$ befindet, dann ergibt sich nach Aktion ${\displaystyle a}$ und Beobachtung ${\displaystyle o}$ der neue Belief-Zustand zu

${\displaystyle b'(s')=\eta \,O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$,

wobei ${\displaystyle \eta }$ eine Normierungskonstante ist.^[1] Der Belief-Zustand enthält damit die für die weitere Planung relevante Information aus der bisherigen Aktions- und Beobachtungsgeschichte.

Ein Beispiel ist die Zuteilung zweier Arbeiten an zwei Beschäftigte unter unvollständiger Information. Ein Planer soll eine wichtige Arbeit ${\displaystyle j_{1}}$ und eine nachrangige Arbeit ${\displaystyle j_{2}}$ den Beschäftigten ${\displaystyle w_{1}}$ und ${\displaystyle w_{2}}$ zuweisen. Der Planer weiß zunächst nicht, welcher Beschäftigte für die wichtige Arbeit besser geeignet ist. Der verborgene Zustand sei

${\displaystyle S=\{s_{1},s_{2},s_{T}\}}$,

wobei ${\displaystyle s_{1}}$ bedeutet, dass ${\displaystyle w_{1}}$ für ${\displaystyle j_{1}}$ besser geeignet ist, und ${\displaystyle s_{2}}$, dass ${\displaystyle w_{2}}$ für ${\displaystyle j_{1}}$ besser geeignet ist. Der Zustand ${\displaystyle s_{T}}$ bezeichnet einen terminalen Zustand, in dem die Arbeit abgeschlossen ist. Der Anfangs-Belief sei

${\displaystyle b(s_{1})=0{,}5,\quad b(s_{2})=0{,}5,\quad b(s_{T})=0.}$

Der Planer nimmt damit vor der ersten Entscheidung an, dass beide Beschäftigte mit gleicher Wahrscheinlichkeit besser für die wichtige Arbeit geeignet sind.

Die Aktionsmenge bestehe aus drei Aktionen:

${\displaystyle A=\{a_{1},a_{2},a_{3}\}.}$

Dabei bezeichnet ${\displaystyle a_{1}}$ die Zuweisung ${\displaystyle w_{1}\mapsto j_{1}}$ und ${\displaystyle w_{2}\mapsto j_{2}}$. Die Aktion ${\displaystyle a_{2}}$ bezeichnet die Zuweisung ${\displaystyle w_{2}\mapsto j_{1}}$ und ${\displaystyle w_{1}\mapsto j_{2}}$. Die Aktion ${\displaystyle a_{3}}$ steht für eine kurze Prüfung oder Rückfrage, bei der noch keine Arbeit abgeschlossen wird, die aber zusätzliche Information über die Eignung der Beschäftigten liefert.

Die Belohnungsfunktion könne so gewählt werden, dass die korrekte Besetzung der wichtigen Arbeit ${\displaystyle 10}$ Punkte bringt, die Bearbeitung der nachrangigen Arbeit ${\displaystyle 2}$ Punkte und eine Fehlbesetzung der wichtigen Arbeit keine Punkte. Damit gilt für die beiden Zuweisungsaktionen

${\displaystyle R(s_{1},a_{1})=12,\quad R(s_{1},a_{2})=2,}$

${\displaystyle R(s_{2},a_{1})=2,\quad R(s_{2},a_{2})=12.}$

Die Prüfaktion habe eine unmittelbare Belohnung von ${\displaystyle 0}$:

${\displaystyle R(s_{1},a_{3})=R(s_{2},a_{3})=0.}$

Die Übergangswahrscheinlichkeiten seien so definiert, dass eine direkte Zuweisung die Aufgabe abschließt und in den terminalen Zustand führt:

${\displaystyle T(s_{T}\mid s_{1},a_{1})=T(s_{T}\mid s_{1},a_{2})=T(s_{T}\mid s_{2},a_{1})=T(s_{T}\mid s_{2},a_{2})=1.}$

Die Prüfaktion verändert den verborgenen Eignungszustand nicht:

${\displaystyle T(s_{1}\mid s_{1},a_{3})=1,\quad T(s_{2}\mid s_{2},a_{3})=1.}$

Als Beobachtungen seien

${\displaystyle \Omega =\{{\text{Hinweis auf }}w_{1},{\text{Hinweis auf }}w_{2},{\text{abgeschlossen}}\}}$

gegeben. Bei der Prüfaktion gebe das Beobachtungsmodell mit Wahrscheinlichkeit ${\displaystyle 0{,}9}$ einen Hinweis auf den tatsächlich besser geeigneten Beschäftigten und mit Wahrscheinlichkeit ${\displaystyle 0{,}1}$ einen falschen Hinweis:

${\displaystyle O({\text{Hinweis auf }}w_{1}\mid s_{1},a_{3})=0{,}9,\quad O({\text{Hinweis auf }}w_{2}\mid s_{1},a_{3})=0{,}1,}$

${\displaystyle O({\text{Hinweis auf }}w_{2}\mid s_{2},a_{3})=0{,}9,\quad O({\text{Hinweis auf }}w_{1}\mid s_{2},a_{3})=0{,}1.}$

Nach einer direkten Zuweisung werde die Beobachtung „abgeschlossen“ ausgegeben.

Bei einem Planungshorizont von einem Schritt ergeben sich die erwarteten Werte der beiden direkten Zuweisungen zu

${\displaystyle Q(b,a_{1})=0{,}5\cdot 12+0{,}5\cdot 2=7}$

und

${\displaystyle Q(b,a_{2})=0{,}5\cdot 2+0{,}5\cdot 12=7.}$

Die Prüfaktion hat bei einem Ein-Schritt-Horizont den unmittelbaren Wert

${\displaystyle Q(b,a_{3})=0.}$

Für einen einzelnen Entscheidungsschritt sind die beiden direkten Zuweisungen daher gleichwertig und der Prüfaktion vorzuziehen.

Bei einem längeren Planungshorizont kann die Prüfaktion dagegen vorteilhaft sein, weil sie den Belief-Zustand verändert. Wird ${\displaystyle a_{3}}$ ausgeführt und der Hinweis „${\displaystyle w_{1}}$ ist besser geeignet“ beobachtet, ergibt sich nach der Bayes-Regel

${\displaystyle b'(s_{1})={\frac {O({\text{Hinweis auf }}w_{1}\mid s_{1},a_{3})b(s_{1})}{O({\text{Hinweis auf }}w_{1}\mid s_{1},a_{3})b(s_{1})+O({\text{Hinweis auf }}w_{1}\mid s_{2},a_{3})b(s_{2})}}={\frac {0{,}9\cdot 0{,}5}{0{,}9\cdot 0{,}5+0{,}1\cdot 0{,}5}}=0{,}9.}$

Wird dagegen der Hinweis „${\displaystyle w_{2}}$ ist besser geeignet“ beobachtet, ergibt sich

${\displaystyle b'(s_{1})={\frac {0{,}1\cdot 0{,}5}{0{,}1\cdot 0{,}5+0{,}9\cdot 0{,}5}}=0{,}1.}$

Nach der Prüfaktion ist der Planer daher mit hoher Wahrscheinlichkeit über den besser geeigneten Beschäftigten informiert. Für einen Planungshorizont von zwei Schritten mit Diskontfaktor ${\displaystyle \gamma }$ ergibt sich der Wert der Prüfaktion aus dem erwarteten Wert der anschließenden Zuweisung:

${\displaystyle Q(b,a_{3})=0+\gamma \sum _{o\in \Omega }P(o\mid b,a_{3})V^{*}(\tau (b,a_{3},o)).}$

Da die Hinweise „${\displaystyle w_{1}}$“ und „${\displaystyle w_{2}}$“ bei neutralem Anfangs-Belief jeweils mit Wahrscheinlichkeit ${\displaystyle 0{,}5}$ auftreten, ergibt sich nach einer Prüfung in beiden Fällen ein erwarteter Wert von

${\displaystyle 0{,}9\cdot 12+0{,}1\cdot 2=11.}$

Damit gilt für die Prüfaktion

${\displaystyle Q(b,a_{3})=11\gamma .}$

Bei einem Diskontfaktor von beispielsweise ${\displaystyle \gamma =0{,}9}$ ergibt sich

${\displaystyle Q(b,a_{3})=9{,}9.}$

Unter diesen Zahlen ist die Prüfaktion bei einem Zwei-Schritt-Horizont besser als eine sofortige Zuweisung mit dem Wert ${\displaystyle 7}$. Das Beispiel zeigt, dass eine optimale Strategie in einem POMDP nicht notwendigerweise die Aktion mit der höchsten unmittelbaren erwarteten Belohnung wählt. Eine Aktion kann auch deshalb optimal sein, weil sie Informationen liefert und dadurch spätere Entscheidungen verbessert. Die Lösung des POMDP besteht folglich in einer Strategie, die jedem möglichen Belief-Zustand eine Aktion zuordnet.

Ein POMDP kann in einen vollständig beobachtbaren Markow-Entscheidungsprozess über dem Raum der Belief-Zustände überführt werden.^[7] Dieser Belief-Raum ist bei endlicher Zustandsmenge ein Simplex, also die Menge aller Wahrscheinlichkeitsverteilungen über ${\displaystyle S}$. Die erwartete unmittelbare Belohnung einer Aktion ${\displaystyle a}$ in einem Belief-Zustand ${\displaystyle b}$ ist

${\displaystyle r(b,a)=\sum _{s\in S}b(s)R(s,a)}$.

Für den diskontierten unendlichen Horizont kann die optimale Wertfunktion in der Form einer Bellman-Gleichung beschrieben werden:

${\displaystyle V^{*}(b)=\max _{a\in A}\left[r(b,a)+\gamma \sum _{o\in \Omega }P(o\mid b,a)V^{*}(\tau (b,a,o))\right]}$.

Dabei bezeichnet ${\displaystyle \tau (b,a,o)}$ die Aktualisierung des Belief-Zustands nach Aktion ${\displaystyle a}$ und Beobachtung ${\displaystyle o}$. Eine Politik ordnet entweder einer gesamten Aktions- und Beobachtungsgeschichte oder, in der Belief-Darstellung, einem Belief-Zustand eine Aktion zu.^[1]

Für endliche Horizonte ist die optimale Wertfunktion stückweise linear und konvex. Sie kann durch eine endliche Menge sogenannter ${\displaystyle \alpha }$-Vektoren dargestellt werden.^[6] Diese Eigenschaft bildet die Grundlage mehrerer exakter Lösungsverfahren.

Klassische exakte Verfahren für POMDPs beruhen auf dynamischer Programmierung, Wertiteration oder Policy Iteration. Bei endlichem Horizont können die stückweise linearen Wertfunktionen über Mengen von ${\displaystyle \alpha }$-Vektoren berechnet werden.^[6] Für den unendlichen diskontierten Horizont wurden Verfahren entwickelt, die Wertfunktionen oder stationäre Politiken iterativ verbessern.^[7]

Die exakte Lösung allgemeiner POMDPs ist rechnerisch aufwendig. Papadimitriou und Tsitsiklis zeigten, dass das finite-horizon-Problem für partiell beobachtbare Markow-Entscheidungsprozesse PSPACE-vollständig ist.^[9] Für bestimmte unendliche Horizonte und Zielkriterien sind Entscheidungsprobleme sogar unentscheidbar.^[10]

Aus diesem Grund werden in Anwendungen häufig approximative Verfahren eingesetzt. Dazu gehören gitterbasierte Approximationen des Belief-Raums, punktbasierte Wertiteration und heuristische Suchverfahren.^[8][11] Punktbasierte Verfahren berechnen Wertfunktionen nur auf einer ausgewählten Menge repräsentativer Belief-Zustände und können dadurch größere Zustandsräume behandeln als viele exakte Methoden.^[11]

POMDPs modellieren Entscheidungssituationen, in denen Handlungen sowohl die Entwicklung eines Systems als auch den Informationsstand des Agenten beeinflussen. Eine Aktion kann daher zugleich der Zielerreichung und der Informationsgewinnung dienen.^[1] Dies unterscheidet POMDPs von vielen einfacheren Entscheidungsmodellen, bei denen der relevante Zustand vollständig bekannt ist.

Anwendungen finden sich unter anderem in der mobilen Robotik, bei autonomer Navigation, in Wartungs- und Inspektionsproblemen, in der Qualitätskontrolle und in Planungsproblemen mit unsicheren Sensorinformationen.^[2][3] In der Robotik können POMDPs beispielsweise verwendet werden, wenn ein Roboter seine Position, die Lage von Hindernissen oder den Zustand seiner Umgebung nur über verrauschte Sensoren erschließen kann.^[3] In angewandten Bereichen wie Ökologie und werden POMDPs eingesetzt, um Entscheidungen unter unvollständiger Beobachtung des Systemzustands zu formulieren.^[12]

Ein POMDP verallgemeinert den Markow-Entscheidungsprozess. Wenn der aktuelle Zustand vollständig beobachtbar ist, reduziert sich das Modell auf einen gewöhnlichen Markow-Entscheidungsprozess.^[1] Ist dagegen keine aktive Entscheidungswahl vorhanden oder ist die Strategie fest vorgegeben, besteht eine enge Beziehung zu Hidden Markov Models, bei denen aus Beobachtungen auf verborgene Zustände geschlossen wird. Im Unterschied zu einem Hidden Markov Model steht beim POMDP jedoch die Wahl optimaler Aktionen im Vordergrund.

Von Reinforcement Learning unterscheidet sich ein POMDP zunächst dadurch, dass er ein Modell für die Entscheidungsaufgabe beschreibt. Reinforcement-Learning-Verfahren können auf POMDP-artige Probleme angewendet werden, müssen dann aber mit der partiellen Beobachtbarkeit umgehen, etwa durch Gedächtnis, Zustandsfilterung oder eine Belief-Repräsentation.^[3]

1. ↑ ^{a b c d e f g} Leslie Pack Kaelbling; Michael L. Littman; Anthony R. Cassandra: Planning and Acting in Partially Observable Stochastic Domains. In: Artificial Intelligence. Band 101, Nr. 1–2, 1998, S. 99–134, doi:10.1016/S0004-3702(98)00023-X (englisch). 
2. ↑ ^{a b c} George E. Monahan: State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms. In: Management Science. Band 28, Nr. 1, 1982, S. 1–16, doi:10.1287/mnsc.28.1.1 (englisch). 
3. ↑ ^{a b c d e} Matthijs T. J. Spaan: Partially Observable Markov Decision Processes. In: Marco Wiering; Martijn van Otterlo (Hrsg.): Reinforcement Learning: State-of-the-Art. Springer, Berlin/Heidelberg 2012, S. 387–414, doi:10.1007/978-3-642-27645-3_12 (englisch). 
4. ↑ Karl Johan Åström: Optimal Control of Markov Processes with Incomplete State Information. In: Journal of Mathematical Analysis and Applications. Band 10, Nr. 1, 1965, S. 174–205, doi:10.1016/0022-247X(65)90154-X (englisch). 
5. ↑ Edward J. Sondik: The Optimal Control of Partially Observable Markov Processes. Stanford University, Stanford 1971 (englisch, Dissertation). 
6. ↑ ^{a b c} Richard D. Smallwood; Edward J. Sondik: The Optimal Control of Partially Observable Markov Processes over a Finite Horizon. In: Operations Research. Band 21, Nr. 5, 1973, S. 1071–1088, doi:10.1287/opre.21.5.1071 (englisch). 
7. ↑ ^{a b c} Edward J. Sondik: The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs. In: Operations Research. Band 26, Nr. 2, 1978, S. 282–304, doi:10.1287/opre.26.2.282 (englisch). 
8. ↑ ^{a b} William S. Lovejoy: A Survey of Algorithmic Methods for Partially Observed Markov Decision Processes. In: Annals of Operations Research. Band 28, 1991, S. 47–65, doi:10.1007/BF02055574 (englisch). 
9. ↑ Christos H. Papadimitriou; John N. Tsitsiklis: The Complexity of Markov Decision Processes. In: Mathematics of Operations Research. Band 12, Nr. 3, 1987, S. 441–450, doi:10.1287/moor.12.3.441 (englisch). 
10. ↑ Omid Madani; Steve Hanks; Anne Condon: On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems. In: Proceedings of the Sixteenth National Conference on Artificial Intelligence. 1999, S. 541–548 (englisch). 
11. ↑ ^{a b} Joelle Pineau; Geoff Gordon; Sebastian Thrun: Point-Based Value Iteration: An Anytime Algorithm for POMDPs. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence. 2003, S. 1025–1030 (englisch). 
12. ↑ Iadine Chadès; Geoffrey G. Latombe; Makenzie A. Robinson; Jonathan M. Shaw; Tara G. Martin; Steven Possingham; Michael Bode: A Primer on Partially Observable Markov Decision Processes. In: Methods in Ecology and Evolution. Band 12, Nr. 11, 2021, S. 2058–2072, doi:10.1111/2041-210X.13692 (englisch).