강화학습 - Model Free(1)

이제 MDP를 모르는 상황에서의 value를 평가하는 방법을 배워볼 차례입니다. 보상함수$r^{a}_{s}$와 전이 확률 $P^{a}_{ss'}$을 모르는 상황을 model-free라고 부릅니다.

간단하게 하나만 보고 넘어가겠습니다. model은 강화학습에서 환경의 모델(model of environment)을 줄인 말로 에이전트의 액션에 대해 환경이 어떻게 응답할지 예측하기 위해 사용하는 모든 것을 가리킵니다. 결국 모델을 모른다는 말은 MDP를 모른다와 같은 의미입니다. 그리고 아직까지 작은 MDP를 다루기 때문에 테이블 룩업 방법을 통해 해결할 수 있습니다.

---

몬테 카를로 학습(Monte Carlo)

간단하게 동전을 던져서 앞면이 나올 확률의 기댓값을 구하고 싶을 때 어떻게 구할 수 있을까요? 간단하게 50퍼센트라고 할 수 있지만 동전의 무게중심에 따라 실제 값은 다를 수 있습니다. 그래서 실제로 던져보고 평균을 내어 기댓값을 구합니다. 앞면이 나온 횟수에서 전체 던진 횟수를 나누면 되고 횟수가 많아질 수록 그 값이 정확해집니다(대수의 법칙(Law of Large number)). 이것이 몬테카를로 방법론의 철학입니다.

강화학습에만 등장하는 방법론은 아니지만 직접 측정하기 어려운 통계량이 있을 때 통계량을 바탕으로 여러 번 샘플링 하여 값을 측정 하는 기법에는 대부분 몬테카를로가 들어갑니다. (ex: MCTS(Monte Carlo Tree Search), MCMC(Markov Chain Monte Carlo)

학습 알고리즘

1. 테이블 초기화
   이전처럼 테이블을 만들어서 상태값을 0으로 초기화합니다. 테이블은 방문횟수와 리턴 총합을 기록하기 위해 $N(s), V(s)$두개가 필요합니다.
2. 경험 쌓기
   각 상태에 대해서 리턴을 계산합니다.
   $G_{0}=r_{0}+\gamma r_{1}+\gamma^{2}r_{2}+...+\gamma^{T-1}r_{T-1}\\ G_{1}=r_{1}+\gamma r_{2}+\gamma^{2}r_{3}+...+\gamma^{T-1}r_{T-1}\\ ...\\ G_{T-1}=r_{1}\\ G_{T}=0$
3. 테이블 업데이트
   이번 에피소드에 방문한 모든 상태에 해당하는 칸의 값을 업데이트 해줍니다.
   $N(s_{t}):=N(s_{t})+1\\ V(s_{t}):=V(s_{t})+G_{t}$
4. value 계산
   $v_{\pi} \cong {V(s_{t})\over N(s_{t})}$

---

점진적인 업데이트

위의 방법과 동일하지만 1000번, 10000번의 에피소드가 마치고 평균을 내는 것이 아닌 하나의 에피소드가 끝날 때마다 업데이트 하는 방법이 있습니다.

위의 식을 사용합니다. $\alpha$는 다음 리턴의 값을 얼마만큼 반영할지 결정하는 파라미터 입니다. 이런 방식을 사용하면 얼마나 에피소드를 시행했는지 셀 필요가 없습니다.

몬테 카를로 학습 구현 코드

GridWorld 클래스

먼저 환경에 해당하는 GridWorld 클래스를 정의합니다.
step마다 보상은 -1을 받고 action 별로 메서드와 종료단계인지 확인하는 메서드를 정의해줍니다.

import random

class GridWorld:
    # 환경에 해당하는 클래스
    def __init__(self, n):
        self.n = n - 1
        self.r = 0
        self.c = 0
        
    def step(self, a):
        # action을 받아서 상태 변이를 일으키며 보상을 정해주는 함수
        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.r, self.c), reward, done
    
    def move_right(self):
        self.c += 1
        if self.c > self.n:
            self.c = self.n
    
    def move_left(self):
        self.c -= 1
        if self.c < 0:
            self.c = 0
    
    def move_up(self):
        self.r -= 1
        if self.r < 0:
            self.r = 0
    
    def move_down(self):
        self.r += 1
        if self.r > self.n:
            self.r = self.n
            
    def is_done(self):
        # 에피소드 끝났는지 판결
        if self.r == self.n and self.c == self.n:
            return True
        else:
            return False
    
    def reset(self):
        self.r, self.c = 0, 0
        return (self.r, self.c)

Agent 클래스

네 방향 랜덤 정책이므로 간단하게 표현할 수 있습니다.

class Agent:
    def __init__(self):
        pass
    
    def select_action(self):
        coin_list = [0, 1, 2, 3]
        action = random.choice(coin_list)
        return action

학습 진행

학습을 진행하는 메인 함수입니다.

환경과 에이전트 인스턴스를 선언하고 테이블과 변수를 초기화합니다.

def main():
    length = 5
    env = GridWorld(n=length)
    agent = Agent()
    data = [[0]*length for _ in range(length)]
    gamma = 1.0
    alpha = 0.0001
    
    for k in range(50000):
        # 에피소드 5만번 진행
        done = False
        history = []
        while not done:
            action = agent.select_action()
            (r, c), reward, done = env.step(action)
            history.append((r, c, reward))
        env.reset()
        
        # 매 에피소드가 끝나면 해당 데이터를 이용해 테이블을 업데이트
        cum_reward = 0

        for transition in history[::-1]:
            # 방문했던 상태들을 뒤에서부터 보며 리턴 계산
            r, c, reward = transition
            data[r][c] = data[r][c] + alpha * (cum_reward - data[r][c])
            cum_reward = cum_reward + gamma * reward # 가장 마지막부터 계산하며 재귀적 관계로 인해 이렇게 표현 가능
    
    for row in data:
        for e in row:
            print(f"{e:>10.2f}", end=" ")
        print()

        
main()

에피소드를 진행하면 할수록 실제값에 가까워지는 것을 확인할 수 있습니다.