On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence

Abstract

We provide non-asymptotic bounds for the well-known temporal difference learning algorithm 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 number of iterations cannot guarantee optimal rate of convergence unless we assume (partial) knowledge 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 dependency while exhibiting the optimal rate of convergence. Furthermore, we propose a variant of TD(0) with linear approximators that incorporates a centering sequence, and establish that it exhibits an exponential rate of convergence in expectation. We demonstrate the usefulness of our bounds on two synthetic experimental settings.

References in corpus (1)

• On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence

Cited by in corpus (14)

• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Reanalysis of Variance Reduced Temporal Difference Learning
• Actor-Critic Reinforcement Learning for Control with Stability Guarantee
• Finite Sample Analyses for TD(0) with Function Approximation
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• Reinforcement Learning Control of Constrained Dynamic Systems with Uniformly Ultimate Boundedness Stability Guarantee
• SVRG for Policy Evaluation with Fewer Gradient Evaluations
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis
• Temporal Difference Learning as Gradient Splitting
• On Convergence of Gradient Expected Sarsa($\lambda$)
• Expected Sarsa($\lambda$) with Control Variate for Variance Reduction