Q-learning és unalgorisme d'aprenentatge de reforçsense models per aprendre el valor d'una acció en un estat particular. No requereix un model de l'entorn (per tant, "sense model"), i pot gestionar problemes amb transicions i recompenses estocàstiques sense requerir adaptacions.

Q-learning va ser introduït perChris Watkins el 1989.^[1] Watkins iPeter Dayan van presentar una prova de convergència el 1992.^[2]

Watkins parlava de "Learning from delayed rewards", el títol de la sevatesi doctoral. Vuit anys abans, el 1981, el mateix problema, sota el nom d'"aprenentatge de reforç retardat", va ser resolt pel Crossbar Adaptive Array (CAA) de Bozinovski.^[3][4] La matriu de memòria${\displaystyle W=\Vert w(a,s)\Vert }$ era el mateix que la taula Q de Q-learning vuit anys més tard. L'arquitectura va introduir el terme "avaluació de l'estat" en l'aprenentatge de reforç. L'algorisme d'aprenentatge de barres transversals, escrit enpseudocodi matemàtic al document, en cada iteració realitza el càlcul següent:

• A l'estats realitzar l'accióa;
• Rebre estat de conseqüèncias';
• Calculeu l'avaluació de l'estat${\displaystyle v(s^{\prime })}$;
• Actualitza el valor de la barra transversal${\displaystyle w^{\prime }(a,s)=w(a,s)+v(s^{\prime })}$.

El terme "reforç secundari" es pren en préstec de la teoria de l'aprenentatge animal, per modelar els valors d'estat mitjançantla retropropagació: el valor d'estat${\displaystyle v(s^{\prime })}$ de la situació conseqüent es retropropaga a les situacions anteriorment trobades. CAA calcula els valors d'estat verticalment i les accions horitzontalment (la "barra transversal"). Els gràfics de demostració que mostraven l'aprenentatge de reforç retardat contenien estats (estats desitjables, indesitjables i neutres), que van ser calculats per la funció d'avaluació d'estats. Aquest sistema d'aprenentatge va ser un precursor de l'algoritme Q-learning.^[5]

Per a qualsevolprocés de decisió de Markov finit (FMDP),Q-learning troba una política òptima en el sentit de maximitzar el valor esperat de la recompensa total en tots els passos successius, començant per l'estat actual.^[6]Q-learning pot identificar una política deselecció d'accions òptima per a qualsevol FMDP donat, donat un temps d'exploracióinfinit i una política parcialment aleatòria.^[6] "Q" es refereix a la funció que calcula l'algorisme: les recompenses esperades per una acció realitzada en un estat determinat.^[7]

Algorisme:

El nucli de l'algorisme és unaequació de Bellman com aactualització simple d'iteració de valors, utilitzant la mitjana ponderada del valor actual i la nova informació:

Cal tenir en compte que${\displaystyle Q^{new}(s_t,a_t)}$ és la suma de tres factors:

• ${\displaystyle (1-\alpha )Q(s_t,a_t)}$: el valor actual (ponderat per un menys la taxa d'aprenentatge).
• ${\displaystyle \alpha r_t}$: la recompensa per obtenir si acció es pren quan està en estat (ponderat per la taxa d'aprenentatge).
• ${\displaystyle \alpha \gamma \underset{a}{max}Q(s_{t+1},a)}$: la màxima recompensa que es pot obtenir de l'estat (ponderat per la taxa d'aprenentatge i el factor de descompte).

${\displaystyle Q^{new}(s_t,a_t)\leftarrow \underset{\text{current value}}{\underbrace{Q(s_t,a_t)}}+\underset{\text{learning rate}}{\underbrace{\alpha }}\cdot \stackrel{\text{temporal difference}}{\overbrace{(\underset{\text{new value (temporal difference target)}}{\underbrace{\underset{\text{reward}}{\underbrace{r_t}}+\underset{\text{discount factor}}{\underbrace{\gamma }}\cdot \underset{\text{estimate of optimal future value}}{\underbrace{\underset{a}{max}Q(s_{t+1},a)}}}}-\underset{\text{current value}}{\underbrace{Q(s_t,a_t)}})}}}$on${\displaystyle r_t}$ és la recompensa rebuda quan es mou de l'estat${\displaystyle s_t}$ a l'estat${\displaystyle s_{t+1}}$, i${\displaystyle \alpha }$ és lataxa d'aprenentatge .

• Aprenentatge automàtic