Aprenentatge per reforç

L'aprenentatge per reforç, o RL de l'anglès reinforcement learning, és una àrea de l'aprenentatge automàtic que desenvolupa agents que poden aprendre a triar les accions que han de realitzar en un entorn, simulat o real, per maximitzar una recompensa de forma autònoma. Més col·loquialment, l'aprenentatge de reforç estudia sistemes que interactuen amb el seu entorn i aprenen a triar les accions que funcionen millor automàticament.

Diagrama d'un procés d'aprenentatge de reforç.

És un dels tres paradigmes bàsics de l'aprenentatge automàtic, juntament amb l'aprenentatge supervisat i el no supervisat. A diferència d'aquestes altres dues aproximacions, però, a l'aprenentatge per reforç no se li subministra un conjunt de dades; aprèn a partir de la interacció amb l'entorn, que pot ser el món real o una simulació. Per dur a terme aquesta tasca hi ha nombrosos algorismes, que a grans trets es divideixen en algoritmes basats en model o sense model. Els primers disposen, o generen, un model matemàtic intern per decidir com actuar, l'AlphaZero n'és un exemple particularment famós. Per altra banda, els algorismes sense model relacionen directament l'estat amb la recompensa esperada, alguns dels exemples més populars són els algorismes DQN, A2C i DDPG.

L'aprenentatge de reforç té els seus orígens en dos altres camps d'investigació: l'aprenentatge animal i el control òptim. El primer estudia com els animals aprenen a relacionar-se amb el seu entorn amb el mètode d'assaig i error. Per altra banda, la segona àrea analitza el disseny de controladors que optimitzin el comportament d'un sistema dinàmic. Aquests dos camps de recerca es van començar a combinar a principis de la dècada dels 60, però no seria fins als 80 que s'establirien els fonaments actuals d'aquesta àrea. Recentment, la combinació dels mètodes d'aprenentatge per reforç amb aprenentatge profund ha permès resoldre tasques complexes i se n'ha popularitzat l'ús en molts tipus d'aplicacions, com la robòtica o les finances.

Conceptes clau

Els principals aspectes de l'aprenentatge de reforç són l'agent i l'entorn. L'agent és l'entitat controlada per l'algorisme d'aprenentatge per reforç; pot ser real, per exemple un robot, o pot ser simulat, com un personatge de videojoc. Per altra banda, l'entorn és l'espai amb el qual l'agent interacciona, que també pot ser real o simulat. A cada pas de la interacció l'agent obté, sovint parcialment, una observació de l'estat de l'entorn, i a partir d'això decideix quines accions prendre. L'entorn canvia quan l'agent hi actua, però també pot canviar sense intervenció per part de l'agent.

Els videojocs clàssics de les màquines recreatives i l'Atari 2600, com l'Space Invaders, s'han fet servir darrerament per comparar diferents algorismes d'aprenentatge per reforç.

L'agent també percep un senyal de recompensa de l'entorn, un nombre que determina com de bo o dolent és l'estat en cada moment. L'objectiu de l'agent és maximitzar la recompensa acumulada, anomenada retorn. Els mètodes d'aprenentatge per reforç permeten a l'agent d'aprendre comportaments per assolir aquest objectiu.

Estats i observacions

Un estat s és la descripció completa de les característiques rellevants de l'entorn. No hi ha cap informació important que no estigui descrita per l'estat. Una observació o és una descripció parcial de l'estat, que pot ometre certa informació rellevant. En aprenentatge per reforç, els estats i observacions se solen representar amb vectors, matrius o tensors d'alt ordre amb valors reals.

Per exemple, l'estat d'un robot industrial podria descriure la posició de cada element del manipulador. Per altra banda, s'obtindria una observació si un sensor s'espatllés i no es tingués tota la informació de la posició del robot. Quan un agent pot observar la totalitat de l'estat es diu que l'entorn és totalment observat. Per contra, quan l'agent només té accés a una observació parcial es diu que l'entorn és parcialment observat.

Accions

Les accions són qualsevol interacció que l'agent pot realitzar amb l'entorn. El conjunt de totes les accions vàlides en un entorn sovint s'anomena espai d'accions. Alguns entorns, com els populars videojocs de l'Atari 2600, tenen un espai d'accions discret, l'agent té un nombre limitat d'accions. En d'altres casos l'espai d'accions és continu, quan són vectors amb valors reals, i el nombre d'accions és pràcticament il·limitat, com els moviments que pot dur a terme un robot industrial. Aquesta distinció té profundes conseqüències en els mètodes d'aprenentatge per reforç que es poden aplicar. Hi ha algorismes que només es poden aplicar en un o altre dels casos, o en ambdós.

Polítiques

Una política és la regla o conjunt de normes que un agent fa servir per decidir quina acció ha de prendre tenint en compte el seu estat actual. Aquesta política pot ser determinista, representada amb la notació $\mu$, o estocàstica, de notació $\pi$. Així doncs, l'acció que l'agent triarà depèn de l'estat actual i d'una política determinista o estocàstica que es pot representar, respectivament, amb la següent formulació:

$a_{t}=\mu (s_{t})$

$a_{t}=\pi (\cdot |s_{t})$

Les polítiques són funcions computables que depenen d'un conjunt de paràmetres, que s'ajusten amb algun tipus d'algorisme d'optimització per aconseguir el millor comportament possible. Els paràmetres emprats per la política sovint es representen a la notació com, $\theta$ o $\phi$.

Trajectòries

Una trajectòria o episodi, $\tau$, és la seqüència d'estats i accions que un agent ha experimentat en una seqüència de passos discrets $t=0,1,2,3...$:

$\tau =(s_{0},a_{0},s_{1},a_{1}...)$

El primer estat de l'entorn, $s_{0}$, és mostrejat aleatòriament de la distribució d'estats d'inici, que sovint té la notació $\rho _{0}$:

$s_{0}\sim \rho _{0}(\cdot )$

Les transicions d'estat són els canvis a l'entorn entre l'estat a temps t, $s_{t}$, i l'estat a temps t+1, $s_{t+1}$. Aquestes transicions d'estat estan governades per les lleis de l'entorn i l'acció més recent duta a terme per l'agent, $a_{t}$. Les transicions d'estat poden ser deterministes o estocàstiques, respectivament:

$s_{t+1}=f(s_{t},a_{t})$

$s_{t+1}\sim P(\cdot |s_{t},a_{t})$

Recompenses

La funció de recompensa, $R$, és crucial en l'aprenentatge per reforç. Aquesta funció determina la recompensa que se li atorgarà a l'agent depenent de l'estat actual de l'entorn, l'acció presa i el posterior estat de l'entorn.

$r_{t}=R(s_{t},a_{t},s_{t+1})$

La recompensa sovint se sol simplificar a la parella estat-acció $r_{t}=R(s_{t},a_{t})$ o, fins i tot, simplement a l'estat $r_{t}=R(s_{t})$.

L'objectiu de l'agent és maximitzar la recompensa acumulada al llarg de tota la trajectòria, sovint anomenat retorn. La notació del retorn, la recompensa acumulada a través de la trajectòria, és $R(\tau )$, i n'hi ha diferents tipus. El retorn sense descompte d'horitzó finit és la suma de totes les recompenses obtingudes en una finestra de temps fixa:

$R(\tau )=\sum _{t=0}^{T}r_{t}$

El retorn amb descompte d'horitzó infinit és la suma de totes les recompenses obtingudes per l'agent, amb un cert descompte que penalitza obtenir recompenses. Aquesta formulació de la retorn inclou un factor de descompte $\gamma \in (0,1)$:

$R(\tau )=\sum _{t=0}^{\infty }\gamma ^{t}r_{t}$

El factor de descompte, intuïtivament, és útil perquè prioritza que l'agent obtingui recompenses ràpidament. Matemàticament, en un horitzó infinit, la suma de recompenses pot no convergir a un valor finit i és difícil de resoldre amb equacions. En canvi, amb un factor de descompte i amb unes condicions raonables, la suma infinita convergeix.

El problema de l'aprenentatge per reforç

Sigui quina sigui la mesura de retorn, l'objectiu en l'aprenentatge per reforç és aprendre una política que maximitzi el retorn esperat quan l'agent actua a l'entorn. Suposant que les transicions de l'entorn i les polítiques són estocàstiques, la probabilitat d'una trajectòria de T passos és:

$P(\tau |\pi )=\rho _{0}(s_{0})\prod _{t=0}^{T-1}P(s_{t+1}|s_{t},a_{t})\pi (a_{t}|s_{t})$

El retorn esperat d'aquesta trajectòria, denotat per $J(\pi )$ seria:

$J(\pi )=\int _{\tau }P(\tau |\pi )R(\tau )=\mathbb {E} _{\tau \sim \pi }[R(\tau )]$

L'objectiu de l'aprenentatge per reforç és aconseguir una política que maximitzi aquest retorn esperat, la política òptima $\pi ^{*}$. Així doncs, el problema de l'aprenentatge per reforç és trobar aquesta política òptima:

$\pi ^{*}=\arg \max _{\pi }J(\pi )$

Exploració

Els problemes d'exploració contra explotació s'han estudiat profundament a partir del problema de la màquina escurabutxaques i per als MDPs amb un espai d'estats finit a Burnetas i Katehakis (1997).

L'aprenentatge reforçat requereix mecanismes d'exploració intel·ligents; la selecció aleatòria d'accions, sense referència a una distribució de probabilitat estimada, mostra un rendiment deficient. El cas dels MDPs (petits) finits està relativament ben entès. No obstant això, a causa de la falta d'algorismes que s'escalin bé amb el nombre d'estats (o es puguin aplicar a problemes amb espais d'estats infinits), els mètodes simples d'exploració són els més pràctics.

Un d'aquests mètodes és el $\varepsilon$-greedy, on $0<\varepsilon <1$ és el paràmetre que controla la quantitat de exploració vs. explotació. Amb una probabilitat d'$1-\varepsilon$, es tria l'explotació, i l'agent escull l'acció que creu que té el millor efecte a llarg termini (empats entre accions es desempaten de manera uniforme i aleatòria). Alternativament, amb probabilitat $\varepsilon$, s'escull l'exploració, i l'acció s'escull de manera uniforme i aleatòria. Normalment $\varepsilon$ és un parametre fix, però pot ser ajustat, sigui a partir d'un schedule (fent que l'agent explori progressivament menys) o adaptativament, basat en heurístiques.

Algoritmes per a l'aprenetatge per reforç

Fins i tot si la qüestió de l'exploració es deixa de costat i si l'estat és observable (suposada posteriorment), el problema segueix utilitzant l'experiència passada per esbrinar quines accions condueixen a recompenses acumulatives més altes.

Criteri d'optimització

Política

La selecció d'acció de l'agent es modela com un mapa anomenat política:

$\pi :A\times S\rightarrow [0,1]$

$\pi (a,s)=Pr(a_{t}=a|s_{t}=s)$

El mapa de polítiques dóna la probabilitat de prendre mesures a quan són en estat s. També hi ha polítiques deterministes

Funció estat-valor

La funció estat-valor $V_{\pi }(s)$ es defineix com, s'espera un retorn que comenci per l'estat s, i.e. $s_{0}=s,$ i seguint successivament la política $\pi$. Per tant, parlant més o menys, la funció valor estima "com de bo" es estar en un estat donat.

$V_{\pi }(s)=E[R|s_{0}=s]=E[\sum _{t}^{\infty }\gamma ^{t}r_{t}|s_{0}=s],$

on la variable aleatòria $R$ denota el retorn, i es defineix com el sumatori de les futures recompenses amb descompte

$R[\sum _{t}^{\infty }\gamma ^{t}r_{t}]$,

On $r_{t}$ es la recompensa al pas t, $\gamma \in [0,1)$ és la taxa de descompte. Gamma és inferior a 1, de manera que els esdeveniments en un futur llunyà tenen un pes menor que els esdeveniments en un futur immediat.

L'algoritme busca una política amb el màxim retorn esperat. A partir de la teoria de MDPs, és sap que, sense perdre generalitat, la cerca pot ser restrictiva amb el conjunt de polítiques estacionàries. Una política és estacionària si la distribució d'accions retornada depèn únicament de l'últim estat visitat (de l'historial d'observacions de l'agent). La cerca es pot restringir a més a les polítiques deterministes estacionàries. Una política estacionaria determinista selecciona accions basades en l'estat actual. Com que qualsevol política d'aquest tipus pot ser identificada com una aplicació del conjunt d'estats al conjunt d'accions, aquestes polítiques es poden identificar amb aquestes assignacions sense pèrdua de generalitat.

Força Bruta

L'enfocament de la força bruta comporta dos passos:

• Per a cada política possible, retorna mentre el segueix
• Trieu la política amb el retorn esperat més gran

Un problema és que el nombre de polítiques pot ser gran, o fins i tot infinit. Una altra és que la variància dels retorns pot ser gran, el que requereix moltes mostres per estimar amb precisió el retorn de cada política.

Aquests problemes poden millorar-se si assumim alguna estructura i permetem que les mostres generades a partir d'una política influeixin en les estimacions fetes per a unes altres. Els dos enfocaments principals per aconseguir-ho són l'estimació de funcions de valor i la cerca de polítiques directes.

Algorismes basats en models

Finalment, tots els mètodes anteriors es poden combinar amb algorismes que primer aprenen un model. Per exemple, l'algoritme Dyna aprèn un model a partir de l'experiència, i s'utilitza per proporcionar transicions més modelades per a una funció de valor, a més de les transicions reals. De vegades, aquests mètodes es poden estendre a l'ús de models no paramètrics, com quan les transicions simplement s'emmagatzemen i es tornen a 'reproduir' a l'algoritme d'aprenentatge.

Hi ha altres maneres d'utilitzar models que actualitzar una funció de valor. Per exemple, en el model de control predictiu s'utilitza per actualitzar el comportament directament.

Bibliografia

• Dayan, Peter; Yael, Niv «Reinforcement learning: the good, the bad and the ugly.». Current opinion in neurobiology, 2008, p. 12 [Consulta: 23 febrer 2020].
• François-Lavet, Vincent; Henderson, Peter; Islam, Riashat; Bellemare, Marc G.; Pineau, Joelle. «An Introduction to Deep Reinforcement Learning» p. 106, 2018. DOI: 10.1561/2200000071. [Consulta: 15 agost 2019].
• Graesser, Laura; Loon Keng, Wah. Foundations of Deep Reinforcement Learning. Theory and Practice in Python. Pearson Addison-Wesley, 2020, p. 379. ISBN 978-0-13-517238-4 [Consulta: 10 juliol 2020]. 
• Izquierdo, L.R.; Izquierdo, S.S. «Reinforcement Learning». Encyclopedia of the Sciences of Learning. Springer., 2012. [Consulta: 26 desembre 2019].
• Kaelbling, Leaslie Pack; Littman, Michael L.; Moore, Andrew W. «Reinforcement Learning: A Survey». Journal of Artificial Intelligence Research 4, 1996, p. 237-285 [Consulta: 24 febrer 2020].
• Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Bellemare, Marc G.; Graves, Alex; Riedmiller, Martin; Fidjeland, Andreas K.; Ostrovski, Georg; Petersen, Stig; Beattie, Charles; Sadik, Amir; Antonoglou, Ioannis; King, Helen; Kumaran, Dharshan; Wierstra, Daan; Legg, Shane; Hassabis, Demis «Human-level control through deep reinforcement learning». Nature, 2015, p. 529–533 [Consulta: 15 agost 2019].
• Sutton, Richard S.; Barto, Andrew G. Reinforcement Learning. An introduction. Cambridge, Massachusetts: The MIT Press, 2018, p. 526. ISBN 978-0-262-19398-6 [Consulta: 8 febrer 2020]. 
• Torra i Reventós, Vicenç. Fonaments d'intel·ligència artificial. Editorial UOC, 2007, p. 456. ISBN 9788497886062 [Consulta: 15 agost 2019]. 

Enllaços externs

• Recull de materials sobre aprenentatge per reforç a Github (anglès)
• Curs sobre aprenentatge per reforç de la Universitat de Berkeley a Youtube (anglès)