5.4 Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm

5.2 n-step Sarsa

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한 것을 업데이트 해준다는 개념입니다.

4.2 Advantages of TD prediction Methods

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