Monte Carlo methods - Importance Sampling

Importance의 필요성에 대해

이 전 글에서 언급했던 내용을 다시 복습해보면 아래와 같다. 

 

off-policy의 단점: 한번 try했던 policy가 가장 best임에도 불구하고,

random하게 생성된 policy로 진행이 되어 이전 best policy에 대한 가치를 제대로 반영 하지 못함

→ randomly하게 선택했을 때의 distribution과(behavior policy) 

     목표하는 것의 distribution(target policy)이 일치 하지 못할 때

→ 해결책: importance sampling을 사용하여 해결함

 

 

the importance sampling ratio

The relative probability of the trajectory under the target and behavior policies

을 통해서 구할 수 있는 것 

 

 

Importance sampling

새로운 분포 q(x)를 적용해줌

원래는 

위의식인데, q(x)를 적용해줌으로써 새로운 분포를 사용할 수 있음

새로운 분포(importance sampling ratio) : p(x) / q(x) 

→ p(x) / q(x) 를 구하기 위해 아래 내용을 참고함

 

Importance sampling in off-policy method

b: behavior policy

pi: target policy 

위의 값을 알게되면 "(importance sampling ratio) : p(x) / q(x)"  를 근사화 하여 구할 수 있음

 

Importance sampling ratio 구하기

 

위의 필기에서 분자가 1이 되는게 아래 노란색 표시임

분자가 1인 이유는 target policy는 deterministic 하므로

behavior policy가 정해졌을 때 return값은 위와 같고,

위의 값을 참고하여 target policy에서의 return값을

위에서 추정한 Pt:T-1을 곱하여 구할 수 있음

Ordinary importance sampling vs. Weighted importance sampling

 

예를 들어, 각 episode별 11번 state에 있을때의 return값을 다 구한것이 {Gt}이고

거기에 가중치를 준것이 {Pt:..}라고 했을 때

Ordinary importance sampling:

총 return값의 합 Sigma(Gt)를 전체 episode에서 11번 state가 존재하는 episode의 개수로 나눠준 것

100*4, 200*3, 300*2 = 1600/3

즉, 위의 수식은

11번 state에 있는 episode가 총 60개라고 하면 분모는 60

분자는 각 episode에서 얻은 return 값에 importance ratio를 곱해준 값임

Weighted importance sampling(실제에서 더 많이 씀)

1600/(4+3+2) = 1600 / 9

위의 식에서 분자는 ordinary sampling과 같으나,

분모에 importance sampling ratio를 적용해서 하는 것임

 

Weighted Importance Sampling using Incremental Mean

여기서 W = importance sampling ratio, 초기값은 1임

W는 아래와 같이 updated됨

원래 이식은 아래와 같은데, target policy는 deterministic 하므로 1로 표현할 수 있음

target policy가 deterministic 하다고 함은

우리가 역으로 목적지에서 출발점으로 역계산(reverse order)을 통해 update시키므로

항상 behavior가 최적의 목적지로 가기위해서

아래식의 분자는 1이 됨

Monte Carlo method의 단점

episode가 너무 길거나, 끝나지 않는 episode이면(continuous tasks)

return값을 계산할 수 없으므로 temporal difference learning을 사용함