기술적 요약: 평균 보상과 할인된 TD 학습 간의 격차 해소

문제 제기

시간차 (TD) 학습은 강화학습의 핵심이지만, 평균 보상 환경에서의 이론적 분석은 할인된 환경에 비해 현저히 뒤처져 있습니다. 할인된 경우, 벨만 연산자는 축소 사상 (contraction mapping) 이므로 유일한 해를 보장하고 수렴 분석이 직관적입니다. 반면, 평균 보상 환경에서는 벨만 연산자가 어떤 노름에 대해서도 축소되지 않으며, 해당 벨만 방정식의 해는 유일하지 않습니다 (가산 상수만큼만 정의됨).

할인된 경우에 비해 평균 보상 TD 를 다루는 기존 문헌은 다음과 같은 여러 한계를 겪고 있습니다:

1. 제한적인 가정: 많은 방법론들이 $\Phi\theta \neq ce$와 같은 가정 (예: 표형 설정을 배제하는 조건) 을 요구합니다.
2. 수렴 보장: 일부 접근법은 유일한 결정론적 해가 아닌, 표본 경로에 의존하는 고정점이나 집합으로의 수렴만을 보장합니다.
3. 차원 의존성: 수렴 경계는 종종 매개변수 차원 $d$의 명시적 인자를 포함합니다.
4. 조건수 스케일링: 최첨단 샘플 복잡도는 문제의 조건수에 대해 4 차 의존성 ($O(\eta^{-4})$) 을 보이는 반면, 할인된 환경에서는 2 차 스케일링 ($O(\eta^{-2})$) 을 달성합니다.
5. 알고리즘적 복잡성: 이전 연구에서 더 나은 스케일링을 달성하려면 중첩 루프와 같은 복잡한 분산 감소 기법이 필요하여, 표준 TD 의 단순성에서 벗어났습니다.

방법론

저자들은 벨만 방정식의 해를 제약 최적화 문제로 공식화함으로써 평균 보상 환경에서의 정책 평가를 위한 새로운 접근법을 제안합니다. 핵심 통찰은 상대 가치 함수 $W^*$가 정상 상태 제약 조건 ($\mu^\top W^* = 0$) 을 만족해야 한다는 점입니다.

1. 더블-체인 알고리즘

$\Pi = I - e\mu^\top$인 투영된 벨만 방정식 $W^* = \Pi T_\pi W^*$를 풀기 위해, 저자들은 확률적 업데이트 규칙을 유도합니다. 이 환경에서의 확률적 근사 (stochastic approximation) 의 주요 과제는 "이중 샘플링" 문제입니다: $\mu\mu^\top(R + W_t)$항을 추정하려면 확률 변수의 곱에 대한 기댓값이 필요하며, 이는 상관관계로 인해 단일 궤적로는 추정할 수 없습니다.

이를 해결하기 위해 저자들은 각 반복에서 두 개의 독립적인 마르코프 체인 ($\{s_t\}$와 $\{\hat{s}_t\}$) 을 활용하는 더블-체인 알고리즘을 도입합니다.

• 업데이트 규칙: 매개변수 벡터 $\theta_t$는 두 가지 구성 요소를 사용하여 업데이트됩니다:
  • $g(s_t, s'_t, \theta_t)$: 표준 TD 오차 항 $D(R + P\Phi\theta_t - \Phi\theta_t)$를 추정합니다.
  • $f(s_t, \hat{s}_t, \theta_t)$: 상관관계를 끊기 위해 독립 샘플 $\hat{s}_t$를 사용하여 제약 항 $-\mu\mu^\top(R + \Phi\theta_t)$를 추정합니다.
• 선형 근사: 이 방법은 업데이트를 특징 공간에 투영함으로써 선형 함수 근사 ($W \approx \Phi\theta$) 로 일반화됩니다.

2. 싱글-체인 알고리즘

두 개의 체인을 유지하는 계산 오버헤드를 피하기 위해, 저자들은 Gradient TD(GTD) 에서 영감을 받은 싱글-체인 알고리즘을 제안합니다.

• 메커니즘: 두 번째 독립 상태 $\hat{s}_t$를 샘플링하는 대신, 알고리즘은 기댓값 $E[\phi(s)] = \Phi^\top\mu$를 추적하는 보조 변수 $w_t$를 유지합니다.
• 업데이트: 더블-체인 업데이트의 $\phi(\hat{s}_t)$항을 $w_t$로 대체합니다. 변수 $w_t$는 $\Phi^\top\mu$로 수렴하도록 별도의 확률적 근사 단계를 통해 업데이트됩니다.
• 트레이드오프: 이는 샘플링 요구 사항을 단일 궤적으로 단순화하지만, 분석 결과 더블-체인 변형에 비해 조건수에 대한 의존성이 다소 더 나쁜 것으로 나타납니다.

3. 이론적 프레임워크: 그라디언트 분할

수렴 분석은 그라디언트 분할 (gradient splitting) 기법 [19] 에 의존합니다. 저자들은 알고리즘의 기대 업데이트 방향이 특정 복합 2 차 함수의 "그라디언트 분할"로 작용함을 보여줍니다:
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
이를 통해 저자들은 근본적인 벨만 연산자의 비축소성에도 불구하고 표준 확률적 경사 하강법 (SGD) 재귀 기법을 사용하여 알고리즘을 분석할 수 있습니다.

주요 기여

이 논문은 다음과 같은 특징들을 동시에 달성함으로써 평균 보상과 할인된 TD 학습 간의 이론적 격차를 해소했다고 주장합니다:

1. 유일한, 표본 독립적 고정점: 제안된 알고리즘들은 무작위 궤적 및 초기화와 무관한 단일 결정론적 해 $\theta^*$로 거의 확실하게 (almost surely) 수렴합니다.
2. 표형 및 선형 환경 적용성: 분석은 $e \notin \text{span}(\Phi)$와 같은 제한적인 가정 없이 표형 경우 ($\Phi = I$) 와 선형 함수 근사 모두에 대해 성립합니다.
3. 차원 무관 경계: 수렴 경계는 $\|\theta^*\|$ 또는 $\|\theta_0\|$에 내재된 것을 제외하고 차원 $d$의 명시적 인자를 포함하지 않습니다.
4. 최종 반복 수렴: 결과는 반복 평균에 의존하는 것이 아니라, 할인된 TD 의 표준과 일치하는 마지막 반복 (last iterate) 에 대해 보장됩니다.
5. 개선된 조건수 스케일링:
   • 더블-체인 알고리즘은 $\eta_1 = \min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$로 정의된 조건수에 대해 $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$의 샘플 복잡도를 달성합니다. 이는 할인된 환경에서 관찰되는 2 차 스케일링과 일치합니다.
   • 싱글-체인 알고리즘은 $\tilde{O}(\epsilon^{-1}\eta^{-4})$(4 차) 를 달성하여 일부 이전 연구보다 개선되었지만 더블-체인 변형보다는 다소 나쁩니다.
6. 알고리즘적 단순성: 2 차 스케일링은 중첩 루프나 주기적 전체 배치와 같은 분산 감소 기법 없이 달성되어, 단순한 TD 업데이트의 단순성을 유지합니다.

결과

저자들은 상수 및 감소하는 스텝 크기를 가진 i.i.d. 및 마르코프 샘플링 하에서 두 알고리즘에 대한 유한 샘플 분석을 제공합니다.

• 이론적 경계: 정리 4.1–4.3 은 수렴률과 샘플 복잡도를 확립합니다. 더블-체인 방법은 매개변수 스케일링 측면에서 할인된 TD 의 최첨단 수준과 일치합니다.
• 수치 실험: 알고리즘은 OpenAI Gym 과 MO-Gymnasium 의 15 개 표형 MDP 에서 테스트되었습니다.
  • 결과는 제안된 방법들이 진정한 해에 대한 근사 오차 측면에서 기존 베이스라인 ([10], [11], [12], [17], [18], [21] 포함) 보다 일반적으로 더 나은 성능을 보임을 나타냅니다.
  • 실험은 방법들이 유일한 해로 수렴하는 것을 확인한 반면, 일부 베이스라인 (집합이나 표본 의존점으로 수렴하는 경우) 은 표형 환경에서 더 높은 분산이나 오차를 보임을 입증했습니다.

의의

이 논문은 평균 보상 TD 분석과 관련된 지속적인 이론적 주의 사항을 해결했다고 주장합니다. 그라디언트 분할과 두 체인 (또는 보조 변수가 있는 단일 체인) 샘플링 전략을 활용함으로써, 저자들은 평균 보상 TD 가 할인된 TD 와 동일한 유리한 수렴 속성을 달성할 수 있음을 보여줍니다:

• 유일성: 잘 정의된 유일한 해로의 수렴.
• 일반성: 제한적인 가정 없이 표형 및 선형 환경에 적용 가능.
• 효율성: 복잡한 분산 감소 장치 없이 조건수에 대한 2 차 의존성 달성.

이 연구는 평균 보상 환경의 이론적 어려움을 벨만 연산자의 비축소성을 처리하기 위한 특정 샘플링 전략을 활용하면서 문제를 제약 최적화 작업으로 재구성함으로써 극복할 수 있음을 시사합니다.