Bestärkendes Lernen

Bestärkendes Lernen bzw. Verstärkendes Lernen (engl. Reinforcement Learning) ist eine Variante des Maschinellen Lernens, bei dem ein Agent (ein Computerprogramm) lediglich durch ein System von Belohnung und Bestrafung lernt, seinen Nutzen zu optimieren.

Einführung

Betrachtet ein wird dynamisches System - bestehend aus einem Agenten und seiner Umgebung (der Welt) - in diskreten Zeitschritten $t=0,1,2,...$ . Zu jedem Zeitpunkt $t$ befindet sich die Welt im einem Zustand $z_{t}\in Z$ und der Agent wählt eine Aktion $a_{t}\in A(z_{t})$ aus. Daraufhin geht die Welt in den Zustand $z_{t+1}\in Z$ und der Agent erhält eine Belohnung $b_{t}\in B$ .

Erwarteter Gewinn

Ziel ist es den erwarteten Gewinn (engl. expected return)

B_{t}=\sum _{k=0}^{N}\delta ^{k}\cdot b_{t+k+1}

mit

0\leq \delta \leq 1

zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man $\delta$ den Diskontierungsfaktor (engl. discount factor). 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 $\delta =1$ . In diesem Fall wird jede Belohnung $b_{t+k+1}$ gleich gewertet. Bei kontinuierlichen Problemen ( $N=\infty$ ) muss man ein $\delta <1$ wählen, damit die unendliche Reihe $B_{t}$ konvergiert. Für $\delta =0$ zählt nur die aktuelle Belohnung $b_{t}$ ; alle zukünftigen Belohnungen werden ignoriert. Geht $\delta$ gegen 1 wird der Agent weitsichtiger.

Strategien

Beim Bestärkenden Lernen verfolgt der Agent eine Strategie (engl. policy). Üblicherweise wird die Strategie als eine Funktion $s:Z\rightarrow A(Z)$ betrachtet, die jedem Zustand eine Aktion zuweist. Jedoch sind auch nichtdeterministische Strategien (oder gemischte Strategien) möglich, so dass eine Aktion mit einer bestimmten Wahrscheinlichkeit ausgewählt wird. Im allgemeinen wird eine Strategie demnach als bedingte Wahrscheinlichkeitsverteilung definiert: $s(z,a)=p(a|s)\quad$ .

Zustands-Bewertungsfunktion

...

Markow-Entscheidungsprozess

Bestärkendes Lernen wird häufig als Markow-Entscheidungsprozess (engl. Markov Decision Process) aufgefasst. Charakteristisch ist die Annahme, dass die Markow-Eigenschaft erfüllt ist:

Fehler beim Parsen (Syntaxfehler): {\displaystyle p(z_{t+1},r_{t+1}|z_{0:t},a_{0:t},b_{0:t})=p(z_{t+1},r_{t+1}|z_{t},a_{t})\left} .

Zentrale Begriffe eines Markow-Entscheidungsprozess sind das Aktionsmodell (oder Transitionswahrscheinlichkeit) und die Erwartete Belohnung im nächsten Zeitschritt (engl.expected reward). Das Aktionsmodel $p(z_{t+1}|z_{t},a_{t})$ ist die bedingte Wahrscheinlichkeitverteilung, dass die Welt von Zustand $z_{t}$ in Zustand $z{t+1}$ übergeht, falls der Agent die Aktion $a_{t}$ ausgewählt hat. Im deterministischen Fall ist das Aktionsmodel einfach eine Funktion, die einem Zustands-Aktions-Paar einen neuen Zustand zuordnet. Die Erwartete Belohnung ist folgendermaßen definiert

b(z_{t},z_{t+1},a_{t}):=E\{b_{t+1}|z_{t},z_{t+1},a_{t}\}

.

Bellmangleichung

optimale Bellmangleichung

Lernverfahren

Dynamisches Programmieren

Temporal Difference Learning

...

Approximation

... Bei unendlichen Zustandsräumen muss diese Nutzenfunktion approximiert werden, z. B. mit Neuronalen Netzen.

Literatur

Richard Sutton, Andrew Barto: Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA, 1998
Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz, August 2004, Pearson Studium, ISBN 3827370892 (deutsche Übersetzung der 2. Auflage) Kapitel 21