References
PRIORITIZED EXPERIENCE REPLAY (2016, ICLR)
Pattern Recognition and Machine Learning (2006, Christopher Michael Bishop)

What is Importance Sampling?

Importance Sampling(IS)이란 확률 분포 $p(x)$를 따르는 확률변수 $x$가 있고, $x$에 대한 함수 $f(x)$의 기댓값 $\mathbb{E}_{x\sim p}[f(x)]$를 Monte Carlo method를 이용해서 추정을 할 때 본래의 확률 분포 $p(x)$가 아닌 다른 확률 분포 $q(x)$에서의 sampling으로 $\mathbb{E}_{x\sim p}[f(x)]$의 값을 추정하고자 하는 방법이다.

Importance Weight

위에서 언급한 것처럼 $\mathbb{E}_{x \sim p}[f(x)] = \int{f(x)p(x)}dx$ 를 직접 계산할 수 없을 때 아래와 같이 Monte Carlo method를 이용해서 $f(x)$의 기댓값을 근사 시킬 수 있다.

이때 원래의 확률 분포 $p(x)$가 아닌 새로운 새로운 확률 분포 $q(x)$에서의 sampling으로 $\mathbb{E}_{x \sim p}[f(x)]$를 얻고자 할 때 위 기댓값 계산식을 아래와 같이 수정할 수 있다.

여기서 Monte Carlo method에 의한 근사를 수행하면 아래와 같이 표현된다.

이때 $\frac{p(x)}{q(x)}$를 importance weight라고 하며 확률 분포 $q(x)$에서 sampling을 수행해서 $\mathbb{E}_{x\sim p}[f(x)]$를 추정했을 때 발생하는 bias를 보정하는 역할을 한다. 이때 importance sampling의 성공 여부는 새로운 분포 $q(x)$는 원 분포 $p(x)$와 얼마나 잘 맞는지에 달려 있다.

Utilization of Importance Sampling in PER

위 식에서 $x$의 차원수가 늘어남에 따라 합산항이 커지며, 이때 대부분의 값들은 $x$공간상의 상대적으로 작은 부분에 몰려있다. 이러한 고차원 문제에서 $\mathbb{E_{x\sim p}[f(x)]}$를 추정할 때 $p(x)$에서 uniform sampling하는 것은 비효율 적이다. $p(x)$가 큰 구역에서 표본들을 선택하거나 $p(x)f(x)$가 큰 구역에서 sampling을 하는 것이 이상적이다. Prioritized Experience Replay(PER)에서는 이를 위해 TD-error($\delta$)값으로 도출한 priority기반의 새로운 분포 $q(x)$하에서 transition sampling을 하고자 한다. Importance sampling의 목적이 $x\sim p(x)$ 상황에서 $\mathbb{E}_{x\sim p}[f(x)]$를 추정하는 것이라고 할 때, 각 요소는 DQN과 같은 가치기반 DRL에서 각각 다음과 같다.

• $x$ : Replay buffer내부의 개별 transition

• $p(x)$ : transition $x$가 sampling될 확률 (buffer에 $N$개의 transition이 있을때 $p(x) = \frac{1}{N}$)

• $f(x)$ : $x$의 loss값

• $\mathbb{E_{x\sim p}}[f(x)]$ : Replay buffer안에 들어있는 전체 transition의 loss의 평균값.

위에서 언급 했듯이 $p(x)f(x)$가 큰 구역에서 sampling을 하는 것이 이상적일 때, $p(x)f(x)$에서 $p(x) = \frac{1}{N}$로 상수이다. 또한 $f(x)$값 즉, $x$의 loss값의 크기는 $|\delta|$의 크기에 의존하므로 $|\delta_a| <|\delta_b|$ 이면 $p(x_a)f(x_a) <p(x_b)f(x_b)$를 만족한다. 이 말은 즉, $|\delta|$가 큰 구간에서 sampling을 집중해서 하는 것이 유리하다는 말이된다. 이는 개별 transition의 priority를 $|\delta|$로서 측정하고 이를 이용해서 priority가 높은 transition을 집중적으로 sampling하고자 하는 PER의 본질적인 아이디어와 일치한다. PER에서는 원분포를 대신하는 새로운 분포 $q(x)$를 아래와 같이 설정한다.

이때 $\rho_i =|\delta|+\epsilon$이다. $q(x)$가 위와 같을 때 importance sampling weight는 다음과 같다.

$\beta = 1$ 일때 $\frac{p(x)}{q(x)}$와 완전 동일한 형태인 것을 볼 수 있다.