Log-derivative trick부터 score function의 zero-mean 성질, REINFORCE의 unbiasedness와 variance 폭발 메커니즘, reparameterization과의 tradeoff까지 policy gradient의 수학적 토대를 추적한다.
Policy gradient는 J ( θ ) = E τ ∼ p θ [ R ( τ ) ] J(\theta) = \mathbb{E}_{\tau \sim p_\theta}[R(\tau)] J ( θ ) = E τ ∼ p θ [ R ( τ )] R ( τ ) R(\tau) R ( τ ) θ \theta θ
Gradient를 기대값 안으로 옮기는 방법
E x ∼ p θ [ f ( x ) ] \mathbb{E}_{x \sim p_\theta}[f(x)] E x ∼ p θ [ f ( x )] θ \theta θ ∇ θ p θ ( x ) \nabla_\theta p_\theta(x) ∇ θ p θ ( x )
∇ θ p θ ( x ) = p θ ( x ) ⋅ ∇ θ log p θ ( x ) \nabla_\theta p_\theta(x) = p_\theta(x) \cdot \nabla_\theta \log p_\theta(x) ∇ θ p θ ( x ) = p θ ( x ) ⋅ ∇ θ log p θ ( x ) 이를 기대값에 대입하면,
∇ θ E x ∼ p θ [ f ( x ) ] = E x ∼ p θ [ f ( x ) ⋅ ∇ θ log p θ ( x ) ] \nabla_\theta \mathbb{E}_{x \sim p_\theta}[f(x)] = \mathbb{E}_{x \sim p_\theta}\bigl[f(x) \cdot \nabla_\theta \log p_\theta(x)\bigr] ∇ θ E x ∼ p θ [ f ( x )] = E x ∼ p θ [ f ( x ) ⋅ ∇ θ log p θ ( x ) ] gradient가 기대값 안으로 들어갔다. f ( x ) f(x) f ( x ) likelihood ratio method 또는 score function estimator 라고 불리는 이유다.
이산 분포에서도 동일하게 성립한다. p θ ( a ) p_\theta(a) p θ ( a ) ∇ θ log p θ ( a ) = 1 ( a ) − p θ \nabla_\theta \log p_\theta(a) = \mathbf{1}(a) - p_\theta ∇ θ log p θ ( a ) = 1 ( a ) − p θ
Score Function의 두 가지 핵심 성질
s θ ( x ) : = ∇ θ log p θ ( x ) s_\theta(x) := \nabla_\theta \log p_\theta(x) s θ ( x ) := ∇ θ log p θ ( x )
Zero-mean : E x ∼ p θ [ s θ ( x ) ] = 0 \mathbb{E}_{x \sim p_\theta}[s_\theta(x)] = 0 E x ∼ p θ [ s θ ( x )] = 0
E [ s ] = ∫ ∇ θ log p θ ( x ) ⋅ p θ ( x ) d x = ∫ ∇ θ p θ ( x ) d x = ∇ θ ∫ p θ ( x ) d x = ∇ θ 1 = 0 \mathbb{E}[s] = \int \nabla_\theta \log p_\theta(x) \cdot p_\theta(x)\,dx = \int \nabla_\theta p_\theta(x)\,dx = \nabla_\theta \int p_\theta(x)\,dx = \nabla_\theta 1 = 0 E [ s ] = ∫ ∇ θ log p θ ( x ) ⋅ p θ ( x ) d x = ∫ ∇ θ p θ ( x ) d x = ∇ θ ∫ p θ ( x ) d x = ∇ θ 1 = 0 Fisher Information : F ( θ ) = E [ s ⋅ s T ] = − E [ ∇ 2 log p θ ] F(\theta) = \mathbb{E}[s \cdot s^T] = -\mathbb{E}[\nabla^2 \log p_\theta] F ( θ ) = E [ s ⋅ s T ] = − E [ ∇ 2 log p θ ]
정리 1
· Fisher = −E[Hessian of log p]
정규 조건(dominated convergence) 하에,
F ( θ ) = E x ∼ p θ [ s θ ( x ) s θ ( x ) T ] = − E x ∼ p θ [ ∇ θ 2 log p θ ( x ) ] F(\theta) = \mathbb{E}_{x \sim p_\theta}[s_\theta(x)\, s_\theta(x)^T] = -\mathbb{E}_{x \sim p_\theta}[\nabla^2_\theta \log p_\theta(x)] F ( θ ) = E x ∼ p θ [ s θ ( x ) s θ ( x ) T ] = − E x ∼ p θ [ ∇ θ 2 log p θ ( x )]
▷ 증명
∇ 2 log p = ∇ 2 p p − ( ∇ log p ) ( ∇ log p ) T \nabla^2 \log p = \frac{\nabla^2 p}{p} - (\nabla \log p)(\nabla \log p)^T ∇ 2 log p = p ∇ 2 p − ( ∇ log p ) ( ∇ log p ) T ( ∇ log p ) ( ∇ log p ) T = ∇ 2 p p − ∇ 2 log p (\nabla \log p)(\nabla \log p)^T = \frac{\nabla^2 p}{p} - \nabla^2 \log p ( ∇ log p ) ( ∇ log p ) T = p ∇ 2 p − ∇ 2 log p E [ ∇ 2 p / p ] = ∇ θ 2 ∫ p θ d x = 0 \mathbb{E}[\nabla^2 p / p] = \nabla^2_\theta \int p_\theta\,dx = 0 E [ ∇ 2 p / p ] = ∇ θ 2 ∫ p θ d x = 0 F = − E [ ∇ 2 log p ] F = -\mathbb{E}[\nabla^2 \log p] F = − E [ ∇ 2 log p ] □ \square □
∎
Zero-mean 성질은 baseline의 정당화 로 직결된다. 임의의 함수 b ( s ) b(s) b ( s ) E [ b ( s ) ⋅ s θ ] = 0 \mathbb{E}[b(s) \cdot s_\theta] = 0 E [ b ( s ) ⋅ s θ ] = 0
E [ ( f + b ) ⋅ s θ ] = E [ f ⋅ s θ ] \mathbb{E}[(f + b) \cdot s_\theta] = \mathbb{E}[f \cdot s_\theta] E [( f + b ) ⋅ s θ ] = E [ f ⋅ s θ ] baseline을 빼도 기대값(=gradient)이 보존된다.
REINFORCE: Trajectory로의 확장
trajectory τ = ( s 0 , a 0 , r 0 , … ) \tau = (s_0, a_0, r_0, \ldots) τ = ( s 0 , a 0 , r 0 , … )
p θ ( τ ) = ρ 0 ( s 0 ) ∏ t π θ ( a t ∣ s t ) P ( s t + 1 ∣ s t , a t ) p_\theta(\tau) = \rho_0(s_0)\prod_{t} \pi_\theta(a_t|s_t)\,P(s_{t+1}|s_t,a_t) p θ ( τ ) = ρ 0 ( s 0 ) t ∏ π θ ( a t ∣ s t ) P ( s t + 1 ∣ s t , a t ) log를 취하면 환경 dynamics 항은 θ \theta θ
∇ θ log p θ ( τ ) = ∑ t ∇ θ log π θ ( a t ∣ s t ) \nabla_\theta \log p_\theta(\tau) = \sum_{t} \nabla_\theta \log \pi_\theta(a_t|s_t) ∇ θ log p θ ( τ ) = t ∑ ∇ θ log π θ ( a t ∣ s t ) score는 policy 항만 남는다. Log-derivative trick을 J ( θ ) = E τ [ R ( τ ) ] J(\theta) = \mathbb{E}_\tau[R(\tau)] J ( θ ) = E τ [ R ( τ )]
∇ θ J ( θ ) = E τ [ ∑ t G t ⋅ ∇ θ log π θ ( a t ∣ s t ) ] \boxed{\nabla_\theta J(\theta) = \mathbb{E}_\tau\!\left[\sum_t G_t \cdot \nabla_\theta \log \pi_\theta(a_t|s_t)\right]} ∇ θ J ( θ ) = E τ [ t ∑ G t ⋅ ∇ θ log π θ ( a t ∣ s t ) ] 여기서 G t = ∑ l ≥ 0 γ l r t + l G_t = \sum_{l \geq 0} \gamma^l r_{t+l} G t = ∑ l ≥ 0 γ l r t + l t t t r l r_l r l l < t l < t l < t g ^ ( τ ) \hat{g}(\tau) g ^ ( τ ) unbiased : E [ g ^ ] = ∇ J ( θ ) \mathbb{E}[\hat{g}] = \nabla J(\theta) E [ g ^ ] = ∇ J ( θ )
Williams(1992)의 “reinforcement” 해석: G t > 0 G_t > 0 G t > 0 log π ( a t ∣ s t ) \log \pi(a_t|s_t) log π ( a t ∣ s t ) G t < 0 G_t < 0 G t < 0
분산 폭발의 메커니즘
Unbiasedness는 수렴을 보장하지만 분산을 제어하지 않는다.
Var [ G t ] = ∑ l = 0 ∞ γ 2 l σ r 2 = σ r 2 1 − γ 2 \text{Var}[G_t] = \sum_{l=0}^{\infty} \gamma^{2l}\,\sigma_r^2 = \frac{\sigma_r^2}{1-\gamma^2} Var [ G t ] = l = 0 ∑ ∞ γ 2 l σ r 2 = 1 − γ 2 σ r 2 γ → 1 \gamma \to 1 γ → 1 σ r 2 2 ( 1 − γ ) \frac{\sigma_r^2}{2(1-\gamma)} 2 ( 1 − γ ) σ r 2
Var [ g ^ ] = O ( σ r 2 ( 1 − γ ) 3 ) \text{Var}[\hat{g}] = O\!\left(\frac{\sigma_r^2}{(1-\gamma)^3}\right) Var [ g ^ ] = O ( ( 1 − γ ) 3 σ r 2 ) ⚠ Sparse Reward에서의 분산 폭발
보상이 r = 1 r = 1 r = 1 p s p_s p s r = 0 r = 0 r = 0 1 − p s 1-p_s 1 − p s Var [ R ] ≈ p s R 2 \text{Var}[R] \approx p_s R^2 Var [ R ] ≈ p s R 2 ≈ 1 / p s \approx 1/p_s ≈ 1/ p s p s = 0.01 p_s = 0.01 p s = 0.01
Horizon이 길어질수록, discount가 1에 가까울수록, reward가 희박할수록 분산은 지수적으로 커진다. Baseline b ( s t ) b(s_t) b ( s t ) A t = G t − b ( s t ) A_t = G_t - b(s_t) A t = G t − b ( s t ) λ \lambda λ
Score Function vs. Reparameterization
연속 행동 공간에서는 다른 gradient 경로가 있다.
Reparameterization : a = g θ ( ϵ ) a = g_\theta(\epsilon) a = g θ ( ϵ ) ϵ ∼ p ( ϵ ) \epsilon \sim p(\epsilon) ϵ ∼ p ( ϵ ) θ \theta θ
∇ θ E [ f ( a ) ] = E ϵ [ ∇ θ f ( g θ ( ϵ ) ) ] \nabla_\theta \mathbb{E}[f(a)] = \mathbb{E}_\epsilon[\nabla_\theta f(g_\theta(\epsilon))] ∇ θ E [ f ( a )] = E ϵ [ ∇ θ f ( g θ ( ϵ ))] chain rule로 f f f f f f 분산이 score function 방식보다 훨씬 낮다 .
✎ 트레이드오프
Score function : discrete·continuous 모두 적용. f f f
Reparameterization : continuous만 적용. f f f
Discrete action에서 reparameterization을 쓰려면 Gumbel-Softmax처럼 연속 근사가 필요하고, 이는 temperature hyperparameter와 근사 bias를 도입한다.
이산 행동에서 a = g θ ( ϵ ) a = g_\theta(\epsilon) a = g θ ( ϵ ) ∂ g θ / ∂ θ = 0 \partial g_\theta / \partial \theta = 0 ∂ g θ / ∂ θ = 0 ∇ log p \nabla \log p ∇ log p
✎ 설계 철학
두 방법의 분기점은 “reward에 미분을 요구하는가”다. Score function은 reward를 블랙박스로 취급하고 policy의 log-prob만 미분한다. Reparameterization은 reward까지 미분 경로를 열어 분산을 낮추는 대신 환경 미분가능성을 요구한다. 행동 공간의 구조가 알고리즘 선택을 결정한다.
정리
∇ θ p θ = p θ ⋅ ∇ θ log p θ \nabla_\theta p_\theta = p_\theta \cdot \nabla_\theta \log p_\theta ∇ θ p θ = p θ ⋅ ∇ θ log p θ f f f Score function의 zero-mean 성질 E [ s θ ] = 0 \mathbb{E}[s_\theta] = 0 E [ s θ ] = 0
REINFORCE는 unbiased이지만 Var [ g ^ ] = O ( ( 1 − γ ) − 3 ) \text{Var}[\hat{g}] = O((1-\gamma)^{-3}) Var [ g ^ ] = O (( 1 − γ ) − 3 )
Reparameterization은 연속 행동에서 분산을 낮추는 대안이지만 이산 행동에는 적용할 수 없다.
분산 문제는 알고리즘의 결함이 아니라 log-derivative trick이 요구하는 구조적 대가다.