从 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\) 增大。