3.5 Off-policy prediction via Importance Sampling

이전 챕터에 배웠던 Learning control methods 는 딜레마가 있습니다.

optimal behavior을 조건으로 action value를 배우는데

모든 action으로 explore하기 위해서는 optimal하지 않은 action도 또한 선택해줘야한다는 것입니다.

Optimal한 값을 찾기 위해 Optimal하지 않은 action을 선택해야할 필요가 있다는게 좀 이상하기도 합니다.

*그러면 Exploratory policy를 하는 동시에 Optimal policy를 배우게 만들수도 있을까요? *

그렇게 하기 위해 On policy와는 달리 Policy 두개를 만들어 보겠습니다!

Policy하나는 Optimal policy가 되는 Policy를 배우고,다른 Policy는 Exploratory를 하며 Behavior을 생성합니다.*

배우는 Policy를 Target Policy, 생성하는 policy를 Behavior Policy라고 합니다.

$배우는 Policy = Target Policy$

$생성하는 Policy = Behavior Policy$

이러한 두개의 policy를 통하여 배우는 process를 off-policy learning 이라고 합니다.

On-policy와 Off-policy를 비교하면, On-policy가 좀더 간단합니다. Off-policy는 variance가 많고, Converge가 느리게 됩니다. 하지만 보통 off-policy 방법이 더 강력합니다. Off-policy를 좀 더 많은 분야에서 사용할수 있으며, Behavior policy와 target policy가 같을때 Off-policys는 on-policy를 포함한다고 할수 있습니다.

여기서는 prediction problem을 푸는 목적으로, target policy와 behavior policy가 고정되어있는 off-policy를 공부하도록 하겠습니다.

이 말은 예를들어 우리가 $v_\pi$ 와 $q_\pi$를 estimate하려고 하지만 우리는 b라는 policy를 따를 것입니다.(여기서 b는 $\pi$와 다른 policy입니다.) b는 behavior policy이고 $\pi$는 target policy입니다.

b를 따른 episode를 사용하여 $\pi$ value를 estimate하면서 $\pi$를 따른 action도 항상 같이 estimate하기 위해서는 b를 따를때 ㅠ를 따른 action도 같이 선택이 되어야 합니다.

그래서 $\pi(a \mid s)>0$ 은 $b(a \mid s)>0$을 의미하며 이것을 assumption of convergence라고 합니다.
Converage $b$은 $\pi$와 동일하지 않은 states에서 는 stochastic이어야 하고 Target policy $\pi$는 그 반대로 deterministic할 것입니다.

이러한 case가 특정 control problems에서 발생합니다.

Control에서 target policy는 현재의 action-value function을 estimate한것의 greedy policy 입니다. 쉽게 말해 value를 estimate했을때 가장 큰 value를 가져오는 policy 입니다.

이 policy는 behavior policy가 계속 stochastic하며 exploratory하는 도중에 deterministic optimal이 됩니다. 예를 들면 epsilon-greedy policy입니다.

하지만 여기 prediction problem에는 $\pi$가 변하지 않고 주어졌다고 전제하겠습니다.

거의 모든 off-policy는 importance sampling을 활용합니다.

이 importance sampling은 주어진 다른 sample 의 distribution 아래의 에서 expected value를 estimating 하는 general technique 입니다.

. Importance sampling을 off-policy에 적용을 한 것을 importance-sampling ratio 라고 합니다.

주어진 시작 state st에서 어떠한 policy $\pi$를 따른 state-action trajectory $A_t,S_{t+1},A_{t+1},.....,S_T$ 은 다음과같습니다.

$$pr\left \{ {A_t,S_{t+1},A_{t+1},.....,S_T\mid S_t,A_{t:T-1} \sim \pi} \right \}$$ $$= \pi(A_t \mid S_t)p(S_t+1 \mid S_t,A_t)\pi(A_{t+1} \mid S_{t+1})...p(ST \mid S_{T-1}, A_{T-1})$$ $$=\prod_{k=t}^{T-1}\pi(A_k \mid S_k)p(S_k+1 \mid S_k,A_k)$$

여기서 p는 state transition probability을 의미합니다. 그러므로 target policy와 behavior policy를 따른 relative probability 의 trajectories는 다음과 같습니다.

$$p_{t:T-1}$$ $$\doteq\frac{\prod_{k=t}^{T-1}\pi(A_t \mid S_t)p(S_k+1 \mid S_k,A_k) }{\prod_{k=t}^{T-1}b(A_t \mid S_t)p(S_k+1 \mid S_k,A_k)}$$ $$=\frac{\prod_{k=t}^{T-1}\pi(A_t \mid S_t)}{\prod_{k=t}^{T-1}b(A_t \mid S_t)}$$

Trajectories probability가 MDP에 따라 달라도 ( 보통 Unknown 입니다. ) numerator과 denominator에 둘다 나오기 때문에 cancel됩니다.

그래서 importance sampling ratio는 MDP에 의하여 변하지 않습니다.

여기서 time step은 episode가 증가함에 따른다고 하겠습니다. 만약에 첫 Episode가 100에 끝나면 다음 Episode는 101부터 시작합니다.

여기서 state s 가 visited한 모든 time step의 집합을 $\tau(s)$ 라고 denote 하겠습니다.

이것은 state s가 visit한 모든 time step 집합을 나타내기 때문에 every-visit method입니다.

반면, First-visit methods의 $\tau(s)$는 한 episode에서 first visit to s의 time step 만을 포함합니다.

또한, $T(t)$는 time을 따라 처음 termination 된 것을 denoted 하고

$G_t$ 는 $t$부터 $T(t)$까지의 return을 denote합니다. 그렇다면 $\left \{ Gt \right \}_{t\in \tau(s)}$ 는 state s 일때 retrun들 이고, $\left \{ p_t:T(t)-1) \right \}_{t\in \tau(s)}$는 corresponding importance ratios입니다.

$V_\pi(s)$를 estimate하기 위해서 ratio와 average로 return을 scale 합니다.

$$V(s)\doteq \frac{\sum_{t\in \tau(s)}p_{t:T(t)-1}G_t}{\left | \tau(s) \right |}$$

위의 식과 같이 Importance sampling이 위와 같이 간단한 average로 된다면, ordinary importance sampling 이라고 합니다.

Weighted 된 average로 importance 하는 방법도 있는데, 이것을 weighted importance sampling 이라고 합니다.

식은 다음과 같습니다.

$$V(s)\doteq \frac{\sum_{t\in \tau(s)}p_{t:T(t)-1}G_t}{\sum_{t\in \tau(s)}p_{t:T(t)-1}}$$

이 두개의 sampling은 biases 와 variances입니다. Ordinary importance-sampling estimaor은 unbiased하고,

weighted importance-sampling estimator은 biased 합니다.

그리고 Ordinary importance-sampling estimator의 variance는 unbounded합니다. 실제로 weighted estimator은 아주 lower variance하여서 많이 쓰입니다!!

Reference

• Reinforcement Learning: An Introduction Richard S. Sutton and Andrew G. Barto Second Edition, in progress MIT Press, Cambridge, MA, 2017