Online Limited Memory Neural-Linear Bandits
Authors: Tom Zahavy
Ofir Nabati
Leor Cohen
Shie Mannor
Venue:  (2021)

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 optimized during learning, information regarding exploration with “old” features is lost. We propose the first limited memory neural- linear bandit that is resilient to this catastrophic forgetting phenomenon by solving a semi-definite program. We then approximate the semi-definite program using stochastic gradient descent to make the algorithm practical and adjusted for online usage. We perform simulations on a variety of data sets, including regression, classification, and sentiment analysis. In addition, we evaluate our algorithm in a challenging uplink rate-control application. The bandit controls the transmission rates of data segments over cellular links to achieve optimal throughput. We observe that our algorithm achieves superior performance and shows resilience to catastrophic forgetting.

Under review as a conference paper at ICLR 2021
ONLINE LIMITED MEMORY NEURAL-LINEAR BAN- DITS
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 optimized during learning. information regarding exploration with "old" features is lost. We propose the first limited memory neural- linear bandit that is resilient this catastrophic forgetting phenomenon by solving a semi-definite program. We then approximate the semi-definite program using stochastic gradient
to make the algorithm practical and adjusted for online usage. We perform simulations on a variety of data sets, including regression, classification, and sentiment analysis. We observe that our a 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 sate-of-thheart 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-spectie specific knowledge. and learn rich domain representations from raw, high-dimensional inputs (Mnih et al., 2015 Silver et al. 2016).
Nevertheless, the question of how to perform efficient exploration during the representation learning phase is still an open problem. The c-greedy policy (Langford & Zhang 2008) is simple to implement and widely used practice (Mnih et al. 2015). However, Is statistically suboptimal. Optimism in the Face of Uncertainty (AbbasI-Yadkon Yadkori al. 2011:: Auer [002 OFU), and Thompson Sampling (Thompson) 1933 Agrawal & Goyal| 2013) IS) use confidence sets to balance exploitation and exploration. For DNNs, such confdence sets may not be accurate enough to allow efficient exploration. For example, using dropout as a posterior approximation for exploration does not concentrate on observed data (Osband et al. 2018) and was shown empirically to be insufficient (Riquelme et al. 2018). Alternatively. pseudo-couss exploration bonus (Bellemare et al. 2016 Pathak et al. 2017). Inspired by tabular RL, these ideas ignore the uncertainty in the value function approximation each context. As result, they may lead to inefficient confidence sets (Osband et al. 2018).
a generalization of the number of visits, were used as an
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-lineal approach. In RL, this approach was shown to refine the performance of DONs (Levine et al. 2017) and improve exploration when combined with TS (Azizzadenesheli et al. 20188) () and OFU D'Dooggeee et al.) 2018 Zahavy et al. 20188). For contextual bandits, Riquelme et al. (2018) showed that neural-Imeat TS achieves superior performance multiple data sets.
practical challenge for neural-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. Zhou et al. (2019) recently suggested to analyze deep contextual bandits with an "infinite width" via the Neural Tangent Kernel (NTK) (Jacot et al. 2018). Under the NTK assumptions, the optimal solution (and its features) are guaranteed to be close to the initialization point, so that the deep bandit can be viewed as a kernel method. Riquelme et al. (2018), on the other hand, observed that with standard DNN architectures. the features do change from the initialization point and mechanism to adapt for that change is required. They tackled this problem by storing the entire data set in memory buffer and computing new features for all the data

---

Under review as a conference paper at ICLR 2021
after each DNN learning phase. The authors also experimented with bounded memory buffer but dereaantteeeeaaeee
observed a significant decrease in performance due to catastrophie forgetting (Kirkpatrick et al.) 2017), i.e., a loss of information from previous experience.
In this work, we propose neural-linesd bandit that uses TS on top of the last layer of a DNN. Key to our approach is novel method to 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 Vandenberghee & Boyd, 1996 SDP) to approximate the covariance and using the weights of the last layer as prior to the mean. To make the algorithm more appealing for real-time usage, we implement it in an online manner, in which updates of the DNN weights and the priors are done simultancously every step by using stochastic gradient descent (SGD) followed by projection of the priors. This obviates the need to process the whole memory buffer after each DNN learning phase and keeps the computational burden of our algorithm small.
We performed experiments on several real-world and simulated data sets, including classification and regression, using Multi-Layered Perceptrons (MLPs). These experiments suggest that our prior approximation scheme improves performance significantly when memory is limited. We demonstrate that our neural-linear bandit performs well in sentiment analysis data set where the input is given in natural language (there are 8k features), and we use a Convolution Neural Network (CNNs). In this regime, it is not feasible to use a linear method due to computational problems. In addition, we evaluate our algorithm in stochastic simulation of an uplink redeo-transmmisionn application. In this application, the length of the simulation is so long that is not possible to use the unlimited memory neural-linear approach of Riqqulme et al. (2018). To the best of our knowledge, this the first neural- linear algorithm that is resilient to catastrophic forgetting due to limited memory. In addition, unlike Riquelme et al. (2018), which use a patch-based approach, our algorithm can be configured to work in an online manner, in which the DNN and statistics are efficiently updated each step. Thus, this is also the first neural- linear online algorithm.
2 BACKGROUND
The stochastic, contextual (linear) multi-armed bandit problem. At every time t, contextual bandit algorithm observes context b(t) and chooses an arm a(I) E [I,...,N] N).
The bandit can use the history H to make its decisions, where Hz-1 = (b(T), a(T), (T),
I,..,/ 1}, and a(r) denotes the arm played at time r. Most existing works typically make the following realizability assumption (Chu et al. 2011 Abbasi- Yadkori et al. 2011 Agrawal & Goyal, 2013).
Assumption 1. The reward for arm at time I is generated from an (unknown) distribution s.I. E [r:()))())) H,-1] E (r:(()](())) = b(L)² pi, where {1r E R are fixed but unknown.
Let (f) denote the optimal arm at time t, i.e. a²())= = arg max, maxxb(()TTnn p4, and let (t(t) the difference between the mean rewards of the optimal arm and of arm i at time 4, i.e. (,( = b(()²) (a-(0)
b(t)TTH 14. The objective is to minimize the total regret R(T) Σ Aact). where T is finite.
TS for linear contextual bandits. Thompson sampling is an algorithm for online decision problems where actions are taken sequentially in manner that must balance between exploiting what is known to maximize immediate perfor- mance and investing to accumulate new infor- mation that may improve future performance (Russo et al.] 2018; Lattimore & Szepesvári 2018). For linear contextual bandits, TS was introduced in (Agrawal & Goyal 2013 Alg. D
Algorithm 1 TS for linear contextual bandits
Vi [1...N, set $ = Ia. Pu Od, fr = Os for t t= 1,
do
Vi [1.., N). sample jas from N( o2 Play arm a(t) == arg max; b(1) 1hg
Observe reward r
Update: & Pa(t) = 4 a(t) + b(t)b(t)T
fa(n) = Sa(o + b(t)re. Pa(t) Tb (ltffal
Suppose that the likelihood of reward rt(,), given context b(t) and parameter μ4, were given end for
by the pdf of Gaussian distribution N (b(()" un, ui, )²). and let (.()) = D + -ーー b(T)6(T)* 1==(()) where is the indicator function and Φ is the precision prior. Given a Gaussian prior for arm at time t, ((:(()), 22 (t)), the posterior distribution at
(,( Φb- (t) Σ (T)
time + 1 is given by,
Pr(jd)r((1)
& (( + 1), u2 (t + 1)).
2

---

Under review as a conference paper at ICLR 2021
At each time step t, the algorithm generates samples {ū,(t)} from the posterior distribution N (t.(t), (f), guaranteed to have total regret at time T that not larger than O(d5/2/T) which is within factor of vd of the information-theom 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... 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).
plays the arm i that maximizes b(t)² (t) and updates the posterior. TS is
lower bound for this problem. It is also known to achieve excellent
LIMITED MEMORY NEURAL-LINEAN TS
Algorithm. Our algorithm is composed of four main components: (1) Representation: A DNN takes the raw context as an input and is trained to predict the reward of each arm; (2) Exploration: a mechanism that uses the last layer activations of the DNN as features and performs linear TS on top of them; (3) Memory buffer that stores previous experience; (4) Likelihood matching: mechanism that uses the memory buffer and the DNN to account for changes in representation.
To derive our algorithm, we make realizability assumption, which is similar to Assumption I The difference is that we assume that all the representations that are produced by the DNN are realizable. Assumption 2. For any representation o that is produced by the DNN, the reward for arm i at time t is generated from an (unknown) distribution s.t. E (t)((()()), Hz-1] = E (t)(t))(()) = o(t)"Mu, where {14 E ] are fixed but unknown parameters.
That is. for each representation there exist a different linear coefficients vector (e.g. l for Φ, 3 for vh.)) such that the expected reward is linear in the features. While this assumption may be too strong to hold in practice, it allows us to derive our algorithm as good approximation that performs extremely well on many problems. We now explain how each of these components works; code can be found in (link) and pseudo code in the supplementary (Algorithm (2).
1. Representation. Our algorithm uses DNN, denoted by Das, where w denotes the DNN's weights (for convenience. we exclude the weight notation for the rest of the paper). The DNN takes the raw context b(t) E HE as its input. The network has N outputs that correspond to the estimation of the reward of each arm, given context b(t) E Rd, D(b(t)); denotes the estimation of the reward of the i-th arm.
Using DNN to predict each arm's 's reward allows our algorithm 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 p(() = aasttlaaercctivationn raw measurements that can be high dimensional (e.g.. image or text), where the size of s(t) is design parameter that we choose to be smaller (g < d). This makes contextual bandit algorithms practical for such data sets. Moreover, d(() can potentially be linearly realizable (even if (() is not)
this
((b())), where ((t) E Rd. The context b(t) represents
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 P mini-batches. Training is performed by sampling experience tuples (b(T), a(T), (T) from the replay buffer E (details below) and minimizing the mean squared error (MSE),
LNN = (ID((()) (T)))
where ra(r) the reward that was received at time r after playing arm a(r) and observing context B(T). Notice that only the output of arm a(T) is differentiated, and that the DNN (including the last layer) is trained end-to-end to minimize Eq. (I).
2. Exploration. Since our algorithm is performing training in phases (every L steps), exploration is performed using a fixed representation è (D has fixed weights between training phases). At each time step I, the agent observes a raw context b(t) and uses the DNN D to produces a feature vector Φ(().
The features (tt) are used to perform linear TS, similar to Algorithm [ but with two key differences: (1) We introduce a likelihood matching mechanism that accounts for changes in representation (2) Instead of using a Gaussian posterior. we use the Bayesian Linear Regression (BLR) formulation that was suggested in Riquelme et al. (2018). Empirically, this update scheme was shown to convergence to the true posterior and cemonsttaaed excellent empirical performance (Riquelme et al. 2018).
In BLR, the noise parameter v (Alg. [ is replaced with prior belief that is being updated over time. The prior for arm i time t is given by Pr(ū,, i??) = Pr Pr(2))PPr(() [2?), where Pr ) is an inverse- gamma distribution Iny-Gamma (1), (()), and the conditional prior density Pr (2)) is a normal
3

---

Under review as a conference paper at ICLR 2021
distribution, Pr( b7 x N (fa(t), (t))()) Combining this prior with a Gaussian likelihood guarantees that the the posterior distribution at time T = 1+ is given in the same form (a conjugate prior), i.e., Pr(E.)) = Iny-Gamma| (A,(r); (T)) and Pr(ji[(e,) =N (f((T),)?,((TT)
In each step and for each arm E I..N,, we sample a noise parameter i? from Pr(if) and then sample a weight vector j., from the posterior N (A,, ( + +))) Once we sampled a weight vector for each arm, we choose to play arm a(t) = arg max,o(t) Jus, and observe reward (t))) This is followed by a posterior update step:
Pa(e) = Pa(e) + Pa(t) + =())(()), fa(t) = Sa(t) + +1(() Tt:
Pa(t) = (Pa(t)) (8 (Bav) + fa(o), 12(1)= = R2 1) +r²
t
1 (1) + (ma(()) T (l(o (1)) (t)
A.(1) = 40(0 + 2' B.(l)= Ba(o) 2
We note that the exploration mechanism only chooses actions; it does not change the DNN's weights.
3. Memory. After an action a(t) is played at time t, we store the experience tuple (b(t), Fa(e) (t) in finite memory buffer of size n that denote by E. Once E is full, remove tuples from E in round robin manner, i.e., 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 a subset of memory tuples in E at which arm i was played, and let my be its size. We denote by E gold E I= 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 RRx,9, Our approach is to summarize the knowledge that the algorithm has gained from exploring with the features gold into priors the new features Φ n.. Once these priors are computed, we restart the linear TS algorithm using the data that is currently available in the replay buffer. For each arm i, let o' = -E²),, )5 be the j-th row in E and let ry be the corresponding reward, we set $; - (of)) . = Ef= -)ー((())) (1)))
We now explain how we compute 8. L..44. Recall that under the realizability assumption we have that (f[r(t)) é(t) <ot)" μ4 = (old(t)* pight ((r Thus, the likelihood of the reward invariant to the choice of representation i.c. ((((t) u4, 12) ~ (o)old()) pigld v²). For all i, define the estimator of the reward as (t( <(t)" (t), and its standard deviation St, (1) (see Agrawal & Goyal 2013) for derivation). By definition of (t), marginal distribution of each (t) is Gaussian with mean Φ; (t)T (t) and standard deviation 14,1,,5. The goal is 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.::: The DNN is trained to minimize the MSE (Eq. 1D. Given the new features é, the current weights of the last layer of the DNN already make good prior for u.. In Levine et al. (2017). this approach was shown empirically to improve the performance of neural Tinear DQN. The máin advantage is that the DNN is optimized online by observing all the data and is therefore not limited to the current replay buffer. Thús, the weights of the current DNN hold information on more data and make a strong prior.
4.2 A Approximation of the correlation matrix Φ... For each arm i, our algorithm receives as input the sets of new and old features E,, Egels gots with elements (dold , } : In addition, the algorithm receives the correlation matrix Φolld Notice that due to our algorithm's 's nature, aeldd holds information on contexts that not available in the replay buffer. The goal is find a correlation matrix, $ for the new features that will have the same variance on past contexts hold Le.. want to find Φ such 67 ( وb = Trace ((0)) +5 ))
that Vi E [I..N]..j E [1..n:] 83,, = (Øg ( where the last equality follows from the cyclic property of the trace.
We denote by X, a vector of size n; in the vector space of d x d symetric matrices, with its j-th element X,,s to be the matrix o, Using this notation, we have that Note that Trace ((0?) (0))) = Trace(X") (b)) is an inner product over the vector space of symmetric matrices, known as the Frobenius inner product. Finally, as (4h))1 is an inverse correlation matrix, we constrain the solution to be semi positive definite. Thus, the optimization problem is equivalent to a linear regression
4

---

Under review as a conference paper at ICLR 2021
problem in the vector space of positive semi definite (PSD) matrices for all actions i [1..N]
minimize
Σ |TraceeXX X3, (0.) (((?))=)) 5,,l subject to (0?)-
(Ø = 0.
(3)
In practice, we solve the SDP by applying SGD using sampled batches from E Ex and E Each SGD iteration is followed by eigenvalues thresholding (denoted by Eigen Value T'hresholdin((() (())))))))))))))))) in order project (Ø$)- - back to PSD matrices space. To avoid evaluating E'J each time the DNN is updated. we take advantage of the iterative learning phase of the DNN and the iterative nature of the SGD by using the same batch to update the DNN weights and (Φ9)-1 simultaneously. In each iteration, we treat the inverse correlation matrix from the previous iteration as (Dold)-1 and also as the initial guess for the current gradient decent step. For each action a E A, we use a subset of the batch, in which action was used.
Lemma 1. The rank of a stochastic gradient of Ei= |Tacee [Trace(XX,. (7,((9))1) - s3,111. given a batch size is at most min (,gg g).
The proof can be found in the supplementary.
Computational complexity. We consider the time and memory complexity of the algorithm and their dependence on different parameters of the problem. Recall that the last layer's 's dimension is 9 < d where d is the dimension of the raw features, the size of the replay buffer is n and the batch size is B. Therefore, each gradient step is Bg² (matrix-vector multiplications) plus the thresholding operator, which has a time complexity of (gg") due the matrix cigendecomposition. This can be improved in the case of low-rank stochastic gradients (B= < g) into O(g²) suggested in Chen et al. (2014).
Let T be the number of contexts seen by the algorithm. The computational complexity of the full memory approach results is, therefore, )( and the memory complexity is O(T). This is because it is 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 and training the network/updating the priors in batch manner. This gives memory complexity of (1))
and computational complexity of O(T);; ; Due to the stochastic behavior of our SGD modification, the computational complexity is linear in the batch size and not in [A].
To summarize, our method is more efficient than the full memory baseline in problems with lot
of data (large T). Instead of solving an SDP after each update phase (which is computationally prohibitive in general), we apply efficient SGD in parallel to the DNN updates. This is also sample efficient due to the reuse of the same batch for both tasks. By setting the update frequency to I 1) and the number of iterations to I (P = 1), our algorithm becomes fully online in the sense it updates the DNN and the statistics each step. We use the fully online configuration in our experiments to show that even under extreme configuration, our algorithm produces competitive results.
EXPERIMENTS
In this section, we empirically investigate the performance of the proposed algorithm to address the following questions:
1. Can Neural-linear bandits explore efficiently while learning representations under finite memory constraints?
2. Does the moment matching mechanism allows neural-linear bandits to avoid catastrophic forgetting?
3. Can the method be applied in wide range of problems and across different DNN architec- tures?
We address these questions by performing experiments on ten real-world data sets, including a high dimensional natural language data on a task of sentiment analysis (all of these data sets are publicly available through the UCI Machine Learning Repository). In the supplementary. we include an additional experiments: synthetic data, where we observe that our algorithm can learn nonlinear representations during exploration and sentiment analysis from text, in which we evaluate our algorithm on text-based dataset using CNNs.
Methods and setup. We experimented with different ablations of our approach, as well as a few baselines: (1) Linear TS (Agrawal & Goyal 2013, Algorithm I using the raw context feature. with an additional uncertainty the varianic (Riquelme al. 2018). (2) Neural-Linear TS (Riquelme)
5

---

Under review as a conference paper at ICLR 2021
et al. 2018).
(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). (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. In all versions of our algorithm, we set P L = 1, which makes work in an online manner. In all the experiments, we used the same hyperparameters as in Riquelme et al. al.] (2018). E.g. the network architecture is an MLP with single hidden layer of size 50. The only exceptron is with the text CNN (details below). The size of the memory buffer is set to be 100 per action.
4.1 CATASTROPHIC FORGETTING.
We begin with an illustrative example on the Shuttle Statlog dataset (Newman et al. 2008), Each context is composed of 9 features deseribing the space shuttle flight. The goal is to predict the state of the radiator of the shuttle (the reward). There are k possible actions; for correct predictions 0 otherwise.
the reward is
and
Fig. shows the performance of each of the algorithms 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 instantancous regret (lower is better). For this experiment, all Neural-Linee methods retrained the DNN every I, = 400 steps for P 800 mini-batches, The cumulative reward achieved by each algorithm averaged over seeds (mean and std) can be found in Table 5| (Statlog); in Fig. D we focus on the qualitative behavior, as described below.
First, we can see that the neural linear method (green) outperforms the linear one (magenta), suggesting that this data set requires nonlinear function approximation. We can also see that our approach to computing the priors allows the limited memory algorithm (red) to perform almost as good as the neural linear algorithm without memory constraints (green).
We can also see that the two limited memory neural linear algorithms that do not calculate the prior for the covariance matrix (blue and teal) suffer from "catastrophic forgetting" due to limited memory. Intuitively, the covariance matrix holds information regarding the number of contexts seen by the agent and 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 (blue and teal); this is significantly reduced when we compute the prior on the covariance matrix (red), making the limited memory neural-linear bandit resilient to catastrophic forgetting.
Figure 1: Catastrophic forgetting
4.2 REAL WORLD DATA.
We evaluate our approach ten real-world data sets; for each data set, we present the cumulative reward achieved by each algorithm, averaged over 50 runs. Each steps. 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 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 (e.g., the mushroom data set has 22 categorical features that become 1 117 binary features). The DNN based methods performed better when the features were dense and high dimensional.
performed for 5000
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, 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 consistent with our reported cumulative reward (3000 out of 5000). Similarly, DNNs achieved around 60% accuracy, which indicates that the Covertype data set is 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 find this architecture to yield better cumulative reward. Similarly, for the Adult data set, lincar and deep classifiers were reported to achieve similar results (link) (around 84%), which is again equivalent to our cumulative reward of 4000 out of 5000. A specific DNN

---

Under review as a conference paper at ICLR 2021
Full memory
Limited memory. Neural-Lincar
Name
d
A
Linear (1)
Neural Linear
Both Priors
No prior (4)
NeuralUCB (5)
Linear Datasets
Mushroom
117
11022 774
10880 1: 853
11030 810
7613 1670
-102 84
Jester
32
14080 2240
12819:: 2135
11880 283
11114 + 2050
5373 7
Adult
88
2
40666. + 11.03
4010.0 22.19
4027 27
3608 34
3751 6
Covertype
54
7
3054 557
2898 + 545
2622 166
2334 = 603
1840.0 = 34.62
Nonlinear Datasets
Census
377
1791.5 d: 39.47
2135.5 51.47
2733.6 1: 76.15
1195
2103.2 12.76
Statlog
9
4483 353
4781 + 274
4797.7 = 48.21
3416 =
4190 + 13
Eppileptic
178
5
1202.9 +: 34.68
1706.9 41.26
1458.3 + 76
1411 33.43
1011 +
Smartphones
561
6
3085.8 + 24.64
3643.5 64.89
4328.5 + 81.75
1117 =
2733 + 713
Scania Tracks
170
4691.8 J. 7.23 2
4784 1. 6
4817.5 1. $41.89
4470.4 1. 37
4919.8 1. 193
Table 1: Cumulative reward of TS algorithms on 10 real world data sets. The context dim and the size of the action space A are reported for each data set. The mean result and standard deviation of each algorithm is reported for 50 runs.
was reported to achieve 90% test accuracy but did not yield improvement in cumulative reward. These observations can be explained by the different loss functions that optimize by the partial observably of the bandit problem (bandit feedback). Alternatively, competitions tend to suffer from paper Regret, on the other hand, is less prone to model overfitting because it is evaluated at each iteration and shuffles the data at each run.
overfitting in model selection (see the "reusable holdout" paper for more details (Dwork
2015)).
Inspecting Table 5] we can also see that on all datasets using our memory limited algorithm with prior computations (Algorithm 3), improved the performance of the limited memory Neural-L.nnarr in which the priors are not updated (Algorithm 4). Furthermore, on six datasets (Mushroom. Adult, Census, Statlog, Smartphones, Scania Trucks), Algorithm 3 even outperformed the unlimited Neural- Linear algorithm (Algorithm 2). We can also see that in five (out of five) of the nonlinear data sets, the limited memory TS (Algorithm 3) outperformed Linear TS (Algorithm 1, which online well). Our findings suggest that when the data not linear, neural-linear bandits beat the linear method, even if they must perform with limited memory. In this case, computing priors improve performance and make the algorithm resilient to catastrophic forgetting.
We also compare our algorithm against NeuralUCB (Algorithm 5 Zhou et al. (2019) with limited memory based on their offical code provided here). To make a fair comparison, we used the same network architecture. Also, NeuralUCB perform multiple network training iteration each step, while our online algorithm performs only one followed by SGD step. We can see that NeuralUCB is outperformed by our algorithm on almost all datasets (except one) and poorly perform on the linear datasets. We attribute this results the fact that NeuralUCB is based on NTK assumptions, which are not necessarily holds. Our likelihood matching technique can be seen as a fix between the NTK theory and applying it in practical problems.
5 RATE CONTROL FOR VIDEO TRANSMISSION OVER CELLULAR LINKS
The goal in this application is to control the sending rate of data segments sent over a cellular link, where the frequency of the changes to the sending rate should be low. In uplink video transmission the video encoder compresses the raw video into a stream of data to be transported. The encoder could adapt the video quality for near future throughput predictions, without inducing additional latency into the system. In this section, show that both representation and exploration are advantagcous on simulated cellular link, well showing resilience catastrophic forgetting.
We model the transmission rate control as contextual bandit problem. At step t, context b (t) E Rd revealed, which represents the current state of the link, and an action a(t) E A that controls the sending rate over the link is chosen by a policy. The action takes place for a fixed duration p (seconds), k(t) and a reward is presented afterward. Let (xx,)) i=1 be the sequence of acknowledged (ACKed) packets observed during step t, where ktt) is the number of ACKed packets during that step. Let (x) be the size (in MB) of packet æ, and (()) be the latency of packet in ms.
Context Vectors: Each context b(t) is a vector that contains information about the state of the link during the last h steps. After each step, we compute vector of three features u(t) that should
7

---

Under review as a conference paper at ICLR 2021
represents the state of the link at time f. Then, we construct the context b(t + 1) by concatenating (u(7)))==-A++ Specifically, for each u(() we measure the mean and variance of the latency values of the packets, and an approximation of the round-trip-time (RTT) by storing the minimal latency value observed over the last 100 steps. The values are normalized to keep the contexts bounded. The first context is generated by running the simulation for one step with a predefined initial action and
using u(t) =0 0 E RS, Vt < O. Actions: The set of actions (arms) A = {a:]== 1 N = 70 is set of evenly distributed values in the interval [Ntow; Anigh] C R such that 0D = Atous aN = Anigh, and V1 Si < N < d.+1. Each action value corresponds to a sending rate (in MBps).
Rewards: The reward signal is the total amount of data (in MB) that was transferred over the link with latency under 1y ms minus the total amount of data with latency over 7) during step t. Formally,
To = Ekit) a (Z.,e) 9n (zi,),, where (x,,)) = 1 when (Ir,1) < 17, and -1 otherwise.
Cellular Link Simulation: Many existing network simu- lators require significant resources (compute, time, human knowledge, etc.) configure even just a single simulation setup, limiting the ability to obtain a diverse set of links quickly. We developed a queue-baser simulation that re- quires only a few parameters and can model links with a wide range of behaviors. The simulation was designed to empirically fit patterns observed in data collected from uplink video transmission applications operating over real- world LTE networks. To make our agents more robust, during the training, randomly sample links every steps given some boundary constraints on the parameters domain.
CCumolattve Rewards Arzumalattd Through The Cource "hwining
1234
1084
Gsserme
Ieers-cies fallmeryyy
Liaar sCredd
200
We compared our algorithm to the following baselines: lin- ear TS, linear e-greedy, DNN e-greedy, unlimited memory neural-linear TS and a variant of the Additive-Increann (AIMD) control scheme, which is one of the dominant algorithms for congestion control. In our version of the algorithm. we control the sending rate at each step instead of controlling congestion window size. Our AIMD will increase the sending rate by 0.1 MBps if the mean value of the latency was under RTT+50ms, otherwise, the sending rate would be cut in half. We used the same DNN architecture for both the neural linear and DNN e-greedy bandits. The architecture consists of two fully connected hidden layers with ReLU activations sizes 128 and 32, respectively. For our algorithm, we used a memory buffer of size 2048. The other hyperparameters can be found in the supplementary material (Table 4).
Figure 2: Cumulative rewards of the vari- ous algorithms. The results are averaged over 15 seeds. Shaded area corresponds to a 95% Gaussian confidence interval.
Multiplicativ--eerraa
Fig. 2 shows that the neural linear bandit benefits from both the nonlinear representations of the DNN, which allow it to improve over the linear TS bandit and from the efficient exploration, which allow it to improve over the DNN e-greedy bandit. Both DNN bandits improved over their linear counterparts, which shows that nonlinear approximations yield better predictions in this problem. Also, both TS bandits improved over their e-greedy counterparts, due to their efficient exploration mechanisms. It can also be seen that the AIMD baseline was competitive and surpassed all but our neural linear bandit terms of cumulative rewards
6 SUMMARY
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 previous methods that store all the data in a replay buffer. The algorithm approximately solves an SDP using SGD, which enables it to efficiently operates online. Our algorithm demonstrated excellent performance on multiple real-world data sets and especially on challenging uplink transmission control problem. Moreover, its performance did not deteriorate due to the changes in the representation and limited memory. We believe that our findings make important step towards solving contextual bandit problems where both exploration and representation learning play important roles. A main avenue for future work to extend the ideas presented in this paper to Bayesian RL, where the immediate reward is replaced by the return, perhaps focusing on Markov decision processes with fast mixing time. An interesting future work would be to examine the effect of the network architecture on the performance of contextual bandits DNN-based algorithms such as ours and perhaps consider ways to choose the DNN architecture for contextual bandits problems as opposed to this work where the network's 's architecture is built for supervised learning, which in general may not be optimal for bandit problems.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yadkor, Y., Pal, D., and Szepesvari, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Agrawal, S. and Goyal, N. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pp. 127-135, 2013.
Auer, P. Using confidence bounds for exploitation-explorraion trade-offs. Journal of Machine Learning Research, 3970 2002.
Azizzadenesheli, K., Brunskill, E., and Anandkumar, A. Efficient exploration through bayesian deep q-networks. urXiv preprint arXiv: 0002. 2018.
Barron, A. R. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-94) 1993.
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T. Saxton, D., and Munos, R. Unifying count-based exploration and intrinsic motivation. Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Chen, J.. Yang. T., and Zhu, S. Efficient low-rank stochastic gradient descent methods for solving semidefinite programs. Artificial Intelligence and Statistics, pp. 122-130, 2014.
Chu. W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoft functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligncce and Statistics, pp- 204,211,77 2011.
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. The reusable holdout: Preserving validity in adaptive data analysis. Science, 64966248),666-63, 2015.
Goodfellow, I., Bengio, Y., and Courville. Deep learning. MIT press, 2016.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
Kim, Y. Convolutional neural networks for sentence classification. arXiv preprint. 2014.
Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A. A., Milan, K.. Quan, A., Hassabis, D., Clopath, C.,, Kumaran, D., and Hadsell, R.
J. Ramalho, T., Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, (1((13)3352-33333 2017. ISSN 0027-8424. doi: 10.1073/pnas. 161 1835114, 10.1073//mas.11118351111 URL
https::/ www. pnas. org/
Langford, and Zhang, T. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances neural information processing systems, pp. 817-824, 2008
Lattimore, T. and Szepesvári, C. Bandit algorithms. 2018.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. nature, 521(7553):436, 2015.
Levine, N., Zahavy, T., Mankowitz, D. J., Tamar, A., and Mannor, S. Shallow updates for deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3135-3145, 2017.
Mnih, V. Kavukcuoglu, K., Silver, D.,, Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Ried- miller, M., Fidjeland, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533, 2015.
Newman, D., Smyth, P., Welling, M., and Asuncion, A. U. Distributed inference for latent dirichlet allocation. Advances in neural information processing systems, pp. 1081-1088, 2008.
O' DDonoghue, B., Osband, I., Munos, R., and Mnih, V. The uncertainty bellman equation and exploration. International Conference on Machine Learning, 2018.
Osband, I,, Aslanides, J., and Albin, C. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 2018.
Pathak, D.,. Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, 2017.

---

Under review as a conference paper at ICLR 2021
Riquelme, C., Tucker, G., and Snoek,
J. Deep bayesian bandits showdown. In International Conference Learning Representations, 2018.
Russo, J.J., Van Roy, B., Kazerouni. A., Osband, L,, Wen, Z., et al. A tutorial on thompson sampling. Foundations and Trends R in Machine Learning, 11(1):1-96, 2018.
Silver, D., Huang, A., Maddison, C. Guez, A., Sifre, L.., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panncershelvam, V., Lanctot, M.. Dieleman, S., Grewe, D., Nham. J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 jan 2016. ISSN 0028-0080 083-.083..222 doi: 10.1038/nature 16961.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):255-294 1933.
Vandenberghe, L. and Boyd, S. Semidefinite programming. SIAM review, 38(1):49-955 1996.
Zahavy, T., Haroush, M., Merlis, N., Mankowitz, D. J., and Mannor, S. Learn what not to learn: Action elimination with deep reinforcement learning. Advances in Neural Information Processing Systems, 2018a.
Zahavy, T., Magnani, A., Krishnan, A., and Mannor, Is a picture worth a thousand words? deep multi-modal fusion architecture for product classification e-commerce. The Thirtieth Conference on Innovative Applications of Artificial Intelligence (IAAI), 2018b.
Zhang, Y. and Wallace, B. A sensitivity analysis of (and practitioners' guide to) convolutional neural networks for sentence classification. arXiv preprint arXiv: 1510.03800, 2015.
Zhou, D.,, Li, L.,, and Gu, Q. Neural contextual bandits with upper confidence bound- based exploration. arXiv preprint arXiv: 4xXh:1911.04466 2019.
10

---

Under review as a conference paper at ICLR 2021
7
PSEUDO CODE
Algorithm 2 Limited Memory Neural-linear TS
Set Vi [L, .., N] 40 Ld. Rr d
Od, 2 Odtdd f: 0l
Initialize Replay Buffer F., and DNN D
Define <(t) + LassLayyrActivvttonss(////
for 1= 1,2
do
Observe b(t). evaluate ((1)
Posterior sampling: Vi E [1,., N), sample:
(=((t) N (ja, 2² ( 0;)-1)
Play arm a(t) := arg max, o(t) (t))
Observe reward r2
Store (b(t), a(t), re) in E
if E is full then
Remove the first tuple in E with a(t) (round robin) end if
Posterior update:
+ Da(e) = aa()) + (())(1))) Sa(t) -aces + x(1)
Pa(t) (8a a(t) th (a(o))
@ (P21))2(0)) + Sa(o)
Update phase:
if (t mod -)=00 0 then
for P steps do
Sample batch (b), oy r3) 4=1 from
Compute old features (oold) 11
Optimize w V.LNN (Eq and compute new features {
(4))) (Ø + 4,)-1 [Initial guess for SGD)
for vi E N1 do
el + [dgldl aj = - føyla,= =
(DD)-1 Poojete(CrademmDccmm(((1111 oold a)
end for end for
update using buffer: for Vi E [I,.,, N] do
Use the current weights of the last layer of the DNN prior for 1
4 = -ー (0)) f. = (o)
end for end if end for
Algorithm 3 ProjeceeGGradientDeeett
Inputs: A PSD matrix, Ba14, B,
for lighd E Bata and Φ5 E B do Gradient step:
8) + (dold) Adgia
X, + (0,
A A- a (Tacee A) 53112
Projection step:
A < Value Value T Thresholding(4)
end for
11

---

Under review as a conference paper at ICLR 2021
Algorithm 4 Naive Limited Memory Neural-linear TS
Set Vi E [.... N $ = J. fr = 14, ON, 4; = Odand- S: = 0,
Initialize Replay Buffer E5, and DNN D Define (bt)) <- Lastt_ayerActiiations/ (D((t)))
for t 1, 2....... ..... do
Observe b(t), evaluate (6()
Posterior sampling: Vi E [1,..N]] N), sample:
[+(t) ~ (pc, (2) + -
Play arm a({)= == arg max, (.))
Observe reward T
Store (b(t), r(t), in E
if E is full then
Remove the first tuple in E with a(t) (round robin) end if
Posterior update:
Pa(e) = Pa(t) + o(t)o(t)) fa(t) fa(t) + r(t)Tr+
Pato) (a)()) Pa(o)) @D Pa + Sa(e))
if (t mod L) = 0 then
for Vi E [1,.., .] do
Evaluate old features on the replay buffer: E Eoo end for
Train DNN for P steps
Compute priors for new features:
for vi [1. do
Evaluate new features on the replay buffer: E
Solve for D6 using Eq. 3 with Ey, Et gona Bold
Use the current weights of the last layer of the DNN as prior for 4 + = Σド= (o TT (o)
end for end if end for
8 PROOF FOR LEMMA
Proof. We note that Xz.; (0))² is I-rank matrix. The stochastic gradient with re- spect to (#9)-1, computed from mini-batch of size B taken from Ey, of the loss term is " j.a( (T)))) s. By marking y/.s 2(Trace(XT, B
sf.). the gradient can be presented as a weighted sum of I-rank matrices: > K Therefore, the rank of the stochastic gradient most min B.
SENTIMENT ANALYSIS FROM TEXT USING CNNS
This is experiment on the " "Amazon Reviews: Unlocked Mobile Phones" data set. This data set contains reviews of unlocked mobile phones sold "Amazon.com" The goal is to find out the rating to 5 stars) of each review using only the text itself. We use our model with Convolutional Neural Network (CNN) that is suited NLP tasks (Kiml 2014; Zahavy al.) 2018b). Specifically, the architecture is shallow word-level CNN that was demonstrated to provide state-of-the-an results on variety of classification tasks by using word embeddings, while not being sensitive to hyperparameters (Zhang & Wallace 2015). We use the architecture with its default hyper-parameten standard pre-processing (e.g., we use random embeddings of size 128, and we trim and pad each sentence to 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 previous experiments.
(Github) and
In this experiment, the input dimension is large (R (RT*), we could not run linear baseline since it is impractical to do linear algebra (e.g., calculate an inverse) in this dimension. Instead, compare the proposed method neural-linear
e-grody
Neural-Lincar
Neural Lineur Limited Memory
2963.9 68.5
3155.6 + 34.9
3143.9 = 33.5
Table 2: Cumulative reward on Amazon review's
12

---

Under review as a conference paper at ICLR 2021
neratt
Figure 3: Representations learned on the wheel data set with 5 = 0.5. Reward samples (top), linear predictions (middle) and neural-liness predictions (bottom). Columns correspond to arms.
with finite memory with the neural linear TS
baseline and with an additional baseline that uses an e-greedy exploration scheme (which also not limited by memory). 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 Table we can see that the limited memory version performs almost as good as the full memory, and better than the e- e-greedy baseline.
10 NON LINEAR REPRESENTATION LEARNING ON A SYNTHETIC DATA SET
we adapted synthetic data set, known as the "wheel bandit" RRiquelme et al. 2018), to investigate the exploration properties bandit algorithms when the reward Is a nonlinear lunction of the context. Specifically, contexts I are sampled uniformly random in the unit circle, and there are
Setup:
possible actions.
One action as, always offers reward F's N (Mss σ), independently of the context. The reward of the other actions depend on the context and parameter 5, that defines d-circle ||~=|| < 8.
For contexts that are outside the circle, actions a,,.., 04 equally distributed and sub-optimal, with N(u, o) for Ps, [1.44].
For contexts that inside circle, the reward of each action depends the respective quadrant. Each action achieves r; N (Mi o), where μs 14 ji in exactly one quadrant, and μ4; = μ < μs in all the other quadrants, For example, μ1 jr in the first quadrant {x : ||>|| < 6, T2 > 0} and μr = elsewhere. We set μ 0.1, /4s 0.2, j = 0.4, a = 0.1. Note that the probability of context randomly falling in the high-reward region is proportional to d. For lower values of ö, observing high rewards for arms a,,.., 04 becomes more scarce, and the role of the nonlinear representation less significant.
We train our model on n 4000 contexts, where we optimize the network every 200 steps for P = 400 mini batches. The results can be seen in Table
Not surprisingly,
neural-lines approaches, even with limited memory, achieved better reward than the linear method (Table B)
Fig. presents the reward of each arm as a function of the context. In the top row, we can see empirical samples from the reward distribution. In the middle row, we see the predictions of the linear bandit. Since it is limited to linear predictions, the predictions become function of the distance from the 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), see that the DNN was able to learn good predictions successfully. Each of the first four arms
13

---

Under review as a conference paper at ICLR 2021
learns to make high predictions in the relevant quadrant of the inner circle, while arm 5 makes higher predictions in the outer circle.
Neural-Linear Lim- ited Memory
Linear
8=0.5
737.44 3.04
899.72 + 12.79
8=0.3
735.37 = 2.58
781.09 = 11.34
5=0.1
735.51 + 2.59
751.75 = 3.6
Table Cumulative reward on the wheel bandit
11 PARAMETERS FOR THE TRANSMISSION RATE CONTROL EXPERIMENT
Parameter
Value
120
16
2
N
70
Atom
0.01
Whigh
T
105
h
256
512
0.05
Learning rate
3e-4
Memory buffer size
2048
Table Hyper-parameters values for the experiment section
12
OLD RESULTS
Full memory
Limited memory, Neural- Linear
Name
Linear
Neural-Linear
Both
Prior
I Linear Datasets
Mushroom
117
11022 +
10880
10923
9442 + 1351
7613
Financial
21
8
4588 +: 587
4389 + 584
4597 597
4311 + 598
4225 + 594
Jester
128191:
10996 2013
11114
88
2
4066.1 = 11.03
4010.0 4: 22.19
3943.0 +: 54.29
3839.5 :: 17.63
3608.2 1 34.94
Covertype
2828
Nonlinear Datasets
377
9
1791.5
39.47
2135.5 + 51.47
2023.16 37.3
1873 + 757
1943.83 + 84.2
Statlog
4483
353
4781
285
Epileptic
178
5
1202.9 1: 34.68
1706.9 1: 41.26
1716.8 1: 60.44
1572.9
48.66
1411.0 1: 33.43
Smartphones
3643.5
Trucks
170
2
4691.8 = 7.23
4784,7 1 6.05
4742.0 4: 33.0
4698.0 :: 13.06
4470.4 + 37.9
Table 5: Cumulative reward
algorithms on real world data sets. The context dim and the size of the action space are reported for each data set. The mean result and standard deviation of each algorithm is reported for 50 runs.
14


Reviews:
[{"review_id": "aCDcv23Ltp8", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main contribution of the paper is the likelihood matching method for dealing with the catastrophic forgetting and save the memory usage. The empirical results demonstrate that the proposed method achieves good results comparing to other baselines.\n\nHowever, the paper has several issues, as discussed below.\n\n- The paper lacks the theoretical result on their algorithm. It is understandable that an algorithm based on DNN may be hard to analyze. But the NeuralUCB algorithm of Zhou et al. (2019) does provide a theoretical regret analysis, even though NeuralUCB is also based on a DNN. Therefore, at least some more discussions and comparisons are needed. What are the difficulties for the regret analysis comparing to NeuraUCB? In general, a more detailed comparison with NeuralUCB is needed, also see the empirical evaluation part below.\n\n- The realizability assumption (Assumption 2) on the DNN is quite strong. It requires that ANY representation \\phi produced by DNN is realizable, that is, have a corresponding unknown but fixed parameters \\mu_i that could generate the reward of i with representation \\phi(t) by a linear combination. The authors only mention that the assumption is too strong to hold in practice, but it does allow their algorithm to perform well in many problems. So what is the reason behind? is there any way to relax it and make it more reasonable? It is difficult to accept an approach that is based on an impossible assumption. I think this is linked to the underlying principle of the proposed approach. The DNN is part of the proposed algorithm that needs to be constructed and tuned from data, but when taking its last year for TS exploration, it seems that the authors are treating this entire DNN as given by the environment, as a transformation from the context b(t) to a representation \\phi(t), and thus making an assumption patterned from the Assumption 1 for linear bandit, which is entirely on the environment. This mixing of algorithm and environment creates the difficulty of both justifying the assumption and carrying out the analysis I believe. I hope that the authors could provide more discussions on this important point. Is there any way to alleviate this, such as considering a class of DNNs so that such a realizability assumption could be supported?\n\n- For the empirical comparison, the authors do not compare the NeuralUCB algorithm in Zhou et al. 2019. In fact, this paper already appears in ICML'2020. Since Thompson Sampling and UCB are two main approaches for stochastic MAB, it is important to compare the Neural-Linear algorithm of the current paper with NeuralUCB algorithm, both analytically and empirically. Moreover, I do not understand a result reported in Figure 2. In this figure, it shows that the Neural-linear TS with full memory performs much worse than Neural-Linear TS with finite memory. How could this be? To me the finite memory algorithm (proposed in the paper) is an approximation of the full memory version. It only gains in saving memory, but why could it also win in reward?\n\n- The writing of the paper is not entirely clear. Some technical parts of the paper is not easy to follow. For example, at the beginning of Page 4, it starts to use notations \\Phi_i and \\Phi^0_i, but they are not defined. Then \\Phi_i appears in Eq.(2), seemingly to be a definition, but \\Phi^0_i is still not defined. It turned out that at the end of this page, \\Phi^0_i is discussed as the correlation matrix connecting the new features with the old ones. But it still does not look like a solid technical definition to me. Without a clear definition up front on these key notations, it is very hard to understand the entire logical flow. Also, in line 3 of Page 4 mentions the noise parameter \\nu in Alg. 1, but there is no such parameter in the Alg. 1 pseudocode. I am guessing it is the v in the pseudocode. The authors need to provide rigorous technical definitions and the logical flow to help readers understand their approach. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RCLeEdHmO3w", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a neural-bandit approach using Thomson sampling for leveraging the DNN’s non-linear representation. There is a growing interest in using Multi-armed Bandits with DNN in an end-to-end learning fashion but the difficulty of the understanding how the representation is learned in DNN, makes this problem a very challenging and interesting one. The paper proposes one solution to consider explore-exploit tradeoff in the non-linear DNN space. There is still several unanswered questions in this paper and leave the readers with more confusion than clarify. This is not because the paper is not written properly but the topic is fairly new and a very few works have considered this problem setting. The likelihood matching seems interesting idea but I couldn’t find a reason whether it contributed to reward boost compared to using all the history. Some of the claims in the paper is demonstrated experimentally, not theoretically. Please clarify the following questions to understand the paper better. \n  \n### Major Questions:\n\n* The realizability assumption A2 doesn’t seems to apply here as the history of the decisions (stored in the replay buffer) is used to update the representation. \n\n* The paper says $\\mu$ is assumed to be fixed in this problem, even before the representation is known. As we update the representation,$\\mu$ for the new representation varies and cannot be fixed.\n\n* Memory is poorly used without any significance to past decisions that are somehow key to changing the reward distribution or representation or both.\n\n* Unlike in the earlier work (Zhou et. Al), no theoretical guarantees have been provided. As in the earlier work, Network width/depth based guarantees can be used to show how the representation affects the realization assumption.\n\n* It is unclear why Alg 3 with limited memory outperforms Alg 2 with Full memory (stores all the past decisions) on both linear and non-linear datasets (Mushroom, Financial, Statlog, Epileptic). Please clarify.\n\n### Minor Questions:\n\n* $\\Phi_0$ was introduced before explaining about the likelihood matching. I suggest moving the updates at the end.\n\n* It would be beneficial for the paper if an additional experiment on how varying the size of the memory buffer affect the cumulative rewards\n\n* The paper claims that the linear models work only for ”medium-sized” inputs (with around 1000 features) due to numerical issues. Can you provide any further analysis on this? Perhaps varying the dim d vs cumulative rewards for linear vs Neural linear would demonstrate this claim. If there is an earlier work that did this, the citation would suffice.\n\nI have read the author's comments and I stand with my previous rating. I believe the paper addresses an interesting problem but lacks sufficient analysis due to the realizability assumption A2 which doesn't apply for the given problem and the other reviewers feel the same way. Unlike in online learning and MAB, the memory used by the proposed Neural-linear bandit significantly deviates from the A2 assumption. These should have been analyzed empirically or theoretically to understand the impact of the past history on the regret. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "8LqK2_hA3eI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Online Limited Memory Neural-Linear Bandits\nThe presented paper suggests a method for neural linear bandits that use limited memory. The memory limit is introduced by forgetting past observations and fitting the likelihood of the data under moments constraints using a semi definite program. The paper presents an interesting approach to a relevant problem but lacks novelty. Moreover, the presentation of the paper needs improvement (i.e. figures are not readable and results should be highlighted better in the tables). The paper needs another pass to correct writing mistakes and errors in the mathematical formulas. \n\nIntroduction:\nRepresentation change -> representation changes\nThe are -> there are\nWhat do you mean by computational problems? \nPlease change the citation style (no parentheses)\nWhat do you mean by “patch-based”?\n\n\nBackground: \nFirst equation: what do you mean by \\sim? Is this rather \\propto?\nPlays the arm that maximises -> use \\tilde{\\mu} here\n\nLimited memory NL TS\nThe part on exploration is not clear, please improve readability\nInv-Gamma(a,b) you use a and b here (like action and context), please change notation\n\nExperiments: \nPlot is not readable\nTable would be better if best were highlighted in bold\n\nRate Control: \nPlot not readable\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a promising solution to a very interesting and challenging problem, and the authors have improved the paper during the rebuttal by adding an important missing baseline. However, all reviewers still agree that the paper currently lacks sufficient analysis that would be required to understand properly the implications of past history on the regret. More specifically, the fact that assumption A2 does not apply to the given problem raises questions that should be addressed before publication. Theoretical analysis was provided for previous similar work (e.g. NeuralUCB). Providing this for the proposed method would significantly improve the impact of this work.
Decision: Reject