Bestärkendes Lernen

Ziel des Agenten ist es, den zukünftig zu erwarteten Gewinn (englisch total discounted reward)

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

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

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

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.[5]

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).

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

${\displaystyle \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 ${\displaystyle \pi _{\theta }(a|s)}$ nach ${\displaystyle \theta }$ differenzierbar sein und ${\displaystyle \tau =(s_{0},a_{0},s_{1},a_{1},\dots ,s_{T},a_{T})}$ stellt einen Spielablauf dar, der aus der Wahrscheinlichkeitsverteilung ${\displaystyle p_{\theta }}$ entnommen wird. Diese setzt sich einerseits aus der Strategie ${\displaystyle \pi _{\theta }}$, als auch der möglicherweise nicht-deterministischen Umgebung ${\displaystyle p(s'|s,a)}$ (auf die der Agent keinen Einfluss hat), zusammen:

${\displaystyle 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 ${\displaystyle \mu }$ eine Verteilung über den Startzustand darstellt. Über die Definition der Erwartungswerts kann nun REINFORCE wie folgt hergeleitet werden:

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

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

${\displaystyle \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 ${\displaystyle {\hat {\nabla }}_{\theta }\mathbf {E} _{\tau \sim p_{\theta }}[R_{0}]}$ des Gradienten des zu erwartenden Gewinns erhalten, indem man erst einen Spielablauf ${\displaystyle \tau }$ mit dem Agenten generiert und einsetzt:

${\displaystyle {\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 ${\displaystyle \eta }$ erfolgt dann wie folgt:

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

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.[7] 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.[8] 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.[9] Eine andere Klasse von Methoden, welche auf dem Dyna-Algorithmus[10] 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.[11]

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.[12]