본문으로 바로가기

지금까지 봐왔던 Off-policy는 importance-sampling weight를 discount return에 곱하는 식으로 했었다. 그런데 이것은 discounted rewards의 합이라는 내부 구조를 고려하지 않고 그저 return 하나로만 생각했다. 이렇게 하면서 생기는 문제는 분산이 늘어난다는 것이다.

예를 들어, 에피소드가 길고 $\gamma$가 1보다 많이 작다고 생각해보자. 그냥 정확하게 에피소드가 100이고, $\gamma=0$이라고 하자. 첫 번째 time step에서 return은 $G_0=R_1$이지만, importance sampling ratio는 100개 $\frac{\pi(A_0|S_0)}{b(A_0|S_0)}\frac{\pi(A_1|S_1)}{b(A_1|S_1)}\cdots\frac{\pi(A_{99}|S_{99})}{b(A_{99}|S_{99})}$를 곱한다. ordinary importance sampling에서는 이 모든 걸 곱해서 return이 scale 되지만, 사실 첫 번째 요소 $\frac{\pi(A_0|S_0)}{b(A_0|S_0)}$만으로 scale해야한다. 나머지 99개 요소는 보상을 받고난 이후 return은 이미 결정되어 있기 때문에 아무런 관련이 없다. 즉, return과 expected value과 모두 독립적이라서, expected update를 바꾸지는 않지만 분산을 엄청 늘려버리는 꼴이 된다. 심지어 무한으로 만들 수 있기에 이런 크면서도 아무런 관계없는 분산을 피하기 위한 아이디어에 대해서 다룬다.

아이디어의 핵심은 termination의 확률이나 부분적으로 termination이 되었는지 정도(degree)에 따라 discounting 하는 것이다. 한 step에서 partly termination은 $1-\gamma$에 $R_1$을 곱하는 것으로 표현하고 두 step 이후 partly termination을 $(1-\gamma)\gamma$에 $R_1+R_2$을 곱하고, 그 뒤로 계속 $\gamma$와 $R_{t}$를 계속 추가해서 동일하게 적용한다. 이런 식으로 적용해도 이전의 보상의 합과 동일하다.


하지만 이렇게 나타내기엔 너무 길기 때문에 간단히 하기 위해, 일정 구간(partial)에 discount가 없는(flat) return을 다음과 같이 표현하며, 이를 flat partial return이라 한다.

이를 이용해서 위 식을 flat partial return으로 표현하면 다음과 같다.

이제 보상의 수에 맞게 importance sampling을 곱해서 scale하게 된다. 그럼 variance도 이전보다는 줄어든다.

ordinary importance sampling estimator는 다음과 같이 정의한다.

weighted importance sampling estimator는 다음과 같이 정의한다.

이 두 estimator를 discounting-aware importance sampling estimator라고 한다. discount rate에 대해 고려는 하고 있지만, $\gamma=1$일 때는 이전과 완전히 똑같이 된다.

이전에는 discounting이 return에 들어가는 지 고려하지 않았기 때문에 몰랐다고 생각하고 이번에는 고려했기 때문에 discounting이 들어간 것을 안다(discounting-aware)라고 표현한 것 같다.



댓글을 달아 주세요

  1. Favicon of https://nmoonma7.tistory.com BlogIcon nmoonma7 2019.04.10 20:03 신고

    좋은 글 잘 보고 있습니다. 다만 중간에 R(t+1) 값들의 합은 근사가 아니라 교재 표현이 맞는것 같습니다. (1-r)이 곱해져 있는 항들의 합이 (1-r^T-t-1) * R(t+1)이고 맨 마지막 항이 r^T-t-1 * R(t+1) 이므로 앞의 r^T-t-1이 결국 사라지니까 R(t+1)만 남지 않을까요?