Q-learning

Da Wikipedia, l'enciclopedia libera.

Q-learning è uno dei più conosciuti algoritmi di apprendimento per rinforzo. 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[modifica | modifica wikitesto]

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 learning~rate} \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 \le 1). Il fattore di sconto \gamma è tale che 0 \le \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[modifica | modifica wikitesto]

Learning Rate[modifica | modifica wikitesto]

Il learning rate 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[modifica | modifica wikitesto]

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 che tendente ad 1 renderà l'agente attento anche alle ricompense che riceverà in un futuro a lungo termine.

Implementazione[modifica | modifica wikitesto]

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 delle rete neurale artificiale come approssimatore di funzione.

Studi recenti[modifica | modifica wikitesto]

Q-learning fu inizialmente introdotto da Watkins[1] nel 1989.

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


Note[modifica | modifica wikitesto]

  1. ^ Watkins, C.J.C.H., (1989), Learning from Delayed Rewards. Ph.D. thesis, Cambridge University.
  2. ^ Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning', ISBN : 8:279-292

Collegamenti esterni[modifica | modifica wikitesto]