Replay Memory as An Empirical MDP: Combining Conservative Estimation with Experience Replay

Hongming Zhang, Chenjun Xiao, Han Wang, Jun Jin, bo xu, Martin MüllerICLR 2023 · OpenReview

TL;DR

Deep Reinforcement Learning (DRL) often struggles with sample efficiency, requiring millions of interactions to learn simple tasks. This paper introduces CEER (Conservative Estimation with Experience Replay), a method that treats the agent's replay memory not just as a bucket of transitions, but as a structured "empirical MDP" that can be solved using classic dynamic programming. By using this solved "mini-world" to regularize the neural network, the authors significantly boost learning speed and prevent the agent from taking "suicidal" actions in sparse-reward environments.

What Problem Does This Paper Address?

In standard DRL, agents store their experiences (state, action, reward, next state) in a replay memory. Most algorithms, like DQN, treat this memory as a simple database, sampling random transitions to update a neural network. However, this approach ignores the global structure of the transitions—how they link together to form paths and cycles.

Furthermore, neural networks are notorious for "overestimation bias," where they confidently predict high rewards for actions they haven't actually mastered. This leads to poor sample efficiency, especially in environments with sparse or delayed rewards (like a puzzle where you only get a point at the very end). The authors ask: Can we extract more "truth" from the data we’ve already collected to anchor the neural network’s wilder guesses?

Methods

The authors propose a framework called RM-MDP (Replay Memory Markov Decision Process).

Overview of the RM-MDP framework

Here is the breakdown of their approach:

  1. Graph Construction: They represent the replay memory as a directed graph. Each unique state (identified via hashing or embeddings) is a node, and each transition is an edge. Unlike the neural network, this is a tabular representation.
  2. Solving the RM-MDP: Because this graph is a discrete MDP, they can use classic Value Iteration (dynamic programming) to find the optimal values within this "empirical" world. This estimate is "conservative" because it only considers actions the agent has actually tried.
  3. CEER (The Regularizer): They integrate this tabular knowledge into the deep learning process using two regularizers:
  4. Value Regularizer: The target value for the neural network becomes a weighted average of its own estimate and the "ground truth" from the RM-MDP.
  5. Policy Regularizer: They use Kullback–Leibler (KL) divergence to ensure the neural network’s policy doesn't stray too far from the successful paths found in the RM-MDP.

Datasets

The researchers evaluated CEER on three challenging suites designed to test logic and navigation:

  • Sokoban: A classic warehouse-keeper puzzle requiring long-term planning.
  • MiniGrid: Grid-world environments with sparse rewards (e.g., finding a key to open a door).
  • MinAtar: A simplified, "miniature" version of Atari games like Breakout and Seaquest, designed for faster experimentation.

Key Insights and Ideas

  • The "Anchor" Effect: The RM-MDP acts as a reliable anchor. While the neural network might generalize poorly to unseen states, the RM-MDP provides a rock-solid estimate of what has actually worked in the past.
  • Memory Density: The authors introduce a new metric called "memory density"—the average number of actions explored per state in the memory.
Correlation between Memory Density and Performance

They found a very strong correlation between high memory density and the performance boost provided by CEER.

  • Avoiding "Suicide": Even when memory density is low, the RM-MDP is excellent at identifying "suicidal" actions (transitions that lead to immediate failure). By regularizing against these, the agent survives longer and collects better data.
  • Efficiency vs. Planning: CEER provides many of the benefits of Model-Based RL (which plans into the future) but at a fraction of the computational cost, as it solves a graph of existing data rather than simulating imaginary futures.

Key Results

  • Massive Sample Efficiency: In hard Sokoban tasks (like Push-7x7-2), CEER achieved high scores while baseline methods like DQN and PER (Prioritized Experience Replay) failed completely.
  • Breakout Performance: On the MinAtar Breakout task, CEER’s final score was double that of other state-of-the-art algorithms.
  • Wall-Clock Speed: Despite the extra step of solving the RM-MDP, CEER remains fast. It runs at ~308 Frames Per Second (FPS), only slightly slower than standard DQN (~402 FPS) and significantly faster than complex model-based methods like DreamerV2 (~19 FPS).

Limitations and Future Work

  • State Abstraction: The method relies on being able to identify "the same state." In the game Freeway, CEER struggled because the state representation didn't include the speed of cars. The graph merged different states into one, leading to "wrong" estimations. Future work could involve better state abstraction to handle such nuances.
  • Continuous Action Spaces: Currently, the RM-MDP construction is designed for discrete actions. Extending this to continuous control (like robotics) would require discretization or clustering techniques.
  • Exploration Trade-off: Being "conservative" can sometimes discourage exploration. The authors suggest that balancing the "aggressive" neural network with the "conservative" RM-MDP is a promising area for future tuning.

Summary updated

Abstract

Experience replay, which stores transitions in a replay memory for repeated use, plays an important role of improving sample efficiency in reinforcement learning. Existing techniques such as reweighted sampling, episodic learning and reverse sweep update further process the information in the replay memory to make experience replay more efficient. In this work, we further exploit the information in the replay memory by treating it as an empirical \emph{Replay Memory MDP (RM-MDP)}. By solving it with dynamic programming, we learn a conservative value estimate that \emph{only} considers transitions observed in the replay memory. Both value and policy regularizers based on this conservative estimate are developed and integrated with model-free learning algorithms. We design the metric \textit{memory density} to measure the quality of RM-MDP. Our empirical studies quantitatively find a strong correlation between performance improvement and memory density. Our method combines \emph{Conservative Estimation with Experience Replay (CEER)}, improving sample efficiency by a large margin, especially when the memory density is high. Even when the memory density is low, such a conservative estimate can still help to avoid suicidal actions and thereby improve performance.
BibTeX
@inproceedings{zhang2023replay,
  author = {Hongming Zhang and Chenjun Xiao and Han Wang and Jun Jin and bo xu and Martin Müller},
  title = {{Replay Memory as An Empirical MDP: Combining Conservative Estimation with Experience Replay}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=SjzFVSJUt8S},
}
Figure