시간차 학습(Temporal Difference; TD) — Q-Learning & SARSA

몬테카를로(Monte Carlo)는 에피소드(episode)가 끝날 때까지 기다립니다. 시간차 학습(Temporal Difference; TD)은 다음 가치 추정값을 부트스트래핑(bootstrapping)해 매 스텝마다 갱신합니다. Q-learning은 오프 정책(off-policy)이고 낙관적(optimistic)입니다. SARSA는 온 정책(on-policy)이고 조심스럽습니다. 두 방법의 차이는 코드 한 줄에 불과하지만, 둘 다 이 phase에 등장하는 모든 심층 강화학습(deep RL) 방법의 기반이 됩니다.

유형: Build 언어: Python 선수 지식: Phase 9 · 01 (MDP), Phase 9 · 02 (동적 계획법), Phase 9 · 03 (몬테카를로) 예상 시간: 약 75분

문제

몬테카를로는 동작하기는 하지만 비용이 큰 두 가지 요구 조건이 있습니다. 에피소드가 반드시 종료되어야 하고, 최종 리턴(final return)이 들어와야만 비로소 갱신을 수행합니다. 한 에피소드가 1,000 스텝이라면 몬테카를로(MC)는 아무것도 갱신하지 않고 1,000 스텝 동안 기다리게 됩니다. 결과적으로 분산은 높고(high-variance) 편향은 낮으며(low-bias), 실제 학습은 느리게 진행됩니다.

동적 계획법(Dynamic Programming; DP)은 정반대 특성을 가집니다. 분산이 0인 부트스트랩 백업(bootstrapped backup)을 사용하지만, 알려진 모델(known model)이 반드시 필요하다는 단점이 있습니다.

시간차 학습은 이 둘의 중간 지점을 택합니다. 단일 전이(single transition) (s, a, r, s') 하나로부터 한 스텝짜리 타깃(one-step target) r + γ V(s')을 만들고, V(s)를 이 타깃 쪽으로 조금씩 이동시킵니다. 모델이 필요 없고, 완전한 에피소드도 필요 없습니다. 우변(right-hand side; RHS)에 근사값인 V를 사용하므로 편향은 생기지만, 몬테카를로보다 분산이 극적으로 낮고 첫 스텝부터 온라인 갱신(online update)이 가능합니다.

이것이 바로 DQN, A2C, PPO, SAC를 포함한 현대 강화학습 전체가 회전하는 축(pivot)입니다. Phase 9의 나머지 강의는 이번 강의에서 작성할 한 스텝짜리 TD 갱신 위에 함수 근사(function approximation)와 여러 기법(trick)을 쌓아 올린 것들입니다.

개념

가치 함수 V에 대한 TD(0) 갱신은 다음과 같습니다.

V(s) ← V(s) + α [r + γ V(s') - V(s)]

대괄호 안의 값을 TD 오차(TD error) δ = r + γ V(s') - V(s)라고 부릅니다. 몬테카를로의 G_t - V(s_t)에 대응하는 온라인 버전입니다. 수렴을 보장하려면 α가 로빈스-먼로(Robbins-Monro) 조건(Σ α = ∞, Σ α² < ∞)을 만족해야 하고, 모든 상태가 무한히 자주 방문되어야 합니다.

Q-learning. 제어(control) 문제를 위한 오프 정책 TD 방법입니다.

Q(s, a) ← Q(s, a) + α [r + γ max_{a'} Q(s', a') - Q(s, a)]

max는 에이전트가 실제로 어떤 행동을 취했는지와 무관하게 s' 이후에는 탐욕(greedy) 정책을 따른다고 가정합니다. 이러한 분리(decoupling) 덕분에 에이전트가 ε-탐욕(ε-greedy)으로 탐험(exploration)하는 동안에도 Q-learning은 Q*를 학습할 수 있습니다. Mnih 외(2015)는 이 아이디어를 아타리(Atari)에서의 심층 Q-learning(deep Q-learning)으로 확장했습니다(Lesson 05).

SARSA. 온 정책 TD 방법입니다.

Q(s, a) ← Q(s, a) + α [r + γ Q(s', a') - Q(s, a)]

이름은 튜플 (s, a, r, s', a')의 머리글자에서 왔습니다. SARSA는 탐욕 argmax가 아니라 에이전트가 다음에 실제로 선택한 행동 a'를 사용합니다. 현재 실행 중인 ε-탐욕 정책 π에 대한 Q^π로 수렴하며, ε → 0 극한에서는 Q*가 됩니다.

절벽 걷기(cliff-walking)에서 드러나는 차이. 고전적인 절벽 걷기 과제(보상 -100을 받으며 절벽으로 떨어짐)에서 Q-learning은 절벽 가장자리를 따라가는 최적 경로를 학습하지만, 탐험 중에는 가끔 페널티를 받습니다. SARSA는 탐험 잡음(exploration noise)을 Q 값에 함께 반영하기 때문에 절벽에서 한 칸 떨어진 더 안전한 경로를 학습합니다. 학습이 충분히 진행되어 ε → 0이 되면 두 방법 모두 최적에 도달합니다. 그러나 실전에서 이 차이는 중요합니다. 배포(deployment) 시점에도 실제로 탐험이 일어난다면 SARSA의 동작이 더 보수적입니다.

기대 SARSA(Expected SARSA). Q(s', a')를 정책 π 아래에서의 기대값으로 바꿉니다.

Q(s, a) ← Q(s, a) + α [r + γ Σ_{a'} π(a'|s') Q(s', a') - Q(s, a)]

a'를 표본 추출(sampling)하지 않으므로 SARSA보다 분산이 낮고, 타깃은 동일한 온 정책 타깃입니다. 현대 교재에서는 보통 기본 선택지로 다룹니다.

n-스텝 TD와 TD(λ). TD(0)와 몬테카를로 사이를 보간(interpolation)합니다. 부트스트래핑하기 전에 n 스텝을 기다리는데, n=1이면 TD, n=∞이면 몬테카를로가 됩니다. TD(λ)는 모든 n에 대해 기하 가중치 (1-λ)λ^{n-1}로 평균을 취합니다. 대부분의 심층 강화학습은 n을 3에서 20 사이로 사용합니다.

직접 만들기

Step 1: ε-탐욕 정책으로 SARSA 구현하기

def sarsa(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})

    def choose(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)

    for _ in range(episodes):
        s = env.reset()
        a = choose(s)
        while True:
            s_next, r, done = env.step(s, a)
            a_next = choose(s_next) if not done else None
            target = r + (gamma * Q[s_next][a_next] if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s, a = s_next, a_next
    return Q

여덟 줄이면 충분합니다. Q-learning과의 유일한 차이는 target 줄 한 곳뿐입니다.

Step 2: Q-learning 구현하기

def q_learning(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    for _ in range(episodes):
        s = env.reset()
        while True:
            a = choose(s, Q, epsilon)
            s_next, r, done = env.step(s, a)
            target = r + (gamma * max(Q[s_next].values()) if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s = s_next
    return Q

max 연산자가 타깃을 행동 정책(behavior policy)으로부터 분리해 줍니다. 이 기호 하나가 온 정책과 오프 정책을 가르는 본질적 차이입니다.

Step 3: 학습 곡선(learning curve) 그리기

에피소드 100개당 평균 리턴(mean return)을 추적합니다. 단순한 결정론적(deterministic) GridWorld에서는 Q-learning이 더 빨리 수렴하고, 절벽 걷기에서는 SARSA가 더 보수적으로 행동합니다. code/main.py의 4×4 GridWorld에서는 α=0.1, ε=0.1로 설정했을 때 두 방법 모두 약 2,000 에피소드 이후 거의 최적(near-optimal)에 가까워집니다.

Step 4: 동적 계획법의 정답과 비교하기

가치 반복(value iteration, Lesson 02)을 실행해 Q*를 얻은 뒤, max_{s,a} |Q_learned(s,a) - Q*(s,a)|를 확인합니다. 건강하게 학습한 표(tabular) 기반 TD 에이전트는 4×4 GridWorld에서 10,000 에피소드를 학습한 뒤 대략 ~0.5 이내에 들어옵니다.

주의할 점

• 초기 Q 값(Initial Q values)이 중요합니다. 낙관적 초기화(optimistic init), 예를 들어 음의 보상(negative-reward) 과제에서 Q = 0으로 두는 것은 탐험을 장려합니다. 반대로 비관적 초기화(pessimistic init)는 탐욕 정책을 영원히 한 곳에 가둘 수 있습니다.
• α 스케줄(schedule). 비정상(non-stationary) 문제에서는 상수 α로도 충분합니다. 감소하는 α_n = 1/n은 이론적으로 수렴을 보장하지만 실전에서는 너무 느립니다. α를 [0.05, 0.3] 범위에 고정하고 학습 곡선을 관찰하는 것이 일반적입니다.
• ε 스케줄. 높은 값(ε=1.0)에서 시작해 ε=0.05까지 감소시킵니다. "GLIE"(greedy in the limit with infinite exploration; 무한 탐험 하에서 극한에서 탐욕적)가 수렴 조건입니다.
• Q-learning의 최대화 편향(max bias). Q가 잡음을 포함할 때 max 연산자는 위쪽으로 편향(upward-biased)됩니다. 이는 과대추정(overestimation)으로 이어지며, Hasselt의 이중 Q-learning(Double Q-learning)이 두 개의 Q 표(table)를 사용해 이 문제를 해결합니다(Lesson 05의 DDQN도 같은 아이디어를 사용합니다).
• 종료되지 않는 에피소드(non-terminating episodes). TD는 종단(terminal) 상태가 없어도 학습할 수 있지만, 스텝 상한(step cap)을 두거나 상한 지점에서 부트스트랩을 올바르게 처리해야 합니다. 표준 방법은 상한 지점을 비종단(non-terminal)으로 취급하고 부트스트래핑을 계속하는 것입니다.
• 상태 해싱(state hashing). 상태가 튜플(tuple)이나 텐서(tensor) 형태라면 해시 가능한(hashable) 키를 사용해야 합니다. 리스트가 아니라 튜플을 사용하고, 원시 부동소수점(raw float) 튜플이 아니라 반올림한 부동소수점 튜플을 사용하는 식입니다.

사용해보기

2026년 기준의 TD 지형은 다음과 같습니다.

2026년 논문에서 읽게 되는 "강화학습"의 90%는 Q-learning이나 SARSA의 어떤 변형입니다. 더 깊은 내용을 읽기 전에 표 기반 갱신을 손에 익혀 두는 것이 좋습니다.

산출물 만들기

outputs/skill-td-agent.md로 저장합니다.

---
name: td-agent
description: Pick between Q-learning, SARSA, Expected SARSA for a tabular or small-feature RL task.
version: 1.0.0
phase: 9
lesson: 4
tags: [rl, td-learning, q-learning, sarsa]
---

Given a tabular or small-feature environment, output:

1. Algorithm. Q-learning / SARSA / Expected SARSA / n-step variant. One-sentence reason tied to on-policy vs off-policy and variance.
2. Hyperparameters. α, γ, ε, decay schedule.
3. Initialization. Q_0 value (optimistic vs zero) and justification.
4. Convergence diagnostic. Target learning curve, `|Q - Q*|` check if DP is possible.
5. Deployment caveat. How will exploration behave at inference? Is SARSA's conservatism needed?

Refuse to apply tabular TD to state spaces > 10⁶. Refuse to ship a Q-learning agent without a max-bias caveat. Flag any agent trained with ε held at 1.0 throughout (no exploitation phase).

연습문제

1. 쉬움. 4×4 GridWorld에서 Q-learning과 SARSA를 구현합니다. 2,000 에피소드 동안 학습 곡선(에피소드 100개당 평균 리턴)을 그려 봅니다. 어느 쪽이 더 빨리 수렴하나요?
2. 중간. 절벽 걷기 환경을 만들어 봅니다. 4×12 격자이고, 마지막 행(row)이 절벽이며 보상 -100을 받고 시작 지점으로 재설정(reset)됩니다. Q-learning과 SARSA의 최종 정책을 비교하고 각각의 경로를 화면으로 캡처(screenshot)합니다. 어느 쪽이 절벽에 더 가까운가요?
3. 어려움. 이중 Q-learning(Double Q-learning)을 구현합니다. 스텝마다 받는 보상에 가우시안 잡음(Gaussian noise) σ=5를 더한 잡음이 있는 GridWorld에서, Q-learning이 V*(0,0)을 의미 있는 수준으로 과대추정하는 반면 이중 Q-learning은 그렇지 않다는 점을 보입니다.

핵심 용어

더 읽을거리

• Watkins & Dayan (1992). Q-learning — 원 논문과 수렴 증명을 담고 있습니다.
• Sutton & Barto (2018). Ch. 6 — Temporal-Difference Learning — TD(0), SARSA, Q-learning, 기대 SARSA를 다룹니다.
• Hasselt (2010). Double Q-learning — 최대화 편향(maximization bias)을 보정하는 방법을 제시합니다.
• Seijen, Hasselt, Whiteson, Wiering (2009). A Theoretical and Empirical Analysis of Expected SARSA — 기대 SARSA의 동기와 분석을 다룹니다.
• Rummery & Niranjan (1994). On-line Q-learning using connectionist systems — SARSA라는 이름의 기원이 된 논문으로, 당시에는 "modified connectionist Q-learning"이라고 불렸습니다.
• Sutton & Barto (2018). Ch. 7 — n-step Bootstrapping — TD(0)를 TD(n)으로 일반화하며, Q-learning에서 자격 흔적(eligibility traces)을 거쳐 이후 PPO의 GAE로 이어지는 경로를 다룹니다.