[강화학습] 5. TD 학습, 핵심편

지난 글에서 몬테카를로는 훌륭한 성질을 하나 갖고 있었다. 모델을 몰라도 된다는 것. 대신 치명적인 제약이 붙었다. 에피소드가 끝나야만 배운다.

그리고 마지막에 이런 표를 봤다. 동적 계획법과 몬테카를로는 거의 정반대의 장단점을 갖고 있었다.

	모델 필요	끝까지 가야 함
동적 계획법	필요	아니오
몬테카를로	불필요	예
???	불필요	아니오

빈칸이 하나 남아 있다. 모델도 필요 없고 끝까지 가지도 않는 방법. 그게 TD 학습(Temporal Difference learning)이고, 많은 사람이 강화학습에서 가장 중요한 아이디어로 꼽는 것이다.

---

1. 두 세계에서 좋은 것만 가져오기

동적 계획법이 끝까지 안 가도 됐던 이유가 뭐였나. 다음 상태의 가치 $v(s')$를 이미 알고 있다고 치고 썼기 때문이다.

$$v(s) \leftarrow \sum_{a} \pi(a \mid s) \sum_{s'} p(s' \mid s, a)\big[r + \gamma v(s')\big]$$

여기서 우변의 $v(s')$는 정답이 아니다. 지금까지 계산해둔 추정치다. 추정치를 가지고 추정치를 고치는 것 — 이걸 부트스트래핑(bootstrapping)이라 부른다. 자기 신발끈을 잡아당겨 스스로를 들어올린다는 관용구에서 온 말이다.

몬테카를로는 이걸 안 한다. 실제로 받은 보상만 더한다. 정직하지만 느리다. 세 방법의 위치를 한눈에 보면 이렇다.

그림 1. TD는 남아 있던 빈칸을 채운다

그렇다면 이렇게 하면 어떨까. 기댓값 계산은 몬테카를로처럼 실제 경험 하나로 대신하고, 그 다음은 동적 계획법처럼 추정치를 갖다 쓴다.

---

2. 핵심 아이디어: 목표값만 바꾼다

지난 글에서 갱신식의 구조를 눈에 익혀두라고 했다. 이런 모양이었다.

$$\text{새 추정} \leftarrow \text{옛 추정} + \alpha\big[\text{목표값} - \text{옛 추정}\big]$$

몬테카를로는 목표값 자리에 실제 리턴 $G_t$를 넣었다. 그런데 $G_t$를 알려면 에피소드 끝까지 가야 한다. 문제는 오직 그것뿐이다.

그러니 목표값을 바꾸자. 리턴의 재귀식을 떠올리면 된다.

$$G_t = R_{t+1} + \gamma G_{t+1}$$

미래의 리턴 $G_{t+1}$을 우리가 이미 갖고 있는 추정치 $V(S_{t+1})$로 바꿔치기한다.

$$G_t \;\approx\; R_{t+1} + \gamma V(S_{t+1})$$

이 우변은 한 스텝만 가면 전부 알 수 있다. 보상 $R_{t+1}$ 하나 받고, 다음 상태 $S_{t+1}$이 무엇인지만 보면 된다. 에피소드의 끝을 기다릴 이유가 사라졌다.

그림 2. 어디까지 보고 되돌리는가 — 이 하나가 두 방법의 전부다

출근길 비유. 집에서 회사까지 40분 걸린다고 예상했다고 하자.

몬테카를로식: 회사에 도착해서 시계를 본다. 47분 걸렸다. "다음부터는 좀 더 잡아야겠군." 도착하기 전까지는 아무것도 배우지 못한다.

TD식: 5분 만에 첫 사거리에 도착했는데, 평소 이 사거리에서 회사까지가 38분이다. 그러면 지금 시점의 예상은 5 + 38 = 43분. 처음 예상 40분보다 3분 늘었다. 회사에 도착하기 전에, 사거리에서 이미 예상을 고친다.

사람은 실제로 이렇게 산다. 최종 결과를 기다렸다가 배우는 게 아니라, 상황이 바뀔 때마다 예상을 갱신한다. TD는 그걸 수식으로 옮긴 것이다.

---

3. 수식으로 정리하기

TD(0) 갱신식

목표값을 바꾼 것 말고는 몬테카를로와 완전히 같다.

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

$V$는 우리의 추정값, $\alpha$는 학습률(한 번에 얼마나 옮길지), $\gamma$는 할인율이다. 대괄호 안이 목표값에서 현재 추정을 뺀 것, 즉 오차다. 이름을 붙여둔다.

$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$$

$\delta$(델타)는 TD 오차(TD error)다. 앞으로 이 시리즈 내내 등장한다. "(0)"이라는 이름은 한 스텝만 본다는 뜻인데, 그 의미는 다음 글에서 밝혀진다.

이게 어디서 나온 식인가

2편의 벨만 기대 방정식을 다시 보자.

$$v_\pi(s) = \mathbb{E}_\pi\big[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s\big]$$

이 방정식이 성립하면 좌변과 우변이 같다. 그런데 우리 추정값 $V$는 아직 정답이 아니므로 좌우가 어긋난다. 그 어긋난 정도가 정확히 $\delta_t$다.

TD 오차는 벨만 방정식의 잔차다. 방정식이 성립하면 0이고, 성립하지 않는 만큼 그쪽으로 조금씩 옮겨간다. 2편에서 "강화학습 알고리즘은 벨만 방정식의 고정점을 찾아가는 반복"이라고 했던 말이 여기서 코드가 된다.

두 목표값 비교

	몬테카를로	TD(0)
목표값	$G_t$	$R_{t+1} + \gamma V(S_{t+1})$
필요한 것	에피소드 전체	한 스텝
갱신 시점	에피소드 종료 후	매 스텝 즉시
정확성	실제 값	추정 섞임

---

4. 손으로 돌려보기

3편부터 써온 4칸 복도를 그대로 쓴다.

무작위 정책의 참값은 $v_\pi = (-12,\ -10,\ -6)$이었다. 이번엔 같은 에피소드 하나를 두 방법에 똑같이 먹여서 무슨 일이 벌어지는지 본다.

그림 3. 두 방법에 똑같이 먹일 에피소드

시작값은 모두 $V = 0$, 학습률은 $\alpha = 0.1$로 둔다.

몬테카를로 — 끝나고 나서 한꺼번에

리턴은 뒤에서부터 계산한다. $G(\text{S3}) = -1$, $G(\text{S2}) = -2$, $G(\text{S1}) = -3$. 에피소드가 끝난 뒤 세 상태를 갱신한다.

$$V(\text{S1}) \leftarrow 0 + 0.1\,(-3 - 0) = -0.3$$

같은 방식으로 $V(\text{S2}) = -0.2$, $V(\text{S3}) = -0.1$이 된다.

TD(0) — 걸어가면서 한 걸음씩

이쪽은 이동할 때마다 즉시 갱신한다. 목표값은 받은 보상 + 다음 상태의 현재 추정이다.

시점	갱신 대상	목표값	새 $V$
$t=0$	S1	$-1 + V(\text{S2}) = -1$	−0.1
$t=1$	S2	$-1 + V(\text{S3}) = -1$	−0.1
$t=2$	S3	$-1 + 0 = -1$	−0.1

갱신이 언제 일어나는지를 시간축에 놓고 보면 차이가 더 분명하다.

그림 4. 같은 에피소드, 다른 갱신 시점

에피소드 1 이후 비교

상태	몬테카를로	TD(0)
S1	−0.3	−0.1
S2	−0.2	−0.1
S3	−0.1	−0.1

TD는 세 값이 전부 같다. 처음엔 모든 추정이 0이라 "다음 상태는 0점"이라고 믿고 갱신했기 때문이다. 아직 종료 지점의 정보가 뒤로 전파되지 않았다.

같은 에피소드를 한 번 더

이번엔 다르다. TD의 목표값에 이제 0이 아닌 값이 들어간다.

시점	대상	목표값	새 $V$
$t=0$	S1	$-1 + (-0.1) = -1.1$	−0.2
$t=1$	S2	$-1 + (-0.1) = -1.1$	−0.2
$t=2$	S3	$-1 + 0 = -1$	−0.19

상태	몬테카를로	TD(0)
S1	−0.57	−0.2
S2	−0.38	−0.2
S3	−0.19	−0.19

여기서 볼 것 세 가지

첫째, S3에서 두 값이 정확히 같다. 우연이 아니다. S3에서 한 걸음이면 에피소드가 끝나므로, "받은 보상 + 다음 상태 추정"과 "실제 리턴"이 같은 숫자다. 종료 직전 상태에서 TD와 MC는 항상 일치한다. 두 방법의 차이는 오직 "그 다음이 얼마나 남았는가"에서 나온다.

둘째, TD는 정보가 한 번에 한 칸씩 뒤로 간다. 3편의 Value Iteration에서 봤던 것과 똑같은 현상이다. 부트스트래핑하는 방법의 숙명이다.

셋째, 이 예제만 보면 MC가 참값에 더 빨리 다가간다. 참값이 $-12$인데 MC는 $-0.57$, TD는 $-0.2$다. 그런데 이건 이 에피소드가 유난히 짧았기 때문이다. 무작위 정책은 평균 12걸음을 헤매는데 여기선 3걸음 만에 끝났다. MC는 그 운 좋은 결과를 통째로 믿고 크게 움직였다. 다음 절이 이 이야기다.

---

5. 왜 TD가 더 좋은가 — 편향과 분산

지난 글의 과녁 비유를 다시 꺼내자. 편향은 화살들의 중심이 정중앙에서 벗어난 정도, 분산은 화살들이 흩어진 정도였다.

그림 5. 편향은 중심에서 벗어난 정도, 분산은 흩어진 정도

TD는 편향이 있다

목표값 $R_{t+1} + \gamma V(S_{t+1})$ 안의 $V(S_{t+1})$은 추정값이다. 그게 틀렸다면 목표값도 틀린다. 몬테카를로의 리턴은 실제로 받은 값이라 이런 문제가 없었다.

대신 분산이 훨씬 작다

몬테카를로의 리턴 하나에는 에피소드 전체의 우연이 다 들어 있다. 100스텝이면 100번의 행동 선택과 100번의 환경 반응이 그 숫자 하나에 녹아 있다.

TD의 목표값에 들어 있는 무작위성은 딱 한 스텝치다. 행동 한 번, 전이 한 번. 흔들릴 여지가 비교할 수 없이 적다.

실전에서는 대체로 TD가 이긴다. 편향은 학습이 진행되며 $V$가 정확해지면 저절로 줄어들지만, 분산은 표본을 $\sqrt{N}$배로 늘려야만 줄어들기 때문이다. 그리고 두 방법 모두 $\alpha$를 적절히 줄여가면 참값 $v_\pi$로 수렴한다는 것이 증명되어 있다.

둘은 애초에 다른 답을 찾는다

편향/분산보다 더 근본적인 차이가 있다. 유명한 예제로 보자. 상태가 A, B 두 개이고, 에피소드 8개를 관측했다.

  A → 0 → B → 0      (1회)
  B → 1              (6회)
  B → 0              (1회)

화살표 위 숫자는 보상이다. $V(\text{B})$는 둘 다 동의한다. B를 8번 봤고 보상 합이 6이니 $6/8 = 0.75$.

문제는 $V(\text{A})$다. A는 딱 한 번 나왔고, 그때 받은 보상 총합은 0이었다.

	$V(\text{A})$	근거
몬테카를로	0	A에서 시작한 유일한 경험의 리턴이 0이었다
TD(0)	0.75	A 다음엔 항상 B였고, $V(\text{B}) = 0.75$이니 $0 + 0.75$

둘 다 나름의 논리가 있다. 몬테카를로는 본 것에만 충실하고, TD는 본 것으로 세상의 구조를 짜맞춘 뒤 그 구조에 충실하다. "A 다음엔 B가 온다"는 구조를 TD는 활용하고 MC는 무시한다.

미래에도 이 구조가 유지된다면 TD의 답이 낫다. 그래서 TD가 실전에서 더 빨리 배운다. 다만 이 이점은 상태가 마르코프 성질을 만족한다는 전제에 기대고 있다. 지난 글에서 몬테카를로의 장점으로 꼽았던 "마르코프 성질이 필요 없다"의 뒷면이다.

---

6. 구현

from collections import defaultdict

def td0_prediction(env, policy, gamma, alpha, n_episodes):
    V = defaultdict(float)
    for _ in range(n_episodes):
        s = env.reset()
        done = False
        while not done:
            a = policy(s)
            s2, r, done = env.step(a)
            nxt = 0.0 if done else V[s2]
            V[s] += alpha * (r + gamma * nxt - V[s])
            s = s2                  # 매 스텝 즉시 갱신
    return V

지난 글의 몬테카를로 코드와 비교해보면 차이가 분명하다. 거기엔 에피소드를 통째로 모으는 리스트와, 끝난 뒤 거꾸로 훑는 루프가 있었다. 여기엔 없다. 루프 안에서 바로 갱신한다. 이 한 가지 차이가 TD를 연속 태스크와 온라인 학습에 쓸 수 있게 만든다.

---

7. 제어로 넘어가기: SARSA와 Q-learning

여기까지는 주어진 정책을 평가만 했다. 정책을 개선하려면 지난 글에서 본 대로 $V$가 아니라 $Q$를 추정해야 한다. 모델 없이 $\arg\max$를 취하려면 $Q$가 필요하기 때문이다.

$Q$에 TD를 적용하는 순간, 답이 갈린다. 목표값 안의 다음 행동을 무엇으로 할 것인가.

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]$$

$A_{t+1}$은 다음 스텝에 실제로 고른 행동이다. 탐험 때문에 무작위 행동을 골랐다면 그 행동의 값이 그대로 목표에 들어간다. 이름은 갱신에 쓰이는 다섯 개를 순서대로 읽은 것이다 — 상태, 행동, 보상, 다음 상태, 다음 행동.

Q-learning — 가장 좋은 행동을 쓴다

$$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]$$

실제로 무슨 행동을 했든 상관없이, 다음 상태에서 가능한 행동 중 가장 좋은 것의 값을 쓴다. 같은 상황에서 두 알고리즘이 서로 다른 칸을 집어 든다.

그림 6. 목표값에 무엇을 넣는가가 두 알고리즘을 가른다

2편의 표가 여기서 회수된다

2편에서 벨만 방정식에 두 형태가 있다고 했다. 정책의 평균을 취하는 기대형과 최댓값을 취하는 최적형. 그 구분이 그대로 알고리즘이 됐다.

알고리즘	다음 행동	벨만 형태
SARSA	$A_{t+1} \sim \pi$	기대형
Q-learning	$\max_a$	최적형

왜 Q-learning은 중요도 샘플링이 필요 없나

지난 글에서 남겨둔 질문이다. 몬테카를로로 오프폴리시를 하려면 확률 비를 궤적 길이만큼 곱해야 했고, 그래서 분산이 폭발했다.

Q-learning의 목표값을 다시 보자. $R_{t+1} + \gamma \max_a Q(S_{t+1}, a)$. 여기에 행동 정책 $\pi$가 등장하지 않는다. $\max$가 정책을 지워버렸기 때문이다.

보정할 것이 없으니 비를 곱할 일도 없다. 어떤 정책으로 모은 데이터든 그대로 쓸 수 있다. 이것이 Q-learning이 오프폴리시의 대표가 되고, 나중에 리플레이 버퍼를 쓰는 DQN으로 이어지는 이유다.

---

8. 절벽 걷기: 두 알고리즘이 다른 길을 배운다

차이를 가장 선명하게 보여주는 고전 예제가 있다. 아래쪽 한 줄이 절벽이고, 빠지면 큰 벌점과 함께 출발점으로 돌아간다.

그림 7. 같은 문제, 다른 답

왜 이런 차이가 나는가

가장자리 칸에 서 있다고 하자. 탐험 때문에 가끔 무작위 행동이 나오고, 그러면 절벽으로 떨어진다.

SARSA의 목표값에는 실제로 고른 다음 행동이 들어간다. 무작위로 절벽에 빠진 그 경험이 목표값에 그대로 반영된다. 그래서 SARSA는 "가장자리는 위험한 자리"라고 배운다. 자신이 탐험한다는 사실을 계산에 넣는 것이다.

Q-learning의 목표값에는 $\max$가 들어간다. 다음 상태에서 완벽하게 행동한다면 얼마인지를 쓴다. 자기가 가끔 실수로 떨어진다는 사실을 목표값에 반영하지 않는다. 그래서 "완벽히만 걸으면 가장자리가 최선"이라고 배운다.

그래서 누가 맞나

둘 다 맞다. 다른 질문에 답하고 있을 뿐이다.

	배우는 것	학습 중 성적
Q-learning	진짜 최적 정책 $\pi_*$	나쁨 (자주 떨어짐)
SARSA	ε만큼 실수하는 조건의 최적	좋음 (덜 떨어짐)

학습이 끝나고 탐험을 끄면 Q-learning의 정책이 더 낫다. 하지만 학습하는 동안 받는 보상은 SARSA가 더 좋다.

이 구분은 실제 로봇에서 특히 중요하다. 시뮬레이터라면 절벽에 백만 번 떨어져도 상관없다. 실제 기체라면 한 번의 추락이 프로젝트의 끝이다. 학습 과정 자체가 안전해야 하는 상황에서는 온폴리시 계열이 유리하다.

---

9. 실무에서 걸리는 것들

최대화 편향

Q-learning의 $\max$에는 숨은 함정이 있다. $Q$가 추정값이라 노이즈가 섞여 있는데, 그중 최댓값을 고르면 노이즈가 큰 쪽이 뽑히기 쉽다. 여러 사람의 어림값 중 가장 큰 것을 고르면 대체로 과장된 값이 뽑히는 것과 같다.

2편에서 짚었던 부등식이 이것이다.

$$\mathbb{E}\big[\max_a X_a\big] \;\ge\; \max_a \mathbb{E}\big[X_a\big]$$

그 결과 Q-learning은 값을 체계적으로 과대추정한다. 해법인 Double Q-learning은 10편에서 다룬다.

학습률 설정

$\alpha$가 크면 최근 경험에 휘둘려 값이 요동친다. 작으면 학습이 기어간다. 이론적 수렴 조건은 $\alpha$를 점점 줄이는 것이지만, 실제로는 정책이 계속 바뀌므로 작은 고정값(0.01~0.1)을 쓰는 경우가 많다.

마르코프 성질에 기댄다

TD는 $V(S_{t+1})$이 "그 상태 이후의 모든 것"을 제대로 요약한다고 믿는다. 상태가 마르코프가 아니면 그 믿음이 깨진다. 1편에서 강조했듯 실제 로봇 문제는 대부분 엄밀히는 부분관측이다. 속도를 상태에 넣었는지, 프레임을 몇 장 쌓았는지가 TD 계열의 성패를 가른다.

---

10. 한 장 요약

	DP	MC	TD
모델 필요	예	아니오	아니오
부트스트랩	예	아니오	예
끝까지 대기	—	예	아니오
편향	없음	없음	있음
분산	없음	큼	작음
연속 태스크	가능	불가	가능
마르코프 의존	강함	없음	강함

서두의 빈칸이 채워졌다. TD는 모델도 필요 없고 끝까지 가지도 않는다. 온라인으로 배우고, 연속 태스크에서도 돌아가며, 오프폴리시도 된다. 이후 이 시리즈에 나오는 거의 모든 알고리즘이 TD 위에 서 있다.

그런데 아직 답하지 않은 질문이 있다. TD는 한 스텝만 보고, 몬테카를로는 끝까지 본다. 둘 사이에 두 스텝, 세 스텝은 없을까? 그리고 그중 어디가 가장 좋을까?

있다. 그리고 그 사이를 연속적으로 조절하는 다이얼이 존재한다. 다음 글의 주제다.

---

11. 확인 문제

1. 4칸 복도 예제에서 $\alpha = 0.5$로 바꾸면 TD(0)의 에피소드 1 이후 값은 얼마인가?
2. S3에서 TD와 MC의 갱신 결과가 항상 같은 이유를 한 문장으로 써보라.
3. A/B 예제에서 만약 A가 두 번 관측되었고 두 번째는 $A \to 0 \to B \to 1$이었다면, MC와 TD의 $V(\text{A})$는 각각 어떻게 바뀌는가?
4. SARSA를 쓰면서 탐험률 $\varepsilon$을 0으로 줄여가면 어떤 정책으로 수렴하는가? Q-learning과 같아지는가?
5. 실제 로봇에 강화학습을 적용할 때 SARSA와 Q-learning 중 무엇을 고르겠는가? 8절의 논의를 근거로 답해보라.

---

참고 자료

• Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.) — 6장 전체. 6.3(A/B 예제), 6.5(Q-learning), 6.6(절벽 걷기), 6.7(최대화 편향)
• David Silver, UCL RL Course — Lecture 4 후반부, Lecture 5
• Watkins & Dayan (1992), Q-learning — 수렴 증명의 원전

← 이전 · #4 몬테카를로: 끝까지 가보고 배우기 다음 · #6 TD(λ)와 적격 흔적 (준비 중)