Proximal Gradient Temporal Difference Learning: Stable Reinforcement
  Learning with Polynomial Sample Complexity
  In this paper, we introduce proximal gradient temporal difference learning,
which provides a principled way of designing and analyzing true stochastic
gradient temporal difference learning algorithms. We show how gradient TD (GTD)
reinforcement learning methods can be formally derived, not by starting from
their original objective functions, as previously attempted, but rather from a
primal-dual saddle-point objective function. We also conduct a saddle-point
error analysis to obtain finite-sample bounds on their performance. Previous
analyses of this class of algorithms use stochastic approximation techniques to
prove asymptotic convergence, and do not provide any finite-sample analysis. We
also propose an accelerated algorithm, called GTD2-MP, that uses proximal
``mirror maps'' to yield an improved convergence rate. The results of our
theoretical analysis imply that the GTD family of algorithms are comparable and
may indeed be preferred over existing least squares TD methods for off-policy
learning, due to their linear complexity. We provide experimental results
showing the improved performance of our accelerated gradient TD methods.
