Episodic Reinforcement Learning with Associative Memory

Guangxiang Zhu, Zichuan Lin, Guangwen Yang, Chongjie ZhangICLR 2020 · OpenReview

TL;DR

ERLAM (Episodic Reinforcement Learning with Associative Memory) boosts the sample efficiency of deep reinforcement learning by organizing past experiences into a graph rather than a simple list. By propagating rewards across connected trajectories in this "associative memory," the agent can rapidly discover effective strategies that combine pieces of different past attempts, significantly outperforming state-of-the-art models on Atari games with far less data.

What Problem Does This Paper Address?

Deep Reinforcement Learning (RL) is notoriously "data-hungry." While humans can often learn a task in a few tries, algorithms like DQN require millions of interactions. This is because gradient-based updates are slow and incremental.

"Episodic RL" was introduced to solve this by creating a "cheat sheet" (non-parametric memory) of past successful states and actions. However, previous methods treated every experience as an isolated item. If an agent reached a goal via Path A, and in a separate attempt reached the middle of Path A via Path B, it wouldn't realize it could connect Path B to the goal.

Conceptual difference between isolated episodic memory and associative memory.

This lack of association means agents miss out on "counterfactual" reasoning—the ability to piece together a winning strategy from fragments of different experiences.

Methods

The authors introduce ERLAM, which adds a layer of relational reasoning to episodic memory by structuring it as a network of connected experiences.

ERLAM architecture showing dual-system learning with a value network and associative memory graph.
  1. Memory as a Graph: Instead of a flat table, ERLAM builds a directed graph where nodes are state embeddings (created via random projection) and edges represent transitions.
  2. Reverse-Trajectory Propagation: When a reward is found, ERLAM doesn't just update the current path. It uses a "reverse-trajectory" strategy to propagate that value through the graph. If two different trajectories cross at a "join point," the high value from one path can flow into the other.
  3. Dual-System Learning: The framework uses this fast-updating associative memory to guide a standard, slow-learning parametric model (like a DQN). The DQN's loss function is regularized to stay close to the high-value estimates found in the associative memory.
  4. Efficiency: To keep lookups fast, they use a kd-tree for state retrieval and a strategy to discard the least recently used items when memory is full.

Key Insights and Ideas

  • The Power of Join Points: The core "aha" moment is that states appearing in multiple trajectories act as bridges. By connecting these, the agent effectively performs "automatic augmentation of counterfactual trajectories." It learns from paths it never actually took in their entirety.
  • Rapid Value Propagation: Because the graph allows values to jump between episodes, the agent can "latch on" to successful policies much faster than waiting for standard Bellman updates to trickle back through a neural network.
  • Memory as Guidance: ERLAM doesn't replace the neural network; it acts as a high-speed scout. The non-parametric memory provides an early lower bound on the Q-value, preventing the neural network from wandering aimlessly during the early stages of training.

Datasets and Key Results

The researchers evaluated ERLAM on two main benchmarks: Monster Kong (a custom navigation environment based on the Pygame Learning Environment) and the Atari 2600 (ALE) suite of 25 diverse games.

  • Superior Sample Efficiency: In the Monster Kong navigation task, ERLAM achieved higher scores with only 10 million samples than the previous state-of-the-art (EMDQN) did with 80 million samples.
  • Atari Performance: When limited to 10 million frames, ERLAM outperformed EMDQN (which was given 40 million frames) on 17 out of 25 games.
  • Human-Normalized Scores: ERLAM achieved a mean human-normalized score of 515.4%, compared to 250.6% for EMDQN and 83.6% for standard DQN. In games like Defender and Atlantis, the performance gains were massive, reaching thousands of percentage points higher than DQN.

Limitations and Future Work

While highly effective, ERLAM has a few limitations that pave the way for future research:

  • Stochasticity: ERLAM currently uses the maximum Q-value in its memory. In highly random (stochastic) environments, this can lead to overestimation. Future versions could store a distribution of values instead.
  • Simple Embeddings: The current model uses "naive" random projections for state embeddings. While this works, it doesn't capture high-level semantic features (like identifying specific objects). Integrating advanced representation learning could further boost performance.
  • State Overlap Requirement: The associative power of ERLAM relies on "join points"—revisiting the exact same or very similar states. In games with massive, non-repeating state spaces, the graph might remain too fragmented to be useful.

Summary updated

BibTeX
@inproceedings{zhu2020episodic,
  author = {Guangxiang Zhu and Zichuan Lin and Guangwen Yang and Chongjie Zhang},
  title = {{Episodic Reinforcement Learning with Associative Memory}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=GhwRfCDsoq},
}
Figure