Q Learning 先学到一个value function，之后基于value function可以得到最优的policy。那Policy Gradient名字已经很直白了，直接对Policy进行建模，就很直接～如果Policy是一个神经网络，那么它的输入就是当前的环境状态(state)，输出的是此时采取每个动作的概率，于是policy gradient自然的引入了exploration，就不必像Q Learning那样得我们自己设计explore and exploit了。
如果$\rho$表示policy的性能，$\theta$是这个policy的所有系数，于是更新这个policy可以表示成
$$\Delta \theta = \alpha \frac{\partial \rho}{\partial \theta}$$
其中$\alpha$是learning rate，这样迭代一段时间就可以得到比较稳定的policy了，那么这个梯度是怎么算的呢？先给出结论吧，毕竟后面的推导过程也未必有兴趣看～
结论
$$\frac{\partial \rho}{\partial \theta} = \sum_{s} d^{\pi}(s) \sum_{a} \frac{\partial \pi(s,a)}{\partial \theta} Q^{\pi}(s,a)$$
其中$d^{\pi}(s) = \lim_{t \rightarrow \infty} \text{Pr}\{s_t = s | s_0, \pi\}$是stationary distribution, 大概可以理解成每个state出现的概率, stationary distribution 证明了在Markov Decision Process(MDP)下只要执行足够的步数每种状态出现的概率会稳定下来，这里直接理解成全句上每个state出现的概率应该没问题～
推导过程
接下来我们看怎么推导出上述结论的，开始前先定义几个变量
- $t \in {0, 1, 2, …}$
- $s_t \in S$, 时刻$t$的状态，$S$是状态(state)空间
- $a_t \in A$，时刻$t$的动作，$A$是动作(action)空间
- $r_t \in R$ 状态$s_t$下执行动作$a_t$的收益
还有几个假设
- 环境的状态转移概率(state transition probabilities)$$P_{ss’}^{a} = \text{Pr}\{s_{t+1} = {s}’ | s_t = s, a_t = a\}$$意思是说状态$s_t=s$下执行动作$a_t=a$后转移到状态${s}’$的概率
- 当从一个状态转移到另一个状态环境会给你一个反馈(reward)$$R_{s}^{a} = E \{ r_{t+1} | s_t=s, a_t=a \}, \forall s, {s}’ \in S, a \in A$$没错，它是一个均值，因为上面状态转移我们定义的是概率。
- agent每一步之行的动作由policy决定$$\pi(s, a, \theta) = Pr \{ a_t=a | s_t=s, \theta \}, \forall s \in S, a \in A$$ 一般会省略掉$\theta$写成$\pi(s,a)$
Policy 性能评估
原始论文种提供了两种评估某个policy性能的计算方式
1. average-reward formulation
$$\rho_{\pi} = \lim _{n \rightarrow \infty} \frac{1}{n} E \{ r_1 + r_2 + r_3 + … + r_n | \pi \} = \sum_{s}d^{\pi}(s) \sum_{a} \pi(s, a)R_{s}^{a}$$
公式比较好理解，状态$s$下执行每个动作有不同的收益$R_{s}^{a}$，该状态下执行每个动作的概率是$\pi(s,a)$，于是可以计算出该状态的平均收益$\pi(s, a)R_{s}^{a}$，我们也知道每个状态出现的概率$d^{\pi}(s)$，于是可以得到一个平均收益。比较强的policy在状态$s$下可以预测出可以获得最高收益的那个动作，我们取样这个动作的概率也最大，基于这个policy可以定义某个动作的value:
$$Q^{\pi}(s,a) = \sum_{t=1}^{\infty}E\{ r_t – \rho (\pi) | s_0=s, a_0 =a, \pi \}, \forall s \in S, a \in A$$
状态$s$下执行动作$a$的value是执行该动作后引发的后续所有步骤的收益减去policy的性能，即减去每个状态的平均收益，评价的是状态$s$下执行动作$s$的value是不是强于这个policy在每个状态下的平均能力。
2. the start-state formulation
$$\rho(\pi) = E \left \{ \sum_{t=1}^{\infty} \gamma^{t-1}r_t|s_0,\pi \right \}$$
用初始状态$s_0$的discount reward作为policy的性能，这种方式动作的value：
$$Q^{\pi}(s, a) = E \left \{ \sum_{k=1}^{\infty} \gamma^{k-1} r_{t+k} | s_t=s, a_t=a, \pi \right \}$$
状态$s$下执行动作$a$的value是引发的后续所有步骤的收益的discount reward。
PG的证明
Policy Gradient的证明在论文的Appendix部分，我这里只证明当performance是平均收益的情况，每一步我都加上了解释～
$$\frac{\partial V^{\pi}(s)}{\partial \theta} = \frac{\partial}{\partial \theta}\sum_{a}\pi(s,a)Q^{\pi}(s,a), \forall s \in S$$
定义$V^{\pi}(s)$是状态$s$的value，很显然它是这个状态下执行执行每个动作后的value的均值，根据导数乘法分解一下
$$=\sum_{a} \left [ \frac{\partial \pi(s,a)}{\partial \theta}Q^{\pi}(s,a) + \pi(s,a)\frac{\partial}{\partial \theta}Q^{\pi}(s,a) \right ]$$
根据上面$Q^{\pi}(s,a)$的定义可以重写成$R_{s}^{a} -\rho(\pi) + \sum_{s’} P_{ss’}^{a}V^{\pi}(s’)$，不要试图去推导它～感受它～状态$s$下执行一个动作会得到reward$R_{s}^{a}$，接着会转移到另一个状态(${s}’$)，每个$s’$都有自己的value，转移概率$P_{ss’}^{a}$我们知道，于是可以得到下一步的平均value
$$=\sum_{a} \left [ \frac{\partial \pi(s,a)}{\partial \theta}Q^{\pi}(s,a) + \pi(s,a)\frac{\partial}{\partial \theta} \left [ R_{s}^{a} -\rho(\pi) + \sum_{s’} P_{ss’}^{a}V^{\pi}(s’) \right ]\right ]$$
$R_{s}^{a}$和$P_{ss’}^{a}$中没有$\theta$，再算一步
$$=\sum_{a} \left [ \frac{\partial \pi(s,a)}{\partial \theta}Q^{\pi}(s,a) + \pi(s,a) \left [- \frac{\partial \rho}{\partial \theta} + \sum_{s’}P_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta} \right ] \right ]$$
整理下
$$=\sum_{a} \left [ \frac{\partial \pi(s,a)}{\partial \theta}Q^{\pi}(s,a) – \pi(s,a) \frac{\partial \rho}{\partial \theta} + \pi(s,a) \sum_{s’}P_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta} \right ]$$
$\rho$是一个标量，衡量$\pi$的性能，于是也只跟选择什么样$\pi$有关，跟动作$a$没啥关系，于是中间那段$ -\pi(s,a) \frac{\partial \rho}{\partial \theta}$和它外面的$\sum_{a}$重写成$-\frac{\partial \rho}{\partial \theta} \sum_{a}\pi(s,a)$,状态$\pi(s,a)$是个概率，采取所有动作的可能性是1，最后会剩下我们想要的$-\frac{\partial \rho}{\partial \theta}$，把它放左边
$$\frac{\partial \rho}{\partial \theta} = \sum_{a} \left [ \frac{\partial \pi(s,a)}{\partial \theta}Q^{\pi}(s,a) + \pi(s,a) \sum_{s’}P_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta} \right ] – \frac{\partial V^{\pi}(s)}{\partial \theta} $$
同时乘上$\sum_{s}d^{\pi}(s) = 1$
$$\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_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta} – \sum_{s}d^{\pi}(s) \frac{\partial V^{\pi}(s)}{\partial \theta} $$
原论文中从这一步到下一步很夸张的直接化简了，我们还是一点点来，等式右边中间的部分
$$ \sum_{s}d^{\pi}(s) \sum_{a} \pi(s,a) \sum_{s’}P_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta}$$
stationary distribution $d^{\pi}(s)$满足
$$d^{\pi}(\hat{s}) = \sum_{s}d^{\pi}(s)\sum_{a}\pi(s,a)P_{s\hat{s}}^{a}$$
直觉上理解，即任意状态$\hat{s}$出现的概率，等于所有状态转移到这个状态的概率的均值，于是遍历所有状态再遍历每个状态下执行某个动作后转移到状态$\hat{s}$的概率，算出来就是状态$s’$出现的概率。
由于$\sum$满足交换律和结合律
$$\sum_{s}d^{\pi}(s) \sum_{a} \pi(s,a) \sum_{s’}P_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta} = \sum_{s’} \left [ \sum_{s}d^{\pi}(s) \sum_{a} \pi(s,a) P_{ss’}^{a}\frac{\partial V^{\pi}(s’)}{\partial \theta} \right ]$$
于是中间凑出一个转移到状态$s’$的概率
$$\sum_{s’} \left [ \sum_{s}d^{\pi}(s) \sum_{a} \pi(s,a) P_{ss’}^{a}\right ] \frac{\partial V^{\pi}(s’)}{\partial \theta} = \sum_{s’}d^{\pi}(s’) \frac{\partial V^{\pi}(s’)}{\partial \theta}$$
于是最终公式变成了
$$\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} $$
后面两项等价直接去除，再去掉左边的$\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)$$
原文有一句感觉比较点题的话
In any event, the key aspect of both expressions for the gradient is that their are no terms of the from $\frac{\partial d^{\pi}(s)}{\partial \theta}$: the effect of policy changes on the distribution of states does not appear. This is convenient for approximating the gradient by sampling.