Finite-Sample Analysis of GTD Algorithms

Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, Marek Petrik
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:89-98, 2015.

Abstract

In this paper, we conduct the finite-sample analysis of the gradient temporal difference learning (GTD) family of algorithms. Previous analyses of this class of algorithms use ODE techniques to show their asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done. Moreover, there has been very little sample complexity analysis for reinforcement learning algorithms in off-policy learning scenarios. In this paper, we formulate the GTD methods as stochastic gradient algorithms w.r.t. a primal-dual saddle-point objective function, and then conduct a saddle-point error bound analysis to obtain finite-sample error bounds of GTD algorithms family. Two revised algorithms are also proposed as projected GTD2 and GTD2-MP for better convergence guarantee and acceleration, respectively. The results of our theoretical analysis show that the GTD algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-liu15b, title = {Finite-Sample Analysis of {GTD} Algorithms}, author = {Liu, Bo and Liu, Ji and Ghavamzadeh, Mohammad and Mahadevan, Sridhar and Petrik, Marek}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {89--98}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/liu15b/liu15b.pdf}, url = {https://proceedings.mlr.press/r13/liu15b.html}, abstract = {In this paper, we conduct the finite-sample analysis of the gradient temporal difference learning (GTD) family of algorithms. Previous analyses of this class of algorithms use ODE techniques to show their asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done. Moreover, there has been very little sample complexity analysis for reinforcement learning algorithms in off-policy learning scenarios. In this paper, we formulate the GTD methods as stochastic gradient algorithms w.r.t. a primal-dual saddle-point objective function, and then conduct a saddle-point error bound analysis to obtain finite-sample error bounds of GTD algorithms family. Two revised algorithms are also proposed as projected GTD2 and GTD2-MP for better convergence guarantee and acceleration, respectively. The results of our theoretical analysis show that the GTD algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Finite-Sample Analysis of GTD Algorithms %A Bo Liu %A Ji Liu %A Mohammad Ghavamzadeh %A Sridhar Mahadevan %A Marek Petrik %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-liu15b %I PMLR %P 89--98 %U https://proceedings.mlr.press/r13/liu15b.html %V R13 %X In this paper, we conduct the finite-sample analysis of the gradient temporal difference learning (GTD) family of algorithms. Previous analyses of this class of algorithms use ODE techniques to show their asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done. Moreover, there has been very little sample complexity analysis for reinforcement learning algorithms in off-policy learning scenarios. In this paper, we formulate the GTD methods as stochastic gradient algorithms w.r.t. a primal-dual saddle-point objective function, and then conduct a saddle-point error bound analysis to obtain finite-sample error bounds of GTD algorithms family. Two revised algorithms are also proposed as projected GTD2 and GTD2-MP for better convergence guarantee and acceleration, respectively. The results of our theoretical analysis show that the GTD algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios. %Z Reissued by PMLR on 04 October 2026.
APA
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S. & Petrik, M.. (2015). Finite-Sample Analysis of GTD Algorithms. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:89-98 Available from https://proceedings.mlr.press/r13/liu15b.html. Reissued by PMLR on 04 October 2026.

Related Material