강화학습 - (17) 중요도 샘플링

강화학습

중요도 샘플링 (Importance Sampling)

중요도 샘플링이랑 다른 분포에서 샘플링된 값을 가지고, 구하고자 하는 분포(타깃 분포)에서의 기댓값을 유추하는 방법이다.

랜덤 변수 $x$가 분포 $b$에서 샘플링 되었다고 가정해보자:

Sample: $x ~ b$

Estimate: $\mathbb{E}_{\pi}[X]$

여기서 우리는 $X$의 기댓값을 구하고 싶지만, 분포 $b$에서의 샘플 평균을 그대로 사용할 수는 없다.

왜냐하면 이 방식으로 구하게 되면 타깃 분포에서의 기댓값이 아닌 분포 $b$에서의 기댓값이 구해지기 때문이다.

 

먼저 기댓값의 정의를 다시한번 살펴보자:

(0)$\mathbb{E}_{\pi}[X] \dot{=} \sum_{x \in X} x\pi(x)$

(1)$= x \pi(x) \frac{b(x)}{b(x)}$

(2)$= x \frac{\pi(x)}{b(x)} b(x)$

(3)$= x \rho(x) b(x)$

(4)$= \mathbb{E}_b [X_{\rho}(X)]$

 

(0) $X$의 기댓값은 일어날 수 있는 모든 결과 $x$에 각 $x$가 일어날 확률 $\pi(x) $를 곱해 모두 더한 것이다.

(1) 그리고 각 $x$에 분포 $b$에서의 확률을 각각 분자와 분모에 곱해준다.

이는 1을 곱한것과 같기 떄문에 수식상으로는 아무 문제가 없다.

(2) 그리고 $\pi$와 분자의 $b$를 맞바꾸면 비율이 된다.

이 비율을 중요도 샘플링 비율이라고 부른다. 

(3) 이 비율은 보통 $\rho$로 표기한다.

(4) $x$와 중요도 샘플링 비율을 새로운 랜덤변수로 간주한다면,

우리는 이를 $b$에서의 기댓값으로 바꿀 수 있다.

 

위에서 보이는 중요도 샘플링은 매우 복잡해 보일 수 있다.

하지만 이를 몬테카를로 샘플링을 사용해 표현하면 매우 쉬워진다.

우리는 그저 $x$가 일어날 $X$에서의 확률과 $b$에서의 확률의 비율을 구해 곱해주고, 이를 평균하면 된다.

$\mathbb{E}_b \approx \frac{1}{n} \sum^n_{i=1} x_i \rho(x_i)$

$x_i ~ b$

 

예제)

위 두가지 다른 분포 $b$와 $\pi$를 통해 중요도 샘플링을 예를 들어 살펴보자.

먼저 우리는 실제 $X$ 기댓값이 2.2라고 가정한다.

 

분포 $b$에서 샘플링을 한 값이 각 $x = [1, 3, 1]$ 이라고 하자.

$b$에서 이와 같이 샘플링될 확률은 각각 $[.85, .5, .85]$ 이다.

그리고 이를 $\pi$에서 샘플링 할 확률은 각각 $[.3, .1, .3]$ 이다.

중요도 샘플링을 통해 샘플 평균을 구하는 방법은 다음과 같다:

$\frac{1}{n} \sum^n_{i=1} x_i \rho(x_i)$

$\frac{(1 \times \frac{.3}{.85}) + (3 \times \frac{.1}{.05}) + (1 \times \frac{.3}{.85})}{3} = 2.24$

이는 우리가 위에서 본 기댓값 2.2와 유사한 수치이다.

 

몬테카를로 예측 (Monte-Carlo Prediction)

그렇다면 이를 몬테카를로 예측에서 어떻게 사용할 수 있을까?

다음과 같이 각 에피소드들의 리턴이 있다:

$average(Returns[0], Returns[1], Returns[2])$

 

우리는 행동 정책 $b$를 따라 몬테카를로 기법을 통해 얻어진 결과값들은 정책 $\pi$를 학습시키는데 그대로 사용될 수 없다.

이 역시 중요도 샘플링을 적용해야 한다:

$average(\rho_0 Returns[0], \rho_1 Returns[1], \rho_2 Returns[2])$

 

하지만 이 실제 샘플들의 경우 비율 $\rho$를 어떻게 구할 수 있을까?

실제 샘플에서 중요도 샘플링을 하려면 우리는 각각 정책들의 궤적(trajectory)이 필요하다.

$\rho = \frac{\mathbb{P}(trajectory \; under \; \pi)}{\mathbb{P}(trajectory \; under \; b)}$

궤적의 비율을 맞추면, 이는 보상을 통한 결과값의 비율도 맞출 수 있다.

 

궤적의 비율

궤적의 분포란 임의의 상태 $S_t$에서 임의의 행동 $A_t$를 선택한 후 벌어질 수 있는 확률들의 집합니다:

$P(A_t, S_{t+1}, A_{t+1}, ..., S_T | S_t, A_{t:T})$

이 확률은 $S_t$부터 $S_T$까지 도달할떄까지의 모든 확률이다.

마르코프 속성으로 인해 우리는 이 확률을 작은 확률들로 분리할 수 있다:

$b(A_t|S_t) p(S_{t+1}|S_t, A_t) \;\times\; b(A_{t+1}|S_{t+1}) p(S_{t+2}|S_{t+1}, A_{t+1}) ... p(S_T | S_{T-1}, A_{T-1})$

그리고 이를 곱셈 표기법으로 합쳐서 표현할 수 있고, 이를 $b$에서의 궤적의 확률 분포로 정의한다:

$\prod_{k=t}^{T-1} b(A_k|S_k) p(S_{k+1}|S_t,A_k)$

 

이제 위에서 정의한 궤적의 확률 분포를 비율 수식에 대입해보자:

$\rho_{t:T-1} \dot{=} \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)p(S_{k+1}|S_k,A_k)}{b(A_k|S_k)p(S_{k+1}|S_k,A_k)}$

$\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)}$

각각의 상태 전환 확률은 분모와 분자에서 제거할 수 있기 때문에, 위 수식이 최종 비율이 된다.

 

위의 비율은 가치함수의 기댓값에도 대입하여 사용할 수 있다.

가치함수는 에이전트의 정책이 학습하는데 매우 중요하기 때문에, 이 역시 비율을 맞추어 계산해 주어야 한다.

$v_{\pi}(s) = \mathbb{E}_b[\rho_{t:T-1}G|S_t = s]$

 

아래는 Off-Policy 에서의 몬테카를로 예측 알고리즘이다: