这一课帅小哥主要讲的内容是预测的部分，在第五课会加入控制的部分。其中预测的部分主要是两个相似的算法，一个为 Monte-Carlo（MC），另一个为 Temporal-Difference（TD）。两者的区别主要在于，MC 为需要在出现终止状态后，才能得到 Reward，而 TD 则是实时的。
Monte-Carlo
Monte-Carlo强化学习指的是，在不清楚 MDP 状态转移和奖励方案的情况下，直接通过经历完整的 episode 来学习状态的 value。一般而言，一个状态的 value 为，其在多个 episode 下的 value 的平均值。
注：episode 指的是不定的起始状态开始，直到某一特定的终止状态结束。
其评价每个状态的 value 的主要算法如下两种：
- 首次访问 Monte-Carlo 策略评估
首先，固定一个策略 $\pi$ ，之后使用这个策略进行多个完整的 episode。对于每个 episode，当且仅当状态第一次出现时才列入计算：
1
2
3N(s) = N(s) + 1 # 状态计数 +1 S(s) = S(s) + G_t # 总收获更新 V(s) = V(s) / N(s) # 状态的 value 更新注：当 N 很大时， $V(s)$ 就是我们所求估计
- 每次访问 Monte-Carlo 策略评估 同首次访问 MC 算法一致，但是这个算法中，每次出现在状态转移链中的状态都会更新。
Temporal-Difference
首先，在开始 TD 算法前，小哥补充了一个 baby math，即一个求平均值的操作其实是可以写成一种迭代的样式如下：
\[\begin{split} \mu_k &= \frac{1}{k} \sum_{j=1}^k x_j \\ &= \mu_{k-1} + \frac{1}{k}(x_k-\mu_{k-1}) \end{split}\]再抽象点就得到了以下公式：
\[\begin{split} V(S_t) &= V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t)) \\ & = V(S_t) + \alpha(G_t - V(S_t)) \end{split}\]而 TD 算法就是从这里开始的。TD 算法和 MC 算法不同的地方在于，其不用完成整个 episode 才得到状态的 value，即它可以学到一个不完整的 episode，通过自身的引导（bootstrapping）来猜测结果。其公式如下：
\[V(S_T) = V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t))\]注：其中 $R_{t+1}$ 为离开该状态的时候的即刻奖励， $S_{t+1}$ 为下一状态的预估状态价值。
TD 与 MC 的对比
- TD 可以在知道最终结果前就可以学习，MC 必须在 episode 结束后才知道。 注：小哥举了个例子，说你不能在被车撞死后再重来。
- MC 是基于某一个策略的无偏估计，而 TD 则是有偏估计。（毕竟 TD 瞎猜了）
- MC 没有 bias，但是有较高的变异性（Variance），对初值不敏感，而 TD 有 bias，低变异性，但效率高。
注：MDP、TD 和 MC 都是计算状态 value 的方案