Chapter 5. 몬테카를로 법

Intro

4장에서는 동적 프로그래밍으로 최적 가치 함수와 최적 정책을 찾았다. DP를 이용하려면 '환경 모델(상태 전이 확률과 보상 함수)'을 알아야 한다. 하지만 실제로 환경 모델을 알 수 있는 경우는 많지 않다. 혹은 알 수 있더라도 DP 방식으로는 계산량이 너무 많아서 사실상 풀 수 없는 경우가 많다. 이런 상황에서 문제를 풀려면 에이전트가 실제로 행동하여 얻은 경험을 토대로 학습해야 한다.

몬테카를로법(monte carlo method, MC)가 바로 그런 방법 중 하나이다. 데이터를 반복적으로 샘플링하여 그 결과를 토대로 추정하는 방법을 일컫는다. 강화 학습에서는 MC를 통해 경험으로부터 가치 함수를 추정할 수 있다. 여기서 말하는 경험이란 환경과 에이전트가 실제로 상호작용하여 얻은 (상태, 행동, 보상) 데이터를 의미한다. 이번 장의 목표는 에이전트가 얻은 경험을 바탕으로 가치 함수를 추정하는 것이다. 

몬테카를로법 기초

지금까지 살펴본 그리드 월드 문제 같은 경우, 에이전트의 행동에 따른 다음 상태(위치)와 보상이 명확했다.

하지만 현실에서는 환경 모델을 알 수 없는 문제가 많다. 예를 들어 '상품 재고 관리'를 생각해보면, '상품이 얼마나 팔릴 것인가'가 환경의 상태 전이 확률에 해당한다. 그런데 이러한 상품의 판매량은 여러 요인이 복잡하게 얽혀 결정되기 때문에 완벽하게 알아내는 것이 불가능하다.

또한 이론적으로 알 수 있더라도 계산량이 너무 많은 경우가 허다하다. 얼마나 많은지 실감할 수 있도록 주사위의 예를 들어보자.

주사위 눈의 합

주사위 두 개를 굴리는 문제를 상상해보자. 각 눈이 나올 확률은 정확하게 1/6이라고 가정한다. 이 때 주사위 눈의 합을 전개도와 확률 분포로 표현해보자.

확률 분포를 알면 기대값을 구할 수 있다. 

$$\mathbb{E}(x) = 2 * 1/36 + 3 * 2/ 36 + \cdots + 12 * 1/36 = 6.9999...$$ 

여기서 기대값을 구하는 이유는 강화 학습에서는 기대값 계산이 주를 이루기 때문이다. 다시 이야기하지만 강화 학습의 목적은 '수익'을 극대화 하는 것이다. 여기서 수익은 '보상의 총합에 대한 기대값'이다.

분포 모델과 샘플 모델

앞서 주사위 눈의 합을 '확률 분포'로 표현했다. 즉, 주사위를 굴리는 시도를 확률 분포로 모델링한 것이다. 이렇게 확률 분포로 표현된 모델을 분포 모델(distribution model)이라고 한다.

반면, '표본을 추출(샘플링)할 수만 있으면 충분하다'라는 모델로 샘플 모델(sample model)도 있다. 분포 모델의 조건이 '확률 분포를 정확하게 알고 있다'라면 샘플 모델의 조건은 '샘플링할 수 있다"이다.

샘플 모델에서는 전체의 확률 분포는 필요하지 않으며 단순히 샘플링만 할 수 있으면 충분하다. 다만 샘플링을 무한히 반복하면 그 분포가 곧 확률 분포와 같아진다.

주사위가 2개라면 분포 모델을 만드는 것이 쉽지만 주사위가 10개라면 분포 모델로 구현하기란 쉽지 않다. 경우의 수만해도 \(6^{10}=60,466,176\)이다. 

반면 샘플 모델로 기대값을 계산하려면 단순히 샘플링을 많이 하고 평균을 구하면 된다. 이 방법이 바로 몬테카를로법이다. '숫자를 세어 평균을 구하는' 간단한 방법이지만 표본 수를 무한대로 늘리면 큰 수의 법칙에 따라 그 평균이 참값으로 수렴한다.

(1장에서 봤었던 밴디트 문제에서 사용했던 방식이 몬테카를로법)

몬테카를로법으로 정책 평가하기

이번 절에서는 정책 \(\pi\)가 주어졌을 때, 그 정책의 가치 함수를 몬테카를로법으로 계산한다. 

가치 함수를 몬테카를로법으로 구하기

가치 함수는 다음 식으로 표현된다. 

$$v_\pi(s) = \mathbb{E}_\pi[G|s]$$

위 가치 함수는 '정책 \(\pi\)에 따라 행동했을 때 얻을 수 있는 기대 수익'으로 정의된다. 이 가치 함수를 몬테카를로법으로 계산해보자. MC는 에이전트의 실제 행동에 따라 샘플 데이터를 많이 모아서 평균을 구하는 식이므로 다음과 같이 정의된다.

$$V_\pi(s)=\frac{G^{(1)} + G^{(2)} + G^{(3)}  + \cdots + G^{(n)}}{n}$$

참고로 몬테카를로법은 일회성 과제에만 이용할 수 있다. 지속성 과제에는 끝이 없기 때문에 \(G^{(1)}\) 등이 확정되지 않는다.

구체적인 예를 보자.

$$G^{(1)} = 1 + 0 + 2 = 3$$

$$G^{(2)} = 0 + 0 + 1 + 1 = 2$$

$$V_\pi(s) = \frac{ G^{(1)} + G^{(2)}}{2} = 2.5$$

1차 수익과 2차 수익의 평균을 통해서 이 시점의 가치 함수는 2.5가 된다. 

모든 상태의 가치 함수 구하기

이번에는 모든 상태에서의 가치 함수를 구해보자. 단순하게 생각하면 시작 상태를 바꿔가며 앞 절의 과정을 반복하면 된다.

위와 같이 계산한다면 각 상태의 가치 함수를 독립적으로 구한다는 점에서 비효율 적이다. 예를 들어 상태 A에서 시작하여 얻은 샘플 데이터는 다른 가치 함수 계산에는 기여하지 않는다.

좀 더 효율적인 방법을 생각해보자.

그림 5-8처럼 A에서 출발해서 \(\pi\)에 따라 행동하고 A, B, C 순서로 상태를 거쳐 목표에 도달했다고 가정하자. 상태 A에서 출발하여 얻은 수익은 다음과 같다.

$$G_A=R_0+\gamma R_1 + \gamma^2 R_2$$

위 그림의 오른쪽 부분은 상태 B에서 시작하여 얻는 수익의 샘플 데이터로 볼 수 있다. 그러므로 상태 B에서 시작했을 때의 수익은,

$$G_B=R_1 + \gamma R_2$$

마찬가지로 상태 C에서 시작했을 때의 수익은,

$$G_C=R_2$$

이와 같이 '한 번의 시도'만으로 세 가지 상태에 대한 수익을 얻었다. 이와 같이 에이전트의 시작 위치가 고정되어 있더라도 에피소드를 반복하는 동안 모든 상태를 경유할 수 있다면 모든 상태에 대한 수익 샘플 데이터를 수집할 수 있다.

몬테 카를로법 계산 효율 개선

다음 세 가지 상태에 대한 수익을 계산해야 할 때,

$$G_A=R_0+\gamma R_1 + \gamma^2 R_2$$

$$G_B=R_1 + \gamma R_2$$

$$G_C=R_2$$

위 식을 다음처럼 변형할 수 있다.

$$G_A=R_0+\gamma G_B$$

$$G_B=R_1 + \gamma G_C$$

$$G_C=R_2$$

위 식에서 보면 중복된 계산이 있다. \(G_A\)를 계산할 때 \(G_B\)를 사용하고 \(G_B\)를 계산할 때 \(G_C\)를 사용한다. 따라서 \(G_C, G_B, G_A\) 순서대로 계산하면 중복 계산을 없앨 수 있다.

몬테카를로법 구현

4장에서 다룬 '그리드 월드' 문제를 이번에는 몬테카를로법으로 풀어보자.

이번에는 환경 모델(상태 전이 확률과 보상 함수)을 이용하지 않고 정책을 평가한다. 이렇게 하려면 실제로 행동하도록 시키는 메서드가 필요하다.

step() 메서드

step() 메서드는 행동을 매개 변수로 받는다. env.step(action)을 호출하면 현재 환경에서 action을 수행하고 그 결과로 next_state, reward, done을 반환한다.

몬테카를로 에이전트 구현

add() 메서드를 통해 경험을 추가해준다. 이때 (상태, 행동, 보상)을 튜플 단위로 묶어서 저장한다. 

eval() 메서드를 통해서 self.memory를 역방향으로 따라가면서 각 상태에서 얻은 수익을 계산한다. 그리고 각 상태에서의 가치 함수를 그때까지 얻은 수익의 평균으로 구한다.

가치 업데이트 방식은 <증분 방식>으로 구현되어 있다.

<일반적인 방식>

\(s_n\)은 n번째로 얻은 샘플 데이터

$$V_n = \frac{s_1 + s_2 + \cdots + s_n}{n}$$

<증분 방식>

$$V_n = V_{n-1} + \frac{1}{n}(S_n-V_{n-1})$$

몬테카를로법 실행

DP와 MC의 차이가 거의 없음을 알 수 있다. 이처럼 MC를 이용하면 환경 모델을 몰라도 정책 평가를 제대로 할 수 있다.

몬테카를로법으로 정책 제어하기

정책 평가를 했으니 이제 최적 정책을 찾기 위한 '정책 제어'를 해야 한다. 정책 제어의 핵심은 평가와 개선을 번갈아 반복하는 것이다.

평가와 개선

평가 단계에서 \(\pi\)라는 정책을 통해 \(V_\pi(s)\)를 얻을 수 있었다. 개선 단계에서는 탐욕화를 수행한다.

$$\mu(s)= \underset{a}{\operatorname{argmax}} Q(s,a)$$ (5.3)

$$\mu(s)= \underset{a}{\operatorname{argmax}} \sum_{s'} p(s'|s,a,) \{r(s,a,s') + \gamma V(s')\}$$ (5.4)

개선 단계에서는 가치 함수의 값을 최대로 만드는 행동을 선택한다. 앞절까지는 [식 5.4]를 사용하여 가치 함수 V에 대한 평가를 진행했으나 일반적인 상황에서는 환경 모델(p,r)을 모르기 때문에 V를 계산 할 수가 없다.

따라서 일반적인 강화학습의 경우, Q 함수를 사용하는 [식 5.3]을 이용해야 한다(Q도 풀어보면 계산을 위해서 p와 r이 필요 한 건 마찬가진데???;;;; 이해가 안되네..)

Q함수를 대상으로 개선할 경우 Q 함수를 '평가'해야 한다. 앞 절까지는 MC로 V를 평가했으나 이제 Q 함수로 바꿔야 한다. 그럴려면 MC 갱신식에서 V(s)에서 Q(s,a)로 전환해야 한다 수식으로느 다음과 같다

[상태 가치 함수 평가]

• 일반적인 방식: \(V_n(s) = \frac{G^{(1)} + G^{(2)} + \cdots + G^{(n)} }{n}\)
• 증분 방식: \(V_n(s) = V_{n-1}(s) + \frac{1}{n} \{ G^{(n)} - V_{n-1}(s)\}\)

[Q 함수 평가]

• 일반적인 방식: \(Q_n(s, a) = \frac{G^{(1)} + G^{(2)} + \cdots + G^{(n)} }{n}\)
• 증분 방식: \(Q_n(s, a) = Q_{n-1}(s, a) + \frac{1}{n} \{G^{(n)} - Q_{n-1}(s, a)\}\)

식에서 알 수 있듯이 대상만 바뀌었을 뿐 계산 자체는 변하지 않는다(그럼 왜바꾸는거야??)

ε-탐욕 정책으로 변경(첫 번째 개선 사항)

에이전트는 개선 단계에서 정책을 탐욕화 해야한다. 탐욕화의 결과로 해당 상태에서 취할 수 있는 행동이 단 하나로 고정된다.

예를 들어 위 그림처럼 탐욕 행동만을 수행하면 에이전트의 경로가 한 가지로 고정된다. 이 문제를 해결하려면 에이전트가 '탐색'도 시도하도록 해야 한다.

에이전트에게 '탐색'을 시키는 대표적인 방법이 'ε-탐욕' 정책이다. 

고정값 \(\alpha\) 방식으로 수행(두 번째 개선 사항)

# 수정 전
self.Q[key] += (g - self.Q[key]) / self.cnt[state]

# 수정 후
alpha = 0.1
self.Q[key] += (g - self.Q[key]) * alpha

Q 함수 값을 계산할 때, 모든 샘플 데이터에 가중치를 균일하게 주는 '표본 평균' 방법에서 고정값 \(\alpha\)로 갱신하는 '지수 이동 평균' 방식으로 변형해준다.

MC를 이용한 정책 제어에는 지수 이동 평균이 적합하다. '수익'이라는 샘플 데이터가 생성되는 확률 분포가 시간에 따라 달라지기 때문이다. 즉, 에피소드가 진행될수록 정책이 갱신되기 때문에 수익이 생성되는 확률 분포도 달라진다. 비정상 문제(non-stationary problem)이라고 할 수 있다. 

수익은 '환경의 상태 전이'와 '에이전트의 정책'이라는 두 가지 확률적 처리를 반복하며 만들어진다. 이 두 가지 처리에서의 확률 분포가 아무것도 변하지 않는다면 샘플링되는 수익의 분포 역시 '정상(변하지 않음)'이다. 하지만 둘 중 하나라도 변환한다면 수익의 확률 분포는 '비정상'이 된다. 지금 예에서는 정책을 반복적으로 개선하기 때문에 에피소드를 거칠 때마다 정책이 달라질 수밖에 없다. 이에 따라 수익의 확률 분포도 변화한다.

실행 결과

Off-policy & Importance Sampling

앞서 ε-탐욕 정책을 결합하여 최적에 가까운 정책을 얻었다. 하지만 그 결과는 완벽한 최적 정책이 아니다. 이번 절에서는 MC 법을 이용해 완벽한 최적 정책을 학습하는 방법에 대해서 알아보자.

On-policy and Off-policy

사람이 다른 사람의 행동을 관찰하여 자신의 능력을 개선할 힌트를 얻을 수 있다. 강화 학습 용어로는 '자신과 다른 환경에서 얻은 경험을 토대로 자신의 정책을 개선한다'고 표현할 수 있다. 이러한 접근 방식을 강화 학습에서는 off-policy라고 한다. 반면 스스로 쌓은 경험을 토대로 자신의 정책을 개선하는 방식은 On-policy라고 한다.

역할 측면에서 보면 에이전트의 정책은 두 가지이다. 하나는 평가와 개선의 대상으로서의 정책이다. 즉, 정책에 대해 평가한 다음 개선한다. 이러한 정책을 '대상 정책(target policy)'라고 한다. 다른 하나는 에이전트가 실제로 행동을 취할 때 활용하는 정책이다. 이 정책에 따라 '상태, 행동 보상'의 샘플 데이터가 생성된다. 이러한 정책을 행동 정책(behaviour policy)라고 한다.

지금까지 이 책에서는 target policy와 behaviour policy를 구분하지 않았다. 즉 평가와 개선의 대상인 정책과 실제 행동을 선택하는 정책을 동일시 한 것이다. 이처럼 두 정책이 같은 경우를 on-policy, 다른 경우를 off-policy라고 한다.

이번 절의 주제는 Off-policy이다. off-policy라면 행동 정책에서는 '탐색'을, 대상 정책에서는 '활용'만을 할 수 있다. 다만 행동 정책에서 얻은 샘플 데이터로부터 대상 정책과 관련된 기대값을 계산하는 방법에는 다른 방법이 필요한데, 이때 등장하는 것이 중요도 샘플링 기법이다.

중요도 샘플링

중요도 샘플링(importance sampling)은 어떤 확률 분포의 기대값을 다른 확률 분포에서 샘플링한 데이터를 사용하여 계산하는 기법이다. 

x를 확률 변수라고 하고 x의 확률을 \(\pi(x)\)로 표시하자. 그러면 확률 분포의 기대값은 다음과 같다.$$\mathbb{E}_\pi(s) = \sum x\pi(x)$$이 기대값을 MC로 근사하려면 x를 확률 분포  \(\pi\)에서 샘플링하여 평균을 내면 된다.

• 샘플링: \(x^{(i)} \text{~} \pi\)
• \( \mathbb{E}_\pi[x] \simeq  \frac{x^{(1)} + x^{(2)} + \cdots + x^{(n)} }{n}\)

위와 같이 x를 \(\pi\)가 아닌 b라는 다른 확률 분포에서 샘플링되었다고 가정하자. 그러면 기대값 \(\mathbb{E}_\pi[x]\)는 어떻게 구할 수 있을까? 다음과 같이 식을 변형해보자.

$$\begin{equation} \begin{split} \mathbb{E}_\pi[x] &= \sum x\pi(x) \\ &=  \sum x \frac{b(x)}{b(x)} \pi(x) \\ &=  \sum x \frac{\pi(x)}{b(x)} b(x) \\ &= \mathbb{E}_b\Big[x\frac{\pi(x)}{b(x)}\Big] \end{split} \end{equation}$$

\(\frac{b(x)}{b(x)} = 1\)이므로 위와 같이 변경 가능하다. 위처럼 변경하면 확률 분포 b에 대한 기대값으로 표현된다.여기서 \(\rho(x) = \frac{\pi(x)}{b(x)}\)라고 하면, 각각의 x에는 '가중치'로서 \(\rho(x)\)가 곱해진다고도 볼 수 있다. 이를 수식으로 표현하면,

• 샘플링: \(x^{(i)}~ b\)
• \( \mathbb{E}_\pi[x] \simeq  \frac{\rho(x^{(1)})x^{(1)} + \rho(x^{(2)}) x^{(2)} + \cdots + \rho(x^{(n)}) x^{(n)} }{n}\)

이렇게 되면 이제 다른 확률 분포 b에서 샘플링한 데이터를 이용하여 \(\mathbb{E}_pi[x]\)를 계산할 수 있다.

이제 직접 구현을 통해서 비교해보자.

먼저 확률 분포 \(\pi\)의 기대값을 일반 적인 몬테카를로 법으로 계산해보면,

• 평균: 2.78
• 분산: 0.27

중요도 샘플링을 이용하여 기대값을 구해보면,

• 평균: 2.95
• 분산: 10.63

평균은 아주 동떨어진 정도는 아니지만 분산은 MC 때보다 훨씬 큰 것을 알 수 있다.

분산을 작게 하기

분산이 작을수록 적은 샘플로도 정확하게 근사할 수 있다. 반대로 분산이 클수록 샘플을 더 많이 사용해야 한다. 따라서 중요도 샘플링에서 분산을 줄이는 방법을 알아보자. 

중요도 샘플링을 쓰면 분산이 커지는 이유

위 그림처럼 샘플 데이터가 3인 경우를 생각해보자. 이 때 가중치 \(\rho\)는 2.4다. 즉, 3을 뽑았음에도 3 X 2.4 = 7.2를 얻는다는 뜻이다. 이런 상황이 일어나는 이유는 다음과 같다.

• 확률 분포 \(\pi\)에서는 3이 많이 뽑힌다.
• 하지만 확률 분포 b에서는 특별히 많이 뽑히지 않는다.
• 이 간극을 메우기 위해 3이 샘플링된 경우, 그 값이 커지도록 '가중치 \(\rho\)'를 곱하여 조정하게 된다.

위에서 보듯 가중치를 부여하는 일 자체는 중요한 일이지만 그로 인해서 보정 효과가 발생하여 분산(참값으로부터의 편차)이 자연스럽게 커지게 된다.

하지만 만약 b의 분포를 \(\pi\)와 비슷하게 만들면 분산은 자연스럽게 작아지게 된다.

이처럼 중요도 샘플링 시 두 확률 분포를 비슷하게 설정하면 분산을 줄일 수 있다. 단, 강화 학습에서의 핵심은 한쪽 정책(확률 분포)은 탐색에, 다른 쪽 정책은 '활용'에 이용하는 것이기 때문에 이 조건을 염두에 둔 상태에서 두 확률 분포를 최대한 가깝게 조정하면 분산을 줄일 수 있다.

이것이 바로 중요도 샘플링이다. 중요도 샘플링을 이용하면 off-policy를 구현할 수 있다. 즉, 행동 정책이라는 확률 분포에서 샘플링된 데이터를 토대로 대상 정책에 대한 기대값을 계산할 수 있다.

정리

• 몬테카를로법을 이용하면 실제로 얻은 경험 데이터로부터 가치 함수를 근사적으로 구할 수 있다.
• 몬테카를로법으로 Q 함수를 평가할 수 있으면 Q 함수를 이용하여 정책을 개선할 수 있다.
• ε-탐욕 정책을 통해 활용과 탐색의 균형을 맞출 수 있따.
• 에이전트의 정책은 역할 측면에서 target policy와 behaviour policy로 나눌 수 있다.
• target policy와 behaviour policy가 같은 경우를 On-policy, 다르면 Off-policy라고 한다.

부록: Off-Policy 몬테카를로법

Off-Policy MC의 이론

On-policy 방식의 몬테카를로 법은 다음과 같은 Q 함수를 근사한다.

$$q_\pi(s,a) = \mathbb{E}_\pi[G|s, a]$$

$$\text{샘플링}: G \text{~} \pi$$

$$ q_\pi(s,a)  = \frac{\sum_{i=1}^n G_i}{n}$$

이어서 Off-policy 몬테카를로 법을 생각해보자.

$$q_\pi(s,a) = \mathbb{E}_b[\rho G|s, a]$$

$$\text{샘플링}: G \text{~} b $$

$$ q_\pi(s,a)  = \frac{\sum_{i=1}^n \rho_i G_i}{n}$$

다음으로 가중치 \(\rho\)를 구하는 방법을 알아보자. 정책 b에 의해 다음과 같은 시계열 데이터를 얻는다 해보자.

위와 같은 데이터를 얻었을 때 가중치 \(\rho\)는 다음처럼 표현 가능하다.

$$\rho = \frac{\text{Pr(trajectory | π)}}{ \text{Pr(trajectory | b)} }$$

\(\text{Pr(trajectory | π)}\)는 정책이 π일 때 trajectory가 얻어질 확률을 뜻한다.

위 확률은 마르코프 결정 과정을 고려하면 더 간결히 표현 가능하다. 마르코프 결정 과정에서는 환경의 다음 상태와 에이전트의 행동이 한 단계 이전의 상태와 행동에만 의존하여 결정된다.

$$ \text{Pr(trajectory | π)} = p(S_{t+1}| S_t, A_t) π( A_{t+1} | S_{t+1} )  \cdots p(S_T| S_{T-1}, A_{T-1}) $$

$$ \text{Pr(trajectory | b)} = p(S_{t+1}| S_t, A_t) b( A_{t+1} | S_{t+1} )  \cdots p(S_T| S_{T-1}, A_{T-1}) $$

가중치 \(\rho\)는 위 두 식의 비율인데 공통적으로 상태 전이 확률 p(s'|s,a)가 존재하므로 상쇄시키면 다음처럼 표현 가능하다.

$$\rho = \frac{\text{Pr(trajectory | π)}}{ \text{Pr(trajectory | b)} } = \frac{\pi(A_{t+1}|S_{t+1}) \cdots \pi(A_{T-1}|S_{T-1}) }{ b(A_{t+1}|S_{t+1}) \cdots b(A_{T-1}|S_{T-1})}$$ (4.4)

위와 같이 가중치 \(\rho\)는 정책만의 비율로 구할 수 있다. 이상이 Off-policy MC의 방법이다. 알고리즘의 절차를 정리하면 다음과 같다.

1. 행동 정책 b로 샘플링
2. 얻은 trajectory에서 수익 G를 계산
3. 식 4.4를 이용해 가중치 \(\rho\)를 계산
4. 1~3을 여러 번 반복하여 \(\rho G\)의 평균을 구한다.

Off-Policy MC 구현

먼저 가중치 \(\rho\)를 구해보자.

위 그림은 상태와 행동의 쌍(\(S_t, A_t\)를 시작 위치로 삼았을 때의 결과지만, 중간에 등장하는 각각을 시작 위치로 해서 얻은 샘플 데이터로도 간주할 수 있다. 따라서 가중치 \(\rho\)를 구할 때 오른쪽 끝에서 왼쪽으로 갱신하는 편이 효율적이다.

먼저 \(\rho\)의 초기값을 1로 설정한다. 그러면 \(Q_\pi(S_{T-1}, A_{T-1})\)의 가중치는 1이다. 다음으로 \(Q_\pi(S_{T-2}|A_{T-2})\)의 가중치를 구해보면,

$$\rho \gets \frac{\pi( A_{T-1} | S_{T-1})}{ b( A_{T-1} | S_{T-1})} \rho $$

같은 방법으로 \(Q_\pi(S_{T-3}|A_{T-3})\)의 가중치는,

$$\rho \gets \frac{\pi( A_{T-2} | S_{T-2})}{ b( A_{T-2} | S_{T-2}) } \rho $$

이처럼 역방향으로 가중치를 갱신하면 효율적으로 계산 가능하다.

구현 부분에서 구체적으로 다른 점은,

위 처럼 rho를 이용하여 샘플 데이터로 얻은 수익을 보정하는 것이 전부이다.

그리고 pi와 b 두개의 정책을 두고 pi는 탐욕 정책, b는 엡실론-탐욕 정책으로 갱신한다. 행동 정책 b는 탐색이 주 목적이므로 무작위 정책으로 해도 괜찮지만 수익의 분산을 줄이기 위해 엡실론 탐욕 정책으로 갱신하였다. 이렇게 하여 pi와 b의 분포를 가깝게 만들어주면서도 탐색을 적절히 수행할 수 있다.

마지막으로 위 그림처럼 off-policy MC를통해서도 좋은 결과를 얻을 수 있음을 볼 수 있다. 하지만 문제가 커지면 샘플 데이터의 분산이 커지게 되어 좋은 결과를 기대하기 힘들다. 문제가 커지면 목표에 도달하기까지 더 많은 상태와 행동을 거쳐야 하기 때문에 분산이 커질 수밖에 없다. 그만큼 \(\rho\)의 분산도 커지기 때문에 off-policy MC 방법은 정책 개선에 대량의 에피소드가 필요하므로 계산에 시간이 오래 걸린다는 단점이 존재한다.