MDPG: Markov Decision Process with Graph Representation in Reinforcement Learning
Yide Yu, Dennis Wong, Yan Ma, Yue Liu · 2023
The Markov Decision Process (MDP) is a widely used framework for modeling decision-making problems. However, its traditional representation as a set of states and actions may be limited in its ability to capture complex dependencies between variables. This study proposes an alternative representation of MDP, called MDP represented by the graph (MDPG), which leverages Graph Theory to represent and address decision-making problems. In this paper, we provide the definition of MDPG and valid walks, and explore its degree and induced subgraph properties. Additionally, we prove that MDPG is capable of detecting non-stationary and partially observable processes, which is an important advantage over traditional MDP models. To enhance the practical application of MDPG, we redefine the state-value and state-action-value functions. Overall, our study demonstrates the potential of MDPG as a promising framework for modeling decision-making problems, and offers a new perspective on the use of Graph Theory in the field of decision-making.