다음과 같이 구성을 해봤습니다. TRPO를 정말 너무너무 이해하고 싶었는데 이 참에 binge-reading 하고 흐름을 전체적으로 정리해봤습니다.
Step 핵심 개념 역할 / 의미 요약 1 Advantage 정의 행동이 평균보다 얼마나 나은지 측정 2 Bellman Expectation 식 Q와 V의 관계 정의, Advantage 계산에 사용 3 Score Function Trick 확률 정책의 gradient 계산 가능하게 만듦 4 Policy Gradient Theorem 기대 보상을 높이는 gradient 방향 도출 5 Performance Difference 새 정책의 성능 향상 정도를 정확히 계산 6 Surrogate Objective 정의 실제 성능을 근사하는 계산 가능한 손실 함수 7 Importance Sampling 기존 정책으로 기대값을 추정하는 테크닉 8 State Visitation Bound 정책 변경 시 생기는 분포 차이를 제한 9 Policy Improvement Bound surrogate와 실제 성능 차이를 이론적으로 제한 10 Pinsker's Inequality TV 거리 대신 KL 제약을 쓰기 위한 이론적 근거 11 TRPO 최적화 문제 정의 KL 제약 하에서 surrogate를 최대화 12 Natural Gradient 분포의 곡률을 고려한 최적 ascent 방향 선택
STEP 1: Advantage Function 정의
A π ( s , a ) = Q π ( s , a ) − V π ( s ) A_\pi(s, a) = Q_\pi(s,a) - V_\pi(s) A π ( s , a ) = Q π ( s , a ) − V π ( s )
Advantage는 특정 행동이 평균보다 얼마나 더 나은지를 측정합니다.
Q Q Q V V V A A A
STEP 2: Bellman Expectation Equation
State-value function (Definition) :
V π ( s t ) = E a t , s t + 1 , a t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ∣ s t ] V_\pi(s_t) = \mathbb{E}_{a_t, s_{t+1}, a_{t+1}, \dots} \left[ \sum_{l=0}^\infty \gamma^l r(s_{t+l}) \mid s_t \right] V π ( s t ) = E a t , s t + 1 , a t + 1 , … [ l = 0 ∑ ∞ γ l r ( s t + l ) ∣ s t ]
Action-value function (Definition) :
Q π ( s t , a t ) = E s t + 1 , a t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ∣ s t , a t ] Q_\pi(s_t, a_t) = \mathbb{E}_{s_{t+1}, a_{t+1}, \dots} \left[ \sum_{l=0}^\infty \gamma^l r(s_{t+l}) \mid s_t, a_t \right] Q π ( s t , a t ) = E s t + 1 , a t + 1 , … [ l = 0 ∑ ∞ γ l r ( s t + l ) ∣ s t , a t ]
Bellman Expectation Equation
V π ( s ) = ∑ a π ( a ∣ s ) Q π ( s , a ) V_\pi(s) = \sum_a \pi(a|s) Q_\pi(s,a) V π ( s ) = a ∑ π ( a ∣ s ) Q π ( s , a ) 증명
TRPO 논문 내에서 사용되는 Bellman expectation identity입니다. Performance Difference Lemma (Step 5) 등에서 핵심적으로 활용할 수 있습니다.
V π ( s t ) = E a t ∼ π ( ⋅ ∣ s t ) [ E s t + 1 , a t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ∣ s t , a t ] ] = ∑ a t π ( a t ∣ s t ) ⋅ E s t + 1 , a t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ∣ s t , a t ] = ∑ a t π ( a t ∣ s t ) Q π ( s t , a t ) \begin{aligned} V_\pi(s_t) &= \mathbb{E}_{a_t \sim \pi(\cdot|s_t)} \left[ \mathbb{E}_{s_{t+1}, a_{t+1}, \dots} \left[ \sum_{l=0}^\infty \gamma^l r(s_{t+l}) \mid s_t, a_t \right] \right] \\ &= \sum_{a_t} \pi(a_t | s_t) \cdot \mathbb{E}_{s_{t+1}, a_{t+1}, \dots} \left[ \sum_{l=0}^\infty \gamma^l r(s_{t+l}) \mid s_t, a_t \right] \\ &= \sum_{a_t} \pi(a_t | s_t) Q_\pi(s_t, a_t) \end{aligned} V π ( s t ) = E a t ∼ π ( ⋅ ∣ s t ) [ E s t + 1 , a t + 1 , … [ l = 0 ∑ ∞ γ l r ( s t + l ) ∣ s t , a t ] ] = a t ∑ π ( a t ∣ s t ) ⋅ E s t + 1 , a t + 1 , … [ l = 0 ∑ ∞ γ l r ( s t + l ) ∣ s t , a t ] = a t ∑ π ( a t ∣ s t ) Q π ( s t , a t ) STEP 3: Score Function Trick
∇ θ 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}[f(x) \nabla_\theta \log p_\theta(x)] ∇ θ E x ∼ p θ [ f ( x ) ] = E x ∼ p θ [ f ( x ) ∇ θ log p θ ( x ) ] 다음과 같은 가정하에 증명을 완수할 수 있습니다.
p θ ( x ) p_\theta(x) p θ ( x ) θ \theta θ f ( x ) f(x) f ( x ) x x x E p θ [ f ( x ) ] \mathbb{E}_{p_\theta}[f(x)] E p θ [ f ( x ) ] 미분 연산과 적분 순서를 바꿀 수 있을 만큼 regular한 조건이 성립한다고 가정 (Lebesgue의 dominated convergence theorem 사용 가능)
증명
E x ∼ p θ [ f ( x ) ] = ∫ f ( x ) p θ ( x ) d x \mathbb{E}_{x \sim p_\theta}[f(x)] = \int f(x)\ p_\theta(x)\ dx E x ∼ p θ [ f ( x ) ] = ∫ f ( x ) p θ ( x ) d x ∇ θ E x ∼ p θ [ f ( x ) ] = ∇ θ ∫ f ( x ) p θ ( x ) d x = ∫ f ( x ) ∇ θ p θ ( x ) d x \nabla_\theta \mathbb{E}_{x \sim p_\theta}[f(x)] = \nabla_\theta \int f(x)\ p_\theta(x)\ dx = \int f(x)\ \nabla_\theta p_\theta(x)\ dx ∇ θ E x ∼ p θ [ f ( x ) ] = ∇ θ ∫ f ( x ) p θ ( x ) d x = ∫ f ( x ) ∇ θ p θ ( x ) d x 한편, chain rule에 의해
∇ θ log p θ ( x ) = 1 p θ ( x ) ∇ θ p θ ( x ) ⇒ ∇ θ p θ ( x ) = p θ ( x ) ∇ θ log p θ ( x ) \nabla_\theta \log p_\theta(x) = \frac{1}{p_\theta(x)} \nabla_\theta p_\theta(x) \Rightarrow \nabla_\theta p_\theta(x) = p_\theta(x) \nabla_\theta \log p_\theta(x) ∇ θ log p θ ( x ) = p θ ( x ) 1 ∇ θ p θ ( x ) ⇒ ∇ θ p θ ( x ) = p θ ( x ) ∇ θ log p θ ( x ) 임을 확인할 수 있습니다. 따라서,
∫ f ( x ) ∇ θ p θ ( x ) d x = ∫ f ( x ) p θ ( x ) ∇ θ log p θ ( x ) d x \int f(x)\ \nabla_\theta p_\theta(x)\ dx = \int f(x)\ p_\theta(x)\ \nabla_\theta \log p_\theta(x)\ dx ∫ f ( x ) ∇ θ p θ ( x ) d x = ∫ f ( x ) p θ ( x ) ∇ θ log p θ ( x ) d x = E x ∼ p θ [ f ( x ) ∇ θ log p θ ( x ) ] = \mathbb{E}_{x \sim p_\theta} \left[ f(x)\ \nabla_\theta \log p_\theta(x) \right] = E x ∼ p θ [ f ( x ) ∇ θ log p θ ( x ) ] Score Function Trick은 강화학습의 policy gradient, variational inference, REINFORCE 등에 폭넓게 사용됩니다.
STEP 4: Policy Gradient Theorem
Expected Return(Definition)
η ( π θ ) = E τ ∼ π θ [ ∑ t = 0 ∞ γ t r ( s t ) ] \eta(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \gamma^t r(s_t) \right] η ( π θ ) = E τ ∼ π θ [ t = 0 ∑ ∞ γ t r ( s t ) ] (여기서 τ = ( s 0 , a 0 , s 1 , a 1 , … ) \tau = (s_0, a_0, s_1, a_1, \dots) τ = ( s 0 , a 0 , s 1 , a 1 , … ) π θ \pi_\theta π θ
(un-normalized) State Visitation Distribution(Definition)
ρ π ( s ) = ∑ t = 0 ∞ γ t P ( s t = s ∣ π ) \rho_{\pi}(s) = \sum_{t=0}^\infty \gamma^t P(s_t = s \mid \pi) ρ π ( s ) = t = 0 ∑ ∞ γ t P ( s t = s ∣ π ) → 모든 timestep에서 방문될 확률을 가중합한 분포 (discounted)
Policy Gradient Theorem :
∇ θ η ( π θ ) = E s ∼ ρ π , a ∼ π [ ∇ θ log π θ ( a ∣ s ) Q π ( s , a ) ] \nabla_\theta \eta(\pi_\theta) = \mathbb{E}_{s \sim \rho_\pi, a \sim \pi} \left[ \nabla_\theta \log \pi_\theta(a|s) Q_\pi(s, a) \right] ∇ θ η ( π θ ) = E s ∼ ρ π , a ∼ π [ ∇ θ log π θ ( a ∣ s ) Q π ( s , a ) ]
증명
η ( π θ ) = E τ ∼ π θ [ ∑ t = 0 ∞ γ t r ( s t ) ] \eta(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \gamma^t r(s_t) \right] η ( π θ ) = E τ ∼ π θ [ t = 0 ∑ ∞ γ t r ( s t ) ] = ∫ P ( τ ; θ ) ( ∑ t = 0 ∞ γ t r ( s t ) ) d τ = \int P(\tau; \theta)\ \left( \sum_{t=0}^{\infty} \gamma^t r(s_t) \right)\ d\tau = ∫ P ( τ ; θ ) ( t = 0 ∑ ∞ γ t r ( s t ) ) d τ 여기서 trajectory 확률은:
P ( τ ; θ ) = ρ 0 ( s 0 ) ∏ t = 0 ∞ π θ ( a t ∣ s t ) P ( s t + 1 ∣ s t , a t ) P(\tau; \theta) = \rho_0(s_0) \prod_{t=0}^\infty \pi_\theta(a_t | s_t) P(s_{t+1} | s_t, a_t) P ( τ ; θ ) = ρ 0 ( s 0 ) t = 0 ∏ ∞ π θ ( a t ∣ s t ) P ( s t + 1 ∣ s t , a t ) 미분 연산자를 도입하면,
∇ θ η ( π θ ) = ∇ θ ∫ P ( τ ; θ ) ( ∑ t = 0 ∞ γ t r ( s t ) ) d τ \nabla_\theta \eta(\pi_\theta) = \nabla_\theta \int P(\tau; \theta)\ \left( \sum_{t=0}^{\infty} \gamma^t r(s_t) \right)\ d\tau ∇ θ η ( π θ ) = ∇ θ ∫ P ( τ ; θ ) ( t = 0 ∑ ∞ γ t r ( s t ) ) d τ = ∫ ( ∑ t = 0 ∞ γ t r ( s t ) ) ∇ θ log P ( τ ; θ ) P ( τ ; θ ) d τ = \int \left( \sum_{t=0}^{\infty} \gamma^t r(s_t) \right) \nabla_\theta \log P(\tau; \theta)\ P(\tau; \theta)\ d\tau = ∫ ( t = 0 ∑ ∞ γ t r ( s t ) ) ∇ θ log P ( τ ; θ ) P ( τ ; θ ) d τ = E τ ∼ π θ [ ( ∑ t = 0 ∞ γ t r ( s t ) ) ∇ θ log P ( τ ; θ ) ] = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \left( \sum_{t=0}^{\infty} \gamma^t r(s_t) \right)\ \nabla_\theta \log P(\tau; \theta) \right] = E τ ∼ π θ [ ( t = 0 ∑ ∞ γ t r ( s t ) ) ∇ θ log P ( τ ; θ ) ] 한편, 환경의 transition은 θ \theta θ
∇ θ log P ( τ ; θ ) = ∑ t = 0 ∞ ∇ θ log π θ ( a t ∣ s t ) \nabla_\theta \log P(\tau; \theta) = \sum_{t=0}^{\infty} \nabla_\theta \log \pi_\theta(a_t | s_t) ∇ θ log P ( τ ; θ ) = t = 0 ∑ ∞ ∇ θ log π θ ( a t ∣ s t ) ∇ θ η ( π θ ) = E τ ∼ π θ [ ∑ t = 0 ∞ γ t r ( s t ) ∑ t ′ = 0 ∞ ∇ θ log π θ ( a t ′ ∣ s t ′ ) ] \nabla_\theta \eta(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \gamma^t r(s_t)\ \sum_{t'=0}^{\infty} \nabla_\theta \log \pi_\theta(a_{t'}|s_{t'}) \right] ∇ θ η ( π θ ) = E τ ∼ π θ [ t = 0 ∑ ∞ γ t r ( s t ) t ′ = 0 ∑ ∞ ∇ θ log π θ ( a t ′ ∣ s t ′ ) ] 즉,
= E τ ∼ π θ [ ∑ t = 0 ∞ ∇ θ log π θ ( a t ∣ s t ) R t ] = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \nabla_\theta \log \pi_\theta(a_t | s_t)\ R_t \right] = E τ ∼ π θ [ t = 0 ∑ ∞ ∇ θ log π θ ( a t ∣ s t ) R t ] 여기서 R t = ∑ l = 0 ∞ γ l r ( s t + l ) R_t = \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) R t = ∑ l = 0 ∞ γ l r ( s t + l )
마지막으로, 각 ( s t , a t ) (s_t, a_t) ( s t , a t )
E τ [ ∇ θ log π θ ( a t ∣ s t ) ⋅ R t ] = E s t ∼ ρ π , a t ∼ π [ ∇ θ log π θ ( a t ∣ s t ) Q π ( s t , a t ) ] \mathbb{E}_{\tau} \left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \cdot R_t \right] = \mathbb{E}_{s_t \sim \rho_\pi,\ a_t \sim \pi} \left[ \nabla_\theta \log \pi_\theta(a_t|s_t)\ Q_\pi(s_t, a_t) \right] E τ [ ∇ θ log π θ ( a t ∣ s t ) ⋅ R t ] = E s t ∼ ρ π , a t ∼ π [ ∇ θ log π θ ( a t ∣ s t ) Q π ( s t , a t ) ] 따라서,
∇ θ η ( π θ ) = E s ∼ ρ π θ , a ∼ π θ [ ∇ θ log π θ ( a ∣ s ) Q π θ ( s , a ) ] \boxed{ \nabla_\theta \eta(\pi_\theta) = \mathbb{E}_{s \sim \rho_{\pi_\theta}, a \sim \pi_\theta} \left[ \nabla_\theta \log \pi_\theta(a|s) Q_{\pi_\theta}(s, a) \right] } ∇ θ η ( π θ ) = E s ∼ ρ π θ , a ∼ π θ [ ∇ θ log π θ ( a ∣ s ) Q π θ ( s , a ) ] η ( π ′ ) − η ( π ) = ∑ s ρ π ′ ( s ) ∑ a π ′ ( a ∣ s ) A π ( s , a ) \eta(\pi') - \eta(\pi) = \sum_s \rho_{\pi'}(s) \sum_a \pi'(a|s) A_\pi(s, a) η ( π ′ ) − η ( π ) = s ∑ ρ π ′ ( s ) a ∑ π ′ ( a ∣ s ) A π ( s , a )
새 정책과 기존 정책의 기대 리턴 차이 계산법입니다만, 엄격한 항등식임을 증명하진 못했습니다. 아마, η \eta η r r r A A A
증명
η ( π ′ ) = E τ ∼ π ′ [ ∑ t = 0 ∞ γ t r ( s t ) ] = ∑ t = 0 ∞ γ t E s t , a t ∼ π ′ [ r ( s t ) ] (1) \eta(\pi') = \mathbb{E}_{\tau \sim \pi'} \left[ \sum_{t=0}^\infty \gamma^t r(s_t) \right] = \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_t, a_t \sim \pi'} [r(s_t)] \tag{1} η ( π ′ ) = E τ ∼ π ′ [ t = 0 ∑ ∞ γ t r ( s t ) ] = t = 0 ∑ ∞ γ t E s t , a t ∼ π ′ [ r ( s t ) ] ( 1 ) 이제 r ( s t ) r(s_t) r ( s t ) Q π ( s t , a t ) Q_\pi(s_t, a_t) Q π ( s t , a t )
= ∑ t = 0 ∞ γ t E s t , a t ∼ π ′ [ Q π ( s t , a t ) ] = \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_t, a_t \sim \pi'} [Q_\pi(s_t, a_t)] = t = 0 ∑ ∞ γ t E s t , a t ∼ π ′ [ Q π ( s t , a t ) ] 한편,
Q π ( s , a ) = A π ( s , a ) + V π ( s ) Q_\pi(s,a) = A_\pi(s,a) + V_\pi(s) Q π ( s , a ) = A π ( s , a ) + V π ( s ) 이므로
η ( π ′ ) = ∑ t = 0 ∞ γ t E s t , a t ∼ π ′ [ A π ( s t , a t ) ] + ∑ t = 0 ∞ γ t E s t ∼ π ′ [ V π ( s t ) ] \eta(\pi') = \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_t, a_t \sim \pi'} [A_\pi(s_t, a_t)] + \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_t \sim \pi'} [V_\pi(s_t)] η ( π ′ ) = t = 0 ∑ ∞ γ t E s t , a t ∼ π ′ [ A π ( s t , a t ) ] + t = 0 ∑ ∞ γ t E s t ∼ π ′ [ V π ( s t ) ] η ( π ) \eta(\pi) η ( π )
η ( π ) = ∑ t = 0 ∞ γ t E s t ∼ π [ V π ( s t ) ] \eta(\pi) = \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_t \sim \pi} [V_\pi(s_t)] η ( π ) = t = 0 ∑ ∞ γ t E s t ∼ π [ V π ( s t ) ] 이 둘의 차이를 구하면
η ( π ′ ) − η ( π ) = ∑ t = 0 ∞ γ t E s t , a t ∼ π ′ [ A π ( s t , a t ) ] + ∑ t = 0 ∞ γ t ( E s t ∼ π ′ [ V π ( s t ) ] − E s t ∼ π [ V π ( s t ) ] ) \eta(\pi') - \eta(\pi) = \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_t, a_t \sim \pi'} [A_\pi(s_t, a_t)] + \sum_{t=0}^\infty \gamma^t (\mathbb{E}_{s_t \sim \pi'} [V_\pi(s_t)] - \mathbb{E}_{s_t \sim \pi} [V_\pi(s_t)]) η ( π ′ ) − η ( π ) = t = 0 ∑ ∞ γ t E s t , a t ∼ π ′ [ A π ( s t , a t ) ] + t = 0 ∑ ∞ γ t ( E s t ∼ π ′ [ V π ( s t ) ] − E s t ∼ π [ V π ( s t ) ] ) 정책이 매우 조금 변동되어 두 번째 항을 0 0 0
STEP 6: Surrogate Objective (approximation)
η ( π ′ ) ≈ L π ( π ′ ) = η ( π ) + ∑ s ρ π ( s ) ∑ a π ′ ( a ∣ s ) A π ( s , a ) \eta(\pi') \approx L_\pi(\pi') = \eta(\pi) + \sum_s \rho_\pi(s) \sum_a \pi'(a|s) A_\pi(s,a) η ( π ′ ) ≈ L π ( π ′ ) = η ( π ) + s ∑ ρ π ( s ) a ∑ π ′ ( a ∣ s ) A π ( s , a ) L π ( π ′ ) 는 η ( π ′ ) 의 1차 근사이며, π ′ = π 에서 함수값과 gradient가 동일하다 \boxed{ L_\pi(\pi') \text{는 } \eta(\pi') \text{의 1차 근사이며, } \pi' = \pi \text{에서 함수값과 gradient가 동일하다} } L π ( π ′ ) 는 η ( π ′ ) 의 1 차 근사이며 , π ′ = π 에서 함수값과 gradient 가 동일하다 surrogate objective는 η ( π ′ ) \eta(\pi') η ( π ′ )
증명
우리는 다음을 증명하고자 합니다:
L π ( π ) = η ( π ) and ∇ π ′ L π ( π ′ ) ∣ π ′ = π = ∇ π ′ η ( π ′ ) ∣ π ′ = π L_\pi(\pi) = \eta(\pi) \quad \text{and} \quad \nabla_{\pi'} L_\pi(\pi')\Big|_{\pi' = \pi} = \nabla_{\pi'} \eta(\pi')\Big|_{\pi' = \pi} L π ( π ) = η ( π ) and ∇ π ′ L π ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π = ∇ π ′ η ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π 먼저, 함수값이 동일한지 살펴봅시다.
L π ( π ) = η ( π ) + ∑ s ρ π ( s ) ∑ a π ( a ∣ s ) A π ( s , a ) L_\pi(\pi) = \eta(\pi) + \sum_s \rho_\pi(s) \sum_a \pi(a|s) A_\pi(s,a) L π ( π ) = η ( π ) + s ∑ ρ π ( s ) a ∑ π ( a ∣ s ) A π ( s , a ) 한편,
A π ( s , a ) = Q π ( s , a ) − V π ( s ) , V π ( s ) = ∑ a π ( a ∣ s ) Q π ( s , a ) A_\pi(s,a) = Q_\pi(s,a) - V_\pi(s), \quad V_\pi(s) = \sum_a \pi(a|s) Q_\pi(s,a) A π ( s , a ) = Q π ( s , a ) − V π ( s ) , V π ( s ) = a ∑ π ( a ∣ s ) Q π ( s , a ) 따라서:
∑ a π ( a ∣ s ) A π ( s , a ) = ∑ a π ( a ∣ s ) [ Q π ( s , a ) − V π ( s ) ] = V π ( s ) − V π ( s ) = 0 \sum_a \pi(a|s) A_\pi(s,a) = \sum_a \pi(a|s) [Q_\pi(s,a) - V_\pi(s)] = V_\pi(s) - V_\pi(s) = 0 a ∑ π ( a ∣ s ) A π ( s , a ) = a ∑ π ( a ∣ s ) [ Q π ( s , a ) − V π ( s ) ] = V π ( s ) − V π ( s ) = 0 즉,
L π ( π ) = η ( π ) L_\pi(\pi) = \eta(\pi) L π ( π ) = η ( π ) 다음으로 1계 미분항을 살펴봅시다.
∇ π ′ L π ( π ′ ) = ∑ s ρ π ( s ) ∑ a ∇ π ′ π ′ ( a ∣ s ) ⋅ A π ( s , a ) (1) \nabla_{\pi'} L_\pi(\pi') = \sum_s \rho_\pi(s) \sum_a \nabla_{\pi'} \pi'(a|s) \cdot A_\pi(s,a) \tag{1} ∇ π ′ L π ( π ′ ) = s ∑ ρ π ( s ) a ∑ ∇ π ′ π ′ ( a ∣ s ) ⋅ A π ( s , a ) ( 1 ) 해당 미분을 π ′ = π \pi' = \pi π ′ = π
∇ π ′ L π ( π ′ ) ∣ π ′ = π = ∑ s ρ π ( s ) ∑ a ∇ π ′ π ′ ( a ∣ s ) ⋅ A π ( s , a ) ∣ π ′ = π (2) \nabla_{\pi'} L_\pi(\pi')\Big|_{\pi' = \pi} = \sum_s \rho_\pi(s) \sum_a \nabla_{\pi'} \pi'(a|s) \cdot A_\pi(s,a)\Big|_{\pi' = \pi} \tag{2} ∇ π ′ L π ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π = s ∑ ρ π ( s ) a ∑ ∇ π ′ π ′ ( a ∣ s ) ⋅ A π ( s , a ) ∣ ∣ ∣ ∣ π ′ = π ( 2 ) Q π = A π + V π Q_\pi = A_\pi + V_\pi Q π = A π + V π
∇ π ′ η ( π ′ ) ∣ π ′ = π = ∑ s ρ π ( s ) ∑ a ∇ π ′ π ( a ∣ s ) [ A π ( s , a ) + V π ( s ) ] \nabla_{\pi'} \eta(\pi') \Big|_{\pi' = \pi} = \sum_s \rho_\pi(s) \sum_a \nabla_{\pi'} \pi(a|s) [A_\pi(s,a) + V_\pi(s)] ∇ π ′ η ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π = s ∑ ρ π ( s ) a ∑ ∇ π ′ π ( a ∣ s ) [ A π ( s , a ) + V π ( s ) ] V π ( s ) V_\pi(s) V π ( s )
∑ a ∇ π ′ π ( a ∣ s ) V π ( s ) = V π ( s ) ⋅ ∇ π ′ ∑ a π ( a ∣ s ) = V π ( s ) ⋅ ∇ π ′ 1 = 0 \sum_a \nabla_{\pi'} \pi(a|s) V_\pi(s) = V_\pi(s) \cdot \nabla_{\pi'} \sum_a \pi(a|s) = V_\pi(s) \cdot \nabla_{\pi'} 1 = 0 a ∑ ∇ π ′ π ( a ∣ s ) V π ( s ) = V π ( s ) ⋅ ∇ π ′ a ∑ π ( a ∣ s ) = V π ( s ) ⋅ ∇ π ′ 1 = 0 따라서
∇ π ′ η ( π ′ ) ∣ π ′ = π = ∑ s ρ π ( s ) ∑ a ∇ π ′ π ( a ∣ s ) A π ( s , a ) (5) \nabla_{\pi'} \eta(\pi') \Big|_{\pi' = \pi} = \sum_s \rho_\pi(s) \sum_a \nabla_{\pi'} \pi(a|s) A_\pi(s,a) \tag{5} ∇ π ′ η ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π = s ∑ ρ π ( s ) a ∑ ∇ π ′ π ( a ∣ s ) A π ( s , a ) ( 5 ) 한편,
∇ π ′ η ( π ′ ) = ∑ s ρ π ′ ( s ) ∑ a ∇ π ′ π ′ ( a ∣ s ) ⋅ Q π ( s , a ) (3) \nabla_{\pi'} \eta(\pi') = \sum_s \rho_{\pi'}(s) \sum_a \nabla_{\pi'} \pi'(a|s) \cdot Q_\pi(s,a) \tag{3} ∇ π ′ η ( π ′ ) = s ∑ ρ π ′ ( s ) a ∑ ∇ π ′ π ′ ( a ∣ s ) ⋅ Q π ( s , a ) ( 3 ) 즉,
∇ π ′ L π ( π ′ ) ∣ π ′ = π = ∇ π ′ η ( π ′ ) ∣ π ′ = π \nabla_{\pi'} L_\pi(\pi') \Big|_{\pi' = \pi} = \nabla_{\pi'} \eta(\pi') \Big|_{\pi' = \pi} ∇ π ′ L π ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π = ∇ π ′ η ( π ′ ) ∣ ∣ ∣ ∣ π ′ = π STEP 7: Importance Sampling
E π ′ [ f ( s , a ) ] = E π [ π ′ ( a ∣ s ) π ( a ∣ s ) f ( s , a ) ] \mathbb{E}_{\pi'}[f(s,a)] = \mathbb{E}_{\pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} f(s,a) \right] E π ′ [ f ( s , a ) ] = E π [ π ( a ∣ s ) π ′ ( a ∣ s ) f ( s , a ) ]
기대값을 샘플링 가능한 분포 로 바꾸기 위한 테크닉입니다.
증명
물론, 다음과 같은 가정이 필요합니다.
π ( a ∣ s ) > 0 \pi(a|s) > 0 π ( a ∣ s ) > 0 π ′ ( a ∣ s ) \pi'(a|s) π ′ ( a ∣ s ) f ( s , a ) f(s,a) f ( s , a )
좌변:
E a ∼ π ′ [ f ( s , a ) ] = ∑ a π ′ ( a ∣ s ) f ( s , a ) \mathbb{E}_{a \sim \pi'} [f(s,a)] = \sum_a \pi'(a|s) f(s,a) E a ∼ π ′ [ f ( s , a ) ] = a ∑ π ′ ( a ∣ s ) f ( s , a ) 우변:
E a ∼ π [ π ′ ( a ∣ s ) π ( a ∣ s ) f ( s , a ) ] = ∑ a π ( a ∣ s ) ⋅ π ′ ( a ∣ s ) π ( a ∣ s ) f ( s , a ) = ∑ a π ′ ( a ∣ s ) f ( s , a ) \mathbb{E}_{a \sim \pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} f(s,a) \right] = \sum_a \pi(a|s) \cdot \frac{\pi'(a|s)}{\pi(a|s)} f(s,a) = \sum_a \pi'(a|s) f(s,a) E a ∼ π [ π ( a ∣ s ) π ′ ( a ∣ s ) f ( s , a ) ] = a ∑ π ( a ∣ s ) ⋅ π ( a ∣ s ) π ′ ( a ∣ s ) f ( s , a ) = a ∑ π ′ ( a ∣ s ) f ( s , a ) E a ∼ π ′ [ f ( s , a ) ] = E a ∼ π [ π ′ ( a ∣ s ) π ( a ∣ s ) f ( s , a ) ] \boxed{ \mathbb{E}_{a \sim \pi'} [f(s,a)] = \mathbb{E}_{a \sim \pi} \left[ \frac{\pi'(a|s)}{\pi(a|s)} f(s,a) \right] } E a ∼ π ′ [ f ( s , a ) ] = E a ∼ π [ π ( a ∣ s ) π ′ ( a ∣ s ) f ( s , a ) ] 따라서 Importance Sampling은 원래 분포 π ′ \pi' π ′ π \pi π π ′ π \frac{\pi'}{\pi} π π ′
STEP 8: State Visitation Difference Bound
정책 π , π ′ \pi, \pi' π , π ′ D T V max ( π , π ′ ) D_{TV}^{\max}(\pi, \pi') D T V m a x ( π , π ′ )
D T V max ( π , π ′ ) : = max s D T V ( π ( ⋅ ∣ s ) , π ′ ( ⋅ ∣ s ) ) = 1 2 max s ∑ a ∣ π ( a ∣ s ) − π ′ ( a ∣ s ) ∣ D_{TV}^{\max}(\pi, \pi') := \max_s D_{TV}(\pi(\cdot|s), \pi'(\cdot|s)) = \frac{1}{2} \max_s \sum_a |\pi(a|s) - \pi'(a|s)| D T V m a x ( π , π ′ ) : = s max D T V ( π ( ⋅ ∣ s ) , π ′ ( ⋅ ∣ s ) ) = 2 1 s max a ∑ ∣ π ( a ∣ s ) − π ′ ( a ∣ s ) ∣ 그렇다면 두 정책의 Discounted State Visitation Distribution ρ π ( s ) \rho_{\pi}(s) ρ π ( s ) ρ π ′ ( s ) \rho_{\pi'}(s) ρ π ′ ( s ) ℓ 1 \ell_1 ℓ 1
∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ 2 γ ( 1 − γ ) 2 D T V max ( π , π ′ ) 2 \boxed{ \sum_s |\rho_{\pi'}(s) - \rho_\pi(s)| \le \frac{2 \gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi')^2 } s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ ( 1 − γ ) 2 2 γ D T V m a x ( π , π ′ ) 2 증명
각 정책의 상태 방문 분포는 다음과 같이 정의(normalized version)됩니다:
ρ π ( s ) = ( 1 − γ ) ∑ t = 0 ∞ γ t d t π ( s ) , where d t π ( s ) : = P ( s t = s ∣ π ) \rho_\pi(s) = (1 - \gamma) \sum_{t=0}^\infty \gamma^t d_t^\pi(s), \quad \text{where } d_t^\pi(s) := P(s_t = s \mid \pi) ρ π ( s ) = ( 1 − γ ) t = 0 ∑ ∞ γ t d t π ( s ) , where d t π ( s ) : = P ( s t = s ∣ π ) 이로부터 ℓ 1 \ell_1 ℓ 1
∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ = ( 1 − γ ) ∑ t = 0 ∞ γ t ⋅ δ t with δ t : = ∑ s ∣ d t π ′ ( s ) − d t π ( s ) ∣ \sum_s |\rho_{\pi'}(s) - \rho_\pi(s)| = (1 - \gamma) \sum_{t=0}^\infty \gamma^t \cdot \delta_t \quad \text{with } \delta_t := \sum_s |d_t^{\pi'}(s) - d_t^\pi(s)| s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ = ( 1 − γ ) t = 0 ∑ ∞ γ t ⋅ δ t with δ t : = s ∑ ∣ d t π ′ ( s ) − d t π ( s ) ∣ 한편, 재귀적 특성에 의해 d t + 1 π ( s ′ ) d_{t+1}^\pi(s') d t + 1 π ( s ′ )
d t + 1 π ( s ′ ) = ∑ s , a d t π ( s ) π ( a ∣ s ) P ( s ′ ∣ s , a ) d_{t+1}^\pi(s') = \sum_{s,a} d_t^\pi(s) \pi(a|s) P(s'|s,a) d t + 1 π ( s ′ ) = s , a ∑ d t π ( s ) π ( a ∣ s ) P ( s ′ ∣ s , a ) 이제 d t + 1 π ′ ( s ′ ) − d t + 1 π ( s ′ ) d_{t+1}^{\pi'}(s') - d_{t+1}^{\pi}(s') d t + 1 π ′ ( s ′ ) − d t + 1 π ( s ′ )
d t + 1 π ′ ( s ′ ) − d t + 1 π ( s ′ ) = ∑ s , a [ d t π ′ ( s ) π ′ ( a ∣ s ) − d t π ( s ) π ( a ∣ s ) ] P ( s ′ ∣ s , a ) = ∑ s , a [ ( d t π ′ ( s ) − d t π ( s ) ) π ′ ( a ∣ s ) + d t π ( s ) ( π ′ ( a ∣ s ) − π ( a ∣ s ) ) ] P ( s ′ ∣ s , a ) \begin{aligned} d_{t+1}^{\pi'}(s') - d_{t+1}^{\pi}(s') &= \sum_{s,a} \left[ d_t^{\pi'}(s)\pi'(a|s) - d_t^\pi(s)\pi(a|s) \right] P(s'|s,a) \\ &= \sum_{s,a} \left[ (d_t^{\pi'}(s) - d_t^\pi(s)) \pi'(a|s) + d_t^\pi(s)(\pi'(a|s) - \pi(a|s)) \right] P(s'|s,a) \end{aligned} d t + 1 π ′ ( s ′ ) − d t + 1 π ( s ′ ) = s , a ∑ [ d t π ′ ( s ) π ′ ( a ∣ s ) − d t π ( s ) π ( a ∣ s ) ] P ( s ′ ∣ s , a ) = s , a ∑ [ ( d t π ′ ( s ) − d t π ( s ) ) π ′ ( a ∣ s ) + d t π ( s ) ( π ′ ( a ∣ s ) − π ( a ∣ s ) ) ] P ( s ′ ∣ s , a ) 절댓값 합을 취한 후 triangle inequality 적용:
δ t + 1 : = ∑ s ′ ∣ d t + 1 π ′ ( s ′ ) − d t + 1 π ( s ′ ) ∣ ≤ ∑ s ∣ d t π ′ ( s ) − d t π ( s ) ∣ + 2 D T V max ( π , π ′ ) \delta_{t+1} := \sum_{s'} |d_{t+1}^{\pi'}(s') - d_{t+1}^\pi(s')| \le \sum_s |d_t^{\pi'}(s) - d_t^\pi(s)| + 2 D_{TV}^{\max}(\pi, \pi') δ t + 1 : = s ′ ∑ ∣ d t + 1 π ′ ( s ′ ) − d t + 1 π ( s ′ ) ∣ ≤ s ∑ ∣ d t π ′ ( s ) − d t π ( s ) ∣ + 2 D T V m a x ( π , π ′ ) 초기 조건 δ 0 = 0 \delta_0 = 0 δ 0 = 0
δ t ≤ 2 t ⋅ D T V max ( π , π ′ ) \delta_t \le 2t \cdot D_{TV}^{\max}(\pi, \pi') δ t ≤ 2 t ⋅ D T V m a x ( π , π ′ ) 위의 도출된 식들을 대입하면:
∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ ( 1 − γ ) ∑ t = 0 ∞ γ t ⋅ 2 t D T V max ( π , π ′ ) = 2 D T V max ( π , π ′ ) ⋅ ( 1 − γ ) ∑ t = 0 ∞ t γ t \sum_s |\rho_{\pi'}(s) - \rho_\pi(s)| \le (1 - \gamma) \sum_{t=0}^\infty \gamma^t \cdot 2t D_{TV}^{\max}(\pi, \pi') = 2 D_{TV}^{\max}(\pi, \pi') \cdot (1 - \gamma) \sum_{t=0}^\infty t \gamma^t s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ ( 1 − γ ) t = 0 ∑ ∞ γ t ⋅ 2 t D T V m a x ( π , π ′ ) = 2 D T V m a x ( π , π ′ ) ⋅ ( 1 − γ ) t = 0 ∑ ∞ t γ t 다음 합 공식을 사용:
∑ t = 0 ∞ t γ t = γ ( 1 − γ ) 2 \sum_{t=0}^\infty t \gamma^t = \frac{\gamma}{(1 - \gamma)^2} t = 0 ∑ ∞ t γ t = ( 1 − γ ) 2 γ 따라서:
∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ 2 γ ( 1 − γ ) 2 D T V max ( π , π ′ ) \sum_s |\rho_{\pi'}(s) - \rho_\pi(s)| \le \frac{2\gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi') s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ ( 1 − γ ) 2 2 γ D T V m a x ( π , π ′ ) TRPO 본문에서는 이를 보수적으로 다음과 같이 제곱하여 사용합니다:
∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ 2 γ ( 1 − γ ) 2 D T V max ( π , π ′ ) 2 \sum_s |\rho_{\pi'}(s) - \rho_\pi(s)| \le \frac{2\gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi')^2 s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ ( 1 − γ ) 2 2 γ D T V m a x ( π , π ′ ) 2 이는 D T V max ( π , π ′ ) ∈ [ 0 , 1 ] D_{TV}^{\max}(\pi, \pi') \in [0,1] D T V m a x ( π , π ′ ) ∈ [ 0 , 1 ] D T V max ( π , π ′ ) ≤ D T V max ( π , π ′ ) 2 D_{TV}^{\max}(\pi, \pi') \le D_{TV}^{\max}(\pi, \pi')^2 D T V m a x ( π , π ′ ) ≤ D T V m a x ( π , π ′ ) 2
STEP 9: Policy Improvement Bound (Theorem 2)
η ( π ′ ) ≥ L π ( π ′ ) − 2 ϵ γ ( 1 − γ ) 2 D T V max ( π , π ′ ) 2 \eta(\pi') \ge L_\pi(\pi') - \frac{2 \epsilon \gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi')^2 η ( π ′ ) ≥ L π ( π ′ ) − ( 1 − γ ) 2 2 ϵ γ D T V m a x ( π , π ′ ) 2
surrogate objective와 실제 성능 차이를 이론적으로 bound할 수 있습니다.
증명
Performance Difference Lemma에 의해
η ( π ′ ) = η ( π ) + ∑ s ρ π ′ ( s ) ∑ a π ′ ( a ∣ s ) A π ( s , a ) \eta(\pi') = \eta(\pi) + \sum_s \rho_{\pi'}(s) \sum_a \pi'(a|s) A_\pi(s,a) η ( π ′ ) = η ( π ) + s ∑ ρ π ′ ( s ) a ∑ π ′ ( a ∣ s ) A π ( s , a ) Surrogate Objective는 다음과 같이 정의 했으므로
L π ( π ′ ) = η ( π ) + ∑ s ρ π ( s ) ∑ a π ′ ( a ∣ s ) A π ( s , a ) L_\pi(\pi') = \eta(\pi) + \sum_s \rho_\pi(s) \sum_a \pi'(a|s) A_\pi(s,a) L π ( π ′ ) = η ( π ) + s ∑ ρ π ( s ) a ∑ π ′ ( a ∣ s ) A π ( s , a ) 이 둘의 차이를 취하면:
η ( π ′ ) − L π ( π ′ ) = ∑ s ( ρ π ′ ( s ) − ρ π ( s ) ) ∑ a π ′ ( a ∣ s ) A π ( s , a ) \eta(\pi') - L_\pi(\pi') = \sum_s \left( \rho_{\pi'}(s) - \rho_\pi(s) \right) \sum_a \pi'(a|s) A_\pi(s,a) η ( π ′ ) − L π ( π ′ ) = s ∑ ( ρ π ′ ( s ) − ρ π ( s ) ) a ∑ π ′ ( a ∣ s ) A π ( s , a ) 이제 오른쪽 항을 upper bound 해보면
∣ η ( π ′ ) − L π ( π ′ ) ∣ = ∣ ∑ s ( ρ π ′ ( s ) − ρ π ( s ) ) ∑ a π ′ ( a ∣ s ) A π ( s , a ) ∣ \left| \eta(\pi') - L_\pi(\pi') \right| = \left| \sum_s \left( \rho_{\pi'}(s) - \rho_\pi(s) \right) \sum_a \pi'(a|s) A_\pi(s,a) \right| ∣ η ( π ′ ) − L π ( π ′ ) ∣ = ∣ ∣ ∣ ∣ ∣ ∣ s ∑ ( ρ π ′ ( s ) − ρ π ( s ) ) a ∑ π ′ ( a ∣ s ) A π ( s , a ) ∣ ∣ ∣ ∣ ∣ ∣ triangle inequality에 의해
≤ ∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ⋅ ∣ ∑ a π ′ ( a ∣ s ) A π ( s , a ) ∣ \le \sum_s \left| \rho_{\pi'}(s) - \rho_\pi(s) \right| \cdot \left| \sum_a \pi'(a|s) A_\pi(s,a) \right| ≤ s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ⋅ ∣ ∣ ∣ ∣ ∣ ∣ a ∑ π ′ ( a ∣ s ) A π ( s , a ) ∣ ∣ ∣ ∣ ∣ ∣ 또,
∣ ∑ a π ′ ( a ∣ s ) A π ( s , a ) ∣ ≤ ∑ a π ′ ( a ∣ s ) ∣ A π ( s , a ) ∣ ≤ ϵ ∑ a π ′ ( a ∣ s ) = ϵ \left| \sum_a \pi'(a|s) A_\pi(s,a) \right| \le \sum_a \pi'(a|s) |A_\pi(s,a)| \le \epsilon \sum_a \pi'(a|s) = \epsilon ∣ ∣ ∣ ∣ ∣ ∣ a ∑ π ′ ( a ∣ s ) A π ( s , a ) ∣ ∣ ∣ ∣ ∣ ∣ ≤ a ∑ π ′ ( a ∣ s ) ∣ A π ( s , a ) ∣ ≤ ϵ a ∑ π ′ ( a ∣ s ) = ϵ 따라서:
∣ η ( π ′ ) − L π ( π ′ ) ∣ ≤ ϵ ∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ \left| \eta(\pi') - L_\pi(\pi') \right| \le \epsilon \sum_s \left| \rho_{\pi'}(s) - \rho_\pi(s) \right| ∣ η ( π ′ ) − L π ( π ′ ) ∣ ≤ ϵ s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ State visitation difference bound에 의해
∑ s ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ 2 γ ( 1 − γ ) 2 D T V max ( π , π ′ ) 2 \sum_s \left| \rho_{\pi'}(s) - \rho_\pi(s) \right| \le \frac{2 \gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi')^2 s ∑ ∣ ρ π ′ ( s ) − ρ π ( s ) ∣ ≤ ( 1 − γ ) 2 2 γ D T V m a x ( π , π ′ ) 2 이를 이용해 다음이 성립합니다.
∣ η ( π ′ ) − L π ( π ′ ) ∣ ≤ ϵ ⋅ 2 γ ( 1 − γ ) 2 D T V max ( π , π ′ ) 2 \left| \eta(\pi') - L_\pi(\pi') \right| \le \epsilon \cdot \frac{2 \gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi')^2 ∣ η ( π ′ ) − L π ( π ′ ) ∣ ≤ ϵ ⋅ ( 1 − γ ) 2 2 γ D T V m a x ( π , π ′ ) 2 즉,
η ( π ′ ) ≥ L π ( π ′ ) − 2 ϵ γ ( 1 − γ ) 2 D T V max ( π , π ′ ) 2 \eta(\pi') \ge L_\pi(\pi') - \frac{2 \epsilon \gamma}{(1 - \gamma)^2} D_{TV}^{\max}(\pi, \pi')^2 η ( π ′ ) ≥ L π ( π ′ ) − ( 1 − γ ) 2 2 ϵ γ D T V m a x ( π , π ′ ) 2 STEP 10: Pinsker's Inequality로 KL bound
D T V ( p , q ) 2 ≤ 1 2 D K L ( p ∥ q ) \boxed{ D_{TV}(p, q)^2 \le \frac{1}{2} D_{KL}(p \| q) } D T V ( p , q ) 2 ≤ 2 1 D K L ( p ∥ q ) 이 부등식은 TRPO의 trust region 조건을 KL divergence로 정당화하는 데 핵심적인 역할을 합니다.
증명 (sketch, 실제론 3~5 pg 분량, 나중에 따로 다루겠습니다!)
Pinsker’s inequality는 Csiszár–Kullback–Pinsker inequality 의 특수한 경우이며, f f f
Csiszár–Kullback–Pinsker inequality에 따르면 다음이 성립합니다:
D T V ( p , q ) ≤ 1 2 D K L ( p ∥ q ) ⇒ D T V ( p , q ) 2 ≤ 1 2 D K L ( p ∥ q ) D_{TV}(p, q) \le \sqrt{ \frac{1}{2} D_{KL}(p \| q) } \Rightarrow D_{TV}(p, q)^2 \le \frac{1}{2} D_{KL}(p \| q) \quad D T V ( p , q ) ≤ 2 1 D K L ( p ∥ q ) ⇒ D T V ( p , q ) 2 ≤ 2 1 D K L ( p ∥ q )
이 부등식은 TRPO의 trust region 조건 을 KL 제약으로 바꾸는 정당성의 이론적 근거입니다.
실제로는 이 bound가 너무 loose할 수 있으므로 practical TRPO 구현에서는 surrogate loss에 KL penalty를 직접 넣거나, Lagrange multiplier로 최적화합니다.
STEP 11: TRPO 최적화 문제 정의
max θ L π ( π θ ) s.t. D ˉ K L ρ π ( π ∥ π θ ) ≤ δ \boxed{ \max_\theta L_\pi(\pi_\theta) \quad \text{s.t. } \bar{D}_{KL}^{\rho_\pi}(\pi \| \pi_\theta) \le \delta } θ max L π ( π θ ) s.t. D ˉ K L ρ π ( π ∥ π θ ) ≤ δ 배경
Performance difference lemma :
η ( π θ ) − η ( π ) = ∑ s ρ π θ ( s ) ∑ a π θ ( a ∣ s ) A π ( s , a ) \eta(\pi_\theta) - \eta(\pi) = \sum_s \rho_{\pi_\theta}(s) \sum_a \pi_\theta(a|s) A_\pi(s, a) η ( π θ ) − η ( π ) = s ∑ ρ π θ ( s ) a ∑ π θ ( a ∣ s ) A π ( s , a )
Surrogate Objective
η ( π θ ) ≈ L π ( π θ ) \eta(\pi_\theta) \approx L_\pi(\pi_\theta) η ( π θ ) ≈ L π ( π θ )
Pinsker’s inequality 로 이 근사의 오차를 KL로 bound:
∣ η ( π θ ) − L π ( π θ ) ∣ ≤ O ( D K L ) |\eta(\pi_\theta) - L_\pi(\pi_\theta)| \le \mathcal{O}(D_{KL}) ∣ η ( π θ ) − L π ( π θ ) ∣ ≤ O ( D K L )
⇒ 신뢰 구간 내에서만 근사를 믿을 수 있음
STEP 12: Natural Policy Gradient
∇ ~ θ J ( θ ) = F − 1 ∇ θ J ( θ ) \boxed{ \tilde{\nabla}_\theta J(\theta) = F^{-1} \nabla_\theta J(\theta) } ∇ ~ θ J ( θ ) = F − 1 ∇ θ J ( θ ) 증명
max θ ′ J ( θ ′ ) ≈ J ( θ ) + ∇ θ J ( θ ) T ( θ ′ − θ ) s.t. D ˉ K L ρ π ( π θ ∥ π θ ′ ) ≤ δ \begin{aligned} \max_{\theta'}\quad & J(\theta') \approx J(\theta) + \nabla_\theta J(\theta)^T (\theta' - \theta) \\ \text{s.t.}\quad & \bar{D}_{KL}^{\rho_\pi}(\pi_\theta \| \pi_{\theta'}) \le \delta \end{aligned} θ ′ max s.t. J ( θ ′ ) ≈ J ( θ ) + ∇ θ J ( θ ) T ( θ ′ − θ ) D ˉ K L ρ π ( π θ ∥ π θ ′ ) ≤ δ KL-divergence를 활용해 2차 근사를 하면 (θ ′ \theta' θ ′
D ˉ K L ( π θ ∥ π θ ′ ) ≈ 1 2 ( θ ′ − θ ) T F ( θ ′ − θ ) (1) \bar{D}_{KL}(\pi_\theta \| \pi_{\theta'}) \approx \frac{1}{2} (\theta' - \theta)^T F (\theta' - \theta) \tag{1} D ˉ K L ( π θ ∥ π θ ′ ) ≈ 2 1 ( θ ′ − θ ) T F ( θ ′ − θ ) ( 1 ) F F F
F : = E s ∼ ρ π , a ∼ π θ [ ∇ θ log π θ ( a ∣ s ) ∇ θ log π θ ( a ∣ s ) T ] F := \mathbb{E}_{s \sim \rho_\pi, a \sim \pi_\theta} \left[ \nabla_\theta \log \pi_\theta(a|s) \nabla_\theta \log \pi_\theta(a|s)^T \right] F : = E s ∼ ρ π , a ∼ π θ [ ∇ θ log π θ ( a ∣ s ) ∇ θ log π θ ( a ∣ s ) T ] 목적함수와 제약조건을 이용한 라그랑지안을 구해봅니다.
L ( θ ′ ) = ∇ θ J ( θ ) T ( θ ′ − θ ) − λ ⋅ 1 2 ( θ ′ − θ ) T F ( θ ′ − θ ) \mathcal{L}(\theta') = \nabla_\theta J(\theta)^T (\theta' - \theta) - \lambda \cdot \frac{1}{2} (\theta' - \theta)^T F (\theta' - \theta) L ( θ ′ ) = ∇ θ J ( θ ) T ( θ ′ − θ ) − λ ⋅ 2 1 ( θ ′ − θ ) T F ( θ ′ − θ ) Convex optimization 문제의 Stationary Condition을 적용하면,
∇ θ ′ L = ∇ θ J ( θ ) − λ F ( θ ′ − θ ) = 0 ⇒ θ ′ − θ = 1 λ F − 1 ∇ θ J ( θ ) \nabla_{\theta'} \mathcal{L} = \nabla_\theta J(\theta) - \lambda F (\theta' - \theta) = 0 \Rightarrow \theta' - \theta = \frac{1}{\lambda} F^{-1} \nabla_\theta J(\theta) ∇ θ ′ L = ∇ θ J ( θ ) − λ F ( θ ′ − θ ) = 0 ⇒ θ ′ − θ = λ 1 F − 1 ∇ θ J ( θ ) 즉,
∇ ~ θ J ( θ ) : = F − 1 ∇ θ J ( θ ) ■ \boxed{ \tilde{\nabla}_\theta J(\theta) := F^{-1} \nabla_\theta J(\theta) } \quad \blacksquare ∇ ~ θ J ( θ ) : = F − 1 ∇ θ J ( θ ) ■ KL-divergence는 확률 분포의 공간에 Riemannian metric을 부여하며, 이로 인해 정책 파라미터 공간은 단순한 유클리드 공간이 아닌 정보 기하학적 곡률을 지닌 공간으로 해석됩니다. 이러한 구조 하에서 가장 빠른 성능 향상을 보장하는 최적 상승 방향은 일반적인 Euclidean gradient가 아니라, 분포 간의 거리(정보 기하학적 구조)를 반영한 방향인 Natural Gradient입니다. 즉, 일반 gradient는 평탄한 공간(Euclidean geometry)을 가정하는 반면, Natural Gradient는 확률 분포 사이의 변화에 민감한 방향을 따름으로써 보다 효율적이고 안정적인 최적화를 가능하게 합니다.
