2025-11-10T02:47:02.164832

Central Limit Theorems for Asynchronous Averaged Q-Learning

Liu
This paper establishes central limit theorems for Polyak-Ruppert averaged Q-learning under asynchronous updates. We prove a non-asymptotic central limit theorem, where the convergence rate in Wasserstein distance explicitly reflects the dependence on the number of iterations, state-action space size, the discount factor, and the quality of exploration. In addition, we derive a functional central limit theorem, showing that the partial-sum process converges weakly to a Brownian motion.
academic

비동기 평균화 Q-러닝의 중심극한정리

기본 정보

  • 논문ID: 2509.18964
  • 제목: Central Limit Theorems for Asynchronous Averaged Q-Learning
  • 저자: Xingtu Liu (Simon Fraser University)
  • 분류: cs.LG math.OC stat.ML
  • 발표 학회: OPT2025: 17th Annual Workshop on Optimization for Machine Learning
  • 논문 링크: https://arxiv.org/abs/2509.18964

초록

본 논문은 비동기 업데이트 하에서 Polyak-Ruppert 평균화 Q-러닝에 대한 중심극한정리를 수립한다. 본 논문은 Wasserstein 거리에서의 수렴률이 반복 횟수, 상태-동작 공간 크기, 할인 인자 및 탐색 품질에 대한 의존성을 명시적으로 반영하는 비점근 중심극한정리를 증명한다. 또한 부분합 과정이 브라운 운동으로 약수렴함을 보이는 함수 중심극한정리를 도출한다.

연구 배경 및 동기

문제 배경

  1. Q-러닝의 중요성: Q-러닝은 강화학습에서 가장 널리 사용되는 알고리즘 중 하나로, 경험적 궤적으로부터 최적 동작 가치 함수를 직접 학습하며, Atari 게임, 바둑, 로봇 조작 및 대규모 언어 모델 정렬 등의 분야에서 큰 성공을 거두었다.
  2. 이론적 분석의 도전:
    • Q-러닝은 확률적 근사(SA)의 사례로 해석될 수 있으나, 비동기 Q-러닝은 마르코프 잡음을 가진 비선형 SA 문제이다
    • 선형 SA 및 TD 러닝과 비교하여 Q-러닝의 분석은 비선형성, 비매끄러운 연산자 및 비정상 과정의 특성으로 인해 더욱 도전적이다
    • 비동기 업데이트는 마르코프 잡음을 추가로 도입하여 분석 복잡도를 증가시킨다
  3. 기존 연구의 한계:
    • 기존 연구는 동기식 Q-러닝의 함수 CLT를 수립했으나, 동기식 Q-러닝은 마팅게일 잡음만 고려한다
    • Zhang과 Xie (2024)는 상수 스텝 크기의 비동기 Q-러닝에 대한 함수 CLT를 수립했으나, 상수 스텝 크기는 비점근 CLT 수립에 필요한 조건을 만족하지 않는다
    • 현재까지 동기식 설정에서도 Q-러닝의 비점근 CLT가 존재하지 않는다

연구 동기

중심극한정리 수립은 알고리즘의 통계적 성질을 이해하는 데 필수적이며, 이러한 점근 정규성은 강화학습에서의 불확실성 정량화 및 통계적 추론에 중요한 의미를 갖는다.

핵심 기여

  1. Q-러닝의 첫 번째 비점근 CLT: 비동기 평균화 Q-러닝의 비점근 중심극한정리를 증명하며, 수렴률은 O~((∣S∣∣A∣)1/2K−1/6ρ−2(1−γ)−3)\tilde{O}((|S||A|)^{1/2}K^{-1/6}\rho^{-2}(1-\gamma)^{-3})이다
  2. 함수 중심극한정리: 감소 스텝 크기 하에서 비동기 Q-러닝의 함수 CLT를 수립하여 부분합 과정이 브라운 운동으로 약수렴함을 보인다
  3. 명시적 의존성: 수렴률이 반복 횟수 K, 상태-동작 공간 크기 |S||A|, 할인 인자 γ 및 탐색 품질 ρ에 대한 의존성을 명시적으로 반영한다
  4. 기술적 혁신: 비선형성, 마르코프 잡음 및 비매끄러운 연산자로 인한 분석 도전을 해결한다

방법론 상세 설명

문제 정의

무한 지평 할인 마르코프 결정 과정(MDP) M=⟨S,A,P,r,γ⟩M = \langle S, A, P, r, \gamma \rangle을 고려하며, 여기서:

  • SS: 상태 집합
  • AA: 동작 집합
  • P:S×A→ΔSP: S \times A \rightarrow \Delta_S: 전이 확률 함수
  • γ∈[0,1)\gamma \in [0,1): 할인 인자

목표는 최적 Q 함수 Q∗=max⁡πQπQ^* = \max_\pi Q^\pi를 학습하는 것이다.

비동기 Q-러닝 알고리즘

비동기 Q-러닝은 Q 함수 추정기 QkQ_k를 유지하며, 업데이트 규칙은 다음과 같다: Qk+1=Qk+αk(Fk−Qk)Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)

여기서:

  • Fk=F(Qk,yk)F_k = F(Q_k, y_k), yk=(sk,ak,sk+1)y_k = (s_k, a_k, s_{k+1})
  • [F(Qk,sk,ak,sk+1)](s,a)=1{(sk,ak)=(s,a)}Γ(Qk,sk,ak,sk+1)+Qk(s,a)[F(Q_k, s_k, a_k, s_{k+1})](s,a) = \mathbf{1}_{\{(s_k,a_k)=(s,a)\}}\Gamma(Q_k, s_k, a_k, s_{k+1}) + Q_k(s,a)
  • Γ(Qk,sk,ak,sk+1)=rk(sk,ak)+γmax⁡aQk(sk+1,a)−Qk(sk,ak)\Gamma(Q_k, s_k, a_k, s_{k+1}) = r_k(s_k, a_k) + \gamma\max_a Q_k(s_{k+1}, a) - Q_k(s_k, a_k)

핵심 가정

가정 1: 최적 정책 π∗\pi^*이 존재하여 모든 Q∈R∣S∣×∣A∣Q \in \mathbb{R}^{|S|\times|A|}에 대해: ∥(Pπ−Pπ∗)(Q−Q∗)∥∞≤L∥Q−Q∗∥2∞\|(P^\pi - P^{\pi^*})(Q-Q^*)\|_\infty \leq L\|Q-Q^*\|_2^\infty

가정 2: {yk}k≥0\{y_k\}_{k \geq 0}는 기약이고 비주기적인 유한 상태 마르코프 연쇄이다.

스텝 크기 선택

다항식 스텝 크기 αk=α(k+b)−β\alpha_k = \alpha(k+b)^{-\beta}를 선택하며, 여기서 α,b>0\alpha, b > 0, β∈(0.5,1)\beta \in (0.5, 1)이다.

이러한 선택의 이유:

  1. Polyak-Juditsky 평균화 방식의 핵심 조건을 만족한다
  2. 상수 스텝 크기는 조건 (i)과 (iii)을 위반하고, 선형 스텝 크기는 조건 (ii)를 위반한다
  3. 다항식 스텝 크기는 모든 필요 조건을 만족한다

주요 이론적 결과

비점근 중심극한정리

정리 4: 가정 1과 2 하에서: W1(K−1/2∑k=1KΔk,N~)≤(∣S∣∣A∣)1/2ρ(1−γ)2K1/2⋅O~((ρ(1−γ))β−21−β+Kβ/2ρ−1(1−γ)−1+K1−β+K1−β2ρ−1−β(1−γ)−β)W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, \tilde{N}\right) \leq \frac{(|S||A|)^{1/2}}{\rho(1-\gamma)^2K^{1/2}} \cdot \tilde{O}\left((\rho(1-\gamma))^{\frac{\beta-2}{1-\beta}} + K^{\beta/2}\rho^{-1}(1-\gamma)^{-1} + K^{1-\beta} + K^{\frac{1-\beta}{2}}\rho^{-1-\beta}(1-\gamma)^{-\beta}\right)

여기서 Δk=Qk−Q∗\Delta_k = Q_k - Q^*, N~=(A−1ΣA−⊤)1/2N(0,I)\tilde{N} = (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)이다.

따름정리 5: β=2/3\beta = 2/3일 때, 수렴률은 다음과 같이 단순화된다: W1(K−1/2∑k=1KΔk,(A−1ΣA−⊤)1/2N(0,I))≤O~((∣S∣∣A∣)1/2K1/6ρ2(1−γ)3)W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)\right) \leq \tilde{O}\left(\frac{(|S||A|)^{1/2}}{K^{1/6}\rho^2(1-\gamma)^3}\right)

함수 중심극한정리

정리 6: 정리 4의 설정 하에서, 부분합 과정 ΦK(ζ)=K−1/2∑k=1⌊ζK⌋Δk\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k는 D[0,1]D[0,1]에서 (A−1ΣA−⊤)1/2B(⋅)(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot)로 약수렴하며, 여기서 B(⋅)B(\cdot)는 표준 브라운 운동이다.

기술적 혁신 및 증명 전략

주요 기술적 도전

  1. 비선형성: Q-러닝은 비선형 SA로서 선형 SA보다 복잡하다
  2. 마르코프 잡음: 비동기 업데이트는 독립동일분포가 아닌 마르코프 잡음을 도입한다
  3. 비매끄러운 연산자: 비동기 Q-러닝의 경험적 Bellman 연산자는 비매끄럽다

증명 전략

  1. 상하한 기법: 상한 수열 Δk↑\Delta_k^{\uparrow}과 하한 수열 Δk↓\Delta_k^{\downarrow}를 도입하여 조임 정리를 활용한다
  2. 항 분해: ∑k=1KΔk\sum_{k=1}^K \Delta_k를 6개 항으로 분해한다:
    • 항 (1): 초기 오차 항
    • 항 (2): 비선형 오차 항
    • 항 (3): 마르코프 잡음 항
    • 항 (4-5): 고차 수정 항
    • 항 (6): 마팅게일 차분 수열
  3. Poisson 방정식 기법: 마르코프 잡음을 마팅게일 차분 수열로 변환한다
  4. 마팅게일 중심극한정리: Srikant (2024)의 비점근 마팅게일 CLT를 적용한다

관련 연구

확률적 근사 이론

  • Polyak, Juditsky (1992): 고전적인 평균화 분산 감소 기법
  • Anastasiou 등 (2019): Polyak-Ruppert 평균화 SGD의 비점근 CLT
  • Mou 등 (2020): 선형 SA의 비점근 CLT

강화학습의 CLT

  • Xie, Zhang (2022), Li 등 (2023): 동기식 Q-러닝의 함수 CLT
  • Zhang, Xie (2024): 상수 스텝 크기 비동기 Q-러닝의 함수 CLT
  • Srikant (2024), Samsonov 등 (2024): TD 러닝의 비점근 CLT

결론 및 논의

주요 결론

  1. Q-러닝의 첫 번째 비점근 CLT를 수립하며, 수렴률은 문제 매개변수에 명시적으로 의존한다
  2. 비동기 Q-러닝 부분합 과정의 약수렴성을 증명한다
  3. 강화학습에서의 불확실성 정량화를 위한 이론적 기초를 제공한다

한계

  1. 강한 Lipschitz 가정(가정 1)이 필요하다
  2. 유한 상태-동작 공간만 고려한다
  3. 수렴률이 최적이 아닐 수 있다

향후 방향

  1. 수렴률 개선
  2. 1-Wasserstein 거리 이외의 다른 메트릭으로 확장
  3. 함수 근사 설정 고려

심층 평가

장점

  1. 중대한 이론적 기여: Q-러닝의 비점근 CLT를 최초로 수립하여 중요한 이론적 공백을 메운다
  2. 기술적 혁신: 상하한 기법, Poisson 방정식 및 마팅게일 CLT를 교묘하게 결합하여 기술적 어려움을 해결한다
  3. 완전한 결과: 비점근 및 함수 CLT를 동시에 제시한다
  4. 명시적 의존성: 수렴률이 각 매개변수의 영향을 명시적으로 반영한다

부족한 점

  1. 강한 가정: Lipschitz 가정은 실제로 검증하기 어려울 수 있다
  2. 수렴률: K−1/6K^{-1/6}의 수렴률은 상대적으로 느리다
  3. 유한 상태: 연속 상태 공간 또는 함수 근사를 고려하지 않는다

영향력

  1. 이론적 가치: Q-러닝 이론 분석에 새로운 도구와 관점을 제공한다
  2. 실용적 의의: 강화학습 알고리즘의 불확실성 정량화를 위한 이론적 기초를 마련한다
  3. 방법론: 증명 기법은 다른 비선형 SA 문제로 일반화될 수 있다

적용 시나리오

  1. 표 형식 강화학습 문제의 이론적 분석
  2. 비동기 업데이트 알고리즘의 수렴성 연구
  3. 강화학습에서의 통계적 추론 및 신뢰 구간 구성

참고문헌

  • Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging.
  • Xie, C. and Zhang, Z. (2022). A statistical online inference approach in averaged stochastic approximation.
  • Zhang, Y. and Xie, Q. (2024). Constant stepsize q-learning: Distributional convergence, bias and extrapolation.