An implementation of dynamic programming for many-core computers

In this paper, computational results by programs which implement the value iteration, a representative of dynamic programming methods, for a computer with a Graphics Processing Unit (GPU) are displayed to demonstrate the potential speedup brought by many-core computers. That implementation is motivated by two expectations: one is that computing a part of data required in a dynamic programming method on each core may decrease the amount of data transferred from a main memory to a GPU thus result in shorter computational time, and the other is that those computations on cores can become efficient by a modeling scheme proposed by the authors. The computational results indicate that the implementation which deploys the scheme seems to be promisingly applicable at least to a toy problem, in which an agent moves around in a slippery plane to maximize accumulated rewards.