Notas sobre aprendizaje por refuerzo (XIII): sistemas multi-agente

Casi todo lo que he comentado en esta larga serie de artículos dedicados al aprendizaje por refuerzo ('reinforcement learning'), se refería a problemas o situaciones en que nos centrábamos en un único agente, del cual queríamos maximizar su política.

En el último post, introdujimos ya el caso de dos agentes.

En este artículo damos un paso más para abordar los escenarios o sistemas multi-agente.

Como en toda esta serie, me guiaré por las enseñanzas recogidas en el libro 'Deep reinforcement learning' de Aske Plaat y, como anuncié en el post anterior, en los últimos artículos de esta serie profundizaré poco en los algoritmos propiamente dichos, delineando sólo las ideas principales.

Vamos, allá, pues, con los sistemas multi-agente.

Recordatorio: lo que hemos visto de aprendizaje por refuerzo

Pero antes, y como en toda esta serie, recordemos brevemente lo que hemos visto hasta ahora.

Mientras nos mantuvimos, en los primeros posts, en el caso de sistemas mono-agente, nos ocupábamos de la situación de un agente que interactúa con un entorno que se encuentra en un estado s. Sobre ese entorno, el agente aplica unas acciones, a, como consecuencia de las cuales, el entorno puede experimentar una transición y cambiar de estado, pasando del estado s al s', y el agente recibe una recompensa r. El agente decide la acción a aplicar en cada momento, siguiendo una política π y su objetivo es maximizar la recompensa obtenida lo largo de una secuencia o trayectoria.

Los métodos más básicos, aquellos en que el espacio de estado es reducido, siguen un enfoque tabular, en que se tabulan, de ahí el nombre, los posibles estados y para ellos se calculan unas funciones que nos dan el valor, Q, de la recompensa esperada. Cuando la dimensión del espacio de estados es muy alta, como sucede habitualmente en problemas reales, dejan de tener sentido estos métodos tabulares así que renunciamos a representar la situación del entorno mediante su estado, y a cambio lo representamos mediante unas características ('features') y la obtención de valores o acciones vienen a ser unas funciones con base en esas características e implementadas mediante redes neuronales profundas, dando lugar al 'deep reinforcement learning'.

Cuando tratamos problemas ya no de alta dimensionalidad, sino continuos, como es la locomoción de robots, se adoptan los denominados métodos basados en políticas en que se prescinde de la visión de valores, y se trabaja directamente en optimizar las políticas, que pasan a considerarse como estocásticas, es decir, como distribuciones de probabilidad. 

También aparecía como opción el denominado aprendizaje basado en modelos ('model-based'), en que el agente primero consigue un modelo del entorno y luego ya prescinde del entorno propiamente dicho par a trabajar con ese modelo local durante todo el entrenamiento.

Y, en el último post, ya introdujimos brevemente las situaciones en que tenemos dos agentes, exactamente dos. Dos agentes que se encontraban en una situación competitiva, en uno de los denominados juegos de suma cero en que la ganancia de un agente supone la perdida del otro. En esa situación, una opción habitual es trabajar con el aprendizaje basado en modelos, dado que, para un agente, el entorno está constituido por el otro agente, y se adopta la hipótesis razonable de que su política, la del otro agente, es igual a la nuestra, por lo que modelamos el entorno con el modelo de nuestra propia política. 

Eso, además, conduce a la posibilidad del autoaprendizaje o auto-juego ('self-play'), en que un agente aprende jugando, en el fondo, contra sí mismo (contra otro agente con la misma política, en realidad).

Mediante los problemas mono-agente, se pueden tratar problemas como la locomoción de robots, la búsqueda de rutas o videojuegos. Y mediante los problemas de dos agentes, se ha conseguido tratar casos de juegos de mesa, por ejemplo. 

Sistemas multi-agente

Pues bien, ahora damos un nuevo salto de complejidad, abordando los escenarios o sistemas multi-agente, es decir, ya no nos limitamos a uno o dos agentes, sino que el número es mayor e indefinido.

Siendo un poquito formales, los problemas o sistemas multi-agente se podrían definir como problemas de decisión secuencial de múltiples agente autónomos que operan en un entorno estocástico compartido y donde cada uno de los agentes busca optimizar su recompensa a largo plazo mediante la interacción con el entorno y con los otros agentes.

El entrar en sistemas multi-agente, nos introduce además la idea de la colaboración entre agentes. En los casos mono-agente, no tiene sentido ni siquiera plantearlo y, en el caso de dos agentes, el foco ha estado en la competencia entre ellos, en los juegos de suma cero.

Sin embargo en los sistemas multi-agente una situación habitual es que los agentes colaboren para conseguir un objetivo común. Pero tampoco es extraño que los agentes compitan entre sí. Es decir, en los sistemas multi-agente, en general tenemos que contemplar tanto la competición como la colaboración.

Por eso, a la hora de trabajar con ellos, se suele dividir los problemas multi-agente en tres situaciones:

• Comportamiento competitivo
• Comportamiento cooperativo
• Comportamiento mixto

Algunos retos de los sistemas multi-agente

Los sistemas multi-agente se enfrentan a varios retos. En concreto, en la obra citada, Plaat se concentra en tres:

• Observabilidad parcial
• Entornos no estacionarios
• Espacios de estado grandes

El problema de la observabilidad parcial hace referencia que se trata de problemas en que no podemos suponer que el agente disponga de información perfecta sino que, bien al contrario, ésta es incompleta e imperfecta. Así, por ejemplo, un agente puede trabajar con información privada que no pone a disposición del resto de agentes, como se podría ejemplificar con las cartas propias de los jugadores de póker. Esto nos lleva a tener que considerar todos los posibles 'estados del mundo' lo que incrementa enormemente el número de variantes a considerar.

El problema de los entornos no estacionarios se refiere al hecho de que el entorno no permanece estable, dado que los agentes (que, en el fondo, forman parte del entorno para un agente dado) van mejorando sus propias políticas y, por tanto, el entorno para un agente dado, se modifica de manera continuada. De alguna forma, todos los agentes están aprendiendo de manera concurrente. El encontrarnos ante entornos no estacionarios hace que los agentes deban de tener en cuenta una suerte de espacio de acciones conjunto que, no sólo tenga en cuenta sus propias acciones, sino también las del resto de agentes. Esto, de nuevo, incrementa muchísimo, de manera exponencial, el espacio de acciones a considerar.

El tercer reto, espacio de estado grandes deriva, y en el fondo ya lo hemos mencionado, de que la presencia de múltiples agentes aumenta el espacio de acciones de manera exponencial con el número de agentes. De momento, la única forma de acometer estos grandes espacios de acciones es aplicando hipótesis simplificadoras pero realistas.

Aproximaciones

Plaat reconoce que este tipo de problemas no están realmente resueltos de manera general y que se encuentran fundamentalmente en investigación, pero menciona y describe algunos algoritmos o situaciones útiles como el CFR ('Counter Factual Regret minimization'), y su generalización a deep learning: Deep Counter Factual Regret Minimization con resultados interesantes para entornos competitivos.

También se explica la opción de, pese a estar hablando de agentes autónomos, centralizar el aprendizaje lo que, en el fondo, lo hace equivalente a un problema de un solo agente.

E igualmente explica estrategias en que se intenta reducir la complejidad, modelando el comportamiento del oponente basándose para ello en la teoría de la mente procedente del campo de la psicología.

Existen, asimismo, los algoritmos evolutivos (creo que otro nombre para o una derivada de los algoritmos genéticos) que se basan en los mecanismos propios de la biogenética: mutación, recombinación, y selección.

Finalmente, menciona los enfoques propios del 'swarm computing' (computación de enjambre) que se centra en los comportamientos emergentes que surgen en sistemas colectivos, descentralizados y auto-organizados.

No profundizaré más en los algoritmos aunque, especialmente el 'swarm computing' es muy de mi interés, y seguramente vuelva a él en otro momento ya fuera del ámbito del aprendizaje por refuerzo y pensando más en robótica..

Conclusiones

Un nuevo paso en el aprendizaje por refuerzo es el salto a los sistemas multi-agente donde, aparte de un entorno común, tenemos varios agentes autónomos, cada uno de los cuales desea optimizar su recompensa a largo plazo, y que interactúan entre si exhibiendo comportamientos tanto competitivos, como colaborativos o mixtos.

Aunque hay avances, se trata de un campo fundamentalmente en investigación.

Artículos de este blog relacionados

• Notas sobre aprendizaje por refuerzo (XII): autoaprendizaje y el caso de AlphaGo y AlphaZero
• Notas sobre aprendizaje por refuerzo (XI): métodos basados en modelo
• Notas sobre aprendizaje por refuerzo (X): locomoción de robots
• Notas sobre aprendizaje por refuerzo (IX): aprendizaje de políticas y el ascenso de gradiente
• Notas sobre aprendizaje por refuerzo (VIII): problemas continuos y métodos basados en políticas
• Notas sobre aprendizaje por refuerzo (VII): El triunfo del algoritmo DQN (Deep Q-Network)
• Notas sobre el aprendizaje por refuerzo (VI): los tres retos del deep reinforcement learning
• Notas sobre el aprendizaje por refuerzo (V): deep reinforcement learning
• Notas sobre aprendizaje por refuerzo (IV): Métodos tabulares. SARSA Y Q-Learning
• Notas sobre aprendizaje por refuerzo (III): recompensas, trazas y valores
• Notas sobre aprendizaje por refuerzo (II): Visualizando el aprendizaje en procesos de Markov
• Notas sobre aprendizaje por refuerzo (I): Procesos de decisión de Markov