04. 몬테카를로 방법 (Monte Carlo Methods)¶

난이도: ⭐⭐ (기초)

학습 목표¶

몬테카를로(MC) 방법의 기본 개념 이해
모델 프리(Model-Free) 학습의 의미 파악
First-visit MC와 Every-visit MC의 차이 이해
MC 정책 평가 및 제어 알고리즘 구현
탐험의 중요성과 해결 방법 학습

1. 몬테카를로 방법이란?¶

1.1 개요¶

몬테카를로(Monte Carlo, MC) 방법은 실제 경험(에피소드)으로부터 가치 함수를 추정하는 방법입니다. 환경 모델 없이 학습하는 모델 프리(Model-Free) 방법입니다.

1.2 DP vs MC 비교¶

특성	동적 프로그래밍 (DP)	몬테카를로 (MC)
환경 모델	필요 (P, R 알아야 함)	불필요
학습 방식	계산 (부트스트래핑)	샘플링 (경험)
업데이트 시점	매 스텝 가능	에피소드 종료 후
적용 환경	에피소딕/연속	에피소딕만

1.3 핵심 아이디어¶

$$V(s) \approx \text{평균}(\text{상태 } s \text{에서 시작한 에피소드들의 리턴})$$

에피소드 1: S₀ → S₁ → S₂ → ... → 종료, G₁ = 10
에피소드 2: S₀ → S₃ → S₁ → ... → 종료, G₂ = 8
에피소드 3: S₀ → S₂ → S₁ → ... → 종료, G₃ = 12

V(S₀) = (10 + 8 + 12) / 3 = 10

2. 리턴 (Return) 계산¶

2.1 에피소드에서 리턴 계산¶

def calculate_returns(episode, gamma=0.99):
    """
    에피소드에서 각 상태의 리턴 계산

    Args:
        episode: [(state, action, reward), ...] 형태의 리스트
        gamma: 할인율

    Returns:
        returns: {state: return} 딕셔너리
    """
    G = 0  # 리턴 초기화
    returns = {}

    # 역순으로 계산 (효율적인 계산)
    for t in range(len(episode) - 1, -1, -1):
        state, action, reward = episode[t]
        G = reward + gamma * G  # 할인된 리턴
        returns[t] = (state, G)

    return returns


# 예시
episode = [
    ('s0', 'right', -1),
    ('s1', 'right', -1),
    ('s2', 'right', 10),  # 목표 도달
]

returns = calculate_returns(episode, gamma=0.9)
for t, (state, G) in returns.items():
    print(f"t={t}: {state}, G={G:.2f}")

# 출력:
# t=2: s2, G=10.00
# t=1: s1, G=8.00  (= -1 + 0.9 * 10)
# t=0: s0, G=6.20  (= -1 + 0.9 * 8)

3. MC 정책 평가¶

3.1 First-visit MC vs Every-visit MC¶

방법	설명
First-visit MC	에피소드에서 상태 s를 처음 방문했을 때만 리턴 기록
Every-visit MC	에피소드에서 상태 s를 방문할 때마다 리턴 기록

에피소드: S₀ → S₁ → S₂ → S₁ → S₃ (종료)
                     ↑      ↑
              첫 방문   두 번째 방문

First-visit: S₁의 첫 방문만 카운트
Every-visit: S₁의 모든 방문 카운트

3.2 First-visit MC 구현¶

import numpy as np
from collections import defaultdict

def first_visit_mc_prediction(env, policy, n_episodes=10000, gamma=0.99):
    """
    First-visit MC 정책 평가

    Args:
        env: Gymnasium 환경
        policy: 정책 함수 policy(state) -> action
        n_episodes: 에피소드 수
        gamma: 할인율

    Returns:
        V: 상태 가치 함수
    """
    # 각 상태의 리턴 합과 방문 횟수
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    V = defaultdict(float)

    for episode_num in range(n_episodes):
        # 에피소드 생성
        episode = []
        state, _ = env.reset()
        done = False

        while not done:
            action = policy(state)
            next_state, reward, terminated, truncated, _ = env.step(action)
            episode.append((state, action, reward))
            state = next_state
            done = terminated or truncated

        # First-visit: 각 상태의 첫 방문 인덱스 찾기
        visited = set()
        G = 0

        # 역순으로 리턴 계산
        for t in range(len(episode) - 1, -1, -1):
            state_t, action_t, reward_t = episode[t]

            G = gamma * G + reward_t

            # First-visit 체크
            if state_t not in visited:
                visited.add(state_t)
                returns_sum[state_t] += G
                returns_count[state_t] += 1
                V[state_t] = returns_sum[state_t] / returns_count[state_t]

        if (episode_num + 1) % 1000 == 0:
            print(f"Episode {episode_num + 1}/{n_episodes}")

    return dict(V)


# 사용 예시
import gymnasium as gym

env = gym.make('Blackjack-v1')

def random_policy(state):
    """랜덤 정책"""
    return env.action_space.sample()

V = first_visit_mc_prediction(env, random_policy, n_episodes=50000)
print(f"\n추정된 상태 수: {len(V)}")

3.3 Every-visit MC 구현¶

def every_visit_mc_prediction(env, policy, n_episodes=10000, gamma=0.99):
    """
    Every-visit MC 정책 평가
    """
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    V = defaultdict(float)

    for episode_num in range(n_episodes):
        episode = []
        state, _ = env.reset()
        done = False

        while not done:
            action = policy(state)
            next_state, reward, terminated, truncated, _ = env.step(action)
            episode.append((state, action, reward))
            state = next_state
            done = terminated or truncated

        G = 0

        # Every-visit: 모든 방문에서 업데이트
        for t in range(len(episode) - 1, -1, -1):
            state_t, action_t, reward_t = episode[t]

            G = gamma * G + reward_t

            # 모든 방문 카운트
            returns_sum[state_t] += G
            returns_count[state_t] += 1
            V[state_t] = returns_sum[state_t] / returns_count[state_t]

    return dict(V)

4. MC 정책 제어¶

4.1 Exploring Starts (ES)¶

모든 상태-행동 쌍에서 에피소드가 시작할 수 있다고 가정합니다.

def mc_exploring_starts(env, n_episodes=100000, gamma=0.99):
    """
    MC with Exploring Starts

    모든 (s, a) 쌍이 시작점이 될 수 있음을 가정
    """
    n_states = env.observation_space.n
    n_actions = env.action_space.n

    # Q 함수와 방문 횟수 초기화
    Q = defaultdict(lambda: np.zeros(n_actions))
    returns_sum = defaultdict(lambda: np.zeros(n_actions))
    returns_count = defaultdict(lambda: np.zeros(n_actions))

    # 정책 (탐욕적)
    policy = defaultdict(lambda: 0)

    for episode_num in range(n_episodes):
        # Exploring Starts: 랜덤한 상태와 행동으로 시작
        start_state = env.observation_space.sample()
        start_action = env.action_space.sample()

        # 에피소드 생성
        episode = []
        state = start_state
        action = start_action

        # 첫 스텝
        env.reset()
        env.unwrapped.s = state  # 상태 강제 설정 (환경에 따라 다름)
        next_state, reward, terminated, truncated, _ = env.step(action)
        episode.append((state, action, reward))
        state = next_state
        done = terminated or truncated

        # 나머지 에피소드
        while not done:
            action = policy[state]
            next_state, reward, terminated, truncated, _ = env.step(action)
            episode.append((state, action, reward))
            state = next_state
            done = terminated or truncated

        # 리턴 계산 및 Q 업데이트
        G = 0
        visited = set()

        for t in range(len(episode) - 1, -1, -1):
            state_t, action_t, reward_t = episode[t]
            G = gamma * G + reward_t

            if (state_t, action_t) not in visited:
                visited.add((state_t, action_t))
                returns_sum[state_t][action_t] += G
                returns_count[state_t][action_t] += 1
                Q[state_t][action_t] = (returns_sum[state_t][action_t] /
                                        returns_count[state_t][action_t])

                # 정책 개선 (탐욕적)
                policy[state_t] = np.argmax(Q[state_t])

    return Q, policy

4.2 ε-greedy 정책¶

Exploring Starts는 현실적이지 않으므로, ε-greedy 정책을 사용합니다.

$$\pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|A|} & \text{if } a = \arg\max_{a'} Q(s, a') \\ \frac{\epsilon}{|A|} & \text{otherwise} \end{cases}$$

def epsilon_greedy_policy(Q, state, n_actions, epsilon=0.1):
    """
    ε-탐욕 행동 선택

    Args:
        Q: 행동 가치 함수
        state: 현재 상태
        n_actions: 행동 수
        epsilon: 탐험 확률

    Returns:
        action: 선택된 행동
    """
    if np.random.random() < epsilon:
        # 탐험: 랜덤 행동
        return np.random.randint(n_actions)
    else:
        # 활용: 최선의 행동
        return np.argmax(Q[state])

4.3 On-policy MC 제어¶

def mc_on_policy_control(env, n_episodes=100000, gamma=0.99,
                         epsilon=0.1, epsilon_decay=0.9999):
    """
    On-policy MC 제어 (ε-greedy)

    Args:
        env: Gymnasium 환경
        n_episodes: 에피소드 수
        gamma: 할인율
        epsilon: 탐험율
        epsilon_decay: epsilon 감소율

    Returns:
        Q: 행동 가치 함수
        policy: 학습된 정책
    """
    n_actions = env.action_space.n

    Q = defaultdict(lambda: np.zeros(n_actions))
    returns_sum = defaultdict(lambda: np.zeros(n_actions))
    returns_count = defaultdict(lambda: np.zeros(n_actions))

    episode_rewards = []

    for episode_num in range(n_episodes):
        episode = []
        state, _ = env.reset()
        done = False
        total_reward = 0

        # ε-greedy 정책으로 에피소드 생성
        while not done:
            action = epsilon_greedy_policy(Q, state, n_actions, epsilon)
            next_state, reward, terminated, truncated, _ = env.step(action)

            episode.append((state, action, reward))
            total_reward += reward

            state = next_state
            done = terminated or truncated

        episode_rewards.append(total_reward)

        # Q 업데이트 (First-visit)
        G = 0
        visited = set()

        for t in range(len(episode) - 1, -1, -1):
            state_t, action_t, reward_t = episode[t]
            G = gamma * G + reward_t

            if (state_t, action_t) not in visited:
                visited.add((state_t, action_t))
                returns_sum[state_t][action_t] += G
                returns_count[state_t][action_t] += 1
                Q[state_t][action_t] = (returns_sum[state_t][action_t] /
                                        returns_count[state_t][action_t])

        # epsilon 감소
        epsilon = max(0.01, epsilon * epsilon_decay)

        if (episode_num + 1) % 10000 == 0:
            avg_reward = np.mean(episode_rewards[-1000:])
            print(f"Episode {episode_num + 1}: avg_reward = {avg_reward:.3f}, "
                  f"epsilon = {epsilon:.4f}")

    # 최종 탐욕적 정책
    policy = {}
    for state in Q:
        policy[state] = np.argmax(Q[state])

    return dict(Q), policy, episode_rewards

5. Off-policy MC (Importance Sampling)¶

5.1 Off-policy 학습이란?¶

On-policy: 행동 정책 = 목표 정책 (같은 정책으로 탐험하고 학습)
Off-policy: 행동 정책 ≠ 목표 정책 (다른 정책으로 탐험하고 학습)

행동 정책 (Behavior Policy) b: 데이터 수집용
목표 정책 (Target Policy) π: 학습하고자 하는 최적 정책

5.2 중요도 샘플링 (Importance Sampling)¶

$$\mathbb{E}_b[X] = \sum_x x \cdot b(x) = \sum_x x \cdot \frac{\pi(x)}{b(x)} \cdot b(x) = \mathbb{E}_b\left[\frac{\pi(X)}{b(X)} X\right]$$

중요도 샘플링 비율: $$\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}$$

def importance_sampling_ratio(episode, target_policy, behavior_policy, t):
    """
    중요도 샘플링 비율 계산

    ρ = π(a₀|s₀)/b(a₀|s₀) × π(a₁|s₁)/b(a₁|s₁) × ...
    """
    rho = 1.0

    for k in range(t, len(episode)):
        state, action, _ = episode[k]
        pi_prob = target_policy(state, action)  # π(a|s)
        b_prob = behavior_policy(state, action)  # b(a|s)

        if b_prob == 0:
            return 0  # 행동 정책에서 불가능한 행동

        rho *= pi_prob / b_prob

    return rho

5.3 Off-policy MC 구현¶

def mc_off_policy_prediction(env, target_policy, behavior_policy,
                              n_episodes=100000, gamma=0.99):
    """
    Off-policy MC 정책 평가 (Weighted Importance Sampling)

    Args:
        target_policy: 목표 정책 (결정적) - π(s) -> a
        behavior_policy: 행동 정책 - b(s) -> a (ε-greedy 등)
    """
    Q = defaultdict(lambda: np.zeros(env.action_space.n))
    C = defaultdict(lambda: np.zeros(env.action_space.n))  # 가중치 합

    for episode_num in range(n_episodes):
        # 행동 정책으로 에피소드 생성
        episode = []
        state, _ = env.reset()
        done = False

        while not done:
            action = behavior_policy(state)
            next_state, reward, terminated, truncated, _ = env.step(action)
            episode.append((state, action, reward))
            state = next_state
            done = terminated or truncated

        G = 0
        W = 1.0  # 중요도 샘플링 가중치

        # 역순 처리
        for t in range(len(episode) - 1, -1, -1):
            state_t, action_t, reward_t = episode[t]
            G = gamma * G + reward_t

            # 가중 중요도 샘플링 업데이트
            C[state_t][action_t] += W
            Q[state_t][action_t] += W / C[state_t][action_t] * (G - Q[state_t][action_t])

            # 목표 정책에서의 행동
            target_action = target_policy(state_t)

            # 행동이 목표 정책과 다르면 중단 (결정적 정책의 경우)
            if action_t != target_action:
                break

            # 중요도 비율 업데이트
            # π(a|s) = 1 (결정적), b(a|s) = 행동 정책 확률
            b_prob = behavior_policy_prob(state_t, action_t)  # 구현 필요
            W = W * 1.0 / b_prob

    return dict(Q)

6. 블랙잭 예제¶

6.1 블랙잭 환경¶

import gymnasium as gym
import numpy as np
from collections import defaultdict

# 블랙잭 환경
# 상태: (플레이어 합, 딜러 오픈카드, 사용 가능한 에이스)
# 행동: 0 = stick (패 유지), 1 = hit (카드 추가)

env = gym.make('Blackjack-v1', sab=True)  # sab: Sutton and Barto 버전

print("상태 공간:", env.observation_space)
print("행동 공간:", env.action_space)

6.2 블랙잭에서 MC 학습¶

def learn_blackjack(n_episodes=500000, gamma=1.0, epsilon=0.1):
    """블랙잭에서 MC 제어"""

    env = gym.make('Blackjack-v1', sab=True)

    Q = defaultdict(lambda: np.zeros(2))
    returns_sum = defaultdict(lambda: np.zeros(2))
    returns_count = defaultdict(lambda: np.zeros(2))

    def get_action(state, Q, epsilon):
        if np.random.random() < epsilon:
            return env.action_space.sample()
        return np.argmax(Q[state])

    wins = 0
    for ep in range(n_episodes):
        episode = []
        state, _ = env.reset()
        done = False

        while not done:
            action = get_action(state, Q, epsilon)
            next_state, reward, terminated, truncated, _ = env.step(action)
            episode.append((state, action, reward))
            state = next_state
            done = terminated or truncated

        if episode[-1][2] == 1:  # 승리
            wins += 1

        # Q 업데이트
        G = 0
        visited = set()

        for t in range(len(episode) - 1, -1, -1):
            state_t, action_t, reward_t = episode[t]
            G = gamma * G + reward_t

            if (state_t, action_t) not in visited:
                visited.add((state_t, action_t))
                returns_sum[state_t][action_t] += G
                returns_count[state_t][action_t] += 1
                Q[state_t][action_t] = (returns_sum[state_t][action_t] /
                                        returns_count[state_t][action_t])

        if (ep + 1) % 50000 == 0:
            win_rate = wins / (ep + 1)
            print(f"Episode {ep + 1}: 승률 = {win_rate:.3f}")

    env.close()
    return Q


def visualize_blackjack_policy(Q):
    """블랙잭 정책 시각화"""
    print("\n=== 사용 가능한 에이스가 없을 때 ===")
    print("딜러 카드:  A  2  3  4  5  6  7  8  9  10")
    print("-" * 50)

    for player_sum in range(21, 10, -1):
        row = f"합계 {player_sum:2d}:  "
        for dealer in range(1, 11):
            state = (player_sum, dealer, False)
            if state in Q:
                action = np.argmax(Q[state])
                row += "H  " if action == 1 else "S  "
            else:
                row += "?  "
        print(row)

    print("\n=== 사용 가능한 에이스가 있을 때 ===")
    print("딜러 카드:  A  2  3  4  5  6  7  8  9  10")
    print("-" * 50)

    for player_sum in range(21, 11, -1):
        row = f"합계 {player_sum:2d}:  "
        for dealer in range(1, 11):
            state = (player_sum, dealer, True)
            if state in Q:
                action = np.argmax(Q[state])
                row += "H  " if action == 1 else "S  "
            else:
                row += "?  "
        print(row)


# 학습 실행
Q = learn_blackjack(n_episodes=500000)
visualize_blackjack_policy(Q)

7. MC 방법의 장단점¶

7.1 장점¶

장점	설명
모델 프리	환경 모델 불필요
편향 없음	부트스트래핑 없이 실제 리턴 사용
직관적	평균 리턴 계산으로 간단함
에피소드 독립	에피소드별 병렬 처리 가능

7.2 단점¶

단점	설명
높은 분산	전체 리턴의 분산이 큼
에피소드 종료 필요	연속 태스크에 부적합
느린 학습	에피소드 끝까지 기다려야 함
탐험 문제	방문하지 않은 상태 학습 불가

7.3 DP vs MC 요약¶

                    DP                    MC
              ─────────────          ─────────────
필요 정보     환경 모델              경험 (에피소드)

업데이트      V(s) ← Σ P(s'|s,a)    V(s) ← 평균(G)
방식          [R + γV(s')]

편향          편향 있음              편향 없음
              (부트스트랩)           (실제 리턴)

분산          낮음                   높음
              (기대값 계산)          (샘플 분산)

적용 환경     유한 MDP               에피소딕 태스크

8. 요약¶

핵심 개념¶

개념	설명
몬테카를로	경험으로부터 학습
First-visit	첫 방문만 카운트
Every-visit	모든 방문 카운트
On-policy	행동 정책 = 목표 정책
Off-policy	행동 정책 ≠ 목표 정책
Importance Sampling	분포 보정을 위한 가중치

MC 정책 평가 공식¶

$$V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i(s)$$

MC Q-함수 업데이트¶

$$Q(s, a) \leftarrow Q(s, a) + \frac{1}{N(s,a)} (G - Q(s, a))$$

9. 연습 문제¶

First-visit vs Every-visit: 동일한 상태를 3번 방문하는 에피소드에서 두 방법의 차이를 계산하세요.
탐험 문제: ε-greedy에서 ε=0이면 어떤 문제가 발생하나요?
Importance Sampling: 목표 정책이 결정적이고 행동 정책이 ε-greedy일 때, 중요도 비율이 발산할 수 있는 경우는?
수렴 속도: MC의 분산이 높은 이유와 해결 방법을 설명하세요.

다음 단계¶

다음 레슨 05_TD_Learning.md에서는 DP의 부트스트래핑과 MC의 샘플링을 결합한 TD 학습을 배웁니다.

참고 자료¶

Sutton & Barto, "Reinforcement Learning: An Introduction", Chapter 5
David Silver's RL Course, Lecture 4: Model-Free Prediction
Gymnasium Blackjack