확률적 반복 알고리즘의 비점근적 수렴: Lyapunov 프레임워크

우리는 연산자 $\bar{F}(\cdot)$에 노이즈가 섞인 오라클 (noisy oracle)을 통해서만 접근할 수 있는 고정점 방정식 $\bar{F}(x)=x$를 풀기 위한 확률적 반복 알고리즘(stochastic iterative algorithms), 즉 확률적 근사 (stochastic approximation, SA) 알고리즘의 유한 시간 분석 (finite-time analysis)을 위한 Lyapunov 기반 기술들을 조사합니다. 먼저 $\bar{F}(\cdot)$가 특정 노름 (norm)에 대해 수축적 (contractive)이고 노이즈가 독립 항등 분포 (i.i.d.)인 표준 설정에 집중하며, 일반화된 모로 포락선 (generalized Moreau envelopes)이 기저 노름에 관계없이 어떻게 보편적인 Lyapunov 함수 역할을 하는지 설명합니다. 이어서 이 프레임워크가 어떻게 평균 제곱 수렴 (mean-square convergence) 보장을 제공하는지 보여주고, 확률적 경사 하강법 (stochastic gradient descent), 선형 SA, 그리고 Q-learning 및 시간차 학습 (temporal-difference learning)과 같은 가치 기반 강화학습 (value-based reinforcement learning) 알고리즘에 어떻게 적용되는지 보여줍니다. 마지막으로 마르코프 노이즈 (Markovian noise), 준노름 수축 연산자 (seminorm-contractive operators), 소산 연산자 (dissipative operators), 그리고 고확률 경계 (high-probability bounds)로의 확장을 논의하고 미해결 문제들과 함께 결론을 맺습니다. 본 연구의 목표는 SA 및 그 응용 분야, 특히 강화학습에서의 유한 시간 분석을 위한 통합적이고 자기 완결적인 로드맵을 제시하는 것입니다.