Temporal Difference Method

본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar

수강 후정리를 위한 포스팅입니다.

모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다.

---

Before This Episode

https://jinwoo-jung.tistory.com/29

Monte Carlo Method

---

 

DP는 Model을 알기 때문에 $v(S)$를 policy에 의해 선택되는 action $a$과 state의 변화 $S \to S'$의 확률을 기반으로 얻어지는 reward $r$과 $S'$에서의 discounted state-value로 계산된다. 이때, $v(S)$를 추정하는 과정에서 다른 추정 $v(S')$을 이용하기 때문에 Bootstrapping이라 칭한다.

 

MC의 경우 Free-Model으로, t에서 Sampling 된 Episode에 대한 reward $G_t$의 평균으로 계산되며 이는 reward $R_{t+1}$과 $t+1$에서의 discounted state value로 계산된다.

 

$v(s) = E[R_{t+1} + \gamma R_{t+2} + {\gamma}^2 R_{t+3} + \cdots | S_t = s]$

$=E[G_t|S_t = s]$

$=E[R_{t+1} + \gamma v(s_{t+1})|S_t = s$

$=\sum_{a}^{} \pi(a|s) \sum_{}^{} P(s',r|s,a)[r + \gamma V(s')]$

 

이때, DP는 Bootstrapping을 통해 state-value를 update 한다.

$$v_{k+1} \leftarrow \sum_{a}^{} \pi(a|S) \sum_{S',r}^{} P(S',r|S,a)[r + \gamma v_k(S')]$$

MC는 Sampling 된 Episode를 진행할 때 마다 update 한다.

$$v_{k+1} \leftarrow  v_k(S_t) + \alpha [G_t - v_k(S_t)]$$

 

Temporal Difference(TD) Method

 

앞으로 배울 TD는 DP의 Bootstrapping과 MC의 Sampling의 특성을 모두 지닌 Method로 모든 state에 대해서 진행하기 힘들기 때문에 sampling 된 특정 State에 대해서만 bootstrapping 방식을 적용하여 state-value를 update 한다.

$$v_{k+1} \leftarrow v_k(S) + \alpha [R_{t+1} + \gamma v_k(S') - v_k(S)]$$

 

따라서 $v_{\pi}$는 아래와 같이 정의된다.

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

 

TD

 

TD는 MC의 특성을 지니기에 Model-Free임과 동시에 DP의 특성을 지녀 MC와 달리 Terminal State까지 진행하지 않고 즉각적인 Update가 가능하고 Terminal State가 없는 Episode에 대해서도 적용 가능하다.

 

여기서 TD(0)는 one-step TD임을 가르키며 이는 추후 N-step TD와의 비교를 위해 다음과 같이 표현하였다. 이에 대한 Sudo-Code는 다음과 같다.

 

Tabular TD(0) Sudo-Code

 

MC에서 배운 것처럼 초기 State $S$를 임의로 설정하여 누락되는 State, Action을 방지하는 것을 알 수 있으며, 위의 sudo-code의 경우 terminal state가 있는 Episode를 가정하였다. 이때, Tabular의 의미는 state,action이 계산 가능한 범위 내에서 충분히 작음을 의미한다.

 

TD Example : Random Walk

 

위의 예시를 살펴보고 TD와 MC의 차이를 이해 해 보자.

0.5의 확률로 좌/우로 움직이고, $\gamma = 1$을 가정하자. 또한, terminal state는 양 끝에 존재하고, 오른쪽 끝 terminal state로 가는 return만 1이고 나머지는 0이다. 즉, 각 state에서의 state-value는 오른쪽 terminal로 가는 확률로 계산되는데, 이는 state-value가 reward의 sum이고 현재 discount factor가 1이기 때문이다.

따라서 $v_{\pi} = [ 1/6, 2/6, 3/6, 4/6, 5/6 ]$임을 알 수 있다. $v(s)$를 0.5로 초기화 하고 계산하면 아래와 같다.

 

TD and MC Results

 

그래프를 보면 TD가 true values에 더 가까움을 알 수 있으며, RMS error역시 TD가 더 빠른 속도로 줄어들기에 더 빠른 속도로 정답에 수렴함을 알 수 있다.

 

TD Example : Predictor

 

위 예시를 보면 더 극단적으로 둘의 차이를 알 수 있다. 

직관적으로 Optimal Value는 $v(A) = v(B) = 0.75$임을 알 수 있다. 

Episode가 위에 주어진 것처럼 8가지가 있다고 가정하고 그 순서는 왼쪽 위부터 오른쪽 아래로 흘러간다고 가정하자. MC 방식으로 계산하면 Episode의 순서에 상관없이 v(A) = 0이다. 하지만, TD의 경우 Episode의 순서가 거꾸로 흘러간다고 가정하면, $v(A) = v(A) + \alpha [0 + \gamma v(B) - v(A)]$로 계산되고, $\gamma = 1, v(A),v(B)$의 초기값이 0이라 가정한다면, v(A) = 0.75로 계산된다.