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

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

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

다이나믹 프로그래밍 DP 작은 문제가 큰 문제 안에 중첩되어 있는 경우, 작은 문제의 답을 다른 작은 문제에 이용함으로써 효율적으로 계산하는 방법
- DP로 벨만 기대 방정식 풀기 → 정책 이터레이션 Policy Iteration
- DP로 벨만 최적 방정식 풀기 → 가치 이터레이션 Value Iteration
→ DP의 한계를 극복하고자 하는 학습이 강화학습이므로 DP 또한 제대로 알아야 한다.

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

순차적 행동 결정 문제

순차적 행동 결정 문제를 푸는 방법
1. 순차적 행동 문제를 MDP로 전환한다.
2. 가치함수를 벨만 방정식으로 반복적으로 계산한다.
3. 최적 가치함수와 최적 정책을 찾는다.
벨만 방정식을 푼다 == 최적 가치함수를 알아낸 것
- $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_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s]$

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

→ k번째 가치함수로 k+1번째 가치함수 계산 : $v_{k+1}(s) = \sum_{a \in A}\pi(a | s)(r_{(s, a)} + \gamma v_k(s'))$
정책 평가: $\pi$ 라는 고정된 정책에 대해 반복적으로 수행하는 것.

정책 발전

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

$q_\pi(s,a) = E_\pi [R_{t+1}+ \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a]$

→ 계산 가능한 형태의 큐함수 : $q_\pi(s, a) = r_{(s, a)} + \gamma v_\pi(s')$
탐욕 정책 발전으로 얻을 수 있는 새로운 정책

$\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) =\max_aE[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a]$
- 벨만 기대 방정식 $v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s]$ 과 달리 max를 사용함
- 가치함수를 업데이트할 때 정책의 값을 고려해줄 필요가 없다. $E_\pi$ 가 아니기 때문.
- 그저 현재 상태에서 가능한 값들 중 최고의 값으로 업데이트한다.
- 계산 가능한 벨만 최적 방정식 $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를 해결하기 위해서는 보상과 상태 변환 확률을 정확히 알고 있어야 함.
- 보상과 상태 변환 확률은 환경의 모델에 해당함.
- 환경과의 상호작용을 통해 경험을 바탕으로 학습하는 방법 = 강화학습