Sessione 2
Model-free control (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) 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)
NB: MC è un metodo "off line" ovvero che impare dopo aver finito l'episodio.
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 stat o 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 stiamo migliorando, per poi metterle in qualche modo a confronto ed eventualmente cambiare la policy con quella nuova trovata tramite esplorazione.
General Policy Iteration
Come miglioro la policy? Basta fare il calcolo della funzione valore stato-azione Q(s,a) anzichè il valore della stato azione V(s) in modo da ottere la probabilità dell'azione. Ok, ma questo non serve realmente per migliorare la policy in quanto agisce sempre in manidera greedy sulla stessa policy. Per migliorare la policy quindi è necessario scegliere "ogni tanto" delle azioni che non sono greedy in modo da effettuare l'esplorazione. Ricordo per miglioramento della policy si intende: "il valore della nuova policy è migliore della precedente in tutti gli stati".
Di qui il metodo "epsisol greedy" (ε-greedy) , dove epsilon è la percentuale di scelta di una azione casuale. (in genere un valore piccolo es. 10%)
Bisogna quindi lavorare con policy stato-azione con probabilità > 0 in particolare la percentuale deve essere maggiore di ε. (questo concetto non mi è chiaro)
GL-IE (teorema generale)
Come deve funzionare l'algoritmo epsilon greedy? L'algoritmo da utilizzare è il GLIE che, per definizione, converge alla policy ottimale, ma cosa significa GLIE e come funziona?
GL= greedy in the limit: si richiede che nella policy iteration (valutazione della policy e miglioramento) che il miglioramento tenda ad una policy greedy. Che significa che la policy a cui si converge è greedy.
IE= infinite exploration: tutte le coppie stato-azione siano visitate dall'algoritmo infinite volte. (richiesto dalla legge dei numeri)
Se GL e IE sono confermati ed implementati allora l'algoritmo è ottimale.
Ma come fare? La risposta è implementare l'algoritmo espisolon-greedy facendo in modo che epsilon decresca al crescere degli episodi k. Il che significa che ad un certo punto epsilon tenderà a zero.
On-policy MC (Monte Carlo)
Vedi lezione 2020 01 13
Per calcolare la policy e migliorarla va usato il Q-Value.
Partenze esplorative (exploring starts)
Un altro algorino GLIE è per es. quello che implementa le "partenze esplorative" ovvero la scelta causale di uno stato di partenza.
On-policy TD (temporal difference)
Anche per il TD dovremmo utilizzare il Q-Vaue, l'algoritmo da utilzzare si chiama "Sarsa".
Si chiama così perchè parte dalla coppia Stato-Azione vede ricompensa abbiamo ottenuto, vede lo stato successivo ottenuto, prende una nuova azione (quindi va in un nuovo nodo Stato-Azione) e si ferma. Ricordo che il concetto di stato stato nel "model free" è sempre riferito allo Stato-Azione. (vedi diagramma di backup sotto riportata)
Predizione
Per la fase di predizione TD, quando arrivo nel nuovo nodo vedo il valore Q-Value associato allo stato-azione di arrivo. Anche qui vale la formula classica di calcolo del valore stato per TD con la differenza che, essendo model free, dovremo utilizzare il Q-Value e quindi la combianazine Stato-Azione. Anche qui alpha rappresenta il fattore di apprendimento, la tabella dei q-value va anche qui va inizializzata con valori a piacimento, alla fine dei vari episodi il tutto dovrebbe convergere.
e quindi il diagramma di convergenza
e lo psudo-codice:
Scegliamo il tasso di apprendimento (alpha), inizializziamo la tabella degli stati-azioni facendo attenzione a impostare il valore dello stato terminale a zero. (altrimenti avremo una distorsione nel valore iniziale che non verrà mai corretta)
Controllo epsilon-greedy
Per migliorare la policy utilizzo il metodo epsiolo-greedy ovvero partendo dalla matrice dove ogni cella contine il valori stato-azione... TODO 10:00
Scegliamo la partenza, scegliamo un'azione dallo stato S utilizzando una policy epsilon-greedy. Quando lo stato è terminale riconciamo.
Funziona? si purchè siano soddisfatte delle ipotesi (teoriche) che sono:
1) la successione di policy che ottengo devono tutte darmi tutte esplorazini infinite (soft) e devono essere greedy-in-limit, ovvero con espisol-greedy non costante, cioè che deve tendere - all'aumentare di k - al valore zero
2) il tasso di apprendimento alpha che tende allo zero velocemente ma non troppo..
Però queste due condizioni teoriche non vengono quasi mai rispettate, quindi in genere si tengono come costanti.
Esiste anche al versione a N step di Sarsa:
e questo lo pseudo codice:
Metodi off-policy
- risolve il dilemma esplorazione-sfruttamento molto bene
- l'esperienza pregressa può essere acquisita (importata) dall'esterno ed essere sfruttata
- posso riusare quado voglio le esperienza generata nelle policy precedenti
- posso imparare policy multiple ovvero seguo una policy da questa ne derivo N che possono essere tutte ottimali
Prerequisito di utilizzo
Se un'azione ha probabilità positiva di essere scelta allora deve essere positiva anche la probabilità di scelta di un'azione della policy di comportamento, ovvero: pi(s,a) > 0 -> u(s,a) > 0
Quindi la policy che impariamo può/deve essere deterministica, mentre la policy di comportamento deve essere stocastica.
1:12:45