Cache Performance of Priority Metrics for MDP Solver

David Wingate and Kevin D. Seppi

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.