# A Tighter Convergence Proof of Reverse Experience Replay

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 30 Aug 2024.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

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

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction](https://mlsanity.com/paper/2003.07305/) (2020)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update](https://mlsanity.com/paper/1805.12375/) (2018)
- [Principled Exploration via Optimistic Bootstrapping and Backward Induction](https://mlsanity.com/paper/2105.06022/) (2021)
- [Recall Traces: Backtracking Models for Efficient Reinforcement Learning](https://mlsanity.com/paper/1804.00379/) (2018)
- [Actor Prioritized Experience Replay](https://mlsanity.com/paper/2209.00532/) (2022)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Large Batch Experience Replay](https://mlsanity.com/paper/2110.01528/) (2021)
- [Rate of Convergence and Error Bounds for LSTD(λ)](https://mlsanity.com/paper/1405.3229/) (2014)
- [Reverse Experience Replay](https://mlsanity.com/paper/1910.08780/) (2019)

## Abstract (arXiv)

In reinforcement learning, Reverse Experience Replay (RER) is a recently proposed algorithm that attains better sample complexity than the classic experience replay method. RER requires the learning algorithm to update the parameters through consecutive state-action-reward tuples in reverse order. However, the most recent theoretical analysis only holds for a minimal learning rate and short consecutive steps, which converge slower than those large learning rate algorithms without RER. In view of this theoretical and empirical gap, we provide a tighter analysis that mitigates the limitation on the learning rate and the length of consecutive steps. Furthermore, we show theoretically that RER converges with a larger learning rate and a longer sequence.