[RL] Introduction to Temporal Difference Learning

(해당 포스트는 Coursera의 Sample-based Learning Methods의 강의 요약본입니다)

 이전 포스트에서는 Off-policy 방식의 Monte Carlo Prediction에 대해서 다뤘다. 일단 Monte Carlo의 특성상 policy에 대한 trajectory를 여러개 뽑아서 expectation을 취해야 한다.

$$ v_{\pi}(s) \doteq \mathbb{E}_{\pi}[ \color{red}{G_t} | S_t=s] $$

 일단 위처럼 State value function을 구하기 위해서는 해당 state \(s\)에서의 total expected return \(G_t\)을 구해야 하고, 이때 Policy Evaluation에선 다음과 공식을 통해서 state value를 update했다. (참고로 아래 식에선 bandit 알고리즘처럼 constant step size \(\alpha\)를 사용했다.)

$$ V(S_t) \leftarrow V(S_t) + \alpha[\color{red}{G_t} - V(S_t)] $$

 결국 Monte Carlo를 통해서 값을 update하기 위해서는 total expected return \(G_t\) 가 필요하다. 그런데 용어에 담긴 뜻 그대로 total이란 말은 해당 policy에 대한 full trajectory의 expected reward를 모두 더한 값이므로, 이 값을 구하기 위해서는 무조건 policy \(\pi\)가 수행되고 있는 episode가 무조건 종료되어야 값을 update할 수 있다는 것이다. episode가 짧은 경우라면, 전체 학습시간에 큰 지장이 없겠지만, 실제 환경과 같이 episode가 매우 긴 경우라면, optimal policy를 찾는데 어려움을 겪을 것이다. 만약 episode가 진행되는 도중에도 state value를 update하는 방법은 없을까?

 먼저 total expected return \(G_t\)를 그대로 풀어쓰면, future reward와 discounted factor의 조합으로 된 식이라는 것을 알고 있다. 또한 바로 다음 state의 reward (\(R_{t+1}\))과 그때의 expected return (\(G_{t+1}\))을 활용해서 recursive하게 표현할 수도 있다.

$$ \begin{align} G_t &\doteq \sum_{i=t+1}^{T} \gamma^{i-t-1} R_i \\ &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots \\ &= R_{t+1} + \gamma G_{t+1} \end{align} $$

 그럼 앞에서 언급한 value state의 update하는 과정도 다음 state의 정보 (\(G_{t+1}\))를 활용해서 다시 정리를 해볼 수 있다. 그런데 다음 state의 정보 역시 그때의 state value이므로, 결론적으로 state value function의 recursive한 형태로 표현할 수 있게 된다.

$$ \begin{align} v_{\pi}(s) &\doteq \mathbb{E}_{\pi}[G_t|S_t = s] \\ &= \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t = s] \\ &= R_{t+1} + \gamma v_{\pi}(S_{t+1}) \end{align} $$

 이렇게 최종적으로 얻은 state value를 앞에서 잠깐 언급했던 Policy Evaluation에서의 total expected return 항에 대입해보자.

$$ \begin{align} V(S_t) &\leftarrow V(S_t) + \alpha [G_t - V(S_t)] \\ \Downarrow \\V(S_t) &\leftarrow V(S_t) + \alpha [\color{red}{R_{t+1} + \gamma V(S_{t+1})} - \color{blue}{V(S_t)}] \end{align} $$ 

이렇게 되면, 굳이 episode가 끝날때까지 trajectory에 대한 return을 수집하지 않더라도 다음 state에서 얻을 수 있는 reward (\(R_{t+1}\))와 그 state의 value (\(V_{t+1}\))만 알게 된다면, 현재의 state value를 update할 수 있다는 결론을 얻을 수 있다. 이렇게 현재의 state와 next state의 value의 차이를 토대로 state value를 update하는 방식을 Temporal Difference(TD) Learning 이라고 하고, 위 식 중 빨간색으로 표시된 \(R_{t+1} + \gamma V(S_{t+1})\)을 TD Target이라고 표현한다. 의미는 policy evauation시 우리가 확인해야할 target policy \(\pi\)가 가지고 있는 현재 state 의 value 라는 것이다. 

 위 식을 통해서 우리가 구한 것은 target policy가 가진 state value와 진짜 state value 간의 오차 (TD Error)이고, 보통 식에서는 \(\delta_t\)라고 표기하여, \(t\)에서의 TD error라는 의미를 가지게 된다. 그런데 이런 접근 방식은 이미 Dynamic Programming에서도 나왔었다.

그림 1. Iterative Policy Evaluation (DP)

 Dynamic Progamming에서도 언급된 Iterative Policy Evaluation 에서도 현재의 State value를 update하는데 next state의 state value \(V(s')\)를 이용했다. 다만 차이가 있다면, Dynamic Programming의 특성상 state value를 update하기 위해서는 각 event가 발생할 확률이 필요하다는 것이고, Temporal Difference에서는 확률없이도 next state의 value만 가지고 state value를 update할 수 있다는 것이다. (사실 environment내에서 event가 일어날 확률을 안다는 것은 사전에 environment에서 학습된 model이 있다던가, 그 environment의 dynamics를 알고 있다는 것과 동일한 전제이므로 dynamics를 알지 못하는 real environment에서는 DP를 적용하기 어려운 부분이 있다.)

  위에서 소개한 TD Learning에서의 state value update에서는 1-step에 boundary를 뒀다. 예를 들어 다음과 같이 trajectory가 진행된다고 치면,

$$ \color{red}{S_0}, A_0, \color{blue}{R_1, S_1}, A_1, R_2, S_2, A_2, R_3, S_3, \ldots $$

  \(S_0\)에서의 value를 update하는데 있어 해당 state에서 action을 취했을 때 얻을 수 있는 reward (\(R_1\))와 다음 state \(S_1\)의 value를 활용한 것이다. 다시 말해 현재 agent가 특정 state에 있다면, state value는 1-step 이전 state에 초점을 맞춰서 update하는 것이다. 이를 1-step TD, 혹은 TD(0) 라고 표현한다. 이렇게 얻은 state value를 표 형식(tabular)으로 가지고 있을 때에 대한 algorithm은 다음과 같다.

그림 2. Tabular TD(0)

 그리고 이렇게 다음 state의 value를 활용해서 현재 state의 value를 update하는 과정을 bootstrapping이라고 한다. 이처럼 TD Learning 자체는 Monte Carlo처럼 estimation이 들어가면서 DP에서 다뤘던 bootstrapping이 반영되어 있어서, 보통 Monte Carlo와 DP의 Combination이라고 표현하기도 한다. 이를 통해서 얻는 이점은 추후에 설명하고자 한다.

 TD Learning은 일종의 prediction learning이라고 할 수 있다. 아마 sutton 책에도 자주 나오는 내용을 보면 MC prediction이라는 개념이 있을텐데, 이는 next state value에 대한 prediction(or estimation)을 통해서 state value function을 update하기 때문이다. 강화학습에서는 Q-learning이나 SARSA, DQN, Actor-Critic 같은 기법들이 이렇게 prediction을 통해 구한 value function을 이용해서 학습을 하고 있다. (AlphaGo나 Policy Gradient method랑은 다른 접근 방식이다.) 

 이 Prediction Learning은 unsupervised supervised learning이라고 표현하기도 한다. Unsupervised란 개념은 ML에서도 따온 것처럼 어떤 데이터에 대한 정답을 갖지 않은 상태에서 학습이 이뤄지는 것인데, TD Learning 같은 경우도 일단 prediction이 일어난 후에는 그 prediction이 옳고 그른 여부를 확인하지 않고, 수행한다. 반면 supervised의 개념은 이렇게 prediction 후에 얻은 경험을 토대로 모델을 개선시켜나가기 때문에 들어 있다. 어떻게 보면 사람이 미지의 일에 대해서 경험을 쌓고, 이후에 그 경험을 바탕으로 더 나은 결과를 얻는 그런 직관적인 형태의 학습인 것이다. (강의에서 이를 설명한 표현이 "learning a guess from a guess" 였다.)