Source-linked AI summary
Model-Free Episodic Control
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, Demis Hassabis
TL;DR
The paper addresses how reinforcement-learning agents can learn rewarding strategies rapidly despite the data inefficiency of deep RL. It proposes model-free episodic control, which memorizes and replays high-return experiences while generalizing to novel states through nearest neighbours. The method learns good policies faster than parametric function approximators and can remain effective even when exact states are rarely repeated, though it may be overtaken later in training.
Problem
Deep RL systems require many interactions to reach human-level performance, motivating a machine analogue of humans' rapid exploitation of rewarding experiences without domain-specific prior knowledge.
Method
Model-free episodic control non-parametrically records the highest returns for state-action pairs, replays episodes backward, and estimates values for novel states using nearest neighbours.
Results
The episodic controller learned good policies faster than parametric function approximators and performed well even in 3D environments where exact states were essentially never revisited.
Takeaways & Limitations
The results support episodic control as a fast-learning model-free mechanism, particularly during early learning in a new environment.
Takeaways & Limitations
Because QEC values cannot decrease, the update is not suited to rational action selection in stochastic environments.
Abstract
from arXiv · showhide
State of the art deep reinforcement learning algorithms take many millions of interactions to attain human-level performance. Humans, on the other hand, can very quickly exploit highly rewarding nuances of an environment upon first discovery. In the brain, such rapid learning is thought to depend on the hippocampus and its capacity for episodic memory. Here we investigate whether a simple model of hippocampal episodic control can learn to solve difficult sequential decision-making tasks. We demonstrate that it not only attains a highly rewarding strategy significantly faster than state-of-the-art deep reinforcement learning algorithms, but also achieves a higher overall reward on some of the more challenging domains.
1 Introduction
The paper asks how machines can learn rewarding strategies rapidly, without domain-specific prior knowledge, by drawing on hippocampal episodic-memory ideas. It proposes episodic control as a fast, instance-based complement to slower generalization and tests whether it remains useful when exact states are rarely repeated.
- Deep RL systems can require tens of millions of interactions to reach human-level Atari performance, whereas humans learn much faster.
- Slow gradient-based updates make deep RL systems inefficient at assimilating rewarding action sequences into improved policies.
- Episodic control records highly rewarding experiences and rapidly replays action sequences that previously produced high returns.
- Hippocampal learning is described as instance-based, with states co-represented alongside action returns for rapid retrieval and replay.The proposed mechanism includes pattern completion and reverse-ordered replay after rewarding events.
- Model-free episodic control is motivated as a quick-to-learn approximation while slower, more generalizable decision systems acquire repeated experience.
- 10-60% of Atari states were re-encountered exactly, yet the episodic model also performed well in 3D environments where states were essentially never revisited.
2 The episodic controller
Model-free episodic control stores the highest returns observed for state-action pairs and selects actions that replay successful sequences. It uses episode-level backward replay and nearest-neighbour estimates to handle novel states, but its optimistic update is unsuitable for stochastic settings.
- The controller is a non-parametric table QEC(s, a), whose entries store the highest return observed after taking action a from state s.
- The policy selects the action with the highest QEC value, aiming to replay successful sequences and recreate past successes.
- The QEC update stores nondecreasing values, so it is not a general-purpose learning rule for rational action selection in stochastic environments.
- For novel states, QEC estimates action values by averaging values from the k nearest previously visited states.
- Each episode first executes the QEC policy and records experience, then updates QEC through backward replay of rewards, actions, and states.
- The implementation uses separate k-nearest-neighbour buffers for each action and removes the least recently updated entry when capacity is reached.
- Highest-return estimates favor exploitation over exploration and work best when environmental noise is relatively low.
3 Representations
Because exact observations are costly and novel states require generalization, the controller maps observations into a lower-dimensional representation space. Different embeddings impose different inductive biases on nearest-neighbour value estimation.
- The feature mapping φ determines how episodic control generalizes when it encounters novel states.
- Using raw observations would be impractical because each frame requires about 28 KBytes and the experiments would exceed 300 gigabytes of memory.
- Random projection maps x to Ax in a lower-dimensional space, with the Johnson-Lindenstrauss lemma approximately preserving relative distances.
- Abstract feature extraction can help when visually similar observations have dissimilar action values because illumination, textures, or scrolling backgrounds are irrelevant.
4 Experimental results
Across Atari and Labyrinth, episodic control learned rewarding strategies rapidly, outperforming parametric controllers early and exploiting sparse or repeated experiences. Its later performance depended on environment structure and representation, with parametric generalization sometimes catching up.
- Atari: The episodic controller outperformed DQN, prioritized-replay DQN, and A3C during the initial learning phase across all five Atari games.Atari experiments used random-projection and VAE embeddings, with performance compared against the listed parametric baselines.
- Atari: After fast initial learning, parametric controllers overtook episodic control on Q*bert and River Raid by using non-local generalization in later game stages.The episodic controller became limited as episodes lengthened and yielded less new experience per episode.
- Atari: Random-projection and VAE embeddings produced similar episodic-control performance overall, although VAE features performed noticeably worse on Frostbite.The paper attributes this possible weakness to a random policy producing a poor VAE training set.
- Atari: Atari’s deterministic structure produced exact state-action matches in buffers ranging from 10% in Frostbite and River Raid to 60% in Q*bert.The reported percentages were 50% for Ms. PAC-MAN and 45% for Space Invaders.
- Labyrinth: In Labyrinth, episodic control found apple-seeking behavior quickly, matched A3C’s Forage-and-Avoid performance in fewer than 3 million frames versus over 40 million steps, and learned Double-T-Maze from few rewarding episodes.A3C eventually surpassed episodic control on Forage and never achieved expected reward above zero on Double-T-Maze.
- Nearest-neighbour analysis: Increasing the nearest-neighbour count significantly affected final Labyrinth performance, suggesting that VAE features provided generalization there.The nearest-neighbour analysis compared VAE features across Labyrinth and Atari tasks.
5 Discussion
The work presents model-free episodic control as a fast-learning system based on non-parametric memorisation, while positioning it within a broader framework of multiple control strategies selected according to available time and working memory. It may learn good policies faster than parametric function approximators but can be overtaken later in training.
- Model-free episodic control addresses current reinforcement learning systems’ inability to learn in a one-shot fashion through non-parametric memorisation of experience.
- The approach can learn good policies faster than parametric function approximators, although those approximators may overtake it at later training stages.
- The authors conjecture that model-free and model-based episodic strategies may complement habitual and goal-directed systems in the brain.
- Available decision-making time and working-memory resources are proposed as key determinants of which control system should guide behavior.
A Variational autoencoders for representation learning
The paper uses variational autoencoders to learn latent representations of observations through an encoder–decoder communication model. The experiments specify a 32-dimensional latent space and train the models on one million observations collected under random policies.
- A variational autoencoder uses an encoder to map observations into messages and a decoder to approximately reconstruct observations from those messages.The model minimizes the cost of transmitting observations through a communication channel.
- The encoder produces q(z|x), the channel uses a prior p(z), and the decoder models observations with p(x|z).Training minimizes the cost of recovering the original observation from a sampled latent message.
- 32-dimensional latent representations encode 84 by 84 grayscale observations represented in R7056.The observation values range from 0 to 1, and the specified distributions use diagonal-covariance Gaussians.
- 1,000,000 observations from random policies were used to train each environment’s VAE.Training used 400,000 stochastic-gradient-descent steps with RMSProp and minibatches of 100.
- Figure 4 depicts the variational autoencoder architecture used for representation learning.