Sessione 2

2019 12 02

Ora inizieremo a considerare il fatto che non abbiamo a disposizione il modello, parliamo del Model-free prediction che rappresenta il vero Reinforcement learning. Nelle lezioni precedenti è stato fatta quella che viene chiamata "pianficazione" o "dynamic programming".

Iniziamo a parlare di predizione che ci fa capire quanto vale una policy prefissata.

Alcuni dei metodi che vedremo sono "Monte Carlo" e "Temporal difference".

Monte Carlo è un metodo che stima il valore degli stati facendo delle prove, però questo può essere oneroso perchè i passi possono essere tanti, in questi casi allora si fanno dei passi in avanti e si fa una differenza temporale tra il passo x e il passo x+y e si fa la dirrenza.

Entriamo quindi nel RL vero e proprio, verrà utilizzata la tecnica GPI che sta per "General Policy Iteration": prediction, improvemene, iteration.

Metodo Monte Carlo prediction

E' un metodo che stima una quantità facendo dei campionamenti casuali. (per es. Il metodo MC si usa per approssimare pigrego (pi))

OBIETTIVO: stimare il valore dello stato S della policy pi. Lo stato "s" è il valore medio del ritorno Gt che ottengo partendo al tempo "t" dallo stato "s". Dallo stato faccio un epidio fino alla fine, ne faccio tanti e poi ottengo la probabilità di ottenere questi ritorni.

La legge dei grandi numeri ci aiuta a capire le probabilità dei ritorni.

VANTAGGI DEL MC:

1) non ci serve conoscere le probabilità, in quanto quando facciamo l'episodia la ricompensa ci arriva

2) il boostrapping, quando stimo il valore di uno stato utilizzando il valore degli stati successivi che MC non usa. (non mi è chiaro)

Vogliamo quindi stimare V_pi(s), cerchiamo in primis di capire cosa significa "stimare": è una regola che permette di approssimare la quantità che stiamo cercando. La regola è il "metodo Monte Carlo".

La regola può essere:

0) scelgo una policy (Es. quella uniforme)

1) faccio un episodio da "s" e memorizzo il ritorno.

2) faccio la media aritmetica (G(1)+G(2)+... G(N) )/N <- queste sono tutte variabili aleatorie

3) torno in "s"

4) ritono allo step 1

questa serie di passi è lo stimatore MC di V_pi(s)

Quindi G(k) è il ritorno dell'episodio kappesimo, dove questi ritorni (variabili aleatorie) devono essere identicamente distribuite e indipendenti ovvero che un epidosio non influenzi quelli successivi. (detto anche IID)

Di seguito il pseudo codice:

spiegone:

genero l'episodio come sequenza di stato, azione, reward e inizializzo l'episodio
inizializzo il ritorno (G <- 0)
il ciclo ripercorre l'episodio dalla fine all'inizio, questo metodo aspetta la fine dell'episodio, si dice quindi che è un metodo "off line". Per questo motivo il valore G inizializzato a zero è ritorno dell'ultimo stato.
Sommo quindi le rewards fino allo stato iniziale "s"
A questo punto viene memorizzato nel valore dello stato V(St) tutti i ritorni dal quello stato in poi. Es:

2019 12 0316

Siamo quindi nel caso in cui non abbiamo il modello, dobbiamo quindi stimare le cose (predizione). Dobbiamo quindi applicare il modello Monte Carlo. Nella pratica il metodo MC fa un sacco di episodi e poi per la legge dei grandi numeri = se abbiamo delle variabili aleatorie indipendenti, la media di infiniti esperimenti tende al valor medio.

Attenzione esiste una ottimizzazione dele calcolo della media in modo che non si tengano in memoria tutti gli elementi per fare la media. (anche se dicono che potrebbe essere "instabile")

attenzione, adesso sostituisco 1/K (dove K è il passo, numero utile per fare la media aritmetica) con un valore alpha, che empiricamente comunque converge.

Alpha torna utile in quegli ambienti dove dopo X episodi (con X abbastanza grande) l'ambiente cambia leggermente (e si dice che l'ambiene non è stazionario, ovvero il modello cambia nel tempo) e quindi i valori dei primi episodi sono meno veritieri degli ultimi. (quindi è una pesatura degli episodi non uniforme) Alpha non deve quindi tener traccia del numero di episodi che ho fatto.

Altra variabile aleatoria è la policy che, al pari dell'ambiente, potrebbe cambiare in quanto cerchiamo di migliorarla. Quindi a maggior ragione bisogna utilizzare il valore apha e non la media aritmetica.

Temporal-Differece prediction

Mentre con il metodo MC abbiamo predetto e stimato il valore facendo l'episodio, abbiamo fatto una stima.

Il metodo "tempora difference" TD, funziona così:

inizia mettendo in ogni stato un valore random, chiamimolo V0(S)

adesso cerchiamo di migliorare la stima, facciamo un'azione con la nostra policy e salviamo la nuova stima in V1(S)

Una differenza con MC è data dal fatto che MC fa un intero episodio, TD invece lavoro uno step alla volta andanso da s a s'.