Part I · 第 6 章优化 · 6.12Part I · Ch. 6 Optimization · 6.12

动态规划Dynamic Programming

想知道从这里走到目标的最优路线，只需要知道"下一步走到哪里，从那里出发的最优代价是多少"。把这句话从终点往回递推，就是动态规划：它把一个指数级的路径搜索变成一张"到达目标的代价表"。Dijkstra、A*、LQR、值迭代、强化学习里的价值函数，都是同一个想法的不同面孔。 To know the best route from here to the goal, you only need to know "where the next step lands and what the best cost from there is". Recurse that sentence backward from the goal and you have dynamic programming: it turns an exponential search over paths into a table of costs-to-go. Dijkstra, A*, LQR, value iteration and the value functions of reinforcement learning are all faces of the same idea.

约 30 分钟~30 min 前置：6.1 什么是优化问题 · 1.4 矩阵乘法Prereqs: 6.1 Optimization problems · 1.4 Matrix multiplication 4 个交互4 interactives

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

机器人的许多问题都是"一步接一步的决策"：扫地机器人每一格往哪走，机械臂每个时刻施加多大的力矩，无人机每个控制周期怎样推力。每一步选得好不好，要看它对以后所有步骤造成的后果。如果穷举所有"动作序列"，选择数量随步数指数增长：3 个选择走 20 步就是 $3^{20}\approx3.5\times10^9$ 种。

动态规划 (dynamic programming, DP) 观察到一件事：整条最优路径的后半段，一定也是从那个中间点出发的最优路径。这条看似平凡的"最优性原理"（Bellman, 1950s）让我们不必再枚举路径，而是为每个状态记一个数：从这里出发到目标的最优代价，叫作代价到终点 (cost-to-go) 或价值函数。有了这张表，每个状态下的最优动作就是"走向代价到终点更小的邻居"。

它在机器人里无处不在：栅格地图上的最短路（Dijkstra、A*）是 DP；LQR（线性二次调节器）用 DP 导出解析的反馈增益；强化学习学的就是价值函数，贝尔曼方程是它的核心；轨迹优化里的 DDP/iLQR 在轨迹附近做 DP。本课先用最直观的格子世界建立图像，再看随机转移，最后看 DP 如何在连续状态里变成 LQR。

Many robot problems are "decisions one step after another": which cell a vacuum robot enters next, what torque an arm applies at each moment, what thrust a drone commands each control cycle. How good a step is depends on its consequences for all later steps. Enumerating every action sequence grows exponentially: 3 choices over 20 steps is $3^{20}\approx3.5\times10^9$ sequences.

Dynamic programming (DP) rests on one observation: the second half of an optimal path is itself an optimal path from that midpoint. This seemingly trivial "principle of optimality" (Bellman, 1950s) means we need not enumerate paths at all: we store one number per state, the optimal cost from here to the goal, called the cost-to-go or value function. With that table, the best action in any state is simply "move to the neighbour with the smaller cost-to-go".

DP is everywhere in robotics: shortest paths on grid maps (Dijkstra, A*) are DP; LQR (the linear-quadratic regulator) uses DP to derive an analytic feedback gain; reinforcement learning learns exactly a value function, with the Bellman equation at its heart; DDP/iLQR in trajectory optimization does DP around a trajectory. This lesson builds the picture on a grid world, adds stochastic transitions, and finally shows DP on continuous states turning into LQR.

2直觉：从目标向外"涨水"Intuition: water rising outward from the goal

在格子地图上，每走进一个格子要付出该格的代价（普通格 1，泥地格 4），墙不能走。我们想知道每个格子到目标的最小总代价 $V(s)$。

值迭代从最笨的猜测开始：目标格 $V=0$，其余格 $V=\infty$（还不知道怎么到）。然后反复"扫一遍"，对每个格子取：

On a grid map, entering a cell costs that cell's price (1 for ordinary cells, 4 for mud) and walls are impassable. We want the minimum total cost $V(s)$ from every cell to the goal.

Value iteration starts from the dumbest guess: $V=0$ at the goal and $V=\infty$ everywhere else (no known way there yet). Then repeatedly sweep, setting every cell to

$$ V_{k+1}(s)=\min_{a}\Big[\ \hl{step}{c(s')}+\hl{cost}{V_k(s')}\ \Big],\qquad s'=\text{the cell reached by action }a,\qquad V(\text{goal})=0 $$

读作：一步的代价 + 邻居已知的最优代价，在所有动作里取最小。第 $k$ 次扫描之后，$V_k(s)$ 就是"至多走 $k$ 步能到目标的最小代价"。于是信息像水波一样从目标向外扩散，一圈一圈把每个格子的 $V$ 填上；再没有格子的值变化时就收敛了。把代价到终点画出来，最优路线就是沿着"最陡下坡"的方向，每个格子里的小箭头指向代价更低的邻居。

用下面的图玩一玩：拖动滑块看第 $k$ 次扫描的结果；在格子上点击或拖动涂墙、泥地，或改变目标；拖动 S 改变起点。

Read: cost of one step + the neighbour's already-known optimal cost, minimized over actions. After sweep $k$, $V_k(s)$ is "the minimum cost of reaching the goal in at most $k$ steps". Information therefore spreads from the goal like ripples, filling in $V$ ring by ring; when no cell changes any more it has converged. Plotting the cost-to-go, the optimal route follows the "steepest descent" and the little arrow in each cell points to a lower-cost neighbour.

Play with it below: drag the slider to see the result of sweep $k$; click or drag on cells to paint walls and mud, or move the goal; drag S to move the start.

FIG 1格子世界里的值迭代Value iteration in a grid world

蓝色越浓表示到目标的代价越小，数字是 $V_k$，小箭头是当前贪心动作，琥珀色粗线是起点 S 按最终 $V$ 走出的最优路线。有琥珀色描边的格子是这一扫描里刚刚变化的格子：它们就是向外扩散的"波前"。"8 方向"允许走斜线（代价乘 $\sqrt2$）。 A more saturated blue means smaller cost to the goal, numbers are $V_k$, the small arrows are the current greedy actions, and the thick amber line is the optimal route from S following the final $V$. Cells with an amber outline are those that just changed in this sweep: they form the outward-moving "wavefront". "8-way" allows diagonal moves (cost times $\sqrt2$).

试一试Try this

按"运行"，看波前从目标扩散到起点；记下它扩散到起点用了多少次扫描。Press "Run" and watch the wavefront spread from the goal to the start; note how many sweeps it takes to reach the start.
用"墙"工具把最优路线上的一个通道堵死：最优路线立刻绕行，起点的 $V$ 变大。Use the "Wall" tool to block a passage on the optimal route: the route detours at once and the start's $V$ grows.
用"泥地"工具在最优路线上铺一块泥地：路线是穿过去还是绕过去，取决于绕路多出的代价是否小于每块泥地多付的 3（4 减去普通格的 1）。Use the "Mud" tool to lay mud across the optimal route: whether the route crosses or avoids it depends on whether the detour costs less than the 3 extra paid per mud cell (4 instead of 1).

核心洞见Key insight

值迭代没有"搜索路径"。它只是反复让每个格子问邻居"你到终点要多少"，自己取最小的一份加上一步的代价。最优路径是读出来的：从任何起点顺着代价下坡走即可。所以换一个起点完全不用重算，只要目标不变，这张表对所有起点都有效，这是 DP 与"为一个起点搜索一条路"的根本不同。

Value iteration does no "path search". It just has every cell keep asking its neighbours "how much from you to the goal?" and add one step's cost to the smallest answer. The optimal path is read off: from any start just walk downhill in cost. Changing the start requires no recomputation: as long as the goal is unchanged the table is valid for every start, which is the fundamental difference between DP and "search for one path from one start".

3贝尔曼最优性原理：为什么不用穷举Bellman's principle: why we need not enumerate

下图是一张小小的"多阶段图"：从起点 S 到终点 G 要经过 4 个阶段，每个阶段 3 个节点，相邻阶段之间每对节点都有一条带代价的边。从 S 到 G 一共有 $3^4=81$ 条路径。穷举要把 81 条路径的代价都加一遍；DP 从 G 往回算，每个节点的 $J$ 只需要看它出发的 3 条边。拖动滑块让 DP 一个阶段一个阶段往回走。

每个节点的数字 $J$ 是"从这里到 G 的最小代价"。看第一个节点是怎么算出来的：它是 3 个"边的代价 + 下一个节点的 $J$"里最小的，下一个节点的 $J$ 已经是最优了，所以不必再看它之后的所有路径。

Below is a little "multi-stage graph": from the start S to the goal G you pass through 4 stages of 3 nodes each, and every pair of nodes in consecutive stages is joined by an edge with a cost. There are $3^4=81$ paths from S to G. Brute force adds up all 81 path costs; DP works backward from G, and each node's $J$ needs only a look at its 3 outgoing edges. Drag the slider to let DP walk back one stage at a time.

Each node's number $J$ is "the minimum cost from here to G". See how the first node's is computed: it is the smallest of 3 values "edge cost + next node's $J$"; the next node's $J$ is already optimal, so we need not look again at any paths beyond it.

FIG 2多阶段图上的反向递推Backward recursion on a multi-stage graph

边上的数字是代价，点击数字可把它加 1（超过 9 回到 1）。节点上方是 $J$。绿色粗边是每个节点的最优后继（$\arg\min$）。滑块到 0 时，沿着绿边从 S 走到 G 的琥珀色路径就是全局最优。试着改一条最优路径上的边，看看 DP 重新给出的路径。 Numbers on edges are costs; click a number to add 1 (wrapping from 9 to 1). Above each node is $J$. Thick green edges mark each node's optimal successor ($\arg\min$). With the slider at 0, the amber path from S to G following the green edges is the global optimum. Try changing an edge on the optimal path and see the path DP returns.

把滑块从右拖到左，观察 $J$ 是怎么一个阶段一个阶段往回填满的。Drag the slider from right to left and watch $J$ fill in stage by stage.
点击最优路径上的一个边代价，把它加大，直到最优路径改道。Click a cost on the optimal path and raise it until the optimal path reroutes.

两种计算量Two amounts of work

$N$ 个阶段、每阶段 $m$ 个节点：穷举要比较 $m^N$ 条路径；DP 只需要 $O(N m^2)$ 次"边的代价 + 后继的 $J$"。在 $m=3,\ N=4$ 时是 81 对 33。$N=20$ 时是 $3^{20}\approx3.5\times10^9$ 对 $\approx 180$。DP 把乘法关系变成了加法关系：这是它最重要的好处。

With $N$ stages of $m$ nodes each, brute force compares $m^N$ paths while DP needs only $O(Nm^2)$ evaluations of "edge cost + successor's $J$". At $m=3,\ N=4$ that is 81 vs. 33; at $N=20$, $3^{20}\approx3.5\times10^9$ vs. about 180. DP turns a multiplicative blow-up into an additive one: its most important benefit.

4加入随机性：离悬崖远一点Adding randomness: stay away from the cliff

真实的机器人不是想走哪就走到哪：轮子打滑，风吹歪了无人机。设想"悬崖行走"：目标在右边，最下面一排是悬崖（掉下去代价 100，游戏结束）。我们执行一个动作时，以概率 $1-p$ 如愿以偿，以概率 $p/2$ 各偏向左右两个垂直方向（"打滑"）。此时下一个状态是随机的，值迭代里的"邻居的 $V$"换成期望：

Real robots do not go exactly where told: wheels slip, wind pushes a drone sideways. Picture "cliff walking": the goal is on the right and the bottom row is a cliff (falling costs 100 and ends the episode). When we take an action, with probability $1-p$ it works, and with probability $p/2$ each it veers to one of the two perpendicular directions ("slip"). The next state is now random, and value iteration's "neighbour's $V$" becomes an expectation:

$$ V(s)=\min_a\ \sum_{s'}\ \hl{prob}{P(s'\mid s,a)}\,\big[\,c(s,a,s')+V(s')\,\big] $$

当 $p=0$ 时最短路径紧贴悬崖边走。当 $p$ 变大，紧贴悬崖的路线每走一格都有 $p/2$ 的概率掉下去，期望代价迅速上升，DP 自己就会把路线移到离悬崖更远的一排。这种"根据噪声自动留出安全余量"的行为，是规划不确定性时 DP 的强项（也是强化学习学到的东西）。拖动 $p$，对比"最优"策略和"按无噪声最短路径照走"的天真策略。

At $p=0$ the shortest path hugs the cliff edge. As $p$ grows, a route along the edge has a $p/2$ chance of falling at every cell, the expected cost jumps, and DP itself moves the route a row away from the cliff. This "automatic safety margin according to the noise" is a strength of DP when planning under uncertainty (and exactly what reinforcement learning learns). Drag $p$ and compare the "optimal" policy with the naive one that just follows the noise-free shortest path.

FIG 3打滑的格子世界：最优策略随噪声改变A slippery grid world: the optimal policy changes with noise

红色格子是悬崖（$V=100$），绿圈是目标。箭头是当前选定策略在各格的动作；琥珀色线是"每步都成功"时的路线。右侧读数里的"掉崖概率"是按所选策略从起点出发、在打滑噪声下最终掉下悬崖的概率（由策略评估精确算出，不是蒙特卡洛）。 Red cells are the cliff ($V=100$) and the green ring is the goal. Arrows are the actions of the selected policy; the amber line is the route if every step succeeds. The "probability of falling" in the readout is the exact probability, under slip noise, that following the selected policy from the start ends in the cliff (computed by policy evaluation, not Monte Carlo).

从 $p=0$ 慢慢加大噪声，找到最优路线从紧贴悬崖跳到远离悬崖的那个 $p$（大约 1%）。Start from $p=0$ and raise the noise slowly: find the $p$ at which the optimal route jumps from hugging the cliff to staying away (about 1%).
设 $p=0.2$，切到"天真策略"：它的期望代价和掉崖概率是最优策略的多少倍？Set $p=0.2$ and switch to the "naive policy": how many times larger are its expected cost and fall probability than the optimal policy's?

与强化学习的联系Link to reinforcement learning

上面这个带"期望"的方程叫贝尔曼最优方程，$P(s'|s,a)$ 是环境模型。值迭代是在知道模型时解它的方法。强化学习处理"不知道 $P$，只能通过试错采样"的情形：Q-learning、DQN 都是在用采样去逼近同一个方程的不动点。因此本课的值迭代，是理解后续强化学习的第一块基石（Part V）。

The equation above with an expectation is the Bellman optimality equation, and $P(s'|s,a)$ is the environment model. Value iteration solves it when the model is known. Reinforcement learning handles the case where $P$ is unknown and only trial-and-error samples are available: Q-learning and DQN approximate the fixed point of the same equation from samples. Value iteration here is therefore the first building block for the reinforcement learning of Part V.

5再看数学The math

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

有限时域 DPFinite-horizon DP

系统 $\mathbf x_{k+1}=f(\mathbf x_k,\mathbf u_k)$，总代价 $\sum_{k=0}^{N-1}\ell(\mathbf x_k,\mathbf u_k)+\ell_f(\mathbf x_N)$。定义价值函数 $V_k(\mathbf x)$：从第 $k$ 步状态 $\mathbf x$ 出发能得到的最小剩余代价。贝尔曼方程从终点往回递推：

System $\mathbf x_{k+1}=f(\mathbf x_k,\mathbf u_k)$, total cost $\sum_{k=0}^{N-1}\ell(\mathbf x_k,\mathbf u_k)+\ell_f(\mathbf x_N)$. Define the value function $V_k(\mathbf x)$: the minimum remaining cost obtainable from state $\mathbf x$ at step $k$. The Bellman equation recurses backward from the end:

$$ V_N(\mathbf x)=\ell_f(\mathbf x),\qquad V_k(\mathbf x)=\min_{\mathbf u}\Big[\ell(\mathbf x,\mathbf u)+V_{k+1}\big(f(\mathbf x,\mathbf u)\big)\Big],\qquad \pi_k(\mathbf x)=\arg\min_{\mathbf u}\Big[\cdots\Big] $$

$V_0(\mathbf x_0)$ 就是整个问题的最优代价，$\pi_k$ 是每步的最优反馈策略：它是状态的函数，不只是一条开环轨迹，所以遇到扰动、偏离轨迹时仍然知道该怎么办。这一点和 6.13 节的轨迹优化（只给一条轨迹）形成对比。

$V_0(\mathbf x_0)$ is the optimal cost of the whole problem and $\pi_k$ is the optimal feedback policy at each step: a function of the state, not just one open-loop trajectory, so it still knows what to do after a disturbance knocks the system off course. This contrasts with the trajectory optimization of Lesson 6.13, which returns a single trajectory.

无限时域与值迭代的收敛Infinite horizon and the convergence of value iteration

带折扣因子 $\gamma\in[0,1)$ 的无限时域问题，价值函数满足不动点方程 $V=\mathcal T V$，其中 $\mathcal T$ 是"贝尔曼算子"。它是压缩映射：

For the infinite-horizon problem with discount $\gamma\in[0,1)$, the value function satisfies the fixed-point equation $V=\mathcal T V$, where $\mathcal T$ is the "Bellman operator". It is a contraction:

$$ (\mathcal T V)(s)=\min_a\sum_{s'}P(s'|s,a)\big[c+\gamma V(s')\big],\qquad \|\mathcal T V-\mathcal T W\|_\infty\le\gamma\,\|V-W\|_\infty\ \Longrightarrow\ \|V_k-V^\star\|_\infty\le\gamma^k\|V_0-V^\star\|_\infty $$

由巴拿赫不动点定理：不动点 $V^\star$ 唯一，且值迭代从任何初值出发都几何级数地收敛到它。FIG 1 的最短路问题相当于 $\gamma=1$，并没有压缩性，但从 $V=\infty$ 出发时，第 $k$ 次扫描恰好得到"至多 $k$ 步"的最优值，所以最多 $|S|$ 次扫描收敛（Bellman–Ford 的思路）。更聪明的"按代价从小到大扩展"的次序就是 Dijkstra 算法：每个格子只处理一次。

By Banach's fixed-point theorem the fixed point $V^\star$ is unique and value iteration converges to it geometrically from any starting point. The shortest-path problem of FIG 1 is the $\gamma=1$ case, which is not a contraction, but starting from $V=\infty$ sweep $k$ yields exactly the optimal "within $k$ steps" values, so at most $|S|$ sweeps suffice (the Bellman–Ford view). The smarter ordering "expand cells in increasing cost" is Dijkstra's algorithm: each cell is processed once.

LQR：连续状态里的 DPLQR: DP on a continuous state

当动力学是线性的 $\mathbf x_{k+1}=A\mathbf x_k+B\mathbf u_k$、代价是二次的 $\mathbf x^\top Q\mathbf x+\mathbf u^\top R\mathbf u$（终端 $\mathbf x^\top Q_f\mathbf x$）时，贝尔曼方程可以精确求解：价值函数仍然是二次的，$V_k(\mathbf x)=\mathbf x^\top P_k\mathbf x$，只需递推一个矩阵（Riccati 递推）：

When the dynamics are linear, $\mathbf x_{k+1}=A\mathbf x_k+B\mathbf u_k$, and the cost is quadratic, $\mathbf x^\top Q\mathbf x+\mathbf u^\top R\mathbf u$ (terminal $\mathbf x^\top Q_f\mathbf x$), the Bellman equation can be solved exactly: the value function stays quadratic, $V_k(\mathbf x)=\mathbf x^\top P_k\mathbf x$, and only a matrix needs recursing (the Riccati recursion):

$$ P_N=Q_f,\qquad K_k=\big(R+B^\top P_{k+1}B\big)^{-1}B^\top P_{k+1}A,\qquad P_k=Q+A^\top P_{k+1}\big(A-BK_k\big),\qquad \mathbf u_k=-K_k\mathbf x_k $$

推导只有两步：把 $V_{k+1}=\mathbf x^\top P_{k+1}\mathbf x$ 代入贝尔曼方程，里面的 $\min_{\mathbf u}$ 是 $\mathbf u$ 的二次函数，令导数为零得到 $\mathbf u=-K_k\mathbf x$；再把它代回去得到新的二次型 $P_k$。当时域很长时 $P_k$ 收敛到常数矩阵 $P_\infty$，增益 $K$ 也不再变化（稳态 LQR，FIG 4 里能看到）。这是 DP 在连续空间里仅有的几个能不"离散化"的例子，也是控制课里最重要的结论之一（Part IV）。

The derivation takes two steps: substitute $V_{k+1}=\mathbf x^\top P_{k+1}\mathbf x$ into the Bellman equation; the inner $\min_{\mathbf u}$ is a quadratic in $\mathbf u$, and zeroing its derivative gives $\mathbf u=-K_k\mathbf x$; substituting back yields the new quadratic form $P_k$. For long horizons $P_k$ converges to a constant $P_\infty$ and the gain $K$ stops changing (steady-state LQR, visible in FIG 4). It is one of the few cases where DP on a continuous space needs no discretization, and one of the most important results in control (Part IV).

维数灾难The curse of dimensionality

离散化的 DP 要存一张覆盖所有状态的表。每一维取 $n$ 个格点、$d$ 维状态，就有 $n^d$ 个状态：$n=100$，$d=2$ 是 $10^4$（FIG 1 只有 $12\times8$ 格），$d=6$（比如一个 3 关节机械臂的位置和速度各 3 维）就是 $10^{12}$。这就是 Bellman 所说的"维数灾难"，也是为什么机器人里的高维问题要用近似：线性二次（LQR）、在轨迹附近局部近似（DDP/iLQR）、或者用神经网络表示价值函数（深度强化学习）。

Discretized DP stores a table over all states. With $n$ grid points per dimension and a $d$-dimensional state there are $n^d$ states: $n=100$, $d=2$ is $10^4$ (FIG 1 has only $12\times8$ cells); $d=6$ (say the positions and velocities of a 3-joint arm) is $10^{12}$. This is Bellman's "curse of dimensionality", and the reason high-dimensional robotics problems use approximations: linear-quadratic (LQR), local approximation around a trajectory (DDP/iLQR), or a neural network for the value function (deep reinforcement learning).

6机器人中的它：Riccati 递推与 LQRIn robotics: the Riccati recursion and LQR

一个一维小车（双积分器）：状态 $\mathbf x=(p,v)$，控制 $u$ 是加速度，$\Delta t=0.1$ s，$A=\left[\begin{smallmatrix}1&\Delta t\\0&1\end{smallmatrix}\right],\ B=\left[\begin{smallmatrix}\Delta t^2/2\\ \Delta t\end{smallmatrix}\right]$。代价 $Q=\operatorname{diag}(1,0.1)$，$Q_f=Q$，$R=r$：要把小车平稳地停在原点。下图是 $k=0$ 时的价值函数 $V_0(\mathbf x)=\mathbf x^\top P_0\mathbf x$ 的等值线（椭圆）：越靠内的椭圆，剩余代价越小。拖动橙色的初始状态 $\mathbf x_0$，看小车沿着 DP 求出的反馈律回到原点的轨迹。

读数里有一个重要的"验算"：用 DP 递推出的 $P_0$ 算的 $V_0(\mathbf x_0)=\mathbf x_0^\top P_0\mathbf x_0$，应该和真的仿真一遍这条闭环轨迹并把每一步的代价累加起来的结果完全相同。这就是"价值函数 = 最优剩余代价"的含义。

A 1D cart (a double integrator): state $\mathbf x=(p,v)$, control $u$ is acceleration, $\Delta t=0.1$ s, $A=\left[\begin{smallmatrix}1&\Delta t\\0&1\end{smallmatrix}\right],\ B=\left[\begin{smallmatrix}\Delta t^2/2\\ \Delta t\end{smallmatrix}\right]$. Cost $Q=\operatorname{diag}(1,0.1)$, $Q_f=Q$, $R=r$: bring the cart smoothly to rest at the origin. The figure shows the level sets (ellipses) of the value function at $k=0$, $V_0(\mathbf x)=\mathbf x^\top P_0\mathbf x$: the further inside, the smaller the remaining cost. Drag the amber initial state $\mathbf x_0$ and watch the cart return to the origin under the DP-derived feedback law.

The readout contains an important check: $V_0(\mathbf x_0)=\mathbf x_0^\top P_0\mathbf x_0$ from the DP recursion must exactly equal what you get by really simulating this closed-loop trajectory and summing the cost of every step. That is what "value function = optimal remaining cost" means.

FIG 4LQR：价值函数是椭圆LQR: the value function is an ellipse

反馈增益 $K_k$ 随时刻 $k$feedback gain $K_k$ vs. step $k$

左：相平面（横轴位置 $p$，纵轴速度 $v$），紫色椭圆是 $V_0$ 的等值线，通过 $\mathbf x_0$ 的那条加粗；琥珀色是有限时域最优反馈（时变 $K_k$）的闭环轨迹，青色虚线是稳态增益 $K_\infty$ 的轨迹。右：增益的两个分量 $K_k=(k_p,k_v)$：离终点很远时它们是常数（等于稳态 LQR），只在接近终点的最后几步才变化。$r$ 越大，控制越"吝啬"，同一个 $\mathbf x_0$ 的剩余代价越大（椭圆收紧）并且椭圆向速度轴倾斜，轨迹越慢。 Left: the phase plane (horizontal $p$, vertical $v$); purple ellipses are level sets of $V_0$, the one through $\mathbf x_0$ bold; amber is the closed-loop trajectory of the finite-horizon optimal feedback (time-varying $K_k$), the dashed cyan one uses the steady-state gain $K_\infty$. Right: the two components of the gain $K_k=(k_p,k_v)$: far from the end they are constant (the steady-state LQR) and change only in the last few steps. The larger $r$, the "stingier" the control: the remaining cost of a given $\mathbf x_0$ grows (the ellipses tighten) and the ellipses tilt toward the velocity axis, and the trajectory slows.

拖动 $\mathbf x_0$：轨迹形状变了吗？价值 $V_0(\mathbf x_0)$ 随 $\mathbf x_0$ 怎么变？（二次增长：把 $\mathbf x_0$ 放大一倍，$V_0$ 变成 4 倍。）Drag $\mathbf x_0$: does the trajectory shape change? How does $V_0(\mathbf x_0)$ vary? (Quadratically: doubling $\mathbf x_0$ multiplies $V_0$ by 4.)
把 $r$ 从 0.01 拖到 10：增益 $K$ 变小，轨迹变慢，椭圆收紧并转向速度轴。Drag $r$ from 0.01 to 10: the gain $K$ shrinks, the trajectory slows, and the ellipses tighten and tilt toward the velocity axis.
把时域 $N$ 缩到 5：增益不再是常数，整条轨迹的 $K_k$ 都随时间变化；加长 $N$，开头部分的 $K_k$ 趋于稳态。Shrink the horizon $N$ to 5: the gain is no longer constant and $K_k$ varies along the whole trajectory; lengthen $N$ and the early $K_k$ settle to the steady state.

真实系统里In real systems

LQR 是两轮自平衡车、倒立摆、四旋翼悬停的标准控制器：把非线性系统在平衡点附近线性化，解 Riccati 方程得到常数增益 $K$，实时代价只是一次矩阵乘法 $\mathbf u=-K\mathbf x$。把同样的递推应用到"沿一条轨迹线性化"的系统上，就是 iLQR/DDP，是轨迹优化（6.13 节）和接触丰富的机器人运动规划的常用求解器。栅格上的 DP 则是 Dijkstra、A*、Dubins/Reeds–Shepp 状态格规划的内核。

LQR is the standard controller for self-balancing two-wheelers, inverted pendulums and quadrotor hover: linearize the nonlinear system about the equilibrium, solve the Riccati equation for a constant gain $K$, and the real-time cost is a single matrix product $\mathbf u=-K\mathbf x$. Apply the same recursion to a system linearized along a trajectory and you have iLQR/DDP, a common solver for trajectory optimization (Lesson 6.13) and contact-rich robot motion planning. DP on a grid is the kernel of Dijkstra, A*, and state-lattice planners with Dubins/Reeds–Shepp primitives.

7常见误区Common pitfalls

误区 1：以为 DP 只能做离散问题Pitfall 1: believing DP only handles discrete problems

贝尔曼方程对连续状态同样成立（FIG 4 的 LQR 就是）。只是在一般情形下，$V$ 是个没有解析形式的函数，只能离散化、或用函数逼近（插值、神经网络）。线性二次和少数结构化问题是例外，价值函数有闭式。

The Bellman equation holds just as well for continuous states (the LQR of FIG 4). In general, though, $V$ is a function without a closed form, and one must discretize or use function approximation (interpolation, neural networks). Linear-quadratic problems and a few other structured cases are the exceptions, with closed-form value functions.

误区 2：把"贪心"与"最优"混为一谈Pitfall 2: confusing "greedy" with "optimal"

"每一步走离目标最近的邻居"是贪心，会撞进死胡同（FIG 1 里把墙堵死试试）。DP 里的"贪心"是对 $V$ 贪心，而 $V$ 已经包含了后续所有步骤的最优后果，所以局部的一步选择才是全局最优的。区别在于你贪的是哪张表。

"Always step to the neighbour closest to the goal" is greedy and walks into dead ends (try walling off a passage in FIG 1). The "greedy" in DP is greedy with respect to $V$, which already contains the optimal consequences of all later steps, so a locally chosen step is globally optimal. What matters is which table you are greedy about.

误区 3：忽略折扣、环路和"不可达"Pitfall 3: ignoring discounts, cycles and unreachable states

无折扣 ($\gamma=1$) 的问题只有在"所有策略最终都会到达吸收状态"或"环路代价为正"时才有有限的最优值；否则值迭代会发散，或给出"原地打转"的退化策略。真实代价里要保证"每走一步都有正的代价"，或者设置 $\gamma<1$。另外 $V=\infty$ 的格子（目标不可达）在数值上要用一个大数或显式处理，别让 $\infty-\infty$ 出现 NaN。

An undiscounted ($\gamma=1$) problem has a finite optimum only if "every policy eventually reaches an absorbing state" or "cycles have positive cost"; otherwise value iteration diverges or returns a degenerate policy that idles in place. Make sure real costs give "positive cost per step" or set $\gamma<1$. Also, cells with $V=\infty$ (goal unreachable) need a large sentinel or explicit handling so $\infty-\infty$ does not produce NaN.

误区 4：Riccati 递推的方向搞反Pitfall 4: running the Riccati recursion in the wrong direction

$P_k$ 是从终点 $N$ 往回算的，而闭环仿真是从 $k=0$ 往前走的：先把所有 $K_k$ 反向算出来存好，再前向使用。把 $K_k$ 的下标当成"前向递推"会得到错误的增益。若 $R+B^\top PB$ 接近奇异（$R$ 太小而 $B$ 方向有问题），求逆会数值不稳；LQR 要求 $Q\succeq0,\ R\succ0$。

$P_k$ is computed backward from the end $N$, while the closed-loop simulation runs forward from $k=0$: compute and store all $K_k$ backward, then use them forward. Treating the index of $K_k$ as a forward recursion yields wrong gains. If $R+B^\top PB$ is nearly singular (tiny $R$ with a poor $B$ direction), the inverse becomes numerically unstable; LQR needs $Q\succeq0,\ R\succ0$.

8小练习Check yourself

1. 节点 A 有两条出边：到 B 的边代价 2，到 C 的边代价 5。已知 $J(B)=4,\ J(C)=2$。$J(A)$ 和最优后继是？1. Node A has two outgoing edges: to B at cost 2 and to C at cost 5. Given $J(B)=4,\ J(C)=2$, what are $J(A)$ and its optimal successor?

$J(A)=\min(2+4,\ 5+2)=\min(6,7)=6$，经 B。注意不能只看边的代价（2 < 5）：到 C 的边贵，但 C 之后更便宜；也不能只看 $J$（$J(C)<J(B)$）。要看"边 + $J$"的和。$J(A)=\min(2+4,\ 5+2)=\min(6,7)=6$, via B. You cannot look at edge costs alone (2 < 5) or at $J$ alone ($J(C)<J(B)$); the sum "edge + $J$" is what counts.

2. 一张多阶段图有 10 个阶段，每个阶段 5 个节点，相邻阶段的每对节点之间都有边。DP 要计算多少条边的代价（"边 + 后继 $J$"）？（穷举有 $5^{10}\approx9.8\times10^6$ 条路径。）2. A multi-stage graph has 10 stages of 5 nodes each, with an edge between every pair of nodes in consecutive stages. How many edges does DP evaluate ("edge + successor's $J$")? (Brute force has $5^{10}\approx9.8\times10^6$ paths.)

相邻阶段之间有 $5\times5=25$ 条边，10 个阶段有 9 个这样的间隔，所以 $9\times25=225$ 次。从百万量级降到几百，这就是 DP 的威力。Between consecutive stages there are $5\times5=25$ edges, and 10 stages have 9 such gaps, so $9\times25=225$ evaluations. Millions down to a couple of hundred: that is the power of DP.

3. 在 FIG 3 的悬崖行走里，打滑概率 $p$ 增大时，最优路线为什么离悬崖越来越远？3. In the cliff-walking of FIG 3, why does the optimal route move away from the cliff as the slip probability $p$ grows?

DP 的"期望"把掉崖的小概率乘上很大的惩罚后加了进去；沿边走 $\approx7$ 格，累计掉崖概率可观，期望惩罚远大于多绕两步的 2。只要 $p$ 超过一个很小的阈值，DP 就自己选择了更安全的路线。DP's expectation multiplies the small chance of falling by the large penalty and adds it in; along about 7 edge cells the accumulated fall probability is substantial, and the expected penalty far exceeds the 2 extra steps of a detour. Once $p$ passes a small threshold, DP picks the safer route by itself.

4. 价值函数 $V(\mathbf x)=\mathbf x^\top P\mathbf x$，其中 $P=\left[\begin{smallmatrix}2&0\\0&0.5\end{smallmatrix}\right]$。状态 $\mathbf x=(1,2)$ 的剩余代价是？4. The value function is $V(\mathbf x)=\mathbf x^\top P\mathbf x$ with $P=\left[\begin{smallmatrix}2&0\\0&0.5\end{smallmatrix}\right]$. What is the remaining cost of state $\mathbf x=(1,2)$?

$\mathbf x^\top P\mathbf x=2\cdot1^2+0.5\cdot2^2=2+2=4$。$\mathbf x^\top P\mathbf x=2\cdot1^2+0.5\cdot2^2=2+2=4$.

5. 把一个有 6 个状态变量的系统，每个变量离散成 50 个格点，做表格式 DP。状态总数约为？5. A system with 6 state variables is discretized into 50 grid points per variable for tabular DP. About how many states are there?

$50^6=1.5625\times10^{10}$。状态数随维度指数增长，这就是维数灾难。所以高维问题要用 LQR 这类解析结构、局部近似（DDP/iLQR）或函数逼近（神经网络）。$50^6=1.5625\times10^{10}$. The state count grows exponentially with dimension: the curse of dimensionality. High-dimensional problems therefore use analytic structure such as LQR, local approximation (DDP/iLQR) or function approximation (neural networks).

9延伸阅读Further reading

R. S. Sutton & A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Ch. 3–4 — MDP、贝尔曼方程与动态规划（含悬崖行走例子）MDPs, Bellman equations and dynamic programming (including the cliff-walking example)
D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. I, 4th ed., Athena Scientific, 2017 — DP 的经典教材：最优性原理、最短路与 LQRthe classic DP text: the principle of optimality, shortest paths and LQR
R. Bellman, Dynamic Programming, Princeton University Press, 1957 — 原始来源，"维数灾难"一词出自此书the original source; the phrase "curse of dimensionality" comes from this book
B. D. O. Anderson & J. B. Moore, Optimal Control: Linear Quadratic Methods, Prentice-Hall, 1990 — LQR 与 Riccati 方程LQR and the Riccati equation
E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, 1959 — 最短路算法，是按序扩展的值迭代the shortest-path algorithm, i.e. value iteration with an ordered expansion