Riepilogo Tecnico: Un Singolo Step-size è Sufficiente per il TD(0) Lineare Non Proiettato

Definizione del Problema

Il documento affronta l'analisi di convergenza in tempo finito e ad alta probabilità dell'apprendimento Temporal Difference con errore zero (TD(0)) lineare sotto campionamento Markoviano. In questo contesto, i dati sono generati lungo una singola traiettoria di una catena di Markov piuttosto che come campioni indipendenti e identicamente distribuiti (i.i.d.).

La sfida centrale risiede nel fatto che il TD(0) non è un metodo di gradiente stocastico standard; i suoi aggiornamenti sono distorti (biased), non simmetrici e il rumore è temporalmente correlato. Inoltre, l'entità dell'aggiornamento dipende dall'entità delle iterazioni correnti. Le analisi non asintotiche esistenti si affidano tipicamente a uno di due approcci restrittivi:

1. Proiezioni: Imporre la limitatezza proiettando le iterazioni su una sfera nota. Ciò semplifica gli argomenti di concentrazione ma altera l'algoritmo e richiede la conoscenza preventiva di un raggio idoneo (spesso legato alla curvatura del problema).
2. Stabilità Dipendente dalla Curvatura: Sfruttare la natura contrattiva della dinamica media per argomentare la stabilità senza proiezioni. Tuttavia, ciò produce tipicamente condizioni di step-size o limiti di stabilità che dipendono da un parametro di curvatura ignoto ($\omega$). Quando $\omega$ è piccolo, questi limiti diventano arbitrariamente lenti, e lo step-size non può essere scelto indipendentemente da $\omega$.

Gli autori mirano a stabilire uno schema di step-size singolo che sia indipendente dal parametro di curvatura $\omega$ e che non richieda proiezioni, garantendo simultaneamente:

• Robustezza: Un tasso di convergenza di $\tilde{O}(1/\sqrt{T})$ che sia valido indipendentemente da $\omega$.
• Velocità: Un tasso di convergenza di $\tilde{O}(1/(\omega T))$ che sfrutti la curvatura favorevole quando essa esiste.

Metodologia

1. Argomento di Auto-Limitazione tramite Equazioni di Poisson

La centralità della novità tecnica è un nuovo argomento induttivo di "auto-limitazione" (self-bounding) che controlla la limitatezza pathwise delle iterazioni $\theta_t$ senza fare affidamento sulla curvatura $\omega$ o su proiezioni artificiali.

• Il Ciclo: Un'analisi di concentrazione ingenua è circolare: limitare l'errore richiede aggiornamenti limitati, ma aggiornamenti limitati richiedono iterazioni limitate.
• La Soluzione: Gli autori decompongono il rumore Markoviano utilizzando l'equazione di Poisson associata alla catena di Markov a mescolamento geometrico. Per un termine di forza centrato $h$, risolvono $u - P_Z u = \tilde{h}$.
• Decomposizione: Ciò consente che l'accumulo del rumore Markoviano venga decomposto in un termine di martingala ($M_t$) e un termine residuo controllato ($R_t$).
• Induzione: Stabiliscono un'ipotesi induttiva in cui la limitatezza delle iterazioni fino al tempo $t-1$ implica la limitatezza al tempo $t$. Controllando il termine di martingala tramite l'ineguaglianza di Pinelis e il termine residuo tramite le proprietà Lipschitz della soluzione di Poisson, dimostrano che le iterazioni rimangono uniformemente limitate con alta probabilità, indipendentemente da $\omega$.

2. Media di Polyak–Ruppert (PR)

Il documento analizza l'iterata media di Polyak–Ruppert $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$, dove $S_T = \sum \eta_{t-1}$.

• Una volta stabilita la limitatezza uniforme di $\theta_t$, gli autori possono controllare la variazione quadratica dei termini di martingala e i termini di bias nell'analisi della convergenza.
• Derivano due distinti limiti superiori per l'errore della funzione potenziale $f(\bar{\theta}_T) - f(\theta^*)$:
  • Un limite robusto derivato da una classica analisi del gradiente stocastico mediato, che produce $\tilde{O}(1/\sqrt{T})$.
  • Un limite veloce derivato dall'analisi dell'evoluzione dell'errore $e_t = \theta_t - \theta^*$ e sfruttando la definitività positiva della parte simmetrica della matrice TD (curvatura $\omega$), producendo $\tilde{O}(1/(\omega T))$.

3. Schema di Step-size

Lo step-size proposto è:
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
dove $c$ è una costante numerica, $\tau_{\text{mix}}$ è il tempo di mescolamento (mixing time) e $\phi_\infty$ limita le norme delle feature. Fondamentalmente, questo schema dipende dal tempo di mescolamento ma non dalla curvatura $\omega$.

Risultati Chiave

1. Limitatezza ad Alta Probabilità (Teorema 4.1)

Sotto ipotesi standard (MRP ergodica, feature full-rank), le iterazioni del TD(0) non proiettato sono uniformemente limitate con alta probabilità ($1-\delta$):
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
dove $R_{\text{base}}$ dipende dall'errore iniziale, dalla norma della soluzione ottima e dalle costanti del problema, ma è indipendente da $\omega$. Questo è il primo risultato a mostrare tale limitatezza per il TD(0) non proiettato sotto campionamento Markoviano senza utilizzare $\omega$ nello step-size o nell'argomento di stabilità.

2. Simultaneità dei Tassi di Convergenza (Teorema 4.2)

Utilizzando lo stesso step-size e la media PR, l'algoritmo raggiunge un tasso di convergenza ad alta probabilità per l'errore della funzione potenziale:
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
Sostituendo lo schema dello step-size, ciò si traduce in:

• Tasso Robusto: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• Tasso Veloce: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

Il limite si adatta automaticamente al minimo di questi due tassi senza conoscenza preventiva di $\omega$.

3. Variante Senza Conoscenza del Mixing (Appendice E)

Gli autori propongono anche uno step-size modificato $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ che non richiede la conoscenza di $\tau_{\text{mix}}$. Tuttavia, ciò comporta una dipendenza doppiamente esponenziale da $\tau_{\text{mix}}$ nelle costanti del limite di convergenza, specificamente attraverso il limite iniziale $B_{m^*}$.

Significato e Rivendicazioni

Il documento afferma di essere il primo a stabilire che il TD(0) lineare con campionamento Markoviano può raggiungere sia tassi di convergenza robusti che veloci ad alta probabilità utilizzando un singolo step-size che è:

1. Indipendente dal parametro di curvatura $\omega$.
2. Privo di proiezioni.

Gli autori sottolineano che i lavori precedenti o richiedevano proiezioni (cambiando l'algoritmo), o si affidavano a step-size dipendenti dalla curvatura (fallendo quando $\omega$ è piccolo), o fornivano solo limiti di aspettativa (ad esempio, Lee e Orabona [2025]) piuttosto che garanzie ad alta probabilità.

La significatività risiede nell'argomento di auto-limitazione tramite equazioni di Poisson, che rompe la dipendenza circolare tra la limitatezza delle iterazioni e l'entità degli aggiornamenti senza ricorrere alle proprietà contrattive della dinamica media. Ciò consente all'algoritmo di rimanere stabile e di convergere rapidamente anche quando la curvatura è arbitrariamente piccola, uno scenario in cui le precedenti analisi prive di proiezioni tipicamente fallivano o richiedevano strategie di scarto dei dati.

Il documento rimane modesto riguardo alla dipendenza dal tempo di mescolamento $\tau_{\text{mix}}$. Sebbene il tasso veloce abbia una dipendenza di $\tau_{\text{mix}}^2$ (peggiore della dipendenza lineare $\tau_{\text{mix}}$ in alcuni lavori precedenti basati su proiezioni o scarto dei dati), gli autori notano che la dipendenza ottimale da $\tau_{\text{mix}}$ in assenza di proiezioni e scarto dei dati rimane una questione aperta. Riconoscono anche che il loro termine di errore iniziale decade con un tasso $1/T$ piuttosto che esponenziale, una conseguenza dell'aver evitato argomenti basati sulla contrazione.