Markow-Entscheidungsproblem

Grundidee des Modells

Das Markow-Entscheidungsproblem (MEP), auch Markow-Entscheidungsprozess oder MDP (englisch: Markov decision process), ist ein Modell für Entscheidungsprobleme mit unsicheren Ergebnissen. Es beschreibt eine Situation, in der sich ein Prozess in verschiedenen Zuständen befindet und ein Agent zwischen mehreren Aktionen wählen kann. Eine Aktion führt mit bestimmten Wahrscheinlichkeiten in einen Folgezustand. Als Rückmeldung erhält der Agent eine positive oder negative Belohnung.

Die Grundlage bildet die Markow-Annahme: Der Prozess hat kein Gedächtnis. Die Wahrscheinlichkeit für den nächsten Zustandsübergang hängt nur vom aktuellen Zustand, der gewählten Aktion und dem möglichen Folgezustand ab, nicht von früheren Zuständen oder Übergängen. Ohne Entscheidungsmöglichkeiten entspricht der Prozess einer Markow-Kette.

Ein MEP befindet sich zum Zeitpunkt t im Zustand s = sₜ. Der Agent wählt eine Aktion a = aₜ. Daraufhin erreicht der Prozess zum Zeitpunkt t + 1 mit der Wahrscheinlichkeit p einen Folgezustand s′ = sₜ₊₁. Der Übergang kann eine Belohnung r(s,s′) auslösen. Sind alle Zustände, Aktionen, Übergangswahrscheinlichkeiten und Belohnungen bekannt, lässt sich eine optimale Strategie berechnen. Dazu dient insbesondere die dynamische Programmierung, die auf Rückwärtsinduktion beruht. Die Grundidee wird auch im bestärkenden Lernen verwendet, bei dem ein Software-Agent durch Rückmeldungen eine Strategie erlernt, die möglichst viele Belohnungen erzielt.

Formale Bestandteile

Formal ist ein Markow-Entscheidungsprozess ein Tupel (S, A, T, r, p₀):

• S ist eine Menge von Zuständen.
• A ist eine Menge von Aktionen.
• T ist das Aktionsmodell beziehungsweise die Transitionswahrscheinlichkeit. Es ist definiert als T: S × A × S → [0,1]. Dabei gilt T(sₜ,aₜ,sₜ₊₁) = p(sₜ₊₁ | sₜ,aₜ). Dieser Wert gibt an, wie wahrscheinlich es ist, durch die Aktion aₜ vom Zustand sₜ in den Zustand sₜ₊₁ zu gelangen.
• r: S × A × S → ℝ ist die Belohnungsfunktion. Sie ordnet jedem Zustandsübergang eine reelle Belohnung zu.
• p₀: S → ℝ ist die Startverteilung. Sie gibt für jeden Zustand an, wie wahrscheinlich es ist, in diesem Zustand zu starten.

Der Agent wählt seine Aktionen mit einer Strategie π. In der beschriebenen Form ordnet die Strategie jedem Zustand genau eine Aktion zu: π: S → A; π(sₜ) = aₜ. Kennt man den aktuellen Zustand, steht die vom Agenten auszuführende Aktion damit fest.

Optimale Strategie und kumulierter Reward

Gesucht wird eine optimale Strategie π*, die den Gewinn des Agenten maximiert. Das Optimalitätsprinzip von Bellman besagt: Eine optimale Strategie wählt in jedem Zustand s diejenige Aktion a, für die zukünftig der größte Gewinn zu erwarten ist. Folgt der Agent einer festen Strategie, ist seine Aktion in jedem Zustand vorgegeben; der Prozess verhält sich dann wie eine Markow-Kette.

Der zukünftig erwartete Gewinn wird kumulierter Reward genannt. Er wird in der Regel als Summe aller Belohnungen über unendlich viele Zustandsübergänge berechnet:

E[Gₜ] = E[∑ᵢ₌₀^∞ γⁱ · rₜ₊ᵢ] mit 0 ≤ γ < 1.

Dabei bezeichnet rₜ₊ᵢ die Belohnung, die der Agent wahrscheinlich im Zeitschritt t + i erhält. Der Diskontierungsfaktor γ gewichtet kurzfristige Belohnungen stärker als spätere Belohnungen. Außerdem sorgt er dafür, dass die Summe bei kontinuierlichen Problemen mit unendlich vielen Zustandsübergängen gegen einen Grenzwert konvergiert. Für γ = 0 zählt nur die unmittelbare Belohnung einer Aktion; zukünftige Belohnungen werden ignoriert. Für γ → 1 erhalten zukünftige Belohnungen zunehmend mehr Gewicht. Typische Werte für γ liegen zwischen 0,95 und 0,99.

Beispiel: Roboter im Labyrinth

Bei einem deterministischen Markow-Entscheidungsproblem führt jede Aktion genau zu einem Folgezustand. Ein Beispiel ist ein Roboter, der durch ein Labyrinth zu einem Ziel navigiert.

Die Zustände entsprechen den möglichen Positionen des Roboters. Die Aktionen sind Schritte in verschiedene Richtungen. Für den letzten Schritt, mit dem der Roboter das Ziel erreicht, erhält er eine positive Belohnung. Durch den Diskontierungsfaktor γ wird der kumulierte Reward maximiert, wenn der Roboter das Ziel mit möglichst wenigen Schritten erreicht. Spätere Belohnungen werden dadurch geringer bewertet als frühere.

Value-Iteration-Algorithmus

Die Algorithmen zur Lösung eines MEP verwenden dynamische Programmierung und lösen das Problem iterativ. Sie sind auf MEPs mit endlich vielen Zuständen und Aktionen anwendbar, wenn alle Übergangswahrscheinlichkeiten und Belohnungen bekannt sind. Sie können für solche Probleme eine optimale Strategie finden oder überprüfen.

Beim Value-Iteration-Algorithmus wird der optimale Zustandswert als maximal zu erwartender kumulierter Reward verstanden. Er setzt sich aus der durchschnittlichen Belohnung zusammen, die im aktuellen Zustand mit der bestmöglichen Aktion erreicht wird, sowie aus allen zukünftigen Belohnungen, die zu erwarten sind, wenn in den Folgezuständen ebenfalls jeweils die bestmögliche Aktion gewählt wird.

Die rekursive Berechnung lautet:

Vᵢ₊₁(s) := maxₐ {∑ₛ′ Pₐ(s,s′) (Rₐ(s,s′) + γVᵢ(s′))} für alle s.

Dabei ist i die Nummer des aktuellen Durchlaufs und Vᵢ₊₁(s) der geschätzte Zustandswert im Durchlauf i + 1. Zu Beginn gilt i = 0; alle Schätzwerte werden auf 0 gesetzt. In jedem Durchlauf werden die Werte Vᵢ₊₁ für alle Zustände anhand der Werte des vorherigen Durchlaufs neu berechnet. Bei genügend vielen Wiederholungen konvergieren die Schätzungen zu den Zustandswerten, die mit einer optimalen Strategie erreicht werden können.

Q-Wert-Iterationsalgorithmus

Der Q-Wert-Iterationsalgorithmus schätzt nicht nur den Wert eines Zustands, sondern den Wert eines Zustands zusammen mit einer bestimmten Aktion. Diese optimalen Zustands-Aktions-Werte heißen Q-Werte oder Qualitätswerte.

Die rekursive Formel lautet:

Qᵢ₊₁(s,a) := ∑ₛ′ Pₐ(s,s′) {Rₐ(s,s′) + γ maxₐ (Qᵢ(s′,a′))} für alle (s,a).

Das Verfahren entspricht grundsätzlich dem Vorgehen der Value Iteration: Die Schätzungen werden in wiederholten Durchläufen anhand der Werte des vorherigen Durchlaufs aktualisiert. Sobald die optimalen Q-Werte gefunden sind, ist die optimale Strategie π*(s) bestimmt. Der Agent wählt dann in jedem Zustand die Aktion, die für diesen Zustand den höchsten Q-Wert besitzt. Beide Iterationsverfahren bilden damit eine mathematische Grundlage für Algorithmen des bestärkenden Lernens.