---
title: "Deep Exploration via Bootstrapped DQN — Osband 2016"
description: "Osband and colleagues propose bootstrapped DQN, a method inspired by Thompson sampling that… 27 references, cited by 56 papers here."
authors: ["Ian Osband", "Charles Blundell", "Alexander Pritzel", "Benjamin Van Roy"]
year: 2016
venue: "arXiv:1602.04621"
source: "https://arxiv.org/abs/1602.04621"
doi: "10.48550/arxiv.1602.04621"
arxiv: "1602.04621"
licence: "arXiv — non-exclusive license to distribute"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/osband-2016-deep-exploration-bootstrapped-dqn/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/osband-2016-deep-exploration-bootstrapped-dqn/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2016](https://md.research.elamur.ai/free/en/papers/2016/page/2/) / Deep Exploration via Bootstrapped DQN

# Deep Exploration via Bootstrapped DQN

**Authors:** Ian Osband, [Charles Blundell](https://md.research.elamur.ai/free/en/authors/charles-blundell/), [Alexander Pritzel](https://md.research.elamur.ai/free/en/authors/alexander-pritzel/) and Benjamin Van Roy · **Year:** 2016 · **Venue:** arXiv:1602.04621 · **Licence:** [arXiv — non-exclusive license to distribute](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/1602.04621) · [PDF](https://arxiv.org/pdf/1602.04621) · [DOI 10.48550/arxiv.1602.04621](https://doi.org/10.48550/arxiv.1602.04621) · [arXiv 1602.04621](https://arxiv.org/abs/1602.04621) · [OpenAlex](https://openalex.org/W2280163991)

**Citations:** 434 citations (OpenAlex, 2026-10-14) · [56](https://md.research.elamur.ai/free/en/papers/osband-2016-deep-exploration-bootstrapped-dqn/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Reinforcement learning agents typically explore with dithering schemes like ε-greedy. These schemes randomly perturb individual actions and cannot pursue information over several steps, which can make learning exponentially slower. Provably efficient alternatives exist, but they mostly apply only to small tabular problems or to linear value functions such as RLSVI. Osband and colleagues propose bootstrapped DQN, a method inspired by Thompson sampling that works with deep networks. A shared network feeds K separate Q-value heads. Each head has its own target network and learns from a bootstrapped portion of the replay data, tracked with Bernoulli masks. At the start of every episode the agent picks one head at random and acts greedily with it until the episode ends. This gives consistent, multi-step ("deep") exploration. On the Arcade Learning Environment, the method learns faster than DQN in most games, reaches human-level scores in fewer frames and gains far more cumulative reward, at modest extra compute. The work shows that cheap ensemble-style uncertainty can replace dithering in large-scale deep RL.

## Key points
- **Architecture:** One shared body with K bootstrapped heads, trained in a single forward/backward pass. The Atari setup used K=10 and p=1 and ran with under 20% more wall-clock time than DQN. Results were similar across mask probabilities p.
- **Regression check:** On a toy regression task, bootstrapped 2-layer networks (50 ReLU units per layer, 50 bootstrap samples) gave sensible uncertainty bands. The authors could not get useful estimates from dropout on the same task.
- **AUC-20 score:** Averaged over 14 games, bootstrapped DQN scored 0.62, versus 0.29 for base DQN and 0.37 for the best earlier exploration method. Full tables cover all 49 games.
- **Montezuma's Revenge:** The agent found the first key after 20m frames, while DQN saw no reward even after 200m frames. However, the agent did not learn to exploit this experience.
- **Ensemble policy:** Voting across heads can beat any single head. The spread of votes also signals policy uncertainty, and the heads tend to agree at critical decision points.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Google](https://md.research.elamur.ai/free/en/companies/google/) — Company, Mountain View, United States · 492 works · 440,463 citations
- [Stanford University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 506 works · 330,053 citations
- [Google DeepMind](https://md.research.elamur.ai/free/en/companies/google-deepmind/) — Company, London, United Kingdom · 72 works · 84,326 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎯 Decision Sciences](https://md.research.elamur.ai/free/en/shelves/decision-sciences/) · 249 works · [🎯 Management Science and Operations Research](https://md.research.elamur.ai/free/en/shelves/decision-sciences/management-science-and-operations-research/) · 134 works

## Cite

Cite as: Ian Osband, Charles Blundell, Alexander Pritzel and Benjamin Van Roy. 2016. Deep Exploration via Bootstrapped DQN. arXiv:1602.04621.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{osband2016deep,
  title = {{Deep Exploration via Bootstrapped DQN}},
  author = {Ian Osband, Charles Blundell, Alexander Pritzel and Benjamin {Van Roy}},
  year = {2016},
  doi = {10.48550/arxiv.1602.04621},
  eprint = {1602.04621},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1602.04621}
}
```

- [← previous Learning Natural Language Inference with LSTM](https://md.research.elamur.ai/free/en/papers/wang-2016-learning-natural-language-inference-lstm/)
- [next → Demographic Dialectal Variation in Social Media: A Case Study of African-American English](https://md.research.elamur.ai/free/en/papers/blodgett-2016-demographic-dialectal-variation-social-media/)
- [↑ back to papers of 2016](https://md.research.elamur.ai/free/en/papers/2016/page/2/)

## References

27 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. [The arcade learning environment: An evaluation platform for general agents](https://md.research.elamur.ai/free/en/papers/bellemare-2012-arcade-learning-environment-evaluation-platform/). arXiv preprint arXiv:1207.4708, 2012.
2. Peter J Bickel and David A Freedman. Some asymptotic theory for the bootstrap. The Annals of Statistics, pages 1196–1217, 1981. [find](https://scholar.google.com/scholar?q=Peter+J+Bickel+and+David+A+Freedman%2E+Some+asymptotic+theory+for+the+bootstrap%2E+The+Annals+of+Statistics%2C+pages+1196%E2%80%931217%2C+1981%2E)
3. Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. ICML, 2015. [find](https://scholar.google.com/scholar?q=Charles+Blundell%2C+Julien+Cornebise%2C+Koray+Kavukcuoglu%2C+and+Daan+Wierstra%2E+Weight+uncertainty+in+neural+networks%2E+ICML%2C+2015%2E)
4. Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems, pages 2800–2808, 2015. [find](https://scholar.google.com/scholar?q=Christoph+Dann+and+Emma+Brunskill%2E+Sample+complexity+of+episodic+fixed%2Dhorizon+reinforcement+learning%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+2800%E2%80%932808%2C+2015%2E)
5. Bradley Efron. The jackknife, the bootstrap and other resampling plans, volume 38. SIAM, 1982. [find](https://scholar.google.com/scholar?q=Bradley+Efron%2E+The+jackknife%2C+the+bootstrap+and+other+resampling+plans%2C+volume+38%2E+SIAM%2C+1982%2E)
6. Bradley Efron and Robert J Tibshirani. An introduction to the bootstrap. CRC press, 1994. [find](https://scholar.google.com/scholar?q=Bradley+Efron+and+Robert+J+Tibshirani%2E+An+introduction+to+the+bootstrap%2E+CRC+press%2C+1994%2E)
7. Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. arXiv preprint arXiv:1506.02142, 2015. [find](https://scholar.google.com/scholar?q=Yarin+Gal+and+Zoubin+Ghahramani%2E+Dropout+as+a+bayesian+approximation%3A+Representing+model+uncertainty+in+deep+learning%2E+arXiv+preprint+arXiv%3A1506%2E02142%2C+2015%2E)
8. Arthur Guez, David Silver, and Peter Dayan. Efficient bayes-adaptive reinforcement learning using sample-based search. In Advances in Neural Information Processing Systems, pages 1025–1033, 2012. [find](https://scholar.google.com/scholar?q=Arthur+Guez%2C+David+Silver%2C+and+Peter+Dayan%2E+Efficient+bayes%2Dadaptive+reinforcement+learning+using+sample%2Dbased+search%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+1025%E2%80%931033%2C+2012%2E)
9. Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563–1600, 2010. [find](https://scholar.google.com/scholar?q=Thomas+Jaksch%2C+Ronald+Ortner%2C+and+Peter+Auer%2E+Near%2Doptimal+regret+bounds+for+reinforcement+learning%2E+Journal+of+Machine+Learning+Research%2C+11%3A1563%E2%80%931600%2C+2010%2E)
10. Sham Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, University College London, 2003. [find](https://scholar.google.com/scholar?q=Sham+Kakade%2E+On+the+Sample+Complexity+of+Reinforcement+Learning%2E+PhD+thesis%2C+University+College+London%2C+2003%2E)
11. Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4–22, 1985. [find](https://scholar.google.com/scholar?q=Tze+Leung+Lai+and+Herbert+Robbins%2E+Asymptotically+efficient+adaptive+allocation+rules%2E+Advances+in+applied+mathematics%2C+6%281%29%3A4%E2%80%9322%2C+1985%2E)
12. Volodymyr et al. Mnih. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015. [find](https://scholar.google.com/scholar?q=Volodymyr+et+al%2E+Mnih%2E+Human%2Dlevel+control+through+deep+reinforcement+learning%2E+Nature%2C+518%287540%29%3A529%E2%80%93533%2C+2015%2E)
13. Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. In NIPS, pages 3003–3011. Curran Associates, Inc., 2013. [find](https://scholar.google.com/scholar?q=Ian+Osband%2C+Daniel+Russo%2C+and+Benjamin+Van+Roy%2E+%28More%29+efficient+reinforcement+learning+via+posterior+sampling%2E+In+NIPS%2C+pages+3003%E2%80%933011%2E+Curran+Associates%2C+Inc%2E%2C+2013%2E)
14. Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pages 1466–1474, 2014. [find](https://scholar.google.com/scholar?q=Ian+Osband+and+Benjamin+Van+Roy%2E+Model%2Dbased+reinforcement+learning+and+the+eluder+dimension%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+1466%E2%80%931474%2C+2014%2E)
15. Ian Osband and Benjamin Van Roy. Bootstrapped thompson sampling and deep exploration. arXiv preprint arXiv:1507.00300, 2015. — [arXiv:1507.00300](https://arxiv.org/abs/1507.00300) [find](https://scholar.google.com/scholar?q=Ian+Osband+and+Benjamin+Van+Roy%2E+Bootstrapped+thompson+sampling+and+deep+exploration%2E+arXiv+preprint+arXiv%3A1507%2E00300%2C+2015%2E+%E2%80%94+%5BarXiv%3A1507%2E00300%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1507%2E00300%29)
16. Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. arXiv preprint arXiv:1402.0635, 2014. — [arXiv:1402.0635](https://arxiv.org/abs/1402.0635) [find](https://scholar.google.com/scholar?q=Ian+Osband%2C+Benjamin+Van+Roy%2C+and+Zheng+Wen%2E+Generalization+and+exploration+via+randomized+value+functions%2E+arXiv+preprint+arXiv%3A1402%2E0635%2C+2014%2E+%E2%80%94+%5BarXiv%3A1402%2E0635%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1402%2E0635%29)
17. Art B Owen, Dean Eckles, et al. Bootstrapping data arrays of arbitrary order. The Annals of Applied Statistics, 6(3):895–927, 2012. [find](https://scholar.google.com/scholar?q=Art+B+Owen%2C+Dean+Eckles%2C+et+al%2E+Bootstrapping+data+arrays+of+arbitrary+order%2E+The+Annals+of+Applied+Statistics%2C+6%283%29%3A895%E2%80%93927%2C+2012%2E)
18. Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05952, 2015. [find](https://scholar.google.com/scholar?q=Tom+Schaul%2C+John+Quan%2C+Ioannis+Antonoglou%2C+and+David+Silver%2E+Prioritized+experience+replay%2E+arXiv+preprint+arXiv%3A1511%2E05952%2C+2015%2E)
19. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. [Dropout: A simple way to prevent neural networks from overfitting](https://md.research.elamur.ai/free/en/papers/srivastava-2014-dropout-simple-way-prevent/). The Journal of Machine Learning Research, 15(1):1929–1958, 2014.
20. Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv:1507.00814, 2015. [find](https://scholar.google.com/scholar?q=Bradly+C+Stadie%2C+Sergey+Levine%2C+and+Pieter+Abbeel%2E+Incentivizing+exploration+in+reinforcement+learning+with+deep+predictive+models%2E+arXiv+preprint+arXiv%3A1507%2E00814%2C+2015%2E)
21. Malcolm J. A. Strens. A bayesian framework for reinforcement learning. In ICML, pages 943–950, 2000. [find](https://scholar.google.com/scholar?q=Malcolm+J%2E+A%2E+Strens%2E+A+bayesian+framework+for+reinforcement+learning%2E+In+ICML%2C+pages+943%E2%80%93950%2C+2000%2E)
22. Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, March 1998. [find](https://scholar.google.com/scholar?q=Richard+Sutton+and+Andrew+Barto%2E+Reinforcement+Learning%3A+An+Introduction%2E+MIT+Press%2C+March+1998%2E)
23. Gerald Tesauro. Temporal difference learning and td-gammon. Communications of the ACM, 38(3):58–68, 1995. [find](https://scholar.google.com/scholar?q=Gerald+Tesauro%2E+Temporal+difference+learning+and+td%2Dgammon%2E+Communications+of+the+ACM%2C+38%283%29%3A58%E2%80%9368%2C+1995%2E)
24. W.R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294, 1933. [find](https://scholar.google.com/scholar?q=W%2ER%2E+Thompson%2E+On+the+likelihood+that+one+unknown+probability+exceeds+another+in+view+of+the+evidence+of+two+samples%2E+Biometrika%2C+25%283%2F4%29%3A285%E2%80%93294%2C+1933%2E)
25. Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. arXiv preprint arXiv:1509.06461, 2015. [find](https://scholar.google.com/scholar?q=Hado+Van+Hasselt%2C+Arthur+Guez%2C+and+David+Silver%2E+Deep+reinforcement+learning+with+double+q%2Dlearning%2E+arXiv+preprint+arXiv%3A1509%2E06461%2C+2015%2E)
26. Ziyu Wang, Nando de Freitas, and Marc Lanctot. Dueling network architectures for deep reinforcement learning. arXiv preprint arXiv:1511.06581, 2015. [find](https://scholar.google.com/scholar?q=Ziyu+Wang%2C+Nando+de+Freitas%2C+and+Marc+Lanctot%2E+Dueling+network+architectures+for+deep+reinforcement+learning%2E+arXiv+preprint+arXiv%3A1511%2E06581%2C+2015%2E)
27. Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. In NIPS, pages 3021–3029, 2013. [find](https://scholar.google.com/scholar?q=Zheng+Wen+and+Benjamin+Van+Roy%2E+Efficient+exploration+and+value+function+generalization+in+deterministic+systems%2E+In+NIPS%2C+pages+3021%E2%80%933029%2C+2013%2E)

*Updated 2 November 2026*