Top-Fragen
Zeitleiste
Chat
Kontext

Temporal Difference Learning

Methode des bestärkenden Lernens Aus Wikipedia, der freien Enzyklopädie

Remove ads

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.

Remove ads

Modell

Zusammenfassung
Kontext

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 bewertet (englisch state-value function). Zur Verbesserung seiner Strategie π (englisch policy) nähert er V mit jeder Iteration dem idealen 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:

,

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

und

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.

Remove ads

Algorithmen

Zusammenfassung
Kontext

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.[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:

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.[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:

Remove ads

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

Einzelnachweise

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads