참고한 책 : Reinforcement Learning: An Introduction, 2nd edition (Richard S. Sutton, Andrew G. Barto)
개요
책의 챕터 8 은 Planning and Learning with Tabular Methods로 주로 planning, learning, model-based 등에 대한 내용을 다룬다. 먼저 model은 환경에 대한 정보라고 할 수 있는데, 문제가 MDP로 표현된 경우 dynamics function p로 나타낼 수 있다.
(dynamics function p, 한 time step이 지나가면서 state s에서 s'로 transition할 때 어떤 action a가 관여하고, s' 시점에서 environment로부터 어떤 reward r을 받을 확률에 대한 정보를 담고 있음.)
앞선 챕터들에서 나온 Bellman equation, dynamic programming은 model에만 의지해 다음 s' 및 r 정보를 가져와 계산한다. 이처럼 Model로부터 받은 정보로만 value function, policy를 계산하는 것을 planning이라 한다. 반면 Monte carlo 방식처럼 model의 도움 없이 직접 환경에 부딪히면서 직접 샘플한 정보에 기반해 value function, policy를 계산하는 것을 learning이라 한다.
실제 문제를 풀 때는 이상적인 model이 먼저 주어지지 않을 것이기에 어떻게든 환경에 대한 정보를 얻어내 model에 축적해야 하고, 이러한 model에 기반해서 planning해야 할 것이다. 이러한 방식을 model-based RL이라 할 수 있다.
p133, sutton and barto, Relationships among learning, planning, and acting.
책에서 소개되는 Dyna-Q 알고리즘은 direct RL을 통해 learning 하고, model을 업데이트 하고, 업데이트된 모델로 planning도 하는 구조이다.
p135, sutton and barto, Dyna-Q algorithm
단지 경험으로부터만 value function을 개선하는 것이 아니라 개선된 model로부터 planning을 통해 한 발자국 더 생각해보고 한번 더 value function을 개선하는 것이다.
Planning at decision time
8.8 챕터 제목은 Planning at Decision Time이다. 위에서 소개했던 planning은 value function이나 policy를 개선하기 위해 쓰였다. 위와 같이 planning이 쓰이는 경우를 background planning이라고 한다. 한편, action을 선택해야 하는 시점에도 planning을 할 수 있다. 이를 decision-time planning이라 한다. 그 예시로 Rollout 알고리즘과 Monte Carlo Tree Search를 소개한다
Rollout algorithm
Rollout 알고리즘은 마치 챕터 5의 Monte carlo control과 유사하게 policy를 따라 episode 끝까지 달려보고 trajectory의 return들을 평균내는 동작을 한다. 하지만 Monte carlo control처럼 이를 value function이나 policy를 업데이트하는데 사용하지는 않는다. 특정 state에서 기존 policy를 그대로 따르는 대신 가능한 action들의 가치를 monte carlo하게 재본 뒤에 그를 따르는 것이다. 그러면 마치 improve된 policy를 따르는 것과 같은 효과가 난다.
Monte Carlo Tree Search(MCTS)
MCTS는 강화된 방식의 Rollout 알고리즘의 일종이다. MCTS는 효율적으로 tree search를 할 수 있게끔 몇가지 단계를 거치고 나서 Rollout 알고리즘을 사용해서 본래 policy보다 좋은 action을 선택할 수 있게 한다. 알파고 및 그 이후 연구들에서도 사용된 방식이다. 첫번째 단계는 Selection 단계로, 탐색할 트리 노드를 찾아 뻗어나가는 초기 단계이다. 뻗어나갈 노드는 가치에 따라 greedy하게 선택, 방문 횟수에 따른 선호 등을 섞어서 효율적으로 선택된다. 두번째는 Expansion으로, 앞서 뻗어나간 끝의 노드에서 child node를 추가한다. 선택 방식은 selection과 다를 수 있다.
p154, sutton and barto, Selection and expansion stage of MCTS
그리고 Simulation단계에는 rollout policy에 따라 Monte carlo하게 policy를 따라 episode 끝까지 계산해서 return들의 합을 계산한다. Rollout policy는 빠르게 실행가능한 단순화된 policy를 사용하는 경우가 있다. 마지막으로 Backup 단계에서는 simulation해서 얻은 값을 반영하기 위해 앞선 단계들에서 거쳐온 edge들을 거꾸로 올라가며 edge들의 정보를 업데이트한다.
p154, sutton and barto, Selection and expansion stage of MCTS
그리고 Simulation단계에는 rollout policy에 따라 Monte carlo하게 policy를 따라 episode 끝까지 계산해서 return들의 합을 계산한다. Rollout policy는 빠르게 실행가능한 단순화된 policy를 사용하는 경우가 있다. 마지막으로 Backup 단계에서는 simulation해서 얻은 값을 반영하기 위해 앞선 단계들에서 거쳐온 edge들을 거꾸로 올라가며 edge들의 정보를 업데이트한다.
p154, sutton and barto, Simulation and backup stage of MCTS
이러한 MCTS는 알파고에서는 최종적으로 시합을 할 때 사용되었다. 반면 알파고 제로 이후 연구에서는 MCTS를 시합때 사용할 뿐 아니라 policy improvement operator로도 사용하였다. 이는 제로 계열 알고리즘들이 강력해진 이유이다.
댓글
댓글 쓰기