Temporal-Difference(TD)

Temporal-Difference(TD) 학습은 강화학습에서 최적 가치 함수를 찾을때 Monte Carlo와 자주 비교되는 Model-free 방법입니다. Monte Carlo는 에피소드가 종료되었을 때 비로서 실제 Return값을 받고 이를 평균내어 가치 함수를 추정하였습니다. 하지만 현실에서는 에피소드가 너무 길거나 혹은 아예 끝나지 않는 경우도 많습니다. 공장에서 24시간 돌아가는 로봇 팔 제어 문제 처럼 말이죠. 이런 상황에서 Monte Carlo를 대체할 수 있는 학습이 Temporal-Diffrence(TD)입니다.

TD의 핵심은 간단합니다. "정답(실제 Return)을 끝까지 기다리지 말고, 한 스텝 뒤의 예측치를 임시 정답으로 쓰자"는 것입니다.

Temporal-Diffrence의 기본 원리

위에서 말한 "한 스텝 뒤의 예측치를 임시 정답으로 쓴다"를 식으로 옮기면 다음과 같습니다.

$$ V(S_t) \leftarrow V(S_t) + \alpha \big[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \big] $$

 

여기서 우변의 \(V(S_t)\)는 추정값이며 \( R_{t+1} + \gamma V(S_{t+1})\)는 임시 정답값 입니다. 즉 추정값과 정답의 차이를 통해 현재 추정값을 업데이트해 나가는 식을 의미합니다. 임시 정답에 해당하는 \( R_{t+1} + \gamma V(S_{t+1})\) 이 부분을 TD Target이라고 부르고 여기서 추정값 \(V(S_t)\)를 뺀 \([ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) ] \) 이 부분을 TD Error라고 부릅니다. 참고로 \(\alpha\)는 인공지능에서 학습률과 같습니다. 오차를 얼마나 반영할지를 결정하는 계수입니다.

 

그런데 왜 \(V(S_t)\)는 추정값이며 \( R_{t+1} + \gamma V(S_{t+1})\) 는 임시 정답값 이라고 표현하냐

 

 \(V(S_t)\)나  \(V(S_{t+1})\)이나 둘다 추정치인건 마찬가지입니다. 그런데 실제로 보상 \( R_{t+1}\)을 한번이라도 더 받아본 쪽이 통계적으로 정답에 가깝다고 Bellman 방정식을 통해 알 수 있습니다.

 

$$ V^\pi(s) = \mathbb{E}_\pi\!\big[ R_{t+1} + \gamma V^\pi(S_{t+1}) \,\big|\, S_t = s \big] $$

 

“한 스텝 보상 + 다음 가치” 의 기대값이 곧 현재 가치라는 뜻입니다. TD 는 이 기대값을 매 스텝 한 표본으로 추정하는 셈입니다.
다만 다음 가치 자리에 진짜 값이 아니라 추정값을 끼우기 때문에, 그 추정이 부정확한 동안엔 target자체에 편향(bias) 이 있습니다. 그래서 MC 와는 이런 trade-off 가 생깁니다.

- MC: 비편향, 분산 큼 
- TD: 편향 있음, 분산 작음 

n-step TD와 TD(λ)

앞서 설명한 TD는 한 스텝만 가보고 값을 추정하고 MC의 경우엔 완전 끝까지 가봐야 값을 추정하는 극과 극의 성향을 띄고 있습니다. 그래서 이 둘의 중간 절충안이 n-step TD입니다. 이름에서 알 수 있듯이 이전 TD가 1 step 만 갓다면 말 그대로 n step 가보고 값을 추정하는 방식입니다.

$$ G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n}) $$
$$ V(S_t) \leftarrow V(S_t) + \alpha \big[ G_t^{(n)} - V(S_t) \big] $$

여기서 \(G_t^{(n)}\) 을 n-step Return이라고 부릅니다. 앞쪽 \(n\)개 항 \(R_{t+1}, \dots, R_{t+n}\) 은 실제로 받아본 보상을 할인해서 더한 부분이고, 마지막 \(\gamma^n V(S_{t+n})\) 은 \(n\) 스텝 뒤 상태의 추정값으로 끝맺은 부분입니다. 즉 앞은 실제로 받아본 정답, 뒤는 임시 정답인 셈이지요. \(n=1\) 이면 위에서 정의한 1step TD인 TD(0) 와 같고, \(n\) 을 에피소드 끝까지 늘리면 뒤의 추정 항이 사라져 MC 와 같아집니다.

\(n\) 이 작으면 실제 보상을 조금만 받아보고 나머지는 추정값에 기대니까, 그 추정이 부정확한 동안에는 결과도 부정확합니다 (편향). 반대로 \(n\) 이 크면 실제 보상은 많이 받아봤지만 그만큼 에피소드의 다양한 운까지 같이 안고 가니까 결과가 들쭉날쭉해집니다 (분산). 즉 \(n\) 을 어디에 두느냐가 곧 편향과 분산의 균형을 정합니다.

그러면 굳이 \(n\) 을 하나로 고정할 필요가 있을까요?

여러 \(n\) 의 n-step Return 을 한꺼번에 섞어서 평균을 내면 더 안정적이지 않을까 하는 발상에서 나온 것이 TD(λ) 입니다. \(\lambda \in [0, 1]\) 이라는 가중치로 짧은 시야와 긴 시야를 골고루 섞은 새 Return 을 정의하지요.

$$G_t^\lambda = (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$$

이 \(G_t^\lambda\) 를 λ-return 이라고 부릅니다. 1-step Return, 2-step Return, 3-step Return, ... 을 \(\lambda^{n-1}\) 만큼의 가중치로 더한 다음 \((1 - \lambda)\) 를 곱해서 합이 균형 맞게 다듬은 값이지요. \(\lambda\) 가 작을수록 짧은 시야(작은 \(n\))쪽으로 가중치가 쏠리고, \(\lambda\) 가 클수록 긴 시야의 Return 까지 골고루 반영됩니다. \(\lambda = 0\) 이면 사실상 TD(0), \(\lambda = 1\) 이면 MC 와 같아집니다.

그런데 식대로 \(G_t^\lambda\) 를 계산하려면 1-step 부터 끝까지 모든 n-step Return 을 다 더해야 합니다. 결국 또 에피소드가 끝나야 한다는 문제로 돌아오지요.

이걸 우회하기 위해 실제 구현에서는 eligibility trace 라는 보조 변수 \(e_t(s)\) 를 도입합니다. 상태마다 \(e_t(s)\) 를 하나씩 들고 다니면서, 매 스텝의 TD error \(\delta_t\) 한 번으로 "지금까지 방문한 모든 상태" 의 가치를 동시에 조금씩 갱신하는 방식입니다.

$$ e_t(s) = \begin{cases} \gamma \lambda \, e_{t-1}(s) + 1, & s = S_t \\ \gamma \lambda \, e_{t-1}(s), & s \ne S_t \end{cases} $$

$$ V(s) \leftarrow V(s) + \alpha \, \delta_t \, e_t(s) \quad (\text{모든 } s \text{에 대해}) $$

\(e_t(s)\) 는 상태 \(s\) 가 얼마나 최근에 방문되었는지를 나타내는 값입니다. 매 스텝 \(\gamma\lambda\) 비율로 조금씩 작아지다가, \(s\) 가 다시 방문되는 순간 \(+1\) 이 되지요. 그래서 방금 방문한 상태일수록 지금 일어난 TD error 에 대한 책임이 크고, 오래 전에 방문한 상태일수록 그 책임이 점점 잊혀집니다. 이렇게 하면 매 스텝마다 학습하면서도 결과적으로 λ-return 으로 갱신한 것과 같은 효과를 얻을 수 있습니다.

On Policy와 Off policy

지금까지는 한 종류의 정책만 가정했지만, 강화학습에서는 사실 정책을 두 갈래로 나눠 둘 수 있습니다. 하나는 환경에서 실제로 행동을 골라 데이터를 만들어 내는 정책 \(b\) 이고, 다른 하나는 우리가 최종적으로 학습하고 평가하고 싶은 정책 \(\pi\) 입니다. 앞쪽 \(b\) 를behavior policy \(\pi\) 를 target policy 이라고 부릅니다. 이 두 정책이 같으면 On-policy, 다르면 Off-policy 학습이라고 부르지요.

그러면 왜 굳이 정책을 두 개로 나눠 두는 걸까요?

On-policy 는 행동을 고르는 정책과 학습 대상인 정책이 똑같으니 흐름이 단순하고 직관적입니다. 다만 탐험을 위해 \(\epsilon\)-greedy 처럼 무작위성을 섞으면, 그 무작위성까지 같이 정책에 포함되어 학습된다는 점이 걸립니다. 즉 학습되는 것은 "진짜 최적 정책" 이 아니라 "약간 덜 greedy한 정책" 의 가치가 되지요.

Off-policy 는 행동과 학습을 분리해서 이 문제를 우회합니다. 데이터는 탐험 잘하는 \(b\) 가 마음껏 만들어 내고, 학습은 그와 다른 greedy한 \(\pi\) 에 대해 진행하지요. 이렇게 분리해 두면 한 정책으로 모은 데이터를 여러 다른 정책 평가에 재활용할 수 있고, 사람이나 다른 에이전트가 만든 경험으로부터도 학습할 수 있고, 탐험은 충분히 하면서 학습 대상은 깔끔한 정책으로 둘 수 있다는 자유가 생깁니다.

Importance Sampling

Off policy에서 \(b\) 가 만든 데이터를 그대로 \(\pi\) 의 가치 추정에 쓰면 두 정책이 행동을 고르는 비율이 달라서 \(b\) 가 자주 고른 행동의 영향력이 \(\pi\) 의 가치에 과하게 반영됩니다. 그래서 이 비율 차이를 보정해 주는 도구가 필요한데 이것이 바로 Importance Sampling(IS) 입니다.

 

원리는 단순합니다. 분포 \(\pi\) 에서의 평균을 알고 싶은데 표본은 다른 분포 \(b\) 에서만 뽑을 수 있는 상황을 떠올려 봅시다. \(b\) 의 표본 평균을 그대로 쓰면 당연히 \(b\) 의 평균이 나오지, \(\pi\) 의 평균이 안 나옵니다. 그래서 각 표본에 \(\pi(x) / b(x)\) 라는 가중치를 곱해서 차이를 보정해 주는 것이 IS 의 아이디어입니다.

$$\mathbb{E}_{\pi}[X] = \mathbb{E}_{b}\!\left[ \frac{\pi(X)}{b(X)} \, X \right]$$

여기서 가중치 \(\rho = \pi(x) / b(x)\) 를 importance sampling ratio 라고 부릅니다. 직관도 단순합니다. \(\pi\) 가 자주 만들 만한 표본이면 ratio 가 커져서 더 무겁게 반영되고, 반대로 \(\pi\) 는 잘 안 만드는데 \(b\) 가 자주 만든 표본이면 ratio 가 작아져서 가볍게 반영됩니다.

강화학습에서는 한 스텝이 아니라 시점 \(t\) 부터 에피소드 끝까지의 trajectory 전체에 대해 ratio 를 계산합니다. 매 스텝의 ratio 를 모두 곱해서 누적해야 하지요.

$$\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}$$

그런데 이 "곱하기" 에서 문제가 생깁니다. trajectory 가 길어질수록 두 정책이 조금만 달라도 ratio 가 폭발하거나 0 으로 사라지고, 그 결과 추정값이 한쪽으로 크게 치우치거나 0에 가까워져 버립니다. 그래서 실전에서는 ratio 변동을 줄여 주는 weighted IS 같은 변형을 쓰거나, 아예 IS 자체가 필요 없는 알고리즘을 쓰는 편입니다. 대표적인 게 뒤에 나올 Q-learning 이지요.

SARSA

SARSA는 On Policy TD 방식입니다. 이름 자체가 알고리즘 형태를 그대로 알려 주는데, 한 번 업데이트하는 데 \(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}\) 다섯 양이 모두 필요해서 SARSA 입니다.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \big]$$

식 모양은 앞에서 본 TD(0) 의 가치 함수 업데이트와 똑같이 생겼습니다. 차이는 두 가지입니다. 첫째로 상태 가치 \(V(S_t)\) 가 아니라 행동 가치 \(Q(S_t, A_t)\) 를 갱신한다는 점, 둘째로 TD target 자리에 \(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\) 이 들어간다는 점이지요. 여기서 \(A_{t+1}\) 은 정책 \(\pi\) 가 다음 상태 \(S_{t+1}\) 에서 실제로 고른 행동입니다.

SARSA가 On Policy인 이유는 행동을 고르는 것도 정책 \(\pi\) 이고 (보통 \(\epsilon\)-greedy), 학습 target에 들어가는 \(A_{t+1}\) 도 그 \(\pi\) 가 다음 스텝에 실제로 고른 행동이기 때문입니다. 즉 Behavior Policy와 Target Policy가 동일한 \(\pi\) 가 되니까 On-policy 인 것이지요.

이 일치 때문에 SARSA 가 학습하는 \(Q\) 는 사실 "완전 Greedy 정책" 의 가치가 아니라 "\(\epsilon\)-greedy 정책" 의 가치입니다. 즉 학습되는 가치 안에 탐험 위험까지 같이 들어가 있어요. 

Q-Learning

Q-learning 은 가장 유명한 Off-policy TD 방식입니다. SARSA 와 식이 거의 같은데, Target 한 곳에서만 한 글자가 바뀝니다.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t) \big]$$

바뀐 부분은 target의 두 번째 항입니다. SARSA 는 다음 스텝에 실제로 고른 행동의 가치 \(Q(S_{t+1}, A_{t+1})\) 을 썼지만, Q-learning 은 다음 상태에서 가능한 모든 행동 중 가장 좋은 값 \(\max_a Q(S_{t+1}, a)\) 을 씁니다. 즉 다음 스텝에 실제로 어떤 행동을 골랐든 상관없이, "그 상태에서 최선을 골랐다면 얼마였을까?" 를 임시 정답으로 삼는 것이지요.

\(\max_a\) 가 들어가는 순간, target은 더 이상 Behavior Policy \(b\) 가 다음에 무엇을 고를지에 의존하지 않습니다. 행동은 \(\epsilon\)-greedy 같은 탐험적인 \(b\) 로 마음껏 굴리되, 학습 target은 항상 그리디 정책 \(\pi(s) = \arg\max_a Q(s, a)\) 의 가치를 향해 갱신되는 셈이지요. Behavior Policy와 Target Policy가 다르니 Off-policy 입니다.

여기서 한 가지 깔끔한 점은 Q-learning 이 Importance Sampling 없이도 안전하게 학습할 수 있다는 사실입니다. 앞 절에서 IS 가 필요했던 이유는 표본 분포가 \(b\) 와 \(\pi\) 사이에서 어긋났기 때문인데, Q-learning 의 Target \(\max_a Q(S_{t+1}, a)\) 은 \(S_{t+1}\) 만 주어지면 곧장 결정되는 값입니다. 그리고 \(S_{t+1}\) 이 어떤 확률로 등장하는지는 환경의 전이 확률이 정하지 Behavior Policy가 정하지 않습니다. 그래서 비율 보정이 필요 없고, IS 의 분산 폭발 문제로부터도 자유롭습니다. 이게 Q-learning 이 DQN 같은 딥 강화학습의 출발점이 된 큰 이유 중 하나입니다.

SARSA와 Q-Learning 비교

이후 SARSA와 Q-learning의 차이를 설명하기 위해 등장하는 표준 예시가 cliff walking입니다. 아래 빨간색 x 표시의 셀은 절벽이라고 생각해 주시면 됩니다. 

 

그럼 왜 SARSA는 안전한 경로를 택하고 Q-Learning은 최단 경로를 택할까요?

이 질문은 한 1분만 생각해보시길 추천합니다! 생각보다 어렵지 않거든요

 

SARSA의 경우 \(\epsilon\)-greedy 정책으로 에이전트가 행동한다면 절벽 바로 옆에서 가끔식 무작위로 행동하는데 그게 절벽으로 떨어지는 결과를 초래하다 보니 그런 경험(에피소드)을 몇번 하다 보니 절벽 근처는 얼씬도 못하는 에이전트가 되버렸습니다.

반대로 Q-Learning의 경우 Behavior Policy가 데이터 수집 단계에서 절벽에 몇번 떨어졌더라도 결국 에이전트가 최종적으로 따르는 정책인 Target Policy는 greedy하게 이동하므로 최단 경로를 이동하는 에이전트가 됬습니다.