목차
Policy Gradient
\[J_{\theta}=\int_{\tau} G_0 P_{\theta}(\tau) \,d\tau\] \[\theta \gets \theta + \alpha \nabla_{\theta}J_{\theta}\]policy-based 목적 함수는 위와 같다. trajectory에 대해서 적분을 해야하기 때문에 어려운 점이 있다. 그래서 이를 expectation 형식으로 바꾸어 편하게 연산할 수 있도록 만든다.
Expectation 형식으로 만들기 위해서 아래의 수식을 사용한다.
\[\nabla_{\theta} P_{\theta}(\tau) = P_{\theta}(\tau) \frac{\nabla_{\theta}P_{\theta}(\tau)}{P_{\theta}(\tau)} = P_{\theta}(\tau) \nabla_{\theta} \text{ln} P_{\theta}(\tau)\]이를 통해 처음 공식이 아래와 같이 변화된다.
\[J_{\theta}=\int_{\tau} G_0 P_{\theta}(\tau) \,d\tau= \int_{\tau} G_0 (\nabla_{\theta} \text{ln}P_{\theta}(\tau)) P_{\theta}(\tau) \,d\tau\]\(\nabla_{\theta} \text{ln} P_{\theta}(\tau)\)는 \(\tau\)로 이루어져있어 변형을 해야한다.
\[P_{\theta}(\tau) = P_{\theta}(s_0,a_0,s_1,a_1, \dots s_{\infty},a_{\infty})=P(s_0)P_{\theta}(a_0,s_1,a_1 \dots \vert s_0)\]위 식의 뒤쪽 공식은 bellman equation에 의해 풀어진다.
\[P_{\theta}(a_0,s_1,a_1 \dots \vert s_0) = P_{\theta}(a_0 \vert s_0) P_{\theta}(s_1,a_1, \dots \vert s_0, a_0)\] \[P_{\theta}(s_1,a_1, \dots \vert s_0, a_0) = P_{\theta}(s_1 \vert s_0, a_0) P_{\theta}(a_1, s_2, a_2, \dots \vert s_0, a_1, s_2)\] \[P_{\theta}(a_1, s_2, a_2, \dots \vert s_0, a_1, s_2) = P_{\theta}(a_1 \vert s_1)P_{\theta}(s_2,a_2, \dots \vert s_0, a_0, s_1, a_1)\]결국 남는 것은 \(P(s_0)P_{\theta}(a_0 \vert s_0)P(s_1 \vert s_0, a_0) P_{\theta}(a_1 \vert s_1) \dots\)이다. \(P_{\theta}(\tau)\)의 함수가 ln안에 있어 곱연산이 합연산으로 바뀐다. 또한 \(P(s_0)\),\(P(s_1 \vert s_0, a_0)\)는 transition으로 상수이므로 미분하면 0이된다. 그래서 \(\nabla_{\theta} \text{ln} P_{\theta}(\tau)\)는 아래 수식으로 표현이 가능하다.
\[\nabla_{\theta} \text{ln} P_{\theta}(\tau)=\nabla_{\theta} \underset{t=0}{\overset{\infty}{\sum}} \text{ln} P(a_t \vert s_t)\]현재까지 공식은 아래와 같이 정리할 수 있다.
\[\int_{\tau} G_0 P_{\theta}(\tau) \, d\tau = \int_{\tau} G_0 (\nabla_{\theta} \underset{t=0}{\overset{\infty}{\sum}}\text{ln} P(a_t \vert s_t))P_{\theta}(\tau) \,d\tau\]여기서 특별한 점은 분배 법칙에 의해 몇몇 term이 사라진다.
\(G_0 \nabla_{\theta} \underset{t=0}{\overset{\infty}{\sum}} \text{ln}P(a_t \vert s_t)\)
\(=(R_0 + \gamma R_1 + \gamma^2 R_2 + \cdots) \times (\nabla_{\theta}\text{ln}P_{\theta}(a_0 \vert s_0) + \nabla_{\theta}\text{ln}P_{\theta}(a_1 \vert s_1) + \cdots)\)
분배 법칙에 의해 나누어지는 term 중 \(R_0\)과 \(\nabla_{\theta} \text{ln} P_{\theta}(a_1 \vert s_1)\)로 이루어진 term만 고려해보자.
\[\int_{\tau} R_0 \nabla_{\theta} \text{ln} P_{\theta}(a_1 \vert s_1)P_{\theta} (\tau) \, d\tau\]\(\tau\) 중 \(a_1\)를 뺀 경우를 \(\tau_{-a_1}\)이라고 표기한다면 위 식은 아래와 같이 변환할 수 있다.
\[\int_{\tau_{-a_1}} \int_{a_1} R_0 \nabla_{\theta} \text{ln} P_{\theta}(a_1 \vert s_1)P_{\theta}(a_1 \vert s_1) \,da_1 P_{\theta} (\tau_{-a_1}) \, d\tau_{-a_1}\]위 식에서 \(R_0\) \(s_0,a_0\)영향을 받아 만들어지는 reward이므로 밖으로 뺄 수 있다.
\[\int_{\tau_{-a_1}} R_0 \int_{a_1} \nabla_{\theta} \text{ln} P_{\theta}(a_1 \vert s_1) P_{\theta}(a_1 \vert s_1)\,da_1 P_{\theta} (\tau_{-a_1}) \, d\tau_{-a_1}\]그리고 \(\nabla\)를 밖으로 뺀다면 아래와 같은 식이 된다.
\[\int_{\tau_{-a_1}} R_0 \nabla_{\theta}\int_{a_1} \text{ln} P_{\theta}(a_1 \vert s_1) P_{\theta}(a_1 \vert s_1)\,da_1 P_{\theta} (\tau_{-a_1}) \, d\tau_{-a_1}\] \[=\int_{\tau_{-a_1}} R_0 \nabla_{\theta}\int_{a_1} P_{\theta}(a_1 \vert s_1) \,da_1 P_{\theta} (\tau_{-a_1}) \, d\tau_{-a_1}\]아래 식이 1이 되므로 이를 미분하면 0이 된다. 그래서 \(R_0\)과 \(\nabla_{\theta} \text{ln} P_{\theta}(a_1 \vert s_1)\)로 이루어진 term은 0이된다.
\[\int_{a_1} P_{\theta}(a_1 \vert s_1) \,da_1=1\]즉 state, action에 영향 받는 reward 짝만 남고 나머지는 다 제거되어 아래와 같은 식이된다. 예를 들어, \(R_0, R_1\)은 \(a_2, s_2\)의 영향을 받지 않는다. 하지만 \(R_2, R_3\)는 영향을 받는다. \(R_3\)를 만들기 위해서는 \(s_2\)에서 \(a_2\)의 행동을 해서 \(s_3\)로 이동했으므로 영향을 받는다.
결로적으로 아래 식이 도출된다.
\[\int_{\tau} \underset{t=0}{\overset{\infty}{\sum}} (\nabla_{\theta} \text{ln} P(a_t \vert s_t) \times \underset{k=t}{\overset{\infty}{\sum}} \gamma^k R_k) P_{\theta}(\tau) \,d\tau\]\(\gamma^t\gamma^{k-t}R_t\) 이므로 \(\underset{k=t}{\overset{\infty}{\sum}}\gamma^k R_k = \gamma^t G_t\)가 된다. t가 커지면 \(\gamma^t\) 영향을 무시할 수 있므로 아래와 같은 유사식을 얻을 수 있다.
\[\int_{\tau} \underset{t=0}{\overset{\infty}{\sum}} (\nabla_{\theta} \text{ln} P(a_t \vert s_t) \times \underset{k=t}{\overset{\infty}{\sum}} \gamma^k R_k) P_{\theta}(\tau) \,d\tau\] \[\approx \int_{\tau} \underset{t=0}{\overset{\infty}{\sum}} (\nabla_{\theta} \text{ln} P(a_t \vert s_t) \times G_t) P_{\theta}(\tau) \,d\tau\]REINFORCEMENT Algorithm
큰 수의 법칙에 따르면 \(\int_x P(x) \,dx \approx \frac{1}{x} \underset{i=1}{\overset{N}{\sum}} x_i\)가 된다.
하지만 N이 \(\infty\)라면 \(\theta\)를 \(\infty\)만큼 계산하고 update해야하므로 오래 걸리고 간헐적이라는 문제가 있다. 그래서 REINFORCEMENT Algorithm에서는 N을 1로 설정한다.
REINFORCEMENT Algorithm 순서도는 아래와 같다.
- Initialize \(\theta\)
- repeat 2~3
- Get \(\tau\) from \(P_{\theta}(a_t \vert s_t)\)
- Update: \(\theta \gets \theta + \alpha \underset{t=0}{\overset{\infty}{\sum}} \nabla_{\theta} \text{ln} P_{\theta}(a_t \vert s_t) G_t\)
- Go to step 1
Expectation form
REINFORCEMENT Algorithm을 Expectation form을 이용하여 정리할 경우 간단하게 이해할 수 있다.
\[J(\theta) = \underset{s \in S}{\sum} d^{\pi}(s) V^{\pi}(s) = \underset{s \in S}{\sum} d^{\pi}(s) \underset{a \in A}{\sum} \pi_{\theta}(a \vert s) Q^{\pi}(s,a)\] \[\nabla_{\theta} J(\theta) \propto \underset{s \in S}{\sum} d^{\pi}(s) \underset{a \in A}{\sum} Q^{\pi}(s,a)\nabla_{\theta} \pi_{\theta}(a \vert s)\] \[= \underset{s \in S}{\sum} d^{\pi}(s) \underset{a \in A}{\sum}\pi_\theta(a \vert s) Q^{\pi}(s,a) \frac{\nabla_{\theta} \pi_{\theta}(a \vert s)}{\pi_{\theta}(a \vert s)}\] \[= E_\pi [Q^\pi(s,a) \nabla_\theta \text{ln} \pi_\theta(a \vert s)]\] \[= E_\pi [G_t \nabla_\theta \text{ln} \pi_\theta(A_t \vert S_t)]\]where, \(Q^\pi(S_t, A_t) = E_\pi [G_t \vert S_t, A_t]\)