[RL] Temporal Difference Learning : TD(0)

 이전에 다뤘던 Q-learning같은 방법들을 보면, 각 state에 대한 expected return들을 일종의 table 형식으로 관리하는 것을 확인할 수 있었다. Bellman Equation을 사용해서 우리는 나름의 각 state에 대한 \(v_{\pi}(s)\) 를 구하거나, 각 state-action pair에 대한 \(q_{\pi}(s, a)\)를 구하고 매 step마다 table을 업데이트하면서 나름의 optimal policy를 찾으려고 노력할 것이다.

 여기서 주어진 환경내에서 취할 action을 정의한 policy \(\pi\)에 대한 state value function \(v_{\pi}(s)\) 를 구한다고 해보자. 강화학습의 특성상 우리는 미래에 얻을 수 있는 expected return \( G_{t} = \sum_{i=0}^{T}\gamma^{i}R_{t+i+1} \)를 최대화할 수 있는 optimal policy를 찾기를 원할 것이다. (여기서 \(\gamma\)는 discounted factor라고 해서,지금은 얻지 않았지만 미래에 얻을 reward에 대해서 얼마나 신경을 쓸 것인지에 대한 관심 정도라고 보면 좋을 거 같다.) 이런 문제를 풀 때 있어서 간단하게 해볼 수 있는 방법은 random search 기반의 Monte-Carlo estimation를 사용해서 value function을 정의하는 것이다.

 그런데 문제가 있다. Monte-Carlo estimation (MC) 을 사용하게 되면, 우리가 처음 시작하는 state에서부터 expected return을 계산하게 되고, 정해진 policy \(\pi\)를 따라가면서 expected return에 대한 평균을 계속 활용해나가게 된다. 그런데 간단한 환경이면 그런 방식으로도 적절한 policy를 찾을 수 있겠지만, 복잡한 환경을 고려해보면 좀 달라지게 된다. 보통 episode가 끝나면서 expected return을 업데이트하면 말이 되겠지만, 그 episode가 너무 길어져서 episode가 끝나기 전에 update가 이뤄지는 상황을 가정해보면, update 이전에 계산된 값들은 이미 바뀐 환경을 제대로 반영할 수 없게 된다. 소위 expected return에 대한 high variance가 발생하는 것이다. 여기서 high variance가 발생한다는 것은 말 그대로 policy의 결과에 대해서 일관성이 없어지는 것이다. 예를 들어 같은 MC를 사용해서 optimal policy를 구했다고 해도, 그에 대한 output이 제각각이 되는 것이다. 

 결국 MC가 제대로 동작하려면 특정 episode가 끝나야지 의미가 있는 것인데, 만약 지금 사용하는 환경이 정해진 episode가 없다면 어떨까? 그래서 보통 pure MC 방법은 Online update가 안된다고 표현한다. 그렇기 때문에 특정 episode가 끝날때까지 무조건 기다려야 되고, 그 사이에 environment간에 어떠한 interaction도 expected return에 영향을 줄 수 없다. 그래서 느리다는 문제도 하나의 단점이다.

 여기서 policy evaluation에 나온 target이라는 개념을 활용해 볼 수 있다. MC Algorithm에서 update하는 부분을 살펴보면 다음과 같이 되어 있는 것을 알 수 있다.

$$ v_{\pi}(s_{t}) \leftarrow v_{\pi}(s_{t}) + \alpha (g_{t} - v_{\pi}(s_{t})) $$

 여기서 \( g_{t} \)는 t step 이후로 얻을 discounted expected return에 대한 sampling된 값을 말하는데, 이게 우리가 구하고자 하는 target이 된다. 

위에서 구한 target 개념은 나중에 적용해보고, 또하나 적용해볼 수 있는 idea가 return을 어느 정도 의미있는 정도만 살펴보자는 것이다. MC의 문제 중 하나가 episode가 끝날때까지 기다려야지 결과를 나온 expected return을 사용할 수 있는 것이었는데, 이럴 필요를 없앤 것이다. 그렇게 되면 total expected return \(G_{t}\)을 다음과 같이 확 줄일 수 있게 된다.

$$ G_{t} = R_{t} + \gamma R_{t+1} + \gamma^{2} R_{t+2} + \cdots = R_{t} + \gamma \epsilon $$

(여기서 \( \epsilon \)은 MC처럼 특정 시점의 expected return을 함축적으로 표현한 형식이다.)

 이를 활용하게 되면, 우리가 기존에 알고있던 bellman equation에 의한 state value function이 다음과 같이 바뀌게 된다. 

$$ \mathbb{E}_{\pi}[G_{t} | S_{t} = s] = \mathbb{E}_{\pi}[R_{t} + \gamma G_{t} | S_{t} = s] $$
$$ v_{\pi}(s) = R_{t} + \gamma \mathbb{E}_{a \sim \pi(a|s), s' \sim \mathcal{P}_{a}^{s, \cdot}}(v_{\pi}(s'))  $$

 식이 조금 복잡해지고, 계산하기 어렵게 되었지만, 이 식이 의미하는 것은 만약 우리가 주어진 state \(s\)에 대해서 모든 state에 대한 value를 알고만 있다면, 다음 state에 대한 value도 estimate할 수 있다는 것이다. 말그대로 prediction이 가능해지는 것이다. 물론 이 state value를 알 수 없기 때문에 approximation이 들어가게 된다.

 일단 위 식을 풀기 위해서는 Expectation term을 대체할 뭔가가 필요하다는 것이다. 물론 approximation이 잘되서 모든 state value function을 구할 수 있으면 최고로 좋겠지만, 그렇게 되기는 힘들뿐더러, 처음에는 Expectation을 구할 데이터가 작기 때문에 approximation이 잘 될 수 없다. 그래도 학습의 목적은 시간이 지나가면서 total expected reward가 커지는 것이고, approximation이 처음에 잘 안되더라도 상관없다.

 일단 예를 들어서 주어진 데이터를 통해서 구할 수 있는 state value function에 대한 approximation을 \(\hat{v_{\pi}}(s)\) 이라고 해보자. 그러면 다음 step에 대한 state value function도 주어진 term을 이용해서 유도할 수 있게 된다.

$$ \hat{v_{\pi}}(s_{t}) \leftarrow \hat{v_{\pi}}(s_{t}) + \alpha (\color{red}{r_{t+1} + \gamma \hat{v_{\pi}}(s_{t+1})} - \hat{v_{\pi}}(s_{t})) $$

앞에서 잠깐 언급한 target 개념을 다시 가져오면, 위 식에서는 빨간색으로 정의된 \( r_{t+1} + \gamma \hat{v_{\pi}}(s_{t+1}) \) 부분이 next state

의 state value를 바탕으로 구한 target이 되는 것이다. 그리고 전체 term인 \( r_{t+1} + \gamma \hat{v_{\pi}}(s_{t+1}) -\hat{v_{\pi}}(s_{t}) \) 은 target가 현재와의 차이 (error)가 되겠다.

결국 step이 진행되면 될수록, 우리가 가지고 있던 estimated state value function \( \hat{v_{\pi}}(s_{t}) \)은 target과 기존 estimated된 값 사이의 차이(difference)를 활용하면서 계속 업데이트되는 것임을 알 수 있게 된다. 물론 이때 next state에 대한 value도 알고 있어야 가능한 부분이기 때문에 어느정도 시간(temporal)에 대한 개념이 필요하다. 그래서 이런 학습 방법을 temporal difference learning (TD) 라고 표현한다. 그리고 위에 나왔던 공식의 예는 next state의 target만 가지고 estimate하는 방식으로 TD(0), 혹은 one-step TD라고 부르기도 한다. 이게 말이 되는 이유는 Sutton책의 6.3 Optimality of TD(0) 를 참고해보면 좋을거 같다. (나중에 기회가 되면 다룰지도...)

 아무튼 이런 내용을 실제 코드에서는 다음과 같이 써먹을 수 있다. 

state_values = [0.0 for _ in range(n_states)]

for _ in range(n_episodes):
  state = env.reset()
  while True:
    action = policy(state)
    next_state, reward, done = env.step(action)
    # Update current estimate for last state
    state_values[state] += alpha * (reward + gamma * state_values[next_state] - state_values[state])
    # If we reached the end of an episode, break
    if done:
      break
    state = new_state

 이렇게 되면, 한 episode가 진행되는 동안, done이 될 때까지 state_values list안에서 state value들이 계속 업데이트될텐데, MC랑 다른 것은 update된 state_values list를 한 episode내에서 계속 활용한다는 것이다. MC를 사용했으면 같은 episode내에서는 동일한 state_values list만 사용했을 것인데 말이다.