Sintesi Tecnica: Generalizzare Oltre la Subottimalità nel Reinforcement Learning Offline per lo Scheduling

1. Definizione del Problema

Il paper affronta il Problema di Scheduling Job Shop (JSP) e il Problema di Scheduling Job Shop Flessibile (FJSP). L'obiettivo è pianificare un insieme di lavori su macchine disponibili per minimizzare il makespan (il tempo di completamento dell'ultima operazione).

• JSP: Ogni operazione deve essere elaborata da una specifica macchina singola.
• FJSP: Ogni operazione può essere elaborata da qualsiasi macchina appartenente a un sottoinsieme compatibile.
• Sfida: I metodi esatti (es. Programmazione Vincolata) garantiscono l'ottimalità ma mancano di scalabilità per istanze di grandi dimensioni. Le euristiche (es. Algoritmi Genetici, Regole di Priorità di Dispatching) sono scalabili ma subottimali.
• Limitazioni attuali del RL: I metodi di Deep Reinforcement Learning (DRL) online (es. L2D, DANIEL) ottengono prestazioni elevate ma soffrono di inefficienza campionaria, richiedendo un'estesa interazione con ambienti simulati per convergere. Al contrario, i metodi di RL offline hanno faticato a imparare da dati subottimali nello scheduling, spesso affidandosi a dimostrazioni di esperti quasi ottimali o fallendo nel generalizzare oltre la distribuzione dei dati.

2. Metodologia: Conservative Discrete Quantile Actor-Critic (CDQAC)

Gli autori propongono CDQAC, un algoritmo di RL offline progettato per apprendere politiche di scheduling efficaci direttamente da dataset statici e subottimali (inclusi quelli generati da euristiche casuali) senza interazione con l'ambiente.

Componenti Core

1. Critic Quantile con Architettura Dueling:

   • Invece di stimare un ritorno atteso scalare $Q(s,a)$, CDQAC modella l'intera distribuzione del ritorno $Z_\theta(s,a)$ utilizzando la regressione quantilica. Ciò cattura la varianza nei risultati per una singola azione, il che è cruciale nello scheduling dove la stessa azione può portare a makespan molto diversi a seconda delle decisioni future.
   • Impiega un'architettura Dueling Network che separa il flusso del valore dello stato $V_\theta(s)$ dal flusso dell'advantage $A_\theta(s,a)$.
   • Novità: A differenza delle standard dueling networks che inviano lo stesso input a entrambi i flussi, CDQAC utilizza input separati: $V_\theta$ riceve solo l'embedding globale dello stato, mentre $A_\theta$ riceve gli embedding specifici di operazione, macchina e coppia, stabilizzando l'apprendimento evitando che stime di advantage rumorose corrompano il valore dello stato globale.

2. Regolarizzazione Conservative Q-Learning (CQL):

   • Per prevenire la sovrastima delle azioni Out-of-Distribution (OOD) (un comune modo di fallimento nel RL offline), CDQ \text{Q} integra una penalità CQL.
   • La perdita del critic combina la perdita di Temporal Difference (TD) con un termine di regolarizzazione che penalizza la sovrastima di azioni non presenti nel dataset, garantendo che la politica appresa rimanga conservativa sulle coppie stato-azione non viste.

3. Aggiornamenti della Politica Ritardati (Delayed Policy Updates):

   • Nel RL discreto offline con spazi di azione di dimensione variabile, stime del critic precoci e rumorose possono propagare errori attraverso i target di bootstrapping.
   • CDQAC aggiorna la rete della politica solo ogni $\eta$ passi del critic (impostato a 4 negli esperimenti). Ciò consente al critic quantilico di stabilizzarsi e adattarsi alla distribuzione del ritorno prima di essere utilizzato per guidare il miglioramento della politica, prevenendo la convergenza prematura verso ottimi locali subottimali.

4. Architettura della Rete:

   • L'algoritmo utilizza una Dual Attention Network (DAN) per codificare l'istanza di scheduling. La DAN elabora le operazioni e le macchine attraverso blocchi di attenzione separati per catturare complessi vincoli di precedenza e di risorsa, generando gli embedding per l'actor e il critic.

3. Contributi Chiave

1. Innovazione Algoritmica: Introduzione di CDQAC, il primo metodo di RL offline per JSP/FJSP che apprende politiche efficaci puramente da dati subottimali (inclusi quelli di una politica casuale), superando sia le euristiche che generano i dati sia i baselines di RL online allo stato dell'arte.
2. Design Architetturale: Un nuovo critic quantilico dueling con input separati e aggiornamenti della politica ritardati, specificamente adattato per gestire gli spazi di azione discreti, combinatori e di dimensione variabile dei problemi di scheduling.
3. Insight Teorico sulla Qualità dei Dati: Il paper sfida il paradigma convenzionale del RL offline (dove i dati "esperto-rumoroso" sono superiori ai dati casuali). Argomenta che per lo scheduling, la copertura stato-azione è il fattore determinante per le prestazioni, non la qualità dei dati. Ciò è dovuto a due proprietà strutturali dello scheduling:
   • Reward Densa e Allineata all'Obiettivo: Il segnale di reward (incremento negativo del makespan parziale) è denso e perfettamente allineato con l'obiettivo di ottimizzazione, a differenza dei reward sparsi nella robotica.
   • Traiettorie di Lunghezza Uguale: Tutte le euristiche costruttive (sia esperte che casuali) generano traiettorie di lunghezza identica (uguale al numero di operazioni), eliminando il bias della lunghezza della traiettoria che tipicamente favorisce i dati dell'esperto.
   • Di conseguenza, una politica casuale fornisce la più ampia copertura stato-azione, rendendola la fonte di addestramento ottimale per il RL offline in questo dominio.

4. Risultati Sperimentali

Gli autori hanno valutato CDQAC su benchmark standard JSP (Taillard, Demirkol) e FJSP (Brandimarte, Hurink), nonché su istanze generate.

• Performance rispetto ai Baselines:

  • CDQAC ha costantemente superato i baselines di RL online (DANIEL, Residual, FJSP-DRL, L2D) sia sui benchmark JSP che FJSP, anche quando addestrato su dati casuali.
  • Ha superato altri metodi di RL offline (Offline-LD, IQL, Behavioral Cloning) e le euristiche utilizzate per generare i dataset.
  • Notevolmente, CDQAC addestrato su dati Random ha ottenuto i migliori risultati, superando i modelli addestrati su dati di Algoritmi Genetici (GA) o Regole di Priorità di Dispatching (PDR).

• Efficienza Campionaria:

  • CDQAC è altamente efficiente dal punto di vista campionario, richiedendo solo l'1% - 5% della dimensione originale del dataset (es. 10–25 istanze di addestramento) per apprendere politiche di alta qualità.
  • Generalizza bene da istanze di addestramento piccole (es. $10 \times 5$) a istanze più grandi e non viste (es. $40 \times 10$), superando i baselines online in questi scenari out-of-distribution.

• Studi di Ablazione:

  • Rimuovere l'Aggiornamento della Politica Ritardato ha causato un massiccio degrado delle prestazioni (fino a un gap del 112% nell'incremento) su istanze $20 \times 10$, confermando la sua necessità per la stabilità in ampi spazi di azione.
  • Anche l'Architettura Dueling con input separati ha mostrato una significativa importanza all'aumentare della dimensione dell'istanza.
  • Gli esperimenti con strutture di reward modificate (sparse o proxy reward) ed estinzione precoce hanno confermato che il fenomeno "i dati casuali sono i migliori" dipende strettamente dalle proprietà di reward denso e traiettoria a lunghezza uguale dello scheduling standard.

5. Significato e Rivendicazioni

Il paper sostiene che CDQAC rappresenti un cambiamento significativo nel modo in cui il RL offline dovrebbe essere approcciato per i problemi di ottimizzazione combinatoria come lo scheduling.

• Cambio di Paradigma: Dimostra che l'assunto standard del RL offline — ovvero che siano necessari dati di un esperto di alta qualità per avere successo — non vale per lo scheduling. Inveente, la ampia copertura dello spazio stato-azione è il vincolo critico.
• Applicabilità Pratica: Imparando da euristiche casuali o subottimali, CDQAC elimina la necessità di simulatori costosi (per l'addestramento online) o solver esperti computazionalmente intensivi (come il CP) per generare dati di addestramento. Ciò rende il RL offline una soluzione scalabile e valida per lo scheduling reale, dove costruire un simulatore perfetto è impraticabile ma esistono dati storici subottimali.
• Stato dell'Arte: Gli autori posizionano CDQAC come il primo metodo di RL offline in grado di superare il RL online su JSP/FJSP addestrandosi esclusivamente su dati casuali, stabilendo un nuovo benchmark di efficienza e performance in questo dominio.