Finite-Sample Analysis of Proximal Gradient TD Algorithms
  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. Two revised algorithms are also
proposed, namely projected GTD2 and GTD2-MP, which offer improved convergence
guarantees and acceleration, respectively. The results of our theoretical
analysis show that the GTD family of algorithms are indeed comparable to the
existing LSTD methods in off-policy learning scenarios.
