Temporal Difference Learning

Temporal Difference Learning (auch TD-Learning) ist eine Methode des bestärkenden Lernens. Beim bestärkenden Lernen erhält ein Agent nach einer Reihe von Aktionen eine Belohnung und passt seine Strategie an, um die Belohnung zu maximieren. Ein Agent mit einem TD-Learning-Algorithmus macht die Anpassung nicht erst, wenn er die Belohnung erhält, sondern nach jeder Aktion auf Basis einer geschätzten erwarteten Belohnung.

Modell

Wie bei anderen Algorithmen des bestärkenden Lernens ist die Interaktion des Agenten mit seiner Umwelt als Markow-Entscheidungsproblem beschrieben.

Der Agent besitzt eine Funktion V, die einen bestimmten Zustand $s_{t}$ bewertet (englisch state-value function). Zur Verbesserung seiner Strategie π (englisch policy) nähert er V mit jeder Iteration dem idealen $V^{\pi }$ an. Frühere Methoden mussten auf die Belohnung am Ende einer Episode warten, um zu wissen, wie gut die Strategie war, um die Funktion anzupassen. TD-Methoden dagegen aktualisieren ihre Bewertungsfunktion nach jeder Aktion mit der beobachteten Belohnung r (die auch null sein kann) und der durch die derzeitige Bewertungsfunktion geschätzten erwarteten Belohnung. Dieser Prozess heißt Bootstrapping und dabei wird mit jeder Iteration die Schätzung genauer.

Bei dem einfachsten Algorithmus wählt der Agent in jeder Iteration eine Aktion anhand seiner Strategie, beobachtet die Belohnung und passt die Bewertungsfunktion mit folgender Formel an:

$V(s_{t})\leftarrow (1-\alpha )V(s_{t})+\alpha {\big (}r_{t}+\gamma V(s_{t+1}){\big )}$,

wobei α für die Lernrate und γ für den Diskontierungsfaktor steht.

Die Lernrate gibt an, inwieweit neue Werte die derzeitige Bewertungsfunktion anpassen. Es ist mathematisch bewiesen, dass der Algorithmus zu einem Optimum konvergiert, wenn die Lernrate anfangs groß ist und allmählich kleiner wird. Genau heißt das, wenn die beiden Bedingungen

$\sum _{i=1}^{\infty }\alpha _{i}=\infty$ und $\sum _{i=1}^{\infty }\alpha _{i}^{2}<\infty$

erfüllt sind. In der Praxis wählt man häufig eine kleine konstante Lernrate, welche die Bedingung zwar nicht erfüllt, sich im Falle einer veränderlichen Umwelt jedoch besser eignet.

Der Diskontierungsfaktor gewichtet die zukünftigen Belohnungen. Ein kleiner Wert lässt den Agenten kurzsichtiger und ein großer Wert weitsichtiger handeln.

Die Strategie des Agenten kann dabei abhängig sein von der Bewertungsfunktion. Eine prominente Strategie ist die ε-greedy policy. Hierbei wählt der Agent entweder die aus seiner Sicht erfolgversprechendste Aktion (gemäß Bewertungsfunktion) oder eine zufällige Aktion. Der Parameter ε mit Werten zwischen 0 und 1 gibt die Wahrscheinlichkeit an, mit der der Agent eher eine Zufallsaktion anstatt die beste Aktion wählt.

Algorithmen

Q-Learning

Q-Learning ist eine Variante von TD-learning, bei welcher der Agent den Nutzen einer Aktion bewertet, anstelle eines Zustandes. Die erlernte Funktion Q(s,a) heißt demzufolge action-value function. 1989 führte Chris Watkins diesen Algorithmus erstmals ein. Den Konvergenzbeweis erbrachte er gemeinsam mit Peter Dayan im Jahr 1992.

Der Algorithmus sieht vor, dass der Agent zum aktuellen Zustand s eine Aktion a gemäß seiner Strategie ausführt und die daraus resultierende Belohnung r erhält. Aus dem Folgezustand s' nimmt der Agent die erfolgversprechendste Aktion a' gemäß seiner derzeitigen Bewertungsfunktion als zukünftige Belohnung an. Anhand dieser passt er seine Bewertungsfunktion nach folgender Formel an:

$Q(s,a)\leftarrow (1-\alpha )Q(s,a)+\alpha {\big (}r+\gamma \max _{a'}Q(s',a'){\big )}$

Da die Annahme, die zukünftige Belohnung entspräche der bestmöglichen Aktion, von der Strategie (zum Beispiel ε-greedy) abweichen kann, spricht man von einem off-policy-Algorithmus.

SARSA

SARSA steht für state-action-reward-state-action und ist ebenfalls ein Algorithmus zum Erlernen einer action-value function. Im Gegensatz zu Q-Learning bleibt der Agent allerdings bei der Berechnung seiner Folgeaktion seiner Strategie treu (on-policy). G. A. Rummery und M. Niranjan erwähnten den Algorithmus erstmals 1994. Die von Rich Sutton vorgeschlagene und nur in der Fußnote erwähnte Bezeichnung SARSA setzte sich durch.

Ein Agent, der SARSA implementiert, führt zum aktuellen Zustand s eine Aktion a gemäß seiner Strategie aus und erhält eine Belohnung r. Im Folgezustand s' wählt er nun wieder eine Aktion a' gemäß seiner Strategie und nimmt dessen Bewertung als zukünftigen Gewinn, um die Bewertungsfunktion nach folgender Formel anzupassen:

$Q(s,a)\leftarrow (1-\alpha )Q(s,a)+\alpha {\big (}r+\gamma Q(s',a'){\big )}$

TD-Lambda

TD(λ) ist eine Erweiterung des Algorithmus mit „eligibility traces“. Beim ursprünglichen Algorithmus bewirkt eine Aktion nur die Anpassung der Bewertungsfunktion für den zuletzt besuchten Zustand. TD(λ) dagegen passt die Werte mehrerer besuchter Zustände an. Dazu besitzt jeder Zustand ein numerisches Attribut, das angibt, in welchem Maße seine Bewertung zur Änderung berechtigt ist. Wird ein Zustand besucht, geht das Attribut auf 1, und mit jeder Iteration zerfällt es exponentiell mit der Zerfallsrate λ.

Diese Erweiterung schlug so die Brücke zwischen TD-Learning und früheren Monte-Carlo-Methoden. Wird 1 für λ gewählt, zerfällt das Berechtigungsattribut nicht und am Ende der Episode werden alle besuchten Zustände anhand der beobachteten Belohnung angepasst. Dies entspricht dem Vorgehen von Monte-Carlo-Algorithmen. Dagegen ist TD(0) der klassische TD-Algorithmus. In der Praxis eignet sich meist ein Mittelweg zwischen diesen beiden Extremen, bei der mehrere Zustände angepasst werden.

Die Erweiterung kann auch auf SARSA und Q-Learning angewandt werden. Die Algorithmen werden dann SARSA(λ) und Q(λ) bezeichnet.

Konkrete Anwendungen

Einer der bekanntesten Anwendungen TD-Lernens ist TD-Gammon. In den 1980er Jahren entwickelte Gerald Tesauro das Programm, das Backgammon auf Niveau menschlicher Experten spielt. Er implementierte dabei den TD-Lambda-Algorithmus mit einem Perzeptron zur Approximation der Bewertungsfunktion. Die Änderung des neuronalen Netzes erfolgte durch Backpropagation.