📊 statistics

A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

이 논문은 비투영 TD(0) 학습이 선형 함수 근사를 사용할 때, 유계된 반복값이나 추가적인 정규성 조건에 의존하는 대신 업데이트의 새로운 자기 제한적(self-bounding) 성질에 의존하여 마르코프 노이즈 하에서 강건한 $\widetilde{\mathcal{O}}(1/\sqrt{T})$ 수렴율을 달성함을 증명함으로써 미해결 문제를 해결한다.

원저자: Wei-Cheng Lee, Francesco Orabona

게시일 2026-06-09

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Wei-Cheng Lee, Francesco Orabona

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

큰 그림: 안전망 없이 배우기

비디오 게임을 배우거나 미로를 통과하는 법을 익히는 것처럼, 시행착오를 통해 새로운 기술을 배우려고 노력한다고 상상해 보세요. 인공지능의 세계에서는 이를 **강화 학습(Reinforcement Learning)**이라고 부릅니다. 이를 위한 가장 인기 있는 도구 중 하나가 바로 **TD 학습(TD Learning)**입니다.

TD 학습을 노트를 적는 학생에 비유해 봅시다. 학생은 매 동작을 할 때마다 자신이 예상했던 결과와 실제로 일어난 결과를 비교합니다. 그리고 다음번에는 더 정확하게 예측할 수 있도록 자신의 노트(즉, "모델")를 수정합니다.

오랫동안 수학자들은 이 학생이 결국 게임을 완벽하게 배울 수 있다는 사실을 알고 있었습니다. 하지만 이 것을 증명하는 데 사용된 수학에는 큰 문제가 하나 있었습니다.

"안전망" 문제: 학생이 미쳐서 불가능한 숫자를 적어 내려가지 않도록 증명하기 위해, 기존 이론들은 "안전망"을 필요로 했습니다. 이는 학생의 노트가 특정 범위 안에 머물도록 강제되어야 한다는 수학적 가정을 의미했습니다. 만약 노트의 숫자가 너무 커지려고 하면, 수학적으로 그 숫자를 잘라내어 다시 박스 안으로 밀어 넣어야 했습니다.
현실 세계의 문제: 현실에서 아무도 이런 "안전망"을 사용하지 않습니다. 우리는 그저 학생이 자연스럽게 배우도록 내버려 둡니다.
열린 질문: 수년간 연구자들은 이렇게 물었습니다. "우리가 아주 엄격한 추가 규칙을 더하지 않고도, 학생이 제대로 배우고 제정신을 유지할 수 있다는 것을 증명할 수 있을까?" 이전의 시도들은 "게임의 구조에 대해 매우 엄격한 규칙을 추가하지 않는 한, 불가능하다"라고 답했습니다.

이 논문은 이렇게 말합니다: "네, 가능합니다."

저자들은 학생(알고리즘)이 별도의 안전망이나 추가적인 엄격한 규칙 없이도 자연스럽게 안전한 범위 내에 머무른다는 것을 보여줍니다. 또한, 데이터가 지저지고 서로 연결되어 있을 때(예: 한 동작이 다음 동작에 영향을 주는 실제 게임처럼)도 이 방법이 최선의 방법들과 거의 비슷한 속도로 학습된다는 것을 증명했습니다.

핵심 개념 설명

1. "안전망" (투영, Projection)

기존 수학에서는 알고리즘이 폭주하지 않는다는 것을 증명하기 위해, 숫자가 너무 커지면 물리적으로 값을 깎아내는 것처럼 가정해야 했습니다.

비유: 등산객이 골짜기 바닥을 찾아가는 상황을 상상해 보세요. 기존 수학은 "우리는 등산객이 절벽 아래로 떨어지지 않을 것이라고 증명할 수 있다. 단, 우리가 마법의 울타리를 만들어 그들이 가장자리로 걸어 나가지 못하게 막는다고 가정한다면"이라고 말하는 것과 같습니다.
이 논문의 돌파구: 저자들은 등산객이 마법의 울타리 없이도 걷는 방식 덕분에 자연스럽게 경로를 유지한다는 것을 증명했습니다.

2. "곡률(Curvature)"의 함정

다른 방법들은 안전망을 피하기 위해, 그들이 걷고 있는 골짜기가 매우 가파르고 그릇 모양(수학적으로 "강한 볼록성(strongly convex)"이라 불림)이라고 가정했습니다.

비유: 만약 골짜기가 완벽하고 가파른 그릇 모양이라면, 바닥으로 굴러 내려가는 것을 증명하기 쉽습니다. 하지만 만약 지형이 평평하거나 이상한 굴곡이 있다면 어떨까요?
문제점: 지형이 평평할 때(실제 데이터에서 자주 발생함), 이러한 "가파른 그릇" 기반의 방법들은 믿을 수 없을 정도로 느려지거나 무용지물이 됩니다.
이 논문의 해결책: 이들의 방법은 지형이 가파른 그릇이든 평평한 평지든 상관없이 작동합니다. 즉, 지형의 특정 모양에 의존하지 않는 "강건함(robustness)"을 갖추고 있습니다.

3. "자기 경계(Self-Bounding)"의 마법

안전망 없이 어떻게 숫자가 폭주하지 않는다는 것을 증명했을까요? 그들은 학습 과정에 숨겨진 성질인 **자기 경계(self-bounding)**를 발견했습니다.

비유: 고무줄을 상상해 보세요. 만약 학생의 노트가 진실로부터 너무 멀리 떨어지면, "학습하는 힘"이 자연스럽게 그것을 다시 끌어당깁니다. 마치 알고리즘에 적절한 "밀어주는 힘(학습률)"만 주어진다면, 경로를 벗어나지 않게 잡아주는 내부 나침반이 있는 것과 같습니다.
비결: 저자들은 학습률(learning rate)에 아주 작은 로그 보정값(logarithmic correction)을 더함으로써, 알고리즘이 스스로를 통제할 수 있다는 것을 발견했습니다.

4. "노이즈"가 섞인 데이터

현실의 데이터는 무작위가 아니라 서로 연결되어 있습니다. 오늘 사자를 봤다면, 내일도 사자를 볼 확률이 높습니다. 이를 **마르코프 노이즈(Markovian noise)**라고 합니다.

비유: 날씨를 배우는 것과 같습니다. 지금 비가 오고 있다면, 나중에도 비가 올 가능성이 높습니다. 이는 학습을 더 어렵게 만드는 의존성의 사슬을 만듭니다.
결과: 저자들은 데이터의 "끈적임(연결성)"이 정확히 어떠한지 알지 못하더라도, 이 방법이 이러한 연결된 노이즈 데이터에서도 작동함을 증명했습니다.

그들은 실제로 무엇을 했는나?

울타리를 제거함: 그들은 안전망이 없는 버전(Unprojected version)의 알고리즘을 분석했습니다.
속도를 찾아냄: 그들은 이 알고리즘이 대략 **시간의 제곱근 역수( $1/\sqrt{T}$ $1/ T$ )**의 속도로 수렴(학습)한다는 것을 증명했습니다.
- 참고: 이는 "가파른 그릇" 가정을 사용하는 빠른 방법들보다는 약간 느리지만, 그릇이 평평할 때도 작동하기 때문에 훨씬 더 신뢰할 수 있습니다.
추가 규칙 없음: 그들은 어떤 추가적인 "정칙성 조건(regularity conditions, 데이터에 대한 엄격한 규칙)"도 필요로 하지 않았습니다.
학습률: 단순히 학습률 공식에 아주 작은 로그 인자를 더하는 것만으로도 알고리즘의 안정성을 보장할 수 있음을 보여주었습니다.

한 문장 요약

이 논문은 학습 속도를 아주 미세하게 조정하는 것만으로도, 인기 있는 AI 학습법이 인위적인 안전망이나 데이터의 완벽한 형태에 의존하지 않고도 스스로 안정성을 유지하며 효과적으로 학습할 수 있다는 오래된 수수께끼를 풀었습니다.

기술 요약: 비투영(Unprojected) TD 학습에 대한 강건한 $O(1/\sqrt{T})$ 수렴율

문제 정의

선형 함수 근사를 사용하는 템포럴 디퍼런스(Temporal Difference, TD) 학습은 정책 평가를 위한 근본적인 알고리즘이다. 점근적 수렴은 잘 이해되어 있으나, 현실적인 조건(즉, 독립적인 샘플이 아닌 마르코프 체인에 의해 생성된 데이터/마르코프 노이즈) 하에서 유한 시간 수렴율을 확립하는 것은 여전히 어려운 과제로 남아 있다.

이론적으로 중요한 격차는 "강건한(robust)" 수렴율인 $O(1/\sqrt{T})$ 에 관한 것이다. 이 속도를 입증했던 기존 연구(예: Bhandari et al., 2018)는 반복값(iterates)이 발산하는 것을 방지하기 위해 유계 집합(bounded set)으로 강제 투영하는 인위적인 **투영 단계(projection step)**에 의존했다. 이러한 투영은 실제로는 거의 사용되지 않으며, 최적해 $\theta^*$ 에 대한 상한(bound)에 대한 지식을 요구하는데, 이는 대개 가용하지 않다. 반대로, 비투영 TD 학습에 대해 존재하는 "빠른(fast)" 수렴율 $O(1/T)$ 는 포텐셜 함수의 최소 곡률( $\omega$ )의 역수의 제곱에 의존한다. $\omega$ 는 임의로 작아질 수 있으므로(ill-conditioned 문제), 비점근적 영역에서 빠른 수렴율은 크게 저하될 수 있다.

Bhandari et al. (2018)이 제기한 미해결 문제는, 추가적인 정칙성 조건이나 인위적인 투영 없이도 비투영(unprojected) TD(0)가 강건한 $O(1/\sqrt{T})$ 속도를 달성할 수 있는지 여부이다.

방법론

저자들은 마르코프 샘플링 하에서의 선형 함수 근사를 사용하는 표준 비투영 TD(0) 알고리즘을 분석한다. 이들의 접근 방식은 수축 특성(contraction properties)이나 인위적 투영에 의존하는 기존 분석과는 근본적으로 다르다.

1. 포텐셜 함수 선택

저자들은 표준 $D$ -노름 거리 $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$ 대신, Liu와 Olshevsky (2021)가 제안한 포텐셜 함수를 활용한다:
$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$
이 포텐셜 함수는 다음과 같은 장점이 있다:

할인 계수 $\gamma \to 1$ 일 때도 안정적으로 유지된다.
정상 상태 업데이트 필드(stationary update field) $\bar{g}(\theta)$ 가 $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$ 를 만족하여, 다른 연구에서 사용되는 부등식보다 분석을 단순화한다.

2. 귀납법을 통한 자기 바운딩(Self-Bounding) 성질

핵심적인 기술적 기여는 TD 업데이트의 새로운 자기 바운딩 성질이다. 저자들은 스텝사이즈(stepsize)를 신중하게 선택한다면, 투영 없이도 반복값 $\{\theta_t\}$ 가 최적해 $\theta^*$ 주변에서 기대값 상으로 유계임을 증명한다.

스텝사이즈 설계: 스텝사이즈는 $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$ 로 정의되며, 여기서 $c$ 는 $c > 15 + 18\sqrt{2}$ 를 만족하는 상수이다.
귀납적 논증: 증명은 귀납법으로 진행된다. $t-1$ 시점까지 반복값이 유계라고 가정할 때, 저자들은 $t$ 시점의 업데이트 역시 유계임을 보여준다. 이는 업데이트를 마틴게일 차이 수열(martingale difference sequence, 노이즈)과 편향(bias) 항으로 분해하는 것에 기반한다.
마르코프 노이즈 처리: 마르코프 상관관계에 의한 편향(즉, $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$ )을 해결하기 위해, 저자들은 기저 마르코프 체인의 기하학적 혼합(geometric mixing)을 활용한다(Theorem 3.2). 이들은 지연(lag) $k'$ 에 대한 현재 상태 분포를 정상 분포와 연관시켜 편향을 제한한다(decay rate $\alpha^k$ 이용).

3. 유계성 분석

저자들은 반복값이 다음을 만족함을 입증한다:
$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$
여기서 $\rho_c$ 는 스텝사이즈 파라미터 $c$ 에 의존하는 상수이다. 이러한 유계성은 반복값을 투영하지 않고도 달성되며, 이를 통해 귀납법의 루프를 닫는다.

주요 결과

이론적 보장

정리 4.2: 지정된 스텝사이즈를 가진 비투영 TD(0)에 의해 생성된 가중 평균 반복값 $\bar{\theta}_T$ 에 대해, 반복값의 기대 제곱 노름은 혼합 시간(mixing time) 및 곡률 $\omega$ 와 무관한 상수로 유계된다.

따름정리 4.3: 알고리즘은 다음의 수렴율을 달성한다:
$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$
결정적으로, $\tilde{O}$ 표기법 내의 숨겨진 상수들은 $\|\theta^*\|$ 및 특징량(feature)의 경계에 의존하지만, 최소 곡률 $\omega$ 나 혼합 시간 $\alpha$ 에는 의존하지 않는다 (스텝사이즈 조건의 미세한 다항 로그 보정을 제외하면).

기존 연구와의 비교

투영된 강건한 속도와 비교: Bhandari et al. (2018)과 달리, 본 결과는 투영 단계를 제거하고 $\theta^*$ 에 대한 사전 경계 지식 요구를 없앴다. 속도는 유사( $\tilde{O}(1/\sqrt{T})$ )하지만 인위적인 제약 없이 달성되었다.
비투영 빠른 속도와 비교: Srikant와 Ying (2019) 및 이후의 $O(1/T)$ 를 달성한 연구들과 달리, 본 결과는 알려지지 않은 곡률 파라미터 $\omega$ 에 의존하지 않는다. 저자들은 반례를 통해 $\omega$ 가 임의로 작아질 수 있음을 보여주며, 이로 인해 빠른 속도가 실제 비점근적 영역에서는 매우 느려질 수 있는 반면, 강건한 속도는 안정적으로 유지됨을 보여준다.

의의 및 주장

본 논문은 Bhandari et al. (2018)이 식별한 특정 미해결 문제를 해결한다: 즉, 선형 함수 근사를 사용하는 비투영 TD(0)에 대해 강건한 수렴율을 제공하는 유한 시간 분석을 제시하는 것이다.

인위적 가정의 제거: 투영 단계가 강건한 분석을 위해 필수적이라고 여겨졌던 것과 달리, 투영 없이도 가능하다는 것을 보여준다. 반복값의 유계성은 스텝사이즈를 로그 인자와 함께 적절히 조절할 때 알고리즘의 역학(dynamics)으로부터 자연스럽게 발생한다.
추가적인 정칙성 불요: 본 결과는 문제 구조에 대한 표준적인 가정(기약성, 비주기성, 특징량의 풀 컬럼 랭크) 외에 추가적인 정칙성 조건을 가정하지 않는다.
실무적 관련성: 저자들은 이론적으로는 증명을 단순화하기 위해 투영을 사용하지만, 실제로는 사용되지 않는다는 점을 강조한다. 이 분석은 이론적 보장과 실제 알고리즘 설계 사이의 간극을 메운다.
안정성 임계치: 논문은 안정성을 위한 충분 조건으로서 스텝사이즈 상수 $c$ 에 대한 임계치(구체적으로 $c > 15 + 18\sqrt{2}$ )를 식별한다. 합성 데이터에 대한 실험 결과는 이 임계치가 실제적인 유한 시간 안정성 효과를 포착함을 시사한다. 만약 $c$ 가 너무 작으면 반복값이 발산할 수 있다.

저자들은 $c$ 에 대한 임계치가 (삼각 부등식, 코시-슈바르츠 부등식, 적분 테스트 등) 증명 과정의 상수들로부터 도출된 보수적인 충분 조건이며, 반드시 엄격한 실무적 튜닝 규칙은 아님을 언급한다. 또한, $T$ 가 혼합 시간 $\alpha$ 에 비해 충분히 커야 한다는 요구 사항은 알려진 강건한 경계(robust bounds) 문헌들이 공유하는 한계점이지만, 저자들은 알려지지 않은 혼합 파라미터를 알 필요가 있는 "anytime" 형식보다는 실행 가능한 가정(executable presentation of assumptions)을 제시하는 쪽을 선호한다고 밝히고 있다.