Markov Decision Process (MDP)

Auch genannt: MDP
Kategorie: Learning & autonomy › RL & simulation
Schlagwörter: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

Das mathematische Standardmodell für sequenzielle Entscheidungsfindung: Zustände, Aktionen, Übergangswahrscheinlichkeiten, Belohnungen und ein Diskontfaktor, wobei der nächste Zustand nur vom aktuellen Zustand und der aktuellen Aktion abhängt.

Definition

Ein Markov-Entscheidungsprozess (Markov decision process, MDP) beschreibt einen Agenten, der wiederholt einen Zustand beobachtet, eine Aktion wählt, eine Belohnung erhält und in einen neuen Zustand übergeht. Er wird meist als Tupel (S, A, P, R, γ) geschrieben, oft mit einer Anfangszustandsverteilung ρ₀: der Zustandsraum, der Aktionsraum, die Übergangswahrscheinlichkeiten P(s′ | s, a), die Belohnungsfunktion R(s, a) und ein Diskontfaktor γ zwischen 0 und 1, der künftige Belohnungen gegen unmittelbare gewichtet. Die bestimmende Annahme ist die Markov-Eigenschaft: Die Verteilung des nächsten Zustands hängt nur vom aktuellen Zustand und der aktuellen Aktion ab, nicht von der Vorgeschichte, die dorthin geführt hat. Richard Bellmans Arbeiten zur dynamischen Programmierung in den 1950er-Jahren begründeten den Rahmen.

Ziel in einem MDP ist eine Policy, eine Abbildung von Zuständen auf Aktionen (oder auf Verteilungen über Aktionen), die die erwartete diskontierte Summe der Belohnungen maximiert. Die Wertfunktion V(s) und die Aktionswertfunktion Q(s, a) geben diesen erwarteten Return ab einem Zustand bzw. ab einem Zustand und einer Aktion unter einer Policy an. Sie erfüllen die Bellman-Gleichungen, die den Wert eines Zustands als unmittelbare Belohnung plus den diskontierten Wert der nachfolgenden Zustände ausdrücken. Sind P und R bekannt und ist der Zustandsraum klein, lösen Value Iteration und Policy Iteration den MDP exakt. Sind sie unbekannt oder sind die Räume groß und kontinuierlich, schätzt Reinforcement Learning Werte und Policies aus gesampelter Erfahrung.

MDPs sind die formale Grundlage für nahezu das gesamte Reinforcement Learning und einen großen Teil der Planung unter Unsicherheit. Viele Varianten lockern eine der Annahmen: Ein teilweise beobachtbarer MDP (POMDP) verzichtet auf die Annahme, dass der Agent den wahren Zustand sieht; beschränkte MDPs fügen Kostengrenzen hinzu; Semi-MDPs erlauben Aktionen mit variabler Dauer; und Multi-Agenten-Erweiterungen wie Markov-Spiele modellieren mehrere Entscheidungsträger. Was in den Zustand aufgenommen wird, ist eine technische Entscheidung: Fehlen wichtige Informationen wie Geschwindigkeiten, Kontaktstatus oder die Absichten anderer Agenten, ist der Prozess aus Sicht des Agenten nicht mehr markovsch.

Warum es wichtig ist

Jedes Paper zum Reinforcement Learning und die meisten Entscheidungsverfahren in der Robotik formulieren ihr Problem als MDP oder als eine seiner Varianten. Wer die Bestandteile des Tupels kennt und weiß, auf welcher Annahme jede Methode beruht, kann diese Paper lesen, Zustände und Belohnungen für einen realen Roboter entwerfen und erkennen, wann ein Problem in Wirklichkeit teilweise beobachtbar ist.

Wichtige Anwendungen

Formulierung von Reinforcement-Learning-Problemen für Manipulation und Fortbewegung
Planung unter Unsicherheit mit Value Iteration und Policy Iteration
Belohnungsdesign und Inverse Reinforcement Learning, die R erschließen oder formen
Modellbasiertes Reinforcement Learning, das die Übergangsfunktion P lernt
Modellierung der Interaktion mit anderen Agenten über Markov-Spiele und latente Absichtsvariablen

In der Praxis

Ein Team, das einem Roboterarm beibringt, einen Block zu einem Ziel zu schieben, formuliert die Aufgabe als MDP. Der Zustand enthält die Gelenkwinkel und -geschwindigkeiten, die Pose des Blocks und die Zielposition; die Aktion ist eine Änderung der Endeffektorposition pro Regelschritt; die Belohnung ist der negative Abstand zwischen Block und Ziel mit einem Bonus bei Erfolg; und γ wird nahe 1 gesetzt, weil die Aufgabe viele Schritte umfasst. In ersten Tests verhält sich die Policy sprunghaft, wenn sich der Block bewegt, weil der Zustand zwar die Pose des Blocks enthält, nicht aber seine Geschwindigkeit. Wird die Blockgeschwindigkeit hinzugefügt oder werden die letzten Beobachtungen gestapelt, ist die Markov-Eigenschaft weit genug wiederhergestellt, dass ein Standardalgorithmus wie SAC oder PPO zuverlässig lernt.

Häufige Missverständnisse

Ein MDP erfordert diskrete Zustände und Aktionen — kontinuierliche Zustands- und Aktionsräume sind in der Robotik üblich; Summen werden dann durch Integrale und tabellarische Methoden durch Funktionsapproximation ersetzt
Die Markov-Eigenschaft ist eine Tatsache über die Welt — sie ist eine Eigenschaft des gewählten Zustands; werden Geschwindigkeiten oder verborgene Variablen weggelassen, kann ein physikalisches System aus Sicht des Agenten nicht markovsch werden
Der Diskontfaktor spiegelt nur Ungeduld wider — er beschränkt auch den Return bei Problemen mit unendlichem Horizont und beeinflusst Varianz und Stabilität des Lernens, daher wird er oft wie ein Hyperparameter abgestimmt
Zum Lösen eines MDP braucht man ein Modell von P — Reinforcement-Learning-Methoden finden gute Policies aus gesampelten Übergängen, ohne P je aufzuschreiben

Wer das wissen sollte

Praktiker und Forscher im Reinforcement Learning
Ingenieure für Roboterlernen, die Zustände, Aktionen und Belohnungen entwerfen
Forscher in Planung und Entscheidungsfindung
Robotikstudierende, die mit Roboterlernen beginnen

Videos

Markov Decision Processes - Computerphile: Computerphile

Open Source Robotics