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:

1.  genero l'episodio come sequenza di stato, azione, reward e inizializzo l'episodio
2. inizializzo il ritorno (G <- 0)
3. 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.
4. Sommo quindi le rewards fino allo stato iniziale "s"
5.  A questo punto viene memorizzato nel valore dello stato V(St) tutti i ritorni dal quello stato in poi. Es:

 2019 12 16

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'.

Un'altra differenza rispetto a MC è che è un metodo basato sul "boostrapping" ovvero ogni stato è basato sul valore del precedente, e non c'è bisogno che l'sperienza attivi alla fine per aggiornare gli stati valori.

E questo è l'algoritmo:

Model-free control (ripassone)Monte Carlo e Temporal difference)

Nel capitolo precedente abbiamo svolto un lavoro di pianificazione e non di appredimento per rinforzo in quanto avevamo il modello (ambiente) che ci diceva con quale probabilità svolgeva le azioni. La policy (pi) era in qualche modo nota, questo però non rappresenta la realtà in quanto il modello, nella natura delle cose, non ci viene dato apriori, dobbiamo quindi trovare un modo per ricavarlo, come fare? Bene bisogna quindi interrogare l'ambiete e con le risposte ottenute ricavare in quale modo il modello. 

Si deve quindi fare un lavoro di predizione e di miglioramento del modello (policy)

Predizione

E' model free perchè non abbiamo a priori il modello, cosa che invece avevamo all'inizio del corso con la pianificazione.

Dobbiamo quindi fare un lavoro di predizione che si basa su due modalità:

1)1) il primo metodo è detto Monte Carlo (MC), nella pratica voglio "imparare" il valore delle mie azioni iteragendo con l'ambiente. Svolgo quindi un episodio partendo dallo stato k e raccolgo tutti i valori, e relative reward, degli stati fino allo stato terminale, faccio la media aritmetica G(T) e salvo il valore ottenuto nello stato k. Svolgo questo lavoro per N volte per tutti gli M stati, in questo modo a tendere, sempre per la legge dei grandi numeri, mi avvicino al valore reale dello stato. (da notere che con questo metodo non devo inizializzare gli stati in quanto interrogo subito l'ambiente)

2)2) il secondo metodo, detto anche Temporal difference (TD). E' un metodo iterativo, per prima cosa devi inizializzare tutti gli stati con dei valori che potrebbero anche essere random. Partendo dallo stao k faccio una sola azione per arrivare nello stato k+1 e raccolgo il valore dello stato e la rimpensa corrispondente all'azione. Torno quindi allo stato in cui ero parito (k) e aggiorno il valore. Come aggiorno il valore di K? V(k) = V(k) + alpha(R + V(k+1) - Vk) dove aplha è il fattore di apprendimento, più è grande più do importanza al valore restituito dallo stato k+1. Che significa sommare il valore dello stato attuale alla somma data dalla reward più la differenza tra il valore dello stato successivo e il valore dello stato attuale, il tutto moltiplicato per il tasso di apprendimento alpha. Da notare che la differenza tra V(k) e alpha(R + V(k+1) - Vk) è detta errore, che posso variare con il tasso di apprendimento alpha.  Poi si continua passando allo stato successvo e faccio la stessa cosa aggiornando V(k+1) con i valori ricavati da V(k+2). Anche quindi come con il MC faccio passare tutti gli stati M e lo faccio per N volte, in questo modo i valori a tendere (dopo un numero considerevole di volte) convergeranno al valore reale.

Miglioramento e controllo

Nella predizione, viene sempre applicata la stessa policy, ovvamente anche la policy deve migliorare nel tempo, ecco che quindi dopo il ciclo di predizione deve seguire il ciclo di miglioramentento e controllo della policy. Questo significa che i valori  degli stati migliorarano nella fase di predizione e che la scelta degli stati stessi, conseguenza del miglioramento della policy, cambia in quanto le azioni cambiano (in genere) con il cambio della policy per via del miglioramento della stessa.

Esistono due famiglie di metodi me fare miglioramento e controllo e sono relative ai due metodi visti per fare predizione, e sono:

1) On-policy MC control

2) On-policy TD control

3) Off-policy prediction

4) Off-policy control

Che differenza c'è tra i metodi on-policy e off-policy?

On-policy

Questi metodi nella pratica utilizzano la stessa policy migliorandola. Ovvero agendo "greedy" vengono scelte le azioni che massimizzano il risultato e che ne migliorarno la polcy, ma, la policy seppur migliorata è sempre la stessa.

Off-policy

Con i metodi off-policy viene introdotto un fattore di "esplorazione" che in qualche modo crea delle policy nuove "parallele" a quella che stimo migliorando, per poi metterle in qualche modo a confronto ed eventualmente cambiare la policy con quella nuova trovata tramite esplorazione.

20:50