Ein Markov-Entscheidungsprozess (englisch Markov Decision Process, kurz MDP) ist ein mathematisches Modell für sequenzielle Entscheidungen, bei denen jede Aktion einen Zustandswechsel mit unsicherem Ausgang auslöst und Belohnungen erst über die Zeit sichtbar werden. Er bildet die formale Grundlage des Reinforcement Learning.
Aufbau eines MDP
Ein MDP ist definiert als Tupel (S, A, P, R, γ): S ist die Menge der Zustände, A die Menge der Aktionen, P(s'|s,a) die Übergangswahrscheinlichkeit vom Zustand s in den Zustand s' unter Aktion a, R die Belohnungsfunktion und γ der Diskontierungsfaktor zwischen 0 und 1. Der Diskontierungsfaktor gewichtet zukünftige Belohnungen geringer als unmittelbare und sorgt bei unendlichen Horizonten für endliche Erwartungswerte.
Markov-Eigenschaft
Der Prozess heißt Markovsch, weil die Markov-Eigenschaft gilt: Die Wahrscheinlichkeit des nächsten Zustands hängt nur vom aktuellen Zustand und der gewählten Aktion ab, nicht von der gesamten Vorgeschichte. Der Zustand fasst damit alles relevante Wissen über die Vergangenheit zusammen. Namensgeber ist der russische Mathematiker Andrei Markov, der die zugrunde liegenden Markov-Ketten untersuchte.
Lösungskonzepte
Ziel ist eine Policy, also eine Strategie, die jedem Zustand eine Aktion zuordnet. Bewertet werden Policies über ihre Wertfunktion, die den erwarteten diskontierten Gesamtertrag angibt. Die optimale Policy lässt sich über die Bellman-Gleichung charakterisieren. Kennt der Agent das Modell (Übergangswahrscheinlichkeiten und Belohnungen), kann er mit Verfahren der dynamischen Programmierung wie Policy Iteration oder Value Iteration rechnen. Sind die Modellgrößen unbekannt, lernt er die Lösung mit Methoden des Reinforcement Learning wie Q-Learning, Temporal-Difference-Learning oder Policy-Gradient-Verfahren direkt aus Erfahrung.
Anwendungen
MDPs modellieren Robotik-Aufgaben, Spielstrategien, Empfehlungssysteme, autonomes Fahren und Ressourcenverteilung. Für die Praxis erweitert man das Grundmodell um teilweise beobachtbare Zustände (POMDP) oder kontinuierliche Aktionsräume.
Verwandte Grundlagen: Wertfunktion, Bellman-Gleichung.