El diseño de algoritmos para el aprendizaje por refuerzo de múltiples agentes (MARL) en juegos con información imperfecta (escenarios en los que los jugadores actúan secuencialmente y no pueden ver la información privada de los demás, como el póquer) históricamente se ha basado en la iteración manual. Los investigadores identifican esquemas de ponderación, reglas de descuento y solucionadores de equilibrios mediante la intuición y el ensayo y error. Los investigadores de Google DeepMind proponen AlphaEvolve, un agente de codificación evolutivo impulsado por un LLM que reemplaza ese proceso manual con una búsqueda automatizada.
El equipo de investigación aplica este marco a dos paradigmas establecidos: Minimización del arrepentimiento contrafactual (CFR) y Oráculos de respuesta del espacio de políticas (PSRO). En ambos casos, el sistema descubre nuevas variantes de algoritmos que funcionan de manera competitiva o mejor que las líneas de base de última generación diseñadas a mano existentes. Todos los experimentos se realizaron utilizando el marco OpenSpiel.
Antecedentes: CFR Y PSRO
CFR es un algoritmo iterativo que descompone la minimización del arrepentimiento en conjuntos de información. En cada iteración, acumula “arrepentimiento contrafáctico” (cuánto habría ganado un jugador jugando de manera diferente) y deriva una nueva política proporcional al arrepentimiento positivo acumulado. Tras muchas iteraciones, la estrategia promediada en el tiempo converge hacia un equilibrio de Nash (NE). Variantes como DCFR (CFR con descuento) y PCFR+ (CFR+ predictivo) mejoran la convergencia mediante la aplicación de reglas específicas de descuento o actualización predictiva, todas desarrolladas mediante diseño manual.
PSRO opera a un nivel más alto de abstracción. Mantiene una población de políticas para cada jugador, construye un tensor de pagos (el metajuego) calculando las utilidades esperadas para cada combinación de políticas de población y luego utiliza un solucionador de metaestrategias para producir una distribución de probabilidad sobre la población. Las mejores respuestas se entrenan en función de esa distribución y se agregan a la población de forma iterativa. El solucionador de metaestrategias (cómo se calcula la distribución de la población) es la opción de diseño central a la que apunta el artículo para el descubrimiento automatizado. Todos los experimentos utilizan un oráculo de mejor respuesta exacto (calculado mediante iteración de valores) y valores de pago exactos para todas las entradas del metajuego, eliminando el ruido de muestreo de Monte Carlo de los resultados.
EL MARCO AlphaEvolve
AlphaEvolve es un sistema evolutivo distribuido que utiliza LLM para mutar el código fuente en lugar de parámetros numéricos. El proceso: se inicializa una población con una implementación estándar (CFR+ como semilla para experimentos CFR; Uniform como semilla para ambas clases de solucionador PSRO). En cada generación, se selecciona un algoritmo principal en función de la aptitud; su código fuente se pasa a un LLM (Gemini 2.5 Pro) con un mensaje para modificarlo; el candidato resultante se evalúa en juegos de poder; Los candidatos válidos se añaden a la población. AlphaEvolve admite la optimización multiobjetivo: si se definen varias métricas de aptitud física, se selecciona una al azar por generación para guiar el muestreo de los padres.
La señal de aptitud es la explotabilidad negativa después de las iteraciones de K, evaluada en un conjunto fijo de juegos de entrenamiento: Kuhn Poker de 3 jugadores, Leduc Poker de 2 jugadores, Goofspiel de 4 cartas y Liars Dice de 5 caras. La evaluación final se realiza en un conjunto de pruebas separado de juegos más grandes e invisibles.
Para CFR, el espacio de búsqueda evolutivo consta de tres clases de Python: RegretAccumulator, PolicyFromRegretAccumulator y PolicyAccumulator. Estos rigen la acumulación de arrepentimiento, la derivación de políticas actuales y la acumulación promedio de políticas, respectivamente. La interfaz es lo suficientemente expresiva como para representar todas las variantes conocidas del CFR como casos especiales. Para PSRO, los componentes evolucionables son TrainMetaStrategySolver y EvalMetaStrategySolver, los solucionadores de metaestrategias utilizados durante el entrenamiento de Oracle y durante la evaluación de explotabilidad.
Algoritmo descubierto 1: VAD-CFR
La variante CFR evolucionada es la CFR con descuento adaptativo a la volatilidad (VAD-CFR). En lugar del promedio lineal y el descuento estático utilizados en la familia CFR, la búsqueda produjo tres mecanismos distintos:
Descuento adaptativo a la volatilidad. En lugar de aplicar factores de descuento fijos α y β a los arrepentimientos acumulativos (como en DCFR), VAD-CFR rastrea la volatilidad del proceso de aprendizaje utilizando un promedio móvil ponderado exponencial (EWMA) de la magnitud del arrepentimiento instantáneo. Cuando la volatilidad es alta, el descuento aumenta, por lo que el algoritmo olvida más rápidamente el historial inestable; cuando la volatilidad cae, conserva más historia. El factor de caída de EWMA es 0,1, con base α = 1,5 y base β = −0,1. Impulso instantáneo asimétrico. Los arrepentimientos instantáneos positivos se multiplican por un factor de 1,1 antes de agregarlos a los arrepentimientos acumulativos. Esta asimetría se aplica a la actualización instantánea, no al historial acumulado, lo que hace que el algoritmo sea más reactivo a las buenas acciones actuales. Difícil comienzo en caliente con ponderación de magnitud del arrepentimiento. El promedio de políticas se pospone por completo hasta la iteración 500. El proceso de acumulación de arrepentimiento continúa normalmente durante esta fase. Una vez que comienza la acumulación, las políticas se ponderan mediante una combinación de peso temporal y magnitud de arrepentimiento instantáneo, priorizando iteraciones con alto contenido de información al construir la estrategia promedio. El umbral de 500 iteraciones fue generado por el LLM sin conocimiento del horizonte de evaluación de 1000 iteraciones.
VAD-CFR se compara con CFR estándar, CFR+, CFR lineal (LCFR), DCFR, PCFR+, DPCFR+ y HS-PCFR+(30) en 1000 iteraciones con K = 1000. La explotabilidad se calcula exactamente. En la evaluación completa de 11 juegos, VAD-CFR iguala o supera el rendimiento de última generación en 10 de los 11 juegos, con Kuhn Poker de 4 jugadores como única excepción.
Algoritmo descubierto 2: SHOR-PSRO
La variante PSRO evolucionada es PSRO de arrepentimiento optimista híbrido suavizado (SHOR-PSRO). La búsqueda produjo un meta-solucionador híbrido que construye una meta-estrategia combinando linealmente dos componentes en cada iteración interna del solucionador:
σ_ORM (Optimistic Regret Matching): proporciona estabilidad para minimizar el arrepentimiento. Las ganancias se calculan, opcionalmente se normalizan y se ajustan en función de la diversidad, y luego se utilizan para actualizar los arrepentimientos acumulados mediante la comparación de arrepentimientos. Se aplica un término de impulso a las ganancias de pago. σ_Softmax (mejor estrategia pura suavizada): una distribución de Boltzmann sobre estrategias puras sesgada hacia modos de alto beneficio. Un parámetro de temperatura controla la concentración: una temperatura más baja significa que la distribución está más concentrada en la mejor estrategia pura.
El solucionador de tiempo de entrenamiento utiliza un programa de recocido dinámico sobre las iteraciones externas de PSRO. El factor de combinación λ se templa de 0,3 → 0,05 (pasando de una explotación codiciosa a la búsqueda de equilibrio), la bonificación de diversidad decae de 0,05 → 0,001 (lo que permite la exploración temprana de la población y luego el refinamiento en la última etapa), y la temperatura softmax cae de 0,5 → 0,01. El número de iteraciones del solucionador interno también aumenta con el tamaño de la población. El solucionador de entrenamiento devuelve la estrategia promediada en el tiempo en iteraciones internas para lograr estabilidad.
El solucionador de tiempo de evaluación utiliza parámetros fijos: λ = 0,01, bonificación de diversidad = 0,0, temperatura = 0,001. Ejecuta más iteraciones internas (base 8000, escalando con el tamaño de la población) y devuelve la estrategia de la última iteración en lugar del promedio, para una estimación de explotabilidad reactiva y silenciosa. Esta asimetría entre formación y evaluación fue en sí misma un producto de la búsqueda, no una elección de diseño humano.
SHOR-PSRO se compara con Uniform, Nash (a través de un programa lineal para juegos de 2 jugadores), AlphaRank, Projected Replicator Dynamics (PRD) y Regret Matching (RM), utilizando K = 100 iteraciones de PSRO. En la evaluación completa de 11 juegos, SHOR-PSRO iguala o supera el rendimiento más moderno en 8 de los 11 juegos.
Configuración experimental
El protocolo de evaluación separa los juegos de entrenamiento y de prueba para evaluar la generalización. El conjunto de entrenamiento para los experimentos CFR y PSRO consta de Kuhn Poker para 3 jugadores, Leduc Poker para 2 jugadores, Goofspiel de 4 cartas y Liars Dice de 5 caras. El conjunto de prueba utilizado en el cuerpo principal del artículo consta de Kuhn Poker para 4 jugadores, Leduc Poker para 3 jugadores, Goofspiel de 5 cartas y Liars Dice de 6 caras: variantes más grandes y complejas que no se han visto durante la evolución. En el apéndice se incluye un análisis completo de 11 juegos. Los algoritmos se corrigen después del descubrimiento de la fase de entrenamiento antes de que comience la evaluación de la prueba.
Conclusiones clave
AlphaEvolve automatiza el diseño de algoritmos: en lugar de ajustar hiperparámetros, evoluciona el código fuente Python real de los algoritmos MARL utilizando Gemini 2.5 Pro como operador de mutación, descubriendo reglas de actualización completamente nuevas en lugar de variaciones de las existentes. VAD-CFR reemplaza el descuento estático con conciencia de la volatilidad: rastrea la magnitud del arrepentimiento instantáneo a través de EWMA y ajusta sus factores de descuento dinámicamente, además retrasa el promedio de políticas por completo hasta la iteración 500, un umbral que el LLM encontró sin que le dijeran que el horizonte de evaluación era de 1000 iteraciones. SHOR-PSRO automatiza la transición de exploración a explotación: al combinar un factor de combinación entre Optimistic Regret Matching y un componente de mejor estrategia pura de Softmax durante el entrenamiento, elimina la necesidad de ajustar manualmente cuándo un meta-solucionador PSRO debe pasar de la diversidad de la población al refinamiento del equilibrio. La generalización se prueba, no se asume: ambos algoritmos se desarrollan en un conjunto de cuatro juegos y se evalúan en un conjunto separado de juegos más grandes e invisibles. VAD-CFR aguanta en 10 de 11 juegos; SHOR-PSRO en 8 de 11, sin reajuste entre entrenamiento y prueba. Los mecanismos descubiertos no son intuitivos por diseño: cosas como un arranque en caliente duro en la iteración 500, un aumento asimétrico de los arrepentimientos positivos en exactamente 1,1 y configuraciones separadas de resolución de entrenamiento/evaluación no son el tipo de opciones a las que suelen llegar los investigadores humanos, que es el argumento central de esta investigación para la búsqueda automatizada en este espacio de diseño.
Consulte el documento. Además, no dude en seguirnos en Twitter y no olvide unirse a nuestro SubReddit de más de 120.000 ML y suscribirse a nuestro boletín. ¡Esperar! estas en telegrama? Ahora también puedes unirte a nosotros en Telegram.
Michal Sutter es un profesional de la ciencia de datos con una Maestría en Ciencias de Datos de la Universidad de Padua. Con una base sólida en análisis estadístico, aprendizaje automático e ingeniería de datos, Michal se destaca en transformar conjuntos de datos complejos en conocimientos prácticos.