Year: 2019

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.

heading: 1 INTRODUCTION
text: In Reinforcement Learning (RL), an agent seeks to maximize the cumulative rewards obtained from interactions with an unknown environment (Sutton et al., 1998). Since the agent can learn only by its interactions with the environment, it faces the exploration-exploitation 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 a table containing a value for each state-action pair can be stored in the computer’s memory. For more general settings, where generalization is required, a common practice is to use hand-designed state representation (or state-action), upon which a function approximation can be learned to represent the value for each state and action. RL algorithms based on 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. Qfunction, will be a linear combination of the state representation. This is, of course, a hard constraint as the representation is 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.
The DQN algorithm (Mnih et al., 2015) has changed RL. Using Deep Neural Networks (DNN) as function approximators, the DQN algorithm enabled the learning of policies directly from raw highdimensional data and led to unprecedented achievements over a wide variety of domains (Mnih et al., 2015). Over the years, many improvements to DQN were presented, suggesting more fitting network architectures (Wang et al., 2015), reducing overestimation (Van Hasselt et al., 2016; Anschel et al., 2017) or improving its data efficiency (Schaul et al., 2015). Despite its great success, DQN uses the overly simple -greedy strategy for exploration. This strategy is one of the simplest exploration
strategies that currently exist. The agent takes random action with probability and takes the optimal action according to its current belief with probability 1− . This strategy is commonly used despite its simplicity and proven inefficiency (Osband et al., 2016). The main shortcoming of -greedy and similar strategies derives from the fact that they do not use observed data to improve exploration. To explore, it takes a completely random action, regardless of the experience obtained by the agent.
Thompson Sampling (TS) (Thompson, 1933), is one of the oldest heuristics to address the ’exploration/exploitation’ trade-off in sequential decision-making problems. Its variations were proposed in RL (Wyatt, 1998; Strens, 2000) and various bandits settings (Chapelle & Li, 2011; Scott, 2010). For Multi-Armed Bandit (MAB) problems, TS is very effective both in theory (Agrawal & Goyal, 2012; 2013) and practice (Chapelle & Li, 2011). Intuitively, TS randomly takes actions according to the probability it believes to be optimal. In practice, a prior distribution is assumed over the model’s parameters p(w), and a posterior distribution 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 linear function approximation and is inspired by Thompson Sampling. It explores by sampling plausible Q-functions from uncertainty sets and selecting the action that optimizes the sampled models. This algorithm was proven to be efficient in tabular settings, with a 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, as it assumes a 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 explores by using the last layer’s activations of DQN as state representation for RLSVI. To compensate 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 regarding 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, we compare our algorithm to the DQN and Rainbow algorithms on several Atari benchmarks. We show that it outperforms DQN both in learning speed and performance.

heading: 2 RELATED WORK
text: Thompson Sampling in Multi-Armed Bandit problems: Thompson Sampling (TS) (Thompson, 1933), is one of the oldest heuristics to address the ’exploration/exploitation’ trade-off in sequential decision-making problems. Chapelle & Li (2011) sparked much of the interest in Thompson Sampling in recent years. They rewrote the TS algorithm for Bernoulli bandit and showed impressive 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 exploration and exploitation in sequential decision-making problems than other popular alternatives like the Upper Confidence Bound algorithm (Auer et al., 2002). Agrawal & Goyal (2013) suggested a Thompson Sampling algorithm for the linear contextual bandit problem and supplied a high-probability regret bound for it. They use Bayesian Linear Regression (BLR) with Gaussian likelihood and Gaussian prior to design their version of Thompson Sampling algorithm. Riquelme et al. (2018) suggested performing a BLR on top of the representation of the last layer of a neural network. The predicted value vi for each action ai is given by vi = βTi zx, where zx is the output of the last hidden layer of the network for context x. While linear methods directly try to regress values v on x, they independently trained a DNN to learn a representation z, and then used a BLR to regress v on z, obtaining uncertainty estimates on the β’s, and making decisions accordingly via Thompson Sampling. Moreover, the network is only being used to find good representation – z. Since training the network and updating the BLR can be done independently, they train the network for a fixed number of iterations, then, perform a forward pass on all the training data to obtain the new zx, 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
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.
Thompson Sampling in RL: In the Reinforcement Learning settings, Strens (2000) suggested a 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; Osband & Van Roy, 2017) have shown a theoretical analysis of PSRL that guarantees strong expected performance over a wide range of environments. The main problem with PSRL, like all modelbased approaches, is that it may be applied to relatively small environments. The Randomized Least Squares Value Iteration (RLSVI) algorithm is an application of Thompson Sampling to Model-Free Reinforcement Learning. It explores by sampling plausible Q-functions from uncertainty sets and selecting the action that optimizes the sampled models.
Thompson Sampling in DRL: 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 a different prior. Fortunato et al. (2017) and Plappert et al. (2017) investigate a similar idea and propose to adaptively perturb the parameterspace, which can also be thought of as tracking approximate posterior over the network’s parameters. O’Donoghue et al. (2017) proposed TS in combination with uncertainty Bellman equation, which connects the uncertainty at any time-step to the expected uncertainties at subsequent timesteps. Recently and most similar to our work, Azizzadenesheli et al. (2018) experimented with a Deep Learning extension to RLSVI. They changed the network architecture to exclude the last layer weights, optimized the hyper parameters and used double-DQN. In contrary, we don’t change anything in the DQN agent. We use the representation learned by DQN to perform RLSVI, however, the network structure, loss and hyper-parameters are the same. Additionally, differently from our method, they don’t compensate for the changing representation and solve BLR problem with the same arbitrary prior every time.

heading: 3 PRELIMINARIES
text: 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 a tuple < S,A, P,R, γ >, where S is a state space, A a finite action space, P : S × A −→ ∆(S), is a transition kernel, and R : S × A −→ R a reward function. At each step the agent receives an observation st ∈ S which represents the current physical state of the system, takes an action at ∈ A which is applied to the environment, receives a scalar reward rt = r(st, at), and observes a new state st+1 which the environment transitions to. As mentioned above, the agent seeks an optimal policy π∗ : S −→ ∆(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.

heading: 3.1 RANDOMIZED LEAST SQUARES VALUE ITERATION
text: 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: Sampling value-functions rather than sampling actions. The Q-function is assumed to be in the form Q(s, a) = φ(s, a)Tw, where φ(s, a) is a hand-designed state-action representation. RLSVI operates similar to other linear function algorithms and minimizes the Bellman equation by solving a regression problem – Bayesian Linear Regression. BLR obtains a posterior distribution over valuefunction instead of point estimates. To explore, RLSVI samples plausible value functions from the posterior distribution and acts the greedy action according to the sampled value-function. In the episodic settings where the representation is tabular, i.e., no generalization is needed, RLSVI guarantees near-optimal expected episodic regret. Finally, the main benefit of this algorithm is that it
displays impressive results even when generalization is required – despite the lack of theoretical guarantees. A pseudo-code can be found in Appendix 1.

heading: 4 THE DEEP RANDOMIZED LEAST SQUARES VALUE ITERATION ALGORITHM
text: In this paper, we propose to use RLSVI as the exploration mechanism for DQN. RLSVI capabilities are enhanced by using state representation that is learned directly from the data by a neural network rather than hand-designed one. As the neural network gradually improves its representation of the states, a likelihood matching mechanism is applied to transfer information from old to new representations.

heading: 4.1 LEARNING REPRESENTATION
text: A DQN agent is trained in the standard fashion, i.e., the same architecture, hyper-parameters and loss function as the original DQN. Two exceptions were made (1) The size of the last hidden layer is 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 < st, at, rt, st+1 > is placed instead of the oldest transition with the same action at.

heading: 4.2 EXPLORATION
text: Exploration is performed using RLSVI on top of the last hidden layer of 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 φ(st) = LastLayerActivations(Qθtarget(st)). Several changes to the original RLSVI algorithm were made: First, rather than solving different regression problem for every time step, a different regression problem is being solved for every action. As the last hidden layer’s activations serves as 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 is that a slightly different formulation of Bayesian Linear Regression than RLSVI is being used. Similar to RLSVI a Gaussian form for the likelihood is assumed: Q(s, a) ∼ N(wTa φ(s), σ2), however, like Riquelme et al. (2018) the noise parameter σ2 is formulated as a random variable, which is distributed according to the Inverse-Gamma distribution. The prior for each regression problem is therefore in the form: p(w, σ2) = p(w|σ2)p(σ2), p(w|σ2) ∼ N(µ0, σ2Σ0), p(σ2) ∼ InvGamma(a0, b0). For this prior and the Gaussian likelihood Q(s, a) ∼ N(wTa φ(s), σ2) it is known that the posterior distribution can be calculated analytically as follows:
φn={φ(s1), ..., φ(sn)}∈Rd×n, Yn=(y1, ..., yn)T ∈ Rn
Σn = (φnφ T n + Σ −1 0 ) −1, µn = Σn(φnYn + Σ −1 0 µ0),
an = a0 + n
2 , bn = b0 +
1 2 (Y Tn Yn + µ T 0 Σ −1 0 µ0 − µTnΣ−1n µn),
(1)
Formulating σ2 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 discuss further on. Since RLSVI requires a fixed representation and the target network’s weights are fixed, we use the last layer activations of the target network, denoted φ(s), as state-representation. Every T target training time steps, the target network is updated with the weights of the Q-network. In these T target time steps the Q-network is changing due to the optimization performed by the DQN algorithm. Since the representation is 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 in 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, we follow (Zahavy & Mannor, 2019) and match the
likelihood of the Q-function in the old and new representation. This approach assumes that the important information from old experiences is coded in the state representation.
Algorithm 1 Deep RLSVI
Input: s0 − Initial state, Qθ(s, a), Qθtarget(s, a), ER buffer, Prior: σ2a ∼ InvGamma(aa,0, ba,0), p(wa,0|σ2a) ∼ N(µa,0, σ2Σa,0) Define: φ(st)← LastLayerActivation(Qθtarget), ψ(st)← LastLayerActivation(Qθ) for t = 0, 1... do
if t mod Tsample then for a = 0, ..., |A|, j = 0, ..., |J | do
Sample σ̃2a,j ∼ InvGamma(âa, b̂a) Sample w̃a,j ∼ N(µ̂a, σ̃2a,jΣ̂a)
end for end if Sample ja ∼ U{1, 2, ..., |J |}∀a ∈ A Act at ∈ arg maxα w̃Tα,jαφ(st) Observe st+1, rt, Store Transition < st, at, st+1, rt > Train DQN using sampled mini-batch if t mod Ttarget = 0 then
for a = 0, ..., |A| do Construct Priors µ0,Σ0 by likelihood matching (Equation 2) Sample NBLR transitions < si, a, si+1, ri > from ER buffer Solve Bayesian Linear Regression (Equation 1) end for Qθtarget(s, a)←− Qθ(s, a)
end if end for

heading: 4.3 CONSTRUCTING PRIORS BY LIKELIHOOD MATCHING
text: Recall that the likelihood of the Q function is Q(s, a) ∼ N(wTa φ(s), σ2), our best estimate for this likelihood is to plug-in the posterior approximation for wa: Q̂(s, a) ∼ (wTa µ φ n, σ
2φT (s)Σφnφ(s)). The likelihood for the new representation, ψ(s), is in the same form: Q̂(s, a) ∼ (wTa µψn , σ2ψT (s)Σψnψ(s)). Since the likelihood is Gaussian, to compensate for the changing representation, we 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 theQ-function, given the new last layer activations ψ, a good prior for µ0 in the new representation will be the last layer weights of the DQN (Levine et al., 2017).
Covariance prior: We use NSDP samples from the experience replay buffer. We evaluate both old and new representation {φ(si), ψ(si)}NSDPi=1 . Our goal is to find a solution Σ ψ 0 that will match the covariance of the likelihood in the new representation to the old one: ψ(si) TΣψ0ψ(si) = φ(si) TΣφnφ(si). Using the cyclic property of the trace, this is equivalent to finding Trace(ψ(si)ψ(si)TΣ ψ 0 ) = Si, where Si = φ(si) TΣφ0φ(si) = Trace(φ(si) TΣφ0φ(si)). We denote Ψi = ψ(si)ψ(si)T ∈ Rd×d. Adding the constraint that Σψ0 should be Positive-Semi-Definite as it is a covariance matrix, we end up with the following Semi-Definite Program (SDP) (Vandenberghe & Boyd, 1996):
min Σψ0 m∑ i=0 ||Trace(ΨiΣψ0 )− Si||2 s.t. Σ ψ 0 0 (2)
In practice, we solve this SDP by using CVXPY (Diamond & Boyd, 2016).

heading: 4.4 REDUCING COMPUTATION COMPLEXITY
text: Approximate Sampling: To perform Thompson Sampling one needs to sample the posterior distribution before every decision. This, regrettably, is computationally expensive and will slow down training significantly. To speed up learning, we sample j weights for every action {w̃i,1, ..., w̃i,j} every T Sample time steps. Then, every step we sample an index ia ∈ 1, .., j for every action, which is computationally cheap, and act greedy accordingly: at = arg maxα w̃Tα,iαφ(st).
Solving the SDP: Another bottleneck our algorithm faces is solving the SDP. We refer the reader to Vandenberghe & 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 , we chose the last hidden layer size to be d = 64, used NSDP = 600 for every SDP and set = 1e− 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.

heading: 5 EXPERIMENTS
text: We conduct a series of experiments that highlight the different aspects of our method. We begin with a qualitative evaluation of our algorithm on a simple toy environment, then, move to report quantitative results on 5 different Atari games in the ALE.

heading: 5.1 THE AUGMENTED CHAIN ENVIRONMENT
text: Setup: The chain environment includes a chain of states S = 1, ..., n. 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 a reward of 1. Each episode is of length H = n − 1, and the agent will begin each episode at state 1. The raw state-representation is a one-hot vector. The Q-network is an MLP with 2 hidden layers. Results are averaged across 5 different runs. We report the cumulative episodic regret: Regret(T ) =∑T t=0(v ∗ 0(s0) − ∑H h=0 rt,h). Here T is the number of played episodes, v ∗ 0(s0) is the return of the optimal policy, and rt,h is the reward the agent received in episode t at time step h. An illustration for the augmented chain environment can be found in figure 1. The hyper-parameters that are being used in the following experiments can be found in Appendix 2.

heading: 5.1.1 EPSILON-GREEDY
text: We compared our algorithm to standard DQN where -greedy serves as the exploration strategy. We experimented with various values, however, as the results for different values were similar, we display the result for a single value (Figure 2 (a)). We can see that -greedy (red) achieves a linear regret in T which is the lower bound for this type of problems, while our algorithm (blue) achieves much lower regret. These results demonstrate that -greedy can be highly inefficient even in very simple scenarios.

heading: 5.1.2 ADAPTIVE SIGMA
text: In this experiment, we compared our algorithm with variants that do not model σ2 as a random variable. We experimented with various constant σ2 values. We can see that modeling σ2 as a random variable (red) leads to lower regret compared to constant σ2 variants (Figure 2 (b)). Note that choosing a small value for σ2 (blue) results in near-deterministic posterior function. Therefore the results are very similar to the -greedy variant. Intuitively, a deterministic posterior acts as a 0-greedy strategy. On the other hand, choosing a high value for σ2 (purple) results in a very noisy sampling of the posterior approximation, therefore we get a policy which is relatively random concluding in a bad performance. Choosing σ2 with the appropriate size for the given MDP (green, black) results in better performance, as indicated by the lower regret. However, as σ2 is constant it doesn’t adapt. We can see that the regret at the beginning of the learning is better even compared to the adaptive-version. However, as the uncertainty level decrease, the algorithm ”over-explores” which results in inferior regret compared to the adaptive version.

heading: 5.1.3 LIKELIHOOD MATCHING
text: 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 a 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 as 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 demonstrate any degradation in performance confirms that this phenomenon is caused since the ER buffer is bounded.

heading: 5.1.4 BUFFER SIZE
text: 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 environment (no self-loop actions; k = 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 2 (c) shows the performance of each of the algorithms in this setup. We can see that our algorithm (blue) doesn’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. It is interesting to observe how catastrophic forgetting happens: When the buffer reaches a point where it doesn’t contain experience of acting the non-optimal actions, a 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.

heading: 5.2 THE ARCADE LEARNING ENVIRONMENT
text: We report the performance of our algorithm across 5 different Atari games. We trained our algorithm 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 -greedy policy ( = 0.001), results are averaged across 5 different runs. We use the original DQN’s hyper-parameters. Hyperparameters that are only relevant for our method are summarised in Appendix 2. For comparison, we used the publically available learning curves for DQN1 and Rainbow from the Dopamine framework (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 a much faster rate than DQN, and is competitive with the Rainbow algorithm that combines multiple improvements to the DQN.
Note: Azizzadenesheli et al. (2018) didn’t supply standard evaluation metrics and reported results for a single run only. Additionally, they change the architecture of the Q-network to exclude last layer weights, so a direct comparison to our method is not feasible. We, therefore, didn’t compare our results with theirs.

heading: 6 DISCUSSION
text: A 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.
1In the publicly available results the authors use a different set of hyper-parameters than the original paper. We use the original paper’s hyper-parameters. Notice that the results for DQN are generally the same for the new set of hyper-parameters, however, they may vary for a specific game

Review summaries:
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.

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.