[강화학습] 05 - 그리드월드와 다이내믹 프로그래밍 (2)

개요 

지금까지 배운 내용을 한번 정리해봅시다. 저희는 순차적 행동 결정 문제를 MDP를 이용해서 수학적으로 정의했습니다. 

 

이 MDP로 정의된 문제의 최종 목표는 에이전트가 받을 보상의 합을 최대로 하는 것입니다. 이를 위해서 저희는 앞으로 받을 보상의 합에 대한 기댓값인 가치함수를 이용하기로 했습니다.

 

그리고 이 가치함수의 정의를 이용해서 벨만 기대 방정식과 벨만 최적 방정식을 만들었죠. 두 벨만 방정식은 다이내믹 프로그래밍을 이용해서 풀 수 있는데, 벨만 기대 방정식을 이용하는 것이 정책 이터레이션이고 벨만 최적 방정식을 이용하는 것이 가치 이터레이션입니다. 

 

정책 이터레이션과 가치 이터레이션은 후에 살사로 발전하고 살사는 다시 변형되어 큐러닝으로 이어집니다. 

지난번엔 정책 이터레이션의 정책 평가와 정책 발전에 대해서 그리드월드의 예제와 함께 알아봤다면 이번 시간엔 가치 이터레이션에 대해서 설명하려고 합니다.

 

---

가치 이터레이션

정책 이터레이션은 명시적인 정책이 있으며, 그 정책을 평가하는 도구로서 가치함수를 사용합니다. 그리고 가치함수로 평가한 정책을 발전시키는 과정을 반복하면서 최적정책에 도달하였죠. 이를 그림으로 나타내면 다음과 같습니다.

이렇게 정책과 가치함수가 완전히 분리돼 있다는 점이 정책 이터레이션이 벨만 기대 방정식을 사용하는 이유입니다. 

 

정책이 독립적이므로 대부분 확률적인 정책일텐데, 이 확률적인 정책을 고려하여 가치함수를 계산하기 위해서 기댓값 개념이 들어있는 벨만 기대 방정식을 사용하는 것이죠.

 

가치 이터레이션에서는 이와 반대로 정책이 결정적인 형태로 정의됩니다. 즉 정책이 가치함수에 의해 정해진다는 의미입니다. 

 

현재의 가치함수가 최적은 아니지만 최적이라고 가정하고 다이내믹 프로그래밍을 이용하여 반복적으로 가치함수를 업데이트한다면 최적 가치함수에 도달할 것입니다. 

 

그리고 그 최적 가치함수에 내재돼 있는 정책이 바로 최적 정책인 것이죠.(최적 정책을 따랐을 때 얻는 보상의 합이 최적 가치함수이기 때문입니다.) 

 

정책이 가치함수 안에 내재적으로 포함되어 있기 때문에 가치함수를 업데이트한다면 정책은 자동으로 발전되게 됩니다. 따라서 가치 이터레이션에서는 정책 발전 과정이 필요없을 뿐더러 정책의 값도 고려하지 않아도 됩니다.

 

이런 가치 이터레이션을 풀기 위해서 해가 최적 가치함수인 벨만 최적 방정식을 이용합니다. 앞에서 배웠던 벨만 최적 방정식은 다음과 같습니다. $$v_*(s) = \underset{a}{max}E[R_{t+1} + γv_*(S_{t+1}) | S_t = s, A_t = a]$$ 

 

저희는 이 식을 이용해서 $v_*(S_{t+1})$가 이미 최정 정책에 의한 가치함수라고 가정하고 $R_{t+1} + rv_*(S_{t+1})$ 값 중 최대값을 현재 상태 s의 최적 가치함수 $v_*(s)로 업데이트 해줍니다. 이를 그림으로 나타내면 다음과 같습니다.

 

모든 상태에 대해서 계산을 진행하여 가치함수를 업데이트해주고 이 과정을 반복적으로 계산한다면 최적 가치함수가 나올 것입니다. 그리고 최적 정책은 최적 가치함수에 내재되어 있겠죠.

 

벨만 최적 방정식을 계산 가능한 형태로 변환하면 다음과 같이 바뀝니다. $$v_{k+1}(s) = \underset{a∈A}{max}(r_{(s,a)} + γv_k(s'))$$

※ 벨만 최적 방정식에서 $R_{t+1}$ 앞의 E는 상태 변환 확률 때문에 포함되었으므로 상태 변환 확률이 1인 그리드 월드에서는 생략해도 무관합니다.

 

가치 이터레이션 코드 설명

가치 이터레이션에서도 정책 이터레이션과 똑같이 Env 클래스에 정의된 환경의 정보를 사용합니다. 이는 이전 포스팅에서 설명했으니 생략하겠습니다. 

 

환경의 정보와 더불어 정책 이터레이션과 가치 이터레이션을 비교해가면서 보면 도움이 될 것 같으니 필요하신 분은 아래에 있는 이전 포스팅을 참고하면 되겠습니다.

 

https://developer-lionhong.tistory.com/10

[강화학습] 04 - 그리드월드와 다이내믹 프로그래밍 (1)

 

<변수 선언>

def __init__(self, env):
    # 환경에 대한 객체 선언
    self.env = env
    # 가치 함수를 2차원 리스트로 초기화
    self.value_table = [[0.0] * env.width for _ in range(env.height)]
    # 할인율
    self.discount_factor = 0.9

정책 이터레이션과 다 똑같지만, 정책이 가치함수 안에 내재되어 있는 가치 이터레이션에서는 policy_table(정책을 저장하는 리스트)이 정의되어 있지 않은 것을 확인할 수 있습니다. 

 

<value_iteration>

# 벨만 최적 방정식을 통해 다음 가치 함수 계산
def value_iteration(self):
    # 다음 가치함수 초기화
    next_value_table = [[0.0] * self.env.width 
                       for _ in range(self.env.height)]

    # 모든 상태에 대해서 벨만 최적방정식을 계산                           
    for state in self.env.get_all_states():
        # 마침 상태의 가치 함수 = 0
        if state == [2, 2]:
            next_value_table[state[0]][state[1]] = 0.0
            continue

        # 벨만 최적 방정식
        value_list = []
        for action in self.env.possible_actions:
            next_state = self.env.state_after_action(state, action)
            reward = self.env.get_reward(state, action)
            next_value = self.get_value(next_state)
            value_list.append((reward + self.discount_factor * next_value))

        # 최댓값을 다음 가치 함수로 대입
        next_value_table[state[0]][state[1]] = max(value_list)
    # 모든 상태에 대한 가치함수를 업데이트
    self.value_table = next_value_table

$$v_{k+1}(s) = \underset{a∈A}{max}(r_{(s,a)} + γv_k(s'))$$

마침 상태를 제외한 모든 상태에 대해서 위 최적 벨만 방정식을 이용하여 가치 함수를 업데이트하고 있습니다.

 

빈 리스트인 value_list에 각 행동에 대한 $r_{(s,a)} + γv_k(s')$ 값을 추가한 뒤 최대값을 next_value_table에 저장하는 과정을 모든 상태에 대해서 진행하고 이를 value_table에 덮어씌우면서 가치함수를 업데이트하고 있습니다.

 

value_iteration을 한번 실행시키면 가치함수는 한 번 업데이트 된 것입니다. 따라서 최적 정책을 위한 최적 가치함수에 값이 가까워지기 위해서는 value_iteration을 여러번 실행시켜야 합니다.

 

<get_action>

# 현재 가치 함수로부터 행동을 반환
def get_action(self, state):
    if state == [2, 2]:
        return []

    # 모든 행동에 대해 큐함수 (보상 + (감가율 * 다음 상태 가치함수))를 계산
    value_list = []
    for action in self.env.possible_actions:
        next_state = self.env.state_after_action(state, action)
        reward = self.env.get_reward(state, action)
        next_value = self.get_value(next_state)
        value = (reward + self.discount_factor * next_value)
        value_list.append(value)

    # 최대 큐 함수를 가진 행동(복수일 경우 여러 개)을 반환
    max_idx_list = np.argwhere(value_list == np.amax(value_list))
    action_list = max_idx_list.flatten().tolist()
    return action_list

최적 가치함수를 찾았다면 저희는 이제 최적 가치함수에 내재된 최적 정책을 찾아야합니다. 보상의 합을 최대로 하기 위한 최적 정책은 큐함수의 최대값을 이용해서 구할 수 있습니다. 

 

$$r(s,a) + rv_π(s')$$ 위 식을 이용해서 각 행동에 대한 큐함수 값을 value에 저장하고 이를 리스트 형태인 value_list에 추가시킨뒤 이 중 최대값을 가지는 행동의 index를 action_list에 저장시킵니다. (index 반환 과정에 쓰인 함수도 이전 포스팅에서 설명드렸습니다. ^0^)

 

만약 가장 큰 value 값을 가지는 행동이 여러 개라면 그 행동의 index를 모두 action_list에 저장시키고 이후 에이전트가 움질일 때 두 방향 중 무작위로 선택해서 움직입니다.

 

가치 이터레이션 코드 실행

왼쪽 그림은 value_iteration을 한 번 실행시킨 결과입니다. 최대의 값으로만 업데이트하기 때문에 마침 상태인 파란색 주변만 가치함수가 1로 변하고 장애물인 초록색 주변 가치함수는 -1이 아닌 0임을 확인할 수 있습니다.

 

오른쪽 그림은 value_iteration을 여러번 실행시킨 결과로 value_iteration을 더 실행시켜도 더 이상 가치함수 값이 바뀌지 않기 때문에 각 상태에 적혀있는 숫자들이 최적 가치함수임을 알 수 있습니다. 큐함수의 최대값을 이용하여 최적 정책을 구해보면 다음과 같습니다. 

가치 이터레이션의 전체 코드는 아래 링크에서 찾아볼 수 있습니다.

 

https://github.com/rlcode/reinforcement-learning-kr-v2

GitHub - rlcode/reinforcement-learning-kr-v2: [파이썬과 케라스로 배우는 강화학습] 텐서플로우 2.0 개정판

 

---

다이내믹 프로그래밍의 한계와 강화학습

지금까지 저희는 다이내믹 프로그래밍에 속하는 정책 이터레이션과 가치 이터레이션을 열심히 알아봤는데 사실 이것들은 충격적이게도 강화학습이 아닙니다.(헉!) 이들은 계산을 빠르게 하는 것일 뿐 "학습"을 하는 것이 아니기 때문입니다.

 

다이내믹 프로그래밍이 강화학습의 근간이 되긴 했지만 다이내믹 프로그래밍의 한계를 극복하고자 나온 것이 바로 강화학습입니다. 그렇다면 다이내믹 프로그래밍의 한계는 무엇일까요?

 

1. 계산 복잡도

앞에서 예시로 든 그리드월드는 5x5로 크기가 정말 작은 문제입니다. 다이내믹 프로그래밍의 계산 복잡도는 상태 크기의 3제곱에 비례하기 때문에 상태가 많은 바둑이나 무수히 많은 상태를 가진 실제 환경에서는 이를 사용할 수 없는 것이죠.

 

2. 차원의 저주

그리드월드의 상태는 좌표인 (x,y)로 표현되기 때문인데 2차원입니다. 하지만 상태의 차원이 늘어나면 상태의 수가 지수적으로 늘어나 계산량이 너무 많아집니다.

 

3. 환경에 대한 완벽한 정보가 필요

다이내믹 프로그래밍을 풀 때는 환경의 모델(보상함수, 상태 변환 확률)을 정확히 안다는 가정하에 풀었지만 보통은 이 정보를 정확히 알 수 없습니다.

 

위의 세가지 한계를 극복하고자 경험을 바탕으로 학습하는 강화학습이 등장한 것입니다.

 

모델 없이 학습하는 강화학습

MDP에서 환경의 모델은 상태 변환 확률과 보상입니다. 모델이란 어떤 시스템에 입력이 들어왔을 때 시스템이 어떤 출력을 내는지에 대한 방정식이죠. 

 

현실 세계에서는 바람과 공기와 같은 자연현상에 대한 방정식을 정확하게 세우기란 불가능합니다. 따라서 강화학습에서는 모델 없이 환경과의 상호작용을 통해 입력과 출력 사이의 관계를 학습합니다.

 

다이내믹 프로그래밍에서는 환경의 모델(보상함수, 상태 변환 확률)을 모두 알고 있었습니다. 다이내믹 프로그래밍은 어떤 상태에서 특정 행동을 하면 얼만큼의 보상을 주는지 알고 있었다면, 강화학습에서는 이를 알지 못합니다. 강화학습은 단지 에이전트가 직접 행동함으로써 환경으로부터 보상을 얻어가며 시스템의 입력과 출력 사이의 관계를 학습하는 것입니다.

 

이는 다이내믹 프로그래밍과 강화학습의 가장 큰 차이점이자, 복잡한 문제에서 환경에 대한 사전지식이 없는 상태에서도 학습할 수 있는 강화학습의 장점이라고 할 수 있습니다.

 

---

지난 포스팅에 걸쳐서 저희는 다이내믹 프로그래밍에 해당하는 정책 이터레이션, 가치 이터레이션을 이용하여 MDP 문제를 푸는 방법에 대해서 예시와 함께 알아봤습니다.

 

이 다이내믹 프로그래밍을 근간으로 하여 다이나믹 프로그래밍의 한계를 극복하고자 나온 강화학습의 학습 방법에 대해서 다음 포스팅에서 설명하려고 합니다. 지금까지 읽어주셔서 감사합니다~!

 

 

http://www.yes24.com/Product/Goods/44136413

파이썬과 케라스로 배우는 강화학습 - YES24

※ 이 글은 위의 책 내용을 바탕으로 작성한 글입니다.