Finite Sample Analyses for TD(0) With Function Approximation

TD(0) is one of the most commonly used algorithms in reinforcement learning. Despite this, there is no existing finite sample analysis for TD(0) with function approximation, even for the linear case. Our work is the first to provide such results. Works that managed to obtain convergence rates for online Temporal Difference (TD) methods analyzed somewhat modified versions of them that include projections and stepsize dependent on unknown problem parameters. Our analysis obviates these artificial alterations by exploiting strong properties of TD(0). We provide convergence rates both in expectation and with high-probability. Both are based on relatively unknown, recently developed stochastic approximation techniques.

Authors

• Gal Dalal Nvidia Research
• Balázs Szörényi
• Gugan Thoppe
• Shie Mannor Technion - Israel Institute of Technology NVIDIA Research

Keywords

No keywords are indexed for this paper.