Scaling deep reinforcement learning to large combinatorial optimization

Abstract

Recently, deep reinforcement learning (DRL) framework has gained considerable attention as a new approach to solve combinatorial optimization problems which appear ubiquitously in various scientific fields. We propose to improve the existing DRL frameworks by considering the combinatorial nature of the problems. Specifically, we focus on two important applications with overwhelming difficulties for the current DRL framework: (1) the maximum independent set problem where the number of decisions to be made is prohibitively large, and (2) the molecular optimization problem which requires a vast amount of exploration. To this end, we draw inspirations from the traditional domain-specific algorithms for efficiently exploring the solution space. Namely, we show that existing DRL frameworks can be improved by (1) allowing the DRL agent to decide multiple variables at once and (2) using exploration operators that modify the existing candidate solutions.