[RL] What is Monte Carlo?

(해당 포스트는 Coursera의 Sample-based Learning Method의 강의 요약본입니다)

  Policy Evaluation이나 Policy Improvement는 내부적으로 value function \(V(s)\)를 구할 때 transition probability \(p(s', r| s, \pi(s))\)를 활용했고, 이를 Dynamic Programming을 통해서 구했다. 그런데 생각해보면 알겠지만, 보통 강화학습을 구할 때, 이 transition probability를 아는 상태에서 학습을 시키는 경우는 거의 드물다. 이 Probability를 Dynamic Programming을 통해서 구하는 것은 어렵기 때문에, 보통은 estimation을 통해서 구하는데, 이때 많이 활용하는 방법이 바로 Monte Carlo Estimation이다. 간단히 말해서 특정 확률을 구해야 하는 이벤트가 있을 경우, 해당 이벤트를 엄청 많이 돌려서 그에 대한 평균을 취하는 것이다. 가령 주사위 여러개를 던져서 각 주사위의 합의 평균을 구해야 하는 경우, Dynamic Programming으로 이를 풀려면 각 주사위 합별 나올 확률을 일일이 구해서 그 값을 각각 더해야만 한다. 이 경우 주사위 여러개를 무한번 던지지 않는 이상, 각 합이 나올 확률을 구할 수 없다. 대신 대충 어느정도 감안할만큼 많은 수를 던지고, 이에 대한 평균을 내는 것이 Monte Carlo method가 될텐데, 이 경우 각 합이 나올 확률을 알지 못해도 평균을 구할 수 있다. (물론 이같은 관계가 성립하기 위한 조건이 따로 있긴 하지만...)

 결국 Monte Carlo method가 원하는 바는 일단 원하는 만큼 (or temination 조건까지) 돌려보고 얻어진 데이터 기반으로 정보를 얻어내자는 것이고, Policy Evaluation에 이를 적용하면, 주어진 데이터 기반으로 value function \(v_\pi(s)\)를 구하는 것이 된다. 기존에 우리는 value function을 다음과 같이 정의했었다.

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

 말은 즉, 현재의 policy가 \(\pi\)일때, 현재의 state가 \(s\)인 상태에서의 expected total reward \(G_t\)의 expected return을 나타 내는 것이다. 물론 total reward \(G_t\)로 계산되는 값의 갯수가 적으면 적을수록, 최종적으로 얻은 \(v(s)\)과는 거리가 멀겠지만, 갯수가 많으면 많을수록 그 sample들의 평균은 최종의 \(v(s)\)에 가까워질 것이다. 그대신 우리가 원하는 expected total reward가 최종의 것과 같은지를 확인하기 위해서는 일단 termination이 발생한 후에야 가능하다. (그래야 최종 값과 sampling average의 값을 비교해볼 수 있기 때문에) 그래서 Monte Carlo method는 episodic task, 즉 termination 조건이 있는 환경에서만 적용이 가능하다. 

그림 1. (First-visit) MC prediction algorithm

 여기서 Monte Carlo method를 적용하는데 필요한 요소가 바로 \(\text{Returns}(s)\)인데, 이게 바로 termination될 때까지 각 state의 expected return \(G_t\)를 담아놓는 list가 된다.

MC Prediction을 사용한 강의의 예시를 활용해보겠다.

그림 2. Example of MC Prediction

위의 그림은 initial state부터 termination state까지의 간단한 backup diagram을 표시한 것이고, 각 숫자는 state transition시 발생하는 immediate reward를 나타낸다. 그리고 외부 조건으로 discounted factor \(\gamma = 0.5\)이다. 그러면 각 state에서의 total reward는 다음과 같이 정의할 수 있다.

$$ \begin{align} G_0 &= R_1 + \gamma G_1 \\
G_1 &= R_2 + \gamma G_2 \\ G_2 &= R_3 + \gamma G_3 \\ G_3 &= R_4 + \gamma G_4 \\ G_4 &= R_5 + \gamma G_5 \\ G_5 &= 0 \end{align}$$

 그러면 \( G_0 \)를 구하기 위해서는 결국 마지막 step 까지 가야 하니까, 처음 시작할 때부터 마지막 step부터 \(G\)를 계산하면 일부러 backtracking 하면서 연산할 필요가 없게 된다. (이게 바로 그림 1의 알고리즘 중 episode내로 도는 loop를 \(T-1\)부터 도는 이유이기도 하다.) 그러면 마지막 Step부터 다시 계산하면 아래 식과 같이 된다.

$$ \begin{align} G_5 &= 0 \\ G_4 &= R_5 + \gamma G_5 = 2 + 0.5 * 0 = 2 \\ G_3 &= R_4 + \gamma G_4 = 1 + 0.5 * 2 = 2 \\ G_2 &= R_3 + \gamma G_3 = 7 + 0.5 * 2 = 8 \\ G_1 &= R_2 + \gamma G_2 = 4 + 0.5 * 8 = 8 \\ G_0 &= R_1 + \gamma G_1 = 3 + 0.5 * 8 = 7 \end{align}$$

이렇게 하면 결국 한 episode내에서 방문한 모든 state에 대한 value function을 Monte Carlo estimation을 통해 update하게 된 것이다. 이 과정을 많이 수행하게 되면 결과적으로 value function에 대한 good estimation을 얻게 될 것이다.