Resumen Técnico: Aprendizaje por Refuerzo Multi-Agente Cooperativo Condicionado por Autómatas (ACC-MARL)

1. Planteamiento del Problema

El artículo aborda el desafío de aprender políticas multi-tarea y multi-agente para equipos cooperativos que operan bajo un esquema de entrenamiento centralizado y ejecución descentralizada (CTDE). El escenario específico involucra agentes a los que se les asignan tareas temporales desconocidas a priori en tiempo de ejecución, las cuales deben completar sin comunicación explícita.

La dificultad central radica en generalizar a estas tareas dinámicas mientras se satisfacen objetivos complejos de largo horizonte. Los enfoques existentes que utilizan especificaciones formales (como los Autómatas de Estados Finitos Deterministas, DFA) para representar tareas suelen ser ineficientes en términos de muestras y están limitados a escenarios de una sola tarea, requiriendo el reentrenamiento para nuevos objetivos. Además, en un contexto multi-agente, tres desafíos primarios dificultan su viabilidad:

1. Dependencia de la Historia: Las políticas deben rastrear el progreso de la tarea (historia) para tomar decisiones, lo que rompe la propiedad de Markov y conduce a políticas subóptimas.
2. Asignación de Crédito: La recompensa a nivel de equipo es dispersa (solo se otorga tras la finalización total de la tarea), lo que dificulta que los agentes distingan cómo las acciones individuales contribren al objetivo global.
3. Cuello de Botella de Representación: Aprender simultáneamente representaciones latentes de los DFA y las políticas de control crea un problema de escalabilidad, particularmente para equipos de más de dos agentes.

2. Metodología: Marco de Trabajo ACC-MARL

Los autores proponen el Aprendizaje por Refuerzo Multi-Agente Cooperativo Condicionado por Autómatas (ACC-MARL), un marco que condiciona las políticas descentralizadas en representaciones de tareas derivadas de los DFA. El enfoque aborda los tres desafíos mediante los siguientes mecanismos:

A. Mitigación de la Dependencia de la Historia mediante la Reformulación Markoviana

En lugar de condicionar las políticas a la historia bruta de observaciones, el marco aumenta el espacio de estados con el estado actual del DFA mínimo para cada agente.

• Mecanismo: En cada paso, el estado del entorno es etiquetado y los DFA asignados progresan (se actualizan) basándose en estas etiquetas. Las observaciones de los agentes se aumentan con las últimas representaciones mínimas de los DFA.
• Resultado: Esto transforma el juego no-Markoviano en un juego Markoviano sobre el espacio producto de los estados del entorno y los estados de los DFA ($S \times D^n$). Los autores demuestran (Teorema 3.1) que maximizar el retorno en este juego Markoviano reformulado es equivalente a maximizar la probabilidad de satisfacer los objetivos temporales originales a medida que el factor de descuento $\gamma \to 1$.

B. Abordaje de la Asignación de Crédito mediante el Modelado de Recompensa Basado en Potencial (PBRS)

Para superar las recompensas dispersas, los autores aplican Modelado de Recompensa Basado en Potencial (PBRS).

• Mecanismo: Se define una función de potencial $\Phi_i$ para cada agente $i$, que devuelve 1 si su DFA asignado se ha cumplido y 0 en caso contrario. La recompensa se moldea mediante la diferencia en el potencial entre el estado actual y el siguiente: $R_{PBRS} = R_{base} + \gamma \Phi_i(siguiente) - \Phi_i(actual)$.
• Resultado: Los agentes reciben retroalimentación positiva densa por completar sus sub-tareas específicas, manteniendo la garantía teórica de que la política óptima para la recompensa modelada sigue siendo óptima para el objetivo original.

C. Resolución del Cuello de Botella de Representación con Embeddings RAD

Para evitar aprender representaciones latentes de los DFA desde cero durante el entrenamiento (lo que causa una degradación del rendimiento en equipos más grandes), el marco utiliza Embeddings RAD (ReachAvoidDerived) preentrenados.

• MMechanismo: Un codificador de Red de Atención de Grafos (GATv2) congelado mapea los DFA a vectores latentes (Embeddings RAD). Estos embeddings están entrenados para representar de forma única distintos DFA minimizados y codificar similitudes semánticas a través de una amplia clase de tareas temporales.
• Resultado: Las políticas se condicionan a estos embeddings fijos en lugar de a los DFA brutos o representaciones aprendidas. Esto desacopla el aprendizaje de la representación del aprendizaje del control, permitiendo escalar eficientemente a equipos más grandes (por ejemplo, 4 agentes).

D. Asignación Óptima de Tareas

El marco aprovecha las funciones de valor aprendidas para asignar tareas de manera óptima en tiempo de prueba. Al evaluar el desempeño esperado del equipo (suma de las funciones de valor) para diferentes permutaciones de asignación de tareas, el sistema puede seleccionar una asignación Pareto-óptima que maximice el éxito general del equipo, particularmente en entornos asimétricos.

3. Contribuciones Clave

1. Introducción del Marco: La propuesta de ACC-MARL, un marco para aprender políticas multi-tarea, multi-agente y egocéntricas condicionadas por DFA.
2. Garantías Teóricas: Demostración de que la reformulación Markoviana y el modelado de recompensa propuestos preservan la optimalidad con respecto al problema no-Markoviano original.
3. Solución de Escalabilidad: Demostración de que el uso de Embeddings RAD preentrenados supera el cuello de botella de representación, permitiendo el aprendizaje efectivo en equipos de más de dos agentes.
4. Asignación de Tareas: Un método para utilizar las funciones de valor aprendidas para computar asignaciones de tareas óptimas en tiempo de prueba.
5. Herramienta (Toolchain): Implementación de una cadena de herramientas basada en JAX (DFAx) para operaciones de DFA paralelizadas y un paquete de Python para integrar tareas de autómatas en aplicaciones de RL.

4. Resultados Experimentales

El marco fue evaluado en un entorno discreto y totalmente observable llamado TokenEnv, que presenta variantes de dos y cuatro agentes con diseños que incluyen botones, puertas y tokens.

• Factibilidad y Escalabilidad (Q1 y Q2):
  • Los estudios de ablación muestran que sin las soluciones propuestas (específicamente PBRS y Embeddings RAD), las políticas fallan en converger o alcanzan tasas de éxito bajas (<0.5).
  • En entornos de 2 agentes, tanto los codificadores preentrenados como los no entrenados se comportan de manera similar, aunque los embeddings preentrenados ofrecen una menor varianza.
  • En entornos de 4 agentes, las políticas que utilizan Embeddings RAD preentrenados superan significativamente a aquellas que aprenden representaciones desde cero, confirmando que el preentrenamiento es crucial para la escalabilidad.
• Generalización (Q3):
  • Las políticas entrenadas con RAD DFAs se generalizan a clases de tareas no vistas (Reach y ReachAvoid) y a DFAs fuera de la distribución (OOD) con más estados de los vistos durante el entrenamiento.
  • Los embeddings preentrenados mejoran específicamente el rendimiento en tareas que involucran restricciones de "Evitar" (condiciones irrecuperables).
• Asignación de Tareas (Q4):
  • En entornos simétricos (Buttons), el orden de la asignación de tareas tuvo un impacto insignificante.
  • En entornos asimétricos (Rooms), la asignación óptima de tareas derivada de las funciones de valor aprendidas mejoró significativamente las probabilidades de éxito del equipo en comparación con la asignación aleatoria.
• Comportamientos Emergentes (Q5):
  • El análisis cualitativo revela habilidades cooperativas emergentes, como agentes sosteniendo puertas para sus compañeros para ahorrar tiempo y "atajos" en las tareas (por ejemplo, un agente desbloqueando una puerta para permitir que otro tome un camino más corto).

5. Significación y Reivindicaciones

El artículo afirma ser el primer trabajo en utilizar especificaciones formales (DFA) en un entorno de MARL multi-tarea cooperativo donde las tareas se asignan en tiempo de ejecución. Su importancia radica en:

• Puente entre Métodos Formales y MARL: Extiende el RL condicionado por autómatas de un solo agente a entornos multi-agente, permitiendo la descomposición de objetivos de equipo complejos en sub-tareas.
• Resolución del Desafío de Escalabilidad: Al desacoplar el aprendizaje de la representación mediante embeddings preentrenados, aborda los cuellos de botella de rendimiento que anteriormente limitaban el MARL condicionado por autómatas a equipos pequeños.
• Optimalidad: Proporciona un enfoque teóricamente fundamentado que garantiza un comportamiento de equipo óptimo al tiempo que permite una asignación de crédito y generalización eficientes.

Los autores señalan limitaciones, incluyendo la suposición de funciones de etiquetado fijas, observabilidad completa y el costo computacional de enumerar las asignaciones de tareas para equipos muy grandes. Sugieren como trabajo futuro la observabilidad parcial, el etiquetado dinámico y los dominios continuos.