파이썬과 케라스로 배우는 강화학습 D+2


본 노트는 교재 "파이썬과 케라스로 배우는 강화학습"을 공부하며 만든 필기입니다.

강화학습 기초 2 : 그리드월드와 DP

  • 다이나믹 프로그래밍 DP 작은 문제가 큰 문제 안에 중첩되어 있는 경우, 작은 문제의 답을 다른 작은 문제에 이용함으로써 효율적으로 계산하는 방법

    • DP로 벨만 기대 방정식 풀기 → 정책 이터레이션 Policy Iteration
    • DP로 벨만 최적 방정식 풀기 → 가치 이터레이션 Value Iteration

    → DP의 한계를 극복하고자 하는 학습이 강화학습이므로 DP 또한 제대로 알아야 한다.

다이나믹 프로그래밍과 그리드 월드

순차적 행동 결정 문제

  • 순차적 행동 결정 문제를 푸는 방법

    1. 순차적 행동 문제를 MDP로 전환한다.
    2. 가치함수를 벨만 방정식으로 반복적으로 계산한다.
    3. 최적 가치함수와 최적 정책을 찾는다.
  • 벨만 방정식을 푼다 == 최적 가치함수를 알아낸 것

    • v(s)=maxaE[Rt+1+γv(St+1)St=s,At=a]v_*(s) =\max_aE[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a] (벨만 최적 방정식)

다이나믹 프로그래밍

  • 큰 문제 안에 작은 문제들이 중첩된 경우 전체 문제를 작은 문제로 쪼개서 푼다.
  • 시간에 따라 다른 작은 문제들을 풀어나간다... k 타임의 작은 문제 → k+1 타임의 작은 문제
  • 참 가치함수를 한 번에 구하는 것이 아닌 여러 번에 나누어서 구한다.

DP 1: 정책 이터레이션 Policy Iteration

정책 이터레이션

  • REMIND; 정책 - 모든 상태에서 어떻게 행동할지에 대한 정보

    1. 무작위 정책 Random policy 으로 시작
    2. 현재의 정책을 평가 (정책 평가 Policy Evaluation)
    3. 나은 정책으로 발전 (정책 발전 Policy Improvement)

정책 평가

  • 정책을 평가하는 법? 척도? → 가치함수!
  • DP에서는 환경에 대한 모든 정보를 알고 문제에 접근하기 때문에 가치함수를 계산할 수는 있다.

    경우의 수가 기하급수적으로 증가하므로 어려움. → DP로 해결

  • 주변 상태의 가치함수와 한 타임스텝의 보상만 고려한다.

    주변 상태의 가치함수는 참 가치함수가 아님.

    여러 번 반복한다면 참 값으로 수렴하게 됨.

  • 벨만 기대 방정식 : vπ(s)=Eπ[Rt+1+γvπ(St+1)St=s]v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s]

    → 계산 가능한 형태의 벨만 기대 방정식 : vπ(s)=aAπ(as)(r(s,a)+γvπ(s))v_\pi(s) = \sum_{a \in A}\pi(a | s)(r_{(s, a)} + \gamma v_\pi(s'))

    → k번째 가치함수로 k+1번째 가치함수 계산 : vk+1(s)=aAπ(as)(r(s,a)+γvk(s))v_{k+1}(s) = \sum_{a \in A}\pi(a | s)(r_{(s, a)} + \gamma v_k(s'))

  • 정책 평가: π\pi라는 고정된 정책에 대해 반복적으로 수행하는 것.

정책 발전

  • 탐욕 정책 발전 Greedy Policy Improvement
  • 큐함수를 통해 어떤 행동이 좋은지 판단

    qπ(s,a)=Eπ[Rt+1+γvπ(St+1)St=s,At=a]q_\pi(s,a) = E_\pi [R_{t+1}+ \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a]

    → 계산 가능한 형태의 큐함수 : qπ(s,a)=r(s,a)+γvπ(s)q_\pi(s, a) = r_{(s, a)} + \gamma v_\pi(s')

  • 탐욕 정책 발전으로 얻을 수 있는 새로운 정책

    π(s)=argmaxaAqπ(s,a)\pi'(s) = \text{argmax}_{a \in A}q_\pi(s,a)

    큐함수를 최대로 만드는 행동만 골라서 하면 된다.

코드 분석

# 정책 평가는 고정된 policy에 대해서 이루어집니다.
def policy_evaluation(self):
    next_value_table = [[0.00] * self.env.width for _ in range(self.env.height)]

    # 가능한 모든 state에 대해서,
    for state in self.env.get_all_states():
        value = 0.0

        # 도착점이 (2, 2)인 그리드월드 예제이므로 도착점의 가치는 0으로 고정합니다.
        if state == [2, 2]:
            next_value_table[state[0]][state[1]] = value
            continue

        # 한 state의 가능한 모든 action들에 대해서,
        for action in self.env.possible_actions:
            reward = self.env.get_reward(state, action)
            next_state = self.env.state_after_action(state, action)
            next_value = self.get_value(next_state)
            # 가치 += 정책(확률) * (보상 + 감가율 * 다음 상태의 가치)
            value += (self.get_policy(state)[action]
                      * (reward + self.discount_factor * next_value))

        # state에 대한 가치함수 갱신
        next_value_table[state[0]][state[1]] = round(value, 2)

    # 가치함수 최종 갱신
    self.value_table = next_value_table

# 정책 발전
def policy_improvement(self):
    next_policy = self.policy_table

    # 가능한 모든 상태에 대해서,
    for state in self.env.get_all_states():
        if state == [2, 2]:
            continue

        value_list = []
        result = [0.0] * 4

        # 한 stated의 가능한 모든 행동에 대해서, (큐함수 구하기)
        for action in self.env.possible_actions:
            reward = self.env.get_reward(state, action)
            next_state = self.env.state_after_action(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))
        max_idx_list = max_idx_list.flatten().tolist()

        # 1개면 1, 아니면 1/2, 1/3 이런식으로
        prob = 1 / len(max_idx_list)

        for idx in max_idx_list:
            result[idx] = prob

        # 한 상태에 대한 정책 갱신
        next_policy[state[0]][state[1]] = result

    # 전체 정책 발전
    self.policy_table = next_policy

DP 2: 가치 이터레이션 Value Iteration

  • 정책 이터레이션 → 명시적인 정책 존재

    → 정책과 가치함수가 명확히 분리되어 있음 → 벨만 기대 방정식을 사용하는 이유

    → 분리되어 있기에 결정적인 정책이 아닌 확률적인 정책도 가능

  • 만약 정책이 결정적인 형태만으로 정의된다면?

    → 현재 가치함수가 최적은 아니지만 최적이라 가정하고 가치함수에 대해 결정적인 형태의 정책을 사용한다면?

    반복적으로 가치함수를 발전시켜서 최적에 도달한다면 문제가 발생하지 않음.

    최적 가치함수에 도달하고 최적 정책을 구한다. = 가치 이터레이션!

    → 정책 이터레이션처럼 정책이 명시적으로 표현되는 것이 아닌 내재적으로 가치함수 안에 표현

벨만 최적 방정식과 가치 이터레이션

  • 벨만 기대 방정식을 풀어서 나오는 답

    • 가치함수를 현재 정책에 대한 가치함수로 가정
    • 반복적으로 계산 (DP)
    • 현재 정책에 대한 참 가치함수를 구할 수 있다.
  • 벨만 최적 방정식을 풀어서 나오는 답

    • 가치함수를 최적 정책에 대한 가치함수로 가정
    • 반복적으로 계산 (마찬가지로 DP)
    • 최적 정책에 대한 참 가치함수, 즉 최적 가치함수를 찾을 수 있다.

      → 가치 이터레이션에서는 정책 발전이 필요가 없어짐.

  • 벨만 최적 방정식 v(s)=maxaE[Rt+1+γv(St+1)St=s,At=a]v_*(s) =\max_aE[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a]

    • 벨만 기대 방정식 vπ(s)=Eπ[Rt+1+γvπ(St+1)St=s]v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s] 과 달리 max를 사용함
    • 가치함수를 업데이트할 때 정책의 값을 고려해줄 필요가 없다. EπE_\pi가 아니기 때문.
    • 그저 현재 상태에서 가능한 값들 중 최고의 값으로 업데이트한다.
    • 계산 가능한 벨만 최적 방정식 vk+1(s)=maxaA(r(s,a)+γvk(s))v_{k+1}(s) = \text{max}_{a \in A}(r_{(s, a)} + \gamma v_k(s'))

코드 분석

def value_iteration(self):
    next_value_table = [[0.0] * self.env.width for _ in range(self.env.height)]

    # 가능한 모든 state에 대해서,
    for state in self.env.get_all_states():
        if state == [2, 2]:
            next_value_table[state[0]][state[1]] = 0.0
            continue

        value_list = []
        # 한 state의 action들의 가치만 계속 계산해준다.
        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]] = round(max(value_list), 2)

    self.value_table = next_value_table

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

다이나믹 프로그래밍의 한계

  • 계산 복잡도

    • 문제의 규모가 계속해서 늘어난다면 계산만으로는 한계가 있음.
  • 차원의 저주

    • 상태의 차원이 늘어난다면 상태의 수도 지수적으로 늘어남
  • 환경에 대한 복잡한 정보가 필요

    • DP를 해결하기 위해서는 보상과 상태 변환 확률을 정확히 알고 있어야 함.
    • 보상과 상태 변환 확률은 환경의 모델에 해당함.
    • 환경과의 상호작용을 통해 경험을 바탕으로 학습하는 방법 = 강화학습