Temporal Difference Learning as Gradient Splitting

Abstract

Temporal difference learning with linear function approximation is a popular method to obtain a low-dimensional approximation of the value function of a policy in a Markov Decision Process. We give a new interpretation of this method in terms of a splitting of the gradient of an appropriately chosen function. As a consequence of this interpretation, convergence proofs for gradient descent can be applied almost verbatim to temporal difference learning. Beyond giving a new, fuller explanation of why temporal difference works, our interpretation also yields improved convergence times. We consider the setting with $1/\sqrt{T}$ step-size, where previous comparable finite-time convergence time bounds for temporal difference learning had the multiplicative factor $1/(1-\gamma )$ in front of the bound, with $\gamma$ being the discount factor. We show that a minor variation on TD learning which estimates the mean of the value function separately has a convergence time where $1/(1-\gamma )$ only multiplies an asymptotically negligible term.

References in corpus (5)

• Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
• Approximate Temporal Difference Learning is a Gradient Descent for Reversible Policies
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling

Cited by in corpus (1)

• Distributed TD(0) with Almost No Communication