Bestärkendes Lernen

Bestärkendes Lernen oder verstärkendes Lernen (englisch reinforcement learning, RL) steht für einen Lernstil des maschinellen Lernens. Dabei führt ein Software-Agent selbständig Aktionen in einer dynamischen Umgebung aus und erlernt durch Versuch und Irrtum eine Strategie (englisch policy), die die Summe der erhaltenen Belohnungen (englisch rewards) maximiert.

Übersicht über einen typischen Ablauf beim bestärkenden Lernen: Ein Agent führt eine Aktion (Action) in einer Umgebung (Environment) aus. Er bekommt danach Rückmeldungen zu seiner Belohnung (Reward) und dem neuen Zustand (State) der Umgebung.

Der Begriff ist der Psychologie entlehnt und wurde bereits seit den Anfängen der Kybernetik verwendet. So benutzte schon Marvin Minsky den Begriff in seiner Dissertation von 1954. Die Modelle des bestärkenden Lernens versuchen, das Lernverhalten in der Natur nachzubilden.

Die Umgebung wird in der Regel als Markov-Entscheidungsproblem (MDP) beschrieben. Eine klassische Methode für das Lösen eines MDPs ist die dynamische Programmierung. Dazu muss ein genaues mathematisches Modell für das Problem bekannt sein. Außerdem ist die Zahl der Zustände, die effizient verarbeitet werden können, begrenzt. Der wesentliche Unterschied zwischen klassischen Methoden und denen des bestärkenden Lernens besteht darin, dass die Methoden des bestärkenden Lernens kein Modell für das Markov-Entscheidungsproblem voraussetzen und sie auch auf MDPs mit vielen Zuständen effizient angewendet werden können.

Zusätzlich müssen die Methoden einen Kompromiss finden zwischen dem Erkunden (englisch exploration) von noch unbekannten Zuständen und dem Ausnutzen (englisch exploitation) von erlerntem Wissen, mit dem der Agent die Summe der erhaltenen Belohnungen maximiert. Belohnungen können auch verzögert eintreffen. Eine Aktion, auf die zunächst keine hohe Belohnung erfolgt, kann zu einem Zustand führen, von dem aus mit weiteren Aktionen eine hohe Belohnung erreicht werden kann.

Beim bestärkenden Lernen wird die Theorie der optimalen Steuerung angewendet. Ein einfacher Ansatz besteht darin, beim Q-Lernen Daten zu Zuständen und Aktionen in Tabellen zu speichern, ohne ein Modell von der Umgebung zu erstellen. Dieser Ansatz funktioniert gut bei Problemstellungen, die nur wenige Zustände und Aktionen enthalten, so dass der Agent beim Lernen mit Sicherheit jeden Zustand mehrfach erreicht und darin Aktionen ausführt. Andere Methoden erstellen beim Lernen ein Modell der Umgebung.

Ein Spezialfall ist die Verwendung eines Bewertungsmodells, welches durch menschliche Interaktion mit überwachtem Lernen vorprogrammiert wird und die Interaktion mit der Umwelt ergänzt. In diesem Fall erfolgt bestärkendes Lernen durch menschlich beeinflusste Rückkopplung (englisch reinforcement learning through human feedback, (RLHF)).

Grundlagen

Die mathematischen Grundlagen des bestärkenden Lernens bilden die folgenden fünf Begriffe: Der Agent (englisch agent), die Umwelt (englisch environment), die Zustände (englisch states), die Aktionen (englisch actions) und die Belohnungen (englisch rewards). Die Methoden des bestärkenden Lernens betrachten die Interaktion des lernenden Agenten mit seiner Umwelt. Einfache Beispiele sind ein Saugroboter, dessen Belohnung in der Staubmenge besteht, die er in einer bestimmten Zeit aufsaugt oder ein beweglicher Roboter, der in einem Labyrinth steht und mit möglichst wenigen Schritten zu einem Ausgang gehen soll.

Interaktion mit der Umwelt

Die Umwelt wird in der Regel als Markow-Entscheidungsproblem (englisch markov decision process, MDP) $({\mathcal {S}},{\mathcal {A}},\rho ,\mathbb {P} _{0})$ formuliert. Die Umwelt besteht aus einer Menge von Zuständen ${\mathcal {S}}$ und einer Menge von Aktionen ${\mathcal {A}}$, sowie einer Dynamik $\rho$ und einer Startverteilung $\mathbb {P} _{0}$. Die Interaktion des Agenten mit der Umwelt findet zu diskreten Zeitpunkten $t\in \mathbb {N} _{0}$ statt. Zu jedem Zeitpunkt befindet sich der Agent in einem Zustand, wählt eine Aktion aus und erhält dafür eine reellwertige Belohnung. Da diese nicht vorhersehbar sind, fasst man sie als Zufallsvariablen $S_{t},A_{t}$ und $R_{t}$ in ${\mathcal {S}},{\mathcal {A}}$ und $\mathbb {R}$ auf. Zum Zeitpunkt $t$ befindet sich der Agent in Zustand $S_{t}$ und wählt eine Aktion $A_{t}$ gemäß einer Policy $\pi _{t}$ aus. Eine Policy $\pi _{t}$ ist eine Kollektion von Wahrscheinlichkeitsmaßen $(\pi _{t}(\cdot \mid s))_{s\in {\mathcal {S}}}$ auf ${\mathcal {A}}$. $\pi _{t}(a\mid s)$ gibt dabei die Präferenz des Agenten an, zum Zeitpunkt $t$ die Aktion $a$ zu wählen, wenn er sich in Zustand $s$ befindet. In Zufallsvariablen gesprochen bedeutet dies $A_{t}\sim \pi _{t}(\cdot \mid S_{t})$. Anschließend gibt die Umwelt eine Belohnung $R_{t}$ und einen Folgezustand $S_{t+1}$ gemäß einer Dynamik $\rho$ aus. Die Dynamik $\rho$ ist eine Kollektion von (Übergangs-)Wahrscheinlichkeitsverteilungen $(\rho (\cdot ,\cdot \mid s,a))_{(s,a)\in {\mathcal {S}}\times {\mathcal {A}}}$ auf $\mathbb {R} \times {\mathcal {S}}$. Es gilt demnach $(R_{t},S_{t+1})\sim \rho (\cdot ,\cdot |S_{t},A_{t})$. Der Zustand, in dem sich der Agent zum Zeitpunkt $t=0$ befindet, ist durch die Startverteilung $\mathbb {P} _{0}$ festgelegt: $S_{0}\sim \mathbb {P} _{0}$.

Total Discounted Reward Kriterium

Ziel des Agenten ist es, den insgesamt erwarteten Gewinn (englisch total discounted reward)

$\mathbb {E} [G_{t}]=\mathbb {E} \left[\sum _{k=0}^{T}\gamma ^{k}\cdot R_{t+k}\right]$ mit $0\leq \gamma \leq 1$

zu maximieren. Der Gewinn entspricht der Gesamtbelohnung als diskontierte Summe aller folgenden Belohnungen. Dabei gewichtet der Diskontierungsfaktor $\gamma$ zukünftige Belohnungen. Bei episodischen Problemen ($T\in \mathbb {N}$) stellt sich nach einer endlichen Anzahl von Schritten ein Endzustand ein, wie z. B. bei einer Schachpartie. Dafür eignet sich der Diskontierungsfaktor $\gamma =1$, der jede Belohnung $R_{t+k}$ gleich wertet. Bei kontinuierlichen Problemen ($T=\infty$) muss ein $\gamma <1$ gewählt werden, um Konvergenz der unendlichen Reihe $G_{t}$ zu gewährleisten. Für $\gamma =0$ zählt nur die aktuelle Belohnung $R_{t+1}$, alle zukünftigen Belohnungen werden ignoriert. Geht $\gamma$ gegen 1, plant der Agent langfristiger.

Da der Agent nur Einfluss auf die Policys $\pi _{t}$, nicht aber auf die Dynamik $\rho$ der Umwelt hat, ist das Ziel des Agenten, eine Policy $\pi$ zu finden, die den zu erwartenden Gewinn maximiert.

Lernverfahren

Zum Erlernen der Strategie des Agenten gibt es verschiedene Algorithmen. Sie lassen sich grob einteilen in modellbasiert und modellfrei. Die am häufigsten genutzten modellfreien Ansätze sind wertbasiert oder strategiebasiert. Die Mischform wird meist als Actor-Critic bezeichnet.

Modellfrei

Wertbasiert

Bekannte Beispiele sind Monte-Carlo-Methoden und Temporal Difference Learning. Bei diesen handelt es sich um Algorithmen, bei denen der Agent eine Nutzenfunktion erlernt, welche für jeden Zustand die Belohnungsaussichten der möglichen Aktionen bewertet.

Bei kleinen Zustands- oder Aktionsräumen kann dies eine Tabelle sein, deren Felder anhand der erhaltenen Belohnungen aktualisiert werden. Bei großen Zustandsräumen muss die Funktion jedoch approximiert werden. Dazu eignet sich beispielsweise die Fourierreihe oder auch ein Neuronales Netz.

Soll mehr als ein Agent lernen, kann selbst bei kooperativen Agenten, außer in trivialen Fällen, die Konvergenz der Lernvorgänge (bislang) nicht mehr garantiert werden. Trotzdem kann unter Zuhilfenahme von Heuristiken oft ein in der Praxis nützliches Verhalten gelernt werden, da der worst case selten auftritt.

Strategiebasiert

Strategiebasierte Methoden versuchen, die zu erwartende kumulative Belohnung direkt durch Parametrisierung der Strategie zu maximieren. Meistens erfolgt diese Maximierung durch stochastisch gradientbasierte Optimierung (englisch policy gradient). Prominente Vertreter dieser Klasse sind REINFORCE, Trust Region Policy Optimization (TRPO) und Proximal Policy Optimization (PPO).

Beispiel REINFORCE

Der einfach herzuleitende Algorithmus REINFORCE schätzt den Gradienten des zu erwartenden Gewinns

$\nabla _{\theta }\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}]$, um damit seine Parameter über empirisch gewinnbare Spielabläufe zu aktualisieren. Hierbei muss die Strategie $\pi _{\theta }(a|s)$ nach $\theta$ differenzierbar sein und $\tau =(s_{0},a_{0},s_{1},a_{1},\dots ,s_{T},a_{T})$ stellt einen Spielablauf dar, der aus der Wahrscheinlichkeitsverteilung $p_{\theta }$ entnommen wird. Diese setzt sich einerseits aus der Strategie $\pi _{\theta }$, als auch der möglicherweise nicht-deterministischen Umgebung $p(s'|s,a)$ (auf die der Agent keinen Einfluss hat), zusammen:

$p_{\theta }(\tau )=\mu (s_{0})\prod _{t=0}^{T}p(s_{t+1}|s_{t},a_{t})\;\pi _{\theta }(a_{t}|s_{t})$,

wobei $\mu$ eine Verteilung über den Startzustand darstellt. Über die Definition der Erwartungswerts kann nun REINFORCE wie folgt hergeleitet werden:

$\nabla _{\theta }\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}]=\nabla _{\theta }\int R_{0}\;p_{\theta }(\tau )d\tau =\int R_{0}\;\nabla _{\theta }p_{\theta }(\tau )d\tau =$:$\int R_{0}\;\nabla _{\theta }{\text{log}}(p_{\theta }(\tau ))p_{\theta }(\tau )d\tau =\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}\nabla _{\theta }{\text{log}}(p_{\theta }(\tau ))],$

wobei für die erste Gleichung die Leibnizregel verwendet wurde und für die dritte Gleichung die Regel

$\nabla _{x}{\text{log}}(f(x))={\frac {\nabla _{x}f(x)}{f(x)}}$,

wobei der natürliche Logarithmus gemeint ist. Als letzten Schritt erkennen wir, dass

$\nabla _{\theta }{\text{log}}(p_{\theta }(\tau ))=\nabla _{\theta }{\Big [}{\text{log}}(\mu (s_{0}))+\sum _{t=0}^{T}{\text{log}}(p(s_{t+1}|s_{t},a_{t}))+{\text{log}}(\pi _{\theta }(s_{t}|a_{t})){\Big ]}=\sum _{t=0}^{T}\nabla _{\theta }{\text{log}}(\pi _{\theta }(s_{t}|a_{t}))$.

Nun kann man einen erwartungstreuen Schätzer ${\hat {\nabla }}_{\theta }\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}]$ des Gradienten des zu erwartenden Gewinns erhalten, indem man erst einen Spielablauf $\tau$ mit dem Agenten generiert und einsetzt:

${\hat {\nabla }}_{\theta }\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}]=R_{0}\cdot \sum _{t=0}^{T}\nabla _{\theta }{\text{log}}(\pi _{\theta }(a_{t}|s_{t}))$.

Der Parameterupdate mit Lernrate $\eta$ erfolgt dann wie folgt:

$\theta _{t+1}\leftarrow \theta _{t}+\eta {\hat {\nabla }}_{\theta }\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}]$.

Modellbasiert

Modellbasierte Verfahren konstruieren ein prädiktives Modell ihrer Umwelt. Dies bedeutet, dass der Agent Vorhersagen für Anfragen der Art „Was wird passieren, wenn ich eine bestimmte Aktion ausführe?“ generieren kann. Das Modell stellt somit einen (gelernten oder bekannten) reversiblen Zugang zur Umgebungsdynamik dar, da der Agent eine Vorhersage zu jedem beliebigen Zustands-Aktions-Paar ermitteln kann und nicht an die durch den Spielablauf vorgegebene Ordnung gebunden ist. Anders als in modellfreien Ansätzen ermöglicht das Modell explizites Planen. Dies wird in Algorithmen wie z. B. MuZero von Deepmind genutzt, um ein präzise Vorausberechnung zu ermöglichen, die in einigen Spielen wie Schach oder Go von besonderer Relevanz ist. Eine andere Klasse von Methoden, welche auf dem Dyna-Algorithmus basiert, kombiniert den modellbasierten mit dem modellfreien Ansatz, indem sie das gelernte Modell nutzt, um künstliche (halluzinierte) Daten zu generieren. Diese werden dann wiederum zum Lernen einer Strategie und/oder Wertfunktion eingesetzt.

Forschende erhoffen sich, dass modellbasierte RL-Methoden künftig noch mehr zum Verständnis realer Kausalitäten medizinischer, sozial- und wirtschaftswissenschaftlicher Wissenschaftszweige oder Politikgestaltung beitragen können (causal machine learning), deren Themenfelder bisher über wenige inhaltliche und personelle Überschneidungen verfügen.

Literatur

• Richard Sutton, Andrew Barto: Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
• Dimitri P. Bertsekas, John Tsitsiklis: Neuro-Dynamic Programming. Athena Scientific, Cambridge, MA, 1996.
• Csaba Szepesvári, Algorithms for Reinforcement Learning, Morgan and Claypool, 2010 (ualberta.ca PDF).
• Marc Patrick Deisenroth, Gerhard Neumann, Jan Peters: A Survey on Policy Search for Robotics. Foundations and Trends in Robotics, 21, S. 388–403, 2013 (ausy.tu-darmstadt.de PDF).
• Jens Kober, Drew Bagnell, Jan Peters: Reinforcement Learning in Robotics: A Survey. International Journal of Robotics Research, 32, 11, S. 1238–1274, 2013 (ausy.tu-darmstadt.de PDF).
• Uwe Lorenz: Reinforcement Learning: Aktuelle Ansätze verstehen – mit Beispielen in Java und Greenfoot. (aktual. 2. Auflage) Springer Vieweg, 2024, ISBN 978-3-662-68311-8
• Warren B. Powell: Approximate Dynamic Programming. John Wiley and Sons, 2011.
• Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz. Pearson Studium, August 2004, ISBN 3-8273-7089-2 (deutsche Übersetzung der 2. Auflage) Kapitel 21.

Weblinks

• Introduction to reinforcement learning by openAI
• Tutorial zu Reinforcement Learning (englisch, PDF; 101 kB)
• Artikel. In: Scholarpedia. (englisch, inkl. Literaturangaben)
• Der Computer macht sich selbst schlau. In: NZZ, 20. Oktober 2017. Abgerufen am 12. August 2023