跳转至

Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability

会议: NeurIPS 2025 arXiv: 2510.23744 代码: GitHub 领域: llm_alignment 关键词: POMDP, robust planning, model uncertainty, multi-environment, adversarial belief, value iteration, linear programming

一句话总结

系统研究了多环境 POMDP（ME-POMDP）——一类共享状态/动作/观测空间但转移、观测和奖励函数可任意不同的 POMDP 集合，目标是找到在最坏情况环境下最大化奖励的鲁棒策略。通过引入对抗信念 POMDP（AB-POMDP）统一建模，并证明其与单侧部分可观测随机博弈（POSG）的等价关系，提出精确（值迭代 + LP）和近似（AB-HSVI）算法。

研究背景与动机

部分可观测马尔科夫决策过程（POMDP）广泛应用于机器人、医疗等序列决策场景，但现有算法假设已知精确的转移和观测动态参数，这在实践中往往不成立：

  1. 专家分歧：多个领域专家对模型参数有不同看法（如濒危鸟类保护中，专家对状态转移概率看法不同），产生离散的多环境不确定性
  2. 鲁棒 POMDP 的局限：连续不确定性下的 Robust POMDP 假设凸性、矩形性和动态不确定性，而 ME-POMDP 的离散不确定性天然非矩形，直接应用 RPOMDP 方法会过度保守
  3. 完全可观情况已有研究：多环境 MDP（MEMDP）已被广泛研究，但部分可观情况下的算法尚缺失
  4. 静态 vs 动态不确定性：与假设模型可在每步变化的动态不确定性不同，本文考虑模型在整个时间线上保持一致的静态不确定性

方法详解

整体框架

ME-POMDP 定义：\(\mathcal{M} = (S, A, Z, n, \{T_i\}, \{O_i\}, \{R_i\}, \{b_i\}, \gamma, H)\)，包含 \(n\) 个共享 \(S, A, Z\) 但转移、观测、奖励函数各异的 POMDP 环境。目标：

\[V_{\mathcal{M}}^* = \max_{\pi} \min_{i \in [n]} V_{\mathcal{M}_i}^{\pi}\]

AB-POMDP（对抗信念 POMDP）：将初始信念从单点扩展为集合 \(B \subseteq \Delta(S)\)：

\[V_{\mathsf{M}}^* = \max_{\pi} \min_{b \in B} V_{\mathsf{M}_b}^{\pi}\]

关键理论贡献是证明 ME-POMDP → AB-POMDP → 单侧 POSG 的等价关系链。

关键设计

定理 1（AB-POMDP ↔ POSG）：当信念集 \(B = \Delta(Q)\) 时，AB-POMDP 等价于零和单侧 POSG，其中部分观测的 agent 对应原问题的决策者，完全观测的 nature 通过选择初始状态实现对抗。

定理 2（ME-POMDP → AB-POMDP）：任意 ME-POMDP 可构造等价的 AB-POMDP，状态空间为 \(S \times [n] \times \{1, 2\}\)，nature 选择信念等价于选择环境。

定理 3 & 4（受限模型归约）： - 任意 ME-POMDP 可归约为仅观测函数不同的 PO-MEMDP（多项式开销） - PO-MEMDP 可进一步归约为仅转移函数相同的 MO-POMDP（但状态空间指数增长 \(|S|^n\)）

LP 求解最优策略（定理 5）：给定 \(\alpha\)-向量集 \(\Gamma\)，通过对偶线性规划求解值函数最小化：

原始 LP：\(\min_{b, v} v\)，约束 \(\forall \alpha \in \Gamma: \sum_s \alpha(s) b(s) \leq v\)，\(b \in \Delta(Q)\)

对偶 LP：\(\max_{y, v} v\)，约束 \(\forall s \in Q: \sum_\alpha \alpha(s) y(\alpha) \geq v\)，\(y \in \Delta(\Gamma)\)

对偶解 \(y\) 定义了 \(\alpha\)-向量上的混合策略，是 AB-POMDP 的最优策略。

损失函数 / 训练策略

AB-HSVI 算法：基于 HSVI（启发式搜索值迭代）扩展： 1. 初始化上界（Fast Informed Bound）和下界（固定策略 \(\alpha\)-向量） 2. 通过 LP (3) 计算当前下界下的最坏情况信念 \(b\) 3. 从 \(b\) 出发执行 HSVI 深度优先搜索，更新上下界 4. 重新计算最坏情况信念，若上下界间隙 \(< \epsilon\) 则终止

每次迭代相当于用新的最坏情况起点重启 HSVI，逐步收紧近似质量。

实验关键数据

主实验

Bird 问题（不同模型类型对比）：

| 问题实例 | |S| | n | PO-MEMDP 值/时间 | MO-POMDP 值/时间 | ME-POMDP 值/时间 | |---------|-----|---|------------------|------------------|------------------| | BP3,3,3 | 3 | 3 | 68.26 / 58.5s | 70.44 / 85.0s | 69.62 / 2039.3s | | BP3,3,4 | 3 | 4 | 44.44 / 超时(gap=4.33) | 54.85 / 2976.3s | 44.79 / 超时(gap=6.02) | | BP3,3,5 | 3 | 5 | 74.58 / 3104.3s | 80.01 / 21.1s | 74.59 / 超时(gap=0.61) |

RockSample 问题（不同规模与配置）：

| 问题实例 | |S| | n | 石头近处：值/时间 | 石头远处：值/时间 | |---------|-----|---|------------------|------------------| | RS2,1,2 | 9 | 2 | 16.53 / 11.7s | 16.53 / 11.7s | | RS3,1,2 | 19 | 2 | 16.14 / 52.7s | 14.68 / 170.0s | | RS4,1,2 | 33 | 2 | 15.48 / 130.8s | 13.02 / 1589.0s | | RS5,1,2 | 51 | 2 | 15.40 / 331.4s | 11.03 / 超时(gap=1.46) | | RS7,1,2 | 99 | 2 | 14.54 / 1280.7s | — |

消融实验

模型类型对比（Q3）：MO-POMDP（不确定观测）通常比 PO-MEMDP（不确定转移）收敛更快且值更高，说明观测不确定性比转移不确定性更易处理。

AB-POMDP vs ME-POMDP 建模：所有 RockSample 实例中，AB-POMDP 建模几乎总是比 ME-POMDP 收敛更快，且随环境数增加差距扩大。

鲁棒 vs 非鲁棒（Q2）：鲁棒值接近各单独环境最优值，但远优于错误假设环境下的最坏策略表现，证明了鲁棒策略的必要性。

关键发现

  1. 收敛时间主要随环境数 \(n\) 增长，RockSample 因有终止状态通常比 Bird 问题更快收敛
  2. 环境结构对难度影响大：石头远离初始位置时求解时间可增加 10 倍以上
  3. MO-POMDP 在许多情况下是最高效的建模形式，尽管状态空间增长为 \(|S|^n\)
  4. 生成挑战性基准困难：100 个随机 3 状态 PO-MEMDP 中仅 35 个非平凡（> 30s 求解）

亮点与洞察

  1. 理论体系完整：建立了 ME-POMDP ↔ AB-POMDP ↔ POSG 的完整等价关系，以及 PO-MEMDP ↔ MO-POMDP 的归约关系（图 1）
  2. LP 构造策略：通过对偶 LP 从 \(\alpha\)-向量直接构造混合策略的方法简洁优雅
  3. 避免过度保守：相比直接应用 RPOMDP 的矩形化处理，ME-POMDP 方法保持离散不确定性的精确建模
  4. 模型选择指导：实验揭示了不同建模形式（PO-MEMDP vs MO-POMDP）的性能特征，为实际应用提供选型指南

局限性 / 可改进方向

  1. 可扩展性有限：当前方法在状态数 > 100 或环境数 > 5 时难以在合理时间内收敛
  2. 基准缺乏：ME-POMDP 无现有标准基准，论文自建的基准覆盖有限
  3. MO-POMDP 归约的状态爆炸：\(|S|^n\) 的指数增长限制了大规模问题的求解
  4. 与强化学习方法未对比：仅使用规划方法，未探索 RL 方法在 ME-POMDP 上的可能性
  5. 实际应用案例缺失：Bird 和 RockSample 仅为理论基准，缺乏真实世界的应用验证

相关工作与启发

  • MEMDP (Raskin et al.)：完全可观下的多环境模型，本文将其扩展到部分可观设置
  • Robust POMDP：连续不确定性 + 矩形性假设使其对 ME-POMDP 过度保守
  • HSVI (Smith & Simmons)：经典点基值迭代方法，AB-HSVI 通过 LP 重启策略扩展之
  • 启发：ME-POMDP 框架可直接应用于专家意见分歧的医疗决策、多模拟器的鲁棒机器人规划等场景
  • 与 RLHF/alignment 的联系：从广义上看，对多个「环境」（人类偏好模型）的鲁棒优化与 alignment 中的鲁棒奖励建模有概念相似性

评分

  • ⭐⭐⭐⭐⭐ 理论贡献：等价关系、归约定理、LP 策略构造的理论体系非常完整
  • ⭐⭐⭐ 实验规模：仅小规模基准（状态 < 100），离实际应用有较大距离
  • ⭐⭐⭐⭐ 写作质量：定义清晰、定理叙述严谨、图示直观
  • ⭐⭐⭐ 实用性：可扩展性是主要障碍，短期内难以用于大规模实际问题

总评: ⭐⭐⭐⭐ (3.5/5) — 理论贡献扎实的规划领域工作，建立了 ME-POMDP 的完整理论框架。主要不足是可扩展性和实际应用验证。对鲁棒决策理论研究者有重要参考价值。