Deep Exploration via Bootstrapped DQN

Ian Osband; Charles Blundell; Alexander Pritzel; Benjamin Van Roy

Source-linked AI summary

Deep Exploration via Bootstrapped DQN

Ian Osband, Charles Blundell, Alexander Pritzel, Benjamin Van Roy

arXiv:1602.04621v3Feb 15, 2016cs.LGcs.AIeess.SYstat.ML

TL;DR

Reinforcement learning needs efficient exploration in complex environments, where existing deep-exploration methods can be impractical or computationally intractable. The paper introduces bootstrapped DQN, which samples randomized value functions and commits to one policy per episode. It substantially reduces learning times and improves performance across most Atari games, while remaining computationally efficient and parallelizable.

Problem
Efficient exploration in complex reinforcement-learning environments remains difficult because practical methods often use statistically inefficient exploration, while many provably efficient methods do not scale.
Method
Bootstrapped DQN samples one randomized Q-value function from an approximate posterior at each episode start and follows its policy for the episode.
Results
Bootstrapped DQN substantially reduces learning times and improves performance across most Atari games, reaching human performance on average 30% faster than DQN across all games.
Takeaways & Limitations
Temporally extended exploration can improve learning efficiency in large-scale Atari environments, while cumulative rewards through learning improve over DQN.
Takeaways & Limitations
Random initialization is effective in the experimental setting but will not work in all situations, where a more rigorous prior may be necessary.

Abstract

from arXiv · show

Efficient exploration in complex environments remains a major challenge for reinforcement learning. We propose bootstrapped DQN, a simple algorithm that explores in a computationally and statistically efficient manner through use of randomized value functions. Unlike dithering strategies such as epsilon-greedy exploration, bootstrapped DQN carries out temporally-extended (or deep) exploration; this can lead to exponentially faster learning. We demonstrate these benefits in complex stochastic MDPs and in the large-scale Arcade Learning Environment. Bootstrapped DQN substantially improves learning times and performance across most Atari games.

1 Introduction

The paper targets reinforcement learning environments where efficient exploration requires balancing immediate rewards against information gained from temporally extended action sequences. It proposes bootstrapped DQN to bring uncertainty-aware, deep exploration to complex environments using nonlinear neural networks.

1 Introduction: RL agents must explore uncertain states and actions while maximizing cumulative rewards, creating an exploration–exploitation trade-off.Temporally extended exploration matters because failing to reason over informative observation sequences can worsen learning times exponentially.
1 Introduction: Existing provably efficient deep-exploration methods mainly target small finite MDPs or computationally intractable planning problems.Consequently, complex environments have often relied on statistically inefficient exploration or no exploration.
1 Introduction: Bootstrapped DQN extends randomized-value-function exploration from linear models to complex nonlinear generalization with deep neural networks.Random initialization provides low-cost uncertainty estimates that the algorithm uses for deep exploration.
1 Introduction: Bootstrapped DQN substantially reduces learning times and improves performance across most Atari games while running roughly 20% slower than DQN on one machine.The implementation is computationally efficient and parallelizable.

2 Uncertainty for neural networks

The paper seeks computationally efficient uncertainty estimates for neural-network value functions. It uses bootstrap resampling and randomized initialization to obtain posterior-like uncertainty estimates from ensembles of neural networks.

2 Uncertainty for neural networks: Efficient exploration with deep neural networks requires quantifying uncertainty in value estimates so agents can assess exploratory actions.The paper motivates uncertainty quantification as a prerequisite for judging potential learning benefits.
2 Uncertainty for neural networks: The bootstrap approximates a population distribution by repeatedly applying an estimator to datasets sampled with replacement.A bootstrap sample has the same cardinality as the original dataset.
2 Uncertainty for neural networks: Bootstrapped neural networks can produce reasonable posterior estimates for noisy regression data.The figure trains 50 two-layer networks on 50 bootstrapped samples, using 50 ReLU units per layer and random parameter initialization.
2 Uncertainty for neural networks: Random initialization induces diversity among the neural networks, supporting uncertainty estimation at low computational cost.The paper reports that dropout did not produce effective uncertainty estimates for this regression problem.

3 Bootstrapped DQN

Bootstrapped DQN represents uncertainty with multiple bootstrapped Q-value functions and samples one function per episode. The selected function determines a temporally consistent policy, enabling deep exploration while retaining DQN’s scalable neural-network representation.

3 Bootstrapped DQN: DQN scales Q-value learning to large problems by estimating Q(s, a; θ) with a neural network rather than a tabular representation.The optimal value is defined as the maximum policy value for each state–action pair.
3 Bootstrapped DQN: DQN stability modifications include replay-buffer sampling, periodically updated target networks, and Double DQN targets.The target network remains fixed between updates and is periodically copied from the learning network.
3 Bootstrapped DQN: Bootstrapped DQN approximates a distribution over Q-values by sampling one Q-value function from an approximate posterior at each episode start.The agent follows the policy optimal for that sample throughout the episode, producing temporally extended exploration.
3 Bootstrapped DQN: The algorithm builds K bootstrapped estimates and selects a head uniformly at random for each episode.This provides an efficient implementation of the approximate posterior sampling strategy.
3 Bootstrapped DQN: Each value-function head has its own target network and data-visibility flags, preserving temporally extended and consistent uncertainty estimates.The heads are trained with TD estimates while flags track which bootstrap heads observe each transition.

4 Related work

Related work frames deep exploration as requiring posterior or uncertainty-aware value functions, while existing efficient approaches face computational or representation limits. Bootstrapped DQN extends randomized value functions to flexible nonlinear representations at low computational cost.

4 Related work: Exact Bayesian exploration in belief-state MDPs is generally intractable, and many practical RL systems use inefficient exploration or none.This motivates scalable approximations for complex environments.
4 Related work: Optimism-in-the-face-of-uncertainty methods add exploration bonuses but are computationally intractable in complex domains except in particular deterministic settings.Related DQN-based work seeks effective bonuses without solving the full problem exactly.
4 Related work: Thompson sampling explores by sampling a posterior value function, but resampling every timestep can be inefficient and deep exploration requires commitment across several steps.PSRL makes this commitment but still requires solving a known MDP, often intractable for large systems.
4 Related work: Bootstrapped DQN extends randomized posterior value functions beyond linearly parameterized methods to flexible nonlinear representations.The method is presented as simple, general, compatible with deep-RL advances, and low-cost with few tuning parameters.

5 Deep Exploration

Deep exploration requires directing exploration across multiple time steps so the agent can plan to reach informative or rewarding states. The section evaluates this requirement in scalable chain environments and finds that bootstrapped DQN scales gracefully where shallow exploration does not.

Deep Exploration: Deep exploration directs exploration over multiple time steps, enabling an RL agent to plan toward future rewards or information.This contrasts with bandit-style dithering, which does not maintain a temporally consistent exploratory strategy.
Testing for deep exploration: The didactic environments use chains of length N > 3, with episodes lasting N + 9 steps before resetting to state s2.They represent a trade-off between a known mildly successful strategy and an unknown potentially more rewarding approach.
Testing for deep exploration: The experiments use raw pixel features and report results for φtherm, which generalized slightly better across DQN variants than φ1hot.Thompson DQN resamples every timestep, while Ensemble DQN uses an ensemble policy with the same architecture as bootstrapped DQN.
Testing for deep exploration: Only bootstrapped DQN demonstrates graceful scaling to long chains requiring deep exploration, against a conservative lower bound for shallow strategies.Learning is defined as completing one hundred optimal-reward episodes; each chain length uses 2000 episodes across three seeds.
How does bootstrapped DQN drive deep exploration?: Bootstrapped DQN approximates posterior value samples with a bootstrapped neural network, avoiding the additional planning steps required by PSRL.Its random initialization induces diversity, which was effective in this setting but may require a more rigorous prior in other situations.

6 Arcade Learning Environment

Across 49 Atari games, bootstrapped DQN improves exploration and learning speed relative to DQN, while retaining comparable peak performance and exposing limits on difficult games.

Efficient exploration in Atari: Bootstrapped DQN reaches human performance on average 30% faster than DQN across all Atari games.It reaches peak performance roughly similar to DQN while producing significantly improved cumulative rewards through learning.
Implementing bootstrapped DQN at scale: The algorithm uses ten bootstrap heads, with more heads generally producing faster learning but even a small number capturing most benefits.Gradient normalization by 1/K improves final scores but slows early learning, while performance was similar across bootstrap probabilities p and all settings outperformed DQN.
Efficient exploration in Atari: For the same amount of game experience, bootstrapped DQN generally outperforms DQN with ϵ-greedy exploration across diverse Atari games.The comparison is illustrated for a diverse selection of games.
Efficient exploration in Atari: Bootstrapped DQN typically reaches human performance significantly faster than DQN.It reaches human performance on Beam Rider and Battle Zone where DQN does not, but not on Amidar where DQN does.
Efficient exploration in Atari: On challenging games, bootstrapped DQN can improve exploration without solving the problem because network instability, reward clipping, and temporally extended rewards remain important.In Frostbite performance crashes after faster progress, while in Montezuma’s Revenge the agent reaches the first key after 20m frames but fails to learn from it.
Overall performance: Bootstrapped DQN improves cumulative rewards through learning by orders of magnitude relative to DQN.Across 14 games, AUC-20 is 0.62 for bootstrapped DQN, compared with 0.29 for base DQN and 0.37 for the best compared method.
Visualizing bootstrapped DQN: Distinct high-scoring policies across bootstrap heads provide diverse experiences that the authors believe support better generalization.ϵ-greedy policies are described as nearly indistinguishable for small ϵ and ineffectual for larger ϵ.
Visualizing bootstrapped DQN: An ensemble policy can outperform individual policies and use vote distributions to represent uncertainty about the optimal policy.The heads tend to agree at crucial decision points while remaining diverse at less important steps.

7 Closing remarks

The paper presents bootstrapped DQN as a computationally tractable and scalable approach to efficient reinforcement learning in complex environments, while motivating randomized value functions as an alternative to dithering.

Closing remarks: Bootstrapped DQN uses bootstrap-based uncertainty estimates to support efficient reinforcement learning in complex environments.The approach is presented as computationally tractable and naturally scalable to massive parallel systems.

A Uncertainty for neural networks

The appendix examines bootstrap and dropout uncertainty estimates for nonlinear neural networks. It argues that bootstrap estimates are more useful for the paper’s settings because they can reflect different subsets of noisy data and remain temporally consistent in Q-learning.

Experimental setup: The experiment generates twenty noisy regression pairs to qualitatively evaluate uncertainty methods for deep neural networks.The data use a highly nonlinear, noisy generating function with regions where uncertainty should be evident.
Dropout uncertainty: Dropout confidence intervals are unsatisfactory because they extrapolate the mean far beyond observed data, produce spiky samples, and collapse uncertainty in data-rich regions.The authors attribute these effects to dropout perturbing locally around a single neural-network fit.
Bootstrap uncertainty: Bootstrap neural networks can produce more intuitive uncertainty estimates because different data subsets yield different posterior samples for noisy observations.Dropout samples remain concentrated around the mean of highly noisy data trained with an MSE criterion.
Broader perspective: The paper treats deep exploration via randomized value functions as compatible with approximate posterior estimators beyond bootstrap.It presents uncertainty estimation for neural networks as an important research area in its own right.
Q-value uncertainty: Bootstrapped Q-value estimates additionally train each head against its own temporally consistent target network.This allows the estimates to bootstrap on their own estimates of long-run value, unlike the described dropout setup.

B Bootstrapped DQN implementation

Bootstrapped DQN uses multiple value-function heads trained with bootstrap masks, then follows one sampled head for an entire episode to support deep exploration. It remains effective with small K and even complete data sharing, while alternative policies fail to implement deep exploration.

Implementation: Bootstrapped DQN represents K Q-value functions using either separate networks or K heads in one network.The parameterization changes, but Q_k denotes the kth network or head.
Implementation: The bootstrap mask m_t determines which value functions train on each experience tuple, thereby modulating their gradients.A binary mask can include or exclude each head from training on the transition.
Implementation: Masking distributions range from independent Bernoulli masks to all-ones masks, with the latter reducing the algorithm to an ensemble method.Poisson masks provide a parallel to the standard non-parametric bootstrap.
Implementation: At each episode, Bootstrapped DQN samples one value function and follows its greedy policy throughout that episode.Algorithm 1 samples k uniformly and selects actions maximizing Q_k(s_t,a).
Exploration behavior: Small K can still support deep exploration, although larger K is more robust and scalable; complete sharing with p = 1 also remains effective.The complete-sharing configuration is reported as efficient for training large and deep neural networks.
Exploration behavior: Only bootstrapped DQN demonstrates efficient and deep exploration among the compared policies, whereas epsilon-greedy, majority-vote ensembles, and per-timestep Thompson sampling do not.The alternatives use the same network architecture but differ in action selection or head-sampling frequency.

C.2 A difficult stochastic MDP

In a difficult stochastic MDP and Atari experiments, Bootstrapped DQN is evaluated against exploration baselines and with alternative representations and training choices. It achieves performance comparable to efficient exploration schemes in the stochastic setting and improves cumulative Atari rewards, while robustness depends on representation and normalization.

A difficult stochastic MDP: Bootstrapped DQN is presented as unique among scalable deep-RL approaches for efficient exploration in stochastic domains.The comparison includes epsilon-greedy, UCRL2 optimism, and PSRL posterior sampling.
A difficult stochastic MDP: Bootstrapped DQN achieves performance similar to efficient exploration schemes such as PSRL without prior tabular-MDP knowledge in noisy environments.Empirical regret is averaged over 10 seeds during the first 2,000 episodes.
A difficult stochastic MDP: UCRL2’s empirical regret appears linear, but its regret scales similarly to its established bounds.The paper contrasts this behavior with Bootstrapped DQN in Figure 15.
Representation: With one-hot features, Bootstrapped DQN learns the optimal policy for most seeds but is less robust than with thermometer encoding.Two of ten seeds fail to learn the optimal policy within 2,000 episodes.
Experimental setup: The Atari experiments use 49 games, four emulator steps per agent action, clipped rewards, and raw-score evaluation.The convolutional architecture follows the cited DQN setup, with four grayscale 84x84 observations as input.
Atari results: On Atari, Bootstrapped DQN significantly improves cumulative rewards over DQN, although peak performance is much more similar.Cumulative rewards are emphasized as a better measure when an agent learns through real interactions.
Gradient normalization: Without gradient normalization, learning is typically faster but more prone to premature and suboptimal convergence.Normalization was helpful for surpassing benchmark best policies, though its benefit is less clear in all settings.
Data sharing: The discussion notes that data sharing is especially plausible in deterministic Atari because transition observations are uniquely correct.The authors state that more research is needed on where and when sharing matters.

D.4 Results tables

The results tables compare bootstrapped DQN variants with DQN and Dynamic AE using maximal evaluation scores and AUC-100. Bootstrapped DQN performs especially strongly on cumulative learning performance, while peak-policy performance provides a distinct evaluation view.

Table 1: Table 1 reports maximal evaluation scores for agents, including DQN and bootstrapped DQN.These scores represent the average score during each agent’s most successful evaluation period.
Table 2: Bootstrapped DQN is compared with Dynamic AE and DQN baselines using the AUC-100 metric.The comparison includes Boot-DQN, Boot-DQN+ without head rescaling, reproduced DQN* results, and Dynamic AE.
Table 2: Averaged across 14 games, Boot-DQN+ is over 50% better than the next-best competitor on AUC-100.The next-best competitor is bootstrapped DQN with gradient normalization.
Table 2: Both bootstrapped DQN implementations outperform Dynamic AE on average, while Bowling is the only game where Dynamic AE achieves the best result.The Bowling difference is dominated by the implementation comparison between DQN* and DQN.
Evaluation interpretation: Boot-DQN generally reaches higher peak scores over 200m frames, highlighting a distinction between best-policy evaluation and cumulative-reward evaluation.Boot-DQN+ sometimes plateaus early, and the largest improvements over DQN occur when performance during learning matters.