Finite-Sample Analysis of Proximal Gradient TD Algorithms

Understand

In this paper, we analyze the convergence rate of the gradient temporal difference learning (GTD) family of algorithms.

• Previous analyses of this class of algorithms use ODE techniques to prove asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done.
• Moreover, there has been not much work on finite-sample analysis for convergent off-policy reinforcement learning algorithms.
• In this paper, we formulate GTD methods as stochastic gradient algorithms w.r.t.~a primal-dual saddle-point objective function, and then conduct a saddle-point error analysis to obtain finite-sample bounds on their performance.