paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes

在马尔可夫决策过程中混合概率与非概率目标
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 3/10 · 论文属于形式化方法与概率自动机/MDP验证的理论工作，虽与概率系统验证相关，但未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等核心研究方向。引用 1 inbox
Raphaël Berthon, Shibashis Guha, Jean-François Raskin
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：研究MDP中布尔组合的概率与非概率ω-正则目标，给出策略存在性算法和复杂度界。

本文研究马尔可夫决策过程（MDP）中，对若干ω-正则目标进行布尔组合时，判定是否存在满足该组合的策略。每个目标可以要求以必然、几乎必然、存在性或以非零概率成立，因而混合了概率与非概率（定性）目标。作者指出最优策略可能需要随机化且使用无限记忆。论文给出求解一般布尔组合的算法，并分析若干重要子情形，给出相应的复杂度上界，从而刻画这类策略存在性问题的可判定性与计算代价。

问题
在MDP中，判定是否存在策略能满足由ω-正则性质构成的布尔组合，其中各性质需以必然、几乎必然、存在性或非零概率方式成立。
方法
将概率与非概率目标统一为布尔组合，设计策略存在性判定算法，并研究一般情形及相关子情形，分析复杂度界。
评估
通过理论算法与复杂度分析评估问题的可判定性与计算代价；摘要未给出实验评估。
原文摘要（Abstract）

In this paper, we consider algorithms to decide the existence of strategies in MDPs for Boolean combinations of objectives. These objectives are omega-regular properties that need to be enforced either surely, almost surely, existentially, or with non-zero probability. In this setting, relevant strategies are randomized infinite memory strategies: both infinite memory and randomization may be needed to play optimally. We provide algorithms to solve the general case of Boolean combinations and we also investigate relevant subcases. We further report on complexity bounds for these problems.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5527,
  title = {Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes},
  author = {Raphaël Berthon and Shibashis Guha and Jean-François Raskin},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394805}
}