RL : TD Method

TD Method

Monte-Carlo방법에 이어 두 번째 방법은 Temporal Difference, 또는 TD다.

TD Method 목적

Monte-Carlo에서는 실제로 얻어진 return값들을 사용하는데, Agent가 이 return을 얻는데까지는 많은 시간이 필요한 경우도 있다. 그리고 return은 오랜 기간동안 얻은 reward들을 사용하기 때문에 평균을 내야하는 각각의 return값들이 매우 다를 수 있다. 게임이나 현실의 문제는 episode의 끝이 무한대에 가깝도록 길기 때문에 episode가 반드시 끝나야 학습을 하는 MC의 방법으로는 한계가 존재한다.

TD Method 정의

MC Method의 단점들을 보완해 Agent가 return을 얻기까지 기다리지 않고, 매 time-step마다 학습을 하는 방법을 TD라고 한다.

 

TD의 가장 기본형인 TD(0)에서는 V(s)를 현재 상태에서 얻어진 보상 r과 discount된 다음 상태의 가치 V(S_t+1 or S')의 합으로 업데이트 하는 방식이다. Monte-Carlo에서 return값으로 V(s)를 근사하는 것과 비슷하게, TD(0)는 이 합으로 V(s)를 근사한다.

 

이 합은 우리가 도달하기 원하는 목표값이기 때문에 TD target이라고 부르고,

여기서 TD target에서 현재값 V(s)를 뺀 것을 TD-error라고 한다.

TD(0)

TD는 MC와 같은 sample backup이면서 time-step마다 update 한다. 아래 식은 MC에서 value func.을 update하는 식이다. (여기서 return Gt는 해당 state에서 episode의 끝까지 얻은 reward들을 시간에 따라 discount한 것이다.)

이 것을 1 step에 대한 것으로 바꾸면 TD(0)가 된다. 따라서 TD(0)의 update 식은 아래와 같다. 

MC와 마찬가지로 R_t+1+γV(S_t+1)를 TD target, Rt+1+γV(St+1) - V(St) 를 TD error라고 한다.

즉, S_t 의 value func.을 S_t+1로 변할 때의 reward와 그 state의 valuf func.를 discounting한 것(TD target)에서 step size, α만큼 update하겠다는 것이다.

TD(0)는 각 상태의 V(s)값을 TD-error를 이용해 조금씩 업데이트 해나가는 과정이다.

하지만 전 슬라이드에서 얘기 했듯이, 이렇게 state value function을 사용하면 policy를 구할때 model이 필요하다는 단점이 있어서 model을 모를때는 action value function Q(s,a)를 사용한다.

TD Method 응용

이렇게 Q(s,a)를 사용한 TD method중에는 Sarsa와 Q-learning 등의 방법이 있다.

Sarsa는 (state-action-reward-state-action)의 앞글자를 따서 만든 방법이다.
이 두 방법은 앞 슬라이드의 방법과 비교해서 state value function 대신에 action value function을 사용한다는 점 이외에는 매우 비슷하다.

Sarsa와 Q-learning의 차이점은 밑줄친 부분인 TD-target을 구하는 방법에 있다.

Sarsa에서는 s-a-r-s’-a’ 5가지를 실제로 에이전트가 경험으로 얻은 값을 사용한다. 사용한 policy를 통해 실제로 경험한 a’를 사용하기 때문에 sarsa는 on-policy method라고 한다.

반대로 Q-learning에서는 s-a-r-s’ 4가지만 실제로 얻은 값을 사용하고, TD-target에 들어가는 Q(s’,a’)값을 구할 때는 이를 최대화 시키는 a’를 사용한다. 그렇기 때문에 에이전트가 사용한 policy를 통해 얻어진 action이 아닌 다른 ”greedy”한 action을 사용하게 되고, 이 방법은 off-policy라고 한다. 

이 말은 Sarsa에서는 다음 state의 action이 포함되어있어 policy를 따르지만, Q-Learning 은 action 했던 것 중에서 제일 max 인 지점에 대해서만 하기 때문에 off policy 하다라고 한다.

앞서 설명한 Monte-Carlo와 TD(0)는 어떻게 return을 근사하는지 굉장히 다르다.

TD(0)는 TD-target인 현재 얻은 reward와 다음 상태의 가치 V(s’)를 사용하는 반면에 MC는 에이전트가 얻은 모든 reward의 합인 return값을 사용한다.

다시말해, TD(0)는 1-step return으로 근사하고, MC는 그 반대인 n=무한대의 return(일반적인 discounted return과 동일)으로 근사한다.

바로 이 둘을 섞어서 얻는 return의 근사값을 lambda-return이라고 부르고, 이를 TD-target으로 이용한 방법을 TD(λ)라고 한다.

lambda-return은 각각의 n-step return을 lambda라는 (MDP의 discount factor와 비슷한 개념의) 값으로 exponentially weighted average한 값이다. Monte-Carlo방법과 TD방법을 합쳐서 단점들을 보완한 방법이라고 볼 수 있다.

 

Monte Carlo (MC) vs Temporal Difference (TD)

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의 장점을 살리기 위한 방법들이 연구되었습니다.

 

TD : DP + MC

TD learning은 Monte Carlo method처럼 environment dynamics에 관한 model이 없이도 순수한 경험(experience)만으로도 직접 학습이 가능하며, DP처럼 episode가 종료되기까지 기다리지 않아도 다른 예측치를 기반으로 value function의 update가 가능하다(이것을 bootstrap이라는 용어를 사용하여 설명하였다).

 

 

출처 : 

jay.tech.blog/2016/12/28/temporal-difference-learning/