A Simple Finite-Time Analysis of TD Learning with Linear Function
  Approximation
Aritra Mitra
We study the finite-time convergence of TD learning with linear function
approximation under Markovian sampling. Existing proofs for this setting either
assume a projection step in the algorithm to simplify the analysis, or require
a fairly intricate argument to ensure stability of the iterates. We ask:
\textit{Is it possible to retain the simplicity of a projection-based analysis
without actually performing a projection step in the algorithm?} Our main
contribution is to show this is possible via a novel two-step argument. In the
first step, we use induction to prove that under a standard choice of a
constant step-size $\alpha$, the iterates generated by TD learning remain
uniformly bounded in expectation. In the second step, we establish a recursion
that mimics the steady-state dynamics of TD learning up to a bounded
perturbation on the order of $O(\alpha^2)$ that captures the effect of
Markovian sampling. Combining these pieces leads to an overall approach that
considerably simplifies existing proofs. We conjecture that our inductive proof
technique will find applications in the analyses of more complex stochastic
approximation algorithms, and conclude by providing some examples of such
applications.