TD Learning은 왜 MC와 DP 사이에 서 있는가

Monte Carlo는 정확하지만 느리고, Dynamic Programming은 빠르지만 모델이 필요하다. Temporal Difference(TD) 학습은 이 두 한계를 동시에 피한다 — 에피소드가 끝나기 전에 업데이트하고, 환경 모델 없이도 수렴한다. 그런데 이 “절충”이 단순한 타협이 아니라 하나의 일관된 설계 철학에서 나온다면?

Bootstrap — 자기 추정을 믿는 방법

TD(0)의 업데이트 규칙은 다음과 같다.

$$V_{t+1}(s_t) = V_t(s_t) + \alpha_t \bigl[R_{t+1} + \gamma V_t(s_{t+1}) - V_t(s_t)\bigr]$$

괄호 안의 $\delta_t = R_{t+1} + \gamma V_t(s_{t+1}) - V_t(s_t)$가 TD error다. 현재 보상 $R_{t+1}$은 실제로 관측한 값이고, $\gamma V_t(s_{t+1})$은 아직 불완전한 가치 추정치다. 이처럼 자기 자신의 추정을 다시 사용하는 것을 bootstrap이라 한다.

Bootstrap의 핵심 성질은 올바른 $V^\pi$ 하에서 TD error의 기댓값이 0이 된다는 것이다.

이 성질은 TD가 올바른 고정점을 향해 수렴한다는 보장의 씨앗이다. MC의 full return도 불편 추정량이지만, bootstrap은 분산을 극적으로 줄이는 대신 $V'$의 부정확성에서 오는 편향을 받아들인다.

수렴의 조건 — Robbins-Monro와 무한 방문

TD(0)가 “작동한다”는 것과 “수렴한다”는 것은 다른 주장이다. Tsitsiklis & Van Roy(1997)는 수렴의 충분 조건을 다음 세 가지로 정리했다.

첫째, 학습률이 Robbins-Monro 조건을 만족해야 한다.

$$\sum_{t=0}^{\infty} \alpha_t = \infty \qquad \text{그리고} \qquad \sum_{t=0}^{\infty} \alpha_t^2 < \infty$$

첫 번째 조건은 “충분히 오래 배울 것”을, 두 번째 조건은 “점점 천천히 배울 것”을 요구한다. $\alpha_t = 1/(t+1)$은 둘 다 만족하고, 상수 $\alpha = 0.1$은 두 번째 조건을 위반한다 — 그래서 상수 학습률 TD는 수렴이 아니라 진동한다.

둘째, 모든 상태를 무한히 자주 방문해야 한다. 방문하지 않은 상태의 가치는 갱신되지 않기 때문이다.

셋째, 보상이 유계여야 한다.

이 세 조건이 만족되면 $V_t(s) \to V^\pi(s)$ almost surely다. 수렴의 엔진은 Bellman expectation operator $T^\pi$의 $\gamma$-contraction 성질이다.

$$\|T^\pi V - T^\pi V'\|_\infty \leq \gamma \|V - V'\|_\infty$$

유일한 고정점이 존재하기 때문에 확률적 추적이 의미를 갖는다.

On-Policy vs Off-Policy — SARSA가 안전한 이유

TD(0)가 가치 함수를 학습한다면, SARSA는 이를 제어(control)로 확장한다. 이름 자체가 업데이트에 들어가는 튜플을 기술한다: State-Action-Reward-State-Action.

$$Q_{t+1}(s_t, a_t) = Q_t(s_t, a_t) + \alpha\bigl[R_{t+1} + \gamma Q_t(s_{t+1}, a_{t+1}) - Q_t(s_t, a_t)\bigr]$$

여기서 $a_{t+1} \sim \pi(\cdot \mid s_{t+1})$은 학습 중인 정책에서 실제로 샘플한 행동이다. 이것이 on-policy의 의미 — 행동 정책과 목표 정책이 동일하다.

반면 Q-Learning은 $\max_{a'} Q(s_{t+1}, a')$를 사용한다. 탐험 중에 취한 랜덤 행동이 학습 목표에 영향을 주지 않는다. Sutton & Barto의 Cliff Walking 예제는 이 차이를 극명하게 보여준다.

Goal ◄─────────────── Q-Learning (최적, 절벽 위)
Goal ◄──────────────────── SARSA (안전, 한 칸 위)
     ██████ CLIFF ████████ (-100)

$\epsilon$-greedy로 탐험하는 SARSA는 가끔 절벽 옆으로 미끄러질 가능성을 학습에 반영한다. 그래서 더 안전한 경로를 선택한다. Q-Learning은 탐험과 무관하게 최적 정책을 향하지만, 실행 중에 $\epsilon$ 확률로 떨어진다.

SARSA가 $Q^*$로 수렴하려면 GLIE(Greedy in the Limit with Infinite Exploration) 조건이 필요하다 — 무한한 탐험과 함께 점차 greedy로 수렴하는 정책 시퀀스. $\epsilon_t \to 0$인 $\epsilon$-greedy가 이를 만족한다(Singh et al., 2000).

Expected SARSA — Sampling Variance를 제거하면

SARSA의 $a_{t+1}$ 샘플링은 action 선택의 분산을 업데이트에 끌어들인다. Expected SARSA는 이 분산을 제거한다.

$$Q_{t+1}(s, a) = Q_t(s, a) + \alpha\!\left[R + \gamma \sum_{a'} \pi(a' \mid s') Q_t(s', a') - Q_t(s, a)\right]$$

한 번의 샘플 대신 정책의 기댓값을 사용한다. 업데이트 target의 분산이 줄어드는 만큼 학습이 안정된다.

Bias-Variance — MSE를 최소화하는 $n$이란

TD와 MC의 본질적 차이는 estimator의 통계적 성질에 있다.

$$\text{MSE}(\hat{V}) = \underbrace{(\mathbb{E}[\hat{V}] - V^\pi)^2}_{\text{bias}^2} + \underbrace{\text{Var}(\hat{V})}_{\text{variance}}$$

MC는 full return $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$을 사용하므로 불편 추정량이다. 하지만 모든 미래 보상의 분산이 누적된다.

$$\text{Var}(G_t) \approx \frac{\sigma_R^2}{1 - \gamma^2}$$

$\gamma = 0.99$면 이 값은 $\sigma_R^2$의 약 50배다. TD(0)는 $V(s')$의 부정확성에서 $\gamma(\hat{V}(s') - V^\pi(s'))$만큼 편향을 얻는 대신, 분산이 $\sigma_R^2$에 머문다.

n-step return $G_{t:t+n} = \sum_{k=0}^{n-1} \gamma^k R_{t+k} + \gamma^n V(s_{t+n})$은 두 극단 사이의 연속체다. $n=1$이면 TD(0), $n \to \infty$면 MC다. 편향은 $\gamma^n$에 비례해 줄고, 분산은 $n$에 따라 늘어난다. 최적 $n^*$는 환경의 보상 분산, discount factor, 가치 함수의 현재 정확도에 따라 달라진다 — 실무에서는 $n \approx 4 \sim 8$ 또는 TD($\lambda$)로 모든 $n$을 자동 가중한다.

정리

• TD error $\delta_t$는 올바른 $V^\pi$ 하에서 기댓값이 0이다. Bootstrap은 분산을 줄이는 대가로 $V'$ 오차에서 편향을 받는다.
• Tabular TD(0) 수렴의 충분 조건은 Robbins-Monro 학습률 + 모든 상태 무한 방문 + 유계 보상이다.
• SARSA는 on-policy다. 탐험의 위험을 학습에 반영해 안전하지만 보수적이다. GLIE 조건 하에 $Q^*$로 수렴한다.
• Expected SARSA는 action sampling 분산을 제거한다. greedy 극한에서 Q-Learning과 동치다.
• $\text{MSE} = \text{bias}^2 + \text{variance}$. 최적 $n$은 환경에 따라 다르며, TD($\lambda$)는 이 선택을 자동화한다.