Technische Samenvatting: Een enkele stapgrootte volstaat voor ongeprojecteerde lineaire TD(0)

Probleemstelling

Het artikel behandelt de eindige-tijd, hoge-waarschijnlijkheid convergentieanalyse van lineair Temporal Difference leren met nul-bias (TD(0)) onder Markoviaanse bemonstering. In deze setting worden gegevens gegenereerd langs een enkel traject van een Markov-keten in plaats van als onafhankelijke en identiek verdeelde (i.i.d.) steekproeven.

De kernuitdaging ligt in het feit dat TD(0) geen standaard stochastische gradiëntmethode is; de updates zijn vertekend (biased), niet-symmetrisch en de ruis is temporeel gecorreleerd. Bovendien hangt de omvang van de update af van de omvang van de huidige iteraten. Bestaande niet-asymptotische analyses vertrouwen doorgaans op één van de twee restrictieve benaderingen:

1. Projecties: Het afdwingen van begrensdheid door iteraten te projecteren op een bekende bol. Dit vereenvoudigt concentratie-argumenten maar verandert het algoritme en vereist voorafgaande kennis van een geschikte straal (vaak gekoppeld aan de kromming van het probleem).
2. Kromming-afhankelijke stabiliteit: Het exploiteren van de contractieve aard van de gemiddelde dynamica om stabiliteit te beargumenteren zonder projecties. Dit levert echter doorgaans stapgroottevoorwaarden of stabiliteitsgrenzen op die afhankelijk zijn van een onbekende krommingsparameter ($\omega$). Wanneer $\omega$ klein is, worden deze grenzen willekeurig traag, en kan de stapgrootte niet onafhankelijk van $\omega$ worden gekozen.

De auteurs streven ernaar om een enkele stapgrootte-schema vast te stellen die onafhankelijk is van de krommingsparameter $\omega$ en geen projecties vereist, maar tegelijkertijd garandeert:

• Robuustheid: Een convergentiesnelheid van $\tilde{O}(1/\sqrt{T})$ die standhoudt ongeacht $\omega$.
• Snelheid: Een convergentiesnelheid van $\tilde{O}(1/(\omega T))$ die gunstige kromming benut wanneer deze aanwezig is.

Methodologie

1. Zelf-begrenzend argument via Poisson-vergelijkingen

De centrale technische vernieuwing is een nieuw "zelf-begrenzend" inductief argument dat de padgebondenheid van de iteraten $\theta_t$ controleert zonder te vertrouwen op kromming $\omega$ of kunstmatige projecties.

• De Lus: Een naïeve concentratieanalyse is circulair: het begrenzen van de fout vereist begrensde updates, maar begrensde updates vereisen begrensde iteraten.
• De Oplossing: De auteurs deconstrueren de Markov-ruis met behulp van de Poisson-vergelijking geassocieerd met de geometrisch mengenende Markov-keten. Voor een gecentreerde forceringsterm $h$ lossen zij $u - P_Z u = \tilde{h}$ op.
• Decompositie: Dit maakt het mogelijk om de accumulatie van Markov-ruistermen te deconstrueren in een martingaalterm ($M_t$) en een gecontroleerde restterm ($R_t$).
• Inductie: Zij stellen een inductieve hypothese vast waarbij de begrensdheid van iteraten tot tijd $t-1$ de begrensdheid op tijd $t$ impliceert. Door de martingaalterm te controleren via Pinelis' ongelijkheid en de restterm via de Lipschitz-eigenschappen van de Poisson-oplossing, bewijzen zij dat de iteraten met hoge waarschijnlijkheid uniform begrensd blijven, onafhankelijk van $\omega$.

2. Polyak–Ruppert (PR) Averaging

Het artikel analyseert de Polyak–Ruppert gemiddelde iteratie $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$, waarbij $S_T = \sum \eta_{t-1}$.

• Zodra de uniforme begrensdheid van $\theta_t$ is vastgesteld, kunnen de auteurs de kwadratische variatie van de martingaaltermen en de bias-termen in de convergentieanalyse controleren.
• Zij leiden twee verschillende bovenmatige grenzen af voor de potentiaalfunctie-fout $f(\bar{\theta}_T) - f(\theta^*)$:
  • Een robuuste grens afgeleid van een klassieke gemiddelde stochastische gradiëntafdaling analyse, wat een $\tilde{O}(1/\sqrt{T})$ oplevert.
  • Een snelle grens afgeleid door de evolutie van de fout $e_t = \theta_t - \theta^*$ te analyseren en de positief-definietheid van het symmetrische deel van de TD-matrix (kromming $\omega$) te benutten, wat $\tilde{O}(1/(\omega T))$ oplevert.

3. Stapgrootte-schema

Het voorgestelde stapgrootte-schema is:
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
waarbij $c$ een numerieke constante is, $\tau_{\text{mix}}$ de mengtijd is, en $\phi_\infty$ de normen van de features begrenst. Cruciaal is dat dit schema afhankelijk is van de mengtijd, maar niet van de kromming $\omega$.

Belangrijkste Resultaten

1. Hoge-waarschijnlijkheid Begrensdheid (Theorem 4.1)

Onder standaardveronderstellingen (ergodische MRP, full-rank features), zijn de ongeprojecteerde TD(0) iteraten met hoge waarschijnlijkheid ($1-\delta$) uniform begrensd:
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
waarbij $R_{\text{base}}$ afhangt van de initiële fout, de norm van de optimale oplossing en probleemconstanten, maar onafhankelijk is van $\omega$. Dit is het eerste resultaat dat dergelijke begrensdheid aantoont voor ongeprojecteerde TD(0) onder Markoviaanse bemonstering zonder $\omega$ te gebruiken in de stapgrootte of stabiliteitsargumentatie.

2. Gelijktijdige Convergentiesnelheden (Theorem 4.2)

Gebruikmakend van dezelfde stapgrootte en PR-averaging, bereikt het algoritme een hoge-waarschijnlijkheid convergentiesnelheid voor de potentiaalfunctie-fout:
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
Het vervangen van het stapgrootte-schema vertaalt dit naar:

• Robuuste Snelheid: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• Snelle Snelheid: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

De grens past zich automatisch aan aan het minimum van deze twee snelheden zonder voorafgaande kennis van $\omega$.

3. Mixing-vrije Variant (Appendix E)

De auteurs stellen ook een aangepast stapgrootte-schema voor $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ dat geen kennis van $\tau_{\text{mix}}$ vereist. Dit gaat echter gepaard met een dubbel exponentiële afhankelijkheid van $\tau_{\text{mix}}$ in de constanten van de convergentiegrens, specifiek via de initiële prefix-grens $B_{m^*}$.

Betekenis en Claims

Het artikel claimt de eerste te zijn die vaststelt dat lineaire TD(0) met Markoviaanse bemonstering zowel robuuste als snelle hoge-waarschijnlijkheid convergentiesnelheden kan bereiken met een enkele stapgrootte die:

1. Onafhankelijk is van de krommingsparameter $\omega$.
2. Projectievrij is.

De auteurs benadrukken dat eerder werk ofwel projecties vereiste (wat het algoritme verandert), ofwel krommingsafhankelijke stapgroottes vertrouwde (waardoor het faalt wanneer $\omega$ klein is), ofwel alleen verwachtingsgrenzen bood (bijv. Lee en Orabona [2025]) in plaats van hoge-waarschijnlijkheid garanties.

De betekenis ligt in het zelf-begrenzende argument via Poisson-vergelijkingen, wat de circulaire afhankelijkheid tussen de begrensdheid van de iteraten en de omvang van de updates doorbreekt zonder beroep te doen op de contractieve eigenschappen van de gemiddelde dynamica. Dit stelt het algoritme in staat om stabiel te blijven en snel te convergeren, zelfs wanneer de kromming willekeurig klein is, een scenario waarin eerdere projectievrije analyses doorgaans faalden of strategieën voor het weggooien van data vereisten.

Het artikel blijft bescheiden over de afhankelijkheid van de mengtijd $\tau_{\text{mix}}$. Hoewel de snelle snelheid een $\tau_{\text{mix}}^2$ afhankelijkheid heeft (slechter dan de lineaire $\tau_{\text{mix}}$ afhankelijkheid in sommige eerdere projectie- of data-dropping werken), merken de auteurs op dat de optimale afhankelijkheid van $\tau_{\text{mix}}$ in de afwezigheid van projecties en data-dropping een open vraag blijft. Zij erkennen ook dat hun initiële foutterm met een $1/T$ snelheid vervalt in plaats van exponentieel, een gevolg van het vermijden van contractie-gebaseerde argumenten.