Monte Carlo Methods in RL (2)

이번 포스팅에서는 저번 포스팅에 이어서 몬테카를로 방법에 대해 알아보겠습니다. 특히 저번 포스팅에선 개념과 on-policy 방법이 주였다면, 이번 포스팅에서는 off-policy 방법을 살펴보겠습니다.

Monte Carlo Iteration (Off-policy)

Off-policy Learning

Off-policy Learning은 목표 정책 (Target Policy, $\pi$)와 행동 정책 (Behavior Policy, $b$)를 구별하여 학습하는 방법을 일컫습니다. 즉 에이전트가 움직일 때는 행동 정책을 따라서 움직이지만, 거기에서 얻어진 보상으로는 목표 정책을 학습하는 것 입니다. 행동 정책을 별도로 운용함으로써 탐색과 활용의 균형을 유지할 수 있습니다. Off-policy learning을 할 때, 보통 목표 정책 $\pi$는 deterministic 하게 정하고, 행동 정책 $b$는 stochastic 하게 결정합니다. 이때 주의할 점은 $\pi(a|s)>0$이면, $b(a|s)>0$이 만족해야되며, 이를 coverage 가정이라고 부릅니다.

Importance Sampling

Importance Sampling은 주어진 확률분포 아래 기대값을 계산할 때, 또 다른 분포를 이용하여 sampling한 결과로 계산하는 방법입니다. 즉 Importance Sampling이 등장하는 이유는 행동 정책을 이용하여 심플링한 결과로 목표 정책의 가치함수를 계산하기 위함입니다.

어떤 $S_{t}$에서 시작했을 때 종료 상태까지 뒤따르는 상태-행동 trajectory에 대한 확률은 아래와 같습니다. $$\begin{align*}\mathbb{P}&\left[\left.A_{t},S_{t+1},A_{t+1},\cdots,S_{T}\right|S_{t}, A_{t:T-1}\sim\pi\right]\\&=\pi(A_{t}|S_{t})\mathbb{P}(S_{t+1}|S_{t},A_{t})\pi(A_{t+1}|S_{t+1})\cdots\mathbb{P}(S_{T}|S_{T-1},A_{T-1})\\&=\prod_{k=t}^{T-1}\pi(A_{k}|S_{k})\mathbb{P}(S_{k+1}|S_{k},A_{k})\end{align*}$$

위 공식을 이용하면 행동 정책에 대한 확률과 목표 정책에 대한 확률의 비를 계산할 수 있고, 이를 Importance Sampling Ratio로 부릅니다. $$\rho_{t:T-1}=\frac{\prod_{k=t}^{T-1}\pi(A_{k}|S_{k})\mathbb{P}(S_{k+1}|S_{k},A_{k})}{\prod_{k=t}^{T-1}b(A_{k}|S_{k})\mathbb{P}(S_{k+1}|S_{k},A_{k})}=\prod_{k=1}^{T-1}\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}$$ 여기서 하나 알 수 있는 사실은 행동 정책과 목표정책의 비를 이용하면 $\mathbb{P}(s'|s,a)$를 몰라도 된다는 것 입니다.

행동 정책을 따라 에이전트가 얻은 보상은 $$\mathbb{E}\left[\left.G_{t}\right|S_{t}=s\right]=v_{b}(s)$$가 됩니다. 그런데 Importance Sampling Ratio를 이용하면, $$\begin{align*}\mathbb{E}\left[\left.\rho_{t:T-1}G_{t}\right|S_{t}=s\right]&=\sum\cdots\sum \rho_{t:T-1}\prod_{k=t}^{T-1}b(A_{k}|S_{k})\mathbb{P}(S_{k+1}|S_{k},A_{k})G_{t}\\&=\sum\cdots\sum\prod_{k=t}^{T-1}\pi(A_{k}|S_{k})\mathbb{P}(S_{k+1}|S_{k},A_{k})G_{t}=v_{\pi}(s)\end{align*}$$가 되어 목표 정책에 대한 가치함수를 계산할 수 있게됩니다.

위에서 importance sampling ratio 기반 보상 평균을 구하면 목표 정책에 대한 가치 함수를 얻을 수 있다는 사실을 알았느니, 이제 단순히 몬테카를로 방법을 적용하기만 하면됩니다. 몇 가지 notation을 정의하겠습니다. 여기에서는 만약 첫 에피소드가 $t=50$에서 끝났다면, 다음 에피소드의 시작을 $t=51$로 가정합니다.

• $\mathcal{J}(s)$: 상태 $s$를 방문 했을 때 모든 time steps의 집합
• $T(t)$: $t$부터 종료 상태에 도달까지 time step
• $G_{t}$: $t$부터 $T(t)$까지의 누적 보상

그러면 우리는 가치함수를 다음과 같이 추정해 볼 수 있습니다. $$V(s)=\frac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_{t}}{|\mathcal{J}(s)|}$$ 이렇게 계산하는 것을 ordinary importance sampling (OIS)이라고 부릅니다. 이를 가중 평균의 형태로 추정할 수도 있는데, $$V(s)=\frac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_{t}}{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}},$$ 이를 weighted importance sampling (WIS)이라고 부릅니다. OIS와 WIS의 비교를 위해 1개의 episode에 대한 first-visit 방법을 생각해보겠습니다. 이 경우 WIS의 분모와 분자가 약분되기 때문에 $v_{b}(s)$가 아닌 $v_{\pi}(s)$를 구하게 되어 bias가 발생할 수 있습니다. 반면에 OIS는 항상 unbiased합니다. 하지만 만약 분모가 상대적으로 작다면 가치함수를 크게 추정하는 결과를 초래합니다. 그래서 전체적으로 봤을 때는 분산이 커질 수 있습니다. 즉, 서로 장단점이 존재합니다. 일반적으로는 WIS의 경우 샘플이 충분히 얻어지면 bias가 사라지는 것으로 알려져, WIS 방식이 좀 더 선호된다고 합니다.

Incremental Implementation

예전에 MAB 관련 포스팅에서 Incremental Implementation에 대하여 논의한적이 있습니다. MAB에서는 reward를 이용했다면, 강화학습에서는 누적 보상에 대하여 Incremental Implementation을 적용했습니다. 사실 몬테카를로 방법은 어차피 모든 상태와 행동의 짝을 메모리에 보관해야되서 Incremental의 큰 이점은 없습니다. 하지만 여러 에피소드에 대하여 평균을 낼때 간편하게 적용할 수 있다는 장점이 있습니다.

앞서 다룬 Weighted Importance Sampling에 대하여 Incremental Implementation을 적용해보겠습니다. (Ordinary Importance Sampling은 WIS의 특수한 경우라고 생각할 수 있기 때문에 생략했습니다.) 결국 WIS의 importance samplin ratio는 가중치이기 때문에 가치함수를 추정하는 것을 아래와 같이 요약할 수 있습니다. $$V_{n}=\frac{\sum_{k=1}^{n-1}W_{k}G_{k}}{\sum_{k=1}^{n-1}W_{k}}\text{, }n\ge2$$ 이를 Incremental Implementation에 적용하면, $$\begin{align*}V_{n+1}&=\frac{\sum_{k=1}^{n}W_{k}G_{k}}{C_{k}}\\&=\frac{C_{n-1}}{C_{n}}\times\frac{\sum_{k=1}^{n-1}W_{k}G_{k}+W_{n}G_{n}}{C_{n}}\\&=\frac{C_{n-1}}{C_{n}}\times\frac{\sum_{k=1}^{n-1}W_{k}G_{k}}{C_{n-1}}+\frac{W_{n}G_{n}}{C_{n}}\\&=\frac{\left(C_{n}-W_{n}\right)\sum_{k=1}^{n-1}W_{k}G_{k}}{C_{n}C_{n-1}}+\frac{W_{n}G_{n}}{C_{n}}\\&=V_{n}-\frac{W_{n}\sum_{k=1}^{n-1}W_{k}G_{k}}{C_{n}C_{n-1}}+\frac{W_{n}G_{n}}{C_{n}}\\&=V_{n}+\frac{W_{n}}{C_{n}}\left(G_{n}-V_{n}\right),\end{align*}$$ 여기에서 $C_{n+1}=C_{n}+W_{n+1}$이 됩니다.

Monte Carlo Iteration (Off-policy)

Off-policy Monte Carlo Iteration은 On-policy와 비교하여 행동 정책이 추가되고, importance sampling이 추가된 것이 구분되는 부분이며 나머진 내용이 같습니다. Pseudocode를 살펴보겠습니다.

Figure 1: Off-policy Monte Carlo Iteration

위 코드에 대하여 두 가지 이슈가 있습니다. 첫 번째는 'If' 부분입니다. 바로 윗 줄에서 행동가치함수가 가장 큰 쪽으로만 행동하라고 했음으로 만약 목표 정책과 행동 정책으로 얻어진 정책 $A_{t}$가 다르다면 바로 아랫 줄에서 분자 부분이 0이 되어 더 이상 importance sampling ration가 기능하지 못하기 때문에 해당 에피소드의 학습을 종료하고 다음 에피소드로 넘어가라는 의미입니다. 두 번째는 마지막 줄에 importance sampling ration의 분자가 1인 부분입니다. 위 상황과 같은 맥락에서 가장 큰 쪽으로만 행동하라고 했음로 만일 행동 정책과 목표 정책의 행동이 같으면, 목표 정책의 행동은 1이기 때문에 따로 분자에 $\pi(A_{t}|S_{t})$로 표기하지 않은 것입니다.

마치며

Pros. and Cons. for MC

몬테 카를로 방법은 모델을 모르더라도 단순히 샘플링하는 작업을 통해 가치함수를 간편한 방법으로 추정하고, 최적 정책을 찾아갈 수 있다는 점에서 매력적입니다. 하지만 종료 상태가 없는 continuing task에 적용하기에 한계가 있고, episodic task라도 종료 상태까지 너무 오랜 시간이 걸린다면 적용하는데 한계가 있습니다.

Off-policy MC

이전 포스팅을 합쳐 강화학습에 이용되는 몬테카를로 방법을 살펴보았습니다. 사실 off-policy Monte Carlo는 개념적으로 좋지만 실제로 pseudocode 기반 프로그램을 작성해보면 알고리즘이 잘 작동하진 않습니다. 왜냐하면 행동 정책과 목표 정책의 행동이 다르기 쉽기 때문에 에피소드의 뒷 부분만 주로 학습되고 초반부 학습이 어렵기 때문입니다. 이 부분의 개선은 차후 포스팅할 Temporal Difference Learning (TD)로 해결할 수 있습니다. 곧 TD로 찾아뵙겠습니다. 읽어주셔서 감사합니다. :)

References

• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 2. No. 4. Cambridge: MIT press, 1998.