🤖 machine learning

Bridging the Gap Between Average and Discounted TD Learning

Dieser Beitrag stellt einen neuartigen Algorithmus zur Politikbewertung für die Umgebung mit durchschnittlicher Belohnung vor, der zwei markovsche Trajektorien nutzt, um eine Konvergenz ohne dimensionsabhängige Terme zu garantieren und eine quadratische Stichprobenkomplexität zu erreichen, wodurch die theoretische Effizienz des diskontierten TD-Lernens erreicht wird.

Ursprüngliche Autoren: Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis, Alex Olshevsky

Veröffentlicht 2026-05-05

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis, Alex Olshevsky

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Der „Dauerjob" vs. der „Kurzzeit-Job"

Stellen Sie sich vor, Sie trainieren einen Roboter, um eine Aufgabe zu erledigen. Es gibt zwei Hauptmethoden, dem Roboter mitzuteilen, was „eine gute Arbeit" bedeutet:

Der diskontierte Ansatz (Der Kurzzeit-Job): Dies ist vergleichbar damit, einen Arbeiter für eine bestimmte Aufgabe heute zu bezahlen. Ihnen liegt viel daran, was er jetzt gerade verdient, und weniger daran, was er nächstes Jahr verdienen könnte. In der Mathematik nennt man dies „diskontiertes Lernen". Es ist leicht zu analysieren, da die Regeln klar und stabil sind.
Der Durchschnittsbelohnungs-Ansatz (Der Dauerjob): Dies ist vergleichbar damit, einem CEO ein Gehalt basierend auf der langfristigen Leistung des Unternehmens über einen unendlichen Horizont zu zahlen. Ihnen liegt nicht an einem einzelnen guten Tag oder einem einzelnen schlechten Tag; Ihnen liegt am stetigen Durchschnitt über die Ewigkeit. Dies ist das „Durchschnittsbelohnungs"-Szenario.

Das Problem:
Lange Zeit war die Mathematik für den „Dauerjob" (Durchschnittsbelohnung) ein Albtraum für Wissenschaftler. In der Welt des „Kurzzeit-Jobs" verhält sich die Mathematik wie ein Gummiband, das immer zu einem einzigen, klaren Mittelpunkt zurückfedert. Doch in der Welt des „Dauerjobs" ist die Mathematik wie eine rutschige Rutsche. Die Regeln zwingen den Roboter nicht dazu, sich auf nur eine Antwort festzulegen; er könnte für immer herumrutschen oder an verschiedenen Stellen stehen bleiben, je nachdem, wie Sie ihn angestoßen haben.

Aus diesem Grund mussten frühere Versuche, das Lernen des Roboters für den „Dauerjob" zu beheben, seltsame, unrealistische Annahmen treffen (wie etwa zu tun, als könnte der Roboter sich nicht in einem bestimmten Zustand befinden) oder akzeptieren, dass der Roboter möglicherweise nie zu einer einzigen, zuverlässigen Antwort findet.

Die Lösung: Ein neuer Weg, die Rutsche zu bewältigen

Die Autoren dieses Papiers stellten einen neuen Algorithmus vor, um dieses Problem zu lösen. Es gelang ihnen, die „rutschige Rutsche" wieder wie ein stabiles Gummiband zu verhalten, ohne diese seltsamen Annahmen zu treffen.

Hier ist, wie sie es taten, unter Verwendung einiger Metaphern:

1. Der „Doppel-Ketten"-Trick (Die Zwillings-Wanderer)

Um das mathematische Problem zu lösen, entwickelten die Autoren einen Algorithmus, der zwei unabhängige Roboter verwendet, die gleichzeitig herumlaufen.

Die Analogie: Stellen Sie sich vor, Sie versuchen, die durchschnittliche Körpergröße der Menschen in einer Stadt zu erraten. Wenn Sie eine Person fragen: „Was ist die durchschnittliche Größe der Person, die neben Ihnen steht?" und dies dann mit „Was ist die durchschnittliche Größe einer zufälligen Person, die Sie gerade getroffen haben?" multiplizieren, erhalten Sie ein falsches Ergebnis, weil die beiden Personen nicht unabhängig voneinander sind.
Die Lösung: Die Autoren verwenden zwei separate „Ketten" von Daten. Ein Roboter beobachtet die aktuelle Situation, und ein ganz anderer Roboter (der auf einer parallelen Spur läuft) beobachtet einen zufälligen Zustand. Indem diese beiden Beobachtungen getrennt und unabhängig voneinander gehalten werden, verwirrt sich die Mathematik nicht mehr und kann den wahren Durchschnitt finden.

2. Die „Gradienten-Aufteilung" (Das Zwei-Personen-Team)

Das Papier verwendet eine mathematische Technik namens „Gradienten-Aufteilung".

Die Analogie: Stellen Sie sich vor, Sie versuchen, einen schweren Felsbrocken einen Hügel hinaufzuschieben, können aber den Hang nur aus zwei verschiedenen Winkeln sehen. Wenn Sie versuchen, basierend auf nur einem Winkel zu schieben, schieben Sie möglicherweise in die falsche Richtung.
Die Lösung: Der Algorithmus teilt die „Schiebekraft" in zwei Teile auf. Ein Teil behandelt die unmittelbare Veränderung, und der andere Teil behandelt den langfristigen Durchschnitt. Wenn Sie diese beiden „Teilschübe" kombinieren, reproduzieren sie perfekt die Kraft, die benötigt wird, um den Felsbrocken geradewegs nach oben zu schieben, obwohl keiner der beiden Teile dies allein könnte. Dies ermöglicht es der Mathematik, reibungslos zu funktionieren, genau wie in der Welt des „Kurzzeit-Jobs".

3. Das „Einzel-Ketten"-Upgrade (Der Solo-Wanderer)

Obwohl die Verwendung von zwei Robotern großartig funktioniert, ist sie teuer. Die Autoren schufen auch eine Version, die nur einen Roboter verwendet.

Die Analogie: Dies ist wie ein Solo-Wanderer, der ein mentales „Notizbuch" darüber führt, wo er gewesen ist. Anstatt eine zweite Person nach einem zufälligen Datenpunkt zu fragen, schätzt der Wanderer den Durchschnitt basierend auf seiner eigenen Geschichte.
Der Kompromiss: Dies ist etwas weniger effizient (es dauert etwas länger zu lernen), aber viel praktischer, da Sie nur einen laufenden Roboter benötigen.

Warum dies wichtig ist (Die Ergebnisse)

Das Papier behauptet drei große Siege gegenüber früheren Methoden:

Es funktioniert für alle (Tabellarisch & Linear): Frühere Methoden versagten oft, wenn man versuchte, sie auf einfache, kleine Probleme (sogenannte „tabellarische" Einstellungen) anzuwenden, oder wenn man sie auf komplexe, große Probleme anwendete. Diese neue Methode funktioniert für beides, ohne dass spezielle Regeln benötigt werden. Es ist ein universeller Schlüssel.
Es findet eine Antwort: Alte Methoden ließen den Roboter manchmal an verschiedenen Stellen stehen bleiben, je nachdem, wie Sie ihn gestartet haben. Diese neue Methode garantiert, dass der Roboter immer genau am selben, einzigartigen Ort stehen bleibt, egal wie Sie ihn starten.
Es ist schneller und intelligenter: Die Mathematik zeigt, dass diese neue Methode viel schneller lernt als frühere Versuche.
- Die Konditionszahl: In der Mathematik ist die „Konditionszahl" ein Maß dafür, wie „chaotisch" oder „rutschig" das Problem ist. Frühere Methoden wurden immer langsamer, je chaotischer das Problem wurde (skaliert mit der vierten Potenz der Chaotizität). Diese neue Methode skaliert mit dem Quadrat der Chaotizität.
- Die Metapher: Stellen Sie sich vor, Sie versuchen, durch Schlamm zu laufen. Alte Methoden blieben stecken und verlangsamten sich exponentiell, je tiefer der Schlamm wurde. Diese neue Methode ist wie das Anziehen von Schneeschuhen; Sie sinken immer noch ein wenig ein, aber Sie bewegen sich mit einem stetigen, handhabbaren Tempo weiter.

Zusammenfassung

Das Papier schließt die Lücke zwischen der einfachen Mathematik des kurzfristigen Lernens und der schwierigen Mathematik des langfristigen Lernens. Durch die Verwendung eines cleveren „Zwei-Roboter"-Tricks und einer „Aufteilungs"-Technik schufen sie einen Algorithmus, der stabil, zuverlässig und schnell ist und das langfristige Durchschnittslernen endlich so robust macht wie das kurzfristige Lernen.

Technische Zusammenfassung: Überbrückung der Lücke zwischen durchschnittlicher und diskontierter TD-Lernmethode

Problemstellung

Temporal-Difference (TD)-Lernen ist ein Eckpfeiler des Reinforcement Learning, doch seine theoretische Analyse im Durchschnittsbelohnungs-Setting hinkt dem diskontierten Setting erheblich hinterher. Im diskontierten Fall ist der Bellman-Operator eine Kontraktionsabbildung, was eindeutige Lösungen und eine unkomplizierte Konvergenzanalyse gewährleistet. Im Durchschnittsbelohnungs-Setting hingegen ist der Bellman-Operator nicht kontraktiv bezüglich irgendeiner Norm, und die Lösung der entsprechenden Bellman-Gleichung ist nicht eindeutig (sie ist nur bis auf eine additive Konstante definiert).

Die bestehende Literatur zur durchschnittlichen TD-Lernmethode leidet im Vergleich zum diskontierten Fall unter mehreren Einschränkungen:

Einschränkende Annahmen: Viele Methoden erfordern Annahmen (z. B. $\Phi\theta \neq ce$ ), die das tabellarische Setting ausschließen.
Konvergenzgarantien: Einige Ansätze garantieren die Konvergenz nur zu einem von der Stichprobenbahn abhängigen Fixpunkt oder einer Menge, anstatt zu einer eindeutigen, deterministischen Lösung.
Dimensionsabhängigkeit: Konvergenzschranken enthalten oft explizite Faktoren der Parametern dimension $d$ .
Skalierung der Konditionszahl: Die besten verfügbaren Stichprobenkomplexitäten zeigen oft eine quartische Abhängigkeit von der Konditionszahl des Problems ( $O(\eta^{-4})$ ), wohingegen das diskontierte Setting eine quadratische Skalierung erreicht ( $O(\eta^{-2})$ ).
Algorithmische Komplexität: Das Erreichen einer besseren Skalierung in früheren Arbeiten erforderte oft komplexe Varianzreduktionstechniken (z. B. verschachtelte Schleifen), was von der Einfachheit des Standard-TD abweicht.

Methodik

Die Autoren schlagen einen neuartigen Ansatz zur Policy-Evaluation im Durchschnittsbelohnungs-Setting vor, indem sie die Lösung der Bellman-Gleichung als optimierungsproblem mit Nebenbedingungen formulieren. Der Kern der Erkenntnis besteht darin, dass die relative Wertfunktion $W^*$ eine stationäre Nebenbedingung erfüllen muss ( $\mu^\top W^* = 0$ ).

1. Double-Chain-Algorithmus

Um die projizierte Bellman-Gleichung $W^* = \Pi T_\pi W^*$ zu lösen, wobei $\Pi = I - e\mu^\top$ , leiten die Autoren eine stochastische Update-Regel her. Eine zentrale Herausforderung bei der stochastischen Approximation für dieses Setting ist das „Double-Sampling"-Problem: Die Schätzung des Terms $\mu\mu^\top(R + W_t)$ erfordert den Erwartungswert eines Produkts von Zufallsvariablen, der aufgrund von Korrelationen nicht aus einer einzigen Trajektorie geschätzt werden kann.

Um dies zu lösen, führen die Autoren einen Double-Chain-Algorithmus ein, der in jeder Iteration zwei unabhängige Markov-Ketten ( $\{s_t\}$ und $\{\hat{s}_t\}$ ) nutzt.

Update-Regel: Der Parametervektor $\theta_t$ $θ_{t}$ wird unter Verwendung zweier Komponenten aktualisiert:
- $g(s_t, s'_t, \theta_t)$ : Schätzt den Standard-TD-Fehlerterm $D(R + P\Phi\theta_t - \Phi\theta_t)$ .
- $f(s_t, \hat{s}_t, \theta_t)$ : Schätzt den Nebenbedingungsterm $-\mu\mu^\top(R + \Phi\theta_t)$ unter Verwendung der unabhängigen Stichprobe $\hat{s}_t$ , um die Korrelation zu durchbrechen.
Lineare Approximation: Die Methode lässt sich auf lineare Funktionsapproximation ( $W \approx \Phi\theta$ ) verallgemeinern, indem die Updates auf den Merkmalsraum projiziert werden.

2. Single-Chain-Algorithmus

Um den Rechenaufwand für die Wartung zweier Ketten zu vermeiden, schlagen die Autoren einen Single-Chain-Algorithmus vor, der von Gradient-TD (GTD) inspiriert ist.

Mechanismus: Anstatt eine zweite unabhängige Zustandsstichprobe $\hat{s}_t$ zu ziehen, führt der Algorithmus eine Hilfsvariable $w_t$ ein, die den Erwartungswert $E[\phi(s)] = \Phi^\top\mu$ verfolgt.
Update: Der Term $\phi(\hat{s}_t)$ im Double-Chain-Update wird durch $w_t$ ersetzt. Die Variable $w_t$ wird über einen separaten stochastischen Approximationsschritt aktualisiert, um gegen $\Phi^\top\mu$ zu konvergieren.
Kompromiss: Obwohl dies die Stichprobenanforderung auf eine einzige Trajektorie vereinfacht, zeigt die Analyse eine etwas schlechtere Abhängigkeit von der Konditionszahl im Vergleich zur Double-Chain-Variante.

3. Theoretischer Rahmen: Gradient Splitting

Die Konvergenzanalyse stützt sich auf die Technik des Gradient Splitting [19]. Die Autoren zeigen, dass die erwartete Update-Richtung ihres Algorithmus als ein „Gradient Splitting" einer spezifischen zusammengesetzten quadratischen Funktion wirkt:
$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$
Dies ermöglicht den Autoren, den Algorithmus unter Verwendung standardmäßiger SGD-Rekursionstechniken (Stochastic Gradient Descent) zu analysieren, trotz der nicht-kontraktiven Natur des zugrunde liegenden Bellman-Operators.

Hauptbeiträge

Die Arbeit behauptet, die theoretische Lücke zwischen durchschnittlicher und diskontierter TD-Lernmethode zu überbrücken, indem sie folgende Merkmale gleichzeitig erreicht:

Einzigartiger, stichprobenunabhängiger Fixpunkt: Die vorgeschlagenen Algorithmen konvergieren fast sicher zu einer einzigen, deterministischen Lösung $\theta^*$ , die unabhängig von der zufälligen Trajektorie und der Initialisierung ist.
Anwendbarkeit auf tabellarische und lineare Settings: Die Analyse gilt sowohl für tabellarische Fälle (wo $\Phi = I$ ) als auch für lineare Funktionsapproximation, ohne die einschränkende Annahme $e \notin \text{span}(\Phi)$ zu benötigen.
Dimensionsunabhängige Schranken: Die Konvergenzschranken enthalten keine expliziten Faktoren der Dimension $d$ (außer denen, die in $\|\theta^*\|$ oder $\|\theta_0\|$ inhärent sind).
Konvergenz des letzten Iterierten: Die Ergebnisse sind für den letzten Iterierten garantiert und entsprechen dem Standard im diskontierten TD, anstatt sich auf die Mittelung von Iterierten zu verlassen.
Verbesserte Skalierung der Konditionszahl:
- Der Double-Chain-Algorithmus erreicht eine Stichprobenkomplexität von $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$ , wobei $\eta_1$ eine Konditionszahl ist, definiert als $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$ . Dies entspricht der quadratischen Skalierung, die im diskontierten Setting beobachtet wird.
- Der Single-Chain-Algorithmus erreicht $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (quartisch), was eine Verbesserung gegenüber einigen früheren Arbeiten darstellt, jedoch etwas schlechter ist als die Double-Chain-Variante.
Algorithmische Einfachheit: Die quadratische Skalierung wird ohne Varianzreduktionstechniken (z. B. verschachtelte Schleifen oder periodische Vollbatches) erreicht, wodurch die Einfachheit der einfachen TD-Updates erhalten bleibt.

Ergebnisse

Die Autoren liefern eine Finite-Sample-Analyse für beide Algorithmen unter i.i.d.- und Markov-Sampling, sowohl mit konstanten als auch mit abklingenden Schrittweiten.

Theoretische Schranken: Die Sätze 4.1–4.3 etablieren Konvergenzraten und Stichprobenkomplexitäten. Die Double-Chain-Methode entspricht in Bezug auf die Parameterskalierung dem State-of-the-Art für diskontiertes TD.
Numerische Experimente: Die Algorithmen wurden an 15 tabellarischen MDPs aus OpenAI Gym und MO-Gymnasium getestet.
- Die Ergebnisse zeigen, dass die vorgeschlagenen Methoden im Allgemeinen die vorherigen Baselines (einschließlich [10], [11], [12], [17], [18] und [21]) in Bezug auf den Approximationsfehler relativ zur wahren Lösung übertreffen.
- Die Experimente bestätigen, dass die Methoden zu der eindeutigen Lösung konvergieren, wohingegen einige Baselines (die zu Mengen oder stichprobenabhängigen Punkten konvergieren) im tabellarischen Setting eine höhere Varianz oder einen höheren Fehler aufweisen.

Bedeutung

Die Arbeit behauptet, persistente theoretische Vorbehalte im Zusammenhang mit der Analyse des durchschnittlichen TD-Lernens zu beheben. Durch die Nutzung von Gradient Splitting und einer Zwei-Ketten- (oder Single-Chain mit Hilfsvariable) Stichprobenstrategie demonstrieren die Autoren, dass durchschnittliches TD-Lernen dieselben günstigen Konvergenzeigenschaften wie diskontiertes TD erreichen kann:

Eindeutigkeit: Konvergenz zu einer wohldefinierten, eindeutigen Lösung.
Allgemeingültigkeit: Anwendbarkeit auf tabellarische und lineare Settings ohne einschränkende Annahmen.
Effizienz: Quadratische Abhängigkeit von der Konditionszahl ohne die Notwendigkeit komplexer Varianzreduktionsmechanismen.

Diese Arbeit legt nahe, dass die theoretischen Schwierigkeiten des Durchschnittsbelohnungs-Settings überwunden werden können, indem das Problem als Optimierungsproblem mit Nebenbedingungen neu formuliert und spezifische Stichprobenstrategien genutzt werden, um die nicht-kontraktive Natur des Bellman-Operators zu bewältigen.