Markov Decision Process (MDP)

Ein Markow-Entscheidungsprozess (MDP) ist das mathematische Modell eines sequenziellen Entscheidungsproblems: Ein Agent beobachtet einen Zustand, wählt eine Aktion, erhält eine Belohnung und gelangt in einen Folgezustand, der teilweise von seiner Wahl und teilweise vom Zufall abhängt. Formal besteht ein MDP aus einer Menge von Zuständen, einer Menge von Aktionen, Übergangswahrscheinlichkeiten P(s′ | s, a), einer Belohnungsfunktion R(s, a) und üblicherweise einem Diskontfaktor γ zwischen 0 und 1. Es zu lösen bedeutet, eine Strategie zu finden, die in jedem Zustand eine Aktion auswählt und die erwartete abgezinste Summe künftiger Belohnungen maximiert. MDPs gingen aus der Operationsforschung der 1950er-Jahre hervor. Richard Bellmans dynamische Programmierung lieferte die Verfahren zu ihrer Lösung. Heute bilden MDPs die Standardformulierung für bestärkendes Lernen (RL).

Die Markow-Eigenschaft#

Die entscheidende Annahme ist die Markow-Eigenschaft: Der nächste Zustand und die Belohnung hängen nur vom aktuellen Zustand und der aktuellen Aktion ab, nicht vom Weg dorthin. Damit fasst der Zustand alle relevanten Informationen für den Agenten zusammen. Bei einem bewegten Objekt verletzt ein einzelnes Kamerabild diese Annahme, da es zwar die Position, aber nicht die Geschwindigkeit zeigt. Deshalb übergab das DQN von DeepMind, das Atari-Spiele spielte, dem Netzwerk die letzten vier aufeinandergelegten Bilder, damit es Bewegungen erkennen konnte.

Kann der Agent den vollständigen Zustand nicht beobachten, etwa bei einem Roboter mit verrauschten oder verdeckten Sensoren, handelt es sich um einen teilweise beobachtbaren Markow-Entscheidungsprozess (POMDP). Der Agent handelt dann anhand einer Einschätzung des Zustands, die mit einem Filter oder einem rekurrenten Netzwerk aufrechterhalten wird, statt anhand des Zustands selbst.

Bestandteile eines MDP#

• Zustände: Die Situationen, in denen sich der Agent befinden kann, zum Beispiel die Gelenkwinkel eines Roboters und die Position des Objekts, nach dem er greift.
• Aktionen: Die in jedem Zustand verfügbaren Optionen. Der Aktionsraum kann diskret sein (links abbiegen, rechts abbiegen) oder kontinuierlich (ein Lenkwinkel in Grad).
• Übergangswahrscheinlichkeiten: Die Wahrscheinlichkeit jedes Folgezustands nach einer Aktion. Sie bildet rutschende Räder, andere Fahrer und alle weiteren Zufallsquellen ab.
• Belohnungen: Die unmittelbare numerische Rückmeldung für einen Übergang. Die Wahl der Belohnungen durch den Entwickler definiert die Aufgabe. Eine unbedachte Gestaltung kann zu Belohnungsmanipulation führen.
• Diskontfaktor: Gibt an, wie stark künftige Belohnungen im Vergleich zu unmittelbaren zählen. Bei γ = 0.9 ist eine Belohnung in zehn Schritten 0.9¹⁰ ≈ 0.35 so viel wert wie dieselbe Belohnung jetzt.

In jedem Zeitschritt wiederholt sich dieselbe Interaktion, bis die Episode endet:

Ein MDP lösen#

Der Wert eines Zustands ist die erwartete Rendite ab diesem Zustand unter einer Strategie. Die optimalen Werte erfüllen die Bellman-Gleichung: Der Wert jedes Zustands entspricht der unmittelbaren Belohnung der besten Aktion zuzüglich des abgezinsten, nach Wahrscheinlichkeit gewichteten Werts der Zustände, in die sie führt. Sind die Übergangswahrscheinlichkeiten und Belohnungen bekannt, löst die dynamische Programmierung diese Gleichung direkt. Die Wertiteration (Bellman, 1957) wendet sie wiederholt an, bis sich die Werte nicht mehr ändern. Die Strategieiteration (Howard, 1960) wechselt zwischen der Bewertung und der Verbesserung einer Strategie.

Dieses NumPy-Beispiel führt Wertiteration für den Recyclingroboter aus Sutton und Bartos Reinforcement Learning: An Introduction aus. Der Roboter muss bei hohem oder niedrigem Akkustand entscheiden, ob er nach Dosen sucht, wartet oder den Akku auflädt:

import numpy as np

# # MDP des Recyclingroboters: Zustände 0 = hoher Akkustand, 1 = niedriger Akkustand; Aktionen 0 = suchen, 1 = warten, 2 = aufladen
gamma = 0.9  # # Diskontfaktor
P = np.zeros((2, 3, 2))  # # P[s, a, s'] = Wahrscheinlichkeit, nach Aktion a in Zustand s den Zustand s' zu erreichen
P[0, 0] = [0.7, 0.3]  # # Bei hohem Akkustand kann die Suche den Akku auf einen niedrigen Stand entladen
P[1, 0] = [0.4, 0.6]  # # Bei niedrigem Akkustand kann die Suche den Akku vollständig entladen (der Roboter wird gerettet und aufgeladen)
P[:, 1] = np.eye(2)  # # Warten lässt den Akkustand unverändert
P[:, 2] = [1.0, 0.0]  # # Aufladen stellt den hohen Akkustand immer wieder her
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # # Erwartungswert R[s, a]; Suche bei niedrigem Akkustand: 0.6 * 2 + 0.4 * -3 = 0

# # Wertiteration: Bellman-Optimalitätsaktualisierung anwenden, bis sich die Werte nicht mehr ändern
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # # Wert jeder Aktion in jedem Zustand
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Das Programm gibt Werte von 15.75 bei hohem und 14.17 bei niedrigem Akkustand sowie eine Strategie aus, die bei hohem Akkustand die Suche und bei niedrigem das Aufladen vorsieht. Wegen des 40%igen Risikos einer Rettungsstrafe von −3 lohnt sich die Suche bei niedrigem Akkustand weniger als das Aufladen.

Sind die Übergangswahrscheinlichkeiten unbekannt, schätzt das bestärkende Lernen dieselben Werte aus Erfahrung. Q-Learning aktualisiert Aktionswerte anhand beobachteter Übergänge, Policy-Gradient-Verfahren passen eine Strategie direkt an, und Deep Reinforcement Learning verwendet neuronale Netze, wenn sich der Zustandsraum nicht vollständig aufzählen lässt. Planungsverfahren wie die Monte-Carlo-Baumsuche lösen riesige MDPs während des Betriebs, indem sie nur die vom aktuellen Zustand aus erreichbaren Zukunftsverläufe simulieren.

MDPs und verwandte Modelle#

• Markow-Kette: Eine Folge von Zufallszuständen ohne Aktionen oder Belohnungen. Ein MDP ergänzt diese um Wahlmöglichkeiten und ein Ziel.
• Verdecktes Markow-Modell (HMM): Eine Markow-Kette, deren Zustände nur über verrauschte Signale beobachtet werden. Ein POMDP verhält sich in gleicher Weise zu einem MDP.
• Mehrarmiger Bandit: Ein MDP mit nur einem Zustand, bei dem sich jede Aktion unabhängig von der Vergangenheit auszahlt.
• Bestärkendes Lernen: Die Gruppe von Verfahren, die durch Interaktion lernen, in einem MDP gute Aktionen auszuführen, ohne dessen Übergangswahrscheinlichkeiten vorgegeben zu bekommen.

Anwendungen#

• Robotik und Regelung: Greifen, Gehen und Navigation werden als MDPs formuliert. Die zugehörigen Strategien werden oft in Simulationen trainiert. Bei kamerabasierter Regelung kann ein Detektor wie Ultralytics YOLO26 den Zustand bereitstellen: Jedes Bild wird in eine kurze Liste von Objektklassen und Begrenzungsrahmenkoordinaten umgewandelt, die für die Strategie eine deutlich kleinere Eingabe darstellt als die Rohpixel.
• Training von Sprachmodellen: RLHF und RLVR behandeln die Texterzeugung als MDP, dessen Zustand aus der Eingabeaufforderung und den bisherigen Tokens besteht, dessen Aktion das nächste Token ist und dessen Belohnung nach Fertigstellung der Antwort erfolgt.
• Operationsforschung: Nachbestellung von Lagerbeständen, Gerätewartung und dynamische Preisgestaltung sind klassische MDPs. Ronald Howard entwickelte die Strategieiteration, als er den Versand der Sears-Kataloge optimierte.