提出可解的不完全可观测决策模型，让智能体最终获得完整状态信息。
Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives
- 引入揭示机制，确保智能体几乎必然获得完整状态信息
- 构建两类可解的POMDP模型，理论保证策略存在性
- 将问题转化为有限信念支持的马尔可夫决策过程，算法简洁精确
部分可观测马尔可夫决策过程（POMDP）是序贯决策中不确定性建模的重要工具。我们关注如何构造具有理论保障的算法，判断智能体是否存在策略以概率1满足给定规范。这一经典问题在简单欧米伽正则目标下已被证明不可判定，主要源于对不确定事件的推理困难。本文引入一种揭示机制，通过要求几乎必然地使智能体最终获得当前状态的完整信息来限制信息损失。核心技术成果是为两类称为弱揭示和强揭示的POMDP构建了精确算法。重要的是，这些可判定情形可约化为有限信念支撑的马尔可夫决策过程分析，从而为一大类POMDP提供了概念清晰且精确的算法。
原文摘要 · Abstract (English)
Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether the agent has a strategy ensuring a given specification with probability 1. This well-studied problem is known to be undecidable already for very simple omega-regular objectives, because of the difficulty of reasoning on uncertain events. We introduce a revelation mechanism which restricts information loss by requiring that almost surely the agent has eventually full information of the current state. Our main technical results are to construct exact algorithms for two classes of POMDPs called weakly and strongly revealing. Importantly, the decidable cases reduce to the analysis of a finite belief-support Markov decision process. This yields a conceptually simple and exact algorithm for a large class of POMDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。