A Tighter Convergence Proof of Reverse Experience Replay

• URL: http://arxiv.org/abs/2408.16999v1
• Date: Fri, 30 Aug 2024 04:11:35 GMT
• Title: A Tighter Convergence Proof of Reverse Experience Replay
• Authors: Nan Jiang, Jinzhao Li, Yexiang Xue,
• Abstract summary: 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-rewards in reverse order. We show theoretically that RER converges with a larger learning rate and a longer sequence.
• Score: 16.645967034009225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Hierarchical Decomposition of Prompt-Based Continual Learning: Rethinking Obscured Sub-optimality [55.88910947643436]
  Self-supervised pre-training is essential for handling vast quantities of unlabeled data in practice. HiDe-Prompt is an innovative approach that explicitly optimize the hierarchical components with an ensemble of task-specific prompts and statistics. Our experiments demonstrate the superior performance of HiDe-Prompt and its robustness to pre-training paradigms in continual learning.
  arXiv  Detail & Related papers  (2023-10-11T06:51:46Z)
• Temporal Difference Learning with Experience Replay [3.5823366350053325]
  Temporal-difference (TD) learning is widely regarded as one of the most popular algorithms in reinforcement learning (RL) We present a simple decomposition of the Markovian noise terms and provide finite-time error bounds for TD-learning with experience replay.
  arXiv  Detail & Related papers  (2023-06-16T10:25:43Z)
• A simple but strong baseline for online continual learning: Repeated Augmented Rehearsal [13.075018350152074]
  Online continual learning (OCL) aims to train neural networks incrementally from a non-stationary data stream with a single pass through data. Rehearsal-based methods attempt to approximate the observed input distributions over time with a small memory and revisit them later to avoid forgetting. We provide theoretical insights on the inherent memory overfitting risk from the viewpoint of biased and dynamic empirical risk minimization.
  arXiv  Detail & Related papers  (2022-09-28T08:43:35Z)
• Look Back When Surprised: Stabilizing Reverse Experience Replay for Neural Approximation [7.6146285961466]
  We consider the recently developed and theoretically rigorous reverse experience replay (RER) We show via experiments that this has a better performance than techniques like prioritized experience replay (PER) on various tasks.
  arXiv  Detail & Related papers  (2022-06-07T10:42:02Z)
• Convergence Results For Q-Learning With Experience Replay [51.11953997546418]
  We provide a convergence rate guarantee, and discuss how it compares to the convergence of Q-learning depending on important parameters such as the frequency and number of iterations of replay. We also provide theoretical evidence showing when we might expect this to strictly improve performance, by introducing and analyzing a simple class of MDPs.
  arXiv  Detail & Related papers  (2021-12-08T10:22:49Z)
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback [120.5537226120512]
  We introduce a theory of reinforcement learning in which the learner receives feedback only once at the end of an episode. This is arguably more representative of real-world applications than the traditional requirement that the learner receive feedback at every time step.
  arXiv  Detail & Related papers  (2021-05-29T19:48:51Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We build the connections between the theory of approximate maximum inner product search and the regret analysis of reinforcement learning.
  arXiv  Detail & Related papers  (2021-05-18T05:23:53Z)
• Neurally Augmented ALISTA [15.021419552695066]
  We introduce Neurally Augmented ALISTA, in which an LSTM network is used to compute step sizes and thresholds individually for each target vector during reconstruction. We show that our approach further improves empirical performance in sparse reconstruction, in particular outperforming existing algorithms by an increasing margin as the compression ratio becomes more challenging.
  arXiv  Detail & Related papers  (2020-10-05T11:39:49Z)
• Revisiting Fundamentals of Experience Replay [91.24213515992595]
  We present a systematic and extensive analysis of experience replay in Q-learning methods. We focus on two fundamental properties: the replay capacity and the ratio of learning updates to experience collected.
  arXiv  Detail & Related papers  (2020-07-13T21:22:17Z)
• Accelerated Convergence for Counterfactual Learning to Rank [65.63997193915257]
  We show that convergence rate of SGD approaches with IPS-weighted gradients suffers from the large variance introduced by the IPS weights. We propose a novel learning algorithm, called CounterSample, that has provably better convergence than standard IPS-weighted gradient descent methods. We prove that CounterSample converges faster and complement our theoretical findings with empirical results.
  arXiv  Detail & Related papers  (2020-05-21T12:53:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.