아래의 내용은 세종대학교 박성수 교수님께서 쓰신 수학으로 풀어보는 강화학습 원리와 알고리즘 책의 3장의 내용을 표기법만 달리해서 정리한 내용입니다. 책의 전개와 설명이 좋아서 강화학습에 관심있는 분들은 꼭 구입하셔서 읽어보길 바랍니다.
강화학습의 목표: 누적 보상을 최대화하는 최적 정책(optimal policy)를 구하는 것
누적보상: J J J
t t t s s s a a a s t , a t s_t, a_t s t , a t t t t r ( s t , a t ) r(s_t, a_t) r ( s t , a t ) 정책: π ( a t ∣ s t ) \pi(a_t | s_t) π ( a t ∣ s t )
감가율: γ \gamma γ
목적함수 만약 정책이 θ \theta θ π θ ( a t ∣ s t ) \pi_\theta(a_t|s_t) π θ ( a t ∣ s t ) θ \theta θ θ \theta θ
θ ∗ = arg max θ J ( θ ) J ( θ ) = E τ ∼ p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] \theta^*= \argmax_\theta J(\theta) \\ J(\theta) = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] θ ∗ = θ a r g m a x J ( θ ) J ( θ ) = E τ ∼ p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] 여기서 p θ ( τ ) p_\theta(\tau) p θ ( τ ) π θ ( a t ∣ s t ) \pi_\theta(a_t|s_t) π θ ( a t ∣ s t ) τ \tau τ π θ ( a t ∣ s t ) \pi_\theta(a_t|s_t) π θ ( a t ∣ s t ) a t a_t a t π θ ( a t ∣ s t ) \pi_\theta(a_t|s_t) π θ ( a t ∣ s t ) ( p ( s t + 1 ∣ s t , a t ) ) (p(s_{t+1}|s_t, a_t)) ( p ( s t + 1 ∣ s t , a t ) ) θ \theta θ
τ = ( s 0 , a 0 , s 1 , a 1 , … , s T , a T ) ∼ p θ ( τ ) \tau = (s_0, a_0, s_1, a_1, \dots, s_T, a_T) \sim p_\theta(\tau) τ = ( s 0 , a 0 , s 1 , a 1 , … , s T , a T ) ∼ p θ ( τ ) 궤적의 확률밀도함수는 복잡한 결합확률밀도함수로 앞서 가정한 마르코프 가정을 사용하여 간편한 형태로 분해할 수 있다.
p θ ( τ ) = p θ ( s 0 , a 0 , s 1 , a 1 , … , s T , a T ) = p ( s 0 ) π θ ( a 0 , s 1 , a 1 , … , s T , a T ∣ s 0 ) = p ( s 0 ) π θ ( a 0 ∣ s 0 ) p ( s 1 ∣ s 0 , a 0 ) π θ ( a 1 ∣ s 0 , a 0 , s 1 ) p ( s 2 ∣ s 0 , a 0 , s 1 , a 1 ) ⋯ = p ( s 0 ) π θ ( a 0 ∣ s 0 ) p ( s 1 ∣ s 0 , a 0 ) π θ ( a 1 ∣ s 1 ) p ( s 2 ∣ s 1 , a 1 ) ⋯ ( ∵ M a r k o v a s s u m p t i o n ) = p ( s 0 ) ∏ t = 0 T π θ ( a t ∣ s t ) p ( s t + 1 ∣ s t , a t ) \begin{aligned} p_\theta (\tau) &= p_\theta (s_0, a_0, s_1, a_1, \dots, s_T, a_T) \\ &= p(s_0) \pi_\theta(a_0, s_1, a_1, \dots, s_T, a_T | s_0) \\ &= p(s_0) \pi_\theta(a_0|s_0)p(s_1 | s_0, a_0)\pi_\theta(a_1|s_0, a_0, s_1)p(s_2|s_0, a_0, s_1, a_1) \cdots \\ &= p(s_0) \pi_\theta(a_0|s_0)p(s_1 | s_0, a_0) \pi_\theta(a_1|s_1) p(s_2|s_1, a_1) \cdots (\because Markov ~ assumption) \\ & = p(s_0) \prod_{t=0}^T \pi_\theta(a_t|s_t) p(s_{t+1}|s_t, a_t) \end{aligned} p θ ( τ ) = p θ ( s 0 , a 0 , s 1 , a 1 , … , s T , a T ) = p ( s 0 ) π θ ( a 0 , s 1 , a 1 , … , s T , a T ∣ s 0 ) = p ( s 0 ) π θ ( a 0 ∣ s 0 ) p ( s 1 ∣ s 0 , a 0 ) π θ ( a 1 ∣ s 0 , a 0 , s 1 ) p ( s 2 ∣ s 0 , a 0 , s 1 , a 1 ) ⋯ = p ( s 0 ) π θ ( a 0 ∣ s 0 ) p ( s 1 ∣ s 0 , a 0 ) π θ ( a 1 ∣ s 1 ) p ( s 2 ∣ s 1 , a 1 ) ⋯ ( ∵ M a r k o v a s s u m p t i o n ) = p ( s 0 ) t = 0 ∏ T π θ ( a t ∣ s t ) p ( s t + 1 ∣ s t , a t ) 위의 표기에서 확률이 θ \theta θ
J ( θ ) = E τ ∼ p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] J(\theta) = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] J ( θ ) = E τ ∼ p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] 를 다시 τ = ( s 0 , a 0 , s 1 , … , s T , a T ) = ( s 0 ) ∪ ( a 0 , s 1 , … , s T , a T ) \tau = (s_0, a_0, s_1, \dots, s_T, a_T) = (s_0) \cup (a_0, s_1, \dots, s_T, a_T) τ = ( s 0 , a 0 , s 1 , … , s T , a T ) = ( s 0 ) ∪ ( a 0 , s 1 , … , s T , a T )
J ( θ ) = ∫ s 0 ∫ τ a 0 : a T [ ∑ t = 0 T γ t r ( s t , a t ) ] p ( s 0 ) p θ ( τ a 0 : a T ∣ s 0 ) d τ a 0 : a T d s 0 = ∫ s 0 ∫ τ a 0 : a T [ ∑ t = 0 T γ t r ( s t , a t ) ] p θ ( τ a 0 : a T ∣ s 0 ) d τ a 0 : a T ⏟ V π θ ( s 0 ) p ( s 0 ) d s 0 = ∫ s 0 V π θ ( s 0 ) p ( s 0 ) d s 0 = E s 0 ∼ p ( s 0 ) [ V π θ ( s 0 ) ] \begin{aligned} J(\theta) &= \int_{s_0} \int_{\tau_{a_0:a_T}} \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] p(s_0) p_\theta(\tau_{a_0:a_T}|s_0) d\tau_{a_0:a_T} d s_0\\ &= \int_{s_0} \underbrace{\int_{\tau_{a_0:a_T}} \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] p_\theta(\tau_{a_0:a_T}|s_0) d\tau_{a_0:a_T}}_{V^{\pi_\theta}(s_0)} p(s_0) d s_0 \\ &= \int_{s_0} V^{\pi_\theta}(s_0) p(s_0) d s_0 = \mathbb{E}_{s_0 \sim p(s_0)} [V^{\pi_\theta}(s_0)] \end{aligned} J ( θ ) = ∫ s 0 ∫ τ a 0 : a T [ t = 0 ∑ T γ t r ( s t , a t ) ] p ( s 0 ) p θ ( τ a 0 : a T ∣ s 0 ) d τ a 0 : a T d s 0 = ∫ s 0 V π θ ( s 0 ) ∫ τ a 0 : a T [ t = 0 ∑ T γ t r ( s t , a t ) ] p θ ( τ a 0 : a T ∣ s 0 ) d τ a 0 : a T p ( s 0 ) d s 0 = ∫ s 0 V π θ ( s 0 ) p ( s 0 ) d s 0 = E s 0 ∼ p ( s 0 ) [ V π θ ( s 0 ) ] 목적함수 J ( θ ) J(\theta) J ( θ ) s 0 s_0 s 0 V π θ ( s 0 ) V^{\pi_\theta} (s_0) V π θ ( s 0 )
정책 그래디언트 목적함수를 최대 혹은 최소화하는 파라미터를 찾는 문제에서 그래디언트(gradient)를 계산한 경사하강법을 사용한다. 따라서, 목적함수에 대한 그레디언트를 유도해보자.
∂ J ( θ ) ∂ θ = ∇ θ J ( θ ) = ∇ θ ∫ τ p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ = ∫ τ ∇ θ p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) p θ ( τ ) ∇ θ p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) ∇ θ p θ ( τ ) p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) ∇ θ log p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ \begin{aligned} \frac{\partial J(\theta)}{\partial \theta} &= \nabla_\theta J(\theta) = \nabla_\theta \int_\tau p_\theta(\tau) \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \\ &= \int_\tau \nabla_\theta p_\theta(\tau) \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \\ &= \int_\tau \frac{p_\theta(\tau)}{p_\theta(\tau)} \nabla_\theta p_\theta(\tau) \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \\ &= \int_\tau p_\theta(\tau) \frac{\nabla_\theta p_\theta(\tau)}{p_\theta(\tau)} \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \\ &= \int_\tau p_\theta(\tau) \nabla_\theta \log p_\theta(\tau) \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \end{aligned} ∂ θ ∂ J ( θ ) = ∇ θ J ( θ ) = ∇ θ ∫ τ p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ = ∫ τ ∇ θ p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) p θ ( τ ) ∇ θ p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) p θ ( τ ) ∇ θ p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) ∇ θ log p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ 위에서 적분 안으로 미분이 들어가는 것은 무조건 되는 것은 아니지만 여기서는 가능한 함수를 다룬다고 가정하자.
이제 ∇ θ log p θ ( τ ) \nabla_\theta \log p_\theta(\tau) ∇ θ log p θ ( τ )
∇ θ log p θ ( τ ) = ∇ θ log ( p ( s 0 ) ∏ t = 0 T π θ ( a t ∣ s t ) p ( s t + 1 ∣ s t , a t ) ) = ∇ θ ( log p ( s 0 ) + ∑ t = 0 T log π θ ( a t ∣ s t ) + ∑ t = 0 T log p ( s t + 1 ∣ s t , a t ) ) = ∇ θ ∑ t = 0 T log π θ ( a t ∣ s t ) = ∑ t = 0 T ∇ θ log π θ ( a t ∣ s t ) \begin{aligned} \nabla_\theta \log p_\theta(\tau) &= \nabla_\theta \log \left(p(s_0) \prod_{t=0}^T \pi_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t) \right)\\ &= \nabla_\theta \left( \log p(s_0) + \sum_{t=0}^T \log \pi_\theta(a_t|s_t) + \sum_{t=0}^T \log p(s_{t+1}|s_t, a_t) \right) \\ &= \nabla_\theta \sum_{t=0}^T \log \pi_\theta(a_t|s_t) \\ &= \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \end{aligned} ∇ θ log p θ ( τ ) = ∇ θ log ( p ( s 0 ) t = 0 ∏ T π θ ( a t ∣ s t ) p ( s t + 1 ∣ s t , a t ) ) = ∇ θ ( log p ( s 0 ) + t = 0 ∑ T log π θ ( a t ∣ s t ) + t = 0 ∑ T log p ( s t + 1 ∣ s t , a t ) ) = ∇ θ t = 0 ∑ T log π θ ( a t ∣ s t ) = t = 0 ∑ T ∇ θ log π θ ( a t ∣ s t ) θ \theta θ 0 0 0
이제 다시 ∇ θ J ( θ ) \nabla_\theta J(\theta) ∇ θ J ( θ )
∂ J ( θ ) ∂ θ = ∫ τ p θ ( τ ) ∇ θ log p θ ( τ ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) ( ∑ t = 0 T ∇ θ log π θ ( a t ∣ s t ) ) [ ∑ t = 0 T γ t r ( s t , a t ) ] d τ = E τ ∼ p θ ( τ ) [ ( ∑ t = 0 T ∇ θ log π θ ( a t ∣ s t ) ) ( ∑ t = 0 T γ t r ( s t , a t ) ) ] \begin{aligned} \frac{\partial J(\theta)}{\partial \theta} &= \int_\tau p_\theta(\tau) \nabla_\theta \log p_\theta(\tau) \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \\ &= \int_\tau p_\theta(\tau) \left( \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \right) \left [ \sum_{t=0}^T \gamma^t r(s_t, a_t) \right] d\tau \\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \left( \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \right) \left( \sum_{t=0}^T \gamma^t r(s_t, a_t) \right) \right] \end{aligned} ∂ θ ∂ J ( θ ) = ∫ τ p θ ( τ ) ∇ θ log p θ ( τ ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ = ∫ τ p θ ( τ ) ( t = 0 ∑ T ∇ θ log π θ ( a t ∣ s t ) ) [ t = 0 ∑ T γ t r ( s t , a t ) ] d τ = E τ ∼ p θ ( τ ) [ ( t = 0 ∑ T ∇ θ log π θ ( a t ∣ s t ) ) ( t = 0 ∑ T γ t r ( s t , a t ) ) ] 위의 식을 보면 그래디언트를 계산하는데 환경 모델을 의미하는 상태천이확률( p ( s t + 1 ∣ s t , a t ) ) (p(s_{t+1}|s_t, a_t)) ( p ( s t + 1 ∣ s t , a t ) )
그래디언트 개선 ∇ θ J ( θ ) = E τ ∼ p θ ( τ ) [ ( ∑ t = 0 T ∇ θ log π θ ( a t ∣ s t ) ) ( ∑ t = 0 T γ t r ( s t , a t ) ) ] \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \left( \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \right) \left( \sum_{t=0}^T \gamma^t r(s_t, a_t) \right) \right] ∇ θ J ( θ ) = E τ ∼ p θ ( τ ) [ ( t = 0 ∑ T ∇ θ log π θ ( a t ∣ s t ) ) ( t = 0 ∑ T γ t r ( s t , a t ) ) ] 위의 식을 자세히 보면 더 먼 미래 시점( k > t ) (k>t) ( k > t ) t t t
∇ θ J ( θ ) = E τ ∼ p θ ( τ ) [ ∑ k = 0 T ( ∇ θ log π θ ( a t ∣ s t ) ) ( ∑ k = t T γ t r ( s t , a t ) ) ] = E τ ∼ p θ ( τ ) [ ∑ k = 0 T ( γ t ∇ θ log π θ ( a t ∣ s t ) ) ( ∑ k = t T γ k − t r ( s t , a t ) ) ] \begin{aligned} \nabla_\theta J(\theta) &= \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \sum_{k=0}^T ( \nabla_\theta \log \pi_\theta(a_t|s_t)) \left( \sum_{k=t}^T \gamma^t r(s_t, a_t) \right) \right] \\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[\sum_{k=0}^T (\gamma^t \nabla_\theta \log \pi_\theta(a_t|s_t)) \left(\sum_{k=t}^T \gamma^{k-t} r(s_t, a_t) \right) \right] \end{aligned} ∇ θ J ( θ ) = E τ ∼ p θ ( τ ) [ k = 0 ∑ T ( ∇ θ log π θ ( a t ∣ s t ) ) ( k = t ∑ T γ t r ( s t , a t ) ) ] = E τ ∼ p θ ( τ ) [ k = 0 ∑ T ( γ t ∇ θ log π θ ( a t ∣ s t ) ) ( k = t ∑ T γ k − t r ( s t , a t ) ) ] 위의 식에서 γ t ∇ θ log π θ ( a t ∣ s t ) \gamma^t \nabla_\theta \log \pi_\theta(a_t|s_t) γ t ∇ θ log π θ ( a t ∣ s t ) t t t
E τ ∼ p θ ( τ ) [ ∑ k = 0 T ( ∇ θ log π θ ( a t ∣ s t ) ) ( ∑ k = t T γ k − t r ( s t , a t ) ) ] \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[\sum_{k=0}^T (\nabla_\theta \log \pi_\theta(a_t|s_t)) \left(\sum_{k=t}^T \gamma^{k-t} r(s_t, a_t) \right) \right] E τ ∼ p θ ( τ ) [ k = 0 ∑ T ( ∇ θ log π θ ( a t ∣ s t ) ) ( k = t ∑ T γ k − t r ( s t , a t ) ) ] 그래디언트를 수정했기 때문에 원 문제의 그래디언트와 편향(bias)을 가진 그래디언트로 볼 수 있다. 하지만 감가율을 포함할 경우 매우 어렵다고 알려져있어서 해당 그래디언트를 사용하도록 하자.
