Reinforcement Learning - Cheatsheet

Markov-Entscheidungsprozesse (MDPs)

Definition:

Markov-Entscheidungsprozesse (MDPs) sind mathematische Modelle zur Modellierung von Entscheidungsfindungen, bei denen das Ergebnis stochastisch ist und von Entscheidungen abhängt.

Details:

• Ein MDP wird definiert durch \(S, A, P, R\):
• \textbf{Zustandsmenge} \(S\)
• \textbf{Aktionsmenge} \(A\)
• \textbf{Übergangswahrscheinlichkeiten} \(P(s'|s,a)\): Wahrscheinlichkeit von Zustand \(s'\) zu Zustand \(s\) durch Aktion \(a\)
• \textbf{Belohnungsfunktion} \(R(s,a,s')\): Erwarteter Ertrag bei Übergang von \(s\) nach \(s'\) durch Aktion \(a\)
• Ziel: Bestimme eine Politik (policy) \(\pi(a|s)\) die den erwarteten kumulierten Ertrag maximiert.

Bellman-Gleichungen

Definition:

Bellman-Gleichungen beschreiben den optimalen Wert einer Zustands-Belohnung-Funktion in einem Markov-Entscheidungsprozess.

Details:

• Optimale Wertefunktion: \( V^*(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s'|s,a) V^*(s') \right] \)
• Optimale Q-Funktion: \( Q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q^*(s', a') \)
• \( V^* \) und \( Q^* \) erfüllen Bellman-Gleichungen, wenn Agent und Umgebung optimal agieren.
• Geben Richtlinien zur Berechnung der optimalen Politik \( \pi^*(s) \).

Monte-Carlo-Methoden: First-Visit und Every-Visit

Definition:

Monte-Carlo-Methoden zur Schätzung von Aktionswerten in Reinforcement Learning.

Details:

• First-Visit: Schätzt die Werte basierend auf dem ersten Besuch eines Zustands in einer Episode.
• Every-Visit: Schätzt die Werte basierend auf jedem Besuch eines Zustands in einer Episode.
• Formel zur Schätzung des Zustandswertes (First-Visit und Every-Visit gleich): \(V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i\)

TD-Lernen: TD(0) und TD(λ)

Definition:

TD-Lernen: Temporal Difference-Lernen kombiniert Monte-Carlo- und Dynamic-Programming-Ansätze zum Schätzen von Wertfunktionen.

Details:

• TD(0) aktualisiert Wertfunktionen nach jedem Zeitschritt durch \( V(S_t) \leftarrow V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t)) \).
• TD(\(\lambda\)) ist ein verallgemeinertes TD-Verfahren, das Rückblick-Updates durchführt:
• TD-Fehler: \( \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \)
• Spuren \( e_t = \gamma \lambda e_{t-1} + 1(S_t = s_t) \)
• Wertaktualisierung: \( V(s) \leftarrow V(s) + \alpha \delta_t e_t \)

Unterschied zwischen Bootstrapping und Sampling

Definition:

Unterschied zwischen Bootstrapping und Sampling im Kontext des Reinforcement Learning

Details:

• Bootstrapping: aktualisiert Schätzungen auf Basis anderer Schätzungen.
• Verwendet geschätzte Werte für temporäre Differenz (TD) Updates.
• Beispiel: Q-Learning, welches die Q-Werte iterativ verbessert.
• Sampling: nutzt echte, beobachtete Datenpunkte.
• Erfordert vollständige Episoden bzw. Stichproben aus der Umgebung.
• Beispiel: Monte-Carlo Methoden, welche basierend auf beobachteten Rückmeldungen auswerten.

Deep Q-Learning und Varianten

Definition:

Deep Q-Learning kombiniert Q-Learning mit neuronalen Netzen, um Q-Funktionen in komplexen, hochdimensionalen Zustandsräumen zu approximieren.

Details:

• Q-Learning: Algorithmus im Reinforcement Learning zur Bestimmung der optimalen Politik.
• Q-Funktion: Bewertet den Nutzen einer Aktion in einem bestimmten Zustand.
• Neuronales Netz: Approximiert die Q-Funktion, um generalisieren zu können.
• Loss-Funktion: MSE zwischen Q-Werten und Zielwerten \(\text{Loss} = \frac{1}{2}(Q_{\text{target}} - Q(s,a))^2\)
• Erfahrungsspeicher: Speicherung von Übergängen \((s, a, r, s')\) zur Stabilisierung des Lernprozesses.
• Target-Netzwerk: Separates Netzwerk zur Berechnung von Ziel-Q-Werten, um die Lernstabilität zu erhöhen.
• Double DQN: Verhindert Überschätzung der Q-Werte mithilfe eines zweiten Netzwerks.
• Dueling DQN: Trennt Zustandswert- und Vorteilsschätzungen, um Lernleistung zu verbessern.

Policy Gradients und Actor-Critic-Methoden

Definition:

Policy-Gradient-Methoden optimieren direkt die Policy \(\theta\), indem sie den erwarteten kumulativen Belohnungsgradienten maximieren. Actor-Critic-Methoden kombinieren Policy-Gradient und Value-Function-Ansätze.

Details:

• Policy-Gradient-Methoden: Gradientensteigerung für bessere Aktionen
• Policy abgeleitet vom Parametervektor \( \theta \)
• Ziel: Maximierung des erwarteten kumulativen Belohnungsgrads \( J(\theta) \)
• Gradientenschätzung mittels Monte-Carlo oder Temporal Difference
• Actor-Critic: Kombination von Policy (Actor) und Value Function (Critic)
• Actor aktualisiert die Policy \( \pi(\theta) \) basierend auf Critic-Bewertungen
• Critic schätzt die Value-Funktion \( V^{\pi}(s) \) oder \( Q^{\pi}(s, a) \)

Inverse Reinforcement Learning

Definition:

IRL: Ermittlung der Belohnungsfunktion, die das Verhalten eines Agenten in einer Umgebung am besten erklärt.

Details:

• Gegeben: Beobachtungen des Verhaltens eines Experten
• Ziel: Schätzung einer zugrunde liegenden Belohnungsfunktion \( R: S \times A \rightarrow \mathbb{R} \)
• Nützlich für: Nachahmungslernen, Verstehen von Expertenverhalten
• Wichtige Algorithmen: MaxEnt IRL, Apprenticeship Learning (Abbeel, Ng)