内容纲要

欢迎转载,作者: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

RL_04_001

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

RL_04_002

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

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

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

RL_04_003

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

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

RL_04_004

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

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

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

特点

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

TD策略评估

RL_04_005

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

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

MC vs TD vs DP

RL_04_006

 

MC

TD

DP

Sampling

Yes

Yes

No

Bootstrapping

No

Yes

Yes

另外一个对比图:

RL_04_007

  • 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)

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

RL_04_008

MC:

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

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

计算过程:

RL_04_009

第一轮结果:

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))

计算过程

RL_04_010

第一轮结果:

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

RL_04_011

相应回报与Value计算

RL_04_012

Forward-view TD(λ):

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

每个n-step G的权值:

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

RL_04_013

加权平均:

RL_04_014

使用加权平均更新V:

RL_04_015

Backward-View TD(λ)

资格迹:Eligibility Traces

公式

RL_04_016

含义:

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

有这么个序列:

铃声,铃声,亮灯,被电击

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

….

这个资格迹可以权衡

RL_04_030

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

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

这个可以作为权值

Value更新:

之前

RL_04_017

变成

RL_04_018

其中

RL_04_019

TD(0) 与 TD

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

λ为0,则:

RL_04_020

由:

RL_04_021

可知:

RL_04_022

TD(1) 与MC:

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

Ek(s) = 1

 当λ为1时:

RL_04_023

由:

RL_04_024

可知:

RL_04_025

对比MC:

RL_04_026

补充材料:Offline Updates vs Online Updates

RL_04_027

RL_04_028

总结:

RL_04_029

Offline的话:几个完全等

Online的话:不完全等

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