Optimistic Exploration even with a Pessimistic Initialisation
Authors: Tabish Rashid
Bei Peng
Wendelin Boehmer
Shimon Whiteson
Venue:  (2020)
Keywords: Reinforcement Learning
Exploration
Optimistic Initialisation

Abstract: Optimistic initialisation is an effective strategy for efficient exploration in reinforcement learning (RL). In the tabular case, all provably efficient model-free algorithms rely on it. However, model-free deep RL algorithms do not use optimistic initialisation despite taking inspiration from these provably efficient tabular algorithms. In particular, in scenarios with only positive rewards, Q-values are initialised at their lowest possible values due to commonly used network initialisation schemes, a pessimistic initialisation. Merely initialising the network to output optimistic Q-values is not enough, since we cannot ensure that they remain optimistic for novel state-action pairs, which is crucial for exploration. We propose a simple count-based augmentation to pessimistically initialised Q-values that separates the source of optimism from the neural network. We show that this scheme is provably efficient in the tabular setting and extend it to the deep RL setting. Our algorithm, Optimistic Pessimistically Initialised Q-Learning (OPIQ), augments the Q-value estimates of a DQN-based agent with count-derived bonuses to ensure optimism during both action selection and bootstrapping. We show that OPIQ outperforms non-optimistic DQN variants that utilise a pseudocount-based intrinsic motivation in hard exploration tasks, and that it predicts optimistic estimates for novel state-action pairs.

Published as a conference paper at ICLR 2020
OPTIMISTIC EXPLORATION EVEN WITH A PESSIMISTIC INITIALISATION
Tabish Rashid, Bei Peng. Wendelin Böhmer, Shimon Whiteson University of Oxford
Department of Computer Science
(tabish.rashid, bei.peng wendelin medellin... hendelin.boehmer, shimon. whiteson lcs. ox ac. uk
ABSTRACT
Optimistic initialisation is an effective strategy for efficient exploration in reinforce- ment learning (RL). In the tabular case, all provably efficient model-free algorithms rely on it. However. model- free deep RL algorithms do not use optimistic initiali- sation despite taking inspiration from these provably efficient tabular algorithms. In particular, in scenarios with only positive rewards, Q-values are initialised at their lowest possible values due commonly used network initialisation schemes, a pessimistic initialisation. Merely initialising the network to output optimistic Q-values is not enough, since we cannot ensure that they remain optimistic for novel state-action pairs, which is crucial for exploration. We propose simple count-based augmentation to pessimistically initialised Q-values that separates the source of optimism from the neural network. We show that this scheme is provably efficient in the tabular setting and extend it to the deep RI. setting. Our algorithm, Optimistic Pessimistically Initialised Q-Learning (OPIQ), augments the Q-value estimates of a DQN-based agent with count-derived bonuses to ensure optimism during both action selection and bootstrapping. We show that OPIQ outperforms non-optimistic DQN variants that utilise a pseudocount- intrinsic motivation in hard exploration tasks, and that it predicts optimistic estimates for novel state-action pairs.
INTRODUCTION
In reinforcement learning (RL), exploration is crucial for gathering sufficient data to infer a good control policy. As environment complexity grows, exploration becomes more challenging and simple randomisation strategies become inefficient.
While most provably efficient methods for tabular RL are model-based (Brafman and Tennenholtz 2002; Strehl and Littman, 2008: AAzr et al.) 2017). in deep RL, learning models that are useful for planning is notoriously difficult and often more complex (Hafner al., 2019) than model- free methods. Consequently, model-free approaches have shown the best final performance on large complex tasks (Mnih al. 20155] 2016 Hessel et al. (2018), especially those requiring hard exploration (Bellemare et al.] Ostrovskk et al. 2017). Therefore, in this paper, we focus on how devise model-free RL algorithms for effciiett exploration that scale to large complex state spaces and have strong theoretical underpinnings.
Despite taking inspiration from tabular algorithms, current model-free approaches to exploration in deep RI. do not employ optimistic initialisation, which is crucial to provably efficient exploration in all model-free tabular algorithms. This is because deep RI. algorithms do not pay special attention to the initialisation of the neural networks and instead use common initialisation schemes that yield initial Q-values around zero. In the common case of non- non-negative rewards, this means Q-values are initialised to their lowest possible values, i.e., pessimistic initialisation.
While initialising a neural network optimistically would trivial, e.g., by setting the bias of the final layer of the network, the uncontrolled generalisation in neural networks changes this initialisation quickly. Instead, to benefit exploration, we require the Q-values for novel state-action pairs must remain high until they explored.

---

Published as a conference paper at ICLR 2020
An empirically successful approach to exploration in deep RL, especially when reward is sparse, is intrinsic motivation (Oudeyer and Kaplan| 2009). A popular variant is based on pseudocounts (Bellemare et al.) 2016), which derive an intrinsic bonus from approximate visitation counts over states and is inspired by the tabular MBIE-EB algorithm (Strehl and I Littman 2008). However, adding positive intrinsic bonus to the reward yields optimistic Q-values only for state-action pairs that have already been chosen sufficiently often. Incentives to explore unvisited states rely therefore on the generalisation of the neural network. Exactly how the network generalises those novel state-action pairs is unknown, and thus it is unclear whether those estimates are optimistic when compared to nearby visited state-action pairs.
Consider the simple example with single state and two actions shown in Figure I The left action yields +0.1 reward and the right action yields + reward. An agent whose Q-value estimates have been zero-initialised must at the first time step select an action randomly. As both actions are underestimated, this will increase the estimate of the chosen action. Greedy agents always pick the action with the largest Q-value estimate and will select the same action forever, failing to explore the alternative. Whether the agent learns the optimal policy or not is thus decided purely at random based on the initial Q-value estimates. This effect will only be amplified by intrinsic reward.
+0.1
Figure! 1
To ensure optimism in unvisited, novel sateeactiin pairs, we introduce Optimistic Pessimistically Initialised Q-Learning (OPIQ). OPIQ does not rely on an optimistic initialisation to ensure efficient exploration, but instead augments the Q-value estimates with count-based bonuses in the following manner:
C
(s. = (8, a) + (N(s,a)
(1)
where ((s a) is the number of times state-action pair has been visited and M.C 0 are hyperparameters. These Q+ -vauue are then used for both action selection and during bootstrapping. unlike the above methods which only utilise Q-values during these steps. This allows OPIQ to maintain optimism when selecting actions and bootstrapping, since the Q+-values can be optimistic even when the Q-values are not.
In the tabular domain, we base OPIQ on UCB-H (Jin et al., 2018). a simple online Q-learning algorithm that uses count-based intrinsic rewards and optimistic initialisation. Instead of optimistically initialising the Q-values, we pessimistically initialise them and use Q vvlues during action selection and bootstrapping. Pessimistic initialisation is used enable a worst case analysis where all of our Q-value estimates underestimate Q" and is not a requirement for OPIQ. We show that these modifications retain the theoretical guarantees of UCB-H.
Furthermore, our algorithm easily extends to the Deep RL setting. The primary difficulty lies in obtaining appropriate state-action counts in high-dimensional and/or continuous state spaces. which has been tackled by variety of approaches (Bellemare et al. 2016 Ostrovski et al. 2017 Tang et al.) 2017 Machado et al. 2018a) and orthogonal to our contributions.
We demonstrate clear performance improvements in sparse reward tasks over 1) baseline DQN that just uses intrinsic motivation derived from the approximate counts, 2) simpler schemes that aim for an optimistic initialisation when using neural networks, and 3) strong exploration baselines. We show the importance of optimism during action selection for ensuring efficient exploration. Visualising the predicted Q -values shows that they are indeed optimistic for novel state-action pairs.
2 BACKGROUND
We consider a Markov Decision Process (MDP) defined as tuple (S, P, R), where S is the state space, A is the discrete action space, P(-[s, a) is the state-transition distribution, R(-]s,a) a) is the distribution over rewards and E [0, 1) is the discount factor. The goal of the agent is then to maximise the expected discounted sum of rewards: E| ''relra R(-1s,, )., in the discounted episodic setting. A policy π T--ss) is mapping from states to actions such that it is a valid probability distribution. (= a)= == E E "
(a ~ [-]st)] and Q* := max,, Q
Deep Q-Network (DQN) Mmih et al. 2015) uses nonlinear function approximator (a deep neural network) to estimate the action-value function, Q(s, a; 8) x (* a), where are the parameters of the network. Exploration based intrinsic rewards (e.g., Bellemare al.) 2016), which uses
DQN agent, additionally augments the observed rewards r, with bonus // (N 0z) based on
2

---

Published as a conference paper at ICLR 2020
Figure 2: A simple regression task to illustrate the effect of an optimistic initialisation in neural networks. Left: 10 different networks whose final layer biases are initialised (shown in green), and the same networks after training on the blue data points (shown in red). Right: One of the trained networks whose output has been augmented with an optimistic bias as equation I The counts were obtained by computing histogram over the input space [-2, with 50 bins.
psculo-visiiationncounss (st, ar). The DQN parameters are trained by gradient descent on the mean squared regression loss L with bootstrapped 'target' ye:
a;: (st, Tz, 16+1) D].
max
(2)
(st,a.)
The expectation is estimated with uniform samples from replay buffer D (Lin) 1992). D stores past transitions (8t, at, Tt, 8t+1), where the state 8141 is observed after taking the action d in state 8, and receiving reward rtz To improve stability, DQN uses target network, parameterised by 0=, which is periodically copied from the regular network and kept fixed for number of iterations.
3 OPTIMISTIC PESSIMISTICALLY INITIALISED Q-LEARNING
Our method Optimistic Pessimistically Initialised Q-Learning (OPIQ) ensures optimism in the Q- value estimates of unvisited, novel state-action pairs in order to drive exploration. This achieved by augmenting the Q-value estimates in the following manner:
C
(s(,aa= a) (N(s,))+11M
and using these Qt-values during action selection and bootstrapping. In this section, motivate OPIQ, analyse it in the tabular setting, and describe deep RL implementation.
3.1 MOTIVATIONS
Optimistic initialisation does not work with neural networks. For an optimistic initialisation to benefit exploration, the Q-values must start sufficiently high. More importantly, the values for unseen state-action pairs must remain high, until they are updated. When using deep neural network to approximate the Q-values, adjusting the final bias. However, after a small amount of training, the values for novel state-action pairs may remain high. Furthermore, due to the generalisation of neural networks cannot know how the values for these unseen state-action pairs compare to the trained state-action pairs. Figure 2 (left), which illustrates this effect for simple regression task, shows that different initialisations can lead to dramatically different generalisations. It is therefore prohibitively difficult to use optimistic initialisation of deep neural network drive exploration.
initialise the network to output optimistic values, for example, by
Instead, we augment our Q-value estimates with an optimistic bonus. Our motivation for the form of the bonus in equation (N(s.a)41)ā stems from UCB-H (Jin al. 2018). where all tabular
Q- Q-values are initialised with H and the first update for a state-action pair completely overwrites that value because the learning rate for the update (7 is 1. One alternatively view these Q-values as zero- initialised with the additional term Q(s, a. H. 1[N(ss, (s,a a) < 1}. where N N(s, a) is the visitation count for the state-action pair (s, a). Our approach approximates the discrete indicator

---

Published as a conference paper at ICLR 2020
Algorithm 1 OPIQ algorithm
Initialise Qr(s,a) + 0, (s, a. + 0, for each episode k = 1,... K do
for each timestep t 1,........... H do
Take action a t arg max, (s)
Receive r r(st, dt, 1) and 81+1-
Increment (ss;, 0,,
Qr(s,, - (1 7/N (Q a:) nw +b min max, Qt+ ($141, d')).
end end
function 1 as (NVs, + 1)- for sufficiently large M. However, since gradient descent cannot completely overwrite the Q-value estimate for state-action pair after single update, it is beneficial to have a smaller hyperparameter M that governs how quickly the optimism decays.
For worst case analysis assume all Q-value estimates scenario where all rewards are nonnegative, the lowest possible return for an episode is zero. If we then zero-initialise pessimistic initialisation. As shown in 2 leeft) we cannot predict how a neural network will generalise, and thus we cannot predict if the Q-value estimates for unvisited state-action pairs will be optimistic or pessimistic. We thus assume they are pessimistic in order to perform a worst case analysis. However, this is not requirement: our method works with any initialisation and rewards.
pessimistic. In the common
Q-value estimates, is common for neural networks,
starting with
In order to then approximate an optimistic initialisation, the scaling parameter C in equation T can be chosen to guarantee unseen Q -valuess are overestimated, for example, C == H in the undiscounted finite-horizon tabular setting and C' := 1/(1 ?) in the discounted episodic setting (assuming 1 the maximum reward obtainable each timestep). However, in some environments it may be beneficial to use a smaller parameter C' for faster convergence. These Q Q*-vvales are then used both during action selection and during bootstrapping. Note that the finite horizon setting the counts N, and thus Q+ would depend on the timestep I.
Hence, we split the optimistic + into two parts: a pessimistic Q-value component and an optimistic component based solely the counts for state-action pair. This separates our source of optimism from the neural network function approximator, yielding Q that remain high for unvisited state-action pairs, assuming suitable counting scheme. Figure 2 (right) shows the effects of adding this optimistic component to a network's outputs.
Optimistic Q+ -aauue provide increased incentive to explore. By using optimistic Q+ esti- mates, especially during action selection and bootstrapping, the agent is incentivised to try and visit novel state-action pairs. Being optimistic during action selection in particular encourages the agent try novel actions that have not yet been visitied. Without an optimistic estimate for novel state-action pairs the agent would have no incentive to try an action it has never taken before Being optimistic during bootstrapping ensures the agent is incentivised to return to states in which it has not yet tried every action. This because the maximum Q* --alue will be large due to the optimism bonus. Both of these effects lead to strong incentive to explore novel state-action pairs.
given state.
3.2 TABULAR REINFORCEMEN LEARNING
In order ensure that OPIQ has strong theoretical foundation, must ensure it is provably efficient in the tabular domain. We restrict our analysis to the finite horizon tabular setting and only consider building upon UCB-H (Jin al. 2018) for simplicity. Achieving better regret bound using UCB-B (Jin et al. 2018) and extending the analysis to the infinite horizon discounted setting (Dong al. 2019) steps for future work.
Our algorithm removes the optimistic initialisation of UCB-H, instead using a pessimistic initialisation Q+-values during action selection and bootstrapping.
(all Q-values start at 0). We then Pseudocode is presented in Algorithm
4

---

Published as a conference paper at ICLR 2020
Theorem 1. For any p E (0, (0,1), with probability at least - p the total regret of Q* is at most D(VHASATI (ogTpp/p))) for M 2 1 and at most O (HH++ SAT - AO for < M < 1
The proof is based on that of Theorem 1 from (Jin et al. 2018 Our Q+-values are always greater than or equal to the Q-values that UCB-H would estimate, thus ensuring that our estimates are also greater than or equal to Q*. Our overestimation relative to UCB-H is then governed by the quantity (s(N(ss, a) + 1)M which when summed over all timesteps does not depend on T for M > 1. As M we exactly recover UCB-H, and match the asymptotic performance of UCB-H for M 2 1. Smaller values of M result in our optimism decaying more slowly, which results in more exploration. The full proof included in Appendix]] !
We also show that OPIQ without optimistic action selection or the count- bastd intrinsic motivation term by is not provably efficient by showing can incur linear regret with high probability on simple MDPs (see Appendices and and H
Our primary motivation for considering tabular algorithm that pessimistically initialises its Q-values, is to provide firm theoretical foundation on which to base deep RL algorithm, which we describe in the next section.
3.3 DEEP REINFORCEMENT LEARNING
For deep RL, we base OPIQ DQN (Mnih et al. 2013), which uses deep neural network with parameters 0 as a function approximator Qu. During action selection, we use our Q+ -values to determine the greedy action:
Caction
at = arg max (Qo(s,a) + (N(s, 1)
where Caction a hyperparameter governing the scale the optimistic bias during action selection. In practice, we use an e-greedy policy. After every timestep, we sample a batch of experiences from our experience replay buffer, and use n-step Q-learning (Mnih et al.) 2016). We recompute the counts for each relevant acttin pair, to avoid using stale pseudo-rewards, The network is trained by gradient decent on the loss in equation 2
with the target:
V/ Σ ydth (((stts00te)) (iscci.ote)) +
a' max ( d')+ (N(sttn, a') ) 1)ars (4)
Choctstrap
)
where Chaoostrpp a hyperparameter that governs the scale of the optimistic bias during bootstrapping.
For our final experiments on Montezuma's Revenge we additionally use the Mixed Monte Carlo (MMC) target (Bellemare et al.) 2016 Ostrovski et al., (017). which mixes the target with the environmental monte carlo return for that episode. Further details are included in Appendix D.4
We use the method of static hashing (Tang et al., 2017) to obtain our pseudocounts on the first 2 of 3 environments we test on. For our experiments on Montezuma's Revenge we count over downsampled image of the current game frame. More details can be found Appendix B
A DQN with pseudocount derived intrinsic reward (DQN PC) (Bellemare al. 2016) can be seen as a naive extension of UCB-H to the deep RL setting. However, it does not attempt to ensure optimism in the Q-values used during action selection and bootstrapping. which is crucial component of UCB- H. Furthermore, even if the Q-values were initialised optimistically at the start of training they would not remain optimistic long enough to drive exploration, due to the of neural networks. OPIQ, on the other hand, is designed with these limitations of neural networks in mind. By augmenting the neural network's Q-value estimates with optimistic bonuses of the form (N(*.a)+1)ır OPIQ
ensures that the Q +vauue used during action selection and bootstrapping are optimistic. We can thus consider OPIQ as deep version of UCB-H. Our results show that optimism during action selection and bootstrapping is extremely important for ensuring efficient exploration.
4 RELATED WORK
Tabular Domain: There is a wealth of literature related to provably efficient exploration in the tabular domain. Popular model-based algorithms such R-MAX (Brafman and Tennenholtz 2002
5

---

Published as a conference paper at ICLR 2020
MBIE (and MBIE-EB) (Strehl and Littman 2008 UCRL2 (Jaksch et al. 2010) and UCBVI (Azar ct al. 2017) are all based on the principle of optimism in the face of uncertainty. Osband and Van Roy (2017) adopt Bayesian viewpoint and argue that posterior sampling (PSRL) (Strens 2000) is more
practically efficient than approaches that are optimistic in the face of uncertainty, and prove that in Bayesian expectation PSRL matches the performance of any optimistic algorithm up constant factors. Agrawal and Jia (0177) prove that an optimistic variant of PSRL is provably efficient under a frequentist regret bound.
The only provably efficient model-free algorithms to date are delayed Q-learning (Strehl et al. 2006) and UCB-H (and UCB-B) (Jin et al. 2018). Delayed Q-learning optimistically initialises the Q-values that are carefully controlled when they are updated. UCB-H and UCB-B also optimistically initialise the Q-values, but also utilise count-based intrinsic motivation term and a special learning rate to achieve a favourable regret bound compared to model-based algorithms. In contrast, OPIQ pessimistically initialises the Q-values. Whilst we base our current analysis on UCB-H, the idea of augmenting pessimistically initialised Q-values can be applied to any model-free algorithm.
A popular approach to improving exploration in deep RL is to utilise intrinsic motivation (Oudeyer and Kaplan| 2009), which computes quantity to add to the environmental reward. Most relevant to our work is that of Bellemare et al. (2016), which takes inspiration from MBIE-EB (Strehl and Littman 2008). [ellemare et al. (2016) utilise the number of times a state has been visited to compute the intrinsic reward. They outline a framework for obtaining approximate counts, dubbed pseudocounts, through learned density model over the state space. Ostrovski et al. (2017) extend the work to utilise a more expressive PixeICNN (van den Oord et al., 2016)) as the density model, whereas Fuu al. (2017) train a neural network as a discriminator to also recover a density model. Machado et al. (2018g (8)) instead use the successor representation to obtain generalised counts. Choi et al. (2019) learn a feature space to count that focusses on regions of the state space the agent can control, and Pathak et al. (2017) learn similar feature space in order to provide the error of a learned model as intrinsic reward. A simpler and more generic approach to approximate counting is static hashing which projects the state into a lower dimensional space before counting (Tang et al. 2017). None of these approaches attempt to augment or modify the Q-values used for action-selection bootstrapping, and hence do not attempt to ensure optimistic values for novel state-action pairs.
Deep RL Setting:
Chen et al. (217)) build upon bootstrapped DQN (Osband al. 2016) to obtain uncertainty estimates over the Q-values for a given state in order to act optimistically by choosing the action with the largest UCB. However, they do not utilise optimistic estimates during bootstrapping. [Osand et al. (2018) also extend bootstrapped DQN to include a prior by extending RLSVI (Osband et al. 2017)) to deep RL. al. (2017) show that RLSVI achieves provably efficient Bayesian expected regret, which requires a prior distribution over MDPs, whereas OPIQ achieves provably efficient worse case regret. Bootstrapped DQN with a prior is thus model-free algorithm that has strong theoretical support in the tabular setting. Empirically, however, its performance on sparse reward tasks is worse than DQN with pseudocounts.
Machado et al. (2015) shift and scale the rewards so that zero- pero-initialisation is optimistic. When applied to neural networks this approach does not result in optimistic Q-values due the generali- sation of the networks. |Bellemare et al.) (2016) empirically show that using a pseudocount intrinsic motivation term performs much better empirically on hard exploration tasks.
Choshen et al. (2018) attempt to generalise the notion of count to include information about the counts of future state-actions pairs in a trajectory, which they use to provide bonuses during action selection. Oh and Iyengar (2018) extend delayed Q-learning to utilise these generalised counts and prove the scheme is MDP. The generalised counts are obtained through E-values which are learnt using SARSA with constant 0 reward and E-value estimates initialised 1. When scaling to the deep RI. setting, these E-values are estimated using neural networks that cannot maintain their initialisation for unvisited state-action pairs, which is crucial for providing an incentive to explore. By contrast, OPIQ uses a separate source to generate the optimism necessary to explore the environment.

---

Published as a conference paper at ICLR 2020
5 EXPERIMENTAL SETUP
We compare OPIQ against baselines and ablations on three sparse reward environments. The first a randomized version the Chain environment proposed by Osband et al. (2016) and used in (Shyam et al., 2019) with chain of length 100, which we call Randomised Chain. The second is two-dimensional maze in which the agent starts in the top left corner (white dot) and is only rewarded upon finding the goal (light grey dot). We use image of the maze as input and randomise the actions similarly to the chain. The third is Montezuma's Revenge from Arcade Learning environment (Bellemare et al. 2013), notoriously difficult sparse reward environment commonly used benchmark to evaluate the performance and scaling of Deep RL exploration algorithms.
See Appendix for further details on the environments, baselines and hyperparameters used
5.1 ABLATIONS AND BASELINES
We compare OPIQ against a variety of DQN- approaches that use pseudocount intrinsic rewards, the DORA agent (Choshen al. 2018 (which generates count-like optimism bonuses using a neural network), and two strong exploration baselines:
e-greedy DQN: standard DQN that uses an e-greedy policy to encourage exploration. We anneal
linearly over a fixed number of timesteps from 1 to 0.01.
DQN + PC: we add an intrinsic reward of // //VVNss. a) to the environmental reward based on
(Bellemare al. 2016 Tang et al.) (017)).
DQN R-Subtract (+PC): we subtract constant from all environmental rewards received when training, so that a zero-initialisation is optimistic, as described for a DQN in (Bellemare al., 2016)
and based on Machado et al. (2015).
DQN Bias (+PC): we initialise the bias of the final layer of the DQN to a positive value at the start of training as a simple method for optimistic initialisation with neural networks.
DQN + DORA: we use the generalised counts from (Choshen et al.) 2018) as an intrinsic reward.
DQN + DORA OA: additionally use the generalised counts provide optimistic bonus during
action selection.
DQN RND: we add the RND bonus from (Burda al. 2018) as intrinsic reward.
BSP: we use Bootstrapped DQN with randomised prior functions (Osband et al. 2018).
In order to better understand the importance of each component of our method, we also evaluate the following ablations:
Optimistic Action Selection (OPIQ w/o OB): we only use our Q+-values during action selection, and use Q during bootstrapping (without Optimistic Bootstrapping). The intrinsic motivation term remains.
Optimistic Action Selection and Bootstrapping (OPIQ w/o PC): we use our Qt-uus during action selection and bootstrapping, but do not include an intrinsic motivation term (without Pseudo Counts).
6 RESULTS
6.1
RANDOMISED CHAIN
We first consider the visually simple domain of the randomised chain and compare the count-based methods. Figure shows the performance of OPIQ compared to the baselines and ablations. OPIQ significantly outperforms the baselines, which do not have any explicit mechanism for optimism during action selection. A DQN with pseudocount derived intrinsic rewards unable to reliably find the goal state, but setting the final layer's bias to one produces much better performance. For the DQN variant in which a constant is subtracted from all rewards, all of the configurations (including those with pseudocount derived intrinsic bonuses) were unable to find the goal the right and thus the agents learn quickly to latch on the inferior reward of moving left.
Shows
Compared to its ablations, OPIQ is more stable in this task. OPIQ without pseudocounts performs similarly to OPIQ but is more varied across seeds, whereas the lack of optimistic bootstrapping results in worse performance and significantly more variance across seeds.
"ooee available http://gthhuh.cmmooww/////ggggg

---

Published as a conference paper at ICLR 2020
6.2 MAZE
We next consider the harder and more visually complex task of the Maze and compare against all baselines.
shows that only OPIQ is able to find the goal in the sparse reward maze. This indicates that explicitly ensuring optimism during action selection and bootstrapping can have a significant positive impact in sparse reward tasks, and that a naive extension of UCB H to the deep RL setting (DQN + PC) results in insufficient exploration.
Figure 4 (right) shows that attempting to ensure optimistic Q-values by adjusting the bias of the final layer (DQN Bias + PC), or by subtracting a constant from the reward (DQN R-Subtract + PC) has very little effect.
As expected DQN + RND performs poorly on this domain compared to the pseudocount based methods. The visual input does not vary much across the state space, resulting in the RND bonus failing to provide enough intrinsic motivation to ensure efficient exploration. Additionally it does not feature any explicit mechanism for optimism during action selection, and thus Figure 4 (right) shows it explores the environment relatively slowly.
Both DQN+DORA and DON+DORA OA also perform poorly in this domain since their source of intrinsic motivation disappears quickly, As noted in Figure 2 neural networks do not maintain their starting initialisations after training. Thus, the intrinsic reward DORA produces goes to 0 quickly since the network producing its bonuses learns to generalise quickly.
BSP is the only exploration baseline we test that does not add an intrinsic reward to the environmental reward, and thus it performs poorly compared to the other baselines on this environment.
Figure 5 shows that OPIQ and all its ablations manage to find the goal in the maze. OPIQ also explores slightly faster than its ablations (right), which shows the benefits of optimism during both action selection and bootstrapping. In addition, the episodic reward for the the ablation without optimistic bootstrapping is noticeably more unstable (Figure 5 left). Interestingly, OPIQ without pseudocounts performs significantly worse than the other ablations. This surprising since the theory suggests that the count-based intrinsic motivation is only required when the reward transitions of the MDP are stochastic (Jin et al. 2018), which is not the case here. We hypothesise that adding PC-derived intrinsic bonuses to the reward provides easier learning problem, especially when using n-step Q-Learning, which yields the performance gap.
However, results show that the PC-derived intrinsic bonuses are enough their own to ensure sufficient exploration. The large difference in performance between DQN PC and OPIQ w/o OB important, since they only differ in the use of optimistic action selection. The results in Figures
4 and 5 show that optimism during action selection is extremely important in exploring the environment efficiently. Intuitively, this makes sense, since this provides an incentive for the agent to try actions it has never tried before, which is crucial in exploration.
Figure 6 visualises the values used during action selection for DQN PC agent and OPIQ. showing the based augmentation provides optimism for relatively novel state-action pairs, driving the agent explore more of the state-action space.
12
QPIQ
OPIQ
Teat Reward
10
DON grerddy
Median Test Reward
10
QPIQ wife OB
DQN
OPIQ
DON Bis PC
DON R-Subtract
e
10kk
00k
B0k
100k
20k
BBk
Figure 3: Results for the randomised chain environment. Median across 20 seeds is plotted and the 25%-75% quartile is shown shaded. Left: OPIQ outperforms the baselines. Right: OPIQ is more stable than its ablations.
8

---

Published as a conference paper at ICLR 2020
10
350
QPIQ
D-N
Median Episode Reward
Median States Visited
300
DON Blas PC
DQN- PC
DQN R-Suptrct PC
250
DQN DORA
DQN DORA
200
DQN RND
4
150
100
200K
400k
800K
1000k
200k
400k
BOOk
800K 1000k
Figure 4: Results for the maze environment comparing OPIQ and baselines. Median across 8 seeds is plotted and the 25%-75% quartile is shown shaded. Left: The episode reward. Right: Number of distinct states visited over training. The total number of states in the environment is shown dotted line.
350
OPIQ
OPIQ wlo
Median Episode Reward
Median States Visited
300
OPIQ w/o
8
250
200
150
100
200K
400k
600K
800K
1000k
200k
400K
600k
80CK
1000k
Figure 5: Results for the maze environment comparing OPIQ and ablations. Median across 8 seeds plotted and the 75% quartile is shown shaded. Left: The episode reward. Right: Number of distinct states visited over training. The total number of states in the environment is shown as dotted line.
T
Figure 6: Values used during action selection for each of the 4 actions. The region in blue indicates states that have already been visited. Other colours denote Q-values between 0 (black) and 10 (white). Left: The Q-values used by DQN with pseudocounts. Right: +v-uus used by OPIQ with Caction 100.
6.3 MONTEZUMA'S REVENGE
Finally, consider Montezuma's 's Revenge, one of the hardest sparse reward games from the ALE (Bellemare et al. 2013). Note that we only train up to 12.5mil timesteps (50mil frames), a 1/4 the usual training time (50mil timesteps, 200mil frames).
Figure shows that OPIQ significantly outperforms the baselines in terms of the episodic reward and the maximum episodic reward achieved during training. The higher episode reward and much higher maximum episode reward OPIQ compared to DQN + PC once again demonstrates the importance of optimism during action selection and bootstrapping.

---

Published as a conference paper at ICLR 2020
3000
QPIQ
Median Max Episade Reward
6000
DQN PC
Median Episode Reward
DQN RND
5000
DSP
2000
4000
1500
3000
1000
1000
Do
2m
4m
6m
10m
12m
4m
6m
8m
10m
12m
T
Figure 7: Results for Montezuma's Revenge. Median across 4 seeds is plotted and the 25%-75% quartile is shown shaded. Left: The episode reward. Right: The maximum reward achieved during an episode.
DQN PC
Median Rooms Visited
DQN RND BSP
10
8
2m
4m
6m
8m
10m
12m
Figure 8: Further Results for Montezuma's Revenge showing the number of rooms visited over training comparing OPIQ and baselines. Median across 4 seeds is plotted and the 25%-75% quartile shown shaded.
In this environment BSP performs much better than in the Maze, but achieves significantly lower episodic rewards than OPIQ.
Figure 8 shows the distinct number of rooms visited across the training period. We can see that OPIQ manages to reliably explore 12 rooms during the 12.5mil timesteps, significantly more than the other methods, thus demonstrating its improved exploration in this complex environment.
Our results on this challenging environment show that OPIQ can scale to high dimensional complex environments and continue provide significant performance improvements over an agent only using pseudocount based intrinsic rewards.
7 CONCLUSIONS AND FUTURE WORK
This paper presented OPIQ. a model-free algorithm that does not rely on an optimistic initialisation to ensure efficient exploration. Instead, OPIQ augments the Q- Qavauues estimates with a count-based optimism bonus. We showed that this is provably efficient in the tabular setting by modifying UCB-H to use a pessimistic initialisation and our augmented + -values for action selection and bootstrapping. Since method does not rely on specific initialisation scheme, it easily scales deep RL when paired with an appropriate counting scheme. Our results showed the benefits maintaining optimism both during action selection and bootstrapping for exploration environments including Montezuma's 's Revenge. In future work, we aim to extend OPIQ by integrating it with more expressive counting schemes.
number of hard sparse reward
10

---

Published as a conference paper at ICLR 2020
8 ACKNOWLEDGEMENTS
We would like to thank the entire WhiRL lab for their helpful feedback, in particular Gregory Farquhar and Supratik Paul. We would also like thank the anonymous reviewers for their constructive ments during the reviewing process. This project has received funding from the European Research Council (ERC), under the European Union's i Horizon 2020 research and innovation programme (grant agreement number 637713). It was also supported by an EPSRC grant (EP/M508) 1 1/1, EP/N509711/1), The experiments were made possible by generous equipment grant from NVIDIA and the JP Morgan Chase Faculty Research Award.
REFERENCES
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, pages 1 1184-1194, 2017.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning, pages 263-272, 2017.
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, pages 1471-1479, 2016.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Ronen I Brafmma and Moshe Tennenholtz. R-MAX a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(021) 2002.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: /8/0. /2894, 2018.
Richard Chen, John Schulman, Pieter Abbeel, and Szymon Sidor. UCB and infogain exploration via Qennsembles. arXiv preprint arXiv: /706000007 2017.
Jongwook Choi, Yijie Guo, Marcin Moczulski, Junhyuk Oh, Neal Wu, Mohammad Norouzi, and Honglak Lee. Contingency-awant exploration reinforcement learning. In International Confer- on Learning Representations, 2019.
Leshem Choshen, Lior Fox, and Yonatan Loewenstein. Dora the explorer: Directed outreaching reinforcement action-selection. In International Conference on Learning Representations, 2018.
Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. arXiv preprint 1901 09311, 2019.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: new approach for hard eeploraxloot problems. arXiv preprint 1rXiv:1901.1099) 2019.
Li Fan, Pei Cao, Jussara Almeida, and Andrei Z Broder. Summary cache: a scalable wide-area web cache sharing protocol. JEEE/ACM Transactions on Networking (TON), 8(3):281-225 -293, 2000.
Justin Fu, John Co-Reyes, and Sergey Levine. EX2: Exploration with exemplar models for deep reinforcement learning. In Advances in Neural Information Processing Systems, pages 2577-2587, 2017.
Sudhir K Goel and Dennis M Rodriguez. A note on evaluating limits using riemann sums. Mathe- matics Magazine, (0(4):225-222 1987.
Danijar Hafner, Timothy Lillicrap, lan Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In Proceedings of the 36th International Conference Machine learning, 2019.

---

Published as a conference paper at ICLR 2020
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Thomas Jaksch, Ronald Ortnr,, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563-1600 2010.
Chi Jin, Zeyuan Allen- Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863 4873,483, 2018.
Long-Ji Lin. Self- seff-impro reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4):293-33 321, 1992.
Marlos C Machado, Sriram Srinivasan, and Michael H Bowling. Domain-indeeendent optimistic initialization for reinforcement learning. In AAAI Workshop: Learning for General Competency in Video Games, 2015.
Marlos C Machado, Mare Bellemare, and Michael Bowling, Count-based exploration with the successor representation. arXiv preprint arXiv:/801) /622, 2018a.
Marlos C Machado, Marc G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018b.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51 518(7540):529, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of the 33rd International Conference Machine Learning, pages 1937, 2016.
Min-hwan Oh and Garud lyengar. Directed exploration in PAC model-free reinforcement learning. arXiv preprini arXiv: 10552, 2018.
Ian Oshand and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Proceedings of the 34th International Conference on Machine Learning, pages 2701- 2710, 2017.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in Newral Information Processing Systems, pages 4026-4034, 2016.
Ian Osband, Daniel Russo, Zheng Wen, and Benjamin Van Roy. Deep exploration via randomized value functions. arXiv preprint IrXiv::70s: 07608, 2017.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. In Advances in Neural Information Processing Systems, pages 8617-8629, 2018
Georg Ostrovski, Marc G Bellemare, Aaron den Oord, and Rémi Munos. Count-based exploration with neural density models. arXiv preprint
2017.
Pierre-Yvel Oudeyer and Frederic Kaplan. What is intrinsic motivation? a typology of computational approaches. Frontiers in neurorobotics, 1:6, 2009.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Muriosity-driver exploration by self-supervised prediction. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Pranav Shyam, Wojeiech Jaškowski, and Faustino Gomez. Model-based active exploration. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Alexander L Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 1309-1330-1331, 2008.
12

---

Published as a conference paper at ICLR 2020
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model- free reinforcement learning. Proceedings of the 23rd International Conference on Machine learning, pages 881-888 ACM, 2006.
Malcolm Strens. A bayesian framework for reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning, pages 943-950, 2000.
Adrien Ali Taiga, Aaron Courville, and Mare G Bellemare. Approximate exploration through state abstraction. arXiv preprint arXiv:1808.0983 2018.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. Advances in Neural Information Processing Systems, pages 2753 2762, 2017.
Aaron van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, al. Conditional image generation with pixelenn decoders. In Advances in Neural Information Processing Systems, pages 4790 4798, 2016.
13

---

Published as a conference paper at ICLR 2020
A BACKGROUND
A. TABULAR REINFORCEMENT LEARNING
For the tabular setting, we consider a discrete finite-horizon Markov Decision Process (MDP), which can be defined as tuple (S, A, {Pt), {Ra), H, p). where S is the finite state space, A is the finite action space, (- , a) is the state trattetraniiiion distribution for timestep = -,.... H, R-(- a) is the distribution over rewards after taking action in state H is the horizon, and p is the distribution over starting states. Without loss of generality we assume that (= a) E [0. 1]. We use and A to denote the number of states and the number of actions, respectively, and N N(s, a, L) as the number of times a state-action pair (s, a) has been visited at timestep t.
Our goal is to find set of policies n. S A. ग {me). that chooses the agent's actions time t such that the expected sum of future rewards is maximised. To this end we define the Q-value at time of a given policy π as Q7 (s, a) == E r + Q7+1 (s', 1 -- ( where 0, VI H. The agent interacts with the environment for K episodes, T == K HH, yielding a total regret: Regret( = Σ (max.- QF' (sf कं (of) QF (sf mf (sf))) Here of refers to the starting state and n* to the policy at the beginning of episode k. We are interested in bounding the worst case total regret with probability p. < p
Q7 (s)
UCB-H (Jin et al. 2018) is an online Q-learning algorithm for the finite-horizon setting outlined above where the worse case total regret is bounded with a probability of 1 ppp -pby by O( (H''SAS AST(SA//p) All Q-values for timesteps t < H are optimistically initialised at H. The learning rate is defined as Nι = H where N == N (s,, dz t) is the number of times state-action pair (st, a,) has been observed at step Ê and = 1 at the first encounter of any state-action pair. The update rule for transition step from state St to 5e+1, 1, after executing action 0, and receiving reward rr, is:
H+1
Qz 0z) + (1 - 7N) Q2 (sc. 0e) + NN (re + 6% + min H, max Q141 a')3), (5)
where 6/ == 2 Hllog(SAT/y) /p) is the count-based intrinsic motivation term
N
B COUNTING IN LARGE, COMPLEX STATE SPACES
In deep RL, the primary difficulty for exploration based count- count-based intrinsic rewards is obtaining appropriate acteonction counts. In this paper we utilise approximate counting schemes (Bellemare) let al. 2016 Ostrovski et al. 2017: Tang et al. 2017) in order to cope with continuous and/or high- dimensional state spaces. In particular, for the chain and maze environments we use static hashing (Tang al. 2017), which projects state s low-dimensional feature vector (bs) = sign (s)),) where / flattens the state into a single dimension of length D; A is & D matrix whose entries are initialised i.i.d. from a unit Gaussian: (0, 1); and is a hyperparameter controling the granularity of counting: higher l leads to more distinguishable states at the expense of generalisation.
Given the vector (ss), we use a counting bloom filter (Fan et al. 2000) to update and retrieve its counts efficiently. To obtain counts N (ss, a) for state-action pairs, we maintain separate data structure counts for each action (the same vector do(s) used for all actions). This counting scheme is tabular and hence the counts for sufficiently different states do not interfere with one another. This ensures Q -values for unseen state-action pairs in equation are large.
For our experiments on Montezuma's 's Revenge we use the same method of downsampling in (Ecoffet et al., 2019), in which the greyscale state representation is resized from (42x42) to (1 (1x8) and then binned from {0...,, 255} into 8 categories. We then maintain tabular counts over the new representation.
C GRANULARITY OF THE COUNTING MODEL
The granularity of the counting scheme is an important modelling consideration. If it is too granular, then will assign an optimistic bias in regions of the state space where the network should trusted
Jin al. 2018 use 3c s.s.L by = cv 1 SAT/p) in their proof, but we find that 2 suffices.
14

---

Published as a conference paper at ICLR 2020
to generalise. On the other hand, if is too coarse then it could fail provide enough of optimistic bias in parts of the state space where exploration is still required. Figures shows the differences between 2 levels of granularity. [Taiga al. (2018) provide much more detailed analysis on the granularity of the count-based model, and its implications on the learned Q-values.
2
Figure 9: We consider the counting scheme from Figure 2
but vary the number of bins used. Left: bins used. Only the data points far from the training data given optimistic bias. Right: 50 bins are used. An optimistic bias is given to all data points that are not very close to the training data.
D EXPERIMENTAL SETUP
D.1 ENVIRONMENTS
D.1.1 RANDOMISED CHAIN
A randomized version of the Chain environment proposed by Osband et al. (2016) and used in (Shamm al. 2019). We use a Chain of length 100. The agent starts the episode State and interacts with the MDP for 109 steps, after which the agent is reset. The agent has actions that can move Left or Right. the beginning of training the action which takes the agent left or right at each state is randomly picked and then fixed. The agent receives reward of 0.001 for going Left in State 1, a reward of 1 for going Right in State 100 and no reward otherwise. The optimal policy thus to pick the action that takes it Right each timestep. Figure 10 shows the structure of the 100 Chain. Similarly to Osband et al. (2016) we use a thermometer encoding for the state:
((s) = (L S s}) E {0, 1)
Start State
00.001
Figure 10: 100 Chain environment.
1.1.2 MAZE
2-dimensional gridworld maze with a sparse reward in which the agent can move Up, Down, Left or Right. The agent starts each episode at fixed location and must traverse through the maze in order to find the goal which provides +10 reward and terminates the episode, all other rewards are 0. The agent interacts with the maze for 250 timesteps before being reset. Empty space is represented by a O. walls are 1, the goal is 2 and the player is 3. The state representation is a greyscaled image of the entire grid where each entry is divided by to lie in [0, 1]. The shape of the state representation is: (24, 24, 1). Once again the effect of each action is randomised at each state at the beginning of training. Figure TT shows the structure of the maze environment.
15

---

Published as a conference paper at ICLR 2020
Figure 11: Maze environment.
D.1.3 MONTEZUMA'S REVENGE
We follow the suggestions in (Machado et al. 2018b) and use the same environmental setup used in (Burda al. 2018). Specifically, we use stick actions with a probability p = 0.25, frame skip of 4 and do not show a terminal state the loss of life.
D.2 HYPERPARAMETERS AND NETWORK ARCHITECTURES
In all experiments we set 7 = 0.99, use RMSProp with learning rate of 0.0005 and scale the gradient norms during training to be at most 5.
D.2.1 RANDOMISED CIIAIN
The network used is MLP with 2 hidden layers of 256 units and ReLU non-lincarities. We use 1 step Q-Learnin.
Training lasts for 100k timesteps. is fixed at 0.01 for all methods except for e-greedy DQN in which it is linearly decayed from 1 to 0.01 over {100, 50k, 100k] timesteps. We train on batch size of 64 after every timestep with replay buffer of size 10k. The target network is updated every 200 timesteps. The embedding size used for the counts is 32. We set 3 0.1 for the scale of the count-based intrinsic motivation.
For reward subtraction we consider subtracting 1, from the reward. For an optimistic initialisation bias, consider setting the final layer's bias {0.1, 10). We consider both of the methods with and without count-based intrinsic motivation.
For OPIQ and its ablations we consider: M E (0.1, 2, 10), Caetion {0.1, 1, 10}, Chootstrap (0.01,
For all methods considered. We then sort them by the median test reward (largest area underneath the line) and report the median, lower and upper quartiles.
20 independent across the pros-prroduct of all relevant parameters
The best hyperparameters we found were:
DQN e-greedy: Decay rate: 100 timesteps.
Optimistic Initialisation Bias: Bias: 1, Pseudocount intrinsic motivation: True.
Reward Subtraction: Constant to subtract: Pseudocount intrinsic motivation: False.
OPIQ: M: 0.5, Cuction 1, Choonstrap 1.
OPIQ without Optimistic Bootstrapping: M: 2, Caction: 10.
OPIQ without Pseudocounts: M: 2, Castion 10, Opootstrap 10.
For Figure 13 the best hyperparameters for OPIQ with differing values of M are:
M: 0.1: Caction: 10, -boossrapp 1.
M: 0.5: Caction: 1, Obootstrap 1.
M: 2:
Castion 10, C
M: 10: Caction: 10, Obaosstrap: 10.
16

---

Published as a conference paper at ICLR 2020
D.2.2 MAZE
The network used is the following feedforward network:
(State imput: (24,24.1))
->
(Conv Layer, 3x3 Filter, 16 Channels, Stride 2) - ReL.U
(Conv Layer, 3x3 Filter, 16 Channels, Stride 2) ReL.U
- Flatten
+
(FC Layer, 400 Units) ReLU
+ (FC Layer, 200 Units)
+ AA 4 outputs.
We use 3 step Q-Leaming.
Training lasts for Imil timesteps. is decayed linearly from 0.01 over 50k timesteps for all methods except for e-greedy DQN in which it is linearly decayed from 1 to 0.01 over {100, 50k, 100k] timesteps. We train on batch of after every timestep with a replay buffer of size 250k. The target network is updated every 1000 timesteps. The embedding dimension for the counts is 128.
For DQN PC we consider 3 {0.01, 0.1, 1, 10, 100). For all other methods we set / 0.1 performed best.
For reward subtraction we consider subtracting (0.1, 1, 10) from the reward. For an optimistic initialisation bias, we consider setting the final layer's bias to {0.1, 1, 10). Both methods utilise count-based intrinsic motivation.
For OPIQ and its ablations we set M = 2 since it worked best in preliminary experiments. We consider: Caction E (0.1, 1, 10, 1003, Chantstrp E (0.01, 0.1, 10).
For the RND bonus we use the same architecture the DQN for both the target and predictor networks, except the output is of size 128 instead of [|. We scale the squared error by Brnd E {0.001, 0.01, 0.1, 1, 10, 100}:
For DQN + DORA we use the same architecture for the E-network as the DQN. We sigmoid lineaiiey to the output and initialise the final layer's weights and bias to 0 as described in (Choshen jet al. 2018). We sweep across the scale of the intrinsic reward Bdora E (}. For DQN + DORA OA
use Bdora and sweep across Bdora _dtoa_action action E (-.
For BSP we use the following architecture:
Shared conv layers:
(State input: (24,24.1)
+
(Conv Layer, 3x3 Filter, 16 Channels, Stride 2) ReLU
+ (Conv Layer, 3x3 Filter, 16 Channels, Stride 2) > ReL.U
Flatten
Q- Q-value Heads:
(FC Layer, 400 Units) ReLU
+ (FC Layer, 200 Units)
+ AA 4 outputs.
We use K 10 different bootstrapped DQN heads, and sweep over Soep E (0.1, 1, 10, 30, 100}.
For all methods we run independent runs across the cross-product all relevant parameters considered. We then sort them by the median episodic reward (largest area underneath the line) and report the median, lower and upper quartiles.
The best hyperparameters we found were:
DQN e-greedy: Decay rate: 100k timesteps.
DQN + PC: 3 = 0.1.
Optimistic Initialisation Bias: Bias: 1.
Reward Subtraction: Constant to subtract: 0.1.
DQN RND: Brnd 10.
17

---

Published as a conference paper at ICLR 2020
DQN DORA: Pdore 0.01.
DQN + DORA OA: Baora 0.01 and S action 0.1.
BSP: Shep 100.
OPIQ: M: 2, Caction: 100, Chootstrap 0.01.
OPIQ without Optimistic Bootstrapping: M: 2, Cuction: 100.
OPIQ without Pseudocounts: Caction: 100, Choststapp 0.1.
D.2.3 MONTEZUMA'S REVENGE
The network used is the standard DQN used for Atari (Mnih et al. 2015 Bellemare et al. 2016
We 3 step Q-Leaming.
Training lasts for 12.5mil timesteps (50mil frames in Atari). e is decayed linearly from to 0.01 over Imil timesteps. We train on batch of 32 after every 4th timestep with replay buffer of size Imil. The target network is updated every 8000 timesteps.
For all methods we consider 9mme {0.005, 0.01, 0.025).
For DQN PC we consider 3 E {0.01, 0.1,
For OPIQ and its ablations we set M We consider: Caction E (0.1,11).oosttap {0.01, 0.1}. 3 E {0.01,0. 0.1}.
For the RND bonus we the same architectures in (Burda al. 2018 (target network is smaller than the learned predictor network) except we use ReLU non- non-linearity. The output is the same of size 512. We scale the squared error by Brnd E {0.001, 0.01, 13:
For BSP we use the same architecture as in OOsann et al. 2018).
We K 10 different bootstrapped DQN heads, and sweep over Bosp E {0.1, 1, 10, 1003.
For all methods we run 4 independent runs across the cross-product of all relevant parameters considered. We then sort them by the median maximum episodic reward (largest area underneath the line) and report the median, lower and upper quartiles.
The best hyperparameters we found were:
DQN + PC: 3 = 0.01, Ammc 0.01.
DQN RND: Brnd 0.1, 9mmc 0.01.
BSP: 3hap = 0.1, 9mme 0.025.
OPIQ: M= 2, Caction 0.1, Choutstrap 0.01, 9mmm: 0.01.
OPIQ without Optimistic Bootstrapping: M= 2, Caction 0.1, 9mme = 0.005.
D.3 BASELINES TRAINING DETAILS
We do single gradient descent step minibatch of the 32 most recently visited states. We also recompute the intrinsic rewards when sampling minibatches to train the DQN, The intrinsic reward used for state is the squared error between the predictor network and the target network 3rnal (redictorrs)) target(s)]13
DQN RND:
We train the E-values network using n-step SARSA (same as the DQN) with TE = 0.99. We maintain a replay buffer of size (batch size 4) and sample batch size elements to train every timestep. The intrinsic reward we use is 7 lug ((s,a)
DQN DORA:
Baera
DQN DORA OA: We train the DQN DORA agent described above and additionally augment
the valuus used for action selection with Daara
y- log E(s.a)
18

---

Published as a conference paper at ICLR 2020
We train each Bootstrapped DQN head on all of the data from the replay buffer (as is done in (Osband et al., 2016 2018). We normalise the gradients of the shared part of the network by 1/K, where K is the number of heads. The output of each head is Qs ShppPs, where Ps is randomly initialised network (of the same architecture as Qx) which is kept fixed throughout training. Soop is hyperparameter governing the scale of the prior regularisation.
BSP:
D.4 MIXED MONTE CARLO RETURN
For our experiments on Montezuma's 's Revenge we additionally mixed the 3 step Q-Learning target with the environmental rewards monte carlo return for the episode.
That is, the 3 step targets become:
Ymme = (1 Bmmo))B: + Smme!
y (8(4s))
the episode hasn't 't finished yet, we used 0 for the monte carlo return.
Our implementation differs from (Bellemare et al. 2016 Ostrovski et al. 2017) in that we do use the intrinsic rewards as part of the monte carlo return. This because we recompute the intrinsic rewards whenever we are using them as part of the targets for training, and recomputing all the intrinsic rewards for an entire episode (which can be over 1000 timesteps) is computationally prohibitive.
E FURTHER RESULTS
E.1 RANDOMISED CHAIN
Median States Visted
DON Rlw PC PM)
DON grgredy (2])
Median States Vistte
100
GPV2 we (20]
UP 3Ad
DQN PC J20t
(PQQ [X]]
OPIQ
60
40
20
10K 20k
30k
40K 30K 50k 70k BOK 50K ZOOK
10k
20k
30K
40k
50k
60k
70k
30K
30k 100k
Figure 12: The number of distinct states visited over training for the chain environment. The median across 20 seeds is plotted and the 25%- 75% quartile is shown shaded.
OF 0H1 pot GFigg pot
M403
onc 94-1000 20)
Medin Stane Vileed
JuN
30k
206
30%
43k
50c
30kc
70k
50kc
95k
100k
104
206
302
408
506
002
70k
30K
90C
1004
Figure 13: Comparing the performance of E (0.1, 2, 10) on the chain environment. The best hyperparameter combination for the differing values of M is shown. The median across 20 seeds is plotted and the 25%-75% quartile is shown shaded.
We can see that OPIQ and ablations explore the environment much more quickly than the count-bant based baselines. The ablation without optimistic bootstrapping exhibits significantly more variance than the other ablations, showing the importance optimism during bootstrapping. On this simple task the ablation without count-based intrinsic motivation performs par with the full OPIQ. This is most
19

---

Published as a conference paper at ICLR 2020
likely due to the simpler nature of the environment that makes propagating rewards much easier than the Maze. The importance of directed exploration is made abundantly clear by the e-greedy baseline that fails to explore much of the environment.
Figure 1 compares OPIQ with differing values of M. We can clearly see that a small value 0.1 results insufficient exploration, due the over-exploration of already visited state-action pairs. Additionally M is too large then the rate of exploration suffers due to the decreased optimism. On this task found that M 0.5 performed best, but on the harder Maze environment found that M = 2 was better in preliminary experiments.
E.2 MAZE
TRE
Figure 14: The Q* Q-aaue OPIQ used during bootstrapping with Chootstmp 0.01.
Figure 14 shows the values used during bootstrapping for OPIQ. These Q-values show optimism near the novel state-action pairs which provides an incentive for the agent to return to this area of the state space.
E.3 MONTEZUMA'S REVENGE
7000
3500
OPIQ
Median Max Episode Reward
6000
OPIQ wlo OB
Median Episode Reward
3000
2500
5000
2000
4000
1500
3000
1000
2000
500
1000
2m
4m
6m
8mn
10m
12m
2m
4m
6m
8m
10m
12m
OPIQ
OPIQ wio OB
Median Rooms Visited
10
4m
6m
8m
10m
12m
Figure 15: Results for Montezuma's Revenge comparing OPIQ and ablation. Median across 4 seeds is plotted and the 25%-75% quartile is shown shaded.
20

---

Published as a conference paper at ICLR 2020
10
M-0.1
M=0.5
M-1
M=2
0.6
M-10
0.4
0.0
Figure 16:
(a+1)a for various values of M, and the indicator function 1(x < 1} shown in black. Higher values of M provide a better approximation at integer values of x (shown as crosses).
Figure shows further results on Montezuma's Revenge comparing OPIQ and its ablation without optimistic bootstraping (OPIQ w/o OB). Similarly the Chain and Maze results, we can see that OPIQ w/o OB performs similarly to the full OPIQ but has higher variance across seeds.
F
MOTIVATIONS
Figure 16 compares various values of M with the indicator function {ar 1}.
G NECESSITY FOR OPTIMISM DURING ACTION SELECTION
To emphasise the necessity of optimistic Q-value estimates during exploration, analyse the simple failure case for pessimistically initialised greedy Q-learning provided in the introduction. We use Algorithm 1 but use Q instead of Q+ for action selection. We will assume the agent will act greedily with respect to its Q-value estimates and break ties uniformly:
Uniform arg max Qe(st.a)).
Consider the single state MDP in Figure with H 1. We use this MDP to show that with 0.5 probability pessimistically initialised greedy Q-learning never finds the optimal policy.
0.1
+1
Figure 17: A simple failure case for pessimistically initialised greedy Q-learning. There is I state with actions and H The agent receives 0.1 reward for the left action and for the right action.
The agent receives reward of +1 for selecting the right action and 0.1 otherwise. Therefore the optimal policy is to select the right action. Now consider the first episode: Va, Qi a) = 0. Thus, the agent selects action at random with uniform probability. If it selects the left action, updates:
(s L) = m 0.1
Tint
>
MDP reward
Intrinsic Reward
Bootstrap
Thus, in the second episode it selects the left action again, since Q L) 0 = (s, Our (s, L) never drops below 0.1, and so the right action never taken. Thus, with probability of it never selects the correct action (also linear regret of 0.97).
estimate of (s
This counterexample applies for any nen-negative intrinsic motivation (including no intrinsic motiva- tion), and is unaffected if utilise optimistic bootstrapping not.
H NECESSITY FOR INTRINSIC MOTIVATION BONUS
Despite introducing an extra optimism term with tunable hyperparameter M, OPIQ still requires the intrinsic motivation term be ensure does not under-explore in stochastic environments.
21

---

Published as a conference paper at ICLR 2020
We will prove that OPIQ without the intrinsic motivation term bf does not satisfy Theorem Specifically we will show that there exists a state, 2 action MDP with stochastic reward function such that for all M > 0 the probability of incurring linear regret is greater than the allowed failure probability We choose to use stochastic rewards as opposed to stochastic transitions for a simpler proof.
a
Figure 18: The parametrised MDP.
The MDP we will use shown in Figure 18, where > and a E (0, 1) s.tp <1 H 1, and A = 2. The reward function for the left action is stochastic, and will return +1 reward with probability a and 0 otherwise. The reward for the right action is always a/A.
Let > O, the probability with which we are allowed to incur total regret not bounded by the theorem. OPIQ cannot depend on the value of or a as they are unknown.
log(2) Log( Tox(1
Pick À s.t M
OPIQ will recover the sub-optimal policy of taking the right action if every time we take the left action receive 0 reward. This will happen since our Q+ -vauue estimate for the left action will eventually drop below the Q-value estimate for the right action which is a/ a/A > 0. The sup-optimal policy will incur linear regret, which not bounded by the theorem.
Our probability of failure is at least (1 - a)x, where R is the number of times we select the left action, which decreases R increases. This corresponds to receiving a reward for every one of the R left transitions we take. Note that (1 a)* " is an underestimate of the probability of failure.
For the first 2 episodes we will select both actions, and with probability - a) the left action will return 0 reward. Our Q-values will then be: Q1 (s, L) = 0, Q1 (s, Rt) a/X
is possible take the left action long as
R + 1)M 2 a
X²
since the optimistic bonus for the right action decays O.
This then provides very loose upper bound for R. as (2) which then leads to a further underes-
timation of the probability of failure.
Assume for contradiction that (1 a) < p.
(1 - a) <p + (1 - (1-a)(1/)) (//)//1 <p
(2/a)2/a5 log(1 a) log(p)
(MM > log(p)) log a)
(1/M) log(A/a) > log(log(p)/ log(11 -)))
< (ogga//))//aaao (otl/////oolgg///////o/ logh)//ooogg11/
(6)
This provides our contradiction as we choose À s.t M > (og(A//)/ loggl//llllll))))/ log(1 - a)). We can always pick such À because log(A/a) can get arbitrarily close to 0.
So our probability failure (of which (1 a)* R2 is severe underestimate) is greater than the allowed probability of failure p.
22

---

Published as a conference paper at ICLR 2020
1 PROOF OF THEOREM 1
Theorem 1. For any p E (0, 1). with probability at least p the total regret of Q* is at most O(v HT log (SAT)) for M 2 aadd al most O(H2+ ( SATI-M for 0 < M <.
OPIQ is heavily based on UCB-H (Jin et al., 2018). and as such the proof very closely mirrors its proof except for a few minor differences. For completeness, we reproduce the entirety the proof with the minor adjustments required for our scheme.
The proof is concerned with bounding the regret of the algorithm after episodes. The algorithm we follow takes as input the value of K, and changes the magnitudes of byy based on it.
We will make use of corollary to Azuma's 's inequality multiple times during the proof.
Theorem 2. (Azuma's 's Inequality. Let Zo. .... Zn be martingale sequence of random variables such that Vida iZ, - Zi-1| & almost surely, then:
P(Zn - Zo
exp
i==
Corollary 1. Let Zo.... Zn be a martingale sequence of random variables such that V13c iZ, Zi-1| < G; almost surely, then with probability at least 8:
Zn - Zol S
2
log
8
1=1
Lemma 1. (Jin et al.
2018
Define V 11,=111 (1 Th) n/-
7i 1ل (1 -1))
The following properties hold for T'y:
AA 21
VN
VN
max;=l.... N n <
2H
N
Σ N
(T
)3 24
VN
21
EN t = =1 1 v
Lemma 2. Adapted slightly from (Jin el al.
2018)
Define (s) == min H, max Q (s, a' Vs E S.
For notational convenience, we also define P (s at) Ve+1($/41). where st was the state encountered at episode k at timestep L (similarly for )t). and [PV++1] a) := (.gr-P((().ssa.a=a)) [V++1 (s'))
For any (s, a) taken step of episodes k1, m., KN k. Then:
t) E S x A [L], episode k < K and N = N(s, a, t). Suppose (s, a) was previously
(Q (s) =1
H Σ l(V (5 (Pt (s.,)) (N + 1)ar
Proof. We have the following recursive formula for Q+ episode k and timestep t:
N
H
(s, = Σ nxlre(s, + ( (1 + +b, + (N + 1)M
We can produce similar formula for Q":
(s) (r. P
23

---

Published as a conference paper at ICLR 2020
From the Bellman Optimality Equation
(s, Σ ( + (s,))
Since Ex=1 n/y 1 and n/ = 0 for N 2 1 and Σ , 0 and n 1 for N =0
= -7 + Σ ( + (P:-
Pht. P2 + P (8,))
+P" (s, inside the summation.
= 2i + Σ
a) + (++(())))))
(8)
By definition of P
Subtracting equation] 7 from equation giives the required result.
Lemma 3. Adapted slightly from (Jin et al. 2018
Bounding Q* Q"
There exists an absolute constant > 0 such that, for any 8 E (0, 1), letting 6% 22 [S
have that 8h = 2 bi S 8y
H+loe(SAT/e) and, with probability at least - 6, the N
following holds simultaneously for all (s, t, ES x H [K]:
H
S (Qt - (8)( & Σ 1 ( ON
(N+ 1)M
1=1
where N = a) and ki,..., KN < K are the episodes where (s, a) was taken at step t.
Proof. For each fixed (s, a) E S x A [H) let Ko = 0 and
k; min(fk [K] > 1 (s): a.) = (s, a)) UK 1})
k; is then the episode at which (s, a) was taken at step for the ith time, or k; = + if it has been taken fewer than i times.
Then the random variable k; is a stopping time. Let Fi be the a-field generated by all the random variables until episode k; step
Let r E [K].
-P)V Then Z, = - X, is also martingale sequence with respect to the filtration (L[k; K] [PP P.) a)) Zu Z, Zo = Σ X;
Let X; == of 1k; S
and Z, Z = X,. We also have that [X| & H.
Then by Azuma's 's Inequality we have that with probability least 1 - 28/(SAHK)
SAT
Akk < [(P P))
(ni log
SAT
(m+)2) 22) log
24

---

Published as a conference paper at ICLR 2020
Then by Union bound over all 7 E [K], we have that with probability at least 1 - 28/(S
SAT
[ VT E
n [k4
- K] [(P P.)
S H.
2
(n+ (2) (++)))log
1=
H log SAT/8
S 2
7
Since From Lemma we have that Ei= (1x))² = 2H
Since inequality equation 9 holds for all fixed T E [K] uniformly, it also holds for a random variable T N = Nà (s, a, t) K. Also note that [[; S K] for all I N.
We can then additionally apply union bound over all E S, E A, [H] to give:
H H log SAT/8
Σ v (P
2
(10)
N
[ [K]. We then rescale d to which holds with probability 1 28 for all (s) E A 6/2.
By Lemma we have that by
(SAT/8))) S $2/2 Ean S
4v H log (SAT/8)/N 2bT-
From Lemma we have that:
(Q) (8)
(s)
H (N + 1)M
IVV - (1 + (Pt- (s.
(s, + Σ Mvl( - (++4)(
H
Ni [b7]] +
(N 1)M
1=1
1=1
rearranging terms
H (N + 1)M
Σ
(VV VED biy + /
From Eqn equation 10 defn on By and nen-negativity of Q'
H (N + 1)M
[VV VAD 3 +
Since b% /2/2
which gives the R.H.S.
Eqn equation 10 tells us that ΣN niI((P. P
Viti(ss)) 2 -b%, along with 6% < 82/2
IN b7 which then gives:
(Q, - (s, = - (s,
Σ VVV - (++1) (Pt P2 +77]
+ (N + 17ar
H (N 1)M
- A (s,, +
Σ 1V (4
25

---

Published as a conference paper at ICLR 2020
We then prove the L.H.S. by induction on H,.., 1. Fort H(Q Qi) 2 0. This is
because V HH+ V H+ 0, for N 0 (0+1) H QH+ and for N > 0 have that n/ 0.
we assume the statement true for t 1, consider
H (N 1)M
(Q * -
+
QT +
ry [min (H, max (5 max max Qi ((+1(5+t1)d)
a
H
(N + 1)
H
2 - Qi + (N 1)
If min (H, max t (st+1: a max. Q+ (f by our inductive assumption since
(Q44 (s+1)(8,00 a) 2 0 + max,' Q (s, a') 2 max." Qi+1 (i,1(",a")
If min max Q (0tt1; a')} H, we have that max," Qi+1 (0 S H.
This then proves the L.H.S.
Note on stochastic rewards: We have assumed so far that the reward function is deterministic for simpler presentation of the proof. If we allowed for a stochastic reward function, the previous lemmas can be easily adapted to allow for it.
Lemma would give us:
(Q,t* as) (s,a) Σ I' ((-aa()))))
H + (V - Viii) + (P. (P:- (s. (N 1)M
(rt -My-ER-R (. [r']) can then be bounded in the way in Lemma 3. Increasing the constants for by.,3 and rescaling of ê appropriately then completes the necessary changes.
We will now prove that our algorithm is provably efficient. We will do this by showing it has sub-linear regret, following closely the proof of Theorem 1 from (Jin et al. 2018)
Theorem 1. For any p E (0, 1): with probability at least p the total regret of Q+ is at most for M 2 and at most OHH++M AAT1-M HASAT Ar'SATlog(SAAe (Sg(SATT))
Olv logAA for
for < M 1.
Proof. Let
: V,TH = (V² (s,)
Lemma 3 tells us with probability at least å that Q k 2 Qi, which also implics that V 2 Vi* We then upperbound the regret follows:
K
K
Regret(() (K) Σ (VT -
VTT (+))
< Σ
(v}
VIT (5 = 8
k=1
We then aim to bound Σk 5% by the next timestep Σ 8h which will give us a recursive formula upperbound the regret. We will accomplish this by relating ΣK 8% to Σk ot.
26

---

Published as a conference paper at ICLR 2020
For any fixed (k,,), E [K] HI, let N₂ N(s al, t) where (st ab) was previously taken step
t of episodes Ai...., KN < k. We then have:
o = -V - 11 (s - (Qt (s ag)
(Qt Qi) ab) (Q; QF (+
No
$ N (Viit - Vi Vi+1)
H
+
(N₂ + 1)M + [Po(V
V (455)
By Lemma for the first term. Bounding (Qr ²,aa) is acheived through the Bellman Equation giving the final term.
M IN2 Sttt + +N, + (NA + 11M + +P(VV (
H
(V V4ti)((s,, at) (P -V7Ti
+[P/ V44 (s5t a
and subbing for ạ
N
H (Na + 1)at + +I( - P1) (2ti)(ot,0))
=
Σ
ni,
Ptt1 + PN. +
==1
+ (V
(1t1)(s
Since [PA (VA+
(57 at)
(Vi+1 Vith
N
H
NN
kr Ptti
+ NN. +
(Nx + 1)M + + + + 0/41
(11)
==1
Letting Et+ = [(Pr p (V + (VE (5(4)) =8f+1 -oi+1
We must now bound the summation Σx 8h, which we will do by considering each term of equation I1 separately.
Ek=1
K
(N +1
H
H
HK
H
(Nr + 1)M E @AHK!I-M
NN + 1)M
(K + 1)M
(K +
1JM
The first inequality follows since N < K. This shows that require M > 0 in order to guarantee sublinear regret K.
K 20
DO K
H
1(N = n] (n + 1)M
ΣV
1(N = n)
(N& = 1)M
(n 1)M
k=1
n=0 n=0k=
H
1 n2
< SA
SAH
(n 1)M
7=0
The first equality follows by rewriting -N E [[N2 n) . Only one of the indicator functions will be true for episode k. giving us the required value. The incquality is a crude upper bound that suffices for the proof. For given 1 ( n) can only be true for at most SA times across all of training. They will contribute (n+1) to the final sum.
H For M >> 1, the sum ΣK= ,r is bounded, which means that E (NE O(SAH)
27

---

Published as a conference paper at ICLR 2020
For M = 1, 1, n
log K +1
Ex=
(Notijar E OSSAH
H
For 0 M Ek=1 (N++1)M
H
O(SAHK! since Σ
1
KM-M
Goel and
not
1-M
Rodriguez 1987
Σk= i= Vv, 2+11
Nw S (1
li p++
1+1
P+1
i=Ng+1
The first inequality is achieved by rearranging how we take the sum.
Consider k' [K]. The term of will appear in the summation for k > k provided that (sf a²) = (s at ) e.g. we took the same state-action pair at episodes l and k'.
Nor On the first occasion, the associated learning rate will be + the second
NO N2
We can then consider all possible counts up oo achieve an inequality. By considering all k' [K] we will not miss any terms of the original summation.
The second inequality follows by application Lemma on the sum involving the learning rate.
Ekm AN_:
For all t E [H]. we have that:
[s(s..1)
H3 (og(SAT/8)
H3 (og(SAT/))
N
8
2
N
n
1=1
Nú (s.a.))
K
SA
H log SAT/8)
21
2 H3 log (AAT/8)
VTL
3.8
R=1
< 4SAV H log SAT/
SA
E O HASAK log (SAT/6))
O(v /H'SAAT log log(SAT/0))
We transform the sum over the episode's 's counts N into sum over all state-action pairs, summing over all of their respective counts.
The first inequality is due to N₂ = K/SA A maximising the quantity, this is since 1 V/v grows smaller increases. Thus, want to spread out the summation across the state-action space much as possible.
Then we use the result that D 1/Vi < 2/7, and that we are taking the sum over SA identical terms. We then
K/S S and thus taking the sum over N& a, identical terms.
ΣM MM DK shi
Following a similar argument as from Lemma 3 we can apply Azuma's 's inequality and a union bound
over all (s, a, f) E S A [M]. Let X; [(P (V V (s at)). Then Z; = - X; is martingale difference sequence, and have that IZ, Z, | < H. and Zo = 0. Then with probability at least 26 we have that:
H
K
K
Σ
st
<
c < H H222KHPlggSAAT/00 e O(H3/2 VTRV/TT /Tlog (
28

---

Published as a conference paper at ICLR 2020
Finally, utilise these intermediate results when bounding the regret via Equation equation I1
H
TN
Pit
(Nx + 1)
Eit1
0ot1
li+1
K
K
K
K
K (N + 1)
$
++
+
8/
+ Σ
(5t
cx+1)
ct
1=1
1=1
k=1
From our intermediate result on
K
K
H (Nr + 1)
< (1 + H
Σ
(0h + Eit1 +
1+
k=1
k=1
Since V* TT
01+1
oi+1
H Letting A, == Ek= ( + Ebt2 + (Nu+1)ar ), we have that Σ
=k=1 6 S AA since 8H 0. By
induction H, ..., then have that Σ of 11 (1 ) Ah
Ek
8
O H Ex= (3T Et (Ne+1)a))) since +1+ 1| Se
H
Using our intermediate results for the relevant quantities then gives us with probability at least 28:
K (Nx + 1)M
8t EOLW(HH5AAToo((AAT//) 3/12 TlloooSSA//OOO
1=1
H
= =O(/(USSAA/1g((AA7700)
(N + 1)
k=
We then consider the 3 cases of M: For M > 1 get (
(H* ( log SAT/8)) + H2SA).
For M we get (H A7 log( + H2 log()))
And for 0 < M < we have
+ H²+M HH+ SAT2-M).
T Z V HASAT log(S//8)) = HH Z H log( which means we
remove the H²SA (K) H2SA from the upperbound. If T S / /H'SAT AroSAAlog(SAA (og(SAT/O) then that is also a sufficient upper bound since the regret cannot be more than H K = =T.
This gives us the required result after rescaling d to 8/2.
29


Reviews:
[{"review_id": "rke3ol-ItS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "Optimistic Exploration even with a Pessimistic Initialisation\n================================================================\n\nThis paper presents an exploration algorithm based on \"optimism in the face of uncertainty\" via count-based bonus.\nThe authors observe that typical neural net initializations close to zero can be pessimistic, but show that augmenting a count-based bonus for acting and bootstrapping can overcome this.\nThe authors support their claim with an adaptation of a regret bound for the tabular case, and a series of didactic experiments with neural net models.\n\n\nThere are several things to like about this paper:\n- Exploration with generalization in Deep RL is a large outstanding problem, with few effective options and none really commonly used in the field beyond epsilon-greedy or Boltzmann.\n- This algorithm is reasonably well thought out, building on an established literature of exploration bonuses, but with a slightly different take on the structure of the bonus.\n- The paper is well structured, building from intuition to theory to toy examples in DQN setting.\n- Overall the algorithm appears to perform well against a wide variety of related variants (although that presentation is a little confusing / overwhelming).\n\n\nThere are several places the paper might be improved:\n- I don't think the authors make a clear enough case for why this method is *better* than the other optimistic bonus approaches listed... Yes there is a regret bound, but this is not as good as some other methods... Yes there are ablations... but they're not really clear about what the mechanism that makes this method better than others!\n- Although this algorithm is motivated by applications to *deep* RL, the key choice of the \"count\" (and thus the method for optimism bonus) is mostly sidestepped. It amounts to an essentially tabular bonus in the space of the hashing function... and it's not clear why this approach should work any better or worse than other similar approaches that the paper complains about. For example, if you used \"Randomized Prior Functions\" or \"Random Network Distillation\" with that same hashing functions you would likely end up with similar results?\n- The comparison to benchmark algorithms seems quite confusing and I'm not sure if it's really presented well. It might be good to focus on fewer comparisons at a time and push remaining less important ones to the appendix.\n- It would be great to get an evaluation of these algorithms on a standardized and open-source benchmark... and I think that bsuite could be a really good candidate for this paper https://github.com/deepmind/bsuite particularly the \"deep sea\" experiments.\n\n\nOverall I think this is a reasonable paper, and I expect it to improve during the review process.\nAt the moment I have to say that I don't think there is a clear enough case for why this method is preferable to other similar approaches, or enough insight into the pros and cons to accept.\n\n============\n\nUpdating to \"weak accept\" as part of rebuttal.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJeE7x9-5r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "#rebuttal responses\n I am pleased by the authors' responses. Thus I change the score to weak accept.\n\n#review\nThis paper presented OPIQ, a model-free algorithm that does not rely on an optimistic initialization\nto ensure efficient exploration. OPIQ augments the Q-values with a new count-based optimism bonus. \nOPIO is ensured with good sample efficiency in the tabular setting. Experimental results show that OPIQ drives\nbetter exploration than DQN variants that utilize a pseudo count-based intrinsic motivation in the randomized chain and the maze environment.\n\nThe new optimism bonus is interesting and convincing with a good theoretical guarantee. The paper would be more clear if the authors add a motivating example in a tabular environment. That is, why does this extra optimism bonus help to predict optimistic estimates for novel state and action pairs. \n\nI appreciate that the authors compare extensive DQN variants using count-based explorations. But the experimental results are somewhat weak, as there are no comparison results on hard Atari games, such as freeway and Montezuma's revenge.\n\nI am willing to improve the score if the authors show better motivation or results on Atari games.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgEwAgZ5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 method to optimistically initialize Q-values for unseen state actions for the case of Deep Q-Networks (DQNs) with high dimensional state representations, in order to step closer towards the optimistic initializations in the tabular Q-learning case which have proven guarantees of convergence. The paper shows that simple alternatives such as adding a bias to a DQN do not help as the generalization to novel states usually reduces the optimism of unvisited state-actions. Instead, a separate optimistic Q function is proposed that is an addition of two parts - a Deep Q-network which may be pessimistically initialized (in the worst case) and a term with pseudo-counts of state-actions that together form an optimistic estimate of novel state-actions. For the tabular case, the paper shows a convergence with guarantees similar to UCB-H (Jin et. al., 2018). This optimistic Q-function is used during action selection as well as bootstrapping in the n-step TD update.\n\nI vote for weak accept as this paper does a great job at demonstrating the motivation, simple examples and thorough comparisons for their proposed “OPIQ” model on simple environments such as the Randomized Chain (from Shyam et. al., 2019) and a 2D maze grid. While the experiments are in toy settings, the connection to UCB-H and the novel optimistic Q-function and it’s training formulation make the contributions of this paper significant.\n\nHowever, my confidence on this rating is low as I have not gone through the theorem in the appendix and I may be wrong in judging the amount of empirical evidence required for the approach.\n\nWhile the paper does cover a lot of ground with important details and clear motivation, a lot of the desired experiments have been left to future work as mentioned in the paper. This, in addition to the experiments on just toy settings, is not sufficient to conclude that this approach may be applicable to actually high dimensional state spaces where pseudo counts do not work well. Ultimately, the proposed approach relies strongly on good pseudo-count estimates in high dimensional state spaces, which is still an open problem.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper propose a scheme to enable optimistic initialization in the deep RL setting, and shows that it's helpful.

The reviewers agreed that the paper is well-motivated and executed, but had some minor reservations (e.g. about the proposal scaling in practice). In an example of a successful rebuttal two of the reviewers raised their scores after the authors clarified the paper and added an experiment on Montezuma's revenge.

The paper proposes a useful, simple and practical idea on the bridge between tabular and deep RL, and I gladly recommend acceptance.
Decision: Accept (Poster)