🤖 AI

Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs

本文介绍了缺失性马尔可夫决策过程（missingness-MDPs），这是一种新颖的部分可观测马尔可夫决策过程（POMDP）子类，它通过缺失数据理论对状态特征不可观测性进行建模，并提出了 PAC 算法，从轨迹数据中学习底层缺失函数以推导ε-最优策略。

原作者： Joshua Wendland, Markel Zubia, Roman Andriushchenko, Maris F. L. Galesloot, Milan Ceska, Henrik von Kleist, Thiago D. Simao, Maximilian Weininger, Nils Jansen

发布于 2026-05-13

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Joshua Wendland, Markel Zubia, Roman Andriushchenko, Maris F. L. Galesloot, Milan Ceska, Henrik von Kleist, Thiago D. Simao, Maximilian Weininger, Nils Jansen

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试教一个机器人穿越迷宫，但机器人的传感器出了故障。有时，它能清晰地看到整个房间；而有时，房间的部分区域会从它的视野中消失。也许是一堵墙不见了，或者一扇门变得不可见。机器人仍然知道迷宫的规则（如何从一个位置移动到另一个位置），但它不知道传感器为何或何时会失效。

本文介绍了一种新方法，帮助机器人在视野不可靠的情况下学会完美行动。以下是使用简单类比进行的分解说明：

1. 问题：“故障眼镜”

在现实世界中，数据往往是不完整的。想象一位医生正在检查病人。医生了解疾病通常如何发展（规则），但有时体温计会坏掉，或者心率监测器会失去信号。医生必须基于不完整的信息做出决策。

在计算机科学中，这通常被建模为POMDP（部分可观测马尔可夫决策过程）。问题在于，标准人工智能模型难以学习数据缺失的原因。这就像试图学习一副扑克牌的规则，而发牌人有时会藏起某些牌，但你不知道他们是随机藏牌、因为发牌技术拙劣，还是根据你手中的牌在作弊。

2. 解决方案：“缺失性马尔可夫决策过程”（miss-MDPs）

作者创建了一种新的、专门化的模型版本，称为miss-MDPs。他们不再将缺失数据视为模糊的“迷雾”，而是将其视为具有三种不同特性的特定“故障”：

MCAR（完全随机缺失）：就像随机闪烁的灯泡。数据缺失了，但这与病人的健康状况或机器人的位置无关。这只是运气不好。
MAR（随机缺失）：就像一台仅在光线太暗时才会失效的相机。数据缺失了，但这取决于你能看到的其他因素（例如，心率监测器仅在温度高时失效，而温度是可见的）。
MNAR（非随机缺失）：棘手的一种。就像一台如果主体在做尴尬的事情就拒绝拍照的相机。数据缺失是因为数据本身的值（例如，心率监测器专门在心率危险地高时失效）。

3. 策略：学习“故障模式”

本文的重大突破在于弄清楚如何教导人工智能从历史中学习这些“故障模式”。

旧方法：通常，试图学习数据为何缺失是不可能的。这就像试图仅通过观察魔术师的手（而不看牌组）来猜测魔术的规则。
新方法：作者意识到，如果“故障”遵循上述三种模式之一（MCAR、MAR 或特定类型的 MNAR），你可以学习该模式。
- 他们使用过去行动和观察的数据集（就像机器人的旅程日志）。
- 他们运行一种统计算法，统计在不同条件下事物缺失的频率。
- 他们构建了一张“缺失性地图”。

4. 结果：“超级规划器”

一旦人工智能学会了“故障模式”（缺失性函数），它就可以将这些知识输入到标准的规划工具中。

保证：本文从数学上证明，如果你给人工智能足够的数据，它将能够足够准确地学习故障模式，从而做出几乎与完美的理论最佳决策相当的决策。
验证：他们在两种场景下测试了这一点：
1. ICU（重症监护室）：模拟医生治疗缺失生命体征的病人。
2. Predator（捕食者）：模拟狮子追逐野猪，而野猪有时会躲藏。

在这两种情况下，他们的方法（先学习故障模式）的表现都显著优于那些试图在不理解缺失数据的情况下直接猜测答案的标准人工智能方法。

5. 局限性

如果“故障”遵循规则（MCAR、MAR 或特定 MNAR），该方法效果极佳。如果缺失性是混乱的，且不遵循这些模式中的任何一种（如他们测试中的“不可识别”MNAR），人工智能就无法完美地学习该模式，性能也会下降。

简而言之：本文指出，“不要仅仅猜测在数据缺失时该如何行动。首先，通过查看历史来弄清楚数据如何缺失。一旦你理解了缺失部分的模式，你就能完美地解开这个谜题。”

技术摘要：缺失性马尔可夫决策过程（miss-MDPs）

问题陈述

本文解决了在状态特征动态缺失的情况下，不确定性下的序贯决策挑战。虽然马尔可夫决策过程（MDPs）假设完全可观测性，但现实世界场景（例如具有不完整传感器数据的医疗诊断）通常涉及缺失特征。标准的部分可观测马尔可夫决策过程（POMDPs）可以通过观测函数对此进行建模；然而，从动作 - 观测历史中学习该函数通常不可识别且在计算上不可行。

作者定义了一个特定的问题设定：给定一个 miss-MDP，其底层 MDP（转移函数 $T$ ）是已知的，但缺失函数 $M$ 是未知的，并拥有一个动作 - 观测轨迹数据集，目标是计算一个 $\epsilon$ -最优策略 $\pi^*$ 。核心难点在于从数据中学习 $M$ 以支持规划，这是一项对一般 POMDP 而言不可能完成的任务，但对于特定子类则可能可行。

方法论

1. miss-MDPs 的定义

作者将**缺失性马尔可夫决策过程（miss-MDPs）**引入为 POMDP 的一个真子类。

结构：miss-MDP 是一个元组 $(S, A, T, b_0, \varrho, Z, M, \gamma)$ 。
观测空间： $Z = \times_{i \in I} (S_i \cup \{\perp\})$ ，其中 $\perp$ 表示缺失特征。
缺失函数（ $M$ ）：一个随机函数 $M: S \to \Delta(Z)$ ，决定特征被观测到或缺失的概率。
缺失类型：该框架采用了经典的缺失数据分类法（Rubin, 1976）：
- MCAR（完全随机缺失）：缺失性与状态值无关。
- MAR（随机缺失）：缺失性仅依赖于已观测特征。作者区分了简单 MAR（仅依赖于始终被观测的特征）和一般 MAR。
- MNAR（非随机缺失）：缺失性依赖于未观测（缺失）的特征值。

2. 学习算法（PAC 保证）

本文提出了 Probably Approximately Correct (PAC) 学习算法，用于从数据集 $D$ 中近似未知的缺失函数 $\hat{M}$ 。该方法依赖于特定缺失类型的可识别性。

算法 $A_{sMAR}$ （针对简单 MAR）：
- 将特征划分为始终被观测的特征（ $\hat{I}_{always}$ ）和可能缺失的特征。
- 基于始终被观测特征的值，估计缺失指示符的概率。
- 定理 1：证明对于简单 MAR，随着数据集规模增加， $\hat{M}$ 以高概率收敛于真实的 $M$ 。
算法 $A_{IMI}$ （针对独立缺失指示符）：
- 适用于 MCAR、简单 MAR 以及可识别 MNAR 的一个子集。
- 假设：(1) 不同特征间的缺失指示符相互独立，(2) 无自 censoring（特征的值不影响其自身的缺失性），(3) 正性（特征有非零概率被观测到）。
- 基于其他观测特征，独立地估计每个特征的缺失概率。
- 定理 2：在这些假设下，证明了 $\hat{M}$ 的 PAC 保证。
策略计算：
- 一旦近似得到 $\hat{M}$ ，作者构建一个完全指定的 miss-MDP $\hat{P}$ 。
- 他们利用现成的 POMDP 求解器（例如 SARSOP）为 $\hat{P}$ 计算 $\epsilon$ -最优策略。
- 定理 3：证明如果 $\hat{M}$ 足够准确，则生成的策略对于真实的 miss-MDP $P$ 是 $\epsilon$ -最优的。

3. 理论洞察

可忽略性：作者证明（备注 1），对于 MAR（包括 MCAR），缺失函数的具体概率对于信念更新（维持当前状态分布）是“可忽略的”，因为它们在贝叶斯法则中相互抵消。然而，该函数对于计算策略本身仍然是必需的，因为信念之间的转移概率依赖于 $M$ 。

主要贡献

形式化：引入 miss-MDPs，将缺失数据理论（MCAR、MAR、MNAR）整合到 POMDP 框架中，定义了一个观测函数可学习的可处理子类。
可识别性分析：确定了缺失函数可从历史数据中学习的特定条件（简单 MAR、无自 censoring 的独立/MNAR），这与 POMDP 观测函数的一般不可识别性形成对比。
PAC 算法：开发了具有形式化 PAC 保证的算法（ $A_{sMAR}$ 、 $A_{IMI}$ ）用于学习缺失函数。
最优性保证：证明了以足够精度学习 $\hat{M}$ 允许计算真实系统的 $\epsilon$ -最优策略。

实验结果

作者在两个基准测试上评估了他们的方法：

ICU：一个医疗决策模型（医生治疗病人），包含 800 个状态。
Predator：一个追捕 - 逃逸游戏（Tag 变体），最多包含 1,765 个状态。

发现：

近似质量：在正确假设下，随着数据集规模增加，学习到的 $\hat{M}$ 与真实 $M$ 之间的总变差（TV）距离收敛于零。
策略性能：随着近似度的提高，从学习到的 miss-MDP 导出的策略收敛于最优策略值（ $\pi^*$ ）。
假设敏感性：错误的假设（例如，当数据是带有自 censoring 的 MNAR 时却假设为 MAR）会导致近似效果差和次优策略。
与基线比较：所提出的基于模型的方法在两个基准测试上显著优于无模型基线（带/不带记忆的 PPO、POMCP）。作者将无模型方法的失败归因于它们无法有效处理 miss-MDP 特有的部分可观测结构，并指出当缺失性被移除时，这些方法取得了成功。

意义与主张

本文声称弥合了缺失数据理论与序贯决策之间的差距。其主要意义在于提供了一种** principled（有原则的）、基于模型的方法来处理 POMDP 中的缺失数据，并具有统计保证**（PAC）。

与以往将缺失性视为偶然事件或依赖无保证的插补方法的工作不同，本工作：

显式地对缺失过程进行建模。
从数据中学习缺失函数，并带有理论误差界限。
利用该学习到的模型来保证所得策略的近似最优性。

作者谦逊地指出，他们当前的方法假设底层 MDP 转移函数是已知的。他们指出，消除这一假设并将框架扩展到一般 miss-POMDP 是未来的研究方向。实证结果证实，在缺失机制遵循可识别模式的情况下，他们的方法优于直接 POMDP 公式（如 POMCP）和深度强化学习方法（如 PPO）。