Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

Sintesi Tecnica: Ridistribuzione della Ricompensa per MDP CVaR tramite un Operatore di Bellman su $L^\infty$

Enunciato del Problema
Nelle applicazioni critiche per la sicurezza, l'ottimizzazione del rendimento atteso (risk-neutral) è spesso insufficiente, poiché può permettere esiti rari ma catastrofici. Il Conditional Value-at-Risk (CVaR) statico è una misura di rischio coerente utilizzata per controllare la coda inferiore della distribuzione del rendimento. Tuttavia, a differenza degli obiettivi risk-neutral, il CVaR statico di un rendimento manca di separabilità ricorsiva rispetto allo spazio degli stati nominali, impedendo una standard decomposizione di Bellman di tipo Markoviano.

Gli approcci esistenti, in particolare Bauerle & Ott (2111), affrontano questo problema aumentando lo spazio degli stati con una variabile di "budget" continua che traccia le ricompense cumulative. Sebbene teoricamente fondata, questa formulazione soffre di due critiche limitazioni pratiche:

1. Ricompense Sparse: L'informazione rilevante per il CVaR è concentrata interamente in un funzionale terminale dello stato aumentato. Ciò risulta in ricompense per passo nulle nell'MDP aumentato, creando un feedback ritardato che esacerba le sfide di esplorazione e di assegnazione del credito temporale (temporal credit assignment), particolarmente in contesti a orizzonte infinito.
2. Convergenza Limitata: L'operatore di Bellman associato alla formulazione di Bauerle & Ott è garantito essere una contrazione solo su un insieme altamente ristretto di funzioni non limitate. Nello spazio più pratico delle funzioni limitate ($L^\infty$), l'operatore ammette un punto fisso degenero (la funzione zero), rendendo inapplicabili la classica iterazione del valore e il Q-learning senza vincoli di inizializzazione accurati e spesso inaccessibili.

Metodologia
Gli autori propongono una nuova riformulazione dell'obiettivo CVaR statico che risolve queste limitazioni attraverso una trasformazione algebrica della funzione valore.

1. MDP Aumentato Trasformato: Costruendo sulla aumentazione dello stato di Bauerle & Ott (2011), gli autori definiscono una nuova funzione valore $\bar{v}^*(s, z)$ che incorpora un termine di spostamento $z^-$ (la parte negativa del budget). Questa trasformazione permette la derivazione di un nuovo operatore di Bellman, $\bar{T}$, definito sullo spazio delle funzioni limitate $L^\infty(\bar{S})$.
2. Ridistribuzione della Ricompensa: L'innovazione chiave è la definizione di una nuova funzione di ricompensa per passo $\tilde{r}(s, z, a) = z^- - (r(s, a) + z)^-$. A differenza della precedente formulazione che produceva ricompense intermedie nulle, questa nuova ricompensa è densa e informativa ad ogni passo, ridistribuendo efficacemente il segnale rilevante per il CVaR lungo la traiettoria.
3. Proprietà di Contrazione: Gli autori dimostrano che il nuovo operatore $\bar{T}$ è una $\gamma$-contrazione rispetto alla norma sup su tutto lo spazio delle funzioni limitate. Ciò garantisce che l'iterazione del valore converga a un punto fisso unico senza richiedere le ristrettive condizioni di inizializzazione del lavoro precedente.
4. Discretizzazione e Approssimazione: Poiché lo stato aumentato $z$ è continuo, gli autori impiegano uno schema di discretizzazione uniforme. Definiscono operatori di limite inferiore e superiore ($\bar{T}^l$ e $\bar{T}^u$) utilizzando funzioni inviluppo per approssimare il vero operatore. Stabiliscono limiti teorici mostrando che l'errore tra il CVaR ottimale e l'approssimazione discretizzata scala proporzionalmente alla granularità della discretizzazione e al fattore di sconto.
5. Algoritmi: Sulla base di questo framework, il documento sviluppa:
   • Iterazione del Valore CVaR Statica: Un algoritmo model-based che calcola la funzione Q ottimale per tutti gli stati iniziali e i livelli di budget simultaneamente.
   • Q-Learning CVaR Statico: Un algoritmo model-free che utilizza una strategia di aggiornamento a blocchi. Sfruttando la natura deterministica della transizione dello stato aumentato, l'algoritmo ri-etichetta una singola traiettoria per aggiornare i valori Q per molteplici ipotesi di budget iniziale, migliorando l'efficienza dei dati. La convergenza è dimostrata sotto le standard condizioni di dimensione del passo di Robbins-Monro.

Contributi Chiave

• Nuovo Operatore di Bellman: Il documento introduce un nuovo operatore di Bellman per il CVaR statico a orizzonte infinito che opera su uno spazio di stati aumentato, è esatto rispetto all'obiettivo di controllo, fornisce ricompense per passo non sparse e costituisce una mappatura di contrazione sulle funzioni limitate.
• Garanzie di Approssimazione: Gli autori forniscono rigorosi limiti di errore di approssimazione per il CVaR discretizzato, quantificando il divario di prestazione in funzione della risoluzione della griglia.
• Dimostrazioni di Convergenza: Il documento stabilisce condizioni sufficienti per la convergenza dell'algoritmo di Q-learning proposto nello spazio aumentato discretizzato.
• Ottimalità Globale: Gli algoritmi producono soluzioni globalmente ottimali per tutti i livelli di rischio (stato aumentato iniziale) in un'unica esecuzione, anziché richiedere un addestramento separato per ogni parametro di rischio.

Risultati Empirici
Gli autori validano il loro approccio su un ambiente di gridworld stocastico ("Crater Walk") dove un agente deve navigare da un punto di partenza a un obiettivo evitando un cratere (penalità elevata) e minimizzando l'uso di carburante (penalità per passo).

• Sensibilità al Rischio: Le policy apprese regolano con successo il comportamento in base al parametro di rischio $\alpha$. Man mano che $\alpha$ diminuisce (aumento dell'avversione al rischio), la coda inferiore della distribuzione del rendimento si restringe e l'agente evita il cratere più frequentemente, anche se ciò richiede un percorso più lungo.
• Prestazioni: Sia l'iterazione del valore che l'algoritmo di Q-learning ottengono efficaci compromessi tra prestazione e sicurezza. L'algoritmo di Q-learning converge entro 50.000 iterazioni di addestramento.
• Accuratezza della Discretizzazione: Gli esperimenti variando la risoluzione della discretizzazione (da 100 a 5000 bin) dimostrano che le curve di prestazione degli operatori di limite superiore e inferiore convergono al vero valore ottimale all'aumentare della risoluzione, convalidando empiricamente i limiti di errore teorici.

Significato e Rivendicazioni
Il documento sostiene che le limitazioni della scarsità delle ricompense e delle garanzie di convergenza ristrette nei MDP CVaR statici non sono intrinseche al problema, ma sono artefatti di specifiche scelte di modellazione nella letteratura precedente. Proponendo una riformulazione esatta che ridistribuisce le ricompense e opera su funzioni limitate, gli autori consentono l'applicazione di tecniche standard di programmazione dinamica e apprendimento per rinforzo model-free ai problemi di rischio sensibile statico. Questo lavoro pone le basi per algoritmi di RL avversi al rischio scalabili che non dipendono da euristiche di capping della ricompensa o da curricula di rischio specializzati. Gli autori osservano che, sebbene la loro analisi empirica si concentri su contesti tabulari, il framework teorico supporta estensioni future all'approssimazione di funzione (ad esempio, reti neurali profonde) per gestire spazi di stato continui senza restrizioni sul segno della ricompensa.