Q-Learning 수렴 증명의 통일된 구조

Q-Learning의 업데이트 규칙은 한 줄이다.

$$Q(s,a) \leftarrow Q(s,a) + \alpha\bigl[R + \gamma \max_{a'} Q(s',a') - Q(s,a)\bigr]$$

그런데 이 한 줄이 “왜 $Q^*$로 수렴하는가”를 엄밀하게 보이는 데 Watkins 1989부터 Jaakkola–Jordan–Singh 1994까지 5년이 걸렸다. 그 과정에서 드러난 것은 단순한 수렴 정리가 아니라 model-free RL 전체를 하나의 틀로 묶는 수학적 구조였다. 왜 이 구조가 그토록 오래 걸렸고, 무엇을 통일시키는가?

Off-Policy의 정의와 Q-Learning의 혁신

Watkins 이전의 model-free RL은 behavior policy와 target policy가 같아야 했다. SARSA가 대표적이다.

SARSA:  Q(s,a) ← Q(s,a) + α[R + γ Q(s',a') - Q(s,a)]
        여기서 a'는 현재 ε-greedy 정책으로 실제 선택된 행동

Q-Learning: Q(s,a) ← Q(s,a) + α[R + γ max_{a'} Q(s',a') - Q(s,a)]
            여기서 max는 어떤 행동을 취했든 무관하게 최대값 선택

이 차이 하나가 off-policy를 만든다. behavior policy($\epsilon$-greedy)가 탐험을 담당하는 동안, target policy(greedy max)는 최적성을 추구한다. 두 역할이 분리되므로 “탐험하면서 최적 Q를 동시에 학습”이 가능하다.

Cliff Walking 실험은 이 분리의 결과를 극명하게 보여준다. $\epsilon$-greedy 탐험 아래서 SARSA는 절벽 위쪽 안전 경로를 학습하고(탐험 실패 비용을 가치에 반영), Q-Learning은 절벽 가장자리 최단 경로를 학습한다(탐험 실패를 무시하고 max만 추구).

Bellman Operator와 고정점 해석

Q-Learning이 단순한 “경험적 trick”처럼 보이는 이유는 업데이트 대상이 무엇인지가 불분명하기 때문이다. 명확히 하면, Q-Learning의 TD target은 Bellman optimality operator $T^*$의 샘플 추정이다.

$$(T^* Q)(s,a) := \mathbb{E}_{s' \sim P(\cdot \mid s,a)}\bigl[R(s,a) + \gamma \max_{a'} Q(s',a')\bigr]$$

따라서 Q-Learning의 업데이트는 다음과 같이 다시 쓸 수 있다.

$$Q_{t+1}(s,a) = (1-\alpha_t)\,Q_t(s,a) + \alpha_t\bigl[(T^* Q_t)(s,a) + w_t(s,a)\bigr]$$

여기서 $w_t$는 zero-mean noise($\mathbb{E}[w_t \mid Q_t] = 0$), $T^*$는 $\gamma$-contraction이다. 이것이 stochastic approximation to a fixed point의 표준 형태다.

Robbins–Monro 조건과 수렴 보장

stochastic approximation이 fixed point로 수렴하려면 학습률 $\alpha_t$에 정확한 조건이 필요하다(Robbins & Monro 1951).

$$\sum_{t=0}^{\infty} \alpha_t = \infty, \qquad \sum_{t=0}^{\infty} \alpha_t^2 < \infty$$

Lyapunov 함수 $V_t = \|Q_t - Q^*\|^2$를 설정하면, contraction과 zero-mean noise 조건 아래서 $\mathbb{E}[V_{t+1} \mid \mathcal{F}_t] \leq V_t(1 - 2\alpha_t(1-\gamma)) + C\alpha_t^2$임을 보일 수 있다. 이 부등식은 $V_t$가 supermartingale이라는 뜻이고, Doob의 수렴 정리를 거쳐 $V_t \to 0$ a.s.로 이어진다.

Watkins & Dayan 1992의 정리는 세 조건으로 정리된다.

JJS 일반화 — 모든 Model-Free RL을 하나의 틀로

Jaakkola, Jordan, Singh 1994는 같은 구조가 Q-Learning에만 국한되지 않음을 보였다.

알고리즘	Operator $T$	특성
Q-Learning	$T^*$ (Bellman optimality)	off-policy
SARSA	$T^\pi$ (현재 정책의 Bellman)	on-policy
TD(0)	$T^\pi$ for $V$	on-policy, 1-step bootstrap
TD($\lambda$)	$T^\lambda$ (geometric average)	on-policy, n-step

모두 같은 형태다.

$$x_{t+1} = x_t + \alpha_t\bigl[T(x_t) - x_t + w_t\bigr]$$

$T$가 $\gamma$-contraction이고, noise가 zero-mean bounded variance이며, RM 학습률 조건이 만족되면, 어떤 알고리즘이든 fixed point로 수렴한다. 수렴의 속도는 noise의 분산에서 차이가 난다. TD의 noise는 한 step 보상에서만 오지만, MC의 noise는 전체 에피소드 return에서 온다. 낮은 분산 대신 높은 bias, 높은 분산 대신 낮은 bias — bias–variance tradeoff가 바로 여기서 나온다.

트레이드오프 — Maximization Bias와 Double Q-Learning

수렴이 보장된다고 해서 Q-Learning이 올바른 값으로 수렴한다는 뜻은 아니다. **최대화 편향(maximization bias)**이 개입한다.

$\max$ 연산은 convex 함수다. Jensen 부등식에 의해,

$$\mathbb{E}\bigl[\max_a \hat{Q}(a)\bigr] \geq \max_a\,\mathbb{E}\bigl[\hat{Q}(a)\bigr]$$

추정 오차가 있는 $\hat{Q}$에서 max를 취하면, 기댓값의 max보다 체계적으로 크다. 즉, Q-Learning의 TD target은 $Q^*$보다 지속적으로 낙관적이다.

van Hasselt 2010의 해결책은 argmax와 evaluation을 두 독립적 Q 추정으로 분리하는 것이다.

$$Q^A_{t+1}(s,a) = Q^A_t(s,a) + \alpha\Bigl[R + \gamma\,Q^B\!\left(s',\, \arg\max_{a'} Q^A(s',a')\right) - Q^A_t(s,a)\Bigr]$$

$Q^A$가 행동을 선택하고, $Q^B$가 그 행동을 평가한다. $Q^A$와 $Q^B$가 충분히 독립적이면, $Q^B$는 $Q^A$의 argmax 선택에 biased되지 않아 기댓값이 $\max_a Q^*(s',a)$에 수렴한다. 편향 제거의 대가로 분산이 약간 증가하지만 실용적으로 수용 가능하다.

이 아이디어는 2016년 van Hasselt이 DQN에 재적용해 Double DQN으로 완성한다. tabular에서 자명해 보였던 “두 개의 Q”가 neural network parameterization에서 “main network + target network” 구조로 재설계됐다.

정리

• Q-Learning의 업데이트 규칙은 Bellman optimality operator $T^*$에 대한 stochastic approximation이다.
• 수렴 보장의 핵심은 세 가지다: $T^*$의 $\gamma$-contraction, noise의 zero-mean bounded variance, Robbins–Monro 학습률.
• SARSA, TD, MC는 operator $T$만 다를 뿐 같은 구조를 공유한다. 알고리즘 간 차이는 bias와 variance의 tradeoff로 설명된다.
• 수렴하더라도 maximization bias가 Q값을 과장한다. Double Q-Learning은 argmax와 evaluation을 분리해 이 편향을 제거한다.

수렴 정리가 보장하는 것은 “학습이 멈추는 지점”이고, 최대화 편향은 “그 지점이 얼마나 낙관적인지”를 결정한다. 두 문제를 따로 이해해야 Q-Learning을 제대로 쓸 수 있다.