챕터 5, 6에서는 Monte Carlo(MC) 방법과 one-step temporal difference(TD) 방법을 배웠습니다. 사실 이 두 알고리즘은 완전히 별개가 아니라, 하나의 스펙트럼 하에서 양극단의 위치를 차지하고 있으며, 그 중간에 있는 n-step TD 방법에 대해 알아보겠습니다. (조지아텍 커리큘럼이 챕터 8을 먼저 읽는 것을 권하기 때문에 8부터 정리 후 7을 정리합니다)

7.1 n-step TD Prediction

어떤 상태 \(S_t\)의 가치함수 \(V(S_t)\)를 업데이트하려고 할 때, 이 상태값은 결국 다음 스탭 t+1에서 에피소드의 끝까지 얻는 보상(reward)들을 할인하여 더한 수익(return)입니다. Monte Carlo 방법에서는 아래와 같이 이 수익의 샘플 자체를 \(V(S_t)\)값으로 추정합니다.

반면, one-step TD에서는 다음 스탭의 보상 \(R_{t+1}\)만 샘플에서 취하고, 그 이후의 값들은 이미 추정되어 있는 다음 상태 \(S_{t+1}\)의 V값으로 대체합니다.

이것을 two-step TD로 확장하면, 바로 다음 뿐만 아니라 그 다다음 상태 t+2까지의 V값까지 이용해 대입을 할 수 있습니다.

이를 n-step TD로 확장한 것이 아래와 같습니다. 결국 n번째 step 이후의 값은 현재 추정치인 V값으로 대체하는 것이며, \(t+n \geq T\)일 경우, 즉 t+n이 terminal state T 이후로 넘어갈 경우에 모든 값은 0으로 대체합니다. 이 때 n-step return은 일반적인 총 수익과 동일합니다.

결국 Monte Carlo 방법은, n을 무한으로 확장한 \(\infty\)-step TD와 마찬가지가 되는 것입니다.

그런데 여기서 유의할 점은 n > 1 의 n-step return의 계산에는 현재 t에서 t+1으로 넘어가는 시점에서는 관찰할 수 없는 미래 보상과 상태들이 포함된다는 점입니다. 그렇기 때문에 상태-가치함수를 배우는 알고리즘은 아래와 같이 t+n 시점에서 업데이트가 진행됩니다. 이것을 n-step TD라고 합니다.

각 에피소드별로 n-1 스텝까지는 아무런 업데이트가 진행되지 않음을 알 수 있는데, 그 분만큼 에피소드가 끝나고 다음 에피소드가 시작하기 전에 추가 업데이트가 진행됩니다. 아래는 pseudocode입니다.

정책 \(\pi\)를 인풋으로 받고, 파라미터는 learning rate \(\alpha\)와 스텝 크기인 n이 있습니다. 처음에 V(s)를 무작위로 초기화보상(reward)들을 할인하여 더한 수익(return)입니다. Monte Carlo 방법에서는 아래와 같이 이 수익의 샘플 자체를 \(V(S_t)\)값으로 추정합니다. 그 다음 에피소드 별로 루프를 합니다. 여기서 \(\tau \geq 0\)이란 것은 \(t \geq n-1\)임을 체크하는 것과 동일한데, 앞서 언급했듯이 최소한 n 스텝이 지나야지 필요한 정보가 모이기 때문에 그때부터 업데이트를 시작함을 알 수 있습니다.

N-step return은 \(R_{t+n}\) 이후의 값은 가치함수 \(V_{t+n-1}\)을 이용합니다. 여기서 중요한 점은, n-step return의 기대값이 최악의 경우(worst-state)에도 \(V_{t+n-1}\)가 추정하는 값보다 더 낫다는 것이 보장된다는 것입니다. 아래를 error reduction property라고 하며, 이 속성을 이용해 모든 n-step TD 방법들이 올바른 prediction으로 수렴한다는 것을 증명할 수 있습니다.

어떤 n값이 좋은가에 대해서는 문제마다 다르겠지만, 일반적으로 아래에 보는 것과 같이 최적은 극단의 TD 방법과 MC 방법보다는 어느 중간값에 위치함을 알 수 있습니다.

7.2 n-step Sarsa

이 섹션에서는 n-step 방법이 prediction 말고도 control에서 사용되는 것을 살펴봅니다. 이전 챕터에서 다룬 Sarsa를 one-step Sarsa, 즉 Sarsa(0)이라 부를 것이고 여기에서는 n-step Sarsa를 살펴볼 것입니다. 요지는 간단한데, 상태(state)를 상태-행동 쌍(state-action pair)로 바꾸고 \(\epsilon\)-greedy 정책을 사용하면 됩니다.

먼저, 위와 같이 이전의 식에서 V를 Q함수로 대체하는데 \(t+n\geq T\)일 경우에는 \(G_{t:t+n}=G_t\)로 둡니다. 그러면 n-step Sarsa의 업데이트 식은 아래와 같습니다.

다음은 n-step Sarsa의 pseudocode입니다.

Expected Sarsa의 경우도 비슷한데,

여기서 V값을 확률을 고려한 기대값으로 대체하면 됩니다.