An Exact Distributed Newton Method for Reinforcement Learning

摘要

In this paper, we propose a distributed second- order method forreinforcement learning. Our approach is the fastest in literature so-far as itoutperforms state-of-the-art methods, including ADMM, by significant margins.We achieve this by exploiting the sparsity pattern of the dual Hessian andtransforming the problem of computing the Newton direction to one of solving asequence of symmetric diagonally dominant system of equations. We validate theabove claim both theoretically and empirically. On the theoretical side, weprove that similar to exact Newton, our algorithm exhibits super-linearconvergence within a neighborhood of the optimal solution. Empirically, wedemonstrate the superiority of this new method on a set of benchmarkreinforcement learning tasks.