Cache performance of priority metrics for mdp solvers

As algorithms scale to solve larger and larger MDPs, it be-comes 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 ef-ficiency of solution algorithms. We contrast the cache effi-ciency of normal value iteration with that of the P-EVA algo-rithm, and introduce the concept of “intrinsic cacheability.” We concentrate on prioritized solution methods, and demon-strate that the choice of priority metric greatly affects cache behavior. Experimental results indicate that the best prior-ity metric allows problems which are four times larger than available RAM to be solved effectively