Resumen Técnico: GAE Resulta Insuficiente en el Autojuego con Información Imperfecta

Enunciado del Problema

El aprendizaje por refuerzo multiagente competitivo (MARL) en juegos con información imperfecta requiere que los agentes operen bajo observabilidad parcial frente a oponentes adversarios, lo que hace necesarias políticas estocásticas. Aunque el aprendizaje por refuerzo mediante autojuego utilizando Optimización de Política Proximal (PPO) ha logrado éxitos empíricos, enfrenta un cuello de botella crítico en el aprendizaje de equilibrios: la varianza en la estimación de la ventaja.

Las implementaciones estándar de PPO dependen de la Estimación Generalizada de la Ventaja (GAE) para agregar residuos de diferencia temporal (TD) de múltiples pasos. En entornos de agente único, GAE equilibra eficazmente el sesgo y la varianza. Sin embargo, en el autojuego con información imperfecta, las políticas de equilibrio son inherentemente estocásticas. GAE hereda la aleatoriedad de la muestreo de acciones futuras dentro de su rastro de múltiples pasos. Dado que las políticas de equilibrio asignan diferentes valores a distintas acciones, el muestreo de acciones futuras introduce ruido intrínseco. Esta varianza se amplifica en escenarios de autojuego y persiste incluso cuando el crítico de valor de estado ($V$-critic) es exacto. En consecuencia, GAE estándar produce estimaciones de gradiente de alta varianza precisamente en los regímenes donde el aprendizaje estable es más crítico, obstaculizando la convergencia hacia equilibrios de alta calidad.

Metodología

Estimador Q-Boosting

Para abordar la varianza introducida por el muestreo de acciones, los autores proponen Q-boosting, un estimador de ventaja con varianza reducida. La innovación central consiste en reemplazar el rastro TD de múltiples pasos muestreado utilizado en GAE con un rastro de Expected SARSA($\lambda$) de múltiples pasos calculado a partir de un crítico centralizado de valor de acción ($Q$-critic).

• Mecanismo: En lugar de realizar bootstrapping a través de acciones futuras muestreadas (lo que introduce ruido), Q-boosting calcula las expectativas de la política en cada paso de respaldo. Promedia el ruido de las acciones futuras estocásticas tomando la esperanza sobre la distribución de acciones definida por la política actual.
• Formulación: Dado un crítico $Q$ centralizado $Q_i(s, a)$ y una política conjunta $\pi$, el valor de estado se calcula como $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$. La estimación de ventaja Q-boosting $\hat{A}^{boost}_{i,\tau}$ se define como:
  $$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$$
  donde el residuo TD de Expected SARSA es $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$.
• Garantía Teórica: Los autores demuestran que para trayectorias en política y $\lambda=1$, el estimador Q-boosting proporciona una estimación sin sesgo del término del gradiente de política de la función de puntuación. Además, si el crítico $Q$ es suficientemente preciso, el error cuadrático medio del estimador Q-boosting es estrictamente menor que el de GAE con un crítico $V$ exacto, siempre que las acciones futuras exhiban una varianza no nula en sus valores de acción.

Optimización de Política con Varianza Reducida (VRPO)

Los autores integran Q-boosting en un algoritmo estilo PPO denominado Optimización de Política con Varianza Reducida (VRPO).

• Arquitectura: VRPO sigue el paradigma de Entrenamiento Centralizado con Ejecución Descentralizada (CTDE). Utiliza actores descentralizados para la ejecución y un crítico $Q$ centralizado para el entrenamiento.
• Objetivo: El algoritmo conserva la función objetivo sustituta recortada de PPO y las actualizaciones de región de confianza, pero modifica los procedimientos de estimación de ventaja y aprendizaje del crítico.
• Procedimiento de Entrenamiento:
  1. Actualización del Actor: Los actores se actualizan utilizando las estimaciones de ventaja Q-boosting. Para mantener las propiedades en política, los términos de expectativa de la política en el cálculo de la ventaja se recalculan utilizando las probabilidades actuales del actor, manteniendo fijos los valores del crítico.
  2. Actualización del Crítico: Los críticos $Q$ centralizados se entrenan minimizando la pérdida de regresión cuadrada contra el objetivo Q-boosting (un rastro de Expected SARSA de múltiples pasos).
  3. Regularización: Se añade una penalización explícita de divergencia KL relativa a una distribución uniforme a la función objetivo de la política para promover la exploración y fomentar la convergencia de la última iteración.
• Manejo de Espacios de Acción Grandes: Para juegos con conjuntos de acciones masivos (por ejemplo, Dou Dizhu), los autores descomponen decisiones complejas en múltiples pasos de tiempo. Esto reduce el número de acciones disponibles por paso a un tamaño manejable, permitiendo la enumeración requerida para la expectativa de la política en el rastro Q-boosting.

Contribuciones Clave

1. Identificación de la Fuente de Varianza: El artículo identifica que el muestreo de acciones futuras en GAE introduce varianza adicional en el autojuego estocástico, la cual persiste incluso con funciones de valor exactas.
2. Estimador Q-Boosting: Los autores derivan Q-boosting, un estimador compatible con PPO que aplica un rastro de Expected SARSA($\lambda$) a un crítico $Q$ centralizado para promediar el ruido del muestreo de acciones futuras.
3. Algoritmo VRPO: La propuesta de VRPO, un algoritmo estilo PPO que aprovecha Q-boosting para lograr una mayor estabilidad y rendimiento.
4. Validación Empírica: Demostración de que reducir la varianza en la estimación de la ventaja produce ganancias sustanciales en la calidad del equilibrio en juegos de diversas escalas.

Resultados Experimentales

Juegos de Tamaño Medio (Explotabilidad Exacta)

Los autores evaluaron VRPO en juegos de tamaño medio donde se puede calcular la explotabilidad exacta: Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3) y Liar's Dice con 2 dados y 5 caras (LiDi 2D5F).

• Rendimiento: VRPO logró consistentemente una explotabilidad más del 15% menor en comparación con varias líneas base basadas en PPO (IPPO, MAPPO, MMD, PPG) bajo un cronograma de entrenamiento compartido.
• Ablación: Los experimentos confirmaron que las ganancias de rendimiento son robustas frente a diferentes parámetros de rastro ($\lambda$), coeficientes de regularización ($\alpha$) y coeficientes de recorte de PPO ($\epsilon$).

Juegos a Gran Escala

Los autores evaluaron VRPO en dominios a gran escala donde la explotabilidad exacta es intratable.

• Dou Dizhu: VRPO se entrenó contra el agente anterior de última generación, PerfectDou. Bajo un presupuesto de entrenamiento coincidente ($\approx 2.65 \times 10^9$ pasos de tiempo), VRPO superó a PerfectDou después de solo el 40% de los pasos de entrenamiento. En evaluaciones cara a cara sobre 100,000 reparticiones, VRPO logró ganancias positivas frente a PerfectDou, DouZero y contra sí mismo (en enfrentamientos con roles intercambiados), estableciendo un nuevo estado del arte.
• Heads-Up No-Limit Texas Hold'em (HUNL): VRPO se entrenó en HUNL con una pila de 200 ciegas grandes. En comparación con IPPO y MAPPO, VRPO redujo significativamente la desviación estándar de las estimaciones de ventaja durante el entrenamiento. Frente a la sólida línea base Slumbot, el agente VRPO logró una ganancia promedio de $33 \pm 19$ mBB/mano sobre 1,000,000 de manos. Cabe destacar que este rendimiento se logró sin búsqueda en línea, resolución de subjuegos o dimensionamiento de subidas basado en planos.

Significado y Alcance

El artículo afirma que la contribución principal es la identificación de la varianza en la estimación de la ventaja como un cuello de botella en el autojuego de equilibrio y la demostración de que Q-boosting mitiga eficazmente este problema. Los resultados sugieren que reducir la varianza en la estimación de la ventaja puede generar ganancias sustanciales en la calidad de los equilibrios aprendidos.

Los autores mantienen un alcance modesto en sus afirmaciones:

• El enfoque está validado para juegos con grandes conjuntos de acciones discretas (mediante descomposición), pero no aborda espacios de acción continuos de alta dimensión.
• El enfoque empírico se centra en el autojuego estocástico con críticos centralizados; los autores no afirman mejoras amplias sobre GAE en las líneas base estándar de RL de agente único.
• El método depende de la capacidad de calcular expectativas de políticas sobre acciones, lo cual es factible en los dominios probados pero puede requerir consideraciones arquitectónicas específicas para espacios de acción extremadamente grandes.

En conclusión, VRPO representa un paso significativo hacia adelante en la aplicación de métodos de gradiente de política a juegos con información imperfecta, al abordar una fuente específica, previamente subidentificada, de varianza inherente al aprendizaje de equilibrios estocásticos.