Sintesi Tecnica: La Rappresentazione Terminale nel Reinforcement Learning

Definizione del Problema

Nel Reinforcement Learning (RL), l'apprendimento della rappresentazione è critico per l'astrazione spazio-temporale. Due approcci consolidati sono la Successor Representation (SR) e la Default Representation (DR). La SR codifica gli stati in base alle traiettorie di visitazione futura, catturando la dinamica delle transizioni indipendentemente dalle ricompense. La DR estende questo concetto pesando tali traiettorie con le ricompense, integrando così la struttura dell'assegnazione del credito.

Tuttavia, entrambe le rappresentazioni affrontano limitazioni quando applicate a compiti a valle come la scoperta di opzioni (option discovery), il reward shaping e il transfer learning:

1. Overhead Computazionale: L'utilizzo della DR o della SR per questi compiti richiede tipicamente la decomposizione in autovettori (o iterazione di potenza) per estrarre gli autovettori. Ciò impone un costo computazionale di $O((S^+)^2)$ o superiore per query e assume una dinamica di transizione simmetrica (reversibile), una condizione spesso violata in ambienti RL pratici dove le policy sono direzionali.
2. Dimensionalità: La SR e la DR sono definite sull'intero spazio degli stati ($S^+ \times S^+$), che può essere grande ed inefficiente da memorizzare e apprendere.
   3.Conoscenza Indiretta: Sebbene la DR codifichi le traiettorie pesate dalle ricompense, essa non isola esplicitamente la raggiungibilità e la desiderabilità degli stati terminali in un formato direttamente utilizzabile senza ulteriore analisi spettrale.

Metodologia: La Rappresentazione Terminale (TR)

Gli autori propongono la Terminal Representation (TR), una formulazione strutturalmente distinta progettata per codificare le traiettorie pesate dalle ricompense specificamente rispetto agli stati terminali.

Fondamento Teorico

La TR è derivata all'interno del framework dei Markov Decision Processes Linearmente Solubili (LMDP). In un LMDP, la funzione di valore ottimale $v(s)$ può essere trasformata in un valore esponenziato $z(s) = e^{v(s)/\lambda}$, che soddisfa l'equazione lineare:
$$z(s) = e^{R(s)/\lambda} \sum_{s'} P_\mu(s'|s)z(s')$$
dove $P_\mu$ è una policy di default e $\lambda$ è un parametro di temperatura.

Decomponendo lo spazio degli stati in stati non terminali ($S$) e stati terminali ($T$), gli autori derivano la matrice TR come:
$$M = (I_S - D_S)^{-1} D_T$$
dove $D_S = R_S P_S$ rappresenta la dinamica non terminale e $D_T = R_S P_T$ rappresenta le transizioni da stati non terminali a stati terminali. Qui, $R_S$ e $R_T$ sono matrici diagonali di ricompense esponenziate.

La TR permette il recupero zero-shot dei valori esponenziati ottimali $z$ per qualsiasi configurazione di ricompense terminali $y$ (dove $y(\tau) = e^{R(\tau)/\lambda}$) tramite la relazione lineare:
$$z = M y$$

Algoritmi di Apprendimento

Il paper stabilisce la convergenza di due algoritmi di apprendimento per $M$:

1. Dynamic Programming (Model-Based): Una regola di aggiornamento iterativa $M_{k+1} = D_T + D_S M_k$ è provata convergere alla vera TR.
2. Sample-Based (Model-Free): Una regola di aggiornamento di tipo temporal difference (TD) è derivata per l'apprendimento online:
   $$\hat{M}(s_t) \leftarrow (1 - \alpha_t)\hat{M}(s_t) + \alpha_t e^{r_t/\lambda} \hat{M}^+(s_{t+1})$$
   dove $\hat{M}^+$ è una mappatura estesa che gestisce le transizioni verso gli stati terminali. Il Teorema 4.2 prova che questa converge a $M$ sotto le standard condizioni di approssimazione stocastica.

Proprietà Teoriche Chiave

• Dimensionalità: La TR è una matrice $S \times T$. Poiché il numero di stati terminali $T$ è spesso molto più piccolo dello spazio degli stati totale $S^+$, la TR è significativamente più compatta della DR $S^+ \times S^+$.
• Utilizzabilità Diretta (Nessuna Decomposizione in Autovettori): Le colonne della TR corrispondono direttamente alle informazioni tipicamente estratte tramite gli autovettori della DR. Il Teorema 7.1 dimostra che il primo autovettore della DR è strutturalmente composto da una colonna della TR (specificamente la colonna corrispondente allo stato terminale più desiderabile) e una serie geometrica. Pertanto, la TR cattura la stessa conoscenza strutturale sottostante senza richiedere la decomposizione in autovettori.
• Gestione dell'Asimmetria: A differenza degli approcci basati su autovettori che si affidano alla reversibilità delle dinamiche di transizione (simmetria) per garantire autovalori reali, la TR è intrinsecamente asimmetrica e ben definita sotto dinamiche arbitrarie e non reversibili.
• Componibilità: La TR supporta la componibilità zero-shot. Se un nuovo compito è una combinazione lineare di compiti base con diverse ricompense terminali, la funzione di valore ottimale può essere recuperata combinando linearmente le corrispondenti colonne della TR, evitando la necessità di riapprendere le funzioni di valore base.
• Equivalenza delle Ricompense: Gli autori dimostrano che gli LMDP con ricompense dipendenti dalle transizioni o dalle azioni-stato possono essere mappati in LMDP equivalenti con ricompense dipendenti dallo stato, garantendo che la teoria della TR si applichi ampiamente a diverse formulazioni di ricompensa.

Risultati Sperimentali

Gli autori valutano la TR rispetto a SR e DR attraverso quattro applicazioni a valle in ambienti grid-world (Four Rooms, RiverSwim, SixArms):

1. Scoperta di Opzioni (Option Discovery): Nel compito di "covering eigenoptions", la TR viene utilizzata per generare opzioni estraendo direttamente le colonne (evitando il calcolo degli autovettori). Varianti che utilizzano la colonna dello stato terminale a più alta ricompensa o tutte le colonne hanno ottenuto prestazioni competitive con i metodi RACE basati su DR e CEO basati su SR, spesso raggiungendo ricompense medie più elevate spingendo gli agenti direttamente verso gli obiettivi desiderabili.
2. Reward Shaping: Utilizzando la TR per costruire ricompense di potenziale basate ($\hat{r}_t = 1 - M(s_{t+1}, \tau)$), si è ottenuta una performance identica alla DR e superiore alla SR. Ciò conferma la capacità della TR di catturare l'informazione strutturale necessaria per una navigazione efficiente senza decomposizione in autovettori.
3. Esplorazione Basata sul Conteggio (Count-Based Exploration): L'uso della norma della TR come bonus di esplorazione negli ambienti RiverSwim e SixArms ha prodotto una performance quasi identica alla DR e significativamente migliore della SR.
4. Transfer Learning: Quando le ricompense terminali cambiavano tra i compiti, la TR è stata utilizzata per trasferire la conoscenza. Ha performato similmente alle Default Features (DF) (la variante della DR indipendente dalla policy) e ha superato le Successor Features (SF) attraverso varie configurazioni di policy base, il tutto senza un esplicito step di apprendimento delle feature.

Significato e Rivendicazioni

Il paper sostiene che la Rappresentazione Terminale offra un'alternativa valida e computazionalmente efficiente alla SR e alla DR. La sua principale importanza risiede in:

• Efficienza: Riduce la dimensionalità della rappresentazione ed elimina la necessità di costose decomposizioni in autovettori, riducendo la complessità di query da $O((S^+)^2)$ a $O(1)$ per l'estrazione della colonna.
• Robustezza: Funziona correttamente sotto dinamiche di transizione non simmetriche (non reversibili), uno scenario comune nel RL dove i metodi basati su autovettori possono fallire o produrre autovalori complessi.
• Applicabilità Diretta: Codifica esplicitamente la conoscenza degli stati terminali, permettendo l'uso diretto nel reward shaping, nella scoperta di opzioni e nel transfer learning senza analisi spettrale intermedia.

Gli autori mantengono una posizione modesta, osservando che, sebbene la TR sia competitiva con la DR, non è fondamentalmente superiore in tutti gli aspetti semantici; piuttosto, fornisce un meccanismo più compatto e computazionalmente trattabile per accedere alla stessa conoscenza strutturale sottostante riguardante gli stati terminali. Il lavoro futuro suggerito consiste nell'estendere la TR ad ambienti ad alta dimensionalità tramite approssimazione di funzione e nel gestire setting senza stati terminali esplicitamente definiti.