Deep Exploration via Bootstrapped DQN
E cient exploration remains a major challenge for reinforcement learning (RL). Common dithering strategies for exploration, such as '-greedy, do not carry out temporally-extended (or deep) exploration; this can lead to exponentially larger data requirements. However, most algorithms for statistically e cient RL are not computationally tractable in complex environments. Randomized value functions o er a promising approach to e cient exploration with generalization, but existing algorithms are not compatible with nonlinearly parameterized value functions. As a first step towards addressing such contexts we develop bootstrapped DQN. We demonstrate that bootstrapped DQN can combine deep exploration with deep neural networks for exponentially faster learning than any dithering strategy. In the Arcade Learning Environment bootstrapped DQN substantially improves learning speed and cumulative performance across most games.
First of all, let me say I am not an expert in DQN or neural networks, so this review may be a little superficial.  The authors propose a modification of the DQN algorithm for reinforcement learning with neural network function approximation. The objective is to tackle the exploration problem, which is a big issue because the "default" epsilon-greedy approach has provable limitations in all but the simplest of setups. The description of the new approach is sometimes a little vague (see below), but the general approach is to construct several (K - a free parameter) neural networks (or one big neural network with K heads) to approximate the value function and play  each episode by first randomly choosing a network and following its recommendations until the end of the episode and using the resulting  data to train a random subset of the networks. The idea is to use the variation in the learning to simulate some kind of confidence bound  so that the algorithm behaves a little bit like Thompson sampling.
The paper has some strengths and weaknesses. First of all, the experimental results are quite interesting, especially that the algorithm outperforms DQN on Atari. The results on the synthetic experiment are also interesting.  I have three main concerns about the paper.   1. There is significant difficulty in reconstructing what is precisely going on. For example, in Figure 1,  what exactly is a head? How many layers would it have? What is the "Frame"? I wish the paper would spend a lot more space explaining how exactly bootstrapped DQN operates (Appendix B cleared up a lot of my queries and I suggest this be moved into the main body).  2. The general approach involves partitioning (with some duplication) the samples between the heads with the idea that some heads will be optimistic and encouraging exploration. I think that's an interesting idea, but the setting where it is used is complicated. It would be useful if this was reduced to (say) a bandit setting without the neural network. The resulting algorithm will partition the data for each arm into K (possibly overlapping) sub-samples and use the empirical estimate from each partition at random in each step. This seems like it could be interesting, but I am worried that the partitioning will mean that a lot of data is essentially discarded when it comes to eliminating arms. Any thoughts on how much data efficiency is lost in simple settings? Can you prove regret guarantees in this setting?  3. The paper does an OK job at describing the experimental setup, but still it is complicated with a lot of engineering going on in the background. This presents two issues. First, it would take months to re-produce these experiments (besides the hardware requirements). Second, with such complicated algorithms it's hard to know what exactly is leading to the improvement. For this reason I find this kind of paper a little unscientific, but maybe this is how things have to be. I wonder, do the authors plan to release their code?  Overall I think this is an interesting idea, but the authors have not convinced me that this is a principled approach. The experimental results do look promising, however, and I'm sure there would be interest in this paper at NIPS. I wish the paper was more concrete, and also that code/data/network initialisation can be released. For me it is borderline.   Minor comments:  * L156-166: I can barely understand this paragraph, although I think I know what you want to say. First of all, there /are/ bandit algorithms that plan to explore. Notably the Gittins strategy, which treats the evolution of the posterior for each arm as a Markov chain. Besides this, the figure is  hard to understand. "Dashed lines indicate that the agent can plan ahead..." is too vague to be understood concretely.  * L176: What is $x$?  * L37: Might want to mention that these algorithms follow the sampled policy for awhile.  * L81: Please give more details. The state-space is finite? Continuous? What about the actions? In what space does theta lie? I can guess the answers to all these questions, but why not be precise?  * Can you say something about the computation required to implement the experiments? How long did the experiments take and on what kind of hardware?   * Just before Appendix D.2. "For training we used an epsilon-greedy ..." What does this mean exactly? You have epsilon-greedy exploration on top of the proposed strategy?