Deep Randomized Least Squares Value Iteration
Authors: Guy Adam
Tom Zahavy
Oron Anschel
Nahum Shimkin
Venue:  (2020)
Keywords: Thompson Sampling
Deep Learning
Reinforcement Learning

Abstract: Exploration while learning representations is one of the main challenges Deep
Reinforcement Learning (DRL) faces today. As the learned representation is dependant in the observed data, the exploration strategy has a crucial role. The popular DQN algorithm has improved significantly the capabilities of Reinforcement
Learning (RL) algorithms to learn state representations from raw data, yet, it uses
a naive exploration strategy which is statistically inefficient. The Randomized
Least Squares Value Iteration (RLSVI) algorithm (Osband et al., 2016), on the
other hand, explores and generalizes efficiently via linearly parameterized value
functions. However, it is based on hand-designed state representation that requires
prior engineering work for every environment. In this paper, we propose a Deep
Learning adaptation for RLSVI. Rather than using hand-design state representation, we use a state representation that is being learned directly from the data by a
DQN agent. As the representation is being optimized during the learning process,
a key component for the suggested method is a likelihood matching mechanism,
which adapts to the changing representations. We demonstrate the importance of
the various properties of our algorithm on a toy problem and show that our method
outperforms DQN in five Atari benchmarks, reaching competitive results with the
Rainbow algorithm.

Under review as a conference paper at ICLR 2020
DEEP RANDOMIZED LEAST SQUARES VALUE ITERA- TION
Anonymous authors Paper under double-blind review
ABSTRACT
Exploration while learning representations is one of the main challenges Deep Reinforcement Learning (DRL) faces today. As the learned representation de- pendant in the observed data, the exploration strategy has crucial role. The pop- ular DQN algorithm has improved significantly the capabilities Reinforcement Learning (RL) algorithms to learn state representations from raw data, yet, it uses a naive exploration strategy which is statistically inefficient. The Randomized Least Squares Value Iteration (RLSVI) algorithm (Osband al. 2016), on the other hand, explores and generalizes efficiently via linearly parameterized value functions. However, it is based on hand-designed state representation that requires prior engineering work for every environment. In this paper, we propose a Deep Learning adaptation for RLSVI. Rather than using hand-design state representa- tion, we use a state representation that is being learned directly from the data by a DQN agent. As the representation being optimized during the learning process, a key component for the suggested method is a likelihood matching mechanism, which adapts to the changing representations. We demonstrate the importance of the various properties of our algorithm toy problem and show that our method outperforms DQN five Atari benchmarks, reaching competitive results with the Rainbow algorithm.
INTRODUCTION
In Reinforcement Learning (RI.), an agent seeks to maximize the cumulative rewards obtained from interactions with an unknown environment (Sutton al., (998). Since the agent can learn only by its interactions with the environment, it faces the exploration-explotatio dilemma: Should it take actions that will maximize the rewards based on its current knowledge or instead take actions to potentially improve its knowledge in the hope of achieving better future performance. Thus, to find the optimal policy the agent needs to use an appropriate exploration strategy.
Classic RL algorithms were designed to face problems in the tabular settings where table taining a value for each state-action pair can be stored in the computer's 's memory. For more general settings, where generalization is required, common practice is tation (or state-action), upon which a function approximation can be learned to represent the value for each state and action. RL algorithms based linear function approximation have demonstrated stability, data efficiency and enjoys convergence guarantees under mild assumptions (Tsitsiklis & Van Roy 1997 Lagoudakis & Parr 2003). They require that the desired learned function, e.g. Q- function, will be a linear combination of the state representation. This is, of course, a hard constraint as the representation hand-designed, where the designer often does not know how the optimal value-function will look like. Furthermore, hand-designed representation is environment-specific and requires re-designing for every new environment.
hand-designed state represen-
The DQN algorithm (Mnih et al., 2015) has changed RI. Using Deep Neural Networks (DNN) as function approximators, the DQN algorithm enabled the learning of policies directly from raw high- dimensional data and led to unprecedented achievements over wide variety of domains (Mnih et al. 2013). Over the years, many improvements to DQN were presented, suggesting more fitting network architectures (Wang al. 2015), reducing overestimation ( (Van Hasselt et al. 2016 Anschel al.) 2017) or improving its data efficiency (Schaul et al.) 2015). Despite its great success, DQN uses the overly simple e-greedy strategy for exploration. This strategy one of the simplest exploration

---

Under review as a conference paper at ICLR 2020
strategies that currently exist. The agent takes random action with probability and takes the optimal action according to its current belief with probability 1 1-6 c. This strategy is commonly used despite its simplicity and proven inefficiency (Osband et al. 2016). The main shortcoming of e-greedy and similar strategies derives from the fact that they do not use observed data to improve exploration. To explore, it takes completely random action, regardless of the experience obtained by the agent.
Thompson Sampling (TS) (Thompson, [933), is one of the oldest heuristics to address the 'explo- ration/exploitation" trade-off in sequential decision-making problems. Its variations were proposed in RL (Wyatt 1998 Strens 2000) and various bandits settings (Chapelle & Lij 2011, Scort 2010). For Multi- Armed Bandit (MAB) problems, TS is very effective both in theory (Agrawal Goyal 2012 (013) and practice (Chapelle & Li. 201I). Intuitively. TS randomly takes actions according to the probability it believes to be optimal. In practice, a prior distribution assumed over the model's parameters y(w), and a posterior distribution p p(w D) is computed using the Bayes theorem, where D is the observed data. TS acts by sampling models from the posterior distribution, and plays the best action according to these samples.
Randomized Least Squares Value Iteration (Osband et al. 2016) is an RL algorithm which uses lin- ear function approximation and is inspired by Thompson Sampling. It explores by sampling plau- sible Q- ffunctts from uncertainty sets and selecting the action that optimizes the sampled models. This algorithm was proven to be efficient in tabular settings, with bound on the expected regret that match the worst-case lower bound up to logarithmic factors. More importantly, it demonstrates efficiency even when generalization is required. Alas, it assumes linearly parametrized value function on a hand-designed state representation, the success of this algorithm crucially depends on the quality of the given state representation.
In this paper, we present a new DRL algorithm that combines the exploration mechanism of RLSVI with the representation learning mechanism of DQN; we call it the Deep Randomized Least Squares Value Iteration (DRLSVI) algorithm. We use standard DQN to learn state representation and ex- plores by using the last layer's activations of DQN as state representation for RLSVI. To compen- sate for the constantly changing representation and the finite memory of DQN, we use a likelihood matching mechanism, which allows the transfer of information held by an old representation regard- ing past experience. We evaluate our method on a toy-problem- - the Augmented Chain environment for a qualitative evaluation of our method on a small MDP with a known optimal value function. Then, compare our algorithm to the DQN and Rainbow algorithms several Atari benchmarks. We show that it outperforms DQN both in learning speed and performance.
RELATED WORK
Thompson Sampling in Multi-Armed Bandit problems: Thompson Sampling (TS) (Tompson 1933), is one of the oldest heuristics to address the "exploration/exploiation"" trade-off in sequen- tial decision-makinn problems. Chapelle Li (201T) sparked much of the interest in Thompson Sampling in recent years. They rewrote the TS algorithm for Bernoulli bandit and showed impres- sive empirical results on synthetic and real data sets that demonstrate the effectiveness of the TS algorithm. Their results demonstrate why TS might be a better alternative to balance between ex- ploration and exploitation in sequential decision-make like the Upper Confidence Bound algorithm (Auer et al.) 2002). Agrawal & Goyal (2013) sug- gested a Thompson Sampling algorithm for the linear contextual bandit problem and supplied a high- boabbbrbbability regret bound for it. They use Bayesian Linear Regression (BLR) with Gaussian likelihood and Gaussian prior to design their version of Thompson Sampling algorithm. Riquelmee ct al. (2018) suggested performing a BLR on top of the representation of the last layer of neural network. The predicted value v; for each action a; is given by e; = S 2g. where 2n is the output of the last hidden layer of the network for context x. While linear methods directly try to regress values on they independently trained a DNN to learn a representation 2, and then used BLR to regress v on z, obtaining uncertainty estimates on the 3"s, and making decisions accordingly via Thompson Sampling. Moreover, the network is only being used to find good representation Since training the network and updating the BLR can be done independently, they train the network for fixed number of iterations, then, perform forward pass on all the training data to obtain the new 2,, which is then fed to the BLR. This procedure of evaluating the new representation for all the observed data is very costly, moreover, it requires infinite memory which obviously does not
problems than other popular alternatives
2

---

Under review as a conference paper at ICLR 2020
scale. Zahavy & Mannor (2019) suggested matching the likelihood of the reward under old and new representation to avoid catastrophic forgetting when using such an algorithm with finite memory.
In the Reinforcement Learning settings, Strens 2000 suggested method named "Posterior Sampling for Reinforcement Learning" (PSRL) which is an application of Thompson Sampling to Model-Based Reinforcement Learning. PSRL estimates the posterior distribution over MDPs. Each episode, the algorithm samples MDP from it and finds the optimal policy for this sampled MDP by dynamic programming. Recent work (Osband et al. 2013 Os- band & Van Roy, 2017) have shown a theoretical analysis of PSRL that guarantees strong expected performance over wide range of environments. The main problem with PSRL, like all model- based approaches, is that it may be applied to relatively small environments. The Randomized Least Squares Value Iteration (RISVT) algorithm is an application of Thompson Sampling to Model-Free Reinforcement I Learning. It explores by sampling plausible Q-functions from uncertainty sets and selecting the action that optimizes the sampled models.
Thompson Sampling in RL:
Various approaches have been suggested to extend the idea behind RLSVI to DRL. Bootstrapped DQN (Osband et al. 2017) uses an ensemble of Q-networks, each trained with slightly different data samples. To explore, Bootstrapped DQN randomly samples one of the networks and acts greedy with respect to it. Recently, Osband et al. (2018) extended this idea by supplying each member of the ensemble with different prior. Fortunato et al. (2017) and Plappert et al. (2017) investigate a similar idea and propose to adaptively perturb the parameter- space, which can also be thought of as tracking approximate posterior over the network's param- eters. OODonnohuue et al. (2017) proposed TS in combination with uncertainty Bellman equation, which connects the uncertainty any time-step the expected uncertainties at subsequent time- steps. Recently and most similar to our work, Azizzadenesseli et al. (2018) experimented with a Deep Learning extension RLSVI. They changed the network architecture exclude the last layer weights. optimized the hyper parameters and used double-DQN In contrary, we don't ton't change any- thing in the DQN agent. We use the representation learned by DQN to perform RISVI,, however, the network structure, loss and hyper-parameters are the same. Additionally, differently from our method, they don't I compensate for the changing representation and solve BLR problem with the same arbitrary prior every time.
Thompson Sampling in DRL:
3 PRELIMINARIES
We consider the standard RL settings (Sutton et al., 1998), in which an environment with discrete time steps is modeled by a Markov Decision Process (MDP). An MDP is tuple < S, A, P.R. > where state space, A a finite action space. P S x + A(S), is a transition kernel, and R S A - IR reward function. At each step the agent receives an observation represents the current physical state of the system, takes an action at E A which is applied to the environment, receives a scalar reward environment transitions to. As mentioned above, the agent seeks an optimal policy n² :S - A(A), mapping an environment state to probabilities over the agent's executable actions. (0, 1) is the discount factor a scalar representing the trade-off between immediate and delayed reward. A brief survey of the DQN algorithm can be found in Appendix 1.
E S which
r(Sttar) and observes a new state 8141 which the
3.1 RANDOMIZED LEAST SQUARES VALUE ITERATION
The Randomized Least Squares Value Iteration (RLSVI) algorithm is a TS-inspired exploration strategy for Model-Free Reinforcement Learning. It combines TS-like exploration and linear function approximation, where the main novelty is in the manner in which it explores: Sam- pling falue-functions rather than sampling actions. The Q-function assumed to be in the form Q(s,a)= 6(s, a)" w. where ő(s, a) is hand-designed state-action representation. RLSVI oper- ates similar to other linear function algorithms and minimizes the Bellman equation by solving a regression problem Bayesian Linear Regression. BLR obtains posterior distribution over value- function instead of point estimates. To explore, RLSVI samples plausible value functions from the posterior distribution and acts the greedy action according to the sampled fuuuttonnnnion In the episodic settings where the representation is tabular, i.c., no generalization is needed, RLSVI guar- antees near-optimal expected episodic regret. Finally, the main benefit of this algorithm is that it
3

---

Under review as a conference paper at ICLR 2020
displays impressive results even when generalization is required despite the lack of theoretical guarantees. A pseudo-code can be found in Appendix 1.
4 THE DEEP RANDOMIZED LEAST SQUARES VALUE ITERATION ALGORITHM
In this paper, we propose to use RLSVI as the exploration mechanism for DQN. RLSVI capabilities enhanced by using state representation that is learned directly from the data by neural network rather than hand-designed one. As the neural network gradually improves its representation of the states, likelihood matching mechanism is applied transfer information from old new representations.
4.1 LEARNING REPRESENTATION
A DQN agent is trained in the standard fashion, i.e., the same architecture, hyper-paramenn and loss function as the original DQN. Two exceptions were made (1) The size of the last hidden layer reduced to be d 64. (2) The Experience Replay buffer is divided evenly between actions and transitions are stored in a round-robin fashion. I.e., whenever the buffer is full, a new transition Sty ae, Toy St+1 > is placed instead of the oldest transition with the same action ag.
4.2 EXPLORATION
Exploration is performed using RLSVI on top of the last hidden layer the target network. Given a state st, the activations of the last hidden layer of the target network applied to this state are denoted as ((x)) = Aattvvtoorttiivationns (Qr (st)). Several changes to the original RLSVI algorithm were made: First, rather than solving different regression problem for every time step, different regression problem is being solved for every action. As the last hidden layer's activations serves state representation, the representation is time-homogeneous and shared among actions. The regression targets y are DQN's targets which use the target network predictions. Another change that slightly different formulation of Bayesian Linear Regression than RLSVI is being used. Similar to RLSVI Gaussian form for the likelihood is assumed: Q(s, a) ~ N (ww oz)) however, like Riquelme et al. (2018) the noise parameter o² is formulated as random variable, which is distributed according to the Inverse-Gamma distribution. The prior for each regression problem is therefore in the form: p(w, 0²) = p(wlo (ulo"))(((") p(wlo²) ~ N (Ho, ""E)), ~ I IneGaammaa (o. bo). For this prior and the Gaussian likelihood Q(8, a) ~ N(w ((s), o²) it is known that the posterior distribution can be calculated analytically as follows:
Φ - ((R))))ddx Yn=(w .... )na) ER"
Σn (on oh + Eg )-')=1 In ( Y, + Eg po);
n
bn = bu + Y. + u5 En 140 - 1 ",
0 = au 2
Formulating x² as a random variable allows adaptive exploration where the adaptation is derived directly from the observed data. Lastly, while RLSVI's choice for the prior's parameters is somewhat arbitrary, in our algorithm the prior has a central role which we'll lll discuss further on.
Since RLSVI requires fixed representation and the target network's weights are fixed, we use the last layer activations of the target network, denoted o(*), as state-repressntation. Every Jurget training time steps, the target network is updated with the weights of the Q Qenetwork. In these tagget time steps the Q-network is changing due to the optimization performed by the DQN algorithm. Since the representation changing, the posterior distribution that was approximated in the old representation can't be used. A posterior distribution based on the new representation needs to be approximated. Therefore, whenever the target network changes, new Bayesian linear regression problems are being solved using NBLR samples from the ER buffer. Since the ER buffer is finite, some experience-tuples were used to approximate the posterior the old representation and are no longer available. Ignoring this lost experience can and will lead to degradation in performance derived by *Catastrophic Forgetting' (Kirkpatrick et al. 2017). To compensate for the changing representation and the loss of old experience, follow (Zahavy & Mannor 2019) and match the
4

---

Under review as a conference paper at ICLR 2020
likelihood of the Q-function in the old and representation. This approach assumes that the important information from old experiences is coded the state representation.
Algorithm Deep RLSVI
Input: so Initial state, (s, a), Quirr (s, a). ER buffer,
Prior: 0g InvGamma (a,,0 0a,0), p(wa,oloo) Nua, La,,))
Define: ((s;) t- DosillayyrActivatinnnuure for t = 0, 1... do
(5() LastLayerActivationn
if mod ssampe then
for a = 0,... |Ab .,, |J| do
Sample ob. ~ InvGamma(aur bo) Sample Wa, ~ N(aa 82 La.
end for end if
Sample ju 1- E
Act ar E arg max,, W. ai ((5))
Observe 8t41, Tz. Store Transition St, des St41, Train DQN using sampled mini-batch
if t mod Terget for = 0, |A| do
then
Construct Priors Ho, E. by likelihood matching (Equation 2
Sample NBLR transitions <. 8s. 81+1, from ER buffer
Solve Bayesian Linear Regression (Equation]) M
end for Quarget (s, a) + (s, a)
end if end for
4.3 CONSTRUCTING PRIORS BY LIKELIHOOD MATCHING
Recall that the likelihood of the Q function (> Nww (()), our best es- timate for this likelihood is to plug-in the posterior approximation for wa: ((s,a) ~ (w- pi o² ( (s)E{((s)) The likelihood for the new representation, v5(s), in the same form: ass.a) ~ (wT 12 0² 2TT (s) (b)).. Since the likelihood is Gaussian, to compensate for the changing representation,
will find moments that match the likelihood of the Q-function in the new representation to the old one and use them for our Gaussian prior belief.
Expectation prior: As DQN is trained to predict the Q-function, given the new last layer activations tb a good prior for No the new representation will be the last layer weights the DQN (Levine) al. 2017).
Covariance prior: We use NSDP samples from the experience replay buffer. We evalu- ate both old and new representation {d(s;), (ss)), Nuv Our goal is to find solution E that will match the covariance of the likelihood in the new representation to the old one: (*:) 11)7)yy "i (s;) ((x:) (Ms))T<6(e)) (s)().) Using the eyclic property the trace, this equivalent to finding Trace(((s))((())) Eg S,, where S; = d(x)) (1s))"(00(a) (s;()) = Trace( (o(s,)) (()))))))))))))))))))))))))))))) We denote V, (bs))((s)))) E pdxd Adding the constraint that M should be Positive-Semil Definite as it is covariance matrix, we end up with the following Semi-Definin Program (SDP) (Vanden- berghe & Boyd 1996):
m
Trace V S s.t. Σy
(2)
In practice, solve this SDP by using CVXPY DDamond & Boyd 2016
5

---

Under review as a conference paper at ICLR 2020
4.4 REDUCING COMPUTATION COMPLEXITY
Approximate Sampling: To perform Thompson Sampling one needs to sample the posterior dis- tribution before every decision. This, regrettably, is computationally expensive and will slow down training significantly. To speed up learning, we sample weights for every action [ W every Sammle time steps. Then, every step we sample an index ig 1.... for every action, which is computationally cheap, and act greedy accordingly: a, = arg max, 2 a,,. ((s.).
Solving the SDP: Another bottleneck our algorithm faces is solving the SDP. We refer the reader to Vandenherghe & Boyd 1996) for an excellent survey on the complexity of solving SDPs. As the running time of an SDP solver mainly depends on the dimension of the representation d, the number of samples being used NSDP and the desired accuracy e, we chose the last hidden layer size to be 64, used NSDP = 600 for every SDP and set = le - 5. The running time for solving a single SDP took us 10-50 seconds using Intel's Xeon CPU E5-2686 v4 2.30 GHz.
5 EXPERIMENTS
We conduct a series of experiments that highlight the different aspects of our method. We begin with a qualitative evaluation of our algorithm simple toy environment, then, move report quantitative results on 5 different Atari games in the ALE.
r=0
r=0
r=
n-1
Figure 1: The Augmented Chain MDP
5.1 THE AUGMENTED CHAIN ENVIRONMENT
The chain environment includes chain of states S = 1, In each step, the agent can transition left or right. This standard-settings is augmented with additional k actions which transitions the agent to the same state (self-loop). We name this variation "The Augmented Chain Environment". All states have zero rewards except for the far-right n-state which gives reward of Each episode is of length H n 1, and the agent will begin each episode state The raw rettetttprsnnnntooon is one-hot vector. The Q-network is an MLP with 2 hidden layers. Results are averaged across different runs. We report the cumulative episodic regret: Regret(T)) =
Setup:
o - "hT Tt,h). Here T' is the number of played episodes, vū (so) is the return of the optimal policy, and Tr.h is the reward the agent received in episode at time step h. An illustration for the augmented chain environment can be found in figure [ The hyper- parameters that are being used the following experiments can be found Appendix 2.
5.1.1 EPSILON-GREEED
We compared our algorithm to standard DQN where e-greedy serves as the exploration strategy. We experimented with various values, however, as the results for different values were similar, display the result for single e value (Figure 2 (a)). We can see that e-greedy (red) achieves linear regret in T which is the lower bound for this type of problems, while algorithm (blue) achieves much lower regret. These results demonstrate that e-greedy can highly inefficient even very simple scenarios.

---

Under review as a conference paper at ICLR 2020
e-greedy fails in simple MDP
Acapcive vs. Constant noise parameter o
2000
180
episodes
80:0
8:009
2000
2803
4000
opisodes
4003
2003
(a)
(b)
Effect the likelihoad matching mechanism
Effect of buffer size an catastrophic forgetting
Dibon oud dlt rgpart
2200
683
1.00
2002
3300 22:00
00.30 10000
3005
10000
1003
eptsodes
episodes
(c)
(d)
Figure 2: Experimental results in the "Augmented Chain Environment". (a) Comparison of e-greedy exploration with RLSVI exploration. (b) Effect of modeling the noise parameter as a random vari- able in comparison to different choices of constant value. (c) Effect of the likelihood matching mechanism. (d) Effect of the buffer size.
5.1.2 ADAPTIVE SIGMA
In this experiment, we compared our algorithm with variants that do not model a2 as a random variable. We experimented with various constant o² values. We can see that modeling o² as random variable (red) leads to lower regret compared to constant o² variants (Figure 2 (b)). Note that choosing small value for o² (blue) results near-deterministic posterior function. Therefore the results are very similar to the e-greedy variant. Intuitively, a deterministic posterior acts as O-greedy strategy. On the other hand, choosing high value for o² (purple) results noisy sampling of the posterior approximation, therefore we get a policy which is relatively random concluding in bad performance. Choosing o² with the appropriate size for the given MDP (green, black) results in better performance, indicated by the lower regret. However, o² is constant docsn't adapt. We can see that the regret at the beginning the learning is better even compared to the adaptive-version. However, as the uncertainty level decrease, the algorithm "over-explores" which results inferior regret compared to the adaptive version.
very
5.1.3 LIKELIHOOD MATCHING
We compared our method with a variant that matches only the expectation, similar to (Levine et al. 2017). and a variant that does not match the likelihood at all, i.e.. approximates the posterior with a fixed arbitrary prior. The version that does not match the likelihood at all is close to BDQN (Azizzadenesheli et al., 2018) and can be thought of as our implementation for it. Additionally, we report the results of variant of the algorithm where the ER buffer is not bounded this is possible due to the fact that the toy problem is very small and so choosing large enough buffer serves infinite. Results are shown in Figure 2 (c). The superiority of our method (black) over the one-moment method (red) and no-prior at all (blue) support our claim that constructing priors by likelihood matching reduces the forgetting phenomenon. Additionally, the fact that the unbounded memory algorithm (green) doesn't tt demonstrate any degradation in performance confirms that this phenomenon is caused since the ER buffer is bounded.

---

Under review as a conference paper at ICLR 2020
Figure 3: Learning curves of DQN(blue), DRLSVI(red), Rainbow(green) for the first 10M time steps, for 5 different Atari games
5.1.4 BUFFER SIZB
The previous experiment may suggest that catastrophic forgetting in DRLSVI can be avoided by simply increasing the buffer size. In the following experiment, We examine the simple Chain envi- ronment (no self-loop actions; & = 0), with the following modification: we replaced the meaning of the actions in half of the states, i.e., to move right in the odd states, the agent needs to take the opposite action from the even states. We compare our algorithm with variants that do not match the likelihood with different buffer sizes. Figure (c) shows the performance of each of the algorithms in this setup. We can see that our algorithm (blue) doesn't t suffer from degradation of performance. The other algorithms, that don't match the likelihood, all suffer from degradation, where the only difference is the time in which the degradation starts. These results demonstrate that without the likelihood matching mechanism, catastrophic forgetting will occur regardless of the buffer size. is interesting to observe how catastrophic forgetting happens: When the buffer reaches point where it doesn't It contain experience of acting the non-optimal actions, quick degradation occurs. Then, the algorithm initially succeeds to re-learn the optimal policy and the regret saturates. This phenomenon is getting increasingly aggravated until the regret becomes linear. These chain of events occurred in all the experiments without likelihood matching regardless of the buffer size.
5.2 THE ARCADE LEARNING ENVIRONMENT
We report the performance of our algorithm across 5 different Atari games. We trained our algo- rithm for 10 million time steps and followed the standard evaluation: Every 250k training time steps we evaluated the model for 125k time steps. Reported measurements are the average episode return during evaluation. For evaluation, we used the learned Q-network with e-greedy policy (c = 0.001), results are averaged across 5 different runs. We use the original DQN's Sypee--prrmeters. Hyper- parameters that are only relevant for our method are summarised Appendix For comparison, we used the publically available learning curves for DON and Rainbow from the Dopamine frame- work (Castro et al.) 2018). Rainbow (Hessel et al. 2018) is a complex agent comprised of multiple additions to the original DQN algorithm. The averaged scores for the three methods are presented in Figure 3. The evaluation suggests that our method explores in much faster rate than DQN, and competitive with the Rainbow algorithm that combines multiple improvements to the DQN.
Note: Azizzadenesheli et al. (2018) didn't 't supply standard evaluation metrics and reported results for a single only. Additionally, they change the architecture of the Q-network exclude last layer weights, so a direct comparison to our method is not feasible. We, therefore, didn't 't compare our results with theirs.
DISCUSSION
Deep Learning adaptation to RLSVI was presented which learn the state representation directly from the data. We demonstrated the different properties of our method in experiments and showed the promise of our method. We hope to further reduce the complexity and running time of our algorithm in future work.
In the publicly available results the authors use different set of hyper- paraaeearaeeters than the original paper. We use the original paper's paraeepas.meters. Notice that the results for DQN are generally the same for the new of parameeer,,,,rs,, however, they may vary for specific game
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armes bandit prob- lem. In Conference on Learning Theory, pp. 1-39, 2012.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff'. In International Conference on Machine Learning, pp. 127-135, 2013.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqu: Variance reduction and stabilization for deep reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume 70, pp. 176-185. jmlr.org. 2017.
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning. 47(2-3):2352255 2002.
Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep q-networks. In ITA. IEEE, 2018
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Mare G. Bellemare. Dopamine: A Research Framework for Deep Reinforcement Learning. 2018. URL http:
T/arxiv.org/abs/// 06110
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in Neural Information Processing Systems, pp.
2011.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: /706. 10295, 2017.
Matteo Hessel, Joseph Modayil, et al. Rainbow: Combining improvements in deep reinforcement learning. AAAI, 2018
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska Barwinska, et al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13)3521-3526 2017.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of machine learning research, 4(Dec):1107-11493 2003.
Nir Levine, Tom Zahavy, et al. Shallow updates for deep reinforcement learning. In NIPS, 2017.
Long-Ji Lin. Reinforcement learning for robots using neural networks. Technical report, 1993.
Volodymyr Mnih, Koray Kavukcuoglu, et al. Human-level control through deep reinforcement learning. Nature, 518, 2015.
Brendan O' O'Donoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. arXiv preprint arXiv:/709.005: 2017.
Ian Osband and Benjamin Van Roy. Why posterior sampling better than optimism for reinforce- ment learning? In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2701-2710, jmlr.org 2017.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pp. 3003-3011, 2013.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. ICML, 2016.
Ian Osband, Daniel Russo, Zheng Wen, and Benjamin Van Roy. Deep exploration via randomized value functions. arXiv preprint arXiv: arXiv:1733.00 1003.073000 2017.

---

Under review as a conference paper at ICLR 2020
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, pp. 8626 8626-8638, 2018.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marein Andrychowicz. Parameter space noise for exploration. arXiv preprint
2017.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown. In JCML, 2018.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay, arXiv preprint orXiv:/5/1.05530 .05952, 2015.
Steven L. Scott. A modern bayesian look at the multi-armed bandit. Applied Stochastic Models in Business and Industry, 26(6):639-658. 2010.
Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pp- 943-950, 2000.
Richard Sutton, Andrew G Barto, et Introduction to reinforcement learning, volume 135, MIT press Cambridge, 1998.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25, 1933.
John N Tsitsiklis and Benjamin Van Roy, Analysis of camporal-diffferent learning with function approximation. In Advances Neural Information Processing Systems, pp. 1075-1081, 1997.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-
learning. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review, 38(1):49-995 1996.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Marc Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint arXiv:1511.065:: 2015.
Jeremy Wyatt. Exploration and inference in learning from reinforcement. 1998.
Tom Zahavy and Shie Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting 2019.
through likelihood matching. arXiv preprint
10

---

Under review as a conference paper at ICLR 2020
APPENDIX 1: ADDITIONAL PRELIMINARIES
DEEP Q-NETWORKS
The Deep Q-Networks (DQN) algorithm was the first algorithm that successfully combined Deep Learning architectures with Reinforcement Learning algorithms. It operates in the standard RI. set- ting (Sutton et al. 1998) where the state space high dimensional. It approximates the optimal Q-function using Convolutional Neural Network (CNN). The algorithm maintains two DNNs, the Q-network with weights and the target network with weights fugget- The Q-Network gets state input and produce |A| outputs, each representing the Q-value of different tion a, (8,, a). The target network is an older version of the Q-network with fixed weights. The target network is used constructs the targets y that the Q-network is trained to predict. The targets y are based on the Bellman equation. The algorithm uses Stochastic Gradient Descent (SGD) update the network's weights, by minimizing the mean squared error of the Bellman equation defined as BlllQe(sr, az) - Mr 1l2. where the target = rN if st+1 is terminal, otherwise Y1 = Ft + y max,' Qoagy ($t+1, a²). The weights of the target network are set to 0 every fixed num- ber of time steps, Target The tuples < St rt, 8t+1 that are used to optimize the network's weights are first collected into an Experience Replay (ER) buffer (Lin 1993). When performing an optimization step, mini-batch of samples are randomly selected from the buffer and are used to calculate the gradients. DQN is an off-policy algorithm which allows the agent to learn from experience collected by other means rather than its own experience. To explore the environment applies the e-greedy strategy, i.e., with probability it takes random action and with probability 1 1-e takes the greedy action with respect to the current estimate of Q
Algorithm 2 Deep Q-Networks
Input: (s, a), Qutorget (s, a), c, buffer So = EnvironmentRese()
for t = 0, 1.... do
Sample
(0, 1)
if e < e then at U1L, AA}
else
arg max, Q6 (s.
end if
Act az
Observe 8141, T2, de (de = 1 if s, is terminal) Store Transition St, de, S141, Te, d if d then
S EnvironmentReset(
end if
Sample n transitions < 8i, at, 8i+1, ri, d, > from ER buffer (s)+1,
y1 - Q(, a.) - 3:
T; (1 d (1
if (t mod Tearget) = then
Qutarget (s. a) (s)
end if
end for
11

---

Under review as a conference paper at ICLR 2020
PSEUDO CODE FOR RLSVI
Algorithm Randomized Least Squares Value Iteration
Input: Feature Extractors: Po: PH-1,
Parameters: À >> 0, > 0
Output: 00 ..... 01
Sample 80 .... 8 NO0, 0² 1)
for 0, 1... do
Observe 8g
for - 1,... 1,0 do
Sample an E arg max. (o) f (sth: a))
Act aik
Observe 8141, end for
Observe
for
1,0 do Generate regression problem A E Ri D 4 (Spn, aos)
A
2h 11
Fih + max, (+++100 (.4+1)()
for h < -1 h = H -1 for
6. <-
Tih + TiA+1
Bayesian Linear Regression
On ( AT + AT) ATb
M1,h + A + A
Sample Pth (0 21,b,
end for end for
12

---

Under review as a conference paper at ICLR 2020
APPENDIX 2: HYPER-PARAMETERS
AUGMENTED CHAIN EXPERIMENTS
Hyper-Parameter
Value
mini-batch size
32
experience replay bufter size
1000
experience replay buffer size for oracle baseline
1000000
target network update frequency
100
discount factor
0.99
learning starts
0
d - representation dimension
20
Tsampl posterior sample frequency
10
J number of models
NBLR Bayesian linear regression transitions
1000/ a
NSDP likelihood matching transitions
30
n chain states
10
k self loop actions
4
ALE EXPERIMENTS
Hyper-Parameter
Value
d representation dimension
64
Tsampl posterior sample frequency
1000
J number of models
5
NBlR Bayesian linear regression transitions
1000000/ a
NspP likelihood matching transitions
600
13


Reviews:
[{"review_id": "ryeGcQa3FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a deep learning-based adaptation for the RLVSI algorithm, where the agent uses the representation learned by the deep neural network-based RL agent (DQN). They use the last layer of DQN as a state representation for RLSVI.  In order to work with the changing representations of the deep agent, they propose a likelihood matching mechanism. The approach is applied to two tasks: a) A toy modified n-chain experiment and b) set of 5 Atari games. They show that their method outperforms the DQN with naive exploration. \n\n\nThis paper should be rejected because of the following reasons: \n\n1) Lacking comparisons to Azizzadenesheli et al. (2018)\nThe authors acknowledge that their work resembles a lot to Azizzadenesheli et al. (2018), who also provide a deep extension of RLVSI. However, they do not provide any baselines or comparisons with this approach.  To me, this work is one particular form of the work by Azizzadenesheli et al. (2018), where instead of using Bayesian linear regression in the last layer, a specific parameterization of the prior and posterior families is used, that allows an analytical solution for the update (Eq 1).  They claim that they have lesser hyper-parameters but at the same time they introduce additional ones: N_{BLR}, T^{Sample}, etc. and it is not clear to me that if the new set of hyper-parameters are easier to tune than compared to Azizzadenesheli et al. (2018). They claim that it is not possible to compare with Azizzadenesheli et al. (2018)  but their code is available publicly.\n\n2) Lacking comparisons in general \nThe results on Atari are compared with vanilla-DQN (with epsilon greedy). Instead of comparing the method on other works that also extend the RLVSI to deep nets (eg: [1], [2], [3], etc) they compare it with RAINBOW, a method that is not based RLVSI.  \n\n3) Unexplained design choices \nA lot of design choices of the final algorithm are not explained, which makes me skeptical about the work. The main ones in question being:\nThe unique nature of the replay buffer: It is not clear why the experience replay buffer has the specific form, where each action has fixed memory, and a round-robin scheme is used to update the buffer. \n) Non-standard experiments\nIt is not clear why the authors did not use the standard n-chain task but rather used the modified version.  Also, why did the authors only selected the set of only those 5 specific games is not addressed.\n\n\nSuggestions \nI will recommend the authors to address why their algorithm should be used instead of the others I have mentioned above. They can do it either by providing any theoretical or empirical arguments. They also should use a few of the standard experiments so that it gives the reader more insight into where their algorithms excel. \n\n\nThings to improve the paper that did not impact the score:\n\nFigure 3 is too small to read. \nThe section on Likelihood matching is not clear: in motivation and impact. \n\n\nReferences: \n\n[1] ] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances In Neural Information Processing Systems 29, pages 4026–4034, 2016.\n\n[2] Ahmed Touati, Harsh Satija, Joshua Romoff, Joelle Pineau, and Pascal Vincent. Randomized value functions via multiplicative normalizing flows. arXiv preprint arXiv:1806.02315, 2018.\n\n[3] Osband, Ian, John Aslanides, and Albin Cassirer. \"Randomized prior functions for deep reinforcement learning.\" Advances in Neural Information Processing Systems. 2018.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SkeoYT8pKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to extend the popular linear-control algorithm, RLSVI, to utilize learned representations. This is done by adapting a work from bandit literature that utilizes BLR with representations that are learned via a DNN. The proposed solution is then compared to DQN with fixed epsilon as the exploration strategy in a chain MDP, and to the Rainbow agent and DQN in 5 selected Atari games to show sample-efficiency improvements.\n\nThe idea presented by the work is interesting, and utilizing a complete Bayesian Linear Regression framework (variable variance, as opposed to fixed variance in the prior) does sound appealing in terms of adaptability - as it is what the authors argue for, as being key to their proposal. But the work in the paper is not in an acceptable form due to the following key reasons: (1) the presentation of the ideas and the algorithm, \"despite the lack of theoretical guarantees\" is hard to understand, (2) the DQN baseline compared to (definitely in the Augmented Chain Environment, and possibly in the Atari games), are based on a fixed epsilon exploration strategy whereas DQN as proposed uses a epsilon-annealing strategy for exploration, (3) the baselines compared to are not comprehensive, (4) generally the paper is rather unpolished.\n\n\nFollowing are main points of feedback, regarding which I would like to know the authors opinions/responses in the rebuttal if possible. After that, are some concrete questions to clarify the contents of the paper.\n\nFeedback:\n(1) the linear contextual bandit work the paper is built on is currently under review at ICLR 2020. While this should not be the reason for rejection, the idea of likelihood matching as motivated from that bandit work does not simply transfer to the RL case. For instance, based on the pseudocode in the paper (and the provided explanation), after likelihood matching is done, the new BLR updates still seem to use the old representations and targets (as the target net update is done after the loop). This is possibly a typo, or something deeper is left unexplained here.\n(2) While it is true that the BDQN work does not utilize the last layer of their weights, and is built on the DDQN algorithm, I think they still are a reasonable baseline as the key idea distinguishing the two is variable variance prior vs. a fixed variance prior. While I understand having all the baseline experiments from the exploration in deep RL literature is hard as it is quite vast - Bootstrap DQN, UBE, Bootstrap Prior - I think the closest baseline has to be BDQN to your proposal and therefore is a natural competitor.\n(3) DDQN has been shown to be reducing the overestimation bias prevalent in DQN and therefore was the framework BDQN was built on. Why do you choose to use DQN instead of DDQN? A discussion regarding this seems a natural part of the paper.\n(4) Are the benefits of adaptive sigma present if the base algorithm is changed to DDQN? I think this is an important point of discussion/analysis. It does not have to outperform DDQN, but even a comparative study empirically would be an insightful and comprehensive contribution.\n(5) I assume that the likelihood utilizes the inverse of the covariance as opposed to the covariance -- something that seems amiss in the current write-up.\n(6) Isn't S_i in Section 4.3 already a scalar? Why is there a trace of a scalar?\n(7) Section 5.1.3 -- the version that does not match likelihood is not BDQN as it is built on DDQN -- presumable significant regret differences.\n\nQuestions:\n(1) DQN as proposed is with annealed e-greedy. Are the experiments in Augmented Chain Environment utilizing this or a fixed e-greedy strategy?\n(2) What exactly is the connection between catastrophic forgetting and likelihood matching in the policy improvement context? Why should an improved policy match the likelihood of features as learned by an older policy?\n(3) Why choose to sample a set of value functions instead of sampling every timestep? Only because sampling is expensive or does it provide any stability?\n(4) Why did you pick these 5 Atari games?\n\n\nGiven the algorithm is a particular design choice, and the argument for its utility is empirical, I definitely think the design choice needs to be discussed more thoroughly, and the manuscript currently does not do that. While empirical experiments in the Atari suite can be hard ask depending on the availability of computational resources, I think the work algorithmic choices made here are left undiscussed and the empirical results aren't really convincing. Further, the presentation is rather imprecise and error-ridden. Therefore, I do not think the work can be accepted.\n\nThere are many imprecise statements and typos in the paper, which are listed here to aid the future versions:\n(1) Please review your psuedocode based on comment (1) in Feedback.\n(2) The content in the Introduction does not make a note of many algorithms proposed for exploration in Deep RL -- UBE [1], Bootstrap DQN [2], Randomized prior for Bootstrap DQN [3], Parameter noise[4].\n(3) Section 2, para 2 -- Recent work (Osband --> Recent works (Osband\n(4) Section 2, para 3 -- acts greedy --> acts greedily\n(5) Section 3, para 1 -- gamma in (0,1) --> [0,1]\n(6) Section 3, para 1 -- survey --> review\n(7) Section 3.1, para 1 -- acts the greedy action according to the --> acts greedily wrt\n(8) Section 4.1, buffer consists of gamma/termination flag\n(9) Section 4.2, para 1 -- First, rather than solving .. -- so did RLSVI. I guess you mean the regression problem is not solved every tilmestep.\n(10) Section 4.2 last sentence -- please expand why that assumption is good?\n(11) opening inverted commas everywhere.\n(12) Section 5.1.4, last sentence -- grammar.\n(13) Footnote 1 and content in Section 5.2 \"we used publicly available learning curves\" are contradictory.\n\n\n[1] O'Donoghue, Brendan, et al. \"The uncertainty bellman equation and exploration.\" arXiv preprint arXiv:1709.05380 (2017).\n[2] Osband, Ian, et al. \"Deep exploration via bootstrapped DQN.\" Advances in neural information processing systems. 2016.\n[3] Osband, Ian, John Aslanides, and Albin Cassirer. \"Randomized prior functions for deep reinforcement learning.\" Advances in Neural Information Processing Systems. 2018.\n[4] Plappert, Matthias, et al. \"Parameter space noise for exploration.\" arXiv preprint arXiv:1706.01905 (2017).\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gIAox8tH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Deep Randomized Least Squares Value Iteration\n=========================================================\n\nThis paper proposes a method for exploration via randomized value functions in Deep RL.\nThe algorithm performs a standard DQN update, but then acts according to an exploration policy sampled from a posterior approximation based on a last layer linear rule.\nThe authors show that this algorithm can perform well on a toy domain designed to require efficient exploration, together with some results on Atari games.\n\n\nThere are several things to like about this paper:\n- The problem of efficient exploration in Deep RL is a pressing one, and there is no clearly effective method out there widely used.\n- The proposed algorithm is interesting, and appears to have some reasonable properties. One nice thing is that it requires only relatively minor changes to the DQN algorithm.\n- The general flow of the paper and structured progression is nice.\n- The algorithm generally appears to bring superior exploration and outperform epsilon-greedy baseline.\n\n\nHowever, there are some other places the work could be improved:\n- I think that the name \"Deep RLSVI\" is a little imprecise... actually RLSVI could already be a \"deep\" algorithm as defined by the JMLR paper: http://jmlr.org/papers/volume20/18-339/18-339.pdf (Algorithm 4). I see that you mean this as an extension to the linear case for RLSVI... but I do think it would be better to call it something more explicit like \"Last-layer RLSVI for DQN\".\n- Related to the above, the comparison to other similar methods for exploration via \"randomized value functions\" is not very comprehensive. I'm not sure what the pros/cons are of this method versus BootDQN or the very similar work from Azizzadenesheli?\n- It would be good to compare these methods more explicitly, particularly on the domains designed specifically for testing exploration. To this end, I might suggest bsuite https://github.com/deepmind/bsuite and particularly the \"deep sea\" domains?\n- Something feels a little off about the Atari results, particularly the curves for \"rainbow\"... these appear to be inconsistent with published results (look at Breakout).\n\nOverall I think there is interesting material here, and I'd like to see more.\nHowever, I do have some concerns about the treatment/comparison to related work and I think without this it's not ready for publication.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper combines DQN and Randomized value functions for exploration. 

All the reviewers agreed the paper is not yet ready for publication. The experiments lack appropriate baselines and thus it is unclear how this new approach improves exploration in Deep RL. The reviewers also found some of the algorithmic design decisions unintuitive and unexplained. The authors main response was the objective was to improve and compare against vanilla DQN. This could be a valid goal, but it requires clear motivation (perhaps the focus is on simply algorithms that are commonly used in applications or something). Even then comparisons with other methods would be of interest to quantify how much the base algorithm is improved, and to justify empirically all the design decisions that went into building such an improvement (performance vs complexity of implementation etc).

The reviewers gave nice suggestions for improvements.  This is a good area of study: keep going!
Decision: Reject