Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

기술적 요약: 포아송-모로 드리프트를 통한 확률적 근사와 강화 학습의 거의 확실한 수렴 속도

문제 제기
본 논문은 마르코프성 잡음 하에서 작동하는 확률적 근사 (SA) 및 강화 학습 (RL) 알고리즘에 대한 거의 확실한 수렴 속도를 확립하는 근본적인 이론적 과제를 다룹니다. 고전적 이론 (예: 상미분방정식 방법) 은 시퀀스 $\{\theta_n\}$이 거의 확실하게 수렴함을 입증하지만, 개별 표본 경로에 대한 이 수렴의 속도를 정량화하는 데는 종종 실패합니다. 기존 거의 확실한 속도에 대한 문헌은 다음과 같은 중대한 한계를 안고 있습니다:

1. 많은 결과들이 독립 동일 분포 (i.i.d.) 잡음에 의존하는데, 이는 RL 에서 흔히 발생하는 단일 궤적 샘플링을 반영하지 못합니다.
2. 마르코프성 잡음을 다루는 결과들은 종종 기대 업데이트가 선형이어야 하거나 제한적인 학습률 체제를 요구합니다.
3. Qian 등 [2024] 의 최근 연구는 일반적 축소 사상을 가진 마르코프성 잡음을 처리하지만 더 느린 수렴 속도를 산출하며 특정 학습률 체제 (특히 $\eta \in (1/2, 2/3]$) 를 다루지 못합니다.

저자들은 기대 업데이트가 축소적 (비유클리드 노름인 $\ell_\infty$와 같은 것일 수 있음) 이고 잡음이 마르코프 체인을 형성하는 SA 알고리즘 클래스에 초점을 맞춥니다. 이 설정은 Q-학습 및 선형 시간차 (TD) 학습과 같은 핵심 RL 알고리즘을 포괄합니다.

방법론: 포아송 - 모로 드리프트
핵심 기술적 새로움은 포아송 - 모로 드리프트라고 명명된 새로운 리아푸노프 드리프트 함수의 구성에 있습니다. 저자들은 두 가지 확립된 기법을 새로운 보정 메커니즘과 결합합니다:

1. 모로 - 엔벨로프 평활화: 비유클리드 노름 $\|\cdot\|$ 하에서 정의될 수 있는 축소 사상 $T$를 처리하기 위해, 저자들은 모로 엔벨로프 $M_\xi$를 활용합니다. 이는 비미분 가능한 노름 기반 에너지 함수를 연속 미분 가능한 함수 $M_\xi(x)$로 평활화하여, 축소 성질을 보존하면서 그래디언트 기반 분석을 가능하게 합니다.
2. 포아송 방정식 보정: 마르코프성 잡음을 처리하기 위해, 저자들은 포아송 방정식에 기반한 보정을 적용합니다. 잡음 항 $F(\theta, Y) - f(\theta)$는 포아송 방정식의 해 $H_\theta$를 사용하여 마팅글 차이와 텔레스코핑 잔여항으로 분해됩니다: $H_\theta(y) - (PH_\theta)(y) = F(\theta, y) - f(\theta)$.
3. 새로운 구성: 전체 기대값을 취하거나 (경로별 통제를 상실함) "스켈레톤 반복" (부분 수열) 을 사용하는 이전 연구들과 달리, 저자들은 포아송 보정을 리아푸노프 함수에 직접 통합합니다. 그들은 다음과 같은 드리프트를 정의합니다:
   $$V_n^\xi = M_\xi(e_n) + \alpha_n \langle \nabla M_\xi(e_n), H_{\theta_n}(Y_n) \rangle + K \alpha_n^2$$
   여기서 $e_n = \theta_n - \theta^*$는 오차, $\alpha_n$은 학습률, $K$는 충분히 큰 상수입니다.
   • 중간 항 (포아송 보정) 은 조건부 드리프트에서 발생하는 마르코프성 의존성의 주요 편향 항을 상쇄합니다.
   • 마지막 항 ($K \alpha_n^2$) 은 드리프트가 음수가 아니도록 보장하고 잔여 항을 제어합니다.

이 구성을 통해 저자들은 $V_n^\xi$가 조건부 기대에 대해 직접 거의 초마팅글 부등식을 만족함을 입증할 수 있게 되었고, 이는 반복 시퀀스 전체 (부분 수열이 아닌) 에 최근 거의 초마팅글 수렴 속도 정리 (Liu and Yuan [2024]) 를 적용할 수 있게 합니다.

주요 결과
축소적 기대 업데이트, 리프시츠 연속성, 마르코프 체인에 대한 포아송 방정식 해의 존재에 대한 가정 하에, 본 논문은 오차 $\|\theta_n - \theta^*\|$에 대한 다음과 같은 거의 확실한 수렴 속도를 유도합니다:

• 멱함수 학습률 $\alpha_n = O(n^{-\eta})$ ($\eta \in (1/2, 1)$):
  오차는 $o(n^{-(2\eta - 1)})$에 임의로 근접하는 속도로 거의 확실하게 수렴합니다.
• 조화 학습률 $\alpha_n = O(n^{-1})$ (즉, $\eta = 1$):
  오차는 $o(n^{-1})$에 임의로 근접하는 속도로 거의 확실하게 수렴합니다.
  • 저자들은 이것이 i.i.d. 잡음에 대한 반복 로그 법칙이 제시하는 최적 속도 $O(n^{-1} \log \log n)$에 근접하는 강력한 결과라고 지적합니다.

기존 연구와의 비교

• Qian 등 [2024] 대비: 제안된 방법은 더 넓은 범위의 학습률 (특히 Qian 등이 속도를 제시하지 않는 $\eta \in (1/2, 2/3]$) 을 포괄하며, $\eta \in (2/3, 1]$에 대해 엄격히 더 빠른 수렴 속도를 달성합니다.
• 기대값 기반 분석 대비: 이 방법은 기대값 또는 확률에서의 수렴이 아닌 경로별 (거의 확실한) 보장을 제공합니다.
• 부수적 결과: 드리프트 부등식의 무조건부 기대값을 취함으로써, 저자들은 전체 범위 $\eta \in (0, 1]$에 대한 $L_2$ 수렴 속도도 유도하여, $\eta < 1$에 대해 $E[\|\theta_n - \theta^*\|^2] = O(n^{-\eta})$임을 보입니다.

응용
이론적 프레임워크는 일반적 중요도 샘플링 인자를 가진 일반화된 표 TD 알고리즘 계열에 적용됩니다. 이 통합 템플릿은 다음을 포함한 여러 표준 알고리즘을 복원합니다:

• 온 - 정책 및 오프 - 정책 $n$-step TD.
• $Q^\pi(\lambda)$, Tree-Backup, Retrace, 및 Q-trace.

이러한 알고리즘에 대해 본 논문은 구조적 조건 (평균 연산자에 대한 후위츠 행렬, 유한 상태 체인에 대한 포아송 해의 존재) 이 성립함을 검증함으로써, 마르코프성 샘플링 하에서 이러한 일반화된 TD 재귀의 단일 궤적 버전에 대한 최초의 경로별 거의 확실한 수렴 속도를 확립합니다.

의의 및 주장
본 논문은 마르코프성 잡음 및 비유클리드 축소성 하의 일반적 확률적 근사에 대해 더 정교한 거의 확실한 수렴 속도를 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

1. 기술적 새로움: "포아송 - 모로 드리프트"는 단일 거의 초마팅글 프레임워크 내에서 비유클리드 축소 (모로 엔벨로프를 통해) 와 마르코프성 잡음 (포아송 보정을 통해) 을 처리하는 간극을 성공적으로 연결하는 새로운 구성으로 제시됩니다.
2. tightness (밀착성): 유도된 조화 학습률 ($\eta=1$) 에 대한 속도는 이론적 최적에 근접하며, RL 문헌의 기존 결과를 능가하는 것으로 주장됩니다.
3. 완전성: 이 작업은 현대 RL 알고리즘의 특징인 마르코프성 잡음과 일반적 (비선형, 비유클리드) 축소 사상의 특정 조합을 다루어 문헌의 공백을 메웁니다.

저자들은 속도의 tightness 에 관해 겸손하게 언급하며, 기존 문헌보다 결과가 더 정교하지만 반복 로그 법칙의 $O(n^{-1} \log \log n)$ 경계와 아직 완전히 일치하지는 않는다고 인정합니다. 또한 현재 $L_2$에 대해 증명된 거의 확실한 속도를 전체 범위 $\eta \in (0, 1]$로 확장하는 것은 여전히 열린 질문이라고 지적합니다.