Robust Neural Contextual Bandit against Adversarial Corruptions
Authors: Yunzhe Qi
Yikun Ban
Arindam Banerjee
Jingrui He
Venue: NeurIPS 2024 poster (2024)
Keywords: Contextual Bandits
Neural Networks
Adversarial Corruption
Primary area: bandits

Abstract: Contextual bandit algorithms aim to identify the optimal arm with the highest reward among a set of candidates, based on the accessible contextual information. Among these algorithms, neural contextual bandit methods have shown generally superior performances against linear and kernel ones, due to the representation power of neural networks. However, similar to other neural network applications, neural bandit algorithms can be vulnerable to adversarial attacks or corruptions on the received labels (i.e., arm rewards), which can lead to unexpected performance degradation without proper treatments. As a result, it is necessary to improve the robustness of neural bandit models against potential reward corruptions. In this work, we propose a novel neural contextual bandit algorithm named R-NeuralUCB, which utilizes a novel context-aware Gradient Descent (GD) training strategy to improve the robustness against adversarial reward corruptions. Under over-parameterized neural network settings, we provide regret analysis for R-NeuralUCB to quantify  reward corruption impacts, without the commonly adopted arm separateness assumption in existing neural bandit works. We also conduct experiments against baselines on real data sets under different scenarios, in order to demonstrate the effectiveness of our proposed R-NeuralUCB.

Robust Neural Contextual Bandit against Adversarial Corruptions
Yunzhe Qi, Yikun Ban, Arindam Banerjee, Jingrui He
University of Illinois at Arrana-Champpiig
Champaign, IL 61820
fyunzheq2, y rikkub,,2,... arindamb, jingruii Maiuuiiiilllll inoiniois.......... edu
Abstract
Contextual bandit algorithms aim to identify the optimal arm with the highest reward among set of candidates, based on the accessible contextual information. Among these algorithms, neural contextual bandit methods have shown generally superior performances against linear and kernel ones, due to the representation power of neural networks. However, similar to other neural network applications, neural bandit algorithms can be vulnerable adversarial attacks corruptions the received labels (i.e., arm rewards), which can lead to unexpected performance degradation without proper treatments. As result, is necessary to improve the bustness of neural bandit models against potential reward corruptions. this work, we propose novel neural contextual bandit algorithm named R-NeuralUCBB, which utilizes a novel context-aware Gradient Descent (GD) training strategy to improve the robustness against adversarial reward corruptions. Under wver-parameterized neural network settings, we provide regret analysis for R-NeuralUCB to quantify reward corruption impacts, without the commonly adopted arm separateness as- sumption in existing neural bandit works. We also conduct experiments against baselines on real data sets under different scenarios, order demonstrate the effectiveness of our proposed R-NeuralUCB.
Introduction
Contextual bandits refer to one specific type of multi-armed bandit (MAB) problems, where the learner can access the arm context information during the decision-making process. Contextual bandit algorithms have been commonly applied in various real-world applications, including online content
recommendation [59 79 8) and medical experiments (30 73 77. While these algorithms have been proved effective for numerous online learning tasks, they can be susceptible to the malicious feedback from the environment, such malicious user feedback in recommender systems (64], and corrupted labels under active learning settings [61]. This can potentially impair the model performance and interfere with the internal decision- making logic. One renowned research direction formulates this problem as contextual bandits with adversarial corruptions [57 42 [6], where received arm rewards can be potentially "corrupted" by the unknown adversary. In this case, bandit algorithms need be robust against such adversarial corruptions, otherwise they can lead to sub-optimal results. Existing
works on contextual bandits with corruptions are mainly based on linear [17 29 57 and kernelized bandits [15 [6], where the unknown reward mapping function is assumed to be linear, or lies in a specified Reproducing Kernel Hilbert Space (RKHS). However, one key challenge is that these assumptions can evidently fail under real-world application scenarios (86), when we have little prior knowledge regarding this mapping function, or becomes increasingly complex.
have been proposed to relax the assumptions on reward functions. By leveraging the representation power of neural networks, neural contextual bandit algorithms are able to deal with complex reward functions irrespective of whether
In the face of this challenge, neural bandit algorithms 86 84
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

they are linear or non-linear, along with suitable exploration strategies for tackling the exploitation-
exploration dilemma [ [5]. While neural bandit algorithms have been proved effective ( 68 60], they can be sensitive to adversarial corruptions as well. From perspectives of trustworthiness, it is
well known that neural models can be susceptible to "label attacks" [71 62 65], which is akin to
reward corruptions in bandit settings. Failure to comply with robustness requirements can impair the
feasibility under real-world application scenarios like recommender systems [82 27
87 78 and
therefore is necessary for neural bandit methods to be robust against potential adversarial corruptions. Furthermore, existing neural bandit works generally require arm separateness assumptions (e.g.,
assuming desstive-definte Neural Tangent Kernel [NTK] Gram matrix [86] 84 26], or positive arm Euclidean distances [T] (7), which will require no duplicate arm contexts are observed (or chosen) by the learner. This can lead to additional vulnerabilities when arm contexts are intentionally
chosen by the adversary (e.g., assigning duplicate arms in the candidate pool across different rounds), making the arm separateness assumption fail in such adversarial environments.
Motivated by aforementioned challenges, in this paper, we propose a novel neural contextual bandit algorithm named Robust Neural-UCD (R-NeuraLUCB), which can model the discrepancy among candidate arms and adopt arm-specific context-aware Gradient Descent (GD) to enhance model robustness against reward corruptions. Instead of applying ordinary GD to update the network parameters, R-NeuralUCB utilizes a fine-grained GD strategy by modeling the importance level of training samples, to reduce the impact of potential adversarial reward corruptions. Meanwhile, to improve the model performance from both the theoretical and empirical perspectives, R- R-NeuralUCB simultaneously perceives the uncertainty levels of candidate arms, and adaptively customizes network dilemma, R-
parameters for each of these candidates. To deal with the exploitation-explrre UCU is equipped with informative exploration mechanism based on Upper Confidence Bound (UCB) to achieve principled exploration. In addition, we present regret analysis without the commonly adopted arm separateness assumption, which reinforces R-NeuralUCBB ' theoretical robustness under adversarial scenarios. Our contributions can be summarized as follows:
Problem Settings and Proposed algorithm: We study novel neural bandit problem, where the received arm reward can be potentially corrupted by the unknown adversary. To deal with this problem, we propose a novel neural bandit algorithm called R-NeuralUCB, which leverages a refined context-aware Gradient Descent training strategy to improve the model robustness against potential arm reward corruptions. While we consider all the observed arms are governed by the same unknown reward mapping function as in (T) similar to existing neural bandit works, our R-NeuralUCB interestingly maintains separate model parameters specific to the different candidate arms, for fine-grained way of improving the robustness. This casts lights on our contributions of novel algorithmic designs, compared to related existing methods without an arm-specific modeling (e.g.. 42 and our base algorithm NeuralUCB CGGG in Appendix E
Theoretical Analysis: With over-parameterizee neural networks, we present the regret analysis for R-NeuraUUCB. Given finite horizon T, effective dimension of NTK Gram matrix d, and corruption level C, R-NeuralUCB enjoys a data-dependent regret bound of O(d/T + Cd). In addition, to ensure R-NeuralUCB is capable of handling contexts specified by the adversary (e.g., duplicate arms across different rounds), our analysis removes the arm separateness assumption dependency, a widely adopted assumption for neural bandit literature, which can be of independent interest.
Experiments: We conduct experiments on publicly available real-world data sets with various specifications. Under different types of reward corruptions, our R- R-NeuralUCB can achieve better performance, and less vulnerable to reward corruptions than baselines.
2 Related Works
Contextual Bandits with Adversarial Corruptions. To begin with, there have been numerous
studies (76) 17 29 (57 63 31
22
54] working on tackling adversarial reward corruptions under
linear contextual bandit settings 59 24]. A related topic is bandits with missspecifiiations [36] 35]
33
53 83 75 where the deviation of reward estimation comes from problem modeling instead of
the adversary. On the other hand, kernelized bandits [5 40 16] extend the adversarial corruption
problem to non-linear cases by assuming the reward mapping is a functional in the specified RKHS
(72, while comparable ideas are also applicable for robust Bayesian Optimization (52] Adversarial
corruptions are also studied for other formulations, such as Lipschitz bandits 49 89 and MAB
without contexts [8] 80 However, compared with neural bandit methods, these works generally
require assumptions the reward function prior, which may not be satisfied in real-world scenarios.
2

---

Neural Contextual Bandits. Neural contextual bandits algorithms are proposed to leverage the representation power of neural networks, and relax the assumptions on the reward mapping functions
that can be linear or non-linear. Neural-UCB [66] applies fully-connected (FC) neural network for
reward estimation and utilizes corresponding network gradients for principled exploration. Com-
parable ideas have been leveraged by other neural bandit works [84] [5) 25 10
37,
46 9 60 11].
and adopted under various application scenarios such as active learning [74] 13 6 and bandit-based
graph learning [66, 67 [5]] with graph neural networks 77 34 35 Alternatively, [8] utilizes
the neural network to embed original arm contexts for regression. [26] utilizes inverse reward gap for exploration, and [48] achieves exploration with the reward perturbation. However, as these methods are not designed to defend against reward corruptions and widely require arm separateness assumptions, they can fail to meet the robustness requirements in adversarial environment.
Problem Definition
Let T be the finite horizon. In round E [T], the learner receives K candidate arms X, | K, and each arm Big E Xr with arm index E [K] is described by a d-dimensional vector Vi, E IRd. The learner will then choose one arm at, E X₂ and receive its reward rt. The index of at denoted by it E [K], s.t. 2, Fi.t. Here, similar to existing works (e.g., [42] [6] 13 86 (44) ), define corruption-free arm reward Fs, for each candidate arm D E Nc, as well as corrupted arm reward rt for chosen arm 2, Xx as
Fi.e = h(x.s,) + G...
Cs = F2 + C. = h(x1) + q +
where h : Rd + R is an unknown reward mapping function that can be either linear non- linear. 6/, E stands for zero-mean u-sub-Gaussian random noise which standard for stochastic contextual bandit works (e.g., [24 72 86)), and ot IR is the unknown adversarial corruption imposed by the adversary. While kernelized bandit works (c.g.. [16 (22) assume h()) belongs to the RKHS induced by specified kernels, we alternatively consider h(-) an arbitrary unknown function, and utilize the neural model to learn this mapping with flexibility.
Taking expectation w.r.t. zero-mean noise c, for the chosen arm I; E X, we denote its expected perturbed reward E[r,] = h(xx,)) + c; meanwhile, for each candidate arm Fi X,, its expected corruption-free reward B[Fi.r] h((ss.)) Here, we consider E[r] and E[]] both fall into value range
[0, 1]. analogous to existing works (e.g., [86] 84 II 50)). This is intuitive as numerous real-world applications work with bounded rewards (e.g., online recommendation tasks with normalized rating [67] or binary feedback (24)); and the adversary also needs its attack to be stealthy. by ensuring perturbed rewards fall into the normal value range. With previously chosen arms {xr ]re(s] up to round f, we denote received context-reward tuples with perturbed rewards as P. == fr brey = {ar,.r: Fi..r }re(t), and the corresponding context-reward tuples with corruption-free rewards as P. = {a,, Fr]re((] ( Fir.r hre(t), where each corruption but imaginary unobserved
reward is 7, h(z,) G,, [t] based on (I).
Learning Objective. Our objective is to minimize cumulative pseudo-regret for rounds:
Σ T
R(T)
E -rt,,
where Elrd = h(x;) is the expected corruption free reward of the chosen arm xt Xx and Blril exx,, [h(2 (xxx,))) stands for that of the optimal arm 2; E X,.
Corruption Level. If the adversary determines the reward corruption C, for each candidate arm Li E Xr beforehand, without observing the learner's choice æt, some works (e.g.. (38) formulate
the corruption level measurement as C' [ [[]] |e.el] In this work, similar to 42 16).
we alternatively consider reward corruptions are determined w.n.t. particular chosen arms {æ.hee and formulate the corruption level as C Exerry /cc). This leads to C < C².
4 Proposed Algorithm: Robust Neural-UCB (R-NeuralUCBB
Recall that in ① arm rewards under neural bandit settings are governed by the unknown reward mapping function it-),, where ht-)) can be an arbitrary function. For our proposed R-NeuralUCB, we adopt a neural network f-)) to approximate h(-) for reward estimation.
Network Structure. We use [(; 0) to denote an FC network with depth 2 2 and width m E N
f(x; 0) 1o 0 ( (00
3

---

Table 1: Comparison of T -round regret bounds with adversarial corruption level C.
Algorithm
Reward Function
Corruption C'
Regret Bound"
Robust OFUL.
76
Linear
Known
oldVT + ΣT Ei-1
CW-OFUL
Linear
Known
O(dVT + Cd)
COBE + OFUL 76
Linear
Unknown
Ö(dvT + V T 1i
CW-OFLT.
Linear
Unknown
O(dvT), & vT. Otherwise (IT)
Fast-slow GP-UCB 15
Kereeiizdd
Known
ÖldvT + CdvT)
RGB-PE 16
Kernelized
Known
OldvT C
Fast-slow GP-UCB
15
Kernelized
Unknown
OldyT CCvT)
BouralUCB-WGD (Tmm. E
Arbitrary
Known
O(dvT C//2)) C
R-NeuralUCB (Thm.
5.6
Arbitrary
Unknown
d: context dimension; d: NTK matrix effective dimension kernel information guin; 8: data- data-dependent gradient deviation
where a-) is clement-wise ReLU activation, and we have trainable weight matrices 01 E xg 0, E | 2 S L- 1, O E IR' I Xm, For the ease of notation, we denote vectorized parameters
0 == |vec(0,) (01)², vec(O2)"........ O7]T E RP,
with the dimensionality of p. and randomly initialized parameters are denoted by Op. Then, we let g(æ; 0) vec(Vof(a 0)) I2' be vectorized network gradients w.r.t. input and parameters 0.
We motivate our proposed R-NeuralUCB by first mentioning base algorithm named Neural- UCB with Weighted GD (NeuralUCB-WCG) WGD), which is elaborated in Appendix E To begin with, NeuralUCB-WGD measures the uncertainty level of training samples (i.e., previously received arm- reward pairs) through their UCB values, the UCB essentially measures arm uncertainty levels in terms reward estimation 24
72 86 Then, different from conventional neural bandit methods that treat all training samples equally [86] 84), inspired by 42 NeuralUCB-W CGD utilizes a weighted GD process to train neural model f()) for estimating arm rewards, where training samples with high uncertainty levels will be downplayed. The main idea is that although we do not know which training samples are corrupted, we instead aim to reduce potentially severe impacts caused by adversarial conuptions,, by paying relatively more attention the training samples (arm- curn-reward pairs) with low uncertainty levels, for stable GD training process. We also present corresponding regret analysis for NeuralUCB-We WWD in Appendix E.2 well as experiments in Section 6
However, notice that the neural model will also perceive varying uncertainty levels for different candidate arms in terms of reward estimation. In this case, simply applying the same exploitation- exploration strategy across all candidate arms can overlook this discrepancy, leading to insufficient granularity w.r.t. reward estimation. For instance, regarding candidate arms with low uncertainty levels, it can be more beneficial to adequately leverage existing training samples for estimating their rewards, instead of sharing an identical eeploitation-explraaaeee candidate arms. Meanwhile, analogous to existing works (e.g.. [2 16 15)), NeuralUCB. WGD supposes a known corrpption level C' for regret analysis (Theorem E. which can be difficult to satisfy if we have limited knowledge regarding the unknown adversary. With the above motivations, we propose NeuralUCB as refined solution further enhance neural model robustness against potential reward corruptions. For readers' reference, we also compare our proposed R- R-NeuralUCB and NeuralUCB-We BDD with some regret results from existing works in Table [
strategy with other high-uncertainty
4.1 R-NeuralUCBB Robust Neural-UCB
Our R-NeuralUCB formulates a novel context-aware GD process, by taking the uncertainty infor- mation of both candidate arms and training samples into account, for neural network training and decision making. Here, R-NeuraIUCDD customizes individual sets of network parameters 0 0,,-1 for each candidate arm I.,e E X₁. i E [K]. before the actual arm recommendation. Afterwards, these arm-specific networks are applied for arm reward estimation, along with an informative arm-specific UCB-based exploration mechanism. The pseudo-code is presented in Algorithm !
Arm Weight Formulation.
Inspired by NTK-based exploration mechanisms [86] 51 66
84).
we measure arm uncertainty levels with the weighted gradient norm of arms. With a regular- 0, we first define a weight-free gradient covariance matrix Σ,1
ization parameter
+ Σrek-1) (wr;; (0-1))((2:: 0,-1) Here, - is the shorthand of 0 - representing
the network parameters of the previously chosen arm H, TT T E |t 1]. Then, for each

---

Algorithm Robust Neural-UCB (R-NeuraIUCB)
1: Input: Time horizon T. GD iterations J. Learning rate 1/. Exploration coefficient u. Scaling
parameter a. Norm parameter S. Regularization parameter X.
2: Initialization: Parameters 0n. Weight-free covariance matrix Eg = AI. Records Po = 0.
3: for each round E [T'] do
4: Observe collection of K candidate arms 2₂ [at,))
5: for each candidate arm 2i, E X₂ do if t equals to 1 then
6:
7:
02,--1 < 0g.
8:
else
9:
With arm weights {wi, /]] in 4 train parameters 0i with GD and the arm- specific loss function in based on received records Pt-1-
10:
end if
11:
For candidate arm Ti,t, calculate its benefit score ( based on 66
12:
end for
13:
Choose arm 2₁ = arg r [U(x..)) with the highest benefit score.
14:
Receive arm reward rt. and update the records, such that Pa +- Pa-1 (.),
15:
Update the shorthand 0 0s,,-11, and matrix Eg t Σ,- + g 01-1)g(x 02 TT
16:
end for
candidate arm 2 E Mr, we formulate its weight w.r.t. previously chosen arm 2,, T E wt 1] as
min [g(:; 0.- =cXi
m
(T) iit
min
(4)
9r (1 11-1)/ v m
\ (m)
with x² scaled covariance matrix being 5(n) = AI + x2
(z, 0 0f
for a constant K E (0, 1). Alternatively, we also denote w//7 = min { [1.a frac, (I,,;: N, Σ 1) }. with frac.(-) being shorthand that integrally represents the fraction term in A tunable parameter and the squared round-wise minimum weighted norm min [0: -,) /ml : the numerator are applied for scaling purposes. We also include complementary discussions for arm weight scaling in Appendix B.5 Meanwhile, we have 9- [1g 0.- (oo [t-]]
(= quantifying uncertainty levels of previously chosen arms (training samples) motivated by UCB-based exploration strategies (e.g.. (2)). Since previous {g- ]-e[t-1] values can be reused, we only need to compute and store for current round t. As a result, if candidate arm æ; is of high uncertainty re((--1]
(i.e., large l[g (x.,,,;; 0;-1)/ s-- value), arm weights (w(()))((-))
will become small.
Model Training with Context-aware GD. According to line 9 in Algorithm T we perform model training before the actual arm recommendation in each round E (2,..., T) For each candidate
Ri, E Xe, we train its arm-specific parameters 0,,-11 with J iterations of GD and received records Pt- ((x,, ry rE(t-)(- Starting from initialization ((0) On. we have j-th GD iteration G E [J) being 0,-11 = 0---
(P--1;; where > refers to the learning rate.
We formulate loss function (, [K] specified to candidate arm Fi,t E X, as
w!?7 (7) [xx;; - r,,] 2
(pp(P:1:)))= Σ (
ml
0 00112:
(5)
where the Ly loss is scaled by arm weights (7 r [t - 1] from ( Intuitively, if arm weights (r(r) are large (i.e., low uncertainty level), we proceed to train a neural model that adequately fits the collected training data (i.e., previously received records) P,-1, instead of staying around the random (r) initialization Ou given the L, regularization. On the other hand, if arm weights wie are small, it means that the uncertainty level terms of reward estimation high. In this case, we prefer being relatively conservative to prevent potentially large impacts caused by adversarial corruptions. As result, R-NeuralUCB will focus more on the training samples in P.-1 with low uncertainty levels, and stay relatively close to the random initialization d, due to the regularization term in (
5

---

In practice, instead of starting from dg in each round t E (2...., we can alternatively initiate the GD process from the existing trained parameters to reduce computational cost, inspired by the concept of warm-start GID
13 Here, we can start from 0:-2, the parameters of the previously chosen arm 2; and fine-tune arm-specific parameters 0,,--1 for each candidate arm Fi,t E X,, based on its loss function c (,, .) and a small batch of samples from Pt-1- Further details are
elaborated in Appendix [.6] and this approach is also applied for the experiments in Section 6
Arm Selection. For candidate arm Fi,t E X2 and arm weights (wi,7 Jre[e-1], we formulate its arm-
specific gradient covariance matrix Σ = AI + Erett-1 Witt "9(;;; 00);)((1;;; 0 1 //m. Here, if the variance proxy value v in [ is unknown, similar to existing works (e.g., [86 84) ) we deem v 0 as a tunable parameter to control the exploration intensity. With our UCB-type exploration motivated by Appendix Lemma C.II. we formulate the benefit score for arm Fi, E A. as
U ( = ff f( 12.-11 + 7 v glwrr 01,--1) (ar,, 0i,,-1/mm,
(6)
/ det(E...-)) 2 log(d) + vĀ5). along with a where the confidence coefficient "Ma-1 = S. (v log dou(A)
constant < >> 0 from Lemma C.11 Afterwards, we choose D2 = arg Ex, [+:) (line 13, Algorithm| T), based calculated arm benefit scores in (6). After receiving reward rr. the collected records will be updated by P. +- -P-1 {( rt)) (line 14, Algorithm D. We also update the shorthand for model parameters of the chosen arm as 0 f 0,, and the weight-free free covariance matrix Σn < Σ.-1 g( 1)g (z;; 1t-1) //m for next round + 1 (line 15, Algorithm D
In summary, the primary goal of R-NeuralUCB is to customize individual learning objectives (i.e., loss functions) for different candidate arms by leveraging arm uncertainty information before pulling an arm. For candidate arms with high uncertainty levels, the neural model may lack confidence in estimating rewards based current records, due to potential reward corruptions, which can lead to significant estimation errors. In this situation, by using the regularization term "/= ||0 0o we prefer to adopt a relatively conservative approach, training a model close to random initialization to mitigate the potentially large impacts of adversarial corruptions. This approach is inspired by existing work on enhancing model robustness through regularization techniques (e.g.. (69 23 ). On the other hand, for candidate arms with low uncertainty, we aim to train neural models that fully utilize the received records for reward estimation. Since the model is confident in its estimation, the received samples can provide adequate reference. With larger arm weights, the loss function can focus more on the training samples, instead of staying closely around 0..
5 Theoretical Analysis
To the best of our knowledge, we provide the first theoretical results under the neural bandit settings with adversarial reward corruptions, and our proof flow is distinct from those of linear and kernelized bandit works. In particular, as our ReLU activation in (3) is not Lipschitz smooth 3 21, it leads to additional challenges for our theoretical analysis, since small perturbation on rewards can lead to drastic changes of network gradients. As a result, even with a small corruption level C., the corrupted model parameters trained by GD can significantly deviate from the imaginary network parameters trained with corresponding corruption-fre rewards. Therefore, it is non-trivial to quantify corruption impacts from theoretical perspectives, which simultaneously makes our proof flow differ significantly from that of the vanilla Neural-UCB [86). We include additional discussions on analysis distinctions and our contributions in Appendix B.3] To begin with, we first introduce some preliminaries.
Parameter Initialization. Analogous to existing works 86
2
for an L-layer network of
width vn in (3), we let its intermediate-layer matrices 0, 1 E I 1}. where each element of matrix A is drawn from Gaussian distribution (0, 4/m). Similarly, let 02 = (wT, TT,,, where each element of vector w is drawn from (0, 2/m).
0
A
Arm Context Normalization. To ensure arm contexts are of unit length (i.e., || = 1, E [K] t E [T]) as in existing neural bandit works 88,
| 67 50) can apply the following trans- formation inspired by existing works 3 86 84 without loss of generality: with unprocessed context _.,
84
Ti,,, we formulate the corresponding normalized arm context Li,
-.,t |. 2 IT. -)- It can be verified that we have three properties: (i) || = 1; (ii) no two normalized arm contexts
will be in opposite directions; and (iii) f ( 0o) = 0 with the randomly initialized Op.

---

Definitions of NTK Matrices. First, we denote imaginary corruption frreeennn-reeeeeee models as f(: 12
[T] which are trained corruption-fre records P. {ær; Frlrej E [T], for the sake of theoretical analysis, and the learner does not need to own the imaginary model in practice. Let (xi)xe(7] (E(T)) be arms chosen by the corrupted model f(: and (Tzhet(T) herry be those chosen by the corruption-free model f(:; respectively. Then, define a union set Ar := [ U (x; 1 U (=)), based on: (i) the chosen arms (0t)==1 (ii) the op- timal arms [=j)f=1 according to 2 and (iii) arms (2x ) chosen by the imaginary corruption-fiee models. Here, Ar naturally contains unique arms from these three arm collections, with cardinality [rT S 3T' Meanwwile, we simply merge these three arm collections form Ar (with cardinality [Arl = 37), which allows duplicate arms. Afterwards, we have the following two formulations of the NTK Gram matrix: (i) The NTK Gram matrix H with possibly duplicate arms based on the collection Ar; (ii) the NTK matrix for non-duplicate arms H built upon the set År.
Definition 5.1 (NTK Gram Matrix with Possibly Duplicate Arms). Net be the Gaussian distribution. With layer index 1 & [L] and subscripts i E {1,..., | } for enumerating across arms, comparable to [47 86 define the following recursive process
No, yp!
H 1. = (I.,. 2zg),
(7)
2E 2B Noob
Hi, = 2H b.j
ao 1) (oo + v.y.
With AT containing possibly duplicate arms, denote the NTK Gram matrix H
122/2
R x31 and expected reward vector h [h())]=AAr E 32 Existing works with the arm
separateness assumption (e.g.. 86
84
9 25
generally assume H 0, while we do not.
Definition 5.2 (NTK Gram Matrix with Non-duplicate Arms). Follow the recursive process in With set Ar containing non-duplicate arms, we denote the corresponding NTK matrix H (H
/ E glār))(Ar) and expected reward vector h = [h(=)]==AA E RlArl, with |Arl S 3T.
Remark 5.3 (No Arm Separateness Assumption). Existing neural bandit works generally impose separateness assumptions regarding the arm contexts: -TKKhased approaches (e.g.. [86 84
51
50) commonly assume H > 0 which requires no two arms are parallel among {x., ( meanwhile, some other works (e.g., [1 (67) assume the Euclidean separateness: ||2:, ,e, 122 > 0
if (i, * (i','), E 4 E [7]. To avoid the arm separateness assumption, since ÄT contains all the unique arms from Ar, we alternatively build the confidence ellipsoid upon the NTK
matrix H. and the ellipsoid will also hold for all the arms in Ar for regret analysis (Lemma C.I This also leads
tighter definition of NTK norm term S (Theorem 5.6 Remark 5.8).
Fact 5.4. Let No be the minimum eigenvalue of matrix A, and Ag be that of NTK matrix H. We
have (i) A Amin (H) > O; and, (ii) Ao Z Ao 2 O.
For (i) in Fact 5.4 since Ar contains no parallel arms, matrix H will be full-rank, leading to Ao > 0. For (ii), if Ar # Ar, then Ar contains duplicate arms and matrix H will be singular, s.t.
Xo > Ao O. Otherwise, if Är Ar. it will naturally lead to H = H and Xo = Ao. Next, similar to existing neural bandit works (e.g.. 86 84), we define the NTK Gram matrix effective dimension
d, which essentially measures the vanishing speed of NTK Gram matrix eigenvalues.
Definition 5.5 (Effective Dimension of NTK Matrix [86 84). Given the NTK matrix H with possibly duplicate arms (Def. 5.1 its effective dimension is defined as log(1+7K/A)
log det(I+HHA)
5.1 Regret Analysis for R-NeuralUCB
We follow the pseudo-regret R(T)= Σ B - P.) in 2 which is defined based on the expected corruption-Fie free reward of chosen arms and optimal arms across T rounds.
Instance-dependent Gradient Deviation Term 3. Recall that for a candidate arm 24,; E X2 in round
i E [T], its arm weight w.r.t. previously chosen arm æ 7 E [1-1] in (4) can be represented by w min { 11, a- frac, Ng. }, with the scaling parameter > O. Here, we define a minimum fraction value as 3 = (e) mfnn, (xx; Xe, E,-1), frac, (we; Xx, Ex-1)]], which
7

---

is formulated to quantify the gradient deviation among arms. Here, the learner is not required to know B, and we can adjust the scaling parameter a in each round E [T] to constrain the round-wise minimum weight value min (wi, [i([K],rE(t-1] (Subsection B.5 which leads to Theorem 5.6
(7))
Theorem 5.6. finite horizon T E N+, denote 2 V 2h 1 3 0. Suppose À 2 S- 17 S ((TmL++))))) J 2 O(TL./)) Let f()) be an I--layer networrkk with width m. and adjust the scaling parameter a, s.t. min (T)
R², Vt E [T] for a tunable constant E (0,1) from 4. With 5 E (0, 1), let network width m 2 ((poly(T, L, n 1,, 105'.''____ (--) With
[e([]] "
probability at least 6. R-NeuralUCB achieves the regret bound of
A + TK R(T) S (ur Zlog( x TK, 22og(()) T (V (Vrājne) +o Că3-1x² log(
X
The proof of Theorem 5.6 is in Appendix C The first term on the RHS refers to the corruption- independent regret upper bound, which comparably matches the bound Öá + S d))) in existing
corruption- -feee neural bandit works 866 84 Here, our corruption-dependee term is free of the NTK norm S. which measures the complexity of reward mapping i(-)) (Appendix B.4). This is different from existing works (e.g.. (55) that include a parameter norm (similar to our NTK norm S) their corruption-deeende
terms, as the estimation error of confidence ellipsoids. In addition, inspired by [84) we can derive a T -Tindepenneent upper bound for the 3 term, when the arm contexts are nearly spreading within some low-dimensional subspace of the NTK-induced RKHS (Appendix C.9). it
will lead to small effective dimension d and small eigenvalues of NTK matrix H (84). Meanwhile, compared with the regret bound of our base algorithm NeuralUCB-WGil (Theorem 1. Theorem
5.6 removes the assumption of known corruption C; and, reduces the order of effective dimension d as well as the dependency of NTK norm S for corruption-dependentt terms.
Remark 5.7 (Unknown corruption level C). For Theorem 5.6 we do not assume C' is known to the learner in advance, as practitioners can have little prior knowledge regarding the unknown adversary. This makes our regret analysis more challenging, compared with the existing works (c.g.. [[6] where C' is assumed known for setting
to achieve tight regret bounds.
Remark 5.8 (Tighter definition for NTK norm S). For existing works (e.g., [86] 84) the NTK Gram matrix is generally defined with all the TK observed candidate arms, i.e., { (E)) while our NTK matrices (Def. 5.1 and 5.2) only rely on arm collection Ar and set År. with cardinality |Arl S Ar
3T. This results in our parameter norm S that can be tighter compared to existing works (c.g., 84 86 ). because when constructing the confidence ellipsoid around the initialization Oo in Lemma C.I our ellipsoid is intuitively tighter, as it only needs to ensure Eq. holds for
arms in Ar (with cardinality |Árl S 3T), rather than for all TK candidate arms.
Remark 5.9 (Reducing the order of d and removing the dependency of S for corruption-eeendder terms). For corruption-dependent terms involving C, we have ((CB-1d). Using NTK to align the information gain definition [16] with our effective dimension d, our result improves latest kernelized bandit works from ((d//2) to ((d) for corruption-depender terms, given the NTK-induced RKHS and an indefinite arm space (Corollary 7 in (T6). Meanwhile, our coruption-dependen term free of the NTK norm S, while for some existing works with UCB-type exploration (e.g., (15)), they involve comparable parameter norms in their
regret terms, in order to quantify corruption impacts w.r.t the reward mapping function complexity.
Experiments
We evaluate R-NeuralUCB and the base algorithm NeuralUCB--GG (Appendix E with experiments
on three real data sets, under different adversarial corruption scenarios. Following definition in (2), we record the cumulative regret in terms of corruption-
rewards R(T)- = Eie(ry [ - F.]. Note that
the learner will still only have access to the potentially corrupted rewards r2, t E [T]. Our baselines
consist of linear algorithms: Lin-UCB 22), CW-OFUL [42]; and conventional neural algorithms: Neural-UCB 866, Neural-TS 84 Complementary experiment details are in Appendix
Moviel.nns and Amazon Data Sets. From "MovieLens 20M rating data set" we choose 5,000 movies and 10,000 users with most reviews to form the user-movie matrix, and the entries are user ratings. Then, consider the arm (user-item pair) features as the concatenation of corresponding
8

---

Vevaciano Niseet
Areeon Na.ze
PAMST draaet
Moscoety Seland
Amrane Seland
NM011 deaadd
142
3X04
4730
1250
7200
3200
660
50%
61.
1500
11:23
1330
Dr LC3
100
1200
12:0
1500
Figure 1: Regret results on real data sets. (Lefi three figures: For MovieLenn and Amazon, corrupt the chosen arm reward with 20% probability. For MNIST, consider 2000 ramdomly sample 2000 rounds for attack); (Right three figures: Moviel.ens and Amazom: we corrupt reward with 50% probability; For MNIST: C' 4000 and randomly sample 4000 cormuttd munds).
user features and item features, which are obtained by singular value decomposition (SVD) and extracting item rmnom-sscore respectively, with K = 10 and d = 41. The corruption- trreettto--feeeeeeeee arm rewards fi.t are user ratings normalized into range [0, 1]. Here, we consider the "exaggerated reward corruption". If one pulled arm is attacked and its corruption-free reward r: 2 0.5, we exaggerate its reward to r = Otherwise, if one pulled arm Te is attacked and 7 < 0.5, we set its reward r; = 0. Amazon Recommendation data set 43 consists of user reviews and corresponding ratings. With each piece of review (user-item pair) as an arm, we vectorize the review as the arm features using the "Sentire" package [85] [88, with K = 10 and d = 41. Similarly, the corruption-fiee arm rewards fi.e are normalized user ratings with the value range [0. 1]. Different from MovieLens data set, we here consider the "reverse exaggerated corruption" : if the pulled arm Hy is attacked and its corruption-fre free reward F 2 0.5, we downplay its reward to Tr- = 0; or if the pulled arm æ, is attacked and r2 < 0.5, alternatively set the corrupted reward r, = 1.
MNIST Data Set. To perform online classification with bandit feedback experiment, we adopt the MNIST data set [56) which consists of 10 image classes. Similar to previous works (e.g.. 886 (84) given sample E 12d in each round, we transform it into K 10 arms, denoted by 21 (x, (..0......) 0).
= (0, x, ..,.., 0)... ................................ I10 = (0, o..... x) E R 10xd' s.t. d 10 x d'. The arm index that the learner chooses will be its predicted class, and the reward is if the sample belongs to this class; otherwise, the reward will be O. Here, we consider the symmetric tabel--flpppig" attack 39. For example, when sample from digit class 2 is attacked, its corrupted label will be switched to digit class 2 = 7, and the corrupted arm rewards will also change accordingly.
Experiment Results. The experiment results are shown in Fig. [ and we also include a parameter study in Appendix A.2 Due the representation power of neural networks, neural algorithms generally perform better than linear ones. In particular, for the MNIST data set, since the reward mapping can be relatively more complex. neural algorithms manage to achieve more significant improvements over the linear algorithms. Here, compared with conventional neural methods, our proposed NeuralUCB-
and R- N-NeeralUCB are more robust against adversarial reward corrup- tions. In particular, we see that R- ReNeuralUCB outperforms NeuralUCB. WGD on these three data sets, which helps support our claim that it beneficial to involve the uncertainty information in terms of both training samples and candidate arms. When we increase the corruption intensity (three figures on the right), the overall results tend to be consistent with previous findings. Notice that the performance gap among algorithms the Amazon data set tends to be smaller, as this setting becomes significantly more difficult (i.e., with up to 8000 regret) when we increase the corruption probability to 50%. Meanwhile, for MNIST, when we increase C' to 4000, the performance gap between our proposed algorithms and the conventional neural methods tends to increase, as the task becomes increasingly more complex. We also that R-NeuralUCB still outperforms NeuralUCB- WGD given the increased corruption intensity, showing the benefit of involving the candidate arm information and customizing arm-specific model parameters.
7 Conclusion and Future Direction
In this paper, we propose a novel neural bandit algorithm named R-NeuraIUCB to address poten- tial adversarial corruption issues on arm rewards. To enhance model robustness against reward corruptions, R-NeuralUCB applics a refined, context-aware Gradient Descent procedure that incor- porates arm uncertainty information. To demonstrate its effectiveness, we present a regret analysis of R-NeuralUCB to quantify the impacts of adversarial corruption. Furthermore, to ensure that R-NNeralUUBB can handle arm contexts deliberately chosen by an adversary (e.g., duplicate arms across different rounds), our analysis avoids the commonly adopted arm separateness assumption in neural bandit literature, which can be of independent interest. Empirical evaluations on real datasets with varied specifications show the effectiveness of our proposed solution over baseline methods. A challenging future direction is to derive the theoretical lower bound for neural bandits with corruption, and we provide complementary discussions in Appendix B.7

---

Acknowledgments and Disclosure of Funding
This work is supported by National Science Foundation under Award No. IIS-2117902, and Agricul- ture and Food Research Initiative (AFRI) grant no. 0020-67021-32799/pooeee accession no. 1024178 from the USDA National Institute of Food and Agriculture. The work is also supported in part by the National Science Foundation through awards IIS 21-31335, OAC 21 21-30835, DBI 20-21898, as well as a C3.ai research award. The views and conclusions are those of the authors and should not be interpreted representing the official policies of the funding agencies or the govermment.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011.
[2] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In ICML, pages 127-135. PMLR, 2013.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[4] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: 19X1::1944.1195: 2019.
[5] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256, 2002.
[6] Yikun Ban, Ishika Agarwal, Ziwei Wu, Yada Zhu, Kommy Weldemariam, Hanghang Tong, and Jingrui He. Neural active learning beyond bandits. arXiv preprint arXiv:2404. 12522, 2024.
[7] Yikun Ban and Jingrui He. Generic outlier detection in multi-armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 913-923, 2020.
[8] Yikun Ban and Jingrui He, Local clustering in contextual multi-armed bandits. Proceedings of the Web Conference 2021, pages 2335-2346, 2021.
[9] Yikun Ban, Jingrui He, and Curtiss Cook. Multi-facet contextual bandits: A neural network perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 35 45, 2021.
[10] Yikun Ban, Yunzhe Qi, Tianxin Wei, Lihui Liu, and Jingrui He. Meta clustering of neural bandits. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 95-106, 2024.
[11] Yikun Ban, Yuchen Yan. Arindam Banerjee, and Jingrui He. Ee-net: Exploitatioonexploration neural networks in contextual bandits. arXiv preprint 10Xiv:2110.03177, 2021.
[12] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Neural exploitation and exploration of contextual bandits. arXiv preprint arXiv:2305.03784 2023.
[13] Yikun Ban, Yuheng Zhang, Hanghang Tong, Arindam Banerjee, and Jingrui He. Improved algorithms for neural active learning. Advances in Neural Information Processing Systems, 35:27497-27509, 2022.
[14] Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kemcls. Advances in Neural Information Processing Systems, 32, 2019.
[15] Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-toleran gaussian process bandit optimization. International Conference on Artificial Intelligence and Statistics, pages 1071-1081. PMLR, 2020.
10

---

[16] Iija Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett. A robust phased elimination algorithm for corruption-toleratt gaussian process bandits. Advances Neural Information Processing Systems, 35:23951-23964 2022.
[17] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
[18] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[19] Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust gaussian process bandit optimization. In International Conference on Machine Learning, pages 1216-1226. PMLR, 2021.
[20] Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: 198, 2019.
[21] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 122110336-08446 2019.
[22] Vasileios Charisopoulos, Hossein Estandiari, and Vahab Mirrokni. Robust and private stochastic linear bandits. In International Conference on Machine Learning, pages 4096-4115, PMLR, 2023.
[23] Christopher A Proquette-Choo, Florian Tramer, Nicholas Carlini, and Nicolas Papernot. Label- only membership inference attacks. In International conference on machine learning, pages 1964-1974. PMLR, 2021.
[24] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In AISTATS, pages 208-214, 2011.
[25] Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandit. arXiv preprint arXiv:2205. /4309, 2022.
[26] Rohan Deb, Yikun Ban, Shiliang Zuo, Jingrui He, and Arindam Banerjee. Contextual bandits with online neural regression. arXiv preprint a1X 2023.
[27] Yashar Deldjoo, Tommaso Di Noia, and Felice Antonio Merra. A survey on adversarial recommender systems: from attack/defense strategies to generative adversarial networks. ACM Computing Surveys (CSUR), 54(2):1-38, 2021.
[28] Aniket Anand Deshmukh, Urun Dogan, and Clay Scott. Multi-task learning for contextual bandits. In NeurlPS, pages 4848-4856, 2017.
[29] Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 7111-7123. PMLR, 2022.
[30] Audrey Durand, Charis Achilleos, Demetris Iacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pincau. Contextual bandits for adapting treatment in mouse model of de novo carcinogenesis. In Machine learning for healthcare conference, pages 67-82. PMLR, 2018.
[31] Li Fan, Ruida Zhou, Chao Tian, and Cong Shen. Federated linear bandits with finite adversarial actions. Advances in Neural Information Processing Systems, 36, 2024.
[32] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference on machine learning, pages 1126-1135. PMLR, 2017.
[33] Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to mis- specification contextual bandits. Advances in Neural Information Processing Systems, 33:11478- 11489, 2020.
11

---

[34] Dongqi Fu, Liri Fang, Ross Maciejewski, Vetle I. Torvik, and Jingrui He. Meta-learned metrics over multi-evolution temporal graphs. KDD 2022, 2022.
[35] Dongqi Fu and Jingrui He. SDG: A simplified and dynamic graph neural network. In SIGIR 2021, 2021.
[36] Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[37] Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. ACM/IMS Journal of Data Science, 1(1):1-18, 2024.
[38] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference Learning Theory, pages 1578-1578. PMLR, 2019.
[39] Han, Q Yao, X Yu, G Niu, M Xu, Hu, I Tsang, and M Sugiyama. Robust training of deep neural networks with extremely noisy labels. In Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS), volume 2, page 4, 2020.
[40] Eric Han and Jonathan Scarlett. Adversarial attacks on gaussian process bandits. In International Conference on Machine Learning, pages 8304-8329. PMLR, 2022.
[41] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4): 2015.
[42] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:2205.066 06871, 2022.
[43] Ruining He and Julian McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In proceedings of the 25th international conference on world wide web, pages 507-517, 2016.
[44] Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In WWW, pages 173-182, 2017.
[45] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[46] Taehyun Hwang. Kyuwook Chai, and Min-hwan Oh. Combinatorial neural bandits. In Interna- tional Conference on Machine Learning, pages 14203-14236. PMLR, 2023.
[47] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[48] Yiling Jia, Weitong ZHANG, Dongruo Zhou, Quanquan Gu, and Hongning Wang. Learning neural contextual bandits through perturbed rewards. International Conference on Learning Representations, 2021.
[49] Yue Kang, Cho-Jui Hsich, and Thomas Chun Man Lee. Robust lipschitz bandits adversarial corruptions. Advances in Neural Information Processing Systems, 36, 2024.
[50] Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, pages 240-278. PMLR, 2022.
[51] Parnian Kassraie, Andreas Krause, and Iijaa Bogunovic. Graph neural network bandits, arXiv preprint arXiv:2207.06455. 2022.
[52] Johannes Kirschner and Andreas Krause. Bias-robust bayesian optimization via dueling bandits.
In International Conference on Machine Learning, pages 5595-5605. PMLR, 2021.
[53] Sanath Kumar Krishnamurthy, Vitor Hadad, and Susan Athey. Adapting to misspecification contextual bandits with offline regression oracles. International Conference on Machine Learning, pages 5805-5814 14. PMLR. 2021.
12

---

[54] Yuko Kuroki, Alberto Rumi. Taira Tsuchiya, Fabio Vitale, and Nicolò Cesa- Bianchi. oest-of- both-worlds algorithms for linear contextual bandits. International Conference on Artificial Intelligence and Statistics, pages 1216-1224. PMLR, 2024.
[55] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International conference on machine learning, pages 5662-5670. PMLR, 2020.
[56] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning 2324, 1998.
applied to document recognition. Proceedings of the IEEE,
[57] Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimality and minimax-optimality in stochastic and adversarial linear bandits simultancously. In International Conference on Machine Learning, pages 6142-6151. PMLR,
2021.
[58] Lei Li, Yongfeng Zhang, and Li Chen. Generate neural template explanations for recommenda- tion. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 755-764, 2020.
[59] Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In WWW, pages 661-670, 2010.
[60] Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng. Patrick Jaillet, and Bryan Kian Hsiang Low. Use your instinct: Instruction optimization using neural handits coupled with transformers. arXiv preprint 2rXiv:23/00029000 2023.
[61] Brad Miller, Alex Kantchelian, Sadia Afroz, Rekha Bachwani, Edwin Dauber, Ling Huang, Michael Carl Tschantz, Anthony D Joseph, and J Doug Tygar. Adversarial active learning, In Proceedings of the 2014 workshop on artificial intelligent and security workshop, pages 14, 2014.
[62] David J Miller, Zhen Xiang, and George Kesidis. Adversarial learning targeting deep neural network classification: A comprehensive review defenses against attacks. Proceedings of the IEEE, 108(3):402-433, 2020.
[63] Aritra Mitra, Arman Adibi, George J Pappas, and Hamed Hassani. Collaborative linear bandits with adversarial agents: Near-optimal regret bounds. Advances in neural information processing systems, 35:22602-22611 2022.
[64] Bamshad Mobasher, Robin Burke, Runa Bhaumik, and Chad Williams. Toward trustworthy rec- ommender systems: An analysis of attack models and algorithm robustness. ACM Transactions on Internet Technology (TOIT), 7(4):23es, 2007.
[65] Rui Ning, Jiang Li, Chunsheng Xin, and Hongyi Wu. Invisible poison: A blackbox clean label backdoor attack to deep neural networks. In IEEE INFOCOM 2021-IEEB Conference Computer Communications, pages 1-10. IEEE, 2021.
[66] Yunzhe Qi, Yikun Ban, and Jingrui He. Neural bandit with arm group graph. arXiv preprint arXiv:2206.0368 036444 2022.
[67] Yunzhe Qi. Yikun Ban, and Jingrui He. Graph neural bandits. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, page 1920-1931, New York, NY, USA, 2023. Association for Computing Machinery.
[68] Yunzhe Qi, Yikun Ban, Tianxin Wei, Jiaru Zou, Huaxiu Yao, and Jingrui He. Meta-learning with neural bandit scheduler. Advances in Neural Information Processing Systems, 36, 2024.
[69] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing. In International Conference on Machine Learning, pages 8230-8241. PMLR, 2020.
[70] Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy gaussian process bandit optimization. In Conference on Learning Theory, pages 1723-1742. PMLR, 2017.
13

---

[71] Ruixiang Tang, Mengnan Du, Ninghao Liu, Fan Yang, and Xia Hu. An embarrassingly simple approach for trojan attack in deep neural networks. Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 218 2020.
[72] Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Uncertainty Artificial Intelligence, 2013.
[73] Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
[74] Zhilei Wang, Pranjal Awasthi, Christoph Dann, Ayush Sekhari, and Claudio Gentile. Neural active learning with performance guarantees. Advances in Neural Information Processing Systems, 34:7510-7521, 2021.
[75] Zhiyong Wang. Jize Xie, Xutong Liu, Shuai Li, and John Lui. Online clustering of bandits with misspecified user models. Advances in Neural Information Processing Systems, 36, 2024.
[76] Chen- Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages (043-1096 PMLR, 2022.
[77] Max Welling and Thomas N Kipf. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[78] Longfeng Wu, Yao Zhou, and Dawei Zhou. Towards high-order complementary recommen- dation via logical reasoning network. In Xingquan Zhu, Sanjay Ranka, My T. Thai, Takashi Washio, and Xindong Wu, editors, IEEE International Conference on Data Mining, ICDM 2022, Orlando, FL, USA, November 28- Dec. 1, 2022, pages 1227-1232. IEEE, 2022.
[79] Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in a collaborative environment. In SIGIR, pages 529-538, 2016.
[80] Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. On private and robust bandits. Advances Neural Information Processing Systems, 36, 2024.
[81] Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01780, 2020.
[82] Fuzhi Zhang and Quanqiang Zhou. Ensemble detection model for profile injection attacks in collaborative recommender systems based on bp neural network. IET Information Security, 911:24--11 2015.
[83] Weitong Zhang, Jiafan He, Zhiyuan Fan, and Quanquan Gu. On the interplay between misspeci- fication and sub-optimality gap in linear contextual bandits. In International Conference on Machine Learning, pages 41111-41132 PMLR, 2023.
[84] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021.
[85] Yongfeng Zhang, Haochen Zhang, Min Zhang, Yiqun Liu, and Shaoping Ma. Do users rate or review? boost phrase- sentiment labeling with review-level sentiment classification. In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, pages 1027-1030, 2014.
[86] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492- 11502. PMLR, 2020.
[87] Yao Zhou, Haonan Wang, Jingrui He, and Haixun Wang. From intrinsic to counterfactual: On the explainability of contextualized recommender systems. CoRR, 10,14444,,4444, 2021.
[88] Yao Zhou, Jianpeng Xu, Jun Wu, Zeinab Taghavi, Evren Korpeoglu, Achan Kannan, and Jingrui He. Pure: Positive-unlabeled recommendation with generative adversarial network. In KDD, 2021.
14

---

[89] Shiliang Zuo. Corruption- robust lipschitz contextual search. In International Conference on
Algorithmic Learning Theory, pages 1234-1254 PMLR, 2024.
15

---

A Experiment Settings and Additional Experiments
A.1 Experiment settings
For all UCB-based baselines, we choose the exploration parameter through grid search over the range {0.01, 0.1, 13. We set L = 2 for all deep learning models, including our proposed NeuralUCB- WGD and R-NeuralUCB, and set the network width to 200. The learning rate for all neural algorithms is chosen by grid search from the range {0.0001, 0.001, J. For all methods, we select the regularization parameter À from the range {0.0001, 0.001.0..000000 0.01}. The scaling parameter for NeuralUCB WGG and R- R-NeuralUCB is chosen from {0.2, 0.5, 1}. All experiments are conducted on server with an Intel Xeon CPU and NVIDIA V100 GPUs. Additionally, we provide further details on our baseline methods, which include two linear algorithms and two conventional neural algorithms:
Lin-UCB 24 59] uses linear regression as the reward estimation model and employs UCB-based
strategy for exploration.
CW-OFUL 42 applies weighted linear ridge regression in instead of the standard one from Lin-UCB, with weights assigned selected samples in proportion to reward estimation confidence.
Neural-UCB (86) employs single neural network to estimate arm rewards and calculates the UCB based on network gradients for exploration.
Neural-TS 84 utilizes a fully connected network for arm reward estimation, along with the
Thompson Sampling strategy 2 for exploration.
Additional Data Processing Details for Recommendation Data Sets. Here, we provide additional details about our data processing procedure. For the first data set, MovieLens 20M rating data set org/ http/aataett////e/ee
we initially select 5,000 movies and 10,000 users with the most reviews to form user-movie matrix, where the entries represent user ratings. The user features Ia E Rº" are derived via singular value decomposition (SVD) with dimensionality of d' 20. Using the genome scores provided for each movie, we select the 20 tags with the highest variance and used their corresponding scores as movie features v; E RRd At each time step f, given user uy, encode user information into the arm contexts following the Generalized Matrix Factorization (GMF) approach [44] [8) by concatenating the features Ti,t = ( v 2d where E Ce and E [K], with K = 10. Finally, we concatenate a constant 0.01 to each æ5,t and normalize the entire vector to obtain Zi,t E Rd. where d = 41. The corruption-free arm rewards Fi,, are user ratings normalized to the range [0, 1]. We consider the scenario of "exaggerated reward corruption": If a pulled arm Dg is attacked and its corruption-fre reward F. 2 0.5, we exaggerate its reward r, 1. Conversely, if pulled arm æ; is attacked and its corruption-free reward F, < 0.5, we downplay its reward to r. =0 O.
buttps://groupleet
For the Amazon Recommendation data set (https://jmcaull) ucsd. edu/data/ amazon/ index_ 2014x22044.a 2014.html), each user-item pair is associated with a review and the corresponding user rating. We transform the review text into vector representations to derive the arm contexts, following the text processing procedure in the "Sentires" " package [85)58). We then set d = 41 and apply La normalization, with an arm pool size of K 10. Similarly, the corruption-free are normalized user ratings in the range [0. 1]. Unlike the Movielens data set, we apply a "reverse exaggerated corruption" approach here: If the pulled arm æ; is attacked and its corruption-free reward F. 2 0.5, we downplay its reward to rt = O. Conversely, if the pulled arm Φ, is attacked and its corruption-free reward < 0.5, we set the corrupted reward to r,
rewards T,
A.2 Additional experiments: parameter study
We also include additional experiments with different regularization parameter values À and ex- ploration parameter values v. On the MNIST data set (corruption level 2000), we conduct experiments for NeuralUCB- Tables 2 and 3 For both of our proposed algorithms, setting v E 0.5) generally yields the best performance. However, with an overly small exploration coefficient (e.g., = 0.05), optimal empirical performance may not be achievable. Meanwhile, setting to smaller values, such as 0.001 or 0.0001, tends to result in the best performance. Increasingly large regularization parameter values
and R- R-NeuralUCB. We present the parameter study results in
16

---

Algorithm À value
0.1
=
À = 0.001
À = 0.0001
NeuralUCB-Wen
3244 195
2782
190
2156 105
2103 1119
R-NeuralUCB
2933
1001
2501
193
1989
167
2127 192
Table 2: Regret results for different exploration regularization parameter values À (with std.)
Algorithm \
value
==
== 0.5
== 0.1
/ == 0.05
NeuralUCB-We WGG
2510 1:102
2154 1:121
2103 1119
2278 ::85
R-NeuralUCB
2793 1104
2163 888
1989
--67
2197 1:65
Table 3: Regret results for different exploration parameter values v (with std.)
can cause the trained model parameters 0 remain close their random initialization 9g. which can overly constrain the neural network's 's capacity to fit the underlying reward mapping function. Thus, practitioners can adjust the value based on specific application needs, as is common in other neural bandit studies (e.g., (86). In practice, starting with small values like 10-1 and performing grid search to identify the optimal À is reasonable approach for R-NeuralUCB and NeuralUCB-Wi CGD.
B Complementary Discussions on the Content of the Main Body
In this section, we provide additional discussion to complement the main body content.
B.1 Boarder impacts
Since our objective is to deal with the potential adversarial attacks in machine learning applications, this work can contribute to the goal of achieving trustworthy machine learning for general practitioners. Therefore, do not perceive significant negative societal impacts that can be generated by this work.
B.2 Limitations
One limitation of this work the absence of a thcoretical lower bound for neural bandits with adversarial corruptions. We would like mention that this problem is significantly challenging and non-trivial. Given that we deal with an arbitrary reward function h(-), which is considerably different from linear [42] and kernelized bandits [16), deriving the lower bound itself can lead substantial contributions, potentially leading to a separate line of research works (e.g., [70] under kernelized bandit settings). Therefore, we consider the derivation of such lower bound for neural bandits with
adversarial corruptions as an interesting and challenging future direction of this work. Additional discussions the lower bound can be found in Subsec. B.7
B.3 Theoretical contributions and comparisons with vanilla Neural-UCB
Recall that we propose deriving the regret bound using NTK-based regression techniques. Unlike linear bandit approaches (e.g., 42 and kernel bandit methods (e.g., [16)), our regression is conducted
on the network gradients g(:: 0) := Vee(Veff (:: 9)), which serve as the mapping for gradient-based æ, the NTK-embedded arm contexts can differ due
NTK. In this framework, to the corrupted parameters g(x; 0) and the corruption-fiee parameters g x 0). To address this challenge, we define two sets of regression parameters corresponding to the corrupted model and the corruption-free model respectively. Then, using the corruption-free model [(; 0), we derive the confidence ellipsoid around its parameters 0. This serves proxy to quantify the parameter shift of the trained corrupted model parameters 0 enabling us to establish the regret upper bound.
for the same
For the theoretical analysis of R- R-NeuralUCB presented in Theorem 5.6 we considerably modify the regret analysis workflow due to the following reasons: (i) To achieve improved performance, R-NeuralUCB differs from conventional neural bandit approaches by tuning separate sets of network parameters for each candidate arm after perceiving arm context information; (ii) To achieve tighter
regret bound and eliminate the assumption of known corruption level C, unlike in Theorem E.I
17

---

we cannot quantify the impact of C' using the confidence ellipsoid. To address this, let x; and zt represent the optimal arm and the chosen arm by the corrupted model, respectively. We decompose the single-round pseudo-regret R2 = min (A(=;) h)(x;), 1) into three components: (i) The prediction error of the corruption-fres free model; (ii) The reward estimation discrepancy between the corruption free model and the corrupted model on the same arm; (iii) The arm selection discrepancy of the corrupted model induced by adversarial corruptions. Next, we apply carefully designed arm weights in (4) to guide the gradient descent process and mitigate the impact of adversarial corruptions. As a result, R-NeuraIUCB achieves non-trivial theoretical improvements: (i) removing the assumption of known corruption level C in regret analysis; (ii) eliminating the dependency the NTK norm term S for corruption-dependee
terms in the regret bound; (iii) reducing the order of corruption -eruuptioondeeedenett terms in the regret bound to the effective dimension d, from (d2 to (d), compared with our base algorithm NeuralUCB-WGI. and existing kernelized bandit algorithms (e.g.. [6)..
In addition, as mentioned in Remark 5.3 existing neural bandit approaches typically impose sepa- rateness assumptions on observed arm contexts, whereas we do not. For example, Neural-UCB [86] assumes H > O, which requires that no two arms are parallel among {æ.,, Jix [M]. In contrast, by formulating our NTK Gram matrices (Definitions 55 and 5.2), complete our proof without the separateness assumption, reinforcing the theoretical robustness of our approach against possible arm contexts selected by adversary (e.g., duplicate arm contexts across time steps). As in Remark [5.8] existing methods, including Neural-UCB [86]84), generally define their NTK Gram matrices over all TK observed arms, i.e., (Ej,,)) However, our NTK matrices (Definitions 5.1 and 5.2 are
based on AT and Är. where |År] S |Ar] = 3T. This formulation can result in a tighter NTK norm S compared with existing methods.
Upper bound for vanilla Neural-UCB. Meanwhile, to provide insights into the regret bound of Neural-UCB, one possible approach is to follow similar analysis to the regret bound of NeuralUCB-
WGD. The key idea here is to quantify the impact of adversarial corruptions on the confidence ellipsoid around the trained parameters. Referring to the derivations in Lemma F.1, and denoting the corruption-free confidence radius in round as -t- we obtain the corrupted confidence ellipsoid for Neural-UCB as C.-1 = {0: ||0 0z-1 Ir.., I 7t-1/Vm) where - = 7t + (CTLX-1/2) This result is derived by setting w,, = 1 for t E [t 1 1] and applying the fact that Ere(r) C S C. along with Lemma G.2 and the initialization of the gradient covariance matrix r. Following the proof flow of Lemma 5.3 in (86), we obtain a regret upper bound of Ö(dVT + V + CCL//r//
which introduces an additional Ö(VT) to the vorrutioon-deendden term.
Over-parameteriin
For most neural bandit works with experiments (c.g.. 84 86
gap exists between experiments and theoretical analysis. On one hand, as the number of layers L. and hidden dimension m increase, neural networks become progressively harder train, more time- consuming in inference, and more resource-intensive To make neural bandits feasible for practical applications, these works generally use a neural network of ordinary size for experiments. It has been shown that even with ordinary-sized neural networks, neural bandit algorithms achieve notable performance gains over linear and kernel-based methods [86] 84 9 11 67). On the other hand, from a theoretical standpoint, neural networks need to be over-parameterized, with m 2 O(poly(T)) to approximate any arbitrary reward mapping function h(-). Additionally, with over-paramtteriiaaionn the difference between NTK-based regression models and neural networks becomes sufficiently small for regret analysis, which is essential in neural bandit research. Therefore, we use two-layer fully connected network for experiments while performing theoretical analysis under perrpaarameeerized
settings, as most existing neural bandit works (e.g., 86 84
B.4 The definition and order of NTK norm parameter S
Recall that we have the NTK norm defined as the upper bound of the weighted norm S 2 [[]]] h- where h refers to the vector of expected rewards and H refers to the NTK Gram matrix (Definition 5.2). We can follow existing neural bandit works 886 50 51
84 48 by considering that the reward mapping function h(-)) in belongs to the Reproducing Kernel Hilbert Space (RKHS) H induced
by NTK. In this case, we can upper bound S with the RKHS norm, such that | H 2 S, and the RKHS norm ||A]| x will not grow along with the finite horizon T (Remark 4.8 in (86).
18

---

Meanwhile, we also would like to mention that this is a common formulation, and nearly all the neural bandit works (c.g., 86 50 51
48) will include a comparable NTK norm term in the regret bound. This is because the regret analysis of neural bandits is generally depending on the NTK regression approach. In this case, when constructing the confidence ellipsoid within the NTK-induced RKHS, we will need to involve the RKHS norm as the cost. Analogously, for the
[6) ) they inevitably involve the RKHS norm into kernelized contextual bandits works (c.g. [72 28
the regret bound. For linear bandit works (e.g., 42). they will also need to include assumed upper bound of the true parameter norm in the Euclidean space, such that ||0-||2 is bounded by a constant. Meanwhile, since the NTK norm term S stays invariant across candidate arms Fi, X2, we can treat S as a constant in practice (e.g., setting = 1), and control the exploration intensity by tuning the exploration parameter
B.5 Details regarding the scaling of arm weights
Recall that when defining the sample weights w((7 in 4 we use the minimum gradient norm in the numerator scale weights across the current candidate arms X,, while introducing the scaling parameter a > O to provide additional control from the practitioner's perspective. Under the stochastic contextual bandit settings, the learner receives the candidate arm pool X, in each round from the environment, having little control over the minimum gradient norm, as X, is only revealed round I. To address this, we introduce a tunable parameter a control the minimum value of (T) aiming for a more stable learning process. Additionally, when deriving the regret bound for R-NeuralUCB (Theorem (.6), we scale the a values to ensure that the minimum weight value is x?? Without this scaling, such as by setting a = 1, an extra corruption cnrruttioninnependeen term
O(V B--TToog(1 1 + TK)))) would be added to the current regret bound, making the overall bound less tight. Therefore, the scaling parameter is essential for R-NeuralUCB.
Furthermore, the denominator of 4 consists of the product of two gradient norms: (i) the norm of the previously chosen arm 9r, and (ii) the norm of the candidate arm [] 0)/ mm/ 1 Here, we use the squared norm in the numerator balance with the norm product the denominator. This design is also critical for deriving the regret bound in Theorem 5.6 Without using the squared norm, our current derivation would yield corruption-dependee term of OddVT3- C)), rather than the current Ödd3-1C).
To be specific, for scaling the arm weight based on k, we first recall that in round E [7], we have arm weights w r E [t 1], E [K]. We can also denote w.,7) min {1, frac, (3ri, Xr, Ex- } a fixed value across horizon T. we can consider to be varying
Here, instead of deeming across different rounds, denoted by au, E [T]. With a shorthand for minimum fraction value frac..in = min:c[K]),r((-1] [frac, (Zr,,; Xr Eg-1)], we can set each ag n²² m2//frac.in, . E (0, 1).
As result, we can consequently have min w Jiejk =E(t-1 = x², Vt E [T].
B.6 Warm-start training for candidate arms
Recall that each round E (2..... T), we need train different sets of arm-specific parameters 0, E [K] according to Algorithm [] for each of the candidate arms Di, E Xx i E [K]. As we have mentioned in the main body, we can adopt the idea of warm-start GD [3 in practice. Here, instead of training each set of parameters 0;,-- from the randomly initialized Oo. we tune arm-specific parameters for each Vi, E X, with a small number samples from current received
(7) records Pt-1- With the formulated arm weights w in (4 we first recall the arm-specific loss function associated with arm Zi, as
(T)
(P:(P=-1;))=
Σ
[s(=):))
mA r-|2+ +
2 ||0 0011
2
JEP
The idea that instead of starting from Og. we can initiate the GD process from the existing network parameters 0.- from the previous round ( - 1, where 0.-2 O, 1.t-2 represents the parameters associated with the chosen arm .;-1 = -i in round - 1. The pseudo-code for this arm-specific warm-start GD process is provided in Algorithm
19

---

Algorithm 2 Warm-start training for R-NeuralUCB
1: Input: Candidate arm æ; Xr Training steps J. Learning rates 1,. Batch size B. Regulariza- tion parameter A. Network parameters 0,- from round - 1. Received records Pt-1-
2: Output: Trained arm-specific network parameters 0,,-1 for ai,t X.
3: Sample a batch of training samples from Pt-1. denoted by P E Pt-1, where (P--1 = B.
Following (4, calculate arm weights w!,7 for samples in P,-1-
4: 1,t-1 2--2-
5: for each training step j E do
0 0 - VoL.
6:
7: end for
8: 0 1.1-1
9: Return arm- arm-specific network parameters 0,
Number paramaters
Inferance Lime for Novistans
Inference time MIIST
1900
140 ROD0 350 6.0
1050 8000
12:00
2000
1000
10000
Figure 2: Number of parameters with hidden dimensions m. Inference time with warm-start.
As result, in experiments, balance computational costs and model performance, implement the following strategies: (1) Inspired by meta-learning approaches [32]. we apply warm-start gradient descent (GD) by adapting previously trained network parameters 0,- for each candidate arm, using a small number of training samples rather than starting from Op with a large sample size; (2) Based on our formulation of the warm-start GD process, we sample fixed number of mini-batch training samples (i.e., received arm-reward pairs) for each candidate arm to compute arm weights and perform GD. Using fixed number of training samples helps keep round-wise inference time relatively stable, avoiding drastic increase with T. Figure 2aaureeillltraaaa different hidden dimensions. As shown, inference time remains relatively stable due to the fixed number of adaptation samples used for warm-start GD.
the parameter count and inference time across
B.7 Additional discussions the lower bound
Under linear bandit settings, there is model-agnostic lower bound of ceruptioon-eeendentt term (CCd) with probability least 1/2 [17, which will also hold for neural bandit works as our h(-)) can be an arbitrary function. Meanwhile, the lower bounds for kernelized bandits tend to vary depending on kernel characteristics, e.g., (2(())))))))443 for the SE kernel and ((CTTTT for the v-Matérn kernel [70] 16] In this case, the order of term C' and whether the lower bound depends on non-logarithmic T, will both depend on the kernel properties. Therefore, given close connections between NTK-based regression and over-parameterized networks, we hypothesize that such a lower bound for neural bandits with corruption can depend on NTK properties. However, it will require significant efforts and well-established existing knowledge base (e-g., number of functions M needed for the functional separateness condition [70 19 regarding specified kernels) to obtain such a lower bound for non-linear cases, especially considering few restrictions are imposed for reward mapping fu-)) for neural bandits. Since there are no existing works from neural bandits NTK perspectives, it can lead to a different line research work by proving these results, Therefore, we consider providing such corruption -ependdn regret lower bound challenging future direction.
0, we obtain corruption-free regret of Ö SV dr). By setting C ((Rr /d), the regret bound becomes Ô (()) VT S2 ( - Cg-1d-1). We note that, following the proof flow of Theorem 4.12 in 42 and the learning problem defined in Assumption
Meanwhile, when
20

---

2.1 of 42). our effective dimension term de may depend on the horizon T and can grow with T [26]. Consequently, although the regret bound contains only VT terms, the overall order of the regret bound could reach or exceed (T) due to the effective dimension d², discussed in [26]. This behavior differs from that of linear bandits, where regret bounds generally depend on the horizon T' and other 7 T-independent terms, such as context dimension d and fixed 7-independent linear parameter norm ||0*|2- Therefore, our Theorem 5.6 will not contradict Theorem 4.12 42
21

---

C Regret Analysis for R-NeuralUCB
To begin with, recall that we aim to minimize the pseudo-regret for T rounds, denoted by
T
T Σ
R(T)
Σ R 1=1
M(a)) - -((=))
where the second equality is due to the definition of reward mapping h in (T). We denote f(-) as the bandit model we eurrently possess, which is trained with corrupted records Pi-1 up round t. Similarly, we can also suppose a corresponding imaginary corruption- free bandit model, which is trained with corruption-free -freeonn-feeeee records Pi-1. Similarly, the model parameters of our possessed f(-) are denoted as 0, while the parameters of the imaginary corruption-fred frree model will be denoted as O.
Subsections outline and proof sketch. The content in this section organized into the following sub-components In Subsection C.I we first present theoretical properties related to our definitions of the NTK Gram matrix (Definitions
and Subsection C.2 we decompose the single-round objective Re, / E [T] into its sub-components: (i) the first component represents the prediction error of the corruption-fiet model; (ii) the second component measures the potential arm selection discrepancy of the cornupted model caused by adversarial corruptions; and (ii)) the third component captures the estimation discrepancy between the corruption-Fis free model and the corrupted model. Next, in Subsection C.3 we bound the cumulative pseudo-regret R(TT') (proof of Theorem 5.6 Using the auxiliary sequence introduced in Subsection C.4 we bound the components of the single-ruund regret in Subsections C.5
through C.8 Finally, we discuss bounding the minimum fraction term B in Subsection C.9 particularly when the observed arm contexts lie nearly within a nww-dimessiona subspace of the RKHS induced by NTK.
C.1 Theoretical Results with NTK Gram Matrices
We will first introduce some results, in order to link the NTK matrices (Def. 5.1 and Def. 5.2) with the reward mapping function h(-) and the gradient covariance matrix Σ (Algorithm D.
Lemma C.1. With probability at least 1 5, if network width m satisfies the condition in Theorem 5.6 for any x E Ar, there exists a set of parameters 0" such that
h(x)
{g(x;; 0o), 0" 00)
(C.1)
where parameters 0 satisfy 110- - 0oll < 8/ mm, along with the NTK norm SZ V 2h i-
The proof of this lemma is inspired by that of Lemma 5.1 in 86 However, we build our proof upon the non-duplicate arms År and the corresponding NTK Gram matrix H (Def. 5.2).
Proof.
instead of imposing the full-rank assumption on the conventional NTK matrix H (Def. 5. Here, we recall that the matrix H is naturally positive definite (N, Amin H > 0), as it is the NTK Gram
matrix built upon a set of distinct arms that are not parallel (Fact 5.4 5.4
Then, consider the gradient matrix with no-duplicate arms G = [g(:;; mo E RRx] where p represents the total number of parameters in the neural network. As result, by applying conclusion from Lemma C.3 and due to the fact that |Arl S 3T, with the network width m 2 2 7,6 log(TT./8)/e), Ve > and the probability at least 1 - 8, we will have
G
H| P S -r.
Ap By setting e 2|Az|'
we will have
H Ao/21 H12 0.
where the last two inequalities are due to Fact 5.4 that H 2 XnI > 0. Analogous to Lemma 5.1 in 886, we consider the singular value decomposition of G being G PAQT, where we naturally have > 0 since H is positive definite. Then, with the expected reward vector h (Def. 5.2). we have
h (QAPT) -Ā-' h= Vm- ČT - -0)).
22

---

by considering there exists set of parameters 6- = =8 + (PA -QT) (PA-1PA)
h//m.
Therefore, since h .m G (0" Qo), we will have Va E Ar,
h(x) (g(x; 0o), 0" - Oo).
Meanwhile, since GTG H/2, by applying Lemma G.8 will have the distance m |00 0ol1 = h h
- hTGG)) S H
Finally, since the above results holds Væ Ar, due to the fact that Ay contains all the unique arms of the collection Ar, we will directly have the above results regarding parameters 0" feasible Vx Ar. This completes the proof.
Lemma C.2. Suppose satisfies the conditions in Theorem 5.6 Suppose the gradient matrix with randomly initialized parameters is (1)) XI +mm g(:; 0o) g( 0o) /,, upon an arbitrary
subset A C AT of arm collection Ar. With probability at least 8 over the initialization, the result holds:
det X
log
S <dlog(1 4K/AA) +
det AI
Proof. First, recall that we have Ar as the arm collection of: (i) the chosen arms { (ii) the optimal arms ) (iii) and the imaginary ones { ) chosen by the corruption- model. This makes its cardinality [Arl = 37. Thus, for the left hand side, we have
det (et(2(() det(AI)
log
I log det(AI+
Σ g(æ; 0n)g( 7/m) det(AI+ Go GoGT), ΦEAT
where we define gradient matrix Go [0(:; 0o)/ /m mEAr E (2x based on arm collection
Ar. Here, based on Lemma C.3 we can bound the distance between the Gradient matrix product
G Go and the NTK matrix (Def. 5.1. as
| Go
H
37
3T O(VT/A) O(VT/A)
by setting 3T-OIVT/M /Xi
The above results will hold, as long as we have the network width
m 2 Q((TL) log(T L/)) matching the conditions in Theorem 5.6 As a result, we can have log det (1 + G.GGOAA
log H/X+ (G H)/A)
< log (I + ((I (I- H)/A)
S log det(I (///))++(((() +|[[+H/))""]||][[[
H /
< log
+ +OVTT/A)- H
< d H/A) +1
ālog(1 TK/A) + 1.
The first inequality because the concavity of log det(-) function: The third inequality is due to
< | 11 1 SVT: The fourth inequality by applying the above distance upper O(VT/x) The last inequality is because of the choice the m; The last equality because of the Definition of d. The proof completed.
HA)- [[I+HA)-
bound || H|
Lemma C.3. With the randomly initialized network parameters Oo E RR and collection of arms A C. Rd, define the gradient matrix GA [g(x; 0o)]æEA E RPx|AI, Following the recursive procedure in Def. 5.17) construct the NTK Gram matrix HA based on arms A. Then, with the probability at least 8. we will have
G - HAlle $ |A| -e
with the network width m 2 R(L Log[ (og((A))/))/e))
23

---

Proof. The proof of this lemma is analogous to the proof of Lemma B. in [6). Based on Theorem 3.1
from A we have that for any two arms æ. x' A. as the network width m
22(L log(L/))/=*)
we will have (r( 0o), (ax; 0o)) m H [r. æ'Il S e, where H Ha( æ"| represents the element NTK Gram matrix A that corresponds arms a and x:..
Next, taking the union bound over all the arms in A, we will have
G - HAllF = Σ
Σ
Kg(æ; 0o), g(x'; 00)) Halæ, x'1 |Al
#E E'A
as long as the network width m 2 ( lo)((1)1/8//)))
C.2 Bounding single-round regret
With the above results linking the NTK to the neural model, we proceed to bound the single-round regret R2 for t E [T]. This single-round regret will then be aggregated to obtain the cumulative regret R(T) Eie Ra.
Based on Lemma
we have the expected reward of an arm x: E X₁ being
E|r|æ] = h(z) (g(x; 0o), 0" - -0)
where there exist parameters 0* such that | Poll - S/ mm. Meanwhile, apart from the trained parameters 0 based on chosen arms as well as the corresponding received rewards (æ,, 'r ]re(t-1]+ also denote the imaginary corruption-free parameters p.-1 which is trained with the chosen arms along with their unknown corruption-five ffre rewards {æ,, 7r rre(t-1]. 1]. for the sake of analysis.
C.2.1 Decomposing the single-round regret
To bound the single-round regret RG, first decompose the objective into several individual terms, and then bound them individually. For reference, the parameters 0,-1, covariance matrix Σ,-1 1. confidence ellipsoid C.-1. and weights w, pertain to the chosen arm 2t, with the arm index i E [K] omitted for simplicity of notation.
Arm selection scores, First, recall that based on the arm pulling mechanism (line 13, Algorithm I and the benefit score (6) (Lemma C.IT), the chosen arm æt X, selected by
[ari, 02,1-1) Ma-1 v Va O2.-1) ET,- 100.1,9001.1 O2.-- 1)-m1)/mmm
at. arg max E.,,
arg max Uwx,),, E.
where we denote the corresponding score shorthand as
U = f 02,--1) + M ga (i. 1957-19((0,,, ( 0
(C.2)
Analogously, with 0 being the parameters trained set of chosen arms and the corre- sponding corruption- rewards, we denote
( f 0,,-1) + 7 V Va 01,--1 19(2 ( 02.-1).
(C.3)
with corresponding covariance matrix Σ AI+ Ereetn w g( ) 01-1)
and the coefficient 7 based on Σ following the definition from (6. obvious that the arm selection depends on the trained network parameters, and thus if the comuptiion makes the makes the trained network parameters 0 deviate from the corruption-fiet ones 0 i it will lead to discrepancy in terms of arm selection decisions.
Alternative forms of selection scores. On the other hand, to maintain the consistency with the form of (..I in Lemma C.I we can consider an alternative form of arm selection being
V( = (g(w), 0o), O-t-1 - 0n) + 7ht-1 / /g 12.- 1 (x Oi.-1)/m
(C.4)
max OEC,.-1
(g(2),ri0)) 00), 0 0o)
24

---

where we have Cj.r-1 := {0: |0 01.--1lz.... S Vm..1//vm76..-1 Yst-1 0} being the confi-
dence ellipsoid of for the actual trained parameters -,,--1. trained with possibly corrupted records. 7i,t-1 0 represents the radius of the confidence ellipsoid; and the last equality in (C.4) is due
to maxx:|l=blasse x) (a, b) + c. VYTA-LL. [86]. Analogously, for the corruption-free
parameters -, we also define its confidence ellipsoid C,,-- = {0 ||0 0
7.t-1/ / Vm, h, > 0). with 7 > 0 being the radius of the confidence ellipsoid, and by Lemma C.10 we will have 0" C1a--1. As result, we can also formulate an alternative form for arm selection as
(a (g( 0o), 0i.--1 - 0o) + -i,-11 V Vi(ar, Oir 1) 10 Ost-1)/m (C.5)
= max (g(x;,,;; 0o), 0 -n)- Gcc...1
Here, the radius of the confidence ellipsoid for the corruption parameters N,,-,, is provided in Lemma C.10 ensuring that 0* E - On the other hand, deriving the radius for the trained model, Ti,t-1 in face of potential corruptions, considerably more challenging. With our carefully designed arm weights in 4 we manage establish the updated confidence ellipsoid in Lemma C.12 along with the corresponding UCB for reward estimation (Lemma C.I1I.
Note that our UCB- based exploration score (6) is also motivated by Lemma C.II For specific arm Fi E X₁ our UCB-type exploration score includes only terms related 2i,r, omitting constant and arm-invariant parts. This approach is intuitive, arm-independent terms do not influence arm selection (line 13, Algorithm|] [ and they will remain the same across candidate arms X, Moreover, with sufficiently large network width as in Theorem 5.6 majority of these terms can be further reduced to (1).
Decomposing the single-round objective. Up to the time step / E [T), denoting 2z, 2 E X₂ being the chosen arm and the optimal arm each round respectively, we will have the corresponding regret bound for step as:
R₂ = min h(x;)) h(xx)), }
h(x;)) ((xx)) V(xx)) - h(zx), 1
min
(C.6)
(x,)
min (C:: + k(xa)) - V ((xx) + V ((xe) - (xx)) }
JR]
IRg
where the first equality is because have the expected rewards in bounded value range [0, 1]. Here, with the three terms after decomposing the single-round regret R2, we can bound the first term (c,) with Lemma C.9 while bounding the terms TR, and IR, with Lemma and Lemma C.4 respectively.
C.3 Bounding cumulative regret R(T) (Proof of Theorem 5.6
First, we would like to mention that since both the expected corrupted reward TR(r] and the expected corruption-fre reward E fall within the range [0, 1). as defined in ( follows that C S T. In this case, long the network width requirement m ((poly(T)) in Theorem 5.6 adequately satisfied, this naturally implies m 2 ((poly(C, with a sufficiently large network width m. This also indicates that knowledge of C' is not mandatory for setting m before the online learning process begins. The above clarification will also be used to establish the final regret bound.
Then, with the derived results in terms of single-round regret R,, [T]. we can then proceed to bound the cumulative regret over T rounds. By definition in (C.6). we have
R(T) = Er= min (C: + h(x7) vxx,) + V (x:) - Vax)) }
Recall that the first term
18.
UCB,(x)) can be bounded with Lemma C.9 while we bound the other two error terms IR, and I
25

---

with Lemma C.6 and Lemma C.4
respectively. Next, with the conclusions from above lemmas, we
will have
R(T) min (3:) + h(a;)) - V( + ((xe) V(xe)) 1
1R1
Jnz
T
min
2- . 119(21;;; 0,-1)/vm 1,1 + 0 02-10//11/
x
1m1
+ +O(aC)
0(
+O(VAS)
g(ãx: 0 1//--1//
12 12--1)11 )
+O(aC)
| θ, 1m
+ +V(Ss)
g( 0 )/ mm
(2,-1)
(2,-1)
+ Om
2/3 2/3 log(m))
7/ (1(mm))27220 5/3 (1/A)
O(m 1/6
log(m)) (
サリ - 10
1/12 log"
1/4
(m)
3,5/00 x- -7/12)
+ - 0 1//,1///////6//-1 |7 llg(m)
7- 101
log /4 (m) L42 O0 2/3
log( log(m) //3 5/3 55/3(1 v1/A)), 1
where "weight-free" covariance matrices are =I p(r (0-;; 0
and - = AI g (0( 0 - 1 1/m. Afterwards, with sufficient network width m that satisfies the conditions in Theorem 5.6 the majority of the terms the RHS of (C.7).
which contain m to the negative order, can be reduced to O(1). Thus, we will then have
R(T) < 0(1) + Σ min 25 0l1m/;:-11//mmm
بد: 2--1 1Ilg(a; 0,-1 /
+O(aC)
g(0,; 02 0..10//vn m
+O(VAS)
g(ăz; 0 (--1)~11
((-1)--1
|
+O(AC)
g( Or mmmmm
+ +(VVS))
(2.-1)-1
(---))
Σ min 27 |g( 0 0-14:/11///1l533: + 119(x,;; // 1
<0(1) +
T
+((C))
min
0((x;;0-1)))
(E-1))-1
T
+O(VAS)
T
min
g( 0: 00 )/ m
+0(VAS)
T
Σ 0(11/mm (8--))-
min
1
(C.7)
where the second inequality is by applying the triangular inequality. Then, denote Wmin min((w?") (n(") in, )eep). Analogously, we also have the round-wise minimum weight value
being wiin (in he(K),=[[--]] x² < Vt [T]. which will be used to determine
scaling parameter With our notation from Theorem 5.6 this intuitively leads to o. As
26

---

result, we can therefore have
T
Σ min 2 [1,( ب + (a2,, x 1
llog det(AI) + +((Vs)) VT det det(En) (xr)
det det(En) ETr
det()I) + O(VAS) Vog det Eiy)
+O -008-~x2))
+
det(AI)
T
00
Σ
min 2/-1 : |1g(2;;; 0, 1/ 5,1 + 11 02-1)/ E,
1=1
+0 x(2)-1x²)
T
00
min
|l 222; 01-1)/ 1.11
Wmin
T
x }}
Σ
min
Wmin
- -C(BB-1 d'lo(( (K/))++T//)+((///))
Tdlog(1 T//A)
(C.8)
where the first inequality is because the auxiliary matrices Σ and Σ do not involve arm weights, thus we can directly applying the Lemma G.7 and Lemma G.6 The second incquality is by applying Meanwhile, since E/ is not defined w.r.t. randomly initialized Oo. we additional apply the Lemma G.6 in terms of the matrix determinant difference to derive the results, where the extra term will also be reduced to (1) with sufficiently large Afterwards, for the rest of the summation terms in C.8).
Lemma C.2
we can have
fT Wmin
R(T) S 0
T min
|I (iinggg 1/-1)//
T
1
TT
T
min
Wmin
t=1
+ OCC (22) dlog(1 +K/A)+ O(VAS) V Tálog(1 TK/TK// /A) + 0(1)
+
(el(ET) det(AI)
del(ET) 2 2oog(0) + 21/25)
(
2 log(() + x1/25 - / V1o8 det(AI)
Wmin
Tālog(1 + TK/AA)
+ OCB3~+22 Tlog(1 + +TK/A) + ( +O(AS))
+ 0(1
det(E
11/25 + v 1108 det(AI) + (1am=)//1// log(E)
Wmin
del (2(1))
+ +u log
2log()) Tálog(1 + TK/A)
dxI(
+ OC(B-1122) dlog(1 TK/A) +
V Tdlog(1+TK/N) + O(1),
(C.9)
where the second inequality is by applying Lemma G.7 and Lemma
as well as the definition
of coefficients "r, Tr, along with the fact that 7r 2 Ye, Tr Te, t T]. The last inequality is
by applying Lemma G.6 With sufficiently large network width m as in Theorem 5.6 we can have
1/6) Om L 11/6) < O(1). Then, due to the fact that Σ Σ Σ T applying
(0)
T
27

---

the Lemma C.2 it will then lead to
R(T) s
1
o
"V d'log(1 TK/A) 2log(0) + 11255 Tàlog(1+ +
v /imin
+ +O n²) ( (11)
(C.10)
- <0 uV álog(1 + +KK/A) log(()) + +1125) VT + TK/A)/n2
+O dn' + TK/A))
where the second inequality is by setting the tunable parameter a in each round accordingly, in order to ensure Wmin x² < 1. Here, we remind that our regret analysis does not require the learner know the minimum fraction value 3 before the online learning process, where = [7] min (frac, (2x; 1) frac, X;, 1 As we have mentioned, in practice, the learner can scale the a values in each round make sure the round-wia minimum
weight value withh = min(w)7 ]ee = x² < 1, At E [7] (Subsec. B.5)
C.4 Auxiliary sequences: Regression parameters and gradient descent parameters
To bridge neural models with NTK regression, we have two different routes to decouple the effects of adversarial corruptions from the received arm rewards. First, we define the gradient- gradient-based ridge regression parameters specific to a candidate arm Tú E X, in round t E [T], as
( 2
+
Σ re(t-1]
(T) Witt g x 0o) g( 0o)T/m
Ea1-1= +I+ Σ
wii g(x, 0 0,-1) g( 11 /m,
rE(L-1]
Σ AI Σ
1i g( 0--1) g( 0.-1
1E(L-11
(0) = Σ
(T) (xr;; On) .rt/ .rt/mm,
bi
w ((xx;; r /m,
1,1-1
rE(t-1]
rE(t-1]
bitt-
-00
Σ
(T) " g(z,; -it//mm
b
(T) iit g 0 0--1) Vm,
rE(t-1]
(C.11)
where fer, Tr F E [t] respectively stand for the chosen amms as well as their rewards. while (ar, J. T [1] refer to chosen arms and their imaginary corruption- rewards. For notation simplicity, we use w. (r) it 1] to denote the arm weights for 2t..
Meanwhile, given an candidate arm Fi,t E X, with weight w defined in to bound the /2 term by decomposing the adversarial corruptions with a series auxiliary gradient sequences (0,, (1) ..... (J)) (1),..,((())
try
in Lemma D.1 such that for j-th iteration
e (++1) O n7. ())) W. (()))) - 0o) - v) + m)) - 00))
as well as an analogous sequence for corruption-fret parameters
(i+1) 2 (i)
.7. (0) W (())))
()) - 00) -)- + m - On)
where J = (g( 0o), g(rz 0o), .o.. g( 0o)) E (R) and W refers to the diagonal matrix of arm weights (w(77) ) -ej along with the reward vectors y. ÿ R!-1 separately being the vector of received rewards and corruption-free rewards. In particular, with [ being the 7-th column of matrix (0), the auxiliary sequence e (7) can be decmed applying Gradient Descent to
28

---

solve the following optimization problem
min [())=
Σ
(r) wit
[ 0n) V/r md o On
1
|0
(C.12)
rE[t-1]
Analogously, we can also derive the optimization problem for the sequence of corruption-free
auxiliary parameters 2 by applying the same definition of weight matrix W. Since the arm weights by definition, we will also have the diagonal matrix norm [| S 1.
Notation simplicity. For reference, we remind that the parameters 0 covariance matrix Σ/-1- confidence ellipsoid C.-1. and weights w, pertain to the chosen æt. with the arm index i [K] omitted for simplicity of notation. Meanwhile, the gradinet covariance matrix Σi,--1 confidence ellipsoid C, and weights W4,t are associated with each candidate mi, for [K].
C.5 Bounding the error term RR, in (C.6)
Recall that derive the upper bound for the single-round regret R2, we need to respectively bound the three error terms on the RHS of (C.6). Here, we first bound term Ix with the following Lemma
Lemma C.4. Suppose the imaginary neural network f(: in round [T) has been trained on corruption-free rewards (x,,Fr)reje
Meanwhile, f((-) is an L-layer FC network with width m.
Suppose we have m, nn satisfying the conditions Theorem 5.6 Then, for the chosen arm æ, E Nr. with the probability at least 1 6, we will have
IRg =V(x)) V(x.)
7h-1 ( 0 01-1)/ E2 + O(m -1/6 1/6 100
+ +((a))
((1m);01-10 0(11;;0--1//mm
+ +O(AX8) g( 0-11/
(2.-1)-
(1-1)-1
+ 0(m log(m) 1/7/2 3/3(1 + v1/A)) + O(Cm (log(m)(
+ 1(Cmm 1/6 (lg(mm) 1/6
+ +0 1/6 / llg((m))) 2/33 2t 2/3 2/3 17/2).
By definition, we have 7/- (v log det il - 2 (og(6) + x122)), as well as the gradient det(Ai)
covariance matrix Σ,-1 = +I E (x 0-- )g( (rr; 0 1-- /mm The minimum round-wise arm weight wiinn min(w:?7 (7) [E((]) x² < 1, Vt E [T] by scaling parameter a.
Proof. For the error term LR., we have
In. V(x,) (xx)
max (g 0o), 0o) max (g(x;; 0u), Ø 0p) BEC.-1
< max (g(;;; 0o), 0 - 0o) (g(0;; 0n), 0,-1 - 0o) DEC,-1
max (2:;; 0o), 0 0o) (g(2:; 0.-1), 1), 0,1 0o) 00 (og(m))2333 -2/3 1/13 BEC.-1
max (g (x;; 0,), 0.11) (g(a;; 0 0,-1), 0.1 - 0.-1) + Om 1/6 Vlo(m))(2/3 2/3 1,/2) BEC.-1
max (2:; 0o), 0 0. 1) (g(# O 0,1 0.-1 O(m 11/6 BEC,
1/6 ( 1
Projection difference
(C.
where the first inequality is because of the definition of confidence ellipsoids Č.-1 and C,-1. The second incquality is by applying Lemma G.3 and Lemma G.4 Here, have the first term
29

---

the RHS is bounded by Corollary C.5 difference, between the confidence ellipsoid center parameters - and the other parameters in this confidence ellipsoid 0 E C--1- Meanwhile, term 12 will be bounded by Corollary C.8
where this term is used to represent the gradient projection
Corollary C.5. Suppose the imaginary neural network [(:: (1:0)=11) 1) in round l. E [T] has been trained on corruption-free rewards {æ+ TT re]t--- Meanwhile, f()) is an L--aaer FC network with width
m. Suppose we have m, J.n satisfying the conditions in Theorem 5.6 Then, for the chosen arm
2t E X,, with the probability at least - we will have
max (g(0;; 0o). 0.-1) 4-1 l1g(a, 0,-1)/ h 1 + +mm 1/6 /log(m)d/00--10022)) BEC:
and the corresponding summaatin value being
Σ
min
max DEC:-1
(g( 0o), 0.-1),13
xE[T]
log O "
det ET)
+ del (AI) - 2 -)log())+ +
27 log det(Er)
min
det((A)
+ O(Sm 1/6 Vlog(m)T 7/6 1 + Omm 1/6 /log(m)mT// T/6 (
By definition, we have the radius of Ct-1 being Yt- = O log det(Ex-1) log (6) + \1/25),
det(Al]
and the gradient covariance matrix Σ, = XI ErE(t-1) w, g (x f 1190)-1-1((2::0 0- /mm
Proof. The proof of this corollary follows an analogous approach as Lemma C.9 By definition, we have the gradient inner product for the chosen arm æ; round as
max (g(ar;; 0o), 0 - 00-1) OEC,
S max |0 - 0. 02-11/ (a:;; 0p) 00)
(C.14)
OEC.-1
%-11 |1 0t-1)/ Vmll جحح + O0m \o
where the first inequality due to Holder's inequality. The second inequality by applying the definition of confidence ellipsoid C,-1, well as Lemma (G.4] and Lemma G.6] Then, similarly, we will also need to bound the summation over T' rounds. Following an analogous procedure as in Lemma
C.9
we will have
Σ SE[2]
min max (g(2;; 0o), 0 0.-1), 1}
BEC.-1
0
(2v
log det(XI) 2lgg(5) + +
det (Er)
2T log deti [Er
min
det(AI)
+ O0Sm 1/6 /log(m))"/00x11000222
1/1 + O - 1/6 Vlog(m))" 7/6 7/6 2//)).
By the definition 3 = min [min (min (x,; N₁. E,-1), frac, (ã.; Nr E,-1)} we have the lower bound of arm weights being w:min > a- B. Note that we also scale the parameter to ensure wiminn = 2 as indicated in the Subsec. B.5 which requires no prior knowledge for 3.
C.6 Bounding the error term IR, in (C.6)
In this subsection, we bound the error term Ix, (C.6). with the following Lemma C.6
Meanwhile, denote extra weight-free gradient covariance matrix for the chosen arms [2, )re() of the corruption-free model. The corresponding arm index denoted i,, t [T], such that xi, Tt-
Lemma C.6. Suppose the imaginary neural network f(::0 (.;00-1) in round E (T) has been trained on corruption-free rewards {x,, Fr ]r((t-1), Meanwhile, f()) is L-layer FC network with width m.
30

---

Suppose we have m, Jn satisfying the conditions in Theorem 5.6 Then, for the chosen arm æt E Nx. with the probability at least 6. we will have
IR, l((x;) V(x))
$ 0(aC)
+O(Vi5)
g 0 1,1
(x(_1)-1
+ +0(m lm (55 + vt/1)) +0 1/6 1/0/ (t) 110011
+ +0 1/6 (log(m)t 10
(/lgmmm)////(mm///// -00
+1 O( 1/12 log (m)_1,106>> 17/23
+ n 0 (m (00l0/
+ Om 2/3 /lo(m))l + +0 - 7/6 /lg(m))
+ - Om 1/12,7/12 13/12 log
1/4 (m))
By definition, we have the coefficient M,,t-1 = Ovv log det(Al) 2 log(6) + 11) as well as the gradient covariance matrices 1 = Al + ErE(-11 g(Ø+; 0 1) 02 1- / /mm, and Et Al E) - ()(r)))(()))-00 0 The minimum round-wise arm weight with = min(w |E = x² < 1, Vt E [T] by scaling parameter a.
det
--1) det
Proof. By definition, we can have TR. h(x;)) ( + Uxx,) V(x;). Here, in terms of the distance between ( and V ( given a candidate arm æi,t E Xr, we have
(((,,))) V(xx,1) [f( 1 (g(2),,; 0o), 0i,1-1 - -ooi
S (s 0,, (g( Oi, 02,-11 -0o
+ (g( 01, )), 0 0o) (g(0),,1; 0o), 0i,,-1 - -
50 1/6 (log(m)(223 2/3 1,3) + mm- 1/3 2/3 (log(m) 1. 1.7/2)..
where the first inequality by triangular inequality, and the second inequality is by applying a similar approach as in (B. from [86] as well as Lemma G.4 Next, we proceed to bound term 7 RR Here, for candidate arm Vi,t E Xr and the associated corruption-free confidence ellipsoid C,,- we have 0" E C based on Lemma C.10 Thus, with ã; = arg max Vzx,,. being the arm chosen by the corruption-free neural model, with the highest score V(x,), there will be JR. h(x²) ((x.) + U(x:) - V(x;;)
(1( 0o), 0- 0p) - U(x,) + (xx)) - V(x;)
S max
(g(z); 0o), 0 0o) U(z,) U(xz) V(x;)
BEC
S max (,; 0o). 0 Oo) - Un:)) + U(x.) V( -
where Cr 1- refers to the confidence ellipsoid of corruption-free parameters 0 associated to arm T; E X₁. Afterwards, it further leads to
TRi < max (g( 0o), 0 0o) U(x²) bEC,
+ O(m 1/6 v log(m))( x + ( - (10m=1100003322//11111/
2/3 Vlog(m)1.72
max
(9(5,; 0o), 0 0o) V(x,)
icC
+ +0 1/8 /logmm)2233 2/3 (3) + 0(m 1100g/22 2/3 1
< max
(9(3,; 0o), Ô- 0o) -V(z.)
0EC
+ O(m 1/6 [lg(m))2233 2/3 x 2/3 2/3 + 10 1))
= v(a.) - V(x)) + Om
2/3 - [
2//
Vlog(m)
31

---

To bound the output difference between V( and V (xta.) for an arm Di,s, we can decompose them into separate terms. Recall the definition of V(.) in (C.4). and we can also define the analogous (()) by applying the corruption-free parameters and covariance matrix Σ. Therefore, for arm Ci, Xr, we have
V( V(x.,) $ (V(as,,) ((0) + (V(0) (at.)) ( (x..))+ (V(00 V (x
(C.15)
where for the sake of analysis, we define two variants with randomly initialized parameters to being: Vi (x:,a) (g(o 0o), 0:-1- 0o) + 7-11 Va 0o) To) g( 0n) /m, and ( = ( 0o). 0,-1 0o) + 7--1 V g( 0o) (2,1) - a 0o)/m /m. With this result, our objective then is to derive the upper bounds for the three terms on the RHS of (C.15).
Bounding the second term (10 (x;,)) in (C.15). For the second term, we have
(x;,)) - (-)) (Ii,+))
$ (9( 0o). 0i,-1 - 01,1-1)
+ h V (( (oct,,i00T((22) (
(0) g( 00)mm - - V /( 0u) (0) (g0-)))))99_0_,
:( 0u)/ml
(9( 0o). 01,111 01,1-1)) 1 7r,-11 V (o)
00)/m
S (9( 0o). 0i,--1 0 (
-
Due to the fact that Ivā - vbl s v laa- bj, based on the definition of 74.-1 and Ti,--1, we will have
ha--1- - 7r--1 S V O
O( 1 1/6 /10g(m
log( det Et,c-1 log( det Eg
det + log( det Eo,
log( det Σ det AI det AI
det
Sv. V 1+ (( 1/6 1m-1/ (1000 O(m 1/12 log 1/4 3 -1/12).
based on Lemma G.6 Therefore, we will end up with
(x.,, - (((0) (xx))) s ( 0o), Ou.-1 - 0i.-1)1
+v. v 1 1( 1/6 0 L Omm-1/12
1/12 log 1/4 (///// (7/12))
Bounding Term [V(a,,)) (()) and term (1 (* in C..5 On the other hand, for the first term on the RHS, (V (0))
(00 (zx,)). we can bound this difference term by
V(a..))
( (a.,))
7t.1-
01.-1) (1 001100))) -V Vglz, (x) g 0o)
Vm
1
[19 0 0,,-- - ||o(0), 00)
00)1( --))))))))
Vm
1
||9( 1 2 : - + 11g(x1,(:00) - g( :: 0 b.1-vحl 1--
Vm
< Om
1/021/0
(lo((m)L712) +
0 - 11g(2,,0; O ا) إia ,)-1
Vm
32

---

I O(m 1/6 V /log(m)2733)
7,,-1
1) g O (1 D ( 02,1-1) g( (( g( 0i,e-
+
mm
/17 + nie- I O( 00mm-1/6,1/6 77/ 7/6
//6,1/62
(V
- 1
mm
O(m 1/001///,//00---111 /log(m)
1i,111 vm
(((00)::00-1)) Oar-1), - (2) Ei,e-1) (2 (2
g( 0it-1))
I <00m= (/mm-1/61/0x-111 7/6 Vlo((m) 1./2) + Ma-1 O(m 1/12,/122 13/12 1og (m))
where the first inequality is because of the triangular inequality. The second inequality is by applying Lemma G.4 The third inequality is again the application of triangular inequality, and the last inequality is the application of Lemma G.6 Since the similar procedure can also be applied to bound the third term [/(0 (2x.,) - () after summing up the results, we will have
(a,,), (00) (xt,)), (V:00 (x:..) (ax.)))
s (m - 2// 2/3 (log(m)) 00 1/0 7/0 (l0g(m)L313) 7,,-1 0/m-1//277/222-1133 log (m))
Summing up results. Combining the results, we finally have the upper bound for In, being
IR. $ Kg(T 0o).
0 0 ...0-1>1 サレ
-0 1/12 10mm00(mm000)) 1/1 (m) 7/12)
+ 00 -/ - Vlog(m)L7
+ 00 -1/66/66
+ - - 10__11/311111(mmm1m111 (2)
< Ko(0;; 0 (,,1-11: 0 i,,1-1
0 1.,11>1
+ サリ / 1/6
1/6 log( m
-477/0
7/6) O(m 11/211111 1/4 (m) //5
>/00 x7/12)
+ 0(m 1/6 (og(m))
-7/6 + Omm 2/3 Vlg(mm) O(m -1/6,2/6--77 7/6 /lg((m)
+ 7,,--1 0 0mm log (og
and therefore we can formulate our objective to bound as
JR, S (g( 1), 0 0 0 0
+ v 1 1/6 7/7 -0000000mm/--m0 1112 log' 3
+ O(m 1/6,2/1////1221111 (/000)/)22//lllgm 00 -1011111666-77// 10m00//)00000000000000000010>1>-
Vlog(m)
+ 7,,t11 0 1/12/ 188))
(C.16)
where we recall that is the pre-defined exploration parameter that echoes the sub-Gaussian noise variance proxy. Finally, using the upper bound for term I from Lemma C.7 will finish the proof.
C.7 Bounding the terms I,, Iz
Here, we see that there are still two terms in Re, t E [T] that need to be bounded, which are
I = (g(ă) 0 0,,0-1), 0i,0-1 - -0,,-))
Iz = (g(x;; 0,11), θ.-1 - -0-1))
33

---

where we recall 2t E Xr is the actual chosen arm that is selected by the corrupted model 0t-1- while have H. E X₂ being the imaginary b chosen by the corruption-fied model 0z-1- In this subsection, the error term I will be bounded by Lemma C.7 while term Iz will be bounded by Corollary C.8
Recap auxiliary parameter definitions. With definitions in Subsection C.4 we can have two different alternatives to decouple the adversarial corruptions from arm rewards: (i) the gradient-based regression parameters; and, (ii) the auxiliary sequence of gradient descent. For reference, recall that we denote the series of gradient-based regression parameters, specified to candidate arm Li, c Xx
as
20 2,,-1 +
Σ
wL g(0r;;(0)) 00)=::00)//
TE
E AI
Σ
(r) wi g(æri 0 ((-rr:0-11]T/ /mm
(0)
Σ
(7)
g( 0o) Tr/ rr//m,
b =
E rE(r-1]
w g((x;00-11) - TT/ r
TE(--1]
6
-0)
Σ
(7) w g( 0o) Fr/ 7
6 = Σ
Wint g( 11) - /
r](
re[t-1]
where (ær, J. E [t] respectively stands for the chosen arms as well as their received rewards, _ while Tr), E [t] refer to the imaginary corruption -free rewards.
We also recall that with the chosen arm æ; E X2 round t with arm weights wfrh) T E [tt- 1], defined in 4. we will have a series of auxiliary gradient sequences {Og, @ ,..., @ ( as in Lemma D.1 such that for j-th, j [J], iteration
( (6) n7 ( ((J Oo) - 3) + mA(0 00)
where the diagonal weight matrix is made up with the arm weights, W = ((t-1)x(t-11) Similarly, we will also have the sequence definition for corruption- free parameters (++1)
(T) dieg((())))) E
= -
())
77- ((0). ( () -00)-9) -) + m (i) 0o) along with the Jacobian
matrix (() (0x;;; Oo), g(:;; oo).... (x 0)) (I-((-1)) Here, we have y. ÿ R separately being the vector of received rewards and that of the imaginary corruption-free rewards.
In particular, with []()) being the r-th column of matrix ( the auxiliary sequence ( can be deemed applying Gradient Descent to solve the following optimization problem
min L(O) = Σ 6
Σ 2
w
[ T - 0o) VT it
2
+
1
mm
O
2
rE(t-1]
Consequently, we can follow an analogous approach as in Lemma D.T with the above optimization problem, to bound the difference between gradient-based parameters and the auxiliary sequence.
C.7.1 Bounding the error term Ij
We bound the error term using Lemma C77 Following the notation in the main body, let 0,-1 denote the trained parameters associated with the chosen arm æt, and let 0 0- represent the trained parameters of the arm ã. ai i E [T',, which corresponds to the chosen arm of the hypothetical corruption- ceruption-frre model f(; 0). Additionally, we define a weight- free gradient covariance matrix for the arm collection { Trelt containing arms selected by the corruption- free model, which will be denoted by Σ/1 = AI + Ere:-1 g( 1) O
Lemma C.7. Suppose the imaginary corruption neural network f-::0,,-1) (0,1-1).for for arm æ., E X, has been trained corruption-fiee rewards {z,, Fr )re(--I) while the other trained network f(; 0,,-1) is trained on the received records (r Suppose f(-) is an L-layer FC
34

---

network with width m that satisfies the conditions in Theorem 5.6 Then, for the arms It, Te E N'. with the probability at least 6. we will have
1 (g( 00 0...-1). 0i1,s-1- 0 1e,
< O((C):
| (014:00-))//1
pf (,.t://...)///// (2/_,) + O(VAS)
(E,-1)
+ Om 2/3 log(m) L7 5/3 vt/A)) + +0(Cm 1/6 (logmm)t 7 X 1116 L5)
+
where 0,-1 are the parameters associated chosen 3t, and 0 i,,t-1 are those parameters of arm
Tt. The gradient matrix is defined Σ XI + E -- ( - ( o..r-1)1 //m, and we also have Σ, = + Er g (. 0- g xr;
1
Proof. Since the only difference between term 1 and term 12 is the gradients w.r.t. different arms, we begin with term /1 (a 12-1), 0 - 0 0(-1), and the results can be readily generalized to term 12. Here, recall that we have -10 Oel it S 9// / based on Lemma C.10, as well as
10. 00l12: |00 Ooll2 s O O(vt/m²) based on lemma G.3
Simplifying the notation. For the following proof, for the sake of notation simplicity, we directly
use θ
(J) to respectively represent @ -: (J)) fr,t-1' which are the gradient descent based
parameters associated with the arm ã₁ On the other hand, for the terms that belong to arm ã; = ii. we use 0% Di, and b, to separately represent 0: f,,r-1: i and b i,,-- by omitted the subscript of time step t. to simplify the notation.
Afterwards, it can further lead to
h
(g(3);; 0i,), i 0
(g( 0;,), 0i 0('1)| + (a(Trr 0i)), σ0 - + (g(ārr 0:), ã -
h.
0m 2/3 log(m) 553 + v1/A)) (a(T) 02,), O ( 3
where the first inequality is due to triangular inequality, and the last inequality is by applying Lemma C.4 in [86). with the optimization problem being (C.12) which bounds the difference between gradient-based parameters and the auxiliary sequence. Here, term IT.1 measures the distance between the auxiliary sequence trained with corrupted records, and that trained by imaginary corruption-free records.
Next, recall that with randomly initialized network parameters Og. we can formulate the least (0)
square parameters as (>) -1b)))))))))) //m, while the least square parameters trained by corruption-free
rewards are analogously denoted by (I. ) (0) //mi. In this case, the term /I. can be alternatively transformed to
g (Txr 0,), (J) - )
111
g g( 02),, (0()) - -0, - (z. ) (0) //m) -m)@"
-
-6 (J)
-o - -
- \Vm)
(( 0.),, (J) 0 - E (0) 1
1 (0) \/m
+ 0g 02), ② (J)
0, (0)
//m
35

---

which further leads to
11.1 < (p(ze; (11) - 0n - -xx -100 !000 \/m m
g(tr; (0) 00 -22 -bb //mm m
(0)
(C.17)
g(0rr 0z)), 12)))--11
Σ
w fe,t
g(tr;; 0o) cx) cr)/m)
7E[0-1]
11.2
where the inequality is due to the definition of gradient-based regression parameters and triangular inequality. It is obvious that for the third term on the RHS, the only thing we have control on is 0; When trying to bound the first two terms on the RHS for the arm Tt, we can first apply Holder's inequality with Σ for the purpose of analysis and different from previous ones defined in (C.IT) the new matrix (E/_1) contains gradients of the sequenee of arms [ā+)re|--1] chosen by the corruption free model 0(;00-1),, E [t- I]. with the parameters 0,-1, E [ [1-1] 1].
AI Ere[(-1] g 0 (1).==1)((E;; 0
) /mm. Note that
In this case, we use the Holder's inequality to the first term on the RHS of (C.17) as
g (5 0.)).
0o - E (0)
//mm
- (g 0
m
Vm
| 0, - (2,
[ 1)
< gg( 0;,)/
Vm 1/-1/000 (J) 00 - (2 (0)
(E Dll2
= 1g( 0.,)/
( 0(A + tL) Vm 0.)
Σ 00) b l12
< (g( 0; \/vml
(E O(VA+tL)
0 (1 mMM) 11/1 + m 1/6 -1/6 /log(m))77/2///5 5/3 v(/A)
~110( 0z // / (2) 1 O(VAS)
where the first two inequalities are by the Holder's inequality and Cauchy-Schwartz inequality. The third inequality is by Lemma G.6) The fourth inequality is by applying Lemma D.1, with the optimization problem being (C.12) bounding the difference between gradient-based parameters and the auxiliary sequence. Finally, with w, I 1 and the conditions in Theorem [.6] applying the conclusion from Remark 4.7 in (86) will give the last inequality. Following a similar approach can also lead to the identical upper bound for the second term on the RHS of (C.17).
Bounding Term I12 Based on Arm Weights. Next, we proceed to bound term I12. Recall that we need to derive the upper bound for the following term
g(0+;;0)) (0)))))mm))))) )
112
g g( 0,),,
(T) htt
TE|r-11
g 0 (2
00)
w (r)
g(xr; 0o) c mm/
i,t
rE(t-1] 1]
g( 0 )r w (> 100) - g( 0 (.-1)c//m)
rE(t-1] 1]
g(i:; 0.), w!?? (2 - - (g(x); 0u) - g(xt: 0 00-)))c/mm
+
r]
g0 0 w (2!10) g( 0 0,-1) (./m)) (mm 00Cm 1/6 VTog(m)) -7/6
TE(-11
36

---

g(ārr 0,),, O())
w ( ( "9) -./mm//mm))mmm))m) + O00mm11/ 1o
TElt-11 1
g( O.) w ((2 (=()))))((rr;(0 01-1) (.-m))mmmm))
TE(t-1]
g( w (Ex)) g( 0.-1) 0. c//m) +0(0m 1/6 Vlog(m)tt +0/Cm=1//og(mm)) 2-10/// 19)
re[(-1]
O0Cm (oog(m)t'/
where the second and fourth inequality is due to triangular inequality. The third inequality is by Lemma [.4] and the last inequality due to Lemma G.6
In particular, we aim to train separate neural models [(;; (i.)) for each candidate arm Li,t E L, such that the term 4 can be minimized. Recall that we denote Σ,- XI Ey 00 (==; 0-) /mm as the "vanilla" gradient covariance matrix without the arm weights, in terms of the potentially corrupted network parameters -1-
In this case, with u!? referring to the weight of arm 3e the above formulation of term /1.3 can be further transformed into
w. hatt
GT
g( (Ei,) - ((10::0-1))
1.33 <
-E|t-1
(Ix))² g(xx;; 1-1 m
w. ict
Cr
rE(r-
(2;
Σ
w. Cj
9 2 0 1/ m
g(xr; 0,/1 vm
rE(--1] !]
(x1,)-1 -1
12 )-1
Σ
w
ted
Cr
g ( 0 m/mm
(((x;;,--)//
(m)
-E[L-1]
<aC
min =E\is
g(x; 02 1/-1)///// vm
(--1)-1
saC. (o(or;0e-1)/
(E.-1)
where the first inequality follows from applying Holder's inequality, and the second and third
inequalities obtained by using Lemma G.8 along with the fact that Σ, - ž { by definition. The last two inequalities derived from the definition of the arm weight w and the corruption level C = Eiery |ct] Recall that for each arm t; E X,, we define its weight as
a- min (1)(=:0) 1-1 =xx;
where 0 is the tunable parameter. As result, (0 min 1, s- (00 // ((())-)
we will have the upper bound for I1.2, being
1.250(a00
|0 ((1x);0-11// m
O(C 1/6 /oonn/////oo///////
/log(m)t7/>> -
(E--))
+ O0 V
(2) 1/ -
In this case, since the weights are lower bounded by x², the only way to ensure this is by adjusting the tunable parameter 0 accordingly. We remind that this does not require the learner to have global view the minimum fraction value B. In practice, the learner can adjust the a values each
round to ensure that the round-wise minimum weight value mii min ( He(K] = x² < 1, for
(T)
37

---

all t E [T] and T E it - 1], by tuning the parameter a. By summing up all the results, we obtain the single-round bound for term 41 which leads
4 - O(aC)
( 02-1)/
+ +O(VAS) | fi ii.o0-)///v
( 1)-
12/ 1)-
Omm 2/3 log(m) 1. 55 v(/A)) O(Cm 1/6 1/6 /
Vlog(m)( +00Cm=///og(mm -
+ +0Cm 116 1/6
(C.18)
C.7.2 Bounding the error term Ig
Similarly, for the term 1g related to the chosen arm I; E Xr we can follow the below procedure to obtain comparable bound for term I1.
Corollary C.8. Suppose the imaginary corruption-fie neural network f-; (1,1 for amm Ti, E X has been trained on corruption-free rewards {x,, Fr [r] f(-) is an L-layer FC network with
width m that satisfy the conditions in Theorem 5.6
Then, for the chosen arm at E Nx, with the
probability at least 8, we will have
$ O(CC) [((z; 0111:/0-1)//m
(VAS)) 0(0z:0
(E.-1)-
5/3 5/3 (1+ vt/A)) +0(0m 1/6 Vlog(m)t 7/00 x-1/655) O(mm 2/3 log(m) 5//
+ +0 1/6 log(m)e 10
where 0 are the trained parameters associated to chosen arm æ. X₂ in round 1, and a- are the trained parameters of arm Tt. along with the corresponding weight-free gradient covariance matrix E; = AI Ere(t-1) g( 0 -1; /mm.
Proof. The proof of this corollary follows an analogous procedure as in Lemma C.7
and (d) to represent the gradient descent-based parameters associated with the arm æt. For terms specific to the arm 2, T.,t. simplify notation by using 0,-1. E,-1. and b to denote 0,,-1 Et,t-1, and b,, respectively.
Simplifying the notation. For notation simplicity. we apply ① (J)
Then, with the simplified notation, it leads to
1 (g( 0.-1), 0.-1 01-1)
(g(x;;; 0.-1), - (g(00; 001)) (0)) - (g(2; 0--1), ( - o
12.1
O(m 2/3 2/3 loggllgm))//1 17/25/) 1-/55//33533111111 vt/A)) + (o(xx; 0,-1), _ -
1n.1
where the first inequality due to triangular inequality, and the last inequality is by applying Lemma C.4 in (86), with the optimization problem being (C.12) bounding the difference between gradient-based parameters and the auxiliary sequence.
Next, recall that with randomly initialized network parameters 0g. we can formulate the least square (0)
parameters ) -1 (1 //mm while the least square parameters trained by corruption-frec
38

---

rewards are (Σ) t-1 - - Vm. this case, the term 2211 can be alternatively transformed to
g(x;; 0-1)), θ -
121 =
g 1 O 0.- - -x -1 ///1//mm)
+ ((E)) 0--1, 5 (J) 0 (=/0)) - -1, m
(C.19)
(1(0):))11) (100);0-11, (0) ) -1 w/ g( Bo) c7)/ml)
TE|t-1] 11
J2.2
where the inequality due to the definition of gradient-based regression parameters. When trying to bound the first two terms on the RHS, we first apply Holder's inequality with Σ, AI
++EE 1j g( 0 ( 0-- )T /m, and further leads to
g 1). (J) - 0p - (-(_) 1
- |g( 0.-1)/ ( 1)-1 Vm | (J) 0
{ 1)
< | 0
( 1)-1 Vm Vm- O (2 -1 /
[ l1
< |g((zri (olor:i0-1111 11/
( 11-1 -0(++ (| 00) - --=/1)
< |g(am: 0, 11/ (E..) (O(VA+
0 (1- /// 1/6 /log(m))77//00000~00))) v(TA)
$ <119(11; 0o(0);0,-11// 0,-1)/ 1) -OVAS))
where the first two inequalities is by Holder's inequality and Cauchy-Schwartz inequality. The third inequality is by Lemma G.6 The fourth inequality is by applying [.mma.D.]] with the optimization problem being (C.12). in terms of the difference between gradient-based parameters and the auxiliary sequence. Finally, with wa < 1 and the conditions in Theorem [.6] applying the conclusion from Remark 4.7 in [86] will give the last incquality. Following similar approach can also lead the upper bound for the second term on the RHS of (C.19).
Bounding Term I2. Based Arm Weights. Next, need bound term 12.2. Recall that want to have an upper bound for the following term
0(0;;00) (.)/m)) )
12.2
g ai; O 12-1),
(
(0)
Σ
-E[t-1]
g(0;; 0,-)), (2 - g (I, 0--1) (,-1))c/mm) )
+ 00C 1/6 (/Cmmm///oolmmee/ - [4)
7/6
rE[t-1]
0(11;00-11 (E,-1) g(x;; 11 c, /m
+ +00m 1/8 /lo(mm)) 7/6
1 L4)
rE(t-1]
((xx;:111) (EE(1) -1
-.0-)))mmmmm) crlmm
+
rE|(-1]
0(11)0-11) (E--1) :((;; 0--1) c//m )
+000m-11 1/6 Vlo(mm)(7/8 11/6 -1/8
TE|t-1) 1]
Jaa
+ +0 10/0m-1/6
1/6 /00
39

---

where the first inequality is by applying the Holder's inequality, and the second and third inequalities by applying Lemma G.8 with the fact that Σ,-1 > S E(-) by definition. The last two inequalities are due to the definition of arm weight w (T) well as the definition of corruption level where the first inequality follows from applying the triangle inequality and Lemma G.4 The second inequality also due to the triangle inequality, and the last inequality follows from Lemma G.6 In particular, we aim to train separate neural models [(: O2..) for each candidate arm ai, E X, to minimize the term 2..2. Similarly, recall that - = AI + Erejt-i ( ( 0r-1)1/m
is the gradient covariance matrix without arm weights, and (T) is the weight of arm wt. defined as
a-minaex; (l0( 1)/v /mll
w (T) minf1, g-11o((e:0.-1)) (10 -
}. where a > 0 is the tunable parameter. Similar to
the derivation of term 11,,, can further lead to
w(")
(g(21;0) 0--1), (E(-1))
g((z;; ((1z::0-1))
12.3 v
m
76[(-1]
Σ
W c
(T)
g( 01-1)//m
(E(-1) 0(000g0( \m
0
FE/C-11 11
E 1-1
Ex-1
Σ
w
(7)
C
g( 02-1)) mm
gx 0--1)/v
r][t-1]
E1
E [1-1)
Σ
w
(T)
Cr
g O 01-1)/mm
g 0 01-1)/vm
FE|(-11
SaC
min #EXt
g(x; 1/-1)/ m [ 1)-1
SaC. ((1xr;0-11//1
(E--))-1
C' = Eieryy |c.]. As a result, by combining the upper bounds for the terms 12.4 and 12.5, we obtain the following upper bound for T2.2:
12. S O(aC)) (0(z; ((11//-1)//
+ O0Cm 1/6 /log(m)) 15)
1)
+ +0CC (logmm////oomm))t
(log(m)t 1/8 X/-
In this case, since we need ensure that the minimum weight is n², we scale the tunable parameter >> 0 accordingly. Recall that this does not require the learner to have the prior knowledge of the minimum fraction value B, and the learner can adjust the values in each round to ensure that the
round-wise minimum weight with = min(w (7) ]EE[K] < 1, for all t E [T] and T E [t 1]. By summing up all the results, we have
| Or 0-1)/vm
+O(VAS) |0 0(=x0m-1\Vm
1a S O(aC)
1)-1
(E(-1)-1
+ O(m 2/3 log(m / 513 vt/A)) + +0 116 (logmm))77 2 -1
+ O0Cm 1/6 Vlo((m)t -
C.8 Deriving the UCB and confidence ellipsoid for corruption-free parameters and corrupted parameters
In this subsection, we provide upper bounds for (æ+) in terms of the corruption-free param- eters 0.-1 Recall that without the arm index e [K]. the parameters 0, covariance matrix Σg-1,
40

---

confidence ellipsoid C2-1, and weights wy pertain to the chosen arm Zt. For the hypothetical corruption-free parameters 0, trained with corruption-free rewards, Lemma C.9 provides the cor- responding UCB result, and Lemma C.10 introduces the associated confidence ellipsoid. For the trained parameters 0g 1. based the received records P with potentially corrupted rewards,
Lemma C.I presents the corresponding UCB for each candidate arm æi, E A, while Lemma C.12 provides the corresponding confidence ellipsoid. Note that Lemmas [C1T and [C.12 are used solely to motivate the design of our UCB-type exploration strategy and are not applied to derive the cumulative regret analysis result.
Lemma C.9. Suppose the imaginary neural network f(:; ((:)0=-1) in round t E [T] has been trained on corruption-fiet free rewards {xx,, T Trlre(t-1] and f(-) an L-layer FC network with width m. Suppose we have m, J y satisfying the conditions in Theorem 5.6 Then, for the chosen arm æ, E Nr, with the probability at least 6, we will have
(C, = (xx)) - h(xx)) S 25--1 (1g( 00-1)/ V | + +0(Sm (00g())e/0x-1100)
+0 1/6 Vlog(m) / -
and the corresponding summation value across 'I' rounds will be
Σ 1E|T]
min (Z:).)
Σ
min (zxz) h(2,).
LE[T]
det (Er) 2log(8) + 21og(0)+ 2T log det(AI) log
det (Er)
< /
u
v Vumui
det(AI)
O(Sm 1/6 /log(mm777/0-1100222 + O(m 1/6 /og((m)r7/0001000 1,277
By definitions in Lemma C.10 we have the corresponding radius term for confidence ellipsoid ट
as 7--1 = =0(p V. Vlog do 2 log + 11/25) and the gradient covariance matrix as det(Al)
= = E w/
Proof. With the confidence ellipsoid around the corruption-free parameters C, := (0 100
02-1l1s_, I / 7--1 O}. we have 0" E č, according to Lemma C.10 In this case,
with the coefficient 7t-1 = 0v log d 1) 2log(6) + // and the gradient covariance det(Al] g( 0 ()) 0 1T /m, we have
matrix Σ, = +I ΣrE(e-1 W
(xt) = (xx) - 1((x))
(g(a;;; 0o), 0 - 0 - (g(m;; On), 0- - -0o)
max
DEC,-1
(g(z; 0o), 0 - 0.-1) - (9(2)) 0--1), 0" - -0.-1)
max
BEC.-1
+ 0(Sm - 1/6 log m [/67
(C.20)
||0 0-11 11= ا (1g( x 0o) ||را + 11g(0;; 0. 0.-1)
-0--1111s...
max
OEC.-1
+ O(Sm 1/6 Vlog(m)) ) 16 11 1//7
2 11gg@ 0.-1)/ ml 3 -1mm6116
116
+ +0 1ion-1/6/oog/ (lo(mm)) 1/6 1/
where the first inequality is by Lemma G.4 second inequality is by Holder's inequality, and the last inequality is by applying the definition of confidence ellipsoid C.-1. Lemma G.4, and Lemma G.6. Next, recall that the above UCB, is one term composing the single-round regret RG and for the cumulative regret, it will be summed up across T rounds. In this case, for the first term on the RHS
41

---

above, we have
Σ (E|T]
2 min (7--1 11 01-1)////////// /l 2,2 1)
Σ :E(T]
; Nvwggaa;.001 1} Vei
2
min n-1
Pr
2
min {1l (ll/igg(a 0 1}
1E[2)
PT
$ 2(1
min (1l//ag(zx;;0011
1}
:E[T]
where we have w < 1. Then, applying Lemma G.7
and by the definition of yT as well as supposing
that Zr V /
1, we will have
2 min 11-11 11,(2;; 0.-1// "
del (ET) u log det(Al)
llgg(d)+ + + 2T log (e((T)) det(AI)
min
Next, for the corrupted parameters O we consider the confidence ellipsoid Ci,--1 {0 ||0 - 0.0-1llE... I 1/,-1/ 1.0-1//ni vml constructed around the corrupted parameters 0 with the coefficient 7i,t-1 O V log det(En log(5) S)/ and the gradient covariance matrix det(Xi)
Ei.-1 = AI E+EEEEj-11 Wit g(æ,; 0 (00)))((==11 ( 0
Lemma C.10. In round t, with the notation and conditions Theorem 5.6 suppose the corruption- free parameters 0ut-11 associated with a condidate arm Bitt E X, are trained by L(0) Ere((-1] why (f(x;;0) -- md
110 -0ul2 Then, we have the corresponding confi-
dence ellipsoid
CiA-1= = 10: : 10 o. 1 E....... S 5
such that 0* E EC, where 7r,e-1 O(v v Vlog det 1) 2 log + and the gradient
dot(Al)
covariance mairix Di,-1 XI Ereee- (T) g( 1)-1) 0 1/m
Proof. The proof of this lemma follows analogous approach as in Lemma 5.2 in 86 Recall
that based on Lemma C.1 we have the expected reward of an arm z E X, being E x = (x)) =
(g(x; Oo), 0- Oo) where there exist parameters 0" such that 1 0ol < S/v 5/mm, S Intuitively, for each previously chosen arm Ø,, t E 1], we can consider an alternative form being
-(V w/S g( 0o) Vm, vm - -0o)
E
h(x))
where refers to the weight associated with arm in settings of R-NeuralUCB. Afterwards, with the weighted sequence of chosen arm gradients as well as their expected corruption-fiee rewards, can have
det let(
(0) (2 b,
ll 00) - (2:
11
1 Sv. log del (AI)
2 log(d) + 1/25,
by applying the conclusion of Theorem 2 from
[ In this case, by triangular incquality, we also have
|10 - -0olls...
< 110 - 0, -1500
b
(0) S... + 11 0, -
- -55 -16
(0)
m
42

---

Then, for the first term on the right hand side, we have
(0)
10" - -00 - 00
(0" 0. (2 (0)
11,-- 0, -5, -b
b (0)
1 Vm)
(0' 0o (
[0)
(0" - 0u
(0)
)
1 1-1 /vm)
00)
1,t-1
+ (0' 90
(E
(0 1
(0" 0o- (5 0 -',,0
(0)
s <0' 0o
12)
-11-1000 0o-
( 1 /vm)
+
| [00
10-1112
(0' - 00, (2 /,t-
1-11 1 b
b 00)
m) 1/- (0 -0 - -05,
1
b (0)
1
A
|| 5:00
det (5
< (1 +
(v.vi10)
2 2log(0) + 11 /m
X
(eI(
<m 1122.
1 + O(m 1/6 /log(m))467/02-77)
det(En det(En,e11) + 00 1/6 (1gg:mm)mmmmm/m-m_2022 log(()) + 1
(v. 1o1 (AI)
where the first inequality is because Tx Az S x: Ba: || /2/ /min (B) for some 0 < B and the fact that the minimum eigenvalue Amin (5(0) ( 2 X, and the last inequality is by Lemma G.6 as well as
due to the fact w/,6 S 1. Afterwards, for the second term, we have
0, (5:0 ( - -1 - //mlll/ S VI 1l2 -0001-11010000000000 -5- - (0) - /mlll2
1 i1-1 0,
SO(VA+tL) o (1-) 1/2 t/mm m 2/3 (log(m)) - + vt/A))
m-2/3
The first inequality follows from applying Lemma G.6 For the second inequality, we apply a similar approach as in Lemma D.I with the optimization problem given by (C.12). Since we scale the parameter to ensure
w 2 x2, we can follow the proof of Lemma B.2 in [86] to bound the
difference between GD-based optimization and gradient-based regression. With the minimum weight value lower bounded by x² and under the conditions in Theorem 5.6 applying Remark 4.7 in (86] completes the proof.
Lemma C.11. For candidate arm Tii E X, suppose its associated neural network f-: 0,,.-)) has been trained on received records Frbettt) with iterations of GD and learning rate 1). Let f(1 1,)) be an L-layer FC network with width m. Suppose conditions in Theorem 5.6 satisfied. Then, given the candidate arm æi, E Xr with constant Ç >> 0 and probability at least 1 8, we will have
( 0 01,11) - h((r,,))
< ||g(00;,1; 0 /// Eni- {s (u (v/1og log del(En,t-1) 2 log(() + 21/25)
dct(AI)
+ (1 11-1pman mmm)) ///1 + 0(m 1/6 ///0mm
+ +++++// v(/)))
O00
1/6 1/6
/og(mm)
1/6 (og(mm)) -13/ 13// 1//22)
1/6 + /1 / 10 00m 1/12 log 1/ [223/6 -1/12)
+ O(CC)
min [g 0,,1)
=
+ 05m 1ooo-////ooo//)//// 10
+ Om - 1/6 \lo(m))2/33 12
(C.21)
43

---

We also have the covariance matrix Σt,--1 = AI Ererg ( g( 1))))((=);))))) 1--1) with gradient vector g( 0) =
with notation and definitions in Theorem 5.6
Applying the Lemma C.1 we can transform the objective by substituting the reward mapping function h(-). as
Proof.
( - h(ar),))
Maii 02,t-1 - (g(as, (g 0o), 0- - -0o)
< ( 02,-11 - (g(a), 01,--1), - 0o) + O(Sm 11/6, /l 1 (217)
1 ( 021-1) (g(2)),)) 0,, 0n)
+ (g(ti,
( 0i.-- 0 0o) - (g 0i.--),,0'- -00)
+ O0S 1/6 1
where the first equality is due to Lemma C.I while the first inequality is due to Lemma G.4 and Lemma C. and the last inequality because the triangular inequality. Then, we proceed to separately bound the first and second term on the RHS. For the first term, we will have
[f( 01,--1) - (g(æarri 01,--1), - -
= [[ O2 - ( 0o) (1( ((((i,;;:0i--)) Oia-1), - -oo) I O(m 1/6 (log(m)) 2/3 2//3 2/3 13)
11/0
where the first equality is due to the fact that f ;: 0 based on our parameter initialization approach, and the inequality is by applying Lemma G.5 and Lemma G.3 Then, for the second term, we will have
(i( 0 0o) - (g(2;, 0c.-1), - 0o)
(g((z, 0; 1) 0r 0 0,,c-1)
< |19( 02,1-1) m E.L Vm. 100 - -11-1112
< 7 |1 0 ET
where the first inequality is by applying the Holder's inequality, and the last inequality by applying Lemma 5.2 in (86), Lemma C.1 in terms of the confidence set Ci,--1 and the fact that 0" E Ci.--1- Then, with the confidence ellipsoid introduced and discussed in Lemma C.12 summing up the results above, will then have
f( - (xx,,))
< [1g(00,1 1)/ vmll 1
min g| 0,,,-1)) m x-
1 |0(m)) u
det( E, 11) log(() + + + O(a))
log del(
NEt:
10( 0 0
m (1()))-
+ (1 18 / 5/3 /
+ O0 2/3 || -
+ 10 110000000000a0ggggg1111777777771 (mm1 -1/12)
+ -1/ (00 16 2/0gmm) 1/3
44

---

= =1gg(mi,e; 1it- 1/vm)
0 "1 (0(1//
det det(En Ei(t-1) 2 log(d) + 1125
log del(Al)
+ +1- O
O(m (l0 + vt/A))
+ |
+ 1
log
1/4 (m) 2 --11))
min
(a:
( 02.-1)/ - O(aC))
æEA.
[1g(2; 11) m (1(-)) 1
1/6 O(Sm 1/6 Tog(m)(216, 1//6 1,2 + O(m 10m-6166660000000110011101111111 1/6 /log(m))2 2//3 X 2/3 22a)
(K)
where we naturally have Hermitian matrices Σi.-1 >
c-1 by definition, which leads to
(Ea,-1)-2 (- by applying the conclusion from Lemma G.8 Afterwards, due to the fact that the minimum round-wise arm weight with = min(w, (// bE(K),7e](-1] = x² 1 VI V [T] by scaling parameter a, further have
h(2,,))
S 11 0ct-- m 2
1 [o(vv
det (1) 2 2log(0) + 11/25)
log del(Al)
(1- -1-d))) V (/
0
X (/LL)////))) (/A))
+ OCCm 2/3 "/gpp//ph/0000000000000000000110
13/2)
+ 1 + 11m
1/6 00000
1/4 (m) x-1112
+ O(aC)
min [g(;;; 0 0..-1)/ =EX:
+ O0Sm /oog(m) + O0m /log(m)(2/33////
which completes the proof for this lemma.
Lemma C.12. In round [T], with the notation and conditions from Theorem 5.6 suppose the corrupted parameters 0a.-1 associated with a candidate arm Ditt E X₂ are trained by L())
ErE(t-11 (7 [f 0) r-| +
2 1|0 0o112. Then, we have the confidence ellipsoid
C,,t11 0 10 01,--1lEE... S -h.-1/V
where we have the unknown parameter 0" E Ci, and we denote
min min mln 8
7,,-1 0 (v//1// log
det (t..-1)))) 2 log(0) + 1 O(CC)
=Eti
det(AI)
[ 0,,--1// (2(2))
(1 - ///pa////4X000o00/oooom/m/////13
vt/A))
+ |0000"||||0////0000/000000000100 / 13/6 9/22)
+ V. 11+00mm11/ (1000 0(m 1/12 log L24 -1/12).
45

---

Proof. Recall that for the imaginary corruption free parameters 0s, trained on corruption free
records Po-1, we can construct the confidence interval C. {0- |10 -0,.-1ll:...a S
5t.-1/ 7 > 0}, ensuring that the unknown 0" in Lemma C.1 satisfies 0" E Ci The corresponding confidence ellipsoid is presented in Lemma C.10
With the ellipsoid centered at - and the gradient covariance matrix defined as Σ,,-- = AI 1, g 1- g 1 /m, we proceed to derive the corresponding radius. Recall that way denotes the sample weight associated with the chosen arm I,,, For referencee, we first by Lemma G.6 and | 01,t-1122 I (m))) as shown in Lemma G.3 Next, as we already have
Er w
recall the preliminary bounds: - - -ile S O(m-1/6 1/6
|0 0 0,,1-11 _111. $ /1.-1/ /m, we then proceed to transform the objective to
100 0, || 11 S |00 - f - + 1 02,1-111E,,1-
1 10 01,1-1 E 10
10;1-1 01.0-11 11
I 0 0 E -E.,-1 E.,-1 + 110 -1,0-111E...
< 10" 0,,--1 - + +110" 01
- + 110 - -0,,-illE,,.-
S / mm + |00 |0 01 - + 0 O1vll (mm)) O(m Omm-110 / /log(m))147000111)
1/6
S / m + |00, 0 011-i1I - + (m 2/3 / log(m) 11300x22/3)
For the first term the RHS, we can follow the proof flow in Lemma C.6 by applying Lemma G.4 to substitute E with corresponding E,,--1, which will consequently lead to hN.0-1/
7 mm & V. / 1+ O(m / (o7g(m))477/62-1))
O(m 7/12 log LL445/6 1/12).
Meanwhile, for the second term on the RHS, we first define the gradient-based regression parameters as
0 11-1
=
= +
E
(T g(x;;; 0o) g(x;;;(0))
rE[t-1]
b
(0)
Σ w g(xx;;;00 0p) rr/ rr//vm.
11--
re(t-1]
(0) =
Σ
who g(x 0p) -m//mm.
rE(t-1]
Then, we can proceed have
||0 10
0 0 E
< 10,,--1 - 0, (2 (,,-- 1 -1 -it- 0, 0 D
(0)
< 0 - 0u -i, )) -
/
E..- + 110,1-11 - 0u - (D -
b 1 /ml -
1,1-1
S 0 - Oo (1 ) (0)
/ m
E1, + 0 - On - -x10 - 1 E
11-1
+ m '1 (0) -1 Σ
w g( 0o) [c)]lE
E..-1'
rE((-1)
(C.22)
Bounding the first two term in Inequality C.22) Here, for the first term on the RHS, we can individually apply Lemma D.1 by considering the auxiliary sequence in j-th iteration (j E (J) with
(0) = 0v. as
(1++)) 6) n
(0) w ( - 00) v) + +)X( 0b)
where the Jacobian matrix J[ == (g(x;; 0p), g(22: g(t..... Bn)) E (P vector
y - contains the received arm rewards Tr, E It 1]. and matrix W e p(t-1)x(t-1) is the
46

---

diagonal matrix that contains sample weights W [t- 1]. In particular, we have its norm | S I by definition. Here, with [](0),, being the 7-th column matrix ( the above sequence expected to solve the following problem
min (( = E +
Wid 2
- 0o) -rr
|2 + m2
00)
TER--11
As result, following an analogous approach as Lemma C.4 in 86 we can have || ())() A
(_1--1) 1 - 1-111 1/ V E.. S (1 mpnA)s/2 (L/(m))) Furthermore, by applying the conclusion
(0)
of Lemma D.I we can have
|00 1,, 0u 0 i - 1b 1 /mllz
(0)
s (1 1mm) 12 (1/(mA) + O(m 2/3 /1/3//) + vI/A)).
Similarly, for the second term in Inequality C.22 we also can apply a comparable approach by solving the problem:
1 md
min (())
Σ r
(0) [ 0o)
-
-r
+
+ 0g
and constructing the corresponding auxiliary sequence. This will lead to similar bound for the
second term on the RHS of inequality C.22 such that 0 Ou (i111)) b 1/vl// s
(0)
(1 - /22 (t/(mA) + O(m 2/3 [oggmm)
5/3 /t/A)).
Bounding the third term in Inequality C.22 Then, for the third term on the RHS, we first have
m m-
-11 11(2021)-1 Σ
0o) . -,)llx..-
TEL-1]
Sm (m-1((E,,(-)) ( Σ
(T) g((z;; - -,)1l
FE[1-11
+m +m- -
[Σ i 1 Σ
Wit g(a,; Ou) -))l
-E|t-11
S (m="[[_),-1)++ (1 Σ wht g( 0n) ( ()]l
-E(t-1]
+m=,)(E,,--)) -1 -
- (0) - (=
(0)
Wis (T) g(z 0o) c7)ll...
rE(t-1]
<m= -1 Σ
2/3 w g(0;;; 00) c -ll..,.. + O(Cm 2/3 V 7000
rE(t-1]
<m <m=11[E),1-1 Σ
/
(T)
g(x 01- +
(00g::...0000m222mmm//m/0 2/3 /00g
+ O0m 2//3,
rE|t-11
+ m -
Σ
wp?7 ig(x,, - g(x;; 0o)) c, ())1
rE(t-1]
< <m-
Σ
whe (T)
g(xx; 0,_)) c)ll.a... O(Cm 7/6 (0 //
rE(t-1]
O0 2/3
22/3
/log(m)t 7/6 13//6
where the third inequality is due to Lemma G.6 and the last inequality is due to Lemma G.4 Then, (r)
recall that the weight wat from (4) for each previously chosen arm Er. In this case, further
47

---

have
m
(2),-1))
Σ
Wis g ((er;:0-1)=- vt)///ll.)/
(7)
rE|t-1]
m 11/2
Σ
W (7) g(a+; 0--1) Ct/ /m
rE|t-1]
S m 1122
Σ rE|t-1]
Wif cr 1gg
where the first inequality is by applying the triangular inequality. By definition, naturally
have Eie-1 - D/n Vr E [t - I]. Next, we utilize Lemmas G.8 and the fact that with
m (T) HE[K),EE))1) x² < Vt E [T'] by scaling the parameter a, which will lead to
m 1/2 (E
Σ
wh7 g(x+;;(; 0--1) cr)/ /
-E[t-1]
I 00 11/2)
Σ
ti C (g((= 0--1)/ /mllll//mmmlll (Ei 11-1
(r)
TE(t-1/
s 50
Σ
(T) (1 0--1)/mm [S(2]]
TE|t-1]
a min 11( 0 1(r--1 / m
< 50
Σ Cr
#Edi
[g 0
(((2))
rE(t-1]
a min MEt.
[g( 0 0 m
50
(()))
where the third and the last inequalities due to the definition of way and the definition of corruption level C. Finally, summing up all the results will give the lemma.
C.9 Discussion on the Minimum Fraction Value 3
In this subsection, we provide exemplary upper bound of (1/B)) Inspired by [84]. the following analysis is based on a scenario where the arm contexts nearly lie within a low-dimensional subspace of the RKHS, induced by the NTK defined in Definition 5.2 To begin, recall that, defined in
(4), each candidate arm 2i, E X₂ associated with the corresponding arm weight:
min 11 0.-
(T) wit min 1, 9- [g 0.-1)/ (2(2))
min (1, frac, (#i,35 Xe, Σr })},
where O is tunable scaling parameter control the arm weight value range, and frac(-) shorthand for the fraction term. We denote the data-dependent minimum fraction value as minee(7 [min (frac, X,, E,-1), frac, (ă,; Xe, E,-1)}] In this case, the lower bound for (ac,,(ar,. Xr, E, represented by 8, can be expressed
mingex, [|g(2;; 0,-1)/ /mll 1-1
min [1g(;;; 01m
[[ 0, 0,-1) (22) [1g(2 0 1,-1)/ m (1
O(I.11-1)
min ||9(2; 0 01-1)/ Amin (1_1)
where the first inequality is because of Lemma G.2 and Lemma G.6 applying Rayleigh-Rit Ritz theorem.
The second inequality is by
48

---

Then, we let Pi-1 S PI-1 being the collection of received records that only consists of unique chosen arms from Pt-1- With 0 be the parameters trained on Pt-1. applying Lemma G.4 and Lemma G.3 we have 119( (0:11//v ( -aaii-ggaa:- 1// Vmll2 where Ø: = arg min [ag 0/-1)/ /m Given the over-parameeterization settings in Theorem
- log (m)).
5.6 with sufficiently large we can have (=g; 0t-1)//m g(x': 0 0.-1)//mll < 0(1). As
result, it leads
m 11g(2; 0..1)/
min (19( 0, 01-1) Amin ( (5
llg ( - /// / (2 / ( 0,-1// m (2)
O(L --1)
(119(2': 00-1)) m
0
1l 00-1) m3)
Amin (E,-1)
O(L x
0(1) Amin (1-1) O X-1)
where the second inequality is derived based Ox-1)/
(l-1:/ >
-1- (Ilg(x'; ((-1)/
g(x': 10-1)//mmmmmmm.m llg("' ; 0,-1)/ hl/.mm/mmmmmmmm + g(x'; 01-1)/ (2), and
bound the two multipliers separately with choice of m. The last inequality is by applying Theorem of 3 with the fact that 1() O(1) (Lemma B.2 in (2
Afterwards, regarding the lower bound of Amin A since Amin Σ (,_1) Amme (E..,) need to
(0) find the upper bound for -112 Denoting G --1 = [g Ou),
g (z:2 Oo).. . 1 θb)] E
((=1))xp as the gradient matrix, well as H IR (t-1( as the NTK matrix constructed from the chosen arms {æ, (at))_ with sufficient network width m (Theorem 5.6), we first have
| (G. (0) (G) - s 0(1)
and this inequality is because of Lemma B. in 86 by setting c 1. In this case, we will have
| Amax (H,-)) S E 12 | (0) TG
|| (GG/))//ml)) - Amax (Hax(H,,))
1 (G TG / (G ))/T/
H,-1
< Om 1/6 (log(m)) (m) L - + 0 + 0(1)
where the last inequality is by applying Lemma G.6 This leads to the result that 1E,1112 S
Amax (H + Om 1/6 Ll 1/6) - (A) + O(1.
Then, inspired by Section D in [44, based on the formulation from 14 and 20 we can consider
that each entry of H 1 is generated by
N(dA)
Σ (x, (n: j=1
where Yk.j are linearly independent spherical harmonics, w.r.t. degree i and d variables. N k) 2k+d-2 Cd-2 k+ H4 = O (mmax(k (d 1))- With the above feature mapping, if we have a subspace of the RKHS, such that the feature mapping in the RKHS is close enough its projection onto this subspace, we can have Amax(H,-)) = H 2|2 < ((1). As a result, summing up the results and with sufficiently large m, can have (LX-1).
D Bounding the Difference of Trained Parameters and Regression Parameters
In section, with weighted Gradient Descent, provide the upper bound in terms of the distance
(0) between GD trained parameters 0,-1 and the regression parameters ) -1 The results will
be applicd to the proof flow of both Neur and R-NeuralUCB, First, with the definitions
49

---

in Subsec.
C.2
we have the gradient- praseent-based regression parameters specified to arm E 24 as
Σ
i (T) g (0)):,;0) /m,
rE[t-11
E = +
Σ
W g(a;; 0 0
7Eft-11
Σ
wi (T)
g(t;;; 0n) rr/ "///m,
b
Σ of ( g(00;(((00000 0 rr/Vm rE(t-1]
TE(--1]
where (Ir, F [t] respectively stands for the chosen arms as well as their rewards. For notation simplicity, also use w. (T) J E [t-1] 1] to denote the weights for the chosen arm 2; respectively.
Analogously, given an candidate arm ii,t E X2 with arm weight wef7 defined (4. we have a series auxiliary gradient sequences
( (0)
θ (1)
())) as in G.3 such that for j-th iteration
+ ( = e (3)
(0) W (IIO)) - 0o) - -y) + - 0n)
where ( = (9(2)1; Oo), ga 0o). (( 0o)) E (R and W refers to the diagonal matrix of arm weights (w,,7 (T) }re(t-1], along with the reward vectors y E R separately heing the vector of received rewards and corruption-free rewards. In particular, the auxiliary sequence θ (G)
can be deemed as applying Gradient Descent to solve the following optimization problem
|2
min L())
Σ r]
(r) |
0o) yr
1 + mn
4 On 2
where [r refers to the 7-th column of the matrix ( Analogously,
also derive the
optimization problem for the sequence of corruption-free auxiliary parameters θ (0) by applying the
same definition of weight matrix W. By the definition of arm weights, we will also have [[]] & 1.
Lemma D.1 (Lemma B.2 of (6)). With the notation and conditions in Theorem 5.6 m 2 Sl(poly(T L, A51 x-11) and r) S O (mx4tmm For round E [T), we have
consider
(0) - 1 - 00 --
S (1- 111 (t/(mm))mm)/// + O0 2/3,5/3 -m32//3/// 712 vt/A))
with the J iterations of Gradient Descent process.
Proof. The proof of this lemma follows an analogous approach as in Lemma B.2 of 86). Here, similar
to the previous sequence {e (0) (1)) (J)),, J, we denote another set of auxiliary sequences to
simulate the J iterations of GD, by
(++ 9b) 77 J6] w (f()) (f6)-
- m))(()) - -00)
where we denote the corresponding gradient matrix at the j-th iteration as J(] (g(01; ((i)), (xx2; 9(..,,......:: 0b)) E (px((-1), well as the vector of network out- ) ".., -(,,f(x1110000 E gt-1, In this case, we can have the
puts (()) = (f(z; ( f(zz;
difference between parameter sequences
10++1) O (
= ||(1 7m)) (06) 9()) - 1)(( - (0 (f() 4) - - 0,))
[[(1 7m (06) |(01e + +/ W(J ((() a)ll Il| (((()) - 00))
< [[(1 (00)) |1)ee + + [ (()) b)ll
- ( - 0
[[11 (yiu). (00) (()1e [[ ) w)ll +4 (1 - - ( 0,)l
50

---

where the first inequality is by applying the triangular inequality. The second inequality is by using Kauchy-Schwarce inequality, and the third inequality is due the fact that ||]| 1. Here, the first term 14 can be bounded recursively. For the second term T5 on the RHS, we have
Js = =]] ) (F y)l S ml (J JII
b) S (nj m/23 v /og(mm) (,72m))777221111
by extending Lemma G.4 to the matrix Since we have the arm weights w!??? S <(() due to the maximum cap well as the choice of parameter we can also directly apply the conclusion of Lemma C.3 in [86] for the second inequality. Meanwhile, for the third term I6. we will have
T6 - ||] ()
-I 0o)l
- n ||
max Vt (f(1)(((;00) 0') f 0o) (((z):00): 0 0o)l
rE(r-1]
< O 5/3 m 1/3
7/2
by extending Lemma G.2 to the gradient matrix setting, as well as applying the Lemma G.5 on the integrate these three terms, which will lead to
absolute value. Afterwards,
[00+t1) - 1 = [|(1 - 1pm)) (00) - |00
Ont 7/6 m 1/3 Llgg(m) + 0mmt/33mm 1/3 //loo//mmm////mmL 2/3)
$ (1 - 11m)) (1) + Ont /6 m 1/3 /log(m) 7/2 1/6) + Ont 13 m 13 (log(m) 7/22 2213)
< 0/333/360
+ vt/A))
where for term 1a the last inequality is obtained by recursively applying the process to |1 O 0 and substituting the chosen upper bound for the learning rate 17. Then, with sufficiently large network width m as indicated in the lemma, we have
||0-1 On (2 bi9 112 |10 0 ||00+11+) 00 02, b ll
< (0++1) 0o (0) -
(0) Om (m3333335))))
2/3 5/3
vt/a))
S (1 - mmx/i// /t/(mA) + O(m 22/gg///
7/2 V
where the first inequality by applying triangular inequality, and the second inequality by applying the previous conclusion. The last inequality is by applying Lemma C.4 in [86] with the fact that
[ @ S /t/(m)). Since we have the arm weights w < 1 due to its maximum bound, we apply the conclusion of Lemma C.4 in [86] for the last inequality.
51

---

E A Base Algorithm: NeuralUCB-WGD
Recall that for each candidate Fi,t E X,, its corruption-feee expected reward is generated by an unknown reward mapping function ft-). Following existing neural bandit approaches, we use neural network f(-) to approximate h(-) for estimating arm rewards. Consistent with the main text and R-NeuralUCBB, we consider the network f(; 0) to be a fully connected (FC) network with depth 2 and width m N
(2; 0) == vm0 (0 (0,)))
where (.)) denotes the ReI.U activation function, and the trainable weight matrices are 0 E R 0, E m for < L and 0 1m For simplicity, we also denote the vectorized parameters
= ( " E.,
with dimensionality y and randomly initialized parameters Po. Similar to R- R-NeuralUCB, we also define g(;; 0) vec(Vef((z(0) E Rº as the vectorized network gradients, for input æ and parameters 0.
E.1 NeuralUCB-WGD: Neural-UCB with Weighted GD
Then, we introduce the workflow of our base algorithm NeuralUCB-WGI. (Algorithm 3}. which stands for Neural-UCB with Weighted GD. Here, NeuralUCB WGD can be considered as simplified version of R-NeuralUCB, where all the candidate arms XG in round t will share the same neural network for decision making. The idea is that although we do not know which training samples are corrupted, we can reduce the effects caused by the potential corruption instead, by paying relatively more attention the samples with low uncertainty for stable training process.
Algorithm 3 Neural-UCHE with Weighted GD (NeuralUCB-Wer BGGG
Input: Time horizon T. GD steps J. Learning rate y) Exploration coefficient 2 Scaaiig coefficient a > 0. Norm parameter S, regularization parameter X.
2: Initialization: Initialized parameters 0y. Covariance matrix To AI. Received records Po 0.
3: for each round E [T'] do
4: Observe candidate arms X; (ax,))e(())
5: for each arm æi,t X, do
6: Calculate its benefit score ( based on reward estimation f(r,,r 0i.-1) and the UCB-type exploration score for arm Ti.t. E.I. 7: end for
8: Recommend arm based on benefit scores
arg max E. EX; [U(ii:))
9:
Receive arm reward rt, and update the records, such that P. P, U (1x,, Fz)] Then, save
the corresponding weight for chosen arm 3t, as Wi = min 1, a (1;;
(1;; 02 / /m/lr=1))
10: Update the gradient covariance matrix r, T w: 0 ga, 0.- //m.
11: Starting from random initialization On. update the network parameters to o,, based on iterations of Gradient Descent and training data Pt.
12: end for
Arm Selection. each round t E [T]. after observing the candidate arms X; for selection, we calculate the reward estimation and the UCB score for selection (lines 5-7, Algorithm Similar to R-NeuralUCB, in terms of the arm selection (line 8, Algorithm 3. we determine the chosen arm ar, E X, with the highest benefit score, by x; arg max [U(x,,))] Here, with the NTK norm parameter S > and the probability least 5 given probability parameter (0, 1), we formulate the benefit score (II,))), along with a MCB-type exploration strategy (motivated by Lemma F.I as
log det(TT-.). log(s) + x1225) [|g O,-1:
Umx..) = fa 0-11) + Ov hog
det(AI)
(E.1)
where 0,-1 refer to network parameters round before GD, which have been trained with received records Pt-1, and À > is regularization parameter. Different from conventional
52

---

neural bandit works, our gradient covariance matrix is defined as T -I+++++++
Er +I Wr
; 0,-1))(2+;; ( 0--1)=/ /m. Here, to quantity the arm uncertainty level, inspired by 42 define the sample weight as W = min
based on the gradient vector
g(xx;0r-1) - vec(Ve (e)((=00,-)) E IP, and it is scaled by a tunable parameter a >>> 0. Notice
that the arm weight w, is inversely proportional to our UCB-type exploration score in (E. Since the UCB-based exploration score can be considered to quantify reward estimation uncertainty levels
24 72 [6]. we thus assign small weights to training samples with high uncertainty. Recall that in ( we apply // to characterize the random noise e, Similar to R- R-NeuralUCB. when this value is tunable exploration parameter to control the exploration intensity analogous to existing works (e.g., [86]).
unknown, we alternatively deem // 2
After receiving the reward T₁ for the chosen arm Tt, update the records Pt. The arm context Σ, and its received reward 7, are added to the collection Pr, along with their weight wy = min a/ ll/g(1/ //mll/ (line Algorithm 3).
Model Training. Afterwards, we perform J iterations of GD to update the network parameters (line 11, Algorithm 3. With P. Tr)r up round t, we train the model parameters O,, through 0 0f VPL: )) Here, 0(10 , E [J] are the parameters after the j-th GD iteration, starting from randomly initialized ones 0 e(0) On. and 1) >> 0 refers the learning rate. Different from existing neural bandit works (e.g., 86 84 which consider all received records to be equally important with the ordinary 1.2 loss function, we alternatively define the weighted loss function as
((P;0)=
Σ (...
W 2
2 md [(xx;;0) - -r r 2 0 - 0011
where is the regularization parameter as in E.II.. and we have previously defined sample weights Wr, T E [t] associated with each chosen arm-reward pair (ær, E Pe. In summary, the intuition is that, when definnn the loss function for the received records P: to round f, we aim to give extra emphasis to samples with low estimation uncertainty. Intuitively. if samples with high uncertainty are indeed corrupted by the adversary, they are more likely to significantly disrupt the internal decision-makinn making process, thereby impacting the stability of reward estimation. To mitigate this risk, even though we cannot identify which training samples are corrupted, we conservatively assign smaller weights to high-uncertainty samples, supporting stable and robust GD training process.
(e),rr))eln up
E.2
Regret Analysis for NeUD
For the theoretical analysis, different from that of R-NeuralUCB (Subsection 5.1 we focus on the case where the corruption level known, a common setting existing works 16
17.. This assumption allows us to appropriately select the parameter in Algorithm to achieve tighter regret bound. Additionally, we briefly discuss potential outcomes C' is unknown. Recall that our objective
42
76
(2) is to minimize the overall pseudo-regret in terms of the corruption-free expected reward over finite horizon of T rounds: R(T) Σ ElFy Fel. where E[F:] h(xx)) denotes the expected corruption-fret reward from the chosen arm It, and E[ = max [h( (xx,,) represents the expected reward of the optimal arm.
To address challenges in regret analysis, we define two sets of regression parameters corresponding to the corrupted model and the corruption-free model. Using the corruption-fre ffree model ()) we derive the confidence ellipsoid around its parameters 0 which serves as a proxy for updating the confidence ellipsoid around the trained corrupted model parameters 0. With the updated confidence ellipsoid and concentration results, we then finalize the regret upper bound. Here, without carefully designing the arm weights Wr, T E [t] (Algorithm 3 and structuring the regret analysis workflow, deriving the regret upper bound under adversarial corruption settings would be impractical. The following Theorem E. provides a bound on the cumulative pseudo-regret for NeuralUCB-WGGI
Theorem E.1. Given the finite horizon T E N+, denote S Z 2
Suppose prob- ",,'IIssly log(1/6)), ability parameter 5 E (0, 1), network width m 2 (ppoly(T,L, C, A.
n S O(TTLL+ + m))-1), J O(TL/X), and X >
f(-) be the L-layer FC network with
53

---

width m, and set a 1/C without the prior knowledge of d. Then, with probability at least 1 - 6 over random initialization, NeuralUCB- WGD achieves the regret upper bound:
R(T) S Ō Vir) σ u
2 log(o) - = + +0 + + (oilog(1+TK//)) TK/A)) + +((0)-1125)
+0 +0(cā. (u + TK/A) -2log(6))
The proof of Theorem H.1 is provided in Appendix F The first term on the RHS represents the corruptio-inndeeedden regret upper bound, which matches the bound O(dVT) in corruption- free neural bandit studies [86 88]. For terms that depend on the corruption level C,, we obtain O(CA1//25 + /2 by omitting logarithmic terms. When aligning the definition of information gain [6 with the effective dimension d, our results are consistent with the latest kernelized bandit research in terms of the horizon T and effective dimension given the NTK -inducde RKHS and an indefinite arm space (Corollary 7 in [66].. Additionally, we can bound the NTK norm term S by constant if hx-)) belongs to the RKHS norm induced by NTK (Subsection B.4]. The regularization parameter can also be tuned to account for the NTK norm S. Different from the vanilla Neural- UCB [6). we quantify the impact of corruption by deriving a new confidence ellipsoid around the corrupted parameters 0,-1, ensuring that the corruption-related terms remain independent of the non-logarithmic 7 term.
Inspired by [42). when C is unknown to the learner, an estimated corruption level C 0 can be utilized based on prior knowledge
the adversary. In this case, we can set the scaling parameter = 1/CC. If the actual C < C, then the corresponding regret upper bound in Theorem 5.6 still holds. Conversely, C > C, the regret bound will no longer hold, leading to a trivial upper bound of R(T)= s O(T), similar to existing works (e.g., (4).. Here, practically, one approach is set C= V.. For C S vT, the overall regret then bounded by ( VT), which matches [16] and improves upon O(dT)) from [15]. When C > VT. our trivial regret bound of (TT) also aligns with the state-of-the-art kernelized method [15] with unknown C, which has bound of Ö(dyT+ + CdVT) = Õ(dVT dT). Thus, the regret bound for NeuralUCB- BWD comparably matches the latest theoretical results from the kernelized bandit research [6 15 under the indefinite
arm space setting. While the problem definition of neural contextual bandits I is more general and reduce restrictions from the reward mapping function aspect, it is also significantly distinct from the problem definitions of linear or kemelized bandits, which makes lots of techniques from existing works tackling adversarial corruptions (e.g.. [42 [6]) infeasible.
F
Proof of Regret Bound for NeuralUCB-WGD (Proof of Theorem E.
By definition in I recall that we aim to minimize the pseudo-regret for T rounds, denoted by
R(T)= Σ Max1) - h(ar)) Σ
R
= Σ (a(0 0o), 0- 0o) - (g(arr; 0o), 0" - -00)
where Gt is the chosen arm and at = arg maxa, [M(+..)) being the optimal arm in round t. The third equality is due to Lemma C.I Then, we denote f(-) as the bandit model we currently possess, which is trained with corrupted records P up round f, and also suppose an imaginary corruption-free free bandit model accordingly, which trained with corruption freee records P The corresponding model parameters of f(-) will be denoted as O, while the parameters of the imaginary corruption frree model will be denoted O.
Proof sketch. To begin with, we first analyze the single-round pseudo-regret R. for t E [T], where the cumulative regret is given by I(T)- Eierry Rt. Here, we demonstrate that the single-round regret with corruption can be upper bounded by using the updated confidence ellipsoid (Lemma F.I around
54

---

the corrupted network parameters 9. Since we cannot directly apply the self-regularized martingale
concentration results from existing studies [ 86), we instead derive updated concentration results that account for adversarial corruptions, establish the cumulative regret over T rounds. Additionally, we provide the optimal value for the scaling parameter based on the known corruption level C, demonstrating why setting a 1/C yields the desired regret bound.
shown in Lemma F.2 These results are then combined to
F.1 Bounding the Single-round Regret
Following analogous approach as the proof of Lemma 5,3 in 86 we can transform the regret for single round & [T']
Rs (a(zf;0)) 0" - -00 - (g(0); 00). 0" 0o)
(g( Oz-1), 1), 0- -n) (glar 11-1,, 0" Oo) 0(Sm 1/6 /00
I max (g);;; 0, 01-1), 0 - 0o) (0(2; 01- o" 0o) + O0Sm 1/6, llogmm)t /0 1/6 ( 2 OECt-1
where the first inequality is by the gradient difference in Lemma G.4 and the bound of | Pol in Lemma C.1 Here, based on Lemma
F.I. we have the unknown parameter 0" C--1 with the r I h-1//m) induced by our currently possessed parameters - as well as the chosen arms {ar rr]-- Here, with 7t-1 being the corresponding corruption- free radius term, we have
confidence ellipsoid C- = (0 0
7- = 5t-1 a C + (1 1m2 1/2 V1/A+ O(m 1/6 (l0g(m))77/3//333/ |1000 (1/11
+ 00 2/3 22/3 (lggmm)) (/ 0 000mmmmmlmm0mmmm 13/6 1 1,9/2).
Then, based on the arm pulling mechanism, we denote the estimated arm benefit score as U(zi,t) = ( 0.-1) + 7 v g(aa,, O. 1) 1 0r-1), and we also define its alternative based on the confidence ellipsoid as
V(I,,)) ( 0:-1), 01-1- 0o) #- V
0
max eEC;
(9( (._ 0 - 0n)
based on the confidence interval C,-1 induced by the corrupted parameters 0.-1. Regarding their distance, we can further derive (U(2,,,) ((x.,)) < O(m 1/6 ( by applying Lemma G.5 as well as the fact that f(:: 0u) = 0 based random initialization. It then leads to
R, < max (g(0;; 01-1); 0 Ou) OEC.-1
(0(; 0 0,-1); or 0o) + O(Smm 1/6, (1ogmm))000-10003
= (xx;) - (g(0,; 1,- 0- - Op) + O(Sm 1/6 Vlog(m)t -111
< U (xx)) (g(0;; 0,-1), 0- - Go)
O(Sm 1/6 (ogg(m)t" 1/6
1/6 16
+ (m 1/6 1/6 "
2/3
< (xx))
(g(:;; 0t-1), 0r 0o)
+ O(Sm 1/6 V log (m)m 1/6 1-16
1/6 1 + (m 11/6 1/6 /lg(mm)(2/3 2/33
2/3 22/3 (3)
< V(x)) (g(0;; 0,-1), 0" -00)
+ O(Sm -1 1/6 //log(m) )t 166) x 16 1,17 + 0(m 1/6 Vlog(m)(2/3> 2
< max GEC,
(g( 1), 0o) - (g(x;; 0,-1,, 0- -0)
+ O(Sm 1/6 /o
+ O(m /
where the third inequality is due to the arm pulling mechanism. The second and the fourth inequality is due to the distance between (-) and U+). Since we have 0* e C.-1, by Holder's inequality, it
55

---

will further lead to
Rs < max (g(0;; 01-1), 0 - 0o) - (0 0" - -0) O(Sm 1/6 (00 OCC+-1
+0(m 1/6 (log(m)) 2/3 x-208_1110
< max OEC1-1
|1g(2;; 0 -11))111, 110 0ollr.-: + llg(ar; 11-1))11,, 1100 0ollr....
+ 005m - 1/6 / log m 1- + O(m 1:mn-110000 1/6 / 2/3
$ 2 |g( 0,-1)/ 1 + O0Sm 1/6 /l /60 1/1 (3/7) + +0 1/6
1/6 00 x 23)
where the last inequality is due to the definition of confidence ellipsoid Ct- This gives the upper bound for our single-round regret.
F.2 Bounding the cumulative regret
On the other hand, based on the conclusion from Subsec. F.1 the cumulative regret upper bound can be transformed to
T
T
R(T)=
Mxx;)= h((ae) = R
Σ
<
2 min
1/ nt-1 11-1-1191 (1 02-1)/ r. 1 + O(Sm //og(m))200011//1 -1/6, 1,2/T)
m=1
+ Om 116 2
1 (1g( 0:- 0t-1)/ 1r,. j}] + 0()
2 min
where the last inequality because of sufficiently large network width m that satisfies conditions in Theorem E.1 Then, for the first term on the RHS, we can further have
Σ 2 min 7- lla(a, 02-1)/
2 V dT + TK/A) + (1+ "n) dlog(1 + TK/A)
= =dlog(1 +TK/A) 2YT (ViTlos(t TK/A) 1. -.ooo(( + TK//))
S +TK/)) (AVT//A+((VVrrooLL (Vrrlog(++T//M 1 a Tlog(I+
25.-1 2a C mm/ 0(m 100mmm1/011 /11g(m))17//33333- v11Aa)
O0Cm 2/3 /10g(m)))/00-7///// + O0Cm 1/6 10/6 X -13/6 1//)
(VTrlog(1+ 1 dllg(1 (TT(/))
(mv/ So//alog(++T///// TK/A) - 2lg + + 1/2 + 2a C
+ 2[1 1 - / 8/a
(m (lggmm 11 5/3 vt/A))
+ O0Cm 2/3 / + 10 13/6
ī +TK/)) a
log(1 + TK/A)) 0 (ly/lll[++K/// log( + +1/225 41/25+200)
22C) 2ac)+00)) +0(1)
56

---

where the first inequality is due to Lemma F.2 and the second inequality is due to Lemma F.1 The third inequality can be derived following an analogous approach Lemma 5.2 in [6]. and the last inequality is due to the sufficiently large network width m mentioned in Theorem E.1 as well as the sufficient number of GD iterations J O(TL/A)
Discussion on the value of a. Here, notice that we have the tunable parameter a nested in the regret bound. Taking some more steps, we can have
T
2 min { n0-1 11g(201
}
(VVrlogg( + +K/A) + .dlg(1 + +TK/A)
0 UV Tlog(1 + +TK/A) - 2oog(5) + +11/25 + 2a 20. C)
210g(0) + x1 + 20 C) VdT + 2.a) (uvā (vVā-21og(0))
) + + dT + 1 2.0)) (uvā 20og(0)
+ + co(ovvá + cā
Since have prior knowledge of effective dimension d, can set a J. It will then lead to
}}
min 7-- (1g( 0z-1)/
ViT VitT+1 1 2. (uvā ( 2log(0) + x2/25) + cā
VdTT) ( (VVā- x1/35) +
+ Că Cd. (vVā 20-221o 2log(0) + 1/2)) ).
Finally, summing up all the results above will give the conclusion.
F33 Confidence ellipsoid for corrupted parameters
Lemma F.1. With the notation and conditions in Theorem F.1 train the network parameters 0.-1 based on received records Pt-1- The confidence ellipsoid around the corrupted network parameters 0.-1 can be defined as
C--1 (0: 0:: -00-111 S 5t-1/vm
where have the unknown parameter 0" E CC-11, and we denote
T- 7-- + C + (1 - 1/2 v1/X + Om (log(m) 1 +O 2/3 /o 1/6 -- 7/6
55/ v1/AI) 7/6 7/6 13/6 9/2)
/ LT O0Cm 1/6 log(m))t
Proof.
The proof follows an analogous approach as in Lemma C.12 For the imaginary corruption-free parameters 0,-1, which are trained on corruption-free records P.-1. we can construct the confidence
interval C; == (0 110-0.0-10 0.-1l < 7t-1/ mm. 7--1 > 0}, such that the unknown 0" in Lemma
C.1 satisfies 0* E C, However, since we do not possess 0,-1. we need to alternatively derive the confidence ellipsoid C,-1 around the possessed corrupted parameters 0,-1, such that 0" E C.-1-
With the ellipsoid center 0:-1 as well as the weighted gradient covariance matrix T;-1 AI - Ere(e-1] Wr 0 g( 0 1- T /m, we need to derive the corresponding radius. Recall that Wy the sample weight associated with chosen arm Er. Here, we first recall some preliminaries that ||T T--ille < O(m 1/6 Vlog(m) (m)) L 7 - 1/6) due to Lemma G.6, as well as ||0-1
0.1112 12 < O ((vt((mA)) due to Lemma G.3
57

---

Next, as we already have |0 - -10-11lli... I h
/ we proceed to transform the objective to
-0--lln 10 - 01-illri-1 + 101-1 11l1l
< 010 r- 100-1 11-1l1r.-1
0 0 0 P + | 06-1l1r,-1
< 100 0 01-1l1 +110" 0:-1 01- + 1 01-1l1r--1
S --1/vm + 00-1 - 01-1llr.-, + + O ///m//mmm)))))
Om 11/6
Omm-1/6 (
2/3 S / + 00,- - 01-1llr,-, + Om 12/3 (lg(mm) (m)
For the second term on the RHS, we first define the gradient-based regression parameters as
(0) +
Wr g 0o) g(rr; / rE(r-1]
Σ
1-1 =
610)
Σ
Wy g( 0o) . TT/ /mm
TE|t-11
6
Σ
W g 0o) Fr \
rE|t-1]
Then, with the triangular inequality, we can proceed to have
||0-11 0z-1 ||,, < |10,-1 0, (T
(0)
(0)
(T (0) (0)
0o- 0 I|T, |
s 5110-11 0o (T ( 6 T. + 10,-1 0o (r 1-1 m r.-1
(0)
< 010 - Oo (r ) b (0)
m - + 1100- 0o- --rr%) / / r--1
m -1 tE|(-1 11
Wy g( 0o) c ())
(F.1)
Bounding the first two term on the RHS of Inequality E. Here, for the first term on the RHS, we can individually apply Lemma D.I by considering the auxiliary sequence in j-th iteration (j E [J]
with e (0) Oo.
- (++ - n7.
(0) W. (I - 0o)
-0) - - -00)
where the Jacobian matrix (0) == (g(x1; oo), (x:; 9(
E RPx(t-1), and vector E (2'1 contains the received arm rewards Tr, r E [t - 1]. while matrix W E (((-1)(((-1) is
the diagonal matrix that contains sample weights w,, r E [t 10-1 1]. We have its norm || S by definition. Here, the above sequence is expected to solve the following problem with gradient descent
| 00) 0o) - rr 2
|
Σ "r -)
min (()) @
mX
0
As result, following an analogous approach as in Lemma C.4 in (86), we can have ||0() 0o (1))) (0)
b (0)
/ /mmll r.-. (1 - mma))/22 /t/ (t/(m)). Furthermore, by applying the conclusion of
Lemma D.I we can have
(0) |00_1 6, ( -
/m////// & (1-mmA)
(t/(m))+ (I-mm))/1////(//))ttO/))) 2/3 <mmmm Vlog(m) 3//
Similarly, for the second term in Inequality F. the problem:
we also can apply comparable approach by solving
2 + $2" -
min (()) wy
=
Σ
[ T 0o)
mX 2 0
θ rE(r-1)
2
2
58

---

and constructing the corresponding auxiliary sequence. Following an analogous approach, it will
lead to similar bound for the second term, such that | 0o 1/,:)_/i/1//mm S
(1-mm2))/22 (t/(m)) + O(m 2233 (
/t/A)).
Bounding the third term on the RHS of Inequality E. Afterwards, for the third term on the RHS, first have
m
(0)
Σ
wy (a,; 0n) cr c
rE(t-1]
$ (m--((T--))
Σ
W7 g 00) - -))lrm-
TE(T-11
+m 1
(T 1-1 ) ( Σ
wy
-E(t-1]
S Sm (m-
W/ g 00) C,7 ||---
rE(--1]
+ +m='I((T(-)
(Ti-1 ( 1 (0)
Σ w, g(0,; cr)llr. rE|--1]
I <m-'I(T,-1) Σ
W g 00) ,)]l,. + O(Cm 2/3 Vlog(m)t 2
-E[(-1]
Σ
W+ ga 1 l)),,, + +0 2/3 /lg(m)) 13/0 13/
-E|t-11
+ +
WF (g(x; 0 0-- - g(=+; G)]lr,
rE[t-1]
Σ Wr gar 0+-1) CT) (+) ||.
rE[--1]
+ OCm 7/6 lo) / 7/0 2/2) + OCOm 2/3
2/ommm2////o//mmm (ogg(m))7000111) 2/22
where the third inequality is due to Lemma G.6 and the last inequality is due to Lemma G.4 Then, recall that the weight w, = {1, a (0
m ||- } for each chosen arm Vr. this case,
we can further have
m 1/2 (Ti-1)
Σ
Wr g(z 0,-1) cr) /m/lr..
rE[(-1]
m
1/2||
Σ
w, g( 0 0--1) cr /
rc(t-1]
S m 1/2
Σ
wr|cr 10-(==;0-11)/))) (T
rE(r-1]
S -1/2
1/2
Σ
wr|c
1, (T.-))
rE[(-1]
aa C/vm.
where the first inequality is by applying the Sauchy-Schwarte inequality, while the second inequality is due to T,-1 < T and Lemma The last inequality is by the definition of corruption level C. Finally, summing up all the results will give the desired lemma.
F.4 Self-regularized Martingale Sequence with Weighted Matrix
Recall that we have the weighted gradient covariance matrix P--1 XI+ Wy (wxr 0,-1)- ((x=+;,-1)) /m, where g( 0--1) )) is the vectorized gradient vector, and w- S refers to the sampled associated with chosen arm æy..
59

---

By existing works [6], we can have the nermanzor martingale such that
Σ min (19(=):0--1)) TERI
1
2 log det(T,) det(AI)
weights in F3 are all set to However, since our settings the gradient covariance matrix T₁ involves sample weights, will need to further discuss the upper bound for this sequence summation.
Lemma F.2.
With the definition 7t from Lemma F.1 as well as the notation and conditions in we have the following inequality
Theorem
Σ [E[T]
min 7t-1 119((11; 0 00-00---1110 11 1
S YT di + + (1 +1+33 TT
dllo(1 + +TK/A)
where
1 AI Et Wr g( 111 ; 0--1)1/m.
Proof.
The proof of this lemma follows an analogous approach as Theorem 4.2 in 42 Recall that
sample weights W, I T T [T]. In this case, we separately consider two scenarios when (i) w,
then r E T and (ii) the scenario when wy < 1, then E T this case, the original objective will become the following inequality
Σ min eE|
|locass 0r- 0,-10///1///// 1///////lrrr }}
Σ min
Σ min 1
1ET
IET
First, for the scenario where Wr = 1, E T we have
Σ min { (1((x;;
min 0
(T
(TT
min [19(2):0)1)) (15)))))))))
(ET
Here, define an extra auxiliary matrix D XI ETET(e-") Wy g( 0 0,-1)
gxt O 1) 1/m. Compared with the original gradient covariance matrix T4-1, since we have T - and they are both Hermitian matrices. we can derive the last inequality based on Lemma G.8 Then, by applying Lemma G.7 and Lemma C.2 it will lead to
Σ min 1l0(=::00-1///mllp..
1 s
[T
min (
1
dlog(1 + TKK/A)
< är log(1 + TK/A).
Then, since we have 7--1 Yr, plugging in the Pr will complete the proof.
Afterwards, for the second scenario when w, 1, ((T)
will have
min { T--1 [19(0,; 0 0,-1)/ Σ
1
Σ
We
|9(00; 00))//0m)
7-11
( ecl
(ET(TT)
(11- - TT).
Σ
| 1
(ET(T))
|mm ( 1}
< (1
(T
60

---

where the inequality is because we have Nh-1 S YT, Vt E [T].
Following the previous approach, we define the auxiliary matrix T--1 I ETET w, w-1
g 0r-1)T/ /m. Here, since we also have P - and they are both Hermitian matrices, we can derive the last inequality based on Lemma G.8 In addition, we consider an alternative form of the original gradient vector as 01(2+r000 0 = Vw, g( 0 E TT--")
In this case, the auxiliary gradient covariance matrix can be alternatively represented as r AI ETETAT" g' ((=,:0,-1) g' < 11) //m, and the RHS will become
Σ min 72-1 [|g( (011:/0-1)//vm (ET
1 s (1+ I
E
BE
S (1 +
where the last inequality is by applying Lemma G.7 and Lemma finish the proof.
C.2
Summing up the results will
G Lemmas for Over-parameterized FC Neural Networks
Given the input arm context vector æ E IRd, we denote the L-layer FC neural network with width m
L-1
f(x; 0) On II D,O
(G.1)
1=1
where with being the ReLU activation, define the intermediate hidden representations h e (O...., - as
hg === x, h: = (0 [T. [T. and we also have the binary diagonal matrix functioning as the ReLU activation being
Dj = (Oth (()
[L 1].
where I((-) the indicator function. Afterwards, the corresponding gradients will become
[h (,
fe;f(2;0) = h h L.
(G.2)
Lemma G.1. There exists a positive constant C > O such that with probability at least 1 - 5, if m 2 C I log(T2 L//)/ for each arbitrary x, E Ureia X,, there exists a set of parameters 0"
such that with the neural network parameters 0.-1 trained {x, }-=1 we have
Kg(a; On), 0- -o) (g(x; 0.-1). 0- 0o)l S O0Sm 1/6 11111//111 1600 1/6 2 where parameters 0* satisfy | 0oll < SS/ /m,
shown in Lemma C.I
Proof. This lemma is based on Lemma C.I Here, our objective can be reformed into
Kg(x; 0g), 0* - -Oo) (g(x;; 1.11), 0- 0o)! ||0" 00l12 (g(x; 0o)
g(æ: 0
I SS/vm (g(x; 0o)
g( 0,-1))
< OSmm 1/6 (0
where the first inequality is due Lemma C.1 and the second inequality is due Lemmas G.2 and Lemma (.4
G.3
Lemma G.2 (Lemma B.3 in have
). There exist constants (C1, C2) such that for any 8 0, if we
w S L, ( (logm) m) 3/22
then with probability at least 1 1-8 any 10 -bull S and x E (X)T we have [|g(2; 0)112 < C₂ C2VmL.
61

---

Proof. In terms of the gradient upper bound, directly applying Lemma B.3 in [2] will give the desired result that (=: 0)1l O()mI.)
Lemma G.3 (Lemma B.2 86 For the I.-laeer full-connected network f trained with J iterations of GD, there exist constants
(C:) ] 2 0 such that for > for all E (T), 91 m satisfy
2 2///(mA) 2 C1m 3/2 L/a03//22-// 3/2
2 (m/) S C2 min L [log m] 3/2 (m((An) 6 (logm) -
7 S Ca + tmL)
m/ Ca (1/ + vI/A),
then, with probability at least 1 - 8, we have
00. 0oll s (m/)
10, 0 -. S (1 (1- 111-1man 17 1 + C3m 2/3 / t/A).
where the unweighted regression parameters are E, AI E Eret and b. = Ereee g (x; 0- 1)r /
0, 0 1
Lemma G.4 (Theorem 5 in (3). With probability at least 1 - 6, there exist constants C1 C2 such that if w < L, 9/2 log m, for 110, 0ol12 S we have
l 0.) - g( 00)ll2 S C2vlog mw/ 1 0o)ll2-
Lemma G.5 (Lemma 4.1 in (21 There exist constants {C]=) 2 such that for any 8 622 0, ifT satisfies that
S 12L flog m] m1-8/2
then with probability at least 5, for all 0% 0 satisfying 110 -0ol 1. - 0oll any x E {xe HE we have
and for
[s(;; 0²) f(x; 0²) (<g(0; 0²), 0² 02ح) C374/3 / log m.
Lemma G.6. Suppose satisfies the conditions in Theorem 5.6 Suppose the gradient matrix can be
represented by Σ + EiEry g( 0,-1) g g( / m, with an arbitrary arm Vi, E Xe from each time step t. With probability at least 1 over the initialization, the following results hold:
|2 < A O(TL),
E
|| - 0(m 1/6 (17000)
|| log deu ) log dcI(AI)
del del((E (Σ()))
||r S (m I.
dct(AI)
where the gradient matrix defined based on randomly initialized parameters Og is Σ(0) AI Enerrg(as, g( 0o) g( 0o)TTmn
Proof. Based on the Lemma G.2 inequality:
for any EE [T], (1 s O(VmL). Then, for the first
Σ (0) 1| ||I + Σ g( Oo)g(a,; 0o)
|Al||2 + Σ g( θ 0.)
T
<x+>
|9 2 ml < X O(TL)
Then, the second and third inequalities in this lemma are the direct application of Lemma B.3 of 86
62

---

Lemma G.7 (Lemma 11 in [.] Lemma B.7 in [66). Suppose sequence of arms { -re()) with an arbitrary arm x'y E 2, from each time step T E [t]. The gradient matrix is denoted by
E, >I+ g(al;;; g(0'p: -1)1)1/mm //m where - refer to network parameters in round
T E [t]. We can have
det (2:)
Σ TE
min (10((1
1 S 2 log
E 1
del
G.1 Auxiliary Lemma
Lemma G.8 ((Corollary 7.7.4. (a) from [45). Let A, B be Hermitian matrices of the same shape, and suppose they are positive semi-definite. Then, we have A - B iff - 3 B
63

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have included discussion for our contributions in the Abstract and Intro- duction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please appendix for the discussion of the limitation.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
64

---

Justification:
Please see theoretical analysis section and appendix for details.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please appendix and submitted source code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
65

---

Answer: [Yes]
Justification:
We include the source code along with our submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips.com wttpcccpppbccccceec guwdes/dde/eeee Cooeeeoodeesssseeeeee /ttp://bb///uudddd///eeeeeeeesss
ssiniiiiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We have shown our way of selecting the parameters and included the parameter study.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard deviation is given for experiment results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
66

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see appendix where we mention our system specifications.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We confirm this perform conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have included subsection in appendix discussing this.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
67

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is mainly about defensing adversarial attacks under neural bandit settings with no new datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We include the URLs for the datasets used instead.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
68

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new datasets are introduced.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects are involved.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subjects are involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
69


Reviews:
[{"review_id": "cbxwwWoTd6", "reviewer": "Reviewer_xUbn", "summary": "The paper studied neural contextual bandits under adversarial reward corruptions. The adversary is allowed to perturb the reward after observing the action selected by the bandit player, but is subject to the constraint that the total reward corruption must be bounded by some budget C. Within this attack framework, the paper proposed a robust neural contextual bandit algorithm called R-NeuralUCB that formulates a novel context-aware gradient descent process, by taking the uncertainty information of both candidate arms and training samples into\nconsideration. When the neural network is over-parametrized, the paper provided theoretical study on the regret using the NTK technique. The authors proved sublinear regret that scales linearly as the total corruption level C grows. Empirical experiments demonstrated the effectiveness of the proposed robust bandit algorithm.", "questions": "I was wondering if the authors have thought about providing a lower bound on how the regret scales as C grows. Is the upper bound tight?", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper studied a popular topic of robust bandit under corruption. Furthermore, different from existing works, this is the first paper that investigates the robustness of \"neural\" contextual bandit as far as I know, which significantly pushes the frontier of this area.\n\nThe authors provided solid theoretical analysis for the proposed R-NeuralUCB algorithm using the NTK technique, which is a great use case of NTK in the bandit domain. The results are interesting and appealing.\n\nThe authors further demonstrated the effectiveness and efficiency of the R-NeuralUCB algorithm on real-world dataset. The results are convincing and validated the theoretical findings discovered in the paper.", "weaknesses": "The idea to make the UCB algorithm robust is not novel. Prior works have applied similar idea that performs more exploration on arms with lower confidence. This work is mostly relying on the same idea to achieve robustness. Also, the final regret bound is not surprising to me. It is common that the regret scales linearly as the total corruption level C grows. That said, I was wondering if the authors have thought about providing a lower bound on how the regret scales as C grows? Is the upper bound tight?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the reviewer for your valuable questions and comments. We will try our best to provide our detailed response in the form of Q\\&A. Please also see our manuscript for cited papers. *Thank you!*\n\n\n\n**Q1: The regret lower bound in terms of corruption level $C$ under neural bandit settings?**\n\n\nWe appreciate the reviewer for your question on the regret lower bound. \nRecall that in our Conclusion section as well as Appendix Subsection B.7, we mention that one limitation of this paper is lacking a theoretical regret lower bound, and we consider this task as a promising future direction of our work. \nThis is because deriving the lower bound under neural bandits with adversarial corruption settings is significantly non-trivial, and it can lead to a different line of research work by proving these results themselves.\n\nHere, the non-linear bandit settings tend to pose extra challenges compared with linear bandit settings.\nFor instance, for kernelized bandit works, their lower bounds will depend on kernel characteristics, such as $\\Omega(C(\\log(T))^{d/2})$ for the SE kernel and $\\Omega(C^{\\frac{v}{d+v}}T^{\\frac{v}{d+v}})$ for the $v$-Mat\\'ern kernel [63,12]. We see that the order of corruption level $C$ and whether the lower bound is related to non-logarithmic $T$, will both depend on kernel properties.\n\nAs few restrictions are imposed for reward mapping $h(\\cdot)$ for neural bandits, we will need to use regression models based on Neural Tangent Kernel (NTK) to perform theoretical analysis.\nIn this case, without a well-established existing knowledge base for NTK (e.g., number of functions $M$ needed for the functional separateness condition [63,15] for NTK), it will require significant efforts to obtain such a lower bound for neural bandit cases, and can lead to a different line of research work by proving these results. \nIn this case, we consider deriving such a theoretic regret lower bound as one promising and challenging future direction of this paper.", "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": "", "extra_scores": {}}, {"review_id": "yvA2vE1qwU", "reviewer": "Reviewer_MEPN", "summary": "This paper presents R-NeuralUCB, a neural-based network UCB algorithm for robustness under adversarial rewards corruptions in stochastic $K$ multi-armed contextual bandits. Based on NeuralUCB [1], before the arm pulling, R-NeuralUCB additionally optimizes a context-aware gradient descent for each arm by using an objective function. The first term of this function is the weighted-arm uncertainty information from the cumulative observed training samples. The second term is inspired by existing works on enhancing model robustness with the regularization technique between current and initial weights. Contribution includes:\n- A novel R-NeuralUCB algorithm, where each arm weight is formulated by the weight between gradient norm UCB w.r.t. context $x$ and weights $\\theta$ of training and candidate arm. This intuitively means when the uncertainty w.r.t. candidate's arm is high, this weight will be low, encouraging the model to focus on the regularizer to avoid over-fitting. Conversely, if the uncertainty w.r.t. candidate's arm is low, yielding the weight will be high, pushing the model focus on the observed training samples\n- A theoretical upper bound for the proposed algorithm, where the bound for R-NeralUCB is $\\tilde{\\mathcal{O}}(\\tilde{d}\\sqrt{T}+C\\beta^{-1}\\tilde{d}\\)$, where $\\tilde{d}\\$ is the dimensions of NTK matrix, $T$ is the time-horizon, C is the adversarial corruption level C, and $\\beta$ is the data-dependent gradient deviation term. Additionally, the proof of this bound does not require the NTK matrix to be positive-definite.\n- Experiments show the proposed algorithm has a lower cumulative regret than Neural-UCB and other baselines across different datasets and reward corruption types.", "questions": "1. Can you draw two figures, including the first bar chart for the model size (i.e., number of neural network parameters) comparison, and the second line graph for the inference speed (i.e., latency) comparison at each time $t$?\n2. While NeuralUCB [1] set $T=15,000$ in MNIST, why do the authors only limit $T=10,000$? Is this because of the computational reason? Also, do you have any comments to improve the computational efficiency of your algorithms?\n3. The paragraph from L-207 to L-212 does not make sense to me. Specifically, why replacing the initial weight $\\theta_0$ by the warm-start GD can reduce computational cost? Do you mean the computational cost regarding the update step in L-15 in Algorithm 1? Does this replacement affect the loss function in Eq. 5? Do you have any empirical results in this regard (i.e., cumulative regret results between with and without the replacement)?\n4. Can you make a comparison in corruption-free experiments, i.e., set $C=0$? I think this will test whether your Context-aware GD in Eq. (5) hurt NeuralUCB or not. Also in your experiments, at each time $t$, how do you set whether an arm is attacked or not? How do you think about the context corruption like using MNIST-C?\n5. Have you considered the stochasticity of $C$ in your regret upper bound? Empirically, instead of fixing $C$ across time horizon $T$, $C$ can be stochastic, we also can empirically test them by (e.g., set $C$ to be monotonic increase, decrease, or randomly distributed by some mean and variance).\n6. How do you make the neural network model in the experiment to be over-parameterized? Since the true reward function is unknown, how do you select the sub-gaussian value $\\nu$ in your algorithm? Since $\\beta$ in Theorem 5.6 depends on the selection of $\\alpha$ in Eq. 4, does this mean that we can fine-tune the regret in the experiment by searching $\\alpha$?\n\nReferences:\n\n[1] Zhou et al., Neural Contextual Bandits with UCB-based Exploration, ICML, 2020.\n\n[2] Xu et al., Neural Contextual Bandits with Deep Representation and Shallow Exploration, ICLR, 2022.\n\n[3] Bogunovi et al., Corruption-Tolerant Gaussian Process Bandit Optimization, AISTATS, 2020.\n\n[4] Zhang et al., Contextual Gaussian Process Bandits with Neural Networks, NeurIPS, 2023.", "limitations": "Please see my comments on the Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper has clear mathematical notations, is very well-written, and is clear to understand the important aspects of the algorithm.\n- I like the motivation to improve the robustness of neural-UCB-based methods under reward corruption because of their real-world applications.\n- The proposed algorithm also makes sense to me, the weighing arm is based on the uncertainty of the upper confidence bounds, reflecting the reward estimation uncertainty of the model. Therefore, we can use these weights to control the fitting of the cumulative observed training data and prevent impacts caused by adversarial corruption.\n- The theoretical contribution of this paper is good, yielding a solid R-NeralUCB algorithm. I appreciate the theory of this paper for two main reasons. Firstly, in the scope of the neural-based contextual bandits, I think this is the first work to provide a regret upper bounds with the reward corruption value. Secondly, while neural-based UCB often assumes the NTK matrix in Def. 5.1 is positive-definite, the theoretical analysis of this paper does not require this assumption.\n- The authors additionally provide a base algorithm NeuralUCB-WGD, which uses the weighted GD with Neural-UCB. Theoretical analysis and experimental results of NeuralUCB-WGD are also provided sufficiently. \n- Experiments are also elevated across different settings, including datasets, reward corruption types, and running seeds.", "weaknesses": "- My biggest concern about R-NeuralUCB is its computational inefficiency, causing a big limitation in the real world with neural-based contextual bandits. Specifically, while NeuralUCB has been criticized be inefficient by the exploration with UCB performed over the entire DNN parameter space and its gradient [2], R-NeuralUCB is even less inefficient than NeuralUCB for the following reasons:\n  - Firstly, R-NeuralUCB requires different neural network model weights for different arms, so R-NeuralUCB is very expensive when $K$ is high. \n  - Secondly, for each time $t \\in [T]$, R-NeuralUCB requires additionally optimizing the Context-aware GD objective function in Eq. 5 $K$ times. \n  - Thirdly, this Context-aware GD objective function requires computing each weight for each cumulative data, and the numerator of this weight requires finding the min across $\\mathcal{X}_t$, meaning that when $t$ and $K$ increase, the computational cost also increases.\n- The proposed algorithm requires to define some non-trivial hyper-parameters such as $\\alpha$ in Eq. 4 and $\\lambda$ in Eq. 5.\n- Similar to other neural-networking-based contextual UCB papers, the proofs must assume the activation of the network structures is ReLU, the neural network model is over-parameterized, and the dimension of the weight matrix at middle layers $l$-th has the same size $m \\times m$. As also mentioned by the authors, the theory lacks the lower bound for the regret of R-NeuralUCB.\n- Lack of experiment settings, e.g., comparison with other baselines [2, 3, 4], synthetic (i.e., the true reward function is known) and other real-world datasets [1], and a longer time horizon $T$. In some experiments (e.g., Amazon dataset), R-NeuralUCB does not significantly outperform other baselines.\n- Miscellaneous: In Figure 1 on MovieLes Dataset right, the cumulative looks are not significantly lower than others. I would recommend the authors zoom in on it by limiting the y-axis value to 400, so the readers can see your better regret more easily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the reviewer for your valuable questions and comments. \nGiven the page limit of 6000 characters, we will try our best to provide our detailed response in the form of Q\\&A. Please also see our manuscript for cited papers. *Thank you!*\n\n\n**Q1: Discussion on computational efficiency? Why use warm-start GD?**\n\n*Due to page limit, please kindly refer to our \"Global Response\" for complementary discussions.*\n\nFirst, we would like to mention that the warm-start GD process (detailed descriptions and pseudo-code are in Appendix Subsection B.6) here is to reduce the computational cost for calculating arm-specific network parameters (line 9, Algorithm 1) in practice.\n\nIn round $t$, for each candidate arm $x_{i, t}, i\\in [K]$, we can acquire its arm-specific parameters $\\theta_{i, t-1}$ by fine-tuning existing trained parameters $\\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\\theta_{0}$ with a large number of samples.\nThe intuition is analogous to meta-learning works [Finn et al.], where we can consider each candidate arm as a \"task\". In this case, for round $t$, we can start from previously trained model parameters $\\theta_{t-2}$, and adapt $\\theta_{t-2}$ to each candidate arm (task) with a small number of training samples to obtain arm(task)-specific parameters. \nThis helps R-NeuralUCB (1) reduce computational costs of calculating arm weights for GD, and keep inference time relatively stable across horizon $T$, since we are applying a fixed number of samples for adaptation; (2) reduce GD iterations needed, as starting from $\\theta_{0}$ requires more GD iterations for model convergence.\n\n\nIn the \"Global Response\" PDF file: (1) Experiments on warm-start vs. restarting from $\\theta_{0}$ (Figure 1) *given the same number of training (adaptation) samples*. We see the warm-start process can improve performances. (2) Experiments based on increased number of arms $K$ ($K=50, 100$, Figure 2). We see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable. \n\n\n*[Finn et al.] Model-agnostic meta-learning for fast adaptation\nof deep networks.*\n\n\n**Q2: Additional experiments: inference speed with different model sizes? $T=15000$? Corruption-free experiments? Stochastic magnitude of corruption $C$?**\n\n\n\nDue to page limit, please kindly see our \"Global Response\" and attached PDF file for these experiments.\n\n\n- *Experiment 2* (Figure 1): Experiments with $T=15000$.\n\n- *Experiment 4* (Figure 3): Model size comparison, and line graph for inference speed.\n\n- *Experiment 5* (Figure 4): Corruption-free experiments.\n\n- *Experiment 6* (Figure 4): Stochastic magnitude of corruption experiment (increasing corruption probability).\n\n\n\n\n**Q3: Neural network over-parameterization?**\n\nAnalogous to existing works (e.g. [76,74,7,8]), we utilize a two-layer fully-connected (FC) neural network ($L=2$) with hidden dimension $m=200$ for experiments, as in Appendix Subsection A.1. \n\n\nIn terms of over-parameterization, we admit that for basically all the neural bandit works with experiments (e.g. [74,43,21,6,7,8]), there exists a gap between experiments and theoretical analysis. \nOn one hand, along with more levels $L$ and larger hidden dimension $m$, neural networks will become increasingly difficult to train, more time consuming for inference, and more demanding for computational resources. \nIn this case, to make neural bandits practical for real applications, \nneural bandit works generally use an ordinary-size neural network for experiments. It is also shown that with ordinary-size neural networks, neural bandit algorithms can already achieve significant performance gains over linear and kernel methods [76,74,7,8,60].\nOn the other hand, from the theoretical perspective, neural networks need to be over-parameterized with $m\\geq \\mathcal{O}(Poly(T))$, so that they can approximate an arbitrary  reward mapping function $h(\\cdot)$. Meanwhile, with over-parameterization, the difference between NTK-based regression models and neural networks will be sufficiently small for regret analysis, which makes it necessary for neural bandit papers. \nTherefore, we adopt a two-layer FC network for experiments, while performing analysis under over-parameterization settings, as in most existing neural bandit works (e.g., [76,74,7,8,60]).\n\n\nWe have also include above discussions in the manuscript as reference to readers.\n\n\n\n\n\n**Q4:  Can be fine-tune $\\alpha$ to control $\\beta$ value in the regret bound?**\n\n\n\n\nBased on line 184 in the manuscript, for each arm $x\\_{i, t}$, we can represent its arm weight as $w\\_{i, t}^{(\\tau)} = \\min\\\\{ 1,\\alpha\\cdot \\textsf{frac}\\_{\\tau}(x\\_{i, t}; \\mathcal{X}\\_{t}, \\bar{\\Sigma}\\_{t-1})  \\\\}, \\tau\\in [t-1]$, while the minimum fraction value $\\beta$ is defined as $\\beta = \\min\\_{ t\\in [T], \\tau\\in [t-1]} [ \\min\\\\{ \\textsf{frac}\\_{\\tau}(x\\_{t}; \\mathcal{X}\\_{t}, \\bar{\\Sigma}\\_{t-1}), \\textsf{frac}\\_{\\tau}(\\tilde{x}\\_{t}; \\mathcal{X}\\_{t}, \\bar{\\Sigma}\\_{t-1})  \\\\} ]$ (line 301).\nIn this case, tuning parameter $\\alpha$ will not directly alter the $\\beta$ value, since $\\beta$ only explicitly depends on the fraction term $\\textsf{frac}(\\cdot)$ which is determined by candidate arms.\nOn the other hand, different $\\alpha$ can correspond to distinct $\\kappa^{2}$ values in Theorem 5.6, which is the round-wise minimum arm weight. This will consequently affect the regret bound, as in line 307 of Theorem 5.6.\n\n\n\n\n\n\n\n**Q5:  Comments for Figure 1?**\n\nWe sincerely appreciate your comments on improving the paper presentation, and we have integrated these comments into the manuscript.\n\n\n\n\n\n**Q6: Questions about implementation?**\n\n- \"How arms are corrupted?\": Please see \"Global Response\" Q3.\n\n\n- \"Context corruption?\": Please see \"Global Response\" Q4.\n\n\n- \"How to choose $\\nu$?\": Please see \"Global Response\" Q5.", "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": "", "extra_scores": {}}, {"review_id": "Dniy41gg4Z", "reviewer": "Reviewer_Fhvw", "summary": "This paper proposes a novel neural contextual bandit algorithm, called R-NeuralUCB, to improve robustness against adversarial reward corruptions. The authors provide regret analysis for R-NeuralUCB under over-parameterized neural network settings, without the commonly adopted arm separateness assumption. The authors also empirically compare R-NeuralUCB with baseline algorithms on three real data sets, under different adversarial corruption scenarios.", "questions": "In the experiments, NeuralUCB and NeuralTS have similar performance as R-NeuralUCB. Is it possible that these two methods also have sublinear regret under adversarial attacks?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written. To the best of my knowledge, this work proposes the first theoretical result for neural bandits with adversarial corruptions. The theoretical analysis seems solid and the experiments show that R-NeuralUCB outperforms baseline algorithms in the corruption setting.", "weaknesses": "My main concern is about the computational costs. Notice that R-NeuralUCB need to maintain a neural network for each arm. Thus I think R-NeuralUCB could be very expensive when $K$ is very large. I will be happy if the authors could provide some discussions on the computational costs and show some empirical results for larger $K$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the reviewer for your valuable questions and comments. \nGiven the page limit of 6000 characters, we will try our best to provide our detailed response in the form of Q\\&A. Please also see our manuscript for cited papers. *Thank you!*\n\n\n\n\n\n**Q1: Overall discussion on computational efficiency? Performance with large $K$?**\n\n\n\n\nPlease see our \"Global Response\" PDF file for added experiments. (1) With experiments on warm-start vs. restarting from $\\theta_{0}$ given the same number of training (adaptation) samples (Figure 1), we see the warm-start process can improve performances. (2) With experiments based on increased number of arms $K$ ($K=50, 100$, Figure 2), we see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable. \n\nIn practice, for our experiments, we can adopt the warm-start GD process (details and pseudo-code are in Appendix Subsection B.6) to reduce the computational cost, in terms of deriving the arm-specific network parameters (line 9, Algorithm 1). \nIn round $t\\in \\\\{3, \\dots, T\\\\}$, for each candidate arm $x_{i, t}, i\\in [K]$, we can acquire its arm-specific parameters $\\theta_{i, t-1}$ by fine-tuning existing trained parameters $\\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\\theta_{0}$ with a large number of samples.\nSimilar ideas are also applied by other bandit-related works (e.g., [9]).\nThe intuition is inspired by meta-learning [Finn et al.] where we consider each candidate arm as a \"task\". In this case, for round $t$, we can start from previously trained model parameters $\\theta_{t-2}$, and adapt $\\theta_{t-2}$ to each candidate arm (task) with a small number of training samples to obtain arm(task)-specific parameters. This also reduces our computational costs of calculating arm weights for GD, and keep the inference time relatively stable across rounds.\n\n\n\nMeanwhile, it is also a common practice for neural bandit works to adopt warm-start training in practice. On one hand, neural bandit works generally formulate their GD training process by starting from randomly initialized $\\theta_{0}$, in compliance with theoretical analysis requirements. On the other hand, however, for their experiments and source code (e.g, [76,74,7,8,60]), it is a common technique to train model parameters incrementally, by updating trained parameters from previous rounds, since it is more practical and computationally efficient for real applications.\n\n\n\n\nTherefore, we adopt the following approaches to strike a good balance between model performance and computational costs: \n\n- (1) Inspired by meta-learning ideas [Finn et al.], we utilize warm-start GD by adapting previously trained network parameters $\\theta_{t-2}$ for each candidate arm with a small number of training samples, instead of training from $\\theta_{0}$ with a large number of samples. Details are in Appendix Subsection B.6.\n\n- (2) Based on our formulation of the warm-start GD process (Algorithm 2, Subsection B.6), we will sample a fixed number of mini-batch training samples (i.e., received arm-reward pairs) for each candidate arm to calculate arm weights and perform GD. This is inspired by the idea of mini-batch warm-start GD training [9]. In this case, a fixed number of training samples can help the round-wise inference time stay relatively stable, without growing drastically along with $T$. \n\n\n\n*[Finn et al.] Model-agnostic meta-learning for fast adaptation\nof deep networks.*\n\n\n\n\n\n\n\n\n**Q2: Is it possible that Neural-UCB and Neural-TS also have sub-linear regret under adversarial attacks?**\n\n\nWe agree with the reviewer that it is interesting and important to investigate the regret bound of vanilla neural bandit algorithms, in order to better understand the benefit of proposed methods. In particular, to offer some insights on regret bound of Neural-UCB, one possible route is to follow an analogous approach as the regret analysis of NeuralUCB-WGD. \nOn the other hand, regarding Thompson Sampling based approaches, their analysis can be significantly different from our UCB-based methods, where we consider UCB-based analysis in this paper. Therefore, we consider the regret analysis of Neural-TS under corruptions as a part of future works.\n\nHere, the key idea is to quantify the impact of adversarial corruptions upon the confidence ellipsoid around trained parameters.\nBy following the derivations in Lemma F.1, denoting the corruption-free confidence radius as $\\tilde{\\gamma}\\_{t-1}$ in round $t$, we can have the corrupted confidence ellipsoid for Neural-UCB as \n$\\mathcal{C}\\_{t-1} = \\\\{ \\theta: \\\\|\\theta - \\theta\\_{t-1}\\\\|\\_{\\Gamma\\_{t-1}} \\leq \\gamma\\_{t-1} / \\sqrt{m} \\\\}$, where $\\gamma\\_{t-1} = \\tilde{\\gamma}\\_{t-1} + \\mathcal{O}(CL\\lambda^{-1/2})$.\nThis result is derived by applying $w\\_{\\tau}=1, \\tau\\in [t-1]$ and the fact $\\sum\\_{\\tau\\in [t]}|c\\_{\\tau}| \\leq C$, as well as Lemma G.2 and the initialization of the gradient covariance matrix $\\Gamma$.\nAs a result, following the proof flow of Lemma 5.3 in [76], we can have regret upper bound $\\tilde{\\mathcal{O}}(\\tilde{d}\\sqrt{T} + \\sqrt{S\\tilde{d}T} + CL\\sqrt{\\tilde{d}T/\\lambda})$, which will introduce an additional $\\tilde{\\mathcal{O}}(\\sqrt{T})$ to the corruption-dependent term.\nNote that although it is possible for Neural-UCB to have a sub-linear cumulative regret when $C$ is a small constant, our R-NeuralUCB and NeuralUCB-WGD can remove the direct dependency of horizon term $T$, and manage to achieve non-trivial $\\tilde{\\mathcal{O}}(C\\tilde{d}\\beta^{-1})$ and $\\tilde{\\mathcal{O}}(C\\tilde{d}^{3/2} + C\\tilde{d}\\sqrt{\\lambda}S)$ respectively for corruption-dependent terms.\nFor readers' reference, we have also added above discussions to the manuscript Appendix.", "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": "", "extra_scores": {}}, {"review_id": "UKIRS0UgIJ", "reviewer": "Reviewer_1FL3", "summary": "This paper studies the problem of contextual bandits with neural function approximation faced with adversarial corruptions. It proposes an algorithm named R-NeuralUCB, which can improve the robustness of neural contextual bandit training. It provides regret analysis and  conducts experiments to show the advantage of the new algorithm.", "questions": "See Weaknesses", "limitations": "The authors have addressed the limitations and potential societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposes a new algorithm for neural contextual bandits, which is based on a new technique that customizes individual sets of network parameters for each candidate arm. It can improve the robustness under adversarial corruption.\n2. Theoretical analysis has been provided, with a robust regret bound dependent on the effective dimensions of the neural network.\n3. Experiments are conducted on publicly available real-world data sets to show the better performance of the proposed algorithm.", "weaknesses": "1. The computational cost is huge. Compared with NeuralUCB-WGD, the main difference lies in the separate neural networks for each candidate arm, which greatly increases the computation cost, as it needs to compute the gradient descent for every arm in each round separately.\n\n2. In [1], Theorem 4.12 shows that if when no corruption, $Regret(T) \\le R_T$, then when $C > \\Omega(R_T/d)$, the algorithm will suffer $\\Omega(T)$ regret. It seems contradictory with Theorem 5.6 for unknown $C$.\n\n3. Theorem 5.6 relies on the tuning of parameter $\\alpha$, to achieve that $\\min w_{i,t}^\\tau = \\kappa^2, \\forall t$, which is unclear how to achieve.\n\n\n[1]  He et al. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions Neurips 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the reviewer for your valuable questions and comments. \nGiven the page limit of 6000 characters, we will try our best to provide our detailed response in the form of Q\\&A. Please also see our manuscript for cited papers. *Thank you!*\n\n\n\n**Q1: Overall discussion on computational efficiency?**\n\n\n\n\n\nPlease kindly refer to our \"Global Response\" for complementary discussions.\n\nTo reduce the computational cost for obtaining arm-specific network parameters (line 9, Algorithm 1) in practice, for our experiments, we apply the warm-start GD strategy to strike a good balance between performances and computational costs. Pseudo-code and detailed descriptions are in Appendix Subsection B.6 due to page limit. \n\nIn round $t\\in \\\\{3, \\dots, T\\\\}$, for each candidate arm $x_{i, t}, i\\in [K]$, we can acquire its arm-specific parameters $\\theta_{i, t-1}$ by fine-tuning existing trained parameters $\\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\\theta_{0}$ and training with a large number of samples.\nThe intuition is inspired by meta-learning works [Finn et al.], where we consider each candidate arm as a \"task\". In this case, for round $t$, we can start from previously trained model parameters $\\theta_{t-2}$, and adapt $\\theta_{t-2}$ to each candidate arm (task), with a small number of training samples to obtain arm(task)-specific parameters. \n\nThis helps R-NeuralUCB (1) reduce computational costs of calculating arm weights for GD, and keep inference time relatively stable across horizon $T$, since we apply a fixed number of samples for adaptation; (2) reduce GD iterations needed, as starting from $\\theta_{0}$ will require more GD iterations for model convergence.\n\n\nMeanwhile, it is also a common practice for neural bandit works to adopt warm-start training in practice.\nHere, on one hand, neural bandit works generally formulate their GD training process by starting from randomly initialized $\\theta_{0}$ (e.g, [76,74,7,8,60]), in compliance with theoretical analysis requirements. On the other hand, however, for their experiments and source code, it is common to train model parameters incrementally, by updating trained parameters from previous rounds, since it is more computationally efficient for real applications.\n\n\n\nPlease see our \"Global Response\" PDF file for added experiments: (1) With experiments on warm-start vs. restarting from $\\theta_{0}$ (Figure 1) given the same number of training (adaptation) samples, we see the warm-start process can improve performances. (2) With experiments based on increased number of arms $K$ ($K=50, 100$, Figure 2), we see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable. \n\n\n\n*[Finn et al.] Model-agnostic meta-learning for fast adaptation\nof deep networks.*\n\n\n\n\n\n\n\n\n\n**Q2: Relationship with the lower bound in (He et al., 2022)?**\n\n\nFirst, we would like to first recall that Theorem 4.12 of [35] relies on Assumption 2.1 of [35], which formulates a learning problem under linear contextual bandit settings. \nThen, in our Theorem 5.6, when $C=0$, we have the corruption-free regret of $\\tilde{\\mathcal{O}}(\\tilde{d}\\sqrt{T} + S\\sqrt{\\tilde{d}T})$. In this case, after setting $C = \\Omega(R_{T}/d)$, we will end up with a regret bound of $\\tilde{\\mathcal{O}}\\left( (\\tilde{d}^{2}\\sqrt{T} + S\\tilde{d}^{3/2}\\sqrt{T}) \\cdot C \\beta^{-1}d^{-1} \\right)$.\nHere, we note that with the proof flow of Theorem 4.12 in [35] and learning problem specified by Assumption 2.1 of [35], our effective dimension term $\\tilde{d}^{2}$ can possibly depend on horizon $T$, and grow along with $T$ [22].\nAs a result, although the regret bound only contains $\\sqrt{T}$ terms, the overall order of regret bound can be equal or greater than $\\mathcal{O}(T)$ due to effective dimension $\\tilde{d}^{2}$, as discussed in [22].\nThis is distinct from linear bandits works, where regret bounds generally only consist of horizon $T$ and other $T$-independent terms, such as context dimension $d$ and fixed $T$-independent linear parameter norm $\\|\\theta^{*}\\|_{2}$.\nTherefore, our Theorem 5.6 will not contradict with Theorem 4.12 of [35].\n\n\nMeanwhile, we also note that for stochastic neural bandit works, the effective dimension term $\\tilde{d}$ (or information gain for kernelized bandits [65,12]) is generally inevitable [76,74,7,43], since we need to bridge over-parameterized networks with the NTK-based regression model. Comparably, kernelized bandits [12,65,24] will also generally involve similar terms as costs of modeling the unknown non-linear reward mapping function.\n\nWe appreciate the reviewer for your question. For readers' reference, we have included above discussions to Appendix Subsection B.7, as the supplement to our current discussion of the lower bound.\n\n\n\n\n\n\n**Q3: How to tune parameter $\\alpha$ to satisfy the requirements of $\\kappa$?**\n\nWe first recall that in round $t\\in [T]$, we have arm weights $w\\_{i, t}^{(\\tau)}, \\tau\\in [t-1], i\\in [K]$. Based on line 184, we can also denote $w\\_{i, t}^{(\\tau)} = \\min\\\\{ 1,\\alpha\\cdot \\textsf{frac}\\_{\\tau}(x\\_{i, t}; \\mathcal{X}\\_{t}, \\bar{\\Sigma}\\_{t-1})  \\\\}$.\nHere, instead of deeming $\\alpha$ as a fixed value across horizon $T$, we can consider $\\alpha$ to be varying across different rounds, denoted by $\\alpha\\_{t}, t\\in [T]$. \nWith $\\textsf{frac}\\_{t}^{\\textsf{min}} = \\min\\_{i\\in [K], \\tau\\in [t-1]}[ \n\\textsf{frac}\\_{\\tau}(x\\_{i, t}; \\mathcal{X}\\_{t}, \\bar{\\Sigma}\\_{t-1}) ]$, we can set each $\\alpha\\_{t} = \\kappa^{2} / \\textsf{frac}\\_{t}^{\\textsf{min}}, \\kappa\\in (0, 1)$.\nIn this way, we can consequently have $\\min\\\\{w\\_{i, t}^{(\\tau)}\\\\}\\_{i\\in [K], \\tau\\in [t-1]} = \\kappa^{2}, \\forall t\\in [T]$.\n\nTo improve the paper presentation, we have also added above explanations to the manuscript for readers' reference.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to sincerely thank reviewers for your valuable questions and comments. *Please refer to attached PDF for added experiments.*
Given the page limit of 6000 characters, we will try our best to provide our detailed response.  Please also see our manuscript for cited papers. *Thank you!*





**Q1: Overall discussion on computational efficiency?**


In practice, for our experiments, we can adopt the warm-start GD process (details and pseudo-code are in Appendix Subsection B.6) to reduce the computational cost, in terms of deriving the arm-specific network parameters (line 9, Algorithm 1). 
In round $t\in \\{3, \dots, T\\}$, for each candidate arm $x_{i, t}, i\in [K]$, we can acquire its arm-specific parameters $\theta_{i, t-1}$ by fine-tuning existing trained parameters $\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\theta_{0}$ with a large number of samples. Similar ideas on mini-batch warm-start training are also applied by other bandit-related works (e.g., [9]).



Meanwhile, it is also a common practice for neural bandit works to adopt warm-start training. On one hand, neural bandit works generally formulate their GD training process by starting from randomly initialized $\theta_{0}$ (e.g, [76,74,7,8,60]), in compliance with theoretical analysis requirements. On the other hand, however, for their experiments and source code, it is common to train model parameters incrementally, by updating trained parameters from previous rounds, since it is more practical and computationally efficient for real applications.





In this case, for our experiments, in order to strike a balance between computational costs and model performances:



- (1) Inspired by meta-learning ideas [Finn et al.], we utilize warm-start GD by adapting previously trained network parameters $\theta_{t-2}$ for each candidate arm with a small number of training samples, instead of training from $\theta_{0}$ with a large number of samples. Details are in Appendix Subsection B.6.

- (2) Based on our formulation of the warm-start GD process (Algorithm 2, Subsection B.6), we will sample a fixed number of mini-batch training samples (i.e., received arm-reward pairs) for each candidate arm to calculate arm weights and perform GD. This is inspired by the idea of mini-batch warm-start GD training [9]. In this case, a fixed number of training samples can help the round-wise inference time stay relatively stable, without growing drastically along with $T$. 




*[Finn et al.] Model-agnostic meta-learning for fast adaptation
of deep networks.*



**Q2: Complementary experiment results?**




- **Experiment 1** (Figure 1): Warm-start vs. restarting from $\theta_{0}$ for each round, *given the same number of training (adaptation) samples*. We see the warm-start process can improve performances, as it can leverage previous trained parameters while restarting from $\theta_{0}$ can be hard to converge.

- **Experiment 2** (Figure 1): Here, we use $T=10000$ for both recommendation data sets (MovieLens, Amazon) and MNIST to maintain consistency, similar to existing neural bandits for recommendation works, which apply $T=10000$ for their recommendation data sets (e.g., [60,7]). Here, we include experiments with $T=15000$, where our proposed methods can maintain good performances.

- **Experiment 3** (Figure 2): Experimental results with increased number of arms $K$. We see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable.


- **Experiment 4** (Figure 3): Number of parameters and inference time, given different hidden dimensions. We can see that the inference time stays relatively stable, due to a fixed number of adaptation samples for warm-start GD.

- **Experiment 5** (Figure 4): MNIST data set under corruption-free setting, where our proposed methods can maintain competitive performances compared with baselines.


- **Experiment 6** (Figure 4): MovieLens data set with increasing corruption probability, and the probability of corrupting a chosen arm is $p_{t}$, where $p_{t}$ starts from $p_{0} = 20\%$ and increases by $\Delta p = 0.2\%$ for every 100 rounds. NeuralUCB-WGD and R-NeuralUCB can still enjoy an advantage over baselines.




**Q3: How arms are corrupted for our experiments?**

As in the caption of Figure 1: (1) For MovieLens and Amazon, the adversary will randomly decide whether to corrupt the reward of each chosen arm with a probability of 20\% or 50\%; (2) For MNIST data set, we consider a fixed budget $C=2000$ or $C=4000$, and randomly sample 2000 or 4000 rounds across $T=10000$ as corrupted.




**Q4: Context corruption?**

Recall that we use NTK-based regression to bridge reward mapping function $h(\cdot)$ and over-parameterized neural network $f(\cdot)$, where we quantify impacts of reward corruptions by decomposing NTK-based regression parameters as in Appendix Subsection C.4.
However, this approach will fail under arm context corruption settings. With gradient-based mapping being $g(\cdot)$, it can be difficult to measure the difference between projected context with corruption $g(x+\Delta x)$ and the original projection $g(x)$. 
In this case, we may need additional assumptions, such as Lipschitz-smoothness assumption for the neural network [Du et al.] or Lipschitz reward mapping function [42]. We propose to explore this direction in our future works.


*[Du et al.] Gradient descent finds global minima of deep neural networks.*



**Q5: How to choose $\nu$?**

Similar to existing stochastic neural bandit works (e.g. [76,74,7]), when the random noise variance proxy $\nu$ is unknown to the learner, we consider it as a tunable parameter controlling exploration intensity, and use grid search to find a good $\nu$. Please also find related parameter study in Appendix Subsection A.2.

Meta-review: The paper examined neural contextual bandits in the presence of adversarial reward corruptions. In this setting, the adversary can alter the reward after the bandit player has chosen an action but is constrained by a total corruption budget of size C.
The paper introduced a robust neural contextual bandit algorithm named R-NeuralUCB, which incorporates a novel context-aware gradient descent process. This process accounts for the uncertainty associated with both candidate arms and training samples. Additionally, when the neural network is over-parameterized, the paper offers a theoretical analysis of regret using the Neural Tangent Kernel (NTK) technique.
The authors provide regret analysis for R-NeuralUCB under over-parameterized neural network settings, without the commonly adopted arm separateness assumption. The authors also empirically compare R-NeuralUCB with baseline algorithms on three real data sets, under different adversarial corruption scenarios.

All reviewers agreed that the paper features a solid theoretical and empirical study for the study of robust stochastic bandits under adversarial corruptions. On the other hand, reviewers raised a common concern about computational cost. The authors presented an approach that deviated from the proposed algorithm, which is a balance between cost and performance guarantees, which I believe is reasonable.
Decision: Accept (poster)