Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation
Gandharv Patil, Prashanth L.A., Dheeraj Nagaraj, Doina Precup
Abstract
We study the finite-time behaviour of the popular temporal difference (TD) learning algorithm, when combined with tail-averaging. We derive finite time bounds on the parameter error of the tail-averaged TD iterate under a step-size choice that does not require information about the eigenvalues of the matrix underlying the projected TD fixed point. Our analysis shows that tail-averaged TD converges at the optimal O (1/t) rate, both in expectation and with high probability. In addition, our bounds exhibit a sharper rate of decay for the initial error (bias), which is an improvement over averaging all iterates. We also propose and analyse a variant of TD that incorporates regularisation, and show that this variant fares favourably in problems with ill-conditioned features.
BibTeX
@InProceedings{pmlr-v206-patil23a,
title = {Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation},
author = {Patil, Gandharv and L.A., Prashanth and Nagaraj, Dheeraj and Precup, Doina},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {5438--5448},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/patil23a/patil23a.pdf},
url = {https://proceedings.mlr.press/v206/patil23a.html},
abstract = {We study the finite-time behaviour of the popular temporal difference (TD) learning algorithm, when combined with tail-averaging. We derive finite time bounds on the parameter error of the tail-averaged TD iterate under a step-size choice that does not require information about the eigenvalues of the matrix underlying the projected TD fixed point. Our analysis shows that tail-averaged TD converges at the optimal O (1/t) rate, both in expectation and with high probability. In addition, our bounds exhibit a sharper rate of decay for the initial error (bias), which is an improvement over averaging all iterates. We also propose and analyse a variant of TD that incorporates regularisation, and show that this variant fares favourably in problems with ill-conditioned features.}
}