Dopo aver introdotto il formalismo dei Markov Decision Process e le tecniche di ottimizzazione nel caso di modello dell'ambiente noto, l’attenzione si sposta su un problema cruciale: valutare e ottimizzare una policy quando il modello dell’ambiente non è noto. In molti contesti reali, infatti, l’agente non ha accesso esplicito alle dinamiche di transizione \(P(s' \mid s,a)\) né alla funzione di ricompensa R attesa, ma può solo osservare sequenze di stati, azioni e ricompense generate dall’interazione diretta con l'ambiente.

Il primo obiettivo diventa quindi stimare il ritorno atteso di una policy fissata, senza conoscere il MDP sottostante. Questo problema è noto come valutazione della policy in regime model-free. In altre parole, si vuole stimare quanto “vale” una policy basandosi esclusivamente su traiettorie campionate, tipicamente ottenute seguendo la policy stessa (on-policy samples).

Un approccio diretto a questo problema è la valutazione Monte Carlo. In questo caso, la valutazione della policy avviene senza alcun modello del funzionamento del mondo: l’agente osserva episodi completi, calcola i ritorni empirici e utilizza tali campioni per stimare le aspettative. Questo metodo è concettualmente semplice, ma richiede episodi completi e può esibire una elevata varianza.

Un’alternativa più articolata è rappresentata dai metodi di Temporal Difference (TD), che combinano idee di Monte Carlo e di programmazione dinamica. I metodi TD aggiornano le stime dei valori in modo incrementale, utilizzando differenze temporali tra stime successive, senza attendere la fine di un episodio e senza richiedere un modello dell’ambiente.

Un risultato importante è la certezza di equivalenza con la programmazione dinamica: sotto opportune condizioni, le stime ottenute con metodi model-free convergono agli stessi valori che si otterrebbero conoscendo il modello esatto. Ciò fornisce una base solida per comprendere perché tali algoritmi funzionano anche in assenza di informazioni complete sul mondo.

Infine, in molti scenari pratici, evidenziamo che i dati non arrivano in modo incrementale ma sono disponibili in forma di batch, come grandi collezioni di transizioni registrate. Questo introduce il tema della batch policy evaluation, che richiede tecniche specifiche per sfruttare dataset fissi senza ulteriori interazioni con l’ambiente.

Per inquadrare correttamente questi metodi, è utile richiamare alcune definizioni fondamentali.

Il ritorno \(G_t\) è la somma scontata delle ricompense future a partire dal tempo \(t\):

\( G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \gamma^3 r_{t+3} + \cdots \)

La funzione di valore di stato associata a una policy \(\pi\) è definita come il ritorno atteso partendo dallo stato \(s\) e seguendo la policy:

\( V^\pi(s) = \mathbb{E}_\pi[ G_t \mid s_t = s ] \)

In modo analogo, la funzione di valore stato–azione misura il ritorno atteso partendo dallo stato \(s\), eseguendo un’azione \(a\) e seguendo poi la policy \(\pi\):

\( Q^\pi(s,a) = \mathbb{E}_\pi[ G_t \mid s_t = s, a_t = a ] \)

Queste quantità costituiscono il cuore della policy evaluation. Nel seguito, verranno sviluppati algoritmi che permettono di stimarle in modo efficiente senza conoscere il modello dell’ambiente, aprendo la strada al model-free policy evaluation and control, ossia all’apprendimento di politiche efficaci basandosi unicamente sull’esperienza.

Valutazione Monte Carlo

La Monte Carlo policy evaluation rappresenta uno dei primi e più intuitivi approcci alla valutazione di una policy in assenza di modello. L’idea di base è stimare il valore atteso di una policy osservando direttamente le traiettorie generate dall’interazione con l’ambiente e calcolando la media dei ritorni empirici. Questo approccio è applicabile quando tutte le traiettorie sono finite, ossia quando il problema è episodico e ogni episodio termina in un tempo finito.

L'aspetto fondamentale dei metodi Monte Carlo è che non richiedono alcuna conoscenza delle dinamiche dell’MDP: né il modello di transizione \(P(s' \mid s,a)\) né la funzione di ricompensa attesa devono essere noti. Inoltre, a differenza della programmazione dinamica, i metodi Monte Carlo non assumono che lo stato sia Markoviano. È sufficiente che i ritorni siano ben definiti e che gli episodi terminino, perché l’aspettativa possa essere stimata per media empirica.

Nel caso più semplice, la valutazione Monte Carlo di una policy consiste nel:

• campionare un insieme di episodi seguendo la policy \(\pi\);
• calcolare il ritorno \(G_t\) per gli stati visitati;
• stimare il valore come media dei ritorni osservati.

Una prima variante è la First-visit Monte Carlo policy evaluation. In questo caso, per ciascun episodio si considera solo la prima volta in cui uno stato \(s\) viene visitato. L’algoritmo procede inizializzando un contatore \(N(s)=0\) e una somma cumulativa \(G(s)=0\) per ogni stato. Per ogni episodio campionato, si calcola il ritorno \(G_{i,t}\) a partire dal primo istante \(t\) in cui lo stato appare e quindi si aggiorna:

• \(N(s) \leftarrow N(s) + 1\)
• \(G(s) \leftarrow G(s) + G_{i,t}\)
• \(V^\pi(s) = G(s)/N(s)\)

Questo stimatore è non distorto (unbiased) , ovvero \(\Bbb E[{\hat V}^\pi(s)]=V^\pi(s)\)  e consistente,  \(\displaystyle \forall \epsilon>0 \ \ ,\ \lim_{n \to \infty} Pr(|\hat V^\pi_n(s)-V^\pi (s)|>\epsilon )=0\)  ovvero al crescere del numero di episodi, la stima converge al vero valore \(V^\pi(s)\).

Una seconda variante è la Every-visit Monte Carlo policy evaluation. Qui si tiene conto di ogni visita allo stato \(s\) all’interno di un episodio, non solo della prima. L’aggiornamento di \(V^\pi(s)\) avviene quindi per tutti i time-step \(t\) in cui lo stato \(s\) è osservato. Questo stimatore resta consistente, ma in generale è distorto (biased); tuttavia, spesso presenta un errore quadratico medio (MSE) \(\Bbb E[(\hat V^\pi-V^\pi)^2]\) inferiore rispetto alla versione first-visit, risultando più efficace nel caso pratico.

Per rendere l’algoritmo più efficiente dal punto di vista computazionale e della memoria, si utilizza frequentemente una versione incrementale della Monte Carlo policy evaluation. In questo caso, il valore stimato viene aggiornato tramite una media incrementale:

\(\displaystyle V^\pi(s)=V^\pi(s) \frac{N(s)-1}{N(s)}+\frac{G_{i,t}}{N(s)}= \\\displaystyle =V^\pi(s)+\frac{1}{N(s)}(G_{i,t}-V^\pi(s))=\\\displaystyle=V^\pi(s)+\alpha(G_{i,t}-V^\pi(s))\)

dove \(\alpha\) è il learning rate. Le proprietà di convergenza dipendono dalla scelta di \(\alpha\): se soddisfa condizioni standard del tipo \(\sum_t \alpha_t = \infty\) e \(\sum_t \alpha_t^2 < \infty\), la stima converge al valore reale della policy.

In sintesi, la Monte Carlo policy evaluation presenta alcune caratteristiche chiave:

• Stima per media empirica: il valore di uno stato è la media dei ritorni osservati.
• Semplicità: non richiede modelli né equazioni di Bellman.
• Flessibilità: non impone l’assunzione di Markov sullo stato.
• Convergenza: sotto ipotesi deboli, le stime convergono al valore reale.

D’altra parte, i metodi Monte Carlo soffrono in generale di alta varianza, richiedono un grande numero di episodi per ottenere stime accurate e necessitano che ogni episodio termini prima di poter aggiornare i valori. Questi limiti motivano l’introduzione dei metodi di Temporal Difference, che riducono la varianza aggiornando le stime in modo incrementale e online, senza attendere la fine dell’episodio.

 

TD(0) Learning Evaluation

Questo metodo di valutazione combina le idee dei metodi Monte Carlo e del bootstrapping permettendo l'immediato aggiornamento della stima di V dopo ogni campione, senza attendere la fine dell'episodio.

L'idea, rispetto al MC incrementale, è di utilizzare il bootstrapping per stimare \(G_{i,t}\approx r_t + \gamma V^\pi(s_{t+1})\) , senza necessità di calcolare esplicitamente la somma scontata dei ritorni effettivi da t fino al termine dell'episodio.
L'algoritmo prevede di inizializzare \(V^\pi=0\) e per ogni step di ogni episodio procedere con l'assegnamento:

\(V^\pi(s)=V^\pi(s)+\alpha([r_t+\gamma V^\pi(s_{t+1})]-V^\pi(s))\)

che permette di aggiornare ad ogni step la stima di \(V^\pi(s)\) con la sola conoscenza della tupla (s,a,r,s'), senza necessità di attendere il completamento dell'episodio.

Tra le proprietà principali:

• può essere applicato sia in scenari episodici sia in contesti a orizzonte infinito non episodici;

• lo stimatore è in genere biased nelle fasi iniziali, a causa dell’influenza dell’inizializzazione, ma tende alla consistenza se \(\alpha\) soddisfa le stesse condizioni richieste dal metodo di Monte Carlo incrementale.

• presenta una varianza inferiore rispetto alla policy evaluation Monte Carlo

CERTAINITY

Un’alternativa ai metodi puramente model-free per la policy evaluation è rappresentata dall’approccio basato su stima del modello per massima verosimiglianza (Maximum Likelihood Estimation, MLE). L’idea è costruire un modello esplicito dell’MDP a partire dai dati osservati e, successivamente, utilizzare tecniche di pianificazione per calcolare \(V^\pi\). Questo approccio è noto come certainty equivalence: si sostituisce il vero modello ignoto con la sua stima e si procede come se tale stima fosse esatta.

Dopo aver osservato una sequenza di transizioni \((s,a,r,s')\), si aggiornano le stime empiriche del modello di transizione e della funzione di ricompensa. In particolare, per ogni coppia \((s,a)\), si calcola:

\[ \hat{P}(s' \mid s,a) = \frac{1}{N(s,a)} \sum_{k=1}^{K} \sum_{t=1}^{T_k-1} \mathbf{1}(s_{k,t}=s,\; a_{k,t}=a,\; s_{k,t+1}=s') \]

e analogamente la stima della ricompensa attesa:

\[ \hat{r}(s,a) = \frac{1}{N(s,a)} \sum_{k=1}^{K} \sum_{t=1}^{T_k-1} \mathbf{1}(s_{k,t}=s,\; a_{k,t}=a)\, r_{t,k}. \]

Qui \(N(s,a)\) rappresenta il numero di volte in cui la coppia stato–azione è stata osservata. Una volta stimati \(\hat{P}\) e \(\hat{r}\), si definisce un MDP stimato \((S,A,\hat{P},\hat{R},\gamma)\) e si calcola \(V^\pi\) utilizzando le equazioni di Bellman o metodi di dynamic programming.

Questo approccio presenta alcune proprietà rilevanti:

• Consistenza: se il processo è Markoviano e i dati sono sufficienti, le stime convergono al modello reale.
• Efficienza statistica: sfrutta pienamente la struttura del modello stimato, risultando spesso molto accurato in termini di campioni richiesti.
• Elevato costo computazionale: dopo ogni aggiornamento del modello è necessario risolvere nuovamente il problema di pianificazione, con costo \(O(|S|^3)\) per la soluzione analitica o \(O(|S|^2 |A|)\) per metodi iterativi.

Il principio di certainty equivalence evidenzia quindi un trade-off fondamentale: l’approccio è molto efficiente in termini di dati, ma può essere computazionalmente oneroso. Inoltre, il modello stimato può essere utilizzato non solo per valutazione on-policy, ma anche per off-policy evaluation, poiché la stima del modello consente di simulare il comportamento di policy diverse da quella che ha generato i dati.

Questo confronto tra approcci model-based e model-free chiarisce il panorama metodologico della policy evaluation: da un lato la costruzione esplicita del modello con pianificazione, dall’altro l’apprendimento diretto dei valori a partire dall’esperienza, senza passare per una rappresentazione esplicita delle dinamiche del mondo.

Certainty Equivalence \(V^\pi\) MLE MDP Model Estimates

Prova a ricostruire il modello al fine della valutazione della policy senza disporre del modello reale, a partire dagli episodi.

L'algoritmo prevede, dopo ogni tupla (s,a,r,s') di:

- Ricalcolare il modello MLE MDP  per (s,a), sia per il modello dinamico delle transizioni come \(\hat{P}(s'|s,a)=\frac{1}{N(s,a)}\sum_{k=1}^i 1(s_k=s,a_k,=a,s_{k+1}=s')\)  e sia per il modello delle ricompense \(\hat{r}(s,a)=\frac{1}{N(s,a)} \sum_{k=1}^{i} 1(s_k=s,a_k=a)r_k\)

- Calcolare \(V^\pi\) utilizzando MLE MDP con un metodo di programmazione dinamica (policy o value iteration)

Caratteristiche dell'approccio:
- Costo di MLE e MDP planning iterativo a ogni passo  nell'ordine di \(O(|S|^2|A|) \) , computazionalmente rilevante;

- Molto efficiente sui dati forniti

- Consistente per i modelli Markoviani

- può essere utilizzato facilmente per la valutazione off-policy

Batch Policy Evaluation

Batch/Offline per un insieme di K episodi, campionando ripetutatmente da K e applicando MC o TD(0).

Campionando all'infinito vediamo che convergono a due differenti valori:
- MC batch converge al MSE, minimizzando rispetto ai ritorni osservati;
- TD(0) batch converge alla policy \(V^\pi\) per il MDP con la stima MLE, esattamente come il DP con certainity equivalence. (bootstrapping markoviano)

Controllo: MC Policy Evaluation with Epsilon-Greedy Policies

Uno degli aspetti centrali del Reinforcement Learning (RL) nel contesto model-free è il bilanciamento esplorazione-sfruttamento. L’agente interagisce con l’ambiente: compie azioni e riceve osservazioni e ricompense. Il suo obiettivo è imparare a scegliere le azioni che massimizzano la ricompensa totale attesa nel lungo periodo.  E' necessario quindi bilanciare i due aspetti:

• Esplorazione: per imparare quali azioni portano a buone ricompense, l’agente deve necessariamente provarle. Non può conoscere in anticipo il valore di un’azione senza averla sperimentata.

• Sfruttamento: se l’agente prova continuamente nuove azioni, dedica meno tempo a quelle che, sulla base dell’esperienza passata, garantiscono alte ricompense. Per massimizzare il risultato deve quindi sfruttare ciò che ha già appreso.

Una delle strategie più semplici ed efficaci per gestire il dilemma esplorazione-sfruttamento è la politica ε-greedy, definita ispetto a un valore stato-azione Q(s,a)  come:

\(\pi(a|s)= \begin{cases} \arg \max_a Q(s,a) & \text{con probabilita'} \ 1-\epsilon+\frac{\epsilon}{|A|} \\ a'\ne \arg \max_a Q(s,a) & \text{con probabilita'} \ \frac{\epsilon}{|A|} \end{cases} \)

In pratica si seleziona l'azione già individuata a valore stato-azione massimo con probabilità 1-\(\epsilon \) altrimenti si prova una azione scelta casualmente tra le |A| disponibili. In questo modo:

• lo sfruttamento (exploitation) greedy è garantito perché l’agente tende a scegliere l’azione ritenuta migliore  con probabilità 1-\(\epsilon \) ;

• l’esplorazione (exploration) random non viene trascurata, poiché l’agente mantiene sempre una probabilità di provare alternative potenzialmente migliori.

Anche in questo caso si può dimostrare che, per ogni politica \(\varepsilon\)-greedy \(\pi_i\), la politica \(\pi_{i+1}\) definita in modo \(\varepsilon\)-greedy rispetto a \(Q^{\pi_i}\) rappresenta un miglioramento monotono, ossia \(V^{\pi_{i+1}} \geq V^{\pi_i}\).

Formalmente, il valore atteso scegliendo l'azione individuata da una politica aggiornata, può essere espresso come:

\[ Q^{\pi_i}(s, \pi_{i+1}(s)) = \sum_{a \in A} \pi_{i+1}(a|s) Q^{\pi_i}(s,a) = \frac{\varepsilon}{|A|} \left[ \sum_{a \in A} Q^{\pi_i}(s,a) \right] + (1-\varepsilon) \max_a Q^{\pi_i}(s,a) \]

Vediamo come possiamo integrare questa policy con l'algoritmo Monte Carlo, applicato alla funzione stato-valore Q(s,a) anzichè alla funzione valore V(s):
 

• Inizializza \(Q(s,a)=0,\ N(s,a)=0\ \forall (s,a)\), setta \(\varepsilon=1,\ k=1\)
• \(\pi_k = \varepsilon\text{-greedy}(Q)\) // Crea ε-greedy policy iniziale
• loop
  • Campiona k-mo \((s_{k,1}, a_{k,1}, r_{k,1}, s_{k,2}, \ldots, s_{k,T})\) secondo \(\pi_k\) stocastica
  • \(G_{k,t} = r_{k,t} + \gamma r_{k,t+1} + \gamma^2 r_{k,t+2} + \cdots + \gamma^{T_i-t} r_{k,T_i}\)
  • for \(t = 1, \ldots, T\) do
    • if prima volta che incontri \((s,a)\) nell'episodio k then
      • \(N(s,a) = N(s,a) + 1\)
      • \(Q(s_t,a_t) = Q(s_t,a_t) + \frac{1}{N(s,a)}(G_{k,t} - Q(s_t,a_t))\)
    • end if
  • end for
  • \(k = k+1,\ \varepsilon = 1/k\)
  • \(\pi_k = \varepsilon\text{-greedy}(Q)\) // Miglioramento della policy
• end loop

In questo algoritmo vediamo che Q non è una stima di \(Q^{\pi_k}\), ma una media pesata di tutti i dati derivanti dalle applicazioni delle policy precedenti testate, sebbene l'obbiettivo sia convergere  a un \(Q^*\) ottimale

Function Approximation

Nel Reinforcement Learning, memorizzare o apprendere in modo esplicito tutte le informazioni per ogni singolo stato e azione diventa rapidamente impraticabile. Sia per il modello delle dinamiche di transizione, sia per le ricompense, sia per i valori degli stati, sia per i valori stato-azione, sia per la la policy.

L’approssimazione di funzione nasce per superare questo limite, puntando a una rappresentazione più compatta che sia in grado di generalizzare attraverso stati e azioni simili.

I principali vantaggi sono:

• riduzione della memoria necessaria a memorizzare modelli, funzioni di valore e policy;

• riduzione del costo computazionale richiesto per calcolare valori e strategie;

• riduzione dell’esperienza necessaria per apprendere una buona approssimazione di modelli, funzioni di valore e policy.

In sintesi, l’approssimazione di funzione permette di affrontare scenari complessi e di grandi dimensioni, rendendo il Reinforcement Learning più scalabile ed efficace.

Il problema diventa analogo a un compito di apprendimento supervisionato: disponiamo infatti di un insieme di coppie \(((s,a), Q^{\pi}(s,a))\) con obiettivo di trovare la migliore rappresentazione approssimata di \(Q^{\pi}\) all’interno di una classe di funzioni parametrizzate, ad esempio \(\hat{Q}(s,a;w)\), dove \(w\) indica i parametri da ottimizzare , attraverso una linearizzazione o una rete neurale ad esempio. In questo modo, si riduce la complessità della rappresentazione mantenendo la capacità di stimare valori utili per la valutazione di una policy.

 L’obiettivo è trovare il vettore di parametri \(w\) che minimizza la perdita tra la funzione di valore vera \(Q^{\pi}(s,a)\) e la sua approssimazione \(\hat{Q}(s,a;w)\). La funzione di costo comunemente utilizzata a questo fine è il MSE (errore quadratico medio) : \( J(w) = \mathbb{E}_{\pi}\left[(Q^{\pi}(s,a) - \hat{Q}(s,a;w))^2\right] \)

Per minimizzare questa funzione si utilizza generalmente l'algoritmo di discesa del gradiente, che aggiorna i parametri nella direzione della massima discesa locale della quantità \( \Delta w = -\tfrac{1}{2}\alpha \nabla_w J(w) = \alpha \mathbb{E}_{\pi}\left[(Q^{\pi}(s,a) - \hat{Q}(s,a;w))\right] \nabla_w \hat{Q}(s,a;w)\) , dove \(\alpha\) è il learning rate, anche nella versione SGD (stochastic gradient descent) che utilizza un numero finito, spesso anche uno solo, di campioni per stimare il gradiente, algoritmo più leggero e adatto a grandi dataset.

Il tema centrale è come ottenere questi valori di riferimento   \(Q^{\pi}(s,a)\)  con i vari algoritmi in un contesto model-free, da utilizzare poi per il supervised learning.

In un primo approccio di Monte Carlo Value Function Approximation possiamo utilizzare direttamente i vari \(G_t\) come campioni del ritorno atteso \(Q^{\pi}(s_t,a_t)\) , in modo da fare supervised learning su di un dataset \(\langle (s_1,a_1),G_1 \rangle , \langle (s_2,a_2),G_2 \rangle , \cdots , \langle (s_T,a_T),G_T \rangle\).

Questo l'algoritmo di policy evaluation con l'aggiornamento dei pesi w su k episodi in base ad una policy fissata \(\pi\) :

• Inizializza \(w\), \(k=1\)
• loop
  • Campiona il k-esimo episodio \((s_{k,1}, a_{k,1}, r_{k,1}, s_{k,2}, \ldots, s_{k,L_k})\) dato \(\pi\)
  • per \(t = 1, \ldots, L_k\) fai
    • se è la prima visita a \((s,a)\) nell'episodio k allora
      • Calcola \(G_t(s,a) = \sum_{j=t}^{L_k} r_{k,j}\)
      • Calcola il gradiente: \(\nabla_w J(w) = -2 \big[ G_t(s,a) - \hat{Q}(s_t,a_t;w) \big] \nabla_w \hat{Q}(s_t,a_t;w)\)
      • Aggiorna i pesi \(\Delta w\)
    • end if
  • end for
  • Incrementa \(k = k+1\)
• end loop

Utilizzando invece un approccio di Temporal Difference TD(0) ricordiamo che l'algoritmo andava ad aggiornare la \(V^\pi(s)=V^\pi(s) + \alpha(r+\gamma V^\pi(s')-V^\pi(s))\) in ottica di bootstrapping, con un target \(r+\gamma V^\pi(s')\),
In ottica di function approximation il nostro target diverrà quindi \(r+\gamma \hat{V^\pi}(s';w)\) , spostando il problema in ottica di supervised learning con un dataset formato dalle coppie \(\langle s_1,r_1+\gamma \hat{V^\pi}(s_2,w) \rangle, \langle s_2,r_2+\gamma \hat{V^\pi}(s_3,w) \rangle, \cdots\)  attraverso le quali dovremo determinare i valori di w che minimizzano la funzione di costo MSE
\(J(w)=\Bbb E_\pi[(r_j+\gamma \hat{V^\pi}(s_{j+1},w)-\hat{V^\pi}(s_{j},w))^2]\)  attraverso algoritmi di discesa del gradiente.

In-context learning: utilizziamo un Language Model per svolgere i task semplicemente agendo sul testo del prompt.

Few-shot In-context learning: il prompt include esempi del task da svolgere e si presume che il LM non sia stato addestrato su task simili.

Zero-shot In-context learning: Il prompt non include esempi del task da svolgere, sebbene possa contenere altre istruzioni riguardo il task, e si presume che il LM non sia stato addestrato su task simili.

LM Autoregressivi: GPT utilizza una funzione di costo autoregressiva del tipo \(\displaystyle \max_\theta \sum_{t=1}^T \frac{e^{e(x_t)^\top h_\theta(\mathbf x_{1:t-1})}} {\displaystyle \sum_{x' \in V}e^{e(x')^\top h_\theta(\mathbf x_{1:t-1})}}\) che mira a fornire per ogni posizione un vettore di probabilità con massima similarità rispetto all'embedding del carattere effettivo.

Instruction fine-tuning: Il vero fine tuning si effettua in modo supervised e semi-supervised, prima fornendo prompt (campionato o manuale) e una risposta manuale.  In una seconda fase si campiona il prompt e si fa un ranking degli output possibili del sistema.

Self-instruct: In questo particolare caso si addestra il LM, a partire da un set di vari task inseriti manualmente, a generare nuovi esempi di task sui quali addestrarsi a sua volta, che il sistema distinguerà in task di classificazione e generazione, da inserire nel set di task iniziali qualora siano ritenuti qualitativamente adeguati.