CAPO: Counterfactual Credit Assignment in Sequential Cooperative Teams

1. El Problema: Asignación de Crédito en Equipos Cooperativos Secuenciales

El trabajo aborda un desafío fundamental en los sistemas multiagente cooperativos donde los agentes actúan en un orden fijo y comparten una única recompensa de equipo.

• Dificultad de Asignación de Crédito: Cuando el equipo recibe una sola señal de recompensa, es difícil determinar cuánto contribuyó cada agente individual.
• El Reto de la No Estacionariedad: La situación se complica cuando los agentes se actualizan uno a la vez dentro de un mismo lote de entrenamiento (actualización secuencial). Al actualizar un agente "aguas arriba" (anterior), se cambia la distribución de probabilidad de las acciones de los agentes "aguas abajo" (posteriores). Esto hace que los datos recolectados bajo la política antigua (pre-actualización) sean off-policy para los agentes que aún no se han actualizado en ese mismo lote, introduciendo un sesgo de no estacionariedad.
• Limitaciones de los Métodos Actuales:
  • Críticos Centralizados: Su espacio de entrada crece exponencialmente con el tamaño del equipo.
  • Muestreo de Importancia (IS) Acumulado: Métodos como HAPPO o HA-GRPO utilizan correcciones de IS que tienen una varianza que crece exponencialmente con el número de agentes ya actualizados.
  • Replay de Entorno: Métodos como C3 requieren re-ejecutar el entorno para cada contrafactual, lo cual es costoso computacionalmente si la evaluación de la recompensa es cara (ej. ejecutores de código, evaluadores humanos).

2. Metodología: CAPO (Counterfactual Advantage Policy Optimization)

Los autores proponen CAPO, un algoritmo de optimización de políticas basado en gradientes que no requiere un crítico (critic-free) y está diseñado específicamente para entornos secuenciales.

A. Utilidad Aristócrata Secuencial (SeqAU)

Extienden el marco de "opacidad-aprendizaje" de Wolpert y Tumer (2002) al caso secuencial.

• Definen la Utilidad Aristócrata Secuencial (SeqAU) como la señal de aprendizaje única por agente que maximiza la "aprendibilidad" individual.
• Demuestran teóricamente (Teorema 1) que la base óptima para restar a la recompensa del equipo es la esperanza de la recompensa condicionada únicamente al prefijo de acciones anteriores ($E[R | a_{<k}]$).
• Esto genera una ventaja contrafactual: $A_k = E[R | a_{\le k}] - E[R | a_{<k}]$.

B. Tres Componentes Clave del Algoritmo

Para estimar esta ventaja de manera eficiente y sin críticos, CAPO combina tres técnicas:

1. Descomposición Aditiva de la Recompensa:

   • Modelan la recompensa esperada como una suma de contribuciones individuales: $f(a) = \sum \phi_k(a_k)$.
   • En lugar de aprender un crítico complejo, ajustan un estimador de regresión ridge (mínimos cuadrados) para encontrar los componentes $\phi_k$ a partir de los datos del lote. Esto permite una atribución de recompensa en forma cerrada.

2. Identidad de Cancelación Aguas Arriba (Upstream Cancellation):

   • Al aplicar la descomposición aditiva a la ventaja contrafactual, las contribuciones de los agentes anteriores al agente actual ($j < k$) aparecen idénticas en ambos términos de la resta y se cancelan exactamente.
   • Esto reduce la ventaja a dos partes manejables:
     • Efecto Directo ($D_k$): Depende solo de la acción del agente actual y su propia contribución estimada. Se calcula en forma cerrada.
     • Efecto Indirecto ($I_k$): Captura cómo la acción del agente $k$ cambia la distribución de acciones de los agentes posteriores ($j > k$) y, por ende, sus contribuciones a la recompensa.

3. Muestreo Ficticio (Fictitious Sampling):

   • Para estimar el Efecto Indirecto sin re-ejecutar el entorno ni usar IS (que tiene alta varianza), CAPO utiliza muestreo ficticio.
   • Para cada trayectoria real recolectada, el algoritmo genera continuaciones "ficticias" de los agentes posteriores utilizando la política actual (no la política de recolección).
   • Esto permite estimar la expectativa de la recompensa bajo la nueva política sin coste de interacción con el entorno ni inflación de varianza por IS.

3. Contribuciones Clave

1. SeqAU (Teorema 1): Identificación de la base única dependiente del prefijo que maximiza la aprendibilidad en equipos cooperativos secuenciales, generalizando el trabajo de Wolpert y Tumer.
2. Algoritmo CAPO: Un método de gradiente de política sin crítico que utiliza descomposición aditiva, cancelación aguas arriba y muestreo ficticio para estimar ventajas contrafactuales.
3. Análisis Teórico Riguroso (Teoremas 2-4):
   • Sesgo: El sesgo es lineal con respecto al residuo de no aditividad de la recompensa.
   • Varianza: La varianza se adapta a la estructura de acoplamiento. En el límite de políticas factorizadas, es independiente del tamaño del equipo ($K$). En el peor caso, escala como $O(K-k)$, mucho mejor que la escala exponencial de los métodos basados en IS (HA-GRPO) o la escala lineal inherente de los métodos de línea base compartida (MA-GRPO).
   • Error Cuadrático Medio (MSE) del Gradiente: No sufre de inflación por la razón de muestreo de importancia.
4. Validación Empírica: Demostración en un entorno de banda contextual secuencial controlado donde CAPO supera a los baselines (MA-GRPO, HA-GRPO, C3) a medida que aumenta el tamaño del equipo.

4. Resultados Experimentales

Los experimentos se realizaron en un entorno de banda contextual secuencial con recompensas controladas:

• Calidad de Estimación (MSE de la Ventaja):

  • CAPO: El error cuadrático medio (MSE) permanece prácticamente constante a medida que aumenta el número de agentes ($K$), confirmando la teoría de independencia de $K$ en el efecto directo.
  • MA-GRPO: El MSE crece linealmente con $K$ (debido a la varianza inherente de la recompensa compartida).
  • HA-GRPO: El MSE crece más rápido que linealmente debido a la acumulación de varianza en el prefijo de IS.
  • C3: Sigue una forma similar a CAPO pero con un offset constante debido a la varianza de filtrado de prefijos.
  • Hallazgo: En $K=16$, CAPO tiene un MSE ~2x menor que C3, ~30x menor que MA-GRPO y ~46x menor que HA-GRPO.

• Optimización de Políticas (Regret):

  • En equipos pequeños ($K=2$), métodos simples como MA-GRPO son suficientes.
  • A partir de $K=4$, CAPO supera consistentemente a todos los baselines. La ventaja de CAPO sobre MA-GRPO se amplía a medida que crece el equipo.
  • HA-GRPO degrada rápidamente su rendimiento a medida que aumenta $K$ debido a la varianza exponencial del IS.
  • C3 tiene un rendimiento inferior debido a su alto costo computacional por iteración (replay de entorno), lo que limita el número de actualizaciones posibles con el mismo presupuesto de interacción.

• Ablación (Efecto Indirecto):

  • Se comparó CAPO con una versión que solo usa el efecto directo (CAPO-Direct).
  • Cuando la no estacionariedad es baja ($\rho=0$), ambas versiones son similares.
  • A medida que aumenta la no estacionariedad ($\rho \ge 10$), CAPO supera significativamente a CAPO-Direct, demostrando que el efecto indirecto (corregido mediante muestreo ficticio) es esencial para el aprendizaje en entornos secuenciales no estacionarios.

5. Significado e Impacto

• Solución Escalable: CAPO ofrece una solución escalable para la asignación de crédito en equipos grandes, evitando la explosión exponencial de varianza de los métodos de IS y el coste de entrenamiento de críticos centralizados.
• Eficiencia Computacional: Al evitar la re-ejecución del entorno (a diferencia de C3) y el uso de críticos aprendidos, CAPO es particularmente adecuado para pipelines donde la evaluación de la recompensa es costosa (ej. verificación de código, evaluadores humanos, LLMs).
• Aplicabilidad en LLMs: El marco es general y se identifica como un objetivo natural de despliegue para pipelines de múltiples LLMs, donde los agentes (modelos) actúan secuencialmente y comparten una recompensa de tarea global.
• Fundamento Teórico: Proporciona los primeros límites analíticos cerrados de sesgo y varianza para ventajas por agente en métodos de descomposición en el contexto multiagente, llenando una brecha teórica importante.

En resumen, CAPO introduce un nuevo paradigma para el aprendizaje cooperativo secuencial, combinando teoría de utilidad óptima con estimación práctica eficiente, logrando un rendimiento superior a medida que aumenta la complejidad y el tamaño del equipo.