TD Method란?

이전 글에서 살펴보았던 MC Method를 이용하면 환경에 대한 지식 없이도 경험만으로 최적 가치 함수 및 최적 정책을 찾을 수 있었다. 예를 들어 Nonstationary한 환경에서 every-visit MC Method를 사용하는 상황을 생각해 보자. 시간 $t$ 에서, 적절한 상수 $0 < α \leq 1$ 에 대해 가치 함수 $V$ 는 실제로 관측된 Sample Return $G_{t}$ 를 이용해 다음과 같이 업데이트된다.^[1]

V (S_{t}) \leftarrow V (S_{t}) + α [G_{t} - V (S_{t})]

그런데 MC Method는 한 에피소드가 끝나야 학습을 진행할 수 있다는 단점이 있다. Sample Return $G_{t}$ 를 계산하려면 한 에피소드가 끝나야 하기 때문이다. 이 때문에 에피소드의 길이가 긴 경우 MC Method를 이용하면 학습 시간이 너무 길어진다. 또한 MC Method는 실시간으로 학습할 수 없고, Continuing Task에서는 사용할 수 없다.

그런데 생각해 보면 학습을 위해 꼭 에피소드의 종료까지 기다릴 필요가 없다. 상태 $S_{t}$ 에서 $S_{t + 1}$ 로 전이하면서 보상 $R_{t + 1}$ 을 받는 것을 관측했다고 해 보자. 그렇다면, $S_{t}$ 에서의 가치 $V (S_{t})$ 의 추정값은 관측값 $R_{t + 1}$ 과 또 다른 추정값 $V (S_{t + 1})$ 을 이용해 다음과 같이 유의미한 업데이트할 수 있다.

V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

이런 식으로 한 추정값( $V (S_{t})$ )을 관측값( $R_{t + 1}$ )과 다른 추정값( $V (S_{t + 1})$ )을 이용해 추정하는 방법을 TD(Temporal-Difference) Method라 한다. 관측값을 통해 추정값을 추정한다는 점에서 TD Method는 MC Method와 유사하다. 또한 다른 추정값을 통해 한 추정값을 추정한다는 점에서^[2] TD Method는 DP와 유사하다. 즉 TD Method는 DP와 MC Method를 결합한 방법이라 이해할 수 있다.

DP에서는 보상과 다음 상태의 확률 분포 등을 알려주는, 환경에 대한 모델(model)이 필요했다. 그러나 TD Method에서는 모델이 없어도 된다. TD Method는 MC Method에서처럼 경험으로부터 학습이 가능하다. 또한 TD Method에서는^[3] 한 스텝(time step)만 기다리면 되기 때문에 MC Method와 다르게 실시간 학습(online learning)이 가능하다.

여담 : Online Learning vs. Offline Learning

RL에서는 추정값을 업데이트하는 다음과 같은 형태의 식을 많이 볼 수 있다.

(new estimates) \leftarrow (old estimates) + (step size) \cdot [(target) - (old estimates)]

이때 위 식의 빨간색 테두리 영역을 (해당 추정값의) Increment라 부른다.

이때, 다음 두 가지 형태의 학습법이 존재할 수 있다.

Online Learning : 에피소드 진행 중에 Increment가 바로바로 계산되고, 이를 이용해 바로바로 추정값을 업데이트하는 학습법
Offline Learning : 에피소드 진행 중에는 Increment를 계산만 해 놓거나, 또는 에피소드가 끝난 이후에 Increment를 계산해, 에피소드가 모두 끝나고 나서야 추정값을 업데이트하는 학습법

Online Learning의 예로는 상술했듯이 TD Method가 있다. 한편 Offline Learning의 예로는 MC Method가 있다.

TD(0) Method

위에서 살펴본 TD Method의 업데이트 식을 조금 더 자세히 알아보자.

V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

이 식은 TD(0) Method 또는 one-step TD Method라 불리는, 가장 간단한 TD Method 업데이트 식이다.

(Constant- $α$ ) MC Method에서는 $V (S_{t})$ 가 $G_{t}$ 와 가까워지도록 업데이트가 진행된다. 다시 말해, MC Method의 업데이트의 목표(target)는 $G_{t}$ 이다. 한편, TD(0) Method에서는 $V (S_{t})$ 가 $R_{t + 1} + γ V (S_{t + 1})$ 와 가까워지도록 업데이트가 진행된다. 다시 말해, TD(0) Method의 업데이트의 목표는 $R_{t + 1} + γ V (S_{t + 1})$ 이다.

TD(0) Method를 일반화하면 TD( $λ$ ) Method, $n$ -step TD Method라는 TD Method가 된다. 이들에 대해서는 다음 글에서 조금 더 자세히 다루도록 하겠다. 이번 글에서는 TD(0) Method를 이용하여 Prediction 문제와 Control 문제를 풀어보도록 하자.

TD(0) Prediction

TD(0) Method의 업데이트 식

V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

을 이용하면 특정 정책 $π$ 를 따를 때의 가치 함수 $v_{π}$ 를 추정할 수 있다.

Pseudo Code : TD(0) Prediction

입력 : 정책 $π$

모든 $s \in S^{+}$ 에 대해, $V (s) \in R$ 을 임의의 값으로 초기화. 단, $V (terminal) = 0$ .

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

Loop for each step of episode:

$A \leftarrow π (S)$

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

$V (S) \leftarrow V (S) + α [R + γ V (S^{'}) - V (S)]$

$S \leftarrow S^{'}$

until $S$ is terminal

TD(0) Method의 업데이트 식은 다음과 같이 변형할 수 있다.

\begin{aligned} V (S_{t}) & \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})] \\ \leftarrow (1 - α) V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1})] \end{aligned}

$V (S_{t})$ 는 상태 $S_{t}$ 에서의 현재 가치 추정값이고, $R_{t + 1} + γ V (S_{t + 1})$ 은 $V (S_{t})$ 이 가까워지길 원하는, TD(0) Method의 업데이트의 목표이다. 이때, $α$ 의 값이 작으면 현재의 추정값( $V (S_{t})$ )에 좀더 가중치를 두는 것이고, $α$ 의 값이 크면 목표값( $R_{t + 1} + γ V (S_{t + 1})$ )에 조금 더 가중치를 두는 것이다.

한편, 우리는 이전 글에서

\begin{aligned} (1) & v_{π} (s) & = E_{π} [G_{t} | S_{t} = s] \\ = E_{π} [R_{t + 1} + γ G_{t + 1} | S_{t} = s] \\ (2) & = E_{π} [R_{t + 1} + γ v_{π} (S_{t + 1}) | S_{t} = s] \end{aligned}

을 배웠다. DP에서는 위의 (2)번 식을 이용해 최적 정책을 추정했다. DP가 추정인 이유는 계산 과정에서 현재 단계에서 정확히 알 수 없는 $v_{π} (S_{t + 1})$ 대신 추정값인 $V (S_{t + 1})$ 를 쓰기 때문이다(bootstrapping). 한편 MC Method에서는 위의 (1)번 식을 이용해 최적 정책을 추정했다. MC Method가 추정인 이유는 (환경에 대한 모든 정보를 모르므로) $E [G_{t}]$ 대신 샘플링된 값(Sample Return)을 사용하기 때문이다.

DP와 MC Method를 결합한 TD Method의 결과 역시 추정값이다. TD Method는 (2)번 식을 이용해 최적 정책을 추정하는데, 현재 단계에서 정확히 알 수 없는 $v_{π} (S_{t + 1})$ 대신 추정값인 $V (S_{t + 1})$ 를 쓰고, 기댓값 대신 샘플링된 값을 사용하기 때문이다.

참고로 DP처럼 가능한 모든 다음 값들을 이용해 현재 값을 업데이트하는 것을 expected update라 부른다. 반면 MC Method나 TD Method에서처럼 샘플링된 다음 값 하나만을 이용해 현재 값을 얻베이트하는 것을 sample update라 부른다.

TD error

TD(0) Method의 업데이트 식

V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

에서 대괄호 안 빨간색 테두리 영역을 TD error라 하고, 기호로 $δ_{t}$ 라 쓴다.

δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})

$δ_{t}$ 를 계산하려면 보상 $R_{t + 1}$ 과 상태 $S_{t + 1}$ 가 필요하기에, $t$ 번째 TD error $δ_{t}$ 는 시점 $t + 1$ 에서야 계산 가능해진다.

비슷하게, (Constant- $α$ ) MC Method의 업데이트 식

V (S_{t}) \leftarrow V (S_{t}) + α [G_{t} - V (S_{t})]

에서 대괄호 안 빨간색 테두리 영역을 MC error라 부른다. 이때 한 에피소드 동안 $V$ 가 바뀌지 않는다면,^[4] MC error는 다음과 같이 TD error의 합 형태로 표현할 수 있다.

\begin{aligned} G_{t} - V (S_{t}) & = R_{t + 1} + γ G_{t + 1} - V (S_{t}) \\ = R_{t + 1} + γ G_{t + 1} - V (S_{t}) + γ V (S_{t + 1}) - γ V (S_{t + 1}) \\ = [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})] + [γ G_{t + 1} - γ V (S_{t + 1})] \\ = δ_{t} + γ [G_{t + 1} - V (S_{t + 1})] \\ = δ_{t} + γ δ_{t + 1} + γ^{2} [G_{t + 2} - V (S_{t + 2})] \\ = ⋮ \\ = δ_{t} + γ δ_{t + 1} + γ^{2} δ_{t + 2} + \dots + γ^{T - t - 1} δ_{T - 1} + γ^{T - t} [G_{T} - V (S_{T})] \\ = δ_{t} + γ δ_{t + 1} + γ^{2} δ_{t + 2} + \dots + γ^{T - t - 1} δ_{T - 1} + γ^{T - t} [0 - 0] \\ = \sum_{k = t}^{T - 1} γ^{k - t} δ_{k} \end{aligned}

TD(0) Method에서는 매 시간 간격마다 $V$ 가 업데이트되므로 위 성질이 완벽히 성립하진 않는다. 그러나 $α$ 의 크기가 충분히 작다면 위 성질은 (근사적으로) 성립한다. 이 성질은 TD(0) Prediction으로도 가치 함수 $v_{π}$ 를 추정할 수 있음을 보여준다. 구체적으로, 고정된 정책 $π$ 에 대해, $α$ 가 다음 두 가지 중 하나인 경우 TD(0) Prediction을 이용하면 100%의 확률로 $V$ 는 실제 가치 함수 $v_{π}$ 로 수렴한다.

$α$ 가 충분히 작은 상수이다.
$α_{n}$ 은 다음 조건을 따르는, 감소하는 변수이다.

\sum_{n = 1}^{\infty} α_{n} = \infty and \sum_{n = 1}^{\infty} α_{n}^{2} = c

(단, $c$ 는 상수)

MC Prediction과 TD(0) Prediction 모두 $V$ 를 실제 가치 함수 $v_{π}$ 로 수렴시킬 수 있다면, 어느 방법이 더 빨리 수렴할까?(= 어느 방법의 학습 속도가 더 빠를까? = 어느 방법이 더 적은 데이터로도 더 효율적으로 학습할 수 있을까?) 사실 이 질문은 수학적으론 아직 답이 명확하게 증명되진 않았으나, 경험적으로 확률적인 문제(stochastic task)에서는 TD Method가 Constant- $α$ MC Method보다 더 빨리 수렴한다는 것이 알려져 있다.

예제 : Random Walk

간단한 MRP(Markov Reward Process)^[5] 문제에서 Constant- $α$ MC Prediction과 TD(0) Prediction을 적용해 둘을 비교해보자.

Random Walk

Fig.01과 같은 게임판 위에서, 말은 다음과 같은 규칙으로 움직인다.

모든 에피소드는 가운데 C에서 시작한다. 왼쪽 또는 오른쪽 끝(T)에 도착하면 에피소드가 종료된다.
A, B, C, D, E에서는 50%의 확률로 왼쪽, 50%의 확률로 오른쪽으로 갈 수 있다.
E에서 오른쪽 끝의 T로 가면 보상 +1을 받는다(그리고 에피소드가 종료된다). 이외의 모든 이동은 보상 0을 받는다.

예를 들어, 다음과 같은 에피소드가 나올 수 있다 : C, 0, B, 0, C, 0, D, 0, E, 1, T(종료)

위와 같은 상황에서, A, B, C, D, E 각 상태에서의 가치는 얼마일까? $γ = 1$ 이라 하면, 각 상태에서의 가치는 각 상태에서 시작했을 때 오른쪽 끝의 T에 도착할 확률과 같다. 즉,

v (A) = \frac{1}{6} v (B) = \frac{2}{6} v (C) = \frac{3}{6} v (D) = \frac{4}{6} v (E) = \frac{5}{6}

이다. 이 값을 Constant- $α$ MC Prediction과 TD(0) Prediction을 이용해 구해보자.

Code : Random Walk

python

import copy
import numpy as np
import matplotlib.pyplot as plt

labels = ["A", "B", "C", "D", "E"]
true_values = np.array([1/6, 2/6, 3/6, 4/6, 5/6])

class Prediction:
    def __init__(self):
        self.initial_values = {
            "A": 0.5,
            "B": 0.5,
            "C": 0.5,
            "D": 0.5,
            "E": 0.5,
            "T": 0
        }
        
    def generateEpisode(self):
        state_names = ["T", "A", "B", "C", "D", "E", "T"]
        state = 3
        
        episode = []
        while True:
            episode.append(state_names[state])
            if state_names[state] == "T":
                break
            
            delta = np.random.choice([-1, 1])
            
            if state == 5 and delta == 1:
                episode.append(1)
            else:
                episode.append(0)
                
            state += delta
        
        return episode
        
    def td0_predict(self, episode_num, alpha, gamma=1):
        values = copy.deepcopy(self.initial_values)
        
        history = np.zeros((episode_num + 1, 5))
        history[0] = [values[x] for x in labels]
        
        for e in range(episode_num):
            episode = self.generateEpisode()
            idx = 0
            while idx < len(episode) - 1:
                cur_state = episode[idx]
                reward = episode[idx + 1]
                next_state = episode[idx + 2]
                
                values[cur_state] = values[cur_state] + alpha * (reward + gamma * values[next_state] - values[cur_state])
                
                idx += 2
            
            history[e + 1] = [values[x] for x in labels]
            
        return history
    
    def mc_predict(self, episode_num, alpha, gamma=1):
        values = copy.deepcopy(self.initial_values)
        
        history = np.zeros((episode_num + 1, 5))
        history[0] = [values[x] for x in labels]
        
        for e in range(episode_num):
            episode = self.generateEpisode()
            idx = len(episode) - 3
            G = 0
            while idx >= 0:
                cur_state = episode[idx]
                reward = episode[idx + 1]
                
                G = reward + gamma * G
                values[cur_state] = values[cur_state] + alpha * (G - values[cur_state])
                
                idx -= 2
                
            history[e + 1] = [values[x] for x in labels]
            
        return history
    
def drawValues(results, title):
    plt.plot(range(len(labels)), true_values, c="k")
    for result in results:
        plt.plot(range(len(labels)), [result["values"][i] for i in range(len(labels))], marker='o', label=f"{result['episode_num']}")

    plt.xticks(range(len(labels)), labels)
    plt.title(title)
    plt.legend()
    plt.xlabel("States")
    plt.ylabel("Estimated Values")
    plt.show()

def drawErrors(td_results, mc_results):
    for i, result in enumerate(td_results):
        plt.plot(range(101), result["errors"], c=f"C{i}", label=f"TD(0) Prediction [α = {result['alpha']}]")
        
    for i, result in enumerate(mc_results):
        plt.plot(range(101), result["errors"], c=f"C{i}",label=f"MC Prediction [α = {result['alpha']}]", linestyle="--")

    plt.xticks([0, 25, 50, 75, 100])
    plt.xlim(0, 100)
    plt.ylim(0, 0.25)
    plt.title("RMS error")
    plt.legend(loc="upper left", bbox_to_anchor=(1, 1))
    plt.xlabel("Episodes")
    plt.ylabel("RMS Errors")
    plt.show()

if __name__ == "__main__":
    predict = Prediction()
    
    # Values : TD(0) Prediction
    title = "TD(0) Prediction"
    episode_nums = [0, 1, 10, 100]
    results = [{"episode_num": x, "values": predict.td0_predict(episode_num=x, alpha=0.1)[-1]} for x in episode_nums]
    drawValues(results, title)
    
    # Values : MC prediction
    title = "MC Prediction"
    episode_nums = [0, 1, 10, 100]
    results = [{"episode_num": x, "values": predict.mc_predict(episode_num=x, alpha=0.1)[-1]} for x in episode_nums]
    drawValues(results, title)
    
    # RMS Errors
    alphas = [0.01, 0.02, 0.03, 0.04, 0.05, 0.1, 0.15]
    td_results = [{"alpha": alpha, "errors": np.mean([np.sqrt(np.mean(np.square(predict.td0_predict(episode_num=100, alpha=alpha) - true_values), axis=1)) for x in range(100)], axis=0)} for alpha in alphas]
    mc_results = [{"alpha": alpha, "errors": np.mean([np.sqrt(np.mean(np.square(predict.mc_predict(episode_num=100, alpha=alpha) - true_values), axis=1)) for x in range(100)], axis=0)} for alpha in alphas]
    drawErrors(td_results, mc_results)

코드 설명

line 8 ~ 83 : Prediction 클래스
- line 19 ~ 38 : Prediction.generateEpisode()
  - Random Walk 에피소드(ex. C, 0, B, 0, C, 0, D, 0, E, 1, T)를 생성하는 메소드
- line 40 ~ 60 : Prediction.td0_predict()
  - TD(0) Prediction을 수행하는 메소드
  - (episode_num + 1, 5) 크기의 Numpy 배열을 반환
    - $i$ 행은 이때까지 $i$ 개의 에피소드를 사용해 (TD(0) Prediction으로) 현재까지 추정한 가치 함수를 담고 있다.
      - ex) 0번 행 : 0개의 에피소드를 사용해 현재까지 추정한 가치 함수(즉, 초기값)
      - ex) 100번 행 : 99개의 에피소드를 사용해 현재까지 추정한 가치 함수
    - 각 열은 앞에서부터 각각 A, B, C, D, E에서의 가치를 의미한다.
- line 62 ~ 83 : Prediction.mc_predict()
  - MC Prediction을 수행하는 메소드
  - (episode_num + 1, 5) 크기의 Numpy 배열을 반환
    - $i$ 행은 이때까지 $i$ 개의 에피소드를 사용해 (MC Prediction으로) 현재까지 추정한 가치 함수를 담고 있다.
      - ex) 0번 행 : 0개의 에피소드를 사용해 현재까지 추정한 가치 함수(즉, 초기값)
      - ex) 100번 행 : 99개의 에피소드를 사용해 현재까지 추정한 가치 함수
    - 각 열은 앞에서부터 각각 A, B, C, D, E에서의 가치를 의미한다.
line 85 ~ 95 : drawValues()
- Fig.02, Fig.03의 그래프를 그린 함수
line 97 ~ 111 : drawErrors()
- Fig.04의 그래프를 그린 함수
line 113 ~ 132 : main
- 에피소드의 개수를 다르게 하여 TD(0) Prediction과 MC Prediction을 적용 (Fig.02, Fig.03)
- $α$ 를 다르게 하여 TD(0) Prediction과 MC Prediction을 적용 (Fig.04)
  - Fig.04는 다음과 같은 방법으로 그려졌다:
    1. 현재 추정하고 있는 가치 함수가 [0.5, 0.5, 0.5, 0.5, 0.5]라 하자.
    2. 오차(error)를 구한다. 즉, 1에서 참값([1/6, 2/6, 3/6, 4/6, 5/6])을 뺀다 : [0.333, 0.167, 0.000, -0.167, -0.333].
    3. 2를 제곱(Square)한다 : [0.111, 0.028, 0.000, 0.028, 0.111].
    4. 3의 평균(Mean)을 구한다 : 0.056.
    5. 4의 제곱근(Root)을 구한다. 이 값이 RMS Error이다 : 0.236.
    6. 각 $α$ 에 대해, 0개의 에피소드를 보고 추정한 가치 함수의 RMS Error, 1개의 에피소드를 보고 추정한 가치 함수의 RMS Error, ..., 100개의 에피소드를 보고 추정한 가치 함수의 RMS Error를 계산한다.
    7. 6의 과정을 100번 반복한다. 즉, 100개의 에피소드를 보는 학습을 처음부터 100번 반복한다.
    8. 각 $α$ 에 대해, 7의 결과를 평균한다. 즉, 0개의 에피소드로 계산한 RMS Error 100개의 평균, 1개의 에피소드로 계산한 RMS Error 100개의 평균, ... 100개의 에피소드로 계산한 RMS Error 100개의 평균을 구한다. 이를 그래프로 나타낸 것이 Fig.04이다.

Fig.02 Random Walk - TD(0) Prediction
TD(0) Prediction을 이용해 가치 함수를 추정한 결과. 검은 선은 참값(true values)을 나타낸다.

Fig.03 Random Walk - MC Prediction
MC Prediction을 이용해 가치 함수를 추정한 결과. 검은 선은 참값(true values)을 나타낸다.

Fig.04 Random Walk - RMS Errors
각 $α$ 에 대해, TD(0) Prediction과 MC Prediction로 추정한 가치 함수에 대해 RMS Error를 계산한 결과. x축은 사용한 에피소드의 개수를, y축은 RMS Error를 의미한다. 실선은 TD(0) Prediction, 점선은 MC Prediction을 의미한다. 같은 색은 같은 $α$ 를 의미한다.

Fig.02, Fig.03에서 볼 수 있듯이, 에피소드의 개수가 많아짐에 따라 가치 함수의 추정값은 점점 더 참값(검은 실선)에 가까워진다.^[6] 이때 Fig.04에서 볼 수 있듯이, TD(0) Prediction이 MC Prediction에 비해 더 적은 오류(RMS Error)를 가진다.^[7]

TD(0) Control

TD(0) Method를 이용하여 Control 문제를 풀어보자. TD Method로 Control 문제를 푸는 기본적인 아이디어는 GPI이다. 다만 이번엔 TD Prediction을 이용해 Evaluation 과정을 수행한다.

TD Control의 해법에는 On-policy^[8] TD Control 방법인 SARSA, 그리고 Off-policy^[9] TD Control 방법인 Q-Learning, 이렇게 두 가지가 있다. 두 방법 모두 상태-가치 함수(state-value function) $v_{π}$ 가 아닌, 행동-가치 함수 $q_{π}$ 를 사용해 학습을 진행한다.

SARSA

On-policy TD Control Method를 SARSA라 부른다. SARSA에서는 다음 업데이트 식을 이용해 행동-가치 함수(action-value function) $Q$ 를 업데이트한다.

Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1}) - Q (S_{t}, A_{t})]

SARSA는 위 업데이트 식을 이용해 현재 정책 $π$ 에 대해 $q_{π}$ 를 추정하고, 동시에 정책 $π$ 를 $q_{π}$ 에 대해 탐욕적인 정책이 되게 바꾼다. 참고로, SARSA라는 이름은 위 업데이트 식에서 사용하는 5개 값, $S_{t}$ , $A_{t}$ , $R_{t + 1}$ , $S_{t + 1}$ , $A_{t + 1}$ 를 따 만들어졌다. 만약 모든 상태-행동 쌍(state-action pair)이 무한 번 방문되고(visit), 무한한 시간이 지난 후 정책이 Greedy Policy로 수렴하면,^[10] SARSA는 100%의 확률로 최적 정책 $π_{*}$ 와 최적 가치 함수 $q_{*}$ 로 수렴한다.

Pseudo Code : SARSA(On-policy TD(0) Control) ( $ε$ -greedy Policy 사용)

모든 $s \in S^{+}$ , $a \in A (s)$ 에 대해, $Q (s, a) \in R$ 을 임의의 값으로 초기화. 단, $Q (terminal, \cdot) = 0$ .

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

현재 $Q$ 에 대해 $ε$ -greedy Policy를 사용하여 $S$ 에서의 행동 $A$ 를 선택

Loop for each step of episode:

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

현재 $Q$ 에 대해 $ε$ -greedy Policy를 사용하여 $S^{'}$ 에서의 행동 $A^{'}$ 를 선택// Improvement 과정

$Q (S, A) \leftarrow Q (S, A) + α [R + γ Q (S^{'}, A^{'}) - Q (S, A)]$ // Evaluation 과정

$S \leftarrow S^{'}$ , $A \leftarrow A^{'}$

until $S$ is terminal

Q-Learning

On-policy TD Control Method를 Q-Learning이라 부른다. Q-Learning은 다음 업데이트 식을 이용해 행동-가치 함수(action-value function) $Q$ 를 업데이트한다.

Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ max_{a} Q (S_{t + 1}, a) - Q (S_{t}, A_{t})]

$S_{t}$ , $A_{t}$ , $R_{t + 1}$ , $S_{t + 1}$ , $A_{t + 1}$ 를 사용하는 SARSA 업데이트 식과는 다르게 Q-Learning의 업데이트 식은 $S_{t}$ , $A_{t}$ , $R_{t + 1}$ , $S_{t + 1}$ 만 사용한다. 이 업데이트 식을 적용하면 현재 정책이 무엇이든 $Q$ 는 항상 최적 행동-가치 함수 $q_{*}$ 으로 수렴하게 된다. 물론 이 수렴성을 보장하려면 (여느 Off-policy Control 방법에서처럼) 모든 상태-행동 쌍에 대해 $Q (S, A)$ 가 업데이트되어야 한다.

참고로 Q-Learning에서 Q는 Quality의 약자이다. Q-Learning은 현재 상태에서 어떤 행동을 하는 것이 가장 Quality가 좋은지를(= 가장 큰 행동-가치(action-value)를 가지는지 = 가장 높은 보상(reward) 기댓값을 가지는지) 계산하므로 이런 이름이 붙었다.

Pseudo Code : Q-Learning ( $ε$ -greedy Policy 사용)

모든 $s \in S^{+}$ , $a \in A (s)$ 에 대해, $Q (s, a) \in R$ 을 임의의 값으로 초기화. 단, $Q (terminal, \cdot) = 0$ .

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

Loop for each step of episode:

현재 $Q$ 에 대해 $ε$ -greedy Policy를 사용하여 $S$ 에서의 행동 $A$ 를 선택 // Improvement 과정

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

$Q (S, A) \leftarrow Q (S, A) + α [R + γ max_{a} Q (S^{'}, a) - Q (S, A)]$ // Evaluation 과정

$S \leftarrow S^{'}$

until $S$ is terminal

위 의사 코드를 보면, 목표 정책( $Q$ 를 이용한 Greedy Policy)과 행동 정책( $ε$ -greedy Policy)이 다르다. 따라서 Q-Learning은 Off-policy Method이다.

SARSA vs. Q-Learning

SARSA와 Q-Learning 중 어느 것이 더 좋을까? 다음 예제를 통해 알아보자.

Cliff Walking

Fig.05과 같은 게임판 위에서, 말은 다음과 같은 규칙으로 움직인다.

왼쪽 아래 S 칸에서 시작한다. 목표는 오른쪽 아래 G 칸에 도달하는 것이다.
각 칸에서는 위, 아래, 왼쪽, 오른쪽, 이렇게 4가지 방향으로 1칸씩 움직일 수 있다.
한 번 움직일 때마다 -1의 보상을 받는다. 단, 아래 Cliff 영역에 들어간 경우 (절벽에서 떨어진 것이므로) -100의 보상을 받고, (구조되어) 시작점(S)으로 즉시 이동한다. G에 도착하면 0의 보상을 받는다.
테두리 바깥으로 나가는 행동을 하면(ex. S에서 아래로 움직이려 하는 경우) 위치가 바뀌지 않고, 보상만 -1을 받는다.

위 문제에서 최적 정책을 SARSA와 Q-Learning을 통해 찾아보자.

Code : Random Walk

python

import numpy as np
import matplotlib.pyplot as plt
from abc import *

class Env:
    def __init__(self):
        self.state = None
        
    def _getStateIdx(self):
        return self.state[0] * 12 + self.state[1]
    
    def initEpisode(self):
        self.state = [0, 0]
        return True, self._getStateIdx(), 0  # status(False: episode complete, True: episode ongoing), state, reward
    
    def _is_on_cliff(self, state):
        if (state[0] == 0) and (1 <= state[1] <= 10):
            return True
        else:
            return False
        
    def interact(self, action):
        if action == 0: # up
            new_state = [self.state[0] + 1, self.state[1]]
        elif action == 1: # down
            new_state = [self.state[0] - 1, self.state[1]]
        elif action == 2: # left
            new_state = [self.state[0], self.state[1] - 1]
        elif action == 3: # right
            new_state = [self.state[0], self.state[1] + 1]
        else:
            raise Exception("Invalid param:action")
        
        if new_state == [0, 11]: # goal
            R = 0
            status = False
        elif self._is_on_cliff(new_state): # cliff
            R = -100
            status = True
            new_state = [0, 0]
        else:
            R = -1
            status = True
            
            # border
            if new_state[0] < 0:
                new_state[0] = 0
            elif new_state[0] > 3:
                new_state[0] = 3
            elif new_state[1] < 0:
                new_state[1] = 0
            elif new_state[1] > 11:
                new_state[1] = 11
                
        self.state = new_state
        return status, self._getStateIdx(), R  # status(False: episode complete, True: episode ongoing), state, reward

class Control(metaclass=ABCMeta):
    def __init__(self, env, alpha, epsilon=0.1, gamma=1):
        self.env = env
        self.Q = np.zeros((48, 4))
        self.alpha = alpha
        self.epsilon = epsilon
        self.gamma = gamma
    
    def initQ(self):
        self.Q = np.zeros((48, 4))
    
    def chooseAction(self, state, greedy=False): 
        if greedy: # greedy
            max_actions = np.argwhere(self.Q[state] == np.max(self.Q[state])).flatten()
            return np.random.choice(max_actions)
        else: # ε-greedy
            if np.random.random() < self.epsilon: # exploration
                return np.random.choice(4)
            else: # exploitation
                max_actions = np.argwhere(self.Q[state] == np.max(self.Q[state])).flatten()
                return np.random.choice(max_actions)
    
    def _getState(self, state_idx):
        return [state_idx // 12, state_idx % 12]
    
    def _getAction(self, action_idx):
        actions = ["up", "down", "left", "right"]
        return actions[action_idx]
    
    @abstractmethod
    def learn(self, episode_num):
        pass
    
    def test(self, verbose=False):
        result = []
        
        status, S, R = self.env.initEpisode()
        A = self.chooseAction(S, greedy=True)
        result.append(self._getState(S))
        result.append(self._getAction(A) if verbose else A)
        
        while True:
            status, S, R = self.env.interact(A)
            if not status:
                break
            
            A = self.chooseAction(S, greedy=True)
            
            result.append(R)
            result.append(self._getState(S))
            result.append(self._getAction(A) if verbose else A)
            
        result.append(R)
        result.append(self._getState(S))
        
        return result

class SARSA(Control):
    def learn(self, episode_num=1, is_from_scratch=False):
        if is_from_scratch:
            self.initQ()
        
        reward_sums = np.zeros(episode_num)
        for e in range(episode_num):
            reward_sum = 0
            
            status, S, R = self.env.initEpisode()
            A = self.chooseAction(S)
            reward_sum += R
            
            while status:
                status, S_, R = self.env.interact(A)
                
                A_ = self.chooseAction(S_)
                self.Q[S, A] = self.Q[S, A] + self.alpha * (R + self.gamma * self.Q[S_, A_] - self.Q[S, A])
                
                S = S_
                A = A_
                reward_sum += R
            
            reward_sums[e] = reward_sum
                
        return reward_sums

class QLearning(Control):
    def learn(self, episode_num=1, is_from_scratch=False):
        if is_from_scratch:
            self.initQ()
        
        reward_sums = np.zeros(episode_num)
        for e in range(episode_num):
            reward_sum = 0
            
            status, S, R = self.env.initEpisode()
            reward_sum += R
            
            while status:
                A = self.chooseAction(S)
                status, S_, R = self.env.interact(A)
                reward_sum += R
                
                self.Q[S, A] = self.Q[S, A] + self.alpha * (R + self.gamma * np.max(self.Q[S_]) - self.Q[S, A])
                
                S = S_
                
            reward_sums[e] = reward_sum
                
        return reward_sums
    
def drawEpisode(episode, title):
    board = [[" " for x in range(12)] for x in range(4)]
    arrows = ["↑", "↓", "←", "→"]
    
    idx = 0
    reward_sum = 0
    
    S = episode[idx]
    A = episode[idx + 1]
    board[S[0]][S[1]] = arrows[A]
    idx += 2
    
    while True:
        if idx + 2 >= len(episode):
            break
        
        R = episode[idx]
        S = episode[idx + 1]
        A = episode[idx + 2]
        idx += 3
        
        reward_sum += R
        board[S[0]][S[1]] = arrows[A]
    
    R = episode[idx]
    S = episode[idx + 1]
    reward_sum += R
    board[S[0]][S[1]] = "●"
    
    print(f"{title} [rewards = {reward_sum}]")
    for i in reversed(range(len(board))):
        print("|", end="")
        for j in range(len(board[i])):
            print(board[i][j], end="|")
        print()
    print()

def drawGraph(sarsa_reward_sums, qlearning_reward_sums):
    plt.plot(range(500), sarsa_reward_sums, label="SARSA", c="r")
    plt.plot(range(500), qlearning_reward_sums, label="QLearning", c="b")
    
    plt.title("Sum of rewards")
    plt.legend()
    plt.xlabel("Episodes")
    plt.ylabel("Sum of rewards")
    plt.xticks([0, 100, 200, 300, 400, 500])
    plt.ylim(-100, 0)
    plt.show()

if __name__ == "__main__":
    env = Env()

    sarsa = SARSA(env, alpha=0.1)
    sarsa_reward_sums = np.mean([sarsa.learn(episode_num=500, is_from_scratch=True) for x in range(100)], axis=0)
    drawEpisode(sarsa.test(), "SARSA")

    qlearning = QLearning(env, alpha=0.1)
    qlearning_reward_sums = np.mean([qlearning.learn(episode_num=500, is_from_scratch=True) for x in range(100)], axis=0)
    drawEpisode(qlearning.test(), "QLearning")

    drawGraph(sarsa_reward_sums, qlearning_reward_sums)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

코드 설명

line 5 ~ 56 : Env 클래스
- line 9 ~ 10 : Env._getStateIdx() 메소드
  - [x, y] 꼴의 상태를 하나의 숫자(idx)로 변환하는 메소드
- line 12 ~ 14 : Env.initEpisode() 메소드
  - 에피소드를 시작하는 메소드. 말을 S 위치로 옮긴다.
  - status, state, reward를 반환한다.
    - status : 현재 에피소드 진행 상태를 나타낸다. True면 에피소드가 진행 중임을(terminal state에 도달하지 못했음을), False면 에피소드가 종료되었음을(terminal state)에 도달했음을 나타낸다.
    - state : 현재 말이 있는 위치를 나타낸다. 하나의 숫자이다(Env._getStateIdx() 사용).
    - reward : 0
- line 16 ~ 20 : Env._is_on_cliff() 메소드
  - 전달받은 state가 cliff인지 아닌지를 판단한다.
  - cliff가 맞으면 True, cliff가 아니면 False를 반환한다.
- line 22 ~ 56 : Env.interact() 메소드
  - 전달받은 action을 수행하고 그 결과를 반환하는 메소드
  - status, state, reward를 반환한다.
    - status : 현재 에피소드 진행 상태를 나타낸다. True면 에피소드가 진행 중임을(terminal state에 도달하지 못했음을), False면 에피소드가 종료되었음을(terminal state)에 도달했음을 나타낸다.
    - state : 현재 말이 있는 위치를 나타낸다. 하나의 숫자이다(Env._getStateIdx() 사용).
    - reward : action을 수행하고 받은 보상을 나타낸다.
line 58 ~ 113 : Control 클래스
- line 59 ~ 64 : Control.__init__() 메소드
  - 클래스 생성자. 각종 변수들을 초기화한다.
- line 66 ~ 67 : Control.initQ() 메소드
  - Q를 초기화한다.
- line 69 ~ 78 : Control.chooseAction() 메소드
  - 현재 상태 state를 입력받아, $ε$ -greedy Policy로 다음 행동을 선택하는 메소드
  - greedy 매개변수에 True를 주면 Greedy Policy로 동작한다(즉, 탐색(exploration)을 안한다).
- line 80 ~ 81 : Control._getState() 메소드
  - (Env._getStateIdx() 메소드로 인해) 하나의 숫자로 된 상태를 [x, y] 꼴로 바꾼다.
- line 83 ~ 85 : Control._getAction() 메소드
  - 0, 1, 2, 3 형태로 되어 있는 행동을 각각 "up", "down", "left", "right" 꼴로 바꾼다.
- line 88 ~ 89 : Control.learn() 추상 메소드
- line 91 ~ 113 : Control.test() 메소드
  - 현재 (Control.learn() 메소드로) 학습된 Q에 따라 Greedy Policy로 에피소드를 생성하는 메소드
  - verbose 매개변수에 True가 주어지면 행동에 "up", "down", "left", "right"가 들어가고, verbose에 False가 주어지면 0, 1, 2, 3이 들어간다. 아무 값도 주지 않으면 기본값으로 False가 사용된다.
line 115 ~ 140 : SARSA 클래스
- line 116 ~ 140 : SARSA.learn() 메소드
  - SARSA로 학습을 진행하는 메소드
  - episode_num개의 에피소드를 이용해 학습을 진행한다.
  - is_from_scratch 매개변수에 True를 주면 Q를 초기화하고 처음부터 학습을 진행한다. 기본값은 False이다(즉, 현재 Q 값을 초기화하지 않고 계속해서 학습을 이어나간다).
  - 각 에피소드에서 받은 총 보상들의 배열을 반환한다.
line 142 ~ 165 : QLearning 클래스
- line 143 ~ 140 : QLearning.learn() 메소드
  - QLearning으로 학습을 진행하는 메소드
  - episode_num개의 에피소드를 이용해 학습을 진행한다.
  - is_from_scratch 매개변수에 True를 주면 Q를 초기화하고 처음부터 학습을 진행한다. 기본값은 False이다(즉, 현재 Q 값을 초기화하지 않고 계속해서 학습을 이어나간다).
  - 각 에피소드에서 받은 총 보상들의 배열을 반환한다.
line 167 ~ 202 : drawEpisode() 함수
- (Control.test()로 생성된) episode를 받아 이를 그림(Fig.06)으로 그려주는 함수
line 204 ~ 214 : drawGraph() 함수
- (SARSA.learn()과 QLearning.learn()으로 생성된) 에피소드별 보상들의 배열을 그래프(Fig.07)로 그려주는 함수
line 216 ~ 227 : main
- line 220 : sarsa_reward_sums는 500개의 에피소드를 이용해 SARSA로 학습하는 과정을 100번 반복해 얻은, 100개의 에피소드별 보상들의 배열들을 평균해 구한다.
- line 224 : qlearning_reward_sums는 500개의 에피소드를 이용해 Q-Learning로 학습하는 과정을 100번 반복해 얻은, 100개의 에피소드별 보상들의 배열을 평균해 구한다.

Fig.06 Cliff Walking - 학습 결과
500개의 에피소드를 이용해 SARSA와 Q-Learning로 학습한 결과

Fig.07 Cliff Walking - 각 에피소드에서 받은 보상의 합
500개의 에피소드를 이용해 SARSA와 Q-Learning로 학습하는 과정을 100번 반복해 얻은, 100개의 에피소드별 보상의 배열들의 평균을 그래프로 나타내었다. 빨간 색은 SARSA를, 파란 색은 Q-Learning을 의미한다.

Fig.06에서 볼 수 있듯이, Q-Learning으로 구한 정책은 절벽(cliff)에 딱 붙어서 가는, 최적 정책(optimal policy)이다. 그러나 학습 과정에서 행동 정책( $ε$ -greedy Policy)으로 다음 행동을 결정하면 간간히 절벽으로 떨어질 수 있다. 반면 목표 정책과 행동 정책이 같은 SARSA로 구한 정책은 절벽에서 한 칸 떨어진, (최적 정책은 아니지만) 조금 더 '안전한' 정책이다. 이렇게 보면 Q-Learning이 최적 정책을 찾았으므로 조금 더 좋아 보이겠지만, Fig.07을 보면 학습 중 성능(online performance)은 SARSA(빨간 색)가 Q-Learning(파란 색)보다 더 낫다는 것을 볼 수 있다. SARSA는 Q-Learning에 비해 조금 더 안전한 방향으로 학습이 진행되므로, 학습 과정에서 절벽에 떨어지는 경우가 적어 학습 중 성능이 더 잘 나온 것이다.

참고로 만약 $ε$ 이 시간이 지남에 따라 점점 줄어든다면,^[11] SARSA와 Q-Learning 둘 다 (Q-Learning으로 구한 것과 같은) 최적 정책으로 수렴하게 된다.

Expected SARSA

Q-Learning의 업데이트 식에서, 다음 상태 $S_{t + 1}$ 에서의 모든 가치 중 최대값( $max_{a} Q (S_{t + 1}, a)$ )을 사용하는 대신, 다음 상태 $S_{t + 1}$ 에서 현재 정책 $π$ 을 따를 때 받을 수 있는 가치들의 기댓값( $E_{π} [Q (S_{t + 1}, A_{t + 1}) ∥ S_{t + 1}]$ )을 사용하는 다음 업데이트 식을 생각해보자.

\begin{aligned} Q (S_{t}, A_{t}) & \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ E_{π} [Q (S_{t + 1}, A_{t + 1}) | S_{t + 1}] - Q (S_{t}, A_{t})] \\ \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ \sum_{a} π (a | S_{t + 1}) Q (S_{t + 1}, a) - Q (S_{t}, A_{t})] \end{aligned}

이 업데이트 식은 SARSA가 $Q$ 를 움직일 것으로 기대(expectation)되는 방향으로 $Q$ 를 움직인다. 그래서 이 업데이트 식을 사용하고, 나머지 부분에서는 Q-Learning과 동일한 방식으로 하는 Control 방법을 Expected SARSA라 한다.

Pseudo Code : Expected SARSA ( $ε$ -greedy Policy 사용)

모든 $s \in S^{+}$ , $a \in A (s)$ 에 대해, $Q (s, a) \in R$ 을 임의의 값으로 초기화. 단, $Q (terminal, \cdot) = 0$ .

$π$ : $ε$ -greedy Policy

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

Loop for each step of episode:

현재 $Q$ 에 대해 $π$ 를 사용하여 $S$ 에서의 행동 $A$ 를 선택

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

$Q (S, A) \leftarrow Q (S, A) + α [R + γ \sum_{a} π (a ∥ S^{'}) \cdot Q (S^{'}, a) - Q (S, A)]$

$S \leftarrow S^{'}$

until $S$ is terminal

Expected SARSA는 (당연히) SARSA보다 계산의 복잡도가 높지만, SARSA에서 무작위^[12]로 다음 동작 $A_{t + 1}$ 을 뽑음으로 인해 발생하는 분산(variance)이 없다. 따라서 같은 양의 경험(experience)으로 학습을 시켜보면 대부분의 경우 Expected SARSA가 SARSA보다 성능이 좋다. 특히 Expected SARSA는 SARSA와 다르게 큰 $α$ 를 사용해도 최적 정책 및 최적 가치 함수로 수렴시킬 수 있다. 위 Cliff Walking 예제를 예를 들면, 각 상태에서의 행동은 결정론적이므로(deterministically)^[13] 이 예제에서의 무작위성은 오직 정책에서만 나온다. 따라서 Cliff Walking에서는 $α = 1$ 로 놓고 Expected SARSA를 적용해도 아무런 문제가 없다.^[14]

위에서 설명한 Expected SARSA는 목표 정책과 행동 정책이 같은 On-policy Method였지만, 사실 Expected SARSA는 목표 정책과 행동 정책을 다르게 해 Off-policy Method로 사용할 수도 있다. 예를 들어 $π$ 를 Greedy Policy로 설정하고, 현재 상태 $S$ 에서 다음 행동 $A$ 를 만들어내는 행동 정책으로 적당히 탐색적인(exploratory) 정책을 사용하면(ex. $ε$ -greedy Policy) Expected SARSA는 Q-Learning과 완벽히 동일해진다. 이 관점에서 보면 Expected SARSA는 Q-Learning을 포함한다고 할 수 있다. 약간의 추가적인 계산 비용을 감수할 수만 있다면, Expected SARSA는 TD Control 방법들 중 가장 우수한 방법이다.

최대화 편향 (Maximization Bias)

다음 확률론적인(stochastic) MDP 문제를 보자.

Fig.08 Maximization Bias Example
상태 A에서 에피소드가 시작된다.
상태 A에서는 left 또는 right 두 가지 행동을 할 수 있다.
상태 A에서 right를 하면 보상 0을 받고 종료 상태(terminal state)로 전이한다(= 에피소드가 종료된다).
상태 A에서 left를 하면 보상 0을 받고 상태 B로 전이한다.
상태 B에서는 여러 가지 행동을 할 수 있다. 어떠한 행동을 하던 종료 상태로 전이하고(= 에피소드가 종료되고) 평균 -0.1, 분산 1의 정규분포 $N (- 0.1, 1)$ 에서 무작위로 추출한 보상을 받는다.

Q-Learning을 이용해 이 문제를 풀면 Fig.09와 같은 그래프를 얻을 수 있다( $α = 0.1$ , $γ = 1$ , $ε = 0.1$ , 상태 B에서 가능한 행동의 개수 : 15개).

Code : Maximization Bias Example

python

import numpy as np
import matplotlib.pyplot as plt
from abc import *

class Env:
    def __init__(self, b_actions_num=15):
        self.state_names = ["A", "B", "T"]
        self.action_nums = [2, b_actions_num, 1]
        self.state = None
        
    def initEpisode(self):
        self.state = 0
        return True, self.state, 0
    
    def interact(self, action):
        assert action in range(self.action_nums[self.state]), "Invalid param:action"
        
        if self.state == 0: # A
            if action == 0: # left
                self.state = 1
                return True, self.state, 0
            elif action == 1: # right
                self.state = 2
                return False, self.state, 0
        else: # B
            self.state = 2
            return False, self.state, np.random.normal(loc=-0.1, scale=1.0)

class Control(metaclass=ABCMeta):
    def __init__(self, env, alpha=0.1, epsilon=0.1, gamma=1):
        self.env = env
        self.alpha = alpha
        self.epsilon = epsilon
        self.gamma = gamma
    
    def chooseAction(self, Q, state, greedy=False):
        if greedy: # greedy
            max_actions = np.argwhere(Q[state] == np.max(Q[state])).flatten()
            return np.random.choice(max_actions)
        else: # ε-greedy
            if np.random.random() < self.epsilon: # exploration
                return np.random.choice(self.env.action_nums[state])
            else: # exploitation
                max_actions = np.argwhere(Q[state] == np.max(Q[state])).flatten()
                return np.random.choice(max_actions)
    
    @abstractmethod
    def learn(self, episode_num):
        pass
    
    def _getInitQ(self):
        return [np.zeros(self.env.action_nums[state]) for state in range(len(self.env.state_names))]
            
class QLearning(Control):
    def __init__(self, env, alpha=0.1, epsilon=0.1, gamma=1):
        super().__init__(env, alpha, epsilon, gamma)
        self.Q = self._getInitQ()
        
    def learn(self, episode_num=1, is_from_scratch=False):
        if is_from_scratch:
            self.Q = self._getInitQ()
            
        left_actions = np.zeros(episode_num)
        for e in range(episode_num):
            status, S, R = self.env.initEpisode()
            
            while status:
                A = self.chooseAction(self.Q, S)
                if S == 0 and A == 0:
                    left_actions[e] = 1
                    
                status, S_, R = self.env.interact(A)
                
                self.Q[S][A] = self.Q[S][A] + self.alpha * (R + self.gamma * np.max(self.Q[S_]) - self.Q[S][A])
                
                S = S_
        
        return left_actions
    
class DoubleQLearning(Control):
    def __init__(self, env, alpha=0.1, epsilon=0.1, gamma=1):
        super().__init__(env, alpha, epsilon, gamma)
        self.Q1 = self._getInitQ()
        self.Q2 = self._getInitQ()
        
    def _getQ(self):
        return [(self.Q1[state] + self.Q2[state]) for state in range(len(self.env.state_names))]
    
    def _argmax(self, array):
        candidates = np.argwhere(array == np.max(array)).flatten()
        return np.random.choice(candidates)
        
    def learn(self, episode_num=1, is_from_scratch=False):
        if is_from_scratch:
            self.Q1 = self._getInitQ()
            self.Q2 = self._getInitQ()
            
        left_actions = np.zeros(episode_num)
        for e in range(episode_num):
            status, S, R = self.env.initEpisode()
            
            while status:
                A = self.chooseAction(self._getQ(), S)
                if S == 0 and A == 0:
                    left_actions[e] = 1
                    
                status, S_, R = self.env.interact(A)
                
                if np.random.random() < 0.5:
                    self.Q1[S][A] = self.Q1[S][A] + self.alpha * (R + self.gamma * self.Q2[S_][self._argmax(self.Q1[S_])] - self.Q1[S][A])
                else:
                    self.Q2[S][A] = self.Q2[S][A] + self.alpha * (R + self.gamma * self.Q1[S_][self._argmax(self.Q2[S_])] - self.Q2[S][A])
                    
                S = S_
        
        return left_actions
    
def drawGraph(qlearning_result, doubleqlearning_result):
    plt.plot(range(len(qlearning_result)), qlearning_result, label="Q-Learning")
    plt.plot(range(len(doubleqlearning_result)), doubleqlearning_result, label="Double Q-Learning")
    plt.axhline(y=0.05, c='k', linestyle="--", linewidth=0.5)
    plt.axhline(y=0.95, c='k', linestyle="--", linewidth=0.5)
    
    plt.title("Maximization Bias Example")
    plt.xlabel("Episodes")
    plt.ylabel("left actions from A")
    plt.xticks([1, 100, 200, 300])
    plt.yticks([0.05, 0.25, 0.5, 0.75, 0.95, 1], ["5%", "25%", "50%", "75%", "95%", "100%"])
    plt.legend()
    plt.show()
    
if __name__ == "__main__":
    env = Env()
    qlearning = QLearning(env)
    doubleqlearning = DoubleQLearning(env)
    
    qlearning_result = np.mean([qlearning.learn(episode_num=300, is_from_scratch=True) for x in range(10000)], axis=0)
    doubleqlearning_result = np.mean([doubleqlearning.learn(episode_num=300, is_from_scratch=True) for x in range(10000)], axis=0)
    drawGraph(qlearning_result, doubleqlearning_result)

코드 설명

line 5 ~ 27 : Env 클래스
- line 6 ~ 9 : Env.__init__() 메소드
  - b_action_nums : 상태 B에서 가능한 행동들의 개수
- line 11 ~ 13 : Env.initEpisode() 메소드
  - 에피소드를 시작하는 메소드
- line 15 ~ 27 : Env.interact() 메소드
  - 에이전트와 상호작용하는 메소드
  - B를 선택한 경우 $N (- 0.1, 1)$ 의 정규분포에서 무작위로 추출한 보상을 받는다.
line 29 ~ 52 : Control 클래스
- QLearning 클래스와 DoubleQLearning 클래스의 부모 클래스
- line 36 ~ 45 : Control.chooseAction() 메소드
  - 인자로 받은 Q에 따라, 상태 state에서 $ε$ -greedy Policy로 뽑은 행동을 반환
  - greedy 인자에 True가 오면 Greedy Policy로 동작
- line 51 ~ 52 : Control._getInitQ() 메소드
  - QLearning 클래스, DoubleQLearning 클래스가 사용하는 행동-가치 함수(action-value function)를 초기화하는 메소드
line 54 ~ 78 : QLearning 클래스
- 위 Cliff Walking에서의 클래스와 거의 동일하다.
- line 59 ~ 78 : QLearning.learn() 메소드
  - 각 에피소드마다 상태 A에서 left를 선택했는지 안 했는지를 담은 배열 left_actions를 반환
    - ex. 3개의 에피소드를 살펴볼 때(= episode_num=3), 첫 번째 에피소드에서는 상태 A에서 left를, 두 번째 에피소드에서는 right를, 마지막 에피소드에서는 left를 선택해 수행했다면 [1, 0, 1]을 반환
    - 이 반환값은 drawGraph() 함수에서 사용됨
line 80 ~ 116 : DoubleQLearning 클래스
- line 89 ~ 91 : DoubleQLearning._argmax() 메소드
  - 인자로 주어진 1차원 배열 array에서, 최대값의 인덱스를 반환
  - 만약 최대값이 여러 개 있다면 그 중 랜덤한 인덱스를 반환
- line 93 ~ 116 : DoubleQLearning.learn() 메소드
  - 각 에피소드마다 상태 A에서 left를 선택했는지 안 했는지를 담은 배열 left_actions를 반환
    - ex. 3개의 에피소드를 살펴볼 때(= episode_num=3), 첫 번째 에피소드에서는 상태 A에서 left를, 두 번째 에피소드에서는 right를, 마지막 에피소드에서는 left를 선택해 수행했다면 [1, 0, 1]을 반환
    - 이 반환값은 drawGraph() 함수에서 사용됨
line 118 ~ 130 : drawGraph() 함수
- Fig.09의 그래프를 그리는 함수
- x축은 살펴본 에피소드의 개수를, y축은 10,000개의 에이전트 중 left 행동을 수행한 에이전트의 비율을 나타낸다.
- 점선은 left 또는 right가 $ε$ -greedy Policy 하에서 최대로 실행될 수 있는 빈도인 5%와 95%를 나타내고 있다.
line 132 ~ 139 : main
- line 137, 138 : 10,000개의 에이전트를 각각 300개의 에피소드로 학습을 시키고, 학습 과정에서 left 행동이 어떤 비율로 수행되었는지를 계산

Fig.09 Maximization Bias Example - 학습 결과
x축은 살펴본 에피소드 개수를, y축은 10,000개의 에이전트 중 `left` 행동을 수행한 에이전트의 비율을 나타낸다. 점선은 `left` 또는 `right`가 $ε$ -greedy Policy 하에서 최대로 실행될 수 있는 빈도인 5%와 95%를 나타내고 있다.

상태 A에서 left를 수행했을 때의 Return의 기댓값은 -0.1이고 right를 수행했을 때의 기댓값은 0이므로, 최적 정책은 A에서 right를 선택해야 한다. 그러나 Fig.09에서 볼 수 있듯이 학습 초기에 Q-Learning(파란색 그래프)은 오히려 left를 더 많이 하는 방향으로 학습되는 것을 볼 수 있다. 왜 이런 일이 발생했을까?

Q-Learning의 업데이트 식을 살펴보자.

Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ max_{a} Q (S_{t + 1}, a) - Q (S_{t}, A_{t})]

위 식에서, 빨간색 테두리 영역의 정확도가 높아질수록 $Q (S_{t}, A_{t})$ 추정의 정확도도 같이 높아진다. 이때 빨간색 테두리 영역의 참값은 실제 가치 함수 $q$ 를 사용한, $max_{a} q (S_{t + 1}, a)$ 이다. 즉 빨간색 테두리 영역에는 $max_{a} q (S_{t + 1}, a)$ , 또는 하다못해 $max_{a} q (S_{t + 1}, a)$ 전체에 대한 추정값이 들어가는 것이 좋다. 그러나 우리는 $q$ 도 모르고 $max_{a} q (S_{t + 1}, a)$ 의 추정값도 모르기에, 그 대신 가치의 추정값( $Q$ )들에 대한 최대값 $max_{a} Q (S_{t + 1}, a)$ 를 사용했다. 다시말해 "가치들의 최대값에 대한 추정값(estimate of the maximum value)"을 써야할 때 그 대신 "가치의 추정값들에 대한 최대값(maximum over estimated values)"을 사용한 것이다.

어떤 상태에서 행동들을 했을 때 정규분포 $N (μ, σ^{2})$ 에 따른 보상을 받는다는 말은, 원래 받을 보상은 $μ$ 이지만 환경의 불확실성(uncertainty) 때문에 $σ^{2}$ 만큼의 분산(variance)이 생긴다는 말이다. 위 예제로 다시 돌아가보자. 상태 B에서 행동을 수행하면 정규분포 $N (- 0.1, 1)$ 에서 무작위로 추출한 보상(= 가치)을 받는다는 말은, 상태 B에서 가능한 모든 행동 $a \in A (B)$ 에 대해 $q (B, a) = - 0.1$ 이라는 뜻이다. 따라서 $max_{a} q (S_{t + 1}, a) = - 0.1$ 이 된다.

하지만 Q-Learning 업데이트 식에서는 $max_{a} q (S_{t + 1}, a)$ 대신 $max_{a} Q (S_{t + 1}, a)$ 를 쓴다. 정규분포 $N (μ, σ^{2})$ 을 따르는 보상은 몇몇은 양수일 것이고, 몇몇은 음수일 것이다.^[15] 이 때문에 몇몇 행동들의 $Q (B, a)$ 는 양수가 될 것이고, 몇몇 행동들의 $Q (B, a)$ 는 음수가 될 것이다. 따라서 이들에 대해 $max_{a} Q (S_{t + 1}, a)$ 를 계산하면 (-0.1이 아닌) 양수가 나온다. 즉, 편향(bias)이 발생한 것이다. 그리고 이 편향은 left 행동이 right 행동보다 더 좋다고 에이전트가 '착각'하게 만든다.

이런 식으로 최대값 연산을 할 때 "가치들의 최대값에 대한 추정값" 대신 "가치의 추정값들에 대한 최대값"을 사용하여 발생하는 편향을 최대화 편향(Maximiaztion Bias) 이라 한다. 우리가 이때까지 살펴본 TD Control 기법들에는 모두 최대값을 계산하는 부분이 있었다.^[16] 따라서 이 모든 기법들에는 다 최대화 편향이 존재한다.

최대화 편향은 결정론적인 환경(deterministic environment)에서는 큰 문제가 되지 않는다. 하지만 위 예제와 같은 확률론적인 환경(stochastic environment)에서는 학습 속도와 성능에 부정적인 영향을 끼칠 수 있다. 실제로 Fig.09에서 볼 수 있듯이, Q-Learning으로 학습시킨 에이전트(파란색)는 학습 초기에 left를 더 많이 수행한다. 그리고 학습이 진행되며 left의 가치가 점점 더 정확히 추정되고 나서야 left의 선택 비율은 줄어든다.

Double Learning

그러면 어떻게 하면 최대화 편향을 피할 수 있을까? 최대화 편향은 사실 TD Method의 Bootstrapping 과정에서 최적 행동( $A^{*}$ )을 결정하는 과정과 해당 최적 행동의 가치를 추정하는 과정에서 같은 샘플(에피소드)을 사용하기 때문에 발생한다. 그러므로 이 두 과정에서 다른 데이터를 사용하면 최대화 편향을 피할 수 있다.

이를 위한 한 가지 방법이 Double Learning이다. Double Learning은 아이디어는 두 개의 행동-가치 함수(action-value function) $Q_{1}$ , $Q_{2}$ 를 사용하는 것이다. 특정 상태 $S$ 에서의 최적 행동 $A^{*}$ 을 결정할 때는 둘 중 한 정책( $Q_{1}$ 이라 하자)을 결정하고,^[17] 결정된 최적 행동의 가치를 계산할 때는 다른 정책( $Q_{2}$ )를 이용한다.^[18]

학습을 진행하면서 $Q_{1}$ 과 $Q_{2}$ 의 역할을 무작위로 계속 바꿔가며 학습하면^[19] $Q_{1}$ 과 $Q_{2}$ 모두 참값 $q$ 로 수렴하게 만들면서도 최대화 편향을 피할 수 있게 된다. Double Learning은 두 개의 행동-가치 함수를 사용하므로 메모리 사용량이 2배로 늘어난다는 단점이 있지만, 에피소드 하나에 대해 하나의 행동-가치 함수만 학습되므로 (최대화 편향을 없애면서도) 학습 시간이 증가하지는 않는다는 장점이 있다.

Double Q-Learning

Q-Learning에 Double Learning의 아이디어를 결합하면 Double Q-Learning을 만들 수 있다.

Pseudo Code : Double Q-Learning

모든 $s \in S^{+}$ , $a \in A (s)$ 에 대해, $Q_{1} (s, a) \in R$ , $Q_{2} (s, a) \in R$ 을 임의의 값으로 초기화. 단, $Q_{i} (terminal, \cdot) = 0$ ( $i = 1, 2$ ).

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

Loop for each step of episode:

$Q_{1} + Q_{2}$ 에 대해 $ε$ -greedy Policy를 사용하여 $S$ 에서의 행동 $A$ 를 선택// Improvement 과정

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

// Evaluation 과정

50% 확률로:

$Q_{1} (S, A) \leftarrow Q_{1} (S, A) + α [R + γ Q_{2} (S^{'}, \underset{a}{\arg \max} Q_{1} (S^{'}, a)) - Q_{1} (S, A)]$

나머지 50% 확률로:

$Q_{2} (S, A) \leftarrow Q_{2} (S, A) + α [R + γ Q_{1} (S^{'}, \underset{a}{\arg \max} Q_{2} (S^{'}, a)) - Q_{2} (S, A)]$

$S \leftarrow S^{'}$

until $S$ is terminal

Fig.09에서 주황색 그래프가 Double Q-Learning을 적용했을 때의 그래프이다. 그래프에서 볼 수 있듯이 최대화 편향이 생기지 않고 정상적으로(= left를 선택하지 않는 방향으로) 학습이 진행되는 것을 볼 수 있다.

Double SARSA

SARSA에 Double Learning의 아이디어를 결합하면 Double SARSA를 만들 수 있다.

Pseudo Code : Double SARSA ( $ε$ -greedy Policy 사용)

모든 $s \in S^{+}$ , $a \in A (s)$ 에 대해, $Q_{1} (s, a) \in R$ , $Q_{2} (s, a) \in R$ 을 임의의 값으로 초기화. 단, $Q_{i} (terminal, \cdot) = 0$ ( $i = 1, 2$ ).

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

$Q_{1} + Q_{2}$ 에 대해 $ε$ -greedy Policy를 사용하여 $S$ 에서의 행동 $A$ 를 선택

Loop for each step of episode:

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

$Q_{1} + Q_{2}$ 에 대해 $ε$ -greedy Policy를 사용하여 $S^{'}$ 에서의 행동 $A^{'}$ 를 선택// Improvement 과정

// Evaluation 과정

50% 확률로:

$Q_{1} (S, A) \leftarrow Q_{1} (S, A) + α [R + γ Q_{2} (S^{'}, A^{'}) - Q_{1} (S, A)]$

나머지 50% 확률로:

$Q_{2} (S, A) \leftarrow Q_{2} (S, A) + α [R + γ Q_{1} (S^{'}, A^{'}) - Q_{2} (S, A)]$

$S \leftarrow S^{'}$ , $A \leftarrow A^{'}$

until $S$ is terminal

Double Expected SARSA

Expected SARSA에 Double Learning의 아이디어를 결합하면 Double Expected SARSA를 만들 수 있다.

Pseudo Code : Double Expected SARSA ( $ε$ -greedy Policy 사용)

모든 $s \in S^{+}$ , $a \in A (s)$ 에 대해, $Q_{1} (s, a) \in R$ , $Q_{2} (s, a) \in R$ 을 임의의 값으로 초기화. 단, $Q_{i} (terminal, \cdot) = 0$ ( $i = 1, 2$ ).

Loop for each episode:

$S$ 를 임의의 상태 $s \in S^{+}$ 으로 초기화

$Q_{1} + Q_{2}$ 에 대해 $ε$ -greedy Policy를 사용하여 $S$ 에서의 행동 $A$ 를 선택

Loop for each step of episode:

$A$ 시행하고, 보상 $R$ 과 다음 상태 $S^{'}$ 관측

$Q_{1} + Q_{2}$ 에 대해 $ε$ -greedy Policy를 사용하여 $S^{'}$ 에서의 행동 $A^{'}$ 를 선택// Improvement 과정

// Evaluation 과정

50% 확률로:

$Q_{1} (S, A) \leftarrow Q_{1} (S, A) + α [R + γ \sum_{a} π (a ∥ S^{'}) \cdot Q_{2} (S^{'}, a) - Q_{1} (S, A)]$

나머지 50% 확률로:

$Q_{2} (S, A) \leftarrow Q_{2} (S, A) + α [R + γ \sum_{a} π (a ∥ S^{'}) \cdot Q_{1} (S^{'}, a) - Q_{2} (S, A)]$

$S \leftarrow S^{'}$

until $S$ is terminal

여담 : 다음-상태-가치 함수(afterstate value function)

이전 글에서 살펴봤던 tic-tac-toe 게임을 다시 생각해 보자. 우리가 이때까지 보았던 TD Control 기법들은 모두 행동-가치 함수(action-value function)을 사용했었다. 그런데 이전 글에서 tic-tac-toe 게임의 인공지능을 만드는 방법을 간략히 설명할 때는 마치 상태-가치 함수(state-value function)을 쓰는 것처럼 설명했었다.

사실 tic-tac-toe 게임을 만들 때 쓰는 가치 함수는 그냥 상태-가치 함수가 아닌, 다음-상태-가치 함수(afterstate value function)라 불리는 가치 함수이다. 이 가치 함수는 에이전트가 행동을 수행해 전이되는 '다음 상태(afterstate)'의 가치를 반환하는 함수이다. 잘 생각해 보면, tic-tac-toe 게임에서는 다른 상태에서 다른 행동을 하더라도 같은 상태로 전이할 수 있다.

Fig.10 Tic-tac-toe
tic-tac-toe 게임에서는 다른 상태에서 다른 행동을 해도 동일한 '다음 상태(afterstate)'로 전이할 수 있다.

이런 tic-tac-toe 게임을 행동-가치 함수를 이용해 푼다면 (물론 못 풀 것은 없지만) 쓸데없이 메모리를 많이 사용하게 되고 또 학습 속도가 아주 느려진다. 하지만 다음-상태-가치 함수를 사용하면 아주 효율적인 학습이 가능하다.

이처럼 다음-상태-가치 함수는 tic-tac-toe 게임과 같이 에이전트의 행동으로 전이할 다음 상태를 확실히 아는 결정론적인 환경(deterministic environment)에서 유용하다. 그렇다고 환경에 대한 전체 정보(ex. 전체 dynamics function)를 알아야만 다음-상태-가치 함수를 쓸 수 있는건 아니다(당장 tic-tac-toe 게임만 해도 상대방의 다음 행동이 무엇일지는 모른다). 다음-상태-가치 함수는 게임 이외에도 순서 정하기 문제(queing tasks) 등에서도 쓸 수 있다.

이를 Constant- $α$ MC Method라 한다. ↩︎
이를 bootstrapping이라 한다. ↩︎
정확히는, TD(0) Method에서는 ↩︎
예를 들어 MC Method에서는 한 에피소드가 끝나야 $V$ 를 업데이트하므로, 한 에피소드 동안 $V$ 가 바뀌지 않는다. ↩︎
행동(action)이 없는 MDP 문제를 MRP(Markov Reward Process)라 한다. Prediction 문제에서는 행동을 결정할 필요가 없으므로, 논의를 단순하게 하기 위해 MRP 문제를 많이 사용한다. ↩︎
단, $α$ 가 상수이기 때문에 두 방법 모두 완벽히 참값에 수렴하지는 않는다. $α$ 로 상수를 사용하는 경우 가장 최근에 관측한 에피소드의 결과에 따라 추정값이 계속 요동친다. ↩︎
TD(0) Prediction의 RMS Error(실선)가 MC Prediction의 RMS Error(점선)보다 항상 작다(= 아래에 있다). ↩︎
학습을 위한 정책(목표 정책, target policy)과 탐색을 위한 정책(행동 정책, behavior policy)이 동일한 학습법 ↩︎
학습을 위한 정책(목표 정책, target policy)과 탐색을 위한 정책(행동 정책, behavior policy)이 다른 학습법 ↩︎
ex) $ε$ -greedy Policy에서 $ε = 1 / t$ 인 경우. 초반엔 $ε$ 이 크므로 탐색(exploration)이 많이 일어나 모든 상태-행동 쌍이 충분히 방문되고, 시간이 지나며 정책이 Greedy Policy로 수렴한다. ↩︎
위 코드에서는 $ε$ 으로 상수(0.1)를 사용했다. ↩︎
$ε$ -greedy Policy에서 $ε$ -case인 경우 ↩︎
예를 들어, (2, 3) 칸에서 "up" 행동을 하면 무조건 (3, 3) 칸으로 이동한다. 결정론적인 행동의 반댓말은 확률론적(stochastic)인 행동이다. 확률론적인 행동의 예는 (2, 3) 칸에서 "up"을 했을 때 70% 확률로 (3, 3) 칸, 30%의 확률로 (2, 2) 칸으로 이동하는 행동 등이 있다. ↩︎
반면 SARSA의 경우 작은 $α$ 를 사용해야 하므로, 많은 수의 경험으로 오랜 시간 학습시켜야 한다. ↩︎
전체적인 평균은 당연히 -0.1일 것이다. ↩︎
SARSA, Expected SARSA에서는 $ε$ -greedy Policy를 많이 사용하는데, $ε$ -greedy Policy를 만들면서 최대값 연산을 수행한다. Q-Learning에서는 (위에서 살펴본 것처럼) 최대값 연산이 들어 있는 업데이트 식을 이용해 가치 함수를 업데이트하고, 이 가치 함수에 대해 Greedy Policy를 만들면서 또 최대값 연산을 수행한다. ↩︎
$A^{*} = \underset{a}{\arg \max} Q_{1} (S, a)$ ↩︎
$Q_{2} (A^{*})$ . 즉, $Q_{2} (\underset{a}{\arg \max} Q_{1} (S, a))$ ↩︎
즉, $A^{*} = \underset{a}{\arg \max} Q_{2} (S, a)$ , $Q_{1} (A^{*}) = Q_{1} (\underset{a}{\arg \max} Q_{2} (S, a))$ ↩︎

L07. TD Learning

TD Method란? ​

여담 : Online Learning vs. Offline Learning ​

TD(0) Method ​

TD(0) Prediction ​

TD error ​

예제 : Random Walk ​

TD(0) Control ​

SARSA ​

Q-Learning ​

SARSA vs. Q-Learning ​

Expected SARSA ​

최대화 편향 (Maximization Bias) ​

Double Learning ​

Double Q-Learning ​

Double SARSA ​

Double Expected SARSA ​

여담 : 다음-상태-가치 함수(afterstate value function) ​

TD Method란?

여담 : Online Learning vs. Offline Learning

TD(0) Method

TD(0) Prediction

TD error

예제 : Random Walk

TD(0) Control

SARSA

Q-Learning

SARSA vs. Q-Learning

Expected SARSA

최대화 편향 (Maximization Bias)

Double Learning

Double Q-Learning

Double SARSA

Double Expected SARSA

여담 : 다음-상태-가치 함수(afterstate value function)