Perturbando Respuestas Óptimas en Juegos de Suma Cero

Información Básica

• ID del Artículo: 2511.12523
• Título: Perturbing Best Responses in Zero-Sum Games
• Autores: Adam Dziwoki, Rostislav Horčík (Universidad Técnica Checa de Praga)
• Clasificación: cs.GT (Teoría de Juegos), cs.AI (Inteligencia Artificial)
• Fecha de Publicación: 16 de noviembre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2511.12523
• Enlace del Código: https://github.com/geoborek/perturbing-best-responses

Resumen

Este artículo investiga los efectos de la perturbación en algoritmos basados en respuestas óptimas, que se utilizan para aproximar equilibrios de Nash en juegos de suma cero, con especial atención en los algoritmos Double Oracle y Fictitious Play. El estudio asume que el oráculo que calcula respuestas óptimas perturba las utilidades aleatoriamente antes de seleccionar la respuesta óptima. Se demuestra que el uso de este oráculo perturbado reduce el número de iteraciones en ambos algoritmos. En ciertos casos, una perturbación adecuada puede garantizar que el número esperado de iteraciones sea logarítmico. Aunque la perturbación de utilidades requiere recorrer todas las estrategias puras con alto costo computacional, el estudio prueba que para juegos donde las estrategias puras tienen estructura interna (como juegos estocásticos parcialmente observables), la perturbación puede implementarse eficientemente.

Antecedentes y Motivación de la Investigación

Problema Central

Calcular equilibrios de Nash en juegos bipartitos de suma cero con espacios de estrategia grandes es un problema computacionalmente intensivo. Aunque teóricamente se sabe que existen equilibrios ε-Nash de tamaño O(log n) (donde n es el número de estrategias puras), los algoritmos tradicionales basados en oráculos de respuesta óptima (BRO) como Fictitious Play (FP) y Double Oracle (DO) requieren Ω(n) iteraciones en el peor caso.

Importancia

1. Brecha Teoría-Práctica: Althöfer y Lipton demostraron la existencia de ε-NE de tamaño logarítmico, pero los algoritmos prácticos no alcanzan esta complejidad
2. Limitaciones de Cotas Inferiores: Hazan y Koren probaron que cualquier algoritmo basado en BRO requiere al menos Ω(√n/log³n) iteraciones
3. Necesidades de Aplicaciones Prácticas: Los algoritmos de aprendizaje por refuerzo profundo (como Policy Space Response Oracles) dependen de estos algoritmos fundamentales

Limitaciones de Métodos Existentes

1. FP y DO: Requieren O(n) iteraciones en el peor caso
2. Algoritmo Hazan-Koren: Aunque proporciona complejidad O(√n/ε²), es complejo y solo ofrece mejora de raíz cuadrada
3. Métodos de Regularización: Como PU y OMWU alcanzan O(log n) iteraciones, pero requieren mantener distribuciones de probabilidad para todas las estrategias puras, no siendo adecuados para juegos grandes

Motivación de la Investigación

Mediante la introducción de perturbación en el oráculo de respuesta óptima, haciéndolo más potente, se busca superar las limitaciones de las cotas teóricas inferiores, logrando velocidad de convergencia logarítmica.

Contribuciones Principales

1. Introducción del Oráculo de Respuesta Óptima Perturbada (PBRO): Se propone un mecanismo que perturba aleatoriamente las utilidades antes de calcular la respuesta óptima
2. Resultados Teóricos:
   • Se prueba que Stochastic Fictitious Play (SFP) alcanza complejidad de iteraciones O(log n/ε²) en esperanza
   • Se prueba que Stochastic Double Oracle (SDO) alcanza O(log n) iteraciones esperadas en instancias específicamente difíciles (ejemplo de Zhang y Sandholm)
3. Esquema de Implementación Eficiente: Se propone un método de perturbación eficiente para juegos con estructura interna (como POSG, juegos de planificación de rutas), sin necesidad de recorrer todas las estrategias puras
4. Verificación Experimental: Se valida la efectividad del método de perturbación en múltiples tipos de juegos, incluyendo juegos matriciales, juegos estocásticos y juegos de planificación de rutas
5. Herramientas Teóricas: Se utiliza el truco Gumbel-max para establecer la conexión entre SFP y el predictor exponencial ponderado aleatorio (REWF)

Explicación Detallada del Método

Definición de la Tarea

Entrada: Juego matricial M ∈ ℝ^(m×n), parámetro de precisión ε > 0 Salida: Par de estrategias ε-equilibrio de Nash ⟨p*, q*⟩ Restricción: Minimizar el número de iteraciones (llamadas al oráculo)

Definición Matemática de la Respuesta Óptima Perturbada

Para el jugador fila, dada la estrategia mixta del jugador columna q ∈ Δ_n:

B̃R_r(q) ∈ argmin_{i∈[m]} π_i(Mq - u)

donde u es un vector aleatorio cuyos componentes son variables aleatorias i.i.d.

Para el jugador columna, dada la estrategia mixta del jugador fila p ∈ Δ_m:

B̃R_c(p) ∈ argmax_{j∈[n]} π_j(p^⊤M + v)

Stochastic Fictitious Play (SFP)

Flujo del Algoritmo:

1. Inicialización: t←1, p←e_k, q←e_l (estrategias puras iniciales)
2. Calcular límites de condición de terminación: lb←BRVal_r(q), ub←BRVal_c(p)
3. Mientras ub - lb > tε:
   • t←t+1
   • i←B̃R_r(q), j←B̃R_c(p) (respuesta óptima perturbada)
   • p←p+e_i, q←q+e_j (acumulación de estrategias)
   • Actualizar límites
4. Retornar estrategia promediada: ⟨p*/t, q*/t⟩

Innovaciones Clave:

• Uso de oráculo perturbado en lugar de oráculo determinista
• Mantenimiento de vectores de estrategia acumulada, retornando estrategia promediada al final
• Condición de terminación usando valores de respuesta óptima sin perturbar

Fundamentos Teóricos de la Perturbación Gumbel

Truco Gumbel-max (Lema 1): Para un vector x ∈ ℝ^n, si z tiene componentes independientes e idénticamente distribuidas según la distribución Gumbel G(0,β):

P(argmax_i π_i(x+z) = i*) = π_i*(softmax(x/β))

Esto significa que usar respuesta óptima con perturbación Gumbel es equivalente a muestrear de una distribución softmax.

Conexión con REWF:

• La selección de estrategia del jugador fila en SFP es equivalente a la estrategia REWF
• En la ronda t, se muestrea de softmax(-η∑^{t-1} Me)
• El parámetro η = 1/β controla el equilibrio exploración-explotación

Núcleo del Análisis Teórico

Teorema 3 (Complejidad de SFP): Para juego matricial normalizado a 0,1 M ∈ ℝ^(m×n), m ≤ n, estableciendo β = (2+√(2ln n))/(ε√(8ln n)), SFP encuentra ε-NE en O(log n/ε²) iteraciones esperadas.

Esquema de Prueba:

1. Establecer número de iteraciones T = ((2+√(2ln n))/ε)² ∈ O(log n/ε²)
2. Utilizar Corolario 2 (cota de arrepentimiento de REWF), con probabilidad ≥3/4:

   ∑_{t=1}^T M(i_t,j_t) - min_i ∑_{t=1}^T M(i,j_t) ≤ √T(1 + √(ln n)/2)
   

3. Aplicar resultado dual para jugador columna (probabilidad ≥3/4)
4. Ambos eventos ocurren simultáneamente con probabilidad ≥1/2
5. Combinar ambas desigualdades para obtener ub - lb ≤ ε
6. Número esperado de ejecuciones ≤2

Stochastic Double Oracle (SDO)

Características del Algoritmo:

• Mantener subconjuntos de estrategias R ⊆ m, C ⊆ n
• Cada ronda calcula el equilibrio de Nash del subjuego MR,C
• Usar oráculo perturbado para añadir nuevas estrategias

Análisis para Juegos Específicos:

Ejemplo 1 (Matriz L):

L = [0   1   ...  1  ]
    [-1  0   ...  1  ]
    [⋮   ⋮   ⋱   ⋮  ]
    [-1  -1  ... 0  ]

Lema 4 (Esperanza de Perturbación Uniforme): Para la fila k con x = ⟨1,...,1,0,-1,...,-1⟩, usando perturbación U(-1/2,1/2), el índice esperado de respuesta óptima perturbada EI = k/2

Teorema 6: SDO encuentra NE de L en O(log n) iteraciones esperadas

Técnica de Prueba:

• Definir función potencial X_t = max{r_t, c_t}, donde r_t = min R_t, c_t = min C_t
• Usar teoría de drift para probar X_t - EX_{t+2} ≥ X_t/2
• Aplicar Corolario 17 para obtener ET ≤ 2ln n

Implementación Eficiente de Perturbación

Método de Agrupamiento: Para juegos con estructura interna (como juegos estocásticos):

1. Identificar elementos matriciales correspondientes al mismo estado terminal
2. Agrupar elementos matriciales en K clusters
3. Aplicar el mismo valor de perturbación aleatoria a cada cluster

Fórmula de Perturbación:

B̃R_r(q) = argmin_{i∈[m]} π_i((L + ∑_{k=1}^K z_k B_k)q)

donde B_k es matriz de máscara, identificando elementos del k-ésimo cluster

Ventajas:

• Solo necesita generar K números aleatorios (K << mn)
• Preserva la semántica de la estructura del juego
• Aplicable a POSG, EFG y otros juegos estructurados

Configuración Experimental

Conjuntos de Datos y Tipos de Juegos

1. Juegos Matriciales Aleatorios: Matrices n×n, elementos muestreados uniformemente de 0,1, 100 instancias por tamaño
2. Matrices L y U^⊤: Instancias difíciles del Ejemplo 1 y 2
3. Juego f-finger Morra: Juego clásico, tamaño matricial f²×f²
4. Juego Colonel Blotto: 5 campos de batalla, presupuestos de unidades diferentes
5. Juego Estocástico n-bit Aleatorio: Correspondiente a matriz 2^n×2^n, con estructura de árbol
6. Juego de Planificación de Rutas: Malla n×n, un lado busca ruta más corta, otro lado elige aristas para aumentar costo

Métricas de Evaluación

• Número de Iteraciones: Número de llamadas al oráculo necesarias para alcanzar ε-NE
• Valor ε: Establecido en 0.1
• Estadísticas: Media y desviación estándar de 10 experimentos repetidos

Métodos de Comparación

1. FP: Fictitious Play Estándar
2. AFP: Anticipatory Fictitious Play
3. SAFP: Versión perturbada de AFP
4. DO: Double Oracle Estándar
5. SDO: Versión perturbada de Double Oracle

Detalles de Implementación

• Lenguaje de Programación: Python
• Hardware: AMD Ryzen 7 PRO 7840U
• Generación de Números Aleatorios: Biblioteca numpy, semilla inicial 1
• Inicialización: Índice de peor caso (k=l=n)
• Desempate: Seleccionar respuesta óptima con índice mínimo
• Parámetro β de SFP: Establecido según Teorema 3
• Distribución de Perturbación SDO:
  • Análisis teórico: U(-1,1)
  • Aplicación práctica: U(-0.01,0.01) y U(-0.001,0.001)

Resultados Experimentales

Resultados Principales

Desempeño de SFP en Diferentes Juegos

Juegos Matriciales Aleatorios 0,1:

• AFP muestra mejor desempeño, significativamente superior a otros métodos
• SFP y SAFP muestran desempeño similar, ligeramente superior a FP
• En juegos aleatorios, la ventaja de perturbación no es evidente
• El número de iteraciones crece aproximadamente linealmente con la escala

Matriz U^⊤:

• FP y AFP muestran complejidad de peor caso O(n)
• SFP y SAFP reducen significativamente el número de iteraciones
• Para n=1000, SFP requiere aproximadamente 10-15 iteraciones, mientras FP requiere 1000
• Verifica la complejidad teórica O(log n)

Juego f-finger Morra:

• SFP y SAFP convergen rápidamente, incluso para f grande
• El número de iteraciones de FP y AFP crece con f²
• Para f=10, SFP requiere aproximadamente 50 iteraciones, FP requiere 200+

Desempeño de SDO en Diferentes Juegos

Matrices L y U^⊤ (Perturbación Teórica U(-1,1)):

• SDO alcanza la complejidad logarítmica predicha teóricamente
• Para n=2000, SDO requiere aproximadamente 10-15 iteraciones
• DO requiere n iteraciones (no mostrado en gráfico por escala)
• Verifica perfectamente Teorema 6 y 7

Juego f-finger Morra:

• La perturbación reduce significativamente el número de iteraciones
• Tanto U(-0.01,0.01) como U(-0.001,0.001) son efectivos
• Perturbación más pequeña (U(-0.001,0.001)) muestra mejor estabilidad en escala grande

Juego Colonel Blotto:

• 5 campos de batalla, presupuesto de unidades 0-40
• El método de perturbación consistentemente supera versión sin perturbación
• U(-0.01,0.01) muestra mejor desempeño general

Experimentos de Perturbación Eficiente

Juego Estocástico n-bit (Correspondiente a L y U^⊤):

• Usar método de perturbación con agrupamiento
• Para n=2000 (escala 2^11), requiere aproximadamente 100 iteraciones
• Aunque ligeramente más lento que perturbación teórica, muy superior a complejidad lineal de DO
• Prueba la viabilidad de implementación eficiente

Juego de Planificación de Rutas:

• Pruebas en malla n×n
• La perturbación reduce significativamente el número de iteraciones
• La ventaja es más evidente cuando aumenta el tamaño de malla
• Para n=14, versión perturbada requiere aproximadamente 100 iteraciones, sin perturbación requiere 200+

Observaciones de Experimentos de Ablación

Impacto de Intensidad de Perturbación:

• Perturbación excesiva puede dañar convergencia (observado en juegos aleatorios)
• U(-0.001,0.001) muestra desempeño estable en la mayoría de casos
• U(-0.01,0.01) es más efectivo en juegos estructurados

Selección de Distribución de Perturbación:

• Distribución Gumbel: Teóricamente óptima, adecuada para SFP
• Distribución Uniforme: Más simple en práctica, efectiva en SDO
• Ambas muestran desempeño similar en experimentos

Hallazgos Clave

1. Dependencia del Tipo de Juego: La perturbación es efectiva en instancias estructuradas/difíciles, con ventaja no evidente en juegos aleatorios
2. Consistencia Teoría-Práctica: Los resultados experimentales están altamente alineados con predicciones teóricas
3. Viabilidad de Implementación Eficiente: El método de agrupamiento mantiene efectividad mientras reduce significativamente costo computacional
4. Robustez: El método de perturbación muestra desempeño estable en múltiples tipos de juegos

Trabajo Relacionado

Investigación de Convergencia de Fictitious Play

• Robinson (1951): Prueba convergencia de FP a NE en juegos de suma cero
• Conjetura de Karlin: Problema abierto más antiguo sobre velocidad de convergencia de FP
• Resultados Parciales: Resultados de Abernethy et al. (2021), Daskalakis y Pan (2014) para tipos de matriz específicos
• AFP: Propuesto por Cloud et al. (2023), aún requiere O(n) iteraciones pero con constante más pequeña, llamando BRO 4 veces por ronda

Métodos de Regularización

• Hofbauer y Sandholm (2002): Prueba conexión entre perturbación y regularización
• PU y OMWU: Variantes de AFP regularizadas de Cen et al. (2024), alcanzan O(log n) pero requieren mantener distribuciones de probabilidad para todas estrategias
• Diferencia de Este Artículo: PBRO solo requiere mantener subconjunto de estrategias seleccionadas, adecuado para juegos grandes

Investigación de Double Oracle

• Complejidad Base: Se sabe que DO requiere Θ(n) iteraciones, pero falta investigación teórica profunda
• Zhang y Sandholm (2024): Prueba cota inferior exponencial de DO en POSG
• Investigación de Variantes: Self-Play PSRO de McAleer et al. (2022), etc., pero sin garantías de convergencia
• Contribución de Este Artículo: Primer estudio sistemático de propiedades de convergencia de SDO

Límites Teóricos de Algoritmos BRO

• Althöfer (1994), Lipton y Young (1994): Existencia de ε-NE de tamaño O(log n)
• Hazan y Koren (2016):
  • Cota Inferior: Cualquier algoritmo BRO requiere Ω(√n/log³n) iteraciones
  • Cota Superior: Proponen algoritmo O(√n/ε²)
• Avance de Este Artículo: Supera cota inferior teórica mediante fortalecimiento de BRO (añadiendo perturbación)

Aplicaciones en Aprendizaje por Refuerzo Profundo

• Serie PSRO: Lanctot et al. (2017), McAleer et al. (2022), Bighashdel et al. (2024)
• Conexión: Estos métodos dependen del marco DO, SDO de este artículo puede aplicarse directamente
• Impacto Potencial: El mecanismo de perturbación puede mejorar estrategias de exploración en RL profundo

Conclusiones y Discusión

Conclusiones Principales

1. Avance Teórico:
   • SFP alcanza complejidad esperada O(log n/ε²), primera prueba de convergencia logarítmica de algoritmo PBRO
   • SDO alcanza complejidad esperada O(log n) en instancias difíciles específicas
2. Valor Práctico:
   • El método de perturbación reduce significativamente iteraciones en juegos estructurados
   • El esquema de implementación eficiente hace el método aplicable a juegos grandes
3. Contribuciones Metodológicas:
   • Establece conexión teórica entre SFP y REWF
   • Proporciona marco usando teoría de drift para análisis de SDO

Limitaciones

1. Complejidad General de SDO No Resuelta:
   • Solo se prueba complejidad logarítmica para instancias específicas
   • La complejidad en caso general sigue siendo problema abierto
2. Desempeño en Juegos Estocásticos:
   • La perturbación no muestra ventaja evidente en juegos generados aleatoriamente
   • Posiblemente porque juegos aleatorios ya tienen respuestas óptimas inherentemente aleatorias
3. Selección de Parámetro de Perturbación:
   • El parámetro teóricamente óptimo (β) puede ser demasiado grande en práctica
   • Requiere ajuste según juego específico
4. Aproximación de Implementación Eficiente:
   • La perturbación con agrupamiento no es completamente equivalente a perturbación completa
   • Las garantías teóricas solo aplican a caso de perturbación completa
5. Costo Computacional:
   • Aunque reduce iteraciones, cada iteración requiere generar números aleatorios
   • Para algunos juegos, el beneficio puede no compensar costo adicional

Direcciones Futuras

1. Análisis de Complejidad General de SDO:
   • Probar o refutar complejidad logarítmica de SDO en caso general
   • Identificar características de clases de juegos donde SDO es eficiente
2. Estrategias de Perturbación Adaptativa:
   • Ajustar dinámicamente intensidad de perturbación según convergencia
   • Explorar propiedades teóricas de diferentes distribuciones de perturbación
3. Integración con Aprendizaje por Refuerzo Profundo:
   • Integrar PBRO en marco PSRO
   • Investigar efectos de perturbación cuando BRO se aproxima con redes neuronales
4. Clases de Juegos Más Amplias:
   • Extender a juegos generales (no solo suma cero)
   • Investigar mecanismos de perturbación en juegos multiagente
5. Validación en Aplicaciones Reales:
   • Probar en escenarios de juegos reales (póker, juegos de estrategia)
   • Evaluar desempeño bajo restricciones de recursos computacionales reales

Evaluación Profunda

Fortalezas

1. Rigor Teórico:
   • Pruebas matemáticas completas, desde truco Gumbel-max hasta teoría de drift
   • Conexión clara establecida entre SFP y algoritmo de aprendizaje en línea clásico (REWF)
   • Resultados teóricos altamente consistentes con experimentos
2. Selección de Problema Importante:
   • Aborda brecha teoría-práctica de larga data en el campo
   • Supera cota inferior de Hazan-Koren (mediante fortalecimiento de oráculo)
   • Tiene valor de aplicación directa en aprendizaje por refuerzo profundo
3. Innovación de Método:
   • Mecanismo de perturbación simple pero efectivo
   • Esquema de implementación eficiente resuelve cuello de botella computacional
   • Marco unificado aplicable a ambas clases de algoritmos FP y DO
4. Completitud Experimental:
   • Cubre instancias teóricas, juegos clásicos, juegos aleatorios, juegos estructurados
   • Compara múltiples métodos baseline
   • Reporta honestamente resultados negativos en juegos aleatorios
5. Claridad de Escritura:
   • Introducción de antecedentes suficiente, motivación clara
   • Detalles técnicos completos, fuerte reproducibilidad
   • Proporciona código de fuente abierta

Insuficiencias

1. Completitud Teórica:
   • Complejidad general de SDO no resuelta, solo análisis de casos especiales
   • Falta explicación teórica de por qué perturbación falla en juegos aleatorios
   • Brecha teórica entre perturbación eficiente y completa no cuantificada
2. Diseño Experimental:
   • Escala de experimentos en juegos aleatorios relativamente pequeña (n≤1000)
   • Falta comparación directa con algoritmo Hazan-Koren
   • No reporta tiempo de ejecución real, solo número de iteraciones
3. Consideraciones de Practicidad:
   • Falta orientación universal para selección de parámetro de perturbación
   • Falta criterios de decisión sobre cuándo usar perturbación
   • Rango de aplicabilidad de esquema de implementación eficiente no suficientemente claro
4. Profundidad de Análisis:
   • Explicación intuitiva insuficiente de por qué mecanismo de perturbación es efectivo
   • Análisis insuficiente de relación entre estructura de juego y efectividad de perturbación
   • Experimentos de ablación relativamente simples
5. Equidad de Comparación:
   • AFP llama BRO 4 veces por ronda, mientras FP/SFP solo 2 veces
   • Debería reportar también comparación de total de llamadas BRO

Impacto

1. Contribución Teórica:
   • Proporciona nueva dirección para investigación de algoritmos BRO
   • Prueba potencial de fortalecimiento de oráculo
   • Puede inspirar investigación en otros problemas de optimización combinatoria
2. Valor Práctico:
   • Directamente aplicable a marcos DO/FP existentes
   • Tiene potencial de mejora para métodos PSRO en RL profundo
   • Esquema de implementación eficiente tiene operabilidad práctica
3. Limitaciones:
   • Requiere desarrollo teórico adicional para convertirse en método estándar
   • Desempeño en juegos aleatorios limita universalidad
   • Costo computacional requiere validación en aplicaciones a gran escala
4. Reproducibilidad:
   • Proporciona código de fuente abierta, reproducibilidad fuerte
   • Descripción de algoritmo clara, fácil de implementar
   • Configuración experimental detallada

Escenarios de Aplicabilidad

Fuertemente Recomendado:

1. Juegos con estructura clara (EFG, POSG)
2. Juegos con múltiples respuestas óptimas equivalentes
3. Instancias difíciles donde DO/FP converge lentamente
4. Juegos con espacio de estrategia gigante pero estructura interna

Usar con Cautela:

1. Juegos completamente aleatorios
2. Juegos donde respuesta óptima es única y clara
3. Escenarios con recursos computacionales extremadamente limitados
4. Aplicaciones que requieren garantías deterministas

No Recomendado:

1. Juegos pequeños (resolución directa más rápida)
2. Juegos generales sin estructura (ventaja de perturbación no evidente)
3. Escenarios de toma de decisión en tiempo real (aleatoriedad puede no ser aceptable)

Referencias

Fundamentos Teóricos Clave:

1. Althöfer (1994) - Existencia de ε-NE de tamaño logarítmico
2. Hazan & Koren (2016) - Límites teóricos de algoritmos BRO
3. Hofbauer & Sandholm (2002) - Prueba de convergencia de SFP
4. Cesa-Bianchi & Lugosi (2006) - Algoritmo REWF

Trabajo Relacionado: 5. Zhang & Sandholm (2024) - Cota inferior exponencial de DO 6. Cloud et al. (2023) - Anticipatory Fictitious Play 7. Lanctot et al. (2017) - Policy Space Response Oracles 8. Cen et al. (2024) - Algoritmos de juego regularizados

Evaluación General: Este es un excelente artículo que combina bien teoría y práctica. La contribución principal es probar que el mecanismo de perturbación permite que algoritmos BRO alcancen complejidad logarítmica, superando la cota inferior teórica conocida (mediante fortalecimiento de oráculo). El resultado teórico de SFP es completo y riguroso, el análisis de SDO aunque incompleto proporciona perspectivas valiosas. El diseño experimental es completo, reportando honestamente el rango de aplicabilidad del método. Las principales insuficiencias son que la complejidad general de SDO no se resuelve, y falta explicación teórica del pobre desempeño en juegos aleatorios. Este trabajo abre nueva dirección para investigación de algoritmos de teoría de juegos, con potencial valor de aplicación en aprendizaje por refuerzo profundo, mereciendo investigación adicional.