[강화학습] TD Learning (시간차 학습) 개념, 랜덤 벽 GridWorld 실습

강화학습을 공부하다 보면 반드시 마주치는 중요한 개념이 있습니다. 바로 TD Learning(Temporal Difference Learning, 시간차 학습)입니다. Q-learning이나 SARSA 같은 유명한 알고리즘들이 모두 이 TD Learning을 뿌리로 두고 있죠.

오늘은 TD Learning이 대체 무엇인지, 왜 필요한지, 그리고 파이썬 코드로 어떻게 구현하는지 알아보겠습니다.

---

1. TD Learning 이란?

TD Learning(시간차 학습)은 환경의 상태 전이 확률을 완벽히 알지 못하는 상황에서 사용하는 가치 평가 방법입니다.

가장 큰 특징은 에피소드가 끝날 때까지 기다리지 않는다는 것입니다. 현재 상태에서 한 스텝 나아간 뒤, 바로 다음 상태의 가치와 얻은 보상을 이용해 현재 상태의 가치를 '점진적으로' 업데이트합니다.

수식으로 표현하면 다음과 같습니다.

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

• $V(S_{t})$: 현재 상태의 가치
• $\alpha$: 학습률 (Learning Rate)
• $R_{t+1}$: 행동 후 받은 즉각적인 보상
• $\gamma$: 할인율 (Discount Factor)
• $V(S_{t+1})$: 다음 상태의 예상 가치
• $[R_{t+1} + \gamma V(S_{t+1}) - V(S_{t})]$: 이 부분을 TD Error(시간차 오차)라고 부릅니다.

---

2. TD Learning이 필요한 이유와 핵심 아이디어

강화학습의 목표는 "어떤 상태(State)가 좋은 상태인지" 정확히 파악하는 것입니다. 미로 찾기를 예로 들면, 어떤 칸이 출구에 더 가까운 명당인지 알아내야 하죠.

하지만 우리는 미래를 정확히 모릅니다. 지금 밟은 이 칸이 정말 좋은 칸인지, 앞으로 상황이 어떻게 흘러갈지, 결국 목적지에 도착해 성공할지 실패할지 당장 알 길이 없습니다.

그래서 TD Learning은 이렇게 접근합니다.

"지금 당장 최종 정답(Return)은 모르니까, 일단 한 발짝 움직여보고 '다음 상태'를 참고해서 '현재 상태'의 가치를 조금씩 수정하자!"

핵심 아이디어 예시

현재 상태를 A, 한 번 움직여서 도달한 다음 상태를 B라고 해봅시다.

1. 나는 현재 상태 A의 가치를 3이라고 예측하고 있었습니다.
2. 실제로 한 번 움직여보니, 즉각적인 보상 $R = 1$을 받았고 다음 상태 B에 도착했습니다.
3. 상태 B의 가치는 5로 평가되고 있습니다.

이때 TD Learning의 사고방식은 이렇습니다.

"아, A는 내가 생각했던 것(3)보다 훨씬 좋은 상태였네! 움직이자마자 보상(1)도 받고, 도착한 다음 상태도 꽤 좋으니까(5)." 결과적으로 TD Error를 계산하여 A의 가치를 상향 조정하게 됩니다.

---

3. Monte Carlo vs TD Learning

에피소드 기반 학습의 양대 산맥인 Monte Carlo(MC)와 비교하면 TD Learning의 장점이 더욱 명확해집니다.

특징	Monte Carlo (MC)	TD Learning (TD)
업데이트 시점	에피소드가 끝난 후 최종 결과를 보고 학습	매 스텝마다 한 발짝 움직이고 즉시 학습
필요 조건	반드시 끝(Terminal state)이 있는 에피소드여야 함	끝나지 않는 연속적인(Continuous) 환경도 가능
분산(Variance)	최종 결과를 사용하므로 분산이 높음 (결과가 매번 다를 수 있음)	1스텝만 보므로 분산이 낮음
편향(Bias)	실제 얻은 Return을 쓰므로 편향이 없음 (Unbiased)	예측값으로 예측값을 업데이트(Bootstrapping)하므로 편향이 있음
학습 속도	에피소드가 길면 학습이 매우 느림	스텝 단위로 학습하므로 속도가 빠르고 효율적

 

요약: MC는 "끝까지 가보고 나서 한 번에 평가하자"는 주의고, TD는 "가면서 틈틈이 평가를 수정하자"는 주의입니다.

---

4. 파이썬 코드로 보는 TD Learning 구현

앞서 설명한 개념을 3가지 환경에서 코드로 확인해 보겠습니다.

4-1 기본 상태 전이 예제 (상태 A, B, C)

에이전트가 랜덤하게 왼쪽/오른쪽으로 이동하며 Home이나 Bar에 도착하면 끝나는 간단한 환경입니다.

import random

# 상태 가치 초기화
V = {"Home": 1.0, "A": 0.0, "B": 0.0, "C": 0.0, "Bar": -1.0}
alpha = 0.1
gamma = 1.0
episodes = 500000
states = ['A', 'B', 'C']

for ep in range(episodes):
    state = random.choice(states)
    while state not in ['Home', 'Bar']:
        move = random.choice(['left', 'right'])
        
        # 상태 전이 로직
        if state == 'A': next_state = 'Home' if move == 'left' else 'B'
        elif state == 'B': next_state = 'A' if move == 'left' else 'C'
        elif state == 'C': next_state = 'B' if move == 'left' else 'Bar'
        
        reward = 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

for state, value in V.items():
    print(f'{state}: {value:.4f}')

4-2 술 취한 사람 문제 (Drunkard's Walk)

5x5 그리드의 정중앙(2,2)에서 시작하여, 안전한 집(0,0)에 가면 보상 +1, 위험한 곳(0,4)에 가면 보상 -1을 받는 환경입니다.

import random

class DrunkardGridWorld():
    # 환경 설정 (생략: 위에서 제공해주신 GridWorld 클래스 구조와 동일)
    # ... (x=2, y=2 시작, 0,0 도달시 +1, 0,4 도달시 -1, 스텝 보상 0) ...
    pass 

# TD Learning 진행부
def main():
    env = DrunkardGridWorld()
    # 5x5 상태가치 테이블 0으로 초기화
    data = [[0]*5 for _ in range(5)]
    gamma = 1.0
    alpha = 0.01
    # 목표 지점 가치 고정
    data[0][0] = 1.0
    data[0][4] = -1.0

    for k in range(50000):
        env.reset() # (2,2)로 리셋
        done = False
        while not done:
            x, y = env.get_state()
            action = random.randint(0, 3) # 랜덤 정책
            (x_prime, y_prime), reward, done = env.step(action)
            
            # 다음 상태가 도착 지점인지 아닌지에 따라 타겟 계산
            if done:
                td_target = reward
            else:
                td_target = reward + gamma * data[x_prime][y_prime]
                
            # TD 업데이트
            data[x][y] = data[x][y] + alpha * (td_target - data[x][y])
            
        # 목표 지점 가치 유지 보정
        data[0][0] = 1.0
        data[0][4] = -1.0

    for row in data:
        print([round(v, 4) for v in row])

 

결과를 보면 (0,0)에 가까운 상태일수록 가치가 1에 가깝고, (0,4)에 가까울수록 -1에 가까워지는 그라데이션을 확인할 수 있습니다.

---

5. [실습] 랜덤 벽(Random Wall) GridWorld 환경 구현

이번에는 난이도를 높여, 매 에피소드마다 벽의 위치가 무작위로 변하는 4x4 GridWorld를 만들고 TD Learning으로 상태 가치를 평가해 보겠습니다.

환경 조건

• 크기: 4x4, 시작(0,0), 목표(3,3)
• 행동: 상, 하, 좌, 우 (랜덤 정책)
• 랜덤 벽: 매 에피소드 시작 시 무작위 위치에 2~3개의 벽 생성.
  • 단, 시작(0,0), 목표(3,3)에는 생성 불가. 중복 생성 불가.
• 이동 규칙: 빈 칸 이동 가능. 격자를 벗어나거나 벽으로 이동 시도 시 '제자리 유지'.
• 보상: 모든 이동 시도에 대해 -1. 목표 도달 시 에피소드 종료.

import random

class RandomWallGridWorld():
    def __init__(self):
        self.x = 0
        self.y = 0
        self.walls = []

    def reset(self):
        self.x = 0
        self.y = 0
        self.walls = []
        
        # 벽을 생성할 수 있는 후보 좌표들 (시작과 끝 제외)
        possible_walls = [(i, j) for i in range(4) for j in range(4) 
                          if (i, j) not in [(0, 0), (3, 3)]]
        
        # 벽 개수를 2개 또는 3개로 무작위 선택 후 좌표 샘플링
        num_walls = random.choice([2, 3])
        self.walls = random.sample(possible_walls, num_walls)
        
        return (self.x, self.y)

    def step(self, action):
        # 0:왼쪽, 1:위쪽, 2:오른쪽, 3:아래쪽
        next_x, next_y = self.x, self.y
        
        if action == 0:   next_y -= 1
        elif action == 1: next_x -= 1
        elif action == 2: next_y += 1
        elif action == 3: next_x += 1

        # 격자를 벗어나거나, 이동하려는 곳이 벽(walls)인 경우 제자리 유지
        if next_x < 0 or next_x > 3 or next_y < 0 or next_y > 3 or (next_x, next_y) in self.walls:
            pass # 위치 업데이트 하지 않음 (제자리)
        else:
            self.x, self.y = next_x, next_y

        reward = -1 # 모든 스텝에 대해 보상은 -1
        done = self.is_done()
        return (self.x, self.y), reward, done

    def is_done(self):
        return self.x == 3 and self.y == 3

    def get_state(self):
        return (self.x, self.y)

def main():
    env = RandomWallGridWorld()
    data = [[0.0]*4 for _ in range(4)]
    gamma = 1.0
    alpha = 0.01

    for k in range(50000):
        env.reset()
        done = False
        while not done:
            x, y = env.get_state()
            action = random.randint(0, 3) # 완전 랜덤 정책
            
            (x_prime, y_prime), reward, done = env.step(action)
            
            # TD Learning 가치 업데이트
            if done:
                data[x][y] = data[x][y] + alpha * (reward - data[x][y])
            else:
                data[x][y] = data[x][y] + alpha * (reward + gamma * data[x_prime][y_prime] - data[x][y])

    print("=== 랜덤 벽 GridWorld 상태 가치 (V(s)) ===")
    for row in data:
        print([round(v, 2) for v in row])

if __name__ == '__main__':
    main()

---

6. 결과 분석: 일반 그리드 vs 랜덤 벽 그리드의 상태 가치 차이

TD Learning을 통해 도출된 data(상태 가치 $V(s)$)를 비교해보면, 일반 환경과 랜덤 벽 환경 사이에 뚜렷한 차이가 나타납니다.

우선 현재 에이전트는 아무런 지능 없이 네 방향으로 무작위로 움직이는 랜덤 정책을 따르고 있다는 점을 기억해야 합니다. 여기서 상태 가치란 "이 칸에서 시작해서 목적지까지 갈 때 평균적으로 얼마나 많은 -1 보상을 받을 것인가(몇 걸음이나 걸릴 것인가)"를 의미합니다.

 

1. 전체적인 가치 하락 (더 큰 음수값)

• 일반 그리드: 방해물이 없으므로 랜덤하게 움직여도 비교적 수월하게 목적지(3,3)로 흘러갑니다.
• 랜덤 벽 그리드: 매번 위치가 바뀌는 2~3개의 벽 때문에 길이 막힙니다. 벽을 향해 걷다가 제자리에 멈춰 서서 쓸데없이 턴을 낭비(보상 -1 누적)하는 경우가 빈번하게 발생합니다. 목적지에 도달하기까지의 평균 스텝 수가 훨씬 길어지므로, 모든 상태의 가치 $V(s)$가 일반 그리드에 비해 훨씬 낮게(절대값이 큰 음수로) 수렴하게 됩니다.

2. 목표점(3,3) 주변 가치의 불확실성 증가

• 일반 그리드: (2,3)이나 (3,2) 같은 목표 바로 옆 칸은 항상 가치가 가장 높습니다(가장 덜 마이너스입니다).
• 랜덤 벽 그리드: 랜덤 벽이 하필 목표점 주변을 둘러싸는 형태로 맵이 생성되는 에피소드가 존재합니다. 이 경우 목표점 바로 옆 칸이라도 갇혀서 빠져나가지 못하고 헤맬 수 있습니다. 따라서 상태 가치는 이러한 '막막한 맵'에서 깎인 점수까지 평균내어 반영하므로, 일반 환경보다 목표점 주변과 시작점 간의 가치 격차(Gradient)가 상대적으로 완만해지거나 찌그러지는 양상을 보입니다.

결론적으로 랜덤 벽 환경에서의 TD Learning은, "어느 경로든 벽이 생길 수 있는 리스크(불확실성)"까지 모두 고려된 평균적인 상태 가치를 훌륭하게 찾아낸다고 볼 수 있습니다.