跳到主要内容

动态规划 — 把 Bellman 方程改成赋值语句

这一章讲三件事: 已知环境的完整规则时,值函数和最优策略怎么一步步算出来; 「评估」与「改进」这两个动作怎么咬合成策略迭代、又能怎么剪成值迭代; 以及 GPI 这个词为什么能罩住后面所有的算法。 读完你会得到全书的第一个「完整可解」样本——之后所有章节都在回答同一个问题: 不给你这么好的条件,怎么办。

1. 这一章在全书里的位置​

先把立场摆正。动态规划(DP)需要环境的完整模型——那个四参数的动力学函数 p(s′,r|s,a),每个状态动作组合的概率都得知道。现实中这几乎从不成立;而且计算上也不便宜。但作者开篇就给 DP 派了角色:后面所有方法,都可以看成「想达到 DP 的效果,但计算更少、也不要完整模型」的尝试1。DP 是标尺,不是终点。

DP 的关键想法只有一句:用值函数来组织和结构化对好策略的搜索2。做法则简单得惊人——第 03 章说过,每个值函数都满足一条 Bellman 方程(一个等式);把等号读成赋值号,方程就变成了算法3。

2. 核心原理一:策略评估——「照这套打法,值多少」​

策略评估(policy evaluation)回答:给定一套策略 π,每个状态的 vπ(s) 是多少。做法:先把所有状态的值随便设个数(终止态必须是 0),然后一遍遍按 Bellman 方程的右端刷新每个状态——用旧的邻居值算出新的自己的值4。这种「对全部可能后继按概率取期望再更新」的操作,书里统一叫期望更新(expected update)——DP 的所有更新都属于这一类5。

3. 主走查:4×4 网格世界,第一遍扫描​

拿书里的例 4.1 走一遍(规则与 k=1 那一行的数取自书;sweep 2 的两个数是我们照规则自己算的,计算过程当场写出)6:

  规则:4×4 网格,14 个普通格 + 终止格(右上、右下角,实为同一状态);
        四个动作(上下左右)确定性移动,撞墙留在原地;
        每走一步奖励 −1,到达终止格游戏结束;不折扣(γ=1);
        策略:四方向等概率(各 0.25)。初始:所有格 0。

  ┌ 1   2   3  ⬛ ┐
  │ 4   5   6   7 │      ⬛ = 终止格
  │ 8   9  10  11 │
  └ 12 13 14  ⬛ ┘

  第 1 遍扫描,格子 1(左上角):
    上→撞墙留原地:−1 + 0(自身旧值 0)
    左→撞墙留原地:−1 + 0
    右→格子 2:      −1 + 0
    下→格子 4:      −1 + 0
    v(1) = 0.25 × (−4) = −1.0

  格子 5(正中):四邻全是普通格,旧值全 0:
    v(5) = 0.25 × 4 × (−1 + 0) = −1.0

  事实上这一遍扫完,所有 14 个格全是 −1.0 —— 书中 k=1 那一栏正是如此:
  离终止一步之内的信息(「再走一步要花 1」)刚好传遍全盘。

第二遍扫描开始,信息才往深处走。格子 1(所有邻居在第一遍后都是 −1.0):

  v(1) = 0.25 × [ (−1 + (−1.0)) + (−1 + (−1.0)) + (−1 + (−1.0)) + (−1 + (−1.0)) ]
       = 0.25 × (−8) = −2.0

格子 3(紧挨终止格,向右一步就到):

  v(3) = 0.25 × [ 上(撞墙): −1 + v(3) + 左: −1 + v(2) + 右: −1 + 0(终止)
                 + 下: −1 + v(7) ]     ← 此刻邻居都还是第一遍的 −1.0
       = 0.25 × [ (−2) + (−2) + (−1) + (−2) ] = 0.25 × (−7) = −1.75

照这个速度,「离终止的平均步数」这个真值从终止格一圈圈往回扩散。书里给出的收敛结果(vπ 的准确值)是:左上角 −14、上排第二格 −20、上排第三格 −22——这就是随机乱走时各格平均要走的步数7。还有个书里明说的彩蛋:虽然要很多遍才收敛,第三遍之后对应的贪心策略就已经是最优策略了8。

4. 核心原理二:有了值,怎么改策略(策略改进定理)​

评估回答「这套打法多好」,下一步自然是「怎么换一套更好的」。策略改进定理给出判据:在状态 s 改选动作 a,若 qπ(s,a) > vπ(s)——即「只在 s 改走 a、其余照旧」比「永远照旧」好——那么处处都照新选法走的新策略,处处不差于旧策略9。证明的骨架是不断把不等式往远处展开(书里给了完整推导),直觉版:眼前占的便宜不会在别处亏回去。

把每个状态都换成贪心动作,几乎必然得到更好的策略;除非换完一点没变——那原策略就已经是最优10。这就是「改进」这半台机器。

5. 核心原理三:两台机器合体——策略迭代与值迭代​

策略迭代就是把评估和改进交替按到底:π0 评估得 v,改进得 π1,再评估、再改进……有限 MDP 的确定性策略只有有限个,每轮严格变好,所以有限步内必然到达最优11。书里的例 4.2(Jack 租车行:两个门店、每辆车每晚可挪、挪一辆 2 美元、每租出一辆挣 10 美元、需求与归还是泊松流)从「从不挪车」出发,几轮迭代就到最优策略——策略迭代往往收敛得出奇地快12。

它的弱点:每轮的评估本身要扫很多遍才收敛。值迭代把评估剪到只剩一遍:每轮对每个状态直接取「所有动作里最好的那个期望」更新一次,评估与改进合并在同一个更新式里(比策略评估的更新多一个 max)13。它也是把 Bellman 最优方程改成赋值语句的直接产物。

GPI(广义策略迭代): 几乎所有强化学习方法,都是「让值函数贴合当前策略」与「让策略对当前值函数贪心」这两个过程的任意组合与任意粗细的交织。两个过程互相使绊子——策略一贪心,值就不准了;值一校准,策略又不贪心了——但只要两个过程都持续推进,合力的终点只能是既贴合自身值、又对自身值贪心的唯一解:最优14。作者还给了个几何像:两条不垂直的「目标线」,朝一条走难免偏离另一条,但来回拉扯整体在逼近交点15。

6. 两个工程注脚​

异步(不统一节奏、逮着一个更新一个)DP。 整盘扫描在大状态空间里是奢侈品:双陆棋 10^20 个状态,每秒更新一百万个状态,扫一遍要一千多年。异步(不统一节奏、逮着一个更新一个)算法不按顺序全盘扫,逮着一个状态就按同一套更新式更新它,唯一要求是每个状态都被无限次更新到。它还顺手带来一件重要的事:边跟环境真打交道、边解这个 MDP——agent 走到哪,就更新哪16。

bootstrapping 这个词从这里立起来。 DP 的每次更新,用的是「估计的值」去更新「别的估计的值」——拿猜测去校准猜测,作者命名为 bootstrapping17。记住这个词:第 05 章的蒙特卡洛不要它,第 06 章的 TD 又把它捡回来——要不要 bootstrapping,是贯穿全书方法空间的一条大轴。

7. 作者的判断与证据​

书里给了证明/推导的: 策略改进定理(展开式证明)、策略迭代有限步收敛、值迭代收敛(条件同 v* 的存在性)。效率上,作者引一个对照:DP 找最优策略的时间是状态数与动作数的多项式;而策略总数是 k^n——DP 比在策略空间里直接搜索快出指数倍18。

作者的立场: 「维数灾难」常被算在 DP 头上,作者替它辩护——状态数随变量(描述局面的量)个数指数增长是问题本身的属性,不是 DP 方法的毛病;横向比起来 DP 反而更能扛大状态空间19。这句辩护放在这里,是为第二部分(函数逼近)埋伏笔:大状态空间真正的出路在第 09 章。

书里自曝的边界: 例 4.2 图 4.2 那类非线性(规律带拐弯、不是一条直线能解)、任意动态的现实约束,作者明说「往往除动态规划外很难用别的优化方法处理」——这是 DP 的真实领地20。

8. 边界与局限​

  • 必须有完整、准确的模型。 这是 DP 与后面所有「学习」方法的分水岭;模型差一点,解就往错处走(第 08 章专门处理模型错的问题)。
  • 全盘扫描在大问题上不可行,异步只是缓解不是根治。
  • 策略迭代每轮评估要截断到多准,本章只给「值迭代=截到 1 遍」这个极端情形;中间形态(modified policy iteration)书里在文献注里点名,不展开。
  • 本章所有保证都只对表格情形成立;一旦函数逼近进场(第 09 章),第 03 章攒下的部分保证就开始松动——到第 10 章会看到松动到什么程度。

9. 可带走的​

  1. 把等式读成赋值,方程就成了算法——Bellman 方程 → 更新规则,这是本章也是全书技法上的一招鲜。
  2. 期望更新:按环境模型对全部可能后继取期望再更新;后面用「抽样一个后继」替代它的,就是学习类方法。
  3. 主走查的一句话:4×4 网格世界第一遍扫描全盘变 −1.0(离终止一步的代价传遍全盘),vπ 的真值 −14/−20/−22 就是「乱走要走的平均步数」。
  4. 策略改进定理:局部有便宜可占 ⟹ 换策略必不亏;没有便宜可占 ⟹ 已最优。
  5. 策略迭代=评估+改进按到底,值迭代=评估剪到一遍;两者都是 GPI 的极端,中间任意混搭都行。
  6. GPI 是全书原型:两个互相拉扯的过程,合力把对方拽向最优——后面每章的新算法,都是给这两个过程换发动机。
  7. bootstrapping=拿估计更新估计;DP 有它,蒙特卡洛没有,TD 有——这个词是方法空间的一条轴。
  8. 10^20 状态扫一遍要一千年;大规模问题上,更新顺序比更新公式更值得设计。

10. 原文地图​

主题原书章原文位置
DP 定义、全书定位Dynamic Programmingtext/07-fm-dynamic-programming.txt:3(搜「perfect model」) · text/07-fm-dynamic-programming.txt:8(搜「much the same effect」)
值函数组织搜索;方程变赋值Dynamic Programmingtext/07-fm-dynamic-programming.txt:20(搜「organize and structure」) · text/07-fm-dynamic-programming.txt:40(搜「turning Bellman」)
策略评估、期望更新、in-placeDynamic Programmingtext/07-fm-dynamic-programming.txt:76(搜「iterative policy evaluation」) · text/07-fm-dynamic-programming.txt:81(搜「expected update」) · text/07-fm-dynamic-programming.txt:100(搜「converges faster」)
例 4.1 网格世界Dynamic Programmingtext/07-fm-dynamic-programming.txt:125(搜「4」) · text/07-fm-dynamic-programming.txt:140(搜「undiscounted, episodic」) · text/07-fm-dynamic-programming.txt:141(搜「1 on all transitions」) · text/07-fm-dynamic-programming.txt:147(搜「negation of the expected number」)
收敛图、三遍后最优Dynamic Programmingtext/07-fm-dynamic-programming.txt:210(搜「Convergence of iterative」) · text/07-fm-dynamic-programming.txt:215(搜「third iteration」)
策略改进定理Dynamic Programmingtext/07-fm-dynamic-programming.txt:240(搜「policy improvement theorem」)
已最优则无改进Dynamic Programmingtext/07-fm-dynamic-programming.txt:299(搜「must be」)
策略迭代、有限步收敛Dynamic Programmingtext/07-fm-dynamic-programming.txt:322(搜「Policy Iteration」) · text/07-fm-dynamic-programming.txt:491(搜「finite number of iterations」)
Jack 租车Dynamic Programmingtext/07-fm-dynamic-programming.txt:365(搜「car rental」)
值迭代Dynamic Programmingtext/07-fm-dynamic-programming.txt:470(搜「value iteration」) · text/07-fm-dynamic-programming.txt:511(搜「combines, in each of its sweeps」)
异步 DP、一千年Dynamic Programmingtext/07-fm-dynamic-programming.txt:567(搜「Asynchronous」) · text/07-fm-dynamic-programming.txt:574(搜「a thousand」)
GPIDynamic Programmingtext/07-fm-dynamic-programming.txt:616(搜「Generalized Policy Iteration」) · text/07-fm-dynamic-programming.txt:632(搜「well described as GPI」) · text/07-fm-dynamic-programming.txt:646(搜「competing」)
两条线的几何Dynamic Programmingtext/07-fm-dynamic-programming.txt:654(搜「two constraints」)
多项式 vs 指数、维数灾难辩护Dynamic Programmingtext/07-fm-dynamic-programming.txt:683(搜「exponentially faster」) · text/07-fm-dynamic-programming.txt:690(搜「curse of dimensionality」)
bootstrapping 定义Dynamic Programmingtext/07-fm-dynamic-programming.txt:744(搜「bootstrapping」)

Footnotes​

  1. 出处:「Dynamic Programming」第 8 段(text/07-fm-dynamic-programming.txt:8,搜「much the same effect」)。原文:「all of these methods can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model」。 ↩

  2. 出处:「Dynamic Programming」第 20 段(text/07-fm-dynamic-programming.txt:20,搜「organize and structure」)。 ↩

  3. 出处:「Dynamic Programming」第 40 段(text/07-fm-dynamic-programming.txt:40,搜「turning Bellman」)。 ↩

  4. 出处:「Dynamic Programming」第 76 段(text/07-fm-dynamic-programming.txt:76,搜「iterative policy evaluation」);更新式 (4.5) 见第 70 段(搜「vk+1」)。 ↩

  5. 出处:「Dynamic Programming」第 81 段(text/07-fm-dynamic-programming.txt:81,搜「expected update」)。 ↩

  6. 出处:「Dynamic Programming」第 125 段(text/07-fm-dynamic-programming.txt:125,搜「gridworld」)起为例 4.1;规则细节:「undiscounted, episodic」在第 140 段(text/07-fm-dynamic-programming.txt:140,搜「undiscounted, episodic」),「reward is −1 on all transitions」在第 143 段(搜「1 on all transitions」),随机等概率策略在第 144 段(搜「equiprobable random policy」);k=1 全为 −1.0 与收敛值 −14/−20/−22 见图 4.1(第 174-208 段,该图排版有乱码,数字以图为准);「第三遍后策略已最优」在第 215 段(text/07-fm-dynamic-programming.txt:215,搜「third iteration」)。sweep 2 的 v(1)=−2.0 与 v(3)=−1.75 是我们按书中规则(双数组、同步更新)自行算出的演示值。 ↩

  7. 出处:「Dynamic Programming」第 204-208 段(text/07-fm-dynamic-programming.txt:73,搜「k =」)。k=∞ 那一栏的数字(0、−14、−20、−22 等)与「值=−期望步数」的解读见第 147 段(搜「negation of the expected number」)。 ↩

  8. 出处:「Dynamic Programming」第 215 段(text/07-fm-dynamic-programming.txt:215,搜「third iteration」)。 ↩

  9. 出处:「Dynamic Programming」第 240 段(text/07-fm-dynamic-programming.txt:240,搜「policy improvement theorem」)。 ↩

  10. 出处:「Dynamic Programming」第 299 段(text/07-fm-dynamic-programming.txt:299,搜「must be」)。 ↩

  11. 出处:「Dynamic Programming」第 322 段(text/07-fm-dynamic-programming.txt:322,搜「Policy Iteration」)与第 491 段(text/07-fm-dynamic-programming.txt:491,搜「finite number of iterations」)。 ↩

  12. 出处:「Dynamic Programming」第 365 段(text/07-fm-dynamic-programming.txt:365,搜「car rental」);「surprisingly few iterations」在第 426 段(搜「surprisingly few」)。 ↩

  13. 出处:「Dynamic Programming」第 470 段(text/07-fm-dynamic-programming.txt:470,搜「value iteration」)与第 511 段(text/07-fm-dynamic-programming.txt:511,搜「combines, in each of its sweeps」)。 ↩

  14. 出处:「Dynamic Programming」第 616 段(text/07-fm-dynamic-programming.txt:616,搜「Generalized Policy Iteration」)与第 632 段(text/07-fm-dynamic-programming.txt:632,搜「well described as GPI」);两个过程互相拉扯在第 646 段(搜「competing」)。 ↩

  15. 出处:「Dynamic Programming」第 654 段(text/07-fm-dynamic-programming.txt:654,搜「two constraints」);「不垂直」在第 666 段(搜「orthogonal」)。 ↩

  16. 出处:「Dynamic Programming」第 567 段(text/07-fm-dynamic-programming.txt:567,搜「Asynchronous」)与第 574 段(text/07-fm-dynamic-programming.txt:574,搜「a thousand」);「所有状态无限次更新」在第 581 段(搜「infinite number of times」);边交互边解在第 602 段(搜「real-time interaction」)。 ↩

  17. 出处:「Dynamic Programming」第 744 段(text/07-fm-dynamic-programming.txt:744,搜「bootstrapping」)。原文:「they update estimates on the basis of other estimates. We call this general idea bootstrapping」。 ↩

  18. 出处:「Dynamic Programming」第 683 段(text/07-fm-dynamic-programming.txt:683,搜「exponentially faster」)。 ↩

  19. 出处:「Dynamic Programming」第 690 段(text/07-fm-dynamic-programming.txt:690,搜「curse of dimensionality」)。 ↩

  20. 出处:「Dynamic Programming」第 452 段(text/07-fm-dynamic-programming.txt:452,搜「nonlinearities」)。 ↩