Q-learning

Q-learning è uno dei più conosciuti algoritmi di apprendimento per rinforzo. Fa parte della famiglia di algoritmi adottati nelle tecniche delle differenze temporali, relative ai casi di modelli a informazione incompleta. Uno dei suoi maggiori punti di rilievo consiste nell'abilità di comparare l'utilità aspettata delle azioni disponibili senza richiedere un modello dell'ambiente.

Descrizione

Il suo obiettivo è quello di permettere ad un sistema di apprendimento automatico di adattarsi all'ambiente che lo circonda migliorando la scelta delle azioni da eseguire. Per giungere a questo obiettivo, cerca di massimizzare il valore del successivo premio per sconto.

Il modello del problema può essere descritto da un agente, un insieme di stati S e un insieme di azione per stato A. Effettuando un'azione $a\in A$ l'agente si muove da uno stato ad un altro stato. Ogni stato fornisce all'agente una ricompensa (un numero reale o naturale). L'obiettivo dell'agente è quello di massimizzare la ricompensa totale. L'agente fa questo apprendendo quali sono le azioni ottimali associate ad ogni stato.

Quindi l'algoritmo è provvisto di una funzione per calcolare la Qualità di una certa coppia stato-azione:

$Q:S\times A\to \mathbb {R}$

Prima che l'apprendimento inizi, Q restituisce un valore fisso, scelto dal progettista. Poi, ogni volta che l'agente riceve una ricompensa (lo stato è cambiato) vengono calcolati nuovi valori per ogni combinazione stato-azione. Il cuore dell'algoritmo fa uso di un processo iterativo di aggiornamento e correzione basato sulla nuova informazione.

$Q(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\rm {vecchio~valore}}+\underbrace {\alpha _{t}(s_{t},a_{t})} _{\rm {tasso~di~apprendimento}}\times \left[\overbrace {\underbrace {R_{t+1}} _{\rm {ricompensa}}+\underbrace {\gamma } _{\rm {fattore~di~sconto}}\underbrace {\max _{a_{t+1}}Q(s_{t+1},a_{t+1})} _{\rm {valore~futuro~massimo}}} ^{\rm {valore~appreso}}-\underbrace {Q(s_{t},a_{t})} _{\rm {vecchio~valore}}\right]$,

dove $R_{t+1}$ è una ricompensa osservata dopo aver eseguito $a_{t}$ in $s_{t}$, e il tasso di apprendimento (o learning rate) è identificato da $\alpha _{t}(s,a)$ ($0<\alpha \leq 1$). Il fattore di sconto $\gamma$ è tale che $0\leq \gamma <1$

La formula sopra è equivalente a:

$Q(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})(1-\alpha _{t}(s_{t},a_{t}))+\alpha _{t}(s_{t},a_{t})[R_{t+1}+\gamma \max _{a_{t+1}}Q(s_{t+1},a_{t+1})]$

Un episodio dell'algoritmo termina quando lo stato $s_{t+1}$ è uno stato finale (o stato di assorbimento).

Notare che per tutti gli stati finali $s_{f}$, $Q(s_{f},a)$ non viene mai aggiornato e quindi conserva il suo valore iniziale.

Influenza delle variabili sull'algoritmo

Tasso di apprendimento

Il tasso di apprendimento determina con quale estensione le nuove informazioni acquisite sovrascriveranno le vecchie informazioni. Un fattore 0 impedirebbe all'agente di apprendere, al contrario un fattore pari ad 1 farebbe sì che l'agente si interessi solo delle informazioni recenti.

Fattore di sconto

Il fattore di sconto determina l'importanza delle ricompense future. Un fattore pari a 0 renderà l'agente "opportunista" facendo sì che consideri solo le ricompense attuali, mentre un fattore tendente ad 1 renderà l'agente attento anche alle ricompense che riceverà in un futuro a lungo termine.

Implementazione

Una semplice implementazione di Q-learning usa tabelle per memorizzare i dati. Tuttavia questo approccio perde fattibilità al crescere del livello di complessità del sistema. Una possibile soluzione a questo problema prevede l'uso di una rete neurale artificiale come approssimatore di funzione.

Studi recenti

Q-learning fu inizialmente introdotto da Watkins nel 1989.

La dimostrazione di convergenza fu presentata più tardi da Watkins e Dayan nel 1992.

Collegamenti esterni

• Q-Learning topic on Knol
• Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England., su cs.rhul.ac.uk.
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning, su portal.acm.org.
• Q-Learning by Examples, su people.revoledu.com.
• Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
• Connectionist Q-learning Java Framework, su elsy.gdan.pl. URL consultato il 16 marzo 2012 (archiviato dall'url originale il 25 febbraio 2012).
• Piqle: a Generic Java Platform for Reinforcement Learning, su sourceforge.net.
• Reinforcement Learning Maze, a demonstration of guiding an ant through a maze using Q-learning.
• Q-learning work by Gerald Tesauro, su research.ibm.com.
• Q-learning work by Tesauro Citeseer Link, su citeseer.comp.nus.edu.sg. URL consultato il 16 marzo 2012 (archiviato dall'url originale il 29 maggio 2008).
• Q-learning algorithm implemented in processing.org language, su github.com. URL consultato il 3 maggio 2019 (archiviato dall'url originale il 16 giugno 2009).