Le basi

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.

Tipologie di processi decisionali di Markov

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$ "tau". Un esempio può essere:

$\tau$ = 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.

L'episodio è semplicemente una traiettoria che inizia in uno stato e finisce nello stato finale oltre quale non si torna indietro. es:

$\tau$ = S0, A0, R1, S1,.A1, R2, S2, A2, R3, S3, ..... RT,ST.

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.

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.

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.

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 vanni 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 a "b", es. "a" | "b".

Esercizio:

nota: ricordare che il simbolo rappresenta il ritorno atteso ovvero il valor medio dei ritorni.

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.

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.

2019 10 28

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, è 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.

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

Una piccola premessa, V( s) è il valore atteso applicando la policy pi (pigreco) nello stato "s", mentre invece l'azione-valore Q( s,a) è il valore atteso partendo dallo stato "s" e scegliendo l'azione "a" applicando la policy "pi". (vedi immagine sotto riportata) Nel caso di V_pi(s) abbiamo il valore atteso nello stato "s" (nb: specifico stato "s", non altri) applicando un'azione casuale, nentre con Q_pi(s,a) abbiamo si il ritorno nello stato "s" ma applichiamo l'azione "a" in modo che il ritorno sia massimizzato, quindi la differenza rispetto a Vpi(s) è che nel primo caso l'azione non è applicabile, mentre nel Q_pi(s,a) l'azione scelta è quella con maggior probabilità ci restituire un ritorno massimizzato. Quindi viene valutata la "qualità" dell'azione "a".

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

Soluzione q_pi(B,1)

q_pi(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 pi 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_pi(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 valoree-pi 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_pi(A,1) q_pi(A,2) q_pi(B,1) e q_pi(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 "pi" 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_pi(S) =

ovvero:

2019 10 29

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 (pi)

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 pigrego-*

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:

2019 11 04

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.

2019 11 05

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 essre 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 aggiornare in quanto l'assegnazione di V vabbine 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)

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

2019 11 11

Migliorare la policy

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'ambiete cosa può succedere con quale probabilità. Facendo queste azioni prendo quella che massizza il ritorno.

Ma quando una policy è migliore di un'altra? beh quando per ogni stato s, applicando la nuovo policy pi-primo, 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.

Da cui il teorema di miglioramento delle policy

Q-pi (s,a) ricordo che rappresenta la funzione valore azione e rappresenta il valore che ottengo partendo da s e facendo la prima azione - che scelgo io! - dove le prossime azioni saranno scelte esclusivamente policy pi e non da me come invece avviene con la prima azione, ovvero:

notare che q-pi è la policy vecchia, mentre il pi' nella formula rappresenta la nuova policy che viene eseguita nella prima azione, dove la nuova policy pi' è deterministica, perchè altrimenti sarebbe una distribuzione di probabilità.

Ovvero:

dimostrazione che si basa passando per stati intermedi:

Iterazione di policy (algoritmo di controllo)

L'algoritmo alterna la valutazione (evaluation) della policy al improvement fino a che non ottengo la policy.

la figura illustra il processo che partendo dalla funzione-valore i cui valori degli stati sono inizializzati randominicamente prima del cicolo iniziale, si va poi ad applicare la policy "greedy" al termine di ogni ciclo per poi ripetere l'iterazione. La scelta della policy greedy meigliore è l'azione che massimizza il ritorno.

Di seguito l'algorirmo:

dove:

1) inzializza i valori randomicamente e seleziona una policy casuale

2) applica la volutazione 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)
salvo la vecchia azione
calcolo la nuova azione
confronto vecchia e nuova azione se sono uguali l'agoritmo ha trovato la policy migliore altrimenti riparto dal punto 2

Ricordo che la pianficazione si puà applicare solo quando disponiamo del modello, che è il caso più facile e poco probabile che accada nel RL.

2019 11 25

Prediction, Improvement and Control

La programmazione dinanica serve per migliorare la policy attraverso iterazioni continue degli algoritmi.

I passi sono:

1) identificare una policy (per es. nella griglia-matrice potrebbe essere 4 azioni con identica probabilità di esecuzione)

2) Policy Evaluation: applicare l'equzione di Bellman per calcoloare la funzione Valore (V) ottimale. (con tante iterazioni fino a quando raggiungiamo una convergenza con un grado delta tra un'iterazione e l'altra, picccolo a piacere)

3) Control: sulla base della policy evaluetion (2) vado a migliorare la policy per determinare l'azione migliore agendo in modalità "greedy" .

Analizziamo l'algoritimo che valuta la policy:

Il cui output determinare i valori degli stati (funziona stato valore) che sarà utile nella fase successiva che è l'improvmente (o controllo)

Ora per migliorare la policy devo applicare il metodo "one step look ahead", ovvero per ciascun stato, eseguo tutte le possibili azioni e ricavo il relativo valore dell'azione. (valore che deve essere pesato per la probabilità dell'azione, che nel griglia vale 1 in quanto a fronte di un'azione si arriva in un solo stato)

Per quanto devo iterare sul meglioramento della policy? fino a quando la nuova policy calcolata è identica a quella precente.

riporto gli step di "controllo" atti a migliorare la policy.

Innanzitutto il miglioramento della policy è composto dalla valutazione della policy stessa, sommata all'algoritmo di valutazione "one_step_look_head" che riporto di seguto:

nella pratica, passato uno stato e la funzione degli stato-valore (V) valorizzati dalla policy evaluation, calcola il valore atteso per tutte le azioni effettuabili nel singolo stato passato in input. Ovvimanete un'azione potrebbe avere diverse probabilità di andare di diversi stati con la relative ricompese. Nel caso del "mondo griglia", da uno stato esiste un solo stato destinatario, quindi la probabilità è sempre pari a 1 e un unico ciclo. Questo per far capire il ciclo for interno che potrebbe avere più probabilità per singola azione.

In sintesi gli step sono:

0) inizializzo una policy casuale

LOOP

1) calcolo la funziona valore della policy (al primo giro è quella casuale)

PER OGNI STATO

2) scelgo l'azione A che massimizza la reward per lo stato passato

3) scelgo l'azione B applicando la funzione one_step_look_ahead passato lo stato e la funziona valore

4) confronto l'azione A e l'azionbe B, se sono diverse allora la policy non è ancora la migliore in quanto per esserlo la policy precedente deve essere indetica all'attuale.

5) aggiorno la policy relativa allo stato in elaborazione, azzerando le percentuali delle azioni disponibili e portando a 1 (100%) l'unica azione con valore massimo del punt 3. (vedi funzione numpy "eye") Questo vettore è detto anche "vettore policy deterministica"

A questo punto se la policy è stabile la ritorno insieme alla funziona valore ad essa associata.

Ed ecco un esempio di risultata dell'algoritmo applicato ad una griglia 4x4

Oltre alla policy ottimale è interessante notare la funzione valore che a questo livello indica il numero di passi necessari per arrivare alla destinazione.