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