시간차 학습

Temporal difference learning; 시간차 학습
에피소드가 끝나기를 기다리지 않고, 한 걸음 뒤의 추정값으로 지금의 가치 추정을 고치는 강화 학습 방법

시간차 학습(temporal difference learning, TD 학습)은 강화 학습에서 가치 함수를 배우는 방법으로, 실제로 겪은 보상 하나와 다음 상태에 대한 현재 추정값을 합쳐 지금 상태의 추정값을 고친다. 추정값으로 추정값을 갱신하는 이 방식을 부트스트래핑(bootstrapping)이라 한다. 환경 모델 없이 경험에서 배운다는 점은 몬테카를로 방법과 같고, 다음 상태의 추정값을 쓴다는 점은 동적 계획법과 같다. 서턴과 바토는 TD 학습을 "강화 학습에서 가장 중심적이고 새로운 아이디어"로 꼽는다.^[1]

리처드 서턴이 1988년 논문에서 TD 방법을 정식화했고,^[2] 제럴드 테사우로의 TD-Gammon(1992~1995)이 신경망과 TD(λ)로 백개먼을 학습해 실용성을 보였다. Q-러닝, SARSA, DQN, 액터-크리틱의 크리틱, PPO의 GAE까지 현대 강화 학습 알고리즘 대부분이 TD 오차를 학습 신호로 쓴다.

TD(0): 한 걸음 예측

정책 $π$ 를 따르며 상태 가치 $V (s) \approx v_{π} (s)$ 를 배우는 가장 단순한 TD 방법이다. 전이 $(S_{t}, R_{t + 1}, S_{t + 1})$ 하나를 겪을 때마다 다음처럼 갱신한다.

$V (S_{t}) \leftarrow V (S_{t}) + α [\underset{TD 타깃}{\underset{⏟}{R_{t + 1} + γ V (S_{t + 1})}} - V (S_{t})]$

대괄호 안을 TD 오차라 한다.

$δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})$

몬테카를로 방법은 같은 자리에 실제 이득 $G_{t}$ 를 쓴다. $G_{t} = R_{t + 1} + γ G_{t + 1}$ 에서 아직 모르는 $G_{t + 1}$ 를 현재 추정값 $V (S_{t + 1})$ 로 바꾼 것이 TD 타깃이다. 벨만 기대 방정식의 기댓값을 표본 하나로 근사한 것이라고도 볼 수 있다.

몬테카를로, 동적 계획법과 비교

방법	타깃	모델 필요	부트스트래핑	갱신 시점	편향·분산
동적 계획법	$\sum p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$	필요	함	전체 상태를 한 번에	모델이 정확하면 편향 없음
몬테카를로	$G_{t}$ (실제 이득)	불필요	안 함	에피소드 종료 후	편향 없음, 분산 큼
TD(0)	$R_{t + 1} + γ V (S_{t + 1})$	불필요	함	매 단계	편향 있음(초기 추정값 탓), 분산 작음
n단계 TD	$R_{t + 1} + \dots + γ^{n - 1} R_{t + n} + γ^{n} V (S_{t + n})$	불필요	함	n단계 뒤	n이 클수록 몬테카를로 쪽

TD 방법의 장점은 다음과 같다.

끝나지 않는(연속) 과제나 에피소드가 아주 긴 과제에서도 매 단계 배울 수 있다.
TD 타깃은 보상 하나와 추정값 하나에만 의존하므로, 남은 모든 보상이 쌓이는 몬테카를로 타깃보다 분산이 작다. 실제로 확률적 과제에서 보통 몬테카를로보다 빨리 수렴한다.
표 기반 TD(0)는 학습률 조건을 만족하면 $v_{π}$ 로 수렴한다. 배치(같은 데이터를 반복 학습) 상황에서 TD(0)는 데이터에서 추정한 마르코프 모델의 정확한 가치(확실성 등가 추정)를 찾고, 몬테카를로는 훈련 데이터의 평균 제곱 오차를 최소화한다.^[1]

단점은 부트스트래핑에서 오는 편향이다. 초기 추정값이 틀리면 그 오차가 타깃으로 번진다. 함수 근사, 부트스트래핑, 오프 폴리시 학습이 함께 쓰이면 발산할 수 있다는 "치명적 삼요소"(deadly triad) 문제도 부트스트래핑에서 나온다.^[3]

TD 제어: SARSA와 Q-러닝

행동을 고르려면 상태 가치 대신 행동 가치 $Q (s, a)$ 를 배우고, ε-탐욕처럼 $Q$ 에서 정책을 뽑는다.

알고리즘	갱신 타깃	정책 구분	배우는 가치
SARSA	$R + γ Q (S^{'}, A^{'})$ , $A^{'}$ 는 실제로 고른 다음 행동	온 폴리시	탐험을 포함한 현재 행동 정책의 가치
기대 SARSA	$R + γ \sum_{a} π (a ∣ S^{'}) Q (S^{'}, a)$	온·오프 폴리시 모두 가능	목표 정책의 가치. 다음 행동 표본의 분산이 사라진다.
Q-러닝	$R + γ \max_{a} Q (S^{'}, a)$	오프 폴리시	탐욕 정책의 가치, 곧 $q_{*}$
더블 Q-러닝	한 Q로 행동을 고르고 다른 Q로 평가	오프 폴리시	$q_{*}$ , max에서 오는 과대평가를 줄임

SARSA라는 이름은 갱신에 쓰는 다섯 값 $(S_{t}, A_{t}, R_{t + 1}, S_{t + 1}, A_{t + 1})$ 에서 왔다. 러머리와 니란잔이 1994년 "Modified Connectionist Q-learning"이라는 이름으로 처음 내놓았고, SARSA라는 이름은 서턴이 1996년 붙였다.^[1] Q-러닝은 크리스 왓킨스가 1989년 박사 논문에서 제안했다.^[4]

절벽 걷기 예제

온 폴리시와 오프 폴리시의 차이는 서턴·바토 교과서의 절벽 걷기(cliff walking) 예제에서 잘 드러난다.^[1] 4×12 격자에서 매 걸음 보상은 -1이고, 아래쪽 절벽 칸에 떨어지면 -100을 받고 출발점으로 돌아간다. ε=0.1의 ε-탐욕 정책으로 학습하면 Q-러닝은 절벽 바로 옆 최단 경로의 가치를 배우지만, 탐험 중 가끔 절벽으로 떨어져 학습 중 실제로 받는 이득은 낮다. SARSA는 탐험까지 감안한 가치를 배우므로 절벽에서 한 칸 떨어진 안전한 경로를 택해 학습 중 이득이 더 높다. ε를 0으로 줄여 가면 두 방법 모두 최적 경로로 수렴한다.

Gymnasium(1.x)의 CliffWalking-v1 환경으로 재현하는 코드다. Gymnasium의 step()은 (관측, 보상, terminated, truncated, info)를 돌려주며, 부트스트래핑을 끊을 때는 진짜 종료인 terminated만 써야 한다. 시간 제한으로 잘린 truncated에서는 다음 상태의 가치가 0이 아니다.

import numpy as np
import gymnasium as gym

def eps_greedy(Q, s, eps, rng):
    if rng.random() < eps:
        return int(rng.integers(Q.shape[1]))
    return int(np.argmax(Q[s]))

def run(method, episodes=500, alpha=0.5, gamma=1.0, eps=0.1, seed=0):
    env = gym.make("CliffWalking-v1")
    rng = np.random.default_rng(seed)
    Q = np.zeros((env.observation_space.n, env.action_space.n))
    returns = []
    for ep in range(episodes):
        s, _ = env.reset(seed=seed + ep)
        a = eps_greedy(Q, s, eps, rng)
        G, done = 0.0, False
        while not done:
            s2, r, terminated, truncated, _ = env.step(a)
            done = terminated or truncated
            a2 = eps_greedy(Q, s2, eps, rng)
            if method == "sarsa":        # 실제로 고른 다음 행동의 Q
                target = r + gamma * Q[s2, a2] * (not terminated)
            else:                        # Q-러닝: 다음 상태의 최대 Q
                target = r + gamma * Q[s2].max() * (not terminated)
            Q[s, a] += alpha * (target - Q[s, a])   # TD 오차만큼 이동
            s, a, G = s2, a2, G + r
        returns.append(G)
    return np.mean(returns[-100:])

print("SARSA  최근 100회 평균 이득:", run("sarsa"))   # 약 -25
print("Q-러닝 최근 100회 평균 이득:", run("q"))       # 약 -40

주석의 값은 시드 0으로 한 번 돌린 결과다. 교과서 그림과 같은 경향(학습 중 SARSA의 이득이 더 높음)이 나온다.

n단계 TD와 TD(λ)

TD(0)와 몬테카를로는 "얼마나 멀리 실제 보상을 보고 부트스트래핑할 것인가"라는 축의 양 끝이다. 그 사이를 잇는 방법이 n단계 TD와 TD(λ)다.

n단계 이득은 n개의 실제 보상 뒤에 추정값을 붙인다.

$G_{t : t + n} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} V (S_{t + n})$

λ-이득은 모든 n단계 이득을 $(1 - λ) λ^{n - 1}$ 가중치로 섞은 것이다.

$G_{t}^{λ} = (1 - λ) \sum_{n = 1}^{\infty} λ^{n - 1} G_{t : t + n}$

$λ = 0$ 이면 TD(0), $λ = 1$ 이면 몬테카를로가 된다. λ-이득을 타깃으로 쓰는 것을 전방 관점(forward view)이라 하는데, 미래를 다 봐야 하므로 그대로는 온라인 학습이 안 된다. 서턴의 1988년 논문은 이를 과거 쪽으로 돌린 후방 관점(backward view) TD(λ)를 제시했다. 각 상태(또는 가중치)에 최근에 얼마나 자주 방문했는지를 기록하는 eligibility trace $z_{t}$ 를 두고, 매 단계 TD 오차를 그 흔적에 비례해 과거 상태들에 나눠 준다.

$z_{t} = γ λ z_{t - 1} + \nabla_{w} \hat{v} (S_{t}, w), w \leftarrow w + α δ_{t} z_{t}$

표 기반이면 $\nabla_{w} \hat{v}$ 는 현재 상태 칸만 1인 벡터라, 방문한 상태의 흔적에 1을 더하고 모든 흔적을 매 단계 $γ λ$ 배로 줄이는 것과 같다. 오프라인(에피소드 끝에 몰아서) 갱신이면 후방 관점과 전방 관점의 총 갱신량이 같다. 온라인에서도 둘을 정확히 일치시킨 것이 True Online TD(λ)다.^[5]

λ-이득 아이디어는 딥러닝 시대에도 쓰인다. PPO와 A2C 구현이 쓰는 일반화 어드밴티지 추정(GAE)은 TD 오차를 $(γ λ)^{k}$ 로 할인해 더한 것으로, TD(λ)와 같은 구조다. 자세한 내용은 액터-크리틱 문서 참고.

함수 근사와 TD

상태가 많으면 가치를 신경망 같은 함수 $\hat{v} (s, w)$ 로 근사한다. 이때 TD 갱신은 타깃을 상수로 보고 예측값에 대해서만 미분하는 준경사(semi-gradient) 방법이다.

$w \leftarrow w + α [R + γ \hat{v} (S^{'}, w) - \hat{v} (S, w)] \nabla_{w} \hat{v} (S, w)$

타깃 쪽 $\hat{v} (S^{'}, w)$ 도 $w$ 에 의존하지만 미분하지 않으므로 진짜 경사 하강이 아니다. 선형 함수 근사에서 온 폴리시라면 수렴이 보장되지만, 비선형 근사나 오프 폴리시에서는 발산할 수 있다. DQN은 타깃 계산용 신경망을 따로 두고 천천히 갱신하며, 경험 재생으로 연속 표본 사이의 상관을 끊어 이 문제를 완화했다. 딥러닝 프레임워크에서는 타깃 계산을 torch.no_grad() 안에서 하거나 .detach()해서 준경사를 구현한다.

역사와 신경과학

1959년 아서 새뮤얼의 체커 프로그램이 이후 국면의 평가값으로 현재 국면의 평가를 고치는, TD와 비슷한 아이디어를 썼다.
1983년 바토·서턴·앤더슨이 카트폴 문제를 푼 적응 요소(ASE·ACE)에서 TD 오차로 학습하는 크리틱을 썼다. 이는 액터-크리틱의 원형이다.^[6]
1988년 서턴이 TD(λ)를 정식화했다.^[2]
1989년 왓킨스가 Q-러닝을 제안했다.
1992~1995년 TD-Gammon이 TD(λ)와 자기 대국으로 그랜드마스터급 백개먼 실력에 이르렀다.^[7]
1990년대 후반 원숭이 실험에서 중뇌 도파민 뉴런의 발화가 TD 오차와 비슷한 "보상 예측 오차"를 나타낸다는 연구가 나와, TD 학습은 뇌의 보상 학습 모델로도 연구된다.^[8]

같이 보기

각주

↑ ^1.0 ^1.1 ^1.2 ^1.3 Richard S. Sutton, Andrew G. Barto, 《Reinforcement Learning: An Introduction》 2판, MIT Press, 2018, 6장. 저자 공개본
↑ ^2.0 ^2.1 Richard S. Sutton, 〈Learning to predict by the methods of temporal differences〉, Machine Learning 3, 9~44, 1988. doi:10.1007/BF00115009
↑ Sutton & Barto 2판, 11.3절.
↑ Christopher J. C. H. Watkins, Peter Dayan, 〈Q-learning〉, Machine Learning 8, 279~292, 1992. doi:10.1007/BF00992698
↑ Sutton & Barto 2판, 12장.
↑ Andrew G. Barto, Richard S. Sutton, Charles W. Anderson, 〈Neuronlike adaptive elements that can solve difficult learning control problems〉, IEEE Transactions on Systems, Man, and Cybernetics SMC-13(5), 834~846, 1983. doi:10.1109/TSMC.1983.6313077
↑ Gerald Tesauro, 〈Temporal difference learning and TD-Gammon〉, Communications of the ACM 38(3), 58~68, 1995. doi:10.1145/203330.203343
↑ Sutton & Barto 2판, 15장(신경과학).

참고 문헌

[sb6-1] 1.0 ^1.1 ^1.2 ^1.3 Richard S. Sutton, Andrew G. Barto, 《Reinforcement Learning: An Introduction》 2판, MIT Press, 2018, 6장. 저자 공개본

[sutton88-2] 2.0 ^2.1 Richard S. Sutton, 〈Learning to predict by the methods of temporal differences〉, Machine Learning 3, 9~44, 1988. doi:10.1007/BF00115009

[triad-3] Sutton & Barto 2판, 11.3절.

[watkins-4] Christopher J. C. H. Watkins, Peter Dayan, 〈Q-learning〉, Machine Learning 8, 279~292, 1992. doi:10.1007/BF00992698

[sb12-5] Sutton & Barto 2판, 12장.

[bsa83-6] Andrew G. Barto, Richard S. Sutton, Charles W. Anderson, 〈Neuronlike adaptive elements that can solve difficult learning control problems〉, IEEE Transactions on Systems, Man, and Cybernetics SMC-13(5), 834~846, 1983. doi:10.1109/TSMC.1983.6313077

[tdgammon-7] Gerald Tesauro, 〈Temporal difference learning and TD-Gammon〉, Communications of the ACM 38(3), 58~68, 1995. doi:10.1145/203330.203343

[sb15-8] Sutton & Barto 2판, 15장(신경과학).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]