Temporal Diff & SARSA

Monte-Carlo는 랜덤한 난수를 다수번 생성해 큰수의 법칙으로 표현하고자 하는 확률 분포에 근사하는 결과를 얻는 방법이였습니다. 다시 말해 model-free한 방법이였습니다. 같은 특징으로 Temporal Difference Methods를 알아봅니다.

 

MC는 한 episode가 종료 후에 산출된 return으로 각 state에서 얻은 reward를 에피소드 길이 즉시 시간에 비례해 discount($\gamma$)하는 방법으로 가치함수를 update했습니다.

 

하지만, 보다 확장된 application에서는 episode 길이가 잠재적으로 무한대 이므로 episode가 반드시 끝나야 학습을 하는 MC의 방법으로는 한계가 존재합니다. DP처럼 time-step마다 학습하면서 model-free한 방법이 바로 TD입니다. 

 

$Q(s_t,a_t) = \int_{s_{t+1},a_{t+1}}(R_t+\gamma Q(s_{t+1},a_{t+1}))\times P(S_{t+1}|S_t,a_t)\times P(a_{t+1}|S_{t+1})ds_{t+1},a_{t+1}$

 

는 다시말해

 

$\frac{1}{N}\sum_{i=1}^{N}(R_t^i \times \gamma Q(s_{t+1}^i,a_{t+1}^i))$ 였습니다. 

 

값이 결정되었다는것은 모든 값이 끝까지 가봐야 값을 알수 있다는 말입니다. 하지만 모든 에피소드를 끝까지 추정하는 것은 어려운 문제 이므로 $\frac{1}{N}\sum_{i=1}^{N}(R_t^i \times \gamma Q(s_{t+1}^i,a_{t+1}^i))$ 에서 처럼 지금과 다음 한 스텝만 가져가는 셈 입니다. 

 

즉 MC와 DP의 합성인 셈입니다.

 

TD Prediction

 TD(0)

TD는 MC와 같은 sample backup이면서 하나의 에피소드 길이 즉 time-step마다 update합니다.

 

$V(s_t) = V(s_t) + \alpha(G_t-V(s_t))$

 

최종 $G_t$는 해당 state에서 episode의 끝에서 얻은 reward들을 시간에 따라 discount($\gamma$)한 것으로 여기서 1 step을 대입하면 TD(0)가 됩니다. 업데이트는 다음과 같습니다. 

 

$V(s_t) = V(s_t) + \alpha(R_{t+1}+\gamma V(s_{t+1})-V(s_t))$

 

이때 $R_{t+1}+\gamma V(s_{t+1})-V(s_t)$는 이 다음 스템과 지금의 차이 이므로 TD error 입니다. 

즉 지금 상태의 가치 함수 값과 다음 상태의 보상 및 그 상태의 가치 함수의 차이만큼을 업데이트 하는 것이죠.

 

TD의 알고리즘은 이와 같습니다.

SARSA

 

SARSA 는 위에서 계속 봐왔던 한스팁 넘어간 TD 즉 상태(s), 행동(a), 보상(r), 다음 상태(s’), 다음 행동(a’) 을 합친 말입니다.

Q-learning 을 SARSA 와 비교하면 상태(s), 행동(a), 보상(r), 다음 상태(s’) 까지만 사용하는 SARS 라고 말할 수 있겠습니다. 따라서 Q-learning 과 SARSA 의 차이는 다음 행동(a’) 이 학습에 필요한가 입니다.

 

SARSA 의 식에는 max 연산자가 빠진 Q(s′,a′)가 들어가 있습니다. Q-learning 이 다음 스텝의 max-Q 값을 구하는 greedy 한 방법이라면, SARSA 는 Agent가 다음 스텝에서 취한 action의 값을 직접 사용하는 stochastic 한 방법입니다. Q-learning 은 max 값을 구해야 하기 때문에 episode 의 실행이 끝난 다음에 수행해야 하는 Off-policy 알고리즘이며 SARSA 는 episode 의 실행 중에 언제든지 학습이 가능한 On-policy 알고리즘이라는 특성을 갖습니다.