Organizing Experience: A Deeper Look at Replay Mechanisms for Sample-based Planning in Continuous State Domains

1 Introduction

• Experience replay stores previous agent-environment interactions and replays sampled transitions to update the value function.The paper describes replay as a stochastic planning approach that can improve data efficiency.Source: §1 · p. 1
• Dyna can add predecessor states to its search-control queue, while ER replays stored transitions and cannot systematically perform backward search.The paper also identifies on-policy sampling as a Dyna option unavailable to ER.Source: §1 · p. 1
• The paper investigates whether Dyna’s design differences from ER produce empirical advantages and whether Dyna’s added complexity is worthwhile.The stated contribution includes a study of design decisions for one-step, sample-based planning with function approximation.Source: §1 · pp. 1–2
• The paper develops REM-Dyna, a semi-parametric Dyna algorithm intended to combine benefits of Dyna-style planning and experience replay.The paper proposes Reweighted Experience Models as data-efficient, incrementally learnable models that are efficient to sample.Source: §1 · p. 1

2 Background

• The agent observes an MDP state, selects an action, receives a transition and scalar reward, and seeks a policy maximizing expected return.The discount function supports a unified specification of episodic and continuing tasks.Source: §2 · p. 2
• The agent estimates an action-value function from data using a parameterized value function and a sample model that outputs one possible next state and reward.The value-function parameterization allows linear and nonlinear approximations.Source: §2 · p. 2
• After each interaction, the agent updates its model and value function, then performs planning by sampling a state-action pair and simulating a one-step transition.Experience replay and Dyna are identified as implementations of this framework.Source: §2 · p. 2

3 One-step Sample-based Planning Choices

• Sample-based planners draw a next state and reward for a stochastic update, whereas alternatives approximate expected updates; the paper favors sampling for lower computational cost and decoupled model and value parameterizations.The cited expected-update alternatives include kernel-based RL and kernel mean embeddings.Source: §3 · p. 2
• Continuous-domain planners must manage stored samples; recent transitions or state-action pairs are a basic strategy, while absolute TD-error prioritization can guide selection.The experiments compare recency and priority for adding and deleting samples.Source: §3 · p. 2
• A model can generate predecessor states leading into a high-priority state, enabling backward search that ER’s transition buffer can support only in a limited way.The cited heuristic of raising the preceding transition’s priority does not provide systematic backward search.Source: §3 · p. 2
• Dyna can select a state by recency or priority and query the model for the current policy’s action, while ER replays complete stored transitions.On-policy search control focuses planning on actions the agent currently estimates to be best.Source: §3 · pp. 2–3

4.1 Generative Models for Dyna

• The model design targets incremental adaptation, data efficiency, robustness to forgetting, conditional queries, and computationally efficient sampling.These are the paper's stated desiderata for online sample-based planning and acting.Source: §4.1 · p. 3
• KDE is data-efficient and low-bias but scales linearly with data, while mixture and neural models face incremental-training, local-minimum, forgetting, or training-cost issues.The neural models discussed may require experience replay themselves.Source: §4.1 · p. 3

4.2 Reweighted Experience Models

• REM models use representative prototype transitions and product kernels, whose factorization simplifies conditional densities for forward and predecessor models.The same prototypes support p(s′|s, a) and p(s|s′, a).Source: §4.2 · p. 3
• REM estimates conditional coefficients directly, avoiding repeated adjustment of joint and marginal weights as policies and prototypes change.The conditional distribution is described as stationary under a changing policy, and each coefficient can be estimated independently.Source: §4.2 · p. 4
• REM sampling needs only conditional coefficients, and learning and sampling scale linearly with the number of prototypes.The paper also notes that specialized kernels can extend kernel-based approaches to high-dimensional problems.Source: §4.2 · p. 4

Experimental design

• The experiments first examine buffer and queue design in tabular settings, then compare REM-Dyna with ER and other learned models under function approximation.All methods delete the oldest samples; deleting by lowest priority was ineffective in the studied problems.Source: §5 · p. 4

Search-control variants

• For Dyna and ER, predecessor variants combine prioritized sampling with adding predecessors; Dyna samples predecessors from its model, while ER uses the preceding buffer sample’s priority as a heuristic.The study also compares on-policy Dyna, which queues states and simulates actions under the current policy.Source: §5 · p. 5

Experimental scope

• The microworlds are designed to expose phenomena relevant to larger domains, while scaled-down computation and model size reflect limitations of moving to larger settings.The authors frame these experiments as systematic, issue-oriented investigations that suggest directions for further work in real domains.Source: §5 · p. 5

Results in the Tabular Setting

• The tabular study varies gridworld size and stochasticity, while fixing the discount at 0.95; the stochastic transition reaches the intended next state with probability 0.925.The experiments use Q-learning, epsilon-greedy action selection, five planning steps, and a queue or buffer capped at 1,024 samples.Source: §5 · p. 5
• Dyna with priorities and predecessors outperforms every ER variant, with the gap growing as gridworld size increases; prioritized ER degrades considerably in the stochastic setting.Figure 1 shows accumulated reward over 100,000 time-steps in deterministic and stochastic gridworlds of varying sizes.Source: §5 · p. 5, Figure 1 · p. 5

Results for Continuous States

• The continuous-state comparison tests REMs against a two-layer neural network trained on a sliding buffer of 1,000 transitions and a Linear Dyna model with a learned reverse model.The Linear Dyna step sizes were swept for both the model and value-function updates.Source: §5 · p. 6

Continuous-state tasks

• Continuous Gridworld has a sparse goal reward and a wall with a small opening; River Swim requires exploration against a leftward current to reach a larger reward at the rightmost state.Both tasks use continuous states and coarse tile coding; River Swim uses optimistic weight initialization to encourage exploration.Source: §5 · p. 6

Results for Continuous States

• REM-Dyna performs best against ER variants and other model-based approaches; in River Swim, every REM-Dyna variant reaches 85% of optimal within 20,000 steps, while no ER variant does.REM-Dyna with predecessors is particularly effective in River Swim.Source: §5 · p. 6, Figure 2 · p. 6

Conclusion

• REMs use similarities to a representative set of prototypes and require only a small set of learned coefficients, with a learning rule based on conditional independence and conditional models.The approach is developed for Dyna control in continuous-state settings.Source: §6 · p. 6
• The paper identifies data efficiency, robustness to forgetting, conditional-model support, and sampling efficiency as criteria for models used in one-step sampled Dyna.The authors provide a coefficient-learning rule for REMs.Source: §6 · p. 6
• Across tabular and continuous microworlds, Dyna gains from predecessors and on-policy transitions, and REMs outperform Linear and neural-network models.The conclusion describes the study as an investigation of differences between Dyna and ER.Source: §6 · p. 6
• The study revisits how Dyna’s search-control queue and ER’s transition buffer add, remove, and prioritize samples.The investigated choices include recent samples, absolute TD-error priorities, predecessor generation, and on-policy transitions.Source: §6 · p. 6

Consistency result

• Theorem 1 states that the estimator is consistent for p(s′...), with similarity between sample and prototype state-action pairs defined by a kernel.The supplied theorem statement identifies the similarity as ρ(t, i).Source: A Consistency of conditional… · p. 8

Proof

• The proof’s limit argument requires all three limits to exist and the denominator’s limit to be nonzero.The stated condition is that the expected kernel similarity is not zero.Source: A Consistency of conditional… · p. 8
• The proof invokes kernel symmetry to relate the two conditional state-action probabilities and states that the coefficient converges to p(s′...).The fragments do not provide the full displayed estimator or distribution notation.Source: A Consistency of conditional… · p. 8

Algorithm fragments

• The supplied algorithm fragments describe REM-Dyna planning with a model and priority queue, including model-based transition sampling and Q-learning updates.The pseudocode also shows predecessor sampling and insertion into the queue using a TD-error priority.Source: A Consistency of conditional… · p. 8

REM-Dyna algorithm

• REM-Dyna’s online loop updates its model from observed transitions, then performs planning using samples from the model and search-control queue.The accompanying text points to separate pseudocode for sampling and updating REMs.Source: B REM Algorithmic Details · p. 8

Queue and buffer management

• The queue and buffer are circular arrays: new samples replace the oldest, while sampled items remain stored and have their priorities updated.An element is removed only when its position becomes the oldest as new points are added.Source: B REM Algorithmic Details · pp. 8–9

KDE and REM

• KDE uses every observed sample as a uniformly weighted center, whereas REM selects a representative subset and reweights its coefficients.In the illustrated comparison, both use RBF variance 0.15; KDE has 500 samples and REM selects 30.Source: Figure 3 · p. 9

B.1 Computing Conditional Covariances

• The model samples from its conditional distribution over next state, reward, and discount given a state and action.The text distinguishes this model distribution from the true conditional distribution.Source: §B.1 · p. 9
• The conditional covariance reflects variation in [s′, r, γ] for a given (s, a), unlike covariance across the whole state space.A global covariance would be significantly larger because it includes variation across state-action pairs.Source: §B.1 · p. 9
• In a deterministic domain, the conditional covariance is zero, while covariance across the state space is not.Source: §B.1 · p. 9

B.2 Details on Prototype Selection

• Prototype selection maximizes log det(K + I), swaps in sufficiently different prototypes, and uses a 0.01 utility threshold to avoid costly frequent swaps.The threshold is reported to have little impact on solution quality.Source: §B.2 · p. 9
• K-means groups points into blocks to speed log-determinant computation, with clustering rerun every 10 swaps from the previous clustering.The distance uses the empirical covariance of transitions (s, a, s′, r, γ).Source: §B.2 · pp. 9–10

B.3 Additional Pseudocode for REMs

• The predecessor sampler returns an empty set when p(at|st+1) is zero; otherwise it samples predecessors from p(st|st+1, at).Source: §B.3 · p. 10
• REM transition sampling selects a prototype according to its β weights, computes conditional covariance, then samples (s′, r, γ) from a Gaussian.Source: §B.3 · p. 10

• The Tabular Gridworld is a discounted episodic task with obstacles and one goal, rewarding +100 only on the transition into the goal.Its stochastic variant reaches the intended next state with probability 0.925 and each of three adjacent alternatives with probability 0.025.Source: C Domain Details · p. 10
• In the tabular variants, Dyna stores next state and reward in a table for deterministic transitions, and estimates observed-transition probabilities for stochastic ones.Source: C Domain Details · p. 10
• REM predecessor sampling first chooses a prototype using β probabilities, then samples a predecessor state from a Gaussian centered at that prototype.Source: C Domain Details · p. 10
• The Continuous Gridworld has a wall with a small opening, noisy movement, and a sparse reward at the goal in a two-dimensional state space.Moves succeed with probability 0.9; otherwise the environment executes a random move.Source: C Domain Details · p. 10
• River Swim is a continuing one-dimensional task where downstream drift opposes the high-reward upstream goal, and the always-left policy can trap agents in a suboptimal behavior.The optimal policy is always to take the right action.Source: C Domain Details · p. 10

• All domains use one tiling with 16 tiles.Source: D Parameter Settings · p. 10
• All algorithms use 10 planning steps, buffer or queue size 1000, Q-learning, and ε = 0.1, while memory is 2048 for Continuous Gridworld and 512 for River Swim.Step sizes are swept from 0.015625 to 1.0; River Swim weights start at 1 for optimism, while Gridworld weights start at zero.Source: D Parameter Settings · p. 11
• REM uses 1000 prototypes and Gaussian kernels, with the state-kernel bandwidth set to 0.0001 and the other bandwidth based on conditional covariance.Source: D Parameter Settings · p. 11
• The linear model predicts expected next features and reward, with a separate reverse model; neural networks use two hidden layers of 40 and 20 ReLU units for forward and predecessor prediction.The predecessor network also outputs action probabilities, and replay trains the networks with a buffer of 1000 and mini-batches of 32.Source: D Parameter Settings · p. 11