Technische Samenvatting: Natuurlijk Beleidsgradient als Dubbel Gesmoothde Beleiditeratie

Probleemstelling

Problemen in versterkend leren (RL) worden doorgaans gemodelleerd als Markov-beslissingsprocessen (MDP's). Waar klassieke methoden voor dynamische programmering, zoals Beleiditeratie (PI) en Waardeiteratie (VI), vertrouwen op de contractie- en monotonie-eigenschappen van de Bellman-operator, worden moderne op gradiënten gebaseerde methoden zoals Natuurlijk Beleidsgradient (NPG) en Beleid-Dual Averaging (PDA) vaak geanalyseerd door de lens van continue optimalisatie over de beleidsruimte.

Er bestaat een conceptuele kloof in de literatuur: analyses van NPG maken vaak geen gebruik van de fundamentele contractie in de $\ell_\infty$-norm van de Bellman-operator, die de basis vormt voor de sterke convergentiegaranties van klassieke methoden. Bijgevolg lijden bestaande theoretische resultaten voor NPG vaak aan een of meer beperkingen:

1. Gebrek aan globale geometrische convergentie.
2. Afhankelijkheid van initiële verdelingen van toestanden of concentrabiliteitscoëfficiënten.
3. Vereiste voor extra regularisatie van het MDP of het algoritme om kromte te induceren.
4. Verantwoording op adaptieve, traject-afhankelijke stapgroottes.

Het artikel beoogt deze kloof te overbruggen door een unificerend kader te bieden dat klassieke PI verbindt met moderne op gradiënten gebaseerde methoden, waardoor een distributie-vrije, geometrische convergentieanalyse mogelijk wordt zonder het MDP te wijzigen of adaptieve stappen te vereisen.

Methodologie: Dubbel Gesmoothde Beleiditeratie (DSPI)

De auteurs introduceren Dubbel Gesmoothde Beleiditeratie (DSPI), een unificerend algoritmisch kader geformuleerd als een Bellman-operatorkader. DSPI werkt het beleid bij via een geregulariseerde greedy-stap die wordt toegepast op een gewogen gemiddelde van eerdere Q-functies.

De kern van DSPI omvat twee niveaus van smoothing:

1. Averaging Smoothing: In plaats van alleen de meest recente Q-functie te gebruiken, onderhoudt het algoritme een lopend gemiddelde ($\bar{Q}_k$) van alle eerdere Q-functies.
2. Regularization Smoothing: De greedy-beleidsupdate wordt vervangen door een geregulariseerde stap (bijvoorbeeld softmax) die een concaaf functie $\nu(\cdot)$ (zoals entropie) omvat.

De update-regel is gedefinieerd als:
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
waarbij $\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$, en de smoothing-parameter $\eta_k$ geometrisch afneemt op basis van de stapgroottes $\beta_k$.

Cruciaal tonen de auteurs aan dat DSPI een compacte formulering toestaat met behulp van gesmoothde Bellman-operatoren ($H_\eta$ en $H^\pi_\eta$). Dit stelt het algoritme in staat geanalyseerd te worden met behulp van de monotonie- en contractie-eigenschappen van deze operatoren, in plaats van uitsluitend te vertrouwen op optimalisatietheoretische hulpmiddelen.

Belangrijkste Bijdragen

1. Unificatie van Algoritmen

Het artikel stelt vast dat DSPI een algemeen kader is dat meerdere belangrijke algoritmen als speciale gevallen omvat:

• Beleiditeratie (PI): Hersteld wanneer de stapgrootte $\beta_k \equiv 1$ (geen averaging) en regularisatie verdwijnt.
• Natuurlijk Beleidsgradient (NPG): Hersteld door $\nu(\cdot)$ in te stellen op de Shannon-entropie en specifieke schema's voor stapgroottes te kiezen.
• Beleid-Dual Averaging (PDA): Hersteld door $\nu(\cdot)$ te kiezen als een verschoven negatieve divergentie-genererende functie.
• Dual-Averaged Beleiditeratie: Een nieuwe variant waarbij het beleid bijgewerkt wordt op basis van de gemiddelde Q-functies ($\nu(\cdot) \equiv 0$).

2. Unificerend Convergentie-analyse

Door gebruik te maken van de eigenschappen van de gesmoothde Bellman-operatoren, bieden de auteurs een unificerende convergentieanalyse voor DSPI:

• Asymptotische Convergentie: Bewezen voor elke niet-opsommbare reeks stapgroottes.
• Globale Geometrische Convergentie: Bewezen voor constante stapgroottes. De foutgrens wordt gegeven door:
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  waarbij $\gamma$ de disconteringsfactor is en $\beta$ de constante stapgrootte.

3. Verbeterde Theoretische Garanties voor NPG en PDA

Het toepassen van het DSPI-kader op NPG en PDA levert de volgende resultaten op, die de state-of-the-art verbeteren of evenaren zonder restrictieve aannames te vereisen:

• Distributie-vrij: De convergentiegrenzen hangen alleen af van de $\ell_\infty$-norm van de waardenfunctie-gap, niet van de initiële verdeling van toestanden of concentrabiliteitscoëfficiënten.
• Geen Extra Regularisatie: De analyse geldt zonder het MDP te wijzigen of extra regularisatoren toe te voegen buiten de entropieterm die inherent is aan standaard NPG.
• Eenvoudige Stapgroottes: De resultaten gelden voor een eenvoudige, vooraf gespecificeerde geometrisch toenemende schema voor stapgroottes ($\alpha_k = \beta \alpha_0 / (1-\beta)^k$), waardoor de noodzaak voor adaptieve stapgroottes die afhankelijk zijn van het beleids-traject of de Bellman-fout, wordt geëlimineerd.
• Iteratiecomplexiteit: NPG en PDA bereiken een $\epsilon$-optimaal beleid in $O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$ iteraties.

4. Eindige Terminatie van Dual-Averaged PI

Voor het niet-geregulariseerde geval (Dual-Averaged PI) bewijzen de auteurs eindige terminatie. Het algoritme vindt een optimaal beleid in ten hoogste $O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$ iteraties, waarbij $n$ en $m$ de grootte zijn van de toestands- en actieruimten. Dit wordt bereikt door aan te tonen dat het algoritme elke $k^*$ iteraties ten minste één suboptimaal actie elimineert.

5. Uitbreidingen

Het kader blijkt zich op natuurlijke wijze uit te breiden tot:

• Lineaire Functiebenadering: DSPI met lineaire functiebenadering bereikt geometrische convergentie tot op een term voor fout in functiebenadering.
• Stochastisch Kortste Pad (SSP) Problemen: De analyse strekt zich uit tot niet-gedisconteerde SSP-problemen, waarbij distributie-vrije globale geometrische convergentie wordt vastgesteld onder de aanname dat alle stationaire beleidsplannen correct zijn.

Resultaten en Betekenis

Het artikel stelt dat de primaire betekenis ligt in het bieden van een unificerend perspectief dat klassieke dynamische programmering verbindt met modern op gradiënten gebaseerd RL. Door NPG en PDA te interpreteren als gesmoothde en gemiddelde varianten van Beleiditeratie, zijn de auteurs in staat om:

1. Sterke Garanties te Herstellen: Globale geometrische convergentie voor NPG en PDA vast te stellen met uitsluitend de intrinsieke eigenschappen van de Bellman-operator (monotonie en contractie).
2. Artifacts te Verwijderen: De noodzaak voor "kromte-inducerende" regularisatie of adaptieve stapgroottes die vaak vereist waren in eerdere optimalisatie-gebaseerde analyses, te elimineren.
3. Analyse te Vereenvoudigen: Een eenvoudigere, meer principieel onderbouwde analyse te bieden die de complexiteiten van distributie-mismatch-coëfficiënten vermijdt.

De auteurs merken op dat, hoewel hun huidige analyse uitgaat van toegang tot exacte Q-functies (waarbij de dynamiek van beleidsverbetering geïsoleerd wordt), het kader de basis legt voor toekomstig werk in model-vrije omgevingen waar Q-functies moeten worden geschat. Zij identificeren de combinatie van DSPI met garanties voor beleids-evaluatie in eindige tijd als een niet-triviale volgende stap om scherpe resultaten voor sample-complexiteit te bereiken voor model-vrij RL.