목차
- Policy Gradient Theorem
- Theorem 1
- Policy Gradient with Approximation
- Application to Deriving Algorithms and Advantages
- Reference
Policy Gradient Theorem
이전의 value function과 deterministic policy가 아닌 stochastic policy를 이용한다. \(\theta\)는 policy parameter, \(\rho\)는 policy의 performance(매 step마다 reward 평균)을 의미한다. policy는 아래 식을 이용하여 update 가능하다.
\[\vartriangle \theta \approx \alpha \frac{\partial \rho}{\partial \theta}\]Agent의 objective를 표현하는 방법은 두가지이다.
첫 번째는 average reward formulation이다.
\[\rho(\pi) = \lim_{n \to \infty} \frac{1}{n} E \{r_1 + r_2 + \cdots + r_n \vert \pi \} = \underset{s}{\sum}d^\pi (s) \underset{a}{\sum} \pi(s,a) R^a_s\]where \(d^\pi(s) = \underset{t \to \infty}{\lim} Pr \{ s_t = s \vert s_0, \pi \}\)
\[Q^\pi(s,a) = \sum^\infty_{t=1} E \{ r_t - \rho(\pi) \vert s_0 =s, a_0 =a, \pi \}\]두 번째는 start-state formulation이다.
\[\rho(\pi) = E \{ \underset{t=1}{\overset{\infty}{\sum}} \gamma^{t-1}r_t \vert s_0, \pi \}\] \[Q^\pi(s,a) = E \{\underset{k=1}{\overset{\infty}{\sum}} \gamma^{k-1}r_{r+k} \vert s_t =s, a_t=a, \pi \}\]where \(d^\pi(s) = \underset{t=0}{\overset{\infty}{\sum}} \gamma^t Pr \{ s_t = s \vert s_0, \pi \}\)
\(d^\pi(s)\)는 T 시간 동안 state가 s에 있을 확률을 의미한다.
Theorem 1
어떤 MDP라도 average-reward나 start-state formulations은 아래 식을 만족한다.
\[\frac{\partial \rho}{\partial \theta} = \underset{s}{\sum} d^\pi(s) \underset{a}{\sum} \frac{\partial \pi(s,a)}{\partial \theta}Q^\pi(s,a)\]partial derivation을 구할 때 \(\frac{\partial d^\pi(s)}{\partial \theta}\)의 term이 없다. 즉 policy의 변화는 states의 distribution에 영향을 주지않는다는 것이다. 그러므로 \(\sum_a \frac{\partial \pi(s,a)}{\partial \theta}Q^\pi(s,a)\)는 unbiased estimate of \(\frac{\partial \rho}{\partial\theta}\)이 된다.
Appendix: Proof of Theorem 1 average reward formulation
우선 average-reward formulation 증명을 한다.
\[\frac{\partial V^\pi(s)}{\partial \theta} \overset{\text{def}}{=} \frac{\partial}{\partial \theta} \sum_a \pi(s,a) Q^\pi(s,a)\] \[= \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \frac{\partial}{\partial \theta} Q^\pi(s,a) ]\]Q를 V로 표현된 식으로 대체 \(Q^\pi(s,a) = R^a_s - \rho(\pi) +\sum_s' P^a_{ss'}V^\pi(s')\)
\[= \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \frac{\partial}{\partial \theta}[ R^a_s - \rho(\pi) + \sum_{s'} P^a_{ss'} V^\pi(s')]]\]\(\frac{\partial}{\partial \theta}\)를 괄호 안으로
\[= \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) [-\frac{\partial \rho}{\partial \theta} + \sum_{s'} P^a_{ss'} \frac{\partial V^\pi(s')}{\partial \theta}]]\] \[= -\sum_a \pi(s,a) \frac{\partial \rho}{\partial \theta} + \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \sum_{s'} P^a_{ss'} \frac{\partial V^\pi(s')}{\partial \theta}]\]state의 action policy의 probability의 합은 1이므로
\[= -\frac{\partial \rho}{\partial \theta} + \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \sum_{s'} P^a_{ss'} \frac{\partial V^\pi(s')}{\partial \theta}]\]이로 인해 아래 식이 완성된다.
\[\frac{\partial V^\pi(s)}{\partial \theta}= -\frac{\partial \rho}{\partial \theta} + \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \sum_{s'} P^a_{ss'} \frac{\partial V^\pi(s')}{\partial \theta}]\]좌변을 우측으로 옮기고 우측 첫번째항은 좌측으로 넘기면 아래 식이된다.
\[\frac{\partial \rho}{\partial \theta} = \sum_a[ \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \sum_{s'} P^a_{ss'} \frac{\partial V^\pi(s')}{\partial \theta}] - \frac{\partial V^\pi(s)}{\partial \theta}\]양변에 stationary dstribution \(d^\pi\)를 곱한다.
\[\sum_s d^\pi(s) \frac{\partial \rho}{\partial \theta} = \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a)\] \[+ \sum_s d^\pi(s)\sum_a \pi(s,a) \sum_{s'} P^a_{ss'} \frac{\partial V^\pi(s')}{\partial \theta} - \sum_s d^\pi(s)\frac{\partial V^\pi(s)}{\partial \theta}\]좌측항은 모든 state의 probability의 합이므로 1이된다. 우측 두번째 항을 보면 station의 모든 action probability 합은 1이 되고 \(d^\pi\)와 transition은 합쳐진다.(\(\sum_sd^\pi(s)\sum_{s'}P^a_{ss'}=\sum_{s'}d^\pi(s')\))
\[\frac{\partial \rho}{\partial \theta} = \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \sum_s d^\pi(s')\frac{\partial V^\pi(s')}{\partial \theta} - \sum_s d^\pi(s)\frac{\partial V^\pi(s)}{\partial \theta}\] \[\frac{\partial \rho}{\partial \theta} = \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a)\]Appendix: Proof of Theorem 1 start-state formulation
여기서는 start-state formulation 증명을 한다.
\[\frac{\partial V^\pi(s)}{\partial \theta} \overset{\text{def}}{=} \frac{\partial}{\partial \theta} \sum_a \pi(s,a) Q^\pi(s,a)\] \[= \sum_a [\frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) + \pi(s,a) \frac{\partial}{\partial \theta}Q^\pi(s,a)]\] \[= \sum_a [\frac{\partial \pi(s,a)}{\partial \theta}Q^\pi(s,a) + \pi(s,a) \frac{\partial}{\partial \theta} [R^a_s + \sum_{s'} \gamma P^a_{ss'} V^\pi(s')]]\] \[= \sum_a [\frac{\partial \pi(s,a)}{\partial \theta}Q^\pi(s,a) + \pi(s,a) \frac{\partial}{\partial \theta} \sum_{s'} \gamma P^a_{ss'} V^\pi(s')]\cdots (1)\] \[= \sum_x \sum^\infty_{k=0} \gamma^k Pr(s \to x, k, \pi) \sum_a \frac{\partial \pi(x,a)}{\partial \theta} Q^\pi(x,a)\]위 공식 증명 과정에서 마지막 공식으로 변경되는 부분은 아래에서 증명한다.
k=0일 경우 즉 state s에서 state s로 가는 확률은 \(Pr(s \to s, k=0, \pi) = 1\)이다.
k=1일 경우 state s에서 state s’으로 가는 확률은 \(Pr(s \to s', k=1, \pi) = \sum_a \pi(a \vert s)P(s' \vert s, a)\)이다. \(\cdots (2)\)
k+1로 가는 확률은 k step을 갈 경우에서 1 step을 가는 경우를 곱하면 된다.
\[Pr(s \to x, k+1, \pi) = \sum_{s'} Pr(s \to s', k, \pi) Pr(s' \to x, 1, \pi) \cdots (3)\]증명을 위해 위 공식을 이용할 예정이다.
\[\phi(s) = \sum_{a \in A} \nabla_\theta \pi_\theta (a| s) Q^\pi(s,a)\]위 식을 가정한다.
(1)식에서 위 가정식을 대입하면 아래 식이 된다.
\[\nabla_\theta V^\pi(s) = \phi(s) + \sum_a \pi_\theta(a|s)\sum_{s'}\gamma P(s'|s,a) \nabla_\theta V^\pi(s')\] \[= \phi(s) + \sum_{s'} \sum_a \pi_\theta(a|s) \gamma P(s'|s,a) \nabla_\theta V^\pi(s')\]식 (2)를 이용해서 변환한다.
\[= \phi(s) + \sum_{s'} \gamma Pr(s \to s',1,\pi) \nabla_\theta V^\pi(s')\] \[= \phi(s) + \sum_{s'} \gamma Pr(s \to s', 1, \pi) [\phi(s') + \sum_{s''}\gamma Pr(s' \to s'', 1, \pi) \nabla_\theta V^\pi(s'')]\]식 (3)을 이용하여 합친다.
\[= \phi(s) + \sum_{s'} \gamma Pr(s \to s', 1, \pi) \phi(s') + \sum_{s''}\gamma^2 Pr(s' \to s'', 2, \pi) \nabla_\theta V^\pi(s'')] + \cdots\]이와 같은 공식이 반복되면 아래와 같이 정리가 된다.
\[= \sum_{x \in S} \sum^\infty_{k=0} \gamma^k Pr(s \to x, k, \pi) \phi(x)\] \[\frac{\partial \rho}{\partial \theta} = \frac{\partial}{\partial \theta} E \{ \sum^\infty_{t=1} \gamma^{t-1} r_t | s_0, \pi \} = \frac{\partial}{\partial \theta} V^\pi(s_0)\] \[= \sum_s \sum^\infty_{k=0} \gamma^k Pr(s_0 \to s, k, \pi) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a)\]\(\eta(s) = \sum^\infty_{k=0} \gamma^k Pr(s_0 \to s, k, \pi)\)라고 한다.
\[= \sum_s \eta(s)\sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a)\] \[= \sum_{s'} \eta(s') \frac{\sum_s \eta(s)}{\sum_{s'} \eta (s')} \sum_a \nabla \pi(s,a) Q^\pi(s,a)\] \[= \sum_{s'} \eta(s') \sum_s\frac{ \eta(s)}{\sum_{s'} \eta (s')} \sum_a \nabla \pi(s,a) Q^\pi(s,a)\] \[= \sum_{s'} \eta(s') \sum_s d^\pi(s) \sum_a \nabla \pi(s,a) Q^\pi(s,a)\]\(\sum_{s'} \eta(s')\)는 constant이므로
\[\propto \sum_s d^\pi(s) \sum_a \nabla \pi(a|s) Q^\pi(s,a)\] \[= \sum_s d^\pi(s) \sum_a \pi(a|s) \frac{\nabla \pi(a|s)}{\pi(a|s)} Q^\pi(s,a)\] \[=E_\pi [Q^\pi(s,a) \nabla \text{ln} \pi(a|s)]\]Policy Gradient with Approximation
여기서는 Q의 approximation에 대해서 다룬다.
Q가 w로 approximation이 된다면 gradient는 아래 식과 같이된다.
\[\triangle w_t \propto \frac{\partial}{\partial w}[\hat{Q}^\pi(s_t,a_t) - f_w(s_t,a_t)]^2 \propto [\hat{Q}^\pi(s_t,a_t) - f_w(s_t,a_t)] \frac{\partial f_w(s_t,a_t)}{\partial w}\]그리고 local optimum에 수렴한다면 아래 수식이 성립한다.
\(\sum_s d^\pi(s) \sum_a \pi(s,a) [Q^\pi(s,a) - f_w(s,a)] \frac{\partial f_w(s,a)}{\partial w} =0\) \(\cdots (3)\)
Theorem 2
만약 위 식을 만족한다면 아래 식은 compatibility condtion이된다.
\(\frac{\partial f_w(s,a)}{\partial w} = \frac{\partial \pi(s,a)}{\partial \theta} \frac{1}{\pi (s,a)}\) \(\cdots (4)\)
그렇다면 아래 식을 만족하게된다.
\[\frac{\partial \rho}{\partial \theta} = \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} f_w(s,a)\]식 (3), (4)를 합치면 아래 식이 만족한다.
\[\sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} [Q^\pi(s,a) - f_w(s,a)] =0\]위 식이 0이므로 \(\rho\)의 derviation 식이 빼서 사용할 수 있다.
\[\frac{\partial \rho}{\partial \theta} = \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a)\] \[= \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} Q^\pi(s,a) - \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} [Q^\pi(s,a) - f_w(s,a)]\] \[= \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} [Q^\pi(s,a) - Q^\pi(s,a) + f_w(s,a)]\] \[= \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} f_w(s,a)\]Application to Deriving Algorithms and Advantages
\[\pi(s,a) = \frac{e^{\theta^T\phi_{sa}}}{\sum_b e^{\theta^T\phi_{sb}}}\]일 경우 아래 식이 성립한다.
\[\frac{\partial f_w (s,a)}{ \partial w} = \frac{\partial \pi(s,a)}{\partial \theta}\frac{1}{\pi(s,a)} = \phi_{sa} - \sum_b \pi(s,b) \phi_{sb}\]\(f_w\)가 advantage function의 approximation이라고 생각하는 것이 좋다.
\[A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)\] \[\frac{\partial \rho}{\partial \theta} = \sum_s d^\pi(s) \sum_a \frac{\partial \pi(s,a)}{\partial \theta} [f_w(s,a) + v(s)]\]v는 위 식의 결과에는 영향을 주지 않고 variance에만 영향을 준다.