Exploratory Combinatorial Optimization with Reinforcement Learning

Abstract

  • 이 논문의 contribution을 먼저 한줄로 요약하고 시작해도 될 것 같습니다. “instead of learning to construct a single good solution, learn to explore for improving solutions.”
  • 기존의 agent는 주로 partial solution에 action이 추가되었을 때, 이를 다시 고려할 수 없는 구조입니다. 이는 한 episode내에서 초기에 내린 결정들에 대해 재조정할 기회가 없다는 뜻인데, 이 논문은 test time동안 기존 partial solution(이미 선택된 node들)까지 고려하여 이를 넣고 빼면서 explore을 할 수 있도록 돕습니다.

Introduction

  • 본문은 MaximumCut problem에 대해 S2V-DQN을 baseline으로 선택합니다. 이 때, 실험들을 통해 S2V-DQN와 비교해볼 때 성능차이가 어느정도 보여졌는데, 이는 agent가 기존에 이미 뽑았던 nodes를 번복할 수 있고 이런 과정을 이용할 수 있는 적당한 정보와 보상을 받을 수 있다는 것에서 비롯한 차이임을 보았습니다. ECO-DQN은 scratch부터 학습할수도 있지만, 다른 method들과도 결합되어 학습할 수 있습니다.
  • Combinatorial Optimization과 network의 결합부터 GNN부터 MCTS에 이르는 연구를 소개합니다.

Background

  • Max-Cut Problem
    • 그래프 G에 대해, nodes를 두 set으로 나눌 때, edge를 최대한 많이 혹은 edge weights가 존재할 때, 이 weights를 최대한 크게 자르는 문제입니다.
  • Q-learning
  • Message Passing Neural Networks

    • 그래프 \(G\)내의 각 vertex \(v \in V\)는 n-dimensional embedding \(\mu^k_v\)을 통해 나타냅니다. 이 때 k는 각 layer에 대한 index입니다. 노드는 먼저 function \(I\)에 의해 d-dimension으로 embedding됩니다.

      \[\mu^0_v= I(x_v), \ \mu^0_v=\mathrm{relu}(\theta_1x_v)\]

      이 때, message function \(M_i\)과 vertex update function \(U_t\)에 의해 각 노드는 update됩니다. 이는 다음과 같습니다.

      \[m^{k+1}_v = M_k(\mu^k_v, \{\mu^k_u\}_{u \in N(v)},\{w_{uv}\}_{u \in N(v)})\] \[\mu^{k+1}_v = U_k(\mu^k_v,m^{k+1}_v)\]

      \(N(v)\)는 node \(v\)의 neighbor nodes입니다. 기본 아이디어는 neighbors로부터 message를 받아 연산하고 이를 vertex를 update하는데 이러한 형태를 띈 GNN를 MPNN이라고 표현합니다. 이 때 MPNN의 architecture는 Appendix에 다루어져있고, 크게 설명할 것은 없어서 차라리 구현물을 링크하겠습니다. 마지막으로 readout function \(R\)은 graph의 표현을 가져오는 역할을 하는데, 다시 말하면 전체 그래프를 나타내는 feature vector를 구하는 역할을 합니다. 이는 논문에서 각 node를 flipping(partial solution에 더하거나 빼는행위)에 대한 Q value를 얻을 수 있으므로 다음과 같이 표현할 수 있습니다.

      \[\{Q_v\}_{v\in V}= R(\{\mu^K_u\}_{u\in V})\]
  • ECO-DQN은 test할 때, solution space를 explore하도록 학습됩니다. 즉 solution으로부터 Q value에 의해 vertex를 추가하고 빼는 행위는 episode내 history의 context가 계속해서 re-evaluated됨을 의미합니다. 이 때 이러한 행위가 꼭 sub-optimal이 된다는 것을 의미하지는 않는데, ECO-DQN을 통해 이를 학습할 수 있음을 보입니다.

Exploiting Exploration

eco_dqn

알고리즘상 별 다른 점은 크게 없고, random solution set으로부터 학습이 시작됩니다. 이 때, 다른 agent가 만들어낸 solution set을 이용할 수 있음을 알 수 있습니다.

  • Reward Shaping
    • Maxcut problem에 대해서 reward는 다음과 같이 어느 시점의 한 state \(s_t \in S\)로 부터 \(\mathcal{R}(s_t) = \max(C(s_t)-C(s^*),0)/ \vert V \vert\)로 정의합니다. \(s^* \in S\)는 지금까지의 최대의 cut value를 가지는 state를 의미합니다. 최소 reward로 0을 줌은 목적이 exploration이므로 cut value가 줄더라도 punishment는 하지않겠다는 의미입니다. \(\gamma = 0.95\)를 사용합니다. 이 때 생각할 수 있는점은 reward가 최대의 maxcut을 가졌을 때에 한번씩 주어지도록 reward가 설계되었는데, 이는 굉장히 sparse합니다. 그렇기 때문에 local optimal(어떤 action도 당장 cut value를 높힐 수 없는 상태)에 대해서도 \(1/ \vert V \vert\)의 reward를 통해 sub-optimal을 찾을 수 있도록 유도합니다. 이는 전체 state를 다 볼 수 없는만큼 agent는 가까이에있는 local optimal로 올라갈 수 있는 능력을 가지게 됩니다.
  • Observations
    • 각 vertex의 Q value는 이 7개의 observation을 통해 계산됩니다.
      • Vertex state : solution set에 속하는지 여부
      • Immediate cut change : vertex state가 바뀌면서 변하는 cut value
      • vertex가 마지막 변경된 후 time step
      • 최대 cut value와 현재의 차이
      • 최대 cut solution set과의 차이
      • 당장 cut-value를 높일 수 있는 action 개수
      • episode에 남은 steps

References