四、不基于模型的预测

在这种情况隙中，agent的组成只包含策略和奖励

蒙特卡洛算法：

蒙特卡罗是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在（放弃随机采样，而采用类似全采样这样的确定性方法）获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。

MC:

Model-free：不需要知道状态转移概率和奖励

MC通过大量完整的片段学习推导出平均收获值代替状态价值

PS:所有的片段必须有终止状态，因为使用的是每个状态在每个片段中价值函数的真值$G_t$

对于同一个片段中同一状态在不同时刻出现计算状态价值的方法：

First visit：只记录每次片段中第一次访问的价值，然后将每个片段平均后为最终的价值

Every visit：在一个片段中多次遇见同一个状态也需要纳入价值中并最终进行平均值计算

由于MC需要记录每一次每一个状态的价值函数，为了减少数据存储，采用累进更新平均值：

可以用非固定量$\alpha$代替1/k，可以避免还有计数。后面的差值可以看作是对前一次的状态价值进行修正

k表示片段个数/统计节点的次数

$$\begin{gathered} {\mu }_k={\mu }_{k-1}+\frac{1}{k}(x_k-{\mu }_{k-1}) \\ {\mu }_k={\mu }_{k-1}+\alpha (x_k-{\mu }_{k-1}) \\ V\left(S_t\right)\leftarrow V\left(S_t\right)+\alpha \left(G_t-V\left(S_t\right)\right) \end{gathered}$$

TD(0)：

model-free

根据不完整的片段中已知的信息，通过自主学习预估后续状态的目标值代替真值从而求累进平均值，并且在计算后续片段中继续更新价值

自主学习：利用估计值代替真值并且在后续片段中继续更新价值
$$\begin{gathered} V\left(S_{t-1}\right)\leftarrow V\left(S_{t-1}\right)+\alpha \left(R_t+\gamma V\left(S_t\right)-V\left(S_{t-1}\right)\right) \\ V\left(S_t\right)\leftarrow V\left(S_t\right)+\alpha \left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)\right) \end{gathered}$$
误差项：$\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)\right)$

MC,TD(0),DP，穷举区别：

• 当使用单个采样，状态转移概率未知，同时不经历完整的状态序 列更新价值的算法是 TD 学习;
• 当使用单个采样，状态转移概率未知，但依赖完整状态序列的算法是 MC 学习;
• 当考虑全宽度采样，需要知道状态转移概率，但对每一个采样经历只考虑后续一个状态时的算法是 DP 学习;
• 如果既考虑所 有状态转移的可能性，同时又依赖完整状态序列的，那么这种算法是穷举法。

TD($\lambda$)

TD(0)可以看成基于1-步预测（$v_{s+1}$) ，$G_t^{(1)}=R_{t+1}+\gamma V\left(S_{t+1}\right)$

MC可以看成是基于n-步预测$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\dots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V\left(S_{t+n}\right)$

因此想要找到最佳预测的步数，引入了$\lambda$-收获
$$\begin{array}{c}{G}_t^{\lambda }=(1-\lambda ){\sum }_{n=1}^{\infty }{\lambda }^{n-1}{G}_t^{(n)}\\ V\left(S_t\right)\leftarrow V\left(S_t\right)+\alpha \left(G_t^{\lambda }-V\left(S_t\right)\right)\end{array}$$
离线学习是在经历所有Episode后进行状态价值更新；而在线则至多经历一个Episode就更新依次状态价值。

前向观点：

$\lambda \in [0,1]$

$G_t$是要知道完整的片段序列才能计算，必须要经历完整的状态序列获得包括终止状态的每一个状态的即时奖励才能更新当前状态的价值，TD($\lambda$ )与MC特点相同

后向观点：用于不完整的片段

效用迹结合频率启发和就近启发，效用迹定义:

每一个状态都有一个E值， E值随时间而变化：

每个状态都有对应的E值，根据已经经过的状态序列来计算得到，并且随时间变化。当该状态连续出现时，E值增加，但存在饱和现象（上限），当一段时间内该状态不出现，E值就趋近于0

$$\begin{array}{c}{E}_0(s)=0\\ E_t(s)=\gamma \lambda E_{t-1}(s)+1\left(S_t=s\right),\gamma ,\lambda \in [0,1]\end{array}$$

如果考虑效用迹后，价值函数公式：
$$\begin{array}{c}{\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{array}$$
当$\lambda$=0，因为在t时刻当前状态一定是s当前状态，所以$E_t(s)=1$，$V(s)\leftarrow V(s)+\alpha {\delta }_t$等同于TD(0)

当 λ = 1 时，在每完成一个状态序列后更新状态价值时，其完全等同于 MC 学习;但在引 入了效用迹后，误差项可以每经历一个状态就更新，但状态价值是在整体片段序列结束后，这种实时更新的方法并不完全等同于 MC。

当 λ ∈ (0, 1) 时，在每完成一个状态序列后更新价值时，基于前向认识的 TD(λ) 与基于反向 认识的 TD(λ) 完全等效;不过在进行在线实时学习时，两者存在一些差别。

采用几何分布的原因：无记忆性？

MC	TD	备注
通过大量完整的片段学习推导出平均收获值代替状态价值	TD 目标值（基于即时奖励和下一状态的预估价值）代替真实值，通过求累进平均值求状态价值函数
MC状态价值结束必须要等到片段结束才更新value	在知道结果之前就可以学习，也可 以在没有结果时学习，还可以在持续进行的环境中学习
无偏估计，方差大	绝大多数情况下是有偏估计，方差下（对初始状态价值的依赖较大）	偏倚预估的平均值与实际平均值的偏离程度；方差评估单次采样结果相对于与平均值变动的范围大小
不具有马尔可夫性	具有马尔可夫性