Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

기술 요약: 최소 가정 하에서 단일 루프 액터-크리틱을 위한 $\tilde{O}(\epsilon^{-2})$ 샘플 복잡도 달성

문제 제기
강화 학습 (RL) 은 데이터 기반 방법을 통해 마르코프 결정 과정 (MDP) 을 해결하는 것을 목표로 합니다. Q-러닝과 같은 가치 공간 (value-space) 방법들은 최소 가정 (구체적으로, 비가약적 행동 정책의 존재) 하에서 $\tilde{O}(\epsilon^{-2})$의 샘플 복잡도를 입증해 온 반면, 액터-크리틱과 같은 정책 공간 (policy-space) 방법들은 역사적으로 이론적 보장에서 뒤처져 왔습니다. $\tilde{O}(\epsilon^{-2})$ 복잡도를 달성하는 기존 액터-크리틱 분석들은 일반적으로 두 가지 제한적인 조건에 의존합니다:

1. 중첩 루프 (Nested-loop) 구현: 액터가 고정된 상태에서 크리틱이 여러 번 업데이트되는 구조로, 이는 실제적인 단일 루프 알고리즘과 구별됩니다.
2. 강력하고 알고리즘에 종속적인 가정: 알고리즘의 궤적 동안 마주치는 모든 정책 (또는 전체 정책 클래스) 이 균일하게 유계된 혼합 속도와 탐색 속성을 갖는 비가약적이고 비주기적인 마르코프 체인을 유도해야 한다는 요구사항과 같은 가정들입니다.

이러한 가정들은 순환적 의존성을 만들어냅니다: 혼합 속성을 검증하려면 알고리즘이 생성한 정책 시퀀스를 제어해야 하는데, 이는 바로 수렴 분석의 대상이기 때문입니다. 또한, 실제 액터-크리틱 알고리즘들은 오프-정책 학습을 수행하며 시간이 지남에 따라 변하는 목표 정책을 추적하는 단일 루프, 단일 시간 척도 방식으로 작동합니다. 이는 결합된 업데이트 방정식과 중요도 샘플링으로 인해 발생할 수 있는 무계 반복자 (unbounded iterates) 에 대한 도전을 야기하며, 기존 이론적 프레임워크들은 강력한 가정 없이는 이를 해결하는 데 어려움을 겪습니다.

방법론
저자들은 액터와 크리틱이 각 반복에서 동시에 업데이트되는 단일 루프, 단일 시간 척도 오프-정책 액터-크리틱 알고리즘을 제안합니다. 액터는 근사 정책 반복 (API) 또는 자연 정책 경사 (NPG) 를 통해 유도된 목표 정책 $\tilde{\pi}_t$를 향해 점진적 업데이트를 수행하는 반면, 크리틱은 오프-정책 시간차 (TD) 학습을 수행합니다. 저자들은 두 가지 크리틱 변형을 고려합니다:

• 중요도 샘플링 (IS): 중요도 가중치 비율을 사용하여 분포 불일치를 보정합니다.
• 기대 시간차 (ETD): 명시적인 중요도 가중치를 피하고 다음 상태에서의 기대 Q-함수를 직접 계산합니다.

핵심 기술적 혁신은 분석 프레임워크에 있습니다. 액터와 크리틱 업데이트 간의 결합과 오프-정책 반복자의 무계 특성을 처리하기 위해, 저자들은 결합된 리아푸노프 드리프트 (coupled Lyapunov drift) 프레임워크를 사용합니다.

1. 리아푸노프 함수: 그들은 액터 ($V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$) 와 크리틱 ($W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$) 에 대해 별도의 리아푸노프 함수를 구성합니다.
2. 드리프트 부등식: 그들은 두 함수 모두에 대해 음의 드리프트 부등식을 수립합니다. 핵심적으로, 이러한 부등식들은 결합된 시스템의 오차를 나타내는 교차항 (예: 액터의 드리프트에 나타나는 크리틱 오차 및 그 반대) 을 포함합니다.
3. 교차 우세 (Cross-Domination): 분석은 "교차 우세" 속성에 의존합니다. 단계 크기 비율을 신중하게 선택하고 결합 오차 항이 각 시스템의 음의 드리프트 항에 의해 지배되도록 보장함으로써, 저자들은 $V_t + W_t$에 대한 단일 재귀식으로 두 드리프트 부등식을 결합합니다. 이 접근법은 동역학 시스템의 작은 이득 (small-gain) 이론에서 영감을 받았지만, 여기서는 마르코프성 잡음, 시간 가변적 목표, 그리고 무계 반복자를 통합적으로 처리하도록 적응되었습니다.

주요 기여 및 결과
본 논문은 최소 가정 하에서 $\tilde{O}(\epsilon^{-2})$ 샘플 복잡도를 달성하는 단일 루프 액터-크리틱 알고리즘에 대한 최초의 마지막 반복 수렴 (last-iterate convergence) 속도를 확립합니다.

• 최소 가정: 요구되는 유일한 가정은 상태 공간 전체에서 비가약적 마르코프 체인을 유도하는 정책의 존재입니다. 이 정책은 알고리즘에 의해 방문될 필요가 없으며, 알고리즘이 생성하는 정책들의 혼합 속성을 제어할 필요도 없습니다. 이는 궤적 전체나 전체 정책 클래스에 걸친 균일한 에르고딕성을 요구하는 이전 연구들과 대조적입니다.
• 샘플 복잡도: 이러한 최소 가정 하에서, 알고리즘은 $\epsilon$-최적 정책을 찾기 위해 $\tilde{O}(\epsilon^{-2})$의 샘플 복잡도를 달성합니다. 이 속도는 $\epsilon$에 대해 거의 최소 - 최대 (near-minimax) 최적입니다.
• 단계 크기 체계: 결과는 상수, 조화, 다항식 단계 크기 시퀀스에 대해 성립합니다. 구체적으로, 적절한 매개변수를 가진 조화 단계 크기를 사용하면 최적 속도를 얻습니다.
• 알고리즘 변형: 분석은 IS 기반과 ETD 기반 크리틱 모두를 다룹니다. 두 변형 모두 동일한 복잡도 순서를 달성하지만, ETD 변형은 중요도 샘플링 비율로 인해 발생하는 추가적인 확률적 요소를 피하기 때문에 문제 매개변수 (상태 공간 크기 $n$, 행동 공간 크기 $m$, 할인 인자 $\gamma$) 에 대한 의존도가 더 완만합니다.
• 무계 반복자: 이 프레임워크는 오프-정책 학습 (특히 IS 의 경우) 으로 인해 발생할 수 있는 무계 반복자를 성공적으로 처리하며, 이는 이전 문헌에서 종종 강력한 유계성 가정을 필요로 했던 도전 과제입니다.

의의 및 주장
저자들은 이 작업이 가치 공간 방법과 정책 공간 방법 사이의 중요한 이론적 격차를 메웠다고 주장합니다. 중첩 루프나 강력한 알고리즘 종속적 혼합 가정 없이도 액터-크리틱 방법이 최소 - 최대 최적의 샘플 복잡도를 달성할 수 있음을 입증함으로써, 이 논문은 정책 공간 방법들이 본질적으로 샘플 효율성이 낮거나 더 강력한 조건을 필요로 한다는 개념에 도전합니다.

결합된 리아푸노프 드리프트와 교차 우세에 기반한 분석 프레임워크는 독립적인 관심사로 제시되며, 무계 반복자를 가진 다른 결합 반복 알고리즘에도 적용 가능할 수 있습니다. 논문은 명시적으로 $\epsilon$에 대한 의존도는 거의 최적이지만, 문제별 상수 ($n, m, (1-\gamma)^{-1}$) 에 대한 의존도는 가치 기반 방법과 비교하여 최적이지 않을 수 있음을 지적하며, 분산 감소 기법이 향후 개선 방향이 될 수 있음을 시사합니다. 이 작업은 함수 근사 설정 ("치명적인 삼중주") 이나 구체적인 경험적 응용에 대한 주장을 피하고, 엄격하게 표 (tabular) 설정과 이론적 보장에 초점을 맞춥니다.