欢迎转载，作者：Ling，注明出处：强化学习教程: 04-Model-Free Evaluation, MC,TD and TD(λ)

本章主要内容：

• 蒙特卡洛学习：Monte-Carlo Learning，MC
• 时序差分学习：Temporal-Difference Learning,TD
• λ时序差分学习：TD(λ)

前面已经讨论过model-based RL和model-free RL的区别，本章主要讨论model-free RL

不基于模型的学习方法：model-free learning

不需要知道状态转移概率矩阵，Reward Function，和整个模型

基于V函数:

基于Q函数：

Model-free Control：Q-learning

本章讲基于V函数的model-free的Predict，下一周讲model-free的Control

前面已经介绍了predict和control的区别

蒙特卡洛学习：Monte-Carlo Learning，MC

特点：

• 直接从经验片段学习
• 是免模型的，不需要MDP 转移矩阵和奖励的知识
• 从完整的片段中学习，没有自助抽样学习(bootstrapping)
• 使用最简单的可能思想：价值等于平均回报
• 提醒：MC只能在片段化的MDP中使用，而且每个片段必须是终止的，也就是要达到结束状态

MC策略评估：初次访问蒙特卡洛策略评估 vs 每次访问蒙特卡洛策略评估

• 初次访问蒙特卡洛策略评估：First-Visit Monte-Carlo Policy Evaluation

• 每次访问蒙特卡洛策略评估：Every-Visit Monte-Carlo Policy Evaluation

区别仅仅在于在一个样本/Episode过程中更新每个状态访问的次数，以及更新回报的次数上，一个是在一个样本，一个状态只在第一次访问时更新次数以及回报，另一个是每次都更新。

• 提高效率：对于每次访问蒙特卡洛策略评估，有一种提高计算效率的方法：

我们先来看一般的均值计算公式的变形：

第k步的均值，等于上一步均值，加上本步值减去上一步均值，除以K

对于每次访问蒙特卡洛策略评估也需要求G的和，然后除以N(s), 也是要给求均值的问题，每次其中G可以看成是x，v是μ

这样仅需要保存上一次值即可，无需保持所有值

• α：另外有时候会用α替代1/N(st)

时序差分学习：Temporal-Difference Learning,TD

特点：

• TD和MC一样，也是直接从经验片段中学习
• 是免模型的
• 从不完整的片段中学习，利用bootstrapping，和MC的区别在这
• 用一个估计来更新价值函数的估计

TD策略评估：

和“每次访问蒙特卡洛策略评估”相比，主要是红色部分不同，因为每次TD只向前走一步，而MC是完整的一个episode

• 目标项：Gt和Rt+1 + γV (St+1)
• 误差项：Gt − V (St) 和 Rt+1 + γV (St+1) − V (St)

MC vs TD vs DP

另外一个对比图：

• Full表示样本要越全
• Deep表示每个样本要越完整

MC vs TD 优劣势对比：

TD通过每步都修正，可以让方差降低

偏差指和真实情况相比的差别，MC全局考虑，没有偏差，TD局部考虑，可能有些步骤会有偏差

TD会考虑之后一步的影响，所以它会利用马尔科夫性质

直觉上：

TD会根据最新当前情况修正V

举例：说明MC和TD的区别

我们有2个状态，8个经验片段/样本，同事γ折扣为1：

A, 0, B, 0

B, 1

B, 1

B, 1

B, 1

B, 1

B, 1

B, 0

计算V(A)和V(B)

图示：通过样本我们可以得到如下图

MC：

计算公式：始终和V(B)没啥关系

V (St) = V (St) + 1/N * (Gt − V (St))

计算过程：

第一轮结果:

V(A) = 0
V(B) = 3/4

第二轮结果:

V(A) = 0

TD:

计算公式：第二轮时可以用到最新的V(B)

V (St) = V (St) + 1/N * (Rt+1 + γV (St+1) − V (St))

计算过程

第一轮结果:

V(A) = 0
V(B) = 3/4

第二轮结果:

V(A) = 3/4

感觉TD效果更佳

TD(λ)：一种介于MC和TD之间的学习方法

分类：Forward-View TD(λ) vs Backward-View TD(λ)

Forward-View TD(λ)

n-step TD:

n步预测：TD只看下一步，MC必须看完整的, n-step TD只看n-step

相应回报与Value计算：

Forward-view TD(λ)：

n-step TD效果并不好，所以我们可以把n-step TD的不同n值结果加权求平均,这就是TD(λ)

每个n-step G的权值:

该权值从(1-λ)一直递减到

加权平均:

使用加权平均更新V：

Backward-View TD(λ)：

资格迹：Eligibility Traces

公式：

含义：

表明在一段时间步内是否反复发生，例如：

有这么个序列：

铃声，铃声，亮灯，被电击

E0(铃声)=0

E0(亮灯)=0

E0(被电击)=0

E1(铃声)=γ*λ*E0(铃声)+1=0+1=1

E1(亮灯)=0

E1(被电击)=0

E2(铃声)=γ*λ*E1(亮灯)+1=γ*λ+1

E2(亮灯)=0

E2(被电击)=0

E3(铃声)=γ*λ*E2(铃声)+0

E3(亮灯)=γ*λ*E2(亮灯)+1 = 1

….

这个资格迹可以权衡：

如果经常发生，E会更大，但是会根据λ衰减

如果最近发生，E也会更大

这个可以作为权值

Value更新：

之前

变成

其中

TD(0) 与 TD

实际上之前的TD，也就是TD(0):

λ为0，则：

由：

可知：

TD(1) 与MC:

假设在第k步第一次访问s

Ek(s) = 1

 当λ为1时：

由：

可知：

对比MC：

补充材料：Offline Updates vs Online Updates

总结：

Offline的话：几个完全等

Online的话：不完全等

本章基本上都是对V函数进行更新