6.1 Reinforcement Learning & Q-Learning

Worum geht’s#

Die Vorlesung ordnet Reinforcement Learning (RL) als „Variante des unüberwachten Lernens” ein: Anders als beim überwachten Lernen gibt es keinen Lehrer, der für jedes Beispiel die richtige Antwort liefert. Stattdessen führt ein Lerner (Agent, Roboter, Bot) Handlungen aus und bekommt von der Umgebung nur positives oder negatives Feedback — die Folien illustrieren das vom Kleinkind am heißen Herd über die Skinner-Box bis zur Tinder-App. Der Lerner muss selbst herausfinden, welche seiner vielen Aktionen die Belohnung verursacht hat: Die „blinde Maus” der Folien erfährt erst am Käse, dass ihr Weg gut war, und erst in der Falle, dass eine frühere Abzweigung schlecht war.

Mich reizt an diesem Kapitel, dass es eine andere Lernform als die bisherigen ist: kein fester Datensatz, sondern ein Lerner, der durch Ausprobieren Daten selbst erzeugt und dabei abwägen muss, ob er einen noch nicht explorierten Zustand erkundet oder einen bewährten erneut aufsucht — der Konflikt aus Exploration und Ausnutzung. Genau dieser Konflikt, und die Art, wie Q-Learning ihn auflöst, ohne ein Modell der Umgebung zu brauchen, macht das Thema zur Brücke zwischen klassischer Suche und dem späteren Deep Reinforcement Learning.

Kernkonzepte#

Das RL-Setting: Zustände, Aktionen, Belohnungen#

Die Folien modellieren die Lernsituation so: Der Lerner befindet sich in einem Zustand $s_i$ in einem diskreten Zustandsraum $S$ und kann dort aus einer Aktionsmenge $A = \{a_{i,1}, \dots, a_{i,n}\}$ eine Aktion wählen. Durch Ausführung gelangt er in den Nachfolgezustand $s_{i+1}$ und erhält dort eine Belohnung (Pluspunkte) oder Bestrafung (Minuspunkte) — je nach Anwendung. Gesucht ist eine Strategie (Policy) $\pi$, also eine Funktion $\pi(s_i) = a_{i,k}$, die in jedem Zustand die Aktion empfiehlt, welche die erwartete Gesamtbelohnung maximiert. Eine solche $\pi$ lässt sich als Lookup-Tabelle realisieren. (Die saubere Einbettung als Markov-Entscheidungsprozess mit Übergangsdynamik $P(s' \mid s, a)$ und Belohnungsfunktion $R(s, a)$, die ich unten zur Bellman-Gleichung brauche, führen die Folien selbst nicht aus — das ergänze ich aus dem Lehrbuch.)

Die Bellman-Gleichung als Optimalitätsprinzip#

Kennt man die optimale $Q^*$, ergibt sich die optimale Strategie geschenkt als $\pi^*(s) = \arg\max_a Q^*(s, a)$ — man schlägt für jeden Zustand einfach die Aktion mit dem höchsten Q-Wert nach, ohne ein Modell der Umgebung. Hinter der Q-Update-Regel der Folien steckt (ohne dass sie explizit genannt wird) die Bellman-Optimalitätsgleichung, die ich aus dem Lehrbuch ergänze:

Sie ist rekursiv: Der Wert eines Zustands-Aktions-Paares ist die sofortige Belohnung plus der diskontierte Wert des besten Folgezuges. Genau diesen „Look-Ahead” auf nachfolgende Belohnungen gewichtet der Diskontfaktor $\gamma \in [0,1]$: $\gamma = 0$ macht den Lerner kurzsichtig (nur lokale Bewertung, keine globale Strategie), nahe 1 weitsichtig. Die Folien empfehlen $\gamma$ meist im Bereich $0{,}8$–$0{,}95$, denn ein zu großes $\gamma$ kann den unmittelbaren Reward einer Aktion zu stark überschatten. Es ist dasselbe Optimalitätsprinzip wie bei der dynamischen Programmierung.

Q-Learning: die Update-Regel#

Die Bellman-Gleichung verlangt $P$ und $R$ — die kennt der Lerner meist nicht. Q-Learning umgeht das durch ein Iterationsverfahren: Es nähert $Q$ an, indem es bei jedem erlebten Übergang $(s, a, r, s')$ den Q-Wert schrittweise in Richtung „direkter Reward + diskontierter bester Folge-Reward” verschiebt. Das ist genau die Q-Update-Regel der Folien:

Zur Lernrate merken die Folien an: ein zu großes $\alpha \approx 1$ nähert $Q$ zu grob an, ein zu kleines $\alpha \to 0$ verlängert das Training unnötig; als Alternative nennen sie ein dynamisches $\alpha = 1 / (1 + \text{Besuche von }(s,a))$.

Damit Q-Learning genug erlebt, braucht es Exploration. Die Folien nennen das ε-soft: In $(1-\varepsilon)$ der Fälle nimmt man die lokal beste Aktion (greedy), in $\varepsilon$ der Fälle überlässt man die Wahl dem Zufall — meist wählt man $\varepsilon$ klein, sodass in 90–95 % greedy zum Einsatz kommt. Das hält die Chance offen, lokale Maxima zu überwinden. Lässt man $\varepsilon$ über die Zeit abklingen, geht der Lerner von Erkunden zu Ausnutzen über. Als Lehrbuch-Gegenstück sei SARSA (on-policy) erwähnt: Es bootstrappt mit der tatsächlich gewählten Folgeaktion $Q(s', a')$ statt mit dem Maximum und lernt so den Wert der explorierenden Strategie statt der optimalen.

Praxis#

Um die Update-Regel nicht nur zu glauben, habe ich das Maus-Käse-Fallen-Beispiel der Folien (Reward Käse $\to +1$, Falle $\to -1$, sonst $0$) von ihrem 1D-Schlauch in eine 5×5-Gitterwelt übersetzt und in reinem NumPy gebaut: Start unten links, Ziel oben rechts ($+1$), eine Falle in der Mitte ($-1$) und ein kleiner Schritt-Malus ($-0{,}04$), der kurze Wege belohnt. Der Agent lernt über 600 Episoden mit $\gamma = 0{,}95$, $\alpha = 0{,}2$ und abklingendem $\varepsilon$ — die Folien sprechen für ihr Strip-Beispiel von „ca. 1000 Q-Table-Updates”. Der Kern ist exakt die Update-Regel von oben:

# off-policy Update: bootstrapped mit dem MAX des Folgezustands
best_next = 0.0 if done else float(np.max(Q[nxt[0], nxt[1]]))
td = rew + gamma * best_next - Q[s[0], s[1], a]
Q[s[0], s[1], a] += alpha * td

Das vollständige Skript (Umgebung, ε-greedy-Schleife, Plots) liegt in python/src/eport_figures/praxis/p_6_1_qlearning.py. Seine Ausgabe:

Gitterwelt 5x5:  Start=(4, 0)  Ziel=(0, 4) (+1)  Falle=(2, 2) (-1)
Hyperparameter:  gamma=0.95  alpha=0.2  eps0=0.6 (abklingend)
Episoden: 600
  mittlerer Ertrag, erste 50 Episoden:  -0.320
  mittlerer Ertrag, letzte 50 Episoden: +0.700
  mittlere Pfadlaenge, letzte 50:       8.5 Schritte

Gelernte Politik (Greedy je Zelle, X=Ziel, #=Falle):
  → → → → X
  → ↑ ↑ ↑ ↑
  ↑ ↑ # ↑ ↑
  ↑ ↑ → ↑ ↑
  ↑ ↑ ← ↑ ↑

Q-Werte ausgewaehlter Zustaende (hoch / rechts / runter / links):
  Zustand (4, 0):  [+0.46 +0.46 +0.39 +0.39]  -> beste Aktion ↑
  Zustand (0, 3):  [+0.91 +1.00 +0.82 +0.82]  -> beste Aktion →
  Zustand (1, 4):  [+0.96 +0.28 +0.14 +0.00]  -> beste Aktion ↑
  Zustand (3, 2):  [-0.83 +0.52 -0.07 -0.06]  -> beste Aktion →

Der mittlere Ertrag steigt von $-0{,}32$ (frühe, zufällige Episoden) auf $+0{,}70$ — der Agent findet zuverlässig den Käse statt der Falle. Aufschlussreich ist der Q-Wert für die Zelle direkt unter der Falle, Zustand $(3,2)$: „hoch” hat den stark negativen Wert $-0{,}83$ (das führte in die Falle), also weicht die gelernte Politik dort nach rechts aus. So sieht man, wie die einzelne $-1$-Bestrafung über den $\gamma$-diskontierten TD-Fehler rückwärts auf die vorausgehenden Zustände durchschlägt.

Querbezüge#

• 1.2 (KI-Agenten): RL ist die formale Ausarbeitung des dort eingeführten lernenden Agenten im Sequenzentscheidungsfall. Die Politik $\pi(s)$ ist genau die Agentenfunktion, nur diesmal aus Belohnung statt aus Designerhand gelernt.
• 2.3 (Spielbäume): Das Bellman-Maximum ist derselbe Gedanke wie der Minimax-Wert — der Wert eines Zustands ergibt sich rekursiv aus dem besten Folgezustand. Die Folien ziehen sogar eine Brücke zur Wegsuche (Dijkstra/A*): Ersetzt man Belohnungsmaximierung durch Kostenminimierung, erhält man eine ähnliche Bellman-artige Backup-Idee wie bei kürzesten Wegen. Das ist eine strukturelle Analogie, keine identische Implementierung von Dijkstra. Auch das Tic-Tac-Toe-Beispiel der Folien nutzt diese Verwandtschaft (Suchbaum per Tiefensuche).
• 7.1 (Neuronale Netze): Sprengt der Zustandsraum jede Tabelle, approximiert man $Q(s,a)$ durch ein neuronales Netz — Deep Q-Learning. Die Folien führen das am Side-Scroller vor (Spielfigur „Chef”, Aktionen Run/Bend/Jump, Zustand $S=(C,G,T)$) und an Mnihs Atari-Netz (Nature 2015), dessen letzte Schicht die Q-Tabelle approximiert. Das hier von Hand gefüllte Q-Gitter wird dann zum Output eines Netzes, und der TD-Fehler wird zur Verlustfunktion.
• Andere Module: Die Bellman-Gleichung ist dynamische Programmierung (Algorithmen & Datenstrukturen) mit dem gleichen Optimalitätsprinzip. Der MDP ist ein gesteuerter Markov-Prozess (Stochastik), und der TD-Fehler ist ein stochastischer Gradientenschritt — dieselbe Idee wie in der Numerik/Optimierung und der Regelungstechnik, wo man Stellgrößen über erwartete Kosten optimiert.

Quellen#

• Foliensätze _510_RL.pdf (Q-Learning-Prinzip) und _520_RL_SideScroller.pdf (Side-Scroller-Beispiel) — Grundlage für die Q-Update-Regel, die V/Q-Unterscheidung („Q = Quality”), die ε-soft-Idee, die $\gamma$- und $\alpha$-Empfehlungen sowie das Maus-Käse-Fallen-Szenario, das ich zur Gitterwelt abstrahiert habe. _510 enthält außerdem die Beispiele Crawling-Robot, Tic-Tac-Toe und Deep-Q (Atari). Die Folien motivieren gut, formulieren die Bellman-Gleichung aber nicht explizit; die habe ich aus dem Lehrbuch ergänzt.
• Watkins & Dayan (1992), Q-learning (Machine Learning) — die Primärquelle des Verfahrens samt Konvergenzbeweis, und Mnih et al. (2015), Human-level control through deep reinforcement learning (Nature) — das Deep-Q-Netz für Atari, das die Folien als Anwendung zeigen.
• Sutton & Barto, Reinforcement Learning: An Introduction (2. Aufl.), Kap. 6 — als Referenz für die saubere Trennung von Q-Learning (off-policy) und SARSA (on-policy) und die Konvergenzbedingungen konsultiert.
• Russell & Norvig, Artificial Intelligence: A Modern Approach, Kap. 22 (Reinforcement Learning) — für die MDP-Einbettung und den Bezug zur dynamischen Programmierung.
• Gymnasium — die Standard-Umgebungsschnittstelle überflogen; ihr FrozenLake-Beispiel ist im Kern meine Gitterwelt und hat das Design von Belohnung und Falle inspiriert.