Heavy-Ball Q-Learning with Residual Weighting Correction

기술 요약: 잔차 가중치 보정(Residual Weighting Correction)을 적용한 헤비-볼 Q-러닝(Heavy-Ball Q-Learning)

문제 정의
Q-러닝은 명시적인 전이 모델 없이 최적의 Q-함수를 학습하기 위한 강화 학습(RL)의 근본적인 방법입니다. 표준 Q-러닝은 벨만 최적 연산자의 수축 성질(contraction property)에 기초하여 수렴하지만, 할인 계수 $\gamma$가 1에 가까워질수록 이 수축력이 약해져 수렴 속도가 느려지는 문제가 발생합니다. 모멘텀 기반 업데이트, PID형 반복법, 랭크-원 보정(rank-one corrections)과 같은 기존의 가속 방법들은, 특히 능동적인 그리디 정책(greedy policy)이 동적으로 변하는 제어 환경에서 표준 Q-러닝보다 우수하다는 엄격한 이론적 보증을 결여하고 있는 경우가 많습니다. 특정 과제는 비균등 샘플링 가중치를 사용하는 헤비-볼 모멘텀을 Q-러닝에 적용할 때 발생하는데, 표준 가중치 행렬은 특정 스펙트럼 분석에 필요한 "공통 고유벡터(common eigenvector)" 성질(구체적으로는 모든 원소가 1인 벡터)을 파괴하여, 가속을 이론적으로 인증하기 어렵게 만듭니다.

방법론
본 논문은 보정된 헤비-볼 Q-러닝(Corrected Heavy-Ball Q-Learning, HBCQL) 방법을 제안하며, 전환 선형 시스템(Switched Linear System, SLS) 프레임워크를 사용하여 이들의 수렴 및 가속 특성을 입증합니다.

1. 잔차 가중치 보정 (Residual Weighting Correction, CQL):
   저자들은 비균등 샘플링 시 공통 고유벡터의 상실 문제를 해결하기 위해 "보정된" Q-러닝 업데이트(알고리즘 2)를 먼저 도입합니다. 이들은 표준 대각 샘플링 행렬 $D$를 보정 행렬 $H = \delta \Pi_d + D(I - \Pi_d)$로 대체합니다 (여기서 $\Pi_d = \mathbf{1}d^\top$). 이 행렬 $H$는 상수 벡터 $\mathbf{1}$을 자기 자신의 스칼라 배($H\mathbf{1} = \delta\mathbf{1}$)로 매핑하도록 설계되어, 알고리즘의 평균 역학(mean dynamics)에 대한 공통 고유벡터를 복원합니다. 이 보정은 고정점 $Q^\star$를 보존하면서도 특정 구조적 분해를 가능하게 합니다.

2. 헤비-볼 모멘텀 (Heavy-Ball Momentum):
   이 방법은 헤비-볼 모멘텀 항 $\eta(Q_k - Q_{k-1})$을 추가하여 보정된 Q-러닝을 확장합니다(알고리즘 3). 이는 1차 재귀를 2차 시스템으로 변환합니다.

3. SLS 및 합동 스펙트럼 반지름(Joint Spectral Radius, JSR) 분석:
   핵심 분석 도구는 Q-러닝 오차 역학을 전환 선형 시스템(SLS)으로 표현하는 것입니다. 전환 신호(switching signal)는 벨만 연산자에서의 그리디 행동 선택에 의해 결정됩니다. Q-러닝의 수렴 속도는 연관된 전환 행렬 군(family of switching matrices)의 **합동 스펙트럼 반지름(JSR)**에 의해 특징지어집니다.

   • 분해: 저자들은 상태 공간을 공통 고유벡터(또는 헤비-볼의 경우 불변 부분 공간)에 의해 생성되는 부분 공간과 그 직교 보공간으로 분해합니다.
   • 가속 메커니즘: 분석 결과, 전체 시스템의 JSR은 투영된 시스템(공통 방향에 직교하는 방향)의 JSR과 공통 방향을 따르는 역학의 스펙트럼 반지름의 최댓값과 같음을 보여줍니다. 보정 행렬 $H$를 통해 공통 방향을 따르는 역학을 매개변수 $\delta$를 통해 독립적으로 튜닝할 수 있습니다. 이후 $\eta$가 충분히 작다면, 헤비-볼 항이 투영된 역학에 부정적인 영향을 주지 않으면서 이 특정 방향을 따라 수렴을 가속화함을 보여줍니다.

4. 선형 함수 근사(Linear Function Approximation)로의 확장:
   이 프레임워크는 선형 함수 근사(LQL)로 확장됩니다. 특징 공간(feature space)에서 공통 고유벡터 방향(벡터 $c$에 의해 생성되며 $\Phi c = \mathbf{1}$을 만족하는 벡터)의 존재를 보장하기 위해 유사한 보정 행렬 $G$가 구축됩니다. 동일한 SLS 및 JSR 분석을 통해 유사한 수렴 및 가속 결과를 얻습니다.

주요 기여

• 보정된 Q-러닝 (CQL): 비균등 샘플링에 대해 공통 고유벡터 성질을 복원하여 엄격한 스펙트럼 분석을 가능하게 하는 구조적 보정 업데이트 제안.
• 이론적 가속 보증: 헤비-볼 보정된 Q-러닝이 표준 Q-러닝 및 (모멘텀이 없는) 보정된 Q-러닝보다 엄격하게 작은 JSR을 갖는 충분 조건(가정 4.1, 4.2 및 5.1)을 도출함으로써 가속을 입증함. 이는 특정적으로 식별 가능한 방향에 대한 "인증된 속도(certified rate)"를 제공합니다.
• SLS/JSR 프레임워크: Q-러닝에 전환 선형 시스템 및 합동 스펙트럼 반지름 분석을 적용함. 이 접근 방식은 표준적인 정책 평가(policy evaluation)나 확률적 근사(stochastic approximation) 경계만을 사용하는 대신, 그리디 정책의 전환 특성을 명시적으로 다룹니다.
• 함수 근사로의 확장: 보정 및 가속 이론을 선형 함수 근사 설정으로 일반화함.

결과

• 수렴: 제시된 가정 하에서, 오차 재귀가 JSR에 의해 제한되는 속도로 0으로(또는 확률적 상황에서는 노이즈 근방으로) 균일하게 지수적으로 수렴함을 증명합니다.
• 가속: 이론적 분석(정리 5.1 및 10.1)을 통해, 작은 모멘텀 매개변수 $\eta$에 대해 헤비-볼 보정 시스템의 JSR이 표준 또는 보정된 베이스라인보다 엄격히 작음을 보여줍니다.
• 수치적 예시:
  • 결정론적 테이블 설정에서, HBCQL은 CQL보다 상대 오차 임계값에 훨씬 빠르게 도달했습니다.
  • 확률적 테이블 설정에서, HBCQL은 표준 Q-러닝 및 CQL 모두와 비교하여 특정 오차 임계값에 도달하는 중앙 시간을 단축했습니다.
  • 선형 함수 근사 설정(결정론적 및 확률적 모두)에서, 헤비-볼 보정된 선형 Q-러닝(HBCLQL)은 표준 및 보정된 선형 Q-러닝 방법보다 수렴 속도 면에서 일관되게 우수한 성능을 보였습니다.

의의 및 주장
본 논문은 전체 방향에 대한 가속 정리가 아닌, 분석적으로 식별 가능한 하나의 특정 방향(공통 고유벡터 방향)에 대한 정밀한 가속 인증을 제공한다고 주장합니다. 저자들은 본인의 기여가 단순한 정책 평가가 아닌 제어 설정(정책이 변하는 환경)에 초점을 맞추고 있으며, 고정 정책 스펙트럼 분석이나 확률적 근사 경계만을 사용하는 대신 SLS 및 JSR 분석을 사용했다는 점을 강조합니다. 또한, 표준 헤비-볼 Q-러닝이 공통 고유벡터를 결여하는 비균등 샘플링 시나리오에서 분석을 용이하게 하는 구조적 보정을 제공한다는 점을 밝힙니다.

저자들은 가속 보증이 "투영된 간극(projected gap)" 가정(투영된 역학이 공통 방향 역학보다 빠르다는 가정)과 작은 모멘텀 매개변수에 조건부적임을 언급합니다. 이들은 모든 매개변수 선택이나 모든 MDP에 대해 보편적인 가속을 주장하는 것이 아니라, 방법론이 이론적으로 더 빠르다고 보장되는 영역을 식별하는 데 목적을 둡니다. 분석은 주로 결정론적 평균 역학에 대해 수행되었으며, 표준 조건부 평균 논증을 통해 확률적 설정으로 확장되었습니다.