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.