**SVRAI** Aprendizaje La capacidad de aprender es una faceta clave del comportamiento inteligente, y no es de extrañar que las distintas disciplinas que estudian la inteligencia y la racionalidad hayan prestado mucha atención al tema. Nos centraremos en las técnicas extraídas principalmente de dos de esas disciplinas -la Inteligencia Artificial y la Teoría de Juegos-, aunque éstas, a su vez, se inspiran en una gran variedad de disciplinas, como la Teoría del Control, la Estadística, la Psicología y la Biología. Comenzaremos con un debate informal sobre diversos aspectos del aprendizaje en los sistemas multiagente y, a continuación, analizaremos algunas de las teorías más representativas en este ámbito. # La complejidad del Aprendizaje El tema del aprendizaje no es sencillo, por lo que es preferible comenzar con una discusión informal que nos permita saber cuáles son las preguntas más importantes y porqué son importantes. Abordaremos principalmente tres cuestiones: la interacción entre el aprendizaje y la enseñanza, los entornos en los que tiene lugar el aprendizaje y lo que constituye el aprendizaje en esos entornos, y los criterios para medir la eficacia del aprendizaje en los sistemas multiagente. ## Aprendizaje y Enseñanza La mayor parte de los trabajos en IA se refieren al aprendizaje realizado por un agente individual: el objetivo es diseñar un agente que aprenda a funcionar en un entorno que es desconocido y que potencialmente también cambia a medida que el agente aprende. En este contexto, se ha desarrollado una amplia gama de técnicas y las reglas de aprendizaje se han vuelto bastante sofisticadas, definiendo toda una área de conocimiento dentro de la IA, el **Machine Learning** (**ML**), que está fagocitando al resto de técnicas de una forma vertiginosa. Sin embargo, en un entorno multiagente surge una complicación adicional, ya que el entorno contiene a otros agentes. El problema no es sólo que el aprendizaje de los otros agentes cambiará el entorno de nuestro agente protagonista (los entornos dinámicos también se dan en el caso de un solo agente), sino que estos cambios dependerán en parte de las acciones del agente protagonista. Es decir, el aprendizaje de los demás agentes se verá afectado por el aprendizaje realizado por nuestro protagonista. En este sentido, el aprendizaje tiene complejidades similares a los del resto de procesos que dependen de las interacciones entre cada agente y el resto de agentes y entorno. !!! El aprendizaje en un entorno multiagente se convierte en una dinámica con retroalimentación. El aprendizaje simultáneo de los agentes significa que cada regla de aprendizaje conduce a un sistema dinámico, y a veces incluso reglas de aprendizaje muy simples pueden conducir a comportamientos globales complejos del sistema, como ocurre en muchos sistemas dinámicos (los más interesantes). Sin embargo, más allá de este hecho matemático hay otro conceptual. En el contexto de los sistemas multiagente no se puede separar el fenómeno del aprendizaje del de la enseñanza: !!! Al elegir una línea de acción, un agente debe tener en cuenta no sólo lo que ha aprendido del comportamiento pasado de otros agentes, sino también cómo desea influir en su comportamiento futuro. El siguiente ejemplo ilustra este punto: !!!Tip Consideremos un juego infinitamente iterado con recompensa media (es decir, en el que la recompensa de un agente es el límite de la media de las recompensas recibidas en cada iteración individual) en el que cada ronda individual es el juego en forma normal siguiente: \begin{array}{|c|c|c|} \hline & L & R \\ \hline T & 1,0 & 3,2\\ \hline B & 2,1 & 4,0\\ \hline \end{array} En primer lugar, hay que tener en cuenta que el jugador $1$ (el jugador de la fila) tiene una estrategia dominante: $B$. También hay que tener en cuenta que $(B, L)$ es el único equilibrio de Nash del juego. De hecho, si el jugador $1$ jugara $B$ repetidamente, es razonable esperar que el jugador $2$ responda siempre con $L$. Por supuesto, si el jugador $1$ eligiera $T$ en su lugar, entonces la mejor respuesta del jugador $2$ sería $R$, lo que daría al jugador $1$ una recompensa de $3$, que es mayor que la recompensa del equilibrio de Nash del jugador $1$. En un juego de una sola iteración sería difícil para el jugador $1$ convencer al jugador $2$ de que él (el jugador $1$) jugará $T$, ya que es una estrategia estrictamente dominada. Sin embargo, en un escenario de juegos iterados, el agente $1$ tiene la oportunidad de adoptar el papel de profesor, es decir que podría jugar repetidamente $T$... presumiblemente, después de un tiempo, el jugador $2$, si tiene algo de sentido común, captaría el mensaje y empezaría a responder con $R$. En este ejemplo está bastante claro quién es el candidato natural para adoptar el papel de profesor. Pero consideremos ahora el juego iterado dado por la siguiente tabla: !!!Tip En este caso, cualquiera de los dos jugadores podría hacer de profesor con igual éxito. Sin embargo, si ambos deciden jugar a ser profesor y resulta que seleccionan acciones no coordinadas $(L,R)$ o $(R,L)$ entonces los jugadores recibirán una recompensa de $0$ siempre. ¿Existe una regla de aprendizaje que les permita coordinarse sin la designación externa de un profesor o coordinador? \begin{array}{|c|c|c|} \hline & L & R \\ \hline L & 1,1 & 0,0\\ \hline R & 0,0 & 1,1\\ \hline \end{array} ## Qué es el aprendizaje En los dos ejemplos anteriores, el escenario ha sido un juego iterado. Consideramos que se trata de un escenario de *aprendizaje* debido a la naturaleza temporal del dominio y a la regularidad a lo largo del tiempo (en cada ocasión participan los mismos jugadores y juegan el mismo juego que antes). Esto nos permite considerar estrategias en las que la acción futura se selecciona en función de la experiencia adquirida hasta el momento. Una definición relativamente general de aprendizaje dentro del contexto humano podría ser la siguiente: !!! *Proceso a través del cual se adquieren o modifican habilidades, destrezas, conocimientos, conductas o valores como resultado del estudio, la experiencia, la instrucción, el razonamiento y la observación*. De esta definición es importante hacer notar que el aprendizaje debe producirse a partir de la experiencia con el entorno, no se considera aprendizaje toda aquella habilidad o conocimiento que sean innatos en el individuo o que se adquieran como resultado del crecimiento natural de éste. Siguiendo un esquema similar, vamos a considerar aprendizaje a aquello que el agente pueda aprender a partir de la experiencia, no a partir del reconocimiento de patrones programados a priori. Cuando vimos los **Juegos Iterados** mencionamos algunas estrategias sencillas. Por ejemplo, en el contexto del dilema del prisionero iterado, mencionamos la estrategia Tit-for-Tat (TfT), que puede considerarse una forma muy rudimentaria de estrategia de aprendizaje. Se pueden imaginar estrategias mucho más complejas, en las que la siguiente elección de un agente depende de la historia del juego de forma más sofisticada, por ejemplo, el agente podría interpretar la frecuencia de las acciones jugadas por su oponente en el pasado como su estrategia mixta actual, y jugar una mejor respuesta a esa estrategia mixta. Como veremos, esta regla básica de aprendizaje se denomina *Juego Ficticio*. Los juegos iterados no son el único contexto en el que tiene lugar el aprendizaje. En la categoría más general de **Juegos Estocásticos** también la regularidad a lo largo del tiempo permite una aproximación al aprendizaje. De hecho, la mayoría de las técnicas analizadas en el contexto de los juegos iterados son aplicables de forma más general a los juegos estocásticos, aunque los resultados específicos obtenidos para unos no siempre se pueden generalizar a los otros. En ambos casos (iterados y estocásticos) hay aspectos adicionales de la configuración que vale la pena discutir, y que tienen que ver con si el juego es conocido por todos los jugadores. Si lo es, cualquier *aprendizaje* que se produzca será sólo sobre las estrategias empleadas por el otro. Sin embargo, si el juego no es conocido, el agente puede además aprender sobre la estructura del propio juego. Por ejemplo, en un juego estocástico, el agente puede empezar a jugar sin conocer las funciones de recompensa en una etapa determinada del juego o las probabilidades de transición, pero las aprende con el tiempo en el transcurso del juego. Es muy interesante considerar el caso en el que el juego que se está jugando es desconocido; en este caso hay un verdadero proceso de descubrimiento. Algunos de los resultados destacables son que, con ciertas estrategias de aprendizaje, los agentes pueden converger a veces a un equilibrio incluso sin conocer el juego que se está jugando. Además, está la cuestión de si el juego es observable: ¿los jugadores ven las acciones de los demás y/o los pagos de los demás? (por supuesto, en el caso de un juego conocido, las acciones también revelan los pagos). Junto a los juegos iterados y estocásticos también existen otros escenarios. El principal es el de los modelos de grandes poblaciones, que se inspiran en gran medida en los modelos evolutivos de la biología, y que son superficialmente muy diferentes del escenario de los juegos iterados o estocásticos. A diferencia de estos últimos, en los que interviene un pequeño número de jugadores, los modelos evolutivos constan de un gran número de jugadores, que juegan repetidamente un determinado juego entre ellos (por ejemplo, por parejas en el caso de los juegos de dos jugadores). Sin embargo, un examen más detallado muestra que estos modelos están, de hecho, estrechamente relacionados con los modelos de juegos iterados. ## Métricas de aprendizaje Es muy importante tener claro por qué estudiamos el aprendizaje en los sistemas multiagente y cómo juzgamos si una determinada teoría de aprendizaje tiene éxito o no. Pueden parecer preguntas triviales, pero en realidad las respuestas no son obvias ni únicas. En primer lugar, hay que tener en cuenta que, en lo sucesivo, cuando hablemos de estrategias de aprendizaje, éstas deben entenderse como estrategias completas, que implican el aprendizaje en el sentido de la elección de la acción, así como la actualización de las creencias acerca de los demás jugadores y el propio juego. Una consecuencia es que el aprendizaje en el sentido de *conocimiento acumulado* no siempre es beneficioso. En abstracto, acumular conocimientos nunca es perjudicial, ya que siempre se puede ignorar lo que se ha aprendido. Pero cuando uno se compromete de antemano con una estrategia concreta para actuar sobre el conocimiento acumulado, a veces menos es más. Este punto está relacionado con la inseparabilidad entre aprendizaje y enseñanza que se ha comentado anteriormente. !!!Tip Por ejemplo, consideremos un agente que planea jugar una partida del juego del gallina infinitamente iterado (una carrera de coches contra una pared en la que pierde el primero que se retire), representado en la tabla siguiente. En presencia de cualquier oponente que intente aprender la estrategia de este agente y jugar una respuesta óptima, una estrategia óptima es jugar la política estacionaria de atreverse siempre (la política de *cuidado: Estoy loco*). El adversario aprenderá a ceder siempre, un resultado peor para él que no aprender nunca nada. \begin{array}{|c|c|c|} \hline & Abandono & Atrevo \\ \hline Abandono & 2,2 & 1,3\\ \hline Atrevo & 3,1 & 0,0\\ \hline \end{array} En términos generales, podemos dividir las teorías del aprendizaje en sistemas multiagente en dos categorías: **Teorías Descriptivas** y **Teorías Prescriptivas**: 1. Las **Teorías Descriptivas** intentan estudiar la forma en que se produce el aprendizaje en la vida real, normalmente por parte de las personas, pero a veces por otras entidades como organizaciones o especies animales. El objetivo es demostrar experimentalmente que un determinado modelo de aprendizaje coincide con el comportamiento real observado (normalmente, en experimentos de laboratorio) y, a continuación, identificar las propiedades interesantes del modelo formal. Muchas veces también estudian la adecuación entre la convergencia del aprendizaje y las estrategias destacadas (equilibrios de algún tipo de los vistos en temas anteriores). 2. Las **Teorías Prescriptivas** se preguntan cómo deben aprender los agentes. Por ello, muchas veces intentan definir conceptos de optimalidad, y no se les exige que muestren una correspondencia con los fenómenos del mundo real ni se centran en las propiedades del comportamiento, aunque también pueden investigar cuestiones de convergencia. El problema es que muchas veces no es posible definir qué se entiende por óptimo. Ningún procedimiento de aprendizaje es óptimo frente a todos los comportamientos posibles del adversario. Esta observación no es más que un ejemplo del movimiento general en la teoría de los juegos que se aleja de la noción de **estrategia óptima** y se acerca a la **mejor respuesta** y al equilibrio. De hecho, en el sentido amplio en que utilizamos el término, una **estrategia de aprendizaje** es simplemente una estrategia en un juego que tiene una estructura particular (a saber, la estructura de un juego iterado o estocástico) que resulta tener un componente que se considera naturalmente adaptativo. !!! Por lo general, nuestra aproximación en este curso es más cercana a la Prescriptiva que a la Descriptiva. Entonces, ¿cómo evaluamos una estrategia de aprendizaje prescriptiva? Hay varias respuestas. La primera es adoptar la postura estándar de la teoría de los juegos: renunciar a juzgar una estrategia de forma aislada y preguntar, en cambio, qué reglas de aprendizaje están en equilibrio entre sí. Un enfoque más modesto, pero mucho más común y quizás más práctico, es preguntar si una estrategia de aprendizaje consigue unos pagos *suficientemente altos*. Este enfoque es a la vez más fuerte y más débil que el requisito de la *mejor respuesta*. La mejor respuesta requiere que la estrategia produzca la mayor retribución posible frente a una estrategia concreta del adversario o adversarios. Un enfoque en los resultados *suficientemente altos* puede considerar una clase más amplia de oponentes, pero establece requisitos más débiles en cuanto a los resultados, que se permiten no llegar a la mejor respuesta. Hay varias versiones diferentes de estos requisitos de pago alto, cada una de las cuales adopta y/o combina diferentes propiedades básicas: - **Seguridad**: Una regla de aprendizaje es **segura** si garantiza al agente al menos su pago máximo, o **valor de seguridad** (el pago que el agente puede garantizarse a sí mismo independientemente de las estrategias adoptadas por los oponentes). - **Racionalidad**: Una regla de aprendizaje es **racional** si siempre que el oponente se asienta en una estrategia estacionaria del juego por rondas (es decir, el oponente adopta la misma estrategia mixta cada vez, independientemente del pasado), el agente se asienta en una mejor respuesta a esa estrategia. - **Sin arrepentimiento**: Una regla de aprendizaje es **universalmente consistente**, o **consistente de Hannan**, o **sin arrepentimiento** (todos estos son términos sinónimos), si, hablando en términos generales, contra cualquier conjunto de oponentes produce una recompensa que no es menor que la recompensa que el agente podría haber obtenido jugando cualquiera de sus estrategias puras durante todo el tiempo. Algunos de estos requisitos básicos son bastante estrictos y pueden debilitarse de varias maneras: - Una forma es permitir ligeras desviaciones, ya sea en términos de la magnitud de la recompensa obtenida, o de la probabilidad de obtenerla, o de ambas. Por ejemplo, en lugar de exigir la optimalidad, se puede exigir la **$(\varepsilon,\delta)$-optimalidad**, es decir, que con probabilidad de, al menos, $1 - \delta$ la ganancia del agente no se distancia más de $\varepsilon$ de la ganancia obtenida por la mejor respuesta. - Otra forma es limitar la clase de oponentes contra los que se cumple el requisito. Por ejemplo, se puede restringir la atención al caso del **juego propio**, en el que el agente juega contra una copia de sí mismo (aunque las estrategias de aprendizaje sean idénticas, el juego que se juega puede no ser simétrico). Por ejemplo, se puede exigir que la regla de aprendizaje garantice la convergencia en el juego propio. En términos más generales, como en el caso de la optimización dirigida, que tratamos más adelante, se podría exigir una respuesta óptima sólo contra una clase particular de oponentes. En las próximas secciones, a medida que analicemos varias reglas de aprendizaje, nos encontraremos con varias versiones de estos requisitos y sus combinaciones. Aunque nos concentraremos principalmente en juegos iterados de dos jugadores, en algunos casos hablaremos de juegos estocásticos y de juegos con más de dos jugadores. # Juego ficticio El **Juego Ficticio** es una de las primeras reglas de aprendizaje. En realidad, no se propuso inicialmente como un modelo de aprendizaje, sino como un método iterativo para calcular los equilibrios de Nash en juegos de suma cero. Resulta que no es una forma especialmente eficaz de realizar este cálculo, pero como emplea una regla de actualización intuitiva, se suele considerar un modelo de aprendizaje, aunque sea simplista. El juego ficticio es un caso de aprendizaje basado en un modelo, en el que el aprendiz mantiene explícitamente creencias sobre la estrategia del adversario. Su estructura es sencilla: ~~~~none Inicializar las creencias sobre la estrategia del oponente Repetir: Jugar una respuesta óptima a la estrategia evaluada del adversario Observar el juego real del adversario y actualizar las creencias en consecuencia ~~~~ Obsérvese que en este esquema el agente es ajeno a los pagos obtenidos u obtenibles por otros agentes. Sin embargo, suponemos que el agente conoce su propia matriz de retribución en el juego (es decir, la retribución que obtendría en cada perfil de acción, haya sido o no encontrada en el pasado). En el juego ficticio, un agente cree que su oponente está jugando la estrategia mixta dada por la distribución empírica de las acciones anteriores del oponente. Es decir: !!!Def Si $A$ es el conjunto de acciones del adversario, y para cada $a\in A$, $w(a)$ es el número de veces que el adversario ha jugado la acción $a$, entonces el agente evalúa la probabilidad de $a$ en la estrategia mixta del adversario como: $$P(a) = \frac{w(a)}{\sum_{a'\in A} w(a')}$$ Nótese que podemos representar las creencias de un jugador con una medida de probabilidad: $\{w(a)\}_{a\in A}$, o, si hay un orden en $A=\{a_1,\dots,a_n\}$, entonces el vector $(w(a_1),\dots,w(a_n))$. !!!Tip Por ejemplo, en un juego de Dilema del Prisionero iterado, si el adversario ha jugado $\{C, C, D, C, D\}$ en las cinco primeras partidas, antes de la sexta partida se supone que está jugando la estrategia mixta $(0.6, 0.4)$. Existen diferentes versiones del juego ficticio que difieren en el método de desempate utilizado para seleccionar una acción cuando hay más de una respuesta mejor a la estrategia mixta particular inducida por las creencias de un agente. Aunque, en general, la regla de desempate elegida tiene poco efecto en los resultados del juego ficticio. En cambio, el juego ficticio es muy sensible a las creencias iniciales de los jugadores. Esta elección, que puede interpretarse como los recuentos de acciones que se observaron antes del inicio del juego, puede tener un impacto radical en el proceso de aprendizaje. Obsérvese que hay que elegir alguna creencia previa no vacía para cada agente, y no pueden ser $(0, \dots , 0)$ ya que esto no define una estrategia mixta significativa. El juego ficticio es algo paradójico, ya que cada agente asume una política estacionaria del adversario, pero ningún agente juega una política estacionaria excepto cuando el proceso converge a una. El siguiente ejemplo ilustra el funcionamiento de un juego ficticio: !!!Tip Recordemos el juego de emparejamiento de monedas: \begin{array}{|c|c|c|} \hline & C & X \\ \hline C & 1,-1 & -1,1\\ \hline X & -1,1 & 1,-1\\ \hline \end{array} Cada jugador utiliza la regla de aprendizaje del juego ficticio para actualizar sus creencias y seleccionar acciones. El jugador $1$ comienza el juego con la creencia previa de que el jugador $2$ ha jugado cara $1.5$ veces y cruz $2$ veces. El jugador $2$ comienza con la creencia previa de que el jugador $1$ ha jugado cara $2$ veces y cruz $1.5$ veces. ¿Cómo jugarán los jugadores? La siguiente tabla muestra las siete primeras rondas del juego: \begin{array}{|c|c|c|} \hline Ronda & Acción_1 & Acción_2 & Creencias_1 & Creencias_2 \\ \hline 0 & & & (1.5,2) & (2,1.5)\\ \hline 1 & X & X &(1.5,3) &(2,2.5)\\ \hline 2 & X & C &(2.5,3) &(2,3.5) \\ \hline 3 & X & C &(3.5,3) &(2,4.5) \\ \hline 4 & C & C &(4.5,3) &(3,4.5) \\ \hline 5 & C & C &(5.5,3) &(4,4.5) \\ \hline 6 & C & C &(6.5,3) &(5,4.5) \\ \hline 7 & C & X &(6.5,4) &(6,4.5) \\ \hline \vdots & \vdots & \vdots & \vdots &\vdots \\ \hline \end{array} Como se puede ver, cada jugador acaba alternando entre jugar cara y cruz. De hecho, a medida que el número de rondas tiende a infinito, la distribución empírica del juego de cada jugador convergerá a $(0.5, 0.5)$. Si tomamos esta distribución como la estrategia mixta de cada jugador, el juego converge al único equilibrio de Nash del juego iterado en forma normal, aquel en el que cada jugador juega la estrategia mixta $(0.5, 0.5)$. El juego ficticio tiene varias propiedades interesantes. En primer lugar, se puede demostrar la conexión con los equilibrios de Nash de estrategia pura (cuando éstos existen): !!!Def: Definición (Estado estacionario) Un perfil de acción $a$ es un **estado estacionario** (o **estado absorbente**) del juego ficticio si siempre que se juegue $a$ en la ronda $t$ también se juega en la ronda $t + 1$ (y, por tanto, también en todas las rondas futuras). Los dos teoremas siguientes establecen una estrecha relación entre los estados estables y los equilibrios de Nash de estrategia pura: !!!Def: Teorema Si un perfil de estrategia pura es un equilibrio de Nash estricto de un juego simple, entonces es un estado estacionario del juego ficticio en el juego iterado. Obsérvese que el perfil de estrategia pura debe ser un equilibrio de Nash estricto, lo que significa que ningún agente puede desviarse a otra acción sin disminuir estrictamente su recompensa. También tenemos un resultado inverso: !!!Def: Teorema Si un perfil de estrategia pura es un estado estacionario del juego ficticio en el juego iterado, entonces es un equilibrio de Nash (posiblemente débil) en el juego simple. Por supuesto, no se puede garantizar que el juego ficticio converja siempre a un equilibrio de Nash, aunque sólo sea porque los agentes sólo pueden jugar con estrategias puras y puede que el juego no tenga equilibrios de Nash de estrategia pura. Sin embargo, aunque las estrategias del juego por rondas pueden no converger, la distribución empírica de las estrategias del juego por rondas a lo largo de múltiples iteraciones sí puede hacerlo. Y, de hecho, este es el caso en el ejemplo del emparejamiento de monedas anterior, donde la distribución empírica de la estrategia de cada jugador convergió a su estrategia mixta en el (único) equilibrio de Nash del juego. El siguiente teorema muestra que esto no es casual: !!!Def: Teorema Si la distribución empírica de las estrategias de cada jugador converge en el juego ficticio, entonces converge a un equilibrio de Nash. Este parece un resultado muy potente, pero aunque el teorema da condiciones suficientes para que la distribución empírica de las acciones de los jugadores converja a un equilibrio de estrategia mixta, no hemos hecho ninguna afirmación sobre la distribución de los resultados particulares jugados. Para entender mejor este punto, vamos a dar un ejemplo: !!!Tip Consideremos el llamado **juego de Anti-Coordinación** que se muestra en la tabla siguiente: \begin{array}{|c|c|c|} \hline & A & B \\ \hline A & 0,0 & 1,1\\ \hline B & 1,1 & 0,0\\ \hline \end{array} Está claro que hay dos equilibrios de Nash puros en este juego, $(A, B)$ y $(B, A)$, y un equilibrio de Nash mixto, en el que cada agente mezcla $A$ y $B$ con una probabilidad de $0.5$. Cualquiera de los dos equilibrios de estrategia pura da a cada jugador una recompensa de $1$, y el equilibrio de estrategia mixta da a cada jugador una recompensa de $0.5$. Ahora veamos qué ocurre cuando hacemos que los agentes jueguen el juego iterado de Anti-coordinación utilizando un juego ficticio. Supongamos que las creencias de cada jugador se inicializan en $(1, 0.5)$. La siguiente tabla muestra las primeras rondas del juego: \begin{array}{|c|c|c|} \hline Ronda & Acción_1 & Acción_2 & Creencias_1 & Creencias_2 \\ \hline 0 & & & (1,0.5) & (1,0.5)\\ \hline 1 & B & B &(1,1.5) &(1,1.5)\\ \hline 2 & A & A &(2,1.5) &(2,1.5)\\ \hline 3 & B & B &(2,2.5) &(2,2.5)\\ \hline 4 & A & A &(3,2.5) &(3,2.5)\\ \hline \vdots & \vdots & \vdots & \vdots &\vdots \\ \hline \end{array} Como se puede ver, el juego de cada jugador converge a la estrategia mixta $(0.5, 0.5)$, que es el equilibrio de Nash de estrategia mixta. Sin embargo, la retribución recibida por cada jugador es $0$, ya que los jugadores nunca llegan a los resultados con retribución positiva. Por lo tanto, aunque la distribución empírica de las estrategias converge al equilibrio de Nash de estrategia mixta, los jugadores pueden no recibir la recompensa esperada del equilibrio de Nash, porque sus acciones están mal coordinadas. Por último, veamos un ejemplo en el que se muestre que las distribuciones empíricas de las acciones de los jugadores no tienen por qué converger en absoluto: !!!Tip Consideremos el juego siguiente: \begin{array}{|c|c|c|c|} \hline & Piedra & Papel & Tijeras \\ \hline Piedra & 0,0 & 0,1 & 1,0\\ \hline Papel & 1,0 & 0,0 & 0,1\\ \hline Tijeras & 0,1 & 1,0 & 0,0\\ \hline \end{array} Este ejemplo, dado por Shapley, es una modificación del **juego piedra-papel-tijeras** y no es de suma constante. El único equilibrio de Nash de este juego es que cada jugador juegue la estrategia mixta $(1/3, 1/3, 1/3)$. Sin embargo, consideremos el juego ficticio cuando las creencias del jugador $1$ se han inicializado a $(0, 0, 0.5)$ y las del jugador $2$ se han inicializado a $(0, 0.5, 0)$. La siguiente tabla muestra las primeras rondas de este juego. Aunque no es obvio a partir de estas primeras rondas, se puede demostrar que el juego empírico de este juego nunca converge a ninguna distribución fija. \begin{array}{|c|c|c|} \hline Ronda & Acción_1 & Acción_2 & Creencias_1 & Creencias_2 \\ \hline 0 & & & (0,0,0.5) & (0,0.5,0)\\ \hline 1 & Piedra & Tijeras &(0,0,1.5) &(1,0.5,0)\\ \hline 2 & Piedra & Papel &(0,1,1.5) &(2,0.5,0)\\ \hline 3 & Piedra & Papel &(0,2,1.5) &(3,0.5,0)\\ \hline 4 & Tijeras & Papel &(0,3,1.5) &(3,0.5,1)\\ \hline 5 & Tijeras & Papel &(0,1.5,0) &(1,0,0.5)\\ \hline \vdots & \vdots & \vdots & \vdots &\vdots \\ \hline \end{array} Para ciertas clases restringidas de juegos sí se garantiza que se alcanza la convergencia: !!!Def: Teorema Cada una de las siguientes es una condición suficiente para que las frecuencias empíricas del juego converjan en el juego ficticio (no son las únicas, pero otras condiciones del teorema nos obligarían a introducir otros tipos de juegos): - El juego es de suma cero. - El juego es resoluble por eliminación iterada de estrategias estrictamente dominadas. - ... algunas otras. En general, el juego ficticio es un modelo interesante de aprendizaje en los sistemas multiagente, no porque sea realista o porque ofrezca fuertes garantías, sino porque es muy sencillo de enunciar y da lugar a propiedades no triviales. Pero es muy limitado: Su modelo de creencias y actualización de creencias es matemáticamente restrictivo, y es claramente inverosímil como modelo de aprendizaje humano. Existen diversas variantes del juego ficticio que obtienen resultados algo mejores en ambos frentes. Mencionaremos una de ellas (llamada **juego ficticio suave**) cuando hablemos de los métodos de aprendizaje sin arrepentimiento. # Aprendizaje Racional El **aprendizaje racional** (también llamado a veces **aprendizaje bayesiano**) adopta el mismo esquema general basado en modelos que el juego ficticio. Sin embargo, a diferencia del juego ficticio, permite a los jugadores tener un conjunto mucho más rico de creencias sobre las estrategias de los oponentes. En primer lugar, el conjunto de estrategias del adversario puede incluir estrategias de juegos iterados, como el TfT en el juego del Dilema del Prisionero, y no sólo estrategias de juegos simples. En segundo lugar, las creencias de cada jugador sobre las estrategias de su oponente pueden expresarse mediante cualquier distribución de probabilidad sobre el conjunto de todas las estrategias posibles. Al igual que en el juego ficticio, cada jugador comienza la partida con algunas creencias previas. Después de cada ronda, el jugador utiliza la actualización bayesiana para actualizar estas creencias. Si denotamos por $S^i_{-i}$ el conjunto de estrategias del adversario consideradas posibles por el jugador $i$, y $H$ el conjunto de historias posibles del juego, entonces podemos utilizar la regla de Bayes para expresar la probabilidad asignada por el jugador $i$ al evento en el que el oponente está jugando una estrategia particular $s\in S^i_{-i}$ dada la observación de la historia $h \in H$, como $$P_i(s|h) = \frac{P_i(h|s)P_i(s)}{ \sum_{s' \in S^i_{-i}} P_i(h|s')P_i(s')}$$ !!!Tip Por ejemplo, consideremos a dos jugadores que juegan el juego del Dilema del Prisionero iterado siguiente: \begin{array}{|c|c|c|} \hline & C & D \\ \hline C & 3,3 & 0,4\\ \hline D & 4,0 & 1,1\\ \hline \end{array} Supongamos que el soporte de la creencia previa de cada jugador (es decir, las estrategias del adversario a las que el jugador atribuye una probabilidad distinta de $0$) consiste en las estrategias $g_1, g_2, \dots,g_{\infty}$, definidas como sigue: - $g_\infty$ es la estrategia en la que el jugador comienza el juego iterado cooperando, y si su oponente lo delata en cualquier ronda, él delatará en todas las rondas siguientes. - Para $T \le \infty$, $g_T$ coincide con $g_\infty$ en todas las historias más cortas que $T$, pero a partir del tiempo $T$ siempre delatará. Siguiendo esta convención, la estrategia $g_0$ es la estrategia en que delata siempre. Supongamos, además, que cada jugador selecciona efectivamente una respuesta óptima de entre $g_0, g_1, \dots, g_\infty$ (por supuesto, hay infinitas respuestas mejores adicionales fuera de este conjunto). Así, cada ronda del juego se jugará según algún perfil de estrategia $(g_{T_1}, g_{T_2})$. Después de jugar cada ronda del juego iterado, cada jugador realiza una actualización bayesiana. Por ejemplo, si el jugador $i$ ha observado que el jugador $j$ siempre ha cooperado, la actualización bayesiana tras la historia $h_t \in H$ de longitud $t$ se reduce a: $$P_i(g_T |h_t) = \begin{cases} 0 & \text{ si } T \leq t\\ \frac{Pi(g_T)}{\sum_{k=t+1}^\infty P_i(g_k)} & \text{ si } T \ge t\\ \end{cases} $$ El aprendizaje racional es un modelo de aprendizaje muy intuitivo, pero su análisis es bastante complicado. El análisis formal se centra en el juego propio, es decir, en las propiedades del juego iterado en el que todos los agentes emplean el aprendizaje racional (aunque pueden empezar con diferentes creencias). !!! A grandes rasgos, los aspectos más destacados de este modelo son los siguientes: - En algunas condiciones, el aprendizaje racional en el juego propio hace que los agentes tengan creencias casi correctas sobre la parte observable de la estrategia de su oponente. - Bajo algunas condiciones, el aprendizaje racional en el juego propio hace que los agentes se acerquen a un equilibrio de Nash con alta probabilidad. - La principal de estas *condiciones* es la **continuidad absoluta**, un supuesto fuerte. En el resto de esta sección discutiremos estos puntos con más detalle, empezando por la noción de **continuidad absoluta**: !!!Def: Definición (Continuidad absoluta) Sea $X$ un conjunto y sean $\mu, \mu'\in \Pi(X)$ distribuciones de probabilidad sobre $X$. Entonces se dice que $\mu$ es **absolutamente continua** con respecto a $\mu'$ si: $\forall\ C \subseteq X \text{ medible } (\mu(C) > 0 \Rightarrow \mu'(C) > 0)$. Nótese que las creencias de los jugadores y las estrategias reales inducen cada una de ellas distribuciones de probabilidad sobre el conjunto de historias $H$: - Si $s = (s_1, \dots , s_n)$ es un perfil de estrategia, y suponemos que estas estrategias son utilizadas por los jugadores, podemos calcular la probabilidad de que ocurra cada historia del juego, induciendo así una distribución sobre $H$. - Si denotamos por $S^i_j$ un conjunto de estrategias que $i$ cree posibles para $j$, y $P^i_j \in \Pi(S^i_j)$ la distribución sobre $S^i_j$ que cree el jugador $i$. Entonces, si el jugador $i$ asume que todos los jugadores (incluido él mismo) jugarán de acuerdo con sus creencias, también puede calcular la probabilidad de que se produzca cada historia del juego, induciendo así una distribución sobre $H$. Todos los resultados que siguen requieren que la distribución sobre las historias inducida por las estrategias reales sea absolutamente continua con respecto a la distribución inducida por las creencias de un jugador; en otras palabras, si hay una probabilidad positiva de alguna historia dadas las estrategias reales, entonces las creencias del jugador también deberían asignar a la historia una probabilidad positiva (coloquialmente, a veces se dice que *las creencias de los jugadores deben contener un grano de verdad*). Aunque los resultados que siguen son muy elegantes, hay que decir que el supuesto de continuidad absoluta es una limitación importante de los resultados teóricos asociados al aprendizaje racional. !!!Tip En el ejemplo del Dilema del Prisionero comentado anteriormente, es fácil ver que la distribución de las historias inducida por las estrategias reales es absolutamente continua con respecto a la distribución predicha por las creencias previas de los jugadores. A todas las historias con probabilidad positiva en el juego se les asigna probabilidad positiva por las creencias originales de ambos jugadores: si las estrategias verdaderas son $g_{T_1}, g_{T_2}$, los jugadores asignan probabilidad positiva a la historia con cooperación hasta el tiempo $t \le \min(T_1, T_2)$ y delatan en todos los tiempos que superen el $\min(T_1, T_2)$. El modelo de aprendizaje racional es interesante porque tiene algunas propiedades muy deseables. A grandes rasgos, los jugadores que satisfacen los supuestos del modelo de aprendizaje racional tendrán creencias sobre el juego de los demás jugadores que convergen a la verdad y, además, los jugadores convergerán en un tiempo finito a un juego que se acerca arbitrariamente al equilibrio de Nash. Antes de poder exponer estos resultados, necesitamos definir una medida de la similitud de dos medidas de probabilidad: !!!Def: Definición ($\varepsilon$-cercanía) Dado $\varepsilon > 0$ y dos medidas de probabilidad $\mu$ y $\mu'$ en el mismo espacio, decimos que $\mu$ es **$\varepsilon$-cercano** a $\mu'$ si existe un conjunto medible $Q$ que satisface: - $\mu(Q),\ \mu'(Q)> 1 - \varepsilon$, - Para todo conjunto medible $A \subseteq Q$, tenemos que $(1 + \varepsilon)\mu'(A) \geq \mu(A) \geq (1 - \varepsilon)\mu'(A)$. Ahora podemos enunciar un resultado sobre la exactitud de las creencias de un jugador que utiliza el aprendizaje racional: !!!Def: Teorema (Aprendizaje racional y precisión de las creencias) Sea $s$ un perfil de estrategia de juego iterado para un juego dado de $n$ jugadores, y sea $P = (P_1, \dots,P_n)$ una tupla de distribuciones de probabilidad sobre dichos perfiles de estrategia ($P_i$ se interpreta como las creencias del jugador $i$). Sean $\mu_s$ y $\mu_P$ las distribuciones sobre historias del juego infinito inducidas por el perfil de estrategia $s$ y la tupla de creencias $P$, respectivamente. Si tenemos que: - en cada ronda, cada jugador $i$ juega una estrategia de mejor respuesta dadas sus creencias $P_i$, - después de cada ronda, cada jugador $i$ actualiza $P_i$ utilizando la actualización bayesiana, y - $\mu_s$ es absolutamente continua con respecto a $\mu_{P_i}$, entonces para cada $\varepsilon > 0$ y para casi toda historia en el soporte de $\mu_s$ (es decir, toda historia posible dado el perfil de estrategia real $s$), hay un tiempo $T$ tal que para todo $t\geq T$, la jugada $\mu_{P_i}$ predicha por las creencias del jugador $i$ es $\varepsilon$-cercana a la distribución de la jugada $\mu_s$ predicha por las estrategias reales. Nótese que este resultado no afirma que los jugadores aprenderán la verdadera estrategia que están jugando sus oponentes. Como se ha dicho antes, hay un número infinito de estrategias posibles que su oponente podría estar jugando, y cada jugador comienza con una distribución a priori que asigna una probabilidad positiva sólo a un subconjunto de las estrategias posibles. !!!Tip Consideremos de nuevo a los dos jugadores que juegan el juego del Dilema del Prisionero infinitamente iterado que describimos anteriormente. Verifiquemos que, como dice el teorema anterior, el juego futuro de este juego será predicho correctamente por los jugadores: Si $T_1 \le T_2$, a partir del tiempo $T_1 + 1$, las creencias posteriores del jugador $2$ asignarán la probabilidad $1$ a la estrategia del jugador $1$, $g_{T_1}$. Por otro lado, el jugador $1$ nunca conocerá completamente la estrategia del jugador $2$, pero sabrá que $T_2 \ge T_1$. Sin embargo, esta información es suficiente para predecir que el jugador $2$ siempre elegirá desertar en el futuro. Las creencias de un jugador deben converger a la verdad incluso cuando su espacio estratégico es incorrecto (no incluye la estrategia real del adversario), siempre que satisfagan el supuesto de continuidad absoluta. !!!Tip Supongamos, por ejemplo, que el jugador $1$ está jugando la estrategia $g_\infty$, y el jugador $2$ está jugando al TfT, pero que el jugador $1$ cree que el jugador $2$ también está jugando $g_\infty$. Por tanto, las creencias del jugador $1$ sobre la estrategia del jugador $2$ son incorrectas. Sin embargo, sus creencias predecirán correctamente la futura partida del juego. Hasta ahora hemos hablado de la precisión de las creencias en el aprendizaje racional. El siguiente teorema aborda la convergencia al equilibrio. Obsérvese que las condiciones de este teorema son idénticas a las del teorema anterior, y que la definición se refiere al concepto de equilibrio $\varepsilon$-Nash que vimos en su momento, así como a la $\varepsilon$-cercanía definida anteriormente: !!!Def: Teorema (Aprendizaje racional y Nash) Sea $s$ un perfil de estrategia de juego iterado para un juego dado de $n$ jugadores, y sea $P = (P_1, \dots, P_n)$ una tupla de distribuciones de probabilidad sobre dichos perfiles estratégicos. Sean $\mu_s$ y $\mu_P$ las distribuciones sobre historias del juego infinito inducidas por el perfil de estrategia $s$ y la tupla de creencias $P$, respectivamente. Si tenemos que: - en cada ronda, cada jugador $i$ juega una estrategia de mejor respuesta dadas sus creencias $P_i, - después de cada ronda, cada jugador $i$ actualiza $P_i$ utilizando la actualización bayesiana, y - $\mu_s$ es absolutamente continua con respecto a $\mu_{P_i}$, entonces para cada $\varepsilon > 0$ y para casi toda historia en el soporte de $\mu_s$ hay un tiempo $T$ tal que para cada $t \geq T$ existe un $\varepsilon$-equilibrio $s^*$ del juego repetido en el que la jugada $\mu_{P_i}$ predicha por las creencias del jugador $i$ es $\varepsilon$-cercana a la jugada $\mu_{s^*}$ del equilibrio. En otras palabras, si los jugadores que maximizan la utilidad comienzan con creencias subjetivas individuales con respecto a las cuales las estrategias verdaderas son absolutamente continuas, entonces a largo plazo, su comportamiento debe ser esencialmente el mismo que un comportamiento descrito por un equilibrio $\varepsilon$-Nash. Por supuesto, el espacio de equilibrios de juegos repetidos es enorme, lo que deja abierta la cuestión de qué equilibrio se alcanzará. En este caso, hay que tener en cuenta una propiedad que se autocumple: el optimismo de los jugadores puede llevar a recompensas altas, y del mismo modo, el pesimismo puede llevar a recompensas bajas. Por ejemplo, en un juego de dilema del prisionero iterado, si ambos jugadores empiezan a creer que su oponente probablemente jugará la estrategia TfT, cada uno tenderá a cooperar, lo que llevará a una cooperación mutua. Si, por el contrario, cada uno de ellos asigna una alta probabilidad previa a la deserción constante, o a otra estrategia que conlleve la deserción, cada uno de ellos tenderá a desertar. # Aprendizaje por Refuerzo Ahora vamos a estudiar las extensiones multiagente del aprendizaje en MDP, es decir, en juegos estocásticos de un solo agente. A diferencia de las dos primeras técnicas de aprendizaje analizadas, y con una excepción que comentaremos posteriormente, el aprendizaje por refuerzo no modela explícitamente la estrategia del adversario. La familia específica de técnicas que examinamos se deriva del algoritmo de $Q$-Learning para MDP desconocidos (de un solo agente). El $Q$-Learning se describe en la siguiente sección, tras lo cual presentamos su extensión a los juegos estocásticos de suma cero. A continuación, discutimos brevemente la dificultad de extender los métodos a los juegos estocásticos de suma general. ## ... en MDP desconocidos En primer lugar, consideremos los MDP (de un solo agente). El método de iteración del valor (**value-iteration**), que vimos en su momento, supone que el MDP es conocido. ¿Qué ocurre si no conocemos las recompensas o las probabilidades de transición del MDP? Resulta que, si siempre sabemos en qué estado estamos y la recompensa recibida en cada iteración, aún podemos converger a los valores $Q$ correctos. !!! Para ser coherentes con la notación habitual en aprendizaje por refuerzo, usaremos la notación $s$ para estados y $S$ para conjuntos de estados, en vez de estrategias, como hemos hecho hasta ahora. !!!Def: Definición ($Q$-Learning) El $Q$-Learning es el siguiente procedimiento: ~~~~none Inicializar la función Q y los valores V (arbitrariamente, por ejemplo) Repetir hasta la convergencia: Observar el estado actual: s_t Seleccionar la acción a_t y realizarla Observar la recompensa r(s_t, a_t) Realizar las siguientes actualizaciones (y no actualizar ningún otro Q-valor): Q_{t+1}(s_t, a_t) ← (1 - α)Q_t(s_t, a_t) + α_t(r(s_t, a_t) + β V_t(s_{t+1})) V_{t+1}(s) ← max_a Q_t(s, a) ~~~~ !!!Def: Teorema El $Q$-Learning garantiza que los valores de $Q$ y $V$ convergen a los de la política óptima, siempre que cada par $(s,a)$ se muestree un número infinito de veces, y que la tasa de aprendizaje dependiente del tiempo $\alpha_t$ verifique: $0 \leq \alpha_t \le 1$, $\sum_{t=0}^\infty \alpha_t = \infty$ y $\sum_{t=0}^\infty \alpha^2_t\leq \infty$. La intuición detrás de este enfoque es que aproximamos la probabilidad de transición desconocida utilizando la distribución real de los estados alcanzados en el propio juego. Obsérvese que esto todavía nos deja mucho margen a la hora de diseñar el orden en el que el algoritmo selecciona las acciones. !!! Este teorema no dice nada sobre la tasa de convergencia. Además, no da ninguna garantía sobre la acumulación de recompensas futuras óptimas descontadas por el agente; por lo que podría ocurrir, dependiendo del factor de descuento, que cuando el agente converja a la política óptima haya pagado un coste demasiado alto, que no pueda recuperar explotando la política en el futuro. Esto no es un problema si el aprendizaje tiene lugar durante las sesiones de entrenamiento, y sólo cuando el aprendizaje ha convergido lo suficiente se libera el agente en el mundo (por ejemplo, un piloto de caza que se entrena en un simulador antes de entrar en combate). Pero, en general, debe considerarse que el $Q$-Learning garantiza un buen aprendizaje, pero no un aprendizaje rápido ni unas recompensas futuras elevadas. ## ... en Juegos Estocásticos de Suma Cero Para adaptar el método presentado del entorno de los MDP a los juegos estocásticos, debemos hacer algunas modificaciones. La modificación más sencilla consiste en que cada agente ignore la existencia del otro (recordemos que en los juegos de suma cero sólo participan dos agentes). En este caso, podemos definir $Q^\pi_i: S \times A_i\mapsto \mathbb{R}$ como el valor para el jugador $i$ si los dos jugadores siguen el perfil de estrategia $\pi$ después de empezar en el estado $s$ y el jugador $i$ elige la acción $a$, tras lo que podemos aplicar el algoritmo de $Q$-Learning. Como ya hemos dicho, el entorno multiagente nos obliga a renunciar a la búsqueda de una política *óptima* y a centrarnos en una que funcione bien contra su oponente. Por ejemplo, podemos exigir que satisfaga la **consistencia de Hannan**. De hecho, se puede demostrar que el procedimiento de $Q$-Learning es consistente de Hannan para un agente en un juego estocástico contra oponentes que juegan con políticas estacionarias. Sin embargo, contra oponentes que utilizan estrategias más complejas, como el propio $Q$-Learning, no obtenemos tal garantía. Con este enfoque, si el agente es consciente de qué acciones seleccionó su oponente en cada punto de su historia, podemos utilizar una función $Q$ modificada, $Q^\pi_i: S\times A \mapsto \mathbb{R}$, definida sobre estados y perfiles de acción, donde $A = A_1\times A_2$. La fórmula para actualizar $Q$ es sencilla de adaptar para un juego de dos jugadores: $$Q_{i,t+1}(s_t, a_t, o_t) = (1 − \alpha_t)Q_{i,t}(s_t, a_t, o_t) + \alpha_t(r_i(s_t, a_t, o_t) + β\ V_t(s_{t+1}))$$ Ahora que las acciones abarcan tanto las de nuestro agente como las de su competidor, ¿cómo podemos calcular el valor de un estado? Recordemos que, en los juegos de suma cero (de dos jugadores), el perfil de política en el que cada agente juega su estrategia máxima forma un equilibrio de Nash. El resultado del primer agente (y, por tanto, el negativo del resultado del segundo agente) se denomina **valor del juego** y constituye la base de nuestra función de valor adaptada para $Q$-Learning: $$V_t(s) = \max_{\Pi_i}\min_o Q_{i,t}(s, \Pi_i(s), o)$$ Siguiendo estas ideas podemos dar el algoritmo minimax-$Q$-Learning: ~~~~ none // Inicializar: Para cada s ∈ S, a ∈ A, y o ∈ O hacer: Q(s, a, o) ← 1 Para cada s en S hacer: V (s) ← 1 Para cada s ∈ S y a ∈ A hacer: Π(s, a) ← 1/|A| α ← 1.0 // Realizar una acción: Cuando se está en el estado s, con probabilidad ex elige una acción uniformemente al azar, y con probabilidad (1 - ex) elegir la acción a con probabilidad Π(s, a) // Aprender: Después de recibir la recompensa r por pasar del estado s al s' mediante la acción a y la acción del adversario o hacer: Q(s, a, o) ← (1 - α) ∗ Q(s, a, o) + α ∗ (r + γ ∗ V (s')) Π(s, .) ← arg max_{Π'(s,.)}(min_{o'} ∑_{a'}(Π(s, a') ∗ Q(s, a', o')) // Lo anterior puede hacerse, por ejemplo, mediante programación lineal: V (s) ← min_{o'}(∑_{a'}(Π(s, a') ∗ Q(s, a', o')) Actualizar α ~~~~ [Código [minimax-Q-learning]: minimax-$Q$-Learning] Al igual que con el algoritmo básico de $Q$-Learning, se garantiza que el algoritmo minimax-$Q$-Learning anterior converge en el límite cuando obtenemos infinitas muestras de cada par de perfiles de estado y acción. Aunque esto garantizará al agente una recompensa al menos igual a la de su estrategia máxima, ya no satisface la consistencia de Hannan. Si el oponente está jugando una estrategia subóptima, minimax-$Q$-Learning no podrá explotarla en la mayoría de los juegos. Este algoritmo especifica no sólo cómo actualizar los valores de $Q$ y $V$, sino también cómo actualizar la estrategia $\Pi$. Todavía hay algunos parámetros libres, como la forma de actualizar el parámetro de aprendizaje, $\alpha$. Una forma de hacerlo es simplemente utilizar una tasa de decaimiento, $d$, de modo que $\alpha$ se establece en $\alpha\cdot d$ después de cada actualización del valor $Q$, para algún valor de $d\le 1$. Otra posibilidad que se puede encontrar en la literatura de $Q$-Learning es mantener valores de $\alpha$ separados para cada par $(s,a)$. En este caso, un método común es usar $\alpha = 1/k$, donde $k$ es igual al número de veces que ese $Q$-valor particular ha sido actualizado incluyendo el actual. Así, cuando se encuentra por primera vez una recompensa para un estado $s$ en el que se ha jugado un perfil de acción $a$, el $Q$-valor se establece por completo en la recompensa observada más el valor descontado del estado sucesor ($\alpha = 1$). La próxima vez que se encuentre ese par de estado-perfil de acción, se establecerá la mitad del $Q$-valor antiguo más la mitad de la nueva recompensa y el valor descontado del estado sucesor. !!!Tip Veamos un ejemplo que demuestra el funcionamiento del minimax-$Q$-Learning en un juego iterado sencillo: el juego iterado de emparejamiento de monedas contra un oponente desconocido. Obsérvese que los resultados de convergencia para el $Q$-Learning imponen sólo restricciones débiles sobre cómo seleccionar las acciones y visitar los estados. En este ejemplo, seguiremos el algoritmo dado y asumiremos que el agente elige una acción al azar una fracción del tiempo (denotado $ex$), y juega según su mejor estrategia actual en caso contrario. Para actualizar la tasa de aprendizaje, hemos elegido el segundo método comentado anteriormente, con $\alpha = 1/k$, donde $k$ es el número de veces que se ha observado el par de perfiles de estado y acción. Supongamos que los $Q$-valores se inicializan a $1$ y que el factor de descuento del juego es $0.9$. La siguiente tabla muestra los valores de la función $Q$ del jugador $1$ en las primeras iteraciones del juego, así como su mejor estrategia en cada paso. Vemos que el valor del juego, $0$, se aproxima, aunque lentamente. Esto no es casual. \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline t & Actions & Reward_1 & Q_t(H, H) & Q_t(H, T) & Q_t(T, H) & Q_t(T, T) & V(s) & \pi_1(H)\\ \hline 0 & & & 1 & 1 & 1 & 1 & 1 & 0.5\\ \hline 1 & (H*,H) & 1 & 1.9 & 1 & 1 & 1 & 1 & 0.5\\ \hline 2 & (T,H) & -1 & 1.9 & 1 & -0.1 & 1 & 1 & 0.55\\ \hline 3 & (T,T) & 1 & 1.9 & 1 & -0.1 & 1.9 & 1.279 & 0.690\\ \hline 4 & (H*,T) & -1 & 1.9 & 0.151 & -0.1 & 1.9 & 0.967 & 0.534\\ \hline 5 & (T,H) & -1 & 1.9 & 0.151 & -0.115 & 1.9 & 0.964 & 0.535\\ \hline 6 & (T,T) & 1 & 1.9 & 0.151 & -0.115 & 1.884 & 0.960 & 0.533\\ \hline 7 & (T,H) & -1 & 1.9 & 0.151 & -0.122 & 1.884 & 0.958 & 0.534\\ \hline 8 & (H,T) & -1 & 1.9 & 0.007 & -0.122 & 1.884 & 0.918 & 0.514\\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ \hline 100 & (H,H) & 1 & 1.716 & -0.269 & -0.277 & 1.730 & 0.725 & 0.503\\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ \hline 1000 & (T,T) & 1 & 1.564 & -0.426 & -0.415 & 1.564 & 0.574 & 0.500\\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ \hline \end{array} !!!Def: Teorema Bajo las mismas condiciones que aseguran la convergencia del $Q$-Learning a la política óptima en los MDP, en los juegos de suma cero el Minimax-$Q$-Learning converge al valor del juego en el juego propio. Tampoco en este caso se garantiza la tasa de convergencia ni la acumulación de recompensas óptimas. Podemos conseguir una convergencia más rápida si estamos dispuestos a sacrificar la garantía de encontrar una estrategia $maxmin$ perfectamente óptima. Por ejemplo, se puede considerar el marco de **Aprendizaje Probablemente Correcto** (**PAC**). En cualquier caso, su análisis supera las posibilidades en las que podemos entrar en este curso. ## Más allá de los juegos estocásticos de suma cero Hasta ahora hemos mostrado resultados para la clase de juegos estocásticos de suma cero. Aunque los algoritmos discutidos, en particular el minimax-$Q$-Learning, siguen estando bien definidos en el caso general, la garantía de conseguir la máxima estrategia de pago es menos convincente. Otra subclase de juegos estocásticos que se ha abordado es la de los juegos de pago común (coordinación pura), en los que todos los agentes reciben la misma recompensa por un resultado. Esta clase tiene la ventaja de reducir el problema a la identificación de un perfil de acción óptimo y a la coordinación con los demás agentes para jugarlo. En muchos sentidos, este problema puede considerarse realmente como un problema de control distribuido de un solo agente. Se trata de un problema relativamente bien entendido, y existen varios algoritmos para él, dependiendo precisamente de cómo se defina el problema. Por otro lado, ampliar los algoritmos de aprendizaje por refuerzo al caso de la suma general es bastante problemático. Ha habido intentos de generalizar el $Q$-Learning a los juegos de suma general, pero aún no han tenido verdadero éxito. Como se comentó, la cuestión de lo que significa aprender en juegos de suma general es sutil. Un criterio que hemos discutido es la convergencia al equilibrio de Nash del juego por rondas durante el juego propio. No se ha propuesto ninguna generalización del $Q$-Learning que tenga esta propiedad. ## ... Basado en Creencias También existe una versión del aprendizaje por refuerzo que incluye la modelización explícita del otro agente, o agentes, siguiendo las siguientes ecuaciones: $$Q_{t+1}(s_t, a_t) \leftarrow (1 - \alpha)Q_t(s_t, a_t) + \alpha_t(r(s_t, a_t) + β\ V_t(s_{t+1}))$$ $$V_t(s) \leftarrow \max_{a_i}\sum_{a_{-i}\subseteq A_{-i}} Q_t(s, (a_i, a_{-i}))Pr_i(a_{-i})$$ En esta versión, el agente actualiza el valor del juego utilizando la probabilidad que asigna al oponente, u oponentes, que juegan cada perfil de acción. Por supuesto, la función de creencia debe actualizarse después de cada jugada. Cómo se actualiza, depende de cuál sea la función. De hecho, el aprendizaje por refuerzo basado en creencias no es un procedimiento único, sino una familia, cada uno de cuyos miembros se caracteriza por cómo se forman y actualizan las creencias. Por ejemplo, en una versión las creencias son del tipo considerado en el juego ficticio, y en otra son bayesianas al estilo del aprendizaje racional. Hay algunos resultados experimentales que muestran la convergencia al equilibrio en el juego propio para algunas versiones del aprendizaje por refuerzo basado en creencias y algunas clases de juegos, pero no hay resultados teóricos. # Aprendizaje Sin Arrepentimiento Una regla de aprendizaje es **universalmente consistente** o (equivalentemente) **sin arrepentimiento** si, en términos generales, contra cualquier conjunto de oponentes produce una recompensa que no es menor que la que el agente podría haber obtenido jugando cualquiera de sus estrategias puras durante todo el tiempo. Más concretamente: !!!Def: Definición (Arrepentimiento) Si $\alpha^t$ es la recompensa media que el agente recibió hasta el momento $t$, y $\alpha^t(s)$ la recompensa media que el agente habría recibido hasta el momento $t$ si hubiera jugado la estrategia pura $s$ en su lugar, suponiendo que todos los demás agentes siguen jugando como lo hicieron, el **arrepentimiento** que experimenta un agente en el momento $t$ por no haber jugado $s$ es: $R^t(s) = \alpha^t - \alpha^t(s)$. Se dice que una regla de aprendizaje **no presenta arrepentimiento** si garantiza que con alta probabilidad el agente no experimentará ningún arrepentimiento positivo: !!!Def: Definición (Regla de aprendizaje sin arrepentimiento) Una regla de aprendizaje **no presenta arrepentimiento** si para cualquier estrategia pura, $s$, del agente se cumple que: $$Pr([\lim \inf R^t(s)] \leq 0) = 1$$ La cuantificación es sobre todas las estrategias puras del agente, pero no habría diferencia si en lugar de ello se cuantificara sobre todas las estrategias mixtas del juego. Además, esta garantía es sólo en la expectativa, ya que la estrategia del agente será en general mixta, y por lo tanto el pago obtenido en cualquier momento dado es incierto. Es importante tener en cuenta que este requisito ignora la posibilidad de que el juego de los oponentes pueda cambiar como resultado del propio juego del agente. Por lo que es válido para los oponentes estacionarios, y podría ser una aproximación razonable en el contexto de un gran número de oponentes (como en un mercado de valores público), pero no tanto en el contexto de un pequeño número de agentes (del tipo en el que la teoría de juegos tiende a centrarse). Por ejemplo, en el juego del dilema del prisionero con infinitas iteraciones la única estrategia que no presenta arrepentimiento es la de desertar siempre. Esto excluye las estrategias que se aprovechan del comportamiento cooperativo del adversario, como el Tit-for-Tat. A lo largo de los años se han desarrollado diversas técnicas de aprendizaje sin arrepentimiento. Dos de las más famosas son: - **Emparejamiento con arrepentimiento**. En cada paso de tiempo, cada acción se elige con una probabilidad proporcional a su arrepentimiento. Es decir, $$\sigma^{t+1}_i(s) =\frac{R^t(s)}{\sum_{s'\in S_i} R^t(s')}$$ donde $\sigma^{t+1}_i(s)$ es la probabilidad de que el agente $i$ juegue la estrategia pura $s$ en el tiempo $t + 1$. - **Juego ficticio suave**. En lugar de jugar la mejor respuesta a la frecuencia empírica del juego del adversario, como prescribe el juego ficticio, se introduce una perturbación que disminuye gradualmente con el tiempo. Es decir, en lugar de adoptar en el tiempo $t+1$ una estrategia pura $s_i$ que maximice $u_i(s_i, P^t)$, donde $P^t$ es la distribución empírica del juego del adversario hasta el tiempo $t$, el agente $i$ adopta una estrategia mixta $\sigma_i$ que maximiza $u_i(s_i, P^t)+\lambda v_i(\sigma_i)$, donde $\lambda$ es una constante cualquiera, y $v_i$ es una función suave y cóncava con límites en el simplex unitario (por ejemplo, $v_i$ puede ser la función de entropía, $v_i(\sigma_i) = - \sum_{S_i} \sigma_i(s_i) \log \sigma_i(s_i)$). Se puede demostrar (usando el **Teorema de Aproximación de Blackwell**) que el emparejamiento con arrepentimiento no presenta arrepentimiento, y que el juego ficticio suave se aproxima a la ausencia de arrepentimiento cuando $\lambda \to 0$. # Aprendizaje Dirigido El aprendizaje sin arrepentimiento es un enfoque para garantizar buenas recompensas, pero, como ya hemos comentado, este sentido de *bueno* tiene algunos inconvenientes. Por ello, vamos a presentar un sentido alternativo de *bueno*, que mantiene el requisito de la mejor respuesta, pero lo limita a una clase particular de oponentes. La intuición que guía este enfoque es que en cualquier escenario estratégico, en particular en un escenario de aprendizaje multiagente, se tiene cierto conocimiento de los agentes del entorno (por ejemplo, un jugador de ajedrez ha estudiado las jugadas anteriores de su oponente), por lo que tiene sentido intentar optimizar contra este conjunto de oponentes, en lugar de hacerlo contra oponentes completamente desconocidos. Desde el punto de vista técnico, el modelo de **aprendizaje dirigido** toma como parámetro una clase de adversarios probables (la *clase objetivo*) y se le exige que se comporte especialmente bien contra estos adversarios probables. Además, se quiere garantizar al menos la máxima recompensa contra oponentes que no pertenecen a la clase objetivo. Por último, una propiedad adicional deseable es que el algoritmo funcione bien en el juego propio. Para juegos con sólo dos agentes, estos requerimientos se traducen en las siguientes propiedades: !!!Def: Propiedades del Aprendizaje Dirigido - **Optimalidad del objetivo**: Contra cualquier oponente de la clase objetivo, el resultado esperado es el resultado de la mejor respuesta. - **Seguridad**: Contra cualquier oponente, el resultado esperado es al menos el valor de seguridad individual (o máximo) para el juego. - **Autocompatibilidad**: El juego propio es estrictamente eficiente en Pareto. Como además nos interesa que el aprendizaje sea rápido, no sólo que funcione así en el aprendizaje en el límite, necesitamos permitir alguna desviación del ideal. Por tanto, modificamos los requisitos de la siguiente manera: !!!Def: Definición (Aprendizaje dirigido eficiente) Una regla de aprendizaje muestra un **aprendizaje dirigido eficiente** si para cada $\varepsilon > 0$ y $1 > \delta > 0$, existe un $M=pol(1/\varepsilon, 1/\delta)$ tal que después de $M$ pasos de tiempo, con probabilidad mayor que $1 - \delta$, se alcanzan los tres requisitos de recompensa enumerados anteriormente dentro de $\varepsilon$. Hay algunas diferencias con el aprendizaje sin arrepentimiento. Por ejemplo, si consideremos el aprendizaje en un juego de dilema del prisionero iterado, y tomamos como clase objetivo la formada por todos los oponentes cuyas estrategias se basan en la iteración anterior (esto incluye la estrategia Tit-for-Tat), entonces el aprendizaje dirigido exitoso dará como resultado una cooperación constante, mientras que el aprendizaje sin arrepentimiento aconseja una deserción constante. ¿Es difícil conseguir un aprendizaje dirigido eficaz? La respuesta depende, por supuesto, de la clase objetivo. !!! Se ha demostrado que existen procedimientos de aprendizaje correctos (con respecto a este criterio) para la clase de oponentes estacionarios y la clase de oponentes cuya memoria está limitada a una ventana finita en el pasado. El enfoque básico consiste en construir una serie de bloques de construcción y, a continuación, especializarlos y combinarlos de forma diferente en función de la configuración precisa. Los detalles de los algoritmos pueden complicarse, especialmente en el caso de adversarios no estacionarios, pero el flujo esencial es el siguiente: 1. Se empieza suponiendo que el adversario está en el conjunto objetivo y se aprende la mejor respuesta para el agente concreto bajo esta suposición. 2. Si los resultados que se obtienen se desvían demasiado de las expectativas: 1. Se señala al oponente para saber si está empleando la misma estrategia de aprendizaje. Si lo hace, coordínarse con él para obtener un resultado pareto-eficiente. 2. Si sus resultados se alejan demasiado: Se juega la estrategia de seguridad. Hasta ahora hemos restringido el debate a juegos de dos jugadores. ¿Podemos generalizar los criterios, y los algoritmos, a juegos con más jugadores? La respuesta es afirmativa, pero hay que tener cuidado con algunos detalles. Por ejemplo, en el caso de dos agentes tenemos que preocuparnos de tres casos: si el oponente está en el conjunto objetivo, si es un agente que juega por sí mismo, o no es ninguno de esos dos casos. Con un conjunto mayor de jugadores, debemos considerar tres conjuntos de agentes: agentes que juegan por sí mismos (es decir, agentes que utilizan el algoritmo en cuestión), agentes en el conjunto objetivo, y agentes sin restricciones. En estas condiciones, debemos preguntarnos cómo los agentes del primer conjunto pueden lograr conjuntamente un resultado Pareto-eficiente contra el segundo conjunto y, sin embargo, protegerse de la explotación de los agentes del tercer conjunto. Esta aproximación plantea cuestiones sobre la posible **coordinación** entre los agentes: - ¿Pueden los agentes que juegan por su cuenta coordinarse de forma distinta a la implícita a través de sus acciones? - ¿Pueden los oponentes, ya sean del conjunto objetivo o no, coordinarse de otra manera que no sea a través de las acciones? # Aprendizaje por Grandes Poblaciones Vamos a cambiar el enfoque y pasaremos de modelos de aprendizaje de agentes individuales a modelos de aprendizaje de poblaciones de agentes (aunque, como veremos, tendrá consecuencias en la perspectiva para un solo agente). !!! Cuando hablamos de aprendizaje en una población de agentes, nos referimos al cambio en la constitución y el comportamiento de esa población a lo largo del tiempo. Estos modelos fueron desarrollados originalmente por biólogos de poblaciones para modelar el proceso de evolución biológica, y posteriormente fueron adoptados y adaptados por otros campos. Comenzaremos por el modelo de **dinámica del replicador**, un modelo sencillo inspirado en la biología evolutiva. Después presentaremos el concepto de **estrategias evolutivamente estables**, un concepto de estabilidad que está relacionado con la dinámica del replicador. Y concluimos con un modelo algo diferente de simulación basada en agentes y el concepto de **convenciones emergentes**. ## La Dinámica del Replicador La **dinámica del replicador** modela una población que experimenta interacciones frecuentes. Nos concentraremos en el caso simétrico de dos jugadores, en el que los agentes juegan repetidamente un juego por rondas simétrico de dos jugadores entre sí: !!!Def: Definición (Juego simétrico $2 \times 2$) Diremos que un juego de forma normal de 2 jugadores con 2 acciones es un **juego simétrico** si tiene la siguiente forma: \begin{array}{|c|c|c|} \hline & A & B \\ \hline A & x,x & u,v\\ \hline B & v,u & y,y\\ \hline \end{array} Intuitivamente, un juego simétrico es aquel en el que los agentes no tienen roles distintos en el juego, y que el pago de los agentes no depende de sus identidades. Ya hemos visto varios ejemplos de este tipo de juegos, por ejemplo, el dilema del prisionero. !!! La dinámica del replicador describe una población de agentes que juegan un juego de este tipo de forma continua. En cada momento, cada agente sólo juega una estrategia pura: informalmente, el modelo empareja a todos los agentes y los hace jugar entre sí, obteniendo cada uno de ellos una determinada retribución del juego individual en el que participa (que se considera el *fitness* o *aptitud* del agente). A partir de este punto interviene la inspiración biológica: cada agente se *reproduce* de forma proporcional a su fitness y el proceso se repite. La cuestión es si el proceso anterior converge a una proporción fija de las distintas estrategias puras dentro de la población y, en caso afirmativo, cuáles son esas proporciones fijas. Obsérvese la similitud del procedimiento con los Algoritmos Genéticos para optimizar la estrategia por medio de poblaciones. En realidad, el modelo matemático real que se utiliza es un poco diferente: 1. En primer lugar, nunca modelamos explícitamente el juego entre conjuntos particulares de jugadores; sólo modelamos las proporciones de las poblaciones asociadas a una estrategia determinada. 2. En segundo lugar, el modelo no es de repeticiones discretas de juego, sino de evolución continua. 3. En tercer lugar, más allá de la reproducción basada en la aptitud, también hay un elemento aleatorio que afecta a las proporciones de la población (de nuevo, debido a la inspiración biológica, este elemento aleatorio se denomina **mutación**). El modelo formal es el siguiente: !!!Def Dado un juego de forma normal $G = (\{1, 2\}, A, u)$, denotaremos por $\varphi_t(a)$ el número de jugadores que juegan la acción $a$ en el tiempo $t$, y denotemos por $\theta_t(a)$ la proporción de jugadores que juegan la acción $a$ en el momento $t$, es decir: $$\theta_t(a) = \frac{\varphi_t(a)}{\sum_{a'\in A} \varphi_t(a')}$$ Denotaremos con $\varphi_t$ el vector de medidas de los jugadores que juegan cada acción, y con $\theta_t$ el vector de proporciones de población para cada acción. La utilidad esperada de cualquier jugador individual por jugar la acción $a$ en el momento $t$ será: $$u_t(a) = \sum_{a'} \theta_t(a')u(a, a')$$ El cambio en el número de agentes que juegan la acción $a$ en el momento $t$ se define proporcional a su aptitud, es decir, a su retribución media en el momento actual: $$\dot{\varphi}_t(a) = \varphi_t(a)u_t(a)$$ El número absoluto de agentes de cada tipo no es importante, sólo lo son las proporciones relativas. Definiendo la retribución media esperada de toda la población como: $$u^*_t = \sum_a \theta_t(a)u_t(a)$$ tenemos que el cambio en la fracción de agentes que juegan la acción $a$ en el tiempo $t$ es: $$\dot{\theta}_t(a) =\frac{[\dot{\varphi}_t(a)\sum_{a'\in A} \varphi_t(a')]-[\varphi_t(a)\sum_{a'\in A} \dot{\varphi}_t(a')]}{[\sum_{a'\in A} \varphi_t(a')]^2} = \theta_t(a)[u_t(a) - u^*_t]$$ El sistema que hemos definido tiene una propiedad muy intuitiva: si una acción lo hace mejor que la media de la población, entonces la proporción de la población que juega esta acción aumenta, y viceversa. Obsérvese que no es necsario que sea óptima, incluso una acción que no es la mejor respuesta al estado actual de la población puede crecer cuando su recompensa esperada es mejor que la media de la población. ¿Cómo debemos interpretar este modelo evolutivo? Una interpretación directa es que describe a los agentes que interactúan y se replican repetidamente dentro de una gran población. Sin embargo, también podemos interpretar la fracción de agentes que juegan una determinada estrategia como la estrategia mixta de un único agente, y el proceso como el de dos agentes idénticos que actualizan repetidamente sus estrategias mixtas idénticas basándose en su interacción previa. Visto así, salvo por su naturaleza de tiempo continuo, el modelo evolutivo no es tan diferente del modelo de juegos iterados como parece a primera vista. La ventaja que tenemos ahora es que, al disponer de una dinámica (hay un cambio temporal) los equilibrios dinámicos podemos relacionarlos con los equilibrios de la Teoría de Juegos. Por lo que vamos a examinar los puntos de equilibrio de este sistema, pero antes de hacerlo, necesitamos una definición de estabilidad: !!!Def: Definición (Estado estacionario) Un **estado estacionario** de una población que utiliza la dinámica del replicador es un estado poblacional $\theta$ tal que para todo $a\in A$, $\dot{\theta}(a) = 0$. En otras palabras, un estado estacionario es un estado en el que los porcentajes poblacionales de cada acción son constantes. Aunque a primera vista parece una definición correcta, este concepto de estabilidad tiene un problema importante: cualquier estado en el que todos los jugadores jueguen la misma acción es un estado estacionario. Los porcentajes de población de las acciones permanecerán constantes porque la dinámica del replicador no permite la *aparición* de estrategias que no se estén jugando ya. Para no permitir estos estados, a menudo exigiremos que nuestros estados estacionarios sean estables: !!!Def: Definición (Estado estacionario estable) Un estado estacionario, $\theta$, de una dinámica replicadora es **estable** si existe un $\varepsilon > 0$ tal que para cada entorno, $U$, de $\theta$ existe otro entorno, $U'$, de $\theta$ tal que si $\theta_0 \in U'$ entonces $\theta_t \in U$ para todo $t > 0$. Es decir, si el sistema comienza lo suficientemente cerca del estado estacionario, entonces permanece cerca. Por último, podríamos definir un estado de equilibrio que, si se perturba, acabará volviendo al estado. A esto lo llamamos **estabilidad asintótica**: !!!Def: Definición (Estado asintóticamente estable) Un estado estacionario, $\theta$, de una dinámica replicadora es **asintóticamente estable** si es estable, y además existe un $\varepsilon > 0$ tal que para cada $\varepsilon$-entorno, $U$, de $\theta$ se verifica que si $\theta_0 \in U$ entonces $\lim_{t\to \infty} \theta_t = \theta$. El siguiente ejemplo ilustra algunos de estos conceptos: !!!Tip Consideremos una población homogénea que juega el juego de Anti-Coordinación: \begin{array}{|c|c|c|} \hline & A & B \\ \hline A & 0,0 & 1,1\\ \hline B & 1,1 & 0,0\\ \hline \end{array} El juego tiene dos equilibrios de Nash de estrategia pura, $(A, B)$ y $(B, A)$, y un equilibrio de estrategia mixta en el que ambos jugadores seleccionan acciones de la distribución $(0.5, 0.5)$. Debido a la naturaleza simétrica del escenario, no hay forma de que la dinámica del replicador converja a los equilibrios de estrategia pura. Sin embargo, nótese que el estado correspondiente al equilibrio de estrategia mixta es un estado estacionario, porque cuando la mitad de los jugadores juegan con $A$ y la otra mitad con $B$, ambas estrategias tienen la misma recompensa esperada $(0.5)$ y las cuotas de población de cada una son constantes. Además, hay que tener en cuenta que este estado también es asintóticamente estable. La dinámica del replicador, cuando se inicia en cualquier otro estado de la población (donde la proporción de jugadores que juegan $A$ es mayor o menor que $0.5$) convergerá de nuevo al estado $(0.5, 0.5)$. Más formalmente, podemos expresar esto como: $$\dot{\theta}(A) = \theta(A)(1 - \theta(A) - 2\theta(A)(1 - \theta(A))) = \theta(A)(1 - 3\theta(A) + 2\theta(A)^2)$$ Esta expresión es positiva para $\theta(A) \le 0.5$, exactamente $0$ en $0.5$, y negativa para $\theta(A) > 0.5$, lo que implica que el estado $(0.5, 0.5)$ es asintóticamente estable. Este ejemplo sugiere que puede haber una relación especial entre los equilibrios de Nash y los estados en la dinámica del replicador. Y, efectivamente, así es, como indican los siguientes resultados: !!!Def: Teorema Dado un juego en forma normal $G = (\{1, 2\}, A = \{a_1,\dots, a_k\}, u)$, si el perfil de estrategia $(s, s)$ es un equilibrio de Nash de estrategia mixta (simétrico) de $G$, entonces el vector de cuota de población $\theta = (s(a_1),\dots , s(a_k))$ es un estado estacionario de la dinámica del replicador de $G$. En otras palabras, todo equilibrio simétrico de Nash es un estado estacionario. La razón de esto es bastante sencilla: en un estado correspondiente a un equilibrio de Nash mixto, todas las estrategias que se juegan tienen la misma retribución media, por lo que las cuotas de la población permanecen constantes. Sin embargo, como se ha mencionado antes, no todos los estados estables de la dinámica del replicador son equilibrios de Nash. En particular, los estados en los que no se juegan todas las acciones pueden ser estados estables porque la dinámica del replicador no puede introducir nuevas acciones, incluso cuando el perfil de estrategia mixta correspondiente no es un equilibrio de Nash. Por otro lado, la relación entre los equilibrios de Nash y los estados estables es mucho más estrecha: !!!Def: Teorema Dado un juego en forma normal $G = (\{1, 2\}, A=\{a_1,\dots, a_k\}, u)$ y una estrategia mixta $s$, si el vector de proporciones de población $\theta = (s(a_1),\dots, s(a_k))$ es un estado estacionario estable de la dinámica del replicador de $G$, entonces el perfil de estrategia $(s, s)$ es un equilibrio de Nash de estrategia mixta de $G$. En otras palabras, todo estado estacionario estable es un equilibrio de Nash. Para probarlo, es más fácil entender el contrarecíproco de esta afirmación: si un perfil de estrategia mixta no es un equilibrio de Nash, entonces alguna acción debe tener una recompensa mayor que algunas de las acciones en su soporte. Por tanto, en la dinámica del replicador, la proporción de la población que utiliza esta acción mejor aumentará, cuando exista. Por tanto, no es posible que el estado de la población correspondiente a este perfil de estrategia mixta sea un estado estacionario estable. Por último, mostramos que la estabilidad asintótica corresponde a una noción más fuerte que el equilibrio de Nash. Para ello, introducimos la definición de perfección de mano temblorosa: !!!Def: Definición (Equilibrio perfecto de mano temblorosa) Un perfil de estrategia mixta $s$ es un **equilibrio perfecto (de mano temblorosa)** de un juego en forma normal $G$ si existe una secuencia $s^0, s^1,\dots$, de perfiles de estrategia totalmente mixta tal que $\lim_{n\to\infty} s^n = s$, y tal que para cada $s^k$ en la secuencia y cada jugador $i$, la estrategia $s_i$ es una mejor respuesta a las estrategias $s^k_{-i}$. Además, decimos informalmente que un perfil de estrategia de equilibrio está **aislado** si no existe otro perfil de estrategia de equilibrio en el entorno (es decir, alcanzable mediante pequeñas perturbaciones de las estrategias) del perfil original. Podemos relacionar la perfección de la mano temblorosa con la dinámica del replicador como sigue: !!!Def: Teorema Dado un juego de forma normal $G = (\{1, 2\}, A, u)$ y una estrategia mixta $s$, si el vector de participación de la población $\theta = (s(a_1), \dots , s(a_k))$ es un estado estacionario asintóticamente estable de la dinámica del replicador de $G$, entonces el perfil de estrategia $(s, s)$ es un equilibrio de Nash de $G$ que es perfecto y aislado. ## Estrategias Evolutivamente Estables Una **estrategia evolutivamente estable** (**ESS**) es un concepto de estabilidad inspirado en la dinámica del replicador pero que, a diferencia de los estados estables que se han discutido anteriormente, no requiere la dinámica del replicador, ni ningún proceso dinámico, de forma explícita... es un concepto de solución estática. Por tanto, en principio no está intrínsecamente ligado al aprendizaje. A grandes rasgos, una estrategia evolutivamente estable es una estrategia mixta que es *resistente a la invasión* de nuevas estrategias. Supongamos que una población de jugadores juega una estrategia mixta concreta en la dinámica del replicador. Supongamos entonces que se añade a la población una pequeña población de *invasores* que juegan una estrategia diferente. Se considera que la estrategia original es una ESS si obtiene una mayor retribución contra la mezcla resultante de las estrategias nueva y antigua que los invasores, con lo que se *ahuyenta* a los invasores: !!!Def: Definición (Estrategia evolutivamente estable (ESS)) Dado un juego simétrico en forma normal de dos jugadores $G = (\{1, 2\}, A, u)$ y una estrategia mixta $s$, decimos que $s$ es una **estrategia evolutivamente estable** si y sólo si para algún $\varepsilon > 0$ y para todas las demás estrategias $s'$ se verifica: $$u(s, (1 - \varepsilon)s + \varepsilon s') > u(s', (1 - \varepsilon)s + \varepsilon s')$$ Podemos utilizar las propiedades de $u$ para plantear esta condición de forma equivalente: $$(1 - \varepsilon)u(s, s) + \varepsilon u(s, s') > (1 - \varepsilon)u(s', s) + \varepsilon u(s', s')$$ Como esto sólo tiene que cumplirse para valores de $\varepsilon$ pequeños, lo anterior equivale a exigir que, o bien se cumpla $u(s, s) > u(s', s)$, o bien se cumplan tanto $u(s, s) = u(s', s)$ como $u(s, s') > u(s', s')$. También podemos establecer una definición más débil de ESS: !!!Def: Definición (ESS débil) $s$ es una **estrategia evolutivamente estable débil** si y sólo si para algún $\varepsilon > 0$ y para todo $s'$ se verifica que, o bien $u(s, s) > u(s', s)$ se mantiene, o bien $u(s, s) = u(s', s)$ y $u(s, s') \geq u(s', s')$ se mantienen. Esta definición más débil incluye estrategias en las que el invasor lo hace tan bien contra la población original como contra sí mismo. En estos casos, la población que utiliza la estrategia invasora no crecerá, pero tampoco se reducirá. !!!Tip: Juego Halcón-Paloma Dos animales se pelean por un premio, un trozo de comida. Cada animal puede elegir entre dos comportamientos: un comportamiento agresivo de halcón, $H$, o un comportamiento complaciente de paloma, $P$. El premio vale $6$ para cada uno de ellos. Pelearse cuesta $5$ a cada jugador. Cuando un halcón se encuentra con una paloma, obtiene el premio sin pelear, por lo que los pagos son $6$ y $0$, respectivamente. Cuando dos palomas se encuentran, se reparten el premio sin luchar, por lo que la recompensa es de $3$ para cada una. Cuando dos halcones se encuentran, se produce una pelea, que cuesta $5$ a cada jugador (o, lo que es lo mismo, produce $-5$). Además, cada jugador tiene un $50\%$ de posibilidades de quedarse con el premio, lo que añade un beneficio esperado de $3$, para un resultado global de $-2$. \begin{array}{|c|c|c|} \hline & H & P \\ \hline H & -2,-2 & 6,0\\ \hline P & 0,6 & 3,3\\ \hline \end{array} No es difícil comprobar que el juego tiene un único equilibrio simétrico de Nash $(s, s)$, donde $s = ( \frac{3}{5}, \frac{2}{5})$, y que $s$ es también la única EES del juego. Para confirmar que $s$ es un ESS, necesitamos que para todo $s'\neq s$, $u(s, s) = u(s', s)$ y $u(s, s') > u(s', s')$. La condición de igualdad es cierta en cualquier equilibrio de estrategia mixta con soporte completo, por lo que se deduce directamente. Para demostrar que la desigualdad también se cumple, basta con encontrar $s'$ (equivalentemente, la probabilidad de jugar $H$) que minimiza $f(s') = u(s, s') - u(s', s')$. Expandiendo $f(s')$ vemos que es una ecuación cuadrática con un (único) máximo en $s' = s$, lo que demuestra el resultado. Esta conexión entre una EES y un equilibrio de Nash no es accidental. Los dos teoremas siguientes captan esta conexión: !!!Def: Teorema Dado un juego simétrico de forma normal para dos jugadores $G = (\{1, 2\}, A, u)$ y una estrategia mixta $s$, si $s$ es ESS entonces $(s, s)$ es un equilibrio de Nash de $G$. Esto es fácil de demostrar. Obsérvese que, por definición, si $s$ es ESS, debe satisfacer: $u(s, s) \geq u(s', s)$. En otras palabras, es una mejor respuesta a sí misma y, por tanto, debe ser un equilibrio de Nash. Sin embargo, no todo equilibrio de Nash es un ESS. Esta propiedad se garantiza sólo para los equilibrios estrictos: !!!Def: Teorema Dado un juego simétrico de forma normal para dos jugadores $G = (\{1, 2\}, A, u)$ y una estrategia mixta $s$, si $(s, s)$ es un equilibrio de Nash estricto (simétrico) de $G$, entonces $s$ es EES. Esto también es fácil de demostrar. Obsérvese que para cualquier equilibrio de Nash estricto $s$ debe darse el caso de que: $u(s, s) > u(s', s)$, que le permite satisfacer el primer criterio de una ESS. La propiedad ESS también está relacionada con la idea de estabilidad en la dinámica del replicador: !!!Def: Teorema Dado un juego simétrico de forma normal de dos jugadores $G = (\{1, 2\}, A, u)$ y una estrategia mixta $s$, si $s$ es ESS entonces es un estado estacionario asintóticamente estable de la dinámica del replicador de $G$. Intuitivamente, si un estado es ESS, sabemos que será resistente a las invasiones de otras estrategias, por lo que cuando esta estrategia está representada por una población en la dinámica del replicador, será resistente a pequeñas perturbaciones. Sin embargo, lo interesante es que lo contrario no es cierto. La razón es que en la dinámica del replicador sólo se pueden heredar las estrategias puras, por lo que algunos estados que son asintóticamente estables en realidad no serían resistentes a la invasión de una estrategia mixta y, por lo tanto, no serían una ESS. ## Simulación basada en agentes y Convenciones Emergentes Ya mencionamos que, aunque está motivada por una noción de proceso dinámico dentro de una población, en realidad la dinámica del replicador sólo modela las estadísticas del proceso, no sus detalles. Hay otros modelos de grandes poblaciones que proporcionan un modelo más detallado del proceso, con muchos parámetros que pueden afectar a la dinámica. Llamamos a estos modelos, que modelan explícitamente a los agentes individuales, modelos de **simulación basados en agentes**. Vamos a examinar uno de estos modelos, orientado a la investigación de cómo surgen las convenciones en una sociedad. En cualquier sistema multiagente realista es crucial que los agentes se pongan de acuerdo en ciertas leyes sociales, para disminuir los conflictos entre ellos y promover el comportamiento cooperativo. Sin estas leyes, incluso los objetivos más sencillos podrían resultar inalcanzables para cualquiera de los agentes, o al menos no se podrían alcanzar de forma eficiente (basta con imaginar la conducción en ausencia de normas de tráfico). Una ley social restringe las opciones disponibles para cada agente. Un caso especial de leyes sociales son las convenciones sociales, que limitan a los agentes a exactamente una opción de las muchas disponibles (por ejemplo, conducir siempre por el lado derecho de la carretera). Una buena ley o convención social establece un equilibrio entre, por un lado, permitir a los agentes la suficiente libertad para alcanzar sus objetivos y, por otro, restringirlos para que no interfieran demasiado entre sí. Aunque podríamos preguntamos cómo pueden ser diseñadas las leyes y convenciones sociales por un diseñador social, aquí vamos a interesarnos por cómo pueden surgir dichas convenciones de forma orgánica. A grandes rasgos, el proceso que pretendemos estudiar es uno en el que los agentes individuales interactúan ocasionalmente entre sí, y como resultado obtienen alguna información nueva. Basándose en su información personal acumulada, cada agente actualiza su comportamiento a lo largo del tiempo. Este proceso recuerda a la dinámica del replicador, pero hay diferencias cruciales. Vamos a restringir la discusión a los juegos simétricos de dos jugadores y dos opciones como el que muestra la siguiente tabla: \begin{array}{|c|c|c|} \hline & A & B \\ \hline A & x,x & u,v\\ \hline B & v,u & y,y\\ \hline \end{array} A diferencia de la dinámica del replicador, aquí asumimos un proceso discreto y, además, suponemos que en cada etapa juegan exactamente un par de agentes seleccionados al azar de la población. Esto contrasta fuertemente con la dinámica del replicador, que puede interpretarse como la suposición implícita de que casi todas las parejas de agentes juegan antes de actualizar sus elecciones de acción. En este modelo discreto, cada agente es rastreado individualmente y, de hecho, diferentes agentes acaban poseyendo información muy diferente. Lo más importante es que, a diferencia de la dinámica del replicador, la evolución del sistema no está definida por algunas estadísticas globales del sistema. En su lugar, cada agente decide cómo jugar la siguiente partida basándose en su experiencia individual acumulada hasta el momento. Pero hay dos restricciones que imponemos a estas reglas. !!!Def: Restricciones - **Anonimato**: La función de selección no puede basarse en las identidades de los agentes ni en los nombres de las acciones. - **Localidad**: La función de selección es puramente una función de la historia personal del agente. En particular, no es una función de las propiedades globales del sistema. El requisito del anonimato está relacionado con que nos interesa saber cómo surgen las convenciones sociales, pero cuando no podemos prever de antemano los juegos que se van a realizar. Por ejemplo, si sabemos que el problema de coordinación será el de decidir si se conduce por la izquierda o la derecha de la carretera, podemos utilizar los nombres *izquierda* y *derecha* en la regla de selección de acciones. En particular, podemos admitir la regla de actualización trivial que hace que todos los agentes conduzcan por la derecha inmediatamente. En cambio, el tipo de problema de coordinación que nos ocupa está mejor tipificado por el siguiente ejemplo: !!!Tip Consideremos una colección de robots de fabricación que han estado operando en una planta durante cinco años, momento en el que llega una nueva colección de piezas que deben ser ensambladas. El montaje requiere el uso de una de las dos herramientas de fijación disponibles, que se introdujeron hace tres años (y, por tanto, eran desconocidas para el diseñador de los robots hace cinco años). Cualquiera de las herramientas servirá, pero si dos robots utilizan herramientas diferentes, incurrirán en el alto coste de la conversión cuando llegue el momento de acoplar sus respectivas piezas. Nuestro objetivo es que los robots aprendan a utilizar el mismo tipo de herramienta. Lo que hay que destacar de este ejemplo es que hace cinco años el diseñador podría haber establecido reglas de la forma general: *Si en el futuro tienes varias opciones, cada una de las cuales ha sido probada tantas veces y ha dado esta recompensa, entonces la próxima vez haz la siguiente elección* Sin embargo, el diseñador no podría haberse referido a las opciones específicas de la herramienta, ya que éstas se inventaron dos años después. La prohibición de utilizar las identidades de los agentes en las reglas (por ejemplo, *si ves que el Robot 17 utiliza una herramienta de cierto tipo, haz lo mismo, pero si ves que el Robot 5 lo hace, no importa*) tiene una motivación similar. En una sociedad dinámica, los agentes aparecen y desaparecen, lo que niega al diseñador la posibilidad de anticiparse a la norma. A veces se puede hacer referencia a los roles de los agentes (como el Robot Jefe), y hacer que sean tratados de manera especial, pero no discutiremos este aspecto aquí. Por último, la noción de *historia personal* puede afinarse aún más. Supondremos que el agente tiene acceso a la acción que ha realizado y a la recompensa que ha recibido en cada momento. Se podría suponer además que el agente observa las elecciones de los demás en los juegos en los que ha participado, y quizás también sus recompensas. Pero vamos a estudiar específicamente una regla de selección de acciones que no hace esta suposición. Esta regla, denominada **regla de la mayor recompensa acumulada** (**HCR**), consiste en el siguiente procedimiento de aprendizaje: 1. Inicializar la recompensa acumulada para cada acción (por ejemplo, a $0$). 2. Elegir una acción inicial. 3. Jugar según la acción actual y actualizar la recompensa acumulada. 4. Cambiar a una nueva acción si la recompensa total obtenida de esa acción en las últimas $m$ iteraciones es mayor que la recompensa obtenida de la acción actualmente elegida en el mismo periodo de tiempo. 5. Ir al paso 3. El parámetro $m$ en el procedimiento denota un límite finito, pero el límite puede variar. El HCR es un procedimiento sencillo y natural, pero admite muchas variantes. Se pueden considerar reglas que utilicen una acumulación ponderada de retroalimentación en lugar de una acumulación simple, o que normalicen la recompensa de alguna manera en lugar de mirar los números absolutos. Sin embargo, incluso esta regla básica da lugar a propiedades interesantes. En particular, bajo ciertas condiciones garantiza la convergencia a una *buena* convención. !!!Def: Teorema Sea $G$ un juego simétrico como el definido anteriormente, con $x > 0$ o $y > 0$ o $x = y > 0$, y o bien $u \le 0$ o $v \le 0$ o bien $x \le 0$ o $y \le 0$. Entonces, si todos los agentes emplean la regla HCR, se verifica que para cada $\varepsilon > 0$ existe un entero $k$ tal que después de $k$ iteraciones del proceso la probabilidad de que se alcance una convención social es mayor que $1 - \varepsilon$. Una vez alcanzada una convención, nunca se abandona. Además, esta convención garantiza al agente una retribución que no es menor que el valor máximo de $G$. Hay muchas más preguntas que hacer sobre la evolución de las convenciones: ¿Con qué rapidez evoluciona una convención? ¿Cómo depende este tiempo de los distintos parámetros, por ejemplo $m$, la historia recordada? ¿Cómo depende de las opciones de acción iniciales? ¿Cómo depende de estas variables la convención concreta a la que se llega? # Teoría General del Aprendizaje La teoría del aprendizaje en los juegos proporciona al diseñador de sistemas multiagente muchas herramientas útiles para determinar los posibles puntos de equilibrio de un sistema. Por desgracia, la mayoría de los sistemas multiagente con agentes que aprenden no convergen a un equilibrio. Los diseñadores suelen utilizar agentes que aprenden porque no conocen, en el momento del diseño, las circunstancias específicas a las que se enfrentarán los agentes en tiempo de ejecución. Si un diseñador conociera la mejor estrategia, es decir, la estrategia de equilibrio de Nash, para su agente, entonces simplemente implementaría esta estrategia y evitaría las complejidades de implementar un algoritmo de aprendizaje. Por lo tanto, veremos un sistema multiagente con agentes que aprenden cuando el diseñador no puede predecir que surgirá una solución de equilibrio. Como hemos visto, las dos razones principales de esta incapacidad para predecir la solución de equilibrio de un sistema son la existencia de cambios ambientales impredecibles que afectan a las compensaciones de los agentes y el hecho de que en muchos sistemas un agente sólo tiene acceso a su propio conjunto de recompensas, no conoce las de otros agentes. Estas dos razones hacen imposible que un diseñador pueda predecir a qué equilibrio, si es que hay alguno, convergerá el sistema. Sin embargo, los agentes del sistema siguen jugando un juego para el que existe un equilibrio, aunque el diseñador no pueda predecirlo en el momento del diseño. Sin embargo, dado que los beneficios reales cambian constantemente, los agentes cambian constantemente su estrategia para adaptarse a los nuevos beneficios. Los agentes que aprenden en un sistema multiagente se enfrentan a un problema de función de objetivo móvil. Es decir, a medida que los agentes cambian su comportamiento en un esfuerzo por maximizar su utilidad, sus recompensas por esas acciones cambian, modificando la utilidad esperada de su comportamiento. Es probable que el sistema tenga una dinámica no estacionaria, siempre cambiante para adaptarse al nuevo objetivo. Mientras que la teoría de juegos nos dice dónde están los puntos de equilibrio, supuesto que las recompensas permanecen fijas, los sistemas multiagente a menudo nunca llegan a esos puntos. Un diseñador de sistemas necesita saber cómo los cambios en el diseño del sistema y los algoritmos de aprendizaje afectarán al tiempo de convergencia. Este tipo de información puede determinarse utilizando la teoría CLRI. El **modelo CLRI** proporciona un método para analizar un sistema compuesto por agentes que aprenden y determinan cómo se espera que el aprendizaje de un agente afecte al aprendizaje de otros agentes del sistema. Supone un sistema en el que cada agente tiene una función de decisión que rige su comportamiento, así como una función objetivo que describe el mejor comportamiento posible del agente. La función objetivo es desconocida para el agente. El objetivo del aprendizaje del agente es que su función de decisión sea un duplicado exacto de su función objetivo. Por supuesto, la función objetivo sigue cambiando como resultado del aprendizaje de otros agentes. Formalmente, el modelo CLRI supone que hay un conjunto fijo de agentes autónomos en el sistema. El sistema puede describirse mediante un conjunto de estados discretos, $s \in S$, que se presentan al agente con una probabilidad dictada por la distribución de probabilidad fija, $D(S)$. Cada agente $i$ tiene un conjunto de acciones posibles, $A_i$, donde $|A_i| \geq 2$. El tiempo es discreto y está indexado por una variable $t$. En cada unidad de tiempo, $t$, se presenta a todos los agentes un nuevo $s \in D(S)$, toman una acción simultánea y reciben alguna recompensa. El escenario es similar al utilizado por el juego ficticio, excepto por la adición del estado $s$. El comportamiento de cada agente, $i$, está definido por una política, $\pi_i^t: S \to A$. Cuando $i$ se entera en el momento $t$ de que está en el estado $s$, tomará la acción $\pi_i^t(s)$. En cualquier momento existe una política óptima para cada agente $i$, también conocida como su **función objetivo**, que representamos como $\Pi_i^t(s)$. El algoritmo de aprendizaje del agente $i$ intentará reducir la discrepancia entre $\pi_i$ y $\Pi_i$ utilizando los pagos que recibe por cada acción como pistas para saber qué debe hacer, dado que no tiene acceso directo a $\Pi_i$. La probabilidad de que un agente tome una acción equivocada viene dada por su error $e(\pi_i^t) = Pr[\pi_i^t(s) \neq \Pi_i^t(s) | s \in D(S)]$. A medida que otros agentes aprenden y cambian su función de decisión, la función objetivo de $i$ también cambiará, lo que lleva al problema de la función objetivo móvil, como se representa en la siguiente figura:  El error de un agente se basa en una distribución de probabilidad fija sobre los estados del mundo y una correspondencia booleana entre las funciones de decisión y de objetivo. Estas limitaciones suelen ser demasiado restrictivas para modelar adecuadamente muchos sistemas multiagente. Sin embargo, incluso si el sistema que se modela no obedece completamente a estas dos restricciones, el uso del modelo CLRI en estos casos sigue proporcionando al diseñador una valiosa visión de cómo los cambios en el diseño afectarán a la dinámica del sistema. Esta práctica es similar al uso de $Q$-Learning en juegos no markovianos: aunque $Q$-Learning sólo garantiza la convergencia si el entorno es markoviano, puede funcionar bien en otros dominios. El modelo CLRI permite al diseñador comprender la dinámica esperada del sistema, independientemente del algoritmo de aprendizaje que se utilice, modelando el sistema mediante cuatro parámetros, CLRI: Tasa de cambio (*change*), Tasa de aprendizaje (*learning*), Tasa de retención (*retention*) e Impacto (*impact*). Un diseñador puede determinar los valores de estos parámetros y luego utilizar la ecuación en diferencias CLRI para determinar el comportamiento esperado del sistema. La tasa de cambio ($c$) es la probabilidad de que un agente cambie al menos uno de sus mapeos incorrectos en $\delta^t(w)$ por el nuevo $\delta^{t+1}(w)$. Captura la tasa a la que el algoritmo de aprendizaje del agente intenta cambiar sus mapeos erróneos. La tasa de aprendizaje ($l$) es la probabilidad de que el agente cambie un mapeo incorrecto por uno correcto. Es decir, la probabilidad de que $\delta^{t+1}(w) = \Delta^t(w)$, para todo $w$. Por definición, la tasa de aprendizaje debe ser menor o igual que la tasa de cambio, es decir, $l \leq c$. La tasa de retención ($r$) representa la probabilidad de que el agente conserve su mapeo correcto. Es decir, la probabilidad de que $\delta^{t+1}(w) = \delta^t(w)$ dado que $\delta^t(w) = \Delta^t(w)$. CLRI también define un término de volatilidad ($v$) como la probabilidad de que la función objetivo, $\Delta$, cambie del tiempo $t$ al $t + 1$. Es decir, la probabilidad de que $\Delta^t(w) \neq \Delta^{t+1}(w)$. Como cabría esperar, la volatilidad capta la cantidad de cambios a los que debe enfrentarse el agente. También puede verse como la velocidad de la función objetivo en el problema de la función objetivo móvil, con las tasas de aprendizaje y retención representando la velocidad de la función de decisión. Dado que la volatilidad es una propiedad dinámica del sistema (normalmente sólo puede calcularse ejecutando el sistema) CLRI proporciona una medida de impacto ($I_{ij}$), que representa el impacto que tiene el aprendizaje de $i$ en la función objetivo de $j$. En concreto, es la probabilidad de que $\Delta_j^t(w)$ cambie dado que $\delta_i^{t+1}(w) \neq \delta_i^t(w)$. Alguien que intente construir un sistema multiagente con agentes de aprendizaje determinaría los valores apropiados para $c$, $l$, $r$, y $v$ o $I$ y luego usaría: \begin{equation} E[e(\delta^{t+1}_i)] = 1 − r_i + v_i \left(\frac{|A_i|r_i − 1}{|A_i| − 1}\right) + e(\delta^t_i) \left( r_i − l_i + v_i \left(\frac{|A_i|(l_i − r_i) + l_i − c_i}{|A_i| − 1}\right)\right) \end{equation} para determinar los sucesivos errores esperados para un agente típico $i$. Esta ecuación se basa en una definición de volatilidad en términos de impacto dada por: \begin{equation} \forall w\in W,\ v^t_i = Pr[\Delta^{t+1}_i(w) \neq \Delta^t_i(w)] = 1 − \prod_{j\neq i} \left(1 − I_{ji}Pr[\delta^{t+1}_j(w) \neq \delta^t_j(w)]\right) \end{equation} que hace la suposición simplificadora de que los cambios en las funciones de decisión de los agentes no se cancelarán entre sí al calcular su impacto en otros agentes. La ecuación (1) no puede, en la mayoría de los casos, reducirse a una función de $t$, por lo que hay que iterar sobre ella. Por otro lado, un estudio cuidadoso de la función y del razonamiento que subyace a la elección de parámetros de CLRI lleva a una comprensión intuitiva de cómo los cambios en estos parámetros se reflejarán en la función y, por tanto, en el sistema. Un diseñador con conocimientos puede utilizar simplemente esta comprensión añadida para determinar el comportamiento esperado de su sistema bajo varios supuestos. Por ejemplo, es fácil ver que la tasa de aprendizaje de un agente y la volatilidad del sistema ayudan a determinar la rapidez con la que el agente alcanzará su función objetivo, si es que lo hace. Una tasa de aprendizaje elevada significa que un agente cambiará su función de decisión para que casi coincida con la función objetivo. Mientras tanto, una volatilidad baja significa que la función objetivo no se moverá mucho, por lo que será fácil para el agente igualarla. Así, si los agentes no tienen impacto entre sí, es decir, $I_{ij} = 0$ para todos los $i$, $j$, entonces los agentes aprenderán su función objetivo y el sistema convergerá. A medida que aumenta el impacto, es más probable que el sistema no converja nunca. Por supuesto, este tipo de análisis simple ignora una situación común en la que la alta tasa de aprendizaje del agente se une a un alto impacto en la función objetivo de otros agentes haciendo que su volatilidad sea mucho mayor. Estos agentes podrían entonces tener que aumentar su tasa de aprendizaje y, por tanto, aumentar la volatilidad del agente original. La ecuación (1) es muy útil en este tipo de situaciones de retroalimentación. # Referencias [#Axelrod]: Axelrod, R. (1984). The evolution of cooperation. New York: Basic Books. [#Blackwell]: Blackwell, D. (1956). Controlled random walks. Proceedings of the International Congress of Mathematicians (pp. 336–338). North-Holland. [#Brown]: Brown, G. (1951). Iterative solution of games by fictitious play. In Activity analysis of production and allocation. New York: John Wiley and Sons. [#Fudenberg]: Fudenberg, D. and Levine, D. K. (1998). The Theory of Learning in Games. MIT Press. [#Hannan]: Hannan, J. F. (1957). Approximation to Bayes risk in repeated plays. Contributions to the Theory of Games, 3, 97–139. [#Kaelbling]: Kaelbling, L. P., Littman, M. L., and Moore, A. P. (1996). Reinforcement learning: A survey. JAIR: Journal of Artificial Intelligence Research, 4, 237–285. [#Kalai]: Kalai, E., and Lehrer, E. (1993). Rational learning leads to Nash equilibrium. Econometrica, 61(5), 1019–1045. [#Littman]: Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. Proceedings of the 11th International Conference on Machine Learning (pp. 157–163). [#Maynard]: Maynard Smith, J., and Price, G. R. (1973). The logic of animal conflict. Nature, 246, 15–18. [#Powers]: Powers, R., and Shoham, Y. (2005). Learning against opponents with bounded memory. IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. [#Robinson]: Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54, 298–301. [#Taylor]: Taylor, P., and Jonker, L. B. (1978). Evolutionarily stable strategies and game dynamics. Mathematical Biosciences, 40, 145–156. [#Schuster]: Schuster, P., and Sigmund, K. (1982). Replicator dynamics. Theoretical Biology, 100, 533–538. [#Vidal]: Vidal, J. M. and Durfee, E. H. (2003). Predicting the expected behavior of agents that learn about agents: the CLRI framework. Autonomous Agents and MultiAgent Systems, 6(1):77–107. doi:10.1023/A:1021765422660. [#Vu]: Vu, T., Powers, R., and Shoham, Y. (2006). Learning against multiple opponents. AAMAS: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. [#Young]: Young, H. P. (2004). Strategic learning and its limits. Oxford University Press.