RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization
This work addresses robustness and scalability issues in combinatorial optimization for applications like statistical physics and social media marketing, though it appears incremental as it builds on existing DQN frameworks.
The paper tackles the limitations of existing deep Q-learning methods for combinatorial optimization, such as over-smoothing and memory inefficiency, by introducing RELS-DQN, which achieves solution values higher than or equal to local search algorithms and prior DQN models while maintaining runtime and memory efficiency.
Combinatorial optimization (CO) aims to efficiently find the best solution to NP-hard problems ranging from statistical physics to social media marketing. A wide range of CO applications can benefit from local search methods because they allow reversible action over greedy policies. Deep Q-learning (DQN) using message-passing neural networks (MPNN) has shown promise in replicating the local search behavior and obtaining comparable results to the local search algorithms. However, the over-smoothing and the information loss during the iterations of message passing limit its robustness across applications, and the large message vectors result in memory inefficiency. Our paper introduces RELS-DQN, a lightweight DQN framework that exhibits the local search behavior while providing practical scalability. Using the RELS-DQN model trained on one application, it can generalize to various applications by providing solution values higher than or equal to both the local search algorithms and the existing DQN models while remaining efficient in runtime and memory.