知乎链接：https://zhuanlan.zhihu.com/p/345687962
导语
仔细阅读本文章读者能简单理解如下几个问题：
- 估计值函数的主要方法有哪些？(文章中将简单介绍这些方法)
- 为什么说TD(Temporal Difference Method )算法的估计量高偏差低方差？
- 为什么说MC(Monte Carlo Method)算法的估计量无偏差高方差？
- \lambda-return如何做到在方差和方差间找平衡点的？
- TD(\lambda)为何比\lambda-return有计算方面的优势？
- TD、MC、\lambda-return以及之TD(\lambda)间的关系是什么？
- 策略梯度(Policy Gradient)方法为何经常用到优势函数（Advantage Function）？
- 最常用的优势函数的估计方法GAE(Generalized Advantage Estimation)与\lambda-return有什么关系？
大部分强化学习算法中需要用到值函数（状态值函数或者动作值函数），估计值函数的方法主要有时序差分(Temporal-difference, TD)算法和蒙特卡罗(Monte Carlo, MC)方法。这两类方法各有优缺点，TD算法的估计量具有高偏差(Bias)低方差(Variance)的特点，相反，MC算法的估计量具有低偏差高方差的特点。Hajime在2000年提出了一种巧妙地在偏差与方差间找平衡的方法，称为$\lambda$-return(按照Sutton的RL书的叫法)。TD(\lambda)是Sutton提出的能够使计算消耗更平均的$\lambda$-return的变种。
此外，一部分策略梯度(Policy Gradient)的方法经常会选择优势函数来构造策略梯度。泛化优势估计(Generalized Advantage Estimation, GAE)是John Schulman提出的估计优势函数的方法，它实际是将$\lambda$-return方法应用于估计优势函数的方法。
本篇文章将几个最基本的估计值函数的方法(包括TD、MC、$\lambda$ -return和TD($\lambda$))以及估计优势函数的方法（GAE）放在一起介绍，为的是梳理这些方法之间的关系（文末讨论），希望对读者有所帮助。除了常规地介绍这些方法的具体内容外，笔者总结本文与其它相关文章的增加的主要信息有：
- 简单分析了这些方法偏差与方差的高低特点，比如为何说TD算法高偏差低方差。
- 简单梳理了这些方法之间的关系
1. 时序差分算法
强化学习中估计值函数的方法主要有时序差分（Temporal-difference, TD）算法和蒙特卡罗（Monte Carlo, MC）方法。
1.值函数的估计方法
1.1 时序差分算法
(1) 贝尔曼等式
强化学习中Agent与环境的交互过程是由马尔可夫决策过程(Markov Decision Process, MDP)描述的。MDP对环境做了一个假设，称作马尔可夫性质，即下一时刻的状态只由上一时刻的状态和动作决定。该假设下，状态转移概率分布可以被简化：
Pr(S_{t+1},R_t|S_1,A_1,S_2,A_2,...,S_t,A_t)=p(S_{t+1,R_t}|S_{t},A_{t})
马尔可夫性质决定了值函数(状态值与动作值函数)可以写成递归的形式，即贝尔曼等式：
\begin{aligned}
V^{\pi}(s)&=\sum_{A_{t}} \pi(A_t|S_t=s)\sum_{S_{t+1},R_{t}}Pr(S_{t+1},R_{t}|S_{t}=s,A_{t})[R_{t}+\gamma V^{\pi}(S_{t+1})]\\
&=E_{\pi}[R_{t}+\gamma V^{\pi}(S_{t+1})|S_{t}=s]
\\
\\
Q^{\pi}(s,a)&=\sum_{S_{t+1},R_{t}}Pr(S_{t+1},R_{t}|S_{t}=s,A_{t}=a)[R_{t}+\gamma V^{\pi}(S_{t+1})]\\
&=E_{\pi}[R_{t}+\gamma V^{\pi}(S_{t+1})|S_{t}=s,A_{t}=a]
\end{aligned}
其中 $Pr(S',R|S,A)$ 为状态转移概率分布。
贝尔曼等式清晰地展示了值函数之间的迭代规律，或者说是相邻两个时刻的值函数间的关系: (以状态值函数为例)当前时刻的状态值等于下一时刻的回报值与下一时刻的状态值的和的期望。
(2) TD算法——将贝尔曼等式作为优化标准
假设当前需要估计某个策略$\pi$对应的值函数$V^{\pi}(s)$，我们可以用一个参数化函数$V\theta(s)$来近似真实的状态值函数$V^{\pi}(s)$。贝尔曼等式可以用于作为评判近似的值函数是否接近真实值函数的标准：如果近似的值函数也具有贝尔曼等式的迭代性质，就可以认为$V\theta(s)$是$V^{\pi}(s)$合适的近似函数。按照该思路，可以用如下的时序差分误差作为度量$V\theta(s)$性能的标准，即TD-error或者TD-residual：
\delta_{\theta}= R_{t} + \gamma V_\theta(S_{t+1}) - V_\theta(S_t)
一种常见的方式是最小化TD-error的平方值为目标指导参数$\theta$的优化，即求解如下最优化问题：
\min_{\theta} E_{(s,r,s')}[r + \gamma V_\theta(s') - V_\theta(s)]
此外，Q函数也可以用同样的方法进行估计。
(3) TD算法的特点——高偏差低方差
TD算法可以看成是利用策略$\pi$生成的样本$(s_0,r_0,s_1,r_1,...)$，并且使用$r_t + \gamma V\theta(s{t+1})$作为值函数$V^{\pi}(s{t})$的估计量。整个优化的过程，近似值函数$V\theta(s)$与真实的值函数之间一直存在误差，它们之间的关系可以表示为：
V_\theta(s)=V^{\pi}(s)+\epsilon_\theta(s)
其中，$\epsilon_\theta(s)$为近似误差。
接着按照检验估计量无偏性的思路，检查估计量的期望与估计量之间是否相等。估计量$r_t + \gamma V\theta(s{t+1})$的期望可以做如下转化：
\begin{align}
E_{(R_t,S_{t+1})}[R_t + \gamma V_\theta(S_{t+1})]&=E_{(R_t,S_{t+1})}[R_t + \gamma (V^{\pi}(S_{t+1})+\epsilon_\theta(S_{t+1}))]
\\
&=V^{\pi}(S_t)+\gamma E_{S_{t+1}}[\epsilon_\theta(S_{t+1}))]
\end{align}
可以看出估计量中存在$\gamma E{S{t+1}}[\epsilon\theta(S{t+1}))]$这个无法避免的偏差。
此外由于估计量中的随机变量维度较少，即只有当前时刻的回报值$R_t$，以及下一时刻的状态$S_{t+1}$，使值函数的估计量能够保持在较低水平。
1.2 蒙特卡罗算法
题外话：这里介绍的蒙特卡洛算法是指蒙特卡罗估计(用于估计/预测值函数)，区别于蒙特卡罗控制(用蒙特卡罗估计方法预测值函数并用值函数提升策略)。
(1) MC算法——基于值函数的定义
蒙特卡罗算法直接从值函数的定义出发，将回报值的累加作为值函数的估计量。假设$(s_t,r_t,s{t+1},r{t+1},...,s{t+N},r{t+N})$为策略$\pi$生成的样本，MC方法将$(r_t,r{t+1},...,r{t+N})$的折扣累加形式$\sum{n=0}N \gamma^{n} R{t+n}$作为状态$s_t$下的状态值的估计量。(Q函数也可以用同样的方法进行估计。)
(2) MC算法的特点——无偏差高方差
再一次按照检验估计量无偏性的思路，检查估计量的期望与估计量之间是否相等。MC方法对状态值的估计量的期望等于状态值函数的定义：
E_{(R_{t},R_{t+1},...,R_{t+N})}[\sum_{n=0}^N \gamma^{n} R_{t+n}|S_t=s]=V^{\pi}(s)
显然MC算法对状态值的估计量是无偏估计量。
此外由于估计量中的随机变量为$t$时刻之后所有的回报值$(R{t},R{t+1},...,R_{t+N})$，维度高，决定了该估计量具有高方差的特点。
1.3 $\lambda$-return算法
前面对TD算法和MC算法的介绍可以发现它们是两个极端：TD算法高偏差低方差，而MC算法无偏差高方差。$\lambda$-return方法是一种试图在偏差和方差之间找到平衡点的方法。
我们从TD算法出发，尝试找一种降低其估计量偏差的方法。前面的分析中可以知道TD算法为了减少方差(减少估计量中的随机变量数)，仅用到1步的回报值(当前时刻的回报值$R_t$)以及下一时刻的状态值$V\theta(S{t+1})$，而状态值$V\theta(S{t+1})$中的近似误差带来了偏差，偏差为$\gamma E{S{t+1}}[\epsilon\theta(S{t+1}))]$，受到折扣因子$\gamma$加权影响的。如果用到2步的回报值，即用t和t+1时刻的回报值$R_t$、$R{t+1}$以及t+2时刻的近似状态值$V\theta(S{t+2})$也可以作为状态值的估计量，即$R_t+\gamma R{t+1}+\gamma2 V{\theta}(S{t+2})$，该估计量的偏差为$\gamma2 E{S{t+2}}[\epsilon\theta(S{t+2}))]$，受到权重$\gamma2$影响。如果继续考虑n步的情况，可以看出估计量的偏差为$\gamman E{S{t+n}}[\epsilon\theta(S{t+n}))]$，由于$0\le\gamma\le 1$，$\gamman$随n的增大而降低，可以发现n越大偏差越小。
假设RL环境的设置是Episodic的情况（总有一个终止状态），t+N时刻为终止状态，按照上述的思路可以列出N种(n从1到N)关于$S_t$的状态值的估计量：
\begin{align}
G_t^{(1)}&=R_t+\gamma V_{\theta}(S_{t+1})\\
G_t^{(2)}&=R_t+\gamma R_{t+1}+\gamma^2 V_{\theta}(S_{t+2})\\
&...\\
G_t^{(n)}&=R_t+\gamma R_{t+1}+\gamma R_{t+2}+...+\gamma^n V_{\theta}(S_{t+n})\\
&...\\
G_t^{(N)}&=\sum_{n=0}^N \gamma^{n} R_{t+N}\\
\end{align}
n为1即为TD算法的估计量，n为N是MC算法的估计量。$\lambda$-return算法对这N个估计量进行加权平均，在TD于MC算法中找折中点，通过这种方式在偏差和方差间找平衡。加权平均的方式如下所示：
\begin{align}
G^{\lambda}_t&=(1-\lambda)[G_t^{(1)}+\lambda G_t^{(2)}+...+\lambda^{N-1} G_t^{(N)}]\\
&=(1-\lambda)\sum_{n=1}^{N}\lambda^{n-1}G_{t}^{(n)}
\end{align}
每一项前面的权重的和为1。其中$0\le\lambda\le1$，当$\lambda=0$即为TD算法，当$\lambda=1$即为MC算法。注意到n越大，对应的估计量的分量$G_t^{(n)}$的权重越小。
1.4 TD($\lambda$)算法
$\lambda$-return方法虽然有平衡偏差与方差的优点，但它必须用到当前时刻之后直到到达终止状态的所有数据(forward view)，也就是说只有在一条episode结束后才能计算出对应的状态估计量，使得计算消耗在时间上极不平均。
TD($\lambda$)是利用了当前时刻之前的样本(backward view)，不必等到episode结束才进行计算，时计算消耗在时间上更平均。它的思路类似于基于动量的梯度优化器，如(Adagrad、RMSProp、Adam等)，让梯度不仅受当前时刻的样本影响，还收到先前梯度方向的影响。具体做法是增加一个包含先前参数梯度信息的轨迹向量：
e_t=\nabla_\theta V_{\theta}(S_t) + \gamma \lambda e_{t-1}
其中，$\nabla\theta V{\theta}(S_t)$是根据当前时刻的样本计算出的梯度分量，$\gamma \lambda e_{t-1}$包含先前样本计算出的梯度分量信息。实际梯度的方向由$e_t$决定（步长和正负由TD-error决定），即：
\theta_{t+1}=\theta_{t}+\alpha \delta_t e_t
虽然上述操作使得TD($\lambda$)在计算上显得更优雅，但显然它的合理性弱于$\lambda$-return，实际效果也可能会弱于$\lambda$-return。实际上如果在TD算法中用到基于动量的梯度优化器，基本上等同于TD($\lambda$)的效果。
题外话：(off-line与on-line)如果估计值函数时，需要等到episode结束才能开始计算可以成这样的算法为off-line方法（如$\lambda$-return）；否则称为on-line方法（如TD($\lambda$)）。
2.优势函数的估计方法
2.1 优势函数
优势函数可以用比较直白的话来解释：它用于度量在某个状态$s$下选取某个具体动作$a$的合理性——它直接给出动作$a$的性能与所有可能的动作的性能的均值的差值。如果该差值(优势)大于0，说明动作$a$优于平均，是个合理的选择；如果差值(优势)小于0，说明动作$a$次于平均，不是好的选择。度量状态$s$下的动作$a$的性能最合适的形式就是动作值函数（即Q函数）$Q^{\pi}(s,a)$；而度量状态$s$下所有可能动作的性能的均值的最合适形式是状态值函数（即V函数）$V^{\pi}(s,a)$。这里给出优势函数的定义式：
A^{\pi}(s,a)=Q^{\pi}(s,a)-V^{\pi}(s)
（题外话：优势函数对于策略梯度的意义）
优势函数与策略梯度(Policy Gradient)类算法天然契合。策略梯度的常见形式如下：
g_{\theta}=E_{\tau}[\sum^{\infty}_{t=0}f(S_t,A_t)\nabla_{\theta}\log\pi_{\theta}(A_t|S_t)]
可以将梯度式子拆成两部分看：(1) $\nabla_{\theta}\log \pi_{\theta}(A_t|S_t)$是状态$S_t$情况下取到动作$A_t$的对数似然的梯度方向。如果参数$\theta$沿着该方向走，则提升了(鼓励)动作$A_t$的概率；如果参数$\theta$沿着该梯度的负方向走，则降低了(打压)动作$A_t$的概率。(2) $f(S_t,A_t)$这个标量决定了参数$\theta$应该沿着正方向走还是负方向走。
假设选用优势函数作为$f(S_t,A_t)$，即：
g_{\theta}=E_{\tau}[\sum^{\infty}_{t=0}A^{\pi}(S_t,A_t)\nabla_{\theta}\log\pi_{\theta}(A_t|S_t)]
接着分析两种情况：(1)$A^{\pi}(S_t,A_t)>0$:说明动作$A_t$优于平均值，值得鼓励，正好它的值为正数可以让参数$\theta$沿着正梯度方向走。(2)。$A^{\pi}(S_t,A_t)<0$:说明动作$A_t$次于平均值，应该避免，正好它的值为负数可以让参数$\theta$沿着负梯度方向走。因此说优势函数与策略梯度天然契合。
2.2 优势函数与TD-error
介绍到TD算法时提到TD-error的形式如下：
\begin{align}
\delta_t&=r_t+\gamma V^{\pi}(S_{t+1})-V^{\pi}(S_{t})\\
\end{align}
如果将优势函数稍微化简，可以发现它实际上是TD-error的期望：
\begin{align}
A^{\pi}(s,a)&=Q^{\pi}(s,a)-V^{\pi}(s)\\
&=E_{S_{t+1}}[r_t+\gamma V^{\pi}(S_{t+1})|S_t=s]-V^{\pi}(s)\\
&=E_{S_{t+1}}[r_t+\gamma V^{\pi}(S_{t+1})-V^{\pi}(S_t)|S_t=s]\\
&=E_{S_{t+1}}[\delta_t]
\end{align}
也就是说可以用TD-error作为优势函数的估计量。
为了求得TD-error，需要用到值函数$V^{\pi}$，实际算法中一般用到近似的值函数$V_{\theta}$，因此与TD算法一样，由于近似误差的存在，直接将$\delta_t$作为优势函数的估计量会有较大的偏差。
2.3 泛化优势估计(GAE)
泛化优化估计(GAE)实际上是$\lambda$-return应用在估计优势函数的版本。可以按照介绍$\lambda$-return方法中的使用n步回报值的思路列出N种优势函数的估计量。
\begin{align}
A_t^{(1)}&=-V_\theta(S_t)+R_t+\gamma V_\theta(S_{t+1})=\delta_t\\
A_t^{(2)}&=-V_\theta(S_t)+R_t+\gamma R_{t+1}+\gamma^2 V_\theta(S_{t+2})=\delta_t+\gamma \delta_{t+1}\\
&...\\
A_t^{(n)}&=-V_\theta(S_t)+R_t+\gamma R_{t+1}+...+\gamma^n V_\theta(S_{t+n})=\delta_t+\gamma \delta_{t+1}+...+\gamma^n\delta_{t+n}\\
&...\\
A_t^{(N)}&=-V_\theta(S_t)+R_t+\gamma R_{t+1}+...+\gamma^N R_{t+N}=\sum_{n=0}^{N}\gamma^n\delta_{t+n}
\end{align}
其中Sutton的书中将最后一项$A_t^{(N)}$称为蒙特卡罗误差(Monte Carlo error)。这些估计量的偏差同样随着n的增加而减小，方差随着n的增大而增大。GAE采用了同$\lambda$-return一样的加权平均方法来权衡优势函数估计量的偏差与方差：
\begin{align}
A_t^\gamma&=(1-\lambda)(A_t^{(1)}+\lambda A_t^{(2)}+...+\lambda^{K} A_t^{(N)})\\
&=(1-\lambda)[\delta_t+\lambda(\delta_t+\gamma \delta_{t+1})+...+\lambda^{K}\sum_{n=0}^{N}\gamma^n\delta_{t+n}]\\
&=(1-\lambda)[\delta_t(1+\lambda+...+\lambda^{K})+\gamma \delta_{t+1}(\lambda+\lambda^2+...+\lambda^K)+...+\gamma^N\delta_{t+N}\lambda^{K}]\\
\end{align}
当$N\rightarrow \infty$时，该估计量可以化简成简单的形式：
\begin{align}
A_t^\gamma&=(1-\lambda)[A_t^{(1)}+\lambda A_t^{(2)}+\lambda^2 A_t^{(3)}...]\\
=&(1-\lambda)[\delta_t+\lambda(\delta_t+\gamma \delta_{t+1})+\lambda^2(\delta_t+\gamma \delta_{t+2})+...]\\
=&(1-\lambda)[\delta_t(1+\lambda+\lambda^{2}+...)+\gamma \delta_{t+1}(\lambda+\lambda^2+\lambda^3+...)\\
&+\gamma \delta_{t+2}(\lambda^2+\lambda^3+\lambda^4+...)+...]\\
=&(1-\lambda)[\delta_t(\frac{1}{1-\lambda})+\gamma\lambda\delta_{t+1}(\frac{1}{1-\lambda})+(\gamma\lambda)^2\delta_{t+2}(\frac{1}{1-\lambda})+...]\\
=&\sum_{n=0}^{\infty}(\gamma\lambda)^n\delta_{t+n}
\end{align}
实际情况下N很难达到无穷大，因此这个形式的优势函数估计量还是有近似误差的。
3.画重点
估计值函数的方法中，TD算法方差小但偏差大；MC算法无偏但方差大；$\lambda$-return是一种折中又相对简单的方法，但需要采样完一整条episode才能计算(off-line)。TD($\lambda$)是对$\lambda$-return算法的改进，用类似动量优化方法(Adagrad、RMSProp、Adam等)使算法无需在采样到episode的结尾才进行计算，让计算消耗平摊在每个时间点上。GAE实际上是$\lambda$-return用于估计优势函数的版本。
主要参考来源
- Sutton R , Barto A . Reinforcement Learning:An Introduction[M]. MIT Press, 1998.
- Schulman, John & Moritz, Philipp & Levine, Sergey & Jordan, Michael & Abbeel, Pieter. (2015). High-Dimensional Continuous Control Using Generalized Advantage Estimation.
- Kimura, H. and S. Kobayashi. “An Analysis of Actor/Critic Algorithms Using Eligibility Traces: Reinforcement Learning with Imperfect Value Function.” ICML (1998).
