Parallelizing Reinforcement Learning

Reinforcement learning is an important family of algo-rithms that have been extremely effective in fields such as robotics, economics, and artificial intelligence. Current al-gorithms become increasingly expensive as the state space of the problem increases in size. Additionally, computer ar-chitectures are becoming increasingly parallelized, and ex-isting algorithms need to be reworked to fit within this par-allelization paradigm. We will present a general framework for parallelizing such algorithms. Many reinforcement learning problems (such as robot navigation) have state-spaces that correspond to real, phys-ical spaces, in which states are physical locations and ac-tions transition between neighboring locations. We will demonstrate how problems of this nature can be decom-posed into smaller subproblems that can solved in parallel. We built two implementations of our framework, a MATLAB implementation for rapid prototyping (in which all paral-lelism is simulated) and a Java multicore implementation for which our reported runtimes are actual parallel runtime. Our framework improves the runtime of policy iteration by up to 3 × on an simulated 8 core processor (MATLAB), and up to 203 × on an actual 8 core processor (Java). 1