Appunti di informatica

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:

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

1. inizialmente una tabella contiene i valori (delle ricompense!) ottenute su ogni stato,
2. inizialmente sono valori assegnati in modo random perche sconosciuti
3. quando mi trovo in uno stato, ricevo la vera ricompensa di quello stato, la correggo rispetto a quella ipotizzata
4. 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)
5. 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 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 s_t in funzione del valore dello stato successivo s_t+1 (è ricorsiva). Si usa una lockup table

• V(s_t) viene stimanto e contiene anche la predizione della ricompensa r_t+1

Se la predizione r_t+1 non è corretta il valore stimanto V(s_t) 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