Reachability-based model reduction for Markov decision process

Brazilian Computer Society. Journal

Felipe M Santos¹  Felipe W Trevizan²  Leliane N Barros³ 

[1] Institute of Mathematics and Statistics - University of São Paulo, Brazil;o Paulo, Sã

关键词: Probabilistic planning;    Markov decision process;    Model reduction;    Stochastic bisimulation;   

DOI  :  10.1186/s13173-015-0024-1

学科分类：农业科学（综合）

来源: Springer U K

【 摘 要 】

This paper presents how to improve model reduction for Markov decision process (MDP), a technique that generates equivalent MDPs that can be smaller than the original MDP. In order to improve the current state-of-the-art, we take advantage of the information about the initial state of the environment. Given this initial state information, we perform a reachability analysis and then employ model reduction techniques to the reachable space of the original problem. Further, we also eliminate redundancies in the original MDP in order to speed up the model reduction phase. We also contribute by empirically comparing our technique against state-of-the-art model reduction techniques and MDP solvers that do not perform model reduction. The results show that our approach dominates the current model reduction algorithms and outperforms general MDP solvers in dense problems, i.e., problems in which actions have many probabilistic outcomes.

【 授权许可】

CC BY