Reinforcement Learning · Reinforcement Learning Friedhelm Schwenker Institut für Neuroinformatik • Vorlesung/Übung: (V) Di 14-16 Uhr, (Ü) Do 12.30-14.00 jeweils im Raum O27/121

Reinforcement Learning

Friedhelm SchwenkerInstitut für Neuroinformatik

• Vorlesung/Übung: (V) Di 14-16 Uhr, (Ü) Do 12.30-14.00 jeweils im Raum O27/121

• Übungsaufgaben sind schriftlich zu bearbeiten (Schein bei 50% der erreichbaren Punkteund aktiver Teilnahme an der Übung).

• Kernfächer/-module– Mathematische und theoretische Methoden der Informatik– Praktische Informatik

• Vertiefungsfach/-modul: Neuroinformatik.

• Veranstaltung im Graduiertenkolleg: Mathematical analysis of evolution, information, andcomplexity.

Überblick

1. Einführung und Motivation

2. Beispiel: Der n-armige Bandit

3. Allgemeines Reinforcement Lernproblem

4. Dynamisches Optimierung

5. Monte Carlo Methoden

6. Temporal Difference Learning

7. Ausgewählte Kapitel zum Reinforcement Lernen (RL)

F. Schwenker Reinforcement Learning 1

1. Einführung und Motivation

1. Beispiele - Informelle Bescheibung

2. Elemente des Reinforcement Lernens

3. Tic-Tac-Toe

4. Literatur


Beispiele

• Beim Schachspiel führt der Spieler Züge aus. Hierbei versucht er durchPlanung, etwa durch Einbeziehung einer Folge von Zügen und Gegenzü-gen, sowie durch Intuition seine Position einzuschätzen um einen mög-lichst gewinnbringenden Zuge auszuwählen.

• Ein autonomer mobiler Roboter soll in einem Gebäude Müll einsam-meln. Er hat dabei zu entscheiden, ob er weiter sammelt oder zum Raummit der Batterieladestation fährt. Bei der Entscheidung berücksichtigt erseine Erfahrungen, die er in früheren Situation gesammelt hat, also ob erbeispielsweise die Ladestation in der Vergangenheit erreichen konnte (beiähnlichen Entfernungen und Ladezuständen). Andererseits soll der Robo-ter den Müll möglichst vollständig und schnell einsammeln.

• Eine Gazelle ist unmittelbar nach seiner Geburt nicht in der Lage sichsicher fortzubewegen, bereits nach einer halben Stunde läuft das Tier mitüber 30km/h.


Gemeinsame Eigenschaften der genannten Beispiele

• Interaktion eines aktiven Agenten mit seiner Umgebung.

• Der Agent versucht eine gestellte Aufgabe zu erfüllen, also ein gestelltesZiel zu erreichen.

• Aktion des Agenten beeinflusst zukünftige Zustände der Umgebung unddamit auch die zukünftigen Aktionen des Agenten.

• Bei der Auswahl der Aktionen müssen zukünftige Konsequenzen dieserAktion in Betracht gezogen werden.

• Der Effekt von Aktionen kann nicht vollständig vorhergesagt werden.

• Der Agent kann seine Erfahrung nutzen, um sich über die Zeit zu verbes-sern.


Informelle Beschreibung

• Basis-Szenario beim Reinforcement Lernen (RL): Ein Agent (Lerner oderLernalgorithmus) interagiert mit seiner Umgebung und versucht ein defi-niertes Ziel zu erreichen, z.B. ein Spiel zu gewinnen. Der Agent kann dieUmgebung wahrnehmen und Aktionen ausführen, die die Umgebung ver-ändern.

• Beim RL soll der Agent lernen Aktionen so auszuführen, dass der erwarte-te Reward maximal wird. Der Agent muss diese Aktionenfolge selbststän-dig herausfinden (trial-and-error ).

• Bei der Maximierung des erwarteten Rewards kommt es in vielen Fällennicht auf den momentanen Reward an, sondern auch auf die nachfolgen-den Rewards (delayed rewards).

• Der Agent muss einerseits explorieren (Zustandsraum und Aktionenraum),


andererseits muss er seine bereits gesammelten Erfahrungen aus vergan-genen Situationen nutzen (Exploration-Exploitation-Dilemma).

• Strategien die nur auf Exploration oder Exploitation beruhen, führen zusuboptimalen Lösungen.

• RL unterscheidet sich vom supervized learning: Beim überwachten Ler-nen wird dem Agenten in jeder Situation ein Sollwert/Sollaktion als Leh-rersignal vorgegeben. Beim RL wird dem Agenten nur ein reellwertigerReward (eine Belohnung) gegeben.

• Reinforcement Lernen (RL) ist nicht durch Methoden oder Algorithmencharakterisiert, sondern durch eine Klasse von Lernproblemen.


Elemente des Reinforcement Lernens

Neben dem Agenten und der Umgebung sind die folgenden Elemente beimRL von Bedeutung

1. Eine Policy definiert die Vorgehensweise des Agenten. Ist also eine Abbil-dung von der Menge der Zustände der Umgebung in die Menge der Aktio-nen. Policies sind im einfachsten Fall Lookup-Tabellen, können aber auchkomplexe Suchverfahren sein. Policies sind möglicherweise stochastischeAbbildungen.

2. Durch die Reward -Funktion wird die Aufgabe in einem ReinforcementLernproblem bestimmt. Sie bildet einen Zustand oder ein Aktion-Zustand-Paar auf eine reelle Zahl, dem Reward, ab. In einem RL Problem sollder Agent den (über die Zeit) erzielten Reward maximieren. Die Reward-Funktion definiert, welches die guten und die schlechten Zustände in demProblem sind. Sie kann vom Agenten nicht verändert werden, kann ihmaber bekannt sein. Reward-Funktionen können stochastisch sein.


3. Die Value -Funktion definiert, welchen Wert ein Zustand (über den Ge-samtverlauf) hat, den Wert also, den der Agent für den betrachteten Zu-stand in der Zukunft als akkumulierte Rewards erwarten kann.Value-Funktionen sind aus Reward-Funktionen abgeleitet (ohne rewardsist keine Value-Funktion definiert).Reward-Funktionen sind dagegen direkt durch die Umgebung definiert.Die effektivsten Algorithmen des Reinforcement Lernens basieren auf ite-rative Schätzungen der Value-Funktion.

4. Ein Modell zur Simulation der Umgebung, also zur Vorhersage des nächs-ten Zustands und des damit verbundenen Rewards ist für viele Reinforce-ment Lernaufgaben hilfreich. Modelle werden beipielsweise zur Planungvon Aktionen benutzt. Umgebungs-Modelle sind noch relativ neue Ent-wicklungen im Bereich des Reinforcement Lernens.


Tic-Tac-Toe

Zur Erläuterung des RL soll das Erlernen des Tic-Tac-Toe dienen:

• Es spielen 2 Personen auf einem 3 × 3 Spielfeld.

• Die Spieler markieren abwechselnd je ein Feld mit ihrem Symbol (typi-scherweise × und ◦).

• Ein Spieler beendet das Spiel als Gewinner, falls er eine Zeile, Spalte odereine Diagonale mit seinen Symbolen vollständig belegt hat.

• Das Spiel ist unentschieden falls keine Felder mehr frei sind (und keinSpieler gewonnen hat).

• Ein perfekter Spieler kann immer ein Unentschieden erreichen, also gehenwir davon aus, unser Gegenspieler sei nicht perfekt.


RL für Tic-Tac-Toe

1. Erstelle eine Zustandstabelle S des Spielfelds. Jeder mögliche Zustanddes Spiels definiert einen Zustand. Alphabet:×, ◦, − (für noch frei)

s0 = (−,−,−,−,−,−,−,−,−) freies Feld

sl = (−,−,−,−,×,−,−,−,−) Kreuz in der Mitte des Feldes

sk = (×, ◦, ◦, ◦,×,×,−,−,×) 3 Kreuze in der Diagonalen.

2. Jedem Zustand s ∈ S wird eine Zahl v(s) ∈ [0, 1]zugewiesen. Diese soll dieWahrscheinlichkeit des Gewinns (aus der Sicht eines der beiden Spieler,z.B der Spieler, der × setzt/schreibt) für den Zustand s angeben.

3. Initial erhalten alle Zustände s ∈ S mit 3 ×’s in einer Zeile, einer Spalteoder einer Diagonalen den Wert v(s) = 1, da hier der Spielgewinn sicherist.


Entsprechend alle Zustände s ∈ S mit 3 ◦’s in einer Zeile, einer Spalteoder einer Diagonalen den Wert v(s) = 0, da der Verlust sicher ist.Alle anderen Zustände s ∈ S den Wert v(s) = 1/2.

4. Es werden sehr viele Spiele gegen unseren Gegner gespielt.

5. Um einen Zug auszuwählen, betrachten wir die Werte der möglichenNachfolgezustände.

6. Wir wählen dabei meistens den Zug, der in den Zustand s mit dem größtenWert v(s) führt (greedy move).

7. Gelegentlich wählen wir allerdings auch einen Zug zufällig aus (Explorati-on).

8. Während des Spiels versuchen wir die Werte der Zustände v(s) iterativ zuverbessern.


9. Bei einem Greedy-Zug wird der Wert des alten Zustands v(st) in Richtungdes aktuellen Zustandswertes v(st+1) angepasst:

v(st) := v(st) + α[v(st+1) − v(st)]

α > 0 ist eine Lernrate. Dieses Lernverfahren wird als temporal-difference-learning bezeichnet, da es auf der Differenz der Werte zweier aufeinander-folgender Zustände basiert, nämlich [v(st + 1) − v(st)].

10. Dieses einfache Verfahren ist recht gut. So konvergieren die Werte v(s)gegen die wahren Gewinnwahrscheinlichkeiten, falls die Lernrate geeignetgegen 0 konvergiert. Das Verfahren konvergiert gegen die optimale policy.


Literatur

[1] L.P. Kaelbling, M.L. Littmann, and A.W. Moore. Reinforcement learning:A survey. Journal of Artificial Intelligence Research, 4:237–285, 1996.

[2] R.S. Sutton and A.G. Barto. Reinforcement Learning. An Introduction.The MIT Press, 1998.


2. Beispiel: n-armiger Bandit

1. Das Problem des n-armigen Banditen

2. Methoden zur Berechung von Wert-Funktionen

3. Softmax-Auswahl von Aktionen

4. Inkrementelle Schätzverfahren

5. Nichtstationärer n-armiger Bandit


Der n-armige Bandit

• Verallgemeinerung des Glückspielautomaten (1-armiger Bandit)

• Der Agent kann in jedem Schritt eine Aktion aus n möglichen Aktionen(Automaten) wählen.

• Nach jeder Aktion erhält er einen Reward (Gewinn).

• Reward erfolgt gemäß einer festen Wahrscheinlichkeitsverteilung, die nurvon der auswählten Aktion (hier Automat) abhängt.

• Ziel des Spiels: Gesamt-Reward über eine feste Zeitspanne von T Aktio-nen maximieren.

• Jede Aktion hat einen (mittleren) erwarteten Reward, dieser ergibt sichgemäs̈s einer Wahrscheinlichkeitsverteilung.


• Kennt der Agent den tatsächlichen erwarteten Reward, so wählt er ambesten immer die Aktion mit dem höchsten erwarteten Reward aus.Annahme: Der Agent kennt diese Werte nicht—aber Näherungen (Schät-zungen).

• Es gibt mindestens eine Aktion dessen geschätzter erwarteter Reward ma-ximal ist. Wir nennen sie greedy-Aktion (Exploitation).

• Exploration heißt, dass auch gelgentlich Aktionen ausgewählt werden, diekeine greedy-Aktionen sind.

• Der Anteil von Explorations-Aktionen ist abhängig von der Genauigkeit dergeschätzten erwarteten Rewards, der Sicherheit über diese Werte, die An-zahl der verbleibenden Spiele, etc.


Berechnung der Wert-Funktion

• Diskutieren nun einfache Methoden zur Schätzung der Wert-Funktionen.

• Esi sei a eine Aktion, dann bezeichne Q∗(a) den Erwartungswert der zu-künftig Rewards.

• Qt(a) bezeichnet die Schätzung des Wertes für die Aktion a zur Zeit t.

• Schätzung durch den Mittelwert der bisher erzielten Rewards:Wir befinden uns im t-ten Spiel. Eine Aktion a sei ka-mal in den vorheri-gen Spielen als Aktion ausgewählt worden und der Agent habe dabei dieRewards r1, . . . , rka erhalten, dann kann Q∗(a) durch den Mittelwert ange-nähert werden:

Qt(a) :=1

ka

ka∑

i=1

ri


• Für ka = 0 setze etwa Qt(a) auf einen Defaultwert, z.B. Qt(a) = 0.

• Falls nun ka → ∞ wächst, so gilt:

Qt(a) → Q∗(a)

• Greedy Verfahren: Wähle zur Zeit t ein Aktion a∗ mit

Qt(a∗) = max

aQt(a)

• ǫ-greedy -Verfahren: Setze ǫ ∈ (0, 1) und wähle mit Wahrscheinlichkeit 1−ǫeine greedy-Aktion und mit Wahrscheinlichkeit ǫ eine Aktion zufällig, z.B.nach der Gleichverteilung aus.

• Bei ǫ-greedy-Verfahren ist für t → ∞ sichergestellt, dass ka → ∞ gilt undsomit auch Qt(a) → Q∗(a) folgt.


• Die Schätzungen der Value-Funktionen Qt(a) basieren auf den mittlerenRewards, die der Agent in der Vergangenheit gesammelt hat. Ein nai-ve Realisierung wäre nun, für jede Aktion alle Rewards über die Zeit zusammeln und dann jedesmal den Mittelwert zu berechnen, also Qt(a) :=1ka

∑kai=1 ri.

• Inkrementelles Anpassung: Für eine beliebige Aktion a sei Qk der Mittel-wert der ersten k erzielten Rewards. Dann gilt

Qk+1 =1

k + 1

k+1∑

i=1

ri =1

k + 1

(

rk+1 +k∑

i=1

ri

)

=1

k + 1

(

rk+1 + (k + 1)Qk − Qk

)

= Qk +1

k + 1

(

rk+1 − Qk

)


• Für die inkrementelle Implementation sind die Werte Qk(a) und die Zahlder erzielten Rewards k für jede Aktion a zu speichern.

• Der Aufwand pro Update einer Schätzung

NeuerWert := AlterWert + Schrittweite(Ziel − AlterWert)

ist vergleichsweise gering.

• Die Schrittweite konvergiert gegen 0. Bei der Verarbeitung des k-ten Re-wards ist die Schrittweite lk = 1/k. Genauer, für Aktion a ist lk(a) = 1/ka.

• Solche inkrementellen Adaptationsvorschriften findet man auch anderenmaschinellen Lernverfahren.


Softmax Auswahl

• Im ǫ-greedy-Verfahren sind Exploration aud Exploitation einfach balancier-bar.

• Der Nachteil beim ǫ-greedy Verfahren: Verteilung nach der eine Aktion aus-gewählt wird ist fest z.B. die Gleichverteilung, d.h. auch sehr ungünstigeAktionen kommen vor.

• Lösung: Aktionen werden gemäß einer Wahrscheinlichkeitsverteilung aus-gewählt, die auf den bereits geschätzten Werten Q(a) beruht. Dabei sollengreedy-Aktionen die höchsten Ausführungswahrscheinlichkeiten haben.

• Diese Verfahren heißen softmax-Verfahren. Hierbei wird zur Zeit t die Ak-tion a mit einer Wahrscheinlichkeit

pt(a) =eQt(a)/τ

∑

b eQt(b)/τ


ausgewählt. Hierbei ist τ > 0. (Gibbs oder Boltzmann Verteilung)

• Ist τ sehr groß, so werden die Aktion fast nach der Gleichverteilung aus-gewählt.

• Für τ → 0 wird das Softmax-Verfahren zum greedy-Verfahren.

• Ob Softmax- oder ǫ-greedy-Verfahren einzusetzen sind, hängt wohl vonder Aufgabe (und möglicherweise auch vom Anwender) ab.

• Theoretische bzw. ausführliche numerische Studien dazu sind nicht be-kannt.


RL für nichtstationäre Probleme

• Beim n-armed-bandit-problem sind wir bisher davon ausgegangen, dassjeder Automat gemäß einer festen Wahrscheinlichkeitsverteilung dieGewinne auszahlt.

• D.h. nicht, dass die Auszahlungsfunktion der Automaten konstant wäre.

• D.h. der Gewinn (Reward) der Automaten ist eine Zufallsvariable, derenVerteilungsfunktion (über einen Versuch) fest/stationär ist.

• Für Problemstellungen mit stationärer Rewardfunktion, ist es sinnvoll alleRewards gleich zu gewichten, d.h. ohne die Zeitpunkte der erzielten Re-wards zu berücksichtigen.

• In nichtstationären Problemen sollten dagegen Rewards, die vor längererZeit erzielt wurden, schwächer berücksichtigt werden, als solche die aktu-ell erzielt wurden.


• Dazu betrachten das Lernen mit konstanter Lernrate, also

Qk = Qk−1 + α(

rk − Qk−1

)

Hierbei ist α ∈ (0, 1) eine über die Zeit konstante Schrittweite. Es gilt

Qk = Qk−1 + α(

rk − Qk−1

)

= αrk + (1 − α)Qk−1

= αrk + (1 − α)(

αrk−1 + (1 − α)Qk−2

)

= αrk + (1 − α)αrk−1 + (1 − α)2αrk−2 + . . .

. . . + (1 − α)k−1αr1 + (1 − α)kQ0

= (1 − α)kQ0 +k∑

i=1

α(1 − α)k−iri

= (1 − α)kQ0 + α

k∑

i=1

(1 − α)k−iri


• Dies ist ein gewichteter Mittelwert der Rewards r1, . . . , rk und des Anfangs-werts Q0, denn

(1 − α)k + αk∑

i=1

(1 − α)k−i = (1 − α)k + αk−1∑

i=0

(1 − α)i

= (1 − α)k + α1 − (1 − α)k

1 − (1 − α)

= (1 − α)k + α1 − (1 − α)k

α

= (1 − α)k + 1 − (1 − α)k

= 1

• Der Einfluß des Anfangswerts Q0 und der Rewards rk−i nehmen exponen-tiell mit der Zeit ab, Gewichte: (1 − α)k bzw. α(1 − α)k−i


Referenz Reward

• Ziel: Aktionen mit hohen erwarteten Rewards sollen in der Zukunft häufigerausgewählt werden; solche mit niedrigem Reward weniger häufig.

• Wie erkennt der Agent eine Aktion mit hohem Reward? Ist rt = 10 nun einhoher oder ein niedriger Reward?

• Referenz Reward: Beispielsweise der arithmetische Mittelwert aller erziel-ten Rewards, also r̄.

• Interpretation: Der erzielte Reward rt ist hoch, wenn er höher als der Mit-telwert ist und niedrig wenn er kleiner als dieser ist.

• Da die Verteilung der Rewards nicht stationär ist, wird der Mittelwert desRewards gewichtet berechnet:

r̄t+1 = r̄t + α(rt − r̄t), α ∈ (0, 1)


• Beim RL mit Referenz-Reward werden meistens nicht die Werte der Aktio-nen Qk(a) (k Zahl der Aktionen a), geschätzt, sondern eine Präferenzwertpt(a) für Aktion a zur Zeit t.

• Es werde zur Zeit t die Aktion at ausgeführt. Der Agent erhalte den Rewardrt. Dann wird pt adaptiert gemäß

pt+1(a) = pt(a) + β(rt − r̄t) β ∈ (0, 1)

• Die Werte pt(a) können dann wiederum in eine Softmax-Funktion einge-setzt werden. Dies ergibt die Auswahlwahrscheinlichkeiten:

πt(a) =ept(a)

∑

b ept(b)

für die Aktionen a zur Zeit t.


Persuit Verfahren

• Es werden die Werte und die Präferenzen der Aktion geschätzt. Dabeifolgen die Schätzungen der Präferenzen den momentanen Greedy-Aktion(auf der Basis der gerade vorhandenen Schätzungen der Werte der Aktio-nen Qt(a)).

• Die einfachsten Verfahren adaptieren direkt die Auswahlwahrscheinlichkei-ten πt(a) der Aktionen.

• Die Basisidee: Nach einem Spiel sollen die Auswahlwahrscheinlichkeitender Aktionen so angepasst werden, dass die Greedy-Aktion wahrscheinli-cher wird.

• Ermitteln der Greedy-Aktion: Zur Zeit t sei a∗t+1 = arg maxaQt(a) die

Greedy-Aktion für die Zeit t + 1.


• Auswahlwahrscheinlichkeiten und Werte der Aktionen werden angepasst.

• Adaptation der Auswahlwahrscheinlichkeit der Greedy-Aktion:

πt+1(a∗t+1) = πt(a

∗t+1) + β(1 − πt(a

∗t+1))

• Adaptation der Auswahlwahrscheinlichkeit der Nicht-Greedy-Aktionen a 6=a∗

t+1:

πt+1(a) = πt(a) + β(0 − πt(a))

• Die Werte der Aktionen Qt+1(a) werden z.B. durch Mittelwertberechnungbestimmt, wie gehabt.


3. Das Reinforcement Lernproblem

1. Agierender Agent in der Umgebung

2. Discounted Rewards

3. Markov Eigenschaft des Zustandssignals

4. Markov’sche Entscheidung

5. Werte-Funktionen und Bellman’sche Optimalität


Agent und Umgebung - das Bild

Agent

State Reward

rst t

Action

at

st+1

t+1r

Environment


Aktion-Zustand-Reward

• Agent führt eine Aktion at aus.

• Umwelt ändert hierdurch ihren Zustand st und erteilt dem Agenten einenReward rt ∈ R, st und rt werden vom Agenten wahrgenommen.

• Agent führt nächste Aktion at+1 aus.

• S die Menge der Zustände (diskret/endlich)

• A die Menge der Aktionen (diskret/endlich)

• A(st) Menge der Aktion die im Zustand st möglich sind.

• Zeit ist diskret, d.h. t = 1, 2, 3, . . ..


• Der Agent führt die Aktion gemäß einer Strategie/Taktik/Vorgehensweise(policy) aus, bezeichnet mit πt.

• πt(s, a) ist hier die Wahrscheinlichkeit, dass die Aktion at = a ausgeführtwird, falls der Zustand st = s war.

• Reinforcement Lernverfahren adaptieren direkt oder indirekt die policy πt

des Agenten.

• Agent soll die in der Zukunft zu erwartenden Rewards maximieren, alsoden mittleren Reward

1

T

T∑

i=t+1

ri

maximieren.

• Problem: T = ∞ ist möglich


Discounted Rewards

• Wie könnnen die (in der Zukunft) zu erwartenden Rewards maximiert wer-den?

• In einigen Anwendungen ist ein endlicher Zeithorizont T bekannt (z.B.beim Tic-Tac-Toe). In diesen Fällen sind die Rewards bis zur Zeit T zuberücksichtigen. Also einfach den Mitterlwert berechnen.

• In vielen Fällen ist T a priori unbekannt (auch im Verlauf der Zeit nicht),sondern es ist möglicherweise erst kurz vor Schluss T zu schätzen (konti-nuierlich durchgeführte Aufgaben).

• Für diese Aufgabe nehmen wir T = ∞ an. Dann kann aber kein Erwar-tungswert berechnet werden.


• Ausweg: Rewards in der weiteren Zukunft abschwächen mit Konstante γ ∈[0, 1] und dann

Rt =∞∑

i=0

γirt+1+i

• γ < 1, so konvergiert Rt bei beschränkten Rewards (geometrische Reiheanwenden).

• γ = 0, so wird nur rt+1 berücksichtigt.

• γ = 1, so muss T < ∞ sein.

• Je näher γ bei 1, desto stärker werden die weit in der Zukunft liegendenRewards berücksichtigt.


• Wir betrachten also die Summe der discounted Rewards

Rt =T∑

i=0

γirt+1+i

• Also Grenzfälle können T = ∞ oder γ = 1 auftreten, aber nicht beidezusammen.


Markov Eigenschaft

• Als Zustand der Umgebung kann natürlich alles aufgefasst werden, wasder Agent wahrnehmen kann. Dies können einfache Sensorwerte seinoder irgendeine symbolische Repräsentation einer Belegtheitskarte einesRaumes oder Gebäudes. Für den Aufbau einer solchen Karte sind um-fangreiche sensorische Eingaben zuverarbeiten.

• Wir nehmen an, dass der Zustand den der Agent wahrnehmen kann, allefür die Aufgabe relevanten Ereignisse der Vergangenheit enthält.

• Beispiel: Die Positionen der Figuren zu einem Zeitpunkt t geben die voll-ständige Information über den bisherigen Spielverlauf. Wie diese Stellungzustande kam, kann natürlich nützlich sein, für die Berechnung des opti-malen nächsten Zuges ist diese Information nicht nötig.

• Der aktuelle Zustand wird betrachtet, nicht der Weg dort hin!


• Im Allgemeinen basiert die Bestimmung von Zustand und Reward aufWahrscheinlichkeiten der Form

prob{st+1 = s′, rt+1 = r′ | st, at, rt, st−1, at−1, rt−1, . . . , s0, a0} (1)

• Markov Eigenschaft: Die Ausgabe der Umgebung hängt nur ab von at,der letzten Aktion des Agent, sowie von st, dem letzten Zustand der Um-gebenung:

prob{st+1 = s′, rt+1 = r′ | st, at} (2)

• Wir sagen das Zustandssignal hat die Markov-Eigenschaft, gdw.(1) gleich (2) ist für alle s′ und r′ und für alle Vergangenheitenst, at, rt, st−1, at−1, rt−1, . . . , s0, a0.

• Wir nehmen diese Markov-Eigenschaft des Zustandssignals immer an, indiesem Fall sagen wir auch, das Umgebung und RL-Aufgabe die Markov-Eigenschaft erfüllen.


Markov’sche Entscheidung

• Reinforcement-Aufgabe mit der Markov-Eigenschaft wird auch als Mar-kovscher Entscheidungsprozess (MDP=Markov decision process) be-zeichnet.

• Falls A und S endlich sind, auch als finiter MDP. Hiermit beschäftigen wiruns.

• Ein endlicher MDP ist definiert durch A und S und die Dynamik der Um-gebung.

• Gegeben a ∈ A und s ∈ S, die Wahrscheinlichkeit des nächsten Zustandss′ ist

Pas s′ = prob{st+1 = s′ | st = s, at = a}

Dieses sind die Übergangswahrscheinlichkeiten.


• Gegeben a ∈ A und s ∈ S, sowie der nächste Zustand s′ ∈ S der Erwar-tungswert für den nächsten Reward ist

Ras s′ = E{rt+1 | st = s, at = a, st+1 = s′}

• Durch Pas s′ und Ra

s s′ sind die wichtigsten Größen in einem endlichen MDPrepräsentiert.

• Die präzise Verteilung der Rewards um die Erwartungswerte geht aller-dings verloren.


Werte-Funktionen

• Policy des Agenten wird bezeichnet mit πt. Es ist πt(s, a) die Wahrschein-lichkeit, dass die Aktion at = a ausgeführt wird, falls der Zustand st = svorlag.

• Der Wert eines Zustands s bzgl. der Policy π, bezeichnet mit V π(s), ist derErwartungswert von

Rt =∞∑

i=0

γirt+1+i, mit γ ∈ (0, 1]

falls der Agent die Aktionen gemäß π ausführt, wobei er im Zustand sbeginnt, also

V π(s) = Eπ

{

Rt | st = s}

= Eπ

{

∞∑

i=0

γirt+1+i | st = s}


V π Wertfunktion der Zustände (state-value function for policy) π.

• Der Wert der Aktion a im Zustand s bzgl. Strategie π ist der Erwartungswertvon Rt falls der Agent im Zustand s die Aktion a ausführt und dann gemäßder Strategie π vorgeht, also

Qπ(s, a) = Eπ{Rt | st = a, at = a} = Eπ

{

∞∑

i=0

γirt+1+i | st = s, at = a}

Qπ Wertfunktion der Aktionen (action-value function for policy) π.

• V π und Qπ können gelernt werden, beispielsweise durch Mittelwertbildungüber die gesammelten Rewards. Dabei werden im Fall der Schätzung vonV π Mittelwerte für jeden Zustand s gebildet (S endlich) und im Fall von Qπ

Mittelwerte für jede einzelne Aktionen a (A endlich).

• Für viele Zustände und/oder Aktionen müssen V π und Qπ durch adaptiveAbbildungen (z.B. neuronale Netze) gelernt.


Bellman Gleichung

Die Wertfunktion V π erfüllen rekursive Bedingungen zwischen den Zustän-den s und den Folgezuständen:

V π(s) = Eπ {Rt | st = s}

= Eπ

{

rt+1 + γ∞∑

i=0

γirt+2+i | st = s

}

=∑

a

π(s, a)∑

s′

Pass′

(

Rass′ + γEπ

{

∞∑

k=0

γkrt+2+k | st+1 = s′

})

=∑

a

π(s, a)∑

s′

Pass′ (R

ass′ + γV π(s′))

V π ist eindeutige Lösung der Bellman Gleichung, sie ist Grundlage für Algo-rithmen zum Lernen von V π (entsprechende Gleichung gilt für Qπ).


Backup Diagramme

s,as

a

s'

r

a'

s'r

(b)(a)

• (a) die Situation für V π; (b) die Situation für Qπ

• Ausgehend von Zustand s kann der Agent Aktionen a ausführen (hier 3)

• Hierauf geht die Umgebung in Folgezustände über (hier 2), gleichzeitigwird ein Reward r erteilt.

• V π(s) durch Mittelung über alle möglichen Aktionen a und alle möglichenFolgezustände s′.

• Über die Pfade in diesen Bäumen werden die Werte von Zuständen zurAktualisierung der Werte vorherige Zustände propagiert.


Beispiel Gridworld

3.3 8.8 4.4 5.3 1.5

1.5 3.0 2.3 1.9 0.5

0.1 0.7 0.7 0.4 -0.4

-1.0 -0.4 -0.4 -0.6 -1.2

-1.9 -1.3 -1.2 -1.4 -2.0

A B

A'

B'+10

+5

Actions

(a) (b)

Agent bewegt sich im 2D-Gitter. Mögliche Aktionen sind Bewegungen nachNord , Süd, West , Ost .


• Aktionen werden zufällig und mit gleicher Wahrscheinlichkeit gewählt (ran-dom policy π).

• Reward ist −1, falls der Agent eine Aktion ausführt, die ihn hinaus beför-dern würde. In diesem Fall bleibt der Agent allerdings auf seiner Positionim Grid.

• In den Zuständen (Zellen im Grid) A und B. Hier wird ein Reward von 10bzw. 5 erteilt und zwar für alle Aktionen. Diese bringen den Agenten in denZustand A′ bzw. B′.

• Alle anderen Aktion erzielen Reward 0.

• Für γ = 0.9 ist V π in (b) dargestellt.

• Im unteren Bereich haben die Zustände negative Werte V ′(s).

• V π(A) ist das Maximum, allerdings V π(A) < 10, dagegen V π(B) > 5.Warum?


Optimale Wertfunktionen

• Für ein RL Problem suchen wir nach einer Strategie π∗ für die der erwar-tete Reward (Return) möglichst groß ist.

• Die Menge der Strategien Π = {π | π policy auf S ×A} ist teilweise geord-net durch

π ≤ π′ gdw V π(s) ≤ V π′(s) für alle s ∈ S

• Es gibt mindestens eine optimale policy π∗, möglicherweise gibt es mehre-re optimale policies, diese haben aber alle die gleiche Zustandswertfunk-tion, nämlich die optimale Zustandswertefunktion V ∗. Diese ist definiertdurch

V ∗(s) = maxπ

V π(s)


Alle optimalen policies π∗ haben auch gleiche optimale Aktionswertefunk-tion Q∗, definiert durch

Q∗(s, a) = maxπ

Qπ(s, a)

• Für ein Paar aus Zustand und Aktion (s, a) gibt die Funktion Q∗(s, a) denerwarteten Return für die Aktion a im Zustand s an und nachfolgend dieoptimale policy angewendet wird, somit besteht der Zusammenhang zwi-schen Q∗ und V ∗:

Q∗(s, a) = E {rt+1 + γV ∗(st+1) | st = s, at = a}

• V ∗ ist die Wertefunktion einer optimalen policy π∗, somit erfüllt V ∗ dieBellman-Gleichung.


Die Bellman-Gleichung für V ∗:

V ∗(s) = maxa

Qπ∗(s, a)

= maxa

Eπ∗ {Rt | st = s, at = a}

= maxa

Eπ∗

{

∞∑

k=0

γkrt+k+1 | st = s, at = a

}

= maxa

Eπ∗

{

rt + γ∞∑

k=0

γkrt+k+2 | st = s, at = a

}

= maxa

E {rt + γV ∗(st+1) | st = s, at = a}

= maxa

∑

s′

Pass′ (R

ass′ + γV ∗(s′))


Die Bellman-Gleichung für Q∗:

Q∗(s, a) = E

{

rt+1 + γ maxa′

Q∗(st+1, a′) | st = a, at = a

}

=∑

s′

Pass′

(

Rass′ + γ max

a′Q∗(s′, a′)

)

s,as

a

s'

r

a'

s'r

(b)(a)

max

max


• Falls die Dynamik der Umgebung bekannt ist, dh. falls Pass′ und Ra

ss′ be-kannt sind, so besteht das Gleichungssystem für V ∗ aus |S| (nichtlinea-ren) Gleichungen mit |S| Unbekannten. Dieses kann prinzipiell auch gelöstwerden.

• Falls V ∗ bekannt ist, so folgt daraus sehr einfach eine optimale policy. ImZustand s ist π∗(s, a∗) mit

a∗ = arg max∑

s′

Pass′ (R

ass′ + γV ∗(s′))

a) gridworld b) V* c) π*

22.0 24.4 22.0 19.4 17.5

19.8 22.0 19.8 17.8 16.0

17.8 19.8 17.8 16.0 14.4

16.0 17.8 16.0 14.4 13.0

14.4 16.0 14.4 13.0 11.7

A B

A'

B'+10

+5


4. Lösungsansätze für das RL-Problem

1. Dynamic Programming

2. Monte-Carlo-Methoden

3. Temporal-Difference-Learning


Dynamic Programming

Optimale Policies lassen sich einfach aus den optimalen Wertefunktionen V ∗

und Q∗ bestimmen, diese erfüllen die Bellman-Gleichung.

V ∗(s) = maxa

E {rt + γV ∗(st+1) | st = s, at = a}

= maxa

∑

s′

Pass′ (R

ass′ + γV ∗(s′))

Q∗(s, a) = E

{

rt+1 + γ maxa′

Q∗(st+1, a′) | st = a, at = a

}

=∑

s′

Pass′

(

Rass′ + γ max

a′Q∗(s′, a′)

)

Idee: Zur Suche nach optimalen Policies π∗ werden V ∗ bzw. Q∗ verwendet.


Iterative Berechnung von V π

Für eine Policy π gilt bei bekannter Dynamik der Umgebung Pass′ und Ra

ss′,sowie bekannten Werten π(s, a) ist für alle s ∈ S

V π(s) = Eπ

{

rt+1 + γ

∞∑

i=0

γirt+2+i | st = s

}

=∑

a

π(s, a)∑

s′

Pass′ (R

ass′ + γV π(s′))

Dies ist ein lineares Gleichungssystem mit N = |S| Ungekannten, nämlichV π(s1), . . . , V

π(sN). Hierfür gibt es direkte algebraische Methoden, diese sindaufwendig (Matrizeninversion etwa O(N3)).

Es bieten sich iterative Fixpunkt-Verfahren, da sie selbstkorrigierend sind unddie Näherungslösungen bereits während der Iteration benutzt werden kön-nen.


• Idee ist dabei eine Folge von Wertefunktion V0, V1, V2, . . . zu bestimmenmit Vk → V π bei k → ∞.

• Startwert V0 etwa V0(s) = 0 für alle s

• Die Bellman-Gleichung für V π dient dann als Iterationsvorschrift für Vk+1:

Vk+1(s) =∑

a

π(s, a)∑

s′

Pass′ (R

ass′ + γVk(s

′))

• Offenbar ist V π eine Fixpunkt für diese Iterationsvorschrift; ferner kannauch die Konverganz dieses Verfahrens gegen V π gezeigt werden.

• Bei diesem Verfahren werden die Vk+1(s) aus den alten Werte VorgängerVk(s

′). So werden alle neuen Werte nacheinander berechnet. (zur Imple-mentation sind 2 Felder nötig).

• Beim sogenannten in place Verfahren werden die Werte Vk(s) direkt ver-ändert. Dies ist natürlich ein etwas anderes Verfahren, aber es konvergiertebenso gegen V π.

• Es müssen Abbruchkritrien eingefügt werden, da Konvergenz bei k → ∞.


Policy Berechnung (in place Verfahren)

1. Input policy π

2. Initalize V (s) = 0 all s ∈ S

3. Repeat

4. ∆ := 0

5. For each s ∈ S

6. v := V (s)

7. V (s) :=∑

a π(s, a)∑

s′ Pass′

[

Rass′ + γV (s′)

]

8. ∆ := max(∆, |v − V (s)|)

9. until ∆ ≤ ǫ

10. Output: V ≈ V π


Beispiel:Wir betrachten das Beispiel einer 4×4 Grid-World mit den einem Terminalzu-stand (in der ober linken und der unter rechten Zelle(schattiert)) und weiterenZuständen {1, 2, . . . , 14}. Die möglichen Aktionen seien A = {l, r, o, u}, hier-durch wird der entsprechende Zustandsübergang deterministisch hervorge-rufen, mit Ausnahme der Randzellen, hier bleibt der Zustand bestehen. Alsoetwa P l

6,5 = 1 und P l6,10 = 0 und P l

4,4 = 1, usw.

Der Reward ist immer −1 nur beim Ereichen des Terminalzustandes 0. DerAgent wählt jede Aktion mit gleicher Wahrscheinlichkeit 1/4 aus (random po-licy).

actions

r = −1on all transitions

1 2 3

4 5 6 7

8 9 10 11

12 13 14


0.0 0.0 0.0

0.0 0.0 0.0 0.0

0.0 0.0 0.0 0.0

0.0 0.0 0.0

-1.0 -1.0 -1.0

-1.0 -1.0 -1.0 -1.0

-1.0 -1.0 -1.0 -1.0

-1.0 -1.0 -1.0

-1.7 -2.0 -2.0

-1.7 -2.0 -2.0 -2.0

-2.0 -2.0 -2.0 -1.7

-2.0 -2.0 -1.7

-2.4 -2.9 -3.0

-2.4 -2.9 -3.0 -2.9

-2.9 -3.0 -2.9 -2.4

-3.0 -2.9 -2.4

-6.1 -8.4 -9.0

-6.1 -7.7 -8.4 -8.4

-8.4 -8.4 -7.7 -6.1

-9.0 -8.4 -6.1

-14. -20. -22.

-14. -18. -20. -20.

-20. -20. -18. -14.

-22. -20. -14.

Vk for theRandom Policy

Greedy Policyw.r.t. Vk

k = 0

k = 1

k = 2

k = 10

k = ∞

k = 3

optimal policy

random policy

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

• Linke Seite zeigt die NäherungslösungenVk für V π

• Auf der rechten Seite ist die Greedy-Policyπk dargestellt, die sich jeweils aus der Wer-tefunktion Vk ergibt.

• Hier sind dies ab k = 3 sogar optimale Po-licies (dies ist i.A. natürlich nicht der Fall).


Policy Optimierung

• V π und Qπ sollen verwendet werden um die Policy zu verbessern.

• Sei π eine beliebige deterministische Policy und sei V π bekannt.

• In einem Zustand s wollen wir entscheiden ob wir die Poilicy ändern, alsoeine Aktion a 6= π(s) wählen.

• V π(s) gibt uns den erwarteten Return an, falls wir π folgen— aber, ist esbesser eine andere Policy zu wählen?

• Mögliche Vorgehensweise: Wähle eine beliebige Aktion a 6= π(s) im Zu-stand s und folge dann weiter der Policy π.

• Der Wert dieses Vorgehens ist dann

Qπ(s, a) = Eπ {rt+1 + γV π(st+1 | st = s, at = a)}

=∑

s′

Pass′ [R

ass′ + γV π(s′)]


• Ist Qπ(a, s) > V (s), so würde man erwarten, dass es besser ist die Aktiona jedesmal im Zustand s auszuführen.

Policy Improvement Theorem:Sind π und π′ deterministische Policies mit Q(s, π′(s)) ≥ V π(s) für alle s ∈ S,so ist V π′

(s) ≥ V π(s) für alle s.

Gilt ferner Q(s, π′(s)) > V π(s) für ein s ∈ S, dann ist auch V π′(s′) > V π(s′)

für einige Zustände s′. Insbesondere natürlich für s′ = s

Anwendung des Satzes: In jedem Zustand s die beste Aktion bzgl. Qπ(s, a)auswählen, also eine Greedy-Policy π′ durch bestimmen.

π′ = arg maxaQπ(s, a)

= arg maxa

∑

s′

Pass′ [R

ass′ + γV π(s′)]


Beweis des Satzes:

V π(s) ≤ Qπ(s, π′(s))

= Eπ′ {rt+1 + γV π(st+1) | st = s}

≤ Eπ′ {rt+1 + γQπ(st+1, π′(st+1) | st = s}

= Eπ′ {rt+1 + γEπ′ {rt+2 + γV π(st+2)} | st = s}

= Eπ′

{

rt+1 + γrt+2 + γ2V π(st+2) | st = s}

≤ Eπ′

{

rt+1 + γrt+2 + γ2rt+3 + γ3V π(st+3) | st = s}

· · ·

≤ Eπ′

{

rt+1 + γrt+2 + γ2rt+3 + γ3rt+4 + . . . | st = s}

= V π′(s)


Sei nun eine solche Greedy Policy π′ genauso gut wie π aber nicht besser,also V π = V π′

dann gilt

V π′(s) = max

aE {rt+1 + γV π(st+1) | st = s, at = a}

= maxa

E{

rt+1 + γV π′(st+1) | st = s, at = a

}

= maxa

∑

s′

Pass′

[

Rass′ + γV π′

(s′)]

Das ist aber die Bellman Gleichung für V ∗, d.h. damit ist V π = V π′= V ∗ und

π und π′ sind optimale Policies.


Policy Iteration

1. Initialize policy π and V (s) ∈ R

2. Policy BerechnnungRepeat

∆ := 0For each s ∈ S

v := V (s)V (s) :=

∑

a π(s, a)∑

s′ Pass′

[


]

∆ := max(∆, |v − V (s)|)until ∆ ≤ ǫ

3. Policy Verbesserungstable := 1For each s ∈ S

b := π(s)π(s) := arg maxa

∑

s′ Pass′

[


]

if b 6= π(s) then stable := 0if stable 6= 1 then stop; else GoTo 2.


Policy Iteration - Bilder

π0E→ V π0 I

→ π1E→ V π2 I

→ π3E→ V π3 I

→ . . . . . . π∗ E→ V ∗

π V

evaluation

improvement

V →Vπ

π→greedy(V)

*Vπ*

startingV π

V = V π

π = greedy ( V )

V*

π*


Beispiel: Jack’s Autovermietung

• Jack ist der Manager von 2 Filialen einer großen Autovermietungskette.

• Kann er an einen Kunden ein Fahrzeug vermieten, so erhält er 10 Euro.

• Sind die Fahrzeuge in einer Filiale komplett vermietet, so kann er Fahrzeu-ge von der anderen Filale über Nacht transferieren, allerdings entstehenKosten von 2 Euro je Fahrzeug.

• Wir nehmen an, die Zahl der Vermietungsnachfragen in den beiden Filialenseien jeweils Poisson Zufallsvariablen X1 und X2 mit Erwartungswert λ1 =3 und λ2 = 4, d.h.

p(X = n) =λn

n!e−λ.


• Die Zahl der Fahrzeugrückgaben seine ebenfalls Poisson ZufallsvariableY1 und Y2 mit Erwartungswert µ1 = 3 und µ2 = 2.

• Sind in einer Filiale mehr als 20 Fahrzeuge, so werden diese an die Vermie-tungskette zurückgegeben, sie verschwinden einfach (ohne weitere Kos-ten).

• Es können höchstens 5 Autos von einer Filiale in die andere überführtwerden.

• Zeitschritte sind Tage. Zustände sind die Zahlen der Fahrzeuge in denbeiden Filialen. Aktionen sind die Zahl der Fahrzeuge, die von einer zuranderen Filiale bewegt werden.

• Ergebnisse für γ = 0.9

• π0 die Policiy, die keine Fahrzeuge bewegt.


4V

612

#Cars at second location

0420

20 0

20

#Car

s at

firs

t loc

atio

n

1

1

5

−1−2

-4

43

2

43

2

−3

0

0

5

−1−2

−3 −4

1234

0

π1π0 π2

−3 −4−2

0

12

34

−1

π3

2

−4−3−2

0

134

5

−1

π4

#Cars at second location

#Car

s at

firs

t loc

atio

n 5

200

020


Value Iteration

Bei der Berechnung der Wertefunktion V π wird die Konvergenz bei k → ∞erreicht. Value Iteration: Nur je eine Auswertung bei der Berechnung von V π.

1. Initalize V (s) = 0 all s ∈ S

2. Repeat

3. ∆ := 0

4. For each s ∈ S

5. v := V (s)

6. V (s) := maxa

∑

s′ Pass′

[


]

7. ∆ := max(∆, |v − V (s)|)

8. until ∆ ≤ ǫ

9. Output: policy π mit π(s) := arg maxa

∑

s′ Pass′

[


]


Beispiel: Münzwurf

• Eine Münze wird geworfen und ein Spieler wettet. Er gewinnt den Einsatzbei Kopf und er verliert den Einsatz bei Zahl .

• Das Spiel endet, falls er insgesamt ein Kapital s = 100 erreicht hat, bzw.wenn er kein Kapital mehr hat.

• Das Kapital des Spielers s sind die Zustände.• Vor jedem Münzwurf muss der Spieler seinen Einsatz

a ∈ {1, 2, . . . ,min(s, 100 − s)} bestimmen (Aktion).• Rewards sind r = 0, falls der Spieler sein Ziel erreicht hat (s = 100) dann

ist der Reward r = 1.• Policy ist Abbildung von Zuständen in Aktionen.• Optimale Policy maximiert den erwarteten Reward, also die Wahrschein-

lichkeit den Zielzustand s = 100 zu erreichen.• p die Wahrscheinlichkeit für Kopf .• Ergebnisse für p = 0.4.


997550251

1

10

20

30

40

50

1

0

0.2

0.4

0.6

0.8

1

25 50 75 99

Capital

Capital

Valueestimates

Finalpolicy(stake)

sweep 1

sweep 2sweep 3

sweep 32


Monte Carlo Methoden

• Lernverfahren zur Berechnung von Wertefunktionen und Policies werdenvorgestellt.

• Vollständige Kenntnis der Dynamik wird nicht vorausgesetzt (im Gegen-satz zu den Verfahren der DP).

• Für Monte Carlo Methoden werden Erfahrungen in Form von Beispielen(Folgen von Zuständen, Aktionen und Rewards) gebraucht.

• Monte Carlo Methoden basieren auf Mittelung des Returns erzielt für dievorhandenen Beispiele.

• Verfahren werden hier für episodische Aufgaben formuliert, d.h. Erfahrun-gen werden in einzelnen Episoden gesammelt, alle Episoden terminierennach endlicher Zeit (unabhängig von den gewählten Aktionen).

• Monte Carlo Methoden sind inkrementell (im Sinne einzelner Episoden).


MC Policy Bestimmung

• MC Methoden zur Berechnung von V π für eine Policy π gesucht.• V π(s) ist der erwartete (u.U. diskontierte) Return (π folgend) ausgehend

vom Zustand s.• Einfacher Weg um V π(s) zu aus Beispielen zu schätzen ist, die in den

beobachteten Beispielen erzielen Returns zu mitteln.• Falls nur genügend viele Beispiele vorliegen, wird der Mittelwert gegen

den Erwartungswert konvergieren.• Angenommen, wir wollen V π(s) schätzen, gegeben sei die Policy π und

eine Menge von einzelnen Episoden, in welchen der Zustand s vorkommt.

• Ein Vorkommen von s heißt ein visit von s; in einer Episode heißt das ersteVorkommen auch first visit.

• Every visit MC Methoden: Mittelung der Returns über alle Visits von s.• First visit MC Methoden: Mittelung der Returns ausgehend vom first visit

in jeder Episode. Wir benutzen first visit MC Methoden.


First visit MC zur Schätzung von V π

1. Initalize:

π := policy to be evaluated

Returns(s) := ∅ for all s ∈ S

2. Repeat forever:

Generate an episode using π

For each s appearing in the episode:

R := return following the first occurrence of s

Returns(s) := Returns(s) ∪ R

V (s) := mean(Returns(s))


MC Schätzung von Aktion Werten

• Falls die Umgebung bekannt ist (d.h. Rass′,P

ass′) so ist die Kenntnis der

Wertefunktion V π ausrechend um eine Policy zu bestimmen (beste Kom-bination aus Reward und nächstem Zustand bestimmen).

• Falls das Modell nicht bekannt ist, müssen Schätzung über die Werte derAktionen durchgeführt werden.

• Hauptziel ist es also Q∗ zu bestimmen.

• Müssen dazu den Wert von Aktionen Qπ(s, a) bestimmen.

• Methoden hierfür sind dieselben wie bei der Evaluation von V π(s)

• Problem: Viele der Paare (s, a) werden nie besucht.

• Bei einer deterministische Policy wir genau eine Aktion a im Zustand sausgeführt (a = π(s)), sonst wird kein Zustands-Aktions-Paare besucht.

• Idee: Exploring Starts (ES), d.h. zu Beginn einer Episode wird ein Paar(s, a) zufällig gewählt, hierfür sei prob(s, a) > 0 für alle (s, a).


MC Algorithmus mit ES

1. Initalize for all s ∈ S and a ∈ A

Q(s, a) arbitrary

π(s) arbitrary

Returns(s, a) := ∅

2. Repeat forever:

a) Generate an episode using exploring starts and π

b) For each pair (s, a) appearing in the episode:

R := return following the first occurrence of (s, a)

Returns(s, a) := Returns(s, a) ∪ R

Q(s, a) := mean(Returns(s, a))

c) For each s in the episode: π(s) := arg maxaQ(s, a)


On Policy MC Methoden

• Wie können wir exploring starts vermeiden?

• Agent muss in der Lage sein, stets eine beliebige Aktionen a im Zustand sauszuwählen.

• Betrachten soft policies, d.h. mit π(s, a) > 0 für alle (s, a).• Beispiel sind die ǫ-Greedy Policies, d.h. überwiegend wird die Greedy-

Aktion ausgeführt, aber mit Wahrscheinlichkeit ǫ eine Zufalls-Aktion• Nicht-Greedy-Aktionen erhalten somit die Wahrscheinlichkeit ǫ/|A(s)|, die

Greedy-Aktion die Wahrscheinlichkeit (1 − ǫ + ǫ/|A(s)|)

• ǫ-Greedy sind Beispiele für ǫ-Soft Policies.• Wir verwenden first-visit MC Methoden zur Schätzung der Aktions-

Wertefunktion Qπ, für eine gegebene Policy π.• Mit Hilfe des Policy-Improvement-Theorems kann man zeigen, das jede

ǫ-Greedy Policy bzgl. Qπ eine Verbesserung für ǫ-soft Policy π.


Sei nun π′ eine solche ǫ-greedy Policy und s ∈ S:

Qπ(s, π′(s)) =∑

a

π′(s, a)Qπ(s, a)

=ǫ

|A(s)|

∑

a

Qπ(s, a) + (1 − ǫ) maxa

Qπ(s, a)

≥ǫ

|A(s)|

∑

a

Qπ(s, a) + (1 − ǫ)∑

a

π(s, a) − ǫ|A(s)|

1 − ǫQπ(s, a)

=ǫ

|A(s)|

∑

a

Qπ(s, a) −ǫ

|A(s)|

∑

a

Qπ(s, a) +∑

a

π(s, a)Qπ(s, a)

= V π(s)

Nach dem Policy Improvement Theorem folgt dann V π′(s) ≥ V π(s)


Ein ǫ-Soft On-Policy MC Algorithmus


Q(s, a) arbitrary; π(s) arbitrary ǫ soft policy; Returns(s, a) := ∅

2. Repeat forever:a) Generate an episode using π

b) For each pair (s, a) appearing in the episode:R := return following the first occurrence of (s, a)

Returns(s, a) := Returns(s, a) ∪ R

Q(s, a) := mean(Returns(s, a))

c) For each s in the episode:a∗ := arg maxaQ(s, a)

For all s ∈ A(s):

π(s, a) :=

{

1 − ǫ + ǫ/|A(s)| a = a∗

ǫ/|A(s)| a 6= a∗


Off Policy MC Methoden

• Wollen V π bzw. Qπ für eine (deterministische) Policy schätzen, haben aberEpisoden nach einer anderen (Soft) Policy π′ 6= π generiert.

• Kann man die Wertefunktionen V π noch lernen?

• Episoden seinen nach π′ erzeugt.

• In der Menge der Episoden, betrachten wir jeweils den ersten Besucheeines Zustands s und die Folge aus Zuständen und Aktionen die s folgen.

• Seien pi(s) und p′i(s) die Wahrscheinlichkeiten dieser Folgen für die Poli-cies π und π′ (i nummeriert die Episode).

• Ri(s) der beobachtete Return von Zustand s.

• V (s) als gewichtetes Mittel mit Gewichten wi = pi(s)/p′i(s) ergibt

V (s) =

∑nsi=1

pi(s)p′i(s)

Ri(s)∑ns

i=1pi(s)p′i(s)


• Nehmen an, dass falls π(s, a) > 0 gilt, so auch π′(s, a).

• pi(s) und p′i(s) sind i.A. unbekannt. Allerdings wird nur pi(s)p′i(s)

benötigt.

• Sei Ti(s) die Teit bis zur Termination in der i-ten Episode für Zustand s,dann gilt

pi(s) =

Ti(s)−1∏

k=1

π(sk, ak)Paksksk+1

also

pi(s)

p′i(s)=

∏Ti(s)−1k=1 π(sk, ak)P

aksksk+1

∏Ti(s)−1k=1 π′(sk, ak)P

aksksk+1

=

Ti(s)−1∏

k=1

π(sk, ak)

π′(sk, ak)

Damit sind die Gewichte von der Dynamik unabhängig, hängen nur vonden beiden Policies ab.


Ein Off-Policy MC Algorithmus


π(s) arbitrary deterministic policy; N(s, a) := 0; D(s, a) := 0

2. Repeat forever:a) Select a policy π′ and generate episode:

s0, a0, r1, s1, r1, r2, . . . , sT−1, aT−1, rT , sT

b) τ := latest time at which aτ 6= π(sτ)

c) For each pair (s, a) appearing in the episode at time τ or later:

t := time of first occurence of (s, a) such that t ≥ τ

w :=∏T

k=t+1(π′(sk, ak))

−1

N(s, a) := N(s, a) + wRt

D(s, a) := D(s, a) + w

Q(s, a) := N(s, a)/D(s, a)

d) For each s in the episode: π(s) := arg maxaQ(s, a)


Inkrementelles Lernen

• Inkrementelle Lernverfahren lassen sich auch für gewichtete Mittelwerteherleiten

• Es soll berechnet werden:

Vn =

∑nk=1 wkRk∑n

k=1 wk

• Dann ergibt sich die Update-Regel

Vn+1 = Vn +wn+1

Wn+1(Rn+1 − Vn)

und

Wn+1 = Wn + wn+1

mit V0 = W0 = 0.


Beispiel: Blackjack

• Spieler spielt gegen die Bank Blackjack. Ziel: möglichst nahe an 21 kom-men

• Ass kann 1 oder 11 zählen, Bilder alle 10. Sonst Punkte wie auf der Karte.

• Zunächst erhält jeder 2 Karten. Eine Karte der Bank ist offen.

• Hat der Spieler 21 gewinnt er, es sein denn die Bank hat ebenfalls 21.Dann ist das Spiel unentschieden.

• Nun kann der Spieler weitere einzelne Karten anfordern, bis er stoppt odermehr als 21 hat. Im letztgenannten Fall, verliert er. Stoppt er, nimmt dieBank weitere Karten, und zwar nach einer festen Policy: weitere Kartenwerden dann und nur dann genommen wenn die Augenzahl < 17 ist, sonstgestoppt. Hat die Bank mehr als 21, gewinnt der Spieler, sonst wird Ge-winn, Verlust und Unentschieden durch die Augenzahl bestimmt.

• Jedes Spiel eine Episode. Danach werden die Karten dem Stapel wiederzu gefügt.


• Rewards seien 1, −1 und 0 (Gewinn, Verlust, Unentschieden).

• Aktion sind: weitere Karte(hit) oder keine Karte mehr(stick).

• Zustände sind die Augenzahl auf den Karten des Spielers und die Augen-zahl der offenen Karte der Bank.

• Ein Ass heißt hier usable falls es mit 11 gerechnet werden kann, und trotz-dem die Augenzahl 21 nicht überschreitet.

• Gezeigt ist die optimale Policy bestimmt durch MC mit Exploring Starts. V ∗

ist durch Q∗ berechnet.


Usableace

Nousable

ace

20

10A 2 3 4 5 6 7 8 9Dealer showing

Pla

yer

sum

HIT

STICK 19

21

1112131415161718

π*

10A 2 3 4 5 6 7 8 9

HIT

STICK 2019

21

1112131415161718

V*

21

10 12

A

Dealer showing

Pla

yer

sum

10

A

12

21

+1

−1


Temporal Difference Learning

• Das Temporal Difference (TD) Lernen ist eine bedeutende Entwicklung imReinforcement Lernen.

• Im TD Lernen werden Ideen der Monte Carlo (MC) und dynamische Pro-grammierung (DP) Methoden kombiniert.

• Im TD Lernen wird wie beim MC Lernen aus Erfahrung ohne Kenntnisseines Modells gelernt, d.h. dieses wird aus Daten/Beispielen gelernt.

• Wie beim DP werden Schätzungen für Funktionswerte durchgeführt(V π(s) oder Qπ(s, a)), die wiederum auf Schätzungen basieren (nämlichdie Schätzungen V π(s′) nachfolgender Zustände).

• Wir beginnen mit der Evaluation von Policies π, d.h. mit der Berechnungder Wertefunktionen V π bzw. Qπ.


TD Evaluation

• TD und MC Methoden nutzen Erfahrung aus Beispiele um V π bzw. Qπ füreine Policy π zu lernen.

• Ist st der Zustand zur Zeit t in einer Episode, dann basiert die Schätzungvon V (st) auf den beobachteten Return Rt nach Besuch des Zustand st

• In MC Methoden wird nun der Return Rt bis zum Ende der Episode be-stimmt und dieser Schätzwert für V (st) angesetzt.

• Eine einfache Lernregel nach der Every Visit MC Methode hat dann diefolgende Gestalt:

V (st) := V (st) + α [Rt − V (st)] mit α > 0

• In den einfachen 1-Schritt TD Methoden nur der nächste Zustandsüber-gang s → s′ abgewartet und der unmittelbar erzielte Reward zusammenmit V (s′) benutzt.


• Ein 1-Schritt TD Algorithmus, der sog. TD(0) Algorithmushat die Lernregel

V (st) := V (st) + α [rt+1 + γV (st+1) − V (st)] α > 0, γ ∈ (0, 1]

• Zur Erinnerung– es gilt

V π(s) = Eπ

{

Rt | st = s}

= Eπ

{

∞∑

k=0

γkrt+1+k | st = s}

= Eπ

{

rt+1 + γ∞∑

k=0

γkrt+2+k | st = s

}

= Eπ {rt+1 + γV π(st+1) | st = s}

• Sollwert beim MC Lernen : Rt

• Sollwert beim TD Lernen : rt+1 + γV π(st+1)


TD(0) – Schätzung von V π

1. Initalize V (s) arbitrarily, π policy to be evaluated

2. Repeat (for each episode)

Initialize s

Repeat (for each step of episode):

a := π(s)

take a, observe reward r, and next state s′

V (s) := V (s) + α[

r + γV (s′) − V (s)]

s := s′

Until s is terminal

TD-Backup Diagramm

s, s′ ∈ S sind die offe-nen Kreise

a ∈ A die Aktion π(s)

gefüllter Kreis


Sarsa

• Ziel ist das Erlernen der Q-Funktion statt der V -Funktion durch On PolicyMethode, d.h. Schätzung der Werte Qπ(s, a) für die verwendete Policy pi.

• Es kann dasselbe Verfahren wie zur Schätzung der V -Funktion verwendetwerden mit der Lernregel

Q(st, at) := Q(st, at) + α [r + γQ(st+1, at+1) − Q(st, at)]

• Hierzu betrachten wir Zustandsübergänge:

st+2,at+2st+1,at+1

rt+2rt+1st st+1st ,atst+2


Sarsa: Algorithmus

1. Initalize Q(s, a) arbitrarily,


Initialize s

Choose a from s using policy derived from Q (e.g. ǫ-greedy)


Take a, observe reward r, and next state s′

Choose a′ from s′ using policy derived from Q (e.g. ǫ-greedy)

Q(s, a) := Q(s, a) + α[

r + γQ(s′, a′) − Q(s, a)]

s := s′; a := a′

Until s is terminal


Q-Learning

Q-Lernen ist das wichtigste Verfahren im Bereich des Reinforcement Ler-nens, es wurde von Watkins 1989 entwickelt.

Ist ein Off Policy TD Lernverfahren definiert durch die Lernregel

Q(st, at) := Q(st, at) + α[

r + γ maxa

Q(st+1, a − Q(st, at)]

Q konvergiert direkt gegen Q∗ (vereinfacht die Analyse des Verfahrens).

Policy π legt die Aktion fest, und somit wird durch π die Folge von (st, at)festgelegt, die in der Episode vorkommen (und damit auch die Stellen anden die Q-Funktion gelernt wird).


Q-Learning: Algorithmus

1. Initalize Q(s, a) arbitrarily,


Initialize s


Choose a from s using policy derived from Q

(e.g. ǫ-greedy)

Take a, observe reward r, and s′

a∗ := arg maxaQ(s′, a)

Q(s, a) := Q(s, a) + α[

r + γQ(s′, a∗) − Q(s, a)]

s := s′;

Until s is terminal

Q-Learning Backup

s, s′ ∈ S sind die offe-nen Kreise

a,∈ A die Aktion π(s)

gefüllte Kreise

max durch Kreisboden


TD n-step Methoden

• Die bisher vorgestellten TD Lernverfahren verwenden den unmittelbar fol-genden Reward (k = 1-Schritt) rt+1.

• Idee bei den Mehrschritt Methoden ist es, auch die nächsten k = 2, 3, . . . nerzielten Rewards rt+k einzubeziehen.

• Dazu betrachten wir die Zustands-Reward-Folge

st, rt+1, st+1, rt+2, . . . , rT , sT

sT der Endzustand.

• MC Methoden verwenden zum Backup von V π(st) den Return

Rt = rt+1 + γrt+2 + γ2rt+3 + . . . γT−t−1rT

Rt ist das Lehrersignal (Sollwert) für die MC Lernverfahren.


• Für 1-Schritt TD Methoden ist das Lehrersignal

R(1)t = rt+1 + γVt(st+1)

hier dient γVt(st+1) als Näherung für

γrt+2 + γ2rt+3 + . . . γT−t−1rT

• Bei einem 2-Schritt-TD Verfahren ist der Sollwert

R(2)t = rt+1 + γrt+2 + γ2Vt(st+2)

wobei jetzt γ2Vt(st+2) die Näherung ist für

γ2rt+3 + γ3rt+4 + . . . + γT−t−1rT

• Allgemein ist der n-Schritt-Return R(n)t zur Zeit t gegeben durch

R(n)t = rt+1 + γrt+2 + γ2rt+3 + γn−1rt+n + γnVt(st+n)


• Lernregel für die V-Funktion mit n Schritt Backups ist also

∆Vt(st) = α[

R(n)t − Vt(st)

]

TD (1-step) 2-step 3-step n-step Monte Carlo


TD(λ)-Verfahren

• Backups können nicht nur auf der Basis von n-Schritt Returns R(n)t ,

sondern durch Mittelung verschiedener n-Schritt Returns erfolgen, z.B.Mittelwert eines 2− und 4− Schritt Returns

Ravet =

1

2R(2)

t +1

2R(4)

• Allgemeine Mittelungen sind möglich. Nur die Gewichte sollten nicht-negativ sein und sich zu 1 summieren.

• Dies führt auf die TD(λ) Verfahren, hier werden alle n-Schritt Returnsgewichtet.

• Mit einem Nomalisierungsfaktor 1−λ (stellt sicher das die Summe derGewichte = 1 ist) definieren wir den λ-Return durch

Rλt = (1 − λ)

∞∑

n=1

λn−1

R(n)t = (1 − λ)

T−t−1∑

n=1

λn−1

R(n)t + λ

T−t−1Rt

1

2

1

2


TD(λ)-Backup-Diagramm

1−λ

(1−λ) λ

(1−λ) λ2

Σ = 1

TD(λ), λ-return

λT-t-1


Gewichtung von λ

Update (hier der V -Funktion) bei einem λ-Return Algorithmus

∆Vt(st) = α[

Rλt − Vt(st)

]

1−λ

weight given tothe 3-step return

decay by λ

weight given toactual, final return

t TTime

Weight

total area = 1


Forward View/Backward View

Time

rt+3rt+2

rt+1

rT

st+1

st+2

st+3

st

Forward View: Ist nicht kausal und kann deshalb auch nicht so direkt implementiert werden.

δtet etet

et

Time

stst+1

st-1

st-2

st-3


Kummulative Trace-Variable

Backward View benötigt für jeden Zustand eine Trace-Variable et(s) die defi-niert ist als

et(s) =

{

γλet−1(s) s 6= st

γλet−1(s) + 1 s = st

Dabei zeigt et(s) > 0 an, dass der Zustand s kürzlich besucht wurde. Kürzlichist hierbei durch die Größe γλ definiert.

et(s) zeigt, für welche Zustände s ∈ S die Funktion V bzw. Q anzupassen ist.

accumulating eligibility trace

times of visits to a state


Die Fehlersignale sind (hier für V -Funktion):

δt = rt+1 + γVt(st+1) − Vt(st)

Alle kürzlich besuchten Zustände s werden damit adaptiert (wieder für V )

∆Vt(st) = αδtet(s) für alle s ∈ S

Hierbei ist wieder γ ∈ (0, 1] der Diskontierungsfaktor und α > 0 eine konstan-te Lernrate.


TD(λ)

1. Initalize V (s) arbitrarily and e(s) = 0; π policy to be evaluated


Initialize s


a := π(s)


δ := r + γV (s′) − V (s)

e(s) := e(s) + 1;

For all s:

V (s) := V (s) + αδe(s)

e(s) := γλe(s)

s := s′

Until s is terminal


Äquivalenz der beiden Methoden

Wir zeigen nun, das die Updates von V der Vorwärts- und Rückwärtssicht fürdas Off-line-Lernen äquivalent sind.

• Es sei∆V λt (st) die Änderung von V (st) zur Zeit t nach der λ-Return Me-

thode (Vorwärtssicht).

• Es sei ∆V TDt (s) die Änderung von V (s) zur Zeit t von Zustand s nach dem

TD(0) Algorithmus (Rückwärtssicht).

Ziel ist es also zu zeigen

T−1∑

t=0

∆V λt (st)1[s=st] =

T−1∑

t=0

∆V TDt (s) für alle s ∈ S


es ist 1[s=st] gleich 1 genau dann wenn s = st ist. Wir untersuchen eineneinzelnen Update ∆V λ

t (st) = α[

Rλt − Vt(st)

]

.

1

α∆V λ

t (st) = −Vt(st) +

(1 − λ)λ0 [rt+1 + γVt(st+1)] +

(1 − λ)λ1[

rt+1 + γrt+2 + γ2Vt(st+2)]

+

(1 − λ)λ2[

rt+1 + γrt+2 + γ2rt+3 + γ3Vt(st+3)]

+

(1 − λ)λ2[

rt+1 + γrt+2 + γ2rt+3 + γ3rt+4 + γ4Vt(st+4)]

+

. . . . . . . . .

Summation spaltenweise nach den Rewards rt+k durchführen , dh. zuerstdie rt+1 mit den Gewichten (1 − λ)λk über k = 0, 1, . . . summieren ergibt denWert 1 (geometrische Reihe), dann rt+2 mit den Gewichten (1 − λ)γλk überk = 1, 2, 3, . . . ergibt den Wert γλ, usw. mit rt+k für k ≥ 3, 4, . . ..


1

α∆V λ

t (st) = −Vt(st) + (γλ)0[rt+1 + (1 − λ) γVt(st+1)] +

(γλ)1 [rt+2 + (1 − λ) γVt(st+2)] +

(γλ)2[rt+3 + (1 − λ) γVt(st+3)] +

(γλ)3 [rt+4 + (1 − λ) γVt(st+4)] +

. . . . . . . . .

= (γλ)0 [rt+1 + γVt(st+1) − Vt(st)] +

(γλ)1[rt+2 + γVt(st+2) − Vt(st+1)] +

(γλ)2[rt+3 + γVt(st+3) − Vt(st+2)] +

(γλ)3 [rt+4 + γVt(st+4) − Vt(st+3)] +

. . . . . . . . .

=∞∑

k=t

(γλ)k−t

δk =T−1∑

k=t

(γλ)k−t

δk


Wir können somit für die Summe der Updates durch λ-Return schreiben:

T−1∑

t=0

∆V TDt (s)1[s=st] = α

T−1∑

t=0

(

T−1∑

k=t

(γλ)k−t

δk

)

1[s=st]

= αT−1∑

t=0

1[s=st]

T−1∑

k=t

(γλ)k−t

δk.


Nun die Updates des TD(0) Verfahrens: Zunächst gilt

et(s) =

t∑

k=0

(γλ)t−k

1[s=sk]

Einsetzen liefert nunT−1∑

t=0

∆V TDt (s) =

T−1∑

t=0

αδt

t∑

k=0

(γλ)t−k1[s=sk]

= αT−1∑

k=0

k∑

t=0

(γλ)k−t

1[s=st]δk

= αT−1∑

t=0

T−1∑

k=t

(γλ)k−t

1[s=st]δk

= αT−1∑

t=0

1[s=st]

T−1∑

k=t

(γλ)k−t δk


Sarsa(λ)

• Idee von Sarsa(λ) ist, den Sarsa-Algorithmus zum Erlernen der Q-Funktion mit der TD(λ) Methoden zu kombinieren.

• Statt der Variablen et(s) für alle s ∈ S brauchen wir Variablen et(s, a) füralle (s, a) ∈ S × A.

• Dann ersetzen wir V (s) durch Q(s, a) und et(s) durch et(s, a). Also

Qt+1(s, a) = Qt(s, a) + αδtet(s, a) für alle s ∈ S, a ∈ A

δt = rt+1 + γQt(st+1, at+1) − Qt(st, at)

und

et(s, a) =

{

γλet−1(s) + 1 falls st = s und at = a

γλet−1(s) sonst


Sarsa Backup Diagramm

λT-t-1

s , at

1−λ

(1−λ) λ

(1−λ) λ2

Σ = 1

t

sT

Sarsa(λ )


Sarsa Algorithmus ( Q als Tabelle)

1. Initalize Q(s, a) arbitrarily and e(s, a) = 0 all s, a

2. Repeat (for each episode)Initialize s, a


Take a, observe reward r, and next state s′


δ := r + γQ(s′, a′) − Q(s, a)

e(s, a) := e(s, a) + 1

For all s, a:

Q(s, a) := Q(s, a) + αδe(s, a)

e(s, a) := λγe(s, a)

s := s′; a := a′

Until s is terminal


Q(λ)-Lernverfahren

• Es gibt 2 Varianten: Watkin’s Q(λ) und Peng’s Q(λ) Verfahren (Letzterer istschwerer implementierbar, deshalb hier nur Watkin’s Q-Lernverfahren).

• Q-Lernen ist ein Off-Policy Verfahren.

• Beim Q-Lernen folgt der Agent einer explorativen Policy (z.B. ǫ-GreedyVerfahren bzgl. der Q-Funktion) und adaptiert die Q-Funktion nach derGreedy-Policy (bzgl. der Q-Funktion).

• Hier muss in Betracht gezogen werden, dass der Agent explorative Aktio-nen durchführt, die keine Greedy Aktionen sind.

• Zum Erlernen der zur Greedy Policy gehörenden Q-Funktionen dürfen die-se explorativen Aktionen nicht berücksichtigt werden.

• Deshalb werden die n-step Returns beim Q(λ) Verfahren auch nur bis zumAuftreten der nächsten explorativen Aktion berücksichtigt, und nicht stetsbis zum Ende einer Episode.


Q(λ) Backup-Diagramm (Watkins)

1−λ

(1−λ) λ

(1−λ) λ2

Watkins's Q(λ )

OR

firstnon-greedyactionλn−1

s , at t

st+n

λT-t-1


Q(λ)-Algorithmus ( Q als Tabelle)

1. Initalize Q(s, a) arbitrarily and e(s, a) = 0 all s, a

2. Repeat (for each episode)Initialize s, a

Repeat (for each step of episode):Take a, observe reward r, and next state s′


a∗ := arg maxbQ(s′, b) (if a′ ties for the max, then a∗ := a′).

δ := r + γQ(s′, a∗) − Q(s, a)

e(s, a) := e(s, a) + 1

For all s, a:Q(s, a) := Q(s, a) + αδe(s, a)

if a′ = a∗ then e(s, a) := λγe(s, a) else e(s, a) := 0

s := s′; a := a′

Until s is terminal


RL und Funktionsapproximation

• Bisher sind haben wir die Funktionen V oder Q als Tabellen gespeichert.• Im Allgemeinen sind die Zustandsräume und die Zahl der möglichen Ak-

tionen sehr groß.• Deshalb besteht enormer Speicherbedarf. Andereits, liegen in den Anwen-

dungen meist gar nicht genügend Beispieldaten zur Verfügung, um die Vund insbesondere die Q-Funktion vollständig zu lernen.

• Dies ist insbesondere dann der Fall, wenn der Zustandsraum bzw. auchder Aktionenraum (teilweise) kontinuierliche Größen enthält.

• Einziger Weg in diesen Problemstellungen eine Funktion zu lernen, ist dieGeneralisierung. Genauer gesagt die Funktionsapproximation.

• Zur Approximation von Funktionen sind viele Verfahren bekannt (Polyno-me, Splines, künstliche neuronale Netze, Regressionsbäume, etc).

• Funktionsapproximation ist ein wichtiges Beispiel aus dem Bereich desüberwachten Lernens .


• Ziel: Überwachte Lernverfahren zur Funktionsapproximation (eben zur Ap-proximation der V und insbesonder der Q-Funktion mit den bekannten RLLernverfahren kombinieren).

• Für das überwachte Lernen steht eine Vielzahl von Methoden bereit.• Wir beginnen wieder mit dem Problem V π für eine feste Policy pi berech-

nen.• Dazu gehen wir jetzt davon aus, Vt sei nicht als Tabelle Vt(s) mit s ∈ S

gegeben, sondern als eine parametrisierte Funktion mit einem Parameter-vektor θt.

• Der Wert von Vt(s) hängt jetzt von θt ab, etwa die synaptischen Kopp-lungsgewichte eines künstlichen neuronalen Netzes, die Koeffizienten ei-nes multivariaten Polynoms, usw.

• Typischerweise ist die Zahl der Zustände (zustands-Aktions-Paare) sehrviel größer als die Anzahl der reellen Parameter in θ.

• Änderung eines einzelnen Parameters in θ, beeinflusst den Wert der Funk-tion potenziell an allen Stellen, d.h. V (s) ändert sich für alle Zustände s(Q(s, a) ändert sich für alle (s, a)).


• Vorgehen beim Erlernen der V -Funktion: Paar bestehend aus (st, vt) mits ∈ S und dem Lehrersignal v ∈ R verwenden um θt so anzupassen, dassV (st) ≈ vt wird.

• Was sind nun die Lehrersignale vt? Dies hängt vom Verfahren ab: BeimTD(0) Backup ist vt = rt+1 + γtVt(st+1).Bei den Monte Carlo Verfahren gilt vt = Rt und bei den TD(λ) Verfahrenvt = Rλ

t .• Häufig verwendetes Performanzmaß ist der MSE

E(θt) =∑

s∈S

(V π(s) − V (θt)(s))2

• Gesucht ist nun der Vektor θ∗, der den Fehler möglichst klein ist undE(θ∗) ≤ E(θ) für alle θ, also ein globales Minimum des quadratischenFehlers. Dies ist allerdings nur für einfache Funktionsapproimationssche-mata möglich.

• Im Allgemeinen ist auf Lösungen θ∗ angewiesen, die numerisch (z.B. Gra-dientenverfahren) berechnet werden und bei denen es sich um lokale Mi-nima der Fehlerfunktion handelt.


On-line Gradient- TD( λ)

1. Initalize θ ∈ RN arbitrarily and e ∈ R

N ; π policy to be evaluated


Initialize s


a := π(s)


δ := r + γVθ(s′) − Vθ(s)

e := γλe + gradθ(V (s));

θ := θ + αδe

s := s′

Until s is terminal


Lineare Funktionsapproximation

• Hier ist Vt(s) eine lineare Funktion des Parametervektors θt also

Vt(s) =∑

i

θiφi(s)

• Dann ist der Gradient

∂V

∂θi= φi(s)

• Für lineare Funktionsapproximatoren konvergiert die Optimierung nach derquadratischen Fehlerfunktion gegen ein globales Optimum θ∗

• Für das Gradienten TD(λ) Verfahren mit lineare Wertfunktion Vt(s) =∑

i θiφi(s) lässt sich zeigen Konvergenz gegen ein θ∞, das dem theore-tischen Optimum nahe kommt. Es gilt:

E(θ∞) ≤1 − γλ

1 − γE(θ∗)


Lineare Funktionsapproximatoren

Es sei S ⊂ Rn.

• Radiale Basisfunktionen

Vt(s) =∑

i

θi exp

(

−‖s − ci‖

2

2σ2i

)

+ θ0

mit σi > 0, ci ∈ Rn.

Hier in R dargestellt

ci

σi

ci+1ci-1


• Coarse Coding (eine binäre Variante von RBFs)

Vt(s) =∑

i

1{‖s−ci‖2≤σ2i }

mit σi > 0, ci ∈ Rn.

Veranschaulichung im R2


Beispiele möglicher Verallgemeinerungen

a) Narrow generalization b) Broad generalization c) Asymmetric generalization

• Polynomfunktionen vom Grad ≤ 1

Vt(s) =∑

i

θisi + θ0


Q(λ) mit Gradientenverfahren

Es lassen sich jetzt die Funktionsapproximationsverfahren (lineare oder nichtlinear) mit un-terschiedlichen Kodierungen des Zustandsraums mit den verschiedenen Verfahren des Re-inforcementlernens verbinden. So entstehen eine Vielzahl von Lernverfahren. Beispiel: Q(λ)mit Gradientenverfahren für lineare Qa Funktionen mit Gradientenverfahren für binäre Merk-malskodierung

1. Initalize θ ∈ RN arbitrarily and e ∈ R

N


Initialize s

For all a ∈ A(s)

Fa := set of features present in (s, a)

Qa :=∑

i∈Faθi


With probability 1 − ǫ:

a := arg max′aQa′


e := γλe

else

a := random action ∈ A(s)

e := 0

For all features i ∈ Fa:

ei := ei + 1


δ := r − Qa

For all a ∈ A(s′)

Fa := set of features present in (s′, a)

Qa :=∑

i∈Faθi

a′ := arg maxaQa

δ := δ + γQa′

θ := θ + αδe

Until s′ is terminal


Documents

Reinforcement Learning · Reinforcement Learning Friedhelm Schwenker Institut für Neuroinformatik • Vorlesung/Übung: (V) Di 14-16 Uhr, (Ü) Do 12.30-14.00 jeweils im Raum O27/121