HyperDQN: A Randomized Exploration Method for Deep Reinforcement Learning
Authors: Ziniu Li
Yingru Li
Yushun Zhang
Tong Zhang
Zhi-Quan Luo
Venue: ICLR 2022 Poster (2022)
Keywords: exploration
reinforcement learning

Abstract: Randomized least-square value iteration (RLSVI) is a provably efficient exploration method. However, it is limited to the case where (1) a good feature is known in advance and (2) this feature is fixed during the training. If otherwise, RLSVI suffers an unbearable computational burden to obtain the posterior samples. In this work, we present a practical algorithm named HyperDQN to address the above issues under deep RL. In addition to a non-linear neural network (i.e., base model) that predicts Q-values, our method employs a probabilistic hypermodel (i.e., meta model), which outputs the parameter of the base model. When both models are jointly optimized under a specifically designed objective, three purposes can be achieved. First, the hypermodel can generate approximate posterior samples regarding the parameter of the Q-value function. As a result, diverse Q-value functions are sampled to select exploratory action sequences. This retains the punchline of RLSVI for efficient exploration. Second, a good feature is learned to approximate Q-value functions. This addresses limitation (1). Third, the posterior samples of the Q-value function can be obtained in a more efficient way than the existing methods, and the changing feature does not affect the efficiency. This deals with limitation (2). On the Atari suite, HyperDQN with 20M frames outperforms DQN with 200M frames in terms of the maximum human-normalized score. For SuperMarioBros, HyperDQN outperforms several exploration bonus and randomized exploration methods on 5 out of 9 games.

Published as a conference paper at ICLR 2022
HYPERDQN: A RANDOMIZED EXPLORATION METHOD FOR DEEP REINFORCEMENT LEARNING
Ziniu Li', Yingru Li Yushun Zhang', Tong Zhangat, and Zhi-Quan Luo
Shenzhen Research Institute of Big Data,
The Chinese University of Hong Kong, Shenzhen, China
Hong Kong University of Science and Technology
{ziniuli, yingruli, yushunzhang ) link. cuhk. edu. cn, tongzhang@ust. hk, luozq@cuhk.eduu
ABSTRACT
Randomized least-square value iteration (RLSVI) is provably efficient exploration method. However, it is limited to the case where (1) good feature is known in advance and (2) this feature is fixed during the training. If otherwise, RLSVI suffers an unbearable computational burden to obtain the posterior samples. In this work, we present a practical algorithm named HyperDQN address the above issues under deep RL. In addition to non-linear neural network (i.e., base model) that predicts Q-values, our method employs a probabilistic hypermodel (i.e., meta model), which outputs the parameter of the base model. When both models are jointly optimized under a specifically designed objective, three purposes can be achieved. First, the hypermodel can generate approximate posterior samples regarding the parameter of the Q-value function. As a result, diverse Q-value functions sampled to select exploratory action sequences. This retains the punchline of RLSVI for efficient exploration. Second, a good feature is learned to approximate Q-value functions. This addresses limitation (1). Third, the posterior samples of the Q-value function can be obtained in a more efficient way than the existing methods, and the changing feature does not affect the efficiency. This deals with limitation (2). On the Atari suite, HyperDQN with 20M frames outperforms DQN with 200M frames in terms of the maximum human- normalndr score. For SuperMarioBros, HyperDQN outperforms several exploration bonus and randomized exploration methods on out games.
INTRODUCTION
Reinforcement learning (RL) (Sutton & Barto, 2018) involves an agent that interacts with an unknown environment maximize cumulative reward. The trade-off between exploration and exploitation is fundamental problem in RL (Kakade, 2003). On the one hand, the agent needs to explore highly uncertain states and actions, which may sacrifice immediate reward. On the other hand, in the long term, the agent should take the best-known action; however, this action may be sub- sub-optimal due to partial information. To this end, sample-efficient RL agents should qualify the epistemic uncertainty (i.e., subjective uncertainty due to limited samples (Osband, 201 6a)) to address the trade-off.
Bayesian approaches like Thompson sampling (Russo et al., 2018) provide nice way of encoding the epistemic uncertainty by posterior distribution. For instance, randomized least-square value iteration (RLSVI)' (Osband et al., 2016b; 2019) is well-known Bayesian algorithm. Specifically, RLSVI takes three steps address the exploration and exploitation trade-off. First, conditioned observed data, RLSVI solves a Bayesian linear regression problem and updates the posterior distribution over (the parameter of) the optimal Q-value functions by the Bayes update rule. Second, RISVV samples specific Q-value function from the posterior distribution. Third, to collect more data, greedy actions are selected based on this Q-value function. In theory, the randomness in posterior sampling could yield positive bias, which boosts optimistic behaviors (Osband et al., 2019; Russo, 2019; Zanette al., 2020). However, RLSVI is restricted to the following case.
t: Corresponding authors.
For readers who familiar with RLSVI, please refer Appendix 1.1 for brief introduction.

---

Published as a conference paper at ICLR 2022
A good feature is known in advance. Over this feature, the Q-values can be approximated linear function.
This feature is fixed so that the posterior distribution is easy compute in incremental update way (see Remark 2 in Appendix A.I or (1.1) for an illustration).
Unfortunately, these two requirements do not hold in the deep RL scenario. The challenges of extending RLSVI to deep RL are listed below.
1) the provided feature is not good and fixed, RLSVI rarely competent. Under the deep RL setting, only raw feature outputted by randomly initialized neural network is available. Such an unpolished feature has limited representation power, so the Q-value function cannot be approximated accurately. Further, the mechanism of RLSVI only involves updating the model parameter, while the feature is left to be fixed (as a raw feature this setting). As a result, the empirical performance of RLSVI is often poor; see Appendix E.1 for the evidence.
2) When we update the feature over iterations in deep RL, the computational complexity of RLSVI becomes unhearable. As the data accumulates compute the feature covariance matrix to update the posterior distribution. With the fixed feature mapping, this process can be efficiently implemented an incremental way (see (1.1), where æk denotes the state-action pair (sx, (x) at iteration K and ó S x A - I is feature mapping.). However, when the feature mapping ΦK changing over iterations, we need to repeatedly calculate the matrix ox using all historical data as in (1.2) (e.g. in Atari, this calculation could involve more than IM samples with dimension 512), and this process results in a huge computation burden.
iterations, RI.SVI needs repeatedly
fixed Φ:
Ø = Ø + o(zx)
with Lo = 0,
(1.1)
K
K-1
changing ox: $ = Σ
Φx (x())))x(1=)) Px-1 Σ
Φx ( (
(1.2)
E=1
To address these two issues in deep RL, Bootstrapped DQN (BootDQN) (Osband et al., 2016a; 2018) takes a remarkable first step. To bypass the hurdle of issues 1 and 2, BootDQN simultaneously trains tens of ensembles (i.e., randomly initialized neural networks) and views them as approximate posterior samples of Q-value functions. However, with limited computation resources, BootDQN typically uses ensembles with a strictly limited number of elements. As such, the quality of the learned posterior distribution could be poor (Lu & Van Roy, 2017).
In this work, we present principled approach named HyperDQN that addresses the above issues under the context deep RL. Specifically, HyperDQN is built on two parametric models: in addition to non-linear neural network (i.c., base model) that predicts Q-values, it employs a hypermodel (Dwaracherla et al., 2020) (i.e., meta model). This hypermodel maps a vector & (from the Gaussian distribution) to parameter instance of the Q-value function. As shown in Figure 1, this hypermodel aims to serve as a proxy for generating the posterior samples of pprdiitt- To achieve this goal, both models are jointly optimized by a specially designed temporal difference (TD) objective (see (4.2)).
rundoa vector
2
Hypermodel
ppeddis == fo(e)
pl0 p(Opecties)
p(z)
Bose model
value function Qu(8,a) a)
S
Hidden Layers
Layer
prediies
Figure 1: IIlustration for HyperDQN.
After optimization, our approach has the following essential merits.
First, we prove that the optimized hypermodel can approximate the posterior distribution under the Bayesian linear regression case (see Theorem 1). Thus, diverse Q-value functions can be sampled to select exploratory action sequences. This retains the punchline of RLSVI for efficient exploration. We remark that this theoretical guarantee is missing in (Dwaracherla et al., 2020).
2

---

Published as a conference paper at ICLR 2022
Second, the feature mapping Penas (-) is updated in end-to-end way during the training. This deals with the feature learning problem of RLSVI (i.e., issue 1).
Third, the posterior samples of predict are obtained without involving (1.2). Specifically, the hypermodel could directly output an approximate posterior sample by taking a as its input. This addresses the computational problem of RLSVI when the feature is changing (i.e., issue 2).
Finally, compared with the finite ensembles in BootDQN, our approach learns the posterior distribution in a meta way and the hypermodel has certain generalization ability, Thus, our approach could have a better posterior approximation with the same computation resources. As such, our method is more computationally efficient to achieve a near-optimal performance.
To evaluate the efficiency of algorithms, we first consider the Atari suite (Bellemare et al., 2013) and assess the efficiency in terms of the suggests HyperDQN with 20M frames outperforms DQN (Mnih et al., 2015) with 200M frames in terms of the maximum nommannoormalized score. With the same training frames, HyperDQN also outperforms the exploration bonus methods OPIQ (Rashid et al., 2020) and OB2I (Bai et al., 2021), and randomized exploration methods BootDQN (Osband et al., 2018) and NoisyNet (Fortunato et al., 2018). For another challenging benchmark SuperMarioBros (Kauten, 2018), HyperDQN beats these baselines on 5 out of 9 games in terms of the raw scores.
score over 49 tasks. The empirical result
BACKGROUND
Markov Decision Process. In the standard reinforcement learning (RL.) framework (Sutton & Barto, 2018), a learning agent interacts with an Markov Decision Process (MDP) to improve its performance via maximizing cumulative reward. The sequential decision process is characterized as follows: at each timestep f, the agent receives state from the environment and selects an action a from its policy π [a]ss) ss) = fr = ag|s St }: this decision is sent back to the environment, and the environment gives reward signal r(s,, a2) and transits to the next state $t+1 based on the state transition probability ," = Pr(s' = 81+1 = 8t, a = ax)- The main target of RL is to maximize the (expected) discounted return E Ei= 7rr(s, (0 p(-), where p(-) is initial state distribution and E (0, 1) is discount factor.
Deep Q-Networks (DQN). Deep Q-Networks (DQN) (Mnih et al., 2015), it employs a neural net- work to approximate the Q-value function, which is defined as Q" (s. a) = EI (fr(,, (80
8, ag = a]. In particular, a temporal difference (TD) based objective applied:
min
Σ (r(s,a) + m Q, a') Qo(s.a)) (...,T,9')D
(2.1)
where the experience replay buffer. Qo a prediction network parameterized by 6, and Q7 is the so-called target network, which is a delayed copy of Qa for stable training.
RELATED WORK
Epistemic uncertainty qualification. is justified that dithering strategies like e-greedy (Mnih al., 2015) are inefficient (Oshand et al., 2019). This is intuitive since they do not have any epistemic uncertainty measure and hence cannot "write-off" sub-optimal actions after experimentation. Importantly, epistemic uncertainty reflects the confidence about the unknown environment in online decision-making (Osband, 2016a). For tabular MDPs with the one-hot feature, "count" provides an epistemic uncertainty measure (Brafman & Tennenholtz, 2002; Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018) and "covariance" serves as the counterpart for linear MDPs (Jin et al., 2020; Cai et al., 2020). Currently, we do not have perfect epistemic uncertainty qualification tool for deep RL, where a good feature is unknown in advance. As argued in (Osband et al., 201 8), approaches like dropout (Srivastava al., 2014) and distributional operator (Bellemare et al., 2017) are not suitable since they are designed for risk estimation. In this paper, focus on the extension of hypermodel (Dwaracherla et al., 2020), which could capture the epistemic uncertainty for bandit tasks.
OFU-based exploration. Based on the mentioned uncertainty qualification, optimism in the face of uncertainty (OFU) based methods (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018) construct upper confidence bound (UCB) to direct exploration. These theoretical works have inspired many empirical studies that encourage exploration by adding "reward/exploration bonus" to mimic UCB (Stadie et al., 2015; Pathak et al., 2017; Tang et al., 2017; Burda et al., 2019a;b), The challenges in this
3

---

Published as a conference paper at ICLR 2022
direction include: how to obtain task-relevant reward bonus (0 (O'Donoghue et al., 2018)? how to get an optimistic initialization with neural network (Rashid et al., 2020)? how to properly back-pre propagaee the uncertainty over periods to induce temporally extended behaviors (Bai et al., 2021)? Though some of SOTA exploration bonus methods have achieved superior performance on some hard exploration tasks, (Taīga al., 2020) report that these algorithms do not provide meaningful gains over the e-greedy scheme on the whole Atari suite.
TS-based exploration. On the other hand, Thompson sampling (TS) based methods design the exploration strategy in a Bayesian way (Osband et al., 2013; Osband & Van Roy, 2017). Randomized least-square value iteration (RLSVI) provides a promising direction (Osband al., 2016b; 2019). As we have mentioned in Section 1, this method, however, can only be applied when good feature is known and fixed during the training. Following RLSVI, Osband et al. (201 6a) develop a practical algorithm called Bootstrapped DQN, which uses finite ensembles to generate the randomized value functions. As discussed earlier, the main bottleneck of Bootstrapped DQN is its computation complexity: it requires lots of ensembles to obtain accurate approximation of the posterior samples (Lu & Van Roy, 2017). Our method closely related to NoisyNet (Fortunato et al., 2018) as both methods inject noise to the parameter. However, we cannot view NoisyNet as extension of RLSVI. The main reason is that NoisyNet is not ensured to approximate the posterior distribution as stated in (Fortunato al., 2018). Besides, Ishfaq al. (2021) attempt to extend the idea of RLSVI the general case. In particular, their algorithm solves M randomized least-square problems and chooses the most optimistic value function in each iteration. Since M is selected to be proportional to the inherent dimension in theory, their algorithm is also not computationally efficient.
METHODOLOGY
4.1 ARCHITECTURE DESIGN
In this part, we explain the architecture design of HyperDQN shown in Figure 1. First, the hypermodel fu(-) maps N Na-dimension random vector p(z) (e.g., Gaussian distribution) d-dimension parameter 0 := =2). For example, if 2 follows an isotropic Gaussian distribution 40, and the hypermodel (z) V 1/ is linear model, then 0 == fz(2) ~ N(v,, (, vw). where V/ E R.N.x xd and v, E Rd are the weight and bias of the linear hypermodel with v (Mur, ub). In general, the hypermodel could be a non-linear mapping so that (=(=) could follow an arbitrary distribution. Unless stated otherwise, we only consider the linear hypermodel rather than non-linear ones. This is because linear hypermodel has sufficient representation power to approximate the posterior distribution (like RLSVI does) (Dwaracherla et al. (2020)).
specific
Now, we explain the basemodel in Figure 1. standard way: it takes state its input and outputs Qs a) RR for some action a. Concretely,
The base model (i.e., a deep neural network) operates in
the base model employs a feature extractor de : S + R (i.c., the hidden layers in Figure 1) to learn a good representation. Then, the base model outputs Q(s, a) by Q(s, :) = 0 prediica (s). where 0 Opredict E Rd is the parameter of the prediction layer (i.e., the last layer of the base model in Figure 1). By our formulation, Opeddict is also the output of the hypermodel. That is, Oprodiet- = fz(2)= + feyar (z), where fuy. (z) is fixed prior hypermodel; see the discussion below. Numerically, we fix Uprior = Vo. where vo is a random initialization. In the sequel, we will introduce the difference between the hypermodel in Figure I and that in Dwaracherla et al. (2020).
4.2 DIFFERENCES WITH DWARACHERLA ET AL. (2020): HOW THE DIRECT EXTENSION FAILS
Readers may notice that our architecture design is different from the original one in (Dwaracherla et al., 2020). Concretely, we apply the hypermodel for the last layer of the base model, but in (Dwaracherla et al., 2020) the hypermodel is applied for all layers of the base model. This modification aimed to overcome the training difficulty: the training will fail if otherwise (see Appendix F.2 for the numerical evidence). Why does the training fail under the original design? We find out it is due to the severe gradient explosion at the initialization, which does not happen if no hypermodel is attached. For standard deep neural network models, such gradient explosion is mainly avoided by carefully designed initialization strategies (Sun, 2019). For instance, the famous LeCun initialization rule (LeCun et al., 1998) suggests that we should initialize the parameter of i-th layer by sampling from the Gaussian distribution (/ o2) with o = 1/ /d,-1. where di-1 is the width of (i - 1) layer. As result, the input signal and the output signal have the same order fg form after processing.
4

---

Published as a conference paper at ICLR 2022
However, things have changed if we directly use the architecture in (Dwaracherla et al., 2020) with this initialization technique: the output of the hypermodel is expected to lie between -1 and (up to constants); this further implies that the parameter is in [-1, 1] for each layer of the base model, which disobeys the principle 1/ 1/v vd.1j Consequently, the input signal amplifies over layers and the gradient explodes. To bypass the training issue, Dwaracherla et al. (2020) use a shadow base model (e.g., 2 layers with the width of 10) and further implement the blocked hypermodel; see (Dwaracherla et al., 2020, Section 4) for details. But for deep RL, this training issue is severe and we overcome this challenge by the proposed architecture shown in Figure I, in which the hidden layers of the base model are initialized with common techniques and the last layer could be properly initialized by normalizing the output of the hypermodel. This deals with the mentioned parameter initialization issue. Fortunately, this simple architecture still retains the main ingredient of RLSVI (i.e., capturing the posterior distribution over a linear prediction function).
4.3 TRAINING OBJECTIVE
In this part, we introduce the objective function. For the sake of better presentation, let us first consider a regression task. Let Rd be the feature and y R be the label, the objective function developed in (Dwaracherla et al., 2020) for training the hypermodel is
L(v; p(z)
Σ
(u (u+owi 0+ 175-5190 (05 (z) + (z)))
(2)(
(dz),
(..D.)))
(a)
(b)
(4.1)
where & is a random vector independently sampled from the unit hypersphere, paired with each (3r, y) in the dataset DD = {<r: Vi, (,) ===1,, -,..., (DI): ow > is the noise scale and a, >> is the regularization scale. Next, we briefly explain three key parts in (4. First, (a) is an artificial noise term exerted on the label y. which is introduced for pure technical purpose. We defer more discussion of (a) to Remark 1. Second, (b) contains two base models denoted by g. Concretely, Fy (-) is prior model parameterized by the output of a fixed hypermodel Suyan. This term stores the prior information. At the same time, (-) is a differential model linked by the output of a trainable hypermodel fu. We remark that term (b) is called "additive prior models" in (Osband et al., 2018; Dwaracherla et al., 2020); see (Dwaracherla et al., 2020, Section 2.5) for detailed discussion. Finally, (c) is regularization term, which is an essential design in Bayesian learning.
To address the limitations of RLSVI for deep RL tasks, we first employ a feature mapping (param- eterized by Ohiddon) and approximate the Q-value function by linear function (parameterized by pprestict) over the learned feature. Furthermore, the parameter of this linear function is modeled by the hypermodel (i.e., fpredica = Euma (z) + f2)) as discussed in Section 4.1. To this end, we extend (4.1) and implement the following optimization problem:
min / p(=)
Σ
(Qrarper (5', 2) ow= Qprediction (s,iionnn,,,,,,, a, =))²
[[,(()) (dz),
(4.2)
where
Q preetiction ( (8, a, 2) = Ppieer Soneer (8, (1) + Quaster (e)
(4.3)
Qurree (8', (8,2) =r max Qpeert (2) ()')) a²) + Q Prater (8', a²)
Similar to the formulation in the regression problem, the value function is the sum of the prior Oy (=) and the differential Qu Following the target network in DQN, (Ohidden; 7) is the delayed copy of (Onideen v). Compared with the TD loss in (2.1), there is an additional noise term ow for Bayesian learning and the prediction layer of the Q-value function is modeled as probabilistic layer by the hypermodel. In experiments, we use the average of finite samples of a to approximate (4.2); see the empirical loss function in (A.6) in Appendix. We choose Adam (Kingma & Ba, 2015) to optimize the empirical loss function.
4.4 THEORETICAL GUARANTEE
To understand our method, we explain why (4.1) is good objective to generate approximate posterior samples. We provide the analysis under the linear case.
5

---

Published as a conference paper at ICLR 2022
Assumption 1. Suppose the data generation follows y = w², w ~ ~N(0, and the prior distribution over 0 is (0 o.f). Furthermore, assume the base model is linear, i.e, (fv(=)(z) x fz) and I (=) x x Sugaa(2). Moreover, assume the hypermodel is also linear, i.e.
[=(=) = V/ 2 + Vb and Jupine (z) veriorT T prior. ( Vb) and Uprior = =verror , prrio)
Based Assumption 1, the posterior distribution over 0 is N (E
[D], Covl0" D)) with
Ele*
D] =
X
X
+ o7
8p)
p
0
Covi0* [D =
x
o
where X E R and Y IR PI concatenation of x; and yı, respectively. Also, we have that fo (z) (z) = 91 Iy (=)+ = go go(z) = x 0, where 0 := Sunac (2) + fu(z).
Theorem 1 (Informal). Under Assumption I, set yorior = p and v/g Bp. Let = (V 2/, be
the optimal solution of (4.1) conditioned on specific realizations of then 1 Sumar (2) Sv (2)
Nu +V6 (vetior + vio) (verior + +V²i)) satisfies
Aprior + Vi B[O* [D], (verior v()) (verior vw)) Cov(0* D err(f).
Furthermore, the error term satisfies [glerr(E)] =
Theorem 1 states that the optimized hypermodel approx- imate the true posterior distribution. The formal statement and proof are given in Appendix B.3. We emphasize that the message in Theorem is not discussed in (Dwaracherla et al., 2020, Theorem 1). Dwaracherla et al. (2020) prove that linear hypermodel has sufficient representation power to approximate any distribution (over functions) so is unnecessary non-linear one. However, this guarantee is unrelated to the ob- jective 1): Dwaracherla et al. (2020) only show there exists linear hypermodel can approximate the posterior distribution but Dwaracherla et al. (2020) do not tell us whether (4.1) can lead to such hypermodel. Instead, this question is affirma- tively answered by Theorem 1. In addition, Theorem also conveys an important message about the noise used in (4.1), which we explain in Remark 1.
use
0%
Figure 2: Visualization of true pos- terior samples and learned posterior samples.
Remark Readers may ask whether an independent Gaussian noise w (rather than the z-dependent noise 2 [) =TE is applicable in (4.1). Intuitively, w also form randomized-lest least square problem to optimize the hypermodel. However, by inspecting the proof of Theorem 1, we claim that this scheme does not work. Technically speaking, w will introduce exogenous random sources into the objective function, which jeopardizes the learning goal of mapping an index 2 to a posterior sample 0; see Appendix B.4 for a formal argument.
To better understand the fundamental issue involved here, we run simulation on a toy 2-dimensional Bayesian linear regression problem (Assumption with 0" (0t, 0ī); see Appendix C.3 for experiment details. After optimizing (4.1), we visualize the posterior samples generated by the linear hypermodel in Figure 2. In particular, hypermodel (z (zTE) (in green) and hypermo rmodel (w) (in red) correspond to learned samples via solving (4.1) with a z-dependent noise z [and an independent Gaussian noise w, respectively. The variant posteria
sample e (in purple) is obtain by the true posterior distribution (EE D), Cov(g" D)). We observe that the z-dependent noise is indispensable for the hypermodel to approximate the posterior distribution.
4.5
THE ALGORITHM
We outline the proposed method in Algorithm 2 in Appendix. At the beginning of each episode, a random vector is sampled to obtain the Q-value function, which is further used for interactions with environments. Subsequently, the randomized temporal difference objective in (4.2) is optimized to train the hypermodel and the hidden layers based on the collected data.

---

Published as a conference paper at ICLR 2022
Next, interpret HyperDQN from algorithmic level introduced in (Osband al., 2018). In particular, HyperDQN achieves the desiderata:
Task-relevant feature. A task-specific feature can be obtained by the end-to-end training in (4.2). Such feature is good in the sense that it is optimized approximate multiple value functions as different invocations of yield several individual TD loss functions. As discussed previously, this feature learning procedure is beyond the scope of RLSVI.
Commitment." 2 The agent executes action sequences that span multiple periods by obeying its intent. In each episode, HyperDQN samples specific value function and takes greedy actions according this value function until the episode terminates. Unlike BootDQN (Osband al., 201 3 and OFU-based algorithms (Taiga et al., 2020; Rashid et al., 2020; Bai et al., 2021). HyperDQN does not combine c-greedy as the perturbation c-greedy ruins "far-sighted" behaviors generated by the original algorithm.
Cheap computation. As discussed earlier, RLSVI needs to re-compute the feature covariance matrix when the feature mapping changes, which results a huge computation burden. address this issue, BootDQN simultaneously trains tens of ensembles. When the computation resources are limited, the quality of generated posterior samples by BootDQN is poor (Lu & Van Roy, 2017). However, our approach learns the approximate posterior samples in meta way and the hypermodel has certain generalization ability. As such, and our method tends to be more computation efficient.
As a side note, if the random index 2 is repeatedly sampled from a finite set, the hypermodel degenerates to finite ensembles. As such, BootDQN can be viewed as a special case of HyperDQN. Following (Osband et al., 2018), we summarize BootDQN and HyperDQN in Table 1.
Table 1: Important issues in posterior approximations for deep RL. A green tick indicates satisfying result, a red cross implies an undesirable result and a yellow circle means something in between.
Task-relevant feature
Commitment
Cheap computation
BootDQN (Osband et al., 2018)
HyperDQN
RLSVI (Osband et al., 2016b)
XX
EXPERIMENTS
In this section, we present numerical experiments to validate the efficiency of the proposed method. Experiment details can be found in Appendix C.
5.1 ATARI
Our first experiment is on the Arcade Learning Environment (Bellemare al., 2013), which provides platform to assess the general competence. The training and evaluation procedures (e.g., observation preprocessing and reward clipping) follows (Mnih et al., 2015) and (van Hasselt et al., 2016). We measure the sample efficiency in terms of the human- comman-normalized score during the interaction. In particular, the raw score of each game normalized so that 0% corresponds to a random agent and 100% to human expert.
We consider five baselines: DQN (Mnih et al., 2015), OPIQ* (Rashid et al., 2020), OB2I (Bai et al., 2021) I), BootDQN (Osband et al., 2018) and NoisyNet (Fortunato et al., 2018). 8). In particular, OPIQ and OB21 are two advanced OFU (i.e, exploration bonus based) methods while BootDQN and NoisyNet randomized exploration methods.
The learning curve over 49 games (by median) with the 20M frames training budget is displayed in Figure 3. We see that HyperDQN quickly explores and achieves the best performance among baselines. The performance of OFU-based methods is bad: OPIQ cannot achieve a satisfying
"This concept is originally defined in the context concurrent RL (Dimakopoulou & Roy, 2018). We borrow this concept to help discuss combination with e-greedy under the standard RL framework.
BBotDDQ uses e-greedy for complicated tasks like Atari; see (Osband et al., 2016a, 6a1,,, Appendix D.I), hhtpps: : /i thub,
'ttpps: / / thub. ctm wwt.//aicceennn//////aaaoa
6 'Modified from https://githhb. http:hhhhw.ooooooooooaoooooooo rappssttttaaatttttaaaraaapp for a fair comparison.
"Modified from https://giiiie thwbb www.k//mm/e///eeee /ttp///fffffi/ff//// pytprch/bbbboo ob/ master/
fqf_igg www.l/grrgnn/nenneeeeeeeee py for fair comparison.
7

---

Published as a conference paper at ICLR 2022
Table 2:
Comparison of algorithms on Atari in terms of the median over 49 games' maximum scores. Note that the performance of DQN is based on 200M training frames while other methods are based on 20M training frames.
DQN (200M) 93%
OPIQ
OB2I
BootDQN
NoisyNet
HyperDQN
37%
50%
82%
91%
110%
performance over all games and OB2I degenerates after 10M frames. This partially because the exploration bonus may guide direction that is unrelated the environment reward. However, randomized exploration methods do not have such an issue. Our experiment results regarding OFU- based methods consistent with (Taaga et al., 2020): though they may perform well some hard exploration tasks, current OFU-based methods cannot provide meaningful gains over the vanilla DQN method on the whole Atari suite.
We notice that researchers also consider the metric of the maximum human-normalized score, which measures the performance of the best policy during training; refer to (Mnih et al., 2015; van Hasselt et al., 2016; Hessel et al., 2018; Fortunato et al., 2018). Specifically, we compute the maximum evaluation scores after training for each game and average them by the median. We report such results in Table 2. In particular, we see that HyperDQQ outperforms the performance obtained by DQN with 200 training frames. We do not consider the statistics of mean because it significantly affected by some special games (e.g., Atlantis); see Table 5 in Appendix.
We note that the 20M frames training budget (rather than 200M frames) is commonly used in (Lee al., 2019; Bai et al., 2021). The main reason is that algorithms can achieve satisfactory performance on many tasks with 20M frames while the 200M frames training budget requires about 30/10 days with CPU/GPU machine for game, which is expansive in time and money.
HytwDON
Q'ter
NoteyMill
Hype
40%
0621
BooDDN
DP13
0521 80%
horeyles sylet
HlywOON/ww spalor-gneddy
BoolDoN
DQN
0/10
froms
DON
20%
45%
Median
Frame (milllons)
Frame (millonn))
Figure 3: Comparison of algorithms in terms of the human-normalized score over 49 games in Atari.
Figure 4: Comparison of algorithms Q c-greedy makes HyperDQN worse.
To better understand the performance of HyperDQN, visualize the relative improvements baselines on "easy exploration" and "hard exploration" environments in Figure 12, 13, 14, and 15 in Appendix D. We see that HyperDQN could perform well on many easy and hard exploration tasks. However, HyperDQN does not work for Montezuma's 's Revenge. in which the reward is very sparse so there limited feedback for feature selection. For the same reason, randomized exploration methods in (Osband et al., 2018; Fortunato et al., 201 8) do not perform well on this task.
Finally, we provide evidence that commitment is crucial for our method. Specifically, c-greedy would lead to worse performance for HyperDQN; see the empirical result on the game Q*bert in Figure 4. The same observation holds for other environments (refer Appendix D).
5.2 SUPERMARIOBROS
In this part, we evaluate algorithms the SuperMarioBros suite (Kauten, 2018). Environment preprocessing and algorithm parameters basically follow the one used in Atari and we do not tune parameters for any algorithm.
We note that SuperMarioBros-11 1-3 and SuperMarioBros-244 are two hard exploration tasks due to the long planning horizon and sparse reward. Experiments are run with 3 random seeds. Similar to Table 5, we report the maximum scores in the following Table 3; see Figure 17 in Appendix for the learning curves on each game. We see that HyperDQN beats baselines
of games.
8

---

Published as a conference paper at ICLR 2022
Table 3: Comparison of algorithms on SuperMarioBros in terms of the raw scores by the best policies
with 20M training frames.
DQN
OPIQ
OB2I
BootDQN
NoisyNet
HyperDQN
BrperMarioBros-I 1-1
1,070
7,650
4, 457
7.009
12, 439
7.924
SuperMarioBros---2
883
5,515
4, 695
5, 665
6,34
8, 267
SuperMarioBros-1-3
667
2, 2,053
1, 583
1, 609
587
047
BuposMarioBros-211
10, 800
21, 654
14, 226
26, 415
14, 017
23, 047
SuperMarioBros-2222
813
1, 630
I, 1888
1, 092
1, 808
1, 1,984
Super
3, 373
718
4, 402
5, 108
490
5, 980
BupesMarioBros-3-11
2, 560
700
3, 251
8,2
11,310
48, 385
SuperMarioBros-322
11, 633
20, 872
26, 508
20, 955
33, 489
41,
Bupor-arioBros-333
1,007
2, 4,440
3, 009
2,650
886
5,568
5.3 DEEP SEA
In this part, we consider the standard testbed for hard exploration: deep sea (Osband et al., 2018; 2020). In particular, there are two actions this environment: move left and move right; see Figure The reward is sparse and is only released when the agent always takes the "right" action to obtain the treasure the corner. The maximum episode return is 0.99.
Following (Dwaracherla et al., 2020), we measure the computation complexity by
computation complexity = Nlgdd Tiz x K
(5.1)
where Aagd is the number of SGD steps per iteration, n. is the number of ensemble (index) samples, and K the minimum number of episode with return 0.99. This criterion reasonable since without the restriction of the computation complexity, methods may perfectly approximate RLSVI and enjoy the same sample complexity.
The averaged empirical result with 10 random seeds is shown in Figure 6. In particular, the z-axis corresponds to the size of the deep sea, i.c., the number of rows in Figure 5, and the y-axis corresponds to the computation complexity in (5.1). We see that HyperDQN is more computationally efficient than BootDQN. Other methods fail to solve the deep sea when the size larger than 20, which is also observed in (Osband et al., 2018).
1000
Algorthm
HypurDON
Computitoon Compaury
12:00
1000
800
600
200
25
Deep San
Figure Illustration for deep sea.
Figure Comparison HyperDQN and BootDQN in terms of computation complexity on the deep sea.
6 CONCLUSION AND FUTURE WORK
In this work, present practical exploration method to address the limitations of RLSVI and BootDQN. To reinforce the central idea, we leverage the hypermodel (Dwaracherla et al., 2020) and extend it from the bandit tasks to RL problems. Several algorithmic designs developed release the power of randomized exploration.
Future directions include extending the idea for continuous control (Lillicrap et al., 2016; Haarnoja et al., 2018) (i.e., building a randomized actor-critic with a similar architecture with HyperDQN; see Appendix E.5), utilizing the developed epistemic uncertainty qualification tool for offline RL (Fuji- moto et al., 2019; Levine et al., 2020), and acquiring an informative prior from human demonstrations accelerate exploration (Hester al., 2018 8: Sun et al., 2018) (see Appendix E.6).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
We thank Chenjia Bai for sharing some training results of OB2I, Hao Liang for the insightful discussion, and Tian Xu for reading the manuscript and providing valuable comments. The work of Z.-Q. Luo is supported by the National Natural Science Foundation of China (No. 61731018) and the Guangdong Provincial Key Laboratory of Big Data Computation Theories and Methods.
ETHICS STATEMENT
This work focuses on designing efficient exploration method improve the sample efficiency of reinforcement learning. This work may help reinforcement learning to be better used in the real world. There could be some unexpected consequences if the reinforcement learning is abused. For example, robot is trained maliciously to hurt people.
REPRODUCIBILITY STATEMENT
First, a formal statement and proof of Theorem are given in Appendix B.3. Second, the imple- mentation details of the proposed algorithm HyperDQN be found in Appendix A.2. Third, the experiment details of numerical results in Section 5 are provided in Appendix C.
REFERENCES
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning, pp. 263-272, 2017.
Chenjia Bai, Lingxiao Wang, Lei Han, Jianye Hao, Animesh Garg, Peng Liu, and Zhaoran Wang. Principled exploration via optimistic bootstrapping and backward induction. Proceedings of the 38th International Conference on Machine Learning, pp. 577-587, 2021.
Mare 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.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems 29, pp. 1471-1479, 2016.
Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pp. 449-458, 2017.
Ronen I. Brafman and Moshe Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. Journal of Maching Learning Research, 3:213-231, 2002.
Yuri Burda, Harrison Edwards, Deepak Pathak, Amos J. Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of -uriosity-driven learning. In Proceedings of the 7th International Conference on Learning Representations, 2019a.
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by random network distillation. In Proceedings of the 7th International Conference on Learning Representations, 2019b.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In Proceedings of the 37th International Conference on Machine Learning, pp. 1283-1294, 2020.
Maria Dimakopoulou and Benjamin Van Roy. Coordinated exploration in concurrent reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, pp. 1270- 1278, 2018.
10

---

Published as a conference paper at ICLR 2022
Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, lan Osband, Zheng Wen, and Benjamin Van Roy. Hypermodels for exploration. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Meire Fortumato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Rémi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In Proceedings of the 6th International Conference on Learning Representations, 2018.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In Proceedings of the 36th International Conference on Machine Learning, pp- 2052-2062, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference Machine Learning, pp. 1856-1865, 2018.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the 32nd AAAI Conference Artificial Intelligence, pp. 3215-3222, 2018.
Todd Hester, Matej Vecerík, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, Gabriel Dulac-Amold, John P. Agapiou, Joel Z. Leibo, and Audrunas Gruslys. Deep q-learning from demonstrations, In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 3223-3230, 2018.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang. Zhaoran Wang, Doina Precup. and Lin F. Yang. Randomized exploration in reinforcement learning with general value function approximation. In Proceedings of the 38th International Conference on Machine Learning, pp. 4607-4616, 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Maching Learning Research, 11:1563-1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael Jordan. q-lernning provably efficient? In Advances in Neural Information Processing Systems 30, pp. 4868-4877 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Annual Conference on Learning Theory, pp. 2137-2143, 2020.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Christian Kauten. Super Mario Bros for OpenAl Gym. GitHub, 2018. Utt.ttts::// thub. com/ Kautenjaaaaa gym- s super-ueaeee mario bros.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proceedings of the 3rd international Conference on Learning Representations, 2015.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robar Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 48. Springer, 1998.
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 32, pp. 2110-2119, 2019.
2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement Icarning: Tutorial, review, and perspectives open problems. arXiv, 2005.01643, 2020.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proceedings of the 4th International Conference Learning Representations, 2016.
11

---

Published as a conference paper at ICLR 2022
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In Advances in Neural Information Processing Systems 30, pp. 2260-3268, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning, Nature, 51 518(7540):529-535 2015.
Brendan O' D'Donoghue, Ian Osband, Rémi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In Proceedings of the 35th International Conference on Machine Learning, pp.
2018.
Ian Osband. Risk versus uncertainty in deep learning: Bayes, bootstrap and the dangers of dropout. In NIPS workshop on bayesian deep learning, 2016a.
Ian Osband. Deep Exploration via Randomized Value Functions. Phl) thesis, Stanford University, USA, 2016b.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Proceedings of the 34th International Conference on Machine Learning, pp. 2701- 2710, 2017.
lan Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems 26, pp. 3003-3011, 2013.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems 29, pp. 4026-4034, 2016a.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value funetions. In Proceedings of the 33rd International Conference on Machine Learning, pp.
2376-2386, 2016b.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems 31, pp. 8626-8638, 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.
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard S. Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity- exploration by self-supervised prediction. In Proceedings of the 34th International Conference on Machine Learning, pp. 2778-2788 2017.
John Quan and Georg Ostrovski. DQN Zoo: Reference implementations of DQN-based agents. GitHub, 2020. URL http: /ttt:://ithhb.b. com/ aed dqn__oo.
Tabish Rashid, Bei Peng, Wendelin Boehmer, and Shimon Whiteson. Optimistic exploration even with a pessimistic initialisation. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Advances in Neural Information Processing Systems 32, pp. 14410-14420, 2019.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-11) 1958, 2014.
12

---

Published as a conference paper at ICLR 2022
Bradly C. Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv, 1507.008144 2015.
Ruoyu Sun. Optimization for deep learning: theory and algorithms, arXiv, 1912.08957, 2019.
Wen Sun, J. Andrew Bagnell, and Byron Boots. Truncated horizon policy search: Combining reinforcement learning & imitation learning. In Proceedings of the 6th International Conference on Learning Representations, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
Adrien Ali Taiga, William Fedus, Marlos C. Machado, Aaron C. Courville, and Mare G. Bellemare. On bonus based exploration methods in the arcade learning environment. In Proceedings of the 8th International Conference Learning Representations, 2020.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. #exploration: A study of count-based exploration for deep reinforcement learning. Advances in Neural Information Processing Systems 30, pp. 2753-2762, 2017.
Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap. Nicolas Heess, and Yuval Tassa. dm_control: Software and tasks for continuous control. Software Impacts, 6:100022, 2020.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 2094-2100, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanctot, and Nando de Freitas. Dueling network architectures for deep reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, pp. 1995-2003, 2016.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 1954-1964, 2020.
13

---

Published as a conference paper at ICLR 2022
APPENDIX: HYPERDQN: A RANDOMIZED EXPLORATION METHOD FOR DEEP REINFORCEMENT LEARNING
CONTENTS
Introduction
2 Background
3 Related Work
Methodology
4.1 Architecture Design
4.2 Differences with Dwaracherla et al. (2020): How the Direct Extension Fails
4.3
Training Objective
5
4.4 Theoretical Guarantee
4.5 The Algorithm
5
Experiments
5.1
Atari
7
5.2 SuperMarioBros
8
5.3 Deep Sea
Conclusion and Future Work
A Algorithm Details
16
A.1 Randomized Least-square Value Iteration (RLSVI)
16
A.2 Implementation of HyperDQN
17
A.3 Sampling From Unit Hypersphere
18
Connection Between Bayesian Linear Regression and Hypermodel
19
B.1 Bayesian Linear Regression
19
B.2 Hypermodel
20
B.3 Proof of Theorem
20
B.4 Why Independent Gaussian Noise Cannot Work For Hypermodel?
................................
22
Experiment Details
23
C.I Algorithm Implementation And Parameters
23
C.2 Environment Preprocessing
24
C33 Bayesian Linear Regression
25
C.4 Parameter Choice
25
D Additional Results
26
D.1 Atari
26
D.2 SuperMarioBros
27
14

---

Published as a conference paper at ICLR 2022
E Discussion
32
E.1 Direct Extension of RLSVI Could Fail
32
E.2 Trainability Issues of HyperDQN
32
E.3 e-greedy Many Efficient Algorithms
32
E,4 Discussion of NoisyNet
34
E.5 Extension to Continuous Control
34
E.6 When Informative Prior is Available
35
15

---

Published as a conference paper at ICLR 2022
A ALGORITHM DETAILS
A.1 RANDOMIZED LEAST-SQUARE VALUE ITERATION (RLSVI)
In this part, offer brief introduction randomized least-square value iteration (RLSVI) (Osband et al., 2016b; 2019). We hope this helps readers understand how RLSVI works and the underlying limitations of RLSVI.
In its original form, RLSVI is designed for the episodic Markov Decision Process for easy analysis. Here the word of "episodic" means the planning horizon (i.e., the episode length) is finite number T > O. Given a feature map ø S x A + IR in advance, RLSVI assumes the optimal Q-value function is linear model with respect to this feature map. That is, for any stage t 0, 1, RLSVI assumes
(s, = (s,ssa))))))))) Tr
(A.1)
where 0z IRd is the unknown optimal parameter and Q; the optimal value function at stage t. Note that differs from stage to stage, but they are all fixed along the training.
With the above assumption, RLSVI takes three steps to balance the trade-off between exploration and exploitation.
(Updating) Conditioned the collected data, RLSVI estimates the optimal parameter 0; in Bayesian way. In particular, RLSVI obtains the posterior distribution over 0f via solving Bayesian linear regression problem*. More specifically, the Bayesian linear regression problem consists of the fixed feature Φe and the label generated by dynamic programming; see (A.3). Furthermore, the posterior distribution can be obtained by the closed-form solution in (A.4).
(Sampling) With the posterior distribution over 02, RLSVI samples a specific parameter 0,, which forms the Q-value function Qz a) = Φe(5, a) Oz.
(Interaction) RLSVI takes the greedy action argmax, ((s,, a) stage to collect new data.
Let k indicates the episode count and indicates the stage/period count. Let [T'] indicates the set {0, 1, 1}. For instance, o Idd means the posterior mean at episode & and stage t. With these notations, the procedure of RLSVI is outlined in Algorithm
Algorithm RLSVI (Osband et al., 2016b; 2019)
posterior mean o < prior mean 8, posterior covariance Ej, + prior covariance T Vt E [T].
2: sample 02 _N Eo,t) for & [T].
3: for episode k = 0, 1, 2.... ... do
4: for stage
1, T 1 do
Interaction
5:
observe state
6: take the greedy action a; argmax, ((st, TO.
7: receive reward r(st, ar).
8:
end for
1,7 2, do 10: o 0 rt k+11t < update the posterior distribution (see (A.4)).
9:
for stage
Update
11: sample 0, NN Σt -..))
Sampling
end for end for
13:
For Line 10 Algorithm 1, RLSVI leverages the tool of Bayesian linear regression. Abstractly, given the feature matrix X Nxd (N is the number of samples) and the label vector Y E R. the posterior distribution over 6* can be computed in closed-form way. More concretely, RLSVI forms
Bayesian linear regression is reviewed in Appendix B.1.
16

---

Published as a conference paper at ICLR 2022
X, and Y, with the state-action pairs collected at stage t up episode k:
(50.1: ao,t)
yo,r
X, =
01($1,1, (1,1)
E RR Y,
//,
E [R*+1
(A.2)
Φ ((Sk,,,,k.)))
Lk,t
where
yk,t = {
Fk.t maxa (0,4) ((
if -
(A.3)
Tket
if =
With such defined X, and Y. RLSVI can compute the posterior distribution (otiiiionnn()) (V D), Covlo; D)) over 07:
X Y oe /.) 11
1/
Bi0 DJ = +.11
X1
Xx
w
(A.4)
CovlO; DJ = Et 1-1,,
Remark 2. As the feature is fixed in RLSVI, there exists efficient implementation of RLSVI based on the incremental update. Specifically, let be the feature covariance matrix, i.e.,
x, X,
For easy presentation, let dx,, denote of (sk.ee a,,)). Then, we have the incremental update formula:
#R+1, Px.t
Sr.ckke with o T.
Furthermore, we have a more efficient update rule for the posterior covariance in (A.4) by the Sherman Morrissn formula (see Lemma 1). More concretely, we have that
E = Lt. (1/02) OK. 1+ (1/o2) oi, Dx.
with Ej. = o
As side note, the term X, Y, in (A.4) can also be implemented in an incremental update way. In short, the posterior distribution is easy to compute when the feature is fixed.
Lemma 1 Shermmnn-Morrion Morrison formula). Suppose A E g" is an invertible square matrix and u Rhth are column vectors. Then A + up" is invertible if and only if 1 + o A- -u 0. In this case,
A uv A
(A+ ( w) A-1
+ w 1u
Here, T is the outer product of two vectors and v.
A.2 IMPLEMENTATION OF HYPERDQN
In this part, we provide more implementation details of HyperDQN.
Recall that work with value functions: the prior one and the differential one. The prior value function and the differential value function are independently constructed, meaning there are no shared parameters. The actual Q-value is the weighted sum of terms:
Q(s, G, 2) = Pprior Quee (+) (8, a) + Paitterential Qorran. (8, a),
(A.5)
where 3peicr 0 and Batteeential >> O are positive scalars. When Sprior Sditterential 1, recover the formulation in (4.2).
The feature extractor (i.e., the hidden layers) are task-specific, which will be discussed in Appendix C. For the hypermodel, the differential part is initialized based on the default initializer of PyTorch while the initialization of the prior hypermodel each row of vn is sampled from the unit hypersphere and P3 is based on the mean of the desired prior distribution. The purpose of this initialization is guarantee the Optior S (2) follows desired Gaussian distribution. For example, if want to obtain a prior distribution (111 7) for
little tricky. Following (Dwaracherla et al., 2020),
17

---

Published as a conference paper at ICLR 2022
Algorithm 2 HyperDQN
1: agent step +- 0, train step / 4-400 0. 0, 1, do 3: generate random vector ./
2: for episode
Sampling
4: instantiate the Q-value function Q5 a, a) for stage 0, 2, ... T- do observe state 8t. take the greedy action receive the next state 1 and reward r(st, az).
5:
Interaction
6:
7:
argmax, Qo(st; 2).
8:
9:
sample & uniformly from unit hypersphere.
10:
store (St, Qg, S, S(+1) into the replay buffer D.
agent step n <- n + 1.
12:
if mo (agent step n. train frequency M) == 0 then
Update
13:
sample a mini-batch D of (s, a, 5, 8') from the replay buffer D,
sample N random vectors z/- 2 {
15:
optimize v and fnddee using the empirical loss function (A.6) with D and ž. train step & +- 2 1.
16:
17:
end
18:
if mod (train step l, target update frequency G) 0 then
19:
update the target network.
end if
21:
end for
end for
Opiorr == Sunin (z), it suffices to set vs- = and to uniformly sample vn from the unit hypersphere, where 1 is vector with elements of 1.
According the population objective function in (4.2), the empirical objective function Clv, i Z) given the set 2 and mini-batch is
D
Σ
(Qumpells (s), ow Te Qpecdiction (s,iatioonsss,, (,,),))
2 o2
[lf((a))?
D
ZEEZ
(A.6)
where
Qpecdiction (8, a, 2) = Sprior Q S Su (s) Baifferential (=))
Qurger (s',2)
max
Bpriir Q0pece (=)(s', (0(s',a)) a') + Ratterentil Q fo (5', (ass,a))
In practice, (A.6) be efficiently solved by Adam (Kingma & Ba, 2015). In particular, sample multiple = and the mini-batch from the experience replay buffer to construct the empirical objective function. As such, Adam can be applied optimize the hidden layers and the hypermodel as illustrated in Figure I.
Remark (Feature Representation for Prior Value Functions). Different from supervised learning, the prior value function crucial for online decision making (Osband al., 2018). For the prior value functions, we not only need to consider the prior hypermodel but also the prior feature representation. Importantly, the feature extractor for the prior value function should be fixed rather than being shared with the differential part. In other words, we use two independent feature networks (i.e., the hidden layers) for the prior value function and the differential value function, respectively. Instead, the output of the prior value function would change if the prior value function and the differential value function share the same hidden layers, which violates the intuition that the prior value function should not be affected by the learning process.
A.3 SAMPLING FROM UNIT HYPERSPHERE
For completeness, we describe the method for uniform sampling over unit hypersphere. There are two steps:
18

---

Published as a conference paper at ICLR 2022
(1) Generate (I1, .2..... ................................ Fd): using zero mean and unit variance Gaussian distribution. Thus, the probability density of x
x + 22 +
p(x) (2T)
exp
2
is spherically symmetric.
Normalize the vector (x), 22 ... F.) to unit vector, namely x/||x|, which gives sample uniformly over the unit hypersphere. Note that once the vector is normalized, its coordinates are no longer statistically independent.
B CONNECTION BETWEEN BAYESIAN LINEAR REGRESSION AND HYPERMODEL
B.1 BAYESIAN LINEAR REGRESSION
In this part, we review the Bayesian linear regression. Let E Rdd be the feature and y (8*, + be the label, where w' (0, (3) is the observation noise. Here, we treat 0* as random variable and pose prior distribution Po (@ o2.) on 6*. Given the dataset D = {(2;, W)))- we can update the posterior probability density over #" by the Bayes rule:
p(0" D) x p (1(2), ((((z,,;))) y:) 0²) (0")
Thanks to the conjugate prior, the posterior distribution over 0* is also a Gaussian distribution N(E D), Cov D)) with
1 X
El0"
DJ =
X
(B.1)
2
0
Covl0"
[
2
X T
X
-
1/
1
(B.2)
@
p
where
y1
X
T22
R Nxd
Y=
y/2
R.V.
J/N
In summary, given collected dataset (i.e., the features and labels), we can obtain posterior samples through sampling from (EE(* D), Cov(0" D)).
Recently, Oshand al. (2019) provide another way of obtaining posterior samples through optimizing randomized least square problem.
Lemma 2 ((Osband et al., 2019)). Let x be the feature vector and the target be generated by y = (0*, + w", where w" ~ (O, o2) is the noise and the prior on H* is ( ((pp,0) o2I). Let
be the algorithmic noise that follows the same distribution with w" (t.e., NN0, o3)) and
θ ~ NN be a prior sample. Then,
argmin
Σ (a.9.aeD
(g+w 0 x))² +
100 θ
(B.3)
or
+ argmin
Σ (y+w- (0+ 2) (e+)
|0112
(B.4)
0
could yield a sample from the posterior distribution N (E[0*) [D]. Cov(0" D) defined by (B.I) and (B.2).
First, it is obvious that (B.3) and (B.4) are equivalent by the variable change trick. Let us focus on (B.4) to explain the main idea of Lemma 2. Notice that the posterior sample includes two parts: the prior and the differential (0 is a specific optimal solution to (B.4).. In particular, is a random leverage the variable, which depends the randomness in Based on this observation,
19

---

Published as a conference paper at ICLR 2022
optimality condition to obtain the optimal solution of (B.4). Subsequently, verify that the mean of 0 + 0 and its covariance are identical with the posterior mean E D and posterior covariance Cov(0- (D), respectively.
Remark 4. importantly, Lemma 2 recasts a sampling problem to an optimization problem, which provides purely computational cue to obtain posterior sample. Consequently, it provides another way of implementing RLSVI by solving the least square problem in each iteration. However, there is no clear advantage for this implementation under the case where RLSVI can work (e.g., tabular or linear MDPs).
B.2 HYPERMODEL
In this part, we provide more explanation about the hypermodel. To proceed, note that the main issue of the procedure in Lemma 2 is its computational efficiency. The reason is that we have to solve multiple randomized least square problems if we want to obtain many posterior samples. One of the motivations of the hypermodel is to address this computational issue. Indeed, the original optimization problem in (Dwaracherla et al., 2020) is
min J p(=)
Σ
(y+aw= (x)) + o?
[[((()) - Suma (=) (dz),
(B.5)
(R.MEJED
where P/prior Mo is the fixed prior hypermodel parameter. Consider the linear case where (f((=) fu(z) x, then (B.5) becomes
min [ p(=)
p(=))
(u+owzTe- (x()) x) [I((z)) (=))1 (dz), (T.DLE)D
Σ
which is very similar to (B.3) and the difference discussed in Remark Intuitively, the hypermodel wants to solve "infinite" randomized least-square problems simultaneously. Through this, the hypermodel can obtain multiple posterior samples by sampling 2.
Note that (B.5) has different form with the loss function in (4.1). However, discussed in (Dwaracherla et al., 2020, Section 2.5), these two loss functions are equivalent. To derive (4.1) from (B.5), take three steps: replace fz( in (B.5) with fip... fz) let (f)(s)(2) Df (x)+ (a:)
Dy (z) + 3f (e) (1)); 3) change the optimization variable from v to v/_
B.3 PROOF OF THEOREM 1
Here, we consider the linear hypermodel, i.e., f=(2) = VTJ 1b, where u E N.N.xe and vs Rd. By the property of Gaussian distribution, know that fz(2) N(ss, v/ Therefore, P/ and v/ un qualify the mean and covariance, respectively.
uw) Mw)
I).
By the formulation, there are two models in complete hypermodel: the prior one and the differential one. Specifically,
The prior hypermodel is
fa(=) DT = + Dy.
where (Zw: 1b)) fixed and a non-trainable variable. Here, we set the DJ o and Di 8p as the correct prior parameters, then fz( is sample from the prior distribution ./ V(Op. I.
The differential hypermodel is
[=(2) VIT z + bb,
where / = (M 1b) is trainable variable.
Let the sample (z,, y:) generated under Assumption 1. We augment each data sample (æ,, y:) E D with & independently sampled from unit hypersphere (refer Appendix A.3). Then, the dataset becomes
D ((x,, Mis &1) i 1,2....,, IDI.
20

---

Published as a conference paper at ICLR 2022
with the augmented noise realizations
=
Theorem 1 (Formal statement). Under Assumption 1, set v Jyl and 1/ ipriar =Bp. Let 1/ = (V)) be the optimal solution of (4.1) conditioned on specific realizations of & then 8: (2) + fur (2) (u + +vS (uerior + v (u + vnt)) with
up +1% E|0" |D], (v + Vio) (verer + v = Corle" [ Derre))())
where
= :=
D
Σ
E'a' +
Σ
(aET +5xT)) Covio" |
OwOp (a,E)ED
(mr &E)ED
Furthermore, the error term satisfies Bz(err(E)] - 0.
Proof of Theorem 1. For simplicity, we omit the subscript for the optimal solution to (4.1) in the proof. That is, we use the shorthand notation (Mw, 1b) for the optimal solution (4.1).
The objective function (4.1) for learning hypermodel given the data D becomes:
C(v; - - [ppx)
Σ
(y+ ow g x ((vw + fw) T 2 + (vs + k))) 2
o
|| mol? (dz)
+
o
(I.9.E)D
According to the first-order optimality condition:
Oc Eg Σ
o²
(- x ((vw + +w)) (vs + b))))
+
(vo
T 2 + vb)
Ou (R.D))ED
o
(B.6)
Σ
x(x ub + x Dn - 4) +
2
Vb
o
(E. It is straightforward to obtain that
ub + D.) = 0²
Σ
s(x ub + x T Dn
- y) +
4b.
dp
(E.DE)ED
Then, we can infer that
1
1
+
Dz
TE
Σ
zy + o. 23
0
DED
p
(a.
1
x
x
x
y
0p
= E [0*
[D]
where X E RPPidd Y E RPI, and E can recover the posterior mean.
(0 D defined in (B.1). This implies that the hypermodel
For the variable Vur, we calculate its partial derivative ac/Ov,
0²
E,
Σ
Two T- x ((v + (w))= 2 (vs + +b))) (-xz )
(v m
+
v2)=
o
(DDD
E,
Σ (-owz TowzTExzTT xx² (v Dw)) zxx
o T
T T
|
D
(B.7)
o
To proceed, we utilize the following helpful lemma.
Lemma 3. Let NO, Ta)- For any fixed vector E Rd,, have
E2 [a zxz ra.
21

---

Published as a conference paper at ICLR 2022
Proof. The proof is easy if we look at each entry of the matrix,
Eg [2" T axz 'Iles
E& [2 "afaz [as] = Ez
Σ 2R
242]
= 0,24
Then, with the above Lemma and (B.7), we further calculate
ac
Σ
(-owar
+ xx T (ur + (w)) + o
(B.8)
dv
op
(r.y,E)E
By the first order optimality condition, we have
(vw + Pwo) With the posterior covariance in (B.2)
1 X
x
-
Σ
owa
T
+ T
uw
o
(x,5)ED
E-1 = Cov (0* D) = (
of
and define the set S E (61, ,I. corresponding to the & in (I U/s Ee) E DD we obtain that
(uw TM vw))
=--1
Σ
+
of
1
Σ
(ownn Dwr owo E-1
o2 (#+E)
(m,E) (m))Et)
= =--1
X
+
I+
Σ
ot Exx +
(aET + +gaa) E-1
o
owop (s.f)
(x.()+(<))))
= -E-ΣEE-- + err(E), where the second equality is due to the fact that |kEl| = 1 and we set Dy = T, the beginning;
and err(E)- Σ-1 73 E(e of g'a'T T + awar Eis,) (xt + (xTx) T) E-!. Taking the
expectation over (E1, ... ((pi), we have
E=
Σ
x E'
0, Ez
(nnT + x)) =0. (x+5)
Σ
Finally, we have
Ez (w + -w)) (M + Dw)) = =I
+ Ez [er((E)] N
This implies the hypermodel can also recover the posterior covariance in expectation.
B.4 WHY INDEPENDENT GAUSSIAN NOISE CANNOT WORK FOR HYPERMODEL?
Following similar steps in Appendix B.3, we want to argue that the posterior approximation result cannot be achieved if replace: 2T with independent Gaussian noise in (4.1).
Similarly, we augment each sample (I,, y4) E with We ~ NO, o2) and denote w = (wi, (21,42,-...45 wppp) as the noise vector. The dataset becomes
D (I,, Bis wi : 1,2, ... (D]).
Now, the objective function for learning hypermodel given the data D becomes:
(v; D) [p(t) p(2)
Σ
(y (y+ x ((Vw + )w)) + (nr + 2))))
o² o²
| 2 + =011 m011)) (dz).
(R.DW))D
22

---

Published as a conference paper at ICLR 2022
Similar to (B.6), we have the first order optimality condition
dL
0² 1/ = 0.
E
x(x b
+
x' + w) +
x
Ovb
0
(x.
Then, have
xxxxx+x )
J/2 + E 10 DJ.
1
1 + D/
X
Oo
o
o
For the variable Mwn similar to (B.7), we calculate the partial derivative OC θv as
E
Σ
wy+w- ((Vor vw)) To + (vb + (b)1) (-xz
+
(v 2 16)2 T
(E.D.E)E
p
E
(-waz + x (Ver =
2xz
D
(DD
p
0² T T
Eg
(wT(uur (Vw Dw)) 2xxz" T )
+
w 2=
DD
(I.D)w))
p
Σ (xx (vro + Dw))
o
(#.WW)D
By the first order optimality condition, we have
(
(uw + 2w0) =
X
x
+
1/1
(/1)
Dr
02
o
Therefore, by the fact that D. Dw =o2I,
(vw + ) T (v + Dw)) = Σ-
-
1
-
1
--
+ Cov (0 D).
o
This implies that an independent Gaussian noise w cannot work and the z-dependent noise indispensable for posterior approximation.
C EXPERIMENT DETAILS
C.I ALGORITHM IMPLEMENTATION AND PARAMETERS
Common Hyperparameters. All agents use the same network structure as in (Mnih et al., 2015) on Atari and SuperMarioBros:
state - c3nv(32, 8, 4) + relu > conv 4, - relu - conv(64,3,
mlp(512) + relu - mlp(number of actions),
where (3nv 8, 4) means a convolution layer with 64 filters of size and stride of 4, and mlp (512) means a fully-connected layer with output size of 512, and relu stands for Rectified Linear Units.
The algorithmic parameters on Atari and SuperMarioBros basically follow (Mnih et al., 2015, Table 1). For example, the replay buffer size is 1M; the batch size is 32; the discount factor is 0.99; the target network update frequency is 10K agent steps; the train frequency is 4 agent steps; and the replay starts after 50K agent steps. For algorithms with e-greedy (e.g., DQN, BootDQN, OPIQ and OB2I), the exploration is annealed from 1.0 to 0.1 linearly (from 50K agent steps to 1M agent steps, respectively); the test is 0.05.
DQN. The training result of DQN (Mnih et al., 2015) on Atari is based on DQN Zoo (Quan & Ostro- vski, 2020) We implement DQN with tianshou" 10 framework and train on SuperMarioBros.
Pttpps: :/te:://ittttt pettps:/ggt thub.
nd/ http:///aaaa.aaaoooo/o////////aa
23

---

Published as a conference paper at ICLR 2022
OPIQ. We the implementation in the public repository https:/ /ttt:://ggtthtl com/ oowhi r opiq. For a fair comparison, we do no use the mixed Monte Carlo return and set the final to be 0.05. Other parameters follow (Rashid et al., 2020).
OB21. We use the implementation for OB2I in the public repository https: /ttp://gttthh com/ Bai Saichenjie jia /OB2I. The training data of OB2I on Atari is partially shared by authors in (Bai et al., 2021) (private communication). All parameters follow (Bai et al., 2021).
BootDQN. We modify the implementation for BootDQN from the public repository https:// to make a fair comparison. In particular, BootDQN uses 10 independent ensembles and the e-greedy strategy is same with DQN. We use the version with prior value functions (Osband et al.. 2018). Note that we do not implement the "vote" mode because we observe that it does not matter in practice.
github. com/ wow.anaaaaaaaaaaaaaaaa wwwaaannnnooootttaaoeooooooooooe
NoisyNet. We modify the implementation for NoisyNet from the public repository https: / com/ku240 (ate////ff-iin-rrdrrrre beleon.pttocc//bbbe waarech//lob/nnee www.///atte//eggeeeee cqp_grdqp net py to make a fair comparison. In particular, NoisyNet re-samples noisy network for action selection and update. The noise scale 0.5 and other parameters follow (Fortunato et al., 2018). 8)..
HyperDQN. We use the implementation as described Appendix A.2. Algorithm parameters are listed in Table 4. To stabilize training, each 2 corresponds to 32 mini-batch samples and the effective batch size HyperDQN 32 10 = 320.
Table 4: Algorithmic parameters of HyperDQN for Atari and SuperMarioBros.
Atari
SuperMarioBros
Deep Sea
dimension N₂
32
32
2
prior scale Sprior in (A.5)
0.1
0.1
10.0
differential scale Aaittrrntial in (A.5)
0.1
0.1
1.0
number of for training in (A.6)
10
10
20
noise scale o., in (A.6)
0.01
0.01
0.0
prior regularization scale op in (A.6)
0.1
0.1
0.0
learning rate
0.0001
0.0001
0.001
C.2 ENVIRONMENT PREPROCESSING
Atari. We follow the same preprocessing in (Mnih et al., 2015) and (van Hasselt et al., 2016). In particular, there are random no-operation steps (up to 30) before the interaction. Each agent step corresponds to 4 environment steps by repeating the same action while each environment step corresponds to 4 frames of the simulator. The raw score is clipped to {-1, +1} for training but the evaluation performance is based the raw score. Episodes are early stopped after 10SK frames as in (van Hasselt et al., 2016). The observation for the agent is based on stacked frames, which is reshaped to (4, 84.
Super-MarioBros. The observation and action preprocessing are the same with Atari 2600 suite. Two things are different: 1) there is no random "no operation": 2) the training reward is based on 0.01 x raw score rather than clipping. Moreover, the maximum episode length is 1500 x 4 = 6000 frames.
For algorithms (DQN, BootDQN, NoisyNet, HyperDQN) that we implement by the t tianshou framework, the training frequency is 10 and the target update frequency is 500 to accelerate training speed. Other parameters are identical to the one for Atari.
Deep sea. The implementation of the deep sea task is from bsui (Oshand et al., 2020). The neural network architecture is:
state - mlp(64) - relu -> mlp(64) - relu -> mlp(number of actions).
httpps: : / //g thub. com/ /deemmemmi nd/bsui deep_sea sea_peappp...
http:///sssbeeeeeeeeeeeeeee wtttte//rrreeeees/////// ronments/
24

---

Published as a conference paper at ICLR 2022
To make a fair comparison with BootDQN, the training frequency is 1, target update fiequency is 4, batch size is 128, and buffer size is 200K. For HyperDQN, its parameters are listed in Table 4. For BootDQN, it uses 10 ensembles and the other parameters are identical to HyperDQN. Both algorithms do not use e-greedy.
the setting in (Osband et al., 2018). In particular,
C.3 BAYESIAN LINEAR REGRESSION
The 2-dimensional Bayesian linear regression problem used in Section 4.3 is based on y Ow x - 0, + c, where I, y, Ow, 0b: E E IR. Specifically, e is sampled from the Gaussian distribution. To generate the dataset, is sampled from |-4, 4] uniformly. The total number of training samples is 50. The prior distribution for (fw: 86) is (0, I2) while the actual value (0w, is (6.06, 0.47) for the dataset generation.
We obtain the exact posterior distribution by the Bayes update rule. For hypermodel, the dimension of is 2. We use gradient descent with learning rate of 0.005 and momentum of 0.9. The number of of the gradient descent iterations is 10000. After the optimization, we visualize the 5000 samples from different distributions (e.g., the posterior distribution and the one transformed by the hypermodel) in Figure 2. Indeed, the KL-divergence between the exact posterior distribution and the counterparts by hypermoder (2 {) and hypermodel (W) are 0.1 and 326.4, respectively.
C.4 PARAMETER CHOICE
Noise scale ow.. In this part, we provide the ablation study about the noise scale ow. The numerical result is displayed in Figure 7. We observe the performance of HyperDQQN is not very sensitive dw-
SuparMaaroBros112
SuperMartoBoos122
10000
400-
Score
Eppodd Scoe
#00-
6000
4000
4000
X00-
2803
0
15 Prame (milloos))
Fomm (millooss)
Figure 7: Comparison of HyperDQN with
Figure 8: Comparison of HyperDQN with different prior scales op.
different noise scales ow-
Prior scale op. In this part, we provide the ablation study about the prior scale op. The numerical result is shown in Figure 8. We find that large prior scale results in poor performance. The reason is that the posterior update is slow under this case.
Hypermodel architecture. In this paper, we mainly focus on the linear hypermodel. Here, we investigate the variant with non-linear hypermodel (i.e., an MLP hypermodel). In particular, we consider the hypermodel is a two-layer neural network of width 64 with ReLU activation. We call this variant as HyperDON (MLP) and the original HyperDQN as HyperDON (Linear). It is intuitive that HyperDON (MLP) has a more powerful posterior approximation ability but it may be hard to train HyperDQN (MLP) since the architecture is more complex. The empirical results on Atari and SuperMarioBros are shown Figure 9. We see that HyperDQN does not obtain significant gains by an MLP hypermodel. We conjecture the reason is the trainability issue of the MLP hypermodel.
Number of ensembles in BootDQN. In this paper, we implement BootDQN with 10 ensembles, which follows the configuration in (Osband et al., 2016a, Section 6... However, in (Osband et al., 2018), BootDQN is implemented with 20 ensembles. We remark that the choice of 10 ensembles is commonly used in the previous literature (Rashid et al., 2020; Bai et al., 2021) since it is more computationally cheap. For completeness, we provide the ablation study about this parameter choice; Figure 10 for the result.
25

---

Published as a conference paper at ICLR 2022
Pong
SuperMarioBros 1-2
10000
Eppeode
//
Frome (millons))
Fame (millonss)
(a) Episode return on Pong.
(b) Episode return SuperMariiBros--122 1-2.
Figure Comparison of HyperDQN with linear hypermodel and a MLP hypermodel.
SuperMarioBrre-112
-19.8
6000
BooIDQN(10 ensemblee)
BooIDON(10 ansembles)
Episode Score
-20.0
BootDDN/20 onsembles)
5000
BooIDON(20 ersembles)
-20.2
4000
-20.4
Episode
3000
-00.6
2000
-20.8
1000
-21.0
Frame (millions)
Frame (million))
(a) Episode return on Pong.
(b) Episode return SuperMarioBros- 1-2
Figure 10: Comparison of BootDQN with 10 ensembles and 20 ensembles.
D ADDITIONAL RESULTS
D. ATARI
For all algorithms, learning curves on each game are visualized in Figure 11. The maximum raw scores on each individual game are reported in Table 5.
Relative improvement on each game. To better understand the improvement of HyperDQN, we visualize the relative score compared with baselines. Specifically, the relative score is calculated as (Wang et al., 2016). According the taxonomy in (Bellemare et al., 2016), we cluster environments by groups: "hard exploration (dense reward)", "hard exploration (sparse reward)", "easy exploration", and "unknown". See the results in Figure 12, Figure 13, Figure 14, and Figure 15.
proposed baseline
cerhhuman,bssllinng -hman human
We observe that HyperDQQ has improvements both "easy exploration" environments (e.g., Battle Zone, Jamesbond, and Pong) and "hard exploration" environments (e.g., Frostbite, Gravitar, and Zaxxon). However, we notice that HyperDQN does work well on very sparse reward tasks like Montezuma's Revenge. We explain the failure reason as follows. As we have discussed in the introduction, without a good feature, randomized exploration methods are rarely competent. On Montezuma's 's Revenge, the extremely sparse reward provides limited feedback for feature selection. As result, is expected that randomized exploration methods (including BootDQN and NoisyNet) do not work well for this task. In contrast, prediction error based methods (Pathak et al., 2017, 7; Burda al., 201 9b; Rashid al., 2020) could leverage specific architecture designs to provide auxiliary reward feedback to help feature selection and exploration. As result, these methods perform well on Montezuma's 's Revenge. We kindly remind that these methods do not perform well on other tasks because specifically designed architectures in these methods do not generalize well pointed out in (Taïga et al., 2020).
Commitment of randomized exploration. Here we provide the evidence that using the e-greedy strategy contradicts the commitment and leads to poor performance for HyperDQN; see the results in Figure 16. We observe that combing HyperDQN with e-greedy results in poor performance.
26

---

Published as a conference paper at ICLR 2022
ANTRE
Reseet
ANO
Baek
1990
scu0
200
203
112
1790
2003
Figure 11: Learning curves of algorithms on Atari Solid lines correspond to the median performance over 3 random seeds while shaded ares correspond to 90% confidence interval. Same with other figures for Atari.
D.2 SUPERMARIOBROS
For all algorithms, learning curves each game visualized in Figure 17.
27

---

Published as conference paper at ICLR 2022
Table 5: The maximal score over 200 evaluation episodes for the best policy in hindsight (af- ter 20M frames) for Atari games. The performance of the random policy and the human expert is from https: / com/ htep/eeepiiiii dign aiin_2200 aagn__oo/blllo http///ooomatter/////eoaooaaaeee Swari_dater py4 1101. The performance of OB2I is from (Bai et al., 2021).
Random
Human
OB21
OPIQ
BooIDQN
NoisyNet
HyperDON
Alien
227.8
7,127.7
916.9
2,316.7
2,623.3
2,596.7
2,910.0
Amidar
5.8
1,719.5
94.0
161.6
319.0
395.7
565.7
Assault
222.4
742.0
2,996.2
3,385.0
3,182.7
5,000.3
2,083.0
Asterix
210.0
8,503.3
2,719.0
1,500.0
3,466.7
4,000.0
2,283.3
Asteroids
719.1
47.388.7
959,9
976.7
3,353.3
3,143.3
3,190.0
Atlantis
12,850.0
29,028.1
3,146,300,0
1,780,266.7
835,166.7
857,100.0
880,233,3
Bank Heist
14.2
753.1
378.6
430.0
270.0
250.0
470.0
Battle Zone
2,360.0
13.454.5
8,756.5
18,333.3
22,666.7
20,333.3
24,333.3
BeamRider
363,9
16,926.5
3,736.7
4,385.3
7,002.0
5,467.3
3,955.3
Bowling
23.1
160.7
30.0
90.3
116.0
64.0
Boxing
0.1
12.1
75.1
53.7
56.3
Breakout
1.7
30.5
423.1
247.0
212.0
352.0
43.7
Centipede
2,090.9
12,017.0
2,66188
11,891.7
11,051.7
9,492.3
9,923.0
Chopper Command
811.0
7,387.8
1,100.3
1,666.7
1,900.0
2,966.7
2,733.3
Crazy Climber
10,780.5
35,829.4
53,346.7
71,566.7
88,400.0
133.3
1179666.7
Demon Attack
152.1
1.971.
6,794.6
3,805.0
9,148.3
8,845.0
8,755.0
Double Dunk
-18.6
-16.4
-18.2
-18.7
-6.0
3.3
2.7
Enduro
0.0
860.5
719.0
1,033.3
626.3
1,169.7
456.0
Fishing Derby
-91.7
5.5
-60.1
-91.3
-54.3
-3.7
-26.3
Freeway
0.0
29.6
32.1
26.3
9.3
25.0
32.7
Frostbite
4,334.7
1,277.3
1,640.0
1,853.3
4,020.0
3,943.3
Gopher
257.6
2.412.5
6,359.5
2.266.7
5,466.7
7,606.7
4,600.0
Gravitar
173.0
3,351.4
393.6
450.0
966.7
1,250.0
1,316.7
H.E.R.O
1,027.0
30,826.4
3,302.5
8,345.0
13,590.0
12,675.0
20,156.7
Ice Hockey
-11.2
-4.2
-11.7
-4.0
0.7
-1.7
Jamesbond
29.0
302.8
434.3
350.0
650.0
650,0
700.0
Kangaroo
52.0
3,035.0
2,387.0
2,400.0
8,666.7
2,333.3
10, 166.7
Krull
1,598.0
2,665.5
45,388.8
3,763.3
10,643.3
10,260.0
8,413.3
Kung-Fu Master
258.5
22,736.3
16,272.2
18,033.3
1,500.0
34,933.3
26,933,3
Montezuma's is Revenge
0.0
4,753.3
0.0
0.0
0.0
0.0
0.0
Ms. Pacman
307.3
6,95166
1,794.9
2,186.7
3,793.3
4,440.0
4,590.0
Name This Game
2,292.3
4,076.0
8,576.8
4,883.3
8,200.0
9,093.3
7,106.7
Pong
-20.7
14.6
18.7
-20.0
-17.7
2.5
21.0
Private Eye
69,571.3
1.174.1
5.124.3
7,641.0
11,018.7
2,810.0
QeBert
163.9
13,455.0
4,275.0
4,558.3
5,250.0
5,966.7
16,616.7
River Raid
1,338.5
17,118.0
2,926.5
4,536.7
8,003.3
5,993.3
8,020.0
Road Runner
11.5
7,845.0
21,831.4
20,866.7
17,266.7
3,533.3
27,033.3
Rohotank
2.2
11.9
13.5
15.3
11.7
37.7
19.7
Seaquest
68.4
42.054.7
332.1
1,846.7
2,180.0
230.0
1,360.0
Space Invaders
148.0
1,668.7
904.9
853.3
1,390.0
1,410.0
925.0
Star Gunner
664.0
10,250.0
1,290.2
933.3
13,300.0
22,066.7
3,633.3
Tennis
-23.8
-8.3
-1.0
-20.3
-1.0
-1.0
5,3
Time Pilot
3,568.0
5,229.2
3,404.5
4, 1,000.0
8,400.0
8,433.3
10, 166.7
Tutankham
11.4
167.6
297.0
184.0
269.3
181.3
213.3
Up and Down
533.4
11,693.2
5.100.8
37,893,3
16,333.3
52,476.7
16,520.0
Venture
0.0
1,187.5
16.1
133.3
266.7
700.0
966.7
Video Pinball
16,256.9
17,667.9
80,607.0
53,924.7
262.718.0
881,999.3
172,896.3
Wizard of Wor
563.5
4,756.5
480.7
2,500.0
4,266.7
6,066.7
7,266.7
Zaxxon
32.5
9,173.3
2,842.0
3,300.0
8,400.0
4,233.3
10,066.7
Commitment of randomized exploration. Here provide the evidence that using the e-greedy strategy contradicts the commitment and leads to poor performance for HyperDQN on SuperMario- Bros; see the result in Figure 18.
In addition, we provide the evidence that the randomized exploration approach BootDQN (Osband al., 201 6a) could obtain some gains if e-greedy is not used; the result in Figure 19. The result suggests that the original implementation of BootDQN does not satisfy the commitment property. Note that the variant without e-greedy is still inferior compared with HyperDQN.
28

---

Published as a conference paper at ICLR 2022
destive Score popp Compared with deig
1950
toderato (Dias
2.0%
-399%
Figure 12: Relative improvement of HyperDQQ compared with OPIQ (Rashid et al., 2020) on Atari
The relative performance is calculated as (human, baseline) human (Wang et al., 2016). Environments are grouped according to the taxonomy in (Bellemare et al., 2016, Table 1). "Unknown" indicates such environments are not considered in (Bellemare al., 2016).
proposed baseline
Fokiiee Scare of HyporOC Compared winh 002
7500
Figure 13: Relative improvement of HyperDQN compared with OB2I (Bai et al., 2021) on Atari. The proposed baseline
relative performance is calculated as max(human, huumn (Wang et al., 2016). Environments are grouped according to the taxonomy in (Bellemare et al., 2016, Table 1). "Unknown" indicates such environments are not considered in (Bellemare et al., 2016).
29

---

Published as a conference paper at ICLR 2022
Nebile Scer Hypertgh compaist Borrigo
Figure 14: Relative improvement of HyperDQN compared with BootDQN (Osband et al., 2018)
on Atari. The relative performance is calculated maxx(human, haseline) human (Wang et al., 2016). Environments are grouped according to the taxonomy in (Bellemare al., 2016, Table 1). "Unknown" indicates such environments are not considered in (Bellemare et al., 2016).
proposed baseline
Relaoive Score Hypud Camparsd lokyyle
4025
Cow Dny
200%
Figure 15: Relative improvement of HyperDQN compared with NoisyNet (Fortunato et al., 2018)
(hmman,asseline on Atari The relative performance is calculated as max hwwman, baseline) - human (Wang et al., 2016). Environments are grouped according to the taxonomy in (Bellemare al., 2016, Table 1). "Unknown" indicates such environments are not considered in (Bellemare et al., 2016).
proposed baseline
Freeway
Pong
Q'beri
30
MypwOON
HyswbON
12503
Mypw/ONN HypenDONiihh opolooggeedd
Eatocde Store
NWtt ess boodddy)
Hrresggawwhh opaldog
10003
7503
12-
-10
00
30
10
15
20
10 Frame (milions)
20
Frame (millions
Frame (milloon)
Figure 16: Comparison of HyperDQN with and without e-greedy Atari.
30

---

Published as a conference paper at ICLR 2022
SuperlArintros-
SuperMarollroo 1-3
Ep boore
4503
4000
2000
1993
SupartderiBrooee
BupentMerroroa022
BuparideciaBrce225
2500
100000
2000
+000
1000
4500
1001
3000
5593
SuportaridBroo-311
SuperMariiBros-3
SuparMarioBrs 3-3
50000
5302
Estos
20000
3002
10003
10200
1500
Frame (millions)
Frame (millions))
Frame (miibons))
1SpeOON
NotayYett
BoctDON
022
DON
Figure 17: Learning curves algorithms on SuperMarioBros. Solid lines correspond to the median performance over 3 random seeds while shaded ares correspond to 90% confidence interval. Same with other figures for SuperMarioBros.
SuperMMriiBrrostt
SuparManioBros-1 1-3
10000
Exteade Spore
12920
10000
HyrwDDNeeth epe gpelnngg
HaswDDNN
3000
Hype:20N) spalonggmay))
Pape:3ON
8020
Hycwrboh
HypwDDhysth epding
8000
6520
5000
4000
2000
1900
Frame (millions)
Framm (millions)
Frame (millions)
Figure 18: Comparison of HyperDQN with and without e-greedy on SuperMarioBros.
12000
SuperkMariorros-1-
SupparaariBBra-1122
Suparklaroorrss113
7500
BootDON
Egroade Score
10030
bothr epad congwead)
0000
BotDDNiitaar epx bi-(
4000
WorD ezetorggmeety
3000
8000
4000
8000
2000
1500
1000
0
10
15
0
10
15
Frame (milions)
Frame (millions)
Frame (millions)
Figure 19; Comparison of BootDQN with and without e-greedy SuperMarioBros.
31

---

Published as a conference paper at ICLR 2022
E DISCUSSION
E. DIRECT EXTENSION OF RLSVI COULD FAIL
In this part, we provide numerical evidence that the direct extension of RLSVI could fail for Atari tasks. In particular, we use randomly initialized convolutional neural network as the fixed feature extractor and implement RLSVI according Appendix A.I. Since we work with infinite horizon MDPs, we replace the non con-disco target in (A.3) by the corresponding discounted target. We display experiment results in Figure 20. In particular, we observe that such an implementation of RLSVI is unable to solve Atari tasks.
Freeway
Pong
O'beri
30
HypwOON
HyswDON RL
12000
MypeEQN RLSMI
Eptsade State
RLSY
10-
-15
Framo (milllons)
Frame (millors)
Frame (milions)
Figure 20: Comparison of RLSVI and HyperDQN on Atari.
E.2 TRAINABILITY ISSUES OF HYPERDQN
In this part, we continue the discussion of the architecture design in Section 4.1. In particular, we illustrate why the original architecture in (Dwaracherla et al., 2020) is not suitable for RL tasks.
Table 6: Information about the base model used for deep sea.
Shape fout) fout)
Expected Magnitude of Initialization (L/vFm)
Layer
(900, 64)
1/30
Layer
(64, 64)
1/8
Layer
(64, 2)
1/8
As we have argued in Section 4.1, the main challenge of applying the architecture in (Dwaracherla et al., 2020) is parameter initialization. To illustrate this issue, consider that we two-layer MLP neural network with a width of 64 for the deep sea task of size 30. Suppose we use the default Py PyTorch initialization 12 (i.e., sampling from the uniform distribution /d-1,, 1/d=-1))) which is also known as "1 "1/VJm"" with fin being the input dimension of the i-th layer. We list the parameter information in Table (recall that the state dimension is 900 and the action dimension is for the deep sea task). We see that the expected magnitude of the parameter differs over layers. In particular, the desired magnitude is quite small compared with the magnitude of the output of the hypermodel (~ 1). As a result, if we directly apply the hypermodel for all layers of the base model, the input signal over layers explodes and the gradient is quite large.
After about 10 iterations, we observe that the parameter diverges if we use the SGD algorithm and apply the hypermodel for all layers of the base model.
Even if we use adaptive algorithms like Adam, the training result is not expected; see the empirical result in Figure 21. In particular, if we apply the hypermodel for all layers of the base model, Q --values are very large and the resulting algorithm does not succeed.
Furthermore, this parameter initialization issue becomes more severe when we use deep convolution neural networks for Atari and SuperMarioBros tasks.
E.3 C-GREEDY IN MANY EFFICIENT ALGORITTMS
We realize many efficient algorithms (Osband et al., 2016a; Rashid et al., 2020; Bai et al., 2021) still use e-greedy in practice. However, we argue that e-greedy is not efficient since cannot write
stabl e/ wttttaaleegeeeeeeeeee //t.g//eetee/torhch..o nn L. nnar.. rraa html
32

---

Published as a conference paper at ICLR 2022
1.0
Deep Sea-30
Deep Sea-32
0.75
10-
0.2
16'
0:00
19066
33300
40006 $000
15200
3003
00000
Infortctions
(a) Episode return the deep sea.
(b) Q-values the deep sea.
Figure 21: Comparison of HyperDQN with two configurations: 1) the hypermodel is applied only at the last layer of the base model (ours); 2) the hypermodel is applied for all layers of the base model.
off sub-optimal actions after experimentation. In addition, combining with e-greedy violates the principle of commitment as discussed in Section 4.5. We conjecture existing practical algorithms combine their exploration strategies with e-greedy mainly due to imperfect imitation of theoretical algorithms, which is analyzed below. This direction deserves further investigation.
On the one hand, we believe BootDQN (Osband al.. 2016a) uses e-greedy to improve the diversity since finite ensembles could offer limited diverse action sequences. For instance, if the number of actions is larger than the number of ensembles, BootDQN cannot produce all possible action sequences to explore at the initial stage. In this case, e-greedy is somehow helpful. Another explanation is that BootDQN just follows the default setting of DQN (Mnih et al., 2015). In Figure 19, we see that the variant that drops the e-greedy could be better than the original implementation of BootDQN in some tasks.
On the other hand, there are many practical issues to implement OFU-based algorithms in real applications, as discussed Section 3. In fact, directly adding an exploration bonus yields unexpected outcomes. Let us (re-)illustrate this using the example of the deep sea (shown in Figure 5). Imagine the agent visits a certain path to collect the data; for instance, the red path in Figure 22. With the experience replay buffer, the agent only update the Q-value function with state-action pairs from the visited path. By exploration bonus, such state-action sequences would have larger Q-values. During the next episode, the agent would repeat the same action sequences by following the greedy policy. It turns out that theoretical algorithms like (Jin et al., 2018) do not have such an issue. This is because theoretically, algorithms in (Jin et al., 2018) can use an optimistic initialization. With the optimistic initialization, the algorithm instead would select other actions rather than visited actions. In practice, however, is not easy to obtain an optimistic initialization with deep neural networks (Rashid et al., 2020). Again, c-greedy could somehow avoid this issue.
update(so, left)
(ss, left)) > Q(50, right)
Q(5o, left) + bonus Q(50, right)
Figure 22: Illustration for the initialization issue of OFU-based algorithms. After the initialization, action "left" dominates at state 8g. After the experience replay buffer, action "left" dominates again at state 8p. This issue is caused by the pessimistic initialization by neural network (Rashid et al., 2020).
In addition to the initialization issue, the uncertainty (i.e., the exploration bonus) should propagate over stages in a backward manner. In (Jin et al., 2018), this operation is implemented by the exact dynamic programming. In contrast, practical algorithms randomly draw mini-batch from the
33

---

Published as a conference paper at ICLR 2022
experience buffer to update, which may not properly propagate the uncertainty. As result, the Q-values are not always optimistic, and induced action sequences may not be diverse. This issue is pointed out in (Bai et al., 2021). Again, e-greedy may be helpful to address this issue.
E.4 DISCUSSION NOISYNET
In this part, we explain the differences between HyperDQN and NoisyNet in detail. The following discussion aims provide insights about what HyperDQN can achieve while NoisyNet cannot. Note that we are by no means criticizing NoisyNet. Instead, NoisyNet is simple and has strong empirical performance. We hope the above discussion could provide intuitions (or explanations) why NoisyNet succeeds or fails under different cases.
First, as remarked in (Fortunato et al., 2018), NoisyNet is not ensured to approximate the posterior distribution of parameters. Therefore, NoisyNet is not a typical Thompson sampling based algorithm. The implication is that we may not use the well-known theory (Osband et al., 2013; 2019; Zanette al., 2020) to analyze NoisyNet.
Second, NoisyNet re-samples new policy every time step (Line 5 of Algorithm 1 in (Fortunato et al., 2018)). Consequently, it does not implement deep exploration like RLSVI (see (Osband, 2016b, Section 4.1)). This may explain the empirical result that NoisyNet can not solve the deep sea task when the problem size is large than 20 (see Figure (Osband et al., 2018, Figure 9)). Instead, BootDQN and HyperDQN can solve the deep sea task even if the problem size is large than 20.
Third, NoisyNet does not have the mechanism of "prior" (Osband et al., 2018) even though it is randomized. As a consequence, NoisyNet cannot leverage an informative prior to accelerate exploration when such information is available. In contrast, HyperDQN can achieve this goal as discussed in Appendix E.
E.5 EXTENSION TO CONTINUOUS CONTROL
In this part, we briefly discuss how extend the idea in this paper for continuous control tasks. We also present some preliminary results to support this direction.
Following the idea presented in Section 4.3, should leverage the hypermodel to capture the posterior distribution of the Q-value function. Considering the standard actor-critte methods, we can replace the vanilla critic with the one that is built by the hypermodel. In particular, last layer of the critic with a hypermodel. In this way, each corresponds to a specific critic from the posterior distribution. To perform policy optimization, we notice that each actor (i.e., a policy network) should be greedy to specific critic with the same index 2. To this end, the last layer of the actor network is also built by hypermodel. The architecture design is illustrated in Figure 23.
replace the
actor network
critic network
lopermendi LOoE
gymlic funter(s)
prilc
Opretia funna(x)
Bac modial
policy (s(
Qu(s.4)
Blkake
Prwduct Layar
actiic
Layers
Ohgactor
Bemtte
Syotin
Figure 23: Illustration for HAC. In addition to hypermodel in the critic network, there is also a hypermodel for the actor network.
Let (Deriic eritic) be the parameter for the critic network and (Qactor acttor) be the parameter for the actor network. Following the optimization framework in (Lillicrap al., 2016: Haarnoja et al., 2018), the training objective for the actor network is:
max ΣΣ
Q btaden parie (8, a22 a2; with a n Tgaie partor (8; 2);2)
(E.1)
madde
Nabieg 2E RED
34

---

Published as a conference paper at ICLR 2022
Algorithm 3 HyperrAcooCCitticHAACC)
for episode k = 0, 2, do generate a random vector 2 ~ N/ I). instantiate an actor TT(:; for stage = 0, 2, . do
Sampling
> Interaction
observe state 8t-
sample the action 0₃ ~ [0($;; 2).
receive the next state 8t+11 and reward r(s;, az).
sample & uniformly from unit hypersphere.
store (st, at, r, 5c+1) into the replay buffer D. agent step n < nt 1.
if mod (agent step n, train frequency M) == then
Update
sample a mini-batch of (s, a, r, 5') from the replay buffer D. sample random vectors z/: 2 = {=
optimize the critic network using the loss function (E.2) with D and Ž. optimize the actor network using the loss function (E.1) with D and 2. update the critic target network with exponential moving average.
end if end for end for
where Queise you is the critic network and i ga yaur the actor network. In particular, objective Palden
(E.1) states that we should sample actions from the actor network to maximize the Q-value function. The difference with the traditional actor-critic methods that we sample many actor networks (indexed by 2) to optimize.
Similarly, the training objective for the critic network is:
Σ
Σ
(Q
guntie commi (s, a, 2) ow TT = - (r (++ Nisbon panic (8, d z)))
min pottli
genise
#E2 (s,0,n''
(E.2)
with d' Togaa baokkn pore ()),)). In (E.2), Qpeni Habey potro is the target network. The goal of (E.2) to
perform the temporal difference learning to optimize the critic. Note that the prior regularization term is not appeared in (E.2) for easy presentation.
We call the above method as HyperActorCCriiccHHAC)) Its implementation is outlined in Algorithm 3, which shares many features with Algorithm 2.
Now, consider the Cart Pole task from dm_control" 13 (Tunyasuvunakool et al.. 2020) testbed; see Figure 24a Detailed environment information is provided as follows: the dimension of the state space is 5, the dimension of the action space is 1, the planning horizon is 1000 and the reward is between O and 1. This environment is standard platform to test the exploration efficiency for continuous control algorithms because the agent can only obtain +1 reward when it succeeds and obtain 0 reward otherwise.
We compare extension (HAC) with the strong baseline SAC (Haarnoja al., 2018). Even though the policy entropy reward is used to guide exploration, SAC does not have the epistemic uncertainty qualification like HAC. As result, we expect SAC does not perform well for Cart Pole. The numerical result is displayed in Figure 24b. We see that HAC outperforms SAC on this hard exploration task.
E.6
WHEN AN INFORMATIVE PRIOR IS AVAILABLE
In this part, briefly discuss the role of prior value functions in our formulation. In particular, we argue that if an informative prior value function is available, the exploration efficiency can be significantly improved.
Phttps: //atps://gg //gi thub. ccom/deepm nd/ ndddn_ddddnneeeeeeeeeeen cm
35

---

Published as a conference paper at ICLR 2022
CartPioo Swwnguu GarPitt-riingu Baarss Reward))
600
30C
600
Extoods Store
Number Irrowd ore lore))
(a) Illustration for Cart Pole.
(b) Episode return on Cart Pole.
Figure 24: Comparison of HAC and SAC on the hard exploration Cart Pole (Tunyasuvunakool et al., 2020).
Here we show the learning curve with an informative prior in Figure 25. In particular, this informative prior value function is obtained from the pre-trained model after 20M frames. We see that this informative prior value function improves efficiency a lot. Note that the main goal of this experiment to illustrate that an informative prior could accelerate exploration. We will consider how to automatically acquire an informative prior with human demonstrations (Hester al., 2018; Sun et al., 2018 88 in the future.
Hypwiion
HygurOChtee entaraai phop
Ephoods Stme
05
12
(milions)
Figure 25: Comparison of HyperDQN with and without an informative prior on SuperMarioBros-1133
36


Reviews:
[{"review_id": "ViRWbwWAJRE", "reviewer": "Reviewer_C9G4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths: \n+ The outcome of the paper which adapts the ideas from RLSVI to deep reinforcement learning settings is significant and practical. \n+ The paper is very well written, clear, and easy to understand. The supplementary materials provide most of the information needed for acquiring a better understanding of the paper. \n+ The authors provide theoretical analysis and proofs to support their main ideas and design choices. \n+ The experimental results show superior performance of HyperDQN compared to state-of-the-art algorithms. \n+ The results are reproducible as the implementation and experimental details are provided in the paper.\n\nWeaknesses: \n- The proposed approach provides incremental contributions w.r.t. the existing ideas from the previous work.\n- The contributions are very specific to a class of problems and algorithms.\n\nComments: \n- The main ideas of the paper has been previously introduced in the literature and is further extended to the deep RL scenarios which make the presented contributions only somewhat novel. \n- The paper can be improved by providing some information and\\or intuition about the generalizability of the proposed approach to the other domains. Additionally, discussions about the challenges in extending the proposed idea to the areas such as continuous control, offline RL, etc. would be highly appreciated. \n- Could you elaborate about the challenges and potential problems that could arise when jointly optimizing the hypermodel and the feature extractor? One of the main contributions of the paper is addressing the major problems with RLSVI which are restricting its applications in deep RL. While addressing these limitations regarding computational costs of RLSVI is discussed extensively, providing a specific cost function to jointly optimize the feature extractor and the hypermodel might lead to stability and convergence problems. Hence, it would be beneficial if the authors provide further insights into this matter.\n", "summary_of_the_paper": "The paper introduces HyperDQN, a novel exploration technique for deep reinforcement learning, which extends the ideas from an existing method, namely RLSVI, to the deep RL settings. HyperDQN optimizes a linear hypermodel, which is used to compute state-action values as a function of extracted features, to work as a module that converges to a sample from the posterior distribution of the Q-value function. The authors further present a specific cost function to jointly optimize the hypermodel and the feature extractor that can efficiently address the limitation of the RLSVI approach in deep RL scenarios. Empirical study demonstrates significant improvement compared to the competitors on several benchmarks.", "summary_of_the_review": "Overall, the paper introduces a novel approach for randomized exploration in deep RL, is well written, and shows strong promise in terms of performance compared to other state-of-the-art methods. Additionally, it includes valuable theoretical and experimental discussions that provide further support for their contributions. I thus vote for an accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T3njMhocKf1", "reviewer": "Reviewer_GmJU", "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": "The paper begins with a strong motivation towards computationally implementing RLSVI in Deep RL using a base and meta models, and also points out reasons why this is non-trivial. Also, the main differences between BootDQN and HyperDQN are also discussed, which is important because BootDQN is a highly relevant prior work in this domain. Overall the paper is well-written and has strong motivations that are relevant to the RL community at large. \n\nThe following are some of the questions based on my understanding of the paper and would be great if the authors could clarify some of them: \n\n1. The meta-model in HyperDQN is considered as a linear parameterized model and there is a theoretical justification for this. What would happen to the empirical/theoretical results if the meta-model is a non-linear function of the latent variable z? I am inclined to think that the representation power for the posterior distribution would be better and thus should produce improvements overall.\n\n2. How are the sigma_w and sigma_p parameters chosen in the objective function? Have the authors considered a baseline where an agent uses an identical artificial noise term for modifying the Q_{target} (i.e., sigma_w z^{\\top} \\epsilon_i ) to the one used in HyperDQN? \n\n3. The Atari performance curves summarized in Fig 3 is not sufficient to demonstrate the utility of the presented approach. This curve is computed over all the Atari games (some of them require no exploration and some require a complex strategy for exploration). It would be more appropriate to show how the agent performs on “hard-exploration” and “easy-exploration” games (this classification is presented in Bellemare et al. 2016) rather than present a summary across all games. \n\nAlso, why are the agents only trained for 20M frames? It is conventional in Atari to run the agents for 200M frames (Machado et al. 2018). This makes it easier to compare the performance of HyperDQN wrto the prior methods in Atari. \n\nA minor comment: why do some curves in Fig 3 start at 0 and another starts at a value lower than 0? \n\nBellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. Unifying count-based exploration and intrinsic motivation. In NeurIPS, 2016.\n\nMachado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hausknecht, M., & Bowling, M. (2018). Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61, 523-562.\n\n4. How many random seeds were used to produce the learning curves in all the experiments (Atari, Mario and DeepSea)? It would be useful to add this information in the main text. Also, are the error bars reported in each of the presented learning curves?\n", "summary_of_the_paper": "The paper presents HyperDQN as a practical algorithm of Randomized least-square value iteration (RLSVI).  HyperDQN consists of two parametric models: first is a base model that is similar to that of a DQN agent and the second a meta model that parameterizes the last layer of the Q-network as a function of a latent variable. The purpose of this architecture is to generate posterior samples using the diverse Q-value functions represented through this architecture. The paper demonstrates this approach empirically across a variety of Atari games, SuperMarioBros and DeepSea. \n", "summary_of_the_review": "Overall, I think the contribution would be important to the RL community. My main concerns with the paper is that the presented approach claims to be helpful for exploration but the empirical results are not demonstrating this: One specific way to demonstrate this would be to show and emphasize that HyperDQN is able to achieve better returns on Atari games that are classified to be hard-exploration games. This would be a more powerful argument for HyperDQN. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CIFGP0qu-UV", "reviewer": "Reviewer_2epQ", "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": "### Strengths\nOverall, I think it is a good trial to extend the idea of Hypermodel to the realm of deep reinforcement learning. Compared with BootDQN, *HyperDQN* will require much less computational power. Meanwhile, the paper provides a large amount of experiment results to show the superior performance of *HyperDQN*. Meanwhile, the paper is also written in a clear logical flow.\n\n### Weaknesses\nI apologize if I understand incorrectly. One of my major concern is on the novelty. Given the existence of Hypermodel, the *HyperDQN* seems to be a very straightforward application of it on deep reinforcement learning without more insights. Meanwhile, from my perspective, the Theorem 1 simply re-writes the motivation of Hypermodel in a mathematical way, using linear hypermodel to approximate the posterior distribution, which is already explained in [1].\n\nAnother concern I have is about the performance of *HyperDQN*. Specifically, although the experiments compare *HyperDQN* with BootDQN, it seems that this paper uses the version of BootDQN based on [2]. However, the version of BootDQN in [3] has much better performance than that in [2]. Further, it seems the BootDQN in [3] did not use $\\epsilon$-greedy. Have you compred *HyperDQN* with the BootDQN in [3]?\n\n**Honestly, I'm not very experienced in running experiments, so I apologize if the above comments on experiments contain some flaws.**\n\n### Questions\n- Does *HyperDQN* contain other insights that are not presented in [1]?\n- Did the comparison experiments use BootDQN in [2] or [3]?\n- Did you compare *HyperDQN* and BootDQN on deep sea?\n- When you ran BootDQN, did you use number of ensembles significantly less than the one used in [3]?\n\n### Suggestions on Writing\n- In appendix C, it seems $b$ should be replaced by $\\nu_b$ in equation C.6.\n- At the bottom of page 4, it says $\\theta_{\\mathrm{predict}}\\in\\mathbb{R}^{d\\times N_a}$, but in the previous paragraph, it also says $\\theta_{\\mathrm{predict}}\\in\\mathbb{R}^d$. This can potentially be confusing.\n- In Theorem 1, it is may be better to replace \"then $\\theta:=\\dots$ with\" by \"then $\\theta:=\\dots$ satisfies\"\n\n```\n[1] Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy. Hypermodels for exploration. In Proceedings of the 8th International Conference on Learning Representations, 2020.\n\n[2] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems 29, pp. 4026–4034, 2016a.\n\n[3] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. In Advances in Neural Information Processing Systems 31, pp. 8626–8638, 2018.\n```", "summary_of_the_paper": "This paper proposes a new posterior sampling-based exploration method, called *HyperDQN*, for deep reinforcement learning. Conceptually, *HyperDQN* is modified based on randomized least-square value iteration (RLSVI) and it resolves the limitations of RLSVI on feature engineering and high computational complexity. Technically, *HyperDQN* extends the Hypermodel technique, which is only used for bandit learning in its original paper. The performance of *HyperDQN* is evaluated on Atari 2600 games, SuperMarioBros and deep sea environment.", "summary_of_the_review": "The paper proposes a computationally lighter method *HperDQN* for exploration in deep reinforcement learning and shows its superior performance in experiments. However, the formulation of *HyperDQN* is conceptually not novel and its performance compared to other methods is also questionable.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7y5uyLcHrwv", "reviewer": "Reviewer_TPoj", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "$\\textbf{Strength}$: \n- This work tackles an important problem of exploiting randomized exploration methods in deep reinforcement learning problems.\n- This paper is very well written and easy to follow.\n- Overall the method of combining hypermodel with Q-network is quite sound and very general to be applied on deep RL problems.\n- The empirical evaluation results are very extensive where relevant baselines are considered for comparison.\n\n$\\textbf{Weakness}$:\n- Very limited novelty where the idea is from the work [1]. \n- During comparison, only results at intermediate training stage  (i.e., 20M frames)  is presented while the detailed scores for the full training is missing. So it is unclear if the method could really be the next state-of-the-art method for Atari 2600 test suite.\n-Only limited number of baselines are considered. There is not decent exploration methods, such as UCB-type exploration or ramdomized exploration with noisy nets, being considered for comparison.  \n\n\n$\\textbf{Detailed comments}$:\n\n1. My primary concern is about the novelty of this paper. I found that both the formulation for hypermodel and the loss function for optimizing the hypermodel is inherited from the existing work [1]. In [1], a more general formulation for the hypermodel has been discussed which includes linear models, neural models and additive prior models. In HyperDQN, a linear hypermodel is adopted where there is nothing new for the method. Thus the contribution of this paper is not in terms of introducing a new method but is to show additional experimental results for an existing method on several deep RL domains. I feel such contribution might not be significant enough to be published as a full paper in ICLR.\n\n2. This paper tackles the policy learning problem from a direction of considering randomized exploration method. It claims the randomized exploration method O2BI as a SOTA exploration method but I do not think so. Generally, the O2BI as well as HyperDQN is only compared with limited baselines when the training is incomplete. I feel that many other variants of UCB-type algorithms, such as noisy net [2] might be able to outperform O2BI or HyperDQN greatly with 200M training budget. For instance, prediction-error based exploration methods could effectively progress on the extremely hard exploration task Montezuma's Revenge while O2BI and HyperDQN make no progress on it. Therefore, a more inclusive exploration methods for discussion/comparison is desired. \n\n3. The training curves presented in Fig 12 come with no error bars and/or O2BI is missing from the curves.\n\n4. I feel noisy net is also a related randomized exploration model which should be considered for discussion and/or experimental comparison.\n\n[1] HYPERMODELS FOR EXPLORATION\n[2] NOISY NETWORKS FOR EXPLORATION", "summary_of_the_paper": "This paper proposes a new randomized exploration method termed HyperDQN. \n\nIt aims to improve the popular Randomized Least Square Value Iteration (RLSVI) method by addressing RLSVI's major limitations of computational burden and its requirement of known good features in advance to adopt the linear setting. \n\nThe principal of HyperDQN is to combine DQN with a probabilistic hypermodel which could generate posterior samples for the parameter values of the weights at the last linear layer of the Q-function. Both the hypermodel and the Q-function could be jointly optimized during training. By sampling the Q-function parameters, it helps the model to select exploratory action sequences.\n\n Empirical evaluation results are provided in Atari 2600 domain, SuperMarioBros and deep sea. Overall, the proposed method could outperform Bootstrapped DQN, Double DQN and another recent bootstrapping baseline termed OB2I in majority of the testified domains. ", "summary_of_the_review": "This paper is a well written one with extensive experimental results. \n\nThe novelty of this method is rather limited as the method is exactly the same as the one proposed in a prior work. \n\nThe empirical evaluation results appear to be less convincing to me because the results on Atari 2600 are only shown for intermediate model trained after 20M frames and the full training scores (inferred from the learning curves in Fig 12) appear to be much inferior than another variant of randomized exploration model which is the noisy net. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends Randomized least-square value iteration (RLSVI), which is a method for exploration-exploitation tradeoff that is suitable for linear FA, to the deep RL setting. A key component is using Hypermodels of Dwaracherla et al. (ICLR, 2020) to generate the weights of last layer of the DNN. This generates a learnable randomness required in an RLSVI-like procedure.
The paper provides some theoretical results regarding Hypermodels, and provides extensive experiments to show that their method is a competitive one in solving exploration problems.

The majority of the reviewers are positive about this work. The concerns include the incremental nature of this work and the empirical results. In my opinion, the algorithmic contribution is reasonable, but somehow incremental. The theoretical results are minor, but acceptable. The empirical results are extensive, though they have some shortcomings.
I explain the algorithmic and empirical contributions below:


**Algorithmic Contribution:**
Similar formulation has been done by  Dwaracherla et al. But that work does not consider the RL setting, and instead focuses on the bandit setting. This work provides such an extension. A straightforward application of Hypermodels does not work for DRL, but some simple, yet crucial, tricks needs to be applied to make it work. The trick is to use Hypermodel to generate the weights of the last layer, instead of all layers. Although this is simple, the fact that it enables the method to work for DRL paper is significant.


**Empirical Results:**
The empirical results are quite extensive. There are two main issues with them though:

a) Many experiments on the Atari Suite are terminated after 20M samples. This is shorter than usual.
b) The experiments are only repeated for 3 runs (seeds) -- except one, which used 5 runs.

The authors' answer for (a) is that they have a limited compute budget, and running for 200M samples would cost them about $20K. Also they argue that 20M samples is enough to show the benefit in a better exploration method, as shown by some other papers.

After some inquiries, it seems that this $20K value has the correct order to run the experiments on a cloud (maybe within a factor of 2 or 3). Given this prohibitive cost, I am willing to accept that 20M samples might be sufficient for proving the main points of this paper.  I am not giving a large weight to this in my evaluation.

The main concern for me, however, is having only 3 independent runs of the algorithms, especially given that the issue under study is the efficiency of exploration-exploitation tradeoff, and that the proposed method has a lot of randomness built-in. This is the main weakness of the empirical results in my opinion, and not the 20M samples issue.

For instance, Figure 3 (Human-normalized score over 56 environments in Atari 2600 suite) does not have any confidence interval information. And Figure 4 has some shaded areas around the curves, but it is not clear whether it is standard deviation, standard error, or some other quantification of uncertainty.

Even though this is a borderline paper, I recommend acceptance of this work under the expectation that the authors should improve their empirical studies. In particular, I recommend much larger number of independent runs (seeds), maybe around 10 or so, with proper information about the uncertainty of the estimates. If running this for all games is prohibitive, showing the performance with more runs on a subset of the games is sufficient. Also I encourage the authors to consider NeurIPS 2021 paper "Deep Reinforcement Learning at the Edge of the Statistical Precipice".
Decision: Accept (Poster)