최소한의 가정 하에 Single-Loop Actor-Critic에 대한 $\epsilon^{-2}$ 샘플 복잡도 달성

본 논문에서 우리는 강화학습 (Reinforcement Learning) 분야의 오프-폴리시 (off-policy) Actor-Critic 방법론에 대한 마지막 반복 (last-iterate) 수렴 속도를 확립합니다. 특히, 단일 루프 (single-loop), 단일 타임스케일 (single-timescale) 구현 및 근사 정책 반복 (approximate policy iteration)과 자연 정책 경사 (natural policy gradient) 방법을 포함한 광범위한 정책 업데이트 클래스 하에서, 우리는 최소한의 가정, 즉 기약 마르코프 체인 (irreducible Markov chain)을 유도하는 정책의 존재성 하에 $\epsilon$-최적 정책 ($\epsilon$-optimal policy)을 찾기 위한 최초의 $\tilde{\mathcal{O}}(\epsilon^{-2})$ 샘플 복잡도 (sample complexity) 보증을 증명합니다. 이는 $\tilde{\mathcal{O}}(\epsilon^{-2})$ 샘플 복잡도가 중첩 루프 (nested-loop) 업데이트를 통해서만 달성되거나, 균일 혼합 (uniform mixing) 및 균일 탐색 (uniform exploration)과 같이 정책에 대한 알고리즘 의존적인 강력한 가정 하에서만 달성되었던 기존 문헌들과 극명한 대조를 이룹니다. 기술적으로, 단일 루프 구현으로 인해 발생하는 결합된 업데이트 방정식 (coupled update equations)의 난제와 오프-폴리시 학습으로 인해 유도될 수 있는 무제한 반복 (unbounded iterates) 문제를 해결하기 위해, 우리의 분석은 결합된 리아푸노프 드리프트 (coupled Lyapunov drift) 프레임워크를 기반으로 합니다. 구체적으로, 우리는 Actor에 대한 기하학적 수렴 속도 (geometric convergence rate)와 Critic에 대한 $\tilde{\mathcal{O}}(1/T)$ 수렴 속도를 확립하고, 교차 지배 (cross-domination) 성질을 통해 두 리아푸노프 드리프트 부등식을 결합합니다. 우리는 이 분석적 프레임워크가 독립적인 관심 대상이며, 무제한적인 다른 결합된 반복 알고리즘 (coupled iterative algorithms)에도 적용될 수 있을 것이라 믿습니다.