🤖 machine learning

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

本文介绍了 CDQAC，一种离线强化学习算法，该算法能够从静态的、次优的数据集中学习有效的作业车间（Job Shop）和柔性作业车间（Flexible Job Shop）调度策略，并证明了广泛的状态-动作覆盖范围对于实现高性能和样本效率比轨迹质量更为关键。

原作者： Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

发布于 2026-06-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位繁忙工厂的经理，面对着众多的机器和堆积如山的待办任务。你的目标是尽可能快地完成所有工作。这就是车间调度问题（Job Shop Scheduling Problem）。

传统上，为了高效地学习如何处理这个问题，你可能会雇佣一名“机器人学徒”（AI），让它通过尝试不同的调度方案、犯错并从结果中学习来进行练习。这被称为在线强化学习（Online Reinforcement Learning）。但问题在于，它需要练习数百万次才能变得优秀，这需要耗费巨大的时间和计算资源。

或者，你可以雇佣一位人类专家来写下他们最好的调度方案，然后教机器人仅仅去模仿这些笔记。这就是模仿学习（Imitation Learning）。但机器人永远无法超越写下这些笔记的人类；它会被困在那个水平之上。

核心理念：从“随机”错误中学习

这篇论文介绍了一种名为 CDQAC（保守离散分位数行为者-评论家算法，Conservative Discrete Quantile Actor-Critic）的新方法。它使用的是离线强化学习（Offline Reinforcement Learning）。

换句话说，研究人员并没有让机器人在真实的工厂环境中进行练习（这既慢又贵），也没有强迫它去模仿专家（这限制了它的潜力），而是给了机器人一个庞大的图书馆，里面存放着大量陈旧、混乱且有时甚至很糟糕的调度方案——这些方案是由简单的规则、遗传算法甚至纯粹的随机性生成的。

令人惊讶的发现是？机器人从这些随机、混乱的数据中学习到的效果，竟然比从“专家”数据中学习的效果还要好。

为什么随机数据胜出了？（谜题类比）

通常在 AI 训练中，你需要高质量的数据。如果你在教某人开车，你应该看专业驾驶员的视频，而不是看人们撞墙的视频。

然而，作者认为调度问题有所不同。他们使用了两个主要比喻来解释为什么随机数据如此有效：

“密集奖励”（Dense Reward）信号：
在许多 AI 游戏（如电子游戏）中，你只有在最后赢或输时才会获得奖励（分数）。在此过程中，你并不知道自己做得好不好。
但在调度中，你做的每一个动作都会立即给你反馈。如果你把一个任务放在一台机器上，你立刻就能知道这增加了多少总时长。这就像是在舞蹈表演的每一步之后都会得到评分，而不仅仅是在表演结束时。这意味着即使是一个“糟糕”的随机动作，也会明确告诉 AI 它到底有多糟，从而让它能够学习每一个动作的价值。
“拼图碎片”（覆盖范围 vs. 质量）：
想象你正在尝试解决一个巨大的拼图。
- 专家数据就像是一个盒子里只有来自图片左上角的拼图碎片。它们是完美的、高质量的碎片，但它们只展示了图像的一小部分。因为缺少其他部分，你无法完成整个拼图。
- 随机数据则像是从拼图各个角落收集来的碎片袋。有些碎片是倒着的，有些来自天空，有些来自草地。就单个碎片而言，它们可能看起来很乱或“错误”，但组合在一起，它们覆盖了整个画面。
因为这篇论文中的 AI 足以“缝合”这些碎片，所以拥有广泛多样的碎片（覆盖范围）比拥有来自单一位置的完美碎片更为重要。随机数据覆盖了更广阔的“领域”，使得 AI 能够找到比专家数据更好的解决方案。

AI 如何学习（“缝合”的比喻）

这个 AI 不仅仅是复制它看到的调度方案。它的行为就像一位高级裁缝，看着一堆旧的、破损的衣服（即那些随机的调度方案）：

它看到一件红衬衫的袖子非常合身。
它看到一件蓝衬衫的裤子非常合身。
它看到一件绿衬衫的衣领非常合身。

尽管这堆衣服中没有任何一件是完美的，但 AI 可以将这些最好的部分缝合在一起，创造出一套全新的、完美的套装，而这套套装在之前从未存在过。它通过分析成千上万次的过往尝试（甚至是失败的尝试），学习如何在特定的时刻选择最合适的“机器”来处理特定的“任务”。

结果：快速、廉价且更好

论文表明，这种新方法（CDQAC）：

优于在线学习： 它击败了那个必须练习数百万次的“机器人学徒”，尽管 CDQAC 从未见过真实的工厂环境。
优于专家： 它创造出的调度方案比它所接受训练的“专家”数据还要好。
极其高效： 它只需要通常学习所需数据的 1% 到 5%。这就像是通过阅读几页手册就学会了开车，而不是行驶了 10,000 英里。
泛化能力强： 它在小规模问题上学习，并成功解决了它从未见过的更大、更复杂的问题。

总结

论文声称，对于工厂调度而言，你不需要一个完美的老师，也不需要数百万小时的练习。你只需要一大堆过去尝试留下的、杂乱的记录（甚至是随机的尝试）。通过使用一种特殊的算法，仔细分析这些混乱尝试中每一步的“价值”，AI 就可以将这些碎片缝合成一个比原始“老师”所能产出的任何方案都更快、更好的完美调度方案。

技术摘要：超越次优性：面向调度问题的离线强化学习泛化研究

1. 问题定义

本文研究了作业车间调度问题 (JSP) 和 柔性作业车间调度问题 (FJSP)。其目标是在可用机器上调度一组作业，以最小化完工时间 (makespan)（即最后一个工序的完成时间）。

JSP： 每个工序必须由特定的单台机器进行加工。
FJSP： 每个工序可以由兼容子集中的任何一台机器进行加工。
挑战： 精确算法（如约束规划）虽然能保证最优性，但在大规模实例面前缺乏可扩展性。启发式算法（如遗传算法、优先级调度规则）虽然具有可扩展性，但往往是次优的。
当前强化学习的局限性： 在线深度强化学习 (DRL) 方法（如 L2D, DANIEL）取得了强劲的表现，但存在样本效率低的问题，需要与模拟环境进行大量的交互才能收敛。相反，离线强化学习方法在处理调度问题中的次优数据时表现不佳，通常依赖于接近最优的专家演示，或者无法超越数据分布进行泛化。

2. 方法论：保守离散分位数演员-评论家算法 (CDQAC)

作者提出了 CDQAC，这是一种离线强化学习算法，旨在直接从静态的、次优的数据集（包括由随机启发式算法生成的决策数据）中学习有效的调度策略，而无需与环境进行交互。

核心组件

带有对偶结构的分位数评论家 (Quantile Critic with Dueling Architecture)：
- CDQAC 不仅仅估计标量期望回报 $Q(s,a)$ ，而是使用分位数回归来建模完整的回报分布 $Z_\theta(s,a)$ 。这捕捉了单个动作在输出结果上的方差，这在调度问题中至关重要，因为同一个动作可能由于未来的决策不同而导致截然不同的完工时间。
- 它采用了对偶网络 (Dueling Network) 架构，将状态价值流 $V_\theta(s)$ 与优势流 $A_\theta(s,a)$ 分离开来。
- 创新点： 不同于标准的对偶网络将相同的输入喂给两个流，CDQAC 使用了分离的输入： $V_\theta$ 仅接收全局状态嵌入，而 $A_\theta$ 接收工序、机器以及配对特定的嵌入。通过这种方式，它防止了噪声较大的优势估计破坏全局状态价值，从而稳定了学习过程。
保守 Q 学习 (CQL) 正则化：
- 为了防止对分布外 (OOD) 动作的过度估计（这是离线强化学习中常见的失败模式），CDQAC 集成了 CQL 惩罚项。
- 评论家损失函数结合了时序差分 (TD) 损失与一个正则项，该正则项会对数据集中不存在的动作进行惩罚，确保学习到的策略在未见的“状态-动作”对上保持保守。
延迟策略更新 (Delayed Policy Updates)：
- 在具有可变大小动作空间的离线离散强化学习中，早期的噪声评论家估计会通过自助式目标 (bootstrapped targets) 传播误差。
- CDQAC 每经过 $\eta$ 个评论家步数（在实验中设为 4）才更新一次策略网络。这使得分位数评论家能够在被用于引导策略改进之前，先稳定并拟合回报分布，从而防止过早收敛到次优局部最优解。
网络架构：
- 该算法利用双重注意力网络 (Dual Attention Network, DAN) 来编码调度实例。DAN 通过独立的注意力模块处理工序和机器，以捕捉复杂的优先顺序和资源约束，从而为演员和评论家生成嵌入。

3. 主要贡献

算法创新： 引入了 CDQAC，这是首个针对 JSP/FJSP 的离线强化学习方法，它能够纯粹从次优数据（包括随机策略）中学习有效策略，性能超越了生成数据的启发式算法以及最先进的在线强化学习基准。
架构设计： 提出了一种带有分离输入的对偶分位数评论家以及延迟策略更新的新颖架构，专门用于处理调度问题中规模可变、离散且具有组合特性的动作空间。
关于数据质量的理论见解： 本文挑战了传统的离线强化学习范式（即认为“带噪声的专家”数据优于“随机”数据）。作者指出，对于调度问题而言，决定性能的关键因素是状态-动作覆盖度 (state-action coverage)，而非数据质量。这是由于调度问题的两个结构特性：
- 稠密且目标一致的奖励： 奖励信号（负的部分完工时间增量）是稠密的，并且与优化目标完美对齐，这与机器人领域中的稀疏奖励不同。
- 等长的轨迹： 所有构造性启发式算法（无论是专家还是随机）生成的轨迹长度都是一致的（等于工序总数），消除了倾向于专家数据的轨迹长度偏差。
- 因此，随机策略提供了最广泛的状态-动作覆盖度，使其成为此类领域中离线强化学习的最佳训练来源。

4. 实验结果

作者在标准的 JSP (Taillard, Demirkol) 和 FJSP (Brandimarte, Hurink) 基准测试以及生成的实例上对 CDQAC 进行了评估。

性能对比基准：
- 即使在基于随机数据训练的情况下，CDQAC 在 JSP 和 FJSP 基准测试上的表现也始终优于在线强化学习基准 (DANIEL, Residual, FJSP-DRL, L2D)。
- 它超越了其他离线强化学习方法 (Offline-LD, IQL, 行为克隆) 以及用于生成数据集的启发式算法。
- 值得注意的是，使用随机数据训练的 CDQAC 达到了最佳效果，甚至优于使用遗传算法 (GA) 或优先级调度规则 (PDR) 数据训练的模型。
样本效率：
- CDQAC 具有极高的样本效率，仅需原始数据集大小的 1% 到 5%（例如 10–25 个训练实例）即可学习到高质量策略。
- 它在从小规模训练实例（如 $10 \times 5$ ）到更大规模未见实例（如 $40 \times 10$ ）的过程中表现出良好的泛化能力，在这些分布外场景中优于在线基准模型。
消融实验：
- 去除延迟策略更新会导致性能大幅下降（在 $20 \times 10$ 实例上差距增加达 112%），证实了其对于大动作空间稳定性的必要性。
- 采用分离输入的对偶架构在实例规模增大时也显示出了显著的重要性。
- 对修改后的奖励结构（稀疏奖励或代理奖励）以及提前终止进行的实验证实，这种“随机数据最优”的现象严格依赖于标准调度问题中的稠密奖励和等长轨迹属性。

5. 重要性与主张

本文声称 CDQAC 代表了处理调度等组合优化问题时，对待离线强化学习方式的一次重大转变。

范式转移： 它证明了——在调度领域——“高质量专家数据是成功的必要条件”这一标准离线强化学习假设并不成立。相反，广泛的覆盖度才是关键约束。
实际应用价值： 通过从随机或次优启发式算法中学习，CDQAC 消除了对昂贵模拟器（用于在线训练）或计算密集型专家求解器（如 CP）生成训练数据的需求。这使得离线强化学习成为解决现实世界调度问题的可行且可扩展的方案，因为在现实中构建完美的模拟器往往是不可能的，但历史上的次优数据却是现成的。
达到最先进水平 (SOTA)： 作者将 CDQAC 定位为第一个在完全使用随机数据训练的情况下，仍能超越在线强化学习在 JSP/FJSP 任务上的离线强化学习方法，为该领域建立了新的性能与效率基准。