Nel Reinforcement Learning off-policy o Batch RL, l’agente apprende una policy ottimale utilizzando un insieme di dati preesistenti, senza interagire direttamente con l’ambiente. Si parte da un dataset \( \mathcal{D} \) composto da \( n \) traiettorie \( \tau \sim \pi_b \), raccolte da una behavior policy \( \pi_b \) (ad esempio una policy umana o precedente versione dell’agente). Ogni traiettoria contiene sequenze di stati \( s_t \in \mathcal{S} \), azioni \( a_t \in \mathcal{A} \) e ricompense \( r(s_t, a_t) \).

L’obiettivo è stimare o migliorare una nuova policy \( \pi_t(s_t) \to a_t \) a partire da questi dati, valutando controfattualmente cosa accadrebbe se l’agente agisse in modo diverso. Tuttavia, non è possibile semplicemente applicare il Q-learning tradizionale, poiché, pur essendo un algoritmo off-policy, soffre del cosiddetto “deadly triad” — una combinazione pericolosa di tre fattori:

• Bootstrapping: l’aggiornamento del valore dipende da stime precedenti, amplificando eventuali errori.
• Funzione di approssimazione: l’uso di modelli non lineari (es. reti neurali) introduce instabilità.
• Off-policy learning: l’algoritmo apprende da dati generati da una policy diversa, creando divergenze.

Questa interazione può causare instabilità numeriche e fallimenti nella convergenza. Per questo motivo, le tecniche di Batch RL e Counterfactual RL sviluppano varianti più stabili di apprendimento off-policy, capaci di sfruttare dati raccolti in precedenza senza introdurre bias o divergenze.

Offline policy learning and optimization

 

Nel contesto del Batch Policy Evaluation, l’obiettivo è stimare le prestazioni di una specifica policy decisionale \( \pi \) utilizzando un dataset preesistente di esperienze raccolte da una behavior policy \( \pi_b \). Questo processo è fondamentale nel Reinforcement Learning off-policy, dove non è possibile (o desiderabile) generare nuove interazioni con l’ambiente.

Model based approach

Data una policy \( \pi: s \to a \) e un insieme di traiettorie \( \mathcal{D} = \{\tau_i\}_{i=1}^n \) campionate da \( \pi_b \), si stima il valore atteso di \( \pi \) integrando la funzione di valore stimata \( \hat{V}^\pi(s, \mathcal{D}) \) sugli stati iniziali \( S_0 \):

\( \int_{s \in S_0} \hat{V}^\pi(s, \mathcal{D}) \, ds \)

In questo modo si ottiene una stima del rendimento della policy \( \pi \) senza eseguirla direttamente nell’ambiente, basandosi solo sui dati storici raccolti. Tale approccio è cruciale per valutare politiche candidate in modo sicuro e controllato, specialmente in domini dove la sperimentazione diretta è costosa o rischiosa (come medicina o robotica).

Nel Batch Reinforcement Learning, è possibile stimare le prestazioni di una policy anche senza accedere direttamente all’ambiente, ricostruendo dai dati sia il modello di dynamics che quello di reward. A partire dal dataset di esperienze \( \mathcal{D} \), si apprende una stima del modello di transizione \( \hat{p}(s'|s, a) \) e della funzione di ricompensa \( \hat{r}(s, a) \).

Queste due componenti permettono di derivare una policy stimata \( \hat{\pi}^* \) e di calcolare il valore associato:

\( V^\pi \approx (I - \gamma \hat{P}^\pi)^{-1} \hat{R}^\pi \)

dove \( \hat{P}^\pi(s'|s) = p(s'|s, \pi(s)) \) rappresenta le dinamiche indotte dalla policy, e \( \gamma \) è il fattore di sconto. In alternativa, si può utilizzare il modello appreso per addestrare una nuova policy mediante algoritmi come DQN o altri metodi di RL.

Il valore stimato \( \hat{V}^{\pi^*} \) consente quindi di valutare la policy sulla base del dataset \( \mathcal{D} \), senza ulteriori interazioni con l’ambiente, sfruttando appieno l’informazione implicita nei dati raccolti da una behavior policy precedente.

In pratica si incontra un limite cruciale dell'approccio model-based di dynamics e reward appresi dai dati: anche se un modello risulta accurato nel rappresentare le esperienze passate, potrebbe non generalizzare bene alle situazioni future. Questo fenomeno è noto come bias da errata specificazione del modello (model misspecification). Risultati mostrano che migliorare l’adattamento del modello ai dati osservati non implica necessariamente migliori politiche per scenari futuri. Al contrario, può introdurre distorsioni sistematiche se il modello sottostante è mal specificato.

In sintesi, nella costruzione di modelli per il Reinforcement Learning off-policy o batch, è essenziale bilanciare l’accuratezza rispetto ai dati storici con la capacità di generalizzare a contesti nuovi, evitando che la policy appresa resti vincolata alle limitazioni del modello stesso.

Nel contesto della valutazione off-policy, i modelli utilizzati per stimare le prestazioni di una policy alternativa possono fornire risultati migliori se vengono addestrati con una funzione di perdita diversa da quella usata per la semplice massimizzazione della verosimiglianza. In sintesi, per ottenere una buona valutazione off-policy con un approccio model-based, non basta addestrare modelli accurati sui dati, ma può essere necessario progettare la loss function in funzione del tipo di stima desiderata.

In sintesi, nella costruzione di modelli per il Reinforcement Learning off-policy o batch, è essenziale bilanciare l’accuratezza rispetto ai dati storici con la capacità di generalizzare a contesti nuovi, evitando che la policy appresa resti vincolata alle limitazioni del modello stesso.

Model free methods

L’approccio Model-Free all’apprendimento off-line si basa sulla stima diretta della funzione di valore o della funzione \( Q \), senza la necessità di apprendere un modello esplicito delle dinamiche dell’ambiente. In questo contesto, un metodo molto utilizzato è la Fitted Q Evaluation (FQE), proposta da Ernst et al. (2005).

Si parte da un dataset di esperienze \( \mathcal{D} = \{(s_i, a_i, r_i, s_{i+1})\}_i \), generato da una behavior policy \( \pi_b \). L’obiettivo è stimare la funzione di valore d’azione della policy da valutare \( Q^\pi_\theta(s, a) \).

Per ogni transizione, viene costruito un target supervisionato:

\( \tilde{Q}^\pi(s_i, a_i) = r_i + \gamma V^\pi_\theta(s_{i+1}) \)

Il modello viene quindi aggiornato minimizzando l’errore quadratico medio tra il valore stimato e il target:

\( \arg\min_\theta \sum_i \left(Q^\pi_\theta(s_i, a_i) - \tilde{Q}^\pi(s_i, a_i)\right)^2 \)

Iterando questo processo, si ottiene una stima stabile della funzione \( Q^\pi \) che approssima il valore d’azione per la policy in esame, sfruttando solo i dati già raccolti (off-line). Tra le varianti correlate figurano anche i metodi LSTD (Least Squares Temporal Difference) e le tecniche di regressione iterativa applicate alle funzioni di valore.

In sintesi, l’approccio model-free consente di valutare e migliorare le policy direttamente dai dati, evitando gli errori di modellazione tipici dei metodi model-based, ma richiede una buona copertura dello spazio di stati e azioni nel dataset per garantire stime affidabili.

L’algoritmo di Fitted Q Evaluation (FQE) consente di stimare la funzione di valore d’azione di una policy \( \pi \) utilizzando un dataset statico di transizioni, senza interagire con l’ambiente. È un metodo chiave nell’apprendimento off-line model-free.

Input:

• \( \mathcal{D} = \{(x_i, a_i, x'_i, c_i)\}_{i=1}^n \sim \pi_D \): dataset di transizioni;
• \( \pi \): policy da valutare;
• \( \mathcal{F} \): classe di funzioni (ad esempio una rete neurale profonda).

Algoritmo:

• 1. Inizializza \( Q_0 \in \mathcal{F} \) casualmente.
• 2. Per \( k = 1, 2, \ldots, K \):
  • 3. Calcola il target: \( y_i = c_i + \gamma Q_{k-1}(x'_i, \pi(x'_i)) \quad \forall i \)
  • 4. Costruisci il set di addestramento: \( \tilde{\mathcal{D}}_k = \{(x_i, a_i, y_i)\}_{i=1}^n \)
  • 5. Risolvi un problema di apprendimento supervisionato:
    • \( Q_k = \arg\min_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^n (f(x_i, a_i) - y_i)^2 \)
• 6. Fine ciclo.

Output:

\( \hat{Q}^\pi(x) = Q_K(x, \pi(x)) \quad \forall x \)

In pratica, FQE addestra iterativamente una funzione \( Q \) fino alla convergenza, stimando il valore della policy target sui dati raccolti da un’altra policy (behavior policy).

Se si utilizza una DNN come classe di funzioni \( \mathcal{F} \), l’algoritmo diventa analogo al DQN, ma con una differenza cruciale: FQE non interagisce con l’ambiente e aggiorna solo in base ai dati esistenti, mentre DQN genera nuovi campioni online durante l’apprendimento.

La teoria di generalizzazione della Fitted Q Evaluation (FQE) fornisce una stima della quantità di dati necessaria per garantire che la valutazione della policy sia accurata con alta probabilità. In particolare si stabilisce che, dopo \( K \) iterazioni di FQE, la precisione dell’approssimazione dipende dalla numerosità del dataset \( n \).

La condizione sulla dimensione campionaria è:

\( n = O\!\left(\frac{\bar{C}^4}{\varepsilon^2}\!\left(\log\frac{K}{\delta} + \dim\mathcal{F}\log\frac{\bar{C}^2}{\varepsilon^2} + \log\dim\mathcal{F}\right)\right) \)

Il termine \( n \) rappresenta quindi il numero minimo di transizioni necessarie per assicurare, con probabilità almeno \( 1 - \delta \), che la differenza tra il valore stimato \( \hat{V}^\pi(s_0) \) e quello reale \( V^\pi(s_0) \) rimanga entro un margine controllato da \( \varepsilon \).

In termini pratici:

• \( \varepsilon \) indica il livello di accuratezza desiderato — minore è \( \varepsilon \), maggiore deve essere \( n \);
• \( \delta \) controlla la probabilità di errore nella stima (livello di confidenza);
• \( \dim\mathcal{F} \) rappresenta la complessità del modello di apprendimento (ad esempio, la dimensione della rete neurale);
• \( \bar{C} \) e \( d_{\mathcal{F}}^{\pi} \) misurano rispettivamente la stabilità e la capacità di concentrazione della funzione \( Q \) nel dominio della policy target.

In sintesi, il teorema fornisce una garanzia formale sulla generalizzazione della stima ottenuta da FQE: per raggiungere una data precisione \( \varepsilon \) nella valutazione di \( V^\pi \), è necessario un dataset di dimensione \( n \) proporzionale a \( 1 / \varepsilon^2 \) e alla complessità della funzione stimata.

Importance sampling

L’Off-Policy Evaluation (OPE) mira a stimare il valore di una policy target utilizzando dati raccolti da un’altra policy, detta behavior policy, riducendo al minimo le assunzioni sul modello dell’ambiente. L’obiettivo è ottenere una stima affidabile senza dipendere dalla correttezza del modello dinamico né dall’ipotesi di Markov.

In questo contesto, i metodi Monte Carlo rappresentano un punto di partenza utile: essi consentono di stimare aspettative basandosi su campioni empirici, come già avviene per la valutazione online delle policy. Tuttavia, la sfida principale nel caso off-policy è il mismatch di distribuzione dei dati: i dati raccolti dalla policy comportamentale non riflettono necessariamente la distribuzione indotta dalla policy target.

Per affrontare questo problema si utilizza la Importance Sampling (IS), una tecnica statistica che permette di correggere la differenza tra le due distribuzioni tramite un fattore di ponderazione.

L’idea è stimare l’aspettativa di una quantità \( r(x) \) sotto la distribuzione desiderata \( p(x) \) utilizzando campioni estratti da una distribuzione diversa \( q(x) \):

\( \mathbb{E}_p[r] = \sum_x p(x) r(x) = \sum_x q(x) \frac{p(x)}{q(x)} r(x) \approx \frac{1}{N} \sum_{i=1}^N \frac{p(x_i)}{q(x_i)} r(x_i) \)

In questo modo, ogni campione \( x_i \) è pesato in base al rapporto tra la probabilità di osservazione sotto la distribuzione target e quella sotto la distribuzione di comportamento. Questo consente di ottenere una stima non distorta dell’aspettativa reale, a condizione che:

• la distribuzione di campionamento \( q(x) \) copra tutte le regioni dove \( p(x) > 0 \) (proprietà di coverage/overlap);
• non vi siano variabili confondenti nascoste che alterano la relazione tra \( x \), le azioni \( a \) e le ricompense \( r \).

L’Importance Sampling per la valutazione di policy in Reinforcement Learning permette di stimare il valore atteso di una policy target \( \pi \) senza dover conoscere il modello dinamico dell’ambiente. L’idea centrale è riutilizzare traiettorie raccolte da una behavior policy \( \pi_b \), correggendo la differenza di distribuzione tramite pesi di probabilità.

Il valore della policy target è definito come:

\( V^{\pi}(s) = \sum_{\tau} p(\tau \mid \pi, s) R(\tau) \)

Poiché le traiettorie disponibili provengono da \( \pi_b \), possiamo riscrivere:

\( V^{\pi}(s) = \sum_{\tau} p(\tau \mid \pi_b, s) \frac{p(\tau \mid \pi, s)}{p(\tau \mid \pi_b, s)} R_\tau \)

e stimarlo empiricamente con:

\( V^{\pi}(s) \approx \frac{1}{N} \sum_{i=1}^{N} \frac{p(\tau_i \mid \pi, s)}{p(\tau_i \mid \pi_b, s)} R_{\tau_i} \)

Poiché le dinamiche dell’ambiente si annullano nel rapporto, i pesi si riducono ai soli rapporti tra probabilità di azioni sotto le due policy:

\( \frac{p(\tau_i \mid \pi, s)}{p(\tau_i \mid \pi_b, s)} = \prod_{t=1}^{H_i} \frac{p(a_{it} \mid s_{it}, \pi)}{p(a_{it} \mid s_{it}, \pi_b)} \)

Quindi, la stima finale del valore atteso della policy target diventa:

\( V^{\pi}(s) \approx \sum_{i=1}^{N} R_{\tau_i} \prod_{t=1}^{H_i} \frac{p(a_{it} \mid s_{it}, \pi)}{p(a_{it} \mid s_{it}, \pi_b)} \)

In sintesi, l’importance sampling in RL consente di valutare una policy senza conoscere le transizioni \( p(s' \mid s, a) \), basandosi solo sui rapporti di probabilità delle azioni tra policy target e behavior policy. Questo approccio è quindi model-free e particolarmente utile in contesti off-policy, dove l’interazione diretta con l’ambiente non è possibile. Questo approccio pertanto non richiede l'assunzione di Markov, è unbiased, simile all'approccio Monte Carlo ma con la correzione del mismatch tra le distribuzioni.

Il Per-Decision Importance Sampling (PDIS) è una variante dell’importance sampling progettata per la valutazione di policy in Reinforcement Learning, che sfrutta la struttura temporale delle traiettorie per ridurre la varianza della stima. L’idea di base è simile a quella dei policy gradient methods: invece di pesare un’intera traiettoria con un unico fattore di probabilità cumulativo, PDIS applica una correzione passo per passo.

La stima classica dell’importance sampling sull’intero dataset \( D \) è data da:

\( IS(D) = \frac{1}{n} \sum_{i=1}^{n} \left( \prod_{t=1}^{L} \frac{\pi_e(a_t \mid s_t)}{\pi_b(a_t \mid s_t)} \right) \left( \sum_{t=1}^{L} \gamma^t R_t^i \right) \)

dove ogni traiettoria è ponderata in base al prodotto dei rapporti di probabilità tra la policy target \( \pi_e \) (evaluation policy) e la policy comportamentale \( \pi_b \) lungo tutti i passi temporali \( t \).

Il Per-State Importance Sampling (PSIS o PDIS) migliora questa formulazione pesando le ricompense parziali passo per passo:

\( PSID(D) = \sum_{t=1}^{L} \gamma^t \frac{1}{n} \sum_{i=1}^{n} \left( \prod_{\tau=1}^{t} \frac{\pi_e(a_\tau \mid s_\tau)}{\pi_b(a_\tau \mid s_\tau)} \right) R_t^i \)

In questo modo, la correzione di importanza viene applicata fino al tempo \( t \) invece che su tutta la traiettoria, permettendo di:

• sfruttare la struttura temporale del dominio (le ricompense dipendono dal tempo);
• ridurre la varianza della stima, particolarmente elevata nel caso standard di IS cumulativo;
• ottenere stime più stabili e più simili a quelle basate su metodi Monte Carlo passo per passo.

Il PDIS rappresenta quindi un compromesso efficace tra accuratezza e stabilità statistica, mantenendo la proprietà di non distorsione dell’IS, ma migliorando la sua efficienza pratica nel contesto di policy evaluation off-policy.

In generale IS e PSID soffrono di alta varianza, specie con orizzonti lunghi, per cui possono essere adottate misure per contrastare il fenomeno, esplicitando l'assunzione di Markov od utilizzando correttivi.

Off-Policy Optimization

Fino al 2020, la Offline Policy Optimization (OPO) — ovvero l’ottimizzazione di policy in ambienti offline — si è basata su un presupposto cruciale: la presenza di overlap tra le distribuzioni delle policy. Questo significa che, nei dataset di esperienza utilizzati per l’addestramento, ogni azione considerata dalla policy target deve essere stata osservata almeno in alcune circostanze dalla policy comportamentale.

In particolare:

• Off-policy estimation: richiede overlap per la sola policy di interesse, al fine di stimarne correttamente il valore atteso.
• Off-policy optimization: richiede overlap per tutte le policy potenzialmente ottimali, ipotesi nota come concentrability assumption nel contesto del batch reinforcement learning.

Tuttavia, questo presupposto è poco realistico in molti scenari pratici. Gran parte dei dataset reali non deriva da esplorazioni casuali o complete dello spazio di stati e azioni: spesso i dati riflettono soltanto le decisioni prese da un singolo sistema o esperto.

Quando si assume overlap dove in realtà non esiste, si rischia di:

• stimare in modo eccessivamente ottimistico le prestazioni di una policy;
• ottenere un comportamento che appare performante in fase di addestramento, ma che fallisce una volta implementato nel mondo reale.

In sintesi, la ricerca successiva ha riconosciuto che la mancanza di overlap rappresenta uno dei principali ostacoli alla robustezza e generalizzazione delle policy apprese in contesti di offline reinforcement learning.

La Off-Policy Optimization senza piena copertura dei dati rappresenta un’evoluzione del Reinforcement Learning offline, nata per affrontare la mancanza di overlap tra le distribuzioni di comportamento e quelle target. Quando il dataset non copre l’intero spazio di stati e azioni, le stime di valore possono diventare instabili o fuorvianti. L’obiettivo è quindi “fare il meglio possibile con i dati disponibili”.

Le strategie principali adottate sono:

• Limitare l’ottimizzazione off-policy solo alle regioni dello spazio \( (s, a) \) dove esiste effettivo overlap nei dati. Questa idea richiama tecniche già note come i vincoli KL e il PPO clipping, che impediscono deviazioni eccessive dalla policy di riferimento.
• Adottare algoritmi computazionalmente trattabili, che possano stimare e penalizzare le regioni scarsamente supportate senza introdurre complessità eccessiva.
• Applicare un approccio pessimistico nelle aree con scarso supporto: in assenza di dati sufficienti, si assume che gli esiti possano essere sfavorevoli, riducendo così il rischio di sovrastimare il valore atteso di certe azioni.

Questa linea di ricerca mira a fornire una risposta al problema del data coverage limitato nell’apprendimento da dati offline.

Il metodo Marginalized Behavior Supported (MBI) Policy Optimization introduce una strategia per gestire l’ottimizzazione di policy in contesti offline dove il supporto dei dati è limitato. L’idea chiave è quella di considerare solo le azioni che hanno una sufficiente probabilità di essere state osservate nella policy comportamentale, evitando di stimare valori in regioni dello spazio \( (s, a) \) scarsamente rappresentate.

Il meccanismo si basa su una filtrazione comportamentale espressa tramite una funzione indicatrice:

\( \zeta(s, a; \hat{\mu}, b) = 1(\hat{\mu}(s, a) > b) \)

dove:

• \( \hat{\mu}(s, a) \) rappresenta la probabilità stimata che l’azione \( a \) sia stata scelta nello stato \( s \) secondo la policy comportamentale;
• \( b \) è una soglia di confidenza che determina il livello minimo di supporto richiesto per considerare l’azione affidabile.

Questa funzione filtra le azioni poco rappresentate, garantendo che le valutazioni si basino solo su esperienze realmente supportate dai dati.

Sulla base di questo filtro, vengono definite due versioni modificate dell’operatore di Bellman:

• Bellman operator:

\( \mathcal{T}f(s,a) = r(s,a) + \gamma \, \mathbb{E}_{s'}\left[\max_{a'} \zeta(s', a') f(s', a')\right] \)

• Bellman evaluation operator:

\( \mathcal{T}^{\pi}f(s,a) = r(s,a) + \gamma \, \mathbb{E}_{s',a' \sim P,\pi}\left[\zeta(s', a') f(s', a')\right] \)

In queste formulazioni, l’operatore \( \zeta(s', a') \) agisce come un filtro che riduce o annulla il contributo delle coppie stato–azione non sufficientemente supportate. Questo approccio permette di mantenere stabilità e coerenza nelle stime del valore, migliorando la robustezza delle policy apprese in scenari con dati parziali o distribuzioni comportamentali sbilanciate.

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.