Riepilogo Tecnico: Metodi del Gradiente della Politica per l'Apprendimento per Rinforzo Non-Markoviano

Enunciato del Problema

L'Apprendimento per Rinforzo (RL) si basa tradizionalmente sul framework del Processo Decisionale di Markov (MDP), assumendo che le dinamiche e le ricompense dipendano esclusivamente dallo stato e dall'azione correnti. Tuttavia, molti ambienti reali—come sistemi parzialmente osservabili, agenti dialogici, sistemi di raccomandazione e mercati finanziari—sono intrinsecamente Processi Decisionali Non-Markoviani (NMDP). In questi contesti, le osservazioni e le ricompense dipendono dall'intera storia delle interazioni.

Condizionare direttamente le politiche all'intera storia è computazionalmente intrattabile poiché lo spazio delle storie cresce esponenzialmente. Sebbene gli approcci esistenti tentino di comprimere la storia, spesso affrontano limitazioni:

• Dinamiche Fisse: Alcuni metodi assumono che le dinamiche dello stato interno dell'agente siano fisse e ottimizzano solo la politica di controllo (ad esempio, Dong et al., 2022).
• Obiettivi Predittivi: Altri metodi apprendono rappresentazioni dello stato ottimizzando obiettivi predittivi ausiliari (ad esempio, prevedere le osservazioni future), il che può richiedere rappresentazioni ad alta dimensionalità e non si allinea direttamente con l'obiettivo finale di massimizzare la ricompensa cumulativa (ad esempio, Subramanian et al., 2022).

Questo articolo affronta la sfida di apprendere congiuntamente una rappresentazione compatta dello stato e una politica di controllo negli NMDP senza fare affidamento su dinamiche fisse o su obiettivi predittivi intermedi.

Metodologia

Politiche Agent State-Markov (ASM)

Gli autori introducono una classe di politiche Agent State-Markov (ASM). In questo framework, l'agente mantiene uno stato interno $S_t$ che viene aggiornato ricorsivamente in base allo stato precedente, all'azione precedente e all'osservazione corrente:
$$S_t \sim \nu_t(\cdot \mid S_{t-1}, A_{t-1}, O_t)$$
La politica di controllo $\phi$ mappa quindi lo stato attuale dell'agente in un'azione:
$$A_t \sim \phi_t(\cdot \mid S_t)$$
La coppia $(\nu, \phi)$ costituisce la politica ASM. Crucialmente, gli autori propongono di ottimizzare i parametri sia delle dinamiche dello stato $\nu$ che della politica di controllo $\phi$ congiuntamente per massimizzare la ricompensa cumulativa attesa, piuttosto che fissare $\nu$ o apprenderlo tramite previsione.

Contributi Teorici

L'articolo stabilisce un Teorema del Gradiente della Politica per le politiche ASM, estendendo i risultati classici sia agli NMDP episodici che a quelli con orizzonte infinito scontato.

1. Espressione del Gradiente: Per una politica ASM parametrizzata $\pi_\theta$, il gradiente del rendimento atteso $J(\theta)$ è derivato come:
   $$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \sum_{t} R_{t:\infty} \nabla_\theta \log \pi_\theta(S_t, A_t \mid S_{t-1}, A_{t-1}, O_t) \right]$$
   dove $R_{t:\infty}$ rappresenta il rendimento futuro (ricompensa da ottenere).
2. Fattorizzazione: A causa della struttura delle politiche ASM, il termine del log-probabilità si fattorizza nelle dinamiche dello stato e nella politica di controllo:
   $$\nabla_\theta \log \pi_\theta = \nabla_\theta \log \nu_\theta + \nabla_\theta \log \phi_\theta$$
   Ciò consente l'aggiornamento separato ma simultaneo della rappresentazione dello stato e della politica.
3. Garanzie di Convergenza: Sotto standard ipotesi di regolarità e limitatezza, gli autori dimostrano:
   • Convergenza in tempo finito: La norma quadrata media temporale del gradiente converge a un tasso di $\tilde{O}(H^{3.5}/\sqrt{K})$ per compiti episodici (dove $H$ è l'orizzonte e $K$ è il numero di iterazioni).
   • Convergenza quasi certa: Con passi di dimensione decrescente, la norma del gradiente converge a zero quasi certamente.
   • Garanzie simili sono stabilite per l'impostazione con orizzonte infinito scontato, dove l'orizzonte effettivo è determinato dal fattore di sconto $\gamma$.

Algoritmo: ASMPG

Basandosi sul teorema del gradiente, gli autori propongono l'algoritmo Agent State-Markov Policy Gradient (ASMPG). È un algoritmo online, in stile REINFORCE, che:

• Campiona traiettorie utilizzando la politica ASM corrente.
• Calcola la stima del gradiente utilizzando la struttura ricorsiva dello stato dell'agente.
• Aggiorna i parametri sia della rete delle dinamiche dello stato che della rete della politica utilizzando la discesa del gradiente stocastico.

Risultati Sperimentali

Gli autori hanno valutato ASMPG su cinque ambienti non-Markoviani:

1. CheeseMaze: Un compito di navigazione parzialmente osservabile con osservazioni ambigue (alias).
2. HallwayNavigation: Un compito di labirinto deterministico dove le configurazioni locali delle pareti sono ambigue.
3. HealthcareTreatment: Un compito di pianificazione del trattamento con variabili nascoste di tossicità e resistenza.
4. MachineRepair: Un compito di manutenzione con livelli di usura nascosti che influenzano il degrado della macchina.
5. VelocityOnlyCartPole: Un compito di controllo in cui viene osservata solo la velocità (non la posizione).

Confronto: ASMPG è stato confrontato con AIS-KL e AIS-MMD (Subramanian et al., 2022), che apprendono rappresentazioni dello stato tramite obiettivi predittivi (Stati di Informazione Approssimati).

Risultati:

• In tutti e cinque gli ambienti, ASMPG ha ottenuto ricompense medie per passo o per episodio superiori rispetto alle baseline predittive.
• Il divario di prestazioni è stato particolarmente notevole in compiti che richiedono memoria a lungo termine, come CheeseMaze, MachineRepair e VelocityOnlyCartPole.
• I risultati suggeriscono che ottimizzare direttamente le dinamiche dello stato per l'obiettivo di ricompensa è più efficace rispetto all'ottimizzazione per la sufficienza predittiva.

Significato e Affermazioni

L'articolo afferma che il suo contributo principale è una formulazione incentrata sulla ricompensa per il RL non-Markoviano. Trattando le dinamiche dello stato dell'agente come un componente apprendibile ottimizzato congiuntamente alla politica di controllo, il metodo bypassa la necessità di obiettivi predittivi ausiliari o di rappresentazioni dello stato fisse.

Le affermazioni chiave includono:

• Validità Teorica: La derivazione di un teorema del gradiente della politica per NMDP generali fornisce una base rigorosa per l'ottimizzazione congiunta, estendendo i risultati classici degli MDP.
• Efficacia Pratica: I risultati empirici dimostrano che l'ottimizzazione congiunta incentrata sulla ricompensa supera i metodi che si basano su rappresentazioni dello stato predittive, anche quando le dimensioni delle rappresentazioni sono comparabili.
• Condizioni di Ottimalità: L'articolo nota che se esiste una dinamica dello stato dell'agente "ideale" (una che è una statistica sufficiente per le ricompense e le osservazioni future), limitare la ricerca alle politiche ASM non comporta alcuna perdita di ottimalità.

Gli autori riconoscono che il metodo proposto si basa su stimatori di tipo REINFORCE, che possono soffrire di alta varianza. Identificano lo sviluppo di varianti attore-critico per le politiche ASM come una direzione naturale per il lavoro futuro, al fine di ridurre la varianza preservando l'obiettivo incentrato sulla ricompensa.