Tabular Temporal Difference Learning - Sarsa, Q-learning, Double Q-learning

Reinforcement Learning/Tabular Methods에 있는 이전 글에서 Dynamic Programming, Monte Carlo Learning을 알아보았습니다. 위 두 가지 방법은 역사적으로 중요한 방법으로, 각각의 장점을 취한 방법이 Temporal Difference Learning (TD)입니다. 또한 강화학습에서 가장 중요한 방법과 학습의 컨샙은 TD라고 할 수 있습니다. 이번 포스팅에서는 Tabular Methods 세 가지 방법 중 마지막인 TD에 대하여 살펴보겠습니다.

Temporal Difference Learning

DP 와 MC의 장단점

• DP
  • 장점: 최종 상태에 도달하지 않더라도 그때 그때 발생하는 보상을 이용하여 가치함수 업데이트가 가능하다.
  • 단점1: Model-Based 방법으로 모델을 알고 있어야만 적용가능하다. 이에 따라, 학습보단 계산에 가깝다.
  • 단점2: 각 상태별 가치를 메모리에 모두 할당하기 때문에 고차원 상태 공간의 모델이 적용하기 어렵다.
• MC
  • 장점: Model-free 방법으로 모델을 모르더라도 에이전트의 경험을 이용하여 가치함수 업데이트가 가능하다.
  • 단점1: 최종 상태에 도달하여 누적 보상을 얻어야 적용가능하다. Continuing Task에 적용하기 어렵다.
  • 단점2: On-line update를 적용할 수 없다. (Incremental Implementation도 에피소드가 얻어져야 적용가능)

장단점을 위와 같습니다. 첨언하면 $t+1$ 시점의 가치함수를 계산하기 위하여, 이전시점의 가치함수 결과를 이용하는 방법을 bootstrap 방법이라고 하고, 가치함수의 결과에 따라 에이전트가 실제로 행동하여 도달한 다음 상태와 보상을 이용하는 방법을 sampling 방법이라고 합니다. 기본적으로 DP는 Boostrap 방식을, MC는 Sampling 방식을 따릅니다.

Temporal Difference

Temporal Difference Learning, 시간차학습은 DP의 Boostrap 방식으로 최종상태가 필요없는 장점과 MC의 모델을 몰라도 Sampling 방식으로 학습할 수 있는 장점을 취한 방식입니다. 그렇다면 왜 이름이 TD가 되었을까요? 상태가치함수 정의를 다시 살펴보겠습니다. $$\begin{align*}v_{\pi}(s)&=\mathbb{E}_{\pi}\left[\left.G_{t}\right| S_{t}=s\right]\text{ (1)}\\&=\mathbb{E}_{\pi}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+1})\right|S_{t}=s\right]\text{ (2)}\\&=\sum_{a}\pi(a|s)\sum_{r,s'}\mathbb{P}(r,s'|s,a)[r+\gamma v_{\pi}(s')]\text{ (3)}\end{align*}$$ 상태가치함수 정의는 위처럼 세 가지 방법으로 표현할 수 있습니다. DP에서는 (3)을 이용했고, $v_{\pi}$의 참 값을 알 수 없기 때문에 직전 스탭까지 업데이트한 결과를 이용한 bootstrap 방식을 적용했습니다. MC에서는 (1)을 이용하였고, 충분한 episode를 획득하여 평균을 구하는 sampling 방식을 적용했습니다. TD는 (2)를 이용하는 방식이고, $v_{\pi}$의 참 값 대신 직전 스탭까지 결과를 적용하는 bootstrap 방식과 $R_{t+1}+\gamma v_{\pi}(S_{t+1})$을 episode를 이용하여 평균을 구하는 sampling 방식을 결합한 방법입니다. 이제 (2)식을 incremental implementation으로 나타내면 아래와 같습니다. $$V(S_{t})\leftarrow V(S_{t})+\alpha\left[R_{t+1}+\gamma V(S_{t+1})-V(S_{t})\right]$$ 여기에서 $\alpha$는 $1/n$ 대신 상수를 이용한 것이며 step-size라고 부릅니다. 위 괄호안 $R_{t+1}+\gamma V(S_{t+1})-V(S_{t})$를 temporal difference error, 시간차 오차라고 부르며, $t$ 시점의 상태 가치와 $t+1$ 시점의 상태 가치의 차이를 이용하여 학습하기 때문에 시간차 학습 또는 one-step TD Learning이라고 합니다.

단순히 상태가치함수를 예측 (prediction)하는 것과 예측결과 GPI에 적용하는 제어(control)로 구분지을 수 있지만, 결국 필요한 것은 제어이기 때문에 예측부분은 생략하고, 이어서 on-policy control (SARSA), off-policy control (Q-learning), double Q-learning을 살펴보겠습니다.

$\epsilon$-greedy

아주 가볍게 $\epsilon$-greedy에 대해서 살펴보고 넘어가겠습니다. $\epsilon$-greedy는 exploration, exploitation의 딜레마를 극복하기 위한 방법으로 $\epsilon$ 확률로 행동을 무작위로 선택하는 방법을 말합니다. 즉 $\epsilon$의 확률로 exploration을 하는 방법입니다. 방법은 아래와 같습니다.

Figure 1: $\epsilon$-greedy

Sarsa

Sarsa는 On-policy TD control의 일종으로 행동정책(behavior policy)과 목표정책(target policy)을 같이하는 $S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1}$의 샘플을 얻어 가치함수를 업데이트하는 방법입니다.  $$Q\left(S_{t},A_{t}\right)\leftarrow Q\left(S_{t},A_{t}\right)+\alpha\left[R_{t+1}+\gamma Q\left(S_{t+1},A_{t+1}\right)-Q\left(S_{t},A_{t}\right)\right]$$ $sar's'a'$를 이용한다는 이유로 Sarsa라고 불립니다. Pseudocode를 살펴보겠습니다.

Figure 2: Sarsa

단순히 $Q$로 부터 $\epsilon$-greedy하게 행동을 선택하고, 그에 따른 보상 및 다음 상태를 샘플링하여 가치함수를 업데이트 하는 방식입니다.

Q-learning

Q-learning은 off-policy TD control이라는 점이 Sarsa와 구분되며, $(S_{t}, A_{t},R_{t+1},S_{t+1})$의 샘플을 이용하여 가치함수를 업데이트합니다. $$Q(S_{t},A_{t})\leftarrow Q(S_{t},A_{t})+\alpha\left[R_{t+1}+\gamma\underset{a}{\operatorname{max}}Q\left(S_{t+1},a\right)-Q(S_{t},A_{t})\right]$$Q-learning은 Watkins, 1989가 고안했으며 강화학습의 가장 대표적인 알고리즘입니다. Pseudocode를 살펴보면서 off-policy인 이유와 Sarsa와 구분되는 점을 명확히 하도록 하겠습니다.

Figure 3: Q-learning

Off-policy learning은 행동정책과 목표정책이 다른 학습 방법입니다. Q-learning의 행동정책을 살펴보면 $Q$함수 기반 $\epsilon$-greedy한 행동선택을 하는 것을 알 수 있고, 목표정책은 $Q$함수 기반 greedy 행동선택을 합니다. 그래서 Q-learning은 off-policy learning이 됩니다.

Double Q-learning

Q-learning, Sarsa 모두 maximization bias가 존재합니다. Maximization Bias는 가치함수를 업데이트 할 때 최대값을 이용해서 업데이트하며 발생하는 bias를 의미합니다. 예로 Q-learning의 업데이트를 살펴보면, $$R+\gamma\underset{a}{\operatorname{max}}Q(S',a)-Q(S,A)$$인데 결국 이 값은 0보다 크거나 같을 수 밖에 없습니다.

Maximization bias를 해결하기 위해서 두 개의 목표 가치함수를 이용하여, 1번 목표 가치함수 업데이트시 2번 목표 가치함수의 결과를 이용하고 반대의 경우도 비슷하게 처리하는 방법을 Double learning이라고 부르며, Q-learning에 적용한 것이 Double Q-learning입니다.

Figure 4: Double Q-learning

마치며

이번 포스팅에서는 TD 알고리즘 세 가지를 알아봤습니다. 이전 포스팅에서 살펴본 DP, MC에 비해 TD 알고리즘은 상대적으로 단순하고, 구현하기 쉽다는 사실을 알 수 있습니다. 알고리즘은 단순하지만 DP와 MC의 장점을 모두 취하여 더 우수한 성능을 보여줍니다. 다음 포스팅에서는 DP, MC, TD를 비교할 예정입니다. 감사합니다:)

References

• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 2. No. 4. Cambridge: MIT press, 1998.