n-Step Return vs. Lambda-Return

n-Step Return vs. $\lambda$-Return

---

이 글의 목적은 n-Step Return과 $\lambda$-Return의 차이점에 대하여 간락하게 정리하는 것이다.

최근에 읽은 GAE 논문에서 Advantage Function에 비슷한 형태가 나오기 때문에 그 전에 먼저 TD($\lambda$) 의 개념을 정확히 알고 넘어가고자 한다. 각 그림과 설명은 실버 강의 자료와 서튼 책에서 가져온 것이다.

---

먼저 TD의 step을 어디까지 볼 것인지에 대한 n-Step Prediction이다. 보이는 것처럼 TD(1-step)부터 시작하여 2-step, 3-step, ... , n-step, ... 에피소드까지 생각하는 Monte Carlo가 있다. 

우리는 맨 위의 수식처럼 n=1, n=2, n=$\infty$를 생각해볼 수 있다. 그리고 n-step return이라면 두 번째 수식과 같이 생각해볼 수 있고, n-step TD는 마지막 수식처럼 작성할 수 있다.

다음으로 보이는 그림은 random walk 예제에서 A, B, C, D, E, ... 하여 총 19 states가 있다고 한다면 다음으로 나오는 그래프는 첫 번째 10 episodes에 대한 Average RMS error이다. 그래프를 보면 n이 높으면 높을수록 점점 경사가 빠르게 올라가고, $\alpha$에 따라서 error가 변하기도 한다.

최적의 성능은 n=4, $\alpha$=0.4 정도 되는 것 같다.

이러한 n-Step Return은 한계점이 있다. 바로 환경이 바뀌면 최적의 n 또한 변한다는 것이다. 따라서 해결하고자 나온 것이 바로 아래와 같은 $\lambda$-Return이다.

$\lambda$-Return의 경우 왼쪽의 그림처럼 첫 번째 상태에서 모든 n-Step Return을 평균낸 것이라고 볼 수 있다. 다시 말해 n-Step Return은 여러 reward를 평균낸 것이고, $\lambda$-Return은 여러 n-Step Return을 평균낸 것이다. 

$\lambda$-Return은 여러 n을 평균낸 것이기 때문에 아까 다뤘던 n-Step Return과는 다르게 좀 더 robust하다고 말할 수 있다.

이 그림에서 말하고 싶은 것은 시간에 따라서 $\lambda$에 의해 가중치가 dacaying된다는 것이다. 다시 말해 $\lambda$가 작으면 작을수록 위의 그림에서 앞 부분에 점점 더 가중치를 두고, $\lambda$가 크면 클수록 위의 그림에서 뒷 부분에 점점 더 가중치를 둔다. (추가적으로 $\lambda = 0$이면 One-Step TD update이고, $\lambda = 1$이면 Monte-Carlo update가 된다.)  

또한 이러한 방법을 "Geometric weighting"이라고 한다. 이 방법을 사용함으로써 좀 더 효율적으로 computation할 수가 있고, TD(0)과 TD($\lambda$)가 동일한 computation cost를 가진다.

지금까지 다뤘던 방법이 바로 Forward-View TD($\lambda$)이다. 보이는 것처럼 굉장히 직관적인 그림이 나온다. 다시 한 번 말하자면, 지금의 상태에서 각 step마다의 return들을 평균내는 것이다.

또한 세 번째의 문장을 보면, MC처럼 episode가 끝나야 계산이 가능하다.

왼쪽에 보이는 그래프가 $\lambda$-Return이고, 오른쪽에 보이는 그래프가 n-Step Return이다. n-Step Return과 다르게 $\lambda$-Return이 좀 더 smooth한 곡선이고, $\alpha$에 대하여 덜 민감하다는 것을 알 수 있다.

지금까지 다뤘던 Forward-View TD($\lambda$)와 다른 Backward View TD($\lambda$)도 있다.

Forward-View TD($\lambda$) 앞에서 말했다시피 episode가 끝나야 update가 가능하다. 다시말해 offline update이다. 반대로 Backward View TD($\lambda$)는 online, every step update이고, incomplete sequences에서 update를 한다.

첫 번째 문장에서 보이듯이, 과거를 보면서 현재 value에 영향을 미친 state가 무엇인지를 찾는 것을 "Eligibility Trace"라고 한다. 하지만 그림에서도 보이듯이 많은 연산량과 메모리가 필요하다. 쉽게 말해 computational cost가 증가한다는 것이다.

---

이 글의 목적은 GAE논문을 읽기 전에 n-Step Return과 $\lambda$-Return의 차이점에 대하여 간략하게 살펴보는 것이다. 더 나아가서 Eligibility Trace에 대해 더 알고 싶다면 실버 강의와 서튼책을 참고하기 바란다.