Discovering Interpretable Multi-Parameter Control Policies for Evolutionary Algorithms Using Deep Reinforcement Learning

Planteamiento del Problema
Si bien el Aprendizaje por Refuerzo Profundo (Deep-RL) se ha convertido en una herramienta de vanguardia para la Configuración Dinámica de Algoritmos (DAC), específicamente para el control de parámetros en Algoritmos Evolutivos (EAs), persiste una barrera significativa: la falta de un análisis teórico riguroso para configuraciones de múltiples parámetros. Las pruebas teóricas existentes para el control de parámetros están limitadas en gran medida a escenarios de un solo parámetro, debido a que derivar políticas de múltiples parámetros que sean efectivas, interpretables y susceptibles de un estudio formal es difícil. Además, depender de redes neuronales crea un cuello de botella de "caja negra"; los profesionales y teóricos requieren reglas matemáticas simbólicas explícitas en lugar de pesos neuronales opacos para verificar, analizar y generalizar los comportamientos algorítmicos. El desafío específico abordado es el control de cuatro parámetros simultáneamente en el Algoritmo Genético (GA) $(1+(\lambda, \lambda))$ optimizando la función OneMax—un problema donde se ha demostrado formalmente la existencia de aceleraciones super-constantes mediante control dinámico, pero donde el control de múltiples parámetros sigue estando poco explorado.

Metodología
Los autores proponen un marco de dos etapas para cerrar la brecha entre el rendimiento empírico de Deep-RL y la interpretabilidad teórica, tal como se ilustra en la Figura 1 del artículo:

1. Generación de Oráculo mediante Deep-RL (Etapa I):

   • Entorno: El $(1+(\lambda, \lambda))$-GA se modela como un Proceso de Decisión de Markov Contextual (MDP) donde el estado es el fitness actual, y las acciones son los cuatro parámetros: tamaño de la población de mutación ($\lambda_m$), tamaño de la población de cruce ($\lambda_c$), coeficiente de tasa de mutación ($\alpha$) y coeficiente de sesgo de cruce ($\beta$).
   • Comparación de Algoritmos: El estudio compara Double Deep Q-Networks (DDQN) y Proximal Policy Optimization (PPO).
   • Representación del Espacio de Acciones: Se prueban dos arquitecturas: Combinatoria (tratando las combinaciones de parámetros como acciones atómicas) y Factorizada (descomponiendo el espacio de acciones en sub-acciones independientes para cada parámetro).
   • Mejoras: Los autores introducen mejoras agnósticas al algoritmo, incluyendo la descomposición del espacio de acciones, el desplazamiento de recompensa (reward shifting, sesgo adaptativo) y el descuento de horizonte largo (usando $\gamma \approx 1.0$).
   • Hallazgos sobre RL: El DDQN con espacios de acciones factorizados, desplazamiento de recompensa adaptativo y factores de descuento altos resulta robusto. En contraste, PPO sufre de "colapso de política", convergiendo frecuentemente a políticas estáticas subóptimas (por ejemplo, fijando $\lambda_m=1$) independientemente del espacio de acciones o de los intentos de modelado de recompensa.

2. Destilación Simbólica (Etapa II):

   • Diseño Manual: Basándose en las trayectorias generadas por el mejor agente de DDQN, los autores derivan manualmente una política de control transparente y simbólica. Analizan la relación entre el progreso del fitness y los valores de los parámetros para formular ecuaciones explícitas.
   • Ajuste Fino: Estas ecuaciones simbólicas diseñadas a mano son refinadas posteriormente mediante SMAC3 (una herramienta de configuración de algoritmos automatizada). El espacio de búsqueda incluye puntos de cambio para los tamaños de población y factores de amplificación, lo que permite la optimación precisa de las constantes simbólicas.

Contribuciones Clave

• Eficacia Comparativa de los Métodos de Deep-RL: El artículo demuestra que, si bien PPO es estable en dominios generales de RL, falla en este entorno específico de DAC debido al colapso de la política. Por el contrario, DDQN, cuando se equipa con representaciones de acción factorizadas y estrategias específicas de recompensa/descuento, navega con éxito el paisaje de múltiples parámetros para generar trayectorias de alta calidad.
• Descubrimiento de Políticas Simbólicas: Los autores van más allá de las redes neuronales de caja negra al destilar los comportamientos aprendidos en una política simbólica. Esta política no solo es interpretable, sino que también supera a las líneas base existentes.
• Marco de Destilación de Dos Etapas: El artículo introduce una metodología que primero utiliza Deep-RL para explorar el espacio de soluciones y luego utiliza la configuración de algoritmos (SMAC3) para refinar las representaciones simbólicas diseñadas a mano, produciendo una política que es tanto empíricamente superior como teóricamente tratable.
• Análisis de Importancia de Parámetros: A través de estudios de ablación, el artículo establece una jerarquía de importancia de parámetros: $\lambda_m \gg \alpha \gg \lambda_c \gg \beta$. Revela que el desacoplamiento de $\lambda_m$ y $\lambda_c$ (permitiendo que $\lambda_c$ sea significativamente mayor que $\lambda_m$) es un factor crítico para el rendimiento.

Resultos

• Rendimiento de RL: La mejor configuración de DDQN (representación factorizada, Desplazamiento de Recompensa Adaptativo, $\gamma=0.9998$) supera consistentemente a PPO y a las políticas de control de un solo parámetro a través de diversos tamaños de problema ($n=100$ a $n=2,000$).
• Rendimiento de la Política Simbólica: La política simbólica final (refinada por SMAC3) logra un Tiempo de Ejecución Esperado (ERT) normalizado de aproximadamente 4.7, en comparación con 6.9 para la línea base teórica ($\pi_{THEORY}$) y 5.8 para la línea base basada en IRACE.
• Escalabilidad: La política simbólica derivada mantiene su ventaja de rendimiento a través de una amplia gama de tamaños de problema, incluyendo instancias muy grandes de hasta $n=40,000$.
• Magnitud de la Mejora: La política ajustada por SMAC3 produce una aceleración consistente, superando a la línea base derivada de la teoría en aproximadamente un 27.5% y al enfoque basado en IRACE entre un 19.4% y un 32.2% dependiendo del tamaño del problema.

Significancia y Reivindicaciones
El artículo afirma que este trabajo logra cerrar la brecha entre el descubrimiento empírico de Deep-RL y la verificación teórica en Computación Evolutiva. Al convertir la salida de "caja negra" de una red neuronal en una política simbólica de "caja blanca", los autores proporcionan:

1. Interpretabilidad: Reglas matemáticas explícitas que permiten a los investigadores realizar análisis formales de tiempo de ejecución, una tarea previamente obstaculizada por la complejidad de las redes neuronales.
2. Generalización: La naturaleza simbólica de la política permite la generalización zero-shot a instancias de problemas y dimensiones no vistas, evitando el sobreajuste común en las redes neuronales.
3. Eficiencia: La evaluación de la política simbólica incurre solo en un costo de $O(1)$, evitando el costo computacional de la inferencia de redes profundas.
4. Tractabilidad Teórica: La política derivada ofrece un objetivo concreto para futuros procesos de prueba teórica respecto a los factores constantes de los tiempos de ejecución lineales para el $(1+(\lambda, \lambda))$-GA, abordando un vacío donde los límites teóricos actuales suelen ser demasiado pesimistas en comparación con los resultados empíricos.

Los autores concluyen que, si bien Deep-RL es una herramienta poderosa para el descubrimiento de políticas, su verdadero valor en la configuración de algoritmos se realiza solo cuando sus salidas se destilan en formas simbólicas interpretables que puedan ser analizadas y generalizadas rigurosamente.