Processing math: 100%
본문 바로가기
바닥부터 배우는 강화 학습

[ 바닥부터 배우는 강화 학습 ] 05. MDP를 모를 때 밸류 평가하기

by sxlvxrjxms2s2itsmes2s2 2024. 1. 2.

이번 챕터부터는 MDP의 전이 확률과 보상 함수를 모를 때에 대한 이야기이다.

주어진 수식을 이용해 정확한 값을 계산하는 대신, 수많은 샘플을 통해 근사하는 샘플 기반 방법론이 도입될 차례이다.

 

MDP를 모른다는 것은 보상 함수 ras와 전이 확률Pass을 모른다는 뜻이다.

즉, 실제로 액션을 해 보기 전까지는 보상을 얼마를 받을지도 모르고, 어떤 상태로 이동하게 될 지 확률 분포도 모르는 상황이다. 이를 모델 프리 라고 부른다.

 

모델 = 강화 학습에서 환경의 모델의 줄임말로, 에이전트의 액션에 대해 환경이 어떻게 응답할지 예측하기 위해 사용하는 모든것을 가리킨다.

에이전트의 액션에 대하여 환경이 어떻게 반응할지 알 수 있다면 에이전트의 입장에선 여러 가지 계획을 세워볼 수 있다.

그렇기에 에이전트 입장에서는 모델을 아는 것이 좋다.

 

이번 챕터에서는 모델 프리 상황에서의 prediction, 즉 π가 주어졌을 때 가치를 평가하는 2가지 방법에 대해 배울 것이다.

 

5.1 몬테카를로 학습

앞면이 나올 확률을 모르는 동전은 MDP에 대한 정보를 모를 때 각 상태의 가치를 평가하는 문제와 매우 유사하다.

그리고 우리는 확률을 모름에도 기댓값을 알 수 있다. 그 방법은 동전을 여러번 던져보는 것이다.

정확한 확률은 모르지만 10번 던져서 앞면이 3번 나왔다면 우리는 그 확률을 대충 30%라고 가늠해 볼 수 있다.

 

0.3*100 + 0.7*0 = 30 으로 즉 30원이 된다.

 

기댓값까지 계산할 것도 없이 얻은 금액에 대해 평균을 내면 된다.

여러 번 던질수록 그 값은 점점 정확해질 것이다. 이것이 몬테카를로 방법론의 중심 철학이다.

 

MDP에서도 똑같은 방법으로 각 상태의 가치를 평가할 것이다.

그러면 어떤 값으로 가치를 평가할까? 가치 함수의 정의를 떠올려보자.

가치 함수의 정의는 리턴의 기댓값이다. vπ(st)=E(Gt)

 

따라서 동전을 여러번 던졌던 것처럼 리턴을 여러 번 계산해 그 평균을 내면 그 값은 해당 상태의 실제 가치에 수렴할 것이다.

 

일단 환경에다가 에이전트를 가져다 놓고 경험을 하도록 시킨다. 에피소드가 언젠가 끝날 것이고 끝날 때까지 얻었던 리턴들을 기록해 놓았다가 평균을 구한다. 이렇게 에피소드마다 각 상태의 리턴을 기록해 놓았다가 그 값들의 평균을 내면 끝다.

이런 방법을 사용한다면 경험을 더 많이 쌓아 더 많은 에피소드를 진행할수록 각 상태의 밸류 예측치는 점점 정확해진다.

 

몬테카를로 학습 알고리즘

 

이제는 보상 함수와 전이 확률을 모른다. (우리가 그 값을 모르는 것일 뿐 실제 MDP에는 고정된 보상 함수와 전이 확률이 있다.)

 

s2에서 sright액션을 선택한다고 하자. 실제로 해보지 않아도 다음 상태가 s3가 될 것임을 알고 있었다.

 

그래서 챕터 4에서는 실제로 액션을 해보는 것이 아니라 각 상태에서 에이전트가 할 수 있는 모든 액션에 대해 각 액션을 선택할 확률 π(a|s)에다가, 액션 선택으로 인해 도달하게 되는 상태 s'의 가치 v(s')을 곱하는 식으로 기존 상태의 가치를 계산했다.

 

잘 생각해보면 실제로 에이전트가 액션을 취하거나 했던 적이 없었다. 행동에 따른 결과들을 예측할 수 있기 때문에 모든 학습 과정이 머릿속에서 일어난 셈이다. 그래서 챕터 4의 방법론을 플래닝이라고 부른다. 계획만 세운 것이다.

 

미래의 모든 정보를 알기에 계획을 세워보는 것만으로도 실제 가치를 모두 평가할 수가 있었다.

 

이제는 s2에서 sright액션을 선택했을 때 어디에 도달하게 되는지 사전에 알 수 없다. 그래서 경험을 기반으로 배워야한다. 에이전트를 환경에 가져다놓고 경험을 쌓게 한다. 그러면 에이전트가 4방향 랜덤 정책을 통해 돌아다니며 보상과 상태 전이에 대한 경험을 쌓을 것이다.

 

1. 테이블 초기화

 

각 상태별로 N(s)와 V(s) 2개의 값이 필요하다.

N(s) : s를 총 몇번 방문했는지 세기 위해 필요한 값. s를 한 번 방문할 때마다 1을 더해준다.

V(s) : 해당 상태에서 경험했던 리턴의 총합을 기록하기 위함

 

2. 경험 쌓기

이제 정책 π를 이용해 움직이는 에이전트의 경험을 쌓자.

정책은 우리가 평가하고 싶은 그 어떤 정책이 주어져도 괜찮다.

s0부터 시작해 액션 a0을 정하고 맞는 보t상r0을 받고 s1에 도착한다.

 

그러면 각 상태에 대해 리턴을 계산할 수 있다.

G0=r0+γr1+γ2r2+γ3r3+...+γT1rT1G1=r1+γr2+γ2r3+...+γT2rT1...GT1=rT1GT=0

 

여기서 γ와 보상은 모두 관측된 값으로 변수가 아니다. 즉 리턴 또한 숫자값이다.

 

 

3. 테이블 업데이트

 

 

다음과 같은 에피소드를 실행했다고 가정하자.

s0s4s5s6s10s14sT  

 

방문했던 모든 상태에 대해 N(s)와 V(s) 값을 업데이트 한다.

N(st)N(st)+1

V(st)V(st)+Gt

 

 

4. 밸류 계산

많은 횟수의 에피소드를 경험 후 충분히 경험이 쌓이면 리턴의 평균(리턴의 합을 방문 횟수로 나눈 것)을 밸류 근사치로 사용한다.

vπ(st)V(st)N(st)

 

이와 같이 많은 에피소드를 통해 밸류를 추정하는 방식이 몬테카를로 방법론이다.

 

조금씩 업데이트하는 버전

 

본질적으로는 같지만 계산하는 방식이 조금 다른 버전이다.

 

앞의 버전은 100개면 100개의 에피소드가 모두 끝난 후에 평균을 냈다.

이번에는 에피소드가 1개 끝날 때마다 테이블의 값을 조금씩 업데이트 한다.

 

α : 얼만큼 업데이트 할지 크기를 결정해주는 파라미터, 클수록 더 크게 업데이트

 

이러한 방식은 방문 횟수 N(st에 값을 따로 저장해 둘 필요 없이 에피소드가 하나 끝날 때마다 테이블의 값을 업데이트할 수 있다.

 

아래와 같이 표현 가능하다.

V(st)V(st)+α(GtV(st)) 

GtV(st)보다 크면 α에 곱해진 값이 양수가 되어서 기존의 V(st) 값을 더 크게 만들라는 뜻이고 반대의 경우 V(st)를 더 작게 만들라는 수식이다.

 

 

몬테카를로 학습 구현

 

목표는 그리드 월드에서 4방향 랜덤 정책의 상태별 가치를 구하는 것. 이를 위해 4가지 요소가 구현되어야 한다.

환경 : 에이전트의 액션을 받아 상태변이를 일으키고, 보상을 줌

에이전트 : 4방향 랜덤 정책을 이용해 움직임

경험 쌓는 부분 : 에이전트가 환경과 상호작용하며 데이터를 축적

학습하는 부분 : 쌓인 경험을 통해 테이블을 업데이트

 

# 라이브러리 
import random

# Grid World 클래스

class GridWorld():
    def __init__(self):
        self.x=0
        self.y=0
    
    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 > 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.y += 1
        if self.x > 3:
            self.x = 3
    
    def is_done(self):
        '''
        에피소드가 끝났는지 판별해주는 함수
        종료 상태인 (3,3)에 도달했으면 T, 아니면 F
        '''
        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)
        
'''
Agent 클래스
4방향 uniform 랜덤 액션을 선택하는 일이 전부
'''
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 # 감쇄 인자
    alpha = 0.0001 # 업데이트에 사용되는 파라미터
    
    for k in range(1): # 총 n번의 에피소드 진행
        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 = cum_reward + gamma+reward # 리턴을 가리킨다
    
    '''
    학습이 끝나고 난 후 데이터를 출력해보기 위한 코드
    '''
    for row in data:
        print(row)

 

 

5.2 Temporal Difference 학습

몬테카를로의 한 가지 단점은 업데이트를 하려면 반드시 에피소드가 끝난 후에 리턴을 계산해야 한다는 점이다. == 적용할 수 있는 환경이 제한적이다.

 

에피소드가 끝나기 전에 업데이트 할 수 없을까?

== Temporal Difference 학습 방법론 (시간적 차이)

--> 종료하지 않은 MDP에서 학습 가능한 방법, 추측을 추측으로 업데이트 하는 방법이다. (미래의 추측으로 과거의 추측을 업데이트)

 

 

이론적 배경

앞서 몬테카를로는 리턴 여러 개를 모아 평균을 냈다. 이에 대한 이론적 근거는 

vπ(st)=Eπ[Gt] 라는 식 덕분이고

가치 함수 정의가 리턴 Gt의 기댓값이기 때문에 이를 많이 모을수록 그 평균은 vπ(st) 에 수렴하게 된다.

== Gt vπ(st) 의 불편 추정량

 

그렇다면 Temporal Differencd는 어떨까?

벨만 기대 방정식 0단계 수식을 떠올려보자.

 

vπ(st)=Eπ[rt+1+γvπ(st+1)]

 

rt+1+γvπ(st+1)을 여러 번 뽑아서 평균을 내면 그 평균이 vπ(st)에 수렴한다. 즉 기댓값이 곧 vπ(st)가 된다는 의미이다.

 

그래서 우리의 정답지가 되는 값은 rt+1+γvπ(st+1)이고 몬테카를로에서 리턴을 여러개 모았던 것처럼 rt+1+γvπ(st+1)의 값을 여러 개 모으면 된다.

 

이제 구체적인 학습 방식을 살펴보자.

 

 

Temporal Difference 학습 알고리즘

여기서도 마찬가지로 테이블의 값을 초기화하는 것부터 시작한다. 그 다음 에이전트를 s0에 놔두고 경험을 쌓게 한다.

TD 알고리즘이 MC와 다른 점은 2가지 = 업데이트 수식, 업데이트 시점

 

s0s1s2s3s7s6s10s11sT 라는 에피소드를 가정해보자

- 단계마다 -1의 보상을 받는다.

- 총 8번의 상태 전이 = 종료 상태를 제외한 8개의 상태에 대해 값 업데이트 가능

- 여기서 차이점은 종료 상태에 도달하기 전에, 각각의 상태 전이가 일어나자마자 바로 테이블의 값을 업데이트해줄 수 있다는 것이다.

 

MC : V(st)V(st)+α(GtV(st))

TD : V(st)V(st)+α(rt+1+γV(st+1)V(st))

 

이 업데이트 식을 이용해 다음과 같이 8번 업데이트 한다.

(보상 = -1, α = 0.01, γ = 1.0)

 

 

V(s0)V(s0)+0.01(1+V(s1)V(s0))V(s1)V(s1)+0.01(1+V(s2)V(s1))...V(s11)V(s11)+0.01(1+V(s15)V(s11))

 

 

이렇게 8칸을 업데이트하고 나면 하나의 에피소드에 대한 업데이트를 마친 것이다. 이를 반복해 테이블의 값이 수렴할 때까지 진행한다.

 

 

Temporal Difference 학습 구현

 

# Temporal Difference 학습 구현
# 메인 함수

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 # 감쇄 인자
    alpha = 0.01 # MC에 비해 큰 값을 사용
    
    for k in range(1): # 총 n번의 에피소드 진행
        done = False
        '''
        랜덤 에이전트가 경험을 쌓는 과정
        '''
        while not done: 
            x, y = env.get_state()
            action = agent.select_action()
            (x_prime,y_prime), reward, done = env.step(action)
            x_prime, y_prime = env.get_state()
            
            '''
            한 번의 step이 진행되자 말자 바로 테이블의 데이터를 업데이트 해줌
            '''
            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)

 

 

 

한 번의 액션마다 데이터 테이블이 업데이트된다. 또한 MC보다 업데이트 폭을 의미하는 alpha의 값이 매우 커졌다. 

TD가 MC에 비해 학습의 변동성이 작은 덕분에 그만큼 큰 폭의 업데이트가 가능해서 설정된 값이다.

 

 

5.3 몬테카를로 vs TD

뭐가 더 좋은 지는 문제와 상황에 따라 다르다. 

 

학습 시점 --> TD 우세

MC는 에피소드가 끝나고 리턴이 정해져야 되돌아보며 학습을 진행할 수 있다. 반면 TD는 한 스텝이 끝날 때마다 바로 테이블의 값들을 없는 문제와 상황에 따라 다르다. 

이러한 차이는 우리에게 큰 자유를 준다. MDP는 크게 2가지 종류의 MDP가 있기 때문이다.

 

- Episodic MDP

MDP의 상태들 중에 종료 상태라는 것이 있어 에이전트의 경험이 에피소드 단위로 나뉘어질 수 있는 것

 

- Nom- Episodic MDP

종료 상태 없이 하나의 에피소드가 무한히 이어지는 MDP

바둑, 스타크래프트 등 종료 조건이 명확한 경우에는 episodic MDP 형태로 만들 수 있다.

그러나 주식 시장에서의 포트폴리오 분배처럼 명확한 종료 조건이 없거나 하나의 에피소드가 너무 길어지는 경우가 있다.

 

MC는 episodic MDP에만 적용할 수 있다.

TD는 어떤 MDP에서든 적용할 수 있다. 이런 측면에서는 TD가 장점을 가진다고 할 수 있다.

 

편향성 --> MC 우세

MC와 TD의 근간이 되는 식을 살펴보자.

 

MC : vπ(st)=Eπ[Gt] 

TD : vπ(st)=Eπ[rt+1+γvπ(st+1)]

 

TD는 v를 사용하기 때문에 실제와 다르다. vπ와 다르다. 그러므로 실제 v로 수렴할 보장이 없다는 것.

MC가 승.

 

분산--> TD 우세

 

MC는 에피소드가 끝나야 하기 때문에 리턴이 -6 또는 -2000 등 다양한 값을 가질 수 있다. 분산이 크다.

G값들은 경로가 다양하기에 그 사이끼리 갭이 클 수 있다.

 

TD는 한 샘플만 보고 업데이트하기 때문에 분산이 작다.

분산 측면에서는 TD가 승.