A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation

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