Chapter 6. TD법(SARSA, Q-learning)

5장에서 배운 몬테카를로법은 에피소드가 종료가 되고 수익이 확정돼야 가치 함수를 갱신할 수 있는 방법이었다. 따라서 에피소드에 끝이 없는 지속적 과제에는 적용하기 힘들다. 또한 일회성 과제라고 해도 완료 시간이 오래 걸리는 에피소드는 가치 함수를 갱신하는데 오랜 시간이 소요되므로 비효율적이다. 에이전트가 초반에는 무작위인 경우가 많기 때문이다.

이번 장에서는 환경 모델을 사용하지 않을 뿐 아니라 행동을 한 번 수행할 때마다 가치 함수를 갱신하는 TD(Temporal Difference, 시간차) 법을 설명한다.

TD법으로 정책 평가하기

TD법은 MC와 DP를 합친 기법이다. 먼저 이 두 방법을 복습해보자.

TD법 도출

수익과 가치 함수에 대해서 복습해보자.

$$\begin{equation} \begin{split}  G_t &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \\ &= R+ \gamma G_{t+1} \end{split} \end{equation}$$

$$\begin{equation} \begin{split}  V_\pi(s) &= \mathbb{E}_\pi[G_t|S_t=s]  \\ &= \mathbb{E}_\pi[R_t + \gamma G_{t+1}|S_t=s]  \end{split} \end{equation}$$

'MC'법에서는 기대값을 계산하는 대신 실제 수익의 샘플 데이터를 평균하여 기대값을 근사한다. 평균에는 표본 평균과 \(\alpha\)를 활용한 지수 이동 평균이 있다.

$$V_\pi '(S_t) = V_\pi(S) + \alpha \{G_t- V_\pi(S)\}$$

여기서 \(V_\pi(S)\)는 현재의 가치 함수이고 \( V'_\pi(S)  \)는 갱신 후의 가치 함수이다. 그래서 위 식은 현재의 가치 함수를 \(\alpha\)만큼 \(G_t\)쪽으로 갱신하고 있다. 

반면 'DP'법은 MC와 달리 다음 식의 계산을 통해 기대값을 구한다.

$$\begin{equation} \begin{split}  V_\pi(s) &= \mathbb{E}_\pi[R_t + \gamma G_{t+1}|S_t=s]  \\ &= \sum_{a, s'} \pi(a|s)p(s'|s,a,) \{r(s,a,s')+\gamma v_\pi(s')\} \end{split} \end{equation}$$

위 식은 벨만 방정식이다. 즉, DP는 벨만 방정식을 기반으로 가치 함수를 갱신한다. 갱신식은 다음과 같다.

$$\begin{equation} \begin{split}  V'_\pi(s) &= \sum_{a, s'} \pi(a|s)p(s'|s,a) \{r(s,a,s')+\gamma V_\pi(s')\} \end{split} \end{equation}$$

위 식에서 중요한 점은 '현재 상태에서의 가치 함수'를 '다음 상태에서의 가치 함수'로 갱신한다는 점이다. 이 때 모든 전이를 고려하고 있다는게 특징이다.(정확히는 다음 상태에서의 가치 함수 + 현재 상태의 리워드로 갱신;;)

MC와 TD를 그림으로 비교해보면,

DP법은 다음 상태의 가치 함수의 추정치를 이용하여 현재 상태 가치 함수의 추정치를 갱신한다. 이 원리를 '부트스트랩'이라고 한다(추정치를 사용하여 추정치를 갱신). 반면 MC법은 실제로 얻은 일부 경험만을 토대로 현재의 가치 함수를 갱신한다. 

TD법은 이 두가지 방식을 융합한 것이다.

TD법에서 중요한 점은 두 가지이다.

• DP법처럼 부트스트랩을 통해 가치 함수를 순차적 갱신
• MC법처럼 환경에 대한 정보 없이 샘플링된 데이터만으로 가치 함수 갱신

TD법을 수식으로 도출해보면 다음과 같다.

$$\begin{equation} \begin{split}  v_\pi(s) &= \sum_{a, s'} \pi(a|s)p(s'|s,a,) \{r(s,a,s')+\gamma v_\pi(s')\} \\ &= \mathbb{E}_\pi \Big[ R_t + \gamma v_\pi(S_{t+1})|S_t=s\Big]\end{split} \end{equation}$$

TD법은 위 수식을 통해 가치 함수를 갱신하는데, \(R_t + \gamma v_pi(S_{t+1})\) 부분을 샘플 데이터에서 근사한다. 갱신식을 수식으로 표현하면 다음과 같다. 

$$V'_\pi(S_t) = V_\pi(S_t) + \alpha \{R_t + \gamma V_\pi(S_{t+1}) - V_\pi(S_t)\}$$

\(V_\pi\)는 가치 함수의 추정치이고 \(R_t + \gamma v_pi(S_{t+1})\)은 목적지(목표)이다. 이 목적지를 TD target이라 하며, TD 법은 \(V_\pi\)를 TD Target 방향으로 갱신한다.

[TD와 DP 갱신식 비교]

$$V'_\pi(S_t) = V_\pi(S_t) + \alpha \{R_t + \gamma V_\pi(S_{t+1}) - V_\pi(S_t)\}$$

$$\begin{equation} \begin{split}  V'_\pi(s) &= \sum_{a, s'} \pi(a|s)p(s'|s,a) \{r(s,a,s')+\gamma V_\pi(s')\} \end{split} \end{equation}$$

MC법과 TD법의 비교

MC와 TD 모두 환경 모델을 모를 때 사용이 가능하다. 지속적인 과제에서는 MC를 사용할 수 없으니 TD가 유일한 대안이다. 일회성 과제에서는 이론적으로 어느 쪽이 항상 더 나은지 증명되지는 않았다. 하지만 현실의 많은 문제에서는 TD법이 더 빠르게 학습한다.

위 식에서 보다시피 TD는 한 단계 앞의 정보를 이용해 계산하기 때문에, 한 단계 진행될 때마다 가치 함수를 갱신 할 수 있다.

또한 MC법은 에피소드가 끝날때까지 많은 시간동안 얻은 결과이기 때문에 값의 변동성이 심한 편이다. 반면 TD는 한 단계 앞을 보기 때문에 분산이 작다.

TD target은 \(R_t + \gamma v_pi(S_{t+1})\)인데, 추정치인 \(V_\pi\)가 사용된다. 즉 TD법은 추정치로 추정치를 갱신하는 부트스트래핑이다. 이 때문에 정확한 값은 아니기에 '편향'이 존재한다. 하지만 갱신이 반복될때마다 점점 0으로 수렴한다. 

반면 MC는 추정치가 포함되어 있지 않기 때문에 '편향이 없다'라고 할 수 있다.

# TD 법의 가치 함수 갱신
next_V = 0 if done else self.V[next_state]
target = reward + self.gamma * next_V
self.V[state] += (target - self.V[state]) * self.alpha

SARSA

앞 절에서 TD법으로 정책을 평가했으니 정책 제어 단계를 진행해야 한다. 평가와 개선을 반복하여 최적 정책을 구하는 과정이다.

이번에는 On-policy 에 속하는 SARSA 기법을 알아보자.

On-policy SARSA

개선 단계에서는 정책을 탐욕화해야 하며, \(V_\pi(s)\)는 환경 모델이 필요하므로 \(Q_\pi(s,a)\)를 활용하여 갱신 식을 다시 써보자.

$$Q_\pi'(S_t, A_t) = Q_\pi(S_t, A_t) + \alpha \{R_t +\gamma Q_\pi(S_{t+1}, A_{t+1}) - Q_\pi(S_t, A_t)\}$$

SARSA에서는 에이전트가 t와 t+1에서 (\(S_t, A_t, R_t, S_{t+1}, A_{t+1}\))의 데이터를 얻으면 Q 함수를 갱신할 수 있다. 그러면 상태 \(S_t\)에서의 정책은 다음과 같이 갱신된다.

$$\pi'(a|s) = \begin{cases} \underset{a}{\operatorname{argmax}} Q_\pi(S_t,a) &\text{ 1-ε의 확률 } \\ \text{무작위 행동} &\text{ ε의 확률 }\end{cases}$$

SARSA 알고리즘의 구현의 차이점은 다음과 같다.

# TD 법(SARSA)의 Q 함수 개선
next_Q = 0 if done else self.Q[next_state, next_action]
target = reward + self.gamma * next_Q
self.Q[state, action] += (target - self.Q[state, action]) * self.alpha

agent.update()가 호출되는 시점이 MC와 달리 에피소드가 끝나지 않아도 호출하는 것이 특징이다.

Off-policy SARSA

보통 이쯤 Q-러닝을 배우지만 이 책에서는 Off-policy SARSA를 먼저 배운다( '강화학습 이론 & 실습' 책에서도 off-policy SARSA는 없음)

Off-policy 와 Importance Sampling

오프 정책에서는 에이전트가 행동 정책과 대상 정책을 따로 가지고 있다. 행동 정책은 ε-탐욕 정책으로 갱신하고 대상 정책은 탐욕 정책으로 갱신한다. 두 정책이 서로 다르기 때문에 중요도 샘플링을 활용하여 가중치 \(\rho\)로 보정한다.

\(Q_\pi(S_t,A_t\))가 갱신되는 경우를보자.

\(Q_\pi(S_t,A_t\))를 갱신하기 위해 상태 \(S_{t+1}\)에서 사용되는 정책은 \(\pi\) 또는 b에 따라 샘플링 된다. b에 의해 샘플링 된 경우 가중치 \(\rho\)로 TD 목표를 보정한다. 따라서 off-policy SARSA의 갱신식은 다음과 같다.

$$\rho=\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}$$

$$\text{샘플링:} A_{t+1} \text{~} b$$

$$Q_\pi'(S_t, A_t) = Q_\pi(S_t, A_t) + \alpha \{\rho(R_t +\gamma Q_\pi(S_{t+1}, A_{t+1})) - Q_\pi(S_t, A_t)\}$$

Off-policy SARSA 구현

Q 러닝

앞서 Off-policy SARSA를 구현하기 위해 중요도 샘플링을 이용했다. 하지만 중요도 샘플링은 두 분포가 다를 수록 \(\rho\)의 변동성이 커진다는 단점을 가지고 있다. 따라서 가급적 피하고 싶은 기법이다.

이 문제를 해결해주는 것이 Q-learning이다. Q-learning의 대표적인 특징은 다음과 같다.

1. TD법
2. Off-policy
3. 중요도 샘플링을 사용하지 않음

Q 러닝을 도출하기 위해 벨만 방정식과 SARSA의 관계를 확인하고 그 다음 벨만 최적 방정식과 Q 러닝과의 관계를 살펴보자.

벨만 방정식과 SARSA

먼저 벨만 방정식과 SARSA의 관계를 보자. 벨만 방정식은 다음과 같다.

$$q_\pi(s,a) = \sum_{s'} p(s'|s, a) \{r(s, a, s') + \gamma \sum_{a'} \pi(a'|s') q_\pi(s', a')\}$$

벨만 방정식에서 중요한 점은 다음 두 가지 이다.

• 환경의 상태 전이 확률 p(s'|s, a)에 따른 다음 단계의 모든 상태 전이를 고려한다.
• 에이전트의 정책 \(\pi\)에 따른 다음 단계의 '모든' 행동을 고려한다.

Q 함수는 아래 백업 다이어그램에서 처럼 다음 상태와 다음 행동의 모든 후보를 고려한다.

반면 SARSA는 모든 전이를 보는 것이 아닌 샘플링 된 데이터를 사용하기 때문에 벨만 방정식의 샘플링 버전으로 볼 수 있다.

벨만 최적 방정식과 Q 러닝

4장에서 배운 '가치 반복법'은 최적 정책을 얻기 위한 '평가'와 '개선'이라는 두 과정을 하나로 묶은 기법이다. 가치 반복벙의 중요한 점은 벨만 최적 방정식에 기반하여 '단 하나의 갱신식을 반복'함으로써 최적 정책을 얻는 것이었다. 이번에는 벨만 최적 방정식에 의한 갱신인 동시에 '샘플링 버전'으로 만든 방법을 알아보자.

벨만 최적 방정식과 백업 다이어그램은 다음과 같다.

$$Q_*(s,a) = \sum_{s'} p(s'|s,a) \{r(s,a,s') + \gamma \underset{a'}{\operatorname{max}} q_*(s',a')\}$$

이제 '샘플링 버전'의 벨만 최적 방정식의 백업 다이어그램을 보자.

그림에서 보듯 Q 함수가 가장 큰 행동으로 \(A_{t+1}\)을 선택한다. 따라서 특특별한 정책에 따라 샘플링하지 않고 max 연산자로 선택한다. 그렇기 때문에 off-policy 정책임에도 중요도 샘플링을 이용한 보정이 필요 없다

(이 부분 이해가 안된다.. max 연산자로 뽑는다고 해도 어쨌든 분포 b의 max를 뽑는거니까 \(\pi\)와 다른 분포에서 뽑는것이기 때문에 중요도 샘플링 한다고 봐야하지 않나..? -> 다시 생각해보니 SARSA에서는 정말 말 그대로 A'을 뽑는 과정이 존재하는데 Q러닝에서는 A'을 선택하는 과정 자체가 필요가 없다.)

그림 6.14에 기반하여 Q 함수 갱신 식을 써보자.

$$Q'(S_t, A_t) = Q(S_t, A_t) + \alpha \{ R_t + \gamma \underset{a'}{\operatorname{max}} Q(S_{t+1}, a) - Q(S_t, A_t)\}$$

위 식에 따라 Q 함수를 반복해서 갱신하면 최적 정책의 Q 함수에 가까워진다.

Q 러닝은 Off-policy 기반 기법이다. 대상 정책과 행동 정책을 따로 가지며 행동 정책으로는 '탐색'을 수행한다. 에이전트가 행동 할 때마다 위 식으로 Q 함수를 갱신한다. 이상이 Q 러닝이다.

Q 러닝 구현

SARSA의 구현에서는 pi, b를 명시적으로 확률 분포로 정의해놓고 사용했으나, 여기서부터는 정책을 명시적으로 구현하지 않고 Q 함수를 통해서 action을 선택하도록 구현되어 있다(이유: 훨씬 간편)

정리

• TD 법의 특징은 '지금'과 '다음'의 정보만으로 가치 함수를 갱신한다.
• TD의 대표적인 알고리즘으로 SARSA, Q-learning이 있다.
• SARSA는 on-policy 방식이지만 off-policy로 확장도 가능하다.
• Q-learning은 벨만 최적 방정식 기반이다.
• Q-learning은 off-policy 방식이지만 중요도 샘플링 없이 Q 함수를 갱신한다.
• 강화 학습에서 Q-learning은 특히 중요한 알고리즘이다.