一句话：研究带期望停时的随机过程优化，证明精确问题与Positivity问题互约，并给出近似求解的复杂度上界。
马尔可夫链和MDP是随机动态系统的有限状态模型；给定状态奖励，经典准则是固定步数T后停止的最大期望总奖励，可用动态规划求解。本文将停时推广为概率分布，在期望停时等于T的约束下最大化期望总奖励。出人意料地，作者证明马尔可夫链上该期望停时问题与Positivity问题（与Skolem问题相关）可相互归约，因此精确可判定性/不可判定性都将是重大突破。鉴于精确问题的困难性，作者转而研究近似版本，证明马尔可夫链可在指数时间求解，MDP可在指数空间求解。
Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.
@article{paperbot2709,
title = {Stochastic Processes with Expected Stopping Time},
author = {Krishnendu Chatterjee and Laurent Doyen},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 4},
year = {2024},
doi = {10.46298/lmcs-20(4:11)2024}
}