1. Introduction
在前面的课程中我们学习了什么是马尔科夫决策过程，同时学习了如何使用Bellman Expectation Equation去evaluate一个Policy，这属于Prediction的内容。此外，我们还学习使用Policy Iteration和Value Iteration去优化Policy，实现Control。以上两种Iteration的过程都属于Dynamic Programming的思想，这两个方法都要求我们的MDP是完全已知的——也就是environment’s dynamics是已知的，可以获得执行某个操作后，状态之间的转移概率，以及对应的reward. 然而，在现实情况中，这些信息往往是不可知的，比如你无法得到机器人执行一个动作后，环境状态变化的所有可能状态以及对应的概率。
这种时候我们就需要Model-free的方法，其核心要解决的问题是如何去估计并优化未知MDP的value function，这一篇我们先学习如何去估计value function，即Model-free prediction，然后下一篇学习如何去优化，即Model-free control。
2. Monte-Carlo Learning
蒙特卡洛方法（MC）是一个最简单的Model-free prediction方法，它直接从episodes of experience中学习。所谓 experience就是一段采样得到的序列，包含states，actions以及rewards，同时MC要求这一段采样片段式完整的，即最后处于终止状态。其学习的思想非常简单：通过对return进行取平均值得到value的估计。
下面给出具体的说明：
-
目标：从一些来自 Policy $\pi$ 的episodes of experience 学习 $v_{\pi}$ ，即$S_1,A_1,R_2,…,S_k\sim \pi$
-
回顾一些定义：
- Return是 total discounted reward: $G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T}$
- value function是return的期望：$v_{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right]$
-
Monte-Carlo policy evaluation uses empirical mean return instead of expected return，换句话说，由于我们无法获得概率，所以我们无法获得return的期望，于是我们就转而通过统计所有经过某个状态的return，然后求平均作为改状态的value，只要经过该state的episodes足够多，平均的value就可以代表改状态的return期望。
然而，在一个episode中，可能会多次访问到同一个state，如何处理这种情况的return统计决定了两种不同策略的Monte-Carlo Policy Evaluation方法，下面分别介绍。
2.1 First / Every-Visit MC Policy Evaluation
如上述伪代码所示，First-Visit Monte-Carlo Policy Evaluation只统计整个Episode中，从第一次出现某个State开始，到结束状态的Return，然后将所有Episode遍历，计算平均值，作为某个State的估计value。
Every-Visit Monte-Carlo Policy Evaluation 和 First-Visit差不多，唯一的区别是，它统计一个Episode中，某个State出现过的所有Return，然后计算所有Episode统计的平均值。
根据大数定理，当State出现的次数越接近无穷时，估计的Value就越接近真实的Value期望。
2.2 Incremental MC
下面的式子表示，一组数的平均值可以通过增量的方式计算：
\begin{aligned}
\mu_{k} & =\frac{1}{k} \sum_{j=1}^{k} x_{j} \\
& =\frac{1}{k}\left(x_{k}+\sum_{j=1}^{k-1} x_{j}\right) \\
& =\frac{1}{k}\left(x_{k}+(k-1) \mu_{k-1}\right) \\
& =\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right)
\end{aligned}
$$
基于这一定理，我们在使用Monte-Carlo时，就不需要统计所有的episode后再计算平均值，而是在一次episode后增量更新Value：
\begin{array}{l}
N\left(S_{t}\right) \leftarrow N\left(S_{t}\right)+1 \\
V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\frac{1}{N\left(S_{t}\right)}\left(G_{t}-V\left(S_{t}\right)\right)
\end{array}
$$
此外，除了严格的计算平均数，还可以使用一个人为设定的系数去更新value，其实就类似于深度学习的学习率：
V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)
$$
3. Temporal-Difference Learning
3.1 TD Learning
Temporal-Difference Learning 时间差分学习方法使用的场景和MC是一样的，两者不同点在于，时间差分方法不需要完整的episode，通过bootstrapping的方式进行学习，通过估计剩余的episode的return来更新value，因此TD也可以看做是从一种guess来更新guess的策略。
下面对MC和TD进行比较：
-
两者的目标都是：从基于 Policy $\pi$ 的experience 学习 $v_{\pi}$
-
Incremental every-visit Monte-Carlo：$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)$
-
Simplest temporal-difference learning algorithm TD(0)：
- 定义 $R_{t+1}+\gamma V\left(S_{t+1}\right)$ 表示 TD Target
- 定义 $R_{t+1}+\gamma V\left(S_{t+1}\right) – V(S_t)$ 为 TD error
- 我们通过这种方式更新Value：$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right) – V(S_t))\right)$
- 和MC相比，TD使用了自己估计的return来代替真实的return $G$
3.2 TD vs MC
以估计开车到家的时间估计问题为例：
Elapsed Time为实际已经驾驶的时间，Predicted Time to Go表示预计还需要多少时间，Predicted Total Time表示预计一共需要多少时间。基于MC的方法只能在开车这一件事完成后，将每个state的value朝着actual outcome 方向进行更新，而TD方法是根据实际驾驶的时间，更新之前状态的预估时间，也就是可以实时更新。
所以，TD可以在线的从每个step中进行学习，而MC需要等到整个episode都结束了才能完成一次学习。同时TD学习不要求必须要有最终的结果，所以可以部署在一个持续变化没有终结的环境中，而MC必须处于一个具有最终状态的环境中才能使用。
此外，从Bias/Variance Trade-Off的角度我们可以进一步比较TD和MC：
由于Return $G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1}R_T$ 是一个真实值，所以我们称为 $V_\pi(S_t)$ 的无偏估计。而TD Target仅根据当前的情况进行预测，所以是一个有偏估计。但是TD Target的方差却比Return低，这是由于Return是由多次随机的action，transition，rewards确定的，其中包含了多次随机变量的叠加，变动更大。而TD Target只取决于当前的一个 action，transition，reward。因此：
- MC具有高方差，0偏差，具有很好的收敛性，对初始值不敏感，易于使用和理解
- TD具有低方差，一些偏差，相比MC更高效，对初始值更敏感一些。
3.3 Batch MC and TD
如果我们的episodes是趋近无穷的，那么MC和TD都会收敛到真实的Value Function，但是如果我们的episode是有限的呢？（实际上都是有限的），即只有一个batch的episode，然后反复在这一个batch中运行MC和TD，会有什么区别？
我们以AB转移问题为例，假设我们有如下的一个episode batch，每个数字表示动作的reward，如A,0,B,0表示A移动到B的reward为0，然后B移动到终止状态reward为0. 根据这一个batch，其实我们可以构建一个MDP模型，如下图右所示。我们可以得到B的value为0.75，A的状态为 0+0.75-0.75（A以100%概率转移到B，且reward为0，后继状态B的value为0.75，因此A的value为0.75），实际上这也是TD的预测结果。但是，如果我们使用MC进行预测，那么A的value为0，因为A这一状态只出现在了A,0,B,0这一个episode中，且从A开始到终止的return为0，根据MC的公式，计算得到return的平均值为0，value为0。
所以，MC实际上是在拟合观察到的return的最小MSE：
\sum_{k=1}^{K} \sum_{t=1}^{T_{k}}\left(G_{t}^{k}-V\left(s_{t}^{k}\right)\right)^{2}
$$
而TD(0)则是在收敛至 Markov model 解的最大 likelihood，其中MDP的解用下式进行估计：
\begin{aligned}
\hat{\mathcal{P}}_{s, s^{\prime}}^{a} & =\frac{1}{N(s, a)} \sum_{k=1}^{K} \sum_{t=1}^{T_{k}} \mathbf{1}\left(s_{t}^{k}, a_{t}^{k}, s_{t+1}^{k}=s, a, s^{\prime}\right) \\
\hat{\mathcal{R}}_{s}^{a} & =\frac{1}{N(s, a)} \sum_{k=1}^{K} \sum_{t=1}^{T_{k}} \mathbf{1}\left(s_{t}^{k}, a_{t}^{k}=s, a\right) r_{t}^{k}
\end{aligned}
$$
3.4 TD vs MC vs DP
下面将TD，MC，DP三者进行统一的比较：
MC 是获取一条完整的sample序列，然后统计整个序列的Return来更新状态value
TD 是执行一个action，就更新一次state，使用的是执行动作的即时reward和后继节点的value作为Return的估计
DP 在一个完整的MDP中运行，所以在计算Value时可以直接获取每个可转移状态的概率，计算value期望。
换句话说，我们可以从两个维度区分这些方法：
4. TD($\lambda$)
4.1 n-Step TD
我们知道Monte-Carlo方法依赖于整个序列的全部动作reward来估计state value，而上面介绍的TD则使用一次动作执行的reward，以及通过bootstrapping得到的后续状态的value作为return的估计。一般来说，采取中庸之道能同时规避两个极端的劣势，那么，是否有方法介于两者之间？即考虑若干个连续action的影响？这就是n-step TD算法，就是使用n次执行action的reward之和（考虑上discount）加上执行n次action后转移到的后继状态value，作为估计的return来更新state value。
下面的图展示了一个使用n-step TD进行训练的图，横坐标表示不同 $\alpha$ ，纵坐标表示误差，可以发现，n过大和过小都会导致误差很大，在n=4左右，误差可能达到最小。这也就证明了，确实中庸比极端方法好（这种思想在很多算法中都有设计，还是孔先生远见啊！）
4.2 Forward View of TD($\lambda$)
n-Step TD相比极端的MC方法和1-step TD具有更好的性能，那么进一步的，我们是不是可以把多个不同取值的n-step TD综合起来？对，这就是 TD($\lambda$) 的主要思想，并且 TD($\lambda$) 做的更彻底——把所有可能的n都考虑进去，然后将所有的return进行混合作为估计的return。
我们定义：$\lambda$-return 记作 $G_t^{\lambda}$ ，式子如下图所示，可以看到其做法就是在每个n对应的return乘上一个几何级数的项，由于几何级数的和为 $\frac{1}{1-\lambda}$ ，所以在每项前乘以 $1-\lambda$ 使得其权重之和为1，这就确保了整体是一种加权平均，反映原始数据的中心趋势或期望值，没有改变原始数据的规模或相对重要性。
下图进一步展示了几何级数的变化趋势，整个面积为1，可以看到一开始的权重更大，后面权重变小。
需要注意的是，当 $n>T$ 时，即考虑超过终止状态的step时，我们返回的就是实际的最终return，因此 $\lambda$-return还可以写成下面的版本：
G_t^\lambda = (1 – \lambda) \sum_{n=1}^{T-t-1} \lambda^{n-1} G_{t:t+n} + \lambda^{T-t-1} G_t,
$$
从这个式子我们就可以很清晰的看出：
- 当 $\lambda=0$ , $\lambda$-return 就是$G_{t:t+1}$，就变成了1-step TD
- 当 $\lambda=1$，$\lambda$-return 就是真实return，算法变成了MC
对于每个我们访问到的状态，我们需要看向所有的未来状态以获取未来的reward，然后考虑如何最好的将这些reward进行组合，作为当前状态value的估计，一旦我们完成了当前状态的估计，就会移动到下一个状态重复操作，并永远不会返回到之前的状态，如下图所示，这种形式称为forward-view。forward-view解释了算法的思想，易于理解，但是在实际使用中，考虑到效率问题，我们并不会这样去计算，而是采用backward-view.
4.3 Backward View of TD($\lambda$)
考虑下图的 Credit assignment problem，究竟是铃声还是发光导致最后的震动？
- 从Frequency heuristic的角度考虑：由于钟声出现的频率最高，所以是钟声导致了震动
- 从Recency heuristic的角度考虑：发生震动前出现发过现象，所以是发光导致了震动
上述两种启发式方法显然考虑的都不够周全，Eligibility traces 是这两种的一个结合，函数如下图所示，在Episode的初始阶段值为0，随着state出现的次数增加，同时随着时间的增加衰减，因此这一函数同时考虑了频率和时间：
在TD($\lambda$) 中我们使用Eligibility traces对 TD error $\delta_{t}$ 进行加权，用于更新value：
\begin{aligned}
\delta_{t} & =R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right) \\
V(s) & \leftarrow V(s)+\alpha \delta_{t} E_{t}(s)
\end{aligned}
$$
具体的TD($\lambda$) 算法流程如下，其中 $\mathrm{z}$ 表示Eligibility traces，$\delta$ 为TD error，$\mathrm{w}$ 是state的估计value，$\bigtriangledown v(S,\mathrm{w})$ 就是$\mathrm{1} (S_t = s)$：
从算法流程可以看到，我们也是从episode的初始状态开始，按照time step向后逐个更新value，但是在更新value时会乘以权重 $\mathrm{z}$ ，这个权重就是Eligibility traces，假设当前时刻的状态为 $s_t$，则Eligibility traces包含了时刻 $t$ 之前出现过的状态 $s$ 的频率和时间信息。因此，TD($\lambda$) 就可以看成我们在当前状态，沿着time-step向更早的时间看，考虑更早状态的影响，而不是之后状态的影响。所以这种操作就称为 backward view.
4.4 Equivalence
当 $\lambda=0$ , 就变成了 1-step TD——Eligibility traces 取值只有0和1，且只有$S_t = s$ 时为1，结合上面的小人backward view 图，即如果此时我在 $S_{t+1}$ 时，只看前一步 $S_t$ 等价于我只向后看一步（前后其实只是相对的）。
当 $\lambda=1$，Eligibility traces就不会因为时间的衰减而指数衰减，只会受到 $\gamma$ 影响，此时 TD(1)就退化成了一个MC，同时相比原始的MC实现方法，TD(1) 可以online进行，无需等到终止状态的出现。
现在考虑 online 的情况，假设状态 $s$ 在时间步 $k$ 时出现：
下式表示，TD(1) 的TD error等价于MC error。
因此，$\lambda=1$ 时 TD误差可以简化为MC误差，也就类似every-visit MC，区别在于TD是在线更新的，每个step都会更新，如果TD使用离线更新，就完全等价于MC：
总的来说，有以下一个关系：
