Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matching
Authors: Tom Zahavy
Shie Mannor
Venue:  (2020)

Abstract: We study neural-linear bandits for solving problems where both exploration and representation learning play an important role. Neural-linear bandits leverage the representation power of deep neural networks and combine it with efficient exploration mechanisms, designed for linear contextual bandits, on top of the last hidden layer. Since the representation is being optimized during learning, information regarding exploration with "old" features is lost. Here, we propose the first limited memory neural-linear bandit that is resilient to this catastrophic forgetting phenomenon. We perform simulations on a variety of real-world problems, including regression, classification, and sentiment analysis, and observe that our algorithm achieves superior performance and shows resilience to catastrophic forgetting. 

Under review as a conference paper at ICLR 2020
NEURAL LINEAR BANDITS: OVERCOMING CATASTROPHIC THROUGH LIKELIHOOD MATCHING
FORGETTING
Anonymous authors Paper under double-blind review
ABSTRACT
We study neural-linear bandits for solving problems where both exploration and representation learning play an important role. Neural-linear bandits leverage the representation power of deep neural networks and combine it with efficient explo- ration mechanisms, designed for linear contextual bandits, on top of the last hidden layer. Since the representation is being optimized during learning. information regarding exploration with "old" features is lost. Here. we propose the first limited memory neural-linear bandit that is resilient to this catastrophic forgetting phe- nomenon. We perform simulations on a variety of real-world problems, including regression, classification, and sentiment analysis. and observe that our algorithm achieves superior performance and shows resilience to catastrophic forgetting.
INTRODUCTION
Deep neural networks (DNNs) can learn representations of data with multiple levels of abstraction and have dramatically improved the tfte-off-hhearr speech recognition, visual object recognition object detection and many other domains such as drug discovery and genomics (LeCun et al. 2015
Goodfellow et al. 2016). Using DNNs for function approximation in reinforcement learning (RL) enables the agent to generalize across states without domain representations from raw, nigh-dimensiooal inputs (Mnih al., 2015 Silver et al. 2016).
knowledge. and learn rich
Nevertheless, the question of how perform efficient exploration during the representation learning phase still an open problem. The e-greedy policy (Langford & Zhang, 2008) is simple to implement and widely used in practice (Mnih et al. 2015). However, it is statistically suboptimal. Optimism in the Face of Uncertainty (Abbasi- Yadkon et al. [2011] Auer 2002 OFU), and Thompson Sampling TTompson
1933 Agrawal & Goyal 2013 TS) use confidence sets to balance exploitation and exploration. For DNNs, such confidence sets may not be accurate enough allow efficient exploration. For example, using dropout as posterior approximation for exploration does not concentrate with observed data (Osband et al. 2018) and was shown empirically to be insufficient (Riquelme et al. 2018). Alternatively. pscudo-coure cocutss a generalization of the number of visits, were used as an exploration bonus (Bellemare et al. 2016 Pathak et al. 22177). Inspired by tabular RL, these ideas ignore the uncertainty in the value function approximation in each context. As result, they may lead to inefficient confidence sets (Osband et al. 2018).
Linear models, on the other hand, are considered more stable and provide accurate uncertainty estimates but require substantial feature engineering to achieve good results. Additionally, they are known to work in practice only with "medium-sized" inputs (with around 1, 000 features) due to numerical issues. A natural attempt at getting the best of both worlds is to learn a linear exploration policy on top of the last hidden layer of DNN, which we term the neural-linear approach. In RL, this approach was shown refine the performance of DONs (Levine et al.) (017) and improve exploration when combined with TS (Azizzadenesheli et al. 2018) and OFU (O Donoghuee et al. 2018, Zahavy et al. 2018a) For contextual bandits, Riquelme el al. 2018 showed that TS achieves superior performance multiple data sets.
A practical challenge for neural-lineal linear bandits is that the representation (the activations of the last hidden layer) change after every optimization step, while the features are assumed be fixed over time when used by linear contextual bandits. RRquelmee et al. (2018) tackled this problem by storing the entire data set in a memory buffer and computing new features for all the data after each DNN learning phase. The authors also experimented with a bounded memory buffer, but observed significant decrease in performance due to catastrophic forgetting (Kirkpatrick et al. 2017). i.e., loss of information from previous experience.

---

Under review as a conference paper at ICLR 2020
Peskeato features
Traie DMN to prodict reaorrs
Deilaaz 1 Dre bi] saled de ournat DAV ruplay
bandit model (pulic
cow fustars 3dl
Raploee/kappot
Compur prbcs audd warieng the canee fastaco thas Soess
Wagio
Sampll woiihtt vactur the sacuraakiy sn opotraally with sampled weiggtt replay
Nest
Figure 1: Neural-Linear contextual Thompson sampling with limited memory.
In this work, we propose neural-linear bandit that uses TS top of the last layer of DNN (Fig. Key to our approach is novel method compute priors whenever the DNN features change that makes our algorithm resilient to catastrophic forgetting. Specifically, we adjust the moments of the likelihood of the reward estimation conditioned on new features to match the likelihood conditioned on old features. We achieve this by solving a semi-definite program (Vandenberghe & Boyd 1996 SDP) to approximate the covariance and using the weights of the last layer prior to the mean.
We present simulation results several real-world and simulated data sets, including classification and regression, using Multi-Layered Perceptrons (MLPs). Our findings suggest that using our method to approximate priors improves performance when memory is limited. Finally, we demonstrate that our neural-linear bandit performs well in a sentiment analysis data set where the input is given in natural language (of size R&*) and we use Convolution Neural Network (CNNs). In this regime, it is not feasible to use a linear method due to computational problems. To the best of our knowledge, this is the first neural-linear algorithm that is resilient to catastrophic forgetting due to limited memory.
BACKGROUND
The stochastic, contextual (linear) multi- armed bandit problem. There are N arms (actions). At time& t context vector b(t) Rd, revealed. The history at time i. is defined to be H = (D(T), ((T))
Algorithm 1 TS for linear contextual bandits
Vi []...N, set B: Ia. مم= Od, ft Oa for t= 1,2,,,....
do
I,... 1-1), time
Vi [1.., sample ja from N (pi, v² B,B,' Play arm a(t) == arg max; b(t)² ii,
where a(r) denotes the arm played T. The contexts b(t) are assumed to be re-
Observe reward r.
alizable. i.e., the reward for arm i at time is generated from (unknown) distribution s.t. (r. (t),, H.-1]
Update: Ba(t) = Ba(e) + ((t)((tTT
Sa(t) = Sa(o + b(I)r,, Patt) B Sate)
E (r)((b(()
end for
b(1)T u4, where {ur R are fixed but un- known parameters. An algorithm for this prob
lem needs to choose at every time f an arm a(t) to play, with the knowledge of history H₂-1 and current context (()). Let a" (L) denote the optimal arm at time t, i.e. a (1) = arg max,b(t)² ps, and let (t) the difference between the mean rewards of the optimal arm and of arm at time t, i... (1) b(t)" (a-(t) b(t)T p. The objective is minimize the total regret R(T) Ei= Aa(t)- where the time horizon T is finite.
TS for linear contextual bandits. Thompson sampling is an algorithm for online decision problems where actions are taken sequentially in a manner that must balance between exploiting what is known to maximize immediate performance and investing to accumulate new information that may improve future performance (Russo et al. 2018 Lattimore & Szepesvári 2018). For linear contextual bandits,
TS was introduced in (Arrwal & Goyal 2013 Alg.
Image credits: bandit (hottom), Mierosoft research; confidence ellipsoid (right), OriginL.ab.
2

---

Under review as a conference paper at ICLR 2020
Suppose that the likelihood of reward rt(t), given context b(t) and parameter 14, were given by the pdf of Gaussian distribution N (((()" p1,"), and let Bt(t) = D Σ b(T)6(r)" ===((r)> where 1 is the indicator function. Given a Gaussian
(t) = B; (t) Ei (T) prior for arm at time t, (()a(t), v² B, (t)), the posterior distribution at time t is given by, (r()
Pr(r ~ ((a + 1), v2 B 1)).
(1)
At each time step t, the algorithm generates samples {ū,(t)} from the posterior distribution ((a, ((), plays the arm i that maximizes b(t)² (a(()) and updates the posterior. TS is guaranteed to have total regret time T that is not larger than ((d//2/T) which is within factor of vd of the information -ommation-thhorticc lower bound for this problem. It is also known to achieve excellent empirical results (Lattimore & Szepesvári 2018).
Although that TS is a Bayesian approach, the description of the algorithm and its analysis are prior- free, i.e., the regret bounds will hold irrespective of whether or not the actual reward distribution matches the Gaussian likelihood function used to derive this method (Agrawal & Goyal 2013).
Bayesian Linear Regression. A different mechanism, based on Bayesian Linear Regres- sion, was proposed by Riquelme al. (2018). Here, the noise parameter V (Alg. [ is re- placed with a prior beliet that is being updated over time. The prior for arm i at time t is given by Pr(Us, Di))
Pr(i?) Pr(4)) WE), where Pr(D?) is an inverse-gamma distribution (4)), and the conditional prior density Pr (of) is a normal distribution, Pr(je 17) x N (A. (t), 1/ (t) For Gaussian likelihood, the posterior distribution at time 11 is, Pr(ūs) Inv-Gamma (a.(r), b((T) and Pr(ūe((s) N ((r((),,)) B.)))))) where:
an--Gamma(a:())
B((1) B + Σ (T)) fe(1) E ((T)):(7))
(.))) = B.(() - (B9 + f(()). a:(t) = of -/ 12(1)) = 12, +)
- A.1) (1))) = o9 + 2 (1) - B(000.))
1
The problem with this approach is that the marginal distribution of μ4; is heavy tailed (multi-variate t-student distribution, see O'Hagan & Forster (2004), page 246, for derivation), and does not satisfy the necessary concentration bounds for exploration in (Agrawal & Goyal 2013 Abeille et al. (017). Thus, in order to analyze the regret of this approach, new analysis has to be derived, which we leave to future work. Empirically, this update scheme was shown to convergence to the true posterior and demonstrated excellent empirical performance (Riquelme et al. 2018). This can be explained by the 6.()) fact that the mean of the noise parameter Vi, given by Ev; = a is decreasing to zero with time, which may compensate for the lack of shrinkage due to the heavy tail distribution.
3 LIMITED MEMORY NEURAL-LINEAN TS
Our algorithm, depicted in Fig. is composed of four main components: (1) A DNN that takes a raw context as an input and is trained to predict the reward of each arm; (2) An exploration mechanism that uses the last layer activations of the DNN as features and performs linear TS on top of them; (3) A memory buffer that stores previous experience; (4) A likelihood matching mechanism that uses the memory buffer and the DNN to account for changes in representation. We now explain how each of these components works; code can be found in (link)
To derive our algorithm we make the assumption that all the representations that are produced by the DNN are realizable. That is, for each representation there exist a different linear coefficients vector (e.g. y for Φ, 3 for vi.)) such that the expected reward is linear in the features. Explicitly, this means that for representations Φ) t it holds that (1) = ((t)T μ4 = (1)" 3, = (()((())))))))
While the realizability assumption is standard in the existing literature on contextual multi-armed bandits (Chu et al. 2011] AAbbasi- Yadkori et al.; 2011 Agrawal & Goyal, 2013). it is quite strong and may not be realistic in practice. We further discuss these assumptions in the discussion paragraph below and in Section
1. Representation. Our algorithm uses DNN, denoted by D. that takes the raw context b(() IRd as its input. The network has N outputs that correspond to the estimation of the reward of each arm; given context b(t) Rdd D(b(L)); denotes the estimation of the reward of the i-th arm.
3

---

Under review as a conference paper at ICLR 2020
Using DNN to predict the reward of each arm allows algorithm to learn nonlinear representation of the context. This representation is later used for exploration by performing linear TS on top of the last hidden layer activations. We denote the activations of the last hidden layer of D applied context as (tt) = LastLayerActivations// ((((())) where @(t) E R The context b(t) represents
this
raw measurements that can be high dimensional (e.g., image text), where the size of ((t) is design parameter that we choose to be smaller (g- d). This makes contextual bandit algorithms practical for such data sets, Moreover, o(t) can potentially be linearly realizable (even if b(t) not) since a DNN is global function approximator (Barron 1993) and the last layer is linear.
1.1 Training. Every L iterations, we train D for /' mini-batches. Training is performed by sampling experience tuples (b(T), (T)))( from the replay buffer E' (details below) and minimizing the mean squared error (MSE),
((b(T))a(r) - (T)))
(3)
where ra(r) the reward that was received time T after playing arm a(r) and observing context b(T) (similar to Riquelme al. 2018)). Notice that only the output of arm a(r) is differentiated. We emphasize that the DNN, including the last layer, are trained
to minimize Eq. 3
Algorithm 2 Limited Memory Nenral-linear' TS
Set vi E [1, N] 44 Ias jú, n Oa, D. Odwd, J1 = Od, 0g = by 6g
Initialize Replay Buffer E, and DNN D
Define o(t) + aasssLayyyrActivaiinn((Oooo for f t= 1.2..... do
Observe 6(t), evaluate ((t)
Posterior sampling: Vi E [1, .. N), sample:
(t) ~ Inv-Gamma (a, (a,(t), (t))
(=(()= ~ N (it, (1) + 43)
Play arm a(t) == arg max; ((t)T (t) Observe reward r.
Store (b(t), rt) in E if F. is full then
Remove the first tuple in E with a = a(t) (round robin) end if
Bayesian linear regression update:
+ Pa(e) = + aat)) + (()) Sa(t) = Sace + ((t)Frr
Pa(t) (4 + +a(()) ( (0(0)/(10) + fa(e)
Ga(t) = Ga(t) +
R2 = Ra( +
ba()) = 12(;; + 2
1 R2(0) + ((((())
BO ( Voles BacesHace)
if (I mod L) 0 then
for Vi [] do
Evaluate old features on the replay buffer: E end for
gotd
Train DNN for P steps
Compute priors for new features:
for Vi E [I,..,N] N] do
Evaluate new features on the replay buffer: Es
Solve for Φ using Eq. 6 with EG, Ej Eggia, Hold
Set 1 Lastt.ayerWeighns()) 4. Σラ= (0 f. (d)
end for end if end for
Exploration. Since our algorithm performing training phases (every L steps), exploration is performed using fixed representation é (7) has fixed weights between training phases). At each time step t, the agent observes raw context b(t) and uses the DNN D to produces a feature vector Φ(t). The features ((t) are used to perform linear TS, similar to Algorithm 1 but with two key differences.
4

---

Under review as a conference paper at ICLR 2020
First, we introduce likelihood matching mechanism that accounts for changes in representation (see 4. below for more details). Second, we follow the Bayesian linear regression equations, as suggested in (Riquelme et al.) 2018), and perform TS while updating the posterior both for ju, the mean of the estimate, and V, its variance.
This is done in the following manner. We begin by sampling a weight vector jú; for each arm i E I..N, from the posterior by following two steps. First, the variance 2/, is sampled from Inv-Gamma (aq. b;). Then, the weight vector iú sampled, from N (i., i/f ( + -x)=²)) Once we sampled a weight vector for each arm, we choose to play arm a(t) arg max, (t) jts and observe reward Ta(s) (t).
This is followed by a posterior update step, based Eq. (
@ Pa(e) Pa()) + +(t))(t)², fa(t) = Sal: + =ot) re. Ra()) Ract)) + (t)))
(4)
Aa(e) (Pa(t) + + a(o) + fa(e)) anti) = aa(t) + 2'
ba(t) = bo,a(1) + [2()) Moiate) 2o,a(0)/o Pate) (tto)())
The exploration mechanism is responsible for choosing actions; it does not change the weights of the DNN.
3. Memory buffer.
After an action a(t) is played at time t, we store the experience tuple {b((), a((), (()) in finite memory buffer of size n that we denote by E. Once E is full, we remove tuples from E in a round robin manner, i.c., we remove the first tuple in E with = a(t).
4. Likelihood matching, Before each learning phase, we evaluate the features of D on the replay buffer. Let E, be subset of memory tuples in E at which arm i was played, and let n, be its size. We denote by E guls E R2 a matrix whose rows are feature vectors that were played by arm i. After a learning phase is complete, we evaluate the new activations on the same replay buffer and denote the equivalent set by E E RR
Our approach is to summarize the knowledge that the algorithm has gained from exploring with the features gold into priors the new features T Tp, 14. Once these priors computed, restart the linear TS algorithm using the data that is currently available in the replay buffer. For each arm i, let 0f = (Eg); be the j-th row in E and let ry be the corresponding reward, we set 4, = Ej (f)))) = E ())(")) T3.
We now explain how we compute D., uº. Recall that under the realizability assumption we have that ((r:(t))@(t) = (t)) #4 = (o) nith = (frx(t))((() Thus, the likelihood of the reward invariant to the choice of representation i.e. N(O(t)) H,, ~ N()ald(t) pugld v²). For all i, define the estimator of the reward as (,(() x(1)² (t), and its standard deviation 81,4 Vo(1)² (20))12,110 2,()) (see (Agrawal & Goyal 2013) for derivation). By definition of (i(t), marginal distribution of each (t) is Gaussian with mean @ (t)² p. (t) and standard deviation 14 The goal match the likelihood of the reward estimation (t) given the new features to be the same with the old features.
4.1 Approximation of the mean n.: Recall that the realizability assumption implies a linear con- nection between 1 14, i.e., (uuldyr gold (uQ)Tá, o, thus, we can solve a linear set of equations and get linear mapping from pi agld:
(nh)*= = (ng ( Eg (Ea) (E
(5)
In addition to the realizability assumption, for Eq. (5) hold the matrix E must be invertible. In practice, we found that different solution that is based on using the DNN weights performed better. Recall that the DNN is trained to minimize the MSE (Eq. Thus, given the new features Φ, the weights of the last layer of the DNN make good prior for μ. This approach was shown empirically to make a good approximation (Levine et al. 2017). as the DNN was optimized online by observing all the data (and is therefore not limited to the current replay buffer).
4.2 Approximation of the variance sj.t.. For each arm i, our algorithm receives as input the sets of new and old features E3 i denote the elements in these sets by (Øgth &, ) In addition, the algorithm receives the correlation matrix hold Notice that due the nature of our algorithm, Bold holds
5

---

Under review as a conference paper at ICLR 2020
information contexts that are not available in the replay buffer. The goal is to find correlation matrix, for the new features that will hold the same information on past context as Doldd Le., we
want to find T such that Vi E [1..N],,j E [1..m.] 23 = ( ( -ppidd = of (3)) oj
Using the cyclic property of the trace, this is equivalent to finding D. s.t. Vj E [L..., n.l, S3 Trace (00))
Next, we define X; to be a vector of size n; in the vector space of d d symetric matrices, with its j-th element X,,, to be the matrix o Notice that (o.)-1 is constrained to be semi positive definite (being a correlation matrix), thus, the solution can be found by solving an SDP (Eq. (6). Note that (Ta (X)))=)))) is an inner product over the vector space of symmetric matrices, known as the Frobenius inner product. Thus, the optimization problem is equivalent to a linear regression problem in the vector space of PSD matrices. In practice, we use cvxpy (Diamond [1.
& Boyd 2016) to solve for all actions E
minimize (+?)-
Σ
|Tracee ( -1 s3,ll subject to (Φ)) N 0.
(6)
Discussion. The correctness of our algorithm follows from the proof of (Agrawal & Goyal 2013)
To see this, recall that we match the moments of the reward estimate (t) after every time that the representation changes. Assuming that we solve Eq. (5) and Eq. (6) precisely, then the reward estimation given the new features have precisely the same moments and distribution as with the old features. Since the distribution of the estimate did not change, its concentration and anti-concentration bounds do not change, and the proof in (Agrawal & Goyal 2013) can be followed.
The problem is, that general, we cannot guarantee to solve Eq. (5) and Eq. (6) exactly. We will soon show that under the realizability assumption, in addition to an invertibility assumption, it is possible to choose analytical solution for the priors (Mo, t0 that guarantees an exact solution. However, these conditions may be too strong and not realistic. We describe this scenario to highlight the existence of a scenario (and conditions) in which our algorithm is optimal: we hope to relax them in future work. We emphasize here that if these conditions do not hold, then our algorithm is only an approximation, without theoretical guarantees. In the next section we justify using our algorithm through thorough experimentation.
For simplicity, we consider single arm. Assume that m past observations, which we denote by Ex were used to learn estimators (Am)ald &oll using BLR (Eq. (2). Due to the limited memory, some of these measurements are not available in the replay buffer, and all of the information regarding them is summarized in (fim) )old, gold_ In addition, we are given a replay buffer of size n, that is used to produce (before and after the training) new and old feature matrices gom D We also denote by Rm, the reward vector (using data from the replay buffer) and by Rm the reward vector that corresponds to features Equ which is not available the replay buffer. Recall that the realizeability assumption implies that the features ø and gold are linear mappings of the raw context b, i.e., o = A,b, gold Agatab. Under the assumption that all the relevant matrices are invertible, we use Eq. (5) to find a prior for (oo i.c., we set 1i (Dold) (old)TE" E (Ez)= In addition, for the which is a solution
covariance matrix, we set (55)-1 = (Fz) -1 Fignte (Bold)) -1 )T ((E(( to Eq. 6
In addition, we get that if the relevant matrices are invertibele, then h0 + and that t"m0 ET Ru (see the supplementary for derivation). Plugging these estimates as priors in the Bayesian linear regression equation get the following solution for Ā
u = ( 4") (0* p0 + E Rm,) = (Φ. + 2m) -L Rm + By)R),
i.., we got the linear regression solution for μ as if we were able to evaluate the new features 6 on the entire data, while having finite memory buffer and changing features!
3.1 COMPUTATIONAL COMPLEXITY
Solving the SDP. Recall that the dimension of the last layer is g < d where is the dimension of the raw features, and the size of the buffer is n. Following this notation, when solving the SDP, optimize over matrices in Rex9 that are subject to n equality constraints. We refer the reader to Vandenberghe Boyd (199) for an excellent survey on the complexity of solving SDPs. Here, we will reter to interior- interior-point point methods. The number of iterations required to solve an SDP to a given accuracy grows with problem size (.5.) Each iteration involves solving a least-squares

---

Under review as a conference paper at ICLR 2020
problem of dimension g². If, for example, this least-squares problem is solved with projected gradient descent method, then the time complexity for finding an e-optimal solution is g²/ and the computational complexity of each gradient step is ngg (matrix-vector multiplications). Vandenberghe & Boyd experimented with solving SDPs of different sizes and observed that it takes almost the same amount of iterations to solve them. In addition, they found that SDP algorithmss converge much faster than the worst-case theoretical bounds.
In our case, 9, the size of the last layer, was fixed to be 50 in all the experiments. Thus, although the dimension of the raw features varies in size across data sets, the complexity of the solving the SDP is fixed. The dependence of the computational complexity on the buffer size n is at most linear (CVXPY exploits sparsity structure of the matrix to enhance computations); we didn't t encounter a significant changes in computation time when changing the buffer size in the range of 200 2000. It took us 10 - 30 seconds on standard "MacBook Pro" to solve a single SDP.
Dependence on T. The full memory approach results in computational complexity of O(T?) and memory complexity of O(T) where T is the number of contexts seen by the algorithm. This is because it estimating the TS posterior using the complete data every time the representation changes. On the other hand, the limited memory approach uses only the memory buffer to estimate the posterior but additionally solves an SDP. This gives a memory complexity of O(1) and computational complexity of O(T).
Dependence on A. The computational complexity is linear in the number of actions (we solve an SDP for each action). There is a large variety of problems where this is not an issue (as in our experiments). However, if the problem of interest has many discrete actions, our approach may not be useful.
To summarize, our method is more efficient than the full memory baseline in problems with big data (large 7T). Nevertheless, our method requires to solve an SDP (every L iterations), which computationally prohibitive general. We deal with this issue by restricting the size of the last layer to be small (g- = 50), for which solving the SDP is reasonable.
4 EXPERIMENTS
We begin this section by testing the resilience of our method to catastrophic forgetting. We present an ablative analysis of our approach and show that the prior on the covariance is crucial. Then, we present results for using MLPs on ten real-world data sets, including high dimensional natural language data on task of sentiment analysis (all of these data sets are publicly available through the UCI Machinel Learning Repository). Additionally, visualize the ability of our algorithm to learn nonlinear representations during exploration. In all the experiments we used the same hyperparameters (as in (Riquelme et al., (018)) for the model, and the same network architecture (an MLP with a single hidden layer of size 50). The only exception is with the text CNN (details below). The size of the memory buffer is set to be 100 per action.
the supplementary material, we use synthetic data test and
4.1 CATASTROPHIC FORGETTING
We use the Shuttle Statlog data set (Newman al. 2008), real world, nonlinear data set. Each context is composed of 9 features of a space shuttle flight, and the goal is to predict the state of the radiator of the shuttle (the reward). There are k- = pos- sible actions, and if the agent selects the right action, then reward is gen- erated. Otherwise, the agent obtains no reward (r = 0).
Alg1. Linear TS
Alg Nourel Unear memory
Instantanoousssoo roprec
3. Neural- inear TS, frite memory (ours)
Alg Unuart TS, finte memory, only mean prior tabletive
We experimented with the following algorithms: (1) Linear TS (Agrawal & Goyal| 2013 Algorithm D using
Niural-Linaar T5, memory, pñars (ablative)
raw context as a feature, with an
Figure 2: Catastrophic forgetting
additional uncertainty in the variance (Riquelme et al.) 2018). (2) Neural-
L.near IS (Rique me et al. (018). (3) Our neural-linear TS algorithm with limited memory. (4) An
ablative version of (3) that calculates the prior only for the mean, similar to (Levine al. 2017).
7

---

Under review as a conference paper at ICLR 2020
(5) An ablative version of (3) that does not use prior calculations. Algorithms 3-5 make an ablative analysis for the limited memory neural-linear approach. As we will see, adding each one of the priors improves learning and exploration.
Fig. shows the performance of each of the algorithms in this setup. We let each algorithm run for 4000 steps (contexts) and average each algorithm over 10 runs. The x-axis corresponds to the number of contexts seen so far, while the y-axis measures the instantaneous regret. All the neural-linear methods retrained the DNN every L = 400 steps for P = 800 mini-batches.
First, we can see that the neural linear method (2nd row) outperforms the linear one (Ist row), suggesting that this data set in nonlinear. We can also see that our approach to computing the priors allows the limited memory algorithm (3rd row) to perform almost as good as the linear algorithm without memory constraints (2nd row).
In the last two rows we can see version of the limited memory neural linear algorithm that does not calculate the prior for the covariance matrix (4th row), and a version that does not compute priors at all (5th row). Both of these algorithms suffer from "catastrophic forgetting" due limited memory. Intuitively, the covariance matrix holds information regarding the number of contexts that were seen by the agent and are used by the algorithm for exploration. When no such prior is available, the agent explores sub-optimal arms from scratch every time the features are modified (every L = 400 steps, marked by the x-ticks on the graph). Indeed, we observe "peaks" in the regret curve for these algorithms (rows 4&c5); this is significantly reduced when we compute the prior on the covariance matrix (3rd row), making the limited memory neural-lines bandit resilient to catastrophic forgetting.
4.2 REAL WORLD DATA
We evaluate our approach on several (10) real-world data sets; for each data set, we present the cumulative reward achieved by the algorithms, detailed above, averaged over 50 runs. Each run was performed for 5000 steps.
Linear vs. nonlinear data sets: The results are divided into two groups, linear and nonlinear data sets. The separation was performed post hoc, based on the results achieved by the full memory methods, i.e., the first group consists of five data sets on which Linear TS (Algorithm 1) outperformed Neural-Linear TS (Algorithm 2), and vice versa. We observed that most of the linear datasets consisted of a small number of features that were mostly categorical (c.g., the mushroom data set has 22 categorical features that become 1 17 binary features). The DNN based methods performed better when the features were dense and high dimensional.
Pall memory
Limited memory, Neural-Lincar
Name
Linear
Neural Linear
Both Priors
ja Prior
No Prior
Linear Data Sets
Mushroom
117
11022 + 774
10880 853
10923 + 839
9442 + 1351
7613 1670
Financial
21
8
4588 di 587
4389 1: 584
4597 4: 597
4311 d: 598
4225 J: 594
Jester
14080 1: 2240
128191: 2135
9624 1:
10996
2013
11114 2050
Adult
88
2
4066.1 i: 11.03
4010.0 J. 22.19
3943.0 1: 54.29
3839.5 J. 17.63
3608.2 J. 34,94
Covertype
3054 1.
2828 593
2347 1::
2334
Nonlinear Data Sets
Census
377
9
1791.5 + 39.47
2135.5 # 51.47
2023.16 + 37.3
1873 + 757
1943.83 + 84.2
Statlog
7
4483
+ 353
4781 + 274
4825 305
4681 + 285
4623 + 276
Epillppiic
178
5
1202.9 34.68
1706.9 1. 41.26
1716.8 1. 60.44
1572.9 1. 48.66
1411.0 J. 33.43
Smurtphones
3085.8
3643.5 1. 64.89
2660.4 84.72
3064.5
55.06
2851.6 1. 58.77
Scania Trucks
170
2
4691.8
1. 7.23
4784.7 1. 6.05
4742.0 1: 33.0
4698.0
13.06
4470.4 1. 37,9
Cumulative reward of TS algorithms on 10 real world data sets. The context dim d and the size of the action space A are reported for each data set. The mean result and standard deviation of each algorithm reported for 50 runs.
Table 1:
Linear data sets: Since there is no apriori reason to believe that real world data sets should be linear, we were surprised that the linear method made competitive baseline to DNNs. To investigate this further, we experimented with the best reported MLP architecture for the covertype data set (taken from Kaggle). Linear methods were reported (link) to achieve around 60% test accuracy. This number is consistent with our reported cumulative reward (3000 out 5000). Similarly, DNNs achieved around 60% accuracy, which indicates that the Covertype data set is indeed relatively linear. However, when we measure the cumulative reward, the deep methods take initial time to learn, which can explain the slightly worst score. One particular architecture (MLP with layers 54-500-800-7) was reported to achieve 68%; however, we didn't 't find this architecture to yield better cumulative reward.
8

---

Under review as a conference paper at ICLR 2020
Similarly, for the Adult data set, linear and deep classifiers were reported to achieve similar results (link) (around 84%), which is again equivalent our cumulative reward of 4000 out of 5000. A specific DNN was reported to achieve 90% test accuracy but did not yield improvement cumulative reward. These observations can be explained by the different loss function that we optimize or by the partial observably of the bandit problem (bandit feedback). Alternatively, competitions tend to suffer from overfitting in model selection (sce the "reusable holdout" paper for more details (Dwork et al. 2015)). Regret, the other hand, is less prune to model overfitring, because the model is evaluated at each iteration, and because we shuffle the data at each run.
Limited memory: Looking at Table T we can see that on eight out of ten data sets, using the prior computations (Algorithm 3), improved the performance of the limited memory Neural-L.nnar algorithms. On four out of ten data sets (Mushroom, Financial, Statlog, Epileptic), Algorithm 3 even outperformed the unlimited Neural- algorithm (Algorithm 2).
Limited memory neural linear vs. linear: as linear TS is online algorithm it can store all the information on past experience using limited memory. Nevertheless, in four (out of five) of the nonlinear data sets the limited memory TS (Algorithm 3) outperformed Linear TS (Algorithm 1). Our findings suggest that when the data is indeed not linear, than neural-linear bandits beat the linear method, even if they must perform with limited memory. In this case, computing priors improve the performance and make the algorithm resilient to catastrophic forgetting.
4.3 SENTIMENT ANALYSIS FROM TEXT USING CNNS
We use the "Amazon Reviews: Unlocked Mobile Phones" data set, which contains reviews of un- locked mobile phones sold " "Amazon.com" The goal is to find out the rating (1 to 5 stars) of each review using only the text itself. We use our model with a Convolutional Neural Network (CNN) that is suited to NLP tasks (Kim, 2014] (Zahavy et al.] 2018b). Specifically, the architec- ture is a shallow word-level CNN that was demonstrated to provide state-of-the-art results on a variety of classification tasks by using word embeddings, while not being sensitive to hyperpa- rameters (Zhang & Wallace 2015). We (Github) and standard pre-processe precessccssin (e.g.. we use random embeddings of size 128, and we trim and pad each sentence to a length of 60). The only modification we made was to add a linear layer of size 50 to make the size of the last hidden layer consistent with our previous experiments.
the architecture with its default hyper-parameters
Since the input is in R.Th (60 x 128), we did not include a linear baseline in these experiments as it is impractical to do linear algebra (e.g., calculate an inverse) in this dimension. Instead, we focused on comparing our final method with the full memory neural linear TS and both prior computations with an e- greedy baseline. We experimented with 10 values of é, E [0.1, 0.2, ..., 1] and report the results for the value that performed the best (0.1). Looking at Fig. [3] we can see that the limited memory version performs almost as good the full memory, and better than the greeddy baseline.
Neural-Linear Limited Memory 3143.9 + 33.5
6 g-greedy
Neural-Linear
2963.9 + 68.5
3155.6 + 34.9
Figure 3: Cumulative reward on Amazon review's
5 DISCUSSION
We presented neural-linear contextual bandit algorithm that is resilient to catastrophic forgetting and demonstrated its performance on several real-world data sets. Our algorithm showed comparable results to a previous method that stores all the data in replay buffer. The method requires to solve an SDP, which is computationally prohibitive in general. Thus, we restricted the size of the last layer to be small, such that solving the SDP is feasible.
To design our algorithm, we assumed that all the representations that are produced by the DNN are realizable. In practice, the features that are learned in the first iterations are nearly realizable and further iterations improve them. We hope to relax these assumptions in future work.
Our algorithm presented excellent performance on multiple real-world data sets. Moreover, its performance did not deteriorate due to the changes in the representation and the limited memory. We believe that our findings make an important step towards solving problems where both exploration and representation learning play an important role.
9

---

Under review as a conference paper at ICLR 2020
REFERENCES
Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Mare Abeille, Alessandro Lazaric, al. Linear thompson sampling revisited. Electronic Journal of Statistics, 112):5165-5197,, 2017.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In International Conference on Machine Learning, pp- 127-135, 2013.
Peter Auer. Using confidence bounds for exploitation-exxllrraton trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
Kamyar Azizzadenesheli. Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep q-networks. arXiv preprint arXiv:/802.04412..00 2018.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3)930-994,, 1993.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-baset exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire, Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pp. 208-214, 2011.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold. and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 34966248))636-638, 2015.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Yoon Kim. Convolutional neural networks for sentence classification. arXiv preprint, 2014.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan. John Quan, Tiago Ramalho, Agnieszka Grabska Barkknskaaaaaaaa Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114(13)3321-3356 2017. ISSN 0027-8424, doi: 10.10733pnas.166 1835114. ÜRL htt.http:s.. /wwww//wwww.///////////////w pwas....................... org/
Eontent/114/13/555
John Langford and Tong Zhang. The groch- algorithm for multi-armed bandits with side information. In Advances neural information processing systems, pp. 817-824, 2008.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. 2018.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436, 2015.
Nir Levine, Tom Zahavy, Daniel Mankowitz, Aviv Tamar, and Shie Mannor. Shallow updates for deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3135-3145, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53) 2015.
David Newman, Padhraic Smyth, Max Welling, and Arthur U Asuncion. latent dirichlet allocation. In Advances neural information processing systems, pp. 1081-1088, 2008.
Distributed inference for
Brendan O' D'Donoguue, Ian Osband, Remi Munos, and Volodymyr Mnih. equation and exploration. International Conference on Machine Learning, 2018.
The uncertainty bellman
Anthony O' O'Hagan and Jonathan J Forster. Kendall's advanced theory of statistics, volume 2B:
Bayesian inference, volume 2. Arnold, 2004.
10

---

Under review as a conference paper at ICLR 2020
Ian Osband, John Aslanides, and Cassirer Albin. Randomized prior functions for deep reinforcement learning. Advances Neural Information Processing Systems, 2018.
Deepak Pathak, Pulkit Agrawal, Alexci A Efros, and Trevor Darrell. Curiosity- driven exploration by self-supervised prediction. In International Conference Machine Learning, 2017.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown. In Interna- tional Conference on Learning Representations, 2018.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser. Ioannis Antonoglou, Veda Pannecrshelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel. and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, jan 2016. ISSN 0028-0836. doi: 10. 1038/nature 16961.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-29) 1933.
Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review, 38(1):49-95, 1996.
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. Advances in Neural Information Processing Systems, 2018a.
Tom Zahavy, Alessandro Magnani, Abhinandan Krishnan, and Shie Mannor. Is a picture worth thousand words? a deep multi-modal fusion architecture for product classification in e-commerce. The Thirlieth Conference on Innovative Applications of Artificial Intelligence (IAAI), 201 8b.
Ye Zhang and Byron Wallace. A sensitivity analysis of (and practitioners' guide to) convolutional neural networks for sentence classification. arXiv preprint arXiv: 2015.

---

Under review as a conference paper at ICLR 2020
APPENDIX A ADDITIONAL SIMULATIONS: NON LINEAR REPRESENTATION LEARNING ON A SYNTHETIC DATA SET
we adapted synthetic data set, known as the "wheel bandit" (Riquelme et al., 2018). to investigate the exploration properties bandit algorithms when the reward Is a nonimear lunction of the context. Specifically, contexts IR2 are sampled uniformly at random in the unit circle, and there are
Setup:
possible actions.
One action 45, always offers reward r5 ~ N (Pss σ), independently the context. The reward of the other actions depend on the context and parameter 6, that defines d-circle || s 6.
For contexts that outside the circle, actions d1,.., ag equally distributed and sub-optimal, with Ys N (H, ) for μ 1A5, i [1.44].
For contexts that are inside circle, the reward of each action depends on the respective quadrant.
Each action achieves r; ~ [Ms, JJ,, where μl < μ4 = ja in exactly one quadrant, and 14 = μ < μs in all the other quadrants. For example, [41 ji in the first quadrant {2: ||>|| I 5, 1.
0} and 1l1 = μ elsewhere. We set µ 0.1, (As 0.2. j 0.4. 0.1. Note that the probability of a context randomly falling in the high-reward region is proportional ó. For lower values of 5, observing high rewards for arms a,,,,, 04 becomes more scarce, and the role of the nonlinear representation is less significant.
We train our model
4000 contexts, where optimize the network every L 200 steps for P = 400 mini batches. The results can be seen in Table
Not surprisingly, the neural-linear approaches, even with limited memory, achieved better reward than the linear method (Table
6.1n
0/
nb
6.n
Figure 4: Representations learned on the wheel data set with 5 0.5. Reward samples (top), linear predictions (middle) and neural-lines predictions (bottom). Columns correspond to arms.
Fig. presents the reward of each arm a function of the context. In the top row, we can see empirical samples from the reward distribution. In the middle row, see the predictions of the linear bandit. Since it limited to linear predictions, the predictions become function of the distance from learned hyper-plane. This representation is not able to separate the data well, and also makes mistakes due to the distance from the hyperplane. For the neural linear method (bottom row), we can see that the DNN was able to leam good predictions successfully. Each of the first four arms learns to make high predictions in the relevant quadrant of the inner circle, while arm 5 makes higher predictions in the outer circle.
We will provide detailed comparison of the neural-linear algorithms and priors later this section.
12

---

Under review as a conference paper at ICLR 2020
Neural-Linear Lim- ited Memory
Linear
6=0.5
737.44 + 3.04
899.72 12.79
6=0.3
735.37 = 2.58
781.09 11.34
6=0.1
735.51 + 2.59
751.75 + 3.6
Table 2: Cumulative reward on the wheel bandit
APPENDIX B ANALYSIS
B. DERIVATION AUXILIARY RESULTS FOR THE SANITY CHECK
The realizability assumption gives us a method to compute po for the new features:
H = (Dold)" Egoia (E (E (EE (E )T) (E ) Rm E (maa))
-1
(7)
Similarly, using the analytically solution the SDP, we get
E ( (E)) = Egora ) (Egols)
(8)
Using Eq. (7) and Eq. 8 and rearranging we get that
T 140
F3 (Figou)) -1 F Pum
(Agbn)(A (Agotabr)) -1 Agolabai Rm
= AAbim bym A Agdid Agoiabm Rm
Agbm E Rmn
Similarly, for Th we get that
Φ E (E)ol)) ((DD))) (ota) (
(Agb))(Agraan (Agotabn) -2 (Boldd (b, Agdhe) ( (Aobn)²
m7
AdA As
baby A7 (ANr)
A
b.by A% 4m
13


Reviews:
[{"review_id": "rklDDmY0tB", "reviewer": "AnonReviewer1", "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": "This paper adapts Bayesian linear regression to the setting of a limited memory replay buffer. The idea is to calibrate the prior mean and variance when the neural representation of context is updated. Overall the paper is well written and explained clearly. Some experiments are provided to show that the proposed method is able to achieve a performance competitive to Bayesian linear regression with infinite memory.\n\nThe result of this paper is interesting. But I am not sure if the current experimental results are convincing enough to justify the significance of the proposed method. \n1. The results in Section 4.2 seem to be following the setting in Riquelme 2018. These datasets are all in a supervised learning setting. It is a bit disappointing that the proposed method is not tested on RL datasets. \n2. No other baseline is provided in the experiments for comparison. \n    a. There are other methods in the literature to overcome catastrophic forgetting of neural networks, e.g regularizing the update of the network. How would that be compared to the proposed method?\n    b. What about other methods, like [1]?\n3. Most of the experiment details are missing. For example, how is the reward defined in section 4.3? What is the overhead in computation in practice, especially for the SDP?\n\n\nOther comments:\n1. Why would solving a SDP require only O(g^{0.5}) in section 3.1?\n2. In the discussion in section 3, even if equation (5) and (6) can be exactly solved, how does the heavy tailed problem mentioned in section 2 been solved?\n\n\n[1] Elmachtoub, Adam N., et al. \"A practical method for solving contextual bandit problems using decision trees.\" arXiv preprint arXiv:1706.04687 (2017).", "extra_scores": {"experience_assessment": "I do not know much about 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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlaTfYptS", "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": "Summary:\n\nThis work provides a memory-efficient nonlinear bandit algorithm based on deep neural networks. More specifically, the algorithm in this work only uses part of history information to save the memory usage. To overcome the catastrophic forgetting problem,  the authors provided novel covariance matrix approximation method. Experiment results also suggest that \n\nPros:\n\nThe writing of this paper is very well. It provides enough introduction of the background of nonlinear bandit problems. The experiment settings and results are convincible. \n\nCons:\n- The core idea lacks solid theoretical supports. There is no regret bound result in this paper. The reason why I think the authors should add such theoretical proof is that it seems that the idea to construct new prior matrix instead of old one to avoid the catastrophic forgetting is not related to deep neural network at all. Thus, given existing regret analysis for Thompson sampling on linear bandit problems, the authors should also provide a simple analysis on linear case to show that the construction of prior matrix is indeed meaningful. \n\n- The experiment part does not show the accuracy the SDP solve needs. As the authors mentioned in Discussion part, below equation 6, it is very crucial to decide the accuracy the SDP solver needs. I suggest the authors add more details about the SDP solver in the experiment part.\n\n\nMinor comments:\n\n- The authors used DNN to minimize equation 3. Have the authors tried  a regularized MSE instead of (3)? I think to add a regularizer can further improve the results. \n- At page 13, below equation 8: why the first equality lacks?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlg_dy0KB", "reviewer": "AnonReviewer2", "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": "This paper proposes a neural linear bandits algorithm that is resilient to catastrophic forgetting when using limited memory.\n\nThe proposed algorithm Alg. 2 is similar to Thompson sampling for linear contextual bandits, Alg. 1, but using the last layer activation vectors as a linear feature, and also a different way of updating noise parameter prior and posterior is used based on Bayesian linear regression Eq. (2).\n\nAlg. 2 also works with limited memory of history data, therefore after every time, the memory is refreshed, likelihood matching is used to calculate new Phi to make the likelihood (mean and variance) of reward estimation the same as it for the old feature. For mean matching, minimizing MSE Eq. (3) is used and for variance, solving PSD problem Eq. (6) is used.\n\nThe complexity of this algorithm is analyzed. And experiments are conducted to show that the proposed method is resilient to catastrophic forgetting and can achieve good cumulative reward results.\n\nThe proposed method is reasonable and the results look promising. However, I found several weak points as follows.\n\n1. As mentioned Bayesian linear regression Eq. (2) is used to update noise prior and posterior, but this update has no theoretical guarantees as mentioned. As an algorithm mainly works under bandit settings, this is kind of undesirable.\n\n2. This algorithm works with neural network-based features, but it is in nature not scalable as shown in the complexity analysis (linear dependence on action number). The linear feature is just replaced by the last layer activation of NNs. From this perspective, the experimental results just justify again that the NN feature is somehow powerful, which is as expected.\n\n3. The likelihood matching can deal with catastrophic forgetting with limited history memory, which looks good. But the fact that it actually works for linear feature (last layer activation) together with realization assumption weakens this contribution a lot. The authors find using Eq. (3) is better than the exact mean matching Eq. (5), and there is no explanation for this, which kind of shows the proposed likelihood matching probably is not a good way when using full NNs rather than just linear features (last layer). On the other hand, the SDP seems also can only work under linear feature settings, and is not promising to be generalized to fully update for NNs.\n\nOverall, this is a reasonable paper. However, on the one hand, as an algorithm mainly works under bandit settings, it is a lack of theoretical support. On the other hand, the linear feature setting weakens the contribution of likelihood matching to deal with catastrophic forgetting with limited memory. There are some questions of the proposed mean matching, and the matching is not able to generalize. ", "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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers found the problem statement having merit, but found the solution not completely justifiable. Bandit algorithms often come with theoretical justification because the feedback is such that the algorithm could be performing horribly without giving any indication of performance loss. With neural networks this is obviously challenging given the lack of supervised learning guarantees, but reviewers remain skeptical and prefer not to speculate based on empirical results. 
Decision: Reject