David silver强化学习课程第四课 模型无关的预测
第四课 模型无关的预测
在上一节课中，主要讲了利用动态规划的方法求解MDP的预测和控制两个问题，本质上它是model-based的，需要知道模型的信息如状态转移矩阵和回报函数。但是通常遇到的强化学习问题是不知道环境全部信息的，但是具有MDP的形式，在缺乏状态转移矩阵和回报函数的情况下如何求解预测和控制问题？
本章主要讲了三种方法用来求解模型无关(model-free)的预测问题：蒙特卡洛方法(MC)，时间差分方法(TD)和介于这两者之间的TD(λ)方法。这三种方法需要智能体和环境进行交互，获取相关的信息，在此基础上进行预测。
1 蒙特卡洛方法
因为我们不知道环境的信息，此时需要按照某个策略π和环境进行交互（有中止状态），获得状态转移信息和奖励信息：
那么这个过程的回报可以写成：
回想之前讲过的状态s的状态值函数是未来期望回报，因此表示为：
这样可以发现，我们从环境交互中就获得了状态值函数的信息，也就是解决了预测问题。注意，在蒙特卡洛方法中用平均回报代替期望回报。
考虑这种情况，在智能体和环境交互的过程中，在一次episode中某个状态出现了多次，那么我们将如何计算它的Gt？这里出现了两种蒙特卡洛策略评估方法：
首次访问(First-Visit)蒙特卡洛策略评估：
无论每个episode中状态s出现了几次，只取其第一次出现的时刻计算Gt，并且在计算平均回报时此episode贡献一次s，根据大数定理，实验的次数越多，结果越接近真实情况。
每次访问(Every-Visit)蒙特卡洛策略评估：
对于每个episode出现n个状态s的情况，每次分别计算Gt并累加，在计算平均回报时此episode贡献n次s。同样的根据大数定理，实验的次数越多，结果越接近真实情况。
对蒙特卡洛算法有了基本的认识之后，在这里总结一下蒙特卡洛算法的特性：
- 可以看出MC是model-free的，它直接从episodes的经验中学习
- MC不是自举(bootstrapping)的，它利用完整的episode。自举是指状态值的更新依赖于其它状态值。
- MC利用平均回报代替期望回报
- MC仅仅可以解决episode的MDPs，每个episode必须是有终点的。
不论是First-Visit还是Every-Visit，在计算回报均值时，都是利用总回报除以状态s的总访问次数的，下面讨论增量形式的MC：
首先看一下均值的计算可以表现为增量形式：
将其应用到MC中可以得到状态值更新式：
在处理非静态问题时（随着时间变化MDP信息发生改变，例如状态转移概率和回报），使用这个方法跟踪一个实时更新的平均值是非常有用的，可以扔掉那些已经计算过的Episode信息。此时可以引入参数α来更新状态价值：
这里可以把Gt-V(St)理解为一种变化趋势，类似于学习速率的参数。
2 时间差分方法
与MC方法一样，时间差分方法（TD方法）也是直接从episode中进行学习，因而也是模型无关的，不过TD方法并不需要完整的episode，它是bootstrapping的。TD利用对episode的猜测来更新猜测。
MC方法更新V(s)时，需要知道Gt的值，这就需要MC获取完整的episode。那么我们可不可以在不获取完整episode的情况下，每走一步就更新一次V(s)？回想贝尔曼方程给出的V(s)的递归形式：
我们可以利用估计回报Rt+1 + γv(St+1)来表示Gt。
那么我们可以的到TD算法：
在这里
称为TD target，
称为TD error。
正如上面提到的，TD利用对episode的猜测来更新猜测。
3 MC、TD和DP的对比
MC和TD
（引出MC和TD优缺点时课程中给了很多事例，这里就不一一详说了）
-
TD在知道最终的结果之前就可以学习，而MC必须等到episode结束才可以学习
-
因为TD是每步更新的，MC是每episode更新的，因此TD可以从不完整的episode中学习，而MC只能从完整的episode中学习。换句话说，TD适用于non-terminating的环境，MC只适用于terminating环境。
-
MC的Gt是对vπ(St+1)的无偏估计，而TD target是对Vπ(St+1)的有偏估计
TD target依赖一组随机动作，状态转移概率和奖励；Gt依赖多组随机动作，状态转移概率和奖励。所以TD的方差更小。
MC具有良好的收敛性，对初始值不敏感；TD收敛性不好，对初始值敏感但是效率比MC高。
-
前面讨论的两种算法都是在大量采样下得到的结论。如果我们只有小批量采样数据，那么MC方法中的值函数将收敛到使均方误差最小的解，TD中的值函数将收敛到极大似然Markov模型对应的解。
-
TD算法使用了MDP问题的马儿可夫属性，在Markov 环境下更有效；但是MC算法并不利用马尔科夫属性，通常在非Markov环境下更有效。
DP，MC和TD
DP是model-based的，而MC和TD是model-free的，下面三个图解释了三种方法更新值函数的差别：
MC：
TD:
DP:
DP和TD都是用了bootstrapping，而MC没有使用bootstrapping；MC和TD都是用了sampling，而DP没有使用sampling。
下面这幅图从两个维度解释了这几种算法的区别，其中右上角多了一个穷举算法：
4 TD(λ)
TD基于每一步进行更新，MC基于每个episode进行更新，将这两者中和，我们可以得到每n步进行更新的TD算法。
可以看出MC实际上是特殊的TD。
现在V(st)可以由第n步的Gt进行更新，可以这样想，t时刻的状态s会对t+n时刻的状态s’产生影响，那么就由t+n时刻的状态s‘来更新t时刻的状态s。如果考虑某一状态实际上会对后续的所有状态产生影响，换句话说某一状态收到之前的所有状态的影响，该怎么表示呢？（站在值函数更新的角度来说，和马尔科夫状态不冲突）这时候我们可以考虑使用所有时间步1,2,3…n的
来更新当前时刻的V(s)。
综合考虑n个n-step回报对当前V(s)的贡献，引入参数λ对每一步的回报施加一个权重，得到λ-回报：
权重之和定于1。
对应的V(s)更新方式变为（此处指前向视角的TD(λ)）：
Forward-view TD(λ)
前向视角的TD(λ)使用λ-回报来代替TD-target，此时需要在每一轮episode结束后才可以计算λ-回报，它和MC是类似的。
Backward-view TD(λ)
对于后向视角的TD(λ)可以这样理解，状态s’之前的所有状态都对其有贡献，而不仅仅是前一个状态s对其有贡献，所以s‘的状态值不仅用来更新s的状态值，而且对它所经历过的所有状态的状态值都要更新。
为了区别这种贡献大小，引入资格迹的定义：
讨论之前所有的状态对当前状态的影响比重：
- 刚刚经历过的状态影响因子大，随着时间变化影响慢慢变小
- 经历次数多的状态影响因子大
因此我们引入资格迹来表示这种影响因子：
解释为：初始状态下所有的状态s资格迹都为0，现在每经历一个时间步t，所有状态的资格迹都乘以γλ退化，但是当前的状态在乘γλ的同时＋1，提高其资格迹。
有了资格迹的定义，我们现在描述后向视角的TD(λ)：
后向视角的TD(λ)可以在线的更新状态值，而不需要等到episode结束，这点类似于本章讲的TD(0)。这里注意更新V(s)时是对经历过的所有状态进行更新。
现在给出TD(λ)后向视角的on-line更新算法（on-line每一时间步更新一次误差，off-line指在episode结束后把所有的误差累积起来再更新）：
前向视角的TD(λ)提供理论，而后向视角的TD(λ)才是用来解决实际问题的方法。
TD(λ)和TD(0)
当λ=0的时候，只有当前的状态会被更新（由于每一步资格迹会乘γλ，因此只有当前状态的资格迹不为0）：
等价于本课一开始讲到的每步更新的TD，也就是TD(0)：
MC和TD(1)
上式是λ=1时，off-line的后向视角的TD累积误差，可以发现它更新的误差总量是等于MC更新的误差总量，此时TD(1)等价于every-step MC。注意TD(1)既可以用于连续式的任务，也可以用于片段式的任务。
前向视角和后向视角的等价性
其实前向后向两种视角，本质上是一回事（尤其在off-line更新方式下）。怎么定义本质上相同：证明在两种视角下，每个episode中所有的更新增量总和相同。
具体推导公式见https://zhuanlan.zhihu.com/p/27773020
为什么强调off-line更新方式下，前向视角和后向视角相同。因为在on-line更新方式下，Vt(St)是在变化的，只能说这种情况下前向视角和后向视角近似信箱等。随着α越来越小，越来越相近。
最后证明前向视角和后向视角在每个episode内的更新增量是几乎相等的，如果我们保证off-line更新，或者α足够小，那么就可以说是完全相等的。因此这两种视角在本质上是相同的。
放一张课程里的图解释这两种视角的等价关系（每个episode总更新的等价性）：
Exact On-line TD(λ)通过修改资格迹达到了完全等价。
参考资料：https://blog.****.net/u013745804/article/details/78196834
https://zhuanlan.zhihu.com/p/55788587