三种算价值的办法 — 动态规划、蒙特卡罗、时间差分
这一章讲三件事: 有了方程为什么还是算不出来;三种算法各自绕开了什么; 以及**「准但飘」和「稳但偏」这对取舍,是怎么在这里第一次出现的。**
它在全书链条里的位置:第一次真正「能跑」的地方。 第 03 章列出了方程, 这一章把它解出来。但这一章的三种办法全部建立在一张表上 —— 每个局面一格。 那张表写不下的时候,就到了第 05 章。
顶层全景:同一个数,三种算法各算一遍
这一章接着第 03 章那张「学生的一天」的图,一次都不换。
我们只盯一个数:「站在作业二这个圈上,以后总共还能拿多少」。 第 03 章用随机采样估过它,得到 2.348。这一章要用三种办法各算一遍,然后把三个数摆在一起。
要算的:作业二这个局面的价值(γ = 0.9)
① 动态规划 知道那张转移表 → 六条方程反复迭代到不再变 → 3.75
② 蒙特卡罗 不用表,随机走 4 条完整的路,取平均 → 2.348
③ 时间差分 不用表,只走一步就更新一次(步长 0.1) → 第一次更新只到 −0.2
★ 三个数并排,这一章要讲的所有事情都在里面:★
① 和 ② 差了 1.4 —— 因为 4 条路太少,② 飘得厉害(方差)
③ 第一次几乎没动 —— 因为它靠的是邻居的估计,而邻居此刻还是 0(偏差)
图说:这就是本章的主走查。第 2、3 节走 ①,第 4、5 节走 ②,第 6 节走 ③,
第 7 节说明它们其实是同一根轴上的三个位置。
(2.348 是书里给的;3.75 和 −0.2 是**我们按书里的转移表和奖励算出来的**,
算式在正文里写全了,可以自己核。)
1. 有了方程,为什么还是算不出来
这一节回答:第 03 章不是已经把问题变成一组方程了吗?
先看现象
第 03 章那条贝尔曼方程长这样:
作业二的价值 = (−2) + 0.9 × [ 0.6 × 通过的价值 + 0.3 × 睡觉的价值 + 0.1 × 休息的价值 ]
▲ ▲ ▲
这三个 0.6 / 0.3 / 0.1 从哪儿来? ┘
它们来自那张转移表。而真实环境里,没有人会把这张表交给你。
你不知道「在这个局面按这个键,有多大机会落到那个局面」。你只能去试。
这一章的三种办法,正是按「知不知道这张表」分的
| 办法 | 要不要那张表 | 换来什么 |
|---|---|---|
| 动态规划 | 要 | 必然收敛到唯一答案的保证 |
| 蒙特卡罗 | 不要 | 一个模型都不用,但必须等一整局跑完 |
| 时间差分 | 不要 | 每走一步就能学一次 |
书里对动态规划的定位说得很坦率: 它需要知道求解问题的全部信息, 「但是在强化学习的场景中,这些信息是很难被获取的」; 尽管如此,它提供的那套基本思路「被大多数强化学习算法所沿用」1。
所以第 2、3 节不是在教你一个能直接用的算法,是在教你后面所有算法的原型。
2. 动态规划:把方程从「等号」改成「赋值」
这一节走主走查的 ①。
先看名字
书里把这个词拆开解释了。「动态」指的是:求解的问题是序列化(一步接着一步、前后相连, 不是一堆互不相干的题目)的;「规划」指优化策略2。 它的套路是把复杂的问题拆成子问题 —— 书里举的例子是斐波那契数列: 第 4 个数等于前两个数之和,而第 3 个数又能继续往下拆,最后全部落到最朴素的那两个上2。
能用这套办法的问题要满足两条3:
| 条件 | 意思 | 我们的问题满足吗 |
|---|---|---|
| 最优子结构 | 大问题的最优解,可以由子问题的解拼出来 | 满足 —— 贝尔曼方程干的正是这件事 |
| 重叠子问题 | 子问题数量有限、而且反复出现,所以可以存起来重复用 | 满足 —— 价值函数就是那张「存下来的子问题答案表」 |
做法:把等号改成赋值,反复刷
贝尔曼方程是一个等式,两边都有未知数。把它当成一条赋值指令来用,就成了一个算法:
反复做: 每个局面的价值 ← 这一步的分数 + 0.9 × (按转移表加权的邻居价值)
每刷一遍,所有格子的数都往真值靠近一点。
走查 ①:在主走查那张图上刷三遍
初始时所有格子都填 0(睡觉是终点,永远是 0):
刷第 1 遍(用上一轮的数算,全是 0):
通过 ← 10 + 0.9×0 = 10.00
作业二 ← −2 + 0.9×(0.1×0 + 0.6×0 + 0.3×0) = −2.00
休息 ← 1 + 0.9×(0.9×0 + 0.1×0) = 1.00
作业一 ← −2 + 0.9×(0.3×0 + 0.7×0) = −2.00
刷第 2 遍(用第 1 遍的数):
作业二 ← −2 + 0.9×(0.1×1.00 + 0.6×10.00 + 0.3×0) = −2 + 0.9×6.10 = 3.49
▲
「通过」那 10 分,这一遍才传到「作业二」头上 ┘
刷第 3 遍:
休息 ← 1 + 0.9×(0.9×3.49 + 0.1×(−2.00)) = 1 + 0.9×2.941 = 3.65
作业二 ← −2 + 0.9×(0.1×1.00 + 0.6×10.00 + 0.3×0) = 3.49 (邻居还没更新完,暂时不动)
……一直刷到不再变为止,最后:
作业二 = 3.75 · 休息 = 3.93 · 通过 = 10.00 · 作业一 = −1.21 · 打游戏 = −5.84
**转移的机会和分数是书里的;这几轮迭代和最后那五个数是我们算的**,
按的是书里那张转移表和 γ = 0.9,可以自己核。
注意第 2 遍那一行:分数是「一层一层往回传」的。 「通过」的 10 分先落到自己头上,下一遍才传给「作业二」,再下一遍才传到「作业一」。 这个「往回传」的画面,是理解后面所有算法的关键 —— 学习就是让远处的分数一层层渗回来。
完整的算法:评估和改进轮流做
上面只是在评估一个给定的策略。要找到更好的策略,书里的做法是加一步4:
① 策略评估:照当前策略,把每个局面的价值刷到收敛
② 策略提升:每个局面上,改成挑「让『分数 + 折扣 × 下个局面价值』最大」的那个动作
③ 回到 ①,直到策略不再变
图说:这两步轮流做,书里叫策略迭代;
更一般地,「评估与提升交替」这个大套路,书里给了一个名字叫泛化策略迭代。
这个「评估 → 改进 → 再评估」的来回,是后面每一个算法的骨架。 第 07 章那条线在做它,第 08 章那条线在做它, 第 10 章两条线合流之后还在做它。 书里也明说:提升是单调的 —— 每改一次,策略只会变好不会变坏,而且有限步之内会停5。
书里还给了另一个变体:价值迭代 —— 不等评估收敛,每刷一遍就顺手取一次最大, 从最终状态开始一个一个状态往前推6。
3. 凭什么保证它会停:每刷一遍,差距至少缩小一成
这一节是本章唯一一处证明,而它值得看懂 —— 因为第 06 章会告诉你这条保证怎么没的。
先看现象
上一节说「一直刷到不再变为止」。凭什么它一定会停? 万一它来回震荡、永远不收敛呢?
先要一把尺子:两张价值表之间「差多远」
要说「差距在缩小」,先得能量出差距。
两张价值表,每个局面上各有一个数。怎么把「这两张表差多远」压成一个数?
书里用的是最保守的一种量法:看所有局面里差得最多的那一个7。
「把一整组数压成一个表示大小的数」,这类量法称为范数; 取最大的那一个是一种,叫无穷范数,就是这里用的。
范数还有别的取法,比如把每个数平方后加起来再开方 —— 那一种到第 05 章会再见到。
表 A: 打游戏 −5.0 · 作业一 −1.0 · 作业二 3.0 · 休息 3.5 · 通过 10.0
表 B: 打游戏 −5.8 · 作业一 −1.2 · 作业二 3.7 · 休息 3.9 · 通过 10.0
逐格之差: 0.8 0.2 0.7 0.4 0.0
▲
取里面最大的那个 0.8,就是这两张表的「距离」┘
图说:这种「取最大的那一个」的量法,就是上面说的无穷范数。
(这两张表是**为演示编的**;取无穷范数是书里证明用的量法。)
证明的核心只有一步
把两张表各刷一遍,再量一次距离,会发现:
新的距离 ≤ γ × 旧的距离。7
为什么? 因为刷一遍的时候,「这一步的分数」那一项两张表是一样的,减法之后当场消掉; 剩下的只有「0.9 × 邻居的差」—— 而邻居的差再大也不会超过旧距离。
γ = 0.9 的意思就是:每刷一遍,两张表的距离至少缩到原来的九成。
「每作用一次,距离就至少乘上一个小于 1 的数」——这种操作叫收缩映射 (映射就是「把一个东西按固定规则变成另一个东西」的意思,这里是把一张价值表变成另一张)。 而「一个收缩映射反复作用,必然把所有起点挤到同一个点上」是数学上一条现成的定理, 书里点了它的名字:巴拿赫不动点定理7。
初始距离 100 → 刷一遍 ≤ 90 → ≤ 81 → ≤ 72.9 → …… → 必然趋于 0
图说:一个每次至少乘 0.9 的正数,必然趋近于 0。
于是不管从哪张表出发,反复刷都会挤到同一张表上——那张表就是答案。
(100 → 90 → 81 这串数是**为演示编的**。)
★ 这条保证是这一章最值钱的东西,而第 06 章会告诉你:把那张表换成神经网络之后,它就没了。★
4. 蒙特卡罗:不要模型,整局跑完再算账
这一节走主走查的 ②。
先看现象
上面两节从头到尾都在用那张转移表。而真实环境里你没有。
做法:直接去跑,跑完取平均
书里的说法很干脆:蒙特卡罗方法不需要知道环境的所有信息,只需要基于过去的经验就可以学习8。 它就是第 03 章用过的那个办法:跑一批完整的片段,把经过某个局面之后实际拿到的总账平均一下。
书里还顺手交代了这个名字的来历:「蒙特卡罗」可以用来泛指那些有很大随机性的算法8。
走查 ②:还是那四条路(书里的数)
从「作业二」出发,随机走出 4 条完整的路,各自的总账:
−2 · 7 · 4.57 · −0.178
平均 = 2.348
↑ 对照第 2 节算出来的真值 3.75:**差了 1.4。**
(四个数和 2.348 是书里的;3.75 是我们算的。)
★ 第四条路那个 −0.178 是原书的一处笔误,自己算应为 −4.178;
我们沿用书里的数,好跟书里的 2.348 对得上 —— 缘由见第 03 章第 4 节的判断块。★
一个小分别:同一局里经过两次,算一次还是两次
书里给了两种口径9:
| 口径 | 做法 |
|---|---|
| 首次访问 | 一个片段里,只算第一次到达这个局面之后的那笔账 |
| 每次访问 | 每一次到达都算一笔 |
书里说两者有一些理论上的不同,但只要访问次数足够多,都会收敛到真值9。 实现上的区别只有一行:把「是不是第一次」那个判断去掉。
它的两条硬约束
第一,必须等一整局跑完。 因为「总账」要到片段结束才算得出来 —— 书里假设问题是回合制的:不论玩家做什么动作,一个回合最后都会终止8。 局面很长、或者根本没有终点的任务,这条路直接堵死。
第二,没被访问过的局面就没有任何信息。 书里说得很实在: 有些状态可能从来没被访问过,所以就没有回报;而为了选出最优策略,必须探索所有状态10。
书里给的补救办法叫探索开始:干脆把那些「不可能被选到」的局面-动作对拿来当起点, 这样跑够多的回合之后,所有组合都能被访问到10。
注意这是一个很强的假设,现实里往往做不到 —— 你没法让机器人「从任意姿势开始」。 探索这件事的正经解法,要到第 07、10 章才有。
5. 「不准」有两种:飘,和偏
这一节是本章的枢纽,而它解释了主走查里 ① 和 ② 差 1.4 的原因。
先看现象
上面那四条路的总账是 −2、7、4.57、−0.178。同一个局面,四次采样,最大和最小差了 9。
再采四条,平均值又会是另一个数。 这不是算错了 —— 这是这个办法的天性。
两种不准,必须分开
书里把这件事讲得很清楚,而且给了明确的定义11:
| 是什么 | 一句话 | |
|---|---|---|
| 偏差 | 估计值的平均,和真值之间的差 | 「量一万次取平均,仍然偏了」 |
| 方差 | 这个估计本身有多大噪声(每次量都会掺进来的那点随机偏差) | 「每次量出来的数彼此差多远」 |
打靶来说明(比喻,用完即拆):
偏差大、方差小 → 弹着点挤成一小簇,但整簇偏在靶心左上方
偏差小、方差大 → 弹着点散得满靶都是,但它们的中心正好在靶心
↑ 这个比喻只用这一次。往下一律用正式说法:
偏差 = 平均值离真值多远;方差 = 各次结果彼此差多远。
书里还给了一个对照,把这两个词接回了机器学习(让程序从数据里自己找规律,这门学问的总称)的常识。
偏差大,往往意味着欠拟合 —— 模型太笨,连给它看过的数据都学不好11。
偏差小但方差大,往往意味着过拟合 —— 模型把给它看过的数据整个背了下来,换一批就不行11。
蒙特卡罗站在哪一端
书里的判断很明确:蒙特卡罗直接估算「一个回合结束时累计的回报」—— 而这正是价值的定义本身,所以它是没有偏差的12。
但代价也直接:不同回合的经过和结果都不同,所以积累到最后的回报会有较大的方差12。
这就是主走查里那 1.4 的来源。 不是算错了,是 4 条路太少 —— 这个数是飘的,不是偏的。
那有没有办法把方差压下去?
有,而且思路很朴素:别等一整局了,只走一步就更新。
走一步的随机性,总比走一整局的随机性小。 这就是下一节。
6. 时间差分:只等一步,拿估计去更新估计
这一节走主走查的 ③,而它引入了全书最关键的一个动作。
先看现象
蒙特卡罗要等一整局。可你走一步之后,其实已经拿到新信息了:这一步的分数,和你落到了哪个局面。
能不能立刻用上?
做法:把「总账」换成「这一步 + 下一步的估计」
书里的更新式,和第 02 章那个「旧估计 + 步长 ×(新观测 − 旧估计)」是同一个形状13:
这个局面的价值 ← 这个局面的价值 + 步长 × [ 这一步的分数 + 折扣 × 下个局面的价值 − 这个局面的价值 ]
└────────── 新的目标值 ──────────┘ └── 旧估计 ──┘
└────────────── 差多少(叫时间差分误差)─────────────┘
和蒙特卡罗唯一的区别在方括号里那个目标值:
| 目标值是什么 | 什么时候能算出来 | |
|---|---|---|
| 蒙特卡罗 | 这一局实际拿到的总账 | 一个回合结束之后13 |
| 时间差分 | 这一步的分数 + 折扣 × 下个局面的当前估计 | 每一步都能算13 |
那个关键动作:自举
「拿下一个局面的估计,去更新这一个局面的估计」—— 这个动作有名字,叫自举。
书里是从反面引出它的:蒙特卡罗不使用自举,也就是说,它不用其他状态的估算来估算当前的状态值14。
自举的意思就是「用还没学准的数去更新另一个数」。 听起来像自欺欺人,但它正是让学习变快的原因 —— 也是第 06 章那个「三样凑齐会发散」里的第二样。
走查 ③:第一次更新,和第八次更新
初始:所有格子都是 0。步长 α = 0.1,折扣 0.9。
第一次更新(从作业二走一步到通过):
新目标 = (−2) + 0.9 × 通过的当前估计(此刻还是 0) = −2
作业二 ← 0 + 0.1 × (−2 − 0) = **−0.2**
▲
几乎没动,因为它借来的那个邻居值此刻还是 0 —— ** 这就是偏差** ┘
跑了一阵之后,「通过」的估计已经学到 10.0。再从作业二走一步到通过:
新目标 = (−2) + 0.9 × 10.0 = 7.0
作业二 ← −0.2 + 0.1 × (7.0 − (−0.2)) = −0.2 + 0.72 = **0.52**
再反复走下去,这个数会一路爬向 3.75(第 2 节算出来的真值)。
(**这几步是我们按书里的更新式算的**,写全了可以自己核;更新式和步长的记法是书里的。)
三种办法的正式对照(书里的)
书里把三者的区别归结到一句话上:主要区别在策略评估的过程15:
| 要环境模型吗 | 用自举吗 | 什么时候能 学 | |
|---|---|---|---|
| 动态规划 | 要 | 用 | 随时(它不采样,直接算) |
| 蒙特卡罗 | 不要 | 不用 | 一个回合结束之后 |
| 时间差分 | 不要 | 用 | 每一步 |
书里给的判断是:时间差分「在实践中往往收敛得更快」,理由是它的学习来自状态转移的信息、 不需要具体动作信息,而蒙特卡罗往往需要;而在理想情况下,两种方法最终都会收敛到同一个答案15。
代价也是明确的:自举引入偏差(目标值本身就是估出来的),但方差更小 (只依赖当前奖励和下一个状态的估计,不依赖整条路的随机性)12。
7. 它们不是两派,是同一根轴的两端
这一节把前面三节收起来。
先看现象
「等一整局」和「只等一步」听起来是两种主张。其实中 间是连续的:等两步、等三步……都行。
书里明说了这一点:可以把目标值改成「未来 N 步的折扣回报加上 N 步之后的估计」, 这就是 N 步时间差分13。
一个能连续拧的旋钮
书里给了这根轴的正式形式,叫 TD(λ),而它的两端正好是我们已经见过的两个16:
λ = 0 ──────────────────────────────── λ = 1
单步时间差分 蒙特卡罗
偏差大、方差小 偏差为零、方差大
图说:λ 是一个可以在 0 和 1 之间任意取值的数。
书里原话:「当 λ = 1 时,TD(λ) 变为蒙特卡罗法;而当 λ = 0 时,它就变成了一个单步 TD 法。」[^16]
实现这件事的机制,书里叫资格迹16。它的思路很直观:
每当某个部分被用来做了一次估计,就给它记一笔「刚用过」; 这笔记录随时间按一个固定的速度衰减。等到误差来的时候, 按每个部分「刚才被用过多少」来分配这次的修正。
换句话说:一次误差不只改当前这一步,还会按「刚才有多大功劳」回溯着改前面几步。
这里有一处要留意:书里为了讲资格迹,提前引入了一个设定 —— 价值不再是一张表, 而是一个由一组可以调的数决定的函数。 这组数有个名字,叫权重。
而书里当场点明了它是什么:「比如这组数可以是一个神经网络的权重」17 —— 那正是第 05、06 章的主题 —— 也就是说,资格迹这一节,书里已经踩进了下一章的地盘。
8. 学的是自己走的路,还是别人走的路
这一节是本章的落点,而它引入的那条分界会一直用到全书最后。
先看现象
前面几节都在「评估一个给定的策略」。要真的学出一个好策略,还要边学边改。 于是出现一个新问题:你更新用的目标值,和你实际在走的路,是不是同一个策略给的?
两个算法,差别只有一个词
Sarsa: Q(这个局面, 这个动作) ← 旧值 + 步长 × [ 分数 + 折扣 × Q(下个局面, **实际选的下个动作**) − 旧值 ]
Q-Learning: Q(这个局面, 这个动作) ← 旧值 + 步长 × [ 分数 + 折扣 × **max** Q(下个局面, 所有动作里最好的) − 旧值 ]
▲
两者唯一的差别,就在这个「取最大」┘
Sarsa 这个名字的来历很朴素: 书里说它来自这样一串行为 —— 在一个状态(S)下选了一个动作(A),观察到了回报(R),到了另一个状态(S),再选一个新动作(A)18。
这一个词造成的分野
| Sarsa | Q-Learning | |
|---|---|---|
| 目标值用的是 | 它实际会走的那个动作 | 最好的那个动作(哪怕它这次不会走) |
| 于是它在评估的是 | 它自己现在正在执行的策略 | 一个它自己没在走的、完全贪心的策略 |
| 名字 | 在线策略 | 离线策略 |
书里的定义:在线策略指的是「更新策略和行动策略相同」那一类算法;而离线策略往往不同 —— Q-Learning 在更新时假设了一种完全贪心的 方法,而它实际选动作时用的是另一种(比如 ε-贪心)18。
换句话说:Q-Learning 一边小心翼翼地带着随机去探索,一边在心里按「我要是每步都走最优」来记账。
为什么这条分界这么重要
因为「离线策略」意味着:你可以拿别人走过的路、或者自己很久以前走过的路来学。
在线策略 → 样本用完就作废,因为策略一改,旧样本就不再代表当前策略了
离线策略 → 旧样本还能接着用 → **可以把经验存起来反复用**
图说:第 07 章那条线整章建立在这一点上(存起来反复抽);
第 08 章那条线是在线策略,所以样本效率低;
而第 10 章两条线合流,合的就是这个性质。
这个「max」就是分界线的全部来源。记住它。
但它也是一个麻烦的起点
书里在这里埋了一句伏笔: 它说 Q-Learning 在深度学习应用中有很重要的作用,比如深度 Q 网络19。
而第 06 章会告诉你:这个「取最大」正是「三样凑齐会发散」里的第三样; 第 07 章会告诉你:对一堆带噪的估计取最大,结果会系统性偏高。
同一个 max,在这里是优点,到那里是病根。
作者的判断与证据
书里给了证明或数值的:
- 收缩性证明:每作用一次,两张价值表在无穷范数下的距离至少乘上折扣因子; 再引收缩映射定理(巴拿赫不动点定理)得到唯一收敛点7;
- 策略提升是单调的,且有限状态下有限步内停止5;
- 蒙特卡罗是无偏的(因为它的目标值就是价值的定义本身)、方差大; 时间差分有偏、方差小12;
- Sarsa 的收敛性有定理,书里给了条件(每个状态-动作对被访问无数次、步长满足某个条件), 但明说「我们在这里对上面定理的证明不做介绍」,并给了一篇文献20。
作者的判断(书里没给实验或证明):
判断(我们的,不是书里的): 这一章真正的成果不是三个算法, 而是一根轴 —— 一端是「等到底再算,准但飘」,另一端是「只走一步,稳但偏」。 这根轴之所以要现在就认清楚,是因为它后面会换着被估的对象反复出现: 第 08 章估的是「策略该往哪边改」,第 09 章估的是「新策略 会有多好」, 第 14 章估的是「环境会怎么动」—— 每一次,都是同一根轴上重新选一个位置。 如果错,会错在: 如果某个方法同时降低了偏差和方差(比如靠更多的真实数据、 或者靠一个真的很准的环境模型),那它就不在这根轴上,这条串联对它不适用。
边界与局限
- 这一章的三种办法全部建立在一张表上 —— 每个局面(或每个局面-动作对)一格。 表写不下的时候整章作废,而那正是第 05、06 章的起点;
- 动态规划要求你知道转移表,而书里自己说这在强化学习场景中「很难被获取」1 —— 所以它在实践中几乎不能直接用,它的价值是当原型;
- 「探索开始」在真实系统里通常做不到,书里没有讨论这一点;
- 收敛性的证明只对表格形式成立。 书里在这一章给的所有保证, 到第 06 章换成函数之后全部失效 —— 而书里在那里才说这件事;
- 资格迹这一节提前用到了下一章的设定(价值由一组数参数化),书里没有为此做铺垫。
可带走的
全章那条走查,一行写完: 同一个数(作业二的价值,γ = 0.9)三种办法各算一遍 —— 动态规划知道转移表,反复刷方程,分数一层层往回传,最后收敛到 3.75; 蒙特卡罗不用表,随机走 4 条完整的路(−2 / 7 / 4.57 / −0.178)取平均得 2.348,和真值差 1.4,这是飘; 时间差分只走一步就更新,第一次只挪到 −0.2(因为邻居此刻还是 0), 等「通过」学到 10 之后同样一步就跳到 0.52,这是偏。 (2.348 与四条路是书里的;3.75、−0.2、0.52 是我们按书里的表和更新式算的。)
- 三种办法按「知不知道环境怎么动」分:动态规划要模型,另外两个不要;
- 动态规划 = 把贝尔曼方程从等号改成赋值,反复刷。 它在实践中几乎用不上,但它是后面所有算法的原型;
- 「评估 → 改进 → 再评估」这个来回,是全书每个算法的骨架;
- 分数是一层层往回传的 —— 这是理解「学习为什么慢」的第一张画面;
- 收缩性:每刷一遍,两张价值表的距离至少乘上折扣因子 —— 所以必然收敛到唯一答案。 第 06 章会把这条保证收走;
- 量两张表的距离,用的是「所有格子里差得最多的那一个」(无穷范数);
- 蒙特卡罗一个模型都不要,代价是必须等整局结束,而且没访问过的局面完全没信息;
- 偏差 = 平均下来仍然偏了;方差 = 每次结果彼此差很远。 两个词不能混;
- 蒙特卡罗无偏但方差大;时间差分有偏但方差小。 这是同一根轴的两端,中间连续可调;
- 自举 = 拿一个还没学准的数 去更新另一个数。 它让学习变快,也是后面发散的病根之一;
- Sarsa 和 Q-Learning 的唯一区别是一个 max,而这个 max 划出了在线策略与离线策略的分界;
- 离线策略意味着旧经验还能用 —— 第 07 章整章、第 10 章的合流,都建立在这一句上。
原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 动态规划的定位与局限 | 第2章 强化学习入门 | text/06-ch02.txt:843(搜「很难被获取」) · text/06-ch02.txt:844(搜「被大多数强化学习算法所沿用」) |
| 「动态规划」这个名字、斐波那契 | 第2章 强化学习入门 | text/06-ch02.txt:833(搜「动态」) · text/06-ch02.txt:839(搜「斐波那契」) |
| 两个前提条件 | 第2章 强化学习入门 | text/06-ch02.txt:845(搜「最优子结构」) · text/06-ch02.txt:847(搜「重叠子问题是指」) |
| 策略评估、策略提升、泛化策略迭代 | 第2章 强化学习入门 | text/06-ch02.txt:874(搜「策略评估」) · text/06-ch02.txt:877(搜「泛化策略迭代」) |
| 策略提升单调、有限步停止 | 第2章 强化学习入门 | text/06-ch02.txt:906(搜「策略提升是单调的」) |
| 价值迭代与最优性原则 | 第2章 强化学习入门 | text/06-ch02.txt:937(搜「最优性原则」) · text/06-ch02.txt:947(搜「从最终状态开始」) |
| 收缩证明与无穷范数 | 第2章 强化学习入门 | text/06-ch02.txt:887(搜「收缩」) · text/06-ch02.txt:902(搜「巴拿赫不动点」) · text/06-ch02.txt:905(搜「唯一的固定点」) |
| 蒙特卡罗不需要模型、名字的含义 | 第2章 强化学习入门 | text/06-ch02.txt:1062(搜「不需要知道环境的所有信息」) · text/06-ch02.txt:1065(搜「很大随机性的算法」) · text/06-ch02.txt:1072(搜「回合制」) |
| 首次访问与每次访问 | 第2章 强化学习入门 | text/06-ch02.txt:1082(搜「首次蒙特」) · text/06-ch02.txt:1086(搜「无限次访问」) |
| 不用自举 → 偏差小方差大 | 第2章 强化学习入门 | text/06-ch02.txt:1087(搜「不使用」) · text/06-ch02.txt:1090(搜「更小的偏差」) |
| 探索开始 | 第2章 强化学习入门 | text/06-ch02.txt:1099(搜「须要探索所有的状态」) · text/06-ch02.txt:1101(搜「探索开始」) |
| 时间差分的更新式、N 步 TD | 第2章 强化学习入门 | text/06-ch02.txt:1216(搜「自举」) · text/06-ch02.txt:1221(搜「单步」) · text/06-ch02.txt:1223(搜「只有在一个回合过后才能得知」) |
| 三种方法的异同 | 第2章 强化学习入门 | text/06-ch02.txt:1243(搜「策略评估的过程」) · text/06-ch02.txt:1257(搜「收敛得更快」) |
| 偏差与方差的定义、欠拟合与过拟合 | 第2章 强化学习入门 | text/06-ch02.txt:1262(搜「欠拟合」) · text/06-ch02.txt:1264(搜「过拟合」) · text/06-ch02.txt:1267(搜「估计值 和真正值间的差异」) |
| 谁无偏、谁方差大 | 第2章 强化学习入门 | text/06-ch02.txt:1276(搜「没有偏差」) · text/06-ch02.txt:1279(搜「方差更小」) |
| 资格迹与 TD(λ) 的两端 | 第2章 强化学习入门 | text/06-ch02.txt:1294(搜「资格迹是一个向量」) · text/06-ch02.txt:1302(搜「变为蒙」) |
| 资格迹提前用到了函数近似 | 第2章 强化学习入门 | text/06-ch02.txt:1286(搜「一个神经网络的权重」) |
| Sarsa 与在线策略的定义 | 第2章 强化学习入门 | text/06-ch02.txt:1358(搜「首字母缩写」) · text/06-ch02.txt:2406(搜「行为策略」) |
| Q-Learning 与离线策略 | 第2章 强化学习入门 | text/06-ch02.txt:14(搜「深度 Q 网络」) · text/06-ch02.txt:1461(搜「不再依赖于所使用的策略」) |
| Sarsa 收敛定理的条件与省略的证明 | 第2章 强化学习入门 | text/06-ch02.txt:1457(搜「证明不做介绍」) |