一句话：为MC和MDP的累积前景理论值建立多目标可达性联系，给出策略复杂度与EXPTIME算法。
累积前景理论（CPT）兼具理论严谨性与经验现实性，但此前主要用于一次性风险决策，其在序列决策模型马尔可夫链（MC）与马尔可夫决策过程（MDP）中的复杂度问题尚未被研究。本文为MC和MDP的CPT值提出一种新视角，将其与多目标可达性分析相联系，并证明无记忆随机策略对最优性是必要且充分的。基于该联系，作者给出无限时域MDP中计算CPT值的算法，证明该问题属于EXPTIME且固定参数可处理（FPT）；此外，还为MC这一特例提供多项式时间算法。
Cumulative prospect theory (CPT) is the first theory for decision-making under uncertainty that combines full theoretical soundness and empirically realistic features [1], [Page 2]. While CPT was originally considered in one-shot settings for risk-aware decision-making, we consider CPT in sequential decision-making. The most fundamental and well-studied models for sequential decision-making are Markov chains (MCs), and their generalization Markov decision processes (MDPs). The complexity theoretic study of MCs and MDPs with CPT is a fundamental problem that has not been addressed in the literature.Our contributions are as follows: First, we present an alternative viewpoint for the CPT-value of MCs and MDPs. This allows us to establish a connection with multi-objective reachability analysis and conclude the strategy complexity result that memoryless randomized strategies are necessary and sufficient for optimality. Second, based on this connection, we provide an algorithm for computing the CPT-value in MDPs with infinite-horizon objectives. We show that the problem is in EXPTIME and fixed-parameter tractable. Moreover, we provide a polynomial-time algorithm for the special case of MCs.
DOI 原文 ·
@inproceedings{paperbot8642,
title = {Risk-aware Markov Decision Processes Using Cumulative Prospect Theory},
author = {Thomas Brihaye and Krishnendu Chatterjee and Stefanie Mohr and Maximilian Weininger},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00041}
}