In quest post esploriamo l’algoritmo di Temporal Difference Learning e quello di Q-Learning.
Nel nostro precedente post abbiamo visto come Bellman riusci a individuare un metodo efficace per calcolare l’optimal state value di ogni stato.
Conoscere questo valore è utile, in particolare per valutare una policy, ma non comunica espressamente all’agente cosa fare.
Bellman ci ha consegnato allora un secondo algoritmo, molto simile al Value Iteration Algorithm per stimare questa volta i valori ottimali di state-action, chiamati genericamente Q-values.
Oooh, e il primo termine andato.
Non proprio, comprendiamo meglio.
Q-Value
Definiamo con più precisione il Q-Value.
Il Q-Value ottimale per la coppia stato-azione (s,a), indicato come Q*(s,a) è la somma delle future ricompense scontate (i.e. Con applicazione del discount rate, spiegato in questo post) che l’agente può ricevere in media dopo aver raggiunto lo stato s e aver scelto l’azione a, ma prima di aver osservato il risultato dell’azione, assumendo che agisca in modo ottimale dopo l’azione.
Ancora una volta il processo è iterativo: dopo aver inizializzato i valori a zero li aggiorniamo attraverso il Q-Value Iteration algorithm.
Con i Q-Values ottimali, definire la policy ottimale, indicata come π*(s) è banale: quando l’agente si trova nello stato s, gli basta scegliere l’azione con il più alto Q-Value per lo stato corrente: π* (s) = argmax (a) Q*(s, a).
Temporal Difference Learning
I problemi di Reinforcement Learning con azioni discrete sono spesso modellati come processi decisionali di Markov, sebbene inizialmente:
- L’agente non sappia quali siano le probabilità di transizione attraverso gli stati;
- L’agente non sappia quali siano le ricompense future.
Questo implica che l’agente debba esplorare ogni possibile stato e transizione almeno una volta per conoscere la relativa ricompensa, ed esplorare le transizioni numerose volte per stimarne con precisione la probabilità.
Il Temporal Difference Learning (TD Learning) è molto simile al Value Iteration algorithm ma ottimizzato per tenere conto della conoscenza parziale che l’agente ha del MDP.
In generale assumiamo che l’agente conosca inizialmente solo i possibili stati e le azioni. Quindi, attraverso una exploration policy (e.g. Una policy completamente casuale) l’agente esplora il MDP e nel frattempo il TD Learning aggiorna la stima degli state values basandosi sulle transizioni e ricompense effettivamente osservate.
L’algoritmo di TD Learning ha molte somiglianze allo Stochastic Gradient Descent, in particolare la limitazione di gestire un solo campione alla volta.
Analogamente allo SGD, è poi necessario ridurre gradualmente il learning rate per assicurare la convergenza dell’algoritmo.
Per ogni stato s, l’algoritmo calcola la media mobile (running average) delle ricompense immediatamente ottenute lasciando o stato, nonché quelle attese, assumendo che agisca in modo ottimale.
Q-Learning
In modo simile a quanto visto prima, l’algoritmo di Q-Learning è un adattamento del Q-Value Iteration algorithm capace di gestire la situazione in cui le probabilità di transizione e le ricompense sono inizialmente sconosciute.
Per ogni coppia di stato-azione (s,a), l’algoritmo calcola la media mobile (running average) delle ricompense r che l’agente riceve lasciando lo stato s attraverso l’azione a, e quelle attese in futuro.
Poiché ci aspettiamo che la policy agisca in modo ottimale, prendiamo il valore massimo della stima dei Q-Value per il prossimo stato.
Applicando questo metodo, a patto che ci siano sufficienti iterazioni, l’algoritmo converge ai Q-Value ottimali.
Definiamo allora l’algoritmo un off-policy algorithm perché la policy allenata, non è quella eseguita.
Facendoci colpire dalla meraviglia di questo algoritmo, rimaniamo stupiti da come sia in grado d’imparare la policy ottimale semplicmente osservando un agente agire in modo casuale nell’ambiente.
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea.
