解决多环境部分可观测决策问题的最优策略计算难题
Multi-Environment POMDPs with Finite-Horizon Objectives
- 将对抗性初始状态引入多环境POMDP，建模更严苛场景
- 证明该问题在有限时域下仍为PSPACE完全，理论难度不变
- 提出新算法，在经典测试集上显著优于已有方法
部分可观测马尔可夫决策过程（POMDP）中，智能体与随机环境交互，仅获得当前状态的部分信息。在多环境POMDP（MEPOMDP）中，初始状态未知且被假设为对抗性选择。本文聚焦于有限时域目标下MEPOMDP的最优值与策略计算问题。该问题在标准POMDP中已被证明为PSPACE完全。主要结果如下：(1) 我们证明在更一般的MEPOMDP设定下，该问题同样为PSPACE完全；(2) 提出一种实用算法，并在经典基准测试上评估，显著优于此前唯一已知算法。
原文摘要 · Abstract (English)
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. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。