Finite-Sample Analysis of the Temporal Difference Learning
Sergey Samsonov Daniil Tiapkin Alexey Naumov Eric Moulines
In this paper we consider the problem of obtaining sharp bounds for the
performance of temporal difference (TD) methods with linear functional
approximation for policy evaluation in discounted Markov Decision Processes. We
show that a simple algorithm with a universal and instance-independent step
size together with Polyak-Ruppert tail averaging is sufficient to obtain
near-optimal variance and bias terms. We also provide the respective sample
complexity bounds. Our proof technique is based on refined error bounds for
linear stochastic approximation together with the novel stability result for
the product of random matrices that arise from the TD-type recurrence.