Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

Sintesi Tecnica: Convergenza in Tempo Finito del Q-Learning Distribuzionalmente Robusto con Approssimazione Funzionale Lineare

Enunciato del Problema
Il lavoro affronta la sfida di apprendere politiche ottimali nel Reinforcement Learning Distribuzionalmente Robusto (DRRL) quando l'ambiente di deployment differisce dall'ambiente di addestramento (nominale). Nello specifico, gli autori si concentrano sul Q-learning robusto scontato, model-free e distribuazionale sotto un insieme di incertezza $\chi^2$ $(s, a)$-rettangolare.

Il setting prevede un apprendista che opera su una singola traiettoria markoviana generata da un kernel di transizione nominale $P_0$ ignoto e una politica di comportamento $\pi_b$. L'apprendista non dispone di accesso generativo (non può campionare coppie stato-azione arbitrarie) e non conosce $P_0$. L'obiettivo è apprendere la funzione Q robusta ottimale, $Q^\star_\chi$, che massimizza il valore scontato nel caso peggiore rispetto all'insieme di incertezza.

Il problema presenta due difficoltà accoppiate:

1. Difficoltà di Approssimazione Funzionale: Sebbene l'operatore di Bellman robusto esatto sia una contrazione in $\ell_\infty$, l'operatore di Bellman robusto proiettato indotto dall'approssimazione funzionale lineare non è noto per essere una contrazione per fattori di sconto generali $\gamma \in (0, 1)$.
2. Difficoltà di Stima Robusta: L'aggiornamento di Bellman robusto $\chi^2$ comporta una minimizzazione interna sulle distribuzioni di transizione. Il suo gradiente duale dipende dai momenti condizionali (specificamente, la parte positiva del gap di Bellman e il suo quadrato) che devono essere stimati da una singola traiettoria. Le analisi standard per il Q-learning robusto tabulare o il Q-learning lineare non si estendono direttamente a questo setting.

Metodologia
Gli autori propongono l'Algoritmo 1, un algoritmo di approssimazione stocastica a più stadi che combina un ciclo esterno di target-network con uno schema di approssimazione funzionale duale. L'algoritmo opera in blocchi esterni in cui la funzione Q target è congelata. All'interno di ogni blocco, si verificano tre stadi:

1. Stadio 1: Ottimizzazione Duale con Monitoraggio dei Momenti.
   L'algoritmo risolve la minimizzazione interna dell'aggiornamento di Bellman robusto $\chi^2$ tramite la sua forma duale scalare. Inveve di risolvere un problema duale separato per ogni coppia stato-azione, la variabile duale $\eta$ viene approssimata linearmente ($\eta_\nu(i) = \psi(i)^\top \nu$).

   • Schema a Due Scale Temporali: La variabile duale $\nu$ viene aggiornata su una scala temporale lenta, mentre due "critici di monitoraggio dei momenti" ($\omega_1, \omega_2$) stimano i momenti condizionali richiesti ($Z_1$ e $Z_2$) su una scala temporale più veloce.
   • Smoothing (Levigatura): Per gestire la mancanza di regolarità globale nell'obiettivo duale $\chi^2$ (che causa problemi con l'analisi del rumore markoviano), gli autori ottimizzano un obiettivo surrogato levigato utilizzando un parametro regolabile $\tau > 0$. Ciò garantisce che il gradiente duale sia Lipschitz continuo.
   • Media dei Suffissi: Le iterazioni duali sono sottoposte a media dei suffissi per ottenere una stima stabile $\bar{\nu}_t$.

2. Stadio 2: Valutazione Fresca (Fresh Evaluation).
   Prima di aggiornare la funzione Q, l'algoritmo esegue una "valutazione fresca" del momento di tipo varianza ($Z_1$) utilizzando il parametro duale mediato $\bar{\nu}_t$. Questo stadio isola la stima del momento dall'iterazione di ottimizzazione, prevenendo l'accumulo di bias che si verificherebbe se i critici dello Stadio 1 (appresi mentre $\nu$ si muoveva) venissero riutilizzati direttamente.

3. Stadio 3: Aggiornamento Q.
   L'algoritmo esegue un aggiornamento di differenza temporale lento per il parametro della funzione Q robusta contro il target fisso e valutato derivato dagli Stadi 1 e 2.

Contributi Chiave

1. Garanzia di Convergenza in Tempo Finito: Il documento fornisce il primo limite di convergenza in tempo finito per il Q-learning robusto scontato con approssimazione funzionale lineare da dati di singola traiettoria, senza imporre restrizioni su piccoli fattori di sconto.
2. Analisi del Target-Network per il RL Robusto: Gli autori adattano la tecnica del target-network (comune nel RL profondo non robusto) al contesto robusto. Congelando la funzione Q target all'interno dei blocchi esterni, aggirano la non-contrattività dell'operatore di Bellman robusto proiettato, permettendo all'analisi di fare affidamento sulla contrazione dell'operatore non proiettato tra i blocchi.
3. Stima Duale Scalabile: Introducono un metodo per approssimare la variabile duale stessa utilizzando una classe di funzioni lineari, accoppiata con critici di monitoraggio dei momenti. Ciò evita i problemi di scalabilità legati alla risoluzione di problemi duali indipendenti per grandi spazi di stato.
4. Smoothing e Controllo del Bias: Il documento introduce un surrogato levigato per l'obiettivo duale $\chi^2$. Questo risolve il problema del gradiente non-Lipschitz inerente alla formulazione $\chi^2$ esatta, consentendo analisi rigorose di approssimazione stocastica a tempo finito sotto rumore markoviano. Gli autori sottolineano esplicitamente che le precedenti prove per il Q-learning robusto tabulare con incertezza $\chi^2$ si basavano su assunzioni di regolarità globale che non sussistono; la loro prova corregge questa lacuna.

Risultati
Il principale risultato teorico (Teorema 1) stabilisce un limite di convergenza end-to-end della forma:
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
dove:

• Il primo termine rappresenta l'errore di contrazione del target-network.
• $E_{stat}$ cattura gli errori di campionamento finito dall'aggiornamento Q, dall'ottimizzazione duale, dal bias di smoothing e dalla valutazione fresca.
• $E_{app}$ cattura gli errori di approssimazione dovuti all'approssimazione funzionale e allo smoothing.

Esperimenti sull'MDP FrozenLake validano la teoria, dimostrando la convergenza verso il valore di riferimento robusto e illustrando il compromesso introdotto dal parametro di smoothing $\tau$ (un $\tau$ più piccolo riduce il bias ma aumenta la varianza/errore di ottimizzazione).

Significatività e Rivendicazioni
Il documento sostiene di colmare un significativo divario tra il successo empirico degli algoritmi di RL robusto e le garanzie teoriche disponibili per i loro controparti non robusti. I lavori precedenti sul RL robusto model-free erano limitati a contesti tabulari, richiedevano l'accesso generativo, assumevano un'esplorazione attiva o imponevano condizioni restrittive sul fattore di sconto.

Gli autori affermano che il loro lavoro fornisce la prima garanzia di convergenza in tempo finito per il Q-learning robusto scontato con approssimazione funzionale lineare da dati di singola traiettoria senza assunzioni di piccoli fattori di sconto. Inoltre, sostengono che la loro prova per il caso $\chi^2$ (anche nel limite tabulare) appare come la prima prova corretta di convergenza, poiché affronta la mancanza di regolarità globale nell'obiettivo duale che le analisi precedenti avevano trascurato o assunto come data. Il framework è presentato come un modello analizzabile che può essere esteso a implementazioni su larga scala con reti neurali.