Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming

📄 arXiv: 2503.16371v2 📥 PDF

作者: Minori Narita, Ryo Kuroiwa, J. Christopher Beck

分类: cs.AI, cs.LG

发布日期: 2025-03-20 (更新: 2025-05-13)

备注: 24 pages, 4 figures, to be published in CPAIOR 2025 (https://sites.google.com/view/cpaior2025)

💡 一句话要点

提出基于强化学习的启发式方法，指导领域无关动态规划搜索

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

关键词: 强化学习 动态规划 组合优化 启发式搜索 深度Q网络 近端策略优化 领域无关 状态空间搜索

📋 核心要点

  1. 领域无关动态规划(DIDP)依赖人工设计的对偶界限引导搜索，缺乏自适应性。
  2. 利用强化学习(RL)学习启发式函数，指导DIDP搜索，提升搜索效率和自适应性。
  3. 实验表明，基于RL的指导方法在节点扩展数量相同的情况下，优于标准DIDP和贪婪启发式方法。

📝 摘要（中文）

领域无关动态规划(DIDP)是一种基于动态规划的状态空间搜索范式，用于组合优化。目前，DIDP的实现依赖于用户定义的对偶界限来指导搜索。强化学习(RL)越来越多地应用于组合优化问题，并且与动态规划共享几个关键结构，例如贝尔曼方程和基于状态的转换系统。本文提出使用强化学习来获得启发式函数，以指导DIDP中的搜索。我们开发了两种基于强化学习的指导方法：使用深度Q网络的基于价值的指导和使用近端策略优化的基于策略的指导。实验表明，基于强化学习的指导显著优于标准DIDP和具有相同节点扩展数量的特定于问题的贪婪启发式方法。此外，尽管节点评估时间较长，但在四个基准领域中的三个领域中，强化学习指导比标准DIDP实现了更好的运行时间性能。

🔬 方法详解

问题定义：论文旨在解决领域无关动态规划（DIDP）中，依赖人工设计的对偶界限来指导搜索，导致搜索效率不高的问题。现有方法的痛点在于，人工设计的启发式函数难以适应不同问题，且缺乏自适应性，限制了DIDP在复杂组合优化问题中的应用。

核心思路：论文的核心思路是利用强化学习（RL）来自动学习一个启发式函数，该函数能够指导DIDP的搜索过程。通过将DIDP的状态空间视为RL环境，将搜索过程视为智能体的行为，利用RL算法训练一个能够预测状态价值或选择最优动作的策略，从而更有效地探索状态空间。

技术框架：整体框架包括两个主要部分：DIDP搜索框架和RL指导模块。DIDP框架负责状态空间的搜索和动态规划的计算。RL指导模块则负责提供启发式信息，指导DIDP选择下一步要扩展的状态。具体流程是：DIDP在搜索过程中，遇到需要选择下一个状态时，会向RL指导模块查询每个状态的价值或策略，然后根据RL的输出选择最优状态进行扩展。论文提出了两种RL指导方法：基于价值的指导（使用DQN）和基于策略的指导（使用PPO）。

关键创新：论文的关键创新在于将强化学习与领域无关动态规划相结合，利用强化学习的自学习能力来提升动态规划的搜索效率。与传统的基于人工设计的启发式函数相比，基于强化学习的启发式函数能够自动适应不同的问题，并且能够学习到更有效的搜索策略。此外，论文还提出了两种不同的强化学习指导方法，并对它们的性能进行了比较。

关键设计：在基于价值的指导中，使用深度Q网络（DQN）来估计状态的价值函数。DQN的输入是DIDP的状态表示，输出是每个动作（即选择哪个状态进行扩展）的Q值。DQN的训练目标是最小化贝尔曼误差。在基于策略的指导中，使用近端策略优化（PPO）来学习一个策略，该策略直接输出在给定状态下选择每个动作的概率。PPO的训练目标是最大化累积奖励，同时限制策略更新的幅度，以保证训练的稳定性。论文中，奖励函数的设计至关重要，通常与搜索的效率和解的质量相关。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，基于强化学习的指导方法在节点扩展数量相同的情况下，显著优于标准DIDP和特定于问题的贪婪启发式方法。具体来说，在三个基准领域中，基于强化学习的指导方法比标准DIDP实现了更好的运行时间性能，尽管节点评估时间较长。这表明强化学习能够学习到更有效的搜索策略，从而减少了需要探索的状态数量。

🎯 应用场景

该研究成果可应用于各种组合优化问题，例如旅行商问题、调度问题、资源分配问题等。通过强化学习自动学习启发式函数，可以显著提升动态规划的搜索效率，降低人工设计的成本，并有望解决传统方法难以处理的复杂问题。未来，该方法可以进一步扩展到其他搜索算法和优化问题中。

📄 摘要（原文）

Domain-Independent Dynamic Programming (DIDP) is a state-space search paradigm based on dynamic programming for combinatorial optimization. In its current implementation, DIDP guides the search using user-defined dual bounds. Reinforcement learning (RL) is increasingly being applied to combinatorial optimization problems and shares several key structures with DP, being represented by the Bellman equation and state-based transition systems. We propose using reinforcement learning to obtain a heuristic function to guide the search in DIDP. We develop two RL-based guidance approaches: value-based guidance using Deep Q-Networks and policy-based guidance using Proximal Policy Optimization. Our experiments indicate that RL-based guidance significantly outperforms standard DIDP and problem-specific greedy heuristics with the same number of node expansions. Further, despite longer node evaluation times, RL guidance achieves better run-time performance than standard DIDP on three of four benchmark domains.