Resumen Técnico: Generalización más allá de la suboptimidad en el Aprendizaje por Refuerzo Offline para la Programación de Tareas

1. Definición del Problema

El artículo aborda el Problema de Programación de Taller de Trabajo (JSP) y el Problema de Programación de Taller de Trabajo Flexible (FJSP). El objetivo es programar un conjunto de trabajos en máquinas disponibles para minimizar la makespan (el tiempo de finalización de la última operación).

• JSP: Cada operación debe ser procesada por una máquina específica.
• FJSP: Cada operación puede ser procesada por cualquier máquina de un subconjunto compatible.
• Desafío: Los métodos exactos (p. ej., Programación por Restricciones) garantizan la optimalidad pero carecen de escalabilidad para instancias grandes. Las heurísticas (p. ej., Algoritmos Genéticos, Reglas de Despacho de Prioridad) son escalables pero subóptimas.
• Limitaciones actuales del RL: Los métodos de Aprendizaje Profundo por Refuerzo (DRL) en línea (p. ej., L2D, DANIEL) logran un alto rendimiento pero sufren de ineficiencia de muestras, requiriendo una interacción extensiva con entornos simulados para converger. Por el contrario, los métodos de RL offline han tenido dificultades para aprender de datos subóptimos en la programación, a menudo dependiendo de demostraciones de expertos casi óptimas o fallando al generalizar más allá de la distribución de los datos.

2. Metodología: Actor-Crítico de Cuantiles Discretos Conservadores (CDQAC)

Los autores proponen CDQAC, un algoritmo de RL offline diseñado para aprender políticas de programación efectivas directamente de conjuntos de datos estáticos y subóptimos (incluyendo aquellos generados por heurísticas aleatorias) sin interacción con el entorno.

Componentes Principales

1. Crítico de Cuantiles con Arquitectura Dueling:

   • En lugar de estimar un retorno esperado escalar $Q(s,a)$, CDQAC modela la distribución completa del retorno $Z_\theta(s,a)$ mediante regresión de cuantiles. Esto captura la varianza en los resultados para una sola acción, lo cual es crucial en la programación donde una misma acción puede conducir a makespans muy diferentes dependiendo de las decisiones futuras.
   • Emplea una arquitectura de Red Dueling que separa el flujo de valor de estado $V_\theta(s)$ del flujo de ventaja $A_\theta(s,a)$.
   • Novedad: A diferencia de las redes dueling estándar que alimentan la misma entrada a ambos flujos, CDQAC utiliza entradas separadas: $V_\theta$ recibe únicamente la incrustación (embedding) del estado global, mientras que $A_\theta$ recibe incrustaciones específicas de la operación, la máquina y el par. Esto estabiliza el aprendizaje al evitar que estimaciones de ventaja ruidosas corrompan el valor del estado global.

2. Regularización de Aprendizaje Q Conservador (CQL):

   • Para prevenir la sobreestimación de acciones Fuera de Distribución (OOD) (un modo de fallo común en el RL offline), CDQAC integra una penalización CQL.
   • La pérdida del crítico combina la pérdida de Diferencia Temporal (TD) con un término de regularización que penaliza la sobreestimación de acciones no presentes en el conjunto de datos, asegurando que la política aprendida permanezca conservadora en pares estado-acción no vistos.

3. Actualizaciones de Política Retrasadas:

   • En el RL discreto offline con espacios de acción de tamaño variable, las estimaciones tempranas y ruidosas del crítico pueden propagar errores a través de objetivos de bootstrapping.
   • CDQAC actualiza la red de la política solo cada $\eta$ pasos del crítico (establecido en 4 en los experimentos). Esto permite que el crítico de cuantiles se estabilice y se ajuste a la distribución del retorno antes de ser utilizado para guiar la mejora de la política, evitando la convergencia prematura hacia óptimos locales subóptimos.

4. Arquitectura de Red:

   • El algoritmo utiliza una Red de Atención Dual (DAN) para codificar la instancia de programación. La DAN procesa las operaciones y las máquinas a través de bloques de atención separados para capturar restricciones complejas de precedencia y recursos, generando incrustaciones para el actor y el crítico.

3. Contribuciones Clave

1. Innovación Algorítmica: Introducción de CDQAC, el primer método de RL offline para JSP/FJSP que aprende políticas efectivas puramente a partir de datos subóptimos (incluyendo políticas aleatorias), superando tanto a las heurísticas generadoras de datos como a los modelos de RL online de vanguardia.
2. Diseño Arquitectónico: Un novedoso crítico de cuantiles dueling con entradas separadas y actualizaciones de política retrasadas, diseñado específicamente para manejar los espacios de acción discretos, combinatorios y de tamaño variable de los problemas de programación.
3. Perspectiva Teórica sobre la Calidad de los Datos: El artículo desafía el paradigma convencional del RL offline (donde los datos de "experto ruidoso" son superiores a los datos aleatorios). Argumenta que para la programación, la cobertura estado-acción es el factor determinante para el rendimiento, no la calidad de los datos. Esto se debe a dos propiedades estructurales de la programación:
   • Recompensa Densa y Alineada con el Objetivo: La señal de recompensa (incremento negativo de la makespan parcial) es densa y está perfectamente alineada con el objetivo de optimización, a diferencia de las recompensas dispersas en la robótica.
   • Trayectorias de Longitud Igual: Todas las heurísticas constructivas (expertas o aleatorias) generan trayectorias de longitud idéntica (igual al número de operaciones), eliminando el sesgo de longitud de trayectoria que suele favorecer a los datos de expertos.
   • En consecuencia, una política aleatoria proporciona la cobertura estado-acción más amplia, convirtiéndola en la fuente de entrenamiento óptima para el RL offline en este dominio.

4. Resultados Experimentales

Los autores evaluaron CDQAC en los estándares de la industria para JSP (Taillard, Demirkol) y FJSP (Brandimarte, Hurink), así como en instancias generadas.

• Rendimiento vs. Baselines:

  • CDQAC superó consistentemente a los baselines de RL online (DANIEL, Residual, FJSP-DRL, L2D) tanto en los benchmarks de JSP como de FJSP, incluso cuando fue entrenado con datos aleatorios.
  • Superó a otros métodos de RL offline (Offline-LD, IQL, Clonación de Comportamiento) y a las heurísticas utilizadas para generar los conjuntos de datos.
  • Notablemente, CDQAC entrenado con datos Aleatorios alcanzó los mejores resultados, superando a los modelos entrenados con datos de Algoritmos Genéticos (GA) o Reglas de Despacho de Prioridad (PDR).

• Eficiencia de Muestras:

  • CDQAC es altamente eficiente en muestras, requiriendo solo del 1% al 5% del tamaño del conjunto de datos original (p. ej., 10–25 instancias de entrenamiento) para aprender políticas de alta calidad.
  • Generaliza bien desde instancias de entrenamiento pequeñas (p. ej., $10 \times 5$) a instancias más grandes y no vistas (p. ej., $40 \times 10$), superando a los baselines online en estos escenarios fuera de distribución.

• Estudios de Ablación:

  • Eliminar la Actualización de Política Retrasada causó una degradación masiva del rendimiento (hasta un aumento del 112% en la brecha) en instancias de $20 \times 10$, confirmando su necesidad para la estabilidad en espacios de acción grandes.
  • La Arquitectura Dueling con entradas separadas también mostró una importancia significativa a medida que aumentaba el tamaño de la instancia.
  • Los experimentos con estructuras de recompensa modificadas (dispersas o de aproximación) y terminación temprana confirmaron que el fenómeno de "los datos aleatorios son mejores" depende estrictamente de las propiedades de recompensa densa y trayectoria de longitud igual de la programación estándar.

5. Significación y Reivindicaciones

El artículo afirma que CDQAC representa un cambio significativo en cómo debe abordarse el RL offline para problemas de optimización combinatoria como la programación.

• Cambio de Paradigma: Demuestra que la suposición estándar del RL offline —que se requieren datos de experto de alta calidad para tener éxito— no se sostiene para la programación. En su lugar, la amplia cobertura del espacio estado-acción es la restricción crítica.
• Aplicabilidad Práctica: Al aprender de heurísticas aleatorias o subóptimas, CDQAC elimina la necesidad de simuladores costosos (para el entrenamiento online) o de generadores de datos expertos computacionalmente intensivos (como CP) para crear datos de entrenamiento. Esto hace que el RL offline sea una solución viable y escalable para la programación en el mundo real, donde construir un simulador perfecto es inviable pero existen datos históricos subóptimos.
• Estado del Arte: Los autores posicionan a CDQAC como el primer método de RL offline que supera al RL online en JSP/FJSP mientras entrena exclusivamente con datos aleatorios, estableciendo un nuevo referente de eficiencia y rendimiento en este dominio.