3. 강화학습 동적 프로그래밍(Dynamic Programming)

 안녕하세요 '코딩 오페라'블로그를 운영하고 있는 저는 'Master.M'입니다.

오늘 알아볼 내용은 '동적 프로그래밍(Dynamic Programming)'입니다. 

 

 저의 경우 2016년 알파고와 이세돌의 바둑 대결로 인해 인공지능에 관심이 많이 생기기 시작했고 이후 구글의 딥마인드 팀에서 발표한 DQN논문 특히 아타리사의 '브레이트 아웃' 게임을 하는 것을 보고 많은 감명을 받아 '강화 학습'이라는 학문에 많은 관심을 갖게 되었습니다. 그래서 오늘부터는 강화 학습에 대해 차분히 정리를 해보도록 하겠습니다.

 

 저는 '파이썬과 케라스로 배우는 강화 학습'이라는 책을 읽으면서 독학을 하였습니다. 이 글은 이 책을 참고하여 제작합니다.(광고 아닙니다!!)

 

 동적 프로그래밍(Dynamic Programming)이란 프로그램이 시간에 따라 동적으로 변하는 것을 의미합니다. 기본적인 아이디어는 큰 문제 안에 작은 문제들이 중첩된 경우 전체 큰 문제를 작은 문제로 쪼개서 푸는 것입니다. 이런 식으로 계산을 하면 이전의 정보를 이용해 효율적으로 업데이트를 할 수 있게 됩니다. DP에는 벨만 기대 방정식을 이용하는 정책 이터레이션(Policy Iteration)과 벨만 최적 방정식을 사용하는 가치 이터레이션(Value Iteration)이 있습니다.

 

- 정책 이터레이션(Policy Iteration) : 벨만 기대 방정식

# 정책 평가 : 정책을 평가하는 데는 가치 함수가 쓰입니다. 그중에서도 벨만 기대 방정식이 쓰입니다. 이렇게 하면 위에서도 말했듯이 계산량이 줄어들고 계산을 여러 번 반복하면 참 값으로 수렴하게 됩니다. 아래는 벨만 기대 방정식의 수식인데, 간단히 설명하자면 pi는 현재 상태에서 어떤 행동을 할 확률을 의미합니다. 좀 더 자세히 알고 싶으시면 아래 제 글을 참조하시기 바랍니다. 

합의 벨만 기대 방정식

https://codingopera.tistory.com/22

2. 강화학습 MDP(Markov Decision Process)

 

# 정책 발전 : 탐욕 정책 발전(Greedy Policy Improvement) : 상태 s에서 선택 가능한 행동의 q(s, a)를 비교하고 그 중에서 가장 큰 큐 함수를 가지는 행동을 선택하는 방식입니다. 즉 어떠한 상태에서 최대한의 값을 갖도록 하는 행동을 정책으로 발전시킨다는 이야기입니다. 

탐욕 정책 발전으로 얻은 새로운 정책

def policy_iteration(value_table):
    gamma = 0.9
    policy = np.zeros(env.observation_space.n)

    for s in range(env.observation_space.n):
        q_values = [sum([prob*(r+gamma*value_table[s_])for prob,s_,r,_ in env.P[s][a]])for a in range(env.action_space.n)]
        policy[s] = np.argmax(np.array(q_values))
    return policy

위의 코드는 'FrozenLake-v1'이라는 게임을 이용해 policy interation을 코드로 작성한 것입니다. 데이터 구조를 참고하시기 바랍니다.

 

 

- 가치 이터레이션(Value Iteration) : 벨만 최적 방정식

 가치 이터레이션에서는 정책 이터레이션에서처럼 명시적으로 정책이 표현되는 것이 아니고 가치함수 안에 내재적으로 포함돼 있습니다. 때문에 가치 함수를 업데이트하면 따로 정책 발전이 필요 없이 자동으로 정책 또한 발전합니다. 파이썬 코드로 나타내면 아래와 같습니다. 

벨만 최적 방정식

def value_iteration(env):
    num_iterations = 5000
    thre = 1e-20
    gamma = 0.9
    value_table = np.zeros(env.observation_space.n)

    for i in range(num_iterations):
        updated_value_table = np.copy(value_table)
        for s in range(env.observation_space.n):
            q_values = [sum([prob*(r+gamma*updated_value_table[s_])for prob,s_,r,_ in env.P[s][a]])for a in range(env.action_space.n)]
            value_table[s] = max(q_values)
        if(np.sum(np.fabs(updated_value_table - value_table)) <= thre): # np.fabs: 절댓값
            break
    return value_table

 전체 코드는 아래 제 깃허브 주소에 있으니 한번 참고하셔서 직접 실행해 보시기 바랍니다.

https://github.com/CodingOpera/RL/blob/main/FrozenLake-v1.py

GitHub - CodingOpera/RL

 

 

 지금 까지 저희는 동적 프로그래밍(Dynamic Programming)에 대해 알아보았습니다. 이러한 DP는 계산 복잡도, 차원의 저주, 환경에 대한 완벽한 정보가 필요하다는 문제 짐이 있습니다. 이러한 문제를 해결하는 것으로 '강화 학습'이 등장했습니다. 도움이 되셨나요? 만약 되셨다면 구독 및 좋아요로 표현해 주시면 정말 많은 힘이 됩니다. 궁금한 사항 혹은 앞으로 다루어 주었으면 좋을 주제가 있으시면 댓글 남겨주시면 감사하겠습니다. 저는 '코딩 오페라'의 'Master.M'이었습니다. 감사합니다.