Algoritmi di apprendimento per rinforzo
Come abbiamo già detto, l’apprendimento per rinforzo viene utilizzato in situazioni in cui è presente un processo decisionale di Markov che osserva il comportamento di un agente che prende decisioni immerso in un ambiente che assume stati diversi e che produce conseguenze in funzioni delle decisioni prese. Il sistema complessivo appare come un automa a stati finiti che ha:
Spesso un arco viene chiamato esperienza, e una sequenza di esperienze dallo stato iniziale allo stato finale viene chiamato episodio.
Si noti come l’agente abbia il controllo solo delle proprie decisioni, mentre il valore della ricompensa è ignoto e casuale e viene scoperto e campionato al momento dell’esperienza come conseguenza della decisione e del cambiamento di stato. La prima volta che l’agente viene immerso nel sistema, non può far altro che decidere in maniera casuale. Se fosse un oracolo con conoscenza perfetta e futura, sarebbe in grado di fare la scelta migliore. Non resta allora che sperimentare il sistema ed apprendere dall’esperienza, dalle ricompense sperimentate ad ogni scelta, ed utilizzare quanto appreso la prossima volta.
Lo scopo dell'apprendimento per rinforzo è che l'agente impari una politica ottimale, o quasi ottimale, che massimizza la "funzione di ricompensa" o altro segnale di rinforzo fornito dall'ambiente che si accumula a partire dalle ricompense immediate.
Un agente di apprendimento per rinforzo interagisce con il suo ambiente in fasi temporali discrete. In ogni istante t, l'agente è nello stato corrente s(t) e sceglie un'azione a(t) dall'insieme di azioni disponibili, che viene successivamente inviata all'ambiente ricevendo la ricompensa ra(t).
L'agente in genere osserva direttamente lo stato ambientale attuale; in questo caso si dice che il problema ha piena osservabilità. Se l'agente ha accesso solo a un sottoinsieme di stati, o se gli stati osservati sono corrotti dal rumore, si dice che l'agente ha osservabilità parziale e formalmente il problema deve essere formulato come un processo decisionale markoviano parzialmente osservabile. In entrambi i casi, l'insieme di azioni a disposizione dell'agente può essere limitato.
Una delle situazioni di apprendimento per rinforzo utilizzate come test è il gioco del BlackJack.
Nel noto gioco di carte da casinò blackjack, l'obiettivo è raccogliere carte il cui valore totale sia il più alto possibile senza superare 21. Un asso può valere 1 o 11, mentre tutte le figure contano 10 e le altre carte hanno il loro valore facciale. Prendiamo in considerazione la variante in cui ogni giocatore affronta da solo il banco. All'inizio del gioco vengono distribuite due carte al dealer e al giocatore. Le carte del dealer vengono distribuite una scoperta e l'altra coperta.
Un naturale si verifica quando un giocatore ha subito 21 (un asso più una carta da 10). A meno che anche il banco non abbia un naturale, nel qual caso la partita è un pareggio, il giocatore vince. Nel caso in cui il giocatore non abbia un naturale, può chiedere più carte una alla volta (prende: hit) finché non supera 21 (sballa) o si ferma (basta: stand o stick). Può anche raddoppiare la posta e chiedere una sola carta (raddoppia). Se sballa, perde; se si ferma, è il turno del dealer. Il dealer è costretto a chiedere carta o fermarsi secondo una strategia predeterminata: si ferma se il totale è superiore o uguale a 17 e prende in qualsiasi altro caso. Il giocatore vince se il banco sballa; in caso contrario, chiunque abbia un valore totale più vicino a 21 vince.
In questo gioco (a parte altre variazioni di gioco possibili) le azioni sono due ( hit o stand ) , lo stato è costituito dalla coppia (punti del giocatore, carta visibile del dealer), la ricompensa alla fine dell’episodio è zero in caso di pari, +1 in caso di vittoria del player e -1 in caso di sconfitta del player.
Quando la prestazione dell'agente viene confrontata con quella di un agente che agisce in modo ottimale, la differenza di prestazione dà origine alla nozione di rimpianto. Per agire in modo quasi ottimale, l’agente deve ragionare sulle conseguenze a lungo termine delle sue azioni (cioè massimizzare la ricompensa futura), sebbene la ricompensa immediata associata a ciò potrebbe essere negativa. Pertanto, l’apprendimento per rinforzo è particolarmente adatto a problemi che includono un compromesso tra ricompensa a lungo termine e ricompensa a breve termine. Ad esempio è usato per addestrare sistemi robotici che operano in ambienti complessi ed incerti, in agenti che giocano a livello superumano come AlphaGo, in agenti di trading on-line che imparano dal mercato, nella ottimizzazione del trattamento di malattie lunghe e complesse.
L'uso del campionamento e della esplorazione (proviamo a decidere e vediamo come va) per ottimizzare le prestazioni e l'uso dell'approssimazione delle funzioni per gestire ambienti di grandi dimensioni permette di studiare situazioni in cui non si conosce un modello dell'ambiente, o lo si conosce ma non è disponibile una soluzione analitica oppure viene fornito solo un modello di simulazione dell'ambiente o l’unico modo per raccogliere informazioni sull’ambiente è interagire con esso.
Servono algoritmi di esplorazione intelligenti, perchè la selezione casuale delle azioni, senza riferimento a una distribuzione di probabilità stimata, mostra scarse prestazioni. Inoltre, a causa della mancanza di algoritmi che si adattano bene al numero di stati, i metodi di esplorazione semplici sono i più pratici.
Uno di questi algoritmi è ε-greedy, dove 0 < ε < 1 è un parametro che controlla la quantità di esplorazione rispetto alla decisione. Con probabilità 1 − ε , viene scelto la decisione e l'agente sceglie l'azione che ritiene abbia il miglior effetto a lungo termine. In alternativa, con probabilità ε , si sceglie l'esplorazione e l'azione viene scelta in modo uniforme e casuale. ε è solitamente un parametro fisso ma può essere regolato secondo una pianificazione o in modo adattivo.
In generale l’obiettivo dei vari algoritmi è quello di utilizzare l'esperienza passata per scoprire quali azioni portano a ricompense cumulative più elevate, e scegliere una politica π (una funzione) che suggerisca l’azione da prendere quando il sistema è in un certo stato, politica che può essere deterministica o probabilistica:
Nel caso di politica probabilistica, essa fornisce la probabilità di intraprendere un’azione a quando ci si trova nello stato s.
Nel Blackjack, se le due sole azioni sono Hit o Stick e lo stato è costituito dal punteggio del giocatore e dalla carta visibile del dealer, quella che segue è una possibile politica.
Inoltre i vari algoritmi definiscono una funzione Vπ(s) che definisce il valore di uno stato alla luce della politica π, e che è definita come il rendimento scontato atteso a partire dallo stato s, ovvero S0 = s , e successivamente seguendo la politica π . Quindi, grosso modo, la funzione valore stima “quanto sia buono” trovarsi in un dato stato.
Consigliati da LinkedIn
Infine tutti concordano sulla definizione di guadagno finale G, dove la variabile casuale G denota il rendimento finale scontato ed è definita come la somma dei futuri premi (ricompense o rewards) scontati:
d ove R t + 1 è la ricompensa per la transizione dallo stato St a S t + 1 e γ è il tasso di sconto, con 0 ≤ γ < 1. γ è inferiore a 1, quindi le ricompense nel lontano futuro hanno un peso inferiore rispetto alle ricompense nell'immediato futuro.
L'algoritmo deve trovare una politica con il massimo rendimento scontato atteso G. Per essere precisi, una politica è ottimale se raggiunge il miglior rendimento scontato atteso a partire da qualsiasi stato iniziale. Dalla teoria dei processi decisionali markoviani è noto che, senza perdita di generalità, la ricerca può essere ristretta all'insieme delle cosiddette politiche stazionarie, quelle cioè in cui la distribuzione delle azioni restituita dipende solo dall'ultimo stato visitato. La ricerca può essere eventualmente ristretta alle politiche stazionarie deterministiche, che selezionano deterministicamente le azioni in base allo stato attuale.
L’algoritmo più primitivo è quello a forza bruta (Naive Exhaustive Search), in cui si prova a seguire ogni possibile politica, scegliendo quella con il rendimento scontato atteso maggiore. Ovviamente si ha una esplosione combinatoria se il numero di politiche è elevato o addirittura infinito. Inoltre la varianza delle ricompense può essere ampia, il che richiede molti campioni per stimare accuratamente il rendimento scontato di ciascuna politica. Migliore è certamente l’algoritmo di Pruning, che cerca possibili azioni, ma ricorda solo la serie di azioni migliori, ignorando i percorsi precedentemente scoperti con ricavi peggiori.
Gli algoritmi utilizzati fanno parte di diverse categorie:
I metodi Monte Carlo (MC) iterano le politiche attraverso i passi di valutazione di una politica e miglioramento di una politica e sono indipendenti da un modello dell’ambiente. Data una politica stazionaria e deterministica π, l'obiettivo è calcolare i valori della funzione Vπ(s, a) (o una buona approssimazione di essi) per tutte le coppie stato-azione (s ,a) . Gli episodi vengono iterati a partire da uno stato iniziale casuale e viene calcolata la media delle ricompense per ogni coppie stato-azione (s,a) usando la politica π. Quindi la politica viene migliorata cambiando per ogni stato s l’azione a prescelta come quella che massimizza Vπ(s,a). Questi metodi convergono lentamente e funzionano solo per processi piccoli.
I Metodi di Programmazione Dinamica di solito si riferiscono alla semplificazione di una decisione suddividendola in una sequenza di passaggi decisionali nel tempo. Questo viene fatto definendo una sequenza di funzioni valore V1, V2, ..., Vn che prendono un argomento x che rappresenta lo stato del sistema agli istanti i da 1 a n. La definizione di Vn(x) è il valore ottenuto nello stato x all'ultimo istante n. I valori Vi nei tempi precedenti i = n −1, n − 2, ..., 2, 1 possono essere trovati operando all'indietro, utilizzando una relazione ricorsiva chiamata equazione di Bellman. Per i = 2, ..., n, viene calcolato Vi−1 in qualsiasi stato x a partire da Vi massimizzando una funzione semplice (solitamente la somma) del guadagno derivante da una decisione al tempo i − 1 e la funzione Vi al nuovo stato del sistema se viene presa questa decisione. Poiché Vi è già stato calcolato per gli stati necessari, l’operazione di cui sopra produce Vi−1 per quegli stati. Infine, V1 allo stato iniziale del sistema è il valore della soluzione ottima. I valori ottimali delle variabili decisionali possono essere recuperati, uno per uno, rintracciando all’indietro i calcoli già eseguiti. Richiedono un MDP finito con conoscenza perfetta degli stati, azioni, ricompense e probabilità.
L'idea principale alla base dei Metodi di Differenza Temporale (TD) è che possiamo apprendere la funzione valore da ogni esperienza mentre un sistema si evolve nell'ambiente. Come i metodi Monte Carlo, i metodi TD apprendono dall’esperienza senza richiedere un modello dell’ambiente. Ma essi aggiornano la stima del valore ad ogni passo temporale, a differenza dei metodi Monte Carlo che aspettano fino alla fine di un episodio.
I Metodi di Approssimazione della Funzione cercano di approssimare la funzione Vπ(s, a) con tecniche lineari o non parametriche.
I Metodi di Ricerca Diretta della Politica cercano direttamente in un sottoinsieme dello spazio delle politiche, nel qual caso il problema diventa un caso di ottimizzazione stocastica.
I Metodi di Apprendimento del Modello dell’Ambiente attraverso esperienze ripetute tentano di imparare il modello dell’ambiente e quindi usano il modello appreso per calcolare la politica ottimale.
Oltre per la categoria di cui fanno parte, i vari algoritmi si distinguono anche per la funzione valore che usano (state-value, action-value o advantage value) e per il tipo di politica che provano a stimare (on-policy o off-policy). I metodi on-policy stimano il valore di una policy utilizzandola per il controllo. Nei metodi off-policy invece queste due funzioni sono separate. La politica utilizzata per generare il comportamento, chiamata politica comportamentale, può infatti non essere correlata alla politica che viene valutata e migliorata, chiamata politica target.
La funzione valore inizialmente più usata era la state-value, che associa un valore Vπ(s) ad uno stato s in una politica π. Poichè in uno stato è possibile prendere diverse azioni, la funzione valore action-value Vπ(s, a) associa in maniera più puntuale un valore ad una azione a decisa in uno stato s in una politica π. In quest’ottica, lo state-value è la media degli action-value di uno stato. Alcuni dei più recenti algoritmi usano l’advantage value, definita come la differenza tra l’action-value e lo state-value:
AVπ(s, a) = Vπ(s, a) – Vπ(s)
L’advantage value quindi sarebbe il vantaggio nel prendere la decisione a nello stato s rispetto a prendere una decisione casuale.
Una volta scelta la funzione valore, gli algoritmi tentano di trovare una politica che massimizzi il rendimento scontato. Per far questo calcolano una serie di stime dei rendimenti scontati attesi per una politica: alcuni lo fanno per quella "attuale" [on-policy] mentre altri lo fanno per quella ottimale [off-policy].
Gli algoritmi di apprendimento per rinforzo più comuni sono :
...
per saperne di più
su Amazon al link
e su Google Play libri al link