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 ${\textstyle t}$ in einem Zustand ${\textstyle s_{t}}$ , wobei ${\textstyle s_{t}\in {\mathcal {S}}}$. Der Agent führt eine Aktion ${\textstyle a_{t}}$, ${\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

$${\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 ${\textstyle V^{*}(s)}$ beinhaltet implizit, dass zunächst (im Zustand ${\textstyle s}$) die beste Aktion ausgeführt wird. Dies liegt daran, dass die gewichtete Summe in ${\textstyle V_{\pi }(s)}$ mit Wahrscheinlichkeitsgewichten ${\textstyle p(a|s)}$ kann als Interpolation interpretiert werden, weil ${\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 ${\textstyle 1}$. Dies bedeutet, dass das Ergreifen der besten Maßnahme zunächst impliziert, dass die resultierende optimale Policy deterministisch ist.

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

$$Q^{*}(s,a)=\max _{\pi }Q_{\pi }(s,a)$$

gegeben.

Beobachte, dass ${\textstyle V^{*}(s)}$ der Wert ist, bei dem zunächst die beste Aktion durchgeführt wurde. Daraus folgt, dass ${\textstyle V^{*}(s)}$ mit ${\textstyle Q^{*}(s,a)}$ als

$$V^{*}(s)=\max _{a}Q^{*}(s,a)$$

in Beziehung gesetzt werden kann.

Die Bellman-Gleichung für ${\textstyle Q^{*}(s,a)}$ kann wie folgt angegeben werden:

$${\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 ${\textstyle a}$ im Zustand ${\textstyle s}$ ist bereits gegeben).

${\textstyle \mathrm {\ \ \ \ } }$ Optimale Policy

Die optimale (deterministische) Policy ${\textstyle \pi ^{*}(s)}$ kann aus der optimalen Aktionswertfunktion als

$$\pi ^{*}(s)=\arg \max _{a}Q^{*}(s,a)$$

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

$$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 ${\textstyle T}$ zurückgesetzt wird, dann ist das MDP episodisch mit einer Episode der Länge ${\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

$$R=\sum _{t=0}^{T-1}\gamma ^{t}r_{t}$$

gegeben. Im nicht-episodischen MDP ${\textstyle T=\infty }$. In diesem Fall stellt die Einstellung ${\textstyle \gamma <1}$ die Endlichkeit der diskontierten, akkumulierten Belohnung sicher.

Wenn das Modell gegeben ist, sind die Belohnungsfunktion ${\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.

${\textstyle \mathrm {\ \ \ \ } }$ Value iteration

Die Wertfunktion kann iterativ für alle Zustände aus der Bellman-Gleichung für ${\textstyle Q^{*}(s,a)}$, kombiniert mit der Beziehung zwischen ${\textstyle V^{*}(s)}$ und ${\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 ${\textstyle r(s,a)}$ für ${\textstyle s\in {\mathcal {S}}}$ und ${\textstyle a\in {\mathcal {A}}}$,
- die Übergangswahrscheinlichkeiten ${\textstyle p(s^{'}|s,a)}$ für ${\textstyle s,s^{'}\in {\mathcal {S}}}$ und ${\textstyle a\in {\mathcal {A}}}$.
Ausgabe: die optimale Wertfunktion ${\textstyle V^{*}(s)}$ für ${\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 ${\textstyle s\in {\mathcal {S}}}$
4     for ${\textstyle a\in {\mathcal {A}}}$
5       ${\textstyle Q(s,a)=r(s,a)+\gamma \sum _{s^{'}\in {\mathcal {S}}}p(s^{'}|s,a)V(s^{'})}$
6     end
7     ${\textstyle V(s^{'})=\max _{a^{'}}Q(s^{'},a^{'})}$
8   end
9 end
—————————————————————————————
Es kann gezeigt werden, dass der Algorithmus immer gegen ${\textstyle V^{*}(s)}$
([Bellman(1957)], [Bertsekas(1987)]) konvergiert. Die optimale Policy kann aus dem berechneten ${\textstyle Q^{*}(s,a)}$ bestimmt werden. Dies ist ein Greedy Algorithmus, da ${\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 ${\textstyle \epsilon }$-Wert ist.

Die numerische Komplexität des Algorithmus beträgt ${\textstyle {\mathcal {O}}(|{\mathcal {S}}|^{2}|{\mathcal {A}}|I)}$, wobei ${\textstyle I}$ die Anzahl der erforderlichen Iterationen ist.

${\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 ${\textstyle Q^{*}(s,a)}$ mit der Beziehung zwischen ${\textstyle V^{*}(s)}$ und ${\textstyle Q^{*}(s,a)}$ erhalten wird. Dies führt zu

$$\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 ${\textstyle \pi ^{'}}$ basierend auf der obigen Gleichung erfordert die Berechnung von ${\textstyle V_{\pi }(s^{'})}$ für jedes ${\textstyle s^{'}\in {\mathcal {S}}}$ aus der tatsächlichen Policy ${\textstyle \pi (s)}$. Dies kann erreicht werden, indem die Policy ${\textstyle \pi }$ auf die Bellman-Gleichungen der Wertfunktion angewendet und für die Werte ${\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 ${\textstyle r(s,a)}$ für ${\textstyle s\in {\mathcal {S}}}$ und ${\textstyle a\in {\mathcal {A}}}$,
- die Übergangswahrscheinlichkeiten ${\textstyle p(s^{'}|s,a)}$ für ${\textstyle s,s^{'}\in {\mathcal {S}}}$ und ${\textstyle a\in {\mathcal {A}}}$.
Ausgabe: die optimale Policy ${\textstyle \pi ^{*}(s)}$ für ${\textstyle s\in {\mathcal {S}}}$.
—————————————————————————————
1 Auswählen eine beliebige Policy ${\textstyle \pi ^{'}(s)}$ und Einstellen ${\textstyle \pi \neq \pi ^{'}}$
2 while ${\textstyle \pi ^{'}\neq \pi }$
3 ${\textstyle \pi =\pi ^{'}}$
4 Berechnen ${\textstyle V_{\pi }(s^{'})}$ aus der Policy ${\textstyle \pi }$, durch Lösung eines linearen Gleichungssystems lösen
${\textstyle \mathrm {\ \ \ \ \ \ } }$  ${\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
${\textstyle \mathrm {\ \ \ \ \ \ } }$  ${\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 ${\textstyle s\in {\mathcal {S}}}$
6 end
—————————————————————————————
Das Aktualisieren der Policy bedeutet, die beste erste Aktion anstelle der zuvor von der Policy verwendeten ${\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 ${\textstyle |{\mathcal {S}}|}$ höchstens exponentiell, da die Anzahl der verschiedenen Policy ${\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.