Cache Performance of Priority Metrics for MDP Solvers

As algorithms scale to solve larger and larger MDPs, it becomes impossible to store all of the model information of the MDP and the supporting data structures of the algorithm in RAM. This motivates the study of the disk-based-cache efficiency of solution algorithms. We contrast the cache efficiency of normal value iteration with that of the P-EVA algorithm, and introduce the concept of “intrinsic cacheability.” We concentrate on prioritized solution methods, and demonstrate that the choice of priority metric greatly affects cache behavior. Experimental results indicate that the best priority metric allows problems which are four times larger than available RAM to be solved effectively