第 4 章：序贯问题（Sequential Problems）
章节作者：Mykel J. Kochenderfer 章节定位：理论篇第四章，把第 3 章的"单步决策"推广为"在时间上依次做出多个决策"的序贯决策问题。核心抽象是 Markov decision process（MDP），核心工具是 dynamic programming 类的四族算法（policy evaluation / policy iteration / value iteration / asynchronous value iteration），核心变体是 closed-loop vs. open-loop planning 与多类函数近似、在线搜索与直接策略搜索。
4.1 Formulation
作者在开篇点出本章与第 3 章的承接关系：第 3 章讨论的是"一次性做出单个决策"的问题，但许多重要问题要求决策者在多个时间步上依次做出决策。"最大期望效用"的基本原则在序贯场景下仍然适用，但最优决策需要对未来"动作—观察"序列做整体推理，而不是仅在当前步上贪心地最大化即时奖励。本章的讨论被限定在两类理想化假设之下——模型已知（model is known）且环境完全可观察（fully observable），这两个假设将分别在第 5、6 章中被放宽。
4.1.1 Markov Decision Processes
在 Markov decision process（MDP）中，智能体在时刻 \(t\) 基于对状态 \(s_t\) 的观察选择动作 \(a_t\)，并获得即时奖励 \(r_t\)；下一个状态 \(s_{t+1}\) 由 \(s_t\) 与 \(a_t\) 通过概率转移产生。所谓 Markov 假设，是指"下一个状态仅依赖于当前状态与当前动作，而与任何更早的状态或动作无关"。一个 MDP 可以用图 4.1a 所示的决策网络表示：存在从历史动作 \(A_{0:t-1}\) 与历史状态 \(S_{0:t}\) 到当前动作 \(A_t\) 的信息边（图中未显式画出），效用函数被分解为各时刻的奖励 \(R_{0:t}\)。
本章聚焦于 stationary MDP——其状态转移 \(P(S_{t+1} \mid S_t, A_t)\) 与奖励分布 \(P(R_t \mid A_t, S_t)\) 不随时间变化。stationary MDP 可以用图 4.1b 所示的 dynamic decision diagram 更紧凑地表示：状态转移函数 \(T(s' \mid s, a)\) 给出在状态 \(s\) 采取动作 \(a\) 后转移到状态 \(s'\) 的概率；奖励函数 \(R(s, a)\) 给出该步的期望即时奖励。本节假定奖励函数是 \((s, a)\) 的确定性函数，但这一简化并不是必须的。
作者用航空器碰撞告警问题作为贯穿本章的运行实例：状态表示本机与入侵机的位置与速度；动作表示"爬升、下降或保持高度"；与入侵机相撞带来大的负奖励，"爬升"或"下降"带来小的负奖励。
4.1.2 Utility and Reward
MDP 中的奖励被视作"加性分解的效用函数（additively decomposed utility function）"的组成部分（参见 3.1.6 节）。在有限时域（finite horizon）问题中，若共做 \(n\) 次决策，则一个由 \(r_{0:n-1}\) 构成的奖励序列所对应的效用就是它们的简单求和
\(\sum_{t=0}^{n-1} r_t. \tag{4.1}\)
在无限时域（infinite horizon）问题中，决策次数没有上限，奖励之和可能发散。考虑一个直观反例：策略 A 每步获得奖励 1，策略 B 每步获得奖励 100——理性智能体显然应偏好 B，但两者给出的期望效用都是无穷大。为处理这种"无穷发散"问题，无限时域问题通常采用以下三种"个体奖励聚合为总效用"的范式之一。
第一种是折扣奖励（discounted reward）：在 \(0\) 与 \(1\) 之间引入折扣因子 \(\gamma\)，效用定义为
只要 \(0 \le \gamma < 1\) 且每步奖励是有限的，则上述级数一定收敛。\(\gamma\) 的引入使"当前的奖励"在数值上比"未来同等的奖励"更值钱——这一思想在经济学中也有对应的概念。第二种是平均奖励（average reward）：效用定义为
本书主要采用折扣奖励 + 无限时域（discounted infinite horizon）的设定。
4.2 Dynamic Programming
求最优策略的过程可以借助一类统称为 dynamic programming 的计算技术。本章聚焦于 MDP 上的 dynamic programming，但 dynamic programming 本身是一种通用技术，可应用于诸多其他问题——例如计算 Fibonacci 数列、求两个字符串的最长公共子序列、求 hidden Markov model 中最可能的状态序列。一般而言，用 dynamic programming 求解 MDP 远比暴力枚举高效。
4.2.1 Policies and Utilities
MDP 中的"策略（policy）"决定在给定历史状态下应采取何种动作。具体而言，给定历史 \(h_t = (s_{0:t}, a_{0:t-1})\)，时刻 \(t\) 的策略输出 \(\pi_t(h_t)\)。由于未来的状态序列与奖励仅依赖于当前状态与当前动作（由图 4.1a 的条件独立性假设保证），我们仅需关注依赖于当前状态的策略（即可将策略简化为 \(\pi(s)\)）。
对无限时域 MDP 而言，由于状态转移与奖励都是 stationary 的，还可以进一步将注意力限定在 stationary 策略上——用 \(\pi(s)\) 表示平稳策略 \(\pi\) 在状态 \(s\) 下采取的动作（不带时间下标）。但对有限时域问题而言，按"还剩多少步"切换动作选择可能是有利的——作者用"打篮球：除非比赛只剩几秒钟，否则一般不应在半场投球"作为这一现象的直观例子。
执行策略 \(\pi\) 从状态 \(s\) 出发所获得的期望效用记为 \(U^\pi(s)\)，在 MDP 文献中常被称为价值函数（value function）。最优策略 \(\pi^*\) 是使期望效用最大化的策略
\(\pi^*(s) = \arg\max_\pi U^\pi(s) \tag{4.4}\)
对所有状态 \(s\) 成立。在不同的模型上，可能存在多个最优策略。
4.2.2 Policy Evaluation
计算"执行某策略所获得的期望效用"称为策略评估（policy evaluation）。可以用 dynamic programming 评估策略 \(\pi\) 在 \(t\) 步内的期望效用：不执行任何步时 \(U_0^\pi(s) = 0\)；执行一步时 \(U_1^\pi(s) = R(s, \pi(s))\)，即第一步的期望奖励。若已知执行 \(\pi\) 走 \(t-1\) 步的期望效用，则执行 \(t\) 步的期望效用可递推为
其中 \(\gamma\) 是折扣因子（若不使用折扣可设为 1）。Algorithm 4.1 给出了按任意 \(n\) 步迭代计算策略期望效用的方法：对每个时刻 \(t\) 从 \(1\) 到 \(n\)，按上式更新所有状态 \(s\) 的 \(U_t^\pi(s)\)。
对无限时域 + 折扣奖励的情形，有
只要迭代次数足够多，迭代式策略评估（iterative policy evaluation）就能把 \(U^\pi\) 计算到任意精度。另一种思路是直接解一个 \(n\) 元线性方程组（\(n\) 为状态数）：用矩阵形式可将 (4.6) 写为
\(U^\pi = R^\pi + \gamma T_\pi U^\pi, \tag{4.7}\)
其中 \(U^\pi\) 与 \(R^\pi\) 是 \(n\) 维向量，\(T_\pi\) 是 \(n \times n\) 矩阵，\(T_\pi^{ij}\) 表示由第 \(i\) 个状态转移到第 \(j\) 个状态的概率。直接求解上式等价于解线性方程组
其求解代价为 \(O(n^3)\)。
4.2.3 Policy Iteration
策略评估可嵌入一个称为"策略迭代（policy iteration）"的通用过程，用于求最优策略 \(\pi^*\)（Algorithm 4.2）。策略迭代以任意策略 \(\pi_0\) 为起点，反复执行以下两步——
- 策略评估：给定当前策略 \(\pi_k\)，计算 \(U^{\pi_k}\)。
- 策略提升：利用 \(U^{\pi_k}\)，按 \(\pi_{k+1}(s) = \arg\max_a (R(s,a) + \gamma \sum_{s'} T(s' \mid s, a) U^{\pi_k}(s'))\) 对所有状态 \(s\) 计算新策略。
直到不再有改进为止。因为每一步都会带来改进且策略总数有限，算法必终止于一个最优解。
策略迭代有许多变体。其中一种"修正策略迭代（modified policy iteration）"使用有限次迭代式策略评估来近似 \(U^{\pi_k}\)，而不必每步都精确求解效用函数。
4.2.4 Value Iteration
策略迭代的一个替代方案是价值迭代（value iteration, Algorithm 4.3），它因简单易实现而被广泛使用。首先考虑"无折扣、时域长度为 \(n\)"的最优价值函数 \(U_n\) 的计算：边界 \(U_0(s) = 0\)，并按以下递推式由 \(U_{n-1}\) 求 \(U_n\)
对无限时域 + 折扣因子 \(\gamma\) 的情形，可证明最优策略的价值满足 Bellman 方程
注意 \(U^*\) 同时出现在方程两端。价值迭代用 (4.12) 反复更新对 \(U^*\) 的估计。一旦获得 \(U^*\)，可由下式抽取最优策略
Algorithm 4.3 将 \(U_0\) 初始化为 0，但可以证明：在任意有界初始化（即 \(|U_0(s)| < \infty\) 对所有 \(s\)）下价值迭代都会收敛。实践中常见的做法是"以对最优价值函数的猜测作为初值"，以期加快收敛。
Algorithm 4.3 的循环常以 \(\| U_k - U_{k-1} \| < \delta\) 为终止条件，其中 \(\|\cdot\|\) 是 max 范数（\(\|U\| = \max_s |U(s)|\)）。量 \(\| U_k - U_{k-1} \|\) 称为 Bellman 残差（Bellman residual）。若想保证"对价值函数的估计在所有状态上都与 \(U^*\) 相差不超过 \(\varepsilon\)"，则应取 \(\delta = \varepsilon (1-\gamma) / \gamma\)。当 \(\gamma\) 趋近于 1 时，终止阈值趋于更小的值，意味着更慢的收敛——直观上，未来奖励的折扣越弱，迭代需要看到的"等效前瞻"就越远。
若已知 \(\| U_k - U^* \| < \varepsilon\)，则可约束"由 \(U_k\) 抽出的策略"的策略损失。设抽出的策略为 \(\pi\)，策略损失定义为 \(\| U^\pi - U^* \|\)。可证明 \(\| U_k - U^* \| < \varepsilon\) 蕴含策略损失小于 \(2\varepsilon \gamma / (1-\gamma)\)。
4.2.5 Grid World Example
为具体说明价值迭代，作者引入一个 \(10 \times 10\) 的网格世界（grid world）问题。网格中的每个格子对应一个 MDP 状态；可用动作为上、下、左、右。每个动作的效果是随机的：以 \(0.7\) 的概率在指定方向前进一步，以 \(0.1\) 的概率在另外三个方向中的每一个上前进一步；若撞到外边界，则原地不动。撞到外边界带来 \(-1\) 的即时奖励；以下四个格子在进入时给出即时奖励
- \((8, 9)\)：\(+10\)
- \((3, 8)\)：\(+3\)
- \((5, 4)\)：\(-5\)
- \((8, 4)\)：\(-10\)
坐标采用矩阵约定：第一个坐标是从顶部数起的行号，第二个坐标是从左侧数起的列号。\(+10\) 与 \(+3\) 格子是吸收状态（absorbing states）——进入后不再产生任何奖励。
图 4.2a 展示了以折扣因子 \(\gamma = 0.9\) 跑一轮价值迭代后的结果：第一轮后，价值函数退化为"最大期望即时奖励"\(\max_a R(s, a)\)；灰色箭头指示由 (4.13) 得到的最优动作。内部格子的所有动作都最优；邻近边界的格子则倾向于选择"远离边界"的动作。
图 4.2b 展示了第二轮迭代的结果：具有非零奖励的状态价值保持不变，但价值开始扩散到相邻格子；价值反映"两步后"的期望折扣奖励。因此，离吸收状态或边界一格以上的格子价值为 0；一步之内的格子则已被更新为"指向正奖励、远离负奖励"的最优动作。
图 4.3a 与 4.3b 分别给出第三轮与第四轮后的价值函数与策略：\(+3\) 与 \(+10\) 格子的价值在网格上向外扩散；价值扩散得越远，各格子的最优动作之间的并列就越少。
图 4.4a 与 4.4b 分别给出在 \(\gamma = 0.9\) 与 \(\gamma = 0.5\) 下价值函数收敛后的结果。当 \(\gamma = 0.9\) 时，连网格左侧的格子也具有正价值；当 \(\gamma = 0.5\) 时，奖励折扣更陡，\(+3\) 与 \(+10\) 价值的扩散范围明显缩小。折扣陡度对策略的影响在格子 \((4, 8)\) 上最为明显：当 \(\gamma = 0.5\) 时，最优策略是直奔 \(+3\) 格子；当 \(\gamma = 0.9\) 时，最优策略是奔向 \(+10\) 格子。
4.2.6 Asynchronous Value Iteration
4.2.4 节的标准价值迭代在每一轮对所有状态同时更新 \(U_{k+1}\)。在异步价值迭代（asynchronous value iteration）中，每一轮只更新状态的某个子集。可以证明：只要每个状态在迭代过程中被无穷次地更新，价值函数就保证收敛到最优价值函数。
Gauss-Seidel 价值迭代是异步价值迭代的一种特例：它按某种状态顺序遍历所有状态并执行以下更新
由于 Gauss-Seidel 价值迭代"原地"更新状态值，内存中只需保留一份状态值（而不是新旧两份）。此外，Gauss-Seidel 在合适的状态遍历顺序下常常比标准价值迭代收敛更快。
4.2.7 Closed- and Open-Loop Planning
使用模型在序贯问题中选择动作的过程称为"规划（planning）"。规划通常分为两大类方法——闭环规划（closed-loop planning）考虑未来的状态信息；本章所讨论的 dynamic programming 类算法都属于这一类：它们构造一个反应式计划（即策略），能根据动作执行过程中实际产生的不同结果做出反应。与之相对，开环规划（open-loop planning）不考虑未来的状态信息；许多路径规划算法属于这一类：它们构造一个静态的动作序列。
作者用图 4.5 所示的例子直观地说明闭环规划的优势。该例中有 9 个状态，从 \(s_0\) 出发；共有两个决策步，每步可在"向上（黑色箭头）"与"向下（灰色箭头）"之间选择。动作效果是确定性的——除了"从 \(s_0\) 向上"这一动作：以 \(0.5\) 的概率转移到 \(s_1\)，以 \(0.5\) 的概率转移到 \(s_2\)。状态 \(s_4\) 与 \(s_6\) 的奖励为 \(30\)，状态 \(s_7\) 与 \(s_8\) 的奖励为 \(20\)。
该例共有四种开环方案：(up, up)、(up, down)、(down, up)、(down, down)。按图 4.5 给出的奖励设置可以直接算出它们的期望效用：
- \(U(\text{up, up}) = 0.5 \times 30 + 0.5 \times 0 = 15\)
- \(U(\text{up, down}) = 0.5 \times 0 + 0.5 \times 30 = 15\)
- \(U(\text{down, up}) = 20\)
- \(U(\text{down, down}) = 20\)
按开环方案的集合，从 \(s_0\) 出发"向下"是最佳选择——期望奖励 20 优于 15。
而闭环规划则可以利用"在观察第一个动作的结果之后再做第二个决策"这一额外信息：从 \(s_0\) 选择"向上"之后，可以根据实际落到 \(s_1\) 还是 \(s_2\) 来分别选择"向下"或"向上"，从而保证得到 30 的奖励。这恰好是任何"在 \(s_0\) 之后不能再次观察"的方案都达不到的。两种规划范式的差距在此例中从 15（或 20）跳到了 30。
在动作效果具有不确定性的序贯问题中，闭环规划相对开环规划往往具有显著优势。但在一些领域中，状态空间的规模使闭环规划方法（如价值迭代）不可行；开环规划算法虽然在原则上不是最优的，却可以提供令人满意的性能——尤其是当状态空间爆炸使得为每个状态都存一个动作变得不切实际时。本书将聚焦于闭环规划方法以及"在保留利用未来信息能力的前提下处理大规模问题"的方法。
4.3 Structured Representations
本章前述 dynamic programming 算法都假设状态空间是离散的。若状态空间由 \(n\) 个二元变量决定，则离散状态数为 \(2^n\)——这种指数增长把价值迭代与策略迭代等算法的直接应用限制在"状态变量数有限"的问题上。本节讨论利用问题的结构来处理更高维问题的方法。
4.3.1 Factored Markov Decision Processes
Factored Markov decision process 使用 dynamic decision network 来紧凑地表示状态转移与奖励函数；动作、奖励与状态都可以被分解为多个节点。图 4.6 给出了一个 factored MDP 的例子：含 2 个决策变量（\(A\) 与 \(F\)）、3 个状态变量（\(B\)、\(D\)、\(G\)）和 2 个奖励变量（\(C\) 与 \(E\)）。
条件概率分布与奖励函数可以用 decision tree 进一步压缩表示。例如图 4.7a 中以表格形式给出的 \(P(G_{t+1} \mid D_t, F_t, G_t)\) 可用图 4.7b 的 decision tree 表示。引入 decision diagram（而不是 decision tree）可获得更高的紧凑性——在 tree 中除根节点外的所有节点都恰好有 1 个父节点，而 decision diagram 中的节点可以有多个父节点。图 4.8 给出同一棵 decision tree 与等价的 decision diagram：decision tree 需要 5 个叶节点，decision diagram 只需要 2 个叶节点。
4.3.2 Structured Dynamic Programming
存在若干种面向 factored MDP 的 dynamic programming 算法。Structured value iteration、structured policy iteration 等算法在 decision tree 的叶子上执行更新（而不是在所有状态上执行更新），从而在以下两个层面获得效率——把状态聚类到一起以减少更新量、利用奖励与价值函数的加性分解。所得到的策略以 decision tree 表示：内部节点对应"对状态变量的测试"，叶节点对应动作。
4.4 Linear Representations
本章前述方法都要求问题具有离散的状态空间。连续问题当然可以离散化后求解，但当状态或动作空间很大时离散化未必可行。本节给出"对满足一定准则的连续状态—动作空间求精确最优策略"的方法，其适用条件是：
- 动力学是线性高斯的（dynamics are linear Gaussian）。状态转移函数具有形式
\(T(z \mid s, a) = \mathcal{N}(z \mid T_s s + T_a a, \Sigma), \tag{4.15}\)
其中 \(T_s\) 与 \(T_a\) 是由 \(s\) 与 \(a\) 决定下一状态 \(z\) 的均值的矩阵，\(\Sigma\) 是控制动力学噪声大小的协方差矩阵。
- 奖励是二次的（reward is quadratic）。奖励函数具有形式
\(R(s, a) = s^\top R_s s + a^\top R_a a, \tag{4.16}\)
其中 \(R_s = R_s^\top \le 0\)，\(R_a = R_a^\top < 0\)。
为简化叙述，本节考虑"有限时域 + 无折扣奖励"问题；该方法也可推广到"平均奖励"和"折扣无限时域"问题。把 (4.11) 推广到连续状态空间时，将对状态的求和换为对 \(z\) 的积分、\(T(s' \mid s, a)\) 由概率质量换为概率密度
由 \(T\) 与 \(R\) 的假设可将上式改写为
可归纳证明 \(U_n(s)\) 总能写成 \(s^\top V_n s + q_n\) 的形式（其中 \(V_n\) 是矩阵、\(q_n\) 是标量），其含义是"价值函数对状态 \(s\) 是二次的"——这一性质是本节整套推导的关键起点。把上式改写为
化简得
上式中的积分可计算为
其中 \(\text{Tr}\) 是矩阵的迹（即主对角线元素之和）。该式的两项分别来自 Gaussian 噪声的二阶矩贡献（与 \(\Sigma\) 有关的部分）与确定性的状态转移部分。代入上式得
对上式最后一项关于 \(a\) 求最大值，可对 \(a\) 求导、令导数为 0、解出
\(2 a^\top R_a + 2 (T_s s + T_a a)^\top V_{n-1} T_a = 0. \tag{4.23}\)
化简得
\(a = -(T_a^\top V_{n-1} T_a + R_a)^{-1} T_a^\top V_{n-1} T_s s. \tag{4.24}\)
把 (4.24) 代回 (4.22) 化简，可得 \(U_n(s) = s^\top V_n s + q_n\)，其中
\(q_n = q_{n-1} + \text{Tr}(\Sigma V_{n-1}). \tag{4.26}\)
为求任意 \(n\) 步下的 \(V_n\) 与 \(q_n\)，可取初值 \(V_0 = 0\)、\(q_0 = 0\)，按上述迭代式递推——这给出了一种对"任意 \(n\) 步 linear-quadratic 决策问题"求精确解的通用方法。一旦知道 \(V_{n-1}\) 与 \(q_{n-1}\)，就可以抽出最优的 \(n\) 步策略
\(\pi_n(s) = -(T_a^\top V_{n-1} T_a + R_a)^{-1} T_a^\top V_{n-1} T_s s. \tag{4.27}\)
一个值得注意的观察是 \(\pi_n(s)\) 不依赖于噪声的协方差 \(\Sigma\)，但最优代价（最优值 \(q_n\)）依赖于噪声。这一性质揭示了 linear-quadratic 框架中"控制律"与"代价"两个角色的清晰分离：控制律只关心"在没有噪声的世界里应当往哪儿走"；代价则关心"在有噪声的现实世界中平均要付出多少"。"动力学无噪声、线性系统、二次代价"的问题在控制论中称为 linear quadratic regulator（LQR），已有大量研究——本节的内容可视为 LQR 向"含噪声"情形的自然延伸。
4.5 Approximate Dynamic Programming
近似 dynamic programming（approximate dynamic programming）研究的是"在大规模或连续空间中求近似最优策略"的问题。它是一个活跃的研究领域，与强化学习（reinforcement learning）共享诸多思想。强化学习关注的是"在模型未知的情况下尽快累计尽可能多的奖励"；其中很多算法（在下一章中讨论）可以直接用于近似 dynamic programming。本节聚焦于若干"在模型已知前提下高效求价值函数与策略"的局部与全局近似策略。
4.5.1 Local Approximation
Local approximation 建立在如下假设之上：相邻状态具有相近的价值。若已知有限个状态 \(s_{1:n}\) 的价值，则任意状态的价值可以用下式近似
其中 \(\beta_{1:n}\) 是权重函数且满足 \(\sum_{i=1}^n \beta_i(s) = 1\)；\(\lambda_i\) 是状态 \(s_i\) 的价值。一般地，\(\beta_i(s)\) 应赋予与 \(s\) "更近"（按某种距离度量）的状态以更大的权重——权重函数常称为核（kernel）。这一表示形式把"在所有 \(n\) 个状态上都精确"放宽为"用 \(n\) 个参数 \(\lambda_{1:n}\) 加上 \(n\) 个权重函数 \(\beta_{1:n}\) 加权求和"——只要 \(\beta\) 的设计能反映"局部性"，就可以用远少于全状态空间规模的信息获得合理的近似。
Algorithm 4.4 给出用迭代方式更新 \(\lambda\) 来近似最优价值函数的方法——对每个采样点 \(s_i\) 计算局部 Bellman 更新 \(u_i = \max_a [R(s_i, a) + \gamma \sum_{s'} T(s' \mid s_i, a) \lambda^\top \beta(s')]\)，再令 \(\lambda \leftarrow u\)；循环至收敛。一旦获得了近似的价值函数，可按下式抽出近似最优策略
一种最简单的 local approximation 称为"最近邻（nearest neighbor）"——把全部权重赋给最近的离散状态，得到一个分段常数的价值函数。更平滑的近似可用 \(k\)-最近邻实现：对 \(s\) 的 \(k\) 个最近邻，每个赋以 \(1/k\) 的权重。这两种"硬划分 + 等权"的方法虽然简单，但价值函数在邻域边界处不光滑，对依赖平滑性的策略影响较大。
若定义一个"邻域函数 \(N(s)\)"返回来自 \(s_{1:n}\) 的一组状态，则可使用线性插值。设状态空间是一维、\(N(s) = \{s_1, s_2\}\)，则插值后的价值为
其中 \(\beta_1(s) = 1 - (s-s_1)/(s_2-s_1)\)、\(\beta_2(s) = 1 - (s_2-s)/(s_2-s_1)\)。该式可推广到 \(d\) 维状态空间：在二维中常称 bilinear interpolation，在任意维中常称 multilinear interpolation。若状态空间已被多维网格离散化、且网格的顶点对应于离散状态，则可把 \(N(s)\) 定义为"包含 \(s\) 的矩形单元的顶点集合"——在 \(d\) 维中最多有 \(2^d\) 个邻居。
图 4.9 给出二维状态空间网格离散化的一个具体例子：要求图中黑色圆圈所示状态 \(s\) 的插值价值，使用 \(N(s) = \{s_{12}, s_{13}, s_{17}, s_{18}\}\)（白圈）作为邻居；各邻居的值与权重在图 4.9 中已经标出（\(\lambda_{12} = 3.9\)、\(\beta_{12}(s) = 0.64\)；\(\lambda_{13} = 0.5\)、\(\beta_{13}(s) = 0.16\)；\(\lambda_{17} = 1.8\)、\(\beta_{17}(s) = 0.16\)；\(\lambda_{18} = 2.2\)、\(\beta_{18}(s) = 0.04\)）。把这些数值代入 (4.28) 得
当问题的维数较高时，对包含 \(s\) 的矩形单元的 \(2^d\) 个顶点做插值的代价可能过高。一种替代方案是 simplex-based interpolation：把矩形单元拆成 \(d!\) 个多维三角形（称为 simplex）；不再对矩形单元插值，而是对"至多 \(d+1\) 个顶点构成的 simplex"插值——这样插值的代价随状态空间维数线性增长而不是指数增长。但矩形插值在相同网格分辨率下可以给出更高质量的估计，从而可能得到更优的策略。图 4.10 给出二维矩形插值与 simplex 插值的对比示例——可以看到 simplex 插值在数据点间的过渡并不连续，而矩形插值则能更好地保留"邻居之间平滑过渡"的性质。
4.5.2 Global Approximation
Global approximation 用一组固定参数 \(\lambda_{1:m}\) 来近似整个状态空间 \(\mathcal{S}\) 上的价值函数。最常用的 global approximation 方法之一基于 linear regression。定义一组基函数（basis functions）\(\beta_{1:m}\)，其中 \(\beta_i : \mathcal{S} \to \mathbb{R}\)；这些基函数有时也被称为特征（features）。价值函数 \(U(s)\) 的近似是参数与基函数输出的线性组合
该近似的形式与 (4.28) 相同，但解释截然不同：参数 \(\lambda_{1:m}\) 不再对应于"各离散状态上的价值"——它们只是"使近似误差最小化"的实数权重；基函数 \(\beta_{1:m}\) 也未必与距离度量有关，且不必满足求和为 1 的约束。这一去耦使得"参数个数"可以远小于"采样状态数"，从而用 \(m\) 个参数对 \(n\) 个采样点（\(m \ll n\)）做有原则的拟合。
Algorithm 4.5 把 linear regression 嵌入价值迭代——它与 Algorithm 4.4 几乎相同，唯一区别在第 6 行：local approximation 中直接令 \(\lambda \leftarrow u\)（每个采样点对应一个参数），这里则调用 \(\lambda_{1:m} \leftarrow \text{Regress}(\beta, s_{1:n}, u_{1:n})\)。\(\text{Regress}\) 函数求出"使基函数 \(\beta\) 在点 \(s_{1:n}\) 处对目标值 \(u_{1:n}\) 的近似最优"的 \(\lambda\)——它本质上是把"在 \(n\) 个点上的 \(n\) 维目标向量 \(u\)"压缩为"由 \(m\) 个基函数张成的 \(m\) 维子空间内的最佳近似"。一种常见的回归目标是最小化"和方差（sum-squared error）"
Linear least-squares regression 可通过简单的矩阵运算求出让和方差最小的 \(\lambda\)——具体地，对设计矩阵 \(\Phi\)（第 \(i\) 行为 \(\beta(s_i)^\top\)）有 \(\lambda = (\Phi^\top \Phi)^{-1} \Phi^\top u\)。此外还有大量已被充分研究的回归方法，包括线性与非线性方法，例如 ridge regression、kernel ridge regression、Gaussian process regression、神经网络等——它们都共享"用一组基函数表达价值函数"这一基本结构，但在拟合目标与参数化方式上有所不同。
图 4.11 给出 linear interpolation 与 linear regression 在使用不同基函数下的对比。为简单起见，假设状态空间是一维、状态 \(s_{1:10}\) 等间距分布；由 dynamic programming 算出的目标值 \(u_{1:10}\) 在图中以圆点绘制。图 4.11a 展示 linear interpolation——它产生的近似价值函数在状态 \(s_{1:10}\) 处精确匹配 \(u_{1:10}\)，但需要 10 个参数（即每个采样点对应一个 \(\lambda\)），等价于"用阶梯函数穿过所有已知点"。
图 4.11b 给出"以 \(\beta_1(s) = 1\)、\(\beta_2(s) = s\) 为基函数"做 linear least-squares regression 的结果：\(\lambda_1 = 4.53\)、\(\lambda_2 = 0.07\)，即 \(U(s) \approx 4.53 + 0.07s\)。尽管该 \(\lambda\) 在这两个基函数意义下最小化和方差，但近似价值函数（一条直线）并不特别准确——它在 \(s\) 较大时严重低估、在 \(s\) 中等时高估。
图 4.11c 增加了 \(\beta_3(s) = s^2\) 这一基函数：近似价值函数变成状态空间上的二次函数；新加入的基函数使 \(\lambda_1\)、\(\lambda_2\) 的取值也发生变化（\(\lambda_1 = 0.87\)、\(\lambda_2 = 1.90\)、\(\lambda_3 = -0.17\)）；二次价值函数在状态 \(s_{1:n}\) 处的和方差远小于线性情形。
图 4.11d 进一步增加 \(\beta_4(s) = s^3\) 这一三次基函数（\(\lambda_1 = 3.57\)、\(\lambda_2 = -0.50\)、\(\lambda_3 = 0.35\)、\(\lambda_4 = -0.03\)），近似得到进一步改善。本例中的基函数都是多项式，但同样可以加入其他基函数，例如 \(\sin(s)\) 与 \(e^s\)。增加基函数一般能提高对已知状态目标值的拟合能力，但基函数过多会导致对其他状态的近似变差——这是经典的"偏差—方差权衡（bias-variance trade-off）"。已经存在"在回归中选择合适基函数"的原则性方法，例如交叉验证、信息准则、正则化。
4.6 Online Methods
本章前述方法都是先离线（offline）计算整个状态空间上的策略，再在环境中执行。尽管 factored representation 与价值函数近似有助于把 dynamic programming 推广到更高维的状态空间，但在全状态空间上计算并存储一个策略仍然可能不可行。本节讨论若干"把计算限制在从当前状态可达的状态上"的在线（online）方法。由于可达状态空间往往比全状态空间小若干个数量级，online 方法可以显著降低选择最优（或近似最优）动作所需的存储与计算量。
4.6.1 Forward Search
Forward search（Algorithm 4.6）是一种简单的 online 动作选择方法：从某个初始状态 \(s_0\) 出发，向前看一段 horizon（深度）\(d\)。函数 \(\text{SelectAction}(s, d)\) 返回最优动作 \(a^*\) 与其价值 \(v^*\)。伪代码用 \(A(s)\) 表示"在状态 \(s\) 处可用的动作集合"，它可以是完整动作空间 \(\mathcal{A}\) 的子集；\(S(s, a)\) 表示"在 \(s\) 处执行 \(a\) 后可能到达的下一状态集合"，它可以是完整状态空间 \(\mathcal{S}\) 的子集。
Algorithm 4.6 遍历所有"动作—下一状态"对，递归调用自身至所需深度。调用树深度为 \(d\)，最坏情况下的分支因子是 \(|\mathcal{S}| \times |\mathcal{A}|\)，采用深度优先。计算复杂度为 \(O((|\mathcal{S}| \times |\mathcal{A}|)^d)\)。
4.6.2 Branch and Bound Search
Branch and bound search（Algorithm 4.7）是对 forward search 的扩展——它利用价值函数的上下界来剪掉搜索树的一部分。该算法假定已有先验知识，可以方便地算出价值函数 \(U(s)\) 的下界与状态—动作价值函数 \(U(s, a)\) 的上界。其伪代码与 Algorithm 4.6 几乎相同，只是利用下界（第 3 行）以及剪枝检查（第 6 行）。调用 \(\text{SelectAction}(s, d)\) 返回应执行的动作和价值函数的下界。
第 5 行遍历动作的顺序很关键：为了能剪枝，动作必须按"上界降序"排列——即若 \(a_i\) 在 \(a_j\) 之前被评估，则 \(U(s, a_i) \ge U(s, a_j)\)。上下界越紧，能剪掉的搜索空间就越大、计算时间就越少。但最坏情况下的计算复杂度与 forward search 相同。
4.6.3 Sparse Sampling
采样方法可以避免 forward search 与 branch and bound search 最坏情况下的指数复杂度。尽管这些方法不能保证产生最优动作，但可以证明它们在大多数情况下产生近似最优动作，并且实践中往往效果很好。最简单的方法之一称为 sparse sampling（Algorithm 4.8）。
Sparse sampling 用一个生成模型 \(G\) 产生下一状态 \(s'\) 与奖励 \(r\) 的样本。使用生成模型的好处是：对于复杂的多维分布，"写一段从该分布中采样的代码"通常比"显式地把概率表出来"更简单。算法第 8 行执行 \((s', r) \sim G(s, a)\)；所有关于状态转移与奖励的信息都由 \(G\) 表示，状态转移概率 \(T(s' \mid s, a)\) 与期望奖励函数 \(R(s, a)\) 并不被直接使用。
Sparse sampling 与 forward search 的区别在于：它对每个动作采样 \(n\) 个下一状态，而不是遍历 \(S(s, a)\) 中的所有状态。每次采样得到 \(r + \gamma v'\) 的一个样本——其中 \(r\) 来自生成模型、\(v'\) 来自对 \(\text{SelectAction}(s', d-1)\) 的递归调用。所有 \(r + \gamma v'\) 的样本被平均以估计 \(Q(s, a)\)。运行时间复杂度 \(O((n \times |\mathcal{A}|)^d)\) 在 horizon 上仍是指数的，但不再依赖于状态空间的大小。
4.6.4 Monte Carlo Tree Search
近年来最成功的基于采样的 online 方法之一是 Monte Carlo tree search。Algorithm 4.9 是其 Upper Confidence Bound for Trees（UCT）实现。与 sparse sampling 不同，Monte Carlo tree search 的复杂度不再随 horizon 指数增长——这是因为它在每一步只深入到"已有信息支持其有价值"的分支，而不是均匀地探索整棵搜索树；与 sparse sampling 相同的是，它也使用生成模型。
该算法从当前状态出发运行大量模拟，同时更新对状态—动作价值函数 \(Q(s, a)\) 的估计。每次模拟包含三个阶段：
- 搜索（Search）。若模拟中的当前状态在集合 \(T\) 中（\(T\) 初始为空），则进入搜索阶段；否则进入扩展阶段。在搜索阶段中，算法对在搜索中访问与尝试过的状态与动作更新 \(Q(s, a)\)；同时记录从该状态出发采取某动作的次数 \(N(s, a)\)。在搜索阶段中，执行使下式最大的动作
其中 \(N(s) = \sum_a N(s, a)\)、\(c\) 是控制探索量的参数（探索将在下一章详细讨论）。第二项是探索奖励（exploration bonus），鼓励选择尝试次数较少的动作；当 \(N(s, a) = 0\) 时该奖励为无穷大，从而保证"任何从 \(s\) 出发尚未尝试过的动作在第一次都被选到"。
-
扩展（Expansion）。一旦到达不在 \(T\) 中的状态，遍历该状态上可用的所有动作并用 \(N_0(s, a)\) 与 \(Q_0(s, a)\) 初始化 \(N(s, a)\) 与 \(Q(s, a)\)。\(N_0\)、\(Q_0\) 可以基于对该问题的先验专家知识；若无先验知识则可都初始化为 0。然后把当前状态加入 \(T\)。这一阶段是 MCTS 与 sparse sampling 的关键区别——它把"在哪些状态上需要被精确评估"这一信息从"先验"推迟到"运行时根据访问频率决定"。
-
Rollout。扩展阶段结束后，按某个 rollout（或默认）策略 \(\pi_0\) 选择动作直到达到所需深度（Algorithm 4.10）。通常 rollout 策略是随机的，即从 \(\pi_0(s)\) 中采样 \(a \sim \pi_0(s)\)。Rollout 策略不必接近最优，但它是专家把搜索"偏向"到有潜力区域的一种方式——例如围棋的 MCTS 系统中常用"基于局部形状的快速启发式"作为 rollout 策略。Rollout 阶段返回期望值，并被用于更新搜索阶段的 \(Q(s, a)\)。
模拟运行到满足某个停止条件为止——通常就是一个固定的迭代次数。然后执行使 \(Q(s, a)\) 最大的动作。该动作执行完之后，可以重新运行 Monte Carlo tree search 来选择下一个动作。通常会把前一次计算出的 \(N(s, a)\) 与 \(Q(s, a)\) 保留下来——这相当于把"上一次搜索中学到的统计信息"作为"这一次搜索的先验"传给后续运行，从而在多次决策之间累积知识。
4.7 Direct Policy Search
前几节给出的方法都涉及"计算或近似价值函数"。另一种思路是直接搜索策略空间。尽管状态空间可能是高维的，使价值函数的近似变得困难；可能的策略空间却可能相对低维，更便于直接搜索。
4.7.1 Objective Function
设策略由参数 \(\lambda\) 参数化；策略在状态 \(s\) 下选择动作 \(a\) 的概率记为 \(\pi_\lambda(a \mid s)\)。给定初始状态 \(s\)，可估计执行 \(\pi_\lambda\) 的期望效用为
其中 \(u_i\) 是对策略 \(\pi_\lambda\) 第 \(i\) 次 rollout 到某一深度的结果。
直接策略搜索的目标是找到使下式最大化的参数 \(\lambda\)
其中 \(b(s)\) 是初始状态的分布。可以用 Monte Carlo simulation + 生成模型 \(G\) 按 Algorithm 4.11 把 \(V(\lambda)\) 估计到某一深度 \(d\)。\(V(\lambda)\)（由 Algorithm 4.11 估计得到）是一个随机函数——对同一输入 \(\lambda\)，它可能给出不同的输出。随着样本数 \(n\) 增大，\(V(\lambda)\) 的方差会下降。存在多种在策略参数空间中搜索使 \(V(\lambda)\) 最大化的方法，本节将讨论其中几种。
4.7.2 Local Search Methods
一种常见的随机优化方法是 local search，也称为 hill climbing 或 gradient ascent。Local search 从搜索空间中的单点出发，依次在邻域点之间移动直到收敛。该方法基于如下假设：随机函数在搜索空间某一点处的值指示了该点离全局最优的距离。因此 local search 一般选择值最大的邻域点。
一些 local search 技术直接估计 \(\nabla_\lambda V\)（给定策略的梯度），然后沿最速上升方向前进一步。对某些策略表示，梯度可以解析推导。其他的 local search 技术在当前搜索点的有限邻域内做评估，然后移动到值最大的邻域。Local search 容易陷入 \(V(\lambda)\) 的局部最优或平台。可使用 simulated annealing 或 2.4.2 节末尾建议的其他方法来帮助找到全局最优。
4.7.3 Cross Entropy Methods
还有一类策略搜索方法维护"在策略上的一个分布"并按"表现好的策略"更新该分布。更新该分布的一种方法是 cross entropy method。Cross entropy 是信息论中的概念，度量两个分布之间的差异。对两个离散分布 \(p\) 与 \(q\)，cross entropy 定义为
对连续分布，把求和换为积分。在直接策略搜索中，我们感兴趣的是"在 \(\lambda\) 上的分布"，这些分布由参数 \(\theta\) 参数化（\(\theta\) 可以是多维的）。
Cross entropy method 接受"一个初始的 \(\theta\)"与"两个决定样本数的参数 \(n\)、\(m\)"作为输入。过程由两个阶段组成，反复执行直到收敛或满足其他停止条件——
- 采样（Sample）。从 \(P(\lambda \mid \theta)\) 中抽取 \(n\) 个样本，并用 Algorithm 4.11 评估其表现。把样本按表现从高到低排序，使 \(i < j\) 蕴含 \(V(\lambda_i) \ge V(\lambda_j)\)。
- 更新（Update）。用表现最好的 \(m\) 个样本（常称为 elite samples）按"cross entropy minimization"更新 \(\theta\)，具体来说就是
新的 \(\theta\) 恰好对应于"基于这 \(m\) 个表现最好的样本"的最大似然估计。更详细的解释可参考本章末尾的 Further Reading。
完整过程见 Algorithm 4.12。初始分布参数 \(\theta\)、样本数 \(n\)、elite 样本数 \(m\) 都是该过程的输入参数。为防止搜索过度集中在局部极大值，初始的 \(\theta\) 应给出"在 \(\lambda\) 上的一个弥散分布"。\(n\) 与 \(m\) 的选择取决于具体问题。
为具体说明 cross entropy method，假设策略空间是一维，\(V(\lambda)\) 如图 4.12 所示；并假设参数 \(\theta = (\mu, \sigma)\)、\(P(\lambda \mid \theta) = \mathcal{N}(\lambda \mid \mu, \sigma^2)\)。初始时取 \(\theta = (0, 10)\)。为避免图像过于拥挤，只使用 \(n = 20\) 个样本与 \(m = 5\) 个 elite 样本；在实际中（尤其在高维问题中）通常多一两个数量级的样本。
图 4.12a 展示 \(\lambda\) 上的初始分布。从中抽取 20 个样本；5 个 elite 样本用圆圈表示，其余 15 个样本用叉号表示。这 5 个 elite 样本被用来更新 \(\theta\)；因为我们用的是 Gaussian 分布，更新只需把均值设为 elite 样本的均值、标准差设为 elite 样本的标准差。更新后的分布见图 4.12b。重复该过程：在第三次迭代（图 4.12c）时，分布已经移向"搜索空间中更有潜力的区域"；到第四次迭代（图 4.12d）时，已经找到全局最优。
4.7.4 Evolutionary Methods
进化搜索方法（evolutionary search methods）的灵感来自生物进化。一种常见方法是使用 genetic algorithm——从"由（通常为二进制的）字符串表示的策略"的一个随机初始种群出发，按适应度对字符串进行遗传交叉（crossover）与变异（mutation），得到新一代。过程持续进行直至得到满意的解。
相关的方法还有 genetic programming——进化由树结构表示的策略。树由从预定义的终结符集合与非终结符集合中选出的符号组成，比固定长度的位串能给出更灵活的策略表示。Crossover 通过交换子树实现，mutation 通过随机修改子树实现。
Genetic algorithm 与 genetic programming 可以与其他方法（包括 local search）结合使用。例如，可以先用 genetic algorithm 进化出一个满意的策略，再用 local search 进一步改善它。这种方法称为 genetic local search 或 memetic algorithms。
4.8 Summary
- Markov decision process 用状态转移与奖励函数表示序贯决策问题。
- 最优策略可用 dynamic programming 类算法求出。
- 连续问题中，"线性高斯动力学 + 二次代价"的问题可以解析求解。
- Structured dynamic programming 可以高效求解 factored Markov decision process。
- 大规模或连续状态空间的问题可以用函数近似方法近似求解。
- 不必离线求解全状态空间上的最优策略；online 方法从当前状态出发搜索最优动作。
- 在一些问题上，直接用随机优化方法在策略空间上搜索会更简单。
4.9 Further Reading
序贯决策问题的开创性工作始于 1949 年 Richard Bellman 的研究 [1]。自那时起，Markov decision process 已成为该类问题的标准建模框架，并已有多本相关专著 [2]–[5]。4.2.5 节的 grid world 实例取自 Poole 与 Mackworth 合著的《Artificial Intelligence: Foundations of Computational Agents》[6]；该书的配套网站包含 grid world 实例的开源软件演示。
Boutilier、Dearden 与 Goldszmidt 提出了基于 decision tree 的 factored MDP 上的 structured value iteration 与 structured policy iteration 算法 [7]。正如 4.3.2 节提到的，使用 decision diagram 通常比 tree 更高效 [7]–[9]。Guestrin 等人探索了 factored MDP 上的近似线性规划方法 [10]。
"线性系统 + 二次代价"的最优控制在控制论社区已被充分研究，并已有多本专著 [11]–[13]。4.4 节给出的 linear-quadratic-Gaussian（LQG）控制问题是"系统状态被完美观测"这一特例；第 6 章将给出"状态信息不完美"的更传统 LQG 版本。
Approximate dynamic programming 领域的综述见 Powell 的《Approximate Dynamic Programming: Solving the Curses of Dimensionality》[14]。Busoniu 等人合著的《Reinforcement Learning and Dynamic Programming Using Function Approximators》概述了近似方法，并提供了"模型已知与未知"两种情况下的源代码 [15]。"模型未知"问题的求解称为强化学习，将在下一章讨论。强化学习常用于"模型已知但过于复杂或高维、不便用精确 dynamic programming"的问题。
如 4.6 节所述，online 方法适用于"状态空间维数很高、且有足够计算资源在执行期间做规划"的场景。Land 与 Doig 最早为离散规划问题提出 branch and bound 方法 [16]；该方法已应用于广泛的优化问题。Sparse sampling 由 Kearns、Mansour 与 Ng 提出 [17]。其他可用于 online 的方法还包括 real-time dynamic programming [18] 与 LAO* [19]。
Kocsis 与 Szepesvári 最早在 Algorithm 4.9 中通过引入探索奖励（exploration bonus）提出 Monte Carlo tree search 的思想 [20]。自该论文发表以来，加之在围棋上的成功应用，已有大量工作聚焦于 Monte Carlo tree search 方法 [21]。本章所给算法的一个重要扩展是 progressive widening——在搜索的每一步逐步拓宽"被考虑的动作与状态" [22]。Progressive widening 允许算法更好地处理大规模或连续的状态/动作空间。
已有多种方法被提出用于在策略空间上直接搜索。Williams [23]、Baxter 与 Bartlett [24] 等人的工作是基于梯度方法的 local search 算法的代表。Cross entropy method [25]、[26] 已被应用于多种 MDP 策略搜索 [27]–[29]。任何一种随机优化技术都可以用于策略搜索。4.7.4 节讨论的进化方法可追溯到 1950 年代 [30]。Genetic algorithm 的普及主要源于 Holland 的工作 [31]，更近期的理论工作可见 Schmitt [32]、[33]。Genetic programming 由 Koza 引入 [34]。
本章个人批注
作为全书理论篇的第四章，本章的职能是把第 3 章的"单步决策"推广为"在时间上依次做出多个决策"的序贯决策框架。如果说第 3 章是"在概率 + 效用之上做静态最优决策"，本章则引入了"时间维度"——状态随动作在时间上演化、奖励在多个时间步上加性累计，由此引出"在时间维度上递归地优化"的 dynamic programming 思想。这一"从静态到动态"的递进与第 2 章末"从单变量到多变量"的递进、第 3 章"从单智能体到多智能体"的递进一道构成全书理论篇的递进骨架。
本章的形式化路径是高度算法化的：从 Markov decision process 的形式化定义（4.1.1 节）出发，先讨论"加性效用 / 折扣效用 / 平均效用"三种效用聚合范式（4.1.2 节），再依次给出策略评估（4.2.2 节）、策略迭代（4.2.3 节）、价值迭代（4.2.4 节）三大基本 dynamic programming 算法，最后给出连续状态—动作空间下的精确求解（4.4 节，linear-quadratic 情形）、近似 dynamic programming（4.5 节，含局部插值、全局基函数回归两类）、online 方法（4.6 节，从前向搜索到 Monte Carlo tree search）与直接策略搜索（4.7 节，涵盖 local search、cross entropy、进化方法）。这一"从精确解到近似解、从离线解到在线解、从价值函数到策略参数"的递进是本章的主线，也是第 5、6 章将要扩展的母版。
4.2 节关于策略迭代、价值迭代的对比让我印象很深。两种算法各有其应用场景——策略迭代在状态数较少时通常收敛更快（每一步都做精确策略评估，再用 Bellman 最优性做一步提升），但每一步的策略评估代价较高；价值迭代的每一步代价较低，但需要更多轮迭代才能收敛。4.2.4 节末尾关于 Bellman 残差 \(\varepsilon\) 与策略损失 \(2\varepsilon\gamma/(1-\gamma)\) 之间的关系是非常实用的工程性质——它告诉我们在做"用近似价值函数抽策略"时需要把价值估计精确到什么程度。4.2.5 节的 grid world 实例则通过具体的数值展示"折扣因子如何影响价值扩散"——\(\gamma = 0.9\) 时左下角的格子也具有正价值，\(\gamma = 0.5\) 时价值只扩散到吸收状态附近一步的距离。这一现象在工程上有直接对应：在做"长期规划"时如果折扣较陡，"远期奖励"实际上不会真正影响当前决策。
4.2.7 节关于 closed-loop vs. open-loop planning 的对比则让我想到一个工程上的根本问题——状态空间的可处理规模。作者用 9 状态的小例子说明"在有不确定性的序贯问题中闭环规划可以严格优于开环规划"；但他也指出"在一些领域中状态空间规模使闭环规划不可行"——这一"理论最优 vs. 工程可行"的张力贯穿本章后半部分。4.3 节（factored MDP + 决策树/图）、4.4 节（linear-quadratic 解析解）、4.5 节（函数近似）、4.6 节（online 搜索）、4.7 节（直接策略搜索）这五个变体都是对"大规模问题不可处理"这一根本困难的回应：第 1 类与第 2 类用"结构"压缩状态/动作空间，第 3 类用"近似"取代精确求解，第 4 类用"在线"取代"离线全状态求解"，第 5 类则完全绕开价值函数、直接在策略空间上做参数搜索。这种"五种工具对应同一个困难"的结构是我在精读本章时最大的收获。
4.6.4 节关于 Monte Carlo tree search 的描述则是我个人最感兴趣的部分。作者用 Algorithm 4.9 + 4.10 把"搜索 / 扩展 / Rollout"三阶段完整写出来，并显式给出 UCB 探索奖励 \(Q(s,a) + c\sqrt{\log N(s) / N(s,a)}\) 的形式。这一算法在第 9 章（语音应用）与第 10 章（航空器碰撞告警）等应用篇章节中都会被反复使用。Algorithm 4.9 中"在内存中维护 \(N(s,a)\) 与 \(Q(s,a)\)、在动作执行后继续 carry over 这些值"的设计也极具工程价值——它把"在线搜索"和"在线学习"在数据层面打通，使 MCTS 可以在长时间尺度上累积经验。
4.7.3 节关于 cross entropy method 的具体例子（图 4.12 中 4 轮迭代找到全局最优）则让我意识到"基于分布的搜索"相对于"基于点的搜索"（如 local search）的根本优势——前者天然具有跳出局部最优的能力（因为分布的方差允许采样到远离当前均值的点），而后者则需要专门的扰动机制（如 simulated annealing）来跳出局部最优。这一观察在我处理"带噪声评估"或"高维策略空间"问题时具有直接意义。4.7.4 节关于 evolutionary methods 的讨论则把这一思想推到极致——genetic algorithm 用"种群的适应度—交叉—变异"模拟生物进化，genetic programming 进一步把策略表示推广到树结构。这两个工具在我的工程实践中偶尔用得到，但远不如 4.5 节与 4.6 节的方法常用。
整体而言，本章是一份"序贯决策问题的算法地图"——它把策略评估、策略迭代、价值迭代、异步价值迭代、closed-loop vs. open-loop planning、factored MDP、linear-quadratic 解析解、函数近似、online 搜索、直接策略搜索十个主题压缩在约 30 页内，每一节都给出该主题的最小可用版本并指明 Further Reading。本章的风格与第 3 章高度一致：以"形式化定义 + 关键算法 + 工程实例"作为每一节的统一结构。第 5 章将放宽"模型已知"假设，引入 model uncertainty；第 6 章将放宽"环境完全可观察"假设，引入状态不确定性。
与上下章的衔接（一段话）
本章是全书 12 章中的第 4 章，也是理论篇的第四章——紧接在第 3 章"决策问题"之后，把第 3 章的"单步决策"推广为"在时间上依次做出多个决策"的序贯决策框架。从位置上看：第 1 章给出了"为什么要做不确定性下的决策"以及"五种设计方法"；第 2 章把"概率视角"这一支展开为信念度公理化、贝叶斯网络、推理与学习；第 3 章在第 2 章的概率模型之上加入"效用（utility）"与"决策节点"，把贝叶斯网络推广为决策网络，处理的是"单步决策"问题；本章则在第 3 章的基础上加入"时间维度"——状态随动作在时间上演化、奖励在多个时间步上加性累计，把静态的决策网络推广为动态决策网络（即 Markov decision process），并系统讨论四族求解算法（policy evaluation、policy iteration、value iteration、asynchronous value iteration）以及处理大规模问题与连续问题的若干变体。第 5 章 Model Uncertainty 会放宽"模型已知"这一假设，讨论"模型未知时如何通过经验学习"；第 6 章 State Uncertainty 会放宽"环境完全可观察"这一假设，讨论"状态只能被部分观察时如何决策"（这正是 partially observable MDP 的范畴）；第 7 章 Cooperative Decision Making 则把"多智能体"这一维度从本章的"单智能体序贯"推广为多智能体序贯。从作者的整体布局看，本章在理论篇中的位置是"先把单智能体序贯决策的算法骨架搭好，再让后续章节用这些积木搭出更大的结构"——尤其是 4.2 节的 value iteration 与 4.4 节的 linear-quadratic 解析解将在第 6 章（状态不确定性下的 Kalman 滤波与 LQG）与第 10 章（航空器碰撞告警）中作为核心工具被反复使用。