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:
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.
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:
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).
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:
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.
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.
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.
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:
È 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 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:
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.
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.