Markov-Entscheidungsprozess - Markov decision process

In der Mathematik ist ein Markov-Entscheidungsprozess ( MDP ) ein zeitdiskreter stochastischer Steuerungsprozess . Es bietet einen mathematischen Rahmen für die Modellierung der Entscheidungsfindung in Situationen , in denen die Ergebnisse teilweise zufällig sind und teilweise unter der Kontrolle eines Entscheidungsträgers stehen. MDPs sind nützlich, um Optimierungsprobleme zu untersuchen, die durch dynamische Programmierung gelöst werden . MDPs waren mindestens schon in den 1950er Jahren bekannt; ein Kernwerk der Forschung zu Markov-Entscheidungsprozessen resultierte aus Ronald Howards Buch Dynamic Programming and Markov Processes von 1960 . Sie werden in vielen Disziplinen eingesetzt, darunter Robotik , automatische Steuerung , Wirtschaft und Fertigung . Der Name der MDPs stammt von dem russischen Mathematiker Andrey Markov, da sie eine Erweiterung der Markov-Ketten sind .

Bei jedem Zeitschritt befindet sich der Prozess in einem Zustand , und der Entscheidungsträger kann jede Aktion auswählen , die in Zustand verfügbar ist . Der Prozess reagiert im nächsten Zeitschritt, indem er nach dem Zufallsprinzip in einen neuen Zustand übergeht und den Entscheider entsprechend entlohnt . ${\displaystyle s}$${\displaystyle a}$${\displaystyle s}$${\displaystyle s'}$${\displaystyle R_{a}(s,s')}$

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 . Somit hängt der nächste Zustand vom aktuellen Zustand und der Aktion des Entscheidungsträgers ab . Aber gegeben und , ist es bedingt unabhängig von allen vorherigen Zuständen und Aktionen; mit anderen Worten, die Zustandsübergänge eines MDP erfüllen die Markov-Eigenschaft . ${\displaystyle s'}$${\displaystyle P_{a}(s,s')}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s}$${\displaystyle a}$

Markov-Entscheidungsprozesse sind eine Erweiterung von Markov-Ketten ; der Unterschied besteht in der Hinzufügung von Aktionen (Wahlfreiheit) und Belohnungen (Motivation). Umgekehrt, wenn für jeden Zustand nur eine Aktion existiert (zB "warten") und alle Belohnungen gleich sind (zB "null"), reduziert sich ein Markov-Entscheidungsprozess auf eine Markov-Kette.

Definition

Beispiel für ein einfaches MDP mit drei Zuständen (grüne Kreise) und zwei Aktionen (orange Kreise), mit zwei Belohnungen (orange Pfeile).

Ein Markov-Entscheidungsprozess ist ein 4- Tupel , wobei: ${\displaystyle (S,A,P_{a},R_{a})}$

• ${\displaystyle S}$ist eine Menge von Zuständen, genannt Zustandsraum ,
• ${\displaystyle A}$ist eine Menge von Aktionen, die Aktionsraum genannt wird (alternativ ist die Menge von Aktionen, die von state verfügbar sind ),${\displaystyle A_{s}}$${\displaystyle s}$
• ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ist die Wahrscheinlichkeit, dass eine Handlung im Zustand zu einem Zeitpunkt zu einem Zustand zu einem Zeitpunkt führt ,${\displaystyle a}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s'}$${\displaystyle t+1}$
• ${\displaystyle R_{a}(s,s')}$ist die unmittelbare Belohnung (oder die erwartete sofortige Belohnung), die nach dem Übergang von Zustand zu Zustand aufgrund von Maßnahmen erhalten wird${\displaystyle s}$${\displaystyle s'}$${\displaystyle a}$

Die Zustands- und Aktionsräume können endlich oder unendlich sein, zum Beispiel die Menge der reellen Zahlen . Einige Prozesse mit abzählbar unendlichen Zustands- und Aktionsräumen lassen sich auf solche mit endlichen Zustands- und Aktionsräumen reduzieren.

Eine Policy-Funktion ist eine (potenziell probabilistische) Abbildung vom Zustandsraum ( ) zum Aktionsraum ( ). ${\displaystyle \pi}$${\displaystyle S}$${\displaystyle A}$

Optimierungsziel

Das Ziel eines Markov-Entscheidungsprozesses besteht darin, eine gute "Politik" für den Entscheidungsträger zu finden: eine Funktion , die die Aktion angibt, die der Entscheidungsträger im Zustand wählt . Sobald ein Markov-Entscheidungsprozess auf diese Weise mit einer Richtlinie kombiniert wird, fixiert dies die Aktion für jeden Zustand und die resultierende Kombination verhält sich wie eine Markov-Kette (da die im Zustand gewählte Aktion vollständig durch eine Markov-Übergangsmatrix bestimmt wird und auf sie reduziert wird). . ${\displaystyle \pi}$${\displaystyle \pi(s)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle \pi(s)}$${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s)}$

Das Ziel besteht darin, eine Richtlinie zu wählen , die eine kumulative Funktion der zufälligen Belohnungen maximiert, typischerweise die erwartete diskontierte Summe über einen potenziell unendlichen Horizont: ${\displaystyle \pi}$

${\displaystyle E\left[\sum_{t=0}^{\infty }{\gamma^{t}R_{a_{t}}(s_{t},s_{t+1})}\right ]}$(wo wir wählen , dh von der Richtlinie vorgegebene Aktionen). Und die Erwartung wird übernommen${\displaystyle a_{t}=\pi (s_{t})}$${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

wobei der Diskontfaktor erfüllt ist , der normalerweise nahe bei 1 liegt (zum Beispiel für einen Diskontsatz r). Ein niedrigerer Diskontierungsfaktor motiviert den Entscheidungsträger, frühzeitig Maßnahmen zu ergreifen, anstatt sie auf unbestimmte Zeit zu verschieben. ${\displaystyle \ \gamma \ }$${\displaystyle 0\leq\\gamma\\leq\1}$${\displaystyle \gamma=1/(1+r)}$

Eine Richtlinie, die die obige Funktion maximiert, wird als optimale Richtlinie bezeichnet und normalerweise mit bezeichnet . Ein bestimmter MDP kann mehrere unterschiedliche optimale Richtlinien haben. Aufgrund der Markov-Eigenschaft kann gezeigt werden, dass die optimale Richtlinie eine Funktion des aktuellen Zustands ist, wie oben angenommen. ${\displaystyle \pi^{*}}$

Simulatormodelle

In vielen Fällen ist es schwierig, die Übergangswahrscheinlichkeitsverteilungen explizit darzustellen . In solchen Fällen kann ein Simulator verwendet werden, um das MDP implizit zu modellieren, indem Stichproben aus den Übergangsverteilungen bereitgestellt werden. Eine gängige Form des impliziten MDP-Modells ist ein episodischer Umgebungssimulator, der von einem Anfangszustand gestartet werden kann und jedes Mal, wenn er eine Aktionseingabe erhält, einen nachfolgenden Zustand und eine Belohnung liefert. Auf diese Weise können Trajektorien von Zuständen, Aktionen und Belohnungen erzeugt werden, die oft als Episoden bezeichnet werden. ${\displaystyle P_{a}(s,s')}$

Eine andere Form des Simulators ist ein generatives Modell , ein einstufiger Simulator, der Proben des nächsten Zustands generieren und bei jedem Zustand und jeder Aktion belohnen kann. (Beachten Sie, dass dies eine andere Bedeutung als der Begriff generatives Modell im Kontext der statistischen Klassifikation hat.) In Algorithmen , die unter Verwendung von Pseudocode ausgedrückt werden , wird häufig verwendet, um ein generatives Modell darzustellen. Zum Beispiel könnte der Ausdruck die Aktion des Samplings aus dem generativen Modell bezeichnen, wobei und der aktuelle Zustand und die Aktion sind und und der neue Zustand und die Belohnung sind. Im Vergleich zu einem episodischen Simulator hat ein generatives Modell den Vorteil, dass es Daten aus jedem Zustand liefern kann, nicht nur aus solchen, die in einer Trajektorie angetroffen werden. ${\displaystyle G}$${\displaystyle s',r\gets G(s,a)}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s'}$${\displaystyle r}$

Diese Modellklassen bilden eine Hierarchie von Informationsinhalten: Ein explizites Modell ergibt trivialerweise ein generatives Modell durch Stichproben aus den Verteilungen, und die wiederholte Anwendung eines generativen Modells ergibt einen episodischen Simulator. Umgekehrt sind Näherungsmodelle nur durch Regression erlernbar . Der für ein bestimmtes MDP verfügbare Modelltyp spielt eine bedeutende Rolle bei der Bestimmung, welche Lösungsalgorithmen geeignet sind. Beispielsweise erfordern die im nächsten Abschnitt beschriebenen dynamischen Programmieralgorithmen ein explizites Modell, und die Monte-Carlo-Baumsuche erfordert ein generatives Modell (oder einen episodischen Simulator, der in jedem Zustand kopiert werden kann), während die meisten Reinforcement-Learning- Algorithmen nur einen episodischen Simulator erfordern .

Algorithmen

Lösungen für MDPs mit endlichen Zustands- und Aktionsräumen können durch eine Vielzahl von Methoden wie dynamische Programmierung gefunden werden . Die Algorithmen in diesem Abschnitt gelten für MDPs mit endlichen Zustands- und Aktionsräumen und explizit gegebenen Übergangswahrscheinlichkeiten und Belohnungsfunktionen, aber die Grundkonzepte können erweitert werden, um andere Problemklassen zu behandeln, zum Beispiel mithilfe von Funktionsapproximation .

Die Standardfamilie von Algorithmen zum Berechnen optimaler Richtlinien für endliche Zustands- und Aktions-MDPs erfordert die Speicherung von zwei nach Zustand indizierten Arrays: value , das reelle Werte enthält, und policy , das Aktionen enthält. Enthält am Ende des Algorithmus die Lösung und enthält die diskontierte Summe der Belohnungen, die (im Durchschnitt) zu verdienen sind, indem dieser Lösung von Zustand gefolgt wird . ${\displaystyle V}$ ${\displaystyle \pi}$${\displaystyle \pi}$${\displaystyle V(s)}$${\displaystyle s}$

Der Algorithmus hat zwei Schritte, (1) eine Wertaktualisierung und (2) eine Richtlinienaktualisierung, die in einer bestimmten Reihenfolge für alle Zustände wiederholt werden, bis keine weiteren Änderungen mehr stattfinden. Beide aktualisieren rekursiv eine neue Schätzung des optimalen Richtlinien- und Zustandswerts unter Verwendung einer älteren Schätzung dieser Werte.

${\displaystyle V(s):=\sum _{s'}P_{\pi(s)}(s,s')\left(R_{\pi(s)}(s,s')+\gamma V(s')\rechts)}$

${\displaystyle \pi(s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P(s'\mid s,a)\left(R(s'\mid s ,a)+\gamma V(s')\rechts)\rechts\}}$

Ihre Reihenfolge hängt von der Variante des Algorithmus ab; man kann sie auch für alle Staaten gleichzeitig oder Staat für Staat durchführen, und zwar häufiger für einige Staaten als für andere. Solange kein Zustand dauerhaft von einem der Schritte ausgeschlossen ist, kommt der Algorithmus schließlich zur richtigen Lösung.

Bemerkenswerte Varianten

Wertiteration

Bei der Wertiteration ( Bellman 1957 ), die auch Rückwärtsinduktion genannt wird , wird die Funktion nicht verwendet; stattdessen wird der Wert von berechnet, wann immer er benötigt wird. Einsetzen der Berechnung von in die Berechnung von ergibt den kombinierten Schritt: ${\displaystyle \pi}$${\displaystyle \pi(s)}$${\displaystyle V(s)}$${\displaystyle \pi(s)}$${\displaystyle V(s)}$

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s'|s)\left(R_{a}(s ,s')+\gamma V_{i}(s')\rechts)\rechts\},}$

wo ist die Iterationsnummer. Die Wertiteration beginnt bei und als Schätzung der Wertfunktion . Es iteriert dann und berechnet wiederholt für alle Zustände , bis es mit der linken Seite gleich der rechten Seite konvergiert (was die " Bellman-Gleichung " für dieses Problem ist). Lloyd Shapleys Veröffentlichung von 1953 über stochastische Spiele enthielt als Sonderfall die Methode der Wertiteration für MDPs, die jedoch erst später erkannt wurde. ${\displaystyle i}$${\displaystyle i=0}$${\displaystyle V_{0}}$${\displaystyle V_{i+1}}$${\displaystyle s}$${\displaystyle V}$

Richtlinien-Iteration

Bei der Policy-Iteration ( Howard 1960 ) wird Schritt eins einmal ausgeführt und dann wird Schritt zwei wiederholt, bis er konvergiert. Dann wird Schritt eins noch einmal durchgeführt und so weiter.

Anstatt den zweiten Schritt zur Konvergenz zu wiederholen, kann er als ein Satz linearer Gleichungen formuliert und gelöst werden. Diese Gleichungen werden lediglich erhalten, indem in Schritt zwei eine Gleichung erstellt wird. Daher kann das Wiederholen von Schritt zwei zur Konvergenz als Lösen der linearen Gleichungen durch Relaxation (iterative Methode) interpretiert werden.${\displaystyle s=s'}$

Diese Variante hat den Vorteil, dass es eine definitive Stoppbedingung gibt: Wenn sich das Array beim Anwenden von Schritt 1 auf alle Zustände nicht ändert, ist der Algorithmus abgeschlossen. ${\displaystyle \pi}$

Für eine große Anzahl möglicher Zustände ist die Richtlinieniteration normalerweise langsamer als die Wertiteration.

Geänderte Richtlinieniteration

Bei der modifizierten Policy-Iteration ( van Nunen 1976 ; Puterman & Shin 1978 ) wird Schritt eins einmal durchgeführt und dann Schritt zwei mehrmals wiederholt. Dann wird Schritt eins noch einmal durchgeführt und so weiter.

Priorisiertes Kehren

Bei dieser Variante werden die Schritte bevorzugt auf Zustände angewendet, die in irgendeiner Weise wichtig sind – sei es basierend auf dem Algorithmus (es gab in letzter Zeit große Änderungen in oder um diese Zustände) oder basierend auf der Verwendung (diese Zustände sind in der Nähe des Ausgangszustands oder anderweitig) von Interesse für die Person oder das Programm, das den Algorithmus verwendet). ${\displaystyle V}$${\displaystyle \pi}$

Erweiterungen und Verallgemeinerungen

Ein Markov-Entscheidungsprozess ist ein stochastisches Spiel mit nur einem Spieler.

Teilweise Beobachtbarkeit

Die obige Lösung geht davon aus, dass der Zustand bekannt ist, wenn eine Aktion ausgeführt werden soll; sonst nicht kalkulierbar. Wenn diese Annahme nicht zutrifft, wird das Problem als partiell beobachtbarer Markov-Entscheidungsprozess oder POMDP bezeichnet. ${\displaystyle s}$${\displaystyle \pi(s)}$

Einen großen Fortschritt auf diesem Gebiet lieferten Burnetas und Katehakis in "Optimal adaptive Policies for Markov Decision Processes". In dieser Arbeit wurde eine Klasse adaptiver Strategien konstruiert, die gleichförmig maximale Konvergenzrateneigenschaften für die gesamte erwartete Belohnung mit endlichem Horizont besitzen, unter den Annahmen endlicher Zustands-Aktionsräume und Irreduzibilität des Übergangsgesetzes. Diese Richtlinien schreiben vor, dass die Wahl der Maßnahmen in jedem Bundesland und in jedem Zeitraum auf Indizes basieren sollte, die Inflationen der rechten Seite der geschätzten durchschnittlichen Belohnungsoptimalitätsgleichungen sind.

Verstärkungslernen

Reinforcement Learning verwendet MDPs, bei denen die Wahrscheinlichkeiten oder Belohnungen unbekannt sind.

Zu diesem Zweck ist es sinnvoll, eine weitere Funktion zu definieren, die dem Ergreifen der Aktion und dem anschließenden optimalen Fortfahren entspricht (oder gemäß der aktuellen Politik): ${\displaystyle a}$

${\displaystyle \ Q(s,a)=\sum_{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

Obwohl diese Funktion ebenfalls unbekannt ist, basiert die Erfahrung während des Lernens auf Paaren (zusammen mit dem Ergebnis , dh "Ich war in einem Zustand und habe es versucht und ist passiert"). Somit hat man ein Array und nutzt die Erfahrung, um es direkt zu aktualisieren. Dies wird als Q-Lernen bezeichnet . ${\displaystyle (s,a)}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s'}$${\displaystyle Q}$

Reinforcement Learning kann Markov-Entscheidungsprozesse ohne explizite Spezifikation der Übergangswahrscheinlichkeiten lösen; die Werte der Übergangswahrscheinlichkeiten werden in der Wert- und Politikiteration benötigt. Beim Reinforcement Learning wird anstelle einer expliziten Spezifikation der Übergangswahrscheinlichkeiten auf die Übergangswahrscheinlichkeiten durch einen Simulator zugegriffen, der typischerweise viele Male von einem einheitlich zufälligen Anfangszustand neu gestartet wird. Reinforcement Learning kann auch mit Funktionsapproximation kombiniert werden, um Probleme mit einer sehr großen Anzahl von Zuständen anzugehen.

Lernende Automaten

Eine weitere Anwendung des MDP-Prozesses in der Theorie des maschinellen Lernens wird als lernende Automaten bezeichnet. Dies ist auch eine Art von Reinforcement Learning, wenn die Umgebung stochastisch ist. Das erste Papier zum Detaillernen von Automaten wird von Narendra und Thathachar (1974) untersucht, die ursprünglich explizit als endliche Automaten beschrieben wurden . Ähnlich wie beim Reinforcement Learning hat auch ein lernender Automatenalgorithmus den Vorteil, das Problem zu lösen, wenn Wahrscheinlichkeit oder Belohnungen unbekannt sind. Der Unterschied zwischen Lernautomaten und Q-Lernen besteht darin, dass die erstgenannte Technik das Gedächtnis der Q-Werte auslässt, aber die Aktionswahrscheinlichkeit direkt aktualisiert, um das Lernergebnis zu finden. Lernende Automaten sind ein Lernschema mit einem rigorosen Konvergenznachweis.

In der Theorie lernender Automaten besteht ein stochastischer Automat aus:

• eine Menge x möglicher Eingaben,
• eine Menge Φ = { Φ ₁ , ..., Φ _s } möglicher interner Zustände,
• eine Menge α = { α ₁ , ..., α _r } möglicher Ausgaben oder Aktionen mit r ≤ s ,
• ein Anfangszustands-Wahrscheinlichkeitsvektor p (0) = ≪ p ₁ (0), ..., p _s (0) ≫,
• eine berechenbare Funktion A , die nach jedem Zeitschritt t erzeugt p ( t + 1) von p ( t ), den Stromeingang, und den aktuellen Zustand, und
• eine Funktion G : Φ → α, die die Ausgabe bei jedem Zeitschritt erzeugt.

Die Zustände eines solchen Automaten entsprechen den Zuständen eines "diskreten diskreten Parameter- Markov-Prozesses ". Zu jedem Zeitpunkt t = 0,1,2,3,... liest der Automat eine Eingabe aus seiner Umgebung, aktualisiert P( t ) auf P( t +1) um A , wählt zufällig einen Nachfolgezustand gemäß Wahrscheinlichkeiten P( t + 1) und gibt die entsprechende Aktion aus. Die Umgebung des Automaten liest wiederum die Aktion und sendet die nächste Eingabe an den Automaten.

Kategorietheoretische Interpretation

Abgesehen von den Belohnungen kann ein Markov-Entscheidungsprozess im Sinne der Kategorientheorie verstanden werden . Das heißt, sie bezeichnen das freie Monoid mit Stromerzeuger A . Let Dist bezeichnen die Kleisli Kategorie des Giry Monade . Dann kodiert ein Funktor sowohl die Menge S von Zuständen als auch die Wahrscheinlichkeitsfunktion P . ${\displaystyle (S,A,P)}$${\displaystyle {\mathcal{A}}}$${\displaystyle {\mathcal{A}}\to\mathbf{Dist}}$

Auf diese Weise könnten Markov-Entscheidungsprozesse von Monoiden (Kategorien mit einem Objekt) auf beliebige Kategorien verallgemeinert werden. Man kann das Ergebnis nennen eine kontextabhängige Markov - Entscheidungsprozess , weil von einem Objekt zum anderen bei der Bewegung ändert die Menge der zur Verfügung stehenden Aktionen und die Menge der möglichen Zustände. ${\displaystyle ({\mathcal{C}},F:{\mathcal{C}}\to\mathbf{Dist})}$${\displaystyle {\mathcal {C}}}$

Zeitkontinuierlicher Markov-Entscheidungsprozess

Bei zeitdiskreten Markov-Entscheidungsprozessen werden Entscheidungen in diskreten Zeitintervallen getroffen. Bei zeitkontinuierlichen Markov-Entscheidungsprozessen können jedoch Entscheidungen zu jedem beliebigen Zeitpunkt des Entscheidungsträgers getroffen werden. Im Vergleich zu zeitdiskreten Markov-Entscheidungsprozessen können zeitkontinuierliche Markov-Entscheidungsprozesse den Entscheidungsprozess für ein System mit kontinuierlicher Dynamik besser modellieren , dh die Systemdynamik wird durch partielle Differentialgleichungen (PDEs) definiert.

Definition

Um den zeitkontinuierlichen Markov-Entscheidungsprozess zu diskutieren, führen wir zwei Notationen ein:

Sind Zustandsraum und Aktionsraum endlich,

• ${\displaystyle {\mathcal{S}}}$: Zustandsraum;
• ${\displaystyle {\mathcal{A}}}$: Aktionsraum;
• ${\displaystyle q(i\mid j,a)}$: , Übergangsratenfunktion;${\displaystyle {\mathcal{S}}\times {\mathcal{A}}\rightarrow\triangle {\mathcal{S}}}$
• ${\displaystyle R(i,a)}$: , eine Belohnungsfunktion.${\displaystyle {\mathcal{S}}\times {\mathcal{A}}\rightarrow\mathbb{R}}$

Sind Zustandsraum und Aktionsraum stetig,

• ${\displaystyle {\mathcal{X}}}$: Zustandsraum;
• ${\displaystyle {\mathcal {U}}}$: Raum der möglichen Kontrolle;
• ${\displaystyle f(x,u)}$: , eine Übergangsratenfunktion;${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \triangle {\mathcal {X}}}$
• ${\displaystyle r(x,u)}$: , eine Belohnungsratenfunktion, so dass , wo ist die Belohnungsfunktion, die wir im vorherigen Fall besprochen haben.${\displaystyle {\mathcal{X}}\times {\mathcal{U}}\rightarrow\mathbb{R}}$${\displaystyle r(x(t),u(t))\,dt=dR(x(t),u(t))}$${\displaystyle R(x,u)}$

Problem

Wie bei den zeitdiskreten Markov-Entscheidungsprozessen wollen wir in zeitkontinuierlichen Markov-Entscheidungsprozessen die optimale Richtlinie oder Steuerung finden, die uns die optimale erwartete integrierte Belohnung geben könnte:

${\displaystyle \max \operatorname {E} _{u}\left[\left.\int _{0}^{\infty }\gamma ^{t}r(x(t),u(t))\ ,dt\;\right|x_{0}\right]}$

wo ${\displaystyle 0\leq\gamma <1.}$

Formulierung der linearen Programmierung

Wenn der Zustandsraum und der Aktionsraum endlich sind, könnten wir lineare Programmierung verwenden, um die optimale Richtlinie zu finden, was einer der frühesten angewandten Ansätze war. Hier betrachten wir nur das ergodische Modell, was bedeutet, dass unser zeitkontinuierliches MDP unter einer stationären Politik zu einer ergodischen zeitkontinuierlichen Markov-Kette wird . Unter dieser Annahme kann der Entscheidungsträger zwar jederzeit im aktuellen Zustand eine Entscheidung treffen, er könnte jedoch nicht mehr davon profitieren, wenn er mehr als eine Aktion ergreift. Es ist besser für sie, eine Aktion nur zu dem Zeitpunkt durchzuführen, wenn das System vom aktuellen Zustand in einen anderen Zustand übergeht. Unter bestimmten Bedingungen (für Detailprüfung Korollar 3.14 der zeitkontinuierlichen Markov-Entscheidungsprozesse ), wenn unsere Optimalwertfunktion unabhängig von state ist , haben wir die folgende Ungleichung: ${\displaystyle V^{*}}$${\displaystyle i}$

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ und }} a\in A(i)}$

Wenn es eine Funktion gibt , wird die kleinste die obige Gleichung erfüllen. Um zu finden , könnten wir das folgende lineare Programmiermodell verwenden: ${\displaystyle h}$${\displaystyle {\bar {V}}^{*}}$${\displaystyle g}$${\displaystyle {\bar {V}}^{*}}$

• Primäres lineares Programm (P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{st}}\quad &g-\sum _{j\in S}q(j\mid i,a) h(j)\geq R(i,a)\,\,\füralle i\in S,\,a\in A(i)\end{ausgerichtet}}}$

• Duales lineares Programm (D-LP)

${\displaystyle {\begin{ausgerichtet}{\text{Maximieren}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a) \\{\text{st}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ und }}\forall i\in S\end{ausgerichtet}}}$

${\displaystyle y(i,a)}$ist eine zulässige Lösung für das D-LP, wenn es nicht nativ ist und die Beschränkungen im D-LP-Problem erfüllt. Eine zulässige Lösung des D-LP heißt optimale Lösung, wenn ${\displaystyle y(i,a)}$${\displaystyle y^{*}(i,a)}$

${\displaystyle {\begin{ausgerichtet}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{ausgerichtet}}}$

für alle machbaren Lösungen des D-LP. Wenn wir die optimale Lösung gefunden haben , können wir daraus die optimalen Richtlinien erstellen. ${\displaystyle y(i,a)}$${\displaystyle y^{*}(i,a)}$

Hamilton-Jacobi-Bellman-Gleichung

Bei zeitkontinuierlicher MDP, wenn Zustandsraum und Aktionsraum stetig sind, könnte das optimale Kriterium durch Lösen der partiellen Hamilton-Jacobi-Bellman (HJB)-Differentialgleichung gefunden werden . Um die HJB-Gleichung zu diskutieren, müssen wir unser Problem umformulieren

${\displaystyle {\begin{ausgerichtet}V(x(0),0)={}&\max _{u}\int _{0}^{T}r(x(t),u(t)) \,dt+D[x(T)]\\{\text{st}}\quad &{\frac {dx(t)}{dt}}=f[t,x(t),u(t) ]\end{ausgerichtet}}}$

${\displaystyle D(\cdot)}$ist die Terminal-Belohnungsfunktion, ist der Systemzustandsvektor, ist der Systemsteuerungsvektor, den wir zu finden versuchen. zeigt, wie sich der Zustandsvektor über die Zeit ändert. Die Hamilton-Jacobi-Bellman-Gleichung lautet wie folgt: ${\displaystyle x(t)}$${\displaystyle u(t)}$${\displaystyle f(\cdot)}$

${\displaystyle 0=\max_{u}(r(t,x,u)+{\frac {\partial V(t,x)}{\partial x}}f(t,x,u))}$

Wir könnten die Gleichung lösen, um die optimale Steuerung zu finden , die uns die optimale Wertfunktion liefern könnte${\displaystyle u(t)}$ ${\displaystyle V^{*}}$

Anwendung

Zeitkontinuierliche Markov-Entscheidungsprozesse haben Anwendungen in Warteschlangensystemen , epidemischen Prozessen und Populationsprozessen .

Alternative Notationen

Terminologie und Notation für MDPs sind noch nicht vollständig geklärt. Es gibt zwei Hauptrichtungen – der eine konzentriert sich auf Maximierungsprobleme aus Kontexten wie Ökonomie, verwendet die Begriffe Aktion, Belohnung, Wert und nennt den Diskontfaktor oder , während der andere sich auf Minimierungsprobleme aus Technik und Navigation konzentriert und die Begriffe Kontrolle, Kosten verwendet , Cost-to-Go und Aufruf des Rabattfaktors . Außerdem variiert die Schreibweise für die Übergangswahrscheinlichkeit. ${\displaystyle \beta}$${\displaystyle\gamma}$${\displaystyle\alpha}$

In diesem Artikel	Alternative	Kommentar
Handlung ${\displaystyle a}$	Steuerung ${\displaystyle u}$
belohnen ${\displaystyle R}$	Kosten ${\displaystyle g}$	${\displaystyle g}$ ist das Negativ von ${\displaystyle R}$
Wert ${\displaystyle V}$	Kosten zum Mitnehmen ${\displaystyle J}$	${\displaystyle J}$ ist das Negativ von ${\displaystyle V}$
Politik ${\displaystyle \pi}$	Politik ${\displaystyle\mu}$
Abzinsungsfaktor ${\displaystyle \ \gamma \ }$	Abzinsungsfaktor ${\displaystyle\alpha}$
Übergangswahrscheinlichkeit ${\displaystyle P_{a}(s,s')}$	Übergangswahrscheinlichkeit ${\displaystyle p_{ss'}(a)}$

Darüber hinaus wird Übergangswahrscheinlichkeit manchmal geschrieben , oder, selten,${\displaystyle \Pr(s,a,s')}$${\displaystyle \Pr(s'\mid s,a)}$${\displaystyle p_{s}(a).}$

Eingeschränkte Markov-Entscheidungsprozesse

Constrained Markov Decision Processes (CMDPs) sind Erweiterungen des Markov-Entscheidungsprozesses (MDPs). Es gibt drei grundlegende Unterschiede zwischen MDPs und CMDPs.

• Es fallen mehrere Kosten an, nachdem eine Aktion statt einer ausgeführt wurde.
• CMDPs werden nur mit linearen Programmen gelöst und dynamische Programmierung funktioniert nicht.
• Die endgültige Richtlinie hängt vom Ausgangszustand ab.

Es gibt eine Reihe von Anwendungen für CMDPs. Es wurde kürzlich in Bewegungsplanungsszenarien in der Robotik verwendet.

Siehe auch

Verweise

Weiterlesen

• Bellman., RE (2003) [1957]. Dynamische Programmierung (Dover Taschenbuch Hrsg.). Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3.
• Bertsekas, D. (1995). Dynamische Programmierung und optimale Steuerung . 2 . MA: Athene.
• Derman, C. (1970). Markovasche Entscheidungsprozesse mit endlichen Zuständen . Akademische Presse.
• Feinberg, EA; Shwartz, A., Hrsg. (2002). Handbuch der Markov-Entscheidungsprozesse . Boston, MA: Kluwer. ISBN 9781461508052.
• Guo, X.; Hernández-Lerma, O. (2009). Zeitkontinuierliche Markov-Entscheidungsprozesse . Stochastische Modellierung und angewandte Wahrscheinlichkeit. Springer. ISBN 9783642025464.
• Meyn, SP (2007). Steuerungstechniken für komplexe Netzwerke . Cambridge University Press. ISBN 978-0-521-88441-9. Archiviert vom Original am 19. Juni 2010.Anhang enthält gekürzte "Meyn & Tweedie" . Archiviert vom Original am 18. Dezember 2012.
• Puterman., ML (1994). Markov-Entscheidungsprozesse . Wiley.
• Ross, SM (1983). Einführung in die stochastische dynamische Programmierung (PDF) . Akademische Presse.
• Sutton, RS; Barto, AG (2017). Reinforcement Learning: Eine Einführung . Cambridge, MA: Die MIT-Presse.
• Tijms., HC (2003). Ein erster Kurs in stochastischen Modellen . Wiley. ISBN 9780470864289.

Externe Links

• Markovsche Entscheidungsprozesse lösen lernen von Satinder P. Singh