用强化学习生成启发式函数，让动态规划搜索更快更准。
Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming
- 用深度Q网络和近端策略优化生成搜索引导策略
- 相同节点扩展次数下，性能显著优于传统方法
- 在四个基准测试中，三组表现超越标准动态规划
领域无关动态规划（DIDP）是一种基于动态规划的组合优化状态空间搜索范式。当前实现中，搜索由用户定义的对偶界引导。强化学习（RL）在组合优化中的应用日益广泛，其与动态规划共享贝尔曼方程和基于状态的转移系统等核心结构。本文提出利用强化学习获取启发式函数以引导DIDP搜索。我们设计了两种基于RL的引导方法：基于价值的深度Q网络（DQN）和基于策略的近端策略优化（PPO）。实验表明，使用RL引导的DIDP在相同节点扩展次数下，显著优于标准DIDP和同规模问题特化贪婪启发式。此外，尽管单个节点评估耗时更长，但在四个基准领域中的三个，其运行时间表现仍优于标准DIDP。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。