A Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

Technische Samenvatting: Een Theorie voor Eindige Iteraties voor Asynchrone Categorieel-Distributieel Temporaal-Differentie Leren

Probleemstelling
Recente vooruitgang in distributieel versterkend leren (RL) heeft sterke asymptotische garanties vastgesteld voor categorische beleidsevaluatiemethoden, specifiek scalair categorisch temporaal-differentie (CTD) leren in de Cramèrmetriek en multivariate getekend-categorisch temporaal-differentie (MTD) leren in de maximum mean discrepancy (MMD)-metriek. Echter, bestaande niet-asymptotische (eindige iteratie) analyses richten zich grotendeels op synchrone updates voor volledige toestanden, generatieve modellen of geïdealiseerde surrogaten. In praktische online RL-omgevingen werkt standaard categorisch TD-leren asynchroon: het voert per iteratie updates voor een enkele staat uit, gedreven door een Markoviaanse trajectorie. Dit creëert een theoretische kloof tussen de gevestigde asymptotische theorie en het gedrag bij eindige iteraties van de exacte recursies die in de praktijk worden gebruikt. Dit artikel adresseert deze kloof door eindige-iteratiegaranties te bieden voor asynchroon CTD en MTD onder zowel afgekapte als niet-afgekapte regimes met een vaste horizon.

Methodologie
De auteurs overbruggen de kloof tussen praktische asynchrone updates en de theorie van stochastische benadering (SA) bij eindige iteraties via een unifyend raamwerk gebaseerd op isometrische embeddings per staat en block-supremum-geometrie.

1. Isometrische Embeddings en Contractie:

   • Voor CTD maken de auteurs gebruik van de Cramèrmetriek en een isometrische embedding van cumulatieve massa ($I_C$). Dit transformeert de geprojecteerde Bellman-operator in een contractie in een block-supremum-norm ($\|\cdot\|_{2,\infty}$) met modulus $\sqrt{\gamma}$ (afgekapte) of een gewogen contractie (vaste horizon).
   • Voor MTD hanteren zij de MMD-metriek met een karakteristieke kern en een Gram-matrix-embedding ($I_M$). Dit converteert de geprojecteerde Bellman-afbeelding op vergelijkbare wijze in een contractie in de block-supremum MMD-geometrie, met modulus $\gamma^{c/2}$ (afgekapte) of een gewogen contractie (vaste horizon).

2. Formulering van Asynchrone Stochastische Benadering (SA):

   • De standaard regel voor updates per enkele staat wordt herschreven als een asynchrone SA-recursie: $U_{k+1} = U_k + \alpha_k P_{S_k}(\hat{T}(U_k; S_k, \xi_k) - U_k(S_k))$.
   • De analyse steunt op abstracte raamwerken voor eindige iteraties voor contractieve recursies onder i.i.d. en Markoviaanse bemonstering (opbouwend op Chen et al., Robbins-Monro en Borkar).
   • Perturbatie-geometrie: Er wordt een kritisch onderscheid gemaakt tussen de ruisstructuren van de twee methoden. CTD opereert in een regime met gebonden ruis vanwege de gebonden steun van categorische verdelingen en de Cramèr-geometrie. Daarentegen opereert MTD in een regime met affiene perturbatie omdat de getekend-categorische projectie affien is in plaats van uniform gebonden, wat leidt tot perturbatiegrenzen die schalen met de norm van de huidige iteratie.

3. Geanalyseerde Regimes:

   • Afgekapte Beleidsevaluatie: Geanalyseerd onder zowel i.i.d. bemonstering (replay/generatief model) als Markoviaanse trajectoriebemonstering (standaard online RL). Het Markoviaanse geval omvat grenzen voor de geometrische mengtijd.
   • Niet-afgekapte Evaluatie met Vaste Horizon: Geanalyseerd voor episodische taken met een vaste horizon $H$. Aangezien er geen afkappingsfactor $\gamma < 1$ is om contractie te drijven, introduceren de auteurs een gewogen block-metriek ($\lambda^h$) over de horizonstapel. Dit herstelt een contractie-eigenschap waarbij horizon $h$ bootstrapt vanuit $h-1$. De analyse wordt uitgevoerd op episodegrenzen om fase-afhankelijke drift binnen een episode te behandelen.

Belangrijkste Bijdragen

1. Garanties voor Eindige Iteraties voor Asynchroon CTD en MTD: Het artikel vestigt expliciete niet-asymptotische convergentiesnelheden voor de standaard asynchrone recursies van zowel CTD als MTD. Dit is de eerste dergelijke theorie voor deze specifieke methoden onder updates voor een enkele staat, gedreven door trajectoires.
2. Unifyend Raamwerk voor Afgekapte en Vaste-Horizon Regimes: De auteurs bieden een coherent theoretisch behandelingskader dat zowel afgekapte problemen (met i.i.d. en Markoviaanse bemonstering) als niet-afgekapte problemen met vaste horizon (onder i.i.d. episodische bemonstering) bestrijkt.
3. Deterministische Representatiefout-decompositie: Het artikel registreert een decompositie die de totale fout scheidt in een algoritmische term (gecontroleerd door de grenzen voor eindige iteraties) en een deterministische projectie-bias-term (afhankelijk van de familie van categorische steunpunten). Dit maakt het mogelijk de SA-analyse en de discretisatiebias onafhankelijk van elkaar te analyseren.
4. Expliciete Constanten en Stapgrootte-regimes: De analyse biedt expliciete constanten voor drie regimes voor stapgroottes:
   • Constante stapgrootte: Geometrische convergentie naar een $O(\alpha)$-omgeving.
   • Lineair afnemende stapgrootte: Leidend tot residuale afname van $O(1/k)$ (kwadratische fout), wat impliceert dat de steekproefcomplexiteit $O(\epsilon^{-2})$ is voor een gemiddelde fout $\epsilon$.
   • Polynomaal afnemende stapgrootte: Afname van $O(1/k^z)$, waarbij de convergentiesnelheid wordt geruild voor mildere toelaatbaarheidsvoorwaarden.

Resultaten

• Afgekapte Regime: Voor zowel CTD als MTD convergeert de kwadratische fout onder i.i.d. bemonstering met een snelheid van $O(1/k)$ bij lineair afnemende stapgroottes. Onder Markoviaanse bemonstering is de snelheid $\tilde{O}(1/k)$, met een logaritmische overhead als gevolg van de mengtijd van de onderliggende Markovketen.
• Regime met Vaste Horizon: Voor niet-afgekapte episodische taken convergeert de fout op episodegrenzen met snelheden analoog aan het afgekapte geval. Specifiek: $O(1/m)$ convergentie voor kwadratische fout na $m$ episodes (equivalent aan $O(\epsilon^{-2})$ overgangen).
• Ruisregimes: De resultaten bevestigen dat CTD profiteert van uniform gebonden ruis, terwijl MTD omgaan moet met affiene ruisgrenzen, wat extra constanten introduceert die gerelateerd zijn aan de norm van de iteratie in de convergentiegaranties.

Betekenis en Beweringen
Het artikel claimt een aanzienlijke theoretische kloof te overbruggen tussen het asymptotische begrip van distributieel RL en de praktische, asynchrone updates voor een enkele staat die in implementaties worden gebruikt. Door aan te tonen dat standaard categorische recursies asynchrone SA-schema's vormen met contractieve structuren in geschikte embeddings, stellen de auteurs rigoureuze controle bij eindige iteraties mogelijk.

De auteurs merken bescheiden de reikwijdte van hun werk op:

• De theorie is beperkt tot tabulaire, eindige-staat beleidsevaluatie en adresseert geen controle of beleidsverbetering.
• De garanties zijn verwachtingsgrenzen in plaats van grenzen met hoge waarschijnlijkheid.
• De resultaten zijn van toepassing op de exacte asynchrone recursies die in de praktijk worden gebruikt, en onderscheiden zich van eerder werk dat synchrone of modelgebaseerde surrogaten analyseerde.

Het werk stelt vast dat zodra CTD en MTD zijn geformuleerd met de passende embeddings per staat, hun update-regels de nodige structurele eigenschappen bezitten (contractie, Lipschitz-continuïteit en gecontroleerde perturbatie) om te worden geanalyseerd met moderne niet-asymptotische SA-tools, waarmee de eerste theorie voor eindige iteraties wordt geboden voor deze veelgebruikte distributieel methoden in realistische online omgevingen.