值函数 V 与最优值函数 V⋆
这一课不推公式。我们只做一件事：把一个具体的数 一遍一遍刷出来，看着它一步步逼近真正的 。看完再回去看后面的推导，那些符号才有具体的数对应。
先说清楚一件事：为什么整本讲义从「值函数」开始，而不是从某个算法、也不是从 MDP 的定义开始。
强化学习最后要的是策略——在每个状态该走哪一步。那为什么不直接讲策略？因为「该怎么走」这个问题没法直接回答：你要挑一个动作，就得比较几个动作；要比较，就得知道「走过去之后处境有多好」。这个「有多好」，就是值。值没定下来，「更好的动作」这句话根本没有意义。
一条路好不好，本来取决于往后所有步。值函数把这一整条未来折算成一个数，写在格子里。有了它，选动作就从「想清楚整盘棋」退化成「看一眼邻居谁的数大」——深谋远虑变成一次局部比较。后面主线上几乎每一个算法——动态规划、蒙特卡罗、时序差分、Q-learning、DQN、Actor-Critic 里的 critic——估的都是这个数，区别只在用什么数据、按什么规则更新。值函数是它们共同的对象：这个定义清楚了，后面各算法的差异才有可比的基准。
那为什么不先讲 MDP 的定义？五元组 (S, A, P, r, γ) 是形式，值函数是目的。先给形式，那些记号会显得没有来由；先把目的说清楚，下一课再补形式，那时每个符号都能对上一个你已经算过的量。
两个名字先摆在这儿，这一课从头到尾都在算它们。
两行读一遍：上一行说「照这个走法走，平均能拿多少」；下一行说「所有走法里最好的那一种，能拿多少」。Gt 是从此刻起往后所有奖励折现相加，叫回报，§9 会展开写；E 表示取平均，因为落点可能带随机。
所以这一课只用一条 5 个状态的链、一个 γ、一张能手算的表。每个数都小到能在纸上验一遍。
§ 1示例：五状态链
一条最小的链，五个状态：
规则简单到没有任何歧义：
- 每走一步就进下一个状态；走到 之后就原地打转，永远待在 。
- ，。也就是说 每站一次给 1 分，往后每一步都是 1 分，一直到无穷。
- 折现 ：下一步拿到的 1 分，现在只值 0.9 分。
从 出发，把未来所有的分折现加起来，一共值多少？
这个数是有答案的。从 走 4 步到 ，之后每一步都拿 1 分：
先记住这个数 6.5610。下面我们假装不知道它，用「刷」的方式一步一步把它逼出来——因为在真实问题里，你永远写不出这么一个闭式解。
§ 2有限期限值函数 Vk
先给它一句能读懂的话，再给式子。白话是这样的：
就是预算——还允许走几步。就这么简单，没有别的含义。 不是时刻。
写成式子，就是把「只允许走 k 步」这句话直译一遍——把回报那条无穷和只取前 k 项：
这个式子读一遍就够了：从 s 出发，把接下来这 k 步收到的奖励逐个打折加起来，走满 k 步就停，再往后的一概不算。
V0 = 0 不是「初值随便填」——一步都不许走，也就拿不到任何奖励，它是这一族里第一个正确答案。让 k 一直加下去，截掉的那一截就补齐了，剩下的正是 §9 那个回报 G。
先手算一个。 是多少？意思是：从 出发，只给你 3 步，能拿多少？照着数就行：
| 第几步 | 这一步你在哪 | 拿到 | 折现后 |
|---|---|---|---|
| 第 1 步 | 0 | 0 | |
| 第 2 步 | 0 | 0 | |
| 第 3 步 | 1 | ||
| 合计 | 0.810 | ||
所以刷第 遍并不是「第 次瞎猜」，而是把问题的期限从 步延长到 步，然后精确地回答它。
§ 3值表的逐遍迭代
每刷一遍，就把预算加一格，整张表被覆写成新的一版（）。下面把每一版并排印出来只是为了对照——真跑的时候手里始终只有一张 5 个数的表，新的一版盖掉旧的，第 k 版一写完，前面那些就没有了：
| 刷第几遍 | 这一行在回答 | |||||
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1.0000 | 只剩 1 步能拿多少 | |
| 0 | 0 | 0 | 0.9000 | 1.9000 | 只剩 2 步能拿多少 | |
| 0 | 0 | 0.8100 | 1.7100 | 2.7100 | 只剩 3 步能拿多少 | |
| 0 | 0.7290 | 1.5390 | 2.4390 | 3.4390 | 只剩 4 步能拿多少 | |
| 0.6561 | 1.3851 | 2.1951 | 3.0951 | 4.0951 | 只剩 5 步能拿多少 | |
| 1.2466 | 1.9756 | 2.7856 | 3.6856 | 4.6856 | 只剩 6 步能拿多少 | |
| 1.7780 | 2.5070 | 3.3170 | 4.2170 | 5.2170 | 只剩 7 步能拿多少 |
表停在第 7 行只是为了看清规律——这条链在第 7 遍远没有收敛。离真值还差多少、要刷多少遍、什么样的问题能在有限遍精确收敛，都在 §6.3。
这些数没有一个是猜的，靠的是一个公式：
这个式子读一遍就够了：站在 s、手上还有 k 步预算，这一格的值 ＝ 当场收到的奖励，加上打一次折之后、站在下一格且预算只剩 k−1 步时的值。两个下标差一级，正是「走这一步花掉了一格预算」。
就这么回事。 不是什么算法细节，是你真的少了一步可走。
挑四格当场算一遍，每一格都只用上一行（预算少一级）的数字：
| 要算的格 | 套公式 | 代入上一行 | 结果 |
|---|---|---|---|
| 1.9000 | |||
| 1.7100 | |||
| 2.7100 | |||
| 0.8100 |
在表上就是：要填某一格，往上一行（预算少一级）、沿转移方向的下一列去取数。
- 那个 1 只有 自己发得出来。 里的 1 是它站上去当场拿的； 里没有这个 1，它拿到的只是折过一次的、 上一稿的那份。每往左一格，就再乘一个 0.9。这也是为什么同一行里相邻两格的差，越往左越小。
- 取的永远是上一行。算 用的是 ，不是同一行刚刚算出来的 。要是用了后者，你会得到 ——回表里找一下，那正好是下一行的 。就地更新（Gauss–Seidel）确实能多推进一格，但下标就不再对得上「只剩 步」这个解释了。
- 非零值第一次出现的位置，每刷一遍往左挪一格。 只有 非零， 轮到 ， 轮到 。刷一遍，消息走一格——表里加粗的那条斜线就是它，这句话后面每一课都会再遇到。
我们只盯 那一列——那就是我们要的数：
| 预算 | 这一遍新加了 | 离 6.5610 还差 | 差距 / 上一遍 | |
|---|---|---|---|---|
| 1 | 0.0000 | 0 | 6.5610 | — |
| 2 | 0.0000 | 0 | 6.5610 | 1.000 |
| 3 | 0.0000 | 0 | 6.5610 | 1.000 |
| 4 | 0.0000 | 0 | 6.5610 | 1.000 |
| 5 | 0.6561 | = 0.6561 | 5.9049 | 0.900 |
| 6 | 1.2466 | = 0.5905 | 5.3144 | 0.900 |
| 7 | 1.7780 | = 0.5314 | 4.7830 | 0.900 |
| 10 | 3.0742 | = 0.3874 | 3.4868 | 0.900 |
| 20 | 5.3452 | = 0.1351 | 1.2158 | 0.900 |
| 40 | 6.4132 | = 0.0164 | 0.1478 | 0.900 |
| 6.5610 | 0 | 0 | — |
§ 4三处容易读错的地方：刷表、自举、递推方向
4.1 刷表的时候，什么都没在走
三件事必须分开：刷表——你在纸上算，agent 一步没动；收敛——表不再变，得到 V⋆；执行——这时才开始走，而且每一步只查表，不再算任何东西。
所以「是一开始就算完，还是走一步算一步」，答案是一开始全部算完。但更要紧的是下一句：刷表这个过程本身也不是在走。§3 那七行不是七步路。
拿 V3 那一行验一遍：[0, 0, 0.8100, 1.7100, 2.7100]。这五个数同时成立、互不冲突，因为它们回答的是五个不同起点的同一个问题——「只给你 3 步预算，能拿多少」。要是这一行的意思是「走了 3 步之后」，那 agent 此刻只能站在一个格子里，另外四个数就该没有意义——可它们每一个都有意义，而且都精确。
「这一行为什么只能是 3 步」——因为 3 是你自己设定的参数，不是算出来的结果。第 k 行的定义就是「预算 ＝ k」，换一行就是换一个预算、重新问一遍。所以 V3 这一行是五个各自独立的思想实验，唯一的共同点是每个都只给 3 步。把五条路逐条列出：
| 从哪儿出发 | 这 3 步怎么走 | 第 1 步 | 第 2 步 | 第 3 步 | 合计 |
|---|---|---|---|---|---|
| s0 | s0→s1→s2→s3 | 0 | 0 | 0 | 0 |
| s1 | s1→s2→s3→s4 | 0 | 0 | 0 | 0 |
| s2 | s2→s3→s4→s4 | 0 | 0 | γ²·1 = 0.8100 | 0.8100 |
| s3 | s3→s4→s4→s4 | 0 | γ·1 = 0.9000 | γ²·1 = 0.8100 | 1.7100 |
| s4 | s4→s4→s4→s4 | 1·1 = 1.0000 | γ·1 = 0.9000 | γ²·1 = 0.8100 | 2.7100 |
五条路各走各的，谁也不影响谁；每一条都真的走满 3 步，也都真的只走 3 步。注意 s1 那一行——它第 3 步末确实踏进了 s4，但那一分是「从 s4 出发」的那一步才发的，预算已经用完，所以仍是 0。它要等到 V4 才第一次冒头（γ³ = 0.7290）。
就像地图上每个路口都标着「离终点还有多远」——所有路口的数同时印在同一张纸上，不代表你同时站在所有路口。
那还剩最后一问：我只想要 V(s0) 那一个数，为什么非得把五格全算出来？因为算不动。V3(s2) 要引用 V2(s3)，后者又要引用 V1(s4)——你要的那个数，是建立在别的格子的答案之上的。而且全算完之后你还额外得到一样东西：每一格都知道自己该怎么走（§7），从哪格出发都能用。
「边走边算」是有的，但那是 Stage 1 的事：没有转移规则的时候，你只能真走出去、把采样拿回来更新。这一课规则是完整给你的，所以能在动之前把答案全算完。
4.2 自举：形式上是，但不带它的毛病
自举（bootstrapping）＝ 用自己的估计去更新自己的估计，不等真实结果出来。§3 那条备份公式右边引用的正是自己的上一稿，所以形式上它百分之百是自举；§3 那句「取的永远是上一行」还是自举的严格版本——连同一行刚算出来的新值都不许用。
反面是蒙特卡罗：把一整条轨迹走到底、拿到真实的回报 G，再回头更新。全程不引用任何自己的估计。这两条路后面讲蒙特卡罗与时序差分那一课会正面撞上。
4.3 为什么从「只剩 1 步」起
递推只有一条通用原则：从你已经知道答案的那一端开始，往未知的方向推。§2 定义的值是「从这儿开始，今后还能拿多少」，这个量只有一端不用算——V0 = 0，也就是 §2 那个「预算为 0」的答案。种子只能是它，方向也就只剩一个。
而且 k 是从 0 往上长的，不是时间倒流。V1 回答「只给 1 步」，V2 回答「给 2 步」……k 数的是还允许走几步，不是「现在走到第几步」。每一稿都是一个完整问题的完整答案，后一稿引用前一稿。
那「消息一格一格往左传」又是怎么回事？不是 agent 在往左挪，是「看得见奖励」的范围在往外长。§5.2 那条「距离 ＝ 预算」的分界线就是它：预算每加一格，够得着奖励的状态就往左多一个。传到 s0 用了 4 遍，正好是它到 s4 的距离——4 是距离，不是时刻。
§ 5稀疏奖励与 γ 收缩
前两条讲奖励稀疏时值表会怎么长（5.1、5.2），第三条讲它离答案还差多少、这个差距按什么速度缩小（5.3）。第三条是后面所有收敛结论的原型。
5.1 稀疏奖励
的意思是：从 出发只给 4 步，你确实一分都拿不到（第 5 步才走到 ）。这个 0 精确无误。
稀疏奖励难学，难就难在这里，这不是算法设计的问题，是信息传播速度决定的。
5.2 首次非零值
那一遍，。为什么？因为预算刚好够走到 ，只来得及吃一口就没预算了。同理表里每个状态第一次冒头的值都是 （ 是它到 的步数）：
| 离 几步 | 第一次非零在 | 那个值 | |
|---|---|---|---|
| 0 | |||
| 1 | |||
| 2 | |||
| 3 | |||
| 4 |
表里 0 与非 0 的那条分界线，就是 「距离 ＝ 预算」 这条线——§3 第三条那句「刷一遍，消息走一格」，量出来就是它。
5.3 收缩率与截断误差
看「这一遍新加了」那一列： 也就是
刷 遍 ＝ 加完了前面若干项。
那「还差多少」就是还没加进来的那条尾巴：
核对一下： 时 ✓； 时 ✓； 时 ✓。表里那一列一个不差。
尾巴每加进来一项，剩下的尾巴就整体乘一个 ——不多不少，精确 倍。
下一课那个「」的压缩性质，在这条链上就是这一列数字。它不是什么抽象定理，就是等比级数的尾巴在按 缩。
顺带回答了一个常见困惑：你从来不需要真的去加无穷项。你只是加了有限项，而没加的那部分小到可以忽略。
§ 6最优值函数：刷一遍不再变的那张表
6.1 折现与收敛性
无穷多项加起来，为什么不是无穷大？因为折现。第 100 步拿到的 1 分只值 。越远的奖励在总和里占的权重越小，加到最后是个有限的数。 一直原地拿分，加起来是
其余各列停在 ： 停 9、 停 8.1、 停 7.29、 停 6.561——就是我们一路刷出来的那个数。
6.2 为什么 V⋆ 刷一遍不变
看清楚 和 各自满足的式子，区别只在下标：
| 式子 | 左右两边 | |
|---|---|---|
| 不是同一个函数（预算差一级） | ||
| 是同一个函数 |
预算是 的时候，走一步就变成 ，所以式子两边是两个不同的函数。
预算是无穷的时候，走一步还是无穷，所以式子两边是同一个函数。
这就是 V⋆ 的全部特别之处——一句大白话，不需要任何抽象。
在我们这条链上验一下：
✓
✓
那一格左右两边真的是同一个数，因为它走一步之后还是 ，未来还是那个无穷长的未来。
后面那些「」、「Bellman 方程是自洽条件」、「 是唯一与自己一致的函数」，说的全是这一件事。
6.3 那要刷几遍才够
6.2 说的是 V⋆ 刷一遍不变；可你手上拿着的是 Vk，它每刷一遍都还在动。所以还剩一个很实际的问题：刷到第几遍可以停手？
先看它为什么一定会停下来。5.3 那条尾巴 已经把话说完了：每刷一遍，它整体乘一个 γ。 时刷到第 100 遍，尾巴只剩 ——加了等于没加。
这也顺带解释了 γ 的作用——它决定了「多远之后的事情可以不管」。γ 越接近 1，尾巴缩得越慢，你要刷的遍数越多（大致 1/(1−γ) 那个量级），算得越慢；γ 小则很快就够，但你也就真的看不了那么远。
那这条链要刷几遍才算完？把 §5.3 那条尾巴写成不等式，要求它小于精度 ε：
代进 γ ＝ 0.9 算三个数：
| 要 Vk(s0) 离 6.5610 差不到 | 得刷几遍 | 刷完之后的值 |
|---|---|---|
| 0.1 | 44 | 6.4640 |
| 0.01 | 66 | 6.5514 |
| 0.001 | 88 | 6.5601 |
这条链为什么永远差一点点？因为 s4 一直在发分，奖励流没有尽头，尾巴 γk/(1−γ) 只能越缩越小、永远不会真的等于 0。这种情形下没有「第几遍就完事」这回事，只有「订一个阈值、够小了就停手」。
顺带一提：真写代码时没人去解上面那个对数不等式——你不知道 V⋆，也就不知道「还差多少」。实际做法是盯相邻两轮的最大改动 Δ，小到一定程度就停手，收缩性保证这时离真值也够近了。这条只用两轮就能算的界下一课会给。
§ 7一步贪心与最优策略
手上有了 ，做决策就不用再想未来了——只看一步就够：
这个式子读一遍就够了：站在 s，把每个能走的动作都试着算一遍「这一步当场拿多少 ＋ 打折之后落点值多少」，谁算出来最大就走谁。
大括号里那一整块——「这一步拿多少 + 到了那儿以后还能拿多少」——本身也是一个值，它有名字：动作价值 Q⋆(s,a)。用它，上面那一步贪心可以写得更短：
两行读一遍：上一行——这一格的值，就是它所有动作里最好的那个动作值；下一行——最优策略在这一格该走的，就是取到那个最好值的动作。一个交出数，一个交出动作。
这条链上每个状态只有一个动作，所以 Q⋆(s0, 前进) = V⋆(s0) = 6.5610，两者完全重合，看不出差别。要到下一课那间每格有 4 个动作的仓库里，它们才真正分开——而分开之后 Q 会比 V 更好用：用 V 挑动作，必须先知道每个动作会落到哪；用 Q 只要在这一行里挑最大。
带不带星也要分清。V⋆ 和 Q⋆ 说的是「最优地走下去能拿多少」；不带星的 V 和 Q 说的是「照某个给定的走法能拿多少」。这条链只有一种走法，所以这四个记号在这里指的是同一组数——上面那句「到 4 个动作的仓库里才分开」，对它们同样成立。
有了这张表，深谋远虑和目光短浅变成同一件事。
打个比方： 是一张地形图，最优决策就是「永远朝最陡的方向走」。地图一旦到手，全局规划就退化成纯局部的、瞬时的动作。
而整个强化学习在做的，就是在没有地图的情况下，一边走一边把这张图画出来。
§ 8这套刷法的名字：策略评估与值迭代
方法本身只有一句话：从预算 1 开始，一行一行往下加，加到再加也不变为止。这套刷法在动态规划里有正式名字，而且是两个。
「收敛」的意思也很直接：预算再多也改变不了答案了。
§ 9回报
开头只报了它的名字，式子一直没展开。现在把它写全：
| 记号 | 含义 |
|---|---|
| Gt | 回报。从时刻 t 往后，所有奖励折现之后加起来的总和 |
| Rt+1 | 奖励。在时刻 t 行动之后收到的那一个奖励。下标写 t+1 而不是 t，因为它是这一步的结果 |
| t | 时刻。已经走到第几步。它和前面那个 k 是两回事——k 是预算（还能走几步），t 是时间（走到第几步了） |
这个式子是干什么用的。它把「今后能拿多少」从一句话变成一个能算、能取平均的量。值函数就是它的平均值——这一课能把 V⋆ 一格一格算出来，靠的正是背后有这么一个可加的量；后面所有算法要估计的，也都是它。
代进这条链核对一遍。从 s0 出发，前四步都还没站上 s4，所以 R1 到 R4 全是 0；从 R5 起每一步都拿 1：
正是 §1 那个数。§3 那张表的每一行，也都是这个式子的截断版——把无穷和只取前 k 项，得到的就是 Vk；§5 里「还差多少」的那条尾巴，就是被截掉的那些项。
§ 10本章小结
- ＝ 从 出发、预算 步，最多能拿多少。每一遍都是一个正确答案，只是问题的期限不同； 不是时刻。
- 备份公式管的就是预算：花掉一步走到 ，预算少一级。
- 刷 遍 ＝ 把无穷级数的前几项加进来；还差的那点就是没加完的尾巴 ，每刷一遍精确乘 。所以你从来不用真的加无穷项。
- ＝ 预算无限的答案。它特别，是因为无穷减一还是无穷，所以式子两边是同一个函数：刷一遍它还是它自己。
- 有了 ，只看一步就能做最优决策。它把整个未来压成了每个状态上的一个数。
- 回报 G 是这一切的底座。值函数就是它的平均值；这条确定性链上 G 只有一个值，一旦有了随机性才需要「取平均」这件事。