Temporal-Difference Learning

만약 강화학습을 대표할 수 있는 아이디어가 있다면 그것은 TD(temporal-difference) learning 일 것입니다.

TD는 Monte carlo와 DP의 개념을 합쳐놓은 학습 방법입니다. Monte carlo처럼 모델 없이 경험을 통하여 value를 측정하며

DP처럼 끝까지 가지 않아도 중간중간 value를 estimate하는것이 가능합니다.

TD Prediction

TD와 Monte Carlo는 둘다 경험을 통해 value를 측정한다는 것이 공통점 입니다.

하지만 앞에서 말했듯이 둘의 다른점으로는 Montecarlo는 state가 Terminal될때까지 (끝까지) 가야지 value를 측정할 수 있고 TD는 그렇지 않다는 것입니다.

$$V(S_t) \leftarrow V(S_t)+ \alpha \left [ G_t - V(S_t) \right ]$$ $$V(S_t) \leftarrow V(S_t)+ \alpha \left [ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right ]$$

첫번째는 MC 방법으로 $G_t$를 알아야, $V(S_t)$를 update가 가능합니다.

두번째는 TD 방법으로 현재 state에서 action을 선택하며 받을 Reward $R_{t+1}$과 다음 State $S_{t+1}$에 discount factor가 적용된 state value를 estimate하며 update합니다.

위와 같이 한 step을 estimate하는 TD 방법을 TD(0)으로 정의합니다.

아래는 $V_\pi(s)$를 estimating하는 TD(0)의 pseudo code 입니다.

TD(0)은 bootstrapping을 통하여 value를 update하는데 이전이 state value function $V_\pi(s)$의 정의를 보면,

$$V_\pi(s)= E_\pi[G_t \mid S_t=s]$$ $$= E_\pi[R_{t+1}+ \gamma G_{t+1} \mid S_t=s]$$ $$=E_\pi[R_{t+1}+ \gamma v_\pi(S_{t+1} \mid S_t=s]$$

$V_\pi(s)= E_\pi[G_t \mid S_t=s]$ 은 몬테카를로의 $V_\pi(s)$로 사용하며, 다음 state를 estimate하는 $=E_\pi[R_{t+1}+ \gamma v_\pi(S_{t+1} \mid S_t=s]$ -2식은 TD에서 $V_\pi(s)$를 estimate할때 사용합니다.

TD(0)의 Back diagram은

이렇게 생겼습니다. TD와 Monte carlo는 sample updates라고 불리는데, 그 이유는 이미 성공한 다음 state의 value와 reward를 back-up 하여 현재의 state value로 update하기 때문입니다.

이렇게 update하다보면 $V(S_t)$ $R_{t+1} +\gamma V(S_{t+1})$ 간의 오차가 생길텐데 이것을 TD Error이라고 정의합니다.

$$\delta _t \doteq R_{t+1} + \gamma(V(st+1) - V(s_t)$$

만약 몬테카를로 처럼 episode 중에 V의 값이 변하지 않는다면 TD error는 무엇일까요?

몬테카를로의 TD error은 다음처럼 정의할 수 있습니다.

---

TD와 MC의 Td error의 차이를 이해하기 위해 예를 하나 들어보겠습니다.

위의 테이블은 사무실에서 떠나 집에 도착할때까지의 마주치는 states들과 시간의 변화를 테이블로 작성한 것입니다.

Elapsed Time : State가 변할때마다 흐른 시간의 총 합 (단위 : 분)

Predicted Time to go: 그 state에서 집까지 가는데 걸릴시간을 predict 한 시간 (단위 : 분)

predicted Total Time : 총 소요 예상을 predict

이 위의 표를 그래프로 표현해보면,

TD는 time step 마다 value를 estimate하여 error가 TD가 MC보다 작습니다. 하지만 MC는 state가 끝날때까지 기다려야 value를 알 수 있어 예제와 같이 여러 문제가 발생할 수 있는 환경에는 적합하지 않습니다.

TD에서는 즉각 배우고 예측시간을 state가 변화할때마다 초기화 해줘서 예제와 같은 문제에 적용하면 좋습니다,.

위의 그래프중 TD를 나타내는 오른쪽 그래프는

$$V(S_t) \leftarrow V(S_t)+ \alpha \left [ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right ]$$

와 같습니다. 그리고 이 error을 temporal difference라고 합니다.

오늘은 Dynamic programming과 Monte Carlo method가 합쳐진, Temporal-Difference Learning에 대하여 알아보았습니다.

강화학습의 중요한 아이디어라고 한만큼 강화학습에서 유명한 알고리즘이 이 TD에서 파생되어 나온것 같습니다.

다음 포스팅에서는

1. TD prediction methods의 장점
2. on-policy TD control 방법인 sarsa
3. off-policy TD control 방법으로 Q-learning

에 대하여 포스팅 하도록 하겠습니다.

Reference

• Reinforcement Learning: An Introduction Richard S. Sutton and Andrew G. Barto Second Edition, in progress MIT Press, Cambridge, MA, 2017