[강화학습] Monte Carlo Learning 정리

1. MDP를 아는 경우의 Value 평가

MDP(Markov Decision Process)를 안다는 것은 환경에 대한 다음의 주요 정보들을 모두 알고 있다는 뜻입니다.

• 상태 (State): S
• 행동 (Action): A
• 상태 전이 확률 (State Transition Probability): P(s′∣s,a)
• 보상 (Reward): R(s,a,s′)

💡 즉, 환경이 어떻게 움직이는지 완전히 알고 있는 상황입니다. 이 경우에는 벨만 방정식과 같은 수식을 통해 직접 상태 가치(Value)를 계산할 수 있습니다.

2. MDP를 모르는 경우의 Value 평가

하지만 현실의 문제에서는 대부분 환경의 확률 모델을 완벽하게 알 수 없습니다.

• 게임
• 로봇 제어
• 자율주행
• 주식 시장

위와 같은 현실 문제에서는 특정 행동을 했을 때 다음 상태가 될 확률인 $P(s' \mid s,a)$를 알 수 없습니다. 그래서 수식으로 계산하는 대신, 실제로 행동하면서 얻은 '경험'을 바탕으로 Value를 추정하게 됩니다.

---

3. Monte Carlo Learning (몬테카를로 학습)

Monte Carlo Learning은 환경의 상태 전이 확률이나 보상 함수를 모르는 상황에서, 실제로 에이전트가 여러 번 에피소드를 실행해 보고 그 과정에서 얻은 총 보상(Return)의 평균을 이용하여 상태 가치(Value)를 추정하는 강화학습 방법입니다.

이 방법은 특정 상태에서 시작해 에피소드가 끝날 때까지 얻은 누적 보상을 계산하고, 동일한 상태에서 여러 번 실행한 결과들의 평균을 통해 그 상태의 가치를 점점 더 정확하게 추정해 나갑니다.

 

따라서 환경 모델을 알 필요가 없는 모델 프리(Model-Free) 방식이며, 실제 경험 데이터를 기반으로 학습한다는 강력한 특징이 있습니다. 하지만 에피소드가 반드시 종료되어야만 값을 업데이트할 수 있기 때문에, 호흡이 긴 문제에서는 학습이 느려질 수 있다는 단점도 존재합니다.

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

몬테카를로 방법론(Monte Carlo Method)은 확률적 샘플링(무작위 실험)을 반복하여 어떤 값의 근사해나 평균적인 결과를 계산하는 방법입니다. 즉, 어떤 문제를 수학적으로 정확하게 계산하기 어렵거나 복잡할 때, 실제로 많은 무작위 실험을 수행하고 그 결과의 평균을 이용해 답을 추정하는 방식입니다.

이름은 카지노 도시인 모나코의 'Monte Carlo'에서 유래했는데, 주사위나 룰렛처럼 확률과 무작위성(randomness)을 활용하는 방식이기 때문입니다.

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

핵심 원리: 많은 랜덤 실험 → 평균값 도출 → 실제 값에 근접함

2) 강화학습에서 몬테카를로를 사용하는 이유

강화학습에서는 보통 다음 두 가지 핵심 정보를 모릅니다.

• 상태 전이 확률: P(s′∣s,a)
• 보상 함수: R(s,a)

환경의 모델을 모르기 때문에 수식으로 Value를 계산할 수 없어, 직접 부딪혀보고 얻은 결과(경험)의 평균을 내는 몬테카를로 방식을 사용합니다.

3) 몬테카를로 방법의 특징

• 장점
  • 환경 모델(Model)이 필요 없음
  • 구현이 비교적 단순함
  • 개념이 직관적임
• 단점
  • 에피소드가 반드시 종료되어야 함
  • 학습 속도가 느림

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

Monte Carlo Learning에서 에피소드 종료가 꼭 필요한 이유는, 상태의 가치를 계산할 때 그 상태 이후에 얻는 전체 누적 보상(Return)을 사용하기 때문입니다.

Monte Carlo 방법은 어떤 상태에서 시작했을 때 앞으로 받을 보상을 모두 합한 값을 계산한 뒤 그 값을 평균내어 상태 가치를 추정하는 방식이므로, 에피소드가 끝나야 그 상태의 최종 Return을 정확히 알 수 있습니다.

예를 들어 게임에서 어떤 상태에서 시작했을 때 결국 승리(+1)로 끝나는지, 패배(-1)로 끝나는지, 또는 여러 보상을 거쳐 얼마의 총 보상을 얻는지 알아야 상태의 가치를 계산할 수 있는데, 이 값은 게임이 끝나기 전까지는 확정되지 않습니다.

 

따라서 Monte Carlo 방식은 에피소드 전체를 실행하여 최종 결과를 확인한 뒤 그때 얻은 Return을 사용해 상태 가치를 업데이트하기 때문에, 학습을 위해 반드시 에피소드 종료가 필요합니다.

---

4. 실습: 4x4 GridWorld에서 Monte Carlo 상태 가치 추정

"이 칸에 오면 앞으로 목표까지 얼마나 손해를 보게 되는가?"

• 환경: 4x4 공간의 GridWorld. (0, 0)에서 시작해서 목표 지점인 (3, 3)에 도착하면 에피소드가 끝납니다.
• 에이전트: 매번 랜덤하게 상/하/좌/우 중 하나를 선택하여 이동합니다.
• 보상: 한 번 움직일 때마다 보상 -1을 받습니다. (최대한 적은 횟수로 목표에 도달해야 총 보상이 높아짐)
• 목표: 많은 에피소드를 무작위로 실행한 뒤, 각 칸에서 목표까지 가는 데 평균적으로 얼마나 손해(Return)를 보는지 데이터에 저장합니다.

구현 구성요소

1. 환경 (GridWorld 클래스): 격자판 생성, 위치 이동 처리, 에피소드 종료 여부 판단
2. 에이전트 (Agent 클래스): 행동을 선택 (여기서는 상하좌우 25% 확률로 완전 랜덤 선택)
3. 학습 (main 함수): 에피소드를 수만 번 반복하면서 각 상태의 가치를 점진적으로 업데이트

(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)  ← 목표 지점

Python 구현 코드

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 += 1
        if self.y > 3:
            self.y = 3

    def move_left(self):
        self.y -= 1
        if self.y < 0:
            self.y = 0

    def move_up(self):
        self.x -= 1
        if self.x < 0:
            self.x = 0

    def move_down(self):
        self.x += 1
        if self.x > 3:
            self.x = 3

    def is_done(self):
        if self.x == 3 and self.y == 3:
            return True
        else:
            return False

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

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

class Agent():
    def __init__(self):
        pass

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

def main():
    env = GridWorld()
    agent = Agent()
    # 4x4 상태 가치를 저장할 배열 (모두 0으로 초기화)
    data = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    gamma = 1.0     # 할인율
    alpha = 0.001   # 학습률 (업데이트 속도)

    for k in range(50000): # 5만 번의 에피소드 반복
        done = False
        history = []

        # 1. 에피소드 생성 (목표 도달 시까지 반복)
        while not done:
            action = agent.select_action()
            (x, y), reward, done = env.step(action)
            history.append((x, y, reward))
            
        env.reset()
        cum_reward = 0
        
        # 2. 에피소드 종료 후, 역순으로 Return 계산 및 상태 가치 업데이트
        for transition in history[::-1]:
            x, y, reward = transition
            # 상태 가치 업데이트: V(S) = V(S) + alpha * (Return - V(S))
            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()