A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation

By Jalaj Bhandari, Daniel Russo, Raghav Singal. Annual Conference Computational Learning Theory, 2018

409 citations recorded by the source corpus.

Temporal difference learning (TD) is a simple iterative algorithm widely used for policy evaluation in Markov reward processes. Bhandari et al. prove finite time convergence rates for TD learning with linear function approximation. The analysis follows using a key insight that establishes rigorous connections between TD updates and those of online gradient descent. In a model where observations are corrupted by i.i.d. noise, convergence results for TD follow by essentially mirroring the analysis for online gradient descent. Using an information-theoretic technique, the authors also provide results for the case when TD is applied to a single Markovian data stream where the algorithm’s updates can be severely biased. Their analysis seamlessly extends to the study of TD learning with eligibility traces and Q-learning for high-dimensional optimal stopping problems.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/8237b2311d0c41eb4562b3c70eeb1626c64334b6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning (2019, methodology): “Bounds on the ﬁnite-time mean-square error in the general Markovian case have been derived recently in Bhandari et al. (2018).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Distributed TD(0) is first studied in [95], using the proof techniques originated in [209], which requires a projection on the iterates, and the data samples to be independent and identically distributed (i.”
Recent advances in reinforcement learning in finance (2021, background): “…are drawn from a stationary distribution; Lakshminarayanan and Szepesvari (2018) provided an improved ̃′( 1 𝜀 ) bound for iterate-averaged TD(0) with constant step-size; and Bhandari et al. (2018) reached the samemean-square sample complexity ̃′( 1 𝜀 )with a simpler proof and extends the…”
Q-learning with Nearest Neighbors (2018, methodology): “Specific work Method Continuous Unknown Single Online Non-asymptotic state space transition Kernel sample path update guarantees [10], [36], [37] Finite-state approximation Yes No No Yes Yes [43], [22], [41] Q-learning No Yes Yes Yes No [20], [3], [18] Q-learning No Yes Yes Yes Yes [23] Q-learning N”
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, methodology): “Convergence of several model-free RL algorithms has been studied recently in the presence of Markovian data, including but not limited to TD learning and its variants [6, 11, 12, 15, 23, 27, 30, 39, 50, 51], Q-learning [10, 49], and SARSA [53].”