跳到主要内容

有限 MDP — 目标、回报与值函数的正式登场

这一章讲四件事: 目标被压缩成哪一句话;「长远的好处」怎么变成一个能算的数; 值函数怎么定义、Bellman 方程说了什么;「最优」怎么定义、为什么它只可逼近。 读完你就有了一把全书通用的尺子——后面每种算法,都是在不同的假设下估这把尺子。

1. 顶层全景:三个信号,一个闭环​

       智能体 ──── 动作 A(t) ───▶ 环境
          ▲                          │
          └── 状态 S(t+1) + 奖励 R(t+1) ┘     (每个时间步走一圈)

  图说:智能体和环境之间只来回传三样东西——动作、状态、奖励。

有限 MDP(finite Markov decision process)是作者给强化学习问题选定的数学骨架:状态、动作、奖励的集合都有限,环境的行为被一个四参数函数 p(s′,r|s,a) 完全刻画——在状态 s 做动作 a,下一状态是 s′、奖励是 r 的概率1。作者特意强调:这个函数就是环境的全部;想知道环境的任何别的东西(比如「下一步在哪个状态的概率」),都能从它算出来2。

「Markov」这个词是条限制,但限制的不是问题,是状态:状态必须装下历史中一切影响未来的信息3。直觉版:看到现在,就不用再看过去。

框架还有个容易想错的细节:智能体和环境的边界,不是身体的边界。机器人的电机、传感器、连人的肌肉骨骼,都算环境;奖励的 computing 电路也长在「体内」,却算在环境一侧。分界规则只有一条:凡智能体不能随意改变的东西,都划给环境。作者给的理由很锋利——边界画的是「绝对控制力的边界,不是知识的边界」:就算你对魔方的规则了如指掌,它依然不受你随意摆布4。

2. 核心原理一:目标被压缩成一句话(奖励假说)​

「我想要的是长远的总奖励。」这句直觉,书里把它立成了全书的公理,奖励假说(reward hypothesis):

我们所说的一切「目标」与「目的」,都可以很好地理解为:最大化一个收到的标量(一个单独的数)信号(一个单独的数,称为奖励)的累积和的期望值5。

一句公理换来整个领域的可计算性。作者补了两条使用守则,都来自教训:

  • 奖励只说「要什么」,不说「怎么做」。 让下棋的程序只以赢棋得奖励,不要为吃子、占中心这些中间目标发奖——否则它可能学会光吃子不赢棋6。
  • 想教它先验知识,有更好的地方去放:初始策略或初始值函数,奖励信号不是干这个的6。

3. 核心原理二:「长远」怎么变成一个数(回报与折扣)​

奖励是逐个到账的序列,目标要取期望回报(return)——从现在起未来奖励的总和。这里立刻撞上一个坎:

  • 任务有终点(下完一盘、走出迷宫),叫情节任务(episodic task):回报就是这一程的奖励和,天然有限;
  • 任务没终点(流程控制、长寿机器人),叫持续任务(continuing task):奖励一直来,总和可能是无穷——无穷没法最大化7。

解法是折扣(discounting):未来 t 步后的奖励,只按 γ^t 计价(γ 在 0 到 1 之间)。γ=0,只看眼前;γ 越接近 1,看得越远。折扣后,哪怕每步奖励恒为 +1,总回报也只是有限值 1/(1−γ)——γ=0.9 时是 10,γ=0.99 时是 100(这个对照数书里由公式直接给出)8。

回报还有个日后处处要用的递归(总回报的后一项由前一项算出)形状:G(t) = R(t+1) + γ·G(t+1)——总回报等于下一笔奖励加上再往后的总回报。书里加一句:γ=1 与「无终点」不许同时成立,这是「一条式子通吃两种任务」的代价9。

4. 核心原理三:值函数与 Bellman 方程(主走查)​

策略(policy)π 是从状态到动作概率的映射:π(a|s) 即「在 s 选 a 的概率」10。有了策略才能谈值,因为未来取决于你打算怎么走:

  • 状态值 vπ(s):从 s 出发、此后一直照 π 走,期望回报是多少;
  • 动作值 qπ(s,a):从 s 出发、先走 a、此后照 π 走,期望回报是多少11。

值函数有一条全书的承重性质——它满足递归(自己的值由相邻状态的值算出)关系(递归=自己的值由相邻状态的值来表达):我的值,等于「期望的下一笔奖励」加上「折扣后的后继的值」。这条式子叫 Bellman 方程12。

拿书里的 5×5 网格世界走一遍(下面所有数值都是书中图 3.2 给出的真实解,四舍五入到一位小数)13:

  规则:每格四个动作(上下左右),走不出界;
        撞墙得 −1 并留在原地,其余步奖励 0;
        例外:从 A 格出发任何动作得 +10 并被扔到 A′,从 B 格得 +5 扔到 B′。
        策略:四个动作等概率(各 0.25),折扣 γ=0.9。

  问:中间那格(书中值为 0.7)的 Bellman 方程成立吗?
  它的四邻,书中值:上 2.3,下 −0.4,左 0.7,右 0.4;四步都不撞墙,奖励全为 0。

  v = 0.25×(0 + 0.9×2.3) + 0.25×(0 + 0.9×0.7) + 0.25×(0 + 0.9×(−0.4)) + 0.25×(0 + 0.9×0.4)
    = 0.225×(2.3 + 0.7 − 0.4 + 0.4)
    = 0.225×3.0
    = 0.675 ≈ 0.7  ✓  与书中给出的值吻合

  这一步验的就是 Bellman 方程:我的值 = 后继值的折扣平均(加上路上的奖励)。
  整张值函数表就是「每个格子都满足这条方程」的唯一解。

这张表还自带一个反直觉的读法,值得单独说:A 格值 8.8,低于它眼前的 +10——因为 A 会把你扔到贴边的 A′,那儿撞墙风险高;B 格值 5 之后所在的 B′ 反而值不低——B′ 离 A、B 都不远,期望上占便宜。值函数读的是「此后的一生」,不是眼前那一口13。

5. 核心原理四:「最优」长什么样​

策略之间可以比高低:π 不差于 π′,当且仅当每个状态上 vπ 都不低于 vπ′。这样的最优策略至少存在一个(可能多个),它们共享同一个最优状态值函数 v* 与最优动作值函数 q*14。

最优值函数满足的 Bellman 方程多了一个 max:不再「照我的策略平均」,而是「挑最好的动作」。而它带来全书最漂亮的一个转折——对 v* 贪心,就等于最优:

只要手里有 v*,每个状态只看一步、挑「奖励+v*(下一状态)」最大的动作,选出来的就是长程最优策略。因为 v* 已经把未来所有可能的行为后果都算进这个数里了——长程最优被压缩成一步查表15。

q* 更进一步:连一步前瞻都不用。q*(s,a) 直接给出「先走 a 之后最优走」的值,挑 q* 最大的动作就是最优动作;代价是表从「每状态一项」变成「每状态×每动作一项」。书里的说法:动作值函数把所有一步前瞻的结果缓存(把结果预先算好存着待用)了下来16。

6. 作者的判断与证据​

书里给了推导的: 折扣让无穷和有限(几何级数);Bellman 方程对 vπ 有唯一解;n 个状态 n 条方程的解法在原则上存在17。

作者的立场,且说得很重: 精确解 Bellman 方程「 akin to 穷举」,依赖三个在实践中很少同时成立的假设——动力学已知、算力够、状态满足 Markov 性。他给出一个参照数字:双陆棋约 10^20 个状态,在最快的计算机上解 Bellman 方程要几千年——所以强化学习只能要近似解18。这是整本书的立项书:后面的每一章,都是一条通往近似解的路。

另一个立场的预告: 强化学习不追求「把所有状态都算准」。常见状态值得学准,一辈子遇不到一次的状态学错也无妨——Tesauro 的程序对某些从 expert 对局里不出现的局面可能下得很臭,不妨碍它是史上最强。作者说这是 RL 区别于其他 MDP 近似解法的关键性质19。

7. 边界与局限​

  • 状态的选取全章被悬置:什么算「一个状态」是表示问题,本书只留一句「more art than science」20。
  • 奖励假说是公理不是定理。 它经 Littman 建议写成了显式表述;目标能否真的都归约为标量信号最大化,书里没证,也证不了——这是全书的地基假设,值得知道它是有条件的5。
  • 折扣的现实含义含糊。 γ 通常被解释成「利率」或「兴趣衰减」,本书只在持续任务里用它防无穷;到了函数逼近的章节(第 10 章),作者会反过来宣布折扣在控制问题的定义里没有立足之地——此处先埋个记号。
  • MDP 框架覆盖不了所有决策学习问题,作者自己承认这是「广度与可处理性」的妥协;超出 MDP 的部分推给第 17 章21。

8. 可带走的​

  1. 奖励假说:一切目标=最大化一个标量信号的累积期望。全书建立在它上面;拿它当设计奖励时的警钟——你发的分,就是它的全部世界观。
  2. 奖励只定义「要什么」:别拿奖励教知识,中间目标发奖会养出「吃子不赢棋」的投机者。
  3. γ 是远视旋钮:1/(1−γ) 给了量感——γ=0.9 相当于看 10 步的账,γ=0.99 看 100 步。
  4. 值函数是「此后的一生」,不是眼前一口:A 格 8.8<10、B′ 反而占优,读表要读出这层。
  5. Bellman 方程:每个状态的值被钉在后继的值上;主走查里 0.225×3.0=0.675≈0.7 那一步,就是全书所有算法反复在做的事。
  6. 对 v* 贪心=最优:最优值函数把长程计算压缩成一步查表;q* 连查表都省了。
  7. 精确解三假设(模型已知/算力够/Markov)现实中基本凑不齐,双陆棋要算几千年——所以一切从近似开始。

9. 原文地图​

主题原书章原文位置
MDP 定位、动力学 pFinite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:15(搜「mathematically idealized」) · text/06-fm-finite-markov-decision-processes.txt:58(搜「dynamics of the MDP」)
Markov 性质是对状态的限制Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:88(搜「make a difference」)
边界=控制的边界Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:140(搜「changed arbitrarily」) · text/06-fm-finite-markov-decision-processes.txt:150(搜「absolute control」)
奖励假说Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:292(搜「reward hypothesis」)
只奖赢棋、不奖子目标Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:318(搜「subgoals」)
情节/持续、折扣、myopicFinite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:340(搜「terminal state」) · text/06-fm-finite-markov-decision-processes.txt:371(搜「discount rate」) · text/06-fm-finite-markov-decision-processes.txt:375(搜「myopic」)
回报递归、1/(1−γ)Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:388(搜「Gt+1」) · text/06-fm-finite-markov-decision-processes.txt:394(搜「constant +1」)
策略、vπ、qπFinite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:495(搜「mapping from states to probabilities」) · text/06-fm-finite-markov-decision-processes.txt:514(搜「state-value function」)
Bellman 方程Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:567(搜「Bellman equation for」)
网格世界与值表读法Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:677(搜「yield a reward」) · text/06-fm-finite-markov-decision-processes.txt:700(搜「best state to be in」) · text/06-fm-finite-markov-decision-processes.txt:702(搜「valued more than」)
最优策略、贪心即最优、q* 缓存Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:812(搜「partial ordering」) · text/06-fm-finite-markov-decision-processes.txt:910(搜「greedy with respect to」) · text/06-fm-finite-markov-decision-processes.txt:926(搜「caches」)
三假设、几千年Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:989(搜「rarely true」) · text/06-fm-finite-markov-decision-processes.txt:995(搜「thousands of years」)
常见状态优先Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:1065(搜「frequently encountered」)
Littman 与奖励假说出处Finite Markov Decision Processestext/06-fm-finite-markov-decision-processes.txt:1170(搜「Littman」)

Footnotes​

  1. 出处:「Finite Markov Decision Processes」第 58 段(text/06-fm-finite-markov-decision-processes.txt:58,搜「dynamics of the MDP」)。原文:「The function p defines the dynamics of the MDP」。 ↩

  2. 出处:「Finite Markov Decision Processes」第 93 段(text/06-fm-finite-markov-decision-processes.txt:93,搜「compute anything else」)。 ↩

  3. 出处:「Finite Markov Decision Processes」第 88 段(text/06-fm-finite-markov-decision-processes.txt:88,搜「make a difference」)。 ↩

  4. 出处:「Finite Markov Decision Processes」第 140 段(text/06-fm-finite-markov-decision-processes.txt:140,搜「changed arbitrarily」)与第 150 段(text/06-fm-finite-markov-decision-processes.txt:150,搜「absolute control」);魔方比喻在第 148 段(搜「Rubik」)。 ↩

  5. 出处:「Finite Markov Decision Processes」第 292 段(text/06-fm-finite-markov-decision-processes.txt:292,搜「reward hypothesis」)。出处注(第 1170 段,搜「Littman」)说明这个显式表述由 Michael Littman 建议。 ↩ ↩2

  6. 出处:「Finite Markov Decision Processes」第 318 段(text/06-fm-finite-markov-decision-processes.txt:318,搜「subgoals」)与第 355 段(搜「initial policy」,脚注 5)。「要什么/怎么做」的原话在第 322 段(搜「what you want achieved」)。 ↩ ↩2

  7. 出处:「Finite Markov Decision Processes」第 340 段(text/06-fm-finite-markov-decision-processes.txt:340,搜「terminal state」)与第 349 段(搜「continuing tasks」);无穷问题在第 353 段(搜「could easily be infinite」)。 ↩

  8. 出处:「Finite Markov Decision Processes」第 394 段(text/06-fm-finite-markov-decision-processes.txt:394,搜「constant +1」);公式 (3.10) 在第 396 段(搜「1」)。折扣定义在第 371 段(搜「discount rate」)。 ↩

  9. 出处:「Finite Markov Decision Processes」第 388 段(text/06-fm-finite-markov-decision-processes.txt:388,搜「Gt+1」);「不能同时成立」在第 482 段(搜「not both」)。 ↩

  10. 出处:「Finite Markov Decision Processes」第 495 段(text/06-fm-finite-markov-decision-processes.txt:495,搜「mapping from states to probabilities」)。 ↩

  11. 出处:「Finite Markov Decision Processes」第 514 段(text/06-fm-finite-markov-decision-processes.txt:514,搜「state-value function」)与第 515 段(搜「action-value function」)。 ↩

  12. 出处:「Finite Markov Decision Processes」第 543 段(text/06-fm-finite-markov-decision-processes.txt:543,搜「fundamental property」)与第 567 段(搜「Bellman equation for」)。 ↩

  13. 出处:「Finite Markov Decision Processes」第 677 段(text/06-fm-finite-markov-decision-processes.txt:677,搜「yield a reward」)(A→+10、B→+5 的规则)与第 690 段(搜「equiprobable random policy」);值表数字见图 3.2(第 680-686 段,该区排版有乱码,数字以图为准);A 的值低于 10 在第 700 段(text/06-fm-finite-markov-decision-processes.txt:700,搜「less than its」),B 的解读在第 702 段(搜「valued more than」)。主走查的邻值(2.3、0.4、−0.4、0.7)来自第 708 段的习题 3.14(搜「neighboring states」)。防呆提示:该行清洗文本里 −0.4 的负号系转码丢失(显示为「+0.4, 0.4」),回核时以上四个邻值一律以图 3.2 为准。 ↩ ↩2

  14. 出处:「Finite Markov Decision Processes」第 812 段(text/06-fm-finite-markov-decision-processes.txt:812,搜「partial ordering」)与第 816 段(搜「optimal policy」)。 ↩

  15. 出处:「Finite Markov Decision Processes」第 910 段(text/06-fm-finite-markov-decision-processes.txt:910,搜「greedy with respect to」)与第 922 段(搜「one-step-ahead search」)。 ↩

  16. 出处:「Finite Markov Decision Processes」第 926 段(text/06-fm-finite-markov-decision-processes.txt:926,搜「caches」)。 ↩

  17. 出处:「Finite Markov Decision Processes」第 899 段(text/06-fm-finite-markov-decision-processes.txt:899,搜「unique solution」)。 ↩

  18. 出处:「Finite Markov Decision Processes」第 989 段(text/06-fm-finite-markov-decision-processes.txt:989,搜「rarely true」)与第 995 段(text/06-fm-finite-markov-decision-processes.txt:995,搜「thousands of years」)。 ↩

  19. 出处:「Finite Markov Decision Processes」第 1065 段(text/06-fm-finite-markov-decision-processes.txt:1065,搜「frequently encountered」);Tesauro 的例子在第 1059 段(搜「exceptional skill」)。 ↩

  20. 出处:「Finite Markov Decision Processes」第 169 段(text/06-fm-finite-markov-decision-processes.txt:169,搜「art than science」)。 ↩

  21. 出处:「Finite Markov Decision Processes」第 19 段(text/06-fm-finite-markov-decision-processes.txt:19,搜「tension between breadth」)。 ↩