Tabular RL은 왜 Atari를 풀 수 없는가

Tabular Q-Learning은 이론적으로 완벽하다. Watkins(1992)의 수렴 정리는 모든 $(s, a)$를 무한히 방문하면 $Q_t \to Q^*$가 거의 확실히 성립함을 보장한다. 그런데 왜 Atari나 Go에는 쓸 수 없는가? 그리고 그 대안인 함수 근사가 왜 단순히 “신경망을 끼워 넣는 것”만으로는 안 되는가?

이론과 현실 사이: state space 폭발

Tabular 방식의 전제는 $Q(s, a)$ 테이블이 메모리에 들어가고, 모든 항목이 충분히 자주 갱신된다는 것이다. Atari 한 프레임을 보자.

$|\mathcal{S}|_{\text{Atari}} \approx 256^{84 \times 84} = 256^{7056} \approx 10^{16943}$

우주의 원자 수가 $\sim 10^{80}$이다. $10^{10}$번 플레이해도 전체 state space의 $10^{-16,933}$을 방문한다. Go 바둑판은 조금 낫지만 상황은 같다.

$|\mathcal{S}|_{\text{Go}} \approx 3^{361} \approx 10^{172}$

Watkins 정리의 핵심 조건, “모든 $(s, a)$를 무한히 방문”은 유한 시간에는 결코 충족되지 않는다. 더 근본적으로 Tabular는 generalization이 없다 — $s_1$에서 배운 것이 $s_2$에 전혀 전이되지 않는다. 비슷한 픽셀 패턴을 가진 두 프레임이라도 테이블에서는 완전히 독립적인 항목이다.

이것이 함수 근사의 동기다. 파라미터 $\theta \in \mathbb{R}^p$로 $Q(s, a; \theta)$를 표현하면 $p \ll |\mathcal{S}| \times |\mathcal{A}|$이고, 비슷한 state끼리 표현을 공유한다.

Deadly Triad: 함수 근사가 발산하는 조건

함수 근사를 도입하면 새로운 문제가 생긴다. Baird(1995)의 7상태 별 MDP는 이 문제의 가장 간결한 증거다. 7개 state, reward 전부 0, 선형 함수 근사 — 이 단순한 설정에서 가중치 norm이 지수적으로 발산한다.

Projection의 비수축성

발산의 수학적 뿌리는 projection operator에 있다. Tabular Bellman operator $T^*$는 $\|\cdot\|_\infty$ norm 하에서 $\gamma$-contraction이다.

$\|T^* u - T^* v\|_\infty \leq \gamma \|u - v\|_\infty$

함수 근사를 쓰면 $T^*$의 출력을 파라미터 공간 $\mathcal{F}$로 투영해야 한다. 문제는 $\Pi T^*$가 일반적으로 contraction이 아니라는 것이다.

$\|\Pi T^* u - \Pi T^* v\| > \gamma \|u - v\| \quad \text{(가능)}$

Banach 고정점 정리는 contraction에만 적용된다. $\Pi T^*$의 고정점이 존재하더라도 iteration이 그쪽으로 수렴한다는 보장이 없다. Baird의 발산은 정확히 $\lambda_{\max}(\Pi T^*) > 1$인 경우다.

DNN: 표현력은 충분하지만 새로운 세 가지 문제

Universal Approximation 정리(Cybenko 1989)에 따르면 충분히 넓은 1-hidden layer NN은 임의의 연속 함수를 $\epsilon$-근사한다. CNN의 계층 구조는 이보다 실용적이다 — 픽셀에서 에지로, 에지에서 객체로, 객체에서 전략으로 이어지는 hierarchical feature를 자동으로 학습한다. 이 distributed representation이 generalization을 가능하게 한다.

그러나 DNN을 Q-Learning에 단순히 끼워 넣으면 세 가지 문제가 동시에 발생한다.

Sample correlation: 연속 trajectory $(s_t, s_{t+1}, \ldots)$는 강한 시계열 상관을 갖는다. SGD의 i.i.d. 가정이 위배되어 gradient 추정이 편향된다.

Non-stationary target: $y_t = r_t + \gamma \max_a Q(s_{t+1}, a; \theta_t)$는 $\theta_t$에 의존한다. $\theta$가 바뀌면 target도 바뀐다 — “자신의 꼬리를 쫓는” 상황.

Catastrophic forgetting: 새로운 state를 학습하면서 이전 state에 대한 가중치를 덮어쓴다. RL의 sequential 특성상 특히 심각하다.

DQN(Mnih et al. 2015)의 세 trick은 이 세 문제에 각각 대응한다. Experience Replay는 sample correlation을 깨고, Target Network는 $\theta^-$를 $C$ 스텝 동안 고정하여 non-stationary target을 완화하며, Reward Clipping은 게임 간 scale 불일치를 제거한다.

정리

• Tabular Q-Learning의 수렴 보장은 “모든 state-action 쌍을 무한히 방문”을 전제한다. Atari에서 이 조건은 물리적으로 충족 불가능하다.
• Off-policy + bootstrapping + function approximation이 동시에 충족되면 발산한다(Baird 1995). 조건 셋 중 하나만 제거해도 수렴이 회복된다.
• 발산의 수학적 원인은 $\Pi T^*$의 비수축성이다 — Bellman operator 자체는 $\gamma$-contraction이지만 projection을 합성하면 보장이 깨진다.
• DNN은 universal approximation과 계층적 표현으로 generalization을 제공하지만, 새로운 세 도전(sample correlation, non-stationary target, catastrophic forgetting)을 낳는다.
• DQN의 세 trick은 이 도전들을 engineering 수준에서 완화한다. 다음 글에서는 Experience Replay와 Target Network의 내부 동작을 구체적으로 추적한다.