Design and Analysis of Accelerated Algorithms for Temporal Difference Methods using Dynamical Systems

We present a dynamical systems approach for designing accelerated algorithms for semi-gradient TD from first principles and propose two accelerated methods, namely Polyak TD and Nesterov TD. We show that the underlying dynamical system of our proposed methods converges and derive the corresponding accelerated convergence rates by extending the energy conservation law-based analysis framework proposed by \citet{suh2022continuous} to semi-gradient TD. We also provide the exact expressions for damping parameters to get convergence. Finally, we discretize our models to obtain four implementable algorithms and show performance comparable to that of other TD methods in small, linear prediction tasks.