RL에서 함수 근사는 왜 불안정한가

Tabular RL은 상태마다 값을 하나씩 저장한다. 로봇의 관절 각도나 픽셀 이미지처럼 상태 공간이 무한하거나 연속이면, 이 전략은 처음부터 불가능하다. 그래서 함수 근사가 필요하다 — 그런데 이 근사를 도입하는 순간 수렴 보장이 무너지기 시작한다. 어떤 조건에서 수렴하고, 어떤 조건에서 발산하는가?

선형 근사의 출발점

가장 단순한 함수 근사는 선형 모델이다.

$V_\theta(s) = \theta^T \phi(s)$

여기서 $\phi: \mathcal{S} \to \mathbb{R}^d$는 feature map, $\theta \in \mathbb{R}^d$는 학습할 파라미터다. 상태 하나하나를 저장하는 대신, $d$차원 feature 공간에서 공유 표현으로 모든 상태의 값을 근사한다.

선형 모델의 핵심 장점은 볼록성이다. Loss landscape가 convex이므로 수렴 분석이 가능하다. Tsitsiklis & Van Roy (1997)는 이 설정에서 TD(0) 알고리즘이 수렴함을 증명했다.

$\theta_{t+1} = \theta_t + \alpha_t \delta_t \phi(s_t)$

TD error $\delta_t = r_t + \gamma V_{\theta_t}(s_{t+1}) - V_{\theta_t}(s_t)$에 따라 파라미터를 업데이트한다.

수렴점은 optimal value가 아니라 Projected Bellman의 고정점이라는 점이 중요하다. Feature map이 $V^\pi$를 span하지 못하면 근본적인 근사 오차가 남는다.

$\| V^*_\theta - V^\pi \|_{d^\pi} \leq \frac{1}{1-\gamma} \| V^\pi - \Pi V^\pi \|_{d^\pi}$

이 오차는 알고리즘이 아니라 feature map의 표현력이 결정한다.

Deadly Triad — 세 조건이 만나면 발산한다

On-policy 수렴 결과는 아름답지만, 현실의 deep RL은 그 조건을 거의 항상 위반한다.

Deadly Triad는 세 조건의 조합이다 (Baird 1995, Sutton & Barto 2018).

1. Off-policy learning — behavior policy $\mu$로 탐색하고 target policy $\pi$를 최적화
2. Bootstrapping — TD error $\delta_t = r_t + \gamma Q(s_{t+1}, a') - Q(s_t, a_t)$에서 $Q$ 자신을 사용
3. Function Approximation — $Q$를 $\theta$로 파라미터화

Baird의 counterexample은 7-state MDP에서 8-feature linear approximation이 Q-learning 하에서 $\|\theta\| \to \infty$로 발산함을 명시적으로 보인다. 동일한 MDP에서 on-policy SARSA는 수렴한다.

Gradient Temporal Difference (GTD)는 이 문제를 알고리즘적으로 해결한다. 보조 변수 $w$를 도입해 TD error를 “criticality”로 unweight함으로써, off-policy bias를 흡수하고 수렴 조건을 회복한다.

Linear MDP — MDP 구조 자체에서 나오는 수렴 보장

Deadly Triad의 교훈은 “임의의 MDP에서 off-policy + bootstrap + FA는 위험하다”이다. 그렇다면 MDP 자체에 특별한 구조가 있으면 어떨까?

Linear MDP는 transition kernel이 feature의 선형 결합인 MDP다 (Jin et al. 2020).

$P(s'|s,a) = \sum_{i=1}^d \phi_i(s,a)\, \mu_i(s'), \quad R(s,a) = \phi(s,a)^T \theta_R$

이 구조에서 놀라운 결과가 성립한다.

이 구조 위에서 LSVI-UCB (Least-Squares Value Iteration with Upper Confidence Bounds) 알고리즘은 다음 regret bound를 달성한다.

$\text{Regret}(K) = \tilde{O}(d^{3/2} H^{3/2} \sqrt{K})$

$d$(feature 차원), $H$(horizon), $K$(에피소드 수)의 다항식 바운드다. Tabular RL의 지수적 상태 의존성과 달리, feature 차원만으로 sample complexity가 결정된다.

Bisimulation — 어떤 상태가 진짜로 다른가

Linear MDP는 MDP 구조에 강한 가정을 요구한다. 더 일반적인 설정에서 “어떤 상태들이 실제로 구별 필요한가”라는 질문이 state abstraction의 출발점이다.

두 상태 $s, s'$가 bisimilar하다는 것은, 모든 행동에 대해 reward가 같고 다음 상태의 분포가 동일한 equivalence class로 분해된다는 것이다.

Bisimulation이 중요한 이유는 feature design의 이론적 정당화를 제공하기 때문이다. Feature map $\phi$가 bisimulation을 포착한다면 — 즉 $\phi(s) = \phi(s') \Rightarrow V^*(s) = V^*(s')$ — 선형 근사의 approximation error가 최소화된다.

현실에서는 정확한 bisimulation보다 $\epsilon$-bisimulation이 더 실용적이다.

$|V^*(s) - V^*(s')| \leq \frac{2\epsilon}{1-\gamma}$

$\epsilon$이 작으면 value 오차도 작다. 이 bound는 $(1-\gamma)$의 역수로 증폭되므로, 할인율이 1에 가까울수록 작은 근사 오차도 큰 영향을 미친다.

트레이드오프

네 챕터를 관통하는 공통 구조가 있다 — 수렴 보장과 표현력의 교환.

정리

• 선형 근사 $V_\theta(s) = \theta^T\phi(s)$는 on-policy TD(0)에서 수렴하지만, 수렴점은 optimal이 아닌 Projected Bellman의 고정점이다.
• Off-policy + Bootstrapping + FA의 Deadly Triad는 선형 근사에서도 발산을 유발한다. DQN의 불안정성은 버그가 아니라 이 구조에서 나온다.
• Linear MDP는 MDP 자체에 선형 구조를 가정함으로써 $\tilde{O}(d^{3/2}H^{3/2}\sqrt{K})$ regret을 달성한다 — exponential이 아닌 polynomial.
• Bisimulation은 “어떤 상태가 진짜로 다른가”를 수학적으로 정의하고, $\epsilon$-근사에서 value 오차를 $2\epsilon/(1-\gamma)$로 bound한다.

표현력을 높일수록 수렴 보장은 약해진다. Deep RL은 이 트레이드오프의 극단에 서 있다.