몬테카를로 방법(Monte Carlo Methods) — 완전한 에피소드에서 학습하기(Learning from Complete Episodes)

동적 계획법(Dynamic Programming; DP)은 모델(model)이 필요합니다. 몬테카를로(Monte Carlo; MC)는 에피소드(episode)만 있으면 됩니다. 정책을 실행하고, 리턴(returns)을 관측하고, 평균을 냅니다. 강화학습(Reinforcement Learning; RL)에서 가장 단순한 아이디어이며, 이후 모든 것을 열어주는 아이디어입니다.

유형: Build 언어: Python 선수 지식: Phase 9 · 01 (MDP), Phase 9 · 02 (동적 계획법; Dynamic Programming) 예상 시간: 약 75분

문제

동적 계획법은 우아하지만 모든 상태와 행동에 대해 P(s' | s, a)를 질의할 수 있다고 가정합니다. 현실 세계에서 그런 식으로 동작하는 시스템은 거의 없습니다. 로봇은 관절 토크(joint torque)를 가한 뒤 카메라 픽셀 분포를 해석적으로 계산할 수 없습니다. 가격 알고리즘(pricing algorithm)은 가능한 모든 고객 반응을 적분으로 다룰 수 없습니다. 거대 언어 모델(LLM)은 한 토큰 이후에 등장 가능한 모든 연속(continuation)을 일일이 열거할 수 없습니다.

필요한 것은 환경(environment)에서 *샘플링(sample)*만 할 수 있으면 되는 방법입니다. 정책을 실행합니다. 궤적(trajectory) s_0, a_0, r_1, s_1, a_1, r_2, …, s_T를 얻습니다. 이것으로 가치를 추정합니다. 이것이 바로 몬테카를로입니다.

DP에서 MC로의 전환은 철학적으로 중요합니다. 우리는 *알려진 모델 + 정확한 백업(backup)*에서 샘플링된 롤아웃(rollout) + 평균 리턴으로 이동합니다. 분산(variance)은 커지지만 적용 가능성(applicability)은 폭발적으로 넓어집니다. 이 강의 이후의 모든 RL 알고리즘, 즉 시간차 학습(Temporal Difference; TD), Q-러닝(Q-learning), REINFORCE, PPO, GRPO는 본질적으로 몬테카를로 추정량(Monte Carlo estimator)이며, 때로 그 위에 부트스트래핑(bootstrapping)을 얹은 형태입니다.

개념

핵심 아이디어를 한 줄로 쓰면 다음과 같습니다. V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^{(i)}(s)입니다. 여기서 G^{(i)}(s)는 정책 π 아래에서 상태 s를 방문한 뒤 관측된 리턴입니다.

첫 방문 MC와 모든 방문 MC(First-visit vs every-visit MC). 한 에피소드가 상태 s를 여러 번 방문했다면, 첫 방문 MC(first-visit MC)는 첫 방문에서의 리턴만 셉니다. 모든 방문 MC(every-visit MC)는 모든 방문을 셉니다. 둘 다 극한에서는 편향이 없습니다(unbiased in the limit). 첫 방문 방식은 독립 동일 분포(iid) 샘플에 가깝기 때문에 분석하기가 더 쉽습니다. 모든 방문 방식은 에피소드당 더 많은 데이터를 사용하므로 실제로는 보통 더 빨리 수렴합니다.

증분 평균(Incremental mean). 모든 리턴을 저장하지 않고 이동 평균(running average)을 갱신합니다.

V_n(s) = V_{n-1}(s) + (1/n) [G_n - V_{n-1}(s)]

다시 쓰면 V_new = V_old + α · (target - V_old)이고 α = 1/n입니다. 1/n을 상수 학습률(step-size) α ∈ (0, 1)로 바꾸면 π의 변화를 따라가는 비정상(non-stationary) MC 추정량이 됩니다. 이 전환이 MC에서 TD, 그리고 모든 현대 RL 알고리즘으로 이어지는 전체 도약입니다.

탐험(exploration)이 이제 문제가 됩니다. DP는 모든 상태를 열거(enumeration)해서 빠짐없이 다뤘습니다. MC는 정책이 방문하는 상태만 봅니다. π가 결정론적(deterministic)이면 상태 공간의 넓은 영역은 샘플링되지 않고, 해당 가치 추정값은 영원히 0에 머뭅니다. 역사적 순서로 세 가지 해결책이 있습니다.

1. 탐험적 시작(Exploring starts). 각 에피소드를 임의의 (s, a) 쌍에서 시작합니다. 모든 영역의 표본 확보(coverage)를 보장하지만 실제로는 비현실적입니다. 로봇을 임의 상태로 초기화(reset)할 수는 없기 때문입니다.
2. ε-탐욕(ε-greedy). 현재 Q에 대해 탐욕적으로(greedy) 행동하되, 확률 ε로 무작위 행동을 선택합니다. 모든 상태-행동 쌍이 점근적으로 샘플링됩니다.
3. 비활성 정책 MC(Off-policy MC). 행동 정책(behavior policy) μ 아래에서 데이터를 모으고, 중요도 샘플링(importance sampling)으로 목표 정책(target policy) π에 대해 학습합니다. 분산은 높지만, DQN 같은 재현 버퍼(replay buffer) 기반 방법으로 이어지는 다리 역할을 합니다.

몬테카를로 제어(Monte Carlo Control). 정책 반복(policy iteration)처럼 평가 → 개선 → 평가를 수행하되, 평가는 샘플링 기반입니다.

1. π를 실행해 에피소드를 얻습니다.
2. 관측 리턴으로 Q(s, a)를 갱신합니다.
3. Q에 대해 π를 ε-탐욕적으로 만듭니다.
4. 반복합니다.

완만한 조건(mild conditions), 즉 모든 쌍이 무한히 자주 방문되고 α가 로빈스-먼로(Robbins-Monro) 조건을 만족하면 확률 1로 Q*와 π*에 수렴합니다.

직접 만들기

Step 1: 롤아웃(rollout) → (s, a, r) 리스트

def rollout(env, policy, max_steps=200):
    trajectory = []
    s = env.reset()
    for _ in range(max_steps):
        a = policy(s)
        s_next, r, done = env.step(s, a)
        trajectory.append((s, a, r))
        s = s_next
        if done:
            break
    return trajectory

모델은 없습니다. env.reset()과 env.step(s, a)만 있으면 됩니다. gym 환경과 같은 인터페이스지만 더 단순하게 벗겨낸 형태입니다.

Step 2: 리턴 계산하기(역방향 순회; reverse sweep)

def returns_from(trajectory, gamma):
    returns = []
    G = 0.0
    for _, _, r in reversed(trajectory):
        G = r + gamma * G
        returns.append(G)
    return list(reversed(returns))

한 번의 순회로 O(T)에 끝납니다. 뒤쪽으로 가는 점화식(recurrence) G_t = r_{t+1} + γ G_{t+1}를 사용하면 매번 다시 합산하지 않아도 됩니다.

Step 3: 첫 방문 MC 평가(first-visit MC evaluation)

def mc_policy_evaluation(env, policy, episodes, gamma=0.99):
    V = defaultdict(float)
    counts = defaultdict(int)
    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for t, ((s, _, _), G) in enumerate(zip(trajectory, returns)):
            if s in seen:
                continue
            seen.add(s)
            counts[s] += 1
            V[s] += (G - V[s]) / counts[s]
    return V

세 줄이 핵심입니다. 상태를 첫 방문 시점에 seen으로 표시하고, 카운트를 증가시키고, 이동 평균(running mean)을 갱신합니다.

Step 4: ε-탐욕(ε-greedy) MC 제어(활성 정책; on-policy)

def mc_control(env, episodes, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    counts = defaultdict(lambda: {a: 0 for a in ACTIONS})

    def policy(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)

    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for (s, a, _), G in zip(trajectory, returns):
            if (s, a) in seen:
                continue
            seen.add((s, a))
            counts[s][a] += 1
            Q[s][a] += (G - Q[s][a]) / counts[s][a]
    return Q, policy

Step 5: DP 기준값(gold standard)과 비교하기

V^π의 MC 추정값은 에피소드 수가 무한대로 갈 때 Lesson 02의 DP 결과와 일치해야 합니다. 실제로는 4×4 GridWorld에서 에피소드 50,000개를 돌리면 DP 정답의 대략 ~0.1 안쪽까지 가까워집니다.

주의할 점

• 무한 에피소드(Infinite episodes). MC는 에피소드가 끝나야 합니다. 정책이 영원히 반복(loop)될 수 있다면 max_steps를 두고, 상한(cap)에 도달한 경우를 암묵적 실패(implicit failure)로 취급합니다. 무작위 정책의 GridWorld에서 자주 시간 초과(timeout)가 나는 것은 정상이며, 올바르게 카운트만 하면 됩니다.
• 분산(Variance). MC는 전체 리턴(full returns)을 사용합니다. 긴 에피소드에서는 분산이 큽니다. 끝에서의 불운한 보상 하나가 V(s_0)를 같은 크기만큼 흔듭니다. TD 방법(Lesson 04)은 부트스트래핑으로 이를 줄입니다.
• 상태 표본 확보(State coverage). 새 Q에서 동률이 있는 탐욕적 MC는 한 행동만 계속 시도할 수 있습니다. 반드시 탐험을 도입해야 합니다. ε-탐욕, 탐험적 시작(exploring starts), UCB 같은 방법을 사용합니다.
• 비정상 정책(Non-stationary policies). MC 제어처럼 π가 바뀌면 오래된 리턴은 다른 정책에서 나온 것이 됩니다. 상수 α MC는 이를 처리할 수 있지만 표본 평균(sample-average) MC는 그렇지 않습니다.
• 비활성 정책 중요도 샘플링(Off-policy importance sampling). 가중치 π(a|s)/μ(a|s)는 궤적 전체에서 곱해집니다. 시계열 길이(horizon)가 길면 분산이 폭발합니다. 결정별(per-decision) 가중 중요도 샘플링(weighted IS)으로 제한하거나 TD로 전환합니다.

사용해보기

2026년 시점 몬테카를로 방법의 역할은 다음과 같습니다.

현대 심층 강화학습(deep-RL) 알고리즘(PPO, SAC)은 n-스텝 리턴(n-step returns) 또는 일반화 어드밴티지 추정(Generalized Advantage Estimation; GAE)을 통해 순수 MC(전체 리턴)와 순수 TD(1-스텝 부트스트랩) 사이를 보간합니다. 양 끝점 모두 같은 추정량(estimator)의 한 사례입니다.

산출물 만들기

outputs/skill-mc-evaluator.md로 저장합니다.

---
name: mc-evaluator
description: Evaluate a policy via Monte Carlo rollouts and produce a convergence report with DP-comparison if available.
version: 1.0.0
phase: 9
lesson: 3
tags: [rl, monte-carlo, evaluation]
---

Given an environment (episodic, with reset+step API) and a policy, output:

Guide the student in Korean.

1. Method. First-visit vs every-visit MC. Reason.
2. Episode budget. Target number, variance diagnostic, expected standard error.
3. Exploration plan. ε schedule (if needed) or exploring starts.
4. Gold-standard comparison. DP-optimal V* if tabular; otherwise a bound from a Q-learning / PPO baseline.
5. Termination check. Max-step cap, timeouts, handling of non-terminating trajectories.

Refuse to run MC on non-episodic tasks without a finite horizon cap. Refuse to report V^π estimates from fewer than 100 episodes per state for tabular tasks. Flag any policy with zero-variance actions as an exploration risk.

연습문제

1. 쉬움. 4×4 GridWorld에서 균등 무작위 정책(uniform-random policy)의 첫 방문 MC 평가를 구현합니다. 에피소드 10,000개를 실행합니다. 에피소드 수에 따른 V(0,0) 값을 DP 정답과 함께 그래프로 그려 봅니다.
2. 중간. ε ∈ {0.01, 0.1, 0.3}로 ε-탐욕 MC 제어를 구현합니다. 에피소드 20,000개 이후의 평균 리턴을 비교합니다. 곡선은 어떤 모양인가요? 편향-분산 절충(bias-variance tradeoff)은 어디에 위치하나요?
3. 어려움. 중요도 샘플링(importance sampling)을 사용해 비활성 정책(off-policy) MC를 구현합니다. 균등 무작위 정책 μ 아래에서 데이터를 모으고, 결정론적 최적 정책 π의 V^π를 추정합니다. 단순 IS(plain IS), 결정별 IS(per-decision IS), 가중 IS(weighted IS)를 비교합니다. 어느 쪽의 분산이 가장 낮은가요?

핵심 용어

더 읽을거리

• Sutton & Barto (2018). Ch. 5 — Monte Carlo Methods — 정전(canonical)에 해당하는 표준 설명입니다.
• Singh & Sutton (1996). Reinforcement Learning with Replacing Eligibility Traces — 첫 방문(first-visit)과 모든 방문(every-visit) 분석을 다룹니다.
• Precup, Sutton, Singh (2000). Eligibility Traces for Off-Policy Policy Evaluation — 비활성 정책 MC와 분산 제어를 다룹니다.
• Mahmood et al. (2014). Weighted Importance Sampling for Off-Policy Learning — 현대적 저분산 중요도 샘플링 추정량을 다룹니다.
• Tesauro (1995). TD-Gammon, A Self-Teaching Backgammon Program — MC/TD 셀프 플레이(self-play)가 초인적 수준의 플레이로 수렴할 수 있음을 보인 첫 대규모 실증입니다. 이 phase 후반부 모든 lesson의 개념적 선행 사례입니다.