Q-Learning verständlich erklärt

Ein Roboter soll durch eine Lagerhalle zur Packstation fahren. Er kennt weder den Plan der Halle noch den glatten Boden. Er lernt allein dadurch, dass er es immer wieder versucht. Diese Seite zeigt, wie das gelingt und wo es hängen bleibt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Roboter ohne Lageplan

Ein Roboter soll in einer Lagerhalle von der linken unteren Ecke zur Packstation in der rechten unteren Ecke fahren. Die Halle ist in Felder aufgeteilt, pro Schritt fährt er ein Feld nach Norden, Süden, Osten oder Westen. Gegen eine Wand fahrend bleibt er stehen.

Zwischen Start und Packstation liegt am unteren Rand eine Reihe von Feldern, die zu einer Kante gehören, der Klippe. Der Roboter muss also oberhalb daran vorbei. Fährt er hinein, stürzt er ab, verliert viele Punkte und steht wieder am Start. Der Boden ist glatt: Manchmal rutscht der Roboter zur Seite, statt in die gewählte Richtung zu fahren.

Jeder Schritt kostet einen kleinen Punktabzug, die Packstation bringt einen Bonus. Das Besondere: Er kennt weder den Plan der Halle noch die Rutschgefahr. Er sieht nur, wo er nach einem Schritt steht und wie viele Punkte er bekam. Eine Fahrt vom Start bis zur Packstation heißt Versuch (Fachwort: Episode).

Das Notizbuch des Roboters

Vergleichen Sie das mit einem Umzug in eine fremde Stadt ohne Stadtplan. An jeder Kreuzung merken Sie sich für jede Richtung eine Note, wie gut es von dort aus weiterging.

Der Roboter führt so ein Notizbuch. Für jedes Feld und jede Richtung steht dort eine Note (Fachwort: Q-Wert). Anfangs ist jede Note null. Nach jedem Schritt ändert er genau eine Note, die für Feld und Richtung dieses Schrittes.

Die neue Note ist ein Mittelwert aus der alten Note und der neuen Erfahrung. Diese Erfahrung hat zwei Teile: die Punkte des Schrittes und die beste Note, die im Notizbuch für das neue Feld steht. Der zweite Teil ist der Kniff. Die Note sagt dadurch nicht nur, was ein Schritt kostet, sondern auch, wie gut es danach weitergehen dürfte. Ein Beispiel: Eine Richtung war bisher mäßig bewertet, führt diesmal aber auf ein Feld mit guter Note. Dann steigt ihre Note ein Stück, aber nicht ganz auf den neuen Wert.

So wandert gute Nachricht rückwärts. Beim Feld neben der Packstation wird die Note gut, weil der Bonus gleich folgt. Das Feld davor leiht sich seine Note von diesem Nachbarn, und so weiter, wie ein Gerücht von Mund zu Mund.

Wie weit eine Note auf die neue Erfahrung zuwandert, bestimmt die Lernrate. Auf glattem Boden ist jede einzelne Erfahrung auch Zufall, derselbe Schritt kann einmal gut und einmal schlecht ausgehen.

Ausprobieren oder bei der besten Note bleiben

Wählt der Roboter stets die Richtung mit der besten Note, probiert er nichts Neues. Dann bleibt er bei der ersten ordentlichen Route, auch wenn es eine bessere gäbe. Deshalb biegt er manchmal zufällig ab. Wie oft das geschieht, ist der Zufallsanteil (Fachwort: Epsilon).

Zu Beginn fährt er fast nur nach Zufall, denn er weiß nichts, da kostet Zufall wenig. Später soll er nutzen, was er weiß. Der Zufallsanteil sinkt in der Demo mit jedem Versuch, wird aber nie ganz null.

Ungewöhnlich ist ein Punkt. Nehmen wir an, der Roboter biegt aus Zufall falsch ab. Die Note für diesen Schritt fragt trotzdem nur: Wie gut wäre es, vom neuen Feld aus richtig weiterzufahren? Ob er das tatsächlich tut, spielt für die Note keine Rolle. Gesucht wird so die beste Route, nicht die Übungsroute. Ob er sie findet, zeigen die Messungen unten.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Die Demo baut die Halle am Rechner nach, ein vereinfachtes Rechenbild (Fachwort: Modell), und lässt den Roboter viele Versuche fahren. Alle Versuche hintereinander heißen ein Lauf. Die Demo wiederholt Läufe mit jeweils anderem Zufall und zählt aus. Zur Kontrolle rechnet sie außerdem aus, welche Route die beste wäre, wenn man den Plan und die Rutschgefahr kennt. Der Roboter bekommt dieses Wissen nie. Erst am Ende vergleicht die Demo die Punkte seiner Route mit denen der besten.

Was die Demo zeigt

Im Beispiellauf, den die Demo zuerst zeigt, kennt der Roboter am Ende fast überall die beste Richtung. Nur am Start nicht. Dort hat er zwei Möglichkeiten:

• Nach oben fahren: richtig, aber ein Rutscher kann ihn dabei in die Klippe lenken, und ein Absturz zieht die Note stark nach unten.
• Gegen die Westwand fahren: sicher, denn er bleibt stehen, bis ein Rutscher ihn nach oben schiebt. Das kostet Zeit.

Im Rechenbild der Demo sehen beide fast gleich gut aus. Im Beispiellauf bekam die Wand die bessere Note, vermutlich durch Zufälle der Erfahrung. Nennen wir das die Wand-Gewohnheit.

Drei weitere Befunde mit Grund:

• Preis: Wer den Plan kennt, kann die beste Route am Schreibtisch ausrechnen. Der Roboter muss jeden Schritt wirklich fahren, im Beispiellauf ein Vielfaches an Schritten gegenüber den Rechenschritten am Schreibtisch. Die Rutscher machen es vermutlich noch mühsamer (nicht gemessen).
• Mehr Versuche: Mit mehr Versuchen wurde die Route nicht verlässlich besser. Der Anteil der Läufe, die fast die beste Route erreichten, schwankte zwischen 40 % und 85 %. Die Wand-Gewohnheit sieht fast so gut aus wie der richtige Schritt, und mit der Zeit probiert der Roboter seltener etwas anderes. Die Läufe sind wenige, kleine Unterschiede sind Zufall.
• Lernrate: Bei der kleinsten getesteten Lernrate endeten 65 % der Läufe fast optimal, bei der größten nur 15 %. Bei der größten zählt die letzte Erfahrung so viel wie die ganze bisherige Note, die Note schwankt also stärker. Ein Lauf von zwanzig endete sogar so, dass der Roboter nie vom Start losfuhr; das kam auch bei einer mittleren Lernrate einmal vor.

Häufige Missverständnisse

• „Wer beim Üben danebengreift, lernt Falsches.“ Nicht nach dieser Rechenregel. Sie bewertet einen Schritt mit der besten Folge, nicht mit dem, was der Roboter danach tut.
• „Dauerhaft viel Zufall beim Üben bringt am meisten.“ Nein. Blieb das Verhalten dauerhaft rein zufällig, erreichten nur 30 % der Läufe eine fast beste Route, bei sinkendem Zufallsanteil in der besten getesteten Einstellung 60 %. Er fuhr dabei ein Mehrfaches an Schritten, vermutlich weit verstreut. Nur am Anfang, wenn er nichts weiß, ist viel Zufall sinnvoll.

Woran Sie das im Alltag erkennen

Anzeichen, dass Sie selbst so lernen:

• Sie haben eine Gewohnheit, die sich seit Langem bewährt, und prüfen nicht mehr, ob eine andere Wahl besser wäre.
• Ein einziges Erlebnis ändert Ihr Urteil über eine Möglichkeit, etwa ein Lokal oder einen Weg, sofort und stark.

Wie ernst ist das Rechenbild zu nehmen?

Die Halle ist klein, der Boden rutscht überall gleich, und jede Aussage stützt sich auf wenige Läufe je Einstellung. Alles hier beschreibt dieses Rechenbild. Wie das Verfahren in anderen Hallen oder in der Wirklichkeit abschneidet, zeigt die Demo nicht.

Was Sie mitnehmen:

• Fragen Sie bei einer Gewohnheit, wann Sie zuletzt ernsthaft eine Alternative probiert haben.
• Prüfen Sie, wie stark ein einzelnes Erlebnis Ihr Urteil bewegen darf, besonders dort, wo ein Fehler teuer ist.
• Wenn zwei Wege fast gleich gut aussehen, prüfen Sie beide mehrfach, bevor Sie sich festlegen.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Methodik der Demo zusammen; die Formeln stehen auch im Expander „📐 Mathematische Formulierung“ der Demo.

• Umgebung: ein Raster (Standardfall 4×8) mit Start unten links, Ziel unten rechts und einer Klippe in der untersten Zeile dazwischen. Aktionen sind Norden, Süden, Osten und Westen. Mit der Rutsch-Wahrscheinlichkeit \(p\) (Standardfall 0,10) weicht die Bewegung zu gleichen Teilen auf eine der beiden Querrichtungen aus. Eine Wand lässt den Agenten stehen. Belohnungen (feste Werte im Code): \(-1\) je Schritt, \(+10\) beim Erreichen des Ziels, das die Episode beendet, und \(-100\) beim Sturz in die Klippe, der den Agenten an den Start zurücksetzt; die Episode läuft weiter. \(\gamma\) ist der Diskontfaktor (Voreinstellung \(\gamma = 1 - 1/20\)). Alle Zahlen dieses Absatzes stehen im Quelltext der Demo.
• Beobachtung: Der Agent sieht nur einzelne Übergänge \((s, a, r, s')\) (Zustand, Aktion, Belohnung, Folgezustand), nie die Übergangswahrscheinlichkeiten oder erwarteten Belohnungen. Das Modell existiert im Code nur für die Referenzlösung.
• Lernen: eine Tabelle \(Q(s,a)\), anfangs überall null. Weil alle Belohnungen außer dem Ziel negativ sind, ist \(Q^*\) für die meisten Paare negativ (nur Paare mit direktem Weg ins Ziel haben ein positives \(Q^*\)); für sie liegt null über dem wahren Wert und wirkt wie eine optimistische Anfangsschätzung (Standardwissen, hier nicht gemessen). Das Verhalten ist epsilon-gierig, das Lernziel immer die gierige Aktion (Off-Policy). Die Lernrate \(\alpha\) ist konstant.
• Wertbegriffe: \(Q^*(s,a)\) ist der erwartete, mit \(\gamma\) abgezinste Gesamtertrag, wenn man in \(s\) die Aktion \(a\) wählt und danach optimal weiterspielt; \(V^*(s) = \max_a Q^*(s,a)\). \(V_\pi(s)\) ist der erwartete abgezinste Ertrag, wenn man von \(s\) an immer der Policy \(\pi\) folgt.
• Referenz: Value Iteration auf dem bekannten Modell liefert \(V^*\). Ein Bellman-Backup ist die Neuberechnung des Wertes eines Zustands aus den Werten seiner Folgezustände; ein Durchlauf über alle Zustände heißt Sweep, die Zahl der Backups ist Sweeps mal Zustände und dient zur Gegenprobe des Aufwands. Die gelernte Policy \(\pi\) (die Zuordnung von Zustand zu Aktion, gierig bezüglich der Tabelle) wird exakt unter dem bekannten Modell ausgewertet (Policy Evaluation), das ergibt \(V_\pi\).
• Maßstab: der Wert-Abstand \(V^*(\text{Start}) - V_\pi(\text{Start})\), nicht die Übereinstimmung der Aktionen in jeder Zelle, denn für nie besuchte Zellen ist sie ohne Belang. „Nahezu optimal“ heißt in der Demo ein Abstand unter einer halben Einheit, „katastrophal“ ein Abstand von der Größenordnung der Klippenstrafe (Schwelle im Code: 50). Die Umgebungsschritte sind die Summe der Episodenlängen; eine Episode hat im Code eine Höchstlänge.
• Experimente: Q-Learning ist stochastisch; Mehr-Läufe-Aussagen stützen sich deshalb auf 20 Zufalls-Seeds je Stufe. Ein Einzellauf ist bei festem Seed festgelegt.

Die Formeln

Nach jedem Schritt wird genau ein Tabelleneintrag verschoben, in Richtung eines beobachteten Ziels aus Belohnung und bester Folgeschätzung. Der Klammerausdruck heißt TD-Fehler (Temporal Difference):

\[Q(s,a) \leftarrow Q(s,a) + \alpha\big(r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big)\]

Beim Erreichen des Ziels entfällt der Folgeterm, weil danach nichts mehr kommt:

\[Q(s,a) \leftarrow Q(s,a) + \alpha(r - Q(s,a))\]

Das Verhalten ist epsilon-gierig: Mit Wahrscheinlichkeit \(\varepsilon\) wird zufällig gewählt, sonst die Aktion mit dem größten Tabellenwert. Der Zufallsanteil in Episode \(e\) (von 0 an gezählt) folgt einem Schema nach dem Vorbild von GLIE (greedy in the limit with infinite exploration), solange der Zerfall positiv ist; \(\varepsilon_0\) ist der Start-Wert, \(\varepsilon_{\min}\) eine kleine Untergrenze über null. Streng GLIE wäre es ohne die Untergrenze; mit ihr bleibt ein kleiner Rest Zufall:

\[\varepsilon_e = \max(\varepsilon_{\min}, \varepsilon_0 / (1 + \text{decay} \cdot e))\]

Bei Zerfall null bleibt \(\varepsilon\) konstant gleich \(\varepsilon_0\). Die Konvergenzaussage von Watkins und Dayan (1992) lautet: Unter Standardbedingungen an die Lernrate und bei unendlich vielen Besuchen jedes Paares aus Zustand und Aktion gilt \(Q \to Q^*\) mit Wahrscheinlichkeit 1. Die Demo trainiert nur endlich lang, daher die gemessene Lücke zu \(V^*\).

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo. Wo die Demo dieselbe Aussage misst, steht es dabei.

Das Update als Schritt auf eine Stichprobe der Bellman-Gleichung.

• Schritt 1: Die optimale Aktionswertfunktion erfüllt \(Q^*(s,a) = \mathbb{E}\big[r + \gamma \max_{a'} Q^*(s',a')\big]\), der Erwartungswert über die Übergänge von \((s,a)\).
• Schritt 2: Ein beobachteter Übergang liefert eine Stichprobe \(y = r + \gamma \max_{a'} Q(s',a')\) dieses Erwartungswertes, mit der aktuellen Tabelle statt \(Q^*\).
• Schritt 3: Das Update lässt sich schreiben als \(Q \leftarrow (1-\alpha)\,Q + \alpha\,y\). Bei konstantem \(\alpha\) ist der Eintrag ein exponentiell gewichteter Mittelwert; eine Stichprobe, die \(k\) Updates zurückliegt, trägt mit dem Gewicht \(\alpha(1-\alpha)^k\) bei.
• Schritt 4: Weil \(y\) den Eintrag des Folgezustandes enthält, wandert Information rückwärts. Verankert wird sie nur beim Ziel, wo \(y = r\) gilt. Laufen die Updates in Wegreihenfolge, erreicht eine neue Information je Episode im Allgemeinen nur einen Schritt weiter zurück; das ist ein Grund für die vielen nötigen Episoden.

Off-Policy. In \(y\) steht das Maximum über \(a'\), nicht die Aktion, die der Agent im Folgeschritt wirklich wählt. Das Verhalten (epsilon-gierig) bestimmt deshalb nur, welche Paare \((s,a)\) wie oft aktualisiert werden, nicht das Ziel der Updates. Die Konvergenzaussage verlangt, dass jedes Paar unendlich oft besucht wird, aber nicht, dass das Verhalten gierig wird; eine Untergrenze über null stützt die erste Bedingung. Dass auch rein zufälliges Verhalten eine gute Policy liefern kann, zeigt die Messung unten (ein Teil der Läufe ohne Zerfall).

Konstante Lernrate und Rauschen.

• Schritt 1: Die üblichen Konvergenzbedingungen der stochastischen Approximation verlangen eine abnehmende Lernrate (Summe der Lernraten unendlich, Summe ihrer Quadrate endlich; aus dem Gedächtnis, nicht geprüft). Die Demo nutzt ein festes \(\alpha\); die Aussage greift hier also selbst bei unendlichem Training nicht im strengen Sinn.
• Schritt 2: Für unabhängige, gleich verteilte Stichproben \(y\) mit Varianz \(\sigma^2\) hat der exponentiell gewichtete Mittelwert die Varianz \(\alpha\,\sigma^2/(2-\alpha)\). Das ist eine Näherung, denn die Stichproben hängen hier von der sich ändernden Tabelle ab.
• Schritt 3: Diese Streuung wächst mit \(\alpha\). Ein einzelner Absturz in die Klippe verschiebt den Eintrag um den Bruchteil \(\alpha\) der Strafe nach unten. Das passt zum zu tiefen Eintrag für Norden am Start im Standardlauf. Ob bei großem \(\alpha\) stattdessen zu hohe Einträge den Ausschlag geben, misst die Demo nicht; die Herleitung beweist beides nicht.

Warum der Beinah-Gleichstand am Start hängen bleibt.

• Schritt 1: Am Startfeld grenzt im Westen und Süden eine Wand, im Osten die Klippe, im Norden das freie Feld. Die Aktion Westen lässt den Agenten mit Wahrscheinlichkeit \(1 - p/2\) stehen, mit Wahrscheinlichkeit \(p/2\) rutscht er nach Norden.
• Schritt 2: Die Aktion Norden führt mit Wahrscheinlichkeit \(p/2\) in die Klippe, mit großer Strafe und Rückkehr zum Start.
• Schritt 3: Wiederholtes Westen ist also ein Warten, bis ein Rutscher den Agenten nach oben schiebt. Die Wartezeit ist geometrisch verteilt mit Mittel \(2/p\) Schritten. Wegen der Abzinsung zählt jeder spätere Wartschritt weniger: Das reine Warten kostet \(-1/\big(1-\gamma(1-p/2)\big)\), nicht \(-2/p\).
• Schritt 4: In der exakten Lösung (Value Iteration) liegen die Werte der Aktionen Norden und Westen am Start dicht beieinander, Norden ist besser, der Unterschied beträgt weniger als eine halbe Einheit. Der Wert von Westen unterstellt aber nur einen vertanen Schritt, dann optimales Weiterspielen. Die gelernte Policy wählt dagegen jedes Mal wieder Westen und bezahlt das Warten wiederholt. Darum ist der Wert-Abstand der Policy (im Standardfall 2,40) größer als der Abstand der beiden Aktionswerte.
• Probe: Wartet die Policy am Start und geht nach dem Rutscher nach oben, gilt \(V_\pi(\text{Start}) = \big(-1 + \gamma\,(p/2)\,V_\pi(\text{Nord})\big)\big/\big(1 - \gamma(1-p/2)\big)\), mit dem Wert \(V_\pi(\text{Nord})\) des Feldes nördlich vom Start. Dort stimmt die gelernte Policy mit der optimalen überein, also gilt \(V_\pi(\text{Nord}) = V^*(\text{Nord})\). Dieser Wert ist nach der Rechnung dieser Seite mit dem Code der Demo betragsmäßig viel kleiner als der Wert am Start: Vom Feld Nord führt der Weg ohne Klippengefahr über die Reihe darüber zum Ziel, während die Aktion Norden am Start mit Wahrscheinlichkeit \(p/2\) in die Klippe führt, im Mittel etwa fünf Punkte Strafe zusätzlich. Setzt man den Wert von Nord ein, ergibt die Formel den Wert der Tabelle unten (−11,62). Das Warten kostet also nach der Abzinsung nur etwa den zehnfachen Schrittpreis, nicht den zwanzigfachen.

Nachrechnung dieser Seite mit dem Code der Demo (keine Messung der Demo): Im Standardlauf lag die gelernte Schätzung für Norden am Start um mehrere Einheiten unter ihrem exakten Wert, die für Westen nahe an dem ihren. Eine Deutung, nicht gemessen: Das ist die Art Fehler, die ein seltener großer Absturz bei konstantem \(\alpha\) erzeugen kann.

Der Zufallsanteil im Lauf der Zeit. Mit \(\varepsilon_0 = 1\) und dem Standard-Zerfall lag \(\varepsilon\) am Ende des Standardlaufs (1500 Episoden) nach der Formel bei gut einem Zehntel, am Ende des längsten Laufs (4000 Episoden) bei knapp einem Zwanzigstel. Die Untergrenze greift bei diesem Start-Wert in keinem einstellbaren Lauf. Der Zufallsanteil ist am Ende also klein, aber nicht vernachlässigbar. Dass bei langem Training kaum noch erkundet werde, stützt die Rechnung deshalb nicht als Erklärung dafür, dass mehr Training nicht verlässlich hilft.

Befunde

Alle Zahlen der Tabelle sind Messwerte der Demo. Der Standardfall ist ein Einzellauf mit festem Seed. Die übrigen Zeilen sind Anteile über 20 Seeds je Stufe, jeder Lauf zählt also fünf Prozentpunkte. Die Tests der Demo prüfen sie mit großzügigen Bändern, weil Q-Learning stochastisch ist. Eine Neuberechnung dieser Seite mit dem Code der Demo ergab dieselben Anteile.

Frage	Befund
Standardfall (4×8, Rutschen 0,10, α = 0,10, Zerfall 0,005, 1500 Episoden, Seed 0)	V*(Start) = −9,23, gelernte Policy −11,62, Abstand 2,40. 96,0 % der erreichbaren Zellen (24 von 25, ohne Klippe und Ziel) stimmen mit der optimalen Policy überein, nur der Start nicht. 52.917 Umgebungsschritte gegenüber 1.408 Bellman-Backups von Value Iteration auf demselben Modell (38×).
Löst mehr Training das zuverlässig? (100 bis 4000 Episoden, 20 Seeds je Stufe)	Nein. Der Anteil nahezu optimaler Läufe steigt nicht mit dem Training, er schwankt zwischen 40 % und 85 %: 50 % bei 100, 85 % bei 300, 40 % bei 1500, 55 % bei 4000 Episoden. Bei 4000 Episoden braucht Q-Learning im Mittel 107.147 Umgebungsschritte, das 76-fache der 1.408 Backups.
Wie wichtig ist der Zerfall des Zufallsanteils? (Zerfall 0 bis 0,02, 800 Episoden, 20 Seeds je Stufe)	Ohne Zerfall (der Zufallsanteil bleibt bei 1,0, das Verhalten ist rein zufällig) erreichen 30 % der Läufe eine nahezu optimale Policy, bei Zerfall 0,005 sind es 60 %. Ohne Zerfall werden im Mittel 7,6-mal so viele Umgebungsschritte verbraucht wie bei 0,005.
Wie stark wirkt die Lernrate? (α = 0,05 bis 0,50, 800 Episoden, 20 Seeds je Stufe)	α = 0,05: 65 % nahezu optimal. α = 0,50: 15 % nahezu optimal; in einem weiteren Lauf von 20 (5 %) war das Ergebnis katastrophal, mit einem Abstand über 100 gegenüber dem Optimum. Bei der größten Lernrate reichte dieselbe Episodenzahl also seltener zum Optimum, die Zwischenstufen liegen laut Neuberechnung dieser Seite dazwischen.
Stimmt der Kern?	72 Tests prüfen das Raster, die Referenzlösung, den Agenten (Update von Hand, Zufallsanteil-Schema, eine unabhängige Nachrechnung einer Episode und ein Kürzungstest: ein Zwischenstand nach \(k\) Episoden gleicht einem eigenen Lauf mit nur \(k\) Episoden), die Auswertung, die Oberfläche und die wichtigsten Zahlen dieser Tabelle (mit großzügigen Bändern; nicht jede Einzelzahl).

Nachrechnung dieser Seite (keine Messung der Demo): Bei kleiner Lernrate war jeder Lauf, der nicht nahezu optimal endete, derselbe Fall wie im Standardlauf, mit gleichem Abstand: die Wand-Gewohnheit am Start. Bei der größten Lernrate streuten die Abstände breiter. Der einzige katastrophale Lauf wählte am Start die Aktion Süden, also gegen die Wand, verließ den Start nie und verlor deshalb sehr viele Punkte. Ein katastrophaler Lauf (ein Lauf von 20) kam in der Neuberechnung auch bei einer mittleren Lernrate und bei einem sehr langsamen Zerfall je einmal vor. Der Anteil nahezu optimaler Läufe war bei sehr langsamem Zerfall ähnlich hoch wie bei dem Wert der Tabelle und bei den schnelleren Stufen niedriger.

Grenzen: was die Messung zeigt und was nicht

• Ein Beispiel: Die Befunde gelten für ein Raster mit den Voreinstellungen des Standardfalls. Aussagen über Q-Learning allgemein, andere Raster oder andere Rutschwerte belegen sie nicht.
• Wenige Läufe: Aus 20 Läufen je Stufe hat ein Anteil einen Standardfehler von bis zu gut zehn Prozentpunkten (Rechnung dieser Seite). Dass der Anteil über die Trainingsdauer nicht stetig steigt, belegt die Messung; die genaue Form der Kurve, etwa der hohe Wert bei 300 Episoden, nicht.
• Deutungen: Die Wand-Gewohnheit als Beinah-Gleichstand mit zu tiefer Schätzung für Norden ist eine Erklärung, die zu den Messungen passt. Warum eine große Lernrate schlechter abschneidet, ist nicht gemessen; das Ergebnis (Abstand, Anteil katastrophaler Läufe) schon, der Mechanismus nicht. Mit einer abnehmenden Lernrate oder On-Policy-Lernen wurde nicht verglichen.
• Vergleich der Schritte: Umgebungsschritte und Bellman-Backups sind verschiedene Einheiten; Value Iteration braucht das Modell, das dem Lernenden fehlt. Die Zahl ohne Zerfall ist durch die Höchstlänge der Episoden nach oben begrenzt und liegt in der Nachrechnung dieser Seite nahe an dieser Grenze; das Verhältnis hängt damit von der Höchstlänge ab.
• Annahmen des Verfahrens: Genug Training (sonst kann eine harmlos aussehende Gewohnheit genauso billig geschätzt werden wie die echte Optimalroute), ein sinkender Zufallsanteil (ohne Zerfall bleibt er auf dem Start-Wert, im Standardfall 1,0, also rein zufällig; die Konvergenzaussage braucht das nicht, die Messung zeigt dort aber weniger gute Läufe) und eine mäßige Lernrate (sonst gewinnt die jeweils letzte verrauschte Erfahrung zu viel Gewicht).
• Tabelle: Die Q-Tabelle ist dicht gespeichert; bei sehr großen oder stetigen Räumen wird das unhandlich. Jede Erfahrung wird einmal genutzt und dann verworfen.

Erweiterungen und Verweise

Die Demo setzt bewusst nicht um:

• On-Policy-Lernen: die tatsächlich befolgte statt der gierigen Policy lernen (SARSA).
• Wiederverwendung der Erfahrung: ein Modell lernen und damit planen (Dyna-Q).
• Funktionsapproximation: statt der dichten Tabelle eine parametrische Näherung (etwa tiefe Netze, DQN).

Quellen

• Watkins, C. J. C. H., & Dayan, P. (1992): Q-learning. Machine Learning 8, 279–292.
• Sutton, R. S., & Barto, A. G. (2018): Reinforcement Learning: An Introduction, 2. Auflage. MIT Press (Beispiel 6.6, Cliff Walking, Vorlage des Rasters).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/q-learning-demo.

Die Arbeiten wurden nicht nachgeschlagen. Autoren, Jahr und Beispiel nennt die Demo selbst; Zeitschrift und Seiten sowie die Bedingungen an die Lernrate sind aus dem Gedächtnis ergänzt und nicht geprüft. Höchstlänge der Episoden und Schwellen für „nahezu optimal“ und „katastrophal“ stehen im Quelltext der Demo, nicht unter ihren Messwerten.