Reinforcement Learning - Exam

Aufgabe 1)

Betrachten wir einen Markov-Entscheidungsprozess (MDP) mit den folgenden Parametern:

• Eine Menge von Zuständen: S = \{s_1, s_2, s_3\}
• Eine Menge von Aktionen: A = \{a_1, a_2\}
• Übergangswahrscheinlichkeiten: P(s'|s,a)
• Belohnungsfunktion: R(s,a,s')

Die genauen Übergangswahrscheinlichkeiten und Belohnungswerte sind in den folgenden Tabellen angegeben:Übergangswahrscheinlichkeiten P(s'|s,a):

• \(P(s_1|s_1,a_1) = 0.7, P(s_2|s_1,a_1) = 0.3\)
• \(P(s_2|s_2,a_2) = 0.9, P(s_3|s_2,a_2) = 0.1\)
• \(P(s_3|s_3,a_1) = 1.0\)

Belohnungsfunktion R(s,a,s'):

• \(R(s_1,a_1,s_1) = 5, R(s_1,a_1,s_2) = 10\)
• \(R(s_2,a_2,s_2) = 2, R(s_2,a_2,s_3) = 8\)
• \(R(s_3,a_1,s_3) = 0\)

a)

Bestimme die einperiodigen erwarteten Belohnungen (Reward) für die Zustände \(s_1\) und \(s_2\), wenn die Aktionen \(a_1\) bzw. \(a_2\) ausgeführt werden. Zeige alle Berechnungsschritte.

Lösung:

Einperiodige erwartete Belohnungen für die Zustände s₁ und s₂, wenn die Aktionen a₁ bzw. a₂ ausgeführt werden

Um die erwarteten Belohnungen (Rewards) zu berechnen, verwenden wir die Übergangswahrscheinlichkeiten und die Belohnungsfunktion. Die erwartete Belohnung für eine Aktion a in einem Zustand s berechnet sich nach der Formel:

\[ER(s,a) = \sum_{s'} \big( P(s'|s,a) * R(s,a,s') \big)\]

Berechnung für Zustand s₁ und Aktion a₁

\t
• P(s₁|s₁,a₁) = 0.7
\t
• P(s₂|s₁,a₁) = 0.3
\t
• R(s₁,a₁,s₁) = 5
\t
• R(s₁,a₁,s₂) = 10

Die erwartete Belohnung ist:

\[ER(s₁,a₁) = P(s₁|s₁,a₁) * R(s₁,a₁,s₁) + P(s₂|s₁,a₁) * R(s₁,a₁,s₂)\]\[ER(s₁,a₁) = (0.7 * 5) + (0.3 * 10)\]\[ER(s₁,a₁) = 3.5 + 3 = 6.5\]

Berechnung für Zustand s₂ und Aktion a₂

\t
• P(s₂|s₂,a₂) = 0.9
\t
• P(s₃|s₂,a₂) = 0.1
\t
• R(s₂,a₂,s₂) = 2
\t
• R(s₂,a₂,s₃) = 8

Die erwartete Belohnung ist:

\[ER(s₂,a₂) = P(s₂|s₂,a₂) * R(s₂,a₂,s₂) + P(s₃|s₂,a₂) * R(s₂,a₂,s₃)\]\[ER(s₂,a₂) = (0.9 * 2) + (0.1 * 8)\]\[ER(s₂,a₂) = 1.8 + 0.8 = 2.6\]

Daraus ergeben sich die erwarteten einperiodigen Belohnungen:

\t
• ER(s₁,a₁) = 6.5
\t
• ER(s₂,a₂) = 2.6

b)

Es sei \(\gamma = 0.9\) der Diskontierungsfaktor. Berechne die Wertfunktionen \(V(s_1)\) und \(V(s_2)\) in der ersten Iteration der Value Iteration Methode, basierend auf Deiner Berechnung in Teil a).

Lösung:

Berechnung der Wertfunktionen V(s₁) und V(s₂) in der ersten Iteration der Value Iteration Methode

Zuerst fassen wir die in Teil a) berechneten erwarteten Belohnungen (Rewards) zusammen:

• ER(s₁, a₁) = 6.5
• ER(s₂, a₂) = 2.6

Die Wertfunktionsformel in der Value Iteration Methode lautet:

 \[ V(s) = \text{max}_a \big( ER(s, a) + \gamma \sum_{s'} P(s'|s, a) V(s') \big) \]

In der ersten Iteration ergibt V(s) gleich 0 für alle Zustände, da wir bei Value Iteration mit den Initialwerten 0 beginnen.

Berechnung für Zustand s₁

Erinnern wir uns an die erwartete Belohnung: ER(s₁, a₁) = 6.5

\[ V(s₁^{(1)}) = \text{max} \big( ER(s₁, a₁) + \gamma ( P(s₁|s₁, a₁)V(s₁^{(0)}) + P(s₂|s₁, a₁)V(s₂^{(0)}) ) \big) \] \[ V(s₁^{(1)}) = \text{max} \big( 6.5 + 0.9 \times ( 0.7 \times 0 + 0.3 \times 0) \big) \] \[ V(s₁^{(1)}) = \text{max} \big( 6.5 \big) \] \[ V(s₁^{(1)}) = 6.5 \]

Berechnung für Zustand s₂

Erinnern wir uns an die erwartete Belohnung: ER(s₂, a₂) = 2.6

\[ V(s₂^{(1)}) = \text{max} \big( ER(s₂, a₂) + \gamma ( P(s₂|s₂, a₂)V(s₂^{(0)}) + P(s₃|s₂, a₂)V(s₃^{(0)}) ) \big) \] \[ V(s₂^{(1)}) = \text{max} \big( 2.6 + 0.9 \times ( 0.9 \times 0 + 0.1 \times 0) \big) \] \[ V(s₂^{(1)}) = \text{max} \big( 2.6 \big) \] \[ V(s₂^{(1)}) = 2.6 \]

Daraus ergeben sich die Wertfunktionen in der ersten Iteration:

• V(s₁) = 6.5
• V(s₂) = 2.6

c)

Bestimme eine Greedy-Politik \(\pi\) basierend auf den mittels Value Iteration berechneten Werten aus Teil b). Zeige, wie die Politik aus den berechneten Werten abgeleitet wird.

Lösung:

Bestimmung einer Greedy-Politik \(\pi\) basierend auf den berechneten Werten

Wir haben bereits die Wertfunktionen \(V(s_1)\) und \(V(s_2)\) in der ersten Iteration der Value Iteration Methode aus Teil b) berechnet:

• V(s_1) = 6.5
• V(s_2) = 2.6

Um eine Greedy-Politik \(\pi\) zu bestimmen, wählen wir für jeden Zustand die Aktion, die den höchsten Wert ergibt. Dazu berechnen wir für jede Aktion den Q-Wert (den Wert der Zustand-Aktion-Paare).

Berechnung der Q-Werte für jeden Zustand und jede Aktion

Für den Zustand s_1

Es gibt nur eine Aktion \(a_1\):

\[Q(s_1, a_1) = ER(s_1, a_1) + \gamma \sum_{s'} P(s'|s_1, a_1) V(s') \]

• Erwartete Belohnung: \(ER(s_1, a_1) = 6.5\)
• \(P(s_1|s_1, a_1) = 0.7\)
• \(P(s_2|s_1, a_1) = 0.3\)
• Der Diskontierungsfaktor \(\gamma = 0.9\)

Berechnung:

\[Q(s_1, a_1) = 6.5 + 0.9 (0.7 * V(s_1) + 0.3 * V(s_2))\]\[Q(s_1, a_1) = 6.5 + 0.9 (0.7 * 6.5 + 0.3 * 2.6)\]\[Q(s_1, a_1) = 6.5 + 0.9 (4.55 + 0.78)\]\[Q(s_1, a_1) = 6.5 + 0.9 * 5.33\]\[Q(s_1, a_1) = 6.5 + 4.797\]\[Q(s_1, a_1) = 11.297\]

Für den Zustand s_2

Es gibt nur eine Aktion \(a_2\):

\[Q(s_2, a_2) = ER(s_2, a_2) + \gamma \sum_{s'} P(s'|s_2, a_2) V(s') \]

• Erwartete Belohnung: \(ER(s_2, a_2) = 2.6\)
• \(P(s_2|s_2, a_2) = 0.9\)
• \(P(s_3|s_2, a_2) = 0.1\)
• Der Diskontierungsfaktor \(\gamma = 0.9\)\

Berechnung:

\[Q(s_2, a_2) = 2.6 + 0.9 (0.9 * V(s_2) + 0.1 * V(s_3))\]\[Q(s_2, a_2) = 2.6 + 0.9 (0.9 * 2.6 + 0.1 * 0)\]\[Q(s_2, a_2) = 2.6 + 0.9 (2.34 + 0)\]\[Q(s_2, a_2) = 2.6 + 0.9 * 2.34\]\[Q(s_2, a_2) = 2.6 + 2.106\]\[Q(s_2, a_2) = 4.706\]

Bestimmung der Greedy-Politik

Da wir nur eine Aktion pro Zustand zur Verfügung haben, ist die Politik eindeutig:

• Für Zustand s_1 wählen wir Aktion a_1, da kein anderer zur Auswahl steht.
• Für Zustand s_2 wählen wir Aktion a_2, da kein anderer zur Auswahl steht.

Die Greedy-Politik lautet daher:

• \(\pi(s_1) = a_1\)
• \(\pi(s_2) = a_2\)

Aufgabe 2)

Gegeben ist ein Diskreter Markov-Entscheidungsprozess (MDP) mit den folgenden Komponenten:

• Eine Menge von Zuständen S = {s1, s2, s3}
• Eine Menge von Aktionen A = {a1, a2}
• Eine Belohnungsfunktion R(s, a)
• Eine Übergangswahrscheinlichkeitsfunktion P(s'|s, a)
• Ein Diskontierungsfaktor \(0 < \gamma \leq 1\) = 0.9

Im Folgenden sei der Belohnungswert R(s, a) für alle Zustände und Aktionen auf 0 gesetzt, außer für den Zustand s3, bei dem die Belohnung 1 beträgt, wenn Aktion a1 ausgeführt wird:

• R(s3, a1) = 1

Die Übergangswahrscheinlichkeiten sind wie folgt gegeben:

• Für alle Zustände und Aktionen gilt: P(s'|s, a) = 1, wenn s' = s, sonst 0 (stochastische Selbstübergänge).

Finde die optimale Politik und die dazugehörigen optimalen Wertefunktionen V\(s\) und Q\(s, a\) für jeden Zustand in S unter Verwendung der Bellman-Gleichungen.

a)

Berechne die optimale Wertefunktion V\(s\) für jeden Zustand in S unter Verwendung der optimalen Bellman-Gleichung für die Wertefunktion.

Lösung:

Um die optimale Wertefunktion V(s) für jeden Zustand in S zu berechnen, nutzen wir die Bellman-Gleichung für die Wertefunktion, die wie folgt lautet:

\[V^*(s) = \text{max}_a \bigg[ R(s, a) + \beta \times \bar{E} \big[V^*(s')\big] \bigg]\]

Hierbei ist:

• \[ \beta \text{ = Diskontierungsfaktor} = 0.9 \]
• \[ R(s, a) \text{ = Belohnungsfunktion} \]
• \[ \bar{E} \big[V^*(s')\big] \text{ = Erwartungswert der Wertefunktion für den nächsten Zustand} \]

Gegeben ist:

• Für jeden Zustand außer s3 ist die Belohnung 0.Bei Zustand s3 und Aktion a1 ist die Belohnung 1.

Schritte zur Bestimmung der optimalen Wertefunktion V*(s):

Zustand s1:

• P(s' | s1, a1) = 1 für s' = s1, sonst 0
• P(s' | s1, a2) = 1 für s' = s1, sonst 0

Bellman-Gleichung: \[ V^*(s1) = \text{max} \bigg[ R(s1, a1) + 0.9 \times V^*(s1), R(s1, a2) + 0.9 \times V^*(s1) \bigg] \]Da R(s1, a1) = 0 und R(s1, a2) = 0: \[ V^*(s1) = \text{max} \bigg[ 0 + 0.9 \times V^*(s1), 0 + 0.9 \times V^*(s1) \bigg] \]Da die Wertefunktion für s1 nur von sich selbst abhängig ist und alle Belohnungen 0 sind:

• \[ V^*(s1) = 0 \]

Zustand s2:

• P(s' | s2, a1) = 1 für s' = s2, sonst 0
• P(s' | s2, a2) = 1 für s' = s2, sonst 0

Bellman-Gleichung:\[ V^*(s2) = \text{max} \bigg[ R(s2, a1) + 0.9 \times V^*(s2), R(s2, a2) + 0.9 \times V^*(s2) \bigg] \]Da R(s2, a1) = 0 und R(s2, a2) = 0:\[ V^*(s2) = \text{max} \bigg[ 0 + 0.9 \times V^*(s2), 0 + 0.9 \times V^*(s2) \bigg] \]Da die Wertefunktion für s2 nur von sich selbst abhängig ist und alle Belohnungen 0 sind:

• \[ V^*(s2) = 0 \]

Zustand s3:

• P(s' | s3, a1) = 1 für s' = s3, sonst 0
• P(s' | s3, a2) = 1 für s' = s3, sonst 0

Bellman-Gleichung:\[ V^*(s3) = \text{max} \bigg[ R(s3, a1) + 0.9 \times V^*(s3), R(s3, a2) + 0.9 \times V^*(s3) \bigg] \]Da R(s3, a1) = 1 und R(s3, a2) = 0:\[ V^*(s3) = \text{max} \bigg[ 1 + 0.9 \times V^*(s3), 0 + 0.9 \times V^*(s3) \bigg] \]

• Für Aktion a1:\[ V^*(s3) = 1 + 0.9 \times V^*(s3) \]

Um diese Gleichung zu lösen, substituieren wir :

• \[ V^*(s3) = 1 + 0.9 \times V^*(s3) \]\[ V^*(s3) - 0.9 \times V^*(s3) = 1 \]\[ 0.1 \times V^*(s3) = 1 \]\[ V^*(s3) = 10 \]

Ergebnisse:

• \[ V^*(s1) = 0 \]
• \[ V^*(s2) = 0 \]
• \[ V^*(s3) = 10 \]

b)

Berechne die optimale Q-Funktion Q\(s, a\) für jeden Zustand in S und jede Aktion in A unter Verwendung der optimalen Bellman-Gleichung für die Q-Funktion.

Lösung:

Um die optimale Q-Funktion Q(s, a) für jeden Zustand in S und jede Aktion in A zu berechnen, verwenden wir die Bellman-Gleichung für die Q-Funktion. Diese lautet:

\[Q^*(s, a) = R(s, a) + \beta \sum_{s' \in S} P(s' | s, a) V^*(s') \]

Wir haben bereits die optimalen Wertefunktionen V*(s) berechnet:

• \[ V^*(s1) = 0 \]
• \[ V^*(s2) = 0 \]
• \[ V^*(s3) = 10 \]

Lass uns nun die optimale Q-Funktion Q*(s, a) für jeden Zustand und jede Aktion berechnen:

Zustand s1:

• \[Q^*(s1, a1) = R(s1, a1) + 0.9 \times P(s1 | s1, a1) \times V^*(s1)\]
• \[Q^*(s1, a2) = R(s1, a2) + 0.9 \times P(s1 | s1, a2) \times V^*(s1)\]

Da \[ R(s1, a1) = 0 \] und \[R(s1, a2) = 0\], sowie \[P(s'|s1, a) = 1\] für s' = s1:

• \[Q^*(s1, a1) = 0 + 0.9 \times 1 \times 0 = 0 \]
• \[Q^*(s1, a2) = 0 + 0.9 \times 1 \times 0 = 0 \]

Zustand s2:

• \[Q^*(s2, a1) = R(s2, a1) + 0.9 \times P(s2 | s2, a1) \times V^*(s2)\]
• \[Q^*(s2, a2) = R(s2, a2) + 0.9 \times P(s2 | s2, a2) \times V^*(s2)\]

Da \[ R(s2, a1) = 0 \] und \[R(s2, a2) = 0\], sowie \[P(s'|s2, a) = 1\] für s' = s2:

• \[Q^*(s2, a1) = 0 + 0.9 \times 1 \times 0 = 0 \]
• \[Q^*(s2, a2) = 0 + 0.9 \times 1 \times 0 = 0 \]

Zustand s3:

• \[Q^*(s3, a1) = R(s3, a1) + 0.9 \times P(s3 | s3, a1) \times V^*(s3)\]
• \[Q^*(s3, a2) = R(s3, a2) + 0.9 \times P(s3 | s3, a2) \times V^*(s3)\]

Da \[ R(s3, a1) = 1 \] und \[R(s3, a2) = 0\], sowie \[P(s'|s3, a) = 1\] für s' = s3:

• \[Q^*(s3, a1) = 1 + 0.9 \times 1 \times 10 = 10 \]
• \[Q^*(s3, a2) = 0 + 0.9 \times 1 \times 10 = 9 \]

Ergebnisse:

• \[Q^*(s1, a1) = 0 \]
• \[Q^*(s1, a2) = 0 \]
• \[Q^*(s2, a1) = 0 \]
• \[Q^*(s2, a2) = 0 \]
• \[Q^*(s3, a1) = 10 \]
• \[Q^*(s3, a2) = 9 \]

c)

Leite aus den Ergebnissen der vorherigen Teilaufgaben die optimale Politik π*(s) für jeden Zustand in S ab.

Lösung:

Um die optimale Politik \( \pi^*(s) \) für jeden Zustand \( s \) in \( S \) abzuleiten, betrachten wir die zuvor errechneten Q-Werte. Die optimale Politik wählt in jedem Zustand die Aktion, die den höchsten Q-Wert hat.

Erinnerung an die optimalen Q-Werte:

• \[ Q^*(s1, a1) = 0 \]
• \[ Q^*(s1, a2) = 0 \]
• \[ Q^*(s2, a1) = 0 \]
• \[ Q^*(s2, a2) = 0 \]
• \[ Q^*(s3, a1) = 10 \]
• \[ Q^*(s3, a2) = 9 \]

Zustand s1:

• Für \( s1 \) sind die Q-Werte für beide Aktionen gleich: \[ Q^*(s1, a1) = 0 \] und \[ Q^*(s1, a2) = 0 \].Das bedeutet, dass beide Aktionen gleichwertig sind. Wir können daher eine beliebige Aktion wählen. Beispiel: \[ \pi^*(s1) = a1 \] oder \[ \pi^*(s1) = a2 \]

Zustand s2:

• Für \( s2 \) sind die Q-Werte für beide Aktionen ebenfalls gleich: \[ Q^*(s2, a1) = 0 \] und \[ Q^*(s2, a2) = 0 \].Auch hier können wir eine beliebige Aktion wählen. Beispiel: \[ \pi^*(s2) = a1 \] oder \[ \pi^*(s2) = a2 \]

Zustand s3:

• Für \( s3 \) sind die Q-Werte unterschiedlich: \[ Q^*(s3, a1) = 10 \] und \[ Q^*(s3, a2) = 9 \].Die Aktion mit dem höheren Q-Wert ist \( a1 \). Daher: \[ \pi^*(s3) = a1 \]

Ergebnisse:

• Zustand s1: \[ \pi^*(s1) = a1 \] oder \[ \pi^*(s1) = a2 \] (beide sind gleichwertig)
• Zustand s2: \[ \pi^*(s2) = a1 \] oder \[ \pi^*(s2) = a2 \] (beide sind gleichwertig)
• Zustand s3: \[ \pi^*(s3) = a1 \]

Aufgabe 3)

• 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\)

a)

Teilaufgabe 1: Betrachte die folgende Episode einer bestimmten Umgebung:

• Zustand S1 -> Aktion A1 -> Zustand S2 (Belohnung = 2)
• Zustand S2 -> Aktion A2 -> Zustand S3 (Belohnung = 3)
• Zustand S3 -> Aktion A3 -> Zustand S1 (Belohnung = 1)

Ermittle die Schätzung des Zustandswertes V(S1) für First-Visit und Every-Visit Monte-Carlo-Methoden dieser Episode.

Die Rückkehrwerte (G) sind wie folgt gegeben:
• G(S1) = 6 (von S1 zu S3 und zurück zu S1)
• G(S2) = 4 (von S2 zu S3)

Lösung:

Um die Schätzung des Zustandswertes V(S1) für die First-Visit und Every-Visit Monte-Carlo-Methoden zu ermitteln, gehen wir wie folgt vor:

Gegebene Episode:

• Zustand S1 -> Aktion A1 -> Zustand S2 (Belohnung = 2)
• Zustand S2 -> Aktion A2 -> Zustand S3 (Belohnung = 3)
• Zustand S3 -> Aktion A3 -> Zustand S1 (Belohnung = 1)

Die Rückkehrwerte (G) sind gegeben als:

• G(S1) = 6 (von S1 zu S3 und zurück zu S1)
• G(S2) = 4 (von S2 zu S3)

Formel zur Schätzung des Zustandswertes: \( V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i \) wobei \( N(s) \) die Anzahl der Besuche des Zustands S in der Episode ist.

1. First-Visit Monte-Carlo-Methode:

• Bei der First-Visit Monte-Carlo-Methode wird der Wert eines Zustands anhand des ersten Besuchs dieses Zustands in einer Episode geschätzt.
• In der gegebenen Episode wird der Zustand S1 zweimal besucht: einmal zu Beginn und einmal am Ende der Episode.
• Da nur der erste Besuch betrachtet wird, verwenden wir lediglich den Rückkehrwert G(S1) = 6.
• Anzahl der ersten Besuche: \( N(S1) = 1 \)
• Formel anwenden: \( V(S1) = \frac{1}{1} \sum_{i=1}^{1} G_i = 6 \)
• Ergebnis: V(S1) = 6

2. Every-Visit Monte-Carlo-Methode:

• Bei der Every-Visit Monte-Carlo-Methode wird der Wert eines Zustands anhand jedes Besuchs dieses Zustands in einer Episode geschätzt.
• In der gegebenen Episode wird der Zustand S1 zweimal besucht.
• Rückkehrwerte für jeden Besuch: - Beim ersten Besuch: G(S1) = 6 - Beim zweiten Besuch: 0 (da keine weiteren Schritte in der Episode folgen)
• Somit haben wir: Rückkehrwert beim ersten Besuch: 6 Rückkehrwert beim zweiten Besuch: 0
• Summiere die Rückkehrwerte: \( \sum_{i=1}^{N(S1)} G_i = 6 + 0 = 6 \)
• Anzahl der Besuche: \( N(S1) = 2 \)
• Formel anwenden: \( V(S1) = \frac{1}{2} \sum_{i=1}^{2} G_i = \frac{1}{2} \cdot 6 = 3 \)
• Ergebnis: V(S1) = 3

Zusammenfassung der Ergebnisse:

• First-Visit Monte-Carlo-Methode: V(S1) = 6
• Every-Visit Monte-Carlo-Methode: V(S1) = 3

b)

Teilaufgabe 2: Implementiere in Python eine Funktion zur Schätzung des Zustandswertes V(s) basierend auf der Every-Visit Monte-Carlo-Methode. Die Funktion soll eine Liste von Episoden erhalten, wobei jede Episode als Liste von Zustands-Belohnung-Paaren dargestellt wird. Nutze dabei die Formel: \(V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i\).

 def monte_carlo_every_visit(episodes):    # initialisieren    value_estimates = {}    visit_count = {}    # Schleife über alle Episoden    for episode in episodes:        total_return = 0        for state, reward in episode:            # Update Besuchszähler und Rückkehrwert            if state not in visit_count:                visit_count[state] = 0                value_estimates[state] = 0            visit_count[state] += 1            total_return += reward            value_estimates[state] += (total_return - value_estimates[state]) / visit_count[state]    return value_estimates 

Beschreibe zusätzlich, welch Schlüsselidee hinter der Monte-Carlo Every-Visit Methode steht und inwieweit sich diese von der First-Visit Methode unterscheidet.

Lösung:

Um die Schätzung des Zustandswertes V(s) basierend auf der Every-Visit Monte-Carlo-Methode in Python zu implementieren, verwenden wir die folgende Funktion. Die Funktion erhält eine Liste von Episoden, wobei jede Episode als Liste von Zustands-Belohnung-Paaren dargestellt wird:

def monte_carlo_every_visit(episodes):    # initialisieren    value_estimates = {}    visit_count = {}    # Schleife über alle Episoden    for episode in episodes:        total_return = 0        for state, reward in episode:            # Update Besuchszähler und Rückkehrwert            if state not in visit_count:                visit_count[state] = 0                value_estimates[state] = 0            visit_count[state] += 1            total_return += reward            value_estimates[state] += (total_return - value_estimates[state]) / visit_count[state]    return value_estimates

Schlüsselidee der Monte-Carlo Every-Visit Methode:

Die Monte-Carlo Every-Visit Methode schätzt den Wert eines Zustands anhand aller Besuche dieses Zustands in allen Episoden. Bei jedem Besuch eines Zustands wird der zugehörige Rückkehrwert (cumulative reward oder total_return) zum bisherigen geschätzten Wert hinzugerechnet. Die Anzahl der Besuche wird aktualisiert und der Wert wird als Durchschnitt der bisher beobachteten Rückkehrwerte berechnet.

Dies unterscheidet sich von der First-Visit Methode, die nur den Rückkehrwert des ersten Besuchs eines Zustands in jeder Episode verwendet. Während die First-Visit Methode nur einmal pro Episode einen Zustand betrachtet, summiert und mittelt die Every-Visit Methode den Rückkehrwert bei jedem Besuch eines Zustands in den Episoden.

Unterschiede zwischen Every-Visit und First-Visit Methoden:

• Every-Visit: Schätzt den Wert eines Zustands basierend auf jedem Besuch des Zustands in den Episoden. Dies ermöglicht eine vollständigere Schätzung, da mehr Datenpunkte berücksichtigt werden.
• First-Visit: Schätzt den Wert eines Zustands basierend auf dem ersten Besuch des Zustands in den Episoden. Dies kann nützlich sein, um Verzerrungen durch mehrfache Besuche in einer einzigen Episode zu vermeiden, berücksichtigt jedoch weniger Datenpunkte.

Aufgabe 4)

Betrachte ein Agenten-Umwelt-Setup, bei dem ein Agent in einer diskreten Zustandsumgebung agiert. Der Agent verwendet das Temporal Difference (TD)-Lernen, um die Wertfunktion der Zustände zu schätzen. Dabei kommen die Methoden TD(0) und TD(λ) zum Einsatz.

a)

(a) Angenommen, der Agent verwendet TD(0) zum Schätzen der Wertfunktion. Beschreibe den Algorithmus für einen gesamten Episodenverlauf. Erläutere, wie die Wertfunktion zu jedem Zeitpunkt aktualisiert wird.

Gehe speziell auf die Verwendung von \( \alpha \) und \( \gamma \) ein und erkläre, wie der Temporaldifferenz-Fehler \( \delta_t \) berechnet wird. Formuliere den TD(0)-Update-Schritt mathematisch klar und beschreibe ein Beispiel, um das Verfahren zu illustrieren.

Lösung:

Um die Wertfunktion der Zustände mit Hilfe von TD(0) zu schätzen, verwendet der Agent eine Methode, die auf der Schätzung von Belohnungen basiert. Dieser Prozess läuft über eine gesamte Episode, die eine Abfolge von Zuständen und Aktionen darstellt. Lasst uns den TD(0)-Algorithmus für eine Episode im Detail betrachten:

• Initialisierung: Am Anfang der Episode werden alle Werte der Wertfunktion auf einen initialen Wert gesetzt, zum Beispiel auf null. Die Lernrate (Schrittweite) \( \alpha \) und der Diskontierungsfaktor \( \gamma \) müssen ebenfalls festgelegt werden.
• Durchlauf der Episode: Der Agent durchläuft die Episode von einem Startzustand bis zu einem Endzustand. Für jeden Zeitschritt t innerhalb der Episode führt der Agent die folgenden Schritte durch:
• Zustands- und Belohnungsbeobachtung: Der Agent beobachtet den aktuellen Zustand \( s_t \) und die Belohnung \( r_{t+1} \) und bewegt sich in den nächsten Zustand \( s_{t+1} \).
• Berechnung des Temporaldifferenz-Fehlers: Der Temporaldifferenz-Fehler \( \delta_t \) wird berechnet als: \( \delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \) Dies misst den Unterschied zwischen der geschätzten Wertfunktion und der tatsächlich erhaltenen Belohnung plus der geschätzten zukünftigen Belohnung.
• Aktualisierung der Wertfunktion: Die Wertfunktion \( V(s_t) \) wird aktualisiert als: \( V(s_t) \leftarrow V(s_t) + \alpha \delta_t \) Hierbei gibt \( \alpha \) die Lernrate an, die bestimmt, wie stark neue Informationen die bestehende Wertschätzung anpassen.

Dies wird für jeden Zeitschritt der Episode wiederholt.

Beispiel: Angenommen, ein Agent befindet sich im Zustand \( s_0 \) und erhält im nächsten Zeitschritt eine Belohnung \( r_1 = 5 \), bewegt sich in den Zustand \( s_1 \). Angenommen, der Diskontfaktor \( \gamma = 0.9 \) und die Lernrate \( \alpha = 0.1 \).

• Aktuelle Wertfunktion: \( V(s_0) = 2 \) und \( V(s_1) = 3 \).
• Berechnung des Temporaldifferenz-Fehlers: \( \delta_0 = 5 + 0.9 \cdot 3 - 2 = 5 + 2.7 - 2 = 5.7 - 2 = 3.7 \)
• Aktualisierung der Wertfunktion: \( V(s_0) \leftarrow 2 + 0.1 \cdot 3.7 = 2 + 0.37 = 2.37 \) Die neue geschätzte Wertfunktion für den Zustand \( s_0 \) ist nun 2.37.

Das wird für jeden Zustand in der gesamten Episode fortgesetzt.

b)

(b) Vergleiche TD(0) und TD(λ) hinsichtlich ihrer Updatestrategien. Was sind die Hauptunterschiede zwischen diesen Ansätzen? Erkläre detailliert, was für eine Rolle der Parameter \( \lambda \) bei TD(λ) spielt und wie die Spuren \( e_t \) die Wertaktualisierung beeinflussen. Beschreibe, wie der TD-Fehler \( \delta_t \) hier anders verwendet wird im Vergleich zu TD(0).

Lösung:

Um die Unterschiede und Funktionsweisen von TD(0) und TD(\(\lambda\)) zu verstehen, müssen wir die verschiedenen Updatestrategien und die Funktionsweise der beiden Methoden im Detail betrachten:

TD(0)

• Updatestrategie: TD(0) aktualisiert die Wertfunktion eines Zustands einzig und allein basierend auf dem unmittelbar folgenden Zustand. Das heißt, es wird ein Einzel-Schritt-Update durchgeführt.
• Aktualisierung der Wertfunktion: Die Wertfunktion \( V(s_t) \) wird mit Hilfe der folgenden Formel aktualisiert: \( V(s_t) \leftarrow V(s_t) + \alpha \delta_t \) wobei der Temporal-Differenz-Fehler \( \delta_t \) so berechnet wird: \( \delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \).

TD(\(\lambda\))

• Updatestrategie: TD(\(\lambda\)) verwendet eine Methode, die als 'Eligibility Traces' bekannt ist. Diese Methode ermöglicht es, Updates der Wertfunktion über mehrere Zeitpunkte hinweg zu verfolgen, anstelle sich auf den nächsten Zustand allein zu konzentrieren.
• Eligibility Traces: Die Spuren, \( e_t \), bestimmen, in welchem Maß jeder Zustand im Update berücksichtigt wird. Zu Beginn werden alle Spuren auf null gesetzt. Bei jedem Zeitschritt werden die Spuren aktualisiert: \( e_t(s) = \gamma \, \lambda \, e_{t-1}(s) + I(s_t = s) \) Hierbei ist \( I(s_t = s) \) eine Indikatorfunktion, die 1 ist, wenn der aktuelle Zustand \( s_t \) dem Zustand \( s \) entspricht, und 0 sonst. Diese Spuren zerfallen exponentiell mit der Rate \( \gamma \, \lambda \).
• Aktualisierung der Wertfunktion: Die Aktualisierung erfolgt über die Eligibility Traces und den TD-Fehler:\( V(s) \leftarrow V(s) + \alpha \, \delta_t \, e_t(s) \) Der TD-Fehler \( \delta_t \) wird genauso berechnet wie bei TD(0): \( \delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \). Der Hauptunterschied liegt in der Skalierung durch die Spuren \( e_t \), wodurch frühere Zustände ebenfalls im Update berücksichtigt werden.

Hauptunterschiede:

• Berücksichtigung von Zuständen: TD(0) aktualisiert die Wertfunktion ausschließlich basierend auf dem unmittelbar folgenden Zustand. TD(\(\lambda\)) hingegen berücksichtigt eine Summe über vergangene Zustände, was durch die Eligibility Traces ermöglicht wird.
• Rolle von \( \lambda \): Der Parameter \( \lambda \) steuert die Rate, mit der die Eligibility Traces zerfallen. Ein höheres \( \lambda \) bedeutet, dass frühere Zustände stärker in die Wertaktualisierung einfließen. Ein \( \lambda \) von 0 reduziert TD(\(\lambda\)) zu TD(0).

Zusammengefasst: Der Hauptunterschied zwischen TD(0) und TD(\(\lambda\)) besteht darin, dass TD(0) nur den nächsten Zustand zur Wertaktualisierung verwendet und TD(\(\lambda\)) eine historisch gewichtete Summe von Zuständen berücksichtigt, was durch die Eligibility Traces realisiert wird.

c)

(c) Betrachte eine Episode mit den Zuständen \( \{S_0, S_1, S_2, S_3\} \), in der ein Agent Rewards \( R_t \) an den Zeitpunkten \( t=0,1,2\) erhält: \( R_1 = 1 \,\ R_2 = 2 \, \ R_3 = 3 \). Die Anfangswertfunktion ist \( V(S) = 0 \) für alle Zustände, und die Parameter sind \( \alpha = 0.1 \), \( \gamma = 0.9 \), \( \lambda = 0.8 \).

i) Verwende TD(0), um die Wertfunktion nach einem vollständigen Durchlauf der Episode zu aktualisieren. Zeige die Berechnungsschritte für jeden Zeitschritt.

ii) Verwende TD(λ), um die Wertfunktion nach derselben Episode zu aktualisieren. Berechne die Eligibility Traces und zeige, wie sie die Wertaktualisierung in jedem Zeitschritt beeinflussen. Vergleiche die Endresultate beider Methoden.

Lösung:

Um die Aufgabe zu lösen, werden wir sowohl TD(0) als auch TD(\( \lambda \)) verwenden, um die Wertfunktion für die gegebene Episode zu aktualisieren. Hier sind die detaillierten Schritte und Berechnungen für jeden Teil:

i) Verwende TD(0)

Gegeben:

• Zustände: \( \{S_0, S_1, S_2, S_3\} \)
• Rewards: \( R_1 = 1 \), \( R_2 = 2 \), \( R_3 = 3 \)
• Initiale Wertfunktion: \( V(S) = 0 \) für alle Zustände
• Parameter: \( \alpha = 0.1 \), \( \gamma = 0.9 \)

Zeitschritt 0:

• Aktueller Zustand: \( S_0 \)
• Belohnung: \( R_1 = 1 \)
• Nächster Zustand: \( S_1 \)
• Temporaldifferenz-Fehler: \( \delta_0 = R_1 + \gamma V(S_1) - V(S_0) \) \( \delta_0 = 1 + 0.9 \cdot 0 - 0 = 1 \)
• Aktualisiertes \( V(S_0) \): \( V(S_0) \leftarrow 0 + 0.1 \cdot 1 = 0.1 \)

Zeitschritt 1:

• Aktueller Zustand: \( S_1 \)
• Belohnung: \( R_2 = 2 \)
• Nächster Zustand: \( S_2 \)
• Temporaldifferenz-Fehler: \( \delta_1 = R_2 + \gamma V(S_2) - V(S_1) \) \( \delta_1 = 2 + 0.9 \cdot 0 - 0 = 2 \)
• Aktualisiertes \( V(S_1) \): \( V(S_1) \leftarrow 0 + 0.1 \cdot 2 = 0.2 \)

Zeitschritt 2:

• Aktueller Zustand: \( S_2 \)
• Belohnung: \( R_3 = 3 \)
• Nächster Zustand: \( S_3 \)
• Temporaldifferenz-Fehler: \( \delta_2 = R_3 + \gamma V(S_3) - V(S_2) \) \( \delta_2 = 3 + 0.9 \cdot 0 - 0 = 3 \)
• Aktualisiertes \( V(S_2) \): \( V(S_2) \leftarrow 0 + 0.1 \cdot 3 = 0.3 \)

Die aktualisierte Wertfunktion nach einem Durchlauf mit TD(0) ist:

• \( V(S_0) = 0.1 \)
• \( V(S_1) = 0.2 \)
• \( V(S_2) = 0.3 \)
• \( V(S_3) = 0 \) (keine Änderung, da \( S_3 \) der Endzustand ist).

ii) Verwende TD(\( \lambda \))

Gegeben:

• Zustände: \( \{S_0, S_1, S_2, S_3\} \)
• Rewards: \( R_1 = 1 \), \( R_2 = 2 \), \( R_3 = 3 \)
• Initiale Wertfunktion: \( V(S) = 0 \) für alle Zustände
• Parameter: \( \alpha = 0.1 \), \( \gamma = 0.9 \), \( \lambda = 0.8 \)

Zu Beginn: Alle Eligibility Traces \( e(s) \) sind 0.

Zeitschritt 0:

• Aktueller Zustand: \( S_0 \)
• Belohnung: \( R_1 = 1 \)
• Nächster Zustand: \( S_1 \)
• Temporaldifferenz-Fehler: \( \delta_0 = R_1 + \gamma V(S_1) - V(S_0) \) \( \delta_0 = 1 + 0.9 \cdot 0 - 0 = 1 \)
• Eligibility Trace: \( e(S_0) = \gamma \lambda e(S_0) + 1 = 0.9 \cdot 0.8 \cdot 0 + 1 = 1 \)
• Aktualisiertes \( V(S_0) \): \( V(S_0) \leftarrow V(S_0) + \alpha \delta_t e(S_0) \) \( V(S_0) \leftarrow 0 + 0.1 \cdot 1 \cdot 1 = 0.1 \)

Zeitschritt 1:

• Aktueller Zustand: \( S_1 \)
• Belohnung: \( R_2 = 2 \)
• Nächster Zustand: \( S_2 \)
• Temporaldifferenz-Fehler: \( \delta_1 = R_2 + \gamma V(S_2) - V(S_1) \) \( \delta_1 = 2 + 0.9 \cdot 0 - 0 = 2 \)
• Aktualisierung der Eligibility Traces: \( e(S_0) = \gamma \lambda e(S_0) \leftarrow 0.9 \cdot 0.8 \cdot 1 = 0.72 \) \( e(S_1) = \gamma \lambda e(S_1) + 1 = 0.72 \cdot 0 \leftarrow 0 + 1 = 1 \)
• Aktualisiertes \( V(S_0) \): \( V(S_0) \leftarrow 0.1 + 0.1 \cdot 2 \cdot 0.72 = 0.1 + 0.144 = 0.244 \)
• Aktualisiertes \( V(S_1) \): \( V(S_1) \leftarrow 0 + 0.1 \cdot 2 \cdot 1 = 0.2 \)

Zeitschritt 2:

• Aktueller Zustand: \( S_2 \)
• Belohnung: \( R_3 = 3 \)
• Nächster Zustand: \( S_3 \)
• Temporaldifferenz-Fehler: \( \delta_2 = R_3 + \gamma V(S_3) - V(S_2) \) \( \delta_2 = 3 + 0.9 \cdot 0 - 0 = 3 \)
• Aktualisierung der Eligibility Traces: \( e(S_0) = \gamma \lambda e(S_0) = 0.9 \cdot 0.72 = 0.5184 \) \( e(S_1) = \gamma \lambda e(S_1) = 0.9 \cdot 0.8 \cdot 1 = 0.72 \) \( e(S_2) = 1 \)
• Aktualisiertes \( V(S_0) \): \( V(S_0) \leftarrow 0.244 + 0.1 \cdot 3 \cdot 0.5184 = 0.244 + 0.15552 = 0.39952 \)
• Aktualisiertes \( V(S_1) \): \( V(S_1) \leftarrow 0.2 + 0.1 \cdot 3 \cdot 0.72 = 0.2 + 0.216 = 0.416 \)
• Aktualisiertes \( V(S_2) \): \( V(S_2) \leftarrow 0 + 0.1 \cdot 3 \cdot 1 = 0.3 \)

Die aktualisierte Wertfunktion nach einem Durchlauf mit TD(\( \lambda \)) ist:

• \( V(S_0) = 0.39952 \)
• \( V(S_1) = 0.416 \)
• \( V(S_2) = 0.3 \)
• \( V(S_3) = 0 \) (keine Änderung, da \( S_3 \) der Endzustand ist)

Zusammenfassung:

Nach einem Durchlauf der Episode beträgt die Wertfunktion:

Mithilfe von TD(0):

• \( V(S_0) = 0.1 \)
• \( V(S_1) = 0.2 \)
• \( V(S_2) = 0.3 \)
• \( V(S_3) = 0 \)

Mithilfe von TD(\( \lambda \)):

• \( V(S_0) = 0.39952 \)
• \( V(S_1) = 0.416 \)
• \( V(S_2) = 0.3 \)
• \( V(S_3) = 0 \)

TD(\( \lambda \)) führt zu höheren Wertschätzungen als TD(0), da es nicht nur den nächsten Zustand, sondern eine gewichtete Summe früherer Zustände berücksichtigt.