Vedere prima Markov Decision Processes MDP
https://en.wikipedia.org/wiki/Value_iteration
L'obiettivo del 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:
Trattandosi di un processo iterativo, bisogna avere tabelle piccole su cui iterare, quindi insieme finito di stati e azioni.
Ad esempio, ripeto 100 iterazioni e convergo ad una soluzione con questo modello di architettura modello actor-critic
??? 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).
Si ottiene una funzione valore V (value function) della ricompensa nello stato attuale st in funzione del valore dello stato successivo st+1 (è ricorsiva). Si usa una lockup table
Se la predizione rt+1 non è corretta il valore stimanto V(st) 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.
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.
Il modo più semplice di implementare la funzione valore V(s) è quello di usare una 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