第六章 状态不确定性
第一节 章节概述
本章讨论了序贯决策问题中状态不可完全观测的情况。在前两章（第四章和第五章）中，我们假设智能体能够精确获知当前所处的状态，然而在现实应用中，由于传感器噪声、环境干扰或信息不完整等限制，智能体往往无法直接观测到真实状态。这种部分可观测性是许多实际决策问题的核心挑战，例如自动驾驶汽车在暴雨天气下难以准确感知周围车辆的位置，或者医疗诊断中医生只能根据有限的检查结果推断患者的病情。
本章引入部分可观测马尔可夫决策过程（Partially Observable Markov Decision Process，POMDP）作为建模框架。POMDP在标准MDP的基础上增加了观测模型，使得智能体只能通过带有噪声的观测来推断真实状态。为了在部分可观测环境下做出决策，智能体需要维护一个关于状态的信念状态（belief state），即在给定历史观测和动作条件下的后验概率分布。通过将信念状态视为MDP的"状态"，POMDP可以被转化为一个在连续信念空间上运行的MDP，这一转化使得我们可以借用前面章节中关于MDP的分析工具。
本章的内容安排如下：首先给出POMDP的正式数学表述，并通过"哭泣婴儿"这一直观示例帮助读者理解问题结构；接着讨论三种不同的信念更新方法——离散状态滤波器、线性高斯滤波器（卡尔曼滤波器）和粒子滤波器；然后分别介绍精确求解方法（alpha向量、条件计划和值迭代）和近似求解方法，后者又分为离线方法（如QMDP、快速知情界、点基值迭代）和在线方法（如前向搜索、分支定界和蒙特卡洛树搜索）。
本章的核心结论是：POMDP在一般条件下难以精确求解（有限水平POMDP是PSPACE完全的，无限水平POMDP甚至是不可计算的），但可以通过精心设计的近似方法在许多实际问题上获得良好的效果。
第二节 关键问题与研究动机
2.1 核心科学问题
本章围绕以下五个关键科学问题展开：
问题一：如何在状态不可完全观测的环境中做出最优决策？ 在标准MDP中，智能体假设已知当前状态\(s_t\)，从而可以直接查表选择动作。但在POMDP中，智能体仅持有对状态的一个概率分布（信念），需要在信念空间上定义并优化累积期望折扣回报。这一问题的本质是将确定性决策扩展到不确定性推理与决策的联合优化。
问题二：如何有效地表示和更新信念状态？ 信念状态是一个分布在整个状态空间上的概率向量。对于离散状态空间，信念是一个有限维向量；对于连续状态空间，信念可以是高斯分布（线性高斯情况下）或一组样本（粒子滤波器）。不同的表示方式直接影响后续的计算效率和近似精度。
问题三：如何避免精确求解POMDP的计算复杂度爆炸？ 精确的POMDP值迭代需要枚举所有可能的历史条件计划，其数量随视野深度\(h\)指数增长：\((|O|^h - 1) / (|O| - 1)\)。对于实际应用而言，这种指数爆炸是不可接受的，因此必须发展近似技术。
问题四：离线近似与在线规划之间的权衡是什么？ 离线方法在执行前预计算策略或价值函数，适合计算资源充足且环境相对稳定的场景；在线方法在每个决策节点上进行实时搜索，适合状态空间巨大或环境可能变化的场景。两类方法各有优劣，实际应用需要根据问题特性进行选择。
问题五：如何将信息收集动作纳入决策框架？ 某些动作（如"在变道前向右肩看"）本身不产生直接回报，但能够减少状态不确定性，从而间接提升未来决策质量。QMDP等简单近似方法在处理这类信息收集动作时表现不佳，这是近似算法设计中的一个重要挑战。
2.2 研究动机与实际意义
研究POMDP的理论与算法具有广泛的实际意义。在机器人导航领域，机器人依靠有噪声的传感器数据（如激光雷达的测量误差）来估计自身位置和周围障碍物；在医疗决策领域，医生基于不完全的检查结果（症状、化验指标）来诊断疾病并决定治疗方案；在自动控制系统中，飞机需要根据有限的传感器信息在恶劣天气条件下做出安全决策；在金融交易领域，交易算法只能根据历史价格和有限的公开信息做出投资决策。这些场景都天然地适合用POMDP建模。
第三节 主要公式与推导
3.1 POMDP的数学定义
一个POMDP由以下元组定义：
其中\(S\)为状态空间，\(A\)为动作空间，\(T(s'|s,a)\)为状态转移概率，\(R(s,a)\)为奖励函数，\(O(o|s')\)为观测概率（给定下一状态产生某观测的概率），\(\gamma \in [0,1]\)为折扣因子。
信念状态更新公式（离散情况）：
给定当前信念\(b(s)\)、执行的动作为\(a\)、观测到\(o\)后，新的信念\(b'(s')\)由递归贝叶斯估计给出：
式（6.11）是本章最基础的公式之一。它表明信念更新分为两步：预测步（根据转移模型\(T\)预测可能的新状态）和更新步（根据新的观测\(o\)利用似然\(O(o|s',a)\)修正预测）。
信念状态 MDP 的转移函数：
将POMDP转化为信念空间上的MDP，其转移函数为：
展开后可得：
其中\(\delta\)为克罗内克 delta 函数，\(\text{UpdateBelief}(b,a,o)\)按照式（6.11）计算。
信念状态 MDP 的即时奖励：
即原始奖励函数在信念分布上的期望。
3.2 线性高斯滤波（卡尔曼滤波器）
对于具有线性高斯动力学和线性高斯观测的系统，可以进行精确的信念更新。设动力学模型为：
观测模型为：
初始信念为高斯分布\(b(s) = \mathcal{N}(s|\mu_b, \Sigma_b)\)。则信念更新遵循以下方程：
卡尔曼增益： $\(K \leftarrow \Sigma_p O_s^T (O_s \Sigma_p O_s^T + \Sigma_o)^{-1} \tag{6.15}\)$
均值更新： $\(\mu_b \leftarrow \mu_p + K(o - O_s \mu_p) \tag{6.16}\)$
协方差更新： $\(\Sigma_b \leftarrow (I - K O_s) \Sigma_p \tag{6.17}\)$
其中预测均值\(\mu_p = T_s \mu_b + T_a a\)，预测协方差\(\Sigma_p = T_s \Sigma_b T_s^T + \Sigma_s\)。
3.3 Alpha 向量与值函数表示
对于有限视野 POMDP，最优值函数是分段线性凸（piecewise-linear and convex）的。设\(b\)为信念向量，\(\alpha_a\)为与动作\(a\)关联的 alpha 向量（其第\(s\)个分量为\(R(s,a)\)），则一步值函数为：
对于多步条件计划\(p\)，其 alpha 向量\(\alpha_p\)递归定义为：
多步值函数为：
最优值函数为所有条件计划 alpha 向量的上确界：
3.4 QMDP 与快速知情界（FIB）
QMDP 近似使用全观测情况下的 Q 函数构造 alpha 向量，迭代公式为：
FIB 在 QMDP 基础上考虑了部分可观测性：
QMDP 假设下一时刻状态不确定性完全消失，提供价值函数的上界；FIB 考虑了观测对信念的影响，上界更紧。
3.5 点基值迭代（PBVI）
设有一组采样信念点\(B = \{b_1, \ldots, b_n\}\)和对应的 alpha 向量集合\(\Gamma = \{\alpha_1, \ldots, \alpha_n\}\)，则任意信念点\(b\)处的值函数估计为：
_backup 操作对应的 alpha 向量计算公式为：
3.6 在线方法公式
一步前瞻策略：
前向搜索的递归公式：
蒙特卡洛树搜索的UCB选动作：
第四节 关键算法与建模方法
4.1 信念更新算法
4.1.1 离散状态滤波器
对于离散状态空间，信念更新直接应用贝叶斯公式（式6.11）。该方法的核心思想是：首先基于转移模型预测各状态的先验概率，然后根据观测似然修正这些概率。算法的时间复杂度为\(O(|S|^2 |O|)\)，在状态数适中时完全精确。
应用示例（哭泣婴儿问题六步推演）：
| 步骤 | 动作 | 观测 | 信念状态 \((P(\text{不饿}), P(\text{饿}))\) | 说明 |
|---|---|---|---|---|
| 1 | — | — | \((0.5, 0.5)\) | 初始信念：均匀分布 |
| 2 | 不喂 | 哭 | \((0.0928, 0.9072)\) | 哭泣是饿的噪声指示，但可信度高 |
| 3 | 喂 | 不哭 | \((1.0, 0.0)\) | 喂食确定性地使婴儿不再饿 |
| 4 | 不喂 | 不哭 | \((0.9759, 0.0241)\) | 未喂食时饿的概率很低 |
| 5 | 不喂 | 不哭 | \((0.9701, 0.0299)\) | 持续不哭，饿的概率略微上升 |
| 6 | 不喂 | 哭 | \((0.4624, 0.5376)\) | 之前几乎确定不饿，现在哭提供的新信息使饿的概率上升但未过半 |
4.1.2 线性高斯滤波器（卡尔曼滤波）
当系统动力学和观测模型均为线性且噪声为高斯分布时，后验信念始终保持高斯分布。卡尔曼滤波器提供了一种\(O(|S|^3)\)的精确闭式更新。需要特别注意的是，实际系统中很少有严格满足线性高斯假设的情况，但卡尔曼滤波器经常作为非线性系统的基准方法（如扩展卡尔曼滤波、无迹卡尔曼滤波等变体的基础）。
4.1.3 粒子滤波器
当状态空间连续、动力学非线性或状态维度较高时，粒子滤波器通过采样近似的方式表示信念分布。其核心思想是用一组加权样本（粒子）来逼近真实的后验分布。
带拒绝采样的粒子滤波器（Algorithm 6.2）：对每个粒子，从当前信念中随机选一个状态\(s\)，从前向模型采样\((s', o') \sim G(s,a)\)，若\(o'\)与实际观测\(o\)匹配则保留\(s'\)。问题在于当观测空间连续或较大时，拒绝率极高。
不带拒绝的加权粒子滤波器（Algorithm 6.3）：从\(s\)采样\(s' \sim G(s,a)\)，计算权重\(w_i = O(o|s_i',a)\)，然后根据权重对粒子进行重采样（重要性采样）。该方法避免了拒绝采样的效率问题，是更常用的变体。
粒子滤波器的粒子匮乏（particle deprivation）问题：极端情况下，所有粒子都可能远离真实状态，导致近似质量严重下降。可以通过添加过程噪声（抖振）来缓解。
4.2 精确求解：Alpha 向量与条件计划
Alpha 向量是 POMDP 策略表示的核心工具。每个 alpha 向量定义信念空间中的一片超平面，值函数是这些超平面的上包络（upper envelope）。对于哭泣婴儿问题，一步最优策略是"不喂"（对应 alpha 向量\(\alpha_{\text{not-feed}} = (0, -10)\)），因为在该问题设置下喂食的即时成本高于不喂食的潜在成本。然而当视野扩展到多步时，最优策略变为仅在\(P(\text{饿}) > 0.28206\)时喂食。
4.3 离线近似方法
QMDP：将 POMDP 的信念 MDP 的转移近似为全观测 MDP 的转移。优点是计算简单（仅需标准 MDP 值迭代），缺点是无法捕捉信息收集动作的价值。QMDP 对所有信念状态提供上界（过度乐观）。
快速知情界（FIB）：在 QMDP 的基础上考虑了观测模型，使得 alpha 向量更紧。FIB 提供比 QMDP 更低（更接近真实）的上界。两者均只产生\(|A|\)个 alpha 向量，计算效率高。
点基值迭代（PBVI）：核心思想是只在一组精心选择的信念点上计算和存储 alpha 向量，其他信念点的值函数通过插值（取这些 alpha 向量的最大值）获得。PBVI 的关键是信念点选择策略：随机扩展适合初始探索；基于距离的扩展（Algorithm 6.8）确保新信念点与已有集合保持一定距离，使覆盖范围更均匀。
线性策略（Linear Policy）：对于线性高斯动力学 + 二次奖励的特殊情况，最优策略可以离线精确计算——使用卡尔曼滤波更新均值向量\(\mu_b\)，然后将\(\mu_b\)代入全观测 LQR 控制器即可。
4.4 在线方法
前向搜索（Algorithm 6.10）：从当前信念状态出发，递归地展开动作-观测树直到深度\(d\)，计算每个动作的期望折扣回报。时间复杂度\(O(|A|^d |O|^d)\)，随深度指数增长是该方法的主要瓶颈。
分支定界（Algorithm 6.11）：在前向搜索基础上，利用上界函数\(\bar{U}\)和下界函数\(\underline{U}\)对搜索树进行剪枝。如果某动作的上界\(\bar{U}(b,a) \leq\) 当前最优值\(u\)，则立即跳过该动作的整个子树。上下界的紧度直接决定剪枝效率。
蒙特卡洛树搜索（MCTS，Algorithm 6.12）：MCTS 通过采样（而非枚举）来估计动作值。关键创新在于将 MDP 中的状态节点替换为历史节点（histories），因为在部分可观测环境下，真正有意义的信息是观测-动作历史而非隐状态本身。MCTS 的 UCB 公式平衡了探索与利用，其 anytime 特性使其在时间受限的场景下尤为实用。
第五节 主要结论
结论一：POMDP 是 MDP 在信念空间上的自然扩展，但引入了连续状态空间的计算挑战。 通过将信念状态视为 MDP 的状态，我们获得了 POMDP 的一个等效 formulation。然而，信念空间是连续的（对于离散状态空间是\(|S|-1\)维单纯形，对于连续状态空间维数更高），这使得精确求解在计算上极为困难。
结论二：对于线性高斯系统，卡尔曼滤波器提供了精确的最优信念更新；对于一般系统，粒子滤波器是一种灵活且通用的近似方法。 卡尔曼滤波器的精确性来源于线性高斯假设下后验分布的共轭特性；粒子滤波器则通过采样避免了分布形式的限制，但引入了近似误差和粒子匮乏风险。
结论三：Alpha 向量提供了一种紧凑而优雅的策略表示方式，使得值函数的分段线性凸结构得以显式表达。 有限视野 POMDP 的最优值函数始终是分段线性凸的，这一结构性质是所有基于 alpha 向量的算法的理论基础。
结论四：精确求解一般 POMDP 在计算上不可行——有限视野 PSPACE 完全，无限视野甚至不可计算。 这一复杂度结论推动了离线近似和在线近似两大方向的发展。
结论五：离线近似方法（QMDP、FIB、PBVI）通过牺牲最优性换取计算可行性，各有不同的近似误差特性。 QMDP 假设不确定性迅速消散，适合不确定性主要由动作引起而非信息收集驱动的场景；FIB 通过更精细的近似改进了 QMDP；PBVI 通过局部精细化提供了更好的逼近质量。
结论六：在线方法（前向搜索、分支定界、MCTS）通过实时计算在当前信念状态附近寻找好的动作，特别适合高维或复杂动力学问题。 在线方法的优势在于不需要对整个信念空间建立全局近似，而是根据当前决策需求进行有针对性的搜索。
第六节 挑战与开放问题
挑战一：维度灾难与连续空间处理。 即使使用 PBVI，当状态空间和动作空间的维度增加时，所需采样的信念点数量仍可能指数增长。如何在高维连续状态空间中有效地选择代表性信念点，仍然是一个活跃的研究领域。
挑战二：信息收集动作的近似误差。 QMDP 等简单离线方法在信息收集场景（如主动感知、探索性决策）下表现不佳，因为这些方法假设状态不确定性在下一步会自动消失。设计能够正确捕捉信息收集动作价值的近似算法是一个重要挑战。FIB 在这方面的改进有限，PBVI 等方法也需要精心设计信念点选择策略来更好地覆盖信息收集场景。
挑战三：粒子匮乏问题。 粒子滤波器在高维状态空间中容易出现粒子匮乏——大多数粒子集中在一个低概率区域，而真实状态可能位于粒子稀疏的区域。虽然重采样、抖振和辅助粒子滤波器等技术可以缓解这一问题，但尚无根本性解决方案。
挑战四：无限水平 POMDP 的理论难度。 无限水平 POMDP 已被证明是不可计算的，这意味着我们永远无法在有限时间内得到最优解。这一理论结果推动了对"可接受"近似程度的定义和研究，即在有限计算资源下能多好地逼近最优解。
挑战五：在线方法的计算时间约束。 在许多实际应用（如自动驾驶、实时控制系统）中，每个决策步骤允许的计算时间是严格受限的。MCTS 等 anytime 算法虽然可以在任意时间中断，但返回解的质量与运行时间之间需要仔细权衡。
挑战六：跨模态观测与异构传感器融合。 现实世界的系统通常从多个不同类型的传感器获取信息，这些传感器具有不同的噪声特性、更新频率和可靠性。如何在 POMDP 框架内有效地融合异构信息，仍然是一个具有实际重要性的开放问题。
第七节 个人思考与批判性分析
7.1 建模哲学的思考
Kochenderfer 在本章中选择的呈现方式体现了 POMDP 研究中一种常见的工程导向思维：从精确方法出发，指出其不可计算性，然后转向近似方法。这种叙述结构清晰地展示了从理论到实践的过渡，但也可能使读者过快放弃对精确解的追求。
笔者认为，在某些特定应用场景（如低维离散状态空间的博弈问题）中，精确的 alpha 向量方法仍然是有价值的工具。PSPACE 完全性并不意味着所有具体实例都不可解——它只是说明存在最坏情况实例难以处理。实践中，许多实际 POMDP 实例由于结构稀疏或报酬函数特殊，实际上是可以精确求解或接近精确求解的。
7.2 近似方法取舍的思考
QMDP 和 FIB 的比较分析（如图 6.6 所示）给笔者留下了深刻印象。QMDP 产生的上界在\(P(\text{饿})\)较大时显著高于最优值，这说明"假设下一秒状态已知"这一近似在不确定性较大的区域是有害的。这一现象提醒我们：近似的质量可能因状态区域而异，一个对所有信念状态统一提供近似的算法可能在某些区域产生巨大误差。
PBVI 的思想与强化学习中的函数逼近有异曲同工之妙——都是用有限的基函数（或采样点）来表示连续的值函数。但 PBVI 选择在信念空间采样而非在状态空间采样，这是 POMDP 问题结构的一个独特之处。
7.3 与前一章的关联
本章内容与第五章的 MDP 近似动态规划方法形成了良好的呼应。QMDP 可以看作是用全观测 Q 函数作为信念 MDP 价值函数的一个基函数；前向搜索实际上是 BFS/DFS 搜索在信念空间的直接扩展；分支定界则借鉴了 4.6.2 节中相同名称的方法。这种跨章节的方法论连贯性是本书的一大优点。
7.4 值得进一步研究的方向
如果有机会独立实现这些算法，笔者会重点关注以下方面：
- 哭泣婴儿问题的 alpha 向量可视化：手动计算不同视野深度下的 alpha 向量，绘制价值函数超平面，理解分段线性凸结构如何随深度演化。
- PBVI 与 SARSOP/HSVI 的比较实现：深入理解如何通过更智能的信念点选择和边界维护来提高近似质量。
- 将 MCTS 应用于一个小型 POMDP 实例：通过实验观察 UCB 参数\(c\)对探索-利用平衡的影响。
7.5 对本书整体结构的思考
第六章将"状态不确定性"单独成章，与第四章的"MDP 基础"和第五章的"近似方法"形成递进关系。这种安排符合教学逻辑：先建立完全可观测的基础，再逐步放宽假设引入不确定性。然而，由于 POMDP 本质上是 MDP + 贝叶斯推理的组合，读者需要同时具备 MDP 求解和概率推理两方面知识，这对前置准备要求较高。
公式汇总
| 编号 | 名称 | 形式 | 物理意义 | 类型 |
|---|---|---|---|---|
| (6.1) | 信念转移函数 | $\tau(b' | b,a) = P(b' | b,a)$ |
| (6.5) | 展开后的信念转移 | $\tau(b' | b,a) = \sum_o \delta_{b'}(\text{UpdateBelief}(b,a,o)) \sum_{s',s} O(o | s',a) T(s' |
| (6.6) | 信念即时奖励 | \(R(b,a) = \sum_s R(s,a) b(s)\) | 奖励函数在信念分布上的期望 | (T) |
| (6.11) | 离散信念更新 | $b'(s') \propto O(o | s',a) \sum_s T(s' | s,a) b(s)$ |
| (6.12) | 线性高斯动力学 | $T(z | s,a) = \mathcal{N}(z|T_s s + T_a a, \Sigma_s)$ | 状态转移分布 |
| (6.13) | 线性高斯观测 | $O(o | s) = \mathcal{N}(o|O_s s, \Sigma_o)$ | 观测分布 |
| (6.15) | 卡尔曼增益 | \(K = \Sigma_p O_s^T (O_s \Sigma_p O_s^T + \Sigma_o)^{-1}\) | 最优滤波器增益 | (T) |
| (6.16) | 信念均值更新 | \(\mu_b \leftarrow \mu_p + K(o - O_s \mu_p)\) | 后验均值修正 | (T) |
| (6.17) | 信念协方差更新 | \(\Sigma_b \leftarrow (I - K O_s) \Sigma_p\) | 后验协方差修正 | (T) |
| (6.19) | 单步 alpha 向量 | \(U^*(b) = \max_a \alpha_a^T b\) | 值函数表示 | (T) |
| (6.22) | 多步 alpha 向量 | $\alpha_p(s) = R(s,a) + \gamma \sum_{s',o} T(s' | s,a) O(o | s',a) \alpha_{p(o)}(s')$ |
| (6.25) | 最优值函数 | \(U^*(b) = \max_p \alpha_p^T b\) | alpha 向量对上确界 | (T) |
| (6.26) | QMDP 迭代 | $\alpha_a^{(k+1)}(s) = R(s,a) + \gamma \sum_{s'} T(s' | s,a) \max_{a'} \alpha_{a'}^{(k)}(s')$ | 全观测 Q 函数驱动 |
| (6.27) | FIB 迭代 | $\alpha_a^{(k+1)}(s) = R(s,a) + \gamma \sum_{s',o} T(s' | s,a) O(o | s',a) \max_{a'} \alpha_{a'}^{(k)}(s')$ |
| (6.28) | PBVI 值估计 | \(U^\Gamma(b) = \max_{\alpha \in \Gamma} \alpha^T b\) | 基于采样点的值函数插值 | (T) |
| (6.33) | PBVI backup | $\alpha_a(s) \leftarrow R(s,a) + \gamma \sum_{s',o} O(o | s',a) T(s' | s,a) \alpha_{a,o}(s')$ |
| (6.34) | 一步前瞻 | $\pi(b) = \arg\max_a [R(b,a) + \gamma \sum_o P(o | b,a) U(\text{UpdateBelief}(b,a,o))]$ | 在线改进策略 |
| (6.36) | 前向搜索递归 | $U_d(b) = \max_a [R(b,a) + \gamma \sum_o P(o | b,a) U_{d-1}(\text{UpdateBelief}(b,a,o))]$ | 递归树搜索 |
注：(T)=理论推导公式，(E)=经验公式。本章所有公式均为理论推导。
参考文献
- Smallwood, R. D., & Sondik, E. J. (1973). The optimal control of partially observable Markov decision processes over a finite horizon. Operations Research.
- Sondik, E. J. (1978). The optimal control of partially observable Markov decision processes. PhD thesis, Stanford University.
- Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence.
- Pineau, J., Gordon, G., & Thrun, S. (2006). Point-based value iteration: An anytime algorithm for POMDPs. IJCAI.
- Spaan, M. T. J., & Vlassis, N. (2005). Perseus: Randomized point-based value iteration for POMDPs. Journal of Artificial Intelligence Research.
- Silver, D., & Veness, J. (2010). Monte-Carlo planning in large POMDPs. NeurIPS.
- Ross, S., et al. (2008). Online planning algorithms for POMDPs. JAIR.
- Hauskrecht, M. (2000). Value-function approximations for partially observable Markov decision processes. JAIR.