Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz

Sei (S, A, P, R, γ) ein MDP (Bezeichnungen aus dem letzten Teil), π die Strategie, nach der der Agent handelt, V : S → ℝ die bisherige Schätzung der Wertfunktion V^π und α ∈ (0, 1] die Lernrate. Sei (s, a, r, s′) ∈ S × A × ℝ × S ein tatsächlich erlebter Übergang: Der Agent war im Zustand s, wählte die Aktion a, bekam die Belohnung r = R(s, a, s′) und gelangte nach s′. Wir definieren

1. das TD-Ziel y = r + γ V(s′) (ist s′ ein Endzustand, so ist V(s′) = 0, also y = r);
2. den TD-Fehler δ = y − V(s);
3. den TD-Schritt (Methode TD(0)): Die neue Schätzung V′ : S → ℝ ist V′(s) = V(s) + α δ,   V′(u) = V(u) für alle u ∈ S, u ≠ s.

Statt des Mittels ∑_s′ P(s′ | s, a) […] über alle möglichen Folgezustände (wie in der Bellman-Gleichung) wird also ein einziger erlebter Übergang verwendet; P und R müssen wir nicht kennen. Das Ziel y enthält die eigene Schätzung V(s′) — eine Schätzung wird anhand einer anderen Schätzung korrigiert (Bootstrapping).

Die Schätzung von zu Hause ist V(zu Hause) = 30 Minuten. Nach r = 10 Minuten Fahrt stehst du im Stau, und die Schätzung von dort ist V(Stau) = 35. Zeit wird nicht diskontiert (γ = 1), und statt Belohnungen addieren wir Minuten, also ist das TD-Ziel 10 + 1 · 35 = 45 und der TD-Fehler 45 − 30 = 15 (Farben wie in der Formel oben).

• mit α = 0,5: neue Schätzung 30 + 0,5 · 15 = 37,5 Minuten,
• mit α = 0,1: 30 + 0,1 · 15 = 31,5 Minuten,
• mit α = 1: direkt 45 — die letzte Erfahrung würde alle früheren komplett überschreiben.

Seien α ∈ (0, 1], n ∈ ℕ, n ≥ 1, Q₀ ∈ ℝ und c₁, …, c_n ∈ ℝ (Ziele). Für k = 1, …, n sei

Q_k = Q_k−1 + α (c_k − Q_k−1).

Dann gilt

Q_n = (1 − α)ⁿ Q₀ + ∑_k=1ⁿ α (1 − α)^n−k c_k,

und die Gewichte sind nichtnegativ mit der Summe (1 − α)ⁿ + ∑_k=1ⁿ α (1 − α)^n−k = 1 — Q_n ist ein gewichteter Mittelwert von Q₀ und den Zielen.

Beweis. Die Regel lässt sich als Q_k = (1 − α) Q_k−1 + α c_k umschreiben und wiederholt einsetzen (Induktion nach n). Die Summe der Gewichte folgt aus der Formel für die geometrische Reihe: ∑_k=1ⁿ α (1 − α)^n−k = α · 1 − (1 − α)ⁿ/α = 1 − (1 − α)ⁿ. ∎

Die Gewichte fallen geometrisch: Mit α = 0,5 hat das letzte Ziel das Gewicht 0,5, das vorletzte 0,25, das davor 0,125… Ältere Erfahrungen werden also nach und nach vergessen — das hilft, wenn sich die Ziele ändern (und beim TD-Lernen ändern sie sich, weil sie aus Schätzungen berechnet werden, die selbst gerade gelernt werden), aber in einer zufälligen Welt schwankt die Schätzung. Deshalb verlangt die Theorie für sichere Konvergenz, α allmählich zu verkleinern.

Sei (S, A, P, R, γ) ein MDP, Q : S × A → ℝ eine Tabelle der bisherigen Schätzungen der Aktionswerte (am Anfang etwa überall 0), α ∈ (0, 1] die Lernrate und (s, a, r, s′) ein erlebter Übergang wie in der Definition von TD. Für einen Endzustand s′ setzen wir Q(s′, a′) = 0 für alle a′ ∈ A.

1. Q-Learning (Christopher Watkins, 1989) ändert nach jedem Übergang ein einziges Feld der Tabelle: Q(s, a) ← Q(s, a) + α [r + γ · max_{a′ ∈ A} Q(s′, a′) − Q(s, a)]; die übrigen Felder Q(u, b), (u, b) ≠ (s, a), bleiben unverändert.
2. SARSA braucht zusätzlich die Aktion a′ ∈ A, die der Agent in s′ nach seiner Strategie wirklich wählt (daher der Name: s, a, r, s′, a′), und ersetzt das Maximum durch ihren Wert: Q(s, a) ← Q(s, a) + α [r + γ · Q(s′, a′) − Q(s, a)].

Q-Learning lernt also den Wert des besten Verhaltens Q*, SARSA den Wert Q^π dessen, wie sich der Agent tatsächlich verhält, samt Ausprobieren. Für Q-Learning gilt (Watkins und Dayan, 1992): Ist γ < 1, sind die Belohnungen beschränkt, wird jedes Paar (s, a) unendlich oft korrigiert und erfüllen die Lernraten α_k(s, a) bei der k-ten Korrektur des Feldes (s, a) ∑_k α_k = ∞ und ∑_k α_k² < ∞, dann konvergiert Q mit Wahrscheinlichkeit 1 gegen Q*.

Der Agent probiert gleich am Start einen Schritt nach rechts und stürzt: r = −100, s′ = Start, wo bisher alle Werte 0 sind. Der neue Wert ist Q(Start, →) = 0 + 0,5 · (−100 + 1 · 0 − 0) = −50 (Farben wie in der Formel oben).

Dann probiert er einen Schritt nach oben: r = −1, das neue Feld hat lauter Nullen, Q(Start, ↑) = 0 + 0,5 · (−1 + 1 · 0 − 0) = −0,5.

Stürzt er am Start ein zweites Mal, ist der größte Wert am Start immer noch 0 (die Aktionen ↓ und ← hat er noch nicht probiert), also Q(Start, →) = −50 + 0,5 · (−100 + 1 · 0 − (−50)) = −75. Mit jedem weiteren Sturz nähert er sich −100 und mehr.

Beachte die Nebenwirkung: Alle echten Belohnungen sind negativ, also sehen unprobierte Aktionen mit null besser aus als probierte. Eine Tabelle, die bei Nullen beginnt, treibt den Agenten hier von selbst dazu, Neues auszuprobieren (sogenannter Optimismus gegenüber dem Unbekannten) — schon bei der gierigen Wahl, bevor der Zufall ε an die Reihe kommt.

Sei S eine Menge von Zuständen, A eine endliche nichtleere Menge von Aktionen, Q : S × A → ℝ und ε ∈ [0, 1]. Für jedes s ∈ S sei a*(s) ∈ argmax_{a ∈ A} Q(s, a) die gierige Aktion (bei mehreren Maxima eines davon). Die ε-gierige Strategie bezüglich Q ist die stochastische Strategie

π(a | s) = 1 − ε + ε/|A|   für a = a*(s),    π(a | s) = ε/|A|   für a ≠ a*(s).

Äquivalent: Wähle mit Wahrscheinlichkeit 1 − ε die Aktion a*(s), mit Wahrscheinlichkeit ε eine gleichverteilt zufällige Aktion aus ganz A (auch die gierige). Für ε = 0 ist es die gierige Strategie. Ohne zufällige Aktionen würde der Agent nie etwas ausprobieren, das ihm bisher nicht als das Beste erscheint, und er könnte am ersten ordentlichen Weg hängen bleiben, den er findet. Es ist die einfachste Lösung des Dilemmas Erkunden oder Ausnutzen (exploration vs. exploitation).

Die zufällige Aktion wird aus allen |A| = 4 Aktionen gewählt, also auch aus der besten. Deshalb

π(a | s) = 1 − ε + ε/|A| = 1 − 0,1 + 0,1/4 = 0,925 für die beste Aktion und ε/|A| = 0,1/4 = 0,025 für jede der drei anderen.

Jede bestimmte „schlechte“ Aktion — etwa ein Schritt nach unten in die Klippe — kommt also in einem von 40 Schritten vor.

Der gelernte Weg von Q-Learning führt vom Start nach oben und dann zehn Felder direkt über der Klippe entlang. Am Start und auf jedem dieser zehn Felder führt ein Schritt nach unten in die Klippe (am Start ein Schritt nach rechts), also eine bestimmte Aktion — bei ε = 0,1 mit Wahrscheinlichkeit 0,025. 11 solche Felder ohne Sturz durchqueren:

0,975¹¹ = 0,757, ein Sturz während eines Durchgangs hat also die Wahrscheinlichkeit q = 1 − 0,757 = 0,243.

Nach einem Sturz beginnt der Agent wieder am Start, die Zahl der Stürze bis zu einem erfolgreichen Durchgang ist also geometrisch verteilt mit dem Erwartungswert q/1 − q = 0,243/0,757 = 0,32 Stürze pro Episode. Gemessen: 0,34 — etwas mehr, weil die Abschätzung zufällige Schritte nach links vernachlässigt, nach denen der Agent noch weitere Schritte über der Klippe verbringt. SARSA geht am oberen Rand, drei Reihen über der Klippe: Dort brächten sie erst mehrere zufällige Schritte nach unten hintereinander in die Klippe. Ein Risiko geht es vor allem am Start ein, und das allein ergibt 0,025/0,975 = 0,026 Stürze pro Episode; gemessen: 0,04.

Eine Lernmethode schätze die Wertfunktion V^π oder Q^π einer Strategie π (Zielstrategie) aus Übergängen, die entstehen, wenn der Agent nach der Strategie b handelt (Verhaltensstrategie).

1. Die Methode ist on-policy genau dann, wenn Ziel- und Verhaltensstrategie identisch sind, π = b. Beispiel: SARSA mit ε-gieriger Strategie — es schätzt Q^π genau der ε-gierigen Strategie, nach der es handelt.
2. Die Methode ist off-policy genau dann, wenn sie π ≠ b zulässt. Beispiel: Q-Learning — es handelt ε-gierig, schätzt aber dank des Maximums im Ziel Q* der gierigen (optimalen) Strategie.

Off-policy-Methoden können deshalb auch aus Erfahrungen lernen, die früher (mit einer anderen, älteren Strategie) oder von jemand anderem gesammelt wurden.

Gegeben sei ein MDP mit einer endlichen Menge von Aktionen A und mit durch Vektoren beschriebenen Zuständen, S ⊆ ℝ^d (die Zustandsmenge muss hier nicht endlich sein; Summen über s′ in den Definitionen des letzten Teils werden dann durch Erwartungswerte ersetzt). Sei Q(·, ·; θ) : S × A → ℝ ein neuronales Netz mit Parametern θ ∈ ℝ^m, das für einen Zustand s den Vektor (Q(s, a; θ))_{a ∈ A} ∈ ℝ^|A| zurückgibt. DQN (Volodymyr Mnih u. a., DeepMind, 2015) hat zusätzlich

1. einen Erfahrungsspeicher (replay buffer) D — eine endliche Liste von höchstens N letzten Übergängen (s, a, r, s′, k), wobei k ∈ {0, 1} angibt, ob s′ ein Endzustand ist;
2. ein Zielnetz — Parameter θ⁻ ∈ ℝ^m, die nur einmal alle C Schritte aus θ kopiert werden (θ⁻ ← θ).

Für einen Übergang aus D ist das Ziel y = r + (1 − k) γ max_{a′ ∈ A} Q(s′, a′; θ⁻), und DQN minimiert bezüglich θ (bei festem θ⁻) den Verlust

L(θ) = E_{(s, a, r, s′, k) ~ D} [(y − Q(s, a; θ))²],

wobei ~ D eine gleichverteilt zufällige Auswahl eines Übergangs aus dem Speicher bedeutet; in der Praxis wird der Erwartungswert durch den Mittelwert über einen zufälligen Stapel von Übergängen geschätzt. Der Agent handelt also in jedem Schritt (ε-gierig bezüglich Q(·, ·; θ)), speichert den Übergang in D, macht einen Gradientenschritt auf L und erneuert alle C Schritte θ⁻. Der Erfahrungsspeicher sorgt dafür, dass das Netz aus zufälligen Stapeln lernt, nicht aus den letzten Schritten hintereinander; das Zielnetz dafür, dass sich das Ziel nicht mit jedem Lernschritt verschiebt.

Der Huber-Verlust (mit Schwelle 1) ist die Funktion H : ℝ → ℝ,

H(d) = d²/2   für |d| ≤ 1,    H(d) = |d| − 1/2   für |d| > 1.

Sie ist stetig differenzierbar mit der Ableitung H′(d) = d für |d| ≤ 1 und H′(d) = sgn d = ±1 für |d| > 1. Unser DQN setzt d = Q(s, a; θ) − y ein und minimiert statt des Quadrats des Fehlers E[H(d)] (wie der ursprüngliche Artikel, der den Fehler auf ±1 beschneidet): Kleine Fehler werden wie beim Quadrat korrigiert, ein großer Fehler (etwa wenn das Ziel nach dem Kopieren des Zielnetzes springt) gibt höchstens einen Gradienten der Größe eins, und ein einzelner seltsamer Übergang bringt das Netz nicht durcheinander.

Die Erkundung fällt linear: ε₀ = 1 (nur zufällige Aktionen), bei Schritt 5 000 ist ε = 1 − 0,95 · 0,5 = 0,525, und ab Schritt 10 000 bleibt es bei 0,05.

Wie große Werte muss das Netz lernen? Stünde der Stab ewig, wäre der Wert 1 + 0,99 + 0,99² + … = 1/1 − 0,99 = 100; für eine auf 500 Schritte begrenzte Episode ist es 1 − 0,99⁵⁰⁰/1 − 0,99 = 99,3. Am Anfang gibt das Netz Zahlen nahe null zurück, die Ziele müssen während des Lernens also um zwei Größenordnungen wachsen — und verschieben sich dabei ständig mit.

So bezeichnen Sutton und Barto die Situation, in der eine Methode zum Lernen von Werten gleichzeitig alle drei Eigenschaften hat:

1. Funktionsapproximation: Die Schätzung ist keine Tabelle, sondern eine Funktion mit Parametern θ ∈ ℝ^m (etwa ein Netz), und es gibt weniger Parameter als Zustände, sodass eine Änderung von θ wegen eines Zustands auch die Schätzungen in anderen Zuständen ändert;
2. Bootstrapping: Das Ziel enthält die eigene Schätzung, z. B. y = r + γ max_a′ Q(s′, a′; θ);
3. Off-policy-Lernen: Die Übergänge, aus denen gelernt wird, stammen von einer anderen Strategie als der Zielstrategie (siehe die Definition oben).

Fehlt irgendeine der drei Eigenschaften, lässt sich die Instabilität vermeiden; sind alle drei vorhanden, gibt es keine allgemeine Konvergenzgarantie, und die Schätzungen können schwingen oder ins Unendliche divergieren (bekannt ist Bairds Gegenbeispiel). DQN enthält alle drei — Erfahrungsspeicher und Zielnetz mildern die Gefahr nur.

Zwei Aktionen haben den wahren Wert 0, aber die Schätzung jeder von ihnen ist mit einem unabhängigen Fehler +1 oder −1 behaftet (beides mit Wahrscheinlichkeit 1/2). Vier gleich wahrscheinliche Fälle ergeben als Maximum der Schätzungen 1, 1, 1 und −1, also

E[max(Q̂₁, Q̂₂)] = 1 + 1 + 1 − 1/4 = 0,5 > 0 = max(Q₁, Q₂).

Das Maximum über verrauschte Schätzungen ist im Mittel größer als das Maximum der wahren Werte, und weil das Ziel mit dem Maximum immer wieder eingesetzt wird, breitet sich die Überschätzung aus. Wählt eine Schätzung die Aktion und bewertet sie eine zweite, unabhängige, ist der Erwartungswert der Bewertung 0 — der Fehler der zweiten Schätzung hat mit der Wahl nichts mehr zu tun.