On Reward-Balancing Methods for Reinforcement Learning

1. Problema e Contesto

Il lavoro si concentra sui problemi di Apprendimento per Rinforzo (RL) basati su Processi Decisionali di Markov (MDP) a ritorno scontato. L'obiettivo classico è trovare una politica ottima che massimizzi il ritorno cumulativo atteso.
La maggior parte degli algoritmi RL esistenti (come Q-learning) mantiene la funzione di ricompensa fissa e aggiorna iterativamente la politica. Questo paper esplora un approccio alternativo: metodi di bilanciamento delle ricompense (reward-balancing). Invece di modificare la politica, questi metodi modificano iterativamente la funzione di ricompensa per trasformare il problema originale in uno "equivalente" (normalizzato), in cui la politica ottima è semplicemente greedy rispetto alla nuova ricompensa (ovvero, sceglie l'azione con ricompensa massima, che in forma normale è zero).

Il problema centrale affrontato è:

1. Come caratterizzare matematicamente le trasformazioni che preservano l'ottimalità della politica mentre modificano la ricompensa.
2. Come formulare questo processo di "normalizzazione" come un problema di controllo ottimo.
3. Come estendere questo framework a scenari con incertezza del modello (dove la dinamica di transizione non è nota esattamente ma viene campionata), garantendo stabilità e convergenza probabilistica.

2. Metodologia e Struttura Teorica

A. Analisi Algebrica e Geometrica

Gli autori definiscono un gruppo di trasformazioni affini sulle funzioni di ricompensa, parametrize da funzioni definite sullo spazio degli stati.

• Trasformazioni che preservano l'vantaggio (Advantage-Preserving): Viene dimostrato che esiste un gruppo di trasformazioni che lascia invariata la funzione di vantaggio ($adv_{\pi,r}$) di una politica. Questo implica che l'ordine delle politiche (quale è migliore) non cambia, anche se i valori assoluti delle ricompense e dei valori ($v_\pi$) si spostano.
• MDP Normali: Un MDP è in "forma normale" se la sua funzione di valore ottima è zero ovunque. In tale stato, la politica ottima è quella che seleziona, per ogni stato, l'azione con ricompensa zero (massima tra quelle disponibili, dato che le altre sono negative).
• Struttura di Fascio (Fiber Bundle): Lo spazio delle funzioni di ricompensa è analizzato come un fascio principale. Ogni orbita del gruppo di trasformazione interseca l'insieme delle ricompense normali in un unico punto. Questo permette di identificare ogni MDP con una coppia: (ricompensa normale, funzione di valore ottima).

B. Riformulazione come Problema di Controllo Ottimo

Il processo di normalizzazione viene riformulato come un problema di stabilizzazione dell'uscita di un sistema dinamico lineare:

• Stato: Il vettore delle ricompense $R_t$.
• Input: La trasformazione $\Delta_t$ (derivata dalla funzione di valore stimata).
• Dinamica: $R_{t+1} = R_t + (\gamma F - S)\Delta_t$.
• Obiettivo: Guidare lo stato $R_t$ verso l'insieme delle ricompense normali (dove il massimo della ricompensa per stato è zero).

Vengono analizzate diverse leggi di controllo:

1. Controllo Ideale: Risolve il problema in un passo (impraticabile senza modello esatto).
2. Feedback Completo (Full-Output): Corrisponde all'algoritmo di iterazione del valore (Value Iteration).
3. Bilanciamento Sicuro (Safe RB): Una legge non lineare che garantisce la non-positività delle ricompense ad ogni passo.

C. Gestione dell'Incertezza del Modello (Stochastic Model Sampling)

Quando il modello di transizione $F$ non è noto e viene stimato tramite campioni stocastici $\hat{F}_t$, il processo di normalizzazione diventa un sistema stocastico con rumore moltiplicativo.

• Insieme Admissibile Invariante: Viene definito un sottoinsieme di controlli ammissibili che rimane valido indipendentemente dalla realizzazione specifica del modello incerto.
• Garanzie Probabilistiche: Utilizzando la teoria dei martingale e disuguaglianze di concentrazione (maximal inequality per spazi di Banach), gli autori derivano limiti probabilistici sulla deviazione tra il percorso di normalizzazione reale (con modello incerto) e quello ideale (con modello esatto).
• Scenario Model Predictive Control (MPC): Viene proposto un framework MPC basato su scenari. Invece di usare un singolo modello stimato, si campionano $N$ scenari di transizione e si risolve un problema di ottimizzazione per trovare l'input di controllo che minimizza il costo cumulativo atteso, rispettando i vincoli di stabilità su tutti gli scenari.

3. Contributi Chiave

1. Analisi Teorica Completa: Fornisce una caratterizzazione rigorosa del gruppo di trasformazioni alla base dei metodi di reward-balancing, evidenziando la loro struttura algebrica e geometrica (fasci principali).
2. Riformulazione nel Controllo Ottimo: Trasforma il problema di normalizzazione in un problema di controllo ottimo, permettendo l'uso di strumenti avanzati come vincoli, termini di penalità e predizione a orizzonte finito.
3. Estensione Robusta all'Incertezza: Estende il framework a modelli incerti, fornendo condizioni sufficienti per la convergenza geometrica e limiti probabilistici sulla deviazione stocastica.
4. Algoritmo MPC Basato su Scenari: Propone un nuovo metodo di controllo (Scenario MPC) che supera le prestazioni degli algoritmi esistenti in termini di ottimalità della politica finale in presenza di rumore nel modello.

4. Risultati e Simulazioni

Gli autori hanno condotto studi di simulazione su un MDP con due stati e dieci azioni (cinque per stato), con un fattore di sconto $\gamma = 0.8$.

• Confronto: È stato confrontato il nuovo metodo Scenario MPC con il metodo Full-Output Feedback (già presente nella letteratura come algoritmo di bilanciamento sicuro).
• Performance:
  • Entrambi i metodi convergono verso la normalizzazione.
  • Lo Scenario MPC produce input di controllo più piccoli nella fase iniziale, evitando oscillazioni eccessive.
  • Risultato Principale: Lo Scenario MPC raggiunge la politica ottima con una percentuale significativamente più alta rispetto al metodo Full-Output Feedback quando il numero di scenari considerati aumenta.
  • La politica media risultante sotto lo Scenario MPC è più vicina alla politica ottima deterministica rispetto a quella ottenuta con il feedback completo.
• Trade-off: Sebbene lo Scenario MPC offra migliori prestazioni in termini di ottimalità, richiede un costo computazionale superiore rispetto al feedback semplice. Tuttavia, dimostra che è possibile progettare leggi di normalizzazione più efficaci sfruttando il framework di controllo ottimo.

5. Significato e Impatto

Questo lavoro è significativo perché:

• Sposta il paradigma di ricerca in RL dalla sola ottimizzazione della politica all'ottimizzazione della struttura del problema (la ricompensa) per semplificare la soluzione.
• Fornisce una base teorica solida (geometria algebrica e teoria del controllo) per metodi che erano stati precedentemente proposti in modo più empirico.
• Offre una soluzione robusta al problema dell'incertezza del modello, un ostacolo comune nelle applicazioni RL reali, dimostrando che l'uso di tecniche di controllo predittivo (MPC) può mitigare gli effetti del rumore e migliorare la qualità della politica finale.
• Apre la strada a futuri algoritmi di RL che combinano l'aggiornamento della ricompensa con la gestione dell'incertezza, potenzialmente riducendo la complessità del campione (sample complexity) e migliorando la stabilità.

In sintesi, il paper dimostra che il bilanciamento delle ricompense non è solo un trucco euristico, ma un processo matematicamente ben fondato che può essere ottimizzato sistematicamente per ottenere prestazioni superiori, specialmente in ambienti incerti.