적격 흔적

편집 역사 토론
통계 소프트웨어 마지막 수정: 2026-07-30 04:06:12

1. 개요[편집]

적격 흔적(eligibility trace)은 “방금 받은 오차의 책임이 과거의 어느 상태·특징에 얼마나 있는가”를 기록해 두는 단기 기억 벡터이며, 이걸 매 스텝 감쇠시키면서 시간차 학습의 오차 δt\delta_t 하나를 그 벡터 전체에 뿌리는 것이 TD(λ) 계열 알고리즘의 핵심 기제다. 파라미터 벡터 ww 와 같은 차원의 zz 하나를 더 들고 다니는 대가로, 한 스텝짜리 갱신을 여러 스텝짜리 신용 할당으로 바꿔준다.

zt=γλ zt−1+∇wv^(St,wt),wt+1=wt+α δt ztz_t = \gamma\lambda\, z_{t-1} + \nabla_w \hat{v}(S_t, w_t), \qquad w_{t+1} = w_t + \alpha\,\delta_t\, z_t

λ=0\lambda = 0 이면 ztz_t 가 현재 특징벡터 그대로라 TD(0)로 되돌아가고, λ=1\lambda = 1 이면(그리고 γ=1\gamma = 1 이면) 흔적이 전혀 안 줄어서 몬테카를로가 된다. 즉 λ는 부트스트래핑과 실제 수익 사이를 연속적으로 오가는 손잡이다. “TD냐 MC냐”라는 이분법이 사실은 눈금 하나짜리 슬라이더였다는 걸 알려준 게 이 아이디어의 지분이다.

2. 전방 관점 — λ-수익[편집]

먼저 미래를 다 아는 신의 시점에서 정의부터 본다. nn-스텝 수익

Gt(n)=Rt+1+γRt+2+⋯+γn−1Rt+n+γnv^(St+n,w)G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n \hat{v}(S_{t+n}, w)

을 nn 에 대해 기하가중으로 섞은 것이 λ-수익이다.

Gtλ=(1−λ)∑n=1∞λn−1Gt(n)G_t^{\lambda} = (1-\lambda)\sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}

가중치 (1−λ)λn−1(1-\lambda)\lambda^{n-1} 의 총합이 정확히 1이라 이건 볼록결합이고, 유한 에피소드에서는 종료 이후의 항이 전부 GtG_t 와 같아지므로 꼬리를 모아 Gtλ=(1−λ)∑n=1T−t−1λn−1Gt(n)+λT−t−1GtG_t^{\lambda} = (1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_t^{(n)} + \lambda^{T-t-1}G_t 로 쓴다. 목표를 GtλG_t^\lambda 로 두고 w←w+α[Gtλ−v^(St,w)]∇v^w \leftarrow w + \alpha[G_t^\lambda - \hat{v}(S_t,w)]\nabla\hat{v} 하는 것을 전방 관점(forward view)이라 부른다. 개념은 깔끔한데 문제가 하나 있다 — 에피소드가 끝나야 계산이 되므로 온라인으로는 못 돌린다. 이론용 정의라고 보면 된다.

3. 후방 관점 — 흔적으로 뒤집기[편집]

후방 관점(backward view)은 시선을 반대로 돌린다. 매 스텝 TD 오차 δt=Rt+1+γv^(St+1,w)−v^(St,w)\delta_t = R_{t+1} + \gamma\hat{v}(S_{t+1},w) - \hat{v}(S_t,w) 를 계산해서, 지금까지 지나온 모든 특징에 흔적의 크기만큼 나눠 뿌린다. 상태 하나가 kk 스텝 전에 방문됐다면 그 흔적은 (γλ)k(\gamma\lambda)^k 로 줄어 있으므로, 오래된 상태일수록 적게 받는다. 이 감쇠율이 λ-수익의 기하가중과 정확히 같은 비율이라는 게 요점이다.

계산 구조도 완전히 뒤집힌다. 전방 관점은 상태 하나를 붙들고 그 상태의 미래를 전부 모아 목표를 만들지만, 후방 관점은 스칼라 오차 하나를 만들어 과거 전부에 흩뿌린다. 저장해야 할 것이 “미래의 보상 열”에서 ”ww 와 같은 크기의 벡터 하나”로 바뀌므로, 메모리는 O(∣w∣)O(|w|), 스텝당 연산도 O(∣w∣)O(|w|) 로 끝난다. 에피소드 길이가 얼마든 비용이 늘지 않는다는 것이 이 뒤집기의 실질적 수익이다.

두 관점은 오프라인 λ-수익 등가 정리로 묶인다. 에피소드 동안 갱신을 누적만 해두고 끝나서 한 번에 적용하면, 후방 관점의 총 갱신량이 전방 관점의 총 갱신량과 정확히 일치한다. 온라인에서는 ww 가 도중에 바뀌므로 근사적으로만 같은데, 이 틈을 메운 것이 아래의 True Online TD(λ)다.

4. 누적·대체·더치 — 흔적 세 종류[편집]

표 형식(tabular)에서 상태 ss 의 흔적을 어떻게 올릴 것인가에 따라 계보가 갈린다.

  • 누적 흔적(accumulating): 방문할 때마다 z(s)←γλz(s)+1z(s) \leftarrow \gamma\lambda z(s) + 1. 짧은 구간을 여러 번 왔다 갔다 하면 흔적이 1을 훌쩍 넘어가고, 그 상태에 유효 학습률이 곱절로 걸려 발산하기 쉽다.
  • 대체 흔적(replacing): 방문 시 z(s)←1z(s) \leftarrow 1 로 덮어쓴다. 상한이 1로 잡히니 훨씬 안정적이며, 반복 방문이 잦은 문제에서 학습률 범위가 눈에 띄게 넓어진다.1
  • 더치 흔적(dutch): 함수근사에서 위 두 방식의 “올바른” 일반화. zt=γλzt−1+(1−αγλ zt−1⊤xt) xtz_t = \gamma\lambda z_{t-1} + (1 - \alpha\gamma\lambda\, z_{t-1}^\top x_t)\,x_t 로, 학습률 α\alpha 가 흔적 갱신식 안에 들어온다는 점이 특이하다.

특징이 겹치는 함수근사에서는 “그 상태만 1로 덮어쓴다”는 조작 자체가 정의되지 않기 때문에, 대체 흔적을 선형근사로 억지로 밀면 이론적 근거가 사라진다. 더치 흔적은 그 자리를 대신하려고 만들어졌다.

5. True Online TD(λ)[편집]

판 세이언과 서턴(2014)은 온라인 λ-수익 알고리즘(매 스텝마다 지금까지의 데이터로 에피소드 처음부터 다시 갱신했다고 가정하는, 계산량이 폭발하는 이상적 알고리즘)과 정확히 같은 가중치 열을 O(d)O(d) 비용으로 뽑아내는 갱신식을 찾아냈다.

wt+1=wt+αδtzt+α(wt⊤xt−wt−1⊤xt)(zt−xt)w_{t+1} = w_t + \alpha\delta_t z_t + \alpha\left(w_t^\top x_t - w_{t-1}^\top x_t\right)\left(z_t - x_t\right)

여기서 ztz_t 는 더치 흔적이다. 마지막 항은 “직전 갱신 때문에 같은 특징의 예측값이 이미 얼마나 움직였는가”를 되돌려 놓는 보정으로, 근사가 아니라 등가를 만들어 준다. 선형근사에서 기존 TD(λ)보다 성능이 같거나 낫고 계산량은 상수배만 늘어나서, 요즘 선형 함수근사를 쓴다면 사실상 기본값이다. 같은 논리로 True Online SARSA(λ)도 나온다.

6. 제어 — SARSA(λ)와 흔적 절단[편집]

행동가치로 옮기면 흔적도 상태-행동 쌍 위에 얹힌다. SARSA(λ)는 온폴리시라 별 고민 없이 z←γλz+∇q^(St,At,w)z \leftarrow \gamma\lambda z + \nabla \hat{q}(S_t,A_t,w) 를 유지하면 되고, 격자 세계에서 목표 지점을 한 번만 밟아도 지나온 경로 전체의 QQ 가 한꺼번에 올라가는 그림이 나온다. SARSA(0)이 매 에피소드 한 칸씩 정보를 뒤로 미는 것과 대비된다. 절벽 걷기 같은 예제에서 λ를 올리면 학습 곡선이 초반부터 확 내려앉는 것이 이 때문이다.

문제는 오프폴리시다. 왓킨스 Q(λ) 는 Q러닝의 목표정책이 탐욕정책이라는 점을 지키기 위해, 탐험적(비탐욕) 행동을 취한 순간 흔적을 전부 0으로 날린다. 그 이후의 궤적은 목표정책이 걸었을 길이 아니므로 과거에 신용을 줄 근거가 사라지기 때문이다. 논리는 정직하지만 대가가 크다 — ε\varepsilon 이 조금만 커도 흔적이 몇 스텝 못 가서 잘려 나가 λ를 올린 이득이 증발한다. 절단하지 않는 펭 Q(λ)는 흔적을 길게 유지하는 대신 온폴리시도 오프폴리시도 아닌 어중간한 목표로 수렴한다. 이 딜레마를 중요도 비율 없이 정리한 것이 트리 백업(λ)이고, 비율을 1로 잘라 분산을 묶은 것이 Retrace(λ)다.

7. 왜 중간 λ가 이기는가[편집]

λ는 결국 편향-분산 손잡이다. 작은 λ는 아직 틀린 추정값 v^\hat{v} 에 크게 기대므로 편향이 크고, 큰 λ는 실제 보상 열을 길게 쓰므로 분산이 크다. 무작위 보행·산 오르기(mountain car) 같은 고전 시험대에서 성능 대 λ 곡선을 그리면 대체로 0.8~0.95 근처에서 바닥을 찍는 U자가 나오고, 양 끝(TD(0), MC)이 둘 다 진다. “둘 중 뭐가 낫냐”의 정답이 “둘을 섞어라”인 흔한 결말.

흔적의 발상은 가치 예측 바깥에서도 살아남았다. 정책경사·액터-크리틱과 그 위에 신뢰 영역을 얹은 신뢰 영역 정책 최적화 계열에서 쓰는 일반화 이점 추정(GAE)의 A^t=∑l≥0(γλ)lδt+l\hat{A}_t = \sum_{l\ge 0}(\gamma\lambda)^l \delta_{t+l} 은 λ-수익과 같은 기하가중이며, 실질적으로 이점 함수 위의 적격 흔적이다.2 다만 심층 강화학습에서 흔적 벡터 자체를 그대로 쓰는 경우는 드물다 — 경험 재생 버퍼에서 무작위로 뽑은 전이 하나를 학습하는 구조와 “궤적을 따라 감쇠하는 기억”이 궁합이 나쁘기 때문이다.3 ∣w∣|w| 가 수천만인 신경망에서 같은 크기의 조밀한 흔적 벡터를 매 스텝 갱신하는 비용도 만만치 않다.4

8. 관련 문서[편집]

9. Footnotes[편집]

  1. Singh & Sutton (1996). 표 형식에서 누적 흔적 TD(1)은 모든 방문 MC(every-visit MC)에, 대체 흔적 TD(1)은 최초 방문 MC(first-visit MC)에 대응한다는 깔끔한 대응 관계도 같은 논문에 있다. ↩

  2. Schulman et al. (2015), High-Dimensional Continuous Control Using Generalized Advantage Estimation. PPO 구현체의 gae_lambda=0.95 라는 기본값이 바로 이 λ다. 튜닝 안 하고 그냥 쓰는 사람이 대부분이라는 게 함정. ↩

  3. 그래서 심층 RL에서 λ의 역할은 대개 nn-스텝 수익(nn=3~5 정도)이 대신 가져갔다. 흔적의 무한합을 유한 절단으로 바꾼 셈인데, 버퍼에서 궤적 조각째 뽑으면 되니 구현이 훨씬 편하다. ↩

  4. 신경과학 쪽에서는 시냅스에 “최근에 활성화됐음” 표식이 잠시 남았다가 나중에 도착한 도파민 신호와 만나 가소성이 일어난다는 자격 흔적(synaptic eligibility trace) 가설이 실제로 실험적 지지를 받고 있다. 알고리즘 이름이 먼저였는데 뇌가 따라 한 모양새라 강화학습 하는 사람들이 좋아하는 떡밥. ↩