강화학습 - tree policy 와 MCTS

이번 포스팅에서는 MCTS에 대해서 본격적으로 알아보겠습니다. MCTS는 기본적으로 state이 주어질 때 그에 맞게 action을 선택하는 알고리즘입니다. 하지만 기본적으로 이 알고리즘은 learning algorithm이 아닌, search algorithm입니다. 하지만 "learning 하는 것 같이" 지식을 축적해가면 보다 더 있음직한 미래의 경우의 수만 살펴보게 됩니다. 이와 같이 어떻게 추려나가 효율적인 선택을 하는지 본론에서 보겠습니다.

 

---

개요 - MCTS의 한 loop를 구성하는 4개의 연산들

MCTS 알고리즘의 한 호출은 기본적으로 제한된 resource가 모두 소모될때까지 아래의 연산들을 차례로 연산해가며
partial tree를 계속해서 구성해 나갑니다.

1. Selection 
2. Expansion
3. Simulation/rollout
4. Backup/Backpropagation

1,2 연산은 Tree policy를 통해서 수행되고 "보다 더 있음직한 Search tree를 구성하는데에 핵심적인 역할을 하는"연산입니다. 3의 연산은 Default policy에 의해서 일어납니다. 그리고 4의 연산은 simulation으로 일어난 결과를 지금껏 구성해온 partial tree에 반영해 주는 연산입니다. 이제 좀 더 자세히 살펴보겠습니다.

 

---

TreePolicy - Selection 및 Expansion 연산 

우선 위에서도 잠깐 언급했지만, 이 트리를 구성하는 노드에는 어떠한 값들이 적혀집니다. 그리고 그 값들을 이용하여 "어떤 값을 계산"할 수도 있죠. 우리는 각 트리에는 기본적으로 딱 2가지의 노드만을 사용할겁니다. 바로

1. 해당 노드를 몇 번 방문했는지
2. 현재 loop까지 "해당 노드를 방문함으로써" 총 누적 "점수" 또는 utility 값

을 적어놓습니다. 그리고 이 두가지 값을 활용하여 UCB1 값을 계산합니다. 생뚱맞게 갑자기 웬 UCB1이라는 식이 등장합니다. 그 이유는 단순합니다. Multi-armed-problem을 해결하는 방법 중 하나로 제안된 것 중의 하나가 바로 이 UCB1값을 최대화 하는 방향으로 action을 취해나가는 것이었습니다. 그 값을 최대화시킴으로써 강화학습의 고질적인 문제인 Exploitation과 Exploration사이에서 적절히 균형을 잡아나갈 수 있기 때문입니다.

 

그럼 UCB1 값이 어떻게 계산이 되는지를 알아보겠습니다.

argmax의 피연산자가 UCB1값입니다.

왼쪽 항을 볼까요? 해당 노드 v'을 방문한 횟수로 v'을 방문함으로써 쌓인 총 누계점수입니다. 지금까지의 iteration동안의 sample결과를 통하여 추정된 해당 노드 v'의 평균적인 점수라고 할 수 있겠습니다. 우측 항의 값을 살펴볼까요? 공통된 parent node v에 대해서 루트 안의 분자값인 ln(N(v))값은 변하지 않습니다. 대신 분모의 값이 변하죠. 우리는 여기서 N(v')의 값이 0일때 해당 노드 v'의 UCB1값을 양의 무한대 값이라고 생각해도 되겠습니다. 이는 Expansion 연산에 의해 잘 설명됩니다. 아무튼, 우측의 값은 방문횟수가 작으면 작을 수록 큰 값을 갖게 됩니다. 따라서 두 항을 더한 값을 최대화 한다는 것은,

1. 이 노드를 방문함으로써 평균적으로 기대되는 점수가 높은 곳으로 가거나,
2. 아직 방문 횟수가 적은 곳으로 가게 됩니다.

즉 위에서 언급한 "Exploration vs Exploitation" 문제를 어느정도 잘 해결할 수 있게 되는 것이죠.

 

이 Selection연산은 순전히 Tree policy를 기준으로 실행됩니다. 그리고 단 1만큼의 깊이만 partial tree를 들어가는 것이 아니라, UCB1을 최대화 하는 방향으로 구성해놓은 partial tree의 leaf노드에 도달할때까지 깊이 들어갑니다. 이는 그만큼 "여러 수 앞을 더 내다본다는 것입니다"

 

TreePolicy 알고리즘 - Selection연산과 Expansion 연산을 수행하고 있다.

fully expanded 되었다는 것은 그 해당 노드에 도달하였을 때 그 노드(state)에서 취할 수 있는 모든 action들 중 아직 취해보지 않은 action이 없다는 것입니다. 이런 expansion연산은 위에서 말한 N(v')=0일 경우 UCB1(v') 값을 양의 무한으로 계산한다는 것과 일맥상통합니다. 왜냐면 반복문안에서 굳이 조건문을 자꾸 확인해가며 가능한 fully unexpanded 노드에서 멈춰 아직 취해보지 않은 action을 취하여 새로운 child 노드를 추가하려 하기 때문입니다.

Default Policy - sampling

1,2의 연산을 통해 새로운 노드를 추가한 후에, 그 새롭게 추가된 노드에서 고정된, 아주 값싼 computational cost를 갖는 policy를 통해 terminal state까지 sample을 추출합니다. terminal state이기때문에 utility값이 발생할 겁니다. 이 utility값을 잘 기억해둡니다.

 

Backup, Finally

샘플된 값이 있다면 우리는 이것을 이용하여 보다 더 정교한 추정치를 계산하는데에 사용하겠죠? 해당 loop에서 Tree Policy를 통하여 root node에서부터 시작하여 새롭게 추가된 노드까지 traverse를 하였습니다. 해당 path에 존재하는 각각의 노드들에 sample에서 발생한 utility값을 이용하여 백업해나갑니다.
노드에 꼭 저장하는 값 두가지, Q값과 N값입니다.

있음직한 경우의 수 - 나도 상대방도 합리적으로 게임을 플레이할때 !

가장 원론적으로는 P차원 utility값을 더해나가는 것이 정석입니다. 하지만 우리는 지금 two player, zerosum게임을 하고 있습니다. 그렇기 때문에 벡터보다는 스칼라의 utility를 활용해보겠습니다. 편의상 게임에서 발생한 저의 utility 또는 점수 값이라고 하겠습니다. 방법은 NEGAMAX와 매우 유사합니다.

zerosum 게임을 하고 있기때문에 상대방은 내 이익을 최소화하는 방향으로 행동을 택한다고 하였습니다. 가장 기본 backup연산에서와 같이 그냥 더하지 말고, 대신에 alternating하게 부호를 바꾸어 가며 utility값을 더하면 됩니다. 왜냐면 잘 생각해보세요. 게임에서 제가 이겨서 제가 플레이한 게임 수에 대응하는 노드에 점수를 더하는건 말이 됩니다. 하지만 상대편은 졌습니다. 그리고 제로썸이라고 했죠. utility값의 합이 상수이기만 하면 됩니다만 그 상수값을 0으로 한다면 말이 되죠? 아무튼 그렇게 alternating하게 여러번 백업연산을 해왔다면, 제 턴의 게임 state에는 제 utility값이 그대로 더해나가지면 됩니다. 하지만 상대편의 경우 반대 부호의 utility값을 더해나간 값이죠. 그리고 treepolicy는 그 값을 최대화 하는 방향으로 selection을 취할거고요(엄밀하게 말하면 아니지만 대충 넘어가겠습니다). 그렇다면 음의 부호를 취한 값을 최대화 한다는 것은 사실 원래부호의 그 값을 최소화 하겠다는 말입니다. 즉, 상대편의 턴의 게임 state을 지나갈때, 기대되는 평균적인 점수값을 최소화 하는 방향으로 aciton을 취하겠다는 것이죠.

 

알고리즘이 종료되면?

MCTS알고리즘이 timelimit을 넘기면 하던 loop를 마저 마치고, 구성해놓은 partial tree를 근거로 하여 가장 합리적인 연산을 합니다.

 

이 연산에서는 BESTCHILD의 argument를 v=rootnode, c=0으로 줍니다. 즉, 해당 partial tree의 child node들 중에서 
가장 평균적으로 큰 점수를 갖는 방향으로 action을 취하는, greedification을 마지막으로 행하겠다는 것입니다.

 

이 알고리즘이 종료되면 가장 기본적인 MCTS 알고리즘에서는 지어놓은 partial tree를 허물어버립니다. 
하지만 David Silver가 Sutton의 책 Reinforcement Learning : Introduction 에서 코멘트를 남기기를, 실용적으로는 트리를 다 허물진 않고, 만들어놓은 tree중, 써먹을 수 있는 subtree는 그대로 가져와 써먹는다고 합니다. 

---

오늘은 이렇게 저와 함게 MCTS 알고리즘을 이루는 핵심 연산 4가지에 대해서 알아보았습니다.

그리고 각 연산에서 찾아볼 수 있는 MCTS가 갖는 강점, 특히 "있음직한 수들을" 미리 시뮬레이션 돌려봄으로써 합리적인 판단을 하고, 또 해도 되지 않는 시뮬레이션의 양을 줄여나가는 computation cost를 줄여나간다는 의의를 갖는 다는 점을 함께 확인해보았습니다. 

다음 포스팅에서는 더 유익한 정보로 찾아뵙겠습니다. 감사합니다.