Off-policy Prediction via Importance Sampling
control을 학습하는 방법은 최적이라고 생각하는 행동을 하면서 행동 가치를 학습해야하지만, (최적의 행동을 찾기 위해) 모든 행동을 탐험(최적이 아닌 행동)을 해야한다는 것이다. 탐험하는 정책을 통해 어떻게 최적의 정책을 학습하는 걸까? 이전 절에서 나온 on-policy 방법은 최적의 정책 대신 탐험을 계속하도록 하는 최적에 가까운 정책을 하면서 타협을 한 것이다. 좀 더 간단한 방법은 두 개의 정책을 사용해, 하나는 최적의 정책을 학습하고, 다른 하나는 직접 행동하는 정책을 두는 것이다. 전자를 target policy, 후자를 behavior policy라고 부른다. target policy가 아닌 데이터에 의해서 배우는 학습 방법을 off-policy learning이라 부른다.
on-policy가 보통 더 단순하다. on-policy는 off-policy 입장에서 보면 target policy와 behavior policy가 같은 것이다. off-policy는 추가적으로 알아야할 개념과 표기법이 필요하고, 다른 정책의 데이터로 학습하기 때문에 분산(variance)이 더 크고 수렴속도가 느리다. 하지만 off-policy가 더 강력하고 다른 실생활에서 활용할 수 있는 경우가 더 많다. 예를 들어, 사람이 행동해서 만든 데이터같은 학습하지 않는 controller로도 학습을 할 수 있다.
이번 절에서는 target policy와 behavior policy가 고정된 prediction 문제에 대해서 얘기할 예정이다. 즉, $v_\pi$와 $q_\pi$를 구하는 문제를 다룰 것이며, target policy를 $\pi$, behavior policy를 $b$라 부를 것이다.
$\pi$에 의해 취해지는 모든 행동은 $b$에 의해서도 취해져야 한다. 이를 coverage 가정이라고 한다. 이 가정을 따르기 위해서는 $b$는 $\pi$와는 다르게 확률적(stochastic)으로 행동을 결정해야 한다. $\pi$는 control 문제에서는 보통 현재 행동 가치에 대한 determinstic greedy policy이다. 결국 정책은 deterministic optimal policy가 되고 behavior policy는 여전히 확률적이고 탐험하는 정책으로 남아있다. 예를 들면 $\epsilon$-greedy와 같다. 하지만 아까도 말했듯이 이번 절에서는 prediction 문제를 다루므로 두 policy 모두 고정되어있다고 가정한다.
off-policy는 다른 정책에 의해 얻어진 샘플의 분포로 가치를 추정(estimate)하는 방법인 importance sampling을 사용한다. target policy와 behavior policy에서 발생하는 trajectory들의 상대적인 확률인 importance sampling 비율(ratio)을 return에 곱(weight)한다. 어떤 정책 $\pi$에 의해 trajectory $A_t, S_{t+1}, A_{t+1}, ..., S_T$가 발생할 확률은 다음과 같이 나타낼 수 있다.
여기서 $p$는 상태 전이 확률(state-transition probability)이다.(이전에 나온 dynamic의 변형 형태) 결국 target policy와 behavior policy에서 발생하는 trajectory 의 상대적인 확률은 다음과 같다.
trajectory 확률은 상태 전이 확률에 달렸지만 보통은 알 수 없는 값이지만, 분모와 분자에 같은 값이 있으므로 제거된다. 결국 importance sampling ratio는 MDP가 아닌 두 개의 정책과 시퀀스(trajectory)에만 달려있다.
이제 이 behavior policy에 의해서 구해진 return이 있다면
$$\mathbb{E}[G_t|S_t=s] = v_b(s)$$
이를 importance sampling ratio를 곱해주는 것으로 target policy의 expected value를 구할 수 있다.
$$\mathbb{E}[\rho_{t:T-1}G_t|S_t=s] = v_\pi(s)$$
이제 Monte Carlo 알고리즘에 적용할 것이다. 그 이전에 알아두어야할 표기가 몇 가지가 있다.
- $t$는 말 그대로 time step이지만, episode 구분도 할 수 있게 계속 이어서 값을 가진다. 예를 들어 100 time step에서 끝났다면 그 다음 에피소드 첫 번째 step은 1이 아닌 101에서 시작한다.
- $\mathcal{J}(s)$는 every-visit 방법에서는 방문했던 모든 time-step이 저장되고, first time step에서는 처음 방문했던 time step만 저장된다.
- $T(t)$ 한 episode 처음 끝난 time step 크기로 importance sampling 비율을 정할 때 사용한다.
이렇게 간단한 average 방식을 ordinary importance sampling이라 한다. 이것 대신에 weighted average를 이용한 weighted importance sampling도 있다. (이 때 분모가 0이라면 0값으로 처리)
이해를 위해 만약 first-visit MC 방법을 한다고 하자. weighted 방법의 경우 return을 한 번 얻었다고 하자. 그러면 분모, 분자값이 서로 삭제되어 ratio와는 상관없이 return값이 된다. 하지만 $v_b(s)$에 대한 expectation이기 때문에 약간 통계학적으로 약간 편향(bias)된 것으로 볼 수 있다. 반면에, ordinary 방법은 항상 $v_\pi$에 대한 expectation을 가질 수 있다.(즉, 편향되지 않는다는 얘기) 물론 이것은 return 1번만 얻었을 경우이므로 좀 극단적인 경우이다. 또다르게 생각해보면 ratio가 10이라면 ordinary 같은 경우는 10배 더 곱한 셈이므로 target policy을 표현하기 위해 했다고는 하지만 실제로 얻은 return값과 너무나 다른 값이 된다.
위 두 개의 방법은 편향과 분산(biases and variances)에 있어 차이를 보인다.
- Ordinary importance sampling은 편향이 없지만(unbiased) 분산에 있어 제한이 없어서 엄청 커질 수도 있다.(ratio에 제한이 없으므로)
- Weighted importance sampling은 편향이 약간 있지만, weight 곱하는 게 커봐야 1이므로 분산이 그리 크지 않다.
만약 return값이 제한이 없다면 ratio 분산이 무한으로 갈수도 있다. 하지만 weighted 방식은 수렴하기에, 실제로 분산이 확실히 더 작고, 더 선호되는 편이다. 하지만 나중에 approximate 방법에 대해 얘기할 때, ordinary 방식이 더 쉽기 때문에 나중에도 다룰 예정이다.
every-visit 방법에 있어서는 둘 다 편향되지만, 샘플(return) 수가 늘어날수록 점점 0에 가까워진다. 실제로 every-visit이 더 선호되는데, 굳이 방문했던 모든 상태를 저장하지 않고 근사(approximation)하는 방법으로 쉽게 바꿀 수 있기 때문이다. 이 방법은 그 다음 절에서 다룬다.
