Part V · 第 20 章 强化学习 · 20.1

MDP 与 Bellman 方程

机器人一步一步地做决定：看到状态，选一个动作，拿到一份奖励，然后世界（带着随机性）把它送到下一个状态。马尔可夫决策过程 (MDP) 用五样东西把这件事写清楚，Bellman 方程把"从这里出发，长期平均能拿多少奖励"写成一个自洽的一步递推。6.12 节已经在已知的格子世界上用值迭代求过代价到终点；这一节换成强化学习的语言，并往前走：回报与折扣、策略、状态价值 V 与动作价值 Q、Bellman 期望方程与最优方程、策略迭代，再看机器人看不全状态 (POMDP) 时怎么办，以及奖励应该怎样设计。

约 50 分钟 前置：6.12 动态规划 · 4.7 贝叶斯滤波 6 个交互

    1为什么机器人需要它

    一台四足机器人在仿真里学走路，一只机械手学着把方块转到指定朝向，一台移动机器人学会绕开湿滑的地面去充电：这些都是强化学习 (RL)。它们的共同点是：没有人告诉机器人每一步"正确的动作"是什么，只有一个奖励信号说明结果好不好，而且好坏往往要过很多步才显现。

    要谈论"学到一个好的策略"，先得说清楚：状态是什么，能做哪些动作，世界怎样回应，什么叫"好"。马尔可夫决策过程 (MDP) 就是这套共同语言。本章后面的每一个算法，Q-learning 和 DQN（20.2）、策略梯度（20.3）、PPO 和 SAC（20.4）、离线 RL（20.5），以及 Part VI 的机器人 RL，都是在 MDP 上做事，并且都在用Bellman 方程：它们或者用采样去逼近 Bellman 最优方程的不动点，或者用 Bellman 期望方程估计"这个动作比平均好多少"。

    6.12 节已经讲过动态规划的核心：最优性原理、值迭代、带打滑的悬崖行走，以及值迭代作为压缩映射的收敛性。那里用的是代价和 \(\min\)，并且假设环境模型 \(P(s'\mid s,a)\) 已知。本节换成 RL 的习惯（奖励和 \(\max\)，奖励 = 负的代价），把 6.12 只顺带一提的几件事讲透：回报和折扣到底意味着什么，动作价值 Q 为什么比 V 更有用，固定策略的价值怎么求（策略评估）以及怎样一步步改进它（策略迭代），机器人看不全状态时会发生什么，以及奖励写错了会怎样。

    2直觉：一台在湿滑地面上找充电桩的机器人

    本节的例子贯穿全课：一台仓库机器人在 8×5 的地面上，从左边的 S 出发去右边的充电桩。灰色格子是货架，走不进去；最下面一排中间四格是楼梯口，掉下去奖励 −10，回合结束；进入充电桩奖励 +10，回合结束；其余每走一步奖励 −1（耗电、耗时）。地面是湿的：命令"向右"时，机器人以概率 \(1-p\) 真的向右走，以 \(p/2\) 的概率滑向左右两个垂直方向之一（向上或向下），和 6.12 的打滑悬崖是同一个噪声模型。撞到墙或货架就原地不动。

    把它写成 MDP，需要五样东西：

    \(\mathcal S\)状态集合：36 个可走的格子（其中 5 个是终止状态：楼梯 4 格和充电桩）。
    \(\mathcal A\)动作集合：上、右、下、左四个命令。
    \(P(s'\mid s,a)\)转移概率：命令 \(a\) 之后落到 \(s'\) 的概率（打滑模型）。
    \(r(s,a,s')\)奖励：进充电桩 +10，掉楼梯 −10，其余每步 −1。
    \(\gamma\)折扣因子：本例取 0.95，下一节专门讨论它。

    "马尔可夫"指的是：下一个状态的分布只取决于当前状态和动作，与之前怎么走到这里无关。机器人每做一次决定，就产生一段经验 \((s_t,a_t,r_{t+1},s_{t+1})\)；一个回合 (episode) 是从起点到终止状态的整段轨迹。我们关心的不是某一步的奖励，而是整个回合的折扣回报：

    $$ G_0=r_1+\gamma\,r_2+\gamma^2 r_3+\cdots=\sum_{t=0}^{T-1}\gamma^{t}\,r_{t+1} $$

    如果一路都没打滑，机器人走 8 步到充电桩：前 7 步各 −1，最后一步 +10，回报是 \(-(1+\gamma+\cdots+\gamma^6)+10\gamma^7=0.95\)。可地面是湿的，同一个策略每次跑出来的轨迹不一样，回报也不一样：回报是一个随机变量。一个策略 \(\pi\) 从状态 \(s\) 出发的价值 \(V^\pi(s)\) 就是这个随机变量的期望。下面的图让你一回合一回合地跑，再一口气跑 1000 回合，看平均回报怎样逼近精确的 \(V^\pi(S)\)。

    FIG 1回合与回报：同一个策略，每次结果不同
    1000 回合的回报直方图
    琥珀色圆点是机器人，青色折线是本回合走过的路，紫色小点标出打滑的那几步。格子的蓝色越浓，所选策略在该格的精确价值 \(V^\pi\) 越高。三种策略："最优"是对当前 \(p\) 求出的 \(\pi^\star\)；"最短路"是按无噪声 (\(p=0\)) 规划、在湿地上照走的策略；"随机"每步等概率选四个方向之一。直方图里青色柱是 1000 个回合的回报分布，琥珀色竖线是精确的 \(V^\pi(S)\)，紫色虚线是样本均值，灰色带是均值 ±2 倍标准误。回合超过 200 步会被截断。
    试一试
    • 用"最优"策略按"跑一回合"，直到有两个回合的回报不一样（有一回合打滑了）。注意掉下楼梯的那些回合。
    • 分别为两种不同的策略按"1000 回合"：样本均值落在精确 \(V^\pi(S)\) 附近吗？在 \(p=0.2\) 时，"最优"和"最短路"的差距（约 0.14）和标准误（约 0.17）谁大？
    核心洞见

    价值不是某一次的结果，而是期望。在 \(p=0.2\) 时，最优策略从 S 出发的精确价值是 −5.07，可单个回合的回报从 −15 以下一直分布到 0.95；默认种子下，1000 回合的均值是 −5.15，标准误约 0.17，比"最优"与"最短路"两个策略的真实差距（−5.07 对 −5.21）还大。只靠跑回合取平均来比较策略需要很多样本，这正是后面 RL 方法要用 Bellman 方程"借用"相邻状态估计的原因（20.2 的 TD 学习）。

    3折扣因子 \(\gamma\)：机器人能看多远

    \(t\) 步之后的奖励要乘上 \(\gamma^t\)。为什么要折扣？有三种互相补充的理解。数学上：对不会结束的任务，\(\gamma<1\) 保证无穷和有限，奖励不超过 \(r_{\max}\) 时 \(|G|\le r_{\max}/(1-\gamma)\)。偏好上：早拿到的奖励比晚拿到的更好。概率上：可以把 \(\gamma\) 看成"每一步之后任务还在继续"的概率，\(1-\gamma\) 是每步意外终止的概率。

    权重 \(\gamma^t\) 加起来是 \(1/(1-\gamma)\)，所以 \(1/(1-\gamma)\) 常被叫作有效时域：\(\gamma=0.9\) 大约看 10 步，\(\gamma=0.99\) 大约看 100 步。下图是一条走廊：左端是一个慢速充电桩（+3），只需 3 步；右端是快速充电桩（+10），要走 7 步。机器人的选择取决于 \(\gamma\)：从第 \(s\) 格向左的价值是 \(3\gamma^{s-1}\)，向右是 \(10\gamma^{9-s}\)。

    FIG 2近处的小奖励还是远处的大奖励
    上半部分：走廊里每一格上方的蓝色柱是最优价值 \(V^\star(s)\)，格子里的箭头是最优方向；琥珀色圆点是机器人，可以拖动到别的格子。下半部分：紫色柱是第 \(t\) 步奖励的权重 \(\gamma^t\)（\(t=0\ldots39\)），青色虚线标出有效时域 \(1/(1-\gamma)\)（超过 40 时画在最右端）。走廊是确定性的，没有打滑，每步奖励为 0。
    • 机器人在第 3 格时，慢慢降低 \(\gamma\)，找到它从"去 +10"改为"去 +3"的那个 \(\gamma\)（解 \(3\gamma^{2}=10\gamma^{6}\)，即 \(\gamma=0.3^{1/4}\approx0.74\)）。
    \(\gamma\) 是问题的一部分

    同一个环境，不同的 \(\gamma\) 给出不同的"最优"策略：\(\gamma\) 不只是让求和收敛的技术参数，它定义了你想要什么。把 \(\gamma\) 调到 0.86 以上，走廊里每一格都去 +10（第 1 格要求 \(10\gamma^8>3\)）；把 \(\gamma\) 调到 0，机器人只看下一步的奖励，除了紧挨充电桩的两格，所有格子的价值都是 0。机器人里还要把 \(\gamma\) 和控制频率一起考虑：同样 \(\gamma=0.99\)，50 Hz 的策略大约看 100 步，即 2 秒；如果把控制频率提高到 200 Hz 而不改 \(\gamma\)，它就只能看 0.5 秒。

    4动手：V、Q 与一步回溯

    两个价值函数是 RL 的核心对象：

    • 状态价值 \(V^\pi(s)\)：从 \(s\) 出发、一直按 \(\pi\) 行动的期望回报。
    • 动作价值 \(Q^\pi(s,a)\)：在 \(s\) 先做动作 \(a\)（不管 \(\pi\) 会选什么），之后再按 \(\pi\) 行动的期望回报。

    它们由同一个"一步回溯"联系起来。在 \(s\) 做 \(a\)：世界按 \(P(s'\mid s,a)\) 把机器人送到某个 \(s'\)，拿到 \(r(s,a,s')\)，从 \(s'\) 往后的期望回报是 \(V^\pi(s')\)。对所有可能的 \(s'\) 取平均：

    $$ Q^\pi(s,a)=\sum_{s'}\hl{pss}{P(s'\mid s,a)}\,\Big[\,r(s,a,s')+\gamma\,\hl{vnext}{V^\pi(s')}\,\Big],\qquad V^\pi(s)=\sum_a\hl{pi}{\pi(a\mid s)}\,\hl{qsa}{Q^\pi(s,a)} $$

    第二个式子说：状态的价值是它各个动作价值按策略加权的平均。把两个式子合在一起，就得到 Bellman 期望方程，它对任何策略都成立。对最优策略，平均换成最大：\(V^\star(s)=\max_a Q^\star(s,a)\)，这就是 Bellman 最优方程，也就是 6.12 节值迭代所解的方程（换成奖励和 \(\max\)）。

    下图把每个格子分成四个三角形，每个三角形是一个动作的 \(Q(s,a)\)。点击格子里的某个三角形，就选中了那个 \((s,a)\)：图上画出它的三个可能结果和概率，右侧把 \(Q(s,a)\) 拆成每个结果的贡献。

    FIG 3Q 值地图与一步 Bellman 回溯
    三角形的蓝色越浓，该动作的 \(Q\) 越高（色标对所有格子相同，从 −20 到 +10）；格子足够大时写出数值。"最优"模式显示 \(Q^\star\)，琥珀色描边的三角形是每格的最优动作，箭头是 \(\pi^\star\)；"随机策略"模式显示均匀随机策略的 \(Q^\pi\)，每格画四个短箭头。选中的格子有琥珀色粗框；琥珀色箭头从它指向三个可能的结果（实线是命令的方向，虚线是打滑），线越粗概率越大，原地不动画成小圆圈；结果格子用青色框出。
    • 点击楼梯正上方某一格的下三角（命令"向下"）：右侧的分解里，哪一项让这个 \(Q\) 变得这么低？
    • 切到"随机策略"，先猜：价值最低的格子是紧挨楼梯的，还是离一切都远的？然后点击那个价值最低的格子验证。
    • 回到"最优"，把 \(p\) 调到 0.45 或更高，找到最优动作径直驶向楼梯的那一格并点击它。看它的 \(V^\star\)：为什么机器人宁可掉下去？
    为什么 Q 比 V 更有用

    只知道 \(V^\star\)，要决定动作还得在每个动作上做一次回溯 \(\sum_{s'}P(s'\mid s,a)[r+\gamma V^\star(s')]\)，这需要模型 \(P\) 和 \(r\)。知道 \(Q^\star\)，直接取 \(\arg\max_a Q^\star(s,a)\) 就行，不需要模型。真实机器人通常不知道 \(P\)（地面多滑？物体多重？），所以无模型方法学的是 Q（20.2 的 Q-learning、DQN，20.4 的 SAC 的 critic）。代价是 Q 表比 V 表大 \(|\mathcal A|\) 倍，连续动作时 \(\arg\max_a\) 本身就成了一个优化问题。

    "随机策略"模式里有一个有趣的现象：把 \(p\) 从 0 拖到 0.5，随机策略的价值一点都不变（S 处始终是 −15.98）。原因是打滑把命令方向换成两个垂直方向之一，而均匀随机的命令经过这种对称的打滑，仍然是均匀随机的四个方向。最低价值的格子也不在楼梯边，而在左上角（约 −17.99）：随机游走的机器人在那里要漫游很久才碰到任何终止状态，每步都付 −1，下限是 \(-1/(1-\gamma)=-20\)；楼梯边的格子反而很快以 −10 结束。

    5策略评估与策略迭代

    6.12 节的值迭代每一轮对所有状态做一次"取最大"的回溯，直到价值收敛。另一条路线是策略迭代（Howard, 1960），它在两件事之间交替：

    1. 策略评估：对当前固定的 \(\pi\)，求出 \(V^\pi\)。这时 Bellman 期望方程里没有 \(\max\)，是一个线性方程组：每个非终止状态一个未知数、一个方程，\(V^\pi=\mathbf r^\pi+\gamma P^\pi V^\pi\)，可以直接解 \((I-\gamma P^\pi)V^\pi=\mathbf r^\pi\)，也可以反复用期望回溯扫描。
    2. 策略改进：在每个状态改选 \(\arg\max_a Q^\pi(s,a)\)（对 \(V^\pi\) 贪心）。策略改进定理保证新策略在每个状态都不比旧策略差。

    确定性策略只有有限个（这里是 \(4^{31}\) 个），每轮要么严格变好、要么不再变化，所以策略迭代一定在有限步内停在最优策略上，而且实际上通常只要很少几轮。

    FIG 4策略迭代：评估、改进、再评估
    离最优价值的距离 \(\|V-V^\star\|_\infty\)（对数），横轴是迭代 / 扫描次数
    左：当前策略的箭头，以及最近一次评估得到的 \(V^\pi\)（蓝色越浓越高，数字是 \(V^\pi\)）；上一次改进中改变了动作的格子有琥珀色框。点击格子把它的箭头顺时针转 90°，用来自己设定初始策略（这会重新开始一轮策略迭代）。右：琥珀色点是第 \(i\) 次评估的 \(\|V^{\pi_i}-V^\star\|_\infty\)，青色线是从 \(V=0\) 出发的值迭代第 \(k\) 次扫描的误差，紫色虚线是压缩映射给出的上界 \(\gamma^k\|V^\star\|_\infty\)。打滑概率固定为 \(p=0.2\)。
    • 从初始策略"全部向上"出发（按"重置"），交替按"评估"和"改进"，直到改进不再改变任何动作。一共评估了几次？\(V^\pi(S)\) 的序列是单调的吗？
    • 按"重置"后，点击至少 3 个格子，把它们的箭头转向楼梯或货架，造一个糟糕的初始策略，再按"运行到底"：结果还是同一个最优策略吗？

    在默认的 \(\gamma=0.95\) 下，从"全部向上"出发，\(V^\pi(S)\) 依次是 −20.00、−11.36、−11.33、−5.81、−5.68、−5.11、−5.07：7 次评估，前 6 次改进都改变了一些动作，第 7 次什么也不改，停止。第一个值恰好约等于 \(-1/(1-\gamma)=-20\)，因为"一直向上"的机器人会顶着上墙永远付 −1。对比右图里的青色线：值迭代要扫描 36 次误差才降到 \(10^{-6}\) 以下（虽然它的贪心策略从第 9 次扫描起就已经是最优的了）。压缩映射的上界（紫色虚线）要 314 次，它很保守：终止状态会吸收概率，实际收敛比 \(\gamma^k\) 快得多。把 \(\gamma\) 调到 0.99，上界变成 1600 次扫描，值迭代实际要 41 次，策略迭代仍然是 7 次评估。代价是每次评估要解一个 \(31\times31\) 的线性方程组：状态多时这很贵，所以实践中常用折中的"修正策略迭代"：每次只做几次评估扫描就改进。

    后面的 RL 都是"广义策略迭代"

    "估计当前策略有多好"和"让策略对估计更贪心"这两件事交替（或同时）进行，Sutton 和 Barto 称之为广义策略迭代。Actor-critic 方法（20.4）里，critic 就是一个用样本做的、不精确的策略评估，actor 的更新就是一个温和的、只走一小步的策略改进。区别只是：没有模型，评估用采样；状态太多，价值用神经网络表示。

    6看不全状态：POMDP 与信念

    前面的机器人知道自己在哪一格。真实机器人看到的是观测：相机图像、激光点云、关节编码器读数，而不是"状态"本身。如果观测里缺了做决定需要的信息（只有一帧图像，看不出物体在往哪边动；不知道杯子在左边桌上还是右边桌上），问题就成了部分可观测 MDP (POMDP)：在 MDP 之外再加一个观测模型 \(O(o\mid s')\)。

    关键的想法是：虽然看不到状态，但可以维护一个对状态的信念 \(b(s)\)，即概率分布。每做一个动作、收到一个观测，就用 4.7 节的贝叶斯滤波更新它。信念本身满足马尔可夫性，所以 POMDP 等价于一个以信念为状态的 MDP（"信念 MDP"），Bellman 方程照样成立，只不过状态变成了一个连续的概率分布。

    下图是最小的例子：机器人在 T 形路口，要把零件送到工位，工位在左边或右边，它不确定是哪边。信念 \(b=P(L)\)，L 表示工位在左边。三个动作：向左或向右直接送（送对 +10，送错 −10，回合结束），或者先看一眼（代价 \(c\)，相机分类器以准确率 \(q\) 报告"左"或"右"，然后更新信念）。机器人最多做 \(H\) 次决定，最后一次必须送出去。

    $$ \hl{belief}{b'_L}=\frac{q\,b}{q\,b+(1-q)(1-b)},\qquad V_h(b)=\max\Big\{\,10(2b-1),\ \ 10(1-2b),\ \ -c+\sum_{o}P(o\mid b)\,V_{h-1}(b'_o)\Big\},\qquad V_1(b)=10\,|2b-1| $$

    这里 \(b'_L\) 是相机报告"左"之后的信念（报告"右"时同理得到 \(b'_R\)），\(P(o\mid b)\) 是在当前信念下收到每种报告的概率，例如 \(P(L\mid b)=q\,b+(1-q)(1-b)\)。\(V_h\) 是还剩 \(h\) 次决定时的最优价值。

    FIG 5在信念上做 Bellman 回溯：什么时候值得先看一眼
    横轴是信念 \(b=P(L)\)，纵轴是价值。两条紫色虚线是立即送出的价值 \(10(2b-1)\) 与 \(10(1-2b)\)，它们的上包络就是 \(V_1\)；淡紫色线是 \(V_2,\ldots,V_{H-1}\)，琥珀色粗线是 \(V_H\)。青色带是"先看一眼"最优的信念区间。拖动琥珀色圆点改变当前信念。按"模拟一回合"：按 \(b\) 抽一个真实工位，按最优策略行动，下方的编号点是每一步之后的信念。
    • 默认 \(b=0.9\) 时机器人直接向左送。把信念拖进青色带，让"先看一眼"成为最优动作。在默认设置下，这个区间大约是 \(0.152<b<0.848\)。
    • 在 \(H\ge2\) 时降低相机准确率 \(q\)，直到"先看一眼"在任何信念下都不再值得（青色带消失）。在 \(c=1\) 时这发生在 \(q\le0.55\)：只有当 \(10(2q-1)>c\)，看一眼带来的期望收益才抵得上它的代价。

    注意 \(V_h(b)\) 的形状：它是若干条直线的上包络，即分段线性且凸。这对有限时域 POMDP 普遍成立（Smallwood & Sondik, 1973），基于点的 POMDP 求解器正是利用了这个结构。凸性有直观含义：信念越确定（越靠近两端），价值越高；在中间，信息本身就有价值，"看一眼"是一个纯粹为了获取信息而做的动作。完全可观测的 MDP 里永远不会出现这种动作。

    机器人里的部分可观测性

    精确求解 POMDP 只在小问题上可行（SARSOP 等基于点的求解器能处理中等规模的离散问题）。深度 RL 的做法更粗糙也更实用：把最近几帧观测和上一个动作一起输入策略（帧堆叠），或者用循环网络、状态空间模型（17.2）压缩历史，让网络自己学一个"隐式信念"。足式机器人看不到地面摩擦和负载质量，这些也可以看成隐藏状态；23.1 会讲怎样在仿真里用"特权信息"训练教师策略，再让只看本体感觉历史的学生策略模仿它。

    7再看数学

    提示：把鼠标悬停在公式中带底色的符号上，FIG 2、FIG 3、FIG 5、FIG 6 中对应的元素会被高亮。

    MDP、策略与回报

    一个 MDP 是 \((\mathcal S,\mathcal A,P,r,\gamma)\)，外加初始状态分布 \(\rho_0\)。马尔可夫性：\(P(s_{t+1}\mid s_t,a_t,s_{t-1},a_{t-1},\ldots)=P(s_{t+1}\mid s_t,a_t)\)。策略 \(\pi(a\mid s)\) 是给定状态时动作的分布（确定性策略是它的特例 \(a=\pi(s)\)）。从时刻 \(t\) 起的回报满足一个一步递推，它是所有 Bellman 方程的来源：

    $$ G_t=r_{t+1}+\hl{gam}{\gamma}\,r_{t+2}+\hl{gam}{\gamma^2}\,r_{t+3}+\cdots=r_{t+1}+\gamma\,G_{t+1},\qquad V^\pi(s)=\mathbb E_\pi\big[G_t\mid s_t=s\big],\qquad Q^\pi(s,a)=\mathbb E_\pi\big[G_t\mid s_t=s,\,a_t=a\big] $$

    回合式任务里，终止状态是吸收状态，之后奖励恒为 0，所以终止状态的价值为 0。和 6.12 的对应关系：代价 \(c=-r\)，\(\min\) 换成 \(\max\)，代价到终点 \(=-V\)。

    Bellman 期望方程：一个线性方程组

    对 \(G_t=r_{t+1}+\gamma G_{t+1}\) 两边按 \(\pi\) 和 \(P\) 取期望，得到

    $$ V^\pi(s)=\sum_a\hl{pi}{\pi(a\mid s)}\sum_{s'}\hl{pss}{P(s'\mid s,a)}\big[r(s,a,s')+\gamma\,\hl{vnext}{V^\pi(s')}\big]\quad\Longleftrightarrow\quad V^\pi=\mathbf r^\pi+\gamma P^\pi V^\pi\quad\Longleftrightarrow\quad V^\pi=(I-\gamma P^\pi)^{-1}\mathbf r^\pi $$

    其中 \(P^\pi_{ss'}=\sum_a\pi(a\mid s)P(s'\mid s,a)\) 是策略诱导的马尔可夫链，\(\mathbf r^\pi(s)\) 是一步期望奖励。\(P^\pi\) 每行之和为 1（只保留非终止状态时不超过 1），所以 \(\|\gamma P^\pi\|_\infty\le\gamma<1\)，\(I-\gamma P^\pi\) 一定可逆：任何策略的价值都唯一存在。直接求逆要 \(O(|\mathcal S|^3)\)；迭代 \(V\leftarrow\mathbf r^\pi+\gamma P^\pi V\) 每次 \(O(|\mathcal S|^2)\)，并以 \(\gamma\) 为比率收敛（同 6.12 的压缩论证）。\(Q\) 也有同样的方程：\(Q^\pi(s,a)=\sum_{s'}P(s'\mid s,a)\big[r+\gamma\sum_{a'}\pi(a'\mid s')Q^\pi(s',a')\big]\)。

    Bellman 最优方程

    $$ V^\star(s)=\max_a\sum_{s'}P(s'\mid s,a)\big[r+\gamma V^\star(s')\big],\qquad Q^\star(s,a)=\sum_{s'}P(s'\mid s,a)\Big[r+\gamma\max_{a'}Q^\star(s',a')\Big],\qquad \pi^\star(s)=\arg\max_a Q^\star(s,a) $$

    因为有 \(\max\)，这是一个非线性方程组，不能一次解出，只能迭代（值迭代）或在策略空间里搜索（策略迭代）。对有限 MDP 和 \(\gamma<1\)，有一个基本事实（见 Puterman 的教材）：存在一个确定性、平稳（不随时间变化）的策略，它在所有状态同时最优。所以只需在 \(|\mathcal A|^{|\mathcal S|}\) 个确定性策略中找，不必考虑随机或依赖历史的策略。Q 版本的方程里 \(\max\) 在期望里面，样本 \((s,a,r,s')\) 就能给出它的一个无偏的一步目标 \(r+\gamma\max_{a'}Q(s',a')\)：这就是 20.2 中 Q-learning 的出发点。

    策略改进定理

    设 \(\pi'(s)=\arg\max_a Q^\pi(s,a)\)。那么对每个 \(s\)，\(Q^\pi(s,\pi'(s))\ge V^\pi(s)\)。把这个不等式沿着 \(\pi'\) 的轨迹反复展开：

    $$ V^\pi(s)\le Q^\pi(s,\pi'(s))=\mathbb E\big[r_{1}+\gamma V^\pi(s_{1})\big]\le\mathbb E\big[r_{1}+\gamma\,Q^\pi(s_1,\pi'(s_1))\big]\le\cdots\le\mathbb E_{\pi'}\Big[\sum_t\gamma^t r_{t+1}\Big]=V^{\pi'}(s) $$

    若某轮改进后 \(\pi'=\pi\)，则 \(V^\pi\) 满足最优方程，\(\pi\) 就是最优的。差值 \(A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)\) 叫优势函数：贪心改进就是"选优势为正的动作"。20.3 的策略梯度和 20.4 的 PPO 都是沿着优势的方向，把策略往好的动作推一小步。

    POMDP 与信念 MDP

    POMDP 是 \((\mathcal S,\mathcal A,P,r,\Omega,O,\gamma)\)，\(O(o\mid s',a)\) 是到达 \(s'\) 后看到观测 \(o\) 的概率。信念按贝叶斯滤波更新（预测一步，再用观测修正），归一化常数是 \(P(o\mid b,a)\)：

    $$ \hl{belief}{b'(s')}=\frac{O(o\mid s',a)\sum_s P(s'\mid s,a)\,b(s)}{P(o\mid b,a)},\qquad V(b)=\max_a\Big[\sum_s b(s)\,r(s,a)+\gamma\sum_o P(o\mid b,a)\,V(b'_{a,o})\Big] $$

    信念是 \(|\mathcal S|-1\) 维单纯形里的一个点，所以即便原来只有两个状态，信念 MDP 也有连续的状态空间。有限时域时 \(V\) 是有限条"\(\alpha\) 向量"直线（超平面）的上包络 \(V(b)=\max_i\alpha_i^\top b\)，FIG 5 画的正是两个状态时的情形。

    基于势函数的奖励塑形

    在奖励上加一项 \(F(s,s')=\gamma\,\hl{phi}{\Phi(s')}-\hl{phi}{\Phi(s)}\)，其中 \(\Phi\) 是任意的状态函数（终止状态取 \(\Phi=0\)）。沿任何轨迹，额外的回报会相消（望远镜求和）：\(\sum_t\gamma^t F_t=-\Phi(s_0)\)。所以对每个动作 \(Q'(s,a)=Q(s,a)-\Phi(s)\)：同一状态里所有动作被减去同一个数，排序不变，最优策略不变（Ng, Harada & Russell, 1999）。他们还证明了，在不知道环境细节时，这是唯一能保证最优策略不变的加法塑形形式。

    8机器人中的它：怎样把任务写成 MDP，尤其是奖励

    把真实机器人任务写成 MDP，每一项都是工程决定。状态 / 观测：足式机器人通常用关节角 \(\mathbf q\)、关节速度、机身姿态与角速度（IMU）、上一个动作和速度指令；操作任务常加上相机图像。动作：很少直接输出力矩，更常见的是输出关节目标位置，交给底层的 PD 控制器（13.1）以更高的频率跟踪。终止：机身触地、关节超限，或者到达时间上限。奖励：这是最难的一项。

    稀疏奖励（只在成功时给 +1）最诚实，但机器人在随机探索时几乎永远碰不到成功；于是人们加上"引导"项：离目标越近奖励越多，速度跟踪得越准奖励越多，力矩、动作变化率越大惩罚越多。每加一项，都可能悄悄改变"最优"的含义。前面 FIG 3 已经出现过一次：每步 −1、楼梯只罚 −10，于是在 \(p\ge0.45\) 时，楼梯左边那一格（最下排）的最优动作是径直驶向楼梯，因为对它来说"结束"比"继续受罚"更划算；在 \(p=0.2\) 时最优策略从 S 出发掉下楼梯的概率也高达 33%。如果真的有楼梯，−10 显然写得太便宜了。下图看另一种典型错误。

    FIG 6奖励塑形：会被"钻空子"的奖励，与不会的
    机器人从 S 出发去充电桩 G（+10，回合结束），中间隔着一堵墙，只能从下面绕过去；地面不打滑，\(\gamma=0.95\)，其余每步奖励为 0（稀疏）。"接近奖励"每步额外给 \(w\,(1-d(s')/d_{\max})\)，\(d\) 是到 G 的直线距离；"势函数塑形"每步额外给 \(\gamma\Phi(s')-\Phi(s)\)，\(\Phi(s)=-w\,d(s)/d_{\max}\)。蓝色越浓表示在当前奖励下 \(V^\star\) 越高（色标按当前模式的最小、最大值归一化）。琥珀色线是从 S 按贪心策略走出的路线；红色圆圈表示路线停在那里原地打转，永远不进充电桩。
    • 切到"接近奖励"，增大 \(w\)，直到机器人不再进入充电桩，而是停在旁边一直领奖励（\(w\) 约 0.56 以上）。读出它的"真实回报"（只按稀疏奖励计算）。
    • 保持 \(w\ge0.6\)，切到"势函数塑形"：路线和稀疏奖励时完全一样吗？\(V^\star(S)\) 差了多少，是否等于 \(-\Phi(S)\)？

    "接近奖励"的毛病在于它是每一步都能领的正奖励：停在 G 旁边，每步领约 \(0.894\,w\)，永远领下去值 \(0.894\,w/(1-\gamma)\approx17.9\,w\)，一旦超过进门的 +10，"永远不进门"就成了最优。机器人没有错，它精确地优化了我们写下的东西：这叫奖励钻空子 (reward hacking) 或"规格博弈"。势函数塑形则是一个"差分"：靠近目标时得到的，离开时会如数还回去，绕圈不赚钱，所以最优策略不变。

    真实系统里

    足式机器人。大规模并行仿真里训练 ANYmal 等四足机器人行走的工作（例如 Rudin 等, CoRL 2021），奖励是十项左右的加权和：跟踪指令的线速度和角速度、鼓励迈大步的“腾空时间”（正项），以及对力矩、关节加速度、动作变化率、机身碰撞等的惩罚（负项），再加上"机身触地即终止"。每一项的权重都要调，23.1 会详细讨论。操作。许多抓取、插装任务干脆用稀疏的成功奖励，再靠演示数据或"事后经验回放"(HER, Andrychowicz 等, 2017) 解决探索问题。接口。常用的 Gymnasium 接口 env.step(a) 返回 (obs, reward, terminated, truncated, info)，把真正的终止 (terminated) 和到时截断 (truncated) 分开，后者不应当作 \(V=0\) 处理（见误区 1）。折扣。深度 RL 库里 \(\gamma\) 的常见默认值是 0.99（例如 Stable-Baselines3 的 PPO 和 SAC）。如果奖励本身很难写，可以从演示或人的偏好里学奖励：见 20.6。

    9常见误区

    误区 1：把"到时截断"当成"终止"

    训练时每个回合常被限制在若干步（FIG 1 是 200 步）。机器人在第 200 步被叫停，并不是到了终止状态：从那里出发的价值并不是 0。如果在 Bellman 目标里把它当成终止（\(r+\gamma\cdot0\)），就等于告诉学习器"时间一到世界就毁灭"，价值会被系统性低估，而且状态里没有时间时，同一个状态有时被当成终止、有时不是，问题就不再是马尔可夫的。正确做法：真终止用 \(r\)，截断仍用 \(r+\gamma V(s')\) 自举（Pardo 等, 2018），这正是 Gymnasium 区分 terminated 和 truncated 的原因。

    误区 2：以为加奖励项"只会帮忙"

    每一项奖励都会改变最优策略。每步都能领的正奖励会让机器人不愿结束（FIG 6 的接近奖励）；每步都罚的负奖励加上便宜的终止，会让机器人想尽快结束，哪怕是以失败的方式（FIG 3 在 \(p\ge0.45\) 时驶向楼梯）。回合式任务里，给每步奖励加一个常数也会改变最优策略。只有势函数形式 \(\gamma\Phi(s')-\Phi(s)\) 能保证不改变最优策略。

    误区 3：只有 V 就想选动作

    "走向 \(V\) 最高的邻居"只在确定性、且你知道每个动作会到哪里时才对。有打滑时，要比的是 \(\sum_{s'}P(s'\mid s,a)[r+\gamma V(s')]\)，这需要模型。FIG 3 里楼梯旁的格子就是例子：向下一格的价值可能很高，但"命令向下"的 Q 值要把打滑和楼梯算进去。没有模型就学 Q，或者同时学一个策略（actor）。

    误区 4：观测不是马尔可夫的却浑然不觉

    把单帧图像当状态，速度就丢了；传感器和执行器有 20 ms 延迟，当前观测就不能决定下一步会发生什么；摩擦、负载看不见。这时 Bellman 方程的前提不成立，学到的价值和策略会出现奇怪的平均效应。补救：把最近几次观测和动作一起作为输入，用循环网络，或者在仿真里随机化这些隐藏量并让策略从历史中推断它们（POMDP 的思路）。

    误区 5：\(\gamma\) 随手设、和控制频率脱节

    有效时域 \(1/(1-\gamma)\) 是以步计的。\(\gamma\) 太小，机器人短视（FIG 2 里只去近的 +3）；\(\gamma\) 太接近 1，价值的数值范围变大，基于采样的估计方差变大，学习变慢。改变控制频率时要相应改变 \(\gamma\)：保持以秒计的时域不变，新的步长为 \(\Delta t'\) 时需要 \(\gamma'=\gamma^{\Delta t'/\Delta t}\)。

    10小练习

    1. 在 \(s\) 做动作 \(a\)：以 0.8 的概率到 \(s_1\)（\(r=-1\)，\(V(s_1)=5\)），以 0.1 的概率到 \(s_2\)（\(r=-1\)，\(V(s_2)=2\)），以 0.1 的概率掉下楼梯（\(r=-10\)，终止）。\(\gamma=0.9\)。\(Q(s,a)\) 是多少？
    选项 A。\(0.8(-1+0.9\cdot5)+0.1(-1+0.9\cdot2)+0.1(-10+0)=2.8+0.08-1=1.88\)。终止状态之后的价值为 0。
    2. 一台机器人不知道环境的转移概率，但已经得到了精确的 \(Q^\star\)。另一台只得到了精确的 \(V^\star\)。哪个说法正确？
    选项 C。\(\pi^\star(s)=\arg\max_a\sum_{s'}P(s'\mid s,a)[r+\gamma V^\star(s')]\) 需要 \(P\) 和 \(r\)；而 \(Q^\star\) 已经把这一步回溯算进去了。这是无模型 RL 学 Q 的原因。
    3. 在 FIG 3 里，均匀随机策略的价值不随打滑概率 \(p\) 变化。原因是？
    选项 B。策略价值只取决于策略诱导的链 \(P^\pi\) 和 \(\mathbf r^\pi\)。每个方向被命令的概率是 1/4，实际向每个方向移动的概率是 \(\tfrac14(1-p)+2\cdot\tfrac14\cdot\tfrac p2=\tfrac14\)，与 \(p\) 无关。（选项 D 也不对：随机策略约 94% 的回合掉下楼梯，但这不是原因。）
    4. FIG 5 里信念 \(b=P(L)=0.3\)，相机准确率 \(q=0.8\)，看了一眼，相机报告"左"。新的信念约是多少？
    选项 D。\(b'=\dfrac{0.8\cdot0.3}{0.8\cdot0.3+0.2\cdot0.7}=\dfrac{0.24}{0.38}\approx0.63\)。一次观测把信念从偏右翻到偏左，但还不够确定：在默认设置下 0.63 仍在"再看一眼"的区间里。
    5. 一个回合式任务原本只有到达目标时的奖励。下面哪种修改保证最优策略不变？
    选项 C。势函数项沿轨迹相消，只让每个状态的所有 Q 值同时平移 \(-\Phi(s)\)。选项 A 让机器人宁愿不结束；选项 B 就是 FIG 6 里会被钻空子的接近奖励；选项 D 让"尽快结束"更有吸引力，有其他终止方式时（例如失败终止）就可能改变策略。

    11延伸阅读

    • R. S. Sutton & A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Ch. 3–4 — MDP、回报、价值函数、Bellman 方程、策略评估与策略迭代、广义策略迭代
    • M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994 — MDP 理论的标准参考：确定性平稳最优策略的存在性、策略迭代与修正策略迭代
    • R. A. Howard, Dynamic Programming and Markov Processes, MIT Press, 1960 — 策略迭代的原始来源
    • R. Bellman, Dynamic Programming, Princeton University Press, 1957 — 最优性原理与 Bellman 方程
    • L. P. Kaelbling, M. L. Littman & A. R. Cassandra, "Planning and acting in partially observable stochastic domains", Artificial Intelligence 101, 1998 — POMDP、信念状态与价值函数的清晰入门
    • R. D. Smallwood & E. J. Sondik, "The optimal control of partially observable Markov processes over a finite horizon", Operations Research, 1973 — 有限时域 POMDP 价值函数分段线性且凸
    • H. Kurniawati, D. Hsu & W. S. Lee, "SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces", RSS 2008 — 基于点的 POMDP 求解器
    • A. Y. Ng, D. Harada & S. Russell, "Policy invariance under reward transformations: Theory and application to reward shaping", ICML 1999 — 势函数奖励塑形
    • F. Pardo, A. Tavakoli, V. Levdik & P. Kormushev, "Time limits in reinforcement learning", ICML 2018 — 截断与终止的区别
    • J. Kober, J. A. Bagnell & J. Peters, "Reinforcement learning in robotics: A survey", The International Journal of Robotics Research, 2013 — 机器人 RL 的综述，包括状态、动作与奖励的设计