Kapitel 2 : Markov-Entscheidungsprozess
Ein zeitdiskreter stochastischer Regelungsprozess wird in der Mathematik als Markov-Entscheidungsprozess (MDP) bezeichnet. Es bietet einen mathematischen Rahmen für die Modellierung der Entscheidungsfindung in Szenarien, in denen die Ergebnisse teilweise von einem Entscheidungsträger gesteuert und teilweise durch Zufall bestimmt werden. Die Untersuchung von Optimierungsproblemen, die durch dynamische Programmierung behandelt werden können, eignet sich gut für den Einsatz von MDPs. Zumindest gibt es MDPs seit den 1950er Jahren. Heutzutage finden sie Anwendung in einer Vielzahl von Bereichen, darunter Robotik, automatisierte Steuerung, Wirtschaft und Fertigung. Da Markov-Entscheidungsprozesse eine Erweiterung von Markov-Ketten sind, wird dem russischen Mathematiker Andrey Markov zugeschrieben, den Begriff für diese Entscheidungsstrukturen geliefert zu haben.
Zu jedem einzelnen Zeitpunkt befindet sich der Prozess in einem bestimmten Zustand , und der Entscheidungsträger kann jede Aktion auswählen, die im Zustand verfügbar ist .
Der Prozess reagiert im nächsten Zeitschritt, indem er zufällig in einen neuen Zustand wechselt und dem Entscheidungsträger eine entsprechende Belohnung gibt .
Die Wahrscheinlichkeit, dass der Prozess in seinen neuen Zustand übergeht, wird durch die gewählte Aktion beeinflusst.
Konkret ist sie durch die Zustandsübergangsfunktion gegeben.
Der nächste Zustand hängt also vom aktuellen Zustand und der Handlung des Entscheidungsträgers ab.
Aber bei gegebenem und ist es bedingt unabhängig von allen anderen Zuständen und Handlungen, die in der Vergangenheit stattgefunden haben; um es anders auszudrücken: Die Markov-Eigenschaft kann durch die Zustandsübergänge eines MDP als erfüllt gezeigt werden.
Die Unterscheidung zwischen Markov-Entscheidungsprozessen und Markov-Ketten ist die Einbeziehung von Aktionen (die eine Wahl ermöglichen) und Belohnungen. Markov-Entscheidungsprozesse sind eine Erweiterung von Markov-Ketten (die Motivation geben). Auf der anderen Seite kann ein Markov-Entscheidungsprozess auf eine Markov-Kette reduziert werden, wenn für jeden Zustand nur eine Aktion möglich ist (z. B. "warten") und alle Belohnungen gleich sind (z. B. "null").
Ein Markov-Entscheidungsprozess ist ein 4-Tupel , wobei:
ist eine Menge von Zuständen, die als Zustandsraum bezeichnet wird, ist eine Menge von Aktionen, die als Aktionsraum bezeichnet wird (alternativ ist die Menge der Aktionen, die aus dem Zustand verfügbar sind ), ist die Wahrscheinlichkeit, dass eine Aktion im Zustand zum Zeitpunkt zum Zustand führt , ist die unmittelbare Belohnung (oder die erwartete unmittelbare Belohnung), die nach dem Übergang von Zustand zu Zustand erhalten wird, aufgrund von Maßnahmen
Sowohl der Zustands- als auch der Aktionsraum haben das Potenzial, entweder begrenzt oder unendlich zu sein, am Beispiel der Menge der reellen Zahlen. Einige Prozesse, die Zustands- und Aktionsräume haben, die abzählbar unendlich sind, können auf solche vereinfacht werden, die Zustands- und Aktionsräume haben, die endlich sind.
Eine Richtlinienfunktion ist eine (potenziell probabilistische) Zuordnung vom Zustandsraum ( ) zum Aktionsraum ().
Das Ziel in einem Markov-Entscheidungsprozess ist es, eine gute "Richtlinie" für den Entscheidungsträger zu finden: eine Funktion , die die Aktion angibt, die der Entscheidungsträger im Zustand wählen wird .
Wenn eine Richtlinie auf diese Weise in einen Markov-Entscheidungsprozess integriert wird, ist das Ergebnis a, dies legt die Aktion für jeden Zustand fest und die resultierende Kombination verhält sich wie eine Markov-Kette (da die im Zustand gewählte Aktion vollständig von bestimmt ist und auf reduziert wird, (Dies wird als Markov-Übergangsmatrix bezeichnet).
Das Ziel ist es, eine Richtlinie zu wählen , die eine kumulative Funktion der zufälligen Belohnungen maximiert, eine übliche Darstellung des vorhergesagten Betrags nach Diskontierung über einen möglicherweise unendlichen Zeitraum:
(wo wir wählen , d.h.
Rechtsakte, die in der Verordnung vorgeschrieben sind).
Und die Erwartung wird übernommen
wobei der Diskontierungsfaktor zufriedenstellend ist , der oft ziemlich nahe bei 1 liegt (z. B . für einen gewissen Diskontsatz r).
Der Entscheidungsträger wird durch einen geringeren Diskontfaktor motiviert, Maßnahmen in einem frühen Stadium des Prozesses zu bevorzugen, anstatt die Dinge auf unbestimmte Zeit aufzuschieben.
Eine Richtlinie, die die obige Funktion maximiert, wird als optimale Richtlinie bezeichnet und wird normalerweise als bezeichnet.
Ein bestimmtes MDP kann über zahlreiche einzigartige optimale Richtlinien verfügen.
Die Markov-Eigenschaft ist dafür verantwortlich, Es kann gezeigt werden, dass die beste Vorgehensweise von den vorhandenen Bedingungen abhängt, wie zuvor erwartet wurde.
Häufig kann es schwierig sein, die Wahrscheinlichkeitsverteilungen des Übergangs explizit genau zu charakterisieren .
In diesem Fall kann die indirekte Modellierung des MDP durch die Verwendung eines Simulators erreicht werden, indem Stichproben aus den Übergangsverteilungen gegeben werden.
Ein episodischer Umgebungssimulator ist ein Beispiel für eine typische Art von implizitem Modell für das multidimensionale grafische Problem (MDP). Dieser Modelltyp kann von einem Anfangszustand aus gestartet werden und erzeugt jedes Mal, wenn er eine Aktionseingabe erhält, einen nachfolgenden Zustand zusammen mit einer Belohnung.
Da dies der Fall ist, ist es möglich, Verläufe von Situationen und Bedingungen, Aktionen und Belohnungen zu erstellen, die oft als Episoden bezeichnet werden.
Ein generatives Modell ist ein Beispiel für eine zusätzliche Art von Simulator, einen einstufigen Simulator, der bei jedem Zustand und jeder Aktion Stichproben des nachfolgenden Zustands und der Belohnung erstellen kann.
(Es ist wichtig zu beachten, dass sich die Definition des Begriffs "generatives Modell" im Zusammenhang mit der statistischen Kategorisierung von dieser Interpretation unterscheidet.) Wenn es um Algorithmen geht, die durch Pseudocode dargestellt werden, wird häufig verwendet, um ein generatives Modell darzustellen.
Zum Beispiel könnte der Ausdruck die Aktion der Stichprobenentnahme aus dem generativen Modell bezeichnen, wobei und der aktuelle Zustand und die aktuelle Aktion und und und der neue Zustand und die Belohnung sind.
Im Vergleich zu einem episodischen Simulator besteht einer der Vorteile der Verwendung eines generativen Modells darin, dass es Ergebnisse mit Daten aus jedem Bundesstaat liefern kann, nicht nur mit denen, die im Laufe einer Reiseroute erreicht wurden.
Eine Hierarchie des Informationsgehalts wird durch diese Modellklassen gebildet: Ein explizites Modell kann leicht ein generatives Modell erzeugen, indem es aus den Verteilungen stichproben, und die wiederholte Anwendung eines generativen Modells kann einen episodischen Simulator erzeugen. In der anderen Richtung ist die einzige Möglichkeit, Approximationsmodelle zu trainieren, die Regression. Dies liegt an der Art der Daten. Die Vielfalt der Modelle, die zur Analyse eines bestimmten MDP verwendet werden können, spielt einen großen Einfluss darauf, herauszufinden, welche Lösungsmethoden für dieses Problem am besten geeignet sind. Zum Beispiel benötigen die dynamischen Programmieralgorithmen, die im folgenden Abschnitt besprochen werden, ein explizites Modell, und der Monte-Carlo-Baum-Suchalgorithmus benötigt ein generatives Modell (oder einen episodischen Simulator, der in jedem Zustand kopiert werden kann), aber die Mehrheit der Reinforcement-Learning-Algorithmen benötigt nur einen episodischen Simulator, um ordnungsgemäß zu funktionieren.
Eine Reihe verschiedener Ansätze, wie z. B. dynamische Programmierung, können verwendet werden, um Antworten auf die Probleme zu finden, die von MDPs aufgeworfen werden, die endliche Zustands- und Aktionsräume haben. Die Algorithmen, die in diesem Abschnitt vorgestellt werden, sind auf MDPs anwendbar, die über endliche Zustands- und Aktionsräume sowie explizit gegebene Übergangswahrscheinlichkeiten und Belohnungsfunktionen verfügen. Trotzdem können die grundlegenden Konzepte erweitert werden, um andere Problemklassen zu behandeln, z. B. durch Approximation von Funktionen.
Die Standardfamilie von Algorithmen zur Berechnung optimaler Richtlinien für MDPs mit endlichem Zustand und Aktion erfordert Speicher für zwei Arrays, die nach Zustand indiziert sind: Wert , Es besteht aus wahren Werten und Richtlinie , die das Ausführen dieser Aktivitäten einschließen.
An diesem Punkt im Prozess des Algorithmus, enthält die Lösung und enthält die diskontierte Summe der Belohnungen, die (im Durchschnitt) verdient werden sollen, indem diese Lösung aus dem Zustand folgt .
Die Methode besteht aus zwei Phasen: (1) einer Aktualisierung des Werts und (2) einer Aktualisierung der Richtlinie. Diese Schritte werden in einer bestimmten Reihenfolge für jeden der Zustände wiederholt, bis keine Änderungen mehr vorgenommen werden müssen. Beide verfeinern kontinuierlich eine vorhandene Schätzung des besten Policen- und Zustandswerts auf der Grundlage einer früheren Version dieser Berechnung.
Ihre Reihenfolge wird durch die jeweilige Iteration des verwendeten Algorithmus bestimmt. Alternativ können sie für alle Zustände gleichzeitig oder nacheinander ausgeführt werden, wobei bestimmte Zustände mehr Aufmerksamkeit erhalten als andere. Solange in keiner der Phasen ein Zustand in einer...
