5. n-step Bootstrapping

이전의 챕터 Temporal Difference 에서 one-step의 temporal-difference (TD) 방법을 배웠습니다.

이번에는 one-step이 아닌 몬테카를로와 one-step TD를 합친 n-step TD method에 대하여 알아보겠습니다.

5.1 n-step TD prediction

MC와 TD의 update방법의 다른점은 무엇일까요?

MC는 Policy $\pi$를 따라 return된 Sample들을 이용하여 $V_\pi$ 를 estimate할때 MC return된 sample들의 reward를 시작 state부터 episode가 끝날때까지의 각 state를 관찰하며 update합니다.

반면에 One-step TD는 이 작업을 하나의 reward만 계산하고, 다음 state의 estimate한 value를 bootstrapping하여 그 뒤의 return 될 reward들을 Estimate 한 Value(Cafe)로 대체합니다.

예를 들어 MC는 State Home부터 State 모두의연구소까지의 V(home)값을 예측 ( 여기서는 시간을 예측 : State Home일때 State 모두의 연구소까지의 소요시간 예측)

TD는 State Home에서 다음 State Cafe로 갈때 받는 하나의 reward $R_{t+1}$만 계산해 넣어주고 $t+1$에서의 state value를 bootstrapping하여 V(home)을 업데이트 합니다.

이러한 방법들은 환경에 맞춰서 적용해야 하는데요. Monte Carlo에는 TD error은 너무 길고, one step TD를 쓰기에는 적합하지 않은 경우 MC와 One step TD의 중간인 time step이 둘 이상이지만

estimate하고자 하는 state에서 terminal state 까지의 길이보다 짧은 time step의 reward를 기반으로 update하는 방법입니다.

이 방법을 n-step TD라고 합니다.

아래의 Back-up diagram과 같이 one-step TD는 우리가 이전에 배웠던 reward 하나와 time step 다음의 estimate value를 update하는 것이고

two-step update는 처음 두 reward를 바탕으로 two step 뒤의 state value를 estimate 한것입니다.

$\infty$ -step TD는 Monte Carlo와 같이 sample을 따라 episode가 끝날때까지 return된 reward를 바탕으로 update합니다.

이전 state value와 다음 state value의 차이를 비교한다는 점은 같지만 one-step TD는 다음 time step에서의 state value와 비교하는 반면,

n-time step TD는 n step 다음의 state와 비교한다는 점이 다릅니다.

---

식으로 다시 보면,

Monte Carlo에서 State $s_t$ 는 아래의 식과 같이 에피소드가 끝날때까지 reward의 return입니다.

$$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... + \gamma^{T-t-1}R_T$$

Monte Carlo에서 $G_t$를 update의 target값 이라고 정의하겠습니다.

그렇다면 one-step TD에서의 target은

$$G_{t:t+1} \doteq R_{t+1}+\gamma V_t(S_{t+1})$$

로 처음의 reward와 discounted된

다음 time step의 state value의 estimate값을 더한 것 입니다.

$$G_{t:t+2} \doteq R_{t+1}+ \gamma R_{t+2}+ \gamma^2 V_{t+1}(S_{t+2})$$

마찬가지로 n-step의 target은 아래의 식으로 정의할 수 있습니다.

$$G_{t:t+n} \doteq R_{t+1}+ \gamma R_{t+2}+...\gamma^{n-1}R_{t+n} + \gamma^nV_{t+n-1}(S_{t+n})$$

n step까지 return된 reward를 바탕으로 n step일때 state의 value를 estimate한 값 입니다.

n-step은 time step t가 n-step t가 t+n이 될때 $V_{t+n-1}$을 계산할수 있기에 t+n까지 가야지 n-step 방법을 사용할 수 있습니다.

n-step을 사용하려면 $R_{t+n}$ 까지 가서 $V_{t+n-1}$ 을 계산을 한 뒤 사용할 수 있습니다.

그렇기 때문에 이것을 처음 사용할 수 있을때는 t+n의 시점이므로 n-step을 사용한 natural state-value learning algorithm 은 아래의 식으로 정의할 수 있습니다.

$$V_{t+n}(S_t)\doteq V_{t+n-1}(S_t) + \alpha[G_{t:t+n}-V_{t+n-1}(S_t)]$$

또한 n-step TD for estimating $V \approx v_{\pi}$의 pseudo code는 아래와 같습니다.

$\pi(.\mid S_t)$를 따라 action을 선택하면서 reward $R_{t+1}$과 다음 state $S_{t+1}$을 관찰하고 저장합니다.

여기서 $\tau$ 는 update된 state를 의미하고 t-n+1의미를 가지고 있는데요.

계속 위의 과정을 반복하며 t가 0,1,2,3,4…로 가며 $\tau$ 가 0 이상일때,

계속 update를 하며 현재 time step이 지정하였던 n-step까지 도달하였을때,

$\tau +1$가 T에 도달할때까지 G를 Target으로 하나 이전 estimate value $V(S_\tau)$와의 TD를 이용하여 $V(S_\tau)$를 업데이트합니다.

이 개념을 공부할때 개인적으로 $TD(\lambda)$와 많이 혼동되었습니다.

n-step TD는 one-step처럼 reward하나와 다음 state의 value를 bootstrapping하여 가져오지 않고,

n개의 step을 정해주고 한개가 아닌 n개의 reward와 그 다음 state의 value를 bootstrapping한 것을 업데이트 해준다는 개념입니다.