第 6 章：状态不确定性（State Uncertainty）

章节作者：Mykel J. Kochenderfer 章节定位：理论篇第六章。在第 4 章中讨论的序贯决策问题假设智能体能准确观测到当前状态；本章放宽这一假设——由于传感器限制或噪声，状态可能无法被完全观测。本章讨论带有状态不确定性的序贯决策问题，以及计算最优与近似最优解的方法。本章是全书"状态不确定性"主题的集中展开：6.1 节给出 POMDP 形式化，6.2 节讨论信念更新（discrete / linear-Gaussian / particle），6.3 节给出精确解方法（alpha 向量、条件计划、值迭代），6.4 节讨论离线近似方法（QMDP、FIB、PBVI 等），6.5 节讨论在线方法（前瞻搜索、branch and bound、MCTS）。

6.1 Formulation

带有状态不确定性的序贯决策问题可以建模为部分可观测 Markov 决策过程（POMDP）。POMDP 是第 4 章中 MDP 形式化的扩展：在 POMDP 中，模型除了转移与奖励外，还指定"在当前状态下观察到某一观测"的概率。本节先给出一个示例问题（crying-baby），再给出 POMDP 的形式化定义，最后把它转化为一个等价的"信念状态"上的 MDP。

6.1.1 Example Problem

本章用一个 crying-baby（哭泣婴儿）问题贯穿示例。智能体决定何时喂婴儿，决策依据是婴儿是否在哭——哭是一个"婴儿是否饥饿"的有噪指标：婴儿不饿时有 10% 的概率会哭，饥饿时有 80% 的概率会哭。

动力学如下：若喂婴儿，则下一个时刻婴儿停止饥饿。若婴儿不饿且未喂，则有 10% 的概率在下一个时刻转为饥饿。一旦饥饿，婴儿会持续保持饥饿直到被喂。

喂婴儿的成本为 5，婴儿饥饿的成本为 10（成本可加，因此"在饥饿状态下喂婴儿"的总成本为 15）。目标是在折扣因子 γ=0.9 的无限时域下找到最优策略。图 6.1 给出了 crying-baby 问题的动态决策网络结构。

6.1.2 Partially Observable Markov Decision Processes

POMDP 是"带观测模型"的 MDP。"在状态 s 下观测到 o"的概率记为 O(o | s)。在某些形式化中，观测还可能依赖于动作 a，因此记为 O(o | s, a)。POMDP 在时刻 t 的决策只能基于到当前为止的观测历史 o₁:t。为了避免维护任意长的历史，通常维护"信念状态"（belief state）——状态上的一个分布。信念状态 b 中，处于状态 s 的概率为 b(s)。POMDP 的策略是从信念状态到动作的映射。POMDP 的结构可以用图 6.2 的动态决策网络表示。

6.1.3 Policy Execution

算法 6.1 概述了 POMDP 策略的执行过程：在每个时刻，依据当前信念状态查策略 π 选择动作 a；接收到新观测 o 与奖励 r 后更新信念状态。不同的策略表示方式将在本章中讨论。信念状态的更新将在 6.2 节中详细展开。

6.1.4 Belief-State Markov Decision Processes

POMDP 本质上是一个"以信念状态为状态"的 MDP。信念状态 MDP 的状态空间就是 POMDP 中所有可能信念的集合 B；若有 n 个离散状态，则 B 是 Rⁿ 的一个子集。动作空间与原 POMDP 相同。信念状态 MDP 的状态转移函数 τ(b′ | b, a) = P(b′ | b, a) 由式 (6.1)–(6.5) 给出，链式展开依次利用了"给定 b,a,o 后 b′ 由 UpdateBelief 唯一确定"（用 Kronecker delta 表示）、观测模型 O(o | s′) 与转移模型 T(s′ | s, a)。立即奖励为 R(b, a) = Σₛ R(s, a) b(s)，是原奖励在信念分布上的期望。

信念状态 MDP 的求解很有挑战性，因为状态空间是连续的。可以用 4.5 节给出的近似动态规划方法，但常常可以利用信念状态 MDP 的特殊结构得到更好的算法——本章后续节会讨论这些方法。

6.2 Belief Updating

给定初始信念状态，可基于"上一观测与所执行的动作"用递归 Bayesian 估计更新信念状态。对于离散状态问题与线性-高斯动力学及观测问题，更新可以精确执行；对一般的连续状态空间问题，通常需要依靠近似方法。本节给出信念更新的三种方法：离散状态滤波器、linear-Gaussian 滤波器（即 Kalman 滤波器）、粒子滤波器。

6.2.1 Discrete State Filter

在离散状态空间下，递归 Bayesian 估计的形式很直接。设当前信念状态为 b，执行动作 a 后观测到 o，新的信念状态 b′ 由式 (6.7)–(6.11) 给出：b′(s′) ∝ O(o | s′, a) Σₛ T(s′ | s, a) b(s)。观测空间可以是连续的（式中的 O 此时表示概率密度而非概率质量），不影响计算。

以 crying-baby 问题为例，演示六步可能场景：(1) 初始信念 (0.5, 0.5)；(2) 未喂且哭，更新为 (0.0928, 0.9072)——哭只是饥饿的有噪指示；(3) 喂后停止哭，信念变为 (1, 0)，因为喂会确定性地解除饥饿；(4) 未喂且不哭，信念更新为 (0.9759, 0.0241)——上一步已经确定不饿，且动力学规定不饿的婴儿只有 10% 概率变饿，不哭的观测进一步降低饥饿信念；(5) 仍未喂且未哭，信念 (0.9701, 0.0299)，饥饿信念略升；(6) 未喂且开始哭，信念 (0.4624, 0.5376)——因初始时已较确信不饿，因此与第 2 步相比，对"现在饥饿"的置信度要低得多。

6.2.2 Linear-Gaussian Filter

把 4.4 节的线性-高斯动力学推广到部分可观测情形，可以用 Kalman 滤波器做精确的信念更新。动力学与观测为 T(z | s, a) = N(z | Tₛs + Tₐa, Σₛ)、O(o | s) = N(o | Oₛs, Σₒ)，由矩阵 Tₛ、Tₐ、Σₛ、Oₛ、Σₒ 指定。假设初始信念为高斯 b(s) = N(s | μ_b, Σ_b)，则在相同的线性-高斯假设下信念按式 (6.15)–(6.17) 更新：K = Σₚ Oₛᵀ (Oₛ Σₚ Oₛᵀ + Σₒ)⁻¹，μ_b ← μ_p + K(o − Oₛ μ_p)，Σ_b ← (I − K Oₛ) Σ_p，其中 μ_p = Tₛ μ_b + Tₐ a、Σ_p = Tₛ Σ_b Tₛᵀ + Σₛ 是观测前的预测均值与协方差。矩阵 K 称为 Kalman 增益。Kalman 滤波器常被应用于"实际动力学并不严格线性-高斯"的系统，6.7 节讨论为处理非线性动力学而提出的各种变体。

6.2.3 Particle Filter

当状态空间很大或连续、且动力学无法用线性-高斯模型良好近似时，可用基于采样的方法做信念更新。信念用一组粒子表示——粒子就是状态空间中的样本。基于观测调整粒子的算法称为粒子滤波器；粒子滤波器有多种变体（包括为粒子赋权的版本）。

信念 b 就是状态空间的一组样本。更新 b 需要一个生成模型 G：可以从中抽取 (s′, o′) ∼ G(s, a)，即给定当前状态 s 与动作 a，返回下一状态 s′ 与观测 o′。生成模型可以以黑箱模拟器实现，无需显式给出转移或观测概率。

算法 6.2 给出"带拒绝的粒子滤波器"：为生成 |b| 个新粒子，对每个粒子先在 b 中随机抽一个样本 s，然后从 G(s, a) 抽样 (s′, o′)，直到 o′ 与实际观测 o 匹配，把 s′ 加入新信念 b′。其问题在于：当观测空间很大或连续时，需要大量从生成模型中抽样才能得到与 o 匹配的 o′。这与 2.2.5 节讨论"用直接采样在 Bayesian 网络上做推理"时遇到的问题相同——那节的解决方案是不采样观测值，而是用观测的似然为结果赋权。

算法 6.3 给出"无拒绝的粒子滤波器"：生成模型只返回状态、不返回观测，需要显式的观测模型 O(o | s, a)（对离散/连续观测空间分别为概率质量/密度）。算法分两阶段：第一阶段对 b 中随机选出的每个样本用生成模型前向传播得到新样本 s′ᵢ，计算权重 wᵢ = O(o | s′ᵢ, a)，其中 o 是实际观测、a 是所执行的动作；第二阶段按与权重成正比的概率从新状态样本中有放回地抽 |b| 个样本，构成更新后的信念 b′。这两种粒子滤波器都满足：随着粒子数增加，粒子所表示的分布逼近真实后验。但粒子滤波器在实践中可能失败：由于随机性，可能出现一系列样本都不接近真实状态的情形——这称为"粒子匮乏"（particle deprivation），可通过向粒子引入额外噪声在一定程度上缓解。

6.3 Exact Solution Methods

如前所述，POMDP 的策略是从信念状态到动作的映射。本节解释如何计算与表示最优策略。

6.3.1 Alpha Vectors

先考虑一步时域的离散状态 POMDP 的最优策略计算。对完全可观测情形有 U(s) = max_a R(s, a)，但 POMDP 中状态未知，因此 U(b) = max_a Σₛ b(s) R(s, a)（式 (6.18)）。令 α_a 表示把 R(·, a) 写为向量、b 把信念状态写为向量，则式 (6.18) 可改写为 U*(b) = max_a α_aᵀ b（式 (6.19)）。α_a 称为 alpha 向量：对单步 POMDP，每个动作对应一个 alpha 向量。这些 alpha 向量在信念空间中定义超平面；由式 (6.19) 可见，最优值函数是分段线性、凸的（PWLC）。

图 6.3 给出 crying-baby 问题的 alpha 向量：信念向量记为 (b(不饿), b(饿))，两个 alpha 向量是 α_不喂 = (0, −10) 与 α_喂 = (−5, −15)。从图中可见，对当前任意信念，一步最优策略都是"不喂"——由于问题的动力学，喂婴儿带来的好处至少要到一步以后才能体现。

6.3.2 Conditional Plans

上面"一步最优策略"中的 alpha 向量可以推广到任意时域。多步 POMDP 中，策略可视为一棵树形式的"条件计划"：根节点指定第一步要执行的动作；执行该动作后，依据观测转到对应子节点，子节点再指定下一步动作；如此沿树下行。

图 6.4 给出 crying-baby 问题的三步条件计划示例：根节点指定第一步不喂；第二步按有向边所示，哭了就喂、不哭就不喂；第三步再次按是否哭决定是否喂。

可以递归地计算条件计划 p 在状态 s 下的期望效用 U^p(s) = R(s, a) + Σₛ′ T(s′ | s, a) Σₒ O(o | s′, a) U^p(o)(s′)（式 (6.22)），其中 a 是 p 根节点对应的动作、p(o) 是观测 o 对应的子计划。信念状态下的期望效用为 U^p(b) = Σₛ U^p(s) b(s)（式 (6.23)）。用 alpha 向量 α_p 表示 U^p 的向量化形式，U^p(b) = α_pᵀ b（式 (6.24)）。在所有不超过规划时域的计划上最大化，得 U*(b) = max_p α_pᵀ b（式 (6.25)）。因此有限时域最优值函数是分段线性凸的：只需执行"使 α_pᵀ b 最大"那个计划的根节点动作。

6.3.3 Value Iteration

枚举所有 h 步条件计划以从当前信念最大化式 (6.25) 是不现实的：h 步条件计划的节点数为 (|O|ʰ − 1)/(|O| − 1)，每节点有 |A| 个动作，因此 h 步计划的总数为 |A|(|O|ʰ − 1)/(|O| − 1)。即使对 crying-baby（两个动作、两个观测），6 步条件计划就有 2·63 = 126 个分支——多到无法枚举。

POMDP 值迭代的思路是：先在所有"一步计划"中迭代，挑出"对任何初始信念都不被支配"的留下；用留下的一步计划生成所有"潜在最优的"二步计划；再丢掉在任何信念上都不是最优的计划；重复到所需时域。识别"在某些信念上被其他计划支配"的计划可以用线性规划。

图 6.5 给出 crying-baby 问题在折扣因子 0.9 下两条非支配 alpha 向量：两条 alpha 向量在 P(饿) = 0.28206 处相交；如图所示，仅当 P(饿) > 0.28206 时才喂婴儿。对该问题直接存一个阈值比用 alpha 向量更简单；但对更高维的问题，alpha 向量常常提供更紧凑的策略表示。

丢弃被支配的计划能显著减少寻找最优 alpha 向量集合所需的计算；对许多问题，潜在计划中的大多数都被至少一个其他计划支配。但在最坏情况下，一般有限时域 POMDP 的精确求解是 PSPACE 完全的（PSPACE 包含 NP 完全问题并被怀疑还包含更难的子类）；一般无限时域 POMDP 已被证明是不可计算的。这推动了近似方法的大量研究——本章余下部分将讨论这些方法。

6.4 Offline Methods

离线 POMDP 方法在执行前完成全部或大部分计算。实践中通常只能找到近似最优的解：有些方法用 alpha 向量表示策略，有些用有限状态控制器。

6.4.1 Fully Observable Value Approximation

一个简单近似是 QMDP：基于完全可观测下的状态-动作值函数 Q(s, a)，为每个动作生成一个 alpha 向量。可用值迭代来计算这些 alpha 向量。初始化 α_a⁽⁰⁾(s) = 0，然后按式 (6.26) 迭代：α_a⁽ᵏ⁺¹⁾(s) = R(s, a) + γ Σₛ′ T(s′ | s, a) max_{a′} α_{a′}⁽ᵏ⁾(s′)。每次迭代的复杂度为 O(|A|²|S|²)。k → ∞ 时所得 |A| 个 alpha 向量可用来估计值函数：信念 b 处的值函数为 max_a α_aᵀ b，近似最优动作为 arg max_a α_aᵀ b。

QMDP 假定"下一时刻所有状态不确定性都消失"：可以证明 QMDP 对值函数给出上界，即对所有 b 都有 max_a α_aᵀ b ≥ U*(b)。QMDP 在带"信息收集"动作的问题（如"变道前先看右肩"）上表现不佳，但在许多"动作选择对状态不确定性的减少影响很小"的实际问题中表现非常好。

6.4.2 Fast Informed Bound

和 QMDP 一样，fast informed bound（FIB）也为每个动作计算一个 alpha 向量，但 FIB 在一定程度上考虑了部分可观测性。它不采用式 (6.26) 的迭代，而用式 (6.27)：α_a⁽ᵏ⁺¹⁾(s) = R(s, a) + γ max_{a′} Σₒ Σₛ′ O(o | s′, a) T(s′ | s, a) α_{a′}⁽ᵏ⁾(s′)。每次迭代的复杂度为 O(|A|²|S|²|O|)，仅比 QMDP 多一个 |O| 因子。在所有信念状态上，FIB 给出的最优值函数上界都不高于 QMDP 给出的上界。图 6.6 比较了 QMDP、FIB 与 crying-baby 问题最优策略对应的 alpha 向量。

6.4.3 Point-Based Value Iteration

有一族近似方法在信念空间的有限点上对 alpha 向量做 backup。设信念点的集合 B = {b₁, …, bₙ}，其上对应的 alpha 向量集合 Γ = {α₁, …, αₙ}。给定这 n 个 alpha 向量，对任意新点 b 的值函数可由式 (6.28) 估计：U^Γ(b) = max_{α∈Γ} αᵀ b = max_{α∈Γ} Σₛ α(s) b(s)。

假设这些信念点已经给定（点选择方法在 6.4.5 节讨论）。希望把 Γ 中 alpha 向量初始化为使 U^Γ(b) ≤ U*(b) 对所有 b 成立的下界。一种计算该下界的方式是把所有 n 个 alpha 向量的所有分量初始化为式 (6.29) 给出的值：max_a Σ_{t=0}^∞ γᵗ min_s R(s, a) = (1/(1 − γ)) max_a min_s R(s, a)。从该初值开始做 backup 时，可保证每次迭代时 U(b) 对任意 b 都不下降。

可以按式 (6.30) 在信念 b 上更新值函数：U(b) ← max_a [R(b, a) + γ Σₒ P(o | a, b) U(b′)]，其中 b′ 由 UpdateBelief(b, a, o) 确定，U(b′) 由式 (6.28) 估计，P(o | b, a) = Σₛ Σₛ′ b(s) O(o | s′, a) T(s′ | s, a)（式 (6.31)）。由 Bayes 规则有 b′(s′) = O(o | s′, a) Σₛ T(s′ | s, a) b(s) / P(o | b, a)（式 (6.32)）。联立式 (6.28)、(6.30)、(6.32) 化简得式 (6.33) 的更新：U(b) ← max_a Σₒ max_{α∈Γ} Σₛ Σₛ′ b(s) O(o | s′, a) T(s′ | s, a) α(s′)。除在 b 上更新值外，还可用算法 6.4 计算 b 上的 alpha 向量。点基值迭代近似算法对 n 个信念点上的 alpha 向量做 backup 直至收敛；这 n 个 alpha 向量可在信念空间中任意位置近似值函数。

6.4.4 Randomized Point-Based Value Iteration

6.4.3 节的点基值迭代对信念空间中所选每个点都关联一个 alpha 向量。为减少更新所有信念点所需的计算量，可以用算法 6.5 的方法限制"表示值函数"的 alpha 向量数目。

该算法先把 Γ 初始化为"所有分量均为式 (6.29)"的单个 alpha 向量（值函数的下界）。给定该 Γ 与信念点集合 B，调用 RandomizedPointBasedUpdate(B, Γ) 产生一个"对值函数给出更紧下界"的新 alpha 向量集合；该新集合可通过再次调用本函数进一步改进；重复该过程直到收敛。

每次更新都需要找一个 alpha 向量集合 Γ′，使其在 B 上各点的值函数不低于 Γ 所表示的值，即 U^{Γ′}(b) ≥ U^Γ(b) 对所有 b ∈ B 成立。过程是：把 Γ′ 初始化为空集、B′ 初始化为 B；从 B′ 中随机取一点 b，调用 BackupBelief(b, Γ) 得到一个新 alpha 向量 α；若 α 在 b 处改进了值，则把 α 加入 Γ′；否则把 Γ 中"在 b 处占优"的 alpha 向量加入 Γ′。B′ 变为"那些尚未被 Γ′ 改进"的点的集合；每次迭代后 B′ 变小，B′ 为空时过程终止。

6.4.5 Point Selection

许多点基值迭代算法从"B 仅含初始信念 b₀"开始，再迭代扩展该集合。最简单的扩展方法（算法 6.6）是对 B 中每个信念状态依据某种 5.1.3 节的探索策略选动作，并把得到的信念状态加入 B——这需要按算法 6.7 从给定动作下的信念状态中抽样观测。

其他方法尝试把点分散到整个可达状态空间。例如算法 6.8 遍历 B，尝试每个可用动作，并把"与 B 中已有点距离最远"的新信念状态加入 B。两个信念状态之间的距离有多种度量方式；所示算法用 L1 距离，即 b 与 b′ 的距离为 Σₛ |b(s) − b′(s)|。

6.4.6 Linear Policies

如 6.2.2 节所述，线性-高斯动力学问题的信念状态可用高斯分布 N(μ_b, Σ_b) 表示。若奖励函数是二次的（4.4 节的假设），可以证明最优策略可以离线精确求解——其形式与 4.4 节完全可观测情形一致，只是把 Kalman 滤波器计算出的 μ_b 替代真实状态。每次得到新观测时用 Kalman 滤波器更新 μ_b，再把 μ_b 与 4.4 节给出的策略矩阵相乘即得最优动作。

6.5 Online Methods

在线方法通过"从当前信念状态出发做规划"决定最优策略。从当前信念可达的信念状态通常只占整个信念空间的一小部分；许多在线方法采用"深度优先的树搜索"到达某一时域。这些在线算法的时间复杂度一般是时域的指数级。虽然在线方法在执行中每步决策需要比离线方法更多的计算，但有时更易于应用到高维问题。

6.5.1 Lookahead with Approximate Value Function

可以在线用"一步前瞻"来改进离线算出的策略。给定当前信念 b，一步前瞻策略为 π(b) = arg max_a [R(b, a) + γ Σₒ P(o | b, a) U(UpdateBelief(b, a, o))]（式 (6.34)），其中 U 是某个近似值函数。U 可用 QMDP、FIB、点基值迭代等离线方法算出的 alpha 向量表示。实验表明，对许多问题，一步前瞻相对基础离线策略能显著提升性能。

近似值函数也可用 4.6.4 节的 rollout 策略采样得到，但要为部分可观测性做修改（算法 6.9）。生成模型 G 给定状态 s 与动作 a，返回抽样的下一状态 s′ 与奖励 r。该算法用单一 rollout 策略 π₀，但可以用一组 rollout 策略并行评估：取在该信念状态处值最大的策略来估计值。

式 (6.34) 中"对所有可能观测求和"的一种替代是采样：可以为每个动作独立调用 SampleObservation(b, a) 生成 n 个观测，然后按式 (6.35) π(b) = arg max_a [R(b, a) + γ (1/n) Σᵢ U(UpdateBelief(b, a, o_{a,i}))] 计算。当观测空间很大时这种策略尤其有用。

6.5.2 Forward Search

一步前瞻可以扩展到任意深度。算法 6.10 定义 SelectAction(b, d, U)，返回"在当前信念 b、深度 d、给定近似值函数 U 下的最优动作 a 与对应期望效用 u"。

d = 0 时无可选动作，返回 a* = nil、效用为 U(b)。d > 0 时，对每个可用动作 a 计算其值并返回最优动作及其值。动作 a 的值由式 (6.36) R(b, a) + γ Σₒ P(o | b, a) U_{d−1}(UpdateBelief(b, a, o)) 给出，其中 U_{d−1}(b′) 是递归调用 SelectAction(b′, d − 1) 返回的期望效用。算法复杂度为 O(|A|ᵈ |O|ᵈ)。类似式 (6.35) 的做法，可以修改该算法对每个动作抽样 n 个观测而非枚举 |O| 个观测；此时复杂度为 O(|A|ᵈ nᵈ)。

6.5.3 Branch and Bound

4.6.2 节在 MDP 语境下介绍的 branch and bound 可直接推广到 POMDP：和 POMDP 版本的 forward search 一样，需要遍历所有观测并更新信念——除此以外算法几乎与 MDP 版本完全相同。for 循环中动作的顺序很重要：为了尽可能多地剪枝搜索空间，动作应按其上界递减的顺序枚举，即若 U(b, aᵢ) ≥ U(b, aⱼ) 则 aᵢ 在 aⱼ 之前。

上界函数 U 可用 QMDP 或 FIB；下界函数 U 可用一个"盲策略"的值函数——盲策略不信念状态而总选同一动作。该值函数可用 |A| 个 alpha 向量表示，按式 (6.37) 计算：α_a⁽ᵏ⁺¹⁾(s) = R(s, a) + γ Σₛ′ T(s′ | s, a) α_a⁽ᵏ⁾(s′)，其中 α_a⁽⁰⁾ = min_s R(s, a) / (1 − γ)。式 (6.37) 与式 (6.26) 类似，但右侧不再对 alpha 向量取最大。

只要 U 与 U 分别是真下界与真上界，branch and bound 的结果与"以 U 为近似值函数的 forward search"的结果相同。实践中 branch and bound 能显著减少选动作所需的计算量；上下界越紧，能剪掉的搜索空间越多。但最坏情况下，branch and bound 的复杂度与 forward search 相当。

6.5.4 Monte Carlo Tree Search

4.6.4 节 MDP 版本的 Monte Carlo tree search 可以推广到 POMDP（算法 6.12）。算法的输入是信念状态 b、深度 d、rollout 策略 π₀。POMDP 算法与 4.6.4 节 MDP 算法的主要区别是"计数与值与历史关联，而不是与状态关联"——历史是过去的观测与动作序列。例如有两个动作 a₀, a₁ 与两个观测 o₀, o₁，则一个可能的历史是 h = a₀ o₁ a₁ o₁ a₀ o₀。算法执行过程中，对一组"历史-动作"对更新值估计 Q(h, a) 与计数 N(h, a)。

与 Q、N 关联的历史可以组织成一棵树（图 6.7）。根节点表示"从初始信念 b 出发的空历史"。算法执行过程中树结构不断扩展：树的层在"动作节点"与"观测节点"间交替；每个动作节点关联值 Q(h, a) 与计数 N(h, a)，其中 h 由"该节点到根节点的路径"确定。算法中 N(h) = Σ_a N(h, a)。

和 MDP 版本一样，MCTS 是 anytime 算法：SelectAction(b, d) 中的循环可随时终止，并返回某种解。已证明只要迭代次数足够，算法收敛到最优动作。

先验知识可通过初始参数 N₀、Q₀ 与 rollout 策略的选择融入该算法。算法不需要在每次决策时重新初始化：历史树及其计数与值估计可在多次调用间保持。所选动作与实际观测对应的观测节点成为下一时刻的根节点。

6.6 Summary

• POMDP 是信念状态上的 MDP。
• POMDP 一般难以精确求解，但常常可以很好地近似。
• 策略可以用 alpha 向量表示。
• 大型问题常常可以在线求解。

6.7 Further Reading

1960 年代就有人注意到 POMDP 可以转化为信念状态上的 MDP [1]。离散状态空间下的信念状态更新是 Bayes 规则的直接应用。Bar-Shalom, Li 与 Kirubarajan 的《Estimation with Applications to Tracking and Navigation》给出了 Kalman 滤波器及其变体的详尽介绍 [2]。Arulampalam 等人给出了粒子滤波器的教程 [3]。Thrun, Burgard 与 Fox 的《Probabilistic Robotics》在机器人应用语境下讨论了多种信念更新方法 [4]。

POMDP 的精确解方法最早由 Smallwood 与 Sondik [5] 及 Sondik [6] 在 1970 年代提出。早期 POMDP 工作有若干综述 [7]–[9]。Kaelbling, Littman 与 Cassandra 提出了识别被支配计划以提升精确解方法效率的技术 [10]。一般地，精确求解 POMDP 是不可行的 [11]、[12]。

近似方法是 POMDP 领域近期研究的焦点。Hauskrecht 讨论了 QMDP 与 fast informed bound 的关系并给出经验结果 [13]。离线近似 POMDP 算法聚焦于点基近似技术，由 Shani, Pineau 与 Kaplow 综述 [14]。点基值迭代（PBVI）由 Pineau, Gordon 与 Thrun 提出 [15]。还有其他更复杂的点基值迭代算法；其中两个最好的算法——Heuristic Search Value Iteration (HSVI) [16]、[17] 与 Successive Approximations of the Reachable Space under Optimal Policies (SARSOP) [18]——通过在信念空间上构造搜索树并维护值函数的上下界。6.4.4 节讨论的随机化点基值迭代基于 Spaan 与 Vlassis 提出的 Perseus 算法 [19]。基于控制器的解也被探索过，用于简洁地表示无限时域策略并避免执行期信念更新 [20]、[21]。Ross 等人综述了多种在线解方法 [22]。Silver 与 Veness 提出了一个用于 POMDP 的 Monte Carlo tree search 算法——Partially Observable Monte Carlo Planning（POMCP）[23]。

本章个人批注

POMDP 形式化的本质，是把"对真实状态的不确定性"压缩为一个"信念状态"——一个关于状态的概率分布。这个改写看似只是换了个状态空间（B 替代 S），实际上把序贯决策问题从"完全可观测"推进到"部分可观测"，并把代价从"在 S 上做规划"换成"在连续空间 B 上做规划"。这种"换空间"的做法是后续 6.3–6.5 全部算法（alpha 向量、值迭代、QMDP、PBVI、MCTS）的共同出发点。

alpha 向量 + PWLC 值函数是 POMDP 理论的"几何内核"：每个 alpha 向量在信念空间上定义一个超平面，多个 alpha 向量的上确界构成的分段线性凸函数就是值函数。这一结构既给出精确解的有限表示，也给出"几何剪枝"的可能（被支配计划对应于"在所有信念上都不占优"的那片超平面）。但 PWLC 也有代价：表示所需的 alpha 向量数随时域指数增长（式 6.25 的 plan 计数 (|O|ʰ − 1)/(|O| − 1) 即此意），且一般 POMDP 是 PSPACE 完全 / 无限时域不可计算——这迫使后续所有方法都只能在"近似"层面努力。

三类离线近似方法各有侧重：QMDP/FIB 是"轻量上界"，把"下一时刻不确定性消失"或"对观测最大化"做一次集成，单次迭代复杂度低、对许多"动作不影响状态可观测性"的问题足够好；点基值迭代（PBVI）一族用有限信念点 B 上维护的 alpha 向量集合来代表值函数，把"在整个信念空间上做 backup"替换为"在选定点上做 backup"，核心难点转向"如何选点"（6.4.5）；基于控制器的方法另辟蹊径，用有限状态机直接表示策略，省去执行期的信念更新——这与"策略 = 信念→动作"的标准 POMDP 框架不同。

在线方法（6.5）的逻辑是另一条主线：与其预先把策略算好，不如在每个时刻从当前信念状态出发做有限深度的搜索。forward search 给出基准，branch and bound 通过上下界剪枝降低常数因子，MCTS 用采样回避显式枚举——三者都建立在 4.6 节 MDP 在线方法的扩展之上：信念状态带来了"对观测分支 + 更新信念"的额外工作，但搜索框架本身几乎不变。MCTS 中"用历史代替状态"是 POMDP 推广中一个有趣的细节：MDP 中状态是 ground truth，POMDP 中"无法访问真实状态"于是只能从"历史"中重建足够的统计量。

与我此前对"不确定性"的认识相比，本章澄清了几个概念上的区分：(1) "状态不确定性"（本章）与"模型不确定性"（第 5 章）不同——前者是"对环境当前所处状态不知"，后者是"对环境动力学与奖励不知"；(2) "信念状态"是 agent internal state，不是物理状态——它甚至可以高维、连续、不与任何物理量对应；(3) "近似"在 POMDP 中不只是工程妥协，而是问题本身的内在属性——一般 POMDP 的不可计算性把"近似"提到了理论必要性的位置。这些区分在读后续章节（特别是决策网络、博弈）时会反复用到。

与上下章的衔接（一段话）

第 4 章把"序贯决策"问题抽象为 MDP，并假设 agent 能直接观测到当前状态 s；第 5 章放宽了"模型已知"的假设，讨论 agent 必须从经验中学习转移与奖励的问题。本章则放宽第 4 章的另一个假设——"状态可观测"——引入 POMDP：agent 只能获得关于状态的"有噪观测" o，必须用一个"信念状态"（状态分布）替代真实状态来做规划。这种放松把第 4 章的转移-奖励模型（T, R）扩展为转移-奖励-观测模型（T, R, O），并把状态空间从离散的 S 换成连续的 B（信念空间）。从算法角度看，本章既向后回用了第 4 章的信念-状态 MDP 框架、值迭代、branch and bound、Monte Carlo tree search（4.6 节），又向前为后续章节铺设了工具：信念更新、alpha 向量表示、近似策略求解。本章在第 5 章 RL 之后的位置也合理：第 5 章的 Bayesian RL 中，agent 同样维护一个"对模型参数的信念"——这一信念 MDP 的形式化与本章的"对状态的信念 MDP"形式化同构，因此本章建立的信念更新与 alpha 向量语言会直接迁移到第 5 章的 BAMD 形式化中。