Robust Neural Contextual Bandit against Adversarial Corruptions

Authors: yunzhe  qi
yikun  ban
arindam  banerjee
jingrui  he
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 23:36:53

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.

Main paper: 
 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, 7] . While these algorithms have been proved effective for numerous online learning tasks, they can be susceptible to the malicious feedback from the environment, such as 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, 16] , where received arm rewards can be potentially "corrupted" by the unknown adversary. In this case, bandit algorithms need to 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, 16] , 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 it becomes increasingly complex.In the face of this challenge, neural bandit algorithms [86, 84, 11, 12] 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 they are linear or non-linear, along with suitable exploration strategies for tackling the exploitationexploration dilemma [5, 59] . While neural bandit algorithms have been proved effective [9, 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 it 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 a positive-definite Neural Tangent Kernel [NTK] Gram matrix [86, 84, 26] , or positive arm Euclidean distances [11, 67] ), 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-UCB (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-NeuralUCB simultaneously perceives the uncertainty levels of candidate arms, and adaptively customizes network parameters for each of these candidates. To deal with the exploitation-exploration dilemma, R-NeuralUCB is equipped with an 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-NeuralUCB's theoretical robustness under adversarial scenarios. Our contributions can be summarized as follows:• Problem Settings and Proposed algorithm: We study a 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 (1) similar to existing neural bandit works, our R-NeuralUCB interestingly maintains separate model parameters specific to the different candidate arms, for a 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-WGD in Appendix E). • Theoretical Analysis: With over-parameterized neural networks, we present the regret analysis for R-NeuralUCB. 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 + C d).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-NeuralUCB can achieve better performance, and is less vulnerable to reward corruptions than baselines. 
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 mis-specifications [36, 55, 33, 53, 83, 75] , where the deviation of reward estimation comes from problem modeling instead of the adversary. On the other hand, kernelized bandits [15, 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 [18, 80] . However, compared with neural bandit methods, these works generally require assumptions on the reward function prior, which may not be satisfied in real-world scenarios.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 [86] applies a fully-connected (FC) neural network for reward estimation and utilizes corresponding network gradients for principled exploration. Comparable ideas have been leveraged by other neural bandit works [84, 50, 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, 51] with graph neural networks [77, 34, 35] . Alternatively, [81] 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 an adversarial environment. 
problem definition: 
 Let T be the finite horizon. In round t ∈ [T ], the learner receives K candidate arms X t , |X t | = K, and each arm x i,t ∈ X t with arm index i ∈ [K] is described by a d-dimensional vector x i,t ∈ R d . The learner will then choose one arm x t ∈ X t and receive its reward r t . The index of x t is denoted by i t ∈ [K], s.t. x t = x it,t . Here, similar to existing works (e.g., [42, 16, 15, 86, 84] ), we define corruption-free arm reward r i,t for each candidate arm x i,t ∈ X t , as well as corrupted arm reward r t for chosen arm x t ∈ X t , asEQUATIONwhere h : R d → R is an unknown reward mapping function that can be either linear or nonlinear. ϵ i,t ∈ R stands for zero-mean ν-sub-Gaussian random noise which is standard for stochastic contextual bandit works (e.g., [24, 72, 86] ), and c t ∈ R is the unknown adversarial corruption imposed by the adversary. While kernelized bandit works (e.g., [16, 72] ) assume h(•) belongs to the RKHS induced by specified kernels, we alternatively consider h(•) as an arbitrary unknown function, and utilize the neural model to learn this mapping with flexibility.Taking expectation w.r.t. zero-mean noise ϵ, for the chosen arm x t ∈ X t , we denote its expected perturbed reward E[r t ] = h(x t ) + c t ; meanwhile, for each candidate arm x i,t ∈ X t , its expected corruption-free reward E[ r i,t ] = h(x i,t ). Here, we consider E[r] and E[ r] both fall into value range [0, 1], analogous to existing works (e.g., [86, 84, 11, 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 {x τ } τ ∈[t] up to round t, we denote received context-reward tuples with perturbed rewards as P t := {x τ , r τ } τ ∈[t] = {x iτ ,τ , r iτ ,τ } τ ∈[t] , and the corresponding context-reward tuples with corruption-free rewards asP t := {x τ , r τ } τ ∈[t] = {x iτ ,τ , r iτ ,τ } τ ∈[t], where each corruption-free but imaginary unobserved reward is r τ = h(x τ ) + ϵ τ , τ ∈ [t] based on (1) .Learning Objective. Our objective is to minimize cumulative pseudo-regret for T rounds:EQUATIONwhere E[ r t ] = h(x t ) is the expected corruption-free reward of the chosen arm x t ∈ X t , and E[ r * t ] = max xi,t∈Xt [h(x i,t )] stands for that of the optimal arm x * t ∈ X t . Corruption Level. If the adversary determines the reward corruption c i,t for each candidate arm x i,t ∈ X t beforehand, without observing the learner's choice x t , some works (e.g., [38] ) formulate the corruption level measurement asC ′ = t∈[T ] [max i∈[K] |c i,t |].In this work, similar to [42, 16] , we alternatively consider reward corruptions are determined w.r.t. particular chosen arms {x t } t∈[T ] , and formulate the corruption level as C = t∈[T ] |c t |. This leads to C ≤ C ′ .4 Proposed Algorithm: Robust Neural-UCB (R-NeuralUCB)Recall that in (1) , arm rewards under neural bandit settings are governed by the unknown reward mapping function h(•), where h(•) 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 f (•; θ) to denote an FC network with depth L ≥ 2 and width m ∈ N + : where σ(•) is element-wise ReLU activation, and we have trainable weight matricesEQUATIONθ 1 ∈ R m×d , θ l ∈ R m×m , 2 ≤ l ≤ L -1, θ L ∈ R 1×m .For the ease of notation, we denote vectorized parametersθ := [vec(θ 1 ) ⊺ , vec(θ 2 ) ⊺ , . . . , θ L ] ⊺ ∈ R p ,with the dimensionality of p, and randomly initialized parameters are denoted by θ 0 . Then, we let g(x; θ) = vec(∇ θ f (x; θ)) ∈ R p be vectorized network gradients w.r.t. input x and parameters θ.We motivate our proposed R-NeuralUCB by first mentioning a base algorithm named Neural-UCB with Weighted GD (NeuralUCB-WGD), which is elaborated in Appendix E. To begin with, NeuralUCB-WGD measures the uncertainty level of training samples (i.e., previously received armreward pairs) through their UCB values, as the UCB essentially measures arm uncertainty levels in terms of reward estimation [24, 72, 86] . Then, different from conventional neural bandit methods that treat all training samples equally [86, 84] , inspired by [42] , NeuralUCB-WGD 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 corruptions, by paying relatively more attention on the training samples (arm-reward pairs) with low uncertainty levels, for a stable GD training process. We also present corresponding regret analysis for NeuralUCB-WGD in Appendix E.2, as 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 exploitationexploration 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 exploitation-exploration strategy with other high-uncertainty candidate arms. Meanwhile, analogous to existing works (e.g., [42, 16, 15] ), NeuralUCB-WGD supposes a known corruption level C for regret analysis (Theorem E.1), which can be difficult to satisfy if we have limited knowledge regarding the unknown adversary. With the above motivations, we propose R-NeuralUCB as a refined solution to further enhance neural model robustness against potential reward corruptions. For readers' reference, we also compare our proposed R-NeuralUCB and NeuralUCB-WGD with some regret results from existing works in Table 1 . 
r-neuralucb: robust neural-ucb: 
 Our R-NeuralUCB formulates a novel context-aware GD process, by taking the uncertainty information of both candidate arms and training samples into account, for neural network training and decision making. Here, R-NeuralUCB customizes individual sets of network parameters θ i,t-1 for each candidate arm x i,t ∈ X t , i ∈ [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 1.Arm Weight Formulation. Inspired by NTK-based exploration mechanisms [86, 51, 66, 11, 84] , we measure arm uncertainty levels with the weighted gradient norm of arms. With a regularization parameter λ > 0, we first define a weight-free gradient covariance matrix Σt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m. Here, θ τ -1 is the shorthand of θ iτ ,τ -1 , representing the network parameters of the previously chosen arm With arm weights {w (4) , train parameters θ i,t-1 with GD and the armspecific loss function in (5) based on received records P t-1 . For candidate arm x i,t , calculate its benefit score U (x i,t ) based on (6) .x τ = x iτ ,τ , τ ∈ [t -1].(τ ) i,t } τ ∈[t-1] in12:end for 13:Choose arm x t = arg max xi,t∈Xt U (x i,t ) with the highest benefit score.Receive arm reward r t , and update the records, such that P t ← P t-1 ∪ {(x t , r t )}.Update the shorthand θ t-1 ← θ it,t-1 , and matrix Σt ← Σt-1 +g(x t ; θ t-1 )g(x t ; θ t-1 ) ⊺ /m. 16: end for candidate arm x i,t ∈ X t , we formulate its weight w.r.t. previously chosen armEQUATIONwith κ 2 -scaled covariance matrix beingΣ(κ) t-1 := λI + κ 2 • τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1) ⊺ /m, for a constant κ ∈ (0, 1). Alternatively, we also denote w(τ ) i,t = min 1, α • frac τ (x i,t ; X t , Σt-1 ), with frac τ (•) being a shorthand that integrally represents the fraction term in (4) . A tunable parameter α > 0 and the squared round-wise minimum weighted norm min x∈Xt ∥g(x;θ t-1 )/ √ m∥ 2 Σ-1 t-1in the numerator are applied for scaling purposes. We also include complementary discussions for arm weight scaling in Appendix B.5. Meanwhile, we have g τ = ∥g(x τ ; θ τ -1 )/ √ m∥ ( Σ(κ) τ -1 ) -1 , τ ∈ [t-1] quantifying uncertainty levels of previously chosen arms (training samples) motivated by UCB-based exploration strategies (e.g., [86, 42] ). Since previous {g τ } τ ∈[t-1] values can be reused, we only need to compute and store g t for current round t. As a result, if candidate arm x i,t is of high uncertainty (i.e., large ∥g(x i,t ; θ t-1 )/ √ m∥ Σ-1t-1 value), its arm weights {w(τ ) i,t } τ ∈[t-1]will become small. Model Training with Context-aware GD. According to line 9 in Algorithm 1, we perform model training before the actual arm recommendation in each round t ∈ {2, . . . , T }. For each candidate x i,t ∈ X t , we train its arm-specific parameters θ i,t-1 with J iterations of GD and received recordsP t-1 = {(x τ , r τ )} τ ∈[t-1] . Starting from initialization θ (0) i,t-1 = θ 0 , we have j-th GD iteration (j ∈ [J]) being θ (j) i,t-1 = θ (j-1) i,t-1 -η∇ θ L i,t (P t-1 ; θ (j-1) i,t-1 ), where η > 0 refers to the learning rate. We formulate a loss functionEQUATIONwhere the L 2 loss is scaled by arm weights w(τ ) i,t , τ ∈ [t -1] from (4). Intuitively, if arm weights w (τ ) i,t 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 t-1 , instead of staying around the random initialization θ 0 given the L 2 regularization. On the other hand, if arm weights w (τ ) i,t are small, it means that the uncertainty level in terms of reward estimation is high. In this case, we prefer being relatively conservative to prevent potentially large impacts caused by adversarial corruptions. As a result, R-NeuralUCB will focus more on the training samples in P t-1 with low uncertainty levels, and stay relatively close to the random initialization θ 0 due to the regularization term in (5) .In practice, instead of starting from θ 0 in each round t ∈ {2, . . . , T }, we can alternatively initiate the GD process from the existing trained parameters to reduce computational cost, inspired by the concept of warm-start GD [13] . Here, we can start from θ t-2 , the parameters of the previously chosen arm x t-1 , and fine-tune arm-specific parameters θ i,t-1 for each candidate arm x i,t ∈ X t , based on its loss function L i,t (•; •) and a small batch of samples from P t-1 . Further details are elaborated in Appendix B.6, and this approach is also applied for the experiments in Section 6.Arm Selection. For candidate arm x i,t ∈ X t and arm weights {w(τ ) i,t } τ ∈[t-1] , we formulate its arm- specific gradient covariance matrix Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m.Here, if the variance proxy value ν in (1) is unknown, similar to existing works (e.g., [86, 84] ), we deem ν ≥ 0 as a tunable parameter to control the exploration intensity. With our UCB-type exploration motivated by Appendix Lemma C.11, we formulate the benefit score for arm x i,t ∈ X t asEQUATIONwhere the confidence coefficientγ i,t-1 = ζ • ν log det(Σi,t-1) det(λI)-2 log(δ) + √ λS , along with a constant ζ > 0 from Lemma C.11. Afterwards, we choose x t = arg max xi,t∈Xt U (x i,t ) (line 13, Algorithm 1), based on calculated arm benefit scores in (6) . After receiving reward r t , the collected records will be updated by P t ← P t-1 ∪ {(x t , r t )} (line 14, Algorithm 1). We also update the shorthand for model parameters of the chosen arm as θ t-1 ← θ it,t-1 , and the weight-free covariance matrix Σt ← Σt-1 + g(x t ; θ t-1 )g(x t ; θ t-1 ) ⊺ /m for next round t + 1 (line 15, Algorithm 1).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 on current records, due to potential reward corruptions, which can lead to significant estimation errors. In this situation, by using the regularization term mλ 2 ∥θ -θ 0 ∥ 2 2 , 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 . 
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 a 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-free 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, 21, 3, 9, 84] , for an L-layer network of width m in (3), we let its intermediate-layer matricesθ l = Λ 0 0 Λ , l ∈ [L -1],where each element of matrix Λ is drawn from Gaussian distribution N (0, 4/m). Similarly, let θ L = (w ⊺ , -w ⊺ ), where each element of vector w is drawn from N (0, 2/m).Arm Context Normalization. To ensure arm contexts are of unit length (i.e., ∥x i,t ∥ = 1, ∀i ∈ [K], t ∈ [T ]) as in existing neural bandit works [86, 84, 11, 67, 50] , we can apply the following transformation inspired by existing works [3, 86, 84] without loss of generality: with unprocessed context x i,t , we formulate the corresponding normalized arm contextx i,t = [ xi,t 2•∥ xi,t∥2 , 1 2 , xi,t 2•∥ xi,t∥2 , 1 2 ].It can be verified that we have three properties: (i) ∥x i,t ∥ 2 = 1; (ii) no two normalized arm contexts will be in opposite directions; and (iii) f (x i,t ; θ 0 ) = 0 with the randomly initialized θ 0 .Definitions of NTK Matrices. First, we denote imaginary corruption-free models as f (•; θ t-1 ), t ∈ [T ] which are trained on corruption-free recordsP t = {x τ , r τ } τ ∈[t] , t ∈ [T ],for the sake of theoretical analysis, and the learner does not need to own the imaginary model in practice. Let {x t } t∈[T ] = {x it,t } t∈[T ] be arms chosen by the corrupted model f (•; θ), and { x t } t∈[T ] = {x ĩt,t } t∈[T ] be those chosen by the corruption-free model f (•; θ) respectively. Then, define aunion set ȂT := ({x t } T t=1 ∪ {x * t } T t=1 ∪ { x t } T t=1), based on: (i) the chosen arms {x t } T t=1 , (ii) the optimal arms {x * t } T t=1 according to (2) , and (iii) arms { x t } T t=1 chosen by the imaginary corruption-free models. Here, ȂT naturally contains unique arms from these three arm collections, with cardinality | ȂT | ≤ 3T . Meanwhile, we simply merge these three arm collections to form A T (with cardinality |A T | = 3T ), 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 A T ; (ii) the NTK matrix for non-duplicate arms H built upon the set ȂT . Definition 5.1 (NTK Gram Matrix with Possibly Duplicate Arms). Let N be the Gaussian distribution. With layer index l ∈ [L] and subscripts i, j ∈ {1, . . . , |A T |} for enumerating across arms, comparable to [47, 86] , define the following recursive processEQUATIONWith A T containing possibly duplicate arms, we denote the NTK Gram matrix H = (H L +Ψ L )/2 ∈ R 3T ×3T , and expected reward vector h = [h(x)] x∈A T ∈ R 3T . Existing works with the arm separateness assumption (e.g., [86, 84, 9, 25, 81] ) generally assume H ≻ 0, while we do not. Definition 5.2 (NTK Gram Matrix with Non-duplicate Arms). Follow the recursive process in (7) .With set ȂT containing non-duplicate arms, we denote the corresponding NTK matrixH = ( HL + ΨL )/2 ∈ R | ȂT |×| ȂT | , and expected reward vector h = [h(x)] x∈ ȂT ∈ R | ȂT | , with | ȂT | ≤ 3T .Remark 5.3 (No Arm Separateness Assumption). Existing neural bandit works generally impose separateness assumptions regarding the arm contexts: NTK-based approaches (e.g., [86, 84, 9, 51, 50] ) commonly assume H ≻ 0 which requires no two arms are parallel among {x i,t } i∈[K],t∈[T ] ; meanwhile, some other works (e.g., [11, 67] ) assume the Euclidean separateness:∥x i,t -x i ′ ,t ′ ∥ 2 > 0 if (i, t) ̸ = (i ′ , t ′ ), ∀i, i ′ ∈ [K], t, t ′ ∈ [T ].To avoid the arm separateness assumption, since ȂT contains all the unique arms from A T , we alternatively build the confidence ellipsoid upon the NTK matrix H, and the ellipsoid will also hold for all the arms in A T for regret analysis (Lemma C.1). This also leads to our tighter definition of NTK norm term S (Theorem 5.6, Remark 5.8).Fact 5.4. Let λ0 be the minimum eigenvalue of matrix H, and λ 0 be that of NTK matrix H. We have (i) λ0 = λ min ( H) > 0; and, (ii) λ0 ≥ λ 0 ≥ 0.For (i) in Fact 5.4, since ȂT contains no parallel arms, matrix H will be full-rank, leading to λ0 > 0. For (ii), if ȂT ̸ = A T , then A T contains duplicate arms and matrix H will be singular, s.t. λ0 > λ 0 = 0. Otherwise, if ȂT = A T , it will naturally lead to H = H and λ0 = λ 0 . 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 d = log det(I+H/λ) log(1+T K/λ) .We follow the pseudo-regretR(T ) = T t=1 E[ r * t -r t ] in (2), which is defined based on the expected corruption-free reward of chosen arms and optimal arms across T rounds.Instance-dependent Gradient Deviation Term β. Recall that for a candidate arm x i,t ∈ X t in round t ∈ [T ], its arm weight w.r.t. previously chosen arm x τ , τ ∈ [t-1] in (4) can be represented by w (τ ) i,t = min 1, α • frac τ (x i,t ; X t , Σt-1 ) , with the scaling parameter α > 0. Here, we define a minimum fraction value as β = min t∈[T ],τ ∈[t-1] min{frac τ (x t ; X t , Σt-1 ), frac τ ( x t ; X t , Σt-1 )} , which is formulated to quantify the gradient deviation among arms. Here, the learner is not required to know β, and we can adjust the scaling parameter α in each round t ∈ [T ] to constrain the round-wise minimum weight value min{w 5) , which leads to Theorem 5.6.(τ ) i,t } i∈[K],τ ∈[t-1] (Subsection B.T ∈ N + , denote S ≥ 2 h⊺ H-1 h, β > 0. Suppose λ ≥ S -2 , η ≤ O((T mL+mλ) -1 ), J ≥ O(T L/λ).Let f (•) be an L-layer FC network with width m, and adjust the scaling parameter α, s.t. min{w(τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 , ∀t ∈ [T ],for a tunable constant κ ∈ (0, 1) from (4). With δ ∈ (0, 1), let network width m ≥ Ω(poly(T, L, κ -1 , λ-1 0 , λ -1 , S -1 ) log(δ -1 )). With probability at least 1 -δ, R-NeuralUCB achieves the regret bound ofR(T ) ≤ O ν d log( λ + T K λ ) -2 log(δ)+S √ λ O T d/κ 2 +O C dβ -1 κ 2 log( λ + T K λ ) .The proof of Theorem 5.6 is in Appendix C. The first term on the RHS refers to the corruptionindependent regret upper bound, which comparably matches the bound O( d √ T + S dT ) in existing corruption-free neural bandit works [86, 84] . Here, our corruption-dependent term is free of the NTK norm S, which measures the complexity of reward mapping h(•) (Appendix B.4). This is different from existing works (e.g., [15] ) that include a parameter norm (similar to our NTK norm S) in their corruption-dependent terms, as the estimation error of confidence ellipsoids. In addition, inspired by [84] , we can derive a T -independent upper bound for the β -1 term, when the arm contexts are nearly spreading within some low-dimensional subspace of the NTK-induced RKHS (Appendix C.9), as 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-WGD (Theorem E.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-dependent 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 (e.g., [16] ) where C is assumed known for setting hyper-parameters 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 T K observed candidate arms, i.e., {x i,t } i∈[K],t∈[T ] , while our NTK matrices (Def. 5.1 and 5.2) only rely on arm collection A T and set ȂT , with cardinality | ȂT | ≤ |A T | = 3T . This results in our parameter norm S that can be tighter compared to existing works (e.g., [84, 86] ), because when constructing the confidence ellipsoid around the initialization Θ 0 in Lemma C.1, our ellipsoid is intuitively tighter, as it only needs to ensure Eq. C.1 holds for arms in ȂT (with cardinality | ȂT | ≤ 3T ), rather than for all T K candidate arms. Remark 5.9 (Reducing the order of d and removing the dependency of S for corruption-dependent terms). For corruption-dependent terms involving C, we have O(Cβ -1 d). Using NTK to align the information gain definition [16] with our effective dimension d, our result improves latest kernelized bandit works from O( d 3/2 ) to O( d) for corruption-dependent terms, given the NTK-induced RKHS and an indefinite arm space (Corollary 7 in [16] ). Meanwhile, our corruption-dependent term is 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 corruption-dependent 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-WGD (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-free rewards R(T ) = t∈[T ] r * t -r t . Note that the learner will still only have access to the potentially corrupted rewards r t , t ∈ [T ]. Our baselines consist of linear algorithms: Lin-UCB [24] , CW-OFUL [42] ; and conventional neural algorithms: Neural-UCB [86] , Neural-TS [84] . Complementary experiment details are in Appendix A.MovieLens and Amazon Data Sets. From "MovieLens 20M rating data set" [41] , 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, we consider the arm (user-item pair) features as the concatenation of corresponding user features and item features, which are obtained by singular value decomposition (SVD) and extracting item genome-scores respectively, with K = 10 and d = 41. The corruption-free arm rewards r i,t are user ratings normalized into range [0, 1]. Here, we consider the "exaggerated reward corruption". If one pulled arm x t is attacked and its corruption-free reward r t ≥ 0.5, we exaggerate its reward to r t = 1. Otherwise, if one pulled arm x t is attacked and r t < 0.5, we set its reward r t = 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, 58] , with K = 10 and d = 41. Similarly, the corruption-free arm rewards r i,t 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 x t is attacked and its corruption-free reward r t ≥ 0.5, we downplay its reward to r t = 0; or if the pulled arm x t is attacked and r t < 0.5, we alternatively set the corrupted reward r t = 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., [86, 84] ), given a sample x ∈ R d ′ in each round, we transform it into K = 10 arms, denoted by x 1 = (x, 0, . . . , 0), x 2 = (0, x, . . . , 0), . . . , x 10 = (0, 0, . . . , x) ∈ R 10×d ′ , s.t. d = 10 × d ′ . The arm index that the learner chooses will be its predicted class, and the reward is 1 if the sample x belongs to this class; otherwise, the reward will be 0. Here, we consider the symmetric "label-flipping" attack [39] . For example, when a sample from digit class 2 is attacked, its corrupted label will be switched to digit class 9 -2 = 7, and the corrupted arm rewards will also change accordingly.Experiment Results. The experiment results are shown in Fig. 1 , and we also include a parameter study in Appendix A.2. Due to 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-WGD and R-NeuralUCB are more robust against adversarial reward corruptions. In particular, we see that R-NeuralUCB outperforms NeuralUCB-WGD on these three data sets, which helps support our claim that it is 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 on 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 see 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. 
conclusion and future direction: 
 In this paper, we propose a novel neural bandit algorithm named R-NeuralUCB to address potential adversarial corruption issues on arm rewards. To enhance model robustness against reward corruptions, R-NeuralUCB applies a refined, context-aware Gradient Descent procedure that incorporates 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-NeuralUCB 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. 
safeguards: 
 Question: 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, or scraped datasets)?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 no such risks.• Released models that have a 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 to 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 not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: A.1 Experiment settings For all UCB-based baselines, we choose the exploration parameter through grid search over the range {0.01, 0.1, 1}. We set L = 2 for all deep learning models, including our proposed NeuralUCB-WGD and R-NeuralUCB, and set the network width to m = 200. The learning rate for all neural algorithms is chosen by grid search from the range {0.0001, 0.001, 0.01}. For all methods, we select the regularization parameter λ from the range {0.0001, 0.001, 0.01}. The scaling parameter α for NeuralUCB-WGD and R-NeuralUCB is chosen from {0.2, 0.5, 1}. All experiments are conducted on a 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 a 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 to selected samples in proportion to reward estimation confidence.• Neural-UCB [86] employs a 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 (https://grouplens.org/datasets/movielens/20m/), we initially select 5,000 movies and 10,000 users with the most reviews to form a user-movie matrix, where the entries represent user ratings. The user features x u ∈ R d ′ are derived via singular value decomposition (SVD) with a 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 i ∈ R d ′ . At each time step t, given a user u t , we encode user information into the arm contexts following the Generalized Matrix Factorization (GMF) approach [44, 88] by concatenating the featuresx i,t = [x ut ; v i ] ∈ R 2d ′, where c ∈ C t and i ∈ [K], with K = 10. Finally, we concatenate a constant 0.01 to each x i,t and normalize the entire vector to obtain x i,t ∈ R d , where d = 41. The corruption-free arm rewards r i,t are user ratings normalized to the range [0, 1]. We consider the scenario of "exaggerated reward corruption": If a pulled arm x t is attacked and its corruption-free reward r t ≥ 0.5, we exaggerate its reward to r t = 1. Conversely, if a pulled arm x t is attacked and its corruption-free reward r t < 0.5, we downplay its reward to r t = 0.For the Amazon Recommendation data set (https://jmcauley.ucsd.edu/data/amazon/ index_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 L 2 normalization, with an arm pool size of K = 10. Similarly, the corruption-free arm rewards r i,t 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 x t is attacked and its corruption-free reward r t ≥ 0.5, we downplay its reward to r t = 0. Conversely, if the pulled arm x t is attacked and its corruption-free reward r t < 0.5, we set the corrupted reward to r t = 1.We also include additional experiments with different regularization parameter values λ and exploration parameter values ν. On the MNIST data set (corruption level C = 2000), we conduct experiments for NeuralUCB-WGD and R-NeuralUCB. We present the parameter study results in Tables 2 and 3 . For both of our proposed algorithms, setting ν ∈ (0.1, 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 can cause the trained model parameters θ to remain close to their random initialization θ 0 , which can overly constrain the neural network'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 -4 and performing a grid search to identify the optimal λ is a reasonable approach for R-NeuralUCB and NeuralUCB-WGD.In this section, we provide additional discussion to complement the main body content.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, we do not perceive significant negative societal impacts that can be generated by this work.One limitation of this work is the absence of a theoretical lower bound for neural bandits with adversarial corruptions. We would like to 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 to 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 a lower bound for neural bandits with adversarial corruptions as an interesting and challenging future direction of this work. Additional discussions on the lower bound can be found in Subsec. B.7.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(•; θ) := vec(∇ θ f (•; θ)), which serve as the mapping for gradient-based NTK. In this framework, even for the same arm x, the NTK-embedded arm contexts can differ due to the corrupted parameters g(x; θ) and the corruption-free parameters g(x; θ). 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 f (•; θ), we derive the confidence ellipsoid around its parameters θ. This serves as a proxy to quantify the parameter shift of the trained corrupted model parameters θ, enabling us to establish the regret upper bound.For the theoretical analysis of 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 a tighter regret bound and eliminate the assumption of a known corruption level C, unlike in Theorem E.1, we cannot quantify the impact of C using the confidence ellipsoid. To address this, let x * t and x t represent the optimal arm and the chosen arm by the corrupted model, respectively. We decompose the single-round pseudo-regret R t = min{h(x * t ) -h(x t ), 1} into three components: (i) The prediction error of the corruption-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-NeuralUCB achieves non-trivial theoretical improvements: (i) removing the assumption of a known corruption level C in regret analysis; (ii) eliminating the dependency on the NTK norm term S for corruption-dependent terms in the regret bound; (iii) reducing the order of corruption-dependent terms in the regret bound to the effective dimension d, from O( d 3/2 ) to O( d), compared with our base algorithm NeuralUCB-WGD and existing kernelized bandit algorithms (e.g., [16] ).In addition, as mentioned in Remark 5.3, existing neural bandit approaches typically impose separateness assumptions on observed arm contexts, whereas we do not. For example, Neural-UCB [86] assumes H ≻ 0, which requires that no two arms are parallel among {x i,t } i∈[K],t∈ [T ] . In contrast, by formulating our NTK Gram matrices (Definitions 5.1 and 5.2), we complete our proof without the separateness assumption, reinforcing the theoretical robustness of our approach against possible arm contexts selected by an 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 T K observed arms, i.e., {x i,t } i∈ Upper bound for vanilla Neural-UCB. Meanwhile, to provide insights into the regret bound of Neural-UCB, one possible approach is to follow a 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 t as γt-1 , we obtain the corrupted confidence ellipsoid for Neural-UCB asC t-1 = θ : ∥θ -θ t-1 ∥ Γt-1 ≤ γ t-1 / √ m , where γ t-1 = γt-1 + O(CLλ -1/2). This result is derived by setting w τ = 1 for τ ∈ [t -1] and applying the fact that τ ∈[t] c τ ≤ C, along with Lemma G.2 and the initialization of the gradient covariance matrix Γ. Following the proof flow of Lemma 5.3 in [86] , we obtain a regret upper bound of Õ( d√T + S dT + CL dT /λ),which introduces an additional Õ( √ T ) to the corruption-dependent term.Over-parameterization. For most neural bandit works with experiments (e.g., [84, 86, 25, 9, 11] ), a 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 to train, more timeconsuming 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 ≥ O(poly(T )), to approximate any arbitrary reward mapping function h(•). Additionally, with over-parameterization, 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 a two-layer fully connected network for experiments while performing theoretical analysis under over-parameterized settings, as in most existing neural bandit works (e.g., [86, 84, 9, 11, 67] ).Recall that we have the NTK norm S defined as the upper bound of the weighted norm S ≥ ∥ h∥ H-1 , 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 [86, 50, 51, 84, 48] by considering that the reward mapping function h(•) in (1) 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∥ H ≥ S, and the RKHS norm ∥h∥ H will not grow along with the finite horizon T (Remark 4.8 in [86] ).Meanwhile, we also would like to mention that this is a common formulation, and nearly all the neural bandit works (e.g., [86, 50, 51, 84, 9, 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 kernelized contextual bandits works (e.g., [72, 28, 16] ), they inevitably involve the RKHS norm into the regret bound. For linear bandit works (e.g., [42] ), they will also need to include an assumed upper bound of the true parameter θ * norm in the Euclidean space, such that ∥θ * ∥ 2 is bounded by a constant. Meanwhile, since the NTK norm term S stays invariant across candidate arms x i,t ∈ X t , we can treat S as a constant in practice (e.g., setting S = 1), and control the exploration intensity by tuning the exploration parameter ν.Recall that when defining the sample weights w (τ ) i,t in (4), we use the minimum gradient norm in the numerator to scale weights across the current candidate arms X t , while introducing the scaling parameter α > 0 to provide additional control from the practitioner's perspective. Under the stochastic contextual bandit settings, the learner receives the candidate arm pool X t in each round t from the environment, having little control over the minimum gradient norm, as X t is only revealed at round t. To address this, we introduce a tunable parameter α to control the minimum value of w (τ ) i,t , aiming for a more stable learning process. Additionally, when deriving the regret bound for R-NeuralUCB (Theorem 5.6), we scale the α values to ensure that the minimum weight value is κ 2 . Without this scaling, such as by setting α = 1, an extra corruption-independent termO( β -1 T d log(1 + T K/λ))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 g τ , and (ii) the norm of the candidate arm ∥g(x i,t ; θ)/ √ m∥ Σ -1 . Here, we use the squared norm in the numerator to balance with the norm product in 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 a corruption-dependent term of O( d√ T β -1 C), rather than the current O( dβ -1 C).To be specific, for scaling the arm weight based on κ, we first recall that in round t ∈ [T ], we have arm weights w(τ ) i,t , τ ∈ [t -1], i ∈ [K]. We can also denote w (τ ) i,t = min 1, α • frac τ (x i,t ; X t , Σt-1 ) .Here, instead of deeming α as a fixed value across horizon T , we can consider α to be varying across different rounds, denoted by α t , t ∈ [T ]. With a shorthand for minimum fraction valuefrac min t = min i∈[K],τ ∈[t-1] frac τ (x i,t ; X t , Σt-1 ), we can set each α t = κ 2 /frac min t , κ ∈ (0, 1). As a result, we can consequently have min{w(τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 , ∀t ∈ [T ].Recall that in each round t ∈ {2, . . . , T }, we need to train different sets of arm-specific parametersθ i,t-1 , i ∈ [K] according to Algorithm 1, for each of the candidate arms x i,t ∈ X t , i ∈ [K].As we have mentioned in the main body, we can adopt the idea of warm-start GD [13] in practice. Here, instead of training each set of parameters θ i,t-1 from the randomly initialized θ 0 , we tune arm-specific parameters for each x i,t ∈ X t with a small number of samples from current received records P t-1 . With the formulated arm weights w (τ ) i,t in (4), we first recall the arm-specific loss function associated with arm x i,t asL i,t (P t-1 ; θ) = (xτ ,rτ )∈Pt-1 w (τ ) i,t 2 • f (x τ ; θ) -r τ 2 + mλ 2 • ∥θ -θ 0 ∥ 2 2 .The idea is that instead of starting from θ 0 , we can initiate the GD process from the existing network parameters θ t-2 from the previous round t -1, where θ t-2 = θ it-1,t-2 represents the parameters associated with the chosen arm x t-1 = x it-1,t-1 in round t -1. The pseudo-code for this arm-specific warm-start GD process is provided in Algorithm 2. As a result, in our experiments, to balance computational costs and model performance, we implement the following strategies: (1) Inspired by meta-learning approaches [32] , we apply warm-start gradient descent (GD) by adapting previously trained network parameters θ t-2 for each candidate arm, using a small number of training samples rather than starting from θ 0 with a large sample size; (2) Based on our formulation of the warm-start GD process, we sample a 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 a fixed number of training samples helps keep round-wise inference time relatively stable, avoiding a drastic increase with T . Figure 2 illustrates the parameter count and inference time across different hidden dimensions. As shown, inference time remains relatively stable due to the fixed number of adaptation samples used for warm-start GD.θ (0) i,t-1 ← θ t-2 . 5: for each training step j ∈ J do 6: θ (j) i,t-1 = θ (j-1) i,t-1 -η∇ θ L i,t ( P t-1 ; θ (j-1) i,t-1 ) 7: end for 8: θ i,t-1 ← θ ( J) i,t-1 . 9: Return arm-specific network parameters θ i,t-1 .Under linear bandit settings, there is a model-agnostic lower bound of corruption-dependent term Ω(Cd) with probability at 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., Ω(C(log(T )) d/2 ) for the SE kernel and Ω(C [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 a 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 h(•) for neural bandits. Since there are no existing works from neural bandits or NTK perspectives, it can lead to a different line of research work by proving these results. Therefore, we consider providing such a corruption-dependent regret lower bound as a challenging future direction.v d+v T v d+v ) for the v-Matérn kernelMeanwhile, when C = 0, we obtain a corruption-free regret of Õ( d√ T + S dT ). By settingC = Ω(R T /d), the regret bound becomes Õ ( d2 √ T + S d3/2 √ T ) • Cβ -1 d -1. We note that, following the proof flow of Theorem 4.12 in [42] and the learning problem defined in Assumption 2.1 of [42] , our effective dimension term d2 may depend on the horizon T and can grow with T [26] . Consequently, although the regret bound contains onlyT terms, the overall order of the regret bound could reach or exceed O(T ) due to the effective dimension d2 , as discussed in [26] . This behavior differs from that of linear bandits, where regret bounds generally depend on the horizon T and other T -independent terms, such as context dimension d and a fixed T -independent linear parameter norm ∥θ * ∥ 2 . Therefore, our Theorem 5.6 will not contradict Theorem 4.12 in [42] .To begin with, recall that we aim to minimize the pseudo-regret for T rounds, denoted byR(T ) = T t=1 R t = T t=1 h(x * t ) -h(x t )where the second equality is due to the definition of reward mapping h in (1). We denote f (•) as the bandit model we currently possess, which is trained with corrupted records P t-1 up to round t.Similarly, we can also suppose a corresponding imaginary corruption-free bandit model, which is trained with corruption-free records P t-1 . Similarly, the model parameters of our possessed f (•) are denoted as θ, while the parameters of the imaginary corruption-free model will be denoted as θ.Subsections outline and proof sketch. The content in this section is organized into the following sub-components: In Subsection C. 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 1). Lemma C.1. With probability at least 1 -δ, if network width m satisfies the condition in Theorem 5.6, for any x ∈ A T , there exists a set of parameters θ * such thath(x) = ⟨g(x; θ 0 ), θ * -θ 0 ⟩ (C.1)where parameters θ * satisfy ∥θ * -θ 0 ∥ ≤ S/ √ m, along with the NTK norm S ≥ 2 h⊺ H-1 h.Proof. 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 ȂT and the corresponding NTK Gram matrix H (Def. 5.2), instead of imposing the full-rank assumption on the conventional NTK matrix H (Def. 5.1). Here, we recall that the matrix H is naturally positive definite ( λ0 = λ min ( H) > 0), as it is the NTK Gram matrix built upon a set of distinct arms that are not parallel (Fact 5.4).Then, consider the gradient matrix with no-duplicate arms G = [g(x;θ 0 )] x∈ ȂT / √ m ∈ R p×| ȂT |, where p represents the total number of parameters in the neural network. As a result, by applying conclusion from Lemma C.3 and due to the fact that | ȂT | ≤ 3T , with the network width m ≥ Ω(L 6 log(T L/δ)/ϵ), ∀ϵ > 0 and the probability at least 1 -δ, we will have∥ G⊺ G -H∥ F ≤ | ȂT | • ϵ. By setting ϵ = λ0 2| ȂT | , we will have G⊺ G ⪰ H -∥ G⊺ G -H∥ F I ⪰ H -λ0 /2I ⪰ H/2 ≻ 0.where the last two inequalities are due to Fact 5.4 that H ⪰ λ0 I ≻ 0. Analogous to Lemma 5.1 in [86] , we consider the singular value decomposition of G being G = P Ȃ Q⊺ , where we naturally have Ȃ ≻ 0 since H is positive definite. Then, with the expected reward vector h (Def. 5.2), we haveh = ( Q Ȃ P⊺ ) • ( P Ȃ-1 Q⊺ ) • h = √ m • G⊺ (θ * -θ 0 ),by considering there exists a set of parametersθ * = θ 0 + ( P Ȃ-1 Q⊺ ) • h/ √ m. Therefore, since h = √ m • G⊺ (θ * -θ 0 ), we will have ∀x ∈ ȂT , h(x) = ⟨g(x; θ 0 ), θ * -θ 0 ⟩.Meanwhile, since G⊺ G ⪰ H/2, by applying Lemma G.8, we will have the distancem • ∥θ * -θ 0 ∥ 2 2 = h ⊺ Q Ȃ-1 P⊺ • P Ȃ-1 Q⊺ h = h ⊺ ( G⊺ G) -1 h ≤ 2h ⊺ H-1 h.Finally, since the above results holds ∀x ∈ ȂT , due to the fact that ȂT contains all the unique arms of the collection A T , we will directly have the above results regarding parameters θ * feasible ∀x ∈ A T . This completes the proof.Lemma C.2. Suppose m satisfies the conditions in Theorem 5.6. Suppose the gradient matrix with randomly initialized parameters isΣ (0) = λI + x∈A g(x; θ 0 ) • g(x; θ 0 ) ⊺ /m, upon an arbitrary subset A ⊆ A T of arm collection A T . With probability at least 1 -δ over the initialization, the result holds:log det Σ (0) det λI ≤ d log(1 + T K/λ) + 1.Proof. First, recall that we have A T as the arm collection of: (i) the chosen arms {x t } T t=1 ; (ii) the optimal arms {x * t } T t=1 ; (iii) and the imaginary ones { x t } T t=1 chosen by the corruption-free model. This makes its cardinality |A T | = 3T . Thus, for the left hand side, we havelog det(Σ (0) ) det(λI) ≤ log det(λI + x∈A T g(x; θ 0 )g(x; θ 0 ) ⊺ /m) = det(λI + G 0 G ⊺ 0 ),where we define gradient matrixG 0 = g(x; θ 0 )/ √ m x∈A T ∈ R p×(3T ) based on arm collection A T .Here, based on Lemma C.3, we can bound the distance between the Gradient matrix product G ⊺ 0 G 0 and the NTK matrix H (Def. 5.1), as∥G ⊺ 0 G 0 -H∥ ≤ 3T • 1 3T • O( √ T /λ) = 1 O( √ T /λ) , by setting ϵ = 1 3T •O( √ T /λ) .The above results will hold, as long as we have the network width m ≥ Ω((T L) 6 log(T L/δ)/λ 4 ), matching the conditions in Theorem 5.6. As a result, we can havelog det(I + G ⊺ 0 G 0 /λ) = log det(I + H/λ + (G ⊺ 0 G 0 -H)/λ) ≤ log det(I + H/λ) + ⟨(I + H/λ) -1 , (G ⊺ 0 G 0 -H)/λ⟩ ≤ log det(I + H/λ) + ∥(I + H/λ) -1 ∥ F ∥G ⊺ 0 G 0 -H∥ F /λ ≤ log det(I + H/λ) + O( √ T /λ) • ∥G ⊺ 0 G 0 -H∥ F ≤ log det(I + H/λ) + 1 = d log(1 + T K/λ) + 1.The first inequality is because the concavity of log det(•) function; The third inequality is due to∥(I + Hλ) -1 ∥ F ≤ ∥I -1 ∥ F ≤ √ T ;The fourth inequality is by applying the above distance upper bound∥G ⊺ 0 G 0 -H∥ ≤ 1 O( √ T /λ) .The last inequality is because of the choice the m; The last equality is because of the Definition of d. The proof is completed.Lemma C.3. With the randomly initialized network parameters θ 0 ∈ R p and a collection of arms A ⊂ R d , define the gradient matrix G A = [g(x; θ 0 )] x∈A ∈ R p×|A| . Following the recursive procedure in Def. 5.1 (7) , construct the NTK Gram matrix H A based on arms A. Then, with the probability at least 1 -δ, we will have∥G ⊺ A G A -H A ∥ F ≤ |A| • ϵ, with the network width m ≥ Ω(L 6 log(|A|L/δ)/ϵ 4 ).Proof. The proof of this lemma is analogous to the proof of Lemma B.1 in [86] . Based on Theorem 3.1 from [4] , we have that for any two arms x, x ′ ∈ A, as the network width m ≥ Ω(L 6 log(L/δ)/ϵ 4 ), we will have |⟨g(x; θ 0 ), g(x ′ ; θ 0 )⟩/m -H A [x, x ′ ]| ≤ ϵ, where H A [x,x ′ ] represents the element in NTK Gram matrix H A that corresponds to arms x and x ′ .Next, taking the union bound over all the arms in A, we will have∥G ⊺ A G A -H A ∥ F = x∈A x ′ ∈A |⟨g(x; θ 0 ), g(x ′ ; θ 0 )⟩/m -H A [x, x ′ ]| 2 ≤ |A| • ϵ,as long as the network width m ≥ Ω(L 6 log(|A|L/δ)/ϵ 4 ).With the above results linking the NTK to the neural model, we proceed to bound the single-round regret R t for t ∈ [T ]. This single-round regret will then be aggregated to obtain the cumulative regretR(T ) = t∈[T ] R t .Based on Lemma C.1, we have the expected reward of an arm x ∈ X t beingE[r|x] = h(x) = ⟨g(x; θ 0 ), θ * -θ 0 ⟩ where there exist parameters θ * such that ∥θ * -θ 0 ∥ ≤ S/ √ m.Meanwhile, apart from the trained parameters θ t-1 based on chosen arms as well as the corresponding received rewards {x τ , r τ } τ ∈[t-1] , we also denote the imaginary corruption-free parameters θ t-1 , which is trained with the chosen arms along with their unknown corruption-free rewards {x τ , r τ } τ ∈[t-1] , for the sake of analysis.To bound the single-round regret R t , we first decompose the objective into several individual terms, and then bound them individually. For reference, the parameters θ t-1 , covariance matrix Σ t-1 , confidence ellipsoid C t-1 , and weights w t pertain to the chosen arm x t , with the arm index i ∈ [K] omitted for simplicity of notation.Arm selection scores. First, recall that based on the arm pulling mechanism (line 13, Algorithm 1) and the benefit score (6) (Lemma C.11), the chosen arm x t ∈ X t is selected byx t = arg max xi,t∈Xt f (x i,t ; θ i,t-1 ) + γ i,t-1 • g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 )/m = arg max xi,t∈Xt U (x i,t ),where we denote the corresponding score shorthand asU (x i,t ) = f (x i,t ; θ i,t-1 ) + γ i,t-1 • g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 ). (C.2)Analogously, with θ i,t-1 being the parameters trained on same set of chosen arms and the corresponding corruption-free rewards, we denoteU (x i,t ) = f (x i,t ; θ i,t-1 ) + γ i,t-1 • g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 ), (C.3) with corresponding covariance matrix Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1) ⊺ /m, and the coefficient γ i,t-1 based on Σ i,t-1 following the definition from (6) . It is obvious that the arm selection depends on the trained network parameters, and thus if the corruption makes the makes the trained network parameters θ i,t-1 deviate from the corruption-free ones θ i,t-1 , 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 (C.1) in Lemma C.1, we can consider an alternative form of arm selection beingV (x i,t ) = g(x i,t ; θ 0 ), θ i,t-1 -θ 0 + γ i,t-1 • g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 )/m = max θ∈Ci,t-1 g(x i,t ; θ 0 ), θ -θ 0 (C.4)where we have C i,t-1 := {θ : ∥θ -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 / √ m, γ i,t-1 > 0} being the confidence ellipsoid of for the actual trained parameters θ i,t-1 , trained with possibly corrupted records. γ i,t-1 > 0 represents the radius of the confidence ellipsoid; and the last equality in (C.4) is due to maxx:∥x-b∥ A ≤c ⟨a, x⟩ = ⟨a, b⟩ + c • √ a ⊺ A -1 a [86]. Analogously, for the corruption-free parameters θ i,t-1 , we also define its confidence ellipsoid C i,t-1 := {θ : ∥θ -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 / √ m, γ i,t-1 > 0}, with γ i,t-1 > 0 being the radius of the confidence ellipsoid, and by Lemma C.10, we will have θ * ∈ C i,t-1 . As a result, we can also formulate an alternative form for arm selection asV (x i,t ) = g(x i,t ; θ 0 ), θ i,t-1 -θ 0 + γ i,t-1 • g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 )/m = max θ∈ Ci,t-1 g(x i,t ; θ 0 ), θ -θ 0 . (C.5)Here, the radius of the confidence ellipsoid for the corruption-free parameters γ i,t-1 , is provided in Lemma C.10, ensuring that θ * ∈ C i,t-1 . On the other hand, deriving the radius for the trained model, γ i,t-1 in face of potential corruptions, is considerably more challenging. With our carefully designed arm weights in (4), we manage to establish the updated confidence ellipsoid in Lemma C.12, along with the corresponding UCB for reward estimation (Lemma C.11).Note that our UCB-based exploration score ( 6) is also motivated by Lemma C.11. For a specific arm x i,t ∈ X t , our UCB-type exploration score includes only terms related to x i,t , omitting constant and arm-invariant parts. This approach is intuitive, as arm-independent terms do not influence arm selection (line 13, Algorithm 1), and they will remain the same across candidate arms X t . Moreover, with a sufficiently large network width m as in Theorem 5.6, a majority of these terms can be further reduced to O(1).Decomposing the single-round objective. Up to the time step t ∈ [T ], denoting x t , x * t ∈ X t being the chosen arm and the optimal arm in each round respectively, we will have the corresponding regret bound for step t as:R t = min h(x * t ) -h(x t ), 1 = min h(x * t ) -V (x t ) + V (x t ) -h(x t ) UCBt(xt) , 1 = min UCB t (x t ) + h(x * t ) -V (x t ) I R 1 + V (x t ) -V (x t ) I R 2 , 1 (C.6)where the first equality is because we have the expected rewards in bounded value range [0, 1]. Here, with the three terms after decomposing the single-round regret R t , we can bound the first term UCB t (x t ) with Lemma C.9, while bounding the two error terms I R1 and I R2 with Lemma C.6 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 E[r] and the expected corruption-free reward E[ r] fall within the range [0, 1], as defined in (1), it follows that C ≤ T . In this case, as long as the network width requirement m ≥ Ω(poly(T )) in Theorem 5.6 is adequately satisfied, this naturally implies m ≥ Ω(poly(C, T )) 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 , t ∈ [T ], we can then proceed to bound the cumulative regret over T rounds. By definition in (C.6), we haveR(T ) = T t=1 min UCB t (x t ) + h(x * t ) -V (x t ) I R 1 + V (x t ) -V (x t ) I R 2 , 1 .Recall that the first term UCB t (x t ) can be bounded with Lemma C.9, while we bound the other two error terms I R1 and I R2 with Lemma C.6 and Lemma C.4 respectively. Next, with the conclusions from above lemmas, we will haveR(T ) = T t=1 min UCB t (x t ) + h(x * t ) -V (x t ) I R 1 + V (x t ) -V (x t ) I R 2 , 1 ≤ T t=1 min 2 γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) • g( x t ; θ ĩt,t-1 )/ √ m (Σ ′ t-1 ) -1 + O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O √ λS • g(x t ; θ t-1 )/ √ m ( Σt-1) -1 + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(m -1/6 log(m)t 1/6 λ -7/6 L 2/7 ) + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 3 t 5/6 λ -7/12 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) + O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ) + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)), 1where "weight-free" covariance matrices are Σt-EQUATIONΣ ′ t-1 = λI + τ ∈[t-1] g( x τ ; θ ĩτ ,τ -1 )g( x τ ; θ ĩτ ,τ -1 ) ⊺ /m.Afterwards, with sufficient network width m that satisfies the conditions in Theorem 5.6, the majority of the terms on the RHS of (C.7), which contain m to the negative order, can be reduced to O(1). Thus, we will then haveR(T ) ≤ O(1) + T t=1 min 2 γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) g( x t ; θ ĩt,t-1 )/ √ m (Σ ′ t-1 ) -1 + O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O √ λS • g(x t ; θ t-1 )/ √ m ( Σt-1) -1 , 1 ≤ O(1) + T t=1 min 2 γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 1 + O(αC) • T t=1 min g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 , 1 + O( √ λS) T T t=1 min g( x t ; θ ĩt,t-1 )/ √ m 2 (Σ ′ t-1 ) -1 , 1 + O √ λS • T T t=1 min g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 , 1 (C.7)where the second inequality is by applying the triangular inequality. Then, denote w min = min[{w(τ ) t , w (τ ) ĩt,t } t∈[T ],τ ∈[t-1]]. Analogously, we also have the round-wise minimum weight value beingw min t = min{w (τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 < 1, ∀t ∈ [T ], which will be used to determine our scaling parameter α. With our notation from Theorem 5.6, this intuitively leads to α ≤ κ 2 β . As a result, we can therefore haveEQUATION+ O Cβ -1 κ 2 • d log(1 + T K/λ) + O √ λS • T d log(1 + T K/λ) (C.8)where the first inequality is because the auxiliary matrices Σ(0) t-1 and Σ ′ t-1 do not involve arm weights, thus we can directly applying the Lemma G.7 and Lemma G.6. The second inequality is by applying Lemma C.2. Meanwhile, since Σ ′ t-1 is not defined w.r.t. randomly initialized θ 0 , 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 O(1) with sufficiently large m. Afterwards, for the rest of the summation terms in (C.8), we can haveR(T ) ≤ O( γ T √ w min ) T T t=1 min ∥ √ w min g(x t ; θ t-1 )/ √ m∥ 2 Σ -1 t-1 , 1 + O( γ T √ w min ) T T t=1 min ∥ √ w min g(x t ; θ t-1 )/ √ m∥ 2 Σ -1 t-1 , 1 + O Cβ -1 κ 2 • d log(1 + T K/λ) + O √ λS • T d log(1 + T K/λ) + O(1) ≤ 1 √ w min O ν log det( Σ T ) det(λI) -2 log(δ) + λ 1/2 S + ν log det(Σ T ) det(λI) -2 log(δ) + λ 1/2 S • T d log(1 + T K/λ) + O Cβ -1 κ 2 • d log(1 + T K/λ) + O √ λS • T d log(1 + T K/λ) + O(1) ≤ 1 √ w min O λ 1/2 S + ν log det( Σ (0) T ) det(λI) + O(m -1/6 log(m)L 4 T 5/3 λ -1/6 ) -2 log(δ) + ν log det(Σ (0) T ) det(λI) + O(m -1/6 log(m)L 4 T 5/3 λ -1/6 ) -2 log(δ) T d log(1 + T K/λ) + O Cβ -1 κ 2 • d log(1 + T K/λ) + O √ λS • T d log(1 + T K/λ) + O(1), (C.9)where the second inequality is by applying Lemma G.7 and Lemma C.2, as well as the definition of coefficients γ T , γ T , along with the fact that γ T ≥ γ t , γ T ≥ γ t , 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 O(m -1/6 log(m)L 4 T 5/3 λ -1/6 ) ≤ O (1) . Then, due to the fact thatEQUATIONT , applying the Lemma C.2, it will then lead toR(T ) ≤ 1 √ w min O ν d log(1 + T K/λ) -2 log(δ) + λ 1/2 S T d log(1 + T K/λ) + O Cβ -1 κ 2 • d log(1 + T K/λ) + O(1) ≤ O ν d log(1 + T K/λ) -2 log(δ) + λ 1/2 S T d log(1 + T K/λ)/κ 2 + O Cβ -1 dκ 2 log(1 + T K/λ) (C.10)where the second inequality is by setting the tunable parameter α in each round accordingly, in order to ensure w min = κ 2 < 1. Here, we remind that our regret analysis does not require the learner to know the minimum fraction value β before the online learning process, whereβ = min t∈[T ],τ ∈[t-1] min{frac τ (x t ; X t , Σt-1 ), frac τ ( x t ; X t , Σt-1 )} . As we have mentioned, in practice, the learner can scale the α values in each round to make sure the round-wise minimum weight valuew min t = min{w (τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 < 1, ∀t ∈ [T ] (Subsec. B.5).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-based ridge regression parameters specific to a candidate arm x i,t ∈ X t in round t ∈ [T ], asΣ (0) i,t-1 = λI + τ ∈[t-1] w (τ ) i,t g(x τ ; θ 0 ) • g(x τ ; θ 0 ) ⊺ /m, Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t g(x τ ; θ τ -1 ) • g(x τ ; θ τ -1 ) ⊺ /m, Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t g(x τ ; θ τ -1 ) • g(x τ ; θ τ -1 ) ⊺ /m, b (0) i,t-1 = τ ∈[t-1] w (τ ) i,t g(x τ ; θ 0 ) • r τ / √ m, b i,t-1 = τ ∈[t-1] w (τ ) i,t g(x τ ; θ τ -1 ) • r τ / √ m, b (0) i,t-1 = τ ∈[t-1] w (τ ) t g(x τ ; θ 0 ) • r τ / √ m, b i,t-1 = τ ∈[t-1] w (τ ) i,t g(x τ ; θ τ -1 ) • r τ / √ m, (C.11)where {x τ , r τ }, τ ∈ [t] respectively stand for the chosen arms as well as their rewards, while {x τ , r τ }, τ ∈ [t] refer to chosen arms and their imaginary corruption-free rewards. For notation simplicity, we use w(τ ) t , τ ∈ [t -1]to denote the arm weights for x t .Meanwhile, given an candidate arm x i,t ∈ X t with arm weight w (τ ) i,t defined in (4), we can try to bound the I 2 term by decomposing the adversarial corruptions with a series auxiliary gradient sequences {θ 0 , Θ (1) , . . . , Θ (J) } as in Lemma D.1, such that for j-th iterationΘ (j+1) = Θ (j) -η • J (0) • W • [J (0) ] ⊺ (Θ (j) -θ 0 ) -y + mλ(Θ (j) -θ 0 )as well as an analogous sequence for corruption-free parametersΘ (j+1) = Θ (j) -η • J (0) • W • [J (0) ] ⊺ ( Θ (j) -θ 0 ) -y + mλ( Θ (j) -θ 0 )where J (0) := g(x 1 ; θ 0 ), g(x 2 ; θ 0 ), . . . , g(x t-1 ; θ 0 ) ∈ R p×(t-1) , and W refers to the diagonal matrix of arm weights {w(τ ) i,t } τ ∈[t-1], along with the reward vectors y, y ∈ R t-1 separately being the vector of received rewards and corruption-free rewards. In particular, with [J (0) ] τ being the τ -th column of matrix J (0) , the auxiliary sequence Θ (j) can be deemed as applying Gradient Descent to solve the following optimization problemmin Θ L(Θ) = τ ∈[t-1] 1 2 • w (τ ) i,t • [J (0) ] ⊺ τ (Θ -θ 0 ) -y τ 2 2 + 1 2 • mλ • Θ -θ 0 2 2 (C.12)Analogously, we can also derive the optimization problem for the sequence of corruption-free auxiliary parameters Θ (j), by applying the same definition of weight matrix W. Since the arm weights w ≤ 1 by definition, we will also have the diagonal matrix norm ∥W∥ 2 ≤ 1.Notation simplicity. For reference, we remind that the parameters θ t-1 , covariance matrix Σ t-1 , confidence ellipsoid C t-1 , and weights w t pertain to the chosen arm x t , with the arm index i ∈ [K] omitted for simplicity of notation. Meanwhile, the gradinet covariance matrix Σ i,t-1 , confidence ellipsoid C i,t-1 , and weights w i,t are associated with each candidate arm x i,t for i ∈ [K].I R2 in (C.6)Recall that to derive the upper bound for the single-round regret R t , we need to respectively bound the three error terms on the RHS of (C.6). Here, we first bound term I R2 with the following Lemma C.4. Lemma C.4. Suppose the imaginary neural network f (•; θ t-1 ) in round t ∈ [T ] has been trained on corruption-free rewards {x τ , r τ } τ ∈[t-1] . Meanwhile, f (•) is an L-layer FC network with width m. Suppose we have m, J, η satisfying the conditions in Theorem 5.6. Then, for the chosen arm x t ∈ X t , with the probability at least 1 -δ, we will haveI R2 =V (x t ) -V (x t ) ≤ γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(m -1/6 log(m)t 1/6 λ -7/6 L 2/7 ) + O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) g(x t ; θ t-1 )/ √ m ( Σt-1) -1+ O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 )+ O(m -1/6 log(m)t 2/3 λ -2/3 L 7/2 ).By definition, we have γ t-1 = O ν log det(Σt-1) det(λI) -2 log(δ) + λ 1/2 S , as well as the gradient covariance matrix Σt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m. The minimum round-wise arm weightw min t = min{w (τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 < 1, ∀t ∈ [T ] by scaling parameter α.Proof. For the error term I R2 , we haveI R2 = V (x t ) -V (x t ) = max θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ 0 ⟩ -max θ∈ Ct-1 ⟨g(x t ; θ 0 ), θ -θ 0 ⟩ ≤ max θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ 0 ⟩ -⟨g(x t ; θ 0 ), θ t-1 -θ 0 ⟩ ≤ max θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ 0 ⟩ -⟨g(x t ; θ t-1 ), θ t-1 -θ 0 ⟩ + O(m -1/6 log(m)t 2/3 λ -2/3 L 7/2 ) = max θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ t-1 ⟩ -⟨g(x t ; θ t-1 ), θ t-1 -θ t-1 ⟩ + O(m -1/6 log(m)t 2/3 λ -2/3 L 7/2 ) = max θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ t-1 ⟩ Projection difference +| ⟨g(x t ; θ t-1 ), θ t-1 -θ t-1 ⟩ I2 | + O(m -1/6 log(m)t 2/3 λ -2/3 L 7/2 ) (C.13)where the first inequality is because of the definition of confidence ellipsoids C t-1 and C t-1 . The second inequality is by applying Lemma G.3 and Lemma G.4. Here, we have the first term on the RHS is bounded by Corollary C.5, where this term is used to represent the gradient projection difference, between the confidence ellipsoid center parameters θ t-1 and the other parameters in this confidence ellipsoid θ ∈ C t-1 . Meanwhile, term I 2 will be bounded by Corollary C.8.Corollary C.5. Suppose the imaginary neural network f (•; θ t-1 ) in round t ∈ [T ] has been trained on corruption-free rewards {x τ , r τ } τ ∈[t-1] . Meanwhile, f (•) is an L-layer FC network with width m. Suppose we have m, J, η satisfying the conditions in Theorem 5.6. Then, for the chosen arm x t ∈ X t , with the probability at least 1 -δ, we will havemax θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ t-1 ⟩ ≤ γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(m -1/6 log(m)t 1/6 λ -7/6 L 2/7 ),and the corresponding summation value beingEQUATIONw min t O ν log det(Σ T ) det(λI) -2 log(δ) + λ 1/2 S • 2T • log det(Σ T ) det(λI) . + O(Sm -1/6 log(m)T 7/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)T 7/6 λ -7/6 L 2/7 ).By definition, we have the radius of C t-1 being γ t-1 = O ν • log det(Σt-1) det(λI) -2 log(δ) + λ 1/2 S , and the gradient covariance matrixΣ t-1 = λI + τ ∈[t-1] w (τ ) t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m.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 x t in round t asmax θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ t-1 ⟩ ≤ max θ∈Ct-1 ∥θ -θ t-1 ∥ Σt-1 • ∥g(x t ; θ 0 )∥ Σ -1 t-1 ≤ γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(m -1/6 log(m)t 1/6 λ -7/6 L 2/7 ) (C.14)where the first inequality is due to Holder's inequality. The second inequality is by applying the definition of confidence ellipsoid C t-1 , as 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 havet∈[T ] min{ max θ∈Ct-1 ⟨g(x t ; θ 0 ), θ -θ t-1 ⟩, 1} ≤ 1 w min t O ν log det(Σ T ) det(λI) -2 log(δ) + λ 1/2 S • 2T • log det(Σ T ) det(λI) . + O(Sm -1/6 log(m)T 7/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)T 7/6 λ -7/6 L 2/7 ).By the definition Suppose we have m, J, η satisfying the conditions in Theorem 5.6. Then, for the chosen arm x t ∈ X t , with the probability at least 1 -δ, we will haveβ = min t∈[T ],τ ∈[t-1] [min{frac τ (x t ; X t , Σt-1 ), frac τ ( x t ; X t , Σt-1 )}],I R1 = h(x * t ) -V (x t ) ≤ O(αC) g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) • g( x t ; θ ĩt,t-1 )/ √ m (Σ ′ t-1 ) -1+ O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 )+ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 3 t 5/6 λ -7/12 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) + O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ ĩt,t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ).By definition, we have the coefficientγ ĩt,t-1 = O ν log det(Σĩ t ,t-1 ) det(λI)-2 log(δ) + λ 1/2 S , as well as the gradient covariance matricesΣ ′ t-1 = λI + τ ∈[t-1] g( x τ ; θ ĩτ ,τ -1 )g( x τ ; θ ĩτ ,τ -1 ) ⊺ /m, and Σt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1) ⊺ /m. The minimum round-wise arm weightw min t = min{w (τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 < 1, ∀t ∈ [T ] by scaling parameter α.Proof. By definition, we can haveI R1 = h(x * t ) -U (x t ) + U (x t ) -V (x t ).Here, in terms of the distance between U (x i,t ) and V (x i,t ) given a candidate arm x i,t ∈ X t , we have|U (x i,t ) -V (x i,t )| = |f (x i,t ; θ i,t-1 ) -g(x i,t ; θ 0 ), θ i,t-1 -θ 0 | ≤ |f (x i,t ; θ i,t-1 ) -g(x i,t ; θ i,t-1 ), θ i,t-1 -θ 0 | + | g(x i,t ; θ i,t-1 ), θ i,t-1 -θ 0 -g(x i,t ; θ 0 ), θ i,t-1 -θ 0 | ≤ O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ).where the first inequality is by triangular inequality, and the second inequality is by applying a similar approach as in (B.12) from [86] as well as Lemma G.4. Next, we proceed to bound term I R1 . Here, for a candidate arm x i,t ∈ X t and the associated corruption-free confidence ellipsoid C i,t-1 , we have θ * ∈ C i,t-1 based on Lemma C.10. Thus, with x t = arg max xi,t∈Xt V (x i,t ) being the arm chosen by the corruption-free neural model, with the highest score V ( x t ), there will beI R1 = h(x * t ) -U (x t ) + U (x t ) -V (x t ) = ⟨g(x * t ; θ 0 ), θ * -θ 0 ⟩ -U (x t ) + U (x t ) -V (x t ) ≤ max θ∈ Cĩ t ,t-1 ⟨g(x * t ; θ 0 ), θ -θ 0 ⟩ -U (x t ) + U (x t ) -V (x t ) ≤ max θ∈ Cĩ t ,t-1 ⟨g( x t ; θ 0 ), θ -θ 0 ⟩ -U (x t ) + |U (x t ) -V (x t )|,where C ĩt,t-1 refers to the confidence ellipsoid of corruption-free parameters θ ĩt,t-1 , associated to arm x t ∈ X t . Afterwards, it further leads toI R1 ≤ max θ∈ Cĩ t ,t-1 ⟨g( x t ; θ 0 ), θ -θ 0 ⟩ -U (x t ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) ≤ max θ∈ Cĩ t ,t-1 ⟨g( x t ; θ 0 ), θ -θ 0 ⟩ -V (x t ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) ≤ max θ∈ Cĩ t ,t-1 ⟨g( x t ; θ 0 ), θ -θ 0 ⟩ -V ( x t ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) = V ( x t ) -V ( x t ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 )To bound the output difference between V (x i,t ) and V (x i,t ) for an arm x i,t , we can decompose them into separate terms. Recall the definition of V (•) in (C.4), and we can also define the analogous V (•) by applying the corruption-free parameters θ and covariance matrix Σ. Therefore, for arm x i,t ∈ X t , we haveV (x i,t ) -V (x i,t ) ≤ |V (x i,t ) -V (0) (x i,t )| + |V (0) (x i,t ) -V (0) (x i,t )| + | V (0) (x i,t ) -V (x i,t )|, (C.15)where for the sake of analysis, we define two variants with randomly initialized parameters θ 0 being:EQUATIONt-1 ) -1 g(x i,t ; θ 0 )/m, andV (0) (x i,t ) = g(x i,t ; θ 0 ), θ t-1 -θ 0 + γ t-1 • g(x i,t ; θ 0 ) ⊺ (Σ (0)t-1 ) -1 g(x i,t ; θ 0 )/m. With this result, our objective then is to derive the upper bounds for the three terms on the RHS of (C.15). 15) . For the second term, we have|V (0) (x i,t ) -V (0) (x i,t )| in (C.|V (0) (x i,t ) -V (0) (x i,t )| ≤ | g(x i,t ; θ 0 ), θ i,t-1 -θ i,t-1 | + |γ i,t-1 • g(x i,t ; θ 0 ) ⊺ (Σ (0) i,t-1 ) -1 g(x i,t ; θ 0 )/m -γ i,t-1 • g(x i,t ; θ 0 ) ⊺ (Σ (0) i,t-1 ) -1 g(x i,t ; θ 0 )/m| = | g(x i,t ; θ 0 ), θ i,t-1 -θ i,t-1 | + |γ i,t-1 -γ i,t-1 | • g(x i,t ; θ 0 ) ⊺ (Σ (0) i,t-1 ) -1 g(x i,t ; θ 0 )/m ≤ | g(x i,t ; θ 0 ), θ i,t-1 -θ i,t-1 | + |γ i,t-1 -γ i,t-1 | • O(L/ √ λ).Due to the fact that | √ a -√ b| ≤ |a -b|, based on the definition of γ i,t-1 and γ i,t-1 , we will have|γ i,t-1 -γ i,t-1 | ≤ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • log( det Σ i,t-1 det λI ) -log( det Σ 0 det λI ) + log( det Σ 0 det λI ) -log( det Σ i,t-1 det λI ) ≤ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 2 t 5/6 λ -1/12 ),based on Lemma G.6. Therefore, we will end up with|V (0) (x i,t ) -V (0) (x i,t )| ≤ | g(x i,t ; θ 0 ), θ i,t-1 -θ i,t-1 | + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 3 t 5/6 λ -7/12 ). Bounding Term |V (x i,t ) -V (0) (x i,t )| and term | V (0) (x i,t ) -V (x i,t )| in (C.15). On the other hand, for the first term on the RHS, |V (x i,t ) -V (0) (x i,t )|, we can bound this difference term byV (x i,t ) -V (0) (x i,t ) = γ i,t-1 √ m g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 ) -g(x i,t ; θ 0 ) ⊺ (Σ (0) i,t-1 ) -1 g(x i,t ; θ 0 ) = γ i,t-1 √ m g(x i,t ; θ i,t-1 ) Σ -1 i,t-1 -g(x i,t ; θ 0 ) (Σ (0) i,t-1 ) -1 ≤ γ i,t-1 √ m g(x i,t ; θ i,t-1 ) Σ -1 i,t-1 -g(x i,t ; θ i,t-1 ) (Σ (0) i,t-1 ) -1 + g(x i,t ; θ 0 ) -g(x i,t ; θ i,t-1 ) (Σ (0) i,t-1 ) -1 ≤ O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ i,t-1 √ m • g(x i,t ; θ i,t-1 ) Σ -1 i,t-1 -g(x i,t ; θ i,t-1 ) (Σ (0) i,t-1 ) -1 ≤ O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ i,t-1 √ m • g(x i,t ; θ i,t-1 ) ⊺ Σ -1 i,t-1 g(x i,t ; θ i,t-1 ) -g(x i,t ; θ i,t-1 ) ⊺ (Σ (0) i,t-1 ) -1 g(x i,t ; θ i,t-1 ) ≤ O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ i,t-1 √ m • ⟨g(x i,t ; θ i,t-1 ), (Σ -1 i,t-1 -(Σ (0) i,t-1 ) -1 )g(x i,t ; θ i,t-1 )⟩ = O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ i,t-1 √ m • g(x i,t ; θ i,t-1 ), Σ -1 i,t-1 • (Σ (0) i,t-1 -Σ i,t-1 ) • (Σ (0) i,t-1 ) -1 • g(x i,t ; θ i,t-1 )≤ O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ i,t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ) 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 | V (0) (x i,t ) -V (x i,t )|, after summing up the results, we will have|V (x i,t ) -V (0) (x i,t )|, | V (0) (x i,t ) -V (x i,t )| ≤ O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) + O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ i,t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ).Summing up results. Combining the results, we finally have the upper bound for I R1 beingI R1 ≤ | g( x t ; θ 0 ), θ ĩt,t-1 -θ ĩt,t-1 | + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 3 t 5/6 λ -7/12 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) + O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ ĩt,t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ) ≤ | g( x t ; θ ĩt,t-1 ), θ ĩt,t-1 -θ ĩt,t-1 | + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 3 t 5/6 λ -7/12 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 )+ O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) + O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ ĩt,t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ), and therefore we can formulate our objective to bound asI R1 ≤ | g( x t ; θ ĩt,t-1 ), θ ĩt,t-1 -θ ĩt,t-1 I1 | + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 3 t 5/6 λ -7/12 ) + O(m -1/6 t 2/3 λ -2/3 log(m)L 7/2 ) + O(m -1/6 t 1/6 λ -7/6 log(m)L 7/2 ) + γ ĩt,t-1 • O(m -1/12 t 7/12 λ -13/12 log 1/4 (m)L t/2 ), (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 1 from Lemma C.7 will finish the proof.C.7 Bounding the terms I 1 , I 2Here, we see that there are still two terms in R t , t ∈ [T ] that need to be bounded, which areI 1 = g( x t ; θ ĩt,t-1 ), θ ĩt,t-1 -θ ĩt,t-1 , I 2 = ⟨g(x t ; θ t-1 ), θ t-1 -θ t-1 ⟩,where we recall x t ∈ X t is the actual chosen arm that is selected by the corrupted model θ t-1 , while we have x t ∈ X t being the imaginary arm chosen by the corruption-free model θ t-1 . In this subsection, the error term I 1 will be bounded by Lemma C.7, while term I 2 will be bounded by Corollary C.8.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 a series of gradient-based regression parameters, specified to candidate arm x i,t ∈ X t , asΣ (0) i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • g(x τ ; θ 0 ) ⊺ /m, Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • g(x τ ; θ τ -1 ) ⊺ /m, b (0) i,t-1 = τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • r τ / √ m, b i,t-1 = τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • r τ / √ m, b (0) i,t-1 = τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • r τ / √ m, b i,t-1 = τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • r τ / √ m,where {x τ , r τ }, τ ∈ [t] respectively stands for the chosen arms as well as their received rewards, while {x τ , r τ }, τ ∈ [t] refer to the imaginary corruption-free rewards.We also recall that with the chosen arm x t ∈ X t in round t with arm weights w(τ ) t , τ ∈ [t-1], defined in (4), we will have a series of auxiliary gradient sequences {θ 0 , Θ (1) , . . . , Θ (J) } as in Lemma D.1, such that for j-th, j ∈ [J], iterationΘ (j+1) = Θ (j) -η • J (0) • W [J (0) ] ⊺ (Θ (j) -θ 0 ) -y + mλ(Θ (j) -θ 0 )where the diagonal weight matrix is made up with the arm weights, as 1) . Similarly, we will also have the sequence definition for corruption-free parametersW = diag [w (τ ) t ] τ ∈[t-1] ∈ R (t-1)×(t-Θ (j+1) = Θ (j) -η • J (0) • W [J (0) ] ⊺ ( Θ (j) -θ 0 ) -y + mλ( Θ (j)θ 0 ) , along with the Jacobian matrix J (0) := g(x 1 ; θ 0 ), g(x 2 ; θ 0 ), . . . , g(x t-1 ; θ 0 ) ∈ R p×(t-1) . Here, we have y, y ∈ R t-1 separately being the vector of received rewards and that of the imaginary corruption-free rewards. In particular, with [J (0) ] τ being the τ -th column of matrix J (0) , the auxiliary sequence Θ (j) can be deemed as applying Gradient Descent to solve the following optimization problemmin Θ L(Θ) = τ ∈[t-1] 1 2 • w (τ ) i,t [J (0) ] ⊺ τ (Θ -θ 0 ) -y τ 2 2 + 1 2 • mλ Θ -θ 0 2 2Consequently, we can follow an analogous approach as in Lemma D.1 with the above optimization problem, to bound the difference between gradient-based parameters and the auxiliary sequence.We bound the error term using Lemma C.7. Following the notation in the main body, let θ t-1 denote the trained parameters associated with the chosen arm x t , and let θ ĩt,t-1 represent the trained parameters of the arm x t = x ĩt,t , t ∈ [T ], which corresponds to the chosen arm of the hypothetical corruption-free model f (•; θ). Additionally, we define a weight-free gradient covariance matrix for the arm collection { x τ } τ ∈[t] containing arms selected by the corruption-free model, which will be denoted by Σ ′ t-1 = λI + τ ∈[t-1] g( x τ ; θ ĩτ ,τ -1 )g( x τ ; θ ĩτ ,τ -1 ) ⊺ /m. Lemma C.7. Suppose the imaginary corruption-free neural network f (•; θ i,t-1 ) for arm x i,t ∈ X t has been trained on corruption-free rewards {x τ , r τ } τ ∈[t-1] , while the other trained network f (•; θ i,t-1 ) is trained on the received records {x τ , r τ } τ ∈[t-1] . Suppose f (•) is an L-layer FC network with width m that satisfies the in Theorem 5.6. Then, for the arms x t , x t ∈ X t , with the probability at 1 δ, we will haveI 1 = ⟨g( x t ; θ ĩt,t-1 ), θ ĩt,t-1 -θ ĩt,t-1 ⟩ ≤ O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) • g( x t ; θ ĩt,t-1 )/ √ m (Σ ′ t-1 ) -1+ O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ).where θ t-1 are the parameters associated to chosen arm x t , and θ ĩt,t-1 are those parameters of arm x t . The gradient matrix is defined asΣ ′ t-1 = λI + τ ∈[t-1] g( x τ ; θ ĩτ ,τ -1 )g( x τ ; θ ĩτ ,τ -1) ⊺ /m, and we also haveΣt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m.Proof. Since the only difference between term I 1 and term I 2 is the gradients w.r.t. different arms, we begin with term I 1 = ⟨g( x t ; θ t-1 ), θ t-1 -θ t-1 ⟩, and the results can be readily generalized to term I 2 . Here, recall that we have ∥θ * -θ t ∥ Σt-1 ≤ γ t / √ m based on Lemma C.10, as well as∥θ t -θ 0 ∥ 2 , ∥ θ t -θ 0 ∥ 2 ≤ O( t/mλ) based on lemma G.3.Simplifying the notation. For the following proof, for the sake of notation simplicity, we directly useΘ (J), Θ (J) to respectively represent Θ(J) ĩt,t-1 , Θ (J) ĩt,t-1, which are the gradient descent based parameters associated with the arm x t . On the other hand, for the terms that belong to arm x t = x ĩt,t , we use θ ĩt , Σ ĩt and b ĩt to separately represent θ ĩt,t-1 , Σ ĩt,t-1 and b ĩt,t-1 by omitted the subscript of time step t -1 to simplify the notation.I 1 = ⟨g( x t ; θ ĩt ), θ ĩt -θ ĩt ⟩ ≤ ⟨g( x t ; θ ĩt ), θ ĩt -Θ (J) ⟩ + ⟨g( x t ; θ ĩt ), Θ (J) -θ ĩt ⟩ + ⟨g( x t ; θ ĩt ), Θ (J) -Θ (J) ⟩ I1.1 ≤ O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + ⟨g( x t ; θ ĩt ), Θ (J) -Θ (J) ⟩ I1.1, 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 I 1.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 θ 0 , we can formulate the least square parameters as (Σ (0) ĩt) -1 b (0) ĩt / √m, while the least square parameters trained by corruption-free rewards are analogously denoted by (Σ(0) ĩt ) -1 b (0) ĩt / √ m.In this case, the term I 1.1 can be alternatively transformed toI 1.1 = g( x t ; θ ĩt ), Θ (J) -Θ (J) ≤ g( x t ; θ ĩt ), (Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m) -( Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m) ≤ g( x t ; θ ĩt ), Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m + g( x t ; θ ĩt ), Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ mwhich further leads toI 1.1 ≤ x t ; θ ĩt ), Θ (J) -θ 0 -(Σ (0) ĩt ) b ĩt / √ m + g( x t ; θ ĩt ), Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m + g( x t ; θ ĩt ), (Σ (0) ĩt ) -1 ( τ ∈[t-1] w (τ ) ĩt,t • g(x τ ; θ 0 ) • c τ )/m I1.2 (C.17)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 θ ĩt . When trying to bound the first two terms on the RHS for the arm x t , we can first apply Holder's inequality withΣ ′ t-1 = λI + τ ∈[t-1] g( x τ ; θ ĩτ ,τ -1 )g( x τ ; θ ĩτ ,τ -1) ⊺ /m. Note that for the purpose of analysis and different from previous ones defined in (C.11), the new matrix (Σ ′ t-1 ) contains gradients of the sequence of arms{ x τ } τ ∈[t-1] chosen by the corruption-free model f (•; θ τ -1 ), τ ∈ [t -1], with the parameters θ τ -1 , τ ∈ [t -1].In this case, we use the Holder's inequality to the first term on the RHS of (C.17) asg( x t ; θ ĩt ), Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m ≤ g( x t ; θ ĩt )/ √ m (Σ ′ t-1 ) -1 • √ m • Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m (Σ ′ t-1 ) ≤ g( x t ; θ ĩt )/ √ m (Σ ′ t-1 ) -1 • √ m • Θ (J) -θ 0 -(Σ (0) ĩt ) -1 b (0) ĩt / √ m 2 • (Σ ′ t-1 ) 2 ≤ g( x t ; θ ĩt )/ √ m (Σ ′ t-1 ) -1 • O(λ + tL) • √ m(Θ (J) -θ 0 ) -(Σ (0) ĩt ) -1 b (0) ĩt 2 ≤ g( x t ; θ ĩt )/ √ m (Σ ′ t-1 ) -1 • O( √ λ + tL) • O (1 -ηmλ) J/2 t/λ + m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ) ≤ g( x t ; θ ĩt )/ √ m (Σ ′ t-1 ) -1 • O( √ λS)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 t ≤ 1 and the conditions in Theorem 5.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 I 1.2 Based on Arm Weights. Next, we proceed to bound term I 1.2 . Recall that we need to derive the upper bound for the following termI 1.2 = g( x t ; θ ĩt ), (Σ (0) ĩt ) -1 ( τ ∈[t-1] w (τ ) ĩt,t • g(x τ ; θ 0 ) • c τ )/m ≤ τ ∈[t-1] g( x t ; θ ĩt ), (Σ (0) ĩt ) -1 • w (τ ) ĩt,t • g(x τ ; θ 0 ) • c τ /m ≤ τ ∈[t-1] g( x t ; θ ĩt ), w (τ ) ĩt,t • (Σ (0) ĩt ) -1 g(x τ ; θ τ -1 )c τ /m + τ ∈[t-1] g( x t ; θ ĩt ), w (τ ) ĩt,t • (Σ (0) ĩt ) -1 (g(x τ ; θ 0 ) -g(x τ ; θ τ -1 ))c τ /m ≤ τ ∈[t-1] g( x t ; θ ĩt ), w (τ ) ĩt,t • (Σ (0) ĩt ) -1 g(x τ ; θ τ -1 ) • c τ /m + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ) ≤ τ ∈[t-1] g( x t ; ĩt ), w (τ ) ĩt,t • (Σ ĩt ) -1 g(x τ ; θ τ -1 ) • c /m O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ) + τ ∈[t-1] g( x t ; θ ĩt ), w (τ ) ĩt,t • ((Σ (0) ĩt ) -1 -(Σ ĩt ) -1 )g(x τ ; θ τ -1 ) • c τ /m ≤ τ ∈[t-1] g( x t ; θ ĩt ), w (τ ) ĩt,t • (Σ ĩt ) -1 g(x τ ; θ τ -1 ) • c τ /m I1.3+O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 )where the second and fourth inequality is due to triangular inequality. The third inequality is by Lemma G.4, and the last inequality is due to Lemma G.6.In particular, we aim to train separate neural models f (•; θ i,t ) for each candidate arm x i,t ∈ X t , such that the term I 1.2 can be minimized. Recall that we denote Σt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m as the "vanilla" gradient covariance matrix without the arm weights, in terms of the potentially corrupted network parameters θ τ -1 .In this case, with w (τ ) ĩt,t referring to the weight of arm x t , the above formulation of term I 1.3 can be further transformed intoI 1.3 ≤ τ ∈[t-1] w (τ ) ĩt,t • c τ m • g( x t ; θ ĩt ), (Σ ĩt ) -1 • g(x τ ; θ τ -1 ) ≤ τ ∈[t-1] w (τ ) ĩt,t • c τ • g( x t ; θ ĩt )/ √ m (Σĩ t ) -1 • (Σ ĩt ) -1 • g(x τ ; θ τ -1 )/ √ m Σĩ t ≤ τ ∈[t-1] w (τ ) ĩt,t • c τ • g( x t ; θ ĩt )/ √ m (Σĩ t ) -1 • g(x τ ; θ τ -1 )/ √ m (Σĩ t ) -1 ≤ τ ∈[t-1] w (τ ) ĩt,t • c τ • g( x t ; θ ĩt )/ √ m ( Σ(κ) t-1 ) -1 • g(x τ ; θ τ -1 )/ √ m ( Σ(κ) τ -1 ) -1 ≤ αC • min x∈Xt g(x; θ t-1 )/ √ m 2 ( Σt-1) -1 ≤ αC • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1where the first inequality follows from applying Holder's inequality, and the second and third inequalities are obtained by using Lemma G.8, along with the fact thatΣ ĩt ⪰ Σ(κ) t-1 ⪰ Σ(κ)τ -1 by definition. The last two inequalities are derived from the definition of the arm weight w Recall that for each arm x i,t ∈ X t , we define its weight asw (τ ) i,t = min 1, α• min x∈X t ∥g(x;θt-1)/ √ m∥ 2 Σ-1 t-1 gτ •∥g(xi,t;θt-1)/ √ m∥ ( Σ(κ) t-1 ) -1, where α > 0 is the tunable parameter. As a result, we will have the upper bound for I 1.2 , beingI 1.2 ≤ O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 ) + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 )In this case, since the weights are lower bounded by κ 2 , 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 a global view of the minimum fraction value β. In practice, the learner can adjust the α values in each round to ensure that the round-wise minimum weight value w min t = min{w(τ ) i,t } i∈[K] = κ 2 < 1, for all t ∈ [T ] and τ [t -1], by tuning the parameter α. By summing up all the results, we obtain single-round for term I 1 , which leads toI 1 ≤ O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) • g( x t ; θ ĩt,t-1 )/ √ m (Σ ′ t-1 ) -1+ O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t Similarly, for the term I 2 related to the chosen arm x t ∈ X t , we can follow the below procedure to obtain a comparable bound as for term I 1 .Corollary C.8. Suppose the imaginary corruption-free neural network f (•; θ i,t-1 ) for arm x i,t ∈ X t has been trained on corruption-free rewards {x τ , r τ } τ ∈[t-1] . f (•) is an L-layer FC network with width m that satisfy the conditions in Theorem 5.6. Then, for the chosen arm x t ∈ X t , with the probability at least 1 -δ, we will haveI 2 ≤ O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) • g(x t ; θ t-1 )/ √ m ( Σt-1) -1 + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 ) + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ).where θ t-1 are the trained parameters associated to chosen arm x t ∈ X t in round t, and θ ĩt,t-1 are the trained parameters of arm x t , along with the corresponding weight-free gradient covariance matrix Σt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m.Proof. The proof of this corollary follows an analogous procedure as in Lemma C.7.Simplifying the notation. For notation simplicity, we apply Θ(J)and Θ (J) to represent the gradient descent-based parameters associated with the arm x t . For terms specific to the arm x t = x it,t , we simplify notation by using θ t-1 , Σ t-1 , and b t-1 to denote θ it,t-1 , Σ it,t-1 , and b it,t-1 , respectively.Then, with the simplified notation, it leads toI 2 = ⟨g(x t ; θ t-1 ), θ t-1 -θ t-1 ⟩ ≤ ⟨g(x t ; θ t-1 ), θ t-1 -Θ (J) ⟩ + ⟨g(x t ; θ t-1 ), Θ (J) -θ t-1 ⟩ + ⟨g(x t ; θ t-1 ), Θ (J) -Θ (J) ⟩ I2.1 ≤ O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + ⟨g(x t ; θ t-1 ), Θ (J) -Θ (J) ⟩ I2.1where 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) bounding the difference between gradient-based parameters and the auxiliary sequence.Next, recall that with randomly initialized network parameters θ 0 , we can formulate the least square parameters as (Σ(0) t-1 ) -1 b (0) t-1 /m, while the least square parameters trained by corruption-free rewards are (Σ(0) t-1 ) -1 (0) t-1 / √ m.In this case, the term I 2.1 can be alternatively transformed toI 2.1 = t θ t-1 ), Θ (J) -Θ (J) ≤ g(x t ; θ t-1 ), Θ (J) -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 / √ m + g(x t ; θ t-1 ), Θ (J) -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 / √ m + g(x t ; θ t-1 ), (Σ (0) t-1 ) -1 ( τ ∈[t-1] w (τ ) t g(x τ ; θ 0 ) • c τ )/m I2.2 (C.19)where the inequality is 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Σt-1 = λI + τ ∈[t-1] g( x τ ; θ τ -1 )g( x τ ; θ τ -1) ⊺ /m, and it further leads tog(x t ; θ t-1 ), Θ (J) -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 / √ m ≤ g(x t ; θ t-1 )/ √ m ( Σt-1) -1 • √ m • Θ (J) -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 / √ m ( Σt-1) ≤ g(x t ; θ t-1 )/ √ m ( Σt-1) -1 • √ m • Θ (J) -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 / √ m 2 • ( Σt-1 ) 2 ≤ g(x t ; θ t-1 )/ √ m ( Σt-1) -1 • O(λ + tL) • √ m(Θ (J) -θ 0 ) -(Σ (0) t-1 ) -1 b (0) t-1 2 ≤ g(x t ; θ t-1 )/ √ m ( Σt-1) -1 • O( √ λ + tL) • O (1 -ηmλ) J/2 t/λ + m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ) ≤ g(x t ; θ t-1 )/ √ m ( Σt-1) -1 • O( √ λS)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 Lemma D.1, with the optimization problem being (C.12), in terms of the difference between gradient-based parameters and the auxiliary sequence. Finally, with w t ≤ 1 and the conditions in Theorem 5.6, applying the conclusion from Remark 4.7 in [86] will give the last inequality. Following a similar approach can also lead to the upper bound for the second term on the RHS of (C. 19 ).Bounding Term I 2.2 Based on Arm Weights. Next, we need to bound term I 2.2 . Recall that we want to have an upper bound for the following termI 2.2 = g(x t ; θ t-1 ), (Σ (0) t-1 ) -1 ( τ ∈[t-1] g(x τ ; θ 0 ) • c τ )/m ≤ τ ∈[t-1] g(x t ; θ t-1 ), (Σ (0) t-1 ) -1 g(x τ ; θ τ -1 ) • c τ /m + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ) ≤ τ ∈[t-1] g(x t ; θ t-1 ), (Σ t-1 ) -1 g(x τ ; θ τ -1 ) • c τ /m + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ) + τ ∈[t-1] g(x t ; θ t-1 ), ((Σ (0) t-1 ) -1 -(Σ t-1 ) -1 )g(x τ ; θ τ -1 ) • c τ /m ≤ τ ∈[t-1] g(x t ; θ t-1 ), (Σ t-1 ) -1 g(x τ ; θ τ -1 ) • c τ /m I2.3 +O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 ) + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 )where the first inequality follows from applying the triangle inequality and Lemma G.4. The inequality is also due to the triangle inequality, and the inequality follows from Lemma G.6. particular, we aim to train separate neural models f (•; θ i,t ) for each candidate arm x i,t ∈ X t to minimize the term I 2.2 . Similarly, recall that Σt-1 = λI + τ ∈[t-1] g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m is the gradient covariance matrix without arm weights, and w (τ ) t is the weight of arm x t , defined asw (τ ) t = min{1, α•min x∈X t ∥g(x;θt-1)/ √ m∥ 2 Σ-1 t-1 gτ •∥g(xt;θt-1)/ √ m∥ ( Σ(κ) t-1 ) -1}, where α > 0 is the tunable parameter. Similar to the derivation of term I 1.3 , it can further lead toI 2.3 ≤ τ ∈[t-1] w (τ ) t • c τ m • g(x t ; θ t-1 ), (Σ t-1 ) -1 • g(x τ ; θ τ -1 ) ≤ τ ∈[t-1] w (τ ) t • c τ • g(x t ; θ t-1 )/ √ m (Σt-1) -1 • (Σ t-1 ) -1 • g(x τ ; θ τ -1 )/ √ m Σt-1 ≤ τ ∈[t-1] w (τ ) t • c τ • g(x t ; θ t-1 )/ √ m (Σt-1) -1 • g(x τ ; θ τ -1 )/ √ m (Σt-1) -1 ≤ τ ∈[t-1] w (τ ) t • c τ • g(x t ; θ t-1 )/ √ m ( Σ(κ) t-1 ) -1 • g(x τ ; θ τ -1 )/ √ m ( Σ(κ) τ -1 ) -1 ≤ αC • min x∈Xt g(x; θ t-1 )/ √ m 2 ( Σt-1) -1 ≤ αC • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1where the first inequality is by applying the Holder's inequality, and the second and third inequalities are by applying Lemma G.8 with the fact that Σ t-1 ⪰ Σ(κ) t-1 ⪰ Σ(κ) τ -I 2.2 ≤ O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1+ O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ).In this case, since we need to ensure that the minimum weight is κ 2 , 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 β, and the learner can adjust the α values in each round to ensure that the round-wise minimum weightw min t = min{w (τ ) i,t } i∈[K] < 1, for all t ∈ [T ] and τ ∈ [t -1]. By summing up all the results, we haveI 2 ≤ O(αC) • g(x t ; θ t-1 )/ √ m 2 ( Σt-1) -1 + O( √ λS) • g(x t ; θ t-1 )/ √ m ( Σt-1) -1 + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 7/6 λ -1/6 L 5 )+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 4 ).In this subsection, we provide upper bounds for UCB t (x t ) in terms of the corruption-free parameters θ t-1 . Recall that without the arm index i ∈ [K], the parameters θ, covariance matrix Σ t-1 , confidence ellipsoid C t-1 , and weights w pertain to the chosen arm x t . For the hypothetical corruption-free parameters θ, trained with corruption-free rewards, Lemma C.9 the responding UCB result, and Lemma C.10 introduces the associated confidence ellipsoid. For the trained parameters θ i,t-1 , based on the received records P t-1 with potentially corrupted rewards, Lemma C.11 presents the corresponding UCB for each candidate arm x i,t ∈ X t , while Lemma C.12 provides the corresponding confidence ellipsoid. Note that Lemmas C.11 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 (•; θ t-1 ) in round t ∈ [T ] has been trained on corruption-free rewards {x τ , r τ } τ ∈[t-1] , and f (•) is an L-layer FC network with width m. Suppose we have m, J, η satisfying the conditions in Theorem 5.6. Then, for the chosen arm x t ∈ X t , with the probability at least 1 -δ, we will haveUCB t (x t ) = V (x t ) -h(x t ) ≤ 2 γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 1/6 λ -7/6 L 2/7 ),and the corresponding summation value across T rounds will bet∈[T ] min UCB t (x t ), 1 = t∈[T ] min V (x t ) -h(x t ), 1 ≤ 1 w min t O ν log det( Σ T ) det(λI) -2 log(δ) + λ 1/2 S • 2T • log det( Σ T ) det(λI) + O(Sm -1/6 log(m)T 7/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)T 7/6 λ -7/6 L 2/7 )By definitions in Lemma C.10, we have the corresponding radius term for confidence ellipsoid C t-1as γ t-1 = O ν • log det( Σt-1)det(λI) -2 log(δ) + λ 1/2 S , and the gradient covariance matrix asΣ t-1 = λI + τ ∈[t-1] w (τ ) t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m.Proof. With the confidence ellipsoid around the corruption-free parameters C t-1 := {θ : ∥θ -θ t-1 ∥ Σt-1 ≤ γ t-1 / √ m, γ t-1 > 0},we have θ * ∈ C t-1 according to Lemma C.10. In this case, with the coefficient γ t-1 = O ν • log det( Σt-1) det(λI) -2 log(δ) + λ 1/2 S and the gradient covariance matrixΣ t-1 = λI + τ ∈[t-1] w (τ ) t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m, we have UCB t (x t ) = V (x t ) -h(x t ) = max θ∈ Ct-1 g(x t ; θ 0 ), θ -θ 0 -g(x t ; θ 0 ), θ * -θ 0 ≤ max θ∈ Ct-1 g(x t ; θ 0 ), θ -θ t-1 -g(x t ; θ t-1 ), θ * -θ t-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) ≤ max θ∈ Ct-1 ∥θ -θ t-1 ∥ Σt-1 ∥g(x t ; θ 0 )∥ Σ -1 t-1 + ∥g(x t ; θ t-1 )∥ Σ -1 t-1 ∥θ * -θ t-1 ∥ Σt-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) ≤ 2 γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 1/6 λ -7/6 L 2/7 ) (C.20)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 t-1 , Lemma G.4, and Lemma G.6. Next, recall that the above UCB t is one term composing the single-round regret R t , and for the cumulative regret, it will be summed up across T rounds. In this case, for the first term on the RHS above, we havet∈[T ] 2 • min γ t-1 • ∥g(x t θ t-1 )/ √ m∥ Σ -1 t-1 , 1 t∈[T ] 2 • min γ t-1 √ w t • ∥ √ w t g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 , 1 ≤ 2(1 + γ T w min t ) • t∈[T ] min ∥ √ w t g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 , 1 ≤ 2(1 + γ T w min t ) • T • t∈[T ] min ∥ √ w t g(x t ; θ t-1 )/ √ m∥ 2 Σ -1 t-1, 1where we have w min t < 1. Then, applying Lemma G.7 and by the definition of γ T as well as supposing that γ T √ w min t ≥ 1, we will havet∈[T ] 2 min γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Σ -1 t-1 , 1 ≤ 1 w min t O ν log det( Σ T ) det(λI) -2 log(δ) + λ 1/2 S • 2T • log det( Σ T ) det(λI) .Next, for the corrupted parameters θ i,t-1 , we consider the confidence ellipsoidC i,t-1 := {θ : ∥θ -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 / √ m} constructed around the corrupted parameters θ i,t-1 , with the coefficient γ i,t-1 = O ν • log det(Σi,t-1) det(λI)-2 log(δ) + λ 1/2 S and the gradient covariance matrix 10 . In round t, with the notation and conditions in Theorem 5.6, suppose the corruptionfree parameters θ i,t-1 associated with a candidate arm x i,t ∈ X t are trained by L(θ) =Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m. Lemma C.1 2 τ ∈[t-1] w (τ ) i,t • |f (x τ ; θ) -r τ | 2 + mλ 2 • ∥θ -θ 0 ∥ 2 2. Then, we have the corresponding confidence ellipsoidEQUATION-2 log(δ) + λ 1/2 S , and the gradientcovariance matrix Σ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m.Proof. The proof of this lemma follows an analogous approach as in Lemma 5.2 in [86] . Recall that based on Lemma C.1, we have the expected reward of an arm x ∈ X t being E[r|x] = h(x) = ⟨g(x; θ 0 ), θ * -θ 0 ⟩ where there exist parameters θ * such that ∥θ * -θ 0 ∥ ≤ S/ √ m, S > 0. Intuitively, for each previously chosen arm x τ , τ ∈ [t -1], we can consider an alternative form beingE w (τ ) i,t • r x τ = w (τ ) i,t • h(x τ ) = w (τ ) i,t • g(x τ ; θ 0 )/ √ m, √ m(θ * -θ 0 )where w > 0 refers to the weight associated with arm x in our settings of R-NeuralUCB. Afterwards, with the weighted sequence of chosen arm gradients as well as their expected corruption-free rewards, we can have∥ √ m(θ * -θ 0 ) -( Σ (0) i,t-1 ) -1 b (0) i,t-1 ∥ Σ (0) i,t-1 ≤ ν • log det( Σ (0) i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S,by applying the conclusion of Theorem 2 from [1] . In this case, by triangular inequality, we also have∥θ * -θ 0 ∥ Σi,t-1 ≤ ∥θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 + ∥ θ i,t-1 -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 .Then, for the first term on the right hand side, we have∥θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ 2 Σi,t-1 (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ⊺ Σ (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) = (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ⊺ Σ (0) i,t-1 (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) + (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ⊺ • ( Σ i,t-1 -Σ (0) i,t-1 ) • (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ≤ (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ⊺ Σ (0) i,t-1 (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) + ∥ Σ i,t-1 -Σ (0) i,t-1 ∥ 2 λ • (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ⊺ Σ (0) i,t-1 (θ * -θ 0 -( Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m) ≤ (1 + ∥ Σ i,t-1 -Σ (0) i,t-1 ∥ 2 λ ) • ν • log det( Σ (0) i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S /m ≤ m -1/2 • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • ν • log det( Σ i,t-1 ) det(λI) + O(m -1/6 log(m)L 4 t 5/3 λ -1/6 ) -2 log(δ) + λ 1/2 Swhere the first inequality is because x ⊺ Ax ≤ x ⊺ Bx • ∥A∥ 2 /λ min (B) for some 0 ≺ B and the fact that the minimum eigenvalue λ min ( Σi,t-1 ) ≥ λ, and the last inequality is by Lemma G.6 as well as due to the fact w (τ ) i,t ≤ 1. Afterwards, for the second term, we haveEQUATION√ m∥ 2 ≤ O( √ λ + tL) • O (1 -ηmλ) J/2 t/mλ + m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ) .The first inequality follows from applying Lemma G.6. For the second inequality, we apply a similar approach as in Lemma D.1, with the optimization problem given by (C.12). Since we scale the α parameter to ensure 1 > w (τ ) i,t ≥ κ 2 , 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 κ 2 and under the conditions in Theorem 5.6, applying Remark 4.7 in [86] completes the proof.Lemma C.11. For candidate arm x i,t ∈ X t , suppose its associated neural network f (•; θ i,t-1 ) has been trained on received records {x τ , r τ } τ ∈[t-1] , with J iterations of GD and learning rate η. Let f (•; θ i,t-1 ) be an L-layer FC network with width m. Suppose conditions in Theorem 5.6 are satisfied. Then, given the candidate arm x i,t ∈ X t , with a constant ζ > 0 and probability at least 1 -δ, we will havef (x i,t ; θ i,t-1 ) -h(x i,t ) ≤ ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1 • ζ • ν log det(Σ i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 ) + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 2 t 5/6 λ -1/12 ) + O(αC) • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ), (C.21)with notation and definitions in Theorem 5.6. We also have the covariance matrixEQUATIONi,t • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ , with gradient vector g(x i,t ; = vec(∇ θ f (x i,t ; θ)).Proof. Applying Lemma C.1, we can transform the objective by substituting the reward mapping function h(•), asf (x i,t ;θ i,t-1 ) -h(x i,t ) = f (x i,t ; θ i,t-1 ) -g(x i,t ; θ 0 ), θ * -θ 0 ≤ f (x i,t ; θ i,t-1 ) -g(x i,t ; θ i,t-1 ), θ * -θ 0 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) ≤ f (x i,t ; θ i,t-1 ) -g(x i,t ; θ i,t-1 ), θ i,t-1 -θ 0 + g(x i,t ; θ i,t-1 ), θ i,t-1 -θ 0 -g(x i,t ; θ i,t-1 ), θ * -θ 0 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 )where the first equality is due to Lemma C.1, while the first inequality is due to Lemma G.4 and Lemma C.1, and the last inequality is because of the triangular inequality. Then, we proceed to separately bound the first and second term on the RHS. For the first term, we will havef (x i,t ; θ i,t-1 ) -g(x i,t ; θ i,t-1 ), θ i,t-1 -θ 0 = f (x i,t ; θ i,t-1 ) -f (x i,t ; θ 0 ) -g(x i,t ; θ i,t-1 ), θ i,t-1 -θ 0 ≤ O(m -1/6 log(m)t 2/3 λ -2/3 L 3 )where the first equality is due to the fact that f (x i,t ; θ 0 ) = 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 haveg(x i,t ; θ i,t-1 ),θ i,t-1 -θ 0 -g(x i,t ; θ i,t-1 ), θ * -θ 0 = g(x i,t ; θ i,t-1 ), θ * -θ i,t-1 ≤ ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1 • √ m • ∥θ * -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 • ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1where the first inequality is by applying the Holder's inequality, and the last inequality is by applying Lemma 5.2 in [86] , Lemma C.1 in terms of the confidence set C i,t-1 and the fact that θ * ∈ C i,t-1 .Then, with the confidence ellipsoid introduced and discussed in Lemma C.12, summing up the results above, we will then havef (x i,t ; θ i,t-1 ) -h(x i,t ) ≤ ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1 • O ν log det(Σ i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S + O(αC) • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x i,t ; θ i,t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1 + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ))+ O(Cm -2/3 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 )+ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 2 t 5/6 λ -1/12 ) + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) = ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1 • O ν log det(Σ i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 -5/3 (1 + t/λ)) + O(Cm -1/6 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ L 9/2 ) + ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 2 t 5/6 λ -1/12 ) + ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1 • O(αC) • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x i,t ; θ i,t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ).where we naturally have Hermitian matrices Σ i,t-1 ⪰ Σ(κ) t-1 by definition, which leads to(Σ i,t-1 ) -1 ⪯ ( Σ(κ) t-1) -1 by applying the conclusion from Lemma G.8. Afterwards, due to the fact that the minimum round-wise arm weightw min t = min{w (τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 < 1, ∀t ∈ [T ]by scaling parameter α, we can further havef (x i,t ; θ i,t-1 ) -h(x i,t ) ≤ ∥g(x i,t ; θ i,t-1 )/ √ m∥ Σ -1 i,t-1 • O ν log det(Σ i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ))+ O(Cm -2/3 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 )+ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 2 t 5/6 λ -1/12 ) + O(αC) • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ),which completes the proof for this lemma.Lemma C.12. In round t ∈ [T ], with the notation and conditions from Theorem 5.6, suppose the corrupted parameters θ i,t-1 associated with a candidate arm x i,t ∈ X t are trained byL(θ) = 1 2 τ ∈[t-1] w (τ ) i,t • |f (x τ ; θ) -r τ | 2 + mλ 2 • ∥θ -θ 0 ∥ 2 2 .Then, we have the confidence ellipsoidC i,t-1 = θ : ∥θ -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 / √ mwhere we have the unknown parameter θ * ∈ C i,t-1 , and we denoteγ i,t-1 = O ν log det(Σ i,t-1 ) det(λI) -2 log(δ) + λ 1/2 S + O(αC) • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x i,t ; θ i,t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1 + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ))+ O(Cm -1/6 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 )+ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -1/12 log 1/4 (m)L 2 t 5/6 λ -1/12 ).Proof. Recall that for the imaginary corruption-free parameters θ i,t-1 , trained on corruption-free records P t-1 , we can construct the confidence intervalC i,t-1 := {θ : ∥θ -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 / √ m, i,t-1 > 0}, ensuring that the unknown θ * in Lemma C.1 satisfies θ * ∈ C i,t-1 . The corresponding confidence ellipsoid is presented in C.10.With the ellipsoid centered at θ i,t-1 and the gradient covariance matrix defined asΣ i,t-1 = λI + τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • g(x τ ; θ τ -1) ⊺ /m, we proceed to derive the corresponding radius. Recall that w (τ ) i,t denotes the sample weight associated with the chosen arm x τ . For reference, we first recall the preliminary bounds: ∥Σ i,t-1 -Σ i,t-1 ∥ F ≤ O(m -1/6 log(m)L 4 t 7/6 λ -1/6 ) by Lemma G.6 and ∥θ i,t-1 -θ i,t-1 ∥ 2 ≤ O( t/(mλ)) as shown in Lemma G.3. Next, as we already have ∥θ -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 /√ m, we then proceed to transform the objective to∥θ * -θ i,t-1 ∥ Σi,t-1 ≤ ∥θ * -θ i,t-1 ∥ Σi,t-1 + ∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 ≤ ∥θ * -θ i,t-1 ∥ Σi,t-1 + ∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 ≤ ∥θ * -θ i,t-1 ∥ Σi,t-1-Σi,t-1+ Σi,t-1 + ∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 ≤ ∥θ * -θ i,t-1 ∥ Σi,t-1 + ∥θ * -θ i,t-1 ∥ Σi,t-1-Σi,t-1 + ∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 ≤ γ i,t-1 / √ m + ∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 + O( t/(mλ)) • O(m -1/6 log(m)L 4 t 7/6 λ -1/6 ) ≤ γ i,t-1 / √ m + ∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 + O(m -2/3 log(m)L 4 t 13/6 λ -2/3 ).For the first term on the RHS, we can follow the proof flow in Lemma C.6, by applying Lemma G.4 to substitute Σ i,t-1 with corresponding Σ i,t-1 , which will consequently lead to|γ i,t-1 / √ m - γ i,t-1 / √ m| ≤ ν • 1 + O(m -1/6 log(m)L 4 t 7/6 λ -7/6 ) • O(m -7/12 log 1/4 (m)L 2 t 5/6 λ -1/12). Meanwhile, for the second term on the RHS, we first define the gradient-based regression parameters asEQUATIONi,t-1 = τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • r τ / √ m,Then, we can proceed to have∥ θ i,t-1 -θ i,t-1 ∥ Σi,t-1 ≤ ∥ θ i,t-1 -θ 0 -(Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m + (Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m + θ 0 -θ i,t-1 ∥ Σi,t-1 ≤ ∥θ i,t-1 -θ 0 -(Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 + ∥ θ i,t-1 -θ 0 -(Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 ≤ ∥θ i,t-1 -θ 0 -(Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 + ∥ θ i,t-1 -θ 0 -(Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 + m -1 ∥(Σ (0) i,t-1 ) -1 • ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-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 ∈ [J]) with Θ (0) = θ 0 , asΘ (j+1) = Θ (j) -η • J (0) • W • [J (0) ] ⊺ (Θ (j) -θ 0 ) -y + mλ(Θ (j) -θ 0 )where the Jacobian matrix J (0) := g(x 1 ; θ 0 ), g(x 2 ; θ 0 ), . . . , g(x i,t-1 ; θ 0 ) ∈ R p×(t-1) , vector y ∈ R t-1 contains the received arm rewards r τ , τ ∈ [t -1], and matrix W ∈ R (t-1)×(t-1) is the diagonal matrix that contains sample weights w(τ ) i,t , τ ∈ [t -1].In particular, we have its norm ∥W∥ 2 ≤ 1 by definition. Here, with [J (0) ] τ being the τ -th column of matrix J (0) , the sequence is expected to solve the following problemmin Θ L(Θ) = τ ∈[t-1] w (τ ) i,t 2 • (0) ] ⊺ τ (Θ -θ 0 ) -r τ 2 2 + 1 2 • mλ • Θ -θ 0 2 2 .As a result, following an analogous approach as in Lemma C.4 in [86] , we can have∥Θ (j) -θ 0 - (Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ Σi,t-1 ≤ (1 -ηmλ) j/2 t/(mλ). Furthermore, by applying the conclusion of Lemma D.1, we can have∥θ i,t-1 -θ 0 -(Σ (0) i,t-1 ) -1 b (0) i,t-1 / √ m∥ 2 ≤ (1 -ηmλ) J/2 t/(mλ) + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)).Similarly, for the second term in Inequality C.22, we also can apply a comparable approach by solving the problem:min Θ L(Θ) = τ ∈[t-1] w (τ ) i,t 2 [J (0) ] ⊺ τ (Θ -θ 0 ) -r τ 2 2 + 1 2 mλ • Θ -θ 0 2 2 ,and constructing the corresponding auxiliary sequence. This will lead to a similar bound for the second term on the RHS of inequality C.22, such thatEQUATION√ m∥ 2 ≤ (1 -ηmλ) J/2 t/(mλ) + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)).Bounding the third term in Inequality C. 22 . Then, for the third term on the RHS, we first havem -1 • ∥(Σ (0) i,t-1 ) -1 • ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-1 ≤ m -1 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-1 + m -1 ∥ (Σ i,t-1 ) -1 -(Σ (0) i,t-1 ) -1 • ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-1 ≤ m -1 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-1 + m -1 ∥(Σ i,t-1 ) -1 Σ i,t-1 -Σ (0) i,t-1 (Σ (0) i,t-1 ) -1 • ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-1 ≤ m -1 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ 0 ) • c τ )∥ Σi,t-1 + O(Cm -2/3 log(m)t 7/6 λ -13/6 L 9/2 ) ≤ m -1 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • c τ )∥ Σi,t-1 + O(Cm -2/3 log(m)t 7/6 λ -13/6 L 9/2 ) + m -1 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • (g(x τ ; θ τ -1 ) -g(x τ ; θ 0 )) • c τ )∥ Σi,t-1 ≤ m -1 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • c τ )∥ Σi,t-1 + O(Cm -7/6 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -2/3 log(m)t 7/6 λ -13/6 L 9/2 ),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 (τ ) i,t from (4) for each previously chosen arm x τ . In this case, we can further havem -1/2 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • c τ )/ √ m∥ Σi,t-1 = m -1/2 ∥ τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • c τ / √ m∥ -1 ≤ m -1/2 τ ∈[t-1] w (τ ) i,t τ • ∥g(x τ ; θ τ -1 )/ √ m∥ (Σi,t-1) -1where the first inequality is by applying the triangular inequality. By definition, we naturally haveΣ i,t-1 ⪰ Σ(κ) τ -1 , ∀τ ∈ [t -1]. Next, we utilize Lemmas G.8 and the fact thatw min t = min{w (τ ) i,t } i∈[K],τ ∈[t-1] = κ 2 < 1, ∀t ∈ [T ]by scaling the parameter α, which will lead tom -1/2 ∥(Σ i,t-1 ) -1 ( τ ∈[t-1] w (τ ) i,t • g(x τ ; θ τ -1 ) • c τ )/ √ m∥ Σi,t-1 ≤ O(m -1/2 ) τ ∈[t-1] w (τ ) i,t c τ • ∥g(x τ ; θ τ -1 )/ √ m∥ (Σi,t-1) -1 ≤ O(m -1/2 ) τ ∈[t-1] w (τ ) i,t c τ • ∥g(x τ ; θ τ -1 )/ √ m∥ ( Σ(κ) τ -1 ) -1 ≤ O(m -1/2 ) τ ∈[t-1] c τ • α • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x i,t ; θ i,t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1 ≤ O(m -1/2 ) • C • α • min x∈Xt ∥g(x; θ i,t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x i,t ; θ i,t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1, where the third and the last inequalities are due to the definition of w (τ )i,t and the definition of corruption level C. Finally, summing up all the results will give the lemma.In this subsection, we provide an exemplary upper bound of O(1/β). 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, we recall that, as defined in (4), each candidate arm x i,t ∈ X t is associated with the corresponding arm weight:w (τ ) i,t = min    1, α • min x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 Σ-1 t-1 g τ • ∥g(x i,t ; θ t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1    = min 1, α • frac τ (x i,t ; X t , Σt-1 ) ,where α > 0 is a tunable scaling parameter to control the arm weight value range, and frac(•) is a shorthand for the fraction term. We denote the data-dependent minimum fraction value as β = min t∈[T ],τ ∈[t-1] min frac τ (x t ; X t , Σt-1 ), frac τ ( x t ; X t , Σt-1 ) . In this case, the lower bound for frac τ (x i,t ; X t , Σt-1 ), represented by β, can be expressed asmin x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x τ ; θ τ -1 )/ √ m∥ ( Σ(κ) τ -1 ) -1 • ∥g(x i,t ; θ t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1 ≥ min x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 Σ-1 t-1 O(L • λ -1 ) ≥ min x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 2 • λ min ( Σ-1 t-1 ) O(L • λ -1 )where the first inequality is because of Lemma G.2 and Lemma G.6. The second inequality is by applying Rayleigh-Ritz theorem.Then, we let Pt-1 ⊆ P t-1 being the collection of received records that only consists of unique chosen arms from P t-1 . With θt-1 be the parameters trained on Pt-1 , applying Lemma G.4 and Lemma G.3, we have ∥g(x ′ ; θ t-1 )/ √ m -g(x ′ ; θt-1 )/ √ m∥ 2 ≤ -1/6 λ -1/6 t L 7/2 log(m)), where x ′ = arg min x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 . Given the over-parameterization settings in Theorem 5.6 with sufficiently large m, we can have ∥g(x ′ ; θ t-1 )/ √ m -g(x ′ ; θt-1 )/ √ m∥ 2 ≪ O(1). As a result, it leads tomin x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 Σ-1 t-1 ∥g(x τ ; θ τ -1 )/ √ m∥ ( Σ(κ) τ -1 ) -1 • ∥g(x i,t ; θ t-1 )/ √ m∥ ( Σ(κ) t-1 ) -1 ≥ min x∈Xt ∥g(x; θ t-1 )/ √ m∥ 2 2 • λ min ( Σ-1 t-1 ) O(L • λ -1 ) ≥ ∥g(x ′ ; θt-1 )/ √ m∥ 2 2 + ∥g(x ′ ; θ t-1 )/ √ m∥ 2 2 -∥g(x ′ ; θt-1 )/ √ m∥ 2 2 • λ min ( Σ-1 t-1 ) O(L • λ -1 ) ≥ O(1) • λ min ( Σ-1 t-1 ) O(L • λ -1 )where the second inequality is derived based on ∥g(x ′ ;θ t-1 )/ √ m∥ 2 2 -∥g(x ′ ; θt-1 )/ √ m∥ 2 2 ≥ -1 • (∥g(x ′ ; θ t-1 )/ √ m -g(x ′ ; θt-1 )/ √ m∥ 2 • ∥g(x ′ ; θ t-1 )/ √ m + g(x ′ ; θt-1 )/ √ m∥ 2), and we bound the two multipliers separately with choice of m. The last inequality is by applying Theorem 3 of [3] with the fact that f (•; θ t-1 ) = O(1) (Lemma B.2 in [21] ).Afterwards, regarding the lower bound of λ min ( Σ-1 t-1 ), since λ min ( Σ-1 t-1 ) = 1 λmax( Σt-1) , we need to find the upper bound for ∥ Σt-1 ∥ 2 . Denoting G (0) t-1 = [g(x 1 ; Θ 0 ), g(x 2 ; Θ 0 ), . . . , g(x t-1 ; Θ 0 )] ⊺ ∈ R (t-1)×p as the gradient matrix, as well as H t-1 ∈ R (t-1)×(t-1) as the NTK matrix constructed from the chosen arms {x τ } τ ∈[t-1] , with sufficient network width m (Theorem 5.6), we first have∥G (0) t-1 (G (0) t-1 ) ⊺ /m -H t-1 ∥ 2 ≤ O(1)and this inequality is because of Lemma B.1 in [86] by setting ϵ = t -1. In this case, we will have∥ Σt-1 ∥ 2 -λ max (H t-1 ) ≤ ∥ Σt-1 ∥ 2 -∥(G (0) t-1 ) ⊺ G (0) t-1 /m∥ 2 + ∥G (0) t-1 (G (0) t-1 ) ⊺ /m∥ 2 -λ max (H t-1 ) ≤ ∥ Σt-1 -(G (0) t-1 ) ⊺ G (0) t-1 /m∥ 2 + ∥G (0) t-1 (G (0) t-1 ) ⊺ /m -H t-1 ∥ 2 ≤ O(m -1/6 log(m)L 4 t 7/6 λ -1/6 ) + O(λ) + O(1)where the last inequality is by applying Lemma G.6. This leads to the result that ∥ Σt-1 ∥ 2 ≤ λ max (H t-1 ) + O(m -1/6 log(m)L 4 t 7/6 λ -1/6 ) + O(λ) + O(1).Then, inspired by Section D in [84] , based on the formulation from [14] and [20] , we can consider that each entry of H t-1 is generated by[H t-1 ] i,i ′ = ∞ k=0 µ k N (d,k) j=1 Y k,j (x i )Y k,j (x i ′ ),where Y k,j are linearly independent spherical harmonics, w.r.t. degree k and d variables.N (d, k) = 2k+d-2 k • C d-2 k+d-3 , µ k = Θ(max{k -d , (d -1) 1-k }).With the above feature mapping, if we have a subspace of the RKHS, such that the feature mapping in the RKHS is close enough to its projection onto this subspace, we can have λ max (H t-1 ) = ∥H t-1 ∥ 2 ≤ O(1). As a result, summing up the results and with sufficiently large m, we can have 1 β ≤ O(Lλ -1 ).In section, with weighted Gradient Descent, we provide the upper bound in terms of the distance between GD trained parameters θ t-1 and the regression parameters (Σ(0) t-1 ) -1 b (0)t-1 . The results will be applied to the proof flow of both NeuralUCB-WGD and R-NeuralUCB. First, with the definitions in Subsec. C.2, we have the gradient-based regression parameters specified to arm x t ∈ X t asΣ (0) t-1 = λI + τ ∈[t-1] w (τ ) t g(x τ ; θ 0 )g(x τ ; θ 0 ) ⊺ /m, Σ t-1 = λI + τ ∈[t-1] w (τ ) t g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m, b (0) t-1 = τ ∈[t-1] w ) t τ ; θ 0 ) • r τ / √ m, b t-1 = τ ∈[t-1] w (τ ) t g(x τ ; θ τ -1 ) • r τ / √ mwhere {x τ , r τ }, τ ∈ [t] respectively stands for the chosen arms as well as their rewards. For notation simplicity, we also use w(τ ) t , τ ∈ [t -1]to denote the arm weights for the chosen arm x t respectively.Analogously, given an candidate arm x i,t ∈ X t with arm weight w (τ ) i,t defined in (4), we have a series auxiliary gradient sequences {Θ (0) , Θ (1) , . . . , Θ (J) } as in G.3, such that for j-th iterationΘ (j+1) = Θ (j) -η • J (0) • W • [J (0) ] ⊺ (Θ (j) -θ 0 ) -y + mλ(Θ (j) -θ 0 )where J (0) := g(x 1 ; θ 0 ), g(x 2 ; θ 0 ), . . . , g(x t-1 ; θ 0 ) ∈ R p×(t-1) , and W refers to the diagonal matrix of arm weights {w(τ ) i,t } τ ∈[t-1], along with the reward vectors y ∈ R t-1 separately being the vector of received rewards and corruption-free rewards. In particular, the auxiliary sequence Θ (j) can be deemed as applying Gradient Descent to solve the following optimization problemmin Θ L(Θ) = τ ∈[t-1] 1 2 • w (τ ) i,t • [J (0) ] ⊺ τ (Θ -θ 0 ) -y τ 2 2 + 1 2 • mλ • Θ -θ 0 2 2where [J (0) ] τ refers to the τ -th column of the matrix J (0) . Analogously, we can also derive the optimization problem for the sequence of corruption-free auxiliary parameters Θ, by applying the same definition of weight matrix W. By the definition of arm weights, we will also have ∥W∥ 2 ≤ 1. Lemma D.1 (Lemma B.2 of [86] ). With the notation and conditions in Theorem 5.6, consider m ≥ Ω(poly(T, L, λ-1 0 , λ -1 ) and η ≤ O( 1 mλ+tmL ). For round t ∈ [T ], we have∥θ t-1 -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 ∥ 2 ≤ (1 -ηmλ) J/2 t/(mλ) + O(m -2/3 t 5/3 log(m)L 7/2 λ -5/3 (1 + t/λ))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 {Θ (0) , Θ (1) , . . . , Θ (J) }, we denote another set of auxiliary sequences to simulate the J iterations of GD, byθ (j+1) = θ (j) -η • J (j) • W • f (j) -y + mλ(θ (j) -θ 0 )where we denote the corresponding gradient matrix at the j-th iteration as J (j) = g(x 1 ; θ (j) ), g(x 2 ; θ (j) ), . . . , g(x t-1 ; θ (j) ) ∈ R p×(t-1) , as well as the vector of network outputs f (j) = f (x 1 ; θ (j) ), f (x 2 ; θ (j) ), . . . , f (x t-1 ; θ (j) ) ∈ R t-1 . In this case, we can have the difference between parameter sequences as∥θ (j+1) -Θ (j+1) ∥ = ∥(1 -ηmλ) • (θ (j) -Θ (j) ) -ηW(J (j) -J (0) )(f (j) -y) -ηW(f (j) -[J (0) ] ⊺ (Θ (j) -θ 0 ))∥ ≤ ∥(1 -ηmλ) • (θ (j) -Θ (j) )∥ + η∥W(J (j) -J (0) )(f (j) -y)∥ + η∥J (0) W(f (j) -[J (0) ] ⊺ (Θ (j) -θ 0 ))∥ ≤ ∥(1 -ηmλ)(θ (j) -Θ (j) )∥ + η∥W∥∥(J (j) -J (0) )(f (j) -y)∥ + η∥J (0) W∥∥f (j) -[J (0) ] ⊺ (Θ (j) -θ 0 )∥ ≤ ∥(1 -ηmλ) • (θ (j) -Θ (j) )∥ I4 + η • ∥(J (j) -J (0) )(f (j) -y)∥ I5 + η • ∥J (0) ∥∥f (j) -[J (0) ] ⊺ (Θ (j) -θ 0 )∥ I6where the first inequality is by applying the triangular inequality. The second inequality is by using Cauchy-Schwartz inequality, and the third inequality is due to the fact that ∥W∥ 2 ≤ 1. Here, the first term I 4 can be bounded recursively. For the second term I 5 on the RHS, we have I 5 = η∥(J (j) -J (0) )(f (j) -y)∥ ≤ η∥(J (j) -J (0) )∥∥(f (j) -y)∥ ≤ O(ηt 7/6 m 1/3 log(m)L 7/2 λ -1/6 ) by extending Lemma G.4 to the matrix J. Since we have the arm weights w (τ ) i,t ≤ O(1) due to the maximum cap as 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 I 6 , we will haveI 6 = η • ∥J (0) ∥∥f (j) -[J (0) ] ⊺ (Θ (j) -θ 0 )∥ ≤ η • ∥J (0) ∥ • max τ ∈[t-1] √ t • |f (x τ ; θ j ) -f (x τ ; θ 0 ) -⟨g(x τ ; θ 0 ), θ j -θ 0 ⟩| ≤ O(ηt 5/3 m 1/3 log(m)L 7/2 λ -2/3 )by extending Lemma G.2 to the gradient matrix setting, as well as applying the Lemma G.5 on the absolute value. Afterwards, we can integrate these three terms, which will lead to∥θ (j+1) -Θ (j+1) ∥ ≤ ∥(1 -ηmλ) • (θ (j) -Θ (j) )∥ + O(ηt 7/6 m 1/3 log(m)L 7/2 λ -1/6 ) + O(ηt 5/3 m 1/3 log(m)L 7/2 λ -2/3 ) ≤ (1 -ηmλ)∥θ (j) -Θ (j) ∥ + O(ηt 7/6 m 1/3 log(m)L 7/2 λ -1/6 ) + O(ηt 5/3 m 1/3 log(m)L 7/2 λ -2/3 ) ≤ O(m -2/3 t 5/3 log(m)L 7/2 λ -5/3 (1 + t/λ))where for term I 4 , the last inequality is obtained by recursively applying the process to ∥θ (0) -Θ (0) ∥ = 0 and substituting the chosen upper bound for the learning rate η. Then, with a sufficiently large network width m as indicated in the lemma, we have∥θ t-1 -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 ∥ 2 ≤ ∥θ (j+1) -Θ (j+1) ∥ + ∥Θ (j+1) -θ 0 -(Σ (0) t-1 ) -1 b (0) t-1 ∥ 2 ≤ ∥Θ (j+1) -θ 0 -(Σ (0) t-1 ) -1 b (0)t-1 ∥ 2 + O(m -2/3 t 5/3 log(m)L 7/2 λ -5/3 (1 + t/λ)) ≤ (1 -ηmλ) j/2 t/(mλ) + O(m -2/3 t 5/3 log(m)L 7/2 λ -5/3 (1 + t/λ))where the first inequality is by applying triangular inequality, and the second inequality is by applying the previous conclusion. The last inequality is by applying Lemma C.4 in [86] with the fact that ∥θ (j+1) -Θ (j+1) ∥ ≤ t/(mλ). Since we have the arm weights w (τ ) i,t ≤ 1 due to its maximum bound, we apply the conclusion of Lemma C.4 in [86] for the last inequality.Recall that for each candidate arm x i,t ∈ X t , its corruption-free expected reward is generated by an unknown reward mapping function h(•). Following existing neural bandit approaches, we use a neural network f (•) to approximate h(•) for estimating arm rewards. Consistent with the main text and R-NeuralUCB, we consider the network f (•; θ) to be a fully connected (FC) network with depth L ≥ 2 and width m ∈ N + :f (x; θ) := √ mθ L σ(θ L-1 σ(θ L-2 . . . σ(θ 1 x))),where σ(•) denotes the ReLU activation function, and the trainable weight matrices are θ 1 ∈ R m×d , θ l ∈ R m×m for 2 ≤ l ≤ L -1, and θ L ∈ R 1×m . For simplicity, we also denote the vectorized parameters as θ := [vec(θ 1 ) ⊺ , vec(θ 2 ) ⊺ , . . . , vec(θ L )] ⊺ ∈ R p , with dimensionality p and randomly initialized parameters θ 0 . Similar to R-NeuralUCB, we also define g(x; θ) = vec(∇ θ f (x; θ)) ∈ R p as the vectorized network gradients, for input x and parameters θ.E.1 NeuralUCB-WGD: Neural-UCB with Weighted GD Then, we introduce the workflow of our base algorithm NeuralUCB-WGD (Algorithm 3), which stands for Neural-UCB with Weighted GD. Here, NeuralUCB-WGD can be considered as a simplified version of R-NeuralUCB, where all the candidate arms X t 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 on the samples with low uncertainty for a stable training process. Observe candidate arms X t = {x i,t } i∈[K] .for each arm x i,t ∈ X t do 6:Calculate its benefit score U (x i,t ), based on reward estimation f (x i,t ; θ i,t-1 ) and the UCB-type exploration score for arm x i,t , (E.1).end for 8:Recommend arm based on benefit scores x t = arg max xi,t∈Xt U (x i,t ) .Receive arm reward r t , and update the records, such that P t = P t-1 ∪ {(x t , r t )}. Then, save the corresponding weight for chosen arm x t , as w t = min{1, α/∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 }.10:Update the gradient covariance matrix Γ t = Γ t-1 + w t • g(x t ; θ t-1 ) • g(x t ; θ t-1 ) ⊺ /m.Starting from random initialization θ 0 , update the network parameters to θ t , based on J iterations of Gradient Descent and training data P t . 12: end for Arm Selection. In each round t ∈ [T ], after observing the candidate arms X t for selection, we calculate the reward estimation and the UCB score for arm selection (lines 5-7, Algorithm 3). Similar to R-NeuralUCB, in terms of the arm selection (line 8, Algorithm 3), we determine the chosen arm x t ∈ X t with the highest benefit score, by x t = arg max xi,t∈Xt U (x i,t ) . Here, with the NTK norm parameter S > 0 and the probability at least 1 -δ given probability parameter δ ∈ (0, 1), we formulate the benefit score U (x i,t ), along with a UCB-type exploration strategy (motivated by Lemma F.1), asU (x i,t ) = f (x i,t ; θ t-1 ) + O ν log det(Γ t-1 ) det(λI) -2 log(δ) + λ 1/2 S • ∥g(x i,t ; θ t-1 )/ √ m∥ Γ -1 t-1 (E.1)where θ t-1 refer to network parameters in round t before GD, which have been trained with received records P t-1 , and λ > 0 is regularization parameter. Different from conventional neural bandit works, our gradient covariance matrix is defined as Γ t-1 = λI + τ ∈[t-1] w τ • g(x τ ; θ τ -1 )g(x τ ; θ τ -1 ) ⊺ /m. Here, to quantify the arm uncertainty level, inspired by [42] , we define the sample weight as w τ = min{1, α/∥g(x τ ; θ τ -1 )/ √ m∥ Γ -1 τ -1} based on the gradient vector g(x τ ; θ τ -1 ) = vec ∇ θ f (x τ ; θ τ -1 ) ∈ R p , and it is scaled by a tunable parameter α > 0. Notice that the arm weight w τ is inversely proportional to our UCB-type exploration score in (E.1). Since the UCB-based exploration score can be considered to quantify reward estimation uncertainty levels [24, 72, 86] , we thus assign small weights to training samples with high uncertainty. Recall that in (1), we apply ν to characterize the random noise ϵ. Similar to R-NeuralUCB, when this value is unknown, we alternatively deem ν ≥ 0 as a tunable exploration parameter to control the exploration intensity analogous to existing works (e.g., [86] ).After receiving the reward r t for the chosen arm x t , we update the records to P t . The arm context x t and its received reward r t are added to the collection P t , along with their weight ). Here, θw t = min{1, α/∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 } (linet , j ∈ [J] are the parameters after the j-th GD iteration, starting from randomly initialized ones θ (0) t = θ 0 , and η > 0 refers to 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 L 2 loss function, we alternatively define the weighted loss function asL(P; θ) = (xτ ,rτ )∈P w τ 2 f (x τ ; θ) -r τ 2 + mλ 2 ∥θ -θ 0 ∥ 2 2where λ > 0 is the regularization parameter as in (E.1), and we have previously defined sample weights w τ , τ ∈ [t] associated with each chosen arm-reward pair (x τ , r τ ) ∈ P t . In summary, the intuition is that, when defining the loss function for the received records P t = {x τ , r τ } τ ∈[t] up to round t, 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-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 a stable and robust GD training process.For the theoretical analysis, different from that of R-NeuralUCB (Subsection 5.1), we focus on the case where the corruption level C is known, a common setting in existing works [16, 42, 76, 17] . This assumption allows us to appropriately select the parameter α in Algorithm 3 to achieve a tighter regret bound. Additionally, we briefly discuss potential outcomes if C is unknown. Recall that our objective (2) is to minimize the overall pseudo-regret in terms of the corruption-free expected reward over a finite horizon of T rounds: R(T ) =T t=1 E[ r * t -r t ], where E[ r t ] = h(x t ) denotes the expected corruption-free reward from the chosen arm x t , and E[ r * t ] = max xi,t∈Xt [h(x i,t )] 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-free model f (•; θ), we derive the confidence ellipsoid around its parameters θ, which serves as a proxy for updating the confidence ellipsoid around the trained corrupted model parameters θ. With the updated confidence ellipsoid and concentration results, we then finalize the regret upper bound. Here, without carefully designing the arm weights w τ , τ ∈ [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.1 provides a bound on the cumulative pseudo-regret for NeuralUCB-WGD.Theorem E.1. Given the finite horizon T ∈ N + , denote S ≥ 2 h⊺ H-1 h. Suppose probability parameter δ ∈ (0, 1), network width m ≥ Ω(poly(T, L, C, λ-1 0 , λ -1 , S -1 ) • log(1/δ)), η ≤ O((T mL + mλ) -1 ), J ≥ O(T L/λ), and λ ≥ S -2 . Let f (•) be the L-layer FC network with width m, and set α = 1/C without the prior knowledge of d. Then, with probability at least 1 -δ over random initialization, NeuralUCB-WGD achieves the regret upper bound:R(T ) ≤ O dT • O ν d -2 log(δ) + λ 1/2 S + O C d log(1 + T K/λ) + O C d • λ 1/2 S + O C d • ν d log(1 + T K/λ) -2 log(δ)The proof of Theorem E.1 is provided in Appendix F. The first term on the RHS represents the corruption-independent regret upper bound, which matches the bound O( d √ T ) in corruptionfree neural bandit studies [86, 84] . For terms that depend on the corruption level C, we obtain O(C dλ 1/2 S + C d 3/2 ) by omitting logarithmic terms. When aligning the definition of information gain [16] with the effective dimension d, our results are consistent with the latest kernelized bandit research in terms of the horizon T and effective dimension d, given the NTK-induced RKHS and an indefinite arm space (Corollary 7 in [16] ). Additionally, we can bound the NTK norm term S by a constant if h(•) 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 [86] , we quantify the impact of corruption by deriving a new confidence ellipsoid around the corrupted parameters θ t-1 , ensuring that the corruption-related terms remain independent of the non-logarithmic T term.Inspired by [42] , when C is unknown to the learner, an estimated corruption level C > 0 can be utilized based on prior knowledge of the adversary. In this case, we can set the scaling parameter α = 1/ C. If the actual C ≤ C, then the corresponding regret upper bound in Theorem 5.6 still holds. Conversely, if C > C, the regret bound will no longer hold, leading to a trivial upper bound of R(T ) ≤ O(T ), similar to existing works (e.g., [42] ). Here, practically, one approach is to set C = √ T . For C ≤ √ T , the overall regret is then bounded by O( d 3/2 √ T ), which matches [16] and improves upon O( dT ) from [15] . When C > √ T , our trivial regret bound of O(T ) also aligns with the state-of-the-art kernelized method [15] with unknown C, which has a bound ofO( d √ T + C d √ T ) =⇒ O( d √ T + dT ).Thus, the regret bound for NeuralUCB-WGD comparably matches the latest theoretical results from the kernelized bandit research [16, 15] under the indefinite arm space setting. While the problem definition of neural contextual bandits (1) is more general and reduce restrictions from the reward mapping function aspect, it is also significantly distinct from the problem definitions of linear or kernelized bandits, which makes lots of techniques from existing works on tackling adversarial corruptions (e.g., [42, 16] ) infeasible.By definition in (1) , recall that we aim to minimize the pseudo-regret for T rounds, denoted byR(T ) = T t=1 h(x * t ) -h(x t ) = T t=1 R t = T t=1 ⟨g(x * t ; θ 0 ), θ * -θ 0 ⟩ -⟨g(x t ; θ 0 ), θ * -θ 0 ⟩where x t is the chosen arm and x * t = arg max xi,t∈Xt [h(x i,t )] being the optimal arm in round t. The third equality is due to Lemma C.1. Then, we denote f (•) as the bandit model we currently possess, which is trained with corrupted records P t-1 up to round t, and also suppose an imaginary corruption-free bandit model accordingly, which is trained with corruption-free records P t-1 . The corresponding model parameters of f (•) will be denoted as θ, while the parameters of the imaginary corruption-free model will be denoted as θ.Proof sketch. To begin with, we first analyze the single-round pseudo-regret R t for t ∈ [T ], where the cumulative regret is given by R(T ) = t∈[T ] R t . Here, we demonstrate that the single-round regret with corruption can be upper bounded by using the updated confidence ellipsoid (Lemma F.1) around the corrupted network parameters θ t . Since we cannot directly apply the self-regularized martingale concentration results from existing studies [1, 86] , we instead derive updated concentration results that account for adversarial corruptions, as shown in Lemma F.2. These results are then combined to 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 α = 1/C yields the desired regret bound.Following analogous approach as the proof of Lemma 5.3 in [86] , we can transform the regret for a single round t ∈ [T ] toR t = ⟨g(x * t ; θ 0 ), θ * -θ 0 ⟩ -⟨g(x t ; θ 0 ), θ * -θ 0 ⟩ ≤ ⟨g(x * t ; θ t-1 ), θ * -θ 0 ⟩ -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) ≤ max θ∈Ct-1 ⟨g(x * t ; θ t-1 ), θ -θ 0 ⟩ -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ).where the first inequality is by the gradient difference in Lemma G. . Here, with γ t-1 being the corresponding corruption-free radius term, we haveγ t-1 = γ t-1 + α • C + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -2/3 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 ).Then, based on the arm pulling mechanism, we denote the estimated arm benefit score as U (x i,t ) = f (x i,t ; θ t-1 ) + γ t-1 • g(x i,t ; θ t-1 ) ⊺ Γ -1 t-1 g(x i,t ; θ t-1 ), and we also define its alternative based on the confidence ellipsoid asV (x i,t ) = g(x i,t ; θ t-1 ), θ t-1 -θ 0 + γ t-1 • g(x i,t ; θ t-1 ) ⊺ Γ -1t-1 g(x i,t ; θ t-1 )/m = max θ∈Ct-1 g(x i,t ; θ t-1 ), θθ 0 based on the confidence interval C t-1 induced by the corrupted parameters θ t-1 . Regarding their distance, we can further derive |U (x i,t ) -V (x i,t )| ≤ O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) by applying Lemma G.5, as well as the fact that f (x; θ 0 ) = 0 based on random initialization. It then leads toR t ≤ max θ∈Ct-1 ⟨g(x * t ; θ t-1 ), θ -θ 0 ⟩ -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) = V (x * t ) -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) ≤ U (x * t ) -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) ≤ U (x t ) -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) ≤ V (x t ) -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) ≤ max θ∈Ct-1 ⟨g(x t ; θ t-1 ), θ -θ 0 ⟩ -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 )where the third inequality is due to the arm pulling mechanism. The second and the fourth inequality is due to the distance between V (•) and U (•). Since we have θ * ∈ C t-1 , by Holder's inequality, it will further lead toR t ≤ max θ∈Ct-1 ⟨g(x t ; θ t-1 ), θ -θ 0 ⟩ -⟨g(x t ; θ t-1 ), θ * -θ 0 ⟩ + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) ≤ max θ∈Ct-1 ∥g(x t ; θ t-1 )∥ Γ -1 t-1 • ∥θ -θ 0 ∥ Γt-1 + ∥g(x t ; θ t-1 )∥ Γ -1 t-1 • ∥θ * -θ 0 ∥ Γt-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) ≤ 2γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 )where the last inequality is due to the definition of confidence ellipsoid C t-1 . This gives the upper bound for our single-round regret.On the other hand, based on the conclusion from Subsec. F.1, the cumulative regret upper bound can be transformed toR(T ) = T t=1 h(x * t ) -h(x t ) = T t=1 R t ≤ T t=1 2 • min γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 , 1 + O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) + O(m -1/6 log(m)t 2/3 λ -2/3 L 3 ) ≤ T t=1 2 • min γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 , 1 + O(1)where the last inequality is 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 haveT t=1 2 • min γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 , 1 ≤ 2γ T • dT log(1 + T K/λ) + (1 + γ T α ) • d log(1 + T K/λ) = d log(1 + T K/λ) + 2γ T • dT log(1 + T K/λ) + 1 α • d log(1 + T K/λ) ≤ d log(1 + T K/λ) + dT log(1 + T K/λ) + 1 α • d log(1 + T K/λ) • 2 γ t-1 + 2α • C + 2(1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -2/3 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 ) ≤ d log(1 + T K/λ) + dT log(1 + T K/λ) + 1 α • d log(1 + T K/λ) • ν d log(1 + T K/λ) -2 log(δ) + λ 1/2 S + 2α • C + 2(1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ))+ O(Cm -2/3 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 )≤ dT log(1 + T K/λ) + d α log(1 + T K/λ) • O ν d log(1 + T K/λ) -2 log(δ) + λ 1/2 S + 2αC + O(1)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 as Lemma 5.2 in [86] , and the last inequality is due to the sufficiently large network width m as mentioned in Theorem E.1, as well as the sufficient number of GD iterations J = O(T L/λ).Discussion on the value of α. Here, notice that we have the tunable parameter α > 0 nested in the regret bound. Taking some more steps, we can haveEQUATION≤ dT log(1 + T K/λ) + 1 α • d log(1 + T K/λ) • O ν d log(1 + T K/λ) -2 log(δ) + λ 1/2 S + 2α • C ≤ O dT + 1 α • d • ν d -2 log(δ) + λ 1/2 S + 2α • C ≤ O dT + 1 α • d • ν d -2 log(δ) + λ 1/2 S + O αC dT + C dSince we have no prior knowledge of effective dimension d, we can set α = 1 C . It will then lead toT t=1 2 min γ t-1 • ∥g(x t ; θ t-1 )/ √ m∥ Γ -1 t-1 , 1 ≤ O dT + 1 α • d • ν d -2 log(δ) + λ 1/2 S + O αC dT + C d ≤ O dT • ν d -2 log(δ) + λ 1/2 S + O C d + C d • ν d -2 log(δ) + λ 1/2 S .Finally, summing up all the results above will give the conclusion.Lemma F.1. With the notation and conditions in Theorem E.1, train the network parameters θ t-1 based on received records P t-1 . The confidence ellipsoid around the corrupted network parameters θ t-1 can be defined asC t-1 = θ : ∥θ -θ t-1 ∥ Γt-1 ≤ γ t-1 / √ mwhere we have the unknown parameter θ * ∈ C t-1 , and we denoteγ t-1 = γ t-1 + α • C + (1 -ηmλ) J/2 t/λ + O(m -1/6 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)) + O(Cm -2/3 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -1/6 log(m)t 7/6 λ -13/6 L 9/2 )Proof. The proof follows an analogous approach as in Lemma C.12. For the imaginary corruption-free parameters θ t-1 , which are trained on corruption-free records P t-1 , we can construct the confidence intervalC t-1 := {θ : ∥θ -θ t-1 ∥ Γt-1 ≤ γ t-1 / √ m, γ t-1 > 0}, such that the unknown θ * in Lemma C.1 satisfies θ * ∈ C t-1 .However, since we do not possess θ t-1 , we need to alternatively derive the confidence ellipsoid C t-1 around the possessed corrupted parameters θ t-1 , such that θ * ∈ C t-1 .With the ellipsoid center θ t-1 as well as the weighted gradient covariance matrix Γ t-1 = λI + τ ∈[t-1] w τ • g(x τ ; θ τ -1 ) • g(x τ ; θ τ -1 ) ⊺ /m, we need to derive the corresponding radius. Recall that w τ is the sample weight associated with chosen arm x τ . Here, we first recall some preliminaries that ∥Γ t-1 -Γ t-1 ∥ F ≤ O(m -1/6 log(m)L 4 t 7/6 λ -1/6 ) due to Lemma G.6, as well as ∥θ t-1θ t-1 ∥ 2 ≤ O( t/(mλ)) due to Lemma G.3.Next, as we already have ∥θ -θ t-1 ∥ Γt-1 ≤ γ t-1 / √ m, we proceed to transform the objective to∥θ * -θ t-1 ∥ Γt-1 ≤ ∥θ * -θ t-1 ∥ Γt-1 + ∥ θ t-1 -θ t-1 ∥ Γt-1 ≤ ∥θ * -θ t-1 ∥ Γt-1 + ∥ θ t-1 -θ t-1 ∥ Γt-1 ≤ ∥θ * -θ t-1 ∥ Γt-1-Γt-1+ Γt-1 + ∥ θ t-1 -θ t-1 ∥ Γt-1 ≤ ∥θ * -θ t-1 ∥ Γt-1 + ∥θ * -θ t-1 ∥ Γt-1-Γt-1 + ∥ θ t-1 -θ t-1 ∥ Γt-1 ≤ γ t-1 / √ m + ∥ θ t-1 -θ t-1 ∥ Γt-1 + O( t/(mλ))• O(m -1/6 log(m)L 4 t 7/6 λ -1/6 ) ≤ γ t-1 / √ m + ∥ θ t-1 -θ t-1 ∥ Γt-1 + O(m -2/3 log(m)L 4 t 13/6 λ -2/3 ).For the second term on the RHS, we first define the gradient-based regression parameters asEQUATIONEQUATIONt-1 = τ ∈[t-1] w τ • g(x τ ; θ 0 ) • r τ / √ m,Then, with the triangular inequality, we can proceed to have∥ θ t-1 -θ t-1 ∥ Γt-1 ≤ ∥ θ t-1 -θ 0 -(Γ (0) t-1 ) -1 b (0) t-1 / √ m + (Γ (0) t-1 ) -1 b (0) t-1 / √ m + θ 0 -θ t-1 ∥ Γt-1 ≤ ∥θ t-1 -θ 0 -(Γ (0) t-1 ) -1 b (0) t-1 / √ m∥ Γt-1 + ∥ θ t-1 -θ 0 -(Γ (0) t-1 ) -1 b (0) t-1 / √ m∥ Γt-1 ≤ ∥θ t-1 -θ 0 -(Γ (0) t-1 ) -1 b (0) t-1 / √ m∥ Γt-1 + ∥ θ t-1 -θ 0 -(Γ (0) t-1 ) -1 b (0) t-1 / √ m∥ Γt-1 + m -1 ∥(Γ (0) t-1 ) -1 • ( τ ∈[t-1]w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 .(F.1)Bounding the first two term on the RHS of Inequality F.1. 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 ∈ [J]) with Θ (0) = θ 0 , asΘ (j+1) = Θ (j) -η • J (0) • W • [J (0)] ⊺ (Θ (j) -θ 0 ) -y + mλ(Θ (j) -θ 0 )where the Jacobian matrix J (0) := g(x 1 ; θ 0 ), g(x 2 ; θ 0 ), . . . , g(x t-1 ; θ 0 ) ∈ R p×(t-1) , and vector y ∈ R t-1 contains the received arm rewards r τ , τ ∈ [t -1], while matrix W ∈ R (t-1)×(t-1) is the diagonal matrix that contains sample weights w τ , τ ∈ [t -1]. We have its norm ∥W∥ 2 ≤ 1 by definition. Here, the above sequence is expected to solve the following problem with gradient descentmin Θ L(Θ) = τ ∈[t-1] w τ 2 • [J (0) ] ⊺ τ (Θ -θ 0 ) -r τ 2 2 + 1 2 • mλ • Θ -θ 0 2 2 .As a result, following an analogous approach as in Lemma C.4 in [86] , we can have ∥Θ (j) -θ 0 -(Γ m∥ 2 ≤ (1-ηmλ) J/2 t/(mλ)+O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1+ t/λ)).Similarly, for the second term in Inequality F.1, we also can apply a comparable approach by solving the problem:min Θ L(Θ) = τ ∈[t-1] w τ 2 [J (0) ] ⊺ τ (Θ -θ 0 ) -r τ 2 2 + 1 2 mλ • Θ -θ 0 2 2 ,and constructing the corresponding auxiliary sequence. Following an analogous approach, it will lead to a similar bound for the second term, such that ∥ θ t-1 -θ 0 -(Γ (0) t-1 ) -1 b (0)t-1 / √ m∥ 2 ≤ (1 -ηmλ) J/2 t/(mλ) + O(m -2/3 log(m)L 7/2 t 5/3 λ -5/3 (1 + t/λ)).Bounding the third term on the RHS of Inequality F.1. Afterwards, for the third term on the RHS, we first havem -1 • ∥(Γ (0) t-1 ) -1 • ( τ ∈[t-1] w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 ≤ m -1 ∥(Γ t-1 ) -1 ( τ ∈[t-1] w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 + m -1 ∥ (Γ t-1 ) -1 -(Γ (0) t-1 ) -1 • ( τ ∈[t-1] w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 ≤ m -1 ∥(Γ t-1 ) -1 ( τ ∈[t-1] w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 + m -1 ∥(Γ t-1 ) -1 Γ t-1 -Γ (0) t-1 (Γ (0) t-1 ) -1 • ( τ ∈[t-1] w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 ≤ m -1 ∥(Γ t-1 ) -1 ( τ ∈[t-1]w τ • g(x τ ; θ 0 ) • c τ )∥ Γt-1 + O(Cm -2/3 log(m)t 7/6 λ -13/6 L 9/2 )≤ m -1 ∥(Γ t-1 ) -1 ( τ ∈[t-1]w τ • g(x τ ; θ τ -1 ) • c τ )∥ Γt-1 + O(Cm -2/3 log(m)t 7/6 λ -13/6 L 9/2 )+ m -1 ∥(Γ t-1 ) -1 ( τ ∈[t-1] w τ • (g(x τ ; θ τ -1 ) -g(x τ ; θ 0 )) • c τ )∥ Γt-1 ≤ m -1 ∥(Γ t-1 ) -1 ( τ ∈[t-1] w τ • g(x τ ; θ τ -1 ) • c τ )∥ Γt-1+ O(Cm -7/6 log(m)t 1/6 λ -7/6 L 7/2 ) + O(Cm -2/3 log(m)t 7/6 λ -13/6 L 9/2 ) 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, α/∥g(x τ ; θ τ -1 )/ √ m∥ Γ -1 τ -1} for each chosen arm x τ . In this case, we can further havem -1/2 ∥(Γ t-1 ) -1 ( τ ∈[t-1] w τ • g(x τ ; θ τ -1 ) • c τ )/ √ m∥ Γt-1 = m -1/2 ∥ τ ∈[t-1] w τ • g(x τ ; θ τ -1 ) • c τ / √ m∥ (Γt-1) -1 ≤ m -1/2 τ ∈[t-1] w τ |c τ | • ∥g(x τ ; θ τ -1 )/ √ m∥ (Γt-1) -1 ≤ m -1/2 τ ∈[t-1] w τ |c τ | • ∥g(x τ ; θ τ -1 )/ √ m∥ (Γτ-1) -1 ≤ α • C/ √ m.where the first inequality is by applying the Cauchy-Schwartz inequality, while the second inequality is due to Γ τ -1 ⪯ Γ t-1 and Lemma G.8. The last inequality is by the definition of corruption level C. Finally, summing up all the results will give the desired lemma.Recall that we have the weighted gradient covariance matrix Γ t-1 = λI+ τ ∈[t-1] w τ •g(x τ ; θ τ -1 )• g(x τ ; θ τ -1 ) ⊺ /m, where g(x τ ; θ τ -1 ) is the vectorized gradient vector, and w τ ≤ 1 refers to the sampled associated with chosen arm x τ .By existing works [1, 86] , we can have the self-normalized martingale such that Following the previous approach, we define the auxiliary matrix Γ w<1 t-1 = λI + τ ∈T (t-1) w=1 w τ • g(x τ ; θ τ -1 ) • g(x τ ; θ τ -1 ) ⊺ /m. Here, since we also have Γ w<1 t-1 ⪯ Γ t-1 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 g ′ (x τ ; θ τ -1 ) = √ w τ • g(x τ ; θ τ -1 ), τ ∈ T (t-1)w=1 . In this case, the auxiliary gradient covariance matrix can be alternatively represented as Γ w<1 t-1 = λI + τ ∈T (t-1) w=1 g ′ (x τ ; θ τ -1 ) • g ′ (x τ ; θ τ -1 ) ⊺ /m, and the RHS will become t∈T (T ) w<1 min γ t-1 • g(x t ; θ t-1 )/ √ m Γ -1t-1 , 1 ≤ (1 + γ T α ) • t∈T (T ) w<1g ′ (x t ; θ t-1 )/ √ m 2 (Γ w<1 t-1 ) -1 , 1≤ (1 + γ T α ) • d log(1 + T K/λ).where the last inequality is by applying Lemma G.7 and Lemma C.2. Summing up the results will finish the proof.G Lemmas for Over-parameterized FC Neural Networks where I(•) is the indicator function. Afterwards, the corresponding gradients will become∇ θ l f (x; θ) = [h l-1 θ L ( L-1 τ =l+1 D τ θ τ )] ⊺ , l ∈ [L -1] h ⊺ L-1 , l = L. (G.2)Lemma G.1. There exists a positive constant C > 0 such that with probability at least 1 -δ, if m ≥ CT 4 L 6 log(T 2 L/δ)/λ 4 for each arbitrary x τ ∈ τ ∈[t] X τ , there exists a set of parameters θ * such that with the neural network parameters θ t-1 trained on {x τ } t-1 τ =1 , we have |⟨g(x; θ 0 ), θ * -θ 0 ⟩ -⟨g(x; θ t-1 ), θ * -θ 0 ⟩| ≤ O(Sm -1/6 log(m)t 1/6 λ -1/6 L 2/7 ) where parameters θ * satisfy ∥θ * -θ 0 ∥ ≤ S/ √ m, S > 0 as shown in Lemma C.1.Proof. This lemma is based on Lemma C.1. Here, our objective can be reformed into |⟨g(x; θ 0 ), θ * -θ 0 ⟩ -⟨g(x; θ t-1 ), θ * -θ 0 ⟩| = ∥θ * -θ 0 ∥ 2 • g(x; θ 0 ) -g(x; θ t-1 )≤ S/ √ m • g(x; θ 0 ) -g(x; θ t-1 )≤ O(Sm -1/6 log(m)t [45] ). Let A, B be Hermitian matrices of the same shape, and suppose they are positive semi-definite. Then, we have A ⪰ B iff A -1 ⪯ B -1 .• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: 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.

Reviews: review: paper_summary: paper_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
consideration. 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.
strength_weakness: strength_weakness: 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?
questions: 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: limitations: Yes
paper_summary: paper_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:
- 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
- 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.
- Experiments show the proposed algorithm has a lower cumulative regret than Neural-UCB and other baselines across different datasets and reward corruption types.
strength_weakness: strength_weakness: - 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:
  - Firstly, R-NeuralUCB requires different neural network model weights for different arms, so R-NeuralUCB is very expensive when $K$ is high. 
  - Secondly, for each time $t \in [T]$, R-NeuralUCB requires additionally optimizing the Context-aware GD objective function in Eq. 5 $K$ times. 
  - 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.
- The proposed algorithm requires to define some non-trivial hyper-parameters such as $\alpha$ in Eq. 4 and $\lambda$ in Eq. 5.
- 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.
- 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.
- 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.
questions: 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$?
2. 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?
3. 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)?
4. 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?
5. 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).
6. 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$?

References:

[1] Zhou et al., Neural Contextual Bandits with UCB-based Exploration, ICML, 2020.

[2] Xu et al., Neural Contextual Bandits with Deep Representation and Shallow Exploration, ICLR, 2022.

[3] Bogunovi et al., Corruption-Tolerant Gaussian Process Bandit Optimization, AISTATS, 2020.

[4] Zhang et al., Contextual Gaussian Process Bandits with Neural Networks, NeurIPS, 2023.
limitations: limitations: Please see my comments on the Weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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$.
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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$.

3. 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.


[1]  He et al. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions Neurips 2022
questions: questions: See Weaknesses
limitations: limitations: The authors have addressed the limitations and potential societal impact of their work.

Comments: title: Thank you for the review and feedback!
Thank you for the review!
Thank you for the feedback!
comment: Dear Reviewer 1FL3,

Thank you again for your insightful comments and questions, and we will definitely integrate our discussions into the manuscript as readers' reference. Meanwhile, please also kindly let us know if you have any further concerns or questions. We will be more than glad to provide additional explanations in a timely manner. Thank you again!

Best regards,

Authors
Thanks for your detailed responses, which are really helpful. I will keep my scores.
Dear Reviewer Fhvw,

Thank you again for your insightful review and comments, and we will definitely include detailed discussions related to computational efficiency to our final manuscript. Thanks again.

Best regards,

Authors
Thank you for the detailed response. I will keep my score. I hope the authors will include a discussion of computational efficiency in the final version.
Dear Reviewer MEPN,

We would like to sincerely thank you again for your valuable and insightful comments on improving our paper. We will definitely integrate these detailed discussions regarding computational efficiency, parameter selection, and theoretical analysis gap to our final manuscript. Thank you again for your invaluable review and feedback.

Best regards,

Authors
I thank the authors for the detailed rebuttal. I appreciate your explanation and additional results. I keep my original rating for this paper. I hope the authors can add a detailed discussion regarding computational efficiency in the final version. Additionally, I hope the authors can add more detail to the gap between choosing the exploration rate in the theorem and the practical algorithm in Q5. I understand this is a gap in the literature on neural bandits in general, but I believe it is worth discussing to help the community understand the gap between theory and experiments in this direction. Good luck!