„Bestärkendes Lernen“ – Versionsunterschied

Bestärkendes Lernen oder verstärkendes Lernen (englisch reinforcement learning) steht für eine Reihe von Methoden des maschinellen Lernens, bei denen ein Agent selbstständig eine Strategie (englisch policy) erlernt, um erhaltene Belohnungen zu maximieren. Dabei wird dem Agenten nicht vorgezeigt, welche Aktion in welcher Situation die beste ist, sondern er erhält durch die Interaktion mit seiner Umwelt zu bestimmten Zeitpunkten eine Belohnung, die auch negativ sein kann.

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.^[1] Die Modelle des bestärkenden Lernens versuchen das Lernverhalten in der Natur nachzubilden.

Modell

Die Methoden des bestärkenden Lernens betrachten die Interaktion eines lernenden Agenten mit seiner Umwelt. Letztere ist dabei als Markow-Entscheidungsproblem formuliert. So besitzt die Umwelt eine Menge von Zuständen $S$ . Der Agent kann situativ, $s_{t}\in S$ , eine Aktion, $a_{t}\in A(s_{t})$ , aus einer Menge von verfügbaren Aktionen wählen, wodurch er in einen Folgezustand $s_{t+1}\in S$ gelangt und eine Belohnung $r_{t+1}\in \mathbb {R}$ erhält.

Ziel des Agenten ist es, den zukünftig zu erwarteten Gewinn

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

mit

0\leq \gamma \leq 1

zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man $\gamma$ den Diskontierungsfaktor, der zukünftige Belohnungen gewichtet. Bei episodischen Problemen, d. h. die Welt geht nach einer endlichen Anzahl von Schritten in einen Endzustand über (wie z. B. eine Schachpartie), eignet sich der Diskontierungsfaktor $\gamma =1$ . In diesem Fall wird jede Belohnung $r_{t+k+1}$ gleich gewertet. Bei kontinuierlichen Problemen ( $T=\infty$ ) muss man ein $\gamma <1$ wählen, damit die unendliche Reihe $R_{t}$ konvergiert. Für $\gamma =0$ zählt nur die aktuelle Belohnung $r_{t+1}$ ; alle zukünftigen Belohnungen werden ignoriert. Geht $\gamma$ gegen 1, wird der Agent weitsichtiger.

Zu diesem Zweck verfolgt der Agent eine Strategie (englisch policy), die er laufend verbessert. Üblicherweise wird die Strategie als eine Funktion $\pi \colon S\rightarrow A$ betrachtet, die jedem Zustand eine Aktion zuweist. Jedoch sind auch nichtdeterministische Strategien (oder gemischte Strategien) möglich, sodass eine Aktion mit einer bestimmten Wahrscheinlichkeit ausgewählt wird. Im Allgemeinen wird eine Strategie demnach als bedingte Wahrscheinlichkeitsverteilung definiert: $\pi (s,a)=p(a|s)\quad$ ^[2]

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 modellfreie Ansätze sind wertbasiert oder strategiebasiert. Die Mischform wird meist als Actor-Critic bezeichnet.^[3]

Modellbasiert

Wertbasiert

Bekannte Beispiele sind Monte-Carlo-Methoden und Temporal Difference Learning. Bei diesen handelt es sich um Algorithmen, bei denen der Agent eine Nutzenfunktion besitzt, welche einen bestimmten Zustand oder eine bestimmte Aktion in einem Zustand bewertet.

Bei kleinen Zustands- oder Aktionsräumen kann dies eine Tabelle sein, deren Felder anhand der erhaltenen Belohnung 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.^[4]

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^[5] 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}]

.

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. Springer Vieweg, 2020, ISBN 978-3-662-61651-2
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

Tutorial zu Reinforcement Learning (englisch, PDF; 101 kB)
Artikel. In: Scholarpedia. (englisch, inkl. Literaturangaben)
Blogbeitrag zum Thema Reinforcement Learning mit Beispiel

Einzelnachweise

↑ Richard Sutton: Reinforcement Learning FAQ. 2. April 2004, archiviert vom Original (nicht mehr online verfügbar) am 28. August 2016; abgerufen am 21. April 2016 (englisch).
↑ Michel Tokic: Reinforcement Learning mit adaptiver Steuerung von Exploration und Exploitation. Ulm 2013, doi:10.18725/oparu-2517 (PhD thesis, Universität Ulm, Institut für Neuroinformatik).
↑ Sergey Levine: Actor-Critic Algorithms. In: Actor-Critic Algorithms. UC Berkley, abgerufen am 27. Dezember 2021 (englisch).
↑ J. F. Knabe: Kooperatives Reinforcement Lernen in Multiagentensystemen. B. Sc. Thesis, Universität Osnabrück, 2005 (panmental.de PDF)
↑ Ronald J. Williams: Simple statistical gradient-following algorithms for connectionist reinforcement learning. In: Machine Learning. Band 8, Nr. 3, 1. Mai 1992, ISSN 1573-0565, S. 229–256, doi:10.1007/BF00992696.

[1] Richard Sutton: Reinforcement Learning FAQ. 2. April 2004, archiviert vom Original (nicht mehr online verfügbar) am 28. August 2016; abgerufen am 21. April 2016 (englisch).

[2] Michel Tokic: Reinforcement Learning mit adaptiver Steuerung von Exploration und Exploitation. Ulm 2013, doi:10.18725/oparu-2517 (PhD thesis, Universität Ulm, Institut für Neuroinformatik).

[3] Sergey Levine: Actor-Critic Algorithms. In: Actor-Critic Algorithms. UC Berkley, abgerufen am 27. Dezember 2021 (englisch).

[4] J. F. Knabe: Kooperatives Reinforcement Lernen in Multiagentensystemen. B. Sc. Thesis, Universität Osnabrück, 2005 (panmental.de PDF)

[5] Ronald J. Williams: Simple statistical gradient-following algorithms for connectionist reinforcement learning. In: Machine Learning. Band 8, Nr. 3, 1. Mai 1992, ISSN 1573-0565, S. 229–256, doi:10.1007/BF00992696.

[1]

[2]

[3]

[4]

[5]

@@ Zeile 7: / Zeile 7: @@
 Ziel des Agenten ist es, den zukünftig zu erwarteten Gewinn
-: <math>\mathbb{E}[R_t] = \mathbb{E}\left[\sum_{k=0}^T \gamma^k\cdot r_{t+k+1}\right]</math> mit <math> 0\le\gamma\le 1</math>
+: <math>\mathbb{E}[R_t] = \mathbb{E}\left[\sum_{k=0}^T \gamma^k\cdot r_{t+k+1}\right]</math> mit <math> 0 \le \gamma \le 1</math>
-zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man <math>\gamma\,\!</math> den [[Diskontierungsfaktor]], der zukünftige Belohnungen gewichtet. Bei episodischen Problemen, d.&nbsp;h. die Welt geht nach einer endlichen Anzahl von Schritten in einen Endzustand über (wie z.&nbsp;B. eine Schachpartie), eignet sich der Diskontierungsfaktor <math>\gamma=1\,\!</math>. In diesem Fall wird jede Belohnung <math>r_{t+k+1}\,\!</math> gleich gewertet. Bei kontinuierlichen Problemen (<math>T=\infty</math>) muss man ein <math>\gamma<1\,\!</math> wählen, damit die unendliche Reihe <math>R_t\,\!</math> konvergiert. Für <math>\gamma=0\,\!</math> zählt nur die aktuelle Belohnung <math>r_{t+1}\,\!</math>; alle zukünftigen Belohnungen werden ignoriert. Geht <math>\gamma\,\!</math> gegen 1, wird der Agent weitsichtiger.
+zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man <math>\gamma</math> den [[Diskontierungsfaktor]], der zukünftige Belohnungen gewichtet. Bei episodischen Problemen, d.&nbsp;h. die Welt geht nach einer endlichen Anzahl von Schritten in einen Endzustand über (wie z.&nbsp;B. eine Schachpartie), eignet sich der Diskontierungsfaktor <math>\gamma=1</math>. In diesem Fall wird jede Belohnung <math>r_{t+k+1}</math> gleich gewertet. Bei kontinuierlichen Problemen (<math>T=\infty</math>) muss man ein <math>\gamma < 1</math> wählen, damit die unendliche Reihe <math>R_t</math> konvergiert. Für <math>\gamma = 0</math> zählt nur die aktuelle Belohnung <math>r_{t+1}</math>; alle zukünftigen Belohnungen werden ignoriert. Geht <math>\gamma</math> gegen 1, wird der Agent weitsichtiger.
 Zu diesem Zweck verfolgt der Agent eine ''Strategie'' (englisch ''{{lang|en|policy}}''), die er laufend verbessert. Üblicherweise wird die Strategie als eine Funktion <math>\pi\colon S \rightarrow A </math> betrachtet, die jedem Zustand eine Aktion zuweist. Jedoch sind auch nichtdeterministische Strategien (oder [[Strategie (Spieltheorie)#Reine und gemischte Strategien|gemischte Strategien]]) möglich, sodass eine Aktion mit einer bestimmten Wahrscheinlichkeit ausgewählt wird. Im Allgemeinen wird eine Strategie demnach als bedingte Wahrscheinlichkeitsverteilung definiert:
@@ Zeile 31: / Zeile 31: @@
 Der einfach herzuleitende Algorithmus REINFORCE<ref>{{Literatur |Autor=Ronald J. Williams |Titel=Simple statistical gradient-following algorithms for connectionist reinforcement learning |Sammelwerk=Machine Learning |Band=8 |Nummer=3 |Datum=1992-05-01 |ISSN=1573-0565 |DOI=10.1007/BF00992696 |Seiten=229–256}}</ref> schätzt den Gradienten des zu erwartenden Gewinns
-<math>\nabla_{\theta}\mathbf{E}_{\tau \sim p_\theta}[R_0]</math>, um damit seine Parameter über empirisch gewinnbare Spielabläufe zu aktualisieren. Hierbei muss die Strategie <math>\pi_{\theta}(a|s)</math> nach <math>\theta</math> differenzierbar sein und <math>\tau = (s_0, a_0, s_1, a_1, ..., s_T, a_T)</math> stellt einen Spielablauf dar, der aus der Wahrscheinlichkeitsverteilung <math>p_\theta</math> entnommen wird. Diese setzt sich einerseits aus der Strategie <math>\pi_{\theta}</math>, als auch der möglicherweise nicht-deterministischen Umgebung <math>p(s'|s, a)</math> (auf die der Agent keinen Einfluss hat), zusammen:
+<math>\nabla_{\theta}\mathbf{E}_{\tau \sim p_\theta}[R_0]</math>, um damit seine Parameter über empirisch gewinnbare Spielabläufe zu aktualisieren. Hierbei muss die Strategie <math>\pi_{\theta}(a|s)</math> nach <math>\theta</math> differenzierbar sein und <math>\tau = (s_0, a_0, s_1, a_1, \dots, s_T, a_T)</math> stellt einen Spielablauf dar, der aus der Wahrscheinlichkeitsverteilung <math>p_\theta</math> entnommen wird. Diese setzt sich einerseits aus der Strategie <math>\pi_{\theta}</math>, als auch der möglicherweise nicht-deterministischen Umgebung <math>p(s'|s, a)</math> (auf die der Agent keinen Einfluss hat), zusammen:
-<math>p_\theta (\tau) = \mu(s_0) \prod_{t=0}^T p(s_{t+1}|s_t, a_t) \; \pi_\theta (a_t | s_{t})</math>,
+:<math>p_\theta (\tau) = \mu(s_0) \prod_{t=0}^T p(s_{t+1}|s_t, a_t) \; \pi_\theta (a_t | s_{t})</math>,
 wobei <math>\mu</math> eine Verteilung über den Startzustand darstellt. Über die Definition der Erwartungswerts kann nun REINFORCE wie folgt hergeleitet werden:
-<math>\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 =</math><math>\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))],</math>
+:<math>\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 =</math>:<math>\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))],</math>
-wobei für die erste Gleichung die [[Parameterintegral|Leibnizregel]] verwendet wurde und für die dritte Gleichung die Regel <math>\nabla_x \text{log}(f(x)) = \frac{\nabla_x f(x)}{f(x)}</math>, wobei der [[Natürlicher Logarithmus|natürliche Logarithmus]] gemeint ist. Als letzten Schritt erkennen wir, dass
+wobei für die erste Gleichung die [[Parameterintegral|Leibnizregel]] verwendet wurde und für die dritte Gleichung die Regel
+:<math>\nabla_x \text{log}(f(x)) = \frac{\nabla_x f(x)}{f(x)}</math>,
+wobei der [[Natürlicher Logarithmus|natürliche Logarithmus]] gemeint ist. Als letzten Schritt erkennen wir, dass
-<math>\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))</math>.
+:<math>\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))</math>.
 Nun kann man einen [[Erwartungstreue|erwartungstreuen]] Schätzer <math>\hat{\nabla}_\theta \mathbf{E}_{\tau \sim p_\theta}[R_0]</math> des Gradienten des zu erwartenden Gewinns erhalten, indem man erst einen Spielablauf <math>\tau</math> mit dem Agenten generiert und einsetzt:
-<math>\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)) </math>.
+:<math>\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)) </math>.
 Der Parameterupdate mit Lernrate <math>\eta </math> erfolgt dann wie folgt:
-<math>\theta_{t+1} \leftarrow \theta_t + \eta \hat{\nabla}_\theta \mathbf{E}_{\tau \sim p_\theta}[R_0]</math>.
+:<math>\theta_{t+1} \leftarrow \theta_t + \eta \hat{\nabla}_\theta \mathbf{E}_{\tau \sim p_\theta}[R_0]</math>.
 == Literatur ==

C (Programmiersprache)

„Bestärkendes Lernen“ – Versionsunterschied

Version vom 9. April 2022, 10:14 Uhr

Inhaltsverzeichnis

Modell