learning* (PSRL, @osband2013more [@osband2016posterior]), which has near-optimal regret bounds. PSRL samples an MDP from its posterior each episode and exactly solves $Q^*$, its optimal $Q$-function. However, in high-dimensional settings, both approximating the posterior over MDPs and solving the sampled MDP are intractable. Bootstrapped DQN avoids having to establish and sample from the posterior over MDPs by instead approximating the posterior over $Q^*$. In addition, bootstrapped DQN uses a multi-headed neural network to represent the $Q$-ensemble. While the authors proposed bootstrapping to estimate the posterior distribution, their empirical findings show best performance is attained by simply relying on different initializations for the different heads, not requiring the sampling-with-replacement process that is prescribed by bootstrapping.

In this paper, we design new algorithms that build on the $Q$-ensemble approach from @osband2016deep. However, instead of using posterior sampling for exploration, we use the uncertainty estimates from the $Q$-ensemble. Specifically, we propose the UCB exploration strategy. This strategy is inspired by established UCB algorithms in the bandit setting and constructs uncertainty estimates of the $Q$-values. In this strategy, agents are optimistic and take actions with the highest UCB. We demonstrate that our algorithms significantly improve performance on the Atari benchmark.

Background
==========

Notation {#section:notate}
--------

