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.
최근, 심층 강화 학습은 다양한 분야에서 등장하는 조합 최적화 문제를 풀기 위한 새로운 수단으로서 많은 관심을 받게 되었다. 이 논문에서 우리는 이러한 각 조합 최적화 문제의 특성을 고려하여 심층 강화 학습 방법을 개선하는 방법을 다룬다. 특히, 우리는 현 심층 강화 학습이 버거워하는 두 가지의 문제를 다룬다. 그 첫 번째는 아주 많은 숫자의 결정을 내려야 하는 최대 독립 집합 문제이고, 두 번째는 많은 탐험량이 있어야 하는 분자 구조 최적화 문제이다. 이 문제들을 풀기 위하여 우리는 각 문제에 특화된 현존하는 조합 최적화 방법을 심층 강화 학습과 합친다. 이 논문에서는 첫 번째로, 심층 강화 학습이 동시에 여러개의 변수를 결정하는 방법을 연구한다. 두 번째로, 기존의 정답 후보를 변환시켜 새로운 정답 후보를 만드는 특별한 탐험 방법을 연구한다.
