Technische Samenvatting: De Kloof Overbruggen tussen Gemiddelde en Gedisconteerde TD-Learning

Probleemstelling

Temporal Difference (TD) learning is een hoeksteen van reinforcement learning, maar de theoretische analyse in de gemiddelde-beloningsetting loopt aanzienlijk achter op de gedisconteerde setting. In het gedisconteerde geval is de Bellman-operator een contractie-afbeelding, wat unieke oplossingen en een rechttoe-rechtaan convergentieanalyse garandeert. Daarentegen is de Bellman-operator in de gemiddelde-beloningsetting niet contractief met betrekking tot enige norm, en is de oplossing voor de bijbehorende Bellman-vergelijking niet uniek (deze is slechts gedefinieerd tot op een additieve constante).

Bestaande literatuur die zich bezighoudt met TD voor gemiddelde beloning, kampt in vergelijking met de gedisconteerde setting met verschillende beperkingen:

1. Beperkende Aannames: Veel methoden vereisen aannames (bijvoorbeeld $\Phi\theta \neq ce$) die de tabulaire setting uitsluiten.
2. Convergentiegaranties: Sommige benaderingen garanderen alleen convergentie naar een van het steekproefpad afhankelijke vast punt of een verzameling, in plaats van een unieke, deterministische oplossing.
3. Afhankelijkheid van Dimensie: Convergentiegrenzen bevatten vaak expliciete factoren van de parameterdimensie $d$.
4. Schaling van Conditiegetal: State-of-the-art steekproefcomplexiteiten vertonen vaak een kwartische afhankelijkheid van het conditiegetal van het probleem ($O(\eta^{-4})$), terwijl de gedisconteerde setting een kwadratische schaling bereikt ($O(\eta^{-2})$).
5. Algoritmische Complexiteit: Het bereiken van betere schaling in eerdere werken vereiste vaak complexe technieken voor variantiereductie (bijvoorbeeld geneste lussen), wat afwijkt van de eenvoud van standaard TD.

Methodologie

De auteurs stellen een nieuwe aanpak voor voor beleidsevaluatie in de gemiddelde-beloningsetting door de oplossing van de Bellman-vergelijking te formuleren als een geconstrueerd optimalisatieprobleem. Het kerninzicht is dat de relatieve waardenfunctie $W^*$ moet voldoen aan een steady-state constrentie ($\mu^\top W^* = 0$).

1. Dubbele-Keten Algoritme

Om de geprojecteerde Bellman-vergelijking $W^* = \Pi T_\pi W^*$ op te lossen, waarbij $\Pi = I - e\mu^\top$, leiden de auteurs een stochastische update-regel af. Een belangrijke uitdaging in stochastische approximatie voor deze setting is het "dubbel-sampling"-probleem: het schatten van de term $\mu\mu^\top(R + W_t)$ vereist de verwachting van een product van stochastische variabelen, wat niet uit één enkele traject kan worden geschat vanwege correlatie.

Om dit op te lossen, introduceren de auteurs een Dubbele-Keten Algoritme dat gebruikmaakt van twee onafhankelijke Markov-ketens ($\{s_t\}$ en $\{\hat{s}_t\}$) in elke iteratie.

• Update-regel: De parameter-vector $\theta_t$ wordt bijgewerkt met twee componenten:
  • $g(s_t, s'_t, \theta_t)$: Schat de standaard TD-foutterm $D(R + P\Phi\theta_t - \Phi\theta_t)$.
  • $f(s_t, \hat{s}_t, \theta_t)$: Schat de constrentie-term $-\mu\mu^\top(R + \Phi\theta_t)$ met behulp van het onafhankelijke steekproef $\hat{s}_t$ om de correlatie te verbreken.
• Lineaire Benadering: De methode generaliseert naar lineaire functiebenadering ($W \approx \Phi\theta$) door de updates te projecteren op de kenmerkruimte.

2. Enkel-Keten Algoritme

Om de rekenkundige overhead van het onderhouden van twee ketens te vermijden, stellen de auteurs een Enkel-Keten Algoritme voor, geïnspireerd op Gradient TD (GTD).

• Mechanisme: In plaats van een tweede onafhankelijke staat $\hat{s}_t$ te stalen, onderhoudt het algoritme een hulpvariabele $w_t$ die de verwachting $E[\phi(s)] = \Phi^\top\mu bijhoudt.
• Update: De term $\phi(\hat{s}_t)$ in de dubbele-keten update wordt vervangen door $w_t$. De variabele $w_t$ wordt bijgewerkt via een aparte stochastische approximatiestap om te convergeren naar $\Phi^\top\mu$.
• Afweging: Hoewel dit de steekproefvereiste vereenvoudigt tot één enkele traject, toont de analyse een iets sterkere afhankelijkheid van het conditiegetal in vergelijking met de dubbele-keten variant.

3. Theoretisch Kader: Gradient Splitting

De convergentieanalyse is gebaseerd op de techniek van gradient splitting [19]. De auteurs tonen aan dat de verwachte update-richting van hun algoritme fungeert als een "gradient splitting" van een specifieke samengestelde kwadratische functie:
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
Dit stelt de auteurs in staat om het algoritme te analyseren met behulp van standaard Stochastic Gradient Descent (SGD) recursietechnieken, ondanks de niet-contractieve aard van de onderliggende Bellman-operator.

Belangrijkste Bijdragen

Het artikel claimt de theoretische kloof tussen TD-learning voor gemiddelde beloning en gedisconteerde TD te overbruggen door gelijktijdig de volgende kenmerken te bereiken:

1. Uniek, Steekproef-onafhankelijk Vast Punt: De voorgestelde algoritmen convergeren bijna zeker naar een enkele, deterministische oplossing $\theta^*$ die onafhankelijk is van de willekeurige traject en initialisatie.
2. Toepasbaarheid op Tabulaire en Lineaire Settings: De analyse geldt voor zowel tabulaire gevallen (waar $\Phi = I$) als lineaire functiebenadering, zonder de beperkende aanname $e \notin \text{span}(\Phi)$ te vereisen.
3. Dimensievrije Grenzen: De convergentiegrenzen bevatten geen expliciete factoren van de dimensie $d$ (behalve die inherent zijn aan $\|\theta^*\|$ of $\|\theta_0\|$).
4. Convergentie van Laatste Iteratie: Resultaten zijn gegarandeerd voor de laatste iteratie, wat overeenkomt met de standaard in gedisconteerde TD, in plaats van te vertrouwen op iteratie-averaging.
5. Verbeterde Schaling van Conditiegetal:
   • Het Dubbele-Keten algoritme bereikt een steekproefcomplexiteit van $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$, waarbij $\eta_1$ een conditiegetal is gedefinieerd als $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$. Dit komt overeen met de kwadratische schaling die wordt gezien in de gedisconteerde setting.
   • Het Enkel-Keten algoritme bereikt $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (kwartisch), wat een verbetering is ten opzichte van sommige eerdere werken, maar iets slechter is dan de dubbele-keten variant.
6. Algoritmische Eenvoud: De kwadratische schaling wordt bereikt zonder variantiereductietechnieken (zoals geneste lussen of periodieke volledige batches), waardoor de eenvoud van gewone TD-updates behouden blijft.

Resultaten

De auteurs bieden een analyse met een eindig aantal steekproeven voor beide algoritmen onder i.i.d. en Markoviaanse steekproefneming, met zowel constante als afnemende stapgroottes.

• Theoretische Grenzen: Stellingen 4.1–4.3 stellen convergentiesnelheden en steekproefcomplexiteiten vast. De dubbele-keten methode komt overeen met de state-of-the-art voor gedisconteerde TD wat betreft parameter-schaling.
• Numerieke Experimenten: De algoritmen zijn getest op 15 tabulaire MDP's uit OpenAI Gym en MO-Gymnasium.
  • De resultaten tonen aan dat de voorgestelde methoden over het algemeen betere prestaties leveren dan eerdere baselines (waaronder [10], [11], [12], [17], [18] en [21]) wat betreft de benaderingsfout ten opzichte van de ware oplossing.
  • De experimenten bevestigen dat de methoden convergeren naar de unieke oplossing, terwijl sommige baselines (die convergeren naar verzamelingen of steekproef-afhankelijke punten) hogere variantie of fout vertonen in de tabulaire setting.

Betekenis

Het artikel claimt aanhoudende theoretische kanttekeningen geassocieerd met de analyse van TD voor gemiddelde beloning op te lossen. Door gebruik te maken van gradient splitting en een twee-keten (of enkel-keten met hulpvariabele) steekproefstrategie, tonen de auteurs aan dat TD voor gemiddelde beloning dezelfde gunstige convergentie-eigenschappen kan bereiken als gedisconteerde TD:

• Uniciteit: Convergentie naar een goed gedefinieerde, unieke oplossing.
• Generaliteit: Toepasbaarheid op tabulaire en lineaire settings zonder beperkende aannames.
• Efficiëntie: Kwantische afhankelijkheid van het conditiegetal zonder de noodzaak van complexe variantiereductiemachinerie.

Dit werk suggereert dat de theoretische moeilijkheden van de gemiddelde-beloningsetting kunnen worden overwonnen door het probleem te herformuleren als een geconstrueerd optimalisatietaken en specifieke steekproefstrategieën te benutten om de niet-contractieve aard van de Bellman-operator aan te pakken.