The revised practitioner's guide to MDP model checking algorithms

doi:10.1007/s10009-026-00848-y

The revised practitioner's guide to MDP model checking algorithms

2026-03-01

1

PRE

AI

DOI：10.1007/s10009-026-00848-y

原文链接

原文求助

摘要

En 中文

在不折现可达性和预期奖励属性上的马尔可夫决策过程（MDPs）模型检测对于验证在不确定性下行动的系统至关重要。流行的算法是策略迭代和值迭代的各种变体；在工具竞赛中，大多数参与者依赖后者。这些算法通常需要最坏情况下的指数时间。然而，该问题同样可以表述为线性规划，可在多项式时间内求解。本文详细概述了当今用于MDP模型检测的最先进算法，重点关注性能和正确性。我们强调了它们的基本差异，并描述了各种优化和实现变体。我们使用两个概率模型检测器，在三个基准集上实验比较了所有算法的浮点数和精确算术实现。我们的结果表明，（乐观的）值迭代是一个合理的默认选择，但在特定设置下其他算法更为可取。因此，本文为MDP验证从业者——工具构建者和用户——提供了指南。

Keyword:

Quantitative model checking

Markov decision process

Linear programming

Value iteration

Policy iteration

The revised practitioner's guide to MDP model checking algorithms

摘要

期刊

机构