投影潜在强化学习动作：迈向通用的、可扩展的图组合优化

arXiv:2605.19721v1 公告类型：新 摘要：图组合优化（GCO）日益受到关注，因为许多NP难问题自然可以表示为图的形式，但其组合爆炸使得精确方法在计算上难以处理。近期强化学习（RL）与图神经网络（GNN）的结合显著改进了基于学习的GCO求解器。然而，现有方法在跨不同图实例的泛化能力以及随着动作空间增长的计算可扩展性方面存在局限性。为应对这两项挑战，我们引入了投影智能体，这是一种新颖的RL-GCO方法，它直接在连续的基于GNN的动作嵌入空间中运行，通过单次前向传播预测期望的潜在动作，随后将其解码为有效的离散动作。此外，通过共享的观测和动作嵌入空间，我们实现了RL方法之间的公平比较。在多个基准测试中，我们的方法仅使用简单的最近邻解码，推理速度比现有解决方案快达16.2倍，泛化能力提升高达40%，同时为具有多个相互依赖变量的超线性决策空间中实现强大的RL性能打开了大门。最后，我们发布了LaGCO-RL，一个自动构建潜在动作空间并支持现有RL-GCO解决方案的Python库，促进了可复现性及对新GCO基准的适应。