Arbeitsauftrag 4
In diesem Arbeitsauftrag untersuchen Sie grundlegende Verfahren zum Umgang mit dem Exploration-Exploitation-Trade-off bei Bandit Problems und vergleichen verschiedene Möglichkeiten zur Aktualisierung von Wertschätzungen.
Aufgabe 1 – Exploration und Exploitation
Öffnen Sie die App Exploration vs. Exploitation.
Exploration-vs.-Exploitation-Tool öffnen
Schritte in der App
Wählen Sie einen der beiden Kontexte Party-Opener oder Weg zur Schule aus.
- Versuchen Sie zunächst, durch eigene Entscheidungen die Summe der erhaltenen Belohnungen zu maximieren. (Spielmodus Ich entscheide selbst)
- Wählen Sie dazu immer die nächste Aktion aus und beobachten Sie die Schätzungen der Action-Values.
- Nach Ablauf der voreingestellten Anzahl Runden können Sie unterhalb der Aktionen eine Zusammenfassung ihrer Entscheidungen lesen.
- Vergleichen Sie anschließend Ihre Ergebnisse mit denen eines Agenten im Spielmodus Auto.
- Stellen Sie dazu das Verhalten des Agenten ein (Wissen ausnutzend / erkundend) und würfeln Sie seine Entscheidungen aus.
Aufgabe 2 – Verfahren zur Sicherung von Exploration
Öffnen Sie das Tool zum Vergleich von Explorations-Strategien und testen Sie mindestens ein Verfahren.
Bandit-Exploration-Strategien öffnen
Lösen Sie anschließend mithilfe des Tools folgende Anwendungsaufgabe wie in der 2. Infobox beschrieben:
Kursarbeiten Korrektur
| Kurs (Aktion) | Noten (Belohnungen) |
|---|---|
| GK 1 | 4, 2, 3, 3, 5, 2, 1, 1, 4 |
| GK 2 | 3, 4, 4, 1, 1, 1, 2, 5 |
| GK 3 | 2, 5, 2, 5, 2, 5, 1, 6 |
a) Optimistische Anfangswerte
Frau Hempel ist zunächst „optimistisch“ und setzt für alle drei Kurse den Anfangswert
Sie verwendet eine greedy Strategie mit optimistischen Anfangswerten. Bei einem Gleichstand wählt sie immer eine Klassenarbeit des Kurses mit der kleineren Kursnummer.
Ermitteln Sie jeweils, in welcher Reihenfolge sie die ersten sieben Klassenarbeiten korrigiert.
Untersuchen Sie die folgenden drei Varianten:
- Stichprobenmittel: Der Anfangswert beträgt , zählt aber nicht als Beobachtung.
- Konstante Lernrate: Verwenden Sie .
- Pseudo-Beobachtung: Der Anfangswert wird bei der Mittelwertbildung wie eine zusätzliche Beobachtung gezählt.
Anwendungsaufgabe Kursarbeiten
- Laden Sie die JSON-Datei mit den Beispieldaten herunter.
- Laden Sie im Tool die Datei
klassenarbeiten-bandit-beispiel-v4.json. - Öffnen Sie den Tab Optimistische Anfangswerte.
- Stellen Sie unter Optionen die jeweils zu untersuchende Variante ein.
- Verwenden Sie für die Variante mit konstanter Lernrate .
- Führen Sie die ersten Schritte einzeln aus und vergleichen Sie die angezeigten Rechnungen mit Ihrer Lösung.
- Setzen Sie den Tab anschließend zurück und untersuchen Sie die nächste Variante.
Vertiefung: Upper Confidence Bound
Anhand der folgenden Aufgaben kann das UCB1-Verfahren untersucht werden. Auch diese Aufgaben können mit der App durchgeführt werden, sollen hier aber nicht bearbeitet werden.
Kursarbeiten Korrektur
Zunächst korrigiert sie je eine Klassenarbeit aus jedem Kurs. Für die Auswahl der vierten Klassenarbeit () wird anschließend der Wert
für jede Aktion bestimmt.
i) Auswahl der vierten Klassenarbeit
Begründen Sie ohne ausführliche Rechnung, dass
gilt.
Welche Klassenarbeit wird daher als vierte korrigiert?
ii) Auswahl der fünften Klassenarbeit
Als vierte Klassenarbeit wird die zweite Arbeit aus GK 1 korrigiert. Danach gilt für die geschätzten Aktionswerte
Begründen Sie mithilfe der Auswahlzahlen und des Explorationsanteils der UCB-Formel, warum als Nächstes eine Klassenarbeit aus GK 2 gewählt wird.
Aufgabe 3 – Wissen inkrementell aktualisieren
a) Inkrementelle Aktualisierung visualisieren
Mit dem eingebetteten Tool kann visualisiert werden, wie das arithmetische Mittel von Beobachtungen inkrementell aus dem arithmetische Mitteln von Beobachtungen (und der n-ten Beobachtung) berechnet werden kann. (Dieses Verfahren kann zur Aktualisierung der geschätzten Action-Values verwendet werden.)
Visualisieren Sie mit wenigen (z.B. n=3) Werten, wie sich das arithmetische Mittel des -ten Wertes aus dem zuvor berechneten arithmetische Mittel berechnen lässt.
b) Vertiefung: Arithmetisches Mittel inkrementell berechnen
Zeigen Sie durch Umformung, dass für das arithmetische Mittel von Zahlen
gilt:
c) Vertiefung: Vergleich mit Q-Learning
In vielen wertbasierten Reinforcement-Learning-Verfahren werden alte Wertschätzungen mithilfe einer neuen Beobachtung aktualisiert.
Beim tabellarischen Q-Learning kann die Update-Regel geschrieben werden als
Äquivalent gilt
Auch die Aktualisierung des arithmetischen Mittels lässt sich in einer zu Gleichung (1) ähnlichen Form schreiben:
Vergleichen Sie die Update-Regeln miteinander.
Gehen Sie dabei insbesondere auf folgende Fragen ein:
- Welche Größe entspricht jeweils dem bisherigen Wissen?
- Welche Größe enthält die neue Information?
- Welche Rolle spielt der Gewichtungsfaktor?
- Worin unterscheidet sich der Faktor von einer konstanten Lernrate ?
- Welche zusätzliche Information enthält das Q-Learning-Target