시간차 학습

1. 개요[편집]

시간차 학습(Temporal-Difference learning, TD 학습)은 에피소드가 끝날 때까지 기다리지 않고, 한 스텝 뒤의 자기 자신의 추정값을 목표로 삼아 가치함수를 갱신하는 강화학습 기법이다. 한마디로 “추측을 추측으로 갱신한다”(learning a guess from a guess).¹ 가장 단순한 형태인 TD(0)의 갱신식은 다음과 같다.

$$V(S_t) \leftarrow V(S_t) + \alpha \left[\, \underbrace{R_{t+1} + \gamma V(S_{t+1})}_{\text{TD 목표}} - V(S_t) \,\right]$$

여기서 대괄호 안의 값이 TD 오차다.

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

$\delta_t$ 는 “이번에 실제로 받은 보상 + 다음 상태의 현재 추정”과 “지금 상태의 현재 추정”의 불일치다. 벨만 방정식 $v_\pi(s) = \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s]$ 이 성립하면 $\mathbb{E}[\delta_t] = 0$ 이므로, TD는 벨만 방정식의 잔차를 표본으로 줄여나가는 확률적 근사법이다. 강화 학습의 심장부이자, 실전 알고리즘 대부분의 갱신 규칙이 결국 이 한 줄에서 파생된다.

2. 부트스트래핑 — DP와 MC 사이[편집]

정책 $\pi$ 의 상태가치 $v_\pi$ 를 구하는 방법은 크게 세 갈래다.

방법	목표값	모델 필요	갱신 시점
동적 계획법 (DP)	$\sum_{s',r} p(s',r \mid s,\pi(s))\,[r + \gamma V(s')]$	필요 (전이확률 전부)	전체 기댓값 백업
몬테카를로 (MC)	실제 수익 $G_t$	불필요	에피소드 종료 후
시간차 (TD)	$R_{t+1} + \gamma V(S_{t+1})$	불필요	매 스텝

동적 계획법은 모델 $p(s', r \mid s, a)$ 를 전부 알아야 하지만 기댓값을 정확히 계산한다. MC는 모델이 필요 없지만 에피소드가 끝나야 하고, 종료하지 않는 연속 과제에는 아예 쓸 수 없다. TD는 모델 없이(MC처럼) + 기존 추정을 재활용해서(DP처럼) 매 스텝 갱신한다. 이 “기존 추정을 목표에 끼워 넣는” 성질이 부트스트래핑이며, TD가 DP와 MC의 중간 지점이라 불리는 이유다.

부트스트래핑의 실질적 이득은 크다. 격자 세계에서 절벽으로 떨어지는 궤적을 한 번 겪으면, MC는 그 에피소드의 모든 상태에 사후 수익을 뿌리는 반면 TD는 절벽 직전 상태의 가치를 즉시 낮춘다. 그 낮아진 값이 다음 에피소드에서 한 칸 앞 상태로, 그다음엔 두 칸 앞으로 전파된다. 마르코프 결정 과정의 구조를 갱신 규칙이 직접 활용하는 셈.

3. 편향-분산 트레이드오프[편집]

MC의 목표 $G_t$ 는 $v_\pi(S_t)$ 의 불편(unbiased) 추정량이다. 대신 하나의 수익에 에피소드 내내 벌어진 모든 확률적 전이와 보상의 잡음이 누적돼 분산이 크다. TD의 목표 $R_{t+1} + \gamma V(S_{t+1})$ 은 무작위성이 딱 한 스텝치뿐이라 분산이 훨씬 작지만, $V(S_{t+1})$ 이 아직 틀린 추정이므로 편향이 있다.

실무적으로는 TD가 이긴다. 이를 보이는 고전적 시험대가 5-상태 무작위 보행이다. 상태 A~E가 일렬로 놓이고 매 스텝 좌우로 등확률 이동, 왼쪽 끝으로 나가면 보상 0, 오른쪽 끝으로 나가면 보상 1로 종료한다. $\gamma = 1$ 일 때 참값은 각 상태에서 오른쪽으로 나갈 확률 그대로 $1/6,\, 2/6,\, \ldots,\, 5/6$ 이다. 같은 궤적을 TD(0)와 상수-$\alpha$ MC에 먹여보면, 웬만한 $\alpha$ 범위에서 TD 쪽 RMS 오차 곡선이 더 빨리 내려가고 더 낮은 바닥에 눕는다. 표 형식(tabular) 문제에서 두 방법 모두 수렴하지만, TD가 대체로 훨씬 빨리 낮은 RMS 오차에 도달한다. 다만 이유가 미묘한데, 유한한 데이터에 대해 두 방법의 수렴점이 다르다. 배치(batch) 학습에서 MC는 관측된 수익의 제곱오차를 최소화하는 값으로 수렴하고, TD(0)는 데이터로부터 추정한 MDP(최대우도 모델)의 정확한 가치함수로 수렴한다. 후자를 확실성 등가 추정(certainty-equivalence estimate)이라 부르며, 데이터가 실제로 마르코프 성질을 가질 때 더 좋은 예측을 준다.

4. TD(λ)와 적격 흔적[편집]

한 스텝만 볼 이유도, 끝까지 볼 이유도 없다. $n$-스텝 수익

$$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$$

을 놓고 보면 $n = 1$ 이 TD(0), $n = \infty$ 가 MC다. 이걸 기하가중으로 전부 섞은 것이 λ-수익이다.

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

$\lambda = 0$ 이면 TD(0), $\lambda = 1$ 이면 MC. 이 정의를 그대로 쓰면 미래를 알아야 하므로(전방 관점, forward view) 온라인 구현이 안 된다. 그래서 적격 흔적(eligibility trace)을 쓰는 후방 관점(backward view)으로 바꾼다. 각 상태마다 “최근에 얼마나 방문했는가”를 기록하는 흔적

$$z_t = \gamma \lambda z_{t-1} + \nabla_w \hat{v}(S_t, w)$$

을 유지하고, 매 스텝 TD 오차 하나를 흔적 전체에 곱해 뿌린다: $w \leftarrow w + \alpha \delta_t z_t$. 오프라인 갱신 기준으로 두 관점은 정확히 같은 결과를 내며(오프라인 λ-수익 등가 정리), 온라인에서도 엄밀한 등가를 원하면 참 온라인 TD(λ)를 쓴다. 흔적 덕분에 메모리 $O(|w|)$ 만으로 여러 스텝짜리 크레딧 할당을 해내는 게 핵심이다.

5. 수렴 조건과 죽음의 삼중주[편집]

• 표 형식 — 각 상태가 무한히 자주 방문되고 학습률이 로빈스-먼로 조건 $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$ 를 만족하면 TD(0)는 $v_\pi$ 로 확률 1 수렴한다. 상수 $\alpha$ 는 수렴하지 않고 참값 주위를 진동하지만, 비정상 환경에서는 그게 오히려 장점이다.
• 선형 함수근사 + 온폴리시 — $\hat{v}(s,w) = w^\top \phi(s)$ 이고 데이터가 정책 $\pi$ 의 정상분포 $d_\pi$ 에서 나오면 TD(0)는 TD 고정점 $w_\text{TD}$ 로 수렴하며, 오차는 최선 근사와 상수배 이내로 묶인다.

$$\lVert \hat{v}_{w_\text{TD}} - v_\pi \rVert_{d_\pi} \le \frac{1}{1 - \gamma} \min_{w} \lVert \hat{v}_{w} - v_\pi \rVert_{d_\pi}$$

• 죽음의 삼중주(deadly triad) — ① 함수근사, ② 부트스트래핑, ③ 오프폴리시 학습, 이 셋이 동시에 걸리면 발산할 수 있다. 세 개 중 하나만 빼도 안전한데, 하필 딥 강화학습이 셋을 다 쓴다. 베어드(Baird)의 반례는 보상이 전부 0인데도 가중치가 지수적으로 발산하는 것을 보여준다. 완화책으로 목표망(target network), 경험 재생, 그래디언트 TD 계열(GTD/TDC), 강조 TD(emphatic TD) 등이 쓰인다.

비선형 함수근사에서는 이런 보장이 대부분 사라진다. 심층 학습을 얹은 순간부터 수렴은 사실상 경험칙과 하이퍼파라미터의 영역이 되며, 학습 곡선이 갑자기 무너지는 건 버그가 아니라 이론적 예고편일 수 있다.

6. 제어로의 확장 — SARSA와 Q러닝[편집]

가치 예측에서 제어로 넘어가려면 상태가치 $V(s)$ 대신 행동가치 $Q(s,a)$ 를 학습한다.

• SARSA (온폴리시): $Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t,A_t)\right]$. 목표에 실제로 취한 다음 행동 $A_{t+1}$ 이 들어간다. 즉 탐험까지 포함한 현재 행동정책의 가치를 배운다. 절벽 걷기 문제에서 SARSA가 절벽에서 한 칸 떨어진 안전한 우회로를 배우는 이유가 이것.
• Q러닝 (오프폴리시): 목표에 $\max_{a'} Q(S_{t+1}, a')$ 를 쓴다. 행동정책이 무엇이든 최적 가치 $q_*$ 를 향해 간다. 대신 $\varepsilon$-탐욕으로 걷다가 절벽에 떨어지는 사고를 계산에 넣지 않으므로, 학습 중 실제 성적은 SARSA보다 나쁠 수 있다.

두 갱신의 차이는 딱 한 항 — 기댓값을 행동정책으로 잡느냐 탐욕정책으로 잡느냐 — 인데, 여기서 온폴리시/오프폴리시라는 강화학습 최대의 분기점이 갈린다. 관측이 불완전한 경우로 넘어가면 부분관측 마르코프 결정 과정에서 믿음 상태 위의 TD를 다뤄야 한다. 가치가 아니라 정책 자체를 파라미터화하는 반대편 계보는 정책경사 문서로.

7. 여담 — 도파민[편집]

1990년대 신경과학에서 원숭이 중뇌 도파민 뉴런의 발화 패턴이 TD 오차 $\delta_t$ 와 놀랍도록 닮았다는 사실이 보고됐다. 예상보다 좋은 보상이 오면 발화가 증가하고, 예상대로면 변화가 없고, 예상한 보상이 안 오면 기저선 아래로 떨어진다.² 학습이 진행되면 발화 시점이 보상 자체가 아니라 보상을 예고하는 단서로 앞당겨지는데, 이는 TD에서 가치가 시간을 거슬러 전파되는 것과 정확히 같은 현상이다. 이 대응 덕분에 TD는 공학 알고리즘인 동시에 뇌의 보상 예측 오차 가설의 계산 모형이 됐다.³

8. 관련 문서[편집]

• 강화 학습 · 마르코프 결정 과정
• 동적 계획법 · 몬테카를로 방법
• Q러닝 · 정책경사
• 부분관측 마르코프 결정 과정
• 확률적 경사하강법 · 심층 학습
• SARSA · 적격 흔적

9. Footnotes[편집]

1. 서턴(R. Sutton)의 1988년 논문 Learning to Predict by the Methods of Temporal Differences가 출발점. 그 전신인 새뮤얼(A. Samuel)의 1959년 체커 프로그램은 이미 “다음 수의 평가값으로 지금 평가값을 고치는” 짓을 하고 있었다. 이름이 없었을 뿐. ↩

2. Schultz, Dayan & Montague (1997), Science. 요약하면 도파민은 “쾌감 신호”가 아니라 “예상보다 좋았음 신호”다. 기대치를 낮추면 행복해진다는 인터넷 밈에 신경과학적 근거가 생긴 순간. ↩

3. 물론 뇌가 진짜 $\alpha[\,R + \gamma V' - V\,]$ 를 계산한다는 뜻은 아니다. 다만 예측이 이렇게 잘 맞는 계산 모형이 흔치 않다는 게 이 가설이 30년째 살아 있는 이유다. ↩