Resumen Técnico: Oráculos de Respuesta del Espacio de Políticas con Eficiencia de Muestreo mediante la Mejor Respuesta de Experiencia Conjunta

1. Planteamiento del Problema

El aprendizaje por refuerzo multiagente (MARL) ofrece una alternativa escalable al análisis exacto de la teoría de juegos, pero enfrenta dos desafíos principales: la no estacionariedad (donde el aprendizaje independiente causa que el entorno cambie a medida que los agentes se actualizan) y la necesidad de mantener poblaciones de estrategias diversas para capturar interacciones no transitivas. El marco de trabajo de los Oráculos de Respuesta del Espacio de Políticas (PSRO) aborda esto expandiendo iterativamente un juego restringido con mejores respuestas (BRs) aproximadas.

Sin embargo, el PSRO estándar sufre de costos computacionales y de muestreo prohibitivos. En cada iteración, cada agente debe calcular independientemente una mejor respuesta contra el perfil de la meta-estrategia actual de los otros agentes. Esto requiere resolver tantos problemas de aprendizaje por refuerzo (RL) como agentes haya, y cada uno requiere la simulación completa de los agentes restantes. En dominios con muchos jugadores o simuladores costosos, esta estructura de entrenamiento por agente hace que el PSRO sea impracticable.

2. Metodología

Concepto Central: Mejor Respuesta de Experiencia Conjunta (JBR)

Los autores proponen la Mejor Respuesta de Experiencia Conjunta (JBR), una modificación de PSRO que reutiliza los datos de interacción entre todos los agentes. En lugar de entrenar la mejor respuesta de cada agente de forma independiente, JBR:

1. Recolecta trayectorias una sola vez bajo el perfil de la meta-estrategia actual $\sigma = (\sigma_j)_{j \in N}$.
2. Construye un conjunto de datos conjunto compartido $\mathcal{D}_\sigma$ que contiene transiciones $(s_t, a_{1,t}, \dots, a_{n,t}, r_{1,t}, \dots, r_{n,t}, s_{t+1})$.
3. Calcula las mejores respuestas para todos los agentes simultáneamente a partir de este único conjunto de datos.

Esto convierte la computación de la mejor respuesta de un problema de RL en línea a un problema de RL fuera de línea (offline), donde las políticas se optimizan a partir de un conjunto de datos fijo. Si bien esto mejora drásticamente la eficiencia de muestreo, introduce un sesgo de desplazamiento de distribución porque el conjunto de datos se genera bajo la meta-estrategia actual, la cual puede no cubrir las regiones de estado-acción relevantes para la verdadera mejor respuesta.

Abordando el Sesgo de RL Fuera de Línea

Para mitigar las limitaciones del RL fuera de línea (específicamente el desplazamiento de distribución), el artículo introduce tres remedios complementarios:

1. JBR Conservador (Mejora Segura de la Política):

   • Impone una restricción donde la política aprendida $\pi_i$ solo se desvía de la meta-estrategia base $\sigma_i$ en pares de estado-acción suficientemente cubiertos por el conjunto de datos (conteo $N_D(s, a_i) \ge N^\wedge$).
   • En regiones submuestreadas, la política revierte a $\sigma_i$, garantizando que el rendimiento no decaiga por debajo de la base.
   • Limitación: Aunque es seguro, es excesivamente cauteloso y limita la capacidad de encontrar mejoras significativas en comparación con las BRs independientes.

2. JBR con Aumento de Exploración:

   • Perturba el proceso de recolección de datos para mejorar la cobertura. En lugar de actuar estrictamente según $\sigma$, los agentes siguen una meta-estrategia $\delta$-perturbada:
     $$\tilde{\sigma}_j(a_j|s) = (1-\delta)\sigma_j(a_j|s) + \delta\nu_j(a_j|s)$$
   • Se proponen dos estrategias de exploración:
     • $\delta$-Aleatoria ($\delta$-R): $\nu_j$ es una política aleatoria uniforme.
     • $\delta$-Dirigida ($\delta$-T): $\nu_j$ es la candidata actual a mejor respuesta ($\pi^{BR,cur}_j$). Esto dirige la exploración hacia trayectorias prometedoras, actuando efectivamente como una forma de modelado del oponente.
   • Garantía Teórica: El artículo demuestra que para juegos de suma cero de dos jugadores finitos, si los agentes computan una $\epsilon$-mejor respuesta a la estrategia perturbada $\tilde{\sigma}$, la meta-estrategia resultante es un equilibrio de Nash $(\epsilon + 2R\delta)$ del juego original (donde $R$ es el rango de la recompensa).

3. Mejor Respuesta Híbrida (HBR):

   • Alterna entre JBR y una BR Independiente estándar (IBR).
   • En la mayoría de las iteraciones, se utiliza JBR para la eficiencia. Cada $k$-ésima iteración, los agentes realizan una actualización de BR independiente estándar para corregir los errores de aproximación.
   • Esto busca combinar la eficiencia de muestreo de JBR con la precisión de IBR.

3. Contribuciones Clave

1. Marco JBR: Introducción de la Mejor Respuesta de Experiencia Conjunta, una modificación directa de PSRO que reutiliza trayectorias compartidas para calcular las mejores respuestas para todos los agentes simultáneamente, mejorando significativamente la eficiencia de muestreo.
2. Remedios para el Sesgo Fuera de Línea: Identificación de las limitaciones del RL fuera de línea inherentes a JBR y la propuesta/evaluación de tres remedios específicos: JBR Conservador, JBR con Aumento de Exploración (con garantías de convergencia teórica) y BR Híbrida.
3. Estudio Empírico Exhaustivo: Una comparación rigurosa de las variantes de JBR contra PSRO estándar (BR Independiente) y las líneas base de MARL predominantes (Aprendizaje Independiente y CTDE) en entornos discretos (póker) y continuos (partículas).

4. Resultados Experimentales

Entornos

• Discretos: Kuhn Poker (espacio de estados pequeño, totalmente cubierto) y Leduc Poker (espacio de estados más grande, información imperfecta).
• Continuos: Simple Tag, Simple Adversary y Simple Push (entornos de partículas multiagente).

Hallazgos

• Factibilidad en Dominios Simples: En Kuhn Poker, donde el espacio de estados es pequeño y está totalmente cubierto, JBR iguala el comportamiento de convergencia del PSRO estándar, confirmando su factibilidad bajo condiciones de buen muestreo.
• Fallo de la JBR Naíf: En Leduc Poker, la JBR naíf (sin exploración o conservadurismo) falla en mantener la precisión del equilibrio debido al sesgo de aprendizaje fuera de línea, estancándose en una explotabilidad mayor comparada con PSRO.
• Efectividad de las Variantes:
  • JBR Conservador es estable pero tiene un desempeño pobre comparado con PSRO debido a su cautela excesiva.
  • JBR con Aumento de Exploración ($\delta$-R) muestra ganancias moderadas pero carece de dirección.
  • JBR con Aumento de Exploración ($\delta$-T) logra el mejor equilibrio, alcanzando una precisión de equilibrio cercana a la de PSRO con significativamente menos muestras. La exploración dirigida anticipa las actualizaciones de los oponentes, lo que conduce a una convergencia temprana más rápida.
  • BR Híbrida (HBR-PSRO) cierra la brecha de precisión restante con PSRO con solo un aumento modesto en el costo de muestreo.
• Eficiencia de Muestreo: JBR-PSRO-$\delta$T alcanza un NashConv cercano al de PSRO con aproximadamente la mitad de los episodios de mejor respuesta requeridos por el PSRO estándar.
• Comparación con MARL: En todos los entornos, los métodos basados en PSRO (incluyendo variantes de JBR) superan consistentemente a los paradigmas estándar de MARL (Aprendizaje Independiente y CTDE) en términos de robustez estratégica y precisión de equilibrio.

5. Significado y Reivindicaciones

El artículo afirma que JBR hace que PSRO sea sustancialmente más práctico para el aprendizaje estratégico a gran escala preservando la robustez del equilibrio.

• Escalabilidad: Al amortizar las interacciones con el entorno entre los agentes, JBR reduce el costo de muestreo de la computación de la mejor respuesta, abordando el principal cuello de botella de PSRO en entornos de muchos agentes o con simuladores costosos.
• Robustez: Los resultados confirman que el entrenamiento estratégicamente fundamentado (estilo PSRO) sigue siendo más robusto que los enfoques estándar de MARL cuando se hace eficiente en muestreo.
• Despliegue Práctico: Las variantes propuestas, particularmente JBR-PSRO-$\delta$T y HBR-PSRO, ofrecen vías viables para desplegar PSRO en dominios donde los costos de interacción con el entorno dominan el tiempo de ejecución, sin sacrificar la calidad de los equilibrios aprendidos.

Los autores señalan que, aunque JBR mejora la eficiencia, PSRO y sus variantes aún requieren más iteraciones y muestras que los métodos típicos de MARL, y la escalabilidad a dominios continuos de alta dimensión sigue siendo un desafío para trabajos futuros.