一句话：提出端分量分类算法，求解整数权重 MDP 的随机最短路径与权重有界可达性问题并给出复杂度界。
论文研究状态-动作对带整数权重的有限状态马尔可夫决策过程（MDP）。作者给出新算法，按累积权重的极限行为对端分量（end component）分类，并用于求解两类基本问题。其一，提出经典随机最短路径问题的多项式时间算法，推广了特殊加权 MDP 类的结果。其二，研究权重有界（重复）可达性的定性概率约束：判定是否存在调度器使若干权重有界可达条件的析取几乎必然成立；该问题属于 NP ∩ coNP，可在伪多项式时间内求解，且至少与二人 mean-payoff 博弈同难，而对调度器全称量化的问题可在多项式时间内求解。
The paper deals with finite-state Markov decision processes (MDPs) with integer weights assigned to each state-action pair. New algorithms are presented to classify end components according to their limiting behavior with respect to the accumulated weights. These algorithms are used to provide solutions for two types of fundamental problems for integer-weighted MDPs. First, a polynomial-time algorithm for the classical stochastic shortest path problem is presented, generalizing known results for special classes of weighted MDPs. Second, qualitative probability constraints for weight-bounded (repeated) reachability conditions are addressed. Among others, it is shown that the problem to decide whether a disjunction of weight-bounded reachability conditions holds almost surely under some scheduler belongs to NP ∩ coNP, is solvable in pseudo-polynomial time and is at least as hard as solving two-player mean-payoff games, while the corresponding problem for universal quantification over schedulers is solvable in polynomial time.
@inproceedings{paperbot4374,
title = {Stochastic Shortest Paths and Weight-Bounded Properties in Markov Decision Processes},
author = {Christel Baier and Nathalie Bertrand and Clemens Dubslaff and Daniel Gburek and Ocan Sankur},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209184}
}