📊 statistics

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Dieses Paper führt die Robust Halpern Iteration (RHI) ein, einen modellfreien Algorithmus für robustes Average-Reward Reinforcement Learning, der einen neuartigen Multi-Level-Monte-Carlo-Schätzer nutzt, um eine erstklassige endliche Stichprobenkomplexität für das Finden von $\varepsilon$ -optimalen Strategien unter verschiedenen Unsicherheitsmodellen zu erreichen.

Ursprüngliche Autoren: Zachary Roch, George Atia, Yue Wang

Veröffentlicht 2026-06-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Zachary Roch, George Atia, Yue Wang

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

Die große Vorstellung: Das „Sim-to-Real“-Problem

Stellen Sie sich vor, Sie trainieren einen Roboter zum Gehen. Sie bringen es ihm in einem perfekten, reibungsfreien Videospiel-Simulator bei. Im Spiel lernt es, perfekt zu laufen. Aber wenn Sie es in die reale Welt setzen, ist der Boden rutschig, der Wind weht, und der Roboter fällt um.

Dies ist die Sim-to-Real-Lücke. Die Trainingsumgebung des Roboters (die Simulation) stimmt nicht mit der realen Welt überein.

Die meisten Standard-KI-Trainings gehen davon aus, dass die Welt exakt so ist, wie sie gelehrt wurde. Diese Arbeit verfolgt einen anderen Ansatz: Robustes Reinforcement Learning. Anstatt darauf zu hoffen, dass die Welt gleich bleibt, lehrt diese Methode die KI, sich auf das Worst-Case-Szenario (den schlimmsten Fall) vorzubereiten. Sie fragt: „Was ist die schlimmste mögliche Version dieser Umgebung, und wie erreiche ich selbst dann die beste Leistung?“

Die spezifische Herausforderung: Das „lange Spiel“

Die Arbeit konzentriert sich auf eine bestimmte Art von Belohnung namens Durchschnittliche Belohnung (Average-Reward).

Diskontierte Belohnung (Der alte Weg): Stellen Sie sich ein Videospiel vor, in dem Punkte, die Sie heute erhalten, 100 % wert sind, Punkte von morgen 99 % und Punkte vom übermorgigen Tag 98 %. Dies macht die KI „kurzsichtig“ (myopisch). Sie achtet mehr auf unmittelbare Punkte als auf das langfristige Überleben.
Durchschnittliche Belohnung (Der neue Weg): Dies ist für das „lange Spiel“. Denken Sie an einen Taxifahrer. Es ist ihm egal, ob er in der ersten Stunde 100 $ verdient und in der zweiten 0 $; es kommt ihm auf seinen Durchschnittsverdienst über ein ganzes Jahr an. Diese Arbeit lehrt die KI, diesen langfristigen Durchschnitt zu maximieren, selbst wenn die Umgebung chaotisch ist.

Das Problem mit bisherigen Methoden

Die Autoren weisen auf zwei Hauptprobleme bestehender Lösungen hin:

Sie benötigen eine Karte (Modellbasiert): Viele Methoden erfordern, dass die KI zuerst eine perfekte Karte der Welt erstellt. Wenn die Karte falsch ist, scheitert der Plan.
Sie sind langsam und theoretisch: Einige Methoden funktionieren zwar in der Theorie, brauchen aber ewig, um zu lernen, oder sie garantieren Erfolg erst nach unendlicher Zeit (asymptotisch), was bei begrenzten Daten nicht hilfreich ist.

Die Lösung: Robust Halpern Iteration (RHI)

Die Autoren schlagen einen neuen Algorithmus namens Robust Halpern Iteration (RHI) vor. So funktioniert er, unterteilt in drei einfache Konzepte:

1. Das „Black-Box“-Orakel (Der magische Geschmackstester)

In der realen Welt kennt die KI die genauen Regeln des Spiels nicht. Sie verfügt nur über ein „generatives Modell“ – einen Simulator, den sie Fragen stellen kann.

Die Herausforderung: Um robust zu sein, muss die KI das schlechteste Ergebnis eines Zuges kennen. Aber der Simulator zeigt nur das durchschnittliche Ergebnis.
Die Lösung: Die Autoren haben ein „Black-Box-Orakel“ geschaffen (ein Werkzeug, das sie R-SAMPLE nennen). Denken Sie an einen Super-Geschmackstester. Wenn man ihm ein Rezept gibt (einen Zug), schmeckt er nicht nur den durchschnittlichen Geschmack, sondern simuliert tausende Variationen (scharf, fad, verbrannt) und sagt einem den Geschmack der schlechtesten möglichen Version. Dies ermöglicht es der KI zu lernen, ohne die genauen Regeln der Welt im Voraus kennen zu müssen.

2. Der „Quotientenraum“ (Das Rauschen ignorieren)

Die Mathematik hinter durchschnittlichen Belohnungen ist knifflig, da es zwei Unbekannte gibt: den Wert des Zuges und die langfristige durchschnittliche Punktzahl. Es ist, als versuche man, eine Gleichung mit zwei fehlenden Zahlen zu lösen.

Die Lösung: Die Autoren nutzen einen mathematischen Trick namens Quotientenraum. Stellen Sie sich vor, Sie messen den Höhenunterschied zwischen zwei Bergen. Es spielt keine Rolle, ob Sie von der Meereshöhe oder vom Erdmittelpunkt aus messen; der Unterschied bleibt derselbe. Sie ignorieren die „absolute Höhe“ (den unbekannten Durchschnitt) und konzentrieren sich nur auf den „Unterschied“ (den relativen Wert). Dies vereinfacht die Mathematik so sehr, dass das Rätsel gelöst werden kann.

3. Der „K-Order Multi-Level Monte-Carlo“ (Der intelligente Schätzer)

Dies ist die wichtigste technische Innovation der Arbeit. Um diesen „Worst-Case“-Geschmack vom Geschmackstester zu erhalten, müssen viele Simulationen durchgeführt werden.

Der alte Weg: Frühere Methoden waren wie der Versuch, die durchschnittliche Größe einer Menge zu erraten, indem man eine Person, dann zwei, dann drei misst. Sie waren langsam und hatten oft einen „Bias“ (einen systematischen Fehler), wie zum Beispiel immer etwas zu groß zu schätzen.
Der neue Weg: Die Autoren haben einen K-Order Multi-Level Monte-Carlo (MLMLC) Schätzer entwickelt.
- Analogie: Stellen Sie sich vor, Sie möchten die Durchschnittstemperatur eines Sees ermitteln.
  - Level 1: Sie machen ein schnelles, grobes Eintauchen mit der Hand (geringer Aufwand, hoher Fehler).
  - Level 2: Sie nehmen eine präzisere Messung mit einem Thermometer vor (mittlerer Aufwand, mittlerer Fehler).
  - Level K: Sie verwenden einen hochtechnologischen Satellitensensor (hoher Aufwand, geringer Fehler).
- Die „K-Order“-Methode kombiniert diese verschiedenen Ebenen geschickt. Sie nimmt die billigen, groben Schätzungen und subtrahiert die Fehler, die sie mit den teuren, präzisen Schätzungen teilen. Das Ergebnis? Eine super-genaue Schätzung, die sehr wenig kostet. Dies reduziert den „Bias“ (Fehler) erheblich und ermöglicht es der KI, viel schneller zu lernen.

Die Ergebnisse: Schnell und effizient

Die Arbeit beweist, dass ihre neue Methode (RHI) unglaublich effizient ist.

Sample Complexity (Stichprobenkomplexität): Dies ist eine schicke Art zu sagen: „Wie oft muss die KI den Simulator um Hilfe bitten?“
Die Behauptung: Ihre Methode benötigt etwa so viele Stichproben wie die besten theoretischen Methoden, die tatsächlich über eine perfekte Karte der Welt verfügen.
Warum das wichtig ist: Sie haben dies ohne eine Karte erreicht (Model-Free). Sie haben das Worst-Case-Szenario direkt aus den Daten gelernt, indem sie ihren intelligenten „K-Order“-Schätzer nutzten, um das Rauschen zu bereinigen.

Zusammenfassung in einem Satz

Die Autoren haben einen neuen Weg erfunden, um KIs das „lange Spiel“ in unsicheren Umgebungen beizubringen, indem sie einen intelligenten, Bias-korrigierenden Schätzer verwenden, der es der KI ermöglicht, die Worst-Case-Szenarien direkt aus Daten zu lernen, ohne zuerst eine perfekte Karte der Welt erstellen zu müssen.

Technisches Resümee: Modellfreies robustes Average-Reward Reinforcement Learning mit Analyse der Stichprobenkomplexität

1. Problemformulierung

Die Arbeit adressiert die Herausforderung des robusten Reinforcement Learning (RL) unter dem Average-Reward-Kriterium. Während RL in kontrollierten Umgebungen Erfolge erzielt hat, leidet der Einsatz in der realen Welt oft unter der „Sim-to-Real“-Lücke aufgrund von Modellabweichungen, Umgebungsschwankungen oder adversariellen Angriffen. Robustes RL mildert dies ab, indem es die Worst-Case-Performance innerhalb einer Unsicherheitsmenge von Übergangsdynamiken optimiert.

Der spezifische Fokus liegt auf distributionsrobustem Average-Reward MDPs (RAMDPs). Im Gegensatz zu den diskontierten Belohnungsszenarien ist das Average-Reward-Kriterium für die langfristige stationäre Performance in Anwendungen wie der Warteschlangenkontrolle oder der Portfolio-Optimierung essenziell. Das robuste Average-Reward RL ist jedoch signifikant anspruchsvoller als das diskontierte Gegenstück, und zwar aufgrund von:

Nicht-kontraktiven Operatoren: Der robuste Bellman-Operator ist im Allgemeinen nicht-expansiv statt kontraktiv, was Standard-Konvergenzgarantien iterativer Verfahren ungültig macht.
Dualen Unbekannten: Die robuste Bellman-Gleichung beinhaltet zwei unbekannte Variablen: die Wertfunktion (oder den Bias) $Q$ und die optimale durchschnittliche Belohnung $g^*_P$ .
Nichtlinearität: Die Schätzung der Worst-Case-Erwartung (Support-Funktion) aus nominalen Stichproben führt zu einem Bias, insbesondere in modellfreien Settings.

Die bestehende Literatur stützt sich weitgehend auf asymptotische Garantien, modellbasierte Ansätze, die Vorwissen über die Problemparameter (wie die Bias-Span $H$ ) erfordern, oder Reduktionsmethoden, die eine suboptimale Stichprobenkomplexität aufweisen oder starke strukturelle Annahmen (z. B. Irreduzibilität mit spezifischen Kontraktionskoeffizienten) verlangen.

2. Methodik: Robust Halpern Iteration (RHI)

Die Autoren schlagen die Robust Halpern Iteration (RHI) vor, einen modellfreien Algorithmus, der darauf ausgelegt ist, die robuste Bellman-Gleichung ohne die Notwendigkeit von Vorwissen über die MDP-Parameter zu lösen.

2.1. Algorithmischer Kern

Der RHI-Algorithmus ist von der Halpern-Iteration aus der Optimierungsliteratur inspiriert und wurde angepasst, um die spezifischen Herausforderungen des robusten Average-Reward RL zu bewältigen:

Quotientenraum-Formulierung: Um das Problem der „dualen Variablen“ (die unbekannte $g^*_P$ ) zu adressieren, betten die Autoren das Problem in einen Quotientenraum $\mathbb{R}^{SA} / \sim$ ein, in dem Vektoren, die sich nur durch eine Konstante unterscheiden, als äquivalent gelten. Dies ermöglicht es dem Algorithmus, die proximale Gleichung $T_P(Q) - Q = ce$ zu lösen, ohne $g^*_P$ explizit kennen zu müssen.
Halpern-Update: Anstelle der Standard-Wertiteration verwendet RHI eine konvexe Kombination aus der Initialisierung und dem Operator-Update:
$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$
wobei $\beta_k = k/(k+2)$ . Dieser Ansatz bietet Konvergenzgarantien für nicht-expansive Operatoren, ohne auf Kontraktionskoeffizienten angewiesen zu sein.

2.2. Black-Box-Sampling-Oracle (R-SAMPLE)

Da der robuste Operator $T_P$ nichtlinear ist und eine Worst-Case-Erwartung beinhaltet, führen die Autoren ein Black-Box-Sampling-Oracle, R-SAMPLE, ein. Dieses Oracle schätzt die Differenz zwischen robusten Support-Funktionen aufeinanderfolgender Iterationen unter Verwendung lediglich von Stichproben aus dem nominalen Kernel.

Das Oracle liefert ein zufälliges Inkrement $D_k$ , dessen Erwartungswert die Differenz der Werte des robusten Bellman-Operators approximiert.
Die Stichprobenkomplexität des Algorithmus wird basierend auf den Eigenschaften dieses Oracles (Lipschitz-Konstante, Bias und Stichprobenkosten) abgeleitet.

2.3. K-Order Multi-Level Monte-Carlo (MLMC) Schätzer

Um das R-SAMPLE-Oracle konkret mit geringem Bias zu implementieren, schlagen die Autoren einen K-Order MLMC-Schätzer vor.

Motivation: Standardmäßige Plug-in-Schätzer und gewöhnliche MLMC-Schätzer für robuste Support-Funktionen leiden unter einem $O(1/N)$ -Bias, was zu einer Stichprobenkomplexität von $\tilde{O}(\epsilon^{-3})$ führt.
Mechanismus: Der K-Order-Schätzer konstruiert eine Linearkombination von Single-Level-Schätzern bei unterschiedlichen Stichprobengrößen ( $N_\ell = 2^\ell N_0$ ). Durch die sorgfältige Wahl der Gewichte $w^{(K)}_\ell$ eliminiert der Schätzer die ersten $K$ Terme der Bias-Expansion.
Ergebnis: Dies reduziert den Bias auf $\tilde{O}(N_0^{-(K+1)})$ und ermöglicht so eine wesentlich engere Stichprobenkomplexität.

3. Zentrale Beiträge

Ein universeller modellfreier Algorithmus: RHI ist der erste modellfreie Algorithmus für robustes Average-Reward RL, der kein Vorwissen über die robuste optimale Span $H$ oder die Mischzeit benötigt und somit die Einschränkungen reduktionsbasierter Ansätze umgeht.
K-Order MLMC-Schätzer: Die Autoren entwerfen einen neuartigen Schätzer, der den Bias im Vergleich zu bisherigen MLMC-Methoden signifikant reduziert. Dies ist entscheidend, um eine nahezu optimale Stichprobenkomplexität in Gegenwart nichtlinearer robuster Support-Funktionen zu erreichen.
Finite-Sample-Komplexitätsanalyse: Die Arbeit liefert eine rigorose Finite-Sample-Analyse für RHI unter einer generativen Modell-Einstellung.
- Für KL- und $\chi^2$ -Divergenz-Unsicherheitsmengen beträgt die Stichprobenkomplexität zur Auffindung einer $\epsilon$ -optimalen Policy $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$ .
- Für $\ell_p$ -Norm- und Kontaminations-Sets beträgt die Komplexität $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$ .
- Hierbei sind $S$ und $A$ die Anzahl der Zustände und Aktionen, und $H$ ist die robuste optimale Bias-Span.
Parameterfreies Variant (PF-RHI): Die Autoren schlagen eine Variante von RHI vor, die einen Doubling-Trick verwendet, um die Anzahl der Iterationen dynamisch zu bestimmen. Dies entfernt die Notwendigkeit, den Horizont basierend auf dem unbekannten Parameter $H$ vorab festzulegen, während die gleiche Stichprobenkomplexität beibehalten wird.

4. Ergebnisse und theoretische Garantien

Konvergenz: Es wird bewiesen, dass der exakte RHI-Algorithmus asymptotisch konvergiert, wobei die Span der Bellman-Residuen und die Suboptimalitätslücke mit zunehmender Anzahl der Iterationen gegen Null gehen.
Stichprobenkomplexität: Die abgeleitete Stichprobenkomplexität für KL- und $\chi^2$ -Sets stimmt asymptotisch mit den besten bekannten Bounds für modellbasierte Ansätze überein (z. B. Roch et al., 2025; Chen et al., 2025). Der $o(1)$ -Term im Exponenten stellt eine sub-polynomiale Strafe dar, die mit $\epsilon \to 0$ verschwindet, was sie von der $\epsilon^{-3}$ -Komplexität von Methoden unterscheidet, die Standard-MLMC verwenden.
Experimentelle Validierung: Numerische Experimente zum Garnet-Problem und zu verschiedenen Unsicherheitsmengen (Kontamination, $\ell_\infty$ , $\ell_2$ ) zeigen, dass RHI zur optimalen robusten durchschnittlichen Belohnung konvergiert und dass der K-Order MLMC-Schätzer den Bias im Vergleich zu Standardmethoden effektiv reduziert.

5. Bedeutung und Ansprüche

Die Arbeit beansprucht, RHI als den State-of-the-Art Modell-freien Algorithmus für robustes Average-Reward RL zu etablieren. Ihre Bedeutung liegt in:

Überbrückung der Lücke: Sie schließt die Lücke zwischen asymptotischen Garantien und Finite-Sample-Analysen im robusten Average-Reward RL.
Praktikabilität: Da der Algorithmus modellfrei ist und kein Vorwissen über $H$ erfordert, ist er praktikabler für den realen Einsatz, in dem solche Parameter unbekannt sind.
Optimalität: Die Stichprobenkomplexität entspricht asymptotisch den engsten bekannten Bounds für modellbasierte Methoden, was zeigt, dass modellfreie Ansätze eine ähnliche Effizienz ohne den Overhead der Modellkonstruktion erreichen können.
Bias-Reduktion: Das Design des K-Order MLMC bietet eine fundamentale Verbesserung gegenüber bisherigen robusten RL-Schätzern und löst das Problem der hohen Stichprobenkomplexität, die durch unkorrigierten Bias bei der Schätzung nichtlinearer Funktionen entsteht.

Die Autoren merken an, dass ihre Analyse ein generatives Modell (Zugriff auf einen Simulator) voraussetzt, um die statistische Komplexität isoliert zu betrachten. Erweiterungen auf Online- (Exploration-Exploitation) oder Offline-Settings (datengesteuert) werden als zukünftige Arbeiten identifiziert. Zudem wird die sub-polynomiale Lücke in der Stichprobenkomplexität für KL/ $\chi^2$ -Sets auf den inhärenten Bias-Variance-Tradeoff bei der Schätzung nichtlinearer Funktionale zurückgeführt, was eine offene Herausforderung bleibt, um diesen in modellfreien Settings vollständig zu eliminieren.