把决策写成数学 — 马尔可夫决策过程与贝尔曼方程
这一章讲三件事: 一个决策问题写成数学之后长什么样; 「从这里出发以后还能拿多少」这个量怎么定义; 以及一个递归关系怎么把它从「跑到底才知道」变成一组能解的方程。
它在全书链条里的位置:地基。 第 01 章拆了零件,第 02 章解了「只有一步」的情形, 这一章把零件装成一台能推导的机器。后面十七章的每一个算法,都是在解这一章列出的那个方程。 这一章到「直接解它要多贵」为止;怎么解,是第 04 章 。
顶层全景:一张「学生的一天」的图,贯穿全章
书里从 2.3 节起用同一张图讲完整个马尔可夫决策过程,我们也用它,一次都不换。
图上是一个学生的一天:他可能在打游戏、做作业一、做作业二、休息、通过考试、上床睡觉。 每个圆圈是一个局面,每根箭头是「从这里会去哪里」,箭头上的数是这件事发生的机会。
0.9 ┌──┐
└→ 打游戏 ──0.1──→ 作业一 ──0.7──→ 作业二 ──0.6──→ 通过 ──1.0──→ 睡觉
↑ │ │ │ ↑
└─────0.3───────┘ 0.1 └─────────0.3──────────────┘
↓
休息 ←─────────────┘
├──0.9──→ 作业二(回到上面那个圈)
└──0.1──→ 作业一(回到上面那个圈)
每个圈上还挂着一个分数(这一步立刻拿到多少):
打游戏 −1 · 作业一 −2 · 作业二 −2 · 休息 +1 · 通过 +10 · 睡觉 0
图说:全章的主走查就跑在这张图上。
第 3 节算「打游戏 → 作业一 → 作业二 → 通过 → 睡觉」这条路总共值多少(答案 5,打折后 2.87);
第 4 节算「站在作业二这个圈上,以后还能拿多少」(答案 2.348);
第 5 节给它加上动作(在作业二选「休息」,0.8 留在原地、0.2 退回作业一);
第 7、8 节用它解释贝 尔曼方程在干什么。
**这些数全部是书里图 2.4 与图 2.6 给的,不是我们编的。**[^1]
1. 第一步:把「接下来会怎样」压成一张表
这一节回答:第 01 章那堆零件,怎么变成一个能算的东西?
先看现象
第 01 章的乒乓球里,「下一帧长什么样」取决于什么?取决于这一帧的画面、和你按了什么键。 可你要真去写下这件事,得写多少?画面有多少种,就要写多少条。
书里的第一步是把这件事压成一个能摆在纸上的东西:一张表。
表的每一行是一个当前局面,每一列是一个下一个局面,格子里填的是这件事发生的机会。 这张表书里叫状态转移矩阵(矩阵就是这样一张按行按列排好的数表)1。
用主走查那张图:
从\到 打游戏 作业一 作业二 休息 通过 睡觉
打游戏 0.9 0.1 0 0 0 0
作业一 0.3 0 0.7 0 0 0
作业二 0 0 0 0.1 0.6 0.3
休息 0 0.1 0.9 0 0 0
通过 0 0 0 0 0 1.0
睡觉 0 0 0 0 0 1.0
图说:每一行加起来必然是 1(总得去个地方)。
第一行的意思是:正在打游戏的人,有九成机会继续打,只有一成会去做作业一。
休息那一行值得单独看一眼:歇完之后九成回去做作业二、一成回去做作业一,
**一次都不会回到打游戏** —— 这一行后面第 4 节要用来算数。
睡觉那一行只指向自己,意思是「到这儿就结 束了,再也出不去」。
**这些数是书里图 2.4 的转移矩阵给的。**
只要有了这张表,「接下来会怎样」就完全确定了 —— 不是确定到某一个结果,而是确定到「每种结果各有多大机会」。
书里给这种东西的名字是马尔可夫过程2。它只有两样东西:所有局面的清单,和这张表。
一个后面到处默认、但很少有人点破的前提
书里在这里插了一句,而且明说了它是全书大多数推导的基础:这张表不随时间变3。
「早上八点从打游戏跳到作业一的机会」和「晚上八点」是同一个数。 这个性质书里叫时间同质性,并说:「时间同质性是对本书中大多数推导的一个基本假设, 我们在后续绝大多数情况中默认满足这一假设而不再提及」3。
但它也当场给了失效的场合:非稳定的环境、以及多智能体的情形。 后者到第 16 章会变成整章的主题 —— 对手自己在学,他的表天天在变。
2. 那条很强的假设:只看当前这一眼就够了
这一节讲那张表能成立的前提,以及一句到第 20 章会变成排错判据的话。
先看现象
上面那张表的每一行只写了「当前在哪个圈」。它完全没问「你是怎么走到这个圈的」。
凭什么?一个连打了三小时游戏的人,和一个刚打开游戏的人,下一步的机会真的一样吗?
这不是发现,是假设
书里把这件事写成一个等式,意思是:给定当前局面之后,下一个局面的机会, 和「之前经过了哪些局面」完全无关4。这个性质叫马尔可夫性, 书里给这个性质的另一个说法是无记忆:它不记得自己是怎么走到这里的4。
这条假设很强,强到第一眼看上去是错的。
关键的一句:它是状态定义的性质,不是环境的性质
如果「打了多久」真的会影响下一步,那么正确的做法不是放弃这套数学, 而是把「打了多久」也塞进局面的定义里。
局面定义得够全,马尔可夫性就成立;定义得不全,它就不成立。
换句话说:马尔可夫性是你怎么定义「局面」的性质,不是环境自带的性质。
这句话看起来像哲学,其实是一条极实用的排错判据。 第 01 章那个「单帧画面看不出球速」的例子,正是局面定义得不全; 补救是把最近四帧叠起来当一个局面 —— 叠完之后,马尔可夫性就近似成立了。
第 20 章会拿这一条去分辨两种长得很像的失败 —— 「局面定义得不全」和「环境本身就藏了信息不给你看」是两回事,而它们的解法不同。
3. 加上分数:一条路总共值多少
这一节回答:走完一条路,该怎么给它算总账?
先看现象
主走查那张图上,每个圈挂着一个分数:打游戏 −1、做作业 −2、休息 +1、通过考试 +10、睡觉 05。 把马尔可夫过程加上这些分数,书里叫马尔可夫奖励过程6。
现在走一条路:打游戏 → 作业一 → 作业二 → 通过 → 睡觉。 总账是多少?
最直接的算法:全加起来
−1 + (−2) + (−2) + 10 + 0 = 5
图说:一条路上所有分数的和,书里叫这条路的回报。
**这个 5 是书里给的。**[^8]
「回报」这个词从这里开始一直用到全书最后一章:它指的永远是「一整段路的总账」, 不是某一步拿到的那个数。 某一步拿到的那个,第 01 章已经叫过名字,叫立即奖励。
但直接加会出事
如果这条路没有尽头呢? 一个可以一直循环下去的过程,把所有分数加起来会得到无穷大 —— 而两个无穷大之间没法比大小,整套数学当场作废。
补救:越远的分数,越不值钱
书里的做法是给每一步的分数乘一个越来越小的系数:第 0 步乘 1,第 1 步乘 γ,第 2 步乘 γ²,依此类推。 这个 γ 叫折扣因子,取值在 0 到 1 之间7。
同一条路,取 γ = 0.9 再算一遍:
−1 ×1 + (−2)×0.9 + (−2)×0.81 + 10×0.729 + 0
= −1 + (−1.8) + (−1.62) + 7.29
= 2.87
↑ 对照上面不打折的 5:同一条路,同样的分数,只因为「越远越不值钱」,总账从 5 掉到 2.87。
**这两个数都是书里给的。**[^8][^9]
折扣因子的两端,书里也点了7:
| γ 的值 | 意味着什么 |
|---|---|
| γ = 0 | 只看眼前这一步的分数,智能体会非常「短视」 |
| γ = 1 | 完全不打折,就是上面那个 5 |
| 0 < γ < 1 | 中间。而且无限长的过程只有在这一档才算得出有限的总账 |
所以折扣因子不是一个调味料,它是让无限长的问题「有意义」的那个东西。 到第 20 章你会看到它还有一个很实用的读法:γ = 0.99 大约就是「一百步以后的事可以不管了」。
书里还给了另一种理解,值得留着: 折扣因子可以被理解为并进了转移过程本身 —— 把「每一步有 1 − γ 的机会直接掉进一个结束状态」写进那张表里,效果和打折是一样的8。 换句话说,「打折」和「随时可能结束」在数学上是同一件事。
4. 全书最重要的那个量:从这里出发,以后还能拿多少
这一节定义整本书都在估的那个数。
先看现象
上一节算的是「这一条路值多少」。可你站在「作业二」这个圈上的时候,你不知道会走哪一条。 从作业二出发,有 0.6 的机会去通过、0.3 的机会直接去睡觉、0.1 的机会去休息 —— 三条路的总账天差地别。
那「站在作业二」到底值多少?
定义:把所有可能的路按机会加权平均
答案是:所有可能走法的总账,按各自发生的机会加权平均。 第 02 章已经给这件事起过名字 —— 这就是期望。
书里把这个量叫价值函数:一个局面的价值,就是以它为起点的回报的期望9。
这是全书最重要的一个量。 后面十七章里,几乎每一个算法都在做同一件事: 把这个数估得准一点,或者绕过它。
最土的算法:随机走几条路,取平均
书里在这里给了一个非常土、但完全可用的办法:用那张转移表随机采样出一批路,把它们的总账平均一下。 这个办法叫蒙特卡罗法(名字来自赌城,意思就是「靠大量随机试验去逼近一个数」)10。
走查:估「作业二」的价值(全是书里的数)
书里为了讲清方法只采了 4 条路,并特意说明实际中要采的路远多于 4 条10:
从「作业二」出发,随机走出 4 条路(γ = 0.9):
① 作业二 → 睡觉 总账 = −2 + 0×0.9 = −2
② 作业二 → 通过 → 睡觉 总账 = −2 + 10×0.9 + 0×0.81 = 7
③ 作业二 → 休息 → 作业二 → 通过 → 睡觉
总账 = −2 + 1×0.9 − 2×0.81 + 10×0.729 + 0 = 4.57
④ 作业二 → 休息 → 作业一 → 作业二 → 睡觉
总账 = −2 + 1×0.9 − 2×0.81 − 2×0.729 + 0 = −0.178
★ 这一行你自己算会得到 −4.178,不是 −0.178 ★
—— 那是原书的一处笔误,见下面的判断块
平均:(−2 + 7 + 4.57 − 0.178) / 4 = 2.348 ← 这就是「作业二」这个局面的价值估计
**这五个数(−2、7、4.57、−0.178、2.348)全部是书里给的。**[^12]
判断(我们的,不是书里的): ④ 那一行的算式和答案对不上。 按上一节刚讲完的折扣算法一步步算:−2 + 0.9 − 1.62 − 1.458 = −4.178, 而书里印的是 −0.178 —— 它把 −4.178 印成了 −0.178。 我们仍然沿用书里的 −0.178 和 2.348,理由是:书里的平均值 2.348 就是照 −0.178 算出来的, 而第 04 章要拿这个 2.348 跟另外两种算法的结果并排比。换成 −4.178,平均会变成 1.348, 后面全套对照都得跟着改,反而对不上原书。 如果错,会错在: 也可能不是书写错,而是清洗转码时把那个 4 弄丢了。 判据是:书里印的 2.348 —— 只有配 −0.178 才算得出这个平均值, 所以这两个数在书上是一套的,错也是一起错的。
看那四个数彼此差多远:−2 和 7 之间差了 9。 而它们是同一个局面的四次采样。 这就是第 02 章说过的方差 —— 同一件事量多次,结果彼此差很远。 第 04 章会拿这个现象做整整一节的文章:它正是「整局跑完再算账」这条路的天生代价。
有了价值,就有了一个最朴素的策略
书里顺手给了一个用法:每一步都往价值更高的那个局面走11。 这已经是一个能用的策略了 —— 但注意,到这里为止,图上还没有「动作」这个东西。
5. 加上动作,它才成为一个决策过程
这一节补上最后一个零件,而这个零件改变了图的形状。
先看现象
上面那张图里,你没有任何选择。站在「作业二」上,去哪儿完全由转移表决定,你说了不算。
可决策问题的全部意义就在于你能选。
加上动作之后,两处发生了变化
书里把加上动作之后的东西叫马尔可夫决策过程,并点明 了和奖励过程的两处不同12:
| 马尔可夫奖励过程 | 马尔可夫决策过程 | |
|---|---|---|
| 分数挂在哪 | 挂在圈上(到了这个局面就给这么多) | 挂在箭头上(在这个局面做这个动作才给这么多) |
| 「接下来会怎样」由什么决定 | 只由当前局面决定 | 由当前局面和你选的动作一起决定 |
「分数从圈上搬到箭头上」这个说法要记住 —— 它是这两个东西唯一的形状差别。
但同一个动作的结果,仍然可能是随机的
这一点最容易被误解:能选动作,不等于结果就定了。
书里给的例子正好在主走查这张图上:智能体在「作业二」上执行「休息」这个动作之后, 有 0.8 的机会留在作业二,有 0.2 的机会变成作业一13。
在「作业二」选动作「休息」:
├─ 0.8 的机会 → 还在「作业二」
└─ 0.2 的机会 → 退回「作业一」
而在「作业一」选动作「工作」:
└─ 1.0 的机会 → 到「作业二」 ← 这一条是确定的
图说:同一张图上,有的箭头是定死的,有的是抽签的。
**这几个数是书里给的。**[^15]
这就是第 01 章那个「确定性转移 / 随机性转移」的分别,现在落到了具体的图上。
6. 策略:从局面到动作的一张概率表
这一节定义你唯一能改的那个东西。
它是什么
书里的定义很干脆:策略是从每个局面到「各个动作的机会」的一张对应表14。
注意它给出的不是一个动作,是一组机会。 在「作业二」上,策略可能说: 「工作 0.7 的机会、休息 0.3 的机会」。这种策略叫随机性策略。15
确定性策略只是它的一个极限
书里说得很准:把随机性策略的方差一直缩小、缩到极限,就得到了确定性策略 —— 给定一个局面,输出唯一一个动作15。
书里还点了一处后面会绊人的地方:确定性策略不再是「局面 → 各动作的机会」的对应, 而是「局面 → 动作」的直接对应。这个差别会导致第 08 章那类直接调策略的方法推导不同15 —— 那类方法的名字里带一个梯度(意思是「往哪边挪一丁点会变好」,第 05 章会从现象讲起)。 第 08 、10 章会正面撞上这件事。
一个必须现在划清的界:两个「确定性」
第 01 章讲过一个「确定性」,这一节又出现一个。它们不是一回事:
| 说法 | 说的是谁 | 意思 |
|---|---|---|
| 确定性转移 | 环境 | 在这个局面做这个动作,下一个局面是唯一的 |
| 确定性策略 | 你的程序 | 在这个局面,你永远输出同一个动作 |
两者可以任意组合。 你可以在一个抽签的环境里用一个死板的策略,反过来也可以。 第 10 章整章讲的就是「确定性策略」那一支,那时这个区分必须是清楚的。
随机性不是缺点,有时是必需品
第 02 章那条结论在这里接上了:面对会针对你的对手,确定性的策略必输, 因为对方可以提前推演你的下一手。所以策略输出「一组机会」而不是「一个动作」, 是一个能力,不是一个妥协。 第 16 章会把这件事算成具体的数。
目标:让「所有可能的路的总账的期望」最大
有了策略,一整条路发生的机会就能写出来了:起点的机会 × 每一步「策略选了这个动作」的机会 × 每一步「环境跳到这个局面」的机会,一路乘下去16。
于是整件事的目标终于有了一个准确的说法:在所有策略里,挑出那个让「所有可能的路的总账的期望」最大的17。 书里管这个最好的策略叫最优策略。
这就是强化学习这门学问要解的那个问题的全部内容。剩下的十七章都在解它。
顺带一个记号上的分工:两个价值
书里在这里引入了第二个价值,和第 4 节那个配套使用18:
| 记号 | 问的是什么 | 在主走查图上 |
|---|---|---|
| 状态价值 | 「站在这个局面上,以后还能拿多少」 | 站在「作业二」这个圈上值多少 |
| 动作价值 | 「站在这个局面上、先做这个动作,以后还能拿多少」 | 在「作业二」上选「休息」这条箭头值多少 |
两者的关系书里给了一句话:状态价值 = 各个动作的动作价值,按策略给它们的机会加权平均18。
这两个量在后面会分家:第 07 章那条线全程只估动作价值,第 08 章那条线两个都要用。
还有一处名字要现在说清: 书里把「按某个特定策略估出来的价值」叫在线价值函数, 用来和「按最优策略估出来的」区分19。注意这个「在线」和第 04 章那个「在线策略 / 离线策略」不是一回事 —— 书里自己也当场提醒了这一点20。
7. 贝尔曼方程:把「跑到底」换成「只看一步」
这一节是全章的转折点,也是整本书的地基。
先看现象:第 4 节那个办法太贵
第 4 节估「作业二」的价值,靠的是随机走四条路。可要估得准,四条远远不够。 更糟的是:每一个局面都要这么来一遍。
书里把两种笨办法都点了名:一种是穷举所有可能的路,一种就是采样平均; 并说穷举法在实践中不可行,因为可能的轨迹数量非常大,甚至是无穷个的21。
关键的观察:一条路可以拆成「第一步 + 剩下的」
这是整件事的枢纽,而它朴素得像废话:
从「作业二」出发的总账
= 作业二这一 步拿到的分数
+ γ × (从下一个局面出发的总账)
而「从下一个局面出发的总账」的期望,正是下一个局面的价值。
图说:左边是我们要算的东西,右边又出现了同一种东西——只是换了个局面。
于是价值函数满足一条关于自己的等式:一个局面的价值 = 这一步的分数 + γ × 下一个局面的价值(取期望)。 这就是贝尔曼方程。22
它为什么值钱? 因为它把一个「要跑到天荒地老才知道」的量, 变成了「只看一步,加上邻居的同一个量」。从此不必再跑完整条路。
走查:在主走查图上看它一眼
作业二的价值 = (−2) + 0.9 × [ 0.6 × 通过的价值
+ 0.3 × 睡觉的价值
+ 0.1 × 休息的价值 ]
▲ ▲ ▲
这一步的分数 ┘ 折扣 ┘ 按转移表给的机会加权 ┘
图说:右边三个未知数,又各自满足一条同样形状的等式。
六个局面就是六条方程、六个未知数 —— **它从「模拟」变成了「解方程」。**
(转移的机会与分数都是书里的;这一步的展开是我们按书里的方程写出来的。)
那就直接解这组方程?可以,而且很贵
书里给了直接解法:把那组方程写成矩阵形式,一次求逆就得到全部答案 —— 这叫逆矩阵方法23。
但书里同时给了它的代价。 一件事要做多少次基本运算才算得完,这个量就叫复杂度; 而这个解法的复杂度是状态数的三次方23。
6 个局面 → 6³ = 216 次基本运算,一眨眼
1 万个局面 → 1 万³ = 10¹² 次,一台机器要跑很久
围棋的 10^170 个局面 → 连写下这张表都做不到
图说:三次方的意思是「局面数翻十倍,代价翻一千倍」。
**这就是后面所有近似方法存在的全部理由。**
(6³ 与 1 万³ 是我们算的;三次方这个复杂度是书里给的。)
书里自己接着说:幸运的是有一些迭代方法可以在实践 中解决大规模问题, 比如动态规划、蒙特卡罗估计和时间差分学习法23。那三个名字,就是第 04 章的三节。
8. 贝尔曼最优方程:把「长期最优」换成「每一步取最大」
这一节是这一章的落点。
先看现象
第 6 节说「在所有策略里挑最好的那个」。可策略有多少种? 六个局面、每个局面三个动作,光是确定性策略就有 3⁶ = 729 种; 而随机性策略是连续的,有无穷多种。「在所有策略里挑」根本不是一个能执行的指令。
定义最优价值:所有策略里最好的那个
书里先定义了最优价值函数:在所有策略里,让这个局面的价值最大的那个值24。 注意这是一个定义,不是一个算法 —— 它没告诉你怎么找。
然后把贝尔曼方程套上去,魔术就发生了
把上一节那条递归关系用在最优价值上,「取期望」那一步就变成了「取最大」:
一个局面的最优价值
= 在这个局面所有能做的动作里,挑出使
「这个动作的分数 + γ × 下一个局面的最优价值」最大的那一个
图说:这就是贝尔曼最优方程。
★ 注意右边不再有「策略」两个字。★
这才是这一节真正的成果:
原本要在「所有策略」这个无穷大的集合里挑一个; 现在只要在「每个局面上的几个动作」里各挑一个最大的。
一个全局的、跨越整条路的最优化问题,被换成了一堆局部的、每步一次的取最大。
书里给了两个版本:一个是对状态价值的,一个是对动作价值的; 后者的推导原文留给读者练习25。
但它仍然不能直接解 —— 这就是全书剩下十七章的起点
贝尔曼最优方程比上一节那条难解,因为它里面有个「取最大」,不再是一组线性方程。 而且它和上一节共享同一个前提:你得知道那张转移表。
┌──────────────────────────────────────────────────────────┐
│ 贝尔曼最优方程给出了「答案长什么样」 │
│ ↓ 但直接解它,要么太贵(状态数的三次方) │
│ ↓ 要么根本不可能(你没有那张转移表) │
│ 于是后面十七章全部是「怎么近似地解它」 │
└──────────────────────────────────────────────────────────┘
最后补一个名字:局面看不全的时候
第 01 章讲过「看到的不等于真实局面」。书里在这里给了它一个正式的名字: 当环境的状态无法由观测完全表示时,这个决策过程叫部分可观测马尔可夫决策过程26。 书里的评价是:这构成了一个「利用不完整环境状态信息来改进策略」的挑战26。
它和第 2 节那条「马 尔可夫性是状态定义的性质」长得很像,但不是一回事 —— 第 20 章会把这两者掰开讲。
作者的判断与证据
书里给了推导或数值的:
- 贝尔曼方程与贝尔曼最优方程的完整推导,书里逐行给了(状态价值版和动作价值版都有, 后者的最优形式留给读者练习)2225;
- 逆矩阵解法的复杂度是状态数的三次方23;
- 主走查上的全部数字(转移的机会、每个圈的分数、回报 5 与 2.87、四条路的 −2 / 7 / 4.57 / −0.178、 平均 2.348、以及「休息」动作的 0.8 / 0.2)都是书里给的272871013。
作者的假设或未加论证的部分:
- 时间同质性是书里自己声明的「基本假设」,并且明说后面默认成立而不再提及3 —— 这是一个假设,不是一个结论,而书里也当场给了它失效的两种场合;
- 马尔可夫性同样是假设。书里没有讨论「假如它不成立会怎样」—— 那要到第 20 章才以工程忠告的形式出现;
- 书里只用 4 条路来估价值,并且自己注明「实际中采样的轨迹要远大于 4」10 —— 这是教学简化,不是方法主张。
判断(我们的,不是书里的): 这一章真正的成果只有一句话: 「把跨越整条路的最优化,换成每一步的取最大」。 三个概念(马尔可夫性、折扣、价值)全都是为这一句服务的 —— 马尔可夫性让「只看一步」合法,折扣让无限长的账算得出来,价值给出被拆的那个量。 读这一章如果只记一句,记这一句。 如果错,会错在: 如果某条技术路线根本不经过价值函数 (比如把整件事当成「续写一段记录」来做,见总纲第 4 节), 那么这一章的地基对它不适用 —— 而那正是这本书没有覆盖的一支。
边界与局限
- 这一章的一切都建立在「你知道那张转移表」上。 而真实环境里你不知道 —— 这个缺口就是第 04 章存在的全部理由,书里也在本节末尾明说了23;
- 书里的推导略过了不少步骤。 比如贝尔曼最优方程里「取最大和取期望能交换」这一步, 原文直接写下来了,没有论证。要严格的证明得去看更正统的教材;
- 状态怎么定义,书里一个字没讲。 而这恰恰是真实项目里最花力气的一件事 —— 它被推到了第 18 章,用两个具体项目来回答;
- 部分可观测的情形只给了一个名字和一句评价。 全书对它没有系统处理。
可带走的
全章那条走查,一行写完: 一张学生的一天的图 → 把「接下来会怎样」写成一张转移表 → 走「打游戏→作业一→作业二→通过→睡觉」这条路, 不打折的总账是 5、按 0.9 打折是 2.87 → 从「作业二」出发随机走四条路,总账分别是 −2 / 7 / 4.57 / −0.178,平均 2.348 就是它的价值 → 给图加上动作(在作业二选「休息」, 0.8 留下、0.2 退回作业一)→ 贝尔曼方程说「作业二的价值 = −2 + 0.9 ×(按机会加权的邻居价值)」→ 六个局面就是六条方程 → 直接解要状态数的三次方,于是必须近似。 (这些数全部是书里的。)
- 马尔可夫过程 = 一份局面清单 + 一张「从哪儿到哪儿各有多大机会」的表;
- 马尔可夫性是你怎么定义局面的性质,不是环境自带的 —— 这是第 20 章一条排错判据的来源;
- 时间同质性是全书默认的假设,而它在非稳定环境和多智能体里会失效;
- 回报 = 一整段路的总账;立即奖励 = 某一步拿到的那个数。 两个词不能混;
- 折扣因子不是调味料,它是让无限长的问题算得出有限总账的那个东西; 而且「打折」和「随时可能结束」在数学上是同一件事;
- 价值 = 从这个局面出发,以后总共还能拿多少的期望。 这是全书最重要的量;
- 同一个局面采四次得到 −2 / 7 / 4.57 / −0.178 —— 这就是方差,第 04 章会拿它做文章;
- 奖励过程和决策过程唯一的形状差别:分数是挂在圈上,还是挂在箭头上;
- 能选动作 ≠ 结果确定。「确定性转移」说的是环境,「确定性策略」说的是你的程序;
- 策略给出的是一组机会,不是一个动作 —— 而在有对手时这是必需品,不是妥协;
- 贝尔曼方程 = 把「跑到底才知道」换成「这一步 + 折扣 × 邻居」,一个递归就让它变成一组方程;
- 贝尔曼最优方程真正的成果:把「在所有策略里挑一个」换成「在每个局面的几个动作里各取最大」;
- 直接解要状态数的三次方,而且要求你知道转移表 —— 两个条件都不成立,所以有了后面十七章。
原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 学生生活图、转移的机会 | 第2章 强化学习入门 | text/06-ch02.txt:351(搜「Task2」) · text/06-ch02.txt:409(搜「对应的」) |
| 马尔可夫过程的定义 | 第2章 强化学习入门 | text/06-ch02.txt:346(搜「离散随」) · text/06-ch02.txt:364(搜「只取决于当前状态」) |
| 马尔可夫性、无记忆 | 第2章 强化学习入门 | text/06-ch02.txt:392(搜「无记忆」) · text/06-ch02.txt:393(搜「马尔可夫性质」) |
| 时间同质性与它的失效场合 | 第2章 强化学习入门 | text/06-ch02.txt:395(搜「稳定转移函数」) · text/06-ch02.txt:404(搜「基本假设」) · text/06-ch02.txt:406(搜「多智能体强化学习」) |
| 状态转移矩阵 | 第2章 强化学习入门 | text/06-ch02.txt:408(搜「状态转移矩阵」) |
| 奖励过程、奖励挂在状态上 | 第2章 强化学习入门 | text/06-ch02.txt:446(搜「马尔可夫奖励过程」) · text/06-ch02.txt:486(搜「休息」) |
| 回报、非折扣回报 5 | 第2章 强化学习入门 | text/06-ch02.txt:488(搜「累积奖励」) · text/06-ch02.txt:497(搜「非折扣化的回报是」) |
| 折扣回报 2.87、γ 的两端 | 第2章 强化学习入门 | text/06-ch02.txt:511(搜「2.87」) · text/06-ch02.txt:513(搜「短视」) · text/06-ch02.txt:514(搜「增大到无穷」) |
| 折扣因子的另一种理解 | 第2章 强化学习入门 | text/06-ch02.txt:518(搜「吸收状态」) |
| 价值函数的定义 | 第2章 强化学习入门 | text/06-ch02.txt:520(搜「期望回报」) · text/06-ch02.txt:527(搜「以它为初始状态」) |
| 蒙特卡罗估计、四条轨迹与 2.348 | 第2章 强化学习入门 | text/06-ch02.txt:531(搜「只采样 4 个轨迹」) · text/06-ch02.txt:534(搜「4.57」) · text/06-ch02.txt:537(搜「2.348」) |
| 往价值更高的状态走 | 第2章 强化学习入门 | text/06-ch02.txt:539(搜「最大化期望回报」) |
| 决策过程、奖励搬到边上 | 第2章 强化学习入门 | text/06-ch02.txt:552(搜「奖励值在节点上」) · text/06-ch02.txt:553(搜「奖励值在边上」) |
| 休息动作的 0.8 / 0.2 | 第2章 强化学习入门 | text/06-ch02.txt:555(搜「0.8 的概率保留」) · text/06-ch02.txt:589(搜「保持原来的状态」) |
| 策略的定义 | 第2章 强化学习入门 | text/06-ch02.txt:596(搜「策略」) · text/06-ch02.txt:597(搜「动作概率分布」) |
| 轨迹发生的概率、期望回报、最优策略 | 第2章 强化学习入门 | text/06-ch02.txt:603(搜「优化策略」) · text/06-ch02.txt:617(搜「最优策略」) |
| 动作价值、与状态价值的关系 | 第2章 强化学习入门 | text/06-ch02.txt:637(搜「动作价值函数」) · text/06-ch02.txt:652(搜「之间有如 下关系」) |
| 在线价值函数与最优价值函数之别 | 第2章 强化学习入门 | text/06-ch02.txt:649(搜「在线价值函数」) · text/06-ch02.txt:670(搜「与之后」) |
| 穷举与采样两种笨办法 | 第2章 强化学习入门 | text/06-ch02.txt:657(搜「穷举法」) · text/06-ch02.txt:661(搜「甚至是无穷个的」) |
| 贝尔曼方程的推导 | 第2章 强化学习入门 | text/06-ch02.txt:675(搜「递归关系」) · text/06-ch02.txt:8(搜「贝尔曼方程」) |
| 逆矩阵方法与三次方复杂度 | 第2章 强化学习入门 | text/06-ch02.txt:541(搜「逆矩阵方法」) · text/06-ch02.txt:723(搜「求解的复杂度」) · text/06-ch02.txt:725(搜「动态规划」) |
| 最优价值函数的定义 | 第2章 强化学习入门 | text/06-ch02.txt:732(搜「最优价值函数」) |
| 贝尔曼最优方程 | 第2章 强化学习入门 | text/06-ch02.txt:768(搜「贝尔曼最优方程」) · text/06-ch02.txt:801(搜「读者可以练习」) |
| 确定性策略与随机性策略 | 第2章 强化学习入门 | text/06-ch02.txt:806(搜「随机性策略」) · text/06-ch02.txt:812(搜「缩窄到极限」) · text/06-ch02.txt:819(搜「策略梯度方法中的一些」) |
| 部分可观测马尔可夫决策过程 | 第2章 强化学习入门 | text/06-ch02.txt:826(搜「部分可观测的马尔可夫决策过程」) · text/06-ch02.txt:827(搜「不完整环境状态信息」) |