Q-learning

Nell'intelligenza artificiale , più precisamente nell'apprendimento automatico , il Q-learning è una tecnica di apprendimento per rinforzo . Questa tecnica non richiede alcun modello iniziale dell'ambiente . La lettera "Q" indica la funzione che misura la qualità di un'azione eseguita in un dato stato del sistema.

Descrizione

Questo metodo di apprendimento consente di apprendere una politica, che indica quale azione eseguire in ogni stato del sistema. Funziona apprendendo una nota funzione di valore dell'azione statale che determina il potenziale guadagno, cioè la ricompensa a lungo termine , portato dall'esecuzione di una determinata azione in un determinato stato seguendo una politica ottimale. Quando questa funzione del valore dello stato dell'azione è nota / appresa dall'agente, la politica ottimale può essere costruita selezionando l'azione del valore massimo per ogni stato, ovvero selezionando l'azione che massimizza il valore quando l'agente è nello stato . $Q$ ${\ displaystyle Q (s, a)}$ $a$ $S$ $a$ ${\ displaystyle Q (s, a)}$ $S$

Uno dei punti di forza di -learning è che rende possibile il confronto le ricompense probabili di prendere le azioni accessibili senza avere alcuna conoscenza iniziale dell'ambiente. In altre parole, sebbene il sistema sia modellato come un processo decisionale markoviano (finito), l'agente impara a non sapere e l'algoritmo - l' apprendimento non lo usa. $Q$ $Q$

Questa nozione di apprendimento tramite ricompensa è stata originariamente introdotta nella tesi di Watkins nel 1989. È una variante dell'apprendimento per differenza temporale. Successivamente, è stato dimostrato che - l' apprendimento converge verso una politica ottimale, vale a dire che porta a massimizzare la ricompensa totale delle fasi successive. $Q$

Algoritmo

La situazione consiste in un agente, un insieme di stati e azioni . Eseguendo un'azione , l'agente si sposta da uno stato a un nuovo stato e riceve una ricompensa (è un valore numerico). L'obiettivo dell'agente è massimizzare la sua ricompensa totale. Ciò si ottiene imparando l'azione ottimale per ogni stato. L'azione ottimale per ogni stato è quella con la maggiore ricompensa a lungo termine. Questa ricompensa è la somma ponderata dell'aspettativa matematica delle ricompense di ogni passo futuro dallo stato attuale. Il peso di ogni passaggio può essere dove si trova il ritardo tra il passaggio corrente e quello futuro e un numero compreso tra 0 e 1 (ovvero ) chiamato fattore di sconto . $S$ $A$ $a \ in A$ $S$ $S'$ $r$ ${\ displaystyle \ gamma ^ {\ Delta t}}$ $\ Delta t$ $\gamma$ ${\ displaystyle 0 \ leq \ gamma \ leq 1}$

L'algoritmo calcola una funzione del valore dello stato dell'azione:

{\ Displaystyle Q: S \ times A \ to \ mathbb {R}}

Prima che inizi l'apprendimento, la funzione viene inizializzata arbitrariamente. Quindi, con ogni scelta di azione, l'agente osserva la ricompensa e il nuovo stato (che dipende dallo stato precedente e dall'azione corrente). Il cuore dell'algoritmo è un aggiornamento della funzione valore . La definizione della funzione valore viene aggiornata ad ogni passo come segue: $Q$

{\ displaystyle Q [s, a]: = (1- \ alpha) Q [s, a] + \ alpha \ left (r + \ gamma \ max _ {a '} Q [s', a '] \ right )}

dove è il nuovo stato, è lo stato precedente, è l'azione scelta, è la ricompensa ricevuta dall'agente, è un numero compreso tra 0 e 1, chiamato fattore di apprendimento ed è il fattore di aggiornamento . $S'$ $S$ $a$ $r$ $\alfa$ $\gamma$

Un episodio dell'algoritmo finisce quando è uno stato finale. Tuttavia, - l'apprendimento può essere applicato anche alle attività non episodiche. Se il fattore di sconto è minore di 1, il valore dello stato dell'azione è finito anche per l' infinito. $s _ {{t + 1}}$ $Q$ $\ Delta t$

NB: Per ogni stato finale , il valore di non viene mai aggiornato e mantiene il suo valore iniziale. Di solito, è inizializzato a zero. ${\ displaystyle s_ {f}}$ ${\ displaystyle Q (s_ {f}, a)}$ ${\ displaystyle Q (s_ {f}, a)}$

Pseudo-codice

Ecco lo pseudo-codice di Q-learning.

initialiser Q[s, a] pour tout état s, toute action a de façon arbitraire, mais Q(état terminal, a) = 0 pour toute action a répéter //début d'un épisode initialiser l'état s répéter //étape d'un épisode choisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy) exécuter l'action a observer la récompense r et l'état s' Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)] s := s' a := a' jusqu'à ce que s soit l'état terminal

Influenza delle variabili sull'algoritmo

Fattore di apprendimento

Il fattore di apprendimento determina quanto le nuove informazioni calcolate supereranno quelle vecchie. Se = 0, l'agente non apprende nulla. Al contrario, se = 1, l'agente ignora sempre tutto ciò che ha appreso e prenderà in considerazione solo l'ultima informazione. $\alfa$ $\alfa$ $\alfa$

In un ambiente deterministico, la velocità di apprendimento è ottimale. Quando il problema è stocastico, l'algoritmo converge in determinate condizioni a seconda della velocità di apprendimento. In pratica, spesso questa velocità corrisponde a tutta la durata del processo. ${\ displaystyle \ alpha _ {t} (s, a) = 1}$ ${\ displaystyle \ alpha _ {t} (s, a) = 0,1}$

Fattore di sconto

Il fattore di sconto $γ$ determina l'entità delle ricompense future. Un fattore 0 renderebbe l'agente miope considerando solo le ricompense correnti, mentre un fattore vicino a 1 porterebbe anche le ricompense più distanti. Se il fattore di sconto è vicino o uguale a 1, il valore di può divergere. $Q$

Estensioni e varianti

Doppio Q- apprendimento

Poiché Q- learning utilizza lo stimatore massimo, Q- learning sovrastima il valore delle azioni e quindi, in ambienti rumorosi, l'apprendimento è lento. Questo problema è risolto nella variante chiamata double Q- learning che utilizza due funzioni di valutazione e apprende su due diversi set di esperienze. L'aggiornamento viene eseguito trasversalmente: ${\ displaystyle Q ^ {A}}$ ${\ displaystyle Q ^ {B}}$

{\ displaystyle Q_ {t + 1} ^ {A} (s_ {t}, a_ {t}) = Q_ {t} ^ {A} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma ~ Q_ {t} ^ {B} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max }} _ {a} Q_ {t} ^ {A} (s_ {t + 1}, a) \ right) -Q_ {t} ^ {A} (s_ {t}, a_ {t}) \ right) }

, e

{\ displaystyle Q_ {t + 1} ^ {B} (s_ {t}, a_ {t}) = Q_ {t} ^ {B} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma ~ Q_ {t} ^ {A} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max }} _ {a} Q_ {t} ^ {B} (s_ {t + 1}, a) \ right) -Q_ {t} ^ {B} (s_ {t}, a_ {t}) \ right) .}

Poiché il valore stimato viene valutato utilizzando un'altra politica, il problema della sovrastima è risolto. L'apprendimento dell'algoritmo dell'insieme può essere effettuato utilizzando tecniche di apprendimento profondo, che si traducono in DQN ( reti Q profonde ). Possiamo quindi avere Double DQN, per ottenere prestazioni migliori rispetto all'algoritmo DQN originale.

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato “ Q-Learning ” ( vedi l'elenco degli autori ) .

Tambet Matiisen , " Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab " , su neuro.cs.ut.ee ,19 dicembre 2015(visitato il 6 aprile 2018 )
CJ Watkins, Imparare dalle ricompense ritardate , Kings College, Cambridge, maggio 1989
(in) George F. Luger, Artificial Intelligence: Structures and Strategies for complex problem solving. 5a edizione. , Addison Wesley,2005, 903 p. ( ISBN 0-321-26318-9 , leggi online ) , p. 448
Watkins e Dayan, Q-learning. Machine Learning , 1992
(a) David L. Poole e Alan K. Mackworth , Artificial Intelligence , Cambridge University Press ,2009( ISBN 978-0-511-79479-7 , DOI 10.1017 / CBO9780511794797 , leggi online ) , p. 469
Apprendimento per rinforzo: un'introduzione , Richard Sutton e Andrew Barto, MIT Press, 1998.
(in) Stuart J. Russell e Peter Norvig , Artificial Intelligence: A Modern Approach , Prentice Hall ,2010, Terza ed. , 1132 p. ( ISBN 978-0-13-604259-4 ) , p. 649
Hado van Hasselt , " Double Q-learning ", Advances in Neural Information Processing Systems , vol. 23,2011, p. 2613–2622 ( leggi online [PDF] )
Hado van Hasselt , Arthur Guez e David Silver , " Deep reinforcement learning with double Q-learning ", AAAI Conference on Artificial Intelligence ,2015, p. 2094–2100 ( leggi online [PDF] )