Monte Carlo와 TD Learning - GridWorld로 비교하는 모델 프리 가치 학습

MDP를 모르더라도 가치 함수를 배울 수 있을까?

강화학습에서 환경을 완전히 안다는 것은 다음을 모두 아는 상황이다.

• 상태 집합 (S)
• 행동 집합 (A)
• 상태 전이 확률 (P(s'\mid s,a))
• 보상 함수 (R(s,a,s'))

이 경우에는 벨만 방정식 을 그대로 풀어 가치 함수(Value) 를 수식으로 계산할 수 있다. 하지만 현실의 게임·로봇·자율주행·주식시장 같은 문제에서는 보통 (P(s'|s,a)), (R(s,a,s')) 를 모른다. 그래서 실제 환경에서 에피소드를 실행하며 얻은 경험 으로 가치를 추정해야 한다.

이 글에서는 이런 모델 프리(Model-Free) 가치 평가 방법인 Monte Carlo Learning 과 TD(Temporal Difference) Learning 의 아이디어를 정리하고, 4×4 GridWorld와 술취한 사람 1D·2D 예제로 두 방법을 비교한다.

(Monte Carlo Learning, TD Learning을 바탕으로 재구성했다.)

---

1. Monte Carlo Learning: 에피소드 끝까지 보고 평균내기

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

몬테카를로 방법론(Monte Carlo Method) 은 무작위 실험을 많이 반복해서 평균을 내는 방식 이다.

1. 무작위로 실험을 한다.
2. 실험을 아주 많이 반복한다.
3. 결과의 평균을 계산한다.

많은 랜덤 실험을 하면, 평균값이 실제 값에 점점 가까워진다.

1-2. 강화학습에서의 Monte Carlo Learning

현실에서는 보통 아래 정보를 모른다.

상태 전이 확률 P(s'|s,a)
보상 함수 R(s,a,s')

그래서 수식으로 정확히 계산할 수 없다. 이때 Monte Carlo Learning 은 다음 전략을 쓴다.

• 특정 상태에서 시작해 에피소드가 끝날 때까지 얻은 누적 보상(Return) 을 계산.
• 같은 상태에서 여러 번 에피소드를 실행해, Return들의 평균 으로 그 상태의 가치를 추정.

특징:

• 장점: 환경 모델이 필요 없는 모델 프리, 구현이 단순하고 직관적.
• 단점: 에피소드가 끝나야 값을 업데이트할 수 있어, 긴 문제에서는 학습이 느리다.

💬 에피소드 종료가 필요한 이유

Monte Carlo는 상태 (s) 의 가치를 (G_t) (그 상태 이후 전체 Return) 의 평균으로 정의한다.

V(s) ≈ 평균[ G_t | s_t = s ]
G_t = R_t + γ R_{t+1} + γ^2 R_{t+2} + …

Return (G_t) 는 에피소드가 끝나야 확정 되므로, Monte Carlo는 에피소드 전체를 실행한 후 그 Return으로 상태 가치를 업데이트한다.

---

2. GridWorld에서 Monte Carlo Learning 예제

4×4 GridWorld 환경:

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)  ← 목표 지점

• 시작 상태: (0, 0)
• 목표 상태: (3, 3)
• 행동: 0=왼쪽, 1=위, 2=오른쪽, 3=아래
• 매 이동마다 보상: -1
• 에이전트는 완전 랜덤 정책으로 움직인다.

목표: “이 칸에 오면, 목표까지 평균적으로 얼마나 손해(누적 -1)를 보게 되는가?” → 각 칸의 상태 가치를 추정.

2-1. 환경과 에이전트 정의

import random
import numpy as np

class GridWorld:
    def __init__(self):
        self.x = 0
        self.y = 0

    def step(self, a):
        if a == 0:
            self.move_left()
        elif a == 1:
            self.move_up()
        elif a == 2:
            self.move_right()
        elif a == 3:
            self.move_down()

        reward = -1
        done = self.is_done()
        return (self.x, self.y), reward, done

    def move_right(self):
        self.y = min(self.y + 1, 3)

    def move_left(self):
        self.y = max(self.y - 1, 0)

    def move_up(self):
        self.x = max(self.x - 1, 0)

    def move_down(self):
        self.x = min(self.x + 1, 3)

    def is_done(self):
        return self.x == 3 and self.y == 3

    def get_state(self):
        return (self.x, self.y)

    def reset(self):
        self.x, self.y = 0, 0
        return (self.x, self.y)


class Agent:
    def select_action(self):
        coin = random.random()
        if coin < 0.25:
            return 0
        elif coin < 0.5:
            return 1
        elif coin < 0.75:
            return 2
        else:
            return 3

2-2. Monte Carlo로 상태 가치 추정

def main():
    env = GridWorld()
    agent = Agent()
    data = [[0.0 for _ in range(4)] for _ in range(4)]
    gamma = 1.0
    alpha = 0.001

    for k in range(50000):
        done = False
        history = []

        # 에피소드 실행
        while not done:
            action = agent.select_action()
            (x, y), reward, done = env.step(action)
            history.append((x, y, reward))
        env.reset()

        # 뒤에서부터 Return 누적하며 Monte Carlo 업데이트
        cum_reward = 0
        for (x, y, reward) in history[::-1]:
            data[x][y] = data[x][y] + alpha * (cum_reward - data[x][y])
            cum_reward = reward + gamma * cum_reward

    for row in data:
        print(row)

if __name__ == '__main__':
    main()

• history 에 (상태, 보상) 궤적을 저장.
• 뒤에서부터 Return을 누적(cum_reward) 하며 각 상태 값을 조금씩 (α) 만큼 보정.

---

3. TD Learning: 한 스텝씩, 즉시 업데이트

3-1. TD Learning이란?

TD Learning(Temporal Difference Learning) 은 몬테카를로처럼 모델을 몰라도 되지만, 에피소드 끝까지 기다리지 않고 매 스텝마다 상태 가치를 업데이트하는 방법이다.

기본 아이디어:

“지금은 정답(진짜 V)을 모르니까, 일단 다음 상태의 현재 추정값 을 이용해 지금 상태를 조금 수정하자.”

업데이트 식 (TD(0)):

V(s) ← V(s) + α [ r + γ V(s') − V(s) ]

• r + γ V(s') 를 TD 타깃(TD target),
• r + γ V(s') − V(s) 를 TD 에러(TD error) 라고 부른다.

3-2. Monte Carlo vs TD Learning

• Monte Carlo
  • 에피소드가 끝난 뒤, 최종 Return 으로 학습.
  • 전체 결과를 보고 업데이트.
• TD Learning
  • 매 스텝마다, 다음 상태 가치 를 참고해 학습.
  • 에피소드가 끝나기 전에도 계속 업데이트 가능.

그래서 TD는 긴 에피소드 나 무한 에피소드 환경에서도 효율적으로 쓸 수 있고, Q-learning·SARSA 등 많은 알고리즘의 기반이 된다.

---

4. 4×4 GridWorld: TD로 상태 가치 추정

위 4×4 GridWorld를 TD(0)로 학습해 보자.

import random
import numpy as np

# GridWorld와 Agent 클래스는 Monte Carlo 예제와 동일

class GridWorld:
    def __init__(self):
        self.x = 0
        self.y = 0
    # ... (step, move_*, is_done, get_state, reset 동일 구현)

class Agent:
    def select_action(self):
        coin = random.random()
        if coin < 0.25:
            return 0
        elif coin < 0.5:
            return 1
        elif coin < 0.75:
            return 2
        else:
            return 3


def main():
    env = GridWorld()
    agent = Agent()
    data = [[0.0 for _ in range(4)] for _ in range(4)]
    gamma = 1.0
    alpha = 0.01

    for k in range(50000):
        done = False
        while not done:
            x, y = env.get_state()
            action = agent.select_action()
            (x_prime, y_prime), reward, done = env.step(action)
            # TD 업데이트
            data[x][y] = data[x][y] + alpha * (reward + gamma * data[x_prime][y_prime] - data[x][y])
        env.reset()

    for row in data:
        print(row)

if __name__ == '__main__':
    main()

• Monte Carlo와 달리, 에피소드 도중에도 매 스텝 상태 값을 업데이트한다.
• 목표 상태의 값은 간접적으로 전파되며, 점차적으로 “목표와 가까운 칸일수록 덜 손해본다” 는 패턴이 값에 반영된다.

---

5. 술취한 사람 문제에 TD 적용하기

5-1. 1D 술취한 사람을 TD로 학습

이전 벨만 방정식 글에서 보았듯, 1D 술취한 사람 문제에서는 (V(A)=0.5), (V(B)=0), (V(C)=-0.5) 가 정답이다. 이를 TD로 근사해 보자.

import random

states = ["Home", "A", "B", "C", "Bar"]
V = {state: 0.0 for state in states}
V["Home"] = 1.0
V["Bar"] = -1.0

alpha = 0.1
gamma = 1.0
episodes = 50000

inner_states = ['A', 'B', 'C']

for ep in range(episodes):
    state = random.choice(inner_states)
    while state not in ['Home', 'Bar']:
        move = random.choice(['left', 'right'])
        if state == 'A':
            next_state = 'Home' if move == 'left' else 'B'
        elif state == 'B':
            next_state = 'A' if move == 'left' else 'C'
        elif state == 'C':
            next_state = 'B' if move == 'left' else 'Bar'

        reward = 0
        # TD 업데이트: V(s) ← V(s) + α (r + γ V(s') - V(s))
        V[state] = V[state] + alpha * (reward + gamma * V[next_state] - V[state])
        state = next_state

for state, value in V.items():
    print(f'{state}: {value:.4f}')

충분히 많이 학습하면, A/B/C의 값이 0.5 / 0 / -0.5 근처로 수렴한다.

5-2. 5×5 술취한 사람 문제에 TD 적용

2D 격자 환경에서도 TD로 가치 함수를 학습할 수 있다.

import random

SIZE = 5
GAMMA = 1.0
ALPHA = 0.1
EPISODES = 1000

HOME = (0, 0)
BAR = (0, 4)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_terminal(state):
    return state == HOME or state == BAR


def move(state, direction):
    r, c = state
    dr, dc = direction
    nr, nc = r + dr, c + dc
    if nr < 0 or nr >= SIZE or nc < 0 or nc >= SIZE:
        return state
    return (nr, nc)


def get_reward(next_state):
    if next_state == HOME:
        return 1.0
    elif next_state == BAR:
        return -1.0
    else:
        return 0.0


def print_grid(values, title=""):
    if title:
        print(f"\n{title}")
    for r in range(SIZE):
        row = []
        for c in range(SIZE):
            state = (r, c)
            if state == HOME:
                row.append(" Home ")
            elif state == BAR:
                row.append(" Bar  ")
            else:
                row.append(f"{values[r][c]:6.2f}")
        print(" | ".join(row))


def td_learning():
    V = [[0.0 for _ in range(SIZE)] for _ in range(SIZE)]
    V[HOME[0]][HOME[1]] = 1.0
    V[BAR[0]][BAR[1]] = -1.0

    print_grid(V, title="초기 상태 가치")

    for episode in range(1, EPISODES + 1):
        # 무작위 비종결 상태에서 시작
        while True:
            state = (random.randint(0, SIZE-1), random.randint(0, SIZE-1))
            if not is_terminal(state):
                break

        while not is_terminal(state):
            action = random.choice(DIRECTIONS)
            next_state = move(state, action)
            reward = get_reward(next_state)

            r, c = state
            nr, nc = next_state

            td_target = reward + GAMMA * V[nr][nc]
            V[r][c] = V[r][c] + ALPHA * (td_target - V[r][c])

            state = next_state

        if episode in [1, 10, 100, 500, 1000]:
            print_grid(V, title=f"{episode} 에피소드 후 상태 가치")

    return V


if __name__ == "__main__":
    final_V = td_learning()
    print_grid(final_V, title="최종 TD 학습 결과")

여기서도 핵심은 한 줄:

V[r][c] = V[r][c] + ALPHA * (reward + GAMMA * V[nr][nc] - V[r][c])

즉,

V(s) ← V(s) + α [ r + γ V(s') − V(s) ]

---

6. 랜덤 벽 GridWorld: TD로 일반화된 환경 다루기

이제 한 단계 더 나아가, 랜덤하게 생성되는 벽 이 있는 4×4 GridWorld를 TD로 학습해 보자.

조건:

• 시작 위치: (0, 0)
• 목표 위치: (3, 3)
• 행동: 0=왼쪽, 1=위, 2=오른쪽, 3=아래
• 매 에피소드마다 벽을 2~3개 랜덤 생성
  • 시작·목표 위치에는 벽이 생성되면 안 됨.
  • 같은 위치에 벽 중복 생성 금지.
• 이동하려는 위치가
  • 빈 칸이면 이동.
  • 격자 밖이면 제자리.
  • 벽이면 제자리 유지.
• 보상: 일반 이동 -1, 목표 도착 시 에피소드 종료.

목표: 랜덤 벽 환경에서 TD Learning으로 상태 가치 V(s)를 학습 하고,
일반 GridWorld와 비교해 상태 가치가 어떻게 달라지는지 보는 것.

import random
import numpy as np

class GridWorld:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.walls = []

    def step(self, a):
        old_x, old_y = self.x, self.y
        if a == 0:
            self.move_left()
        elif a == 1:
            self.move_up()
        elif a == 2:
            self.move_right()
        elif a == 3:
            self.move_down()

        # 벽이면 이동 취소
        if (self.x, self.y) in self.walls:
            self.x, self.y = old_x, old_y

        reward = -1
        done = self.is_done()
        return (self.x, self.y), reward, done

    def move_right(self):
        self.y = min(self.y + 1, 3)
    def move_left(self):
        self.y = max(self.y - 1, 0)
    def move_up(self):
        self.x = max(self.x - 1, 0)
    def move_down(self):
        self.x = min(self.x + 1, 3)

    def is_done(self):
        return self.x == 3 and self.y == 3

    def reset(self):
        self.x, self.y = 0, 0
        # 벽 재생성
        self.walls = []
        num_walls = random.choice([2, 3])
        candidates = [
            (i, j) for i in range(4) for j in range(4)
            if (i, j) != (0, 0) and (i, j) != (3, 3)
        ]
        self.walls = random.sample(candidates, num_walls)
        return (self.x, self.y)


class Agent:
    def select_action(self):
        return random.randint(0, 3)


def main():
    env = GridWorld()
    agent = Agent()
    data = [[0.0 for _ in range(4)] for _ in range(4)]
    gamma = 1.0
    alpha = 0.01

    for k in range(50000):
        if k % 5000 == 0:
            print(f"Episode {k} 학습 중... (진행률: {k/50000*100:.0f}%)")

        state = env.reset()
        done = False
        steps = 0

        while not done:
            x, y = state
            action = agent.select_action()
            (nx, ny), reward, done = env.step(action)

            data[x][y] = data[x][y] + alpha * (reward + gamma * data[nx][ny] - data[x][y])
            state = (nx, ny)

            steps += 1
            if steps > 200:  # 무한 루프 방지
                break

    print("\n학습 완료! 최종 상태 가치:")
    for row in data:
        print([round(float(val), 2) for val in row])

if __name__ == '__main__':
    main()

• 일반 GridWorld에 비해, 벽 주변 칸의 가치가 더 나빠지거나(우회 필요),
• 벽 배치에 따라 경로가 꼬여 더 큰 손해를 보는 구간 이 생긴다.

이 차이를 비교해 보면, TD Learning이 환경 구조(벽 위치 등) 를 어떻게 가치 함수에 자연스럽게 반영하는지 알 수 있다.

---

7. 정리

방법	업데이트 시점	필요 정보	장단점
Monte Carlo	에피소드 종료 후	모델 불필요 (모델 프리)	구현 단순·직관적, 긴 에피소드에서 느림
TD(0)	매 스텝 즉시	모델 불필요 (모델 프리)	빠른 학습, 벨만 방정식과 직접 연결, 편향/분산 트레이드오프

• Monte Carlo와 TD Learning은 둘 다 환경 모델을 모르는 상황에서 가치 함수를 학습 하는 방법이지만,
  • Monte Carlo는 완전한 Return 을 쓰고,
  • TD는 다음 상태의 현재 추정값 을 쓴다는 점에서 차이가 있다.
• GridWorld·술취한 사람 예제를 통해, 두 방법이 같은 정답 가치 함수로 수렴하면서도 학습 경로와 특성이 다름 을 확인할 수 있다.
• 이후 Q-learning, SARSA, Deep RL로 나아가면, 여기서 본 TD 업데이트 식이 그대로 확장되어 사용된다.