An Empirical Study of the Neural Contextual Bandit Algorithms
Authors: Bowen Wei
Yiling Jia
Hongning Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Contextual Bandits
Neural Network
Neural Bandits

Abstract: Recent advances in representation learning have made significant influences on solutions of contextual bandit problems. Neural bandit algorithms have been actively developed and reported to gain extraordinary performance improvement against classical bandit algorithms in numerous papers. However, there lacks a comprehensive comparison among the existing neural bandit algorithms, and it is still not clear whether or when they can succeed in complex real-world problems. In this work, we present an inclusive empirical study on three different categories of existing neural bandit algorithms on several real-world datasets. The results show that such algorithms are highly competitive against their classical counterparts in most cases, however the advantage is not consistent. The results also reveal crucial challenges for future research in neural bandit algorithms. 

Under review as a conference paper at ICLR 2023
AN EMPIRICAL STUDY OF NEURAL CONTEXTUAL BANDIT ALGORITHMS
Anonymous authors Paper under double-blind review
ABSTRACT
Recent advances in representation learning have made significant influences on solutions of contextual bandit problems. Neural bandit algorithms have been ac- tively developed and reported to gain extraordinary performance improvement against classical bandit algorithms comprehensive comparison among the existing neural bandit algorithms,, and it is still not clear whether or when they can succeed in complex real-world problems. In this work, we present inclusive empirical study three different categories existing neural bandit algorithms on several real-world datasets. The results show that such algorithms are highly competitive against their classical counter- parts in most cases, however the advantage is not consistent. The results also reveal crucial challenges for future research in neural bandit algorithms.
numerous papers. However, there lacks a
INTRODUCTION
In recent decades, contextual bandit algorithms have been extensively studied (Langford & Zhang 2007 Chu et al. 2011) for solving sequntial decision-making problems. In such problems, an agent iteractively interacts with the environment to maximize its accumulated rewards over time based on the given context. The essence of contextual bandits is to balance exploration and exploitation under uncertainty. In practice, contextual bandit algorithms have wide applications in real-world scenarios, including content recommendation (Li et al.) 20100] Wu et al.) (216)), online advertising (Schwartz
al. 2017 7, Nuara et al. 2018). and mobile health (Lei al. 2017 Tewari & Murphy| 2017).
Linear contextual bandits, which assume the expected reward is linearly related to the given context features, have been extensively studied in literature (Auer et al.. [2002 |Ruseevichientong Tsitsik-
lis 2010 Dani et al.] 2008 Abbasi- Yadkori et al., [201]] Chu et al.] 2011). Though linear contextual bandit algorithms are theoretically sound and succeed in number of real-world applications, the
linear assumption fails in capturing non-linear relations between the context vector and the reward.
This motivates the study of generalized linear bandits (Li al., 2017; Faury et al., 2020 Filippi
et al. 2010) and kernelized bandits (Krause & Ong, 2011 Chowddhryyr & Gopalan 2017 Valko
jtt al. 2013). Recently, deep neural networks (DNN) (LeCun et al. (015)) have been introduced
learn the underlying reward mapping directly. (Riquelme et al.) 2018) developed Neurallineaa which applied a Bayesian linear regression on the feature mappings learned by the last layer of neural network and get the approximation of the reward via Thompson Sampling. (Zahavy & Mannor 2019) extended NeuralLinear by adding a likelihood matching mechanism to overcome the catastrophic Torgetting problem. (Xu al., 2020) proposed Neural-LinUCBB by performing explo-
ration over the last layer of the neural network. NeuralUCB (Zhou et al. 2020), NeuralTS (Zhang
al. 2020) and NPR (Jia et al.) 202T) explore the entire neural network parameter space to obtain nearly optimal regret using the neural tangent kernel technique (Jacot et al. 2018).
All the proposed neural contextual bandit algorithms reported encouraging empirical improvement compared to their classical counterparts or selected subset of neural contextual bandit algorithms. However, there still lacks a horizontal comparison among the neural contextual bandit solutions on more comprehensive real-world datasets. We argue, for practical applications, it is important to understand when and how neural contextual algorithm better suits a specific task. In this work, we provide extensive empirical evaluation a set of most referred neural contextual bandit algorithms on nine real-world datasets: six K-class classification datasets from UCI ma- chine learning datasets (Dua & Graff 2017), one learning rank dataset for web search, and two

---

Under review as a conference paper at ICLR 2023
logged bandit dataset for online recommendations. We choose LinUCB reference linear bandit algorithm against six selected neural contextual bandit algorithms: NeuralLinear: NeuralLineas LikelinoodMatthhngg, NeuralUCB NNeural-LnUCCE NeuralTS, and NPR. We evaluated all bandit algorithms under the metric of regret/reward and running time, as long as the model sensitivity to the choices of neural netowrk architectures and hyper-parameter settings. We conclude that in most cases, neural contextual bandit algorithms provide significant performance improvement compared the linear model, while in some specific cases, the advantage of neural bandits is marginal. Be- sides, the results demonstrate that across different datasets and problem settings, different neural contextual bandit algorithms show various patterns. In other words, no single neural bandit algo- rithm outperforms others in every bandit problem.
ALGORIHTM
In this section, we first introduce the general setting of contextual bandit problem, and then present the existing bandit solutions, including both linear and neural models.
2.1 CONTEXTUAL BANDIT PROBLEM
We focus on the problem of contextual bandits, where the agent iteratively interacts with the envi- ronment for T rounds. T is known beforehand. At each round, the agent will choose one arn from K candidate arms, where each arm is associated with a d-dimensional context vector: X, E R. Once the arm a, selected, the agent will receive the corresponding reward rtt,,, that generated as ft.a, h (xtt,,,) + 7/. where h is an unknown reward mapping and is e-sub-Gaussian noise. The goal of a bandit algorithm is to minimize the pseudo regret:
Ry = E Σ
(rea; - re.a))
(2.1)
where of is the optimal arm round with the maximum expected reward.
2.2 LINEAR CONTEXTUAL BANDIT ALGORITHMS
In linear contextual bandits, the unknown reward function 1(()) is assumed to be a linear function: l((x)a;)) x 0% where 0" E R& is the underlying unknown model weight. One of the most popularl linear contextual bandit algorithms is LinUCB (Li at, Abbasi- Yadkori et al. 2011). At each round t, ridge regression is applied learn the current model O, based on the observations collected so far,
0, = arg min
(Tr.er x, xx,,0)² 10
(2.2)
where is the coefficient of L2 regularization. Then, LinUCB pulls the arm with highest upper confidence bound:
{ xr + any XT A A. = AI E XT.o, x r.a,
Gr arg max aE(K]
(2.3)
where ae > is a scaling factor that controls the exploration rate. Once the reward of the pulled arm is received, the model will be updated to 0 By leveraging the width of confidence interval of reward estimation, LinUCB well balances the explore-cxploit trade-off bandit learning and obtains sublinear regret with respect the time horizon T.
2.3 NEURAL BANDIT ALGORITIIMS
Numerous attempts have been made to apply neural networks in contextual bandit problems, under the fact that neural networks remarkable approximators of any unknown functions (Cybenko, 1989). In the following sections, we categorize existing neural contextual bandit algorithms into three main categories based their exploration methods.
2

---

Under review as a conference paper at ICLR 2023
2.3.1 NEURAL NETWORK AS FEATURE MAPPING
The first category of algorithms treats neural networks as non-linear feature mappings and deploys linear bandit models on top of the learned mappings. (Riquelme et al. 2018 Zahavy & Mannor 2019) first introduced linear exploration policy on the last layer of neural network. Different from linear bandit algorithms where the feature mapping is stationary, neural- -ineer algorithms consider the feature mapping changes after the model update at each round.
The NeuralLinnerr algorithm (Riquelme et al. 2018) introduced fully-connected neural network to capture the non-linear relationship between input context vector and the reward. It applies the Bayesian linear regression on the last layer of the neural network (Snoek et al. 2015), and makes the decision via Thompson Sampling. The goal of the neural network is to find a good representation for Bayesian linear regression to predict the reward.
NeuralLinear.
At round i, the NeuralLinear algorithm learns the model by minimizing the mean squared error (MSE),
[(w) =
(2.4)
The exploration is performed by using Φe, the representation learned as the last layer of the neural network. After observing the raw context vector X,, the agent applies the neural network to learn a representation Φi. Then Φ; used to perform a Bayesian linear regression.
The agent computes the posterior reward of an action via linear function mapping: Tt = $ p. After observing r, the prior at time is updated by Pr(u, 2²) = Pr( based on the assumption that 22 ~ InæGammaa(c, by) and Pr(p(v²) x N(H (A A.)- where A, is defined over the history representations of input data.
Specifically, at each step, we sample the noise parameter 2² from Pr(v²) and then sample a weight vector fú from its posterior distribution N N(u,, (²(Ao + A,) With the sampled fú, we select the arm by 0e arg max $. j and then observe the reward rt. The parameters in Neurall.nnear are calculated as follows:
A: ( 1 Au)-1,
fr (A + $ R).
(2.5)
G = co + 1/2,
b. = by + (R
R + 0 AnO - 0, 0,)
(2.6)
where 140 0, Ao ALz, and A is matrix defined based the history representation of input data. In addition, 4 and R can be viewed as memory buffers storing the history representation data and reward, respectively.
NeuralLinear with Likelihood Matching. This algorithm (Zahavy & Mannor 2019) extends Neu- ralLinear with a small memory buffer to handle the catastrophic forgetting problem, which refers to the issue of drifting model estimation caused by the loss of information from previous experi- ence (Kirkpatrick et al. (017). At each round f, it stores the representation into a bounded memory buffer, which is denoted as E. When F is full, it will remove previous observation in a round robin manner.
The likelihood matching mechanism is to deal with the change of representation by using the DNN
and the memory buffer. Based on the posterior distribution O, ~ NoO,, ( A,) 1) the
marginal distribution of r, is (N, o,, 2?). where = Vo A, Φ, (Agraaal& & Goyal 2013 Thus the goal is to make the likelihood of given the new feature mappings consistent with given the old feature mappings.
After each training phase, new feature representation is denoted Es Raxm where n is the length of the previous action sequence and m is the dimension of the feature representation. Use Espura to denote the old representation before training. The likelihood matching approach summa- rizes the old representation into the priors of the correlation matrix A and the mean vector μe' under the new representation. The weights of the last layer of the neural network μ is a good approxima- tion of the mean St" because the neural network is trained online by holding the information of the entire observed data and therefore not limited to the memory buffer. For the approximation of the correlation matrix A 9, the goal is find A such that
3 Φ. (A
Φ -
Trace( Trace((A9)- (AA))1 (1),
3

---

Under review as a conference paper at ICLR 2023
where st ( the definition that Z₁ o Φi. the problem can be viewed as regression problem:
(old)) - Dold and the equality is based on the eyclic property of the trace. With
minimize (A9)
Σ (Trace((Z) A st)², subject to (A") 2 0.
The exploration step is similar to the NeuralLinear algorithm:
A, A 1 Φ Φ1. R R²- + r
L 1-1 Φire. re.
0: = (A + + vt),
= co + 1/2,
b. = ba + (R) + (T²) A 0, A,0.)
where Og is weight vector sampled from the posterior distribution, μr is the mean prior, and A is the prior of the correlation matrix.
NeuralLinUCB. neural network always have the number of parameters in the order of 100 thou- sands, which makes the exploration on the entire parameter space inefficient. The NeuralLinUCB is a combination of the Neurall and the NeuralUCB algorithm. introduces a neural network to learn deep representation and then performs UCB-batt --Beed exploration on the last layer of the neural network. In particular, the reward function is defined as the inner product between the weight of the last layer of the neural network and the last hidden layer representation, namely, r & 1111- Then (CB-based exploration is performed as follows:
arg max aE[K]
Φ 0.- + an A,A
(2.7)
where 0,-1 is point estimator of the unknown weight in the last layer, Φi is the representation learned as the last layer of the neural network and A, is a matrix defined based on the history representation of input data.
2.3.2 NEURAL TANGENT KERNEL BASED ALGORITHMS
Most recently, under the neural tangent kernel space, neural bandit algorithms are able to perform the exploration in the entire parameter space. In this category, a fully connected neural network f(-) is introduced to approximate the reward h(x),
f(x; 0) /m W W L-10 (xx))),,
(2.8)
where (2) ReLU(z), (ve((W1), ... vee (()) L)] IR,, with p as the number of parameters of all hidden layers of the neural network, and m + md + m²(L (L- - 1) with m as the width of the each hidden layer.
NeuralUCB. At round f, NCu learns the model by minimizing an La le-reuularized square loss,
(()) = Σ' (f(x.,:)) ) mAll0 0o13/2.
(2.9)
where the regularization centers at the randomly initialization 0p with the trade-off parameter A. In NeuralUCB, with neural tangent kemnel, proved that with a satisfied neural network width m, with high probability, the underlying reward mapping function can be approximated by linear function over gxx; 0o), parameterized by 0" l. where gxx; 0.) Vxf(x: 0g) IRd is the gradient of the initial neural network. Therefore, at each round, NeuralUCB selects the arm
at arg max
[(xx,aii 0--1) + a 1--1) A, a(xi,aa:00 0 0111)
(2.10)
aE(K]
where 04 positive scaling factor, 0,-1 the current parameter of neural network, and A, is matrix defined based on history gradient of the neural network,
A =
g (x,,,..: (o)g(xr...) 0o) /m + AL.
(2.11)
NeuralTS. The NeuralTS algorithm is similar to the design of NeuralUCB based on the neural tangent kernel technique (Jacot et al. 2018). Similar to NeuralUCB, NeuralTS learns the model
4

---

Under review as a conference paper at ICLR 2023
Table 1: Statistics of UCI dataset
DATASET
Mushroom
Covertype
Magic
Adult
Shuttle
Number of attributes Number of arms
22
54
11
14
9
2
7
2
Number of instances
8,124
581,012
19, 020
48,842
58,000
parameters by minimizing Eq equation 2.9 NeuralTSS explores the neural network parameter space via Thompson Sampling. where maintains a posterior distribution of the reward estimation for each arm. At each round t, for each arm, NeuralTS samples the reward from its posterior distribution,
Tt (x 0c-1),
(2.12)
where y is the exploration variance parameter, and of computed as:
0 Xg( 1--1) A, gXx,,a, 01-1),
with A, defined in Eq 2.11
2.3.3 PERTURBATION BASED ALGORITHMS
The third category of methods avoids explicit exploration by introducing controlled perturbations in the neural network. (Jia et al., 2021) introduced pseudo noise generated from zero-mean Gaussian distribution to the observed reward history, which eliminated explicit exploration in neural bandit algorithms.
NPR. At each round t, NPR updates the model by minimizing the loss function defined as,
(( Σ (f(x,..;))) (rr,a, + +7))) mX 0 0 1//
(2.13)
where (T.) ~ o0, are Gaussian random variables that are independently sampled in each round t, and is hyper-parameter that controls the strength of perturbation and thus the explo- ration. Because of the perturbation, the agent only need to select the arm with the largest estimated reward:
arg max (xa; 0:-1)
(2.14)
aE(K] where [xx 0c-1) the output of the neural network. NPR is proved obtain the same level of regret upper bound as other neural bandit algorithms.
EXPERIMENTS
In this section, we present the empirical evaluations of all the neural contextual bandit algorithms introduced in Sectior[] In particular, we report the results on five K-class classification datasets from UCI machine learning datasets (Dua & Grafi 2017). learning to rank dataset for web search: Web10K (Qin & Liu 2013). and two logged bandit datasets for recommendations: Japanese Fashion datasets (Saito et al. 2020), and Yahoo! Front Page Module dataset( et al. 2010).
3.1 DATASET AND EXPERIMENT SETTINGS
3.1.1 K-CLASS CLASSIFICATION DATASETS
We evaluate all neural bandit algorithms on five datasets from UCI machine learning repository. Specifically, we use datasets mushroom, covertype, shuttle, adult, and magic. These are K-class classification datasets, of which the statistics are presented in Table [ We adopt the disjoint model Li et al. (2010) to build the context feature vectors to generated K-armed pool:
X1 (x, ,,...,... .)..... X5. (O...., O, x) E 1dd The agent receives reward class is selected, otherwise O. Cumulative regret is defined as the total mistakes made by the agent over T' rounds. We report the averaged cumulative regret across 10 runs for 10,000 rounds, except for the mushroom dataset which only contain 8,124 instances in Figure [(a) to ((e) For neural
the correct
bandit algorithms, we apply 3-layer neural network with m = 16 units in each hidden layer and the model is updated every round.
5

---

Under review as a conference paper at ICLR 2023
Gran Ireech
300
Readtat
2503
2000
688
6018
1300
1200
6030
1000
0020
1000
(a) Adult
(b) Covertype
(c) Magic
J-0C3
1431
B-522
300
1233
Sec
Seaddts
1032
Mearafi22
340W
830
030
437
251
(d) Mushroom
(c) Shuttle
Figure I: Empirical results of regret and time consumption on UCI dataset.
3.1.2 LEARNING TO RANK DATASET
The MSLR- Web10K dataset is a public learning to rank dataset from Microsoft LETOR benchmark, contains 10,000 unique queries, each containing set of documents. Each document is associated with 136 ranking features and labeled with a relevance degree range from not relevant(O) to perfectly relevant(4). We treat the documents in each query arms. At each round, query and treat the corresponding documents as the arm pool. The regret is defined as the difference between the best relevance score of the arm pool and the selected one. our experiment, applied 3-layer neural network with m = 64 units in each hidden layer. Figure 3 shows the averaged regret across 5 runs for 150,000 rounds.
randomly select one
3.1.3 JAPANESE FASHION DATASETS
The Japanese Fashion datasets is set of logged bandit datasets collected from a e-commerce plat- form, ZOZOTOWN, The dataset was collected in 7-day experiment by using two different policies: random and bernoulli thompson sampling, iippling.ar It includes three "campaigns", correspond- ing to "ALL", "Men's" and "Women's" items, respectively. In our simulation, we only use the random collected dataset with "ALL" items, which contains 1,374,237 user-item interactions and 80 items. Each item has 4 features and each user is represented with 26-dimension binary feature vector. We generated the candidate pool as follows: we fixed the size of the candidate arm pool to k 25 for each round; for each user. selected the item according the complete observations in the dataset, and randomly choose 24 items from the item list. generated the context vectors by computing the outer product of user feature and item feature. In experiment, we adopted 3-layer neural network with m = 32 units in each hidden layer. Cumulative CTR is used to compare the performance of different algorithms, which is defined the number of clicks it obtains and the number of accesses it is received. To improve visibility, we normalized the cumulative CTR by random strategy's cumulative CTR, which is the algorithm's rel a CTR (Li et al. 20TO) We ran through the dataset times and reported the averaged relative CTR in Figure
3.1.4 YAHOO! FRONT PAGE TODAY MODULE DATASET
The Yahoo! Front Page Module dataset is collected in May 2009. In each observation, users were randomly selected visit small set of articles hand-picked from large article pool, where old

---

Under review as a conference paper at ICLR 2023
Soadir
Grad
Read
200
100
1000
8000
2010
2000
1830
1900
2008
2010
(a) arch: 16,16 freq:20
(b) arch:16,16 freq:100
(c) arch:16,16 freq:2000
Boadd
Srandh
(d) arch:32.32 freq:20
arch:32.32 10e
(I) arch:32,32 freq:200
Tear Bir
Yeart 112
(g) arch:64,64 freq:20
(h) arch:64,64 6,64 freq:100 100
(i) arch:64,66 freq::00
Figure 2: Sensitivity evaluation on the mushroom dataset.
LbcAc3 Neuro
Neur Kiner
Keuth Dove Ivovs hwv)
150000
50000
22060
10200
03030
00360
130000
122020 340002
(a) Web10K
Elapsed time
Figure Cumulative regret and time consumption on Web10K dataset.
articles will be replaced by the new ones after a period of time. The size of the candidate pool 20 on average.
treat the clicked articles for each user as positive feedback. We constructed the context vector by computing the outer product of user feature and article feature, the concatenating the outer product with the user feature and article feature. In our experiment, we select May01 dataset, which contains more than 4.7 million events. A 3-layer neural network with 16 units in each hidden layer was applied. Following the evaluation metric in Japanese Fashion dataset, we report the averaged Relative CTR across runs in Figure

---

Under review as a conference paper at ICLR 2023
16
64
(a) Japanese
(b) Elapsed time
Figure 4: Comparisons of relative CTR and time consumption Japanese Fashion dataset.
1.2
LayKS
10
Keuss Erer
hear
Neurs
0.2
166
(a) Yahoo
Elapsed time
Figure Cumulative relative CTR and time consumption on Yahoo dataset.
3.2 EXPERIMENT RESULTS
3.2.1 RESULTS OF K-CLASS CLASSIFICATION
Figure show the cumulative regret on K-class classification datasets. can be observed that Lin- UCB fails cannot capture the nonlinear relationship between the context vector and the reward. In contrast, thanks to the power of representation learning of neural networks, the performance is strongly boosted by neural models mushroom and shuttle datasets. However, the improve- ment on adult, covertype and magic is limited.
Although neural bandit algorithms show better or at least comparable performance the linear bandit algorithm, the variance of neural bandit models is much higher in Figure [(d) and [(c) which might be harmful in real-world applications. To further investigate the sensitivity of the neural bandit models, we evaluate three different neural architectures with
16, 32 and 64 units in each hidden layer, and three model updating frequencies: (20, 100, 2003. Due space limit, we report the result on the mushroom dataset in Figure 2 and leave the other four covertype shuttle le, magi c, and adu the appendix.
The performance of neural bandit models depends their converge speed. Reducing updating frequency slow down the convergence neural bandit algorithms. The NeuralLinear algorithm even fails to converge in most of the nine settings. Infrequently updating model parameters is not helpful for experiments on small datasets like these K-class classification datasets. Based on the results, conclude that increasing the width of the neural network helps models to converge and reduce the variance since larger neural networks can capture more information, and increasing the update frequency in the initial steps will speed up the convergence.
8

---

Under review as a conference paper at ICLR 2023
3.2.2 RESULTS ON WEB IOK DATASET
Figure Souure]sshon shows the averaged cumulative regret and time consumption of finishing 15,000 rounds on the Webl0K dataset. The neural bandit algorithms, except for NeuralLinear, consistently outper- form the linear bandit algorithm. However, the advantage of applying neural bandit models is not apparent, and the LinUCB algorithm uses almost half of the time less than most neural bandit algo- rithms. Among the neural bandit algorithmss, the NeuralLinear with LikelinoodMatching algorithm shows promising results with the least running time. The limited memory buffer seems efficient and can capture most of the valuable information of the historical data when running a large-scale experiment.
3.2.3 RESULTS ON JAPANESE FASHION DATASET
FigureIshows the averaged cumulative relative CTR and time consumption on the Japanese Fash- ion dataset. The performance is boosted by neural models. The neural bandit algorithms strongly outperform the linear bandit algorithm. Compared with the Web10K dataset, the Japanese Fashion dataset contains more information. It has two sides of features: the user feature and the item feature. The interaction of the user and item feature provides informative knowledge to the neural network, which helps it to capture more detailed information from the data. For time consumption, the Neu- ralLinear with LikelihoodMatching uses the least time to finish the experiment. At the same time, the LinUCB algorithm spends less time than all of the neural bandit algorithms. The NPR algorithm achieves the highest cumulative relative CTR, and the BeuralLinnCCS also performs well.
3.2.4 RESULTS ON YAHOO DATASET
provides the averaged cumulative relative CTR and time consumption on the Yahoo dataset. The linear bandit algorithm outperforms most neural bandit algorithms except the NeuralLin algorithm. As the tiny document and user features, we conclude that simple features might fail to provide helpful knowledge for training a neural model. The linear model is good enough to capture low-level information from a simple feature. We surprisingly found that the NeuralLinear with LikelihoodMatching algorithm used the least time among all of the algorithms, even faster than the linear bandit algorithm, while the performance is not bad. only used less than twenty percent of the time other neural bandit algorithms used, which is strong advantage in such large-scale dataset.
4 CONCLUSION
In this work, we provide an inclusive empirical study to investigate the impact on the performance of applying neural networks in contextual bandit algorithms. We found that the neural bandit al- gorithms can capture more nonlinear information and show promising results in most cases. The neural bandit algorithms might fail if the number of data is insufficient, like the datasets from UCI machine learning, or the context feature is too simple to provide enough knowledge to learn. The NeuralLinUCB and the NPR algorithm always perform the best among all neural bandit algorithms. In contrast, the NeuralLineal with LikelihoodMatching algorithm is the only one that can lever- age the performance and time consumption. Some neural bandit algorithms would prefer frequent model updating in the beginning of the experiment. It is worth investigating further and developing the neural bandit algorithms.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127-135. PMLR, 2013.
Peter Auer, Nicolo Cesa- Desa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(1):48-77) 2002.

---

Under review as a conference paper at ICLR 2023
Sayak Ray Chowdhury and Aditya Gopalan. On kemnliieed aamei bandits. In International Conference on Machine Learning, Pp. 844 PMLR, 2017.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourleenth International Conference on Artificial Intelligence and Statistics, pp. 208-2144 JMLR Workshop and Conference Proceedings, 2011.
George Cybenko. Approximation by superpositions a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 -14,,, 1989.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. lttpp:////acche ics. wci.ccic. edu.mmd/mmm
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In International Conference on Machine Learning, pp. 3052-3060. PMLR, 2020.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Yiling Jia, Weitong Zhang, Dongruo Zhou, Quanquan Gu, and Hongning Wang- Learning neural contextual bandits through perturbed rewards. In International Conference on Learning Repre- sentations, 2021.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Barnkk--Briiska,,, al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):351-33526, 2017.
Andreas Krause and Cheng Ong. Contextual Gaussian process bandit optimization. In Advances in neural information processing systems, pp. 2447-2455, 2011.
John Langford and Tong Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1))96-1, 2007.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553))36-4444 2015.
Huitian Lei, Ambuj Tewari, and Susan A Murphy. An actor-critic contextual bandit algorithm for personalized mobile health interventions. arXiv preprint 1706 2017.
Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual bandit approach to personalized news article recommendation. Proceedings of the 19th international conference World wide web, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Alessandro Nuara, Francesco Trovo, Nicola Gatti, and Marcello Restelli. A combinatorial-bant algorithm for the online joint bid/budget optimization of pay-per-click advertising campaigns. In Proceedings of the AAA/ Conference on Artificial Intelligence, volume 32, 2018.
Tao Qin and Tie-Ya Yan Liu. Introducing letor 4.0 datasets. arXiv preprint
2013.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprint arXiv:1802.09) 2018.
10

---

Under review as a conference paper at ICLR 2023
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Operations Research, 35(2):395 411, 2010.
Mathematics of
Yuta Saito, Shunsuke Aihara, Megumi Matsutani, and Yusuke Narita. Open bandit dataset and pipeline: Towards realistic and reproducible off-policy evaluation. arXiv preprint 0rXiv:2008.071466 2020.
Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-3) 2017.
Jasper Snock, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pp. 2171-2180. PMLR, 2015.
Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health, pp. 495-517. Springer, 2017.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309.60 6869,, 2013.
Qingyun Wu, Huazheng Wang. Quanquan Gu, and Hongning Wang. Contextual bandits in collabo- rative environment, In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 529 529-55295388 2016.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01780, 2020.
Tom Zahavy and Shie Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. arXiv preprint arXiv:1901.0860 2019.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010.00822 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 1 1449--11522 PMLR, 2020.


Reviews:
[{"review_id": "jh25yZ8NQV0", "reviewer": "Reviewer_Zjj4", "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": "This paper proposed a empirical evaluation of neural contextual bandits algorithms. ", "summary_of_the_review": "An nice empirical evaluation but no new message.", "strength_and_weaknesses": "I feel this paper is better suitable for a workshop paper rather than a full conference paper. This paper didn't provide any new algorithm / theory / dataset. The large body of approximate Thompson sampling algorithms (\"Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling\") are not compared. \n\nThe main criticism of neural contextual bandits algorithm is the mismatch between algorithm and theory. I feel experiments should carefully check if the assumption of NTK is not satisfied, will the algorithm still work?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RYJe1rms3t", "reviewer": "Reviewer_22TM", "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": "This paper proposes to investigate the empirical performances of neural contextual bandit algorithms. LinUCB is used as a baseline. The algorithms are tested on four type of problems: UCI classification dataset, MSLR-Web10K dataset, Japanese fashion dataset, and Yahoo front page dataset.\nThe conclusion of the paper is that in comparison to LinUCB, neural contextual bandit algorithms can capture nonlinear information.\n", "summary_of_the_review": "Rather than spending 5 pages to describe state-of-the-art, the author should accurately describe their experiments.\n________________________________________________________________________________________________________\nI thank the authors for their answers. \nI raised my score, but I do not vote for acceptance. ", "strength_and_weaknesses": "The empirical evaluation is made on several datasets. However, the authors spend 5 pages for describing the state-of-the-art, and that is a lot for a nine pages paper. Moreover, some of the described algorithms have pseudo-regret upper bounds, but they are not given. In the case of bandit algorithms, it is however a strong argument since they are often used in “cold start”.\nFinally, despite the fact that they are nonlinear contextual bandit algorithms, and some of them are cited (Kernel UCB, Generalized linear bandit), they are not tested. It is a pity, knowing that the main conclusion of the paper is that neural contextual bandit algorithms can capture nonlinear information.\n\nSome missed references:\nEfficient Bandit Algorithms for Online Multiclass Prediction, ICML 2008 (Banditron is the first attempt to use neural networks in contextual bandit problem)\nEfficient optimal learning for contextual bandits, UAI 2011 (oracle based contextual bandit)\nA Neural Networks Committee for the Contextual Bandit Problem, ICONIP 2014 (first attempt to use neural networks in contextual bandit problem that practically works).\nRandom Forest for the Contextual Bandit Problem, AISTATS 2016 (contextual bandit based on a non-linear model).\nTaming the Monster: A Fast and Simple Algorithm for Contextual Bandits, ICML 2014 (oracle based contextual bandit)\n\nMinor comment:\nDeep neural networks are not recent (page 1).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "PbXxamkKfDq", "reviewer": "Reviewer_qgBu", "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": "This paper provides an empirical study of the neural bandit algorithms, which are the type of bandit algorithms that combine the benefit of deep neural networks, along with the simplicity of the classical linear bandit algorithms. It chooses the linear model: LinUCB as the reference algorithm, and studies how the recently proposed neural bandit models, i.e., NeuralLinear, NeuralLinear-LikelihoodMatching, NeuralUCB , Neural-LinUCB, NeuralTS, and NPR compares with the reference, under different datasets. \n", "summary_of_the_review": "This paper studies an important topic, i.e., the empirical performance of various neural bandit algorithms. Extensive experiments are done, but the empirical results are not well-analyzed and summarized, which makes the empirical results very hard to digest. As this is a pure empirical paper, this aspect discounts the paper's impact a lot. \n\n-------------- After Rebuttal -------------\nIt seems my concerns are not addressed, so i will keep my score. ", "strength_and_weaknesses": "Strength:\n\n- Neural Bandits are popular bandit algorithms these days, with the representation power from deep models. These paper studies an important aspect, i.e., how different algorithms perform under various environments, which should be relevant to the community.\n\n- The paper is easy to read and follow.\n\n- I like the Section 2.3, which seems to provide a nice overview/summary of different neural bandit algorithms. \n\nWeakness:\n\n- I appreciate the authors' efforts on performing the experiments on various datasets, to verify the pros and cons of different algorithms. However, at least for me, Section 3 is not informative. The current structure seems like the following: introduce different datasets first, followed by the setup, finally summarized the results from the figures. The results seem only contain some facts without any analysis/reasoning about why certain algorithms perform well under this setting, even say hypothesis. It then would be very hard for the readers to learn from this paper. \n\n- There are actually lots of interesting aspects from the figures, but are not pointed out/analyzed by the authors. For example, it is kind of well-known TS performs better than UCB empirically. However, from Fig.2 and Fig.3, it seems not the case if we use the representation learned by neural networks as the contextual features. It would be great if the authors could digest and summarize the results in a deeper way, that would also increase the impact of the paper.\n\n- Though the number of datasets seems sufficient, I feel the scenarios it covers is limited. For example, it would be interesting to see the case, when the number of arms is large, this is pretty relevant for practical scenarios such as recommender systems. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4igYU9ehtGC", "reviewer": "Reviewer_sUDB", "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": "Authors compare multiple neural contextual bandit algorithms on multiple data sets along with non-neural baselines.", "summary_of_the_review": "Quite simply, if you can increase the number of datasets used to at least 100, I would accept.  Also great would be to quantify claims about when algo FOO is best with meta-data analysis.\n\nIf the response is something like:\n  * it would take too long to run the algorithms on a large number of datasets ... well ... that's important to know!\n  * there's no single architecture that works well on all the datasets ... well ... that's important to know!\n\nI strongly encourage the authors to continue this line of work, as previously stated, it is undersupplied in the literature.  However, you need to up your game: empirical papers require more comprehensive effort.", "strength_and_weaknesses": "Strength: \n  * This type of empirical investigation is important and undersupplied in the literature.  \n\nWeakness:\n  * Empirical evidence is conditional, so to draw broad conclusions, a massive number of datasets need to be used, e.g. Bietti et al [1] consider more than 500.\n\n> The neural bandit algorithms might fail if the number of data is insufficient, like the datasets from UCI machine learning, or the context feature is too simple to provide enough knowledge to learn.\n\nThe beautiful thing about using many datasets is you can do meta-data analysis, so instead of just saying something like this, you can quantify it (e.g., what properties of datasets allow one to predict which algo is best?)\n\n[1] https://arxiv.org/abs/1802.04064", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject