[강화학습] 몬테카를로 학습

요즘 회사에서 강화학습 쪽으로 업무를 진행할 것 같아서, 대학원 때 이후로 덮어두었던 강화학습을 조금씩 다시 복습하며 공부하고 있습니다. 이번 포스팅에서는 환경의 정보가 없는 모델 프리(model free) 상황에서 자주 쓰이는 몬테카를로 학습에 대해 정리하겠습니다. 강화학습에 대한 첫 포스팅인만큼 policy, value, reward 등 생소한 이야기가 나올 수 있는데, 이는 추후에 따로 정리하겠습니다.

 

몬테카를로

몬테카를로 학습이란?

몬테카를로 방법은 확률론적 시뮬레이션을 기반으로 한 방법으로, 에이전트가 환경과 상호작용하며 얻은 경험(에피소드)을 분석하여 정책(policy)이나 가치 함수(value function)를 평가하고 개선하는 방법입니다. 에피소드가 모두 끝난 이후에 에피소드로부터 얻은 반환값(return)들을 바탕으로 미래에 얻는 보상을 추정합니다. 몬테카를로는 대표적으로 4가지 특징이 있습니다.

1. 에피소드 단위의 학습: 학습은 완료된 에피소드를 기반으로 이루어집니다. 즉, 에피소드가 완료될 때까지 기다린 후에야 학습이 이루어집니다.
2. 모델 불필요: 몬테카를로 학습은 환경의 모델이 주어지지 않아도 적용할 수 있습니다. 실제 경험을 통해 학습하기 때문입니다.
3. 높은 분산: 몬테카를로 방법은 분산이 높을 수 있습니다. 이는 반환값이 에피소드마다 크게 달라질 수 있기 때문입니다. 따라서, 많은 에피소드를 통해 평균을 내야 정확한 추정이 가능합니다.
4. 탐험 필요: 좋은 정책을 학습하기 위해서는 충분한 탐험이 필요합니다. 즉, 다양한 상태와 행동을 경험해 보아야 합니다.

몬테카를로 학습은 간단하면서도 강력한 방법이지만, 모든 상황에 최적인 것은 아닙니다. 에피소드가 매우 길거나 끝이 정의되지 않은 환경에서는 에피소드 중간중간에 값을 업데이트하는 방법인 TD(Temporal Difference) 학습이나 다른 방법이 더 효과적일 수 있습니다.

사전에 에피소드들의 기대값은 다음과 같이 표기할 수 있습니다.

$$v_{\pi}(s_t) = \mathbb{E}_{\pi}[G_t]$$

여기서 $\pi$는 에이전트가 취하는 정책, $G_t$는 각 시점 t에 대한 상태들값들을 의미합니다.  

 

좀 더 구체적인 상황을 정의하며 설명하겠습니다. 

 

4x4그리드 월드를 여행한다고 가정하고 에이전트는 확률적으로 아무곳이나 움직이는 특징을 가지고 있습니다. 0,0이 출발점이고 4,4가 도착점이라 가정하겠습니다.

 

시작	s1	s2	s3
s4	s5	s6	s7
s8	s9	s10	s11
s12	s13	s14	종료

 

초기엔 모든 값을 0으로 초기화시키고, 시작점에서 종료지점에 빠르게 도달해야하는 것을 목표하는 상황을 두겠습니다. 

0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0

그런 상황에서 각 그리드 월드의 가치를 다수의 에피소드들의 기대값으로 다음과 같이 근사할 수 있습니다.

$$v_{\pi}(s_t) \cong \frac{V(s_t)}{N(s_t)}$$

 

이를 좀더 확장하여 

$$V(s_t) = (1-\alpha)*V(s_t) +\alpha*G_t$$

로 식을 변형할 수가 있는데 우리는 $\alpha$라는 추가적은 변수를 새로 설정하여 각 에피소드들의 값을 활용하여 테이블 값을 업데이트 할수 있습니다.

$G_t$에 대한 설명을 드리자면 에피소드 t가 가지는 리턴값을 의미합니다. 예를들면

$$G_0 = r_0 + \gamma r_1 + \gamma^2 r_2 + \gamma^3 r_3 + ... + \gamma^T r_{T-1}$$

의 표기는 0번째 에피소드의 리턴값을 의미합니다.

또한,  $\gamma$는 미래 보상의 현재 가치에 대한 가중치를 결정하는 매개변수로, 일반적으로 0과 1 사이의 값을 가집니다.

다시 상기식을 다시 정리하면

$$V(s_t) = V(s_t) +\alpha(G_t- V(s_t) )$$

로 표시할 수있습니다. 이는 $G_t$가 $V(s_t)$보다 크면 두번째항이 양수항이 되어 $V(s_t)$를 더 크게함으로 기존 방법론에 대한 확신을 더 싫어주는 것이고 반대의 경우 기존 방법론에 대한 신뢰성을 줄임으로써 더 큰 가능성으로 탐색하는 기법이라고 이해하시면 되겠습니다. 또한 새로운 변수인  $\alpha$가 추가되었는데 이는 업데이트 시 새 로운 정보가 기존의 가치 추정치에 얼마나 영향을 미칠지를 결정합니다.

 

그렇다면 이때까지 설명한 내용들을 코드로 표현하겠습니다. 라이브러리 import 및 그리드 환경그리고 에이전트를 정의하겠습니다.

import random
import numpy as np

class NbyNGridWorld():
    def __init__(self,N):
        self.x=0
        self.y=0
        self.N=N
    def step(self,a):
        if a==0:
            self.move_right()
        elif a==1:
            self.move_left()
        elif a==2:
            self.move_up()
        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>self.N-1:
            self.y = self.N-1
    def move_left(self):
        self.y-=1
        if self.y<0:
            self.y = 0
    def move_down(self):
        self.x+=1
        if self.x>self.N-1:
            self.x = self.N-1
    def move_up(self):
        self.x-=1
        if self.x<0:
            self.x = 0
    def is_done(self):
        if self.x==self.N-1 and self.y== self.N-1:
            return True
        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 self_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

이후 몬테 카를로 방법론으로 업데이트하는 실행함수를 정의하겠습니다. 해당 함수의 trainsition파트가 몬테카를로 방법론을 적용시켜 그리드 월드를 업데이트 하는 방식입니다. 또한 해당 for문의 마지막에 gamma를 곱하여 감가개념을 적용시켰습니다.  gamma가 1에 가까우면 미래의 보상을 현재 보상만큼 중요하게 여기는 것이고, gamma가 0에 가까우면 즉각적인 보상만을 중요시하는 것인데, 단순화 하기위해 저는 1을 곱했습니다.

def main(N,gamma=1,alpha=0.0001,itern =10000):
    env = NbyNGridWorld(N)
    agent= Agent()
    data = np.zeros((N,N))
    for k in range(itern):
        done = False
        history = []
        while not done:
            action = agent.self_action()
            (cx,cy),reward,done = env.step(action)
            history.append((cx,cy,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 = cum_reward+gamma*reward
    for row in data:
        print(row)
main(4,itern=10000)

 

다음과 같이 실행결과를 확인할 수 있습니다.

실행결과