[Ch.5] Monte-Calro Methods

 

 

 이전 포스팅에서는 bellman eqn.을 이용한 dynamic programming, policy iteration과 value iteration에 대해 알아보았습니다. 하지만 DP는 우리가 machine learning에서 다루는 learning이 아니라 planning입니다. 따라서, 계산복잡도가 state의 크기 3제곱에 비례하기때문에 grid world보다 차원의 크기도 크고 state가 무수히 많은 실제 문제에 적용하기에는 많은 한계가 있습니다. 이를 보완한 것이, env.의 model을 몰라도 trial and error를 시행해보며 env.과 상호작용을 통해 알아가는, 강화학습입니다. env.으로부터 model을 learning하는 것입니다. 그래서 강화학습은 full-width backup이 아닌 sample backup입니다. sample backup은 이어지는 모든 state들을 고려하지 않고 그 중에서 sampling을 통해 한 길만 선택해서 가보는 것입니다. 그리고 이를 통해 value func.을 update하게 됩니다. 

 

 DP에서도 마찬가지로 강화학습에는 선택된 정책을 따를 때의 value func.을 sample backup으로 구하는 prediction과 이를 통해 policy를 update하는 control이 있습니다. prediction의 종류에는 Monte-Carlo prediction과 Temporal difference prediction가 있고 control에는 SARSA와 Q-learning이 있습니다. 이번 포스팅에서 다룰 내용은 Monte-Calro Method으로 어떻게 prediction과 control하는지에 대해 다루겠습니다.

 

---

Monte-Carlo Method

 Monte-Carlo Approximation

 Monte-Carlo의 기본적인 concept을 이해하기 위해 이 방법으로 원주율을 구하는 예제를 먼저 설명하겠습니다.

방법은 이렇습니다. 

 

1) (0,0), (0,1), (1,0), (1,1) 로 이루어진 좌표 상에 임의의 점 (x, y)를 sampling한다. 

2) sampling한 점이 중심이 (0,0)이고 반지름이 1인 사분원 내에 속하는 점인지를 판단한다.

3) 이 과정을 충분히 반복한다.

<Fig 1. Estimate π by Monte-Carlo Approx.>

image source : https://en.wikipedia.org/wiki/Monte_Carlo_method

 

 

Indicate func. I는 주어진 조건이 만족하면 1, 아니면 0을 반환하는 함수입니다. Monte-Carlo의 핵심은 "추정하고 싶은 값을 random sampling을 통해 근사한다"정도로 이해하시면 충분합니다. 

 

그러면 강화학습에서의 Monte-Carlo의 의미를 알아보기 위해서, Sutton 교수님 책에서 Monte-Carlo에 대해 언급된 부분을 보겠습니다. 

 

The term "Monte Carlo" is often used more broadly for any estimation method whose operation involves a significant random component. Here we use it specifically for methods based on averaging complete returns

Monte-Carlo는 random한 operation으로 estimate하는 방법이라고 설명하고 있습니다. 그리고 강화학습에서는 complete returns를 averaging하는 것이라고 합니다. 이 뜻은 무엇일까요? 

 

 

 

 

Monte-Carlo Prediction

 Monte-Carlo vs Temporal Differ.

 intro부분에서 prediction의 종류에는 Monte-Carlo 방법과 Temporal difference 방법이 있음을 언급했습니다. 이 둘의 가장 큰 차이는 value func.을 estimate하는 방법(시기)입니다. 전자는 episode가 끝날 때 마다, 즉, state sampling 결과 선택된 state들을 끝까지 가보고 update를 합니다. 후자는 time-step마다 한 단계씩 update합니다. 이렇게되면 Monte-Carlo 방법은 terminal state까지 step별로 얻은 reward를 모두 저장하고나서 terminal state에서는 이를 바탕으로 state들의 value func.들을 구하게 됩니다. 이렇게 Monte-Carlo 방법으로 true value func.을 얻는 과정을 Monte-Carlo Prediction이라고 합니다.

 Monte-Carlo prediction 

 이제 "averaging complete returns"의 의미를 생각하볼 차례입니다. value func.을 얻을 때 agent는 sampling한 state를 골라가며 terminal state까지 갑니다. 그리고 이때 받은 reward들을 저장해두었다가 이를 시간 순서대로 discounting한 것이 바로 value func.입니다. DP에서는 이를 Bellman eqn.으로 구했고 계산가능한 형태로 바꾸어 풀었는데, Monte-Carlo 방법에서는 이 reward들의 합(discounted)의 평균으로 value func.을 근사하게 됩니다. 우리는 MDP를 다룰 때, 미래에 받을 reward들을 현재 가치로 discounting하여 모두 더한 값을 return이라고 정의했습니다. 또한, value func.은 state s에서의 return의 기댓값이라고 정의했습니다. Monte-Carlo prediction은 한 episode를 마치고 얻은 return들의 평균값으로 value func.를 근사하고 이를 반복해서 true value를 찾자는 아이디어입니다. 

 

 

 

<Fig 2. The returns of each states in 1 episode>

 

위 그림은 임의의 policy에 대해 첫 번째 state부터 terminal state까지의 한 episode를 나타낸 것입니다(시간 t에 대한 첨자는 생략했습니다). 그리고 state를 이동할 때마다 얻은 reward들을 통해, 각 state별 return값 G(s)를 구할 수 있습니다. 우리는 이전 포스팅에서 true value func.을 위해서 여러 iteration을 통해 value func.을 update하는 것을 배웠습니다. Monte-Carlo도 마찬가지로 여러 episode를 진행하며 해당 state를 지나가는 episode에서 return값들을 모두 구해서 산술평균을 내줍니다. 이러한 return값들이 episode 반복을 통해 여러 값들이 모이면 true value func.으로 근사할 수 있습니다. 이를 식으로 나타내면 아래와 같습니다.

 

 

N (s)는 total episode동안 state s를 방문한 횟수, G i(s)는 episode i에서 state s의 return값입니다.

 

이 식을 하나의 state에 대해서만 생각해보겠습니다. state에 대한 notation을 없애고 n개의 return값을 통해 얻은 value func.은 Vn+1이라고 쓸 수 있고, 가장 최근 얻은 return을 Gn이라고한다면, 아래와 같이 decompose시킬 수 있습니다. 

 

 

그리고 이 식을 조금 고쳐쓰면 다음과 같은 관계를 얻을 수 있습니다.

 

이 식은 새로운 return값을 받았을 때, Vn에서 Vn+1로 value func.을 update하는 방법을 나타냅니다. 이렇게 return값을 모두 모으고 한번에 평균을 내는 것이 아니라 새로운 return값을 얻을 때마다 update하기 때문에 아래와 같은 incremental mean의 식으로 나타낼 수 있습니다. 

 

여기서 1/n을 step-size라고 하고 보통 α로 놓습니다(이 α를 위 식이 수렴하게 끔하는 constant로 둘 수도 있습니다). 그리고 이에 곱해진 (Gn-Vn)를 오차라고 합니다. 그러면 이를 통해서 우리는 아래와 같이 value func.이 G(s)라는 target으로 (αㆍ오차)만큼 update하여 다가간다는 것을 알 수 있습니다. 다음 포스팅에서 다룰 TD(Temporal-difference) prediction에서도 목표가 G(s)가 바뀔 뿐, 개념은 같습니다.

 

 

<Fig 3. update value func. to return>

 

 First-visit MC or Every visit MC

 하나의 episode를 마치면 episode 동안 진행해왔던 state들 마다 return값이 존재하게 됩니다. 이때, 중복 방문에 대한 return값을 처리하는 방식에 따라 first-visit MC와 every-visit MC로 나누어지는데, first-visit MC는 state에 첫 번째 방문했을 때의 return값만 취하고 두 번째 이후는 고려하지 않습니다. every-visit MC는 이와 반대로 방문할 때마다 바뀐 return값으로 계산하는 것입니다. 두 방법 모두 true value func.으로 수렴하지만 지금껏 다룬 내용은 모두 first-visit MC를 채택하여 다루었습니다.

 

Monte-Carlo Control

DP에서 Policy Iteration은 policy evaluation과 (greedy)policy improvement로 나누어집니다. 여기서 policy evaluation에 MC를 이용하면 Monte-Carlo policy Iteration이 됩니다. 

 

ㆍPolicy Iteration = ( policy evaluation + policy improvement )

ㆍMonte-Carlo policy Iteration = ( MC policy evaluation + policy improvement ) 

 

하지만 MC policy Iteration은 다음과 같은 문제점들이 존재하는데, 이를 해결한 것이 Monte-Carlo Control입니다.

 

 1) Value func.의 model-based

 2) Local optimum 3) Inefficiency of policy evaluation

 

 

MC control은 위 문제점의 solution들을 어떻게 algorithm에 반영하였는지 살펴보겠습니다.

 1) The attribute of value func. : model-based

 MC로 policy evaluation을 하는 부분에서 value func.을 이용합니다. MC를 이용하는 것은 model-free의 속성을 이용하기위해 도입했지만 value func.을 사용하게 되면 policy를 improve할 때, model을 알아야만 합니다. 따라서, value func. 대신에 action-value func.(q-func.)을 이용하면 이를 해결할 수 있습니다. 우리가 Ch.3에서 배운 action-value func.의 식에 model이 있어서, 이 말이 이해가 안가실 수도 있는데 이렇게 생각해보겠습니다. 

 

value-func.을 이용할 경우, agent가 episode마다 얻은 reward들로 state의 return값을 계산하고 이를 평균을 취해 state마다 value func.들을 계산해놓습니다. 이 과정이 MC policy evaluation이고 이를 통해 true value func.을 근사하여 얻을 수 있습니다. 하지만 improve과정에서 policy를 update할 때 아래의 식을 이용하는데 reward와 state transition prob.를 알아야합니다. Ch.4 Policy Iteration의 policy improvement부분에서 q.func.을 이용해서 policy를 update했습니다. 이때, model이 쓰이기 때문에 q-func의 식대로 model 필요한 건 맞습니다.

 

 

action-value func.을 이용할 경우, return이 아닌 agent가 episode마다 random하게 움직이며 얻은 reward들 그리고 state transition prob.를 통해서 action-value func.을 계산할 수 있습니다. 이렇게 되면 policy를 improve할 때, model을 굳이 알지 못해도 이미 전 과정에서 q-func.을 이용함으로써 model의 정보가 다 담겨있습니다. 따라서 improve할 때는 이를 선택만 해주면 되는 문제이므로 model을 몰라도 improve할 수 있습니다. 정리하자면 model-free하다는 개념은 policy를 improve할 때의 관점이고, q-func.자체는 model을 알아야지만 구할 수 있는 것은 맞습니다. 다만 trial and error의 과정 속에서 모든 정보가 q-func.에 담겨있으므로 policy improvement의 과정에서는 model-free합니다.

 2) Local optimum

 Policy를 improve하는 방법으로써 greedy policy improvement를 소개했습니다. 하지만 이 방법은 현 상황에서 제일 좋은 것만 찾는 매우 근시안적인 방법이라 local optimum에 빠지는 경우가 생깁니다. 경사로의 공을 아래로 옮기는 일을 agent가 수행한다고 했을 때, 어떤 t시점에서의 slope가 t-1시점에서의 slope보다 계속 작아지는 쪽으로 옮기는 action을 취하면 됩니다. 하지만, 중간에 움푹 패인 골짜기를 만나게 된다면 더 이상 진행을 못하게 되고, 이 것이 local optimum에 빠진 현상입니다. 그래서 우리는 골짜기의 공을 한번 흔들어서 빼내어 다시 경사로 아래로 굴려줘야합니다. 이 작업을 가능하게 하는것이 ε-greedy policy improvement입니다. ε의 확률만큼 exploration을 하고, 1-ε의 확률만큼 empirical mean, 즉, 지금까지 observe한 것 중의 최적을 택하는 방법입니다. exploration은 현재의 optimal 이외의 다른 무언가를 찾기 위해 random하게 action을 선택하는 것을 의미합니다. 

 

 3) Inefficiency of policy evaluation 

 

 DP에서 Policy Iteration의 과정을 optimal policy라는 전제와 함께 q-func.을 이용하여 단 한번만 evaluation하는, Value Iteration이 있었습니다. 마찬가지로 MC control에서도 MC policy iteration에서의 evaluation을 단 한번만 진행하게 됩니다. 아래 그림은 DP의 Policy iteration과 MC control을 비교한 그림입니다. 왼쪽이 Policy Itearation, Monte-Carlo Control입니다.

 

<Fig 4. Policy Iteration vs Monte-Carlo Control>

 

이제는 https://github.com/rlcode/reinforcement-learning-kr(Ref. [2], [3])에 있는 code를 커스터마이징해서 MC control agent를 구현해보겠습니다. 먼저 환경은 5X5 gird-world로써 아래와 같습니다.

 

<Fig 5. env>

 

초록색 영역을 피해서 Goal state로 가는 환경입니다. agent가 value func.을 table로 저장하고 episode가 끝난 후에 얻은 return값으로 이를 update합니다. 그리고 ε-greedy method를 사용하여 action을 택합니다. 중간중간 episode마다 취한 action을 보면 episode마다 step의 수가 다양합니다. 부연설명은 code에 있는 주석으로 대체하겠습니다.

 

 

마치며

 이번 장부터는 강화학습의 시작이라고 말할 수 있습니다. 하지만, MC의 방법은 episode가 무한히 길다면 update하기 어려운 단점이 존재합니다. 다음 포스팅은 이 문제를 해결할 수 있는 Temporal difference learning에 대해 다루겠습니다.

 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

 

Reference

[1] https://dnddnjs.gitbooks.io/rl/content/monte-carlo_methods.html 

[2] 이웅원, 양혁렬, 김건우, 이영무, 이의령. "파이썬과 케라스로 배우는 강화학습". 위키북스. p.110-124

[3] https://github.com/rlcode/reinforcement-learning-kr/tree/master/1-grid-world/3-monte-carlo