Reinforcement Learning

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle t} in einem Zustand ${\textstyle s_{t}}$ , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s_t \in \mathcal{S}} . Der Agent führt eine Aktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a_t} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a_t \in \mathcal{A}} aus den erlaubten Aktionen im Zustand ${\textstyle s_{t}}$ aus. Als Reaktion der Umgebung auf diese Aktion erhält der Agent eine Belohnung (reward) ${\textstyle r_{t}}$, ${\textstyle r_{t}\in {\mathcal {R}}}$ und der Zustand des Agenten ändert sich im nächsten Zeitschritt ${\textstyle t+1}$ zu ${\textstyle s_{t+1}}$ . 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 ${\textstyle r(s_{t},a_{t})}$ und die Zustandsänderungen durch Zustandsübergangswahrscheinlichkeiten
${\textstyle p(s_{t+1}|s_{t},a_{t})}$ beschrieben. Die RL-Literatur hinsichtlich des Zusammenhangs der unmittelbaren Belohnung zur Zeit ${\textstyle t}$ oder ${\textstyle t+1}$ nicht einheitlich ist. Während der gesamten Diskussion von RL übernehmen wir die Assoziation der unmittelbaren Belohnung zum Zeitschritt ${\textstyle t}$. Somit wird die diskontierte, akkumulierte Belohnung im Zeitschritt ${\textstyle t}$, ${\textstyle t\in N^{+}}$ durch

$$R_{t}=\sum _{\tau =0}^{\infty }\gamma ^{\tau }r_{t+\tau }$$

ausgedrückt, wobei ${\textstyle \gamma \in (0,1]}$ der Abzinsungsfaktor ist. Das Verhalten des Agenten wird durch die Wahrscheinlichkeiten ${\textstyle p(a|s)}$ für ${\textstyle s\in {\mathcal {S}}}$ und ${\textstyle a\in {\mathcal {A}}}$ 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 ${\textstyle \pi }$ verwendet wird. Dann das Ziel des Agenenten kann als ein Optimierungsproblem, wie folgt,

$$\arg \max _{\pi }E[R_{t}|s_{t},\pi ]$$

formuliert werden, wobei ${\textstyle E[]}$ 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:

1. das Modell (model),
2. die Strategy (policy),
3. die Wertfunktion (value function) und
4. die Aktionswertfunktion (action value function).

Das Modell beschreibt die Umgebungsdynamik und wird durch die Belohnungsfunktion ${\textstyle r(s,a)}$ und die Übergangswahrscheinlichkeiten der Zuständen
${\textstyle p(s^{'}|s,a)}$ gegeben. Alternativ kann es in kompakter Form durch die Funktion ${\textstyle p(s^{'},r|s,a)}$ 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 ${\textstyle \pi }$ eine Abbildung, die jedem Zustand ${\textstyle s\in {\mathcal {S}}}$ die Wahrscheinlichkeitsverteilung ${\textstyle p(a|s)}$, ${\textstyle a\in {\mathcal {A}}}$ 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 ${\textstyle a=\pi (s)}$ für ${\textstyle a\in {\mathcal {A}}}$ und ${\textstyle s\in {\mathcal {S}}}$.

${\textstyle \mathrm {\ \ \ \ } }$ 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: ${\textstyle V_{\pi }(s)}$ oder ${\textstyle V(s)}$. Basierend auf der obigen Definition kann es formal durch

$$V_{\pi }(s)=E[R_{t}|s_{t}=s,\pi ]$$

gegeben sein.

${\textstyle \mathrm {\ \ \ \ } }$ 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 ${\textstyle Q_{\pi }(s,a)}$ oder einfach ${\textstyle Q(s,a)}$ bezeichnet und ist formal durch

$$Q_{\pi }(s,a)=E[R_{t}|s_{t}=s,a_{t}=a,\pi ]$$

gegeben.

${\textstyle \mathrm {\ \ \ \ } }$ 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

$${\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}}$$

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.

${\textstyle \mathrm {\ \ \ \ } }$ Optimale Wertfunktion

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

$$V^{*}(s)=\max _{\pi }V_{\pi }(s).$$

Auch ${\textstyle V^{*}(s)}$ kann auf rekursive Weise ausgedrückt werden, was durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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}} gegeben werden kann.

Dies ist ebenfalls eine Bellman-Gleichung. Der Ausdruck von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)} beinhaltet implizit, dass zunächst (im Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s} ) die beste Aktion ausgeführt wird. Dies liegt daran, dass die gewichtete Summe in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V_{\pi}(s)} mit Wahrscheinlichkeitsgewichten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p(a|s)} kann als Interpolation interpretiert werden, weil Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \sum_{a \in \mathcal{A}} p(a|s) = 1} . Daher ist das Maximum der gewichteten Summe der höchste Wert in der Summe mit dem Wahrscheinlichkeitsgewicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 1} . Dies bedeutet, dass das Ergreifen der besten Maßnahme zunächst impliziert, dass die resultierende optimale Policy deterministisch ist.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Optimale Aktionswertfunktion

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^*(s,a) = \max_{\pi} Q_{\pi}(s, a)} gegeben.

Beobachte, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)} der Wert ist, bei dem zunächst die beste Aktion durchgeführt wurde. Daraus folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^*(s) = \max_{a} Q^*(s,a) \label{opV_opQ}} in Beziehung gesetzt werden kann.

Die Bellman-Gleichung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} kann wie folgt angegeben werden: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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}}

Auch hier wird zunächst die beste Aktion ausgeführt, jetzt im Zustand ${\textstyle s^{'}}$, da dies der erste Zustand ist, in dem eine Aktion ausgewählt werden muss (die Aktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} im Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s} ist bereits gegeben).

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Optimale Policy

Die optimale (deterministische) Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi^*(s)} kann aus der optimalen Aktionswertfunktion als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^*(s) = \arg \max_{a} Q^*(s,a) \label{opPol_opQ}} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^*(s,a) = r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V^*(s^{'}).}

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle T} zurückgesetzt wird, dann ist das MDP episodisch mit einer Episode der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle T} . 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = \sum_{t = 0}^{T-1} \gamma^{t} r_{t}} gegeben. Im nicht-episodischen MDP Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle T=\infty} . In diesem Fall stellt die Einstellung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \gamma < 1} die Endlichkeit der diskontierten, akkumulierten Belohnung sicher.

Wenn das Modell gegeben ist, sind die Belohnungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle r(s,a)} und die Übergangswahrscheinlichkeiten ${\textstyle p(s^{'}|s,a)}$ 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.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Value iteration

Die Wertfunktion kann iterativ für alle Zustände aus der Bellman-Gleichung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} , kombiniert mit der Beziehung zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} , 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle r(s,a)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s \in \mathcal{S}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a \in \mathcal{A}} ,
- die Übergangswahrscheinlichkeiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p(s^{'}|s,a)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s, s^{'} \in \mathcal{S}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a \in \mathcal{A}} .
Ausgabe: die optimale Wertfunktion ${\textstyle V^{*}(s)}$ für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s \in \mathcal{S}} .
—————————————————————————————
1 Initialisierung von ${\textstyle V(s)}$ mit einer beliebigen nicht negativen Funktion
2 Wenn das Stoppkriterium NICHT erfüllt ist
3   for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s \in \mathcal{S}}
4     for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a \in \mathcal{A}}
5       Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q(s,a) = r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V(s^{'})}
6     end
7     Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V(s^{'})= \max_{a^{'}} Q(s^{'}, a^{'})}
8   end
9 end
—————————————————————————————
Es kann gezeigt werden, dass der Algorithmus immer gegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)}
([Bellman(1957)], [Bertsekas(1987)]) konvergiert. Die optimale Policy kann aus dem berechneten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} bestimmt werden. Dies ist ein Greedy Algorithmus, da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \epsilon} -Wert ist.

Die numerische Komplexität des Algorithmus beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathcal{O}(|\mathcal{S}|^2 |\mathcal{A}| I)} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle I} die Anzahl der erforderlichen Iterationen ist.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} mit der Beziehung zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V^*(s)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle Q^*(s,a)} erhalten wird. Dies führt zu

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^*(s) = \arg \max_{a} \left(r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi^*}^*(s^{'}) \right).}

Die rekursive Berechnung der nächsten Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi^{'}} basierend auf der obigen Gleichung erfordert die Berechnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V_{\pi}(s^{'})} für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s^{'} \in \mathcal {S}} aus der tatsächlichen Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi(s)} . Dies kann erreicht werden, indem die Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi} auf die Bellman-Gleichungen der Wertfunktion angewendet und für die Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V_{\pi}(s^{'})} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle r(s,a)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s \in \mathcal{S}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a \in \mathcal{A}} ,
- die Übergangswahrscheinlichkeiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p(s^{'}|s,a)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s, s^{'} \in \mathcal{S}} und ${\textstyle a\in {\mathcal {A}}}$.
Ausgabe: die optimale Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi^*(s)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s \in \mathcal{S}} .
—————————————————————————————
1 Auswählen eine beliebige Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi^{'}(s)} und Einstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi \neq \pi^{'}}
2 while Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi^{'} \neq \pi}
3 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi = \pi^{'}}
4 Berechnen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V_{\pi}(s^{'})} aus der Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi} , durch Lösung eines linearen Gleichungssystems lösen
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ \ \ }}   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle V_{\pi}(s) = \left(r(s,\pi(s)) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi}(s^{'}) \right)}
5 Aktualisieren die Policy als
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ \ \ }}   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi^{'}(s) = \arg \max_{a} \left(r(s,a) + \gamma \sum_{s^{'} \in \mathcal{S}} p(s^{'}|s,a) V_{\pi}(s^{'})\right)} for every Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle s \in \mathcal{S}}
6 end
—————————————————————————————
Das Aktualisieren der Policy bedeutet, die beste erste Aktion anstelle der zuvor von der Policy verwendeten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \pi(s)} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle |\mathcal{S}|} höchstens exponentiell, da die Anzahl der verschiedenen Policy Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle |\mathcal{A}|^{|\mathcal{S}|}} 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.