Monte Carlo Method

Monte Carlo(MC)는 무작위 시뮬레이션을 반복하여 수치적 해를 구하는 sampling 기반의 근사화 방법론이다. 이 방식은 Model Free 상황에도 학습이 가능하다는 장점이 있다.

위와 같은 그림을 보자. 원호에 의해 정사각형이 두 부분으로 나누어진다. 두 부분에 각각 다른 색의 점을 무작위로 표시하면, 점의 갯수를 통해 두 영역의 넓이 비를 근사할 수 있다.

MC 는 Tabular Updating, Model-Free 방식이다. Tabular Updating 은 (s,a) 쌍을 표 형태로 저장하고 업데이트하는 방식이다. 또한 MC 는 Policy Iteration 을 채택하는데, 에피소드 단위로 전체 경험을 사용하고, 한 에피소드가 끝난 후에 업데이트한다.

그래서 MC 에서의 Value 는 다음과 같이 정의된다.

Value = average of returns $G_t$ of sampled episodes

MC 의 특징

• MC는 경험한 상태만 집중적으로 학습한다. (focuses on a small subset of the sample states)
  • 예: 바둑이나 체스처럼 상태 공간이 너무 큰 경우 효율적
• 마르코프 성질(Markov Property) 위반에 덜 민감
  • 왜냐면 다음 상태의 추정값에 의존하지 않고, 실제 리턴만 보기 때문이다.
• No Bootstrapping
  • Bootstrapping 은 다른 추정값을 이용해 근사하는 방식이다. MC 는 다른 추정값에 의존하지 않는다.

DP는 모델 기반으로 이론적으로 정확하게 계산하고, MC는 모델 없이 경험을 통해 샘플 평균으로 추정한다.

MC Prediction (Policy Evaluation)

Policy Evaluation 방법 중 하나인 Monte Carlo Prediction 의 목적은 정책 $\pi$ 아래에서 행해지는 에피소드들을 통해 $q_\pi$ 를 학습하는 것이다.

MC 는 DP 와 달리 기대값이 아닌 경험적 평균 (empirical mean) 을 사용한다. 여기에는 두 가지 방식이 있다.

• First-Visit : 첫 번째 방문을 기준으로 계산 (안정성 높고 수렴성 낮다)