雅克比矩阵和海塞矩阵对比

1. 雅克比矩阵是一阶导数，海塞矩阵是二阶导数。
2. 雅克比矩阵要求函数的输入是向量，输出也是向量，而海塞矩阵要求输入是向量，输出是标量。
3. 雅克比矩阵不一定是方阵（当输入和输出的维度相等时是方阵），但是海塞矩阵一定是方阵。当函数的输出是标量的时候，雅克比矩阵退化成了梯度向量。
4. 海塞矩阵可以看成梯度的雅克比矩阵。

雅克比矩阵

定义：$f:\mathbb{R}^n \rightarrow \mathbb{R}^m $，即一个函数的输入和输出都是向量，计算输出向量对于输入向量的偏导数（详情可见矩阵求导)，得到一个$m\times n$的矩阵（numerator layout），这就是雅克比矩阵。
$$J = \begin{bmatrix}\frac{\partial \mathbf{y}}{\partial x_1} & \cdots & \frac{\partial \mathbf{y}}{\partial x_n}\end{bmatrix} = \begin{bmatrix} \frac{\partial \mathbf{y_1}}{\partial x_1} & \cdots & \frac{\partial \mathbf{y_1}}{\partial x_n}\\ & \cdots & \\ \frac{\partial \mathbf{y_m}}{\partial x_1} & \cdots & \frac{\partial \mathbf{y_m}}{\partial x_n}\end{bmatrix}$$

海塞矩阵

定义：$f:\mathbb{R}^n \rightarrow \mathbb{R} $，即一个函数的输入是向量，输出是标量时，计算输出对于输入向量的二阶导数（详情可见矩阵求导)，得到一个$n\times n$的矩阵（numerator layout），这就是雅克比矩阵。
$$ H = \begin{bmatrix} \frac{\partial^2 \mathbf{y}}{\partial x_1^2 }\cdots & \cdots & \frac{\partial^2 \mathbf{y}}{\partial x_1 x_n}\\ \cdots \\ \frac{\partial^2 \mathbf{y}}{\partial x_nx_1}\cdots & \cdots & \frac{\partial^2 \mathbf{y}}{\partial x_nx_n}\end{bmatrix}$$

参考文献

1.https://zhuanlan.zhihu.com/p/67521774

Trust Region Policy Optimization

作者提出了optimizing policies的一个迭代算法，理论上保证可以以non-trivial steps单调改善plicy。对经过理论验证的算法做一些近似，产生一个实用算法，叫做Trust Region Policy Optimization(TRPO)。这个算法和natural policy gradient很像，并且在大的非线性网络优化问题上有很高的效率。TRPO有两个变种，single-path方法应用在model-free环境中，vine方法，需要整个system能够能够从特定的states重启，通常在仿真环境中可用。

Introduction

为什么要有TRPO？

1. policy gradient计算的是expected rewards梯度的最大方向，然后朝着这个方向更新policy的参数。因为梯度使用的是一阶导数，梯度太大时容易fail，梯度太小的话更新太慢。
2. 学习率很难选择，学习率固定，梯度大容易失败，梯度小更新太慢。
3. 如何限制policy，防止它进行太大的move。然后如何将policy的改变转换到model parameter的改变上。
4. 采样效率很低。对整个trajectory进行采样，但是仅仅用于一次policy update。在一个trajectory中的states是很像的，尤其是用pixels表示时。如果在每一个timestep都改进policy的话，会一直在某一个局部进行更新，训练会变得很不稳定。

Motivation

我们想要每一次策略$\pi$的更新，都能使得$\eta(\pi)$单调递增。要是能将它写成old poliy $\pi_{old}$和new policy $\pi_{new}$的关系式就好啦。给出这样一个关系式：
$$\eta(\pi_{new}) = \eta(\pi_{old}) + \mathbb{E}_{s_0, a_0, \cdots \sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t A^{\pi_{old}}(s_t,a_t)\right] \tag{1}$$
证明：
\begin{align*}
\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new} }\left[\sum_{t=0}^{\infty} \gamma^t A^{\pi_{old}} (s_t,a_t) \right] &=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}}\left[\sum_{t=0}^{\infty} \gamma^t (Q^{\pi_{old}} (s_t,a_t) - V^{\pi_{old}} (s_t))\right] \\
&=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t ( R_{t+1} + \gamma V^{\pi_{old}} (s_{t+1}) - V^{\pi_{old}} (s_t))\right] \\
&=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t R_{t+1} + \sum_{t=0}^{\infty} \gamma^t (\gamma V^{\pi_{old}} (s_{t+1}) - V^{\pi_{old}} (s_t))\right] \\
&=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t R_{t+1} \right]+ \mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t (\gamma V^{\pi_{old}} (s_{t+1}) - V^{\pi_{old}} (s_t))\right] \\
&=\eta(\pi_{new}) + \mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[ - V^{\pi_{old}} (s_0))\right] \\
&=\eta(\pi_{new}) - \mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[ V^{\pi_{old}} (s_0))\right] \\
&=\eta(\pi_{new}) - \eta(\pi_{old})\\
\end{align*}
将new policy $\pi_{new}$的期望回报表示为old policy $\pi_{old}$的期望回报加上另一项，只要保证这一项是非负的即可。其中$\mathbb{E}_{s_0, a_0,\cdots, \sim \pi_{new}}\left[\cdots\right]$表示actions是从$a_t\sim\pi_{new}(\cdot|s_t)$得到的。

用求和代替期望

代入$s$的概率分布$\rho_{\pi}(s) = P(s_0 = s) +\gamma P(s_1=s) + \gamma^2 P(s_2 = s)+\cdots, s_0\sim \rho_0$，并将期望换成求和：
\begin{align*}
\eta(\pi_{new}) &= \eta(\pi_{old}) + \mathbb{E}_{s_0, a_0, \cdots \sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t A^{\pi_{old}}(s_t,a_t)\right]\\
&=\eta(\pi_{old}) +\sum_{t=0}^{\infty} \sum_s P(s_t=s|\pi_{new}) \sum_a \pi_{new}(a|s)\gamma^t A^{\pi_{old}}(s,a)\\
&=\eta(\pi_{old}) +\sum_s\sum_{t=0}^{\infty} \gamma^t P(s_t=s|\pi_{new}) \sum_a \pi_{new}(a|s)A^{\pi_{old}}(s,a)\\
&=\eta(\pi_{old}) + \sum_s \rho_{\pi_{new}}(s) \sum_a \pi_{new}(a|s) A^{\pi_{old}} (s,a) \tag{2}\\
\end{align*}
从上面的推导可以看出来，任何从$\pi_{old}$到$\pi_{new}$的更新，只要保证每个state $s$处的expected advantage是非负的，即$\sum_a \pi_{new}(a|s) A_{\pi_{old}}(s,a)\ge 0$，就能说明$\pi_{new}$要比$\pi_{old}$好，在$s$处，新的policy $\pi_{new}$:
$$\pi_{new}(s) = \arg\ \max_a A^{\pi_{old}} (s,a) \tag{3}$$
直到所有$s$处的$A^{\pi_{old}} (s,a)$为非正停止。当然，在实际应用中，因为各种误差，可能会有一些state的expected advantage是负的。

$\rho_{\pi_{old}}(s)$近似$\rho_{\pi_{new}}(s)$（第一次近似）

式子$(2)$中包含的$\rho_{\pi_{new}}$依赖于未知的$\pi_{new}$，而我们已知的是$\pi_{old}$，忽略因为policy改变导致的state访问频率的改变，在$L_{\pi_{old}}(\pi_{new} )$中用$\rho_{\pi_{old}}(s)$近似$\rho_{\pi_{new}}(s)$。
\begin{align*}
\eta(\pi_{new}) &= \eta(\pi_{old}) + \sum_s\rho_{\pi_{new}}(s)\sum_a\pi_{new}(a|s)A^{\pi_{old}} (s,a)\\
& = \eta(\pi_{old}) + \mathbb{E}_{s\sim \pi_{new}, a\sim \pi_{new}}A^{\pi_{old}}(s,a)\\
& = \eta(\pi_{old}) + \mathbb{E}_{s\sim \pi_{new}, a\sim \pi_{old}}\left[\frac{\pi_{new}(a|s)}{\pi_{old}(a|s)}A^{\pi_{old}}(s,a)\right]\tag{4}\\
\end{align*}

\begin{align*}
L_{\pi_{old}}(\pi_{new}) & = \eta(\pi_{old}) + \sum_s\rho_{\pi_{old}}(s)\sum_a\pi_{new}(a|s)A^{\pi_{old}} (s,a)\\
& = \eta(\pi_{old}) +\mathbb{E}_{s\sim \pi_{old}, a\sim \pi_{new}}A^{\pi_{old}}(s,a)\\
& = \eta(\pi_{old}) +\mathbb{E}_{s\sim \pi_{old}, a\sim \pi_{old}}\left[\frac{\pi_{new}(a|s)}{\pi_{old}(a|s)}A^{\pi_{old}}(s,a)\right]\tag{5}\\
\end{align*}

用$\pi_{\theta}(a|s)$表示可导policy，用$\theta_{old}$表示$\pi_{old}$的参数。当$\pi_{new} = \pi_{old}$时，即$\theta=\theta_{old}$时，$L_{\pi_{old}}(\pi_{new})$和$\eta(\pi_{new})$的一阶导相等：
$$L_{\pi_{old}}(\pi_{new}) = \eta(\pi_{old}) + \sum_s\rho_{\pi_{old}}(s)\sum_a\pi_{old}(a|s)A^\pi_{old}(s,a) = \eta(\pi_{new})\tag{6}$$
$$\nabla_{\theta} L_{\pi_{old}}(\pi_{new})|_{\theta=\theta_{old}} = \mathbb{E}_{s\sim \pi_{old}, a\sim \pi_{old}}\left[\frac{\nabla_{\theta}\pi_{new}(a|s)}{\pi_{old}(a|s)}A^{\pi_{old}}(s,a)\right]|_{\theta_{old}}\tag{7} $$
$$\nabla_{\theta} \eta(\pi_{new})|_{\theta=\theta_{old}} =\mathbb{E}_{s\sim \pi_{new}, a\sim \pi_{old}}\left[\nabla_{\theta}\log\pi_{new}(a|s)A^{\pi_{old}}(s,a)\right]|_{\theta_{old}} \tag{8}$$
证明：
式子$(6)$将$\pi_{new}=\pi_{old}$代入即可。我对于式子$7$和$8$相等有疑问，为什么？
也就是说当$\pi_{new} = \pi_{old}$时，$L_{\pi_{old}}(\pi_{new})$和$\eta(\pi_{new})$是相等的，在$\pi_{old}$对应的参数$\theta$周围的无穷小范围内，可以近似认为它们依然相等，$\theta$进行足够小的step更新到达新的policy $\pi_{new}$，相应参数为$\theta_{\pi_{new}}$，在改进$L_{\pi_{old}}$同时也改进了$\eta$，但是这个足够小的step是多少是不知道的。

conservative policy iteration

为了求出这个step到底是多少，有人提出了conservative policy iteration算法，该算法提供了$\eta$提高的一个lower bound。用$\pi_{old}$表示current policy，用$\pi’$表示使得$L_{\pi_{old}}$取得最大值的policy，$\pi’ = \arg\ \min_{\pi’} L_{\pi_{old}}(\pi’)$，新的policy $\pi_{new}$定义为：
$$\pi_{new}(a|s) = (1-\alpha) \pi_{old}(a|s)+\alpha\pi’(a|s) \tag{9}$$
可以证明，新的policy $\pi_{new}$和老的policy $\pi_{old}$之间存在以下关系：
$$\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new}) - \frac{2\epsilon \gamma}{(1-\gamma(1-\alpha))(1-\gamma)}\alpha^2 $$
$$\epsilon = \max_s \vert\mathbb{E}_{a\sim\pi’}\left[A^{\pi} (s,a)\right]\vert \tag{10}, \alpha,\gamma\in [0,1]$$
证明：
进行缩放得到：
$$\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new}) - \frac{2\epsilon \gamma}{(1-\gamma)^2 }\alpha^2 \tag{11}$$

通用随机策略单调增加的证明

从公式$9$我们可以看出来，改进右边就一定能改进真实的performance $\eta$。然而，这个bound只适用于通过公式$7$生成的混合policy，在实践中，这类policy很少用到，而且限制条件很多。所以我们想要的是一个适用于任何stochastic policy的lower bound，通过提升这个bound提升$\eta$。
作者使用$\pi_{old}$和$\pi_{new}$之间的一个距离代替$\alpha$，将公式$8$扩展到了任意stochastic policy，而不仅仅是混合policy。这里使用的distance measure，叫做total variation divergence，对于离散的概率分布$p,q$来说，定义为：
$$D_{TV}(p||q) = \frac{1}{2} \sum_i \vert p_i -q_i \vert \tag{12}$$
定义$D_{TV}^{max}(\pi_{old}, \pi_{new})$为：
$$D_{TV}^{max} (\pi_{old}, \pi_{new}) = \max_s D_{TV}(\pi_{old}(\cdot|s) || \pi_{new}(\cdot|s))\tag{13}$$
让$\alpha = D_{TV}^{max}(\pi_{old}, \pi_{new})$，新的bound如下：
$$\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new}) - \frac{4\epsilon \gamma}{(1-\gamma)^2 }\alpha^2 , \qquad\epsilon = \max_{s,a} \vert A^{\pi_{old}}(s,a)\vert \tag{14}$$
证明：
…

Total variation divergence和KL散度之间有这样一个关系：
$$D_{TV}(p||q)^2 \le D_{KL}(p||q) \tag{15}$$
证明：
…
让
$$D_{KL}^{max}(\pi_{old}, \pi_{new}) = \max_s D_{KL}(\pi_{old}(\cdot|s)||\pi_{new}(\cdot|s)) \tag{16}$$
从公式$12$中可以直接得到：
\begin{align*}
\eta(\pi_{new}) &\ge L_{\pi_{old}}(\pi_{new}) - \frac{4\epsilon \gamma}{(1-\gamma)^2 }\alpha^2 \\
&\ge L_{\pi_{old}}(\pi_{new}) - \frac{4\epsilon \gamma}{(1-\gamma)^2 }D_{KL}^{max}(\pi_{old}, \pi_{new}) \\
& \ge L_{\pi_{old}}(\pi_{new}) - CD_{KL}^{max}(\pi_{old}, \pi_{new})\\
C & =\frac{4\epsilon \gamma}{(1-\gamma)^2} \tag{17}
\end{align*}
根据公式$12$，我们能生成一个单调非递减的sequence：$\eta(\pi_0)\le \eta(\pi_1) \le \eta(\pi_2) \le \cdots$，记$M_i(\pi) = L_{\pi_i}(\pi) - CD_{KL}^{max}(\pi_i, \pi)$，有：
因为：
$$\eta(\pi_{i+1}) \ge M_i(\pi_{i+1})\tag{18}$$
$$\eta(\pi_i) = M_i(\pi_i)\tag{19}$$
上面的第一个式子减去第二个式子得到：
$$\eta(\pi_{i+1}) - \eta(\pi_i)\ge M_i(\pi_{i+1})-M_i(\pi_i) \tag{20}$$
在每一次迭代的时候，确保$M_i(\pi_{i+1}) - M_i(\pi_i)\ge 0$就能够保证$\eta$是非递减的，最大化$M_i$就能实现这个目标，$M_i$是miorize $\eta$的近似目标。这种算法是minorizaiton maximization的一种。

参数化策略的优化（第二次近似）

前面几小节考虑的optimization问题时没有考虑$\pi$的参数化，并且假设所有的states都可以被evaluated。这一节介绍如何在有限的样本下和任意的参数化策略下，从理论基础推导出一个实用的算法。
用$\theta$表示参数化策略$\pi_{\theta}(a|s)$的参数$\theta$，将目标表示成$\theta$而不是$\pi$的函数，即用$\eta(\theta)$表示原来的$\eta(\pi_\theta)$，用$L_{\theta}(\hat{\theta})$表示$L_{\pi_{\theta}}(\pi_{\hat{\theta}})$，用$D_{KL}(\theta||\hat{\theta})$表示$D_{KL}(\pi_{\theta}||\pi_{\hat{\theta}})$。用$\theta_{old}$表示我们想要改进的policy参数。
上一小节我们得到$\eta(\theta) \ge L_{\theta_{old}}(\theta) - CD_{KL}^{max}(\theta_{old}, \theta)$，当$\theta = \theta_{old}$时取等。通过最大化等式右边，可以提高$\eta$的下界：
$$\max_{\theta}\left[L_{\theta_{old}}(\theta) - CD_{KL}^{max}(\theta_{old}, \theta)\right]\tag{21}$$
在实践中，如果使用上述理论中的penalty coefficient $C$，会导致steps size很小。一种方法是使用new policy 和old policy之间的KL散度进行约束，可以采取更大的steps，这个约束叫做trust region constraint:
$$\max_{\theta} L_{\theta_{old}} (\theta)$$
$$ s.t. D_{KL}^{max}(\theta_{old},\theta) \le \delta \tag{22}$$
这样会在state space的每一个state都有一个KL散度约束。由于约束太多，这个问题还是不能解。这里使用average KL divergence进行近似:
$$\bar{D}_{KL}^{\rho}(\theta_1, \theta_2) = \mathbb{E}_{s\sim \rho}\left[D_{KL}(\pi_{\theta_1}(\cdot|s) || \pi_{\theta_2}(\cdot|s))\right] \tag{23}$$
公式$22$变成：
$$\max_{\theta} L_{\theta_{old}} (\theta)$$
$$s.t. \bar{D}_{KL}^{\rho_{\theta_{old}}}(\theta_{old},\theta) \le \delta \tag{24}$$

目标函数和约束的采样估计（第三次近似）

上一节介绍的是关于policy parameter的有约束优化问题，约束条件为每一次policy更新时限制policy变化的大小，优化expected toral reward $\eta$的一个估计值。这一节使用Monte Carlo仿真近似目标和约束函数。
代入$L_{\theta_{old}}$的等式，得到：
$$\max_{\theta}\sum_s \rho_{\theta_{old}}(s) \sum_a\pi_{\theta}(a|s)A_{\theta_{old}}(s,a)$$
$$s.t. \bar{D}_{KL}^{\rho_{\theta_{old}}}(\theta_{old},\theta) \le \delta \tag{25}$$
首先用期望$\frac{1}{1-\gamma}\mathbb{E}_{s\sim \rho_{\theta_{old}}}\left[\cdots\right]$代替目标函数中的$\sum_s\rho_{\theta_{old}}(s) \left[\cdots\right]$。接下来用$Q$值$Q_{\theta_{old}}$代替advantage $A_{\theta_{old}}$，结果多了一个常数项，不影响。最后使用importance smapling代替actions上的求和。使用$q$表示采样分布，$q$分布中单个的$s_n$对于loss函数的贡献在于：
$$\sum_a \pi_{\theta}(a|s_n) A_{\theta_{old}}(s_n,a) = \mathbb{E}_{a\sim q}\left[\frac{\pi_{\theta} (a|s_n) }{q(a|s_n)}A_{\theta_{old}}(s_n,a) \right]\tag{26}$$
上面的公式就是使用importance sampling代替求和。将$A$展开：
\begin{align*}
\sum_a \pi_{\theta}(a|s) A_{\theta_{old}}(s,a) &= \sum_a \pi_{\theta}(a|s)\left( Q_{\theta_{old}}(s,a) - V_{\theta_{old}}(s)\right)\\
&= \sum_a \pi_{\theta}(a|s)Q_{\theta_{old}}(s,a)- \sum_a \pi_{\theta}(a|s)V_{\theta_{old}}(s)\\
&= \sum_a \pi_{\theta}(a|s)Q_{\theta_{old}}(s,a)- V_{\theta_{old}}(s)\\
\end{align*}
将公式$25$的优化问题转化为：
$$\max_{\theta} \mathbb{E}_{s\sim\rho_{\theta_{old}}, a\sim q}\left[\frac{\pi_{\theta} (a|s) }{q(a|s)}Q_{\theta_{old}}(s,a)\right]$$
$$s.t. \mathbb{E}_{s\sim \rho_{\theta_{old}}}\left[D_{KL}(\pi_{\theta_{old}}(\cdot|s)||\pi_{\theta}(\cdot|s))\right]\le \delta \tag{27}$$
好了，前面给出各种证明和近似，终于给出了我们要解决的问题的数学公式，这部分是为了帮助我们理解。我们实际需要的是解这个有约束的优化问题，这也是代码中要实现的部分，具体怎么做，一句话，采样然后估计。用采样代替期望，用经验估计代替$Q$值。
介绍两种方法进行估计。第一个叫做single path，通常用在policy gradient estimation，基于单个轨迹的采样。第二个叫做vine，构建一个rollout set，从rollout set的每一个state处执行多个actions。这种方法经常用在policy iteration方法上。

Single Path

采样$s_0\sim \rho_0$，模拟policy $\pi_{\theta_{old}}$一些timesteps生成一个trajectory $s_0, a_0, s_1, a_1, \cdots, s_{T-1}, a_{T-1}, s_T$，因此$q(a|s) = \pi_{\theta_{old}}(a|s)$。根据trajectory对每一个state action pair $(s_t,a_t)$计算$Q_{\theta_{old}}(s,a)$。

Vine

采样$s_0\sim \rho_0$，模拟policy $\pi_{\theta_i}$生成一系列trajectories。在这些trajectories选择一个具有$N$个states的子集，表示为$s_1, c\dots, s_N$，这个集合称为rollout set。对于rollout set中的每一个state $s_n$，根据$a_{n,k}\sim q(\cdot|s_n)$采样$K$个actions。任何$q(\cdot|s_n)$都行，在实践中，$q(\cdot|s_n) = \pi_{\theta_i}(\cdot|s_n)$适用于contionous problems，像机器人运动；而均匀分布适用于离散任务，如Atari游戏。
对于$s_n$处的每一个action $a_{n,k}$，从$s_n$和$a_{n,k}$处进行rollout，估计$\hat{Q}_{\theta_i}(s_n, a_{n,k})$。在小的有限action spaces情况下，我们可以对从给定状态任何可能的action生成一个rollout，单个$s_n$对$L_{\theta_{old}}$的贡献如下：
$$L_n(\theta) = \sum_{k=1}^K \pi_{\theta} (a_k|s_n) \hat{Q}(s_n, a_k)\tag{28}$$
其中action space是$\mathcal{A} = {a_1, a_2,\cdots, a_K}$。在大的连续state space中，可以使用importance sampling构建一个新的目标近似。从$s_n$处计算的$L_{\theta_{old}}$的self-normalized 估计是：
$$L_n(\theta) = \frac{\sum_{k=1}^K \frac{\pi_{\theta}(a_{n,k}|s_n)}{\pi_{\theta_{old}}(a_{n,k}|s_n)}\hat{Q}(s_n, a_{n,k})}{\sum_{k=1}^K \frac{\pi_{\theta}(a_{n,k}|s_n)}{\pi_{\theta_{old}}(a_{n,k}|s_n)}}\tag{29}$$
假设在$s_n$处执行了$K$个actions $a_{n,1}, a_{n,2}, \cdots, a_{n,K}$。Self-normalized 估计去掉了$Q$值baseline的需要。在$s_n\sim \rho(\pi)$上做平均，可以得到$L_{\theta_{old}}$和它的gradient的估计。
Vine比single path好的地方在于，给定相同数量的$Q$样本，目标函数的局部估计有更低的方差，也就是vine能更好的估计advantage。Vine的缺点在于，需要执行更多steps的模拟计算相应的advantage。此外，vine方法需要对rollout set 中的每一个state都生成多个trajectories，这就需要整个system可以重置到任意的一个state，而single path算法不需要，可以直接应用在真实的system中。

实用算法

使用上面介绍的single path或者vine进行采样，给出两个算法。重复执行以下步骤：

1. 使用single path或者vine算法产生一系列state-action pairs，使用Monte Carlo估计相应的$Q$值；
2. 利用样本计算公式$(27)$中目标函数和约束函数的估计值
3. 使用共轭梯度和line search求出有约束优化问题的近似解，更新policy参数$\theta$，。

在第$3$步中，使用KL散度的Hessian矩阵而不是协方差矩阵的梯度计算Fisher information matrix，即使用$\frac{1}{N}\sum_{n=1}^N \frac{\partial^2}{\partial \theta_j}D_{KL}(\pi_{\theta_{old}}(\cdot|s_n)||\pi_{\theta}(\cdot|s_n))$近似$A_{ij}$而不是$\frac{1}{N}\sum_{n=1}^N \frac{\partial}{\partial \theta_i}log(\pi_{\theta}(a_n|s_n))\frac{\partial}{\partial \partial_j}log(\pi_{\theta}(a_n|s_n))$。
这个实用算法和前面的理论关联如下：

1. 验证了优化使用KL散度进行约束的目标函数可以保证policy improvement是单调递增的。如果penalty系数$C$很大step会很小，我们想要减小这个系数。经验上来讲，很难选择一个鲁邦的penalty系数，所以我们使用一个KL散度上的一个hard constraint而不是一个penalty。
2. $D_{KL}^{max}(\theta_{old}, \theta)$是很难计算和估计的，所以将约束条件改成对期望$\bar{D}_{KL}(\theta_{old}, \theta)$进行约束。
3. 本文的理论忽略了advantage function的近似误差。

和policy gradient以及natural policy gradient的对比

Policy gradient和natural policy gradient可以看成特殊的trpo，它们可以统一在policy update框架下。The natural policy gradient可以看成公式$(24)$的一个特例：使用$L$的一个linear approximation，和$\bar{D}_{KL}$的一个二次估计，就变成了下面的优化问题：
$$\max_{\theta} \left[\nabla_{\theta}L_{\theta_{old}}(\theta)|_{\theta=\theta_{old}}\cdot (\theta-\theta_{old}) \right]$$
$$s.t. \frac{1}{2}(\theta_{old}-\theta)^T A(\theta_{old})(\theta_{old} - \theta)\le\delta\tag{30}$$
其中$A(\theta_{old})_{ij} = \frac{\partial}{\partial\theta_i}\frac{\partial}{\partial \theta_j}\mathbb{E}_{s\sim \rho_{\pi}}\left[D_{KL}(\pi(\cdot|s, \theta_{old})||\pi(\cdot|s, \theta))\right]_{\theta=\theta_{old}}$，更新公式是$\theta_{new} = \theta_{old}+\frac{1}{\lambda}A(\theta_{old})^{-1} \nabla_{\theta}L(\theta)|_{\theta=\theta_{old}}$，其中步长$\frac{1}{\lambda}$可以看成算法参数。这和trpo不同，在每一次更新都有constraint。尽管这个差别很小，实验表明它能改善在更大规模问题上算法的性能。
同样，也可以使用$l2$约束，推导出标准的policy gradient如下：
$$\max_{\theta} \left[\nabla_{\theta} L_{\theta_{old}}(\theta)|_{\theta=\theta_{old}}\cdot (\theta - \theta_{old})\right] $$
$$s.t. \frac{1}{2}\vert \theta-\theta_{old}\vert^2 \le \delta\tag{31}$$

TRPO算法

TRPO应用了conjugate gradient方法到natural policy gradient，此外，natural policy gradient的trusted region很小，作者将它换成了一个更大的可以调节的值。二次近似可能会降低accuracy，这些可能会对policy的更新引入其他问题，造成performance的degrade。一种可能的解决办法是在进行更新之前先进行验证：

• 新的policy和老的policy之间的的$\text{KL}$散度是不是小于$\delta$
• $L(\theta) \ge 0$

如果验证失败了，使用衰减因子$0\lt \alpha \lt 1$，减小natural policy gradient直到满足要求即可。下面的算法介绍了这种思想的line search solution：
算法 Line Search for TRPO
计算$\Delta_k = \alpha \hat{\text{F}}_k^{-1} \nabla\eta$
for $j=0,1,2,\cdots, t$ do
$\qquad$计算$\theta = \theta_k + \alpha^j \Delta_k$
$\qquad$If $L_{\theta_k}(\theta) \ge 0$或者$\bar{D}_{KL}(\theta||\theta_k) \le \delta$ then
$\qquad\qquad$接受这个更新， $\theta_{k+1} = \theta_k + \alpha^j \Delta_k$
$\qquad\qquad$break
$\qquad$end if
end for
TRPO将truncated natural policiy gradient(使用conjugate gradient)和line search结合起来：
算法 Trust Region Policy Optimization
输入：初始的policy参数$\theta_0$
for $k=0,1,2,\cdots$ do
$\qquad$使用policy $\pi_k = \pi(\theta_k)$收集trajectories到集合$\mathbb{D}_k$
$\qquad$估计优势函数$\hat{A}_t^{\pi_k}$
$\qquad$计算样本估计：
$\qquad\qquad$使用优势函数估计policy gradient $\nabla \eta(\theta)$
$\qquad\qquad$计算$\text{KL}$散度的海塞矩阵（fisher informaction matrix）$\text{H}$
$\qquad$使用共轭梯度算法计算$\hat{\nabla}\eta(\theta) \approx \text{H}^{-1} \nabla\eta(\theta)$
$\qquad$更新$\theta_{k+1} = \theta_k + \alpha \hat{\nabla}\eta(\theta)$
end for

TRPO的缺点

TRPO通过最小化二次泛函近似$\text{F}$的逆，很大程度减少了计算量。但是每一次更新参数还需要计算$\text{F}$。TRPO和其他policy gradient方法相比，采样效率很低，并且扩展性不好，对于很深的网络不适用，这就有了后来的PPO和ACKTR。

Minorize-Maximization MM算法

如上图所示，通过迭代的最大化下界函数局部地逼近expected reward。更详细的来说，随机的初始化$\theta$，在当前$\theta$下，找到下界$M$最接近expected reward $\eta$的点，然后将$M$的最优点作为下一次的$\theta$。不断的迭代，直到收敛到optimal policy。这样做有一个条件，就是$M$要比$\eta$容易优化。比如$M$是二次函数：
$$ax^2 + bx+c\tag{32}$$
用向量形式表示是：
$$g\cdot(\theta- \theta_{old}) - \frac{\beta}{2} (\theta- \theta_{old})^T F(\theta - \theta_{old})\tag{33}$$
是一个convex function。
为什么MM算法会收敛到optimal policy，如果$M$是下界的话，它不会跨过红线$\eta$。假设新的$\eta$中的new policy更低，那么blue线一定会越过$\eta$，和$M$是下界冲突。

Trust Region

有两种优化方法：line search和trust region。Gradient descent是line search方法。首先确定下降的方向，然后超这个方向移动一步。而trust region中，首先确定我们想要探索的step size，然后直到在trust region中的optimal point。用$\delta$表示初始的maximum step size，作为trust region的半径：
$$max_{s\in \mathbb{R}^n} m_k(s), \qquad s.t. \vert s\vert \le \delta\tag{34}$$
$m$是原始目标函数$f$的近似，我们的目标是找到半径$\delta$范围$m$的最优点，迭代下去直到最高点。在运行时可以根据表面的曲率延伸或者压缩$\delta$控制学习的速度。如果在optimal point，$m$是$f$的一个poor approximator，收缩trust region。如果approximatation很好，就expand trust region。如果policy改变太多的话，可以收缩trust region。

参考文献

Trust Region Policy Optimization
1.http://joschu.net/docs/thesis.pdf
2.https://arxiv.org/pdf/1502.05477.pdf
3.https://medium.com/@jonathan_hui/rl-trust-region-policy-optimization-trpo-explained-a6ee04eeeee9
4.https://medium.com/@jonathan_hui/rl-trust-region-policy-optimization-trpo-part-2-f51e3b2e373a
5.https://people.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/KakadeLangford-icml2002.pdf
6.https://drive.google.com/file/d/0BxXI_RttTZAhMVhsNk5VSXU0U3c/view
7.https://zhuanlan.zhihu.com/p/26308073
8.https://zhuanlan.zhihu.com/p/60257706
9.http://rll.berkeley.edu/deeprlcourse/docs/lec5.pdf
10.https://www.zhihu.com/question/316004388

A Natural Policy Gradient

论文名称：A Natural Policy Gradient
论文地址：https://papers.nips.cc/paper/2073-a-natural-policy-gradient.pdf

Abstract

作者基于参数空间的底层结构提出了natural gradient方法，找出下降最快方向。尽管gradient方法不能过大的改变参数，它还是能够朝着选择greedy optimal action而不是更好的action方向移动。基于兼容值函数的policy iteration，在每一个improvement step选择greedy optimal action。

Introduction

直接的policy gradient在解决大规模的MDPs时很有用，这种方法基于future reward的梯度在满足约束条件的一类polices中找一个$\pi$，但是这种方法是non covariant的，简单来说，就是左右两边的维度不一致。
这篇文章基于policy的底层参数结构定义了一个metric，提出了一个covariant gradient方法，通过将它和policy iteration联系起来，可以证明natural gradient朝着选择greedy optimal action的方向移动。通过在简单和复杂的MDP中进行测试，结果表明这种方法中没有出现严重的plateau phenomenon。

Preliminary

1.fisher信息
2.KL散度

A Natural Gradient

定义average reward $\eta(\pi)$为：
$$\eta(\pi) = \sum_{s,a}\rho^{\pi} (s) \pi(a;s) R(s, a) \tag{1}$$
其中$R(s,a) = \mathbb{E}\left[R_{t+1}\right|s_t=s, a_t = a]$，state action value和value function定义如下：
$$Q^{\pi} (s,a) = \sum_{t=0}^{\infty} \mathbb{E}\left[R_t - \eta(\pi)|s_0=s,a_0=a,\pi\right], \forall s\in S, a\in A \tag{2}$$
$$V^{\pi} (s) = \mathbb{E}_{\pi(a’;s)}\left[Q^{\pi}(s,a’)\right] \tag{3}$$
计算average reward的精确梯度是（可以看policy gradient的推导）：
$$\nabla\eta(\theta) = \sum_{s,a} \rho^{\pi} (s) \nabla \pi(a;s,\theta) Q^{\pi} (s,a) \tag{4}$$
使用$\eta(\theta)$代替了$\eta(\pi_{\theta})$。本文中定义$d\theta$的平方长度$\vert d\theta\vert^2 $和一个正定矩阵$\text{G}(\theta)$有关：
$$\vert d\theta\vert^2 = \sum_{ij} \text{G}_{ij} (\theta)d\theta_i d\theta_j = d\theta^T \text{G}(\theta) d\theta \tag{5}$$
在$d\theta$的平方长度$\vert d\theta\vert^2 $ 等于一个常数时，求使得$\eta(\theta+d\theta)$下降的最快的$d\theta$方向。可以证明，最快的梯度下降方向是$\text{G}^{-1} \nabla \eta(\theta)$。标准的policy gradient假设$\text{G}=\text{I}$，所以最陡的下降方向是$\nabla\eta(\theta)$。本文作者的想法是选择一个其他的$\text{G}$，这个新的$G$对应的metric不根据坐标轴的变化而变化，而是跟着坐标参数化的mainfold变化，根据新的metric定义natural gradient。
给出策略$\pi(a;s,\theta)$的fisher information（似然对数的二阶导）：
$$\text{F}_s(\theta) = \mathbb{E}_{\pi(a;s,\theta)} \left[\frac{\partial \log \pi(a;s,\theta)}{\partial \theta_i} \frac{\partial \log \pi(a;s,\theta)}{\partial \theta_j}\right] \tag{6}$$
显然$\text{F}_s$是正定矩阵，可以证明，FIM是概率分布参数空间上的一个invariant metric。不论两个点的坐标怎么选择，它都能计算处相同的distance，所以说它是invariant。当然，$\text{F}_s$使用了单个的$s$，而在计算average reward时，使用的是一个分布，定义$\text{F}$：
$$\text{F}(\theta) = \mathbb{E}_{\rho^{\pi} (s)} \left[\mathbb{F}_s (\theta)\right] \tag{7}$$
每一个$s$对应的单个$\text{F}_s$都和MDP的transition model没有关系，期望操作引入了对transition model参数的依赖。直观上来说，$\text{F}_s$测量的是在$s$上的probability manifold的距离，$\text{F}(\theta)$对它们进行了平均。对应的下降最快的方向是：
$$\hat{\nabla}\eta(\theta) =\text{F}(\theta)^{-1} \nabla\eta(\theta) \tag{8}$$
为什么natural gradient下降最快的方向是这个方向，接下来我们进行证明。其实上面就是说的这些就是使用$\text{KL}$散度当做metric，而不是使用欧几里得metric。然后对$\text{KL}$散度进行约束，要找到使得目标函数$\eta(\theta)$最大的$d\theta$，需要知道哪个方向的$\text{KL}$散度上升的最快，目标函数：
$$d\theta^{*} = \arg \max \eta(\theta +d\theta) \tag{9}$$
$$s.t. \text{KL}\left[p_{\theta}||p_{\theta’}\right] = c \tag{10}$$
其中$c$是常数，确保更新在一定范围内，不受curvature的影响。目标函数的一阶泰勒展开公式如下：
\begin{align*}
\eta_{\theta’}(\theta) & = \eta_{\theta’}(\theta’) + \left[\nabla_{\theta}\eta_{\theta’}(\theta)|_{\theta=\theta’}\right]^T (\theta’ + d\theta - \theta’) + \cdots \\
& = \eta_{\theta’}(\theta’) + \left[\nabla_{\theta}\eta_{\theta’}(\theta)|_{\theta=\theta’}\right]^T d\theta + \cdots \tag{11}\\
\end{align*}

引理$1$：$\text{KL}$散度在$\theta=\theta’$附近$\theta’ +d\theta, d\theta\rightarrow 0$处的二阶泰勒展开是：
$$\text{KL}\left[p(x|\theta’)||p(x|\theta’+d\theta)\right] \approx \frac{1}{2}d\theta^T \text{F}d\theta \tag{12}$$
证明：
\begin{align*}
\text{KL}\left[p_{\theta’}||p_{\theta’+d\theta}\right] &\approx \text{KL}\left[p_{\theta’}||p_{\theta’}\right] + (\nabla_{\theta}\text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’})^T (\theta’+d\theta -\theta’) \\
&\qquad\qquad\qquad\qquad + \frac{1}{2} (\theta’ +d\theta -\theta’)^T (\nabla_{\theta}^2 \text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’})(\theta’+d\theta-\theta’)\tag{13}\\
& = \text{KL}\left[p_{\theta’}||p_{\theta’}\right] + (\nabla_{\theta}\text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’})^T d\theta \\
&\qquad\qquad\qquad\qquad + \frac{1}{2} d\theta^T (\nabla_{\theta}^2 \text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’}) d\theta\tag{14}\\
& = \text{KL}\left[p_{\theta’}||p_{\theta’}\right] + (\int_x p(x|\theta’)\nabla \log (p|\theta)|_{\theta=\theta’} dx)^T d\theta \\
&\qquad\qquad\qquad\qquad + \frac{1}{2} d\theta^T (\nabla_{\theta}^2 \text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’}) d\theta\tag{15}\\
& = \text{KL}\left[p_{\theta’}||p_{\theta’}\right] + (\mathbb{E}_{p(x|\theta’)} \nabla\log p(x|\theta) dx|_{\theta=\theta’})^T d\theta \\
&\qquad\qquad\qquad\qquad + \frac{1}{2} d\theta^T (\nabla_{\theta}^2 \text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’}) d\theta\tag{16}\\
& = 0 + 0 + \frac{1}{2} d\theta^T (\nabla_{\theta}^2 \text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’}) d\theta\tag{17}\\
& = \frac{1}{2} d\theta^T (\nabla_{\theta}^2 \text{KL}\left[p_{\theta}||p_{\theta’}\right]|_{\theta=\theta’}) d\theta\tag{18}\\
& = \frac{1}{2} d\theta^T \text{H} d\theta\tag{19}\\
& = \frac{1}{2} d\theta^T \text{F} d\theta\tag{20}\\
\end{align*}
这也是为什么$\vert d\theta\vert^2 $定义为$d\theta^T\text{G}\theta$的原因。使用拉格朗日乘子法将$\text{KL}$散度约束条件带入目标函数$\eta$：
\begin{align*}
d\theta^{*} & = {\arg \min}_{d\theta} \eta(\theta’+d\theta) + \lambda(\text{KL}\left[p_{\theta’}||p_{\theta’+d\theta}\right] -c)\\
& = {\arg \min}_{d\theta} L_{\theta’}(\theta’) + \left[\nabla_{\theta}L_{\theta’}(\theta)|_{\theta=\theta’}\right]^T d\theta + \lambda(\left[\frac{1}{2} d\theta^T \text{F} d\theta\right] -c)\tag{21}\\
\end{align*}
对$d\theta$求导，令其等于$0$，得：
\begin{align*}
&0 + \nabla_{\theta}\eta_{\theta’}(\theta)|_{\theta=\theta’} + \text{F}d\theta + 0\\
=& \nabla_{\theta}\eta_{\theta’}(\theta)|_{\theta=\theta’} + \text{F}d\theta \tag{22}\\
=& 0\\
\end{align*}
求解得到：
$$d\theta= - \frac{1}{\lambda}\text{F}^{-1} \nabla_{\theta} \eta_{\theta’}(\theta) \tag{23}$$
所以natural gradient定义为：
$$\hat{\nabla}\eta(\theta) = \text{F}^{-1} \nabla_{\theta}\eta(\theta) \tag{24}$$

The Natural Gradient 和 Policy Iteration

使用$\omega$参数化的值函数$f^{\pi} (s,a;\omega)$近似$Q^{\pi} (s,a)$。

Natural Gradient with Approximation（使用近似的自然梯度）

定义：
$$\psi(s,a)^{\pi} = \nabla \log \pi(a;s, \theta)$$
$$f^{\pi} (s,a;\omega) = \omega^T \psi^{\pi} (s,a) \tag{25}$$
其中$\left[\nabla \log \pi(a;s, \theta)\right]_i = \frac{\partial \log \pi(a;s, \theta)}{\partial \theta_i}$。找到最小化均方根误差函数的$\omega$，记为$\hat{\omega}$：
$$\epsilon(\omega, \pi) = \sum_{s,a}\rho^{\pi} (s)\pi(a;s,\theta)(f^{\pi} (s,a;\omega) - Q^{\pi} (s,a))^2 \tag{26}$$
如果使用$f^{\pi} $代替$Q$计算出来的grdient还是exact的，就称$f$是兼容的。

定理1

如果$\hat{\omega}$是使得均方误差$\epsilon(\omega,\pi_\theta)$最小的$\omega$，可以证明：
$$\hat{\omega} = \hat{\nabla} \eta(\theta) =\text{F}(\theta)^{-1} \nabla\eta(\theta) =\text{F}(\theta)^{-1} \nabla\eta(\theta) \tag{27}$$
证明：
因为$\hat{\omega}$使得$\epsilon$最小，所以当$\omega = \hat{\omega}$时，$\frac{\partial \epsilon}{\partial \omega} = 0$，有：
$$\frac{\partial \epsilon}{\partial \omega} = \sum_{s,a}\rho^{\pi} (s) \pi(a|s;\theta) \psi^{\pi} (s,a) (\psi^{\pi} (s,a)^T \hat{\omega} - Q^{\pi} (s,a)) = 0 \tag{28}$$
移项合并同类项得：
$$\sum_{s,a}\rho^{\pi} (s) \pi(a|s;\theta) \psi^{\pi} (s,a) \psi^{\pi} (s,a)^T \hat{\omega} = \sum_{s,a}\rho^{\pi} (s) \pi(a|s;\theta) \psi^{\pi} (s,a) Q^{\pi} (s,a) \tag{29}$$
根据定义$\psi(s,a)^{\pi} = \nabla \log \pi(a;s, \theta)$，而根据log-derativate trick：$\pi(a|s) \nabla \log \pi(a|s;\theta) = \nabla \pi(a|s;\theta)$，所以式子$(29)$右面就是$\nabla \eta$，而式子左面$\sum_{s,a}\rho^{\pi} (s) \pi(a|s;\theta) \psi^{\pi} (s,a) \psi^{\pi} (s,a)^T = \text{F}(\theta)$。最后得到：
$$ \text{F}(\theta)\hat{\omega} = \nabla\eta(\theta)$$

Greedy Policy Improvement

在greedy policy improvement的每一步，在$s$处，选择$a\in \arg \max_{a’} f^{\pi}(s, a’;\hat{\omega})$。这一节介绍natural gradient能够找到best action，而不仅仅是一个good action。
首先考虑指数函数：$\pi(s;a,\theta) \propto e^{\theta^T \phi_{sa}}$，其中$\phi_{sa} \in \mathbb{R}^m $是特征向量。为什么使用指数函数，因为它是affine geometry。简单来说，就是$\pi(a;s,\theta)$的probability manifold可以被弯曲。接下来证明policy在natrual gradient方向上改进的一大步等价于进行一步greedy policy improvement的policy。

定理2

假设$\pi(s;a,\theta) \propto e^{\theta^T \phi_{sa}} $，$\hat{\nabla}\eta(\theta)$是非零的，并且$\hat{\omega}$是最小化均方误差的$\omega$。令
$$\pi_{\infty}(a;s) = lim_{\alpha\rightarrow \infty}\pi(a;s,\theta + \alpha\hat{\nabla}\eta(\theta)) \tag{30}$$
当且仅当$a\in \arg\max_{a’} f^{\pi} (s,a’;\hat{\omega})$时，有$\pi_{\infty}(a;s)\neq 0$。
证明：
根据定义：$f^{\pi} (s,a,\omega) = \omega^T \psi^{\pi} (s,a)$，由定理$1$可知：$\hat{\omega} = \text{F}^{-1} \nabla \eta(\theta) = \hat{\nabla} \eta(\theta)$，所以$f^{\pi}(s,a,\hat{\omega}) = \hat{\nabla}\eta(\theta)^T \psi^{\pi} (s,a)$。而根据定义$\psi^{\pi} (s,a) = \nabla \log \pi(a|s;\theta) = \phi_{sa} - \mathbb{E}_{\pi(a’|s;\theta)}(\phi_{sa’})$，$\mathbb{E}_{\pi(a’|s;\theta)}(\phi_{sa’})$不是$a$的函数，所以就有：
$$\arg\max_{a’}f^{\pi} (s,a’;\hat{\omega}) = \arg\max_{a’} \hat{\nabla}\eta(\theta)^T \phi_{sa}\tag{31}$$
和$\mathbb{E}_{\pi(a’|s;\theta)}(\phi_{sa’})$无关。。经过一个gradient step：
$$\pi(a|s;\theta+\alpha \hat{\nabla}\eta(\theta)) \propto e^{(\theta+\alpha \hat{\nabla}\eta(\theta))^T \phi_{sa}} \tag{32}$$
因为$\hat{\nabla}\eta(\theta) \neq 0$，很明显，当$\alpha\rightarrow \infty$时，$\hat{\nabla}\eta(\theta)^T\phi_{sa}$会dominate，所以只有当且仅当$a\in \arg\max_{a’} f^{\pi} (s,a’;\hat{\omega})$时，有$\pi_{\infty}(a;s)\neq 0$。
可以看出来natural gradient趋向于选择最好的action，而普通的gradient方法只能选出来一个更好的action。
使用指数函数的目的只是为了展示在极端情况下－－有无限大的learning rate情况下的结果，接下来给出的是普通的参数化策略的结果，natural gradient可以根据$Q^{\pi} (s,a)$的局部近似估计$f^{\pi}(s,a;\hat{\omega})$，近似找到局部best action。

定理3

假如$\hat{\omega}$最小化估计误差，使用$\theta’ = \theta + \alpha \hat{\nabla}\eta(\theta)$更新参数，可以得到：
$$\pi(a;s,\theta’) = \pi(a;s,\theta)(1+f^{\pi}(a,s,\hat{\omega})) + O(\alpha^2)\tag{33}$$
证明：
根据定理$1$，得到$\Delta \theta = \alpha\hat{\nabla}\eta(\theta) = \alpha\hat{\omega}$，然后利用一阶泰勒展开：
\begin{align*}
\pi(a|s;\theta’) &= \pi(a|s;\theta) + \frac{\partial \pi(a|s;\theta)^T }{\partial\theta}\Delta\theta + O(\theta^2 ) \\
&= \pi(a|s;\theta) + \frac{\partial\log \pi(a|s;\theta)^T }{\partial\theta}\pi(a|s;\theta)\Delta\theta + O(\theta^2 ) \\
&= \pi(a|s;\theta)(1 + \frac{\partial\log \pi(a|s;\theta)^T }{\partial\theta}\Delta\theta) + O(\theta^2 ) \\
&= \pi(a|s;\theta)(1 + \psi(s, a)^T \Delta\theta) + O(\theta^2 ) \\
&= \pi(a|s;\theta)(1 + \psi(s, a)^T \alpha\hat{\omega}) + O(\alpha^2 ) \\
&= \pi(a|s;\theta)(1 + \alpha f^{\pi} (s, a, \hat{\omega})) + O(\alpha^2 ) \\
\end{align*}
这个相当于是根据$f^{\pi}(s,a) $选择每个state的action。当然，并不是选择greedy action就一定会改善policy，还有许多例外，这里就不细说了。

Metrics和Curvatures

在不同的参数空间中，fisher information都可以收敛到海塞矩阵，因此，它是aymptotically efficient，即到达了cramer-rao bound。
$\text{F}$是$\log \pi$对应的fisher information。Fisher information 和海塞矩阵有关系，但是都需要和$\pi$联系起来。是这里考虑$\eta(\theta)$的海塞矩阵，它和$\text{F}$两个之间有一定联系，但是不一样。
事实上，定义的新的$\text{F}$并不会收敛到海塞矩阵。但是因为海塞矩阵一般不是正定的，所以在非局部最小处附近，它提供的curvature信息用处不大。在局部最小处使用conjugate methods会更好。

Truncated Natural Policy Gradient

Natural policy gradient需要计算$\delta \theta = \alpha \hat{\nabla}\eta(\theta) = \alpha\text{F}^{-1}\nabla(\eta)$。
需要计算费舍尔信息矩阵（$\text{KL}$散度的海塞矩阵）$\text{F}$以及逆矩阵$\text{F}^{-1} $。寻找deep networks逆的代价很大，而且通常是数值不稳定的，我们想要不计算FIM的逆，而直接计算：
$$\hat{\nabla}\eta(\theta) = \text{F}^{-1} \nabla\eta(\theta)$$
进而转化成求解：
$$\text{F}^{-1} \hat{\nabla}\eta(\theta) = \nabla\eta(\theta)$$
因为$\text{F}$是一个对称矩阵，将原问题转化为：
$$\min_{x\in \mathbb{R}^n } \frac{1}{2}x^T \text{F}x - g^T x$$
这个问题可以使用conjugate method求解。
即用求解出来的$x$近似$\hat{\nabla}\eta(\theta) = \text{F}^{-1}\nabla(\eta)$，大大减少了计算量。

参考文献

1.https://papers.nips.cc/paper/2073-a-natural-policy-gradient.pdf
2.https://wiseodd.github.io/techblog/2018/03/14/natural-gradient/
3.https://medium.com/@jonathan_hui/rl-trust-region-policy-optimization-trpo-part-2-f51e3b2e373a
4.https://medium.com/@jonathan_hui/rl-natural-policy-gradient-actor-critic-using-kronecker-factored-trust-region-acktr-58f3798a4a93

Policy Gradient

强化学习有三种常用的方法，第一种是基于值函数的，第二种是policy gradient，第三种是derivative-free的方法，即不利用导数的方法。基于值函数的方法在理论上证明是很难的。这篇论文提出了policy gradient的方法，直接用函数去表示策略，根据expected reward对策略参数的梯度进行更新，REINFORCE和actor-critic都是policy gradient的方法。
本文给出了policy gradient theorem的证明，使用近似的action-value function或者advantage函数，梯度可以表示成experience的估计。同时证明了任意可导的函数表示的policy通过policy iteration都可以收敛到locl optimal policy。

值函数方法的缺点

基于值函数的方法，在估计出值函数之后，每次通过greedy算法选择action。这种方法有两个缺点。

• 基于值函数的方法会找到一个deterministic的策略，但是很多时候optimal policy可能是stochastic的。
• 某个action的估计值函数稍微改变一点就可能导致这个动作被选中或者不被选中，这种不连续是保证值函数收敛的一大障碍。

用函数表示stochastic policy

Policy gradient用函数表示stochastic policy。比如用神经网络表示的一个policy，输入是state，输出是每个action选择的概率，神经网络的参数是policy的参数。用$\mathbf{\theta}$表示policy参数，用$J$表示该策略的performance measure。然后参数$\mathbf{\theta}$的更新正比于以下梯度：
$$\nabla\mathbf{\theta} \approx \alpha \frac{\partial J}{\partial \mathbf{\theta}} \tag{1}$$
其中$\alpha$是正定的step size，按照式子$(1)$进行更新，可以确保$\theta$收敛到$J$的局部最优值对应的local optimal policy。和value based方法相比，$\mathbf{\theta}$的微小改变只能造成policy和state分布的微小改变。

使用值函数辅助学习policy

使用满足特定属性的辅助近似值函数，利用之前的experience就可以得到式子$(1)$的一个无偏估计。REINFORCE方法也找到了式子$(1)$的一个无偏估计，但没有使用辅助值函数，此外它的速度要比使用值函数的方法慢很多。学习一个值函数，并用它取减少方差对快速学习是很重要的。

证明policy iteration收敛性

本文还证明了基于actor-critic和policy-iteration架构方法的收敛性。在这篇文章中，他们只证明了使用通用函数逼近的policy iteration可以收敛到local optimal policy。

Objective Function

三种形式

智能体每一步的action由policy $\pi$决定：$\pi(s,a,\mathbf{\theta})=Pr\left[a_t=a|s_t=s,\mathbf{\theta}\right],\forall s\in S, \forall a\in A,\mathbf{\theta}\in \mathbb{R}^l $。为了方便，通常把$\pi(s,a,\mathbf{\theta})$简写为$\pi(s,a)$。假设$\pi$是可导的，即$\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}}$存在。有三种方式定义智能体的objective：

• 计算policy $\pi$下从初始状态$s_0$开始的accumulated reward：
  $$J(\theta) = V^{\pi}(s_0) = \mathbb{E}_{\pi}\left[G_0\right] = \mathbb{E}_{\pi} \left[\sum_{t=0}^{\infty} \gamma^{t-1} R_t | s_0 \right] \tag{2}$$
  其中$0 \le \gamma \le 1$，在continuing case中，$0 \le \gamma \lt 1$，而在episodic情况下，$\gamma$能取到$1$，$0 \le \gamma \le 1$。
• 计算policy $\pi$每个timestep的immediate reward的均值，即average reward。
  $$J(\theta) = \mathbb{E}_{\pi}\left[R(s, a)\right] = \sum_s d(s) \sum_a\pi(s, a)R(s,a) \tag{3}$$
  在connuting problems情况下，没有episode boundaries，如果不使用discount factor，可以这么做；事实上，我觉得在episodic情况下，也能这么做。
• 当没有明确的初始状态时，计算policy $\pi$下所有state value的均值：
  $$J(\theta) = \sum_s d(s) V^{\pi} (s) = \sum_s d(s) \sum_a\pi(s, a) Q^{\pi} (s, a) = \mathbb{E}_{\pi}\left[Q^{\pi}(s, a)\right] \tag{4}$$

其中$R(s,a) = \mathbb{E}\left[R_{t+1}|s_t=s, a_t=a\right]$，$d (s) = lim_{t\rightarrow \infty} Pr\left[s_t=s|s_0,\pi\right]$是策略$\pi$下的stationary distribution。Stationary distribution的意思是就是不论初始状态是什么，经过很多步之后，都会达到一个stable state。其实这三个目标本质上都是一样的，都是要最大化每个时刻agent得到的reward。

Accumated Reward from Designated State(从指定状态开始的累计奖励)

我们可以指定一个初始状态$s_0$，计算从这个初始状态开始得到的accumulated reward：
$$\eta(\pi) = V^{\pi} (s_0) = \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^{t-1} R_t|s_0\right] = \mathbb{E}_{\pi}\left[G_0 \right]\tag{5}$$
定义return $G_t$如下：
$$ G_t = \sum_{k=0}^{\infty} R_{t+k+1} \tag{6}$$
定义state-action value function和state value function如下：
\begin{align*}
Q^{\pi} (s,a) = \mathbb{E}_{\pi}\left[G_t|s_t=s, a_t=a\right] & = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} R_{t+k+1}|s_t=s,a_t=a\right] \\
V^{\pi} (s) = \mathbb{E}_{\pi}\left[G_t|s_t=s\right] & = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} R_{t+k+1}|s_t=s\right]\\
\tag{7}
\end{align*}
其中$\gamma\in[0,1]$是折扣因子，只有在episodic任务中才允许取$\gamma=1$。它们之间的关系如下：
\begin{align*}
V^{\pi} (s) = \mathbb{E}_{\pi}\left[Q^{\pi} (s,a)|S_t=s\right] & = \sum_a \pi(a|s) Q^{\pi} (s,a) \\
Q^{\pi} (s, a) = \mathbb{E}_{\pi}\left[R_{t+1} + \gamma V^{\pi}(s)|S_t=s, A_t=a\right] & = \sum_{s’,r}p(s’,r|s,a) (r+\gamma V^{\pi} (s’))\\
\tag{8}
\end{align*}
定义$\rho^{\pi} (s)$是从指定的初始状态$s_0$开始，执行策略$\pi$在$t=\infty$之间的任意时刻所有能到达state $s$的折扣概率之和：
$$\rho^{\pi} (s) = \sum_{t=1}^{\infty} \gamma^t Pr\left[s_t = s|s_0,\pi\right] = \sum_{t=0}^{\infty} \gamma^{t} p(s_0\rightarrow s, t,\pi) \tag{9}$$
把$\rho^{\pi} (s) $换一种写法就容易理解了：
$$\rho^{\pi} (s) = P(s_0 = s) +\gamma P(s_1=s) + \gamma^2 P(s_2 = s)+\cdots \tag{10}$$

Average Reward(平均奖励)

Average reward是根据每一个step的的expected reward $\eta(\pi)$对不同的policy进行排名：
$$\eta(\pi) = lim_{t\rightarrow \infty}\frac{1}{t}\mathbb{E}\left[R_1+R_2+\cdots+R_t|\pi\right] = \int_S d(s) \int_A \pi(s,a) R(s,a)dads \tag{11}$$
第一个等号中，$R_t$表示$t$时刻的immediate reward，所以第一个等号表示的是在策略$\pi$下$t$个时间步的imediate reward平均值的期望。第二个等号后，第一个积分是对$s$积分，相当于求的是$s$的期望；然后对$a$的积分，求的是每一个$s$处对应各个动作$a$出现概率的期望，所以第二个等式后面求的其实就是每一步$R(s,a)$平均值的期望。
Return的定义和accumulated reward不同：
$$G_t = \sum_{k=0}^{\infty} \left[R_{t+k+1} - \eta(\pi)\right] \tag{12}$$
因为$G_t$不同，State-action value $Q^{\pi} (s,a)$以及state value $V^{\pi} (s)$的定义和accumulated reward也就不同了：
\begin{align*}
Q^{\pi} (s,a) = \mathbb{E}_{\pi}\left[G_t|s_t=s, a_t=a\right] & = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty}\left( R_{t+k+1} - \eta(\pi)\right)|s_t=s,a_t=a\right]\\
V^{\pi} (s) = \mathbb{E}_{\pi}\left[G_t|s_t=s\right] & = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \left(R_{t+k+1} - \eta(\pi) \right)|s_t=s\right] \\
\tag{13}
\end{align*}
$Q^{\pi} (s,a)$和$V^{\pi} (s,a)$之间的关系满足：
\begin{align*}
Q^{\pi} (s,a) = \sum_{s’, r}p(s’,r|s,a)(r - \eta(\pi) + V(s’)) \tag{14}
\end{align*}

State value的均值

这个和上面的accumulated reward有一定关联，accumulated计算的是$V^{\pi} (s_0)$，而这里计算的是$V^{\pi} (s_0)$的期望（均值）：
$$ \eta(\pi) = \sum_s \rho_0(s_0) V^{\pi} (s) \tag{15}$$
State action value function和state value function的定义和accumulated reward一样。
定义$\rho^{\pi} $为从任意初始状态$s_0$经过$t$步之后state $s$出现的概率：
$$\rho^{\pi} (s) =\int_S \sum_{t=0}^{\infty} \gamma^t \rho_0^{\pi} (s_0) Pr\left[s_t = s|s_0,\pi\right] ds_0 = \int_S \sum_{t=0}^{\infty} \gamma^{t} \rho_0^{\pi} (s_0)p(s_0\rightarrow s, t,\pi)ds_0 \tag{16}$$

Policy Gradient

对于单步的MDP，从分布$\rho^{\pi} (s)$中采样得到$s$，采取action $a$，得到immediate reward $R=R(s,a)$，结束。上面三种目标函数是一样的：
\begin{align*}
J(\theta) & = \mathbb{E}_{\pi}\left[R\right]\\
& = \sum_s d(s) \sum_a \pi(s,a) R(s,a) \tag{17}\\
\end{align*}
求导有问题！！！！怎么求导得到的。。。
\begin{align*}
\nabla_{\theta} J(\theta) & = \sum_s d(s) \sum_a \nabla_{\theta}\pi(s,a) R(s,a)\\
& = \sum_s d(s) \sum_a\pi(s,a) \nabla_{\theta}\log \pi(s,a) R(s,a)\\
& = \mathbb{E}_{\pi}\left[\nabla_{\theta}\log \pi(s,a) R(s,a)\right] \tag{18}\\
\end{align*}
对于多步的MDP，只需要将$R$换成$Q^{\pi} (s, a)$就行了，上面三种目标函数最后都能够得到：
$$\nabla_{\theta} J(\theta) = \sum_s d(s) \sum_a\pi(a|s) \nabla_{\theta} \log\pi(s,a) Q^{\pi} (s,a) = \mathbb{E}_{\pi} \left[\nabla_{\theta} \log\pi(s,a) Q^{\pi} (s,a)\right] \tag{19}$$
其中$Q$是根据不同的目标函数定义的state-action value function，目标函数不同，$Q$定义也不同。在其他论文中，$\nabla_{\theta} \log\pi_{\theta}(s,a)$不变，可以把$Q$换成其他目标函数，GAE这篇论文对不同的目标函数进行了总结。

Policy Gradient Theorem

对于任何MDP，不论是average reward还是accumulated reward的形式，都有：
\begin{align*}
\nabla_{\theta} \eta & = \sum_s \rho^{\pi} (s)\sum_a{\nabla_{\theta}\pi(s,a)}Q^{\pi} (s,a) \\
& = \sum_s \rho^{\pi} (s)\sum_a{\pi(s,a)\nabla_{\theta}\log\pi(s,a)}Q^{\pi} (s,a), \tag{20}\\
& = \mathbb{E}_{\pi}\left[\nabla_{\theta}\log\pi(s,a)Q^{\pi} (s,a)\right], \tag{21}\\
\end{align*}
证明：
\begin{align*}
\nabla V_{\pi}(s) &= \nabla \left[ \sum_a \pi(a|s)Q_{\pi}(s,a)\right], \forall s\in S \\
&= \sum_a \left[\nabla\pi(a|s)Q_{\pi}(s,a)\right], \forall s\in S \\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\nabla Q_{\pi}(s,a)\right] \\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\nabla \left[\sum_{s’,r}p(s’,r|s,a)(R+\gamma V_{\pi}(s’))\right]\right] \\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\nabla \left[\sum_{s’,r}p(s’,r|s,a)R +\sum_{s’,r}p(s’,r|s,a)\gamma V_{\pi}(s’)\right]\right] \\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\left[0 +\sum_{s’,r}p(s’,r|s,a)\gamma\nabla V_{\pi}(s’)\right]\right] \\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\sum_{s’,r}p(s’,r|s,a)\gamma \nabla V_{\pi}(s’))\right] \\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\sum_{s’}\gamma p(s’|s,a)\nabla V_{\pi}(s’) \right] \\
&= \sum_a\\
&\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\sum_{s’}\gamma p(s’|s,a)\left( \sum_{a’} \nabla\pi(a’|s’)Q_{\pi}(s’,a’) + \pi(a’|s’)\sum_{s’’}\gamma p(s’’|s’,a’)\nabla V_{\pi}(s’’))\right) \right] \tag{22}\\
&= \sum_{x\in S}\sum_{k=0}^{\infty} Pr(s\rightarrow x, k,\pi)\sum_a\nabla\pi(a|x)Q_{\pi}(x,a) \tag{23}\\
&= \sum_{x\in S}\rho^{\pi} (x)\sum_a\nabla \pi(a|x) Q_{\pi}(x,a) \tag{24}\\
\end{align*}

式子$(23)$中的$Pr(s\rightarrow x, k, \pi)$是在策略$\pi$下从state $s$经过$k$步转换到state $x$的概率，对第$(14)$步进行展开以后，从状态$s$开始，在每一个$k$都有可能到达状态$x$，如果不能到$x$，概率为$0$就是了。

指定初始状态$s_0$的accumulated reward

证明思路，在上面我们已经求得了$V^{\pi} (s)$的梯度，而accumulated reward其实就是$V^{\pi} (s_0)$，取$J(\mathbf{\theta}) = V_{\pi}(s_0)$，则：
\begin{align*}
\nabla J(\mathbf{\theta}) &= \nabla_{\theta}V_{\pi}(s_0)\\
&= \sum_{s\in S}( \sum_{k=0}^{\infty} Pr(s_0\rightarrow s,k,\pi) ) \sum_a\nabla{\pi}(a|s)Q_{\pi}(s,a)\qquad\qquad\qquad;\rho(s) = \sum_{k=0}^{\infty} Pr(s_0\rightarrow s,k,\pi) \tag{25}\\
&=\sum_{s\in S}\rho(s)\sum_a \nabla{\pi}(a|s)Q_{\pi}(s,a)\tag{26}\\
&=\sum_{s’\in S}\rho(s’)\sum_s\frac{\rho(s)}{\sum_{s’}\rho(s’)}\sum_a \nabla{\pi}(a|s)Q_{\pi}(s,a) \qquad\qquad\qquad\qquad; \text{normalize } \rho(s) \tag{27}\\
&=\sum_{s’\in S}\rho(s’)\sum_sd(s)\sum_a \nabla{\pi}(a|s)Q_{\pi}(s,a) \tag{28} \qquad\qquad\qquad\qquad\qquad; d(s) = \frac{\rho(s) }{\sum_{s’} \rho(s’)} \text{ is stationary distribution}\\
&\propto \sum_{s\in S}d(s)\sum_a\nabla\pi(a|s)Q_{\pi}(s,a)\tag{29},\qquad\qquad\qquad\qquad\qquad\qquad\qquad; \sum_s\rho(s)\text{是常数}\\
& = \sum_{s\in S}d(s)\sum_a\pi(s, a)\nabla\log\pi(a|s)Q_{\pi}(s,a) \tag{30}\\
& = \mathbb{E}_{\pi}\left[\nabla\log\pi(a|s)Q_{\pi}(s,a)\right] \tag{31}\\
\end{align*}
其中$\mathbb{E}_{\pi}$表示$\mathbb{E}_{s\sim d_{\pi}, a\sim \pi}$，即state和action distributions都遵守policy $\pi$。

Average Reward:

证明思路，首先求$V$的梯度，带入$Q, V$和$\eta$的关系进行转换，能够得到$\eta$的梯度和$Q,V$梯度之间的关系，最后进行一系列化简即可。
\begin{align*}
\nabla V_{\pi}(s) &= \nabla \left[ \sum_a \pi(a|s)Q_{\pi}(s,a)\right], \forall s\in S \tag{32}\\
&= \sum_a \left[\nabla\pi(a|s)Q_{\pi}(s,a)\right], \tag{33} \\
&= \sum_a \left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\nabla Q_{\pi}(s,a)\right] \tag{34}\\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\nabla \left[\sum_{s’,r}p(s’,r|s,a)\left(R(s,a)-\eta(\pi)+V_{\pi}(s’)\right)\right]\right] \tag{35}\\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) + \pi(a|s)\left[-\nabla \eta(\pi)+ \sum_{s’,r}p(s’,r|s,a) \nabla V_{\pi}(s’)\right]\right], \nabla R(s,a) = 0\tag{36}\\
&= \sum_a\left[\nabla\pi(a|s)Q_{\pi}(s,a) - \pi(a|s)\nabla \eta(\pi)+ \pi(a|s) \sum_{s’,r}p(s’,r|s,a) \nabla V_{\pi}(s’)\right]\tag{37}\\
&= \sum_a\nabla\pi(a|s)Q_{\pi}(s,a) - \sum_a \pi(a|s)\nabla \eta(\pi) + \sum_a \pi(a|s) \sum_{s’,r}p(s’,r|s,a) \nabla V_{\pi}(s’) \tag{38}\\
&= \sum_a\nabla\pi(a|s)Q_{\pi}(s,a) -\nabla \eta(\pi)+ \sum_a \pi(a|s)\sum_{s’,r}p(s’,r|s,a)\nabla V_{\pi}(s’), \sum_s\pi(s,a)=1\tag{39}\\
\end{align*}
移项合并同类项得：
$$\nabla \eta(\pi) = \sum_a\nabla\pi(a|s)Q_{\pi}(s,a) + \sum_a\pi(s,a) \sum_{s’,r}p(s’,r|s,a) \nabla V_{\pi}(s’) - \nabla V_{\pi}(s) \tag{40}$$
同时在上式两边对$d(s)$进行求和，得到：
\begin{align*}
\sum_s d(s)\nabla \eta(\pi) &= \sum_s d(s)\sum_a \nabla\pi(a|s)Q_{\pi}(s,a) \\
&\qquad\qquad\qquad + \sum_s d(s) \sum_a\pi(a|s) \sum_{s’,r}p(s’,r|s,a) \nabla V_{\pi}(s’)\\
&\qquad\qquad\qquad - \sum_s d(s)\nabla V_{\pi}(s) \tag{41}\\
\nabla \eta(\pi) &= \sum_s d(s)\sum_a \nabla\pi(a|s)Q_{\pi}(s,a) + \sum_s d(s’) \nabla V_{\pi}(s’) - \sum_s d(s)\nabla V_{\pi}(s) \tag{42}\\
&= \sum_s d(s)\sum_a \nabla\pi(a|s)Q_{\pi}(s,a) \tag{43}\\
&= \sum_s d(s)\sum_a \pi(s,a) \nabla\log\pi(a|s)Q_{\pi}(s,a) \tag{44}\\
& = \mathbb{E}_{\pi}\left[\nabla_{\theta}\log\pi(s,a) Q_{\pi}(s,a)\right] \tag{45}\\
\end{align*}
式子$(41)$到式子$(42)$其实就是$\sum_s d(s) \sum_a\pi(a|s) \sum_{s’,r}p(s’,r|s,a) = \sum_{s’}d(s’)$，根据$\rho^{\pi} (s)$表示的意义，显然这是成立的。
\begin{align*}
\end{align*}

State value的期望

还不会证明。

结论

从这两种情况的证明可以看出来，policy gradient和$\frac{\partial \rho^{\pi} (s)}{\partial\mathbf{\theta}}$无关：即可以通过计算，让policy的改变不影响states distributions，这非常有利于使用采样来估计梯度。举个例子来说，如果$s$是根据policy $\pi$的从$\rho$中采样得到的，那么$\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}}Q^{\pi} (s,a)$就是$\frac{\partial{\rho}}{\partial\mathbf{\theta}}$的一个无偏估计。通常$Q^{\pi}(s,a)$也是不知道的，需要估计。一种方法是使用returns近似，即$G_t = \sum_{k=0}^{\infty} R_{t+k+1}-\rho(\pi)$或者$R_t = \sum_{k=0}^{\infty} \gamma^{t} R_{t+k+1}$（在指定初始状态条件下），这就是REINFROCE方法。$\nabla\mathbf{\theta}\propto\frac{\partial\pi(s_t,a_t)}{\partial\mathbf{\theta}}R_t\frac{1}{\pi(s_t,a_t)}$,$\frac{1}{\pi(s_t,a_t)}$纠正了$\pi$的oversampling）。

Policy Gradient with Approximation(使用近似的策略梯度)

因为$Q^{\pi} $是不知道的，我们希望用函数近似式子$(21)$中的$Q^{\pi} $，大致求出梯度的方向。用$f_w:S\times A \rightarrow \mathbb{R}$表示$Q^{\pi} $的估计值。在策略$\pi$下，更新$w$的值:
$$\Delta w_t\propto \frac{\partial}{\partial w}\left[\hat{Q}^{\pi} (s_t,a_t) - f_w(s_t,a_t)\right]^2 \propto \left[\hat{Q}^{\pi} (s_t,a_t) - f_w(s_t,a_t)\right]\frac{\partial f_w(s_t,a_t)}{\partial w} \tag{67}$$
$\hat{Q}^{\pi} (s_t,a_t)$是$Q^{\pi} (s_t,a_t)$的一个无偏估计，当这样一个过程收敛到local optimum，$Q^{\pi} (s,a)$和$f_w(s,a)$的均方误差最小时：
$$\epsilon(\omega, \pi) = \sum_{s,a}\rho^{\pi} (s)\pi(a|s;\theta)(Q^{\pi} (s,a))^2 - f^{\pi} (s,a;\omega) \tag{68}$$
即导数等于$0$:
$$\sum_s \rho^{\pi} (s)\sum_a\pi(a|s;\theta)\left[Q^{\pi} (s,a) -f_w (s,a;w)\right]\frac{\partial f_w(s,a)}{\partial w} = 0\tag{69}$$

定理2：Policy Gradient with Approximation Theorem

如果$f_w$的参数$w$满足式子$(69)$，并且：
$$\frac{\partial f_w(s,a)}{\partial w} = \frac{\partial \pi(s,a)}{\partial \mathbf{\theta}}\frac{1}{\pi(s,a)} = \frac{\partial \log \pi(s,a)}{\partial \mathbf{\theta}}\tag{70}$$
那么使用$f_w(s,a)$计算的gradient和$Q^{\pi} (s,a)$计算的gradient是一样的：
$$\frac{\partial \rho}{\partial \theta} = \sum_s\rho^{\pi} (s)\sum_a\frac{\partial \pi(s,a)}{\partial \mathbf{\theta}}f_w(s,a)\tag{71}$$

证明：
将式子$(70)$代入$(69)$得到：
\begin{align*}
&\sum_s\rho^{\pi} (s)\sum_a\pi(s,a)\left[Q^{\pi} (s,a) -f_w(s,a)\right]\frac{\partial f_w(s,a)}{\partial w}\\
= &\sum_s\rho^{\pi} (s)\sum_a\pi(s,a)\left[Q^{\pi} (s,a) -f_w(s,a)\right]\frac{\partial \pi(s,a)}{\partial \mathbf{\theta}}\frac{1}{\pi(s,a)}\\
= &\sum_s\rho^{\pi} (s)\sum_a\frac{\partial \pi(s,a)}{\partial \mathbf{\theta}}\left[Q^{\pi} (s,a) -f_w(s,a)\right] \tag{72}\\
= & 0 \\
\end{align*}
将式子$72$带入式子$(21)$：
\begin{align*}
\frac{\partial \eta}{\partial \mathbf{\theta}} & = \sum_a \rho^{\pi} (s)\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}}Q^{\pi} (s,a)\\
&= \sum_a \rho^{\pi} (s)\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}}Q^{\pi} (s,a) - \sum_s\rho^{\pi} (s)\sum_a\frac{\partial \pi(s,a)}{\partial \mathbf{\theta}}\left[Q^{\pi} (s,a) -f_w(s,a)\right]\\
&= \sum_a \rho^{\pi} (s)\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}} \left[Q^{\pi} (s,a) - Q^{\pi} (s,a) +f_w(s,a)\right]\\
&= \sum_a \rho^{\pi} (s)\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}} f_w(s,a) \tag{73}\\
\end{align*}
得证$\sum_a \rho^{\pi} (s)\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}}Q^{\pi} (s,a) = \sum_a \rho^{\pi} (s)\sum_a\frac{\partial\pi(s,a)}{\partial\mathbf{\theta}} f_w(s,a) $。

Application to Deriving Algorithms and Advantages

给定一个参数化的policy，可以利用定理2推导出参数化value function的形式。比如，考虑在features上进行线性组合的Gibbs分布构成的policy：
$$\pi(a|s) = \frac{e^{\theta^T \phi_{sa} } }{\sum_b e^{\theta^T \phi_{sb} }} , \forall s \in S, \forall a \in A \tag{74}$$
其中$\phi_{s,a}$是state-action pair $s,a$的特征向量。满足式子$(70)$的公式如下：
$$\frac{\partial f_w(s,a)}{\partial w} = \frac{\partial \pi(a|s)}{\partial \theta}\frac{1}{\pi(a|s)} = \phi_{sa} - \sum_b\pi(b|s)\phi_{sb}\tag{75}$$
所以：
$$f_w(s,a) = w^T \left[\phi_{sa} - \sum_b\pi(b|s)\phi_{sb} \right]\tag{76}$$
也就是说，$f_w$和policy $\pi$都是feature的线性组合，只不过每一个state处$f_w$的均值都为$0$，$\sum_a\pi(a|s)f_w(s,a) = 0,\forall s\in S$。所以，其实我们可以认为$f_w$是对advantage function $A^{\pi} (s,a) = Q^{\pi} (s,a)- V^{\pi} (s)$而不是$Q^{\pi} (s,a)$的一个近似。式子$(70)$中$f_w$其实是一个相对值而不是一个绝对值。事实上，他们都可对以推广变成一个function加上一个value function。比如式子$(71)$可以变成$\frac{\partial\eta}{\partial \theta} = \sum_s\rho^{\pi}(s) \sum_a \frac{\partial \pi(a|s)}{\partial \theta}\left[f_w(s,a) + v(s)\right]$，其中$v$是一个function，$v$的选择不影响理论结果，但是会影响近似梯度的方差。

Convergence of Policy Iteration with Function Approximation(使用函数近似的策略迭代的收敛性)

定理3：Policy Iteration with Function Approximation

用$\pi$和$f_w$表示policy和value function的可导函数，并且满足式子$(70)$。$\max_{\theta,s,a,i,j} \vert\frac{\partial^2 \pi(a|s)}{\partial\theta_i \partial\theta_j} \vert\lt B\lt \infty$，假设$\left[\alpha_k\right]_{k=0}^{\infty}$是步长sequence，$\lim_{k\rightarrow \infty}\alpha_k = 0$，$\sum_k \alpha_k = \infty$。对于任何有界rewards的MDP来说，任意$\theta_0$，$\pi_k=\pi(\cdot, \theta_k)$定义的$\left[\eta(\pi_k)\right]_{k=0}^{\infty}$，并且$w_k = w$满足：
$$\sum_s\rho^{\pi_k} (s) \sum_a\pi_k(a|s)\left[Q^{\pi_k} (s,a)-f_w(s,a) \right]\frac{\partial f_w(s,a)}{\partial w}=0 \tag{77}$$
$$\theta_{k+1} = \theta_k + \alpha_k \sum_s\rho^{\pi_k}(s) \sum_a\frac{\partial\pi_k(s,a)}{\partial \theta}f_{w_k}(s,a) \tag{78}$$
一定收敛：$\lim_{k\rightarrow \infty}\frac{\partial \rho(\pi_k)}{\partial \theta} = 0$。

Policy Gradient Algorithms

REINFORCE

REINFORCE使用Monte Carlo方法近似return $G_t$，因为$Q^{\pi} (s,a) = \mathbb{E}_{\pi}\left[G_t|s_t=s, a_t=a\right]$使用$G_t$代替policy gradient theorem中的$Q$：
\begin{align*}
\nabla_{\theta}J(\theta) & = \mathbb{E}_{\pi}\left[Q^{\pi} (s,a) \nabla_{\theta}\log\pi_{\theta}(a|s)\right]\\
& = \mathbb{E}_{\pi} \left[G_t\nabla_{\theta}\log\pi_{\theta}(a|s)\right]\\
\end{align*}
接下来进行sampling，使用Monte Carlo方法计算$G_t$即可。完整算法如下：
REINFORCE 算法
输入：policy $\pi$的初始化参数$\theta$，step-size $\alpha$
Loop
$\qquad$使用$\pi_{\theta}$生成一个trajectory $S_0, A_0, R_1, S_1, A_1, \cdots$
$\qquad$for $t=1, 2, \cdots, T$
$\qquad\qquad$估计$G_t = \sum_{k=t}^T \gamma^{k-t} R_{t+1}$
$\qquad\qquad$更新$\theta \leftarrow \theta + \alpha \gamma^t G_t \nabla_{\theta}\log\pi_{\theta}(a_t|s_t)$
$\qquad$end for

REINFORCE with Baseline

REINFROCE的一类变种是在$G_t$的基础上减去一个和$\theta$无关的baseline，作用是在不改变bais的前提下减少方差：
$$\sum_a \nabla_{\theta}\pi(a|s) b(s) = b(s) \nabla_{\theta}\sum_a\pi(a|s) = b(s) \nabla_{\theta} 1 = 0$$
即加了一个baseline之后，梯度更新的期望值依然保持不变，但是可以减少方差。具体的证明可以见why use baselinse in policy gradient。在MDPs中，有的state可能所有的actions都有很高的values，这时候需要一个high baseline，而有的actions可能都有低的values，这时候需要一个low baseline，一个常用的baseline可以选择$V(s)$，可以使用$G_t - V^{\pi} (s,a)$计算梯度。
直观上来首，RL感兴趣的是那些比平均值好的action。如果returns都是正的$(R(\tau)\ge 0)$，PG总是会提高这个trajectory发生的概率，即使它比其他的trajectory要低。考虑以下两个例子：

• Trajectory $A$的return是$10$，trajectory $B$的reward是$-10$
• Trajectory $A$的return是$10$，trajectory $B$的reward是$1$

在第一个例子中，PG会提高$A$发生的概率，降低$B$发生的概率。在第二个例子中，PG会提高$A$和$B$的概率。然而，对于我们来说，在两个例子中，我们都想要降低$B$发生的概率，提高$A$发生的概率。通过引入一个baseline，比如$V$，我们就可以实现这样的目的。
完整算法如下：
REINFORCE with Baseline 算法
输入：可导的policy $\pi$的初始化参数$\theta$，可导的state value function $\hat{v}(s, \mathbf{w})$，step-size $\alpha^{\theta} \gt 0, \alpha^{w} \gt 0 $
Loop
$\qquad$使用$\pi_{\theta}$生成一个trajectory $S_0, A_0, R_1, S_1, A_1, \cdots$
$\qquad$for $t=1, 2, \cdots, T$
$\qquad\qquad$近似$G_t = \sum_{k=t}^T \gamma^{k-t} R_{t+1}$
$\qquad\qquad$近似$\delta \leftarrow G-\hat{v}(s_t, w)$
$\qquad\qquad$更新$w\leftarrow w + \alpha^{w} \delta \nabla\hat{v}(s_t, w)$
$\qquad\qquad$更新$\theta \leftarrow \theta + \alpha^{\theta} \gamma^t\delta\log\pi_{\theta}(a_t|s_t)$
$\qquad$end for
和介绍的原理不同的是，REINFORCE with Baselien使用了近似的$\hat{v}(s, \mathbf{w}) \approx V(s)$，因为我们不知道真实的$Q$，前面也已经证明了。。

Actor-Critic

Policy gradient中两个常用的components是policy和value function，在学习policy的同时学习一个value function是非常有用的，value function可以辅助policy进行更新，比如vanilla policy gradient使用value function辅助policy减小方差，我们把这类方法统称为actor-critic方法。Value function和policy可以共享参数：

• Critic利用mean squared error更新value function $Q_w(s,a)$或者$V_w(s)$的参数$w$；
• Actor根据critic给出的更新方向更新policy $\pi_{\theta}(a|s)$的参数$\theta$。

One-step actor-critic方法使用one-step return代替了full return。完整的算法按如下：
One-step actor critic 算法
输入：policy $\pi$的参数$\theta$，初始化state $s_0$
采样$a\sim \pi(a|s)$
Loop
$\qquad$for $t= 1,\cdots, T$:
$\qquad\qquad$采样reward $r_t \sum R(s,a)$和next state $s’\sim P(s’|s,a)$
$\qquad\qquad$采样next action $s’\sim \pi(a’|s’)$
$\qquad\qquad$更新policy参数$\theta \leftarrow \theta + \alpha_{\theta} Q_w(s,a) \nabla_{\theta}\log\pi_{\theta}(a|s)$
$\qquad\qquad$计算timestep $t$时刻的TD-error：
$\qquad\qquad\qquad \delta_t = r_t + \gamma Q_w(s’, a’) - Q_w(s,a)$
$\qquad\qquad\qquad$使用mean squared error更新$Q$函数：
$\qquad\qquad\qquad w\leftarrow w + \alpha_w \delta_t \nabla_w Q_w(s, a)$
$\qquad\qquad\qquad a\leftarrow a’, s\leftarrow s’$
$\qquad$end for

REINFORCE with baseline的方法同时学习了policy $\pi$和state value function $V$，但是我们一般不把它叫做actor-critic方法，因为$V$在这里是一个baseline而不是一个critic。它没有被用作bootstraping，只是用作待更新state的一个baseline。bootstraping和state representation引入了bias，但是能减小方差和加快学习速度。REINFORCE with baseline是无偏的，并且收敛到local minimum，但是像所有的MC方法一样，它都收敛的很慢，也有很大的方差，并且很难应用到online和continuing问题。使用TD方法可以解决这个问题，并且通过multi-step可以控制boostrapping的度。为了得到policy gradient的方法，可以使用boostrapping critic的actor critic方法。

Off-Policy Policy Gradient

REINFORCE和one-step actor-critic都是on-policy的，behaviour policy和target policy是相同的，很低效。Off-polciy相对于on-policy有几个好处：

• 可以使用过去的experience，即experience replay提高采样效率；
• behaviour policy和target policy不同，能够更好的进行exploration。

如何使用计算off policy graadient，这就牵涉到了importance sampling。用$\beta(a|s)$表示behaviour oplicy，目标函数为：
$$J(\theta) = \sum_s d^{\beta} (s) \sum_a Q^{\pi} (s,a) \pi(a|s) = \mathbb{E}_{s\sim d^{\beta} } \left[\sum_a Q^{\pi} (s,a) \pi(a|s)\right]$$
其中$d^{\beta} (s)$是behaviour policy $\beta$的stationary distrbution， $\pi$是target policy。
实际上$a\sim \beta(a|s)$，对$J(\theta)$求偏导得到：
\begin{align*}
\nabla_{\theta}J(\theta) & = \nabla_{\theta} \mathbb{E}_{s\sim d^{\beta} }\left[ \sum_a Q^{\pi} (s, a) \pi_{\theta} (a|s)\right]\\
& = \mathbb{E}_{s\sim d^{\beta} }\left[ \sum_a\left(\nabla_{\theta} Q^{\pi} (s, a) \pi_{\theta} (a|s) + Q^{\pi} (s, a) \nabla_{\theta}\pi_{\theta} (a|s)\right)\right]\\
& \approx \mathbb{E}_{s\sim d^{\beta} }\left[ \sum_a Q^{\pi} (s, a) \nabla_{\theta}\pi_{\theta} (a|s)\right]\\
& \approx \mathbb{E}_{s\sim d^{\beta} }\left[\sum_a \beta(a|s)\frac{ \pi(a|s)}{\beta(a|s)} Q^{\pi} (s, a) \frac{\nabla_{\theta}\pi_{\theta} (a|s)}{\pi_{\theta}(a|s)}\right]\\
& \approx \mathbb{E}_{\beta}\left[\sum_a \frac{ \pi(a|s)}{\beta(a|s)} Q^{\pi} (s, a) \nabla_{\theta}\log\pi_{\theta} (a|s)\right]\\
\end{align*}
其中$\frac{ \pi(a|s)}{\beta(a|s)}$称作importance sampling ratio。式子$(55)$到式子$(44)$忽略了第二项，有人狰狞了即使忽略了这一项，最终结果还会收敛到局部最优。
即通过importance sampling可以将过去policy的experience用于新policy的训练。

A3C

详细的解释可以见A3C。
A3C是Asynchronous advantage actor-critic，是并行的policy gardient，就是为并行训练设计的。在A3C中，多个actors并行采样进行训练，一个critic学习value function。
A3C算法的实质就是使用多个线程同步训练。分为主网络和线程中的网络，主网络不需要训练，主要用来存储和传递参数，每个线程中的网络用来训练参数。总的来说，多个线程同时训练提高了效率，另一方面，减小了数据之间的相关性，比如，线程$1$和$2$中都用主网络复制来的参数计算梯度，但是同一时刻只能有一个线程更新主网络的参数，比如线程$1$更新主网络的参数，那么线程$2$利用原来主网络参数计算的梯度会更新在线程$1$更新完之后的主网络参数上。

A3C算法－－每个actor-learn线程的伪代码
用$\theta, w$表示全局共享参数，用$T=0$表示全局共享计数器，
用$\theta’,w’$表示每个线程中的参数
初始化线程步计数器$t\leftarrow 1$，
while $T\le T_{max}$
$\qquad$重置梯度$d\theta\leftarrow 0, dw\leftarrow 0$，
$\qquad$同步线程参数$\theta’=\theta,w’=w$
$\qquad t_{start}=t$
$\qquad$采样初始状态$s_t$，
$\qquad$ while $s_t \neq$ terminal且$t-t_{start} \le t_{max}$
$\qquad\qquad$根据策略选择action$a_t \sim \pi_{\theta’}(a_t|s_t;\theta’)$，
$\qquad\qquad$接收下一个状态$s_{t+1}$和reward $r_{t+1}$，
$\qquad\qquad T\leftarrow T+1, t\leftarrow t+1$
$\qquad$设置奖励$R=\begin{cases}0,&for\ terminal\ s_t\\ V(s_t,\theta’_v), &for\ non-terminal\ s_t\end{cases}$
$\qquad$for $i\in{t-1,\cdots,t_{start}}$ do
$\qquad\qquad R\leftarrow r_i+\gamma R$
$\qquad\qquad$累计和$\theta’$相关的梯度：$d\theta \leftarrow d\theta+\frac{\partial (y-Q(s,a;\theta))^2}{\partial \theta}$
$\qquad\qquad$累计和$\theta’_v$相关的梯度：$d\theta_v \leftarrow d\theta_v+\frac{\partial (R-V(s_i;\theta’_v))^2}{\partial \theta’_v}$
$\qquad$end for
$\qquad$使用$d\theta$异步更新$\theta$，使用$d\theta_v$异步更新$\theta_v$.

累计梯度$dw$和$d\theta$其实可以看成是mini-batch的sgd。

A2C

A2C是A3C的同步版本。在A3C中每一个agent独立的和global parameters进行沟通，所以可能在某些时候，不同的thread使用的policy可能都会不同，thread1从global拿了参数，计算梯度，thread2从global拿了参数，计算梯度，thread1更新了global，而这个时候thread2还在计算梯度，thread1就拿到了新的global参数，计算梯度，更新。这时候thread2还没计算完，就产生了不一致。
A2C就是为了解决这个问题的，A2C使用一个调度器，等待所有的actors完成相应的工作，然后更新global的参数，保证在下一次更新的时候每一个actor使用的都是相同的policy。

DPG

完整解释见deterministic policy gardient。
Deterministic policy gradient theorem：
\begin{align*}
J(\mu_{\theta}) & = \int_S\rho^{\mu} (s) R(s, \mu_{\theta}(s)) da ds\tag{48}\\
& = \mathbb{E}_{s\sim \rho^{\mu} } \left[R(s, \mu_{\theta}(s) \right]\tag{49}\\
\end{align*}

\begin{align*}
\nabla_{\theta} J(\mu_\theta) & = \int_S\rho^{\mu} (s)\nabla_{\theta}\mu_{\theta}(s) \nabla_a Q^{\mu} (s, a)|_{\mu_{\theta}(s)} da ds\tag{50}\\
& = \mathbb{E}_{s\sim \rho^{\mu} (s)} \left[ \nabla_{\theta}\mu_{\theta}(s) \nabla_a Q^{\mu} (s, a)|_{\mu_{\theta}(s)} \right]\tag{51}\\
\end{align*}

DDPG

DDPG是一个model-free off-plicy actor critic方法，将DPG和DQN的思想相结合。DQN使用replay buffer和target network稳定学习过程，但是DQN只有在discrete space空间中起作用，DDPG将actor-critic框架扩展到了continous空间，学习deterministic policy。为了更好的exploration，使用$\mu$和noise $\mathbf{N}$构造exploration policy $\mu’$：
$$\mu’(s) = \mu(s) + \mathbf{N} \tag{}$$
此外，DDPG对actor和critic实行soft update，即$\theta’ \leftarrow \tau \theta+(1-\tau) \theta’$。同时使用batch normalizion对每层的输入进行处理，完整的算法如下：
DDPG算法
使用$\theta^Q $和$\theta^\mu $ 随机初始化critic网络$Q(s,a|\theta^Q )$和actor网络$\mu(s|\theta^\mu )$。
使用$\theta^ Q$和$\theta^\mu $初始化target network参数$\theta^{Q’} \leftarrow \theta^Q, \theta^{\mu’} \leftarrow \theta^\mu$。
初始化replay buffer
for episode $= 1, \cdots, M$ do
$\qquad$初始化随机过程$\mathbf{N}$用于exploration
$\qquad$获得初始状态$s_0$
$\qquad$for $t=0, \cdots, T$ do
$\qquad\qquad$选择action $a_t = \mu(s_t|\theta^\mu ) + \mathbf{N}_t$
$\qquad\qquad$执行$a_t$，获得$r_{t+1}, s_{t+1}$
$\qquad\qquad$将$(s_t, a_t, r_{t+1}, s_{t+1})$存入buffer
$\qquad\qquad$从buffer中获取一个大小为$N$的batch，$(s_i, a_i, r_{i+1}，s_{i+1})$
$\qquad\qquad$使用target network计算TD target：$y_i = r_i + \gamma Q’(s_{i+1}, \mu’(s_{i+1}|\theta^{\mu’} ) | \theta^{Q’} )$
$\qquad\qquad$使用TD-error loss更新critic： $L=\frac{1}{N} \sum_i (y_i - Q(s_i,a_i|\theta^Q ) )^2 $
$\qquad\qquad$使用样本计算policy gradient更新actor：
$$\nabla_{\theta^{\mu} } J \approx \frac{1}{N} \sum_i \nabla_a Q(s, a|\theta^Q ) |_{s=s_i,a=\mu(s_i)} \nabla_{\theta^{\mu} }\mu(s|\theta^{\mu} )$$
$\qquad\qquad$更新target networks:
$$\theta^{Q’} \leftarrow \tau \theta^Q + (1 - \tau) \theta^{Q’} $$
$$\theta^{\mu’} \leftarrow \tau \theta^\mu + (1 - \tau) \theta^{\mu’} $$
$\qquad$end for
end for

MADDPG

MADDPG将DDPG扩展到multi agents问题上。多个只有local informaction的agents合作完成任务，从单个agent来看，环境是non-stationary，因为其他agents的polices是未知的。MADDPG就是解决这样一类问题的方法。
对于$N$个agetns的MADDPG算法，每一个agent都有一个decentralized actor和一个centralized critic。每一个decentralized actor输入为当前agent的observation，输出为它的action，每一个centralized critic输入为所有agents的observation，输出为当前agent的$Q$值，和每个智能体的reward相关。

完整的算法如下：
N个agents的MADDPG算法
for episode $= 1, \cdots, M$ do
$\qquad$初始化随机过程$\mathbf{N}$用来exploration
$\qquad$获得初始状态$\mathbf{s}$
$\qquad$for $t=1, \cdots , T$ do
$\qquad\qquad$for $i = 1, \cdots, N$
$\qquad\qquad\qquad a_i = \mu_{\theta_i}(o_i) +\mathbf{N}_t$
$\qquad\qquad$end for
$\qquad\qquad$执行actions $\mathbf{a} = (a_1, \cdots, a_N)$，获得$\mathbf{r}$和$\mathbf{s’}$
$\qquad\qquad$将$(\mathbf{s},\mathbf{a},\mathbf{r},\mathbf{s’})$存入buffer
$\qquad\qquad \mathbf{s}\leftarrow \mathbf{s’}$
$\qquad\qquad$for $i= 1, \cdots, N$ do
$\qquad\qquad\qquad$从buffer中采样$S$个samples $(\mathbf{s}^j ,\mathbf{a}^j ,\mathbf{r}^j ,\mathbf{s’}^j )$
$\qquad\qquad\qquad$计算TD target $\mathbf{y}^j_i = \mathbf{r}^j_i + \gamma Q^{\mu’}_i (\mathbf{x’}^j, a_1^{’},\cdots, a_N^{’} )|_{a_k^{’} = \mu_k^{’} (o_k^j ) }$
$\qquad\qquad\qquad$使用均方误差更新critic：
$$L(\theta_i) = \frac{1}{S} \sum_j \left( y^j - Q_i^{\mu} (\mathbf{x}^j , a_1^j ,\cdots, a_N^j ) \right)^2 $$
$\qquad\qquad\qquad$使用样本近似计算policy gradient：
$$\nabla_{\theta_i} J\approx \frac{1}{S} \sum_j\nabla_{\theta_i}\mu_i(o_i^j ) Q_i^{\mu} (\mathbf{x}^j , a_1^j ,\cdots, a_i^j, a_N^j)|_{a_i = \mu_i(o_i^j)} $$
$\qquad\qquad$end for
$\qquad\qquad$更新每个agent $i$的target network
$$\qquad\qquad \theta_i^{’} \leftarrow \tau\theta_i + (1- \tau) \theta_i^{’}$$
$\qquad$end for
end for

D4PG

Natural PG

TRPO

详细介绍可以查看trust region policy optimization。
TRPO将policy的更新表示为两个policy的performance的一个公式：
\begin{align*}
\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new} }\left[\sum_{t=0}^{\infty} \gamma^t A^{\pi_{old}} (s_t,a_t) \right] &=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}}\left[\sum_{t=0}^{\infty} \gamma^t (Q^{\pi_{old}} (s_t,a_t) - V^{\pi_{old}} (s_t))\right] \\
&=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t ( R_{t+1} + \gamma V^{\pi_{old}} (s_{t+1}) - V^{\pi_{old}} (s_t))\right] \\
&=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t R_{t+1} + \sum_{t=0}^{\infty} \gamma^t (\gamma V^{\pi_{old}} (s_{t+1}) - V^{\pi_{old}} (s_t))\right] \\
&=\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t R_{t+1} \right]+ \mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[\sum_{t=0}^{\infty} \gamma^t (\gamma V^{\pi_{old}} (s_{t+1}) - V^{\pi_{old}} (s_t))\right] \\
&=\eta(\pi_{new}) + \mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[ - V^{\pi_{old}} (s_0))\right] \\
&=\eta(\pi_{new}) - \mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new}} \left[ V^{\pi_{old}} (s_0))\right] \\
&=\eta(\pi_{new}) - \eta(\pi_{old})\\
\end{align*}
我们的目标就是想要最大化
$$\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new} }\left[\sum_{t=0}^{\infty} \gamma^t A^{\pi_{old}} (s_t,a_t) \right]$$
用$\rho_{\pi_{old}}(s)$近似$\rho_{\pi_{new}}(s)$得到
$$\mathbb{E}_{s_0, a_0,\cdots\sim \pi_{new} }\left[\sum_{t=0}^{\infty} \gamma^t A^{\pi_{old}} (s_t,a_t) \right]$$

最后得到目标函数：
$$J = \mathbb{E}_{s\sim\rho_{\theta_{old}}, a\sim q}\left[\frac{\pi_{\theta} (a|s) }{q(a|s)}Q_{\theta_{old}}(s,a)\right] \tag{}$$

为了训练的稳定性，我们应该避免在一个step内policy改变太大。TRPO通过添加一个KL散度约束每一次迭代中，policy改变的大小。
$$s.t. \mathbb{E}_{s\sim \rho_{\theta_{old}}}\left[D_{KL}(\pi_{\theta_{old}}(\cdot|s)||\pi_{\theta}(\cdot|s))\right]\le \delta \tag{}$$

PPO

ACER

ACTKR

SAC

SAC with Automatically Adjusted Temperature

TD3

SVPG

另一种policy gradient的方法

这是CS294上的方法，感觉和前面的有一些不成体系，而且有一些地方的证明让我不能接受。
目标函数$J$如下：
\begin{align*}
J(\theta) & = \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[R(\tau)\right] \tag{46}\\
& = \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[\sum_t R(s_t, a_t)\right] \tag{47}\\
& = \int \pi_{\theta}(\tau) R(\tau) d\tau \tag{48}\\
& = \int \pi_{\theta}(\tau)\sum_t R(s_t, a_t) d\tau \tag{49}\\
& \approx \frac{1}{N}\sum_i \sum_t R(s_{i,t}, a_{i,t}) \tag{50}\\
\end{align*}
其中$\tau = s_0, a_0, s_1, a_1,\cdots \sim \pi_{\theta}$表示一个episode的trajectory，$R(\tau)$表示这个trajectory的returns($G_0$)。Policy gradient变成下式，（为什么？？？还是不懂！！CS294上面的推导！！！为什么$\nabla$可以写进积分号里面，$R(\tau)$不也和$\pi_{\theta}$有关？？？）
\begin{align*}
\nabla_{\theta}J(\theta) & = \int \nabla_{\theta} \pi_{\theta}(\tau) R(\tau)d\tau\\
& = \int \pi_{\theta}(\tau) \nabla_{\theta}\log\pi_{\theta}(\tau) R(\tau)d\tau\\
& = \mathbb{E}_{\tau\sim \pi_{\theta}(\tau)} \left[\nabla_{\theta} \log\pi_{\theta}(\tau) R(\tau) d\tau\right] \tag{51}
\end{align*}
可以将policy gradient表示成期望的形式，然后就可以采样进行估计。对$R(\tau)$进行采样，但是不进行求导。Returns不直接受$\pi_{\theta}$的影响，$\tau$受$\pi_{\theta}$的影响，下面是$\log\pi(\tau)$的偏导数计算。
$\pi(\tau)$定义为：
$$\pi_{\theta}(s_0,a_0,\cdots, s_T,a_T) = p(s_0) \prod_{t=0}^T \pi_{\theta}(a_t|s_t)p(s_{t+1}|s_t,a_t) \tag{52}$$
取$\log$：
$$\log\pi_{\theta}(s_0,a_0,\cdots, s_T,a_T) = \log p(s_0) + \sum_{t=0}^T\log \pi_{\theta}(a_t|s_t) + \log p(s_{t+1}|s_t,a_t) \tag{53}$$
对$\theta$求偏导，得到：
$$\nabla_{\theta} \log\pi(\tau) = \nabla_{\theta}\left[\sum_{t=0}^T \log\pi_{\theta}(a_t|s_t) \right] = \left[\sum_{t=0}^T \nabla_{\theta} \log\pi_{\theta}(a_t|s_t) \right]\tag{54}$$
所以，policy gradient：
\begin{align*}
\nabla_{\theta}J(\theta) &= \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)}\left[\nabla_{\theta}\log\pi_{\theta}(\tau) R(\tau) \right]\tag{55}\\
& = \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \left(\sum_{t=1}^T\nabla_{\theta} \log\pi_{\theta}(a_{i,t}|s_{i,t})\right) \left(\sum_{t=1}^T R(s_{i,t}, a_{i,t})\right) \right] \tag{56}\\
& \approx \frac{1}{N}\sum_{i=1}^N \left(\sum_{t=1}^T\nabla_{\theta} \log\pi_{\theta}(a_{i,t}|s_{i,t})\right) \left(\sum_{t=1}^T R(s_{i,t}, a_{i,t})\right)\tag{57}\\
\end{align*}
$$ \theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)\tag{58}$$
即用多个trajectories近似计算policy gradietn，更新$\theta$。

REINFORCE: Policy Gradient with Monte Carlo rollouts

REINFROCE使用Monte Carlo近似returns，$\nabla_{\theta}J(\theta)$近似为：

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N}\sum_{i=1}^N \left(\sum_{t=1}^T\nabla_{\theta} \log\pi_{\theta}(a_{i,t}|s_{i,t})\right) \left(\sum_{t=1}^T R(s_{i,t}, a_{i,t})\right)$$
完整的算法如下：
REINFORCE 算法
Loop
$\qquad 1.$使用policy $\pi_{\theta}(a_t|s_t)$生成一个trajectory $\left[\tau^i \right]$
$\qquad$估计$\nabla_{\theta}J(\theta) \approx \sum_i (\sum_t \nabla_{\theta} \log\pi_{\theta}(a_t^i |s_t^i )) (\sum_t R(s_t^i , a_t^i ))$
$\qquad \theta\leftarrow \theta+\alpha\nabla_{\theta}J(\theta)$
Until 收敛

Intution

$\nabla_{\theta} \log\pi_{\theta}(a_{i,t}|s_{i,t})$是最大对数似然，表示的是对应的trajectory在当前的policy下发生的可能性。将它和returns相乘，如果产生high positive reward，增加policy的可能性，如果是high negetive reward，减少policy的可能性。在一个trajectory中的states具有很强的相关性，这个trajectory发生的概率定义为：
$$\pi(\tau) = p(s_0) \prod_{t=0}^T \pi_{\theta}(a_t|s_t)p(s_{t+1}|s_t,a_t) \tag{59}$$
但是连续的乘法可能会产生梯度消失或者梯度爆炸问题。policy gradient将连乘变成了连加。

Policy Gradients Improvements

Policy gradient的方差很大，而且很难收敛，这是一大问题。
MC方法根据整个trajectory计算exact rewards，但是stochastic policy可能会在不同的episode采取不同的actions，一个小的改变可能会完全改变结果，MC方法没有bias但是有很大的方差。方差会影响深度学习的优化，一个采样的reward可能想要增加似然，另一个样本rewards可能想要减少似然，给出了冲突的梯度方向，影响收敛性。为了减少选择action造成的方差，我们需要减少样本rewards的方差：
$$\left( \sum_{t=1}^T R(s_{i,t}, a_{i,t})\right)\tag{60}$$
增大PG中的batch size会减少方差。
但是增大batch size会降低sample efficiency。所以batch size不能增加太多，我们需要想其他的方法减少方差：

Causality

未来的action不应该改变过去的decisions：
$$\nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_{\theta}\log\pi_{\theta}(a_{i,t}|s_{i,t}) \left(\sum_{t’=t}^T R(s_{i,t’};a_{i,t’})\right)\tag{61}$$
可以用$Q$代替$\sum_t R(s,a)$，
$$\nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_{\theta}\log\pi_{\theta}(a_{i,t}|s_{i,t}) Q_{i,t}\tag{62}$$
为什么会减少方差？

Baseline

$$\nabla_{\theta}J(\theta) \approx \frac{1}{N}\sum_{i=1}^N \left(\sum_{t=1}^T\nabla_{\theta} \log\pi_{\theta}(a_{i,t}|s_{i,t}\right) \left(\sum_{t=1}^T R(s_{i,t}, a_{i,t})\right)\tag{63}$$
中$\sum_{t=1}^T R(s_{i,t}, a_{i,t})$其实就是$Q(s,a)$，我们可以在上面减去一项，只要这一项和$\theta$无关就好，所以我们可以减去$V(s)$：
\begin{align*}
\nabla_{\theta} J(\theta) & \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_{\theta}\log\pi_{\theta}(a_{i,t}|s_{i,t})\left(Q(s_{i,t}, a_{i,t}) - V(s_{i,t})\right)\\
& = \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_{\theta}\log\pi_{\theta}(a_{i,t}|s_{i,t})\left(A(s_{i,t}, a_{i,t})\right)\\
\end{align*}

Vanilla Policy Gradient

给出一个使用baseline $b$的通用算法：
$$ \nabla\approx \hat{g} = \frac{1}{m} \sum_{i=1}^m \nabla_{\theta}\log P(\tau^{(i)} ;\theta)(R(\tau^{(i)} )-b)\tag{64}$$
Vanilla policy gradient算法
初始化policy 参数$\theta$，baselien $b$
for $i = 1, 2, \cdots$ do
$\qquad$使用当前policy $\pi_{\theta}$收集trajectories
$\qquad$在每个trajectory的每一个timestep，计算
$\qquad\qquad$return $G_t = \sum_{t’=t}^{T-1} \gamma^{t’-t} R_{t’}$
$\qquad\qquad$advantage的估计值$\hat{A}_t = R_t - b(s_t)$
$\qquad$重新拟合baseline，最小化$\vert b(s_t) - G_t\vert^2 $
$\qquad$在所有trajectories和timesteps上求和估计$\hat{g}$
$\qquad$使用policy gradient estimate $\hat{g}$的估计$\hat{g}$更新policy 参数
end for

Reward discount

加上折扣因子：
$$Q^{\pi,\gamma}(s, a) \leftarrow r_0 + \gamma r_1 + \gamma^2 r_2 + \cdots|s_0 = s, a_0 = a \tag{65}$$
得到：
$$\nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \left(\sum_{t=1}^T \nabla_{\theta}\log\pi_{\theta}(a_{i,t}|s_{i,t}) \right) \left(\sum_{t’=t}^T \gamma^{t’-t} R(s_{i,t’};a_{i,t’})\right)\tag{66}$$

参考文献

1.https://papers.nips.cc/paper/1713-policy-gradient-methods-for-reinforcement-learning-with-function-approximation.pdf
2.https://papers.nips.cc/paper/2073-a-natural-policy-gradient.pdf
3.https://medium.com/@jonathan_hui/rl-policy-gradients-explained-9b13b688b146
4.https://medium.com/@jonathan_hui/rl-policy-gradients-explained-advanced-topic-20c2b81a9a8b
5.https://www.jianshu.com/p/af668c5d783d
6.https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#what-is-policy-gradient
7.https://drive.google.com/file/d/0BxXI_RttTZAhY216RTMtanBpUnc/view
8.https://danieltakeshi.github.io/2017/03/28/going-deeper-into-reinforcement-learning-fundamentals-of-policy-gradients/
9.https://danieltakeshi.github.io/2017/04/02/notes-on-the-generalized-advantage-estimation-paper/
10.http://www.tuananhle.co.uk/notes/reinforce.html
11.http://kvfrans.com/simple-algoritms-for-solving-cartpole/

Quantifying Generalization in Reinforcement Learning

下载地址

https://arxiv.org/pdf/1812.02341.pdf

摘要

这篇文章研究的是drl中的overfitting问题。在绝大多数的RL benchmark中，训练和测试都习惯性的在相同环境中，这就让agent’s的泛化能力不够优秀。本文通过程序生成环境构建不同的training set和testing set解决这个问题，设计了一个新的CoinRun环境用于RL的generalization。
实验证明更深的cnn能够改善generalization，监督学习中常用的一些方法，如$L2$正则化，dropout，data augmentation以及batch normalization。
这篇文章的贡献：

1. transfer需要的训练环境数量要远远高于之前的工作中使用到的。
2. 使用CoinRun benchmark提出了一个generalization metric。
3. 找到了不同网络结构和正则化项中最好的那些设置。

Related Work

这篇文章是从Sonic benchmark中得到的idea，agents可以在training set上训练任意的长度，在test时候执行$1$ million timesteps进行fine-tuning，sonic benchmark的目标是解决"training on the test set"的问题。

简介

尽管RL agents能解决很复杂的任务，将experience迁移到新环境，或者在不同的RL tasks之间进行泛化是很困难的。即使已经掌握了$10$ video game的agents，在初次遇到第$11$级时也会失败，agents在训练的时候只学习到了和这个环境相关的知识。
RL agents的训练其实是过拟合的，但是绝大多数的benchmark还是鼓励在相同的环境中进行train和evaluation。和Sonic Benchmark一样，作者认为分train和test集是必要的，同时作者认为量化agent的泛化能力也是很有用的。
Sonic Benchmark通过对环境划分训练集和测试集，解决了在测试集上训练的问题。而Farebrother认识到，没有划分训练集和测试集，使得RL训练中缺乏正则化手段，通过使用监督学习中的$L2$正则化和dropout，使得agents能够学习更多泛化特征。
Zhang等利用程序生成划分train和test环境，他们在gridworld mase上进行实验，得出了许多RL agents为什么过拟合的结论。通过让agents记住在训练集中具体的levels，以及stick actions，random starts，可以减少过拟合的发生。

Quantifying Generalization

CoinRun

CoinRun环境很简单，一个智能体，从最左边，一直往右走，收集在最右边的金币，中间或均匀或随机的散布着一些障碍，只有得到金币后有一个常数的reward。一个episode结束有以下三种可能性：

• 当agent死亡，
• 或者采集到coin，
• 或者$1000$个timesteps后自动结束。

CoinRun和Sonic很像，但是更简单，更容易泛化。给定足够数量的training levels和足够的training time，算法能够学习一个接近最优的optimal policy for all CointRun levels。每一个level都是从一个给定的seed中顺序生成的，能够给智能体相当多并且易于量化提供的training data。

CoinRun泛化曲线

使用CoinRun可以衡量agents从给定的training level中训练迁移到没有见过的test levels上的效果。随着training中使用的levels数量增多，即使是训练固定的timesteps时，我们期望在test set上的性能变好。test时，作者在test set上进行了zero-shot performance评估，即没有在test set上进行fine-tuning。
作者训练了$9$个agents 运行CoinRun，每一个都在具有不同levels数量的训练集上运行。训练过程中，每一个episode从相应的set中随机采样一个level。前$8$个agents使用的train sets中level的数量从$100$到$16000$，最后一个agent在无限个levels的训练集上。Level的seed是$2^32$，所以几乎不可能发生冲突。训练集包含$2$M个独一无二的levels，在test的时候仍然不会遇到已经遇到过的level。整个实验进行了$5$次，每次重新生成training sets。
使用nature-dqn中的三层CNN进行训练，然后使用$8$个workers的PPO总共训练了$256M$步。每个agents都训练相同的timesteps，然后在每个mini-batch的$8$个works上取gradients的均值。
最后的结果中，对$10000$个episodes的final performance进行平均，我们可以看出来，在$4000$个levels以内，过拟合很严重，即使是$1600$个training levels，过拟合也是很多的。当agents遇到的都是新的levels时，表现最好。

Evaluating Architectures

比较Nature-CNN和IMPALA-CNN，结果证明IMPALA-CNN要好一些。为了评估generalization performance，可以直接在无限个levels的train set上训练agents，然后比较learning curves。在这个settings中，智能体不可能过拟合某一些levels的子集，每一个level都是新的。因为Impala-cnn的记过更好，所以作者尝试了更深的网络，发现效果更好，新的网络使用了$5$个residual blocks，每层的channels数量是原来的两倍。再进一步增加网络深度的时候，发现了returns逐渐变小，同时花费的时间也更多了。
当然，使用无限的training set并不会总是会带来性能的提升。选择好的超参数能够加快训练速度，但是并不一定会改善generalization的性能。通常来讲，在固定levels的训练集上训练，能产生一个更有用的metric。

Evaluating Regularization

正则化在监督学习中有很重要的作用，因为监督学习更关心的是generalization。监督学习的数据集通常分为训练集和数据集，有很多正则化技巧可以用来减少generalization gap。但是因为RL中训练集和测试集通常是同一个，所以正则化技术就没什么效果。
现在既然RL中要衡量generalization，可能正则化技术就能起到作用。作者分别在CoinRun environment中试了$L2$正则化，dropout，data augmentation以及batch normalization。
这一节中，所有的agents都是在$500$个levels的CoinRun环境中进行的。我们可以看到有过拟合发生，所以就希望这个setting能够evaluating出不同正则化技术的效果。所有接下来实验的均值和方差都是runs$3$次得到的。使用的是有$3$个残差块的IMPALA-CNN。

Dropout和L2正则化

作者分别试了dropout为$p\in [0, 0.05, 0.10, 0.15, 0.20, 0.25]$，以及L2正则化权重$w\in [0, 0.5, 1.0, 1.5, 2.0, 2.5]\times 10^{-1} $，一次只试了一个。最终找到了$p=0.1$以及$w=10^{-4} $。使用$L2$正则化训练了$256M$ timesteps，使用dropout训练了$512M$ timesteps，dropout更难收敛，而且效果没有$L2$正则化好用。

Data Augmentation

监督学习中，数据增强的手段主要用于图像，包括变换，旋转，亮度调整，锐化等等。不同的数据集可能需要使用不同的augmentations。这里作用使用的是Cutout的一个变形。对于每一个observation，可变大小的矩阵区别被masked掉，这些masked的区域给一个随机的颜色，这个和domain randomization非常相似，用于机器人从仿真到真实世界的transfer。

Batch Normalization

在IMPALA-CNN架构中每层CNN之后使用batch normalization。

Stochasticity

这个随机性很有意思哦。作者考虑了两种方法，一种是改变环境的stochasticity，另一个是改变policy的stochasticity。首先，使用$\epsilon$-greedy action selection算法向环境中加入stochasticity，在每一个timestep中，有$\epsilon$的概率，使用random action代替policy的action。在之前的一些研究中，$\epsilon$-greedy用来鼓励exploration和防止overfitting。然后，通过改变PPO中的entropy bonus控制policy stochasticity。Baseline中使用的entropy bonus是$k_H = 0.01$。
同时增加训练时间步到$512M$个timesteps。单独向环境或者policy加入stochasticity都能改善generalization。

Combining Regularization Methods

作者尝试将data augmentation,batch normalization和L2结合起来，结果表明比任意单独的一种都要好，但是提升的大小并不是很大，可以说这三种方法解决的过拟合问题差不多。
由于某些未知的原因，将stochastic和正则化手段结合起来的效果不理想。

其他环境

CointRun-Platforms

RandomMazes

参考文献

1.https://arxiv.org/pdf/1804.03720.pdf
2.https://arxiv.org/pdf/1812.02341.pdf

凸函数(convex functions)

参考文献

1.stephen boyd. Convex optimization

GCC

GCC是GUN项目下的编译器驱动程序，它可以将文件形式的源代码文件翻译成一个可执行的目标文件。这个翻译过程总共包含四个阶段，执行这四个阶段的程序（预处理器cpp，编译器cc1，汇编器as，链接器ld）组成了编译器驱动程序。

快速入门

1. 保存c++源文件为hello_world.c

1
2
3
4
5

#include <stdio.h>
int main(){
    printf("hello world.\n");
    return 0;
}

2. 使用gcc 编译

gcc -o hello_world hello_world.c

3. 执行编译后的源文件
   ./hello_world

选项

• [-Wall]，允许发出gcc提供的所有有用的警告。
• [-std=standard]，指定C标准的版本，standard取值为c99, c11, gnu89等
• [-Og]，指定编译器优化级别，为debug可用，
• [-m32]，指定编译成32位程序。
• [-m64]，指定编译成64位程序。

参考文献

1.https://legacy.gitbook.com/download/pdf/book/lexdene/gcc-five-minutes

先给出已知条件，两个列向量$a= (x_1,y_1, z_1), w=(x_2,y_2, z_2)$。

点积(dot product)

定义

点积，又叫数量积，定义为$a\cdot b = x_1 x_2 + y_1y_2 + z_1z_2$。
另一种定义方式是$a\cdot b = \vert a \vert \vert b \vert cos <a, b>$`
这两种定义方式实际上是一样的：

叉积(cross product)

定义

叉积，又叫向量积，定义为$\vert a\times b \vert = \vert a \vert \vert b \vert sin <a, b>$，最后得到一个方向和$a,b$都正交的向量，并且方向符合右手规则。向量积的大小等于$a,b$构成的平行四边形的面积。

属性

1. $a\times b, b\times a$是方向相反的
2. $a,b$的叉积垂直于$a$和$b$
3. 任意向量和它自己的叉积为$0$。

混合积(trple product)

定义

混合积定义为$(a\times b) \cdot c$，它的绝对值等于以$a,b,c$三个向量构成的形状的体积。

属性

向量$a\times b$是一个向量，$a\times b$的大小相当于底面积，方向垂直于$a,b$所有的平面，再和$c$点乘，乘上了$c$投影到$a,b$点乘结果所在的直线上，相当于乘上了高。

参考文献

1.MIT线性代数公开课

特征值和特征向量

这里介绍的东西都是针对于方阵来说的。

定义

$Ax=\lambda x $，满足该式子的$x$称为矩阵$A$的特征向量，相应的$\lambda$称为特征值。

求解

将$Ax=\lambda x$进行移项，得到$(A-\lambda I) x =0$，其中$A-\lambda I$必须是sigular（即不可逆），如果$A - \lambda I$是非奇异矩阵，也就是说它的列向量相互独立，那么只有零解，无意义。令$det (A-\lambda I)=0$，求出相应的$\lambda$和$x$。

属性

1. $n$个特征值的乘积等于行列式。
2. $n$个特征值之和等于对角线元素之和。

迹

定义

主对角线元素之和叫做迹（trace）。
$$\lambda_1 +\cdots + \lambda_n = trace = a_{11} + \cdots + a_{nn}$$

矩阵对角化

定义

如果合适的使用矩阵$A$的特征向量，可以把$A$转换成一个对角矩阵。
假设$n\times n$的矩阵$A$有$n$个线性独立的特征向量$x_1,\cdots, x_n$，把它们当做列向量，构成一个新的矩阵$S=\left[x_1, \cdots, x_n\right]$。
$$AS = A\left[x_1, \cdots, x_n\right] = \left[\lambda_1 x_1, \cdots, \lambda_n x_n\right] = \left[x_1, \cdots, x_n\right] \begin{bmatrix} \lambda_1 &\cdots & 0 \\ \vdots&\lambda_i & \vdots\\ 0& \cdots & \lambda_n\end{bmatrix} = S\Lambda$$
即$AS = S\Lambda$，所以有$S^{-1} AS = \Lambda, A = S\Lambda S^{-1} $，这里我们假设$A$的$n$个特征向量都是线性无关的。$A, \Lambda$的特征值相同，特征向量不同。$A$的特征向量用来对角化$A$。

属性

如果一个矩阵有$n$个不同的实特征值，那么它一定可对角化。
如果存在重复的特征值，可能但不一定可对角化，单位矩阵就有重复特征值，但可对角化。

可逆和对角化

矩阵可逆和矩阵可对角化之间没有关联。
矩阵可逆和特征值是否为$0$有关，而矩阵可对角化与特征向量有关，是否有足够的线性无关的特征向量。

矩阵的幂

矩阵幂

$A= S\Lambda S^{-1} $,
$A^2 = S\Lambda S^{-1}S\Lambda S^{-1} = S\Lambda^2 S^{-1} $,
$A^k = S\Lambda^k S^{-1}$
所以，$A^k $和$A$的特征向量相同，特征值是$\Lambda^k $。当$k\rightarrow \infty$时，如果所有的特征值$\lambda_i \lt 1$，那么$A^k \rightarrow 0$。

以解方程组$u_{k+1} = Au_k$

从给定的向量$u_0$开始，$u_1 = Au_0, u_2 = Au_1, u_k = A^k u_0$
假设$u_0 = c_1 x_1 + c_2 x_2 + \cdots + c_nx_n$，$x_1, \cdots, x_n$是一组正交基。
$Au_0 = c_1 \lambda_1 x_1 + \cdots + c_n\lambda_n x_n$
$u_{100} = A^{100} u_0 = c_1 \lambda_1^{100} x_1 + \cdots + c_n \lambda_n^{100} x_n$
$u_{100} = A^{100} u_0 = \Lambda^{100} S c$

微分方程

指数矩阵

Markov Matrices

定义

马尔科夫矩阵满足两个条件

1. 所有元素大于$0$
2. 行向量之和为$1$

属性

1. $\lambda = 1$是一个特征值，对应的特征向量的所有分量大于等于$0$。可以直接验证，假设$A = \begin{bmatrix}a&b\\c&d\\ \end{bmatrix}, a + b = 1, c + d = 1$，$A-\lambda I = \begin{bmatrix}a - 1&b\\c&d - 1\\ \end{bmatrix}$，所有元素加起来等于$0$，即$(A-I)(1, \cdots, 1)^T = 0$，所以这些向量线性相关，因为存在一组不全为$0$的系数使得他们的和为$0$。所以$A-I$是奇异矩阵，也就是说$1$是$A$的一个特征值。
2. 所有其他的特征值小于$1$。

马尔科夫矩阵的幂

$u_k = A^k u_0 = c_1 \lambda_1^k x_1 + c_2 \lambda_2^k x_2 + \cdots$
如果只有一个特征值为$1$，所有其他特征值都小于$1$，幂运算之后$\lambda^k \rightarrow 0, k\rightaroow \infty, \lambda_k \neq 1$。

对称矩阵

定义

满足$A= A^T $的矩阵$A$被称为对称矩阵。

属性

1. 实对称矩阵的特征值都是实数
   证明：由$Ax= \lambda x$，得到$A\bar{x} = \bar{\lambda} \bar{x}$，$\bar{x}$是$x$的共轭，转置得：
   $$\bar{x}^T A^T = \bar{x}^T A = \bar{x}^T \bar{\lambda}$$
   $Ax = \lambda x$的左边乘上$\bar{x}^T $，在$\bar{x}^T A = \bar{x}^T \lambda$的右边同时乘上$x$：
   $$\bar{x}^T Ax = \bar{x}^T \lambda x = \bar{x}^T A x= \bar{x}^T \bar{\lambda} x$$
   即$\bar{x}^T \lambda x = \bar{x}^T \bar{\lambda} x$，而$\bar{x}^T x= \vert x\vert \ge 0 $，如果$x\neq 0$，则$\lambda = \bar{\lambda}$，即$\lambda$的虚部为$0$，即特征值都是实数。
2. 对称矩阵有单位正交的特征向量。
   证明：假设$S = \left[v_1, \cdots, v_i, \cdots, v_n\right]$是矩阵$A$的特征向量矩阵，根据矩阵对角化公式：
   $$A = S \Lambda S^{-1} $$
   而$A=A^T $，所以得到
   $$S\Lambda S^{-1} = A = A^T = \left(S \Lambda S^{-1} \right)^T = S^{-T} \Lambda^T S^T = S^{-T} \Lambda S^T $$
   可以得出$S^T = S^{-1} $，所以$S S^T = I$，即$v_i^T v_i = 1, v_i^T v_j = 0, \forall i\neq j$。
3. 所有的对称矩阵都是可对角化的。

谱定理（Spectral Theorem）

对称矩阵的对角化可以从$A=S\Lambda S^{-1} $变成$A=Q\Lambda Q^{-1} =Q\Lambda Q^T $。
谱定理：每一个对称矩阵都有以下分解$A = Q\Lambda Q^T $，$\Lambda$是实特征值，$Q$是单位正交向量矩阵。
$$A = Q\Lambda Q^{-1} = Q\Lambda Q^T $$
$A$是对称的，$Q \Lambda Q^T $也是对称的。

正定矩阵

正定矩阵，负定矩阵，半正定矩阵，半负定矩阵都是对于对称矩阵来说的。

定义

如果对于所有的非零向量$x$，$x^T Ax$都是大于$0$的，我们称矩阵$A$是正定矩阵。

属性

1. 所有的$n$个特征值都是正的
2. 所有的$n$个左上行列式都是正的
3. 所有的$n$个主元都是正的
4. 对于任意$x\neq 0$，$x^T A x$大于$0$。
5. $A=R^T R$，$R$是一个具有$n$个独立column的矩阵。

如果任意矩阵$A$拥有以上属性中的任意一个，那么它就有其他四个性质，或者说上面五个属性都可以用来判定矩阵是否为正定矩阵。

半正定矩阵

如果对于所有的非零向量$x$，$x^T Ax$都是大于等于$0$的，我们称矩阵$A$是半正定矩阵。

属性

对于任何矩阵$A$，$A^T A$和$A A^T $都是对称矩阵，并且它们一定是半正定矩阵。
假设$A = \begin{bmatrix} a&b\\c&d\end{bmatrix}$，如何判断$A^T A$是不是正定的？根据定义，判断$x^T (A^T A) x$的符号：
$$x^T (A^T A) x = x^T A^T Ax = (Ax)^T (Ax) = \vert Ax \vert $$
相当于计算向量$Ax$的模长，它一定是大于等于$0$的。
同理$A A^T $的二次型相当于计算$A^T x$的模长，大于等于$0$。

参考文献

1.MIT线性代数公开课
2.http://maecourses.ucsd.edu/~mdeolive/mae280a/lecture11.pdf

行列式（Determinants）

这一章介绍行列式相关知识，行列式的一些属性等等。

• 矩阵不可逆，行列式为$0$。
• 主元的乘积是行列式。
• 交换任意两行和两列，行列式的符号改变。
• 行列式的绝对值等于这个矩阵描述的space的体积。
• 行列式的计算公式有三个：
  1. 主元公式，就是所有主元的乘积
  2. big formula
  3. cofact formula

定义以及性质

行列式用det表示，给出以下的几个属性：

1. $n\times n$的单位矩阵$I$的行列式$det I = I$
   $$\begin{vmatrix}1&0\\0&1 \end{vmatrix} = 1$$
2. 交换任意两行，行列式符号取反。
   $$\begin{vmatrix}a&b\\c&d \end{vmatrix} = - \begin{vmatrix}c&d\\a&b \end{vmatrix}$$
3. 行列式是每一行的线性函数
   $$\begin{vmatrix}ta&tb\\c&d \end{vmatrix} = t \begin{vmatrix}a&b\\c&d \end{vmatrix}$$
   $$\begin{vmatrix}a+a’&b+b’\\c&d \end{vmatrix} = \begin{vmatrix}a’&b’\\c&d \end{vmatrix}+\begin{vmatrix}a&b\\c&d \end{vmatrix}$$

以上的三个属性是行列式的性质，事实上，它们定义了行列式是什么，从这几个基本属性出发，我们能推导出更多的属性。

4. 如果$A$的两行相等，那么$det A=0$，交换两行，还是矩阵$A$，行列式变号，所以行列式只能为$0$。
   假设$A = \begin{bmatrix}a&b\\a&b \end{bmatrix}$，$\begin{vmatrix}a&b\\a&b \end{vmatrix}= - \begin{vmatrix}a&b\\a&b \end{vmatrix}$
5. 从某一行减去其他行的倍数，行列式不变
   $$\begin{vmatrix}a&b\\c- la&d-lb \end{vmatrix}= \begin{vmatrix}a&b\\c&d \end{vmatrix} -l \begin{vmatrix}a&b\\a&b\end{vmatrix} = \begin{vmatrix}a&b\\c&d \end{vmatrix}$$
6. 某一行为$0$矩阵，行列式为$0$。
   $$\begin{vmatrix}0&0\\c&d \end{vmatrix} = \begin{vmatrix}c&d\\c&d \end{vmatrix} = 0$$
7. 如果$A$是三角矩阵，行列式的值等于对角元素乘积。
   $$\begin{vmatrix}a&b\\0&d \end{vmatrix} = \begin{vmatrix}a&0\\c&d \end{vmatrix} = \begin{vmatrix}a&0\\0&d \end{vmatrix} = ad \begin{vmatrix}1&0\\0&1 \end{vmatrix} = ad$$
8. 当且仅当$A$不可逆的时候，$det A\neq 0$
   $det A = det U$，如果$A$不可逆，$U$中有零行，从$6$我们知道，行列式为$0$。如果$A$可逆，行列式的值等于主元的乘积。
9. 矩阵$AB$的行列式等于矩阵$A$的行列式以及矩阵$B$的行列式。
   $$\begin{vmatrix}a&b\\c&d \end{vmatrix}\begin{vmatrix}p&q\\r&s \end{vmatrix} = \begin{vmatrix}ap+br&aq+bs\\cp+dr&cq+ds \end{vmatrix}$$
   证明：
   对于$2\times 2$的情况，有$\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix} = (ad - bc) ( ps - qr) = (ap + br) (cq+ds) - (aq+bs)(cp+dr) \begin{vmatrix}AB \end{vmatrix}$
   当$B$是$A^{-1} $的时候，有$det (A A^{-1}) = det (I) = 1 = det (A) det(A^{-1} )$，所以$det A^{-1} = \frac{1}{det A}$
10. $A^T$和$A$的行列式相同。
    $PA=LU, A^T P^T = U^T L^T$，$det L = det L^T = 1, det U = det U^T $，$L$是对角线元素为$1$的对角矩阵，$U$是对角矩阵，$P$是置换矩阵，$P^T P = I$，$det P det P^T = 1$，则$det P = det P^T = 1$，这个为什么？我有点不明明白。最后有$det A = det A^T $。

行列式的计算

主元公式

行列式等于主元的乘积。

大公式

$n=2$的情况下：
$$A= \begin{bmatrix} a & b\\c&d\\\end{bmatrix}$$
$$det A = \begin{vmatrix}a&0\\c&d\end{vmatrix}+\begin{vmatrix}0&b\\c&d\end{vmatrix} = \begin{vmatrix}a&0\\c&0\end{vmatrix}+\begin{vmatrix}a&0\\0&d\end{vmatrix}+\begin{vmatrix}0&b\\c&0\end{vmatrix} \begin{vmatrix}0&b\\0&d\end{vmatrix} = ad - bc$$
$n=3$的情况下，最后有六项不为$0$的取值，$3!= 3\times 2\times 1= 6$
在$n$的情况下，有$n!$个项，将它们加起来求和。

代数余子式（Cofactors）

定义

用$C$表示代数余子式，用$M_{ij}$表示划去$i$行，$j$列的子矩阵，
$$C_{ij} = (-1)^{i+j} det M_{ij} $$

计算行列式

行列式可以沿着任意一行或者任意一列，利用代数余子式进行计算，
沿着第$i$行计算的公式如下：
$$ det A = \sum_{j=1}^n a_{ij} C_{ij}$$
沿着第$j$列计算的公式如下：
$$ det A = \sum_{i=1}^m a_{ij} C_{ij}$$
可以递归下去进行计算。

参考文献

1.MIT线性代数公开课视频