Title: UCB EXPLORATION VIA Q-ENSEMBLES

Abstract: We show how an ensemble of Q * -functions can be leveraged for more effective exploration in deep reinforcement learning. We build on well established algorithms from the bandit setting, and adapt them to the Q-learning setting. We propose an exploration strategy based on upper-confidence bounds (UCB). Our experiments show significant gains on the Atari benchmark.
Deep reinforcement learning seeks to learn mappings from high-dimensional observations to actions. Deep Q-learning (Mnih et al. (2015) ) is a leading technique that has been used successfully, especially for video game benchmarks. However, fundamental challenges remain, for example, improving sample efficiency and ensuring convergence to high quality solutions. Provably optimal solutions exist in the bandit setting and for small MDPs, and at the core of these solutions are exploration schemes. However these provably optimal exploration techniques do not extend to deep RL in a straightforward way.
Bootstrapped DQN (Osband et al. (2016)) is a previous attempt at adapting a theoretically verified approach to deep RL. In particular, it draws inspiration from posterior sampling for reinforcement learning (PSRL, Osband et al. (2013); Osband and Van Roy (2016)), 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 Osband et al. (2016). However, instead of using posterior sampling for exploration, we construct uncertainty estimates from the Q-ensemble. Specifically, we first propose the Ensemble Voting algorithm where the agent takes action by a majority vote from the Q-ensemble. Next, 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
We model reinforcement learning as a Markov decision process (MDP). We define an MDP as (S, A, T, R, p 0 , γ), in which both the state space S and action space A are discrete, T : S × A × S → R + is the transition distribution, R : S × A → R is the reward function, assumed deterministic given the state and action, and γ ∈ (0, 1] is a discount factor, and p 0 is the initial state distribution. We denote a transition experience as τ = (s, a, r, s ) where s ∼ T (s |s, a) and r = R(s, a). A policy π : S → A specifies the action taken after observing a state. We denote the Q-function for policy π as Q π (s, a) := E π ∞ t=0 γ t r t |s 0 = s, a 0 = a where r t = R(s t , a t ). The optimal Q * -function

2.2. EXPLORATION IN REINFORCEMENT LEARNING:

A notable early optimality result in reinforcement learning was the proof by Watkins and Dayan Watkins (1989) ; Watkins and Dayan (1992) that an online Q-learning algorithm is guaranteed to converge to the optimal policy, provided that every state is visited an infinite number of times. However, the convergence of Watkins' Q-learning can be prohibitively slow in MDPs wheregreedy action selection explores state space randomly. Later work developed reinforcement learning algorithms with provably fast (polynomial-time) convergence (Kearns and Singh (2002) ; Brafman and Tennenholtz (2002) ; Strehl et al. (2006) ). At the core of these provably-optimal learning methods is some exploration strategy, which actively encourages the agent to visit novel state-action pairs. For example, R-MAX optimistically assumes that infrequently-visited states provide maximal reward, and delayed Q-learning initializes the Q-function with high values to ensure that each state-action is chosen enough times to drive the value down.

Since the theoretically sound RL algorithms are not computationally practical in the deep RL setting, deep RL implementations often use simple exploration methods such as -greedy and Boltzmann exploration, which are often sample-inefficient and fail to find good policies. One common approach of exploration in deep RL is to construct an exploration bonus, which adds a reward for visiting state-action pairs that are deemed to be novel or informative. In particular, several prior methods define an exploration bonus based on a density model or dynamics model. Examples include VIME by Houthooft et al. (2016) , which uses variational inference on the forward-dynamics model, and Tang et al. (2016) , Bellemare et al. (2016) , Ostrovski et al. (2017) , Fu et al. (2017) . While these methods yield successful exploration in some problems, a major drawback is that this exploration bonus does not depend on the rewards, so the exploration may focus on irrelevant aspects of the environment, which are unrelated to reward.

2.3. BAYESIAN REINFORCEMENT LEARNING:

Earlier works on Bayesian reinforcement learning include Dearden et al. (1998; 1999) . Dearden et al. (1998) studied Bayesian Q-learning in the model-free setting and learned the distribution of Q *values through Bayesian updates. The prior and posterior specification relied on several simplifying assumptions, some of which are not compatible with the MDP setting. Dearden et al. (1999) took a model-based approach that updates the posterior distribution of the MDP. The algorithm samples from the MDP posterior multiple times and solving the Q * values at every step. This approach is only feasible for RL problems with very small state space and action space. Strens (2000) proposed posterior sampling for reinforcement learning (PSRL). PSRL instead takes a single sample of the MDP from the posterior in each episode and solves the Q * values. Recent works including Osband et al. (2013) and Osband and Van Roy (2016) established near-optimal Bayesian regret bounds for episodic RL. Sorg et al. (2012) models the environment and constructs exploration bonus from variance of model parameters. These methods are experimented on low dimensional problems only, because the computational cost of these methods is intractable for high dimensional RL.

2.4. BOOTSTRAPPED DQN:

Inspired by PSRL, but wanting to reduce computational cost, prior work developed approximate methods. Osband et al. (2014) proposed randomized least-square value iteration for linearly-parameterized value functions. Bootstrapped DQN Osband et al. (2016) applies to Q-functions parameterized by deep neural networks. Bootstrapped DQN (Osband et al. (2016) ) maintains a Q-ensemble, represented by a multi-head neural net structure to parameterize K ∈ N + Q-functions. This multi-head structure shares the convolution layers but includes multiple "heads", each of which defines a Q-function Q k .

Bootstrapped DQN diversifies the Q-ensemble through two mechanisms. The first mechanism is independent initialization. The second mechanism applies different samples to train each Q-function.

These Q-functions can be trained simultaneously by combining their loss functions with the help of a random mask

m τ ∈ R K + L = τ ∈Bmini K k=1 m k τ • (Q k (s, a; θ) -y Q k τ ) 2 ,

where y Q k τ is the target of the kth Q-function. Thus, the transition τ updates Q k only if m k τ is nonzero. To avoid the overestimation issue in DQN, bootstrapped DQN calculates the target value y Q k τ using the approach of Double DQN (Van Hasselt et al. (2016) ), such that the current Q k (•; θ t ) network determines the optimal action and the target network Q k (•; θ -) estimates the value

y Q k τ = r + γ max a Q k (s , argmax a Q k (s , a; θ t ); θ -).

In their experiments on Atari games, Osband et al. (2016) set the mask m τ = (1, . . . , 1) such that all {Q k } are trained with the same samples and their only difference is initialization. Bootstrapped DQN picks one Q k uniformly at random at the start of an episode and follows the greedy action a t = argmax a Q k (s t , a) for the whole episode.

3. ENSEMBLE VOTING:

Ignoring computational costs, the ideal Bayesian approach to reinforcement learning is to maintain a posterior over the MDP. However, with limited computation and model capacity, it is more tractable to maintain a posterior of the Q * -function. This motivates using a Q-ensemble as a particle filter-based approach to approximate the posterior over Q * -function and we display our first proposed method, Ensemble Voting, in Algorithm 1.

Each Q k in the Q-ensemble {Q k } K

k=1 is parametrized with a deep neural network whose parameters are initialized independently at the start of training. Each Q k proposes an action that maximizes the Q-value according to Q k at every time step and the agent chooses the action by a majority vote

a t = MajorityVote({argmax a Q k (s t , a)} K k=1 ).

At each learning interval, a minibatch of transitions is sampled from the replay buffer and each Q k takes a Bellman update based on this minibatch. For stability, Algorithm 1 also uses a target network for each Q k as in Double DQN in the batched update.

We point out that the difference among the parameters of the Q-ensemble {Q k } comes only from the independent random initialization. The deep neural network parametrization of the Q-ensemble introduces nonconvexity into the objective function of Bellman update, so the Q-ensemble {Q k } do not converge to the same Q-function during training even though they are trained with the same minibatches at every update. We also experimented with bagging by updating each Q k using an independently drawn minibatch. However, bagging led to inferior learning performance. This phenomenon that that bagging deteriorates the performance of deep ensembles is also observed in supervised learning settings. Lee et al. (2015) observed that supervised learning trained with deep ensembles with random initializations perform better than bagging for deep ensembles. Lakshminarayanan et al. (2016) used deep ensembles for uncertainty estimates and also observed that bagging deteriorated performance in their experiments.

Lu and Van Roy (2017) develop ensemble sampling for bandit problems with deep neural network parametrized policies and the theoretical justification. We derive a posterior update rule for the Q * function and approximations to the posterior update using ensembles in Appendix C. We note that in bootstrapped DQN, ensemble voting is applied for evaluation while Algorithm 1 uses ensemble voting during learning. In the experiments (Sec. 5), we demonstrate that Algorithm 1 is superior to bootstrapped DQN. The action choice of Algorithm 1 is exploitation only. In the next section, we propose our UCB exploration strategy. 

4. UCB EXPLORATION STRATEGY USING Q-ENSEMBLES:

In this section, we propose optimism-based exploration by adapting the UCB algorithms (Auer et al. (2002) ; Audibert et al. (2009) ) from the bandit setting. The UCB algorithms maintain an upper-confidence bound for each arm, such that the expected reward from pulling each arm is smaller than this bound with high probability. At every time step, the agent optimistically chooses the arm with the highest UCB. Auer et al. (2002) constructed the UCB based on empirical reward and the number of times each arm is chosen. Audibert et al. (2009) incorporated the empirical variance of each arm's reward into the UCB, such that at time step t, an arm A t is pulled according to

A t = argmax i ri,t + c 1 • Vi,t log(t) n i,t + c 2 • log(t) n i,t

where ri,t and Vi,t are the empirical reward and variance of arm i at time t, n i,t is the number of times arm i has been pulled up to time t, and c 1 , c 2 are positive constants.

We extend the intuition of UCB algorithms to the RL setting. Using the outputs of the {Q k } functions, we construct a UCB by adding the empirical standard deviation σ(s t , a) of {Q k (s t , a)} K k=1 to the empirical mean μ(s t , a) of {Q k (s t , a)} K k=1 . The agent chooses the action that maximizes this UCB

a t ∈ argmax a μ(s t , a) + λ • σ(s t , a) ,

where λ ∈ R + is a hyperparameter. We present Algorithm 2, which incorporates the UCB exploration. The hyperparemeter λ controls the degrees of exploration. In Section 5, we compare the performance of our algorithms on Atari games using a consistent set of parameters.

Algorithm 2 UCB Exploration with Q-Ensembles 

1: Input: Value function networks Q with K outputs {Q k } K k=1 .

5. EXPERIMENT:

In this section, we conduct experiments to answer the following questions:

1. does Ensemble Voting, Algorithm 1, improve upon existing algorithms including Double DQN and bootstrapped DQN?

2. is the proposed UCB exploration strategy of Algorithm 2 effective in improving learning compared to Algorithm 1, Double DQN and bootstrapped DQN?

3. how does UCB exploration compare with prior exploration methods such as the count-based exploration method of Bellemare et al. (2016) ?

We evaluate the algorithms on each Atari game of the Arcade Learning Environment (Bellemare et al. (2013) ). We use the multi-head neural net architecture of Osband et al. (2016) . We fix the common hyperparameters of all algorithms based on a well-tuned double DQN implementation, which uses the Adam optimizer (Kingma and Ba (2014) ), different learning rate and exploration schedules compared to Mnih et al. (2015) . Appendix A tabulates the hyperparameters. The number of {Q k } functions is K = 10. Experiments are conducted on the OpenAI Gym platform (Brockman et al. (2016) ) and trained with 40 million frames and 2 trials on each game.

We take the following directions to evaluate the performance of our algorithms:

1. we compare Algorithm 1 against Double DQN and bootstrapped DQN, 2. we isolate the impact of UCB exploration by comparing Algorithm 2 with λ = 0.1, denoted as ucb exploration, against Algorithm 1, Double DQN, and bootstrapped DQN.

3. we compare Algorithm 1 and Algorithm 2 with the count-based exploration method of Bellemare et al. (2016) .

4. we aggregate the comparison according to different categories of games, to understand when our methods are suprior. In Appendix B, we tabulate detailed results that compare our algorithms, Ensemble Voting and ucb exploration, against prior methods. In 

6. CONCLUSION:

We proposed a Q-ensemble approach to deep Q-learning, a computationally practical algorithm inspired by Bayesian reinforcement learning that outperforms Double DQN and bootstrapped DQN, as evaluated on Atari. The key ingredient is the UCB exploration strategy, inspired by bandit algorithms.

Our experiments show that the exploration strategy achieves improved learning performance on the majority of Atari games.

A HYPERPARAMETERS:

We tabulate the hyperparameters in our well-tuned implementation of double DQN in 

. C.1 POSTERIOR UPDATE FOR THE Q * -FUNCTION

An MDP is specified by the transition probability T and the reward function R. Unlike prior works outlined in Section 2.3 which learned the posterior of the MDP, we will consider the joint distribution over (Q * , T ). Note that R can be recovered from Q * given T . So (Q * , T ) determines a unique MDP. In this section, we assume that the agent samples (s, a) according to a fixed distribution. The corresponding reward r and next state s given by the MDP append to (s, a) to form a transition τ = (s, a, r, s ), for updating the posterior of (Q * , T ). Recall that the Q * -function satisfies the Bellman equation

Q(s, a) = r + E s ∼T (•|s,a) γ max a Q(s , a ) .

Denote the joint prior distribution as p(Q * , T ) and the posterior as p. We apply Bayes' formula to expand the posterior:

EQUATION

where Z(τ ) is a normalizing constant and the second equality is because s and a are sampled randomly from S and A. Next, we calculate the two conditional probabilities in (1). First,

EQUATION

where the first equality is because given T , Q * does not influence the transition. Second,

EQUATION

where 1 {•} is the indicator function and in the last equation we abbreviate it as 1(Q * , T ). Substituting (2) and ( 3) into (1), we obtain the joint posterior of Q * and T after observing an additional randomly sampled transition τ

EQUATION

C.2 APPROXIMATIONS WITH Q-ENSEMBLES:

The exact Q * -posterior update (4) is intractable in high-dimensional RL due to the large space of (Q * , T ). Thus, we make several approximations to the Q * -posterior update. First, we approximate the prior of Q * by sampling K ∈ N + independently initialized Q * -functions {Q k } K k=1 . Next, we update them as more transitions are sampled. The resulting {Q k } approximate samples drawn from the posterior. The agent chooses the action by taking a majority vote from the actions determined by each Q k .

We derive the update rule for {Q k } after observing a new transition τ = (s, a, r, s ). At iteration i,

given Q * = Q k,i (•; θ k ) parametrized by θ k the joint probability of (Q * , T ) factors into p(Q k,i , T ) = p(Q * , T |Q * = Q k,i ) = p(T |Q k,i ).

(5) Substitute ( 5) into (4) and we obtain the corresponding posterior for each Q k,i+1 at iteration i + 1 as

EQUATION

We first derive a lower bound of the the posterior p(Q k,i+1 |τ ):

EQUATION

where we apply a limit representation of the indicator function in the third equation. The fourth equation is due to the bounded convergence theorem. The inequality is Jensen's inequality. The last equation ( 9) replaces the limit with an indicator function.

A sufficient condition for (8) is to maximize the lower-bound of the posterior distribution in (9) by ensuring the indicator function in (9) to hold. We can replace (8) with the following update

Q k,i+1 ← argmin Q k,i+1 E T ∼ p(T |Q k,i ,τ ) Q k,i+1 (s, a) -r + γ • E s ∼T (•|s,a) max a Q k,i+1 (s , a ) 2 .

(10) However, (10) is not tractable because the expectation in ( 10) is taken with respect to the posterior p(T |Q k,i , τ ) of the transition T . To overcome this challenge, we approximate the posterior update by reusing the one-sample next state s from τ . Solving the exact minimal for each Q k,i+1 is impractical, thus we take a gradient step on Q k,i+1 according to the following gradient

θ k ← θ k + η • Q k (s, a; θ k ) -(r + γ • max a Q k (s , a ; θ k )) ∇ θ k Q k (s, a; θ k ),

where η is the step size. Instead of updating Q k after each transition, we use an experience replay buffer B to store observed transitions and sample a minibatch B mini of transitions (s, a, r, s ) for each update. In this case, the batched update of each Q k,i to Q k,i+1 becomes a standard Bellman update

θ k ← θ k + η • E (s,a,r,s )∈Bmini Q k (s, a; θ k ) -(r + γ • max a Q k (s , a ; θ k )) ∇ θ k Q k (s, a; θ k ) .

D INFOGAIN EXPLORATION:

In this section, we also studied an "InfoGain" exploration bonus, which encourages agents to gain information about the Q * -function and examine its effectiveness. We found it had some benefits on top of Ensemble Voting, but no uniform additional benefits once already using Q-ensembles on top of Double DQN. We describe the approach and our experimental findings. Similar to Sun et al. (2011) 

P T,k (a|s) = exp Q k (s, a)/T a exp Q k (s, a )/T ,

where T > 0 is a temperature parameter. Next, calculate the average Boltzmann distribution

P T,avg = 1 K • K k=1 P T,k (a|s).

The InfoGain exploration bonus is the average KL

EQUATION

The modified reward is r(s, a, s ) = r(s, a)

EQUATION

where ρ ∈ R + is a hyperparameter that controls the degree of exploration.

The exploration bonus b T (s t ) encourages the agent to explore where {Q k } disagree. The temperature parameter T controls the sensitivity to discrepancies among {Q k }. When T → +∞, {P T,k } converge to the uniform distribution on the action space and b T (s) → 0. When T is small, the differences among {Q k } are magnified and b T (s) is large.

We display Algorithrim 3, which incorporates our InfoGain exploration bonus into Algorithm 2. The hyperparameters λ, T and ρ vary for each game.

Algorithm 3 UCB + InfoGain Exploration with Q-Ensembles We demonstrate the performance of the combined UCB+InfoGain exploration in Figure 3 and Figure 3 . We augment the previous figures in Section 5 with the performance of ucb+infogain exploration, where we set λ = 0.1, ρ = 1, and T = 1 in Algorithm 3.

Figure 3 shows that combining UCB and InfoGain exploration does not lead to uniform improvement in the normalized learning curve.

At the individual game level, Figure 3 shows that the impact of InfoGain exploration varies. UCB exploration achieves sufficient exploration in games including Demon Attack and Kangaroo and Riverraid, while InfoGain exploration further improves learning on Enduro, Seaquest, and Up N Down. The effect of InfoGain exploration depends on the choice of the temperature T. The optimal temperature parameter varies across games. In Figure 5 , we display the behavior of ucb+infogain exploration with different temperature values. Thus, we see the InfoGain exploration bonus, tuned with the appropriate temperature parameter, can lead to improved learning for games that require extra exploration, such as ChopperCommand, KungFuMaster, Seaquest, UpNDown. 

:



Figures and Tables:

corresponds to taking the optimal policyQ * (s, a) := sup π Q π (s, a)and satisfies the Bellman equationQ * (s, a) = E s ∼T (•|s,a) r + γ • max a Q * (s , a ) .

Figure 1 compares the normalized learning curves of all algorithms across Atari games. Overall, Ensemble Voting, Algorithm 1, outperforms both Double DQN and bootstrapped DQN. With exploration, ucb exploration improves further by outperforming Ensemble Voting.

Figure1: Comparison of algorithms in normalized learning curve. The normalized learning curve is calculated as follows: first, we normalize learning curves for all algorithms in the same game to the interval [0, 1]; next, average the normalized learning curve from all games for each algorithm.

Figure 4: Comparison of algorithms against Double DQN and bootstrapped DQN.

Pick an action according to a t ∈ argmax a μ(s t , a) + λ • σ(s t , a)Receive state s t+1 and reward r t from environment, having taken action a t 8:Add (s t , a t , r t , s t+1 ) to replay buffer B

Table content: <table><tr><td>4:</td><td>Obtain initial state from environment s 0</td></tr><tr><td>5:</td><td>for step t = 1, . . . until end of episode do</td></tr><tr><td>6:</td><td/></tr><tr><td>7:</td><td/></tr><tr><td>9:</td><td>At learning interval, sample random minibatch and update {Q k }</td></tr><tr><td>10:</td><td>end for</td></tr><tr><td colspan="2">11: end for</td></tr></table>

Figure 2 displays the learning curves of these five algorithms on a set of six Atari games. Ensemble Voting outperforms Double DQN and bootstrapped DQN. ucb exploration outperforms Ensemble Voting.In Table3, we compare our proposed methods with the count-based exploration method A3C+ ofBellemare et al. (2016) based on their published results of A3C+ trained with 200 million frames. We point out that even though our methods were trained with only 40 million frames, much less than A3C+'s 200 million frames, UCB exploration achieves the highest average reward in 28 games, Ensemble Voting in 10 games, and A3C+ in 10 games. Our approach outperforms A3C+.Finally to understand why and when the proposed methods are superior, we aggregate the comparison results according to four categories: Human Optimal, Score Explicit, Dense Reward, and Sparse Reward. These categories follow the taxonomy in Table1ofOstrovski et al. (2017). Out of all games evaluated, 23 games are Human Optimal, 8 are Score Explicit, 8 are Dense Reward, and 5 are

Table content: <table/>



Table content: <table><tr><td>:</td></tr></table>



Table content: <table><tr><td/><td colspan="2">Ensemble Voting UCB-Exploration</td><td>A3C+</td></tr><tr><td>Alien</td><td>2282.8</td><td>2817.6</td><td>1848.33</td></tr><tr><td>Amidar</td><td>683.72</td><td>663.8</td><td>964.77</td></tr><tr><td>Assault</td><td>3213.58</td><td>3702.76</td><td>2607.28</td></tr><tr><td>Asterix</td><td>8740.0</td><td>8732.0</td><td>7262.77</td></tr><tr><td>Asteroids</td><td>1149.3</td><td>1007.8</td><td>2257.92</td></tr><tr><td>Atlantis</td><td>1786305.0</td><td>2016145.0</td><td>1733528.71</td></tr><tr><td>Bank Heist</td><td>869.4</td><td>906.9</td><td>991.96</td></tr><tr><td>Battle Zone</td><td>27430.0</td><td>26770.0</td><td>7428.99</td></tr><tr><td>Beam Rider</td><td>7991.9</td><td>9188.26</td><td>5992.08</td></tr><tr><td>Bowling</td><td>32.92</td><td>38.06</td><td>68.72</td></tr><tr><td>Boxing</td><td>94.47</td><td>98.08</td><td>13.82</td></tr><tr><td>Breakout</td><td>426.78</td><td>411.31</td><td>323.21</td></tr><tr><td>Centipede</td><td>6153.28</td><td>6237.18</td><td>5338.24</td></tr><tr><td>Chopper Command</td><td>3544.0</td><td>3677.0</td><td>5388.22</td></tr><tr><td>Crazy Climber</td><td>126677.0</td><td>127754.0</td><td>104083.51</td></tr><tr><td>Demon Attack</td><td>30004.4</td><td>59861.9</td><td>19589.95</td></tr><tr><td>Double Dunk</td><td>-11.94</td><td>-4.08</td><td>-8.88</td></tr><tr><td>Enduro</td><td>1999.88</td><td>2752.55</td><td>749.11</td></tr><tr><td>Fishing Derby</td><td>30.02</td><td>29.71</td><td>29.46</td></tr><tr><td>Freeway</td><td>33.92</td><td>33.96</td><td>27.33</td></tr><tr><td>Frostbite</td><td>1196.0</td><td>1903.0</td><td>506.61</td></tr><tr><td>Gopher</td><td>10993.2</td><td>12910.8</td><td>5948.40</td></tr><tr><td>Gravitar</td><td>371.5</td><td>318.0</td><td>246.02</td></tr><tr><td>Ice Hockey</td><td>-1.73</td><td>-4.71</td><td>-7.05</td></tr><tr><td>Jamesbond</td><td>602.0</td><td>710.0</td><td>1024.16</td></tr><tr><td>Kangaroo</td><td>8174.0</td><td>14196.0</td><td>5475.73</td></tr><tr><td>Krull</td><td>8669.17</td><td>9171.61</td><td>7587.58</td></tr><tr><td>Kung Fu Master</td><td>30988.0</td><td>31291.0</td><td>26593.67</td></tr><tr><td>Montezuma Revenge</td><td>1.0</td><td>4.0</td><td>142.50</td></tr><tr><td>Ms Pacman</td><td>3039.7</td><td>3425.4</td><td>2380.58</td></tr><tr><td>Name This Game</td><td>9255.1</td><td>9570.5</td><td>6427.51</td></tr><tr><td>Pitfall</td><td>-3.37</td><td>-1.47</td><td>-155.97</td></tr><tr><td>Pong</td><td>21.0</td><td>20.95</td><td>17.33</td></tr><tr><td>Private Eye</td><td>1845.28</td><td>1252.01</td><td>100.0</td></tr><tr><td>Qbert</td><td>12036.5</td><td>14198.25</td><td>15804.72</td></tr><tr><td>Riverraid</td><td>12785.8</td><td>15622.2</td><td>10331.56</td></tr><tr><td>Road Runner</td><td>54768.0</td><td>53596.0</td><td>49029.74</td></tr><tr><td>Robotank</td><td>31.83</td><td>41.04</td><td>6.68</td></tr><tr><td>Seaquest</td><td>20458.6</td><td>24001.6</td><td>2274.06</td></tr><tr><td>Space Invaders</td><td>1890.8</td><td>2626.55</td><td>1466.01</td></tr><tr><td>Star Gunner</td><td>41684.0</td><td>47367.0</td><td>52466.84</td></tr><tr><td>Tennis</td><td>-11.63</td><td>-7.8</td><td>-20.49</td></tr><tr><td>Time Pilot</td><td>6153.0</td><td>6490.0</td><td>3816.38</td></tr><tr><td>Tutankham</td><td>208.61</td><td>200.76</td><td>132.67</td></tr><tr><td>Up N Down</td><td>19528.3</td><td>19827.3</td><td>8705.64</td></tr><tr><td>Venture</td><td>78.0</td><td>67.0</td><td>0.00</td></tr><tr><td>Video Pinball</td><td>343380.29</td><td>372564.11</td><td>35515.92</td></tr><tr><td>Wizard Of Wor</td><td>5451.0</td><td>5873.0</td><td>3657.65</td></tr><tr><td>Zaxxon</td><td>3901.0</td><td>3695.0</td><td>7956.05</td></tr><tr><td>Times Best</td><td>10</td><td>28</td><td>10</td></tr></table>

Comparison of Ensemble Voting, UCB Exploration, both trained with 40 million frames and A3C+ of Bellemare et al. (2016), trained with 200 million frames

Table content: <table><tr><td>Category</td><td colspan="5">Total Bootstrapped DQN Double DQN Ensemble Voting UCB-Exploration</td></tr><tr><td>Human Optimal</td><td>23</td><td>0</td><td>3</td><td>5</td><td>15</td></tr><tr><td>Score Explicit</td><td>8</td><td>0</td><td>2</td><td>1</td><td>5</td></tr><tr><td>Dense Reward</td><td>8</td><td>0</td><td>1</td><td>1</td><td>6</td></tr><tr><td>Sparse Reward</td><td>5</td><td>1</td><td>0</td><td>2</td><td>2</td></tr></table>

Comparison of each method across different game categories. The Atari games are separated into four categories: human optimal, score explicit, dense reward, and sparse reward. In each row, we present the number of games in this category, the total number of games where each algorithm achieves the optimal performance according to Table2. The game categories follow the taxonomy in Table1ofOstrovski et al. (2017) C APPROXIMATING BAYESIAN Q-LEARNING WITH Q-ENSEMBLESIn this section, we first derive a posterior update formula for the Q * -function under full exploration assumption and this formula turns out to depend on the transition Markov chain. Next, we approximate the posterior update with Q-ensembles {Q k } and demonstrate that the Bellman equation emerges as the approximate update rule for each Q k

Table content: <table/>

, we define the information gain from observing an additional transition τ n as H τt|τ1,...,τn-1 = D KL (p(Q * |τ 1 , . . . , τ n )||p(Q * |τ 1 , . . . , τ n-1 )) where p(Q * |τ 1 , . . . , τ n ) is the posterior distribution of Q * after observing a sequence of transitions (τ 1 , . . . , τ n ). The total information gain is Algorithm 1, does not maintain the posterior p, thus we cannot calculate (11) explicitly. Instead, inspired by Lakshminarayanan et al. (2016), we define an InfoGain exploration bonus that measures the disagreement among {Q k }. Note that H τ1,...,τ N + H(p(Q * |τ 1 , . . . , τ N )) = H(p(Q * )), where H(•) is the entropy. If H τ1,...,τ N is small, then the posterior distribution has high entropy and high residual information. Since {Q k } are approximate samples from the posterior, high entropy of the posterior leads to large discrepancy among {Q k }. Thus, the exploration bonus is monotonous with respect to the residual information in the posterior H(p(Q * |τ 1 . . . , τ N )). We first compute the Boltzmann distribution for each Q k

Table content: <table><tr><td>H τ1,...,τ N =</td><td>N n=1</td><td>H τn|τ1,...,τn-1 .</td><td>(11)</td></tr><tr><td>Our Ensemble Voting,</td><td/><td/><td/></tr></table>

Value function networks Q with K outputs {Q k } K k=1 . Hyperparameters T, λ, and ρ. 2: Let B be a replay buffer storing experience for training. 3: for each episode do Pick an action according to a t ∈ argmax a μ(s t , a) + λ • σ(s t , a)Add (s t , a t , r t + ρ • b T (s t ), s t+1 ) to replay buffer B Comparison of all algorithms in normalized curve. The normalized learning curve is calculated as follows: first, we normalize learning curves for all algorithms in the same game to the interval [0, 1]; next, average the normalized learning curve from all games for each algorithm.

Table content: <table><tr><td>0.8</td><td/><td/><td/><td colspan="3">Average Normalized Learning Curve</td><td/><td/><td/></tr><tr><td>0.7</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>0.6</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>0.5</td><td/><td/><td/><td/><td/><td/><td/><td/><td>ucb+infogain exploration, T=1</td></tr><tr><td>0.4</td><td/><td/><td/><td/><td/><td/><td/><td/><td>bootstrapped dqn ensemble voting</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>ucb exploration</td></tr><tr><td>0.3</td><td/><td/><td/><td/><td/><td/><td/><td/><td>double dqn</td></tr><tr><td>0.2</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>0.1</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>0.0</td><td>0.0</td><td>0.5</td><td>1.0</td><td>1.5</td><td>2.0 Frames</td><td>2.5</td><td>3.0</td><td>3.5</td><td>1e7 4.0</td></tr><tr><td colspan="7">Figure 3: D.1 PERFORMANCE OF UCB+INFOGAIN EXPLORATION</td><td/><td/><td/></tr><tr><td>4:</td><td colspan="5">Obtain initial state from environment s 0</td><td/><td/><td/><td/></tr><tr><td>5:</td><td colspan="5">for step t = 1, . . . until end of episode do</td><td/><td/><td/><td/></tr><tr><td>6:</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>7:</td><td colspan="9">Receive state s t+1 and reward r t from environment, having taken action a t</td></tr><tr><td>8:</td><td colspan="7">Calculate exploration bonus b T (s t ) according to (12)</td><td/><td/></tr><tr><td>9:</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>10:</td><td colspan="8">At learning interval, sample random minibatch and update {Q k }</td><td/></tr><tr><td>11:</td><td colspan="2">end for</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">12: end for</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2018):
 This paper paper uses an ensemble of networks to represent the uncertainty in deep reinforcement learning. The algorithm then chooses optimistically over the distribution induced by the ensemble. This leads to improved learning / exploration, notably better than the similar approach bootstrapped DQN. There are several things to like about this paper: - It is a clear paper, with a simple message and experiments that back up the claims. - The proposed algorithm is simple and could be practical in a lot of settings and even non-DQN variants. - It is interesting that Bootstrapped DQN gets such poor performance, this suggests that it is very important in the original paper https://arxiv.org/abs/1602.04621 that "ensemble voting" is applied to the test evaluation... (why do you think this is by the way, do you think it has something to do with the data being *more* off-policy / diverse under a TS vs UCB scheme?) On the other hand: - The novelty/scope of this work is somewhat limited... this is more likely (valuable) incremental work than a game-changer. - Something feels wrong/hacky/incomplete about just doing "ensemble" for uncertainty without bootstrapping/randomization... if we had access to more powerful optimization techniques then this certainly wouldn*t be sensible - I think that you should mention that you are heavily reliant on "random initialization + SGD/Adam + specific network architecture" to maintain this idea of uncertainty. For example, this wouldn*t work for linear value functions! - I think the original bootstrapped DQN used "ensemble voting" at test time, so maybe you should change the labels or the way this is introduced/discussed. It*s definitely very interesting that *essentially* the learning benefit is coming from ensembling (rather than "raw" bootstrapped DQN) and UCB still looks like it does better. - I*m not convinced that page 4 and the "Bayesian" derivation really add too much value to this paper... alternatively, maybe you could introduce the actual algorithm first (train K models in parallel) and then say "this is similar to particle filter" and add the mathematical derivation after, rather than as if it was some complex formula derived. If you want to reference some justification/theory for ensemble-based uncertainty approximation you might consider https://arxiv.org/pdf/1705.07347.pdf instead. - I think this paper might miss the point of the "bigger" problem of efficient exploration in RL... or even how to get "deep" exploration with deep RL. Yes this algorithm sees improvements across Atari, but it*s not clear why/if this is a step change versus simply increasing the amount of replay or tuning the learning rate. (Actually I do believe this algorithm can demonstrate deep exploration... but it looks like we*re not seeing the big improvements on the "sub-human" games you might hope.) Overall I do think this is a pretty good short paper/evaluation of UCB-ensembles on Atari. The scope/insight of the paper isn*t groundbreaking, but I think it delivers a clear short message on the Atari benchmark. Perhaps this will encourage people to dig deeper into some of these issues... I vote accept.