PaperlayerView exact revision on arXiv

Source-linked AI summary

The Effects of Memory Replay in Reinforcement Learning

Ruishan Liu, James Zou

arXiv:1710.06574v1cs.AIcs.LGstat.ML

TL;DR

The effects of replay-buffer size and prioritized sampling on learning dynamics are not well understood. The paper models Q-learning with replay using ODEs and analytic solutions, finding that memory size can slow learning when too large or too small and that adaptive sizing improves performance across evaluated settings.

  • Problem

    The effects of replay-buffer size on learning dynamics and performance, and the mathematical behavior of prioritized replay, remain poorly understood.

    Source: §1 · p. 1

  • Method

    The paper formulates an ODE model of Q-learning with experience replay, derives analytic solutions in a simple setting, and develops an adaptive buffer-sizing algorithm.

    Source: §1 · p. 1, §2 · p. 2

  • Results

    Too little or too much memory can slow learning, and adaptive memory sizing consistently improves over static buffer sizes in the four evaluated settings.

    Source: §5 · p. 8

  • Takeaways & Limitations

    An adaptive replay algorithm evaluates older memories and automatically adjusts buffer size, improving on static memory-size algorithms in the evaluated settings.

    Source: §5 · p. 8

    The simple adaptive memory algorithm tends to shrink the memory, although it already shows good performance in experiments.

    Source: §4 · p. 8

Abstract

from arXiv · show

Experience replay is a key technique behind many recent advances in deep reinforcement learning. Allowing the agent to learn from earlier memories can speed up learning and break undesirable temporal correlations. Despite its wide-spread application, very little is understood about the properties of experience replay. How does the amount of memory kept affect learning dynamics? Does it help to prioritize certain experiences? In this paper, we address these questions by formulating a dynamical systems ODE model of Q-learning with experience replay. We derive analytic solutions of the ODE for a simple setting. We show that even in this very simple setting, the amount of memory kept can substantially affect the agent's performance. Too much or too little memory both slow down learning. Moreover, we characterize regimes where prioritized replay harms the agent's learning. We show that our analytic solutions have excellent agreement with experiments. Finally, we propose a simple algorithm for adaptively changing the memory buffer size which achieves consistently good empirical performance.

1 Introduction

Experience replay reuses stored transitions to update an agent, but the effects of buffer size and prioritized sampling on learning dynamics remain poorly understood. The paper models these effects and studies adaptive buffer sizing.

1 Introduction

  • Experience replay stores transitions in a finite buffer and samples random minibatches for updates, reusing data instead of discarding each experience after one update.The oldest memories are discarded when the buffer is full.Source: §1 · p. 1
  • Buffer size is usually set by heuristics and then fixed, despite limited understanding of how it affects learning dynamics and performance.Source: §1 · p. 1
  • Prioritized experience replay samples surprising experiences more often than uniform replay, but its mathematical behavior is not well understood.Prior work reports empirical performance gains from prioritization.Source: §1 · p. 1
  • The paper derives an ODE model and analytic solutions showing that memory size can non-monotonically affect learning rate, while prioritized replay can also slow learning.Experiments validate the theoretical predictions, and an adaptive replay algorithm consistently improves performance.Source: §1 · p. 1

2 A Dynamical System Model of Experience Replay

The paper represents Q-learning and experience replay with continuous-time dynamics to analyze how learning updates depend on stored experience. The model also describes prioritized sampling and is validated against experiments.

2 A Dynamical System Model of Experience Replay

  • The model defines Q(x, a) as the maximum expected return from state x after first taking action a, with rewards and transitions specified by r, γ, and P.γ is the discount factor and P(x, a, y) is the probability of transitioning from x to y under action a.Source: §2 · p. 2
  • Unlike standard RL, which updates from the most recent transition, experience replay reuses earlier data; the TD update estimates action values with parameters θ.Source: §2 · p. 2
  • The ODE model makes replay’s effects analyzable, with theoretical results obtained numerically and analytically and reported to match experiments well.It is a continuous interpolation of discrete learning steps and assumes the step size is not so large that weights change dramatically over a few steps.Source: §2 · p. 2
  • With experience replay, recent transitions are stored up to capacity N and minibatches are sampled for TD updates; the model expresses parameter dynamics as an expected update.The expected gradient at each step depends on minibatch size m and memory size n(t) ≤ N.Source: §2 · p. 3
  • Prioritized replay changes only the sampling distribution, selecting transitions according to a non-uniform probability based on TD error.The passage gives β = 2 as an instance of the prioritized-replay dynamics.Source: §2 · p. 3

3 Analysis of Memory Effects in a Simple Setting

The authors analyze replay in the LineSearch toy game by solving ODEs for learning dynamics and comparing predictions with experiments. Their analysis finds that memory size can affect learning non-monotonically, and that prioritized replay can perform worse in some settings.

Model setup

  • LineSearch has a one-dimensional state, linear reward, binary actions, and an agent action-value function linear in x + a and weights θ1 and θ2.The analysis derives learning dynamics by analytically solving the ODEs for this toy game.Source: §3 · p. 3

Validation

  • The theoretical learning curves for ER and pER show excellent agreement with experiments on LineSearch.Figure 1 compares numerical solutions with experimental results for both replay settings.Source: Figure 1 · p. 4, §3 · p. 4

Effects of memory size

  • With θ2 fixed at its true value, Δθ1 converges exponentially at a rate that varies non-monotonically with memory size; with θ1 correct, memory size does not affect Δθ2.These analytic results describe the two weights when considered separately.Source: §3 · pp. 4–5
  • For m = 10, optimal memory is around 250; for m = 40, M decreases monotonically as memory grows.For minibatches below 20, performance varies non-monotonically with memory size; above 20, the relation is monotonic.Source: Figure 1 · p. 4, §3 · p. 5
  • For small minibatches, the memory-size effect reflects a trade-off: larger buffers mitigate overshooting, while averaged weight updates first slow and then slightly accelerate.With large minibatches, quick convergence induced by large TD updates means the increase in weight update cannot counteract overshooting.Source: §3 · p. 5

Performance of prioritized replay

  • Prioritized replay performs relatively worse with small memory, particularly when minibatches are not large; with large memory, its quicker updates can support faster convergence.The comparison also identifies settings where ER performs better, pER performs better, or the two behave similarly.Source: Figure 1 · p. 4, §3 · p. 5

Nonzero discount factor

  • For γ > 0, the ODEs and learning results follow principles similar to the γ = 0 case.The paper illustrates this comparison at γ = 0.5.Source: Figure 1 · p. 4, §3 · pp. 5–6

4 Adaptive Memory Size Algorithm

The adaptive experience-replay algorithm adjusts buffer size based on changes in old transitions’ TD errors. It outperformed fixed-size replay in three benchmark games.

4 Adaptive Memory Size Algorithm

  • The algorithm uses rising TD-error magnitude on old transitions as a proxy for overshooting recent memories, and falling magnitude as a sign they may be less useful.It responds by enlarging the buffer in the first case and shrinking it in the second.Source: §4 · p. 6
  • Every k steps, aER shrinks memory when the old transitions’ absolute TD-error sum decreases and increases it otherwise.The algorithm compares the current sum with the sum measured k steps earlier.Source: §4 · p. 6
  • In LineSearch, adaptive memory improved weight updates and mitigated overshooting compared with a fixed buffer of 100.The illustrated setting used minibatch size 10 and step size 10^-3.Source: §4 · p. 6, Figure 2 · p. 6
  • Adaptive memory achieved better performance than fixed-size replay in CartPole, MountainCar, and Acrobot.Figure 3 shows learning curves averaged over 100 new games and corresponding changes in memory size.Source: §4 · p. 7, Figure 3 · p. 7
  • In CartPole, aER increased memory from 100; it outperformed the averaged static-memory strategy in 71% of trials.The reported curves average 100 new games; the best static performance used the full 40,000-transition buffer.Source: §4 · p. 7, Figure 3 · p. 7
  • MountainCar’s best fixed memory was around 50,000; aER adjusted capacity upward or downward from either smaller or larger starting sizes.From an initial size of 150,000, dynamic adjustment also performed better than the best static result.Source: §4 · p. 7, Figure 3 · p. 7
  • In Acrobot, where smaller fixed memory was preferred, aER dynamically decreased memory and beat averaged fixed-memory results in 100% and 95% of trials.Those rates correspond to initial buffer sizes of 25,000 and 100,000, respectively.Source: §4 · p. 7, Figure 3 · p. 7
  • The simple aER algorithm tends to shrink memory; one proposed adjustment is to require a decrease greater than a threshold before shrinking.The threshold could be predefined or learned online.Source: §4 · p. 8

5 Discussion

The discussion reports that replay-buffer size has a non-monotonic effect on learning, even without value-function model mismatch. It also describes consistent empirical gains from adaptive sizing while noting that the study focused on simple settings.

5 Discussion

  • Too little or too much memory can slow learning, even without mismatch between the true and agent value functions.The paper reports that analytic solutions and experiments agree on this non-monotonic effect in simple settings.Source: §5 · p. 8
  • The adaptive algorithm improved over static memory-size algorithms in all four evaluated settings.It evaluates older memories’ usefulness and automatically adjusts buffer size.Source: §5 · p. 8
  • The study focused on simple settings; systematic evaluation of buffer effects in large-scale reinforcement learning remains a proposed direction.The discussion also suggests exploring adaptive prioritization to improve on prioritized replay.Source: §5 · p. 8

A Analytic solutions of the ODEs of the learning dynamics

The paper uses its model to analyze learning properties and replay-memory effects systematically, and discusses memory-size and minibatch-size choices.

A Analytic solutions of the ODEs of the learning dynamics

A.1 Solutions for 1D weights

For one-dimensional weights, the fixed-intercept solution makes the error metric decay exponentially with a cubic-in-step exponent, while memory size changes learning speed non-monotonically. The fixed-slope case instead has memory-independent dynamics and is slower under the reported comparison.

A.1 Solutions for 1D weights

  • After the memory buffer fills, it becomes a sliding window; the error metric decays exponentially with an exponent that is cubic in learning step t.The exponent follows one regime before the buffer fills and another afterward.Source: §A.1 · p. 8
  • A larger minibatch increases the exponent and speeds learning in this case, but the minibatch cannot be too large if the TD-error update is to remain valid.The exponent is strictly proportional to minibatch size m.Source: §A.1 · p. 9
  • In the fixed-intercept case, the steps required to reach target exponent K depend non-monotonically on memory size, and the optimal size eventually falls to 1 as K grows.The analysis attributes the pattern to older transitions helping early, while updating only the current transition becomes preferable later.Source: §A.1 · p. 9
  • Prioritized replay converges faster than uniform selection in the fixed-intercept case because larger absolute TD-errors correspond to larger weight updates.The analytic exponent difference is positive at every learning step.Source: §A.1 · pp. 9–10
  • With fixed slope, the error metric still decays exponentially, but its exponent is proportional to t and learning is slower than with fixed intercept.At minibatch size 5 and step size 5×10−5, fixed slope takes 30000 steps to reach ∆θ/∆θ0 = 0.05, versus fewer than 1200 for fixed intercept.Source: §A.1 · p. 10
  • In the fixed-slope case, all transitions yield the same TD-error and weight update, so memory size does not affect learning dynamics.Prioritized and uniform replay also have the same learning results in this setting.Source: §A.1 · p. 10

A.2 Solution for the full model

The full-model analysis shows that memory size changes learning through a trade-off between overshooting and weight updates. Analytical approximations describe early and late learning stages, while the final metric depends on the state reached when the agent enters the last stage.

A.2 Solution for the full model

  • The early-stage approximation fits the numerical solution well before learning step 100, and its rapid-change values do not depend on memory, policy, minibatch size, or step size.Figure 7 compares analytical curves with numerical solutions; the parameter independence applies to the values after the swift change.Source: §A.2 · pp. 11–12, Figure 7 · p. 11
  • The rigorous result shows a delayed effect because the agent has not fully entered the last stage within the experiment time scale, with neglected Eq. (36) terms also contributing.The passage notes that ∆θ1 and ∆θ2 can vary substantially.Source: §A.2 · p. 12
  • The final metric ∆θ2 does not converge to zero because unidirectional state changes balance with weight updates; reaching the final stage with a small Eq. (37b) value keeps it near zero.The last-stage approximation is compared with the learning curves in Figure 7.Source: §A.2 · p. 12
  • Memory size trades off overshooting against weight updates: size 100 has substantial overshooting, around 250 is optimal, and larger buffers converge more slowly.As memory grows, overshooting is mitigated, but weight updates become smaller.Source: §A.2 · p. 12

B Effects of memory size in prioritized replay

Prioritized replay's performance depends on memory and minibatch size. It can perform worse than regular replay when both are small, but its effects vary across metrics and settings.

B Effects of memory size in prioritized replay

  • For minibatch sizes below 15, the final absolute metric sum M depends non-monotonically on memory size in prioritized replay.Figure 8 compares M across memory and minibatch sizes for ER and pER; smaller M indicates better performance.Source: B Effects of memory size in… · p. 13
  • With both memory and minibatch size small, prioritized replay performs relatively worse than regular replay; at memory size 100 it worsens overshooting, while at 1000 it can converge faster.The comparison varies by metric: prioritization speeds ∆θ2 updates, but not necessarily ∆θ1 updates.Source: B Effects of memory size in… · p. 13

C Nonzero discount factor

For a nonzero discount factor, the theoretical model is reported to fit the experimental result. The passage specifies the parameter setting used for the Figure 10 comparison.

C Nonzero discount factor

  • With γ = 0.5, the theoretical model fits the experimental result, as illustrated in Figure 10.The stated comparison uses minibatch size 5 and step size 0.01.Source: C Nonzero discount factor · p. 14
  • The Figure 10 comparison uses real weights β1 = 0.1 and β2 = 0.5.These are the parameter values specified alongside the reported fit.Source: C Nonzero discount factor · p. 14
Loading 1710.06574v1…