[물고기RL] 6. Temporal Difference, Q-Learning

TD 즉, Temporal Difference는 에피소드가 끝날 때까지 기다리지 않고 매 상태에서 평가하고 개선하는 방법을 말한다.

책에서는 TD가 MonteCarlo와 DP가 합쳐진 것이라고 이야기한다. 왜 그런지 알아보도록하자. 이어서, MonteCarlo는 MC라고 줄여 말하도록 하겠다.

우선, TD가 어떤 것인지 먼저 알아보도록하자.

💡

몬테카를로도 참값을 구해내는 과정이었다면 TD 또한 DP의 개념처럼 n스텝을 목표로 계속 역으로 계산해 나가기 때문에 TD는 MC와 달리 근사치라고도 할 수 있음

What is TD?

우리가 알아보았던 Return 수익은 아래의 식과 같다.

$$\begin{array}{rl}{G}_t& =R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\cdot \cdot \cdot \\ & =R_t+\gamma G_{t+1}\end{array}\text{\hspace{1em}(MDP)(Bellman)}$$

가치함수 또한 재귀적으로 표현해 내면 아래와 같다.

$$\begin{array}{rl}{v}_{\pi }& ={\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_t+\gamma G_{t+1}|S_t=s]\end{array}$$

---

여기서부터 구분선으로 구분된 부분은 책에 설명이 되어있지 않은 부분이지만 구분선이 끝나고 나오는 식 1에 대해서 어떻게 유도되는 것인지 직접 알아본 내용이다.

일반 평균으로 계산한 뒤, 증분 업데이트를 유도

$$\begin{array}{rl}{Q}_n& =\frac{1}{n}\sum _{i=1}^n{R}_i\\ & =\frac{1}{n}\left(R_n+\sum _{i=1}^{n-1}{R}_i\right)\\ & =\frac{1}{n}\left(R_n+(n-1)Q_{n-1}\right)\\ & =Q_{n-1}+\frac{1}{n}(R_n-Q_{n-1})\end{array}$$

증분 구조를 EMA로 변경

$$\begin{array}{rl}{V}_k& =V_{k-1}+\alpha (G_k-V_{k-1})\\ & =\alpha G_k+(1-\alpha )V_{k-1}\\ & =\alpha G_k+(1-\alpha )\{\alpha G_{k-1}+(1-\alpha )V_{k-2}\}\\ & =\underset{\text{Current}}{\underbrace{\alpha G_k}}+\underset{\text{Weight decays}}{\underbrace{\alpha (1-\alpha )G_{k-1}}}+\cdots +(1-\alpha {)}^k{V}_0\end{array}$$

---

식 1로부터 MC를 적용하여 지수이동평균을 고려한다. 다음 수익에 대해 수식을 정리하면 아래의 식 3이 된다.

$$\begin{array}{r}{V}_{\pi }^{\prime }(S_t)=V_{\pi }(S_t)+\alpha \{G_t-V_{\pi }(S_t)\}\end{array}$$

“ $G_t$ 가 미래까지 포함하고 있으니 여태까지의 수익합을 빼서 감가율 때려줌 ”

이제 DP를 적용하여 아래의 식으로 가치함수를 유도해 낼 수 있다.

식 2로부터 TD를 적용하여 보자.

$$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[R_t+\gamma G_{t+1}|S_t=s]\\ & =\sum _{a,s^{\prime }}\pi (a|s)p(s^{\prime }|s,a)\{r(s,a,s^{\prime })+\gamma v_{\pi }(s^{\prime })\}\end{array}\text{\hspace{1em}(2)}$$

식 4는 DP를 벨만방식으로 풀어낸 것이다. 이를 다시 갱신식으로 풀어내면.. 식 5가 된다.

$$\begin{array}{r}{V}_{\pi }^{\prime }(S_t)=\sum _{a,s^{\prime }}\pi (a|s)p(s^{\prime }|s,a)\{r(s,a,s^{\prime })+\gamma V_{\pi }(s^{\prime })\}\end{array}$$

식 5의 의의를 살펴보자면 ‘현재 상태에서의 가치함수’ $V_{\pi }^{\prime }(s)$ 가 ‘다음 상태에서의 가치함수’ $V_{\pi }(s^{\prime })$ 로 갱신할 수 있다는 것이다.

💡

[이해한 바] 좀 실질적인 의미에 대해서 살펴보자면, DP는 선택가능한 모든 Action에 대해서 한 스텝씩 계산할 수 있게 큰 문제를 작은 문제로 나눈 것이라면, MC는 가능한 Action 들 중 일부만을 선택해가며 일부 경험을 토대로 평가 및 개선하는 방법이다. MC에서는 수익을 끝까지 계산해나가야하고 DP는 선택가능한 모든 Action에 대해 한 스텝씩 나아가는 것인데 이를 합쳐서 결국, TD는 Action을 샘플링하면서도 일정 스텝씩 마다 평가 및 개선해 나아가는 방법이다.

책에서 말하는 TD법의 중요한 점 두가지는 아래와 같다.

• DP처럼 부트스트랩을 통해 가치 함수를 순차적으로 갱신

• MC처럼 환경에 대한 정보 없이 샘플링된 데이터만으로 가치 함수 갱신

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _{a,s^{\prime }}\pi (a|s)p(s^{\prime }|s,a)\{r(s,a,s^{\prime })+\gamma v_{\pi }(s^{\prime })\}\\ & ={\mathbb{E}}_{\pi }[R_t+\gamma v_{\pi }(S_{t+1})|S_t=s]\end{array}\text{\hspace{1em}(4)}$$

TD를 이제 수식을 통해 유도해보자.

앞선 식4를 기댓값으로 다시 정리하면 식6이 되는데 식 6에서 $R_t+\gamma v_{\pi }(S_{t+1})$ 부분은 샘플 데이터로 부터 근사되는 데이터이다. 샘플링은 표현했으므로 남은 갱신식으로 변환하는 과정을 거치면 아래의 식 7이 된다.

$$\begin{array}{r}{V}_{\pi }^{\prime }(S_t)=V_{\pi }(S_t)+\alpha \{\underset{\text{TD target}}{\underbrace{R_t+\gamma V_{\pi }(S_{t+1})}}-V_{\pi }(S_t)\}\end{array}$$

$$TDTarget:R_t+\gamma V_{\pi }(S_{t+1})$$

방금 살펴본 것은 TD Target을 1단계 앞의 정보를 활용한 것으로 이를 n단계 앞의 정보를 활용하는 것도 가능하다.

“TD target - $V_{\pi }(S_t)=0$ 이게 되면 다음 상태와 현재 상태의 가치함수가 동일 한 것이고 더이상 업데이트할 게 없게 되는 상황이 된다. 즉, 더 업데이트할게 없고 학습이 끝났다는 것. 따라서 타겟과 현재 상태의 가치함수를 뻬내서 업데이트할 것이 무엇인지 알아보는 것이다.”

MC vs TD

이제, 우리가 살펴본 것들을 토대로 환경 모델을 모를 때 쓸수 있는 방법은 두 가지가 되었다. MC와 TD이다. MC는 지속적 과제에서 그 에피소드의 끝을 알 수 없기 때문에 전체 수익을 계산할 수 없어 사용할 수 없다고 하였다. 그럼, 지속적 과제에서는 TD만 사용할 수 있다. 반면, 일회성 과제에서는 MC와 TD를 모두 사용할 수 있는데 어느 것이 더 좋은지는 증명된 것이 없으나 일반적으로 TD가 더 빠르다고 한다.

수식을 다시 정리해보자.

$$\begin{array}{rl}<MC>& V_{\pi }^{\prime }(S_t)=V_{\pi }(S_t)+\alpha \{\underbrace{G_t}-V_{\pi }(S_t)\}\\ <TD>& V_{\pi }^{\prime }(S_t)=V_{\pi }(S_t)+\alpha \{\underbrace{R_t+\gamma V_{\pi }(S_{t+1})}-V_{\pi }(S_t)\}\end{array}$$

위 식을 살펴보면 MC는 $G_t$ 를 목표로, TD는 TD Target을 목표로 업데이트 되어가고 있음을 알 수 있다.

TD는 한단계 마다 가치함수를 갱신할 수 있어 효율적인 학습을 기대할 수 있다. 반대로 MC는 많은 시간을 쌓아 수익을 모두 계산해내야하기 때문에 값의 변동이 TD에 비해 커질 수 있다.

MC 변동, 분산 큼 / TD 변동, 분산 작음

반대로, TD는 추정치 $V_{\pi }$ 가 사용되고 있기 때문에 정확한 값이 아니고 bias가 생기게 된다.

또한, TD는 추정치를 통해 추정치를 갱신하게 되는 bootstrapping이다.

→ “부트스트랩핑 에러 - 온라인 ”

“Bias가 커지면 Variance는 작아짐, 선택지도 줄어들게됨 둘이 trade-off → 많은 데이터가 통치약”

앞서서… 가치함수와 함께 TD가 어떤 것인지 알아보았다. 즉, 평가해보았다. 여태의 흐름처럼 이제 개선을 해야할 시간이다. SARSA에 대해 알아보도록 하자.

💡

요약 TD의 방식을 Q함수에 적용하여 그저 추정치를 활용해 제어하는 방식이라고 할 수 있다.

의미론적으로 TD target을 목표로 해도 괜찮은거는 이과정을 계속 반복하기 때문이 맞는지?

SARSA

“alternative update or training , iterative”

앞선 5장에서도 우리는 상태가치함수가 아닌 Q-fucntion을 통해 정책을 개선하였다. 정책을 개선하기위해 정책을 탐욕화했고 환경모델을 모르는 경우에 더욱 Q-function을 활용했어야 했다.

$$\begin{array}{r}\mu (s)=\underset{a}{\mathrm{argmax}}{Q}_{\pi }(s,a)\end{array}$$

앞서 살펴본 식 7은 다음과 같았다. 여기서 상태가치함수를 Q-function으로 전환하면 다음과 같다.

$$\begin{array}{rl}& V_{\pi }^{\prime }(S_t)=V_{\pi }(S_t)+\alpha \{R_t+\gamma V_{\pi }(S_{t+1})-V_{\pi }(S_t)\}\\ Q_{\pi }^{\prime }(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)\}\end{array}\text{\hspace{1em}(7)}$$

SARSA

SARSA는 기본적으로 ON-policy이다. OFF-policy를 사용하게 될 때에는 OFF-policy SARSA라고 따로 부르게 된다. 먼저 ON-policy는 행동정책과 타겟정책이 같아 하나의 정책만을 가진다. 이때, 유의할 점은 하나의 정책만을 가지고 있기때문에 완벽하게 정책을 탐욕화 해버리면 그 이후로 탐색을 할 수 없게 된다. 따라서, 탐색을 위해 $ϵ-greedypolicy$ 를 사용하게 된다.

Q-function은 상태와 행동을 그 변수로 취한다. 즉, $(S_t,A_t)$ 가 하나의 입력으로 들어오게 된다.

만약, 우리가 데이터$(S_t,A_t,R_t,S_{t+1},A_{t+1})$ 을 얻게 되었다면 위의 식 9를 통해서 $Q_{\pi }(S_t,A_t)$ 를 갱신할 수 있게 된다. 갱신이 되면 상태 $S_t$ 시점에서의 정책 또한 아래의 수식에 따라 갱신, 즉 변경된다.

$${\pi }^{\prime }(a|S_t)=\{\begin{array}{ll}\underset{a}{\mathrm{argmax}}{Q}_{\pi }(S_t,a)& \text{with probability }1-\epsilon \\ \text{exploration}& \text{with probability }\epsilon \end{array}$$

ON-policy이기 때문에 앞서 말했듯 $ϵ-greedypolicy$ 적용해야만 한다.

수식을 통해 ON-policy SARSA를 알아보면 아래와 같다.

이 식으로부터 어떻게 동작하게 되는지 살펴보자.

$$\begin{array}{r}{Q}_{\pi }^{\prime }(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)\}\end{array}\text{\hspace{1em}(9)}$$

1. $Q_{\pi }(S_t,A_t)$ 가 개선, 갱신될 상태이다. 이때, $(S_t,A_t)$ 는 임의로 선택될 수 있다.

2. $S_{t+1}$ 은 상태전이확률 $p(s^{\prime }|s,a)$ 에 따라 샘플링되게 된다.

3. $S_{t+1}$ 에서의 행동 $A_{t+1}$은 $\pi (a|s)$에 의해 샘플링된다. 정책은 $\pi$ 하나이다.

4. 우리는 식9에서 갱신을 위해 필요한 $S_t,A_t,R_t,S_{t+1},A_{t+1}$ 을 모두 알고 있으므로 비로소 구하고자 하였던 $Q_{\pi }(S_t,A_t)$ 를 갱신할 수 있다. 이때의 TD target은 당연히 $R_t+\gamma Q_{\pi }(S_{t+1},A_{t+1})$ 이다.

식을 정리하여 SARSA의 갱신식을 구하면 아래와 같다.

$$\begin{array}{rl}& 샘플링:A_{t+1}\sim \pi \\ & Q_{\pi }^{\prime }(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)\}\end{array}$$

OFF-policy SARSA

OFF-policy에서는 행동정책과 타겟정책이 다르다고 알아봤었다. 앞서 중요도 샘플링에서 다루어 보았듯, 타겟정책이 갱신되는 동안 행동정책은 갱신되지 않는 기간 동안에는 각각에서 샘플링한 데이터들은 다르다.

실제로, 행동정책을 통해 다양한 행동을 시도하고 샘플 데이터를 폭넓게 수집하며 이 샘플 데이터를 통해 타겟정책을 탐욕화해 업데이트하게 된다.

이때 앞서 알아본 것들과 내용을 정리하여 살펴보면 다음과 같다.

• 행동정책과 타겟정책의 확률분포가 비슷할수록 결과가 안정적이다. 이 점을 고려하면 현재의 Q-fucntion에 대해 행동 정책은 $ϵ-greedypolicy$ 로 갱신하며, 타겟정책은 탐욕정책으로 갱신한다.

• 두 정책이 서로 다르기 때문에 중요도 샘플링을 통해 가중치 $\rho$ 를 통해 보정한다.

Behaviour Policy	Target Policy
$ϵ-greedypolicy$	$greedypolicy$

수식을 통해 OFF-policy SARSA를 알아보면 아래와 같다.

$$\begin{array}{r}{Q}_{\pi }^{\prime }(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)\}\end{array}\text{\hspace{1em}(9)}$$

이 식으로부터 어떻게 동작하게 되는지 살펴보자.

1. $Q_{\pi }(S_t,A_t)$ 가 개선, 갱신될 상태이다. 이때, $(S_t,A_t)$ 는 임의로 선택될 수 있다.

2. $S_{t+1}$ 은 상태전이확률 $p(s^{\prime }|s,a)$ 에 따라 샘플링되게 된다.

3. $S_{t+1}$ 에서의 행동 $A_{t+1}$은 $behaviourpolicyb(a|s)$에 의해 샘플링된다. 개선될 정책인 $\pi (a|s)$ 와 다르면서 앞서 살펴보았던 중요도 샘플링이 필요하다. $\rho$ 를 통하여 TD target 을 보정한다.

4. 우리는 식9에서 갱신을 위해 필요한 $S_t,A_t,R_t,S_{t+1},A_{t+1}$ 을 모두 알고 있으므로 비로소 구하고자 하였던 $Q_{\pi }(S_t,A_t)$ 를 갱신할 수 있다. 이때의 TD target은 $\rho (R_t+\gamma Q_{\pi }(S_{t+1},A_{t+1}))$ 이다.

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

$$\begin{array}{rl}& 샘플링:A_{t+1}\sim b\\ & Q_{\pi }^{\prime }(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)\}\end{array}$$

Q-Learning

Q-Learning 이제 줄여서 Q러닝이라고 하겠다. Q 러닝은 OFF-policy SARSA에서 중요도 샘플링이 피하기 위한 방법이라고 할 수 있다. 우선, 중요도 샘플링이 적용될 때 어떤 문제가 있는지 살펴보자.

중요도 샘플링을 적용하게되면 결과가 불안정해질 수 있다. 확률분포가 달를수록 $\rho$ 의 변동성도 커지면서 SARSA의 TD target으로 쓰이는 값의 변동 또한 커지며 불안정해진다.

그렇다면 Q러닝은 어떻게 문제를 해결하는가?

1. TD

2. OFF-Policy

3. $\rho$ 중요도 샘플링을 사용하지 않음

벨만 방정식이 SARSA에 대응되는 것이라면

벨만 최적 방정식은 Q-Learning에 대응된다.

Bellman → SARSA?

$$\begin{array}{r}{q}_{\pi }(s,a)=\sum _{s^{\prime }}p(s^{\prime }\mid s,a)\left\{r(s,a,s^{\prime })+\gamma \sum _{a^{\prime }}\pi (a^{\prime }\mid s^{\prime })q_{\pi }(s^{\prime },a^{\prime })\right\}\end{array}$$

이 벨만 방정식을 확인하여 보면 현재 상태의 $q_{\pi }$를 업데이트 하기위해 상태전이확률 $p(s^{\prime }|s,a)$에 의해 가능한 모든 상태를 고려한다. 더불어, 그 상태에서 가능한 에이전트의 정책 $\pi$ 에서 가능한 ‘모든’ 행동 또한 고려한다.

그런 상황에서 SARSA는 가능한 모든 후보의 상태와 행동 들 중 하나를 샘플링한 버전이라고 볼 수있다.

Bellman (모든 S, 모든 A) → SARSA (가능한 S, A 중 하나 샘플링)

Bellman optimally euqation → Q-Learning?

$$\begin{array}{rl}{q}_{\ast }(s,a)& =\sum _{s^{\prime }}p(s^{\prime }\mid s,a)\left\{r(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }(s^{\prime },a^{\prime })\right\}\end{array}$$

벨만 최적 방정식은 최적정책 ${\pi }_{\ast }$ 에서의 Q함수이다. 벨만 방정식과 벨만 최적 방정식은 max 연산자를 사용하게 되는데 이는 앞선 Bellman과 다르게 Action을 취하게 만든다.

모든 $S_{t+1}$ 이 고려될 수 있지만 $S_{t+1}$ 에서는 최적정책 ${\pi }_{\ast }$ 을 통해 행동을 결정하게 된다. 따라서, $A_{t+1}$ 은 모든 행동이 고려되는 것이 아니라 값을 MAX로 하는 최적 행동 만을 선택하게 된다.

그렇다면 같은 논리로 Q-learning은 상태전이에 의해 가능한 모든 $S_{t+1}$ 로부터 가장 최적의 Action 을 선택하는 경우 중 하나를 샘플링하는 것으로 이해할 수 있다.

Q-Learning

그렇기때문에, Q러닝의 목표 추정치 $Q(S_t,A_t)$ 의 목표가 $R_t+\gamma {\max }_a{Q}_{\pi }(S_{t+1},a)$ 가 되어 수식이 다음과 같이 표기 되게 된다.

$$\begin{array}{rl}{Q}^{\prime }(S_t,A_t)& =Q(S_t,A_t)+\alpha \left\{R_t+\gamma \underset{a}{\max }Q(S_{t+1},a)-Q(S_t,A_t)\right\}\end{array}$$

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

Q-Learning에서는 중요도 샘플링이 필요하지 않다는 것 또한 매우 중요한 요소 중 하나였는데, $A_{t+1}$ 을 선택하는 과정에서 어떤 target 혹은 behaviour policy에 따라 선택된 것이 아닌 단순 max연산자에 의해 선택되므로 OFF-policy임에도 불구하고 중요도 샘플링을 통해 보정하는 과정을 거치지 않아도 된다.

OFF-policy인 Q러닝은 타겟정책과 행동정책이 구분된다. 행동정책-’탐색’ 이때, 행동정책은 현재 추정치인 Q함수를 $ϵ-greedypolicy$ 로 만든것이라 볼 수 있다.

행동정책이 결정되어 행동에 따라 샘플데이터가 수집되면 그때마다 Q함수를 갱신할 수 있게 된다.

“과대추정되는 문제가 있음”

Distribution Model vs Sample model

예시로 둘의 차이를 쉽게 알아보자. 어떤 사각형 그리드가 주어졌을때 에이전트의 행동이 4개로 주어진다고 치자. 상하좌우 중 하나가 선택되고 각각 확률로써 정의되어있다면 이는 바로 분포 모델이다.

상하좌우가 똑같이 존재한다고 하더라도 어떤 확률을 모르는 상태에서라도 그저 샘플링을 수행할 수 있어서 어떤 행동 하나를 골라낼 수 있다면 이는 샘플 모델이다.

이후 7장부터는 샘플링을 통해 모델을 구현한다.