Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

Technische Samenvatting: Eindige-tijd Convergentie van Distributioneel Robuust Q-Leren met Lineaire Functie-approximatie

Probleemstelling
Het artikel behandelt de uitdaging van het leren van optimale beleidstrategieën in Distributioneel Robuust Reinforcement Learning (DRRL) wanneer de implementatieomgeving verschilt van de trainingsomgeving (de nominale omgeving). Specifiek richt de auteur zich op model-vrij, gedisconteerd robuust Q-leren onder een $(s, a)$-rechthoekige chi-kwadraat onzekerheidsset.

De setting betreft een lerende die opereert op een enkele Markoviaanse traject gegenereerd door een onbekende nominale transitie-kernel $P_0$ en een gedragbeleid $\pi_b$. De lerende heeft geen generatieve toegang (kan niet willekeurige staat-actie paren samplen) en kent $P_0$ niet. Het doel is om de optimale robuuste Q-functie, $Q^\star_\chi$, te leren, die de worst-case gedisconteerde waarde maximaliseert over de onzekerheidsset.

Het probleem presenteert twee gekoppelde moeilijkheden:

1. Functie-approximatie Moeilijkheid: Hoewel de exacte robuuste Bellman-operator een contractie is in $\ell_\infty$, is de geprojecteerde robuuste Bellman-operator geïnduceerd door lineaire functie-approximatie niet bekend als een contractie voor algemene kortingsfactoren $\gamma \in (0, 1)$.
2. Robuuste Schatting Moeilijkheid: De chi-kwadraat robuuste Bellman-update omvat een innerlijke minimalisatie over transitieverdelingen. De duale gradiënt hangt af van conditionele momenten (specifiek het positieve deel van de Bellman-gap en de kwadratische vorm daarvan) die uit een enkele traject geschat moeten worden. Standaard analyses voor tabulair robuust Q-leren of lineair Q-leren laten zich niet direct uitbreiden naar deze setting.

Methodologie
De auteurs stellen Algoritme 1 voor, een multi-stage stochastische benaderingsalgoritme dat een target-netwerk outer loop combineert met een duaal functie-approximatieschema. Het algoritme opereert in outer blocks waarin de target Q-functie bevroren is. Binnen elk block vinden drie stadia plaats:

1. Stadium 1: Duale Optimalisatie met Moment Tracking.
   Het algoritme lost de innerlijke minimalisatie van de chi-kwadraat robuuste Bellman-update op via de scalaire duale vorm. In plaats van een aparte duaal probleem op te lossen voor elk staat-actie paar, wordt de duale variabele $\eta$ lineair benaderd ($\eta_\nu(i) = \psi(i)^\top \nu$).

   • Two-Time-Scale Scheme: De duale variabele $\nu$ wordt bijgewerkt op een trage tijdsschaal, terwijl twee "moment-tracking critics" ($\omega_1, \omega_2$) de vereiste conditionele momenten ($Z_1$ en $Z_2$) op een snellere tijdsschaal schatten.
   • Smoothing: Om de afwezigheid van globale gladheid in de chi-kwadraat duale doelstelling (wat problemen veroorzaakt met Markoviaanse ruis-analyse) aan te pakken, optimaliseren de auteurs een gesmoothde surrogaat-doelstelling met behulp van een instelbare parameter $\tau > 0$. Dit zorgt ervoor dat de duale gradiënt Lipschitz-continu is.
   • Suffix Averaging: De duale iteraties worden suffix-gemiddeld om een stabiele schatting $\bar{\nu}_t$ te verkrijgen.

2. Stadium 2: Fresh Evaluation.
   Voordat de Q-functie wordt bijgewerkt, voert het algoritme een "fresh evaluation" uit van het variantie-achtige moment ($Z_1$) met behulp van de gemiddelde duale parameter $\bar{\nu}_t$. Dit stadium isoleert de schatting van het moment van het optimalisatie-traject, waardoor de accumulatie van bias wordt voorkomen die zou optreden als de Stage 1 critics (die geleerd werden terwijl $\nu$ bewoog) direct zouden worden hergebruikt.

3. Stadium 3: Q-Update.
   Het algoritme voert een trage temporal difference update uit voor de robuuste Q-parameter $\theta$ tegen de vaste, geëvalueerde target afgeleid van de stadia 1 en 2.

Belangrijkste Bijdragen

1. Eindige-tijd Convergentie Garantie: Het artikel biedt de eerste eindige-tijd convergentiebound voor gedisconteerd model-vrij robuust Q-leren met lineaire functie-approximatie vanuit single-trajectory data, zonder restricties op kleine kortingsfactoren op te leggen.
2. Target-Netwerk Analyse voor Robuust RL: De auteurs passen de target-netwerk techniek (gebruikelijk in niet-robuuste deep RL) aan voor de robuuste setting. Door de target Q-functie binnen outer blocks te bevriezen, omzeilen ze de niet-contractiviteit van de geprojecteerde robuuste Bellman-operator, waardoor de analyse kan steunen op de contractie van de ongeprojecteerde operator over de blocks heen.
3. Schaalbare Duale Schatting: Ze introduceren een methode om de duale variabele zelf te benaderen met behulp van een lineaire functieklasse, gekoppeld aan moment-tracking critics. Dit vermijdt de schaalbaarheidsproblemen van het oplossen van onafhankelijke duale problemen voor grote staatruimtes.
4. Smoothing en Bias Controle: Het artikel introduceert een gesmoothde surrogaat voor de chi-kwadraat duale doelstelling. Dit lost het probleem van de niet-Lipschitz continue gradiënt op die inherent is aan de exacte chi-kwadraat formulering, wat strikte eindige-tijd stochastische benadering bounds onder Markoviaanse ruis mogelijk maakt. De auteurs merken expliciet op dat eerdere bewijzen voor tabulair robuust Q-leren met chi-kwadraat onzekerheid vertrouwden op aannames van globale gladheid die niet standhouden; hun bewijs corrigeert deze tekortkoming.

Resultaten
De belangrijkste theoretische resultaat (Theorem 1) vestigt een end-to-end convergentiebound van de vorm:
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
waarbij:

• De eerste term de target-netwerk contractie-error vertegenwoordigt.
• $E_{stat}$ de eindige-steekproef fouten vangt van de Q-update, duale optimalisatie, smoothing bias en fresh evaluation.
• $E_{app}$ de benaderingsfouten vangt door functie-approximatie en smoothing.

Experimenten op de FrozenLake MDP valideren de theorie, waarbij de convergentie naar de robuuste referentiewaarde wordt aangetoond en de trade-off wordt geïllustreerd die wordt geïntroduceerd door de smoothing parameter $\tau$ (een kleinere $\tau$ vermindert bias maar verhoogt variantie/optimalisatiefouten).

Betekenis en Claims
Het artikel claimt de kloof te dichten tussen het empirische succes van robuuste RL-algoritmen en de theoretische garanties die beschikbaar zijn voor hun niet-robuuste tegenhangers. Eerdere werken voor model-vrije robuuste RL waren beperkt tot tabulaire settings, vereisten generatieve toegang, gingen uit van actieve exploratie, of legden restrictieve condities op aan de kortingsfactor.

De auteurs stellen dat hun werk de eerste eindige-tijd convergentie garantie biedt voor gedisconteerd model-vrij robuust Q-leren met lineaire functie-approximatie vanuit single-trajectory data zonder aannames van kleine kortingsfactoren. Bovendien beweren zij dat hun bewijs voor het chi-kwadraat geval (zelfs in de tabulaire limiet) de eerste correcte bewijsvoering voor convergentie lijkt te zijn, aangezien het de afwezigheid van globale gladheid in de duale doelstelling adresseert die eerdere analyses over het hoofd hadden gezien of weg hadden geassumeerd. Het framework wordt gepresenteerd als een analyseerbaar sjabloon dat kan worden uitgebreid naar grootschalige neurale netwerk implementaties.