[Ch.6] Temporal Difference Methods

 이번 포스팅에서는 Ch.5의 Monte-Carlo와 같이 model-free한 방법으로써, Temporal Difference Methods에 대해 다루겠습니다. MC는 한 episode가 끝난 후에 얻은 return값으로 각 state에서 얻은 reward를 시간에 따라 discounting하는 방법으로 value func.을 update합니다. 하지만, atrai게임이나 현실의 문제는 episode의 끝이 무한대에 가깝도록 길기 때문에 episode가 반드시 끝나야 학습을 하는 MC의 방법으로는 한계가 존재합니다. DP처럼 time-step마다 학습하면서 model-free한 방법이 바로 TD입니다. 

 

---

TD Methods

 Sutton교수님 책에서 TD를 아래와 같이 설명하고 있습니다.

 

If one had to identify one idea as central and novel to reinforcement learning, it would 

undoubtedly be temporal-difference (TD) learning. TD learning is a combination of Monte Carlo ideas and dynamic programming (DP) ideas. Like Monte Carlo methods, TD methods can learn directly from raw experience without a model of the environment's dynamics. Like DP, TD methods update estimates based in part on other

learned estimates, without waiting for a final outcome (they bootstrap)

 

 TD는 MC와 DP의 idea를 조합한 방법으로써 MC처럼 model-free하게 raw experience를 통해 learning할 수 있고, DP처럼  episode의 끝을 기다리지 않고 값을 update합니다. 여기서 bootstrap이라는 말이 나오는데, 이 말의 뜻을 알아보겠습니다.

 Bootstrap

 통계학적 관점으로 wikipedia에서는 아래와 같이 설명하고 있습니다.

 

In statistics, bootstrapping is any test or metric that relies on random sampling with replacement. Bootstrapping allows assigning measures of accuracy (defined in terms of bias, variance, confidence intervals, prediction error or some other such measure) to sample estimates.

 

 Bootstrap은 random sampling을 복원추출(with replacement)의 방법으로 가설 검정을 하거나 metric을 구하는 방법입니다. population의 분포에 대한 어떠한 가정도 없이 random sampling을 통해서 모집단의 metric을 추정할 수 있습니다. 우리가 population의 평균을 sample mean을 통해 추정하는 것을 생각해볼 수 있습니다. 

 

 ML 관점에서도 마찬가지로 random sampling을 통해 training set을 늘리는 것을 말합니다. 예를 들어, 0 또는 1, 두 가지 label로 분류하는 classification 문제를 생각해봤을 때, training set에서 이 둘의 분포가 고르지 않다면 model이 충분히 training이 될 수 없습니다. 가령 label이 0인 data가 training set에 압도적으로 많다면 model은 0으로만 분류하도록 학습될 수 있습니다. 이 때 random sampling을 통해 1의 data를 늘려주면 이를 해결할 수 있습니다. label이 0과 1인 data의 수를 비슷하게 sampling한다면(중복을 허용하니까) 1의 data가 0의 scale에 구애받지 않고 학습될 수 있습니다. 

 

 아래 그림은 Silver 교수님의 RL강의자료입니다.

 

 

<Fig 1. Bootstrapping and Sampling>

 

 

 RL 관점에서는 Bootstrap을 추정에 근거한 update라고 설명하고 있습니다. MC의 방법은 episode가 끝나지 않으면 얻은 reward를 통해서 value func.을 추정할 수 없습니다. 그리고 실제 얻은 reward들을 통해서 state들의 value func.을 구하게 됩니다. 하지만 DP나 TD는 이와 달리 time-step별로 이전의 value func.들을 통해 현재 value func.을 추정하게 됩니다. sampling은 model-free한 속성과 관련되어 sample backup과 관련있습니다. DP는 full-width backup backup이므로 이에 해당하지 않습니다. 아래 그림은 DP와 MC, TD에 대해 비교한 표입니다.

 

 

<Fig 2. DP vs MC vs TD>

TD Prediction

 TD(0)

 가장 basic한 TD에 대해서 알아보겠습니다. TD는 MC와 같은 sample backup이면서 time-step마다 update합니다. 아래 식은 MC에서 value func.을 update하는 식입니다.

 

여기서 return Gt는 해당 state에서 episode의 끝까지 얻은 reward들을 시간에 따라 discount한 것입니다. 이 것을 1 step에 대한 것으로 바꾸면 TD(0)가 됩니다. TD에 "(0)"notation이 붙는 이유는 뒤에서 설명하겠습니다. 따라서 TD(0)의 update 식은 아래와 같습니,다. 

 

 

MC와 마찬가지로 Rt+1+γV(St+1)를 TD target, Rt+1+γV(St+1) - V(St) 를 TD error라고 합니다. 즉, 현재의 state의 value func.을 다음 state로 변할 때의 reward와 그 state의 valuf func.를 discounting한 것(TD target)에서 step size, α만큼 update하겠다는 것입니다.

 

TD Prediction의 algorithm은 아래와 같습니다.

 

 

<Fig 3. The Algorithm of TD(0) prediction >

 TD vs MC

 TD와 MC를 예제로 비교해보겠습니다. 직장에서부터 집까지 운전을 하며 가는 episode에 대한 prediction예제입니다. 

 

 

 

<Fig 4. Driving home example>

 

 직장을 출발하고, 차에 도착하여 비가오고, 고속도로를 빠져나가고의 상황을 state로 생각하고 각 state에서 집까지 걸릴 시간이 value func.입니다. 이때 agent는 state에서 다음 state로 이동할 때 실제 걸린 시간을 reward로 간주합니다. agent는 이를 바탕으로 value func.을 update합니다. agent가 total time을 마지막 column처럼 prediction을 하고 이를 바탕으로 state에서의 value func.을 prediction합니다. agent의 prediction total time을 state에 따라 plotting해보면 아래와 같습니다.

 

 

 

<Fig 5. Driving home example>

 

 화살표가 각 state에서 update 대상이 되는, 즉 step size(α)에 곱해지는 error입니다. 이 error를 통해서 value func.을 update하게 됩니다. 여기서 얻어야하는 예제의 교훈은 MC와 TD의 update하는 방법의 차이입니다. MC의 방법을 따르는 agent는 predicted value func.을 update해야하는데, episode가 모두 끝나야 update를 할 도구가 생깁니다. 여기서 도구는 지나온 state마다 얻은 reward를 통해 계산한 return값입니다. 화살표를 보시면 α, γ =1 이라고 할때, 43은 총 걸린 시간이자 reward의 총합이라고 볼 수 있습니다. 그리고 이를 바탕으로 각 state에서 predict한 total time과 비교를 하고 이 error만큼(error에 step size를 곱한만큼) value func.를 update합니다. 이와 달리 TD의 방법을 따를 때는 final outcome을 모르고도 매 step마다 얻은 reward를 바탕으로 update할 수 있습니다. 우리가 운전을 하며 각 상황을 마주했을 때, "생각보다 고속도로를 빨리 나왔네, 10분 일찍 도착할 것 같은데? ",  "고속도로가 막혀서 조금 더 걸리겠는데?"와 같은 prediction을 하는 것과 같다고 생각하시면 될 것 같습니다.

 Bias & Variance

 하지만 TD는 바로 다음 step과의 error만 고려하여 update를 하기 때문에 학습에 시간이 많이 소요되고 학습이 한쪽으로 치우쳐 지게 됩니다. model로 부터 실제로 얻는 정보는 바로 다음 state로 이동할 때의 reward뿐이기 때문입니다. V(St+1)가 이후의 reward들의 정보를 모두 포함하고 있다고 생각할 수도 있지만, 이는 실제로 얻은 reward를 바탕을 계산한 값이 아닌 추정한 값에 불과하여 후에 ture value로 update할 여지가 있는 기대값에 불과합니다. 따라서, TD는 bias가 높습니다. 

 이와 달리 MC는 episode가 끝나야만 update를 할 수 있지만 episode가 끝난 뒤에는 실제 얻은 reward의 정보를 반영할 수 있습니다. 하지만, episode가 어떤 state sequence로 이루어졌느냐에 따라서 동일한 state도 다른 value func.으로 update될 수 있습니다. 따라서 MC는 variance가 높습니다. bias와 variance는 서로 trade-off 관계에 있으며 강화학습에서 학습에 방해되는 요소들입니다. 따라서 이를 줄이기 위해 MC와 TD의 장점을 살리기 위한 방법들이 연구되었습니다.

 n-step TD

이러한 방법 중 하나가 바로 n-step TD입니다. n-step TD는 update를 할 때, 하나의 step이 아니라 n개의 step을 보고 update를 하자는 것입니다. 만약, n을 Terminal state까지 가져간다면 MC가 됩니다. 이렇게 n-step을 취하여 update를 하면 MC와 TD의 장점을 모두 가져갈 수 있습니다. 

 

 

 

<Fig 6. n-step TD prediction>

 

 

<Fig 7. n-step TD return>

 TD(λ)

 강화학습에서뿐만아니라 ML 전반적으로 적당한 hyper parameter의 설정은 항상 고민거리입니다. n-step TD도 적당한 n을 찾는 것에 기준이 필요하고 그 것에 따라 좋은 n을 찾아야합니다. Silver 교수님 강의자료에 있는 Random walker라는 예제를 통해서 그 방법을 설명하겠습니다. 

 

 

 

<Fig 8. Random walker example>

 

C state에서부터 시작해서 양쪽 끝에 있는 terminal state에 도달할 때까지 왼쪽 혹은 오른쪽으로 random한 action을 취하는 example입니다. 아래 graph는 각 state에서의 value func.을 추정한 것이고 옅은 회색 선이 true value func.입니다. C에서부터 시작해서 random한 action을 취하면서 얻은 정보를 바탕으로 true value func.을 prediction해야합니다.

Forward-view TD(λ)

만약 이 문제에 n-step TD를 적용한다면 어떤 n을 적용시켜야할까요? 

 

 

<Fig 9. Large Random walker example>

 

위 그래프는 10개의 episode에서 step size, α와 n에 따른 TD RMS(Root Mean Square) error입니다. 사실 n뿐만 아니라 step size도 이 error에 영향을 주게 됩니다. 그래서 MC와 TD의 절충안이 n-step이듯, 이 n-step 안에서도 여러 n-step 선택하여 평균을 취하면 각 n-step마다의 장점을 모두 취할 수 있게 됩니다. 이때, 단순한 산술평균이 아닌 λ라는 weight을 이용해서 geometrically weighted average를 취합니다. n-step마다 얻어진 return에 이 weight을 곱하여 λ-return(Gtλ)을 만듭니다. 그리고 이 return으로 update를 하면 forward-view TD(λ)가 됩니다. 이때 update하는 식은 아래와 같습니다. 

              

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<Fig 10. Forward-view TD(λ)>

 

 

이때 weight은 (1 – λ) λn-1의 형태를 이용하고 이를 모두 더하면 1이 됩니다. 앞서 살펴본 TD(0)에서 (0)의 의미는 λ=0으로, Gt(1)만을 이용하기 때문입니다. λ=1이면 나머지 weight은 모두 0가 됩니다. 하지만 이런 방법을 취하니, 다시 episode가 끝나야 update를 할 수 있다는 MC에서의 단점이 다시 생겨버립니다.

Backward-view TD(λ)

이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 생각해봐야합니다. 여기서 eligibility trace라는 개념이 나오는데, 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단하여, 현재 얻게 되는 reward을 해당 state에 나누어주는 것입니다. 이때, 영향을 주었다고 판단하는 index를 credit이라고하고 이 credit을 assign할 때, 두 가지 기준을 씁니다. 1) Frequency heuristic(얼마나 자주 방문했는가?) 2) Recency heuristic(얼마나 최근에 방문 했는가?) 

       기준 1)Frequency heuristic을 적용한 예를 들어보겠습니다. 

 

                                    

                   

 

 

 

<Fig 11. Eligibility Trace example (with frequency heuristic)>

 

초기 값 E0(s) = 0이라고 했을 때, 현재 state가 이전에 방문했던 state와 같으면 +1을 하는 식입니다. 이렇게 state마다 eligibility trace를 기억해두고 이를 TD error에 곱하여 update합니다. 이러한 방법을 backward-view TD(λ)라고 합니다. update하는 식은 아래와 같습니다.

 

 

 

forward-view TD(λ)는 MC와 TD의 장점을 모두 취하기 위해 n-step을 쓰려했으나, n에 따라 각기 다른 장점이 있기에 MC의 update식에 있는 target(return)을 λ-return으로 사용하여 각 n-step의 장점을 모두 취하는 것에 의의를 두었다면, backward-view TD(λ)는 TD의 update식에서 eligibility trace라는 방법을 이용해서 새롭게 weight을 주는 것에 의의를 두었다고 생각할 수 있습니다. 개인적으로는 forward-view TD(λ)는 MC의 high variance 문제를 episode의 수를 끝날 때까지가 아닌 특정 n으로 줄여서 해결하려했더니 α와 n에 따라 optimal한 정도가 다르기 때문에 이를 아우르기 위한 방법, 그리고 backward-view TD(λ)는 TD의 high bias문제를 그 동안 지나왔던 state에 heuristic으로 기준을 주어 바로 다음 step뿐만 아니라 이 전의 event도 영향을 주게끔 해결하려는 시도로 이해했습니다. 혹시 사실과 다르다면 의견주세요:)

TD Control

 SARSA

 TD prediction에서 model-free한 속성을 위해 action-value func.을 사용하고 ε-greedy policy improvement를 적용하면 SARSA가 됩니다. 아래는 q-func.을 update하는 식과 backup diagram입니다.

 

            

 

<Fig 12. backup diagram of SARSA>

 

여기서 현재 state, action(S, A) 그리고 이를 통해 얻은 reward(R)와 다음 state, action(S', A')까지 보고 update를 하기 때문에 SARSA라는 이름이 되었습니다.

 

< Fig 13. SARSA >

SARSA의 algorithm은 아래와 같습니다. TD prediction에서 action-value func.을 사용하고 policy improvement과정이 추가되었습니다.

 

 

< Fig 14. The Algorithm of SARSA >

 

Ch.5에서 구현했던 환경에서 SARSA agent를 구현해보겠습니다. 이 역시 Ref.[2], [5]를 참조하여 구현했습니다.

 

 

앞선 문제와는 다르게 accuracy가 좋지 못합니다. 거의 0에 가까운 %가 나오는데 그 원인은 무엇일까요? SARSA agent는 여러 trial and error를 겪으면서 H(green area) 주위의 red area를 dangerous하다고 생각합니다.

 

< Fig 15. The Algorithm of SARSA >

 

 

아래와 같이 실제 agent가 Learning을 종료한 후의 agent.Qtable을 살펴보면, red area의 근처 state들에서 Qvalue를 고려해보면 [0,1]에서는 Left(to [0,0])로, [1,1]에서는 Up(to [0,1])로 가게됩니다. 현재는 [1,0]에서 down으로 가는 쪽으로 학습이 잘 되었지만, [0,1]의 Qvalue처럼 학습되는 문제가 발생할 수도 있습니다. 

 

 

 

 

만약 그렇다면, start state로부터 1로 떨어진 영역([0,0], [0,1], [1,0], [1,1])안에 갇히는 현상이 벌어집니다. 이 현상을 해결하는 방법이 다음 포스팅에서 다룰 off-policy TD control, Q-learning입니다.

 n-step SARSA

 SARSA에도 n-step을 적용할 수 있습니다. 이때는 return값 대신에 q-value를 이용하고 action-value func.을 이용합니다.

 

 

< Fig 16. n-step SARSA >

 SARSA(λ)

Forward-view SARSA(λ)

마찬가지로 forward-view SARSA(λ)도 존재합니다. forward-view TD(λ)와 같으나 q-func.과 qλ return 을 이용합니다.

 

                     

                     

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<Fig 17. Forward-view SARSA(λ)>

 

Backward-view SARSA(λ)

Backward-view SARSA(λ)도 q-func.을 이용하는 backeward-view TD(λ)과 같습니다. 아래 식은 이 방법을 적용한 update하는 식입니다.

 

 

 

 

 

 

마찬가지로 q-func.을 사용한 TD error에 eligibility trace를 곱해서 update합니다. algorithm은 아래와 같습니다.

 

 

< Fig 18. The Algorithm of backward-view SARSA(λ) >

마치며

이전 포스팅에서 다룬 MC와 함께 TD는 강화학습의 대표적인 방법론입니다. 이 두 방법은 모두 on-policy RL입니다. SARSA section에서 agent를 구현한 code를 통해서 이와 구분되는 off-policy과 off-policy RL의 대표적인 방법, Q-learning를 다음 포스팅에서 다루겠습니다.

 

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

 

Reference

[1] https://dnddnjs.gitbooks.io/rl/content/temporal_difference_methods.html

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

[3] https://learningcarrot.wordpress.com/2015/11/12/%EB%B6%80%ED%8A%B8%EC%8A%A4%ED%8A%B8%EB%9E%A9%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC-bootstrapping/

[4] https://en.wikipedia.org/wiki/Bootstrapping_(statistics)

[5] https://github.com/rlcode/reinforcement-learning-kr/tree/master/1-grid-world/4-sarsa