Einfach erklärt
Markow‑Entscheidungsproblem (Markov Decision Process, MDP) Ein MDP beschreibt schrittweise Entscheidungen in einer unsicheren Umgebung. In jedem Schritt befindet sich ein System in einem Zustand, wählt eine Aktion, erhält eine Belohnung und gelangt mit einer gewissen Wahrscheinlichkeit in den nächsten Zustand. Ziel ist, eine Regel (Strategie) zu finden, die auf lange Sicht möglichst viel Belohnung einbringt.
Ganz einfache Beispiele:
• Roboter im Lager: Der Roboter steht an einem Ort (Zustand), kann fahren/abbiegen (Aktion), zahlt Zeit/ Energie (Belohnung/ Kosten) und landet im nächsten Ort – mit kleiner Unsicherheit durch rutschigen Boden.
• Kundendienst‑Dialog: Der Assistent sieht den Gesprächsstatus (Zustand), wählt eine Antwort (Aktion), erhält Feedback (Belohnung, z. B. Kundenzufriedenheit) und der Dialog geht in einen neuen Status über.
• Inventar‑Steuerung: Lagerbestand ist der Zustand; Aktion ist nachbestellen/abwarten; Belohnung ist Gewinn minus Kosten; Nachfrage ist unsicher.
Professionelle Definition
Ein MDP ist ein Tupel ((\mathcal S,\mathcal A, P, R, \gamma)) mit endlichem oder messbarem Zustandsraum (\mathcal S), Aktionsraum (\mathcal A), Übergangskern (P(s’\mid s,a)), Belohnungsfunktion (R(s,a) = \mathbb E[r\mid s,a]) (oder (R(s,a,s‘))) und Abzinsfaktor (\gamma\in[0,1)). Eine Politik/Strategie (\pi(a\mid s)) induziert den Wert
[V^{\pi}(s) = \mathbb E_{\pi}\Big[\sum_{t=0}^{\infty} \gamma^t r_{t},\Big|,s_0=s\Big],]
der die erwartete abgezinste Rückzahlung ab Startzustand misst. Die Bellman‑Gleichungen lauten
[V^{\pi}(s)=\sum_{a}\pi(a\mid s)\Big(R(s,a)+\gamma\sum_{s‘}P(s’\mid s,a),V^{\pi}(s‘)\Big),]
[V^{}(s)=\max_{a}\Big(R(s,a)+\gamma\sum_{s‘}P(s’\mid s,a),V^{}(s‘)\Big).]
Unter Standardannahmen existiert eine optimale (stationäre) Politik (\pi^{*}). Klassische Lösungsverfahren sind Wertiteration und Politik‑Iteration (dynamische Programmierung). In modellfreiem RL (z. B. Q‑Lernen) wird das MDP ohne explizites P aus Erfahrungen gelernt.
Quellen
• Wikipedia – Markov decision process (Definition, Bellman‑Gleichungen, Lösungsverfahren)
https://en.wikipedia.org/wiki/Markov_decision_process
• Puterman (1994/2014) – Markov Decision Processes: Discrete Stochastic Dynamic Programming (Standardwerk)
https://onlinelibrary.wiley.com/doi/book/10.1002/9781118625591
• Sutton & Barto – Reinforcement Learning: An Introduction (Kapitel zu MDPs & DP/RL)
http://incompleteideas.net/book/the-book.html
• Bertsekas – Dynamic Programming and Optimal Control (Grundlagen DP/MDP, Theorie & Algorithmen)
http://www.athenasc.com/dpbook.html
• Wikipedia – Bellman equation (Hintergrund zur optimalen Bellman‑Gleichung)
https://en.wikipedia.org/wiki/Bellman_equation