Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the finite-time performance of the TD(0) temporal-difference method with linear function approximation, focusing on on-policy i.i.d. samples and employing a constant learning step alongside the Polyak-Juditsky averaging technique. The authors establish a new convergence rate for the Mean-Square Error (MSE) that is optimal with respect to the number of iterations, robust against ill-conditioning, and independent of the smallest eigenvalue of the covariance matrix, marking a significant advancement over existing O(1/k) rates. Additionally, they introduce the PCTD(0) variant, which shows improved convergence under strong mixing conditions in the Markov Chain framework.
Achieving a convergence rate for TD(0) that is both fast and robust, independent of the covariance matrix's smallest eigenvalue, could redefine expectations for temporal-difference learning.
In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) fast in the sense that it admits an optimal dependency in the number of iterations k (i.e., of order 1/k), (ii) robust to ill-conditioning: it only depends on an initial error and modelindependent constants and (iii) sharp up to a multiplicative constant lower than 11. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing O(1/k) rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.