Machine learning
- Introduzione
- Reti neurali
- Retropropagazione (backpropagation)
- Apprendimento supervisionato
- Apprendimento per rinforzo (corso uni)
- Reinforcement Learing (beginner)
Introduzione
Tipologie di ML
Esistono diversi tipi di algoritmi di ML, i principali sono:
- Supervised learning
- Unsupervised learning
- Reinforcement learning
Attualmente il più utilizzato è il primo.
Differenze tra supervised e unsupervided learning
Supervised learning (SL)
Nel SL vegono forniti all'algoritmo gli input e gli output e sulla base di questi viene creato un modello che generi un “match” tra i due. In generale all'algorirmo vengono fornite (nella fase di trainign) gli output relativi ai corrispondenti input.
Unsupervised learning (UL)
In questa modalità invece andremo a dire all'algorimo solo informazioni a reltivo al problema e NON alla soluzione. (diversamente da quanto accade con SL)
Un esempio potrebbe dare in pasto all'algoritmo i prezzi degli immobili e lasciare che l'algoritmo trovi le caratteristiche migliori che aiutino a prevedere il prezzo in futuro. L'algorimo andrà a ricercare dei pattern nei dati che abbiano delle connessioni con il prezzo.
Reinforcement learning (RL)
E' una modalità di allenamento della AI in modo che impari SOLO sulla base dell'esperienza fatta nelle varie simulaizoni.
Tipologie di classificazione del SL
Ci sono 2 tipologie, regressione lineare e classificazione
ANNOTAZIONE:
- tutti i valori da dare in pasto all'algoritmo sono detti “trainig set”
- gli input vengono spesso indicati come “feature” o X
- gli output vengono indicati come “labels” o “target” o y
- (x,y) invece per indicare il singolo valore di training
- per indicare lo iesimo elemento del training set utilizzare (x (elavato alla i), y (elevato alla i)) dove la i è la iesima riga del training set
Reti neurali
Le reti neurali (NN) o “multilayer perceptron” sono divise in layers ciascun layer è compostto da “neuroni".
I layers possono essere: 1) input, 2) hidden e 3) output. L'input layer può essere considerato come “hidden”.
Ciascun neurone del layer possiene gli input (o features) e un un output.
L'inferenza di una rete neurale consiste nel ricavare i valori del modello e applicarli alla propria rete
per riprodurre un comportamento. (per valori intendo l'insieme dei w e dell b)
La somma di questi output è anche detta “activations”.
In generale ciascun layer si occupa di “riconoscere” o estrarra specifiche caratteristiche del dataset, nel
caso di immagini di volti, per esempio, il primo layer riconoscere solo righe orizzonati/verticali, il secondo
parti del viso e il terzo un viso completo. (è solo un esempio ovviamente)
per es:
ciascun neurone del layer utilizzata una funzione di attivazione, come per es. la regressione logistica, il cui
output, è il valore di attivazione che diventa l'input del layer successivo:
nel secondo layer infatti il vettore di parametri in input vengono dati in pasto alla funzione di regressione logistica del layer:
l'output del l'ultimo layer non è più un vettore ma uno scalare (quindi un numero semplice) almeno in questo esempio
al quale viene applicato una soglio per determinare l'output true o false. (è giusto è un esempio, vedi immagine sotto)
'attivazione di un layer si basa applicando la funzione di attivazione (activation function) che nel caso
specifico è la sigmoid (ma in realtà che ne sono altre migliori) L'output della funzione di attivazione
è un vettore di valori che diventa l'input del layer successivo.
Di seguita vengono rappresentati i passaggi per l'elaborazione delle funzioni di attivazioni declinate sui vari layer:
Foward propagation
Quando i valori di attivazioni vanno dall'input layer, passando per l'hidden e terminando nell'output
layer seguendo esattamente questo schema, allora parliamo di “forward propagation”. (da sinistra verso destra)
TensorFlow
I framework maggiormente utilizzati sono TF e PyTorch.
Per ora verrà utilizzato TF con layer “densi".
Differenze di rappresentazione dei dati tra Numpy e TF
quando passo i dati a TF, es come input ad un Dense layer, TF converte la matrice
di valori np in un “tensore” che nella pratica è un np “wrappato” per esigenze computazionali e di architettura.
E' possibile convertire un tensore un np applicando il medodo .numpy del tensore che rappresenta il dato.
Di seguito viene rappresentata una tipica rete neurale di tipo “forward propagation” con
due layers di 3 e 1 neurone.
COMPILE:
Nella definizione di compile tra i vari paramtri viene impostato il totale delle epoche: es: 40
questo significa che ad ogni epica viene elaborato l'intero dataset. Ogni epoca è suddivisa
in batch dove in TF il numero massimo di batch per epoca è 32.
Quindi per es. se il dataset è fatto di 5000 records (dove ogni record ha N feautues, ma questo non conta adess)
il numero di batch per epoca sarà 5000/32 ovvero 157. es.
.
.
Epoch 39/40
157/157 [==============================] - 0s 2ms/step - loss: 0.0312
Epoch 40/40
157/157 [==============================] - 0s 2ms/step - loss: 0.0294
Vettorizzazione
La vettorizzazione corrispoonde alla moltiplacazione delle matrici
Supponendo di avere M1 e M2 per moltiplicare bisogna:
1) fare trasposta di M1
2) moltiplicare la riga 1 per la colonna 1 e via così...
NB:
1) il requisito è che la matrice trasposta M1 per la matrice M2 abbiamo il numero di
colonne di M1 uguale al numero di righe di M2
2) inoltre la matrice risultante avrà il numero di righe di M1 trasposta e il numero di colonne di M2
NB2: per fare la trasposta bisogna convertire la collanna (es. 1) nella riga 1.
vedi esempio sotto riportato.
che si converte in:
per effettuare la trasposta di in numpy basta chiare il metodo .T dell'oggetto matrice di np.
che nel codice si traduce:
di seguito un esempio di rete nurale sequenziale di 25 neuroni L1, 15 neuroni L2 e 1 neurone L3
con TF è possibile visualizzare il dettaglio del modello, da notare il numero di parametri
che corrisponde - per ciascun layer - alle w + le b. Per esempio in primo layer che è composto
da 15 neuroni il cui input è un array di 400 valori (sono i 20x20 pixel dell'immagine)
avrà un totale di 10025 parametri dato da: 400x25 -> w + 25 -> b
nel caso specifico il modello predice la probabilità che il numero si un uno (1)
prediction = model.predict(X[0].reshape(1,400)) # a zero
print(f" predicting a zero: {prediction}")
prediction = model.predict(X[500].reshape(1,400)) # a one
print(f" predicting a one: {prediction}")
predicting a zero: [[0.0191125]]
predicting a one: [[0.9788295]]
The output of the model is interpreted as a probability. In the first example above, the input is a zero. The model predicts the probability that the input is a one is nearly zero. In the second example, the input is a one. The model predicts the probability that the input is a one is nearly one. As in the case of logistic regression, the probability is compared to a threshold to make a final prediction.
Training
Paragonando i concentti appresi nella prima settimana, costo della funzione, discesa del gradiente
con quelli appresi nella seconda settimana, rete neuale , modello, fit possiamo riassumere che:
nel modello la funzione di costo è esplicatata dal parametro “loss” e corrisponde alla funzione alla funziona di costo visto
come media dei valori “loss” (Cost)
mentre il metodo fot non è altro che il calcolo della discesa del gradiente nella regressione logistica.
Funzioni di attivazione
PERCHE' UTILIZZARE LE FUNZIONI DI ATTIVAZIONE?
L'uso delle regressione lineare negli hidden layer non serve in quanto basta
calcolare la regressione lineare a livello di funzione matematica. (vedi settimana 1)
E in questo caso il modello può essere utulizzato solo per modelli molto semplici.
FUNZIONI DI ATTIVAZIONE PER L'OUTPUT LAYER
Ci sono vari tipi di “funziona di attivazione” ciascuna delle quali
una sua peculiarità a seconda del fenomeno che si vuole modellare.
Per problemi legati alla classificazione binaria dove l'output è 0/1 or Tryue/False
la funzione Sigmoid può andar bene. Perchè il modello calcola la probabilità
di ottenere un output uguale a 1.
Nel caso in cui invece si deve predirre un output che può assumere più valori
è meglio utilizzare il tipo “linear regression function”. (per es. nel mercato dei titoli)
In questo caso l'output può quindi assumere sia valori positivi che negativi.
Nel caso in cui invece i valori possono essere varibili ma solo positivi, come per
esempio il prezzo delle case, allora è meglio utilizzare la funzione “ReLU”
FUNZIONE DI ATTIVAZIONE PER GLI HIDDEN LAYER:
in generale per gli hidden è meglio utilzzare “ReLU”
Classificazione multiclasse
Come evidenziato negli esempi precedenti, nel caso in cui si voglio classificare un
evento binario, es. true/false utilizzo la funziona di attivazione Sigmoid.
2)
Nel caso di valori lineari, come l'andamento dei prezzi delle case, utilizzo la regressione
lineare seplice. (permane comunque un unico output che puù assumere diversi valori)
3)
Nel caso invece in cui ho più valori in output da prevedere, utilizzo la classificazione multiclasse.
In questo caso si utilizza la funzione “SoftMax” che nella pratica rappresente la generalizzazione
della regressione logistica.
In questo caso ogni attivare del layer di output assume la probabilità che lo isesimo valore si verifichi.
La probabilità vare tra zero e uno, ovvero da dallo zero al cento per cento.
La formula per il caloclo della funzione Softmax è:
che generalizzando si può scrivere come:
Ottimizzazione avanzata
La discesa del gradiente è un ottimo algoritmo che utilizza
piccoli passi per arrivare al minimo del costo della funzione.
Esiste però un algorirmo più veloce che utilizza degli step “maggiorati”
che fanno in modo di arrivare al minimo più velocemente. Il nome
di questo algoritmo è “Adam”.
Adam sta per “Adaptive Moment Estimation” che nella pratica fa si
che il passo “learning rate” sia variabile ovvero possa variare da piccolo a grande
in maniera ottimale.
Layer "convoluzionale"
Oltre al layer fato di neuroni “densi” esite il layer fatto di neuroni “convoluzionari” che
a differenze dei densi, ricevano solo alcune attivazioni del layer precedente.
es.
Bias validation
Nell'ambuito della fase di training del modello, per valutare l'efficacia utilizziamo
la midura dell'errore relativamente a:
1) il trainset, in genere il 60% dei dati da dare in pasto al modell
2) il cross validation set, il 20% dei dati
3) il test set, restante 20 %
L'errore relativo al trainset è detto “bias error" che se è alto significa che il modello
è stato trainito male e quindi bisogna cambiarlo, se è basso puà essere che sia
in overfitting oppure che vada effettivamente bene
L'errore relativo al cross validation indica quanto si discosta il modello utilizzando
dei dati che non sono stati utilizzati nella fase di fitting.
La baseling è il riferimento preso da altri modelli diversi da quello che si sta elaborando.
Si possono quindi verificare i seguenti casi:
Per migliorare il training del modello ci sono alcuni accorgimenti da seguire, di seguito:
Nel grafico sottoriportato si può vedere il caso in cui la differenza tra il modello e il riferimento si discosta di molto in peggio, in questo
caso all'aumentare del numero del trainset la curva tende ad appiattirsi e non miglioare. Il modello quindi ma ba bene
Nel caso invece in qui il trainset performi meglio del riferimento, può essere che all'aumentare dei samples l'errore
di cross validation diminuisca e arriva al livello del riferimento.
In generale trovare bisogna cercare di diminuire i valori di bias e variance attraverso un processo di affinamento
come sotto rappresentato:
Retropropagazione (backpropagation)
La backpropagation è una della pietre miliari del Machine Learning, si applica principalmente alla rete neurale. ( diamo per scontato si sappia cosi sia una rete neurale a livello base)
Per spigare passo passo la BP (backpropagation) utilizzeremo un semplice rete neurale sotto riportata:
TODO
Apprendimento supervisionato
Nel Supervised Learing (SL) vengono passati all'algoritmo gli input - detti anche “features”, e gli output corrispondenti agli input, detti anche “targets” o "labels".
L'algoritmo produce quindi una funzione (f) (f minuscola) , in input alla funzione vengono passate le features detta anche x (x minuscola) e ritorna le y^ (y cappello) che rappresentano i valori predetti dalla funzione.
NB La funzione f è detta anche “modello”.
La differenza tra y e y^ è che la y è il training set di features (quindi i valori noti da passare durante la fase di training) metre i valori y^ sono i valori stimati che il modello prevede in base agli input. (post fase di traing)
Regressione lineare
Tramite la regressione lineare univariata, viene determinato matematicamente l'output della funzione dato l'input, o se vogliamo dirla in altro modo, viene calcolata la Y in funzione della X. (tipicamente determinato la funzione che meglio fitta di valori X e Y)
La RL serve per determinare i valori della funzione che meglio soddisfano l'andamento di un fenomeno relativo ai valori appartenenti all'insieme delle fetures/labels (x,y)
La funzione si può rappresentare come y = b + wx dove b è “intercetta” (ovvero il delta y rispetto allo zero detto anche “bias” in inglese ) mentre la w è il “coefficiente angolare. (ovvero l'inclibazione della retta detto anche ”weight" in inglese o “slope” ovvero pendenza nel caso della funzione)
Nel Machine Learning (ML) i parametri “w” e “b” sono detti anche coefficienti o pesi.
Costo della funzione
La Cost Function (CF) nella pratica confronta il valore “predetto” y^ e il valore di training y, nella pratica è una differenza tra i due valori che definiamo come “errore”, ponendo il delta al quadrato, ovvero:
Sommatoria di (y^ - y)^2 per tutti i valori “m” del training set; diviso per “m” ovvero, viene ritornato la media degli errori -> questo si chiama “metodo dei minimi quadrati”
L'intento è quindi quello di trovare il valore minimo della funzione di costo.
Si tratta quindi di trovare la funzione che minimizza l'errore.
Nell'immagine sotto riportata a sx vengono visualizzate le funzioni ottenibili al variare del permarametro “w”
NB: per semplicità l'esempio pone b= 0 per rendere il grafico più facilemente interpretabile perchè in questo modo il gradico è 2D, se considerassimo anche
il valore b, allora il grafico sarebbe 3D e quindi un pò più difficile da leggere. (vedi es. grafico 3D riportato in pagina)
Si può notare che nella parte sx al varia della funzione si ottengono diversi valori J (ovvero errore) che, se rappresenti graficamente disegnano una curva
dove l'errore minimo si trova quando, per es. nel caso specifico, w vale 1. (grafico a DX)
Il grafico a DX disegna sulle ordinate (y) l'errore mentre sulle ascisse (x) il valore w ottenuti dall'applicazione del metodo
dei minimi quadrati. (vedi grafico a SX)
Nel caso in cui considerassimo anche il parametro “b", il grafico del cost function sarebbe renderezzito in 3D, come sotto rappresentato.
Considerazioni finali
Per determinare il “costo della funzione minimo” o l'errore minimo bisogna determinare i parametri “w” e “b” che avvicinano la funzione al set di dati.
Per determinare questi parametri in maniera algoritmica viene utilizzata la tecnica matematica denominata “gradiant descent” o “discesa del gradiente” analizzata nel paragrafo successivo.
Discesa del gradiente
La discesa del gradiente (GD) è un modo sistematico per determinare i parametri “w” e “b” in modo che minimizzino
il "costo della funzione" (l'errore della funzione)
Ricordo che stiamo parlando della funzione i cui coefficienti (w e b) contribuiscono a determinare
i valori che più si avvicinano al set di dati passati in input (features e labels)
Quindi J(w,b) -> costo della funzione (ovvero la sommatoria dei delta dati da labels - labels calcolate con i coifficienti w)
Tramite questo metodo si procede per “piccoli passi” al fine di trovarel l'errore minimo J(x,b), nota che
possono esistere più minimi (detti anche “minimi locali”) che dipendono dal valore di partenza che in genere è randomico.
Nella pratica si tratta di looppare i valori “w” e "b" calcolati ad ogni iterazione del ciclo. (vedi immagine sopra)
Il valore di w è quindi settato a = “w” meno un parametro “alpha” (detto anche learning rate, valore piccolo compreso tra 0 e 1, es. 0,001) moltiplicato
per la derivata del costo della funzione J(w,b).
Stessa cosa per il parametro b.
Il valore di “learing rate” (LR) è indica la grandezza del “passo”, ovvero la velocità con la quale saliamo i discendiamo il grafico
del costo della funzione.
Attenzione che andare veloce può causare un “salto” eccessivo e farci perdere il punto di minimo.
Sopra viene indicato il calcolo della derivata parziale rispetto al valore “w”. Vengono rappresentati due casi, il primo
dove viene preso a caso un valore “w” a DX dal minimo; In questo caso la derivata parziele ritornerà un numero positivo
in quanto, la derivata indica l'inclinazione della tangente passante per il punto scelto sulla curva avente per coordinate (w1,j(w1))
e in questo caso indica che la tangente è ascendente.
La derivata del costo della funzone indica se la funzione è a un minimo (anche locale) oppure se si trova in discesa o in salita. In pratica
restituisce la pendenza (o la direzione) del punto tangente alla funzione di costo nelle coordinate indicate.
Ora il nuovo “w” viene calcolato sotrraendo il " LR x lla derivata" al valore “w” , essendo positivo, diminuirà il valore finare di “w”.
Stessa cosa, ma invertita di segno in quanto il valore di w preso a SX del minimo è discendete. Quindi, il valore della derivato
del costo della funzione viene negato in quanto la formula sottrae sempre il valore della derivta parziale del costo di “w” e di “b”.
Idem per la variabile “b” fino a quando i valori convergono intorno al minimo della funzione.
Learning rate
Il valore di “learning rate” (LR) nella pratica serve per fare “lo step” nella direzione del minimo in cui valore è dato dal vosto della funzione.
LR però non può essere un valore troppo piccolo in quanto rallenterebbe in maniera importante la determinazione del minimo e, non può
essere nemmeno troppo grande in quanto rischia di far saltare il punto di minimo, sia esso locale che globale.
Per questo motivo il modo migliore per settare il parametro alpha (detto anche LR) è gestire dinamicamente il valore da algoritmo in modo
che sia un valore relativamente grande se la pendenza (slope) dato dalla derivata nel punto della funzione di costo è elevato, piccolo se lo
slope tende allo zero in quanto significa che siamo prossimi al minimo.
Di seguito viene mostrato il calcolo delle deritavate parziali rispetto a “w” e rispetto a “b" per determinare il minumo del costo della funzione.
NOTA di calcolo, si tratta di applicare il teorema della derivata della funzione composta (detta anche "chain rule) rispetto a w e rispetto a b ovvero:
che applicando il tutto alla funzione di costo si ottiene:
Quindi l'algoritmo di calcolo della discesa del gradiente si calcola come:
Conclusione
In conclusione, la regressione lineare consente di determinare il valore minimo relativo al costo della funzione.
Il costo della funzione ritorna la sommatoria degli scostamenti tra la funzione (ad una o più variabili) e l'insieme dei valori (campioni)
labels-features al variare dei coefficiente “w” e “b”.
Al variare di questi coefficienti si genera un insieme di valori dove ciascun valore è un totale che se rappresentato
graficamente, disegna un grafico in 2D (se varia solo un valore) in 3D se variano sia “w” che “b”, del quale dobbiamo trovare
il minimo per identificare la funzione che minimizza l'errore.
Per trovare l'errore minimo si utilizza il metodo della discesa del gradiende, che consente tramite l'utilizzo delle derivate parziali
nel punto iesimo, di avvicinarsi progressivamente al “minimo locale” oppure al “minimo assoluto” avanzando tramite un passo definito “learing rate”.
Di seguito un esempio di come al variare dell'intercetta e del coefficiente angolare, andando con passo (LR) la funzione
giunge al suo costo minimo.
Regressione lineare multipla
PREMESSA:
f(w,b) = modello
J(wb) = costo della funzione -> f (w,b) - y -> dove y sono le label
DISCESA DEL GRADIENTE = d/dw J(w,b) in sistema con d/db J(wb)
Nella regressione lineare univariata (RLS) abbiamo solo una "feature" e una corrispettiva “label”, per es. metri di un appartemento e corrispettivo prezzo.
Nel caso della regressione lineare multipla (RLM) invece, abbiamo più features a fronte di una label, per es. oltre ai metri quadrati dell'appartemento
abbiamo anche il numero di stanze, l'età dell'immobile, piano, etc etc e ovviamente come label il prezzo.
NB: la RLM non è la regressione lineare multivariata, che non conosco.
Il modello che era stato definito per la regressione lineare singola si basa sulla funzione f(x) = wx + b che in pratica definisce la funzione
(attraverso l'opportuno settaggio dei paramerti w e b tramite la discesa del gradiente) che meglio si accosta alle features/label definite per il training.
Nel caso invece della RLM, la formula diventa un polinomio del tipo (consideranto 4 features) f(x) = w1x1 + w2x2 + w3x3 + w4x4 + b
Dove x1,2,3,4 sono le features, mentre w1,2,3,4 sono i coeffienti angolari tutti potenzialmente diversi.
es:
che si può rappresentare anche:
Per risolvare questa equazione viene utilizzato il metodo della Vettorizzazione. (Vectorization)
La Vettorizzazione consente nella pratica di efettuare la moltiplicazione tra vettori/matrici utilizzando la libria numpy che sfrutta appino l'hardware della macchina.
Discesa del gradiente
Il GD a più variabili è simile a quello univariato con la differenza che al posto di un solo “w” e una sola “b” c'è un vettore di w
Il calcolo è simile se non per il fatto che bisogna iterare per il numero di features
Nella pratica la regressione lineare multipla si calcola in 2 marco step:
0) date le features e le labels di esempio:
X_train = np.array([[2104, 5, 1, 45],
[1416, 3, 2, 40],
[852, 2, 1, 35]])
matrice di 3 righe di traing con 4 colonne di features per ogni riga
e
y_train = np.array([460, 232, 178])
una riga di labels
e
dati dei valorei a caso di “w” e “b”
b_init = 785.1811367994083
w_init = np.array([ 0.39133535, 18.75376741, -53.36032453, -26.42131618])
1) calcolo della funzione di costo su variabili multiple, come sotto riportato
Il metodo “compute_cost” serve per calcolare il costo della funzione per i valore w e b passati per una SOLA iterazione.
Sarà poi la fase successiva a variare i w e b richiamando poi la funzione di costo per determinare il costo totale per poi ritare “w” e “b” di conseguenza
2) Calcolo della discesa del gradiente con variabili multiple
applicando la derivata del “calcolo della funzione di costo” loopando fino a che i valore “w” e “b” minimizzano il costo
NB: ricordo che si applica il metodo della "derivata della funzione composta" accennato nella sezione “GRADENT DESCENT” relativa al paragrafo
della regressione lineare univariate.
Nella pratica il calcolo delle derivate parziali in “w” e “b” si traduce in:
che viene richiamata in un loop di N iterazioni, ovvero:
In conclusione questo è la discesa del gradiente, purtroppo i risultati ottenuti non sono particolarmente brillanti, dopo
verrà illustrato come migliorare l'algoritmo.
Scaling delle features e dei parametri
Nel caso in cui ci siano più features (come nella regressione lineare multipla) è importante scalare i valori delle diverse tipologie di parametri in input.
Es. se abbiamo due features come i metri quadrati e il numero di stanze di un appartmento, è bene riportare entrambi gli insiemi di valori
in un range compreso tra -1 e 1.
Il motivo è dettato dal fatto che in questo modo la regressione lineare trova più facilmente (velocemente) il suo minimo.
(vedi i grafici sotto riportati che indicano il minimo dei costi nella parte SX)
SCALING:
Le features e le label vanno quindi “normalizzati” scalandoli principalmente in questi modi:
1) dividere tutti i valori per il massimo
2) “centrando” i valori intorno allo zero applicando la formula (valori-valore medio)/(valore max - valore min)
di seguito un esempio:
un metodo ottimale per normalizzare i dati è detto Z-SCORE che riporto di seguito:
Z-SCORE
Questo metodo nella pratica va a “centrare” le features e le labels inforno allo zero. In questo modo il calcolo della regressione
lineare risulterà più veloce e più accurato nella ricerca del valore minimo relativo al costo della funzione.
DEVIAZIONE STANDARD (o scarto quadratico medio)
La DS rappresenza rappresenta la distanza dei valori di una serie rispetto alla media e si calcaola come:
1) calcolare la media dei valori -> media semplice
2) calcare la varianza dei valori -> è la differenza tra il singolo valore e la media al quadrato il tutto diveso per il totale dei campioni
3) calcolare la daviazione -> è la radice quadrata della varianza
implementazione dell'algoritmo di ZScore
il cui output nell'esempio:
e adesso proviamo a predirre i valori.
Regressione polinomiale
Nella regressione lineare polinomiale la funzone di costo ragione per curve e non per linee rette come
invece accade della regressione lineare (singola o multipla)
Per ottenere questo risultato vengono utilizzate dei confficienti quadrati o cububici o valori esponenziali > di 3.
oppure utilizzare, al contrario, la radice quadrata della feature.
es:
che poi viene dettaglio nel capitolo relativo all'overfitting/underfitting
Apprendimento per rinforzo (corso uni)
corso universitario tenuto da Maurizio Parton
https://www.youtube.com/playlist?list=PLMee1hSjLKdAL16E-7EzqHXsGOgzo8iro
risorse python:
https://github.com/dennybritz/reinforcement-learning
corso avanzato deep-mind:
https://www.youtube.com/@googledeepmind/courses
Introduzione alla probabilità
Prima di procedere con lo studio del RL facciamo una breve introsuzione al calcolo probabilitico. (in particolare la probabilità elementare su insiemi finiti)
Lezione https://www.youtube.com/watch?v=o9Rc1pCYaHo&list=PLMee1hSjLKdAL16E-7EzqHXsGOgzo8iro&index=23
Cosa significa aleatorio? (sinonimo di casuale o stocastico)
E' un osservazione di un fenomeno il cui risultato non è determinabile a priori. (es. le previsioni del tempo, o il valore di un titolo azionario, o il lancio di un dado)
Pur non essendo l'esito sicuro dell'informazione si può comunque estrapolare, per es. nel lancio del classico dado otterremo un valore intero da 1 a 6 non 3,8 in virtù della tipologia del fenomeno.
La descrizione matematica che permette di affrontare questa tipologia di problemi si chiama probabilità.
Spazio campionario
Nell'ambito di un esperimento questo "spazio campionario", rappresntato dal simbolo Ω (omega), contiene tutti gli esiti possibili dell'evento che stiamo esaminando. Es. evento lancio di un dado, lo spazio compionario conterrà tutti gli esiti possibili del lancio del dato, quindi l'insime dei numeri possibili da 1 a 6. -> Ω = {1,2,3,4,5,6)
Non sempre però lo spazio campionario è un numero finito, es. il numero di accessi ad un sito web, in questo caso è l'insieme di tutti i numeri naturali, es. Ω = N0 (dove N0 è l'insieme dei numeri naturali)
Se il numero non è discreto nel caso in cui la misurazione è contina allora l'intervallo è omega comprende tutti i valori da zero a infinito, ovvero: Ω = [0, +∞)
Quindi esistono tre tiologie di spazi campionari:
- discreto finito
- discreto inifinito
- continuo
Modello probabilistico
Rappresenta la probabilità (o fiducia) che si verifichino i valori dello spazio campionario.
Es. quale è la probabilità che il numero ottenuto con il dado sia pari. (2,4,6) o la probabilità che il numero di accessi al sito web sia minore di 100.
Il RL si occupa dello spazio campionario finito. (caso 1)
Definizione: la probabilità su tutto lo spazio campionario è sempre 1. (es, quale è la probabilità che lanciando un dado esca 1 o 2 o 3 o 4 o 5 o 6 ? è il 100% ovvero 1) P(Ω) = 1. Invece la probabilità dell'insieme vuoto è zero.
Definizione: I sottoinsimi dello spazio campionario sono detti eventi. es. nel dato il sottoinsieme (evento) 1 potrebbe essere P {1,2} un altro sottoinsieme potrebbe essere P{3,4,5) e così via. Vien da se che Ω contiene tutti gli eventi possibili, NB: tutto questo vale quando gli eventi (sottoinsiemi) sono disgiunti, ovvero non si intersecano).
Suggerimento, pensiamo alla probabilità di un insieme come all'area di un cerchio, nel caso di insiemi disgiunti la probabilità dei due sottoinsiemi è semplicemente la somma, se invece i due sottoinsiemi si intersecano allora è la somma delle due probabilità meno la probabilità della loro intersezione.
Densità uniforme
Data una probabilità P su uno spazio finito e numerabile Ω, possiamo associare a P una funzione p detta densità, definita su omega valori [0,1]. Quindi la densità è definita SOLO sugli elementi di omega.
La probabilità dell'insieme che contiene il singolo elemento è funzione del singolo elemento. es. nel lancio del dadi la probabilità dell'insieme P({1,2,3}) è la somma delle probabilità dei singoli elementi che indicheremo con p minuscola ovvero: P({1,2,3})= p{(1)} +p{(2) }+ p{(3)}
ATTENZIONE: con P maiuscola ci indica la probabilità mentre con la p minuscola si indica la funzione che resituisce la probabilità. Per es. la densità definita sullo spazio campionario del lancio del dado, P: {Ω} -> [0,1] mentre la densità di ogni elemento di Ω è p(1) = 1/6... fino a p(6)= 1/6
Altro esempio
Esperimento Bernulliano
un esperimento bernulliano è una variabile che può indicare successo o non successo, è una varibile booleana. La variabile che indica la proabilità di successo è P mentre quella che indica l'insuccesso è (1-P), insieme omega è quindi Ω = {successo, insuccesso} o Ω = {1,0}
Esempio: qual'è la probabilità di ottenere un successo alla K-esima volta che facciamo un esperimento. (es. alla 10a volta)
ciò significa che per i primi 9 lanci non deve verificarsi il successo (1-P) e al decimo deve valere P. Per i primi 9 lanci le probabiltià si devono moltiplicare (1-P)*(1-P)*(1-P)*(1-P)*(1-P)*(1-P)*(1-P)*(1-P)*(1-P)*P = exp((1-P),K-1)*P
Densità non uniforme a preferenze (SoftMax)
Esistono casi in cui gli elementi dello spazio capionario hanno delle preferenze (o dei pesi) che ne alternano in qualche modo le probabilità.
NB: L'intento è quello di trasformare queste preferenze (o pesi) in probabilità. Però ci sono dei pesi negativi.
Nel caso in cui questi "pesi" abbiano valori negativi, come si calcola il peso in termini probabiliststici di ciascuno elemento di omega rispetto agli altri?
Il caso viene illustrato nell'immagine sotto riportata dove vediamo ciascuno preferenza H definita per ciascuna delle 6 facce delle dado. Si può notare che esistono delle preferenze negative che se dovessimo calcolare semplicemente come peso della singola preferenza fratto sommatoria di tutti i pesi, ne risulterebbe una probabilità negativa.
Quindi per es. se volessimo calcolare la probabilità di P(H1) sarebbe -> 100 / (somma di tutti i pesi) . Però non funzionerebbe in quanto abbiamo dei pesi negativi, e nel caso per es. di P(H3) verrebbe una probabilità negativa, il che sarebbe sbagliato.
Per nornalizzare questi valori si applica semplicemente la funzione esponenete per ciascuna preferenza che rende tutti i numeri > 0. (anche con esponente negativo i valori sono sempre > 0) quindi diventa. (non considerare la variabile beta)
Q quindi diventa:
Questa tecnica per normalizzare i pesi è detta softmax. E' importante perchè la somma delle probabilità di tutti i valori "pesati" da 1.
Nel caso di insiemi discreti non finiti si applicata la formula Poisson. (che in questo momento non ci interessa)
Contare le combinazioni di eventi complessi
Supponiamo di poter filtrare un insieme per determinare caratteristiche che si sommano in successione.
Utilizziamo degli esempi:
1) voglio determinare le carte pari di cuori e picche da un mazzo di carte di poker:
Applico la regola delle caratteristiche che si sommano,
In questo abbiamo 2 caratteristiche, ovvero:
caratteristica 1) le carte pari ->5 su 13
caratteristica 2) i semi di carte -> 2 su 4
quindi sommiamo la caratteristica 1 e 2 che matematicamente significa moltiplicare, ovvero: 5*2 = 10
2) sempre la mazzo di poker voglio trovare tutte le combinazioni di full possibili. (3 carte dello stesso valore + 2 dello stesso, esclusi vicendevolmente es. 3 carte di assi + 2 carte di jack)
In questo abbiamo 4 caratteristiche, ovvero:
caratteristica 1) 3 carte uguali -> 13
caratteristica 2) 2 carte uguali (in quanto vado ad escludere il tris) -> 12 (in quanto non possono esistere 5 carte con lo stesso valore)
caratteristica 3) 3 carte che hanno 3 semi su 4 -> 4 presi in combinazione di 3 (combinazioni semplici senza dipetizione C(4,3)
caratteristica 4) 2 carte che hanno 2 semi su 4-> 4 presi in combinazione semplice senza ripetizione C(4,2)
= 13*C(4,3)*12*C(4,2) = 3744
Calcolo combinatorio
Di seguito un breve ripasso del calcolo combinatorio
Disposizioni semplici
Le disposizioni prese da un insieme di N elementi in K modi (es. da un insieme di 10 numeri (N) presi a 2 (K) ) sono un sottoinsieme di numeri ordinati, dove l'ordine del numero conta, allora la formula diventa N! / ( N-K)!
Combinazioni
Se invece l'ordine dei non conta allora il numero di casi dimunuisce quindi la formula diventa N! / K! * (N-K)!
Probabilità condizionata
Premessa: l'informazione cambia le probabilità.
Premessa bis: La proababilità ovviamente si calcola come casi favorevoli fratto casi possibili.
Es, qual'è la probabilità che lanciando un dado esca il numero sei? ovviamente 1/6. Supponiamo invece che dopo aver lanciato il dado qualcuno ci dica che è uscito un numero pari, ora come cambia la probabilità? in questo caso lo spazio campionario (omega) cambia e passa da sei numeri a tre tutti pari, a questo punto la proabilità diventa 1/3.
Sia un evento A condizionato a B -> P (A | B) il calcolo diventa P(A|B) = P(A ∩ B) / P (B)
Indipendenza di eventi
Premessa: In genere sapere il verificarsi di un certo evento ci da informazioni sulla probabibilità di un altro evento.
Ci sono però casi che l'informazione non modifica che la probabilità che modifichi l'evento.
Quindi P(A|B) = P(A) significa che se la probabilità di A condizionata all'evento B è invariata allora i due eventi sono indipendenti.
L'intersezione dei due eventi rende la probabilità una funzione moltiplicazione, ovvero: P(A ∩ B) = P(A) * P(B)
Sessione 1
Nell'apprendimento per rinforzo (d'ora in poi verrà indicato con RL) si basa sul processo decisionale di Markov aka MDP attrraverso un task di controllo dove un set di possibili stati e azioni ritornano un reward e una probabilità di passaggio ad uno stato all'altro. Il task nella pratica è un "compito" o una simulazione che per essere svolta (risolta) implica l'utilizzo dell'MDP.
NB: Il processo decisionale di Markov (MDP) asserisce che il passaggio allo stato successivo T+1, dipende esclusivamente dallo stato attuale T e non dagli stati precedenti. Quindi il processo NON ha memoria, in questo caso si dice che il processo è "Markoviano".
Tipologie di processi decisionali di Markov (MDP)
Esistono due tipologie di MPD, il processo a stati finiti e quello a stati infiniti.
Nel MDP finiti gli stati finiti hanno un numero finiti di stati definiti dall'ambiente, es. l'uscita da un labirinto di 5 caselle x 5. In questo caso abbiamo 25 stati e 4 azioni (su, giù, dx e sx)
Nel MDP a stati infiniti, invece, l'ambiente appunto può restituire infiniti stati a fronte di infinite azioni, pensiamo per es. il sistema di guida automatica di una macchina dove l'azione es. girare il volante, è un valore continuo così come la scelta della velocità dell'auto.
Episodi
MDP definisce anche degli "episodi" in particolare:
Nel MDP episodico un episodio termina a determinate condizioni. Es. nel gioco degli scacchi quando la giocare da scacco matto.
Nel MDP continuo, il processo non ha fine, semplicemente continua ad esistere all'infinito in quanto non esiste uno stato fine.
Traiettoria ed episodio
La traiettoria è il movimento che l'agente compie per muoversi da uno stato all'altro. La traiettoria è definita dal simbolo greco 𝜏 "tau". Un esempio può essere:
𝜏 = S0, A0, R1, S1,.A1, R2, S2, A2, R3, S3 che indica la partenza dallo stato zero, dove viene effettuata l'azione A0 che porta la reward R1 e il posizionamento nello stato S1, alla quale segue l'azione A1 e così via. L'ultimo stato della traiettoria sarà (nel caso specifico) S3.
La treittoria può essere finita o infinita, se è finita si chiama episodio è semplicemente una traiettoria che inizia in uno stato e finisce nello stato finale oltre quale non si torna indietro. es:
di cui deriva il concetto di storia, ovvero la somatoria delle osservazioni, ricompense e azioni fino all'azione finale.
Ricompensa vs Ritorno
La ricompensa (reward) viene restituita a fronte di un'azione, quindi per risolvere un task, dobbiamo massimizzare le ricompense ottenute. La ricompensa è quindi un risultato immediato. (Rt)
Invece il ritorno è la somma di tutte le ricompense ad un determinato momento nel tempo es: G(t) = R(t+1) + R(t+2) + ... R(T) finchè il task è stato completato.
Predizione, miglioramento e Controllo
La predizione significa calcolore il valore di una certa policy fissata, il miglioramento, come dice la parola serve per migliorare (anche solo di poco, non la miglioare in assoluto) la policy attuale, mentre il controllo serve per trovare la migliore di tutte.
Da qui il ciclo utile per trovare la policy migliore: pi(s) -> Vpi(s) -> pi'>= pi che inserire in un loop fino a quando converge. (teorema banach caccioppoli)
Fattore di sconto γ (gamma)
Il fattore di sconto è un incentivo per completare l'episodio nel miglior modo (più efficiente) possibile. Per ottenere questo la ricompensa dovrà essere moltiplicata per il fattore di sconto che diminuirà nel tempo all'aumentare delle azioni intraprese, rendendo le ricompense sempre più basse e quindi disincentivando le traiettorie lunghe.
Il fattore è un valore compreso tra zero e uno e viene elevato ad un esponente corrispondente dall'iesima azione fino alla fine dell'episodio.
Se γ (gamma) vale zero l'agente cercherà di prendere una ricompensa immediata, il che denota una strategia miope che non ottimizza l'apprendimento. Al contrario invece, un fattore γ gamma pari a uno, rende l'agente più "paziente" e quindi non prono ad ottimizzare gli step dell'episodio. In genere il fattore gamma viene settato a 0,99 che forza l'agente ad avere una ricompensa immediata ma allo stesso tempo lo forza ad avere una visione "a lungo termine".
In conclusione il fattore gamma indica all'agente quanto può valutare in maniera ottimali le azioni future.
NB: se il task è episodico allora è possibile utilizzare un fattore di sconto pari a 1, diversamente se il task è continuo (infinito senza stati assorbenti terminali) allora il tasso di sconto è meglio che sia <1.
Policy
La policy dell'agente è una funzione che prende in input uno stato e ritorna l'azione che va presa in quello stato. E' rappresenta dalla lettere greca pigreco π
La probabilità di eseguire un'azione (a) nello stato (s) si può rappresentare come:π(a|s)
L'azione che la policy sceglie nello stato (s) viene descritta dalla formula: π(s)
Dipende quindi dal contesto, in alcuni casi si uitilzza il primo π(a|S) in altri il secondo π(s).
La policy può essere di due tipi: stocastica o deterministica.
Si dice che la policy è deterministica quando viene scelta sempre la stessa azione in un determinato stato quindi stiamo parlando del caso π(S).
Si dice invece stocastica quando l'azione viene scelta sulla base delle probabilità es. : π(S) = [0.3, 0.2, 0.5] ovvero la probabilità di effettuare una azione nello stato S, è del 30% nel primo caso, 20% nel secondo e 50% nel terzo. Quindi siamo in presenza del caso π (a|S)
Quindi bisogna trovare la policy ottimale rappresentata come π* (pigreco - asterisco) che sceglie le azioni che massimizzano la somma dei fattori di sconto per le ricompense alla lunga.
La policy π è una distribuzione di probabilità che deciamo noi dato lo stato con la quale scegliamo le azioni e prendendo quindi una decisione, si differenzia dalla probabilità che NON decidiamo noi che si rappresenta con P che invece rappresenta il modello la cui prabobilità non possiamo modificare. (es. P(s',r|s,a) )
Il valore della policy V in genere indica la ricompensa totale media che si ottiene applicando la policy
Controllo Ottimale
Nel RL è fondamentale determinare la Policy Ottimale π* indispensabile per la gestione dell'ambiente. La griglia di centro (visibile in figura) è la rappresentazione del valore di ciascuno stato. (dove per stato si intende ogni casella della griglia) Per valore ottimale V* si intende il valore della policy ottimale, ovvero quello che si può ottenere facendo le azioni migliori possibili. Per migliore azione si intende determinare lo scopo, ovvero massimizzare le somma delle ricompense (dette ritorno) ottenibili con le azioni future.
La policy ottimale quindi, si ottiene valutando di volta in volta il valore ottimale. Le policy ottimali sono tante, anche su un unico stato, vedi per es. che nella casella in fondo a sx il cui valore è 14,4 ha due policy ottimali in quanto i valori ottimali in questo specifico caso sono due.
Pianificazione e Apprendimento
L'apprendimento nel RL si basa sulla pianificazione.
La pianficazione implica la conoscenza del modello associato all'ambiente, es. il lancio di un dado che implica che il valore medio detto anche ritorno medio dell'azione è 3,5 ovvero 1*1/6+2*1/6+3*1/6+4*1/6+5*1/6+6*1/6.
NB: il modello è l'ambiente e normalmente NON lo conosciamo.
L'apprendimento, è la fase successiva alla pianificazione e implica l'iterazione con l'ambiente e prevede il calcolo della media empirica ovvero la media dei valori ottenuti dall'iterazione con l'ambiente.
Quindi con la pianficazione e l'apprendimento, l'agente migliora la policy.
Entrambi guardano avanti nel futuro calcolando i valori cercando il miglioramento della policy.
Tipologie di algoritmi applicabili al RL
Di seguito viene rappresentata la tassonomia (categorizzazione) delle varie tipologie di algoritmi applicabili nell'ambito del RL.
Esplorazione vs Sfruttamento
E' l'eterno dilemma, ovvero provo sempre nuove soluzioni o sfrutto sempre quelle che già conosco. Entrambi vanno utilizzati per "allenare" la rete rete neurale. (vedremo più avanti)
Processi decisionali di Markov (MDP)
I processi decisionali di Markov si basano sulla gestione degli stati. Gli stati vengono rappresentati come dei cerchi dove all'interno è presente una lettera che lo rappresenta. Il pallino nero invece è l'azione.
Nello schema sotto rappresentato vediamo che, partendo dallo stato "u", la risposta dell'ambiente a fronte dell'azione "a" di tipo probabilistico (aleatoria) e quindi non deterministico, è di 0,7 con un reward di +3 che ci porta di v, oppure 0,3 con reward -1 che ci porta in "w". Se invece a fronte di una azione (pallino) ci fosse stato una unica determinazone della riposta dello stato T+1 anzichè due o piu, allora la risposta sarebbe stata derministica.
Es. leggendo la risposta dell'ambiente a fronte dell'azione a (nel caso dello 0,7 - 70%) è: la probabilità di arrivare in "v" con una ricompensa di +3, dato che sono partito dallo stato iniziale "u" e ho fatto l'azione "a".
Sempre rimandendo nel diagramma sopra riportato, qual'è la probabilità di andare in "w" con una reward di 42? (vedi figura sotto)
La risposta è zero in quando deve verificarsi la combinazione stato + reward che in questo caso non esistendo è quindi pari zero.
NOTA: lo stato terminale si indica con un quadrato.
Ora semplifichiamo un attimo lo schema per renderlo più leggibile come sotto riportato:
Nello specifico la differenza tra S0 e S1 indica la situazione dello stato "S" al tempo T. Ovvero S0 è lo stato iniziale, mentre S1 è sempre lo stato S ma al tempo T+1 e può valere "w" o "v" a seconda della probabilità. Se ci fosse uno stato successivo S2 dovremmo considerare le probabilità di transizione da S0 a S1 e da S1 a S2.
La rappresentazione è quindi un grafo orientato in quanto unidirezionale. i tondi sono le azioni e gli archi i risultati probabilistici delle azioni.
Ho quindi un insieme di stati S e di azioni A e di rewards R. Dopo ogni azione ho quindi una distribuzione di probabilità su SxR. Per ogni coppia di stato azione ho una distribuzione di probabilità. Conoscere il modello significa quindi conoscere la distribuzione di probabilità. Introduciamo anche il fattore di sconto gamma che vale sempre di meno all'allungarsi della distanza di tempo in modo che l'agente sia incentivato a trovare la soluzione migliore più velocemente.
La funzione p rappresenta quindi il modello, è quindi la probabilità di transizione dallo stato al tempo T-1 allo stato al tempo T. (a fronte di una certa azioen e relativa ricompensa)
Generalizzando quanto sinora detto:
dove il simbolo ｜ (pipe) indica che un elmento "a" è condizionato da "b", es. "a | b". Occhio che per es. P(a,b) è la probabilità dato in input "a" e "b" mentre invece P(a|b) significa la probabilità dato "a" e condizionato a "b" MA "a" puà assumere più valori in B.
dove il simbolo ~ (tilde) indica che uno stato S è preso da una certa distribuzione di probabibilità P, es. S ~ P(...)
Esercizio:
nota: ricordare che il simbolo 𝔼 rappresenta il ritorno atteso ovvero il valor medio dei ritorni.
In pratica 𝔼 rappresenta il valore medio (media dei valori pesati) delle ricompense che posso ottenere in un determinato stato S. Questo perchè in uno stato protrei avere una distribuzione di probabilità che per es. a fronte di una azione possono scaturire più azioni con associata una proababilità e un ricompensa ciascuna. es: 
1)
La prima riga si legge così: la probabilità che un stato S al tempo T sia s' condizionato al fatto che lo stato precedente fosse s e che io abbia fatto precendetemente una derminazione azione a. Quindi si vuole sapere la probabilità di essere nello stato s' nel caso in cui nello stato precedente s sia stata eseguita l'azione a.
Per ricavare questa probabilità bisogna partire la formula generica MDP che tiene conto delle rewards, ovvero:
quindi per rispondere al prima quesito dobbiamo sommare tutte le rewards in modo che rimanga la sola probabilità che ci porta allo stato s', in quanto non vogliamo la probabilità che esca s' e r, ma vogliamo solo la probabilità che esca s', oovero:
perchè sommando tutte le rewards ho la certezza di finire nello stato s'. Sommare tutti gli "r" si dice anche saturare tutti gli indici r.
2)
In questo caso invece si desiderata la ricompensa media (variabile aletoria) al tempo "t" condizionata dal fatto che al tempo t-1 partissi dallo stato "s" e facessi l'azione "a".
Quindi il valore medio della ricompensa sarà la sommatoria di tutte le ricompense ciascuna di esse moltiplicate per la propria probabilità di uscita, ovvero:
dato che in questo caso vogliamo la reward media al tempo t, come nel caso 1) dobbiamo "saturare" un fattore, in questo caso sono gli stati. Quindi per tutti gli stati s' moltiplichiamo la probabilità ritornata dall'azione a nello stato "s" a t-1 per tutte le reward. La prima sommatoria estrare tutte le reward che vanno a moltiplicare le corrispittive probabilità. Moltiplicando reward per la probabilità si ottinene la reward media. (vedi esempio del valotre medio del lancio del dado, dato dalla sommatoria del valore di ciacuna faccia del dado per 1/6 per un totale di 3,5)
3) per ora non viene spiegato.
Dinamica del MDP: rappresentazione tabbellare
Una delle tecniche più basiche di rappresentazione delle transizioni da uno stato all'altro fa uso di matrici di valori che indicano la probabilità di transizione da uno stato all'altro. Se per esempio un sistema ha 4 stati, la tabella sarò composta da una mtrice di 4x4. Ovviamente questo metodo funziona con sistemi i cui stati sono molto limitati, non per funziona con sistemi complessi come per es. gli scacchi o la dama.
Facciamo un esempio, calcoliamo su questo MDP delle quantità:
Iniziamo con il calcolo di una matrice di transizione detta matrice stocastica, in queso caso avendo due stati la matrice è 2x2, nelle celle della matrice andremo ad inserire le probabilità di transizione da uno stato all'altro. Nell'esempio sotto riportato andremo a calcolare la matrice associata all'azione 1. La peculiarità di questa matrice è che la somma di ciascuna riga da sempre 1 - 100%.
| P = 1 (azione 1) | A | B |
| A | 0,8 | 0,2 |
| B | 0,9 | 0,1 |
Calcoliamo ora il vattore ricompensa associata all'azione 1.
| R = 1 (azione 1) | 10*0,8 + 3*0,2 = 8,6 | 0,9*42+0,1*39 = 41,7 |
ora creiamo che tabella che rappresenta l'intero modello:
| s (stato partenza) | a (azione) | s' (stato di arrivo) | r (ricompensa) | p(s',r | s,a) probabilità |
| A | 1 | B | 3 | 0,2 |
| ... | ||||
La tabella conterrà un totale di righe dato dalle azioni x numero di probabilità di accedere allo stato, questo caso 8.
La proprietà di "Markovianità"
La proprità di markov indica che il valore dello stato St dipende esclusivamente dallo St-1 ma non dipende dagli stati precedenti a St-1. (es. St-2, St-3 etc etc)
Episodi MDP
Se ho uno stato terminale tra gli stati possibili allora il mio task si chiama episodico. Attenzione che però dipende dalla policy, ovvero se ho delle azioni che mi consentono di evitare lo stato terminali posso entrare in loop. E' compito dell'algoritmo evitare questi loop. Nel caso in cui non esista lo stato terminale si tratta di un MDP continuing.
Esiston anche task a orizzonte temporale definito se esistono dei limiti temporali.
Un episodio quindi è una sequenza di stati, azioni, rewards che terminano con lo stato terminale.
Simuliamo un episodio:
EPISODIO: A, 1,10, A, 2, -3, B, 2, 0,9, B , 1, 1, C
PROBABILITA': dipende da:
- probabilità di scegliere (1|A)
- probabilità di scegliere (2|A)
- probabilità di scegliere (1|B)
- probabilità di scegliere (2|B)
Per calcolare un episodio bisogna capire quindi come viene definita la policy.
Un esempio di policy π che per esempio può essere scegliere sempre l'azione 1. Quindi la policy "pi" è fondamentalmente una strategia che può (e spesso deve) variare per massimizzare il ritorno.
Ritorno
Il ritorno (G = gain) è la somma delle ricompense di un episodio ed è una variabile aleatoria.
NB: L'ipotesi è che i ritorni R abbiamo un limite superiore finito che consente al fattore di sconto far convergere il ritorno totale.
Ricordo la notazione che si ripeterà spesso nel corso, 
ovvero la probabilità che facendo un'azione "a" nello stato "s" l'ambiente mi porti nello stato s'. Il mio comportamento è rappresentato da una distribuzione di probabilità negli stati S. La strategia di scelta delle azioni - che sia chiama polocy - è una distribuzione di probabilità neglis stati.
Le policy ottimali possono essere deterministiche o non deterministiche. Un esempio di policy determinisca è il lancio de dado in quanto ho una sola possibile azione, appunto il lancio del dato, invece un esempio di non deterministica è per es. sasso-carta-forbice.
Funzione stato-valore
La funzione stato valore per un MDP è il numero che ci indica quale azione intraprendere. Si rappresenta come:
dove V è il valore indicizzato dalla lettera pi (policy) indicizzato dallo stato S.
Mentre "E" è il valore atteso/valore medio, è il valore dello stato, è il numero teorico che se lo conoscessimo aprioristicamente ci "renderebbe la vita più semplice" in quanto significherebbe che conosceremmo l'ambiente, cosa ovviamente non possibile. (spesso il valore E è la media ponderata dei valori attesi)
"E" il è il valore che voglio massimizzare, viene quindi indicato con la lettera "V" che sta per valore indicizzato a pi-greco ovvero la "policy" cioè quello che facciamo noi espresso in probabilità di effettuare un'azione, dello stato "S" (notazione funzionale) uguale al valore medio atteso di Gt -> ritorno al tempo "t" condizionato al stato "s" che è l'argomento della funzione Vπ( s)
Q-learning
E ora veniamo ad un concetto molto importante, il concetto del Q-learning, ovvero action value function che sta per qualità dell'azione.
Qπ(s,a) = rappresenta la qualità di una azione -> partedo dalla prima azione (fissata) e dallo stato (fissato) eseguo tutte le azioni che la policy mi dice di eseguire. Tenendo ovviamente in conto che il modello (P) mi dice quale sarà il nuovo stato e la ricompensa e la policy π deciderà quale sarà la nuova azione da eseguire.
Vπ(s) = rappresenta il valore dello stato "s" (stato di partenza) che si ottiene seguendo le azioni dettate dalla policy π tenendo conto che la scelta delle azioni è di tipo probabilitstico quindi in teoria sarebbe πP. ("P" si omette) Questo guardagno è una variabile aleatoria. L'intenzione è quello il avere il valor medio (la quantità) più grande possibile
V*(s) = è il valore medio massimo ottimale che si può ottenere su tutti i Vπ(s) applicando tutte le policy possibili. -> maxπ Vπ(s)
Q*(s,a) =è la funzione valore ottimale -> maxπ qπ(s,a)
In fine definiamo la policy ottimale π* in grado di massimizzare il valori (sia l'azione valore che la stato valore)
Ora facciamo un esempio:
Esercizio: calcolare il q-values applicando la policy pi nello stato B e compiendo l'azione 1 in un caso e l'azione 2 nell'altro; e calcolare il valore atteso nello stato B applicando la policy uniforme π.
Soluzione qπ(B,1)
qπi(B,1) = gamma*0,1*(39+ V_pi(B)) + gamma*0,9*(42+V_pi(A))
dove:
V_pi(B) = 0,5*q_pi(B,1)+0,5*q_pi(B,2)
V_pi(A) = 0,5*q_pi(A,1)+0,5*q_pi(A,2)
spiegone:
Per determinare la funzione q (valore azione) relativa alla policy π che nel caso di partenza da B, è necessario applicare la "policy di partenza" ovvero al 50% di probabilità di scegliere un'azione. Quindi la qπ(B,1) è calcolata come la probabilità di scegliere l'azione 1 (che in questo caso è del 100% in quanto viene impostato come richiesta iniziale) che moltiplica la probabilità del 10% di ottenere 39 sommato al valore-π dello stato di arrivo ovvero "B", più la probabilità del 90% di andare nello stato A ottenedo 42 sommato al valore-pi di A.
Il valore-pi di A è a sua volta la probabilità di scegliere l'azione 1 sommata alla probabilità di scegliere l'azione 2 ovvero: V_pi(A) = 0,5*q_pi(A,1)+0,5*q_pi(A,2). (dove la probabilità per questa policy di scegliere l'azione è del 50%)
Analogamente il valore-pi di B è probabilità di scegliere l'azione 1 sommata alla probabilità di scegliere l'azione 2 ovvero: V_pi(B) = 0,5*q_pi(B,1)+0,5*q_pi(B,2). (dove la provabilità per questa policy di scegliere l'azione è del 50%)
Da notare che questa non è la policy ottimale in quanto è la policy di partenza che ci da il 50%, l'apprendimento sta nell'iterare il processo a fine di variare la % della policy per farla convergere a quella ottimale.
Bisogna quindi calcolare 4 equazioni con 4 incognite che sono: qπ(A,1) qπ(A,2) qπ(B,1) e qπ(B,2)
Per farla convergere però, bisogna utilizzare un fattore di sconto gamma, altrimenti tende a infinito... (di qui l'introduzione di gamma)
Questo ciclo (iterazione) viene anche detto controllo.
In conclusione questo sistema è una versione dell'equazione di Bellman.
NB: per ricompensa si intede la somma dei valori che il modello ci da quando da uno stato passa ad un altro. Quindi la ricompensa è composta da uno a più valori con relativa percentuale di ottenimento. (es. mi da valore 20 al 10%, valore 50 al 60% e così via) Una volta ottenuti tutti i valori dello stato si calcola il valore medio che appunto rappresnta la ricompensa.
Equazioni di Bellman
Ed eccoci ad uno dei capisaldi dell'apprendimento per riforzo, le equazioni di Bellman che si basano sui concetti sinora appresi, ovvero ritorno (somma delle ricompense), ricompensa, valore dello stato, funzione valore-azione.
Il ritorno Gt può essere formulato (descritto) in maniera ricorsiva in quanto è la somma delle ricompense.
Ovvero il ritorno al tempo t è la somma della ricompensa al tempo t+1 sommato al ritorno del tempo t+1, dove il ritorno al tempo t+1 è rispetto a t+1 (quindi es. t=2 scontato di gamma ovviamente)
dimostrazione:
quindi
Gt = R(t+1) + gamma*G(t+1)
cvd
da qui ne deriva l'equazione di Bellman:
Funzione valore dello stato
La prima equazione ricorsiva di Bellman
innanzitutto bisogna osservare che è un'equazione ricorsiva, in quanto all'interno della funzione è riproposta la funzione stessa.
Come si legge l'equazione di Bellman:
Partiamo dal presupposto che a questo livello stiamo pianificando, ovvero cerchiamo di capire cosa potrebbe accadere se faccessimo l'azione a1 piuttosto che l'a2. In futuro vedremo come apprendere...
Quindi:
Partiamo dallo stato "s", abbiamo una policy π che ci fa scegliere ogni azione tra le azioni disponibili, con una certa probabilità, ovvero -> 
e quindi vediamo cosa succede, ovvero -> 
che significa:
la ricompensa media (è un singolo numero) ottenuta dallo stato "s" facendo l'azione "a" 
sommata al valore dello stato s', 
la cui probabilità di arrivarci è data da 
che rappresenta quindi la probabilità di passare dallo stato s a s', ed è una matrice di valori detta anche matrice di transizione.
dimostrazione:
partiamo dall'assunto:
che ci dice che il valore-pi allo stato S è pari al valore atteso dato dal ritorno al tempo t subordinato allo stato "s".
Vπ(S) =
+
ovvero:
Funzione valore stato-azione
La seconda equazione ricorsiva di Bellman
Valori migliori possibili delle stati e delle azioni (policy ottimali V* e Q*)
Per migliorare la policy devo cercare il "meglio possibile" sia degli stati-valore che degli stati-valore-azione nello stato s per tutte le policy possibili, e quindi sarà il valore più alto (max) ottenibile. Questi valori saranno indicati come V*(s) e Q*(s,a)
Però bisogna dire che le policy potrebbero essere infinite, quindi trovare il valore massimo di queste è un problema...
Tipologie di policy
Le policy possono essere:
1) dipendenti dalla storia si chiama -> HD (history dependent)
2) dipendenti dal tempo e non dalla storia, si chiama -> MARKOV
3) se non dipende da nulla si dice "stazionaria" e si indica con pigrego (π)
Quindi nonostante l'insieme delle policy è un insieme infinito e quindi non è possibile trovare il massimo, allora come faccio? Bisogna quindi prendere un sottoinsieme di policy e in particolare quelle stazionarie e deterministiche, ma in che modo?
Possiamo farlo se agiamo su stati e azioni finiti. Le policy stazionarie e deterministiche sono tutte le possibili azioni associate agli stati. (che si rappressanta com A elevato alla S, dove A sono le azioni e le S sono gli stati)
Se esiste una policy "ottimale", cioè il valore di tutti gli stati è il valore V*/ Q* (massimo) di quello stato.
La policy ottimale è deterministica in quanto sceglie sempre l'azione (una) che massimizza il ritorno, come si trova? si trova agendo "greedy" sulle azioni.
quindi:
Equazione di ottimabilità per funzione stato valore ottimale V* di Bellman
A questo punto troviamo l'equazione ottimale di Bellman per la policy π*
Partiamo dalla "classica" equazione di Bellman che agisce su tutte le policy, ovvero:
Modifichiamola facendola agire solo sulla policy ottimale:
V* = 
ma la policy valore ottimale sceglie le azioni in maniera greedy, quindi:
V* = 
da notare che la V* è ricorsiva in quanto compare all'interno della formula.
Equazione di ottimabilità per funzione azione-valore ottimale Q* di Bellman
Ricapitolando, le equazioni di Bellman ottimali e non sono:
Risoluzione dell'equazione di Bellman
Partiamo dal presupposto che l'MDP è un processo finito, ciò significa che gli stati sono definiti e numerati. I metodi per risolvere l'equazione sono di tipo "iterativo".
NB: In questa fase non stiamo facendo ancora apprendimento, stiamo facendo quella che viene chiamata "pianificazione" in quanto conosciamo il modello. Per implementare la pianificazione, vengono utilizzate tecniche di programmazione dinamica.
La programmazione dinamica è una tecnica di risoluzione dei problemi, si applica in due fasi:
- il problema complesso viene scomposto in sotto-problemi più semplici
- i sotto-problemi vengono poi ricomposti per risolvere il problema originale
Ci sono però dei requisiti, ovvero:
- il problema deve poter essere scomposto, si dice in questo caso che deve avere "una sotto-struttura ottimale"
- i sotto-problemi devono essere sovrapponibili, ovvero alcuni calcoli si possono ripetere in quanto l'algoritmo riceve in input gli stessi valori, per cui in questi è possibile implementare delle ottimizzazioni per evitare l'utilizzo di computazionale, come per es. l'utilizzo di cache, o altro.
Per calcolare la funzione valore di un policy dobbiamo quindi applicare l'equazione di Bellman iterativamente
Programmazione dinamica parte 2 (fase di pianificazione non apprendimento)
Stiamo quindi cercando di risolvere la fantomatica equazione di Bellman per determinare il valore dello stato e/o dello stato ottimale. La tipologia di casi che stiamo affrontando vengono detti "tabellari" in quanto, avendo a che fare con stati finiti, possono essere rapprentati in una tabella con valori finiti.
Per casi più complicati si utilizzano i casi "non tabellari" utilizzando gli approssimatori, ovvero le rete neurali.
Veniamo al pseudo algoritmo che utilizza l'equazione di Bellman.
spiegone:
L'algoritmo inizializza il vettore V con dei valori casuali tranne l'ultimo stato che deve essere inizializzato a zero, Questo perchè l'algorimo è di tipo "bootstrap" ovvero utilizza i valori del vettore al tempo t1 per deteterminare i valori degli stati al tempo t2. Lo stato "finale" deve essere assorbente, ovvero dallo stato finale o si esce o fa ripartire il loop di convergenza.
Ma questa versione non si usa, di seguito la versione migliorata, che in pratica utilizza l'ultimo valore per aggiornare V in quanto l'assegnazione di V svviene nel ciclo più interno, vedi sotto:
in questo modo tutti gli stati succesivi al primo beneficiano di valori aggiornati degli stati precedenti.
Esercizio:
Di seguito abbiamo un "mondo griglia" con due stati finali.
Analisi:
gli stati sono 15, le azioni sono 4, un esempio di policy potrebbe essere: al 70% vado giù, e all'30% vado a destra.
Invece un esempio di policy ottimale:
Vedendo il modello possiamo pianificazione l'azione, per questo stiamo in modalità "pianificazione".
Ora proviamo con la policy: al 70% vado giù, e all'30% vado a destra.
Applicatione pratica dell'equazione di Bellman valore-stato (con policy non ottimale)
Policy Evaluetion
Ora veniamo al secondo passaggio, che va anche a spiegare il primo (rappresentato qui sopra)
Il secondo passaggio (v2) dopo che il primo passaggio ha settatto il valore V degli stati a -1. (ad eccezione ovviamente degli stati finali T che valgono zero)
Il passaggio logico è:
La prima parte dell'espressizione è relatvia alla policy, che nel caso specifico è al 70% andare giù e al 30% andare a destra. (si legge come probabilità di raggiungere lo stato successivo s' facendo l'azione in s, dove s in questo caso vale 1 in quanto è lo stato 1)
Quindi per prima cosa inseriamo nell'espressione le due probabilità 0.7 e 0.3 che moltiplicano una certa quantità.
(questa quantità in formula si legge come la ricompensa media dell'andare nello stato s' sommato alla probabilità dell'azione "a" di andare nello stato s' motiplicata (la probabilità) per la reward dello stato s'. Attenzione che la probabilità di anadare nello stato s' da s, in questo particolare caso, è 100% quindi 1. Da cui ne deriva che:
Il tutto va iterato per tutti gli stati dell'ambiente fino a che i valori degli stati "convergono", il che si significa che variano di poco.
Il metodo consente di propagare in modalità "backward" dagli stati finali (quelli più vicini allo stato T) verso quegli iniziali i valori.
Alla fine ciascuno stato del modello avrà un valore che indicherà quanti "passi" sono necessari per arrivare alla meta, dandoci quindi un'indicazione sul comportametno della policy.
Conclusioni dell'esercizio
Con una policy che assegna il 25% per ogni azione gli stati valori ottenuti sono:
[[ 0. -14. -20. -22.]
[-14. -18. -20. -20.]
[-20. -20. -18. -14.]
[-22. -20. -14. 0.]]
che indicano la ricompensa totale media che si otterrebbe partendo dallo stato. per es. se parto dallo stato "1" (quello vicino all'uscita) otterrei mediamente, con la policy al 25% una ricompensa media di circa -14.
ATTENZIONE! stiamo parlando di una ricompensa media in quanto ci potrebbero essere casi in cui arrivo subito all'uscita andando per es. subito a sx oppure casi in cui inizio a va girare per la griglia, esistono quindi traiettorie lunghissime.
Ecco l'esempio di codice:
allego a questa pagina le classi di ambiente utilizzate per simulare il "mondo griglia"
from envs.gridworld import GridworldEnv
import numpy as np
# 0 su 1 dx 2 giù 3 sx
# instanzio l'ambiente griglia
env = GridworldEnv()
print (env.nS)
print (env.nA)
env.reset()
env._render()
env.step(1)
print()
env._render()
env.step(1)
def policy_evaluation(policy, env, discount_factor=1.0, theta=0.00000001):
"""
:param policy: [A,S] matrice di shape (rango = 29 a due domensioni che rappresenta la policy, dove sulle riche ci sono gli stati e sulle colonne le azioni
:param env: rappresentazione dell'ambiente
:param discount_factor: fattore di sconto gamma
:param theta: valore che termina la valutazione della policy una volta che la funzione stato valore è sotto questa soglia
:return:
"""
# inizializzamo la funzione stato valore V, per semplificare la vita li portiamo a zero
# dove il valore è il valore di OGNI STATO
V = np.zeros(env.nS)
# il ciclo deve fermarsi solo quanto la qta delta calcolata è minuore o uguale a theta
passaggi = 0
while True:
delta = 0
passaggi += 1
# per ciscuno stato effettuo un "full backup"
# questo primo ciclo fa passare tutti gli stati
for s in range(env.nS):
v = 0
# questo il ciclo fa la sommatoria delle azioni
# ovvero esegue tutte le azioni possibili nello stato s
for a, action_prob in enumerate(policy[s]):
# per ciascuna azione chiedo all'ambiente in quale stato finisco, la probabilità di finirci, la ricompensa e se eventualmente è lo stato finale
# NB: la situazione NON è vera in quanto stiamo facendo "esperienza" senza fare un passo, questo non è vero RL è pianificazione
for prob, next_state, reward, done in env.P[s][a]:
# equazione di Bellman
# probabilità dell'azione per la probabilità della transizione
v += action_prob * prob * (reward + discount_factor * V[next_state])
# quanto del valore stato funzione è variatto tra tutti gli stati
delta = max(delta, np.abs(v - V[s]))
V[s] = v
# finiamo la valutazione una volta che il valore è sotto la soglia theta
if delta < theta:
break
return np.array(V), passaggi
# definiamo una polcy generica, in pratica per ogni stato del mondo griglia associo 4 probabilità di eseguire una azione, le probabilità sono tutte al 25%
random_policy = np.ones( [env.nS, env.nA])/env.nA
v,passaggi = policy_evaluation(random_policy, env)
v = v.reshape(4,4)
print(v,passaggi)Migliorare la policy (policy improvement-iteration)
Il metodo per migliorare la policy è quello di compiere tutte le azioni possibili e scegliere quella che restituisce il valore maggiore agendo in maniera "greedy", ovvero:
Come faccio a calcolare pi' (primo) ? be faccio tutte le azioni "a" possibili, faccio "one step looking forward", ovvero faccio un passo avanti compiendo un'azione sola, guardo cosa succede al passo successivo chiedento all'ambiente cosa può succedere con quale probabilità. Facendo queste azioni prendo quella che massimizza il ritorno.
Ma quando una policy è migliore di un'altra? beh quando per ogni stato s, applicando la nuova policy π', il valore dello stato è maggiore-uguale al valore della vecchia policy. Nella pratica faccio N iterazioni compiendo N traiettorie fino a quando i valori convergano, a questo punto confronto tutti gli stati valori con quelli precedenti, se sono migliori allora faccio un altro giro, loppando fino a quando gli stati valori sono uguali al precedente, il che identifica la policy migliore.
Ma cosa vuol dire nella pratica?
Supponiamo di avare uno stato "s" e un'azione "a1" che porta in tre stati (s',s2, s3), dove per ognuno dei tre stati avviamo una probabilità di entrare in ciascuno stato con una relativa reward, abbiamo anche il valor medio totale dello stato Vπ di ciascun stato che era stato precedentemente calcolato applicando la policy. (vedi schema sotto riportato)
Ora per ogni azione (es. a1 e a2) voglio calcolare il valore medio dell'azione stessa che significa calcolare il valore delle "cose/fatti" che possono accadere pesati per le probabilità. Nell'esempio sopra riportato significa prendere la probabilità che accada s' con la relativa reward r dato lo stato s con l'azione a1, ovvero:
p(s',r | s, a1)*(r+Vπ(s')) -> probabilità di andare in s' con l'azione a1 che moltiplica la somma della reward ottenuta per andare nello stato s' + il valore medio totale dello stato s'.
Questa operazione va ripetuta per ogni stato raggiunto dall'azione a1, ovvero nel nostro caso s',s2, s3 e sommata per questi tre stati quindi:
Qπ(s,a) = Σ (xx) p(sxx,r | s, axx)*(r+Vπ(sxx)) dove xx è s',s2,s3
Poi analogamente calcoliamo il Qπ(s,a2) e ne calcoliamo il massimo tra argmax (Qπ(s,a),Qπ(s,a2)) e scegliamo l'azione associata al Qπ massimo. In questo modo andiamo a miglioare la policy in maniera "greedy" ovvero cercando di massimizzare il valore. Il nome di questo algoritmo di chiama "policy iteration". Il cui pseudo codice è sotto riportato:
L'algoritmo alterna la valutazione (evaluation) della policy al improvement fino a che non ottengo la policy.
dove:
1) inzializza i valori randomicamente e seleziona una policy casuale
2) applica la valutazione delle policy, ovvero calcola V_pi
3) miglioramento, ovvero:
- facciamo un ciclo sugli stati S (detta anche "sweep") -> NB essendo pianificazione di un MDP a stati finiti rende la cosa fattibile, in reatà in giochi come "go" non è possibile in quanto gli stati sono un numero enorme, ma questa è un'altra storia)
- ciclo su tutte le azioni dello stato che sto valutando
- salvo la vecchia azione (V(sxx)
- effettuo la nuova azione e vedo quale valore V(sxx) otttengo
- confronto vecchia e "nuova funzione valore" V(S) se il valore della nuova azione è miglioare allora l'agoritmo non ha ancora trovato la policy migliore e quindi aggiorno la policy con l'azione miglioare e continuo a looppare
- fatti passare tutti gli stati se la policy non è stabile riparto dal punto 2
- in generale il tutto looppa finchè i valori non convergono il che significa che tra uno sweep e l'altro non ci sono grandi variazioni
Ricordo che la pianficazione si può applicare solo quando disponiamo del modello, che è il caso più facile e poco probabile che accada nel RL.
Di seguito l'algoritmo completo
from envs.gridworld import GridworldEnv
import numpy as np
def policy_evaluation(policy, env, discount_factor=1.0, theta=0.001):
"""
:param policy: [A,S] matrice di shape (rango = 29 a due domensioni che rappresenta la policy, dove sulle riche ci sono gli
stati e sulle colonne le azioni
:param env: rappresentazione dell'ambiente
:param discount_factor: fattore di sconto gamma
:param theta: valore che termina la valutazione della policy una volta che la funzione stato valore è sotto questa soglia
:return: ritarna la tabella stato valore (V) contenente i valori ottimali per arrivare allo più efficacemente allo stato terminale
in pratica l'algoritmo incentiva ad andare verso lo stato il cui valore è più alto, es. tra due stati che valgono
rispettivamente- 14 e -20 si va verso il valore pià grande ovvero -14.
NOTA: - le azioni sono: 0 = su, 1 = dx, 2 = giù, 3 sx
- la reward è sempre -1 tranne negli stati terminali
- negli stati terminali le azioni non effettuano spostamento di stato.
"""
# inizializzamo la funzione stato valore V, per semplificare la vita li portiamo a zero
# dove il valore è il valore di OGNI STATO
V = np.zeros(env.nS)
# il ciclo deve fermarsi solo quanto la qta delta calcolata è minuore o uguale a theta
passaggi = 0
while True:
delta = 0
passaggi += 1
# per ciscuno stato effettuo un "full backup"
# questo primo ciclo fa passare tutti gli stati
for stato in range(env.nS):
v_appo = 0
# questo il ciclo fa la sommatoria delle azioni
# ovvero esegue tutte le azioni possibili nello stato s
azioni_stato = enumerate(policy[stato])
for azione , policy_prob in azioni_stato:
# per ciascuna azione chiedo all'ambiente in quale stato finisco, la probabilità di finirci, la ricompensa
# e se eventualmente è lo stato finale
# NB: la situazione NON è vera in quanto stiamo facendo "esperienza" senza fare un passo, questo non è
# vero RL è pianificazione
# Da notare che questo ciclo è utile solo nel caso in cui a fronte di una azione ci possono essere diversi
# stati destinazione con diverse probabilità, nel nostro caso ci sarà sempre e solo uno stato destinazione
# con probabilità (env_prob) pari a 1
for env_prob, next_state, reward, done in env.P[stato][azione]:
# equazione di Bellman
# probabilità dell'azione per la probabilità della transizione
v_appo = v_appo + policy_prob * env_prob * (reward + discount_factor * V[next_state])
# delta misura l'errore su tutti gli stati, ovvero misura la differenza tra tutti gli
# nella passata precedente N-1 e l'attuale N.
# Nella pratica significa che per ogni stato il delta massimo trovato è quello indicato nella varibile
# e quindi potrà poi essere comparato con theta per terminare la valutazione della policy
delta = max(delta, np.abs(v_appo - V[stato]))
V[stato] = v_appo
# stampo la tabella degli stati
# vr = V.reshape(env.shape).round(3)
# print(vr,stato,passaggi,'%5.15f' % delta)
# input()
# finiamo la valutazione una volta che il valore è sotto la soglia theta
if delta < theta:
break
return np.array(V), passaggi
def policy_improvment (env, policy, policy_evaluetion_fn, discount_factor=1.0):
"""
Funzione che migliora la policy iterativamente
:param env: ambiente openAI
:param random_policy: passiamo una policy iniziale
:param policy_evaluetion_fn: funzione che valuta la policy e restituisce gli stati funzione valore V
:param discount_factor: fattore di sconto gamma
:return: ritorna una tupla che che tiene la nuova policy ottimale, gli stati valori e il totale passaggi effettuati
"""
def one_step_lookahead(state, V):
"""
funzione helper che calcola il valore di tutte le azioni dato uno stato
:param state:
:param V:
:return: Q-value -> un vettore di lunghezza env.nA ovvero tutte le azioni possibili nello stato che contiene il valore funzione stato per ogni azione.
"""
A = np.zeros(env.nA)
# prendo tutte le azioni possibili nello stato passato in input alla funzione
for a in range(env.nA):
# come reagisce l'ambiente in quello stato
# per ogni azione ottengo il valore totale medio
# NB: interrogo l'ambiente e sarà lui a dirmi con quella azione in quali stati andrò e con quale probabilità e reward
for prob, next_state, reward, done in env.P[state][a]:
# calcolo il valore medio di tutti gli stati raggiungibili effettuando l'azione "a".
A[a] += prob * (reward + discount_factor * V[next_state])
return A
passaggi = 0
# ciclo di controllo.
while True:
passaggi += 1
# valutiamo la policy
V, psg = policy_evaluation_fn(policy, env, discount_factor)
# setto il flag che mi interromperà il loop while
policy_stable = True
# estraggi tutti glistati
# SWEEP
for s in range(env.nS):
# effetuo lo "one step ahead" per capire quali valori mi restituisce l'azione che ho deciso di
action_values = one_step_lookahead(s, V)
############# calcolo l'azione migliore
# IMPROVMENT
#############
best_a = np.argmax(action_values)
# sceglo l'azione con probabilità maggiore tra quelle presente nella VECCHIA (attuale) policy
# per quello stato, nella pratica estrae l'indice
prev_policy_action = np.argmax(policy[s])
# confronto l'azione delle vecchia policy con quella trovata dall'improvment e verifico se coincidoni
# se non coincidono allora la policy non è ancora stabile e quindi non ottimale.
if prev_policy_action != best_a:
policy_stable = False
# setto l'indice dell'azione che massimizza il valore calcolato a 1 per cambiare la policy ottimizzandola
policy[s] = np.zeros(env.nA)
policy[s][best_a] = 1
# se la policy è stabile allora abbiamo trovato quella ottimale, quindi interrompo il ciclo principale ed esco
if policy_stable:
break
return policy, V, passaggi
# 0 su 1 dx 2 giù 3 sx
# instanzio l'ambiente griglia
env = GridworldEnv([4,4])
print (env.nS)
print (env.nA)
env.reset()
env._render()
env.step(1)
print()
env._render()
env.step(1)
# definiamo una polcy generica, in pratica per ogni stato del mondo griglia associo 4 probabilità di eseguire una azione, le probabilità sono tutte al 25%
random_policy = np.ones( [env.nS, env.nA])/env.nA
print(random_policy)
policy_ottimale, V, passaggi = policy_improvment (env, random_policy, policy_evaluation)
#V,passaggi = policy_evaluation(random_policy, env)
v = V.reshape(env.shape).round(0)
print(v,passaggi)
#
print()
print(policy_ottimale)
(https://www.youtube.com/watch?v=QY3yxYyK4wM&list=PLMee1hSjLKdAL16E-7EzqHXsGOgzo8iro&index=13)
Iterazione di valore
Con queste tipologie di algoritmi vogliamo ottimizzare le policy combianando la policy evaluation e la policy improvement.
Nel iterazione della policy ricordiamo che l'algoritmo è diviso in due parti, la prima che riguarda la valutazione della policy (evaluation) e la seconda che la migliora agendo in maniera "greedy" ovvero scegliendo l'azione che massimizza il valore medio atteso prendendo la argmax dei valori restituiti dal "one step look ahead".
Nella iterazione di valore invece l'alogoritmo di semplica e indirettamente si ottimizza combianando i due step secondo lo pseudo codice sotto riportato:
che in pratica applica l'equazione di Bellman sostituendo direttamente il valore medio atteso della funziona stato valore.:
di seguito l'algorirmo rivisto, la differenza in termini di performace rispetto al precedente è notevole.
from envs.gridworld import GridworldEnv
import numpy as np
import time
# funzione per misurare il tempo di esecuzione di una funzione tramite un decorator
# basterà1:
# 1) importare la funzione -> from objs.TimerDecorator import timing_decorator
# 2) decorare la funzione da misurare con @timing_decorator
def timing_decorator(func):
def wrapper(*args, **kwargs):
start = time.time()
original_return_val = func(*args, **kwargs)
end = time.time()
print("time elapsed in ", func.__name__, ": ", end - start, sep='')
return original_return_val
return wrapper
from envs.gridworld import GridworldEnv
import numpy as np
from utils.TimerDecorator import timing_decorator
@timing_decorator
def value_itaration(env, theta = 0.00001, discount_factor=1.0):
"""
Funzione che migliora la policy policy_improvment
:param env: ambiente openAI
:param theta: valore che termina la valutazione della policy una volta che la funzione stato valore è sotto questa soglia
:param discount_factor: fattore di sconto gamma
:return: ritorna una tupla che che tiene la nuova policy ottimale, gli stati valori e il totale passaggi effettuati
"""
def one_step_lookahead(state, V):
"""
funzione helper che calcola il q-value (valore) di tutte le azioni dato uno stato
:param state:
:param V:
:return: Q-value -> un vettore di lunghezza env.nA ovvero tutte le azioni possibili nello stato che contiene il valore funzione stato per ogni azione.
"""
A = np.zeros(env.nA)
# prendo tutte le azioni possibili nello stato passato in input alla funzione
for a in range(env.nA):
# come reagisce l'ambiente in quello stato
# per ogni azione ottengo il valore totale medio
# NB: interrogo l'ambiente e sarà lui a dirmi con quella azione in quali stati andrò e con quale probabilità e reward
for prob, next_state, reward, done in env.P[state][a]:
# calcolo il valore medio di tutti gli stati raggiungibili effettuando l'azione "a".
# equazione di "punto fisso"
A[a] += prob * (reward + discount_factor * V[next_state])
return A
# inizializziamo gli stati con dei valori casuali a piacere (array di N stati)
V = np.zeros(env.nS)
while True:
# inizializzo la variabile che condizione lo stop del loop
delta = 0
# aggiornare di stati
for s in range(env.nS):
# guardo uno step avanti restituendo la funzione stato valore di ogni azioni che può essere fettuata nello stato
best_action_value = np.max(one_step_lookahead(s,V))
# confronto l'azione con i valore dello stato nell'itezione precedente
delta = max(delta, np.abs (best_action_value - V[s]))
# salvo lo stato valore
V[s] = best_action_value
# se il delta è sotto theta allora i valori sono prossimi alla convergenza desiderata
if delta < theta:
break
# ora dagli stati valore ricavo la policu V*(s) -> Q*(s,a)
# inizilizzo la policy
policy = np.zeros([env.nS,env.nA])
for s in range (env.nS):
azione = np.argmax(one_step_lookahead(s,V))
policy[s][azione] = 1.0
return policy, V
# 0 su 1 dx 2 giù 3 sx
# instanzio l'ambiente griglia
env = GridworldEnv([4, 4])
# print(env.nS)
# print(env.nA)
env.reset()
# env._render()
# env.step(1)
# print()
policy_ottimale, V, = value_itaration(env)
# V,passaggi = policy_evaluation(random_policy, env)
print(V)
#
# print()
print(policy_ottimale)
Esercizio 2
Abbiamo un certo capitale inferiore a 100 (es. 99 o 1 o 44) e lo scopo è arrivare esattamente a 100. (valori oltre il 100 non sono considerati, il goal è esattamente a 100) Possiamo scommetere solo il capitale a nostra disposizione lanciando una monetina scommettendo quello che vogliamo sulla base di quello che abbiamo. (es. ho 70 lancio la monetina e scommetto per es. 30 per arrivare a 100, se perdo vado a 40 se vinco vado a 100 e ho terminato il gioco vnicendo. Ovviamente se arrivo a zero ho perso.
Il problema può essere modellato come un MDP, senza 1) fattore di sconto, 2) episodico, ovvero da traiettorie (successione di azioni, rewards e stati) di lunghezza finita che si concludono in uno (o più) stato/i terminale/i raggiungible/i e 3) finito ovvero che stati e azioni sono finiti.
In generale quando le ricompense sono tutte zero, tranne che nella transizione dallo stato precedente allo stato terminale e lo stato terminale stesso, dove in questo caso vale 1, allora la funzione stato valore indica la probabilità di vittoria in quello stato.
Ricodiamo che: il valore dello stato è media con la probabilità di tutte le traiettorie possibili della ricompensa totale.
import numpy as np
"""
Abbiamo un certo capitale inferiore a 100 (es. 99 o 1 o 44) e lo scopo è arrivare esattamente a 100.
(valori oltre il 100 non sono considerati, il goal è esattamente a 100) Possiamo scommettere solo
il capitale a nostra disposizione lanciando una monetina scommettendo quello che vogliamo sulla
base di quello che abbiamo. (es. ho 70 lancio la monetina e scommetto per es. 30 per arrivare
a 100, se perdo vado a 40 se vinco vado a 100 e ho terminato il gioco vincendo.
Ovviamente se arrivo a zero ho perso.
Il problema può essere modellato come un MDP, senza 1) fattore di sconto, 2) episodico,
ovvero da traiettorie (successione di azioni, rewards e stati) di lunghezza finita che
si concludono in uno (o più) stato/i terminale/i raggiungible/i e 3) finito ovvero che
stati e azioni sono finiti.
In pratica lo stato rappresenta il capitale posseduto, e in base a quello la policy dovrebbe
cercare di assumere il comportamento ottimale.
In prima battuta va definito il modello. Il modello restituisce sempre ricompensa 0 tranne
quando arrivo nello stato terminale 100. Notare che la ricompensa non è quanto stiamo guadagnando in
quanto l'obiettivo è arrivare a 100 e non accumulare più soldi possibili.
"""
def values_iteration_for_gamblers(probab_monetina = 0.5 , theta=0.0001, discount_factor=1.0):
"""
:param probab_monetina: probabilità che esca testa
:param theta: valore delta di convergenza
:param discount_factor: fattore di sconto
:return: policy e funzione stato valore
"""
def one_step_look_ahead(in_capital, V, rewards, probab_monetina, discount_factor):
"""
In base allo stato in cui mi trovo, ovvero il capitale a mia disposizione, effettuo una possibile
giocata per tutte le possibili giocate a mia disposizione. Ovvero se ho un capitale di 40, farò
una giocata partendo dalla somma 1 fino al massimo a mia dispisizione. (ovvero 40)
La funziona ci dice nella pratica per ogni azione fatta con il capitale passato quanto vale quella azione.
:param capitale: capitale del giocatore (rappresentato dallo stato)
:param V: stati valore
:param rewars: ricompense
:return: ritorna l'elenco dei valori medi ottenibili effettuato tutte le azioni nello stato ovvero
del capitale passato in input
"""
# inizializzo le azioni possibili in ogni stato
A = np.zeros(101)
# passato il capitale a disposizione, calcolo tutte le possibili giocate da quella minima (1) al massimo
# che posso giocare con il capitale a disposizione passato in input.
# il min(capital, (100-capital)) serve per calcolare il capitale giocabile considerando che
# non posso andare oltre 100 anche se il capitale a mia disposizione lo consetirebbe
capitale_giocabile = min(in_capital, (100 - in_capital))
# effettuo tutte le giocate possibili
for giocata_in_soldi in range(1,capitale_giocabile+1):
# a questo punto per ogni giocata vedo il valore medeio di quello che può succedere effettuando
# tutte le giocate possibili.
A[giocata_in_soldi] = probab_monetina * (rewards[in_capital + giocata_in_soldi] + V[in_capital + giocata_in_soldi] * pow(discount_factor, giocata_in_soldi)) \
+ (1 - probab_monetina) * (rewards[in_capital - giocata_in_soldi] + V[in_capital - giocata_in_soldi] * pow(discount_factor, giocata_in_soldi))
# array che indica per ogni azione fatta con il capitale a mia disposizione, quanto vale ciascuna azione.
return A
######################
######## INIZIO ######
######################
# creo un array di 101 elementi che rappresenta le rewards dove:
# - l'elemento zero è lo stato di perdita del gioco -> stato terminale
# - l'elemento 101 è lo stato di vincita del gioco -> stato terminale
# tutti gli stati avranno una rewards pari a zero tranne l'ultimo (100) che avrà reward = 1
rewards = np.zeros(101)
# ricordo che è zero based, quindi l'elemento 100 è il 101
rewards[100] = 1
# inzializzo la funzione stato valore con dei valori a "caso" facciamo zero per facilitare
V = np.zeros(101)
# creo la policy ottimale
policy = np.zeros(101)
# ciclo principale
while True:
# inizializzo la variabile che verrà utilizzata per interrompere i ciclo di valutazione della policy
# fino alla sua convergenza.
delta = 0
# simulo tutti le possibili giocate con tutti i possibili capitali a mia disposizione
# fa passare tutti gli stati
for giocata in range (1,100):
# verifico quanto valgono tutte le giocate con il capitale simulato
# faccio tutte le azioni possibili
A = one_step_look_ahead(giocata, V, rewards, probab_monetina, discount_factor)
# determino il valore della giocata più alto
best_action_value = np.max(A)
# verifico se la giocata è migliore della precedente
delta = max(delta, np.abs(best_action_value-V[giocata]))
# salvo il valore migliore nella funzione stato valore
V[giocata] = best_action_value
# verifico se interrompere il loop perchè la funzione stato valore sta converendo
if delta < theta:
break
# questo ciclo indica come giocare in ogni stato, dove lo stato rappresenta il capitale posseduto
# serve solo per identificare l'azione megliore da intraprendere basandosi sulle stati valori ottimali precedentemente
# calcolatir
for giocata in range (1,100):
A = one_step_look_ahead(giocata, V, rewards, probab_monetina, discount_factor)
best_action_value = np.argmax(A)
policy [giocata] = best_action_value
return policy,V
policy, V = values_iteration_for_gamblers(discount_factor=1)
# tampo la funzione valore
for i in range(101):
if i % 10 == 0:
print()
print (" %i-%s"%(i,V[i]), end='')
print ()
# stampo la policy
for i in range(101):
if i % 10 == 0:
print()
#print (" %i-%s"%(i,policy[i]), end='')
print(" %i-%s" % (i,policy[i]), end='')
# print (policy)
# print (np.reshape(policy,(10,10)))Sessione 2
Metodi Model free
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. Abbiamo quindi a che fare un metodi "model free" in quanto il modello NON è noto a priori.
Da notare che possiamo comunque interagire con l'ambiente tramite esperienza, ovvero:
- parto da uno stato che posso scegliere in maniera casuale
- scelgo l'azione tramite la mia policy e vedo cosa succede
- torno al punto 1 e così via fino alla fine dell'episodio
SPIEGONE: Tutto questo fino a quando otterremo la "policy ottimale", ovvero facendo la media di tutti i ritorni Gt. Quindi per via delle legge dei grandi numeri possiamo approssimare il valore medio atteso (
) con la semplice media empirica. Ricordo che il valore atteso (E) è quello che si calcola con le probabilità di transizione, mentre la media empirica è la semplice somma di tutti i valori diviso il numero totale dei valori. Quindi quando il numero di valori tende a infinito allora il valore converge al valore atteso.
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, per fare questo abbiamo due metodi, il primo detto "Monte Carlo" mentre il secondo detto "Temporal Difference"
Metodo Monte Carlo
Il metodo Monte Carlo (MC), nella pratica voglio "imparare" il valore delle mie azioni iteragendo con l'ambiente. Banalmente compio azioni "a caso" e poi tengo traccia delle media aritmetica degli episodi che faccio. Svolgo quindi un episodio partendo dallo stato k e raccolgo tutti i valori, e relative reward, degli stati fino allo stato terminale. Terminato un episodio G(T) ne faccio altri N, poi, per ottnere il valore V(Sxx) faccio la media aritmetica di tutti i G(T) ottenuiti partendo dal quello stato "S" e salvo il valore ottenuto nello stato s. 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.
Questo metodo impara il valore della policy dall'esperienza.
Da qui deriva il concetto di "boostrapping", ovvero quando calcolo il valore Vk applicando la funzione "one step looking ahead" andando ad esplorare gli stati successivi s', utilizzo i valori Vk calcolati in precedenza per ricalcolare l'attuale valore Vk.
Da notare che nei metodi con bootstrapping bisogna stimare i valori di tutti gli stati altrimenti perde efficacia.
Di qui la versione più semplice dell'algoritmo in pseudo-codice:
da notare la formula sottolineata che rappresenta la forma incrementale della media aritmetica, ovvero come aggiungere un valore ad una media considerando il suo peso rispetto alla media stessa. In pratica si tratta di sommare la media a (valore meno la media)/numero totale dei valori.
come funziona:
- inzializza la funzione valore con dei valori a caso (anche zeros)
- facciamo un episodio, ovvero memorizzare:
- tutti gli stati
- tutte le azioni
- tutte le ricompense
- fino alla fine
- partiamo dalla fine dell'episodio (stato Rt) e inzializziamo il valore Gt a zero
- procedo risalendo gli stati partendo da quello terminale che vale zero, vado a T-1 del quale prendo la ricompensa e la sommo a quella dello stato se segue (in questo caso quello finale)
- procedo risalendo in questo modo (sommando) fino allo stato iniziale
- calcolo il valore V(St) come la media dei ritorni di tutti gli stati precendenti (da quello terminale a quello in elaborazione)
Di seguito il codice che implementa l'algoritmo:
import io
from collections import defaultdict
import numpy as np
import sys
import gym
import matplotlib as plot
"""
Il BJ è un gioco a due o più giocatori, si tratta di uno o più giocatori contro il banco.
Il banco mostra una carta e poi ci da 2 carte, noi sommiamo queste due carte e possiamo decidere
se prendere una carta o rimanere fermo (stick)
Quando mi fermo faccio la somma delle mie carte, se ho più vi 21 punti allora ho perso, se invece meno
tocca al banco e lui continua a prendere carte fino a quando arriva ad avere più o uguale 17 punti.
A quel punto si ferma anche lui e chi ha di più vince.
NB: Il banco non è interessato a quello che facciamo noi.
POLICY: continuiamo a prendere fino a quanto arrivo a 20 o 21, la reward è +1 se ho vinto, -1 se perdo o zero se pareggio.
Il valore dello stato non è più la probabilità della vittoria
"""
env = gym.make("Blackjack-v1", sab=True)
def mc_prediction (policy, env, num_episodies, discont_factor =1.0):
"""
Algoritmo di predizione Monte Carlo, calcola la funzione valore per una data policy utilizzando il metodo "sampling"
:param policy: una funzione che mappa un'osservazione ad una azione probabile
:param env: openAI gym
:param num_episodies: numero di epidosi che compongo il sample
:param discont_factor: solito
:return: un dizionaio che mappa lo stato nel valore valore, è una tupla il cui valore è float
"""
# preparo il dizionario di ritorno delle funzione
# tiene traccia e conta i ritorni di ciascuno stato per calcolarne la media
# NOTA: tale metodo è inefficiente
returns_sum = defaultdict(float)
returns_count = defaultdict(float)
# funzone valore finale
V = defaultdict(float)
for i_episode in range (1,num_episodies+1):
# stampo a quale episodio mi trovo (utile per il debug)
if i_episode % 1000 == 0:
print("\repisode {}/{}.".format(i_episode,num_episodies), end="")
sys.stdout.flush()
# genera un epidosodio rappresentato da un array di tuple composte da (stati, azionie e ricompendse)
episode = []
state, info = env.reset() # resetto il gioco ovvero la carta che viene mostrata dal banco + le 2 carte che abbiam
while True:
probs = policy(state) # probabilità della policy
# scelgo un'azione a caso dalle prob. della policy
action = np.random.choice(np.arange(len(probs)), p= probs)
next_state, reward, done , truncated, info = env.step(action)
episode.append((state, action, reward))
if done:
break
state = next_state
# scorro tuti gli stati visitati nell'episodio e calcola il valore medio per ogni stato
states_in_episode = set ([tuple(x[0]) for x in episode])
for state in states_in_episode:
first_occurence_idx = next(i for i,x in enumerate(episode) if x[0] == state)
G = sum ([x[2]*(discont_factor**i) for i,x in enumerate(episode[first_occurence_idx:])])
returns_sum[state] += G
returns_count[state] += 1.0
# media aritmetica
V[state] = returns_sum[state] / returns_count[state]
return V
def sample_policy(observation):
"""
la policy che "sticks" ovvero si ferma se il punteggio del giocare è >= 20, altrimente prende una carta
:param observation:
:return:
"""
score, dealer_score, usable_ace = observation
return [1,0] if score >= 20 else [0,1]
V_10k = mc_prediction (sample_policy, env, num_episodies=10000)
Metodo Temporal Difference
Il mtetodo 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 stato s faccio una sola azione per arrivare nello stato s+1 e raccolgo il valore dello stato e la rimpensa corrispondente all'azione. Torno quindi allo stato in cui ero parito allo step (s) e aggiorno il valore. Come aggiorno il valore di S? V(s) = V(s) + α(R + ɣV(s+1) - Vs) dove α è il fattore di apprendimento, più è grande più do importanza al valore restituito dallo stato s+1. Il che significa sommare il valore dello stato attuale alla somma data della 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(s) e α(R + ɣV(s+1) - Vs) è 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(s+1) con i valori ricavati da V(s+2). Anche quindi come con il MC faccio passare tutti gli stati S e lo faccio per N volte, anche in questo modo i valori convergeranno, dopo un numero considerevole di volte, al valore reale.
Esempio.
- setto dei valori a caso per tutti gli stati (es, zero per tutti)
- ad ogni passo sapendo che ho una stima per ogni stato mi metto nello stato di partenza S
- nello stato V(S) faccio l'azione arrivando nello stato S' ottenendo 14 di ricompensa
- la mia nuova stima di V(S) sarà quindi la ricompensana + il valore di S' -> R+V(S') che essendo all'inizio V(S') varrà zero però..
- la stima nuova non voglio utilizzarla completamente per inserirla nello stato S cerco quindi di "poderarla" in qualche modo, quindi sottrarò dalla stima il valore dello stato S ovvero V(S) che in gergo si chiama errore e lo sommo al valore di S.
- Riassumendo V(S) = V(S) + α(errore) dove l'errore è (R(S') + V(S') - V(S))
- faccio così per tutti gli stati
dove α è un iperparametro (numero) che rappresenta quanto viene valutata affidabile la stima
Nella pratica cerco di pesare il valore di V(S') tramite l'iperparametro α in considerazione del valore V(S')
NB: qui faccio del boostrapping, ovvero ad ogni passo aggiorno le stime utilizzando le stime del passo precedente.
Di seguito lo pseudo-codice per la predizione.
Dove ad ogni passo aggiorno il valore della funzione valore.
Differenze e analogie tra MC e TD
- MC funziona solo quando il task è episodico. (quando l'episodio finisce, in realtà esistono task infiniti) TD funziona anche con task continuativi. Nel metodo MC bisogna vedere i ritorni di tutti gli episodi, nel TD invece stiamo stimando il valore di uno stato usando la stima che avevamo prima. Ovvero, al passo K+1 si stimano i valori degli stati usando i valori del passo K e per questo motivo si parla di "differenza temporale". TD apprende ad ogni passo, MC invece deve finire l'episodio. TD è un metodo ON-LINE ovvero che impara ad ogni passo, mentre MC è un metodo OFF-LINE perchè ha bisogno di finire l'episodio aggiornare le sue stime.
- Il MC sommando tutti i ritorni rischia di avere una varianza molto alta in quanto i ritorni potrebbero variare inducendo un ampliamento totale dell'errore, per contro il TD non sommando tutti i ritorni, in quanto si ferma al solo stato successivo, riduce la varianza dell'errore quindi converge prima.
- TD è distorto, mentre MC non lo è.. un punto a favore di MC
Curiosità: diffrenze tra MC , TD e programmazione dinamica (vista a inizio corso)
Model free -> miglioramento e controllo
Nella predizione, viene sempre applicata la stessa policy, ovviamente anche la policy deve migliorare nel tempo, ecco che quindi dopo il ciclo di predizione deve seguire il ciclo di miglioramento e controllo della policy. Questo significa che i valori degli stati migliorerano 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 per fare miglioramento e controllo, e sono:
- On-policy MC control (controllo = iterazione del miglioramento con la predizione)
- On-policy TD control (controllo = iterazione del miglioramento con la predizione)
- Off-policy prediction
- 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 policy, 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 ottenere 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 che per miglioramento della policy si intende: "il valore della nuova policy è migliore della precedente in tutti gli stati".
Dilemma dell'esplorazione vs sfruttamento
Di qui il metodo "epsisodio 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)
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...
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 espilon-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, mentre le altre azioni sono scelte con la policy "mu" esplorativa.
Nella pratica l'azione A viene scelta in maniera epsilo-greedy con la policu "mu" 
mentre l'azione dello stato di arrivo St+1 è scelta con la polict 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è essendo 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".
Sessione 1 (v2)
Premessa
In questa seconda versione del corso ho deciso di soffermarmi sui concetti che non avevo colto nella prima versione del corso stesso.
Le nozioni del primo corso rimangono valide e sono da utilizzare come integrazione di questa seconda versione.
La V2 quindi sintetizza i concetti che reputo più importanti.
Reinforcement Learing (beginner)
Sessione 1 (Markov Decision Process)
Task di controllo
Il Task di Controllo è una sequenza di stati e azioni utili per addestrare l'algoritmo a risolvere un determinato problema.
Il task di controllo è compostato da:
1) Stati S(t) - sono dei momenti nel tempo che assumono un certo valore
2) Azioni A - sono le azioni eseguibili nell'ambiente basate sullo stato del task ed eseguite in un determinato momento nel tempo
3) Ricompensa R - è un valore che l'agente riceve dall'ambiente dopo aver eseguito un'azione
4) Agente - è l'entita che partecipa al task ne osserva lo stato ed effettua le azioni.
5) L'ambiente - è dove vengono eseguite le azioni da parte dell'agente a fronte delle quali vengono restituite ricompense e osservazioni.
Markov Decision Process
MDP sta per processo decisionale di Markov, è un template che serve per descrivere e gestire i task di controllo.
E' un controllo di processo stocastico basato su un tempo discreto.
L'MDP si basa su 4 elementi detti (S,A,R,P) ovvero:
- il set di possibili stati appartenenti al task
- il set di possibili azioni che possono essere intraprese in ciascun stato
- il set di possibili ricompense restituite a fronte di una azione intrapresa nello stato
- la probabilità di passare da uno stato all'altro eseguendo ogni possibile azione.
Di seguto viene data una rappresentazione grafica:
L'MDP ha una importante proprietà, ovvero la probabilità di visitare lo stato successivo dipende esclusivamente dallo stato attuale, il processo di Markov NON ha quindi memoria del passato.
MDP si diverifica nelle seguenti tipologie, ovvero:
- Finito
- Infinito
- Episodico
- Continuo
Nella versione versione finita le azioni, gli stati e le ricompense sono finite, mentre nella versione infinita uno o più dei valori citati sono infiniti. (un esempio di task finito è il labirinto griglia, mentre infinito può essere la guida automatica perchè il valore della velocità è infinito)
Nella versiona episofica l'episodio ha uno stato terminale mentre (come per es. l'uscita dal labirinto) nella versione continua non esiste uno stato stato terminale.
Traiettoria vs Episodio
La traiettoria è la seguenza: stato-azione-ricompensa, partendo da uno stato iniziale fino a giungere ad un determinato stato che può anche essere quello finale. La traiettoria di identifica con la lettera greca tau 𝛕
L'episodio in invece è una particolare traiettoria che inizia da uno stato e finisce nello stato finale.
Ricompensa vs Ritorno
La ricompensa è il risultato immediato che l'azione produce.
Il ritorno è la somma delle ricompense che l'agente ottiente da un certo momento nel tempo (t) finchè lo stato è completato. Il ritorno è identificato dalla lettera G
Ovvero:
L'intento è quindi quello di massimizzare il ritorno atteso Gt
Fattore di sconto
Il fattore di sconto serve per massimizzare il ritorno nella maniera più veloce e ottimale possibile.
Per ottimizzare il ritorno bisogna quindi moltiplicare la rimpensa ottenuta da ciascuna azione per un fattore di sconto gamma (rappresentato dal carattere γ) compreso tra zero e uno γ ∈ [0,1] elevato al momento nel tempo T, ovvero:
In questo modo vengono ridotti i valori di ricompensa ottenuti nel futuro, più è alto l'esponente più il valore nel futuro è ridotto, il tutto fino alla fine dell'episodio. (concetto derivato dalla matimatica finanziaria dove lo stesso valore nominare assume maggiore rilevanza quando è ravvicinato nel tempo, minore quando è distante rispetto a T0)
Se il valore di gamma valesse zero, allora non verrebbero considerate le ricompense future (perchè tutte portate a zero), e questa sarebbe una visione miope del task; al contrario del gamma valesse uno, allora non verrebbe calcolato l'episodio ottimale in quanto le ricompense non verrebbero scontate. Un valore gamma spesso utilizzato è 0.99 che garantisce - in genere - di massimizzare il ritorno, ovvero la somma delle ricompense scontate.
Policy
La policy è una funzione che prende in input uno stato e ritorna l'azione che deve deve essere eseguita nello stato stesso. E' rappresentata la lettera greca pigreco (π)
π : S -> A
Le due tipiche rappresentazioni in questo corso sono π(a|s) e π(s)
π(a|s) è la probabilità di eseguire un'azione "a" nello stato "s" -> ritorna una %
π(s) è invece l'azione "a" da eseguire nel dato stato "s" -> ritorna una azione "a"
Dipende dal contesto, in alcuni casi verrà restituita la probabilità in altri l'azione.
Tipologie di Policy
Le policy possono essere stocastiche o deterministiche.
Una policy deterministica sceglie sempre la stessa azione nello stesso stato, ovvero: π(s) -> a
es. π(s) = a1
Una policy stocatica, sceglie un'azione sulla base di determinate probabilità, ovvero: π(s) = [p(a1),p(a1),........p(an)]
es. π(s) = [0.3,0.2,0.5] che significa che la policy ha la probabilità del 30% di scegliere la prima azione, del 20% la seconda e del 50% la terza.
La policy ottimale, rappresentata da π* il cui scopo è massimizzare la somma dei valori di ricompensa scontati alla lunga.
Stato valore
Il valore dello stato è il ritorno dello stato ottenuto interagendo con l'ambiente e seguendo la policy π fino alla fine dell'episodio, che si indica:
Vπ(s) = 𝔼[Gt | St=s]
di cui il dettaglio della formula:
dove è visibile l'esplosione del ritorno Gt come la somma delle ricompense scontate partendo dallo stato "s" per giungere allo stato finale "T".
Stato-azione (Q-Value)
Se invece vogliamo valutare una azione in un determinato stato, lo facciamo attraverso lo stato-azione Q.
Il valore Q nello stato "s" con l'azione "a" è il ritorno ottenuto eseguendo l'azione "a" partendo dallo stato "s" interagendo con l'ambiente tramite la policy π che seguiremo fino alla fine dell'episodio.
Di cui la formula generica
e la versione dettagliata:
L'equazione di Bellman
L'equazione di Bellman serve per trovare la policy ottimale per risolvere i task di controllo.
Bellman: Stato valore
Questa è l'equazione di Bellman che determina il valore di uno stato Vπ(s) associato alla policy, ovvero:
Le prime tre formule descrivono che il valore dello stato è il ritorno atteso Gt ottenuto seguendo la policy π partendo dallo stato "s". (prima riga)
Possiamo espandere la definzione del ritorno Gt come la somma delle ricompense scontate da γ fino allo stato terminale. (seconda e terza riga)
Nell'espressione finale che ne deriva, troviamo la probabilità di eseguire ogni azione "a" condizionata nello stato "s" seguendo la policy π -> 
il tutto moltiplicato per 
che rappresenta la probabilità di raggiungere ogni stato successivo (indicato con s' ) moltiplicato per la ricompensa ottenuta arrivando nello stato successivo sommata al valore dello stato successivo scontato dal fattore gamma.
Notare l'esistenza della ricorsione per quanto concerne il valore Vπ(s) -> Vπ(s') che può essere utilizzato durante la stesura dell'algoritmo.
Quindi vengono eseguite tutte le possibili azioni nello stato e calcolato il valore moltiplicando la probabilità nell'azione per il ritorno simmato al valore dello stato succissivo.
Bellman: Stato-Azione (Q-Value)
Questa è l'equazione di Bellman che determina il valore di uno stato-azione associato alla policy, ovvero:
Le prime tre formule descrivono che il Q-Value è il ritorno atteso Gt associato all'azione "a" ottenuto seguendo la policy π e partendo dallo stato "s". (prima riga)
Possiamo espandere la definzione del ritorno Gt come la somma delle ricompense scontate da γ fino allo stato terminale condizionate allo stato "s" per l'azione "a". (seconda e terza riga)
Nell'espressione finale che ne deriva, viene indicata la probabilità di raggiungere ogni stato successivo s' sapendo che abbiamo scelto l'azione "a" -> 
il tutto moltiplicato per 
che rappresenta la ricompensa ottenuta raggiungendo lo stato successivo s' sommanta alla somma scontata di γ dei Q-values di ciascuna azione eseguita negli stati successivi pesata per la probabilità di eseguire l'azione in s' dettata dalla policy.
Anche qui viene espresso il Q-Value in termine di altri Q-Values in maniera ricorsiva.
Soluzione di un MDP
Per risolvere un MDP bisogna risolvere un task di controllo, il che significa massimizzare il ritorno atteso. Nella pratica bisogna massimizzare il valore di ogni stato V*(s) -> 
o il valore di ogni Q-Value
Q*(s,a) -> 
Per massimizzare questi ritorni bisognerà quindi trovare la policy ottimale π* che è quella che sceglie le azioni ottimali in ogni stato e che porta il massimo ritorno atteso.
Di seguto viene rappresentata la formula che sceglie l'azione che restituisce il ritorno più alto
nel caso valore dello stato:
e nel caso stato-azione:
Ma pare che ci sia un problema, per trovare la policy ottimale servono dei valori ottimali, e vice versa, ovvero per trovare il valore dello stato ottimale o dello stato-azione ottimale (V* o Q*) bisogna avere una policy ottimale... come fare?
Dobbiamo ottimizzare le equazioni di Bellman:
Per il valore degli stati V*:
ovvero:
Il valore ottimale dello stato è il ritorno atteso ottenuto seguendo la policy ottimale.
La policy ottimale in pratica sceglie l'azione che ritorna il valore più alto (di qui la max) associato al ritorno attesso.
Il ritorno atteso è la probabilità di accedere ad ogni stato successivo effettuando l'azione ottimale moltiplicato per la ricompensa ottenuta al raggiungemento dello stato s', sommato al valore di quello stato s' ottimale scontato da gamma.
o nel caso di dello stato-azione Q*
Nel caso invece del valore Q* ottimale per una azione "a" nello stato "s":
E' la somma pesata dei ritorni ottenuti raggiungendo ogni possibile stato successivo.
Il ritorno è la ricompensa ottenuta raggiungendo lo stato successivo sommato al valore ottimale massimo dello stato-azione successivo scontato da gamma.
Sessione 2 (Dynamic Programming)
La programmazione dinamica (aka DP) è il primo metodo in grado di risolvere il task di controllo.
Lo scopo del DP è tovare la policy ottimale π* per ogni stato V dell'ambiente (che nel nostro caso è discreto)
Per determinare quindi la policy ottimale bisogna rispettare la catena di dipendenze tra stato-azione e stato-valore, ovvero:
Nella pratica l'equazione di Bellman si dettagglia, nel caso di V* come il valore ottimable ricavato dal'azione che lo massimizza, ovvero:
e nel caso dello stato azione come la probabilità più alta che massimizzi di ritorno:
Partiamo dallo stato valore, per poter tovare il valore ottimale bisogna inzializzare tutti gli stati con dei valori a piacere, poi attraverso un processo detto di "sweep" gli stati subiscono una serie di "passate" che ne affina man mano i valori fino a farli convergere verso l'ottimo. Ogni volta che quindi aggiorniamo i valori stimati andiamo a migliorarli e per questo la nuova stima sarà megliore della precedente.
NOTA: uno dei problemi del DP è che necessita di un "modello perfetto" che descriva con precisione la transizione da uno stato all'altro, cosa che in genere non avviene nella realtà. Il modello perfetto ritorna quindi le probabilità di transizione degli stati, come evidenziato nella parte rossa della formula sotto riportata:
Un dei limiti che del DP è che parte dal presupposto che si conosca il modello e che quindi se ne possa verificare con esattezza il comportamento e quindi i ritorni. Nella realtà non è possibile fare questo, serviranno altri metodi che analizzano il comportamento dell'ambiente e cercano di stimare un modello.
Iterazione del valore (value iteration V*)
Ora vediamo l'algoritmo di "iterazione del valore" utile per determinare la policy ottimale π*. Tale algoritmo calcolo lo stato valore ottimale attraverso N passate (dette anche sweep)
Questa policy fa in modo che per ciascuno stato venga eseguita l'azione che massimizza il ritorno. Per trovare l'azione migliore dobbiamo però conoscere il valore ottimale dello stato che potrebbe seguire lo stato attuale. Per determinare il valore ottimale dobbiamo implementare un processo iterativo sugli stati, per far questo manterremo una tabella con i valori stimati per ciascuno stato. L'inizializzazione iniziale non deve essere suibito ottimale, può anche contenere valori randomici che attraverso le varie passate (sweeps) migliorano convergendo all'ottimale.
La reqola di aggiornamento degli stati sarà quindi:
Formula che tradotta significa: determinare l'azione con la probabilità più alta di ottenere la reward che massimizza il ritorno per andare dallo stato s allo stato s'.
Di seguito lo pseudo codice che determina la policy ottimale attraverso la massimizzazioni degli stati valore:
Come si può vedere si tratta due due cicli innestati, il primo che looppa fino a che il valore precedente di ciascun stato si avvicina al valore attuale, il che significa che lo stato valore non sta migliorando più di tanto e quindi possiamo assumere una convergenza.
Il secondo loop, fa passare tutti gli stati dell'ambiente e per ciascun stato calcola l'equazione di bellman assumento una policy di default che assegna la stessa probabilità per ciascuna azione. In questo modo a tendere alcune di queste probabilità, pur essendo uguali, andranno a trovare il ritono migliore. Nella pratica quindi per ogni stato vengono eseguite tutte le azioni possibili e considerata quella che possiede il ritorno più grande.
Vediamo con un esempio, qui abbiamo il labirinto di 5x5 al tempo t0 i cui valori degli stati sono inizializzati a zero. (sebbene avremmo potuto scegliere altri valori anche random)
La ricompensa per ogni azione è -1 tranne che per lo stato finale che è pari a zero.
Quindi iniziamo a iterare su tutti gli stati fino all'ultimo che è quello finale, al tempo t1 il valore degli stati sarà:
si può notare come le ricompense sono tutte -1 tranne lo stato goal finale.
Al tempo t2 notiamo che il valore degli stati si "propaga" dallo stato goal a quello successivo:
e alla fine dopo 18 iterazioni abbiamo i valori non cambiano in maniera sostanziali, siamo quindi arrivati vicini al valore ottimale:
Possiamo notare che più siamo lontani dal goal e più è basso il valore dello stato.
L'agente raccoglie più ricompense negative quando è più lontano dal goal, invece più il percorso che lo porta al goal è breve, meno saranno le ricompense negative che verrano assegnate allo stao.
Per esempio il valore -15,71 è il più alto perchè da quello stato il percorso per arrivare al goal è il più lungo.
Di seguito l'algoritmo implementato in Python:
Innanzitutto definiamo la policy che inizialialmente sceglie con la stessa probabilità una azione tra le 4 effettuabili per ciascun stato del labirito:
inzializziamo anche il valore degli stati:
implementiamo ora l'algoritmo che va a migliorare il valore degli stati e cambia in base al valore migliorato, la policy scegliendo quella che massimizza il risultato.
I primo while serve per verificare se il valore degli stati è arrivato alla convergenza e quindi non migliora ulteriromente.
I due for servono per sweeppare tutte le righe-colonne, mentre il terzo for innestato esegue tutte le azioni nello stato selezionato dai due for eserni.
Il cuore dell'algoritmo è nel terzo "for" interno dove per ogni azione:
- viene interrogato l'ambiete con l'azione e restituito il risultato (-1 o 0) e lo stato successivo
- viene calcolato il valore dato dall'equazione di Bellman scontata dal fattore gamma
- delle 4 azioni viene salvato il valore calcolato da Bellman più alto e l'azione ad esso associata
Fuori dal terzo "for" delle azioni possibili, viene aggiornato il valore dello stato e aggiornato l'array con l'azione associata al valore dello stato più alto calcolato con Bellman.
Viene calcolato il delta che se per tutti gli stati e tutte le azioni è inferiore ad una soglia "teta", ovvero che per tutti gli stati-valore non ci sono grandi scostamenti, allora il ciclo termina con valori e azioni ottimali.
Alla fine questo è il risultato dell'algoritmo:
La policy ci porta quindi direttamente al goal.
Iterazione della Policy (Policy iteration)
Questo algoritmo evolve il precedente (value iteration) e, dal punto di vista funzionale, funge da base per futuri algoritmi utilizzati nell'ambito del Reinforcemente Learning.
I valori degli stati e della policy vengono inizializzati con dei valori arbitrari. La policy può essere per esempio definita come la probabilità equamente distribuita di effettuare una azione tra quelle disponibili.
Con la policy inizializzata vengono calcolati i valori degli stati, poi, nella seconda parte, la policy viene migliorata utilizzando i valori degli stati calcolati dalla prima parte dell'algoritmo. Dopo di questo viene ripetuto il miglioramento dei valori degli stati fino a che non si giunge ai valori e alla policy ottimale.
Queste due ottimizzazioni sono in concorrenza ma nella pratica uno va ad ottimizzare l'altro alternandosi sino a giungere all'ottimale.
Di seguito il pseudo codice dove si possono notare le due fasi di ottimizzazione:
Nella prima parte che calcola il valore degli stati, il loop viene eseguito fino a che non si giunge a dei valori che risultano essere ottimali per l'attuale policy. (loop fintanto che Delta > Theta)
Da notare che, a differenza dell'algoritmo di value iteration, dove la regola di aggiornamento dello stato era di aggiornare il valore scegliendo l'azione che massimizzava il ritorno, nella policy iteration invece, il valore dello stato viene aggiornato sulla base delle probabilità che la policy assegna ad ogni azione. Dopo ogni "sweep" degli stati, le stime saranno sempre più vicine all'ottimale. V0 -> V1 -> V2 -> ... -> Vπ
Calcolati i volori degli stati, segue l'ottimizzazione delle policy che consiste, per ogni stato dell'ambiente, nell'eseguire tutte le azioni possibili nel singolo stato. Per ogni azione viene applicata l'equazione di Bellman che preleva i valori dagli stati. (ricordo che il valore degli stati era stato calcolato precedentemente applicando la policy π0 che adesso stiamo aggiornando a π1)
A questo punto viene selezionata e salvata nella tabella delle probabilità associate alla policy (sempre per ciascun stato) l'azione che massimizza il ritorno secodo l'equazione di Bellman. Se dopo lo sweep di tutti gli stati, le azioni non sono variate rispetto allo sweep precedente, allora abbiamo trovato la policy ottimale e l'algoritmo si interrompe, altrimenti si rapassa all'ottimizzazione dei valori degli stati con la nuova policy appena calcolata.
Da notare che la policy evaluation continua a looppare fino a che non trova il valore ottimale degli stati con la policy attiva, mentre la policy improvement effettua una sola passata.
Ora vediamo l'implementazione in Python:
anche qui, come nell'value iteration andiamo ad inizalizziare la policy e il valore degli stati:
il valore di default per gli stati sarà zero.
La probabilità di ogni azione per ciascuno stato sarà di defautl uniforme, ovvero del 25%.
Nella funzione di "Policy evaluation", viene fatta una sweep di tutti gli stati dell'ambiente, dove per ciascun stato vengono eseguite tutte le azioni che la policy mette a disposizione sommando nella varibile "new_value" i valori ottenti applicando la formula di Bellman. Si otterrà quindi una sommatoria di valori per ciascin stato, dove gli elementi della sommatoria sono le azioni dello stato applicate con Bellman.
Il ciclo si ripete fino a che, lo sweep N ha dei valori (per tutti gli stati) che differiscono di poco rispetto allo sweep N-1 (delta > theta)
In questo caso si passa all'ottimizzazione della policy appena utilizzata, ovvero:
L'ottimizzazione della polcy prevede il classico sweep di tutti gli stati dove per ogni stato viene salvata l'azione della policy che si sta cercando di ottimizzare (che potremmo definire vecchia)
Sempre per ogni stato vengono eseguite tutte le azioni previste dalla policy precedente e tra queste scelta quella che, tramite l'equazione di Bellman, ritorna un valore più alto.
Se dopo aver effettuato uno sweep tutte le azioni definite in tutti gli stati sono identiche allo sweep precedente, allora l'algoritmo ha trovato la policy ottimale e quindi si interrompe, diversamente si passa alla prima parte ovvero la policy evaluation.
Questa è la parte che messe insieme la valutazione della policy e la successiva ottimizzazione.
Di seguito vengono visualizzati i valori degli stati dopo il primo giro, si può notare come tali valori siano particolarmente alti in quanto la policy iniziale impostata, sbaglia molto non essedo ottimizzata. Il valore alto infatti indica il numero di passi che ci sono voluti per la policy a trovare lo stato di uscita.
Bisogna altresì dire che, nonostante i valori alti degli stati, le azioni sono già quelle ottimali, in quanto seppur non ottilame il goal vien raggiunto.
Quelli di seuito sono già valori che si ottengon alla seconda passata con una policy che ha subito un primo processo di ottimizzazione.
Generalize Policy Evaluation
L'algoritmo di policy iterarion ci insegna che questa logica può essere mutuata come un template in molti degli algoritmi di RL attraverso la valutazione e il miglioramento della policy stessa.
Nei prossimi capitoli verranno studiati degli algoritmi più aderenti alla reatà in quanto i modelli non saranno noti (perfetti) a priori come invece avviene nella programmazione dinamica che risulta utile più ai fini didattici che pratici, senza considerate che la DP ha un alto costo computazionale. I problemi reali hanno un vasto se non infinito numero di stati, per cui questa tecnica non è praticabile.
Sessione 3 (Metodo Montecarlo)
Il Metodo Montecarlo (MC) migliora la policy iteragendo con l'ambiente e ottenendo dei ritorni (scontati da gamma) di cui viene calcolata la media. Per la legge dei grandi numeri più osservazioni (e quindi ritorni) otteniamo più ci avviciniamo al valore ottimale atteso Vπ(S).
Dalla formula si evince che il limite per n che tende a infinto dove n è il numero di misurazioni, genera una stima dei valori degli stati con probabilià 100% di essere ottimale.
Il MC ha dei vantaggi rispetto al DP (dynamic programmig spiegato nella sessione 2):
- la stima dei valori degli stati non dipende dagli altri
- il costo per stimare il valore di uno stato è indipendente dal numero toale degli stati
Nel caso del DP l'algoritmo bootstrappa il valore degli altri stati in modo da utilizzare una stima per produrne un'altra. Per questo la complessità di un algoritmo cresce esponenzialmente con il numero di stati.
Cosa molto importante MC non necessita del modello, la dinamica dell'ambiete sarà implicita nella nostra stima.
Per risolvere l'algorimo del MC verrà utilizzato il metodo, visto in precedenza anche con il DP detto "Generalized Policy Iteration".
Generalized Policy Iteration
La GPI si basa sulla valutazione della policy (partendo da una che può essere randomica o arbitraria) per poi migliorarla e looppando fino a quando non si arriva a quella ottiamale.
MC si elabora generando un episodio la cui traiettoria parte dallo stato iniziale sino allo stato finale durante il quale vengono raccolte e sommate tutte le ricompense scontate gamma, per ogni stato dell'enviroment.
Bisogna quindi trovare la policy che sceglie l'azione con il Q-Value più alto, nella pratica dovremo tenere traccia nella tabella dei valori, non più i valori degli stati V(s) come nel DP, ma salveremo i valori delle azioni Q(s,a), ovvero dell'azione che massimizza il valore. 
Il processo per MC diventerà quindi:
Dove la policy calcola i Q-Value che viene a sua volta utilizzato per migliorare la policy in un ciclo continuo fino ai valori ottimali Q* e π*.
Exploration
Quindi la policy migliora sulla base dell'esperienza che agente effettua mentre interagisce con l'ambiente. L'esperienza che l'agente raccoglie dipende dalle azioni che effettua, e le azioni dipendono dalla policy utilizzata in quel momento. Per questo motivo avremo una policy π' che seleziona l'azione sulla base delle stime Q(s,a). E queste stime saranno sempre più accurate soprattutto mentre ci avviciniamo alle fasi finali dell'apprendimento. (a differenza delle fase iniziale dove invece sono inaccurate)
Immaginiamo il caso in cui l'azione è ottimale ma la sua stima Q(s,a) è pessima, allora la policy non la sceglierà in quanto la stima del valore è molto bassa. Si rende quindi necessario che tutte le azioni vengano scelte ogni tanto in maniera casuale per "esplorare" l'ambiente con scelte che normalmente non verrebbero effettuate, ma che possono migliorare la policy anche se apparentemente non nell'immediato. Tutto questo per scoprire eventuali azioni ottimali non considerate dalla policy in uso.
Quindi come mantenere l'esplorazione?
Beh, nella pratica abbiamo due opzioni:
- La prima si chiama "exploring starts" e prevede che l'agente inizi la sua esplorazione in uno stato casuale dell'ambiente ed effettui un'azione iniziale casuale. Purtroppo non è una modalità molto realistica in quanto ci sono molti task che semplicamente non hanno questa possibilità. (soprattutto se parliamo del mondo reale)
- La seconda si chiama "stocastic policies" ovvero vengono considerate le azioni che hanno una probabilità maggiore di zero, in questo modo ogni tanto vengono prese delle azioni "a caso" che potrebbero aiutare la policy a migliorare grazie al caso. (una sorta di evoluzione naturale della specie 😊 ) Queta seconda ipotesti è più realista e più facilmente implementabil.
Le policy stocastiche si suddivino in due tipologie:
- On-policy learning strategies: la quale genera l'esperienza basandosi nulla stessa policy che stiamo ottimizzando
- Off-policy learning strategies: la quale utilizza due policy distinte, una per esplorare l'ambiente e un'altra da ottimizzare
On-policy
Questo metodo segue una strategia che ogni tanto (randomicamente) effettua un'azione a caso, questa policy è chiamata epsilon-greedy. (ϵ-greedy)
In questa policy ogni azione ha la probabilità di essere eseguita maggiore di zero, ogni volta che bisogna scegliere un'azione ne scegliamo una casuale tra quelle disponibili nello stato con probabilità ϵ (che quindi deve essere abbastanza bassa) mentre nelle restanti probabilità 1-ϵ andiamo a scegliere l'azione con probabilità più alta, ovvero:
come si può vedere dalla formula la probabilità di scegliere l'azione ottimale a* (quindi con la stima q-value più alta) è 1-ϵ sommato alla probabilità di scegliere un'azione casualmente, mentre, per contro, abbiamo la probabilità ϵ di sceglire una azione che potrebbe non essere ottiamale. ϵr rappresenta la probabilità di scegliare un'azione tra tutte le azioeni A disponibili.
Facciamo un esempio:
Abbiamo 4 possibili azioni e un ϵ del 20%, come sotto riportato:
La probabilità di sceglire l'azione con il valore Q(s,a) più alto è 80%.
Quando scegliamo un'azione a caso ϵr, la probabilità di scegliare cmq un'azione ottimale tra le 4 possibili è del 0,2/4 che sono le azioni possibili, ovvero del 5%. (o 0,05)
Per questo la probabilità di scegliere un'azione ottimale è del 0,85 (85%) perchè tra le 4 azioni c'è quella migliore (delle 4) che comunque va sommata a 1-ϵ.
Di seguito il pseudo codice che descrive l'alagoritmo:
In input viene passato epsilon e gamma (che ricordo rappresentare il fattore di sconto)
Vediamolo in codice Python.
L'esempio di utilizzo è il classico labirinto 5x5, dove l'agente inizia nell'angolo in alto a sx e finisce il suo percorso in basso a dx.
Per prima inizializziamo la matrice che contiene le azioni effettuabili nello stato con valori zero il cui shape è 5x5x4 dove 5x5 sono gli stati mentre 4 sono le azioni effettuabili in ciascun stato. Il valore per inizializzare scelto è zero ma avrebbe potuto essere un qualsiasi valore arbitrario che il processo di apprendimento avrebbe comunque ottimizzato.
e ora plottiamo la rappresentazione dei Q-values associati a ciascuno stato:
Si possomo vedere i valori per 4 movimenti effettuabili in ciascono.
Creiamo una policy che scelga una azione dato uno stato e la probabilità di scegliere un'azione casuale. (ϵ)
La funzione che sceglie la policy, effettua un'azione a caso tra le 4 disponibili se un numero compreso tra zero e uno, generato randomicamente, è inferiore al epsilon. (prima riga della funzione)
Nel caso invece nel quale si effettui l'azione migliore (1-ϵ) allora vengono in prima battuta estratti i 4 valori Q(s,a) associati allo stato passato in input. Di questi 4 valori viene scelto quello con il Q(s,a) più alto e, nel caso i valori più alti siano indentici tra loro, allora viene effettuata una scelta random tra questi. (vedi ultima riga della funzione)
NOTA: la funzione np.flatnonzero ritorna gli indici di un array che possiedono un valore diverso da zero.
giusto per cuiosità ho estrapolato la parte di codice che esegue l'azione con il Q-value più alto per far vedere come vengono gesiti i casi particolari come più valori identici massimi:
action_values = np.zeros((5,5,4))
def policy(state, epsilon=0.01):
av= action_values[state]
print (av.max())
print (av == av.max())
print ( np.flatnonzero(av == av.max()))
return np.random.choice(np.flatnonzero(av == av.max()))
print (policy((0,0)))
0.0
[ True True True True]
[0 1 2 3]
3Visualizziamo la policy con i valori inizializzati, ovviamente essendo inizializzati l'azione di default è univoca per tutti gli stati.
ora definiamo l'algoritmo principale
def on_policy_mc_control(policy, action_values, episodes, gamma=0.99)
"""
Algoritmo di Montecarlo nella modalità on-policy
policy: funzione policy che scaglie le azioni, spiegata prima e che
attinge dalla tabella degli stati (action_values)
action_values: tabella contente tutte le azioni effettuabili per tutti gli stati dell'env
episodes: numero di episodi utili per far si che la policy migliori
gamma: fattore di sconto
"""
# dizionario dove verranno salvati i valori associati alle coppie stato-azione
sa_return={}
# main loop
for episode in range (1, episodes +1)
# ricavo lo stato iniziale
state = env.reset()
# flag che determina la fine dell'episodio
done = False
# lista alla quale appendere i valori ritornanti dall'ambiente a fronte in una zione
transtions = []
# loop che gira finchè l'agente trova l'uscita e quindi termina il task
while not done:
# effettuo l'azione utilizzando la policy che abbiamo definito (cone random actions)
action = policy(state, epsilon)
# salvo le risposte dell'ambiente
next_state, reward, done, _ = env.step(action)
# salvo lo stao-azione e la reward ottenuta
transtions.append ([state,action,reward])
# salvo il prossimo stato da eseguire
state = next_state
# inizializzo il rtorno
G = 0
# calcolo il ritorno in modalità "backword" ovvero dall'ultimo al primo
for state_t, action_t, reward_t in reverse(transtions)
G = reward_t + gamma*G
# se l'elemento non esiste nel dictionary allora lo creo con per la coppia stato-azione
if not (state_t, action_t) in sa_retutns:
sa_returns[(state_t, action_r)] = []
# aggiungo il ritorno
sa_returns[(state_t, action_r)].append(G)
# salvo nella stato/azione la media dei ritorni per lo stato-azione
action_vales[state][action] = np.mean (sa_returns[(state_t, action_t)])
# test
on_policy_mc_control(policy, action_values, episodes = 10000)
di seguito la tabella delle azioni ottimali negli stati:
di seguito la mappa delle azioni migliori che portano alla fine del tastk
Oltre al set delle azioni migliori si vede come negli stati non ottimali (in alto a dx) l'agente le evita tranne per il fatto che ogni le esplora casualmente.
Ottimizzazione On-Policy
L'ottimizzazione consiste nel modificare l'algoritmo per aggiornare i valori degli stati in maniera più efficiente semplificando l'algoritmo, mantenendo allo stesso tempo la sua effeficacia.
Le differenze si sostanziano in:
- La prima differenza consiste nel fatto che non teniamo traccia dei ritorni osservati dall'agente
- La seconda invece nel "pushare lentamente" il valore della stima di una percentuale alpha (α) che moltipica la differenza tra il ritorno appena calcolato e il precedente valore stato-azione, ovvero: Q(s,a) = Q(s,a) + α[G - Q(s,a)]
Vediamo il pseudo-codice
l'implementazione
def on_policy_mc_control(policy, action_values, episodes, gamma=0.99, alpha=0.2)
"""
Algoritmo di Montecarlo nella modalità on-policy
policy: funzione policy che sceglie le azioni, spiegata prima e che
attinge dalla tabella degli stati (action_values)
action_values: tabella contente tutte le azioni effettuabili per tutti gli stati dell'env
episodes: numero di episodi utili per far si che la policy migliori
gamma: fattore di sconto
alpha= parametro che muove lo stato valore di una percentuale che va in direzione del ritorno appena osservato
"""
# main loop
for episode in range (1, episodes +1)
# ricavo lo stato iniziale
state = env.reset()
# flag che determina la fine dell'episodio
done = False
# lista alla quale appendere i valori ritornanti dall'ambiente a fronte in una zione
transtions = []
# loop che gira finchè l'agente trova l'uscita e quindi termoina il task
while not done:
# effettuo l'azione utilizzando la policy che abbiamo definito (cone random actions)
action = policy(state, epsilon)
# salvo le risposte dell'ambiente
next_state, reward, done, _ = env.step(action)
# salvo lo stao-azione e la reward ottenuta
transtions.append ([state,action,reward])
# salvo il prossimo stato da eseguire
state = next_state
# inizializzo il rtorno
G = 0
# calcolo il ritorno in modalità "backword" ovvero dall'ultimo al primo
for state_t, action_t, reward_t in reverse(transtions)
G = reward_t + gamma*G
# ottengo il q-value dalla tabella dei valori
qsa = action_vales[state][action]
# ottimizzazione, mi muovo nella direzione del valor appena calcolato
action_vales[state][action] += alpha * ( G - qsa)
# test
on_policy_mc_control(policy, action_values, episodes = 10000)Visualizzare la nuova tabella stati valore
Off-Policy
E' la seconda strategia (la prima è l'on-policy) utile per mantenere il miglioramento e l'esplorazione. La logica è sempre quella di effettuare, ogni tanto, un'azione "sub-ottimale" e per questo motivo vengono utilizzate due policy separate.
Nell'apprendimento MC-Off Policy, andiamo quindi a separare la "Exploratory policy" b(a|s) dalla "Target policy" π(s,a) (quella da ottimizzare)
La policy di esplorazione effettuerà quindi una traiettoria explorativa la cui esperienza verrà utilizzata dalla target per essere migliorata. π(s,a) <- arg max Q(s,a)
Nella pratica i valori della target policy verranno aggiornati sui campioni raccolti dalla exploration policy. Per funzionare, la exploratory policy deve raccogliere tutte le azioni che la target policy può effettuare. Quindi se la target ha una probabilità di effettuare un'azione > 0 allora anche l'exploratory deve avere questa probabilità.
Ovvero: if π(s,a) > 0 allora b(s,a) >0 altrimenti ci potrebbero essere azioni che la target sceglie mentre la exploratory no, il che non farebbe migliorare la target.
Nella pratica viene calcolato il ritorno medio utilizzano la policy di eplorazione andando ad approssimare il valore Q(s,a) non della target policy. Per migliorare la target policy bisogna quindi utilizzare una tecnica chiamata "importance sampling" la quale va a stimare i valori attesi di una distribuzione (la target), lavorando con i campioni di un'altra (l'exploratory).
Importance sampling
Il metodo utilzzato per legare statisticamente le due policy è chiamato "Importance sampling" aka IS, consta nel moltiplicare il ritorno al tempo "t" per un valore chiamato "Wt" il cui valore è dato dal rapporto tra: tutte le probabilità generate allo stato k dalla target policy nell'effettuare le azioni, divisa dalla proprietà generata dalla exploration policy anch'essa nel scegliere le azioni.
E[ Wt x Gt | St = s] = Vπ(s)
In questo modo moltiplicando l'IS per il ritorno Gt andiamo ad approssimare il valore ottimale della target policy Vπ(s)
La regola di aggiornamento dei valori ottimali Q-values (s,a) è quella di tenere traccia della lista di tutti i ritorni osservabili, poi quando c'è da aggiornare i valori Q si fa la media di tutti i ritorni G precedenti. Il ricalcolo però è inefficiente perchè necessita di un grosso quantitativo di memoria per salvare tutti i ritoni G.
Utilizzeremo quindi il metodo già visto nel MC On-Policy ottimizzato, che va a "spostare" lentamente lo stato valore verso il nuovo valore osservato:
solo che questa volta non utilizzeremo un valore alpha discrezionale invece verrà utilizzato l"Importance sampling" precedente descritto, normalizzato con la sommatoria C(s,a) di tutti i valori "importance samples" precedenti.
Per evitare distorsioni dovute ai valori di IS, lo si va a normalizzare divedendolo per tutti gli IS osservati per lo stato azione elaborati. (vedi immagine sopra) Questo manterrà gli aggiornamenti tra zero e uno.
Di seguito il pseudo codice:
E' simile all'online MC ma utilizza due policy e tiene un totalizzatore di "important sampling ratio C(s,a)" per tutti gli stati-azioni.
Passiamo ora all'implementazione
# inizializzazione della tabella Q-value (s,a) con valori arbitrari
action_values = np.full((5,5,4),-100)
# setto il valore del goal a zero
action_values [4,4,:] = 0.e visualizziamo la tabella con i valori:
# creiamo la policy
# scegliere un valore a caso tra quelli pià alti
def target_policy(state):
av = action_values[state]
return np.random.choice(np.flatnonzero(av == av.max()))
# creiamo una policy esplorativa
def exploratory_policy (state, espsilon=0.2):
"""
state: id del valore azione
espsilon: probabilità di intraprendere un'azione casuale
"""
# definiaimo che ogni tanto casualmetne effettua un'azione casuale
if np.random.random() < espsilon:
return np.random.choice(4)
else:
# in caso in cui sceglie l'azione migliore
return target_policy(state)
# implementiamo l'algoritmo MC-off policy
def off_policy_mc_control(action_values, target_policy, exploratory_policy, episodes, gamma=.99, espsilon=.2):
"""
action_values: tabella stati azioni Q(s,a)
target_policy: policy da ottimizzare
exploratory_policy: policy che esplora casuale ogni tanto (espilon)
episodes: numero di episodi
gamma: fattore di sconto
espsilon: probabilità di scelta di un'azione casuale
"""
# creiamo una matrice dove verranno salvate le somme dei rapporti associati agli IS inizializzandola a zeroes
# la matrice contiene un valore per ogni combinazioni di stato-azione 5x5 stati x4 valori a stato
csa = np.zeroes ((5,5,4))
# ciclo per tutti gli episodi passati in input
for episode in rage (1, episodes +1):
# inizializzo il ritorno a zero
G = 0
# inizializzo l'importance sampling (rapporto tra le due policy)
W=1
# inizializzo le variabili del task
state = env.reset()
done = False
transition = [] # array dove vengono salvate le ossercazioni ritornate dell'env
# loop che si ripete fino alla fine dell'episodio
while not done:
# usimo la exploratory policy
action = exploratory_policy(state, espsilon)
# eseguiamo l'azione "esplorativa"
next_state, reward, done, _ = env.step(action)
# salvo l'osservazione ritornata dall'env
transition.append([state,action,reward])
# salvo lo stato per il prossimo giro
state = next_state
# utilizziamo l'esperienza ottenuta dall'esplorazione per migliorare la policy target
# parto dalla fine del task e calcolo il ritorno G scontato da gamma
# L'ordine è inverso per facilitare il calcolo dei ritorno
# Nella pratica faccio passare tutti gli stati-azioni che sono stati ritornati durante
# la fase di esplorazione. Per ciascuno di essi calcolo:
# 1) il rapporto IS
# 2) uso il rapporto IS per "spostare" proporzionalmente il valore Q(s,a) verso il ritorno appena calcolato
# e lo sommo alla tabella stato-azione
for state_t, action_t, reward_t in reversed(transition):
# calcolo il ritorno scontato da gamma
G = reward_t + gamma * G
# calcolo l'important sampling W
csa [state_t,action_t] += W
# salvo il vecchio valore associato allo stato-azione
qsa = action_values[state_t][action_t]
# aggiorniamo i q-values spostando il valore
action_values[state_t][action_t] += (W/csa[state_t][action_t]) * (G -qsa)
# dopo il ricalcolo degli stati azioni riprovo la target policy e verifico se l'azione è diversa da quella precedente
# se così allora interrompo il miglioramento e riprendo con l'esplorazione con un altro episodio
if action_t != target_policy(state_t):
break
# ricalcolo l'IS
W = W * 1 / (1-epsilon + epsilon/4 )
Sessione 4 (Temportal Difference)
54