User Tools

Site Tools


neurali:algoritmo_value_iteration

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
neurali:algoritmo_value_iteration [2017/06/25 18:48]
profpro
neurali:algoritmo_value_iteration [2020/06/08 22:20] (current)
Line 1: Line 1:
 +^ [[neurali:modelli_di_apprendimento|{{:neurali:indice.png?60}}]] ^ [[neurali:modelli_di_apprendimento]] ^
 +
 +====Algoritmo Value Iteration====
 +
 +Vedere prima [[neurali:mdp|Markov Decision Processes]] MDP
 +
 +https://en.wikipedia.org/wiki/Value_iteration
 +
 +L'obiettivo del [[neurali:Reinforcement Learning]] (LD) è, in ogni //stato// del sistema, quello di attuare l'azione che porterà in stati futuri che poi produrranno le **massime** ricompense.
 +Il criterio di scelta delle azioni (la politica delle azioni) si può ottenere in vari modi:
 +  * ad esempio, conoscendo **esplicitamente** prima tutti gli stati, attraversandoli iterativamente, memorizzando in una **tabella le azioni** che producono massima ricompensa o minima punizione. 
 +  * ad esempio, i cuccioli degli animali, con il comportamento del gioco, riescono a fare esperienze ed a scoprire quale azione associare a quale stato per ottenere la massima ricompensa...
 +
 +Trattandosi di un processo iterativo, bisogna avere tabelle piccole su cui iterare, quindi insieme finito di stati e azioni.
 +
 +===Iterazione===
 +
 +  - inizialmente una tabella contiene i valori (delle ricompense!) ottenute su ogni stato,
 +  - inizialmente sono valori assegnati in modo random perche sconosciuti
 +  - quando mi trovo in uno stato, ricevo la vera ricompensa di quello stato, la correggo rispetto a quella ipotizzata
 +  - devo memorizzare anche quale azione mi ha portato a quello stato? si, c'è un coefficiente che serve per dare molto peso alle ricompense iniziali.  (la somma di tutte le ricompense ottenute, per scoprire quale è la strada per ottenere la ricompensa totale massima)
 +  - ripeto un numero finite di volte, alla cieca, perché nessuno sa se si arriva ad una tabella stabile...
 +
 +Ad esempio, ripeto 100 iterazioni e convergo ad una soluzione con questo modello di architettura [[neurali:modello actor-critic]]
 +
 +
 +<del>??? Poiché nel futuro ci potrebbero essere un numero infinito di cambiamenti di stati, **tale somma è scontata** (la somma di tutte le ricompense ottenute, per scoprire quale è la strada per ottenere la ricompensa totale massima). Poiché ci sono variabili //aleatorie//, alla formula si deve applicare anche una funzione Valore Atteso (E).</del>
 +
 +
 +==== Funzione valore ====
 +
 +Si ottiene una funzione valore V (value function) della ricompensa nello stato attuale s<sub>t</sub> in funzione del valore dello stato successivo s<sub>t+1</sub> (è ricorsiva). Si usa una lockup table
 +
 +  * V(s<sub>t</sub>) viene stimanto e contiene anche la predizione della ricompensa r<sub>t+1</sub>
 +
 +Se la predizione r<sub>t+1</sub> non è corretta il valore stimanto V(s<sub>t</sub>) deve essere modificato
 +
 +
 +Alla nuova V(s) aggiornata, non si aggiunge direttamente Delta, ma un Delta * Alfa
 +Scegliendo Alfa abbastanza piccolo, è dimostrato che TD converge.
 +
 +==== Durante la fase di apprendimento ====
 +
 +Al primo tentativo deve osservare la ricompensa in tutti gli stati e non si può fare la differenza con il valore osservato nello stato osservato alla iterazione precedente (perché si tratta della prima iterazione).
 +I passaggi successivi permettono invece di ottenere il Delta con i. Questo delta permette di aggiustare la stima di V(s).
 +Se Delta è positivo significa che lo stato s, all'istante i+1  è migliore di quanto previsto, e V(s) verrà aumentato.
 +
 +===Implementazione===
 +
 +Il modo più semplice di implementare la funzione valore V(s) è quello di usare una [[neurali:look-up table]], con una riga per ogni stato.
 +
 +Lock-up table: è una tabella associativa, che si consulta per cercare il risultato di un calcolo (invece di eseguirlo), come le tabelle trigonometriche. http://it.wikipedia.org/wiki/Tavola_trigonometrica
 +
 +Anche se le azioni sono discrete, la politica Pgreco può essere rappresentata con tante tabelle, una per ogni stato, con una riga per ogni azione per quello stato
 +
 +Le dimensioni della memoria occupata sono: a x s (a: numero azioni per ogni stato) (s: numero stati)
 +
 +La fase di apprendimento e' lenta perche' le tabelle devono essere visitate iterativamente piu' volte per assegnare un buon valore alla funzione valore
 +
 +----