07 Reinforcement Learning Flashcards
MDP : Markov’scher Entscheidungsprozess
Formalisierung der sequentiellen Entscheidungsfindung
- S (State): ein endlicher Satz von Zuständen
- A (Action): ein endlicher Satz von Aktionen
- P (Probability): Transitionswahrscheinlichkeitsmatrix
- R (Reward): Belohnungsfunktion
- gamma: dicount factor €[0,1]
Diskontierung
die meisten Markov Entscheidungsprozesse werden diskontiert:
- mathematisch praktisch
- vermeidet unendliche Belohnungen in zyklischen Markovprozessen
- Impliziert Unsicherheit über die Zukunft
- Verhalten von Tier und Mensch zeigt Präferenzen für sofortige Belohnungen
Markov Eigenschaft
Ein Zustand erfüllt die Markov Eigenschaft wenn, und nur wenn:
P[S_t+1 | S_t] = P[S_t+1 | S1, …, S_t]
=> Die Zukunft ist unabhängig von der Vergangenheit, wenn man die Gegenwart betrachtet.
Sobald der Zustand bekannt ist, kann die Historie verworfen werden.
Belohnung (Reward)
Ziele können als Maximierung der kummulierten Belohnung beschrieben werden.
- eine Belohnung R_t ist ein skalares Feedbacksignal
- beschreibt die Güte der Aktion zum Zeitpunkt t
- der Agent versucht die kummulierte Belohnung zu maximieren
Basis für Reinforcement Learning ist die Belohnungshypothese
Strategie (Policy)
Eine Strategie π beschreibt das Verhalten des Agenten
- Deterministische Strategie: a= π(s)
- Stochasitsche Strategie: a = π(a | s) = P[A_t = a | S_t = s ]
Psychologisch gesehen: Reiz-Reaktions-Modell
Model
Ein Modell sagt voraus, was die Umgebung als nächstes tun wird
P prognostiziert den nächsten Zustand
R prognostiziert die nächste (unmittelbar) Belohnung
Monte Carlo Methoden (MC)
lernen direkt aus ERfahrungsepisoden
sind modellfrei: benötigt kein Wissen über MDP-Übergänge / Belohnungen
lernen aus kompletten Episoden: kein Bootstrapping
verwenden der einfachsten Idee: Wert = durchschnittliche Belohnung
Problem: kann nur auf episodischen MDPs angewendet werden (alle episoden müssen terminieren)
Temporal-Differance Learning (TD)
lernt direkt aus Erfahrungsepisoden
ist modellfrei: benötigt kein Wissen über MDP-Übergänge / Belohnungen
lernt aus unvollständigen Episoden, durch Bootstrapping
aktualisiert eine Schätzung mit einer Schätzung
Bootstrapping
Bootstrapping (shallow backups):
aktualisierung beruht auf Schätzung:
* dynamische Programmierung
* temporal difference learning
Sampling (sample backups):
Aktualisierung beruht auf Erwartungswert
* monte carlo methoden
* temporal differance learning
Exploration vs Exploitation
Reinforcement Learning ist Trial-and-Error-Lernen
Aktionen müssen undendlich oft ausprobiert werden
Änderung der Suchstrategie von global (Exploration) zu lokal (Exploitation) während des Lernprozesses
On-Policy Learning / Off-Policy Learning
On-Policy Methoden evaluieren oder verbessern die Strategie, welche verwendet wird um Entscheidungen zu treffen
=> Learning on the job
Off-Policy Methoden evaluieren oder verbessern eine Strategie, welche sich von der Strategie unterscheidet um Entscheidungen zu generieren
=> Look over someones shoulder
Lernen von Aktionssequenzen
Belohnung erst nach einer Sequenz von Aktionen bekannt
Schach: Züge bauen aufeinander auf (nicht nur der einzelne Zug relevant)
Belohnung erst am Ziel
Schach: erst am Spielende ist klar wer gewonnen hat
- bei langen Aktionssequenzen kann erst am Ende der Sequenz gelernt werden
- nachfolgende Aktionen können für den schlechten Ausgang verantwortlich sein
Lernen vs Planen
Reinforcement learning:
- die Umgebung ist zunächst unbekannt
- der Agent interagiert mit der Umgebung
- der Agent verbessert seine Strategie
Planen:
- ein Modell der Umgebung ist bekannt
- Der Agent führt mit seinem Modell Berechnungen durch (ohne externe Interaktion)
- Der Agent verbessert seine Strategie
