Source-linked AI summary
Neural Episodic Control
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomènech, Oriol Vinyals, Demis Hassabis, Daan Wierstra, Charles Blundell
TL;DR
Deep reinforcement learning can reach super-human performance but often requires far more data than humans. Neural Episodic Control uses a semi-tabular episodic memory with rapidly updated values, and learns faster than prior data-efficient agents across Atari games. Its advantage is strongest early in learning, while Prioritised Replay later achieves higher performance.
Problem
Deep reinforcement learning often requires orders of magnitude more environmental interactions than humans to reach comparable performance, partly because neural updates and reward propagation are slow.
Method
Neural Episodic Control uses semi-tabular memory that stores slowly changing state representations with rapidly updated value estimates and retrieves them through context-based lookups.
Results
An order of magnitude fewer environmental interactions than Prioritised Replay and Retrace(λ) is required by NEC in the reported experiments.
Takeaways & Limitations
NEC is a promising non-parametric addition to deep reinforcement learning when data efficiency is important, particularly early in learning.
Takeaways & Limitations
Prioritised Replay achieves higher performance later in learning, and NEC’s long-term final performance was not shown to be significantly superior to parametric agents.
Abstract
from arXiv · showhide
Deep reinforcement learning methods attain super-human performance in a wide range of environments. Such methods are grossly inefficient, often taking orders of magnitudes more data than humans to achieve reasonable performance. We propose Neural Episodic Control: a deep reinforcement learning agent that is able to rapidly assimilate new experiences and act upon them. Our agent uses a semi-tabular representation of the value function: a buffer of past experience containing slowly changing state representations and rapidly updated estimates of the value function. We show across a wide range of environments that our agent learns significantly faster than other state-of-the-art, general purpose deep reinforcement learning agents.
1. Introduction
Deep reinforcement learning can achieve strong performance but learns inefficiently because neural updates, sparse rewards, and slow value propagation limit rapid use of experience. Neural Episodic Control addresses these concerns with memory that rapidly incorporates successful strategies.
- Motivation: Deep reinforcement learning agents can surpass human performance but may require orders of magnitude more environmental interactions to reach comparable performance.In Atari, DQN requires more than 200 hours of gameplay to achieve scores comparable to a human after two hours.
- Motivation: Small learning rates slow experience integration because high rates can cause catastrophic interference in globally approximating neural networks.
- Motivation: Sparse rewards create an imbalance that makes neural networks underpredict larger rewards and complicates selection of the most rewarding actions.
- Motivation: Random minibatch training and slowly updated target networks slow the one-step-at-a-time propagation of reward information in DQN-style algorithms.
- Scope: The paper focuses on three concerns while recognizing exploration, hierarchical reinforcement learning, and transfer learning as complementary advances in data efficiency.
- Contribution: Neural Episodic Control uses a semi-tabular memory that binds slowly changing state representations to rapidly updated values for context-based action selection.Its values can update faster than the rest of the deep neural network, helping address slow stochastic-gradient-descent updates.
2. Deep Reinforcement Learning
Deep reinforcement learning represents action values with neural networks and trains them from replayed transitions using stabilized Q-learning targets. Extensions improve bias, replay, reward propagation, or memory, but use distinct learning paradigms.
- Value Functions: The action-value function Qπ(s, a) is the expected discounted return after taking action a in state s and then following policy π.The discount factor γ trades off short- versus long-term rewards.
- DQN: DQN uses Q-learning to rank actions from a neural-network value function and selects actions with an ϵ-greedy exploration policy.
- DQN: DQN trains a convolutional network on randomly sampled replay transitions against targets from an older target network.Replay and target networks are used for stable training.
- Extensions: Double DQN reduces target bias, Prioritised Replay changes replay selection, and Q∗(λ) and Retrace(λ) modify Q-learning backup or reward propagation.
- Alternative Methods: A3C learns a policy and value function with policy gradients and entirely on-policy learning, while its added LSTM memory did not significantly improve Atari performance.
3. Neural Episodic Control
Neural Episodic Control combines a shared convolutional embedding with action-specific differentiable neural dictionaries that store and update value estimates. It uses nearest-neighbour lookups, N-step Q-learning targets, replay training, and rapidly updated memory values to estimate action values.
- Architecture: NEC uses a convolutional network, one memory module per action, and a final network that converts memory read-outs into Q(s, a) values.The convolutional architecture is shared across the action-specific memories.
- Differentiable Neural Dictionary: Each action-specific DND stores dynamically sized arrays of keys and values, associating state representations with action-value estimates.The DND supports lookup and write operations and behaves like an append-only key-value memory, updating an existing value when its key is already present.
- Differentiable Neural Dictionary: A lookup maps key h to a weighted sum of memory values, with weights determined by normalized kernels between h and stored keys.For scalability, NEC limits lookups to the top p nearest neighbours, typically p = 50, and uses approximate nearest-neighbour search.
- Agent Architecture: The agent estimates Q(s, a) by querying the DND for each action and selects the action with the highest estimate, using an ϵ-greedy policy during training.The pixel state is first transformed into a key by the shared convolutional network.
- Adding (s, a) pairs to memory: NEC writes N-step Q-learning estimates into the memory after each interaction, combining N on-policy rewards with an off-policy bootstrap for the remaining trajectory.The bootstrap value is obtained by querying all action memories and taking the highest estimated Q-value; values become available N steps after the state-action pair occurs.
- Learning: Existing memory values are updated with a tabular Q-learning rule, while new state-action keys are appended; a high α enables rapid updates for repeatedly visited states.A replay buffer stores training tuples whose N-step estimates play the role of DQN’s target network, and gradient descent updates the embedding network and memory parameters.
4. Experiments
NEC was evaluated on Atari games against DQN-, A3C-, λ-return, Prioritised Replay, and MFEC-based baselines, using learning curves and human-normalised scores. It learned faster in the early training regime and outperformed MFEC on average, with advantages on several games where reward clipping matters.
- Experimental setup: Experiments used 57 Atari games spanning sparse rewards and widely different score magnitudes, comparing NEC with DQN-, A3C-, λ-return, Prioritised Replay, and MFEC baselines.Learning curves averaged performance over five random seeds; NEC and MFEC were evaluated every 200,000 frames, while other algorithms were evaluated every million steps.
- Data efficiency: NEC clearly outperformed all other algorithms below 20 million frames, with the largest difference before 5 million frames.Only at 40 million frames did DQN with Prioritised Replay outperform NEC on average, corresponding to 185 hours of gameplay.
- Learning performance: Across most games, NEC learned significantly faster initially and was comparable only to MFEC, which also uses an episodic-like Q-function.The comparison concerns initial learning speed rather than maximally achieved score.
- Comparison with MFEC: NEC outperformed MFEC on average because its reward signal learns an embedding for value interpolation, especially when a few pixels determine action values.MFEC instead used pixel-space random projections or a reward-independent variational-autoencoder representation that could retain irrelevant details.
- Reward handling: NEC and MFEC avoided reward clipping, producing qualitative behavioral changes and better performance than clipping-based algorithms on Bowling, Frostbite, H.E.R.O., Ms. Pac-Man, and Alien.On Pong and Boxing, where rewards already lie in [−1, 1], NEC did not achieve a higher maximum score but was vastly more data efficient.
5. Related work
Prior work includes recurrent, differentiable, and memory-network approaches, but these generally learn memory through slow training or reset contents between episodes. NEC instead addresses persistent experience memory for data-efficient reinforcement learning.
- Recurrent memories such as LSTMs and DNCs remain subject to slow learning because they are trained with truncated backpropagation through time.
- Many reinforcement-learning memory implementations reset their contents at each episode, functioning as working memory for partial observability rather than persistent experience storage.
- RNNs may learn to write rewarding states or reinforcement-learning algorithms into memory, but learning time can scale strongly with task complexity.
- Differentiable key-value memory layers and memory-network adaptations had been explored, but the cited key-value layer was evaluated on supervised tasks rather than reinforcement learning.
6. Discussion
NEC combines a per-action differentiable memory with rapidly updated value estimates, N-step Q estimates, and stable neural state representations. It learns faster in the early data regime, although Prioritised Replay later achieves higher performance.
- NEC uses one Differentiable Neural Dictionary per potential action to store recent state representations with corresponding value functions.
- An order of magnitude fewer interactions are required by NEC than by Prioritised Replay and Retrace(λ) in the reported experiments.
- NEC’s faster learning is associated with its DND memory architecture, N-step Q estimates, and convolutional-neural-network state representation.
- The DND rapidly integrates state representations and value estimates, preserves memories across episodes, and uses kd-trees for efficient approximate nearest-neighbour access.
- NEC outperforms other agents early in learning, but Prioritised Replay has higher performance later and remains a target for future improvement.
A. Scores on Atari Games
The table reports game scores measured at 10 million frames. Its title identifies the evaluation budget but does not specify further row or column encodings.
- Scores are reported at 10 Million Frames.
- The table is presented as a score summary rather than a learning-curve figure.
- The caption specifies the evaluation time point but provides no additional table layout information.