본문 바로가기

Reinforcement Learning/Contents

[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.으로 근사할 수 있습니다. 이를 식으로 나타내면 아래와 같습니다.


(s)는 total episode동안 state s를 방문한 횟수, 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/nstep-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



'Reinforcement Learning > Contents' 카테고리의 다른 글

[Ch.7] Off-Policy Control  (3) 2018.01.22
[Ch.6] Temporal Difference Methods  (4) 2018.01.18
[Ch.5] Monte-Calro Methods  (16) 2018.01.01
[Ch.4] Dynamic Programming  (8) 2017.12.28
[Ch.3] Bellman Equation  (3) 2017.12.24
[Ch.2] Markov Decision Process  (5) 2017.12.16
  • 비밀댓글입니다

    • 답변이 늦었습니다! 요즘 계속 진로 고민도 있고 여러 시도도 해보느라 블로그 관리에 소홀해 졌네요. 우선 좋은 피드백 감사합니다! 수정해주신 부분 반영하여 accuracy가 올라간 것을 확인하였습니다.

      블로그에 오셔서 시간 내주셔서 피드백 주셔서 감사합니다

    • 궁금 2019.12.18 08:09 댓글주소 수정/삭제

      소스코드 중 아래 부분에서 reversed는 왜 해주는 것인가요? 게임이 종료된 시점부터 역순으로 Reward 및 Value를 계산하던데 정방향 (0.0)부터 시작하면 안되나요?

      for sample in reversed(self.memory):

  • 비밀댓글입니다

  • 감사합니다 2019.02.19 09:50 댓글주소 수정/삭제 댓글쓰기

    혼자 공부하던 중 이해가 안되서 너무 힘들었는데 좋은글보고 시원하게 해결하고 갑니다~ 감사합니다~^^

  • asdf 2019.04.16 11:02 댓글주소 수정/삭제 댓글쓰기

    안녕하세요 너무 좋은 블로그 포스팅 감사합니다 :) 설명을 너무 잘 해 주셨어요.
    다름이 아니라, value funtion update 유도 하는 부분에서 <fig2> 부분 아래에 있어서
    '그리고 이 식을 조금 고쳐쓰면 다음과 같은 관계를 얻을 수 있습니다.' 라는 말의 아래 2번째 식이
    1/n(G_n + (n-1) * V_n) 이 오타가 난 것 같아서 댓글 달아봅니다. ㅎ

    • 반갑습니다:) 우선 도움이 되었다고하니 감사합니다 ㅎㅎㅎ

      오타가 났다고 하시는 부분(아래서 두번째 식)은 바로 위에 있는 식의 (n-1)Vn부분을 전개한 후 정리한 것입니다. n*Vn -Vn

      혹시 제가 잘못 이해한 부분이 있나요?

    • asdf 2019.05.01 10:31 댓글주소 수정/삭제

      아 넵 그부분은 맞는것 같습니다!

      제가 말하는 부분은 아래 2번째 식 (=아래에서 4번째) 식 전개부분 등호를 따라가는 부분에서 의문이 생겼습니다. :)
      위에 설명하신대로 V_n+1 = sigma(i = 1, n) G_i / n 에 의해서
      V_n = sigma(i = 1, n-1) G_i / (n - 1)인데,
      V_n = sigma(i = 1, n-1) G_i 이렇게 전개된것 같아 등호 부분이 맞지 않는것 같았습니다 ㅎㅎ

    • 아아 맞습니다 말씀해주신 "아래에서 4번째 식"이 잘못되었네요

      V_n 앞에 붙은 n-1을 없애야할 것 같습니다.

      이 부분을 아에 삭제하고 바로 아래식으로 유도되는거로 생각해주시면 되겠네요.

      고쳐놓겠습니다. 좋은 피드백 감사합니다 :)

  • abc 2019.11.09 08:47 댓글주소 수정/삭제 댓글쓰기

    좋은 글 감사합니다. 다른 책 보고 있는데 잘 이해가 안되고 있었는데 조금은 이해가 갑니다.

    예제에 대해 질문이 있습니다.
    예제에서 최종적으로 얻은 value function이 아직 수렴되지 않은 것이지요?
    프로그램에서 출력된 value function대로 하면 골을 찾지 못하는 것 같습니다. 예를 들어 [0,0]에서 시작한다면 다음 state는 주변에서 가장 큰 값을 가지는 아래 칸[1,0]으로 가게되고, 다음에는 다시 위 칸[0,0]으로 가게됩니다. 즉 무한 반복을 하게 될 것 같습니다.

  • synops 2019.11.15 17:26 댓글주소 수정/삭제 댓글쓰기

    마지막 작성하신 코드에서
    memory를 reversed하게 반복하면서 visit되었으면 action value func를 update하지 않으시는데
    뒤에부터 조사하면 first visit이라고 할수 있나요? 최초에 등장한 state가 아니라 가장 마지막에 등장한 state의 기대값으로 업데이트를 할것같은데
    first visit이 꼭 첫번째가 아니라 에피소드 안에서 state가 등장한걸 1번만 고려하면 성립하는건가요?

    • 생각해보니 episode를 뒤집어서 reversed로 tracking하면, first-visit이 아니게 되는군요 정방향으로 value를 계산하는 것이 맞다고 생각합니다.

      다만 first-visit의 의의가 단순히 하나의 value값을 찾는 것에 의의가 있다면 reversed로 한 last-visit(임의로 명명하겠습니다)은 똑같이 하나의 value값을 찾되, 최근 방문한 value가 더 가치있다고 생각할 때 사용하면 좋을 것 같네요.

  • 궁금 2019.12.18 10:50 댓글주소 수정/삭제 댓글쓰기

    윗 질문과 유사한건데, reversed 방식으로 Value 계산을 하는 이유가 있나요? (0,0) 시작점부터 Discount 해서 Value 계산하는 것과 차이가 있는지 궁금합니다.