Markow-Entscheidungsproblem

Bei dem Markow-Entscheidungsproblem (MEP, auch Markow-Entscheidungsprozess oder MDP für englisch Markov decision process) handelt es sich um ein Modell für Entscheidungsprobleme mit unsicheren Ergebnissen. Erstmalig beschrieben wurde das Modell 1957 von Richard Bellman. Seitdem findet es auf vielen Gebieten Beachtung, darunter Ökologie, Ökonomie, Gesundheitsversorgung, Telekommunikation und bestärkendes Lernen.

Der Name geht zurück auf die Markow-Kette, die der russische Mathematiker Andrei Andrejewitsch Markow im frühen 20. Jahrhundert untersucht hat. Eine Markow-Kette beschreibt einen stochastischen Prozess ohne Gedächtnis. Dieser Prozess hat eine vorgegebene Anzahl von Zuständen. Der Prozess wechselt zufällig von dem aktuellen Zustand in einen Folgezustand. Dabei gilt die Markow-Annahme: Die Wahrscheinlichkeit für einen Zustandsübergang hängt nur von dem aktuellen Zustand und dem Folgezustand ab und nicht von früheren Zustandsübergängen.

Der Markow-Entscheidungsprozess erweitert die Markow-Ketten um einen Agenten, der sich zwischen mehreren möglichen Aktionen entscheiden kann und positive oder negative Belohnungen als Rückmeldung erhält.

Übersicht

Das Modell eines Markow-Entscheidungsprozesses hat mehrere Zustände und mehrere Aktionen. Der Prozess befindet sich zum Zeitpunkt ${\displaystyle t}$ in einem bestimmten Zustand ${\displaystyle s=s_{t}}$. Dann führt eine Aktion ${\displaystyle a=a_{t}}$ dazu, dass der Prozess mit der Wahrscheinlichkeit ${\displaystyle p}$ zum Zeitpunkt ${\displaystyle t+1}$ einen bestimmten Folgezustand ${\displaystyle s'=s_{t+1}}$ erreicht. Dabei gilt die Markow-Annahme: Die Zustände haben kein Gedächtnis, d. h., die Wahrscheinlichkeit ${\displaystyle p}$ ist nur von den Zuständen ${\displaystyle s}$ und ${\displaystyle s'}$ abhängig und nicht von Vorgängern von ${\displaystyle s}$. Der Zustandsübergang kann zu einer positiven oder negativen Belohnung ${\displaystyle r(s,s')}$ führen.

Wenn alle Zustände, alle Aktionen und alle Übergangswahrscheinlichkeiten bekannt sind, kann die optimale Strategie für den Agenten mit dem Optimalitätsprinzip von Bellman berechnet werden. Eine Methode dazu ist die dynamische Programmierung, die auf Rückwärtsinduktion beruht.

Darauf bauen beispielsweise Methoden auf, die beim bestärkenden Lernen dazu eingesetzt werden, eine Strategie zu erlernen, mit der ein Software-Agent seine Aktionen so wählt, dass er von seiner Umwelt möglichst viele Belohnungen erhält.[1]:743–747

Formale Definition

Beispiel für ein einfaches MEP mit drei Zuständen (grüne Kreise), zwei Aktionen (orange Kreise) und zwei Belohnungen (orange Pfeile)

Ein MEP ist ein Tupel ${\displaystyle (S,A,T,r,p_{0})}$, wobei

• ${\displaystyle S}$ eine Menge von Zuständen,
• ${\displaystyle A}$ eine Menge von Aktionen,
• ${\displaystyle T}$ das Aktionsmodell (auch Transitionswahrscheinlichkeit) ${\displaystyle T\colon S\times A\times S\rightarrow [0,1]}$ ist, so dass ${\displaystyle T(s_{t},a_{t},s_{t+1})=p(s_{t+1}|s_{t},a_{t})}$ die Wahrscheinlichkeit ist, von Zustand ${\displaystyle s_{t}}$ durch Ausführen von Aktion ${\displaystyle a_{t}}$ in den Zustand ${\displaystyle s_{t+1}}$ zu gelangen.
• ${\displaystyle r\colon S\times A\times S\rightarrow \mathbb {R} }$ die Belohnungsfunktion ist, die allen Zustandsübergängen eine Belohnung zuordnet und
• ${\displaystyle p_{0}\colon S\rightarrow \mathbb {R} }$ die Startverteilung ist, die zu jedem Zustand angibt, wie wahrscheinlich es ist, in diesem Zustand zu starten.

Ein Agent wählt seine Aktionen mit Hilfe einer Strategie ${\displaystyle \pi }$ aus. Die Strategie ordnet jedem Zustand genau eine Aktion zu.

• ${\displaystyle \pi \colon S\rightarrow A;\pi (s_{t})=a_{t}}$

Optimale Strategie

Das Ziel ist, dass der Agent bei seinen Entscheidungen einer guten Strategie folgt: einer Funktion ${\displaystyle \pi }$, die für jeden Zustand ${\displaystyle s}$ bestimmt, welche Aktion ${\displaystyle \pi (s)}$ der Agent wählt. Wenn der Agent einer Strategie folgt, ist seine Aktion für jeden Zustand fest vorgegeben. Der Prozess verhält sich dann wie eine Markow-Kette.

Gesucht wird eine optimale Strategie ${\displaystyle \pi ^{*}}$, die den Gewinn maximiert, den der Agent durch seine Aktionen erreicht. Das Optimalitätsprinzip von Bellman besagt, dass eine optimale Strategie in jedem Zustand ${\displaystyle s}$ die Aktion ${\displaystyle a}$ wählt, bei der zukünftig der größte Gewinn zu erwarten ist.

Der zukünftig zu erwartende Gewinn wird auch kumulierter Reward genannt. Er wird in der Regel als Summe aller Belohnungen ${\displaystyle r}$ über unendlich viele Zustandsübergänge berechnet:

${\displaystyle \mathbb {E} [G_{t}]=\mathbb {E} \left[\sum _{i=0}^{\infty }\gamma ^{i}\cdot r_{t+i}\right]}$ mit ${\displaystyle 0\leq \gamma \leq 1}$

Dabei ist ${\displaystyle r_{t+i}}$ die Belohnung, die der Agent wahrscheinlich im Zeitschritt ${\displaystyle t+1}$ erhält. Der Diskontierungsfaktor ${\displaystyle \gamma }$ sorgt dafür, dass die Summe für kontinuierliche Probleme (unendlich viele Zustandsübergänge) gegen einen Grenzwert konvergiert. Für ${\displaystyle \gamma =0}$ zählt nur die direkte Belohnung einer Aktion, alle zukünftigen Belohnungen werden ignoriert.[2]:487–491 Typische Werte für ${\displaystyle \gamma }$ liegen zwischen 0,95 und 0,99.[1]:738

Beispiel

Bei einem deterministischen Markow-Entscheidungsproblem führt jede Aktion zu genau einem Folgezustand. Ein solches Problem liegt vor, wenn ein Roboter durch ein Labyrinth zu einem Ziel navigieren soll. Dabei entspricht die Menge der Zustände der Menge der möglichen Positionen des Roboters und die Aktionen sind Schritte des Roboters in verschiedene Richtungen. Die Belohnungen sind so gewählt, dass der Roboter für den letzten Schritt, mit der er das Ziel erreicht, eine große positive Belohnung erhält und er für alle anderen Schritte die gleiche kleine negative Belohnung erhält. Dadurch erhält der Roboter den höchsten kumulierten Reward, wenn er mit möglichst wenigen Schritten das Ziel erreicht.

Algorithmen

Die folgenden Algorithmen sind Beispiele dafür, wie mit der dynamischen Programmierung ein komplexes Problem iterativ gelöst werden kann. Sie können auf MEPs angewendet werden, bei denen die Anzahl von Zuständen und Aktionen endlich ist und alle Transaktionswahrscheinlichkeiten und Belohnungen bekannt sind. Für solche MEPs können sie eine optimale Strategie finden oder überprüfen. Sie bilden deshalb die mathematische Grundlage für eine Reihe von Algorithmen, die beim bestärkenden Lernen zum Lösen von ähnlichen Problemen eingesetzt werden.

Value-Iteration-Algorithmus

Das Optimalitätsprinzip von Bellman beschreibt den optimalen Wert des aktuellen Zustands als maximal zu erwartenden kumulierten Reward. Dieser Zustandswert entspricht der Summe aus der durchschnittlichen Belohnung, die im aktuellen Zustand mit der bestmöglichen Aktion erreicht wird und allen zukünftigen Belohnungen, die zu erwarten sind, wenn der Agent auch in allen Folgezuständen die jeweils bestmögliche Aktion ausführt.

Daraus hat Bellman eine rekursive Formel für den Value-Iteration-Algorithmus abgeleitet, mit dem man den optimalen Zustandswert für jeden möglichen Zustand abschätzen kann:

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\}}$ für alle ${\displaystyle s}$

Darin sind ${\displaystyle i}$ die Nummer des aktuellen Durchlaufs und ${\displaystyle V_{i+1}(s)}$ der geschätzte Zustandswert für ${\displaystyle s}$ im Durchlauf ${\displaystyle i+1}$. Der erste Durchlauf beginnt im Zustand ${\displaystyle s}$, mit ${\displaystyle i=0}$ und allen Schätzwerten auf ${\displaystyle 0}$. In jedem Durchlauf werden die Schätzungen ${\displaystyle V_{i+1}}$ für alle Zustände ${\displaystyle s}$ basierend auf den Schätzungen des vorigen Durchlaufs neu berechnet. Mit genügend Wiederholungen konvergieren die Schätzungen zu den Zustandswerten, die mit einer optimalen Strategie erreicht werden können.[1]:745,746

Q-Wert-Iterationsalgorithmus

Bellman fand auch eine Formel für einen ähnlichen Algorithmus, mit dem man die optimalen Zustands-Aktions-Werte, auch Q-Werte (Qualitätswerte) genannt, abschätzen kann:

${\displaystyle Q_{i+1}(s,a):=\sum _{s'}P_{a}(s,s')\left\{R_{a}(s,s')+\gamma \max _{a}\left(Q_{i}(s',a')\right)\right\}}$ für alle ${\displaystyle (s,a)}$

Weblinks

• PPT-Vortrag (englisch) (PDF; 739 kB)

Einzelnachweise

1. Aurélien Géron: Praxiseinstieg Machine Learning. 3. Auflage. dpunkt Verlag, Heidelberg 2023, ISBN 978-3-96009-212-4. 
2. Jörg Frochte: Maschinelles Lernen: Grundlagen und Algorithmen in Python (= Hanser eLibrary). 3., überarbeitete und erweiterte Auflage. Hanser, München 2021, ISBN 978-3-446-46144-4.