TD Learning (Temporal Difference Learning)

1. TD Learning이란?

TD Learning(Temporal Difference Learning, 시간차 학습)은 환경의 상태 전이 확률을 모르는 상황에서, 에피소드가 끝날 때까지 기다리지 않고 현재 상태와 다음 상태의 가치 차이를 이용해 상태 가치를 점진적으로 업데이트하는 강화학습 방법입니다.

한 줄로 말하면:

“지금 추정값”과 “바로 다음에 본 정보(보상 + 다음 상태 가치)”의 차이(TD Error)로
현재 상태 가치 V(s)를 조금씩 수정해 나가는 방식

Monte Carlo는 에피소드가 끝난 뒤 전체 Return을 써서 한 번에 업데이트하는 반면, TD Learning은 매 스텝마다 즉시 업데이트할 수 있어서 학습이 빠르고, 긴 에피소드에서도 효율적입니다. Q-learning, SARSA 같은 많은 강화학습 알고리즘의 기반이 되는 방법이라고 보면 됩니다.

---

2. TD Learning이 필요한 이유

강화학습에서는 어떤 상태가 좋은 상태인지 알고 싶어 합니다. 예를 들어 미로에서 “어떤 칸이 출구에 가까운 좋은 칸인지”를 알고 싶은 거죠. 그런데 문제는 미래를 정확히 모른다는 점입니다.

• 지금 이 칸이 좋은 칸인지
• 앞으로 어떻게 흘러갈지
• 결국 성공할지 실패할지

그래서 TD Learning은 이렇게 생각합니다.

“지금은 정답을 모르니까, 일단 다음 상태를 참고해서 현재 상태를 조금 수정하자.”

이게 TD Learning의 핵심입니다.

---

3. TD Learning의 핵심 아이디어

예를 들어 현재 상태가 A, 다음 상태가 B라고 해 보겠습니다.

• 지금까지 상태 A의 가치를 3이라고 생각하고 있었는데
• 실제로 한 번 움직여 보니
  • 보상 r = 1을 받고
  • 다음 상태 B의 가치가 5라면

TD Learning은 이렇게 봅니다.

“아, A는 내가 생각한 것보다 좀 더 좋은 상태였네.
왜냐하면 바로 보상도 받고, 다음 상태도 꽤 좋으니까.”

그래서 A의 가치를 조금 올립니다.
즉, 현재 추정값과 새로 관찰한 정보의 차이를 이용해 수정하는 것이 TD Learning입니다.

---

4. Monte Carlo와 TD Learning의 차이

구분	Monte Carlo	TD Learning
언제 학습?	에피소드가 끝난 후	매 스텝마다
무엇으로 업데이트?	최종 Return(전체 보상 합)	보상 r + γ×다음 상태 가치 (TD target)
특징	최종 결과를 알고 나서 업데이트	끝나기 전에도 계속 업데이트 가능

이 차이 때문에 두 방법의 성격이 완전히 달라집니다. TD는 온라인처럼 매 스텝마다 학습할 수 있어서, 에피소드가 길어도 중간중간 학습이 가능합니다.

---

5. TD 업데이트 식

상태 가치를 업데이트하는 기본 형태는 다음과 같습니다.

V(s) ← V(s) + α × [ r + γ V(s′) − V(s) ]

• α (alpha): 학습률 (얼마나 크게 수정할지)
• r: 현재 스텝에서 받은 보상
• γ (gamma): 할인율
• V(s′): 다음 상태의 (현재 추정) 가치
• r + γ V(s′): TD target (이번에 관찰한 “목표값”)
• r + γ V(s′) − V(s): TD Error (추정이 얼마나 틀렸는지)

즉, TD Error만큼 현재 V(s)를 보정하는 방식입니다.

---

6. 예제 1: 1차원 술취한 사람 문제 (TD로 풀기)

벨만 기대 방정식 글에서 다룬 것처럼, 1차원 술취한 사람 환경을 TD Learning으로 풀어 보겠습니다.

[집] --- A --- B --- C --- [술집]

• Home 도착: +1
• Bar 도착: −1
• 중간 상태 A, B, C에서 매 스텝 50:50으로 왼쪽/오른쪽 한 칸 이동

에피소드를 여러 번 돌리면서, 매 스텝마다 위 TD 식으로 V(s)를 업데이트합니다.
(종료 상태 Home, Bar의 V는 1, −1로 고정해 둡니다.)

코드 요약

V = {"Home": 1.0, "A": 0.0, "B": 0.0, "C": 0.0, "Bar": -1.0}
alpha = 0.1
gamma = 1.0
episodes = 100000

for ep in range(episodes):
    state = random.choice(['A', 'B', 'C'])
    while state not in ['Home', 'Bar']:
        move = random.choice(['left', 'right'])
        # 다음 상태 결정 (A→Home/B, B→A/C, C→B/Bar)
        next_state = ...
        reward = 0  # 중간 이동은 0

        # TD 업데이트: V(s) = V(s) + alpha * (reward + gamma*V(s') - V(s))
        V[state] = V[state] + alpha * (reward + gamma * V[next_state] - V[state])
        state = next_state

충분히 반복하면 V(A) ≈ 0.5, V(B) ≈ 0, V(C) ≈ −0.5 근처로 수렴합니다.
(벨만 기대 방정식으로 구한 이론값과 일치합니다.)

---

7. 예제 2: Grid World (4×4)

4×4 격자에서 에이전트가 상·하·좌·우 중 랜덤으로 움직이고,
매 스텝 보상은 −1, 목표 칸 (3, 3)에 도착하면 에피소드가 끝나는 환경입니다.

• 환경(GridWorld): 좌표 (x, y), 4방향 액션, 보상 −1, (3,3)에서 종료
• 에이전트(Agent): 25% 확률로 각 방향 선택
• TD: 매 스텝 data[x][y] = data[x][y] + alpha * (reward + gamma * data[x'][y'] - data[x][y]) 로 각 칸의 가치를 업데이트

여기서는 목표 칸에 가까울수록 (음수라도) 절댓값이 작아지고, 멀수록 더 큰 음수로 수렴하는 형태가 나옵니다.
(예: 출력에서 (3,3) 근처가 0에 가깝고, (0,0) 쪽이 −59 정도로 큰 음수.)

---

8. 예제 3: 5×5 술취한 사람 (Grid)

2차원으로 확장한 5×5 격자입니다.

+-----+-----+-----+-----+-----+
| H   |     |     |     | BAR |
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
|     |     | *   |     |     |   * 시작 (2,2)
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
+-----+-----+-----+-----+-----+

• H (0,0): Home → 보상 +1, 종료
• BAR (4,4): Bar → 보상 −1, 종료
• 시작: (2, 2)
• 매 스텝 상·하·좌·우 25% 랜덤 이동, 격자 밖이면 제자리
• TD 업데이트: 종료 상태가 아니면 td_target = reward + gamma * data[x'][y'], 종료면 td_target = reward
  → data[x][y] = data[x][y] + alpha * (td_target - data[x][y])

Home(0,0)과 Bar(4,4)의 가치는 매 에피소드마다 1.0, −1.0으로 고정해 두고, 나머지 칸만 학습합니다.

실행 결과 예시

반복 후 각 칸의 가치는 대략 다음과 같이 수렴합니다.

• (0,0) = 1.0, (4,4) = −1.0 (고정)
• Home 쪽(왼쪽 위)일수록 양수에 가깝고
• Bar 쪽(오른쪽 아래)일수록 음수에 가깝게
• 가운데 (2,2) 근처는 0에 가까운 값

즉, “집에 가까운 칸일수록 좋은 상태”, “술집에 가까운 칸일수록 나쁜 상태”가 수치로 드러납니다.

[ 오늘의 정리 ]

• TD Learning은 에피소드 종료를 기다리지 않고,
  매 스텝 “보상 + 할인된 다음 상태 가치”와 현재 추정값의 차이(TD Error)로
  상태 가치 V(s)를 점진적으로 업데이트하는 방법입니다.
• Monte Carlo는 “에피소드 끝 → Return 계산 → 한 번에 업데이트”이고,
  TD는 “한 스텝 진행 → TD target으로 바로 업데이트”라서
  학습 속도와 온라인 활용 측면에서 유리합니다.
• 1차원 술취한 사람, 4×4 Grid World, 5×5 술취한 사람 Grid처럼
  환경만 정의해 주면, 같은 TD 식으로 상태 가치를 학습할 수 있고,
  Q-learning·SARSA 같은 행동 가치 기반 알고리즘의 토대가 됩니다.