A Finite Time Analysis of Temporal Difference Learning With Linear
  Function Approximation
  Temporal difference learning (TD) is a simple iterative algorithm used to
estimate the value function corresponding to a given policy in a Markov
decision process. Although TD is one of the most widely used algorithms in
reinforcement learning, its theoretical analysis has proved challenging and few
guarantees on its statistical efficiency are available. In this work, we
provide a simple and explicit finite time analysis of temporal difference
learning with linear function approximation. Except for a few key insights, our
analysis mirrors standard techniques for analyzing stochastic gradient descent
algorithms, and therefore inherits the simplicity and elegance of that
literature. Final sections of the paper show how all of our main results extend
to the study of TD learning with eligibility traces, known as TD($\lambda$),
and to Q-learning applied in high-dimensional optimal stopping problems.
