强化学习教程: 04-Model-Free Evaluation, MC,TD and TD(λ)
欢迎转载,作者: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函数:
Model-free Predict |
Model-free Control |
MC |
MC control |
TD |
Sarsa |
TD(λ) |
Sarsa(λ) |
基于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
|
MC |
TD |
DP |
Sampling |
Yes |
Yes |
No |
Bootstrapping |
No |
Yes |
Yes |
另外一个对比图:
- Full表示样本要越全
- Deep表示每个样本要越完整
MC vs TD 优劣势对比:
|
MC |
TD |
片段完整性 |
完整,需终止 |
部分,无需终止 |
方差 |
高 |
低 |
偏差 |
0 |
有些 |
收敛 |
一定收敛 |
不一定收敛 |
初始值 |
不敏感 |
敏感 |
效率 |
低 |
高 |
马尔科夫性质 |
不利用 |
会利用 |
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函数进行更新
留言