비동기 Q-러닝의 도달 시간 경계

원문 발행 2026. 10. 10. 02:44원문 언어 영어AI 한국어 번역arXiv cs.LG (Machine Learning) 원문 보기

요약

본 논문은 유한 마르코프 결정 과정(MDP)의 단일 궤적을 사용하여 비동기 Q-러닝의 수렴 속도를 분석했습니다. 상수 스텝 크기를 가진 Q-러닝이 높은 확률로 sup-norm 오차를 $\varepsilon$ 이하로 달성하는 데 필요한 전이 횟수를 구체적으로 증명합니다. 이 연구는 통계적 오차와 고정 정책 초기화 오차를 분리하여 분석한 것이 특징입니다.

핵심 포인트

비동기 Q-러닝의 수렴 속도를 이론적으로 분석함.
필요한 전이 횟수를 $\widetilde{O}(H^4/(\mu_{\min}\varepsilon^2)+\mathfrak h_\star)$로 증명함.
통계적 오차와 초기화 오차를 분리하여 분석하는 방법론을 제시함.
탐험 하한은 임의의 예측 가능한 스텝 크기에 대해 성립함을 보임.

우리는 유한 마르코프 결정 과정(finite Markov decision process)의 단일 궤적으로부터 표준 비동기 Q-러닝(asynchronous Q-learning)의 마지막 반복값(last iterate)을 연구합니다. 이 궤적은 고정된 행동 정책(fixed behavior policy)을 따르며, 그 상태--행동 체인(state--action chain)은 비축소성(irreducible)이고 주기적일 수 있습니다. 할인 계수 $\gamma$에 대해 $H=(1-\gamma)^{-1}$로 정의하고, $\mu_{\min}$을 최소 정상 상태--행동 확률(minimum stationary state--action probability)로, $\mathfrak h_\star$를 역 상태--행동 체인의 최대 기대 도달 시간(largest expected hitting time)으로 둡니다. 우리는 상수 스텝 크기(constant step size)를 가진 영 초기화된 Q-러닝이 $0 < \varepsilon \le 1$에 대해 $\widetilde{O}(H^4/(\mu_{\min}\varepsilon^2)+\mathfrak h_\star)$ 개의 전이(transitions)를 사용하여 높은 확률로 sup-norm 오차를 최대 $\varepsilon$ 이하로 달성함을 증명합니다. 통계적 항은 표준 Q-러닝의 사차 효과 지평 의존성을 유지하는 반면, 초기화 비용은 $\mathfrak h_\star$에 가산적으로 포함됩니다. 비주기적인 행동 체인의 경우, 혼합 시간(mixing time)과의 비교를 통해 $\widetilde{O}(t_{\mathrm{mix}}/\mu_{\min})$의 과도 항(transient term)을 얻습니다. 경험적 상태--행동 카운트 규칙(empirical state--action count rule)은 후속 훈련 실행에 대한 상수 스텝 크기를 선택하고, 모델 매개변수, 목표 정확도 또는 신뢰 수준에 대한 사전 지식 없이 동일한 비율을 달성합니다. 출력값은 마지막 훈련 반복값이며, 두 단계 모두 샘플 수 계산에 포함됩니다. 이 증명은 통계적 오차와 고정 정책 초기화 오차를 분리하기 위해 두 개의 결정론적 벨만 포락선(deterministic Bellman envelopes)을 사용하고, TD 학습에서 상태--행동 전파로 역시간 도달 비용 보상(reverse-time hitting-cost compensation)을 적용합니다. 탐험 하한(exploration lower bound)은 임의의 예측 가능한 스텝 크기(arbitrary predictable step sizes)에 대해 성립합니다. 이는 기존의 통계적 하한 및 이를 파일럿 선택된 상수 스텝으로 확장한 것과 결합하여, 명시된 대규모 샘플 매개변수 클래스에서 로그 인자까지 일치하는 평균 제곱 비율을 제공합니다.

AI 자동 생성 콘텐츠

원문 바로가기

비동기 Q-러닝의 도달 시간 경계

요약

핵심 포인트

댓글