Importance Sampling

지금까지 Monte-Carlo Control과 Temporal-Difference Control 을 살펴보았습니다. 사실은 두 방법이 다 on-policy reinforcement learning입니다. 여기서 새로운 개념을 하나 알고 갈 필요가 있습니다.

1. On-Policy vs Off-Policy

다시 Sarsa의 알고리즘을 살펴보겠습니다. 아래와 같이 Sarsa에서는

• Choose A from S using Policy derived from Q

• Choose A' from S' using Policy derived from Q

action을 선택하는 것이 두 부분이 있습니다. 보면 둘 다 공통적으로 "using Policy derived from Q"가 사용된다는 것을 알 수 있습니다.

이 말은 즉 현재 policy로 움직이면서 그 policy를 평가한다는 것입니다. 위 알고리즘에서 보면 에이전트가 실제로 움직인 Q function을 현재의 Q function을 업데이트합니다. 따라서 현재 policy위에서 control(prediction + policy improvement)을 하기 때문에 on-policy라고 생각해도 좋습니다.

하지만 on-policy 는 한계가 있습니다. 바로 탐험의 문제입니다. 현재알고있는 정보에 대해 greedy로 policy를 정해버리면 optimal에 가지 못 할 확률이 커지기 때문에 에이전트는 항상 탐험이 필요합니다. 따라서 on-policy처럼 움직이는 policy와 학습하는 policy가 같은 것이 아니고 이 두개의 policy를 분리시킨 것이 off-policy입니다. Silver는 수업에서 Off-policy를 다음과 같이 정의합니다.

Evaluate target policy $$\pi(a|s)$$ to compute $$V\pi(s)$$ or $$q\pi(s,a)$$ While following behaviour policy $$\mu(s|a)$$

Off-policy는 다음과 같은 장점이 있습니다.

• 다른 agent나 사람을 관찰하고 그로부터 학습할 수 있다

• 이전의 policy들을 재활용하여 학습할 수 있다.

• 탐험을 계속 하면서도 optimal한 policy를 학습할 수 있다.(Q-learning)

• 하나의 policy를 따르면서 여러개의 policy를 학습할 수 있다.

2. Importance sampling

위에서 Off-policy learning이 어떤 것인지 배웠습니다. 하지만 다른 policy로부터 현재 policy를 학습할 수 있다는 근거가 무엇일까요? "importance sampling"이라는 개념은 원래 통계학에서 사용하던 개념으로 아래와 특정한 분포의 값들을 추정하는 기법중의 하나입니다.https://en.wikipedia.org/wiki/Importance_sampling

In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest

어떤 값을 추정하는데 가장 기본적인 방법은 그냥 random하게 찍어보는 것입니다. 이미 저희가 배웠다시피 이러한 process 표현하는 말은 "monte-carlo"로서 Monte-Carlo estimation이라고 합니다. 하지만 너무 광범위하게 탐색하기도 하고 어떠한 중요한 부분을 알아서 그 위주로 탐색을 하면 더 빠르고 효율적으로 값을 추정할 수 있고 그러한 아이디어가 바로 "Importance Sampling"입니다. 아래는 Importance Sampling에 대해서 설명해놓은 강의입니다. 원래 통계학의 개념이기 때문에 저에게는 생소해서 더 여러웠던 부분인 것 같습니다.https://www.youtube.com/watch?v=S3LAOZxGcnk

P와 q라는 다른 distribution이 있을 때 q라는 distribution에서 실재로 진행을 함에도 불구하고 p로 추정하는 것처럼 할 수 있다는 것입니다. 강화학습에서도 policy가 다르면 state의 distribution은 달라지게 되어 있습니다. 따라서 다른 distribution을 통해 추정할 수 있다는 개념을 그대로 가져와서 다른 policy를 통해서 얻어진 sample을 이용하여 Q 값을 추정할 수 있다는 것입니다. 일종의 trick이라고 할 수 있을 것 같습니다.

위의 내용을 David Silver교수님은 아래와 같이 설명하십니다. f(X)라는 함수를 value function이라고 생각하고 강화학습에서는 이 value function = expected future reward를 계속 추정해나가는데 P(X)라는 현재 policy로 형성된 distribution으로부터 학습을 하고 있었습니다. 하지만 다른 Q라는 distribution을 따르면서도 똑같이 학습할 수 있는데 단, 아래와 같이 간단히 식을 변형시켜주면 됩니다. $$Q(X)$$을 곱해주고 나눠주면 됩니다.

Off-Policy 또한 MC와 TD로 갈립니다. Off-policy MC는 아래와 같습니다. 에피소드가 끝나고 return을 계산할 때 아래와 같이 식을 변형시켜줍니다. 각 스텝에 reward를 받게 된 것은 $$\mu$$라는 policy를 따라서 얻었던 것이므로 매 step마다 $$\pi/\mu$$를 해줘야합니다. 따라서 Monte-Carlo에 Off-policy를 적용시키는 것은 그리 좋은 아이디어가 아닙니다.

Off-Police TD에서는 MC 때와는 달리 Importance Sampling을 1-step만 진행하면 됩니다.

MC때와 비교하면 Variance가 낮아지기는 했지만 여전히 원래 TD에 비하면 Importance sampling때문에 높은 variance를 가지고 있습니다. Off-policy learning을 할 때 Importance sampling말고 다른 방법을 생각할 필요가 있습니다. 바로 여기서 유명한 Q learning알고리즘이 나오게 됩니다.