A Concentration Bound for TD(0) with Function Approximation
Siddharth Chandak Vivek S. Borkar
We derive a concentration bound of the type `for all $n \geq n_0$ for some
$n_0$' for TD(0) with linear function approximation. We work with online TD
learning with samples from a single sample path of the underlying Markov chain.
This makes our analysis significantly different from offline TD learning or TD
learning with access to independent samples from the stationary distribution of
the Markov chain. We treat TD(0) as a contractive stochastic approximation
algorithm, with both martingale and Markov noises. Markov noise is handled
using the Poisson equation and the lack of almost sure guarantees on
boundedness of iterates is handled using the concept of relaxed concentration
inequalities.