  We provide non-asymptotic bounds for the well-known temporal difference
learning algorithm TD(0) with linear function approximators. These include
high-probability bounds as well as bounds in expectation. Our analysis suggests
that a step-size inversely proportional to the number of iterations cannot
guarantee optimal rate of convergence unless we assume (partial) knowledge of
the stationary distribution for the Markov chain underlying the policy
considered. We also provide bounds for the iterate averaged TD(0) variant,
which gets rid of the step-size dependency while exhibiting the optimal rate of
convergence. Furthermore, we propose a variant of TD(0) with linear
approximators that incorporates a centering sequence, and establish that it
exhibits an exponential rate of convergence in expectation. We demonstrate the
usefulness of our bounds on two synthetic experimental settings.
