Optimistic Exploration with Backward Bootstrapped Bonus for Deep Reinforcement Learning
Authors: Chenjia Bai
Lingxiao Wang
Peng Liu
Zhaoran Wang
Jianye HAO
Yingnan Zhao
Venue:  (2021)
Keywords: optimistic exploration
backward bootstrapped bonus
posterior sampling
reinforcement learning

Abstract: Optimism in the face of uncertainty is a principled approach for provably efficient exploration for reinforcement learning in tabular and linear settings. However, such an approach is challenging in developing practical exploration algorithms for Deep Reinforcement Learning (DRL). To address this problem, we propose an Optimistic Exploration algorithm with Backward Bootstrapped Bonus (OEB3) for DRL by following these two principles. OEB3 is built on bootstrapped deep $Q$-learning, a non-parametric posterior sampling method for temporally-extended exploration. Based on such a temporally-extended exploration, we construct an UCB-bonus indicating the uncertainty of $Q$-functions. The UCB-bonus is further utilized to estimate an optimistic $Q$-value, which encourages the agent to explore the scarcely visited states and actions to reduce uncertainty. In the estimation of $Q$-function, we adopt an episodic backward update strategy to propagate the future uncertainty to the estimated $Q$-function consistently. Extensive evaluations show that OEB3 outperforms several state-of-the-art exploration approaches in Mnist maze and 49 Atari games.

Under review as a conference paper at ICLR 2021
OPTIMISTIC EXPLORATION WITH BACKWARD BOOTSTRAPPED BONUS FOR DEEP REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Optimism in the face of uncertainty a principled approach for provably efficient exploration for reinforcement learning in tabular and linear settings. However, such an approach is challenging in developing practical exploration algorithms for Deep Reinforcement Learning (DRL). To address this problem, we propose an Optimistic Exploration algorithm with Backward Bootstrapped Bonus (OEB3) for DRL by following these two principles. OEB3 is built on bootstrapped deep Q-learning, non-paraettric posterior sampling method for lemporally-extendee exploration. Based such remporally-extendee exploration, we construct UCB-bonus indicating the uncertainty
D-ffucctions. The UCB-bone is further utilized to estimate an optimistic Q-value, which encourages the agent to explore the scarcely visited states and actions to reduce uncertainty. the estimation Q-function, adopt episodic backward update strategy propagate the future uncertainty to the estimated Q-function consistently. Extensive evaluations show that OEB3 outperforms several state-of-the-art exploration approaches in MNIST maze and 49 Atari games.
INTRODUCTION
In Reinforcement learning (RI.) (Sutton & Barto 2018) formalized by the Markov decision process (MDP), an agent aims maximize the long-term reward by interacting with the unknown environment. The agent takes actions according to the knowledge of experiences, which leads to the fundamental problem of the exploration-exploiaatii current information or acquire more information by exploring the poorly understood states and actions. Exploring the environment may sacrifice immediate rewards but potentially improves future performance. The exploration strategy is crucial for the RL agent to find the optimal policy.
dilemma. An agent may choose the best decision given
The theoretical RL offers various provably efficient exploration methods in tabular and linear MDPs with the basic value iteration algorithm: least-squares value iteration (LSVV). Optimism in the face of uncertainty (Auer & Ortner 2007 Jin et al. 2018) is a principled approach. In tabular cases, the optimism-based methods incorporate upper confidence bound (UCB) into the value functions as bonuses and attain the optimal worst-case regret (Azar et al. 2017 Jaksch et al.) 2010 Dann & Brunskill 2015). Randomized value function based posterior sampling chooses actions according to the randomly sampled statistically plausible value functions and is known to achieve near-optimal worst-case and Bayesian regrets (Osband Van Roy, 2017 Russo 2019). Recently, the theoretical analyses in tabular cases are extended to linear MDP where the transition and the reward function are assumed to linear. In linear cases, optimistic I.VT (Jin et al., 2020) attains a near-optimal worst-case regret by using designed bonus, which is provably efficient. Randomized LSVI (Zanette ct al. 2020) also attains near-optimal worst-case regret.
Although the analyses in tabular and linear cases provide attractive approaches for efficient explo- ration, these principles are still challenging in developing a practical exploration algorithm for Deep Reinforcement Learning (DRL) (Mnih et al. 2015), which achieves human-level performance in large-scale tasks such as Atari games and robotic tasks. For example, in linear cases, the bonus in optimistic LSVI (Jin et al. 2020 and nontrivial noise in randomized L.SVI (Zanette et al. 2020

---

Under review as a conference paper at ICLR 2021
tailored to linear models (Abbasi-Yadkori et al. 2011). and are incompatible with practically powerful function approximations such as neural networks.
To address this problem, we propose the Optimistic Exploration algorithm with Backward Boot- strapped Bonus (OEB3) for DRL. OEB3 is an instantiation of optimistic LSVI (Jin et al. 2020) in DRL by using a ceneral-purposs. UCB-bonus provide an optimistic Q-value and randomized value function to perform temporally-extennt
exploration. We propose an JCB-bonus that repre- sents the disagreement of bootstrapped Q-functions (Osband et al.) 2016) measure the epistemic uncertainty of the unknown optimal value function. Q-value added by UCB-bonus becomes an optimistic Q" function that higher than Q for scarcely visited state-action pairs and remains close to Q for frequently visited ones. The optimistic Q function encourages the agent to explore the states and actions with high UCB-bonuses, signifying scarcely visited areas or meaningful events in completing task. We propose an extension of episodic backward update (Lee et al., 2019) to propagate the future uncertainty to the estimated action-value function consistently within an episode. The backward update also enables OEB3 to perform highly sample-efficient training.
Comparing to existing count-based and curiosity-driven exploration methods (Taiga et al. 2020), OEB3 has several benefits. (1) We utilize intrinsic rewards to produce optimistic value function and also take advantage of bootstrapped Q-learning to perform temporally-conan conssitentn exploration while existing methods do not combine these two principles. (2) The UCB-bone measures the disagreement of Q-values, which considers the long-term uncertainty in an episode rather than the single-step uncertainty used in most bonus-based methods (Pathak et al., 2019 BBurda al.. (019b). Meanwhile, the UCB-bonus is computed without introducing additional modules compared to bootstrapped DQN, (3) We provide a theoretical analysis showing that OEB3 has theoretical consistency with optimistic LSVI in linear cases. (4) Extensive evaluations show that OEB3 outperforms several state-of-the-art exploration approaches in MNIST maze and 49 Atari games.
BACKGROUND
In this section, we introduce bootstrapped DQN (Osband et al., 2016). which we utilize in OEB3 for empooarily-extender exploration. We further introduce optimistic LSVI (Jin et al. 2020). which we instantiate via DRL. and propose OFB3.
2.1 BOOTSTRAPPED DQN
We consider an episodic MDP represented as (S, A, where T E E is the episode length, S the state space, A is the action space, is the reward function, and P the unknown dynamics. In each timestep, the agent obtains the current state st, takes an action a, interacts with the environment, receives a reward Tt, and updates the next state s,+1- The action-value function Q* a,) := E, [- " (r:" represents the expected cumulative reward starting from state $t, taking action a;- and thereafter following policy (a,]s,) until the end of the episode. 7 E [0. 1) is the discount factor. The optimal value function Q' max, Q", and the optimal action a" arg max Q* Q²(ssa)) a).
Deep Q-Network (DQN) uses deep neural network with parameters to approximate the Qffunction. The loss function takes the form of L(0) = B[( ((s,, a,; [ (,, V2, St+1) DJ. where Yt F. + y max.' ((s++1 a'; 0-) is the target value, and 0 is the parameter of the target network. The agent accumulates experiences (st, Tt, 8(41) in replay buffer D and samples in training.
Bootstrapped DQN (Osband et al. 2016 2018) is a non- non-parametric posterior sampling method, which maintains K estimations of Q-values to represent the posterior distribution of the randomized value function. Bootstrapped DQN uses a multi-head network that contains a shared convolution network and K heads. Each head defines a Q² -uuncinn. Bootstrapped DQN diversifies different Q* by using different random initialization and individual target networks. The loss for training Q* is
L(0*)= E (ra + y max Q (5(411 a'; d':8"-) Q* (st, (si,a;;"))) {((st, Pt, 8(+1) D]. (1)
The k-th head Q* (s, a; 8*) is trained with its target network Q² (s,, a; 6k-). If k-th head is sampled at the start of an episode when interacting with the environment, the agent will follow Q* to choose actions in the whole episode, which provides temporally-consisten exploration for DRI.
2

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Optimistic LSVI in linear MDP
Initialize: A₂ < and wi f- 0
2: for episode m 0 to M - 1 do
3: Receive the initial state So
4: for step t = 0 to T do
5: Take action d; = arg A Qr(se, a) and observe 81-1-
6: end for
7:
for step t = to do
+ 9: Wt A, - of a of) max, (441(1T+1a))
8:
t Ae - -==
Q+(:.)) = min ol a - 1)))31 [T,T)
11: end for
12:
end for
2.2 OPTIMISTIC LSVI
Optimistic LSVI (Jin et al. 2020) uses an optimistic Q-value with LSVI in linear MDP. We denote the feature map of the state-action pair as Φ : 1 A RR, The transition kernel and reward function are assumed to be linear in ø. Optimistic LSVI shown in Algorithm@ consists of two parts. In the first part (line 6). the agent executes the policy according Qe for an episode. In the second part (line I the parameter wi of Q-function is updated in closed-form by following the regularized least-squares problem
We f- arg min arR
Em_orra (f] + max
Qt+1 - w (oT a7)] + A|[w||? aeA
where is the number of episodes, and r is the episodic index. The least-squares problem has the explicit solution W/ = A, "mroo o(a; az [r, (arff,o az) + max, Q1+1(11111 a)]] (line 9b, where A, the Gram matrix. Then the value function is estimated by Qr a) x w, @(s,a).
Optimistic LSVI uses a bonus alo(s, a) AA, A o)] (line 10 to measure the uncertainty of state-action pairs. We can intuitively consider u == (Ø A, x) as a pseudo count of state-action pair by projecting the total features that have observed (A₂) to the direction of the curresponding feature Φ Thus, the bonus 8/vī represents the uncertainty along the direction of ó. By adding the bonus Q-value, we obtain optimistic value function Q+, which serves as upper bound of Q to encourage exploration. The bonus in each step is propagated from the end of the episode by the backward update of Q-value (line 7 ITI, which follows the principle of dynamic programming. Theoretical analysis (Jin et al. 2020) shows that optimistic LSVI achieves a near-optimal worst-case regret of Ö 3V333333 with proper selections of a and X, where L is the total number of steps.
3 PROPOSED METHOD
Optimistic LSVI [Jin et al. 2020) provides an atractive approach for efficient exploration. Neverthe- less, developing a practical exploration algorithm for DRL is challenging, since (i) the UCB- cCB-bonus utilized by Optimistic I.STI tailored for linear MDPs, and (ii) optimistic LSVI utilizes backward update of Q-functions (line 11 in Alg. 11 aggregate uncertainty. To this end, propose the following approaches, which are the building blocks of OEB3.
We propose general-purpose UCB-bonus for optimistic exploration. More specifically, utilize bootstrapped DQN to construct a general-purpose UCB-bonus, which is theoretically consistent with optimistic LSVI for linear MDPs. We refer to Section 3.1 for the details.
We propose sample-efficient learning algorithm to integrate bootstrapped DQN and UCB-bonus into the backward update, which faithfully follows the principle dynamic programming. More specifically, we extend Episodic Backward Update (EBU) (Lee al. 2019) from ordinary Q- learning to bootstrapped Q-learning, which we abbreviate by BEBU (Bootstrapped EBU). BEBU allows sample-efii sample-efficient learning and fast propagation of the future uncertainty to the estimated Q- value consistently. We further propose OEB3 by combining BEBU and the UCB- bonus obtained via bootstrapped Qelearning. We refer Section 3.2 for the details.
3

---

Under review as a conference paper at ICLR 2021
g
14
14
(a)
Figure I: Illustration of UCB-bonus by using bootstrapped estimates in the regression task. The green dots represent 60 data points. (a) Regression curves of 20 neural networks. (b) Mean estimate (black) and uncertainty mcasurement (shadow). (c) The optimistic value (red) and mean value (black).
3.1
IN OEB3
Optimistic exploration uses an optimistic valuee function Q+ to incentive exploration by adding bonus term to the ordinary Q-value. Thus Q+ serves upper bound of ordinary Q. The bonus term represents the epistemic uncertainty that results from lacking experiences of the corresponding states and actions. In this paper, the bootstrapped Q-values (Q* k of the state-action pair (st, at) in bootstrapped DQN, which takes the following form,
UCB-bonus B(s,, a+) by measuring the disagreement of
K
B(s,, az) == ((Q
= K
(s) - Q(. (s))
(3)
where Q(s,, ax) is the mean of bootstrapped Q-values. The similar measurement was first used in Chen et al. (017). We further establish connection between the UCB-bonus defined in Eq. (3) and the bonus in optimistic-LSSI.
Theorem (Informal Version of Theorem 2 In linear function approximation, the UCB-bonus B(st, ar) in OEB3 is equivalent to the bonus-term [6] A, o,) /2 in optimistic-LSVV, where A + E p(x of (0( ag) + + and m is the current episode.
We refer Appendix A for the proof and detailed discussion. Implementing the UCB-bonus (ss,, 4.) defined in Eq. (3) in DRL is desirable for exploration for the following reasons.
Bootstrapped DQN a non-parametric posterior sampling method, which can be implemented via deep neural networks (Osband et al.) 2019).
The UCB-bonus B(st, az) defined in Eq. quantifies the epistemic uncertainty of a specific state-action pair adequately. More specifically, due the non-convexity nature of optimizing neural network and independent initialization, if (st, az) is scarcely visited, the (ss ae) obtained via bootstrapped DQN is high. Moreover, the UCB-bonus converges zero asymptotically as the sample size increases to infinity.
The UCB-bonus is computed in a batch when performing experience replay, which is more effi- cient than other optimistic methods that change the et al. 2017 Nikolov et al. 2019).
scheme in each timestep (Chen
The optimistic Q+ is obtained by summing up the UCB-bonus and the estimated Q-function, which takes the following form,
(+(,,, = Q a.) + aB((s, Ge)-
(4)
We use a simple regression task with neural networks to illustrate the proposed UCB-bonus, as shown in Figure We use 20 neural networks with the same network architecture to solve the same regression problem. Each network contains three residual blocks with two fully-connected layers each. According to (Osband et al. 2016), the difference between the outcome of fitting the neural networks a result different (g:(z) (x) 1,20 as shown in Figure It follows from Figure ((a) that the estimations (9,(x) [ behave similar in the region with rich observations, resulting in small disagreement of the estimations, but vary in the region with scarce observations, resulting in large disagreement of the estimations.
For single input æ, the networks yield different estimations
4

---

Under review as a conference paper at ICLR 2021
In Figure [(b) we illustrate the confidence bound of the regression results g(z) = (g((z)) and g(x) + (z)), where g(z) and δ (g)()) are the mean and standard deviation of the estimations. The standard deviation ( (z)) captures the epistemic uncertainty of regression results. Figure I(c) shows the optimistic estimation as g (x) = g(x) + ā (gg (z)) by adding the uncertainty measured by standard deviation. It can be seen that the optimistic estimation g+ is close g in the region with rich observations, and higher than ÿ in the region with scarce observations.
In DRL, the bootstrapped Q-functions 1Qt(s,, az) )= obtained by fitting the target Q-function per- form similarly (xx( ) in the regression task. A higher UCB-bonus (sst, az) == ā (Q* (s,, az) indicates a higher epistemic uncertainty of the action-value function with (st, aT). The estimated Q-function augmented with the UCB-bone yields Q+, which produces optimistic estimation for novel state-action pairs and behaves similar to the target Q-function in areas that are well explored by the agent. Hence, the optimistic extimation Q+ incentives the agent to explore the potentially informative states and actions efficiently.
3.2 UNCERTAINTY BACKWARD IN OEB3
There are two major reasons for updating the action-value function through Bootstrapped Episodic Backward Update (BEBU) in OEB3.
The backward propagation utilizes complete trajectory from the replay buffer. Such an approach allows OEB3 to infer the long-term effect of decision making from the replay buffer. In contrast, DQN and Bootstrapped DQN utilize the replay buffer by random sampling one-step transitions, which loses the information containing such a long-term effect (Lee et al. 2019).
The backward propagation is required to propagate the future uncertainty the estimated action- value function consistently via UCB- UCBB-bonu within an episode. For instance, let ty > t1 be the indices of two steps in an episode. If the update of Qt, occurs after the update of Qr, within an episode, then it can occur that the uncertainty propagated into Qt, is not consistent with the uncertainty that Qt contains.
To integrate the UCB-bonus into bootstrapped Q-learning, we propose novel Q-target in update by adding the bonus term in both the immediate reward and the next-Q value. The proposed Q-target needs to be suitable for BEBU in training. Formally, the Q-target for updating Q is defined
u/ = (r) + a B(s,
ax; 0]] + >1@* (#141, ('""")"""0="""""""" + a2 a2laaaaay B* (s:+), (5)
where a' arg max, Q² ($141, a; 8²= The choice of a' is determined by the target Q-value without considering the bonus. The immediate reward is added by B(st, ar; 9) with factor a1, where the bonus 1 is computed by bootstrapped Q-network with parameter 6. The next-Q value is added by 0-) with factor a2, where the bonus 8h is computed by the target network
1 fa' 1 with parameter 0- We assign different bonus 8 of next-Q value to different heads, since the choice of action a' are different among the heads. Mcanwhile, we assign the same bonus B of immediate reward for all the heads. We introduce the indicator function La'saet4 suit the backward update of Q-values. More specifically, the (-th step, the action-value funetion Q* is updated optimistically at the state-action pair (s++1, 0(+1) ) due to the backward update. Thus, we ignore the bonus of next-Q value in the update of Q* when a' is equal to 0,+1-
We use an example to explain the process of backward update. We store and sample the experiences in episodes, and perform update in episodes rather than uniformly sampled transitions. We consider an episode containing three time steps. (so, ao) (1), + (32, a2). We thus update the Q-value in the head & in the backward manner, namely ((s2, a2) - Q(11 01) Q(su, an) from the end of the episode. We describe the process as follows.
1. First, we update ((32, 02) t r(s2, a2) + ai B(s,, oz). Note that in the last time step, we do not need consider the next-Q value.
2. Then, Q(s1, + [r(s1, a1) + ai B(s) el)l + [Q(52, a') + a2 B(sg, a')] by following Eq. (5), where a' arg max, Q(2 a). Since ((52, 02) is updated optimistically in step [ we
ignore the bonus-term B in next-Q value when a' ag. The UCB-bonus is augmented in update by adding B and i to the immediate reward and next-Q value, respectively.
5

---

Under review as a conference paper at ICLR 2021
3. The update of (sa ao) follows the same principle. The optimistic Q-value is Q(su, an) t (r(8o 0n) + on (s0: ao) [Q(s1, a') + a' ((s d'), where a' = arg max, ())1;a).
In practice, the episodic update typically leads to instability in DRL due to the strong correlation in con- secutive transitions. Hence, we propose a diffusion factor 3 [0. 1] in BEBU to prevent instability as in Lee et al. (2019). The Q-value is therefore computed the weighted sum of the current value and the back-propagated estimation scaled with factor B. We consider an episodic experience that contains T transitions, denoted by E (S, A. R. S'), where S { ST-1 -)) }. A = (ag...... aT-1)
R , rT-1) ,T-1 and S' {(11.... s1......TT.. We initialize a Q-table Q E [gxx|A)xx XT by Q(=00) to store the next Q-values of all the next states S' and valid actions for K heads. We initialize y E RxT to store the Q-target for K heads and T steps. We use bootstrapped Q-network with parameters 0 to compute the bonus B = [B(su, au).... B( (1$T-1,07-1) ar-1) for immediate reward, and use the target network with parameters 0- to compute bonus B [B* (s1, B B d for next-Q value in each head, where af arg max, Q* a; 0*-). The bonus vector B E IR is the same for all Q-heads, while B E R contains different values for different heads because the choices of of are different.
In the training of head k. we initialize the Q-target in the last step by yk,, - We then perform recursive backward update get all Q-target values. The elements of [K; ac+1 4 for step in head k is updated by using its corresponding Q-target ylk, t +1 1] with the diffusion factor as follows.
[ a++1; 4] + Bylk, t + 1] (1 B) at+
Then, we update ylk, f) in the previous time step based on the newly updated t-th column of Q[Ki as follows,
[k, (R. + +.) + 7 (a(k, a', .] + 02 122 aa B(k:
where a' arg max, [k,, a, t]. In practice, we construct matrix À arg max, al E RxxT to gather all the actions a' that correspond to the nexi-Q. We then construct a mask matrix M E R xT to store the information whether A is identical to the executed action in the corresponding timestep not. The bonus of next-Q Q is the element- wise product of M and B with factor az After the backward update, we compute the Q-value of (S, A) as Q QS, A; A: E R The loss function takes the form of T.(0) TE [(y (),, (t, i',, 8(+1) E F,, E D), where the episodic experience E is sampled from replay buffer to perform gradient descent. The gradient of all heads can be computed simultancously via BEBU. We refer the full algorithm of OEB3 to Appendix B
The theory in optimistic-LSVI requires a strong linear assumption in the transition dynamics. To make works empirically, we make several adjustments in the implementation details. First, in each training step of optimistic-LSVI all historical samples are utilized to update the weight of Q-function and calculate the confidence bonus. While in OEB3, we use samples from a batch of episodic trajectories from the replay buffer in each training step. Such difference in implementation imposed to achieve computational efficiency. Second, in OEB3, the target-network has a relatively low update frequency, whereas, in Optimistic LSVI, the target Q function is updated in each iteration. Such implementation techniques are commonly used in most existing (off-policy) DRL algorithms.
We use BEBU to propagate the future uncertainty in episode, which is extension of EBU (Lee) ett al., 2019). Compared to EBU, BEBU requires extra tensors to store the UCB-bonus for immediate reward and next- Q value, which are integrated to propagate uncertainties. Meanwhile, integrating uncertainty into BEBU needs special design by using the mask. The previous works do not propagate the future uncertainty and, therefore, does not capture the core benefit of utilizing UCB-bonus for the exploration of MDPs. We highlight that OEB3 propagates future uncertainty in a cime-consistent manner based on BEBU, which exploits the theoretical analysis established by Jin et al. (2020). The wack update significantly improves the sample-efficiency by allowing bonuses and delayed rewards to propagate through transitions of the sampled episode, which we demonstrate in the sequel.
4 RELATED WORK
One practical principle for exploration in DRL is maintaining epistemic uncertainty of action- value functions and learning to reduce the uncertainty. Epistemic uncertainty appears due the missing

---

Under review as a conference paper at ICLR 2021
knowledge of the environment, and disappears with the progress of exploration. Bootstrapped DQN (Osband et al.) 2016; 2018) samples Q-values from the randomized value function to encourage exploration through Thompson sampling. Chen et al.] (2017) proposes to the Saandad-devvaatoon of bootstrapped Q-functions to measure the uncertainty. While the uncertainty measurement is similar to that of OEB3, our method is different from Chen et al. (2017) in the following aspects. First, our approach propagates the uncertainty through time by the backward update, which allows for deep exploration for the MDPs. Second, Chen et al. (2017) does not use the bonus in the update of Q-functions. The bonus is computed when taking the actions. Third, we establish a theoretical connection between the UCB-bonus and the bonus in optimistic-LSVI SUNRISE (Lee et al.. 2020) extends Chen et a (0177) to continuous control through confidence reward and weighted Bellman backup. Information-Dires
Sampling (IDS) (Nikolov et al. 2019) is based on bootstrapped DQN, and chooses actions by balancing the instantaneous regret and information gain. OAC (Ciosek et al. 2019) uses two Q- -enttworks to get lower and upper bounds of Q-value to perform exploration in continuous control tasks. These methods seek to estimate the epistemic uncertainty and choose the optimistic actions. In contrast, we use the uncertainty of value function to construct intrinsic rewards and perform backward update, which propagates future uncertainty to the estimated Q-value.
Uncertainty Bellman Equation (UBE) and Exploration (O'Donoghue et al. 2018 proposes an upper bound on the variance of the posterior of the Q-values, which are further utilized for optimism in exploration. UBE uses posterior sampling for exploration, whereas OEB3 uses optimism for exploration. Bayesian-DQN (Azizzadenesheli et al., 2018) modifies the linear regression of the last layer in Q-network and uses Bayesian Linear Regression (BLR) instead, which estimates an posterior of the Q-function. These methods use parametric distributions to describe the posterior while OEB3 uses non non-parametric method to estimate the confidence bonus. UBE and BLR require inverting a large matrix in training. Previous methods also utilize the epistemic uncertainty of dynamics through Bayesian posterior (Ratzlaff et al., (020) and ensembles (Pathak et al. 2019). Nevertheless, these works consider single-step uncertainty, while we consider the long-term uncertainty in an episode.
To measure the novelty of states for constructing count- based intrinsic rewards, previous methods use density model (Bellemare et al. 2016; Ostrovski et al. 2017), static hashing (Tang et al. 2017;
Choi et al. 2019 Rashid et al. 2020)). episodic curiosity (Savinov et al. [2019] Badia al.
2020),
representation changes (Raileanu & Rocktäschel 2020), curiosity-bottleneee
(Kim et al. 2019b),
information gain (Houthooft et al. (016) and RND (Burda et al. 2019b). The curiosity driven
exploration based on prediction-eee
of environment models such as ICM (Pathak et al.] 2017]
Burda al. (019a). EMI (Kim et al., (209a),, variational dynamics (Bai et al. (022))00))) and learning progress (Kim et al. 2020) enable the agents to explore in a self-supervised manner. According Taiga al. (2020), although bonus-based methods show promising results in hard exploration tasks like Montezuma's 's Revenge, they do not perform well on other Atari games. Mcanwhile, NoisyNet (Fortu nato et al. 2018) performs significantly better than popular bonus-based methods evaluated by the whole Atari suit. TTiga et al. (2020) suggests that the real pace of progress in exploration may have been obfuscated by good results on several hard exploration games. We follow this principle and evaluate OEB3 on the whole Atari suit with 49 games.
Beyond model-free methods, model-based RL also uses optimism for planning and exploration (Nix & Weigend 1994). Model-assisted RI. (Kalweit& & Boedecker (017) uses ensembles to make use of artificial data only in cases of high uncertainty. [Bckman et al. (2018) uses ensemble dynamics and BBakknmn Q-functions to model rollouts when they do not cause large errors. Planning to explore (Sekar
ct al. 2020) seeks out future uncertainty by integrating uncertainty to Dreamer (Hafner et al., 2020).
Ready Policy One (Ball et a (0200) optimizes policies for both reward and model uncertainty reduction.
RL (Pacchiano et al. 2020) uses statistical bootstrap to generalize the optimistic posterior sampling (Agrawal & Jia 2017) DRL. Hallucinated UCRL (Curi al., 2020)
reduces optimistic exploration to exploitation by enlarging the control space. The model-based RL
needs to estimate the posterior of dynamics, while OEB3 relies on the posterior of Q-functions.
EXPERIMENTAL RESULTS
5.1 ENVIRONMENTAL SETUP
We evaluate the algorithms in high-dimensional mmage-based tasks, including MNIST Maze and 49 Atari games. We refer Appendix for the experiments on MNIST Maze, and discuss the experiments
7

---

Under review as a conference paper at ICLR 2021
Atari games in the sequel. Comparing OEB3 with bootstrapped DQN-based baselines directly incur performance bias, since OEB3 uses backward update for training, which different from bootstrapped DQN. To this end, re-implement all bootstrapped DQN-based baselines with BEBU- based update. In our experiments, we compare the following methods: (1) OEB3. The proposed optimistic exploration method with UCB-bonus and backward update in this work. (2) BEBU. The re-implementation of bootstrapped DQN (Osband et al.) 2016) with BEBU-based training. (3) BEBU-UCB. BEBU with optimistic action-selection according the upper bound of Q (Chen
et al., 2017). (4) BEBU-IDS. Integrating homoscedastie IDS (Nikolov et al. 2019) into BEBU without distributional RL. We refer Appendix B for the algorithmic comparison between all methods.
According to EBU (Lee al. 2019), the backward update is significantly more sample-efficient than ordinary Q-learning by using 20M training frames to achieve the mean human-normalized score of DQN with 200M training frames. We follow this setting by training BEBU-based methods with 20M frames. In experiments, 20M frames in OEB3 is sufficient produce strong empirical results and achieve competitive results with several baselines in 200M frames. After training, an ensemble policy by majority vote of Q-heads is used for 30 no-op evaluation. The majority- combines all the heads into a single ensemble policy, which follows the same evaluation method as in Osband et al. 2016). We use the popular perform the comparison. In tackling Atari games, Osband et al. (2016) observes that the bootstrapping does not contribute much in performance. Empirically, Bootstrapped DQN uses the same samples to train all Q-heads in each training step. This empirical simplification is also adopted Syyhnn et al. (017)): Osband et al. (2018); Nikolov et al. (2019). We use such an simplification for OEB3 and all Bootstrapped DQN-based baselines.
score ScoreAgeus ScarCRamlom.
[Scoretuman: SSooeeaadon to
We set 01 and 02 to the same value 0.5 10-4 4 by searching coarsely. We diffusion factor 3 = 0.5 for all methods by following Lee al. (2019). OEB3 quires much less training time than BEBU- UCB and BEBU-IDS because the con- fidence bound used in BEBU-UCB and regret-information ratio used BEBU-IDS are both computed in each time step when interacting with the environment, while the UCB-bonuses in OEB3 calculated in episodes when performing batch training. The number of environmental interaction steps L, are typically set to much larger than the number of training steps T.2 (e.g., in DQN, L1 &e 4L2). We refer to Ap-
2.0
180
200
305
400
503
605
705
300
Epicode
Figure 2: Visualizing UCB-bonus in Breakout
pendix D for the detailed specifications. The code available at htttttss//blt..y/3333//
5.2 RESULT COMPARISON
In Table we additionally report the performance of DQN (Mnih al. 2015). NoisyNet (Fortunato et al.) 2018). Bootstrapped DQN (Osband et al. 2016), and IDS (Nikolov et al. 2019) in 200M
training frames. We choose NoisyNet baseline since is shown (Taiga al.) (020) to perform
substantially better than existing bonus-based methods evaluated by the whole Atari suit (instead of
several hard exploration games), including CTS-counts (Bellemare al. (016)). PixelCNN-coure
(Ostrovski et al. 2017), RND (Burda et al. 2019b), and ICM (Pathak et al. 2017). UBE (O'Donoghue)
Table Summary of human-normalized scores in Atari games. BEBU, BEBU-UCB, BEBU-IDS and OFB3 are trained for 20M frames with RTX-2080TI GPU for 5 random seeds.
Frames
200M
20M
DQN
UBE
BootDQN
NoisyNet BootDQN-IDS
BEBU
BEBU-UCB BEBU-IDS
OEB3
Mean
241%
440%
553%
651%
757 %
553%
610%
622%
765 %
Median
93%
126%
139%
172%
187 %
36%
38%
44%
50%
8

---

Under review as a conference paper at ICLR 2021
et al. 2018 uses a parametric method to describe the posterior of Q-values, which are utilized for optimism in exploration. We also use UBE as a baseline. According to Table !I BootDQN-IDS performs better than UBE, BootDQN, and NoisyNet. Thus, BootDQN-IDS outperforms existing bonus-based exploration methods that perform worse than NoisyNet. We re-implement BootDQN- IDS with BEBU-based update and observe that OEB3 outperforms BEBU-IDS in both mean and medium scores, thus outperforming the bonus-based methods that performs worse than NoisyNet. We report the raw scores Appendix F Moreover, Appendix G shows that OEB3 outperforms BEBU, BEBU-UCB, and BEBU-IDS in 36, 34, and 35 games out of all 49 games, respectively.
To understand the proposed UCB-bonus, we use a trained OEB3 agent to interact with the environment for an episode in Break- out and record the UCB-bonuses each step. The curve in Figure
mean UCB-bonus
2 shows the UCB- UCB-bonuses of the subsampled steps in the episode. We choose 8 spikes with high UCB-bonuses and visualize the corresponding frames. The events in spikes cor- respond to scarcely visited areas or crucial events, which are important for the agent to obtain rewards: digging a tunnel (1), throwing the ball to the top of bricks (2.3), rebounding the ball (4,5,6), eliminating all bricks and starting new round (7,8). We provide more examples of visualization in Appendix further record the the mean of UCB-bonus of the training batch in the learning process, which is shown in Figure 3 The UCB-bonin is low at the beginning since the networks are randomly initialized. When the agent starts to explore the environment, the mean UCB-bonus rises rapidly to incentive exploration. As more experiences of states and actions are gathered, the mean UCB-bonus reduces gradually, which indicates that the bootstrapped value func- tions concentrate around the optimal value and the epistemic uncertainty decreases. Nevertheless, the UCB-bonuses are relatively high at scarcely visited areas or crucial events, according to Figure 2 which motivates the agent to enhance exploration at the corresponding events.
8-
0
SM
10M
15M
Z0M
Training Frames
Figure 3: The change of mean UCB-bonus in Breakout
F We
We conduct an ablation study to better comprehend the importance of backward update and bonus term in OEB3. We refer to Table for the outcomes. We observe that:
Table 2: Ablation Study
Backward Bonus
Qbert
SpaceInvaders Freeway
OEB3
UCB
4275.0
904.9
32.1
BooDDON-UCB
UCB
3284.7
731.8
20.5
BEBU
3588.4
814.4
21.5
(1) when we use the ordinary up- date strategy by sampling transi- tions instead of episodes in train-
BooiDQN
2206.8
649.5
18.3
BEBU-RND
RND
3702.5
832.7
22.6
ing, OEB3 reduces to BootDQN-UCB with significant performance loss. Hence, the backward update crucial in OEB3 for sample-efficies training. (2) When the UCB-bonus is set to 0, OEB3 reduces to BEBU. We observe that OEB3 outperforms BEBU in 36 out of all 49 games. (3) When both the backward update and UCB-bonus are removed, OEB3 reduces to standard BootDQN, which performs poorly in 20M training frames. (4) To illustrate the effect of -CB-bbonus, we substitute UCB-bonus with the popular RND-bonus (Burda et al. 2019b). Specifically, we use an independent RND network to generate RND-bonus for each state in training. The RND-bonus is added to both the immediate reward and next-Q. The result shows that UCB-bonus outperforms RND-bonus without introducing additional modules compared to BootDQN.
6 CONCLUSION
In this work, we propose OEB3, which has theorctical underpinnings from optimistic LSVI. We to capture the epistemic uncertainty of Q-function and an BEBU algorithm for sample-efficien training. We demonstrate OEB3 empirically by solving MNIST maze and Atari games and show that OEB3 outperforms several strong baselines. The visualizations suggest that high UCB-bonus corresponds to informative experiences for exploration. As far as we are concerned, our work seems to establish the first empirical attempt of uncertainty propagation in deep RL. Moreover, observe that such a connection between theoretical analysis and practical algorithm provides relatively strong empirical performance in Atari games and outperforms several strong baselines, which hopefully gives useful insights combining theory and practice to the community.
propose

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret
bounds. In Advances in Neural Information Processing Systems, pp. 1184-1194, 2017.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems, pp. 49-56, 2007.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. International Conference on Machine Learning, pp. 263-272, 2017.
Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep g-networks. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martin Arjovsky, Alexander Pritzel, Andrew Bolt, and Charles Blundell. Never give up: Learning directed exploration strategies. In International Conference on Learning Reprexentations, 2020.
Chenjia Bai, Peng Liu, Zhaoran Wang, Kaiyu Liu, Lingxiao Wang, and Yingman Zhao. Varia- tional dynamic for self-supervised exploration in deep reinforcement learning. arXiv preprint arXiv:2010.0875: 2020.
Philip Ball, Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Ready policy one: World building through active learning. arXiv preprint arXiv:2002.02699, 2020.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Marc G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. International Conference on Machine Learning, pp. 449, 2017.
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Advances in Neural Information Processing Systems, pp. 8224-8234, 2018.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large- scale study of curiosity-drive -driven learning. International Conference on Learning Representations, 2019a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019b.
Richard Y Chen, Szymon Sidor, Pieter Abbeel, and John Schulman. Ucb exploration via q-ensembles. arXiv preprint 000i::1700.0155000 2017.
Jongwook Choi, Yijie Guo, Marein Moczulski, Junhyuk Oh, Neal Wu, Mohammad Norouzi, and Honglak Lee. Contingency-aware exploration in reinforcement learning. In International Confer- ence on Learning Representations, 2019.
Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann. Better exploration with optimistic actor critic. In Advances in Neural Information Processing Systems, pp. 1785-1796, 2019.
Sebastian Curi, Felix Berkenkamp, and Andreas Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. Advances in Neural Information Processing Systems, 33, 2020.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed- horizon reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2318-2826,, 2015.
10

---

Under review as a conference paper at ICLR 2021
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, emi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In International Conference Learning Representations, 2018.
Danijar Hafner, Timothy Lillicrap. Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. In International Conference Learning Representations, 2020.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems, pp. 1109-11111 2016.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):156331600 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4863-4873, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of Thirty Third Conference on Learning Theory, pp. 2137-2143, 2020.
Gabriel Kalweit and Joschka Boedecker. Uncertainty-driven imagination for continuous deep reinforcement learning. In Conference on Robot Learning, pp. 195- 2017.
Hyoungseok Kim, Jaekyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi: Exploration with mutual information. In International Conference on Machine Learning, pp. 3360-3369, 2019a.
Kun Ho Kim, Megumi Sano, Julian De Freitas, Nick Haber, and Daniel Yamins. Active world model learning in agent-rich environments with progress curiosity. In International Conference Machine Learning, 2020.
Youngjin Kim, Wontae Nam, Hyunwoo Kim, Ji-Hoon Kim, and Gunhee Kim. Curiosity-bottlene Exploration by distilling task-specific novelty. In International Conference on Machine Learning. pp. 317933373333 3388, 2019b.
Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning. arXiv preprint arXiv:2007.04938, 2020.
Su Young Lee, Choi Sungik, and Sae- Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. In Advances in Neural Information Processing Systems, pp. 21 2110-2119, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A, Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning.
Nature, 518:529 5333, 2015.
Nikolay Nikolov, Johannes Kirschner, Felix Berkenkamp, and Andreas Krause. Information-direeted exploration for deep reinforcement learning. In International Conference on Learning Representa- tions, 2019.
David Nix and Andreas Weigend. Estimating the mean and variance of the target probability distribution. In Proceedings of 1994 ieee international conference neural networks (ICNN'94) 94),
volume 1, pp. 55-60. IEEE, 1994.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pp. 2701-2710, 2017.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pp. 4036-4034, 2016.

---

Under review as a conference paper at ICLR 2021
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, pp. 8617-8629, 2018.
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
Georg Ostrovski, Marc G Bellemare, Aäron van den Oord, and Rémi Munos. Count-based exploration with neural density models. In International Conference on Machine Learning, pp. 2721-2730, 2017.
Brendan O' D'Donoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pp. 3836-3845, 2018.
Aldo Pacchiano, Philip Ball, Jack Parker-Holder Krzysztof Choromanski, and Stephen Roberts. On optimism in model-based reinforcement learning. arXiv preprint arXiv:2006. 11911, 2020.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by sulf-supe prediction. In International Conference on Machine Learning, pp. 2778-2787, 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Sulf-super exploration via disagreement. 2019.
In International Conference on Machine Learning, pp.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally- generated environments. In International Conference on Learming Representations, 2020.
Tabish Rashid, Bei Peng, Wendelin Boehmer, and Shimon Whiteson. Optimistic exploration even with a pessimistic initialisation. In International Conference on Learning Representations, 2020.
Neale Ratzlaff, Qinxun Bai, Li Fuxin, and Wei Xu. Implicit generative modeling for efficient exploration. In International Conference Machine Learning. 2020.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Advances in Neural Information Processing Systems, pp. 14410-14420, 2019.
Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Mare Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability. In International Conference on Learning Representutions, 2019.
Ramanan Sekar, Oleh Rybkin, Kostas Danilldiss, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-super world models. In International Conference on Machine Learning, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Adrien Ali Taiga, William Fedus, Marlos C Machado, Aaron Courville, and Mare G Bellemare. On bonus based exploration methods in the arcade learning environment. In International Conference on Learning Representations, 2020.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip Tururkk, and Pieter Abbeel. Exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pp. 2753-2762, 2017.
Mike West. Outlier models and prior distributions in bayesian linear regression. Journal of the Royal Statistical Society: Series B (Methodological), 46(3):431-433 1984.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. International Conference on Artificial Intelligence and Statistics, pp. 1954 1964, 2020.
12

---

Under review as a conference paper at ICLR 2021
A UCB BONUS IN OEB3
Recall that we consider the following regularized least-square problem,
We < arg min
Σ (rolsT,,0 a.)) + max Q4+1 a) w [[s] + 1|wl1 WERd
(8)
aEA
In the sequel, we consider Bayesian linear regression perspective of (8) that captures the intuition behind the UCB-bonus in OEB3. Our objective is to approximate the action-value function Qe via fitting the parameter w; such that
w ((8,, a.) = (e a.) + max Q++1 ($++1, aeA
where Q4+1 is given. We assume that we are given a Gaussian prior the initial parameter (0,1/AA). With a slight abuse of notation, we denote by we the Bayesian posterior of the parameter w given the set of independent observations Dn, = {(T a, (111) define the following noise with respect the least-square problem in (8)
We further
(St, 04) + max Qu+1($t+1, a) Φ 0c))
acAA
where (st, Oe, S1+1) 1 follows the distribution of trajectory. The following theorem justifies the UCB- bonus in OEB3 under the Bayesian linear regression perspective.
Theorem 2 (Formal Version of Theorem [p. We assume that follows the standard Gaussian distribution (O, given the state-action pair (st, and the parameter w. Let follows the Gaussian prior N (0, I/X). We define
A Σ plot at (o(T,, at) I
(10)
It then holds for the posterior of given the set of independent observations D... of, .6 that
Var(ø at) wi) = Var Var(Qu((s,, ai)) = p(s),)) TA, A, ((s, V(s,,a) E xSx. A. Here we denote by Qi = W. do the estimated action-valts function.
Proof. The proof follows the standard analysis of Bayesian linear regression. See, e.g., West 1984) for a detailed analysis. denote the target of the linear regression in (8 by
Ut rt (st, a2) + max Q++1 ($1+1,
aEA
By the assumption that follows the standard Gaussian distribution, we obtain that Ye (8t, (z), NNw (T((,(((s))) 1)),
(11)
Recall that we have the prior distribution w N/00, I/A). Our objective is compute the posterior density Wi = w Dm, where Dm = {(5T, a7 (111) is the set of observations. holds from Bayes rule that
log p( w Dm.) = log p(w) + log w) + Const.,
(12)
where p(-) denote the probability density function of the respective distributions. Plugging 11 and the probability density function of Gaussian distribution into (12) yields
m
logp(w) (Dn) = -|/ / > I dbss at) vž 1/11 + Const. +onst..
= (w - 14) A (w -44/22 + Const.,
(13)
where define
Pr A
(55 aF)
A Σ ol (l))) at) +A.I.
Thus, by 13) we obtain that we Dm N(H,, then holds for all (st, at) S that Var Var(( a wx) Var Qe(st, ar)) ((),, - (1))
which concludes the proof of Theorem 2
13

---

Under review as a conference paper at ICLR 2021
B ALGORITHMIC DESCRIPTION
Algorithm 2 OEB3 in DRL
1: Initialize: replay buffer D, bootstrapped Q-network (:: 0) and target network Q=: 0
2: Initialize: total training frames 20M, current frame
3: while h < H do
4: Pick bootstrapped Q-function to act by sampling k Unif(1,..., K}
5: Reset the environment and receive the initial state
6:
for step 1 = 0 to Terminal do
7:
With e-greedy choose a; arg max, (*(s;, a)
8:
Take action and observe r; and 814-1, then save the transition in buffer D if h % training frequency 0 then
9:
10:
Sample an episodic experience E = R,, with length T from D Initialize Q-table Q
11:
E R Rx]A|XT by the target Q-network Compute the UCB-bonus for immediate reward for all steps to construct E B Compute the action matrix Á arg max, a, R xT gather all a' of next-Q
14:
Compute the UCB-bonus for next-Q for all heads and all steps to construct B E R xT Compute the mask matrix M R xT where M t = [
15:
16:
Initialize target table E R xT to zeros, and set yl T - = 1
+ aT-
for t = T 2 to 0 do
18:
Q1,0 4 + Byl 1 + 1| + (1 0441
19:
yl.4 - (R, on B.) + (Q a', 0z M B(: where a' = =A[44]
20:
end for
21:
Compute the Q-value of (S, A) for all heads Q QSS, E RxxT Perform gradient descent step on (y - Q)² with respect to 0
22:
23:
end if
24:
Every C' steps reset - + 0
25:
h < h
26:
end for
end while
We summarize the closely related works in Table 3
Table 3: Algorithmic Comparison of Related Works
Bonus Poste-
Update Method
Uncertainty Characterization
rior Variance
EBU (Lee el al. 2019)
backward update
Bootstrapped DQN (Osband al. 2016)
bootstrapped
on on-trajectory update
bootstrapped distribution
BEBU (base of our work)
bootstrapped closed form bootstrapped closed form
backward update backward update backward update
bootstrapped distribution optimism
Optimistic L.VVI (Jin et al.
2020
OEB3 (ours)
optimism
UBE (0 Donoghue et al. 2018)
on-trajectory update
posterior sampling
Bayesian- DQN (Azizzaennehelli
closed form
on-trajectory update
posterior sampling
2018
14

---

Under review as a conference paper at ICLR 2021
Algorithm BEBU BEBU-UCB & BEBU-IDS
1: Input: Algorithm Type (BEBU, BEBU-UCB, or BEBU-IDS)
2: Initialize: replay buffer D, bootstrapped Q-network Q 8) and target network Q(=: 0
3: Initialize: total training frames H = 20M, current frame h =
4: while h < H do
5: Pick bootstrapped Q-function to act by sampling k ~ Unif(1.....
6: Reset the environment and receive the initial state 80
7: for step 0 to Terminal do
8:
Algorithm type is BEBU then
9:
With e-greedy choose a, arg max, Q" a) else if Algorithm type is BEBU-UCB then
10:
11:
With e-greedy choose 0; arg max, Q8; a) (Q(ss, a))), where as)
K +K (*s, a,) and (Q a,)) v (Q" Q(8, a,)) are the mean and standard deviation of the bootstrapped Q-estimates
12:
else if Algorithm type BEBU-IDS then
With e-greedy choose = arg min, A.(,,,)² T(s..a) by following the regret-information
13:
ratio, where Á.(s;,
max.'eA (s; a') - (,(s,, a:) is the expected regret, and [s az), (s, a,)] is the confidence interval. In particular, u, a.) = (s,, a,) +
Aids (Q((s, a,)) and 4(s,, ((s,, a.) A aQQ a,)). I(s;, a,) log(1
o(Q(s,a))) /p") + fids measures the uncertainty, where p and eids are constants.
14:
else
15:
Algorithm type error.
end if
17:
Take action and observe r; and 8 then save the transition in buffer D h % training frequency then R, S') with length T from D A by the target Q-network
19:
Sample an episodic experience E = A, R, Initialize Q-table Q
20:
21:
Compute the action matrix À arg max,, Q i a | E RxT gather all d' of next-Q Initialize target table y E R X
22:
to zeros, and set yl T - = RT-1 + a Br-1
23:
for / T 2 to 0 do
24:
Q 1) + By L+ + - 3) 4:41.
25:
yl. + R. + QQ a', where a' = A(.
end for
27:
Compute the Q-value of (S, A) for all heads Q Q(S A;0) E R Perform gradient descent step on (y Q)2 with respect to 0
28:
29:
end if
30:
Every C steps reset 0- +- 0
31:
h < h
32:
end for
33:
end while
15

---

Under review as a conference paper at ICLR 2021
C
ADDITIONAL EXPERIMENT: MNIST MAZE
BE9I: BIBLICS BEBLLCCS
SERU DEDJANZ REDLANC
D2BL IDS BTOLL JACE
Pel000 arith
408.
200
200K
123
246K
166K
2006
405
606
301
1000
120K
1468
200
408
905
106.
100K
1330
140K
LOX
100K 2006
(a) Wall density of 30%
(b) Wall density of 40%
(c) Wall density of 50%
Figure 4: Results of 200K steps training of MNIST maze with different wall-density setup.
with randomly placed walls to evaluate our method. The agent starts from the initial position (0. 0) in the upper-left of the maze and aims to reach the goal position (9, 9) in the bottom-right. The state of position (i,j) is repre- sented by stacking two randomly sampled images with label i and j from the MNIST dataset. When the agent steps to new position, the state represen- tation is reconstructed by sampling images. Hence stepping to the
We 10 10 MNIST
D
5
35-35
DE 77
8
the agent gets different states same location twice, which minimizes the correlation among locations. We further add some stochasticity in the transition probability. The agent has a probabil- ity of 10% arrive in the adjacent locations when taking an action. For example, when taking action "left', the agent has a 10% chance of transiting to 'up", and 10% chance of transiting to 'down'. The agent gets a reward -1 when bumping into wall, and gets 1000 when reaching the goal.
Figure 5: An example MNIST maze (left) and the UCB-bonuses the agent's path (right).
We use the different setup of wall-density in the experiment. The wall-density means the proportion of walls in all locations. Figure (left) shows a generated maze with wall-density of 50%. The gray positions represent walls. We train all methods with wall-density of 30%, 40%, and 50%. For each setup, we train 50 independent agents for 50 randomly generated mazes. The relative length defined by lagent//b /beat is used to evaluate the performance, where lagent is the length of the agent's path an episode (maximum steps are 1000), and lhst is the length of the shortest path. The performance comparison is shown in Figure 4 OEB3 performs best in all methods, and BEBU-IDS a strong baseline. We use a trained OEB3 agent to take action in the maze of Figure (left). The of state-action pairs in the agent's path computed and visualized in Figure S (right). The state-action pairs with high UCB-honus show the bottleneck positions in the path. For example, the state-action pairs in location (3, and (6, produce high UCB-bonus guide the agent choose the right direction. The UCB- encourages the agent to walk through these bottleneck positions correctly. We give more examples of visualization Appendix B
16

---

Under review as a conference paper at ICLR 2021
D IMPLEMENTATION DETAIL
D.1 MNIST MAZE
Hypee-parameters of BEBU. BEBU is the basic algorithm of BEBU-UCB and BEBU-IDS. BEBU
uses the same network-architecture as Bootstrapped DQN (Osband et al. 2016). The diffusion factor and other training parameters are set by following EBU paper (Lee et 2019). Details are summarized in Table
Table 4: Hyper-paramelter of BEBU for MNIST-Maze
Hyperparameters
Value
Description
state space
28 28
Stacking two images sampled from MNIST dataset with labels according to the agent's current location.
action space K
Including left, right, and down.
10
Number of bootstrapped heads.
network-
conv(64,4,4)
Using convolution (channels, kernel size, stride) layers first, then fully connected into K bootstrapped heads. Each head has 512 ReLUs and 1 linear units.
architecture
16nv(64.3,1) dense (512, 1)
gradient norm
10
The gradient is clipped by 10. The gradient of each head is normalize 1/K K according bootstrapped DQN.
learning starts
10000
The agent takes actions according to the initial policy before learning starts.
replay buffer size training frequency
170
A simple replay buffer used to store episodic experience. Number of action-selection step between successive gradient descent steps.
50
200,000
Total timesteps to train single maze. The target-network is updated every 2000 steps.
target network up-
2000
date frequency optimizer
Adam
Adam optimizer is used for training. Detailed parameters: 81 0.9, 8g = 0.999, CADAM 10-?
learning rate
0.001 (
Learning rate Adam optimizer.
Exploration factor. H is the total timesteps for training, and h is the current timestep. starts from I and is annealed to 0 in quadratic manner. Discount factor.
7 3 wall density reward
1.0
Diffusion factor of backward update.
30%, 40%, and 50%
Proportion of walls in all locations of the maze.
-1 or 1000
Reward is -1 when bumping into wall, and 1000 when reaching the goal.
stochasticity
10%
Has a prohability of 10% to arrive the adjacent locations when taking an action.
evaluation metric
has Lagent/ /wwst
Ratio between length of the agent's path and the best length.
Slyper-parametery of BEBU-UCB, BEBU-UCB uses the upper-bound of Q-values to select actions. In particular, = arg max (u(s,a) a) o (s, a)), where pls, a) and (s, a) are the mean and standard deviation of bootstrapped Q-values (Qa (s, aa) I= We use Aueb = 0.1 in our experiment.
Hyper-parameters of BEBU-IDS. The retion-selection in IDS Nikolov al. 2019) follows the which balances the regret and exploration.
regret-information ratio as arg min Á.(a.0)²
T((sa)
(e(s,a) a) is the expected regret that indicates the loss of reward when choosing suboptimal action IDS
conservative estimate of regret as Á a) max (1 a') (s, a), where [1(s, a), u4(s, a)] is the confidence interval of action-value function. In particular, ur(s, a) = u(s, a) A a) and ((s, = uuss, a) As, a), where u(s, a) and a (ss, a) are the mean and standard deviation of bootstrapped Q-values (Q* (s,a) a),a /=r- The information gain Iz(a) measures (ssa))
the uncertainty action-values as T(s, a) = log(1 + pls.a) + fids. where p(s, a) is the variance of the return distribution. p(s, a) is measured by C51 (Bellemare al. 2017) in distributional RL and becomes constant in ordinary Q-learning. We use Aids 0.1, p a) 1.0, and Eits = 10 in experiment.
17

---

Under review as a conference paper at ICLR 2021
Hyper-parameters of OEB3. We set d1 and dg to the same value of 0.01. We find that adding normalizer to UCB-bonus B of the next Q-value enables to get more stable performance. B is smoothed by dividing a running estimate its standard deviation. Because the UCB-bonuses for next-Q different for each Q-head, the normalization is useful in most cases by making the value function have smooth and stable update.
D.2 ATARI GAMES
syper--arameters BEBU. The basic setting of the Atari environment the same as Nature DQN (Mnih et al. 2015) and EBU (Lee et at. 2019) papers. We use the different network architecture, environmental setup, exploration factor, and evaluation scheme from MNIST maze experiment. Details are summarized in Table
Table Hyper-parameters of BEBU for Atari games
Hyperparameters
Value
Description
state space
84 x 84 x
Stacking recent frames as the input to network.
action repeat
Repeating each action 4 times.
K
10
The number of bootstrapped heads.
network-
conv(32,8,4)
Using cnnvolutioncchanel. kernel size, stride) layers first, then fully connected into K bootstrapped heads. Each head has 512 ReLUs and [A] linear units.
architecture
conv(64,4,2)
conv(64.3,1)
dense (512,, [A])
gradient
10
The gradient is clipped by 10, and also be normalize by 1/K each head by following bootstrapped DQN. The agent takes random actions before learning starts. The number of recent transitions stored in the replay buffer. The number of action-selection step between successive gra- dient descent steps.
learning starts
50000
replay buffer size
IM
training frequency
20M
Total frames to train an environment.
target network
10000
The neter- is updated every 10000 steps.
date frequency optimizer
Adam
Adam optimizer is used for training. Detailed parameters: 31 = 0.9, 82 = 0.999, CADAM 10-7 The number of training cases for gradient decent each time. Learning rate for Adam optimizer.
mini baiib size
32
learning rate
0,00025
initial exploration
1.0
Initial value of e-greddy exploration.
final exploration
0.1
Final value of e-greedy exploration.
final exploration
The number of frames annealed to the final value.
initial value linearly
frames
0.99
Discount factor.
9
0.5
Diffusion factor of backward update. Exploration factor e-greedy for evaluation.
Gooet evaluation policy
0.05
ensemble vote
The same evaluation method as in Bootstrapped DQN Os
band et al, (2016).
evaluation length
108000
The policy evaluated for 108000 steps. The policy is evaluated every 100K steps.
evaluation
fre-
100K
quency max no-ops
30
Maximum number no-op actions before an episode starts.
Hyper-parameters of BEBU-UCB. BEBU-UCB selects actions by a arg max [u(s, a) + Aucbo as) The detail is given in Appendix D.I We use Aueb 0.1 in our experiment by searching coarsely.
Hyper-parameters of BEBU-IDS. The action-selection follows the regret-information ratio as a, arg min [.(=,) The details are given in Appendix D.I We use \ 0.1, p(s,ppss.00) 1.0
[s(s,))
and Eids = 10-5 5 our experiment by searching coarsely.
Hyper-parameters of OEB3. We set an and 0g to the same value of 0.5 10- The UCB-bonus B for the next Q-value normalized by dividing running estimate of its standard deviation have a stable performance.
18

---

Under review as a conference paper at ICLR 2021
E VISUALIZING OEB3
OEB3 uses the UCB-bonus that indicates the disagreement of bootstrapped Q-estimates to measure the uncertainty of Q-functions. The state-action pairs with high UCB--bousee signify the bottleneck positions meaningful events. We provide visualization in several tasks to illustrate the effect of UCB-bonuses, Specifically, we choose Mnist-maze and two popular Atari games Breakoud and Mspacman analyze.
E.1 MNIST-MAZE
Figure 6 illustrates the JCB-bonus in four randomly generated mazes. The mazes in Figure ((a) and 6(b) have a wall-density of 40%, and in Figure and ((d) have wall-density of 50%. The left of each figure shows the map of maze, where the black blocks represent the walls. We do not show the MNIST representation of states for simplification, and MNIST states are used in training. trained OEB3 agent starts at the upper-left, then takes actions to achieve the goal bottom-right. The UCB-bonen -eBuesss of itate-action pairs in the agent's path are computed and shown on the right of 1 for visualization. We show the maximal value the agent appears several times in the same location.
each figure. The value normalized
The positions with JCB-bonuses that higher than draw the path of the agent. The path is usually winding and includes positions beyond the shortest path because the state transition has stochasticity. The state-action pairs with high UCB-bonuses show
bottleneck positions the path. maze ((a)
the agent slips from the right path in position (4, 7) to (4, (4,9). The state-action in position (4,
produces high bonus to guide the agent back to the right path. In maze maze 6(b] the bottleneck state in
(3, 2) has high bonus avoid the agent from entering into the wrong side of the fork. The other
two mazes also have bottleneck positions, like (3, 3) maze 6(c) and (7, 6) in maze ((d) Selecting actions incorrectly in these important locations is prone failure. The UCB- encourages the agent to walk through these bottleneck positions correctly.
UCI-bborus
Map
UCBB-bom BuB8-bonus
T
G
(a)
(b)
Map
UCB bonus
Map
UCB--brrus
(c)
Figure 6: Visualization of UCB-bonus in Mnist-maze
E.2 BREAKOUT
In Breakout, the agent uses walls and the paddle to rebound the ball against the bricks and eliminate them. We use trained OEB3 agent to interact with the environment for an episode in Breakout. The whole episode contains 3445 steps, and we subsample them every 4 steps for visualization. The curve Ssows shows the UCB-bonus in 861 sampled steps. We choose spikes with high UCB-bonuses
and visualize the corresponding frames. The events in spikes usually mean meaningful experiences that are important for the agent to get rewards. In step 1, the agent is hoping to dig tunnel and get rewards faster. After digging tunnel, the balls appear the top of bricks in steps 2, 3, 4, 5, 6, and 12. Balls on the top are casier to hit bricks. The agents rebound the ball and throw it over the bricks in steps 7, 8, 10, and 11. In state 13, the agent eliminates all bricks and then comes
19

---

Under review as a conference paper at ICLR 2021
round, which is novel and promising to get more rewards. The agents in steps 14, 15, and 16 rebound the ball and try to dig a tunnel again. The UCB-bome encourages the agent to explore the potentially informative and novel action pairs to get high rewards. We record 15 frames after each spike for further visualization. The video is available at ttt.ts::///utttit w.utu.. be /ttp/Vttt..k........ 8g
1-
NID
10
3P
24
20
13
1.5
1.0
100
200
300
400
500
600
700
800
Figure 7: Visualization of in Breakout
E.3 MSPACMAN
In MsPacman, the agent earns points by avoiding monsters and eating pellets. Eating an energizer causes the monsters to turn blue, allowing them to be eaten for extra points. We use trained OEB3 agent to interact with the environment for an episode. Figure & shows the UCB bonus in all 708 steps. We choose 16 spikes to visualize the frames. The spikes of exploration bonuses correspond to meaningful events for the agent to get rewards: starting a new scenario (1,2,9,10), changing direction (3,4,13,14.16) cating energizer (5,11), cating monsters 17,8, and entering the corner (6,15). These state-action pairs with high UCB-bonuses make the agent explore the environment efficiently. We record 15 frames after each spike, and the video is shown at https 7/youtu. be/C C 8NHKpBNXM
10
0.9
Www.mp))))))
0.6
Figure 8: Visualization UCB-bonus in MsPacman
20

---

Under review as a conference paper at ICLR 2021
RAw SCORES OF ALL 49 ATARI GAMES F
Table 6: Raw scores for Atari games. Each game is trained for 20M frames with single RTX-2080Ti
GPU. Bold scores signify the best score out of all methods.
Random
Human
BEBU
BEBU-UCB
BEBU-IDS
OEB3
Alien
227.8
6,875.0
1,118.0
811.1
857.9
916.9
Amidar
5.8
1676.0
81.7
166.4
148.1
94.0
Assault
222.4
1,496.0
1,377.0
3,574.5
2,441.8
2,996.2
Asterix
210.0
8,503.0
2,315.0
2,709.3
2,433.9
2,719.0
Asteroids
719.1
13,157.0
962.8
1,025.0
868.8
959.9
Atlantis
12,850.0
29,028.0
3,020,500.0
3, 3,191,600 16000
3, 3,144,440.0
3,146,30..0
Bank Heist
14.2
734.4
331.8
277.0
361.6
378.6
Battle Zone
2,360.0
37,800.0
5,446.4
16,348.8
10,520.0
13,454.5
BeamRider
363.9
5,775.0
2,930.0
3,208.3
3,391.0
3,736.7
Bowling
23.1
154.8
29.9
30.7
40.2
30.0
Boxing
0.1
4.3
72.4
68.3
69.8
75.1
Breakout
1.7
31.8
473.2
382.3
412.7
423.1
Centipede
2,090.9
11,963.0
2,547.2
2,377.9
3,328.4
2,661.8
Chopper Command
811.0
9,882.0
930.6
1,013.4
1,100.0
1,100.3
Crazy Climber
10,780.5
35,411.0
49,735.7
39,187.5
42,242.9
53,346.7
Demon Attack
152.1
3,401.0
6,506.3
6,840.4
7,080.0
6,794.6
Double Dunk
-18.6
-15.5
-18.9
-16.5
-18.2
Enduro
0.0
309.6
504.1
697.8
513.6
719.0
Fishing Derby
99.77
5.5
-6..7
-83.8
-53.3
-60.1
Freeway
0.0
29.6
21.5
21.6
21.3
32.1
Frostbite
65.2
4,335.0
393.4
470.4
466.2
1,77.33
Gopher
257.6
2,321.0
4,842.6
7,211.8
7,171.5
6,359.5
Gravitar
173.0
2,672.0
256.1
321.0
283.3
393.6
H.E.R.O
1,027.0
25,763.0
2,951.4
2,905.0
3,059.4
3,302.5
Ice Hockey
-11.2
0.9
-5.4
-6.5
446
-4.2
Jamesbond
406.7
650.0
360.3
302.1
434.3
Kangaroo
52.0
3,035.0
3624.2
2,711.1
4,448.0
2,387.0
Krull
1,598.0
2,395.0
15,716.7
11,499.0
10,818.0
45,388.8
Kung-Fu Fu Master
258.5
22,736.0
56.0
20,738.9
26,909.7
16,272.2
Montezuma's Revenge
0.0
4.376.0
0.0
0.0
Pacman
307.3
15,693.0
1,723.8
1,706.8
1,615.5
1,794.9
Name This Game
2,292.3
4,076.0
8,275.3
6,573.9
8,925.0
8,576.8
Pong
-20.7
9.3
18.1
18.5
17.2
18.7
Private Eye
24.9
69,571.0
1,185.8
1,925.2
1,897.1
1.174.1
Q*Bert
163.9
13,455.0
3,588.4
3,783.2
3,696.0
4,275.0
River Raid
1,338.5
13,513.0
3,127.5
3,617.7
3,169.1
2,926.5
Road Runner
11.5
7,845.0
11,483.0
20,990.7
17,281.4
21,831,4
Robotank
2.2
11.9
10.3
13.3
10.7
13.5
Seaquest
68.4
20,182.0
447.0
492.3
332.4
332.1
Space Invaders
148.0
1,652.0
814.4
782.2
794.7
904.9
Star Gunner
664.0
10,250.0
1,467.2
1,201.5
1,158.9
1,290.2
Tennis
-23.8
-8.9
-1.0
-2.0
-1.0
-1.0
Time Pilot
3,568.0
5,925.0
2,622.1
3,321.2
1,950.6
3,404.5
Tutankham
167.6
167.0
151.0
80.5
297.0
Up and Down
533.4
9,082.0
5,954.8
4,530.2
4,619.7
5,100.8
Venture
0.0
1,188.0
42.9
3.4
150.0
16.1
Vidco Pinball
16,256.9
17,298.0
26,829.6
48,959.1
58,398.3
80,607.0
Wizard of Wor
563.5
4,757.0
810.8
1,316.7
578.2
480.7
Zaxxon
32.5
9,173.0
1,587.5
2,104.8
1,594.2
2,842.0
21

---

Under review as a conference paper at ICLR 2021
G PERFORMANCE COMPARISON
We use the relative scores
AcoreAgent ScoreBaseline
max (Scorehmman; Scorebaseline) Scorerandom
compare OEB3 with baselines. The results of OEB3 comparing with BEBU, BEBU-UCB, and BEBU-IDS is shown in Figure 9 Figure I0, and Figure II respectively.
508.64
250
210.16
200
150
90.21
72.24
42.63
32.00
33.08
2319
35.81
33:72
14.11
20.7
22.58
22.6
0063
87
$3.03
12.28
|1.85
11.05
:0.02
00.02
0.0
0.08
10.74
[1.42
11.55
11:87
3.73
1438
4,54
6.87
5.04
5.5
6.5
9.92
Breakeg Broskeott Up and Down
Faniin Derty
Abar
Ventore
Star Gurrter
Rivet Foldd
Sewsvess
Hontezime's Revegge rgge
fateront
brhare Eye
Termi
Bowling
Racttann
Amoder
I.E.D.
Olgger Command
Pong
Bortng
Demen Artack
Adtantis
Nome This Game
Auveroo
Orbert
space murdees
Gravter
Bank Bank Hout
erary Carbeer
ics Heckoy
Zazson
Boem Riteer
Frosth roe
Double Dung
Buttie Zone
Robelarak
Gapter
Time Polot
Kump- Menter
Endiro
Tuoenthen
Food Rumnee Ascaut
Vileo Prigball
Jamer
wicard
Figure Relative score of OEB3 compared to BEBU percents (%).
342.29
250
03.47
06.78
100
43.04
47
50
94
25
96
1.3
11:08
1088
-052
0.0
0.12
0.51
0.
1.07
[1.59
11.01
[2.88
2.01
3.04
1.01
6667
8.16
0.97
10:72
:4:11
10.9
39.59
Dooble Dunk
woard War
Kung Montrr
Gopther
Kangomo
Raitts-a Zone
River Reid
kmider
Altentss
irvvat-. Eye
Sesaiess
Dwntn ok
Hontezuma's Nevango
banting
Anternids
Asseris
Pong
M
Star Gurner
command
Vonture
Albnn
HE HEA.O. a
Rabetook
Contiett cont
Growtar
Grdtro
Time pior
Road Ruoner
GrBert
Tenns
Pawan
invettrs
Rüler
Breateut
Bave Heist
fresttite tott
keeHocke Hockey
James Band
Fisking Derbyy
prenway
Grazy Chrnber
Game
Tucenkhum
Video Pegiial Koot
Spacd Boam
Choppter
Nomo
Figure 10: Relative score of OEB3 compared to BEBU-UCB in percents (%).
22

---

Under review as a conference paper at ICLR 2021
374.3 5355
100
61.68
52.7
35.29
20.43
90
50
26.35
1.500
13.65
10.0
0.74
0075
12:33
11.99
1.004
0.0
0.0
0.06
10.72
10.89
10.98
11.17
1137
|2.30
3331
13.06
4.36
1.41
5.63
6.39
7.33
7.8
kong Macker
tomperso
Douible Dunk
Ventune
Bowing
Fashing Darby
Itemee Thit Game
Ceroevess
Demon Attecs
Amader Wizard War River Raid
Privgts Eye
Memeaamma Revangee
Seugures
Choppe Command
Terelg
Arientty
Abben
R.E. R.R.R.
Mt. Pac-Ma
Shar Gurens
Bank Hest
Breatenn
Horday
Antera
Ponu
option
Grawtta
Down
Rites
invadio
Boxing
Battie Zone
Zourn
Frostale e
Acoouh
Road Rumnay
Roterbnn aacrtnng
lamos Bord
Clmbeer
Freewny
Vitto Proghaa! Time play
Endioro
Tatanham Krud
Up g-an
space
Figure 11: Relative score of OEB3 compared to BEBU-IDS in percents (%).
H
FAILURE ANALYSIS
Table 7: Comparison of scores in Montezuma's 's Revenge.
Frames
200M
20M
DQN
BootDQN 100
NoisyNet BootDONNIDDS BERU BEBU-UCH BEBU-IDS OFB3
Scores
0
0
0
Our method does have a good performance on Montezuma's Revenge (see Table 7 because the epistemic uncertainty-basse methods are not particularly tweaked for this domain. IDS, NoisyNet and BEBU-based methods all fail this domain and score zero. Bootstrapped DQN achieves 100 points, which is also very low and does not indicate successful learning in Montezuma's 's revenge. In contrast, the bonus-based methods achieve significantly higher scores in this tasks (e.g., RND achieves 8152 points). However, according to Taiga et al. (2020) and Table [ NoisyNet and IDS significantly outperform several strong bonus-based methods evaluated by the mean and median scores of 49 Atari games.
23


Reviews:
[{"review_id": "keGGnoLZhmK", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a UCB-based optimistic exploration method for DRL, called Optimistic Exploration algorithm with Backward Bootstrapped Bonus (OEB3). The algorithm builds on the idea of optimistic exploration developed in the theoretical optimistic LSVI algorithm for linear MDP. In optimistic LSVI, the optimistic Q-value is backward updated for each episode with an UCB bonus at each step. OEB3 extends this backward update of UCB bonus to DRL by estimating the UCB bonus using bootstrapped Q-learning. OEB3 learns an ensemble of bootstrapped Q-values and estimates the UCB bonus as the variance of the Q-values. Another important part of OEB3 is to adapt episodic backward update to bootstrapped Q-learning. This is done by procedure called Bootstrapped Episodic Backward Update (BEBU) which extends previous episodic update idea to the ensemble of bootstrapped Q-values. \n\nExperiments have be done in Mnist Maze and Atrari games comparing OEB3 with previous exploration methods and some OEB3 variants. Table 2 nicely summarizes the algorithm design difference of related algorithms and highlight the two important components of backward update and UCB bonus in OEB3, and the improvements clearly helps OEB3 to outperforms similar exploration approaches. However, it may be miss-leading to say that OEB3 outperforms all existing bonus-based methods since it actually performs worse than some prior methods in Montezuma’s Revenge.\n\nI think this is a nice work given its connection to theory and the nice empirical performance, but I think the following questions about steps in the OEB3 algorithm should be answered.\n\n- The paper claims to use bootstrapped Q-learning, but in the algorithm description, at each time only one episode E is sampled for all head. This is different from the original bootstrapped Q-learning design where different heads are learned using different samples with bootstrap. Are there some steps missing in the algorithm description or no bootstrapped samples are used? If all heads are learned from the same sample, does the diversity among different heads only depend on their initialization?\n\n- In training, the action is selected by randomly picking a head, i.e. the Thompson sampling approach. However, in evaluation the action seems to be selected by majority vote. Is there a reason for this difference in training and evaluation? Does random sampling help exploration in training?\n\n- In algorithm description, epsilon-greedy is actually used in OEB3 during training. The use of epsilon-greedy is different from other exploration methods which guide exploration by bonus or other randomness. Why does OEB3 need epsilon-greedy given its exploration bonus design? In experiments, do other baselines also use epsilon-greedy?\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hfPWPiBPTt6", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### SUMMARY\n\nThe paper proposes a strategy for computing and propagating uncertainty to improve exploration in deep reinforcement learning. While the architecture necessary for computing the uncertainty is reliant on the framework of an existing deep RL algorithm — bootstrap DQN — the idea for propagation of this uncertainty to yield effective behaviour, or optimistic value estimates, hinges upon strategies used in the finite-horizon algorithms — constraining learning to be at the timescale of episodes (instead of samples).\n\nThe proposed main algorithm OEB3 — Optimistic Exploration with Backward Bootstrapped Bonus — combines ideas from existing literature to promote optimistic value estimates, and hence, as a product, effective exploratory behaviour. Particularly, I think it brings together 4 ideas from 4 different referenced papers: \n1. a learning architecture that implements non-parametric Bayesian Value Iteration (as done in Osband et. al. 2016)\n2. uncertainty estimation (as done in Chen et. al. 2019)\n3. uncertainty propagation by constraining learning timescale (as done in Lee et. al. 2019 and Jin et. al. 2019)\n4. uncertainty propagation by bootstrapping from optimistic estimates (as done in Jin et. al. 2019)\n\nThe paper also highlights that due to the uncertainty propagation achieved by incorporating ideas from (3) and (4) the induced exploratory behaviour is more effective, and hence the sample complexity of learning is reduced. Therefore, instead of the more common 200M frames used for training deep RL agents, 20M frames are used for training in the experiments here.\n\n\n#### STRENGTHS\n\nI think the paper is a fine example of research that builds on existing ideas in the field. The relevant work is discussed and the paper gradually builds up to the core proposal. The empirical analysis is comprehensive across the Atari suite, in order to be wary of recent work that suggests design of deep RL exploration methods may be overfitting to performance measures in a skewed subset of Atari (although, as it seems to be de-facto standard of the field, it averages across 5 seeds). Additionally, as the algorithm does have many components, the paper does a good job of explaining the strategy employed for uncertainty propagation well in the text.\n\n\n#### WEAKNESSES\n\nWhile I do think incremental research that builds on existing work is very valuable, I think the paper can be improved due to the following three key limitations:\n1.  the presentation style currently obfuscates the incremental nature of the paper. For instance \n\t(a) the uncertainty estimation strategy is as proposed by Chen et. al. 2019, but the presentation seems to suggest it is novel. While Chen et. al. 2019 do not propose to “propagate” it during bootstrap as well, the bonus computed is the straightforward empirical standard deviation, as proposed by them.\n\t(b) the informal Theorem 1 (and corresponding formal Theorem 2) I think are well known in that the bonus used by UCB algorithms for linear regression is proportional to the posterior variance of bayesian linear regression. I am having a hard time seeing this as an insightful contribution. Further, LSVI-UCB is a frequentist solution approach and bootstrap DQN a non-parametric Bayesian approach — combining the two definitely warrants some discussion.\n\t(c) BEBU is essentially EBU as proposed in Lee et. al. 2019 with bonuses added. I do not think the text presents it so. Further, “faithfully follows the backward update of optimistic LSVI” may be a stretch as the optimistic LSVI bootstrap estimates are post learning at every step of backward induction.\n2. While I understand a complete empirical comparison to the many existing deep RL methods can be very expensive, the literature review does miss methods proposed with a similar ethos — propagation of uncertainty. I think they need to be discussed and compared against\n\t(a) Bayesian Deep Q-Networks : Azizzadenesheli et. al. 2019 [https://arxiv.org/pdf/1802.04412.pdf]\n\t(b) Uncertainty Bellman Equation: Osband et. al. 2018 [https://arxiv.org/pdf/1709.05380.pdf]\n3. Some of the proposals made are unclear and left unexplored/discussed.\n\t(a) bonus in bootstrap target - different from LSVI-UCB\n\t(b) $\\epsilon$-greedy with bootstrap dqn - non-parametric “optimistic” bayesian approach with dithering?\n\t(c) computation of $\\tilde{B}^k$ (I may have missed this, but presumably its the empirical standard deviation with the target networks of the ensembles)\n\nFurther, I think some discussion in the main/appendix are warranted in terms of the empirical setup: \n1. the buffer is a circular buffer of size 1M — is it 1M trajectories or 1M samples?\n2. handling of episode cutoffs (which I presume are used), for bootstrapping at the end of the trajectory.\n3. the magnitude of $\\alpha_1$ and $\\alpha_2$ are really small — the scale of the bonuses would be interesting to look into as well.\n\n\n#### QUESTIONS\n1. I understand the bonus proposed is an empirical surrogate to promote optimistic values (with respect to the seen data) — but ideally, do we not need optimistic values that include q*. What is the guarantee that q^* is included in the set (as it seems to be for the example in Figure 1).\n2. What do you see are the key advantages of the proposed approach? Is scalability by constraining learning to be at the episode level an issue in practical applications? (I think this also can be discussed in the paper).\n\n\n#### SUGGESTIONS\nMy concrete suggestions to improve the paper while keeping the core idea the same is two fold:\n1. a more thorough empirical section comparing to methods designed for uncertainty propagation\n2. a rewrite which reflects that the components of the core idea are existing proposals in literature in the case of both bonus estimation and the EBU algorithm.\n3. I think it is surprising that OEB3 is poorer that Bootstrap DQN in Montezuma’s revenge - presumably an increased number of training steps should alleviate the discrepancy; if not, the bonuses propagated by OEB3 may actually hinder performance which I think warrants acknowledgment/discussion.\n\n#### Minor typos\n1. Mnist  —> MNIST\n2. Medium —> Median (Table 1)\n3. Presumably Figures 2 and 3 are bonuses during learning — but a phrase in Section 5.2 says “trained OEB3”.\n4. Section 5.2: incentive —> incentivize\n\n\n\n## POST-REBUTTAL\n\nI really appreciate the author's engagement and response during the discussion phase to help me understand the paper better, and the revisions incorporated in the paper.\nBut after much thought, I do not think the current form of the paper meets the bar for publication.\n\nHere are my main concerns that I hope is useful for the next version or final submission.\n\nI think the core idea of the algorithm is uncertainty propagation is necessary for inducing effective exploratory behaviour. This core idea is theoretically motivated from sound strategies for exploration in finite-horizon RL, but as the paper addresses the discounted problem setting with deep neural networks the soundness is traded-in for computational tractability — which is a fine choice.\n\nBut, currently the choices are presented in a confusing way, and the actual contributions of the algorithm are unclear: most importantly, is it a Frequentist approach to exploration or Bayesian?\n\n- under the Frequentist approach setting, utilizing e-greedy seems justifiable just based on the reasoning of this is “the widely accepted practice in the field”.\n- under the Bayesian viewpoint, which is the crux of the architecture used here (Bootstrap DQN), the attempted theoretical connections in the paper (Theorem 1) and the practical algorithm proposed (based on the ideas of Optimistic LSVI), do not provide a clear picture.\n\nTo show theoretical soundness the algorithm is anchored to a Bayesian architecture and theoretical uncertainty connection, but for practical performance purposes the paper leverages reasoning from Frequentist Deep RL methods. Maybe this is a step in the right direction, and the extensive empirical results do seem to suggest it is effective, but the presentation is unclear. From the current draft:\n- “OEB3 relies on the posterior of Q-functions” — Bayesian\n- “UBE uses posterior sampling for exploration, whereas OEB3 uses optimism for exploration” — Frequentist\n\nTherefore, this can be improved and presented more clearly to communicate the idea.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UZ4qdCmndTa", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors of the submission \"Optimistic Exploration with Backward Bootstrapped Bonus for Deep Reinforcement Learning\" draw inspiration from the theoretical reinforcement learning literature to propose an optimism based bonus for deep q learning. The idea is to compute an optimistic bonus based on a Q function ensemble, and use this to augment the present reward signal and the future return estimator (future optimism) to yield an algorithmic approach that reduces to LSVI in the case of linear MDPs (or at least reduces to something akin to LSVI in that case). \n\nThe authors then introduce a generic procedure (BEBU) that can be plugged into a variety of Q learning algorithms to produce an \"optimistic\" bootstrapped backward episodic update. Crucially the order of the updates matters, since the uncertainty bonuses should be propagated backwards in time. This is a very nice poin: the uncertainty propagation should be done backwards. \n\nThe authors are right in my opinion to claim their work represents a welcome addition to the emerging literature that proposes the use of uncertainty bonuses around the value function as opposed to myopic uncertainty bonuses only at the immediate reward level. There exist other recent works that introduce similar ideas (bringing in bonuses for the future uncertainty as opposed to solely penalizing immediate  ) are some missing citations in the related work section, most notably \"On optimism in model based reinforcement learning\" (using value optimism in model based RL and deep RL), \"Efficient model based RL through optimistic policy search and planning\"(optimism and GPs in model based RL), and also SUNRISE which looks awfully related to BEBU-UCB. \n\nThe experimental results of this work are strong. It is nevertheless unclear how much of these results are the consequence of accessibility to massive computing resources. I would like to see the paper positioned more faithfully within the relevant optimism-at-value-level literature, even though these works are model based in nature. It would also be very useful to have algorithm boxes for the different methods or method templates that the authors describe in the text. It is hard to follow what they intended to say or at least a table listing succinctly in a reader friendly way what the differences are between the different instantiations of the approach (OEB3, BEBU, BEBU-UCB, etc ...). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "DwVTcjLAAk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies optimistic exploration for deep reinforcement learning. They propose an algorithm called OEB3, which utilizes the disagreement of bootstrapping Q-functions as the confidence bonus to guide exploration. They show that their confidence bonus matches the confidence bonus of optimistic LSVI in linear setting. After that, they evaluate their algorithm on plenty of benchmark problems including Mnist maze and 49 Atari games. Their algorithm outperforms other SOTA exploration approaches.\n\nPros:\n\n- The optimistic exploration problem is very important for the RL community. From the theoretical perspective, the classical $\\epsilon$-greedy exploration method has been shown to be inefficient, and UCB-based algorithms are shown to be sample efficient with regret guarantee. However, how to apply these theoretical insights into practical algorithms is still an open problem. The paper proposes a method that uses bootstrapping to construct confidence bonus, and connects the theoretical findings to practical algorithms.\n\n- The experimental results on 49 Atari games are rich enough to show the improvement of the algorithm, with visualization results and ablation studies. \n\nOther comments:\n\n- The connection with optimistic LSVI is interesting but not satisfying. Theorem 2 assumes that $\\epsilon$ follows the standard Gaussian distribution. Why does this assumption hold? A more natural and reasonable assumption is that the rewards and transitions are sampled from a Gaussian distribution. Can theorem 2 still hold under such assumptions?\n\n\n-------Post Rebuttal---------\n\n\nThanks for the feedback from the authors. After the rebuttal and discussion period, I believe that the contribution of the paper are mainly empirical. The Theorems (Theorem 1 and 2) are proposed to show the intuition of the bootstrapping and backward-update methods, and to connect the algorithm with recent theoretical results. During the discussion, there are mainly three concerns about the theorems among reviewers. \n\n- Firstly, the algorithm uses eps-greedy to help exploration, which is theoretically unclear. \n- Secondly, the theorems focus on episodic setting, while the algorithm is designed for discounted setting. \n- Lastly, it is unclear whether the algorithm is a frequentest approach or Bayesian. \n\nI believe that the former two concerns can be addressed in the following way, and don't weaken the contribution of the paper.\n- From the theoretical perspective, the feedback from the authors does tackle this problem. The eps-greedy will only add an epsilon-term to the final regret. I am eager to see the discussion in the final version. From the experimental view, the authors also claim that all the algorithms in the experiments use eps-greedy to help exploration. In that case, the improved performance of their algorithms are mainly due to their bootstrapping and backward-update methods, instead of eps-greedy trick. Besides, I think applying several widely-used tricks (such as eps-greedy) to the algorithm is acceptable, which makes the results comparable to other methods that also use the tricks. \n- To the best of my knowledge, there is currently no paper studying linear MDP in the discounted setting from the theoretical perspective. I think this is the reason why this paper studies the connection of the theorems in episodic setting. Meanwhile, it is hard to conduct experiments in episodic setting (In that case, the algorithm needs to learn the value function of all the possible horizon). Moreover, we can reduce an MDP with discounted rewards to episodic MDP by setting the effective horizon $H = \\frac{1}{1-\\gamma}$. This means that the theorem for episodic MDP can hold in the discounted setting with slight modification. Maybe such discussion should be added to the paper.\n\nHowever, for the last concern, I am still puzzled whether the algorithm is a frequentest approach or Bayesian, as there are many unclear statements.\n\nOverall, I believe the main contribution of the paper is from the empirical perspective. The theorem is intended to show the intuition of the algorithm and to connect the approach to the recent theoretical results. The experimental results look nice in general. I am a little disappointed that the authors missed the comparison with two related literatures in the initial version. I agree with R5 that these results may be done under a time-crunch. As a result, I change my score to 6, and I hope the above problems can be addressed in the next version.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5JrhgxJfvR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on deep reinforcement learning and proposes a practical exploration algorithm called Optimistic Exploration algorithm with Backward Bootstrapped Bonus. Based on the Optimistic LSVI algorithm, the authors propose a new optimistic exploration bonus for general cases, similar to the optimistic exploration bonus in the LSVI algorithm under the linear MDP setting. Experiment results show that the QWR algorithm has better performance than previous algorithms.\nThis paper is well-written and easy to follow.  The main contributions are delivered:  Proposed optimistic exploration bonus for general cases; New deep reinforcement learning algorithm. However, I still have some concerns about this paper.\nFirst, the actor-value function Q is the expected cumulative reward with discounted factor \\gamma. However, it is usually set 0<\\gamma<1 for infinite-horizon MDP and set \\gamma=1 for episodic MDP or finite-horizon MDP. Besides, the LSVI algorithm also set \\gamma=1, and it seems strange that there is a discounted factor \\gamma in the OEB3 algorithm.\nSecond, in the LSVI algorithm, the agent chooses action by the totally greedy policy with the state-actor value function. In the OEB3 algorithm, the agent chooses action by the \\epsilon-greedy policy. Even the optimistic exploration bonus in the OEB3 algorithm is the same as the LSVI algorithm under the linear MDP setting, theoretic proof of LSVI may not support the OEB3 algorithm.\nFinally, in the experiment, it seems that the action space is relatively small. It is better to do more experiments with a broader action set and show the OEB3 algorithm's performance in those experiments.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper represents a practical extension of sound theoretical uncertainty propagation ideas for exploration in deepRL. All the reviewers agreed this was a promising direction and the empirical results strong. It was nice to see additional qualitative analysis of the proposed method, beyond the typical "my number is bigger than yours" type of claims. The discussion was extensive; reviewers with specific subject matter expertise provided high quality and detailed reviews.  Several reviewers were in favour of the paper, but none were willing to champion it as a clear accept. 

Indeed the discussion highlighted important concerns with the paper. Several reviewers found the paper to overclaim: most importantly the paper suggests strong theoretical underpinnings of the method without clear evidence. Some found the text very imprecise. The reviewers were torn if such changes represented wording changes or major rewrites. The original submission missed two key pieces of work which were added during the rebuttal phase---UBE was added by including the scores from the literature, and the other (Bayesian-DQN) was only added to the discussion. Good on the authors for doing so, though ideally both would be implemented again. 

The AC's own reading of the paper highlighted a few other concerns. The writing needs work. In addition, the majority of improvement in overall performance appears to be due to very large improvements in a handful of games (e.g. Atlantis, Krull) and significant losses in performance in other games. This was not discussed at all. More surprisingly these games with huge performance gains were not used in the qualitative visualizations of the utility of the bonus found in the paper. The game breakout was used for analysis instead. Oddly the proposed method actually does worse or the same as SOTA methods (e.g., Adaptive EBU, Boot-DQN, UBE) in breakout.  This is difficult to get to the bottom of because: (a) the per-game score tables in the appendix don't include the scores achieved by important baselines (e.g., Boot-DQN, EBU, Adapt EBU), (b) different setups are used across the relevant literature (Boot-Q & UBE papers use 200m frames, EBU paper uses 10m frames, and this paper uses 20m), (c) the per-game analysis in the appendix focuses on comparing methods proposed in the paper under review. That might all make sense, but it is left to the reader to figure out and I never got to the bottom of it all (table 3 of the Lee et al contains some of the relevant comparison data). Such missing details and lack of analysis are particularly important when the paper boldly claims state of the art performance improvement.

All put together a clear picture emerges: the paper needs polishing, is unclear in places, over-claiming, and missing important analysis and explanations---in regards to both the theory and the experiments. The reviews are extensive and have provided many insights in how to improve the paper. 
Decision: Reject