Reachability-based Model Reduction for Markov Decision Process

Santos, F., Barros, L. N. and Trevizan, F., Journal of the Brazilian Computer Society

We are working on the camera-ready of this paper and it will be available in my website soon. Below is the abstract of this paper.

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.

  • News and Highlights
    • h-pom, h-roc, and i2-dual won the best paper award at ICAPS'17!
    • New efficient approach to solve SSPs and C-SSPs with dead ends (UAI'17).
    • Solving SSPs and MDPs with PCTL* constraints to appear on TABLEAUX'17.
    • h-pom and h-roc: the first heuristics able to handle probabilities and costs for SSPs and C-SSPs (ICAPS'17).
    • i-dual won the best paper award at ICAPS'16!
    • QTM won the best paper award from the AI committee of TRB'16! (demo).
    • i-dual: combining AI and OR to efficiently solve constrained SSPs (ICAPS'16).
  • Word cloud of my papers:
  • wordcloud
    large wordcloud