[강화학습-6] 시간차 학습 (Temporal-Difference, TD)

6. 시간차 학습 (Temporal-Difference, TD)

“경험은 한 발 먼저, 오류는 한 발 뒤에.”
시간차(TD) 학습은 에피소드가 끝나기를 기다리지 않고, 한 스텝 지연된 오차만으로 가치를 업데이트합니다.
Monte Carlo의 “무편향·고분산”과 DP의 “모델 필요·저분산” 사이에서 균형점을 찾은 방법이라 볼 수 있습니다.

---

6-1. TD(0) 업데이트

상태 가치 버전

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

• $\alpha$ : 학습률 (step-size)
• $R_{t+1} + \gamma V(S_{t+1})$ : 부트스트랩 목표(1-스텝 리턴)
• 대괄호 내부는 TD 오차 $\delta_t$ (예측 – 관측 차이)

요점 : 미래 가치를 현재 추정치로 대체해 편향이 조금 생기지만, 즉시·연속 업데이트가 가능해집니다.

---

6-2. SARSA vs Q-Learning

알고리즘	업데이트 식	성격
SARSA (State–Action–Reward–State–Action)	$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\bigl[R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)\bigr] $$	On-policy 업데이트에 정책이 실제로 고른 $A_{t+1}$ 사용
Q-Learning	$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\bigl[R_{t+1} + \gamma \max_{a}Q(S_{t+1},a) - Q(S_t,A_t)\bigr] $$	Off-policy 목표 정책은 항상 탐욕적 ($\max$) – 학습과 행동이 분리

● On-policy vs Off-policy

• On-policy : 업데이트·행동 ☞ 동일 정책. 안정적이나 탐험이 중요.
• Off-policy : 행동은 행동 정책, 업데이트는 목표 정책. 탐험(behavior)과 학습(target) 분리 → 유연하지만 고variance 문제(Importance Sampling)가 뒤따름.

---

6-3. CartPole 예제 – Q-Learning VS SARSA

CartPole은 연속 상태 4-차원 벡터(위치, 속도, 각도, 각속도)를 출력합니다. 가장 간단한 해결책은 균등 구간 (Discretization) 으로 상태를 작은 그리드로 바꾸는 방식입니다.

"""
pip install gymnasium numpy
"""
import gymnasium as gym
import numpy as np
from collections import defaultdict

ENV_ID     = "CartPole-v1"
N_BINS     = (6, 6, 12, 12)      # 각 상태변수 구간 수
EPISODES   = 20_000
GAMMA      = 0.99
ALPHA      = 0.1
EPS_MIN    = 0.05
EPS_DECAY  = 0.9995
EPSILON    = 1.0                 # 초기 ε
METHOD     = "q_learning"        # 또는 "sarsa"

env   = gym.make(ENV_ID)
n_act = env.action_space.n

# 구간 경계 (관측값 범위 참고)
obs_hi = env.observation_space.high
obs_lo = env.observation_space.low
obs_hi[1]  =  5    ; obs_lo[1]  = -5     # 속도 클리핑
obs_hi[3]  =  5    ; obs_lo[3]  = -5     # 각속도 클리핑
grid       = [np.linspace(lo, hi, n-1) for lo, hi, n in zip(obs_lo, obs_hi, N_BINS)]

def discretize(obs):
    return tuple(int(np.digitize(x, g)) for x, g in zip(obs, grid))

Q = defaultdict(lambda: np.zeros(n_act))

def epsilon_greedy(state, eps):
    if np.random.rand() < eps:
        return env.action_space.sample()
    return np.argmax(Q[state])

for ep in range(EPISODES):
    state, _ = env.reset()
    state = discretize(state)
    action = epsilon_greedy(state, EPSILON)

    done = False
    while not done:
        next_obs, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated
        next_state = discretize(next_obs)

        # --- TD Target ---
        if METHOD == "sarsa":
            next_action = epsilon_greedy(next_state, EPSILON)
            target = reward + GAMMA * Q[next_state][next_action] * (not done)
        else:                              # Q-learning
            target = reward + GAMMA * np.max(Q[next_state]) * (not done)

        # --- TD Update ---
        Q[state][action] += ALPHA * (target - Q[state][action])

        # 다음 스텝
        if METHOD == "sarsa":
            action = next_action
        else:
            action = epsilon_greedy(next_state, EPSILON)

        state = next_state

    # ε 감소
    EPSILON = max(EPS_MIN, EPSILON * EPS_DECAY)

    # 간단한 모니터링
    if (ep+1) % 1000 == 0:
        print(f"Episode {ep+1:5d} | ε = {EPSILON:.3f}")

• 성공 기준 : CartPole-v1 목표는 avg_reward ≥ 475 (500 만점) over 100 episodes.
• 구간 수·학습률·$\epsilon$ 스케줄을 높이면 더 빨리 수렴.
• 더 나은 성능을 원한다면 신경망 근사(DQN)·정책 경사 등으로 확장하세요.

---

6-4. 요약 & 다음 편 예고

• TD(0)는 1-스텝 부트스트랩으로 빠른 온라인 업데이트를 제공한다.
• Q-Learning(Off-policy) ↔ SARSA(On-policy) – 목표/행동 정책 분리 여부가 핵심 차이.
• CartPole 같이 연속 상태 환경은 이산화·타일 코딩·신경망 등의 함수 근사가 필수.

다음 글 : TD(λ)와 N-step 리턴으로 일반화된 Eligibility Trace 개념, 그리고 딥 Q-Network(DQN)·Policy Gradient로 이어지는 딥 강화학습의 서막을 살펴봅니다.

---

참고 자료

• Sutton & Barto, Reinforcement Learning: An Introduction, Ch. 6
• David Silver, RL Course Lecture 5 – TD Learning & Control
• OpenAI (gymnasium) CartPole-v1 환경 소스코드