Riepilogo Tecnico: Apprendimento per Rinforzo con Politiche di Diffusione Discreta per Spazi di Azione Combinatori

1. Enunciato del Problema

L'Apprendimento per Rinforzo (RL) affronta sfide significative quando si scala verso grandi spazi di azione discreti combinatori, prevalenti in applicazioni reali come la pianificazione gerarchica con macro-azioni, il coordinamento multi-agente e le raccomandazioni a "slate" nei sistemi di raccomandazione. Gli algoritmi RL standard faticano con questi spazi a causa della crescita esponenziale delle dimensioni dello spazio delle azioni, richiedendo parametrizzazioni delle politiche e strategie di esplorazione altamente efficienti.

Gli approcci precedenti hanno tentato di mitigare questa complessità attraverso la riduzione della dimensionalità, l'addestramento gerarchico o l'assunzione di specifiche proprietà strutturali. Più recentemente, i modelli autoregressivi sono stati applicati alle azioni combinatorie; tuttavia, soffrono di elevati costi computazionali durante l'inferenza a causa della generazione sequenziale e impongono ordinamenti causali artificiali delle azioni che possono limitare l'espressività della politica. Sebbene i modelli di diffusione abbiano mostrato promesse nel controllo continuo e nelle attività generative discrete, un quadro principiale ed efficiente per l'addestramento di politiche di diffusione discreta tramite RL online rimane inesplorato.

2. Metodologia: RL-D2

Gli autori introducono RL-D2, un nuovo quadro per l'addestramento di modelli di diffusione discreti come politiche per spazi di azione combinatori. L'innovazione centrale risiede in un processo di addestramento online efficiente che disaccoppia l'ottimizzazione dell'obiettivo RL dal complesso compito dell'apprendimento delle rappresentazioni.

2.1. Obiettivo della Discesa dello Specchio della Politica (PMD)

Il quadro riformula l'aggiornamento della politica come un problema di corrispondenza distribuzionale. Invece di ottimizzare direttamente l'obiettivo RL, il metodo utilizza la Discesa dello Specchio della Politica (PMD) per definire una distribuzione target ideale e regolarizzata ($\pi_{MD}$). Data una politica corrente $\pi_{old}$ e una funzione di vantaggio $A_{\pi_{old}}$, la distribuzione target è derivata analiticamente:
$$\pi_{MD}(a|s) \propto \pi_{old}(a|s) \exp(A_{\pi_{old}}(s, a)/\lambda)$$
dove $\lambda$ è un parametro di temperatura. Il modello di diffusione espressivo viene quindi addestrato per replicare questa distribuzione target stabile.

2.2. Minimizzazione della Divergenza

L'aggiornamento della politica è ottenuto minimizzando la divergenza tra la politica di diffusione ($\pi_\theta$) e il target PMD ($\pi_{MD}$). Il documento analizza due varianti specifiche basate sulla divergenza di Kullback-Leibler (KL):

• KL Inverso (FKL): Minimizza $d_{KL}(\pi_{MD}, \pi_\theta)$. Questo comportamento "ricercante la media" incoraggia la politica a coprire le modalità della distribuzione target, promuovendo l'esplorazione. Gli autori derivano una perdita ELBO ponderata trattabile per questo obiettivo, che consente l'addestramento off-policy e ripesa le azioni campionate in base ai loro valori di vantaggio.
• KL Inverso (RKL): Minimizza $d_{KL}(\pi_\theta, \pi_{MD})$. Questo comportamento "ricercante la modalità" si concentra sulle azioni di valore più alto ed è teoricamente equivalente all'ottimizzazione PMD originale. A causa dell'intrattabilità della verosimiglianza della diffusione, gli autori costruiscono un MDP aumentato per derivare un rapporto di campionamento per importanza trattabile, ottimizzando l'obiettivo utilizzando un meccanismo di clipping in stile PPO.

2.3. Apprendimento della Diffusione On-Policy

Per allineare la distribuzione di addestramento con la distribuzione di inferenza, gli autori propongono l'Apprendimento della Diffusione On-Policy. Invece di generare azioni rumorose da un processo forward fisso partendo da un'azione pulita, la traiettoria di diffusione è generata on-policy campionando dal processo inverso appreso dalla politica corrente. Ciò migliora la stabilità e l'efficienza del campione.

3. Contributi Chiave

1. Quadro RL-D2: Un nuovo quadro di addestramento online efficiente per l'uso di modelli di diffusione discreti come politiche in RL per spazi di azione combinatori. Riformula gli aggiornamenti della politica come problemi di corrispondenza distribuzionale utilizzando target PMD.
2. Derivazioni Teoriche: La derivazione e l'analisi di due metodi pratici di miglioramento della politica basati sulla minimizzazione delle divergenze Forward e Reverse KL verso il target PMD.
3. Validazione Empirica: Esperimenti estesi su tre domini impegnativi che dimostrano risultati allo stato dell'arte:
   • Generazione di Sequenze di DNA: Affinamento guidato dal reward di un modello di diffusione discreto.
   • RL a Orizzonte Lungo: Pianificazione di macro-azioni negli ambienti MinAtar e Atari.
   • RL Multi-Agente: Apprendimento cooperativo nel dominio Google Research Football.

4. Risultati Sperimentali

Il documento riporta prestazioni superiori ed efficienza del campione in tutti i domini testati:

• Generazione di Sequenze di DNA: RL-D2 ha ottenuto punteggi di reward allo stato dell'arte mantenendo un'alta verosimiglianza logaritmica (naturalità) delle sequenze generate. Ha dimostrato un'efficienza computazionale significativa, riducendo il consumo di memoria GPU da 66,4 GB a 10,6 GB e il tempo di addestramento da 268 minuti a 97 minuti rispetto alla baseline DRAKES.
• Atari (Macro-Azioni): RL-D2 ha superato baselines robuste (DQN, IMPALA, R2D2, PPO) in 36 ambienti Atari su 56. Ha mostrato una forza particolare in compiti che richiedono strategie a lungo termine (ad esempio, Breakout, Space Invaders). Il metodo ha dimostrato scalabilità, mantenendo le prestazioni all'aumentare delle lunghezze delle macro-azioni (fino a 16), mentre baselines come DQN-Macro fallivano a causa della crescita esponenziale dello spazio delle azioni.
• Google Research Football: In compiti multi-agente cooperativi (fino a 11 contro 11), la politica di diffusione discreta ha ottenuto i tassi di vittoria medi più alti, superando le baselines autoregressive (MAT, MAPPO) e dimostrando la capacità di catturare complesse dipendenze inter-agenti senza fattorizzazioni restrittive.

Compromessi Empirici: FKL vs. RKL

Gli autori evidenziano un compromesso chiave tra le due varianti di divergenza:

• FKL: Dimostra un'efficienza del campione superiore e una convergenza iniziale più rapida, rendendolo adatto a scenari con vincoli di dati (ad esempio, Atari). Tuttavia, è meno stabile e richiede un'attenta regolazione della temperatura per evitare il collasso.
• RKL: Garantisce un addestramento stabile e raggiunge prestazioni asintotiche più elevate in compiti impegnativi con dati sufficienti (ad esempio, Google Football), sebbene apprenda leggermente più lentamente inizialmente.

5. Significato e Affermazioni

Il documento afferma che RL-D2 fornisce una soluzione scalabile e ad alte prestazioni alla sfida di lunga data del RL in grandi spazi di azione combinatori. Sfruttando il potere espressivo dei modelli di diffusione discreti e stabilizzando l'apprendimento attraverso la corrispondenza distribuzionale basata su PMD, il quadro gestisce efficacemente problemi decisionali complessi dove i metodi tradizionali spesso falliscono.

Gli autori sottolineano che il loro approccio offre un vantaggio distinto rispetto ai solutori standard a scatola nera discreti (ad esempio, algoritmi evolutivi) imparando una politica condizionata allo stato che sfrutta le dinamiche di transizione e si generalizza a stati non visti, piuttosto che ottimizzare obiettivi statici da zero. Inoltre, la natura disaccoppiata del metodo stabilizza il processo di apprendimento, migliorando significativamente le prestazioni in spazi discreti complessi e non strutturati.