(5) 정책 이터레이션, 가치 이터레이션

본 포스트는 “파이썬과 케라스로 배우는 강화학습” 도서의 다섯번째 리뷰 포스트입니다.

3장 강화학습 기초 2: 그리드월드와 다이내믹 프로그래밍

정책 이터레이션 (Policy Iteration)

정책 평가 (Policy Evaluation)

한 번의 정책 평가 과정을 순서대로 나타내면 다음과 같다.

1. 번째 가치함수 matrix에서 현재 상태 에서 갈 수 있는 다음상태 에 저장돼 있는 가치함수 을 불러온다. (보라색 부분중의 하나)

2. 에 할인율 를 곱하고 그 상태로 가는 행동에 대한 보상 을 더한다.

3. 2번에서 구한 값에 그 행동을 할 확률, 즉 정책 값을 곱한다.

4. 3번을 모든 선택 가능한 행동에 대해 반복하고 그 값들을 더한다.

5. 4번 과정을 통해 더한 값을 번째 가치함수 matrix의 상태 자리에 저장한다.
 

6. 1-5 과정을 모든 에 대해 반복한다

정책 발전 (Policy Improvement)

정책 이터레이션 코드

class PolicyIteration:
  def __init__(self, env):
    # 환경에 대한 객체
    self.env = env

  # 정책 평가
  def policy_evaluation(self):
    pass

  # 정책 발전
  def policy_improvement(self):
    pass

  # 특정 상태에서 정책에 따른 행동
  def get_action(self, state):
    return action

if __name__ == "__main__":
  env = Env()
  policy_iteration = PolicyIteration(env)
  grid_world = GraphicDisplay(policy_iteration)
  grid_world.mainloop()

• env.width, env.height: 그리드월드의 너비와 높이

• env.state_after_aciton(state, action): 특정 상태에서 특정 행동을 했을 때 에이전트가 가는 다음 상태

• env.get_all_states(): 존재하는 모든 상태

• env.get_reward(state, action): 특정 상태의 보상

• env.possible_actions: 상,하,좌,우

policy_evaluation

# 벨만 기대 방정식을 통해 다음 가치함수를 계산하는 정책 평가
def policy_evaluation(self):
    # 다음 가치함수 초기화
    next_value_table = [[0.00] * self.env.width
                        for _ in range(self.env.height)]

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

        # 벨만 기대 방정식
        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 += (self.get_policy(state)[action] *
                      (reward + self.discount_factor * next_value))

        next_value_table[state[0]][state[1]] = value

    self.value_table = next_value_table

• : for action in self.env.possible_actions:

• : self.get_policy(state)[action]

• : reward = self.env.get_reward(state, action)

• : self.discount_factor (0.9)

• : next_state = self.env.state_after_action(state, action)

• : self.get_value(next_state)

• : next_value_table[state[0]][state[1]]

policy_improvement

# 현재 가치 함수에 대해서 탐욕 정책 발전
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, 0.0, 0.0, 0.0]

        # 모든 행동에 대해서 [보상 + (할인율 * 다음 상태 가치함수)] 계산
        for index, action in enumerate(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))
        max_idx_list = max_idx_list.flatten().tolist()
        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

• 현재 상태에서 가능한 행동에 대해 을 계산한다.

• 계산한 값을 value_list에 저장한다.

• max 함수를 통해 value_list에 담긴 값 중 가장 큰 값을 알아낸다.

• argwhere를 통해 가장 큰 값의 index를 알아내고(여러개면 여러개 반환) max_idx_list에 저장한다.

• max_idx_list의 길이를 바탕으로 확률을 계산하여 확률값을 계산하고 result에 저장한다.

정책 이터레이션에서 에이전트는 정책 평가와 정책 발전을 반복하여 최적 정책을 찾아낸다.

가치 이터레이션

class ValueIteration:
  def __init__(self, env):
    # 환경 객체 생성
    self.env = env

  # 벨만 최적 방정식을 통해 다음 가치함수 계산
  def value_iteration(self):
    return

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

  def get_value(self, state):
    return

if __name__ == "__main__":
  env = Env()
  value_iteration = ValueIteration(env)
  grid_world = GraphicDisplay(value_iteration)
  gird_world.mainloop()

# 벨만 최적 방정식을 통해 다음 가치 함수 계산
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

• 위의 벨만 최적 방정식을 계산하여 value_list에 저장한다.

• value_list에 저장된 값중 최대의 값을 새로운 가치함수로 저장한다.

# 현재 가치 함수로부터 행동을 반환
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

• 모든 행동에 대해 큐함수를 구한다.

• 그 중 가장 큰 value 값을 가지는 행동의 인덱스를 가져온다(여러개라면 여러개 모두 가져온다)

• 행동들을 모두 action_list에 저장한다.

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

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

1. 할 수 있는 선에서 정확한 모델링을 한 다음, 모델링 오차에 대한 부분을 실험을 통해 조정한다.

2. 모델 없이 환경과의 상호작용을 통해 입력과 출력 사이의 관계를 학습한다.

정리

• 정책 이터레이션: 벨만 기대 방정식을 이용해 정책을 평가하고, 탐욕 정책 발전을 이용해 정책 발전

• 가치 이터레이션: 최적 정책을 가정하고 벨만 최적 방정식 이용. 정책이 직접적으로 주어지지 않아 큐함수를 통해 행동 선택

• 다이내믹 프로그래밍의 한계: 계산 복잡도, 차원의 저주, 환경에 대한 완벽한 정보 필요

3장 한줄평

짧고 간결하게 쓰는게 오히려 힘들다..