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

Sintesi Tecnica: Una Teoria a Iterazioni Finite per l'Apprendimento Asincrono Temporale-Differenziale Distribuzionale Categorical

Enunciato del Problema
I recenti progressi nell'apprendimento per rinforzo (RL) distribuzionale hanno stabilito forti garanzie asintotiche per i metodi di valutazione della politica categorical, in particolare l'apprendimento temporale-differenziale categorical scalare (CTD) nella metrica di Cramér e l'apprendimento temporale-differenziale categorical multivariato con segno (MTD) nella metrica di discrepanza massima del kernel (MMD). Tuttavia, le analisi esistenti non asintotiche (a iterazioni finite) si concentrano in gran parte su aggiornamenti sincroni di stato completo, modelli generativi o surrogati idealizzati. Nei contesti pratici di RL online, l'apprendimento TD categorical standard opera in modo asincrono: esegue aggiornamenti a stato singolo ad ogni iterazione guidati da una traiettoria markoviana. Ciò crea un divario teorico tra la teoria asintotica consolidata e il comportamento a iterazioni finite delle esatte ricorrenze utilizzate nella pratica. Questo articolo colma tale divario fornendo garanzie a iterazioni finite per CTD e MTD asincroni sia nei regimi scontati che in quelli non scontati a orizzonte fisso.

Metodologia
Gli autori colmano il divario tra gli aggiornamenti asincroni pratici e la teoria dell'approssimazione stocastica (SA) a iterazioni finite attraverso un quadro unificato basato su embedding isometrici per stato e geometria del supremo a blocchi.

1. Embedding Isometrici e Contrazione:

   • Per CTD, gli autori utilizzano la metrica di Cramér e un embedding isometrico della massa cumulativa ($I_C$). Ciò trasforma l'operatore di Bellman proiettato in una contrazione in una norma di supremo a blocchi ($\|\cdot\|_{2,\infty}$) con modulo $\sqrt{\gamma}$ (scontato) o una contrazione pesata (orizzonte fisso).
   • Per MTD, impiegano la metrica MMD con un kernel caratteristico e un embedding della matrice di Gram ($I_M$). Ciò converte analogamente la mappa di Bellman proiettata in una contrazione nella geometria MMD a supremo a blocchi, con modulo $\gamma^{c/2}$ (scontato) o una contrazione pesata (orizzonte fisso).

2. Formulazione dell'Approssimazione Stocastica (SA) Asincrona:

   • La regola standard di aggiornamento a stato singolo è riformulata come una ricorrenza SA asincrona: $U_{k+1} = U_k + \alpha_k P_{S_k}(\hat{T}(U_k; S_k, \xi_k) - U_k(S_k))$.
   • L'analisi si basa su quadri astratti a iterazioni finite per ricorrenze contrattive sotto campionamento i.i.d. e markoviano (costruendo su Chen et al., Robbins-Monro e Borkar).
   • Geometria della Perturbazione: Viene effettuata una distinzione critica tra le strutture di rumore dei due metodi. CTD opera in un regime a rumore limitato a causa del supporto limitato delle distribuzioni categorical e della geometria di Cramér. Al contrario, MTD opera in un regime di perturbazione affine perché la proiezione categorical con segno è affine piuttosto che uniformemente limitata, portando a limiti di perturbazione che scalano con la norma dell'iterata corrente.

3. Regimi Analizzati:

   • Valutazione della Politica Scontata: Analizzata sia sotto campionamento i.i.d. (replay/modello generativo) che sotto campionamento di traiettoria markoviana (RL online standard). Il caso markoviano incorpora limiti sui tempi di mescolamento geometrici.
   • Valutazione Non Scontata a Orizzonte Fisso: Analizzata per compiti episodici con orizzonte fisso $H$. Poiché non esiste un fattore di sconto $\gamma < 1$ per guidare la contrazione, gli autori introducono una metrica a blocchi pesata ($\lambda^h$) attraverso lo stack dell'orizzonte. Ciò recupera una proprietà di contrazione dove l'orizzonte $h$ si basa su $h-1$. L'analisi viene eseguita ai confini degli episodi per gestire la deriva dipendente dalla fase all'interno di un episodio.

Contributi Chiave

1. Garanzie a Iterazioni Finite per CTD e MTD Asincroni: L'articolo stabilisce tassi di convergenza non asintotici espliciti per le ricorrenze asincrone standard di entrambi CTD e MTD. Questa è la prima teoria di questo tipo per questi specifici metodi sotto aggiornamenti a stato singolo guidati da traiettoria.
2. Quadro Unificato per Impostazioni Scontate e a Orizzonte Fisso: Gli autori forniscono un trattamento teorico coerente che copre sia problemi scontati (con campionamento i.i.d. e markoviano) sia problemi non scontati a orizzonte fisso (sotto campionamento episodico i.i.d.).
3. Decomposizione dell'Errore di Rappresentazione Deterministica: L'articolo registra una decomposizione che separa l'errore totale in un termine algoritmico (controllato dai limiti a iterazioni finite) e un termine di bias di proiezione deterministico (dipendente dalla famiglia di supporto categorical). Ciò permette di analizzare l'analisi SA e il bias di discretizzazione indipendentemente.
4. Costanti Esplicite e Regimi di Dimensione del Passo: L'analisi fornisce costanti esplicite per tre regimi di dimensione del passo:
   • Dimensione del passo costante: Convergenza geometrica verso un intorno $O(\alpha)$.
   • Dimensione del passo linearmente decrescente: Decadimento residuo di $O(1/k)$ (errore quadratico), implicando una complessità di campionamento di $O(\epsilon^{-2})$ per errore medio $\epsilon$.
   • Dimensione del passo polinomialmente decrescente: Decadimento di $O(1/k^z)$, scambiando il tasso di convergenza per condizioni di ammissibilità più miti.

Risultati

• Regime Scontato: Sia per CTD che per MTD, sotto campionamento i.i.d., l'errore quadratico converge a un tasso di $O(1/k)$ con dimensioni del passo linearmente decrescenti. Sotto campionamento markoviano, il tasso è $\tilde{O}(1/k)$, sostenendo un sovraccarico logaritmico dovuto al tempo di mescolamento della catena di Markov sottostante.
• Regime a Orizzonte Fisso: Per compiti episodici non scontati, l'errore ai confini degli episodi converge a tassi analoghi al caso scontato. Nello specifico, convergenza $O(1/m)$ per l'errore quadratico dopo $m$ episodi (equivalente a $O(\epsilon^{-2})$ transizioni).
• Regimi di Rumore: I risultati confermano che CTD beneficia di un rumore uniformemente limitato, mentre MTD richiede la gestione di limiti di rumore affini, il che introduce costanti aggiuntive relative alla norma dell'iterata nelle garanzie di convergenza.

Significato e Affermazioni
L'articolo afferma di colmare un divario teorico significativo tra la comprensione asintotica dell'RL distribuzionale e gli aggiornamenti pratici, asincroni e a stato singolo utilizzati nelle implementazioni. Dimostrando che le ricorrenze categorical standard costituiscono schemi SA asincroni con strutture contrattive in embedding adeguati, gli autori abilitano un controllo rigoroso a iterazioni finite.

Gli autori notano modestamente la portata del loro lavoro:

• La teoria è limitata alla valutazione della politica tabulare a stati finiti e non affronta il controllo o il miglioramento della politica.
• Le garanzie sono limiti di aspettativa piuttosto che limiti ad alta probabilità.
• I risultati si applicano alle esatte ricorrenze asincrone utilizzate nella pratica, distinguendole da lavori precedenti che hanno analizzato surrogati sincroni o basati su modelli.

Il lavoro stabilisce che, una volta formulati CTD e MTD con gli opportuni embedding per stato, le loro regole di aggiornamento possiedono le proprietà strutturali necessarie (contrazione, continuità di Lipschitz e perturbazione controllata) per essere analizzate utilizzando moderni strumenti SA non asintotici, fornendo la prima teoria a iterazioni finite per questi metodi distribuzionali ampiamente utilizzati in contesti online realistici.