SAFFER Zsolt am 14. September 2024 um 23:20 Uhr

2024-09-14T23:20:01Z

← Nächstältere Version		Version vom 14. September 2024, 23:20 Uhr
Zeile 82:		Zeile 82:
	<math display="block">Q^*(s,a) = \max_{\pi} Q_{\pi}(s, a)</math> gegeben.		<math display="block">Q^*(s,a) = \max_{\pi} Q_{\pi}(s, a)</math> gegeben.

	Beobachte, dass <math display="inline">V^(s)</math> der Wert ist, bei dem zunächst die beste Aktion durchgeführt wurde. Daraus folgt, dass <math display="inline">V^(s)</math> mit <math display="inline">Q^(s,a)</math> als <math display="block">V^(s) = \max_{a} Q^*(s,a) ~~\label{opV_opQ}~~</math> in Beziehung gesetzt werden kann.		Beobachte, dass <math display="inline">V^(s)</math> der Wert ist, bei dem zunächst die beste Aktion durchgeführt wurde. Daraus folgt, dass <math display="inline">V^(s)</math> mit <math display="inline">Q^(s,a)</math> als <math display="block">V^(s) = \max_{a} Q^*(s,a) </math> in Beziehung gesetzt werden kann.

	Die Bellman-Gleichung für <math display="inline">Q^*(s,a)</math> kann wie folgt angegeben werden: <math display="block">\begin{aligned}		Die Bellman-Gleichung für <math display="inline">Q^*(s,a)</math> kann wie folgt angegeben werden: <math display="block">\begin{aligned}
Zeile 93:		Zeile 93:
	<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimale Policy'''''</span>		<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimale Policy'''''</span>

	Die optimale (deterministische) Policy <math display="inline">\pi^(s)</math> kann aus der optimalen Aktionswertfunktion als <math display="block">\pi^(s) = \arg \max_{a} Q^*(s,a) ~~\label{opPol_opQ}~~</math> erhalten werden.		Die optimale (deterministische) Policy <math display="inline">\pi^(s)</math> kann aus der optimalen Aktionswertfunktion als <math display="block">\pi^(s) = \arg \max_{a} Q^*(s,a) </math> erhalten werden.

	Die optimale Policy kann auch aus der optimalen Wertfunktion berechnet werden, indem zunächst die optimale Aktionswertfunktion aus der optimalen Wertfunktion berechnet wird. Dies führt zu <math display="block">Q^(s,a) = r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}\|s,a) V^(s^{'}).</math>		Die optimale Policy kann auch aus der optimalen Wertfunktion berechnet werden, indem zunächst die optimale Aktionswertfunktion aus der optimalen Wertfunktion berechnet wird. Dies führt zu <math display="block">Q^(s,a) = r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}\|s,a) V^(s^{'}).</math>

SAFFER Zsolt: Die Seite wurde neu angelegt: „ = Reinforcement Learning = Reinforcement Learning - RL (Bestärkendes Lernen oder Verstärkungslernen) ist ein agentenbasierter ML Ansatz. Ein Agent passt seine Aktionen iterativ entsprechend dem Feedback der Umgebung an, um sein Ziel zu erreichen. Dieser Mechanismus kommt in vielen biologischen Systemen vor und ist typisch für Kontrollaufgaben. Dieser auf iterativer Bewertung basierende Mechanismus findet jedoc…“

2024-09-14T23:15:15Z

Die Seite wurde neu angelegt: „ = Reinforcement Learning = Reinforcement Learning - RL (Bestärkendes Lernen oder Verstärkungslernen) ist ein agentenbasierter ML Ansatz. Ein Agent passt seine Aktionen iterativ entsprechend dem Feedback der Umgebung an, um sein Ziel zu erreichen. Dieser Mechanismus kommt in vielen biologischen Systemen vor und ist typisch für Kontrollaufgaben. Dieser auf iterativer Bewertung basierende Mechanismus findet jedoc…“

Neue Seite

= Reinforcement Learning =

Reinforcement Learning - RL (Bestärkendes Lernen oder Verstärkungslernen) ist ein agentenbasierter ML Ansatz. Ein Agent passt seine Aktionen iterativ entsprechend dem Feedback der Umgebung an, um sein Ziel zu erreichen. Dieser Mechanismus kommt in vielen biologischen Systemen vor und ist typisch für Kontrollaufgaben. Dieser auf iterativer Bewertung basierende Mechanismus findet jedoch auch bei vielen anderen Aufgaben aus anderen Anwendungsbereichen, da er ein Optimierungsproblem realisiert.


== Kurze Beschreibung von Reinforcement Learning (RL) ==


=== Problemstellung ===

Die Zeit wird als diskrete Zeit modelliert, d. h. sie verläuft in Zeitschritten (time steps). Der RL-Agent befindet sich zum Zeitpunkt <math display="inline">t</math> in einem Zustand <math display="inline">s_t</math> , wobei <math display="inline">s_t \in \mathcal{S}</math>. Der Agent führt eine Aktion <math display="inline">a_t</math>, <math display="inline">a_t \in \mathcal{A}</math> aus den erlaubten Aktionen im Zustand <math display="inline">s_t</math> aus. Als Reaktion der Umgebung auf diese Aktion erhält der Agent eine Belohnung (reward) <math display="inline">r_t</math>, <math display="inline">r_t \in \mathcal{R}</math> und der Zustand des Agenten ändert sich im nächsten Zeitschritt <math display="inline">t+1</math> zu <math display="inline">s_{t+1}</math> . Der Begriff „Umgebung“ wird im weitesten Sinne verwendet, was bedeutet, dass die Umgebung alles sein kann, was auf die Aktionen eines Agenten reagiert. Das Ziel des RL-Agenten wird durch die Maximierung der akkumulierten (erwarteten) Belohnungen (accumulated expected reward) in der Zukunft modelliert, wobei der Wertverlust der Belohnungen (depreciation of rewards) im Laufe der Zeit berücksichtigt wird. Dies erfolgt auf die in der Wirtschaftswissenschaft übliche Methode durch die Anwendung von Abzinsungsfaktoren (discount factors). Auf diese Weise erreicht der RL-Agent sein Ziel, indem er durch iterative Auswertungen der Reaktionen der Umgebung auf seine Aktionen eine Folge von Aktionen festlegt.

Die Interaktion mit der Umgebung wird durch die Belohnungsfunktion <math display="inline">r(s_t,a_t)</math> und die Zustandsänderungen durch Zustandsübergangswahrscheinlichkeiten 
<math display="inline">p(s_{t+1}|s_t,a_t)</math> beschrieben. Die RL-Literatur hinsichtlich des Zusammenhangs der unmittelbaren Belohnung zur Zeit <math display="inline">t</math> oder <math display="inline">t+1</math> nicht einheitlich ist. Während der gesamten Diskussion von RL übernehmen wir die Assoziation der unmittelbaren Belohnung zum Zeitschritt <math display="inline">t</math>. Somit wird die diskontierte, akkumulierte Belohnung im Zeitschritt <math display="inline">t</math>, <math display="inline">t \in N^+</math> durch

<math display="block">R_t = \sum_{\tau = 0}^{\infty} \gamma^{\tau} r_{t+\tau}</math> ausgedrückt, wobei <math display="inline">\gamma \in (0,1]</math> der Abzinsungsfaktor ist. Das Verhalten des Agenten wird durch die Wahrscheinlichkeiten <math display="inline">p(a|s)</math> für <math display="inline">s \in \mathcal{S}</math> und <math display="inline">a \in \mathcal{A}</math> charakterisiert. Sie beschreiben, welche Aktion mit welcher Wahrscheinlichkeit in jedem Zustand durchgeführt wird. Dies bestimmt auch die vom Agenten befolgte Policy, für die die Notation <math display="inline">\pi</math> verwendet wird. Dann das Ziel des Agenenten kann als ein Optimierungsproblem, wie folgt,

<math display="block">\arg\max_{\pi} E[R_t|s_t, \pi]</math>

formuliert werden, wobei <math display="inline">E[]</math> für die Erwartung steht. Die Erwartung bezieht im obigen Ausdruck auf alle zufälligen Komponenten der bedingten diskontierten, akkumulierten ermäßigten Belohnung, gegeben der Startzustand und die Policy. Basierend auf der obigen Optimierungsformulierung kann das Ziel des Agenten auch darin ausgedrückt werden, die optimale Policy zu finden, die zu der maximal erwarteten diskontierten, akkumulierten zukünftigen Belohnung führt.

Wir haben den RL Ansatz in diskreten Räumen (discrete spaces) erklärt, er kann aber auch auf kontinuierliche Zustands- und Aktionsräume (continuous state and action spaces) erweitert werden.


=== Elemente von RL ===

Die typischen Elemente eines RL Ansatzes sind:

# das Modell (model),
# die Strategy (policy),
# die Wertfunktion (value function) und
# die Aktionswertfunktion (action value function).

Das Modell beschreibt die Umgebungsdynamik und wird durch die Belohnungsfunktion <math display="inline">r(s,a)</math> und die Übergangswahrscheinlichkeiten der Zuständen 
<math display="inline">p(s^{'}|s,a)</math> gegeben. Alternativ kann es in kompakter Form durch die Funktion <math display="inline">p(s^{'},r|s,a)</math> angegeben werden.

Die Policy beschreibt das langfristige Verhalten, das der Agent während seiner Interaktion mit der Umgebung im Laufe der Zeit verfolgt. Im Allgemeinen ist die Policy <math display="inline">\pi</math> eine Abbildung, die jedem Zustand <math display="inline">s \in \mathcal{S}</math> die Wahrscheinlichkeitsverteilung <math display="inline">p(a|s)</math>, <math display="inline">a \in \mathcal{A}</math> zuweist , d. h. die Policy wird durch die Aktionswahrscheinlichkeiten spezifiziert, die die Wahrscheinlichkeit des Ausführens einer Aktion in einem bestimmten Zustand charakterisieren. Im Falle einer deterministischen Policy wird jedem Zustand nur eine Aktion zugewiesen. Für diesen Fall verwenden wir die Funktionsnotation <math display="inline">a = \pi(s)</math> für <math display="inline">a \in \mathcal{A}</math> und <math display="inline">s \in \mathcal{S}</math>.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Wertfunktion'''''

Die (Zustands-)Wertfunktion gibt die erwartete diskontierte, akkumulierte zukünftige Belohnung unter Berücksichtigung des tatsächlichen Zustands und der Policy an. Aufgrund der Erwartung handelt es sich um eine Art Vorhersage der künftig angesammelten Belohnung. Die Wertfunktion hängt vom Ausgangszustand und der angewendeten Policy ab. Diese werden auch in seinen Notationen ausgedrückt: <math display="inline">V_{\pi}(s)</math> oder <math display="inline">V(s)</math>. Basierend auf der obigen Definition kann es formal durch

<math display="block">V_{\pi}(s) = E[R_t|s_t=s, \pi]</math> gegeben sein.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Aktionswertfunktion'''''

In ähnlicher Weise gibt die Aktionswertfunktion die erwartete diskontierte, akkumulierte zukünftige Belohnung an, jedoch neben dem Anfangszustand und der Policy auch als Abhängigkeit von der Anfangsaktion. Es wird mit <math display="inline">Q_{\pi}(s,a)</math> oder einfach <math display="inline">Q(s,a)</math> bezeichnet und ist formal durch

<math display="block">Q_{\pi}(s,a) = E[R_t|s_t=s, a_t=a, \pi]</math> gegeben.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Bellman-Gleichungen'''''

Sowohl die Wertfunktion als auch die Aktionswertfunktion können rekursiv über die möglichen Zustandsübergänge ausgedrückt werden. Diese werden durch die Bellman-Gleichungen wie folgt angegeben

<math display="block">\begin{aligned}
V_{\pi}(s) &= \sum_{a \in \mathcal{A}} p(a|s) \sum_{s^{'} \in \mathcal{S}, r \in \mathcal{R}} p(s^{'},r|s,a) \left(r + \gamma V_{\pi}(s^{'}) \right) \\
&= \sum_{a \in \mathcal{A}} p(a|s) \left(r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi}(s^{'}) \right), \\
Q_{\pi}(s,a) &= \sum_{s^{'} \in \mathcal{S}, r \in \mathcal{R}} p(s^{'},r|s,a) \left(r + \gamma \sum_{a^{'} \in \mathcal{A}} p(a^{'}|s^{'}) Q_{\pi}(s^{'}, a^{'}) \right) \\
&= r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) \sum_{a^{'} \in \mathcal{A}} p(a^{'}|s^{'}) Q_{\pi}(s^{'}, a^{'}) .
\end{aligned}</math>

Diese rekursiven Gleichungen können als Zerlegungen (decompositions) betrachtet werden und als Grundlage für Lösungsalgorithmen für RL, wie dynamische Programmierung (dynamic programming) dienen.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimale Wertfunktion'''''

Die optimale Wertfunktion ist der maximale Wert, der über alle mögliche Policy erreicht werden kann. Anders ausgedrückt:

<math display="block">V^*(s) = \max_{\pi} V_{\pi}(s).</math>

Auch <math display="inline">V^*(s)</math> kann auf rekursive Weise ausgedrückt werden, was durch <math display="block">\begin{aligned}
V^*(s) &= \max_{a} \sum_{s^{'} \in \mathcal{S}, r \in \mathcal{R}} p(s^{'},r|s,a) \left(r + \gamma V^*(s^{'}) \right) \\
&= \max_{a} \left(r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V^*(s^{'}) \right)
\end{aligned}</math> gegeben werden kann.

Dies ist ebenfalls eine Bellman-Gleichung. Der Ausdruck von <math display="inline">V^*(s)</math> beinhaltet implizit, dass zunächst (im Zustand <math display="inline">s</math>) die beste Aktion ausgeführt wird. Dies liegt daran, dass die gewichtete Summe in <math display="inline">V_{\pi}(s)</math> mit Wahrscheinlichkeitsgewichten <math display="inline">p(a|s)</math> kann als Interpolation interpretiert werden, weil <math display="inline">\sum_{a \in \mathcal{A}} p(a|s) = 1</math>. Daher ist das Maximum der gewichteten Summe der höchste Wert in der Summe mit dem Wahrscheinlichkeitsgewicht <math display="inline">1</math>. Dies bedeutet, dass das Ergreifen der besten Maßnahme zunächst impliziert, dass die resultierende optimale Policy deterministisch ist.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimale Aktionswertfunktion'''''

Ebenso ist die optimale Aktionswertfunktion der maximale Aktionswert, der über alle mögliche Startegie erreicht werden kann. Somit ist es durch

<math display="block">Q^*(s,a) = \max_{\pi} Q_{\pi}(s, a)</math> gegeben.

Beobachte, dass <math display="inline">V^*(s)</math> der Wert ist, bei dem zunächst die beste Aktion durchgeführt wurde. Daraus folgt, dass <math display="inline">V^*(s)</math> mit <math display="inline">Q^*(s,a)</math> als <math display="block">V^*(s) = \max_{a} Q^*(s,a) \label{opV_opQ}</math> in Beziehung gesetzt werden kann.

Die Bellman-Gleichung für <math display="inline">Q^*(s,a)</math> kann wie folgt angegeben werden: <math display="block">\begin{aligned}
Q^*(s,a) &= \sum_{s^{'} \in \mathcal{S}, r \in \mathcal{R}} p(s^{'},r|s,a) \left(r + \gamma \max_{a^{'}} Q^*(s^{'}, a^{'}) \right) \\
&= r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) \max_{a^{'}} Q^*(s^{'}, a^{'}) .
\end{aligned}</math>

Auch hier wird zunächst die beste Aktion ausgeführt, jetzt im Zustand <math display="inline">s^{'}</math>, da dies der erste Zustand ist, in dem eine Aktion ausgewählt werden muss (die Aktion <math display="inline">a</math> im Zustand <math display="inline">s</math> ist bereits gegeben).

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimale Policy'''''

Die optimale (deterministische) Policy <math display="inline">\pi^*(s)</math> kann aus der optimalen Aktionswertfunktion als <math display="block">\pi^*(s) = \arg \max_{a} Q^*(s,a) \label{opPol_opQ}</math> erhalten werden.

Die optimale Policy kann auch aus der optimalen Wertfunktion berechnet werden, indem zunächst die optimale Aktionswertfunktion aus der optimalen Wertfunktion berechnet wird. Dies führt zu <math display="block">Q^*(s,a) = r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V^*(s^{'}).</math>


== Methodentypen von RL ==

Es gibt zwei Arten von Methoden zur Lösung eines RL Problems:

* Modellbasierte Methoden (model-based methods)
* Modellfreie Methoden (model-free methods)


=== Modellbasierte Methoden ===

Wenn das RL Modell die Markov-Eigenschaft erfüllt, d. h. die zukünftige Entwicklung der Zustände und Aktionen nur vom tatsächlichen Zustand abhängt, kann das RL Problem als Markov Entscheidungsprozess (MDP) formuliert werden.

Wenn der Status des Prozesses nach jedem Intervall der Länge <math display="inline">T</math> zurückgesetzt wird, dann ist das MDP episodisch mit einer Episode der Länge <math display="inline">T</math>. Eine Trajectory (oder Rollout) ist eine Verwirklichung der Abfolge von Zuständen, Aktionen und Belohnungen in einer Episode. In diesem Fall wird die kumulierte ermäßigte Prämie <math display="block">R = \sum_{t = 0}^{T-1} \gamma^{t} r_{t}</math> gegeben. Im nicht-episodischen MDP <math display="inline">T=\infty</math>. In diesem Fall stellt die Einstellung <math display="inline">\gamma < 1</math> die Endlichkeit der diskontierten, akkumulierten Belohnung sicher.

Wenn das Modell gegeben ist, sind die Belohnungsfunktion <math display="inline">r(s,a)</math> und die Übergangswahrscheinlichkeiten <math display="inline">p(s^{'}|s,a)</math> bekannt. Daher kann der rekursive Charakter der Bellman-Gleichungen genutzt werden. Dies ermöglicht die Erstellung von Algorithmen mithilfe dynamischer Programmierung. Die beiden wichtigsten modellbasierten Algorithmen sind

* Value Iteration und
* Policy Iteration.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Value iteration'''''

Die Wertfunktion kann iterativ für alle Zustände aus der Bellman-Gleichung für <math display="inline">Q^*(s,a)</math>, kombiniert mit der Beziehung zwischen <math display="inline">V^*(s)</math> und <math display="inline">Q^*(s,a)</math>, berechnet werden. Dies ist die Basis für den Value Iteration Algorithmus. Der Pseudocode des Algorithmus wird in Algorithm dargestellt.

 
Algorithm Value iteration 
'''—————————————————————————————''' 
Eingabe: 
- die Belohnungsfunktion <math display="inline">r(s,a)</math> für <math display="inline">s \in \mathcal{S}</math> und <math display="inline">a \in \mathcal{A}</math>, 
- die Übergangswahrscheinlichkeiten <math display="inline">p(s^{'}|s,a)</math> für <math display="inline">s, s^{'} \in \mathcal{S}</math> und <math display="inline">a \in \mathcal{A}</math>. 
Ausgabe: die optimale Wertfunktion <math display="inline">V^*(s)</math> für <math display="inline">s \in \mathcal{S}</math>. 
'''—————————————————————————————''' 
1 Initialisierung von <math display="inline">V(s)</math> mit einer beliebigen nicht negativen Funktion 
2 Wenn das Stoppkriterium NICHT erfüllt ist 
3 for <math display="inline">s \in \mathcal{S}</math> 
4 for <math display="inline">a \in \mathcal{A}</math> 
5 <math display="inline">Q(s,a) = r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V(s^{'})</math> 
6 end 
7 <math display="inline">V(s^{'})= \max_{a^{'}} Q(s^{'}, a^{'})</math> 
8 end 
9 end 
'''—————————————————————————————''' 
Es kann gezeigt werden, dass der Algorithmus immer gegen <math display="inline">V^*(s)</math> 
([Bellman(1957)], [Bertsekas(1987)]) konvergiert. Die optimale Policy kann aus dem berechneten <math display="inline">Q^*(s,a)</math> bestimmt werden. Dies ist ein Greedy Algorithmus, da <math display="inline">V^*(s)</math> in jeder Iteration basierend auf der besten Aktion in jedem Zustand bestimmt wird. Allgemeiner gesagt ist ein Algorithmus Greedy, wenn in jedem Iterationsschritt die Eingabe für die nächste Iteration als die (in gewisser Weise) beste Ausgabe des tatsächlichen Iterationsschritts bestimmt wird. Ein wirksames Stoppkriterium besteht darin, zu iterieren, bis die maximale Differenz zwischen zwei aufeinanderfolgenden Wertfunktionen kleiner als ein vorgeschriebener kleiner <math display="inline">\epsilon</math>-Wert ist.

Die numerische Komplexität des Algorithmus beträgt <math display="inline">\mathcal{O}(|\mathcal{S}|^2 |\mathcal{A}| I)</math>, wobei <math display="inline">I</math> die Anzahl der erforderlichen Iterationen ist.

'''''<math display="inline">\mathrm{\ \ \ \ }</math> Policy Iteration'''''

Bei der Value Iteration wird die optimale Policy indirekt aus der optimalen Wertfunktion ermittelt. Im Policy Iteration Algorithmus wird die Policy direkt in jedem Iterationsschritt berechnet. Die iterative Berechnung der Policy kann direkt erfolgen, indem eine Gleichung verwendet wird, die wiederum aus der Kombination der Bellman-Gleichung für <math display="inline">Q^*(s,a)</math> mit der Beziehung zwischen <math display="inline">V^*(s)</math> und <math display="inline">Q^*(s,a)</math> erhalten wird. Dies führt zu

<math display="block">\pi^*(s) = \arg \max_{a} \left(r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi^*}^*(s^{'}) \right).</math>

Die rekursive Berechnung der nächsten Policy <math display="inline">\pi^{'}</math> basierend auf der obigen Gleichung erfordert die Berechnung von <math display="inline">V_{\pi}(s^{'})</math> für jedes <math display="inline">s^{'} \in \mathcal {S}</math> aus der tatsächlichen Policy <math display="inline">\pi(s)</math>. Dies kann erreicht werden, indem die Policy <math display="inline">\pi</math> auf die Bellman-Gleichungen der Wertfunktion angewendet und für die Werte <math display="inline">V_{\pi}(s^{'})</math> gelöst wird. Sie bilden ein lineares Gleichungssystem, da sie keine Maximaloperation beinhalten. Das Zusammenfügen all dieser Punkte ergibt den Policy Iteration Algorithmus. Der Pseudocode des Algorithmus wird in Algorithm angezeigt.

 
Algorithm Policy iteration 
'''—————————————————————————————''' 
Eingabe: 
- die Belohnungsfunktion <math display="inline">r(s,a)</math> für <math display="inline">s \in \mathcal{S}</math> und <math display="inline">a \in \mathcal{A}</math>, 
- die Übergangswahrscheinlichkeiten <math display="inline">p(s^{'}|s,a)</math> für <math display="inline">s, s^{'} \in \mathcal{S}</math> und <math display="inline">a \in \mathcal{A}</math>. 
Ausgabe: die optimale Policy <math display="inline">\pi^*(s)</math> für <math display="inline">s \in \mathcal{S}</math>. 
'''—————————————————————————————''' 
1 Auswählen eine beliebige Policy <math display="inline">\pi^{'}(s)</math> und Einstellen <math display="inline">\pi \neq \pi^{'}</math> 
2 while <math display="inline">\pi^{'} \neq \pi</math> 
3 <math display="inline">\pi = \pi^{'}</math> 
4 Berechnen <math display="inline">V_{\pi}(s^{'})</math> aus der Policy <math display="inline">\pi</math>, durch Lösung eines linearen Gleichungssystems lösen 
<math display="inline">\mathrm{\ \ \ \ \ \ }</math> <math display="inline">V_{\pi}(s) = \left(r(s,\pi(s)) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi}(s^{'}) \right)</math> 
5 Aktualisieren die Policy als 
<math display="inline">\mathrm{\ \ \ \ \ \ }</math> <math display="inline">\pi^{'}(s) = \arg \max_{a} \left(r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi}(s^{'})\right)</math> for every <math display="inline">s \in \mathcal{S}</math> 
6 end 
'''—————————————————————————————''' 
Das Aktualisieren der Policy bedeutet, die beste erste Aktion anstelle der zuvor von der Policy verwendeten <math display="inline">\pi(s)</math> zu bestimmen. Wenn sie unterschiedlich sind, verbessert die Änderung der ersten Aktion strikt die Wertfunktion (der Wert mit der besten Aktion ist aufgrund von max besser als mit der vorherigen Aktion) und damit auch die Policy. Wenn in der Policy keine Aktion geändert werden, ist keine Verbesserung möglich und die Policy ist somit optimal. Die Anzahl der Iterationen ist mit <math display="inline">|\mathcal{S}|</math> höchstens exponentiell, da die Anzahl der verschiedenen Policy <math display="inline">|\mathcal{A}|^{|\mathcal{S}|}</math> beträgt. Die Anzahl der Operationen ist jedoch pseudopolynomiell.


=== Modellfreie Methoden ===

Wenn kein MDP vorhanden ist, da die Zustände nicht vollständig beobachtbar (fully observable) sind, können in einigen Fällen andere Modelle etabliert werden. Bei MDP stellt die Markov-Eigenschaft sicher, dass die Zustände vollständig beobachtbar sind. Dies ist jedoch nicht immer realistisch. Wenn die Zustände nicht vollständig beobachtbar sind, dann können in einigen Fällen die teilweise beobachtbaren MDPs (partially observable MDPs - POMDPs) ermittelt werden, die die Verallgemeinerung der MDPs darstellen.

Wenn kein Modell vorhanden ist oder das Modell nicht bekannt ist, können modellfreie Methoden verwendet werden. Sie funktionieren auch, wenn es ein MDP-Modell oder ein anderes Modell als MDP, die teilweise beobachtbaren MDPs oder das Multiarmed-Bandit-Modell vorhanden ist.

Zu den wichtigsten modellfreien Algorithmen gehören:

* Temporal Difference (TD) Learning + Bootstrapping
* Q-Learning (einschließlich SARSA)
* Function approximation (Funktionsnäherung)
* Policy Based Methoden (Policy-basierte Methoden) oder Policy Optimization

Weitere Einzelheiten zu modellfreien RL-Methoden können in [Li(2018)] gefunden werden.

Reinforcement Learning - Versionsgeschichte

SAFFER Zsolt am 14. September 2024 um 23:20 Uhr