Summary

• ICLR 2020, Tencent AI Lab에서 발표한 논문
• WU-UCT는 MCTS 4가지 단계 중 Selection에서 사용되는 수식
• 기존에 사용되었던 MCTS 병렬화 방법에서 수식만 조금 변경되었음
• 아타리 게임들에 대해 실험해봤을 때 기존 방법들 보다 성능이 좋았음

WU-UCT

• 연구를 하게된 동기: MCTS 병렬화에 대한 연구가 많이없어서 한 번 해봤다고 함 😅
• 설명의 편의를 위해서 바둑이라고 가정

Monte Carlo Tree Search (MCTS)

• WU-UCT를 이해하기 위해서는 MCTS를 알아야함.
• MCTS ? 쉽게 말하면 Tree Search를 이용해 최선의 수를 찾는 방법

Selection

• Selection: 어떤 자식노드로 가볼 지 결정하는 단계

Expansion

• Expansion: 리프노드에서 random한 자식노드를 추가하는 단계

Simulation

• Simulation: 추가한 자식노드에서 게임이 끝날 때까지 랜덤한 자식노드를 추가하는 단계

Backpropagation

• Backpropagation: Simulation의 결과를 업데이트하는 단계

Best Action

• MCTS ? Tree Search를 이용해 최선의 수를 찾는 방법
• 최선의 수: MCTS를 n번 or n시간 동안하고, 방문 횟수가 제일 많은 노드

Cons

• MCTS의 단점: 환경과 상호작용해야 하는 단계가 있으므로 느리다

MCTS parallelizing

• MCTS parallelizing: multi-thread로 MCTS를 수행
• 기존에는 크게 3가지 방법이 있음

Leaf parallel

• Leaf parallel: 모든 thread는 같은 리프 노드에서 simulation을 각자 수행

• 3번째 simulation 단계만 multi-thread로 하는 방법
• 같은 노드에서 시작하더라도, thread 별로 다른 결과가 나올 수 있음
  • simulation은 랜덤하게 자식을 추가하기 때문에

Root parallel

• Root parallel: 각각의 thread는 루트의 서브트리에 대해 MCTS를 각자 수행

Tree parallel

• Tree parallel: 모든 thread는 전체 트리에 대해 MCTS를 각자 수행

• 앞의 2개의 방법처럼 트릭(?)을 쓰지않고
• Virtual loss를 사용하여 모든 thread는 전체 트리에대해 MCTS를 각자 수행

• MCTS 1회가 완료되면 Virtual loss (VL)를 다시 감소시킴

Cons

• 기존 방법들이 가지는 문제점: Exploration or Exploitation이 불완전하다.
• Leaf parallel: 같은 리프노드를 모든 스레드가 시뮬레이션하므로 Exploration이 불완전
• Tree parallel
  • Virtual loss를 이용해서 다른 thread가 작업중이면, 그쪽으로는 덜 가도록 함
  • Selection value가 아무리 좋아도 누가 처리하고 있으면, 그 쪽으로는 덜 가게됨
  • 어떻게 보면 Exploration은 만족하지만, Exploitation이 부족하다고 볼 수 있음
• Root parallel
  • 논문에서 언급은 없었지만
  • 아마 루트에서 Selection하는 단계가 없어서, Exploration도 Exploitation도 이루어지지 않는 것으로 보아서 불완전하다라고 생각됨

WU-UCT

• WU-UCT: Tree parallel 방법에서 Virtual loss를 V가 아니라 U에 적용하는 방법

• Watch the unobserved (WU)의 의미를 생각해보면 ..
  • = 관측되지 않은 것을 본다
  • = 시뮬레이션이 덜 끝난 것을 Virtual loss로 표시해둔다

Experiments

• 1 thread 성능 vs n threads (parallelizing) 성능

  • 성능(같은 시간 기준): 1 thread < n threads
  • 성능(같은 MCTS 횟수 기준): 1 thread > n threads

• 아타리 게임 15개에 대한 실험 결과 (3회, 평균 리워드)
  

  • metric은 명시되어있지 않았지만, 기존 알고리즘들에 비해 성능 향상이 있다고 함

Reference

• ✔ 논문, ICLR 2020 온라인 포스터 세션: https://iclr.cc/virtual_2020/poster_BJlQtJSKDB.html
• 후속 논문 BU-UCT: https://arxiv.org/pdf/2006.08785.pdf