Cache-Efficient Memory Representation of Markov Decision Processes
by Jaël Champagne Gareau, Éric Beaudry, and Vladimir Makarenkov
Published onMay 27, 2022
Cache-Efficient Memory Representation of Markov Decision Processes
·
Abstract
Research in automated planning typically focuses on the development of new or improved algorithms. Yet, an equally important but often overlooked topic is that of how to actually implement these algorithms e ciently. In this study, we are making an attempt to close this gap in the context of optimal Markov Decision Process (MDP) planning. Precisely, we present a novel cache-e cient memory representation of MDPs, which we call CSR-MDP, that takes advantage of low-level hardware features such as memory hierarchy. We evaluate the speed improvement provided by our memory representation by comparing the performance of CSR-MDP with the performance obtained by traditional MDP representation. We show that by using our CSR-MDP memory representation, existing MDP solvers, including VI, LRTDP and TVI, are able to nd an optimal policy an order of magnitude faster
Creative Commons Attribution 4.0 International License (CC-BY 4.0)