Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

Titolo: Analisi a Tempo Finito dell'Approssimazione Stocastica a Due Scale di Tempo Proiettata

1. Il Problema

L'approssimazione stocastica (SA) è uno strumento fondamentale per risolvere problemi di ottimizzazione e di ricerca delle radici basati su osservazioni rumorose. In molte applicazioni moderne, come l'apprendimento per rinforzo (RL) e l'ottimizzazione vincolata, si utilizza la SA a due scale di tempo (TTSA), dove due gruppi di variabili (una "veloce" $x$ e una "lenta" $y$) vengono aggiornati con passi di apprendimento diversi ($\alpha \gg \beta$).

Tuttavia, in scenari ad alta dimensionalità (es. valutazione di politiche in RL con spazi degli stati enormi), è spesso necessario vincolare le iterazioni a sottospazi lineari a bassa dimensionalità (approssimazione lineare tramite proiezione).
Il problema centrale affrontato è l'analisi della convergenza di questi metodi proiettati in un regime di tempo finito. In particolare, gli autori vogliono quantificare il compromesso tra:

1. Errore di approssimazione (Bias): L'errore intrinseco dovuto al fatto che la soluzione vincolata nel sottospazio differisce dalla soluzione vera nello spazio completo.
2. Errore statistico (Variance): L'errore dovuto al rumore di campionamento, che dovrebbe decrescere con il numero di iterazioni.

Mentre la convergenza asintotica è ben nota, manca un'analisi rigorosa a tempo finito per la TTSA proiettata che utilizzi passi di apprendimento costanti e media di Polyak-Ruppert (PR).

2. Metodologia

Gli autori analizzano l'algoritmo TTSA proiettato definito come:
$$\begin{aligned} x_{t+1} &= \Pi_X [x_t + \alpha(g(x_t, y_t) + \epsilon_t)] \\ y_{t+1} &= \Pi_Y [y_t + \beta(h(x_t, y_t) + \psi_t)] \end{aligned}$$
dove $\Pi_X$ e $\Pi_Y$ sono operatori di proiezione su sottospazi lineari $X$ e $Y$.

La metodologia si basa sui seguenti pilastri:

• Media di Polyak-Ruppert (PR): Invece di analizzare l'ultima iterazione, si studia la media delle iterazioni $\bar{x}_T = \frac{1}{T}\sum x_t$ e $\bar{y}_T = \frac{1}{T}\sum y_t$. Questa tecnica è nota per migliorare l'efficienza statistica, cancellando le fluttuazioni a media zero.
• Passi di apprendimento costanti: A differenza di molti lavori precedenti che usano passi decrescenti, questo studio utilizza passi costanti ($\alpha, \beta$), il che permette di ottenere identità telescopiche esatte e una decomposizione più pulita dell'errore.
• Decomposizione Bias-Varianza: L'errore totale viene scomposto analiticamente in due componenti distinte:
  1. Errore di approssimazione: La distanza tra la soluzione vincolata $(x^*_p, y^*_p)$ e la soluzione libera $(x^*, y^*)$.
  2. Errore statistico: La distanza tra la media delle iterazioni e la soluzione vincolata.
• Assunzioni Tecniche: Si assumono condizioni di stabilità (matrici di Hurwitz), invertibilità delle matrici di accoppiamento proiettate e rumore martingala con varianza limitata.

3. Contributi Chiave

Il contributo principale del paper è la stabilimento di un limite superiore esplicito per l'errore quadratico medio (MSE) per le medie PR, con le seguenti caratteristiche distintive:

1. Decomposizione Esplicita dell'Errore:
   Il limite è della forma:
   $$\mathbb{E}[\|\bar{x}_T - x^*\|^2] \leq \underbrace{C_{app} \cdot \epsilon^2}_{\text{Errore di Approssimazione}} + \underbrace{\frac{L}{T}}_{\text{Errore Statistico}}$$
   dove $\epsilon^2$ rappresenta la distanza tra la soluzione vincolata e quella libera, e $L/T$ è il termine statistico.

2. Costanti Interpretabili:
   Le costanti che moltiplicano gli errori sono espresse in termini di:

   • Margini di stabilità ristretti: ($\mu_x, \mu_y$) legati alla stabilità delle dinamiche proiettate.
   • Condizione di invertibilità dell'accoppiamento: ($\kappa_{xy}, \kappa_{yx}$) che quantifica quanto le variabili veloci e lente sono accoppiate all'interno dei sottospazi.
   • Questo permette di separare chiaramente l'effetto della scelta del sottospazio (che influenza l'errore di approssimazione) dalla durata dell'orizzonte di mediazione (che influenza l'errore statistico).

3. Analisi a Tempo Finito per TTSA Proiettata:
   Il lavoro colma un vuoto nella letteratura fornendo la prima analisi a tempo finito che combina TTSA, proiezione su sottospazi e media PR, mostrando che il tasso di convergenza statistica rimane $O(1/T)$ anche in presenza di vincoli di proiezione.

4. Risultati Teorici e Sperimentali

Risultati Teorici (Teorema 1):

• È stato dimostrato che l'errore statistico decade al tasso $O(1/T)$, confermando l'efficacia della media PR anche in questo contesto complesso.
• L'errore totale converge a un "pavimento" (floor) determinato dall'errore di approssimazione, che non può essere ridotto aumentando le iterazioni, ma solo migliorando la scelta del sottospazio.
• Le costanti $L_x, L_y$ mostrano come il rumore si propaghi attraverso l'accoppiamento a due scale di tempo: il rumore sulla variabile lenta influenza la veloce e viceversa, scalato dai margini di stabilità.

Risultati Sperimentali:
Gli autori hanno validato la teoria su due casi d'uso:

1. Sistemi Lineari Accoppiati Sintetici: Hanno mostrato che gli errori PR decrescono e poi si stabilizzano al livello dell'errore di approssimazione teorico, confermando la decomposizione.
2. Gradient Temporal-Difference (GTD) in RL:
   • Hanno testato l'algoritmo GTD con diverse scelte di basi di feature (ben allineate, casuali, mal allineate rispetto alla funzione valore vera).
   • Risultato chiave: Indipendentemente dall'allineamento del sottospazio (che cambia l'errore di approssimazione), il tasso di decadimento dell'errore statistico rimane costante ($O(1/T)$).
   • Le curve di errore mostrano chiaramente il "plateau" sull'errore di approssimazione, confermando che la scelta del sottospazio determina il limite di accuratezza, mentre il numero di iterazioni determina quanto velocemente si raggiunge tale limite.

5. Significato e Implicazioni

Questo lavoro è significativo per diversi motivi:

• Guida alla Selezione dei Sottospazi: Fornisce una cornice teorica quantitativa per scegliere i sottospazi di approssimazione. Gli algoritmi di progettazione delle feature possono ora essere ottimizzati per minimizzare l'errore di approssimazione ($\epsilon^2$), sapendo che l'errore statistico sarà gestito efficientemente dalla media PR.
• Robustezza della Media PR: Dimostra che la media di Polyak-Ruppert mantiene le sue proprietà di accelerazione della convergenza ($O(1/T)$) anche in scenari complessi di ottimizzazione vincolata e accoppiata.
• Applicabilità Pratica: I risultati sono direttamente applicabili a problemi reali di Reinforcement Learning (come la valutazione di politiche con approssimazione lineare) e ottimizzazione duale-prima, offrendo garanzie di performance in tempo finito invece di semplici limiti asintotici.

In sintesi, il paper offre una comprensione profonda del compromesso tra bias (dovuto alla dimensionalità ridotta) e varianza (dovuta al rumore), fornendo strumenti analitici precisi per progettare algoritmi di apprendimento più efficienti e stabili.