Q-Learning의 부호 분리 유한 시간 오차 분석

본 논문은 일정한 스텝 크기(constant step-size)를 사용하는 Q-learning에 대해 부호 분리 유한 시간 오차 분석(sign-separated finite-time error analysis)을 전개합니다. 스위칭 시스템(switching-system) 표현법으로부터 시작하여, 오차를 구성 요소별 음수 부분과 양수 부분으로 분해합니다. 음수 부분은 고정된 최적 정책(optimal policy)과 관련된 하한 비교 선형 시불변(LTI, linear time-invariant) 시스템에 의해 지배되는 반면, 양수 부분은 선형 스위칭 시스템(linear switching system)에 의해 제어됩니다. 결과적인 경계값(bounds)은 음수 측 LTI 인증(certificate)이 양수 측 스위칭 인증보다 느리지 않으며, 더 빠른 지수 포락선(exponential envelope)을 생성할 수 있음을 보여줍니다. 이 분석은 Q-learning 오차 역학(error dynamics)에서 max에 의해 유도된 비대칭성(max-induced asymmetry)을 식별합니다. 이러한 비대칭성은 과대평가(overestimation)와 연결됩니다. 즉, 액션별 양수 오차는 Bellman maximum에 의해 선택되고 전파될 수 있는 반면, 음수 오차는 최적 정책 하한 비교(optimal-policy lower comparison)를 허용합니다. 결정론적(deterministic) 및 확률적(stochastic) 일정한 스텝 크기 재귀(constant-step-size recursions) 모두에 대해 유한 시간 경계값(finite-time bounds)이 제공됩니다.