[Reinforcement Learning] Temporal Difference policy Evaluation(Prediction)

2025.06.29 - [Data & Research] - [Reinforcement Learning] Table of Contents

---

이번에는 시간차 학습 (Temporal Difference, TD) 방법으로 policy evaluation하는 방법을 알아보겠습니다. 시간차학습이란 모델을 모르는 환경에서 경험을 통해 가치 함수를 추정하는 방법입니다. 몬테카를로(MC)의 샘플 기반 학습 아이디어와 동적 계획법(DP)의 부트스트래핑(Bootstrapping) 아이디어를 결합한 형태입니다.

 

1. TD 학습의 기본 원리

TD 학습을 이해하기 위해 먼저 MC와 업데이트 목표(리턴)를 어떻게 다르게 정의하는지 비교해 보겠습니다.

• MC의 업데이트 목표 (실제 보상): 에피소드가 끝난 후 얻어지는 전체 보상의 합입니다.
  \[ G_t \overset{\text{def}}{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-1-t} R_T \]
• TD(0)의 업데이트 목표 (추정된 보상): 만약 보상이 MDP를 따른다고 가정한다면 "상태가치함수"로 이를 대체하고자 하는 발상입니다.위의 MC식에서 $$ \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-1-t} R_T $$ 부분을 상태가치함수로 대체할 수 있다는 건데요. 
  \[ G_t^{(1)} \overset{\text{def}}{=} R_{t+1} + \gamma V(S_{t+1}) \]

TD는 MC처럼 에피소드가 끝날 때까지 기다리지 않고, 한 스텝 진행한 후의 정보(\(R_{t+1}\))와 미래에 대한 현재의 예측(\(V(S_{t+1})\))을 이용해 바로 현재의 예측(\(V(S_t)\)을 수정합니다. 이처럼 자신의 다른 예측을 이용해 현재 예측을 업데이트하는 것을 부트스트래핑(Bootstrapping)이라고 합니다.

부트스트래핑(Bootstrapping) :  '가지고 있는 것을 이용해 자신을 개선한다'는 근본적인 철학을 말합니다. 이러한 맥락에서 통계학에서 사용되는 부트스트래핑은 일반적으로 재표집 (Resampling with Replacement)을 의미하죠? 강화학습에서의 부트스트래핑은  현재의 (불완전한) 가치 추정치를 이용하여 다른 상태의 가치 추정치를 업데이트하는 것을 의미합니다.

• TD Target: update의 '목표'가 되는 부분입니다. \(V(S_t)\)가 이 값에 가까워지도록 조정됩니다.
  \[ \text{TD Target} = R_{t+1} + \gamma V(S_{t+1}) \]
• TD Error \(\delta_t\)): 현재 예측과 TD target 사이의 차이입니다. 이 오차를 줄이는 방향으로 학습이 진행됩니다.
  \[ \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \]
  (이 TD 오차는 DP의 우선순위 스위핑에서 사용된 '벨만 오차'의 sample 기반 버전으로 볼 수 있습니다.)

 

2. N-step TD

TD(0)는 단 한 스텝만 내다보고 부트스트래핑을 합니다. 만약 두 스텝, 세 스텝, 혹은 그 이상을 내다본 후 부트스트래핑을 한다면 어떻게 될까요? 이것이 바로 N-step TD의 아이디어입니다.

일반화된 TD 업데이트 규칙은 \(V(S) \leftarrow V(S) + \alpha(G_t^{(n)} - V(S))\) 입니다. 여기서 N-step return \(G_t^{(n)}\)은 아래와 같이 정의됩니다.

• 1- step TD (TD(0)): \(G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})\)
  1 스텝의 실제 보상 + 1 스텝 후의 상태 가치 추정치
• 2- step TD: \(G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2})\)
  2 스텝의 실제 보상 + 2 스텝 후의 상태 가치 추정치
• 3- step TD: \(G_t^{(3)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 V(S_{t+3})\)
  3 스텝의 실제 보상 + 3 스텝 후의 상태 가치 추정치
•                 ...
• ∞- step TD: \(G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots\)
  끝까지의 실제 보상 합. 이는 몬테카를로(MC) 방법과 동일합니다.

이처럼 N- step TD는 TD와 MC를 연결합니다. 일반화된 N- step return은 다음과 같습니다.

\[ G_t^{(n)} \overset{\text{def}}{=} R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n}) \]

 

3. 편향-분산 트레이드오프 (Bias-Variance Trade-off)

N을 몇으로 설정할 것인가가 중요할텐데요, 편향(Bias)과 분산(Variance) 사이의 trade-off관계가 존재합니다. 

• n=1에 가까울수록:
  • 높은 편향 (High Bias): 업데이트 목표가 실제 리턴이 아닌, 부정확할 수 있는 추정치 \(V(S_{t+1})\)에 크게 의존하므로 편향이 높습니다.
  • 낮은 분산 (Low Variance): 업데이트가 단 하나의 랜덤한 결과(보상 \(R_{t+1}\)과 전이 \(S_{t+1}\))에만 의존하므로 분산이 낮습니다.
• n=∞에 가까울수록:
  • 낮은 편향 (Low Bias): 업데이트 목표가 추정치가 아닌, 에피소드의 실제 전체 리턴이므로 편향이 없습니다.
  • 높은 분산 (High Variance): 하나의 리턴을 계산하는 데 많은 랜덤한 결과(보상, 행동)가 포함되므로, 에피소드마다 리턴 값이 크게 달라져 분산이 높습니다.

 

4. N-step 추정치의 통합

결국 N이라는 step을 어떻게 설정하느냐에 따라 산출되는 값이 달라지는데요, 그럼 이것들을 통합해서 하나로 취합하는 방법은 없을까요? 가장 간단하게는 그냥 단순하게 산술평균을 하는 방법이 있을 것 같긴합니다. 그런데 이건 2가지 측면에서 좀 naive한 방법이라고 할 수 있는데요. 

1) Bias-Variance 간 Trade-off가 존재한다고 했는데, 적절한 균형점을 찾아낸 것이 아니라 그냥 계산의 단순성을 위한 선택을 했습니다. 

2) 여러 N-step 추정치를 집계하고 있는데 집계 후 적절한 scaling(혹은 normalization)에 대한 고민이 없었습니다. 

 

그럼, 이런 요소들을 고려하면 어떻게 취합하면 될까요? 단순히 산술 평균을 내는 것이 아니라, 기하급수적으로 감소하는 가중치를 부여하여 평균을 낼 수 있습니다. 이렇게 계산된 새로운 목표값을 λ-리턴(lambda-return)이라고 합니다.

λ-리턴 \(G_t^\lambda\)는 아래와 같이 모든 N-스텝 리턴 \(G_t^{(n)}\)들의 가중 평균으로 정의됩니다.

\[ G_t^\lambda \overset{\text{def}}{=} (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)} \quad (0 \le \lambda \le 1) \]

• 이 식에서 각 N-스텝 리턴 \(G_t^{(n)}\)에 곱해지는 가중치는 \((1-\lambda)\lambda^{n-1}\) 입니다.
• \(\lambda\)가 0과 1 사이의 값이므로, \(n\)이 커질수록(즉, 더 먼 미래를 예측하는 리턴일수록) 가중치 \(\lambda^{n-1}\)는 기하급수적으로 작아집니다.
• 단기 예측(TD에 가까움)에 높은 가중치를, 장기 예측(MC에 가까움)에 낮은 가중치를 부여합니다.

참고: 가중치의 합은 1일까?

기하급수(등비수열의 합) 공식을 이용하면 가중치의 총합을 확인할 수 있습니다. \(0 \le \lambda < 1\) 일 때, 무한 등비급수 \(\sum_{k=0}^{\infty} \lambda^k = \frac{1}{1-\lambda}\) 입니다. 따라서 가중치의 합은,

$$ \sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} = (1-\lambda) \sum_{k=0}^{\infty} \lambda^k = (1-\lambda) \left(\frac{1}{1-\lambda}\right) = 1 $$

이므로, \(G_t^\lambda\)는 수학적으로 타당한 가중 평균임을 알 수 있습니다.

하이퍼파라미터 \(\lambda\)는 0과 1 사이의 값을 가지며, 이 값을 조절하여 TD와 MC의 특성을 섞을 수 있습니다. 즉, 편향과 분산의 관계를 세밀하게 조정하는 역할을 합니다.

• \(\lambda = 0\) 일 때 (TD(0)):
  \(\lambda=0\)을 대입하면 가중치 \((1-0) \cdot 0^{n-1}\)는 \(n=1\)일 때만 1이고 나머지는 모두 0이 됩니다. 따라서,이는 1-스텝 TD, 즉 TD(0)와 정확히 동일합니다. (높은 편향, 낮은 분산) $$ G_t^0 = G_t^{(1)} $$
• \(\lambda = 1\) 일 때 (TD(1)):
  \(\lambda\)가 1에 가까워질수록, 가중치는 점점 더 큰 \(n\)값을 가진 보상(장기 예측)에 쏠리게 됩니다. 극학의 케이스에는 (\(\lambda \to 1\)) 에피소드의 끝까지 모든 실제 보상을 고려하는 것과 같아집니다. 따라서 이는 몬테카를로(MC) 방법과 유사한 특성을 갖게 됩니다. (낮은 편향, 높은 분산)

 

λ-리턴의 정의를 보면, 이를 계산하기 위해서는 원칙적으로 에피소드가 끝날 때까지 기다려야 합니다(\(G_t^{(n)}\)들을 모두 알아야 하므로). 이는 TD의 장점인 'Online Learning'을 불가능하게 합니다. 이를 'Forward-view' TD(λ)라고 하며, 이론적인 개념에 가깝습니다.

실제 알고리즘에서는 이와 수학적으로 동일한 결과를 내면서도, 매 스텝마다 온라인으로 학습할 수 있는 'Backward-view' TD(λ)를 사용합니다. 이 방법은 자격 추적(Eligibility Trace)이라는 메커니즘을 사용하여 과거의 어떤 상태-행동이 현재의 TD 오차에 얼마나 '자격'이 있는지를 추적하고, 오차가 발생했을 때 자격이 있는 과거의 모든 상태들에게 책임을 분배하여 가치를 업데이트합니다. 이것이 TD(λ) 알고리즘의 표준적인 구현 방식입니다.