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

📄 arXiv: 2509.10303v1 📥 PDF

作者: Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

分类: cs.LG, cs.AI

发布日期: 2025-09-12

💡 一句话要点

提出CDQAC算法，通过离线强化学习从随机数据中学习高效作业调度策略

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 离线强化学习 作业调度问题 分位数回归 Actor-Critic 保守策略更新

📋 核心要点

  1. 在线强化学习方法在作业调度问题中需要大量与模拟环境的交互，且随机策略初始化导致样本效率低下。
  2. CDQAC算法通过离线强化学习直接从历史数据中学习调度策略，无需在线交互，并能改进次优数据。
  3. 实验表明，CDQAC优于现有离线和在线强化学习方法，且在随机数据上训练效果优于高质量数据。

📝 摘要（中文）

本文针对Job-Shop调度问题(JSP)和柔性Job-Shop调度问题(FJSP)，提出了一种新的离线强化学习算法——保守离散分位数Actor-Critic (CDQAC)。该算法直接从历史数据中学习有效的调度策略，无需耗时的在线交互，并能改进次优训练数据。CDQAC将基于分位数的评论家与延迟策略更新相结合，估计每个机器-操作对的回报分布，而不是直接选择配对。实验结果表明，CDQAC能够从多样的数据源中学习，始终优于原始数据生成启发式方法，并超越了最先进的离线和在线强化学习基线。此外，CDQAC具有很高的样本效率，仅需10-20个训练实例即可学习高质量的策略。令人惊讶的是，CDQAC在随机启发式生成的数据上训练时，比在遗传算法和优先级调度规则等更高质量的数据上训练时表现更好。

🔬 方法详解

问题定义：论文旨在解决Job-Shop调度问题(JSP)和柔性Job-Shop调度问题(FJSP)。现有在线强化学习方法需要大量的环境交互，成本高昂，且模拟环境可能无法捕捉真实世界的复杂性。此外，随机策略初始化导致样本效率低下，难以快速学习到有效的调度策略。

核心思路：论文的核心思路是利用离线强化学习，直接从历史数据中学习调度策略，避免在线交互带来的高成本和低效率。通过保守策略更新，算法能够从次优数据中学习，甚至在随机数据上也能取得良好的效果。这种方法的核心在于学习回报的分布，而非仅仅是选择动作。

技术框架：CDQAC算法采用Actor-Critic框架，包含一个基于分位数的Critic和一个Actor。Critic负责估计每个机器-操作对的回报分布，Actor则根据Critic的估计结果选择动作。算法采用延迟策略更新，以保证策略的稳定性。整体流程为：首先，利用历史数据训练Critic；然后，利用Critic指导Actor的策略更新；最后，利用训练好的Actor进行作业调度。

关键创新：CDQAC的关键创新在于将分位数回归引入Critic，从而能够估计回报的分布，而非仅仅是期望回报。这使得算法能够更好地处理不确定性，并从次优数据中学习。此外，保守策略更新保证了算法的稳定性，避免了策略崩溃。另一个创新点是发现随机数据训练效果优于高质量数据，这表明算法具有很强的泛化能力。

关键设计：CDQAC算法的关键设计包括：1) 基于分位数的Critic，采用分位数回归损失函数进行训练；2) 延迟策略更新，采用软更新的方式更新Actor；3) 保守策略更新，通过约束策略更新的幅度，避免策略崩溃；4) 针对JSP/FJSP问题的状态表示和动作空间设计。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

CDQAC算法在JSP和FJSP问题上取得了显著的性能提升。实验结果表明，CDQAC始终优于原始数据生成启发式方法，并超越了最先进的离线和在线强化学习基线。更令人惊讶的是，CDQAC在随机启发式生成的数据上训练时，比在遗传算法和优先级调度规则等更高质量的数据上训练时表现更好，并且仅需10-20个训练实例即可学习高质量的策略。

🎯 应用场景

CDQAC算法在工业运营领域具有广泛的应用前景，可用于优化生产调度、资源分配、物流管理等。通过利用历史数据，企业可以快速部署高效的调度策略，提高生产效率，降低运营成本。该研究成果还有助于推动离线强化学习在其他组合优化问题中的应用。

📄 摘要（原文）

The Job-Shop Scheduling Problem (JSP) and Flexible Job-Shop Scheduling Problem (FJSP), are canonical combinatorial optimization problems with wide-ranging applications in industrial operations. In recent years, many online reinforcement learning (RL) approaches have been proposed to learn constructive heuristics for JSP and FJSP. Although effective, these online RL methods require millions of interactions with simulated environments that may not capture real-world complexities, and their random policy initialization leads to poor sample efficiency. To address these limitations, we introduce Conservative Discrete Quantile Actor-Critic (CDQAC), a novel offline RL algorithm that learns effective scheduling policies directly from historical data, eliminating the need for costly online interactions, while maintaining the ability to improve upon suboptimal training data. CDQAC couples a quantile-based critic with a delayed policy update, estimating the return distribution of each machine-operation pair rather than selecting pairs outright. Our extensive experiments demonstrate CDQAC's remarkable ability to learn from diverse data sources. CDQAC consistently outperforms the original data-generating heuristics and surpasses state-of-the-art offline and online RL baselines. In addition, CDQAC is highly sample efficient, requiring only 10-20 training instances to learn high-quality policies. Surprisingly, we find that CDQAC performs better when trained on data generated by a random heuristic than when trained on higher-quality data from genetic algorithms and priority dispatching rules.