In molti contesti esistono già politiche decisionali umane estremamente efficaci, e l’obiettivo dell’imitation learning è automatizzarle.

Una prima idea consiste nel far fornire a un supervisore umano un segnale di ricompensa ogni volta che l’algoritmo di reinforcement learning prende una decisione. Questo approccio ha il vantaggio di essere semplice e poco costoso, ma presenta un’elevata complessità in termini di numero di campioni richiesti per l’apprendimento.

Una valida alternativa consiste nell’apprendere direttamente dalle dimostrazioni dell’esperto. Ricompense che variano frequentemente nel tempo permettono di guidare l’agente in modo preciso, tuttavia, progettare manualmente funzioni di ricompensa di questo tipo può risultare fragile e poco scalabile. Un approccio più robusto è quello di definire implicitamente tali ricompense attraverso esempi o dimostrazioni del comportamento desiderato.

Nell’imitation learning, un esperto fornisce una serie di traiettorie dimostrative, cioè sequenze di stati e azioni \((s_0,a_0,s_1,a_1,\dots)\). Questo metodo è utile quando risulta più facile per l’esperto mostrare il comportamento corretto piuttosto che specificare esplicitamente una funzione di ricompensa in grado di generare tale comportamento e/o la policy ottimale da seguire in ogni situazione.

Il problema può essere formalizzato nei seguenti termini:

• Input:
  • Spazio degli stati e delle azioni;
  • Modello di transizione \(P(s'|s,a)\);
  • Nessuna funzione di ricompensa R nota;
  • Un insieme di una o più dimostrazioni dell’esperto \((s_0,a_0,s_1,a_1,\dots)\), generate dalla sua policy \(\pi\).
• Obiettivi principali:
  • Behavioral Cloning: apprendere direttamente la policy dell’esperto tramite apprendimento supervisionato;
  • Inverse Reinforcement Learning (IRL): stimare la funzione di ricompensa R che spiega il comportamento osservato;
  • Apprenticeship Learning via IRL: una volta stimata R, usarla per addestrare una policy ottimale.

In sintesi, l’imitation learning sfrutta la conoscenza di un esperto per ridurre la complessità dell’apprendimento, trasferendo comportamenti desiderabili a un agente artificiale senza necessità di una funzione di ricompensa esplicita.

Behavioral Cloning

Il behavioral cloning riduce il problema dell’imitation learning a un classico compito di apprendimento supervisionato. L’idea è quella di apprendere direttamente la policy dell’esperto a partire dalle coppie stato–azione osservate durante le dimostrazioni.

Il processo si articola in due passaggi principali:

• Definire una classe di policy, ad esempio una rete neurale, un albero decisionale o un modello lineare.
• Stimare i parametri della policy a partire da esempi di addestramento del tipo \( (s_0, a_0), (s_1, a_1), (s_2, a_2), \ldots \), in cui ogni stato \( s_t \) è associato all’azione esperta corrispondente \( a_t \).

Questo approccio permette di mappare gli stati alle azioni senza definire esplicitamente una funzione di ricompensa, trattando l’apprendimento della policy come una normale procedura di apprendimento supervisionato con RNN (specie nei casi non-markov).

Dagger

Uno dei limiti dei sistemi di behavorial cloning, in ottica di supervised learning, è che assume che le coppie (s,a) siano IID e ignora la struttura temporale (che anche con l'assunzione di Markov è presente).

Uno dei principali problemi del behavioral cloning è il fenomeno dei compounding errors, ossia l’accumulo progressivo di errori dovuto al disallineamento tra i dati usati per l’addestramento e quelli realmente incontrati durante l’esecuzione della policy appresa.

Nel classico apprendimento supervisionato, i dati di training e di test provengono dalla stessa distribuzione \( D \). Tuttavia, nei processi decisionali sequenziali (MDP), ciò non è vero:

• Durante l’addestramento, gli stati sono campionati secondo la distribuzione della policy esperta \( s_t \sim D_{\pi^*} \).
• Durante l’esecuzione del modello appreso, invece, gli stati provengono dalla distribuzione indotta dalla policy del modello stesso \( s_t \sim D_{\pi_\theta} \).

Questa discrepanza di distribuzione fa sì che piccoli errori nelle prime fasi si propaghino lungo la traiettoria, portando l’agente a visitare stati mai osservati in fase di addestramento e, di conseguenza, a commettere errori sempre più gravi.

Nel behavioral cloning, un piccolo errore di predizione in un singolo passo temporale può avere un impatto crescente nel tempo. Supponiamo che l’agente commetta un errore al tempo \( t \) con probabilità \( \epsilon \). Ogni errore può portare l’agente in uno stato diverso da quelli osservati durante l’addestramento, aumentando così la probabilità di commettere ulteriori errori nei passi successivi.

L’intuizione approssimata è che il numero totale atteso di errori cresca quadraticamente con l’orizzonte temporale \( T \):

\( \mathbb{E}[\text{Total errors}] \le \epsilon (T + (T-1) + (T-2) + \ldots + 1) \propto \epsilon T^2 \)

In altre parole, anche una piccola probabilità di errore per singolo passo può generare un aumento quadratico del numero complessivo di errori lungo la traiettoria, rendendo il comportamento dell’agente rapidamente divergente rispetto a quello dell’esperto.

Il metodo DAgger (Dataset Aggregation) è un approccio iterativo che mira a superare il problema della divergenza tra le distribuzioni degli stati del modello e quelle dell’esperto, aggiornando continuamente il dataset di addestramento con nuove traiettorie corrette dall’esperto.

• Algoritmo DAgger:
  • Inizializza il dataset \( \mathcal{D} \leftarrow \emptyset \).
  • Inizializza la prima policy stimata \( \hat{\pi}_1 \) in modo arbitrario nello spazio delle politiche \( \Pi \).
  • Per ogni iterazione \( i = 1, 2, \ldots, N \):
    • Definisci una policy mista \( \pi_i = \beta_i \pi^* + (1 - \beta_i)\hat{\pi}_i \), dove \( \pi^* \) è la policy esperta e \( \beta_i \) regola il peso dato all’esperto.
    • Campiona traiettorie di lunghezza \( T \) usando la policy \( \pi_i \).
    • Crea un dataset \( \mathcal{D}_i = \{(s, \pi^*(s))\} \) di stati visitati e azioni corrispondenti fornite dall’esperto.
    • Aggrega i dati nel dataset complessivo: \( \mathcal{D} \leftarrow \mathcal{D} \cup \mathcal{D}_i \).
    • Addestra un nuovo classificatore \( \hat{\pi}_{i+1} \) sui dati aggregati \( \mathcal{D} \).
  • Restituisci la migliore policy \( \hat{\pi}_i \) sulla base della validazione.

Questo approccio consente di ottenere una policy deterministica stazionaria con buone prestazioni sulla distribuzione di stati effettivamente indotta dal modello. Tuttavia, presenta una limitazione pratica importante: l’intervento costante dell’esperto umano, che deve supervisionare le traiettorie e fornire le azioni corrette a ogni iterazione.

Reward Learning

Nel reward learning, l’obiettivo è ricostruire la funzione di ricompensa che motiva le scelte di un esperto osservando il suo comportamento. In questo scenario si parte da un modello dell’ambiente che include lo state space, l’action space e il modello di transizione \( P(s' \mid s, a) \), ma senza conoscere la funzione di ricompensa \( R \).

Si dispone di una o più dimostrazioni dell’esperto, rappresentate da sequenze di stati e azioni \( (s_0, a_0, s_1, a_1, s_2, \ldots) \), in cui ogni azione \( a_t \) è campionata dalla policy dell’esperto \( \pi^* \).

L’obiettivo è quindi inferire la funzione di ricompensa \( R \) che spiega il comportamento osservato, assumendo che la policy dell’esperto sia ottimale rispetto a tale funzione. In altre parole, si ipotizza che l’esperto agisca sempre per massimizzare il ritorno atteso derivante dalle proprie azioni.

Nell’Inverse Reinforcement Learning (IRL) con feature lineari, si assume che la funzione di ricompensa possa essere espressa come una combinazione lineare di caratteristiche dello stato. In particolare, si definisce:

\( R(s) = \mathbf{w}^T \mathbf{x}(s) \),

dove \( \mathbf{w} \in \mathbb{R}^n \) rappresenta un vettore di pesi da stimare e \( \mathbf{x}: S \to \mathbb{R}^n \) è un vettore di funzioni di caratteristiche (feature) che descrivono ciascuno stato.

L’obiettivo dell’IRL è quindi quello di determinare il vettore dei pesi \( \mathbf{w} \) a partire da un insieme di dimostrazioni dell’esperto, in modo tale che il comportamento indotto dalla funzione di ricompensa lineare approssimi quello osservato.

In questo contesto, la funzione di valore di una policy \( \pi \) può essere espressa come:

\( V^{\pi}(s_0) = \mathbb{E}_{s \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t) \mid s_0 \right] = \mathbb{E}_{s \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t \mathbf{w}^T \mathbf{x}(s_t) \mid s_0 \right] \)

Poiché \( \mathbf{w} \) è costante, può essere estratto dall’atteso:

\( V^{\pi}(s_0) = \mathbf{w}^T \mathbb{E}_{s \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t \mathbf{x}(s_t) \mid s_0 \right] = \mathbf{w}^T \boldsymbol{\mu}(\pi) \)

dove \( \boldsymbol{\mu}(\pi) \) rappresenta la frequenza ponderata scontata delle feature di stato sotto la policy \( \pi \), partendo dallo stato iniziale \( s_0 \). In pratica, questa quantità misura quanto spesso — e con quale peso temporale — la policy visita stati con determinate caratteristiche.

Poiché la policy ottimale \( \pi^* \) massimizza il valore atteso della funzione di ricompensa, deve valere la disuguaglianza:

\( \mathbb{E}_{s \sim \pi^*} \left[ \sum_{t=0}^{\infty} \gamma^t R^*(s_t) \right] = V^* \geq V^{\pi} = \mathbb{E}_{s \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t R^*(s_t) \right] \quad \forall \pi \).

Da ciò segue che, per identificare il vettore dei pesi ottimale \( \mathbf{w}^* \) coerente con il comportamento dell’esperto, è sufficiente imporre la seguente condizione di ottimalità:

\( \mathbf{w}^{*T} \boldsymbol{\mu}(\pi^*) \geq \mathbf{w}^{*T} \boldsymbol{\mu}(\pi), \quad \forall \pi \neq \pi^* \).

Questa relazione stabilisce che il prodotto scalare tra \( \mathbf{w}^* \) e la distribuzione delle feature indotta dalla policy esperta deve essere maggiore (o uguale) rispetto a qualsiasi altra policy. In questo modo, il comportamento osservato viene interpretato come il risultato di un processo decisionale ottimale rispetto a una funzione di ricompensa implicita appresa dai dati.

Una policy \( \pi \) può essere garantita come equivalente o non peggiore della policy esperta \( \pi^* \) se le sue feature expectations scontate risultano simili a quelle dell’esperto. Questa condizione si può formalizzare come segue: se

\( \| \boldsymbol{\mu}(\pi) - \boldsymbol{\mu}(\pi^*) \|_1 \leq \epsilon \),

allora, per ogni vettore dei pesi \( \mathbf{w} \) tale che \( \| \mathbf{w} \|_\infty \leq 1 \), risulta che

\( | \mathbf{w}^T \boldsymbol{\mu}(\pi) - \mathbf{w}^T \boldsymbol{\mu}(\pi^*) | \leq \epsilon \).

Questa disuguaglianza  garantisce che, se le distribuzioni delle feature visitate dalle due policy sono sufficientemente vicine, anche le rispettive ricompense attese saranno simili entro un margine controllato \( \epsilon \). In altri termini, far corrispondere le aspettative delle feature tra la policy appresa e quella esperta è sufficiente per assicurare un comportamento quasi ottimale.

Max Entropy Inverse RL

Il Principio di Massima Entropia applicato all’Inverse Reinforcement Learning (IRL) stabilisce che, tra tutte le distribuzioni di probabilità compatibili con i dati osservati, la più appropriata è quella che massimizza l’entropia. In altre parole, la distribuzione con la maggiore entropia rappresenta lo stato di conoscenza meno arbitrario possibile, dato ciò che si sa dai dati empirici.

Ricordando che l’entropia di una distribuzione \( \rho(s) \) è definita come:

\( H(\rho) = - \sum_{s'} \rho(s') \log \rho(s') \),

il principio di massima entropia suggerisce di considerare tutte le distribuzioni di probabilità \( P(\tau) \) compatibili con i dati osservati e di selezionare quella che massimizza l’entropia, rispettando però i vincoli imposti dalle traiettorie esperte.

Nel caso di una ricompensa lineare, si cercano i pesi \( \mathbf{w} \) che producono una policy con la massima entropia soggetta al vincolo di uguaglianza tra le aspettative delle feature osservate e quelle stimate:

\(\displaystyle \max_{P} - \sum_{\tau} P(\tau) \log P(\tau) \quad \text{dati} \quad \sum_{\tau} P(\tau) \boldsymbol{\mu}(\tau) = \frac{1}{|\mathcal{D}|} \sum_{i \in \mathcal{D}} \boldsymbol{\mu}(\tau_i), \quad \sum_{\tau} P(\tau) = 1 \)

dove \( \boldsymbol{\mu}(\tau) \) rappresenta le feature associate a una traiettoria \( \tau \) e \( \mathcal{D} \) è il dataset delle traiettorie dimostrate dall’esperto.

Nel quadro dell’Inverse Reinforcement Learning basato sul principio di massima entropia, l’obiettivo generale è trovare una policy \( \pi \) che induca una distribuzione sulle traiettorie \( p(\tau) \) tale da ottenere la stessa ricompensa attesa delle dimostrazioni fornite dall’esperto \( \hat{P}(\tau) \), a partire da una funzione di ricompensa parametrizzata \( r_{\phi} \).

Il problema di ottimizzazione si esprime come:

\( \max_{p(\tau)} - \sum_{\tau} p(\tau) \log p(\tau) \quad \text{s.t.} \quad \sum_{\tau} p(\tau) r_{\phi}(\tau) = \sum_{\tau} \hat{P}(\tau) r_{\phi}(\tau), \quad \sum_{\tau} p(\tau) = 1 \)

In pratica, il processo di apprendimento alterna due fasi principali:

• calcolare una funzione di ricompensa \( r_{\phi} \) che spieghi le traiettorie osservate,
• utilizzare tale funzione per apprendere una policy ottimale, aggiornando di conseguenza le frequenze di traiettorie e stati per migliorare progressivamente la stima della funzione di ricompensa.

È importante notare che, nel modello originario di Maximum Entropy Inverse Reinforcement Learning, si assumeva di conoscere esattamente la dinamica dell’ambiente e la struttura del modello di ricompensa. Ciò rendeva possibile formulare il problema in termini analitici precisi, garantendo che la distribuzione appresa fosse coerente con le dimostrazioni esperte e massimizzasse contemporaneamente l’entropia.

Data la formulazione del problema di Massima Entropia per l’Inverse Reinforcement Learning, possiamo derivare la forma analitica della distribuzione di probabilità sulle traiettorie \( p(\tau) \) quando conosciamo la funzione di costo (o di ricompensa).

Si considera il problema vincolato di massimizzazione secondo la lagrangiana

\( \mathcal{L}(p, \lambda) = \sum_{\tau} p(\tau) \log p(\tau) + \lambda_1 \left( \sum_{\tau} \hat{P}(\tau) r_{\phi}(\tau) - \sum_{\tau} p(\tau) r_{\phi}(\tau) \right) + \lambda_0 \left( \sum_{\tau} p(\tau) - 1 \right) \)

Derivando rispetto a \( p(\tau) \) e ponendo la derivata pari a zero:

\( \frac{\partial \mathcal{L}}{\partial p(\tau)} = \log p(\tau) + 1 - \lambda_1 r_{\phi}(\tau) + \lambda_0 = 0 \)

da cui segue che:

\( \log p(\tau) = -1 + \lambda_1 r_{\phi}(\tau) - \lambda_0 \Rightarrow p(\tau) = e^{-1 - \lambda_0} \, e^{\lambda_1 r_{\phi}(\tau)} \)

\( p(\tau) \propto e^{r_{\phi}(\tau)} \)

Questa relazione mostra che, sotto il principio di massima entropia, la probabilità di una traiettoria cresce esponenzialmente con la sua ricompensa cumulata: traiettorie con ricompense più alte sono più probabili, ma senza eliminare del tutto la possibilità di traiettorie meno ottimali, preservando così l’esplorazione e l’incertezza del modello.

Il principio di Massima Entropia stabilisce che massimizzare l’entropia di una distribuzione sulle traiettorie \( \tau \) equivale a massimizzare la verosimiglianza dei dati osservati sotto una distribuzione appartenente alla famiglia esponenziale .

La distribuzione sulle traiettorie può essere scritta come:

\( p(\tau_i \mid \phi) = \frac{1}{Z(\phi)} e^{r_{\phi}(\tau_i)} \)

dove \( Z(\phi) \) è il termine di normalizzazione (partizione) definito come:

\( Z(\phi) = \sum_{\tau} e^{r_{\phi}(\tau)} \)

oppure, in forma più esplicita, considerando che una traiettoria è composta da una sequenza di stati:

\( p(\tau_i \mid \phi) = \frac{1}{Z(\phi)} e^{\sum_{s_i \in \tau_i} r_{\phi}(s_i)} \)

Poiché la funzione di ricompensa \( r_{\phi} \) non è nota, l’idea è di stimarla dai dati osservati. L’osservazione chiave è che la distribuzione che massimizza l’entropia assume la forma di una distribuzione esponenziale normalizzata, il che permette di trasformare il problema di inferenza della funzione di ricompensa in un problema di massimizzazione della probabilità dei dati osservati sotto tale distribuzione.

In sintesi, possiamo ora stimare o apprendere \( r_{\phi} \) massimizzando la probabilità delle traiettorie esperte, ossia cercando i parametri \( \phi \) che rendono più probabili i comportamenti osservati all’interno della distribuzione di massima entropia.

Nel contesto dell’Inverse Reinforcement Learning con il principio di Massima Entropia, l’obiettivo è massimizzare, rispetto ai parametri della funzione di ricompensa \( r_{\phi} \), la verosimiglianza dei dati osservati (ovvero delle traiettorie esperte) sotto la distribuzione esponenziale di massima entropia.

La funzione di ottimizzazione è:

\( \max_{\phi} \log \prod_{\tau^* \in \mathcal{D}} p(\tau^*) = \max_{\phi} \sum_{\tau^* \in \mathcal{D}} \log p(\tau^*) \)

Sostituendo la distribuzione esponenziale normalizzata:

\( p(\tau) = \frac{e^{r_{\phi}(\tau)}}{\sum_{\tau'} e^{r_{\phi}(\tau')}} \)

si ottiene:

\( \mathcal{J}(\phi) = \sum_{\tau^* \in \mathcal{D}} r_{\phi}(\tau^*) - |\mathcal{D}| \log \sum_{\tau} e^{r_{\phi}(\tau)} \)

Derivando rispetto a \( \phi \), il gradiente della funzione di log-verosimiglianza è:

\( \nabla_{\phi} \mathcal{J}(\phi) = \sum_{\tau^* \in \mathcal{D}} \frac{\partial r_{\phi}(\tau^*)}{\partial \phi} - |\mathcal{D}| \sum_{\tau} p(\tau \mid \phi) \frac{\partial r_{\phi}(\tau)}{\partial \phi} \)

Il termine \( p(\tau \mid \phi) = \frac{e^{r_{\phi}(\tau)}}{Z(\phi)} \) rappresenta la probabilità della traiettoria sotto la distribuzione di massima entropia.

In forma intuitiva, questo gradiente misura la differenza tra:

• la ricompensa media osservata nei dati esperti, e
• la ricompensa media attesa secondo la distribuzione indotta dal modello corrente.

La formulazione della Massima Entropia nell’Inverse Reinforcement Learning può essere riscritta passando dalle traiettorie complete agli stati individuali, semplificando il calcolo del gradiente.

Partendo dalla probabilità di una traiettoria:

\( p(\tau) = \rho(s_1) \prod_{t=1}^{T} p(a_t \mid s_t) \, p(s_{t+1} \mid s_t, a_t) \)

e ricordando che nella formulazione a massima entropia la probabilità è proporzionale all’esponenziale della ricompensa cumulata, si ottiene:

\( p(\tau) \propto e^{-r_{\phi}(\tau)} = e^{-\sum_{s \in \tau} r_{\phi}(s)} \)

In questo modo, il contributo della ricompensa può essere espresso come somma sui singoli stati visitati, anziché sull’intera traiettoria.

Il gradiente della funzione obiettivo rispetto ai parametri \( \theta \) (che definiscono la funzione di ricompensa) diventa quindi:

\( \nabla_{\theta} \mathcal{J}(\theta) = \sum_{s \in \tau^* \in \mathcal{D}} \frac{\partial r_{\phi}(s)}{\partial \theta} - |\mathcal{D}| \sum_{s} p(s \mid \theta, \gamma) \frac{\partial r_{\phi}(s)}{\partial \theta} \)

Questa espressione riflette la differenza tra:

• la frequenza (ponderata) degli stati visitati dagli esperti, e
• la frequenza degli stessi stati stimata sotto la policy indotta dal modello corrente.

In pratica, l’algoritmo aggiorna i parametri della ricompensa per aumentare la probabilità degli stati osservati nelle dimostrazioni esperte e ridurla per quelli generati dal modello, avvicinando così la distribuzione appresa a quella dell’esperto.

Quando la dinamica dell’ambiente è nota e la policy \( \pi \) è fissata, è possibile esprimere il comportamento dell’agente in termini di densità di stati anziché di traiettorie.

Si definisce la densità di occupazione degli stati come:

\( \mu_t(s) = p(s_t = s) \)

che rappresenta la probabilità di trovarsi nello stato \( s \) al tempo \( t \).

Per ogni passo temporale, la densità si aggiorna in base alla dinamica di transizione e alla policy:

\( \mu_{t+1}(s') = \sum_{a} \sum_{s} \mu_t(s) \, p(a \mid s) \, p(s' \mid s, a) \)

La distribuzione complessiva degli stati, integrata su tutti i tempi della traiettoria, è:

\( p(s \mid \phi, \mathcal{T}) = \sum_{t} \mu_t(s) \)

Il gradiente della funzione obiettivo rispetto ai parametri \( \phi \) della funzione di ricompensa è quindi:

\( \nabla_{\phi} \mathcal{J}(\phi) = \sum_{s \in \tau^* \in \mathcal{D}} \frac{\partial r_{\phi}(s)}{\partial \phi} - |\mathcal{D}| \sum_{s} p(s \mid \phi, \mathcal{T}) \frac{\partial r_{\phi}(s)}{\partial \phi} \)

Se la funzione di ricompensa è lineare nelle feature, ossia:

\( r_{\phi}(s) = \phi^{\top} f_s \)

allora la derivata rispetto ai parametri diventa semplicemente:

\( \frac{\partial r_{\phi}(s)}{\partial \phi} = f_s \)

Questo porta a una forma del gradiente che dipende direttamente dalla differenza tra le frequenze di visita degli stati esperti e quelle previste dal modello, pesate dalle rispettive feature. Tale formulazione costituisce la base dei metodi di Maximum Entropy Inverse Reinforcement Learning applicati con rappresentazioni lineari dello stato.

Il metodo di Maximum Entropy Inverse Reinforcement Learning assume di conoscere il modello dinamico dell’ambiente e che la funzione di ricompensa sia lineare nelle feature. Dato un insieme di dimostrazioni esperte \( \mathcal{D} \) e una ricompensa del tipo \( r_\phi(s) = \phi^\top f_s \), l’obiettivo è stimare i parametri \( \phi \) che rendono massima la probabilità delle traiettorie osservate.

• Input: dimostrazioni esperte \( \mathcal{D} \)
• Inizializza la funzione di ricompensa \( r_\phi \)
• Calcola la policy ottimale \( \pi(a \mid s) \) dato \( r_\phi \) (ad esempio tramite value iteration)
• Calcola le frequenze di visita degli stati \( p(s \mid \phi, \mathcal{T}) \)
• Calcola il gradiente della funzione obiettivo rispetto alla ricompensa:
  • \( \nabla_\phi \mathcal{J}(\phi) = \frac{1}{M} \sum_{\tau^* \in \mathcal{D}} \sum_{s \in \tau^*} f_s - \sum_s p(s \mid \phi, \mathcal{T}) f_s \)
• Aggiorna i parametri \( \phi \) con un passo di gradiente
• Ripeti dal passo 3 fino a convergenza

Questo schema di aggiornamento ottimizza la funzione di ricompensa in modo da ridurre la differenza tra le feature osservate nelle dimostrazioni esperte e quelle generate dal modello, garantendo che la policy imparata riproduca il comportamento esperto.

Limiti dell'approccio Policy Gradient

I metodi basati sul policy gradient cercano di risolvere un problema di ottimizzazione diretta della policy, ossia di trovare i parametri \( \theta \) che massimizzano il valore atteso cumulativo delle ricompense future:

\( \max_\theta J(\pi_\theta) \doteq \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \right] \)

Per risolvere questo problema, si applica l’ascesa stocastica del gradiente rispetto ai parametri della policy, utilizzando il gradiente di policy definito come:

\( g = \nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \gamma^t \nabla_\theta \log \pi_\theta(a_t|s_t) A^{\pi_\theta}(s_t, a_t) \right] \)

In questa formulazione, \( A^{\pi_\theta}(s_t, a_t) \) rappresenta la funzione di advantage, che misura quanto l’azione presa in uno stato è migliore o peggiore della media rispetto alla policy corrente.

Evidenziamo due limitazioni principali del metodo "vanilla" di Policy Gradient:

• Bassa efficienza del campionamento: per stimare accuratamente il gradiente è necessario raccogliere molte traiettorie di interazione con l’ambiente, rendendo il processo lento e costoso, con limitato riuso.
• Lo spazio dei parametri non coincide con lo spazio delle policy: piccoli cambiamenti nei parametri \( \theta \) possono corrispondere a variazioni molto grandi o molto piccole nel comportamento della policy. Nel caso tabulare, lo spazio delle policy può essere descritto come l’insieme di tutte le matrici di probabilità \( \Pi = \left\{ \pi : \pi \in \mathbb{R}^{|S| \times |A|}, \ \sum_a \pi_{sa} = 1, \ \pi_{sa} \ge 0 \right\} \).
  Poiché gli aggiornamenti vengono effettuati sui parametri \( \theta \) e non direttamente sulle probabilità, non è garantito che un piccolo passo in \( \theta \) corrisponda a una piccola variazione della policy. Ciò comporta che la dimensione del passo (learning rate) sia critica e difficile da regolare, poiché un valore troppo grande può far divergere la policy, mentre uno troppo piccolo rallenta drasticamente la convergenza.

Approfondendo il tema dell'efficienza nel campionamento (sample efficiency), rileviamo che nei metodi “vanilla”, infatti, ogni batch di dati raccolto viene utilizzato solo per un singolo aggiornamento del gradiente e poi scartato, il che comporta un notevole spreco di informazioni utili.

La ragione di questa limitazione è che il policy gradient è un’aspettativa on-policy: i campioni utilizzati per stimare il gradiente devono provenire dalla stessa policy che si sta attualmente aggiornando. Utilizzare dati provenienti da una policy differente con un approccio off-policy (meno stabile) introdurrebbe un bias nella stima.

Un’opportunità interessante per migliorare l’efficienza consiste nel riutilizzare i dati già raccolti per eseguire più passi di gradiente prima di aggiornare la policy e raccogliere nuovi campioni. In questo modo, ogni batch di dati contribuisce maggiormente all’apprendimento, riducendo il numero complessivo di interazioni necessarie con l’ambiente.

Tuttavia, ciò introduce una nuova sfida: anche se teoricamente è possibile usare più volte gli stessi dati, non è chiaro quanti passi di aggiornamento sia ottimale eseguire prima che la stima del gradiente diventi troppo incoerente rispetto alla policy corrente.

Negli algoritmi di ottimizzazione della policy, l’obiettivo è definire una regola di aggiornamento che sia il più efficiente possibile e che tenga conto della reale distanza tra le policy nello spazio delle policy, invece che nella semplice distanza dei parametri. Questo è importante perché piccole variazioni nei parametri della funzione che rappresenta la policy possono produrre grandi cambiamenti nel comportamento dell’agente.

Idealmente, vogliamo quindi un aggiornamento che:

• utilizzi in modo efficiente i rollouts raccolti dalla policy più recente;
• faccia passi di aggiornamento che rispettino la distanza nello spazio delle policy, garantendo una transizione stabile da una policy all’altra.

Performance delle Policy e ottimizzazione

Per determinare una regola di aggiornamento corretta, è necessario comprendere come la performance di due policy diverse sia correlata. Per due policy qualsiasi \( \pi \) e \( \pi' \), si può dimostrare che la differenza di performance può essere espressa come:

\( J(\pi') - J(\pi) = \mathbb{E}_{\tau \sim \pi'} \left[ \sum_{t=0}^{\infty} \gamma^t A^{\pi}(s_t, a_t) \right] \)

Questa equazione mostra che la differenza tra i rendimenti medi delle due policy dipende dal valore atteso dell’advantage function della policy originale \( \pi \), calcolato su traiettorie campionate dalla nuova policy \( \pi' \).

Una forma equivalente che è possibile dimostrare, più compatta, è:

\( J(\pi') - J(\pi) = \frac{1}{1-\gamma} \, \mathbb{E}_{s \sim d^{\pi'},\, a \sim \pi'} \left[ A^{\pi}(s, a) \right] \)

dove \( d^{\pi}(s) \) rappresenta la distribuzione stazionaria scontata degli stati sotto la policy \( \pi \), definita come:

\( d^{\pi}(s) = (1 - \gamma) \sum_{t=0}^{\infty} \gamma^t P(s_t = s \, | \, \pi) \)

In termini intuitivi, questo lemma afferma che per valutare quanto una nuova policy \( \pi' \) sia migliore o peggiore della precedente, è sufficiente osservare il vantaggio medio che le azioni scelte da \( \pi' \) producono rispetto alle azioni medie della policy di riferimento \( \pi \).

Possiamo chiederci come usare questa relazione per migliorare la policy. Supponiamo che \( \pi \) rappresenti la policy attuale e \( \pi' \) quella nuova che vogliamo ottimizzare. L’obiettivo dell’improvement è massimizzare il valore atteso della nuova policy:

\( \max_{\pi'} J(\pi') = \max_{\pi'} \, [ J(\pi') - J(\pi) ] \)  =  \( \max_{\pi'} \, \mathbb{E}_{\tau \sim \pi'} \left[ \sum_{t=0}^{\infty} \gamma^t A^{\pi}(s_t, a_t) \right] \)

Questa formulazione è interessante perché definisce il miglioramento della nuova policy \( \pi' \) in funzione degli advantage calcolati rispetto alla vecchia policy \( \pi \). In altre parole, ci permette di capire se e quanto la nuova policy supera la precedente, basandoci sul vantaggio medio delle sue azioni.

Tuttavia, questa espressione presenta un limite importante: per calcolare l’aspettativa dobbiamo comunque disporre di traiettorie campionate dalla nuova policy \( \pi' \), che ancora non conosciamo. Questo rende il metodo non immediatamente utilizzabile nella pratica.

Il problema quindi diventa: come stimare \( J(\pi') \) — cioè la performance della nuova policy — utilizzando solo i dati raccolti dalla policy precedente \( \pi \)?

Possiamo riscrivere l’identità che descrive la performance relativa tra due policy, evidenziando come la differenza tra le loro prestazioni possa essere stimata anche utilizzando i campioni provenienti dalla policy originale. Possiamo riscrivere questa espressione come:

\( J(\pi') - J(\pi) = \frac{1}{1 - \gamma} \, \mathbb{E}_{s \sim d^{\pi'}, \, a \sim \pi'} \left[ A^{\pi}(s, a) \right] \)

Dove \( d^{\pi'}(s) \) è la distribuzione stazionaria scontata degli stati secondo la nuova policy \( \pi' \).

Tuttavia, questa formulazione richiede ancora campioni generati da \( \pi' \). Per superare questo vincolo, possiamo introdurre un cambio di misura di probabilità che ci consente di esprimere l’aspettativa in termini della policy precedente \( \pi \). Questo porta alla forma:

\( J(\pi') - J(\pi) = \frac{1}{1 - \gamma} \, \mathbb{E}_{s \sim d^{\pi'}, \, a \sim \pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} \, A^{\pi}(s, a) \right] \)

Il termine in rosso, \( \frac{\pi'(a|s)}{\pi(a|s)} \), è noto come importance sampling ratio e permette di “correggere” la distribuzione dei campioni, pesandoli in base a quanto la nuova policy differisce da quella precedente.

Questo passaggio è fondamentale, perché consente di stimare la differenza di performance tra due policy diverse utilizzando solo i dati raccolti dalla vecchia policy \( \pi \), evitando la necessità di eseguire nuovi rollouts ogni volta che la policy viene aggiornata. 
Per semplificare il calcolo della differenza di performance tra due policy \( \pi \) e \( \pi' \), possiamo fare una approssimazione utile assumendo che le rispettive distribuzioni stazionarie degli stati siano simili,  ovvero \( d^{\pi'} \approx d^{\pi} \)  .

Sotto questa ipotesi, possiamo riscrivere l’identità della performance relativa come:

\( J(\pi') - J(\pi) \approx \frac{1}{1-\gamma} \, \mathbb{E}_{s \sim d^{\pi},\, a \sim \pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} A^{\pi}(s, a) \right] \doteq \mathcal{L}_{\pi}(\pi') \)

Questa approssimazione è in genere valida quando le due policy sono “abbastanza vicine” — cioè quando \( \pi' \) non differisce troppo da \( \pi \). La vicinanza tra policy può essere quantificata attraverso la divergenza di Kullback–Leibler (KL-divergence). Infatti, i limiti di performance relativi mostrano che:

\( \big| J(\pi') - (J(\pi) + \mathcal{L}_{\pi}(\pi')) \big| \le C \sqrt{ \mathbb{E}_{s \sim d^{\pi'}} \left[ D_{KL}(\pi' \| \pi)[s] \right] } \)

Dove \( C \) è una costante di proporzionalità. In altre parole, se la divergenza KL tra le due policy è piccola, l’approssimazione è molto accurata.

La divergenza di Kullback–Leibler misura quanto una distribuzione di probabilità \( P \) differisce da un’altra \( Q \) ed è definita come:

\( D_{KL}(P \| Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)} \)

Ha alcune proprietà fondamentali:

• \( D_{KL}(P \| P) = 0 \)
• \( D_{KL}(P \| Q) \ge 0 \)
• Non è simmetrica: \( D_{KL}(P \| Q) \neq D_{KL}(Q \| P) \)

Nel contesto delle policy, la KL-divergence misura la differenza tra due distribuzioni di azioni condizionate dallo stato:

\( D_{KL}(\pi' \| \pi)[s] = \sum_{a \in A} \pi'(a|s) \log \frac{\pi'(a|s)}{\pi(a|s)} \)

Più questo valore è piccolo, più le due policy si comportano in modo simile nello stesso stato.

Perché questa approssimazione è utile

Grazie all’assunzione \( d^{\pi'} \approx d^{\pi} \), possiamo stimare il miglioramento della policy \( \pi' \) utilizzando solo traiettorie raccolte dalla policy precedente \( \pi \). Ciò consente di ottimizzare \( \mathcal{L}_{\pi}(\pi') \) senza dover eseguire nuovi rollouts a ogni aggiornamento.

\( \mathcal{L}_{\pi}(\pi') = \frac{1}{1-\gamma} \, \mathbb{E}_{s \sim d^{\pi},\, a \sim \pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} A^{\pi}(s, a) \right] \)

Questo equivale a stimare il gradiente della policy usando l’importance sampling, ma con pesi che dipendono solo dalle probabilità relative tra \( \pi' \) e \( \pi \). Poiché questi pesi non dipendono dalla lunghezza della traiettoria, l’approccio rimane stabile e computazionalmente efficiente.

L’approssimazione \( J(\pi') - J(\pi) \approx \mathcal{L}_{\pi}(\pi') \) consente di riscrivere la differenza di performance tra due policy come una funzione ottimizzabile utilizzando i dati raccolti dalla policy precedente \( \pi \).

In particolare, si definisce:

\( \mathcal{L}_{\pi}(\pi') = \frac{1}{1 - \gamma} \mathbb{E}_{s \sim d^{\pi},\, a \sim \pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} A^{\pi}(s, a) \right] = \mathbb{E}_{\tau \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t \frac{\pi'(a_t|s_t)}{\pi(a_t|s_t)} A^{\pi}(s_t, a_t) \right] \)

Questa formulazione presenta un vantaggio pratico: possiamo ottimizzare la nuova policy \( \pi' \) sfruttando le traiettorie già campionate dalla policy precedente \( \pi \), senza dover generare nuovi dati a ogni iterazione.

 

PPO con Adaptive KL Penalty

La Proximal Policy Optimization (PPO) è una famiglia di metodi che mira a evitare che la policy aggiornata si discosti troppo da quella precedente in ogni iterazione di training. L’idea di fondo è quella di penalizzare gli aggiornamenti eccessivi, mantenendo la stabilità dell’apprendimento e al contempo migliorando la performance.

Una delle varianti principali è la Adaptive KL Penalty, che introduce una penalizzazione adattiva basata sulla divergenza di Kullback–Leibler (KL) tra la nuova policy e quella precedente. In questo caso, l’aggiornamento dei parametri della policy è ottenuto risolvendo il seguente problema di ottimizzazione non vincolato:

\( \theta_{k+1} = \arg\max_{\theta} \, \mathcal{L}_{\theta_k}(\theta) - \beta_k \, \bar{D}_{\mathrm{KL}}(\theta \| \theta_k) \)

dove

\( \bar{D}_{\mathrm{KL}}(\theta \| \theta_k) = \mathbb{E}_{s \sim d^{\pi_k}} \left[ D_{\mathrm{KL}}\big(\pi_{\theta_k}(\cdot|s), \pi_{\theta}(\cdot|s)\big) \right]. \)

Il termine \(\beta_k\) è un coefficiente di penalità che si adatta dinamicamente tra le iterazioni per regolare quanto fortemente la nuova policy deve rimanere vicina alla precedente, in modo da rispettare un vincolo approssimato sulla divergenza KL. Questo meccanismo consente di bilanciare stabilità e velocità di apprendimento durante l’ottimizzazione della policy.

L’algoritmo PPO con penalità adattiva KL regola dinamicamente la distanza consentita tra la policy corrente e quella aggiornata, mantenendo l’ottimizzazione stabile. Il processo si articola come segue:

• Input: parametri iniziali della policy \( \theta_0 \), penalità KL iniziale \( \beta_0 \), divergenza KL target \( \delta \)
• Per ogni iterazione \( k = 0, 1, 2, \dots \):
  • Raccogliere un set di traiettorie parziali \( \mathcal{D}_k \) secondo la policy corrente \( \pi_k = \pi(\theta_k) \)
  • Stimare i vantaggi \( \hat{A}_t^{\pi_k} \) usando un algoritmo di stima dei vantaggi
  • Aggiornare la policy risolvendo:
    \( \theta_{k+1} = \arg\max_{\theta} \mathcal{L}_{\theta_k}(\theta) - \beta_k \, \bar{D}_{\mathrm{KL}}(\theta \| \theta_k) \)
    mediante K passi di mini-batch SGD (ad esempio con Adam)
  • Adattare la penalità KL:
    • Se \( \bar{D}_{\mathrm{KL}}(\theta_{k+1} \| \theta_k) \ge 1.5 \delta \), allora \( \beta_{k+1} = 2 \beta_k \)
    • Se \( \bar{D}_{\mathrm{KL}}(\theta_{k+1} \| \theta_k) \le \delta / 1.5 \), allora \( \beta_{k+1} = \beta_k / 2 \)

Questo approccio consente alla penalità KL di adattarsi rapidamente al comportamento della policy, senza richiedere un valore iniziale particolarmente preciso. Anche se alcune iterazioni possono violare temporaneamente il vincolo di divergenza KL, la maggior parte delle iterazioni resta entro i limiti, garantendo stabilità e miglioramento progressivo della policy.

PPO con Clipped Objective

La seconda variante di Proximal Policy Optimization (PPO) è nota come Clipped Objective, ed è stata introdotta per limitare direttamente l’entità dell’aggiornamento della policy senza richiedere un termine di penalità esplicito.

L’idea centrale è definire un rapporto di probabilità tra la nuova e la vecchia policy:

\( r_t(\theta) = \frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_k}(a_t|s_t)} \)

A partire da questo rapporto, la nuova funzione obiettivo è definita come:

\( \mathcal{L}_{\theta_k}^{\text{CLIP}}(\theta) = \mathbb{E}_{\tau \sim \pi_k} \left[ \sum_{t=0}^{T} \min \left( r_t(\theta) \, \hat{A}_t^{\pi_k}, \, \text{clip}(r_t(\theta), 1 - \epsilon, 1 + \epsilon) \, \hat{A}_t^{\pi_k} \right) \right] \)

dove \(\epsilon\) è un iperparametro (tipicamente \(\epsilon = 0.2\)) che controlla quanto la nuova policy può differire dalla precedente. La funzione clip taglia i valori di \(r_t(\theta)\) al di fuori dell’intervallo \([1 - \epsilon, 1 + \epsilon]\), impedendo grandi variazioni nella probabilità delle azioni e garantendo stabilità.

In questo modo, PPO favorisce miglioramenti “prossimali”: la policy può evolvere verso azioni migliori, ma non troppo rapidamente, evitando così instabilità e oscillazioni. L’aggiornamento dei parametri avviene quindi massimizzando:

\( \theta_{k+1} = \arg\max_{\theta} \, \mathcal{L}_{\theta_k}^{\text{CLIP}}(\theta) \)

Questa formulazione ha il vantaggio di mantenere la semplicità computazionale e la stabilità del metodo, eliminando la necessità di regolare dinamicamente un termine di penalità, come avviene nella variante con KL adattiva.

Il grafico a sinistra mostra \(\mathcal{L}^{\text{CLIP}}\) quando la funzione di vantaggio A>0  e il grafico sulla destra quando A<0:

Il meccanismo di clipping nel PPO serve a mantenere la nuova policy vicina a quella precedente, rendendo la funzione obiettivo più “pessimistica” rispetto alle performance ottenute quando la nuova policy si allontana troppo dai parametri originali \( \theta_k \).

In altre parole, il clipping limita l’effetto delle variazioni eccessive di \( r_t(\theta) = \pi_{\theta}(a_t|s_t)/\pi_{\theta_k}(a_t|s_t) \) sulla funzione di vantaggio \( \hat{A}_t \). Quando l’aggiornamento della policy produce un valore di \( r_t(\theta) \) troppo grande o troppo piccolo, la funzione obiettivo viene “tagliata” (clipped), riducendo il contributo positivo al gradiente e scoraggiando aggiornamenti troppo aggressivi.

Il grafico riportato mostra il confronto tra diverse funzioni obiettivo in funzione del fattore di interpolazione lineare \( \alpha \) tra i parametri \( \theta_{k+1} \) e \( \theta_k \) dopo un aggiornamento con PPO-Clip:

• \( \hat{\mathbb{E}}_t[\mathrm{KL}_t] \): rappresenta la divergenza KL tra le policy.
• \( L^{\mathrm{CPI}} = \hat{\mathbb{E}}_t[r_t A_t] \): l’obiettivo del classico policy gradient.
• \( \hat{\mathbb{E}}_t[\text{clip}(r_t, 1 - \epsilon, 1 + \epsilon)A_t] \): la versione con valori tagliati (clipped).
• \( L^{\mathrm{CLIP}} = \hat{\mathbb{E}}_t[\min(r_t A_t, \text{clip}(r_t, 1 - \epsilon, 1 + \epsilon)A_t)] \): l’obiettivo finale usato da PPO.

Dal confronto emerge che \( L^{\mathrm{CLIP}} \) cresce più lentamente e si appiattisce rispetto a \( L^{\mathrm{CPI}} \) quando la policy si allontana, garantendo così una maggiore stabilità e impedendo aggiornamenti eccessivi che potrebbero compromettere la performance complessiva.

In sintesi, il clipping introduce un controllo automatico sulla magnitudine degli aggiornamenti della policy, rendendo l’ottimizzazione più stabile e prevenendo la divergenza del modello.

L’algoritmo PPO con Clipped Objective rappresenta una delle versioni più efficaci e semplici del Proximal Policy Optimization. A differenza della variante con penalità KL, questo metodo controlla implicitamente la distanza tra le policy successive attraverso il meccanismo di “clipping” applicato alla funzione obiettivo.

• Input: parametri iniziali della policy \( \theta_0 \), soglia di clipping \( \epsilon \)
• Per ogni iterazione \( k = 0, 1, 2, \dots \):
  • Raccogliere un insieme di traiettorie parziali \( \mathcal{D}_k \) eseguendo la policy \( \pi_k = \pi(\theta_k) \)
  • Stimare i vantaggi \( \hat{A}_t^{\pi_k} \) usando un algoritmo di stima appropriato
  • Aggiornare la policy risolvendo:
    \( \theta_{k+1} = \arg\max_{\theta} \mathcal{L}_{\theta_k}^{\text{CLIP}}(\theta) \)
    attraverso K passi di mini-batch SGD (ad esempio con l’ottimizzatore Adam)
  • La funzione obiettivo è definita come:
    \( \mathcal{L}_{\theta_k}^{\text{CLIP}}(\theta) = \mathbb{E}_{\tau \sim \pi_k} \left[ \sum_{t=0}^{T} \min \left( r_t(\theta) \hat{A}_t^{\pi_k}, \text{clip}(r_t(\theta), 1 - \epsilon, 1 + \epsilon)\hat{A}_t^{\pi_k} \right) \right] \)

Il termine di clipping evita che la nuova policy si discosti troppo da quella precedente \( \pi_k \), impedendo aggiornamenti eccessivi che potrebbero portare a una perdita di stabilità o a un peggioramento delle prestazioni.

In pratica:

• Il clipping riduce l’incentivo della policy a compiere grandi variazioni nei parametri tra un aggiornamento e l’altro.
• Le performance risultano comparabili, se non migliori, rispetto alla variante con penalità KL, pur mantenendo una implementazione più semplice e robusta.

Generalized Advantage Estimator (GAE)

Per introdurre quello è che l'Advantage estimator utilizzato nel PPO, è utile partire dai cosiddetti N-step advantage estimators, che rappresentano un modo per stimare il vantaggio di una determinata azione tenendo conto di un numero variabile di passi futuri.

Consideriamo inizialmente la definizione di vantaggio a un passo:

\( \hat{A}^{(1)}_t = r_t + \gamma V(s_{t+1}) - V(s_t) \)

Questa espressione misura quanto la ricompensa immediata e il valore previsto del prossimo stato superino (o meno) il valore dello stato attuale.  Possiamo migliorarla includendo più passi futuri:

\( \hat{A}^{(2)}_t = r_t + \gamma r_{t+1} + \gamma^2 V(s_{t+2}) - V(s_t) \)

e, più in generale, per un orizzonte infinito:

\( \hat{A}^{(\infty)}_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots - V(s_t) \)

Definiamo ora un termine più compatto per rappresentare la differenza temporale corretta dal valore, noto come errore di vantaggio a un passo:

\( \delta_t^V = r_t + \gamma V(s_{t+1}) - V(s_t) \)

Con questa notazione, possiamo riscrivere i vantaggi a più passi come somme pesate di questi termini:

• \( \hat{A}^{(1)}_t = \delta_t^V \)
• \( \hat{A}^{(2)}_t = \delta_t^V + \gamma \delta_{t+1}^V \)
• In generale: \( \hat{A}^{(k)}_t = \sum_{l=0}^{k-1} \gamma^l \delta_{t+l}^V \)

Questa formulazione evidenzia come ciascun termine derivi da una somma telescopica, cioè una sequenza in cui molti termini intermedi si cancellano, lasciando una forma compatta e facilmente computabile. È proprio da questa struttura che il GAE deriva, introducendo un ulteriore fattore di pesatura esponenziale per controllare il compromesso tra bias e varianza nella stima del vantaggio.

Partendo dal vantaggio a \(k\) passi definito come:

\( \hat{A}^{(k)}_t = \sum_{l=0}^{k-1} \gamma^l r_{t+l} + \gamma^k V(s_{t+k}) - V(s_t) \)

il GAE viene definito come una media esponenzialmente pesata di questi stimatori a più passi:

\( \hat{A}^{\text{GAE}(\gamma, \lambda)}_t = (1 - \lambda) \left( \hat{A}^{(1)}_t + \lambda \hat{A}^{(2)}_t + \lambda^2 \hat{A}^{(3)}_t + \dots \right) \)

Sostituendo la definizione di A in termini di differenze temporali  \( \delta^V_t = r_t + \gamma V(s_{t+1}) - V(s_t) \) , si ottiene una forma più compatta:

\( \hat{A}^{\text{GAE}(\gamma, \lambda)}_t = \sum_{l=0}^{\infty} (\gamma \lambda)^l \, \delta^V_{t+l} \)

Il risultato è un vantaggio che combina i termini futuri con un peso esponenzialmente decrescente, dove il parametro \( \lambda \in [0,1] \) controlla la velocità di decadimento: valori piccoli di  lambda privilegiano le ricompense immediate (riducendo la varianza ma introducendo più bias), mentre valori prossimi a 1 tengono conto di orizzonti più lunghi (riducendo il bias ma aumentando la varianza).

In sostanza, il GAE realizza una somma geometrica delle differenze temporali successive, costruendo una stima del vantaggio che è più stabile e più efficiente per l’ottimizzazione della policy rispetto ai metodi tradizionali a passo singolo o multi-step.

PPO utilizza una versione troncata di GAE,  \(\displaystyle \hat{A}_t=\sum_{l=0}^{T-t-1}(\gamma \lambda)^l \delta^V_{t+l}\) , che prevede quindi di eseugire la policy solo per T timestep prima di aggiornare la stima del gradiente.

Crescita Monotonica del PPO

Come abbiamo visto la differenza di performance tra due policy può essere approssimata usando la distribuzione di visita degli stati della policy corrente. In particolare, vale  \( \mathcal{L}_{\pi}(\pi') \), ottenuta assumendo \( d^{\pi'} \approx d^{\pi} \). La bontà di questa approssimazione è garantita quando le due policy sono “vicine” in divergenza di Kullback–Leibler: abbiamo infatti già visto il bound di prestazione relativa

\( \big|\, J(\pi') - \big(J(\pi)+\mathcal{L}_{\pi}(\pi')\big) \,\big| \;\le\; C \sqrt{ \mathbb{E}_{s\sim d^{\pi'}}\!\left[ D_{\mathrm{KL}}\!\left(\pi'\,\|\,\pi\right)[s]\right] }\, . \)

Da questo segue un vincolo inferiore (miglioramento monotono approssimato):

\( J(\pi') - J(\pi) \;\ge\; \mathcal{L}_{\pi}(\pi') \;-\; C \sqrt{ \mathbb{E}_{s\sim d^{\pi'}}\!\left[ D_{\mathrm{KL}}\!\left(\pi'\,\|\,\pi\right)[s]\right] } \, . \)

Da ciò  vediamo che se massimizziamo il lato destro rispetto a \( \pi' \), otteniamo un aggiornamento di policy che garantisce miglioramento rispetto a \( \pi \) (finché la divergenza KL resta piccola). Sia \( \mathcal{L}_{\pi}(\pi') \) sia il termine KL si possono stimare con traiettorie campionate dalla policy corrente \( \pi \).

 

La garanzia di miglioramento monotono si basa sul fatto che, a ogni iterazione, la nuova policy \( \pi_{k+1} \) è ottenuta massimizzando un obiettivo surrogato penalizzato:

\( \pi_{k+1} = \arg\max_{\pi'} \left[\, \mathcal{L}_{\pi_k}(\pi') - C \sqrt{ \mathbb{E}_{s \sim d^{\pi_k}} \!\left[ D_{\mathrm{KL}}(\pi' \| \pi_k)[s] \right] } \,\right]. \)

Poiché la policy corrente \( \pi_k \) è un punto ammissibile del dominio di ottimizzazione, possiamo verificare che:

• La funzione surrogata ha valore nullo nel punto corrente: \( \mathcal{L}_{\pi_k}(\pi_k) \propto \mathbb{E}_{s,a \sim d^{\pi_k},\,\pi_k}[A^{\pi_k}(s,a)] = 0. \)
• La penalità di divergenza è anch’essa nulla: \( D_{\mathrm{KL}}(\pi_k \| \pi_k)[s] = 0. \)

Ne consegue che il valore ottimo della funzione obiettivo (ottenuto per \( \pi_{k+1} \)) non può essere inferiore a quello calcolato in \( \pi_k \), cioè:

\( \text{valore ottimo} \ge 0 \;\;\Rightarrow\;\; J(\pi_{k+1}) - J(\pi_k) \ge 0. \)

In altre parole, a ogni passo di aggiornamento la performance della policy non peggiora. Questa dimostrazione resta valida anche se si restringe il dominio di ottimizzazione a una famiglia parametrica di policy \( \Pi_{\theta} \), purché \( \pi_k \in \Pi_{\theta} \).

L’aggiornamento della policy può essere definito come la massimizzazione dell’obiettivo surrogato penalizzato dalla divergenza di Kullback–Leibler:

\( \pi_{k+1} = \arg\max_{\pi'} \left[ \, \mathcal{L}_{\pi_k}(\pi') - C \sqrt{ \mathbb{E}_{s \sim d^{\pi_k}} \!\left[ D_{\mathrm{KL}}(\pi' \| \pi_k)[s] \right] } \, \right]. \)

Il problema in questo tipo di approccio è  che Il coefficiente teorico \( C \) risulta molto elevato quando il fattore di sconto \( \gamma \) è vicino a 1, di conseguenza, i passi di aggiornamento derivanti dall’equazione risultano eccessivamente piccoli, rallentando l’apprendimento.

Le soluzioni sono regolare dinamicamente la penalità KL, approccio che porta alla formulazione già vista del del metodo PPO (Proximal Policy Optimization), o imporre un vincolo esplicito sulla divergenza KL, introducendo una trust region come in TRPO (Trust Region Policy Optimization), per controllare direttamente l’ampiezza del passo di aggiornamento.

Entrambi gli approcci mirano a mantenere un equilibrio tra stabilità e velocità di apprendimento, evitando sia aggiornamenti troppo conservativi sia cambiamenti eccessivamente drastici della policy.

Il risultato fornisce quindi una base teorica per gli algoritmi di ottimizzazione di policy (come TRPO e PPO), garantendo un miglioramento monotono — o almeno non negativo — della funzione di performance a ogni iterazione.