I metodi Policy Gradient prescindono da un approccio basato sulla definizione della policy a partire dal'approssimazione una funzione di stato V(s) o di stato-azione Q(s,a) anche attraverso la loro parametrizzazione,  e provano a parametrizzare direttamente la policy stocastica \(\pi_\theta(s,a)=\Bbb P[a|s;\theta]\)  con l'obiettivo di trovare una policy che massimizzi la funzione di valore \(V^\pi\) , apprendendo dall'esperienza in ottica model-free.

I metodi Policy Based nella quale si apprende direttamnete una policy, si contrappongono quindi ai metodi Value Based, nella quale si apprende una funzione di Valore dalla quale si ricava una policy in modo implicito (es: \(\epsilon\)-greedy).  Vi sono poi metodi Actor-Critic a cavallo tra le due tipologie nelle quale si apprendono sia la Funzione di Valore che la Policy.

In un contesto Policy Based, come misurare la qualità di una policy? In un ambiente episodico potremmo utilizzare il valore della policy allo stato di partenza \(V(s_0,\theta)\) , approccio che può essere esteso al caso di un orizzonte infinito.

Il problema di massimizzare \(V(s_0,\theta)\) è di un problema di ottimizzazione complesso, perchè non conosciamo la funzione , la possiamo solo stimare attraverso i dati; non abbiamo quindi idea di come \(\theta\) si relaziona a V, relazione che è oggetto di apprendimento.

Nel reinforcement learning basato su policy il problema è di ottimizzazione, ovvero trovare i parametri \(\theta\) che massimizzano \(V(s_0,\theta)\).

Si possono usare metodi di ottimizzazione senza gradiente, ma spesso l’uso del gradiente consente maggiore efficienza. Tra i principali approcci troviamo: discesa del gradiente, gradiente coniugato e metodi quasi-Newton.

Quando il gradiente è difficile o costoso da stimare, si possono usare metodi di ottimizzazione senza gradiente, tra cui: hill climbing, simplex/Nelder–Mead, algoritmi genetici, Cross-Entropy Method (CEM) e Covariance Matrix Adaptation (CMA).

L’attenzione è rivolta in particolare alla discesa del gradiente, che può essere estesa in varie forme, e ai metodi che sfruttano la struttura sequenziale del problema.

Nel reinforcement learning basato su policy il problema si formula quindi come un’ottimizzazione: occorre trovare i parametri della policy \(\theta\) che massimizzano il valore atteso a partire dallo stato iniziale, \(V(s_0,\theta)\).

Si definisce \(V^{\pi^\theta} = V(s_0,\theta)\) per rendere esplicita la dipendenza del valore dai parametri della policy. Si assume un contesto di MDP episodici.

Gli algoritmi di policy gradient cercano un massimo locale di \(V(s_0,\theta)\) risalendo il gradiente della policy rispetto ai parametri \(\theta\):

\(\Delta \theta = \alpha \nabla_\theta V(s_0,\theta)\)  ,  con il policy gradient  \( \nabla_\theta V(s_0,\theta) = \begin{pmatrix} \frac{\partial V(s_0,\theta)}{\partial \theta_1} \\ \vdots \\ \frac{\partial V(s_0,\theta)}{\partial \theta_n} \end{pmatrix} \)  e \(\alpha\) il parametro di passo (step-size).

I metodi di policy gradient presentano alcuni vantaggi: migliori proprietà di convergenza, efficacia in spazi d’azione ad alta dimensionalità o continui e la capacità di apprendere policy stocastiche.

Tra gli svantaggi vi è la tendenza a convergere a un ottimo locale piuttosto che globale, e la valutazione della policy che risulta spesso inefficiente e caratterizzata da alta varianza.

Policy differenziabile

Calcoliamo il policy gradient analiticamente, assumendo che \(\pi_\theta\) sia differenziabile quando non nulla, che possiamo calcolare il gradiente \(\nabla_\theta \pi_\theta(s,a)\) analiticamente.

In questa categoria rientrano molte classi di policy differenziabili p(a|s), quali softmax, la Gaussiana, e le reti neurali.

Assumendo quindi che la policy \(\pi_\theta\) sia differenziabile quando non è nulla e che sia noto il gradiente \(\nabla_\theta \pi_\theta(s,a)\), il valore della policy è definito come \(V(s_0,\theta) = \mathbb{E}_{\pi_\theta}\left[\sum_{t=0}^T R(s_t,a_t);\, \pi_\theta, s_0\right]\), dove l’aspettativa è calcolata sugli stati e le azioni visitati da \(\pi_\theta\).

Questa definizione può essere espressa in modi equivalenti:

• \(V(s_0,\theta) = \sum_a \pi_\theta(a|s_0)\, Q(s_0,a,\theta)\)
• \(V(s_0,\theta) = \sum_\tau P(\tau;\theta)\,R(\tau)\), dove \(\tau = (s_0,a_0,\ldots,s_T,a_T,r_T)\) è una traiettoria stato-azione, \(P(\tau;\theta)\) indica la probabilità della traiettoria sotto la policy \(\pi_\theta\) a partire da \(s_0\), e \(R(\tau) = \sum_{t=0}^T R(s_t,a_t)\) è la somma delle ricompense per la traiettoria \(\tau\).

Adottando questa formulazione l'obiettivo è quello di trovare i parameteri della policy \(\theta \) che soddisfano  \(\displaystyle \arg \max_\theta V(\theta) = \arg \max_\theta \sum_\tau P(\tau;\theta)\,R(\tau)\)

Calcolando il gradiente di \(V(\theta)\) rispetto ai parametri \(\theta\) abbiamo:

\[ \nabla_\theta V(\theta) = \nabla_\theta \sum_\tau P(\tau;\theta) R(\tau) = \sum_\tau \nabla_\theta P(\tau;\theta) R(\tau). \]

\[ \nabla_\theta V(\theta) = \sum_\tau P(\tau;\theta) R(\tau) \frac{\nabla_\theta P(\tau;\theta)}{P(\tau;\theta)}. \]      Il rapporto \(\frac{\nabla_\theta P(\tau;\theta)}{P(\tau;\theta)}\) è noto come likelihood ratio,

\[ \nabla_\theta V(\theta) = \sum_\tau P(\tau;\theta) R(\tau)\,\nabla_\theta \log P(\tau;\theta). \]

Per approssimare il gradiente della funzione valore \(V(\theta)\), si utilizza una stima empirica basata su \(m\) traiettorie campionate dalla politica \(\pi_\theta\). In questo modo:

\[ \nabla_\theta V(\theta) \approx \hat{g} = \frac{1}{m} \sum_{i=1}^m R(\tau^{(i)}) \, \nabla_\theta \log P(\tau^{(i)};\theta) \]

dove \(R(\tau^{(i)})\) rappresenta il ritorno della traiettoria \(\tau^{(i)}\). Questa formulazione consente di stimare il gradiente tramite campionamento Monte Carlo.

Per calcolare \(\nabla_\theta \log P(\tau^{(i)};\theta)\), possiamo scomporre la probabilità della traiettoria \(\tau^{(i)}\) nei suoi elementi costitutivi:

\( \nabla_\theta \log P(\tau^{(i)};\theta) = \nabla_\theta \log \Bigg[ \mu(s_0) \prod_{t=0}^{T-1} \pi_\theta(a_t|s_t) P(s_{t+1}|s_{0:t},a_{0:t}) \Bigg] \)

Espandendo il logaritmo:

\( = \nabla_\theta \left[ \log \mu(s_0) + \sum_{t=0}^{T-1} \log \pi_\theta(a_t|s_t) + \log P(s_{t+1}|s_{0:t},a_{0:t}) \right] \)

Poiché né la distribuzione iniziale \(\mu(s_0)\) né il modello dinamico \(P(s_{t+1}|s_{0:t},a_{0:t})\) dipendono dai parametri \(\theta\), i loro gradienti sono nulli. Rimane quindi:

\(\displaystyle \nabla_\theta \log P(\tau^{(i)};\theta) = \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \)

e quindi \(\displaystyle \nabla_\theta V(\theta) = \frac{1}{m} \sum_{i=1}^m R(\tau^{(i)}) \, \sum_{t=0}^{T-1}\nabla_\theta \log \pi_\theta(a_t^{(i)}|s_t^{(i)}) \)

Il risultato mostra che non è necessario conoscere il modello dinamico dell’ambiente: il gradiente dipende unicamente dalla politica \(\pi_\theta\).

 

Policy Softmax

Vediamo ad esempio il calcolo della score function  \(\nabla_\theta \log \pi_\theta(s,a)\) con una Softmax Policy della forma \(\displaystyle \pi_\theta (s,a)=\frac{e^{[s,a]^\top \theta}}{\sum_a e^{[s,a]^\top \theta}}\) 

\(\nabla_\theta \log \frac{e^{[s,a]^\top \theta}}{\sum_a e^{[s,a]^\top \theta}} = \nabla_\theta \left[ \log {e^{[s,a]^\top \theta}} - \log {\sum_a e^{[s,a]^\top \theta}} \right]= \\ = [s,a] - \frac{{\sum_a [s,a]e^{[s,a]^\top \theta}}}{\sum_a e^{[s,a]^\top \theta}}=[s,a]-\sum_a [s,a] \pi_\theta(s,a)=[s,a]-\Bbb E_{\pi_\theta}[s,\cdot]\)

Policy Gaussiana

Negli spazi di azione continui, una policy gaussiana rappresenta una scelta naturale. In questo caso, la media è definita come combinazione lineare delle caratteristiche dello stato: \(\mu(s) = \phi(s)^\top \theta\). La varianza \(\sigma^2\) può essere fissata oppure parametrizzata. La politica assume quindi la forma gaussiana: \(a \sim \mathcal{N}(\mu(s), \sigma^2)\)    ,  ed in forma analitica \(\displaystyle \pi_\theta(s,a)=\frac{1}{\sqrt{2\pi \sigma^2}} e^{- \frac{(a-\phi(s)^\top \theta)^2}{2 \sigma^2}}\)

La funzione punteggio (score function) associata è:

\[ \nabla_\theta \log \pi_\theta(s,a) = \frac{(a - \mu(s)) \, \phi(s)}{\sigma^2} \]

Intuizione e teorema del policy gradient 

Consideriamo la forma generica \(\hat{g}_i = f(x_i)\nabla_\theta \log p(x_i|\theta)\).   \(f(x)\) misura la ricompensa, ovvero quanto è  buona la traiettoria campione \(x\). Muoversi nella direzione di \(\hat{g}_i\) significa aumentare la probabilità logaritmica del campione in proporzione alla sua qualità.

Questo approccio rimane valido anche se \(f(x)\) è discontinua, sconosciuta, oppure se lo spazio dei campioni che contiene \(x\) è un insieme discreto.

Il policy gradient theorem generalizza l’approccio del likelihood ratio. Per qualsiasi policy differenziabile \(\pi_\theta(s,a)\) e per qualunque funzione obiettivo della policy \(J\) (che può rappresentare la ricompensa episodica \(J_1\), la ricompensa media per passo temporale \(J_{avR}\), oppure il valore medio \(\tfrac{1}{1-\gamma} J_{avV}\)), il gradiente della policy è dato da:

\[ \nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\left[\nabla_\theta \log \pi_\theta(s,a) Q^{\pi_\theta}(s,a)\right] \]

Struttura Temporale della Score function e algoritmo REINFORCE

In precedenza è stato mostrato che il gradiente del valore atteso delle ricompense totali può essere scritto come:

\( \nabla_\theta \mathbb{E}_\tau[R] = \mathbb{E}_\tau \left[ \left( \sum_{t=0}^{T-1} r_t \right) \left( \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \right) \right] \)

Che come abbiamo visto ha 

Lo stesso argomento può essere applicato per stimare il gradiente di una singola ricompensa \(r_{t'}\):

\( \nabla_\theta \mathbb{E}[r_{t'}] = \mathbb{E}\left[ r_{t'} \sum_{t=0}^{t'} \nabla_\theta \log \pi_\theta(a_t|s_t) \right] \)  , non entrando nel gradiente la score function relativa ai time step successivi.

Sommando questa formula su tutti i valori di \(t\), otteniamo:

\(\nabla_\theta \mathbb{E}[R] = \mathbb{E}\left[ \sum_{t'=0}^{T-1} r_{t'} \sum_{t=0}^{t'} \nabla_\theta \log \pi_\theta(a_t|s_t) \right] \)

e osservando quando vengono coinvolti i termini della score function otteniamo infine

\(\nabla_\theta \mathbb{E}[R] = \mathbb{E}\left[ \sum_{t=0}^{T-1}\nabla_\theta \log \pi_\theta(a_t|s_t) \sum_{t'=t}^{T-1} r_{t'} \right] \)

che evidenzia che il contributo della score function al time step t incide solo per gli step \(t'\ge t\).

Nel caso di un campionamento, ricordando che per una particolare traiettoria \(\tau^{(i)}\) il ritorno a partire da un timestep t  è  \(G_t^{(i)}=\sum_{t'=t}^{T-1}{r_{t'}^{(i)}} \) , abbiamo perciò

\(\displaystyle \nabla_\theta \mathbb{E}[R] \approx \frac{1}{m} \sum_{i=1}^m \sum_{t=0}^{T-1}\nabla_\theta \log \pi_\theta(a_t|s_t) G_t^{(i)}\)

relazione alla base dell'algoritmo REINFORCE, che  stima il gradiente utilizzando la score function e la struttura temporale delle traiettorie.
L’aggiornamento dei parametri della policy diviene \( \Delta \theta_t = \alpha \nabla_\theta \log \pi_\theta(s_t,a_t)\, G_t \), dove \( G_t \) rappresenta il ritorno a partire dal tempo \( t \).

Algoritmo REINFORCE:

• Inizializza i parametri della policy \( \theta \) in modo arbitrario.
• Per ogni episodio campionato secondo la policy corrente \( \pi_\theta \) (sequenza \( \{s_1,a_1,r_2,\ldots,s_{T-1},a_{T-1},r_T\} \)):
  • Per \( t=1,\ldots,T-1 \):
    • Calcola o aggiorna il ritorno \( G_t \) a partire dal tempo \( t \).
    • Aggiorna i parametri secondo la regola di ascesa del gradiente: \( \theta \leftarrow \theta + \alpha \,\nabla_\theta \log \pi_\theta(s_t,a_t)\, G_t \).
• Restituisci i parametri finali \( \theta \).

Baseline

Per ridurre ulteriormente la varianza della stima del gradiente, si può introdurre una baseline \( b(s) \), dipendente solo dallo stato. L’espressione generale del gradiente diventa:

\( \nabla_\theta \mathbb{E}_\tau[R] = \mathbb{E}_\tau \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t;\theta) \left( \sum_{t'=t}^{T-1} r_{t'} - b(s_t) \right) \right] \)

Per qualunque scelta della funzione di baseline \( b(s_t) \), lo stimatore del gradiente rimane non distorto (unbiased). Tuttavia, una scelta adeguata di \( b(s_t) \) può ridurre significativamente la varianza e migliorare la stabilità dell’apprendimento.

Una scelta quasi ottimale per la baseline è il valore atteso del ritorno a partire dallo stato \( s_t \):

\( b(s_t) \approx \mathbb{E}[r_t + r_{t+1} + \cdots + r_{T-1}] \)

L’interpretazione intuitiva è che l’algoritmo aumenta la probabilità logaritmica dell’azione \( a_t \) in proporzione a quanto il ritorno ottenuto da quel punto in poi (\( \sum_{t'=t}^{T-1} r_{t'} \)) sia superiore rispetto al valore atteso. In altre parole, le azioni che portano risultati migliori della media vengono rafforzate, mentre quelle peggiori vengono penalizzate.

La dimostrazione seguente mostra in modo dettagliato che l’aggiunta di una baseline \( b(s_t) \) non altera la correttezza dello stimatore del gradiente, poiché il suo contributo ha valore atteso nullo:

\( \mathbb{E}_\tau[\nabla_\theta \log \pi(a_t|s_t;\theta)\, b(s_t)] = 0 \)

I passaggi sono i seguenti:

\( \mathbb{E}_\tau[\nabla_\theta \log \pi(a_t|s_t;\theta)\, b(s_t)] = \mathbb{E}_{s_{0:t}, a_{0:(t-1)}} \left[ \mathbb{E}_{s_{t+1:T}, a_{t:T-1}} \left[ \nabla_\theta \log \pi(a_t|s_t;\theta)\, b(s_t) \right] \right] \) (scomposizione del valore atteso lungo la traiettoria)

\( = \mathbb{E}_{s_{0:t}, a_{0:(t-1)}} \left[ b(s_t) \, \mathbb{E}_{s_{t+1:T}, a_{t:T-1}} \left[ \nabla_\theta \log \pi(a_t|s_t;\theta) \right] \right] \) (estrazione del termine \( b(s_t) \) che non dipende da \( a_t \))

\( = \mathbb{E}_{s_{0:t}, a_{0:(t-1)}} \left[ b(s_t) \, \mathbb{E}_{a_t} [\nabla_\theta \log \pi(a_t|s_t;\theta)] \right] \) (si rimuovono le variabili irrilevanti rispetto a \( s_t, a_t \))

Ora utilizziamo la forma esplicita della likelihood ratio:

\( \mathbb{E}_{a_t} [\nabla_\theta \log \pi(a_t|s_t;\theta)] = \sum_a \pi_\theta(a|s_t) \, \nabla_\theta \log \pi_\theta(a|s_t) \)

Poiché \( \nabla_\theta \log \pi_\theta(a|s_t) = \frac{\nabla_\theta \pi_\theta(a|s_t)}{\pi_\theta(a|s_t)} \), si ha:

\( \sum_a \pi_\theta(a|s_t) \, \frac{\nabla_\theta \pi_\theta(a|s_t)}{\pi_\theta(a|s_t)} = \sum_a \nabla_\theta \pi_\theta(a|s_t) \)

Il gradiente della somma delle probabilità è nullo, poiché la loro somma è sempre 1:

\(\nabla_\theta \sum_a \pi_\theta(a|s_t) = \nabla_\theta [1] = 0 \)

Sostituendo nel calcolo originale otteniamo:

\( \mathbb{E}_\tau[\nabla_\theta \log \pi(a_t|s_t;\theta)\, b(s_t)] = \mathbb{E}_{s_{0:t}, a_{0:(t-1)}}[b(s_t) \cdot 0] = 0 \)

In conclusione, il termine della baseline non contribuisce al valore atteso del gradiente, ma solo alla sua varianza. Ciò garantisce che lo stimatore rimanga non distorto (unbiased), migliorando al contempo la stabilità numerica e l’efficienza della stima.

L'integrazione della baseline ci permette di giungere alla versione base degli attuali algoritmi di policy optimization nel reinforcement learning. Si tratta di un metodo iterativo che aggiorna i parametri della policy in direzione del gradiente stimato, utilizzando un insieme di traiettorie campionate e una baseline per ridurre la varianza.

Lo schema operativo dell’algoritmo può essere riassunto come segue:

• Inizializza i parametri della policy \( \theta \) e la baseline \( b \).
• Per ogni iterazione \( i = 1, 2, \ldots \):
  • Raccogli un insieme di traiettorie eseguendo la policy corrente \( \pi_\theta \).
  • Per ogni istante temporale \( t \) e per ogni traiettoria \( \tau^i \), calcola:
    • il ritorno cumulativo: \( G_t^i = \sum_{t'=t}^{T-1} r_{t'}^i \)
    • la stima dell’advantage: \( \hat{A}_t^i = G_t^i - b(s_t^i) \)
  • Adatta la baseline minimizzando l’errore quadratico medio tra i ritorni osservati e la baseline: \( \min_b \sum_i \sum_t |b(s_t^i) - G_t^i|^2 \)
  • Aggiorna la policy utilizzando una stima del gradiente medio: \( \hat{g} = \sum_t \nabla_\theta \log \pi(a_t|s_t; \theta)\, \hat{A}_t \)
  • L’aggiornamento dei parametri può essere implementato con ottimizzatori come SGD o Adam.

Questo approccio è definito “vanilla” perché applica direttamente il gradiente stimato senza correzioni o adattamenti avanzati (come nel caso di algoritmi più evoluti quali TRPO o PPO). Nonostante la sua semplicità, costituisce la base concettuale per tutte le varianti moderne di policy gradient.

Per quanto riguarda la scelta della baseline , una alternativa naturale ricordando la funzione di valore stato-azione \(Q^\pi(s,a)=\Bbb E_\pi [r_0+\gamma r_1+\gamma^2 r_2 + \cdots | s_0=s, a_0=a] \)  è proprio la funzione di valore di stato \(V^\pi(s)=\Bbb E_\pi [r_0+\gamma r_1+\gamma^2 r_2 + \cdots | s_0=s] =\Bbb E_{a\sim \pi}[Q^\pi(s,a)]\)

Alternative all'utilizzo dei ritorni Monte Carlo

Una strategia alternativa all'utilizzo di \(G^i_t \) , stima della funzione di valore a \(s_t\) da campionamento,  unbiased ma con alta varianza,  è quella di utilizzare il bootstrapping  e l'approssimazione di funzione, al prezzo di reintrodurre bias.

Questo presuppone un approccio attore/critico  (Actor/Critic),  dove la stima di Q è fatta da un critico e quella della policy da un attore attraverso i parametri \(\theta\) .

\( \nabla_\theta \mathbb{E}_\tau[R] \approx \mathbb{E}_\tau \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t;\theta) \left( Q(s_t,a_t;w) - b(s_t) \right) \right] \)

Nel caso in cui la baseline sia una stima di V, possiamo rappresentare il gradiente in termini della funzione di vantaggio stato-azione \(A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)\)  come \( \nabla_\theta \mathbb{E}_\tau[R] \approx \mathbb{E}_\tau \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t;\theta) \hat {A^\pi} (s_t,a_t) \right] \)

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.

Limitazioni dei metodi di Policy Gradient

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.

 

Abbiamo visto che il Q-learning converge alla funzione ottimale \(Q^*(s,a)\) quando viene utilizzata una rappresentazione tabulare.

 Nell’approssimazione di funzione, invece, il Q-learning minimizza la perdita MSE tramite discesa stocastica del gradiente, usando una stima  \(\hat{Q^\pi}(s;a;w)\approx Q^\pi\) per quanto riguarda la policy evaluation.

Ricordiamo a fronte di una funzione di costo del tipo \(J(w)=\Bbb E_\pi[(r+\gamma \max_{a'} \hat{Q}(s';a';w)-\hat{Q}(s;a;w)^2]\)   avremmo con la discesa del gradiente un aggiornamento dei pesi del modello \(\Delta w=\alpha(r+\gamma \max_{a'} \hat{Q}(s';a';w)-\hat{Q}(s;a;w))\nabla_w\hat{Q}(s;a;w)\)

Tuttavia, il Q-learning con approssimazione di funzione di valore può divergere. Si rilevano dei problemi di stabilità relativi alla compresenza  dell'approssimazione di funzione (potenziale espansione), del bootstrapping (contrazione)  e dell'off-policy learning, tali da non garantire la convergenza.

Due delle principali cause di questo problema sono: correlazioni tra i campioni e target non stazionari.

Il Deep Q-learning (DQN) affronta queste difficoltà introducendo due meccanismi fondamentali: l’experience replay, che riduce le correlazioni tra i dati campionati, e i fixed Q-targets, che stabilizzano l’apprendimento limitando la variazione dei target.

Experience replay

Per ridurre le correlazioni tra campioni (molti potenzialmente simili, tali da rompere l'ipotesi di IID) , nel Deep Q-learning viene utilizzato un dataset chiamato replay buffer \(\mathcal{D}\), che memorizza le esperienze passate sotto forma di tuple \((s, a, r, s')\), relative a tutte le tuple differenti incontrate nel passato, per rendere l'aggiornamento il più indipendente possibile.

L’experience replay si realizza ripetendo i seguenti passi:

• Campionare una tupla di esperienza \((s, a, r, s') \sim \mathcal{D}\) dal replay buffer.
• Calcolare il valore target per lo stato campionato: \(r + \gamma \max_{a'} \hat{Q}(s', a'; w)\).
• Aggiornare i pesi della rete neurale tramite discesa stocastica del gradiente  \[ \Delta w = \alpha \Big(r + \gamma \max_{a'} \hat{Q}(s', a'; w) - \hat{Q}(s, a; w)\Big) \nabla_w \hat{Q}(s, a; w) \]

Fixed Q-Targets

Il target \(r+\gamma \max_{a'} \hat{Q}(s';a';w)\)  prevede una parte dipendente a sua volta dai pesi w che vengono aggiornati in ogni iterazione del SGD; per migliorare la stabilità, è possibile far utilizzare un insieme differente di pesi \(\overline w\) rispetto a quelli aggiornati, da tenere fissi più a lungo per permettere un raggiungimento dell'obiettivo più stabile.

In questo caso il calcolo del target value prevederà:

• Campionare dal dataset  \((s,a,r,s') \sim \mathscr D\)
• Calcolare il target value \(r+\gamma \max_{a'} \hat{Q}(s';a'; \overline w)\)
• Usare SGD per aggiornare i pesi della rete \(\Delta w=\alpha(r+\gamma \max_{a'} \hat{Q}(s';a';\overline w)-\hat{Q}(s;a;w))\nabla_w\hat{Q}(s;a;w)\)

Algoritmo DQN

Vediamo un algoritmo base per implementare il DQN, tenendo conto che vi sono numerosi iperparametri e strategie che  possono essere perfezionate e specificate, quali la gestione del replay buffer, 

• Set parametri \(C\), \(\alpha\), \(D=\{\}\); inizializza \(w\), \(w^{-}=w\), \(t=0\)
• Ottieni lo stato iniziale \(s_0\)
• loop
  • Campiona l’azione \(a_t\) con politica \(\varepsilon\)-greedy rispetto a \(\hat Q(s_t,a;w)\)
  • Osserva ricompensa e prossimo stato \((r_t, s_{t+1})\)
  • Memorizza la transizione nel replay buffer \(D\): \((s_t, a_t, r_t, s_{t+1})\)
  • Estrai un minibatch casuale di tuple \((s_i, a_i, r_i, s_{i+1})\) da \(D\)
  • per ciascun indice \(i\) nel minibatch
    • se l’episodio termina allo step \(i+1\), imposta il target \(y_i = r_i\)
    • altrimenti imposta target \(y_i = r_i + \gamma \max_{a'} \hat Q(s_{i+1}, a';\, w^{-})\)
    • Esegui un passo di discesa del gradiente sulla perdita \(\big(y_i - \hat Q(s_i,a_i;\,w)\big)^2\) aggiornando \(\Delta w = \alpha \big(y_i - \hat Q(s_i,a_i;\,w)\big)\,\nabla_w \hat Q(s_i,a_i;\,w)\)
  • Aggiorna il tempo: \(t \leftarrow t+1\)
  • Se \(\mathrm{mod}(t,C)=0\) allora sincronizza la rete target: \(w^{-} \leftarrow w\)
• end loop

In sintesi rispetto al Q-Learning tabulare le Deep Q-Networks (DQN) combinano due tecniche fondamentali: l’experience replay e l’uso di target fissi. Le transizioni \((s_t, a_t, r_{t+1}, s_{t+1})\) vengono memorizzate in un buffer di replay \(\mathcal{D}\) e da questo si estrae in modo casuale un mini-batch di tuple \((s,a,r,s')\). I target di Q-learning vengono calcolati rispetto a parametri congelati \(w^-\), mentre la rete Q viene aggiornata minimizzando l’errore quadratico medio (MSE) tra le stime della rete e i target di Q-learning. L’ottimizzazione avviene attraverso lo stochastic gradient descent, migliorando la stabilità e l’efficacia dell’apprendimento.