强化学习定义以下几个变量：
a：操作action，可以是N种操作构成一个有限集合$\{a_1, a_2, …, a_N\}$，每种操作的概率分布是$\pi$；当然如果a是连续操作，那么$\pi$就变成了概率密度分布。
s：状态state，描述了能够用于决策的有关环境的所有信息的表征。
r：回报reward，是当某个状态s下执行了操作a后，对agent的奖励的预期值。
主要优化目标是整个交互过程内的reward收益累积：
$$\mathbb{E}_{p(s_0), \pi(a_0 \mid s_0)}[r(s_1)\mid s_0] + \gamma \mathbb{E}_{p(s_1\mid s_0, a_0), \pi(a_1\mid s_1)}[r(s_2)\mid s_1] + ……$$
每一个step时，收益$r_t$的预期值累加，以$\gamma$的衰弱递减。这里求预期，就涉及到两个不确定分布，首先是状态转移概率$p(s_{t+1} \mid s_t, a_t)$，马尔可夫过程中的状态转移，以及$\pi(a_t\mid s_t)$，策略决策过程本身。要在每个事件“分歧点”对这两个概率分布求预期。
因为“分叉点”的存在，更适合把优化目标写成迭代的形式，这样每个时间点Q的计算，都需要未来各个：
\begin{equation}
Q(s_t, a_t) = \sum\limits_{s_{t+1}} p(s_{t+1}\mid s_t, a_t) r(s_{t+1} \mid s_t, a_t) + \gamma \sum\limits_{s_{t+1}, a_{t+1}} p(s_{t+1}\mid s_t, a_t) \pi(a_{t+1} \mid s_{t+1}) Q(s_{t+1}, a_{t+1})
\label{eq2}
\end{equation}
Q由两部分组成：
- 第一部分是如果当前t时采用策略$a_t$，到下次观测的状态$s_{t+1}$无论是哪个时，即将收获的单步收益的预期，写作$R_s^a$。
- 第二部分是当1的预期收益入账之后，对未来尚未发生的一系列事件，在当前策略$\pi(a \mid s)$的影响下，即将累积到的直到游戏结束的所有收益的预期。
agent需要通过$\pi$来选择操作$a(s)$，或是直接调整连续的$a(s)$的值，使得无论任何路径上，只要初始状态和策略固定了，就让累积收益的预期都能最大化。
\begin{equation}
J=\mathbb{E}_{p(s) \sim \tau}[\sum\limits_{t=0}^{\infty} \gamma^{t} \left( \sum\limits_{a \in A} \pi(a \mid s_t) R_s^a \right) \mid s_0, \pi]
\label{eq1}
\end{equation}最大化。
有两种思路来解决这个问题：
- 值迭代。平均$P_{s\rightarrow s’}^a$的预期后，$Q(s_t, a_t) \approx r(s_{t+1}) + \mathbb{E}_{\pi(s_{t+1})}[Q(s_{t+1}, a_{t+1})] = r(s_{t+1}) + V(s_{t+1})$。当从真实分布中通过采样来近似出$p(s_{t+1} \mid s_t, a_t)$、$r(s_{t+1})$、$\pi(a \mid s_t)$以及$p(s_0)$时，约等号就变成了等号。所以我们要确保无论任何时候间隔了一步（当然也可以是多步）的Q的差值，符合真实分布中这一（几）步内累积的收益，Q的预测就是准确的。有了准确的Q值预测网络之后，只需要在每一次面临决策时，选取能让Q值收益最大的一个操作，即可得到最优策略。
- 策略迭代。直接使用$\frac {\partial J} {\partial \pi} =0$优化策略$\pi$。这时面临的最主要问题是如何获得相对精确的J，这时采样过程非常重要。退一步讲如果没有很好的办法直接获取J，是否存在一些替代方法能够得到等同于优化$\frac {\partial J} {\partial \pi} =0$的效果。
值迭代的经典算法DQN，就是用replay buffer以及环境采样trajectory里统计出的$target=\sum\limits_{t=0}^{n} \gamma^t r_t$，与Q值网络$pred = Q(s_0, a_0) – Q(s_n, a_n)$的最小二乘$(pred-target)^2$作为loss来优化Q值网络的评估准确率。
如果从环境采样，那么训练时采样策略一般是epsilon-greedy，其中greedy是在$a^*=argmax_{a} Q_{tgt}(s)$上获得的。
Double DQN与的区别DQN在于$a^*=argmax_{a} Q_{eval}(s)$，之后预估用于最小二乘的目标值$Q(s, a) = r + \gamma Q_{tgt}(s, a^*) $时使用另一个Q网络。$Q_{tgt}$是一个比较落后的版本的$Q_{eval}$。本质上是把actor和critic网络分开，再定时同步。这样做的优点可以避免DQN里过估计(overestimate)的问题。因为$\mathbb{E}[max_a Q] > max_a \mathbb{E}[Q]$是常态，每一步都取max后得到的Q，一般都会大于真实Q。
值迭代目的是为了得到优质的评价器criticizer，策略迭代目的是为了更好的actor。两者结合构成了AC框架。 Asynchronous Advantage Actor Critic（A3C）在AC框架的基础上对策略迭代的目标做了些许修改，又对采样部分采用了一些并行策略，于是可以取得更好的效果。
进入A3C具体细节之前，首先讲一下策略梯度方法，策略梯度主要通过策略迭代的方法进行优化。
$\pi=\pi_{\theta}(s)$，假设使用可训练参数$\theta$时策略对其可求导，则根据梯度提升，有$\frac {\partial J} {\partial \theta}=0$
\eqref{eq1}里的$R_s^a$只与环境有关而与$\theta$无关，所以梯度更新时$\nabla_{\theta} J = \mathbb{E}_{p(s) \sim \tau}[\sum\limits_{t=0}^{\infty} \gamma^{t} \left( \sum\limits_{a \in A} \pi(a \mid s_t) \frac{\nabla_{\theta} \pi(a \mid s_t)} { \pi(a \mid s_t)} R_s^a \right) \mid s_0, \pi]$
\begin{equation}
\nabla_{\theta} J = \mathbb{E}_{p(s) \sim \tau, \pi(a) \sim \tau}[ \sum\limits_{t=0}^{\infty} \gamma^{t} \nabla_{\theta}\left(log\pi(a \mid s_t)\right) R_s^a]
\label{eq3}
\end{equation}
where $\tau=(s_0, a_0) \rightarrow (s_1, a_1) \rightarrow ……$
这样的优化梯度需要完整采样出一个足够长的路径$\tau$，每次都从$s_0$按照策略$\pi$开始推演，工程中虽然能够实现，但当环境无法满足on-policy实时推演时，也会使得优化难以进行。
需要转换一下思路：
假设当某步t时观测到$s_t$，过去的所有路径信息已经丢失，可以看作是$i=1, 2…,\infty$条轨迹$\tau_i$分别在不同的演化位置上达成了当前观测到的状态$s\in \tau_i = s_t$。那么可以定义一个静态先验概率$p(s_t)=d(s_t) = \sum\limits_{t^*=0}^{\infty} \gamma^{t^*} P(s_{t^*}=s_t \mid s_{0^*}=\tau_i(0), \pi)$。相当于对无论之前发生了任何事情，算出一个考虑了衰减的用于计算无数个$\tau$之间预期的概率。
$V(s_t) = \mathbb{E}_{\tau} [ \sum\limits_{t^*=t}^{\infty} \gamma^{t^*} \sum\limits_{a \in A} \pi(a \mid s_{t^*})R_s^a]$
之后将t的时间刻度假设看作新起点，例如$t=0$，那么$J =\sum\limits_{s_t \in S} d(s_t) V(s_t)$
于是优化目标将“从$s_0$出发使用$\pi$的无数路径上的收益累积预期（平均$\tau$求预期）”变成了“从$s_0$出发使用$\pi$的，暂时以$s_t$收尾的无论任何长度路径上，所有剩余未累积到的收益预期（使用$d(s_t)$求预期）”。这样一来就不用非要等推演完毕之后再平均求预期，只需要在推演过程中的每一步t不断用网络评估$Q(s_t, a_t)$再结合$\pi(a_t \mid s_t)$算出$V(s_t)$即可。取而代之的难点就变成了如何求$d(s_t)$的问题。
考虑$V(s) = \sum\limits_{a \in A} \pi(a \mid s) Q(s, a)$
定义单步转移概率$ p(s_{t+1}\mid s_t, a_t) = P_{s\rightarrow s’}^a$，对上式求$\nabla_{\theta}$，则有
$$ = \sum\limits_a \left[ Q(s, a) \frac {\partial \pi(a \mid s) } {\partial \theta} + \pi(a\mid s) \frac {\partial } {\partial \theta} \left[ R_s^a + \gamma \sum\limits_{s’} \sum\limits_{a’} P_{s\rightarrow s’}^a \pi(a’ \mid s’) Q(s’, a’) \right] \right]$$
对$R_s^a$求导得到0，因为critic函数不会改变预先定义好的reward规则。
可以看到递归出现，那么如果多展开几次，每次都会带出一个$\gamma$还有$P_{s\rightarrow s’}^a$，所以这两项会累乘起来。
注意到$P_{s\rightarrow s’}^a= Pr(s\rightarrow s’ \mid a)$，利用$ Pr(s\rightarrow s’) = \sum\limits_{a} Pr(s\rightarrow s’ \mid a) \pi(a \mid s)$。可得trajectory上对action空间取预期后的$Pr(s\rightarrow s’)$
所以要让$s \rightarrow s’ \rightarrow s” \rightarrow… \rightarrow x$被连续采出来，就要让右边改成：
$$\sum\limits_a Q(s, a) \frac {\partial \pi(a \mid s) } {\partial \theta} + \sum\limits_a \gamma Pr(s\rightarrow s’ \mid a) \pi(a \mid s) \frac {\partial } {\partial \theta} \left[ \sum\limits_{s’} \sum\limits_{a’} \pi(a’ \mid s’) Q(s’, a’) \right]$$
$$=\sum\limits_a Q(s, a) \frac {\partial \pi(a \mid s) } {\partial \theta} + \gamma Pr(s\rightarrow s’) \frac {\partial } {\partial \theta} \left[ \sum\limits_{s’} \sum\limits_{a’} \pi(a’ \mid s’) Q(s’, a’) \right]$$
现在转换一下思路，不考虑初始$s$的值是什么，只要在对应第k步的$s_t = x \mid t=k$的state是$x$即可，那么展开后的式子变成了：
$$\frac {\partial V(s)} {\partial \theta} = \sum\limits_x \sum\limits_{k=0}^{\infty} \gamma^k Pr(s \rightarrow x, k \mid \pi) \sum\limits_a Q(x, a) \frac {\partial \pi(a \mid x)}{\partial \theta}$$
其中$Pr(s \rightarrow x, k)$是经历了k轮之后从初始s演变成最终x状态的概率。
把初始状态重写为$s_0$，最终状态重写为$s$，则
$$\frac {\partial V(s_0)} {\partial \theta} = \sum\limits_s \sum\limits_{k=0}^{\infty} \gamma^k Pr(s_0 \rightarrow s, k) \sum\limits_a Q(s, a) \frac {\partial \pi(a \mid s)}{\partial \theta}$$
注意到$\sum\limits_{k=0}^{\infty} \gamma^k Pr(s_0 \rightarrow s, k)$等于$d(s)$，即所有可能的长度的演化路线根据衰减系数$\gamma$后得到的状态为s的概率，所以$\nabla_{\theta} V(s_0) = \sum\limits_{s} d(s) \sum\limits_{a} Q(s, a) \nabla_{\theta} \pi(a \mid s)$。
由于稳态分布$d(s)$不方便求，一般使用MC采样来近似，于是需要在不同的t时刻进行采样。不同t时刻之间的采样又不可避免地进行a的采样，于是$\mathbb{E}_{\tau} = \mathbb{E}_{p(s, a, k) \sim \tau}=\sum\limits_{s, a, k} p(s, a, k)=\sum\limits_{s, a, k} P(s_0 \rightarrow s, k)\pi(a\mid s)$。
$\nabla_{\theta} J = \sum\limits_{s, k}\sum\limits_a P(s_0 \rightarrow s, k) \pi(a \mid s) Q(s, a) \frac {\nabla_{\theta} \pi(a \mid s)} {\pi(a \mid s)} $
$=\mathbb{E}_{p(s, a, k) \sim \tau}[ Q(s, a) \nabla_{\theta}\left(log\pi(a \mid s)\right)]$
这样我们就不需要完整采样整个路径之后按照\eqref{eq3}累加每一步的$R_s^a$，只需要在任意路径的任意一截采出$p(s, a, k)$以及对应的$Q(s, a)$和$\nabla_{\theta}\left(log\pi(a \mid s)\right)$就可以了。
注意到每一步$a_t$之间存在非连续的采样操作，所以例如seq2seq的解码过程里对target loss求导这一类对于非连续不可导的反向传播，也是可以使用策略梯度来更新解码器参数的。
A3C:
Proximal Policy Optimization(PPO):
更新actor时，策略梯度的方向$g = \mathbb{E}_{p(s, a, k) \sim \tau}[ Q(s, a) \nabla_{\theta}\left(log\pi(a \mid s)\right)]$
在沿$\tau$采样action时，一般常见的方式是$a \sim \pi_{\theta}$，这是on-policy的训练方法。如果改变当前的策略，例如加上一些随机性（像epsilon greedy那样），那么就可以变成off-policy的方式了。为了保证模型策略的稳定性，我们的off-policy策略可以使用比较旧版本的$\pi$，写作$\pi_{\theta \text{old}}$。
但是采样策略变了，虽然不影响值迭代，却影响policy gradient，要如何保证梯度方向不变呢？这里就需要使用importance sampling的方法了。
对一个连续函数$f(x)$求预期，可以写作
$$\mathbb{E}_{x \sim p(x)}[f(x)]=\int\limits f(x) p(x) dx = \int\limits f(x) \frac{p(x)} {q(x)} q(x) dx = \mathbb{E}_{x \sim q(x)}[f(x) \frac{p(x)} {q(x)}]$$
其中$\frac{p(x)} {q(x)}$是importance weight，负责在计算预期的采样分布从$p$变成$q$时，把$f$预期还原成原本的值的一个修正。
所以要让gradient即使采样策略变了的情况下，方向（预期值）不变，就要加上importance weight:
$$g = \mathbb{E}_{p(s, a, k) \sim \tau(\theta \text{old})}[ Q(s, a) \frac {\pi_{\theta}(a \mid s)} { \pi_{\theta \text{old}}(a \mid s)} \nabla_{\theta}\left(log\pi_{\theta \text{old}}(a \mid s)\right)]$$
如果使用优势函数$A$代替$Q$，则使用到的$V(s)=\sum\limits_{a} \pi_{\theta \text{old}}(a \mid s) Q(s, a)$也应该基于旧分布。
TRPO对$D_{KL}(\pi_{\theta} || \pi_{\theta \text{old}})$做了硬约束，要搜索出合适的Lagrange multiplier, 不方便求解。所以PPO改成了惩罚项软约束。此外软约束下的优化替代函数$L_{\pi_{old}}(\pi)=\mathbb{E}_{\tau_{old}} \left[ \frac{\pi(a \mid s, \theta)} {\pi(a \mid s, \theta_{old})} A^{GAE}(s, a) – \lambda D_{KL}(\pi || \pi_{old}) \right]$ 也是直接用adam求导，而非套用Policy Gradient公式的。在升级版本PPO2论文里，在计算importance weight （理论值从$0$到$\infty$）时引入了clip函数，当$A>0$时限制它的上限，当$A<0$时限制它的下限。这样优势函数$A$不会被importance weight修改得即使在新旧策略差异较大（importance weight超出某个门槛。毕竟软KL约束无法杜绝这种情况）时，对于更新方向的影响也特别大。KL距离的约束被clip操作取代，而clip阈值的大小控制了“约束后的新策略”位于“旧策略”与“无约束新策略”之间的某个中间位置是更接近于哪一方。
注意优势函数$A$实际上拥有下标$A_t$，下标t用于求trajectory[0, T]上的时间平均预期用。
$A_t=A(s_t, a_t)=\delta_t + \gamma \delta_{t+1} + \gamma^2\delta_{t+2}+…+\gamma^{T-t+1}\delta_{T-1}$
where $\delta_t = r_t + \gamma V(s_{t+1}) – V(s_t)$
使用GAE的逻辑是这样的：
一个准确评估的$V(s_t)$，在actor达成最优策略时，$\delta_t=0$。而在那之前，单步优势就是$\delta_t = r_t \mid _{a_t} + \gamma V(s_{t+1}) – V(s_t)$
我们希望以任意t作为起点时，对于后续累加的优势$\hat{A}(t) = \sum\limits_{l=0}^{\infty} \delta_{t+l}$ 最大化。但与累加reward时需要$\gamma$来调节衰减一样，累加$\delta$时也添加了一个衰减$\gamma\lambda$，其中$\lambda$的作用就是对$\gamma$做出改变从而获得一个不一样的衰减。
最终得到 $\hat{A}^{GAE}(t)= \sum\limits_{l=0}^{\infty} (\gamma\lambda)^{l} \delta_{t+l}$
当$\lambda=1$时，GAE变成远距离TD，这时reward累加得到的$V_{start}$很准确，但评估$V_{end}$时输入$s$已经经过太多轮不确定的状态转移，导致$V_{end}$的variance很大。而当$\lambda=0$时，GAE变成1步TD，1步采样得到的reward大概率是偏离预期值$\mathbb{E}_{\pi}[r \mid s]$的，所以必然导致V的学习目标带有bias，而状态转移相对确定一些，所以variance会小一些。$\lambda$于是起到了n步TD中调节bias与variance平衡的作用。
