A Memory-Efficient Markov Decision Process Computation Framework Using BDD-based Sampling Representation Conference Paper uri icon


  • 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. Although Markov Decision Process (MDP) has wide applications in autonomous systems as a core model in Reinforcement Learning, a key bottleneck is the large memory utilization of the state transition probability matrices. This is particularly problematic for computational platforms with limited memory, or for Bayesian MDP, which requires dozens of such matrices. To mitigate this difficulty, we propose a highly memory-efficient representation for probability matrices using Binary Decision Diagram (BDD) based sampling, and develop a corresponding (Bayesian/classical) MDP solver on a CPU-GPU platform. Simulation results indicate our approach reduces memory by one and two orders of magnitude for Bayesian/classical MDP, respectively.

name of conference

  • DAC '19: The 56th Annual Design Automation Conference 2019

published proceedings

  • Proceedings of the 56th Annual Design Automation Conference 2019

author list (cited authors)

  • Zhou, H. e., Khatri, S. P., Hu, J., & Liu, F.

complete list of authors

  • Zhou, He||Khatri, Sunil P||Hu, Jiang||Liu, Frank

publication date

  • January 1, 2019 11:11 AM


  • ACM  Publisher