Temporal-difference (TD)는 Monte Carlo (MC)처럼 환경의 dynamics 모델없이 experience만으로 학습하고, dynamic programming (DP)처럼 return이 아닌 학습했던 estimate를 사용해서 estimate한다.(bootstrap) TD, MC, DP간의 관계는 강화학습 이론에서 자주 나오며, n-step이나 TD($\lambda$)와 같이 다양한 형태로 조합이 나올 수 있다. DP와 TD, MC는 모두 GPI에서 약간 변형된 형태로 볼 수 있다. 다만 다른 점은 모두 prediction 문제를 어떻게 해결하냐의 차이이다. 이전에도 그랬듯 주어진 정책 $\pi$로부터 가치 $v_\pi$를 구하는 prediction 문제를 다루고 최적의 정책을 찾는 control 문제에 대해서 얘기할 예정이다.
TD Prediction
MC 방법은 terminal이 아닌 상태들 $S_t$에서 주어진 정책 $\pi$을 따를 때 가치를 return $G_t$으로 구했었다.
여기서 $V$는 $v_\pi$를 estimate한 것이며 $G_t$는 $t$에서 실제 return 값, $\alpha$는 step-size를 말한다. MC는 return을 얻을 때까지 기다려야한다. 하지만 TD는 거지 다음 step까지만 기다리면 된다. 왜냐하면 target 값을 $R_{t+1}$과 discounting한 $V(S_{t+1})$을 사용하기 때문이다.
이러한 방법을 TD(0) 또는 one-step TD라 부른다. (나중에 TD($\lambda$)나 n-step TD$ 같은 방법이 등장한다.)
TD(0)은 기존에 Dynamic Programming (DP) 방법과 같이 bootstrapping을 기반으로 하고 있다.
다만 expected value 값을 정확한 환경의 모델로 계산했던 DP와 달리 TD(0)은 모르기 때문이 $v_\pi(S_{t+1})$ 대신 $V(S_{t+1})$라는 표기를 사용해서 experience를 통해 구한다.
tabular TD(0)의 backup diagram
TD(0) 업데이트식에서 대괄호 안은 estimate $R_{t+1} + \gamma V(S_{t+1})$와 $V(S_t)$가 얼마나 차이가 나는지 척도로써, 에러라고 볼 수 있다. 이를 TD error라고 부르며 강화학습에서 자주 다양한 형태로 나타난다.
이 에러는 다음 time step $t+1$에서의 state와 reward를 알아야만 구할 수 있다. $V$가 변하지 않고 유지한채로 다음 $t+1, t+2, ...$의 에러를 구해서 모두 더하면 TD error의 합은 Monte Carlo error로 볼 수 있다.
$V$가 episode동안 변한다 해도 step size가 작다면 거의 비슷하게(approximately) 값을 가지고 있을 것이다.
