§ 1TD 예측 — 한 걸음만 기다린다
시간차(Temporal-Difference, TD) 학습은 몬테카를로(MC) 아이디어와 동적 프로그래밍(DP) 아이디어의 결합이다. MC처럼 환경의 모델 없이 원시 경험에서 직접 배운다. DP처럼 최종 결과를 기다리지 않고, 다른 학습된 추정에 부분적으로 기대어 추정을 갱신한다 — 부트스트랩(bootstrap)한다.
예측 문제 — 주어진 정책 π의 가치 함수 vπ를 추정하는 문제 — 부터 시작하자. MC와 TD 모두 정책 π를 따르는 경험을 쓰며, 그 경험에 등장하는 비종료 상태 St의 추정 V를 갱신한다. 차이는 언제 무엇을 목표로 삼는가에 있다.
몬테카를로 방법은 방문 이후의 반환값 Gt가 알려질 때까지 — 즉 에피소드 끝까지 — 기다린 다음, 그 반환값을 V(St)의 목표로 쓴다. 반면 TD 방법은 다음 시간 단계까지만 기다린다. 시간 t+1에 관찰한 보상 Rt+1과 추정 V(St+1)로 곧바로 목표를 만들어 유용한 갱신을 한다.
이 가장 단순한 TD 방법을 TD(0) 또는 원-스텝 TD라 부른다. 7장의 n단계 TD와 12장의 TD(λ)의 특수 경우이기 때문이다. TD(0)가 기존 추정 V(St+1)에 부분적으로 기대어 갱신하므로, 우리는 그것이 DP처럼 부트스트래핑 방법이라 말한다.
왜 이 목표가 타당한가? 3장에서 가치 함수가 다음 세 가지로 쓰임을 안다 — vπ(s)=Eπ[Gt|St=s], 그리고 이를 한 단계 펼친 Eπ[Rt+1+γGt+1], 다시 가치로 접은 Eπ[Rt+1+γvπ(St+1)]. 몬테카를로는 첫 번째 식의 추정을 목표로 삼고, DP는 마지막 식을 목표로 삼는다. TD는 마지막 식의 추정을 — 그러나 기대값이 아닌 샘플로 — 목표로 삼는다. TD는 샘플링하면서 동시에 부트스트랩한다.
# 입력: 평가할 정책 π · 매개변수: 스텝 크기 α ∈ (0,1] 모든 s ∈ S+ 에 대해 V(s) 임의 초기화, 단 V(terminal) = 0 각 에피소드에 대해 반복: S 초기화 에피소드의 각 단계에 대해 반복: A ← π 가 S에서 주는 행동 행동 A 수행, 보상 R과 다음 상태 S′ 관찰 V(S) ← V(S) + α[ R + γV(S′) − V(S) ] S ← S′ until S 가 종료 상태
§ 2TD 오차 δ와 세 방법의 비교
TD(0) 갱신의 대괄호 안 양은 일종의 오차다 — St의 추정 가치와, 더 나은 추정 Rt+1+γV(St+1) 사이의 차이를 잰다. 이 양을 TD 오차(TD error) δ라 부르며, 강화학습 전반에 걸쳐 다양한 형태로 거듭 나타난다.
흥미로운 항등식이 하나 있다. 배열 V가 에피소드 동안 변하지 않으면, 몬테카를로 오차는 TD 오차들의 합으로 쓸 수 있다: Gt−V(St) = δt + γδt+1 + γ²δt+2 + ⋯. 이 항등식이, TD 학습이 끝을 기다리는 MC의 한 단위 — 단 한 시간 단계의 경험 — 만 처리하고도 유용한 일을 할 수 있는 까닭을 설명한다. (TD(0)처럼 V가 에피소드 중에 갱신되면 항등식은 근사적으로만 성립하지만, 스텝 크기가 작으면 여전히 거의 맞다.)
아래 모션은 이 차이의 본질을 보여준다 — TD 오차 δ가 단 하나의 전이에서 계산되어 즉시 가치를 갱신하는 모습. 몬테카를로와 달리 에피소드의 끝을 기다리지 않는다.
| 구분 | 동적 프로그래밍 | 몬테카를로 | 시간차(TD) |
|---|---|---|---|
| 환경 모델 | 필요 — 완전한 분포 | 불필요 | 불필요 |
| 부트스트래핑 | 한다 (추정 위에 추정) | 안 한다 (실제 반환값) | 한다 |
| 샘플링 | 안 한다 (기대값) | 한다 | 한다 |
| 갱신 시점 | 스윕 | 에피소드 끝 | 매 시간 단계 |
| 온라인 구현 | — | 불가 (끝을 기다림) | 완전 점진적·온라인 |
다섯 상태 A–B–C–D–E의 마르코프 보상 과정. 모든 에피소드는 중앙 C에서 시작해 매 단계 좌우로 동일 확률 이동, 양 끝에서 종료한다. 오른쪽 끝에서만 보상 +1, 나머지는 0. 할인이 없으니 각 상태의 진짜 가치는 그곳에서 출발해 오른쪽에서 끝날 확률이다 — A부터 1/6, 2/6, 3/6, 4/6, 5/6.
모든 가치를 0.5로 초기화하고 TD(0)와 상수-α MC를 비교하면, 다양한 α에 걸쳐 TD가 일관되게 MC보다 빨리, 더 낮은 RMS 오차로 수렴한다. TD가 왜 더 효율적인가 — 그 답이 다음 절에 있다.
§ 3TD(0)의 최적성 — 배치 갱신이 드러내는 것
유한한 경험만 — 가령 10개의 에피소드만 — 가졌다고 하자. 점진적 학습에서 흔한 접근은 배치 갱신(batch updating)이다: 같은 경험을 수렴할 때까지 반복 제시한다. 각 비종료 상태 방문마다 증분을 계산하되 가치 함수는 모든 증분의 합만큼 한 번만 바꾸고, 그 새 가치로 전체 경험을 다시 처리하는 일을 반복한다.
배치 갱신 하에서 TD(0)는 단일 답으로 결정론적으로 수렴한다. 상수-α MC도 수렴하지만 — 다른 답으로 수렴한다. 이 두 답을 이해하면 두 방법의 본질적 차이가 드러난다.
다음 8개 에피소드를 관찰했다 — A,0,B,0 / B,1 ×6 / B,0. 즉 A는 한 번 보였고 보상 0과 함께 B로 갔다가 0으로 끝났다. B는 8번 중 6번 +1로, 2번 0으로 끝났다.
V(B)는 모두 동의할 것이다 — 3/4. 그런데 V(A)는? 두 답이 가능하다.
답 1 (TD): A에 있었던 100%가 보상 0과 함께 B로 갔다. B의 가치가 3/4이니 A도 3/4여야 한다 — 먼저 마르코프 모델을 세우고 그로부터 계산한 값이다.
답 2 (MC): A를 한 번 봤고 그 반환값은 0이었다. 따라서 V(A)=0 — 훈련 데이터에 대해 오차가 정확히 0인 값이다.
§ 4Sarsa와 Q-러닝 — 제어로 가다
이제 제어 문제 — 최적 정책 찾기 — 로 간다. 늘 그렇듯 GPI 패턴을 따르되, 평가 부분에 TD 방법을 쓴다. 첫 단계는 상태 가치 대신 행동 가치 qπ(s,a)를 배우는 것이다. 이제 상태에서 상태로가 아니라 상태-행동 쌍에서 상태-행동 쌍으로의 전이를 본다. 형식적으로 두 경우는 동일하므로, TD(0)의 수렴 정리가 그대로 적용된다.
Sarsa는 온-정책이다 — 행동 정책 π에 대해 qπ를 계속 추정하면서, 동시에 π를 qπ에 대해 탐욕적인 쪽으로(예: ε-탐욕) 변경한다. 실제로 다음에 취해진 행동 At+1의 가치를 목표에 쓴다는 점이 핵심이다. 모든 상태-행동 쌍이 무한 번 방문되고 정책이 극한에서 탐욕 정책으로 수렴하면(예: ε=1/t), Sarsa는 확률 1로 최적 정책과 행동 가치로 수렴한다.
강화학습 초기의 돌파구였던 Q-러닝은 오프-정책이다. 목표에 maxa를 써, 실제로 어떤 정책을 따르든 상관없이 q∗를 직접 근사한다. 정책은 여전히 어떤 쌍이 방문·갱신되는지를 정한다는 점에서 영향을 주지만, 수렴에 필요한 것은 모든 쌍이 계속 갱신되는 것뿐이다. 이 단순함이 분석을 극적으로 쉽게 만들고 초기 수렴 증명을 가능케 했다.
# 매개변수: 스텝 크기 α ∈ (0,1], 작은 ε > 0 모든 s,a 에 대해 Q(s,a) 임의 초기화, 단 Q(terminal,·) = 0 각 에피소드에 대해 반복: S 초기화 에피소드의 각 단계에 대해 반복: Q에서 유도된 정책으로 S에서 A 선택 (예: ε-탐욕) 행동 A 수행, R, S′ 관찰 Q(S,A) ← Q(S,A) + α[ R + γ maxa Q(S′,a) − Q(S,A) ] S ← S′ until S 가 종료 상태
온-정책과 오프-정책의 차이가 가장 선명하게 드러나는 곳이 절벽 걷기(Cliff Walking)다. 시작 S에서 목표 G까지 가는 격자, 아래 한 줄은 절벽 C — 들어가면 −100과 함께 시작점으로 되돌려진다. 다른 모든 전이는 −1. ε-탐욕(ε=0.1)으로 행동을 고른다.
Q-러닝은 절벽 바로 위를 따라가는 최적 경로의 가치를 배운다 — 그러나 ε-탐욕 때문에 가끔 절벽으로 떨어진다. Sarsa는 행동 선택의 위험을 고려하여 격자 위쪽으로 도는 더 길지만 안전한 경로를 배운다. Q-러닝이 최적 정책의 가치를 배움에도, 학습 중 온라인 성능은 우회하는 Sarsa가 더 낫다. 아래 모션에서 두 경로를 나란히 본다.
§ 5기대 Sarsa · 최대화 편향 · 후상태
기대 Sarsa(Expected Sarsa)는 Q-러닝과 Sarsa의 성질을 잇는다. Q-러닝처럼 동작하되, 다음 상태에서 행동의 최댓값 대신 현재 정책 하에서 각 행동이 선택될 확률로 가중한 기댓값을 쓴다.
세 알고리즘의 차이는 백업 다이어그램에 응축된다 — Sarsa는 실제 샘플링된 다음 행동을, Q-러닝은 모든 행동 중 최댓값을, 기대 Sarsa는 정책에 따른 가중 평균을 쓴다. 기대 Sarsa는 다음 행동 At+1을 샘플링할 때 생기는 분산을 제거하므로, 추가 계산을 대가로 더 안정적인 학습을 얻는다. 절벽 걷기에서 학습률 α가 1에 가까울 때, Sarsa는 발산하지만 기대 Sarsa는 안정적이다. 또한 행동 정책과 목표 정책을 분리할 수 있어 — ε-탐욕으로 행동하면서 탐욕적 π로 갱신하면 — 오프-정책 알고리즘이 된다.
해법은 이중 학습(double learning)이다. 표본을 두 세트로 나눠 두 독립 추정치 Q1, Q2를 배운다. 하나로 최대화 행동을 정하고(A∗=argmaxa Q1(a)), 다른 하나로 그 가치를 추정한다(Q2(A∗)) — 이 추정치는 비편향이다. Double Q-러닝은 이 발상을 전체 MDP로 확장한다. 매 단계 동전을 던져 Q1 또는 Q2 중 하나만 갱신한다. 메모리는 두 배가 되지만 단계당 계산량은 늘지 않으며, 예제 MDP에서 최대화 편향으로 인한 해를 사실상 제거한다.
마지막으로 후상태(afterstates). 1장의 틱택토에서 배운 함수는 행동 가치도 일반적 상태 가치도 아니었다 — 에이전트가 수를 둔 직후의 보드 위치를 평가했다. 후상태 가치 함수는 환경 동역학의 초기 부분은 알지만(내 수의 즉각 효과) 전체는 모를 때 유용하다. 게임에서 우리는 각 수의 결과 위치는 알지만 상대의 응답은 모른다. 결정적 이점은 — 서로 다른 위치-수 쌍이 같은 후상태를 낳을 때, 전통적 행동 가치 함수는 둘을 따로 평가해야 하지만 후상태 가치 함수는 둘을 즉시 동등하게 평가한다. 한쪽에 대한 학습이 곧바로 다른 쪽으로 전이된다.