一句话：研究马尔可夫链与MDP中乘性奖励期望值/最优值的计算问题，给出复杂度刻画与算法。
本文研究马尔可夫链（MC）和马尔可夫决策过程（MDP）中每步相乘的乘性奖励期望值。与加性奖励不同，期望值不仅可因常返状态、也可因瞬态状态发散到∞。对MC，在简洁表示整数比较（CSRI）谕示下，值可在多项式时间计算；CSRI仅在某些数论猜想下已知多项式可解。判定值是否为∞或0至少和CSRI一样难，但判定它是否属于这两者之一可多项式时间完成。对MDP，最优值可在多项式空间计算，并给出进一步复杂度与最优调度器结果。所提技术还可求解随机最短路径的乘性变体。若MC/MDP几乎必然到达吸收态，所有问题均多项式时间可解。
This paper studies the expected value of multiplicative rewards, where rewards obtained in each step are multiplied (instead of the usual addition), in Markov chains (MCs) and Markov decision processes (MDPs). One of the key differences to additive rewards is that the expected value may diverge to ∞ not only due to recurrent, but also due to transient states.For MCs, computing the value is shown to be possible in polynomial time given an oracle for the comparison of succinctly represented integers (CSRI), which is only known to be solvable in polynomial time subject to number-theoretic conjectures. Interestingly, distinguishing whether the value is ∞ or 0 is at least as hard as CSRI, while determining if it is one of these two can be done in polynomial time. In MDPs, the optimal value can be computed in polynomial space. Further refined complexity results and results on the complexity of optimal schedulers are presented. The techniques developed for MDPs additionally allow to solve the multiplicative variant of the stochastic shortest path problem. Finally, for MCs and MDPs where an absorbing state is reached almost surely, all considered problems are solvable in polynomial time.
DOI 原文 ·
@inproceedings{paperbot8680,
title = {Multiplicative Rewards in Markovian Models},
author = {Christel Baier and Krishnendu Chatterjee and Tobias Meggendorfer and Jakob Piribauer},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00044}
}