Optimal Value Function을 찾기 위한 Monte Carlo 방법

지난 글에서는 강화학습의 목적은 최적의 정책을 찾는것이며 최적이란 것을 비교할 수치를 나타내기 위해 가치 함수에 대한 설명을 하였습니다. 그렇다면 가치 함수중 에서도 최적의 가치 함수는 어떻게 찾아낼 것인가요? 고전적인 방법론으로 Dynamic Programming과 Monte Carlo, Temporal-Diffrence 3가지 방법을 대표적으로 꼽을 수 있습니다. 이 세 가지를 비교하기 전에, 먼저 강화학습에서 말하는 모델(model) 이 무엇인지부터 짚고 넘어가겠습니다. 강화학습에서 모델이란, 환경이 어떻게 동작하는지를 수학적으로 기술한 것으로, 구체적으로는 어떤 상태 s에서 행동 a를 했을 때 다음 상태 s′와 보상 r이 어떤 확률로 나오는지를 알려주는 \(P(s', r \mid s, a)\)를 의미합니다. 

즉, “이 상태에서 이 행동을 하면 이후에 환경이 어떻게 반응하는가?”를 예측해 주는 것이 모델입니다. 반대로, 각 상태에서 어떤 행동을 선택할지를 정의한 것은 정책 이고, 모델과는 구분되는 개념입니다. 만약 우리가 환경의 모델 \(P(s', r \mid s, a)\) 를 완전히 알고 있다면, 실제로 환경과 상호작용을 많이 해 보지 않아도, 이 모델을 이용해 기대 보상과 상태 전이를 계산함으로써 최적의 가치 함수와 정책을 계산만으로 구할 수 있습니다. 이렇게 환경 모델을 이용해 계획을 수행하는 접근을 Model-based 강화학습이라고 부르며, 그 중에서도 Dynamic Programming이 대표적인 방법입니다. 반대로, 현실 세계의 많은 문제에서는 환경의 전이 확률이나 보상 함수를 정확히 알기 어렵습니다. 이 경우에는 모델을 가정하지 않고, 실제로 환경과 상호작용하면서 쌓인 경험(episode) 을 기반으로 가치 함수를 추정하고 정책을 개선해야 합니다. 이런 접근을 Model-free 강화학습이라고 부르며, 대표적인 방법이 바로 Monte Carlo(MC)와 Temporal-Difference(TD) 입니다. MC는 에피소드가 끝날 때까지의 실제 Return을 이용해 가치 함수를 추정하고, TD는 다음 글에서 정리하겠습니다...
아무튼 실제 우리가 다루는 많은 강화학습 문제들은 순수 Model-free이거나, 모델을 어느 정도 학습해서 Model-based와 Model-free를 혼합해 사용하는 경우가 많습니다. 

Monte Carlo의 기본 아이디어

Monte Carlo 방법은 어려운 기대값을 표본평균으로 바꾼다는 점입니다. 어떤 확률변수 \(X\)의 기대값 \(\mathbb{E}[X]\)를 직접 계산하기 어렵다면, 독립 표본 \(X_1,\dots,X_n\)을 뽑아 평균을 다음과 같이 근사합니다.

$$ \hat{\mu}_n = \frac{1}{n}\sum_{i=1}^n X_i $$ 

위의 식을 우리가 익숙한 표현에 빗대면 그냥 큰수의 법칙 입니다.

큰수의 법칙에 의해, 표본 수가 커지면 \(\hat{\mu}_n\)은 실제 기대값 \(\mu=\mathbb{E}[X]\)에 수렴합니다. 

원주율 \(\pi\)로 큰수의 법칙 이해하기

큰 수의 법칙으로 가장 유명한 예시는 정사각형 안의 원에 점을 무작위로 뿌려 \(\pi\)를 근사하는 방법입니다. 반지름 \(R\)인 원이 한 변 길이 \(2R\)인 정사각형 안에 내접하면, 원 넓이와 정사각형 넓이의 비는 다음과 같습니다.

$$ \frac{\pi R^2}{(2R)^2} = \frac{\pi}{4} $$ 

따라서 정사각형 내부에서 균등하게 점을 뿌렸을 때, 점이 원 안에 들어갈 확률은 \(\pi/4\)이고, 점 \(n\)개 중 원 안에 들어간 점 수를 \(K\)라고 하면 다음과 같이  \(\pi\)를 추정할 수 있습니다.

$$ \hat{\pi} = 4\frac{K}{n} $$

여기서 \(K\)는 사실상 베르누이 확률변수의 합이므로, 결국 "확률의 기대값을 표본평균으로 근사"한 전형적인 Monte Carlo입니다.

예시 자료

이 방법은 정사각형 바닥에 콩을 무작위로 던지는 것과 비슷합니다. 콩이 원 안에 떨어진 비율이 면적비와 같아질 것이므로, 충분히 많이 던지면 그 비율이 \(\pi/4\) 근처로 모입니다.

Python으로 간단히 구현하면 다음과 같습니다.

import random

def estimate_pi(n):
    k = sum(1 for _ in range(n)
            if random.random()**2 + random.random()**2 <= 1)
    return 4 * k / n

# estimate_pi(1_000_000) → ~3.1415

강화학습의 Monte Carlo

큰수의 법칙을 이해했다면 짐작할 수 있듯이 강화학습에서 MC는 특정 상태에서 발생하는 Return 즉, 가치함수를 반복적으로 측정하여 위의 원주율을 구하듯이 가치 함수의 기댓값을 구합니다. 그러고 나서 정책 평가와 개선을 수렴할 때 까지 반복하여 최적의 정책을 찾아가는것 이것이 강화학습에서 Monte Carlo 방법입니다.

 

다만 여기서 한가지 문제가 있습니다. \(V^\pi(s)\)만 알고 있을 때 지난 글에서 Bellman 최적 방정식을 정리하며 아래와 같이 정의된다고 설명하였습니다.

 

$$ \pi'(s) = \arg\max_a \sum_{s', r} P(s', r \mid s, a) \big[ r + \gamma V^\pi(s') \big] $$

 

문제는 모델 \(P(s', r \mid s, a)\)이 다시 등장합니다. 위에서 모델을 알 수 없는 Model-free 방식이기 때문에 MC를 사용한다고 하였기에 \(V^\pi(s)\)를 가지곤 해당 식을 풀 수 없습니다. 그래서 다음과 같이 행동 가치 함수 \(Q^\pi(s, a)\)를 추정해야 합니다.

 

$$ Q^\pi(s, a) = \mathbb{E}_\pi \big[ G_t \mid S_t = s,\ A_t = a \big] $$

\(Q^\pi(s, a)\)  만 알면 모델 없이도 곧바로 더 나은 행동을 고를 수 있습니다.

$$
\pi'(s) = \arg\max_a Q^\pi(s, a)
$$

First-visit MC vs Every-visit MC

이제 \(Q^\pi(s, a)\)를 실제 표본 Return 으로 추정해야 하는데, 여기서 한 가지 선택지가 다시 등장합니다. 한 에피소드 안에서 같은 (s, a) 쌍이 여러 번 등장할 수 있는데, 그 중 어떤 시점의 Return 을 표본으로 채택할 것인지의 문제입니다. 표기 편의를 위해 에피소드 \(i\) 에서 (s, a)가 방문된 시점들의 집합을 \(\mathcal{T}_i(s, a) = \{ t : S_t = s,\ A_t = a \}\) 라고 부르겠습니다.

First-visit MC 는 한 에피소드 안에서 (s, a) 가 처음 등장한 시점의 Return 만 표본으로 사용합니다. 즉, \(i\)번째 에피소드의 첫 방문 시점을 \(t_1^{(i)} = \min \mathcal{T}_i(s, a)\) 라 할 때, 다음과 같이 추정합니다.

$$
Q^\pi(s, a) \approx \frac{1}{N(s, a)} \sum_{i=1}^{N(s, a)} G_{t_1^{(i)}}
$$

여기서 \(N(s, a)\) 는 (s, a) 가 첫 방문된 에피소드의 수입니다. 각 에피소드에서 표본이 하나씩만 나오기 때문에 표본들이 서로 독립이고, \(N(s, a) \to \infty\) 일 때 우리가 추정한 가치 함수는 정답에 근사하게 수렴할 수 있습니다.

Every-visit MC 는 한 에피소드 안에서 (s, a) 가 방문될 때마다 그 시점의 Return 을 전부 표본으로 사용합니다.

$$
Q^\pi(s, a) \approx \frac{1}{M(s, a)} \sum_{i=1}^{N_e} \sum_{t \in \mathcal{T}_i(s, a)} G_t,
\quad M(s, a) = \sum_{i=1}^{N_e} | \mathcal{T}_i(s, a) |
$$

 

같은 에피소드 안에서 뽑힌 표본들은 서로 상관되어 있어 분석은 약간 까다롭지만 표본을 더 많이 활용하기 때문에 실용적으로는 분산이 더 적게 나오는 경우가 많고 충분한 표본에서 \(Q(s,a)\)로 수렴함이 증명되어 있습니다.

 

예시 자료

위 그림을 보면 한 에피소드동안 상태 S5 3번 진입하는것을 볼 수 있으며 동일 상태지만 시점마다 각각의 Return값은 다르게 존재합니다. 

이때 "First-visit은 처음 방문했을때의 Return값만 사용하고 Every-visit은 3번의 Return값을 모두 사용한다." 요런 차이 밖에 없습니다.

 

두 방식 모두 매번 평균을 다시 계산하지 않고 보통은 아래처럼 점진적으로 업데이트 합니다.

$$
N(s, a) \leftarrow N(s, a) + 1
$$
$$
Q(s, a) \leftarrow Q(s, a) + \alpha \big[ G_t - Q(s, a) \big]
$$

 

여기서 \(\alpha = 1 / N(s, a)\) 로 두면 정확한 표본 평균과 동일하고, 상수 \(\alpha\) 로 두면 최근 경험에 더 가중치를 두는 형태가 됩니다.