[Review] POMO: Policy Optimization with Multiple Optimafor Reinforcement Learnin

빠르게 아이디어만 보는 걸로 

 

combinatorial optimization의 문제를 풀기 위해서 강화 학습을 적용함.

 

 

조합 최적화에서 일반적으로 NP-hard(Nondeterministic polynomial (NP)) 즉 다항시간내에 풀 수 없는 문제에 적용한다고 한다.

 

NP-Hard는 TSP문제와 같이 모든 경우의 수를 일일히 확인해보는 방법 이외에는 다항식처럼 답을 풀이할 수 없는 문제들을 말한다고 한다. (외판원 문제)

 

 

 

저자는 Policy Optimization with Multiple Optima(POMO)를 도입한다고 한다. 

그래서 여기서는 TSP(Traveling salesman) , capacitated vehicle routing (CVRP),  and 0-1 knapsack (KP).과 같은 문제에 적용해보고 성능 개선이 있다고 한다.

 

CO 같은 경우 운송업이나 제조업 또는 Supply chain과 같은 순차적으로 자원으로 할당할 때 쓰는 중요한 문제다.

많은 제약조건도 있고, 굉장히 어렵기 때문에 현재도 수작업으로 전문가들이 하고 있다고 한다.

 

저자가 말한 기여한점
• We identify symmetries in RL methods for solving CO problems that lead to multiple optima. Such symmetries can be leveraged during neural net training via parallel multiple rollouts, each trajectory having a different optimal solution as its goal for exploration. 

• We devise a new low-variance baseline for policy gradient. Because this baseline is derived from a group of heterogeneous trajectories, learning becomes less vulnerable to local minima. 

• We present the inference method based on multiple greedy rollouts that is more effective than the conventional sampling inference method. We also introduce an instance augmentation technique that can further exploit symmetries of CO problems at the inference stage

 

 

 

 

핵심 아이디어는 위에 그림에서 a group of nodes $v_1, v_2,..., v_m$을 최적화하는 문제이고, 이 문제를 풀기 위해서  타당한 설루션을 만드는 $\theta$를 가진 신경망을 만드는 것이다

해결책 $\tau=(a_1, a_2,..., a_m)$ (node $v_j$를 선택하고 a_i라는 행동을 선택)을 한 번에 하나의 노드를 autoregressively 하게 생성하는 것이다.

 

 

위에 식수에서 이 문제에서 $t$는 node를 의미하고, autoregressively 하게 이전 액션을 반영한 행동을 취하게 하는 policy를 설계한 것 같다.

 

CO 문제는 "아이템의 SET"을 찾는 것이 목적이고, 예를 들어 $\tau^{`}=(v_1, v_2, v_3, v_5, v_4)$와 같이 표현하는 게 최정 결과물이 될 것이다.

 

POMO는 N개의 다른 노드들($a_1^1 , a_1^2 , a_1^3 , a_1^4... , a_1^N$) N개의 샘플 설루션의 경로 ($\tau^1,\tau^2 , \tau^N$)을 샘플링한다. 

$\tau^i = (a_1^i , a_2^i , a_3^i ,.., a_M^i)$

 

저자는 이러한 방식을 취해 rnn이나 transformer 같은 방법론 사용한 거처럼 보인다.

 

 

위에 $a_1$은 시작점을 의미한다고 보면 될 것 같다. 각각의 시작점에서 선택한 행동부터 해서 만들어진 N개의 Trajectoryt를 샘플링하는 방법을 사용

 

 

시작점을 어떻게 하는지 찾기 위해서 일단은 탐색하기 위해서 entropy maximization 하는 것을 적용했다고 한다.

목적함수에 entropy 정규 텀을 줌으로써 에이전트의 시작점을 다양하게 탐색할 수 있게 했다(편향 전략 금지)

 

 

보통 이러한 순차적인 경우에 대해서 목적함수 설계가 궁금했는데, 

일단 보상 함수는 Trajectory 단위로 해서 보상을 측정하는 것을 알 수 있고, 목적함수도 각각의 trajectory들의 기댓값을 최대화하는 방향으로 설계한 것을 알 수 있다. 

즉 여기서의 각각의 값들은 trajetory로 하나의 본 것이 좋았다. 

mini batch로 POMO가 학습되고, BASELINE을 사용하고 있다. 

특이한 점은 각각의 trajectory($\tau^i$에 다르게 할당된 $a_1^i$) 함수가 돼야 하지만, shared baseline을 썼다고 한다. 

머 저렇게 하면 더 적은 분산을 야기할 수 있다고 한다. 

그리고 저런 식으로 shared baseline을 하게 되니까 local minima에 빠지지 않는다고 말하고 있다. 하나씩 보다는 여러 개를 봐야 이질적인 trajectory를 가지는 수가 증가하는 효과가 있다고 저자는 말하고 있다.

 

 

 

 

 

 

 

 

 

 

 

저자의 코드를 보면 reward를 결국에는 다 움직이고 나서 하나의 값만 reward를 사용한 것을 알 수 있다.

근데 저렇게 구성하면 실제로 학습이 되는 건지가 궁금하다... 액션은 어떻게 정의를 해야 하는 건지가 난해해 보인다.

코드를 봤는데, 배울게 많을 것 같다..

 

 

 

inference에서 저자는 2가지 방법을 사용한다고 한다.

1. argmax 방식과 2. sampling 방법이다.

 

실제로 argmax보다 sampling 방법이 더 좋은 결과가 나온다고 한다. 

 

 

 

실험 결과는 다음과 같다.

 

 

 

 

 

 

 

결론

 

이 논문은 순순히 데이터 기반의 강화 학습을 활용한 조합 최적화를 제시하고 있다. 

수많은 해결책이 있는 CO에서 POMO는 레버리지 할 수 있다고 저자는 말하고 있고, 여러 문제에서 평가를 해보고 좋은 성능이 나왔다고 한다.

 

개인적인 생각

 

일단 이 분야에 대해서는 도메인 지식이 많이 부족하여 잘은 모르겠지만, 조합 최적화를 하는 방식에 있어서는 충분히 배울만한 코드도 있고, 방법론이라 생각한다!

 

 

arxiv.org/abs/2010.16011

POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

 

 

github.com/yd-kwon/POMO

yd-kwon/POMO