Part V · 第 20 章强化学习 · 20.1Part V · Ch. 20 Reinforcement Learning · 20.1

MDP 与 Bellman 方程MDPs & Bellman Equations

机器人一步一步地做决定：看到状态，选一个动作，拿到一份奖励，然后世界（带着随机性）把它送到下一个状态。马尔可夫决策过程 (MDP) 用五样东西把这件事写清楚，Bellman 方程把"从这里出发，长期平均能拿多少奖励"写成一个自洽的一步递推。6.12 节已经在已知的格子世界上用值迭代求过代价到终点；这一节换成强化学习的语言，并往前走：回报与折扣、策略、状态价值 V 与动作价值 Q、Bellman 期望方程与最优方程、策略迭代，再看机器人看不全状态 (POMDP) 时怎么办，以及奖励应该怎样设计。 A robot makes decisions one step at a time: it sees a state, picks an action, receives a reward, and the world (with some randomness) moves it to the next state. A Markov decision process (MDP) pins this down with five objects, and the Bellman equations turn "how much reward can I expect in the long run from here" into a self-consistent one-step recursion. Lesson 6.12 already ran value iteration on a known grid world to get the cost-to-go; this lesson switches to the language of reinforcement learning and goes further: returns and discounting, policies, state values V and action values Q, the Bellman expectation and optimality equations, policy iteration, what to do when the robot cannot see the whole state (POMDPs), and how to design the reward.

约 50 分钟~50 min 前置：6.12 动态规划 · 4.7 贝叶斯滤波Prereqs: 6.12 Dynamic programming · 4.7 The Bayes filter 6 个交互6 interactives

1为什么机器人需要它Why robots need this

一台四足机器人在仿真里学走路，一只机械手学着把方块转到指定朝向，一台移动机器人学会绕开湿滑的地面去充电：这些都是强化学习 (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 更有用，固定策略的价值怎么求（策略评估）以及怎样一步步改进它（策略迭代），机器人看不全状态时会发生什么，以及奖励写错了会怎样。

A quadruped learning to walk in simulation, a robot hand learning to turn a cube to a target orientation, a mobile robot learning to avoid slippery floor on its way to the charger: all of these are reinforcement learning (RL). What they share is that nobody tells the robot the "correct action" at each step. There is only a reward signal saying how good the outcome was, and whether something was good often shows up only many steps later.

Before we can talk about "learning a good policy" we must say what the state is, which actions exist, how the world responds, and what "good" means. The Markov decision process (MDP) is that shared language. Every algorithm later in this chapter (Q-learning and DQN in 20.2, policy gradients in 20.3, PPO and SAC in 20.4, offline RL in 20.5) and the robot RL of Part VI works on an MDP, and all of them use the Bellman equations: they either approximate the fixed point of the Bellman optimality equation from samples, or use the Bellman expectation equation to estimate "how much better than average this action is".

Lesson 6.12 already covered the core of dynamic programming: the principle of optimality, value iteration, slippery cliff walking, and the convergence of value iteration as a contraction. It used costs and $\min$, and it assumed the environment model $P(s'\mid s,a)$ was known. Here we switch to the RL convention (rewards and $\max$, reward = negative cost) and work out what 6.12 only touched on: what returns and discounting really mean, why the action value Q is more useful than V, how to compute the value of a fixed policy (policy evaluation) and improve it step by step (policy iteration), what happens when the robot cannot see the whole state, and what goes wrong when the reward is written badly.

2直觉：一台在湿滑地面上找充电桩的机器人Intuition: a robot looking for its charger on a slippery floor

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

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

This example runs through the whole lesson: a warehouse robot on an 8×5 floor starts at S on the left and heads for the charging dock on the right. Grey cells are shelves and cannot be entered; the middle four cells of the bottom row are a stairwell: falling in gives reward −10 and ends the episode; entering the dock gives +10 and ends the episode; every other step gives −1 (battery and time). The floor is wet: when commanded "right", the robot really moves right with probability $1-p$, and with probability $p/2$ each it slides in one of the two perpendicular directions (up or down), the same noise model as the slippery cliff of 6.12. Bumping into a wall or a shelf leaves it where it is.

Writing it as an MDP takes five things:

$\mathcal S$	状态集合：36 个可走的格子（其中 5 个是终止状态：楼梯 4 格和充电桩）。the state set: 36 free cells (5 of them terminal: the 4 stair cells and the dock).
$\mathcal A$	动作集合：上、右、下、左四个命令。the action set: the four commands up, right, down, left.
$P(s'\mid s,a)$	转移概率：命令 $a$ 之后落到 $s'$ 的概率（打滑模型）。the transition probabilities: the chance of landing in $s'$ after command $a$ (the slip model).
$r(s,a,s')$	奖励：进充电桩 +10，掉楼梯 −10，其余每步 −1。the reward: +10 into the dock, −10 into the stairs, −1 for every other step.
$\gamma$	折扣因子：本例取 0.95，下一节专门讨论它。the discount factor: 0.95 here; the next section is about it.

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

"Markov" means the distribution of the next state depends only on the current state and action, not on how the robot got here. Every decision produces one piece of experience $(s_t,a_t,r_{t+1},s_{t+1})$; an episode is the whole trajectory from the start to a terminal state. What we care about is not the reward of one step but the discounted return of the whole 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)$。

If nothing slips, the robot reaches the dock in 8 steps: −1 for each of the first 7 and +10 for the last, a return of $-(1+\gamma+\cdots+\gamma^6)+10\gamma^7=0.95$. But the floor is wet: the same policy produces a different trajectory, and a different return, every time. The return is a random variable. The value $V^\pi(s)$ of a policy $\pi$ from state $s$ is its expectation. The figure below lets you run episodes one at a time, then 1000 at once, and watch the average return approach the exact $V^\pi(S)$.

FIG 1回合与回报：同一个策略，每次结果不同Episodes and returns: one policy, a different outcome every time

1000 回合的回报直方图histogram of 1000 returns

琥珀色圆点是机器人，青色折线是本回合走过的路，紫色小点标出打滑的那几步。格子的蓝色越浓，所选策略在该格的精确价值 $V^\pi$ 越高。三种策略："最优"是对当前 $p$ 求出的 $\pi^\star$；"最短路"是按无噪声 ($p=0$) 规划、在湿地上照走的策略；"随机"每步等概率选四个方向之一。直方图里青色柱是 1000 个回合的回报分布，琥珀色竖线是精确的 $V^\pi(S)$，紫色虚线是样本均值，灰色带是均值 ±2 倍标准误。回合超过 200 步会被截断。 The amber dot is the robot, the cyan polyline is the path of this episode, and small purple dots mark the steps that slipped. The stronger the blue tint of a cell, the higher the exact value $V^\pi$ of the selected policy there. Three policies: "optimal" is $\pi^\star$ solved for the current $p$; "shortest path" is planned without noise ($p=0$) and then followed on the wet floor; "random" picks one of the four directions uniformly at every step. In the histogram the cyan bars are the distribution of 1000 returns, the amber vertical line is the exact $V^\pi(S)$, the dashed purple line is the sample mean and the grey band is the mean ±2 standard errors. Episodes longer than 200 steps are truncated.

试一试Try this

用"最优"策略按"跑一回合"，直到有两个回合的回报不一样（有一回合打滑了）。注意掉下楼梯的那些回合。With the "optimal" policy press "Run episode" until two episodes end with different returns (one of them slipped). Watch for the episodes that end in the stairs.
分别为两种不同的策略按"1000 回合"：样本均值落在精确 $V^\pi(S)$ 附近吗？在 $p=0.2$ 时，"最优"和"最短路"的差距（约 0.14）和标准误（约 0.17）谁大？Press "1000 episodes" for two different policies: does the sample mean land near the exact $V^\pi(S)$? At $p=0.2$, which is larger: the gap between "optimal" and "shortest path" (about 0.14) or the standard error (about 0.17)?

核心洞见Key insight

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

A value is not the outcome of one run but an expectation. At $p=0.2$ the optimal policy's exact value from S is −5.07, yet single returns spread from below −15 up to 0.95; with the default seed the mean of 1000 episodes is −5.15 with a standard error of about 0.17, larger than the true gap between the "optimal" and "shortest path" policies (−5.07 vs −5.21). Comparing policies only by averaging episodes takes many samples, which is why the RL methods ahead use the Bellman equation to "borrow" estimates from neighbouring states (TD learning in 20.2).

3折扣因子 $\gamma$：机器人能看多远The discount factor $\gamma$: how far the robot looks ahead

$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}$。

A reward $t$ steps ahead is multiplied by $\gamma^t$. Why discount? There are three complementary views. Mathematically: for tasks that never end, $\gamma<1$ keeps the infinite sum finite; with rewards bounded by $r_{\max}$, $|G|\le r_{\max}/(1-\gamma)$. As a preference: a reward now is worth more than the same reward later. Probabilistically: $\gamma$ can be read as the probability that the task is still running after each step, and $1-\gamma$ as the chance it ends unexpectedly.

The weights $\gamma^t$ sum to $1/(1-\gamma)$, so $1/(1-\gamma)$ is often called the effective horizon: $\gamma=0.9$ looks about 10 steps ahead, $\gamma=0.99$ about 100. The figure below is a corridor: at the left end is a slow charger (+3), just 3 steps away; at the right end a fast charger (+10), 7 steps away. The robot's choice depends on $\gamma$: from cell $s$, going left is worth $3\gamma^{s-1}$ and going right $10\gamma^{9-s}$.

FIG 2近处的小奖励还是远处的大奖励A small reward nearby or a large one far away

上半部分：走廊里每一格上方的蓝色柱是最优价值 $V^\star(s)$，格子里的箭头是最优方向；琥珀色圆点是机器人，可以拖动到别的格子。下半部分：紫色柱是第 $t$ 步奖励的权重 $\gamma^t$（$t=0\ldots39$），青色虚线标出有效时域 $1/(1-\gamma)$（超过 40 时画在最右端）。走廊是确定性的，没有打滑，每步奖励为 0。 Top: the blue bar above each corridor cell is the optimal value $V^\star(s)$, and the arrow in the cell is the optimal direction; the amber dot is the robot, which you can drag to another cell. Bottom: the purple bars are the weights $\gamma^t$ of the reward at step $t$ ($t=0\ldots39$), and the dashed cyan line marks the effective horizon $1/(1-\gamma)$ (drawn at the right edge when it exceeds 40). The corridor is deterministic, with no slip and zero reward per step.

机器人在第 3 格时，慢慢降低 $\gamma$，找到它从"去 +10"改为"去 +3"的那个 $\gamma$（解 $3\gamma^{2}=10\gamma^{6}$，即 $\gamma=0.3^{1/4}\approx0.74$）。With the robot in cell 3, lower $\gamma$ slowly and find the $\gamma$ at which it switches from "go to +10" to "go to +3" (solve $3\gamma^{2}=10\gamma^{6}$, i.e. $\gamma=0.3^{1/4}\approx0.74$).

$\gamma$ 是问题的一部分$\gamma$ is part of the problem

同一个环境，不同的 $\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 秒。

The same environment gives different "optimal" policies for different $\gamma$: $\gamma$ is not just a technicality that makes sums converge; it defines what you want. Raise $\gamma$ above 0.86 and every corridor cell heads for +10 (cell 1 needs $10\gamma^8>3$); set $\gamma$ to 0 and the robot sees only the next reward, so every cell except the two next to a charger has value 0. In robotics $\gamma$ also has to be read together with the control rate: with $\gamma=0.99$, a 50 Hz policy looks about 100 steps, or 2 seconds, ahead; raise the control rate to 200 Hz without changing $\gamma$ and it sees only 0.5 seconds.

4动手：V、Q 与一步回溯Play: V, Q and the one-step backup

两个价值函数是 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'$ 取平均：

Two value functions are the central objects of RL:

the state value $V^\pi(s)$: the expected return from $s$ when acting by $\pi$ throughout;
the action value $Q^\pi(s,a)$: the expected return when you first take action $a$ in $s$ (whatever $\pi$ would choose) and follow $\pi$ afterwards.

The same "one-step backup" links them. Take $a$ in $s$: the world sends the robot to some $s'$ with probability $P(s'\mid s,a)$, it collects $r(s,a,s')$, and the expected return from $s'$ onward is $V^\pi(s')$. Averaging over all possible $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)$ 拆成每个结果的贡献。

The second formula says a state's value is the policy-weighted average of its action values. Combining the two gives the Bellman expectation equation, which holds for any policy. For the optimal policy the average becomes a maximum, $V^\star(s)=\max_a Q^\star(s,a)$: the Bellman optimality equation, which is exactly what the value iteration of 6.12 solved (with rewards and $\max$).

The figure below splits every cell into four triangles, one per action, each showing $Q(s,a)$. Click a triangle inside a cell to select that $(s,a)$: the figure draws its three possible outcomes with their probabilities, and the panel on the right breaks $Q(s,a)$ into the contribution of each outcome.

FIG 3Q 值地图与一步 Bellman 回溯A Q-value map and the one-step Bellman backup

三角形的蓝色越浓，该动作的 $Q$ 越高（色标对所有格子相同，从 −20 到 +10）；格子足够大时写出数值。"最优"模式显示 $Q^\star$，琥珀色描边的三角形是每格的最优动作，箭头是 $\pi^\star$；"随机策略"模式显示均匀随机策略的 $Q^\pi$，每格画四个短箭头。选中的格子有琥珀色粗框；琥珀色箭头从它指向三个可能的结果（实线是命令的方向，虚线是打滑），线越粗概率越大，原地不动画成小圆圈；结果格子用青色框出。 The stronger the blue tint of a triangle, the higher that action's $Q$ (the colour scale is shared by all cells, from −20 to +10); numbers appear when the cells are large enough. "Optimal" mode shows $Q^\star$: the triangle with an amber outline is each cell's best action, and the arrow is $\pi^\star$. "Random policy" mode shows $Q^\pi$ of the uniformly random policy, with four short arrows per cell. The selected cell has a thick amber frame; amber arrows run from it to its three possible outcomes (solid for the commanded direction, dashed for slips), thicker for more probable ones, with a small circle for staying put; the outcome cells are framed in cyan.

点击楼梯正上方某一格的下三角（命令"向下"）：右侧的分解里，哪一项让这个 $Q$ 变得这么低？Click the lower triangle (command "down") of a cell directly above the stairs: which term in the breakdown on the right makes this $Q$ so low?
切到"随机策略"，先猜：价值最低的格子是紧挨楼梯的，还是离一切都远的？然后点击那个价值最低的格子验证。Switch to "random policy" and guess first: is the lowest-valued cell the one next to the stairs, or the one far from everything? Then click the lowest-valued cell to check.
回到"最优"，把 $p$ 调到 0.45 或更高，找到最优动作径直驶向楼梯的那一格并点击它。看它的 $V^\star$：为什么机器人宁可掉下去？Back in "optimal", raise $p$ to 0.45 or more, then find and click the cell whose best action drives straight into the stairs. Read its $V^\star$: why would the robot rather fall?

为什么 Q 比 V 更有用Why Q is more useful than 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$ 本身就成了一个优化问题。

With only $V^\star$, choosing an action still takes a backup $\sum_{s'}P(s'\mid s,a)[r+\gamma V^\star(s')]$ for every action, which needs the model $P$ and $r$. With $Q^\star$ you simply take $\arg\max_a Q^\star(s,a)$, no model needed. Real robots usually do not know $P$ (how slippery is the floor? how heavy is the object?), so model-free methods learn Q (Q-learning and DQN in 20.2, the critic of SAC in 20.4). The price is a table $|\mathcal A|$ times larger than V, and with continuous actions the $\arg\max_a$ becomes an optimization problem of its own.

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

"Random policy" mode shows a curious effect: drag $p$ from 0 to 0.5 and the random policy's values do not change at all (−15.98 at S throughout). Slipping replaces the commanded direction with one of the two perpendicular ones, and a uniformly random command passed through this symmetric slip is still a uniformly random direction. Nor is the lowest-valued cell next to the stairs: it is the top-left corner (about −17.99), where a randomly wandering robot roams for a long time before reaching any terminal state, paying −1 per step, bounded below by $-1/(1-\gamma)=-20$; cells next to the stairs end quickly with −10 instead.

5策略评估与策略迭代Policy evaluation and policy iteration

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

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

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

The value iteration of 6.12 does one "max" backup over all states per round until the values converge. The other classic route is policy iteration (Howard, 1960), which alternates two steps:

Policy evaluation: for the current fixed $\pi$, compute $V^\pi$. The Bellman expectation equation then contains no $\max$ and is a linear system with one unknown and one equation per non-terminal state, $V^\pi=\mathbf r^\pi+\gamma P^\pi V^\pi$; solve $(I-\gamma P^\pi)V^\pi=\mathbf r^\pi$ directly, or sweep repeatedly with the expectation backup.
Policy improvement: in every state switch to $\arg\max_a Q^\pi(s,a)$ (greedy with respect to $V^\pi$). The policy improvement theorem guarantees the new policy is no worse in any state.

There are finitely many deterministic policies ($4^{31}$ here), and each round either strictly improves or changes nothing, so policy iteration must stop at an optimal policy after finitely many rounds, and in practice it usually takes very few.

FIG 4策略迭代：评估、改进、再评估Policy iteration: evaluate, improve, evaluate again

离最优价值的距离 $\|V-V^\star\|_\infty$（对数），横轴是迭代 / 扫描次数distance to the optimal values $\|V-V^\star\|_\infty$ (log scale) against iteration / sweep

左：当前策略的箭头，以及最近一次评估得到的 $V^\pi$（蓝色越浓越高，数字是 $V^\pi$）；上一次改进中改变了动作的格子有琥珀色框。点击格子把它的箭头顺时针转 90°，用来自己设定初始策略（这会重新开始一轮策略迭代）。右：琥珀色点是第 $i$ 次评估的 $\|V^{\pi_i}-V^\star\|_\infty$，青色线是从 $V=0$ 出发的值迭代第 $k$ 次扫描的误差，紫色虚线是压缩映射给出的上界 $\gamma^k\|V^\star\|_\infty$。打滑概率固定为 $p=0.2$。 Left: the current policy's arrows and the $V^\pi$ from the latest evaluation (stronger blue = higher, numbers are $V^\pi$); cells whose action changed in the last improvement have an amber frame. Click a cell to turn its arrow 90° clockwise and set your own initial policy (this starts a new run of policy iteration). Right: amber dots are $\|V^{\pi_i}-V^\star\|_\infty$ after the $i$-th evaluation, the cyan line is the error of value iteration from $V=0$ after sweep $k$, and the dashed purple line is the contraction bound $\gamma^k\|V^\star\|_\infty$. The slip probability is fixed at $p=0.2$.

从初始策略"全部向上"出发（按"重置"），交替按"评估"和"改进"，直到改进不再改变任何动作。一共评估了几次？$V^\pi(S)$ 的序列是单调的吗？Starting from the initial policy "all up" (press "Reset"), alternate "Evaluate" and "Improve" until an improvement changes no action. How many evaluations did it take? Is the sequence of $V^\pi(S)$ monotone?
按"重置"后，点击至少 3 个格子，把它们的箭头转向楼梯或货架，造一个糟糕的初始策略，再按"运行到底"：结果还是同一个最优策略吗？After "Reset", click at least 3 cells to point their arrows into the stairs or shelves, building a bad initial policy, then press "Run to the end": do you still end at the same optimal policy?

在默认的 $\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$ 的线性方程组：状态多时这很贵，所以实践中常用折中的"修正策略迭代"：每次只做几次评估扫描就改进。

At the default $\gamma=0.95$, starting from "all up", $V^\pi(S)$ goes −20.00, −11.36, −11.33, −5.81, −5.68, −5.11, −5.07: 7 evaluations, the first 6 improvements each change some actions, and the 7th changes nothing, so it stops. The first value is almost exactly $-1/(1-\gamma)=-20$, because a robot that "always goes up" ends up pressing against the top wall paying −1 forever. Compare the cyan line on the right: value iteration needs 36 sweeps to push its error below $10^{-6}$ (although its greedy policy is already optimal from sweep 9). The contraction bound (dashed purple) would need 314; it is conservative, because the terminal states absorb probability and the actual convergence is much faster than $\gamma^k$. Raise $\gamma$ to 0.99 and the bound grows to 1600 sweeps, value iteration actually needs 41, and policy iteration still needs 7 evaluations. The price is that each evaluation solves a $31\times31$ linear system, which is expensive with many states, so in practice a compromise, "modified policy iteration", does only a few evaluation sweeps before each improvement.

后面的 RL 都是"广义策略迭代"All RL ahead is "generalized policy iteration"

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

Alternating (or interleaving) "estimate how good the current policy is" with "make the policy greedier with respect to that estimate" is what Sutton and Barto call generalized policy iteration. In actor-critic methods (20.4), the critic is an inexact policy evaluation from samples and the actor update is a gentle, small-step policy improvement. The only differences: without a model, evaluation uses samples; with too many states, values are represented by neural networks.

6看不全状态：POMDP 与信念When the state is hidden: POMDPs and beliefs

前面的机器人知道自己在哪一格。真实机器人看到的是观测：相机图像、激光点云、关节编码器读数，而不是"状态"本身。如果观测里缺了做决定需要的信息（只有一帧图像，看不出物体在往哪边动；不知道杯子在左边桌上还是右边桌上），问题就成了部分可观测 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$ 次决定，最后一次必须送出去。

The robot so far knew which cell it was in. A real robot receives observations (camera images, lidar points, encoder readings), not the "state" itself. When the observation lacks information the decision needs (a single image cannot show which way an object is moving; the robot does not know whether the cup is on the left table or the right one), the problem becomes a partially observable MDP (POMDP): an MDP plus an observation model $O(o\mid s')$.

The key idea: although the state is hidden, the robot can maintain a belief $b(s)$, a probability distribution over states, and update it with the Bayes filter of Lesson 4.7 after every action and observation. The belief itself is Markov, so a POMDP is equivalent to an MDP whose state is the belief (the "belief MDP"); the Bellman equation still holds, only the state is now a continuous probability distribution.

The figure below is the smallest example: a robot at a T-junction must deliver a part to a workstation that is either to the left or to the right, and it is not sure which. The belief is $b=P(L)$, where L means "the workstation is on the left". Three actions: deliver left or right straight away (+10 if correct, −10 if wrong, the episode ends), or look first (cost $c$; a camera classifier with accuracy $q$ reports "left" or "right", and the belief is updated). The robot gets at most $H$ decisions, and the last one must be a delivery.

$$ \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$ 次决定时的最优价值。

Here $b'_L$ is the belief after the camera reports "left" (likewise $b'_R$ after "right"), and $P(o\mid b)$ is the probability of each report under the current belief, e.g. $P(L\mid b)=q\,b+(1-q)(1-b)$. $V_h$ is the optimal value with $h$ decisions left.

FIG 5在信念上做 Bellman 回溯：什么时候值得先看一眼Bellman backups on beliefs: when is it worth looking first

横轴是信念 $b=P(L)$，纵轴是价值。两条紫色虚线是立即送出的价值 $10(2b-1)$ 与 $10(1-2b)$，它们的上包络就是 $V_1$；淡紫色线是 $V_2,\ldots,V_{H-1}$，琥珀色粗线是 $V_H$。青色带是"先看一眼"最优的信念区间。拖动琥珀色圆点改变当前信念。按"模拟一回合"：按 $b$ 抽一个真实工位，按最优策略行动，下方的编号点是每一步之后的信念。 The horizontal axis is the belief $b=P(L)$, the vertical axis the value. The two dashed purple lines are the values of delivering at once, $10(2b-1)$ and $10(1-2b)$; their upper envelope is $V_1$. Thin purple lines are $V_2,\ldots,V_{H-1}$, and the thick amber line is $V_H$. The cyan band is the range of beliefs where "look first" is optimal. Drag the amber dot to change the current belief. "Simulate episode" draws a true workstation according to $b$ and acts optimally; the numbered dots along the bottom are the belief after each step.

默认 $b=0.9$ 时机器人直接向左送。把信念拖进青色带，让"先看一眼"成为最优动作。在默认设置下，这个区间大约是 $0.152<b<0.848$。At the default $b=0.9$ the robot delivers left at once. Drag the belief into the cyan band so that "look first" becomes optimal. With the default settings that range is about $0.152<b<0.848$.
在 $H\ge2$ 时降低相机准确率 $q$，直到"先看一眼"在任何信念下都不再值得（青色带消失）。在 $c=1$ 时这发生在 $q\le0.55$：只有当 $10(2q-1)>c$，看一眼带来的期望收益才抵得上它的代价。With $H\ge2$, lower the camera accuracy $q$ until looking is no longer worth it at any belief (the cyan band disappears). At $c=1$ this happens at $q\le0.55$: looking pays for itself only when $10(2q-1)>c$.

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

Notice the shape of $V_h(b)$: it is the upper envelope of straight lines, piecewise linear and convex. This holds for every finite-horizon POMDP (Smallwood & Sondik, 1973), and point-based POMDP solvers exploit exactly that structure. The convexity has an intuitive meaning: the more certain the belief (the closer to either end), the higher the value; in the middle, information itself is valuable, and "look first" is an action taken purely to gather information. Such actions never appear in a fully observable MDP.

机器人里的部分可观测性Partial observability in robots

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

Exact POMDP solutions are feasible only for small problems (point-based solvers such as SARSOP handle moderate discrete ones). Deep RL takes a cruder but practical route: feed the policy the last few observations together with the previous action (frame stacking), or compress the history with a recurrent network or state-space model (17.2) and let the network learn an "implicit belief". A legged robot cannot see ground friction or payload mass, which can also be treated as hidden state; 23.1 shows how a teacher policy trained in simulation with "privileged information" is imitated by a student that sees only its proprioceptive history.

7再看数学The math

提示：把鼠标悬停在公式中带底色的符号上，FIG 2、FIG 3、FIG 5、FIG 6 中对应的元素会被高亮。Tip: hover the highlighted symbols in the formulas; the matching elements in FIG 2, FIG 3, FIG 5 and FIG 6 light up.

MDP、策略与回报MDPs, policies and returns

一个 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 方程的来源：

An MDP is $(\mathcal S,\mathcal A,P,r,\gamma)$ plus an initial state distribution $\rho_0$. The Markov property: $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)$. A policy $\pi(a\mid s)$ is a distribution over actions given the state (a deterministic policy is the special case $a=\pi(s)$). The return from time $t$ obeys a one-step recursion, the source of every Bellman equation:

$$ 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$。

In episodic tasks a terminal state is absorbing with zero reward afterwards, so terminal states have value 0. The dictionary to 6.12: cost $c=-r$, $\min$ becomes $\max$, and cost-to-go $=-V$.

Bellman 期望方程：一个线性方程组The Bellman expectation equation: a linear system

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

Taking expectations of $G_t=r_{t+1}+\gamma G_{t+1}$ under $\pi$ and $P$ gives

$$ 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]$。

Here $P^\pi_{ss'}=\sum_a\pi(a\mid s)P(s'\mid s,a)$ is the Markov chain the policy induces and $\mathbf r^\pi(s)$ the expected one-step reward. Each row of $P^\pi$ sums to 1 (to at most 1 if only the non-terminal states are kept), so $\|\gamma P^\pi\|_\infty\le\gamma<1$ and $I-\gamma P^\pi$ is always invertible: every policy has a unique value. A direct solve costs $O(|\mathcal S|^3)$; iterating $V\leftarrow\mathbf r^\pi+\gamma P^\pi V$ costs $O(|\mathcal S|^2)$ per sweep and converges at rate $\gamma$ (the contraction argument of 6.12). Q satisfies the same kind of equation: $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 最优方程The Bellman optimality equation

$$ 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 的出发点。

Because of the $\max$ this is a nonlinear system: it cannot be solved in one shot, only iterated (value iteration) or searched over policies (policy iteration). For finite MDPs with $\gamma<1$ a basic fact holds (see Puterman's book): there exists a deterministic, stationary (time-invariant) policy that is optimal in all states simultaneously, so the search can be restricted to the $|\mathcal A|^{|\mathcal S|}$ deterministic policies, with no need for random or history-dependent ones. In the Q version the $\max$ sits inside the expectation, so a single sample $(s,a,r,s')$ gives an unbiased one-step target $r+\gamma\max_{a'}Q(s',a')$ for it: the starting point of Q-learning in 20.2.

策略改进定理The policy improvement theorem

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

Let $\pi'(s)=\arg\max_a Q^\pi(s,a)$. Then $Q^\pi(s,\pi'(s))\ge V^\pi(s)$ for every $s$. Unrolling this inequality along trajectories of $\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 都是沿着优势的方向，把策略往好的动作推一小步。

If an improvement leaves $\pi'=\pi$, then $V^\pi$ satisfies the optimality equation and $\pi$ is optimal. The difference $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$ is the advantage function: greedy improvement means "pick actions with positive advantage". The policy gradients of 20.3 and PPO in 20.4 both push the policy a small step toward actions with positive advantage.

POMDP 与信念 MDPPOMDPs and the belief MDP

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

A POMDP is $(\mathcal S,\mathcal A,P,r,\Omega,O,\gamma)$, with $O(o\mid s',a)$ the probability of observing $o$ after arriving in $s'$. The belief is updated by the Bayes filter (predict one step, then correct with the observation), normalized by $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 画的正是两个状态时的情形。

A belief is a point in the $(|\mathcal S|-1)$-dimensional simplex, so even with only two underlying states the belief MDP has a continuous state space. At finite horizon $V$ is the upper envelope of finitely many "$\alpha$-vector" lines (hyperplanes), $V(b)=\max_i\alpha_i^\top b$; FIG 5 draws exactly the two-state case.

基于势函数的奖励塑形Potential-based reward shaping

在奖励上加一项 $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）。他们还证明了，在不知道环境细节时，这是唯一能保证最优策略不变的加法塑形形式。

Add a term $F(s,s')=\gamma\,\hl{phi}{\Phi(s')}-\hl{phi}{\Phi(s)}$ to the reward, with $\Phi$ any function of the state (and $\Phi=0$ at terminal states). Along any trajectory the extra return telescopes: $\sum_t\gamma^t F_t=-\Phi(s_0)$. So for every action $Q'(s,a)=Q(s,a)-\Phi(s)$: all actions in a state lose the same amount, their ranking is unchanged, and the optimal policy is unchanged (Ng, Harada & Russell, 1999). They also showed that, without knowledge of the environment's details, this is the only additive shaping form that is guaranteed to keep the optimal policy.

8机器人中的它：怎样把任务写成 MDP，尤其是奖励In robotics: writing a task as an MDP, especially the reward

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

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

Writing a real robot task as an MDP makes every item an engineering decision. State / observation: a legged robot typically uses joint angles $\mathbf q$, joint velocities, base orientation and angular velocity (IMU), the previous action and the velocity command; manipulation often adds camera images. Action: rarely raw torques; more often joint position targets, tracked at a higher rate by a low-level PD controller (13.1). Termination: the base touches the ground, a joint leaves its limits, or a time limit is reached. Reward: the hardest item of all.

A sparse reward (+1 only on success) is the most honest, but a robot exploring at random almost never stumbles on success; so people add "guiding" terms: more reward the closer to the goal, the more accurately the velocity is tracked; penalties for torque and for the rate of change of actions. Every added term can quietly change what "optimal" means. FIG 3 already showed one case: with −1 per step and only −10 for the stairs, at $p\ge0.45$ the optimal action in the bottom-row cell left of the stairs is to drive straight into them, because for it "ending" beats "continuing to be penalized"; and at $p=0.2$ the optimal policy from S still falls down the stairs with probability 33%. If the stairs were real, −10 is clearly far too cheap. The figure below shows another typical mistake.

FIG 6奖励塑形：会被"钻空子"的奖励，与不会的Reward shaping: a reward that gets hacked, and one that cannot be

机器人从 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 按贪心策略走出的路线；红色圆圈表示路线停在那里原地打转，永远不进充电桩。 The robot starts at S and heads for the dock G (+10, the episode ends), with a wall in between that must be passed underneath; the floor does not slip, $\gamma=0.95$, and every other step gives 0 (sparse). "Closeness bonus" adds $w\,(1-d(s')/d_{\max})$ per step, with $d$ the straight-line distance to G; "potential-based shaping" adds $\gamma\Phi(s')-\Phi(s)$ per step with $\Phi(s)=-w\,d(s)/d_{\max}$. Stronger blue means higher $V^\star$ under the current reward (scaled between the minimum and maximum of the current mode). The amber line is the greedy route from S; a red circle means the route stalls there forever and never enters the dock.

切到"接近奖励"，增大 $w$，直到机器人不再进入充电桩，而是停在旁边一直领奖励（$w$ 约 0.56 以上）。读出它的"真实回报"（只按稀疏奖励计算）。Switch to "closeness bonus" and raise $w$ until the robot no longer enters the dock but parks next to it collecting the bonus (from about $w=0.56$). Read its "true return" (counting the sparse reward only).
保持 $w\ge0.6$，切到"势函数塑形"：路线和稀疏奖励时完全一样吗？$V^\star(S)$ 差了多少，是否等于 $-\Phi(S)$？Keep $w\ge0.6$ and switch to "potential-based shaping": is the route exactly the same as with the sparse reward? By how much does $V^\star(S)$ differ, and does it equal $-\Phi(S)$?

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

The trouble with the "closeness bonus" is that it is a positive reward collected at every step: parked next to G the robot earns about $0.894\,w$ per step, worth $0.894\,w/(1-\gamma)\approx17.9\,w$ forever, and once that exceeds the +10 of entering, "never enter" becomes optimal. The robot did nothing wrong; it optimized exactly what we wrote. This is reward hacking, or "specification gaming". Potential-based shaping is a difference instead: whatever is gained by approaching the goal is paid back in full when moving away, so circling earns nothing and the optimal policy is unchanged.

真实系统里In real systems

足式机器人。大规模并行仿真里训练 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。

Legged robots. In work that trains quadrupeds such as ANYmal to walk with massively parallel simulation (e.g. Rudin et al., CoRL 2021), the reward is a weighted sum of about ten terms: tracking the commanded linear and angular velocity and a "feet air time" term that encourages long steps (positive), and penalties on torques, joint accelerations, the action rate, base collisions and so on (negative), plus "terminate when the base touches the ground". Every weight has to be tuned; 23.1 discusses this in detail. Manipulation. Many grasping and insertion tasks simply use a sparse success reward and handle exploration with demonstrations or hindsight experience replay (HER, Andrychowicz et al., 2017). Interfaces. The common Gymnasium interface env.step(a) returns (obs, reward, terminated, truncated, info), separating true termination from a time-limit truncation, which should not be treated as $V=0$ (see pitfall 1). Discount. A common default $\gamma$ in deep RL libraries is 0.99 (e.g. PPO and SAC in Stable-Baselines3). If the reward is too hard to write, it can be learned from demonstrations or human preferences: see 20.6.

9常见误区Common pitfalls

误区 1：把"到时截断"当成"终止"Pitfall 1: treating a time-limit truncation as termination

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

Training episodes are often capped at some number of steps (200 in FIG 1). A robot stopped at step 200 has not reached a terminal state: its value from there is not 0. Treating it as terminal in the Bellman target ($r+\gamma\cdot0$) tells the learner "the world ends when time runs out", which biases values downward, and if time is not part of the state, the same state is sometimes terminal and sometimes not, so the problem is no longer Markov. The fix: use $r$ for true terminations and keep bootstrapping with $r+\gamma V(s')$ for truncations (Pardo et al., 2018), which is exactly why Gymnasium separates terminated from truncated.

误区 2：以为加奖励项"只会帮忙"Pitfall 2: assuming an extra reward term "can only help"

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

Every reward term changes the optimal policy. A positive reward collected at every step makes the robot reluctant to finish (the closeness bonus of FIG 6); a per-step penalty combined with a cheap termination makes it want to finish as soon as possible, even by failing (FIG 3 driving into the stairs at $p\ge0.45$). In episodic tasks, even adding a constant to every step's reward changes the optimal policy. Only the potential form $\gamma\Phi(s')-\Phi(s)$ is guaranteed to leave it unchanged.

误区 3：只有 V 就想选动作Pitfall 3: trying to act from V alone

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

"Move to the neighbour with the highest $V$" is right only when transitions are deterministic and you know where each action leads. With slip, what must be compared is $\sum_{s'}P(s'\mid s,a)[r+\gamma V(s')]$, which needs a model. The cells beside the stairs in FIG 3 are an example: the cell below may have a high value, but the Q of "command down" must account for slips and the stairs. Without a model, learn Q, or learn a policy (an actor) as well.

误区 4：观测不是马尔可夫的却浑然不觉Pitfall 4: a non-Markov observation you did not notice

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

Use a single image as the state and velocity is lost; with 20 ms of sensor and actuator latency the current observation no longer determines what happens next; friction and payload are invisible. The premise of the Bellman equation then fails, and the learned values and policies show strange averaging effects. Remedies: feed the last few observations and actions together, use a recurrent network, or randomize these hidden quantities in simulation and let the policy infer them from history (the POMDP view).

误区 5：$\gamma$ 随手设、和控制频率脱节Pitfall 5: picking $\gamma$ casually, detached from the control rate

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

The effective horizon $1/(1-\gamma)$ is counted in steps. Too small a $\gamma$ and the robot is short-sighted (going for the nearby +3 in FIG 2); too close to 1 and the values span a larger range, sample-based estimates get noisier and learning slows. When changing the control rate, change $\gamma$ with it: keeping the horizon in seconds fixed with a new step $\Delta t'$ requires $\gamma'=\gamma^{\Delta t'/\Delta t}$.

10小练习Check yourself

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)$ 是多少？1. Taking action $a$ in $s$: with probability 0.8 you reach $s_1$ ($r=-1$, $V(s_1)=5$), with 0.1 you reach $s_2$ ($r=-1$, $V(s_2)=2$), and with 0.1 you fall down the stairs ($r=-10$, terminal). $\gamma=0.9$. What is $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。Option A. $0.8(-1+0.9\cdot5)+0.1(-1+0.9\cdot2)+0.1(-10+0)=2.8+0.08-1=1.88$. The value after a terminal state is 0.

2. 一台机器人不知道环境的转移概率，但已经得到了精确的 $Q^\star$。另一台只得到了精确的 $V^\star$。哪个说法正确？2. One robot does not know the transition probabilities but has the exact $Q^\star$. Another has only the exact $V^\star$. Which statement is right?

选项 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 的原因。Option C. $\pi^\star(s)=\arg\max_a\sum_{s'}P(s'\mid s,a)[r+\gamma V^\star(s')]$ needs $P$ and $r$, whereas $Q^\star$ already contains that backup. This is why model-free RL learns Q.

3. 在 FIG 3 里，均匀随机策略的价值不随打滑概率 $p$ 变化。原因是？3. In FIG 3 the values of the uniformly random policy do not change with the slip probability $p$. Why?

选项 B。策略价值只取决于策略诱导的链 $P^\pi$ 和 $\mathbf r^\pi$。每个方向被命令的概率是 1/4，实际向每个方向移动的概率是 $\tfrac14(1-p)+2\cdot\tfrac14\cdot\tfrac p2=\tfrac14$，与 $p$ 无关。（选项 D 也不对：随机策略约 94% 的回合掉下楼梯，但这不是原因。）Option B. A policy's value depends only on its induced chain $P^\pi$ and $\mathbf r^\pi$. Each direction is commanded with probability 1/4, and the robot actually moves in each direction with probability $\tfrac14(1-p)+2\cdot\tfrac14\cdot\tfrac p2=\tfrac14$, independent of $p$. (Option D is wrong too: the random policy falls in about 94% of episodes, but that is not the reason.)

4. FIG 5 里信念 $b=P(L)=0.3$，相机准确率 $q=0.8$，看了一眼，相机报告"左"。新的信念约是多少？4. In FIG 5 the belief is $b=P(L)=0.3$ and the camera accuracy is $q=0.8$. The robot looks and the camera reports "left". What is the new belief, approximately?

选项 D。$b'=\dfrac{0.8\cdot0.3}{0.8\cdot0.3+0.2\cdot0.7}=\dfrac{0.24}{0.38}\approx0.63$。一次观测把信念从偏右翻到偏左，但还不够确定：在默认设置下 0.63 仍在"再看一眼"的区间里。Option D. $b'=\dfrac{0.8\cdot0.3}{0.8\cdot0.3+0.2\cdot0.7}=\dfrac{0.24}{0.38}\approx0.63$. One observation flips the belief from leaning right to leaning left, but not decisively: with the default settings 0.63 is still inside the "look again" range.

5. 一个回合式任务原本只有到达目标时的奖励。下面哪种修改保证最优策略不变？5. An episodic task originally has a reward only on reaching the goal. Which modification is guaranteed to leave the optimal policy unchanged?

选项 C。势函数项沿轨迹相消，只让每个状态的所有 Q 值同时平移 $-\Phi(s)$。选项 A 让机器人宁愿不结束；选项 B 就是 FIG 6 里会被钻空子的接近奖励；选项 D 让"尽快结束"更有吸引力，有其他终止方式时（例如失败终止）就可能改变策略。Option C. The potential term telescopes along trajectories and only shifts all Q-values of a state by $-\Phi(s)$. Option A makes the robot prefer never to finish; option B is the hackable closeness bonus of FIG 6; option D makes "finish quickly" more attractive and can change the policy when another way to end exists (a failure termination, say).

11延伸阅读Further reading

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

\(\mathcal S\)	状态集合：36 个可走的格子（其中 5 个是终止状态：楼梯 4 格和充电桩）。the state set: 36 free cells (5 of them terminal: the 4 stair cells and the dock).
\(\mathcal A\)	动作集合：上、右、下、左四个命令。the action set: the four commands up, right, down, left.
\(P(s'\mid s,a)\)	转移概率：命令 \(a\) 之后落到 \(s'\) 的概率（打滑模型）。the transition probabilities: the chance of landing in \(s'\) after command \(a\) (the slip model).
\(r(s,a,s')\)	奖励：进充电桩 +10，掉楼梯 −10，其余每步 −1。the reward: +10 into the dock, −10 into the stairs, −1 for every other step.
\(\gamma\)	折扣因子：本例取 0.95，下一节专门讨论它。the discount factor: 0.95 here; the next section is about it.