Bandidos Contextuales: Fundamentos y Aplicaciones

Bandidos Con ex uales: Fundamen os y Aplicaciones Con ex ual Bandi s: Founda ions and Applica ions I ´an He n´andez Rold´an y Alejand o Maga zo Gonzalo Di igido po Miguel Palomino Ta juelo Doble G ado: Ingenie ´ıa In o m´a ica y Adminis aci´on y Di ecci´on de Emp esas T abajo de Fin de G ado en Ingenie ´ıa In o m´a ica Facul ad de In o m´a ica, Uni e sidad Complu ense de Mad id Cu so acad´emico 2022/2023 Resumen Como pun o de pa ida, se abo dan los undamen os e´o icos subyacen es a los bandidos mul i-b azo, p epa ando as´ı el e eno pa a la p o undizaci´on en los bandidos con ex uales. Los bandidos, como elemen o undamen al en el ap endizaje po e ue zo, o ecen una espues a e icien e a los p oblemas b´asicos del dilema de la explo aci´on en e a la explo aci´on. Un p oblema de bandidos implica un juego secuencial en e un agen e y un en o no, donde en cada onda el agen e iene a ias acciones a su disposici´on y debe elegi una pa a ecibi la ecompensa co espondien e como esul ado. Basado en las ecompensas an e io es, el agen e debe ´a mejo a su oma de decisiones pa a ob ene la m´axima ecompensa acumulada al inal del juego, man enien- do un balance en e explo a acciones menos p obadas y explo a la mejo acci´on seg´un la in o maci´on que posee. Adem´as, se explican los bandidos es oc´as icos y an agonis as como p eludio pa a p esen a a ios algo i mos que se ´an de g an u ilidad en una a ian e pa icula del modelo de bandidos: los bandidos con ex uales. En es e ipo de bandido, cada acci´on disponible es ´a asociada a una dis ibuci´on de p obabilidad de ecompensas, desconocida de an emano po el agen e, de la cual se ob iene la ecompensa co espondien e as elegi una ac- ci´on. Po lo an o, el agen e a a ´a de maximiza sus ecompensas eligiendo los b azos que mayo ecompensa media engan en unci´on del con ex o. A lo la go de es e abajo se p esen an los algo i mos que esuel en los p oblemas de los bandidos plan eados y se compa an sus endimien os a a ´es de la m´e ica del emo dimien o. Tambi´en, se a an las di e encias en e los emo dimien os de los algo i mos que se adap an al con ex o y los que no g acias a la exposici´on de un juego con ex ual. T as abo da cada concep o e´o ico del ´ambi o de los bandidos con ex uales, se expone una aplicaci´on p ´ac ica en consonancia pa a es udia el desempe˜no de los bandidos con ex uales en di e sos dominios. Las p incipales apo aciones p ´ac icas de es e abajo se localizan den o del sec o inancie o, con- c e amen e en el depa amen o de la au oma izaci´on de la in e si´on en el me cado de alo es a a ´es de los bo s de come cio, y en el mundo digi al, ealizando un sis ema ecomendado de pel´ıculas. Palab as cla e Bandidos mul i-b azo. Explo aci´on-explo aci´on. Remo dimien o. Bandidos es oc´as icos. Bandidos an ago- nis as. Bandidos con ex uales. Clase pol´ı ica. Exp4. Bo s de come cio. Sis ema ecomendado . 1 Abs ac As a s a ing poin , he heo e ical ounda ions unde lying mul i-a med bandi s a e add essed, he eby laying he g oundwo k o a deep di e in o con ex ual bandi s. Bandi s, as a undamen al elemen in ein o cemen lea ning, p o ide an e icien esponse o he basic p oblems o he explo a ion-exploi a ion dilemma. A bandi p oblem in ol es a sequen ial game be ween an agen and an en i onmen , whe e in each ound he agen has se e al ac ions a his disposal and mus choose one o ecei e he co esponding ewa d as a esul . Based on pas ewa ds, he agen should imp o e his decision-making o ob ain he g ea es accumula ed ewa d a he end o he game, main aining a balance be ween explo ing lesse - es ed ac ions and exploi ing he bes ac ion acco ding o he in o ma ion he possesses. In addi ion, s ochas ic and ad e sa ial bandi s a e explained as a p elude o p esen ing a ious algo i hms ha will be ex emely use ul in a pa icula a ian o he bandi model: he con ex ual bandi s. In his ype o bandi , each a ailable ac ion is associa ed wi h a p obabili y dis ibu ion o ewa ds, unknown o he agen be o ehand, om which he co esponding ewa d is ob ained a e choosing an ac ion. The e o e, he agen will y o maximize his ewa ds by choosing he a ms wi h he highes a e age ewa d based on he con ex . Th oughou his wo k, algo i hms ha sol e he p oblems posed by bandi s a e p esen ed and hei pe o - mances a e compa ed h ough he me ic o eg e . Also, he di e ences be ween he eg e s o algo i hms ha adap o he con ex and hose ha do no a e discussed, hanks o he exposi ion o a con ex ual game. A e add essing each heo e ical concep in he ield o con ex ual bandi s, a p ac ical applica ion is p esen ed o s udy he pe o mance o con ex ual bandi s in a ious domains. The main p ac ical con ibu ions o his wo k a e loca ed wi hin he inancial sec o , speci ically in he depa men o au oma ing in es men in he s ock ma ke h ough ading bo s, and in he digi al wo ld, by implemen ing a mo ie ecommenda ion sys em. Keywo ds Mul i-a med bandi s. Explo a ion-exploi a ion. Reg e . S ochas ic bandi s. Ad e sa ial bandi s. Con ex ual bandi s. Policy class. Exp4. T ading bo s. Recommenda ion sys em. 2 ´ Indice 1. In oducci´on 6 2. In oduc ion 9 3. P oblema de los Bandidos Mul i-b azo 12 3.1. Ca ac e ´ıs icas y Di e enciaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2. TiposdeBandidos ............................................ 13 3.3. Aplicaciones de los Bandidos Con ex uales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4. Bandidos Es oc´as icos 15 4.1. Algo i mosSimples............................................ 16 4.1.1. Algo i mo Explo aci´on-P ime o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.2. Algo i mo ´ Epsilon-A a icioso.................................. 17 4.2. Algo i mos A anzados: Explo aci´on Adap a i a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.1. Algo i mo Eliminaci´on Sucesi a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.2. Algo i moUCB1......................................... 19 5. Bandidos An agonis as 21 5.1. P ime In en odeSoluci´on ....................................... 23 5.2. Algo i mosE ec i os........................................... 24 5.2.1. Algo i moHedge......................................... 24 5.2.2. Algo i moExp3 ......................................... 25 5.2.3. Algo i moExp4 ......................................... 27 6. Bandidos Con ex uales 29 6.1. Bandidos Con ex uales con Pocos Con ex os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6.1.1. Recomendado de Pel´ıculas pa a Cua o G upos . . . . . . . . . . . . . . . . . . . . . . . 31 6.2. Bandidos Con ex uales Lipschi zianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2.1. Mo i aci´on ............................................ 35 6.2.2. Implemen aci´on de Bandidos Con ex uales Lipschi zianos del Me cado . . . . . . . . . . . 36 6.2.3. Demos aci´on de Lispchi z pa a Bandidos Con ex uales Lipschi zianos . . . . . . . . . . . 40 6.3. Bandidos Con ex uales con Clase Pol´ı ica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.3.1. Algo i mo Exp4 con Pol´ı icas en luga de Expe os . . . . . . . . . . . . . . . . . . . . . . 42 7. Bandidos Con ex uales en Juegos Con ex uales 44 7.1. In oducci´ondelSis ema......................................... 44 7.2. JuegoCon ex ual............................................. 45 7.3. LaRed................................................... 45 7.4. Algo i mos ................................................ 46 7.4.1. Algo i moHedge......................................... 46 7.4.2. Algo i moGPMW ........................................ 49 7.4.3. Algo i mocGPMW ....................................... 51 7.5. Conclusiones ............................................... 54 8. Bo s de Come cio 59 8.1. Plan eamien o............................................... 59 8.2. Expe os.................................................. 61 8.2.1. Expe o en Posiciones Co as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 8.2.2. Expe o en Posiciones La gas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 8.2.3. Expe o en Posiciones Cambian es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.2.4. Expe o en C uce de Medias M´o iles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.2.5. Expe oenRSI.......................................... 63 8.2.6. Expe o en MACD y Bandas de Bollinge . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 8.2.7. Expe oenTodo......................................... 64 8.3. An´alisis de la Soluci´on Plan eada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 8.3.1. Conside acionesp e ias ..................................... 65 8.3.2. An´alisis del Ho izon e Tempo al . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.3.3. An´alisis de la Tasa de Ap endizaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 8.3.4. An´alisis de la Tasa de Explo aci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 8.3.5. Pues a en P ´ac ica de la Soluci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3 9. Sis ema Recomendado de Pel´ıculas 75 9.1. BasedeDa os............................................... 75 9.2. Iniciaci´on ................................................. 76 9.3. Funcionamien o.............................................. 77 9.4. Pol´ı icas.................................................. 78 9.4.1. Pol´ı icasSimples......................................... 79 9.4.2. Fil o Colabo a i o Basado en Vecindad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 9.4.3. Red Neu onal como Bandido Con ex ual . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9.5. Resul ados................................................. 86 9.5.1. Resul adosIniciales ....................................... 86 9.5.2. Resul adosFinales........................................ 87 9.5.3. An´alisisDe allado ........................................ 90 10.Apo aciones indi iduales 94 11.Conclusiones 96 12.Conclusions 96 13.Anexo 97 13.1. Depu aci´on de la E oluci´on de Pesos de los Bo s con P obabilidades Indi iduales de Elecci´on de B azode100%y0%........................................... 97 13.2. Resul ados Sis ema Recomendado Pel´ıculas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4 No aci´on En es e b e e apa ado se in oducen algunos concep os cla e asociados a su s´ımbolo. Es os s´ımbolos se ´an u ilizados en las secciones pos e io es. KEl n´ume o de b azos en el p oblema plan eado. TEl ho izon e empo al o n´ume o de ondas del p oblema plan eado. a B azo elegido en la onda . Recompensa obse ada en la onda as elegi el b azo a . DaDis ibuci´on de p obabilidad de las ecompensas del b azo a. IID Recompensas Independien es e Id´en icamen e Dis ibuidas. La ecompensa pa a cada b azo es IID cuando, en cada onda, se oma una mues a de o ma independien e a pa i de la dis ibuci´on Da. Es deci , es una dis ibuci´on de ecompensas independien e de la onda y po an o es ´a ica, pe o di e en e seg´un el b azo. R(T) El emo dimien o del algo i mo en la onda T. El emo dimien o calcula la di e encia en e el mejo endimien o posible del algo i mo du an e dichas ondas y el endimien o eal. E[R(T)] El emo dimien o espe ado del algo i mo en la onda T. a∗El b azo ´op imo. µ(a) La ecompensa media pa a un b azo a. O() O den que e leja la e iciencia del algo i mo. n (a) El n´ume o de eces que se selecciona el b azo ahas a la onda . (a) El adio de con ianza que ep esen a la a iabilidad de las ecompensas ob enidas po el b azo aen una onda . UCB(a) Co a supe io dado un b azo a. LCB(a) Co a in e io dado un b azo a. c (a) La abla de cos es que e leja el cos e pa a un b azo aen una onda . cos e(a) El cos e o al de un b azo a, conside ando odas las ondas que ha jugado. ˆµaP edicci´on de ecompensa pa a un b azo a. PesoaImpo ancia de un b azo pa a el modelo. waPeso o impo ancia de un b azo pa a el modelo. p Dis ibuci´on de p obabilidades de elegi un b azo. P obabilidadaPosibilidades de elegi un b azo. la(En juegos con ex uales) P´e didas, o emo dimien o, de un b azo en una onda . La(En juegos con ex uales) P´e didas acumuladas de un b azo en una onda . ϵEpsilon que ep esen a ´a la asa de ap endizaje en Hedge. γGamma que ep esen a ´a la asa de ap endizaje (juegos con con ex o). x El con ex o dada una onda . UCBiUna ins ancia del algo i mo UCB, de los bandidos es oc´as icos. LLa cons an e Lipschi z que se u iliza en los bandidos con ex uales lipschi zianos. γEn el algo i mo Exp4, es a a iable e leja la asa de explo aci´on. acum(a|x) La ecompensa acumulada de un b azo dado un con ex o x. πPol´ı ica, que se usa como expe o, en el Exp4. Π Conjun o de pol´ı icas p esen ado al Exp4 en su e si´on de bandidos con ex uales con clase pol´ı ica. ˆc (e) Cos es alsos que se calculan en el algo i mo Exp4 pa a abaja con el algo i mo Hedge. p Dis ibuci´on de p obabilidad de elegi una pol´ı ica π. Se emplea en los algo i mos Hedge y Exp4. 5 1. In oducci´on O igen de los Bandidos El p oblema de los bandidos mul i-b azo ue inicialmen e es udiado po Thompson en 1933 cuando pu- blic´o un a ´ıculo que aho a ha pasado a la his o ia en la e is a Biome ika [1]. En dicha e is a, Thompson se in e es´o po las p uebas m´edicas que se ealizaban en esa ´epoca, po que se consum´ıan medicamen os sin conoce su e ec i idad. En es as p uebas, Thompson obse ´o que los ´a macos no e an buenos inicialmen e ni se ajus aban sob e la ma cha. Lleg´o a la conclusi´on de que se ealizaban p uebas m´edicas “a ciegas”, su giendo la necesidad de adap aci´on du an e el ensayo pa a que el e ec o del a amien o ue a ´op imo. El nomb e de los bandidos mul i-b azo p o iene de 1950s, cuando F ede ick Mos elle y Robe Bush es u- dia on el ap endizaje animal. Du an e su es udio, ealiza on p uebas a a as en un labe in o con o ma de T, es deci un camino ec o que e mina en una bi u caci´on. De es a o ma, si uaban a los animales an e un p oblema de decisi´on: izquie da o de echa. Solo en uno de los dos amales hab´ıa comida como ecompensa, en el o o no hab´ıa nada. An e es e escena io, el oedo eleg´ıa un camino sin sabe qu´e iba a encon a . Con el obje i o de es udia algo pa ecido con los humanos, se usa on unas m´aquinas agape as de dos b azos, ambi´en conocidas como “bandidos” de dos b azos po que obaban el dine o del jugado que las usaba. Pa a usa las m´aquinas agape as, en cada i ada o onda el jugado elige un b azo, la palanca de la izquie da o la de la de echa. Se llama onda a cada opo unidad que iene el jugado pa a elegi un b azo. Al igual que con los oedo es, el obje i o del jugado es consegui la m´axima ecompensa posible eniendo en cuen a que al p incipio no sabe qu´e b azo de uel e las mejo es ecompensas. Se en iende que i a de una palanca de la m´aquina agape as se ´a elegi un b azo del bandido mul i-b azo. Los bandidos mul i-b azo ep esen an el p oblema que se da en una si uaci´on de ap endizaje simila a la de la m´aquina agape as: explo a una opci´on que puede pa ece in e io a p io i, seg´un la expe iencia p e ia del jugado , o con inua explo ando la mejo al e na i a o b azo. Po ejemplo, un jugado puede es a an e la disyun i a de elegi en e un b azo con el cual ha conseguido mucho dine o en las ondas an e io es, o p oba un b azo nue o que a´un no hab´ıa usado. Po ello, encon a el co ec o equilib io en e la explo aci´on-explo aci´on es el co az´on de los p oblemas de los bandidos mul i-b azo y la a ea de los algo i mos que se es udia a lo la go de es e abajo. Es os algo i mos se encuad an den o del ap endizaje au om´a ico en el ´ambi o del ap endizaje po e ue zo. El ap endizaje po e ue zo es un ipo de ap endizaje que iene como obje i o maximiza las ecompensas que consigue el algo i mo a a ´es de sus acciones. Al p incipio el algo i mo no sabe qu´e acciones oma , debe descub i con el paso de las ondas qu´e acciones le p opo cionan m´as ecompensas. La p incipal ca ac e ´ıs ica de los bandidos mul i-b azo den o del ap endizaje po e ue zo es que son un escena io modi icado de ap endizaje po e ue zo cuyo aspec o di e encial es que el es ado pe manece cons an e. El es ado es el en o no donde abaja el algo i mo. Pa a en ende las en ajas de es e escena io “segu o”, p ime o se explica el escena io opues o, es deci una si uaci´on de ap endizaje po e ue zo comple a donde las acciones del algo i mo modi iquen el es ado del juego. Un ejemplo es el ajed ez. En es e juego cada mo imien o que hace un jugado (o algo i mo, en es e caso) cambia el es ado del able o. Si el algo i mo decide mo e un pe´on, es o cambia el es ado del able o y ambi´en las posibles acciones o b azos que an o ´el como su oponen e pueden oma en el u u o. A su ez, es as decisiones ambi´en pueden in lui en la es a egia del oponen e, lo que a su ez cambia el en o no una ez m´as. Es a si uaci´on p esen a a ios desa ´ıos: Complejidad: En el ap endizaje po e ue zo comple o, el algo i mo necesi a ap ende una pol´ı ica comple a que en unci´on del es ado elija la acci´on ´op ima, en luga de solo ap ende la ecompensa espe ada de cada acci´on. Es o puede hace que el p oceso de ap endizaje sea mucho m´as complejo y equie a m´as iempo y ecu sos compu acionales. Mayo iesgo: Dado que el es ado del en o no puede cambia con cada acci´on que se oma, exis e un iesgo inhe en e de al e a el en o no de mane a nega i a du an e el p oceso de explo aci´on. Es o puede di icul a el an´alisis del dilema de explo aci´on-explo aci´on y puede lle a a esul ados indeseables si no se maneja adecuadamen e. 6 Ine iciencia: En los p oblemas de ap endizaje po e ue zo comple o, la op imizaci´on puede se menos di ec a y el ap endizaje m´as len o, ya que el algo i mo necesi a ap ende a es ima la ecompensa de cada acci´on en cada posible es ado. Es o puede eque i un n´ume o mucho mayo de in e acciones con el en o no, lo que puede se cos oso en ´e minos de iempo y ecu sos. Po an o, al conside a que el es ado no cambia, los bandidos mul i-b azo e i an la mayo pa e de la com- plejidad del ap endizaje po e ue zo comple o y abajan c´omodamen e uno de los concep os m´as impo an es del ap endizaje po e ue zo: el dilema explo aci´on-explo aci´on [7]. Los algo i mos de ap endizaje au om´a ico se pueden clasi ica en dos ´a eas o ipos: ap endizaje o line y ap endizaje en l´ınea. En es e caso, los bandidos mul i-b azo se encuen an den o de la segunda ca ego ´ıa po - que no se en enan o line, sino que ap enden con o me an omando decisiones. En de ini i a, los bandidos mul i-b azo se han con e ido en un ma co simple pe o muy ´u il pa a algo i mos que oman decisiones bajo ince idumb e a lo la go del iempo. Obje i os y plan de abajo El p op´osi o p imo dial de es e abajo eside en la in es igaci´on y comp ensi´on del p oblema de los ban- didos con ex uales. Se hace hincapi´e en los de alles de los algo i mos que solucionan dicho p oblema a ando de explica la l´ogica inhe en e a es os. Finalmen e, es e es udio p opone la c eaci´on de aplicaciones p ´ac icas con el obje i o de ilus a los bene icios que los bandidos con ex uales pueden apo a en una amplia a iedad de dominios de aplicaci´on. Po lo an o, es a in es igaci´on iene un en oque eminen emen e p ´ac ico sus en ado en p incipios e´o icos. La es uc u a empleada en la memo ia es la siguien e: Las secciones 1 y 2 con o man la in oducci´on. Explican la mo i aci´on, los obje i os, el plan de desa ollo y los ecu sos u ilizados. El con enido de la secci´on 1 es ´a en espa˜nol y el de la secci´on 2 en ingl´es, pe o ambos son iguales. La secci´on 3 cons i uye la in oducci´on de los bandidos mul i-b azo, as´ı como de alles a ene en cuen a. Las secciones 4 y 5 in oducen dos ipos de bandidos esenciales pa a despu´es abaja con los bandidos con ex uales. La secci´on 6 desa olla al comple o la eo ´ıa del ema undamen al del abajo, los bandidos con ex uales, y expone las dos p ime as aplicaciones p ´ac icas. La secci´on 7 es udia un caso conc e o donde se compa a el endimien o de algo i mos con ex uales y no con ex uales en un juego con ex ual. La secci´on 8 expone un aplica i o de los bandidos con ex uales con una clase pol´ı ica, explicados en 6, den o del me cado inancie o. La secci´on 9 p esen a un sis ema ecomendado como una aplicaci´on de los bandidos con ex uales con una clase pol´ı ica. Las secciones 11 y 12 o man la conclusi´on del abajo. Ambas secciones ienen el mismo con enido, pe o la secci´on 11 es ´a en espa˜nol y la secci´on 12 es ´a en ingl´es. Recu sos y Documen aci´on Re e encias bibliog ´a icas p incipales Es e abajo se ha basado undamen almen e en el lib o de Sli kins [2], donde se pueden encon a las demos aciones de odos los esul ados e´o icos que p esen amos. Tambi´en se ha consul ado cuando ha sido necesa io los ex os de La imo e y Bubeck [3, 4]. 7 Reposi o io de implemen aciones Las implemen aciones de so wa e ealizadas du an e el desa ollo de es e abajo quedan e lejadas en los eposi o ios pe sonales de los au o es [26, 27]. Los lenguajes de p og amaci´on empleados son Py hon, p inci- palmen e, y C++. Py hon un lenguaje de p og amaci´on de al o ni el muy e s´a il y ´acil de usa . Debido a su meno complejidad de c´odigo y la p esencia de biblio ecas a anzadas en compu aci´on cien ´ı ica y ap endizaje au om´a ico, Py hon es especialmen e ele an e en el campo de la in eligencia a i icial, incluyendo el ap endizaje po e ue zo. Se han u ilizado biblio ecas imp escindibles en el ap endizaje au om´a ico como numpy, pandas, scipy y enso low. Dichas biblio ecas pe mi en c ea algo i mos y a a adecuadamen e los da os. Y ambi´en se han ap o echado o as biblio ecas pa a isualiza da os como ma plo lib y seabo n. 8 4. Bandidos Es oc´as icos El obje i o de es e apa ado es de ini uno de los p incipales ipos de bandidos, as´ı como de alla sus ca ac e ´ıs icas pa a en ende su esencia. Los es oc´as icos son el modelo b´asico de los bandidos mul i-b azo. A lo la go de es a secci´on, se a a ´an a ios algo i mos disponibles pa a es e ipo de bandidos y se compa a ´an. Se conside a un p oblema en el que un algo i mo iene Kposibles b azos a elegi en cada una de las T ondas. T as la elecci´on de un b azo, el algo i mo ob iene una ecompensa co espondien e al b azo elegido. El p o ocolo a segui es el siguien e, donde [T] = {1,2, . . . , T}: P oblema Bandidos Es oc´as icos Habiendo Kb azos y T ondas, En cada onda ∈[T]: 1. El algo i mo elige un b azo a . 2. El algo i mo obse a la ecompensa ∈[0,1] pa a el b azo elegido. El escena io es oc´as ico se gene a bajo las siguien es es suposiciones: El algo i mo ´unicamen e obse a la ecompensa de la acci´on seleccionada. Es o se conoce como e oali- men aci´on de bandido. Po an o, el algo i mo no conoce las ecompensas asociadas al es o de acciones que pod ´ıa habe elegido. Las ecompensas es ´an aco adas al in e alo [0,1]. La ecompensa pa a cada b azo es IID. Pa a cada b azo ahay una dis ibuci´on Dallamada dis ibuci´on de ecompensas que es inicialmen e desconocida po el algo i mo. La mo i aci´on que hay de ´as de aco a las ecompensas en un in e alo en e 0 y 1 es pe mi i el c´alcu- lo del emo dimien o en unci´on del n´ume o de ondas Tdel p oblema. Es o se ´a demos ado m´as adelan e en la explicaci´on del emo dimien o del algo i mo Explo aci´on-P ime o, que es el p ime o de odos los que se comen an en es e abajo, con el ´animo de que quede cla o pa a el es o de eces que apa ezca la a iable T en la ´o mula de un emo dimien o. Po es e mo i o, si las ecompensas del p oblema ienen aco adas de la o ma [m, n] al que m<n, se ecomienda ealiza una aducci´on o eescala de las ecompensas al in e alo [0,1]. Uno de los m´e odos m´as comunes pa a aslada y eescala ecompensas al in e alo [0,1] es la ans o ma- ci´on lineal. La ´o mula co espondien e se ´ıa: ′= −a b−a, donde es la ecompensa o iginal y ′es la ecompensa ans o mada en el in e alo [0, 1]. No es necesa io que las ecompensas sigan una dis ibuci´on espec´ı ica o que cumplan alguna o a condici´on. Sin emba go, es muy impo an e ene en cuen a que la ans o maci´on lineal asume que la elaci´on en e las ecompensas se man iene cons an e a lo la go del in e alo. Si es e no ue a el caso, se ´ıa necesa io una ans- o maci´on di e en e que se ajus e mejo a las ca ac e ´ıs icas del p oblema. Po o o lado, se de ine el ec o de ecompensas medias como µ∈[0,1]K, donde µ(a) = E[Da] es la e- compensa media del b azo a∈K. Se usa a∗:= a g m´axa∈Aµ(a) pa a de ini el b azo ´op imo, es deci , el que de uel e la ecompensa media m´as al a. Una o ma ap oximada de calcula el emo dimien o es median e la compa aci´on de la suma de las ecom- pensas medias de los b azos ya elegidos, espec o al benchma k es ablecido po escoge en odas las T ondas el b azo ´op imo a∗. Fo malmen e, se de ine el emo dimien o: R(T) = µ(a∗)T− T X =1 µ(a ) Cabe des aca que a , el b azo omado en cada onda , es una a iable alea o ia si su elecci´on depende de la alea o iedad en las ecompensas o la es a egia de selecci´on de b azo del algo i mo. En consecuencia, mien as las ecompensas sean alea o ias o el b azo sea escogido de o ma alea o ia, el emo dimien o R(T) ambi´en 15 es una a iable alea o ia. Po an o, cuando las ecompensas sean IID, al y como sucede en el escena io es- oc´as ico, el emo dimien o es una a iable alea o ia y se habla en ´e minos de emo dimien o espe ado E[R(T)]. A con inuaci´on, se de allan algunos de los algo i mos disponibles, empezando con los m´as simples pa a i- nalmen e o ece soluciones m´as elabo adas y complejas. 4.1. Algo i mos Simples 4.1.1. Algo i mo Explo aci´on-P ime o El p ime algo i mo que se p opone pa e de la siguien e idea: explo a los b azos uni o memen e du- an e N ondas y elegi el mejo b azo el es o de las ondas. Es e algo i mo se conoce como Explo aci´on-P ime o. Algo i mo 4.1 Explo aci´on-P ime o (N) 1: Fase de Explo aci´on: Se p ueba cada b azo N eces. 2: Se selecciona el b azo acon la mejo media de ecompensas. 3: Fase de Explo aci´on: El b azo aes u ilizado el es o de ondas. Teo ema 4.1. El algo i mo Explo aci´on-P ime o consigue un emo dimien o espe ado E[R(T)] ≤T2/3× O(Klog T)1/3cuando N=T K2 3·O(log T)1 3. Pa a di e en es alo es de Nno se asegu a dicho emo dimien o. N´o ese que el alo de Tes mayo que K, ya que es necesa io explo a cada b azo al menos una ez. Despu´es de p esen a cada algo i mo se incluye un eo ema demos ado en [2] que enuncia el emo dimien o conseguido po dicho algo i mo y pe mi e e alua su endimien o. Conc e amen e, cuan o meno es su emo di- mien o mejo es su endimien o. Las ´o mulas de los emo dimien os de es e abajo es ablecen co as supe io es del “peo ” endimien o del algo i mo en cada p oblema y gene almen e u ilizan las a iables Tho izon e em- po al y Kb azos. Con el obje i o de comp ende la p esencia de la a iable Ten la ´o mula del emo dimien o, se plan ea un sencillo ejemplo que equie e que las ecompensas es ´en p e iamen e aco adas en el in e alo [0, 1]. Exis en dos cajas, una oja (caja A) y o a azul (caja B). Cada d´ıa, du an e 10 d´ıas (T= 10), se puede elegi una de las dos cajas pa a ab i la y ecibi una ecompensa. La caja A siemp e iene una ecompensa de 1, mien as que la caja B siemp e iene una ecompensa de 0. Si se elige siemp e la caja A du an e los 10 d´ıas, se ecibe una ecompensa o al de 10 (1 ∗10). Po o o lado, si se elige siemp e la caja B, la ecompensa o al se ´a de 0 (0 ∗10). En el caso peo , eligiendo siemp e la caja B, el l´ımi e supe io del emo dimien o iene dado po la a iable T(10 en es e ejemplo), ya que la di e encia en e la m´axima ecompensa (10) y la m´ınima ecompensa (0) es igual a T. Es po ello que, o malmen e, se de ine el emo dimien o asociado al caso peo como R(T) = O(T). Es impo an e en ende que, en el modelo de bandidos mul i-b azo, los casos ce canos al caso peo se in e - p e an como si uaciones en las que el algo i mo no es capaz de ap ende a ob ene ecompensas mayo es con el paso de las ondas. Sin emba go, los algo i mos que se plan ean a lo la go de es e abajo s´ı consiguen ap ende a oma las mejo es decisiones con m´as ecuencia. Debido a es e hecho obje i o, se pod ´a obse a que los l´ımi es supe io es de los emo dimien os que o ecen son signi ica i amen e meno es que el l´ımi e supe io en el caso peo (O(T)). En la igu a 1 se explica el ap endizaje del algo i mo Explo aci´on-P ime o de una o ma g ´a ica. La unci´on de colo azul ep esen a el emo dimien o asociado al peo caso de odos en el que el algo i mo escoge siemp e el peo b azo. Es e caso espec´ı ico simboliza la inexis encia de ap endizaje. Po o a pa e, la unci´on de colo ojo ep esen a el l´ımi e supe io del emo dimien o espe ado asociado al algo i mo Explo aci´on-P ime o. Po ende, las l´ıneas e icales ep esen an el emo dimien o que el algo i mo ha sido capaz de e i a o el ni el de ap endizaje del algo i mo as 100 y 200 ondas, espec i amen e. 16 0 50 100 150 200 250 300 0 100 200 300 Rondas (T) Remo dimien o (R(T)) R(T) = O(T) R(T) = T2/3×O(Klog T)1/3 Figu a 1: G ´a ica de Remo dimien o. El algo i mo Explo aci´on-P ime o unciona en dos ases. P ime o, explo a cada b azo du an e un n´ume o Np ede inido de ondas. Despu´es, selecciona el b azo con la mejo ecompensa p omedio, obse ada du an e la ase de explo aci´on, has a el inal del ho izon e empo al. El p oblema de es e algo i mo es que la explo aci´on se ealiza po comple o al comienzo del p oceso y no se dis ibuye a lo la go del iempo. Es o signi ica que, una ez que se ha comple ado la ase de explo aci´on, el algo i mo deja de explo a y se cen a ´unicamen e en la explo aci´on del b azo que ob u o el mejo endimien o du an e la ase de explo aci´on. En muchos casos, se ´ıa m´as e ec i o dis ibui la explo aci´on de mane a m´as uni- o me a lo la go del iempo en luga de ealiza la oda al comienzo. Al dis ibui la explo aci´on de mane a m´as uni o me, el algo i mo end ´ıa m´as opo unidades de ap ende sob e los b azos y ac ualiza sus es imaciones de ecompensas medias a medida que a anza el iempo. Es o pod ´ıa ayuda a e i a que el algo i mo se a asque en una decisi´on sub´op ima basada en in o maci´on inicial limi ada y a aumen a el ni el de ap endizaje del algo i mo. Po es e mo i o nace o o algo i mo simple: ´ Epsilon-A a icioso. 4.1.2. Algo i mo ´ Epsilon-A a icioso Algo i mo 4.2 ´ Epsilon-A a icioso (ε1, ε2, . . . ). 1: o cada onda = 1,2, . . . do 2: Ti a una moneda con unas p obabilidades de explo aci´on ε 3: i explo aci´on hen 4: explo a : elegi un b azo auni o memen e 5: else 6: explo a : elegi el b azo con la ecompensa m´as al a has a el momen o 7: end i 8: end o Teo ema 4.2. El algo i mo ´ Epsilon-A a icioso con p obabilidades de explo aci´on ε = −1/3·(Klog )1/3al- canza un l´ımi e supe io de emo dimien o E[R( )] ≤ 2/3·O(Klog )1/3pa a cada onda . Se conoce como “a a icioso” ya que se undamen a en elegi la mejo opci´on a co o plazo. Sin emba go, es un algo i mo que p esen a una explo aci´on de b azos dis ibuida uni o memen e a lo la go de las ondas dado que en cualquie onda, con ε >0, hay p obabilidades de explo a . De es a o ma, se consigue soluciona el p oblema que p esen a el algo i mo Explo aci´on-P ime o y, a la ez, como se consigue demos a en [2], ob ene un emo dimien o id´en ico cuando el n´ume o de ondas en las que se ha explo ado es del o den de 2/3con un ho izon e empo al T= . Es a can idad de ondas explo adas se consigue, al y como sugie e el eo ema 17 an e io , con una p obabilidad de ´exi o ε ∼ −1/3. La no aci´on “∼” sugie e que una exp esi´on es simila a o a. En cada onda , el algo i mo explo a con una p obabilidad de ε . Es deci , la p obabilidad de explo a ε se ajus a de acue do con el n´ume o de ondas que se han comple ado. La idea es que al p incipio se debe explo a en mayo medida pa a descub i los b azos que dan las mejo es ecompensas y, a medida que se adquie e in o - maci´on adicional, se pueden explo a los b azos que ya se sabe que son buenos. Po lo an o, la p obabilidad de explo a se educe a medida que aumen a el n´ume o de ondas. An es de con inua con la explicaci´on de los algo i mos a anzados, se se˜nala la ele ancia de es e algo i mo en una implemen aci´on que se lle a ´a a cabo en la secci´on e eb al de es e abajo. 4.2. Algo i mos A anzados: Explo aci´on Adap a i a Los algo i mos a anzados se han desa ollado a a´ız de que los an e io es algo i mos, ´ Epsilon-A a icioso y Explo aci´on-P ime o, ienen el de ec o de no plani ica la explo aci´on en unci´on del his o ial de las ecompensas obse adas. Con el obje i o de se m´as e icien es en ´e minos de ap endizaje, es deci , necesi a menos ondas pa a adqui i el mismo ni el de ap endizaje, los algo i mos a anzados inco po an o o modelo de plani icaci´on conocido como explo aci´on adap a i a que dis ibuye o adap a la explo aci´on seg´un las ecompensas obse adas. Pa a comenza , es necesa io de ini el concep o y signi icado de los l´ımi es de con ianza supe io ein e io , denominados como UCB (a) y LCB (a) espec i amen e pa a un b azo ay una onda . Es os concep os son la base en la que se cimien an los algo i mos a anzados que se comen an en es e apa ado. El in e alo de inido po [LCB (a),UCB (a)] es conocido como el in e alo de con ianza. Ma em´a icamen e, se de inen: UCB (a) = µ (a) + (a) y LCB (a) = µ (a)− (a) De es a o ma, los l´ımi es de con ianza se ob ienen a pa i de la ecompensa media µ (a) conside ada pa a el b azo aen la onda y a pa i del adio de con ianza (a), que ac ´ua como la a iabilidad de la media de ecompensas y se calcula en unci´on de n (a), donde n (a) ep esen a el n´ume o de eces que se ha seleccionado el b azo ahas a la onda . Ma em´a icamen e, el adio de con ianza se calcula como sigue: (a) = p2 log T/n (a) El c´alculo del adio sugie e que, como la a iable n (a) se encuen a en el denominado de la exp esi´on, cuan o meno sea el n´ume o de eces que se ha seleccionado el b azo ahas a la onda , mayo se ´a el alo del adio de con ianza pa a dicho b azo y dicha onda. En esumen, al ec o de ecompensas medias se le suma o es a el adio de con ianza pa a ob ene el l´ımi e de con ianza supe io o in e io , espec i amen e. A pa i del in e alo de con ianza, que un b azo asea elegido en la onda puede se po dos azones: po que ha de uel o una ecompensa media µ (a) al a y/o po que el adio de con ianza (a) es al o debido a que el b azo ano se ha explo ado mucho en compa aci´on con el es o de b azos. Ambos mo i os son alicien es pa a que el b azo sea elegido y, po an o, la combinaci´on empleada de µ (a) y (a) log a un equilib io cohe en e en e la explo aci´on y la explo aci´on. 4.2.1. Algo i mo Eliminaci´on Sucesi a Un algo i mo que u iliza es a idea de l´ımi es supe io es e in e io es a pa i del ec o de ecompensas medias y el adio de con ianza es el algo i mo Eliminaci´on Sucesi a. Algo i mo 4.3 Algo i mo Eliminaci´on Sucesi a. 1: Inicialmen e odos los b azos es ´an “ac i os”; 2: o cada ase = 1,2, . . . do 3: se p ueban odos los b azos ac i os (po lo que cada ase puede con ene m´ul iples ondas, an as como b azos ac i os es en); 4: se desac i a un b azo asi exis e b azo a′con UCB (a)<LCB (a′); 5: end o 18 Teo ema 4.3. El algo i mo Eliminaci´on Sucesi a iene un emo dimien o espe ado E[R(T)] ≤ O(K log T)1/2 pa a cada onda ≤T. Po an o, en la ´ul ima onda del ho izon e empo al T, el emo dimien o espe ado es E[R(T)] ≤ O(KT log T)1/2. Pa a explica c´omo el algo i mo a desca ando la explo aci´on de los peo es b azos sucesi amen e, se incluye un co o ejemplo que supone 3 b azos y un escena io as la ase 1 en el que se ob u ie on los siguien es UCB y LCB: B azo A: UCB(A) = 0,5, LCB(A) = 0,3. B azo B: UCB(B) = 0,9, LCB(B) = 0,6. B azo C: UCB(C) = 0,8, LCB(C) = 0,7. En es e caso, UCB(A) <LCB(B) y UCB(A) <LCB(C), po lo que se desac i a el b azo A. Aho a, solo quedan los b azos B y C ac i os. El algo i mo con inua con la siguien e ase y epi e los pasos 2-4. Si en alg´un momen o UCB(B) <LCB(C) o UCB(C) <LCB(B), el algo i mo desac i a el b azo co espondien e y se queda con el b azo es an e como el que iene la mejo ecompensa p omedio es imada. A con inuaci´on, en la igu a 2, se analiza el emo dimien o del algo i mo Eliminaci´on Sucesi a en compa aci´on con el de los algo i mos simples: 0 50 100 150 200 250 300 0 100 200 300 Rondas (T) Remo dimien o (R(T)) R(T) = O(T) R(T) = T2/3×O(Klog T)1/3 R(T) = O(KT log T)1/2 Figu a 2: G ´a ica de Remo dimien o. En ´e minos de ap endizaje, la di e encia en e es e p ime algo i mo a anzado que se ha analizado y los algo i mos simples ya comen ados iene ep esen ada po la longi ud de las l´ıneas e des. En conclusi´on, se obse a una lige a mejo a o disminuci´on del l´ımi e supe io del emo dimien o espe ado al usa los concep os UCB y LCB pa a soluciona un p oblema de bandidos es oc´as icos. 4.2.2. Algo i mo UCB1 O o en oque pa a la explo aci´on adap a i a en unci´on del his o ial de las ecompensas obse adas es conocido como op imismo bajo ince idumb e. En es a a ian e, se asume que cada b azo es lo mejo que pod ´ıa se dadas las obse aciones has a el momen o, y se elige el mejo b azo bas´andose en es as es imaciones op imis as. Es o da luga al algo i mo conocido como UCB1. Teo ema 4.4. El algo i mo UCB1 se ca ac e iza po ene el mismo emo dimien o que iene el algo i mo Eliminaci´on Sucesi a. Po lo an o, su endimien o ambi´en queda ep esen ado po la unci´on de colo na anja de la igu a 2. 19 Algo i mo 4.4 Algo i mo UCB1. 1: Se p ueba cada b azo una ez. 2: En cada onda , se elige el a g m´axa∈[K]UCB (a), donde UCB (a) = µ (a) + (a). Es e algo i mo ambi´en pod ´a se denominado como UCB a lo la go de es e abajo. Po o o lado, al y como se ha mencionado an e io men e, un b azo aes elegido po habe ob enido una media de ecompensas al a o po un adio de con ianza al o. En o as palab as, la elecci´on del b azo se basa bien en su explo aci´on (dada su media de ecompensas) o en su explo aci´on (dada su adio de con ianza). De es a mane a, se consigue un pun o ´op imo en e la explo aci´on y la explo aci´on. Sin emba go, al suma el adio de con ianza se es ´a aplicando un en oque muy op imis a y se supone que un b azo ob end ´a la mejo ecompensa que le es posible, y es o no siemp e es cie o. Po o a pa e, al pa i de la base de que las acciones son p ome edo as, UCB1 ga an iza que no se desca en p ema u amen e acciones que pod ´ıan se p ome edo as en un u u o. Es o omen a la b´usqueda de nue as soluciones y ambi´en pe mi e una co ec a adap aci´on al en o no. Es e algo i mo es uno de los m´as ep esen a i os den o de los es oc´as icos, ya que ealiza explo aci´on adap a- i a y mues a in ui i amen e c´omo un bandido mul i-b azo a a de encon a un equilib io en e la explo aci´on y la explo aci´on. Adem´as, su escalabilidad a dis in as aplicaciones es o o ac o impo an e que juega a a o de es e algo i mo. Debido a su idiosinc asia, UCB1 es ampliamen e usado y es incluso aplicable a los bandidos con ex uales; es po ello que en las secciones pos e io es se ha ´a uso del algo i mo UCB1 en p oblemas m´as complicados que conside en el con ex o. 20 5. Bandidos An agonis as Es a subsecci´on es ´a o ien ada a de ini el p oblema de los bandidos an agonis as con el obje i o de iden- i ica es e escena io en las aplicaciones eales que se expond ´an como abajo p incipal de es a in es igaci´on. Se ´a de g an u ilidad conoce las especi icaciones de dos algo i mos, Hedge y Exp4, ya que se ´an pues os en p ´ac ica en las aplicaciones que culminan es e abajo. En los bandidos es oc´as icos, la unci´on de ecompensas es es ´a ica con espec o al paso de las ondas. En cambio, en el p oblema de bandidos an agonis as la unci´on de ecompensas es din´amica, en el sen ido de que cambia con el paso de las ondas bajo la in luencia de un ad e sa io o an agonis a. Pa a ilus a es e nue o escena io se plan ea un p oblema en el que, dada una ed de ciudades y ca e e as, en cada onda el obje i o es encon a el camino, en endido como un b azo del bandido, m´as e icien e pa a un en ´ıo de paque es con una ciudad o igen y o a des ino. Adem´as, se supone que la longi ud de odas las ca e e as es igual pa a hace m´as sencilla la explicaci´on. Se con empla una unci´on de ecompensas de e minis a que, en unci´on de las ciudades de o igen y des- ino, jun o con la elecci´on de u a del algo i mo, asigna una ecompensa de ‘1’ al camino m´as e icien e y ‘0’ a cualquie o a u a. De odas o mas, se pod ´ıa hace uso de una unci´on de ecompensas alea o ias sin que a ec ase a la comp ensi´on del escena io de los bandidos an agonis as, al y como se comen a ´a m´as adelan e. Se oma la siguien e ed pa a ealiza es a explicaci´on: 1 2 3 4 Figu a 3: Red de ciudades y ca e e as. Sup´ongase que se pide al algo i mo encon a el camino m´as ´apido pa a i desde la ciudad o igen 1 a la ciudad des ino 4. A pa i de la igu a 3 se dis inguen dos ´unicos caminos posibles: el azado 1-2-4, que se designa ´a como “camino 1”, y el azado 1-3-4, denominado “camino 2”. La cla e del p oblema, sin ene en cuen a las longi udes, se encuen a en la exis encia de a iables que el al- go i mo no es capaz de con ola . La p esencia de es as a iables ep esen a la p esencia de un an agonis a en el p oblema de bandidos. En es e caso, la conges i´on de las ca e e as es el an agonis a. Es a a iable desconocida pa a el algo i mo, que se supone que oma alo es dis in os en cada onda, modi ica el compo amien o de las ecompensas de cada onda sin que el algo i mo sea conscien e. En consecuencia, ya no hab ´a un camino m´as e icien e que o o siemp e, sino que la e iciencia de los caminos cambia en cada onda seg´un las conges iones. Po an o, el algo i mo, cuyo obje i o es ap ende el camino m´as e icien e dado un ayec o, obse a ´a en alg´un momen o que el camino que ha conside ado como m´as e icien e has a ese momen o deja ´a de se lo, y debe ´a conside a o o camino como el m´as e icien e. Como apun e adicional, la conges i´on es una medida que elaciona la ocupaci´on de la ca e e a con su capacidad, pe o es o aho a no es ele an e po que se oma la conges i´on como un da o di ec o que no iene que se calculado. Pa a comp oba que la conges i´on hace a ia las ecompensas que de uel en los caminos en e ondas, se plan ea que en la onda 1 la conges i´on de las ca e e as 1-2, 1-3, 2-4 y 3-4 es 8, 3, 4 y 1 espec i amen e, y que en la onda 2 la conges i´on es 3, 6, 4 y 7, ambi´en espec i amen e. Es a sucesi´on de conges iones se epi e desde la onda 3 en bucle. De es a o ma, la conges i´on o al expe imen ada en el “camino” 1 iene un alo de 12 en las ondas impa es y de 7 en las ondas pa es. En cuan o al “camino 2”, su conges i´on es de 4 en las ondas impa es y de 13 en las pa es. Po an o, en las ondas pa es las ecompensas se ´an de ‘1’ pa a el camino 1 y de ‘0’ pa a el camino 2, mien as que en las ondas impa es las ecompensas se ´an de ‘1’ pa a el camino 2 y de ‘0’ pa a el camino 1. Es deci , como se ha que ido demos a desde el p incipio, es e es un escena io en el que el p oblema plan eado es de bandidos an agonis as po que las ecompensas pueden a ia en e ondas debido a la p esencia de un 21 an agonis a que el algo i mo no puede con ola . La explicaci´on m´as ´ecnica del p oblema a gumen a que las ecompensas asociadas a cada camino no pueden modeliza se median e una dis ibuci´on es aciona ia, po lo que se ´ıa necesa io un conjun o m´as so is icado de supues os es ad´ıs icos. En gene al, puede se di ´ıcil o imposible de e mina los supues os es ad´ıs icos co ec os pa a un dominio dado, y algunos dominios pueden mos a un al o g ado de ince idumb e. Algunos ´ambi os pueden p esen a dependencias has a el pun o de que no esul e ap opiado aplica ales supues os. De es a o ma, en p oblemas en los que la ecompensa se gene e de una mane a m´as compleja o pseudo-alea o ia y no se sepa cla amen e qu´e alo a a oma , hab ´a que ecu i a conside a que la ecompensa depende de ac o- es ajenos desconocidos pa a el algo i mo, que ep esen a ´an el papel de an agonis a es udiado en es a secci´on [6]. A la ho a de explica los bandidos an agonis as, muchos au o es como Aleksand s Sli kins en [2] hacen hincapi´e en la idea de que en es os bandidos las ecompensas a ´ıan como si es u iesen decla adas po un ad- e sa io con la in enci´on maliciosa de as idia al algo i mo. Es com´un en e los au o es que explican es a idea que compa en es e ipo de p oblema con una casa de apues as en la que las ecompensas han sido de inidas po un ad e sa io, la casa de apues as, con in enci´on de que el jugado ob enga la m´ınima ecompensa. Es o puede lle a a con usiones al lec o debido a una inco ec a gene alizaci´on. Es deci , de ´as de las ecompensas a ian es de los bandidos ad e sa ios no iene po qu´e habe una mala in encionalidad. Es cie o que es una aba pa a el algo i mo, pe o puede no se malin encionada. De hecho, en el ejemplo conside ado an e io men e pa a explica los bandidos an agonis as no exis e ninguna in enci´on de as idia de ´as de la a iabilidad de las ecompensas, sino que es ´a p esen e la conges i´on como una a iable desconocida pa a el algo i mo que al e a la unci´on de ecompensas, pe o en ning´un caso los alo es de la conges i´on de las ca e e as es ´an suges ionados po alg´un ad e sa io con mala in enci´on. Una ez explicado el concep o de ecompensas din´amicas que di ie e de las ecompensas es ´a icas IID de los bandidos es oc´as icos, es impo an e sabe que exis e o a di e encia m´as en e las ecompensas es oc´as icas y las an agonis as. Es a di e encia a iende a que las ecompensas es oc´as icas IID, po no ma gene al, son alea o ias debido a que es ´an siemp e desc i as po una dis ibuci´on de p obabilidades, mien as que en las ecompensas en un escena io an agonis a no hay ninguna especi icaci´on, es deci pueden se de e minis as o alea o ias. Cabe des aca que las ecompensas es oc´as icas pueden se de e minis as si su dis ibuci´on es i ial y solo pe mi- e un alo . Las ecompensas de e minis as, po su p opia de inici´on, es ´an desc i as de o ma de e minada, sin alea o iedad. Es o que se acaba de comen a iene un e ec o di ec o en el an´alisis del emo dimien o de los p oblemas an agonis as po que obliga a dis ingui en e si la unci´on de ecompensas es de e minis a o alea o ia. An es de explica el emo dimien o, es e abajo conside a, al igual que los de o os au o es, que la mejo o ma de abaja con bandidos an agonis as es con cos es en luga de con ecompensas. Es deci , se en iende que lo que el algo i mo ob iene po la elecci´on de un b azo es un cos e. De es a o ma, el obje i o del algo i mo es educi el cos e ob enido y, po an o, se a on a la explicaci´on del emo dimien o desde el pun o de is a de los cos es ob enidos. De odas o mas, si el p oblema plan eado se basa en la ob enci´on de ecompensas se puede ealiza una con e si´on sencilla pa a que el p oblema se base en la ob enci´on de cos es en su luga . Es a con e si´on se cimien a en la idea de que las e siones de p´e dida y ganancia son sim´e icas, en el sen ido de que se puede aslada el an´alisis de una a o a median e la equi alencia: li, = 1 −gi, , donde li, es el cos e asociado al b azo ien la onda ygi, es la ecompensa asociada al b azo ien la onda . Po ejemplo, en el plan eamien o de la ed de ciudades y ca e e as plan eado an e io men e, si se asume que las ecompensas es ´an aco adas en el in e alo [0,1] y la ecompensa de elegi el “camino 1” en la onda 1 es 0,3, el cos e equi alen e a dicha ecompensa es 0,7. El emo dimien o asociado a un p oblema de bandidos an agonis as es un aspec o complejo de en ende . Pa a un en endimien o igu oso y eniendo en cuen a que, a a´ız de la exis encia de ecompensas din´amicas, no hay un solo b azo ´op imo como en el caso de los bandidos es oc´as icos, sino m´as bien una secuencia ´op ima de b azos, el concep o de emo dimien o con ola ´ıa la di e encia en e el cos e que ealmen e ha ob enido y el cos e que se hab ´ıa acumulado si el algo i mo hubie a seguido en odas las ondas la es a egia ma cada po es a secuencia ´op ima de b azos [8]. En es e abajo, al igual que en los del es o de au o es, no se a a llega an lejos en el an´alisis y se a a ealiza igual que en el en o no es oc´as ico. Es deci , se a a conside a que s´ı exis e un ´unico b azo ´op imo a lo la go de odas las ondas. Po an o, el emo dimien o exp esa la di e encia 22 en e el cos e ob enido po el algo i mo y el cos e que pod ´ıa habe se ob enido si el algo i mo hubie a jugado en odas las ondas el b azo ´op imo. Se conside a una “ abla de cos es” c (a) que indica el cos e pa a un b azo a∈Ken la onda ∈T: Si la unci´on de cos es es de e minis a, el cos e o al de cada b azo aes cos e(a) = PT =1 c (a). In ui i a- men e, el b azo ´op imo a∗es el b azo con el cos e o al m´as bajo. Fo malmen e, a∗:= a g m´ına∈[K]cos e(a). Po es as azones, el emo dimien o con cos es de e minis as se exp esa como: R(T) = T X =1 c (a )−m´ın a∈[K]cos e(a) Si los cos es son alea o ios, el b azo ´op imo a∗es el b azo con el cos e espe ado o al m´as bajo. Fo - malmen e, a∗:= a g m´ına∈[K]E[cos e(a)], conociendo la dis ibuci´on de p obabilidades que desc ibe el compo amien o de los cos es de cada b azo. Po an o, el emo dimien o en es e caso queda de inido po : R(T) = T X =1 c (a )−m´ın a∈[K]E[cos e(a)] T as habe expues o es os aspec os undamen ales, se a a un pun o cla e: las a iedades de an agonis as que pueden da se, en endiendo como an agonis a aquellas a iables desconocidas pa a el algo i mo que p o ocan la a iaci´on de la unci´on de ecompensas. Dependiendo de los conocimien os del ad e sa io, se conside an dos ipos di e en es: Si el an agonis a no conoce las elecciones de b azo del algo i mo se denomina indi e en e. Po an o, la a iaci´on que eje ce sob e las ecompensas no depende del compo amien o pasado del algo i mo. Po ejemplo, el escena io plan eado al inicio de es a subsecci´on se ca ac e iza po la p esencia de un an agonis a indi e en e po que el alo de las conges iones es independien e de las elecciones p e ias del algo i mo. En cambio, el an agonis a adap able o lexible, como su p opio nomb e indica, es un an agonis a que es conocedo de las elecciones pasadas del algo i mo y puede a ia as cada onda la con igu aci´on de la unci´on de ecompensas seg´un los b azos escogidos po el algo i mo en las ondas an e io es. Po ejemplo, en un casino ama˜nado, el p opie a io puede obse a la o ma en que apues a un jugado pa a dise˜na secuencias de ganancias maliciosas que ayan a con aco ien e de las es a egias del jugado [4]. Independien emen e de los ejemplos an e io es, la malin encionalidad no es un equisi o obliga o io ni en el an agonis a indi e en e ni en el an agonis a adap able. Debe queda cla o que la p esencia de es a ca ac e ´ıs ica no a ec a al an´alisis del p oblema. 5.1. P ime In en o de Soluci´on Dicho es o, un p ime en oque pa a esol e un p oblema de bandidos an agonis as pod ´ıa se el empleo de un algo i mo de e minis a b´asico. A con inuaci´on, se mues a un ejemplo: Algo i mo 5.5 Algo i mo Segui al L´ıde 1: Inicializa : Juegue cada b azo una ez pa a ob ene una es imaci´on inicial de los cos es. 2: o cada onda = 1,2, . . . do 3: Selecciona el b azo con el cos e acumulado m´as bajo has a el momen o: a = a g m´ınaP −1 s=1 cs(a). 4: Juga el b azo seleccionado a y obse a el cos e incu ido. 5: Ac ualiza el cos e acumulado del b azo a . 6: end o Es e algo i mo siemp e selecciona el b azo con el cos e acumulado m´as bajo en cada onda. Sin emba go, es e algo i mo no es e icaz pa a es e p oblema. Es o se debe a que, como expone [2], incluso un an agonis a indi e en e puede as idia el algo i mo si conoce su es a egia an es de empeza , aunque no sea sabedo de sus elecciones du an e las ondas. Pod ´ıa ap o echa es e conocimien o pa a manipula los cos es de los b azos y 23 o za al algo i mo a oma decisiones sub´op imas. Pa a demos a lo se plan ea esol e un p oblema b´asico en el que solo hay dos b azos A y B con el algo i mo Segui al L´ıde . Adem´as, se supone que el an agonis a p esen e en es e p oblema es conscien e de la es a egia que el algo i mo a a lle a a cabo. Al conoce la es a egia, el an agonis a pod ´ıa dise˜na la siguien e unci´on de cos es: En la p ime a onda, el an agonis a asigna un cos e de 0.5 a A y un cos e de 1 a B (cos e acumulado de A <cos e acumulado de B). El algo i mo, como no iene e e encias de los cos es acumulados de cada b a- zo, elige de o ma alea o ia el b azo A, po ejemplo. En es e caso, el algo i mo ha escogido el b azo m´as e icien e. En la segunda onda, el algo i mo elige A po que iene el cos e acumulado m´as bajo. Sin emba go, el an a- gonis a sabe que el algo i mo a a elegi el b azo A en la segunda onda po que es conscien e de que el b azo con meno cos e acumulado as la p ime a onda es dicho b azo. Po ello, asign´o o os alo es a los cos es de la onda 2 de modo que el b azo A u iese un cos e asociado de 1 y el b azo B un cos e asociado de 0. El algo i mo ha elegido el b azo menos e icien e es a ez. En la e ce a onda, el algo i mo cambia de b azo de nue o y op a po el b azo B ya que iene meno cos e acumulado (1,5>1), pe o como el an agonis a lo pod´ıa an icipa , cambi´o la unci´on de cos es pa a que en la onda 3 el b azo A u iese cos e 0 y B cos e 1. De es a mane a, el algo i mo ha uel o a selecciona de nue o el b azo menos ´op imo po segunda ez consecu i a. Ya en la cua a onda, el algo i mo p e ie e el b azo A po que aho a es el que iene menos cos e acumulado has a el momen o (1,5<2), de nue o el an agonis a sab´ıa que es o a a sucede y o o g´o, pa a la onda 4, al b azo A un cos e de 0 y al b azo B un cos e de 1. Es a ya es la e ce a ez que el algo i mo pie de en e al an agonis a. T as expone el ejemplo an e io , se comp ende, bajo la p emisa de que el ad e sa io descub e la es a egia de elecci´on de b azos del algo i mo, que el ad e sa io puede o za al algo i mo a oma decisiones equi ocadas cada onda. Conc e amen e, se obse a que el algo i mo nunca se ´a capaz de iden i ica cu´al de los dos es el b azo que o ece los cos es ´op imos. Po an o, a pa i de la segunda onda, aunque pod ´ıa habe sido a pa i de la p ime a onda si la elecci´on alea o ia del algo i mo hubiese sido el b azo peo en luga del mejo , el algo i mo elige el b azo con mayo cos e en odas las ondas pos e io es ya que es enga˜nado po el an agonis a. Si se conside a que cada onda iene una unidad de emo dimien o po que en cada onda el meno cos e es 0 y el m´aximo es 1, al cabo de T ondas su emo dimien o se ´a de Tunidades ya que su e el m´aximo cos e en odas las ondas. El emo dimien o en es a si uaci´on se puede exp esa de la siguien e o ma: R(T) = O(T) Es e emo dimien o, como ya se i´o en la secci´on de los bandidos es oc´as icos 4, e leja la incapacidad de ap en- dizaje o al po pa e del algo i mo. Es deci , el peo o m´aximo emo dimien o posible. 5.2. Algo i mos E ec i os La idea cla e pa a so ea es a di icul ad es a˜nadi alea o iedad a la selecci´on del b azo a juga . De es e modo, el algo i mo puede “so p ende ” al ad e sa io e impedi se manipulado po el an agonis a, e go, no se alcanza ´an emo dimien os an al os. Es e e ec o so p esa bas a pa a ob ene un emo dimien o esencialmen e an bajo como el emo dimien o en el modelo es oc´as ico. 5.2.1. Algo i mo Hedge Po es e mo i o, se p ocede a explica un algo i mo muy conocido en el escena io de bandidos an ago- nis as que inco po a es a alea o iedad mencionada, el algo i mo Hedge 6 ob enido de [2]. En inanzas, el ´e mino “hedge” se e ie e a una es a egia de in e si´on que se u iliza pa a educi o elimina el iesgo de p´e didas en una posici´on o ca e a de in e si´on. La idea de ´as del hedging es p o ege una in e si´on con a posibles mo imien os des a o ables en el me cado, lo que puede ayuda a minimiza las p´e didas en 24 ALGx, se alcanza ´ıa un emo dimien o de la siguien e magni ud: E[R(T)] ≤O(KT log T)1/2. Po lo que el emo dimien o pa a odos los con ex os se ´ıa la suma del emo dimien o alcanzado po odas las ins ancias. 6.1.1. Recomendado de Pel´ıculas pa a Cua o G upos Con el obje i o de en ende es e algo i mo, se ha desa ollado una implemen aci´on basada en es a p emisa de usa pocos con ex os e ins ancias pa a cada uno de ellos. Conc e amen e, se a a de un sis ema ecomen- dado pa a un educido n´ume o de con ex os, 4, y cada uno es conside ado como un g upo de pe sonas. En el g upo x1hay homb es de m´as de 40 a˜nos, en el g upo x2hay muje es de m´as de 40 a˜nos, en el g upo x3hay homb es de menos de 40 a˜nos y en el g upo x4hay muje es de menos de 40 a˜nos. Con es a simpli icaci´on y un n´ume o an educido de g upos se puede ilus a co ec amen e es e caso. Los b azos del sis ema ecomendado son pel´ıculas, y son siemp e las mismas 5 pel´ıculas, K= 5. Tambi´en cabe se˜nala que hay T ondas, siendo un pa ´ame o a bi a io de acue do al expe imen o, y en cada onda se ecomienda una pel´ıcula a un usua io, po lo que cada una de las ondas ep esen a un unsua io con una in o maci´on con ex ual, es o es, un usua io que pe enece a un g upo. Po ejemplo, en la onda uno se iene que ecomenda una pel´ıcula a un homb e mayo de 40 a˜nos y en la onda 2 a una muje de menos de 40, y as´ı sucesi amen e. Po ´ul imo, hay que se˜nala que las ecompensas son ob enidas alea o iamen e pa a cada pel´ıcula, b azo, y pa a cada con ex o, g upo. Las ecompensas pueden ene es alo es [0, 0.6, 1]: siendo 0 si una pel´ıcula no le gus a nada al usua io, 0.6 si le gus a un poco y 1 si le gus a mucho. Las ecompensas se calculan alea oa iamen e ya que no hay da os eales. Se u iliza una unci´on c eada po los au o es que calcula las p obabilidades alea o ias pa a cada g upo de usua ios y pa a cada b azo, y den o de es e con ex o se gene an es p obabilidades que suman 1 y ep esen an lo que le puede gus a la pel´ıcula. Realmen e las p obabilidades de que a un g upo de usua ios le gus e una pel´ıcula u o a se calculan de o ma alea o ia ya que lo in e esan e de es e apa ado es ene di e en es gus os pa a las pel´ıculas de cada g upo de usua io. Haci´endolo de es a mane a, se asegu a que al g upo de usua ios 1 es m´as p obable que les gus e una pel´ıcula A, mien as que al g upo de usua ios 2 hab ´a m´as posibilidades de que les gus e una pel´ıcula D. Es necesa io pa i de es a p emisa de que cada con ex o, g upo de usa ios, iene di e en es gus os, o lo que es lo mismo, dis in as unciones de p obabilidades, ya que al hace lo es posible es udia c´omo de bueno es es e algo i mo ecomendando pel´ıculas pa a cada g upo de usua ios con dis in as p e e encias. Sin emba go, s´ı que puede habe dos g upos de usua ios que engan una dis ibuci´on de ecompensas pa ecidas, al y como pod ´ıa pasa si se analizan los gus os de pel´ıculas de dos g upos en la ida eal. Pos e io men e, du an e la simulaci´on, se ex ae una p obabilidad alea o ia pa a un b azo elegido en un con ex o obse ado y usando su dis ibuci´on de p obabilidades, calculada an e io men e, se ob iene una ecom- pensa den o del ango mencionado que es elegida alea o iamen e pe o en la dis ibuci´on de p obabilidades del b azo en el con ex o. Pa a ilus a mejo c´omo es la unci´on de ecompensas se expone un ejemplo. Dado el con ex o 2, muje es de m´as de 40 a˜nos, y el b azo 1, la pel´ıcula A, hay una dis ibuci´on de p obabilidades gene ada alea o iamen e que pod ´ıa se de la siguien e o ma: 25 % a que no le gus a la pel´ıcula, 35 % a que le gus a un poco y 40 % a que le gus a mucho. Si en la onda apa ece un usua io de es e con ex o y se elige el b azo 1, se coge ´a uno de los es posibles alo es alea o iamen e de la ecompensa con o me a es a dis ibuci´on, pe o al simula m´ul iples ondas, a pesa del ac o de alea o iedad, a la la ga se ob end ´a el 25 % una ecompensa de 0, el 35 % una ecompensa de 0.6 y el 40 % una ecompensa de 1. Es impo an e conside a que la unci´on de ecompensas pe manece ´a cons an e. Po ejemplo, es o signi ica que dicha unci´on de ecompensas pa a muje es de m´as de 40 a˜nos se ´a igual pa a las pel´ıculas A que se les mues en, sus gus os po dicha pel´ıcula se ´an iguales pa a odas las ondas, y hab ´a un 40 % de p obabilidades de que le gus en mucho la pel´ıcula A en la onda 1 y en la onda T−1. Aplicando el algo i mo de bandidos mul i-b azo con ex uales pa a es e caso de uso, se han de inido cua o ins ancias del algo i mo UCB1 de mane a que cada ins ancia a a un g upo. U ilizando es a ´ecnica es posible consegui que la ins ancia 1 se especialice en encon a cu´al es el mejo b azo (pel´ıcula) pa a el g upo de a ones mayo es de 40 a˜nos mien as que la ins ancia 2 busca ´a dicho b azo pa a muje es de m´as de 40 a˜nos. Es o pe mi- e que cada ins ancia explo e y explo e de mane a di e en e las pel´ıculas seg´un las p e e encias de es os usua ios. Po ejemplo, la ins ancia uno del algo i mo UCB1 que a a a a ones mayo es de 40 a˜nos pod ´ıa explo a 31 mucho desde las p ime as ondas la pel´ıcula C si obse a que le da muy buenos esul ados en compa aci´on con el es o de pel´ıculas. Po o o lado, la ins ancia que a e a las muje es de menos de 40 a˜nos pod ´ıa cen a se m´as en la explo aci´on si hay es pel´ıculas: A, B y D que le epo an ecompensas simila es. De es e modo, es ap eciable que cada ins ancia adecua ´a su explo aci´on-explo aci´on de mane a ´unica pa a adcua se a la unci´on de p obabilidades del g upo de usua ios que a a. T as de ini el undamen o de es os algo i mos, se con empla ´an cu´ales ue on los pasos a segui pa a imple- men a es e ejemplo. En p ime luga , se c ea una base de da os sin ´e ica, alea o iamen e o denada de 10000 pe sonas, es deci , T= 10000 ondas. Las dis ibuciones en cada g upo son elegidas alea o iamen e, pudiendo habe un g an po cen aje de un g upo y un peque˜no po cen aje de o os pa a e c´omo se desen uel e el bandido con ama˜nos de g upos dis in os. Cabe menciona que, al y como es ´a siendo explicada es a secci´on, en es e caso las palab as g upos y con ex os son sin´onimos, al igual que pel´ıculas y b azos. Despu´es de habe ob enido los usua ios con su con ex o, ha sido implemen ado el algo i mo UCB1 [de acue do al esquema del algo i mo 2.5]. El algo i mo consis e esencialmen e en dos unciones undamen ales. P ime o iene que selecciona un b azo usando el en oque op imis a, seg´un el alo UCB, que se calcula con la ecompensa media, y ep esen a la explo aci´on, y con el adio de con ianza, que ep esen a la explo aci´on. As´ı el algo i mo busca el balance pa a cada g upo de pe sonas de explo a o explo a . Tambi´en el algo i mo debe ac ualiza la ecompensa media pa a cada b azo, y se hace es a ope aci´on as ob ene una ecompensa pa a el b azo ob enido. Es o se ac ualiza pa a que en las p ´oximas ondas se engan en cuen a los alo es ac ualizados pa a la selecci´on de b azo. Una ez hechos odos es os pasos (la c eaci´on de usua ios, el algo i mo UCB1 y la unci´on de ecompensas), ha sido ealizada una simulaci´on pa a obse a la ac uaci´on del algo i mo con ex ual. Como lo que se p e ende es en ende c´omo de bueno es su endimien o, se compa an sus ecompensas y emo dimien o con un algo i mo UCB1. Po lo an o, po un lado es ´a el algo i mo con ex ual que son cua o ins ancias del UCB1, una pa a cada con ex o, y po o o lado se encuen a el algo i mo UCB1 que a a odos los da os po igual y no dis ingue con ex os. Es e segundo algo i mo ecomenda ´a po igual a pe sonas del g upo 1 y del g upo 4 po lo que lo que ealmen e se es udia ´a aqu´ı es cu´al es el alo de conside a la in o maci´on con ex ual. Pues bien, se pod ´a obse a en las siguien es g ´a icas que mues an el endimien o de ambos bandidos du an e una simulaci´on de 10000 usua ios. Adem´as debe ene se en cuen a que el bandido UCB1 puede usa se como una ep esen aci´on del endimien o de un bandido es oc´as ico en e a un bandido con ex ual, y as´ı se pod ´a ap ecia c´omo de impo an e es el con ex o pa a dos algo i mos que ienen la misma es uc u a. Figu a 5: Recompensas medias y emo dimien os medios. En ambas g ´a icas se puede obse a la e oluci´on de las ecompensas ob enidas pa a ambos algo i mos: el bandido con ex ual y el UCB1 que es un bandido es oc´as ico. Se puede ap ecia como aumen a conside able- men e la ecompensa en es os bandidos que conside an el con ex o y p oduce una dis ancia signi ica i a en e la ecompensas y los emo dimien os ipos. Adem´as, se mues a como a lo la go de las ondas los dos bandidos an mejo ando su endimien o ya que ap enden, pe o los bandidos con ex uales ap enden m´as ´apido al p in- cipio y po el hecho de ene en cuen a el con ex o alcanzan mejo es ecompensas y, consecuen emen e, meno 32 emo dimien o. G acias a es os esul ados, po p ime a ez apa ece la u ilidad del con ex o pa a mejo a el endimien o de los bandidos mul i-b azo. Y adem´as, es des acable que es e es un en oque in ui i o pa a ilus a las en a- jas de p ime a mano de los bandidos mul i-b azo con ex uales. Como conclusi´on, los esul ados son m´as que sa is ac o ios y p esen an un ho izon e p ome edo pa a el desa ollo de bandidos con ex uales en pos e io es aplicaciones p ´ac icas. A pesa de es o, se pod ´ıa pensa que la dis ibuci´on de la poblaci´on, es deci , el n´ume o de pe sonas de cada uno de los cua o g upos puede a ec a signi ica i amen e a las ecompensas ob enidas, ya que el n´ume o de usua ios que pe enece a un g upo es ob enido alea o iamen e. Po es e mo i o, la misma simulaci´on ha sido ealizada pa a cien dis ibuciones o bases de da os dis in as, habiendo en cada una de es as 10000 pe so- nas epa idas alea o iamen e en e los 4 g upos. Al usa es e en oque, se pod ´a e si ealmen e los bandidos con ex uales son mejo es pa a dis in as dis ibuciones de los usua ios, y si son e icien es en dis ibuciones con dis in os po cen ajes de usua ios de un g upo. En es e an´alisis, se obse a ´a el endimien o de es e algo i mo pa a dis ibuciones en las que pod ´a habe pocos miemb os de g upo de usua ios. As´ı, se es udia ´a si usa un bandido con ex ual puede se un opci´on in e esan e aunque pudiese habe pocos usua ios de un cie o g upo y, en es e caso, el ap endizaje de la ins ancia co espondien e se e ´ıa pe judicado. Po ello, es signi ica i a es a cues i´on. Los esul ados son p opo cionados en las siguien es g ´a icas. Figu a 6: Resul ados pa a dis in as dis ibuciones de usua ios. Cabe menciona que es as ´ul imas g ´a icas mues an las ecompensas acumuladas pa a cada base de da os, es ando una base de da os compues a po 10000 usua ios y siendo la ecompensa m´axima 10000, el n´ume o de usua ios po la ecompensa m´axima, que es 1. Se puede a i ma con o al i meza que los esul ados son p ome edo es pa a dis in as dis ibuciones, y pa a una can idad su icien e de da os, la dis ibuci´on de los con ex os no es ning´un p oblema pa a los bandidos con ex uales. Gene almen e el bandido con ex ual es m´as e icaz que un bandido es oc´as ico, al y como e lejan los da os de ecompensas y emo dimien os. Po o a pa e, el ´ul imo expe imen o desa ollado en es a secci´on ha sido pa a e en qu´e medida in luyen el n´ume o de con ex os pa a e alua el endimien o del bandido. Debido a es o, se supone que en ez de cua o g upos de pe sonas o cua o con ex os, hay di e sos n´ume os c ecien es de con ex os pa a comp oba si es e bandido con ex ual, en ocado a pocos con ex os, segui ´ıa ob eniendo mejo es ecompensas pa a muchos con ex- os espec o a un bandido es oc´as ico como el UCB1. Es a ´ul ima pa e de la secci´on a oja ´a esul ados de e minan es espec o a la compa aci´on en e bandidos con ex uales y bandidos es oc´as icos y, en de ini i a, conclui ´a po p esen a las en ajas de es os bandidos en una p ime a ins ancia. En la igu a 7 es ´an ep esen ados los esul ados de un bandido con ex ual en e a un bandido es oc´as ico pa a di e en es ama˜nos del con ex o. Los b azos y la o ma de ob ene la ecompensa no han a iado espec o al inicio de la implemen aci´on, pe o pa a u iliza a ios ama˜nos de con ex os se han enido que ealiza algunas 33 Figu a 7: Resul ados al aumen a el n´ume o de con ex os. modi icaciones. Pa a ello, se han c eado al igual que an es dis ibuciones de 10000 usua ios y 150 simulaciones, habiendo pa a cada una de es as dis ibuciones un n´ume o de con ex os dis in os. Es o signi ica que pa a cada una de las 150 simulaciones se ha p obado con un ama˜no dis in o del con ex o, y pa a cada ama˜no se han ecomendado pel´ıculas a 10000 usua ios. De es a mane a, se obse a ´an las ecom- pensas medias si hubie a 4 g upos de usua ios y se les sugie en pel´ıculas a odos ellos. Tambi´en se analizan las ecompensas medias si hay 10 g upos de usua ios, 100 g upos, 500 g upos... As´ı has a los 10000.. Realmen e ha sido ealizado el mismo p oceso de ecomendaci´on a 10000 usua ios pe o 150 eces, y en cada una de es as e- ces los usua ios se di iden en menos o m´as g upos. De es e modo, se puede e c´omo in luye el ama˜no del g upo. Es a simulaci´on se ealiza ´a 150 eces y en cada una de las i e aciones se usa un n´ume o de con ex os dis in os. Pa a e ealmen e el e ec o del n´ume o de con ex os se plan ea la siguien e l´ogica: se comienza con cua o dis in os con ex os al igual que an es, y a aumen ando el n´ume o de con ex os has a llega al ama˜no de la dis ibuci´on, es deci , 10000, un con ex o dis in o pa a cada usua io. Conc e amen e, los 150 ama˜nos de con ex os dis in os se encuen an uni o memen e di ididos desde 4 has a T, que es 10000. Los esul ados son escla ecedo es y con i man las e idencias que se es ´an exponiendo a lo la go de es e apa - ado. Es se˜nalable que el endimien o de ambos bandidos es mejo pa a pocos con ex os, y con o me aumen a el n´ume o de dis in os con ex os, ambos bandidos ob ienen peo endimien o, cosa que se e e lejada en las ecompensas medias y en las p´e didas, emo dimien os medios. Adem´as, hay una g ´a ica adicional pa a e la di e encia en e emo dimien os y con su ayuda se en iende pe ec amen e que el bandido con ex ual siemp e alcanza menos emo dimien o que el es oc´as ico, e go el endimien o de un bandido con ex ual es conside able- men e supe io . Po ello, si se compa an es ic amen e el UCB con un bandido con ex ual que ins ancie UCBs pa a cada con ex o, es obse able que el endimien o de las ins ancias pa a cada con ex o se ´a supe io . No obs an e, debe ene se en cuen a que si se aumen an el g upo de usua ios has a ene un g upo po cada usua io, es deci , 10000 con ex os, cada ins ancia del UCB1 a a ´a exclusi amen e a un usua io y po lo an o, no ap ende ´a. Po es e mo i o, se obse a en el g ´a ico que pa a muchos g upos de usua ios, y muchas ins ancias del UCB1, el algo i mo no ap ende ya que iene pocos usua ios a los que ecomenda . Adem´as, cabe se˜nala que las mejo es ecompensas se dan al p incipio de la g ´a ica, cuando hay pocos g upos de usua ios y s´ı que hay un espacio no able en e las ecompensas del bandido con ex ual y el bandido es oc´as ico. Y, a pa i de ap oximadamen e los 2000 g upos de usua ios, 5 usua ios po g upo (Kusua ios), las ecompensas son ex emadamen e malas po que ninguno de los algo i mos ap enden pe o el con ex ual sigue ob eniendo una insigni ican e mejo ecompensa media. Debido a es o, los mejo es esul ados son ob enidos usando un n´ume o peque˜no de g upos de usua ios, es deci , educiendo los con ex os. Y ambi´en es as ecompensas se mejo an ap o echando los bandidos con ex ua- les. Es con ienen e eco da que en las p ime as igu as de es a secci´on alcanzaban ecompensas de en e 0,7y0,8. Y pa a conclui , se puede a i ma que en e ec o es e ipo de bandidos con ex uales inde de mane a sob e- salien e en en o nos con pocos con ex os. Adem´as, si e de pe ec a mues a pa a ejempli ica lo in e esan e que puede se desa olla bandidos con ex uales. Conside ando el con ex o es posible desa olla algo i mos m´as ´op imos y ambi´en es udia p oblemas m´as complejos g acias a los bandidos mul i-b azo con ex uales. 34 6.2. Bandidos Con ex uales Lipschi zianos 6.2.1. Mo i aci´on En es a secci´on se conside a una a ian e de los bandidos con ex uales, los lipschi zianos o de ipo Lipschi z. Se a a ´a la mo i aci´on de ´as de es e ipo en conc e o de bandidos con ex uales y cu´ales son sus p incipales ca ac e ´ıs icas. A con inuaci´on, se p ocede ´a a explo a en p o undidad los bandidos con ex uales con la condici´on de Lips- chi z. Es e ma co pe mi e maneja bandidos con ex uales con un g an n´ume o de con ex os. La condici´on de Lipschi z es el eje de es a secci´on. Adem´as, en luga de ene con ex os disc e os pa a elegi (como un n´ume o ini o de opciones), hay con ex os ilimi ados en un espacio con inuo. Es esencial econoce que exis en in ini os con ex os, y es os se encuen an dis ibuidos de o ma con inua. Dada la na u aleza con inua del espacio de con ex os, los p oblemas que in oluc an un n´ume o in ini o de con ex os ep esen an una g an complejidad, ol i´endose inmanejables en muchos casos. No obs an e, el algo- i mo de bandido con ex ual lipschi ziano puede capi aliza es a ci cuns ancia. Se p esume que es posible ubica cualquie con ex o en un in e alo [0,1]. A es e p oceso se le denomina ´a “mapea ”, que e ie e a si ua un con ex o den o de un in e alo de e minado. Se puede pos ula que, de acue do a la condici´on Lipschi z, las ecompensas pueden se in e p e adas en elaci´on a los con ex os median e la u ilizaci´on de una a iable L, conocida como cons an e de Lipschi z, que es econocida po el algo i mo. A con inuaci´on, se p esen a la condici´on de Lipschi z: De inici´on 6.1. Un bandido es Lipschi ziano si cumple con la condici´on: |µ(a|x)−µ(a|x′)| ≤ L·|x−x′|pa a cualquie b azo a, a′∈Ay con ex os x, x′∈X. La condici´on de Lipschi z implica que la di e encia en e las ecompensas medias de un b azo pa a dos con ex os di e en es es meno o igual a la di e encia en e los con ex os mul iplicada po una cons an e L. Si se cumple es a condici´on en un p oblema, se ´a posible disc e iza uni o memen e el espacio con ex ual. La disc e izaci´on es un en oque que pe mi i ´a di idi el espacio con ex ual. Conside ando que exis e un espacio con ex ual donde se pueden ep esen a odos los con ex os posibles, se usa ´a la disc e izaci´on pa a di idi es e espacio en dis in as secciones. De es a mane a, se a a el con ex o obse ado en cada onda como si pe enecie a a una secci´on del espacio de con ex os y cada uno de es os espacios disc e izados se ´a a ado po un algo i mo dis in o. Pa a explica es e p oceso de disc e izaci´on se puede usa un ejemplo muy in ui i o y ep esen a i o. Se puede supone que se quie e es udia la si uaci´on de unos es udian es en unci´on de su no a acad´emica, que puede se del uno al diez. Median e el p oceso de disc e izaci´on, el espacio de posibles con ex os se ´a di idido en: sob esalien e, no able, bien, su icien e o insu icien e. Usando es e en oque, cada uno de los cinco espa- cios disc e izados se ´a a ado con un algo i mo dis in o. Po ello, los es udian es que engan en e un sie e y un ocho se ´an analizados po un algo i mo y los alumnos que engan menos de un cinco se ´an es udiados po o o algo i mo ya que pe enecen a o o espacio disc e izado. U ilizando es a ap oximaci´on, hab ´a algo i mos es- pecializados pa a cada ipo de es udian e, y es o pod ´ıa pe mi i a los algo i mos endi mejo seg´un el con ex o. Las en ajas que o ece es e sis ema es que pa a un g an n´ume o de con ex os, es os se pueden ep esen a en un in e alo a bi a io, mapea . En cada una de las secciones hab ´a un algo i mo especializado en los con ex os que haya en dicha secci´on. Adem´as, la me odolog´ıa se ´a pa ecida al apa ado an e io de pocos con ex os 6.1. Hab ´a una ins ancia de un algo i mo UCB pa a cada espacio disc e izado. En el ejemplo an e io , un algo i mo se enca ga ´ıa de los alumnos de sob esalien e, o o de los de no able, o o de los de bien, uno dis in o de los de su icien e y un ´ul imo de los de insu icien e. Pa a disc e iza se usa la siguien e unci´on: S(x) = m´ın(a g m´ın x′∈S|x−x′|). Con es a o ma de mapea , cada pun o es pues o en una egi´on del espacio disc e izado de acue do a es a unci´on conocida como la unci´on de mapeo. G acias es e mapeo, cada con ex o obse ado en una onda , se ´a ubicado en uno de los con ex os disc e izados, y pa a es e con ex o disc e izado, exis i ´a una ins ancia del algo i mo UCBSque ope a ´a exclusi amen e en dicha zona disc e izada. 35 Con el obje i o de en ende co ec amen e los bandidos con ex uales lipschi zianos, hay que expone una implemen aci´on p opia, y se p o undiza en es a ma e ia. An es de pode ahonda en la implemen aci´on, es imp escindible demos a que se cumple la condici´on de Lispchi z, y el siguien e apa ado se cen a ´a en es a cues i´on. En ´ul imo luga , se mues a el emo dimien o alcanzado pa a es e ipo de bandidos con ex uales. El emo di- mien o ob enido es simila al que alcanzan los bandidos es oc´as icos, pe o es e bandido con ex ual lipschi ziano pe mi e abo da p oblemas complejos que, sin usa la condici´on de Lispchi z, no se ´ıan azables po un bandido mul i-b azo. El emo dimien o es el siguien e: Teo ema 6.2. E[R(T)] ≤T2/3×O(LK log T)1/3. Es e emo dimien o es seg´un el n´ume o de T ondas, el n´ume o de Kb azos y la cons an e Lispchi z L. 6.2.2. Implemen aci´on de Bandidos Con ex uales Lipschi zianos del Me cado A con inuaci´on, se p esen a el desa ollo de la implemen aci´on de bandidos con ex uales de ipo Lipschi z de acue do a las di ec ices expues as en el lib o de Sli kins. Se p ocede ´a a de alla el obje i o de es a im- plemen aci´on, la me odolog´ıa pa a desa olla es a p ´ac ica y las conclusiones ob enidas as ealiza es e abajo. En p ime luga , se de ine cu´al es el undamen o de es a p ´ac ica. Se a a de un sis ema ecomendado que u iliza un bandido mul i-b azo con ex ual lipschi ziano Es e sis ema ecomendado cuen a con dis in as ca e as, que son los b azos, cada ca e a es ´a o mada po un po cen aje dis in o de acciones y bonos, de mane a que hay ca e as que ienen un g an po cen aje de bonos mien as que o as ienen casi odo acciones. Se pa e de la base de que en el siguien e apa ado se analiza y demues a la condici´on de Lipschi z. Es o apa ece en la subsecci´on 6.2.3 donde se demues a que se cumple dicha condici´on. Dicha secci´on es undamen al pa a que se pueda plan ea el p oblema ya que debe da se es a condici´on pa a desa olla el algo i mo adecua- damen e conside ando el con ex o. En es e p oblema, se conside a ´a el con ex o del c ecimien o del me cado y la asa de in e ´es. Se aplica una l´ogica sencilla e in ui i a pa a en ende el uncionamien o de es e ipo conc e o de bandidos. El me cado se ´a educido a dos a iables mac oecon´omicas: el c ecimien o del me cado y la asa de in e ´es, y se juga ´a con dichas a iables pa a explica es e modelo. En un me cado eal es ´a cla o que a ec an innume ables a iables al p ecio de ac i os inancie os como bonos o acciones. Sin emba go, al p escindi de o as a iables, es posible cen a se en un modelo simulado dependien e ´unicamen e del c ecimien o del me cado y la asa de in e ´es pa a pone en p ´ac ica el obje i o de es e cap´ı ulo: la disc e izaci´on pa a desa olla bandidos con ex uales ipo Lispchi z. Respec o a las ca ac e ´ıs icas del me cado inancie o simulado, hay dos a iables que son la asa de in e ´es y el c ecimien o del me cado, y exis en dos ipos de ac i os: los bonos y las acciones. Se conside a ´a que los bonos son ac i os inancie os que o ecen poca en abilidad. Se puede gana poco dine o con ellos, pe o su p incipal en aja es que an e un dec ecimien o del me cado no pie den an o alo como las acciones. Debido a es o, es m´as in e esan e comp a bonos si el me cado es ´a cayendo, en e a acciones. Adem´as, su en abilidad es ´a ligada a la asa de in e ´es que ijan los bancos cen ales. Una ez en endido es o, es posible comp ende que an e una buena asa de in e ´es y un dec ecimien o del me cado es bas an e mejo opci´on comp a bonos que comp a acciones ya que a pesa de que no epo en an os bene icios, son opciones m´as segu as que pueden se m´as bene iciosas en es as si uaciones, o con ex os. Po o o lado, las acciones dependen mucho de la si uaci´on del me cado. En un me cado en expansi´on, o en c ecimien o, se puede supone que las acciones an a subi mucho y o ecen en abilidades muy al as. Al con a io que los bonos, que o ecen ganancias m´ınimas, las acciones p opo cionan bene icios muy buenos. L´ogi- camen e, si el me cado cae, las acciones pe de ´an mucho alo po que al igual que dependen mucho pa a gana , ambi´en bajan mucho si el me cado cae, po eso se dice que luc ´uan mucho. Po ello, an e un c ecimien o al alza del me cado es m´as in e esan e comp a acciones ya que un bono no o o ga ´a apenas bene icios. Pe o con un me cado en decadencia, las acciones pueden hace pe de mucho dine o y los bonos son alo es m´as segu os. Una ez explicado es o, ya es ´a cla a la idea de que con una buena asa de in e ´es son con enien es los bonos pe o que si el me cado c ece las acciones son muy en ado as. Su ge en onces la p egun a de cu´al es la mejo es a egia pa a elegi una ca e a con m´as bonos o m´as acciones seg´un el con ex o: me cado y asa de in e ´es. Es a ´an p esen es los siguien es ipos de ca e a a elegi pa a que el algo i mo pueda juga con las ca e as que mejo le pa ezcan seg´un las condiciones del me cado. 36 B azo 1: 0 % de acciones y 100 % de bonos. B azo 2: 25 % de acciones y 75 % de bonos. B azo 3: 50 % de acciones y 50 % de bonos. B azo 4: 75 % de acciones y 25 % de bonos. B azo 5: 100 % de acciones y 0 % de bonos. Es as cinco ca e as an a pe mi i busca la opci´on ´op ima con o me al con ex o que haya. Como ya se ha explicado, el c ecimien o del me cado a ec a muy posi i amen e a las acciones. Po eso, con un c ecimien o al o del me cado se elegi ´a siemp e el b azo 5, ya que los o os b azos a pesa de que ganen dine o end ´an un emo dimien o muy al o. Igualmen e, an e un me cado en dec ecimien o y una asa de in e ´es al o, el b azo uno epo a ´a g andes ecompensas y el es o de b azos end ´an un emo dimien o signi ica i o. Aho a bien, la cues i´on que se debe plan ea es qu´e b azo usa pa a odos los dem´as con ex os, en los que no haya una asa de in e ´es excesi amen e al o ni un c ecimien o de me cado exage ado. Pues ese es el co az´on de es e p oblema, la elecci´on de la mejo ca e a espec o a un con ex o. Una ez esal ada es a idea, debe se abo dada la unci´on de ecompensas. El mecanismo de ecompensas es el siguien e: se calcula una en abilidad espe ada pa a las acciones y o a pa a los bonos en unci´on de las condiciones del me cado, con ex o. Pos e io men e, se ob iene la en abilidad de la ca e a, b azo, en unci´on del po cen aje de bonos y de acciones, que suman uno. Es deci , con el b azo 4, se mul iplica la en abilidad de las acciones po el 75 % y la en abilidad de los bonos po el 25 %. As´ı, se puede sabe cu´al es la en abilidad o al esul an e de la dis ibuci´on de bonos-acciones. Po ´ul imo, se no maliza ´a y c ea ´a una dis ibuci´on no malizada usando una a ianza asociada a la ca e a, que se calcula de acue do al peso de las acciones y bonos en dicha ca e a. Luego se ob end ´a el alo medio usando dicha des iaci´on y se coge un alo alea o iamen e. Dicho alo medio se ´a no malizado en e 0 y 1 pa a e la en abilidad espe ada espec o al b azo usado en un con ex o dado. Las ecompensas se ep esen an del siguien e modo: las ecompensas es ´an no malizadas en e 0 y 1. Se pa e de un alo de 0.5 como ecompensa. De es e modo, una ecompensa de 0.5 signi ica que ni se ha ganado ni pe dido dine o. Si hay una ecompensa meno de 0.5 e leja ´a que se ha pe dido dine o con la ca e a. Es e suceso se pod ´a epe i en nume osas ocasiones ya que hay si uaciones en las que es muy ´acil pe de dine o. Po el con a io, si se da una ecompensa mayo de 0.5, se hab ´ıa ganado una en abilidad con la ca e a elegida. Si se ob iene una ecompensa de 1, la in e si´on se hab a mul iplicado po dos, mien as que si se llega a 0, se hab ´ıa pe dido la in e si´on comple amen e. Una ez de inido el con ex o y los b azos, hay que explica el uncionamien o de es e bandido con ex ual. Es e sis ema ecomendado elige una ca e a pa a cada in e so , y lo hace pa a Tin e so es, es deci , du an e T ondas. Cada in e so iene un con ex o di e en e, gene ado alea o iamen e, un me cado que a ´ıa desde un 10 % a un −10 % y una asa de in e ´es de 0 has a 8 %. Es os Tin e so es se gene an alea o iamen e en e es os angos y en es e caso, se u ilizan 10000 in e so es pa a e el desa ollo eal del bandido con ex ual ecomen- dando ca e as y ob eniendo ecompensas pa a dis in os in e so es. G acias a que se cumple la condici´on de Lipschi z, se pueden disc e iza los con ex os en un espacio con ex- ual, o mapa, pa a es e bandido con ex ual, donde las coo denadas yson el c ecimien o del me cado y las xla asa de in e ´es. Hab ´a un espacio con ex ual di idido en cuad ´ıculas, donde hay diez ilas y diez columnas en unci´on de es as dos a iables. Usando es a disc e izaci´on se epa e el espacio de con ex os en 100 con ex os disc e izados y pa a cada uno hay una ins ancia del algo i mo UCB1, o ambi´en llamado UCB, de mane a que dicha ins ancia se enca ga de explo a y explo a una ´unica egi´on del espacio con ex ual. De es a mane a, se u iliza la disc e izaci´on de una o ma muy isual ya que es posible imagina se un mapa di ido en cien po ciones; ambi´en si e pa a pode plasma un g ´a ico con los esul ados pa a cada egi´on. Es undamen al se˜nala c´omo ap ende ´a cada una de las ins ancias del algo i mo UCB. Hay que ene en cuen a que cada una de las ins ancias ´unicamen e se u iliza en uno de los 100 con ex os disc e izados, pe o no se usa en ning´un o o con ex o disc e izado. En cada onda una ins ancia decide qu´e b azo, o ca e a, eco- menda y sabe la ecompensa que ha ob enido pa a ese b azo. Consecuen emen e, cada ins ancia del UCB solo ap ende ´a cuando sea llamada. Una ins ancia es llamada cuando se de un con ex o en la onda que encaje en su con ex o disc e izado, es a ins ancia del UCB ha ´a una ecomendaci´on pa a es e con ex o y ap ende ´a de la ecompensa ob enida, pe o el es o de ins ancias no sab ´an ni el b azo que ha elegido ni su ecompensa. Po ello, debe habe el su icien e n´ume o de ondas pa a que cada ins ancia ap enda de sus acciones y elabo e su 37 es a egia de explo aci´on-explo aci´on de acue do a lo que ha ap endido con sus decisiones an e io es. Con el uso de es os bandidos lipschi zianos se es udia un caso de uso dis in o y se saca pa ido a disc e iza con un n´ume o al o de con ex os, 100 en es e caso. Adem´as, se ´a posible ep esen a los posibles con ex os en un mapa, donde cada in e so se ´a a ado po una ins ancia de UCB. Dicha ins ancia conoce a la pe ec- ci´on los alo es en los que se encuen a es e in e so , an o in e ´es como me cado y as´ı conoce la explo aci´on y explo aci´on en esa zona en e b azos, y ap ende a explo a el b azo con el espec i o po cen aje de accio- nes y bonos necesa ios. Po es o, es e sis ema ecomendado aplica es a condici´on pa a ap o echa los con ex os. Al ealiza es a implemen aci´on, se obse a que el algo i mo o ece muy buenos endimien os y ap ende a usa el b azo necesa io pa a cada con ex o median e las ins ancias de UCB (que hay una pa a cada con ex o disc e izado). Adem´as, se puede e que los bonos son menos a iables en la ´o mula calculada y po ello, en las zonas de in e ´es al o se en muy buenos endimien os. Es e bandido con ex ual inde bas an e bien seg´un los esul ados ob enidos. Con la disc e izaci´on y el uso de bandidos con ex uales lipsc hizanos, el algo i mo puede explo a cada zona del con ex o disc e izado con una ins ancia dis in a, que ap ende ´a m´as ´apidamen e a ope a en un con ex o de e minado, con unos alo es de asa de in e ´es y c ecimien o del me cado conc e os. Es as ins ancias sab ´an cu´al es el mejo b azo a aplica en su p opia egi´on y es o pe mi e op imiza un p oblema g acias a la disc e i- zaci´on. T as habe expues o los pila es de es e sis ema, se mos a ´an los esul ados ob enidos, en dos g ´a icas que son u o de la implemen aci´on ealizada en Py hon. Como se puede ap ecia , los esul ados son posi i os y el algo i mo es capaz de no pe de dine o median e la elecci´on del mejo b azo seg´un el con ex o, y ambi´en mejo a con el iempo y se con empla es a cu a de ap endizaje y su mejo ´ıa. Aho a, se obse a ´an los esul ados ob enidos po medio de unos g ´a icos que ilus an c´omo se desen uel e el bandido. Figu a 8: Recompensas medias y emo dimien os medios con bandidos con ex uales lipschi zianos. En es os g ´a icos apa ecen las ecompensas p omedias ob enidas a lo la go de 10000 ondas, y, en con apo- sici´on, ambi´en se e el emo dimien o que es lo que se deja de gana . Cada una de las ondas ep esen a a un in e so , y se obse a un con ex o di e en e. Tal y como se ha de allado an e io men e, las ecompensas e lejan que el algo i mo es capaz de man ene el dine o si la ecompensa es igual a 0.5. Po o o lado, si la ecompensa es supe io a 0.5, el algo i mo es ´a siendo capaz de ob ene una en abilidad eligiendo una buena ca e a. En es e caso, se e que el algo i mo empieza en las p ime as ondas con una a iaci´on muy al a de ecompensas y ya a pa i de la onda 2000, es capaz de elegi los mejo es b azos pa a siemp e ob ene una en abilidad (posi i a) de la ca e a elegida. De hecho, solo al p incipio ob iene una ecompensa media nega i a y pe de ´ıa dine o in e ido. Es o signi ica que con o me a ap endiendo, es capaz de disce ni qu´e ca e a usa seg´un el con ex o pa a ob ene bene icios. La g ´a ica 8 mues a pa a una de e minada onda , la ecompensa media pa a es a onda. As´ı se puede e c´omo a ´ıa la ecompensa media ob enida. Tambi´en se expone el emo dimien o medio, que pe mi e obse a 38 Figu a 9: Mapa de calo pa a cada con ex o disc e izado. si el algo i mo a ob eniendo mejo es ecompensas con o me pasa el iempo. Se puede ap ecia la mejo a con inua en el algo i mo y que ap ende a lo la go de las ondas, y siemp e p opo ciona ecompensas posi i as, es o es mayo es de 0.5 a pa i de la onda 2000. Se obse a lo mismo en el emo dimien o que a disminuyendo con o me a anza la pa ida. Po lo an o, es posible deduci que el algo i mo que ha sido desa ollado ap ende a usa adecuadamen e sus b azos y es capaz de man ene siemp e la en abilidad po encima del 0.5 pa a no pe de dine o, y mejo a con el iempo. Es o es muy impo an e, ya que el algo i mo ope a en si uaciones muy nega i as como un dec ecimieno o del me cado de −7 %, y en es a si uaci´on lo m´as p obable es que con la mayo ´ıa de b azos el bandido pie da dine o, de hecho, as´ı se obse a en las p ime as ondas donde hay en abilidades de 0.3, lo que supone que en esas ondas el algo i mo pie de ap oximadamen e la mi ad de su in e si´on. Es o con as a con su e oluci´on y su ap endizaje que queda e lejado en las cu as de ecompensas y emo dimien o, el bandido es capaz de endi en cualquie con ex o po muy nega i o que sea, y o ece ecompensas posi i as, po lo que su ac uaci´on es b illan e. Es a segunda imagen 9 es muy in e esan e, ya que se obse an las ecompensas medias ob enidas en cada con- ex o disc e izado. Adem´as, pe mi e al lec o e una imagen isual de c´omo se ep esen a el espacio con ex ual seg´un el c ecimien o del me cado y el in e ´es. En es e mapa se en las 100 secciones, o con ex os disc e izados, ca- da uno de es os es a ado po un algo i mo UCBSen unci´on de la asa de in e ´es y el c ecimien o del me cado. Los esul ados mues an lo ya expues o a lo la go de es a secci´on. Con un c ecimien o del me cado muy posi i o, se pueden alcanza ecompensas muy al as debido a la ola ilidad de las acciones, que, hay que e- co da que pueden subi mucho de p ecio. Po el con a io, an e una si uaci´on de una al a asa de in e ´es, las ecompensas simplemen e se man ienen o se gana un peque˜no po cen aje. Es e g ´a ico ilus a muy bien la l´ogica de c´omo unciona el me cado inancie o y a oja luz ace ca de las ecompensas ob enidas po el algo i mo. El uso de un mapa de calo es una al e na i a id´onea en es e caso po que es posible en ende es e modelo de mane a in ui i a. Adem´as, la disc e izaci´on de los con ex os apa ece ep esen ada en es e mapa de calo con sus ecompensas asociadas y se puede in ui c´omo de posi i o a a se el me cado, o cu´an as p obabilidades hab ´a de ob ene una ecompensa posi i a (ganancias) seg´un la in o maci´on con ex ual. 39 Figu a 10: E oluci´on de las ecompensas y emo dimien os p omedios si Tes aumen ado. Po ´ul imo, se pone el oco en la e oluci´on de las ecompensas con m´as ondas Tpa a analiza mejo es e algo i mo y su desempe˜no en el me cado. Se puede e en la igu a 10 que se es anca el c ecimien o de las ecompensas p omedias. A pesa de ello, s´ı que es posible ap ecia que el c ecimien o de las ecompensas medias y ambi´en el dec ecimien o del e- mo dimien o p omedio, mejo a con o me an pasando las ondas, y con i ma es e ap endizaje po pa e de el algo i mo de bandidos con ex uales ipo Lipschi z. T as explica odo es o, se puede conclui ace adamen e que el algo i mo ap ende a usa ca e as con menos o m´as acciones en unci´on del con ex o con el obje i o de maximiza su ecompensa cumpliendo en odo momen- o con la condici´on de Lipschi z. Cabe se˜nala que los esul ados son muy in e esan es po que pe mi en e c´omo pa a un g an n´ume o de con ex os, g acias al cumplimien o de la condici´on de Lipschi z se puede consegui un bandido con ex ual co ec o que puede disc e iza con ex os. Es a implemen aci´on ha cumplido co ec amen e su unci´on de expone un p oblema que puede se esuel o con los bandidos con ex uales lipschi zianos y su p oceso de disc e izaci´on. 6.2.3. Demos aci´on de Lispchi z pa a Bandidos Con ex uales Lipschi zianos A con inuaci´on, se p esen a una explicaci´on de la demos aci´on de que la unci´on de ecompensa cumple con la condici´on de Lipschi z, u ilizando el c ecimien o del me cado y la asa de in e ´es como las a iables del con ex o. Se conside a ´a que la a iable x ep esen a la asa de in e ´es y la a iable yel c ecimien o del me cado. Debe eco da se que en es e p oblema se da un con ex o en cada onda, que se compone de las a iables xey. Hay una ecompensa que ep esen a la en abilidad de una ca e a. Como ya se ha p o undizado en cada de alle de es a implemen aci´on, aho a lo impo an e es demos a que se cumple la condici´on de Lipschi z en es e caso. En el caso de uso del me cado, se p esupone que las ecompensas ienen de e minadas po la asa de in e ´es y el c ecimien o del me cado. En es e escena io de me cado, se asume que las ecompensas es ´an in ´ınsecamen e ligadas a la asa de in e ´es y al c ecimien o del me cado. Pa a simpli ica la explicaci´on, se pos ula que ambas a iables, ponde adas po dos coe icien es dis in os (ayc), que pod ´ıan ep esen a la en abilidad de una ca e a. Dicha unci´on de ecompensas es la siguien e: R(x, y) = a∗x+c∗y, En es e caso, se u iliza la exp esi´on R(x, y) pa a deno a las ecompensas. De es e modo queda la en e que las ecompensas ienen de e minadas po es as dos a iables pe enecien es al con ex o. Pa a demos a que es a unci´on cumple con la condici´on de Lipschi z, debe demos a se que exis e una cons an e L al que: 40 algo i mos, es minimiza el iempo de iaje en cada onda median e la mejo a de oma de decisiones. Es o sig- ni ica que a a ´a de elegi el camino que eduzca el iempo de iaje y, consecuen emen e, mejo e las ecompensas. Debido a es o, al exis i e oalimen aci´on o al, es un algo i mo que no se puede compa a di ec amen e con los o os dos. Ni GPMW, ni cGPMW ienen e oalimen aci´on o al. El algo i mo Hedge conoce oda la in o - maci´on posible. Tene e oalimen aci´on o al no es compa able con conoce el con ex o. Mien as que sabe el con ex o es una in o maci´on que pod ´ıa se conside ada ´u il, la e oalimen aci´on o al es equi alen e a conoce oda la in o maci´on de la ed. A pesa de que el Hedge juega un ´unico b azo en cada onda, es como si juga ´a odos. Po es o, dicho algo i mo se i ´a de in oducci´on y ejemplo pe o a la ho a de compa a algo i mos, el es udio se cen a ´a en los dos siguien es. An es de abo da es e algo i mo en p o undidad, hay que se˜nala una p emisa undamen al de los bandidos con ex uales que s´ı cumple el cGPMW pe o no el algo i mo ac ual. En un bandido con ex ual, el algo i mo obse a el con ex o x de la onda an es de selecciona un b azo. Es a es la cla e que debe se en endida y asimilada. Si el algo i mo iene en cuen a el con ex o obse ado an es de elegi una acci´on se ´a un bandido con ex ual. Debido a es e mo i o, el algo i mo Hedge, no es un bandido con ex ual, ya que no usa el con ex o (capacidades) pa a selecciona un camino. En cambio, el algo i mo Hedge elige en unci´on del iempo, es deci , oma el camino que menos iempo a de po que le epo a ´a mejo es ecompensas. Po o o lado, aunque Hedge no enga en cuen a el con ex o pa a decidi un camino, s´ı lo u iliza (adem´as de las ocupaciones de las ca e e as y el ec o de es a egias) pa a calcula el iempo de iaje pa a cada b azo, y ob ene la e oalimen aci´on o al. Una ez que han sido mencionados los aspec os m´as ele an es, se expone el algo i mo pa a despu´es ahonda en sus ca ac e ´ıs icas exhaus i amen e. Algo i mo 7.12 Algo i mo Hedge en Juego Con ex ual. 1: Al inicializa : Se es ablece una asa de ap endizaje γ, se inicializan los pesos a 1, se calculan la ecompensa m´axima y la ecompensa m´ınima. Se ob ien los Kcaminos que puede oma . 2: o cada onda = 1,2, . . . do 3: Se juega un b azo aelegido alea o iamen e en unci´on del ec o pesos. 4: Se ac ualiza el ec o pesos:∀a∈A:pesosa←pesosa·eγ·(−la). 5: end o Como se puede obse a , an es de la simulaci´on el algo i mo Hedge se enca ga de inicializa los pa ´ame os necesa ios. P ime o se inicializa a uno el alo de los pesos de odos los b azos. La a iable pesos ep esen a la impo ancia de cada b azo. La p obabilidad de dicho b azo se calcula di idiendo su peso en e la suma de odos los pesos. Un peso mayo se aduci ´a en m´as posibilidades de que ese b azo sea seleccionado. Como odos pa en con un peso de 1, odos ienen a p io i las mismas posibilidades de se elegidos. Una p obabilidad al a de un b azo A supone que se elegi ´a segu amen e an es que un b azo B. Es as p obabilidades cambian a lo la go de la simulaci´on po medio de la unci´on ac ualiza . Despu´es, es ablece un alo a γ, que ep esen a la asa de ap endizaje y es a bi a ia. Su o icio es ac ualiza en meno o mayo can idad los pesos as habe ob enido una ecompensa en la ac ualizaci´on. Como se encuen a en una exponencial en nega i o, se puede azona que una γal o in lui ´a menos en el cambio de los pesos mien as que una γde un alo meno in lui ´a m´as en los pesos. Po de ec o, oma el siguien e alo pa a que haya un equilib io en es a a iable en e el n´ume o de b azos y el n´ume o de ondas: γ= 8 log(K) T Po ´ul imo, se ob ienen los alo es de las ecompensas m´aximas y m´ınimas que se calculan an es de la simu- laci´on, es os alo es pe mi i ´an escala las ecompensas en la ac ualizaci´on y ep esen an el alo m´aximo y el m´ınimo que puede consegui un agen e con cualquie con ex o y cualquie b azo. Se calculan haciendo m´ul iples simulaciones de ap oximaci´on con odos los con ex os y b azos pa a ob ene el m´aximo y el m´ınimo. Dichas ap oximaciones se ealizan an es de la simulaci´on eal, y ayudan a consegui es os alo es. Tambi´en se de inen los b azos o caminos que puede oma es e agen e, y en cada onda elegi ´a en e uno de es os b azos. T as desa olla es o, de es e algo i mo, apa e de la inicializaci´on, deben di e encia se dos unciones cla es que ealiza: la elecci´on de un b azo y la ac ualizaci´on. La selecci´on del b azo es un p oceso muy sencillo y l´ogico 47 de acue do a la a iable pesos y su p obabilidad, siendo: p obabilidada=pesoa P∀apesoa Se elige un b azo alea o iamen e en unci´on de los pesos de cada uno de los b azos. Es o se ealiza al p incipio de la onda y, as juga un b azo, se ob iene una ecompensa. A a´ız de es a ecompensa, iene luga el segundo pun o i al que es la ac ualizaci´on. La ac ualizaci´on es el eje de es e algo i mo ya que se enca ga de ac ualiza el ec o pesos y a ec a di ec- amen e en la selecci´on de b azos. B´asicamen e lo que hace la ac ualizaci´on es ob ene una ecompensa pa a cada b azo y ecalcula el ec o pesos. Es o se ha ´a de la siguien e o ma: A a ´es de la unci´on de la ed se calcula el iempo espe ado pa a cada uno de los b azos. Hay que eco da que pa a calcula el iempo espe ado de cada b azo se usan las capacidades, las ocupaciones o ales y el ec o de es a egias. Pos e io men e, se usan las ecompensas m´ınimas y m´aximas pa a que la ecompensa calculada sea meno que la ecompensa m´axima y mayo que la ecompensa m´ınima, luego se no maliza pa a que la ecompensa es e en ´e 0 y 1, y despu´es se calcula las p´e didas, pa a cada b azo la, que son igual a uno menos la ecompensa, es deci , las p´e didas son lo que se deja de gana . Pa a ac ualiza los pesos con las p´e didas de cada b azo se aplica ´a la siguien e ´o mula usando γcomo se ha mencionado, y ambi´en las p´e didas conseguidas, se calculan los pesos pa a cada b azo: ∀a∈A:pesosa←pesosa·eγ·(−la). La a iable la e leja las p´e didas del b azo aen esa onda . Median e es a ´o mula es posible obse a c´omo el peso de los b azos que ob engan peo es ecompensas disminui ´a, mien as que aquellos b azos que ob engan buenas ecompensas man end ´an alo es al os y, po consiguien e, se ´an m´as eces elegidos en ondas u u as. El uncionamien o de los pesos se puede explica con un ejemplo. Hay que imagina que exis en 5 b azos que ep esen an las mejo es u as o caminos pa a un agen e. Pasada una onda , el agen e juga ´a el b azo uno, pe o como hay e oalimen aci´on o al, sab ´a cu´an o ha a dado usando su camino y cu´an o hab ´ıa a dado usando los o os cua o caminos. Si se supone que el camino que ha elegido ha sido el que m´as iempo a da, se ac ualiza ´a el ec o pesos de acue do a es a l´ogica. El b azo uno, que es el elegido, y el que o ece peo ecompensa ya que a da m´as iempo, disminui ´a su peso. Es o p o oca ´a que el b azo uno end ´a un peso meno en la siguien e onda + 1, y hab ´a menos p obabilidades de elegi es e b azo. Po o a pa e, el es o de b azos aumen a ´an su peso espec o al b azo uno. Es a es a egia pe mi e al algo i mo penaliza los caminos que sean len os y engan malas ecompensas y p emia los caminos ´apidos que las engan buenas. De es e modo, a lo la go de las ondas, as epe i es a ac ualizac´on de los pesos se acaba ´an eniendo pesos al os en los caminos que sean m´as ´apidos mien as que los caminos m´as len os end ´an pesos meno es. As´ı, el algo i mo ende ´a a elegi caminos con pesos al os, que le e o na ´an mejo es ecompensas a la la ga. Y usando es a es a egia en el la go plazo el algo i mo mejo a ´a sus ecompensas. No obs an e, es imp escindible conside a que dicho algo i mo Hedge no conside a el con ex o, po que a a de elegi los mejo es caminos pe o no discie ne si en una onda hay mucha o poca conges i´on en un camino. Simplemen e el algo i mo ecibe, con e oalimen aci´on o al, el iempo que a da en usa cada camino y seg´un los iempos de iaje, que a ´ıan cada onda seg´un la ocupaci´on (con ex o), se ac ualiza ´a. Es deci , es e algo i - mo ealiza ´a ac ualizaciones a su ec o pesos en unci´on del iempo de iaje de cada camino, y la ecompensa asociada a es e iempo de iaje, y sin di e encia en e con ex os dis in os cada onda, el algo i mo man end ´a con al os pesos los caminos m´as ´apido a lo la go de las ondas. Es deci , los caminos que mejo es ecompensas medias den se ´an m´as elegidos. A pesa de que es e algo i mo no conside a el con ex o, es el algo i mo que mejo es endimien os o ece ya que iene e oalimen aci´on o al. Al con a io que los o os algo i mos, es e sabe en ealidad cu´ales son las p´e didas y ecompensas pa a odos los b azos como si los hubiese elegido. Es a es una di e enciaci´on muy impo an e ya que aunque no iene en cuen a el con ex o, se pod ´ıa deci que es e algo i mo juega con o as eglas y alcanza meno es emo dimien os que el es o. Debido a es o, el an´alisis se cen a en la compa a i a en e el GPMW y el cGPMW pa a e de qu´e mane a puede in lui la in o maci´on con ex ual. Po o o lado, el algo i mo Hedge es muy impo an e ya que adem´as de en iquece el abajo y se mues a un bandido mul i-b azo con e oalimen aci´on o al en un caso eal, ambi´en 48 se explica como pun o de pa ida pa a amilia iza nos con el uncionamien o de es os algo i mos en la ed. Tambi´en hay que se˜nala que es el algo i mo usado po de ec o po los jugado es que no son con olados po el algo i mo elegido (GPMW o cGPMW) en la simulaci´on, po lo que es imp escindible pa a pode desa olla adecuadamen e es e p og ama. 7.4.2. Algo i mo GPMW La in es igaci´on aho a se cen a en el algo i mo GPMW. A pesa de no se un algo i mo es ic amen e con ex ual, s´ı que conside a las capacidades o ales de las ca e e as. Po es o, se puede a i ma que es udia dicho algo i mo a a apo a mucho alo a es e abajo y a a en iquece los conocimien os ob enidos ace ca del desa ollo de es os bandidos. El algo i mo GPMW a a se compa ado con el cGPMW que s´ı es es ic amen e con ex ual. Una ez que ha sido acla ado es e aspec o, se puede desa olla exhaus i amen e el uncionamien o de es e bandido. A di e encia del algo i mo Hedge, es e algo i mo no iene e oalimen aci´on o al, solo conoce el cos e de su b azo elegido. Sin emba go, el algo i mo GPMW simula e oalimen aci´on o al con cos es alsos. En el p ime algo i mo, Hedge, se calculaba con la ed la ecompensa de cada b azo dado el con ex o de ese momen o. En el algo i mo de es e apa ado la e oalimen aci´on o al es simulada con p edicciones, no con esul ados eales como lo hac´ıa el algo i mo Hedge. El aspec o de las p edicciones es i al pa a en ende es e algo i mo. Es e algo i mo ealiza p edicciones pa a simula las ecompensas que espe a ´ıa ob ene pa a odos los b azos en la onda en la que se encuen e. G acias a es a ´ecnica, el algo i mo ac ualiza ´a los pesos que o o ga a cada b azo seg´un lo buenas que sean sus p edicciones. Hay un peso po cada b azo y los b azos con mejo es endi- mien os, o p edicciones aho a, end ´an pesos mayo es po lo que ende ´an a se elegidos. El uncionamien o de los pesos es simila al apa ado an e io excep o po una cues i´on. Una di e encia a ene en cuen a espec o al algo i mo Hedge es la o ma de calcula los pesos. En cada onda el algo i mo ac ualiza los pesos de acue do a la asa de ap endizaje y lo ha ´a con las p´e didas acumuladas. ∀a∈A:pesosa←pesosa·eγ·(−La). En es e caso, es ´a u ilizando las p´e didas acumuladas en el exponen e que mul iplica los pesos. Dichas p´e didas acumuladas las ep esen a como La. An e io men e, usaba las p´e didas de la onda, pe o es e algo i mo iene en cuen a las p´e didas de odas las ondas an e io es. Es o se debe a que en Hedge los pesos se ac ualizan en unci´on de la p´e dida de la onda ac ual po que se supone que la dis ibuci´on de p obabilidad de las acciones ´op imas es ela i amen e es able de una onda a o a. Po eso, con las p´e didas de la onda ac ual se conside a que es su icien e. Po o a pa e, el algo i mo GPMW conside a la p´e dida acumulada eniendo en cuen a las ondas an e io es po que su es a egia no depende solo de las obse aciones de p´e didas de la onda ac ual, sino ambi´en las obse aciones p e ias, ya que el GPMW pa e de la p emisa de que la dis ibuci´on de p obabilidad de las acciones ´op imas puede cambia a lo la go del iempo. Una ez que se ha mencionado es os aspec os se mos a ´a el esquema que sigue es e algo i mo, y despu´es hay una explicaci´on de allada de cada paso: Algo i mo 7.13 Algo i mo GPMW en Juego Con ex ual. 1: Al inicializa : Se es ablece una asa de ap endizaje γ, se inicializan los pesos a 1, se calculan la ecompensa m´axima y la ecompensa m´ınima. Se ob ienen los Kcaminos que puede oma . Se inicializan el his o ial (ocupaciones o ales y unidades en iadas) y el his o ial de ecompensas. 2: o cada onda = 1,2, . . . do 3: Se juega un b azo aelegido alea o iamen e en unci´on del ec o pesos. 4: Se ac ualizan el his o ial y el his o ial de ecompensas con el b azo ay su ecompensa . 5: Se simula la e oalimen aci´on o al: ∀a∈A: simulada(a) = (his o iales, ocupaciones ) 6: Se ac ualiza el ec o pesos:∀a∈A:pesosa←pesosa·egamma·(−La) 7: end o Lo p ime o que ealiza es e algo i mo es una inicializaci´on muy simila a la del algo i mo an e io pe o a˜nadiendo nue os a ibu os po que la me odolog´ıa u ilizada es m´as compleja. Se ob ienen la asa de ap endiza- 49 je, γ, las ecompensas m´aximas y m´ınimas y los Kcaminos al igual que an es. Tambi´en el algo i mo end ´a dos piezas c uciales: el his o ial y el his o ial de ecompensas de ondas pasadas. Es deci , en una onda , end ´a los his o iales has a esa onda de odas las an e io es. Aho a se e ´a qu´e alo ienen y pa a qu´e si en es os a ibu os. Po un lado, el his o ial de ecompensas e leja la ecompensa ob enida en cada una de las ondas an e io es. Po o o lado, el his o ial almacena dos ec o es en cada onda. P ime o almacena la es a egia jugada po el b azo elegido ay los ca e e as que usa ese b azo. Tambi´en gua da las ocupaciones o ales de las ca e e as que necesi a es e camino, b azo, elegido. En de ini i a, el his o ial con end ´a la in o maci´on de las ca e e as jugadas po el jugado en una onda, an o la ocupaci´on o al de esa ca e e a, como las paque es que el b azo en ´ıa po esas ca e e as, de acue do a su camino escogido. Usando es os his o iales, y las ocupaciones dada la onda en la que se encuen e, pod ´a calcula las ecompensas simuladas de la siguien e mane a, al y como se de alla en [12]: En p ime luga , el algo i mo ac ualiza los his o iales: el his o ial de ecompensas con la nue a ecompensa de la onda y el his o ial que e leja las ocupaciones o ales pa a las ca e e as del camino aelegido y los paque es en iados del camino aelegido. Una ez hecho es o, usa un modelo de eg esi´on gaussiana y lo en ena pa a las ondas an e io es, siendo la a iable Xel his o ial y la a iable independien e el his o ial de ecompensas. Pos e io men e calcula las o as ocupaciones, que son las ocupaciones o ales menos las que equie e el jugado , pa a sabe cu´ales son los paque es en iados po odos los dem´as jugado es, a excepci´on de el p opio agen e. Despu´es, es e algo i mo ob iene pa a cada b azo los paque es que iene que en ia pa a cada ca e e a, y jun o con o as ocupaciones, lo u iliza como Xpa a p edeci con la eg esi´on gaussiana, que ya ja sido en enada, y ob iene una p edicci´on de la ecompensa pa a cada b azo y la a ianza de es a p edicci´on. Con un alo de be a, β, de 0.5, calcula el l´ımi e supe io de con ianza con la p edicci´on ob enida pa a cada b azo: UCBa= ˆµa+β ˆσa. La a ianza la p opo ciona el modelo de eg esi´on gaussiana. El algo i mo GPMW ac ualiza el ec o pesos usando el ec o UCB al igual que pa a el algo i mo Hedge. Las ecompensas se ´an el ec o UCB pa a odos los b azos, comp ueba que es ´an den o de la ecompensa m´axima y ecompensa m´ınima pa a despu´es escala las. Calcula las p´e didas pa a cada b azo la, haciendo la di e encia en e uno y las ecompensas escaladas. Ac ualiza con las p´e didas acumuladas que en´ıa ya de o as ondas: La=La+lapa a cada b azo a. Usa Lay modi ica el ec o pesos: ∀a∈A:pesosa←pesosa·eγ·(−La). A con inuaci´on, se de alla ´a qu´e es la eg esi´on gaussiana y qu´e u ilidad iene en es a implemen aci´on. La eg esi´on gaussiana es un m´e odo de ap endizaje au om´a ico que p opo ciona una o ma de in e i una unci´on desconocida a pa i de da os de en enamien o uidosos. Es un modelo de eg esi´on no pa am´e ico, lo que signi ica que puede adap a se a da os de cualquie o ma sin ene una o ma p ede inida. Po o o lado, en el con ex o de la eg esi´on gaussiana, un ke nel (o unci´on de co a ianza) es una unci´on que mide cu´an o se pa ecen dos pun os. En o as palab as, de ine el g ado de co elaci´on o simili ud en e dos pun os en el espacio de en ada. En la implemen aci´on o iginal, usa el modelo de eg esi´on gaussiana (con el ke nel) pe mi e ex- plo a la simili ud en e dos con ex os ya que se mide la simili ud en e los pun os. De es e modo, un bandido que conside e el con ex o como el siguien e algo i mo, cGPMW, consigue alcanza muy buenas ecompensas al saca pa ido de la eg esi´on gaussiana pa a mismos con ex os y cap u a muchas o mas di e en es de elaciones en e da os de en ada y salida. Respec o a dicho modelo de eg esi´on gaussiana, cabe se˜nala que en Py hon se usa la lib e ´ıa GPy mien as que en la adap aci´on que ha sido implemen ada en C++, se usa “ m eg ession aine ” de la biblio eca dlib. Es o es un modelo de eg esi´on de ec o es de sopo e (RVM) que pe mi e en ena dicho modelo pa a que pueda ealiza p edicciones pa a ob ene las ecompensas simuladas. Pa a el modelo RVM no ha sido necesa io u iliza el ke nel, la unci´on de co a ianza po que el modelo de eg esi´on de ec o es u ilizado no pe mi e pasa le po pa ´ame o un ke nel. En cualquie caso, es e algo i mo GPMW, usa un modelo de ap endizaje au om´a ico, un modelo de eg esi´on, pa a p edeci las ecompensas de odos los b azos y simula e oalimen aci´on o al. Po ello, la eg esi´on juega un ol cla e pa a simula las p edicciones de cada b azo, ya que en unci´on de es as p edicciones se ac ualizan los pesos de cada b azo y, en consecuencia, se juegan m´as aquellos b azos que engan mejo es p edicciones. 50 Es o se puede en ende con un ejemplo. Si hay una si uaci´on en la que dada una onda se elige un b azo a, el algo i mo ac ualiza ´ıa los his o iales pa a en ena el modelo con oda la in o maci´on has a , que se incluye ambi´en. El algo i mo ha ´ıa p edicciones pa a los 5 b azos que iene, y si el modelo de eg esi´on p edice una muy buena ecompensa pa a el b azo 2 en e al es o de b azos, el peso del b azo 2 aumen a ´a en e a los dem´as b azos, y se ´a m´as p obable elegi el b azo 2 a pa i de la siguien e onda. Las p edicciones de inen cu´ales se ´an los b azos m´as u ilizados ya que modi ica ´an los pesos de los b azos en cada onda. Si las p edicciones a ec an mucho o poco pa a cambia el peso de un b azo depende ´a del γ, o asa de ap endizaje, (al igual que el Hedge). 7.4.3. Algo i mo cGPMW Po ´ul imo, se explica el algo i mo m´as complicado pe o ambi´en m´as e icaz. Es e es el ´unico algo i mo con ex ual de los es. Dicho algo i mo es una ex ensi´on o mejo a del algo i mo GPMW, y hay que ene en cuen a que se encuen an muchas simili udes en e es os dos algo i mos. Adem´as, el peso de los b azos se ac ua- liza ´a usando el ec o pesos al igual que lo hacen los o os dos algo i mos. Po ello, es e algo i mo abaja a con nomencla u a simila as´ı como con concep os desa ollados en las subsecciones an e io es del algo i mo Hedge y el algo i mo GPMW. Pa a empeza con el algo i mo cGPMW, se comienza explicando po qu´e es el ´unico bandido con ex ual. A di e encia de los o os dos, es e algo i mo obse a el con ex o an es de oma una decisi´on espec o a qu´e acci´on quie e juga . Po ello, iene una nue a es uc u a, obse a el con ex o y calcula una es a egia an es de selecciona la acci´on. Es a unci´on de calculo de es a egia le pe mi e conside a el con ex o pa a elegi el mejo b azo de acue do al con ex o igen e. El c´alculo de es a egia es algo simila a lo que hace el algo i mo GPMW cuando simula la e oalimen aci´on o al. No obs an e, el algo i mo cGPMW compu a su es a egia eniendo en cuen a el con ex o y ealizando las ope aciones de mane a di e en e. La p incipal idea de es e algo i mo con ex ual es u iliza el con ex o pa a op imiza las ecompensas. Su undamen o se basa en que un agen e pod ´a mejo a las acciones jugadas pa a un mismo con ex o si se epi e du an e el iempo de mane a que ap ende ´a c´omo elegi adecuadamen e cada con ex o. Es o es lo que se co- noce en la eo ´ıa de juegos con ex uales como que en un juego con ex ual d´onde con ex os y acciones simila es p obablemen e p oduzcan ecompensas pa ecidas. El agen e a a ´a de explo a es as si uaciones simila es con el obje i o de maximiza sus ecompensas median e el ap endizaje de que b azo es adecuado en cada si uaci´on o con ex o. Es o se en iende mejo con un ejemplo. Hay que eco da que los con ex os ep esen an las capacidades de las ca e e as. Se supone un caso muy sencillo, donde hay dos con ex os: un con ex o si hace un d´ıa con un iempo soleado y o o si nie a. Si nie a las ca e e as educen su capacidad. La p ime a ez que nie a el agen e sab ´a que las capacidades de la ca e e a son m´as peque˜nas y puede manda menos paque es, sin emba go, como no ha expe imen ado es e con ex o no sab ´a qu´e acci´on es mejo . Si se suceden las ondas y el agen e pasa po a ios d´ıas con nie e, comenza ´a a ap ende que acciones son las mejo es pa a los d´ıas con nie e. Po es o, puede que aunque pa a los d´ıas soleados (sin nie e) el mejo camino es el uno, mien as pa a los d´ıas con nie e el mejo camino sea el cua o. El agen e pod ´ıa acaba d´andose cuen a de es o as a ios d´ıas con nie e donde ha p obado odos los caminos. Es a es la base de la explo aci´on de los bandidos con ex uales en los juegos, el agen e se ap o echa de epe idas si uaciones de un con ex o pa a ap ende cu´al es la mejo es a egia, o b azo, que puede segui . Respec o al uncionamien o del algo i mo, la mejo o ma de e lo es mos a el esquema y luego explica lo, el cGPMW ope a de la siguien e mane a que se p esen a en el algo i mo 14. Cabe se˜nala que sigue un esquema simila al del algo i mo GPMW pe o iene sus p opias di e enciaciones. P ime o se inicializa, despu´es obse a el con ex o y pos e io men e ealiza las ope aciones necesa ias pa a mejo a su oma de decisiones. 51 Algo i mo 7.14 Algo i mo cGPMW en Juego Con ex ual. 1: Al inicializa : Se es ablece una asa de ap endizaje γ, se inicializan los pesos a 1, se calculan la ecompensa m´axima y la ecompensa m´ınima. Se ob ienen los Kcaminos que puede oma . Se inicializan el his o ial y el his o ial de ecompensas. 2: o cada onda = 1,2, . . . do 3: Se obse a el con ex o x ∈X. 4: Se calcula la es a egia y se simula la e oalimen aci´on o al pa a dicho con ex o x :∀a∈A: acumulada(a|x ) = (his o iales, ocupaciones, capacidades ) 5: Se ac ualiza el ec o pesos:∀a∈A:pesosa←pesosa·eγ·(−La) 6: Se juega un b azo aelegido alea o iamen e en unci´on del ec o pesos. 7: Se ac ualizan el his o ial y el his o ial de ecompensas con el b azo ay su ecompensa . 8: end o T as habe mos ado el esquema, es ap eciable el p incipal asgo de es e algo i mo. P ime o obse a el con- ex o, x , y despu´es calcula la es a egia a segui an es de elegi un b azo. Po lo an o, ya ha desa ollado una es a egia al habe obse ado un con ex o espec´ı ico an es de elegi un b azo. A p io i, pod ´ıa pensa se que es una en aja po que ap o echa ´a ese con ex o en espec´ı ico al c ea una pol´ı ica aco de a las capacidades de la ed an es de oma una decisi´on, an es de elegi un b azo. Es e es un ac o di e encial en con as e con el es o de algo i mos como el algo i mo GPMW que, p ime o, no obse a el con ex o, y segundom ac ualiza sus pesos y ealizan p edicciones al inal de la onda, no an es de elegi la acci´on. Aho a se p o undiza en los pasos cla e de es a unci´on y se de end ´a en desa olla es as ases pa a acili a la comp ensi´on y pode abo da el algo i mo con odo de alle: En p ime luga , cGPMW Obse a el con ex o, x , al comienzo de la onda. Es e con ex o e leja las capacidades de las ca e e as. El con ex o de cada onda se ob iene alea o iamen e en e los x∈X con ex os posibles. Despu´es el algo i mo la es a egia dado el con ex o. Pa a calcula la es a egia, al igual que con el algo i mo an e io ap o echa la simulaci´on de e oalimen aci´on o al. Sin emba go, el algo i mo cGPMW iene a ias di e encias ap eciables espec o a su an eceso . •El modelo es en enado con eg esi´on gausiana con los siguien es da os his ´o icos: el his o ial de ecompensas y el his o ial que se compone po es ac o es: las ocupaciones o ales, los paque es en iados po el agen e seg´un el camino elegido y las capacidades. Al con a io que los algo i mos GPMW, se almacenan las capacidades de cada onda, es deci , los con ex os. •El algo i mo cGPMW i e a desde las ondas an e io es has a la onda −1. •En cada onda, ealiza una p edicci´on pa a cada b azo con el modelo de eg esi´on gaussiana, dadas las capacidades ac uales, y calcula la ecompensa pa a cada b azo con la siguien e ´o mula: UCBa= ˆµa+β ˆσa.Be a es una a iable que se sigue usando pa a educi a la mi ad la a ianza. La a ianza es ob enida po el modelo de eg esi´on gaussiana. •Una ez ha calculado la ecompensa pa a esa onda, escala ´a dicha ecompensa (pa a cada b azo), de acue do a las mismas eglas que necesi aba el algo i mo GPMW. •Escala las ecompensas sob e 0 y 1 usando la ecompensa m´axima y la ecompensa m´ınima que ob enida en la incializaci´on. •Cuando se ob ienen las ecompensas escaladas, el algo i mo calcula la ecompensa acumulada escalada has a la onda −1. De es e modo, se ienen en cuen a la p edicci´on de las ecompensas de odas las ondas an e io es dado un con ex o conc e o pa a cada uno de los b azos. •T as habe calculado odas las ecompensas acumuladas pa a cada b azo haciendo p edicciones en las ondas an e io es con las capacidades ac uales, u iliza ´a las p´e didas acumuladas, y simplemen e es a ´a a ondas an e io es las ecompensas acumuladas: L=T− ecompensasacumuladasapa a cada b azo a.La ep esen a ´ıa las p´e didas acumuladas pa a las ondas an e io es con un con ex o pa icula pa a un b azo. Se hace de es a o ma ya que las ecompensas acumuladas se han ido sumando du an e T ondas y es a ´an en e un alo de 0 y Tpa a cada b azo. •Ac ualiza los pesos el ec o pesos:∀a∈A:pesosa←pesosa·eγ·(−La). 52 El siguien e paso a segui po es e algo i mo es elegi un b azo aalea o iamen e dado el ec o pesos que ha sido modi icado an e io men e con el calculo de la es a egia. Ac ualiza ´a los his o iales pa a el b azo ay la ecompensa ob enida du an e esa onda, . Cabe se˜nala , que el algo i mo cGPMW ealiza p edicciones en odas las ondas an e io es a la onda en la que se encuen e y, como esul ado, necesi a mucho iempo pa a ejecu a se. En compa aci´on con el algo i mo GPMW a da bas an e m´as po que aunque en las p ime as ondas el algo i mo cGPMW no equie e mucho iempo, cuando ya hay un n´ume o conside able de ondas, como 40, end ´a que hace p edicciones con la e- g esi´on pa a las 39 ondas an e io es po lo que el iempo de ejecuci´on aumen a exage adamen e a pa i de un n´ume o al o de ondas. Como se puede obse a , al igual que el algo i mo GPMW los pesos se ac ualizan en unci´on de las p´e didas acumuladas y no las p´e didas de la onda. Es o se hace po que se conside a que la dis ibuci´on de las acciones ´op imas cambia du an e la pa ida. Se usa es e plan eamien o ya que se puede pensa que las capacidades del oponen e pueden a ia a lo la go del iempo y, po lo an o, ambi´en lo ha ´ıan las ecompensas espe adas. En ende el uncionamien o de es e algo i mo hace comp ensible que ene en cuen a el con ex o puede se muy bene icioso. En es e caso, se p edicen como ac ua ´an odos los b azos dadas dis in as ocupaciones pa a es e con ex o. Es a in o maci´on es de g an u ilidad ya que el algo i mo conoce ´a c´omo de bueno se ´ıa cada camino con las capacidades que se dan en la onda. Po es e mo i o, se puede a i ma que en e al algo i mo GPMW, el algo i mo cGPMW ap o echa el con- ex o pa a ealiza p edicciones m´as p ecisas y, en consecuencia, oma mejo es decisiones. Po ejemplo, si se p edice cu´al a a se el endimien o de en ia paque es a a ´es de un camino y no es conocida su capacidad, no se sab ´a si puede habe conges i´on que e ase el iempo de en ´ıo y haga que el camino sea una mala opci´on. Po el con a io, si an es de manda los paque es es sabido si el camino iene mucha capacidad, se pod ´a in ui si es una buena al e na i a pa a a da poco en en ia los paque es. Tambi´en se ´ıa lo mismo si se obse a que el camino iene poca capacidad ya que hab ´a mucha conges i´on debido a la limi ada capacidad del mismo, y si es a in o maci´on del camino es conocida, es ´e no se ´a conside ado como un buen b azo. Cuando se hace e e encia a la capacidad de un camino, se es ´a hablando de las capacidades de las ca e e as que componen dicho camino. En segundo luga , el algo i mo cGPMW ambi´en pod ´a ap ende m´as ´apido ya que iden i ica ´a mejo los pa ones en e b azos y ecompensas al conoce la in o maci´on con ex ual. Es o sucede po que el algo i mo puede ajus a su pol´ı ica de selecci´on de b azos pa a oma decisiones m´as in o madas en unci´on del con ex o ac ual. Se pa e de la base de que las ecompensas es ´an elacionadas con los con ex os y los b azos. Al con- side a odas las a iables in oluc adas, endi ´a mejo . Se pod ´ıa deci que el algo i mo comp ende ´a pa ones mejo ya que es el ´unico algo i mo que ap ecia ´a la oma de decisiones de mane a global, conside ando la ed en su o alidad y aba cando m´as in o maci´on que la que conocen o os algo i mos. Es o mejo a ´a sus decisiones y al ene m´as in o maci´on pa a decidi ap ende ´a m´as ´apido que o os algo i mos. O o ac o impo an e es que se pod ´a adap a mejo a cada si uaci´on. Como ya se ha comen ado, hay cie as limi aciones pa a algo i mos que no ienen en cuen a el con ex o po que oman la decisi´on en base al mejo b azo en gene al sin conside a si uaciones espec´ı icas. Pasa lo con a io con es e algo i mo, que sab ´a pe ec amen e que aunque un b azo pueda se una al e na i a medioc e, pa a un con ex o de e minado puede se la mejo ´ıa. Pa a ilus a es o, en una ed donde un agen e iene cinco dis in os caminos y se supone que el camino es es una opci´on que o ece endimien os egula es, que no es muy ´apido ni muy len o, es e b azo es pod ´ıa conside a se como un b azo medioc e. Sin emba go, pod ´ıa da se una si uaci´on que es muy pun ual y ocu e espo ´adicamen e pe o p o oca que el es o de caminos engan poca capacidad, como que se aumen en las es icciones en las ca e e as po la con aminaci´on excep o en las ca e e as del camino es. Dicho camino a pesa de no se especialmen e bueno, se ´ıa emendamen e ´u il an e es a coyun u a ya que el es o de caminos se e ´ıan g a emen e pe judicados. Mien as que el algo i mo GPMW no ap ecia ´ıa es o, el algo i mo cGPMW saca ´ıa pa ido de es a si uaci´on y po eso es des acable su habilidad pa a adap a se a di e sas si uaciones. Po ´ul imo, el algo i mo cGPMW puede desa olla una buena es a egia de ca a a la explo aci´on-explo aci´on. Al se conocedo del con ex o puede cen a m´as su explo aci´on en cie os con ex os donde hay mucha ince i- dumb e mien as que puede man ene una cons an e explo aci´on en con ex os segu os. Es o puede comp ende se cla amen e con el mapa de ca e e as. Si se supone que una de las a iables del con ex o es el calenda io, dada una ´epoca del a˜no es i a, se puede pensa que en es os d´ıas las ca e e as end ´an mucha ocupaci´on y an e dicha si uaci´on hab ´a mucha ince idumb e po sabe qu´e ca e e as se ´an m´as concu idas que o as. El algo i mo puede pensa que al aumen a el iesgo le con iene explo a m´as en un s´abado de una semana es i a como 53 Semana San a que an e un s´abado no mal donde las ca e e as end ´an ocupaciones simila es. De es a mane a pod ´ıa cen a se en desa olla una es a egia adecuada en es os con ex os espec´ı icos donde la ince idumb e aumen a conside ablemen e. 7.5. Conclusiones Es a aplicaci´on p ´ac ica se inici´o con dos obje i os. El p ime o e a ealiza una aducci´on de la imple- men aci´on o iginal del juego en Py hon [18] a C++, un lenguaje de m´as bajo ni el que pe mi i ´ıa escud i˜na los de alles pa a en ende el uncionamien o del juego. El segundo obje i o e a obse a las di e encias en e los algo i mos que no en´ıan en cuen a el con ex o: Hedge y GPMW, y los que s´ı: cGPMW. En cuan o al p ime obje i o, se ha conseguido implemen a co ec amen e en C++ los algo i mos es udia- dos, al y como queda e lejado en los eposi o ios [26] y [27]. G acias a es o, se ha ob enido un conocimien o muy a anzado ace ca de las pa es o p ocesos que con o man los algo i mos usados en los p oblemas de bandidos mul i-b azo. Po ejemplo, se ha ap endido que la o ma de implemen a un algo i mo es median e una clase que enga como a ibu os imp escindibles el n´ume o de b azos, la dis ibuci´on ac ualizada de las p obabilidades de elecci´on de cada b azo y dem´as pa ´ame os necesa ios, como la asa de explo aci´on, que ajus an el unciona- mien o del algo i mo. Adem´as, la clase del algo i mo debe implemen a dos m´e odos que son ejecu ados en cada onda: el p ime o ejecu a la ase de elecci´on de b azo y, as ecibi la ecompensa co espondien e, el segundo ac ualiza la dis ibuci´on de p obabilidades de los b azos en base a dicha ecompensa. Po o a pa e, no solo se han desa ollado co ec amen e odos los algo i mos, sino que ambi´en se ha c eado una ed y una simulaci´on en C++ que imi a la o iginal en Py hon. Respec o al segundo obje i o, es e cap´ı ulo se ha aden ado en las ca ac e ´ıs icas de los algo i mos con- ex uales y los no con ex uales pa a pode explica los de mane a cla a y p ecisa. Asimismo, se ha conseguido en ende y explica las di e encias en e es os algo i mos. Po ano , se puede conside a que es e obje i o ha sido cumplido con c eces. Pe o no odo ue sencillo, du an e el p oceso de adap aci´on se encon a on cie as limi aciones de C++ con espec o a Py hon que imped´ıan ob ene los mismos esul ados que en los an´alisis ealizados po Guissepe Sessa y sus colabo ado es e lejados en la igu a 12, ex a´ıda de [12], y en la igu a 13, ex a´ıda de [14]. Figu a 12: Cos e medio y conges i´on media. Pa a sabe los b azos o caminos que pueden se escogidos po los agen es e a necesa io conoce p e iamen e los kcaminos m´as co os (5 en es e caso). Con es e p op´osi o, en el c´odigo de Py hon se emplea una lib e ´ıa conocida como Ne wo kx que simpli ica el p oceso. Sin emba go, en C++ no exis e dicha biblio eca, lo que supuso la p ime a di icul ad pa a la aducci´on a dicho lenguaje. Finalmen e, as la ealizaci´on de muchas p uebas allidas, se alcanzo el ´exi o al adecua el c´odigo publicado en [19] al desa ollo p e io, consiguiendo desa olla la misma unci´on que la lib e ´ıa Ne wo kx en Py hon. El ap o echamien o de es e c´odigo pe mi i´o implemen a el algo i mo Yen K Caminos M´as Co os, que a su ez hace uso del algo i mo Dijks a Camino M´as Co o. P e iamen e, ue necesa ia la amilia izaci´on con el ipo de g a os con los que abajan es os algo i mos. Adem´as, hubo que conec a el algo i mo Yen con la ed de nodos y ca e e as, almacenada en la es uc u a de da os “SiouxNe wo k”, y con el ec o de es a egias que se explica a con inuaci´on. Po ello, pa a adap a adecuadamen e es e algo i mo hubo que modi ica g an pa e del c´odigo ya desa ollado y del p opio Yen K Caminos M´as Co os. En conclusi´on, es a a ea se lle ´o a cabo 54 Figu a 13: Remo dimien o medio y conges i´on media. co ec amen e y se pudo sol en a la di icul ad. En el c´odigo desa ollado es os caminos se gua dan en un ec o de es a egias de es dimensiones, con- c e amen e [528][5][76], compues o po un p ime ec o de 528 jugado es o posiciones, un segundo ec o pa a cada jugado de 5 caminos o posiciones y un e ce ec o pa a cada camino. Cada uno de los caminos iene un ama˜no de 76 ca e e as de la ed, y en cada ca e e a o posici´on del ec o del camino apa ecen las demandas de ese jugado en dicho camino. Se ecue da que cada uno de los 5 caminos e leja uno de los 5 b azos del agen e. Po ejemplo, en la posici´on 20 del ec o de es a egias hay cinco b azos asociados a ese jugado (el de la posici´on 20). El b azo 1 se de ine po un ec o de 76 posiciones y cada una de es as 76 posiciones ep esen a una ca e e a. Po lo an o, si la posici´on 2 iene un alo de 10 ([20][1][2] = 10) y la posici´on 14 iene un alo de 5 ([20][1][14] = 5), signi ica ´a que el b azo o camino 1 del jugado 20 u iliza ´a las ca e e as 2 y 14, con una demanda o al de 15. Po o o pa e, el p oblema m´as impo an e que su gi´o se debe, de nue o, a ac o es ´ecnicos p opios de C++, que ca ece de de e minadas lib e ´ıas que s´ı es ´an disponibles en Py hon. Conc e amen e, hubo p oblemas al in en a adap a una lib e ´ıa llamada GPy de Py hon a C++. Es a lib e ´ıa se enca ga de ealiza la eg esi´on gaussiana usada po los algo i mos GPMW y cGPMW. En su de ec o, en C++, se ha abajado con la unci´on de eg esi´on “ m eg ession aine ” de la biblio eca dlib, ambi´en conocida como RVM (Rele ance Vec o Machine), que consis e en un algo i mo de ap endizaje au om´a ico. El ´unico hipe pa ´ame o que equie e RVM es la asa de ap endizaje, cuyo alo se modi ic´o con el obje i o de no ob ene sob eajus e en las p edicciones ealizadas du an e las p uebas. En de ini i a, a pesa de que con es a al e na i a s´ı ue posible ealiza la eg e- si´on co ec amen e, los esul ados conseguidos no ue on iguales a los de Py hon. Cabe se˜nala que inicialmen e se p ob´o con el eg eso “k aine ”, ambi´en implemen ado en la biblio eca dlib, pe o los esul ados ue on sus ancialmen e peo es que los ob enidos con el eg eso RVM. Adem´as, aunque se consigui´o elabo a en una unci´on que calcula y op imiza los Ke nels en C++ u ilizando la biblio eca Eigen, es o no ue de u ilidad ya que no e a compa ible con la unci´on de eg esi´on RVM de la biblio eca dlib. Po o a pa e, como la biblio eca dlib, a di e encia de GPy, no p opo ciona la a ianza de las p edicciones, se decidi´o op a po calcula la a ianza de los da os de en enamien o y usa la como a ianza pa a las p edicciones de la adap aci´on. Realmen e, odas las decisiones han sido omadas con el in de mejo a las p edicciones ealizadas po la adap aci´on en C++ y desa olla buenos algo i mos. De odas o mas, se ha llegado a la conclusi´on de que la aducci´on de es e juego con ex ual y sus algo i mos en Py hon a C++ ha eque ido de excesi o iempo y es ue - zo debido a las limi aciones ´ecnicas de C++ en compa aci´on con las en ajas y capacidades del lenguaje Py hon. Con odo lo an e io , se conside a que la implemen aci´on desa ollada si e como base s´olida pa a en ende los bandidos con ex uales y sus algo i mos, y en iquece las apo aciones de es e apa ado con ibuyendo al a ance del conocimien o en es e campo. Una ez expues as las ca ac e ´ıs icas del juego en C++, se p ocede al an´alisis del mismo. Pa a ello, se com- pa an los esul ados del algo i mo GPMW y el algo i mo cGPMW pa a un agen e alea o io en una simulaci´on conc e a. Es deci , en es a simulaci´on, se obse a el compo amien o de un ´unico agen e pa a los dos algo i mos. De es a mane a, ambos algo i mos disponen de los mismos b azos o caminos pa a elegi y sus endimien os pueden se con as ados bajo el mismo escena io. No se conside a el algo i mo Hedge po que iene e oalimen- aci´on o al. El in e ´es de es e an´alisis adica en obse a las di e encias en e un algo i mo que iene en cuen a 55 el con ex o, cGPMW, y o o que no obse a dicho con ex o, GPMW. Figu a 14: B azos elegidos. Figu a 15: P´e didas po onda. Pa a ob ene las igu as 14 y 15, p ime o se han gua dado los esul ados de la simulaci´on de C++ en un iche o. Despu´es, con Py hon se ha analizado dicho iche o y se han c eado es as g ´a icas que es udian el compo - amien o y endimien o de los algo i mos. Jun o a la igu a 16, es as e lejan, en cada onda, los b azos elegidos po cada algo i mo y su e ec o inmedia o en las p´e didas. Cabe menciona que en la p ime a igu a los 5 b azos se ep esen an con los alo es en e os del in e alo [0, 4]. Al analiza es as g ´a icas, se obse a que el algo i mo cGPMW no siemp e elige mejo que GPMW, hay oca- siones en las que es e segundo elige un camino que implica menos p´e didas. De odas o mas, po egla gene al el algo i mo GPMW es el que ob iene mayo es p´e didas, o peo es ecompensas, a lo la go del ho izon e empo al. Po ´ul imo, la igu a 17 mues a e dade amen e qu´e algo i mo consigue minimiza las p´e didas medias a lo la go de la simulaci´on. En es e caso, se puede ap ecia que el algo i mo cGPMW es el que consigue meno es p´e didas medias al inal de la simulaci´on. En de ini i a, se puede conclui que el algo i mo cGPMW, que consi- de a el con ex o, alcanza un mayo endimien o que el algo i mo GPMW en escena ios con ex uales Debido a la p´e dida de e icacia po el p oceso de aducci´on del lenguaje que ha sido e lejada en es a sec- ci´on y a que solo se ha podido compa a el endimien o de dos algo i mos en e s´ı, no ha sido posible ob ene 56 Figu a 18: C uce de SMA de pe iodo la go, medio y co o [24]. Las g ´a icas de colo ojo, e de y na anja de la igu a ep esen an las SMA de la go, medio y co o plazo, espec i amen e. Se puede comp oba que cuando las medias m´o iles de medio y co o plazo co an con la de la go plazo se p oduce un cambio en la endencia del p ecio del ´ı ulo. La es a egia de c uce de medias m´o iles es una ´ecnica de an´alisis ´ecnico popula que se basa en la idea de que las endencias a co o plazo pueden p edeci las endencias a la go plazo. Conc e amen e, es e bo esuel e los posibles con ex os como sigue: Si es ´a en posesi´on del ´ı ulo: Man iene su posici´on la ga a menos que la media m´o il a co o plazo (SMA co a) sea meno que la media m´o il a la go plazo (SMA la ga). En ese caso ende ´ıa el ´ı ulo po que ep esen a ´ıa una se˜nal de que el p ecio a a descende p ´oximamen e. Si no es ´a en posesi´on del ´ı ulo: Man iene su posici´on co a a menos que sal e la se˜nal de comp a cuando la media m´o il a co o plazo sea mayo que la media m´o il a la go plazo. Sin emba go, es a es a egia puede no unciona bien en me cados la e ales o con baja ola ilidad, ya que las se˜nales de comp a y en a pueden se menos p ecisas en esas condiciones. 8.2.5. Expe o en RSI El bo expe o en el oscilado RSI, al igual que el bo an e io , solo abaja moni o izando una uen e de da os. El ´ındice de ue za ela i a o RSI (Rela i e S eng h Index) es un oscilado de impulso u ilizado en el an´alisis ´ecnico. El RSI mide la elocidad y la magni ud de las a iaciones ecien es del p ecio de un alo pa a e alua las condiciones de sob e alo aci´on o in a alo aci´on del p ecio de ese alo . Fue desa ollado po J. Welles Wilde J . e in oducido en su lib o [15]. Cabe des aca que el RSI puede hace algo m´as que se˜nala alo es sob ecomp ados y sob e endidos. Tam- bi´en puede indica alo es que pueden es a p epa ados pa a un cambio de endencia o un e oceso co ec i o en el p ecio. Po ejemplo, si el p ecio de un ac i o es ´a alcanzando nue os m´aximos o m´ınimos, pe o el RSI no es ´a egis ando nue os m´aximos o m´ınimos espec i amen e, pod ´ıa es a indicando una desacele aci´on en el impulso y una posible in e si´on de la endencia. [25] Pa a calcula el alo del RSI, p ime o se calculan las ganancias medias y las p´e didas medias pa a un pe iodo an e io de n= 14 d´ıas, po egla gene al. Una ez ob enido el alo de dichas a iables, se calcula el alo del indicado como RSI = 100 −(100/(1 + (Ganancias Medias/P´e didas Medias))). La es a egia de es e bo sigue las se˜nales adicionalmen e usadas pa a comp a y ende del RSI. Es deci , una lec u a del RSI igual o supe io a 70 indicia que el p ecio es ´a supe ando el umb al de sob ecomp a y, po an o, el bo ecomienda ende , o man ene se en caso de que la posici´on del algo i mo ya uese co a. Po el o o lado, una lec u a de 30 o in e io indica una si uaci´on de sob e en a y el bo sugie e comp a , o man ene se en caso de que el algo i mo ya p esen e una posici´on la ga. No malmen e, es e oscilado se suele moni o iza conjun amen e con o os indicado es pa a mejo a la ca- lidad del an´alisis. Es o se debe en pa e a que, como odos los ´ındices, puede p oduci se˜nales alsas. Po es e mo i o, si el bo de come cio o cualquie agen e no iene o as e e encias segui ´a las se˜nales alsas sin de ec- a las, incu iendo en p´e didas. Po o o lado, como es e oscilado no p esen a in o maci´on de la di ecci´on de la 63 endencia, el bo pod ´ıa no ecibi se˜nales de sob ecomp a o sob e en a po pa e del RSI mien as que el ac i o puede es a en una endencia alcis a o bajis a ue e. Adem´as, el RSI ampoco p opo ciona ni eles de sopo e y de esis encia que pod ´ıan se ´u iles pa a es ablece obje i os de p ecio pa a ende cuando es ´e al o o pa adas de las p´e didas pa a ende cuando el p ecio disminuya has a un de e minado ni el. Po es os mo i os, se suele ecomenda el an´alisis ´ecnico combinando los da os de a ios ´ındices al mismo iempo. 8.2.6. Expe o en MACD y Bandas de Bollinge Se in oduce, po p ime a ez, un bo que hace uso de m´as de un indicado al mismo iempo. Es e bo se ige a pa i de dos indicado es, el MACD y las bandas de Bollinge . El indicado MACD (Mo ing A e age Con e gence Di e gence) es una he amien a muy com´un di igida al an´alisis de me cado. Es e indicado de ine la di e encia en e una media m´o il exponencial (EMA) del co o plazo y o a del la go plazo. Lo no mal es que se conside en los 12 y 26 d´ıas an e io es como el co o y la go plazo, espec i amen e. Ma em´a icamen e, la l´ınea MACD se calcula al que MACD = ema(12,P ecio) −ema(26,P ecio). Adem´as, a pa i de la l´ınea MACD calculada an e io men e, se gene a una l´ınea de se˜nal conocida como EMA en base a, no malmen e, los 9 d´ıas an e io es de al o ma que Se˜nal = ema(9,MACD). La di e encia en e la l´ınea MACD y la l´ınea de se˜nal se denomina His og ama MACD, po an o, His og ma = MACD −Se˜nal. En [16] se puede encon a la in e p e aci´on de es e indicado . Po o a pa e, las bandas de Bollinge son o o ins umen o de an´alisis ´ecnico que se u iliza pa a medi la ola ilidad del p ecio. La ola ilidad de un ´ı ulo en un de e minado in e alo de iempo es la a iabi- lidad de su en abilidad en elaci´on a su en abilidad media en dicho pe iodo. A pa i de la media m´o il simple (SMA) del p ecio de los 20 d´ıas an e io es y su des iaci´on ´ıpica, se puede es ablece una banda supe io e in e io al que Banda Supe io = sma(20,P ecio) + 2 ∗s d de (20,P ecio) y Banda In e io = sma(20,P ecio) −2∗s d de (20,P ecio). Seg´un el ama˜no del ancho de banda, que como se˜nala John Bo- llinge en [21] ep esen a c´omo de sepa adas es ´an las bandas ex e nas con espec o a la l´ınea cen al, se puede cuan i ica la ola ilidad del ´ı ulo. El bo expe o en MACD y las bandas de Bollinge que se plan ea abaja de la siguien e mane a: Si es ´a en posesi´on del ´ı ulo: Man iene su posici´on la ga a menos que se de alguna de las siguien es 2 condiciones pa a ende : •La se˜nal del MACD es mayo que el alo del MACD. Es a condici´on indicia una posible endencia bajis a. •El p ecio de cie e es mayo que la banda supe io de Bollinge . Pod ´ıa indica que el p ecio es ´a sob e alo ado y pod ´ıa co egi se a la baja. Si no es ´a en posesi´on del ´ı ulo: Man iene su posici´on co a a menos que se de alguna de las siguien es 2 condiciones pa a comp a : •La se˜nal del MACD es meno que el alo del MACD. Es a condici´on indicia una posible endencia alcis a. •El p ecio de cie e es meno que la banda in e io de Bollinge . Pod ´ıa indica que el p ecio es ´a in a alo ado y pod ´ıa co egi se a la alza. 8.2.7. Expe o en Todo Po ´ul imo, se ha que ido inclui en el conjun o de bo s de come cio p opo cionado al algo i mo un bo que se compo e de acue do al mo imien o de muchos de los indicado es habi uales en el me cado ac ual. En cada onda, es e bo obse a un conjun o de indicado es inancie os y la posici´on ac ual del algo i mo: co a o la ga. A con inuaci´on, e al´ua una se ie de condiciones basadas en es os indicado es. Po ejemplo, comp ueba si el p ecio de cie e es supe io a la banda supe io de Bollinge , si el MACD es supe io a su l´ınea de se˜nal, si el RSI es supe io a 50, e c. Suma el n´ume o de condicionan es de su es a egia que son e dade os y luego ealiza una ecomendaci´on basada en si es e n´ume o es mayo o igual a 6. 64 Si en una de e minada onda el algo i mo es ´a en posesi´on del ´ı ulo y el n´ume o de condiciones e dade as es mayo o igual a 6, el expe o decide man ene la posici´on la ga. De o ma in e sa, si el n´ume o de condiciones e dade as es meno que 6, decide ende el ´ı ulo. La l´ogica es simila si el algo i mo u iese una posici´on co a. Es deci , si no posee el ´ı ulo en una onda en la que la can idad de condiciones e dade as supe a o iguala el alo 6 el bo expe o en odo ecomenda ´a al algo i mo comp a y en caso con a io man ene su posici´on. En e odos los bo s que se ´an e aluados y explo ados po el algo i mo Exp4, es e es el bo cuya es a egia p esen a la mayo complejidad de cons ucci´on debido a la a iedad de indicado es que igen su compo amien- o. Una de las objeciones que se pod ´ıan plan ea a es a es a egia es que conside a la impo ancia de odos los indicado es po igual. Es a objeci´on se undamen a en el hecho de que dependiendo de las condiciones del me cado unos indicado es pueden se m´as ele an es que o os. En cambio, la di e sidad de se˜nales que p esen a pe mi e al bo inc emen a su lexibilidad de decisi´on con espec o al es o de bo s ya que adquie e una isi´on m´as comple a del es ado del me cado. Es deci , su compo - amien o no siemp e queda de inido po los mismos indicado es. Con odo es o, el bo expe o en odo es una g an inco po aci´on al conjun o de bo s. Se pod ´ıa habe seguido incluyendo m´as es ilos de bo s de come cio en el conjun o de bo s, pe o la pa e ele an e de es a secci´on, en elaci´on al abajo de in de g ado, se cen a en el an´alisis del compo amien o de la soluci´on plan eada pa a esol e el p oblema que se iene explicando. De odas o mas, el c´odigo desa ollado incluye la implemen aci´on de o os bo s que pueden se incluidos, si se desea, en el conjun o de bo s con emplado po el algo i mo Exp4, como po ejemplo el expe o en Ichimoku, el expe o en Fibonacci, e c. 8.3. An´alisis de la Soluci´on Plan eada An es de comenza , en la igu a 19 se p esen a la leyenda pa a iden i ica a cada bo del conjun o de bo s en egado al algo i mo Exp4. Figu a 19: Leyenda de los bo s de come cio. De es a o ma es posible iden i ica con el colo azul al bo expe o en posiciones co as, con el na anja al bo expe o en posiciones la gas, con el e de al bo expe o en posiciones cambian es, e c. La inalidad con la que se ha sepa ado la leyenda de la p esen aci´on del las g ´a icas mos adas a con inuaci´on es inc emen a la isibilidad de los de alles, pe mi iendo mejo a la comp ensi´on de las si uaciones e lejadas. 8.3.1. Conside aciones p e ias P e io al an´alisis de la soluci´on plan eada, en es e apa ado se busca jus i ica dos decisiones omadas con espec o a la implemen aci´on de la soluci´on pa a supe a cie as limi aciones que a p io i p esen an los algo i mos Exp4 y Hedge de o ma conjun a. Conc e amen e, ha sido necesa io modi ica la unci´on de ecompensas y el c´alculo de las p obabilidades que p esen an los expe os de elegi cada b azo. Modi icaci´on en la Funci´on de Recompensas En un p incipio, se quiso es ablece 1 como alo pa a la ecompensa posi i a y 0 pa a la ecompensa nula. Pe o debido a la o ma ( c (a ) P [a =a ,π |p ]) que el algo i mo Exp4 iene de es ablece los cos es es imados pa a aque- llos bo s que eligen, en una de e minada onda, el mismo b azo que el seleccionado inalmen e po el algo i mo en dicha onda, se u o que ealiza una modi icaci´on. Es o se debe a que, si el algo i mo ace aba con su 65 decisi´on de b azo, aquellos bo s cuya ecomendaci´on coincid´ıa ob en´ıan una ecompensa de 1, que equi ale a un cos e de 0. Sus i uyendo dicho cos e en la ´o mula mencionada an e io men e, dichos bo s ob en´ıan un cos e es imado de 0. Po de ec o, Exp4 po de ec o o o ga un cos e es imado de 0 a los bo s que no ecomiendan el mismo b azo que el elegido po el algo i mo. Po ende, en es e escena io en el que el algo i mo acie a con su elecci´on, no hab ´ıa di e encia en e los cos es es imados de aquellos bo s que ace asen con su elecci´on y los que no. Como esul ado, al y como explica la ´o mula (w +1(a) = w (a)·(1 −ϵ)ˆc (a)) que el algo i mo Hedge aplica pa a ac ualiza los pesos de los bo s, ninguno de los pesos se modi ica ´ıa. Es o implica ´ıa que oma buenas decisiones no p opo ciona ´ıa ninguna “ en aja” a los bo s. Po an o, con la in enci´on de soluciona es e impasse se ha omado la decisi´on de conside a una ecompensa posi i a de 0,9 que e i a el p oblema an e io y, pa a man ene un equilib io, una ecompensa “casi nula” de 0,1. Modi icaci´on de las P obabilidades Indi iduales de Elegi un B azo Seg´un el lib o de Sli kins [2], que cons i uye el pila undamen al del desa ollo de es e abajo, la de inici´on e´o ica del algo i mo Exp4 hace e e encia a que, en cada onda, cada expe o debe de ol e la p obabilidad con la que ha ecomendado su b azo con la inalidad de que Exp4 pueda calcula la p obabilidad conjun a, en e odos los expe os, de escoge cada uno de los b azos posibles. Es o se debe a que Exp4 necesi a ene calculada la a iable P [a =a ,π|p ] pa a usa la como denominado en su paso 6. Su aplicaci´on en el denominado lle a impl´ıci a la condici´on de que su alo no puede se 0 o ce cano a 0, ya que en ambos casos el esul ado de la di isi´on se ´ıa nulo. Pa a ello, como ya indica Sli kins en una de sus ano aciones del cap´ı ulo 6, la soluci´on consis e en asegu a que las p obabilidades indi iduales de cada expe o de elegi o ecomenda cada uno de los b azos sean mayo que 0. Es o supone i en con a de la l´ogica de los concep os ap endidos has a el momen o, dado que un bo de come cio es un expe o que asocia con ex os a b azos siguiendo una es a egia p ede inida e in a ian e. Es deci , dado un de e minado con ex o, el bo siemp e decide ecomenda el mismo b azo de acue do a su es a egia, lo que implica una p obabilidad de elecci´on del 100 % sob e dicho b azo, quedando educidas a 0 las p obabilidades de ese bo de elegi el es o de b azos disponibles. Pa a comp oba que la soluci´on mencionada po Sli kins es necesa ia, se ha p obado a p og ama las p o- babilidades indi iduales de elecci´on de b azo de los bo s al y como se ha mencionado an e io men e, siguiendo es ic amen e la l´ogica y no los comen a ios de Sli kins. La igu a 20 ilus a el p oblema que sucede con los pesos de los bo s si las p obabilidades indi iduales de ecomendaci´on de cada bo son 100 % pa a el b azo indicado, bajo cada con ex o, po su es a egia y 0 % pa a el es o. Figu a 20: E oluci´on de los Pesos de los Expe os con γ= 0,2. An es de aden a nos en el an´alisis, es esencial eco da que la p obabilidad conjun a en e odos los bo s 66 de ecomenda el b azo a , inalmen e elegido po el algo i mo, es usada como denominado en el c´alculo de los cos es es imados, con los cuales Hedge ac ualiza los pesos de los bo s. Adem´as, es necesa io eco da que el c´alculo de es a p obabilidad iene en cuen a las p obabilidades indi iduales de ecomendaci´on de cada bo y los pesos de es os bo s. Cuan o mayo sea el alo de γ, m´as p obabilidades hay de que el algo i mo elija alea o iamen e un b azo, sin ene en cuen a los pesos de los bo s. Po an o, a pesa de que algunos bo s ya hayan su ido una ca´ıda de sus pesos y el algo i mo, di ´ıcilmen e, aya a segui sus ecomendaciones, con γ > 0 Exp4 pod ´ıa llega a elegi el mismo b azo que los bo s “in a alo ados”. En el caso de que, en una de e minada onda, el algo i mo elija un b azo que solo ha sido ecomendado po uno o pocos bo s cuyos pesos son muy bajos, se es a ´ıa incu iendo en una si uaci´on en la que la p obabilidad conjun a de inida an e io men e eciba un alo de 0 o ce cano a 0. Es a si uaci´on sucede a ias eces du an e el anscu so de la ejecuci´on e lejada en la igu a 20. Cada ez que se da es a si uaci´on, como po ejemplo en la onda 292, supone un an es y un despu´es en la e oluci´on de los pesos de los bo s. Se deja en el anexo 13 una depu aci´on “case a” ob enida du an e la ejecuci´on mencionada en caso de que se quie a ap ecia con mayo de alle lo acon ecido en la onda 292. Como se ha que ido demos a , es necesa io que las p obabilidades indi iduales de elecci´on de cada bo sean mayo es que 0 pa a odos los b azos. Si se in e p e a ex ualmen e la de inici´on de una pol´ı ica (asociaci´on de con ex os a b azos con p obabilidad del 100 %), los esul ados que se ob ienen ca ecen de alo po que en el c´alculo de los cos es es imados se di ide el cos e eal en e una p obabilidad de 0 o ce cana a 0. Po an o, pa a el es o de la secci´on se adop a una in e p e aci´on menos ealis a pe o que e i a el p oblema y pe mi e ealiza un an´alisis igu oso. Es a a ian e consis e en p og ama que el bo in o me al Exp4 de que su p obabilidad de ecomenda el b azo que indica su es a egia seg´un el con ex o es del 90 %, mien as que la del o o b azo no escogido es del 10 %. Es e simple y peque˜no epa o de la p obabilidad o al es su icien e pa a palia los p oblemas gene ados po la in e p e aci´on li e al de la eo ´ıa del p oblema. 8.3.2. An´alisis del Ho izon e Tempo al En la in oducci´on del p oblema de los bo s de come cio se mencionaba que el ho izon e empo al con- end ´ıa se de inido as un an´alisis p e io debido a la complejidad que p esen a. Es e es uno de los aspec os m´as ele an es del plan eamien o del p oblema po que los cos es es imados en los que incu e cada expe o en cada una de las ondas dependen en g an medida de la con igu aci´on del ho izon e empo al. Po ejemplo, pa a analiza 6 a˜nos se puede conside a una onda como cada uno de sus d´ıas, meses, imes- es, a˜nos, e c. Lo que a ´ıa es la sepa aci´on empo al en e cada da o del p ecio del ac i o. Po an o, se puede analiza el mismo in e alo de iempo combinando dis in as can idades de sepa aci´on empo al con dis in o n´ume o de ondas u ho izon e empo al. Debe eco da se que el bo ecibe una ecompensa u o a dependiendo del b azo que ha ecomendado y del siguien e p ecio p opo cionado po la uen e de los da os. En es e sen ido, no es lo mismo que el siguien e p ecio sea el del d´ıa siguien e que el de una semana despu´es o un mes despu´es. En de ini i a, las ecompensas de los bo s de come cio quedan al ampa o de la decisi´on que se ome en es e aspec o. Pa a un ac i o (Apple Inc.) y un in e alo de iempo (2015-2021) de e minados al aza , se han analizado las ecompensa medias ob enidas po el algo i mo pa a di e en es d´ıas de sepa aci´on en e cada da o, y los esul ados quedan e lejados en la igu a 21. 67 Figu a 21: Relaci´on en e la Sepa aci´on Tempo al de Con ex os (en d´ıas) y la Recompensa Media Ob enida Las ecompensas medias ob enidas po el algo i mo dependen de c´omo de bien se compo an los bo s en el escena io es ablecido. Po an o, a pa i de la igu a an e io , se puede deduci que los bo s de come cio inden mejo con una sepa aci´on empo al de 15 y 25 d´ıas en e los con ex os dia ios que ecibe el algo i mo Exp4. La explicaci´on de ´as de es a conclusi´on se encuen a en la o ma en la que son dise˜nados los indicado es. En la soluci´on plan eada, es os se o man analizando los n= 9,14,12,20,26 d´ıas an e io es. En onces, es l´ogico que la ampli ud del in e alo de los da os his ´o icos, que los bo s ienen en cuen a pa a escoge b azos, in luya en cu´al es el mejo escena io pa a los bo s. Po ejemplo, un bo que ecomienda en base a los da os ela i os al ´ul imo a˜no de la ida del ac i o iene in o maci´on ace ca de la e oluci´on del me cado a la go plazo. Es e bo nunca se ´a capaz de iguala el endimien o a co o plazo de un bo que ha sido in o mado ´unicamen e de los p ecios de la semana an e io , ya que es e ´ul imo iene una iel imagen del compo amien o del ac i o a co o plazo. Cabe des aca que la exis encia de es a disyun i a es independien e del alo de los hipe pa ´ame os γyε, asociados a la asa de explo aci´on y ap endizaje, espec i amen e. Po lo an o, eniendo en cuen a los alo es de ncomen ados, pa a el an´alisis inal de los esul ados se ha conside ado una sepa aci´on empo al de 18 d´ıas en e los p ecios consecu i os conside ados po la unci´on de ecompensas. Apa e de ap o echa al m´aximo el po encial de los bo s plan eados, ambi´en se consigue disminui la co e- laci´on en e los esul ados ob enidos po los bo s. Has a el momen o no se hab´ıa mencionado es a ci cuns ancia, pe o es impo an e ene en cuen a que, apa e de que el n´ume o de b azos disponibles en cada onda es muy educido (2), los bo s in e p e an el me cado y ecomiendan b azos de o ma muy simila en e s´ı. En conse- cuencia, sus ecompensas espe adas ienen compo amien os pa ecidos. Po an o, amino ando la co elaci´on en e los endimien os de los bo s se ayuda a que el algo i mo Exp4 ap enda, de mane a ´op ima, cu´ales son los mejo es bo s. En las igu as 22 y 23 se pueden obse a las di e encias en e las co elaciones en unci´on de la sepa aci´on empo al en e las ondas. Figu a 22: Co elaci´on en e los endimien os es- pe ados de los bo s con 3 d´ıas de sepa aci´on en e ondas. Figu a 23: Co elaci´on en e los endimien os es- pe ados de los bo s con 20 d´ıas de sepa aci´on en e ondas. 68 8.3.3. An´alisis de la Tasa de Ap endizaje En es a secci´on se es udia qu´e asa de ap endizaje es ´op ima pa a el p oblema p oblema plan eado. Se de ine ambi´en como ε. Pa a ello, se ealiza un an´alisis con el obje i o de comp ende el compo amien o del Exp4 bajo di e en es asas de ap endizaje. La asa de ap endizaje es un hipe pa ´ame o que iene mucha impo ancia en el modelo Exp4. De ine la apidez con la que el algo i mo compone una dis ibuci´on de pesos sob e los expe os que ya p esen a cla as di e encias en e las p io idades ela i as o o gadas a cada expe o, es deci la apidez con la que ap ende. Una asa al a cas iga mucho a los bo s que oman decisiones e ´oneas al p incipio de la ejecuci´on, educiendo demasiado su peso y dejando de ene sus ecomendaciones en conside aci´on. Es o puede se pe judicial pa a el endimien o inal ob enido po el algo i mo si los bo s menosp eciados son a la la ga los mejo es. Po el con- a io, con una asa de ap endizaje muy baja, el algo i mo a da ´ıa demasiado en ap ende y segui ´ıa muchas eces las suge encias de bo s que no son buenos, educiendo la ecompensa media inal. Po an o, se de inen dos ideas que se a a ´an de demos a seguidamen e: La p ime a es que una asa de ap endizaje baja implica que Exp4 a da mucho en ap ende pe o e mina ´a ap endiendo co ec amen e cu´ales son los bo s buenos. Po an o, aunque e mine ap endiendo bien, su ecompensa media inal no se ´a muy ele ada debido al las e que supone p oba demasiadas eces odos los bo s, incluyendo los malos, al p incipio. La segunda idea es que una asa de ap endizaje al a no ga an iza que Exp4 ap enda cu´ales son los mejo es bo s, po que puede cas iga les mucho al p incipio. En consecuencia, con la asa al a, la ecompensa media se ´a muy ele ada si Exp4 ap ende adecuadamen e desde el p incipio cu´ales son los bo s que mejo inden. Como ya se ha mencionado, es e ap endizaje ´apido no siemp e es e ec i o, ya que depende de la alea o- iedad. Hab ´a eces que el algo i mo no ap enda id´oneamen e y explo e en mayo medida los peo es bo s du an e el es o del ho izon e empo al, pe judicando eno memen e la ecompensa media inal. En la igu a 24, se lle a a cabo una p ueba del algo i mo con di e en es asas de ap endizaje. Como esul ado, se obse an a iaciones en la ecompensa media. Adem´as, se cons a a que el bo m´as ecuen emen e seleccionado y el bo con mayo peso en la ´ul ima onda no siemp e son los mismos. Tambi´en, pe mi e ap ecia la segunda idea comen ada an e io men e: con asas de ap endizaje al as muy simila es (0.4 y 0.5) Exp4 ob iene esul ados comple amen e dis in os. Con una ε= 0,4 alcanza una de las peo es ecompensas medias, mien as que con una asa ε= 0,5 la ecompensa media es mayo . Es o e leja la alea o iedad en las ecompensas a consecuencia de una asa de ap endizaje al a, al como se que ´ıa demos a . Figu a 24: Resul ados de Ejecu a la Soluci´on con de Dis in as Tasas de Ap endizaje ε. Pa alelamen e y de o ma adicional a la ejecuci´on del Exp4, se han gua dado en a iables auxilia es las ecompensas espe adas asociadas a las ecomendaciones de los bo s, simulando que los bo s abajan indi i- dualmen e el p oblema, aunque ealmen e Exp4 decida el anscu so de la soluci´on eniendo en cuen a odos los bo s. Es deci , a pesa de que el algo i mo sigue la ecomendaci´on de un solo bo y es ima las ecompensas pa a el es o de bo s, las a iables auxilia es gua dan las ecompensas que odos los bo s ob end ´ıan po su elecci´on. Es a simulaci´on pe mi e el an´alisis a pos e io i de qu´e bo s ob ienen las mejo es ecompensas independien e- men e de las decisiones omadas po algo i mo Exp4. Po ende, posibili a comp oba si la soluci´on plan eada a pa i del algo i mo Exp4 consigue ap ende a explo a los bo s m´as e icien es. 69 Figu a 25: Recompensa Media Espe ada de Cada Bo pa a ε= 0,39. Figu a 26: Pesos de los Bo s pa a ε= 0,39. Con una asa de ap endizaje ε= 0,39, la igu a 25 expone la simulaci´on a gumen ada an e io men e, y la igu a 26 ilus a la e oluci´on de los pesos de los bo s desde el pun o de is a del algo i mo Exp4, sin ene en cuen a la simulaci´on. Es a segunda g ´a ica pe mi e obse a el p oceso de ap endizaje del algo i mo ya que e le- ja c´omo a ´ıa su conside aci´on de odos los bo s. La combinaci´on de ambas g ´a icas da luga a la mani es aci´on de la exis encia o no de un ap endizaje adecuado po pa e de Exp4. Po ejemplo, si el bo expe o en RSI es el que mejo ecompensas medias o ece a lo la go de la simulaci´on y Exp4 nunca le o o ga un peso ela i o al o, es o signi ica que el algo i mo no es ´a ap endiendo a explo a el mejo bo . Los esul ados, en es e escena io con una asa de ap endizaje al a, son e iden es. El segundo mejo bo seg´un la simulaci´on, el bo expe o en c uce de medias m´o iles ( ojo), al p incipio llega a ob ene pesos de m´as de 40 %, pe o as alguna mala ecomendaci´on, su peso disminuye has a casi 0 di icul ando su pos e io econside aci´on. Po an o, queda cla o que Exp4 no es ´a ap endiendo bien po que penaliza demasiado al bo ojo al p incipio, a pesa de que es e sea en ealidad uno de los bo s con mayo es ecompensas medias espe adas. De es a o ma la segunda idea ha quedado p obada. Po o o lado, se analiza el compo amien o del algo i mo con una asa demasiado baja, conc e amen e ε= 0,01, median e las igu as 27 y 28. 70 Figu a 27: Recompensa Media Espe ada de Cada Bo pa a ε= 0,01. Figu a 28: Elecci´on de Bo s pa a ε= 0,01. La igu a 27 ilus a las ecompensas espe adas ob enidas con la simulaci´on. Cabe des aca que en es e caso es lige amen e di e en e a la simulaci´on ep esen ada an e io men e. Es o es po que las ecomendaciones de los bo s dependen de la posici´on la ga o co a que p esen e el algo i mo. El desa ollo de las posiciones del algo i mo depende ´a de c´omo el algo i mo decida en cada ejecuci´on. Como sus decisiones no son de e minis as, las posiciones p esen adas a los bo s a ´ıan en e ejecuciones y, en consecuencia, sus ecompensas espe adas ambi´en. Po es e mo i o, las g ´a icas se pa ecen pe o no son id´en icas. Es as di e encias se dan po el simple hecho de se dis in as ejecuciones, independien emen e de si se a ia la asa de ap endizaje o la de explo aci´on. De odas o mas, la a iaci´on de las ecompensas espe adas es an peque˜na que se suele man ene el o den de los mejo es bo s en e ejecuciones. Como se puede obse a en la igu a 28, odas los bo s se eligen casi uni o memen e du an e las p ime as 120 ondas; hay muy poca a iaci´on excep uando el bo ma ´on expe o en los indicado es MACD y bandas de Bollinge . A pa i de la onda 50, el algo i mo elije m´as eces el bo ma ´on que los dos mejo es bo s seg´un 27, el expe o en posiciones la gas (na anja) y el expe o en medias m´o iles ( ojo). Aunque inalmen e aumen e el peso de es os dos mejo es bo s, ha elegido demasiadas eces a los peo es bo s, y es o p o oca que la ecompensa media inal del algo i mo sea muy baja. Adem´as, como la asa de ap endizaje es an peque˜na, a pesa de que pasen las ondas, el algo i mo sigue man eniendo al bo ma ´on con mucho peso, a´un siendo uno de los peo es bo s, como e idencia la igu a 27. Po lo an o, ha quedado demos ado que elegi una asa de ap endizaje baja no es bene icioso pa a el algo i - mo po que la ecompensa ob enida se educe. Tampoco se debe op a un alo al o ya que hay mucho iesgo de que no ap enda las mejo es pol´ı icas. Po ello, se ha de ec ado una buena zona de abajo, pa a ob ene mejo es ecompensas, cuando las asas de ap endizaje se encuen an en el in e alo de 0,15 y 0,25 ap oximadamen e. 71 En el an´alisis inal de los esul ados se ejecu a ´a la soluci´on con un alo ε= 0,2. 8.3.4. An´alisis de la Tasa de Explo aci´on La asa de explo aci´on γin luye en la can idad de eces que el algo i mo explo a un b azo alea o iamen e sin segui las ecomendaciones de los bo s. La elaci´on en e el alo de es a asa y la ecompensa media ob enida se puede analiza a a ´es de la igu a 29. Figu a 29: Relaci´on en e el Ni el de Explo aci´on y la Recompensa Media. Como ya se comen ´o en la in oducci´on, el n´ume o de b azos disponibles pa a cada onda es K= 2. Es e n´ume o de b azos es un can idad bas an e limi ada y no exis e la necesidad de ealiza una g an explo aci´on con el obje i o de comp oba el endimien o medio de odos los b azos. En muy poco iempo, po el simple anscu so de las ondas, el algo i mo hab ´a explo ado sob adamen e cada uno de los dos b azos. De odas o mas, no es ´a de m´as o o ga un cie o alo a es e hipe pa ´ame o pa a p e eni si uaciones en la que los bo s se es anquen con una misma ecomendaci´on y no consigan e el po encial de o o b azo dado un con ex o de e minado. Po ello, pa a el an´alisis inal de los esul ados se usa ´a una γ= 0,05. 8.3.5. Pues a en P ´ac ica de la Soluci´on Con el obje i o de soluciona el p oblema de los bo s de come cio de mane a ´op ima, se ha conside ado una sepa aci´on en e ondas de 18 d´ıas, una asa de ap endizaje ε= 0,2 y una asa de explo aci´on γ= 0,05. Se ilus a de nue o la leyenda de los bo s en la igu a 30. Figu a 30: Leyenda. A con inuaci´on se plan ean un escena io pa a comp oba c´omo se compo a la soluci´on. En es e caso, el algo i mo se si ´ua en e mediados del a˜no 2015 y inales del 2019 pa a ope a en el me cado sob e las acciones de la emp esa NVIDIA Co po a ion (NVDA) dedicada al desa ollo de so wa e y ha dwa e. Pa a se capaces de in e p e a el compo amien o del algo i mo es necesa io se conscien es de la e oluci´on del p ecio del ´ı ulo du an e el pe iodo mencionado, e lejada en la igu a 31 72 ples, cuya me odolog´ıa ya se ha es udiado, y se han aplicado o as dos pol´ı icas m´as, que son m´as complicadas, y apo an mucho alo a es e caso. Es as dos ´ul imas pol´ı icas apa ecen en las siguien es subsecciones 9.4.2 y 9.4.3. 9.4.1. Pol´ı icas Simples A con inuaci´on, se indaga ´a las pol´ı icas m´as sencillas, que no po ello son p escindibles. A pesa de su simpleza, an a apo a ideas muy in e esan es y ayuda ´an a llega a mejo es conclusiones. P ime o, hay que a comenza con la pol´ı ica m´as simple: elegi el mejo b azo siemp e. Se selecciona el mejo b azo de acue do a su ecompensa media µ(a). Pa a desa olla es a es a egia ha sido u ilizado el ´ Epsilon- A a icioso, o Epsilon-G eedy en ingl´es, con un ´epsilon igual a 0. Hay que ene p esen e que el ´epsilon en es a pol´ı ica ep esen a la asa con la que el algo i mo explo a ´a en e los b azos. Po lo que si se da un ϵ= 0, nunca explo a ´a, y es o asegu a que siemp e explo a ´a el mejo b azo. Du an e la ase de en enamien o la ecompensa media de cada b azo se ´a almacenada. De es e modo, la pol´ı ica sab ´a cual es el b azo que iene mejo es ecompensas. En la ase de e aluaci´on, con Exp4, dicha pol´ı ica elegi ´a siemp e el b azo que mejo ecompensa haya enido du an e el en enamien o. Po ejemplo, si el mejo b azo en la p ime a pa e es la ca ego ´ıa musical, siemp e selecciona ´a es e b azo: musical. Lo in e esan e de es a es a egia es e c´omo endi ´a un algo i mo que solo elija el mejo b azo sin ene en cuen a el con ex o. Realmen e se es ´a poniendo a p ueba si la in o maci´on con ex ual es de u ilidad, ya que en caso de que es a p ime a pol´ı ica sea la mejo , se pod ´a deduci que el con ex o no es ´a mejo ando el algo i mo. Debido a es o, con ecomenda siemp e el mejo g´ene o de pel´ıculas ya se consegui ´ıan buenas ecompensas sin ene en cuen a la in o maci´on con ex ual. Es a al e na i a esul a a ac i a pues o que puede se que el g´ene o cinema og ´a ico m´as popula esul e se siemp e la mejo opci´on. Aunque un sis ema de ecomendaci´on puede con a con g´ene os de nicho como an asy osci- i, es os pueden ene menos ´exi os con una audiencia m´as gene al. En luga de ello, pod ´ıa se p e e ible op a siemp e po ecomenda el g´ene o que consis en emen e ob iene mejo es cali icaciones p omedio en e odo el p´ublico, en es e caso se ´ıan los usua ios de en enamien o. Po ejemplo, un g´ene o como el suspense pod ´ıa se una elecci´on m´as ace ada pa a una ecomendaci´on que busque sa is ace a una amplia gama de espec ado es. En segundo luga , hay o a pol´ı ica simple: ´ Epsilon-A a icioso con un ´epsilon igual a 0.95 (ϵ= 0,95). Es a pol´ı ica ealmen e se cen a ´a en explo a en e odos los b azos en la inmensa mayo ´ıa de las ocasiones. Las en ajas que o ece implemen a es a pol´ı ica son dos: Po un lado, se saca pa ido de es a pol´ı ica pa a la ase de en enamien o. Tal y como se ha explicado en el apa ado an e io , dicha pol´ı ica es usada pa a explo a en la p ime a e apa de en enamien o con el obje i o de que los expe os puedan ecaba da os en e los 18 b azos con sus ecompensas y con ex os. Su p op´osi o es que con la in o maci´on ecabada, las pol´ı icas puedan hace buenas ecomendaciones en la segunda pa e al Exp4. Po o o lado, ambi´en si e como pol´ı ica pa a obse a c´omo de buena se ´a una es a egia que es p ´ac ica- men e alea o ia (explo a casi siemp e). Es o pe mi i ´a ex ae conclusiones sob e si elegi alea o iamen e puede ene sen ido. Se e ´a si un ´ Epsilon-A a icioso que explo a se ´a p emiado po el algo i mo Exp4. Debido a es o, se puede deci que la p ime a pol´ı ica ep esen a ´ıa la explo aci´on y es a segunda la explo aci´on. Una ez que han sido expues as las dos p ime as pol´ı icas, las que se denomina ´ıan simples, se desa olla ´an las pol´ı icas complejas. Hay un apa ado dedicado pa a cada una de es as dos es a egias. 9.4.2. Fil o Colabo a i o Basado en Vecindad Es e apa ado ahonda en la e ce a pol´ı ica: il o colabo a i o basado en ecindad. Pa a desa olla es a idea, la in o maci´on ha sido ob enida de es a uen e [11]. Es e algo i mo nace de la necesidad de algo i mos especializados en ecomenda como los que se usan en p´aginas web, en iendas online como Amazon, pel´ıculas de Ne lix o no icias de Google. 79 Po ejemplo, se p esen a el caso de Ne lix. Ne lix se und´o como una emp esa de alquile de discos de ´ıdeo digi al (DVD) po co eo, que luego se expandi´o a la en ega de con enido en l´ınea, o ambi´en llamado s ea- ming. Ac ualmen e, el p incipal negocio de Ne lix es p opo ciona en l´ınea pel´ıculas, se ies y o os p og amas de ele isi´on po medio de susc ipciones. Ne lix pe mi e a los usua ios cali ica las pel´ıculas y p og amas en una escala de 5 pun os. Almacena las acciones de los usua ios en ´e minos de lo que en. Es as cali icaciones se usan pa a hace ecomendaciones pe sonalizadas, lo cual mejo a la expe iencia del usua io y puede ayuda a mejo a la leal ad y e enci´on del clien e. Pa a man ene se como uno de los l´ıde es en el me cado, Ne lix ha p obado con muchos sis emas de eco- mendaci´on y ha desa ollado compe iciones donde se pon´ıan a p ueba dis in os sis emas como el que se a a ´a aho a. Tambi´en se usaba una me odolog´ıa simila a la que se desa olla en es e sis ema, en enaba sus algo- i mos con unos usua ios de en enamien o y luego med´ıa su endimien o con o os usua ios de e aluaci´on, o es . Adem´as, cabe se˜nala que es a pol´ı ica se cen a en analiza la in o maci´on con ex ual del usua io. El obje- i o del TFG es desa olla bandidos con ex uales mul i-b azo eniendo en cuen a es e ipo de da os. A pesa de que se pueden analiza las ca ac e ´ıs icas de las pel´ıculas (que son los ´ı ems), es e il o colabo a i o end ´a la pe spec i a que ha sido comen ada: ecomenda en base al con ex o del usua io. Po o o lado, hay m´as in o maci´on de los usua ios en la base de da os que de los ´ı ems pa a ealiza el sis ema ecomendado , po lo que es con enien e aplica el p ime en oque. Pa a comenza , se explica ´a lo que son los algo i mos de il o colabo a i o basados en ecindad, que ambi´en son denominados como algo i mos basados en memo ia. Es os algo i mos pa en de la p emisa de que usua ios pa ecidos ienen un pa ´on de compo amien o simila . Conduc as que son semejan es se pueden obse a a la ho a de alo a ´ı ems, y po es o, los ´ı ems pa ecidos ob ienen alo aciones simila es de usua ios con un cie o g ado de semejanza. Se llama ´ı em a un obje o o a ´ıculo que el usua io a a alo a ; en Amazon el ´ı em es un p oduc o, como un lib o, mien as que en el ecomendado de Google el ´ı em es una no icia. Hay dos ipos de algo i mos de ecindad: Fil o colabo a i o basado en usua ios. En es e caso, las alo aciones de usua ios simila es espec o a un usua io obje i o A son usadas pa a hace le ecomendaciones a dicho obje i o A. Las alo aci´on que se espe a que enga A de un ´ı em es la alo aci´on media ponde ada del g upo de iguales. El p oceso de ponde a la media de cada miemb o del g upo de iguales se ´a explicado pos e io men e. Fil o colabo a i o basado en ´ı ems. En es a es a egia, como se p e enden hace ecomendaciones de un ´ı em obje i o B, deben de e mina se un conjun o S de ´ı ems, que son simila es al ´ı em B. Luego, pa a p edeci la alo aci´on de un usua io A del ´ı em B, se ienen en cuen a las alo aciones de ese usua io A pa a el ´ı ems pe enecien es al conjun o S. De es a mane a, se e ´a c´omo ha e aluado A obje os an´alogos al que se le quie e ecomenda . La media ponde ada de dichas e aluaciones es u ilizada pa a p edeci cu´al a a se la alo aci´on del usua io A del ´ı em B. Una ez que han sido obse adas las dos p incipales clases de es e algo i mo, se puede ap ecia la p incipal di e encia. En el p ime o ipo, se ecomienda en base a alo aciones que han dado usua ios simila es mien as que en la segunda clase se p edice la alo aci´on del ´ı em de acue do a la alo aci´on que ha dado ese mismo usua io a ´ı ems simila es. L´ogicamen e, en es e caso debe aplica se con un il o colabo a i o basado en usua ios pa a explo a su in o maci´on con ex ual. La idea es abaja con un g upo de iguales de un usua io obje i o, que es aquel al que se le desea ecomenda una pel´ıcula. Po ello, un g upo de iguales es c eado y los miemb os pe enecen a los usua ios de en enamien o. Se usa ´an sus alo aciones pa a ecomenda la mejo ca ego ´ıa posible de pel´ıcula a usua ios obje i os, que son miemb os conjun o de usua ios de e aluaci´on. Adem´as, hay dos o mas de en oca el algo i mo de ecindad: La p ime a o ma se ´ıa p edeci la alo aci´on de la combinaci´on de un usua io y un ´ı em. Es el m´e odo m´as simple y p imi i o de los sis emas ecomendado es. En es e caso, es necesa ia la alo aci´on de un usua io, y se p edice un ´ı em. La p edicci´on de es a cali icaci´on se basa gene almen e en las alo aciones del usua io de o os ´ı ems y de las e aluaciones de o os usua ios a es e ´ı em. La segunda al e na i a es de e mina los k´ı ems m´as p ´oximos, ambi´en llamados op−k´ı ems, o a pa i de aho a los usua ios m´as p ´oximos, es deci , el g upo de iguales. Es e en oque op a po iden i ica los k usua ios o ´ı ems m´as ele an es. 80 La implemen aci´on u iliza la segunda opci´on y g acias al g upo de iguales es posible hace una ecomenda- ci´on a o o usua io en base a su con ex o. El algo i mo elegi ´a un b azo u o o pa a un usua io en unci´on del g upo de iguales. Es e se ´a el g upo de usua ios que m´as se puedan asemeja al usua io obje i o. Se oma 5 como el n´ume o de usua ios de un g upo de iguales. El algo i mo desa ollado se basa en [11] y es una adap aci´on al modelo. U iliza los usua ios m´as simila es al usua io al que el sis ema ecomendado p e ende ecomenda . Pa a calcula la simili ud en e dos usua ios, se usa el coe icien e de la simili ud del coseno. Cabe se˜nala que el g upo de iguales an a se del en enamien o, y el usua io al que se le a a ecomenda , pe enece ´a a la e aluaci´on. As´ı, se ga an iza que en ning´un caso el p opio usua io pe enezca al g upo de sus usua ios semejan es. Es a es a egia pe mi i ´a ag upa a los usua ios que ienen un con ex o pa ecido al usua io obje i o pa a ealiza una ecomendaci´on. Po es o, cie amen e se es a ´a e aluando la elaci´on en e el con ex o, los b azos y las ecompensas. Si es a pol´ı ica es e icaz, se pod ´a a i ma que ecomenda seg´un las p e e encias de usua ios con con ex os pa ecidos (edad, abajo y sexo) es una buena idea. T as habe explicado los undamen os de es a pol´ı ica, se mues a el coe icien e de simili ud del coseno y c´omo se ha u ilizado en el c´odigo: Simili ud del coseno: CosSim(u, ) = u· ||u||·|| || Aqu´ı uy son ec o es, u· es el p oduc o escala , y ||u|| y|| || son las no mas magni udes de uy , espec i amen e: ||u|| =qu2 1+u2 2+. . . +u2 n En es e caso, los ec o es ep esen a ´ıan la in o maci´on con ex ual de un usua io: sexo, edad y ocupaci´on. Ha sido u ilizada la dis ancia del coseno, que se de ine a con inuaci´on: Dis ancia del coseno: CosDis (u, )=1−CosSim(u, ) donde CosSim(u, ) es la simili ud del coseno en e uy , como ha sido mos ada an e io men e. Los usua ios con meno dis ancia espec o a el usua io obje i o o ma ´an el g upo de iguales. La explicaci´on se mues a con el siguien e ejemplo. Si el usua io obje i o es un homb e de 45 a˜nos, educado , si hay o o usua io, pe enecien e al conjun o de usua ios de en enamien o, que iene 50 a˜nos, es homb e y ambi´en educado , la dis ancia del coseno se ´a muy peque˜na en e es os dos usua ios. Po ello, se ´a muy p obable que ese usua io pase a o ma pa e del g upo de iguales usua ios. Con es e y cua o usua ios m´as, se o ma ´ıa del g upo de iguales. Con dicho conjun o el algo i mo abaja a pa a maximiza la ecompensa de dicho usua io obje i o. Se hace de la siguien e mane a: En p ime luga , es obse ado el con ex o x de dicho usua io obje i o. Despu´es, son ob enidos los k= 5 usua ios que m´as se pa ecen usando la dis ancia del coseno. Pa a cada usua io del g upo de iguales se gua dan las ecompensas de cada b azo en un ec o . Se calcula la ecompensa media de cada b azo seg´un las ecom- pensas de los 5 usua ios. Y inalmen e, es seleccionado el b azo que enga mejo ecompensa media. El obje i o consis e en mos a la ca ego ´ıa de pel´ıcula que haya enido m´as ´exi o medio en e usua ios simila es. Vol iendo al caso an e io , si hubie a un a ´on de 45 a˜nos que es educado . El algo i mo de il o colabo a i o ob iene los 5 usua ios que m´as se asemejan. Despu´es, calcula la ecompensa media pa a cada b azo seg´un las o aciones de es os 5 usua ios an´alogos. Pa a ilus a lo, se pod ´ıa supone que las pel´ıculas de ac ion ienen una media de 0,61, las de d ama 0,72, las de ilm-noi 0,83.... T as habe calculado la media de cada ca ego ´ıa, el algo i mo escoge ´a la ca ego ´ıa que m´as media, en es e caso ilm-noi , y ecomenda ´a una pel´ıcula de ilm-noi al usua io obje i o. Realmen e, se pa e de la p emisa de que buenos b azos en con ex os an e io es o ece ´an al os endimien os en el con ex o ac ual de acue do al g upo de iguales. Es a hip´o esis es pues a a p ueba en el apa ado de esul- ados donde se analiza ´a si ha in luido de mane a de e minan e el con ex o o simplemen e con una pol´ı ica de 81 elegi el mejo b azo el algo i mo Exp4 ob end ´ıa buenas ecompensas. Asimismo, pod ´ıa sucede que el con- ex o sea un ac o esencial pa a la gene aci´on de ecomendaciones, pe o es a pol´ı ica espec´ı ica no esul e se la m´as adecuada a ene en cuen a. Consecuen emen e, ecomenda seg´un las p e e encias del g upo de iguales puede no se la es a egia m´as in eligen e pa a es e caso y, po consiguien e, hab ´a es a egias m´as ace adas pa a ecomenda conside ando el con ex o. Al adap a es a pol´ı ica al algo i mo Exp4 se ha enido que ealiza una unci´on que calcule las p obabilida- des de que un b azo sea elegido. Dicho m´e odo calcula las medias de los b azos. Si an e un con ex o, la media de un b azo aies mayo que la media del es o de b azos de ol e ´a 1 pa a el b azo iya que se ´a elegido con o al ce eza. Po el con a io, si la media no es la m´as al a, de ol e ´a 0. Como se puede obse a , selecciona ´a siemp e el b azo que m´as media enga pa a el g upo de iguales. El pseudoc´odigo del algo i mo se ´ıa el siguien e: Algo i mo 9.15 Fil ado colabo a i o con algo i mo de ecindad. 1: Al inicializa : Se almacenan los con ex os de los usua ios de en enamien o, con sus b azos ac i ados y sus ecompensas asociadas. 2: o cada onda = 1,2, . . . do 3: Se obse a el con ex o x ∈Xde un usua io. 4: Pa a odos los con ex os de los usua ios de en enamien o ∀xi∈X ain, se calcula la dis ancia del coseno espec o a x :CosDis (x , xi)=1−CosSim(x , xi). 5: Se ob ienen los usua ios del g upo de iguales, los kcon ex os m´as simila es a x , que co es- ponden a las kdis ancias m´as peque˜nas den o de los usua ios de en enamien o o denados po CosDis (x , xi) de meno a mayo . 6: Se calcula la ecompensa media pa a odos los b azos ∀a∈Ade las alo aciones del g upo de iguales. 7: Se selecciona el b azo a con mejo ecompensa media. 8: end o Po ´ul imo, debe menciona se alguno de los ac o es po los cuales se ha decidido implemen a es e expe o. Es un algo i mo que pe mi e la pe sonalizaci´on. Los sis emas de il ado colabo a i o p opo cionan ecomen- daciones pe sonalizadas basadas en el compo amien o de usua ios simila es. A di e encia de o as ´ecnicas de ecomendaci´on como el il ado basado en el con enido, el il ado colabo a i o basado en usua ios no equie e ninguna in o maci´on espec´ı ica sob e los´ı ems, es o hace que encaje pe ec amen e con el modelo. Su lexibilidad ambi´en es un aspec o a se˜nala ya que po ejemplo, se puede es ablece a bi a iamen e el n´ume o de k ecinos as´ı como o os ajus es del modelo. Tambi´en, un pun o a a o es que es una pol´ı ica que apo a mucho alo a la in es igaci´on. Es a es a egia se es ´a abajando desde una pe spec i a di e en e y pe mi e es udia algo i mos especializados en sis emas de ecomendaci´on. 9.4.3. Red Neu onal como Bandido Con ex ual Po ´ul imo, es e apa ado se aden a ´a en la pol´ı ica inal que es una de las ideas m´as es imulan es con la que se ha abajado en es a implemen aci´on. Es a pol´ı ica que ha necesi ado de muchas p uebas, hace uso de una ed neu onal como si ue a un bandido con ex ual. Pa a implemen a la, se u iliza Tenso low, y Ke as, en Py hon. Es as he amien as pe mi en abaja con una ed neu onal de mane a lexible y adap a la como un bandido. Hay que se˜nala que la idea es p opia de los au o es del abajo. Dicha idea ha sido posible ma e iali- za la g acias a las uen es mencionadas y a los conocimien os adqui idos con es e abajo. La in o maci´on con la que se ha abajado pa a desa olla la ed neu onal y los concep os e´o icos de ´as de la explicaciones es ´an en [20]. Las edes neu onales se implemen an adecuadamen e g acias a dicha uen e. El conocimien o adqui ido en es e campo se aslada al ma co de los bandidos mul i-b azo. Es os modelos pueden apo a mucho alo po los siguien es mo i os: Son algo i mos que o ecen buenas al e na i as po que ienen capacidad de maneja g andes can idades de da os y ca ac e ´ıs icas. En es e caso, hay muchos usua ios y 1 mill´on de alo aciones de pel´ıculas, po lo que se ealizan muchas ecomendaciones y es o es un pun o a a o de las edes neu onales. 82 Las edes neu onales ienen la habilidad de es ablece elaciones in e esan es en e m´ul iples ca ac e ´ıs icas. En es e sis ema de ecomendaci´on, se ienen en cuen a el con ex o como da os de en ada y las ecompensas ( alo aciones de los usua ios). Es os algo i mos ienen la capacidad de ex ae complejas elaciones en e las a iables con las que es ´an abajando pa a op imiza los esul ados. La ed neu onal se adap a con enien emen e al modelo. Es o es debido a que como es necesa io en ena a los expe os, es la ocasi´on ideal pa a c ea una ed neu onal con los da os de en enamien o. De es e modo, pa a la ase de e aluaci´on hab ´a una ed o almen e en enada y se ´a posible e alua su endimien o. De mane a esumida, la aplicaci´on de una ed neu onal a un p oblema de bandido mul i-b azo se hace pa a que es a ed modele la elaci´on en e el con ex o y las ecompensas de los b azos. La en ada a la ed neu onal es la in o maci´on con ex ual y la salida es una dis ibuci´on de p obabilidades sob e los b azos de mane a que se elige un b azo en unci´on de es a dis ibuci´on. Es a pol´ı ica o ece ´a o o en oque di e en e pa a cap u a las elaciones en e el con ex o y los b azos. Al con a io que la e ce a pol´ı ica, il o colabo a i o usando el algo i mo de ecindad, las edes neu onales calcula ´an dis in as conexiones en e con ex os, b azos y ecompen- sas sin u iliza el g upo de iguales. Es e con as e en e las dos pol´ı icas se ´a de g an u ilidad pa a analiza los esul ados inales y en ende c´omo es m´as con enien e conside a el con ex o en es e caso de uso. La idea ha sido u iliza una ed neu onal mul iclase. Dicha ed iene 18 clases o neu onas en su ´ul ima capa. Es deci , una clase pa a cada b azo. Pa a un con ex o la ed neu onal de uel e las p obabilidades de lo bueno que se ´a cada b azo. Es o signi ica que dado un con ex o, la ed neu onal o ece ´a p obabilidades pa a cada b azo. La suma de odos los b azos da ´a 1, y hay 18 p obabilidades, una po cada b azo. En las p ime as implemen aciones la ed neu onal eleg´ıa alea o iamen e en es a unci´on de p obabilidad pe o dado que las e- compensas son IID (no hay un ad e sa io), se ob end ´an ecompensas m´as al as si es seleccionado el b azo con mayo p obabilidad. No es imp escindible escoge el b azo de acue do a la alea o iedad po que las ecompensas no son ad e sa ias, sino que son IID. Po ello, as a ias p uebas, la ed neu onal inalmen e escoge siemp e el b azo con mayo p obabilidad. Una ez explicada c´omo ac ´ua la ed neu onal como bandido mul i-b azo, se de alla c´omo es exac amen e es a ed y po qu´e ha sido dise˜nada de una de e minada mane a. El abajo se ha ealizado con una ed de es capas densas, que es ´an comple amen e conec adas. Dichas capas ienen 120, 70 y 18 neu onas espec i amen e. Es o es debido a que se ha implemen ado un modelo complejo, con muchas neu onas. Seg´un la documen aci´on expues a en [20] se ha op ado po es a es a egia con el obje i o de c ea un modelo complejo a˜nadiendo e- gula izaci´on. Es o es debido a que al ene un modelo complejo (muchas neu onas), el modelo alcanza mucha a ianza po que da demasiado peso a los pa ´ame os del modelo y se p oduce un sob eajus e espec o a los da os de en enamien o. Pa a e i a dicho sob eajus e, se usa la egula izaci´on. El p op´osi o undamen al del modelo es ealiza ecomendaciones de calidad con los usua ios de e aluaci´on, no con los de en enamien o. El in es c ea un modelo que gene alice bien. Po ello, odas las medidas que se han omado han sido de acue do a es e obje i o. Po ejemplo, se ha ajus ado la asa de ap endizaje, la egula izaci´on, las unciones de ac i aci´on y la p´e dida pa a ga an iza es a gene alizaci´on. Aunque aqu´ı se comen an los hipe pa ´ame os elegidos, se han hecho p uebas y simulaciones con m´ul iples opciones. Debido a es o, se mos a ´an las elecciones inales que mejo op imizan la ed. El p oceso de selecci´on de es os pa ´ame os ha sido i e a i o y ha eque ido de muchas simulaciones pa a maximiza la ecompensa. La elecci´on de la asa de ap endizaje ha sido de 0,05. Es e es un hipe pa ´ame o c ucial en las edes neu ona- les que de e mina c´omo de ´apido se quie en ac ualiza los pesos de es e modelo. Si la asa de ap endizaje ue a muy g ande, el modelo puede con e ge muy ´apidamen e. Sin emba go, como es posible en ena al modelo con muchos da os de en enamien o, se ha es ablecido una asa igual a 0,05 pa a que con e ga de mane a adecuada y ap enda co ec amen e. Pa a lle a a cabo la egula izaci´on, se ha u ilizado una egula izaci´on L2 que p e iene el sob eajus e. Es a egula izaci´on a˜nade una penalizaci´on a los pesos g andes del modelo pa a que no se ajus e demasiado a los da os de en enamien o disminuyendo la a ianza del modelo y mejo ando la gene alizaci´on. El alo elegido de la egula izaci´on, λ, ha sido 0,015 en la capa de en ada y la capa in e media. Respec o a las unciones de ac i aci´on, elu ha sido la unci´on de ac i aci´on elegida pa a la capa de en ada y la ocul a (la del medio). Es a unci´on ayuda a hace m´as ´apido el p oceso de descenso de g adien e, que es la o ma en la que se en ena la ed. En la capa de salida es u ilizad la unci´on de ac i aci´on so max que se usa a menudo en la clasi icaci´on mul iclase, que en es e caso se ealiza con 18 clases o b azos. 83 Figu a 35: Red neu onal como bandido mul i-b azo. Tambi´en hay que menciona que se han usado unas ´epocas con un alo de 170. El obje i o es que la ed neu onal en ene lo su icien e y pueda con e ge adecuadamen e sin sob epasa se con los da os de en e- namien o. Despu´es de muchas p uebas y depu aciones al ededo de es a ci a se encuen an esul ados co ec os. Finalmen e, el modelo se compila con la p´e dida de “ca ego ical c ossen opy” y el op imizado “Adam”. Ca ego ical co ssen opy es una unci´on de p´e dida com´unmen e usada en p oblemas de clasi icaci´on mul iclase. Adam es un algo i mo de op imizaci´on que se u iliza pa a ac ualiza los peso de la ed en unci´on de los da os de en enamien o. La asa de ap endizaje se pasa a Adam que pe mi e con ola la elocidad a la que el modelo ap ende. La igu a 35 mues a c´omo se e ´ıa la ed neu onal de mane a simpli icada. Hay es capas: La p ime a capa de en ada de 120 neu onas, la capa in e media (u ocul a) 70 neu onas, y la capa de salida de 18 neu onas (una pa a cada b azo). Como se puede ap ecia , las en adas, son el con ex o del usua io mien as que cada una de las neu onas de salida ep esen a ´ıa un b azo. La igu a es de g an ayuda ya que pe mi e isualiza la es uc u a de la ed Po ejemplo, du an e el en enamien o, si se ienen el b azo 2 con una ecompensa de 0.8 pa a un con ex o x , se en ena ´ıa la ed neu onal con el con ex o como en ada. En la salida, al b azo 2 se le asigna una ecompensa de 0.8, mien as que al es o de b azos se les da una ecompensa de 0. De es a mane a solo se ac ualiza ´an los b azos ac i ados en cada onda. Como cada pel´ıcula iene a ias ca ego ´ıas, cuando la ed es en enada con la alo aci´on de un usua io, se ha ´a a ias eces. Una ez pa a cada ca ego ´ıa pe enecien e a la pel´ıcula elegida. En cada una de es as eces se ´a usada la misma ecompensa pa a ese b azo y el mismo con ex o como en ada. Si en el ejemplo mencionado ambi´en se ac i a ´a el b azo 7, po que la pel´ıcula pe enece a ambos g´ene os, an o el b azo 2 como el b azo 7 se ´ıan ac ualizados con una ecompensa de 0.8. Igual que an es, el es o de b azos end ´ıan una ecompensa de 0. A con inuaci´on, se mues a un algo i mo que ilus e cu´ales son los pasos a segui de la ed neu onal. Hay una exposici´on de es os dos pseudoc´odigos, uno pa a el en enamien o y o o pa a la e aluaci´on: Al e la es uc u a del c´odigo, los pasos que sigue la ed neu onal quedan muy cla os. Median e es e en e- namien o consigue es ablece elaciones en e con ex os y las ecompensas asociadas a los b azos ac i ados. Hay que ene en cuen a que una pel´ıcula iene a ias ca ego ´ıas y hay e oalimen aci´on pa cial, po lo que ob iene la ecompensa pa a a ios b azos, los b azos ac i ados que co esponden a los g´ene os de la pel´ıcula seleccionada. Aquellos b azos que engan buenas ecompensas se ´an elegidos con mayo p obabilidad du an e la siguien e e apa. Po lo an o, es e en enamien o es undamen al y en unci´on de c´omo se ealice la ed neu onal o ece ´a unos buenos endimien os o no. Hay que menciona que en el c´odigo la ed neu onal es en enada al inal del en enamien o, es deci , no 84 Algo i mo 9.16 Red neu onal en el en enamien o. 1: o cada onda = 1,2, . . . do 2: Se obse a el con ex o x ∈Xde un usua io. 3: Se ecibe el b azo elegido, que ambi´en es b azo ac i ado, a∈Ay los b azos ac i ados ai, aj... ∈A. 4: Pa a cada b azo ac i ado a∈A, se en ena la ed con x (como a iable de en ada), y con la ecompensa ob enida como salida de ese b azo. El es o de b azos no ac i ados, a∈Aand !ac i ado, les asigna una ecompensa = 0. 5: end o en ena onda a onda como se hace en un bandido con encional que se ac ualizan los pesos as obse a una ecompensa, sino que en ena as habe pasado po odos los usua ios de en enamien o. Es o se hace pa a aho a cos es de iempo y ejecu a el algo i mo m´as ´apidamen e. Po lo an o, en ena ´a con odos los usua ios de una sola ez. Algo i mo 9.17 Red neu onal en la e aluaci´on. 1: Al inicializa : En ena la ed neu onal con los usua ios de en enamien o. 2: o cada onda = 1,2, . . . do 3: Se obse a el con ex o x ∈Xde un usua io. 4: Se calcula una dis ibuci´on de p obabilidades pa a los Kb azos dado ese con ex o x . 5: Se selecciona el b azo a con mayo p obabilidad. 6: end o Despu´es de habe en enado dicha ed neu onal, se puede conside a que ya es una expe a y el algo i mo Exp4 la u iliza ´a como una de sus pol´ı icas. Como se ha ecalcado an es, la ed neu onal no en ena du an e la e aluaci´on del Exp4 po que ya es una expe a y el obje i o es obse a cu´ales son las mejo es y peo es pol´ı icas. Po ello, en es a ase de e aluaci´on la ed no se ´a ac ualizada. En dicha e apa de e aluaci´on, la ed neu onal calcula ´a una dis ibuci´on de p obabilidades dado un con ex o eniendo en cuen a los da os con los que hab´ıa sido en enado an e io men e. Aqu´ı en a en juego las elaciones que puede deduci en e los con ex os y la ecompensas. Las ecomendaciones se ´an de calidad en unci´on de la capacidad de la ed neu onal pa a cap u a la elaci´on en e es as a iables. Po o o lado, dado un con ex o, la ed neu onal end ´a la p obabilidad de 1 de elegi un b azo si es el b azo que m´as p obabilidades iene. De es e modo, el es o de b azos ienen una p obabilidad de 0 de se elegidos. Adem´as de es as unciones, la ed neu onal ambi´en debe se capaz de da la p obabilidad de elegi un b azo dado un con ex o. Es o es necesa io po que el algo i mo Exp4 necesi a es a p obabilidad pa a ajus a el peso de sus pol´ı icas po lo que se ha enido que implemen a es e m´e odo. La ed neu onal de ol e ´a 1 si el b a- zo iene la mayo p obabilidad de se el mejo y se elegi ´a con ce eza, mien as que de ol e ´a 0 en caso con a io. Po ´ul imo, se ha podido elegi en e dos es a egias pa a la ed neu onal cuando selecciona un b azo a ecomenda : elegi el b azo alea o iamen e de acue do a la dis ibuci´on de p obabilidades o selecciona el b azo con mayo p obabilidad. Pa a escoge la mejo opci´on y op imiza la ed neu onal, se ha ealizado la simula- ci´on de una p ueba pa a el algo i mo Exp4 con ambas es a egias y se selecciona ´a la que mejo esul ados de. La esul an e se ´a u ilizada como la pol´ı ica de ed neu onal y compe i ´a con a la pol´ı ica del mejo b azo, la pol´ı ica ´ Epsilon-A a icioso que explo a y la e ce a pol´ı ica del il o colabo a i o basado en algo i mos de ecindad. 85 Figu a 36: Compa aci´on de edes neu onales. Es a simulaci´on se ha ealizado pa a solo un 30 % de los usua ios pe o los esul ados son e elado es. La ed neu onal 1 es la que elige el b azo alea o iamen e de acue do a una dis ibuci´on donde cada b azo iene una p obabilidad de se elegido seg´un lo bueno que sea y la ed neu onal 2 elige simplemen e el b azo que mayo p obabilidad enga sin a˜nadi alea o iedad. Se obse a en la igu a 36 que la ed neu onal 1 es p emiada po el Exp4 y ob iene mejo es pesos ya que sus ecompensas son mejo es. Al con a io, la ed neu onal 2 consigue peo es esul ados y su peso a disminuyendo en con as e con la o a ed neu onal. Debido a es e an´alisis, en la simulaci´on inal, se u iliza ´a una ed neu onal que elija el b azo con mayo p obabilidad sin ene en cuen a la alea o iedad. Hay que eco da que es o no es un p oblema po que las ecompensas son IID y signi ica que no hay un ad e sa io. Es o co esponde con la secci´on 5. 9.5. Resul ados En es e ´ul imo apa ado se analizan los esul ados po medio de g ´a icas y se o ecen las conclusiones opo unas espec o a cada igu a. An es de comen a los esul ados inales, se expone una simulaci´on inicial que es escla ecedo a pa a desa olla algunas hip´o esis en es e sis ema ecomendado . Los esul ados es udiados co esponden a la ase de e aluaci´on del Exp4 en cualquie caso. 9.5.1. Resul ados Iniciales Al ealiza es e sis ema de ecomendaci´on se ha llegado a muchas conclusiones pe o an es, hay unos esul ado p elimina es que deben se comen ados ya que se llega a una conclusi´on en iquecedo a pa a el plan- eamien o en gene al. En p ime luga , hay que se˜nala que las mejo es pol´ı icas han sido siemp e dos: la ed neu onal y la pol´ı ica de explo aci´on, de elegi el mejo b azo. La pol´ı ica de explo aci´on (´ Epsilon A a icioso con un ´epsilon de 0.95) no ha ob enido buenos esul ados, como se pod´ıa espe a no es buena idea elegi casi siemp e alea o iamen e una pel´ıcula. Sin emba go, lo que s´ı es so p enden e es el mal endimien o de la pol´ı ica de il o colabo a i o. Se pod´ıan ene muchas expec a i as pues as en es e expe o y no ha enido ninguna ele ancia en las simulaciones, alcanzando siemp e pesos ´ın imos y siendo desca ada comple amen e po el Exp4. Po o o lado, ambi´en hay que des aca el buen endimien o de la pol´ı ica de elegi siemp e el mejo b azo. Es algo que llama la a enci´on ya que es a pol´ı ica no ha enido en cuen a el con ex o, sino que simplemen e elige la ca ego ´ıa que mejo no a media haya enido du an e la ase de en enamien o. Es e aspec o es e elado ya que ha llegado a supe a a una mala ed neu onal. A con inuaci´on, se mues a el g ´a ico de una ed neu onal, con unos hipe pa ´ame os no ap opiados, y consiguien emen e, una mala ed neu onal en e a la pol´ı ica del mejo b azo. En es e caso la pol´ı ica de mejo b azo gene almen e es la mejo es a egia pa a el algo i mo Exp4. 86 Es o expone unos esul ados so p enden es. Incluso al inal de la simulaci´on, la pol´ı ica del mejo b azo acaba ganando la pa ida comple amen e a la ed neu onal. La g ´a ica en cues i´on es la siguien e: Figu a 37: P ime a e aluaci´on Exp4. Tal y como se ha comen ado, los esul ados no son los espe ados: el il o colabo a i o es una o al decepci´on y elegi siemp e el mejo b azo pa ece que puede llega a se una al e na i a a ene en cuen a ya que acaba siendo el expe o a o i o po el Exp4. No obs an e, as ob ene es os esul ados, es deducible que se pueden mejo a los hipe pa ´ame os de la ed neu onal y e si ealmen e puede supe a a odas las pol´ı icas con unos pa ´ame os adecuados o po lo menos man ene se como una buena opci´on a la go plazo. Cabe se˜nala que en es a simulaci´on la ed neu onal en´ıa 64 neu onas, 60 neu onas y Kneu onas (18), una asa de ap endizaje de 0,001 y unos ´epocas de 10, po lo que se ha in en ando mejo a es os aspec os con el obje i o de consegui la mejo ed neu onal posible pa a e si es una pol´ı ica iable. Tambi´en es se˜nalable que solamen e la ed neu onal es en enada con una sola onda de en enamien o, con una ecomendaci´on pa a cada usua io de en enamien o, po lo que no con aba con an a in o maci´on. Po lo an o, se puede conclui en es os p ime os esul ados que aunque pudie a pa ece un buen expe o, la pol´ı ica de il o colabo a i o es supe ada de mane a supe la i a po la pol´ı ica del mejo b azo, as´ı como ambi´en pasa con la pol´ı ica del ´ Epsilon-A a icioso con un ´epsilon de 0,95 (una pol´ı ica que explo a). Es as dos pol´ı icas ya han quedado en e idencia y se ha demos ado po el Exp4 que no son pol´ı icas dominan es en es e sis ema. Adem´as, pa a una ed neu onal que pod ´ıa denomina se compleja, no se han conseguido buenos esul ados en e a la pol´ı ica del mejo b azo, con egula izaci´on, muchas neu onas, op imizaci´on con Adam y 10 ´epocas. Es necesa io modi ica algunos de los aspec os de la ed y debe se en enada m´as, con m´as ´epocas. Consecuen emen e, se ha a ado de mejo a la ed neu onal pa a que ob enga mejo es esul ados y comp oba si es capaz de endi mejo y man ene se como un al e na i a iable. 9.5.2. Resul ados Finales T as habe ob enido unos esul ados p elimina es en el apa ado an e io 9.5.1, se p ocede ´a a de alla los aspec os enidos en cuen a pa a mejo a la ed neu onal con el obje i o de e si una ed m´as op imizada pa a es e caso ob end ´ıa mejo es esul ados. Po o o lado, se pa e de la base de que las o as dos pol´ı icas an a se i ele an es y el an´alisis debe basa se en la pol´ı ica de elegi siemp e el mejo b azo y la ed neu onal. Se p ueba con unos hipe pa ´ame os que ue on lo su icien emen e buenos pa a que la ed neu onal supe ase a la pol´ı ica de mejo b azo. Es a ed en´ıa unas 200 ´epocas, 120 neu onas en la p ime a capa, 60 en la siguien e, la asa de ap endizaje ya se man u o 0,05. La ´ul ima capa siemp e debe se de 18 neu onas. Al ob ene an buenos esul ados, se aumen a a´un m´as la complejidad de la ed, sin emba go se ob u o sob eajus e po que la ed neu onal ya no supe aba a la pol´ı ica del mejo b azo. Po lo an o, ha debido gene aliza mal. La conclusi´on a la que se llega es que se hab´ıa p oducido un sob eajus e y hab´ıa que encon a un pun o medio pa a que la ed neu onal no sob eajus a ´a y se consigan las mejo es ecompensas. 87 Los pa ´ame os que inalmen e han sido man enidos de la ed neu onal son los siguien es: Se ha u ilizado una asa de ap endizaje de 0,05, una asa de egula izaci´on de 0,015, unos ´epocas de 170, unas neu onas de 120 en la p ime a capa, 70 en la segunda y 4 ondas de en enamien o. Los esul ados ob enidos pa a Exp4 con es a ed neu onal mejo ada y el es o de pol´ı icas igual que an es son los siguien es: Figu a 38: E aluaci´on Exp4. Con es a igu a 38, se ap ecia que al op imiza la ed se con ie e en una pol´ı ica dominan e pa a el Exp4 y que puede ayuda a mejo a la ecompensa media. Po el con a io, se sigue obse ando que las pol´ı icas de un ´ Epsilon-A a icioso que explo a o un il o colabo a i o siguen sin se buenos expe os. Po o o lado, elegi el mejo b azo sigue siendo una al e na i a que puede se en ajosa pa a el algo i mo al y como e leja la igu a. Du an e es cua as pa es de la simulaci´on la ed neu onal es la pol´ı ica m´as ace ada. En las ondas inales se p oduce una al e nancia en e la pol´ı ica de elegi el mejo b azo y la ed neu onal. Debido a es o, se puede deduci que ambos expe os o ecen ecomendaciones buenas pa a el algo i mo Exp4 y iene en cuen a a los dos. Pos e io men e se o ece la ecompensa media de la simulaci´on a lo la go de las ondas, pe o su alo inal es de 0.7536 po lo que se puede es a sa is echos con el desempe˜no del Exp4. Respec o a la pol´ı ica de il o colabo a i o que u iliza el algo i mo de ecindad, se puede llega a la siguien e conclusi´on: los esul ados son cla amen e nega i os, es o indica que dicha pol´ı ica no cap u a adecuadamen e las elaciones en e el con ex o y los b azos pa a maximiza la ecompensa. Po ello, se puede deduci que en es e caso pa icula no es buena idea ecomenda de acue do con las p e e encias del g upo de iguales. A pesa de que el g upo de iguales iene un con ex o simila al usua io obje i o, si el sis ema ecomendado iene en cuen a las p e e encias de dicho conjun o, los esul ados son malos. Sin emba go, es o no sugie e que el con ex o no apo e in o maci´on aliosa. Aunque el algo i mo de il ado colabo a i o no haga ecomendaciones de calidad, la ed neu onal s´ı que ob iene buenas ecompensas y iene en conside aci´on el con ex o. Sin emba go, la pol´ı ica de la ed neu onal c ea elaciones dis in as en e el con ex o y los b azos seleccionados. Po lo an o, con un en oque di e en e como el que u iliza la ed neu onal si que se puede ap o echa la in o maci´on con ex ual pa a mejo a las ecompensas. En de ini i a, la es a egia ´op ima en el sis ema ecomendado es combina la pol´ı ica de la ed neu onal y la del mejo b azo. El Exp4 ap o echa ´a ambas es a egias du an e la simulaci´on. Pa a ello, egula ´a los pesos de es as dos pol´ı icas cas igando a la que o ezca malas ecompensas y dando opo unidades a la o a. Ha ´a es o de o ma inde inida con o me a anzan las ondas. In e cala dichos expe os se supone que es la mejo al e na i a. Po lo an o, pa a algunos usua ios el sis ema ecomendado suge i ´a el mejo b azo, una opci´on bas an e segu a, mien as que pa a o os usua ios ecomenda ´a un g´ene o seg´un la ecomendaci´on de la ed neu onal. Es a pol´ı ica iene en cuen a el con ex o y pe sonaliza ´a la ecomendaci´on adap ´andose a los da os con ex uales del usua io pa a o ece una ecomendaci´on ´unica. Consecuen emen e, el sis ema ecomendado encuen a un equilib io en e suge i siemp e el mejo g´ene o y hace ecomendaciones pe sonalizadas en base al con ex o. Es o consis e en la coo dinaci´on del expe o del mejo b azo y la ed neu onal. La mayo ´ıa de eces el sis ema ecomenda aconseja ´a el b azo elegido po la ed neu onal, que escoge dicho b azo adap ´andolo al 88 Pa a ello, se ha enido que es udia , en cie a medida, desde las edes neu onales que son una ins ancia del ap endizaje au om´a ico, has a algo i mos de ecomendaci´on como el il o colabo a i o especializado en sis e- mas ecomendado es. Tambi´en se ha abajado con o os bandidos es oc´as icos como el ´ Epsilon-A a icioso. Es e abajo ha sido muy es imulan e, aunque necesi ado de mucho abajo al habe a ado demasiado con enido. Como esul ado, el sis ema ecomendado c eado ep esen a la pues a en p ´ac ica de m´ul iples conocimien os y mucho abajo en dis in os campos, equi iendo el es udio de m´ul iples algo i mos. Un pun o que ha p esen ado mucha di icul ad ha sido modela una ed neu onal como bandido mul i-b azo con ex ual. Pa a es o, se ha enido que es udia a ondo el p oblema y adap a es a soluci´on, que ha esul ado en algo muy in e esan e. Cabe des aca que la ed neu onal ha eque ido de un g an es ue zo pa a op imiza sus pa ´ame os. Po ´ul imo, ambi´en ha sido necesa io ap ende a adap a la in o maci´on de una base de da os pa a que sea a able po el modelo. Los esul ados han sido analizados po medio de la es ad´ıs ica. Es udia los esul ados es ad´ıs icamen e ha sido un aspec o c ucial, no solo pa a en ende un sis ema ecomendado , sino ambi´en pa a que los esul ados ob enidos en es e sis ema puedan se conside ados po implemen aciones enide as. En de ini i a, ambos au o es han ealizado un es ue zo conjun o du an e el desa ollo de odo el abajo. Los dos han ocado odos los pun os in oluc ados en es e p oyec o. Se ha conseguido saca pa ido del buen equipo o mado, gene ando as´ı una g an opo unidad pa a p o undiza en es e complejo aspec o del ap endizaje au om´a ico. F u o de es a conexi´on ha su gido un equipo din´amico en el que los oles han ido a iando con el iempo g acias a la e sa ilidad de sus in eg an es. Adem´as, sendos au o es han abajado en odas las ases de desa ollo de las aplicaciones p ´ac icas. Es o ha pe mi ido exp imi al m´aximo sus i udes y ap o echa la sine gia c eada pa a cons ui un p oyec o muy s´olido, que apo a mucho alo debido a su complejidad y que conlle a mucho es ue zo po de ´as. Debido a es o, se puede a i ma que ha salido a eluci un g an abajo de mane a exi osa, o eciendo muchas implemen aciones y es udios de suma ele ancia en el campo de los bandidos mul i-b azo y, consecuen emen e, apo ando conocimien os al ap endizaje po e ue zo. 95 11. Conclusiones Es e abajo cumple con c eces las expec a i as iniciales y los obje i os plan eados. Po un lado, se aba- jan adecuadamen e los concep os e´o icos undamen ales de los bandidos y sus algo i mos, y se hace ´en asis en los es oc´as icos y an agonis as pa a aba ca co ec amen e el ma co de los bandidos con ex uales. Po o o lado, los bandidos con ex uales han sido es udiados en p o undidad incluyendo el ex enso y exhaus i o desa ollo de m´ul iples aplicaciones p ´ac icas. Es a pues a en p ´ac ica de los bandidos con ex uales cub e di e en es ´ambi os y puede se un pun o de pa ida pa a el despliegue de aplicaciones eales en la sociedad ac ual. Adem´as de habe desa ollado algo i mos en dis in os campos, ambi´en se expone su me odolog´ıa al de alle pa a hace los comp ensibles. Con es o en conside aci´on, los esul ados ob enidos son m´as que sa is ac o ios. Han salido a eluci las en- ajas de los bandidos mul i-b azo con ex uales ya que son cie amen e ´u iles en di e sas aplicaciones p ´ac icas. En es e abajo hay di e en es implemen aciones que cub en el ´ambi o inancie o y de las in e siones y am- bi´en aspec os undamen ales del mundo digi al como los sis emas ecomendado es. Es os emas ienen un cla o impac o en la sociedad mode na. Adem´as, se ha es udiado una a ian e en la que los algo i mos abajan en un juego con ex ual dando luga a o o posible uso de es os bandidos. Debido a su e sa ilidad en una amplia gama de campos y su escalabilidad pa a desa olla cons ucciones de so wa e, que no son i iales y pe mi en explo a p oblemas muy complejos, los bandidos con ex uales son una ama emendamen e signi ica i a del ap endizaje po e ue zo. Pe mi en ob ene soluciones p agm´a icas a p oblemas del mundo eal encon ando un co ec o equilib io en e la explo aci´on y explo aci´on pa a ob ene buenos endimien os que e lejan la e icacia de es os algo i mos. Es o ha quedado demos ado de mane a no o ia a a ´es de las implemen aciones o ecidas en es e abajo. 12. Conclusions This wo k mo e han ul ills he ini ial expec a ions and he s a ed objec i es. On he one hand, he undamen al heo e ical concep s o bandi s and hei algo i hms a e adequa ely wo ked ou , and emphasis is placed on s ochas ics and ad e sa ial bandi s o p ope ly co e he amewo k o con ex ual bandi s. On he o he hand, con ex ual bandi s ha e been s udied in dep h including he ex ensi e and exhaus i e de elopmen o mul iple p ac ical applica ions. These implemen a ions o con ex ual bandi s co e di e en domains and can be a s a ing poin o he deploymen o eal applica ions in oday’s socie y. In addi ion o ha ing de eloped al- go i hms in di e en ields, hei me hodology is also exposed in de ail o make hese algo i hms unde s andable. Wi h his in conside a ion, he esul s ob ained a e mo e han sa is ac o y. The ad an ages o con ex ual mul i-a med bandi s ha e come o ligh as hey a e ce ainly use ul in a ious p ac ical applica ions. In his wo k, di e en implemen a ions a e co e ing he inancial and in es men domain and also undamen al aspec s o he digi al wo ld such as ecommende sys ems. These opics ha e a clea impac on mode n socie y. In addi ion, a a ian has been s udied in which he algo i hms wo k in a con ex ual game gi ing ise o ano he possible use o hese bandi s. Because o hei e sa ili y in a wide ange o domains and hei scalabili y o de eloping so wa e cons uc s, which a e non- i ial and allow he explo a ion o e y complex p oblems, con- ex ual bandi s a e a emendously signi ican b anch o ein o cemen lea ning. They enable he disco e y o p agma ic solu ions o eal-wo ld p oblems by inding he igh balance be ween explo a ion and exploi a ion o ob ain good pe o mances ha e lec he e ec i eness o hese algo i hms. This has been no o iously de- mons a ed h ough he implemen a ions o e ed in his wo k. 96 13. Anexo 13.1. Depu aci´on de la E oluci´on de Pesos de los Bo s con P obabilidades Indi- iduales de Elecci´on de B azo de 100 % y 0 % La depu aci´on “case a” comen ada en la secci´on 8.3.1 se p esen a a con inuaci´on. Adem´as, la igu a 45 uel e a expone la e oluci´on de los expe os, ambi´en e lejada en dicha secci´on. Ronda: 292 C´alculo de a iables B azo elegido po el algo i mo: P.LARGA Recompensa ob enida po el algo i mo = 0.1 Cos e pa a los bo s que han ecomendado el b azo P.LARGA = 1 - 0.1 = 0.9 P obabilidad Indi idual de cada bo de elegi el b azo que elija = 100 % P obabilidad Conjun a en e los bo s de elegi P.LARGA = = 100 % * 1.42e-008 + 100 % * 4.86e-259 = 1.421292709769473e-08 Ob enci´on de cos es es imados P ob[Elegi Bo PCo as] = 2.76e-252 |Elige b azo: MANTENER |Cos e es imado: 0.0 P ob[Elegi Bo PLa gas] = 1.42129271e-008 |Elige b azo: P.LARGA |Cos e es imado: 63322635.36 P ob[Elegi Bo PCambian es] = 4.86e-259 |Elige b azo: P.LARGA |Cos e es imado: 63322635.36 P ob[Elegi Bo C uce de MM] = 8.10e-002 |Elige b azo: MANTENER |Cos e es imado: 0.0 P ob[Elegi Bo RSI] = 9.96e-004 |Elige b azo: MANTENER |Cos e es imado: 0.0 P ob[Elegi Bo MACD y BB] = 2.71e-005 |Elige b azo: MANTENER |Cos e es imado: 0.0 P ob[Elegi Bo Todo] = 9.18e-001 |Elige b azo: MANTENER |Cos e es imado: 0.0 Ac ualizaci´on de pesos y de la dis ibuci´on de p obabilidad Nue os Pesos de los bo s: [1.e+250, 1.e-001, 1.e-001, 1.e+250, 1.e+250, 1.e+250, 1.e+250] Nue as P obabilidades, espec i amen e: [2.e-001 2.e-252 2.e-252 2.e-001 2.e-001 2.e-001 2.e-001] Figu a 45: E oluci´on de los Pesos de los Expe os con γ= 0,2. Como se puede obse a en la depu aci´on, en la onda 292, el algo i mo ha allado al elegi el mismo b azo 97 que han ecomendado dos de los es bo s con meno es p obabilidades de se escogidos. Es o ha p o ocado que la p obabilidad conjun a de elegi dicho b azo sea baj´ısima. Po consiguien e, el cos e es imado pa a los bo s que han suge ido la opci´on de comp a ha esul ado se ele ad´ısimo. Lo no mal es ob ene cos es es imados en e los alo es 0 y 5, y en es e caso el alo es 63322635.36. La ob enci´on de an ele ados cos es es imados po pa e de los bo s de come cio expe os en posiciones la gas y posiciones cambian es ha p o ocado que su p obabilidad de se elegidos en la siguien e onda sea e- ducida a p ´ac icamen e 0. Tambi´en, ha conlle ado la dis o si´on de las p obabilidades de elegi el es o de bo s, epa iendo en e es os la p obabilidad o al es an e de o ma iguali a ia. Conc e amen e, como son sie e bo s en o al, y dos de ellos han ecibido una p obabilidad de casi 0, a los cinco es an es se les ha o o gado una p obabilidad ce cana al 20 %. En la igu a 45, se puede con i ma es a si uaci´on al con empla que los pesos de es os cinco bo s, as la onda 292, pa en desde el mismo pun o (0.2 en el eje de las o denadas). En cambio, los pesos de los bo s pe judicados adquie en el alo m´as bajo, sin pode emon a la si uaci´on en lo que es a de ondas. 13.2. Resul ados Sis ema Recomendado Pel´ıculas P ime o se o ecen o as dos simulaciones del Exp4 con las mejo as hechas en la ed neu onal pa a que se puedan obse a o as ejecuciones como e e encia. La ed neu onal y elegi el mejo b azo son siemp e las mejo es pol´ı icas y al mos a o as p uebas se con i ma es a eo ´ıa. Figu a 46: Simulaci´on auxilia 1. En es a igu a 46 se hab´ıa in en ando usa m´as neu onas: 120 en la p ime a capa (igual que an es) y 73 en la segunda. Hay una asa de egula izaci´on de 0.015 en ambas capas y son aumen adas las ´epocas has a 200. 98 Figu a 47: Simulaci´on auxilia 2. Es a segunda simulaci´on auxilia se ealiz´o con los pa ´ame os inales de la ed neu onal, y puede se i pa a e c´omo di ie en los esul ados seg´un lo que se equi oquen los expe os: la ed neu onal y la pol´ı ica del mejo b azo. En odas las simulaciones se puede ap ecia que la ed neu onal iene un buen compo amien o y es una pol´ı ica a ene en cuen a siemp e. Adem´as, as habe o ecido o as simulaciones, se mues an algunos de los esul ados ob enidos en el sis ema ecomendado de pel´ıculas que hace uso de un bandido con ex ual de clase pol´ı ica. Los mapas de calo pa a los g upos de edad al an es son p esen ados a con inuaci´on: Figu a 48: Mapa calo de ecompensas po b azo pa a pe sonas de menos de 18 a˜nos. 99 Figu a 49: Mapa calo de ecompensas po b azo pa a pe sonas de en e 18 y 24 a˜nos. Figu a 50: Mapa calo de ecompensas po b azo pa a pe sonas de en e 25 y 34 a˜nos. 100 Figu a 51: Mapa calo de ecompensas po b azo pa a pe sonas de en e 35 y 44 a˜nos. Figu a 52: Mapa calo de ecompensas po b azo pa a pe sonas de en e 50 y 55 a˜nos. 101 Figu a 53: Mapa calo de ecompensas po b azo pa a pe sonas de m´as de 56 a˜nos. Tambi´en se adjun an o as igu as auxilia es 54 y 55 que no se a˜nadie on en la secci´on 9: Figu a 54: Recompensas pa a la cada g upo de edad. 102 Figu a 55: G ´a ico de con o no de la edad y la ecompensa. 103 Re e encias [1] W. Thompson. Sob e la p obabilidad de que una p obabilidad desconocida supe e a o a en is a de la e idencia de dos mues as. Biome ika 1933. [2] Aleksand s Sli kins. In oduc ion o Mul i-A med Bandi s, 2019. [3] To La imo e and Csaba Szepes ´a i. Bandi s Algo i hms. Camb idge Uni e si y P ess, 2020. [4] S´ebas ien Bubeck and Nicol`o Cesa-Bianchi. Reg e Analysis o S ochas ic and Nons ochas ic Mul i-a med Bandi P oblems, 2012. [5] Djallel Boune ou , I ina Rishz. A Su ey on P ac ical Applica ions o Mul i-A med and Con ex ual Bandi s, 2019. [6] Pe e Aue , Nicol`o Cesa-Bianchi, Yoa F eund, and Robe E. Schapi e. The non-s ochas ic mul i-a med bandi p oblem, 2012. [7] Rein o cemen Lea ning by Richa d S. Su on and And ew G. Ba o. The MIT P ess. Camb idge, 2018. [8] Ye geny Seldin, Csaba Szepes ´a i, Pe e Aue , Yasin Abbasi-Yadko i. E alua ion and Analysis o he Pe - o mance o he EXP3 Algo i hm in S ochas ic En i onmen s, 2012. [9] Yoa F eund and Robe E. Schapi e. A decision- heo e ic gene aliza ion o on-line lea ning and an appli- ca ion o boos ing. Jou nal o Compu e and Sys em Sciences, 55(1):119–139, Augus 1997. [10] Wal e Rudin. Real and complex analysis, 1987. [11] Cha u C. Agga wal, Recommende sys ems. Sp inge , 2016. [12] Pie Guisseppe Sessa, Ilija Boguno ic, Ma yam Kamga pou , And eas K ause. Con ex ual Games: Mul i- Agen Lea ning wi h Side In o ma ion, 2020. [13] La y J. LeBlanc, Edwa d K. Mo lok, William P. Pie skalla. An e icien app oach o sol ing he oad ne wo k equilib ium a ic assignmen p oblem, 1975. [14] Pie Guissepe Sessa, Ilija Boguno ic, Ma yam Kamga pou , And eas K ause. No- eg e Lea ning in Unk- nown Games wi h Co ela ed Payo s, 2019. [15] J. Welles Wilde J . New Concep s in Technical T ading Sys ems, 1978. [16] Raul Canessa C. (h ps://www. ecnicasde ading.com/2010/06/macd-mo ing-a e age- con e gence-di e gence.h ml), Indicado MACD – Uso e in e p e aci´on del MACD. URL:h ps://www. ecnicasde ading.com/2010/06/macd-mo ing-a e age-con e gence-di e gence.h ml ( echa de acceso: 2023-04). [17] Mo ieLens (h ps://g ouplens.o g/da ase s/mo ielens/1m/), Base de da os de pel´ıculas Mo ieLens 1M. URL:h ps://g ouplens.o g/da ase s/mo ielens/1m/ ( echa de acceso: 2023-03) [18] Pie Guissepe Sessa (h ps://gi hub.com/sessap/con ex ualgames), Con ex ual Games: Mul i-Agen Lea ning wi h Side In o ma ion. URL:h ps://gi hub.com/sessap/con ex ualgames ( echa de acceso: 2023-02). [19] Yan Qui (h ps://gi hub.com/yan-qi/k-sho es -pa hs-cpp- e sion), K-Sho es Pa h Algo i hm. URL:h ps://gi hub.com/yan-qi/k-sho es -pa hs-cpp- e sion ( echa de acceso: 2023-03). [20] And ew Ng (h ps://www.cou se a.o g/specializa ions/machine-lea ning-in oduc ion), Machi- ne Lea ning p og am by DeepLea ning.AI and S an o d Uni e si y. URL:h ps://www.cou se a.o g/ specializa ions/machine-lea ning-in oduc ion. [21] John Bollinge (h ps://edi o ial.blob.co e.windows.ne /miscelaneous-inpu / 43nU6TU 1Bph 3 s4zs8DU7xSqDBbdNJ99K Xi1a/John%20Bollinge -637370664925974496.pd ), As´ı uso hoy en d´ıa en el me cado mis he amien as. URL:h ps://edi o ial.blob. co e.windows.ne /miscelaneous-inpu /43nU6TU 1Bph 3 s4zs8DU7xSqDBbdNJ99K Xi1a/John% 20Bollinge -637370664925974496.pd ( echa de acceso: 2023-04). [22] Seabo n. (h ps://seabo n.pyda a.o g/gene a ed/seabo n. iolinplo .h ml). seabo n. iolinplo . URL: h ps://seabo n.pyda a.o g/gene a ed/seabo n. iolinplo .h ml ( echa de acceso: 2023-03). 104