# Finite-Time Analysis of Temporal Difference Learning with Experience Replay

arXiv: https://arxiv.org/abs/2306.09746 · HTML: https://mlsanity.com/paper/2306.09746/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 16 Jun 2023.

## Builds on (most cited first, 21 of 21)

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Revisiting Fundamentals of Experience Replay](https://mlsanity.com/paper/2007.06700/) (2020)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Parrot: Data-Driven Behavioral Priors for Reinforcement Learning](https://mlsanity.com/paper/2011.10024/) (2020)
- [FinRL: A Deep Reinforcement Learning Library for Automated Stock Trading in Quantitative Finance](https://mlsanity.com/paper/2011.09607/) (2020)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Target-Based Temporal Difference Learning](https://mlsanity.com/paper/1904.10945/) (2019)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Topological Experience Replay](https://mlsanity.com/paper/2203.15845/) (2022)
- [Analysis of Stochastic Processes through Replay Buffers](https://mlsanity.com/paper/2206.12848/) (2022)
- [Reverse Experience Replay](https://mlsanity.com/paper/1910.08780/) (2019)
- [Sim and Real: Better Together](https://mlsanity.com/paper/2110.00445/) (2021)

## Built on by (most cited first, 1 of 1)

- [A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Bounds](https://mlsanity.com/paper/2609.18782/) (2026)

## Abstract (arXiv)

Temporal-difference (TD) learning is widely regarded as one of the most popular algorithms in reinforcement learning (RL). Despite its widespread use, it has only been recently that researchers have begun to actively study its finite time behavior, including the finite time bound on mean squared error and sample complexity. On the empirical side, experience replay has been a key ingredient in the success of deep RL algorithms, but its theoretical effects on RL have yet to be fully understood. In this paper, we present a simple decomposition of the Markovian noise terms and provide finite-time error bounds for TD-learning with experience replay. Specifically, under the Markovian observation model, we demonstrate that for both the averaged iterate and final iterate cases, the error term induced by a constant step-size can be effectively controlled by the size of the replay buffer and the mini-batch sampled from the experience replay buffer.