Lecture 4: Model-Free Prediction

一、Monte-Carlo Learning

（一）Monte-Carlo Reinforcement Learning

MC方法可直接从经验中学习
MC是model-free：不了解MDP转换/奖励
MC从完整的episode中学到：no bootstrapping
MC使用最简单的想法：value = mean return
警告：只能将MC应用于episodic MDPs
- All episodes must terminate

（二）Monte-Carlo Policy Evaluation

目标：从policy $\pi$ 规定的经验中学习 $v_\pi$
回想一下，回报是总折扣奖励：
回想一下，value function是预期的回报：
蒙特卡洛策略评估使用经验均值回报而非预期回报

（三）First-Visit Monte-Carlo Policy Evaluation

评估状态s
只统计状态s第一次出现在episode中时的长期回报
增量计数器 $N(s)\leftarrow N(s)+1$
总收益增加 $S(s)\leftarrow S(s)+G_t$
价值由平均回报估算 $V(s)= S(s)/N(s)$
根据大数定律， $V(s)\rightarrow v_\pi(s)$ as $N(s)\rightarrow \infty$

（四）Every-Visit Monte-Carlo Policy Evaluation

评估状态s
统计状态s每一次出现在episode中时的长期回报
增量计数器 $N(s)\leftarrow N(s)+1$
总收益增加 $S(s)\leftarrow S(s)+G_t$
价值由平均回报估算 $V(s)= S(s)/N(s)$
根据大数定律， $V(s)\rightarrow v_\pi(s)$ as $N(s)\rightarrow \infty$

（五）Incremental Monte-Carlo

1、Incremental Mean
序列 $x_1,x_2,...$ 的平均值 $\mu_1,\mu_2,...$ 可以递增计算，

是误差，平均值将会朝着误差的方向移动更新。
2、增量蒙特卡洛更新

在episode $S_1,A_1,R_2,...R_T$ 后逐步更新 $V(s)$
对于每个具有回报 $G_t$ 的状态 $S_t$
在非平稳问题中，跟踪连续平均值（即忘掉旧episodes.）可能很有用。

我们的环境一直在变化，很久以前的episodes对于我现在没有什么用，可能还会拖累我们的更新。所以我们将1/N用 $\alpha$ 代替，每次让值朝着比较新的return的方向更新，而不需要使用真正的平均值。
不会直接更新到平均值，平均值可能还没达到正确的程度。取一个恒定步长进行更新。
类似于常见的梯度下降法的更新公式

二、Temporal-Difference Learning

TD方法可直接从经验中学习
TD是model-free:的：不了解MDP转换/奖励
TD通过自举（bootsstrapping）从不完整的episodes中学习
- 利用估计来代表episode的剩余部分。
TD将猜测更新为猜测
- 更新最开始的猜想，得到后来的猜想

（一）MC and TD

目标：从策略 $\pi$ 下的经验中在线学习 $v_\pi$
Incremental every-visit Monte-Carlo
- 朝着实际回报 $G_t$ 的方向更新价值 $V(S_t)$
最简单的时序查分算法：TD(0)
- 朝着估计回报 $R_{t+1}+\gamma V(S_{t+1})$ 的方向更新价值 $V(S_t)$
- $R_t+1+\gamma V(S_{t+1})$ 被称为TD target
- $\sigma_t = R_{t+1}+\gamma V(S_{t+1})$ 被称为TD error

（二）Driving Home Example

在这个例子中，reward是每一段行程消耗的时间（Elapsed Time）。过程不加折扣（）,因此每个状态的回报就是从这个状态开始直到回家实际经过的总时间。每个状态的价值是剩余时间的期望值。第二列数字给出了遇到的每个状态的价值的当前估计值。

一种描述蒙特卡洛方法的步骤的简单方法是在时间轴上画出行车总耗时的预测值（最后一行数据）。箭头表示的是MC方法推荐的对预测值的改变。这个值正是每个状态的价值的估计值（预估的剩余时间）与实际值回报（真是的剩余时间）之差。例如，当你下高速时，你估计还有15分钟就能到家。但实际上你需要23分钟。此时就可以用公式

确定离开高速后的剩余时间估计的增量。这时的误差是是8分钟。假设步长参数是1/2，根据这一经验，离开高速后的预估剩余时间会增加4分钟。在当前这个例子中，这个改变可能过大了，因为堵在卡车后面知识偶然运气不好。无论如何，这种更新只能离线进行，即只有到家以后才能进行更新，因为只有到家你才知道实际的回报是多少。

是否真的需要知晓最终结果才能开始学习呢，假设有一天你回家也是预计30分钟到家，到途中碰到了严重的交通拥堵，离开办公司25分钟仍然在高速上寸步难行，这时你估计还有25分钟才能到家，总共50分钟。是否只有到家后才能增加对初始状态的估计值呢？如果使用蒙特卡洛方法，答案是肯定的，因为我们还不知道真正的回报。

但是根据TD的方法，我们可以立即学习，将初始估计得30分钟增加到50分钟。事实上，每一个估计都会跟着其后继的估计一起更新。回到例子，右图显示了根据TD规则推荐的总时间的预测值的变化。每个误差都与预测值在时序上的变化（即预测中的时序差分）成正比。

（三）Advantages and Disadvantages of MC vs. TD

TD可以在知道最终结果之前学习
- TD可以在每一步之后在线学习
- MC必须等到episode结束才能知道回报
TD可以在没有最终结果的情况下学习
- TD可以从不完整的序列中学习
- MC只能从完整序列中学习
- TD在持续（非终止）环境中工作
- MC仅适用于episode（终止）环境

（四）Bias/Variance Trade-Off

回报 $G_t=R_{t+1}+\gamma R{t+2}+...+\gamma^{T-1}R_t$ 是 $v_\pi(S_t)$ 的无偏估计。
真实TD target $R{t+1}+\gamma v_\pi (S_{t+1})$ 是 $v_\pi(S_t)$ 的无偏估计。
这里的 $v_\pi(S_t)$ 是真实的 $v_\pi(S_t)$ 。贝尔曼方程得到的，理想状态下的。
TD target $R{t+1}+\gamma v_\pi (S_{t+1})$ 是 $v_\pi(S_t)$ 的有偏估计。
这里的 $v_\pi(S_t)$ 是我们目前最符合实际的猜测。
TD target的方差比回报低得多
- 回报取决于许多随机actions，transitions, rewards
- TD target取决于一个action，transitions, rewards

（五）Advantages and Disadvantages of MC vs. TD (2)

首先理解一下方差。
蒙特卡洛通过与环境交互得到序列的回报信息，然后用这些信息求平均，就可以得到估计得价值函数。但是每次采样得到的回报差别可能很大，因为在计算回报时每一步都会收到噪声干扰，导致方差很大。
偏差就是你对V有一些估计，这可能是错误的，并不是真实值。这不是干扰。

MC具有高方差，零偏差（ $G_t$ 在每一步转换都会有噪声干扰，得到受到干扰的reward，所以方差比较大）
- 良好的收敛性
- （具有函数近似）
- 对初始值不太敏感
  因为我们不从初始值进行自举。开始的地方很重要，但是我会花更长的时间来调整你那些错得很厉害的值，把他们改成正确的值。但他不做自身循环。他不使用自己。
- 很容易理解和使用
TD方差低，有些偏差（因为只会受到一步干扰，所有方差较小）
- 通常比MC更高效
- TD(0)收敛至 $v_\pi(S_t)$
- （但并非总是用近似函数）
  TD里的偏差可能是的算法不起作用
- 对初始值更敏感

（六）Random Walk Example

随着episode的增多，开始趋近于真实的value（那条直线）。

Random Walk: MC vs. TD

从上图可以看出TD的效果比MC要好，RMS误差减小的很快。
调整不同的可以达到更好的效果。

（七）Batch MC and TD

MC和TD收敛： $V(s)\rightarrow V_\pi(s)$ ,随着 $experience\rightarrow \infty$
但是对于有限经验的批处理解决方案呢？
例如：重复采样episode $k\in[1,K]$
将MC或TD(0)应用于episode $k$
给定近似价值函数V，在访问非终止状态的每个时刻t，使用

或

计算相应的增量，但是价值函数仅根据所有增量的和改变一次。然后，利用新的值函数再次处理所有可用的经验，产生新的总增量，依此类推，知道价值函数收敛。我们称这种方法为批量更新，因为只有在处理了整批的训练数据后才进行更新。

AB Example

两种状态A，B；没有折扣； 8个episode的经验

求

Certainty Equivalence

MC收敛到具有最小均方误差的解决方案
- 最适合观察到的收益
- 在AB示例中， $V(A)= 0$
TD(0)收敛到最大似然马尔可夫模型的解
- 最适合数据的MDP $\left\langle S,A,P,R,\gamma\right\rangle$ 的解决方案
- 在AB示例中， $V(A)= 0.75$

（八）Advantages and Disadvantages of MC vs. TD (3)

TD利用马尔科夫性质
- 通常在马尔可夫环境中效率更高
MC不利用马尔科夫性质
- 通常在非马尔可夫环境中更有效

（九）United View

1、Monte-Carlo Backup

蒙特卡洛所做的基本上是这里一个完整轨迹的取样，然后使用该样本来更新价值函数。

2、Temporal-Difference Backup

时序差分备份只有一步，我们对环境和动作进行采样，当在下一步结束时，看看价值函数，备份该价值函数。得到在一个步骤中发生的样本，不会一直走到尽头。

3、Dynamic Programming Backup

动态规划也是一步向前搜索，但我们没有取样，我们必须了解动态，我们使用这些动态来计算这个期望。做完整的备份来算出期望值。

4、Bootstrapping and Sampling

Bootstrapping: 更新涉及估计
- MC不自举
- DP自举
- TD自举
  DP和TD用了贝尔曼方程，对下一步状态进行估计。
Sampling: 期望更新样本
- MC samples
- DP does not sample，穷举考虑每一个可能性
- TD samples

5、United View of Reinforcement Learning

为什么我们假设一步之后的值比一步之前更准确？为什么不转移到另一个方向，替代的算法会得到正确的答案吗？
不会得到正确的答案。事实上，即使你做了什么事情，比如让这些东西相互靠近，然后将TD误差等均方误差最小化，你找到了错误的答案，你实际上通过另一种方法得到了错误的答案。为什么我们给你直觉，直觉是，如果你采取一个步骤，你在某种意义上总是更准确一点，因为这一步是真实的一步，涉及到了真实回报，也是真实动态的一步，然后你估计你结束之处的价值函数，但是因为你已经包含了一个真正的动态和真正的回报，你在某种意义上更准确，如果你采取足够的这些步骤，真正的动态总是带你接近真理。

三、TD( $\lambda$ )

（一）n-Step TD

1、n-Step Prediction

让TD目标展望未来的n步

2、n-Step Return

考虑 $n=1,2,\infty$ 的n步收益：
定义n步收益
n步时序差分学习

3、大型随机游动示例

当n趋近于无穷，接近于蒙特卡洛，会得到很高的错误率，可能是训练时间较短。
n=1时，TD(0)表现很好。

4、平均n步回报

我们可以对不同n取n步收益的平均值
例如：平均两步和四步收益
合并来自两个不同时间步的信息
我们能否有效地结合所有时间步骤中的信息？

（二）Forward View of TD( $\lambda$ )

如果，则整个更新被简化为只有第一部分的更新，即单步时序差分更新；当时，则整个更新被简化为最后一部分的更新，即蒙特卡洛更新。

The $\lambda$ -return $G_t^\lambda$ 结合了n步return $G_t^{(n)}\$
使用权重 $(1-\lambda)\lambda^{(n-1)}$

可以把TD( $\lambda$ )看作平均n步更新的一种特例，这里的平均值包含了所有可能的n步更新，每一个按比例 $\lambda^{n-1}$ 加权，这里 $\lambda\in[0,1]$ ,最后乘上正则项 $1-\lambda$ 保证权值的和为1。产生的结果为 $\lambda$ 回报。
Forward-view TD( $\lambda$ )

（三） $TD(\lambda)$ Weighting Function

lambda-回报中每个n-步回报的权重

参数表征了权值衰减的程度，因此就确定了在更新时回报算法往后看多远。
-回报的定义为

在到达一个终止状态后，所有的后续n步回报等于。可以将终止状态之后的计算项从主要的求和项中独立出来。

（四）Forward-view $TD(\lambda)$

前向视图，如何通过未来的收益和状态更新每一个状态值

向 $\lambda$ -return更新值函数
前向视图通过观察未来来计算 $G_t^\lambda$
像MC一样，只能根据完整episodes进行计算

（五）Forward-View $TD(\lambda)$ Large Random Walk

性能由最开始10个episode中19个状态的真实价值和估计价值的均方根误差的平均值来衡量，两种算法的性能相当。在两种情况下，都是在n-步算法的n和-回报的取中间值时获得最好的性能。

（六）Backward View $TD(\lambda)$

Forward view提供理论
Backward view提供了机制
从不完整的序列在线更新每一步

Eligibility Traces（资格迹）

信用分配问题：电铃还是电灯引起电击？
频率启发式：将信用分配给最频繁的状态
新近度启发式方法：将信用分配给最近的状态
资格迹结合了两种启发式方法：

资格迹是 $E_t$ 是一个和权值向量同维度的向量。权值向量是一个长期的记忆，在整个系统的生命周期中进行积累；而资格迹是一个短期记忆，其持续时间通常少于一个episode的长度。资格迹辅助整个学习过程，它们唯一的作用是影响权值向量，而权值向量则决定了估计值。

在 $TD(\lambda)$ 中，资格迹向量被初始化为0，然后再每一步累加价值函数的梯度，并以 $\lambda \gamma$ 衰减。在这里 $\gamma$ 是折扣系数，而 $\lambda$ 为衰减率参数。资格迹追踪了对最近的状态评估值做出了或正或负贡献的权值向量的分量。这里的最近由 $\lambda \gamma$ 来定义。

我们回顾了我们访问的状态的时间，所以这是一个特定状态的资格迹，竖道是我们访问的那个时刻，基本上每次我们访问那个状态，就增加资格迹，当我们不去访问它时，我们就指数地减少资格迹。

Backward View $TD(\lambda)$

保持每个状态的资格迹
更新每个状态s的值 $V(s)$
与TD错误 $\delta_t$ 和资格迹 $E_t(s)$ 成比例
当一个强化学习事件出现时，我们认为这些贡献“痕迹”展示了权值向量的对应分量有多少“资格”可以接受学习过程引起的变化。我们关注的强化学习事件是一个又一个时刻的单步时序差分误差。预测的状态价值函数的时序差分误差为

在 $TD(\lambda)$ 中，权值向量每一步的更新正比于时序差分的标量误差和资格迹。

在时间上往回看，每个时刻我们计算当时的时序查分误差，并根据之前状态对当前资格迹的贡献来分配它。可以想象在一个状态流中，计算时序差分误差，然后将其传播给之前访问的状态。当时序差分误差和迹同时起作用时，使得式子得到更新。

（六）Relationship Between Forward and Backward TD

1、 $TD(\lambda)$ and $TD(0)$

当 $\lambda=0$ ，只有当前状态被更新。
$E_t(s)=1,$ 此时相当于时序差分。也就是TD(0)。
这完全等同于 $TD(0)$ 更新

TD(0)仅仅让当前时刻的前导状态被当前的时序差分误差所改变。对于更大的 $\lambda(\lambda<1)$ ，更多的之前的状态会被改变，越远的状态改变越少，这是因为对应的资格迹更小。也可以这样说，较早的状态被分配了较小的信用来“消费”TD误差。

2、 $TD(\lambda)$ and MC

当 $\lambda=1$ 时，信用被推迟到了episode结束。
考虑具有离线更新的episodic环境
在episode过程中， $TD(1)$ 的总更新与MC的总更新相同

对于前视图和后视图 $TD(\lambda)$ ，离线更新的总和是相同的
如果 $\lambda=1$ ，那么之前状态的信用每步仅仅衰减 $\gamma$ 。这个恰好和蒙特卡洛算法的行为一致。

3、MC and TD(1)

考虑在时间步k访问一次s的episode，
自访问以来的TD（1）资格迹折扣时间
TD(1)更新在线累积误差
到episode结束时，它累计了总误差

4、Telescoping in TD(1)

当 $\lambda=1$ 时，将将TD误差缩合为MC误差

5、 $TD(\lambda)$ 和 $TD(1)$

$TD(1)$ 大致等于every-visit蒙特卡洛
误差是在线累计的，一步接一步
如果值函数仅在episode结束时离线更新，那么，总更新与MC完全相同

6、Telescoping in $TD(\lambda)$

7、Forwards and Backwards $TD(\lambda)$

考虑在步骤k中访问一次s的episode
自访问以来 $TD(\lambda)$ 资格迹折扣时间，
Backward $TD(\lambda)$ 在线更新累积误差
到episode结束时，它会累计 $\lambda-return$ 的误差
对于对s的多次访问， $E_t$ 会累积许多误差

8、Offline Equivalence of Forward and Backward TD

离线更新

更新在episode中累积
但在episode结束批量应用

9、Onine Equivalence of Forward and Backward TD

在线更新

$TD(\lambda)$ 更新将在episode内的每个步骤在线应用
前视和后视 $TD(\lambda)$ 略有不同
新：精确的在线实现了完美的等效性
- 通过使用略有不同的资格迹形式
- Sutton and von Seijen, ICML 2014

10、Summary of Forward and Backward $TD(\lambda)$

= 表示episode结束时的总更新量相等。

最后编辑于：2019.12.23 12:05:51

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,236评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,867评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,715评论 0赞 340
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,899评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,895评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,733评论 1赞 283
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,085评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,722评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,025评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,696评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,816评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,447评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,057评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,009评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,254评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,204评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,561评论 2赞 343