arXiv cs.AI· L\'eonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger, Stefanie Muroya·· 4 小时前AI 评分39
多环境 POMDP 在有限时域目标下的最优值与策略计算研究
Multi-Environment POMDPs with Finite-Horizon Objectives
AI 导读
一项 NeurIPS 2026 主会论文研究了多环境部分可观测马尔可夫决策过程(MEPOMDP)在有限时域目标下的最优值与策略计算问题。论文证明该问题在 MEPOMDP 中仍为 PSPACE-complete,并证明至多 n 个确定性策略的混合足以应对 n 个环境。作者提出一种实用算法,在经典基准上显著优于此前唯一已知算法。
正文 · 原文
Abstract:Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. The extension is nontrivial: MEPOMDPs require reasoning about beliefs and payoffs across environments, and deterministic policies are no longer enough for optimal payoff. While the lower bound transfers immediately, the upper bound requires new techniques: we prove that mixtures of at most $n$ deterministic policies suffice for $n$ environments and show how to explore them without storing exponential-size policy descriptions. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.
| Comments: | 33 pages, accepted at NeurIPS 2026 (Main Track) |
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2605.07537 [cs.AI] |
| (or arXiv:2605.07537v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2605.07537 arXiv-issued DOI via DataCite |
Submission history
From: Filip Cano [view email]
[v1]
Fri, 8 May 2026 10:14:03 UTC (2,637 KB)
[v2]
Fri, 13 Nov 2026 10:01:48 UTC (2,647 KB)
来源:arXiv cs.AI · arxiv.org