Robust Neural Contextual Bandit against Adversarial Corruptions

We would like to sincerely thank the reviewer for your valuable questions and comments. Given the page limit of 6000 characters, we will try our best to provide our detailed response in the form of Q&A. Please also see our manuscript for cited papers. Thank you!

Q1: Overall discussion on computational efficiency?

Please kindly refer to our "Global Response" for complementary discussions.

To reduce the computational cost for obtaining arm-specific network parameters (line 9, Algorithm 1) in practice, for our experiments, we apply the warm-start GD strategy to strike a good balance between performances and computational costs. Pseudo-code and detailed descriptions are in Appendix Subsection B.6 due to page limit.

In round $t\in \\{3, \dots, T\\}$, for each candidate arm $x_{i, t}, i\in [K]$, we can acquire its arm-specific parameters $\theta_{i, t-1}$ by fine-tuning existing trained parameters $\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\theta_{0}$ and training with a large number of samples. The intuition is inspired by meta-learning works [Finn et al.], where we consider each candidate arm as a "task". In this case, for round $t$, we can start from previously trained model parameters $\theta_{t-2}$, and adapt $\theta_{t-2}$ to each candidate arm (task), with a small number of training samples to obtain arm(task)-specific parameters.

This helps R-NeuralUCB (1) reduce computational costs of calculating arm weights for GD, and keep inference time relatively stable across horizon $T$, since we apply a fixed number of samples for adaptation; (2) reduce GD iterations needed, as starting from $\theta_{0}$ will require more GD iterations for model convergence.

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

Please see our "Global Response" PDF file for added experiments: (1) With experiments on warm-start vs. restarting from $\theta_{0}$ (Figure 1) given the same number of training (adaptation) samples, we see the warm-start process can improve performances. (2) With experiments based on increased number of arms $K$ ($K=50, 100$, Figure 2), we see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable.

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

Q2: Relationship with the lower bound in (He et al., 2022)?

First, we would like to first recall that Theorem 4.12 of [35] relies on Assumption 2.1 of [35], which formulates a learning problem under linear contextual bandit settings. Then, in our Theorem 5.6, when $C=0$, we have the corruption-free regret of $\tilde{\mathcal{O}}(\tilde{d}\sqrt{T} + S\sqrt{\tilde{d}T})$. In this case, after setting $C = \Omega(R_{T}/d)$, we will end up with a regret bound of $\tilde{\mathcal{O}}\left( (\tilde{d}^{2}\sqrt{T} + S\tilde{d}^{3/2}\sqrt{T}) \cdot C \beta^{-1}d^{-1} \right)$. Here, we note that with the proof flow of Theorem 4.12 in [35] and learning problem specified by Assumption 2.1 of [35], our effective dimension term $\tilde{d}^{2}$ can possibly depend on horizon $T$, and grow along with $T$ [22]. As a result, although the regret bound only contains $\sqrt{T}$ terms, the overall order of regret bound can be equal or greater than $\mathcal{O}(T)$ due to effective dimension $\tilde{d}^{2}$, as discussed in [22]. This is distinct from linear bandits works, where regret bounds generally only consist of horizon $T$ and other $T$-independent terms, such as context dimension $d$ and fixed $T$-independent linear parameter norm $\|\theta^{*}\|_{2}$. Therefore, our Theorem 5.6 will not contradict with Theorem 4.12 of [35].

Meanwhile, we also note that for stochastic neural bandit works, the effective dimension term $\tilde{d}$ (or information gain for kernelized bandits [65,12]) is generally inevitable [76,74,7,43], since we need to bridge over-parameterized networks with the NTK-based regression model. Comparably, kernelized bandits [12,65,24] will also generally involve similar terms as costs of modeling the unknown non-linear reward mapping function.

We appreciate the reviewer for your question. For readers' reference, we have included above discussions to Appendix Subsection B.7, as the supplement to our current discussion of the lower bound.

Q3: How to tune parameter $\alpha$ to satisfy the requirements of $\kappa$?

We first recall that in round $t\in [T]$, we have arm weights $w\_{i, t}^{(\tau)}, \tau\in [t-1], i\in [K]$. Based on line 184, we can also denote $w\_{i, t}^{(\tau)} = \min\\{ 1,\alpha\cdot \textsf{frac}\_{\tau}(x\_{i, t}; \mathcal{X}\_{t}, \bar{\Sigma}\_{t-1}) \\}$. Here, instead of deeming $\alpha$ as a fixed value across horizon $T$, we can consider $\alpha$ to be varying across different rounds, denoted by $\alpha\_{t}, t\in [T]$. With $\textsf{frac}\_{t}^{\textsf{min}} = \min\_{i\in [K], \tau\in [t-1]}[ \textsf{frac}\_{\tau}(x\_{i, t}; \mathcal{X}\_{t}, \bar{\Sigma}\_{t-1}) ]$, we can set each $\alpha\_{t} = \kappa^{2} / \textsf{frac}\_{t}^{\textsf{min}}, \kappa\in (0, 1)$. In this way, we can consequently have $\min\\{w\_{i, t}^{(\tau)}\\}\_{i\in [K], \tau\in [t-1]} = \kappa^{2}, \forall t\in [T]$.

To improve the paper presentation, we have also added above explanations to the manuscript for readers' reference.

We would like to sincerely thank the reviewer for your valuable questions and comments. Given the page limit of 6000 characters, we will try our best to provide our detailed response in the form of Q&A. Please also see our manuscript for cited papers. Thank you!

Q1: Overall discussion on computational efficiency? Performance with large $K$?

Please see our "Global Response" PDF file for added experiments. (1) With experiments on warm-start vs. restarting from $\theta_{0}$ given the same number of training (adaptation) samples (Figure 1), we see the warm-start process can improve performances. (2) With experiments based on increased number of arms $K$ ($K=50, 100$, Figure 2), we see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable.

In practice, for our experiments, we can adopt the warm-start GD process (details and pseudo-code are in Appendix Subsection B.6) to reduce the computational cost, in terms of deriving the arm-specific network parameters (line 9, Algorithm 1). In round $t\in \\{3, \dots, T\\}$, for each candidate arm $x_{i, t}, i\in [K]$, we can acquire its arm-specific parameters $\theta_{i, t-1}$ by fine-tuning existing trained parameters $\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\theta_{0}$ with a large number of samples. Similar ideas are also applied by other bandit-related works (e.g., [9]). The intuition is inspired by meta-learning [Finn et al.] where we consider each candidate arm as a "task". In this case, for round $t$, we can start from previously trained model parameters $\theta_{t-2}$, and adapt $\theta_{t-2}$ to each candidate arm (task) with a small number of training samples to obtain arm(task)-specific parameters. This also reduces our computational costs of calculating arm weights for GD, and keep the inference time relatively stable across rounds.

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

Therefore, we adopt the following approaches to strike a good balance between model performance and computational costs:

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

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

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

Q2: Is it possible that Neural-UCB and Neural-TS also have sub-linear regret under adversarial attacks?

We agree with the reviewer that it is interesting and important to investigate the regret bound of vanilla neural bandit algorithms, in order to better understand the benefit of proposed methods. In particular, to offer some insights on regret bound of Neural-UCB, one possible route is to follow an analogous approach as the regret analysis of NeuralUCB-WGD. On the other hand, regarding Thompson Sampling based approaches, their analysis can be significantly different from our UCB-based methods, where we consider UCB-based analysis in this paper. Therefore, we consider the regret analysis of Neural-TS under corruptions as a part of future works.

Here, the key idea is to quantify the impact of adversarial corruptions upon the confidence ellipsoid around trained parameters. By following the derivations in Lemma F.1, denoting the corruption-free confidence radius as $\tilde{\gamma}\_{t-1}$ in round $t$, we can have the corrupted confidence ellipsoid for Neural-UCB as $\mathcal{C}\_{t-1} = \\{ \theta: \\|\theta - \theta\_{t-1}\\|\_{\Gamma\_{t-1}} \leq \gamma\_{t-1} / \sqrt{m} \\}$, where $\gamma\_{t-1} = \tilde{\gamma}\_{t-1} + \mathcal{O}(CL\lambda^{-1/2})$. This result is derived by applying $w\_{\tau}=1, \tau\in [t-1]$ and the fact $\sum\_{\tau\in [t]}|c\_{\tau}| \leq C$, as well as Lemma G.2 and the initialization of the gradient covariance matrix $\Gamma$. As a result, following the proof flow of Lemma 5.3 in [76], we can have regret upper bound $\tilde{\mathcal{O}}(\tilde{d}\sqrt{T} + \sqrt{S\tilde{d}T} + CL\sqrt{\tilde{d}T/\lambda})$, which will introduce an additional $\tilde{\mathcal{O}}(\sqrt{T})$ to the corruption-dependent term. Note that although it is possible for Neural-UCB to have a sub-linear cumulative regret when $C$ is a small constant, our R-NeuralUCB and NeuralUCB-WGD can remove the direct dependency of horizon term $T$, and manage to achieve non-trivial $\tilde{\mathcal{O}}(C\tilde{d}\beta^{-1})$ and $\tilde{\mathcal{O}}(C\tilde{d}^{3/2} + C\tilde{d}\sqrt{\lambda}S)$ respectively for corruption-dependent terms. For readers' reference, we have also added above discussions to the manuscript Appendix.

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

We would like to sincerely thank the reviewer for your valuable questions and comments. Given the page limit of 6000 characters, we will try our best to provide our detailed response in the form of Q&A. Please also see our manuscript for cited papers. Thank you!

Q1: Discussion on computational efficiency? Why use warm-start GD?

Due to page limit, please kindly refer to our "Global Response" for complementary discussions.

First, we would like to mention that the warm-start GD process (detailed descriptions and pseudo-code are in Appendix Subsection B.6) here is to reduce the computational cost for calculating arm-specific network parameters (line 9, Algorithm 1) in practice.

In round $t$, for each candidate arm $x_{i, t}, i\in [K]$, we can acquire its arm-specific parameters $\theta_{i, t-1}$ by fine-tuning existing trained parameters $\theta_{t-2}$ with a small number of training samples (received arm-reward pairs), instead of obtaining $\theta_{i, t-1}$ by training from scratch, i.e., starting from randomly initialized $\theta_{0}$ with a large number of samples. The intuition is analogous to meta-learning works [Finn et al.], where we can consider each candidate arm as a "task". In this case, for round $t$, we can start from previously trained model parameters $\theta_{t-2}$, and adapt $\theta_{t-2}$ to each candidate arm (task) with a small number of training samples to obtain arm(task)-specific parameters. This helps R-NeuralUCB (1) reduce computational costs of calculating arm weights for GD, and keep inference time relatively stable across horizon $T$, since we are applying a fixed number of samples for adaptation; (2) reduce GD iterations needed, as starting from $\theta_{0}$ requires more GD iterations for model convergence.

In the "Global Response" PDF file: (1) Experiments on warm-start vs. restarting from $\theta_{0}$ (Figure 1) given the same number of training (adaptation) samples. We see the warm-start process can improve performances. (2) Experiments based on increased number of arms $K$ ($K=50, 100$, Figure 2). We see that the warm-start strategy can lead to good performances while helping the inference time stay relatively stable.

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

Q2: Additional experiments: inference speed with different model sizes? $T=15000$? Corruption-free experiments? Stochastic magnitude of corruption $C$?

Due to page limit, please kindly see our "Global Response" and attached PDF file for these experiments.

• Experiment 2 (Figure 1): Experiments with $T=15000$.

• Experiment 4 (Figure 3): Model size comparison, and line graph for inference speed.

• Experiment 5 (Figure 4): Corruption-free experiments.

• Experiment 6 (Figure 4): Stochastic magnitude of corruption experiment (increasing corruption probability).

Q3: Neural network over-parameterization?

Analogous to existing works (e.g. [76,74,7,8]), we utilize a two-layer fully-connected (FC) neural network ($L=2$) with hidden dimension $m=200$ for experiments, as in Appendix Subsection A.1.

In terms of over-parameterization, we admit that for basically all the neural bandit works with experiments (e.g. [74,43,21,6,7,8]), there exists a gap between experiments and theoretical analysis. On one hand, along with more levels $L$ and larger hidden dimension $m$, neural networks will become increasingly difficult to train, more time consuming for inference, and more demanding for computational resources. In this case, to make neural bandits practical for real applications, neural bandit works generally use an ordinary-size neural network for experiments. It is also shown that with ordinary-size neural networks, neural bandit algorithms can already achieve significant performance gains over linear and kernel methods [76,74,7,8,60]. On the other hand, from the theoretical perspective, neural networks need to be over-parameterized with $m\geq \mathcal{O}(Poly(T))$, so that they can approximate an arbitrary reward mapping function $h(\cdot)$. Meanwhile, with over-parameterization, the difference between NTK-based regression models and neural networks will be sufficiently small for regret analysis, which makes it necessary for neural bandit papers. Therefore, we adopt a two-layer FC network for experiments, while performing analysis under over-parameterization settings, as in most existing neural bandit works (e.g., [76,74,7,8,60]).

We have also include above discussions in the manuscript as reference to readers.

Q4: Can be fine-tune $\alpha$ to control $\beta$ value in the regret bound?

Based on line 184 in the manuscript, for each arm $x\_{i, t}$, we can represent its arm weight as $w\_{i, t}^{(\tau)} = \min\\{ 1,\alpha\cdot \textsf{frac}\_{\tau}(x\_{i, t}; \mathcal{X}\_{t}, \bar{\Sigma}\_{t-1}) \\}, \tau\in [t-1]$, while the minimum fraction value $\beta$ is defined as $\beta = \min\_{ t\in [T], \tau\in [t-1]} [ \min\\{ \textsf{frac}\_{\tau}(x\_{t}; \mathcal{X}\_{t}, \bar{\Sigma}\_{t-1}), \textsf{frac}\_{\tau}(\tilde{x}\_{t}; \mathcal{X}\_{t}, \bar{\Sigma}\_{t-1}) \\} ]$ (line 301). In this case, tuning parameter $\alpha$ will not directly alter the $\beta$ value, since $\beta$ only explicitly depends on the fraction term $\textsf{frac}(\cdot)$ which is determined by candidate arms. On the other hand, different $\alpha$ can correspond to distinct $\kappa^{2}$ values in Theorem 5.6, which is the round-wise minimum arm weight. This will consequently affect the regret bound, as in line 307 of Theorem 5.6.

Q5: Comments for Figure 1?

We sincerely appreciate your comments on improving the paper presentation, and we have integrated these comments into the manuscript.

Q6: Questions about implementation?

• "How arms are corrupted?": Please see "Global Response" Q3.

• "Context corruption?": Please see "Global Response" Q4.

• "How to choose $\nu$?": Please see "Global Response" Q5.

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

We would like to sincerely thank the reviewer for your valuable questions and comments. We will try our best to provide our detailed response in the form of Q&A. Please also see our manuscript for cited papers. Thank you!

Q1: The regret lower bound in terms of corruption level $C$ under neural bandit settings?

We appreciate the reviewer for your question on the regret lower bound. Recall that in our Conclusion section as well as Appendix Subsection B.7, we mention that one limitation of this paper is lacking a theoretical regret lower bound, and we consider this task as a promising future direction of our work. This is because deriving the lower bound under neural bandits with adversarial corruption settings is significantly non-trivial, and it can lead to a different line of research work by proving these results themselves.

Here, the non-linear bandit settings tend to pose extra challenges compared with linear bandit settings. For instance, for kernelized bandit works, their lower bounds will depend on kernel characteristics, such as $\Omega(C(\log(T))^{d/2})$ for the SE kernel and $\Omega(C^{\frac{v}{d+v}}T^{\frac{v}{d+v}})$ for the $v$-Mat'ern kernel [63,12]. We see that the order of corruption level $C$ and whether the lower bound is related to non-logarithmic $T$, will both depend on kernel properties.

As few restrictions are imposed for reward mapping $h(\cdot)$ for neural bandits, we will need to use regression models based on Neural Tangent Kernel (NTK) to perform theoretical analysis. In this case, without a well-established existing knowledge base for NTK (e.g., number of functions $M$ needed for the functional separateness condition [63,15] for NTK), it will require significant efforts to obtain such a lower bound for neural bandit cases, and can lead to a different line of research work by proving these results. In this case, we consider deriving such a theoretic regret lower bound as one promising and challenging future direction of this paper.