🤖 machine learning

Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions

This paper introduces CDQAC, an offline reinforcement learning algorithm that learns effective Job Shop and Flexible Job Shop scheduling policies from static, suboptimal datasets, demonstrating that broad state-action coverage is more critical than trajectory quality for high performance and sample efficiency.

Original authors: Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

Published 2026-06-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Learning from "Bad" Examples

Imagine you want to learn how to solve a complex puzzle, like a massive Jigsaw Puzzle representing a factory schedule. Usually, to learn this skill, you’d need a master puzzle-solver to show you exactly how to place every piece perfectly. This is how most AI systems are trained today: they watch "expert" data or try thousands of times in a simulator until they get it right. This takes a long time and a lot of computing power.

This paper introduces a new AI method called CDQAC. The surprising twist? CDQAC doesn’t need expert advice. It learns how to solve the puzzle effectively by looking at randomly assembled puzzles.

Yes, you read that right. The AI looks at schedules made by a computer program that just picks machines and jobs at random—schedules that are usually terrible and inefficient. From this "garbage" data, the AI figures out how to build a much better schedule than even the experts who created the original data.

The Problem: Factory Scheduling is Hard

In factories, managers face the Job Shop Scheduling Problem (JSP). Imagine you have 10 different jobs to do, and 5 different machines. Each job has several steps, and each step must happen in a specific order on a specific machine. The goal is to finish everything as fast as possible (minimizing the "makespan").

Old Way: Use complex math or trial-and-error simulations. This is slow and expensive.
The AI Way: Teach a computer to make decisions step-by-step. But usually, this requires the AI to "play" the simulation millions of times to learn, which is inefficient.

The Solution: CDQAC (Conservative Discrete Quantile Actor-Critic)

The authors created an AI agent named CDQAC. Think of it as a smart student who studies from a library of old, messy test papers.

The "Actor" (The Decision Maker): This part of the AI decides which job to put on which machine next.
The "Critic" (The Judge): This part looks at the random schedules in the dataset and tries to figure out: "If I had chosen this specific machine for this specific job, how good or bad would that have been?"

CDQAC is special because it uses a "Quantile Critic." Instead of just guessing an average score for a decision, it looks at the range of possible outcomes. It’s like a weather forecaster who doesn’t just say "It will be 70 degrees," but says "There’s a 10% chance it’s 60, a 80% chance it’s 70, and a 10% chance it’s 80." This helps the AI understand risk and uncertainty better.

The Counter-Intuitive Discovery: Why Random Data Works Best

In most AI fields (like robotics or video games), random data is useless. If a robot moves randomly, it falls off a cliff, and the AI learns nothing. Experts say you need high-quality, expert data to learn well.

But this paper proves that for Factory Scheduling, the opposite is true.

The authors found that random data is actually the best training material. Here is why, using an analogy:

The "Puzzle Piece" Analogy:
Imagine the perfect schedule is a completed picture.

Expert Data (Genetic Algorithms): These are like looking at 100 nearly-finished puzzles. They are all very similar. They show you how to finish the puzzle, but they don’t show you many different ways to start or middle sections. If the AI only sees these, it gets stuck in a "local optimum"—it knows how to finish that specific type of puzzle, but it’s rigid.
Random Data: This is like looking at 1,000 piles of puzzle pieces where people just grabbed handfuls and slapped them together. Most are nonsense. However, because the piles are so diverse, they contain every possible combination of pieces.

The AI’s job is "Trajectory Stitching." It looks at the random piles and says:

"In this random pile, the start was terrible, but the middle was okay."
"In that other random pile, the start was okay, and the end was great."
"I can stitch the 'okay start' from Pile A to the 'great end' from Pile B to make a perfect schedule!"

Because random data covers the widest variety of situations (State-Action Coverage), it gives the AI the most "puzzle pieces" to work with. The AI can then pick and choose the best fragments from different random schedules to build a new, superior schedule that never existed in the original data.

Key Features of the AI

To make this work, CDQAC has two special tricks:

Delayed Policy Updates: The AI doesn’t change its decision-making strategy immediately. It waits until its "Judge" (the Critic) has had enough time to accurately evaluate the random data. This prevents the AI from making bad decisions based on early, noisy guesses.
Dueling Architecture: The AI separates its thinking into two streams:
- Value Stream: How good is the current situation overall?
- Advantage Stream: How much better is choosing Machine A over Machine B in this specific situation?
  This helps the AI focus on the differences between choices, which is crucial when there are hundreds of possible machines and jobs.

The Results

The authors tested CDQAC against:

Online RL: AI that learns by playing the simulation (like DANIEL or L2D).
Offline RL: Other AI that learns from static data.
Heuristics: Traditional rule-based methods.

The findings:

CDQAC trained on random data outperformed AI trained on expert data.
CDQAC outperformed state-of-the-art online AI methods, even though it never interacted with a simulator during training.
It was highly sample-efficient. It only needed 1% to 5% of the data that other methods required to achieve similar or better results.
It generalized well. It learned on small problems (10 jobs, 5 machines) and successfully solved much larger, unseen problems (30 or 40 jobs).

Summary

This paper flips the script on how we train AI for scheduling. Instead of needing perfect examples or expensive simulations, we can use cheap, random, suboptimal data. By using a smart algorithm (CDQAC) that stitches together the best parts of many bad schedules, the AI can learn to solve complex factory problems faster and more efficiently than ever before. It proves that in scheduling, breadth of experience (coverage) is more valuable than depth of expertise (quality).

Technical Summary: Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions

Problem Statement
The Job Shop Scheduling Problem (JSP) and Flexible Job Shop Scheduling Problem (FJSP) are critical combinatorial optimization challenges in manufacturing, aiming to minimize makespan. While online deep reinforcement learning (DRL) methods like Learning-to-Dispatch (L2D) and DANIEL have shown strong performance, they suffer from sample inefficiency, requiring extensive interaction with simulated environments. Existing offline RL approaches for scheduling, such as Offline-LD, rely on near-optimal data generated by computationally expensive Constraint Programming (CP) solvers, limiting scalability and leaving the potential of vast, suboptimal heuristic data underutilized. The authors argue that scheduling problems possess unique structural properties—dense, objective-aligned rewards and equal-length trajectories—that make them particularly suited for learning from suboptimal, even random, data, contrary to standard offline RL benchmarks where data quality typically dictates performance.

Methodology
The paper introduces Conservative Discrete Quantile Actor-Critic (CDQAC), an offline RL algorithm designed to learn effective scheduling policies from static, suboptimal datasets. CDQAC integrates three key components:

Quantile Critic: Instead of estimating a scalar Q-value, the critic approximates the full return distribution $Z_\pi(s, a)$ using a mixture of Dirac deltas at fixed quantile fractions. This provides more accurate value estimates than standard Q-learning. To mitigate overestimation, two critic heads are used, and the minimum of their estimates is taken for target computation.
Conservative Q-Learning (CQL): To address distributional shift in offline settings, CDQAC employs CQL regularization. This penalizes the overestimation of out-of-distribution (OOD) actions by maximizing the log-sum-exp of Q-values for all available actions while minimizing the Q-value for the action taken in the dataset. This ensures the policy remains conservative regarding actions not supported by the static dataset.
Delayed Policy Updates and Dueling Architecture: The policy is updated less frequently than the critic (every $\eta$ steps) to prevent the propagation of noisy critic estimates to the policy, a critical stabilization mechanism for offline discrete RL. The critic utilizes a novel dueling architecture with separated inputs: the value stream $V_\theta$ receives only global state embeddings, while the advantage stream $A_\theta$ receives specific machine-operation pair embeddings. This decomposition helps stabilize learning in variable-size action spaces.

The state representation is encoded using a Dual Attention Network (DAN), which processes operations and machines in parallel attention streams to capture complex relationships.

Key Contributions

CDQAC Algorithm: A novel offline RL method that outperforms state-of-the-art online and offline baselines on JSP and FJSP using only suboptimal data, eliminating the need for expert demonstrations or environment interaction during training.
Architectural Innovations: Integration of a quantile critic with a separated-input dueling architecture and delayed policy updates, tailored for the variable-size, discrete action spaces of scheduling problems.
Theoretical Insight on Data Quality: The paper demonstrates that for scheduling, offline RL performance is governed by state-action coverage rather than data quality. Due to dense rewards and equal trajectory lengths, random data provides broader coverage than heuristic data (like Genetic Algorithms), making it the strongest training source.
Sample Efficiency: CDQAC achieves competitive performance using only 1–5% of the data required by online RL baselines (e.g., 10–25 training instances).

Results

Offline RL Comparison: CDQAC consistently outperforms Offline-LD, Implicit Q-Learning (IQL), and Behavioral Cloning (BC) across various training datasets (PDR, GA, PDR-GA, Random). Notably, CDQAC achieves its best performance when trained on Random data, surpassing policies trained on higher-quality heuristic data.
Online RL Comparison: CDQAC outperforms online baselines (DANIEL, Residual, FJSP-DRL, L2D) on standard benchmarks (Taillard, Demirkol, Brandimarte, Hurink) and generated instances. It demonstrates superior generalization to larger, unseen instance sizes (e.g., 30x10, 40x10) when trained on smaller instances (10x5).
Ablation Studies: Removing the delayed policy update or the dueling architecture significantly degrades performance, especially as instance size and action space complexity increase.
Coverage Analysis: Empirical metrics confirm that Random datasets have significantly higher state-action coverage than heuristic datasets. Ablations show that if the structural properties of scheduling (dense reward, equal trajectory length) are removed (e.g., via sparse rewards or early termination), the advantage of random data disappears, validating the coverage hypothesis.

Significance
The paper challenges the conventional wisdom in offline RL that "noisy-expert" data is superior to random data. It establishes that in domains with dense, objective-aligned rewards and fixed horizons, state-action coverage is the primary driver of offline performance. Consequently, simple random heuristics can generate the most effective training data for scheduling problems. CDQAC demonstrates that offline RL can not only match but exceed online RL performance in scheduling, offering a highly sample-efficient alternative that leverages readily available, suboptimal data without the computational burden of expert solvers or online simulation.