강화학습 - Model Free(4)

이전까지 MDP를 모를 때 value를 평가하는 방법(MC, TD)을 봤습니다(Prediction). 이제 정책을 찾는 방법을 알아볼 차례입니다.(Control)

몬테카를로 컨트롤

MDP를 알고있을 때에는 정책 이터레이션을 사용해 밸류를 계산하고 그 값에서 그리디하게 움직이는 정책을 만드는 과정을 반복했습니다.

정책 이터레이션을 사용할 수 없는 이유

MDP를 알 수 없는 상황에서 정책 평가시 반복적 정책 평가를 사용할 수 없습니다. 벨만 기대 방정식을 보면 $r_{s}^{a}$와$P^{a}_{ss'}$를 알아야 가치를 구할 수 있는데 Model free의 경우는 모르는 값이기 때문입니다.

보상을 알기 위해서는 직접 액션을 통해 값을 확인해야하며 오직 도착했다는 정보만 알수있고 얼마의 확률로 이 상태에 도달하는지 다른 상태의 도착확률은 얼마인지 알 수 없습니다. 이것이 model free상황에서 정책 이터레이션을 사용할 수 없는 첫 번째 이유입니다.

두번째 이유로는 정책 개선 단계에서 그리디 정책을 만들 수 없다는 점입니다. 그리디 정책을 쓰고 싶어도 액션을 통해 어떤 상태에 도달할지 모르기에 상태의 밸류, 액션의 밸류를 비교할 수 없어 쓸 수가 없습니다.

해결 방법

1. 평가자리에서 정책 평가
   정책 평가 단계에서 반복적 정책 평가가 불가능 하니 MC나 TD를 사용할 수 있습니다.
2. V 대신 Q 사용
   상태 가치 함수 $v(s)$만으로는 정책 개선 단계애서 그리디 정책을 생성할 수 없습니다. 그래서 $v(s)$대신 $q(s, a)$를 이용해볼 수 있습니다.
   $q(s, a)$를 알게 되면 MDP에 대한 정보를 몰라도 그리디한 액션을 할 수 있습니다.

종합적으로 보면 MC 방법을 이용해 $q(s, a)$를 구하는 것이 핵심입니다. 그리고 추가할 한 가지는 탐색(exploration)단계입니다.

에이전트가 최적의 해를 찾으려면 주어진 MDP를 충분히 탐색해야합니다. MC를 통해 실제 행한 액션의 밸류를 업데이트 하는 순간 그리디 정책을 만들면서 한쪽 방향으로만 가게 만듭니다. 그러면 다른 액션을 할 기회가 사라지고 상태, 액션의 가치를 평가할 수 없게 됩니다. 그리고 하필 그 상태가 최적의 해라면 에이전트는 최적해를 찾을 수가 없습니다.
그렇다고 무작정 탐색만 할 순 없습니다. 적절한 탐색의 정도를 조절해야합니다. 다양한 방법들이 있지만 가장 단순하면서도 좋은 방법인 $\epsilon$-greedy방법이 있습니다.

$\epsilon$-greedy

입실론 그리디 방법은 굉장히 간단한 아이디어 입니다. 원래의 정책을 따르면서 $\epsilon$확률 만큼은 랜던하게 액션을 선택하는 방법입니다.
수식으로 표현하면 아래와 같습니다.

식은 간단합니다. 여기서 조금 더 좋은 방법론은 $\epsilon$을 처음에 높게 주다가 점점 줄여주는 것입니다. 처음에는 환경에 대해 잘 모르기 때문에 탐색을 많이 하다가 정보를 충분히 얻으면 최선의 선택을 내리는데 중점을 둡니다. 이런 방법론을 decaying $\epsilon$-greedy라고 부릅니다.

몬테카를로 컨트롤 구현 코드

decaying $\epsilon$-greedy를 구현해 보겠습니다.
이전과 마찬가지로 그리드 월드 이지만 장애물이 있는 버전입니다.

구체적인 진행 방법은 수렴할 때 까지 아래 과정을 반복하는 것입니다.
1. 에피소드에서 경험 쌓기
2. 경험한 데이터로 $q(s, a)$ 테이블 값을 업데이트(정책 평가)
3. 업데이트된 $q(s, a)$테이블을 이용해 $\epsilon$-greedy 정책 만들기(정책 개선)

환경은 이전에 작성한 코드와 유사합니다. 장애물을 파라미터로 넣어주고 move함수만 조금 바꾸면 됩니다. 그리고 시작 지점은 (0, 0)이 아닌 (2, 0)에서 시작합니다.

import numpy as np
import random

class GridWorld:
    # 환경에 해당하는 클래스
    def __init__(self, nr, nc, obstacles):
        self.nr = nr-1 # 행
        self.nc = nc-1 # 열
        self.obstacles = obstacles
        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):
        if (self.r, self.c+1) in self.obstacles:
            pass
        elif self.c >= self.nc:
            pass
        else:
            self.c += 1
    
    def move_left(self):
        if (self.r, self.c-1) in self.obstacles:
            pass
        elif self.c <= 0:
            pass
        else:
            self.c -= 1
    
    def move_up(self):
        if (self.r-1, self.c) in self.obstacles:
            pass
        elif self.r <= 0:
            pass
        else:
            self.r -= 1
    
    def move_down(self):
        if (self.r+1, self.c) in self.obstacles:
            pass
        elif self.r >= self.nr:
            pass
        else:
            self.r += 1
            
    def is_done(self):
        # 에피소드 끝났는지 판결
        if self.r == self.nr and self.c == self.nc:
            return True
        else:
            return False
    
    def reset(self):
        self.r, self.c = 2, 0
        return (self.r, self.c)

QAgent에 해당하는 클래는 q테이블을 가지고 있고 이를 실제 액션을 선택할 때 사용합니다. 실제 장애물의 정보를 미리 QAgent가 들고있다는 점을 수정해야겠지만 행동은 select_action을 통해 선택하고 MC방법으로 값을 업데이트합니다.

class QAgent:
    def __init__(self, nr, nc, obstacles):
        self.nr = nr
        self.nc = nc
        self.obstacles = obstacles
        self.q_table = np.zeros((nr, nc, 4))
        self.eps = 0.9
        self.alpha = 0.01
    
    def select_action(self, s):
        r, c = s
        coin = random.random()
        if coin < self.eps:
            action = random.randint(0, 3)
        else:
            action_val = self.q_table[r, c, :]
            action = np.argmax(action_val)
        return action

    def update_table(self, history):
        cum_reward = 0 
        for transition in history[::-1]:
            s, a, reward, _ = transition
            r, c = s
            self.q_table[r, c, a] = self.q_table[r, c, a] + self.alpha * (cum_reward - self.q_table[r, c, a])
            cum_reward += reward
    
    def anneal_eps(self):
        self.eps -= 0.03
        self.eps = max(self.eps, 0.1)
    
    def show_table(self):
        q_lst = np.argmax(self.q_table, axis=2).tolist()
        for r_idx, _r in enumerate(q_lst):
            for c_idx, _c in enumerate(_r):
                if (r_idx, c_idx) in self.obstacles:
                    q_lst[r_idx][c_idx] = '◼'
                elif _c == 0:
                    q_lst[r_idx][c_idx] = '→'
                elif _c == 1:
                    q_lst[r_idx][c_idx] = '←'
                elif _c == 2:
                    q_lst[r_idx][c_idx] = '↑'
                elif _c == 3:
                    q_lst[r_idx][c_idx] = '↓'
        for r in q_lst:
            for c in r:
                print(c, end=" ")
            print()

메인 학습 함수는 아래와 같습니다.

def main():
    row_len = 5
    col_len = 7
    obstacles = [(0, 2), (1, 2), (2, 2), (2, 4), (3, 4), (4, 4)]
    env = GridWorld(row_len, col_len, obstacles)
    agent = QAgent(row_len, col_len, obstacles)
    
    for _ in range(10000):
        done = False
        history = []
        s = env.reset()
        while not done:
            a = agent.select_action(s)
            s_prime, reward, done = env.step(a)
            history.append((s, a, reward, s_prime))
            s = s_prime
        agent.update_table(history)
        agent.anneal_eps()
    agent.show_table()
    
main()

### 출력 결과 ###
↓ ← ◼ ↓ → → ↓ 
→ ↓ ◼ → → → ↓ 
↓ ↓ ◼ ↑ ◼ ↓ ↓ 
→ → → ↑ ◼ ↓ ↓ 
↑ ↑ ↑ ↑ ◼ → →

액션 테이블에서 가장 보상이 높은 값을 선택하여 나타낸 결과 올바른 길을 가는 것을 확인 할 수 있습니다. 하이퍼 파라미터에 따라 결과가 다르게 나올 수 있어 여러번 돌려보며 안정적인 학습이 되는 파라미터를 찾는 것도 중요합니다.