Cache Efficient Value Iteration
Anuj Jain, Sartaj K. Sahni · 2019
Value Iteration (VI) is a powerful, though time consuming, approach to solve Markov Decision Processes (MDPs). Exisitng algorithms for VI incur a large number of cache misses. Motivated by the observation that, on modern computers, the cost of a cache miss is two to three orders of magnitude more than that of an arithmetic operation, we explore the possibility of improving the performance of VI by reducing the number of cache misses, possibly at the expense of increasing the number of backups. We demonstrate experimentally that the strategies proposed by us, in this paper, to improve the cache efficiency of VI result in speedups of up to a factor of 3.7 when incorporated into state-of-the-art VI software.