Fast and Highly Scalable Bayesian MDP on a GPU Platform

By employing Optimal Bayesian Robust (OBR), Bayesian Markov Decision Process (BMDP) can be a power optimization method to solve large problems. However, due to the “curse of dimensionality”, the data storage limitation hinders the practical application of BMDP. To overcome this impediment, we propose a novel Improved Compressed Sparse Row (ICSR) data structure in this paper, and developed the implementation of BMDP solver with ICSR technique on a heterogeneous platform with GPU. The simulation results demonstrate that our techniques achieve about a 5× reduction in memory utilization over using full matrix, and an average speedup of 4.1× over using full matrix. Additionally, we present a study of the tradeoff between the runtime and the trends of result difference between our ICSR techniques and using full matrix.