Q-learning

Q-Learning: taula d'estats per accions que s'inicialitza a zero, després cada cel·la s'actualitza mitjançant l'entrenament.

Q-learning és un algorisme 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 per Chris Watkins el 1989. Watkins i Peter Dayan van presentar una prova de convergència el 1992.

Watkins parlava de "Learning from delayed rewards", el títol de la seva tesi 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. La matriu de memòria $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 en pseudocodi matemàtic al document, en cada iteració realitza el càlcul següent:

• A l'estat Plantilla:Mvar realitzar l'acció Plantilla:Mvar;
• Rebre estat de conseqüència Plantilla:Mvar;
• Calculeu l'avaluació de l'estat Plantilla:Tmath;
• Actualitza el valor de la barra transversal $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çant la retropropagació: el valor d'estat Plantilla:Tmath 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.

Per a qualsevol procé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. Q-learning pot identificar una política de selecció d'accions òptima per a qualsevol FMDP donat, donat un temps d'exploració infinit i una política parcialment aleatòria. "Q" es refereix a la funció que calcula l'algorisme: les recompenses esperades per una acció realitzada en un estat determinat.

Algorisme:

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

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

• $(1-\alpha )Q(s_t,a_t)$: el valor actual (ponderat per un menys la taxa d'aprenentatge).
• $\alpha r_t$: la recompensa per obtenir si acció es pren quan està en estat (ponderat per la taxa d'aprenentatge).
• $\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).

$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 $r_t$ és la recompensa rebuda quan es mou de l'estat $s_t$ a l'estat $s_{t+1}$, i $\alpha$ és la taxa d'aprenentatge $(0<\alpha \le 1)$ .