Resumen Técnico: Aprender a Buscar y Buscar para Aprender para la Generalización en la Planificación

Enunciado del Problema

La generalización combinatoria sigue siendo un desafío central en el Aprendizaje por Refuerzo Profundo (DRL), donde las políticas o funciones de valor deben generalizar a escenarios fuera de distribución definidos por una estructura de problema común. La planificación clásica ofrece un campo de pruebas ideal para este problema porque la estructura relacional subyacente (predicados y esquemas de acción) es fija y explícita, mientras que las instancias varían en la cantidad de objetos, estados iniciales y objetivos.

Sin embargo, los enfoques estándar de DRL luchan en dominios de planificación con recompensas escasas. La búsqueda en tiempo real (transiciones iterativas de estado a estado), típica en algoritmos de RL como LRTA* o RTDP, es ineficaz para encontrar planes en estos entornos. Por el contrario, los planificadores clásicos utilizan búsqueda de mejor primero (por ejemplo, A*, WA*), pero dependen de heurísticas diseñadas a mano. Aunque trabajos recientes han intentado aprender políticas o heurísticas generales, los métodos existentes a menudo dependen de la búsqueda en tiempo real, el aprendizaje supervisado a partir de demostraciones expertas o el reetiquetado retrospectivo, fallando en establecer un bucle de auto-mejora donde la búsqueda y el aprendizaje se refuercen mutuamente para lograr una generalización de cero disparos a través de tamaños de problema variables.

Metodología: Búsqueda Generalizada para Planificación (GSP)

Los autores proponen GSP, un marco de auto-mejora que combina la búsqueda de mejor primero con Q-learning para aprender funciones generales de valor-acción ($Q_\theta$).

Bucle Central

1. Aprendizaje Guiado por Búsqueda: En lugar de búsqueda en tiempo real, GSP utiliza WA (A ponderado)** para resolver instancias de entrenamiento. La búsqueda se guía por los valores actuales aprendidos de $Q_\theta(s, a)$.
2. Generación de Datos: A medida que WA* expande nodos, genera un búfer de repetición de transiciones. Crucialmente, la búsqueda proporciona señales de supervisión que carece el RL estándar:
   • Rutas al Objetivo: Cuando se alcanza un objetivo, el algoritmo retrocede para asignar valores reales de retorno-hasta-el-objetivo a los pares en la ruta de solución.
   • Caminos Sin Salida: Si un estado es un camino sin salida (sin acciones aplicables), se asigna una penalización fija de retorno al par padre.
   • Límites Inferiores: La búsqueda proporciona un límite inferior sobre el retorno óptimo para cualquier par estado-acción encontrado en una ruta de solución.
3. Actualización de Q-Learning: La red $Q_\theta$ se actualiza utilizando estos objetivos derivados de la búsqueda. Para los pares de rutas al objetivo, el objetivo es $\max(R, \hat{y})$, donde $R$ es el límite inferior derivado de la búsqueda y $\hat{y}$ es el objetivo estándar de bootstrap. Esto evita que las estimaciones de valor caigan por debajo de lo que la búsqueda ya ha demostrado alcanzable.
4. Selección de Instancias: Para optimizar la eficiencia del aprendizaje, el marco mantiene tres grupos de instancias (sin resolver, resueltas y satisfechas) y muestrea de ellos con pesos que aumentan exponencialmente, priorizando las instancias que proporcionan las actualizaciones más informativas (por ejemplo, aquellas con soluciones subóptimas).

Representación: GNN Relacionales

Para garantizar la generalización a través de diferentes números de objetos y objetivos, $Q_\theta$ se representa mediante una Red Neuronal de Grafos Relacional (R-GNN).

• Entrada: Un estado $s$ y un objetivo $g$ se codifican como un conjunto de átomos base. Las acciones aplicables se representan explícitamente introduciendo "objetos de acción" y átomos auxiliares, lo que permite a la red evaluar elecciones de acción específicas dentro del contexto del estado.
• Arquitectura: La red utiliza paso de mensajes sobre la estructura relacional. MLPs específicos de predicados generan mensajes basados en los roles de los argumentos, que se agregan mediante funciones invariantes a la permutación.
• Salida: Un MLP de lectura compartido combina la incrustación del objeto de acción específico con un resumen agrupado del estado y el objetivo para producir el valor Q. Esta arquitectura asegura que el modelo aprenda un principio de puntuación común para acciones fundamentadas en lugar de predictores separados para cada esquema.

Contribuciones Clave

1. Bucle de Búsqueda-Aprendizaje de Auto-mejora: El artículo introduce un marco donde la búsqueda de mejor primero (WA*) genera datos de entrenamiento de alta calidad (incluyendo límites inferiores y señales de caminos sin salida) para actualizar una heurística aprendida, que a su vez guía búsquedas futuras más eficientes.
2. Generalización de Cero Disparos: Las funciones Q aprendidas funcionan como políticas generales capaces de resolver instancias con significativamente más objetos y objetivos diferentes a los vistos durante el entrenamiento, sin requerir búsqueda en tiempo de prueba en muchos casos.
3. Marco Unificado: El enfoque se aplica uniformemente a diversos dominios, desde los puntos de referencia de la pista de aprendizaje de la Competición Internacional de Planificación (IPC) 2023 hasta rompecabezas combinatorios (Sokoban, The Witness) y el dominio PushWorld, utilizando una sola arquitectura y conjunto de hiperparámetros.
4. Superioridad sobre la Búsqueda en Tiempo Real: El trabajo demuestra que reemplazar la búsqueda en tiempo real con búsqueda de mejor primero en el bucle de aprendizaje es crítico para el éxito en dominios de planificación con recompensas escasas y alto factor de ramificación.

Resultados Experimentales

Los autores evaluaron GSP en tres categorías de puntos de referencia:

• Pista de Aprendizaje IPC 2023:

  • Ejecución Codiciosa ($GSP_\pi$): Logró una cobertura del 100% en Blocksworld, Miconic y Spanner, superando líneas base como Lifted HER, LAMA y políticas estilo AlphaZero.
  • Guiado por Búsqueda ($GSP_{WA^*}$): Mostró resultados mixtos; aunque mejoró la cobertura en rompecabezas como Sokoban (14% $\to$ 32%), a veces redujo la cobertura en dominios con factores de ramificación masivos (por ejemplo, Blocksworld) donde la heurística aprendida, aunque buena para la clasificación local, carecía de calibración global.
  • Escalado: Las heurísticas entrenadas en instancias de Blocksworld con <30 bloques resolvieron con éxito instancias con 488 bloques sin búsqueda.

• Rompecabezas Combinatorios (Sokoban, The Witness, 24-Puzzle):

  • En Sokoban, $GSP_{WA^*}$ resolvió el 100% de las instancias con un promedio de 207 expansiones, superando significativamente a WA* con heurísticas estándar (3298 expansiones) y DeepCubeA (1050 expansiones).
  • En The Witness, el método resolvió todas las instancias, demostrando el valor de entrenar en estados de camino sin salida.
  • En 24-Puzzle, el método no logró encontrar soluciones durante el entrenamiento, destacando que el enfoque requiere la capacidad de encontrar al menos una solución para arrancar el aprendizaje, lo cual es difícil en rompecabezas de tamaño fijo extremadamente difíciles sin heurísticas informadas iniciales.

• PushWorld:

  • Entrenado en el Nivel 0, el modelo se generalizó al Nivel 1. $GSP_{WA^*}$ resolvió 48 de 63 instancias del Nivel 1 con planes más cortos y ~30$\times$ menos expansiones que el planificador clásico LAMA.
  • Como política codiciosa, superó significativamente a las líneas base de RL sin modelo (DQN, PPO).

Significado y Afirmaciones

El artículo afirma que la búsqueda de mejor primero es un mecanismo de exploración superior para el aprendizaje por refuerzo generalizado cuando el modelo de transición es conocido, particularmente en dominios con recompensas escasas donde la búsqueda en tiempo real falla al descubrir trayectorias informativas.

El significado principal radica en la demostración de un ciclo de auto-refuerzo: la búsqueda proporciona los objetivos de entrenamiento (límites inferiores, caminos sin salida) que permiten mejorar la heurística, y la heurística mejorada hace que las búsquedas subsiguientes sean más eficientes. Esto permite que el sistema aprenda políticas generales que pueden resolver problemas de tamaño y complejidad arbitrarios sin búsqueda, o heurísticas altamente eficientes que guían la búsqueda hacia soluciones óptimas.

Los autores notan modestamente las limitaciones: la función Q aprendida a menudo actúa como un fuerte mecanismo de clasificación local de acciones, pero puede carecer de calibración global en todo el frente de búsqueda, lo que puede llevar a un rendimiento subóptimo en WA* en dominios con factores de ramificación extremadamente grandes. Sugieren que el trabajo futuro podría centrarse en mejorar la generalización de valores a través de estados y combinar la búsqueda de mejor primero con las fortalezas complementarias de la búsqueda en tiempo real y el reetiquetado retrospectivo de experiencias.