Markov-Entscheidungsprozesse

Markov-Entscheidungsprozesse formalisieren sequentielle Entscheidungsfindung und modellieren einen Agenten, der in Zuständen Aktionen wählt, um den langfristigen Nutzen zu maximieren.

Definition

Ein Markov-Entscheidungsprozess ist ein Modell der sequentiellen Entscheidungsfindung, definiert durch eine Menge von Zuständen, verfügbaren Aktionen, Wahrscheinlichkeiten des Übergangs zwischen Zuständen bei gegebenen Aktionen und Belohnungen, wobei das Ziel darin besteht, eine Politik zu finden, die den erwarteten kumulativen diskontierten Nutzen maximiert.

Scope

Dieses Thema behandelt den mathematischen Rahmen, der dem Reinforcement Learning zugrunde liegt: Zustände, Aktionen, Übergangswahrscheinlichkeiten, Belohnungen und der Diskontierungsfaktor; Politiken und Wertfunktionen; die Bellman-Optimalitätsgleichungen; und die dynamischen Programmierverfahren der Wertiteration und Politikiteration, die einen bekannten Prozess lösen. Es wird die Markov-Eigenschaft angenommen, dass die Zukunft nur vom aktuellen Zustand abhängt.

Core questions

• Welche Komponenten definieren einen Markov-Entscheidungsprozess?
• Wie verknüpfen die Bellman-Gleichungen den Wert eines Zustands mit seinen Nachfolgern?
• Wie finden Wertiteration und Politikiteration optimale Politiken?
• Was nimmt die Markov-Eigenschaft über die Umgebung an?

Key theories

Bellman-Optimalitätsgleichungen

Der Wert des optimalen Handelns aus einem Zustand entspricht der besten unmittelbaren Belohnung plus dem diskontierten Wert des resultierenden Zustands, eine rekursive Beziehung, deren Lösung die optimale Politik definiert.

Dynamische Programmierung

Wenn der Prozess vollständig bekannt ist, berechnen Wertiteration und Politikiteration optimale Wertfunktionen und Politiken durch wiederholte Anwendung des Bellman-Updates, wodurch die Konvergenz zum Optimum garantiert wird.

Diskontierung und Ertrag

Zukünftige Belohnungen werden mit einem Diskontierungsfaktor gewichtet, sodass der Gesamtertrag wohldefiniert ist und nähere Belohnungen stärker zählen, was die Planung des Agenten in die Zukunft beeinflusst.

Clinical relevance

Markov-Entscheidungsprozesse sind das konzeptionelle Rückgrat des Reinforcement Learning und eines Großteils der Operations Research und Steuerung. Sie stellen die Sprache von Zuständen, Aktionen und Werten bereit, die nahezu alle Lernalgorithmen annähern, wenn das Modell unbekannt oder zu groß ist, um exakt gelöst zu werden.

History

Der Rahmen entstand aus Bellmans dynamischer Programmierung in den 1950er Jahren und Howards Arbeit zur Politikiteration, die exakte Lösungsmethoden für bekannte Entscheidungsprozesse lieferte. Das Reinforcement Learning übernahm später den Markov-Entscheidungsprozess als seinen Standardformalismus für den Fall, dass Übergänge und Belohnungen aus Erfahrung gelernt werden müssen.

Key figures

• Richard Bellman
• Ronald Howard
• Richard Sutton

Seminal works

• sutton2018
• bellman1957
• puterman1994

Frequently asked questions

Was ist die Markov-Eigenschaft?

Die Markov-Eigenschaft besagt, dass die zukünftige Entwicklung des Prozesses nur vom aktuellen Zustand und der Aktion abhängt, nicht von der gesamten Historie, wie der Agent dorthin gelangt ist. Dies macht den aktuellen Zustand zu einer ausreichenden Zusammenfassung für die Entscheidungsfindung.

Warum wird ein Diskontierungsfaktor verwendet?

Die Diskontierung gewichtet nähere Belohnungen stärker als entfernte. Sie hält den Gesamtertrag über lange oder unendliche Horizonte endlich und kodiert eine Präferenz für frühere Belohnungen, während sie auch steuert, wie weit in die Zukunft der Agent effektiv plant.