Com aplicar l'aprenentatge de reforç a problemes de planificació de la vida real

Recentment he publicat alguns exemples on he creat models d'aprenentatge de reforç d'alguns problemes del món real. Exemple: fer servir l’aprenentatge de reforç per planificar els àpats en funció d’un pressupost fixat i de les preferències personals.

L’aprenentatge de reforç es pot utilitzar d’aquesta manera per a diversos problemes de planificació, inclosos els plans de viatges, la planificació pressupostària i l’estratègia comercial. Els dos avantatges de RL són que té en compte la probabilitat de resultats i ens permet controlar parts de l’entorn. Per això, vaig decidir escriure un exemple senzill perquè altres poguessin pensar en com començar a resoldre alguns dels seus problemes quotidians o de treball.

Què és l’aprenentatge de reforç?

L’aprenentatge de reforç (RL) és el procés de comprovació de les accions més adequades per a cada estat d’un entorn, bàsicament mitjançant proves i errors. El model introdueix una política d’inici aleatòria i cada vegada que es fa una acció s’afegeix al model una quantitat inicial (anomenada recompensa). Això continua fins que s’assoleix un objectiu final, per exemple. Guanyeu o perdeu el joc si finalitza aquesta cursa (o episodi) i es restableix el joc.

A mesura que el model passa per cada vegada més episodis, comença a saber quines accions tenen més probabilitats de produir un resultat positiu. Per tant, troba les millors accions en un estat determinat, anomenada pauta òptima.

Procés general d'aprenentatge de reforç

Moltes de les aplicacions RL entrenen models en línia en un entorn de joc o virtual on el model pot interactuar repetidament amb l’entorn. Per exemple, deixeu que el model reprodueixi una simulació de tic-tac-toe una i altra vegada per tal d’observar l’èxit i el fracàs en provar diferents moviments.

A la vida real, probablement no tenim accés a formar el nostre model d’aquesta manera. Per exemple, quan es fa una compra en línia, un sistema de referència necessita els comentaris d'una persona per dir-nos si ha tingut èxit o no, i la seva disponibilitat és limitada en funció del nombre d'usuaris que interactuen amb el lloc web de compres.

En canvi, és possible que tinguem dades de mostra que mostrin les tendències de compra durant un període de temps i que puguem utilitzar per crear probabilitats estimades. Amb aquests podem crear el que es coneix com a procés de decisió Markov parcialment observat (POMDP) ​​per tal de generalitzar la distribució de probabilitat subjacent.

Processos de presa de decisions (POMDP) ​​de Markov parcialment observats

Els processos de decisió de Markov (MDP) proporcionen un marc per modelar la presa de decisions en situacions en què els resultats són en part aleatoris i en part sota el control d’un decisor. La característica principal dels MDP és que segueixen la propietat Markov. Tots els estats futurs són independents del passat donat el present. En altres paraules, la probabilitat d'anar al següent estat només depèn de l'estat actual.

Els POMDP funcionen de manera similar, tret que es tracta d’una generalització dels MDP. En resum, això significa que el model no pot interactuar simplement amb l’entorn, sinó que rep una distribució de probabilitat fixa en funció del que hem observat. Podeu trobar més informació aquí. Podríem fer servir mètodes d’iteració de valor al nostre POMDP, però en aquest cas vaig triar Monte Carlo Learning.

Entorn de mostra

Imagineu que heu tornat (o potser encara esteu) a l’escola a l’aula. El professor té unes pautes estrictes sobre els residus de paper i requereix que se li lliurin tots els trossos de paper a la part davantera de l’aula i que hi posi les escombraries a la paperera.

No obstant això, a alguns estudiants de la classe no els importa molt les regles del professor i prefereixen estalviar-se la molèstia de passar el diari per l’aula. En canvi, aquestes molèsties poden optar per llançar remotament els residus de paper a les escombraries. Ara això molesta el professor i els qui ho facin seran castigats.

Això introdueix un concepte molt bàsic de recompensa a l’acció i tenim un exemple de configuració d’aula com es mostra a la figura següent.

El nostre objectiu és trobar la millor instrucció per a cada persona perquè el paper arribi al professor i entri a la brossa i impedeixi tirar-lo a la brossa.

Estats i accions

Al nostre entorn, cada persona es pot veure com un estat i té diverses mesures que pot prendre amb els residus de paper. Podeu optar per passar-ho a un company veí, agafar-lo o tirar-lo a la brossa. Per això, podem assignar el nostre entorn a un disseny de quadrícula més estàndard, com es mostra a continuació.

Està dissenyat intencionadament perquè qualsevol persona o estat pugui fer quatre accions: amunt, avall, esquerra o dreta. Depenent de qui va dur a terme l'acció, cada acció té un resultat diferent a la "vida real". Una acció que la persona enganxa a una paret (inclòs el bloc negre al mig) indica que la persona s’aguanta al paper. En alguns casos, aquesta acció es duplica, però no és un problema al nostre exemple.

Per exemple, les accions de la persona A tenen com a resultat:

  • Pujar = tirar a la paperera
  • Part inferior = Mantingueu el paper fermament
  • Enllaços = reenviament a la persona B
  • Dreta = Mantingueu el paper

Entorn probabilista

Ara mateix som els responsables de la presa de decisions que controlen parcialment el medi ambient. Direm a cada persona quines accions cal fer. Això es coneix com a política.

El primer repte de l’aprenentatge és entendre que l’entorn és probable que sigui probabilístic i el que significa. En un entorn probabilístic, quan dirigim un estat a actuar com a part de la nostra política, és probable que es segueixi amb èxit. Dit d’una altra manera, si donem instruccions a la persona A que doni el paper a la persona B, pot optar per no seguir les mesures descrites a la nostra política i llençar els residus de paper a les escombraries.

Un altre exemple és quan recomanem comprar productes en línia, no es garanteix que la persona en vegi cadascun.

Probabilitats de transició observades

Per tal de determinar les probabilitats de transició observades, cal recollir algunes dades de mostra sobre el comportament de l’entorn. Abans de recopilar informació, proporcionem primer una pauta inicial. Per iniciar el procés, en vaig triar un a l’atzar que semblés que donaria un resultat positiu.

Ara estem veient l’acció que fa cada persona en funció d’aquesta política. Dit d’una altra manera, diguem que ens vam asseure al fons de l’aula i vam veure la classe i observar els resultats següents per a la persona A:

Accions observades de la persona A.

Veiem que un tros de paper va passar per aquesta persona 20 vegades; La van aguantar 6 vegades, la van passar 8 vegades a la persona B i la van tirar a la brossa 6 vegades més. Això vol dir que, segons la nostra pauta inicial, la probabilitat que aquesta persona mantingui la brossa o la llenci a la brossa és de 6/20 = 0,3 i també de 8/20 = 0,4 per transmetre-la a la persona B. Podem veure com la resta de la classe recull les dades de mostra següents:

Resultat observat a la vida real

De la mateixa manera, calculem les probabilitats com a matriu següent i podríem utilitzar-la per simular l'experiència. La precisió d’aquest model depèn en gran mesura de si les probabilitats són representacions reals de tot l’entorn. Dit d’una altra manera, hem d’assegurar-nos que disposem d’una mostra gran i rica en dades.

Funció de probabilitat de transició observada

Bandolers multi-armats, episodis, recompenses, taxes de retorn i descompte

Per tant, hem estimat les nostres probabilitats de transició a partir de les dades de mostra en un POMDP. El següent pas abans d’introduir models és introduir recompenses. Fins ara només hem discutit el resultat de l’últim pas. O bé el paper es posa a la brossa pel professor i es premia amb una recompensa positiva, o bé es llença amb A o M i es premia amb una recompensa negativa. Aquesta recompensa final que posa fi a l'episodi es diu Terminal Reward.

Tot i això, també hi ha un tercer resultat que tampoc no és òptim. El paper es passa constantment i mai arriba a les escombraries (o triga molt més del que voldríem). En resum, tenim tres resultats finals

  • El professor posa el paper a la brossa i rep una recompensa final positiva
  • Un alumne llença paper a la brossa i rep una recompensa final negativa
  • El paper es passa constantment per la sala o s’enganxa als estudiants durant més temps del que voldríem

Per evitar que el paper es llanci a les escombraries, estem donant una gran recompensa negativa, com ara: B. -1, i com que el professor està content de tirar-lo a la brossa, rep una gran recompensa positiva, +1. Per evitar que es transmeti per la sala tot el temps, establim la recompensa per a totes les altres accions a un valor negatiu petit, per exemple. B. -0.04.

Si establim això com a número positiu o zero, el model pot deixar que el paper vagi, ja que seria millor obtenir petits resultats positius que arriscar-se a aproximar-se al resultat negatiu. Aquest nombre també és molt petit, ja que només obté una única recompensa final, però pot passar molts passos perquè finalitzi l’episodi i ens hem d’assegurar que el resultat positiu no es cancel·li quan es llença el paper a la paperera.

Tingueu en compte que les recompenses sempre són relatives entre si i he triat números arbitraris, però es poden canviar si els resultats no són els desitjats.

Tot i que hem parlat accidentalment d’episodis a l’exemple, encara hem de definir-los formalment. Un episodi és simplement les accions que realitza cada article de l’aula per arribar a la paperera, que és l’estat final i finalitza l’episodi. En altres exemples com tic-tac-toe, aquest és el final d’un joc en què guanyes o perds.

El treball teòricament podria començar en qualsevol condició, i això explica per què necessitem prou episodis per assegurar-nos que cada condició i acció es provin suficientment perquè els resultats no siguin determinats per resultats invàlids. D'altra banda, però, com més episodis introduïm, més temps de càlcul serà més llarg. Depenent de la mida de l’entorn, és possible que no tinguem una quantitat il·limitada de recursos per fer-ho.

Això es coneix com el problema dels bandits amb diversos braços. Amb un temps limitat (o altres recursos), hem d’assegurar-nos que provem cada parell d’acció estat suficientment perquè les accions seleccionades a la nostra política siguin les òptimes. En altres paraules, hem d’afirmar que les accions que ens han portat bons resultats en el passat no són casuals, sinó que realment prenen la decisió correcta, incloses aquelles que semblen males. En el nostre exemple, això pot semblar fàcil tenint en compte el pocs estats que tenim, però imaginem si augmentem i com això cada vegada és més un problema.

L’objectiu general del nostre model RL és seleccionar les accions que maximitzin les recompenses acumulatives esperades, coneguda com a taxa de rendiment. En altres paraules, el ROI és simplement la recompensa general de l’episodi. Una manera fàcil de calcular-ho és sumar totes les recompenses, inclosa la recompensa final, a cada episodi.

Un enfocament més rigorós consisteix a fer els primers passos més importants que els posteriors de l’episodi aplicant un factor de descompte (gamma) a la fórmula següent:

En altres paraules, sumem totes les recompenses, però pesem els passos posteriors per un factor de gamma, depenent de quants passos es van fer per aconseguir-los.

Quan reflexionem sobre el nostre exemple, es fa encara més clar preveure l’ús d’una taxa de rendibilitat amb descompte a mesura que el professor premia (o penalitza) a tots els que van participar en l’episodi, però ho fa en funció de la distància que tenen de la línia de fons és.

Per exemple, si es passa el paper d'A a B a M que l'ha tirat a la brossa, M hauria de penalitzar-se més, després B per passar-li-ho i, finalment, la persona A que encara participa en el resultat final, però és inferior a M o B. Això també subratlla que com més temps trigui (en funció del nombre de passos) a començar en un estat i arribar al contenidor, menys hi haurà recompensa o càstig, però hi haurà recompenses negatives per completar-lo es van acumular més passos.

Aplicant un model al nostre exemple

Com que el nostre entorn de mostra és reduït, el podem aplicar i visualitzar alguns dels càlculs que hem fet manualment i demostrar els efectes del canvi de paràmetres.

Per a cada algorisme, primer hem d'inicialitzar la funció de valor d'estat V (s) i hem decidit establir-lo a 0 tal com es mostra a continuació.

A continuació, deixem que el model simuli experiències amb l’entorn en funció de la nostra distribució de probabilitats observada. El model inicia un full de paper en estats aleatoris i els resultats de qualsevol acció segons la nostra pauta es basen en les probabilitats observades. Per exemple, suposem que tenim les tres primeres seqüències simulades:

Amb aquests episodis podem calcular les primeres actualitzacions de la nostra funció de valor d’estat mitjançant qualsevol dels tres models donats. Per simplificar els nostres càlculs manuals, inicialment seleccionem qualsevol valor alfa i gamma de 0,5. Més endavant mostrarem com afecta aquesta variable als resultats.

Primer apliquem la diferència de temps 0. El més senzill dels nostres models i les tres primeres actualitzacions de valor són els següents:

Com es van calcular? Bé, com que el nostre exemple és petit, podem mostrar els càlculs a mà.

Llavors, què podem observar en aquesta primera etapa? En primer lloc, l'ús de TD (0) sembla injust per a alguns estats, com ara la persona D, que en aquest moment no va guanyar res del fet que el document va entrar a la paperera dues de cada tres vegades. La seva actualització només es va veure afectada pel valor del següent nivell, però això subratlla com les recompenses positives i negatives es van estendre cap a fora des de la cantonada cap als estats.

Com més episodis incloguem, més les recompenses positives i negatives s’estendran a tots els estats. Això es mostra aproximadament a la figura següent, que mostra que els dos episodis condueixen a un resultat positiu i afecten el valor del professor i dels estats G, mentre que l'episodi negatiu únic castiga la persona M.

Per mostrar-ho, podem provar altres episodis. Si repetim els tres camins ja donats, obtindrem la següent funció de valor d'estat:

(Tingueu en compte que hem repetit aquests tres episodis en aquest exemple per simplicitat, però el model real tindria episodis en què els resultats es basen en la funció de probabilitat de transició observada.)

El diagrama anterior mostra les recompenses del terminal que s’estenen des de la cantonada superior dreta fins als estats. A partir d’això, podem decidir actualitzar la nostra política, ja que és evident que la recompensa negativa final passa per la persona M i, per tant, B i C es veuen afectats negativament. Per tant, segons V27, per a cada estat podem decidir actualitzar la nostra política seleccionant el següent millor valor d'estat per a cada estat, tal com es mostra a la figura següent

Hi ha dos motius de preocupació en aquest exemple: el primer és que la millor acció de la persona A és tirar-les a la paperera i rebre una recompensa negativa. Això es deu al fet que cap dels episodis no va visitar aquesta persona, cosa que va posar de manifest el problema dels bandits amb diversos braços. Hi ha molt pocs estats en aquest petit exemple, de manera que caldrien molts episodis per visitar-los tots, però hem d’assegurar-nos que es faci.

La raó per la qual aquesta acció és millor per a aquesta persona és que cap dels estats finals no té cap valor, sinó que els resultats positius i negatius resideixen en les recompenses finals. Podríem llavors, si la nostra situació ho requereix, inicialitzar V0 amb números per als estats finals en funció dels resultats.

En segon lloc, el valor d’estat de la persona M canvia d’anada i tornada entre -0,03 i -0,51 (aproximadament) després dels episodis i hem de considerar per què passa això. Això és causat pel nostre índex d’aprenentatge alfa. De moment, només hem introduït els nostres paràmetres (taxa d’aprenentatge alfa i taxa de descompte gamma), però no hem explicat detalladament com afecten els resultats.

Un gran ritme d’aprenentatge pot produir resultats erràtics, però no hauria de ser tan petit que la convergència s’allargui per sempre. Això es mostra més avall a la figura, que mostra el nombre total de V (s) per a cada episodi, i podem veure clarament que hi ha una tendència general creixent entre episodis, però que s’alterna d’anada i tornada. Una altra bona explicació de la taxa d’aprenentatge és la següent:

“Al golf, quan la pilota està lluny del forat, és molt difícil per al jugador acostar-se el més possible al forat. Més tard, quan arriba a la zona marcada, tria un altre club per fer un tir curt precís.

Per tant, no és que no pugui ficar la pilota al forat sense escollir el pal de tir curt, sinó que podria enviar la pilota davant de l'objectiu dues o tres vegades. No obstant això, és millor si juga de manera òptima i utilitza la força adequada per arribar al forat. "

episodi

Hi ha alguns mètodes complexos per determinar la taxa d’aprenentatge òptima per a un problema. Com passa amb qualsevol algorisme d’aprenentatge automàtic, però, si l’entorn és prou senzill, haureu d’iterar diferents valors fins que s’aconsegueixi la convergència. Això també es coneix com a gradient decent estocàstic. En un projecte recent de RL, vaig demostrar els efectes de la reducció alfa mitjançant un gràfic animat. Això es mostra a continuació. Això mostra la vibració quan l'alfa és gran i com es suavitza quan l'alfa és reduït.

De la mateixa manera, hem d’establir la nostra taxa de descompte entre 0 i 1. Sovint se suposa que s’acosta al 0,9. El factor de descompte ens indica la importància de les recompenses en el futur; Un gran nombre indica que es consideren importants, mentre que apropar-se a 0 fa que el model tingui cada vegada menys en compte els passos futurs.

Tenint en compte aquests dos factors, podem canviar l’alfa de 0,5 a 0,2 i la gamma de 0,5 a 0,9 i obtenir els resultats següents:

Com que la nostra taxa d’aprenentatge és molt més baixa ara, el model triga més a aprendre i els valors generalment són menors. El més notable per al professor és clarament el millor estat. Tanmateix, aquest compromís per a un temps de càlcul més llarg significa que el nostre valor per a M ja no fluctua com era abans. Ara ho podem veure a la figura següent per a la suma de V (s) segons els nostres paràmetres actualitzats. Tot i que no són perfectament suaus, la V (s) general (s) augmenta lentament a un ritme molt més constant que abans i sembla que convergeixi de la manera que ens agradaria, però es necessiten uns 75 episodis per fer-ho.

Canvieu el resultat objectiu

Un altre avantatge clau de RL, que no hem esmentat amb detall, és un cert control sobre el medi ambient. Actualment, les recompenses es basen en la nostra decisió d’obtenir un model positiu tan aviat com sigui possible.

Suposem que el professor ha canviat i al nou no li importa que els estudiants tirin el paper a la brossa mentre hi arriba. Aleshores podem canviar la nostra recompensa negativa i la política òptima canviarà.

Això és particularment útil per a solucions empresarials. Per exemple, suposem que esteu planejant una estratègia i que sabeu que certes transicions són menys desitjables que altres. Aleshores es pot tenir en compte i canviar-lo a voluntat.

Conclusió

Ara hem creat un model d’aprenentatge de reforç simple a partir de dades observades. Hi ha moltes coses que es podrien millorar o desenvolupar, inclòs l’ús d’un model més complex. Tot i això, aquesta hauria de ser una bona introducció per a aquells que vulguin provar de resoldre els seus propis problemes del món real.

Espero que us hagi agradat llegir aquest article. Si teniu cap pregunta, no dubteu a fer comentaris a continuació.

Moltes gràcies

esterlina