用次优示范指导强化学习，提升分支决策效率。
SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch
- 基于价值估计筛选次优示范进行学习
- 在多种MILP问题上表现优于已有方法
- 适合缺乏高质量示范的分支策略学习场景
混合整数线性规划（MILP）求解器主要基于分支定界（B&B）算法，其效率依赖于手工设计的分支启发式。近年来数据驱动方法逐渐兴起，可自动学习这些启发式，但其成功高度依赖高质量示范，而高质量示范需近似最优启发式或耗时采样。本文提出次优示范引导的强化学习（SORREL）来学习分支策略。SORREL通过价值估计选择性地从次优示范中学习，结合次优启发式生成的离线强化学习与自身采样的良好经验自模仿学习。实验表明，该方法在多种MILP问题上均展现出更优的分支质量与训练效率。
原文摘要 · Abstract (English)
Mixed Integer Linear Program (MILP) solvers are mostly built upon a Branch-and-Bound (B\&B) algorithm, where the efficiency of traditional solvers heavily depends on hand-crafted heuristics for branching. The past few years have witnessed the increasing popularity of data-driven approaches to automatically learn these heuristics. However, the success of these methods is highly dependent on the availability of high-quality demonstrations, which requires either the development of near-optimal heuristics or a time-consuming sampling process. This paper averts this challenge by proposing Suboptimal-Demonstration-Guided Reinforcement Learning (SORREL) for learning to branch. SORREL selectively learns from suboptimal demonstrations based on value estimation. It utilizes suboptimal demonstrations through both offline reinforcement learning on the demonstrations generated by suboptimal heuristics and self-imitation learning on past good experiences sampled by itself. Our experiments demonstrate its advanced performance in both branching quality and training efficiency over previous methods for various MILPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。