A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs

最近几年，越来越多的研究采用深度强化学习（Deep-RL）来推导解决图上组合优化（CO）问题的启发式算法。在这一领域中，最大覆盖问题（MCP）及其在社交网络上的概率变体——影响最大化（IM）——尤为突出。本文提出了一项全面的基准研究，深入探究了五种最近用于MCP和IM的Deep-RL方法的有效性和效率。这些方法发表在顶级数据科学会议上，分别为S2V-DQN、Geometric-QN、GCOMB、RL4IM和LeNSE。我们的发现表明，在各种情况下，懒惰贪心算法始终优于所有Deep-RL方法用于MCP。在IM的情况下，理论上可靠的算法，如IMM和OPIM，在大多数情况下表现优于Deep-RL方法。值得注意的是，在IM问题中，当影响传播几乎不随预算增加而增加时，Deep-RL方法略优于IMM和OPIM，这是一种异常现象。此外，我们的实验结果突出了将Deep-RL方法应用于MCP和IM的实际设置时的常见问题。最后，我们讨论了改进Deep-RL方法的潜在途径。我们的基准研究揭示了当前深度强化学习研究在解决组合优化问题方面可能面临的挑战。

深度强化学习方法在解决组合优化问题上的有效性和效率问题

本文对五种最近的深度强化学习方法在最大覆盖问题（MCP）和影响最大化问题（IM）上的有效性和效率进行了全面的基准研究，并发现在大多数情况下，懒惰贪心算法在MCP问题上优于所有深度强化学习方法，而在IM问题上，IMM和OPIM等理论上可靠的算法在大多数情况下表现优异。

实验结果揭示了在实际应用中应用深度强化学习方法解决MCP和IM问题时的常见问题，并探讨了改进深度强化学习方法的潜在途径。

最近的相关研究包括： 1. Learning Combinatorial Optimization Algorithms over Graphs 2. Reinforcement Learning for Solving the Vehicle Routing Problem with Stochastic Demands 3. Deep Reinforcement Learning for Graph Coloring