Resumen Técnico: El Problema de los Dos Bultos en el Aprendizaje por Refuerzo Matemático

Definición del Problema

El artículo aborda el desafío de aplicar el Aprendizaje por Refuerzo (RL) a la conjetura de Andrews–Curtis (AC), un prominente problema abierto en la teoría de grupos combinatoria. La conjetura postula que cualquier presentación balanceada del grupo trivial puede transformarse en la presentación trivial $\langle x, y \mid x, y \rangle$ mediante una secuencia finita de movimientos específicos (AC1: inversión, AC2: conjugación/concatenación, AC3: permutación cíclica).

La dificultad central reside en la naturaleza del espacio de búsqueda:

1. Espacios de búsqueda vastos: El grafo de las presentaciones posibles es infinito.
2. Recompensas dispersas: Un agente recibe una recompensa solo tras la trivialización completa; no existen señales de "fallo temprano" intermedio o indicadores de progreso parcial.
3. El fenómeno de los "Dos Bultos" (Two-Hump): Los autores identifican una barrera estructural crítica donde las instancias del problema están distribuidas de forma bimodal. La mayoría de las presentaciones son o bien trivialmente resolubles (mediante una reducción de longitud simple y codiciosa/greedy) o efectivamente imposibles (que requieren caminos que aumentan temporalmente la longitud, los cuales los heurísticos estándar rechazan). Crucialmente, existe una escasez de instancias intermedias de "dificultad media pero resolubles", creando un "valle" de datos que impide un aprendizaje de currículo efectivo.

Metodología

Para cerrar la brecha de dificultad y superar la distribución de los Dos Bultos, los autores proponen un enfoque de tres vertientes que combina innovaciones algorítmicas, diseño arquitectónico y generación de datos dirigida.

1. Espacio de Acción: Supermovimientos de Sustitución

En lugar de operar sobre movimientos AC primitivos, los autores introducen los movimientos de sustitución como el espacio de acción primario.

• Mecanismo: Una sustitución trata a los relatores como secuencias cíclicas e inserta uno dentro de otro en un punto donde ocurre una cancelación. Esto combina múltiples movimientos primitivos (AC1, AC2, AC3) en una sola acción.
• Beneficio: Esto permite al agente dar pasos más grandes y significativos a través del grafo AC y reduce significativamente el espacio de estados efectivo al ignorar las permutaciones cíclicas.
• Base Teórica: Ivanov (2018) demostró que, si la conjetura AC es cierta, las sustituciones bastan para realizar todas las transformaciones AC.

2. Arquitectura: El Transformer de Doble Anillo (Dual-Ring Transformer)

Para manejar el espacio de acción estructurado y de gran escala de las sustituciones, respetando las simetrías matemáticas del problema, los autores desarrollaron el Transformer de Doble Anillo.

• Simetría Cíclica: A diferencia de los Transformers estándar que utilizan codificación posicional absoluta, esta arquitectura trata a los relatores como anillos cíclicos. Emplea codificaciones posicionales relativas cíclicas donde la puntuación de atención depende de la distancia cíclica $d(i, j) = (i - j) \mod L$.
• Atención Cruzada (Cross-Attention): La red procesa ambos relatores en paralelo, utilizando atención cruzada para identificar subcadenas coincidentes entre $r_1$ y $r_2$, lo cual es crítico para determinar movimientos de sustitución válidos.
• Cabeza de Política (Policy Head): La salida es una distribución sobre movimientos de sustitución válidos, enmascarada para asegurar que solo las acciones que conducen a una cancelación (donde $r_1[i] = \pm r_2[j]$) reciban una probabilidad distinta de cero.

3. Generación de Datos: Poblando el Valle

Reconociendo que las estrategias estándar de "desordenamiento" (scrambling) fallan al generar instancias difíciles pero resolubles, los autores emplean dos técnicas novedosas de generación de datos:

• Perturbación por Automorfismo: Aplicar automorfismos a presentaciones triviales conocidas (ej. $AK(2)$) transforma estas en presentaciones con características de trayectoria drásticamente diferentes. Mientras que la original puede ser fácil, su imagen automórfica puede requerir pasos de aumento de longitud, moviéndola efectivamente del "bulto fácil" al "valle".
• Juego Generador-Solucionador: Se formula un juego asimétrico de dos jugadores donde un Generador (un agente PPO) aplica secuencias de automorfismos para aumentar la dificultad de la presentación, mientras un Solucionador (búsqueda codiciosa/greedy) intenta trivializarlas. El Generador es recompensado por crear instancias que desafíen al Solucionador, apuntando específicamente a la región de dificultad intermedia.
• Datasets Resultantes: Este proceso produce AC-19 (125,192 presentaciones AC-triviales cortas, longitud $\le 19$) y AC-1M (1,136,154 presentaciones AC-triviales difíciles, longitud $\le 30$), los primeros conjuntos de datos públicos a gran escala de este tipo.

Resultados Clave

Los autores evalúan sus métodos en el conjunto de datos de referencia Miller–Schupp de 1,190 presentaciones.

• Mejora de Rendimiento: La combinación de supermovimientos de sustitución y el Transformer de Doble Anillo (PPO-Sub-DRT) resuelve 610 presentaciones (media sobre 5 semillas), un incremento significativo respecto al mejor baseline de RL previo de 457 (PPO-AC-ResNet).
• Impacto de los Datos: La incorporación del dataset generado AC-1M mejora aún más el rendimiento, demostrando que la generación de datos dirigida ayuda con éxito a los agentes a aprender estrategias generales para presentaciones difíciles.
• Eficiencia de la Ruta: Aunque la Búsqueda Codiciosa (GS) con sustituciones resuelve más instancias (640) debido a la exploración exhaustiva, el agente PPO descubre rutas de solución sustancialmente más cortas, particularmente en las presentaciones más difíciles. PPO identifica desvíos de aumento de longitud que los heurísticos codiciosos rechazan, probando que el agente aprende estructuras matemáticas no obvias.
• Superioridad Arquitectónica: El Transformer de Doble Anillo (usando codificaciones relativas cíclicas) supera a una variante que utiliza preprocesamiento de forma canónica con codificaciones absolutas por aproximadamente 25 presentaciones resueltas, resaltando la importancia de aprender representaciones conscientes de la simetría.
• Progreso Matemático: Los autores lograron trivializar más de 100 presentaciones previamente no resueltas de la familia Miller–Schupp. Redujeron los 550 ejemplos no resueltos restantes a 261 clases de equivalencia AC distintas, proporcionando una lista de verificación concreta para investigaciones futuras.

Significado y Reivindicaciones

El artículo sostiene que el progreso en la conjetura de Andrews–Curtis requiere comprender la estructura de dificultad inherente al problema en lugar de simplemente escalar el cómputo.

• La Perspectiva de los Dos Bultos: La identificación de la distribución bimodal de dificultad explica por qué los enfoques anteriores tuvieron dificultades y motiva la necesidad de combinar mejoras algorítmicas con la generación de datos dirigida.
• RL en Entornos de Recompensa Dispersa: El trabajo demuestra que el RL puede tener éxito en entornos de recompensa extremadamente dispersa donde las soluciones requieren cientos de decisiones secuenciales precisas, ofreciendo conocimientos transferibles a la robótica, la demostración de teoremas y la síntesis de programas.
• Utilidad Matemática: Independientemente de si la conjetura AC es finalmente verdadera o falsa, el trabajo realiza un progreso concreto. Si es verdadera, cada nueva trivialización contribuye a una prueba; si es falsa, la trivialización de aparentes contraejemplos estrecha la búsqueda de los genuinos.
• Transferibilidad: La estructura de los "Dos Bultos" y las técnicas desarrolladas (sustituciones, arquitecturas cíclicas, juegos generador-solucionador) se presentan como generalizables a otros problemas de búsqueda matemática donde ocurren distribuciones de dificultad bimodal y movimientos que violan el progreso.

Los autores concluyen que el progreso futuro no vendrá de mejoras marginales en la búsqueda clásica, sino que requerirá métodos basados en el aprendizaje capaces de explotar la estructura más allá de lo que los heurísticos fijos pueden capturar.