Q-learning

Questa voce o sezione sull'argomento informatica è ritenuta da controllare.

Motivo: Troppo tecnico

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 ${\displaystyle 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:

${\displaystyle 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.

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

La formula sopra è equivalente a:

${\displaystyle 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 ${\displaystyle s_{t+1}}$ è uno stato finale (o stato di assorbimento).

Notare che per tutti gli stati finali ${\displaystyle s_{f}}$, ${\displaystyle 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^[1].

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

Note

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

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Regole di associazione · Apprendimento non supervisionato · Apprendimento supervisionato · Apprendimento per rinforzo · Apprendimento profondo
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · Dbscan · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random fields · Modello di Markov nascosto · K-nearest neighbors · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Probabilistic graphical model · Macchine a vettori di supporto
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Selezione delle caratteristiche · Estrazione di caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Rete neurale a base radiale · Rete bayesiana · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · Torch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico

Portale Informatica

Portale Ingegneria

Portale Statistica