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 a priori, 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.
Predizione
E' model free perchè non abbiamo a priori il modello, cosa che invece avevamo all'inizio del corso con la pianificazione.
Dovremo quindi far uso di "stimatori" in grado di ricostruire nella maniera più federe possibile il modello.
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 quando 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.
Predizione: Regole di update dei metodi di predizione off-policy:
Viene suggerito di non considerare il metodo off-policy con MC in quanto, per via dei troppi stati da esplorare nell'episodio, viene generata troppa varianza dei valori, il che rende la formula molto complicata.
Invece il metodo off-polcy funziona bene con il temporal difference, in quanto il rapporto tra u (mu) e pi risulta essere un rapporto tra probabilità il che non presenta il difetto della varianza.
Predizine + miglioramento dei metodi off-policy
Controllo MC
Nonostante MC non sia forse il metodo migliore nell'ambito degli off-policy, l'algoritmo cmq esiste, ne riporto lo pseudo codice sotto:
Questo algoritmo nel 2019 ancora non era stato ben esplorato, per cui per in questo corso non verrà approfondito.
Controllo TD
Quando si lavora con i metodi on-policy, viene utilizzata la stessa policy per esplorare gli stati e la si faceva migliorare e tende ad essere la policy ottimale. Si era poi deciso che per mantere una policy che sia in grado, da un lato di migliorare in maniera greedy e che nel contempo possa anche eplorare, di utilizzare le epsilon-greedy ovvero che facesse anche dell'esplorazione mentre migliora.
A questo punto separiamo le due policy, ovvero scegliamo una poloicy che esplora e usiamo l'esperienza fatta con questa per aggiornare un'altra policy, che è quella che piano piano diventa migliore e che a questo punto può essere totalmente greedy.
Il rapporto tra le due policy si chiama "rapporto di verosimilianza". Quando il rapporto tra i due è grande (pi/u)
Controllo Q-learning
I Q-learning sono una famiglia di algoritmi, dove l'azione nel target la scelgo con la policy pi di improvement.
che migliorata si può scrivere:
dove la policy pi è scelta come max di Q ovvero in maniera greedy.
Ippotizziamo ora questo esercizio, ovvero un mondo griglia con un burrone come sotto riportato:
Vogliamo applicare l'algoritmo Sarsa e l'algoritmo Q-Learning. Sarsa è epsilo-greedy mentre Q-Learning è greedy. Quanto emerge viene riportato sotto:
ovvero che Sarsa (blu) trova un percorso sub-ottimale, questo perchè essenso epsilong-greedy, tende a "rischiare" di meno e quindi sbagliare di meno. Mentre invece Q-learning è si ottimale, ma tende a rischiare di più. Q-Learning è quindi meglio? Dipende, se abbiamo a che fare con delle simultazioni, allora è sicuramente meglio, se invece abbiamo a che fare con il mondo reale dove i rischi sono reali allora è meglio scegliere una soluzione più "safe" come quella di Sarsa.
Se quindi misuro la somma delle ricompense il Q-learning ne riceve meno in quanto appunto rischia di più in quanto, nell'esempio tende a cadere maggiormente nel burrone. (vedi gradico sotto riportato)
Miglioramento della policy target pi Q-Learning (detto Sarsa Atteso o Expeted)
Target Q-Learning (predizione ovvero fissato pi) -> R + gamma*Q(S',A') dove A' è campionata di pi di S' che si scrive (A=pi(.|S')
ovvero:
questo algoritmo migliora il Sarsa On-policy e il Q-Learning Off-policy.
Questo è un metodo che stima il modello, lo impara e lo usa man mano che lo imparano, sono detti "model based".