Q-Learning ist noch nicht skalierbar

• RL hat bei Go·Schach und beim Post-Training von LLMs große Erfolge erzielt, doch die meisten davon beruhen auf On-Policy RL, das neue Rollouts benötigt und sich damit von Off-Policy RL unterscheidet, bei dem sich frühere Daten frei wiederverwenden lassen
• Q-Learning als repräsentatives Off-Policy RL ist zwar sehr sample-effizient, skaliert aber bei langfristigen Aufgaben, die mehr als 100 sinnvolle Entscheidungsschritte erfordern, noch nicht ausreichend
• Der Flaschenhals ist, dass sich verzerrte Bootstrap-Ziele im TD-Lernen mit wachsendem Horizon aufsummieren; das ist eine andere Einschränkung als bei Next-Token-Prediction, Diffusionsmodellen oder kontrastivem Lernen
• In Experimenten mit OGBench konnten flow BC, IQL, CRL und SAC+BC selbst auf einem 1B-Datensatz, der 1000-mal größer ist als übliche Offline-RL-Datensätze, nicht alle langfristigen Aufgaben lösen; die Leistung stagnierte unter dem optimalen Niveau
• Horizon Reduction wie n-step returns und hierarchisches RL verbesserte Skalierbarkeit und Endleistung, doch aktuelle Verfahren mindern das Problem nur um einen konstanten Faktor und reichen nicht aus, um beliebig komplexe langfristige Aufgaben zu lösen

---

Wo die Skalierbarkeit von RL heute steht

• Next-Token-Prediction, denoising diffusion und kontrastives Lernen haben gezeigt, dass es Zielfunktionen gibt, die sich mit großen Datenmengen und Modellen mit Milliarden Parametern skalieren lassen
• Auch RL hat bei Go·Schach übermenschliche Leistung erreicht und löst bei LLMs komplexe Reasoning-Aufgaben wie Mathematik und Coding
• Die meisten heutigen praktischen Erfolgsgeschichten basieren allerdings auf On-Policy RL-Algorithmen
  • Repräsentative Beispiele sind REINFORCE, PPO, GRPO usw.
  • Es werden immer frisch aus der aktuellen Policy gesampelte Rollouts benötigt
  • Frühere Daten lassen sich nicht wiederverwenden
  • Methoden der PPO-Familie können Daten begrenzt wiederverwenden, werden aber gemäß Einordnungen wie in OpenAI-Dokumenten dennoch als On-Policy RL betrachtet
• In Umgebungen wie Brettspielen oder LLMs, in denen sich Rollouts günstig in großer Zahl erzeugen lassen, ist diese Einschränkung womöglich kein großes Problem
• In der Robotik würde es mehrere Monate oder länger dauern, in der realen Welt so viele Samples zu erzeugen, wie sie beim Post-Training eines Sprachmodells mit RL verwendet werden; zudem müsste während des Trainings rund um die Uhr ein Mensch zum Zurücksetzen des Roboters anwesend sein

Off-Policy RL und Q-Learning

• Off-Policy RL kann prinzipiell Daten verwenden, unabhängig davon, wann und wie sie gesammelt wurden
• Dieselben Daten lassen sich mehrfach wiederverwenden, weshalb die Sample-Effizienz in der Regel höher ist
• Es gibt sogar Fälle, in denen ein Roboterhund in der realen Welt in nur 20 Minuten das Laufen gelernt hat
  • Verwandtes Beispiel: walk in the park
• Q-Learning ist der am weitesten verbreitete Off-Policy-RL-Algorithmus
• Die meisten praktischen modellfreien Off-Policy-RL-Algorithmen beruhen auf Varianten des TD-Losses
• Wenn RL auf mehr reale Probleme angewendet werden soll, wird die Frage „Ist Q-Learning, also TD-Learning, skalierbar?“ zentral
• Falls ja, könnten vielfältigere und komplexere reale Aufgaben wie Robotik oder Agenten für die Computernutzung effizient gelöst werden

Was „skalierbar“ hier bedeutet: nicht Breite, sondern Tiefe

• Skalierbarkeit bedeutet hier die Fähigkeit, mit mehr Daten bei ausreichender Coverage, mehr Compute und mehr Zeit schwierigere und längere Probleme mit größerem Horizon lösen zu können
• Das ist etwas anderes als die Fähigkeit, mit einem einzelnen Modell eine größere Zahl von Aufgaben zu lösen
  • Mehr Aufgaben zu bearbeiten heißt nicht zwangsläufig, schwierigere Aufgaben zu lösen
  • Mehrere frühere Scaling-Arbeiten zeigen Potenzial entlang dieser Achse der Breite (width)
• Die wichtigere und schwierigere Achse ist jedoch die Tiefe (depth)
  • Denn sie erfordert fortgeschrittenere Entscheidungsfähigkeiten
• In seiner heutigen Form ist Q-Learning entlang dieser Tiefenachse nicht stark skalierbar
• Um Q-Learning und Off-Policy RL auf komplexe Langfristprobleme auszuweiten, braucht es algorithmische Durchbrüche

Q-Learning fehlt in großen RL-Erfolgsgeschichten

• Viele reale RL-Erfolge beruhen nicht auf TD-basiertem Q-Learning, sondern auf anderen Ansätzen
• AlphaGo, AlphaZero und MuZero verwenden modellbasiertes RL und Monte Carlo tree search; in Brettspielen setzen sie nicht auf TD-Learning
  • Siehe: MuZero, Seite 15
• OpenAI Five erreichte in Dota 2 übermenschliche Leistung mit PPO
  • Siehe: OpenAI Five, Fußnote 6
• RL für LLMs wird derzeit von On-Policy-Policy-Gradient-Verfahren wie PPO und GRPO dominiert
• Praxisbeispiele, in denen Off-Policy RL, insbesondere 1-step TD-Learning, auf einem mit AlphaGo oder LLMs vergleichbaren Maßstab erfolgreich war, werden nicht gezeigt
• Diese Einschätzung soll Off-Policy RL nicht abwerten, sondern unterstreicht vor allem den Bedarf an weiterer Forschung zu RL-Algorithmen

Warum Q-Learning bei langfristigen Aufgaben ins Wanken gerät

• Der TD-Loss von Q-Learning trainiert darauf, den aktuellen Q-Wert an ein Ziel aus Belohnung plus maximalem Q-Wert des nächsten Zustands anzupassen
• Dieses Ziel ist ein verzerrtes Bootstrap-Ziel, das nicht mit dem tatsächlichen optimalen Q-Wert übereinstimmen muss
• Der Hauptgrund dafür, dass Q-Learning schlecht skaliert, ist, dass sich die Verzerrung des Vorhersageziels entlang des Horizons aufsummiert
• Diese Akkumulation der Verzerrung wirkt als grundlegende Grenze des TD-Lernens
  • Zielfunktionen wie Next-Token-Prediction, denoising diffusion oder kontrastives Lernen haben keine solche Verzerrung im Vorhersageziel
  • Bei BYOL und DINO gibt es zwar Verzerrung, sie akkumuliert sich aber nicht entlang des Horizons
• Je komplexer das Problem und je länger der Horizon, desto stärker summiert sich die Verzerrung der Bootstrap-Ziele auf
• Mehr Daten und größere Modelle allein können dieses Problem nicht leicht entschärfen
• Damit hängt auch zusammen, dass in der Praxis kaum höhere Diskontfaktoren wie (\gamma > 0.999) verwendet werden
• Policy-Gradient-Methoden leiden vergleichsweise weniger unter diesem Problem
  • On-Policy-Verfahren zur Wertschätzung wie GAE können längere Horizons relativ leichter behandeln, nehmen dafür aber höhere Varianz in Kauf
  • Sie sind nicht strikt an eine 1-step-Rekursion gebunden

Skalierungsexperimente auf Basis von OGBench

• Das jüngste Paper Horizon Reduction Makes RL Scalable überprüft diese Hypothese mit verschiedenen kontrollierten Scaling-Studien
• Ziel ist zu prüfen, ob heutige Off-Policy-RL-Methoden sehr schwierige Aufgaben lösen können, wenn lediglich Daten und Compute vergrößert werden
• Für die Experimente wurden komplexe, zuvor ungelöste Aufgaben aus OGBench verwendet
• Die Anforderungen der Aufgaben sind wie folgt
  • Der Agent muss aus unstrukturierten, zufälligen Play-Style-Demonstrationen komplexes zielgerichtetes Verhalten lernen
  • Zur Testzeit muss er präzise Manipulation, kombinatorisches Lösen von Rätseln und langfristige Navigation ausführen
  • Die Aufgaben erstrecken sich über 1.000 Environment-Schritte
• Die Experimente wurden so entworfen, dass Störvariablen minimiert werden
  • Es wurde nahezu unendliche Datenmenge gesammelt, sodass Overfitting praktisch unmöglich ist
  • Um das Explorationsproblem auszuschließen, liegt der Fokus auf Offline RL
  • Es wird sichergestellt, dass der Datensatz ausreichend Coverage hat und dass alle Aufgaben mit dem gegebenen Datensatz lösbar sind
  • Um den Aufwand für Repräsentationslernen zu senken, werden direkt Ground-Truth-State-Observations bereitgestellt
• Wenn Q-Learning selbst in diesem kontrollierten Setting nicht skaliert, ist es in realen Umgebungen mit begrenzten Daten und noisy Beobachtungen noch unwahrscheinlicher

Ergebnisse standardisierter Offline-RL-Algorithmen

• Standardisierte und weit verbreitete Offline-RL-Algorithmen konnten nicht alle Aufgaben lösen
• Untersucht wurden flow BC, IQL, CRL und SAC+BC
• Die Experimente wurden selbst mit einem 1B großen Datensatz durchgeführt
  • Dieser ist (1000 \times) größer als typische Offline-RL-Datensätze
• Noch wichtiger ist, dass die Leistung oft auf einem Plateau weit unterhalb der optimalen Leistung landete
• Auch verschiedene Ablationen und Kontrollversuche mit größeren Modellen, längerem Training oder anderen Hyperparametern brachten keine Verbesserung
• Die einzige Methode mit klarer Wirkung war Horizon Reduction

Verbesserungen durch Horizon Reduction

• Die oben genannte Hypothese lautet, dass der Horizon und die damit verbundene Akkumulation von Verzerrung das Haupthindernis für die Skalierung von Off-Policy RL sind
• Um das zu prüfen, wurden verschiedene Verfahren zur Horizon Reduction ausprobiert, die die Zahl verzerrter TD-Backups verringern
  • Beispiele sind n-step returns, hierarchisches RL usw.
• Die Ergebnisse waren positiv
  • Schon einfache Verfahren wie n-step returns verbesserten Skalierbarkeit und Endleistung deutlich
  • Es handelt sich nicht nur um einen Trick zur Beschleunigung des Trainings, sondern verbessert auch die asymptotische Leistung
  • Voll ausgearbeitete hierarchische Methoden funktionierten noch besser
• Über alle Experimente hinweg war Horizon Reduction die einzige Technik, die konsistent wirkte
• Daten und Compute einfach nur zu vergrößern reicht nicht aus, um den Fluch des Horizons zu überwinden
• Es braucht bessere Algorithmen, die dieses Problem direkt adressieren

Forschungsrichtungen für eine skalierbare Off-Policy-RL-Zielfunktion

• Horizon Reduction kann den Weg zu skalierbarem Q-Learning öffnen, löst das Problem mit heutigen Verfahren aber nicht grundlegend
• Aktuelle Methoden wie n-step returns und hierarchisches RL entschärfen das Problem meist nur um einen konstanten Faktor
• Es fehlt weiterhin an Off-Policy-RL-Algorithmen, die sich auf beliebig komplexe langfristige Probleme skalieren lassen
• Mögliche Forschungsrichtungen lassen sich in drei Punkte gliedern
  • Die Suche nach einfachen und skalierbaren rekursiven Hierarchien, die über eine zweistufige Hierarchie hinausgehen, um Horizons beliebiger Länge zu behandeln
  • Ein modellbasierter RL-Ansatz, bei dem zunächst ein Modell gelernt und dann On-Policy RL innerhalb dieses Modells ausgeführt wird, da Modelllernen überwachtes Lernen ist und sich On-Policy RL ebenfalls skalieren lässt
  • Ansätze, die TD-Learning vollständig vermeiden
    • Beispielsweise basiert quasimetric RL auf der LP-Formulierung von RL
    • Auch MC-basierte Verfahren wie contrastive RL könnten sich besser skalieren lassen als TD-basierte Ansätze
• Das beschriebene experimentelle Setup kann als Ausgangspunkt dienen, um solche Ideen zu testen
  • Komplexe Robotikaufgaben und Datensätze sind bereits entworfen
  • Es wurde bestätigt, dass die Aufgaben mit den gegebenen Daten lösbar sind
  • Durch das Hinzufügen weiterer Würfel lässt sich der Schwierigkeitsgrad der Aufgaben beliebig erhöhen, um die algorithmische Skalierbarkeit kontrolliert unter Stress zu testen
  • Code: horizon-reduction

[GN⁺]

Hacker-News-Kommentare

• Dieser Beitrag scheint den größeren Grund, warum Q-Learning schwer zu skalieren ist, auszulassen.
  Je länger der Horizont wird, desto stärker wächst die Zahl möglicher Zustände normalerweise exponentiell; um ein Q zu lernen, das mit diesen Zuständen umgehen kann, muss auch die Datenmenge exponentiell wachsen.
  Beim On-Policy-Lernen ist dieses Problem geringer, weil nur Zustände in der Nähe der aktuellen Policy wichtig sind und in der Praxis auch nur solche Zustände gesampelt werden.

  • Ich halte die Analyse des Overestimation Bias im Beitrag für richtig.
    Der Kern ist, dass die max-Operation im Q-Learning Rauschen über Zeitschritte hinweg verstärkt; Verfahren zur Bias-Reduktion wie https://arxiv.org/abs/1509.06461 haben erfolgreich die Leistung von Reinforcement-Learning-Agenten verbessert.
    Untersuchungen zufolge tritt dieses Phänomen stärker in Zuständen auf, die das Netzwerk nicht oft besucht hat.
    Dass es exponentiell viele Zustände gibt, ist nur dann entscheidend, wenn es zwischen diesen Zuständen keine Muster gibt. Wenn eine lernbare Struktur existiert, kann es gut funktionieren, und das ist keine Schwäche von Deep Learning, sondern eine Stärke.
    Entscheidend ist, das richtige Lernziel zu wählen; der Beitrag argumentiert im Grunde, dass Q-Learning nicht dieses Ziel ist.
    Ich frage mich auch, ob modellbasiertes Reinforcement Learning wie MuZero eine Lösung für die Bedenken des Autors sein könnte. MuZero kann durch Reanalyse früherer Trajektorien die Lerneffizienz erhöhen, und Monte-Carlo Tree Search (MCTS) ist eine prinzipielle Methode, um durch mehrstufiges Entfalten des Modells den Horizont zu verkürzen.
    Die max-Operation in MCTS kann ähnliche Probleme verursachen, aber der Prozess tieferer Suche kann das ausgleichen.
  • https://news.ycombinator.com/item?id=44280505 Dieser Thread könnte hilfreich sein.
    Aus der Sicht eines völligen Laien: Manche Aufgaben könnten, obwohl sie „tief“ sind, ausreichend „gleichförmig“ sein, sodass selbst schlechte Stichproben ausreichen. Solche Aufgaben würde ich gern ergodische Aufgaben nennen.
    Natürlich wird es sicher auch Aufgaben geben, die nicht so sind.
  • Entspricht dieser Unterschied im Kern dem zwischen allgemeiner Gitter-Monte-Carlo-Integration und Monte-Carlo-Integration mit Importance Sampling?

• Dieses Paper setzt bereits voraus, dass man sich mit Reinforcement Learning ziemlich gut auskennt.
  Wenn man wirklich tiefer in Reinforcement Learning einsteigen möchte, ist die Einführungsvorlesung von David Silver (DeepMind) hervorragend: https://youtu.be/2pWv7GOvuf0?si=CmFJHNnNqraL5i0s

• Ich stimme voll zu und halte das für eine sehr gute Zusammenfassung.
  Ganz kurz gesagt geht es darum, ein bewegliches Ziel zu verfolgen, das sich je nachdem verändert, wie ich mich bewege.
  Bei wertbasiertem Reinforcement Learning gibt es keine echte richtige Antwort, gegen die man konvergieren könnte. Man minimiert gewissermaßen eine Differenz, bei der auf beiden Seiten der Gleichung die eigene Approximation steht.
  Trotzdem halte ich das nicht für hoffnungslos. Meiner Ansicht nach ist Reinforcement Learning sehr nah daran, zu funktionieren; was bisher fehlte, war ein verlässliches Weltmodell bzw. eine Vorwärtsdynamik-Funktion.
  Wenn man die hat, kann man planen, ohne zu explorieren, und solche Modelle gibt es inzwischen.

• Der Nutzen von Off-Policy-Lernen ist grundsätzlich dadurch begrenzt, dass ineffiziente Daten aus der frühen Exploration später nicht besonders nützlich sind, um eine verfeinerte Policy zu verbessern.
  Das wird klar, wenn man an Fehler im Schach, verkrampfte Bewegungen oder gescheiterte Puzzle-Lösungen denkt.
  Noch klarer wird es, wenn man erkennt, dass Daten nur dann off-policy sind, wenn sie etwas beschreiben, was die aktuelle Policy nicht tun würde.
  Die Lösung für dieses Problem hängt leider wohl damit zusammen, dass bessere Generalisierung und höhere Sample-Effizienz nötig sind.

  • Beweist diese Behauptung nicht zu viel?
    Wie erklärt man dann den zitierten Hund, der durch Off-Policy-Lernen in 20 Minuten laufen gelernt hat? Oder ist die Aussage subtiler gemeint?

• Ich finde es merkwürdig, dass Decision Transformer und Trajectory Transformer fehlen.
  Beide sind Offline-Ansätze und funktionieren dank Attention-Mechanismus bei Aufgaben mit langem Horizont ziemlich gut, weil sie das Credit-Assignment-Problem umgehen.
  Die meisten Reinforcement-Learning-Forscher sehen solche Ansätze nicht als „echtes Reinforcement Learning“, weil sie außerhalb des Kontextfensters keine Credits zuweisen können und daher keine Aufgaben mit unendlichem Horizont lernen können.
  Aber wenn das Kontextfenster mehr als eine Million Tokens umfasst, könnte das in der Praxis vielleicht weniger problematisch sein? Ich wäre neugierig auf andere Meinungen.
  DT: https://arxiv.org/abs/2106.01345
  TT: https://arxiv.org/abs/2106.02039

  • TFP zitiert den Decision Transformer.
    Nur weil man Transformer verwendet, umgeht man nicht das Credit-Assignment-Problem.
    Ein Transformer ist eine Architektur zur Lösung von Sequenzmodellierungsproblemen, und das Credit-Assignment-Problem im Reinforcement Learning ist ein Beispiel für ein solches Problem. Solche Architekturen gab es auch früher schon viele.
    Dass das Credit-Assignment-Problem schwierig ist, ist eine Aussage über Datensparsamkeit. Man kann es nicht allein durch die Wahl der Architektur „umgehen“.

• Menschen machen tatsächlich beides.
  Sie lernen on-policy, indem sie die Folgen ihres eigenen Handelns explorieren, und auch off-policy, etwa durch Expertendemonstrationen.
  Der Unterschied ist, dass Menschen gute von schlechten Handlungen unterscheiden und nur die als gut bewerteten Handlungen herausfiltern und daraus lernen können.
  In den meisten Off-Policy-Reinforcement-Learning-Ansätzen sind auch viele schlechte Handlungen enthalten, und wenn sie in den Trainingssatz eingehen, verlangsamt das das Lernen.

  • „Gute von schlechten Handlungen unterscheiden können“ stimmt nicht immer.
    Deshalb sind manche Expertendemonstrationen reizvoll: Man sieht, dass sie bessere Ergebnisse erzielen, obwohl sie aus Sicht von „Best Practices“ auf Anfängerniveau völlig falsch aussehen.
    Natürlich bedeutet es manchmal auch nur, dass man, wenn man so gut ist, solche Techniken oder Fehler verkraften kann.

• Es ist erwähnenswert, dass Aufgaben mit langem Horizont, die Menschen durch wiederholtes Üben lernen, in Aufgaben mit kürzerem Horizont zerlegt und später hierarchisch zusammengesetzt werden.

  • Vielleicht ist das naiv gedacht, aber das wirkt eher wie ein Problem des Ansatzes als des Algorithmus.
    Ein Modell kann vielleicht nicht von Anfang an Aufgaben mit langem Horizont bewältigen, aber es kann zuerst Fertigkeiten mit kurzem Horizont lernen und dann diese Bündel kleiner Fertigkeiten nutzen, um längere Horizonte zu lernen.
    Es ist wie das Chunking, das wir alle betreiben.
    Niemand lernt, ein Verkehrsflugzeug interkontinental zu fliegen, als Sequenz winziger Hand- und Armbewegungen.
    Als Kind lernt man vielleicht auf diese Weise, einen Ball zu greifen, aber Fliegen oder Sport bestehen aus Hierarchien gelernter Fertigkeiten und Pläne.

• Mir gefällt der Beitrag, aber durch die Verwendung unerklärter Abkürzungen hat er die Chance vertan, für ein breiteres Publikum nützlich zu sein.
  Kleiner Kritikpunkt, aber Abkürzungen und Fachbegriffe sollte man erklären.

  • Bei inhaltlich sehr guten Texten, die aber umfangreiches Vorwissen voraussetzen und dadurch weniger zugänglich sind, sind KI-Tools zum Erklären und Vereinfachen ziemlich nützlich.
    Ich habe es gerade mit dem neuen Browser Dia ausprobiert, und es hat gut funktioniert. Man kann den Text auch in den bevorzugten Modellanbieter kopieren und einfügen.
    So kann der Beitrag knapp bleiben, während man dem KI-Tool Fragen stellen und Unklarheiten klären kann.
  • Wenn das Fazit lautet: „Kann bitte jemand eine skalierbare Q-Learning-Methode entwickeln“, dann richtet sich der Beitrag eindeutig an andere Reinforcement-Learning-Forscher.

• Das Magische an Off-Policy-Methoden wie Q-Learning ist, dass sie zum optimalen Ergebnis konvergieren, selbst wenn sie nur nichtoptimale Trainingsdaten sehen.
  Wenn man zum Beispiel einen Datensatz von Schachpartien völlig zufällig ziehender Agenten ohne jede Strategie als Eingabe für Q-Learning verwendet, konvergiert es letztlich trotzdem zur optimalen Policy — nur langsamer als mit hochwertiger Eingabe.

  • Wenn das wahr ist, kommt es meiner Meinung nach einer Definition davon nahe, dass diese Aufgabe ergodisch ist.
    Vielleicht verwende ich den Begriff etwas abgewandelt, aber ich denke, dass es auch nicht-ergodische Aufgaben geben wird.