Convergence Results For Q-Learning With Experience Replay

• URL: http://arxiv.org/abs/2112.04213v1
• Date: Wed, 8 Dec 2021 10:22:49 GMT
• Title: Convergence Results For Q-Learning With Experience Replay
• Authors: Liran Szlak, Ohad Shamir
• Abstract summary: 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.
• Score: 51.11953997546418
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A commonly used heuristic in RL is experience replay (e.g.~\citet{lin1993reinforcement, mnih2015human}), in which a learner stores and re-uses past trajectories as if they were sampled online. In this work, we initiate a rigorous study of this heuristic in the setting of tabular Q-learning. 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 replay iterations. We also provide theoretical evidence showing when we might expect this heuristic to strictly improve performance, by introducing and analyzing a simple class of MDPs. Finally, we provide some experiments to support our theoretical findings.

Related papers

• SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learning [89.04776523010409]
  This paper studies the transfer reinforcement learning (RL) problem where multiple RL problems have different reward functions but share the same underlying transition dynamics. In this setting, the Q-function of each RL problem (task) can be decomposed into a successor feature (SF) and a reward mapping. We establish the first convergence analysis with provable generalization guarantees for SF-DQN with GPI.
  arXiv  Detail & Related papers  (2024-05-24T20:30:14Z)
• 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)
• Improving Experience Replay with Successor Representation [0.0]
  Prioritized experience replay is a reinforcement learning technique shown to speed up learning. Recent work in neuroscience suggests that, in biological organisms, replay is prioritized by both gain and need.
  arXiv  Detail & Related papers  (2021-11-29T05:25:54Z)
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs [50.75812033462294]
  We bridge the gap between practical success of Q-learning and pessimistic theoretical results. We present novel methods Q-Rex and Q-RexDaRe. We show that Q-Rex efficiently finds the optimal policy for linear MDPs.
  arXiv  Detail & Related papers  (2021-10-16T01:47:41Z)
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates [67.19481956584465]
  It has been experimentally observed that the efficiency of distributed training with saturation (SGD) depends decisively on the batch size and -- in implementations -- on the staleness. We show that our results are tight and illustrate key findings in numerical experiments.
  arXiv  Detail & Related papers  (2021-03-03T12:08:23Z)
• Learning to Sample with Local and Global Contexts in Experience Replay Buffer [135.94190624087355]
  We propose a new learning-based sampling method that can compute the relative importance of transition. We show that our framework can significantly improve the performance of various off-policy reinforcement learning methods.
  arXiv  Detail & Related papers  (2020-07-14T21:12:56Z)
• 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)

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.