On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

기술 요약: 시간차 학습(Temporal Difference Learning)의 분산과 제어 변수(Control Variates)를 이용한 분산 감소에 관하여

문제 정의
정책 평가(Policy evaluation)는 강화 학습(RL)의 근본적인 과제입니다. 몬테카를로(Monte Carlo, MC) 방법은 가치 함수에 대한 불편 추정치(unbiased estimates)를 제공하지만, 전체 궤적을 평균 내야 하기 때문에 높은 분산 문제를 겪습니다. 반면, 시간차(TD) 학습은 부트스트래핑(bootstrapping, 다른 추정치를 기반으로 업데이트하는 방식)을 활용하여 분산을 줄이지만, 이 과정에서 편향(bias)이 발생합니다. TD가 특히 온라인 환경에서 분산을 줄이는 정확한 메커니즘이 무엇인지, 그리고 점근적으로 MC와 어떻게 비교되는지는 그동안 미묘한 논쟁의 대상이 되어 왔습니다. 또한, 직접 어드밴티지 추정(Direct Advantage Estimation, DAE)은 심층 강화 학습에서 경험적인 성공을 보여주었으나, 표준 TD와 비교한 분산 경계(variance bounds)에 관한 엄밀한 분석보다는 수렴 특성에만 이론적 근거가 국한되어 있었습니다.

방법론
저자들은 단계적(동기식) 설정 내에서 **테이블 표현(tabular representations)**을 사용하여 다단계 TD 학습의 분산을 분석합니다. 이 설정은 비동기적 업데이트 및 확률적 근사(stochastic approximations)와 관련된 복잡성을 배제하여, 분산 메커니즘만을 명확하게 격리하여 관찰할 수 있게 해줍니다.

1. 분산 분해(Variance Decomposition): 본 논문은 다단계 TD 업데이트의 분산에 대한 재귀 관계(recurrence relation)를 유도합니다. 이 재귀식을 확장함으로써, 저자들은 TD의 점근적 분산을 MC 추정치와 비교합니다.
2. 제어 변수 프레임워크(Control Variate Framework): 저자들은 어드밴티지 함수($A^\pi$)를 정책 평가를 위한 제어 변수로 설정합니다. 저자들은 리턴 추정치의 분산을 최소화하기 위해 어드밴티지 함수를 가치 함수와 동시에 추정하는 회귀 조정 제어 변수(regression-adjusted control variates) 개념을 활용합니다.
3. 직접 어드밴티지 추정(DAE): 본 논문은 DAE(Pan et al., 2022)를 제약된 최소제곱 문제(constrained least-squares problem)로 분석합니다. 어드밴티지 함수 추정치를 회귀 프레임워크 내의 섭동 파라미터(nuisance parameters)로 취급함으로써, 저자들은 DAE 업데이트 규칙을 회귀 조정 제어 변수의 구조를 명시적으로 보여주는 형태로 재구성합니다.
4. 경험적 검증: 이론적 주장은 정교하게 설계된 체인 MDP(Chain MDP) 환경을 통해 입증됩니다. 이 실험들은 보상 마스킹(reward masking), 스티키 전이(sticky transitions) 등의 정도와 상태-행동 커버리지(state-action coverage)를 변화시켜 MC, TD, DAE의 점근적 동작을 테스트합니다.

핵심 기여

1. TD의 점근적 분산 경계: 저자들은 단계적(동기식) 및 IID(비동기식) 설정 모두에서 다단계 TD 학습의 점근적 분산이 **몬테카를로 방법의 분산에 의해 상한이 결정됨(upper-bounded)**을 증명합니다.

   • 메커니즘: 본 논문은 TD가 단순히 편향-분산 트레이드오프에 의해서만이 아니라, 더 큰 독립적 궤적 풀을 효과적으로 집합(aggregating)함으로써 분산을 줄인다는 점을 밝혀냅니다. 부트스트래핑되는 상태들이 다양하고 상관관계가 낮을 때, 그 값들을 평균 내는 것은 분산을 줄입니다. 반대로, 부트스트래핑되는 상태들이 동일하거나(상관관계가 높으면), TD의 분산 감소 능력은 약화되며 점근적으로 MC의 분산에 수렴하게 됩니다.
   • 호라이즌 효과(Horizon Effect): 고정된 샘플 수에 대해, 짧은 호라이즌 업데이트(작은 $k$)는 긴 호라이즌 단일 업데이트보다 적은 분산을 초래합니다.

2. 회귀 조정 제어 변수로서의 DAE: 본 논문은 어드밴티지 함수가 MC 추정치를 위한 제어 변수 역할을 할 수 있음을 보여줍니다. 나아가 **직접 어드밴티지 추정(DAE)**이 가치 함수와 어드밴티지 함수를 동시에 추정하는 회귀 조정 제어 변수의 일종임을 확립합니다.

   • 분산 경계: 대규모 샘플 한계(large-sample limit)에서, DAE는 표준 TD보다 더 타이트한 분산 상한을 달가합니다. 구체적으로, DAE의 분산은 어드밴티지 함수에 의해 조정된 MC 추정치(MC-A)의 분산에 의해 제한되며, 이는 표준 MC의 분산보다 작거나 같습니다.

3. 경험적 예시:

   • 결정론적 환경에서는 부트스트래핑되는 상태가 동일하므로, TD는 MC에 비해 분산을 줄이지 못하며, 이는 궤적 다양성에 대한 이론적 의존성을 확인시켜 줍니다.
   • 확률적 전이 환경에서 TD는 기대되는 편향-분산 트레이드오프를 보여주며, DAE는 어드밴티지 함수가 분산을 완전히 설명하기 때문에 벨만 반복(Bellman iterations)과 유사하게 빠르게 수렴합니다.
   • 보상 마스킹 시나리오(행동으로 설명할 수 없는 보상 분산이 존재하는 경우)에서, DAE의 어드밴티지 추정치는 분산을 완전히 제거할 수 없으므로 벨만 반복과 비교했을 때 약간의 점근적 격차가 발생하지만, 여전히 TD보다는 우수한 성능을 보입니다.
   • 낮은 커버리지(low-coverage) 설정(언더샘플링된 행동 공간)에서, DAE는 신뢰할 수 없는 어드치 추정치로 인해 작은 샘플 편향(small-sample bias)을 겪을 수 있지만, 여전히 TD보다 낮은 평균 제곱 오차(MSE)로 수렴하여 불완전한 제어 변수 상황에서도 강건함을 시사합니다.

결과 및 의의
본 논문은 부트스트래핑의 분산 감소 능력을 단순한 "편향-분산 트레이드오프"라는 직관을 넘어, **궤적 집합(trajectory aggregation)**이라는 메커니즘을 통해 엄밀하게 설명합니다. TD가 MC보다 우월하기 위한 조건은 부트스트래핑되는 상태의 다양성에 달려 있음을 명확히 합니다.

또한, 본 연구는 DAE에 대한 이론적 토대를 제공하며, DAE를 제어 변수 방법론으로 프레임화함으로써 심층 강화 학습에서 DAE가 보이는 경험적 성공을 설명합니다. 결과에 따르면, 어드밴티지 함수를 제어 변수로 활용하는 것이 표준 TD보다 더 타이트한 분산 경계를 달성할 수 있는 원칙적인 경로를 제시합니다.

한계 및 범위
저자들은 몇 가지 한계를 언급합니다:

• 이론적 결과는 단계적 및 IID 설정에 대해 도출되었으며, 실제 마르코프 샘플링 스킴(Markovian sampling schemes)으로의 일반화는 여전히 미해결 과제로 남아 있습니다.
• 본 분석은 분산 감소에 집중합니다. DAE는 추가적인 계산 비용(최소제곱법 해결)과 저장 공간 요구 사항을 수반합니다.
• DAE에 대한 타이트한 분산 경계는 제어 변수 계수가 최적일 때의 대규모 샘플 근사에 의존합니다. 경험적 결과는 작은 샘플 규모에서도 이점을 시사하지만, DAE의 작은 샘플 편향에 대한 엄밀한 분석은 향후 과제로 남겨두었습니다.

결론적으로, 본 논문은 독립적인 궤적의 집합을 이해하는 것이 TD의 분산 감소의 핵심이며, 제어 변수 회귀(DAE를 통한)가 정책 평가의 분산을 더욱 줄일 수 있는 원칙적인 경로를 제공한다고 결론짓습니다.