Riepilogo Tecnico: Colmare il Divario tra Apprendimento TD Medio e Scontato

Enunciato del Problema

L'apprendimento Temporal Difference (TD) è un pilastro dell'apprendimento per rinforzo, tuttavia la sua analisi teorica nel setting a ricompensa media è significativamente in ritardo rispetto al setting scontato. Nel caso scontato, l'operatore di Bellman è una contrazione, garantendo soluzioni uniche e un'analisi della convergenza diretta. Al contrario, nel setting a ricompensa media, l'operatore di Bellman non è contrattivo rispetto a nessuna norma, e la soluzione della corrispondente equazione di Bellman non è unica (è definita solo a meno di una costante additiva).

La letteratura esistente che affronta il TD a ricompensa media soffre di diverse limitazioni rispetto al caso scontato:

1. Assunzioni Restrittive: Molti metodi richiedono assunzioni (ad esempio, $\Phi\theta \neq ce$) che escludono il setting tabellare.
2. Garanzie di Convergenza: Alcuni approcci garantiscono la convergenza solo verso un punto fisso dipendente dal percorso del campione o verso un insieme, piuttosto che verso una soluzione unica e deterministica.
3. Dipendenza dalla Dimensione: I limiti di convergenza contengono spesso fattori espliciti della dimensione dei parametri $d$.
4. Scalatura del Numero di Condizionamento: Le complessità di campionamento all'avanguardia mostrano spesso una dipendenza quartica dal numero di condizionamento del problema ($O(\eta^{-4})$), mentre il setting scontato ottiene una scalatura quadratica ($O(\eta^{-2})$).
5. Complessità Algoritmica: Ottenere una migliore scalatura nei lavori precedenti richiedeva spesso tecniche complesse di riduzione della varianza (ad esempio, cicli annidati), allontanandosi dalla semplicità del TD standard.

Metodologia

Gli autori propongono un approccio innovativo alla valutazione della politica nel setting a ricompensa media formulando la soluzione dell'equazione di Bellman come un problema di ottimizzazione vincolata. L'idea centrale è che la funzione valore relativa $W^*$ deve soddisfare un vincolo di stato stazionario ($\mu^\top W^* = 0$).

1. Algoritmo a Doppia Catena

Per risolvere l'equazione di Bellman proiettata $W^* = \Pi T_\pi W^*$, dove $\Pi = I - e\mu^\top$, gli autori derivano una regola di aggiornamento stocastica. Una sfida chiave nell'approssimazione stocastica per questo setting è il problema del "doppio campionamento": stimare il termine $\mu\mu^\top(R + W_t)$ richiede l'aspettativa di un prodotto di variabili casuali, che non può essere stimato da una singola traiettoria a causa della correlazione.

Per risolvere ciò, gli autori introducono un Algoritmo a Doppia Catena che utilizza due catene di Markov indipendenti ($\{s_t\}$ e $\{\hat{s}_t\}$) in ogni iterazione.

• Regola di Aggiornamento: Il vettore dei parametri $\theta_t$ viene aggiornato utilizzando due componenti:
  • $g(s_t, s'_t, \theta_t)$: Stima il termine standard di errore TD $D(R + P\Phi\theta_t - \Phi\theta_t)$.
  • $f(s_t, \hat{s}_t, \theta_t)$: Stima il termine vincolare $-\mu\mu^\top(R + \Phi\theta_t)$ utilizzando il campione indipendente $\hat{s}_t$ per rompere la correlazione.
• Approssimazione Lineare: Il metodo si generalizza all'approssimazione lineare della funzione ($W \approx \Phi\theta$) proiettando gli aggiornamenti sullo spazio delle caratteristiche.

2. Algoritmo a Singola Catena

Per evitare il sovraccarico computazionale del mantenimento di due catene, gli autori propongono un Algoritmo a Singola Catena ispirato al Gradient TD (GTD).

• Meccanismo: Invece di campionare un secondo stato indipendente $\hat{s}_t$, l'algoritmo mantiene una variabile ausiliaria $w_t$ che traccia l'aspettativa $E[\phi(s)] = \Phi^\top\mu$.
• Aggiornamento: Il termine $\phi(\hat{s}_t)$ nell'aggiornamento a doppia catena viene sostituito da $w_t$. La variabile $w_t$ viene aggiornata tramite un passo separato di approssimazione stocastica per convergere a $\Phi^\top\mu$.
• Compromesso: Sebbene ciò semplifichi il requisito di campionamento a una singola traiettoria, l'analisi mostra una dipendenza leggermente peggiore dal numero di condizionamento rispetto alla variante a doppia catena.

3. Quadro Teorico: Splitting del Gradiente

L'analisi di convergenza si basa sulla tecnica dello splitting del gradiente [19]. Gli autori dimostrano che la direzione di aggiornamento attesa del loro algoritmo agisce come uno "splitting del gradiente" di una specifica funzione quadratica composita:
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
Ciò permette agli autori di analizzare l'algoritmo utilizzando le tecniche standard di ricorsione della Discesa del Gradiente Stocastica (SGD), nonostante la natura non contrattiva dell'operatore di Bellman sottostante.

Contributi Chiave

Il documento afferma di colmare il divario teorico tra l'apprendimento TD a ricompensa media e quello scontato ottenendo simultaneamente le seguenti caratteristiche:

1. Punto Fisso Unico e Indipendente dal Campione: Gli algoritmi proposti convergono quasi certamente a una soluzione deterministica singola $\theta^*$ che è indipendente dalla traiettoria casuale e dall'inizializzazione.
2. Applicabilità ai Setting Tabellari e Lineari: L'analisi vale sia per i casi tabellari (dove $\Phi = I$) sia per l'approssimazione lineare della funzione, senza richiedere l'assunzione restrittiva $e \notin \text{span}(\Phi)$.
3. Limiti Indipendenti dalla Dimensione: I limiti di convergenza non contengono fattori espliciti della dimensione $d$ (oltre a quelli intrinseci in $\|\theta^*\|$ o $\|\theta_0\|$).
4. Convergenza dell'Ultima Iterata: I risultati sono garantiti per l'ultima iterata, allineandosi allo standard del TD scontato, piuttosto che fare affidamento sulla media delle iterazioni.
5. Migliorata Scalatura del Numero di Condizionamento:
   • L'algoritmo a Doppia Catena ottiene una complessità di campionamento di $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$, dove $\eta_1$ è un numero di condizionamento definito come $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$. Ciò corrisponde alla scalatura quadratica osservata nel setting scontato.
   • L'algoritmo a Singola Catena ottiene $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (quartica), che rappresenta un miglioramento rispetto ad alcuni lavori precedenti ma è leggermente peggiore della variante a doppia catena.
6. Semplicità Algoritmica: La scalatura quadratica è ottenuta senza tecniche di riduzione della varianza (ad esempio, cicli annidati o batch completi periodici), mantenendo la semplicità degli aggiornamenti TD puri.

Risultati

Gli autori forniscono un'analisi a campione finito per entrambi gli algoritmi sotto campionamento i.i.d. e markoviano, con dimensioni del passo sia costanti che decrescenti.

• Limiti Teorici: I Teoremi 4.1–4.3 stabiliscono tassi di convergenza e complessità di campionamento. Il metodo a doppia catena corrisponde allo stato dell'arte per il TD scontato in termini di scalatura dei parametri.
• Esperimenti Numerici: Gli algoritmi sono stati testati su 15 MDP tabellari provenienti da OpenAI Gym e MO-Gymnasium.
  • I risultati mostrano che i metodi proposti generalmente superano i baseline precedenti (inclusi [10], [11], [12], [17], [18] e [21]) in termini di errore di approssimazione rispetto alla soluzione vera.
  • Gli esperimenti confermano che i metodi convergono alla soluzione unica, mentre alcuni baseline (che convergono verso insiemi o punti dipendenti dal campione) mostrano una varianza o un errore più elevati nel setting tabellare.

Significato

Il documento afferma di risolvere le persistenti riserve teoriche associate all'analisi del TD a ricompensa media. Utilizzando lo splitting del gradiente e una strategia di campionamento a due catene (o a singola catena con variabile ausiliaria), gli autori dimostrano che il TD a ricompensa media può ottenere le stesse proprietà di convergenza favorevoli del TD scontato:

• Unicità: Convergenza verso una soluzione ben definita e unica.
• Generalità: Applicabilità ai setting tabellari e lineari senza assunzioni restrittive.
• Efficienza: Dipendenza quadratica dal numero di condizionamento senza la necessità di complesse macchine di riduzione della varianza.

Questo lavoro suggerisce che le difficoltà teoriche del setting a ricompensa media possono essere superate riformulando il problema come un compito di ottimizzazione vincolata e sfruttando strategie di campionamento specifiche per gestire la natura non contrattiva dell'operatore di Bellman.