Model Free Prediction Flashcards
Cos’è il model free RL?
Quando si parla di “model-free” nel contesto del reinforcement learning, si intende che l’agente non ha conoscenza diretta o accesso al modello di transizione di stato, cioè non conosce le probabilità di transizione o le ricompense associate a tali transizioni. Questo significa che l’agente non può utilizzare le informazioni del modello per pianificare in anticipo le sue azioni o per valutare le value function offline.
Invece, l’agente deve interagire direttamente con l’ambiente, eseguendo azioni e osservando gli stati risultanti e le ricompense corrispondenti. Utilizzando queste interazioni, l’agente cerca di apprendere una policy ottimale o di stimare le value function senza fare affidamento su un modello esplicito dell’ambiente.
Cosa sono i metodi Monte-Carlo?
i metodi Monte Carlo vengono utilizzati per stimare i valori delle azioni o delle situazioni (stati) in un ambiente basandosi sull’esperienza diretta acquisita attraverso l’interazione con esso.
Cos’è l’aggiornamento della media incrementale nei metodi monte carlo?
L’aggiornamento della media incrementale è un concetto chiave nei metodi Monte Carlo, usato per calcolare stime più accurate dei valori stimati durante l’apprendimento.
Supponiamo di avere una sequenza di valori x_1,x_2,…,x_n
e vogliamo calcolare la media di questi valori. L’aggiornamento della media incrementale si svolge iterativamente, aggiungendo un nuovo valore x_n+1
alla media già calcolata dei primi n valori.
La formula per aggiornare la media al passo n+1 considerando un nuovo valore x_n+1 è:
media_{n+1} = media_n + (1 / (n+1)) * (x_{n+1} - media_n)
Dove:
-media_{n+1} rappresenta la nuova media dopo aver incluso x_{n+1}.
-media_n indica la media precedente dei primi n valori.
-x_{n+1} è il nuovo valore aggiunto.
-n rappresenta il numero totale di valori considerati fino a quel punto, incluso x_{n+1}.
Cos’è il Temporal-Difference Learning?
Il Temporal-Difference (TD) Learning è una tecnica chiave nell’apprendimento per rinforzo che combina elementi di due approcci principali: il Monte Carlo e la programmazione dinamica.
L’obiettivo del TD Learning è stimare i valori delle azioni o degli stati (noti come valori Q o valori V) tramite l’apprendimento dall’esperienza di interazione con l’ambiente, senza la necessità di avere episodi completi come nel Monte Carlo. Invece di aspettare fino alla fine di un episodio per aggiornare le stime dei valori, il TD Learning aggiorna le stime ad ogni passo temporale, basandosi sulla differenza tra le stime attuali e le stime successive.
La formula chiave del TD Learning è l’equazione di aggiornamento TD, che può variare leggermente a seconda del contesto, ma in generale è rappresentata come:
V(St)←V(S_t)+α⋅[R_{t+1}+γ⋅V(S_{t+1})−V(St)]
Dove:
-V(St) è la stima del valore dello stato S_t al tempo t.
-α è il tasso di apprendimento (learning rate) che regola l’importanza di nuove informazioni rispetto alle informazioni precedentemente apprese.
-R_{t+1} è la ricompensa ottenuta dopo l’azione nello stato S t
-γ è il fattore di sconto che determina l’importanza delle ricompense future rispetto a quelle immediate.
-V(S{t+1}) è la stima del valore del prossimo stato S_{t+1}
In pratica, il TD Learning calcola l’errore tra la stima corrente del valore di uno stato e la stima successiva, aggiornando la stima corrente con un passo proporzionale a questo errore. Questo processo permette di aggiornare gradualmente le stime dei valori in ogni passo temporale durante l’interazione con l’ambiente, senza la necessità di completare interi episodi come nel Monte Carlo.
Il TD Learning è flessibile e può essere implementato in vari algoritmi, come il TD(0), il SARSA (State-Action-Reward-State-Action) o il Q-learning, che sfruttano l’idea dell’aggiornamento dei valori basato sull’errore temporale tra le stime correnti e quelle successive. Questa flessibilità rende il TD Learning una tecnica fondamentale nell’ambito dell’apprendimento per rinforzo.
Vantaggi e Svantaggi di MC e TD
Vantaggi di Monte Carlo (MC):
Vantaggi:
1. Convergenza asintotica garantita: I metodi MC convergono alla soluzione ottimale quando il numero di episodi tende all’infinito.
- Nessuna necessità di conoscere la dinamica dell’ambiente: MC non richiede una conoscenza pregressa o modelli dell’ambiente per stimare i valori di stato-azione o di stato.
Svantaggi di Monte Carlo (MC):
Svantaggi:
1. Richiede episodi completi: MC deve completare interi episodi prima di poter aggiornare le stime dei valori.
- Varianza elevata: L’accuratezza delle stime dei valori può essere influenzata da episodi rari o non rappresentativi.
3.MC non sfrutta la proprietà di Markov: Solitamente più efficace in ambienti non di Markov
Vantaggi di Temporal-Difference (TD) Learning:
Vantaggi:
1. Aggiornamenti a ogni passo temporale: TD Learning aggiorna le stime dei valori ad ogni passo temporale.
- Non richiede episodi completi: TD Learning può aggiornare le stime dei valori continuamente.
- TD sfrutta la proprietà di Markov: Solitamente più efficiente in ambienti di Markov
Svantaggi di Temporal-Difference (TD) Learning:
Svantaggi:
1. Convergenza non sempre garantita: A differenza di MC, TD Learning non garantisce la convergenza agli ottimi globali.
- Sensibile alla scelta del tasso di apprendimento: La scelta del tasso di apprendimento può influenzare notevolmente le prestazioni di TD Learning.
In sintesi, MC è più affidabile in situazioni dove è possibile eseguire molti episodi completi, mentre TD Learning può essere più efficiente e flessibile nel continuo aggiornamento delle stime dei valori. La scelta tra i due dipende dalle caratteristiche specifiche del problema, dalle risorse disponibili e dalla natura dell’ambiente di apprendimento. In molti casi, si utilizzano approcci ibridi che combinano elementi di entrambi i metodi per ottenere i vantaggi di entrambi.
Cos’è l’n-step return?
è una generalizzazione del TD
In modo formale, l’n-step return rappresenta una stima dei valori di stato o di stato-azione, considerando le ricompense ottenute nei prossimi n passi temporali a partire da uno stato specifico.
L’n-step return per i valori di stato è rappresentato come:
G^{(n)}t = R{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … + γ^{n-1} R_{t+n} + γ^n V(S_{t+n})
Dove:
- G^{(n)}t è l’n-step return dal tempo t al tempo t+n.
- R{t+i} è la ricompensa ottenuta al passo temporale t+i.
- γ è il fattore di sconto che indica l’importanza delle ricompense future rispetto a quelle immediate.
- V(S_{t+n}) rappresenta la stima del valore dello stato S_{t+n} al tempo t+n.
L’n-step return è utile poiché consente di bilanciare l’importanza delle ricompense immediate con quelle future, fornendo una stima della somma delle ricompense future attese fino a n passi successivi. Questo concetto è centrale in alcune tecniche di apprendimento per rinforzo, consentendo di stimare i valori di stato o di stato-azione basandosi su una finestra temporale n di passi.
Cos’è il λ-return?
Il γ-return, o lambda-return, è un concetto fondamentale nell’apprendimento per rinforzo e si riferisce alla somma delle ricompense future attese, pesate da un fattore di sconto γ.
In modo formale, il γ-return è definito come segue con i pesi (1-γ)γ^n-1:
FORMULA
Il γ-return è utilizzato per valutare la bontà di una politica o per stimare i valori di stato o di stato-azione. Rappresenta la somma delle ricompense future attese, dove il valore di γ influenza quanto peso viene dato alle ricompense più lontane nel tempo. Un valore di γ vicino a 0 dà maggior peso alle ricompense immediate, mentre un valore vicino a 1 considera più importanti anche le ricompense a lungo termine.
Forward view e backward view TD
Forward view: Gli algoritmi come il Monte Carlo (MC) richiedono episodi completi per calcolare i valori successivi della Value Function. Questo approccio prevede di aggiornare gli stati in base alle ricompense ottenute negli stati successivi.
Backward view TD(lambda): Si utilizza un approccio “backward view”, dove una volta calcolato il valore per uno stato, lo si comunica agli stati precedenti. Questo permette un aggiornamento in tempo reale, senza bisogno di informazioni future.
Eligibility traces: Per determinare quali stati sono influenti per una determinata situazione, si utilizzano le eligibility traces. Queste assegnano valori basati sulla frequenza e sulla recente visita di uno stato, permettendo di calcolare quale stato ha maggior peso nell’aggiornamento della Value Function.
In sintesi, mentre il forward view si basa sul calcolo dei valori successivi della Value Function, il backward view TD(lambda) permette di aggiornare gli stati in base ai valori precedenti. Le eligibility traces sono utilizzate per determinare l’importanza di uno stato nell’aggiornamento della Value Function.
first visit montecarlo e every visit montecarlo
First Visit Monte Carlo Policy Evaluation:
Questa versione calcola il guadagno solo per la prima occorrenza di ogni stato in ogni episodio.
Si calcola la media dei guadagni solo per i primi incontri di ogni stato, ignorando le ripetizioni.
Per calcolare in maniera efficiente il guadagno, si utilizza una procedura che parte dall’episodio finale e ritorna all’inizio.
Il fine è valutare gli stati basandosi sulla policy e ottenere una stima dei loro valori.
Every Visit Monte Carlo Policy Evaluation:
Questa versione considera tutti i guadagni di ogni stato in ogni episodio, non solo la prima occorrenza.
Non viene effettuato alcun controllo sulla ripetizione degli stati, quindi si prendono in considerazione tutte le occorrenze.
Si dimostra che questa versione converge al valore corretto in modo più rapido rispetto alla versione first visit, ma non richiede l’ultimo controllo.
Anche se entrambe le versioni convergono al valore corretto con il crescere del numero di episodi, spesso si preferisce questa versione per la sua praticità e per ottenere stime più rapide dei valori degli stati.
In sintesi, mentre la prima versione calcola solo la prima occorrenza di ogni stato in ogni episodio, la seconda considera tutte le occorrenze. La seconda versione converge più velocemente al valore corretto, ma entrambe forniscono stime utili dei valori degli stati basate sulla policy.
