가치반복 알고리즘

보상

• 강화학습에서는 가치의 척도로 돈 대신 보상(reward)를 사용한다
• 어떤 시각 $t$에 받을 수 있는 보상 $R_t$를 즉각보상(immediate reward)이라고 한다
• 그리고 앞으로 받을 수 있으리라 예상되는 보상의 합계 $G_t$를 총보상이라고 한다
  $R_t=R_{t+1}+R_{t+2}+R_{t+3}+\cdots$
• 다만 시간을 고려해야한다. 그래서 이자율을 포함시킨다
• 시간 할인율(time discount) : $r$
• 따라서 할인총보상(discounted total reward) $G_t$을 사용한다
  $G_t=R_{t+1}+rR_{t+2}+r^2R_{t+3}+\cdots$

행동가치와 상태가치

행동가치

• 정책 $\pi$를 기반으로 할 때 행동가치는 행동가치 함수 $Q^\pi(s,a)$로 나타낼 수 있다
• 행동은 (위, 오른쪽, 아래, 왼쪽)의 4종류가 있으며 오른쪽은 인덱스가 1이므로 $a=1$이며
  $Q^\pi(s=7,a=1)=R_{t+1}=1$
• 그럼 에이전트의 위치가 $s = \text{S7}$이고, 행동 $a =$ 위인 경우, 행동가치 함수 $Q^\pi(s,a)$는 어떻게 될까?
  지나야 하는 단계가 두 단계가 늘어난다
  $Q^\pi(s=7,a=0)=r^2*1$

상태가치

• 상태 $s$에서 정책 $\pi$를 따라 행동할 때 얻으리라 기대할 수 있는 할인총보상 $G_t$를 말한다
  $V^\pi(s=7)=1$
  예를 들어, 에이전트가 S7에 있을 때 오른쪽으로 이동하면 목표 지점에 도달해서 보상 1을 받는다
  $V^\pi(s=4)=r*1$
  에이전트가 S4에 있을 때 상태가치 함수는 다음과 같이 나타낼 수 있다. 상태 S4에서 최적의 행동(아래)을 취하면 상태가 S7이 되므로 S7 상태가치 값을 사용하면 된다
  $V^\pi(s=4)=R_{t+1}+r*V^\pi(s=7)$
  이때 $R_{t+1}$은 상태 S7이 됐을 때 바로 받게 되는 즉각보상이지만, 여기서는 목표 지점 외에는 즉각보상이 없으므로 $R_{t+1}=0$이 된다. 즉, 다음과 같다
  $V^\pi(s=4)=0+r*V^\pi(s=7)=r*1=r$

벨만 방정식과 마르코프 결정 프로세스

벨만 방정식

• 좌변은 상태 $s$에서 상태가치 $V$를 나타낸다. 그리고 상태가치 $V$는 우변의 값이 가장 커지는 행동 $a$를 취했을 때 기대할 수 있는 값이다.
• 우변의 $R_{s,a}$는 상태 $s$에서 행동 $a$를 취했을 때 얻을 수 있는 즉각보상 $R_{t+1}$을 의미한다. 우변의 $V^\pi()$에서 괄호 안의 $s(s,a)$는 상태 $s$에서 행동 $a$를 취해서 이동한 다음 단계의 새로운 상태 $s_{t+1}$을 의미한다
• 다시 말해, 새로운 상태 $s_{t+1}$에서의 상태가치 $V$에 1단계만큼 시간할인율을 곱해서 계산한 항과 즉각보상 $R_{s,a}$의 합이 가질 수 있는 최댓값이 현재의 상태가치가 된다.
• 이 벨만 방정식은 상태가치 함수에 대한 것이지만 행동가치 함수에 대해서도 성립한다

마르코프 결정 프로세스(Markov decision process, MDP)

• 벨만 방정식이 성립하려면 학습 대상이 마르코프 결정 프로세스(MDP)이어야 한다는 전제조건을 만족해야 한다
• 마르코프 결정 프로세스란 다음 단계의 상태 $s_{t+1}$이 현재 상태 $s_t$에서 취한 행동 $a_t$에 의해 결정되는 시스템을 말한다
• 다시 말해 조금 전 벨만 방정식에서 설명했던 우변의 $s(s,a)$가 상태 $s$에서 행동 $a$를 취했을 때 이동하는 새로운 상태 $s_{t+1}$을 나타낸다는 설명과 딱 들어맞는다
• 그럼 마르코프 결정 프로세스가 아닌 것은 무엇일까? 현재 상태 $s_t$ 외의 과거 예를 들면 $s_{t+1}$이 $s_{t-1}$로부터도 영향을 받는 시스템이 이에 해당한다

Sarsa 알고리즘 구현

Epsilon-Greedy 알고리즘으로 정책 구현

• 일단 미로와 theta 생성까지 그대로 진행한다

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

fig = plt.figure(figsize=(5,5))
ax = plt.gca()

# 붉은 벽 그리기
plt.plot([1,1], [0,1], color = 'red', linewidth=2)
plt.plot([1,2], [2,2], color = 'red', linewidth=2)
plt.plot([2,2], [2,1], color = 'red', linewidth=2)
plt.plot([2,3], [1,1], color = 'red', linewidth=2)

plt.text(0.5, 2.5, "S0", size = 14, ha ='center')
plt.text(1.5, 2.5, "S1", size = 14, ha ='center')
plt.text(2.5, 2.5, "S2", size = 14, ha ='center')
plt.text(0.5, 1.5, "S3", size = 14, ha ='center')
plt.text(1.5, 1.5, "S4", size = 14, ha ='center')
plt.text(2.5, 1.5, "S5", size = 14, ha ='center')
plt.text(0.5, 0.5, "S6", size = 14, ha ='center')
plt.text(1.5, 0.5, "S7", size = 14, ha ='center')
plt.text(2.5, 0.5, "S8", size = 14, ha ='center')
plt.text(0.5, 2.3, "START", size = 14, ha ='center')
plt.text(2.5, 0.3, "GOAL", size = 14, ha ='center')

ax.set_xlim(0, 3)
ax.set_ylim(0, 3)
plt.tick_params(axis = "both", which ='both', bottom = False, top = False, labelbottom = False, right = False, left = False, labelleft = False)

line, =ax.plot([0.5], [2.5], marker = "o", color = 'g', markersize = 60)

# 정책을 결정하는 파라미터의 초깃값 theta_0을 설정

# 줄은 상태 0~7, 열은 행동 방향(상, 우, 하, 좌)를 나타낸다
theta_0 = np.array([[np.nan, 1, 1, np.nan], # S0
                    [np.nan, 1, np.nan, 1], # S1
                    [np.nan, np.nan, 1, 1], # S1
                    [1, 1, 1, np.nan], # S3
                    [np.nan, np.nan, 1, 1], # S4
                    [1, np.nan, np.nan, np.nan], # S5
                    [1, np.nan, np.nan, np.nan], # S6
                    [1, 1, np.nan, np.nan], # S7, S8은 목표 지점이므로 정책이 없다
                    ])

• 이어서 가치반복 알고리즘에서 사용할 행동가치 함수를 표형식 표현으로 구현하겠다
• 행은 상태 $s$를 나타내고, 열은 행동 $a$를 나타내는 형태로 행동가치 함수 $Q(s,a)$를 구현한다
• 실제 행동가치는 알 수 없으므로 초기 상태로 난수값을 부여한다
• 코드 중 2번째에서 theta_0을 곱하는 이유는 난수 중에 벽에 해당하는 부분을 np.nan으로 바꿔주기 위해서다
• 각 시각에서 행동가치 함수 $Q$에서 행동 $a$를 계산하기 위한 정책을 구현한다
  • 단순하게 생각하면 $Q$ 값이 최대가 되는 행동을 고르기만 하면 된다(Greedy 전략)
  • 그러나 $Q$가 제대로 계산돼 있지 않은 상태에서 이런 전략을 채용하면 무작위로 생성한 행동가치 함수 $Q$의 초깃값에 따라 행동이 결정되며 그 뒤로 학습이 제대로 일어나지 않을 가능성이 있다

    이를테면 맨 처음 위치 S0에서 계속 오른쪽으로 가게 되는 현상 등

• 이 때문에 일정 확률 $\epsilon$으로 무작위 행동을 취하고, 나머지 확률 $1-\epsilon$으로 행동가치 $Q$가 최대가 되는 행동을 취하기로 한다
• 이러한 알고리즘을 $\epsilon-\text{greedy}$라고 한다
• 이때 $\epsilon$ 값은 시행 회차가 늘어남에 따라 작아지게 한다

---

• 이처럼 가치반복 알고리즘에서는 현재 행동가치 함수의 최댓값을 이용해 행동을 결정하는 방법(이용, exploit)
• 무작위로 행동을 선택하는 방법(탐색, explore)를 적절히 섞어야 한다
• 이를 탐색-이용 트레이드오프(explore-exploit tradeoff)라고 한다

Epsilon-Greedy 알고리즘 구현

• 먼저 무작위 행동정책 pi_0을 정의한다

# 정책 파라미터 theta_0을 무작위 행동 정책 pi로 변환하는 함수

def simple_convert_into_pi_from_theta(theta):
    '''단순 비율 계산'''

    [m, n] = theta.shape # theta의 행렬 크기를 구함
    pi = np.zeros((m, n))
    for i in range(0, m) :
        pi[i, :] = theta[i, :] / np.nansum(theta[i, :]) # 비율 계산

    pi = np.nan_to_num(pi) # nan을 0으로 변환

    return pi

# 무작위 행동정책 pi_0을 계산
pi_0 = simple_convert_into_pi_from_theta(theta_0)

• 이어서 알고리즘을 구현한다. 여기서는 행동을 결정하는 함수 get_action과 행동을 인자로 받아 다음 상태로 구하는 함수 get_s_next로 나누어 구현한다

# Epsilon-Greedy 알고리즘 구현

def get_actions(s, Q, epsilon, pi_0):
    direction = ["up", "right", "down", "left"] 

    # 행동을 결정
    if np.random.rand() < epsilon :
        # 확률 epsilon으로 무작위 행동을 선택함
        next_direction = np.random.choice(direction, p=pi_0[s, :])
    else :
        # Q값이 최대가 되는 행동을 선택함
        next_direction = direction[np.nanargmax(Q[s, :])]

    # 행동을 인덱스로 변환
    if next_direction == "up":
        action = 0
    elif next_direction == "right":
        action = 1
    elif next_direction == "down":
        action = 2
    elif next_direction == "left":
        action = 3

    return action

def get_s_next(s, a, Q, epsilon, pi_0):
    direction = ["up", "right", "down", "left"]
    next_direction = direction[a] # 행동 a의 방향

    # 행동으로 다음 상태를 결정
    if next_direction == "up":
        s_next = s - 3 # 위로 이동하면 상태값이 3만큼 줄어든다
    elif next_direction == "right":
        s_next = s + 1 # 오른쪽으로 이동하면 상태값이 1만큼 늘어난다
    elif next_direction == "down":
        s_next = s + 3 # 아래로 이동하면 상태값이 3만큼 늘어난다
    elif next_direction == "left":
        s_next = s - 1 # 왼쪽으로 이동하면 상태값이 1만큼 줄어든다

    return s_next

행동가치 함수 $Q(s,a)$를 Sarsa 알고리즘으로 수정

• 행동가치 함수 $Q(s,a)$가 제대로 된 값이 될 수 있도록 학습하는 부분을 구현하겠다.
• Sarsa 알고리즘을 이용해 함수를 수정한다.
• 벨만 방정식에 따라 다음 관계식이 성립
  $Q(s_t,a_t) = R_{t+1}+rQ(s_{t+1},a_{t+1})$
• 그러나 학습 중에는 행동가치 함수가 정확하지 않기 때문에 이 관계식의 등호가 성립하지 않음
• 이때 위 식에서 양변의 차이에 해당하는
  $R_{t+1}+rQ(s_{t+1},a_{t+1})-Q(s_t,a_t)$
  를 TD 오차(temporal difference error)라고 한다
• 이 TD오차가 0이 되면 정확한 행동가치 함수가 학습된 것이다
• 이때 $Q$는 다음 식에 따라 수정한다
  $Q(s_t, a_t)=Q(s_t,a_t)+\eta*(R_{t+1}+rQ(s_{t+1},a_{t+1})-Q(s_t,a_t))$
  • $\eta$ : 학습률
  • $R_{t+1}+rQ(s_{t+1},a_{t+1})-Q(s_t,a_t)$ : TD 오차
  • 현재 상태 $s$와 행동 $a$, 즉각보상 $R$, 다음 단계의 상태 $s$와 행동 $a$를 사용해서 Sarsa이다

Sarsa 알고리즘 구현

# Sarsa 알고리즘으로 행동가치 함수 Q를 수정

def Sarsa(s, a, r, s_next, a_next, Q, eta, gamma) :
    if s_next == 8 : # 목표 지점에 도달한 경우
        Q[s, a] = Q[s, a] + eta * (r - Q[s, a])
    else :
        Q[s, a] = Q[s, a] + eta * (r + gamma * Q[s_next, a_next] - Q[s, a])

    return Q

Sarsa로 미로찾기 구현

• 지난번 사용했던 정책경사 알고리즘과는 달리, 가치반복 알고리즘에서는 가치함수를 매 시행 단위가 아니라 단계 단위로 수정한다

# Sarsa 알고리즘으로 미로를 빠져나오는 함수, 상태 및 행동 그리고 Q값의 히스토리를 출력

def goal_maze_ret_s_a_Q(Q, epsilon, eta, gamma, pi):
    s = 0 # 시작 지점
    a = a_next = get_action(s, Q, epsilon, pi) # 첫 번째 행동
    s_a_history = [[0, np.nan]] # 에이전트의 행동 및 상태의 히스토리를 기록하는 리스트

    while (1) : # 목표 지점에 이를 때까지 반복
        a = a_next # 행동 결정

        s_a_history[-1][1] = a
        # 현재 상태(마지막이므로 인덱스가 -1)를 히스토리에 추가

        s_next = get_s_next(s, a, Q, epsilon, pi)
        # 다음 단계의 상태를 구함

        s_a_history.append([s_next, np.nan])
        # 다음 상태를 히스토리에 추가, 행동은 아직 알 수 없으므로 nan으로 둔다

        # 보상을 부여하고 다음 행동을 계산
        if s_next == 8:
            r = 1 # 목표 지점에 도달했다면 보상을 부여
            a_next = np.nan
        else :
            r = 0
            a_next = get_action(s_next, Q, epsilon, pi)
            # 다음 행동 a_next를 계산

        # 가치함수를 수정
        Q = Sarsa(s, a, r, s_next, a_next, Q, eta, gamma)

        # 종료 여부 판정
        if s_next == 8 : # 목표 지점에 도달하면 종료
            break
        else :
            s = s_next

    return [s_a_history, Q]

• 마지막으로 미로를 헤매지 않고 곧장 빠져나갈 수 있도록 반복해서 가치함수를 수정하는 부분을 구현한다. 여기서는 100시행(에피소드)을 마치면 학습를 종료하기로 한다
• 그리고 상태가치 함수 $V(s)$는 각 상태 $s$에서 행동가치 함수 $Q(s,a)$의 최댓값을 계산한다

# Sarsa 알고리즘으로 미로 빠져나오기

eta = 0.1 # 학습률
gamma = 0.9 # 시간할인율
epsilon = 0.5 # epsilon-greedy 알고리즘 epsilon 초깃값
v = np.nanmax(Q, axis = 1) # 각 상태마다 가치의 최댓값을 계산
is_continue = True
episode = 1

while is_continue : # is_continue의 값이 False가 될 때까지 반복
    print('에피소드 :'+str(episode))

    # epsilon 값을 조금씩 감소시킴
    epsilon = epsilon / 2

    # Sarsa 알고리즘으로 미로를 빠져나온 후, 결과로 나온 행동 히스토리와 Q값을 변수에 저장
    [s_a_history, Q] = goal_maze_ret_s_a_Q(Q, epsilon, eta, gamma, pi_0)

    # 상태가치의 변화
    new_v = np.nanmax(Q, axis = 1) # 각 상태마다 행동가치의 최댓값을 계산
    print(np.sum(np.abs(new_v - v))) # 상태가치 함수의 변화를 출력
    v = new_v
    print("목표 지점까지의 단계 수 :" + str(len(s_a_history)))

    # 100 에피소드 반복
    episode += 1
    if episode > 100:
        break