Temporal Difference Learning

Temporal Difference Learning (auch TD-Learning) ist eine Methode des bestärkenden Lernens. Beim bestärkenden Lernen führt ein Agent Aktionen aus und erhält dafür Belohnungen. Er passt seine Strategie an, um die Belohnungen zu maximieren. Ein Agent mit einem TD-Learning-Algorithmus aktualisiert seine Schätzungen nach jeder Aktion auf Basis der gerade erhaltenen Belohnung und der geschätzten zukünftig zu erwartenden Belohnung.

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

Der Agent besitzt eine Funktion V, die einen bestimmten Zustand s t {\displaystyle s_{t}} bewertet (englisch state-value function). Zur Verbesserung seiner Strategie π (englisch policy) nähert er V mit jeder Iteration dem idealen V π {\displaystyle V^{\pi }} an. Monte-Carlo-Methoden warten das Ende einer Episode ab und bewerten dann anhand der Summe aller erhaltenen Belohnungen, wie gut die Strategie war. TD-Methoden dagegen aktualisieren ihre Bewertungsfunktion direkt nach jeder Aktion mit der beobachteten Belohnung r (die auch null sein kann) und der durch die Bewertungsfunktion geschätzten zukünftig erwarteten Belohnung. Die Schätzfunktion wird dazu verwendet, sich selber zu verbessern. Dieses Verfahren nennt man auch Bootstrapping. 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 ) ← ( 1 − α ) V ( s t ) + α ( r t + γ V ( s t + 1 ) ) {\displaystyle 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

∑ i = 1 ∞ α i = ∞ {\displaystyle \sum _{i=1}^{\infty }\alpha _{i}=\infty } und ∑ i = 1 ∞ α i 2 < ∞ {\displaystyle \sum _{i=1}^{\infty }\alpha _{i}^{2}<\infty }

erfüllt sind.^[1] 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.

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.^[2] 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 ) ← ( 1 − α ) Q ( s , a ) + α ( r + γ max a ′ Q ( s ′ , a ′ ) ) {\displaystyle 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 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.^[3]

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 ) ← ( 1 − α ) Q ( s , a ) + α ( r + γ Q ( s ′ , a ′ ) ) {\displaystyle Q(s,a)\leftarrow (1-\alpha )Q(s,a)+\alpha {\big (}r+\gamma Q(s',a'){\big )}}

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.

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

1. ↑ Peter Dayan, Terrence J. Sejnowski: TD(λ) Converges with Probability 1. In: Machine Learning. Nr. 14, 1994, S. 295–301 (PDF [abgerufen am 22. April 2016]).  PDF (Memento des Originals vom 22. April 2016 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/pdfs.semanticscholar.org
2. ↑ Chris Watkins: Learning from Delayed Rewards. Ph.D. Thesis. 1989 (PDF [abgerufen am 26. April 2016]). 
3. ↑ G. A. Rummery, M. Niranjan: On-line Q-Learning Using Connectionist Systems. 1994, S. 6 (PDF [abgerufen am 26. April 2016]). 
4. ↑ Gerald Tesauro: Practical Issues in Temporal Difference Learning. In: Machine Learning. Nr. 8, 1992, S. 257–277 (PDF [abgerufen am 25. April 2016]). 
5. ↑ Gerald Tesauro: Temporal difference learning and TD-Gammon. In: Commun. ACM. Band 38, Nr. 3, 1995, S. 58–68, doi:10.1145/203330.203343.