Technische Samenvatting: Generaliseren voorbij suboptimaliteit in Offline Reinforcement Learning voor Planning

1. Probleemdefinitie

Het artikel behandelt het Job Shop Scheduling Problem (JSP) en het Flexible Job Shop Scheduling Problem (FJSP). Het doel is om een reeks taken te plannen op beschikbare machines om de makespan (de voltooiingstijd van de laatste operatie) te minimaliseren.

• JSP: Elke operatie moet door een specifieke, enkele machine worden verwerkt.
• FJSP: Elke operatie kan worden verwerkt door elke machine uit een compatibele subset.
• Uitdaging: Exacte methoden (bijv. Constraint Programming) garanderen optimaliteit maar missen schaalbaarheid voor grote instanties. Heuristieken (bijv. Genetische Algoritmen, Priority Dispatching Rules) zijn schaalbaar maar suboptimaal.
• Huidige RL-beperkingen: Online Deep Reinforcement Learning (DRL) methoden (bijv. L2D, DANIEL) bereiken sterke prestaties, maar lijden aan sample-inefficiëntie, waarbij uitgebreide interactie met gesimuleerde omgevingen nodig is om te convergeren. Daarentegen hebben offline RL-methoden moeite gehad met het leren van suboptimale data in planning, waarbij ze vaak vertrouwen op bijna optimale expert-demonstraties of falen in het generaliseren buiten de datadistributie.

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

De auteurs stellen CDQAC voor, een offline RL-algoritme dat is ontworpen om effectieve planningspolicies direct te leren van statische, suboptimale datasets (inclusief die gegenereerd door random heuristieken) zonder omgevingsinteractie.

Kerncomponenten

1. Quantile Critic met Dueling Architectuur:

   • In plaats van een scalaire verwachte return $Q(s,a)$ te schatten, modelleert CDQAC de volledige return distributie $Z_\theta(s,a)$ met behulp van quantile regressie. Dit vangt de variantie in uitkomsten voor een enkele actie op, wat cruciaal is in planning waar dezelfde actie tot zeer verschillende makespans kan leiden afhankelijk van toekomstige beslissingen.
   • Het maakt gebruik van een Dueling Network architectuur die de state value stream $V_\theta(s)$ scheidt van de advantage stream $A_\theta(s,a)$.
   • Nieuwigheid: In tegenstelling tot standaard dueling netwerken die dezelfde input naar beide streams voeden, gebruikt CDQAC gescheiden inputs: $V_\theta$ ontvangt alleen de globale state embedding, terwijl $A_\theta$ operatie-, machine- en paar-specifieke embeddings ontvangt. Dit stabiliseert het leren door te voorkomen dat ruizige advantage-schattingen de globale state value corrumperen.

2. Conservative Q-Learning (CQL) Regularisatie:

   • Om overschatting van Out-of-Distribution (OOD) acties te voorkomen (een veelvoorkomende foutmodus in offline RL), integreert CDQAC een CQL-penalty.
   • De critic loss combineert de Temporal Difference (TD) loss met een regularisatieterm die de overschatting van acties die niet in de dataset aanwezig zijn bestraft, waardoor de geleerde policy conservatief blijft op ongeziene state-action paren.

3. Vertraagde Policy Updates:

   • In offline discrete RL met variabel-omvang actieruimtes kunnen vroege ruizige critic-schattingen fouten voortplanten via gebootstrapped targets.
   • CDQAC update de policy network pas elke $\eta$ critic stappen (gesteld op 4 in experimenten). Dit staat de quantile critic toe om te stabiliseren en de return distributie te fitten voordat deze wordt gebruikt om de policy verbetering te sturen, wat voortijdige convergentie naar suboptimale lokale optima voorkomt.

4. Netwerkarchitectuur:

   • Het algoritme maakt gebruik van een Dual Attention Network (DAN) om de planningsinstantie te encoderen. DAN verwerkt operaties en machines via aparte attention blokken om complexe precedentie- en resource-restricties te vangen, en genereert embeddings voor de actor en critic.

3. Belangrijkste Bijdragen

1. Algoritmische Innovatie: Introductie van CDQAC, de eerste offline RL-methode voor JSP/FJSP die effectieve policies leert puur van suboptimale data (inclusief random policies), waarbij zowel de datagenererende heuristieken als state-of-the-art online RL baselines wordt overtroffen.
2. Architecturaal Ontwerp: Een nieuwe dueling quantile critic met gescheiden inputs en vertraagde policy updates, specifiek afgestemd op de variabel-omvang, discrete en combinatorische actieruimtes van planningsproblemen.
3. Theoretisch Inzicht in Datakwaliteit: Het artikel daagt het conventionele offline RL-paradigma uit (waarbij "noisy-expert" data superieur is aan random data). Het betoogt dat voor planning state-action coverage de bepalende factor is voor prestaties, niet de datakwaliteit. Dit komt door twee structurele eigenschappen van planning:
   • Dichte, Objective-Aligned Reward: Het beloningssignaal (negatieve gedeeltelijke toename van de makespan) is dicht en perfect uitgelijnd met het optimalisatie-doel, in tegenstelling tot sparse rewards in robotica.
   • Trajecten van Gelijke Lengte: Alle constructieve heuristieken (expert of random) genereren trajecten van identieke lengte (gelijk aan het aantal operaties), waardoor de bias in trajectlengte die expert-data bevoordeelt, wordt geëlimineerd.
   • Bijgevolg biedt een random policy de breedste state-action coverage, wat het optimale trainingsbron maakt voor offline RL in dit domein.

4. Experimentele Resultaten

De auteurs evalueerden CDQAC op standaard JSP (Taillard, Demirkol) en FJSP (Brandimarte, Hurink) benchmarks, evenals gegenereerde instanties.

• Prestaties vs. Baselines:

  • CDQAC overtrof consequent online RL baselines (DANIEL, Residual, FJSP-DRL, L2D) op zowel JSP als FJSP benchmarks, zelfs wanneer getraind op random data.
  • Het versloeg andere offline RL methoden (Offline-LD, IQL, Behavioral Cloning) en de heuristieken die werden gebruikt om de datasets te genereren.
  • Opvallend genoeg behaalde CDQAC getraind op Random data de beste resultaten, waarmee modellen getraind op Genetic Algorithm (GA) of Priority Dispatching Rule (PDR) data werden overtroffen.

• Sample Efficiëntie:

  • CDQAC is zeer sample-efficiënt en heeft slechts 1% tot 5% van de oorspronkelijke dataset grootte nodig (bijv. 10–25 trainingsinstanties) om hoogwaardige policies te leren.
  • Het generaliseert goed van kleine trainingsinstanties (bijv. $10 \times 5$) naar grotere, ongeziene instanties (bijv. $40 \times 10$), waarbij het online baselines overtreft in deze out-of-distribution scenario's.

• Ablatie Studies:

  • Het verwijderen van de Delayed Policy Update veroorzaakte een enorme prestatiedegradatie (tot 112% gap increase op $20 \times 10$ instanties), wat bevestigt dat dit essentieel is voor stabiliteit in grote actieruimtes.
  • De Dueling Architectuur met gescheiden inputs toonde ook aanzienlijk belang bij toenemende instantie-omvang.
  • Experimenten met aangepaste beloningsstructuren (sparse of proxy rewards) en vroegtijdige terminatie bevestigden dat het "random data is best" fenomeen strikt afhankelijk is van de dichte reward en de gelijke trajectlengte eigenschappen van standaard planning.

5. Betekenis en Claims

Het artikel claimt dat CDQAC een significante verschuiving vertegenwoordigt in hoe offline RL benaderd moet worden voor combinatorische optimalisatieproblemen zoals planning.

• Paradigmaverschuiving: Het demonstreert dat de standaard offline RL-aanname — dat hoogwaardige expert-data vereist is voor succes — niet standhoudt voor planning. In plaats daarvan is brede coverage de kritieke beperking.
• Praktische Toepasbaarheid: Door te leren van random of suboptimale heuristieken, verwijdert CDQAC de noodzaak voor dure simulators (voor online training) of computationeel intensieve expert solvers (zoals CP) om trainingsdata te genereren. Dit maakt offline RL een levensvatbare, schaalbare oplossing voor real-world planning waar het bouwen van een perfecte simulator onhaalbaar is, maar historische suboptimale data wel beschikbaar is.
• State-of-the-Art: De auteurs positioneren CDQAC als de eerste offline RL-methode die online RL op JSP/FJSP overtreft terwijl er uitsluitend op random data wordt getraind, waarmee een nieuwe benchmark voor efficiëntie en prestaties in dit domein wordt gesteld.