Reinforcement Learning Cliff-Walking: Sarsa, Q-Learning und Dyna-Q Tutorial

Einführung in das Verstärkungslernen am Beispiel Cliff-Walking

Stell dir vor, du steuerst einen Agenten durch ein 12×4-Gitterraster, ähnlich wie bei einem klassischen Spiel. Ziel ist es, vom Start unten links zum Ziel unten rechts zu gelangen, ohne in die Klippe zu fallen. Jeder Schritt kostet -1, ein Sturz in die Klippe -100 und das Erreichen des Ziels beendet die Episode. Dieses Szenario ist perfekt, um die Grundlagen des Reinforcement Learning zu verstehen – ein Bereich, der auch in modernen KI-Anwendungen wie autonomen Fahrzeugen oder Spielen wie AlphaGo eine Rolle spielt.

Grundlagen: Zustände, Aktionen und Belohnungen

Der Zustand st ist eine ganze Zahl, die die Koordinaten (x,y) repräsentiert. Die Aktion at ∈ {0,1,2,3} steht für die vier Himmelsrichtungen. Die Umgebung belohnt den Agenten mit -1 pro Schritt, -100 bei Sturz und 0 bei Zielerreichung. Dieses einfache Modell hilft, die Konzepte von Policy, Value Function und Exploration vs. Exploitation zu erlernen.

Implementierung von Sarsa, Q-Learning und Dyna-Q

In dieser Aufgabe implementierst du drei Algorithmen: Sarsa (On-Policy), Q-Learning (Off-Policy) und Dyna-Q (modellbasiert). Jeder hat seine Stärken und Schwächen. Hier zeige ich dir, wie du die Agenten in Python umsetzt.

1. ε-greedy mit ε-Decay

Die choose_action-Methode wählt mit Wahrscheinlichkeit ε eine zufällige Aktion (Exploration) und sonst die beste Aktion (Exploitation). Der ε-Wert sollte im Laufe des Trainings abnehmen, z.B. von 1.0 auf 0.01. Ein typischer Decay könnte exponentiell sein: ε = max(ε_min, ε * ε_decay).

def choose_action(self, state):
    if np.random.rand() < self.epsilon:
        return np.random.choice(self.n_actions)
    else:
        return np.argmax(self.q_table[state])

2. Sarsa – On-Policy TD-Learning

Sarsa aktualisiert den Q-Wert basierend auf der tatsächlich ausgeführten Aktion. Das macht es vorsichtiger, da es die aktuelle Explorationspolitik berücksichtigt.

def learn(self, state, action, reward, next_state, next_action):
    q_predict = self.q_table[state][action]
    q_target = reward + self.gamma * self.q_table[next_state][next_action]
    self.q_table[state][action] += self.lr * (q_target - q_predict)

3. Q-Learning – Off-Policy TD-Learning

Q-Learning aktualisiert mit dem maximalen Q-Wert des nächsten Zustands, unabhängig von der gewählten Aktion. Das führt oft zu einer schnelleren Konvergenz, aber auch zu riskanterem Verhalten.

def learn(self, state, action, reward, next_state):
    q_predict = self.q_table[state][action]
    q_target = reward + self.gamma * np.max(self.q_table[next_state])
    self.q_table[state][action] += self.lr * (q_target - q_predict)

4. Dyna-Q – Modellbasiertes Lernen

Dyna-Q kombiniert TD-Lernen mit einem internen Modell der Umgebung. Nach jedem echten Schritt führt es mehrere simulierte Schritte durch, um die Daten effizienter zu nutzen. Das beschleunigt das Lernen besonders in frühen Phasen.

def learn(self, state, action, reward, next_state):
    # Q-Learning Update
    q_predict = self.q_table[state][action]
    q_target = reward + self.gamma * np.max(self.q_table[next_state])
    self.q_table[state][action] += self.lr * (q_target - q_predict)
    # Modell speichern
    self.model[(state, action)] = (reward, next_state)
    # Simulierte Erfahrungen
    for _ in range(self.planning_steps):
        s, a = random.choice(list(self.model.keys()))
        r, s_next = self.model[(s, a)]
        q_predict = self.q_table[s][a]
        q_target = r + self.gamma * np.max(self.q_table[s_next])
        self.q_table[s][a] += self.lr * (q_target - q_predict)

Visualisierung und Analyse der Ergebnisse

Nach dem Training solltest du drei Diagramme erstellen: (1) Episodenbelohnung über die Zeit, (2) ε-Wert über die Zeit und (3) den endgültigen Pfad des Agenten. Ein Vergleich der Lernkurven zeigt, dass Dyna-Q oft schneller eine hohe Belohnung erreicht als Sarsa oder Q-Learning, da es die gesammelten Erfahrungen mehrfach nutzt.

Modellbasiert vs. Modellfrei: Effizienzunterschiede

Dyna-Q ist ein modellbasierter Ansatz, der ein internes Modell der Umgebung aufbaut und damit Planungsschritte durchführt. Das führt zu einer höheren Datenausnutzung. Im Gegensatz dazu lernen Sarsa und Q-Learning nur aus echten Interaktionen. In Umgebungen mit vielen Zuständen kann Dyna-Q daher schneller konvergieren. Allerdings ist das Modell nur eine Annäherung und kann bei komplexen Umgebungen ungenau sein.

Deep Reinforcement Learning mit LunarLander

Im zweiten Teil der Aufgabe geht es um die LunarLander-v2-Umgebung. Hier steuerst du eine Mondlandefähre mit acht Zustandsdimensionen und vier diskreten Aktionen. Die Implementierung eines Deep Q-Networks (DQN) ist vorgegeben. Du musst den Code kommentieren und Hyperparameter wie Gamma, Epsilon und dessen Abklingrate tunen.

Hyperparameter-Tuning für DQN

Ein guter Startwert für Gamma ist 0.99, für Epsilon 1.0 mit einem Decay auf 0.01 über 300 Episoden. Du kannst auch die Netzwerkstruktur anpassen, z.B. zwei versteckte Schichten mit 64 und 32 Neuronen. Die Verwendung mehrerer aufeinanderfolgender Frames (z.B. 4) verbessert die Stabilität, da der Agent so Bewegungen besser wahrnimmt.

Alternative Explorationsstrategien: Upper Confidence Bound (UCB)

Neben ε-greedy gibt es Upper Confidence Bound (UCB). Diese Methode wählt Aktionen basierend auf einer Obergrenze des Konfidenzintervalls: a = argmax(Q(s,a) + c * sqrt(log(N(s)) / N(s,a))). Vorteile: systematischere Exploration, keine zufälligen Sprünge. Nachteile: rechenintensiver, benötigt Schätzung der Besuche. UCB eignet sich besonders für Umgebungen mit wenigen Aktionen, wie hier.

Fazit

Das Cliff-Walking-Problem ist ein hervorragendes Beispiel, um die Unterschiede zwischen On-Policy, Off-Policy und modellbasiertem Lernen zu verstehen. Durch die Implementierung von Sarsa, Q-Learning und Dyna-Q erhältst du praktische Einblicke in die Funktionsweise von Reinforcement Learning. Die Erweiterung auf Deep Q-Networks und alternative Explorationsstrategien rundet das Verständnis ab. Viel Erfolg bei deiner Implementierung!