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.^[1] Watkins i Peter Dayan van presentar una prova de convergència el 1992.^[2]

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.^[3][4] La matriu de memòria ${\displaystyle W=\|w(a,s)\|}$ 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 s realitzar l'acció a;
• Rebre estat de conseqüència s';
• Calculeu l'avaluació de l'estat ${\displaystyle v(s')}$;
• Actualitza el valor de la barra transversal ${\displaystyle w'(a,s)=w(a,s)+v(s')}$.

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 ${\displaystyle v(s')}$ 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 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.^[6] 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.^[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 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 ${\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 \max _{a}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 \underbrace {Q(s_{t},a_{t})} _{\text{current value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}-\underbrace {Q(s_{t},a_{t})} _{\text{current value}}{\bigg )}} ^{\text{temporal difference}}}$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 la taxa d'aprenentatge ${\displaystyle (0<\alpha \leq 1)}$ .

Referències

1. «learning from delayed rewards» (en anglès). https://www.cs.rhul.ac.uk.+[Consulta: 31 desembre 2022].
2. Watkins, Chris; Dayan, Peter Machine Learning, 8, 3–4, 1992, pàg. 279–292. DOI: 10.1007/BF00992698 [Consulta: free].
3. Bozinovski, S. «[Q-learning, p. 320-325, a Google Books Crossbar Adaptive Array: The first connectionist network that solved the delayed reinforcement learning problem]». A: Dobnikar. Artificial Neural Nets and Genetic Algorithms: Proceedings of the International Conference in Portorož, Slovenia, 1999 (en anglès). Springer Science & Business Media, 15 juliol 1999, p. 320–325. ISBN 978-3-211-83364-3. 
4. Bozinovski, S. «[Q-learning, p. 397, a Google Books A self learning system using secondary reinforcement]». A: Trappl. Cybernetics and Systems Research: Proceedings of the Sixth European Meeting on Cybernetics and Systems Research (en anglès). North Holland, 1982, p. 397–402. ISBN 978-0-444-86488-8. 
5. Barto, A. «[Q-learning a Google Books Reinforcement learning]». A: Omidvar. Neural Systems for Control (en anglès). Elsevier, 24 febrer 1997. ISBN 978-0-08-053739-9. 
6. Melo, Francisco S. Convergence of Q-learning: a simple proof.
7. Matiisen, Tambet. «Demystifying Deep Reinforcement Learning» (en anglès). neuro.cs.ut.ee. Computational Neuroscience Lab, 19-12-2015. [Consulta: 6 abril 2018].