[강화학습-5] 몬테카를로 방법 (Monte Carlo Methods)

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

“모형이 없을 때, 우리는 실제 경험을 모아 평균을 낸다.”
몬테카를로(MC) 방법은 환경 모델이 없더라도 에피소드를 완주하고 얻은 표본 Return의 평균으로 가치함수를 추정합니다.

---

5-1. 에피소드 기반 학습

특징	설명
샘플 단위	전체 에피소드 $(S_0,A_0,R_1,\dots,S_T)$
업데이트 시점	에피소드가 끝난 뒤 한꺼번에
편향	없음 (표본 평균이 불편추정량)
분산	높음 → 많은 에피소드 필요

$$G_t \;=\; R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$$

MC 추정치 $\hat V(s)$ 는 $G_t$ (여러 에피소드) 평균으로 수렴합니다.

---

5-2. First-visit vs Every-visit MC

방식	업데이트 시점	수렴 성질
First-visit	각 에피소드에서 처음 방문한 $s$에 대해서만 $G_t$ 저장 / 평균	천천히 업데이트 하지만 표본간 상관↓ → 분산 조금 낮음
Every-visit	에피소드에서 $s$가 나올 때마다 $G_t$ 추가	표본 많음 → 속도↑ (약간 상관 있어도 불편)

두 방법 모두 Law of Large Numbers 덕분에 $$\hat V(s)\;\xrightarrow{\;p\;}\;V_\pi(s)$$ 로 수렴합니다.

---

5-3. 탐험 vs 활용 균형 (ε-Greedy)

Exploration 없이는 최적 정책을 찾을 수 없고,
Exploitation 없이는 배운 것을 활용할 수 없습니다.

• 정책 $\pi_\epsilon$ : $$\pi_\epsilon(a\mid s)= \begin{cases} 1-\epsilon + \dfrac{\epsilon}{|\mathcal{A}|} & \text{if } a = a^\* \\ \dfrac{\epsilon}{|\mathcal{A}|} & \text{otherwise} \end{cases}$$
• $a^\*$ 은 $Q(s,a)$ 가 최대인 탐욕적 행동.
• $\epsilon$ 스케줄 ➜ ε(t)=ε_0·0.99^t 처럼 점진적 감소가 일반적.

---

5-4. 코드 실습 : FrozenLake Monte Carlo Control

목표 : $8×8$ FrozenLake-v1 에서 MC Control with ε-greedy로 $Q^\*$ 및 $\pi^\*$ 학습

import gym
import numpy as np
from collections import defaultdict

env = gym.make("FrozenLake-v1", map_name="8x8", is_slippery=True)
n_states  = env.observation_space.n
n_actions = env.action_space.n

def epsilon_greedy(Q, state, eps):
    if np.random.rand() < eps:
        return env.action_space.sample()
    return np.argmax(Q[state])

episodes   = 50_000
gamma      = 0.99
epsilon    = 1.0
eps_decay  = 0.9995
eps_min    = 0.05
alpha      = 0.1               # step-size (incremental mean)

Q  = np.zeros((n_states, n_actions))
N  = np.zeros_like(Q)          # 방문 횟수 (평균 계산용)

for ep in range(episodes):
    state = env.reset(seed=None, return_info=False)
    episode = []

    # 1️⃣ 에피소드 수집
    done = False
    while not done:
        action = epsilon_greedy(Q, state, epsilon)
        next_state, reward, done, _ = env.step(action)
        episode.append((state, action, reward))
        state = next_state

    # 2️⃣ Return 계산 & every-visit 업데이트
    G = 0.0
    for (s, a, r) in reversed(episode):
        G = gamma * G + r      # 뒤에서부터 누적
        N[s, a] += 1
        Q[s, a] += alpha * (G - Q[s, a])   # incremental MC

    epsilon = max(eps_min, epsilon * eps_decay)

# 최종 정책
policy = np.argmax(Q, axis=1)
print("FrozenLake 8×8 – MC Control 완료, ε =", round(epsilon,3))

TIP 1 : Gym 패키지가 없다면 pip install gym==0.25 gym[toy_text] 로 설치.
TIP 2 : 모든 $\epsilon$ 탐험 데이터를 그대로 평균내면 온-폴리시(First-visit / Every-visit) MC 컨트롤이 됩니다.

---

5-5. MC 방법 vs TD 방법 미리보기

	Monte Carlo	TD(0)
업데이트 단위	에피소드 종료 후	매 타임스텝
편향	없음	조금 있음
분산	높음	낮음
온/오프-폴리시	둘 다 가능	둘 다 가능(Q-learning 등)

---

5-6. 요약 & 다음 편 예고

• MC 방법은 모델 없이 “경험 평균”으로 가치·정책을 추정한다.
• First-visit / Every-visit 모델 – 두 방식 모두 $V_\pi$ 로 수렴한다.
• 탐험·활용 균형은 ε-Greedy 전략으로 간단히 구현할 수 있다.
• 다음 글에서 시간차(TD) 학습을 통해 빠르고 온라인 업데이트가 어떻게 가능한지 살펴본다.

---

참고 자료

• Sutton & Barto, Reinforcement Learning: An Introduction, Ch. 5
• David Silver, RL Course Lecture 4 – Monte Carlo Methods
• OpenAI Gym FrozenLake-v1 환경 소스코드