Riepilogo Tecnico: Integrazione di DAG Causali nel RL Profondo con MOSE

Enunciato del Problema

Gli algoritmi di apprendimento per rinforzo (RL) online si basano fondamentalmente sulla proprietà di Markov, che assume che il futuro sia condizionalmente indipendente dal passato dato lo stato presente. Tuttavia, nelle applicazioni reali che coinvolgono osservazioni grezze (ad esempio, flussi di sensori, fotogrammi video), le variabili osservate spesso non formano intrinsecamente uno stato markoviano perché la dinamica del sistema può dipendere da una quantità sconosciuta di contesto storico.

Sebbene la letteratura esistente sul RL causale utilizzi Grafi Aciclici Diretti (DAG) causali per accelerare l'apprendimento o progettare ricompense robuste, questi metodi assumono tipicamente che sia già disponibile una rappresentazione dello stato markoviano valida e pre-specificata. Rimane un divario critico: dato un grafo causale longitudinale sulle variabili osservate, non esiste una procedura consolidata per costruire una rappresentazione dello stato che soddisfi provabilmente la proprietà di Markov. Inoltre, nel contesto del RL profondo, la semplice costruzione di uno stato markoviano teoricamente "minimale" spesso non migliora le prestazioni empiriche, poiché le reti neurali possono faticare a generalizzare da tali rappresentazioni sparse a causa dell'overfitting e della mancanza di caratteristiche ridondanti che aiutano l'approssimazione della funzione.

Metodologia

Il documento propone un approccio a due facce: una procedura teorica per costruire stati minimi da grafi causali noti e un metodo euristico (MOSE) per il RL profondo quando il grafo è sconosciuto o per migliorare la stabilità dell'apprendimento.

1. Costruzione di uno Stato Markoviano Minimo da DAG Causali

Gli autori stabiliscono una connessione formale tra DAG causali delle serie temporali e Processi Decisionali di Markov (MDP).

• Quadro Teorico: Utilizzando Modelli Causali Strutturali (SCM) estesi alle serie temporali, il documento definisce un "Grafo Temporale Completo" in cui i nodi rappresentano variabili in specifici passi temporali e gli archi rappresentano dipendenze causali con ritardi temporali.
• Criterio Grafico: Il Teorema 4.1 fornisce quattro condizioni necessarie e sufficienti affinché una sequenza di insiemi di variabili $\{S_t\}$ costituisca uno spazio degli stati valido:
  1. Inclusione dei Genitori della Ricompensa: Tutti i genitori della variabile ricompensa $R_t$ devono essere inclusi in $S_t$.
  2. Inclusione Estesa dei Genitori del Prossimo Stato: Tutti i genitori (ai tempi $\le t$) dell'"insieme esteso del prossimo stato" (la chiusura di $S_{t+1}$ rispetto ai genitori nello stesso tempo) devono essere inclusi in $S_t$.
  3. Nessuna Rientro Ancestrale: Una volta che una variabile viene rimossa dalla costruzione dello stato, i suoi antenati non possono rientrare nello stato in un momento successivo.
  4. Persistenza: Se una variabile appare nello stato in due momenti diversi, deve apparire in tutti gli stati intermedi.
• Algoritmo F.1: Viene proposto un algoritmo di costruzione inversa per generare una sequenza di stati provabilmente minima che soddisfi i suddetti criteri. Partendo dalla fine dell'orizzonte, seleziona iterativamente i genitori necessari della ricompensa e del prossimo stato, assicurandosi che non siano incluse variabili ridondanti, preservando al contempo la proprietà di Markov e il valore ottimale.

2. Esposizione Multi-Ordine dello Stato (MOSE)

Riconoscendo che le rappresentazioni minime possono portare a una scarsa generalizzazione nel RL profondo (a causa di minimi acuti e mancanza di flessibilità statistica), gli autori propongono MOSE.

• Meccanismo: Invece di fornire una singola stato minimo o una finestra fissa di storia alla funzione Q, MOSE fornisce multipli ordini di costruzioni di stati storici simultaneamente. Nello specifico, per una lunghezza della finestra $W$, l'algoritmo aggiorna iterativamente la funzione di valore utilizzando input che vanno dall'osservazione corrente ($l=0$) fino all'intera finestra ($l=W$).
• Razionale: Gli input di ordine inferiore, non markoviani, agiscono come rumore strutturato che rimodella il paesaggio della perdita. Questo fornisce un gradiente graduale e informativo da rappresentazioni subottimali a quelle ottimali, agendo come regolarizzatore simile all'aumento dei dati o all'apprendimento multi-vista.
• Causal-MOSE: Un'estensione in cui lo stato markoviano minimo (derivato dal DAG causale) è incluso insieme agli input multi-ordine. Questo combina la garanzia teorica del nucleo minimo con i benefici empirici della ridondanza.

Contributi Chiave

1. Costruzione di Stato Markoviano Minimo: Il documento fornisce un criterio grafico e un algoritmo costruttivo inverso (Algoritmo F.1) per derivare uno spazio degli stati provabilmente minimo da un DAG causale longitudinale noto. Questo colma il divario tra la scoperta causale e la definizione dello stato MDP.
2. Esposizione Multi-Ordine dello Stato (MOSE): Un metodo euristico per la costruzione dello stato che non richiede conoscenze preliminari del DAG causale. Dimostra che esporre gli agenti di RL profondo a finestre temporali multiple di storia migliora le prestazioni rispetto sia all'impilamento di fotogrammi ingenuo sia alle rappresentazioni causali minime.
3. Causal-MOSE: Un approccio ibrido che mostra come combinare lo stato markoviano minimo con l'esposizione multi-ordine produca prestazioni pari o superiori a MOSE da solo, validando l'utilità della struttura causale quando disponibile.

Risultati Sperimentali

Gli autori hanno valutato i loro metodi su tre Processi di Generazione Dati (DGP) sintetici e sul gioco Atari GOPHER.

• DGP Sintetici: Utilizzando Modelli a Rumore Additivo Lineare (ANM) e Modelli Post-Non Lineari (PNL) con ordini MDP variabili ($W=2, 5, 10$), MOSE ha costantemente superato:
  • Politica a Finestra: Impilamento standard di fotogrammi (concatenazione di $W$ fotogrammi fissi).
  • Genitori della Ricompensa: Utilizzo dei soli genitori della ricompensa come stato.
  • Stato-DAG: Lo stato minimo costruito dall'Algoritmo F.1.
  • Risultato Chiave: Lo stato minimo (Stato-DAG) da solo non ha migliorato le prestazioni rispetto alle politiche a finestra e talvolta le ha peggiorate, confermando che la minimalità teorica non equivale all'ottimalità empirica nel RL profondo.
• Prestazioni di Causal-MOSE: Negli ambienti ANM lineari, Causal-MOSE (stato minimo + MOSE) ha costantemente superato MOSE da solo, suggerendo che lo stato minimo fornisce un nucleo affidabile su cui la rete può costruire.
• Atari (GOPHER): MOSE ha superato l'algoritmo Rainbow standard (che utilizza l'impilamento di 4 fotogrammi) in 1 milione di passi di addestramento. Ciò indica che negli ambienti ad alta dimensionalità dei pixel, non tutti i fotogrammi impilati contribuiscono ugualmente al controllo e che la selezione adattiva dello stato migliora l'efficienza del campione.
• Ablazioni: Gli esperimenti hanno confermato che i guadagni non erano dovuti a un aumento dei passi di gradiente per batch (artefatti di ottimizzazione) ma piuttosto alle rappresentazioni dello stato più ricche fornite da MOSE.

Significato e Affermazioni

Il documento stabilisce un principio fondamentale per il RL causale profondo: la sufficienza minima non è sufficiente e una ridondanza controllata è necessaria per sbloccare il beneficio delle informazioni sullo stato causale.

Gli autori sostengono che, sebbene i grafi causali forniscano un modo principiato per identificare le variabili minime richieste per la proprietà di Markov, le reti neurali profonde beneficiano della "flessibilità statistica" fornita da input ridondanti e non markoviani. Questi input ridondanti aiutano la rete a evitare l'overfitting su correlazioni spurie e facilitano una migliore generalizzazione.

Il lavoro contribuisce con una base teorica per costruire stati MDP validi da grafi causali e con un'euristica pratica (MOSE) che rende queste intuizioni causali utilizzabili nel moderno RL profondo. Gli autori notano che il loro approccio presuppone l'accesso a un grafo causale longitudinale di verità fondamentale; apprendere tali grafi da dati ad alta dimensionalità e non stazionari rimane una sfida aperta per il lavoro futuro.