Q-learning

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

Motivo: Troppo tecnico

---

Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti del progetto di riferimento.

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.

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.

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.

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.

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.

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

• 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 CRF · Modello di Markov nascosto · K-nearest neighbors · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modelli grafici · Macchine a vettori di supporto
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della 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