En el aprendizaje cooperativo por refuerzo multiagente (MARL), debido a su en política Por su naturaleza, generalmente se cree que los métodos de gradiente de políticas (PG) son menos eficientes que los métodos de descomposición de valores (VD), que son menos eficientes en la muestra. fuera de política. Sin embargo, algunos reciente empírico estudios demostrar que con una representación de entrada adecuada y un ajuste de hiperparámetros, el PG multiagente puede lograr rendimiento sorprendentemente fuerte en comparación con los métodos VD fuera de política.
¿Por qué los métodos PG podrían funcionar tan bien? En esta publicación, presentaremos un análisis concreto para mostrar que en ciertos escenarios, por ejemplo, entornos con un panorama de recompensas altamente multimodal, la VD puede ser problemática y conducir a resultados no deseados. Por el contrario, los métodos de GP con políticas individuales pueden converger hacia una política óptima en estos casos. Además, los métodos PG con políticas autorregresivas (AR) pueden aprender políticas multimodales.
Figura 1: representación de políticas diferentes para el juego de permutación de 4 jugadores.
CTDE en Cooperativa MARL: métodos VD y PG
Capacitación centralizada y ejecución descentralizada (CTDE) es un marco popular en la cooperativa MARL. Se aprovecha global información para una formación más eficaz manteniendo al mismo tiempo la representación de las políticas individuales para las pruebas. CTDE se puede implementar mediante descomposición de valores (VD) o gradiente de políticas (PG), lo que da lugar a dos tipos diferentes de algoritmos.
Los métodos VD aprenden redes Q locales y una función de mezcla que mezcla las redes Q locales en una función Q global. La función de mezcla generalmente se aplica para satisfacer el Individual-Global-Max (IGM), que garantiza la acción conjunta óptima, se puede calcular eligiendo con avidez la acción óptima localmente para cada agente.
Por el contrario, los métodos de PG aplican directamente un gradiente de políticas para aprender una política individual y una función de valor centralizada para cada agente. La función de valor toma como entrada el estado global (por ejemplo, MAPPO) o la concatenación de todas las observaciones locales (por ejemplo, MADDPG), para una estimación precisa del valor global.
El juego de permutación: un contraejemplo simple donde falla VD
Comenzamos nuestro análisis considerando un juego cooperativo sin estado, concretamente el juego de permutación. En un juego de permutación de $N$ jugadores, cada agente puede generar $N$ acciones ${ 1,\ldots, N }$. Los agentes reciben una recompensa de $+1$ si sus acciones son mutuamente diferentes, es decir, la acción conjunta es una permutación sobre $1, \ldots, N$; de lo contrario, reciben una recompensa de $0$. Tenga en cuenta que hay $N!$ estrategias óptimas simétricas en este juego.
Figura 2: el juego de permutación de 4 jugadores.
Figura 3: intuición de alto nivel sobre por qué falla VD en el juego de permutación de 2 jugadores.
Centrémonos ahora en el juego de permutación de 2 jugadores y apliquemos VD al juego. En esta configuración sin estado, usamos $Q_1$ y $Q_2$ para indicar las funciones Q locales, y usamos $Q_\textrm{tot}$ para indicar la función Q global. El principio IGM requiere que
\[\arg\max_{a^1,a^2}Q_\textrm{tot}(a^1,a^2)=\{\arg\max_{a^1}Q_1(a^1),\arg\max_{a^2}Q_2(a^2)\}.\]
Demostramos que VD no puede representar el resultado del juego de permutación de 2 jugadores por contradicción. Si los métodos VD pudieran representar el beneficio, tendríamos
\[Q_\textrm{tot}(1, 2)=Q_\textrm{tot}(2,1)=1\quad \text{and}\quad Q_\textrm{tot}(1, 1)=Q_\textrm{tot}(2,2)=0.\]
Si cualquiera de estos dos agentes tiene valores Q locales diferentes (por ejemplo, $Q_1(1)> Q_1(2)$), tenemos $\arg\max_{a^1}Q_1(a^1)=1$. Entonces, según el principio IGM, cualquier acción conjunta óptima
\[(a^{1\star},a^{2\star})=\arg\max_{a^1,a^2}Q_\textrm{tot}(a^1,a^2)=\{\arg\max_{a^1}Q_1(a^1),\arg\max_{a^2}Q_2(a^2)\}\]
satisface $a^{1\star}=1$ y $a^{1\star}\neq 2$, por lo que la acción conjunta $(a^1,a^2)=(2,1)$ es sub- óptimo, es decir, $Q_\textrm{tot}(2,1)<1$.
De lo contrario, si $Q_1(1)=Q_1(2)$ y $Q_2(1)=Q_2(2)$, entonces
\[Q_\textrm{tot}(1, 1)=Q_\textrm{tot}(2,2)=Q_\textrm{tot}(1, 2)=Q_\textrm{tot}(2,1).\]
Como resultado, la descomposición del valor no puede representar la matriz de pagos del juego de permutación de 2 jugadores.
¿Qué pasa con los métodos PG? De hecho, las políticas individuales pueden representar una política óptima para el juego de permutación. Además, el descenso de gradiente estocástico puede garantizar que PG converja a uno de estos óptimos. bajo suposiciones suaves. Esto sugiere que, aunque los métodos PG son menos populares en MARL en comparación con los métodos VD, pueden ser preferibles en ciertos casos que son comunes en aplicaciones del mundo real, por ejemplo, juegos con múltiples modalidades de estrategia.
También observamos que en el juego de permutación, para representar una política conjunta óptima, cada agente debe elegir acciones distintas. En consecuencia, una implementación exitosa de PG debe garantizar que las políticas sean específicas para cada agente. Esto se puede hacer utilizando políticas individuales con parámetros no compartidos (denominadas PG-Ind en nuestro documento) o una política condicionada por ID de agente (PG-ID).
PG supera a los métodos VD existentes en los populares bancos de pruebas MARL
Yendo más allá del simple ejemplo ilustrativo del juego de permutación, ampliamos nuestro estudio a puntos de referencia MARL populares y más realistas. Además del desafío multiagente de StarCraft (SMAC), donde la efectividad del GP y el aporte de políticas condicionadas por el agente Ha sido verificadomostramos nuevos resultados en Google Research Football (GRF) y multijugador Desafío Hanabi.
Figura 4: (izquierda) tasas de éxito de los métodos PG en GRF; (derecha) puntuaciones de evaluación mejor y promedio en Hanabi-Full.
En GRF, los métodos de PG superan a la línea base de VD de última generación (CDS) en 5 escenarios. Curiosamente, también notamos que las pólizas individuales (PG-Ind) sin compartir parámetros logran tasas de ganancia comparables, a veces incluso más altas, en comparación con las pólizas específicas de agente (PG-ID) en los 5 escenarios. Evaluamos PG-ID en el juego Hanabi a gran escala con diferentes números de jugadores (2-5 jugadores) y los comparamos con TRISTEuna fuerte variante de Q-learning fuera de la política en Hanabi, y Value Decomposition Networks (VDN). Como se demuestra en la tabla anterior, PG-ID puede producir resultados comparables o mejores que las mejores recompensas promedio logradas por SAD y VDN con diferentes números de jugadores que utilizan el mismo número de pasos del entorno.
Más allá de mayores recompensas: aprender comportamientos multimodales mediante modelos de políticas autorregresivos
Además de aprender recompensas más altas, también estudiamos cómo aprender políticas multimodales en MARL cooperativo. Volvamos al juego de permutación. Aunque hemos demostrado que PG puede aprender efectivamente una política óptima, el modo de estrategia que finalmente alcance puede depender en gran medida de la inicialización de la política. Así, una pregunta natural será:
¿Podemos aprender una única política que pueda cubrir todos los modos óptimos?
En la formulación descentralizada de GP, la representación factorizada de una política conjunta sólo puede representar un modo particular. Por lo tanto, proponemos una forma mejorada de parametrizar las políticas para lograr una mayor expresividad: las políticas autorregresivas (AR).
Figura 5: comparación entre políticas individuales (PG) y políticas autorregresivas (AR) en el juego de permutación de 4 jugadores.
Formalmente, factorizamos la política conjunta de $n$ agentes en la forma de
\[\pi(\mathbf{a} \mid \mathbf{o}) \approx \prod_{i=1}^n \pi_{\theta^{i}} \left( a^{i}\mid o^{i},a^{1},\ldots,a^{i-1} \right),\]
donde la acción producida por el agente $i$ depende de su propia observación $o_i$ y de todas las acciones de los agentes anteriores $1,\dots,i-1$. La factorización autorregresiva puede representar cualquier política conjunta en un MDP centralizado. El solo la modificación de la política de cada agente es la dimensión de entrada, que se amplía ligeramente al incluir acciones anteriores; y la dimensión de producción de la política de cada agente permanece sin cambios.
Con una sobrecarga de parametrización tan mínima, la política AR mejora sustancialmente el poder de representación de los métodos PG. Observamos que PG con política AR (PG-AR) puede representar simultáneamente todos los modos de política óptimos en el juego de permutación.
Figura: los mapas de calor de acciones para políticas aprendidas por PG-Ind (izquierda) y PG-AR (centro), y el mapa de calor de recompensas (derecha); mientras que PG-Ind solo converge a un modo específico en el juego de permutación de 4 jugadores, PG-AR descubre con éxito todos los modos óptimos.
En entornos más complejos, incluidos SMAC y GRF, PG-AR puede aprender comportamientos emergentes interesantes que requieren una fuerte coordinación intraagente que PG-Ind nunca aprenderá.
Figura 6: (izquierda) comportamiento emergente inducido por PG-AR en SMAC y GRF. En el mapa 2m_vs_1z de SMAC, los marines permanecen de pie y atacan alternativamente mientras se aseguran de que solo haya un marine atacante en cada paso de tiempo; (derecha) en el escenario academy_3_vs_1_with_keeper de GRF, los agentes aprenden un comportamiento de estilo “Tiki-Taka”: cada jugador sigue pasando el balón a sus compañeros de equipo.
Discusiones y conclusiones
En esta publicación, proporcionamos un análisis concreto de los métodos VD y PG en MARL cooperativo. Primero, revelamos la limitación en la expresividad de los métodos populares de VD, mostrando que no podrían representar políticas óptimas ni siquiera en un simple juego de permutación. Por el contrario, mostramos que los métodos PG son probablemente más expresivos. Verificamos empíricamente la ventaja de expresividad de PG en bancos de pruebas MARL populares, incluidos SMAC, GRF y Hanabi Challenge. Esperamos que los conocimientos de este trabajo puedan beneficiar a la comunidad hacia algoritmos MARL cooperativos más generales y más potentes en el futuro.
Esta publicación se basa en nuestro artículo: Revisando algunas prácticas comunes en el aprendizaje cooperativo por refuerzo de múltiples agentes (papel, sitio web).