[RL] Model & Planning

(해당 포스트는 Coursera의 Sample-based Learning Methods의 강의 요약본입니다)

 강화학습을 공부하다보면 state나 action같은 기본 notation만큼이나 자주 나오는 단어가 Model이 아닐까 생각된다. 이전 포스트에서 Monte Carlo method나 Temporal Difference Learning을 다뤘고, 이 둘의 차이가 여러가지가 있지만, 그래도 넓은 관점에서 보자면 두 알고리즘은 Model이 있냐(Model-based) 없냐(Model-free)로 나눠서 볼 수 있다. sutton 책에 있는 표현을 가져오자면 Model-based RL은 planning에 초점이 맞춰져 있고, Model-free RL은 learning에 중점을 두고 있다. 그럼 여기서 말하는 Model이란 무엇을 말하는걸지 이번 포스트에서 다뤄보고자 한다.

그림 1. Model

 보통 강화학습의 본질은 environment의 dynamics를 이해시키는 것을 목적으로 하는데, Model은 이 dynamics에 대한 knowledge를 저장한 요소를 말한다. 간단하게 말하면 pure한 environment까지는 아니더라도, 나름의 reward function과 state transition을 통해서 next state와 받은 action에 대한 reward를 agent에게 전달해주는 역할을 한다. 그래서 앞에서 잠깐 이런 Model을 활용한 학습법인 Model-based RL은 planning에 초점을 맞추고 있다고 했는데, 이때의 Planning은 단어 뜻 그대로 어떤 action을 취하는데 있어, 좋은 reward를 얻게끔 policy를 개선하는 것이다. 이전 포스트에서 설명했던 Policy Improvement가 바로 model을 활용해서 planning을 수행하는 학습법이다. 그래서 Monte Carlo계열의 sampling이 반영된 알고리즘을 Model-based RL이라고 하는 것이다.

그림 2. Model for Planning

 일단 Model-based RL의 특징은 앞에서 말한것처럼 pure environment와 비슷한 Model이 있다는 것이다. 다르게는 Simulator라고 표현하는 것인데, 이를 통해서 실제 experience가 아닌 simulator에 의해서 생성된 experience (Simulated Experience)를 얻어낼 수 있다. 일단 experience가 있다는 것은 일반적인 notation을 가져오면, 어떤 state, action으로 이뤄진 trajectory들이 있다는 것이고, 이를 활용해서 기존의 value function을 update하게 된다. 그러면 update된 value function을 바탕으로 현재의 policy \(\pi\)를 improve하는 것이 대략적인 Planning 과정이 된다. 물론 Planning은 실제 environment와의 interaction은 적게 일어나면서 experience를 쌓을 수 있기 때문에, Sample Efficiency가 Model-free Approach에 비해서 좋다고 볼 수 있다.

 이 Model은 sutton책에 설명되어 있는대로라면 크게 두가지로 나눠볼 수 있다. 하나는 주어진 확률을 가진 data를 sampling하면서 결과를 도출하는 sample model이고, 다른 하나는 주어진 확률을 가지고 조건부 확률 계산 등을 통해서 data의 distribution을 수치적으로 계산하는 distribution model이다. 예를 들어서 동전의 앞뒤를 뽑는 문제가 있다면 sample model은 실제로 동전을 던져서 random하게 나온 앞뒤의 결과를 가져오는 것이 될 것이고, distribution model이라면, (bias가 없는 동전임을 가정했을때) 50%의 앞뒤가 나올 확률을 가지고 원하는 조건에 대한 확률을 계산하는 것이다. Sample model같은 경우는 그냥 결과만 sampling하는 것이므로, 확률을 계산해야 하는 distribution model에 비해서 연산량이 적을 것이다. 물론 distribution model은 sample model의 data에 비해서 특정 사건에 대한 정보도 더 많이 가지고 있겠지만, model의 크기도 주어진 action이나 state에 따라서 상대적으로 커질 수 있다는 점도 고려해야한다.

그림 3. Example of Sample Model

 만약 12개의 주사위를 던지는 문제가 있을때, sample model을 쓴다면 그냥 하나의 주사위를 가지고 12개를 연속으로 던져보면 된다. 여기에는 어떠한 연산도 들어가 있지 않고, 단순히 1~6사이의 값이 랜덤하게 나오는 주사위에 대한 정보만 가지고 있으면 된다.

그림 4. Example of Distribution Model

 그런데 distribution model을 쓰는 경우, 하나의 주사위가 6개의 state를 가지고 있다는 것을 바탕으로 모든 경우에 대해서 고민해봐야 한다. 그래서 위와 동일한 12개의 주사위를 던지는 문제에서는 \(6^{12} \approx 2176782336\)의 경우의 수를 고려해야 한다. 단순히 계산하기 어려운 숫자지만, 이를 바탕으로 sample model에서 얻을 수 없는 전체 distribution에 대한 expectation이나, variance를 구할 수 있다. 

 간략하게 요약하면 Sample model은 앞에서 얘기한것과 같이 주사위에 대한 정보만 활용해서 data를 sampling하기 때문에 모든 state에 대한 정보를 가지고 있을 필요도 없고, 이에 따라서 필요한 memory도 적다. 반면 distribution model을 쓰게 되면, 가지고 있는 방대한 정보를 가지고 정확한(실제에 근사한) expectation이나 variance를 구할 수 있다.

(그럼 sample model에서는 expectation이나 variance를 구할 수 없냐는 궁금증이 생길 수 있는데, sample model에서 distribution model에 준하는 expectation이나 variance를 가지기 위해서는 event 수가 엄청 많아야 한다. 이를 설명한 것이 Law of Large Number (LLN)인데, 관심있으면 찾아보면 좋을듯싶다.)

 일단 앞에서도 소개했지만, Model이 있게되면 Planning이 가능해지고, 이를 통해 simulated된 experience를 생성할 수 있어 sample efficiency가 좋아진다고 했었다. 이런 개념을 이전에 다뤘던 Q-learning에 접목시킨 것이 Q-planning이다. sutton책에서는 매 step마다 table로 저장된 Q value를 sampling해서 그 값을 이용해 update한다는 내용을 담아 Random-sample one-step tabular Q-planning이라는 이름을 달았고, 알고리즘 내용은 다음과 같다. (참고로 Q-learning과도 비교해보았다.)

그림 5. Random-sample one-step tabular Q-planning

그림 6. Q-learning

 Q-planning도 Q value를 update하는 부분에서는 전형적인 Q-learning과 동일하지만, 큰 차이가 있다면 Q-planning에서는 앞에서 다뤘던 sample model을 사용한다는 것이다. model에 random samping된 state과 action만 전해주면, 이에 따른 next_state와 reward는 model이 내보내주므로 이를 활용해서 update할 수 있게 되는 것이다. 

 이렇게 Planning을 하면서 얻을 수 있는 이점은 바로 environment와의 interaction이 없어도 policy를 improve할 수 있다는 것이다. 이 말은 즉, 실제 environment상에서 action을 취하고 얻은 결과로 policy를 하지 않더라도, action이 발생할 주기내에 기존의 experience를 가지고 Q value를 update할 수 있다는 것이다. 마치 사람이 실제 행동하지 않더라도, 머릿속으로 상상하면서 배우는 것과 비슷한 과정이다.

그림 7. Advantage of Planning

 강의에서는 위의 도식표를 소개했는데, 위와 같이 Action과 Learning update 주기가 어느정도 term이 있다면, 그 term 사이에는 기존의 sample model에서 얻을 수 있는 data을 바탕으로 update할 수 있다는 것이다. 물론 model이 부정확할 수는 있어도, 어차피 Q-learning의 특성상 Q-value를 update할때 활용되는 값은 next state에서 뽑을 수 있는 Q-value (\(\max_{a}Q(S', a)\)   )의 maximum 값이므로, 궁극적으로는 improve된 policy로 수렴하게 되는 것을 알 수 있다. 

sutton책에서 이 Planning의 효과에 대해서 간략히 요약한 것에 대해 인용해본다.

This enables planning to be interrrupted or redirected at any time with little wasted compuation, which appears to b a key requirement for efficiently intermixing planning with acting and with learning of the model. Planning in very small steps may be the most efficient approach even on pure planning problems if the problem is too large to be solved exactly.