A multigraph and multiplex approach for the recognition of important states in Markov decision processes
将重构转移图从简单无权重图扩展到加权多图和多重图，通过调整经典中心性度量来识别马尔可夫决策过程中的重要状态，实验表明该方法在非稀疏奖励环境中优于现有技术。
Abstract The determination of the most important states in Markov Decision Processes has recently gained interest due to its applicability in increasing both the performance and the explainability of Reinforcement Learning algorithms. In this paper, we extend the concept of Reconstructed Transition Graphs from simple unweighted graphs to advanced notions of weighted Multigraphs and Multiplexes to better represent Markov Decision Processes and identify the most important states. To this end, we adapt the classical centrality measures (betweenness, closeness, and eigenvector) to our proposed frameworks and delineate the theoretical assumptions required to ensure their existence and uniqueness. Compared to other graph-based measures available in the literature, this novel approach can take into account the different rewards and transform them into weights specific to the task. Computational experiments indicate the superior capacity of these measures in the detection of dangerous states and high-reward situations for non-sparse reward environments compared to state-of-the-art methodologies. Moreover, a statistical analysis carried out allowed to discover significant interconnections between the newly defined centrality measure structures and Q-value-based measures that are helpful for the recognition of critical states.