Monte Carlo Learning

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

MDP를 안다는 것은 다음 정보를 알고 있다는 뜻입니다.

• 상태 S
• 행동 A
• 상태 전이 확률 P(s′∣s,a)
• 보상 R(s,a,s′)

즉 환경이 어떻게 움직이는지 완전히 알고 있는 상황입니다. 이 경우에는 수식으로 직접 Value를 계산할 수 있습니다.

 

 

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

현실에서는 대부분 환경의 확률을 모릅니다.

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

P(s'|s,a) 를 알 수 없습니다. 그래서 실제로 행동하면서 얻은 경험으로 Value를 추정합니다.

 

 

 

3. Monte Carlo Learning

Monte Carlo Learning은 환경의 상태 전이 확률이나 보상 함수를 모르는 상황에서 실제로 에이전트가 여러 번 에피소드를 실행해 보고, 그 과정에서 얻은 총 보상(Return)의 평균을 이용하여 상태 가치(Value)를 추정하는 강화학습 방법입니다. 이 방법은 특정 상태에서 시작해 에피소드가 끝날 때까지 얻은 누적 보상을 계산하고, 동일한 상태에서 여러 번 실행한 결과들의 평균을 통해 그 상태의 가치를 점점 더 정확하게 추정합니다. 따라서 Monte Carlo Learning은 환경 모델을 알 필요가 없는 모델 프리(Model-Free) 방식이며, 실제 경험 데이터를 기반으로 학습한다는 특징이 있지만, 에피소드가 종료되어야 값을 업데이트할 수 있기 때문에 긴 문제에서는 학습이 느려질 수 있습니다.

 

1. 몬테카를로 방법론

몬테카를로 방법론(Monte Carlo Method)은 확률적 샘플링(무작위 실험)을 반복하여 어떤 값의 근사해나 평균적인 결과를 계산하는 방법입니다. 즉, 어떤 문제를 수학적으로 정확하게 계산하기 어렵거나 복잡할 때, 실제로 많은 무작위 실험을 수행하고 그 결과의 평균을 이용해 답을 추정하는 방식입니다. 이름은 카지노 도시인 Monte Carlo에서 유래했는데, 이는 주사위나 룰렛처럼 확률과 무작위성(randomness)을 활용하는 방식이기 때문입니다.

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

많은 랜덤 실험 → 평균값 → 실제 값에 가까워짐

 

2. 강화학습에서 사용하는 이유

강화학습에서는 보통 다음 정보를 모릅니다.

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

그래서 수식으로 계산할 수 없습니다.

 

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

장점

• 모델이 필요 없음
• 구현이 단순
• 직관적

단점

• 에피소드 종료 필요
• 학습이 느림

 

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

Monte Carlo Learning에서 에피소드 종료가 필요한 이유는 상태의 가치를 계산할 때 그 상태 이후에 얻는 전체 누적 보상(Return)을 사용하기 때문입니다. Monte Carlo 방법은 어떤 상태에서 시작했을 때 앞으로 받을 보상을 모두 합한 값을 계산한 뒤 그 값을 평균내어 상태 가치를 추정하는 방식이므로, 에피소드가 끝나야 그 상태의 최종 Return을 정확히 알 수 있습니다. 예를 들어 게임에서 어떤 상태에서 시작했을 때 결국 승리(+1)로 끝나는지, 패배(-1)로 끝나는지, 또는 여러 보상을 거쳐 얼마의 총 보상을 얻는지 알아야 상태의 가치를 계산할 수 있는데, 이 값은 게임이 끝나기 전까지는 확정되지 않습니다. 따라서 Monte Carlo 방식은 에피소드 전체를 실행하여 최종 결과를 확인한 뒤 그때 얻은 Return을 사용해 상태 가치를 업데이트하기 때문에, 학습을 위해 반드시 에피소드 종료가 필요합니다.

 

import random
import numpy as np

class GridWorld():
    def __init__(self):
        self.x=0
        self.y=0
    
    def step(self, a):
        # 0번 액션: 왼쪽, 1번 액션: 위, 2번 액션: 오른쪽, 3번 액션: 아래쪽
        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 # 보상은 항상 -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()
    data = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    gamma = 1.0
    reward = -1
    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()

        cum_reward = 0
        for transition in history[::-1]:
            x, y, reward = transition
            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()