Bandidos Contextuales: Fundamentos y Aplicaciones

Bandidos Contextuales: Fundamentos y Aplicaciones Contextual Bandits: Foundations and Applications Iv´an Hern´andez Rold´an y Alejandro Magarzo Gonzalo Dirigido por Miguel Palomino Tarjuelo Doble Grado: Ingenier´ıa Inform´atica y Administraci´on y Direcci´on de Empresas Trabajo de Fin de Grado en Ingenier´ıa Inform´atica Facultad de Inform´atica, Universidad Complutense de Madrid Curso acad´emico 2022/2023 Resumen Como punto de partida, se abordan los fundamentos te´oricos subyacentes a los bandidos multi-brazo, preparando as´ı el terreno para la profundizaci´on en los bandidos contextuales. Los bandidos, como elemento fundamental en el aprendizaje por refuerzo, ofrecen una respuesta eficiente a los problemas b´asicos del dilema de la exploraci´on frente a la explotaci´on. Un problema de bandidos implica un juego secuencial entre un agente y un entorno, donde en cada ronda el agente tiene varias acciones a su disposici´on y debe elegir una para recibir la recompensa correspondiente como resultado. Basado en las recompensas anteriores, el agente deber´a mejorar su toma de decisiones para obtener la m´axima recompensa acumulada al final del juego, manteniendo un balance entre explorar acciones menos probadas y explotar la mejor acci´on seg´un la informaci´on que posee. Adem´as, se explican los bandidos estoc´asticos y antagonistas como preludio para presentar varios algoritmos que ser´an de gran utilidad en una variante particular del modelo de bandidos: los bandidos contextuales. En este tipo de bandido, cada acci´on disponible est´a asociada a una distribuci´on de probabilidad de recompensas, desconocida de antemano por el agente, de la cual se obtiene la recompensa correspondiente tras elegir una acci´on. Por lo tanto, el agente tratar´a de maximizar sus recompensas eligiendo los brazos que mayor recompensa media tengan en funci´on del contexto. A lo largo de este trabajo se presentan los algoritmos que resuelven los problemas de los bandidos planteados y se comparan sus rendimientos a trav´es de la m´etrica del remordimiento. Tambi´en, se tratan las diferencias entre los remordimientos de los algoritmos que se adaptan al contexto y los que no gracias a la exposici´on de un juego contextual. Tras abordar cada concepto te´orico del ´ambito de los bandidos contextuales, se expone una aplicaci´on pr´actica en consonancia para estudiar el desempe˜no de los bandidos contextuales en diversos dominios. Las principales aportaciones pr´acticas de este trabajo se localizan dentro del sector financiero, concretamente en el departamento de la automatizaci´on de la inversi´on en el mercado de valores a trav´es de los bots de comercio, y en el mundo digital, realizando un sistema recomendador de pel´ıculas. Palabras clave Bandidos multi-brazo. Exploraci´on-explotaci´on. Remordimiento. Bandidos estoc´asticos. Bandidos antagonistas. Bandidos contextuales. Clase pol´ıtica. Exp4. Bots de comercio. Sistema recomendador. 1 Abstract As a starting point, the theoretical foundations underlying multi-armed bandits are addressed, thereby laying the groundwork for a deep dive into contextual bandits. Bandits, as a fundamental element in reinforcement learning, provide an efficient response to the basic problems of the exploration-exploitation dilemma. A bandit problem involves a sequential game between an agent and an environment, where in each round the agent has several actions at his disposal and must choose one to receive the corresponding reward as a result. Based on past rewards, the agent should improve his decision-making to obtain the greatest accumulated reward at the end of the game, maintaining a balance between exploring lesser-tested actions and exploiting the best action according to the information he possesses. In addition, stochastic and adversarial bandits are explained as a prelude to presenting various algorithms that will be extremely useful in a particular variant of the bandit model: the contextual bandits. In this type of bandit, each available action is associated with a probability distribution of rewards, unknown to the agent beforehand, from which the corresponding reward is obtained after choosing an action. Therefore, the agent will try to maximize his rewards by choosing the arms with the highest average reward based on the context. Throughout this work, algorithms that solve the problems posed by bandits are presented and their performances are compared through the metric of regret. Also, the differences between the regrets of algorithms that adapt to the context and those that do not are discussed, thanks to the exposition of a contextual game. After addressing each theoretical concept in the field of contextual bandits, a practical application is presented to study the performance of contextual bandits in various domains. The main practical contributions of this work are located within the financial sector, specifically in the department of automating investment in the stock market through trading bots, and in the digital world, by implementing a movie recommendation system. Keywords Multi-armed bandits. Exploration-exploitation. Regret. Stochastic bandits. Adversarial bandits. Contextual bandits. Policy class. Exp4. Trading bots. Recommendation system. 2 ´ Indice 1. Introducci´on 6 2. Introduction 9 3. Problema de los Bandidos Multi-brazo 12 3.1. Caracter´ısticas y Diferenciaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2. TiposdeBandidos ............................................ 13 3.3. Aplicaciones de los Bandidos Contextuales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4. Bandidos Estoc´asticos 15 4.1. AlgoritmosSimples............................................ 16 4.1.1. Algoritmo Exploraci´on-Primero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.2. Algoritmo ´ Epsilon-Avaricioso.................................. 17 4.2. Algoritmos Avanzados: Exploraci´on Adaptativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.1. Algoritmo Eliminaci´on Sucesiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.2. AlgoritmoUCB1......................................... 19 5. Bandidos Antagonistas 21 5.1. PrimerIntentodeSoluci´on ....................................... 23 5.2. AlgoritmosEfectivos........................................... 24 5.2.1. AlgoritmoHedge......................................... 24 5.2.2. AlgoritmoExp3 ......................................... 25 5.2.3. AlgoritmoExp4 ......................................... 27 6. Bandidos Contextuales 29 6.1. Bandidos Contextuales con Pocos Contextos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6.1.1. Recomendador de Pel´ıculas para Cuatro Grupos . . . . . . . . . . . . . . . . . . . . . . . 31 6.2. Bandidos Contextuales Lipschitzianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2.1. Motivaci´on ............................................ 35 6.2.2. Implementaci´on de Bandidos Contextuales Lipschitzianos del Mercado . . . . . . . . . . . 36 6.2.3. Demostraci´on de Lispchitz para Bandidos Contextuales Lipschitzianos . . . . . . . . . . . 40 6.3. Bandidos Contextuales con Clase Pol´ıtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.3.1. Algoritmo Exp4 con Pol´ıticas en lugar de Expertos . . . . . . . . . . . . . . . . . . . . . . 42 7. Bandidos Contextuales en Juegos Contextuales 44 7.1. Introducci´ondelSistema......................................... 44 7.2. JuegoContextual............................................. 45 7.3. LaRed................................................... 45 7.4. Algoritmos ................................................ 46 7.4.1. AlgoritmoHedge......................................... 46 7.4.2. AlgoritmoGPMW ........................................ 49 7.4.3. AlgoritmocGPMW ....................................... 51 7.5. Conclusiones ............................................... 54 8. Bots de Comercio 59 8.1. Planteamiento............................................... 59 8.2. Expertos.................................................. 61 8.2.1. Experto en Posiciones Cortas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 8.2.2. Experto en Posiciones Largas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 8.2.3. Experto en Posiciones Cambiantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.2.4. Experto en Cruce de Medias M´oviles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.2.5. ExpertoenRSI.......................................... 63 8.2.6. Experto en MACD y Bandas de Bollinger . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 8.2.7. ExpertoenTodo......................................... 64 8.3. An´alisis de la Soluci´on Planteada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 8.3.1. Consideracionesprevias ..................................... 65 8.3.2. An´alisis del Horizonte Temporal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.3.3. An´alisis de la Tasa de Aprendizaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 8.3.4. An´alisis de la Tasa de Exploraci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 8.3.5. Puesta en Pr´actica de la Soluci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3 9. Sistema Recomendador de Pel´ıculas 75 9.1. BasedeDatos............................................... 75 9.2. Iniciaci´on ................................................. 76 9.3. Funcionamiento.............................................. 77 9.4. Pol´ıticas.................................................. 78 9.4.1. Pol´ıticasSimples......................................... 79 9.4.2. Filtro Colaborativo Basado en Vecindad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 9.4.3. Red Neuronal como Bandido Contextual . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9.5. Resultados................................................. 86 9.5.1. ResultadosIniciales ....................................... 86 9.5.2. ResultadosFinales........................................ 87 9.5.3. An´alisisDetallado ........................................ 90 10.Aportaciones individuales 94 11.Conclusiones 96 12.Conclusions 96 13.Anexo 97 13.1. Depuraci´on de la Evoluci´on de Pesos de los Bots con Probabilidades Individuales de Elecci´on de Brazode100%y0%........................................... 97 13.2. Resultados Sistema Recomendador Pel´ıculas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4 Notaci´on En este breve apartado se introducen algunos conceptos clave asociados a su s´ımbolo. Estos s´ımbolos ser´an utilizados en las secciones posteriores. KEl n´umero de brazos en el problema planteado. TEl horizonte temporal o n´umero de rondas del problema planteado. atBrazo elegido en la ronda t. rtRecompensa observada en la ronda ttras elegir el brazo at. DaDistribuci´on de probabilidad de las recompensas del brazo a. IID Recompensas Independientes e Id´enticamente Distribuidas. La recompensa para cada brazo es IID cuando, en cada ronda, se toma una muestra de forma independiente a partir de la distribuci´on Da. Es decir, es una distribuci´on de recompensas independiente de la ronda y por tanto est´atica, pero diferente seg´un el brazo. R(T) El remordimiento del algoritmo en la ronda T. El remordimiento calcula la diferencia entre el mejor rendimiento posible del algoritmo durante dichas rondas y el rendimiento real. E[R(T)] El remordimiento esperado del algoritmo en la ronda T. a∗El brazo ´optimo. µ(a) La recompensa media para un brazo a. O() Orden que refleja la eficiencia del algoritmo. nt(a) El n´umero de veces que se selecciona el brazo ahasta la ronda t. rt(a) El radio de confianza que representa la variabilidad de las recompensas obtenidas por el brazo aen una ronda t. UCB(a) Cota superior dado un brazo a. LCB(a) Cota inferior dado un brazo a. ct(a) La tabla de costes que refleja el coste para un brazo aen una ronda t. coste(a) El coste total de un brazo a, considerando todas las rondas que ha jugado. ˆµaPredicci´on de recompensa para un brazo a. PesoaImportancia de un brazo para el modelo. waPeso o importancia de un brazo para el modelo. ptDistribuci´on de probabilidades de elegir un brazo. ProbabilidadaPosibilidades de elegir un brazo. la(En juegos contextuales) P´erdidas, o remordimiento, de un brazo en una ronda t. La(En juegos contextuales) P´erdidas acumuladas de un brazo en una ronda t. ϵEpsilon que representar´a la tasa de aprendizaje en Hedge. γGamma que representar´a la tasa de aprendizaje (juegos con contexto). xtEl contexto dada una ronda t. UCBiUna instancia del algoritmo UCB, de los bandidos estoc´asticos. LLa constante Lipschitz que se utiliza en los bandidos contextuales lipschitzianos. γEn el algoritmo Exp4, esta variable refleja la tasa de exploraci´on. racum(a|x) La recompensa acumulada de un brazo dado un contexto x. πPol´ıtica, que se usa como experto, en el Exp4. Π Conjunto de pol´ıticas presentado al Exp4 en su versi´on de bandidos contextuales con clase pol´ıtica. ˆct(e) Costes falsos que se calculan en el algoritmo Exp4 para trabajar con el algoritmo Hedge. ptDistribuci´on de probabilidad de elegir una pol´ıtica π. Se emplea en los algoritmos Hedge y Exp4. 5 1. Introducci´on Origen de los Bandidos El problema de los bandidos multi-brazo fue inicialmente estudiado por Thompson en 1933 cuando public´o un art´ıculo que ahora ha pasado a la historia en la revista Biometrika [1]. En dicha revista, Thompson se interes´o por las pruebas m´edicas que se realizaban en esa ´epoca, porque se consum´ıan medicamentos sin conocer su efectividad. En estas pruebas, Thompson observ´o que los f´armacos no eran buenos inicialmente ni se ajustaban sobre la marcha. Lleg´o a la conclusi´on de que se realizaban pruebas m´edicas “a ciegas”, surgiendo la necesidad de adaptaci´on durante el ensayo para que el efecto del tratamiento fuera ´optimo. El nombre de los bandidos multi-brazo proviene de 1950s, cuando Frederick Mosteller y Robert Bush estudiaron el aprendizaje animal. Durante su estudio, realizaron pruebas a ratas en un laberinto con forma de T, es decir un camino recto que termina en una bifurcaci´on. De esta forma, situaban a los animales ante un problema de decisi´on: izquierda o derecha. Solo en uno de los dos ramales hab´ıa comida como recompensa, en el otro no hab´ıa nada. Ante este escenario, el roedor eleg´ıa un camino sin saber qu´e iba a encontrar. Con el objetivo de estudiar algo parecido con los humanos, se usaron unas m´aquinas tragaperras de dos brazos, tambi´en conocidas como “bandidos” de dos brazos porque robaban el dinero del jugador que las usaba. Para usar las m´aquinas tragaperras, en cada tirada o ronda el jugador elige un brazo, la palanca de la izquierda o la de la derecha. Se llama ronda a cada oportunidad que tiene el jugador para elegir un brazo. Al igual que con los roedores, el objetivo del jugador es conseguir la m´axima recompensa posible teniendo en cuenta que al principio no sabe qu´e brazo devuelve las mejores recompensas. Se entiende que tirar de una palanca de la m´aquina tragaperras ser´a elegir un brazo del bandido multi-brazo. Los bandidos multi-brazo representan el problema que se da en una situaci´on de aprendizaje similar a la de la m´aquina tragaperras: explorar una opci´on que puede parecer inferior a priori, seg´un la experiencia previa del jugador, o continuar explotando la mejor alternativa o brazo. Por ejemplo, un jugador puede estar ante la disyuntiva de elegir entre un brazo con el cual ha conseguido mucho dinero en las rondas anteriores, o probar un brazo nuevo que a´un no hab´ıa usado. Por ello, encontrar el correcto equilibrio entre la exploraci´on-explotaci´on es el coraz´on de los problemas de los bandidos multi-brazo y la tarea de los algoritmos que se estudia a lo largo de este trabajo. Estos algoritmos se encuadran dentro del aprendizaje autom´atico en el ´ambito del aprendizaje por refuerzo. El aprendizaje por refuerzo es un tipo de aprendizaje que tiene como objetivo maximizar las recompensas que consigue el algoritmo a trav´es de sus acciones. Al principio el algoritmo no sabe qu´e acciones tomar, debe descubrir con el paso de las rondas qu´e acciones le proporcionan m´as recompensas. La principal caracter´ıstica de los bandidos multi-brazo dentro del aprendizaje por refuerzo es que son un escenario modificado de aprendizaje por refuerzo cuyo aspecto diferencial es que el estado permanece constante. El estado es el entorno donde trabaja el algoritmo. Para entender las ventajas de este escenario “seguro”, primero se explica el escenario opuesto, es decir una situaci´on de aprendizaje por refuerzo completa donde las acciones del algoritmo modifiquen el estado del juego. Un ejemplo es el ajedrez. En este juego cada movimiento que hace un jugador (o algoritmo, en este caso) cambia el estado del tablero. Si el algoritmo decide mover un pe´on, esto cambia el estado del tablero y tambi´en las posibles acciones o brazos que tanto ´el como su oponente pueden tomar en el futuro. A su vez, estas decisiones tambi´en pueden influir en la estrategia del oponente, lo que a su vez cambia el entorno una vez m´as. Esta situaci´on presenta varios desaf´ıos: Complejidad: En el aprendizaje por refuerzo completo, el algoritmo necesita aprender una pol´ıtica completa que en funci´on del estado elija la acci´on ´optima, en lugar de solo aprender la recompensa esperada de cada acci´on. Esto puede hacer que el proceso de aprendizaje sea mucho m´as complejo y requiera m´as tiempo y recursos computacionales. Mayor riesgo: Dado que el estado del entorno puede cambiar con cada acci´on que se toma, existe un riesgo inherente de alterar el entorno de manera negativa durante el proceso de exploraci´on. Esto puede dificultar el an´alisis del dilema de exploraci´on-explotaci´on y puede llevar a resultados indeseables si no se maneja adecuadamente. 6 Ineficiencia: En los problemas de aprendizaje por refuerzo completo, la optimizaci´on puede ser menos directa y el aprendizaje m´as lento, ya que el algoritmo necesita aprender a estimar la recompensa de cada acci´on en cada posible estado. Esto puede requerir un n´umero mucho mayor de interacciones con el entorno, lo que puede ser costoso en t´erminos de tiempo y recursos. Por tanto, al considerar que el estado no cambia, los bandidos multi-brazo evitan la mayor parte de la complejidad del aprendizaje por refuerzo completo y trabajan c´omodamente uno de los conceptos m´as importantes del aprendizaje por refuerzo: el dilema exploraci´on-explotaci´on [7]. Los algoritmos de aprendizaje autom´atico se pueden clasificar en dos ´areas o tipos: aprendizaje offline y aprendizaje en l´ınea. En este caso, los bandidos multi-brazo se encuentran dentro de la segunda categor´ıa porque no se entrenan offline, sino que aprenden conforme van tomando decisiones. En definitiva, los bandidos multi-brazo se han convertido en un marco simple pero muy ´util para algoritmos que toman decisiones bajo incertidumbre a lo largo del tiempo. Objetivos y plan de trabajo El prop´osito primordial de este trabajo reside en la investigaci´on y comprensi´on del problema de los bandidos contextuales. Se hace hincapi´e en los detalles de los algoritmos que solucionan dicho problema tratando de explicar la l´ogica inherente a estos. Finalmente, este estudio propone la creaci´on de aplicaciones pr´acticas con el objetivo de ilustrar los beneficios que los bandidos contextuales pueden aportar en una amplia variedad de dominios de aplicaci´on. Por lo tanto, esta investigaci´on tiene un enfoque eminentemente pr´actico sustentado en principios te´oricos. La estructura empleada en la memoria es la siguiente: Las secciones 1 y 2 conforman la introducci´on. Explican la motivaci´on, los objetivos, el plan de desarrollo y los recursos utilizados. El contenido de la secci´on 1 est´a en espa˜nol y el de la secci´on 2 en ingl´es, pero ambos son iguales. La secci´on 3 constituye la introducci´on de los bandidos multi-brazo, as´ı como detalles a tener en cuenta. Las secciones 4 y 5 introducen dos tipos de bandidos esenciales para despu´es trabajar con los bandidos contextuales. La secci´on 6 desarrolla al completo la teor´ıa del tema fundamental del trabajo, los bandidos contextuales, y expone las dos primeras aplicaciones pr´acticas. La secci´on 7 estudia un caso concreto donde se compara el rendimiento de algoritmos contextuales y no contextuales en un juego contextual. La secci´on 8 expone un aplicativo de los bandidos contextuales con una clase pol´ıtica, explicados en 6, dentro del mercado financiero. La secci´on 9 presenta un sistema recomendador como una aplicaci´on de los bandidos contextuales con una clase pol´ıtica. Las secciones 11 y 12 forman la conclusi´on del trabajo. Ambas secciones tienen el mismo contenido, pero la secci´on 11 est´a en espa˜nol y la secci´on 12 est´a en ingl´es. Recursos y Documentaci´on Referencias bibliogr´aficas principales Este trabajo se ha basado fundamentalmente en el libro de Slivkins [2], donde se pueden encontrar las demostraciones de todos los resultados te´oricos que presentamos. Tambi´en se ha consultado cuando ha sido necesario los textos de Lattimore y Bubeck [3, 4]. 7 Repositorio de implementaciones Las implementaciones de software realizadas durante el desarrollo de este trabajo quedan reflejadas en los repositorios personales de los autores [26, 27]. Los lenguajes de programaci´on empleados son Python, principalmente, y C++. Python un lenguaje de programaci´on de alto nivel muy vers´atil y f´acil de usar. Debido a su menor complejidad de c´odigo y la presencia de bibliotecas avanzadas en computaci´on cient´ıfica y aprendizaje autom´atico, Python es especialmente relevante en el campo de la inteligencia artificial, incluyendo el aprendizaje por refuerzo. Se han utilizado bibliotecas imprescindibles en el aprendizaje autom´atico como numpy, pandas, scipy y tensorflow. Dichas bibliotecas permiten crear algoritmos y tratar adecuadamente los datos. Y tambi´en se han aprovechado otras bibliotecas para visualizar datos como matplotlib y seaborn. 8 4. Bandidos Estoc´asticos El objetivo de este apartado es definir uno de los principales tipos de bandidos, as´ı como detallar sus caracter´ısticas para entender su esencia. Los estoc´asticos son el modelo b´asico de los bandidos multi-brazo. A lo largo de esta secci´on, se tratar´an varios algoritmos disponibles para este tipo de bandidos y se comparar´an. Se considera un problema en el que un algoritmo tiene Kposibles brazos a elegir en cada una de las T rondas. Tras la elecci´on de un brazo, el algoritmo obtiene una recompensa correspondiente al brazo elegido. El protocolo a seguir es el siguiente, donde [T] = {1,2, . . . , T}: Problema Bandidos Estoc´asticos Habiendo Kbrazos y Trondas, En cada ronda t∈[T]: 1. El algoritmo elige un brazo at. 2. El algoritmo observa la recompensa rt∈[0,1] para el brazo elegido. El escenario estoc´astico se genera bajo las siguientes tres suposiciones: El algoritmo ´unicamente observa la recompensa de la acci´on seleccionada. Esto se conoce como retroalimentaci´on de bandido. Por tanto, el algoritmo no conoce las recompensas asociadas al resto de acciones que podr´ıa haber elegido. Las recompensas est´an acotadas al intervalo [0,1]. La recompensa para cada brazo es IID. Para cada brazo ahay una distribuci´on Dallamada distribuci´on de recompensas que es inicialmente desconocida por el algoritmo. La motivaci´on que hay detr´as de acotar las recompensas en un intervalo entre 0 y 1 es permitir el c´alculo del remordimiento en funci´on del n´umero de rondas Tdel problema. Esto ser´a demostrado m´as adelante en la explicaci´on del remordimiento del algoritmo Exploraci´on-Primero, que es el primero de todos los que se comentan en este trabajo, con el ´animo de que quede claro para el resto de veces que aparezca la variable T en la f´ormula de un remordimiento. Por este motivo, si las recompensas del problema vienen acotadas de la forma [m, n] tal que m<n, se recomienda realizar una traducci´on o reescala de las recompensas al intervalo [0,1]. Uno de los m´etodos m´as comunes para trasladar y reescalar recompensas al intervalo [0,1] es la transformaci´on lineal. La f´ormula correspondiente ser´ıa: r′=r−a b−a, donde res la recompensa original y r′es la recompensa transformada en el intervalo [0, 1]. No es necesario que las recompensas sigan una distribuci´on espec´ıfica o que cumplan alguna otra condici´on. Sin embargo, es muy importante tener en cuenta que la transformaci´on lineal asume que la relaci´on entre las recompensas se mantiene constante a lo largo del intervalo. Si este no fuera el caso, ser´ıa necesario una transformaci´on diferente que se ajuste mejor a las caracter´ısticas del problema. Por otro lado, se define el vector de recompensas medias como µ∈[0,1]K, donde µ(a) = E[Da] es la recompensa media del brazo a∈K. Se usa a∗:= arg m´axa∈Aµ(a) para definir el brazo ´optimo, es decir, el que devuelve la recompensa media m´as alta. Una forma aproximada de calcular el remordimiento es mediante la comparaci´on de la suma de las recompensas medias de los brazos ya elegidos, respecto al benchmark establecido por escoger en todas las Trondas el brazo ´optimo a∗. Formalmente, se define el remordimiento: R(T) = µ(a∗)T− T X t=1 µ(at) Cabe destacar que at, el brazo tomado en cada ronda t, es una variable aleatoria si su elecci´on depende de la aleatoriedad en las recompensas o la estrategia de selecci´on de brazo del algoritmo. En consecuencia, mientras las recompensas sean aleatorias o el brazo sea escogido de forma aleatoria, el remordimiento R(T) tambi´en 15 es una variable aleatoria. Por tanto, cuando las recompensas sean IID, tal y como sucede en el escenario estoc´astico, el remordimiento es una variable aleatoria y se habla en t´erminos de remordimiento esperado E[R(T)]. A continuaci´on, se detallan algunos de los algoritmos disponibles, empezando con los m´as simples para finalmente ofrecer soluciones m´as elaboradas y complejas. 4.1. Algoritmos Simples 4.1.1. Algoritmo Exploraci´on-Primero El primer algoritmo que se propone parte de la siguiente idea: explorar los brazos uniformemente durante Nrondas y elegir el mejor brazo el resto de las rondas. Este algoritmo se conoce como Exploraci´on-Primero. Algoritmo 4.1 Exploraci´on-Primero (N) 1: Fase de Exploraci´on: Se prueba cada brazo Nveces. 2: Se selecciona el brazo acon la mejor media de recompensas. 3: Fase de Explotaci´on: El brazo aes utilizado el resto de rondas. Teorema 4.1. El algoritmo Exploraci´on-Primero consigue un remordimiento esperado E[R(T)] ≤T2/3× O(Klog T)1/3cuando N=T K2 3·O(log T)1 3. Para diferentes valores de Nno se asegura dicho remordimiento. N´otese que el valor de Tes mayor que K, ya que es necesario explorar cada brazo al menos una vez. Despu´es de presentar cada algoritmo se incluye un teorema demostrado en [2] que enuncia el remordimiento conseguido por dicho algoritmo y permite evaluar su rendimiento. Concretamente, cuanto menor es su remordimiento mejor es su rendimiento. Las f´ormulas de los remordimientos de este trabajo establecen cotas superiores del “peor” rendimiento del algoritmo en cada problema y generalmente utilizan las variables Thorizonte temporal y Kbrazos. Con el objetivo de comprender la presencia de la variable Ten la f´ormula del remordimiento, se plantea un sencillo ejemplo que requiere que las recompensas est´en previamente acotadas en el intervalo [0, 1]. Existen dos cajas, una roja (caja A) y otra azul (caja B). Cada d´ıa, durante 10 d´ıas (T= 10), se puede elegir una de las dos cajas para abrirla y recibir una recompensa. La caja A siempre tiene una recompensa de 1, mientras que la caja B siempre tiene una recompensa de 0. Si se elige siempre la caja A durante los 10 d´ıas, se recibe una recompensa total de 10 (1 ∗10). Por otro lado, si se elige siempre la caja B, la recompensa total ser´a de 0 (0 ∗10). En el caso peor, eligiendo siempre la caja B, el l´ımite superior del remordimiento viene dado por la variable T(10 en este ejemplo), ya que la diferencia entre la m´axima recompensa (10) y la m´ınima recompensa (0) es igual a T. Es por ello que, formalmente, se define el remordimiento asociado al caso peor como R(T) = O(T). Es importante entender que, en el modelo de bandidos multi-brazo, los casos cercanos al caso peor se interpretan como situaciones en las que el algoritmo no es capaz de aprender a obtener recompensas mayores con el paso de las rondas. Sin embargo, los algoritmos que se plantean a lo largo de este trabajo s´ı consiguen aprender a tomar las mejores decisiones con m´as frecuencia. Debido a este hecho objetivo, se podr´a observar que los l´ımites superiores de los remordimientos que ofrecen son significativamente menores que el l´ımite superior en el caso peor (O(T)). En la figura 1 se explica el aprendizaje del algoritmo Exploraci´on-Primero de una forma gr´afica. La funci´on de color azul representa el remordimiento asociado al peor caso de todos en el que el algoritmo escoge siempre el peor brazo. Este caso espec´ıfico simboliza la inexistencia de aprendizaje. Por otra parte, la funci´on de color rojo representa el l´ımite superior del remordimiento esperado asociado al algoritmo Exploraci´on-Primero. Por ende, las l´ıneas verticales representan el remordimiento que el algoritmo ha sido capaz de evitar o el nivel de aprendizaje del algoritmo tras 100 y 200 rondas, respectivamente. 16 0 50 100 150 200 250 300 0 100 200 300 Rondas (T) Remordimiento (R(T)) R(T) = O(T) R(T) = T2/3×O(Klog T)1/3 Figura 1: Gr´afica de Remordimiento. El algoritmo Exploraci´on-Primero funciona en dos fases. Primero, explora cada brazo durante un n´umero Npredefinido de rondas. Despu´es, selecciona el brazo con la mejor recompensa promedio, observada durante la fase de exploraci´on, hasta el final del horizonte temporal. El problema de este algoritmo es que la exploraci´on se realiza por completo al comienzo del proceso y no se distribuye a lo largo del tiempo. Esto significa que, una vez que se ha completado la fase de exploraci´on, el algoritmo deja de explorar y se centra ´unicamente en la explotaci´on del brazo que obtuvo el mejor rendimiento durante la fase de exploraci´on. En muchos casos, ser´ıa m´as efectivo distribuir la exploraci´on de manera m´as uniforme a lo largo del tiempo en lugar de realizarla toda al comienzo. Al distribuir la exploraci´on de manera m´as uniforme, el algoritmo tendr´ıa m´as oportunidades de aprender sobre los brazos y actualizar sus estimaciones de recompensas medias a medida que avanza el tiempo. Esto podr´ıa ayudar a evitar que el algoritmo se atasque en una decisi´on sub´optima basada en informaci´on inicial limitada y a aumentar el nivel de aprendizaje del algoritmo. Por este motivo nace otro algoritmo simple: ´ Epsilon-Avaricioso. 4.1.2. Algoritmo ´ Epsilon-Avaricioso Algoritmo 4.2 ´ Epsilon-Avaricioso (ε1, ε2, . . . ). 1: for cada ronda t= 1,2, . . . do 2: Tirar una moneda con unas probabilidades de exploraci´on εt 3: if exploraci´on then 4: explorar: elegir un brazo auniformemente 5: else 6: explotar: elegir el brazo con la recompensa m´as alta hasta el momento 7: end if 8: end for Teorema 4.2. El algoritmo ´ Epsilon-Avaricioso con probabilidades de exploraci´on εt=t−1/3·(Klog t)1/3alcanza un l´ımite superior de remordimiento E[R(t)] ≤t2/3·O(Klog t)1/3para cada ronda t. Se conoce como “avaricioso” ya que se fundamenta en elegir la mejor opci´on a corto plazo. Sin embargo, es un algoritmo que presenta una exploraci´on de brazos distribuida uniformemente a lo largo de las rondas dado que en cualquier ronda, con εt>0, hay probabilidades de explorar. De esta forma, se consigue solucionar el problema que presenta el algoritmo Exploraci´on-Primero y, a la vez, como se consigue demostrar en [2], obtener un remordimiento id´entico cuando el n´umero de rondas en las que se ha explorado es del orden de t2/3con un horizonte temporal T=t. Esta cantidad de rondas exploradas se consigue, tal y como sugiere el teorema 17 anterior, con una probabilidad de ´exito εt∼t−1/3. La notaci´on “∼” sugiere que una expresi´on es similar a otra. En cada ronda t, el algoritmo explora con una probabilidad de εt. Es decir, la probabilidad de explorar εtse ajusta de acuerdo con el n´umero de rondas que se han completado. La idea es que al principio se debe explorar en mayor medida para descubrir los brazos que dan las mejores recompensas y, a medida que se adquiere informaci´on adicional, se pueden explotar los brazos que ya se sabe que son buenos. Por lo tanto, la probabilidad de explorar se reduce a medida que aumenta el n´umero de rondas. Antes de continuar con la explicaci´on de los algoritmos avanzados, se se˜nala la relevancia de este algoritmo en una implementaci´on que se llevar´a a cabo en la secci´on vertebral de este trabajo. 4.2. Algoritmos Avanzados: Exploraci´on Adaptativa Los algoritmos avanzados se han desarrollado a ra´ız de que los anteriores algoritmos, ´ Epsilon-Avaricioso y Exploraci´on-Primero, tienen el defecto de no planificar la exploraci´on en funci´on del historial de las recompensas observadas. Con el objetivo de ser m´as eficientes en t´erminos de aprendizaje, es decir, necesitar menos rondas para adquirir el mismo nivel de aprendizaje, los algoritmos avanzados incorporan otro modelo de planificaci´on conocido como exploraci´on adaptativa que distribuye o adapta la exploraci´on seg´un las recompensas observadas. Para comenzar, es necesario definir el concepto y significado de los l´ımites de confianza superior einferior, denominados como UCBt(a) y LCBt(a) respectivamente para un brazo ay una ronda t. Estos conceptos son la base en la que se cimientan los algoritmos avanzados que se comentan en este apartado. El intervalo definido por [LCBt(a),UCBt(a)] es conocido como el intervalo de confianza. Matem´aticamente, se definen: UCBt(a) = µt(a) + rt(a) y LCBt(a) = µt(a)−rt(a) De esta forma, los l´ımites de confianza se obtienen a partir de la recompensa media µt(a) considerada para el brazo aen la ronda ty a partir del radio de confianza rt(a), que act´ua como la variabilidad de la media de recompensas y se calcula en funci´on de nt(a), donde nt(a) representa el n´umero de veces que se ha seleccionado el brazo ahasta la ronda t. Matem´aticamente, el radio de confianza se calcula como sigue: rt(a) = p2 log T/nt(a) El c´alculo del radio sugiere que, como la variable nt(a) se encuentra en el denominador de la expresi´on, cuanto menor sea el n´umero de veces que se ha seleccionado el brazo ahasta la ronda t, mayor ser´a el valor del radio de confianza para dicho brazo y dicha ronda. En resumen, al vector de recompensas medias se le suma o resta el radio de confianza para obtener el l´ımite de confianza superior o inferior, respectivamente. A partir del intervalo de confianza, que un brazo asea elegido en la ronda tpuede ser por dos razones: porque ha devuelto una recompensa media µt(a) alta y/o porque el radio de confianza rt(a) es alto debido a que el brazo ano se ha explorado mucho en comparaci´on con el resto de brazos. Ambos motivos son alicientes para que el brazo sea elegido y, por tanto, la combinaci´on empleada de µt(a) y rt(a) logra un equilibrio coherente entre la exploraci´on y la explotaci´on. 4.2.1. Algoritmo Eliminaci´on Sucesiva Un algoritmo que utiliza esta idea de l´ımites superiores e inferiores a partir del vector de recompensas medias y el radio de confianza es el algoritmo Eliminaci´on Sucesiva. Algoritmo 4.3 Algoritmo Eliminaci´on Sucesiva. 1: Inicialmente todos los brazos est´an “activos”; 2: for cada fase f= 1,2, . . . do 3: se prueban todos los brazos activos (por lo que cada fase puede contener m´ultiples rondas, tantas como brazos activos resten); 4: se desactiva un brazo asi existe brazo a′con UCBt(a)<LCBt(a′); 5: end for 18 Teorema 4.3. El algoritmo Eliminaci´on Sucesiva tiene un remordimiento esperado E[R(T)] ≤ O(Kt log T)1/2 para cada ronda t≤T. Por tanto, en la ´ultima ronda del horizonte temporal T, el remordimiento esperado es E[R(T)] ≤ O(KT log T)1/2. Para explicar c´omo el algoritmo va descartando la explotaci´on de los peores brazos sucesivamente, se incluye un corto ejemplo que supone 3 brazos y un escenario tras la fase 1 en el que se obtuvieron los siguientes UCB y LCB: Brazo A: UCB(A) = 0,5, LCB(A) = 0,3. Brazo B: UCB(B) = 0,9, LCB(B) = 0,6. Brazo C: UCB(C) = 0,8, LCB(C) = 0,7. En este caso, UCB(A) <LCB(B) y UCB(A) <LCB(C), por lo que se desactiva el brazo A. Ahora, solo quedan los brazos B y C activos. El algoritmo continua con la siguiente fase y repite los pasos 2-4. Si en alg´un momento UCB(B) <LCB(C) o UCB(C) <LCB(B), el algoritmo desactiva el brazo correspondiente y se queda con el brazo restante como el que tiene la mejor recompensa promedio estimada. A continuaci´on, en la figura 2, se analiza el remordimiento del algoritmo Eliminaci´on Sucesiva en comparaci´on con el de los algoritmos simples: 0 50 100 150 200 250 300 0 100 200 300 Rondas (T) Remordimiento (R(T)) R(T) = O(T) R(T) = T2/3×O(Klog T)1/3 R(T) = O(KT log T)1/2 Figura 2: Gr´afica de Remordimiento. En t´erminos de aprendizaje, la diferencia entre este primer algoritmo avanzado que se ha analizado y los algoritmos simples ya comentados viene representada por la longitud de las l´ıneas verdes. En conclusi´on, se observa una ligera mejora o disminuci´on del l´ımite superior del remordimiento esperado al usar los conceptos UCB y LCB para solucionar un problema de bandidos estoc´asticos. 4.2.2. Algoritmo UCB1 Otro enfoque para la exploraci´on adaptativa en funci´on del historial de las recompensas observadas es conocido como optimismo bajo incertidumbre. En esta variante, se asume que cada brazo es lo mejor que podr´ıa ser dadas las observaciones hasta el momento, y se elige el mejor brazo bas´andose en estas estimaciones optimistas. Esto da lugar al algoritmo conocido como UCB1. Teorema 4.4. El algoritmo UCB1 se caracteriza por tener el mismo remordimiento que tiene el algoritmo Eliminaci´on Sucesiva. Por lo tanto, su rendimiento tambi´en queda representado por la funci´on de color naranja de la figura 2. 19 Algoritmo 4.4 Algoritmo UCB1. 1: Se prueba cada brazo una vez. 2: En cada ronda t, se elige el arg m´axa∈[K]UCBt(a), donde UCBt(a) = µt(a) + rt(a). Este algoritmo tambi´en podr´a ser denominado como UCB a lo largo de este trabajo. Por otro lado, tal y como se ha mencionado anteriormente, un brazo aes elegido por haber obtenido una media de recompensas alta o por un radio de confianza alto. En otras palabras, la elecci´on del brazo se basa bien en su explotaci´on (dada su media de recompensas) o en su exploraci´on (dada su radio de confianza). De esta manera, se consigue un punto ´optimo entre la exploraci´on y la explotaci´on. Sin embargo, al sumar el radio de confianza se est´a aplicando un enfoque muy optimista y se supone que un brazo obtendr´a la mejor recompensa que le es posible, y esto no siempre es cierto. Por otra parte, al partir de la base de que las acciones son prometedoras, UCB1 garantiza que no se descarten prematuramente acciones que podr´ıan ser prometedoras en un futuro. Esto fomenta la b´usqueda de nuevas soluciones y tambi´en permite una correcta adaptaci´on al entorno. Este algoritmo es uno de los m´as representativos dentro de los estoc´asticos, ya que realiza exploraci´on adaptativa y muestra intuitivamente c´omo un bandido multi-brazo trata de encontrar un equilibrio entre la exploraci´on y la explotaci´on. Adem´as, su escalabilidad a distintas aplicaciones es otro factor importante que juega a favor de este algoritmo. Debido a su idiosincrasia, UCB1 es ampliamente usado y es incluso aplicable a los bandidos contextuales; es por ello que en las secciones posteriores se har´a uso del algoritmo UCB1 en problemas m´as complicados que consideren el contexto. 20 5. Bandidos Antagonistas Esta subsecci´on est´a orientada a definir el problema de los bandidos antagonistas con el objetivo de identificar este escenario en las aplicaciones reales que se expondr´an como trabajo principal de esta investigaci´on. Ser´a de gran utilidad conocer las especificaciones de dos algoritmos, Hedge y Exp4, ya que ser´an puestos en pr´actica en las aplicaciones que culminan este trabajo. En los bandidos estoc´asticos, la funci´on de recompensas es est´atica con respecto al paso de las rondas. En cambio, en el problema de bandidos antagonistas la funci´on de recompensas es din´amica, en el sentido de que cambia con el paso de las rondas bajo la influencia de un adversario o antagonista. Para ilustrar este nuevo escenario se plantea un problema en el que, dada una red de ciudades y carreteras, en cada ronda el objetivo es encontrar el camino, entendido como un brazo del bandido, m´as eficiente para un env´ıo de paquetes con una ciudad origen y otra destino. Adem´as, se supone que la longitud de todas las carreteras es igual para hacer m´as sencilla la explicaci´on. Se contempla una funci´on de recompensas determinista que, en funci´on de las ciudades de origen y destino, junto con la elecci´on de ruta del algoritmo, asigna una recompensa de ‘1’ al camino m´as eficiente y ‘0’ a cualquier otra ruta. De todas formas, se podr´ıa hacer uso de una funci´on de recompensas aleatorias sin que afectase a la comprensi´on del escenario de los bandidos antagonistas, tal y como se comentar´a m´as adelante. Se toma la siguiente red para realizar esta explicaci´on: 1 2 3 4 Figura 3: Red de ciudades y carreteras. Sup´ongase que se pide al algoritmo encontrar el camino m´as r´apido para ir desde la ciudad origen 1 a la ciudad destino 4. A partir de la figura 3 se distinguen dos ´unicos caminos posibles: el trazado 1-2-4, que se designar´a como “camino 1”, y el trazado 1-3-4, denominado “camino 2”. La clave del problema, sin tener en cuenta las longitudes, se encuentra en la existencia de variables que el algoritmo no es capaz de controlar. La presencia de estas variables representa la presencia de un antagonista en el problema de bandidos. En este caso, la congesti´on de las carreteras es el antagonista. Esta variable desconocida para el algoritmo, que se supone que toma valores distintos en cada ronda, modifica el comportamiento de las recompensas de cada ronda sin que el algoritmo sea consciente. En consecuencia, ya no habr´a un camino m´as eficiente que otro siempre, sino que la eficiencia de los caminos cambia en cada ronda seg´un las congestiones. Por tanto, el algoritmo, cuyo objetivo es aprender el camino m´as eficiente dado un trayecto, observar´a en alg´un momento que el camino que ha considerado como m´as eficiente hasta ese momento dejar´a de serlo, y deber´a considerar otro camino como el m´as eficiente. Como apunte adicional, la congesti´on es una medida que relaciona la ocupaci´on de la carretera con su capacidad, pero esto ahora no es relevante porque se toma la congesti´on como un dato directo que no tiene que ser calculado. Para comprobar que la congesti´on hace variar las recompensas que devuelven los caminos entre rondas, se plantea que en la ronda 1 la congesti´on de las carreteras 1-2, 1-3, 2-4 y 3-4 es 8, 3, 4 y 1 respectivamente, y que en la ronda 2 la congesti´on es 3, 6, 4 y 7, tambi´en respectivamente. Esta sucesi´on de congestiones se repite desde la ronda 3 en bucle. De esta forma, la congesti´on total experimentada en el “camino” 1 tiene un valor de 12 en las rondas impares y de 7 en las rondas pares. En cuanto al “camino 2”, su congesti´on es de 4 en las rondas impares y de 13 en las pares. Por tanto, en las rondas pares las recompensas ser´an de ‘1’ para el camino 1 y de ‘0’ para el camino 2, mientras que en las rondas impares las recompensas ser´an de ‘1’ para el camino 2 y de ‘0’ para el camino 1. Es decir, como se ha querido demostrar desde el principio, este es un escenario en el que el problema planteado es de bandidos antagonistas porque las recompensas pueden variar entre rondas debido a la presencia de un 21 antagonista que el algoritmo no puede controlar. La explicaci´on m´as t´ecnica del problema argumenta que las recompensas asociadas a cada camino no pueden modelizarse mediante una distribuci´on estacionaria, por lo que ser´ıa necesario un conjunto m´as sofisticado de supuestos estad´ısticos. En general, puede ser dif´ıcil o imposible determinar los supuestos estad´ısticos correctos para un dominio dado, y algunos dominios pueden mostrar un alto grado de incertidumbre. Algunos ´ambitos pueden presentar dependencias hasta el punto de que no resulte apropiado aplicar tales supuestos. De esta forma, en problemas en los que la recompensa se genere de una manera m´as compleja o pseudo-aleatoria y no se sepa claramente qu´e valor va a tomar, habr´a que recurrir a considerar que la recompensa depende de factores ajenos desconocidos para el algoritmo, que representar´an el papel de antagonista estudiado en esta secci´on [6]. A la hora de explicar los bandidos antagonistas, muchos autores como Aleksandrs Slivkins en [2] hacen hincapi´e en la idea de que en estos bandidos las recompensas var´ıan como si estuviesen declaradas por un adversario con la intenci´on maliciosa de fastidiar al algoritmo. Es com´un entre los autores que explican esta idea que comparen este tipo de problema con una casa de apuestas en la que las recompensas han sido definidas por un adversario, la casa de apuestas, con intenci´on de que el jugador obtenga la m´ınima recompensa. Esto puede llevar a confusiones al lector debido a una incorrecta generalizaci´on. Es decir, detr´as de las recompensas variantes de los bandidos adversarios no tiene por qu´e haber una mala intencionalidad. Es cierto que es una traba para el algoritmo, pero puede no ser malintencionada. De hecho, en el ejemplo considerado anteriormente para explicar los bandidos antagonistas no existe ninguna intenci´on de fastidiar detr´as de la variabilidad de las recompensas, sino que est´a presente la congesti´on como una variable desconocida para el algoritmo que altera la funci´on de recompensas, pero en ning´un caso los valores de la congesti´on de las carreteras est´an sugestionados por alg´un adversario con mala intenci´on. Una vez explicado el concepto de recompensas din´amicas que difiere de las recompensas est´aticas IID de los bandidos estoc´asticos, es importante saber que existe otra diferencia m´as entre las recompensas estoc´asticas y las antagonistas. Esta diferencia atiende a que las recompensas estoc´asticas IID, por norma general, son aleatorias debido a que est´an siempre descritas por una distribuci´on de probabilidades, mientras que en las recompensas en un escenario antagonista no hay ninguna especificaci´on, es decir pueden ser deterministas o aleatorias. Cabe destacar que las recompensas estoc´asticas pueden ser deterministas si su distribuci´on es trivial y solo permite un valor. Las recompensas deterministas, por su propia definici´on, est´an descritas de forma determinada, sin aleatoriedad. Esto que se acaba de comentar tiene un efecto directo en el an´alisis del remordimiento de los problemas antagonistas porque obliga a distinguir entre si la funci´on de recompensas es determinista o aleatoria. Antes de explicar el remordimiento, este trabajo considera, al igual que los de otros autores, que la mejor forma de trabajar con bandidos antagonistas es con costes en lugar de con recompensas. Es decir, se entiende que lo que el algoritmo obtiene por la elecci´on de un brazo es un coste. De esta forma, el objetivo del algoritmo es reducir el coste obtenido y, por tanto, se afronta la explicaci´on del remordimiento desde el punto de vista de los costes obtenidos. De todas formas, si el problema planteado se basa en la obtenci´on de recompensas se puede realizar una conversi´on sencilla para que el problema se base en la obtenci´on de costes en su lugar. Esta conversi´on se cimienta en la idea de que las versiones de p´erdida y ganancia son sim´etricas, en el sentido de que se puede trasladar el an´alisis de una a otra mediante la equivalencia: li,t = 1 −gi,t, donde li,t es el coste asociado al brazo ien la ronda tygi,t es la recompensa asociada al brazo ien la ronda t. Por ejemplo, en el planteamiento de la red de ciudades y carreteras planteado anteriormente, si se asume que las recompensas est´an acotadas en el intervalo [0,1] y la recompensa de elegir el “camino 1” en la ronda 1 es 0,3, el coste equivalente a dicha recompensa es 0,7. El remordimiento asociado a un problema de bandidos antagonistas es un aspecto complejo de entender. Para un entendimiento riguroso y teniendo en cuenta que, a ra´ız de la existencia de recompensas din´amicas, no hay un solo brazo ´optimo como en el caso de los bandidos estoc´asticos, sino m´as bien una secuencia ´optima de brazos, el concepto de remordimiento controlar´ıa la diferencia entre el coste que realmente ha obtenido y el coste que se habr´ıa acumulado si el algoritmo hubiera seguido en todas las rondas la estrategia marcada por esta secuencia ´optima de brazos [8]. En este trabajo, al igual que en los del resto de autores, no se va a llegar tan lejos en el an´alisis y se va a realizar igual que en el entorno estoc´astico. Es decir, se va a considerar que s´ı existe un ´unico brazo ´optimo a lo largo de todas las rondas. Por tanto, el remordimiento expresa la diferencia 22 entre el coste obtenido por el algoritmo y el coste que podr´ıa haberse obtenido si el algoritmo hubiera jugado en todas las rondas el brazo ´optimo. Se considera una “tabla de costes” ct(a) que indica el coste para un brazo a∈Ken la ronda t∈T: Si la funci´on de costes es determinista, el coste total de cada brazo aes coste(a) = PT t=1 ct(a). Intuitivamente, el brazo ´optimo a∗es el brazo con el coste total m´as bajo. Formalmente, a∗:= arg m´ına∈[K]coste(a). Por estas razones, el remordimiento con costes deterministas se expresa como: R(T) = T X t=1 ct(at)−m´ın a∈[K]coste(a) Si los costes son aleatorios, el brazo ´optimo a∗es el brazo con el coste esperado total m´as bajo. Formalmente, a∗:= arg m´ına∈[K]E[coste(a)], conociendo la distribuci´on de probabilidades que describe el comportamiento de los costes de cada brazo. Por tanto, el remordimiento en este caso queda definido por: R(T) = T X t=1 ct(at)−m´ın a∈[K]E[coste(a)] Tras haber expuesto estos aspectos fundamentales, se trata un punto clave: las variedades de antagonistas que pueden darse, entendiendo como antagonista aquellas variables desconocidas para el algoritmo que provocan la variaci´on de la funci´on de recompensas. Dependiendo de los conocimientos del adversario, se consideran dos tipos diferentes: Si el antagonista no conoce las elecciones de brazo del algoritmo se denomina indiferente. Por tanto, la variaci´on que ejerce sobre las recompensas no depende del comportamiento pasado del algoritmo. Por ejemplo, el escenario planteado al inicio de esta subsecci´on se caracteriza por la presencia de un antagonista indiferente porque el valor de las congestiones es independiente de las elecciones previas del algoritmo. En cambio, el antagonista adaptable o flexible, como su propio nombre indica, es un antagonista que es conocedor de las elecciones pasadas del algoritmo y puede variar tras cada ronda la configuraci´on de la funci´on de recompensas seg´un los brazos escogidos por el algoritmo en las rondas anteriores. Por ejemplo, en un casino ama˜nado, el propietario puede observar la forma en que apuesta un jugador para dise˜nar secuencias de ganancias maliciosas que vayan a contracorriente de las estrategias del jugador [4]. Independientemente de los ejemplos anteriores, la malintencionalidad no es un requisito obligatorio ni en el antagonista indiferente ni en el antagonista adaptable. Debe quedar claro que la presencia de esta caracter´ıstica no afecta al an´alisis del problema. 5.1. Primer Intento de Soluci´on Dicho esto, un primer enfoque para resolver un problema de bandidos antagonistas podr´ıa ser el empleo de un algoritmo determinista b´asico. A continuaci´on, se muestra un ejemplo: Algoritmo 5.5 Algoritmo Seguir al L´ıder 1: Inicializar: Juegue cada brazo una vez para obtener una estimaci´on inicial de los costes. 2: for cada ronda t= 1,2, . . . do 3: Seleccionar el brazo con el coste acumulado m´as bajo hasta el momento: at= arg m´ınaPt−1 s=1 cs(a). 4: Jugar el brazo seleccionado aty observar el coste incurrido. 5: Actualizar el coste acumulado del brazo at. 6: end for Este algoritmo siempre selecciona el brazo con el coste acumulado m´as bajo en cada ronda. Sin embargo, este algoritmo no es eficaz para este problema. Esto se debe a que, como expone [2], incluso un antagonista indiferente puede fastidiar el algoritmo si conoce su estrategia antes de empezar, aunque no sea sabedor de sus elecciones durante las rondas. Podr´ıa aprovechar este conocimiento para manipular los costes de los brazos y 23 forzar al algoritmo a tomar decisiones sub´optimas. Para demostrarlo se plantea resolver un problema b´asico en el que solo hay dos brazos A y B con el algoritmo Seguir al L´ıder. Adem´as, se supone que el antagonista presente en este problema es consciente de la estrategia que el algoritmo va a llevar a cabo. Al conocer la estrategia, el antagonista podr´ıa dise˜nar la siguiente funci´on de costes: En la primera ronda, el antagonista asigna un coste de 0.5 a A y un coste de 1 a B (coste acumulado de A <coste acumulado de B). El algoritmo, como no tiene referencias de los costes acumulados de cada brazo, elige de forma aleatoria el brazo A, por ejemplo. En este caso, el algoritmo ha escogido el brazo m´as eficiente. En la segunda ronda, el algoritmo elige A porque tiene el coste acumulado m´as bajo. Sin embargo, el antagonista sabe que el algoritmo va a elegir el brazo A en la segunda ronda porque es consciente de que el brazo con menor coste acumulado tras la primera ronda es dicho brazo. Por ello, asign´o otros valores a los costes de la ronda 2 de modo que el brazo A tuviese un coste asociado de 1 y el brazo B un coste asociado de 0. El algoritmo ha elegido el brazo menos eficiente esta vez. En la tercera ronda, el algoritmo cambia de brazo de nuevo y opta por el brazo B ya que tiene menor coste acumulado (1,5>1), pero como el antagonista lo pod´ıa anticipar, cambi´o la funci´on de costes para que en la ronda 3 el brazo A tuviese coste 0 y B coste 1. De esta manera, el algoritmo ha vuelto a seleccionar de nuevo el brazo menos ´optimo por segunda vez consecutiva. Ya en la cuarta ronda, el algoritmo prefiere el brazo A porque ahora es el que tiene menos coste acumulado hasta el momento (1,5<2), de nuevo el antagonista sab´ıa que esto va a suceder y otorg´o, para la ronda 4, al brazo A un coste de 0 y al brazo B un coste de 1. Esta ya es la tercera vez que el algoritmo pierde frente al antagonista. Tras exponer el ejemplo anterior, se comprende, bajo la premisa de que el adversario descubre la estrategia de elecci´on de brazos del algoritmo, que el adversario puede forzar al algoritmo a tomar decisiones equivocadas cada ronda. Concretamente, se observa que el algoritmo nunca ser´a capaz de identificar cu´al de los dos es el brazo que ofrece los costes ´optimos. Por tanto, a partir de la segunda ronda, aunque podr´ıa haber sido a partir de la primera ronda si la elecci´on aleatoria del algoritmo hubiese sido el brazo peor en lugar del mejor, el algoritmo elige el brazo con mayor coste en todas las rondas posteriores ya que es enga˜nado por el antagonista. Si se considera que cada ronda tiene una unidad de remordimiento porque en cada ronda el menor coste es 0 y el m´aximo es 1, al cabo de Trondas su remordimiento ser´a de Tunidades ya que sufre el m´aximo coste en todas las rondas. El remordimiento en esta situaci´on se puede expresar de la siguiente forma: R(T) = O(T) Este remordimiento, como ya se vi´o en la secci´on de los bandidos estoc´asticos 4, refleja la incapacidad de aprendizaje total por parte del algoritmo. Es decir, el peor o m´aximo remordimiento posible. 5.2. Algoritmos Efectivos La idea clave para sortear esta dificultad es a˜nadir aleatoriedad a la selecci´on del brazo a jugar. De este modo, el algoritmo puede “sorprender” al adversario e impedir ser manipulado por el antagonista, ergo, no se alcanzar´an remordimientos tan altos. Este efecto sorpresa basta para obtener un remordimiento esencialmente tan bajo como el remordimiento en el modelo estoc´astico. 5.2.1. Algoritmo Hedge Por este motivo, se procede a explicar un algoritmo muy conocido en el escenario de bandidos antagonistas que incorpora esta aleatoriedad mencionada, el algoritmo Hedge 6 obtenido de [2]. En finanzas, el t´ermino “hedge” se refiere a una estrategia de inversi´on que se utiliza para reducir o eliminar el riesgo de p´erdidas en una posici´on o cartera de inversi´on. La idea detr´as del hedging es proteger una inversi´on contra posibles movimientos desfavorables en el mercado, lo que puede ayudar a minimizar las p´erdidas en 24 ALGx, se alcanzar´ıa un remordimiento de la siguiente magnitud: E[R(T)] ≤O(KT log T)1/2. Por lo que el remordimiento para todos los contextos ser´ıa la suma del remordimiento alcanzado por todas las instancias. 6.1.1. Recomendador de Pel´ıculas para Cuatro Grupos Con el objetivo de entender este algoritmo, se ha desarrollado una implementaci´on basada en esta premisa de usar pocos contextos e instancias para cada uno de ellos. Concretamente, se trata de un sistema recomendador para un reducido n´umero de contextos, 4, y cada uno es considerado como un grupo de personas. En el grupo x1hay hombres de m´as de 40 a˜nos, en el grupo x2hay mujeres de m´as de 40 a˜nos, en el grupo x3hay hombres de menos de 40 a˜nos y en el grupo x4hay mujeres de menos de 40 a˜nos. Con esta simplificaci´on y un n´umero tan reducido de grupos se puede ilustrar correctamente este caso. Los brazos del sistema recomendador son pel´ıculas, y son siempre las mismas 5 pel´ıculas, K= 5. Tambi´en cabe se˜nalar que hay Trondas, siendo un par´ametro arbitrario de acuerdo al experimento, y en cada ronda t se recomienda una pel´ıcula a un usuario, por lo que cada una de las rondas representa un unsuario con una informaci´on contextual, esto es, un usuario que pertenece a un grupo. Por ejemplo, en la ronda uno se tiene que recomendar una pel´ıcula a un hombre mayor de 40 a˜nos y en la ronda 2 a una mujer de menos de 40, y as´ı sucesivamente. Por ´ultimo, hay que se˜nalar que las recompensas son obtenidas aleatoriamente para cada pel´ıcula, brazo, y para cada contexto, grupo. Las recompensas pueden tener tres valores [0, 0.6, 1]: siendo 0 si una pel´ıcula no le gusta nada al usuario, 0.6 si le gusta un poco y 1 si le gusta mucho. Las recompensas se calculan aleatoariamente ya que no hay datos reales. Se utiliza una funci´on creada por los autores que calcula las probabilidades aleatorias para cada grupo de usuarios y para cada brazo, y dentro de este contexto se generan tres probabilidades que suman 1 y representan lo que le puede gustar la pel´ıcula. Realmente las probabilidades de que a un grupo de usuarios le guste una pel´ıcula u otra se calculan de forma aleatoria ya que lo interesante de este apartado es tener diferentes gustos para las pel´ıculas de cada grupo de usuario. Haci´endolo de esta manera, se asegura que al grupo de usuarios 1 es m´as probable que les guste una pel´ıcula A, mientras que al grupo de usuarios 2 habr´a m´as posibilidades de que les guste una pel´ıcula D. Es necesario partir de esta premisa de que cada contexto, grupo de usarios, tiene diferentes gustos, o lo que es lo mismo, distintas funciones de probabilidades, ya que al hacerlo es posible estudiar c´omo de bueno es este algoritmo recomendando pel´ıculas para cada grupo de usuarios con distintas preferencias. Sin embargo, s´ı que puede haber dos grupos de usuarios que tengan una distribuci´on de recompensas parecidas, tal y como podr´ıa pasar si se analizan los gustos de pel´ıculas de dos grupos en la vida real. Posteriormente, durante la simulaci´on, se extrae una probabilidad aleatoria para un brazo elegido en un contexto observado y usando su distribuci´on de probabilidades, calculada anteriormente, se obtiene una recompensa dentro del rango mencionado que es elegida aleatoriamente pero en la distribuci´on de probabilidades del brazo en el contexto. Para ilustrar mejor c´omo es la funci´on de recompensas se expone un ejemplo. Dado el contexto 2, mujeres de m´as de 40 a˜nos, y el brazo 1, la pel´ıcula A, hay una distribuci´on de probabilidades generada aleatoriamente que podr´ıa ser de la siguiente forma: 25 % a que no le gusta la pel´ıcula, 35 % a que le gusta un poco y 40 % a que le gusta mucho. Si en la ronda taparece un usuario de este contexto y se elige el brazo 1, se coger´a uno de los tres posibles valores aleatoriamente de la recompensa conforme a esta distribuci´on, pero al simular m´ultiples rondas, a pesar del factor de aleatoriedad, a la larga se obtendr´a el 25 % una recompensa de 0, el 35 % una recompensa de 0.6 y el 40 % una recompensa de 1. Es importante considerar que la funci´on de recompensas permanecer´a constante. Por ejemplo, esto significa que dicha funci´on de recompensas para mujeres de m´as de 40 a˜nos ser´a igual para las pel´ıculas A que se les muestren, sus gustos por dicha pel´ıcula ser´an iguales para todas las rondas, y habr´a un 40 % de probabilidades de que le gusten mucho la pel´ıcula A en la ronda 1 y en la ronda T−1. Aplicando el algoritmo de bandidos multi-brazo contextuales para este caso de uso, se han definido cuatro instancias del algoritmo UCB1 de manera que cada instancia trata un grupo. Utilizando esta t´ecnica es posible conseguir que la instancia 1 se especialice en encontrar cu´al es el mejor brazo (pel´ıcula) para el grupo de varones mayores de 40 a˜nos mientras que la instancia 2 buscar´a dicho brazo para mujeres de m´as de 40 a˜nos. Esto permite que cada instancia explore y explote de manera diferente las pel´ıculas seg´un las preferencias de estos usuarios. Por ejemplo, la instancia uno del algoritmo UCB1 que trata a varones mayores de 40 a˜nos podr´ıa explotar 31 mucho desde las primeras rondas la pel´ıcula C si observa que le da muy buenos resultados en comparaci´on con el resto de pel´ıculas. Por otro lado, la instancia que trate a las mujeres de menos de 40 a˜nos podr´ıa centrarse m´as en la exploraci´on si hay tres pel´ıculas: A, B y D que le reportan recompensas similares. De este modo, es apreciable que cada instancia adecuar´a su exploraci´on-explotaci´on de manera ´unica para adcuarse a la funci´on de probabilidades del grupo de usuarios que trata. Tras definir el fundamento de estos algoritmos, se contemplar´an cu´ales fueron los pasos a seguir para implementar este ejemplo. En primer lugar, se crea una base de datos sint´etica, aleatoriamente ordenada de 10000 personas, es decir, T= 10000 rondas. Las distribuciones en cada grupo son elegidas aleatoriamente, pudiendo haber un gran porcentaje de un grupo y un peque˜no porcentaje de otros para ver c´omo se desenvuelve el bandido con tama˜nos de grupos distintos. Cabe mencionar que, tal y como est´a siendo explicada esta secci´on, en este caso las palabras grupos y contextos son sin´onimos, al igual que pel´ıculas y brazos. Despu´es de haber obtenido los usuarios con su contexto, ha sido implementado el algoritmo UCB1 [de acuerdo al esquema del algoritmo 2.5]. El algoritmo consiste esencialmente en dos funciones fundamentales. Primero tiene que seleccionar un brazo usando el enfoque optimista, seg´un el valor UCB, que se calcula con la recompensa media, y representa la explotaci´on, y con el radio de confianza, que representa la exploraci´on. As´ı el algoritmo busca el balance para cada grupo de personas de explorar o explotar. Tambi´en el algoritmo debe actualizar la recompensa media para cada brazo, y se hace esta operaci´on tras obtener una recompensa para el brazo obtenido. Esto se actualiza para que en las pr´oximas rondas se tengan en cuenta los valores actualizados para la selecci´on de brazo. Una vez hechos todos estos pasos (la creaci´on de usuarios, el algoritmo UCB1 y la funci´on de recompensas), ha sido realizada una simulaci´on para observar la actuaci´on del algoritmo contextual. Como lo que se pretende es entender c´omo de bueno es su rendimiento, se comparan sus recompensas y remordimiento con un algoritmo UCB1. Por lo tanto, por un lado est´a el algoritmo contextual que son cuatro instancias del UCB1, una para cada contexto, y por otro lado se encuentra el algoritmo UCB1 que trata todos los datos por igual y no distingue contextos. Este segundo algoritmo recomendar´a por igual a personas del grupo 1 y del grupo 4 por lo que lo que realmente se estudiar´a aqu´ı es cu´al es el valor de considerar la informaci´on contextual. Pues bien, se podr´a observar en las siguientes gr´aficas que muestran el rendimiento de ambos bandidos durante una simulaci´on de 10000 usuarios. Adem´as debe tenerse en cuenta que el bandido UCB1 puede usarse como una representaci´on del rendimiento de un bandido estoc´astico frente a un bandido contextual, y as´ı se podr´a apreciar c´omo de importante es el contexto para dos algoritmos que tienen la misma estructura. Figura 5: Recompensas medias y remordimientos medios. En ambas gr´aficas se puede observar la evoluci´on de las recompensas obtenidas para ambos algoritmos: el bandido contextual y el UCB1 que es un bandido estoc´astico. Se puede apreciar como aumenta considerablemente la recompensa en estos bandidos que consideran el contexto y produce una distancia significativa entre la recompensas y los remordimientos tipos. Adem´as, se muestra como a lo largo de las rondas los dos bandidos van mejorando su rendimiento ya que aprenden, pero los bandidos contextuales aprenden m´as r´apido al principio y por el hecho de tener en cuenta el contexto alcanzan mejores recompensas y, consecuentemente, menor 32 remordimiento. Gracias a estos resultados, por primera vez aparece la utilidad del contexto para mejorar el rendimiento de los bandidos multi-brazo. Y adem´as, es destacable que este es un enfoque intuitivo para ilustrar las ventajas de primera mano de los bandidos multi-brazo contextuales. Como conclusi´on, los resultados son m´as que satisfactorios y presentan un horizonte prometedor para el desarrollo de bandidos contextuales en posteriores aplicaciones pr´acticas. A pesar de esto, se podr´ıa pensar que la distribuci´on de la poblaci´on, es decir, el n´umero de personas de cada uno de los cuatro grupos puede afectar significativamente a las recompensas obtenidas, ya que el n´umero de usuarios que pertenece a un grupo es obtenido aleatoriamente. Por este motivo, la misma simulaci´on ha sido realizada para cien distribuciones o bases de datos distintas, habiendo en cada una de estas 10000 personas repartidas aleatoriamente entre los 4 grupos. Al usar este enfoque, se podr´a ver si realmente los bandidos contextuales son mejores para distintas distribuciones de los usuarios, y si son eficientes en distribuciones con distintos porcentajes de usuarios de un grupo. En este an´alisis, se observar´a el rendimiento de este algoritmo para distribuciones en las que podr´a haber pocos miembros de grupo de usuarios. As´ı, se estudiar´a si usar un bandido contextual puede ser un opci´on interesante aunque pudiese haber pocos usuarios de un cierto grupo y, en este caso, el aprendizaje de la instancia correspondiente se ver´ıa perjudicado. Por ello, es significativa esta cuesti´on. Los resultados son proporcionados en las siguientes gr´aficas. Figura 6: Resultados para distintas distribuciones de usuarios. Cabe mencionar que estas ´ultimas gr´aficas muestran las recompensas acumuladas para cada base de datos, estando una base de datos compuesta por 10000 usuarios y siendo la recompensa m´axima 10000, el n´umero de usuarios por la recompensa m´axima, que es 1. Se puede afirmar con total firmeza que los resultados son prometedores para distintas distribuciones, y para una cantidad suficiente de datos, la distribuci´on de los contextos no es ning´un problema para los bandidos contextuales. Generalmente el bandido contextual es m´as eficaz que un bandido estoc´astico, tal y como reflejan los datos de recompensas y remordimientos. Por otra parte, el ´ultimo experimento desarrollado en esta secci´on ha sido para ver en qu´e medida influyen el n´umero de contextos para evaluar el rendimiento del bandido. Debido a esto, se supone que en vez de cuatro grupos de personas o cuatro contextos, hay diversos n´umeros crecientes de contextos para comprobar si este bandido contextual, enfocado a pocos contextos, seguir´ıa obteniendo mejores recompensas para muchos contextos respecto a un bandido estoc´astico como el UCB1. Esta ´ultima parte de la secci´on arrojar´a resultados determinantes respecto a la comparaci´on entre bandidos contextuales y bandidos estoc´asticos y, en definitiva, concluir´a por presentar las ventajas de estos bandidos en una primera instancia. En la figura 7 est´an representados los resultados de un bandido contextual frente a un bandido estoc´astico para diferentes tama˜nos del contexto. Los brazos y la forma de obtener la recompensa no han variado respecto al inicio de la implementaci´on, pero para utilizar varios tama˜nos de contextos se han tenido que realizar algunas 33 Figura 7: Resultados al aumentar el n´umero de contextos. modificaciones. Para ello, se han creado al igual que antes distribuciones de 10000 usuarios y 150 simulaciones, habiendo para cada una de estas distribuciones un n´umero de contextos distintos. Esto significa que para cada una de las 150 simulaciones se ha probado con un tama˜no distinto del contexto, y para cada tama˜no se han recomendado pel´ıculas a 10000 usuarios. De esta manera, se observar´an las recompensas medias si hubiera 4 grupos de usuarios y se les sugieren pel´ıculas a todos ellos. Tambi´en se analizan las recompensas medias si hay 10 grupos de usuarios, 100 grupos, 500 grupos... As´ı hasta los 10000.. Realmente ha sido realizado el mismo proceso de recomendaci´on a 10000 usuarios pero 150 veces, y en cada una de estas veces los usuarios se dividen en menos o m´as grupos. De este modo, se puede ver c´omo influye el tama˜no del grupo. Esta simulaci´on se realizar´a 150 veces y en cada una de las iteraciones se usa un n´umero de contextos distintos. Para ver realmente el efecto del n´umero de contextos se plantea la siguiente l´ogica: se comienza con cuatro distintos contextos al igual que antes, y va aumentando el n´umero de contextos hasta llegar al tama˜no de la distribuci´on, es decir, 10000, un contexto distinto para cada usuario. Concretamente, los 150 tama˜nos de contextos distintos se encuentran uniformemente divididos desde 4 hasta T, que es 10000. Los resultados son esclarecedores y confirman las evidencias que se est´an exponiendo a lo largo de este apartado. Es se˜nalable que el rendimiento de ambos bandidos es mejor para pocos contextos, y conforme aumenta el n´umero de distintos contextos, ambos bandidos obtienen peor rendimiento, cosa que se ve reflejada en las recompensas medias y en las p´erdidas, remordimientos medios. Adem´as, hay una gr´afica adicional para ver la diferencia entre remordimientos y con su ayuda se entiende perfectamente que el bandido contextual siempre alcanza menos remordimiento que el estoc´astico, ergo el rendimiento de un bandido contextual es considerablemente superior. Por ello, si se comparan estrictamente el UCB con un bandido contextual que instancie UCBs para cada contexto, es observable que el rendimiento de las instancias para cada contexto ser´a superior. No obstante, debe tenerse en cuenta que si se aumentan el grupo de usuarios hasta tener un grupo por cada usuario, es decir, 10000 contextos, cada instancia del UCB1 tratar´a exclusivamente a un usuario y por lo tanto, no aprender´a. Por este motivo, se observa en el gr´afico que para muchos grupos de usuarios, y muchas instancias del UCB1, el algoritmo no aprende ya que tiene pocos usuarios a los que recomendar. Adem´as, cabe se˜nalar que las mejores recompensas se dan al principio de la gr´afica, cuando hay pocos grupos de usuarios y s´ı que hay un espacio notable entre las recompensas del bandido contextual y el bandido estoc´astico. Y, a partir de aproximadamente los 2000 grupos de usuarios, 5 usuarios por grupo (Kusuarios), las recompensas son extremadamente malas porque ninguno de los algoritmos aprenden pero el contextual sigue obteniendo una insignificante mejor recompensa media. Debido a esto, los mejores resultados son obtenidos usando un n´umero peque˜no de grupos de usuarios, es decir, reduciendo los contextos. Y tambi´en estas recompensas se mejoran aprovechando los bandidos contextuales. Es convienente recordar que en las primeras figuras de esta secci´on alcanzaban recompensas de entre 0,7y0,8. Y para concluir, se puede afirmar que en efecto este tipo de bandidos contextuales rinde de manera sobresaliente en entornos con pocos contextos. Adem´as, sirve de perfecta muestra para ejemplificar lo interesante que puede ser desarrollar bandidos contextuales. Considerando el contexto es posible desarrollar algoritmos m´as ´optimos y tambi´en estudiar problemas m´as complejos gracias a los bandidos multi-brazo contextuales. 34 6.2. Bandidos Contextuales Lipschitzianos 6.2.1. Motivaci´on En esta secci´on se considera una variante de los bandidos contextuales, los lipschitzianos o de tipo Lipschitz. Se tratar´a la motivaci´on detr´as de este tipo en concreto de bandidos contextuales y cu´ales son sus principales caracter´ısticas. A continuaci´on, se proceder´a a explorar en profundidad los bandidos contextuales con la condici´on de Lipschitz. Este marco permite manejar bandidos contextuales con un gran n´umero de contextos. La condici´on de Lipschitz es el eje de esta secci´on. Adem´as, en lugar de tener contextos discretos para elegir (como un n´umero finito de opciones), hay contextos ilimitados en un espacio continuo. Es esencial reconocer que existen infinitos contextos, y estos se encuentran distribuidos de forma continua. Dada la naturaleza continua del espacio de contextos, los problemas que involucran un n´umero infinito de contextos representan una gran complejidad, volvi´endose inmanejables en muchos casos. No obstante, el algoritmo de bandido contextual lipschitziano puede capitalizar esta circunstancia. Se presume que es posible ubicar cualquier contexto en un intervalo [0,1]. A este proceso se le denominar´a “mapear”, que refiere a situar un contexto dentro de un intervalo determinado. Se puede postular que, de acuerdo a la condici´on Lipschitz, las recompensas pueden ser interpretadas en relaci´on a los contextos mediante la utilizaci´on de una variable L, conocida como constante de Lipschitz, que es reconocida por el algoritmo. A continuaci´on, se presenta la condici´on de Lipschitz: Definici´on 6.1. Un bandido es Lipschitziano si cumple con la condici´on: |µ(a|x)−µ(a|x′)| ≤ L·|x−x′|para cualquier brazo a, a′∈Ay contextos x, x′∈X. La condici´on de Lipschitz implica que la diferencia entre las recompensas medias de un brazo para dos contextos diferentes es menor o igual a la diferencia entre los contextos multiplicada por una constante L. Si se cumple esta condici´on en un problema, ser´a posible discretizar uniformemente el espacio contextual. La discretizaci´on es un enfoque que permitir´a dividir el espacio contextual. Considerando que existe un espacio contextual donde se pueden representar todos los contextos posibles, se usar´a la discretizaci´on para dividir este espacio en distintas secciones. De esta manera, se trata el contexto observado en cada ronda como si perteneciera a una secci´on del espacio de contextos y cada uno de estos espacios discretizados ser´a tratado por un algoritmo distinto. Para explicar este proceso de discretizaci´on se puede usar un ejemplo muy intuitivo y representativo. Se puede suponer que se quiere estudiar la situaci´on de unos estudiantes en funci´on de su nota acad´emica, que puede ser del uno al diez. Mediante el proceso de discretizaci´on, el espacio de posibles contextos ser´a dividido en: sobresaliente, notable, bien, suficiente o insuficiente. Usando este enfoque, cada uno de los cinco espacios discretizados ser´a tratado con un algoritmo distinto. Por ello, los estudiantes que tengan entre un siete y un ocho ser´an analizados por un algoritmo y los alumnos que tengan menos de un cinco ser´an estudiados por otro algoritmo ya que pertenecen a otro espacio discretizado. Utilizando esta aproximaci´on, habr´a algoritmos especializados para cada tipo de estudiante, y esto podr´ıa permitir a los algoritmos rendir mejor seg´un el contexto. Las ventajas que ofrece este sistema es que para un gran n´umero de contextos, estos se pueden representar en un intervalo arbitrario, mapear. En cada una de las secciones habr´a un algoritmo especializado en los contextos que haya en dicha secci´on. Adem´as, la metodolog´ıa ser´a parecida al apartado anterior de pocos contextos 6.1. Habr´a una instancia de un algoritmo UCB para cada espacio discretizado. En el ejemplo anterior, un algoritmo se encargar´ıa de los alumnos de sobresaliente, otro de los de notable, otro de los de bien, uno distinto de los de suficiente y un ´ultimo de los de insuficiente. Para discretizar se usa la siguiente funci´on: fS(x) = m´ın(arg m´ın x′∈S|x−x′|). Con esta forma de mapear, cada punto es puesto en una regi´on del espacio discretizado de acuerdo a esta funci´on conocida como la funci´on de mapeo. Gracias este mapeo, cada contexto observado en una ronda t, ser´a ubicado en uno de los contextos discretizados, y para este contexto discretizado, existir´a una instancia del algoritmo UCBSque operar´a exclusivamente en dicha zona discretizada. 35 Con el objetivo de entender correctamente los bandidos contextuales lipschitzianos, hay que exponer una implementaci´on propia, y se profundiza en esta materia. Antes de poder ahondar en la implementaci´on, es imprescindible demostrar que se cumple la condici´on de Lispchitz, y el siguiente apartado se centrar´a en esta cuesti´on. En ´ultimo lugar, se muestra el remordimiento alcanzado para este tipo de bandidos contextuales. El remordimiento obtenido es similar al que alcanzan los bandidos estoc´asticos, pero este bandido contextual lipschitziano permite abordar problemas complejos que, sin usar la condici´on de Lispchitz, no ser´ıan trazables por un bandido multi-brazo. El remordimiento es el siguiente: Teorema 6.2. E[R(T)] ≤T2/3×O(LK log T)1/3. Este remordimiento es seg´un el n´umero de Trondas, el n´umero de Kbrazos y la constante Lispchitz L. 6.2.2. Implementaci´on de Bandidos Contextuales Lipschitzianos del Mercado A continuaci´on, se presenta el desarrollo de la implementaci´on de bandidos contextuales de tipo Lipschitz de acuerdo a las directrices expuestas en el libro de Slivkins. Se proceder´a a detallar el objetivo de esta implementaci´on, la metodolog´ıa para desarrollar esta pr´actica y las conclusiones obtenidas tras realizar este trabajo. En primer lugar, se define cu´al es el fundamento de esta pr´actica. Se trata de un sistema recomendador que utiliza un bandido multi-brazo contextual lipschitziano Este sistema recomendador cuenta con distintas carteras, que son los brazos, cada cartera est´a formada por un porcentaje distinto de acciones y bonos, de manera que hay carteras que tienen un gran porcentaje de bonos mientras que otras tienen casi todo acciones. Se parte de la base de que en el siguiente apartado se analiza y demuestra la condici´on de Lipschitz. Esto aparece en la subsecci´on 6.2.3 donde se demuestra que se cumple dicha condici´on. Dicha secci´on es fundamental para que se pueda plantear el problema ya que debe darse esta condici´on para desarrollar el algoritmo adecuadamente considerando el contexto. En este problema, se considerar´a el contexto del crecimiento del mercado y la tasa de inter´es. Se aplica una l´ogica sencilla e intuitiva para entender el funcionamiento de este tipo concreto de bandidos. El mercado ser´a reducido a dos variables macroecon´omicas: el crecimiento del mercado y la tasa de inter´es, y se jugar´a con dichas variables para explicar este modelo. En un mercado real est´a claro que afectan innumerables variables al precio de activos financieros como bonos o acciones. Sin embargo, al prescindir de otras variables, es posible centrarse en un modelo simulado dependiente ´unicamente del crecimiento del mercado y la tasa de inter´es para poner en pr´actica el objetivo de este cap´ıtulo: la discretizaci´on para desarrollar bandidos contextuales tipo Lispchitz. Respecto a las caracter´ısticas del mercado financiero simulado, hay dos variables que son la tasa de inter´es y el crecimiento del mercado, y existen dos tipos de activos: los bonos y las acciones. Se considerar´a que los bonos son activos financieros que ofrecen poca rentabilidad. Se puede ganar poco dinero con ellos, pero su principal ventaja es que ante un decrecimiento del mercado no pierden tanto valor como las acciones. Debido a esto, es m´as interesante comprar bonos si el mercado est´a cayendo, frente a acciones. Adem´as, su rentabilidad est´a ligada a la tasa de inter´es que fijan los bancos centrales. Una vez entendido esto, es posible comprender que ante una buena tasa de inter´es y un decrecimiento del mercado es bastante mejor opci´on comprar bonos que comprar acciones ya que a pesar de que no reporten tantos beneficios, son opciones m´as seguras que pueden ser m´as beneficiosas en estas situaciones, o contextos. Por otro lado, las acciones dependen mucho de la situaci´on del mercado. En un mercado en expansi´on, o en crecimiento, se puede suponer que las acciones van a subir mucho y ofrecen rentabilidades muy altas. Al contrario que los bonos, que ofrecen ganancias m´ınimas, las acciones proporcionan beneficios muy buenos. L´ogicamente, si el mercado cae, las acciones perder´an mucho valor porque al igual que dependen mucho para ganar, tambi´en bajan mucho si el mercado cae, por eso se dice que fluct´uan mucho. Por ello, ante un crecimiento al alza del mercado es m´as interesante comprar acciones ya que un bono no otorgar´a apenas beneficios. Pero con un mercado en decadencia, las acciones pueden hacer perder mucho dinero y los bonos son valores m´as seguros. Una vez explicado esto, ya est´a clara la idea de que con una buena tasa de inter´es son convenientes los bonos pero que si el mercado crece las acciones son muy tentadoras. Surge entonces la pregunta de cu´al es la mejor estrategia para elegir una cartera con m´as bonos o m´as acciones seg´un el contexto: mercado y tasa de inter´es. Estar´an presentes los siguientes tipos de cartera a elegir para que el algoritmo pueda jugar con las carteras que mejor le parezcan seg´un las condiciones del mercado. 36 Brazo 1: 0 % de acciones y 100 % de bonos. Brazo 2: 25 % de acciones y 75 % de bonos. Brazo 3: 50 % de acciones y 50 % de bonos. Brazo 4: 75 % de acciones y 25 % de bonos. Brazo 5: 100 % de acciones y 0 % de bonos. Estas cinco carteras van a permitir buscar la opci´on ´optima conforme al contexto que haya. Como ya se ha explicado, el crecimiento del mercado afecta muy positivamente a las acciones. Por eso, con un crecimiento alto del mercado se elegir´a siempre el brazo 5, ya que los otros brazos a pesar de que ganen dinero tendr´an un remordimiento muy alto. Igualmente, ante un mercado en decrecimiento y una tasa de inter´es alto, el brazo uno reportar´a grandes recompensas y el resto de brazos tendr´an un remordimiento significativo. Ahora bien, la cuesti´on que se debe plantear es qu´e brazo usar para todos los dem´as contextos, en los que no haya una tasa de inter´es excesivamente alto ni un crecimiento de mercado exagerado. Pues ese es el coraz´on de este problema, la elecci´on de la mejor cartera respecto a un contexto. Una vez resaltada esta idea, debe ser abordada la funci´on de recompensas. El mecanismo de recompensas es el siguiente: se calcula una rentabilidad esperada para las acciones y otra para los bonos en funci´on de las condiciones del mercado, contexto. Posteriormente, se obtiene la rentabilidad de la cartera, brazo, en funci´on del porcentaje de bonos y de acciones, que suman uno. Es decir, con el brazo 4, se multiplica la rentabilidad de las acciones por el 75 % y la rentabilidad de los bonos por el 25 %. As´ı, se puede saber cu´al es la rentabilidad total resultante de la distribuci´on de bonos-acciones. Por ´ultimo, se normalizar´a y crear´a una distribuci´on normalizada usando una varianza asociada a la cartera, que se calcula de acuerdo al peso de las acciones y bonos en dicha cartera. Luego se obtendr´a el valor medio usando dicha desviaci´on y se coge un valor aleatoriamente. Dicho valor medio ser´a normalizado entre 0 y 1 para ver la rentabilidad esperada respecto al brazo usado en un contexto dado. Las recompensas se representan del siguiente modo: las recompensas est´an normalizadas entre 0 y 1. Se parte de un valor de 0.5 como recompensa. De este modo, una recompensa de 0.5 significa que ni se ha ganado ni perdido dinero. Si hay una recompensa menor de 0.5 reflejar´a que se ha perdido dinero con la cartera. Este suceso se podr´a repetir en numerosas ocasiones ya que hay situaciones en las que es muy f´acil perder dinero. Por el contrario, si se da una recompensa mayor de 0.5, se habr´ıa ganado una rentabilidad con la cartera elegida. Si se obtiene una recompensa de 1, la inversi´on se habra multiplicado por dos, mientras que si se llega a 0, se habr´ıa perdido la inversi´on completamente. Una vez definido el contexto y los brazos, hay que explicar el funcionamiento de este bandido contextual. Este sistema recomendador elige una cartera para cada inversor, y lo hace para Tinversores, es decir, durante Trondas. Cada inversor tiene un contexto diferente, generado aleatoriamente, un mercado que var´ıa desde un 10 % a un −10 % y una tasa de inter´es de 0 hasta 8 %. Estos Tinversores se generan aleatoriamente entre estos rangos y en este caso, se utilizan 10000 inversores para ver el desarrollo real del bandido contextual recomendando carteras y obteniendo recompensas para distintos inversores. Gracias a que se cumple la condici´on de Lipschitz, se pueden discretizar los contextos en un espacio contextual, o mapa, para este bandido contextual, donde las coordenadas yson el crecimiento del mercado y las xla tasa de inter´es. Habr´a un espacio contextual dividido en cuadr´ıculas, donde hay diez filas y diez columnas en funci´on de estas dos variables. Usando esta discretizaci´on se reparte el espacio de contextos en 100 contextos discretizados y para cada uno hay una instancia del algoritmo UCB1, o tambi´en llamado UCB, de manera que dicha instancia se encarga de explorar y explotar una ´unica regi´on del espacio contextual. De esta manera, se utiliza la discretizaci´on de una forma muy visual ya que es posible imaginarse un mapa divido en cien porciones; tambi´en sirve para poder plasmar un gr´afico con los resultados para cada regi´on. Es fundamental se˜nalar c´omo aprender´a cada una de las instancias del algoritmo UCB. Hay que tener en cuenta que cada una de las instancias ´unicamente se utiliza en uno de los 100 contextos discretizados, pero no se usa en ning´un otro contexto discretizado. En cada ronda una instancia decide qu´e brazo, o cartera, recomendar y sabe la recompensa que ha obtenido para ese brazo. Consecuentemente, cada instancia del UCB solo aprender´a cuando sea llamada. Una instancia es llamada cuando se de un contexto en la ronda tque encaje en su contexto discretizado, esta instancia del UCB har´a una recomendaci´on para este contexto y aprender´a de la recompensa obtenida, pero el resto de instancias no sabr´an ni el brazo que ha elegido ni su recompensa. Por ello, debe haber el suficiente n´umero de rondas para que cada instancia aprenda de sus acciones y elabore su 37 estrategia de exploraci´on-explotaci´on de acuerdo a lo que ha aprendido con sus decisiones anteriores. Con el uso de estos bandidos lipschitzianos se estudia un caso de uso distinto y se saca partido a discretizar con un n´umero alto de contextos, 100 en este caso. Adem´as, ser´a posible representar los posibles contextos en un mapa, donde cada inversor ser´a tratado por una instancia de UCB. Dicha instancia conoce a la perfecci´on los valores en los que se encuentra este inversor, tanto inter´es como mercado y as´ı conoce la exploraci´on y explotaci´on en esa zona entre brazos, y aprende a explotar el brazo con el respectivo porcentaje de acciones y bonos necesarios. Por esto, este sistema recomendador aplica esta condici´on para aprovechar los contextos. Al realizar esta implementaci´on, se observa que el algoritmo ofrece muy buenos rendimientos y aprende a usar el brazo necesario para cada contexto mediante las instancias de UCB (que hay una para cada contexto discretizado). Adem´as, se puede ver que los bonos son menos variables en la f´ormula calculada y por ello, en las zonas de inter´es alto se ven muy buenos rendimientos. Este bandido contextual rinde bastante bien seg´un los resultados obtenidos. Con la discretizaci´on y el uso de bandidos contextuales lipscthizanos, el algoritmo puede explotar cada zona del contexto discretizado con una instancia distinta, que aprender´a m´as r´apidamente a operar en un contexto determinado, con unos valores de tasa de inter´es y crecimiento del mercado concretos. Estas instancias sabr´an cu´al es el mejor brazo a aplicar en su propia regi´on y esto permite optimizar un problema gracias a la discretizaci´on. Tras haber expuesto los pilares de este sistema, se mostrar´an los resultados obtenidos, en dos gr´aficas que son fruto de la implementaci´on realizada en Python. Como se puede apreciar, los resultados son positivos y el algoritmo es capaz de no perder dinero mediante la elecci´on del mejor brazo seg´un el contexto, y tambi´en mejora con el tiempo y se contempla esta curva de aprendizaje y su mejor´ıa. Ahora, se observar´an los resultados obtenidos por medio de unos gr´aficos que ilustran c´omo se desenvuelve el bandido. Figura 8: Recompensas medias y remordimientos medios con bandidos contextuales lipschitzianos. En estos gr´aficos aparecen las recompensas promedias obtenidas a lo largo de 10000 rondas, y, en contraposici´on, tambi´en se ve el remordimiento que es lo que se deja de ganar. Cada una de las rondas representa a un inversor, y se observa un contexto diferente. Tal y como se ha detallado anteriormente, las recompensas reflejan que el algoritmo es capaz de mantener el dinero si la recompensa es igual a 0.5. Por otro lado, si la recompensa es superior a 0.5, el algoritmo est´a siendo capaz de obtener una rentabilidad eligiendo una buena cartera. En este caso, se ve que el algoritmo empieza en las primeras rondas con una variaci´on muy alta de recompensas y ya a partir de la ronda 2000, es capaz de elegir los mejores brazos para siempre obtener una rentabilidad (positiva) de la cartera elegida. De hecho, solo al principio obtiene una recompensa media negativa y perder´ıa dinero invertido. Esto significa que conforme va aprendiendo, es capaz de discernir qu´e cartera usar seg´un el contexto para obtener beneficios. La gr´afica 8 muestra para una determinada ronda t, la recompensa media para esta ronda. As´ı se puede ver c´omo var´ıa la recompensa media obtenida. Tambi´en se expone el remordimiento medio, que permite observar 38 Figura 9: Mapa de calor para cada contexto discretizado. si el algoritmo va obteniendo mejores recompensas conforme pasa el tiempo. Se puede apreciar la mejora continua en el algoritmo y que aprende a lo largo de las rondas, y siempre proporciona recompensas positivas, esto es mayores de 0.5 a partir de la ronda 2000. Se observa lo mismo en el remordimiento que va disminuyendo conforme avanza la partida. Por lo tanto, es posible deducir que el algoritmo que ha sido desarrollado aprende a usar adecuadamente sus brazos y es capaz de mantener siempre la rentabilidad por encima del 0.5 para no perder dinero, y mejora con el tiempo. Esto es muy importante, ya que el algoritmo opera en situaciones muy negativas como un decrecimienoto del mercado de −7 %, y en esta situaci´on lo m´as probable es que con la mayor´ıa de brazos el bandido pierda dinero, de hecho, as´ı se observa en las primeras rondas donde hay rentabilidades de 0.3, lo que supone que en esas rondas el algoritmo pierde aproximadamente la mitad de su inversi´on. Esto contrasta con su evoluci´on y su aprendizaje que queda reflejado en las curvas de recompensas y remordimiento, el bandido es capaz de rendir en cualquier contexto por muy negativo que sea, y ofrece recompensas positivas, por lo que su actuaci´on es brillante. Esta segunda imagen 9 es muy interesante, ya que se observan las recompensas medias obtenidas en cada contexto discretizado. Adem´as, permite al lector ver una imagen visual de c´omo se representa el espacio contextual seg´un el crecimiento del mercado y el inter´es. En este mapa se ven las 100 secciones, o contextos discretizados, cada uno de estos es tratado por un algoritmo UCBSen funci´on de la tasa de inter´es y el crecimiento del mercado. Los resultados muestran lo ya expuesto a lo largo de esta secci´on. Con un crecimiento del mercado muy positivo, se pueden alcanzar recompensas muy altas debido a la volatilidad de las acciones, que, hay que recordar que pueden subir mucho de precio. Por el contrario, ante una situaci´on de una alta tasa de inter´es, las recompensas simplemente se mantienen o se gana un peque˜no porcentaje. Este gr´afico ilustra muy bien la l´ogica de c´omo funciona el mercado financiero y arroja luz acerca de las recompensas obtenidas por el algoritmo. El uso de un mapa de calor es una alternativa id´onea en este caso porque es posible entender este modelo de manera intuitiva. Adem´as, la discretizaci´on de los contextos aparece representada en este mapa de calor con sus recompensas asociadas y se puede intuir c´omo de positivo va a ser el mercado, o cu´antas probabilidades habr´a de obtener una recompensa positiva (ganancias) seg´un la informaci´on contextual. 39 Figura 10: Evoluci´on de las recompensas y remordimientos promedios si Tes aumentado. Por ´ultimo, se pone el foco en la evoluci´on de las recompensas con m´as rondas Tpara analizar mejor este algoritmo y su desempe˜no en el mercado. Se puede ver en la figura 10 que se estanca el crecimiento de las recompensas promedias. A pesar de ello, s´ı que es posible apreciar que el crecimiento de las recompensas medias y tambi´en el decrecimiento del remordimiento promedio, mejora conforme van pasando las rondas, y confirma este aprendizaje por parte de el algoritmo de bandidos contextuales tipo Lipschitz. Tras explicar todo esto, se puede concluir acertadamente que el algoritmo aprende a usar carteras con menos o m´as acciones en funci´on del contexto con el objetivo de maximizar su recompensa cumpliendo en todo momento con la condici´on de Lipschitz. Cabe se˜nalar que los resultados son muy interesantes porque permiten ver c´omo para un gran n´umero de contextos, gracias al cumplimiento de la condici´on de Lipschitz se puede conseguir un bandido contextual correcto que puede discretizar contextos. Esta implementaci´on ha cumplido correctamente su funci´on de exponer un problema que puede ser resuelto con los bandidos contextuales lipschitzianos y su proceso de discretizaci´on. 6.2.3. Demostraci´on de Lispchitz para Bandidos Contextuales Lipschitzianos A continuaci´on, se presenta una explicaci´on de la demostraci´on de que la funci´on de recompensa cumple con la condici´on de Lipschitz, utilizando el crecimiento del mercado y la tasa de inter´es como las variables del contexto. Se considerar´a que la variable xrepresenta la tasa de inter´es y la variable yel crecimiento del mercado. Debe recordarse que en este problema se da un contexto en cada ronda, que se compone de las variables xey. Hay una recompensa que representa la rentabilidad de una cartera. Como ya se ha profundizado en cada detalle de esta implementaci´on, ahora lo importante es demostrar que se cumple la condici´on de Lipschitz en este caso. En el caso de uso del mercado, se presupone que las recompensas vienen determinadas por la tasa de inter´es y el crecimiento del mercado. En este escenario de mercado, se asume que las recompensas est´an intr´ınsecamente ligadas a la tasa de inter´es y al crecimiento del mercado. Para simplificar la explicaci´on, se postula que ambas variables, ponderadas por dos coeficientes distintos (ayc), que podr´ıan representar la rentabilidad de una cartera. Dicha funci´on de recompensas es la siguiente: R(x, y) = a∗x+c∗y, En este caso, se utiliza la expresi´on R(x, y) para denotar las recompensas. De este modo queda latente que las recompensas vienen determinadas por estas dos variables pertenecientes al contexto. Para demostrar que esta funci´on cumple con la condici´on de Lipschitz, debe demostrarse que existe una constante Ltal que: 40 algoritmos, es minimizar el tiempo de viaje en cada ronda mediante la mejora de toma de decisiones. Esto significa que tratar´a de elegir el camino que reduzca el tiempo de viaje y, consecuentemente, mejore las recompensas. Debido a esto, al existir retroalimentaci´on total, es un algoritmo que no se puede comparar directamente con los otros dos. Ni GPMW, ni cGPMW tienen retroalimentaci´on total. El algoritmo Hedge conoce toda la informaci´on posible. Tener retroalimentaci´on total no es comparable con conocer el contexto. Mientras que saber el contexto es una informaci´on que podr´ıa ser considerada ´util, la retroalimentaci´on total es equivalente a conocer toda la informaci´on de la red. A pesar de que el Hedge juega un ´unico brazo en cada ronda, es como si jugar´a todos. Por esto, dicho algoritmo servir´a de introducci´on y ejemplo pero a la hora de comparar algoritmos, el estudio se centrar´a en los dos siguientes. Antes de abordar este algoritmo en profundidad, hay que se˜nalar una premisa fundamental de los bandidos contextuales que s´ı cumple el cGPMW pero no el algoritmo actual. En un bandido contextual, el algoritmo observa el contexto xtde la ronda antes de seleccionar un brazo. Esta es la clave que debe ser entendida y asimilada. Si el algoritmo tiene en cuenta el contexto observado antes de elegir una acci´on ser´a un bandido contextual. Debido a este motivo, el algoritmo Hedge, no es un bandido contextual, ya que no usa el contexto (capacidades) para seleccionar un camino. En cambio, el algoritmo Hedge elige en funci´on del tiempo, es decir, toma el camino que menos tiempo tarde porque le reportar´a mejores recompensas. Por otro lado, aunque Hedge no tenga en cuenta el contexto para decidir un camino, s´ı lo utiliza (adem´as de las ocupaciones de las carreteras y el vector de estrategias) para calcular el tiempo de viaje para cada brazo, y obtener la retroalimentaci´on total. Una vez que han sido mencionados los aspectos m´as relevantes, se expone el algoritmo para despu´es ahondar en sus caracter´ısticas exhaustivamente. Algoritmo 7.12 Algoritmo Hedge en Juego Contextual. 1: Al inicializar: Se establece una tasa de aprendizaje γ, se inicializan los pesos a 1, se calculan la recompensa m´axima y la recompensa m´ınima. Se obtien los Kcaminos que puede tomar. 2: for cada ronda t= 1,2, . . . do 3: Se juega un brazo aelegido aleatoriamente en funci´on del vector pesos. 4: Se actualiza el vector pesos:∀a∈A:pesosa←pesosa·eγ·(−la). 5: end for Como se puede observar, antes de la simulaci´on el algoritmo Hedge se encarga de inicializar los par´ametros necesarios. Primero se inicializa a uno el valor de los pesos de todos los brazos. La variable pesos representa la importancia de cada brazo. La probabilidad de dicho brazo se calcula dividiendo su peso entre la suma de todos los pesos. Un peso mayor se traducir´a en m´as posibilidades de que ese brazo sea seleccionado. Como todos parten con un peso de 1, todos tienen a priori las mismas posibilidades de ser elegidos. Una probabilidad alta de un brazo A supone que se elegir´a seguramente antes que un brazo B. Estas probabilidades cambian a lo largo de la simulaci´on por medio de la funci´on actualizar. Despu´es, establece un valor a γ, que representa la tasa de aprendizaje y es arbitraria. Su oficio es actualizar en menor o mayor cantidad los pesos tras haber obtenido una recompensa en la actualizaci´on. Como se encuentra en una exponencial en negativo, se puede razonar que una γalto influir´a menos en el cambio de los pesos mientras que una γde un valor menor influir´a m´as en los pesos. Por defecto, toma el siguiente valor para que haya un equilibrio en esta variable entre el n´umero de brazos y el n´umero de rondas: γ=r8 log(K) T Por ´ultimo, se obtienen los valores de las recompensas m´aximas y m´ınimas que se calculan antes de la simulaci´on, estos valores permitir´an escalar las recompensas en la actualizaci´on y representan el valor m´aximo y el m´ınimo que puede conseguir un agente con cualquier contexto y cualquier brazo. Se calculan haciendo m´ultiples simulaciones de aproximaci´on con todos los contextos y brazos para obtener el m´aximo y el m´ınimo. Dichas aproximaciones se realizan antes de la simulaci´on real, y ayudan a conseguir estos valores. Tambi´en se definen los brazos o caminos que puede tomar este agente, y en cada ronda elegir´a entre uno de estos brazos. Tras desarrollar esto, de este algoritmo, aparte de la inicializaci´on, deben diferenciarse dos funciones claves que realiza: la elecci´on de un brazo y la actualizaci´on. La selecci´on del brazo es un proceso muy sencillo y l´ogico 47 de acuerdo a la variable pesos y su probabilidad, siendo: probabilidada=pesoa P∀apesoa Se elige un brazo aleatoriamente en funci´on de los pesos de cada uno de los brazos. Esto se realiza al principio de la ronda y, tras jugar un brazo, se obtiene una recompensa. A ra´ız de esta recompensa, tiene lugar el segundo punto vital que es la actualizaci´on. La actualizaci´on es el eje de este algoritmo ya que se encarga de actualizar el vector pesos y afecta directamente en la selecci´on de brazos. B´asicamente lo que hace la actualizaci´on es obtener una recompensa para cada brazo y recalcular el vector pesos. Esto se har´a de la siguiente forma: A trav´es de la funci´on de la red se calcula el tiempo esperado para cada uno de los brazos. Hay que recordar que para calcular el tiempo esperado de cada brazo se usan las capacidades, las ocupaciones totales y el vector de estrategias. Posteriormente, se usan las recompensas m´ınimas y m´aximas para que la recompensa calculada sea menor que la recompensa m´axima y mayor que la recompensa m´ınima, luego se normaliza para que la recompensa este entr´e 0 y 1, y despu´es se calcula las p´erdidas, para cada brazo la, que son igual a uno menos la recompensa, es decir, las p´erdidas son lo que se deja de ganar. Para actualizar los pesos con las p´erdidas de cada brazo se aplicar´a la siguiente f´ormula usando γcomo se ha mencionado, y tambi´en las p´erdidas conseguidas, se calculan los pesos para cada brazo: ∀a∈A:pesosa←pesosa·eγ·(−la). La variable larefleja las p´erdidas del brazo aen esa ronda t. Mediante esta f´ormula es posible observar c´omo el peso de los brazos que obtengan peores recompensas disminuir´a, mientras que aquellos brazos que obtengan buenas recompensas mantendr´an valores altos y, por consiguiente, ser´an m´as veces elegidos en rondas futuras. El funcionamiento de los pesos se puede explicar con un ejemplo. Hay que imaginar que existen 5 brazos que representan las mejores rutas o caminos para un agente. Pasada una ronda t, el agente jugar´a el brazo uno, pero como hay retroalimentaci´on total, sabr´a cu´anto ha tardado usando su camino y cu´anto habr´ıa tardado usando los otros cuatro caminos. Si se supone que el camino que ha elegido ha sido el que m´as tiempo tarda, se actualizar´a el vector pesos de acuerdo a esta l´ogica. El brazo uno, que es el elegido, y el que ofrece peor recompensa ya que tarda m´as tiempo, disminuir´a su peso. Esto provocar´a que el brazo uno tendr´a un peso menor en la siguiente ronda t+ 1, y habr´a menos probabilidades de elegir este brazo. Por otra parte, el resto de brazos aumentar´an su peso respecto al brazo uno. Esta estrategia permite al algoritmo penalizar los caminos que sean lentos y tengan malas recompensas y premiar los caminos r´apidos que las tengan buenas. De este modo, a lo largo de las rondas, tras repetir esta actualizac´on de los pesos se acabar´an teniendo pesos altos en los caminos que sean m´as r´apidos mientras que los caminos m´as lentos tendr´an pesos menores. As´ı, el algoritmo tender´a a elegir caminos con pesos altos, que le retornar´an mejores recompensas a la larga. Y usando esta estrategia en el largo plazo el algoritmo mejorar´a sus recompensas. No obstante, es imprescindible considerar que dicho algoritmo Hedge no considera el contexto, porque trata de elegir los mejores caminos pero no discierne si en una ronda hay mucha o poca congesti´on en un camino. Simplemente el algoritmo recibe, con retroalimentaci´on total, el tiempo que tarda en usar cada camino y seg´un los tiempos de viaje, que var´ıan cada ronda seg´un la ocupaci´on (contexto), se actualizar´a. Es decir, este algoritmo realizar´a actualizaciones a su vector pesos en funci´on del tiempo de viaje de cada camino, y la recompensa asociada a este tiempo de viaje, y sin diferenciar entre contextos distintos cada ronda, el algoritmo mantendr´a con altos pesos los caminos m´as r´apido a lo largo de las rondas. Es decir, los caminos que mejores recompensas medias den ser´an m´as elegidos. A pesar de que este algoritmo no considera el contexto, es el algoritmo que mejores rendimientos ofrece ya que tiene retroalimentaci´on total. Al contrario que los otros algoritmos, este sabe en realidad cu´ales son las p´erdidas y recompensas para todos los brazos como si los hubiese elegido. Esta es una diferenciaci´on muy importante ya que aunque no tiene en cuenta el contexto, se podr´ıa decir que este algoritmo juega con otras reglas y alcanza menores remordimientos que el resto. Debido a esto, el an´alisis se centra en la comparativa entre el GPMW y el cGPMW para ver de qu´e manera puede influir la informaci´on contextual. Por otro lado, el algoritmo Hedge es muy importante ya que adem´as de enriquecer el trabajo y se muestra un bandido multi-brazo con retroalimentaci´on total en un caso real, tambi´en 48 se explica como punto de partida para familiarizarnos con el funcionamiento de estos algoritmos en la red. Tambi´en hay que se˜nalar que es el algoritmo usado por defecto por los jugadores que no son controlados por el algoritmo elegido (GPMW o cGPMW) en la simulaci´on, por lo que es imprescindible para poder desarrollar adecuadamente este programa. 7.4.2. Algoritmo GPMW La investigaci´on ahora se centra en el algoritmo GPMW. A pesar de no ser un algoritmo estrictamente contextual, s´ı que considera las capacidades totales de las carreteras. Por esto, se puede afirmar que estudiar dicho algoritmo va a aportar mucho valor a este trabajo y va a enriquecer los conocimientos obtenidos acerca del desarrollo de estos bandidos. El algoritmo GPMW va a ser comparado con el cGPMW que s´ı es estrictamente contextual. Una vez que ha sido aclarado este aspecto, se puede desarrollar exhaustivamente el funcionamiento de este bandido. A diferencia del algoritmo Hedge, este algoritmo no tiene retroalimentaci´on total, solo conoce el coste de su brazo elegido. Sin embargo, el algoritmo GPMW simula retroalimentaci´on total con costes falsos. En el primer algoritmo, Hedge, se calculaba con la red la recompensa de cada brazo dado el contexto de ese momento. En el algoritmo de este apartado la retroalimentaci´on total es simulada con predicciones, no con resultados reales como lo hac´ıa el algoritmo Hedge. El aspecto de las predicciones es vital para entender este algoritmo. Este algoritmo realiza predicciones para simular las recompensas que esperar´ıa obtener para todos los brazos en la ronda en la que se encuentre. Gracias a esta t´ecnica, el algoritmo actualizar´a los pesos que otorga a cada brazo seg´un lo buenas que sean sus predicciones. Hay un peso por cada brazo y los brazos con mejores rendimientos, o predicciones ahora, tendr´an pesos mayores por lo que tender´an a ser elegidos. El funcionamiento de los pesos es similar al apartado anterior excepto por una cuesti´on. Una diferencia a tener en cuenta respecto al algoritmo Hedge es la forma de calcular los pesos. En cada ronda el algoritmo actualiza los pesos de acuerdo a la tasa de aprendizaje y lo har´a con las p´erdidas acumuladas. ∀a∈A:pesosa←pesosa·eγ·(−La). En este caso, est´a utilizando las p´erdidas acumuladas en el exponente que multiplica los pesos. Dichas p´erdidas acumuladas las representa como La. Anteriormente, usaba las p´erdidas de la ronda, pero este algoritmo tiene en cuenta las p´erdidas de todas las rondas anteriores. Esto se debe a que en Hedge los pesos se actualizan en funci´on de la p´erdida de la ronda actual porque se supone que la distribuci´on de probabilidad de las acciones ´optimas es relativamente estable de una ronda a otra. Por eso, con las p´erdidas de la ronda actual se considera que es suficiente. Por otra parte, el algoritmo GPMW considera la p´erdida acumulada teniendo en cuenta las rondas anteriores porque su estrategia no depende solo de las observaciones de p´erdidas de la ronda actual, sino tambi´en las observaciones previas, ya que el GPMW parte de la premisa de que la distribuci´on de probabilidad de las acciones ´optimas puede cambiar a lo largo del tiempo. Una vez que se ha mencionado estos aspectos se mostrar´a el esquema que sigue este algoritmo, y despu´es hay una explicaci´on detallada de cada paso: Algoritmo 7.13 Algoritmo GPMW en Juego Contextual. 1: Al inicializar: Se establece una tasa de aprendizaje γ, se inicializan los pesos a 1, se calculan la recompensa m´axima y la recompensa m´ınima. Se obtienen los Kcaminos que puede tomar. Se inicializan el historial (ocupaciones totales y unidades enviadas) y el historial de recompensas. 2: for cada ronda t= 1,2, . . . do 3: Se juega un brazo aelegido aleatoriamente en funci´on del vector pesos. 4: Se actualizan el historial y el historial de recompensas con el brazo ay su recompensa r. 5: Se simula la retroalimentaci´on total: ∀a∈A:rsimulada(a) = f(historiales, ocupacionest) 6: Se actualiza el vector pesos:∀a∈A:pesosa←pesosa·egamma·(−La) 7: end for Lo primero que realiza este algoritmo es una inicializaci´on muy similar a la del algoritmo anterior pero a˜nadiendo nuevos atributos porque la metodolog´ıa utilizada es m´as compleja. Se obtienen la tasa de aprendiza49 je, γ, las recompensas m´aximas y m´ınimas y los Kcaminos al igual que antes. Tambi´en el algoritmo tendr´a dos piezas cruciales: el historial y el historial de recompensas de rondas pasadas. Es decir, en una ronda t, tendr´a los historiales hasta esa ronda de todas las anteriores. Ahora se ver´a qu´e valor tienen y para qu´e sirven estos atributos. Por un lado, el historial de recompensas refleja la recompensa obtenida en cada una de las rondas anteriores. Por otro lado, el historial almacena dos vectores en cada ronda. Primero almacena la estrategia jugada por el brazo elegido ay los carreteras que usa ese brazo. Tambi´en guarda las ocupaciones totales de las carreteras que necesita este camino, brazo, elegido. En definitiva, el historial contendr´a la informaci´on de las carreteras jugadas por el jugador en una ronda, tanto la ocupaci´on total de esa carretera, como las paquetes que el brazo env´ıa por esas carreteras, de acuerdo a su camino escogido. Usando estos historiales, y las ocupaciones dada la ronda en la que se encuentre, podr´a calcular las recompensas simuladas de la siguiente manera, tal y como se detalla en [12]: En primer lugar, el algoritmo actualiza los historiales: el historial de recompensas con la nueva recompensa de la ronda ty el historial que refleja las ocupaciones totales para las carreteras del camino aelegido y los paquetes enviados del camino aelegido. Una vez hecho esto, usa un modelo de regresi´on gaussiana y lo entrena para las rondas anteriores, siendo la variable Xel historial y la variable independiente el historial de recompensas. Posteriormente calcula las otras ocupaciones, que son las ocupaciones totales menos las que requiere el jugador, para saber cu´ales son los paquetes enviados por todos los dem´as jugadores, a excepci´on de el propio agente. Despu´es, este algoritmo obtiene para cada brazo los paquetes que tiene que enviar para cada carretera, y junto con otras ocupaciones, lo utiliza como Xpara predecir con la regresi´on gaussiana, que ya ja sido entrenada, y obtiene una predicci´on de la recompensa para cada brazo y la varianza de esta predicci´on. Con un valor de beta, β, de 0.5, calcula el l´ımite superior de confianza con la predicci´on obtenida para cada brazo: UCBa= ˆµa+βtˆσa. La varianza la proporciona el modelo de regresi´on gaussiana. El algoritmo GPMW actualiza el vector pesos usando el vector UCB al igual que para el algoritmo Hedge. Las recompensas ser´an el vector UCB para todos los brazos, comprueba que est´an dentro de la recompensa m´axima y recompensa m´ınima para despu´es escalarlas. Calcula las p´erdidas para cada brazo la, haciendo la diferencia entre uno y las recompensas escaladas. Actualiza con las p´erdidas acumuladas que ten´ıa ya de otras rondas: La=La+lapara cada brazo a. Usa Lay modifica el vector pesos: ∀a∈A:pesosa←pesosa·eγ·(−La). A continuaci´on, se detallar´a qu´e es la regresi´on gaussiana y qu´e utilidad tiene en esta implementaci´on. La regresi´on gaussiana es un m´etodo de aprendizaje autom´atico que proporciona una forma de inferir una funci´on desconocida a partir de datos de entrenamiento ruidosos. Es un modelo de regresi´on no param´etrico, lo que significa que puede adaptarse a datos de cualquier forma sin tener una forma predefinida. Por otro lado, en el contexto de la regresi´on gaussiana, un kernel (o funci´on de covarianza) es una funci´on que mide cu´anto se parecen dos puntos. En otras palabras, define el grado de correlaci´on o similitud entre dos puntos en el espacio de entrada. En la implementaci´on original, usar el modelo de regresi´on gaussiana (con el kernel) permite explotar la similitud entre dos contextos ya que se mide la similitud entre los puntos. De este modo, un bandido que considere el contexto como el siguiente algoritmo, cGPMW, consigue alcanzar muy buenas recompensas al sacar partido de la regresi´on gaussiana para mismos contextos y captura muchas formas diferentes de relaciones entre datos de entrada y salida. Respecto a dicho modelo de regresi´on gaussiana, cabe se˜nalar que en Python se usa la librer´ıa GPy mientras que en la adaptaci´on que ha sido implementada en C++, se usa “rvm regression trainer” de la biblioteca dlib. Esto es un modelo de regresi´on de vectores de soporte (RVM) que permite entrenar dicho modelo para que pueda realizar predicciones para obtener las recompensas simuladas. Para el modelo RVM no ha sido necesario utilizar el kernel, la funci´on de covarianza porque el modelo de regresi´on de vectores utilizado no permite pasarle por par´ametro un kernel. En cualquier caso, este algoritmo GPMW, usa un modelo de aprendizaje autom´atico, un modelo de regresi´on, para predecir las recompensas de todos los brazos y simular retroalimentaci´on total. Por ello, la regresi´on juega un rol clave para simular las predicciones de cada brazo, ya que en funci´on de estas predicciones se actualizan los pesos de cada brazo y, en consecuencia, se juegan m´as aquellos brazos que tengan mejores predicciones. 50 Esto se puede entender con un ejemplo. Si hay una situaci´on en la que dada una ronda tse elige un brazo a, el algoritmo actualizar´ıa los historiales para entrenar el modelo con toda la informaci´on hasta t, que se incluye tambi´en. El algoritmo har´ıa predicciones para los 5 brazos que tiene, y si el modelo de regresi´on predice una muy buena recompensa para el brazo 2 frente al resto de brazos, el peso del brazo 2 aumentar´a frente a los dem´as brazos, y ser´a m´as probable elegir el brazo 2 a partir de la siguiente ronda. Las predicciones definen cu´ales ser´an los brazos m´as utilizados ya que modificar´an los pesos de los brazos en cada ronda. Si las predicciones afectan mucho o poco para cambiar el peso de un brazo depender´a del γ, o tasa de aprendizaje, (al igual que el Hedge). 7.4.3. Algoritmo cGPMW Por ´ultimo, se explica el algoritmo m´as complicado pero tambi´en m´as eficaz. Este es el ´unico algoritmo contextual de los tres. Dicho algoritmo es una extensi´on o mejora del algoritmo GPMW, y hay que tener en cuenta que se encuentran muchas similitudes entre estos dos algoritmos. Adem´as, el peso de los brazos se actualizar´a usando el vector pesos al igual que lo hacen los otros dos algoritmos. Por ello, este algoritmo trabajara con nomenclatura similar as´ı como con conceptos desarrollados en las subsecciones anteriores del algoritmo Hedge y el algoritmo GPMW. Para empezar con el algoritmo cGPMW, se comienza explicando porqu´e es el ´unico bandido contextual. A diferencia de los otros dos, este algoritmo observa el contexto antes de tomar una decisi´on respecto a qu´e acci´on quiere jugar. Por ello, tiene una nueva estructura, observa el contexto y calcula una estrategia antes de seleccionar la acci´on. Esta funci´on de calculo de estrategia le permite considerar el contexto para elegir el mejor brazo de acuerdo al contexto vigente. El c´alculo de estrategia es algo similar a lo que hace el algoritmo GPMW cuando simula la retroalimentaci´on total. No obstante, el algoritmo cGPMW computa su estrategia teniendo en cuenta el contexto y realizando las operaciones de manera diferente. La principal idea de este algoritmo contextual es utilizar el contexto para optimizar las recompensas. Su fundamento se basa en que un agente podr´a mejorar las acciones jugadas para un mismo contexto si se repite durante el tiempo de manera que aprender´a c´omo elegir adecuadamente cada contexto. Esto es lo que se conoce en la teor´ıa de juegos contextuales como que en un juego contextual d´onde contextos y acciones similares probablemente produzcan recompensas parecidas. El agente tratar´a de explotar estas situaciones similares con el objetivo de maximizar sus recompensas mediante el aprendizaje de que brazo es adecuado en cada situaci´on o contexto. Esto se entiende mejor con un ejemplo. Hay que recordar que los contextos representan las capacidades de las carreteras. Se supone un caso muy sencillo, donde hay dos contextos: un contexto si hace un d´ıa con un tiempo soleado y otro si nieva. Si nieva las carreteras reducen su capacidad. La primera vez que nieva el agente sabr´a que las capacidades de la carretera son m´as peque˜nas y puede mandar menos paquetes, sin embargo, como no ha experimentado este contexto no sabr´a qu´e acci´on es mejor. Si se suceden las rondas y el agente pasa por varios d´ıas con nieve, comenzar´a a aprender que acciones son las mejores para los d´ıas con nieve. Por esto, puede que aunque para los d´ıas soleados (sin nieve) el mejor camino es el uno, mientras para los d´ıas con nieve el mejor camino sea el cuatro. El agente podr´ıa acabar d´andose cuenta de esto tras varios d´ıas con nieve donde ha probado todos los caminos. Esta es la base de la explotaci´on de los bandidos contextuales en los juegos, el agente se aprovecha de repetidas situaciones de un contexto para aprender cu´al es la mejor estrategia, o brazo, que puede seguir. Respecto al funcionamiento del algoritmo, la mejor forma de verlo es mostrar el esquema y luego explicarlo, el cGPMW opera de la siguiente manera que se presenta en el algoritmo 14. Cabe se˜nalar que sigue un esquema similar al del algoritmo GPMW pero tiene sus propias diferenciaciones. Primero se inicializa, despu´es observa el contexto y posteriormente realiza las operaciones necesarias para mejorar su toma de decisiones. 51 Algoritmo 7.14 Algoritmo cGPMW en Juego Contextual. 1: Al inicializar: Se establece una tasa de aprendizaje γ, se inicializan los pesos a 1, se calculan la recompensa m´axima y la recompensa m´ınima. Se obtienen los Kcaminos que puede tomar. Se inicializan el historial y el historial de recompensas. 2: for cada ronda t= 1,2, . . . do 3: Se observa el contexto xt∈X. 4: Se calcula la estrategia y se simula la retroalimentaci´on total para dicho contexto xt:∀a∈A: racumulada(a|xt) = f(historiales, ocupaciones, capacidadest) 5: Se actualiza el vector pesos:∀a∈A:pesosa←pesosa·eγ·(−La) 6: Se juega un brazo aelegido aleatoriamente en funci´on del vector pesos. 7: Se actualizan el historial y el historial de recompensas con el brazo ay su recompensa r. 8: end for Tras haber mostrado el esquema, es apreciable el principal rasgo de este algoritmo. Primero observa el contexto, xt, y despu´es calcula la estrategia a seguir antes de elegir un brazo. Por lo tanto, ya ha desarrollado una estrategia al haber observado un contexto espec´ıfico antes de elegir un brazo. A priori, podr´ıa pensarse que es una ventaja porque aprovechar´a ese contexto en espec´ıfico al crear una pol´ıtica acorde a las capacidades de la red antes de tomar una decisi´on, antes de elegir un brazo. Este es un factor diferencial en contraste con el resto de algoritmos como el algoritmo GPMW que, primero, no observa el contexto, y segundom actualiza sus pesos y realizan predicciones al final de la ronda, no antes de elegir la acci´on. Ahora se profundiza en los pasos clave de esta funci´on y se detendr´a en desarrollar estas fases para facilitar la comprensi´on y poder abordar el algoritmo con todo detalle: En primer lugar, cGPMW Observa el contexto, xt, al comienzo de la ronda. Este contexto refleja las capacidades de las carreteras. El contexto de cada ronda tse obtiene aleatoriamente entre los x∈X contextos posibles. Despu´es el algoritmo la estrategia dado el contexto. Para calcular la estrategia, al igual que con el algoritmo anterior aprovecha la simulaci´on de retroalimentaci´on total. Sin embargo, el algoritmo cGPMW tiene varias diferencias apreciables respecto a su antecesor. •El modelo es entrenado con regresi´on gausiana con los siguientes datos hist´oricos: el historial de recompensas y el historial que se compone por tres factores: las ocupaciones totales, los paquetes enviados por el agente seg´un el camino elegido y las capacidades. Al contrario que los algoritmos GPMW, se almacenan las capacidades de cada ronda, es decir, los contextos. •El algoritmo cGPMW itera desde las rondas anteriores hasta la ronda t−1. •En cada ronda, realiza una predicci´on para cada brazo con el modelo de regresi´on gaussiana, dadas las capacidades actuales, y calcula la recompensa para cada brazo con la siguiente f´ormula: UCBa= ˆµa+βtˆσa.Beta es una variable que se sigue usando para reducir a la mitad la varianza. La varianza es obtenida por el modelo de regresi´on gaussiana. •Una vez ha calculado la recompensa para esa ronda, escalar´a dicha recompensa (para cada brazo), de acuerdo a las mismas reglas que necesitaba el algoritmo GPMW. •Escala las recompensas sobre 0 y 1 usando la recompensa m´axima y la recompensa m´ınima que obtenida en la incializaci´on. •Cuando se obtienen las recompensas escaladas, el algoritmo calcula la recompensa acumulada escalada hasta la ronda t−1. De este modo, se tienen en cuenta la predicci´on de las recompensas de todas las rondas anteriores dado un contexto concreto para cada uno de los brazos. •Tras haber calculado todas las recompensas acumuladas para cada brazo haciendo predicciones en las rondas anteriores con las capacidades actuales, utilizar´a las p´erdidas acumuladas, y simplemente restar´a a trondas anteriores las recompensas acumuladas: L=T−recompensasacumuladasapara cada brazo a.Larepresentar´ıa las p´erdidas acumuladas para las rondas anteriores con un contexto particular para un brazo. Se hace de esta forma ya que las recompensas acumuladas se han ido sumando durante Trondas y estar´an entre un valor de 0 y Tpara cada brazo. •Actualiza los pesos el vector pesos:∀a∈A:pesosa←pesosa·eγ·(−La). 52 El siguiente paso a seguir por este algoritmo es elegir un brazo aaleatoriamente dado el vector pesos que ha sido modificado anteriormente con el calculo de la estrategia. Actualizar´a los historiales para el brazo ay la recompensa obtenida durante esa ronda, rt. Cabe se˜nalar, que el algoritmo cGPMW realiza predicciones en todas las rondas anteriores a la ronda en la que se encuentre y, como resultado, necesita mucho tiempo para ejecutarse. En comparaci´on con el algoritmo GPMW tarda bastante m´as porque aunque en las primeras rondas el algoritmo cGPMW no requiere mucho tiempo, cuando ya hay un n´umero considerable de rondas, como 40, tendr´a que hacer predicciones con la regresi´on para las 39 rondas anteriores por lo que el tiempo de ejecuci´on aumenta exageradamente a partir de un n´umero alto de rondas. Como se puede observar, al igual que el algoritmo GPMW los pesos se actualizan en funci´on de las p´erdidas acumuladas y no las p´erdidas de la ronda. Esto se hace porque se considera que la distribuci´on de las acciones ´optimas cambia durante la partida. Se usa este planteamiento ya que se puede pensar que las capacidades del oponente pueden variar a lo largo del tiempo y, por lo tanto, tambi´en lo har´ıan las recompensas esperadas. Entender el funcionamiento de este algoritmo hace comprensible que tener en cuenta el contexto puede ser muy beneficioso. En este caso, se predicen como actuar´an todos los brazos dadas distintas ocupaciones para este contexto. Esta informaci´on es de gran utilidad ya que el algoritmo conocer´a c´omo de bueno ser´ıa cada camino con las capacidades que se dan en la ronda. Por este motivo, se puede afirmar que frente al algoritmo GPMW, el algoritmo cGPMW aprovecha el contexto para realizar predicciones m´as precisas y, en consecuencia, toma mejores decisiones. Por ejemplo, si se predice cu´al va a ser el rendimiento de enviar paquetes a trav´es de un camino y no es conocida su capacidad, no se sabr´a si puede haber congesti´on que retrase el tiempo de env´ıo y haga que el camino sea una mala opci´on. Por el contrario, si antes de mandar los paquetes es sabido si el camino tiene mucha capacidad, se podr´a intuir si es una buena alternativa para tardar poco en enviar los paquetes. Tambi´en ser´ıa lo mismo si se observa que el camino tiene poca capacidad ya que habr´a mucha congesti´on debido a la limitada capacidad del mismo, y si esta informaci´on del camino es conocida, est´e no ser´a considerado como un buen brazo. Cuando se hace referencia a la capacidad de un camino, se est´a hablando de las capacidades de las carreteras que componen dicho camino. En segundo lugar, el algoritmo cGPMW tambi´en podr´a aprender m´as r´apido ya que identificar´a mejor los patrones entre brazos y recompensas al conocer la informaci´on contextual. Esto sucede porque el algoritmo puede ajustar su pol´ıtica de selecci´on de brazos para tomar decisiones m´as informadas en funci´on del contexto actual. Se parte de la base de que las recompensas est´an relacionadas con los contextos y los brazos. Al considerar todas las variables involucradas, rendir´a mejor. Se podr´ıa decir que el algoritmo comprender´a patrones mejor ya que es el ´unico algoritmo que apreciar´a la toma de decisiones de manera global, considerando la red en su totalidad y abarcando m´as informaci´on que la que conocen otros algoritmos. Esto mejorar´a sus decisiones y al tener m´as informaci´on para decidir aprender´a m´as r´apido que otros algoritmos. Otro factor importante es que se podr´a adaptar mejor a cada situaci´on. Como ya se ha comentado, hay ciertas limitaciones para algoritmos que no tienen en cuenta el contexto porque toman la decisi´on en base al mejor brazo en general sin considerar situaciones espec´ıficas. Pasa lo contrario con este algoritmo, que sabr´a perfectamente que aunque un brazo pueda ser una alternativa mediocre, para un contexto determinado puede ser la mejor v´ıa. Para ilustrar esto, en una red donde un agente tiene cinco distintos caminos y se supone que el camino tres es una opci´on que ofrece rendimientos regulares, que no es muy r´apido ni muy lento, este brazo tres podr´ıa considerarse como un brazo mediocre. Sin embargo, podr´ıa darse una situaci´on que es muy puntual y ocurre espor´adicamente pero provoca que el resto de caminos tengan poca capacidad, como que se aumenten las restricciones en las carreteras por la contaminaci´on excepto en las carreteras del camino tres. Dicho camino a pesar de no ser especialmente bueno, ser´ıa tremendamente ´util ante esta coyuntura ya que el resto de caminos se ver´ıan gravemente perjudicados. Mientras que el algoritmo GPMW no apreciar´ıa esto, el algoritmo cGPMW sacar´ıa partido de esta situaci´on y por eso es destacable su habilidad para adaptarse a diversas situaciones. Por ´ultimo, el algoritmo cGPMW puede desarrollar una buena estrategia de cara a la exploraci´on-explotaci´on. Al ser conocedor del contexto puede centrar m´as su exploraci´on en ciertos contextos donde hay mucha incertidumbre mientras que puede mantener una constante explotaci´on en contextos seguros. Esto puede comprenderse claramente con el mapa de carreteras. Si se supone que una de las variables del contexto es el calendario, dada una ´epoca del a˜no festiva, se puede pensar que en estos d´ıas las carreteras tendr´an mucha ocupaci´on y ante dicha situaci´on habr´a mucha incertidumbre por saber qu´e carreteras ser´an m´as concurridas que otras. El algoritmo puede pensar que al aumentar el riesgo le conviene explorar m´as en un s´abado de una semana festiva como 53 Semana Santa que ante un s´abado normal donde las carreteras tendr´an ocupaciones similares. De esta manera podr´ıa centrarse en desarrollar una estrategia adecuada en estos contextos espec´ıficos donde la incertidumbre aumenta considerablemente. 7.5. Conclusiones Esta aplicaci´on pr´actica se inici´o con dos objetivos. El primero era realizar una traducci´on de la implementaci´on original del juego en Python [18] a C++, un lenguaje de m´as bajo nivel que permitir´ıa escudri˜nar los detalles para entender el funcionamiento del juego. El segundo objetivo era observar las diferencias entre los algoritmos que no ten´ıan en cuenta el contexto: Hedge y GPMW, y los que s´ı: cGPMW. En cuanto al primer objetivo, se ha conseguido implementar correctamente en C++ los algoritmos estudiados, tal y como queda reflejado en los repositorios [26] y [27]. Gracias a esto, se ha obtenido un conocimiento muy avanzado acerca de las partes o procesos que conforman los algoritmos usados en los problemas de bandidos multi-brazo. Por ejemplo, se ha aprendido que la forma de implementar un algoritmo es mediante una clase que tenga como atributos imprescindibles el n´umero de brazos, la distribuci´on actualizada de las probabilidades de elecci´on de cada brazo y dem´as par´ametros necesarios, como la tasa de exploraci´on, que ajustan el funcionamiento del algoritmo. Adem´as, la clase del algoritmo debe implementar dos m´etodos que son ejecutados en cada ronda: el primero ejecuta la fase de elecci´on de brazo y, tras recibir la recompensa correspondiente, el segundo actualiza la distribuci´on de probabilidades de los brazos en base a dicha recompensa. Por otra parte, no solo se han desarrollado correctamente todos los algoritmos, sino que tambi´en se ha creado una red y una simulaci´on en C++ que imita la original en Python. Respecto al segundo objetivo, este cap´ıtulo se ha adentrado en las caracter´ısticas de los algoritmos contextuales y los no contextuales para poder explicarlos de manera clara y precisa. Asimismo, se ha conseguido entender y explicar las diferencias entre estos algoritmos. Por tanot, se puede considerar que este objetivo ha sido cumplido con creces. Pero no todo fue sencillo, durante el proceso de adaptaci´on se encontraron ciertas limitaciones de C++ con respecto a Python que imped´ıan obtener los mismos resultados que en los an´alisis realizados por Guissepe Sessa y sus colaboradores reflejados en la figura 12, extra´ıda de [12], y en la figura 13, extra´ıda de [14]. Figura 12: Coste medio y congesti´on media. Para saber los brazos o caminos que pueden ser escogidos por los agentes era necesario conocer previamente los kcaminos m´as cortos (5 en este caso). Con este prop´osito, en el c´odigo de Python se emplea una librer´ıa conocida como Networkx que simplifica el proceso. Sin embargo, en C++ no existe dicha biblioteca, lo que supuso la primera dificultad para la traducci´on a dicho lenguaje. Finalmente, tras la realizaci´on de muchas pruebas fallidas, se alcanzo el ´exito al adecuar el c´odigo publicado en [19] al desarrollo previo, consiguiendo desarrollar la misma funci´on que la librer´ıa Networkx en Python. El aprovechamiento de este c´odigo permiti´o implementar el algoritmo Yen K Caminos M´as Cortos, que a su vez hace uso del algoritmo Dijkstra Camino M´as Corto. Previamente, fue necesaria la familiarizaci´on con el tipo de grafos con los que trabajan estos algoritmos. Adem´as, hubo que conectar el algoritmo Yen con la red de nodos y carreteras, almacenada en la estructura de datos “SiouxNetwork”, y con el vector de estrategias que se explica a continuaci´on. Por ello, para adaptar adecuadamente este algoritmo hubo que modificar gran parte del c´odigo ya desarrollado y del propio Yen K Caminos M´as Cortos. En conclusi´on, esta tarea se llev´o a cabo 54 Figura 13: Remordimiento medio y congesti´on media. correctamente y se pudo solventar la dificultad. En el c´odigo desarrollado estos caminos se guardan en un vector de estrategias de tres dimensiones, concretamente [528][5][76], compuesto por un primer vector de 528 jugadores o posiciones, un segundo vector para cada jugador de 5 caminos o posiciones y un tercer vector para cada camino. Cada uno de los caminos tiene un tama˜no de 76 carreteras de la red, y en cada carretera o posici´on del vector del camino aparecen las demandas de ese jugador en dicho camino. Se recuerda que cada uno de los 5 caminos refleja uno de los 5 brazos del agente. Por ejemplo, en la posici´on 20 del vector de estrategias hay cinco brazos asociados a ese jugador (el de la posici´on 20). El brazo 1 se define por un vector de 76 posiciones y cada una de estas 76 posiciones representa una carretera. Por lo tanto, si la posici´on 2 tiene un valor de 10 ([20][1][2] = 10) y la posici´on 14 tiene un valor de 5 ([20][1][14] = 5), significar´a que el brazo o camino 1 del jugador 20 utilizar´a las carreteras 2 y 14, con una demanda total de 15. Por otro parte, el problema m´as importante que surgi´o se debe, de nuevo, a factores t´ecnicos propios de C++, que carece de determinadas librer´ıas que s´ı est´an disponibles en Python. Concretamente, hubo problemas al intentar adaptar una librer´ıa llamada GPy de Python a C++. Esta librer´ıa se encarga de realizar la regresi´on gaussiana usada por los algoritmos GPMW y cGPMW. En su defecto, en C++, se ha trabajado con la funci´on de regresi´on “rvm regression trainer” de la biblioteca dlib, tambi´en conocida como RVM (Relevance Vector Machine), que consiste en un algoritmo de aprendizaje autom´atico. El ´unico hiperpar´ametro que requiere RVM es la tasa de aprendizaje, cuyo valor se modific´o con el objetivo de no obtener sobreajuste en las predicciones realizadas durante las pruebas. En definitiva, a pesar de que con esta alternativa s´ı fue posible realizar la regresi´on correctamente, los resultados conseguidos no fueron iguales a los de Python. Cabe se˜nalar que inicialmente se prob´o con el regresor “krr trainer”, tambi´en implementado en la biblioteca dlib, pero los resultados fueron sustancialmente peores que los obtenidos con el regresor RVM. Adem´as, aunque se consigui´o elaborar en una funci´on que calcula y optimiza los Kernels en C++ utilizando la biblioteca Eigen, esto no fue de utilidad ya que no era compatible con la funci´on de regresi´on RVM de la biblioteca dlib. Por otra parte, como la biblioteca dlib, a diferencia de GPy, no proporciona la varianza de las predicciones, se decidi´o optar por calcular la varianza de los datos de entrenamiento y usarla como varianza para las predicciones de la adaptaci´on. Realmente, todas las decisiones han sido tomadas con el fin de mejorar las predicciones realizadas por la adaptaci´on en C++ y desarrollar buenos algoritmos. De todas formas, se ha llegado a la conclusi´on de que la traducci´on de este juego contextual y sus algoritmos en Python a C++ ha requerido de excesivo tiempo y esfuerzo debido a las limitaciones t´ecnicas de C++ en comparaci´on con las ventajas y capacidades del lenguaje Python. Con todo lo anterior, se considera que la implementaci´on desarrollada sirve como base s´olida para entender los bandidos contextuales y sus algoritmos, y enriquece las aportaciones de este apartado contribuyendo al avance del conocimiento en este campo. Una vez expuestas las caracter´ısticas del juego en C++, se procede al an´alisis del mismo. Para ello, se comparan los resultados del algoritmo GPMW y el algoritmo cGPMW para un agente aleatorio en una simulaci´on concreta. Es decir, en esta simulaci´on, se observa el comportamiento de un ´unico agente para los dos algoritmos. De esta manera, ambos algoritmos disponen de los mismos brazos o caminos para elegir y sus rendimientos pueden ser contrastados bajo el mismo escenario. No se considera el algoritmo Hedge porque tiene retroalimentaci´on total. El inter´es de este an´alisis radica en observar las diferencias entre un algoritmo que tiene en cuenta 55 el contexto, cGPMW, y otro que no observa dicho contexto, GPMW. Figura 14: Brazos elegidos. Figura 15: P´erdidas por ronda. Para obtener las figuras 14 y 15, primero se han guardado los resultados de la simulaci´on de C++ en un fichero. Despu´es, con Python se ha analizado dicho fichero y se han creado estas gr´aficas que estudian el comportamiento y rendimiento de los algoritmos. Junto a la figura 16, estas reflejan, en cada ronda, los brazos elegidos por cada algoritmo y su efecto inmediato en las p´erdidas. Cabe mencionar que en la primera figura los 5 brazos se representan con los valores enteros del intervalo [0, 4]. Al analizar estas gr´aficas, se observa que el algoritmo cGPMW no siempre elige mejor que GPMW, hay ocasiones en las que este segundo elige un camino que implica menos p´erdidas. De todas formas, por regla general el algoritmo GPMW es el que obtiene mayores p´erdidas, o peores recompensas, a lo largo del horizonte temporal. Por ´ultimo, la figura 17 muestra verdaderamente qu´e algoritmo consigue minimizar las p´erdidas medias a lo largo de la simulaci´on. En este caso, se puede apreciar que el algoritmo cGPMW es el que consigue menores p´erdidas medias al final de la simulaci´on. En definitiva, se puede concluir que el algoritmo cGPMW, que considera el contexto, alcanza un mayor rendimiento que el algoritmo GPMW en escenarios contextuales Debido a la p´erdida de eficacia por el proceso de traducci´on del lenguaje que ha sido reflejada en esta secci´on y a que solo se ha podido comparar el rendimiento de dos algoritmos entre s´ı, no ha sido posible obtener 56 Figura 18: Cruce de SMA de periodo largo, medio y corto [24]. Las gr´aficas de color rojo, verde y naranja de la figura representan las SMA de largo, medio y corto plazo, respectivamente. Se puede comprobar que cuando las medias m´oviles de medio y corto plazo cortan con la de largo plazo se produce un cambio en la tendencia del precio del t´ıtulo. La estrategia de cruce de medias m´oviles es una t´ecnica de an´alisis t´ecnico popular que se basa en la idea de que las tendencias a corto plazo pueden predecir las tendencias a largo plazo. Concretamente, este bot resuelve los posibles contextos como sigue: Si est´a en posesi´on del t´ıtulo: Mantiene su posici´on larga a menos que la media m´ovil a corto plazo (SMA corta) sea menor que la media m´ovil a largo plazo (SMA larga). En ese caso vender´ıa el t´ıtulo porque representar´ıa una se˜nal de que el precio va a descender pr´oximamente. Si no est´a en posesi´on del t´ıtulo: Mantiene su posici´on corta a menos que salte la se˜nal de compra cuando la media m´ovil a corto plazo sea mayor que la media m´ovil a largo plazo. Sin embargo, esta estrategia puede no funcionar bien en mercados laterales o con baja volatilidad, ya que las se˜nales de compra y venta pueden ser menos precisas en esas condiciones. 8.2.5. Experto en RSI El bot experto en el oscilador RSI, al igual que el bot anterior, solo trabaja monitorizando una fuente de datos. El ´ındice de fuerza relativa o RSI (Relative Strength Index) es un oscilador de impulso utilizado en el an´alisis t´ecnico. El RSI mide la velocidad y la magnitud de las variaciones recientes del precio de un valor para evaluar las condiciones de sobrevaloraci´on o infravaloraci´on del precio de ese valor. Fue desarrollado por J. Welles Wilder Jr. e introducido en su libro [15]. Cabe destacar que el RSI puede hacer algo m´as que se˜nalar valores sobrecomprados y sobrevendidos. Tambi´en puede indicar valores que pueden estar preparados para un cambio de tendencia o un retroceso correctivo en el precio. Por ejemplo, si el precio de un activo est´a alcanzando nuevos m´aximos o m´ınimos, pero el RSI no est´a registrando nuevos m´aximos o m´ınimos respectivamente, podr´ıa estar indicando una desaceleraci´on en el impulso y una posible inversi´on de la tendencia. [25] Para calcular el valor del RSI, primero se calculan las ganancias medias y las p´erdidas medias para un periodo anterior de n= 14 d´ıas, por regla general. Una vez obtenido el valor de dichas variables, se calcula el valor del indicador como RSI = 100 −(100/(1 + (Ganancias Medias/P´erdidas Medias))). La estrategia de este bot sigue las se˜nales tradicionalmente usadas para comprar y vender del RSI. Es decir, una lectura del RSI igual o superior a 70 indicia que el precio est´a superando el umbral de sobrecompra y, por tanto, el bot recomienda vender, o mantenerse en caso de que la posici´on del algoritmo ya fuese corta. Por el otro lado, una lectura de 30 o inferior indica una situaci´on de sobreventa y el bot sugiere comprar, o mantenerse en caso de que el algoritmo ya presente una posici´on larga. Normalmente, este oscilador se suele monitorizar conjuntamente con otros indicadores para mejorar la calidad del an´alisis. Esto se debe en parte a que, como todos los ´ındices, puede producir se˜nales falsas. Por este motivo, si el bot de comercio o cualquier agente no tiene otras referencias seguir´a las se˜nales falsas sin detectarlas, incurriendo en p´erdidas. Por otro lado, como este oscilador no presenta informaci´on de la direcci´on de la 63 tendencia, el bot podr´ıa no recibir se˜nales de sobrecompra o sobreventa por parte del RSI mientras que el activo puede estar en una tendencia alcista o bajista fuerte. Adem´as, el RSI tampoco proporciona niveles de soporte y de resistencia que podr´ıan ser ´utiles para establecer objetivos de precio para vender cuando est´e alto o paradas de las p´erdidas para vender cuando el precio disminuya hasta un determinado nivel. Por estos motivos, se suele recomendar el an´alisis t´ecnico combinando los datos de varios ´ındices al mismo tiempo. 8.2.6. Experto en MACD y Bandas de Bollinger Se introduce, por primera vez, un bot que hace uso de m´as de un indicador al mismo tiempo. Este bot se rige a partir de dos indicadores, el MACD y las bandas de Bollinger. El indicador MACD (Moving Average Convergence Divergence) es una herramienta muy com´un dirigida al an´alisis de mercado. Este indicador define la diferencia entre una media m´ovil exponencial (EMA) del corto plazo y otra del largo plazo. Lo normal es que se consideren los 12 y 26 d´ıas anteriores como el corto y largo plazo, respectivamente. Matem´aticamente, la l´ınea MACD se calcula tal que MACD = ema(12,Precio) −ema(26,Precio). Adem´as, a partir de la l´ınea MACD calculada anteriormente, se genera una l´ınea de se˜nal conocida como EMA en base a, normalmente, los 9 d´ıas anteriores de tal forma que Se˜nal = ema(9,MACD). La diferencia entre la l´ınea MACD y la l´ınea de se˜nal se denomina Histograma MACD, por tanto, Histogrma = MACD −Se˜nal. En [16] se puede encontrar la interpretaci´on de este indicador. Por otra parte, las bandas de Bollinger son otro instrumento de an´alisis t´ecnico que se utiliza para medir la volatilidad del precio. La volatilidad de un t´ıtulo en un determinado intervalo de tiempo es la variabilidad de su rentabilidad en relaci´on a su rentabilidad media en dicho periodo. A partir de la media m´ovil simple (SMA) del precio de los 20 d´ıas anteriores y su desviaci´on t´ıpica, se puede establecer una banda superior e inferior tal que Banda Superior = sma(20,Precio) + 2 ∗std dev(20,Precio) y Banda Inferior = sma(20,Precio) −2∗std dev(20,Precio). Seg´un el tama˜no del ancho de banda, que como se˜nala John Bollinger en [21] representa c´omo de separadas est´an las bandas externas con respecto a la l´ınea central, se puede cuantificar la volatilidad del t´ıtulo. El bot experto en MACD y las bandas de Bollinger que se plantea trabaja de la siguiente manera: Si est´a en posesi´on del t´ıtulo: Mantiene su posici´on larga a menos que se de alguna de las siguientes 2 condiciones para vender: •La se˜nal del MACD es mayor que el valor del MACD. Esta condici´on indicia una posible tendencia bajista. •El precio de cierre es mayor que la banda superior de Bollinger. Podr´ıa indicar que el precio est´a sobrevalorado y podr´ıa corregirse a la baja. Si no est´a en posesi´on del t´ıtulo: Mantiene su posici´on corta a menos que se de alguna de las siguientes 2 condiciones para comprar: •La se˜nal del MACD es menor que el valor del MACD. Esta condici´on indicia una posible tendencia alcista. •El precio de cierre es menor que la banda inferior de Bollinger. Podr´ıa indicar que el precio est´a infravalorado y podr´ıa corregirse a la alza. 8.2.7. Experto en Todo Por ´ultimo, se ha querido incluir en el conjunto de bots de comercio proporcionado al algoritmo un bot que se comporte de acuerdo al movimiento de muchos de los indicadores habituales en el mercado actual. En cada ronda, este bot observa un conjunto de indicadores financieros y la posici´on actual del algoritmo: corta o larga. A continuaci´on, eval´ua una serie de condiciones basadas en estos indicadores. Por ejemplo, comprueba si el precio de cierre es superior a la banda superior de Bollinger, si el MACD es superior a su l´ınea de se˜nal, si el RSI es superior a 50, etc. Suma el n´umero de condicionantes de su estrategia que son verdaderos y luego realiza una recomendaci´on basada en si este n´umero es mayor o igual a 6. 64 Si en una determinada ronda el algoritmo est´a en posesi´on del t´ıtulo y el n´umero de condiciones verdaderas es mayor o igual a 6, el experto decide mantener la posici´on larga. De forma inversa, si el n´umero de condiciones verdaderas es menor que 6, decide vender el t´ıtulo. La l´ogica es similar si el algoritmo tuviese una posici´on corta. Es decir, si no posee el t´ıtulo en una ronda en la que la cantidad de condiciones verdaderas supera o iguala el valor 6 el bot experto en todo recomendar´a al algoritmo comprar y en caso contrario mantener su posici´on. Entre todos los bots que ser´an evaluados y explotados por el algoritmo Exp4, este es el bot cuya estrategia presenta la mayor complejidad de construcci´on debido a la variedad de indicadores que rigen su comportamiento. Una de las objeciones que se podr´ıan plantear a esta estrategia es que considera la importancia de todos los indicadores por igual. Esta objeci´on se fundamenta en el hecho de que dependiendo de las condiciones del mercado unos indicadores pueden ser m´as relevantes que otros. En cambio, la diversidad de se˜nales que presenta permite al bot incrementar su flexibilidad de decisi´on con respecto al resto de bots ya que adquiere una visi´on m´as completa del estado del mercado. Es decir, su comportamiento no siempre queda definido por los mismos indicadores. Con todo esto, el bot experto en todo es una gran incorporaci´on al conjunto de bots. Se podr´ıa haber seguido incluyendo m´as estilos de bots de comercio en el conjunto de bots, pero la parte relevante de esta secci´on, en relaci´on al trabajo de fin de grado, se centra en el an´alisis del comportamiento de la soluci´on planteada para resolver el problema que se viene explicando. De todas formas, el c´odigo desarrollado incluye la implementaci´on de otros bots que pueden ser incluidos, si se desea, en el conjunto de bots contemplado por el algoritmo Exp4, como por ejemplo el experto en Ichimoku, el experto en Fibonacci, etc. 8.3. An´alisis de la Soluci´on Planteada Antes de comenzar, en la figura 19 se presenta la leyenda para identificar a cada bot del conjunto de bots entregado al algoritmo Exp4. Figura 19: Leyenda de los bots de comercio. De esta forma es posible identificar con el color azul al bot experto en posiciones cortas, con el naranja al bot experto en posiciones largas, con el verde al bot experto en posiciones cambiantes, etc. La finalidad con la que se ha separado la leyenda de la presentaci´on del las gr´aficas mostradas a continuaci´on es incrementar la visibilidad de los detalles, permitiendo mejorar la comprensi´on de las situaciones reflejadas. 8.3.1. Consideraciones previas Previo al an´alisis de la soluci´on planteada, en este apartado se busca justificar dos decisiones tomadas con respecto a la implementaci´on de la soluci´on para superar ciertas limitaciones que a priori presentan los algoritmos Exp4 y Hedge de forma conjunta. Concretamente, ha sido necesario modificar la funci´on de recompensas y el c´alculo de las probabilidades que presentan los expertos de elegir cada brazo. Modificaci´on en la Funci´on de Recompensas En un principio, se quiso establecer 1 como valor para la recompensa positiva y 0 para la recompensa nula. Pero debido a la forma ( ct(at) Pr[at=at,π |pt]) que el algoritmo Exp4 tiene de establecer los costes estimados para aquellos bots que eligen, en una determinada ronda, el mismo brazo que el seleccionado finalmente por el algoritmo en dicha ronda, se tuvo que realizar una modificaci´on. Esto se debe a que, si el algoritmo acertaba con su 65 decisi´on de brazo, aquellos bots cuya recomendaci´on coincid´ıa obten´ıan una recompensa de 1, que equivale a un coste de 0. Sustituyendo dicho coste en la f´ormula mencionada anteriormente, dichos bots obten´ıan un coste estimado de 0. Por defecto, Exp4 por defecto otorga un coste estimado de 0 a los bots que no recomiendan el mismo brazo que el elegido por el algoritmo. Por ende, en este escenario en el que el algoritmo acierta con su elecci´on, no habr´ıa diferencia entre los costes estimados de aquellos bots que acertasen con su elecci´on y los que no. Como resultado, tal y como explica la f´ormula (wt+1(a) = wt(a)·(1 −ϵ)ˆct(a)) que el algoritmo Hedge aplica para actualizar los pesos de los bots, ninguno de los pesos se modificar´ıa. Esto implicar´ıa que tomar buenas decisiones no proporcionar´ıa ninguna “ventaja” a los bots. Por tanto, con la intenci´on de solucionar este impasse se ha tomado la decisi´on de considerar una recompensa positiva de 0,9 que evita el problema anterior y, para mantener un equilibrio, una recompensa “casi nula” de 0,1. Modificaci´on de las Probabilidades Individuales de Elegir un Brazo Seg´un el libro de Slivkins [2], que constituye el pilar fundamental del desarrollo de este trabajo, la definici´on te´orica del algoritmo Exp4 hace referencia a que, en cada ronda, cada experto debe devolver la probabilidad con la que ha recomendado su brazo con la finalidad de que Exp4 pueda calcular la probabilidad conjunta, entre todos los expertos, de escoger cada uno de los brazos posibles. Esto se debe a que Exp4 necesita tener calculada la variable Pr[at=at,π|pt] para usarla como denominador en su paso 6. Su aplicaci´on en el denominador lleva impl´ıcita la condici´on de que su valor no puede ser 0 o cercano a 0, ya que en ambos casos el resultado de la divisi´on ser´ıa nulo. Para ello, como ya indica Slivkins en una de sus anotaciones del cap´ıtulo 6, la soluci´on consiste en asegurar que las probabilidades individuales de cada experto de elegir o recomendar cada uno de los brazos sean mayor que 0. Esto supone ir en contra de la l´ogica de los conceptos aprendidos hasta el momento, dado que un bot de comercio es un experto que asocia contextos a brazos siguiendo una estrategia predefinida e invariante. Es decir, dado un determinado contexto, el bot siempre decide recomendar el mismo brazo de acuerdo a su estrategia, lo que implica una probabilidad de elecci´on del 100 % sobre dicho brazo, quedando reducidas a 0 las probabilidades de ese bot de elegir el resto de brazos disponibles. Para comprobar que la soluci´on mencionada por Slivkins es necesaria, se ha probado a programar las probabilidades individuales de elecci´on de brazo de los bots tal y como se ha mencionado anteriormente, siguiendo estrictamente la l´ogica y no los comentarios de Slivkins. La figura 20 ilustra el problema que sucede con los pesos de los bots si las probabilidades individuales de recomendaci´on de cada bot son 100 % para el brazo indicado, bajo cada contexto, por su estrategia y 0 % para el resto. Figura 20: Evoluci´on de los Pesos de los Expertos con γ= 0,2. Antes de adentrarnos en el an´alisis, es esencial recordar que la probabilidad conjunta entre todos los bots 66 de recomendar el brazo at, finalmente elegido por el algoritmo, es usada como denominador en el c´alculo de los costes estimados, con los cuales Hedge actualiza los pesos de los bots. Adem´as, es necesario recordar que el c´alculo de esta probabilidad tiene en cuenta las probabilidades individuales de recomendaci´on de cada bot y los pesos de estos bots. Cuanto mayor sea el valor de γ, m´as probabilidades hay de que el algoritmo elija aleatoriamente un brazo, sin tener en cuenta los pesos de los bots. Por tanto, a pesar de que algunos bots ya hayan sufrido una ca´ıda de sus pesos y el algoritmo, dif´ıcilmente, vaya a seguir sus recomendaciones, con γ > 0 Exp4 podr´ıa llegar a elegir el mismo brazo que los bots “infravalorados”. En el caso de que, en una determinada ronda, el algoritmo elija un brazo que solo ha sido recomendado por uno o pocos bots cuyos pesos son muy bajos, se estar´ıa incurriendo en una situaci´on en la que la probabilidad conjunta definida anteriormente reciba un valor de 0 o cercano a 0. Esta situaci´on sucede varias veces durante el transcurso de la ejecuci´on reflejada en la figura 20. Cada vez que se da esta situaci´on, como por ejemplo en la ronda 292, supone un antes y un despu´es en la evoluci´on de los pesos de los bots. Se deja en el anexo 13 una depuraci´on “casera” obtenida durante la ejecuci´on mencionada en caso de que se quiera apreciar con mayor detalle lo acontecido en la ronda 292. Como se ha querido demostrar, es necesario que las probabilidades individuales de elecci´on de cada bot sean mayores que 0 para todos los brazos. Si se interpreta textualmente la definici´on de una pol´ıtica (asociaci´on de contextos a brazos con probabilidad del 100 %), los resultados que se obtienen carecen de valor porque en el c´alculo de los costes estimados se divide el coste real entre una probabilidad de 0 o cercana a 0. Por tanto, para el resto de la secci´on se adopta una interpretaci´on menos realista pero que evita el problema y permite realizar un an´alisis riguroso. Esta variante consiste en programar que el bot informe al Exp4 de que su probabilidad de recomendar el brazo que indica su estrategia seg´un el contexto es del 90 %, mientras que la del otro brazo no escogido es del 10 %. Este simple y peque˜no reparto de la probabilidad total es suficiente para paliar los problemas generados por la interpretaci´on literal de la teor´ıa del problema. 8.3.2. An´alisis del Horizonte Temporal En la introducci´on del problema de los bots de comercio se mencionaba que el horizonte temporal convendr´ıa ser definido tras un an´alisis previo debido a la complejidad que presenta. Este es uno de los aspectos m´as relevantes del planteamiento del problema porque los costes estimados en los que incurre cada experto en cada una de las rondas dependen en gran medida de la configuraci´on del horizonte temporal. Por ejemplo, para analizar 6 a˜nos se puede considerar una ronda como cada uno de sus d´ıas, meses, trimestres, a˜nos, etc. Lo que var´ıa es la separaci´on temporal entre cada dato del precio del activo. Por tanto, se puede analizar el mismo intervalo de tiempo combinando distintas cantidades de separaci´on temporal con distinto n´umero de rondas u horizonte temporal. Debe recordarse que el bot recibe una recompensa u otra dependiendo del brazo que ha recomendado y del siguiente precio proporcionado por la fuente de los datos. En este sentido, no es lo mismo que el siguiente precio sea el del d´ıa siguiente que el de una semana despu´es o un mes despu´es. En definitiva, las recompensas de los bots de comercio quedan al amparo de la decisi´on que se tome en este aspecto. Para un activo (Apple Inc.) y un intervalo de tiempo (2015-2021) determinados al azar, se han analizado las recompensa medias obtenidas por el algoritmo para diferentes d´ıas de separaci´on entre cada dato, y los resultados quedan reflejados en la figura 21. 67 Figura 21: Relaci´on entre la Separaci´on Temporal de Contextos (en d´ıas) y la Recompensa Media Obtenida Las recompensas medias obtenidas por el algoritmo dependen de c´omo de bien se comportan los bots en el escenario establecido. Por tanto, a partir de la figura anterior, se puede deducir que los bots de comercio rinden mejor con una separaci´on temporal de 15 y 25 d´ıas entre los contextos diarios que recibe el algoritmo Exp4. La explicaci´on detr´as de esta conclusi´on se encuentra en la forma en la que son dise˜nados los indicadores. En la soluci´on planteada, estos se forman analizando los n= 9,14,12,20,26 d´ıas anteriores. Entonces, es l´ogico que la amplitud del intervalo de los datos hist´oricos, que los bots tienen en cuenta para escoger brazos, influya en cu´al es el mejor escenario para los bots. Por ejemplo, un bot que recomienda en base a los datos relativos al ´ultimo a˜no de la vida del activo tiene informaci´on acerca de la evoluci´on del mercado a largo plazo. Este bot nunca ser´a capaz de igualar el rendimiento a corto plazo de un bot que ha sido informado ´unicamente de los precios de la semana anterior, ya que este ´ultimo tiene una fiel imagen del comportamiento del activo a corto plazo. Cabe destacar que la existencia de esta disyuntiva es independiente del valor de los hiperpar´ametros γyε, asociados a la tasa de exploraci´on y aprendizaje, respectivamente. Por lo tanto, teniendo en cuenta los valores de ncomentados, para el an´alisis final de los resultados se ha considerado una separaci´on temporal de 18 d´ıas entre los precios consecutivos considerados por la funci´on de recompensas. Aparte de aprovechar al m´aximo el potencial de los bots planteados, tambi´en se consigue disminuir la correlaci´on entre los resultados obtenidos por los bots. Hasta el momento no se hab´ıa mencionado esta circunstancia, pero es importante tener en cuenta que, aparte de que el n´umero de brazos disponibles en cada ronda es muy reducido (2), los bots interpretan el mercado y recomiendan brazos de forma muy similar entre s´ı. En consecuencia, sus recompensas esperadas tienen comportamientos parecidos. Por tanto, aminorando la correlaci´on entre los rendimientos de los bots se ayuda a que el algoritmo Exp4 aprenda, de manera ´optima, cu´ales son los mejores bots. En las figuras 22 y 23 se pueden observar las diferencias entre las correlaciones en funci´on de la separaci´on temporal entre las rondas. Figura 22: Correlaci´on entre los rendimientos esperados de los bots con 3 d´ıas de separaci´on entre rondas. Figura 23: Correlaci´on entre los rendimientos esperados de los bots con 20 d´ıas de separaci´on entre rondas. 68 8.3.3. An´alisis de la Tasa de Aprendizaje En esta secci´on se estudia qu´e tasa de aprendizaje es ´optima para el problema problema planteado. Se define tambi´en como ε. Para ello, se realiza un an´alisis con el objetivo de comprender el comportamiento del Exp4 bajo diferentes tasas de aprendizaje. La tasa de aprendizaje es un hiperpar´ametro que tiene mucha importancia en el modelo Exp4. Define la rapidez con la que el algoritmo compone una distribuci´on de pesos sobre los expertos que ya presenta claras diferencias entre las prioridades relativas otorgadas a cada experto, es decir la rapidez con la que aprende. Una tasa alta castiga mucho a los bots que toman decisiones err´oneas al principio de la ejecuci´on, reduciendo demasiado su peso y dejando de tener sus recomendaciones en consideraci´on. Esto puede ser perjudicial para el rendimiento final obtenido por el algoritmo si los bots menospreciados son a la larga los mejores. Por el contrario, con una tasa de aprendizaje muy baja, el algoritmo tardar´ıa demasiado en aprender y seguir´ıa muchas veces las sugerencias de bots que no son buenos, reduciendo la recompensa media final. Por tanto, se definen dos ideas que se tratar´an de demostrar seguidamente: La primera es que una tasa de aprendizaje baja implica que Exp4 tarda mucho en aprender pero terminar´a aprendiendo correctamente cu´ales son los bots buenos. Por tanto, aunque termine aprendiendo bien, su recompensa media final no ser´a muy elevada debido al lastre que supone probar demasiadas veces todos los bots, incluyendo los malos, al principio. La segunda idea es que una tasa de aprendizaje alta no garantiza que Exp4 aprenda cu´ales son los mejores bots, porque puede castigarles mucho al principio. En consecuencia, con la tasa alta, la recompensa media ser´a muy elevada si Exp4 aprende adecuadamente desde el principio cu´ales son los bots que mejor rinden. Como ya se ha mencionado, este aprendizaje r´apido no siempre es efectivo, ya que depende de la aleatoriedad. Habr´a veces que el algoritmo no aprenda id´oneamente y explote en mayor medida los peores bots durante el resto del horizonte temporal, perjudicando enormemente la recompensa media final. En la figura 24, se lleva a cabo una prueba del algoritmo con diferentes tasas de aprendizaje. Como resultado, se observan variaciones en la recompensa media. Adem´as, se constata que el bot m´as frecuentemente seleccionado y el bot con mayor peso en la ´ultima ronda no siempre son los mismos. Tambi´en, permite apreciar la segunda idea comentada anteriormente: con tasas de aprendizaje altas muy similares (0.4 y 0.5) Exp4 obtiene resultados completamente distintos. Con una ε= 0,4 alcanza una de las peores recompensas medias, mientras que con una tasa ε= 0,5 la recompensa media es mayor. Esto refleja la aleatoriedad en las recompensas a consecuencia de una tasa de aprendizaje alta, tal como se quer´ıa demostrar. Figura 24: Resultados de Ejecutar la Soluci´on con de Distintas Tasas de Aprendizaje ε. Paralelamente y de forma adicional a la ejecuci´on del Exp4, se han guardado en variables auxiliares las recompensas esperadas asociadas a las recomendaciones de los bots, simulando que los bots trabajan individualmente el problema, aunque realmente Exp4 decida el transcurso de la soluci´on teniendo en cuenta todos los bots. Es decir, a pesar de que el algoritmo sigue la recomendaci´on de un solo bot y estima las recompensas para el resto de bots, las variables auxiliares guardan las recompensas que todos los bots obtendr´ıan por su elecci´on. Esta simulaci´on permite el an´alisis a posteriori de qu´e bots obtienen las mejores recompensas independientemente de las decisiones tomadas por algoritmo Exp4. Por ende, posibilita comprobar si la soluci´on planteada a partir del algoritmo Exp4 consigue aprender a explotar los bots m´as eficientes. 69 Figura 25: Recompensa Media Esperada de Cada Bot para ε= 0,39. Figura 26: Pesos de los Bots para ε= 0,39. Con una tasa de aprendizaje ε= 0,39, la figura 25 expone la simulaci´on argumentada anteriormente, y la figura 26 ilustra la evoluci´on de los pesos de los bots desde el punto de vista del algoritmo Exp4, sin tener en cuenta la simulaci´on. Esta segunda gr´afica permite observar el proceso de aprendizaje del algoritmo ya que refleja c´omo var´ıa su consideraci´on de todos los bots. La combinaci´on de ambas gr´aficas da lugar a la manifestaci´on de la existencia o no de un aprendizaje adecuado por parte de Exp4. Por ejemplo, si el bot experto en RSI es el que mejor recompensas medias ofrece a lo largo de la simulaci´on y Exp4 nunca le otorga un peso relativo alto, esto significa que el algoritmo no est´a aprendiendo a explotar el mejor bot. Los resultados, en este escenario con una tasa de aprendizaje alta, son evidentes. El segundo mejor bot seg´un la simulaci´on, el bot experto en cruce de medias m´oviles (rojo), al principio llega a obtener pesos de m´as de 40 %, pero tras alguna mala recomendaci´on, su peso disminuye hasta casi 0 dificultando su posterior reconsideraci´on. Por tanto, queda claro que Exp4 no est´a aprendiendo bien porque penaliza demasiado al bot rojo al principio, a pesar de que este sea en realidad uno de los bots con mayores recompensas medias esperadas. De esta forma la segunda idea ha quedado probada. Por otro lado, se analiza el comportamiento del algoritmo con una tasa demasiado baja, concretamente ε= 0,01, mediante las figuras 27 y 28. 70 Figura 27: Recompensa Media Esperada de Cada Bot para ε= 0,01. Figura 28: Elecci´on de Bots para ε= 0,01. La figura 27 ilustra las recompensas esperadas obtenidas con la simulaci´on. Cabe destacar que en este caso es ligeramente diferente a la simulaci´on representada anteriormente. Esto es porque las recomendaciones de los bots dependen de la posici´on larga o corta que presente el algoritmo. El desarrollo de las posiciones del algoritmo depender´a de c´omo el algoritmo decida en cada ejecuci´on. Como sus decisiones no son deterministas, las posiciones presentadas a los bots var´ıan entre ejecuciones y, en consecuencia, sus recompensas esperadas tambi´en. Por este motivo, las gr´aficas se parecen pero no son id´enticas. Estas diferencias se dan por el simple hecho de ser distintas ejecuciones, independientemente de si se varia la tasa de aprendizaje o la de exploraci´on. De todas formas, la variaci´on de las recompensas esperadas es tan peque˜na que se suele mantener el orden de los mejores bots entre ejecuciones. Como se puede observar en la figura 28, todas los bots se eligen casi uniformemente durante las primeras 120 rondas; hay muy poca variaci´on exceptuando el bot marr´on experto en los indicadores MACD y bandas de Bollinger. A partir de la ronda 50, el algoritmo elije m´as veces el bot marr´on que los dos mejores bots seg´un 27, el experto en posiciones largas (naranja) y el experto en medias m´oviles (rojo). Aunque finalmente aumente el peso de estos dos mejores bots, ha elegido demasiadas veces a los peores bots, y esto provoca que la recompensa media final del algoritmo sea muy baja. Adem´as, como la tasa de aprendizaje es tan peque˜na, a pesar de que pasen las rondas, el algoritmo sigue manteniendo al bot marr´on con mucho peso, a´un siendo uno de los peores bots, como evidencia la figura 27. Por lo tanto, ha quedado demostrado que elegir una tasa de aprendizaje baja no es beneficioso para el algoritmo porque la recompensa obtenida se reduce. Tampoco se debe optar un valor alto ya que hay mucho riesgo de que no aprenda las mejores pol´ıticas. Por ello, se ha detectado una buena zona de trabajo, para obtener mejores recompensas, cuando las tasas de aprendizaje se encuentran en el intervalo de 0,15 y 0,25 aproximadamente. 71 En el an´alisis final de los resultados se ejecutar´a la soluci´on con un valor ε= 0,2. 8.3.4. An´alisis de la Tasa de Exploraci´on La tasa de exploraci´on γinfluye en la cantidad de veces que el algoritmo explora un brazo aleatoriamente sin seguir las recomendaciones de los bots. La relaci´on entre el valor de esta tasa y la recompensa media obtenida se puede analizar a trav´es de la figura 29. Figura 29: Relaci´on entre el Nivel de Exploraci´on y la Recompensa Media. Como ya se coment´o en la introducci´on, el n´umero de brazos disponibles para cada ronda es K= 2. Este n´umero de brazos es un cantidad bastante limitada y no existe la necesidad de realizar una gran exploraci´on con el objetivo de comprobar el rendimiento medio de todos los brazos. En muy poco tiempo, por el simple transcurso de las rondas, el algoritmo habr´a explorado sobradamente cada uno de los dos brazos. De todas formas, no est´a de m´as otorgar un cierto valor a este hiperpar´ametro para prevenir situaciones en la que los bots se estanquen con una misma recomendaci´on y no consigan ver el potencial de otro brazo dado un contexto determinado. Por ello, para el an´alisis final de los resultados se usar´a una γ= 0,05. 8.3.5. Puesta en Pr´actica de la Soluci´on Con el objetivo de solucionar el problema de los bots de comercio de manera ´optima, se ha considerado una separaci´on entre rondas de 18 d´ıas, una tasa de aprendizaje ε= 0,2 y una tasa de exploraci´on γ= 0,05. Se ilustra de nuevo la leyenda de los bots en la figura 30. Figura 30: Leyenda. A continuaci´on se plantean un escenario para comprobar c´omo se comporta la soluci´on. En este caso, el algoritmo se sit´ua entre mediados del a˜no 2015 y finales del 2019 para operar en el mercado sobre las acciones de la empresa NVIDIA Corporation (NVDA) dedicada al desarrollo de software y hardware. Para ser capaces de interpretar el comportamiento del algoritmo es necesario ser conscientes de la evoluci´on del precio del t´ıtulo durante el periodo mencionado, reflejada en la figura 31 72 ples, cuya metodolog´ıa ya se ha estudiado, y se han aplicado otras dos pol´ıticas m´as, que son m´as complicadas, y aportan mucho valor a este caso. Estas dos ´ultimas pol´ıticas aparecen en las siguientes subsecciones 9.4.2 y 9.4.3. 9.4.1. Pol´ıticas Simples A continuaci´on, se indagar´a las pol´ıticas m´as sencillas, que no por ello son prescindibles. A pesar de su simpleza, van a aportar ideas muy interesantes y ayudar´an a llegar a mejores conclusiones. Primero, hay que a comenzar con la pol´ıtica m´as simple: elegir el mejor brazo siempre. Se selecciona el mejor brazo de acuerdo a su recompensa media µ(a). Para desarrollar esta estrategia ha sido utilizado el ´ EpsilonAvaricioso, o Epsilon-Greedy en ingl´es, con un ´epsilon igual a 0. Hay que tener presente que el ´epsilon en esta pol´ıtica representa la tasa con la que el algoritmo explorar´a entre los brazos. Por lo que si se da un ϵ= 0, nunca explorar´a, y esto asegura que siempre explotar´a el mejor brazo. Durante la fase de entrenamiento la recompensa media de cada brazo ser´a almacenada. De este modo, la pol´ıtica sabr´a cual es el brazo que tiene mejores recompensas. En la fase de evaluaci´on, con Exp4, dicha pol´ıtica elegir´a siempre el brazo que mejor recompensa haya tenido durante el entrenamiento. Por ejemplo, si el mejor brazo en la primera parte es la categor´ıa musical, siempre seleccionar´a este brazo: musical. Lo interesante de esta estrategia es ver c´omo rendir´a un algoritmo que solo elija el mejor brazo sin tener en cuenta el contexto. Realmente se est´a poniendo a prueba si la informaci´on contextual es de utilidad, ya que en caso de que esta primera pol´ıtica sea la mejor, se podr´a deducir que el contexto no est´a mejorando el algoritmo. Debido a esto, con recomendar siempre el mejor g´enero de pel´ıculas ya se conseguir´ıan buenas recompensas sin tener en cuenta la informaci´on contextual. Esta alternativa resulta atractiva puesto que puede ser que el g´enero cinematogr´afico m´as popular resulte ser siempre la mejor opci´on. Aunque un sistema de recomendaci´on puede contar con g´eneros de nicho como fantasy osci-fi, estos pueden tener menos ´exitos con una audiencia m´as general. En lugar de ello, podr´ıa ser preferible optar siempre por recomendar el g´enero que consistentemente obtiene mejores calificaciones promedio entre todo el p´ublico, en este caso ser´ıan los usuarios de entrenamiento. Por ejemplo, un g´enero como el suspense podr´ıa ser una elecci´on m´as acertada para una recomendaci´on que busque satisfacer a una amplia gama de espectadores. En segundo lugar, hay otra pol´ıtica simple: ´ Epsilon-Avaricioso con un ´epsilon igual a 0.95 (ϵ= 0,95). Esta pol´ıtica realmente se centrar´a en explorar entre todos los brazos en la inmensa mayor´ıa de las ocasiones. Las ventajas que ofrece implementar esta pol´ıtica son dos: Por un lado, se saca partido de esta pol´ıtica para la fase de entrenamiento. Tal y como se ha explicado en el apartado anterior, dicha pol´ıtica es usada para explorar en la primera etapa de entrenamiento con el objetivo de que los expertos puedan recabar datos entre los 18 brazos con sus recompensas y contextos. Su prop´osito es que con la informaci´on recabada, las pol´ıticas puedan hacer buenas recomendaciones en la segunda parte al Exp4. Por otro lado, tambi´en sirve como pol´ıtica para observar c´omo de buena ser´a una estrategia que es pr´acticamente aleatoria (explora casi siempre). Esto permitir´a extraer conclusiones sobre si elegir aleatoriamente puede tener sentido. Se ver´a si un ´ Epsilon-Avaricioso que explora ser´a premiado por el algoritmo Exp4. Debido a esto, se puede decir que la primera pol´ıtica representar´ıa la explotaci´on y esta segunda la exploraci´on. Una vez que han sido expuestas las dos primeras pol´ıticas, las que se denominar´ıan simples, se desarrollar´an las pol´ıticas complejas. Hay un apartado dedicado para cada una de estas dos estrategias. 9.4.2. Filtro Colaborativo Basado en Vecindad Este apartado ahonda en la tercera pol´ıtica: filtro colaborativo basado en vecindad. Para desarrollar esta idea, la informaci´on ha sido obtenida de esta fuente [11]. Este algoritmo nace de la necesidad de algoritmos especializados en recomendar como los que se usan en p´aginas web, en tiendas online como Amazon, pel´ıculas de Netflix o noticias de Google. 79 Por ejemplo, se presenta el caso de Netflix. Netflix se fund´o como una empresa de alquiler de discos de v´ıdeo digital (DVD) por correo, que luego se expandi´o a la entrega de contenido en l´ınea, o tambi´en llamado streaming. Actualmente, el principal negocio de Netflix es proporcionar en l´ınea pel´ıculas, series y otros programas de televisi´on por medio de suscripciones. Netflix permite a los usuarios calificar las pel´ıculas y programas en una escala de 5 puntos. Almacena las acciones de los usuarios en t´erminos de lo que ven. Estas calificaciones se usan para hacer recomendaciones personalizadas, lo cual mejora la experiencia del usuario y puede ayudar a mejorar la lealtad y retenci´on del cliente. Para mantenerse como uno de los l´ıderes en el mercado, Netflix ha probado con muchos sistemas de recomendaci´on y ha desarrollado competiciones donde se pon´ıan a prueba distintos sistemas como el que se tratar´a ahora. Tambi´en se usaba una metodolog´ıa similar a la que se desarrolla en este sistema, entrenaba sus algoritmos con unos usuarios de entrenamiento y luego med´ıa su rendimiento con otros usuarios de evaluaci´on, o test. Adem´as, cabe se˜nalar que esta pol´ıtica se centra en analizar la informaci´on contextual del usuario. El objetivo del TFG es desarrollar bandidos contextuales multi-brazo teniendo en cuenta este tipo de datos. A pesar de que se pueden analizar las caracter´ısticas de las pel´ıculas (que son los ´ıtems), este filtro colaborativo tendr´a la perspectiva que ha sido comentada: recomendar en base al contexto del usuario. Por otro lado, hay m´as informaci´on de los usuarios en la base de datos que de los ´ıtems para realizar el sistema recomendador, por lo que es conveniente aplicar el primer enfoque. Para comenzar, se explicar´a lo que son los algoritmos de filtro colaborativo basados en vecindad, que tambi´en son denominados como algoritmos basados en memoria. Estos algoritmos parten de la premisa de que usuarios parecidos tienen un patr´on de comportamiento similar. Conductas que son semejantes se pueden observar a la hora de valorar ´ıtems, y por esto, los ´ıtems parecidos obtienen valoraciones similares de usuarios con un cierto grado de semejanza. Se llama ´ıtem a un objeto o art´ıculo que el usuario va a valorar; en Amazon el ´ıtem es un producto, como un libro, mientras que en el recomendador de Google el ´ıtem es una noticia. Hay dos tipos de algoritmos de vecindad: Filtro colaborativo basado en usuarios. En este caso, las valoraciones de usuarios similares respecto a un usuario objetivo A son usadas para hacerle recomendaciones a dicho objetivo A. Las valoraci´on que se espera que tenga A de un ´ıtem es la valoraci´on media ponderada del grupo de iguales. El proceso de ponderar la media de cada miembro del grupo de iguales ser´a explicado posteriormente. Filtro colaborativo basado en ´ıtems. En esta estrategia, como se pretenden hacer recomendaciones de un ´ıtem objetivo B, deben determinarse un conjunto S de ´ıtems, que son similares al ´ıtem B. Luego, para predecir la valoraci´on de un usuario A del ´ıtem B, se tienen en cuenta las valoraciones de ese usuario A para el ´ıtems pertenecientes al conjunto S. De esta manera, se ver´a c´omo ha evaluado A objetos an´alogos al que se le quiere recomendar. La media ponderada de dichas evaluaciones es utilizada para predecir cu´al va a ser la valoraci´on del usuario A del ´ıtem B. Una vez que han sido observadas las dos principales clases de este algoritmo, se puede apreciar la principal diferencia. En el primero tipo, se recomienda en base a valoraciones que han dado usuarios similares mientras que en la segunda clase se predice la valoraci´on del ´ıtem de acuerdo a la valoraci´on que ha dado ese mismo usuario a ´ıtems similares. L´ogicamente, en este caso debe aplicarse con un filtro colaborativo basado en usuarios para explotar su informaci´on contextual. La idea es trabajar con un grupo de iguales de un usuario objetivo, que es aquel al que se le desea recomendar una pel´ıcula. Por ello, un grupo de iguales es creado y los miembros pertenecen a los usuarios de entrenamiento. Se usar´an sus valoraciones para recomendar la mejor categor´ıa posible de pel´ıcula a usuarios objetivos, que son miembros conjunto de usuarios de evaluaci´on. Adem´as, hay dos formas de enfocar el algoritmo de vecindad: La primera forma ser´ıa predecir la valoraci´on de la combinaci´on de un usuario y un ´ıtem. Es el m´etodo m´as simple y primitivo de los sistemas recomendadores. En este caso, es necesaria la valoraci´on de un usuario, y se predice un ´ıtem. La predicci´on de esta calificaci´on se basa generalmente en las valoraciones del usuario de otros ´ıtems y de las evaluaciones de otros usuarios a este ´ıtem. La segunda alternativa es determinar los k´ıtems m´as pr´oximos, tambi´en llamados top−k´ıtems, o a partir de ahora los usuarios m´as pr´oximos, es decir, el grupo de iguales. Este enfoque opta por identificar los k usuarios o ´ıtems m´as relevantes. 80 La implementaci´on utiliza la segunda opci´on y gracias al grupo de iguales es posible hacer una recomendaci´on a otro usuario en base a su contexto. El algoritmo elegir´a un brazo u otro para un usuario en funci´on del grupo de iguales. Este ser´a el grupo de usuarios que m´as se puedan asemejar al usuario objetivo. Se toma 5 como el n´umero de usuarios de un grupo de iguales. El algoritmo desarrollado se basa en [11] y es una adaptaci´on al modelo. Utiliza los usuarios m´as similares al usuario al que el sistema recomendador pretende recomendar. Para calcular la similitud entre dos usuarios, se usa el coeficiente de la similitud del coseno. Cabe se˜nalar que el grupo de iguales van a ser del entrenamiento, y el usuario al que se le va a recomendar, pertenecer´a a la evaluaci´on. As´ı, se garantiza que en ning´un caso el propio usuario pertenezca al grupo de sus usuarios semejantes. Esta estrategia permitir´a agrupar a los usuarios que tienen un contexto parecido al usuario objetivo para realizar una recomendaci´on. Por esto, ciertamente se estar´a evaluando la relaci´on entre el contexto, los brazos y las recompensas. Si esta pol´ıtica es eficaz, se podr´a afirmar que recomendar seg´un las preferencias de usuarios con contextos parecidos (edad, trabajo y sexo) es una buena idea. Tras haber explicado los fundamentos de esta pol´ıtica, se muestra el coeficiente de similitud del coseno y c´omo se ha utilizado en el c´odigo: Similitud del coseno: CosSim(u, v) = u·v ||u||·||v|| Aqu´ı uyvson vectores, u·ves el producto escalar, y ||u|| y||v|| son las normas magnitudes de uyv, respectivamente: ||u|| =qu2 1+u2 2+. . . +u2 n En este caso, los vectores representar´ıan la informaci´on contextual de un usuario: sexo, edad y ocupaci´on. Ha sido utilizada la distancia del coseno, que se define a continuaci´on: Distancia del coseno: CosDist(u, v)=1−CosSim(u, v) donde CosSim(u, v) es la similitud del coseno entre uyv, como ha sido mostrada anteriormente. Los usuarios con menor distancia respecto a el usuario objetivo formar´an el grupo de iguales. La explicaci´on se muestra con el siguiente ejemplo. Si el usuario objetivo es un hombre de 45 a˜nos, educador, si hay otro usuario, perteneciente al conjunto de usuarios de entrenamiento, que tiene 50 a˜nos, es hombre y tambi´en educador, la distancia del coseno ser´a muy peque˜na entre estos dos usuarios. Por ello, ser´a muy probable que ese usuario pase a formar parte del grupo de iguales usuarios. Con este y cuatro usuarios m´as, se formar´ıa del grupo de iguales. Con dicho conjunto el algoritmo trabajara para maximizar la recompensa de dicho usuario objetivo. Se hace de la siguiente manera: En primer lugar, es observado el contexto xtde dicho usuario objetivo. Despu´es, son obtenidos los k= 5 usuarios que m´as se parecen usando la distancia del coseno. Para cada usuario del grupo de iguales se guardan las recompensas de cada brazo en un vector. Se calcula la recompensa media de cada brazo seg´un las recompensas de los 5 usuarios. Y finalmente, es seleccionado el brazo que tenga mejor recompensa media. El objetivo consiste en mostrar la categor´ıa de pel´ıcula que haya tenido m´as ´exito medio entre usuarios similares. Volviendo al caso anterior, si hubiera un var´on de 45 a˜nos que es educador. El algoritmo de filtro colaborativo obtiene los 5 usuarios que m´as se asemejan. Despu´es, calcula la recompensa media para cada brazo seg´un las votaciones de estos 5 usuarios an´alogos. Para ilustrarlo, se podr´ıa suponer que las pel´ıculas de action tienen una media de 0,61, las de drama 0,72, las de film-noir 0,83.... Tras haber calculado la media de cada categor´ıa, el algoritmo escoger´a la categor´ıa que m´as media, en este caso film-noir, y recomendar´a una pel´ıcula de film-noir al usuario objetivo. Realmente, se parte de la premisa de que buenos brazos en contextos anteriores ofrecer´an altos rendimientos en el contexto actual de acuerdo al grupo de iguales. Esta hip´otesis es puesta a prueba en el apartado de resultados donde se analizar´a si ha influido de manera determinante el contexto o simplemente con una pol´ıtica de 81 elegir el mejor brazo el algoritmo Exp4 obtendr´ıa buenas recompensas. Asimismo, podr´ıa suceder que el contexto sea un factor esencial para la generaci´on de recomendaciones, pero esta pol´ıtica espec´ıfica no resulte ser la m´as adecuada a tener en cuenta. Consecuentemente, recomendar seg´un las preferencias del grupo de iguales puede no ser la estrategia m´as inteligente para este caso y, por consiguiente, habr´a estrategias m´as acertadas para recomendar considerando el contexto. Al adaptar esta pol´ıtica al algoritmo Exp4 se ha tenido que realizar una funci´on que calcule las probabilidades de que un brazo sea elegido. Dicho m´etodo calcula las medias de los brazos. Si ante un contexto, la media de un brazo aies mayor que la media del resto de brazos devolver´a 1 para el brazo iya que ser´a elegido con total certeza. Por el contrario, si la media no es la m´as alta, devolver´a 0. Como se puede observar, seleccionar´a siempre el brazo que m´as media tenga para el grupo de iguales. El pseudoc´odigo del algoritmo ser´ıa el siguiente: Algoritmo 9.15 Filtrado colaborativo con algoritmo de vecindad. 1: Al inicializar: Se almacenan los contextos de los usuarios de entrenamiento, con sus brazos activados y sus recompensas asociadas. 2: for cada ronda t= 1,2, . . . do 3: Se observa el contexto xt∈Xde un usuario. 4: Para todos los contextos de los usuarios de entrenamiento ∀xi∈Xtrain, se calcula la distancia del coseno respecto a xt:CosDist(xt, xi)=1−CosSim(xt, xi). 5: Se obtienen los usuarios del grupo de iguales, los kcontextos m´as similares a xt, que corresponden a las kdistancias m´as peque˜nas dentro de los usuarios de entrenamiento ordenados por CosDist(xt, xi) de menor a mayor. 6: Se calcula la recompensa media para todos los brazos ∀a∈Ade las valoraciones del grupo de iguales. 7: Se selecciona el brazo atcon mejor recompensa media. 8: end for Por ´ultimo, debe mencionarse alguno de los factores por los cuales se ha decidido implementar este experto. Es un algoritmo que permite la personalizaci´on. Los sistemas de filtrado colaborativo proporcionan recomendaciones personalizadas basadas en el comportamiento de usuarios similares. A diferencia de otras t´ecnicas de recomendaci´on como el filtrado basado en el contenido, el filtrado colaborativo basado en usuarios no requiere ninguna informaci´on espec´ıfica sobre los´ıtems, esto hace que encaje perfectamente con el modelo. Su flexibilidad tambi´en es un aspecto a se˜nalar ya que por ejemplo, se puede establecer arbitrariamente el n´umero de kvecinos as´ı como otros ajustes del modelo. Tambi´en, un punto a favor es que es una pol´ıtica que aporta mucho valor a la investigaci´on. Esta estrategia se est´a trabajando desde una perspectiva diferente y permite estudiar algoritmos especializados en sistemas de recomendaci´on. 9.4.3. Red Neuronal como Bandido Contextual Por ´ultimo, este apartado se adentrar´a en la pol´ıtica final que es una de las ideas m´as estimulantes con la que se ha trabajado en esta implementaci´on. Esta pol´ıtica que ha necesitado de muchas pruebas, hace uso de una red neuronal como si fuera un bandido contextual. Para implementarla, se utiliza Tensorflow, y Keras, en Python. Estas herramientas permiten trabajar con una red neuronal de manera flexible y adaptarla como un bandido. Hay que se˜nalar que la idea es propia de los autores del trabajo. Dicha idea ha sido posible materializarla gracias a las fuentes mencionadas y a los conocimientos adquiridos con este trabajo. La informaci´on con la que se ha trabajado para desarrollar la red neuronal y los conceptos te´oricos detr´as de la explicaciones est´an en [20]. Las redes neuronales se implementan adecuadamente gracias a dicha fuente. El conocimiento adquirido en este campo se traslada al marco de los bandidos multi-brazo. Estos modelos pueden aportar mucho valor por los siguientes motivos: Son algoritmos que ofrecen buenas alternativas porque tienen capacidad de manejar grandes cantidades de datos y caracter´ısticas. En este caso, hay muchos usuarios y 1 mill´on de valoraciones de pel´ıculas, por lo que se realizan muchas recomendaciones y esto es un punto a favor de las redes neuronales. 82 Las redes neuronales tienen la habilidad de establecer relaciones interesantes entre m´ultiples caracter´ısticas. En este sistema de recomendaci´on, se tienen en cuenta el contexto como datos de entrada y las recompensas (valoraciones de los usuarios). Estos algoritmos tienen la capacidad de extraer complejas relaciones entre las variables con las que est´an trabajando para optimizar los resultados. La red neuronal se adapta convenientemente al modelo. Esto es debido a que como es necesario entrenar a los expertos, es la ocasi´on ideal para crear una red neuronal con los datos de entrenamiento. De este modo, para la fase de evaluaci´on habr´a una red totalmente entrenada y ser´a posible evaluar su rendimiento. De manera resumida, la aplicaci´on de una red neuronal a un problema de bandido multi-brazo se hace para que esta red modele la relaci´on entre el contexto y las recompensas de los brazos. La entrada a la red neuronal es la informaci´on contextual y la salida es una distribuci´on de probabilidades sobre los brazos de manera que se elige un brazo en funci´on de esta distribuci´on. Esta pol´ıtica ofrecer´a otro enfoque diferente para capturar las relaciones entre el contexto y los brazos. Al contrario que la tercera pol´ıtica, filtro colaborativo usando el algoritmo de vecindad, las redes neuronales calcular´an distintas conexiones entre contextos, brazos y recompensas sin utilizar el grupo de iguales. Este contraste entre las dos pol´ıticas ser´a de gran utilidad para analizar los resultados finales y entender c´omo es m´as conveniente considerar el contexto en este caso de uso. La idea ha sido utilizar una red neuronal multiclase. Dicha red tiene 18 clases o neuronas en su ´ultima capa. Es decir, una clase para cada brazo. Para un contexto la red neuronal devuelve las probabilidades de lo bueno que ser´a cada brazo. Esto significa que dado un contexto, la red neuronal ofrecer´a probabilidades para cada brazo. La suma de todos los brazos dar´a 1, y hay 18 probabilidades, una por cada brazo. En las primeras implementaciones la red neuronal eleg´ıa aleatoriamente en esta funci´on de probabilidad pero dado que las recompensas son IID (no hay un adversario), se obtendr´an recompensas m´as altas si es seleccionado el brazo con mayor probabilidad. No es imprescindible escoger el brazo de acuerdo a la aleatoriedad porque las recompensas no son adversarias, sino que son IID. Por ello, tras varias pruebas, la red neuronal finalmente escoge siempre el brazo con mayor probabilidad. Una vez explicada c´omo act´ua la red neuronal como bandido multi-brazo, se detalla c´omo es exactamente esta red y porqu´e ha sido dise˜nada de una determinada manera. El trabajo se ha realizado con una red de tres capas densas, que est´an completamente conectadas. Dichas capas tienen 120, 70 y 18 neuronas respectivamente. Esto es debido a que se ha implementado un modelo complejo, con muchas neuronas. Seg´un la documentaci´on expuesta en [20] se ha optado por esta estrategia con el objetivo de crear un modelo complejo a˜nadiendo regularizaci´on. Esto es debido a que al tener un modelo complejo (muchas neuronas), el modelo alcanza mucha varianza porque da demasiado peso a los par´ametros del modelo y se produce un sobreajuste respecto a los datos de entrenamiento. Para evitar dicho sobreajuste, se usa la regularizaci´on. El prop´osito fundamental del modelo es realizar recomendaciones de calidad con los usuarios de evaluaci´on, no con los de entrenamiento. El fin es crear un modelo que generalice bien. Por ello, todas las medidas que se han tomado han sido de acuerdo a este objetivo. Por ejemplo, se ha ajustado la tasa de aprendizaje, la regularizaci´on, las funciones de activaci´on y la p´erdida para garantizar esta generalizaci´on. Aunque aqu´ı se comentan los hiperpar´ametros elegidos, se han hecho pruebas y simulaciones con m´ultiples opciones. Debido a esto, se mostrar´an las elecciones finales que mejor optimizan la red. El proceso de selecci´on de estos par´ametros ha sido iterativo y ha requerido de muchas simulaciones para maximizar la recompensa. La elecci´on de la tasa de aprendizaje ha sido de 0,05. Este es un hiperpar´ametro crucial en las redes neuronales que determina c´omo de r´apido se quieren actualizar los pesos de este modelo. Si la tasa de aprendizaje fuera muy grande, el modelo puede converger muy r´apidamente. Sin embargo, como es posible entrenar al modelo con muchos datos de entrenamiento, se ha establecido una tasa igual a 0,05 para que converga de manera adecuada y aprenda correctamente. Para llevar a cabo la regularizaci´on, se ha utilizado una regularizaci´on L2 que previene el sobreajuste. Esta regularizaci´on a˜nade una penalizaci´on a los pesos grandes del modelo para que no se ajuste demasiado a los datos de entrenamiento disminuyendo la varianza del modelo y mejorando la generalizaci´on. El valor elegido de la regularizaci´on, λ, ha sido 0,015 en la capa de entrada y la capa intermedia. Respecto a las funciones de activaci´on, relu ha sido la funci´on de activaci´on elegida para la capa de entrada y la oculta (la del medio). Esta funci´on ayuda a hacer m´as r´apido el proceso de descenso de gradiente, que es la forma en la que se entrena la red. En la capa de salida es utilizad la funci´on de activaci´on softmax que se usa a menudo en la clasificaci´on multiclase, que en este caso se realiza con 18 clases o brazos. 83 Figura 35: Red neuronal como bandido multi-brazo. Tambi´en hay que mencionar que se han usado unas ´epocas con un valor de 170. El objetivo es que la red neuronal entrene lo suficiente y pueda converger adecuadamente sin sobrepasarse con los datos de entrenamiento. Despu´es de muchas pruebas y depuraciones alrededor de esta cifra se encuentran resultados correctos. Finalmente, el modelo se compila con la p´erdida de “categorical crossentropy” y el optimizador “Adam”. Categorical corssentropy es una funci´on de p´erdida com´unmente usada en problemas de clasificaci´on multiclase. Adam es un algoritmo de optimizaci´on que se utiliza para actualizar los peso de la red en funci´on de los datos de entrenamiento. La tasa de aprendizaje se pasa a Adam que permite controlar la velocidad a la que el modelo aprende. La figura 35 muestra c´omo se ver´ıa la red neuronal de manera simplificada. Hay tres capas: La primera capa de entrada de 120 neuronas, la capa intermedia (u oculta) 70 neuronas, y la capa de salida de 18 neuronas (una para cada brazo). Como se puede apreciar, las entradas, son el contexto del usuario mientras que cada una de las neuronas de salida representar´ıa un brazo. La figura es de gran ayuda ya que permite visualizar la estructura de la red Por ejemplo, durante el entrenamiento, si se tienen el brazo 2 con una recompensa de 0.8 para un contexto xt, se entrenar´ıa la red neuronal con el contexto como entrada. En la salida, al brazo 2 se le asigna una recompensa de 0.8, mientras que al resto de brazos se les da una recompensa de 0. De esta manera solo se actualizar´an los brazos activados en cada ronda. Como cada pel´ıcula tiene varias categor´ıas, cuando la red es entrenada con la valoraci´on de un usuario, se har´a varias veces. Una vez para cada categor´ıa perteneciente a la pel´ıcula elegida. En cada una de estas veces ser´a usada la misma recompensa para ese brazo y el mismo contexto como entrada. Si en el ejemplo mencionado tambi´en se activar´a el brazo 7, porque la pel´ıcula pertenece a ambos g´eneros, tanto el brazo 2 como el brazo 7 ser´ıan actualizados con una recompensa de 0.8. Igual que antes, el resto de brazos tendr´ıan una recompensa de 0. A continuaci´on, se muestra un algoritmo que ilustre cu´ales son los pasos a seguir de la red neuronal. Hay una exposici´on de estos dos pseudoc´odigos, uno para el entrenamiento y otro para la evaluaci´on: Al ver la estructura del c´odigo, los pasos que sigue la red neuronal quedan muy claros. Mediante este entrenamiento consigue establecer relaciones entre contextos y las recompensas asociadas a los brazos activados. Hay que tener en cuenta que una pel´ıcula tiene varias categor´ıas y hay retroalimentaci´on parcial, por lo que obtiene la recompensa para varios brazos, los brazos activados que corresponden a los g´eneros de la pel´ıcula seleccionada. Aquellos brazos que tengan buenas recompensas ser´an elegidos con mayor probabilidad durante la siguiente etapa. Por lo tanto, este entrenamiento es fundamental y en funci´on de c´omo se realice la red neuronal ofrecer´a unos buenos rendimientos o no. Hay que mencionar que en el c´odigo la red neuronal es entrenada al final del entrenamiento, es decir, no 84 Algoritmo 9.16 Red neuronal en el entrenamiento. 1: for cada ronda t= 1,2, . . . do 2: Se observa el contexto xt∈Xde un usuario. 3: Se recibe el brazo elegido, que tambi´en es brazo activado, a∈Ay los brazos activados ai, aj... ∈A. 4: Para cada brazo activado a∈A, se entrena la red con xt(como variable de entrada), y con la recompensa obtenida rtcomo salida de ese brazo. El resto de brazos no activados, a∈Aand !activado, les asigna una recompensa rt= 0. 5: end for entrena ronda a ronda como se hace en un bandido convencional que se actualizan los pesos tras observar una recompensa, sino que entrena tras haber pasado por todos los usuarios de entrenamiento. Esto se hace para ahorrar costes de tiempo y ejecutar el algoritmo m´as r´apidamente. Por lo tanto, entrenar´a con todos los usuarios de una sola vez. Algoritmo 9.17 Red neuronal en la evaluaci´on. 1: Al inicializar: Entrena la red neuronal con los usuarios de entrenamiento. 2: for cada ronda t= 1,2, . . . do 3: Se observa el contexto xt∈Xde un usuario. 4: Se calcula una distribuci´on de probabilidades para los Kbrazos dado ese contexto xt. 5: Se selecciona el brazo atcon mayor probabilidad. 6: end for Despu´es de haber entrenado dicha red neuronal, se puede considerar que ya es una experta y el algoritmo Exp4 la utilizar´a como una de sus pol´ıticas. Como se ha recalcado antes, la red neuronal no entrena durante la evaluaci´on del Exp4 porque ya es una experta y el objetivo es observar cu´ales son las mejores y peores pol´ıticas. Por ello, en esta fase de evaluaci´on la red no ser´a actualizada. En dicha etapa de evaluaci´on, la red neuronal calcular´a una distribuci´on de probabilidades dado un contexto teniendo en cuenta los datos con los que hab´ıa sido entrenado anteriormente. Aqu´ı entra en juego las relaciones que puede deducir entre los contextos y la recompensas. Las recomendaciones ser´an de calidad en funci´on de la capacidad de la red neuronal para capturar la relaci´on entre estas variables. Por otro lado, dado un contexto, la red neuronal tendr´a la probabilidad de 1 de elegir un brazo si es el brazo que m´as probabilidades tiene. De este modo, el resto de brazos tienen una probabilidad de 0 de ser elegidos. Adem´as de estas funciones, la red neuronal tambi´en debe ser capaz de dar la probabilidad de elegir un brazo dado un contexto. Esto es necesario porque el algoritmo Exp4 necesita esta probabilidad para ajustar el peso de sus pol´ıticas por lo que se ha tenido que implementar este m´etodo. La red neuronal devolver´a 1 si el brazo tiene la mayor probabilidad de ser el mejor y se elegir´a con certeza, mientras que devolver´a 0 en caso contrario. Por ´ultimo, se ha podido elegir entre dos estrategias para la red neuronal cuando selecciona un brazo a recomendar: elegir el brazo aleatoriamente de acuerdo a la distribuci´on de probabilidades o seleccionar el brazo con mayor probabilidad. Para escoger la mejor opci´on y optimizar la red neuronal, se ha realizado la simulaci´on de una prueba para el algoritmo Exp4 con ambas estrategias y se seleccionar´a la que mejor resultados de. La resultante ser´a utilizada como la pol´ıtica de red neuronal y competir´a contra la pol´ıtica del mejor brazo, la pol´ıtica ´ Epsilon-Avaricioso que explora y la tercera pol´ıtica del filtro colaborativo basado en algoritmos de vecindad. 85 Figura 36: Comparaci´on de redes neuronales. Esta simulaci´on se ha realizado para solo un 30 % de los usuarios pero los resultados son reveladores. La red neuronal 1 es la que elige el brazo aleatoriamente de acuerdo a una distribuci´on donde cada brazo tiene una probabilidad de ser elegido seg´un lo bueno que sea y la red neuronal 2 elige simplemente el brazo que mayor probabilidad tenga sin a˜nadir aleatoriedad. Se observa en la figura 36 que la red neuronal 1 es premiada por el Exp4 y obtiene mejores pesos ya que sus recompensas son mejores. Al contrario, la red neuronal 2 consigue peores resultados y su peso va disminuyendo en contraste con la otra red neuronal. Debido a este an´alisis, en la simulaci´on final, se utilizar´a una red neuronal que elija el brazo con mayor probabilidad sin tener en cuenta la aleatoriedad. Hay que recordar que esto no es un problema porque las recompensas son IID y significa que no hay un adversario. Esto corresponde con la secci´on 5. 9.5. Resultados En este ´ultimo apartado se analizan los resultados por medio de gr´aficas y se ofrecen las conclusiones oportunas respecto a cada figura. Antes de comentar los resultados finales, se expone una simulaci´on inicial que es esclarecedora para desarrollar algunas hip´otesis en este sistema recomendador. Los resultados estudiados corresponden a la fase de evaluaci´on del Exp4 en cualquier caso. 9.5.1. Resultados Iniciales Al realizar este sistema de recomendaci´on se ha llegado a muchas conclusiones pero antes, hay unos resultado preliminares que deben ser comentados ya que se llega a una conclusi´on enriquecedora para el planteamiento en general. En primer lugar, hay que se˜nalar que las mejores pol´ıticas han sido siempre dos: la red neuronal y la pol´ıtica de explotaci´on, de elegir el mejor brazo. La pol´ıtica de exploraci´on (´ Epsilon Avaricioso con un ´epsilon de 0.95) no ha obtenido buenos resultados, como se pod´ıa esperar no es buena idea elegir casi siempre aleatoriamente una pel´ıcula. Sin embargo, lo que s´ı es sorprendente es el mal rendimiento de la pol´ıtica de filtro colaborativo. Se pod´ıan tener muchas expectativas puestas en este experto y no ha tenido ninguna relevancia en las simulaciones, alcanzando siempre pesos ´ınfimos y siendo descartada completamente por el Exp4. Por otro lado, tambi´en hay que destacar el buen rendimiento de la pol´ıtica de elegir siempre el mejor brazo. Es algo que llama la atenci´on ya que esta pol´ıtica no ha tenido en cuenta el contexto, sino que simplemente elige la categor´ıa que mejor nota media haya tenido durante la fase de entrenamiento. Este aspecto es revelador ya que ha llegado a superar a una mala red neuronal. A continuaci´on, se muestra el gr´afico de una red neuronal, con unos hiperpar´ametros no apropiados, y consiguientemente, una mala red neuronal frente a la pol´ıtica del mejor brazo. En este caso la pol´ıtica de mejor brazo generalmente es la mejor estrategia para el algoritmo Exp4. 86 Esto expone unos resultados sorprendentes. Incluso al final de la simulaci´on, la pol´ıtica del mejor brazo acaba ganando la partida completamente a la red neuronal. La gr´afica en cuesti´on es la siguiente: Figura 37: Primera evaluaci´on Exp4. Tal y como se ha comentado, los resultados no son los esperados: el filtro colaborativo es una total decepci´on y elegir siempre el mejor brazo parece que puede llegar a ser una alternativa a tener en cuenta ya que acaba siendo el experto favorito por el Exp4. No obstante, tras obtener estos resultados, es deducible que se pueden mejorar los hiperpar´ametros de la red neuronal y ver si realmente puede superar a todas las pol´ıticas con unos par´ametros adecuados o por lo menos mantenerse como una buena opci´on a largo plazo. Cabe se˜nalar que en esta simulaci´on la red neuronal ten´ıa 64 neuronas, 60 neuronas y Kneuronas (18), una tasa de aprendizaje de 0,001 y unos ´epocas de 10, por lo que se ha intentando mejorar estos aspectos con el objetivo de conseguir la mejor red neuronal posible para ver si es una pol´ıtica viable. Tambi´en es se˜nalable que solamente la red neuronal es entrenada con una sola ronda de entrenamiento, con una recomendaci´on para cada usuario de entrenamiento, por lo que no contaba con tanta informaci´on. Por lo tanto, se puede concluir en estos primeros resultados que aunque pudiera parecer un buen experto, la pol´ıtica de filtro colaborativo es superada de manera superlativa por la pol´ıtica del mejor brazo, as´ı como tambi´en pasa con la pol´ıtica del ´ Epsilon-Avaricioso con un ´epsilon de 0,95 (una pol´ıtica que explora). Estas dos pol´ıticas ya han quedado en evidencia y se ha demostrado por el Exp4 que no son pol´ıticas dominantes en este sistema. Adem´as, para una red neuronal que podr´ıa denominarse compleja, no se han conseguido buenos resultados frente a la pol´ıtica del mejor brazo, con regularizaci´on, muchas neuronas, optimizaci´on con Adam y 10 ´epocas. Es necesario modificar algunos de los aspectos de la red y debe ser entrenada m´as, con m´as ´epocas. Consecuentemente, se ha tratado de mejorar la red neuronal para que obtenga mejores resultados y comprobar si es capaz de rendir mejor y mantenerse como un alternativa viable. 9.5.2. Resultados Finales Tras haber obtenido unos resultados preliminares en el apartado anterior 9.5.1, se proceder´a a detallar los aspectos tenidos en cuenta para mejorar la red neuronal con el objetivo de ver si una red m´as optimizada para este caso obtendr´ıa mejores resultados. Por otro lado, se parte de la base de que las otras dos pol´ıticas van a ser irrelevantes y el an´alisis debe basarse en la pol´ıtica de elegir siempre el mejor brazo y la red neuronal. Se prueba con unos hiperpar´ametros que fueron lo suficientemente buenos para que la red neuronal superase a la pol´ıtica de mejor brazo. Esta red ten´ıa unas 200 ´epocas, 120 neuronas en la primera capa, 60 en la siguiente, la tasa de aprendizaje ya se mantuvo 0,05. La ´ultima capa siempre debe ser de 18 neuronas. Al obtener tan buenos resultados, se aumenta a´un m´as la complejidad de la red, sin embargo se obtuvo sobreajuste porque la red neuronal ya no superaba a la pol´ıtica del mejor brazo. Por lo tanto, ha debido generalizar mal. La conclusi´on a la que se llega es que se hab´ıa producido un sobreajuste y hab´ıa que encontrar un punto medio para que la red neuronal no sobreajustar´a y se consigan las mejores recompensas. 87 Los par´ametros que finalmente han sido mantenidos de la red neuronal son los siguientes: Se ha utilizado una tasa de aprendizaje de 0,05, una tasa de regularizaci´on de 0,015, unos ´epocas de 170, unas neuronas de 120 en la primera capa, 70 en la segunda y 4 rondas de entrenamiento. Los resultados obtenidos para Exp4 con esta red neuronal mejorada y el resto de pol´ıticas igual que antes son los siguientes: Figura 38: Evaluaci´on Exp4. Con esta figura 38, se aprecia que al optimizar la red se convierte en una pol´ıtica dominante para el Exp4 y que puede ayudar a mejorar la recompensa media. Por el contrario, se sigue observando que las pol´ıticas de un ´ Epsilon-Avaricioso que explora o un filtro colaborativo siguen sin ser buenos expertos. Por otro lado, elegir el mejor brazo sigue siendo una alternativa que puede ser ventajosa para el algoritmo tal y como refleja la figura. Durante tres cuartas partes de la simulaci´on la red neuronal es la pol´ıtica m´as acertada. En las rondas finales se produce una alternancia entre la pol´ıtica de elegir el mejor brazo y la red neuronal. Debido a esto, se puede deducir que ambos expertos ofrecen recomendaciones buenas para el algoritmo Exp4 y tiene en cuenta a los dos. Posteriormente se ofrece la recompensa media de la simulaci´on a lo largo de las rondas, pero su valor final es de 0.7536 por lo que se puede estar satisfechos con el desempe˜no del Exp4. Respecto a la pol´ıtica de filtro colaborativo que utiliza el algoritmo de vecindad, se puede llegar a la siguiente conclusi´on: los resultados son claramente negativos, esto indica que dicha pol´ıtica no captura adecuadamente las relaciones entre el contexto y los brazos para maximizar la recompensa. Por ello, se puede deducir que en este caso particular no es buena idea recomendar de acuerdo con las preferencias del grupo de iguales. A pesar de que el grupo de iguales tiene un contexto similar al usuario objetivo, si el sistema recomendador tiene en cuenta las preferencias de dicho conjunto, los resultados son malos. Sin embargo, esto no sugiere que el contexto no aporte informaci´on valiosa. Aunque el algoritmo de filtrado colaborativo no haga recomendaciones de calidad, la red neuronal s´ı que obtiene buenas recompensas y tiene en consideraci´on el contexto. Sin embargo, la pol´ıtica de la red neuronal crea relaciones distintas entre el contexto y los brazos seleccionados. Por lo tanto, con un enfoque diferente como el que utiliza la red neuronal si que se puede aprovechar la informaci´on contextual para mejorar las recompensas. En definitiva, la estrategia ´optima en el sistema recomendador es combinar la pol´ıtica de la red neuronal y la del mejor brazo. El Exp4 aprovechar´a ambas estrategias durante la simulaci´on. Para ello, regular´a los pesos de estas dos pol´ıticas castigando a la que ofrezca malas recompensas y dando oportunidades a la otra. Har´a esto de forma indefinida conforme avanzan las rondas. Intercalar dichos expertos se supone que es la mejor alternativa. Por lo tanto, para algunos usuarios el sistema recomendador sugerir´a el mejor brazo, una opci´on bastante segura, mientras que para otros usuarios recomendar´a un g´enero seg´un la recomendaci´on de la red neuronal. Esta pol´ıtica tiene en cuenta el contexto y personalizar´a la recomendaci´on adapt´andose a los datos contextuales del usuario para ofrecer una recomendaci´on ´unica. Consecuentemente, el sistema recomendador encuentra un equilibrio entre sugerir siempre el mejor g´enero y hacer recomendaciones personalizadas en base al contexto. Esto consiste en la coordinaci´on del experto del mejor brazo y la red neuronal. La mayor´ıa de veces el sistema recomendar aconsejar´a el brazo elegido por la red neuronal, que escoge dicho brazo adapt´andolo al 88 Para ello, se ha tenido que estudiar, en cierta medida, desde las redes neuronales que son una instancia del aprendizaje autom´atico, hasta algoritmos de recomendaci´on como el filtro colaborativo especializado en sistemas recomendadores. Tambi´en se ha trabajado con otros bandidos estoc´asticos como el ´ Epsilon-Avaricioso. Este trabajo ha sido muy estimulante, aunque necesitado de mucho trabajo al haber tratado demasiado contenido. Como resultado, el sistema recomendador creado representa la puesta en pr´actica de m´ultiples conocimientos y mucho trabajo en distintos campos, requiriendo el estudio de m´ultiples algoritmos. Un punto que ha presentado mucha dificultad ha sido modelar una red neuronal como bandido multi-brazo contextual. Para esto, se ha tenido que estudiar a fondo el problema y adaptar esta soluci´on, que ha resultado en algo muy interesante. Cabe destacar que la red neuronal ha requerido de un gran esfuerzo para optimizar sus par´ametros. Por ´ultimo, tambi´en ha sido necesario aprender a adaptar la informaci´on de una base de datos para que sea tratable por el modelo. Los resultados han sido analizados por medio de la estad´ıstica. Estudiar los resultados estad´ısticamente ha sido un aspecto crucial, no solo para entender un sistema recomendador, sino tambi´en para que los resultados obtenidos en este sistema puedan ser considerados por implementaciones venideras. En definitiva, ambos autores han realizado un esfuerzo conjunto durante el desarrollo de todo el trabajo. Los dos han tocado todos los puntos involucrados en este proyecto. Se ha conseguido sacar partido del buen equipo formado, generando as´ı una gran oportunidad para profundizar en este complejo aspecto del aprendizaje autom´atico. Fruto de esta conexi´on ha surgido un equipo din´amico en el que los roles han ido variando con el tiempo gracias a la versatilidad de sus integrantes. Adem´as, sendos autores han trabajado en todas las fases de desarrollo de las aplicaciones pr´acticas. Esto ha permitido exprimir al m´aximo sus virtudes y aprovechar la sinergia creada para construir un proyecto muy s´olido, que aporta mucho valor debido a su complejidad y que conlleva mucho esfuerzo por detr´as. Debido a esto, se puede afirmar que ha salido a relucir un gran trabajo de manera exitosa, ofreciendo muchas implementaciones y estudios de suma relevancia en el campo de los bandidos multi-brazo y, consecuentemente, aportando conocimientos al aprendizaje por refuerzo. 95 11. Conclusiones Este trabajo cumple con creces las expectativas iniciales y los objetivos planteados. Por un lado, se trabajan adecuadamente los conceptos te´oricos fundamentales de los bandidos y sus algoritmos, y se hace ´enfasis en los estoc´asticos y antagonistas para abarcar correctamente el marco de los bandidos contextuales. Por otro lado, los bandidos contextuales han sido estudiados en profundidad incluyendo el extenso y exhaustivo desarrollo de m´ultiples aplicaciones pr´acticas. Esta puesta en pr´actica de los bandidos contextuales cubre diferentes ´ambitos y puede ser un punto de partida para el despliegue de aplicaciones reales en la sociedad actual. Adem´as de haber desarrollado algoritmos en distintos campos, tambi´en se expone su metodolog´ıa al detalle para hacerlos comprensibles. Con esto en consideraci´on, los resultados obtenidos son m´as que satisfactorios. Han salido a relucir las ventajas de los bandidos multi-brazo contextuales ya que son ciertamente ´utiles en diversas aplicaciones pr´acticas. En este trabajo hay diferentes implementaciones que cubren el ´ambito financiero y de las inversiones y tambi´en aspectos fundamentales del mundo digital como los sistemas recomendadores. Estos temas tienen un claro impacto en la sociedad moderna. Adem´as, se ha estudiado una variante en la que los algoritmos trabajan en un juego contextual dando lugar a otro posible uso de estos bandidos. Debido a su versatilidad en una amplia gama de campos y su escalabilidad para desarrollar construcciones de software, que no son triviales y permiten explorar problemas muy complejos, los bandidos contextuales son una rama tremendamente significativa del aprendizaje por refuerzo. Permiten obtener soluciones pragm´aticas a problemas del mundo real encontrando un correcto equilibrio entre la exploraci´on y explotaci´on para obtener buenos rendimientos que reflejan la eficacia de estos algoritmos. Esto ha quedado demostrado de manera notoria a trav´es de las implementaciones ofrecidas en este trabajo. 12. Conclusions This work more than fulfills the initial expectations and the stated objectives. On the one hand, the fundamental theoretical concepts of bandits and their algorithms are adequately worked out, and emphasis is placed on stochastics and adversarial bandits to properly cover the framework of contextual bandits. On the other hand, contextual bandits have been studied in depth including the extensive and exhaustive development of multiple practical applications. These implementations of contextual bandits cover different domains and can be a starting point for the deployment of real applications in today’s society. In addition to having developed algorithms in different fields, their methodology is also exposed in detail to make these algorithms understandable. With this in consideration, the results obtained are more than satisfactory. The advantages of contextual multi-armed bandits have come to light as they are certainly useful in various practical applications. In this work, different implementations are covering the financial and investment domain and also fundamental aspects of the digital world such as recommender systems. These topics have a clear impact on modern society. In addition, a variant has been studied in which the algorithms work in a contextual game giving rise to another possible use of these bandits. Because of their versatility in a wide range of domains and their scalability for developing software constructs, which are non-trivial and allow the exploration of very complex problems, contextual bandits are a tremendously significant branch of reinforcement learning. They enable the discovery of pragmatic solutions to real-world problems by finding the right balance between exploration and exploitation to obtain good performances that reflect the effectiveness of these algorithms. This has been notoriously demonstrated through the implementations offered in this work. 96 13. Anexo 13.1. Depuraci´on de la Evoluci´on de Pesos de los Bots con Probabilidades Individuales de Elecci´on de Brazo de 100 % y 0 % La depuraci´on “casera” comentada en la secci´on 8.3.1 se presenta a continuaci´on. Adem´as, la figura 45 vuelve a exponer la evoluci´on de los expertos, tambi´en reflejada en dicha secci´on. Ronda: 292 C´alculo de variables Brazo elegido por el algoritmo: P.LARGA Recompensa obtenida por el algoritmo = 0.1 Coste para los bots que han recomendado el brazo P.LARGA = 1 - 0.1 = 0.9 Probabilidad Individual de cada bot de elegir el brazo que elija = 100 % Probabilidad Conjunta entre los bots de elegir P.LARGA = = 100 % * 1.42e-008 + 100 % * 4.86e-259 = 1.421292709769473e-08 Obtenci´on de costes estimados Prob[Elegir Bot PCortas] = 2.76e-252 |Elige brazo: MANTENER |Coste estimado: 0.0 Prob[Elegir Bot PLargas] = 1.42129271e-008 |Elige brazo: P.LARGA |Coste estimado: 63322635.36 Prob[Elegir Bot PCambiantes] = 4.86e-259 |Elige brazo: P.LARGA |Coste estimado: 63322635.36 Prob[Elegir Bot Cruce de MM] = 8.10e-002 |Elige brazo: MANTENER |Coste estimado: 0.0 Prob[Elegir Bot RSI] = 9.96e-004 |Elige brazo: MANTENER |Coste estimado: 0.0 Prob[Elegir Bot MACD y BB] = 2.71e-005 |Elige brazo: MANTENER |Coste estimado: 0.0 Prob[Elegir Bot Todo] = 9.18e-001 |Elige brazo: MANTENER |Coste estimado: 0.0 Actualizaci´on de pesos y de la distribuci´on de probabilidad Nuevos Pesos de los bots: [1.e+250, 1.e-001, 1.e-001, 1.e+250, 1.e+250, 1.e+250, 1.e+250] Nuevas Probabilidades, respectivamente: [2.e-001 2.e-252 2.e-252 2.e-001 2.e-001 2.e-001 2.e-001] Figura 45: Evoluci´on de los Pesos de los Expertos con γ= 0,2. Como se puede observar en la depuraci´on, en la ronda 292, el algoritmo ha fallado al elegir el mismo brazo 97 que han recomendado dos de los tres bots con menores probabilidades de ser escogidos. Esto ha provocado que la probabilidad conjunta de elegir dicho brazo sea baj´ısima. Por consiguiente, el coste estimado para los bots que han sugerido la opci´on de comprar ha resultado ser elevad´ısimo. Lo normal es obtener costes estimados entre los valores 0 y 5, y en este caso el valor es 63322635.36. La obtenci´on de tan elevados costes estimados por parte de los bots de comercio expertos en posiciones largas y posiciones cambiantes ha provocado que su probabilidad de ser elegidos en la siguiente ronda sea reducida a pr´acticamente 0. Tambi´en, ha conllevado la distorsi´on de las probabilidades de elegir el resto de bots, repartiendo entre estos la probabilidad total restante de forma igualitaria. Concretamente, como son siete bots en total, y dos de ellos han recibido una probabilidad de casi 0, a los cinco restantes se les ha otorgado una probabilidad cercana al 20 %. En la figura 45, se puede confirmar esta situaci´on al contemplar que los pesos de estos cinco bots, tras la ronda 292, parten desde el mismo punto (0.2 en el eje de las ordenadas). En cambio, los pesos de los bots perjudicados adquieren el valor m´as bajo, sin poder remontar la situaci´on en lo que resta de rondas. 13.2. Resultados Sistema Recomendador Pel´ıculas Primero se ofrecen otras dos simulaciones del Exp4 con las mejoras hechas en la red neuronal para que se puedan observar otras ejecuciones como referencia. La red neuronal y elegir el mejor brazo son siempre las mejores pol´ıticas y al mostrar otras pruebas se confirma esta teor´ıa. Figura 46: Simulaci´on auxiliar 1. En esta figura 46 se hab´ıa intentando usar m´as neuronas: 120 en la primera capa (igual que antes) y 73 en la segunda. Hay una tasa de regularizaci´on de 0.015 en ambas capas y son aumentadas las ´epocas hasta 200. 98 Figura 47: Simulaci´on auxiliar 2. Esta segunda simulaci´on auxiliar se realiz´o con los par´ametros finales de la red neuronal, y puede servir para ver c´omo difieren los resultados seg´un lo que se equivoquen los expertos: la red neuronal y la pol´ıtica del mejor brazo. En todas las simulaciones se puede apreciar que la red neuronal tiene un buen comportamiento y es una pol´ıtica a tener en cuenta siempre. Adem´as, tras haber ofrecido otras simulaciones, se muestran algunos de los resultados obtenidos en el sistema recomendador de pel´ıculas que hace uso de un bandido contextual de clase pol´ıtica. Los mapas de calor para los grupos de edad faltantes son presentados a continuaci´on: Figura 48: Mapa calor de recompensas por brazo para personas de menos de 18 a˜nos. 99 Figura 49: Mapa calor de recompensas por brazo para personas de entre 18 y 24 a˜nos. Figura 50: Mapa calor de recompensas por brazo para personas de entre 25 y 34 a˜nos. 100 Figura 51: Mapa calor de recompensas por brazo para personas de entre 35 y 44 a˜nos. Figura 52: Mapa calor de recompensas por brazo para personas de entre 50 y 55 a˜nos. 101 Figura 53: Mapa calor de recompensas por brazo para personas de m´as de 56 a˜nos. Tambi´en se adjuntan otras figuras auxiliares 54 y 55 que no se a˜nadieron en la secci´on 9: Figura 54: Recompensas para la cada grupo de edad. 102 Figura 55: Gr´afico de contorno de la edad y la recompensa. 103 Referencias [1] W. Thompson. Sobre la probabilidad de que una probabilidad desconocida supere a otra en vista de la evidencia de dos muestras. Biometrika 1933. [2] Aleksandrs Slivkins. Introduction to Multi-Armed Bandits, 2019. [3] Tor Lattimore and Csaba Szepesv´ari. Bandits Algorithms. Cambridge University Press, 2020. [4] S´ebastien Bubeck and Nicol`o Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, 2012. [5] Djallel Bouneffouf, Irina Rishz. A Survey on Practical Applications of Multi-Armed and Contextual Bandits, 2019. [6] Peter Auer, Nicol`o Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The non-stochastic multi-armed bandit problem, 2012. [7] Reinforcement Learning by Richard S. Sutton and Andrew G. Barto. The MIT Press. Cambridge, 2018. [8] Yevgeny Seldin, Csaba Szepesv´ari, Peter Auer, Yasin Abbasi-Yadkori. Evaluation and Analysis of the Performance of the EXP3 Algorithm in Stochastic Environments, 2012. [9] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, August 1997. [10] Walter Rudin. Real and complex analysis, 1987. [11] Charu C. Aggarwal, Recommender systems. Springer, 2016. [12] Pier Guisseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, Andreas Krause. Contextual Games: MultiAgent Learning with Side Information, 2020. [13] Larry J. LeBlanc, Edward K. Morlok, William P. Pierskalla. An efficient approach to solving the road network equilibrium traffic assignment problem, 1975. [14] Pier Guissepe Sessa, Ilija Bogunovic, Maryam Kamgarpour, Andreas Krause. No-regret Learning in Unknown Games with Correlated Payoffs, 2019. [15] J. Welles Wilder Jr. New Concepts in Technical Trading Systems, 1978. [16] Raul Canessa C. (https://www.tecnicasdetrading.com/2010/06/macd-moving-averageconvergence-divergence.html), Indicador MACD – Uso e interpretaci´on del MACD. URL:https://www.tecnicasdetrading.com/2010/06/macd-moving-average-convergence-divergence.html (fecha de acceso: 2023-04). [17] MovieLens (https://grouplens.org/datasets/movielens/1m/), Base de datos de pel´ıculas MovieLens 1M. URL:https://grouplens.org/datasets/movielens/1m/ (fecha de acceso: 2023-03) [18] Pier Guissepe Sessa (https://github.com/sessap/contextualgames), Contextual Games: Multi-Agent Learning with Side Information. URL:https://github.com/sessap/contextualgames (fecha de acceso: 2023-02). [19] Yan Qui (https://github.com/yan-qi/k-shortest-paths-cpp-version), K-Shortest Path Algorithm. URL:https://github.com/yan-qi/k-shortest-paths-cpp-version (fecha de acceso: 2023-03). [20] Andrew Ng (https://www.coursera.org/specializations/machine-learning-introduction), Machine Learning program by DeepLearning.AI and Stanford University. URL:https://www.coursera.org/ specializations/machine-learning-introduction. [21] John Bollinger (https://editorial.blob.core.windows.net/miscelaneous-input/ 43nU6TUt1Bpht3fs4zs8DU7xSqDBbdNJ99KrXi1a/John%20Bollinger-637370664925974496.pdf), As´ı uso hoy en d´ıa en el mercado mis herramientas. URL:https://editorial.blob. core.windows.net/miscelaneous-input/43nU6TUt1Bpht3fs4zs8DU7xSqDBbdNJ99KrXi1a/John% 20Bollinger-637370664925974496.pdf (fecha de acceso: 2023-04). [22] Seaborn. (https://seaborn.pydata.org/generated/seaborn.violinplot.html). seaborn.violinplot. URL: https://seaborn.pydata.org/generated/seaborn.violinplot.html (fecha de acceso: 2023-03). 104