On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
Nathaniel Korda, L. A. Prashanth · 2015
We provide non-asymptotic bounds for the well-known temporal difference learning algo-rithm TD(0) with linear function approximators. These include high-probability bounds as well as bounds in expectation. Our analysis suggests that a step-size inversely proportional to the num-ber of iterations cannot guarantee optimal rate of convergence unless we assume (partial) knowl-edge of the stationary distribution for the Markov chain underlying the policy considered. We also provide bounds for the iterate averaged TD(0) variant, which gets rid of the step-size depen-dency while exhibiting the optimal rate of con-vergence. Furthermore, we propose a variant of TD(0) with linear approximators that incorpo-rates a centering sequence, and establish that it exhibits an exponential rate of convergence in ex-pectation. We demonstrate the usefulness of our bounds on two synthetic experimental settings. 1.