从 0 开始到 PPO
一、问题定义与基本概念
马尔科夫决策过程 (MDP)：状态 $s$，行为 $a$，奖励函数 $r$，转移算子 $t=p(s’|s,a)$。
策略：给定当前状态 $s$ 和参数 $\theta$，策略是一种概率分布 $\pi_\theta(a|s)$。
目标：$\theta^\star=\arg\max_\theta E[\sum_t r(s_t,a_t)]=\arg\max J(\theta)$。
Q 函数：$Q(s_t,a_t)=\sum {t’=t}^{T}E{\pi_\theta}[r(s_{t’},a_{t’})|s_t,a_t]$, 即在状态 $s_t$ 采取动作 $a_t$ 的奖励期望
V 函数：$V(s_t)=\sum {t’=t}^TE{\pi_\theta}[r(s_{t’},a_{t’})|s_t]=E_{a_t\sim \pi_\theta(a_t|s_t)}[Q(s_t,a_t)]$，即在状态 $s_t$ 的奖励期望
A 函数：$A(s_t,a_t)=Q(s_t,a_t)-V(s_t)$，即某个动作比平均好多少
二、Value-based 方法与 Policy-based 方法
Value-based
在这种方法中，我们尝试估计 $Q(s_t,a_t)$，并采用某种固定的策略（例如，每次选择 $Q$ 估值最高的行动，或以 $\varepsilon$ 的概率选择 $Q$ 估值最高的行动，以 $1-\varepsilon$ 的概率随机行动 ）采样来更新我们的估计。
具体的，当我们获得一条新轨迹时，我们用 $Q_{n+1}=Q_n+\alpha[R_n-Q_n]$ 来更新 $Q$。这里的采样是 Off-Policy 的，即任意的策略均可更新 $Q$ 值表。
在推理时，只需采取 $Q$ 值最大的行动即可。这里的最优化问题有多种解法，如梯度下降、二次函数先验假设、网络学习等等。
Policy-based
在这种方法中，我们（暂时）不考虑 $Q$，转而优化 $\pi_\theta(a_t|s_t)$。对目标函数 $J(\theta)$ 求导得：
$$
\nabla_\theta J(\theta)=E[(\sum {t=1}^T\nabla\theta \log\pi_\theta(a_t|s_t))(\sum {t=1}^Tr(s_t,a_t))]
$$
直接更新 $\theta’=\theta+\alpha \nabla\theta J(\theta)$ 的算法称为 REINFORCE 算法，由于期望的获取依赖采样，因此该算法具有低偏差、高方差的特点。
改进一（Causality）：将来不能影响过去，因此在时刻 $t$ 只需考虑 $t$ 之后的奖励。即 $\nabla_\theta J(\theta)=\frac1N\sum {i=1}^N\sum {t=1}^T\nabla\theta\log\pi\theta(a_{i,t}|s_{i,t})(\sum {t’=t}^T r(s{i,t’},a_{i,t’}))$。
改进二（Baseline）：当 Reward 统一减去某个 $b$ 值时，策略偏差应该不变。
三、Actor-Critic 方法
在上面的基线改进中，如果令 $b=V(s_t)$，那么策略梯度为
$$
\nabla_\theta J(\theta)=\frac1N \sum {i=1}^n\sum{t=1}^T\nabla_\theta\log \pi_\theta(a_{i,t}|s_{i,t})(\sum {t’=t}^T A(s{i,t’},a_{i,t’}))
$$
如果我们能对 $V(s_t)$ 得到一个好的估计，那么问题可以得到解决。估计 $V(s_t)$ 或 $Q(s_t,a_t)$ 的模型称为评论家（Critic），而根据评论家的估计调整策略的模型称为演员（Actor）。可以看出，Actor-Critic 方法是把 Value-based 的方法和 Policy-based 的方法结合起来。
评论家模型可以通过蒙特卡洛的方法采样 $N$ 条轨迹，近似为
$$
V(s_t)=\frac{1}{N}\sum {i=1}^{N}\sum {t’=t}^{T}r(s{t’},a{t’})
$$
也可以使用神经网络学习的方法：利用预测的 $V(s_{t+1})$ 作为目标，优化 $||V(s_t)-(r(s_t,a_t)+V(s_{t+1}))||_2$。该方法称为自举（左脚踩右脚螺旋升天）。
以下是标准的 Actor-Critic 算法（带衰减因子）的流程：
- 从 $\pi_\theta(a|s)$ 中采样若干轨迹 $(s_i,a_i)$
- 用得到的奖励更新评论家网络 $V(s_t)$
- 估计优势函数 $A(s_i,a_i)=r(s_i,a_i)+\gamma V(s_i’)-V(s_i)$
- 计算策略梯度 $\nabla_\theta J(\theta)=\sum \nabla_\theta \log\pi_\theta(a_i|s_i)A(s_i,a_i)$
- 更新策略 $\theta =\theta+\alpha \nabla_\theta J(\theta)$
在网络设计中，可以让演员和评论家共享一部分网络层级，从而节省计算开销。
优势函数的改进：回顾标准的蒙特卡洛策略梯度算法，若将 $V(s_t)$ 作为基线，则优势函数应为 $\sum {t’=t}^T\gamma^{t’-t}r(s{i,t’},a_{i,t’})-V(s_t)$，具有无偏、高方差的特点；而在 Actor-Critic 算法中，采用 $r(s_i,a_i)+\gamma V(s_i’)-V(s_i)$ 作为优势函数（TD），具有有偏差、低方差的特点。若将二者融合，则可平衡偏差与方差：令 $\delta_t=r(s_t,a_t)+\gamma V(s_{t+1})-V(s_t)$，则 $A_{GAE}(s_t,a_t)=\sum {t’=t}^T(\gamma\lambda)^{t’-t}\delta{t’}$，其中 $\lambda=0$ 时该方法退化到 TD，$\lambda=1$ 时该方法退化到蒙特卡洛。
四、PPO 算法
标准的策略梯度算法是同策略（On-policy）的，也就意味着每次策略更新以后，之前采样的所有轨迹 $(s_t,a_t)$ 全部作废，必须重新采样。而与此同时，价值函数的估计是异策略（Off-policy）的，也就意味着不同策略的采样都可以用来更新评论家网络。显然异策略的模型数据使用更充分，如何改进 Actor-Critic 算法使其称为异策略的学习？
经过数学推导，异策略的策略梯度应写作：
$$
\nabla_{\theta’}J(\theta’)=E[\sum {t=1}^T\nabla{\theta’}\log\pi_{\theta’}(a_t|s_t)(\prod_{t’=1}^t\frac{\pi {\theta’}(a{t’}|s_{t’})}{\pi_\theta(a_{t’}|s_{t’})})(\sum {t’=t}^Tr(s{t’},a_{t’})(\prod_{t’‘=t}^{t’}\frac{\pi_{\theta’}(a_{t’‘}|s_{t’‘})}{\pi_\theta(a_{t’‘}|s_{t’'})}))]
$$
如果忽略掉末项，可以简写为 $J(\theta)=E_t[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}A_t]$。如果 $\frac{\pi_\theta}{\pi_{\theta_{old}}}$ 比值过大，则轨迹无效。
TRPO 算法：在 $E_t[KL[\pi_{\theta_{old}}(\cdot|s_t),\pi_\theta(\cdot|s_t)]]\le \delta$ 的硬约束下，求解 $J(\theta)$ 的最优化问题。
PPO 算法：通过截断函数与自适应 KL 惩罚项的软约束求解 $J(\theta)$ 的最优化问题。
截断函数
令 $r_t(\theta)=\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}$，则带截断的目标函数为
$$
L(\theta)=E_t[\min(r_t(\theta)A_t,clip(r_t(\theta),1-\varepsilon,1+\varepsilon)A_t)]
$$
其含义为：当两个策略的分布差距很大，也即 $r_t(\theta)>1+\varepsilon$ 或 $r_t(\theta)<1-\varepsilon$ 时，超出项会被抹平，从而在求策略梯度时梯度为零，不会对策略更新产生影响。
自适应 KL 惩罚项
$$
L(\theta)=E_t[r_t(\theta)A_t-\beta KL[\pi_{\theta_{old}}(\cdot|s_t),\pi_{\theta}(\cdot|s_t)]]
$$
其中，$\beta$ 随着相邻两次策略的 KL 散度值自适应变化。当相邻两次的 KL 散度值较小时，$\beta$ 相应减小；反之 $\beta$ 增大。