Q-Learning
- Introdotto da
- Christopher Watkins & Peter Dayan
- Anno
- 1992
- Tipo
- Model-free reinforcement-learning control algorithm
- Famiglia
- Reinforcement learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il Q-learning, introdotto da Christopher Watkins e Peter Dayan nel 1992, è un algoritmo di apprendimento per rinforzo (reinforcement learning) model-free che apprende il valore di intraprendere ogni azione in ogni stato — la funzione Q — puramente dall'esperienza, senza un modello dell'ambiente.
È off-policy: apprende i valori ottimali delle azioni seguendo una politica di comportamento esplorativa e, in condizioni standard, converge in modo dimostrabile alla politica ottimale.
L’intuizione alla base del metodo
Un agente che apprende per tentativi ed errori deve sapere, per ogni situazione, quanto sia buona ogni possibile azione a lungo termine. Il Q-learning mantiene esattamente questo: una tabella (o funzione) di valori Q che stima la ricompensa futura totale derivante dall'intraprendere un'azione in uno stato e comportarsi in modo ottimale in seguito. Ogni volta che l'agente agisce, osserva una ricompensa e si trova in un nuovo stato, sposta il valore Q verso ciò che ha appena sperimentato più il meglio che crede di poter fare successivamente. Fondamentalmente, si aggiorna verso la MIGLIORE azione successiva indipendentemente da ciò che ha effettivamente fatto dopo — in modo da poter esplorare liberamente pur continuando ad apprendere la strategia ottimale.
Storia
Christopher Watkins ha introdotto il Q-learning nella sua tesi del 1989, e Watkins e Dayan (1992) hanno fornito la prova di convergenza, stabilendolo come una pietra miliare dell'apprendimento per rinforzo. Generalizza l'apprendimento per differenza temporale al controllo e sta alla base di successivi traguardi — in particolare le Deep Q-Networks (Mnih et al., 2015), che hanno combinato il Q-learning con reti profonde per giocare ai giochi Atari dai pixel. È trattato canonicamente nel libro di testo di Sutton e Barto e rimane un punto di partenza predefinito per l'RL basato sul valore.
Quando usarlo
Utilizzare il Q-learning per problemi di decisione sequenziale formulati come un processo decisionale di Markov in cui è possibile campionare transizioni e ricompense ma non si dispone di un modello (o di un modello inaffidabile) delle dinamiche — controllo, giochi, routing, scheduling e sistemi adattivi. Il Q-learning tabulare è adatto a spazi di stato-azione piccoli e discreti e converge all'ottimo data sufficiente esplorazione e una dimensione del passo decrescente. Per spazi grandi o continui la tabella è sostituita da un approssimatore di funzione (Deep Q-Networks). Presuppone la proprietà di Markov e un ambiente stazionario, può essere inefficiente in termini di campioni e l'operatore max induce un bias ottimistico (di massimizzazione) affrontato da varianti come il Double Q-learning. Quando è necessaria una politica stocastica o ad azione continua, i metodi di gradiente di politica sono l'alternativa.
Limiti e considerazioni
- La forma tabulare non è scalabile per spazi di stato/azione grandi o continui.
- Inefficiente in termini di campioni; può richiedere molti episodi per convergere.
- Bias di massimizzazione (sovrastima) dall'operatore max; mitigato dal Double Q-learning.
- Presuppone un processo decisionale di Markov (stazionario); ha difficoltà in condizioni di osservabilità parziale o deriva.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Model-free: non necessita di un modello di transizione/ricompensa, solo di esperienza campionata.
- Off-policy: apprende la politica ottimale mentre esplora con un'altra politica.
- Converge in modo dimostrabile ai valori ottimali delle azioni in condizioni standard.
- Semplice, fondamentale e base per le Deep Q-Networks e molte estensioni.
Applicazioni
- Gioco e compiti di controllo simulato.
- Navigazione robotica e controllo adattivo.
- Routing dinamico, scheduling e allocazione delle risorse.
- Politiche di raccomandazione e interazione adattiva.
- Un metodo di base basato sul valore prima delle Deep Q-Networks.
Come funziona
Come funziona
Q(s, a) stima la somma attesa scontata delle ricompense future derivanti dall'intraprendere l'azione a nello stato s e quindi agire in modo ottimale. Il fattore di sconto γ pondera le ricompense vicine più di quelle distanti. L'apprendimento di Q per tutte le coppie stato-azione è equivalente alla risoluzione del problema di controllo.
Formula
Q(s,a) \approx \mathbb{E}\!\left[\textstyle\sum_{k\ge0}\gamma^{k} r_{t+k+1}\mid s_t=s,a_t=a\right]Dopo ogni transizione (stato s, azione a, ricompensa r, stato successivo s'), il Q-learning aggiorna Q(s, a) di un passo α verso il target di differenza temporale r + γ·max sulle azioni successive di Q(s', a'). Il 'max' è ciò che lo rende off-policy e indirizza l'apprendimento al valore ottimale, indipendentemente dall'azione effettivamente intrapresa successivamente.
Formula
Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big]Per raccogliere esperienza l'agente agisce con una politica di esplorazione, comunemente ε-greedy: di solito sceglie la migliore azione corrente, ma con probabilità ε ne sceglie una casuale. L'esplorazione assicura che tutte le coppie stato-azione vengano provate, cosa che la garanzia di convergenza richiede; ε tipicamente decade nel tempo.
Formula
a = \begin{cases}\arg\max_a Q(s,a) & \text{prob } 1-\epsilon\\ \text{random} & \text{prob } \epsilon\end{cases}Una volta che Q è convergente ai valori ottimali delle azioni Q*, la politica ottimale consiste semplicemente nel prendere, in ogni stato, l'azione con il valore Q più alto. In pratica, la politica greedy rispetto al Q corrente viene estratta alla fine (o utilizzata al momento dell'implementazione).
Formula
\pi^*(s) = \arg\max_a Q^*(s,a)
Errori comuni
- Esplorazione insufficiente (ε troppo piccolo/decaduto troppo velocemente), lasciando l'ottimo non appreso.
- Programmazione del tasso di apprendimento scadente, causando divergenza o apprendimento dolorosamente lento.
- Applicare il Q-learning tabulare a spazi grandi invece di un approssimatore di funzione.
- Ignorare il bias di sovrastima su problemi stocastici in cui il Double Q-learning è d'aiuto.
Domande frequenti
Cosa significa 'off-policy' nel Q-learning?
Significa che il Q-learning apprende il valore della politica ottimale mentre l'agente segue una politica di comportamento diversa (esplorativa). L'aggiornamento mira a r + γ·max Q(s', a') — la migliore azione successiva — non l'azione effettivamente intrapresa, quindi l'esplorazione non distorce l'ottimo appreso.
Come si relaziona il Q-learning alle Deep Q-Networks (DQN)?
DQN sostituisce la tabella Q con una rete neurale profonda che approssima Q(s, a), consentendo il Q-learning in spazi di stato grandi o continui (ad esempio, pixel). Aggiunge trucchi stabilizzanti — replay dell'esperienza e una rete target — ma la regola di apprendimento fondamentale è l'aggiornamento della differenza temporale del Q-learning.
Perché il Q-learning sovrastima i valori?
L'operatore max nell'aggiornamento tende a selezionare stime eccessivamente ottimistiche, distorcendo Q verso l'alto, specialmente con ricompense rumorose. Il Double Q-learning riduce questo disaccoppiando la selezione dell'azione dalla valutazione del valore utilizzando due stimatori, producendo politiche meno distorte e spesso migliori.
Metodi correlati
Fonti
Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3–4), 279–292.
Apri il riferimento DOICopiato.Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
ISBN: 978-0-262-03924-6Copiato.