Robust Thompson Sampling Algorithms Against Reward Poisoning Attacks

## Abstract

Abstract Thompson sampling is one of the most popular learning algorithms for online sequential decision-making problems and has rich real-world applications. However, current Thompson sampling algorithms are limited by the assumption that the rewards received are uncorrupted, which may not be true in real-world applications where adversarial reward poisoning exists. To make Thompson sampling more reliable, we want to make it robust against adversarial reward poisoning. The main challenge is that one can no longer compute the actual posteriors for the true reward, as the agent can only observe the rewards after corruption. In this work, we solve this problem by computing pseudo-posteriors that are less likely to be manipulated by the attack. We propose robust algorithms based on Thompson sampling for the popular stochastic and contextual linear bandit settings in both cases where the agent is aware or unaware of the budget of the attacker. We theoretically show that our algorithms guarantee near-optimal regret under any attack strategy.

## 1 Introduction

The multi-armed bandit (MAB) setting is a popular learning paradigm for solving sequential decision-making problems (Slivkins et al., ). The stochastic and linear contextual MAB settings are the most fundamental and representative of the different bandit settings. Due to their simplicity, many industrial applications such as recommendation systems frame their problems as stochastic or contextual linear MAB (Brodén et al., ; Chu et al., ). As one of the most famous stochastic bandit algorithms, Thompson sampling has been widely applied in these applications and achieves excellent performance both empirically (Chapelle & Li, ; Scott, ) and theoretically (Agrawal & Goyal, ; ). Compared to another popular exploration strategy known as optimality in the face of uncertainty (OFUL/UCB), Thompson sampling has several advantages:

- •
Utilizing prior information: By design, Thompson sampling algorithms utilize and benefit from the prior information about the arms.
- •
Easy to implement: While the regret of a UCB algorithm depends critically on the specific choice of upper-confidence bound, Thompson sampling depends only on the best possible choice. This becomes an advantage when there are complicated dependencies among actions, as designing and computing with appropriate upper confidence bounds present significant challenges Russo et al. (). In practice, Thompson sampling is usually easier to implement Chapelle & Li ().
- •
Stochastic exploration: Thompson sampling is a random exploration strategy, which could be more resilient under some bandit settings Lancewicki et al. ().

Despite the success, Thompson sampling faces the problem of low efficacy under adversarial reward poisoning attacks Jun et al. (); Xu et al. (); Liu & Shroff (). Existing algorithms assume that the reward signals corresponding to selecting an arm are drawn stochastically from a fixed distribution depending on the arm. However, this assumption does not always hold in the real world. For example, a malicious user can provide an adversarial signal for an article from a recommendation system. Even under small corruption, Thompson sampling algorithms suffer from significant regret under attacks. While robust versions of the learning algorithms following other fundamental exploration strategies such as optimality in the face of uncertainty (OFUL) and $\epsilon$-greedy were developed Lykouris et al. (); Neu & Olkhovskaya (); Ding et al. (); He et al. (); Xu et al. (), there has been no prior investigation of robust Thompson sampling algorithms. The main challenge is that under the reward poisoning attacks, it becomes impossible to compute the actual posteriors based on the true reward, which is essentially required by the algorithm. Naively computing the posteriors based on the corrupted reward causes the algorithm to be manipulated by the attacker arbitrarily (Xu et al., ).

This work. We are the first to show the feasibility of making Thompson sampling algorithms robust against adversarial reward poisoning. Our main contribution is developing robust Thompson sampling algorithms for stochastic and linear contextual bandits. We consider both cases where the corruption budget of the attack is known or unknown to the learning agent. The regrets induced by our algorithms under the attack are near-optimal with theoretical guarantees. We adopt two ideas to achieve robustness against reward poisoning attacks in the two MAB settings. The first idea is ‘optimality in the face of corruption.’ In the stochastic MAB setting, we show that the Thompson sampling algorithm can maintain sufficient explorations on arms and identify the optimal arm by relying on optimistic posteriors considering potential attacks. The second idea is to adopt a weighted estimator He et al. () that is less susceptible to the attack. In the linear contextual MAB setting, we show that with such an estimator, the influence of the attack on the estimation of the posteriors is limited, and the Thompson sampling algorithm can almost always identify the optimal arm at each round with a high probability. We empirically demonstrate the training process of our algorithms under the attacks and show that our algorithms are much more robust than other fundamental bandit algorithms, such as UCB, in practice. Compared to the state-of-the-art robust algorithm CW-OFUL He et al. () for linear contextual bandit setting, our algorithm is as efficient, and in addition, it inherits the advantages from using Thompson sampling exploration strategy as aforementioned.

## 2 Related Work

Thompson Sampling Algorithms:
Algorithms based on the Thompson sampling exploration strategy have been widely applied in online sequential decision-making problems Agrawal et al. (); Bouneffouf et al. (); Ouyang et al. (), including MAB settings with different constraints and reinforcement learning. Agrawal & Goyal (; ) develop insightful theoretical understandings of the learning efficiency of Thompson sampling. In the stochastic MAB and linear contextual MAB settings, algorithms based on Thompson sampling achieve near-optimal performance in that the upper bounds on regret match the lower bound of the setting Agrawal & Goyal (; ). However, these algorithms are designed for a setting without poisoning attacks, which may not be true in real-world scenarios. Differentially-private bandit setting is close to the poisoning attack considered in our case (Mishra & Thakurta, ; Hu et al., ), and efficient learning algorithms have been achieved through Thompson sampling (Hu & Hegde, ). In this setting, the learning algorithm should behave similarly if one reward at a training step can be arbitrary while others are stochastic. The results in this setting cannot be applied to our setting, where the attacker can perturb the reward at every step.

Reward Poisoning Attack against Bandits:
Reward poisoning attacks against bandits have been considered a practical threat against MAB algorithms Lykouris et al. (). A majority of studies on poisoning attacks adopt a strong attack model where the attacker decides its attack strategy after the agent takes an arm at each timestep Jun et al. (); Liu & Shroff (); Garcelon et al. (). This attack scenario is argued to be more practical Zhang et al. (). Jun et al. () proposes attack strategies that can work for specific learning algorithms. It has been well understood that the most famous bandit algorithms are vulnerable to poisoning attacks. The other attack model is called weak attack, where the attacker decides its attack strategy before the agent takes an arm Lykouris et al. (). Xu et al. () shows that a family of algorithms, including the most famous ones, are vulnerable even under weak attacks.

Robust Bandit Algorithms:
Finding bandit algorithms robust against poisoning attacks is a popular topic. Robust algorithms against weak or strong attack models have been developed in both stochastic bandit and linear contextual bandit settings Lykouris et al. (); Neu & Olkhovskaya (); Ding et al. (); He et al. (). Recently, Wei et al. () shows that with an algorithm robust against the strong attack model, one can extend it to a robust algorithm against the weak attack model. Our work focuses on robustness against the strong attack model as (1) the strong attack model is more practical, and (2) one can develop robust algorithms against weak attacks based on our algorithms.

## 3 Preliminaries

### 3.1 Stochastic Bandit Setting

For the stochastic multi-armed bandit setting, an environment consists of $N$ arms with fixed support in $[0,1]$ reward distributions centered at $\left\{\mu_{1},\ldots,\mu_{N}\right\}$, and an agent interacts with the environment for $T$ rounds. At each round $t$, the agent selects an arm $i(t)\in[N]$ and receives reward $r^{o}_{t}$ drawn from the reward distribution associated with the arm $i(t)$. The performance of the bandit algorithm is measured by its expected regret $\left.R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\left(\mu_{i^{*}}-\mu_{i(t)}\right)
\right)\right]$, where $i^{*}$ is the best arm at hindsight, i.e., $i^{*}=\arg\max_{i\in[N]}\mu_{i}$. Without loss of generality, we assume arm $i^{*}=1$ is the optimal arm. We denote $\Delta_{i}=\mu_{1}-\mu_{i}$ as the gap between arm $i$ and the optimal arm. The time horizon $T$ is predetermined, but the reward distribution of each arm is unknown to the agent. The agent’s goal is to minimize its expected regret $R_{T}$.

### 3.2 Linear Contextual Bandit Setting

Next, we consider the linear contextual bandit setting. An environment consists of $N$ arms and a context space with $d$ dimensions $\mathbb{R}^{d}$, and an agent interacts with the environment for $T$ rounds. At each round $t$, $N$ contexts $\{x_{i}(t)\in\mathbb{R}^{d}\},i=1,\ldots,N$ are revealed by the environment for the $N$ arms. We denote $\textbf{x}(t)=(x_{1}(t),\ldots,x_{N}(t))$. The agent draws an arm $i(t)$ and receives a reward $r^{o}_{i}(t)$. The reward is drawn from a distribution dependent on the arm $i(t)$ and the context $x_{i(t)}(t)$. In the linear contextual bandit setting, the expectation of reward is a linear function depending on the context: $\mathbb{E}[r(t)|x_{i(t)}(t)]=x_{i(t)}(t)^{T}\mu$, where $\mu\in\mathbb{R}^{d}$ is the reward parameter. Without loss of generality, we assume that the contexts and the reward parameters are bounded $\left\|x_{i}(t)\right\|_{2}\leq 1,\|\mu\|_{2}\leq 1$. The regret to measure the performance of the agent in this case is defined as $R_{T}=\sum_{t=1}x_{i^{*}(t)}(t)^{T}\mu-x_{i(t)}(t)^{T}\mu$ where $i^{*}(t)=\arg\max_{i}x_{i}(t)^{T}\mu$ is the optimal arm at time $t$. The time horizon $T$ is predetermined, but the agent’s reward parameter $\mu$ is unknown. The goal of the agent is to minimize the regret.

To make the regret bounds scale-free, we adopt a standard assumption Agrawal & Goyal () that $\epsilon_{t}=r^{o}(t)-x_{i(t)}(t)^{T}\mu$ is conditionally $\sigma$-sub-Gaussian for a constant $\sigma\geq 0$, i.e.,

$$ $\forall\lambda\in\mathbb{R},\mathbb{E}\left[e^{\lambda\epsilon_{t}}\mid\left\{ x_{i}(t)\right\}_{i=1}^{N},\mathcal{H}_{t-1}\right]\leq\exp\left(\frac{\lambda ^{2}\sigma^{2}}{2}\right),$ $$

where $\mathcal{H}_{t-1}=\left\{i(s),r(s),x_{i(s)}(s),s=1,\ldots,t-1\right\}$.

### 3.3 Strong Reward Poisoning Attack against Bandits

This work considers the strong reward poisoning attack model Wei et al. (), where an attacker sits between the environment and the agent. At each round $t$, the attacker observes the arm pulled by the agent $i(t)$, the reward $r^{o}(t)$, and additionally the context $x_{i(t)}(t)$ in the contextual bandit setting. Then the attacker can inject a perturbation $c(t)$ to the reward, and the agent will receive the corrupted reward ${r}(t)=r^{o}(t)+c(t)$ in the end. The attacker has full knowledge of the environment and the learner, including the algorithm it uses and the actions it takes each time. We denote $C$ as the budget of the attack $C:\sum_{t=1}^{T}|c(t)|\leq C$, representing the maximum amount of total perturbation it can apply during the training process. We also refer to it as ‘corruption level’ since it indicates the level of corruption the learning agent faces.

The weak attack model has been considered in previous works Lykouris et al. (); Liu & Shroff (). Unlike the strong attack model, the weak attack has to decide on the perturbation of the reward before observing the actions taken by the agent. In this work, we only consider the strong attack model for the following reasons: 1. in practice, the strong attack is more realistic. For example, in a recommendation system, the attacker, which is a malicious user, observes the recommendation first before deciding on the malicious feedback 2. Wei et al. () shows that a robust algorithm against strong attack can be used to construct robust algorithms against weak attacks. In section 4 and 5, we discuss the case where the corruption level or an upper bound on it is known or unknown to the learning agent.

### 3.4 Thompson Sampling Algorithms

Thompson sampling is a heuristic exploration strategy that belongs to the family
of randomized probability matching algorithms Thompson (). At each time step, a general Thompson sampling algorithm takes an arm based on a randomly drawn belief about the rewards of the arms. More specifically, the algorithm maintains a posterior distribution related to the expected reward of each arm. At each time, the algorithm samples a parameter from each arm’s posterior to formulate a belief on the reward of an arm, and then it takes the arm with the maximal reward belief. After observing the reward of the taken arm, the algorithm updates the posteriors. The distribution of each arm’s prior will influence the exact format of the algorithm.

In this work, we always assume that the priors for the rewards of the arms and the reward parameter are Gaussian distributions. This is a typical choice representative of Thompson sampling algorithms Agrawal & Goyal (; ). Although our algorithms assume Gaussian priors, in principle, it is not hard to extend them to other kinds of priors following the same idea, and many of our theoretical results are not dependent on the format of priors. In the Appendix, we show the Thompson sampling algorithms in Alg 3 and 4 for the stochastic and linear contextual MAB settings, respectively, with Gaussian distributions as priors.

## 4 Robust Thompson Sampling for Stochastic Multi-armed Bandits

In this section, we present our robust Thompson sampling algorithm for the stochastic MAB setting and the theoretical guarantee of its learning efficiency. We discuss both cases, whether the corruption level $C$ is known or unknown to the learning agent. To understand why the original Thompson sampling algorithm (Alg 3) is vulnerable under the poisoning attack, we note that the actual posteriors of arms given the uncorrupted reward drawn from the environments can no longer be acquired. When calculating the posterior as if the data are uncorrupted, the resulting posteriors can be biased to the actual posteriors. Therefore, the attacker can make the learner underestimate the posteriors of the optimal arms or overestimate that of the sub-optimal arms. As a result, the learner believes that the optimal arm has a low reward and rarely selects it.

To make the algorithm robust against attack, we utilize the idea of optimism. Instead of computing the posteriors as if the data are uncorrupted, the algorithm computes the optimistic posteriors with respect to corruption for each of the arms. For each arm, the algorithm finds the posterior that maximizes the expected reward for any possible true rewards before corruption. In the stochastic MAB settings with Gaussian priors, the mean in the posterior is $\frac{\sum_{s=1,i(s)=i}^{t-1}r(s)}{k_{i}(t)+1}$ where $k_{i}(t)$ is the number of times arm $i$ be pulled before time $t$. Since the possible reward with the maximal sum is $\sum_{s=1,i(s)=i}^{t-1}r(s)+C$, the mean of the optimistic posterior is $\frac{\sum_{s=1,i(s)=i}^{t-1}r(s)+C}{k_{i}(t)+1}$.

The robustness against the bias of posteriors induced by the poisoning attack is achieved by optimism. By using the optimistic posteriors for each arm, the algorithm never underestimates the posteriors of any arm. Even if a sub-optimal arm becomes the empirically optimal arm, after being selected a few times, its optimal posterior will be close to its actual posterior, which is inferior to the optimistic posterior of the optimal arm. As a result, the optimal arm will eventually be selected. Together with the Thompson sampling strategy to deal with the stochastic rewards from the environment, the algorithm can be robust and efficient in the stochastic MAB setting under poisoning attacks.

The empirical post-attack mean $\hat{\mu}_{i}(t)$ for arm $i$ at time $t$ is defined by $\hat{\mu}_{i}(t):=\frac{\sum_{s=1,i(s)=i}^{t-1}r(s)}{k_{i}(t)+1}$(note that $\hat{\mu}_{i}(t)=0$ when $\left.k_{i}(t)=0\right)$ and the empirical pre-attack mean $\hat{\mu}^{o}_{i}(t)$ for arm $i$ at time $t$ is defined by $\hat{\mu}^{o}_{i}(t):=\frac{\sum_{s=1,i(s)=i}^{t-1}r^{o}(s)}{k_{i}(t)+1}$(note that $\hat{\mu}^{o}_{i}(t)=0$ when $\left.k_{i}(t)=0\right)$. Let $\theta_{i}(t)$ denote a sample generated independently for each arm $i$ from the posterior distribution at time $t$. This is generated from posterior distribution $\mathcal{N}\left(\hat{\mu}_{i}(t)+\frac{\overline{C}}{k_{i}+1},\frac{1}{k_{i}(
t)+1}\right)$, where $\overline{C}$ is a hyper-parameter of the algorithm for tuning robustness against different level of corruption. In Alg 1, we formally show our robust Thompson sampling algorithm for the stochastic MAB setting.

Figure: Algorithm 1 Robust Thompson Sampling for Stochastic Bandits

At each round $t$, Alg 1 samples a parameter $\theta_{i}(t)$ from a Gaussian distribution for arm $i$ with the compensation term $\frac{\overline{C}}{k_{i}(t)+1}$ to make it the optimistic posterior. This enables the algorithm to explore the optimal arm even if the attack injects a negative bias. Notice that when $\overline{C}=0$, it degenerates into original Thompson Sampling using Gaussian priors. The regret of the algorithm under the attack is guaranteed in Theorem 4.1 as below.

###### Theorem 4.1 .

For the $N$-armed stochastic bandit problem under any reward poisoning attack with corruption level $C$, the expected regret of the Robust Thompson Sampling Alg 1 with $\overline{C}\geq C$ is bounded by:

$$ $\mathbb{E}[\mathcal{R}(T)]\leq O(\sqrt{NT\ln N}+N\overline{C}+N)$ $$

The big-Oh notation hides only absolute constants.

Proof Sketch:
A detailed proof can be found in the Appendix. Our proof technique is based on a previous study (Agrawal & Goyal, ). Here, we provide a sketch for the proof. First, we define two good events:

###### Definition 4.2 (Good Events) .

For $i\neq 1$, define $E_{i}^{\mu}(t)$ is the event $\hat{\mu}_{i}(t)\leq\mu_{i}+\frac{\Delta_{i}}{3}$, and $E_{i}^{\theta}(t)$ is the event $\theta_{i}(t)\leq\mu_{i}-\frac{\Delta_{i}}{3}$.

$E_{i}^{\mu}(t)$ represents the case where the empirical means of sub-optimal arms are not much larger than their true mean. $E_{i}^{\theta}(t)$ represents cases where the sampled rewards from sub-optimal arms’ posteriors are less than their true mean. Next, we can prove that when both good events are true, the probability that the agent selects the optimal arm is high, so the regret in this case is limited. Then, we can prove that the probability of either or both good events being false is low, so even if the worst scenario happens when the good events are false, the regret is still limited due to the low probability of this case. The key reason why both good events are true with a high probability is because of the bonus term $\frac{\overline{C}}{k_{i}(t)s+1}$ we add for the posterior distributions of each arm compensates for the bias induced by the attack in the worst case. As a result, the agent is very unlikely to underestimate the performance of each arm under any poisoning attack within the budget limit. Therefore, the explorations of each arm are likely to be sufficient. Finally, by combining all the cases, we can show that the total regret is limited.

Corruption level $C$ known to the learner: In this case, we simply set $\overline{C}=C$ in Alg 1. Then, the dependency of regret on $C$ is linear according to Theorem 4.1, which is near-optimal Gupta et al. ().

Corruption level $C$ unknown to the learner: In this case, we set $\overline{C}=\sqrt{T\ln N/N}$ in Alg 1. Theorem 4.1 shows that if $C\leq\sqrt{T\ln N/N}$, the regret can be upper bounded by $O(\sqrt{NT\ln N})$ when $T\geq N$, and if $C>\sqrt{T\ln N/N}$ the regret can be trivially bounded by
$O(T)$. This upper bound is near-optimal when $C\leq\sqrt{T\ln N/N}$ due to the lower bound in Theorem 1.4 from Agrawal & Goyal (). And the multi-armed bandit case of Theorem 4.12 in He et al. () shows it’s also near-optimal when $C>\sqrt{T\ln N/N}$.

###### Theorem 4.1 .

###### Definition 4.2 (Good Events) .

## 5 Robust Thompson Sampling for Contextual Linear Bandits

In this section, we present our robust Thompson sampling algorithm for the contextual linear MAB setting and the theoretical guarantee of its learning efficiency. The vulnerability of Thompson sampling in the linear contextual bandit setting is similar to that in the stochastic bandit setting. The posterior on the reward parameter based on the corrupted reward can be biased compared to the actual posterior, resulting in poor decisions on action selection. Even worse, the bias induced by the reward corruption is relatively large when computing the posterior parameters as in Alg 4. Consequently, Zhao et al. () follows the UCB exploration strategy using such an estimator, and the resulting algorithm is still not robust enough under the poisoning attacks. Therefore, we are not using the original estimator for our robust algorithm.

Inspired by He et al. (), we use a weighted ridge regression estimator as described in Alg 2 line $6$ to compute the expectation of the Gaussian posterior. Such an estimator can effectively reduce the bias induced by reward poisoning. The key is that it assigns less weight to the data with a ‘large’ context so that the attacker can apply less influence on the estimator by corrupting such data. We formally show the algorithm in Alg 2, where $v_{t}=\sigma\sqrt{9d\ln\left(\frac{t+1}{\delta}\right)}$ and $\gamma>0$ is a hyper-parameter representing the degree of robustness against different corruption.

Figure: Algorithm 2 Robust Thompson Sampling for Contextual Linear Bandits

In general, Alg 2 is very similar to the original version in Alg 4 except for using the ridge regression estimator. This change ensures that the posterior calculated in line $3$ is not far from the actual posterior under poisoning attacks. In Theorem 5.1, we provide a high probability bound on the regret for Alg 2.

###### Theorem 5.1 .

For the stochastic contextual bandit problem with linear payoff functions, with probability $1-\delta$, the total regret in time $T$ for Robust Thompson Sampling for Contextual Linear Bandits (Algorithm 2) is bounded by

$$ $\displaystyle O\left(de^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}\sqrt{dT\ln T\ln \left(\frac{T}{\delta}\right)}+C\gamma e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}} \sqrt{dT\ln T}\right.$ $\displaystyle\left.+\frac{d^{2}e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}}{\gamma} \ln T\sqrt{\ln\left(\frac{T}{\delta}\right)}+Cde^{(1+\frac{C\gamma}{\sqrt{d}}) ^{2}}\ln T\right)$ $$

Proof Sketch: Here we provide a proof sketch for Theorem 5.1. The full proof can be found in the Appendix. Similar to the proof for Theorem 4.1, first, we define two good events:

###### Definition 5.2 (Good Events) .

Define $E^{\mu}(t)$ as the event

$$ $\displaystyle\forall i:\left|x_{i}(t)^{T}\hat{\mu}(t)-x_{i}(t)^{T}\mu\right|$ $\displaystyle\leq\left(\sigma\sqrt{d\ln\left(\frac{t^{3}}{\delta}\right)}+1+C \gamma\right)\|x_{i}(t)\|_{B(t)^{-1}}$ $$

Define $E^{\theta}(t)$ as the event that

$$ $\forall i:\left|\theta_{i}(t)-x_{i}(t)^{T}\hat{\mu}(t)\right|\leq\sqrt{4d\ln(t )}v_{t}\|x_{i}(t)\|_{B(t)^{-1}}.$ $$

$E^{\mu}(t)$ represents the case where the mean of the posterior of each arm is close to its actual reward parameter. $E^{\theta}(t)$ represents the case where the sampled reward for each arm is close to its expected value. Next, we prove that both good events hold with a high probability. The key reason is that the variance of the posterior distribution is limited due to the weighted estimator under reward poisoning attacks. Therefore, the evaluation for each arm is more likely to be accurate, and the exploration will be sufficient correspondingly. For each arm that is sub-optimal at a round, we define an arm as saturated if it has been selected more than a specific number of times. The value for this particular number is also limited due to the weighted estimator. Next, we prove that if an arm is saturated and both good events are true, then it is very unlikely for the algorithm to select the arm. In other words, for a sub-optimal arm at a round, if it has already been selected a limited number of times, then it is very unlikely to be chosen furthermore unless the good events are false, which happens with a low probability. Therefore, the cumulative times that a sub-optimal arm is selected at a time is limited, so the regret of the algorithm is bounded.

Corruption level $C$ known to the learner: In this case, we set $\gamma=\sqrt{d}/C$. By Theorem 5.1, the regret is upper bounded by

$$ $\begin{aligned} \mathcal{R}(T)&=O\left(d\sqrt{dT\ln T\ln\left(\frac{T}{\delta} \right)}+Cd\sqrt{d}\ln T\sqrt{\ln\left(\frac{T}{\delta}\right)}\right)\\ &=\widetilde{O}(d\sqrt{dT}+d\sqrt{d}C)\end{aligned}.$ $$

The dependency of regret on the corruption level $C$ is near-optimal Bogunovic et al. (), and the algorithm becomes the same as the LinUCB algorithm when there is no corruption $C=0$.

Corruption level $C$ unknown to the learner:
In this case, we set $\gamma=\sqrt{d}/\sqrt{T}$ in Alg 2. From Theorem 5.1 and the results in the known $C$ case above, the algorithm’s regret is upper bounded by $\widetilde{O}(d\sqrt{dT})$ when $C\leq\sqrt{T}$, else it is trivially bounded by $O(\sqrt{T})$. According to Hamidi & Bayati (), the worst-case lower bound for Thompson Sampling is $\Omega(d\sqrt{dT})$. Therefore, our upper bound is near-optimal when $C\leq\sqrt{T}$, and from Theorem 4.12 in He et al. () we know that it’s also optimal when $C>\sqrt{T}$.

###### Theorem 5.1 .

###### Definition 5.2 (Good Events) .

## 6 Simulation Results

In this section, we show the simulation results of running our algorithm on general bandit environments under typical attacks commonly used in other literature. We notice that the constant term in our regret analysis is large, so we want to show that the constant term is low in practice and verify that the regret is indeed linearly dependent on the corruption budget. We also want to use empirical results to intuitively show how our robust algorithms perform under the poisoning attack.

### 6.1 Stochastic MAB Setting

Experiment setup:
We consider a stochastic MAB environment consisting of $N=5$ arms and a total number of timesteps of $T=5000$. We adopt two attack strategies: (1) Junsun’s attack proposed by Jun et al. (). (2) oracle MAB attack, which is also used in Jun et al. (). The choice for corruption level varies in our experiments, which will be specified in the experimental results. Each experiment is repeated for $10$ times, and we show the empirical mean and standard deviation in the experimental results.

Cumulative regret during training under attack:
Here, we intuitively show the behavior of our robust Thompson sampling algorithms under the attack. For comparison, we choose the UCB and Thompson sampling algorithms to represent the behavior of an efficient but not robust algorithm. The corruption level for the attack is set as $C=25$. Such a corruption level is high enough to show the vulnerability of a vulnerable attack and lower than the threshold to induce high regret on a robust algorithm when $C$ is unknown. We will show the results of higher corruption levels later.

In Figure 1, we show the cases of corruption level $C$ known and unknown to the learning agent. For any non-robust algorithm, the regret rapidly increases with time, indicating that they rarely take the optimal arm during the whole learning process. For our robust algorithms, after the first few timesteps, the regret increases slowly with time. This suggests that after some explorations, our algorithm successfully identifies the optimal arm and takes it for most of the time.

Figure: Figure 1: In the stochastic bandit setting, the cumulative regret of different learning algorithms during training under different attacks.
Refer to caption: extracted/5949835/figure/MAB_Average_Accumulated_Regret_Under_Attack_Method_junsun_and_Budget_25_with_Iteration_5000.png

Robustness evaluation and comparison under different corruption level:

Here, we show the total regret of our algorithm under attacks at different corruption levels. For both attack strategies we test with, the results in Figure 2 show that for the algorithms that are not robust, the regret becomes large quickly as the corruption level increases, indicating that these algorithms cannot find the optimal arm with even a low corruption level.

In the known corruption level case, the regret almost increases linearly with the corruption level for our robust algorithm, which agrees with our theoretical result. In the unknown corruption level case, we observe a threshold in the corruption level such that the regret of our algorithm increases rapidly with the corruption level, which is also aligned with our theoretical analysis.

Figure: Figure 2: In the stochastic bandit setting, the total regret of different algorithms under attacks at different corruption level.
Refer to caption: extracted/5949835/figure/MAB_Average_Accumulated_Regret_Under_Attack_Method_junsun.png

### 6.2 Contextual Linear Bandit Setting

Experiment setup:
We consider a linear contextual bandit environment with $N=5$ arms and $T=5000$ timesteps. The dimension of the context space is $d=5$. For the baseline algorithms, we choose two standard algorithms, LinUCB and LinTS, to represent the vulnerable algorithms. They are the extensions of the UCB and Thompson sampling algorithm to the linear contextual case. In addition, algorithms robust to strong attacks in the contextual bandit setting have been developed in previous studies, and we choose the state-of-the-art CW-OFUL algorithm He et al. () as the baseline of a different robust algorithm. We adopt two attack strategies: (1) Garcelon’s attack proposed in Garcelon et al. (); (2) oracle MAB attack, which is also adopted in Garcelon et al. ().

Cumulative regret during training under attack:
Here, we show the behavior of different learning algorithms under different attacks during the learning process. The corruption level for the attack is set as $C=200$. In Figure 3, we show the cases of corruption level $C$ known and unknown to the learning agent. Similar to the stochastic bandit case, the regret of the vulnerable algorithms rapidly increases with time, suggesting that they almost can never find the optimal arm. For our robust algorithms, after the first few timesteps, it learns to estimate the reward parameter accurately and can almost always find the optimal arm.

Figure: Figure 3: In the linear contextual bandit setting, the cumulative regret of different learning algorithms during training under different attacks.The total training steps is $T=5000$.
Refer to caption: extracted/5949835/figure/Average_Accumulated_Regret_Under_Attack_Method_Garcelon_and_Budget_300_with_Iteration_5000.png

Figure: Figure 4: In the contextual linear bandit setting, the total regret of different algorithms under attacks at different corruption level. The total training steps is $T=5000$.
Refer to caption: extracted/5949835/figure/Average_Accumulated_Regret_Under_Attack_Method_Garcelon_with_CWOFUL.png

Robustness evaluation and comparison under different corruption level:
Here, we show the regret of different learning algorithms under attacks at different corruption levels. For both attack strategies we test with, the results in Fig 4 show that for the vulnerable algorithms, the regret increases quickly as the corruption level increases and converges to a large value in the end, indicating that these algorithms can no longer find the optimal arm for even a relatively low corruption level.

For our robust algorithm, when $C$ is known to the agent, the regret increases linearly with the corruption level; when $C$ is unknown to the agent, there exists a threshold in the corruption level such that at one point, the regret rapidly increases with the corruption level. This observation agrees with our theoretical result.

Figure 4 also shows that our algorithm is as robust as the CW-OFUL algorithm. In our setup, our algorithm performs slightly worse in the known corruption level $C$ case and significantly better in the unknown $C$ case, especially when $C$ is large. Our robust algorithms not only inherit the idea of Thompson sampling exploration but also achieve state-of-the-art performance in practice.

## 7 Conclusion and Limitation

In this work, we propose two robust Thompson sampling algorithms for stochastic and linear contextual MAB settings, with a theoretical guarantee of near-optimal regret. However, we mainly focus on the case where the posteriors of the arms are Gaussian distributions, though the theoretical analysis can be applied to other posterior settings. Our ideas for building robust Thompson sampling have been used in the two most popular bandit settings, and we do not cover settings like MDP. In the future, we aim to extend our techniques to other online learning settings.

## 8 Reproducibility

We clearly explain the bandit settings and threat models we work on. The proofs for any Theorems and Lemmas can be found in the appendix. The codes we use for the simulations are included in the supplementary materials.

## Appendix A Proof for Section 4

### A.1 Proof of Theorem 4.1

To begin with, it’s easy to see that we only need to prove the case where $\overline{C}=C$ in Alg 1. Suppose we have set $\overline{C}=C$. Following the proof in Agrawal & Goyal (), first, we define two good events such that the agent is likely to pull the optimal arm when the events are true.

###### Definition A.1 (Good Events) .

For $i\neq 1$, define $E_{i}^{\mu}(t)$ is the event $\hat{\mu}_{i}(t)\leq\mu_{i}+\frac{\Delta_{i}}{3}$, and $E_{i}^{\theta}(t)$ is the event $\theta_{i}(t)\leq\mu_{i}-\frac{\Delta_{i}}{3}$.

$E_{i}^{\mu}(t)$ holds mean that the empirical post-attack mean of any sub-optimal arm is not much greater than its true mean, and $E_{i}^{\theta}(t)$ holds means that the sampled value of any sub-optimal arm is not much greater than its true mean. Intuitively, under such situations, the regret should be low.

Next, we define a random variable $p_{i,t}$ determined by $\mathcal{F}_{t-1}$. $p_{i,t}$ represents that for a history $\mathcal{F}_{t-1}$, the probability of the sample from the optimal arm’s distribution being much higher than the means of other arms.

###### Definition A.2 .

Define, $p_{i,t}$ as the probability
$p_{i,t}:=\operatorname{Pr}\left(\theta_{1}(t)>\mu_{1}-\frac{\Delta_{i}}{3}\mid
\mathcal{F}_{t-1}\right).$

We decompose the regret into different cases based on whether the good events are true or not. The following lemma bounds the expected number of arm pulls for arm $i$ when both the good events are true.

###### Lemma A.3 .

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,E_{i}^{\mu}(t),E_{i}^ {\theta}(t)\right)\leq\sum_{k=0}^{T-1}\mathbb{E}\left[\frac{\left(1-p_{i,\tau_ {k}+1}\right)}{p_{i,\tau_{k}+1}}\right]$ $\displaystyle\leq 72\left(e^{64}+4\right)\frac{\ln\left(T\Delta_{i}^{2}\right) }{\Delta_{i}^{2}}+\frac{4}{\Delta_{i}^{2}}$ $$

Sampling from the optimistic posterior, the reward belief of the optimal arm is likely to be large even under poisoning attacks. Therefore, the value of $p_{i,t}$ is more likely to be large, and the probability of pulling any sub-optimal arm $i$ in this case will be small. We notice that the constant term here is a big value. In Section 6 we empirically show that in practice the constant term is small.

Next, we consider the case when only $E_{i}^{\mu}(t)$ is true. The key insight is that for a sub-optimal arm $i$, when the empirical post-attack mean $\hat{\mu}_{i}$ is close to the true mean $\mu_{i}$ and the arm has already been pulled many times, the probability that sampled $\theta_{i}(t)$ is large is low. As a result, the total number of times when the sub-optimal arm is pulled in this case is limited. The formal result is shown in A.4

###### Lemma A.4 .

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,\overline{E_{i}^{ \theta}(t)},E_{i}^{\mu}(t)\right)\leq\sum_{t=1}^{T}\operatorname{Pr}\left(i(t) =i,\overline{E_{i}^{\theta}(t)},\right.$ $\displaystyle\left.E_{i}^{\mu}(t),k_{i}(t)\leq\max\{\frac{32\ln\left(T\Delta_{ i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i}}\}\right)+\frac{1}{\Delta _{i}^{2}}$ $$

At last, we consider the case when neither good event is true. The key insight is that when a sub-optimal arm $i$ has already been pulled many times, the probability that the empirical post-attack mean $\hat{\mu}_{i}$ is far from the true mean $\mu_{i}$ is low, and the total number of times it being pulled in this case is limited as shown in Lemma A.5.

###### Lemma A.5 .

For $i\neq 1$,

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,\overline{E_{i}^{\mu} (t)}\right)\leq\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,\overline{E_{i}^{ \mu}(t)},k_{i}(t)\right.$ $\displaystyle\left.\leq\max\{\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{ i}^{2}},\frac{12C}{\Delta_{i}}\}\right)+1+\frac{8}{\Delta_{i}^{2}}$ $$

Next, we can prove Theorem 4.1 by combining the lemmas.

###### Proof of Theorem 4.1 .

We decompose the expected number of plays of a suboptimal arm $i\neq 1$ depending on whether the good events hold or not.

$$ $\displaystyle\mathbb{E}\left[k_{i}(T)\right]$ $\displaystyle=\sum_{t=1}^{T}\operatorname{Pr}(i(t)=i)=\sum_{t=1}^{T} \operatorname{Pr}\left(i(t)=i,E_{i}^{\mu}(t),E_{i}^{\theta}(t)\right)+$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,E_{i}^{\mu}(t), \overline{E_{i}^{\theta}(t)}\right)+\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)= i,\overline{E_{i}^{\mu}(t)}\right).$ $$

For each sub-optimal arm $i$, combine the bounds from Lemmas A.3 to A.4, we obtain

$$ $\displaystyle\mathbb{E}\left[k_{i}(T)\right]\leq 72\left(e^{64}+4\right)\frac{ \ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}}+\max\{\frac{12C}{\Delta_{i}},$ $\displaystyle\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}}\}+\frac{ 13}{\Delta_{i}^{2}}+1$ $$

$\Rightarrow$ The total regret can be upper bouded by:

$$ $\displaystyle\mathbb{E}[\mathcal{R}(T)]=\sum_{i}\Delta_{i}\mathbb{E}\left[k_{i }(T)\right]$ $\displaystyle\leq\sum_{i}[72\left(e^{64}+5\right)\frac{\ln\left(T\Delta^{2}_{i }\right)}{\Delta_{i}}+12C+\frac{13}{\Delta_{i}}+\Delta_{i}]$ $$

Then for every arm $i$ with $\Delta_{i}\geq e\sqrt{\frac{N\ln N}{T}}$, the expected regret is bounded by
$O\left(\sqrt{NT\ln N}+NC+N\right)$. And for arms with $\Delta_{i}\leq e\sqrt{\frac{N\ln N}{T}}$, the total regret is bounded by $O(\sqrt{NT\ln N}+NC)$. By combining these results we prove the Theorem 4.1.

∎

###### Definition A.1 (Good Events) .

###### Definition A.2 .

###### Lemma A.3 .

###### Lemma A.4 .

###### Lemma A.5 .

###### Proof of Theorem 4.1 .

### A.2 Proof of Lemma A.3

###### Lemma A.6 (Lemma 2.8 in Agrawal & Goyal ( 2017 ) ) .

For all $t,i\neq 1$ and all instantiations $F_{t-1}$ of $\mathcal{F}_{t-1}$ we have

$$ $\displaystyle\operatorname{Pr}\left(i(t)=i,E_{i}^{\mu}(t),E_{i}^{\theta}(t) \mid F_{t-1}\right)\leq\frac{\left(1-p_{i,t}\right)}{p_{i,t}}\operatorname{Pr} \left(i(t)=1,E_{i}^{\mu}(t),E_{i}^{\theta}(t)\mid F_{t-1}\right)$ $$

From the proof of Lemma 2.8 in Agrawal & Goyal (), it’s not hard to find that it is the event $E^{\theta}_{i}(t)$ that holds the above inequality. Therefore, although the distribution of $\theta_{i}$ has been changed to make the algorithm robust against adversarial attack, their proof can still be applied directly to the lemma A.6.

###### Lemma A.7 .

Let $s_{j}$ denote the time of the $j^{\text{th }}$ play of the first arm. Then,

$$ $\mathbb{E}\left[\frac{1}{p_{i,s_{j}+1}}-1\right]\leq\left\{\begin{array}[]{ll} e^{64}+5\\ \frac{4}{T\Delta_{i}^{2}}&j>\frac{72\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i }^{2}}\end{array}\right.$ $$

###### Proof.

Given $\mathcal{F}_{s_{j}}$, let $\Theta_{j}$ denote a random variable sampled from $\mathcal{N}\left(\hat{\mu}_{1}\left(s_{j}+1\right)+\frac{C}{j+1},\frac{1}{j+1}\right)$, and $\Theta^{o}_{j}$ denote a random variable sampled from $\mathcal{N}\left(\hat{\mu}^{o}_{1}\left(s_{j}+1\right),\frac{1}{j+1}\right)$. We abbreviate $\hat{\mu}_{1}\left(s_{j}+1\right)$ to $\hat{\mu}_{1}$ and $\hat{\mu}^{o}_{1}\left(s_{j}+1\right)$ to $\hat{\mu}^{o}_{1}$ in the following.
Let $G_{j}$ and $G^{o}_{j}$ be the geometric random variable denoting the number of consecutive independent trials until a sample of $\Theta_{j}$ or $\Theta^{o}_{j}$ becomes greater than $\mu_{1}-\frac{\Delta_{i}}{3}$, respectively. Notice that $\hat{\mu}_{1}\left(s_{j}+1\right)+\frac{C}{j+1}\geq\hat{\mu}^{o}_{1}\left(s_{j
}+1\right)$, then we have

$$ $p_{i,s_{j}+1}=\operatorname{Pr}\left(\Theta_{j}>\mu_{1}-\frac{\Delta_{i}}{3} \mid\mathcal{F}_{s_{j}}\right)\geq\operatorname{Pr}\left(\Theta^{o}_{j}>\mu_{1 }-\frac{\Delta_{i}}{3}\mid\mathcal{F}_{s_{j}}\right)$ $$

$\Rightarrow$

$$ $\mathbb{E}\left[\frac{1}{p_{i,s_{j}+1}}-1\right]\leq\mathbb{E}\left[\frac{1}{ \operatorname{Pr}\left(\Theta^{o}_{j}>\mu_{1}-\frac{\Delta_{i}}{3}\mid\mathcal {F}_{s_{j}}\right)}-1\right]$ $$

From the result in Agrawal & Goyal (),

$$ $\mathbb{E}\left[\frac{1}{\operatorname{Pr}\left(\Theta^{o}_{j}>\mu_{1}-\frac{ \Delta_{i}}{3}\mid\mathcal{F}_{s_{j}}\right)}-1\right]\leq\left\{\begin{array} []{ll}e^{64}+5\\ \frac{4}{T\Delta_{i}^{2}}&j>\frac{72\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i }^{2}}\end{array}\right.$ $$

Combining the above two inequalities, we derive the needed result.
∎

###### Proof.

Let $s_{k}$ denote the time at which arm $i$ is pulled $k$ times. Set $s_{0}=0$. Now applying Lemma A.6 and Lemma A.7, we have

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,E_{i}^{\mu}(t),E_{i}^ {\theta}(t)\right)$ $\displaystyle=\sum_{t=1}^{T}\mathbb{E}\left[\operatorname{Pr}\left(i(t)=i,E_{i }^{\mu}(t),E_{i}^{\theta}(t)\mid\mathcal{F}_{t-1}\right)\right]$ $\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\left[\frac{\left(1-p_{i,t}\right)}{p _{i,t}}\operatorname{Pr}\left(i(t)=1,E_{i}^{\theta}(t),E_{i}^{\mu}(t)\mid \mathcal{F}_{t-1}\right)\right]$ $\displaystyle=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{E}\left[\frac{\left(1-p_{i ,t}\right)}{p_{i,t}}I\left(i(t)=1,E_{i}^{\theta}(t),E_{i}^{\mu}(t)\right)\mid \mathcal{F}_{t-1}\right]\right]$ $\displaystyle=\sum_{t=1}^{T}\mathbb{E}\left[\frac{\left(1-p_{i,t}\right)}{p_{i ,t}}I\left(i(t)=1,E_{i}^{\theta}(t),E_{i}^{\mu}(t)\right)\right]$ $\displaystyle=\sum_{k=0}^{T-1}\mathbb{E}\left[\frac{\left(1-p_{i,s_{k}+1} \right)}{p_{i,s_{k}+1}}\sum_{t=s_{k}+1}^{s_{k+1}}I\left(i(t)=1,E_{i}^{\theta}( t),E_{i}^{\mu}(t)\right)\right]$ $\displaystyle\leq\sum_{k=0}^{T-1}\mathbb{E}\left[\frac{\left(1-p_{i,s_{k}+1} \right)}{p_{i,s_{k}+1}}\right]$ $\displaystyle\leq 72\left(e^{64}+4)\right)\frac{\ln\left(T\Delta_{i}^{2}\right )}{\Delta_{i}^{2}}+\frac{4}{\Delta_{i}^{2}}$ $$

Then we obtain the bound in Lemma A.3.
∎

###### Lemma A.6 (Lemma 2.8 in Agrawal & Goyal ( 2017 ) ) .

###### Lemma A.7 .

###### Proof.

###### Proof.

### A.3 Proof of Lemma A.4

###### Proof.

We have

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,\overline{E_{i}^{ \theta}(t)},E_{i}^{\mu}(t)\right)$ $\displaystyle=\sum_{t=1}^{T}\operatorname{Pr}\bigg{(}i(t)=i,k_{i}(t)\leq\max\{ \frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i} }\},\overline{E_{i}^{\theta}(t)},E_{i}^{\mu}(t)\bigg{)}+$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\bigg{(}i(t)=i,k_{i}(t)>\max\{ \frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i} }\},\overline{E_{i}^{\theta}(t)},E_{i}^{\mu}(t)\bigg{)}$ $$

Next, we prove that the probability that the event $E_{i}^{\theta}(t)$ is violated is small when $k_{i}(t)$ is large enough and $E_{i}^{\mu}(t)$ holds. Notice that

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,k_{i}(t)>\max\{\frac{ 32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i}}\}, \overline{E_{i}^{\theta}(t)},E_{i}^{\mu}(t)\right)$ $\displaystyle\leq\mathbb{E}\bigg{[}\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i ,\overline{E_{i}^{\theta}(t)}\mid k_{i}(t)>\max\{\frac{32\ln\left(T\Delta_{i}^ {2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i}}\},E_{i}^{\mu}(t),\mathcal{F }_{t-1}\right)\bigg{]}$ $\displaystyle\leq\mathbb{E}\bigg{[}\sum_{t=1}^{T}\operatorname{Pr}\left(\theta _{i}(t)>\mu_{1}-\frac{\Delta_{i}}{3}\mid k_{i}(t)>\max\{\frac{32\ln\left(T \Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i}}\},E_{i}^{\mu}(t) ,\mathcal{F}_{t-1}\right)\bigg{]}$ $$

Recall that $\theta_{i}(t)$ is sampled from $\mathcal{N}\left(\hat{\mu}_{i}(t)+\frac{C}{k_{i}(t)+1},\frac{1}{k_{i}(t)+1}\right)$. Since $\hat{\mu}_{i}(t)\leq\mu_{i}+\frac{\Delta_{i}}{3}$, we have

$$ $\displaystyle\operatorname{Pr}\left(\theta_{i}(t)>\mu_{1}-\frac{\Delta_{i}}{3} \mid k_{i}(t)>\max\{\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}}, \frac{12C}{\Delta_{i}}\},\hat{\mu}_{i}(t)\leq\mu_{i}+\frac{\Delta_{i}}{3}, \mathcal{F}_{t-1}\right)$ $\displaystyle\leq\operatorname{Pr}\left(\mathcal{N}\left(\mu_{i}+\frac{\Delta_ {i}}{3}+\frac{C}{k_{i}(t)+1},\frac{1}{k_{i}(t)+1}\right)>\mu_{1}-\frac{\Delta_ {i}}{3}\mid\mathcal{F}_{t-1},k_{i}(t)>\max\{\frac{32\ln\left(T\Delta_{i}^{2} \right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i}}\}\right)$ $$

Since $k_{i}(t)>\max\{\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{
12C}{\Delta_{i}}\}$, from the property of Gaussian distribution we obtain that

$$ $\displaystyle\operatorname{Pr}\left(\mathcal{N}\left(\mu_{i}+\frac{\Delta_{i}} {3}+\frac{C}{k_{i}(t)+1},\frac{1}{k_{i}(t)+1}\right)>\mu_{1}-\frac{\Delta_{i}} {3}\right)$ $\displaystyle\leq\frac{1}{2}e^{-\frac{\left(k_{i}(t)+1\right)\left(\frac{ \Delta_{i}}{3}-\frac{C}{k_{i}(t)+1}\right)^{2}}{2}}$ $\displaystyle\leq\frac{1}{2}e^{-\frac{\left(k_{i}(t)+1\right)\left(\frac{ \Delta_{i}}{3}\right)^{2}}{2}}$ $\displaystyle\leq\frac{1}{T\Delta_{i}^{2}}$ $$

the second inequality holds because $k_{i}(t)\geq\frac{12C}{\Delta_{i}}$ and the last inequality holds because $k_{i}(t)\geq\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\left(\Delta_{i}\right)^{
2}}$. Therefore,

$$ $\displaystyle\operatorname{Pr}\left(\theta_{i}(t)>\mu_{1}-\frac{\Delta_{i}}{3} -\frac{\Delta_{i}}{12}\mid k_{i}(t)>\max\{L_{i}(T),\frac{12C}{\Delta_{i}}\}, \hat{\mu}_{i}(t)\leq\mu_{i}+\frac{\Delta_{i}}{3},\mathcal{F}_{t-1}\right)\leq \frac{1}{T\Delta_{i}^{2}}$ $$

$\Rightarrow$

$$ $\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,k_{i}(t)>\max\{\frac{32\ln\left(T \Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{\Delta_{i}}\},\overline{E_{i }^{\theta}(t)},E_{i}^{\mu}(t)\right)\leq\frac{1}{\Delta_{i}^{2}}$ $$

Then we finish the proof.
∎

###### Proof.

### A.4 Proof of Lemma A.5

###### Proof.

Let $s_{k}$ denote the time at which arm $i$ is pulled $k$ times. Set $s_{0}=0$. We have

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,\overline{E_{i}^{\mu} (t)}\right)$ $\displaystyle\leq\sum_{t=1}^{T}\operatorname{Pr}\left(i(t)=i,\overline{E_{i}^{ \mu}(t)},k_{i}(t)\leq\max\{\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i} ^{2}},\frac{12C}{\Delta_{i}}\}\right)+$ $\displaystyle\sum_{k>\max\{\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i} ^{2}},\frac{12C}{\Delta_{i}}\}}^{T-1}\operatorname{Pr}\left(\overline{E_{i}^{ \mu}\left(s_{k+1}\right)}\right)$ $$

At time $s_{k+1}$ for $k\geq 1,$ we have
$\hat{\mu}_{i}\left(s_{k+1}\right)=\frac{\sum_{t=1,i(t)=i}^{s_{k+1}}r_{i}(t)}{k
+1}\leq\frac{\sum_{t=1,i(t)=i}^{s_{k+1}}r^{o}_{i}(t)}{k+1}+\frac{C}{k+1}$. By Chernoff-Hoeffding inequality, when $k>\max\{\frac{32\ln\left(T\Delta_{i}^{2}\right)}{\Delta_{i}^{2}},\frac{12C}{
\Delta_{i}}\}$,

$$ $\displaystyle\operatorname{Pr}\left(\hat{\mu}_{i}\left(s_{k+1}\right)>\mu_{i}+ \frac{\Delta_{i}}{3}\right)$ $\displaystyle\leq\operatorname{Pr}\left(\frac{\sum_{t=1,i(t)=i}^{s_{k+1}}r^{o} _{i}(t)}{k+1}+\frac{C}{k+1}>\mu_{i}+\frac{\Delta_{i}}{3}\right)\leq e^{-2(k+1) \left(\frac{\Delta_{i}}{3}-\frac{C}{k+1}\right)^{2}}\leq e^{\frac{-(k+1)\Delta _{i}^{2}}{8}}$ $$

we then obtain that

$$ $\displaystyle\sum_{k>\max\{L_{i}(T),\frac{12C}{\Delta_{i}}\}}^{T-1} \operatorname{Pr}\left(\overline{E_{i}^{\mu}\left(s_{k+1}\right)}\right)=\sum_ {k>\max\{L_{i}(T),\frac{12C}{\Delta_{i}}\}}^{T-1}\operatorname{Pr}\left(\hat{ \mu}_{i}\left(s_{k+1}\right)>\mu_{i}+\frac{\Delta_{i}}{3}\right)$ $\displaystyle\leq 1+\sum_{k=1}^{T-1}\exp\left(-\frac{(k+1)\Delta_{i}^{2}}{8} \right)\leq 1+\frac{8}{\Delta_{i}^{2}}$ $$

Combining the above results we finish the proof.
∎

###### Proof.

## Appendix B Proof from Section 5

### B.1 Proof of Theorem 5.1

Follow the proof of Agrawal & Goyal (), to prove Theorem 5.1, we begin with some basic definitions. The sample $\tilde{\mu}(t)$ from the posterior is a belief in the reward parameter. Therefore, we denote the actual sample for the belief in the reward of an arm as $\theta_{i}(t):=x_{i}(t)^{T}\tilde{\mu}(t)$. By definition of $\tilde{\mu}(t)$ in Algorithm 2, marginal distribution of each $\theta_{i}(t)$ is Gaussian with mean $x_{i}(t)^{T}\hat{\mu}(t)$ and standard deviation $v_{t}\|x_{i}(t)\|_{B(t)^{-1}}$. Similar to before, we denote $\Delta_{i}(t):=x_{i^{*}(t)}(t)^{T}\mu-x_{i}(t)^{T}\mu$ as the gap between the mean reward of optimal arm and arm $i$ at time $t$, and we define two good events as Definition 5.2

Next, we define a notion called saturated arm to indicate whether an arm has been taken for enough time such that the variance in its reward estimation is less than the gap in reward compared to the optimal arm at a timestep.

###### Definition B.1 (Saturated Arm) .

Denote $g_{t}=\sqrt{4d\ln(t)}v_{t}+\sigma\sqrt{d\ln\left(\frac{t^{3}}{\delta}\right)}+
1+C\gamma$. An arm $i$ is called saturated at time $t$ if $\Delta_{i}(t)>g_{t}\|x_{i}(t)\|_{B(t)^{-1}}$, and unsaturated otherwise. Let $C(t)$ ne the set of saturated arms at time $t$.

First, in Lemma B.2 we show that good events hold with a high probability at each round. The reason why Lemma B.2 holds is because of the weighted ridge estimator we use for computing the posteriors. With such an estimator, the attack has less influence on the estimations, and therefore the difference between the estimation and the true value can be bounded.

###### Lemma B.2 .

For all $t,0<\delta<1,\operatorname{Pr}\left(E^{\mu}(t)\right)\geq 1-\frac{\delta}{t^{2}}$. For all possible filtrations $\mathcal{F}_{t-1},\operatorname{Pr}\left(E^{\theta}(t)\mid\mathcal{F}_{t-1}
\right)\geq 1-\frac{1}{t^{2}}$.

Next, Lemma B.3 shows that when the good events are true, with a high probability, the sampled reward for the optimal arm at a timestep is likely to be larger than its actual expected reward.

###### Lemma B.3 .

Denote $p=\frac{1}{4e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}\sqrt{\pi}}$. For any filtration $\mathcal{F}_{t-1}$ such that $E^{\mu}(t)$ is true,

$$ $\operatorname{Pr}\left(\theta_{i^{*}(t)}(t)>x_{i^{*}(t)}(t)^{T}\mu\mid\mathcal {F}_{t-1}\right)\geq p$ $$

Lemma B.3 suggests that the algorithm is unlikely to underestimate the reward of the optimal arm.

Based on Lemma B.2 and Lemma B.3, we can further show that when the good events are true, since the optimal arm and the unsaturated arm will be pulled with at least a certain probability, the algorithm can perform effective exploration. Therefore, the regret will be upper bounded with a high probability. We establish a super-martingale process that will form the basis of our proof of the high-probability regret bound. This result shows that expected regret will be $O(\frac{g_{t}}{p}\ast\sum_{t}\|x_{i(t)}(t)\|_{B(t)^{-1}})$.

###### Definition B.4 .

Recall that regret $(t)$ was defined as, regret $(t)=\Delta_{i(t)}(t)=x_{i^{*}(t)}(t)^{T}\mu-$ $x_{i(t)}(t)^{T}\mu$. Define regret ${}^{\prime}(t)=\operatorname{regret}(t)\cdot I\left(E^{\mu}(t)\right)$.

###### Definition B.5 .

Let

$$ $\displaystyle X_{t}$ $\displaystyle=\operatorname{regret}^{\prime}(t)-\min\{\frac{3g_{t}}{p}\|x_{i(t )}(t)\|_{B(t)^{-1}}+\frac{2g_{t}}{pt^{2}},1\}$ $\displaystyle Y_{t}$ $\displaystyle=\sum_{w=1}^{t}X_{w}.$ $$

###### Lemma B.6 .

$\left(Y_{t};t=0,\ldots,T\right)$ is a super-martingale process with respect to filtration $\mathcal{F}_{t}$.

###### Proof of Theorem 5.1 .

Note that $X_{t}$ is bounded, $\left|X_{t}\right|\leq 1+\frac{3}{p}g_{t}+\frac{2}{pt^{2}}g_{t}\leq\frac{6}{p}
g_{t}$. Thus, we can apply the Azuma-Hoeffding inequality, to obtain that with probability $1-\frac{\delta}{2}$,

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{regret}^{\prime}(t)\leq\sum_{t=1}^{T} \min\{\frac{3g_{t}}{p}s_{a(t)}(t),1\}+\sum_{t=1}^{T}\frac{2g_{t}}{pt^{2}}+ \sqrt{2\left(\sum_{t}\frac{36g_{t}^{2}}{p^{2}}\right)\ln\left(\frac{2}{\delta} \right)}$ $$

Note that $p$ is a constant. Also, by definition, $g_{t}\leq g_{T}$. Therefore, from above equation, with probability $1-\frac{\delta}{2}$,

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{regret}^{\prime}(t)\leq\sum_{t=1}^{T} \min\{\frac{3g_{t}}{p}s_{i(t)}(t),1\}+\frac{2g_{T}}{p}\sum_{t=1}^{T}\frac{1}{t ^{2}}+\frac{6g_{T}}{p}\sqrt{2T\ln\left(\frac{2}{\delta}\right)}$ $$

Now, we have

$$ $\displaystyle\sum_{t=1}^{T}\min\{1,\frac{3g_{k}}{p}s_{t,i(t)}\}$ $\displaystyle=\underbrace{\sum_{k:w_{k}=1}\min\left(1,\frac{3g_{t}}{p}\sqrt{x_ {i(k)}(k)^{\top}B_{i(k)}^{-1}x_{i(k)}(k)}\right)}_{I_{1}}+\underbrace{\sum_{k: w_{k}<1}\min\left(1,\frac{3g_{k}}{p}\sqrt{x_{i(k)}(k)^{\top}B_{i(k)}^{-1}x_{i( k)}(k)}\right)}_{I_{2}},$ $$

For the term $I_{1}$, we consider all rounds $k\in[T]$ with $w_{k}=1$ and we assume these rounds can be listed as $\left\{k_{1},\cdots,k_{m}\right\}$ for simplicity. With this notation, for each $i\leq m$, we can construct the auxiliary covariance matrix $A_{i}=\lambda I+\sum_{j=1}^{i-1}x_{i(k_{j})}(k_{j})x_{i(k_{j})}(k_{j})^{\top}$. Due to the definition of original covariance matrix $B_{k}$ in Algorithm, we have

$$ $B_{k_{i}}\geq\lambda I+\sum_{j=1}^{i-1}w_{k_{j}}x_{i(k_{j})}(k_{j})x_{i(k_{j}) }(k_{j})^{\top}=A_{i}$ $$

It further implies that for vector $x_{k_{i}}$, we have

$$ $x_{i(k)}(k)^{\top}B_{i(k)}^{-1}x_{i(k)}(k)\leq x_{i(k)}(k)^{\top}A_{i}^{-1}x_{ i(k)}(k)$ $$

The term $I_{1}$ can be bounded by

$$ $\displaystyle I_{1}$ $\displaystyle=\sum_{k:w_{k}=1}\min\left(1,\frac{3g_{t}}{p}\sqrt{x_{i(k)}(k)^{ \top}B_{i(k)}^{-1}x_{i(k)}(k)}\right)$ $\displaystyle\leq\sum_{i=1}^{m}\frac{3g_{t}}{p}\min\left(1,\sqrt{x_{i(k_{i})}( k_{i})^{\top}A_{i}^{-1}x_{i(k_{i})}(k_{i})}\right)$ $\displaystyle\leq\frac{3g_{t}}{p}\sqrt{\sum_{i=1}^{m}1\times\sum_{i=1}^{m}\min \left(1,x_{i(k_{i})}(k_{i})^{\top}A_{i}^{-1}x_{i(k_{i})}(k_{i})\right)}$ $\displaystyle\leq\frac{3g_{t}}{p}\sqrt{2dT\ln\left(1+T\right)},$ $$

For the second term $I_{2}$, according to the definition for weight $w_{k}<1$ in Algorithm 1 , we have $w_{k}=\gamma/\sqrt{x_{i(k)}(k)^{\top}B_{k}^{-1}x_{i(k)}(k)}$, which implies that

$$ $\displaystyle I_{2}$ $\displaystyle=\sum_{k:w_{k}<1}\min\left(1,\frac{3g_{t}}{p}\sqrt{x_{i(k)}(k)^{ \top}B_{i(k)}^{-1}x_{i(k)}(k)}\right)$ $\displaystyle=\sum_{k:w_{k}<1}\min\left(1,\frac{3g_{t}}{p}w_{k}x_{i(k)}(k)^{ \top}B_{i(k)}^{-1}x_{i(k)}(k)/\gamma\right)$ $\displaystyle\leq\sum_{k:w_{k}<1}\min\left((1+\frac{3g_{t}}{p\gamma}),(1+\frac {3g_{t}}{p\gamma})w_{k}x_{i(k)}(k)^{\top}B_{i(k)}^{-1}x_{i(k)}(k)\right)$ $\displaystyle=\sum_{k:w_{k}<1}(1+\frac{3g_{t}}{p\gamma})\min\left(1,w_{k}x_{i( k)}(k)^{\top}B_{i(k)}^{-1}x_{i(k)}(k)\right)$ $$

where the first equation holds due to the definition of weight $w_{k}$. Now, we assume the rounds with weight $w_{k}<1$ can be listed as $\left\{k_{1},\cdots,k_{m}\right\}$ for simplicity. In addition, we introduce the auxiliary vector $x_{i}^{\prime}$ as $x_{i}^{\prime}=\sqrt{w_{k_{i}}}x_{i(k_{i})}(k_{i})$ and matrix $B_{i}^{\prime}$ as

$$ $B_{i}^{\prime}=\lambda I+\sum_{j=1}^{i-1}w_{k_{j}}x_{i(k_{j})}(k_{j})x_{i(k_{j })}(k_{j})^{\top}=\lambda I+\sum_{j=1}^{i-1}x_{j}^{\prime}\left(x_{j}^{\prime} \right)^{\top}.$ $$

We have $\left(B_{i}^{\prime}\right)^{-1}\succeq B_{i}^{-1}$. Therefore, for each $i\in[m]$, we have

$$ $x_{i(k_{i})}(k_{i})^{\top}\left(B_{i}^{\prime}\right)^{-1}x_{i(k_{i})}(k_{i}) \geq x_{i(k_{i})}(k_{i})^{\top}B_{i}^{-1}x_{i(k_{i})}(k_{i})$ $$

Now we have

$$ $\displaystyle\sum_{i=1}^{m}\min\left(1,w_{k_{i}}x_{i(k_{i})}(k_{i})^{\top}B_{i (k_{i})}^{-1}x_{i(k_{i})}(k_{i})\right)$ $\displaystyle\leq\sum_{i=1}^{m}\min\left(1,w_{k_{i}}x_{i(k_{i})}(k_{i})^{\top} (B_{i}^{\prime})^{-1}x_{i(k_{i})}(k_{i})\right)$ $\displaystyle=\sum_{i=1}^{m}\min\left(1,\left(x_{i}^{\prime}\right)^{\top} \left(B_{i}^{\prime}\right)^{-1}x_{i}^{\prime}\right)$ $\displaystyle\leq 2d\ln\left(1+T\right),$ $$

Then we have

$$ $\displaystyle I_{2}$ $\displaystyle\leq\sum_{k:w_{k}<1}(2+\frac{3g_{t}}{p\gamma})\min\left(1,w_{k}x_ {i(k_{i})}(k_{i})^{\top}B_{i(k_{i})}^{-1}x_{i(k_{i})}(k_{i})\right)$ $\displaystyle\leq 2d(1+\frac{3g_{t}}{p\gamma})\ln\left(1+T\right).$ $$

Recalling the definitions of $p$ and $g_{T}$, by definition $g_{T}=O\left(d\sqrt{\ln\left(\frac{T}{\delta}\right)}+C\gamma\right)$. Substituting the above, we get

$$ $\displaystyle\sum_{t=1}^{T}\operatorname{regret}^{\prime}(t)$ $\displaystyle=O\left(e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}\left(d\sqrt{\ln\left (\frac{T}{\delta}\right)}+C\gamma\right)\cdot\sqrt{dT\ln T}+e^{(1+\frac{C \gamma}{\sqrt{d}})^{2}}\left(d\sqrt{\ln\left(\frac{T}{\delta}\right)}+C\gamma \right)\frac{d}{\gamma}\ln T+2d\ln T\right)$ $\displaystyle=O\left(de^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}\sqrt{dT\ln T\ln \left(\frac{T}{\delta}\right)}+C\gamma e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}} \sqrt{dT\ln T}+\frac{d^{2}e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}}{\gamma}\ln T \sqrt{\ln\left(\frac{T}{\delta}\right)}+Cde^{(1+\frac{C\gamma}{\sqrt{d}})^{2}} \ln T\right)$ $$

Also, because $E^{\mu}(t)$ holds for all $t$ with probability at least $1-\frac{\delta}{2}$ (see Lemma B.2), $\operatorname{regret}^{\prime}(t)=\operatorname{regret}(t)$ for all $t$ with probability at least $1-\frac{\delta}{2}$. Hence, with probability $1-\delta$,

$$ $\displaystyle\mathcal{R}(T)=\sum_{t=1}^{T}\operatorname{regret}(t)=\sum_{t=1}^ {T}\operatorname{regret}^{\prime}(t)$ $\displaystyle=O\left(de^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}\sqrt{dT\ln T\ln \left(\frac{T}{\delta}\right)}+C\gamma e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}} \sqrt{dT\ln T}+\frac{d^{2}e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}}{\gamma}\ln T \sqrt{\ln\left(\frac{T}{\delta}\right)}+Cde^{(1+\frac{C\gamma}{\sqrt{d}})^{2}} \ln T\right).$ $$

Choose $\gamma=\sqrt{d}/C$, its regret can be upper bounded by $\mathcal{R}(T)=O\left(d\sqrt{dT\ln T\ln\left(\frac{T}{\delta}\right)}+Cd\sqrt{
d}\ln T\sqrt{\ln\left(\frac{T}{\delta}\right)}\right)$.

∎

###### Definition B.1 (Saturated Arm) .

###### Lemma B.2 .

###### Lemma B.3 .

###### Definition B.4 .

###### Definition B.5 .

###### Lemma B.6 .

###### Proof of Theorem 5.1 .

### B.2 Proof of Lemma B.2

###### Proof.

First, the probability bound for $E^{\mu}(t)$ can be directly obtained from Lemma 1 in Agrawal & Goyal ().

Now we bound the probability of event $E^{\mu}(t)$. We use Lemma C.3 with $m_{t}=\sqrt{w_{t}}x_{i(t)}(t),\epsilon_{t}=\sqrt{w_{t}}(r^{0}_{i(t)}(t)-$ $x_{i(t)}(t)^{T}\mu),\mathcal{F}_{t}^{\prime}=\left(a(s+1),m_{s+1},\epsilon_{s}
:s\leq t\right)$. By the definition of $\mathcal{F}_{t}^{\prime},m_{t}$ is $\mathcal{F}_{t-1}^{\prime}$-measurable, and $\epsilon_{t}$ is $\mathcal{F}_{t}^{\prime}$-measurable. $\epsilon_{t}$ is conditionally $\sigma$-sub-Gaussian due to $\sqrt{w_{t}}\leq 1$ and the problem setting, and is a martingale difference process:

$$ $\displaystyle\mathbb{E}\left[\sqrt{w_{t}}\epsilon_{t}\mid\mathcal{F}_{t-1}^{ \prime}\right]=\mathbb{E}\left[\sqrt{w_{t}}r^{0}_{i(t)}(t)\mid x_{i(t)}(t),i(t )\right]-\sqrt{w_{t}}x_{i(t)}(t)^{T}\mu=0$ $$

We denote

$$ $\begin{gathered}M_{t}=I_{d}+\sum_{s=1}^{t}m_{s}m_{s}^{T}=I_{d}+\sum_{s=1}^{t}w _{t}x_{i(s)}(s)x_{i(s)}(s)^{T}\\ \xi_{t}=\sum_{s=1}^{t}m_{s}\epsilon_{s}=\sum_{s=1}^{t}w_{t}x_{i(s)}(s)\left(r^ {0}_{i(s)}-x_{i(s)}(s)^{T}\mu\right)\end{gathered}$ $$

Note that $B(t)=M_{t-1}$, and $\hat{\mu}(t)-\mu=M_{t-1}^{-1}\left(\xi_{t-1}-\mu+\sum_{s=1}^{t}w_{s}x_{i(s)}(s
)c_{s}\right)$. Let for any vector $y\in\mathbb{R}$ and matrix $A\in\mathbb{R}^{d\times d},\|y\|_{A}$ denote $\sqrt{y^{T}Ay}$. Then, for all $i$,

$$ $\displaystyle\left|x_{i}(t)^{T}\hat{\mu}(t)-x_{i}(t)^{T}\mu\right|$ $\displaystyle=\left|x_{i}(t)^{T}M_{t-1}^{-1}\left(\xi_{t-1}-\mu+\sum_{s=1}^{t} w_{s}x_{i(s)}(s)c_{s}\right)\right|$ $\displaystyle\leq\left\|x_{i}(t)\right\|_{M_{t-1}^{-1}}||\xi_{t-1}-\mu+\sum_{s =1}^{t}w_{s}x_{i(s)}(s)c_{s}\|_{M_{t-1}^{-1}}$ $\displaystyle\leq(\|\xi_{t-1}-\mu\|_{M_{t-1}^{-1}}+\sum_{s=1}^{t}|w_{s}||c_{s} |\|x_{i(s)}(s)\|_{B(t)^{-1}})$ $\displaystyle\left\|x_{i}(t)\right\|_{B(t)^{-1}}$ $$

The inequality holds because $M_{t-1}^{-1}$ is a positive definite matrix. Using Lemma C.3 , for any $\delta^{\prime}>0,t\geq 1$, with probability at least $1-\delta^{\prime}$,

$$ $\left\|\xi_{t-1}\right\|_{M_{t-1}^{-1}}\leq\sigma\sqrt{d\ln\left(\frac{t}{ \delta^{\prime}}\right)}$ $$

Therefore, $\|\xi_{t-1}-\mu\|_{M_{t-1}^{-1}}\leq R\sqrt{d\ln\left(\frac{t}{\delta^{\prime}
}\right)}+\|\mu\|_{M_{t-1}^{-1}}\leq$ $R\sqrt{d\ln\left(\frac{t}{\delta^{\prime}}\right)}+1$.
By the definition of $w_{k}$, we also note that $\sum_{s=1}^{t}|w_{s}||c_{s}|\|x_{i(s)}(s)\|_{B_{t}^{-1}}\leq\gamma\sum_{s=1}^{
t}|c_{s}|\leq C\gamma$. Substituting $\delta^{\prime}=\frac{\delta}{t^{2}}$, we get that with probability $1-\frac{\delta}{t^{2}}$, for all $i$,

$$ $\displaystyle\left|x_{i}(t)^{T}\hat{\mu}(t)-x_{i}(t)^{T}\mu\right|\leq$ $\displaystyle\left\|x_{i}(t)\right\|_{B(t)^{-1}}\cdot\left(R\sqrt{d\ln\left( \frac{t}{\delta^{\prime}}\right)}+1+C\gamma\right)$ $\displaystyle\leq$ $\displaystyle\left\|x_{i}(t)\right\|_{B(t)^{-1}}\cdot\left(R\sqrt{d\ln\left(t^ {3}\right)\ln\left(\frac{1}{\delta}\right)}+1+C\gamma\right)$ $\displaystyle=$ $\displaystyle\ell(t)s_{i}(t).$ $$

This proves the bound on the probability of $E^{\mu}(t)$.
∎

###### Proof.

### B.3 Proof of Lemma B.3

###### Proof.

Given event $E^{\mu}(t),\left|x_{i^{*}(t)}(t)^{T}\hat{\mu}(t)-x_{i^{*}(t)}(t)^{T}\mu\right|\leq$ $\ell_{t}s_{t,i^{*}(t)}(t)$. And, since Gaussian random variable $\theta_{i^{*}(t)}(t)$ has mean $x_{i^{*}(t)}(t)^{T}\hat{\mu}(t)$ and standard deviation $v_{t}s_{i^{*}(t)}(t)$, using Lemma C.1,

$$ $\displaystyle\operatorname{Pr}\left(\theta_{i^{*}(t)}(t)\geq x_{i^{*}(t)}(t)^{ T}\mu\mid\mathcal{F}_{t-1}\right)$ $\displaystyle=$ $\displaystyle\operatorname{Pr}\left(\frac{\theta_{i^{*}(t)}(t)-x_{i^{*}(t)}(t) ^{T}\hat{\mu}(t)}{v_{t}s_{t,i^{*}(t)}}\right.$ $\displaystyle\left.\geq\frac{x_{i^{*}(t)}(t)^{T}\mu-x_{i^{*}(t)}(t)^{T}\hat{ \mu}(t)}{v_{t}s_{t,i^{*}(t)}}\mid\mathcal{F}_{t-1}\right)$ $\displaystyle\geq$ $\displaystyle\frac{1}{4\sqrt{\pi}}e^{-Z_{t}^{2}}$ $$

where

$$ $\displaystyle\left|Z_{t}\right|$ $\displaystyle=\left|\frac{x_{i^{*}(t)}(t)^{T}\mu-x_{i^{*}(t)}(t)^{T}\hat{\mu}( t)}{v_{t}s_{i^{*}(t)}(t)}\right|$ $\displaystyle\leq\frac{\ell_{t}s_{i^{*}(t)}(t)}{v_{t}s_{i^{*}(t)}(t)}$ $\displaystyle=\frac{\left(\sigma\sqrt{d\ln\left(\frac{t^{3}}{\delta}\right)}+1 +C\gamma\right)}{\sigma\sqrt{9d\ln\left(\frac{t}{\delta}\right)}}$ $\displaystyle\leq 1+\frac{C\gamma}{\sqrt{d}}$ $$

So

$$ $\operatorname{Pr}\left(\theta_{i^{*}(t)}(t)\geq x_{i^{*}(t)}(t)^{T}\mu\mid \mathcal{F}_{t-1}\right)\geq\frac{1}{4e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}} \sqrt{\pi}}$ $$

∎

###### Proof.

### B.4 Proof of Lemma B.6

###### Lemma B.7 .

For any filtration $\mathcal{F}_{t-1}$ such that $E^{\mu}(t)$ is true,

$$ $\operatorname{Pr}\left(i(t)\notin C(t)\mid\mathcal{F}_{t-1}\right)\geq p-\frac {1}{t^{2}}.$ $$

This Lemma is from Lemma 4 in Agrawal & Goyal (). By using the Lemma B.2, we get that when both events $E^{\mu}(t)$ and $E^{\theta}(t)$ hold, for all $j\in C(t),\theta_{j}(t)\leq b_{j}(t)^{T}\mu+g_{t}s_{t,j}$. Also, by Lemma B.3, we have that if $E^{\mu}(t)$ is true,$\operatorname{Pr}\left(\theta_{i^{*}(t)}(t)>x_{i^{*}(t)}(t)^{T}\mu\mid\mathcal
{F}_{t-1}\right)\geq p$. Then directly following the proof of Lemma 3 in Agrawal & Goyal () we can obtain our result.

###### Lemma B.8 .

For any filtration $\mathcal{F}_{t-1}$ such that $E^{\mu}(t)$ is true,

$$ $\mathbb{E}\left[\Delta_{i(t)}(t)\mid\mathcal{F}_{t-1}\right]\leq\min\{\frac{3g _{t}}{p}\mathbb{E}\left[s_{i(t)}(t)\mid\mathcal{F}_{t-1}\right]+\frac{2g_{t}}{ pt^{2}},1\}$ $$

This Lemma is from Lemma 4 in Agrawal & Goyal (). Using Lemma B.7, for any $\mathcal{F}_{t-1}$ such that $E^{\mu}(t)$ is true, we have $\operatorname{Pr}\left(i(t)\notin C(t)\mid\mathcal{F}_{t-1}\right)\geq p-\frac
{1}{t^{2}}=\frac{1}{4e^{(1+\frac{C\gamma}{\sqrt{d}})^{2}}\sqrt{\pi}}-\frac{1}{
t^{2}}$. Also, by Lemma B.2 we have that on the events $E^{\mu}(t)$ and $E^{\theta}(t)$, $\theta_{i}(t)\leq$ $x_{i}(t)^{T}\mu+g_{t}\|x_{i}(t)\|_{B(t)^{-1}}$. Using these two facts, by directly following the proof in Lemma 4 of Agrawal & Goyal () we immediately obtain our needed result.

###### Proof.

We need to prove that for all $t\in[1,T]$, and any $\mathcal{F}_{t-1},\mathbb{E}\left[Y_{t}-Y_{t-1}\mid\mathcal{F}_{t-1}\right]\leq
0$, i.e.

$$ $\mathbb{E}\left[\operatorname{regret}^{\prime}(t)\mid\mathcal{F}_{t-1}\right] \leq\min\{\frac{3g_{t}}{p}\mathbb{E}\left[s_{i(t)}(t)\mid\mathcal{F}_{t-1} \right]+\frac{2g_{t}}{pt^{2}},1\}$ $$

Note that whether $E^{\mu}(t)$ is true or not is completely determined by $\mathcal{F}_{t-1}$. If $\mathcal{F}_{t-1}$ is such that $E^{\mu}(t)$ is not true, then $\operatorname{regret}^{\prime}(t)=\operatorname{regret}(t)\cdot I\left(E^{\mu}
(t)\right)=0$, and the above inequality holds trivially. And, for $\mathcal{F}_{t-1}$ such that $E^{\mu}(t)$ holds, the inequality follows from Lemma B.8.
∎

###### Lemma B.7 .

###### Lemma B.8 .

###### Proof.

## Appendix C Inequalities

###### Lemma C.1 .

For a Gaussian distributed random variable $Z$ with mean $m$ and variance $\sigma^{2}$, for any $z\geq 1$,

$$ $\frac{1}{2\sqrt{\pi}z}e^{-z^{2}/2}\leq\operatorname{Pr}(|Z-m|>z\sigma)\leq \frac{1}{\sqrt{\pi}z}e^{-z^{2}/2}.$ $$

###### Lemma C.2 (Azuma-Hoeffding inequality) .

If a super-martingale $\left(Y_{t};t\geq 0\right)$, corresponding to filtration $\mathcal{F}_{t}$, satisfies $\left|Y_{t}-Y_{t-1}\right|\leq c_{t}$ for some constant $c_{t}$, for all $t=1,\ldots,T$, then for any $a\geq 0$,

$$ $\operatorname{Pr}\left(Y_{T}-Y_{0}\geq a\right)\leq e^{-\frac{a^{2}}{2\sum_{t= 1}^{T}c_{t}^{2}}}$ $$

###### Lemma C.3 ( Abbasi-Yadkori et al. ( 2011 ) ) .

Let $\left(\mathcal{F}_{t}^{\prime};t\geq 0\right)$ be a filtration, $\left(m_{t};t\geq\right.$ 1) be an $\mathbb{R}^{d}$-valued stochastic process such that $m_{t}$ is $\left(\mathcal{F}_{t-1}^{\prime}\right)$-measurable, $\left(\eta_{t};t\geq\right.$ 1) be a real-valued martingale difference process such that $\eta_{t}$ is $\left(\mathcal{F}_{t}^{\prime}\right)$-measurable. For $t\geq 0$, define $\xi_{t}=\sum_{\tau=1}^{t}m_{\tau}\eta_{\tau}$ and $M_{t}=I_{d}+\sum_{\tau=1}^{t}m_{\tau}m_{\tau}^{T}$, where $I_{d}$ is the d-dimensional identity matrix. Assume $\eta_{t}$ is conditionally $R$-sub-Gaussian.
Then, for any $\delta^{\prime}>0,t\geq 0$, with probability at least $1-\delta^{\prime}$,

$$ $\left\|\xi_{t}\right\|_{M_{t}^{-1}}\leq R\sqrt{d\ln\left(\frac{t+1}{\delta^{ \prime}}\right)},$ $$

where $\left\|\xi_{t}\right\|_{M_{t}^{-1}}=\sqrt{\xi_{t}^{T}M_{t}^{-1}\xi_{t}}$.

###### Lemma C.1 .

###### Lemma C.2 (Azuma-Hoeffding inequality) .

###### Lemma C.3 ( Abbasi-Yadkori et al. ( 2011 ) ) .

### C.1 Thompson Sampling Algorithms

Figure: Algorithm 3 Thompson Sampling for Stochastic Bandits

Figure: Algorithm 4 Thompson Sampling for Linear Contextual Bandits

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. what does not mean of "optimality in the face of corruption" in line 65?

2. In line 795, the constant is 72 e^{64}. You can improve the constant by using some analysis in https://arxiv.org/abs/2407.14879.

Also, I think the aforementioned paper is quite related to this work.
soundness: 2
strengths: a new problem
summary: This work studies the setting where the revealed rewards are corrupted. So, the learning agent cannot use the true reward to do posterior sampling. They consider two bandit variants with corruption: stochastic bandit and linear contextual bandit. They also propose efficient algorithms.
weaknesses: problem set up: I still think the proposed problem is a special case (actually a simpler case) of differentially private online learning, based on lines 149 to 151. 

proposed algorithms: they is not that interesting nor novel, simply re-shaping the posterior distribution in an optimistic way. This idea has been used in Hu and Hedge, 2022.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: What can be said about Bayesian regret?
soundness: 4
strengths: This is the first work providing variants of Thompson sampling for this class of problems.
Proposed algorithms are near-optimal and, being based on Thompson sampling, they inherit the advantages of Thompson sampling over approaches based on optimism in face of uncertainty.
summary: This paper proposes first near-optimal variants of Thompson sampling for stochastic bandit and contextual linear bandit problems with adversarial reward poisoning.
weaknesses: Previous works are mentioned in the introduction and related works section. However, comparing existing results requires finding each cited paper and going through them one by one. It would be better if a table was included with previous works.

typos:
At the end of Sections 4 and 5, the paper (He et al., 2022) should be cited instead of (He et al., 2023).

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: I did not fully follow the intuition behind Algorithm 2 and the corresponding proof sketch. More specifically, it would be helpful if the authors elaborated further on their two remarks:
- *...the attacker can apply less influence on the estimator by corrupting such data...*, 
- *...variance of the posterior distribution is limited due to the weighted estimator under reward poisoning...* 

Please see *Strengths* and *Weaknesses* for my other comments and questions.
soundness: 3
strengths: - The paper is interesting and enjoyable to read. It clearly explains the most important ideas and positions its contributions well with respect to prior work on corruption-robust bandits.
- To my knowledge, prior work has not studied Thompson sampling algorithms that are robust to reward poisoning attacks. The proof techniques in the paper appear to be standard, but I found the analysis non-trivial. While I didn't check all the proofs in great detail, the arguments provided in the proof sketches appear sound.
- The proposed algorithms are simple extensions of existing methods and are based on adjusting the posteriors to make them less susceptible to manipulation. The upper bounds on the regret of the proposed algorithms are near-optimal, as argued in the paper, with the arguments relying on the lower bounds from prior work. 
- The paper supports its theoretical results with experiments.
summary: This paper considers poisoning attacks in multi-armed bandit setting. More specifically, the authors consider Thompson sampling algorithms and aim to design corruption-robust versions of these algorithms. They propose two algorithms, for stochastic and contextual linear settings, respectively, robust to poisoning attacks against an attacker that has limited corruption budget. The authors argue that their results are near-optimal, and they provide simulation results comparing their approaches to validate their theoretical findings.
weaknesses: - While I found the results interesting, they are also somewhat expected, given the findings from prior work on poisoning attacks and corruption robustness in bandits.
- The experiments related to the stochastic MAB setting do not include a corruption-robust baseline. For the contextual bandit setting, the performance of the proposed method is similar to the corruption-robust baseline but is often worse. It would also be useful to include a richer set of attack strategies in the experiments.
- While I believe that the paper is overall well-written, the presentation could be improved and polished. There are quite a few typos in the text, and some of the figures in the experimental section do not adequately label the axes on the plots (see Figs. 2 and 4). Moreover, the fonts in the figures are too small. It also seems that some references are cited incorrectly. For example, the paper frequently cites He et al. (2023), which appears to be about *Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes*. It would be helpful if the authors clarified this.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 1
questions: Here is a list of suggestions for the authors. 

- The first suggestion would be to entirely rewrite the proofs of Theorem 4.1 and Theorem 5.1 in the Appendix. Make sure to properly introduce all the notation with clear definitions to justify all the steps in your proofs (equalities, inequalities, the use of some lemma,….) to provide reference to all the lemmata you borrow from previous work. To the best of your capacity, try to write the proofs in a pedagogical way such that a reader familiar with the work can easily follow and asses the steps in the reasoning. 
- The second suggestion is for the authors to verify and clarify the omission in the last step of Theorem 4.1’s proof regarding the summation over all arms.
\item The third suggestion is for the authors to provide more details supporting their claim that the algorithm and regret bounds can be extended to general priors. If this is not possible, the authors would have to change the title, abstract, and introduction to acknowledge the limited scope of the work. 
\item A fourth suggestion concerns the experimental results. For the Gaussian stochastic bandit setting, the authors should compare the performance of the first suggested algorithm against a competitive, robust algorithm. Also, the authors should provide a detailed description of the adversarial attacks used in the experiments. Also, the authors should address the following issues in Figures 1 and 2:
   - are the data in the left and right plots of Figure 1 indeed distinct?
   - why the expected regret of TS is nearly identical to UCB?
   - clarification on the expected regret’s decrease as the adversarial budget increases on Figure 3.
   - the authors should explain the level of confidence for the plotted intervals. 
   - finally, the authors should provide commented code with a description of the different files and functions and a readme.txt file so that a reviewer can reproduce the experiments quickly. 
- A fifth suggestion would be for the authors to avoid using generative tools to write articles. It is frustrating for a reviewer to question whether they have spent more time writing a review than the author to write their paper.
soundness: 2
strengths: The main strength of the paper is to propose modifications to the Thompson Sampling algorithm to mitigate the effects of adversarial reward attacks.
summary: This paper studies the performance of Thompson Sampling for stochastic Gaussian bandits and contextual Gaussian $d$-dimensional linear bandit problems with Gaussian prior. Starting from the prior distribution over the "reward-parameter", the Thompson Sampling algorithm works by randomly selecting actions according to their posterior probability of being optimal. More specifically, at each time step, it samples a "reward-parameter" estimate from the posterior distribution conditioned on the history and selects the optimal action for the sampled parameter estimate given the context.  

In this work, the authors study the case where the rewards can be corrupted by an adversary with full knowledge of the "reward-parameter", the history, the current context and the random reward before attack. The adversary perturbs the reward with an additive perturbation. The sum of absolute perturbation, $C$, is referred to as the budget of the attack or the corruption level and is assumed to be finite. The authors propose two modifications of the Thompson Sampling to mitigate the effects of the adversarial attacks on the algorithm's performance. The first algorithm, developed for Gaussian stochastic bandits with Gaussian prior, uses an optimistic biased distribution over the reward-parameters to compensate for potential reward attacks. The authors claim that they have derived a bound of order $O(\sqrt{NT \log(N)} + N\overline{C} + N)$ on the expected regret, where $N$ is the number of arms, $T$ is the number of time steps and $\overline{C}$ is the "robustness level", a parameter of the algorithm that is assumed to be greater than $C$. It has to be noted that the constant term in the bounds is of the order $10^{29}$. 

The second algorithm, developed for contextual Gaussian $d$-dimensional linear bandit problems with Gaussian prior,  works by weighting the posteriors updates inversely proportional to the weighted 2-norm of the current context.  The authors derive a probabilistic bound on the expected regret. 


The authors then perform experiments to demonstrate the performance of their modified Thompson Sampling algorithms. The first experiment compares the performance of their first algorithm against UCB and TS for Gaussian stochastic bandits with Gaussian priors. The second experiment compares the performance of their first algorithm against UCB and TS for contextual Gaussian $d$-dimensional linear bandit problems with Gaussian prior.
weaknesses: Although adapting the Thompson Sampling to adversarial reward attacks is an interesting idea, the paper suffers from several weaknesses listed below (the order does not reflect a hierarchy in the severity of the weaknesses).

 - The first weakness concerns the considered settings. The authors considered a very limited settings as they assume that "the priors for the rewards of the arms and the reward parameters are Gaussian distributions" [lines 172-173]. They later claim that their algorithm can be "in principle" extended to general priors without giving any detail or example to support their claim. More problematic, their derived regret bounds (Theorem 4.1 and 5.1) rely extensively on those assumptions and do not hold for general priors. This limitation regarding the scope of the paper needs to be included in the title, the abstract, and the introduction. 
 - A second weakness concerns the result derived in Theorem 4.1. Following the last part of the proof in the Appendix, the authors forgot to sum over all the possible $ N $ arms. Taking the sum over all possible arms leads to a regret bound of order $O(N^{3/2}\sqrt{T \log(N)} + N^{2}\overline{C} + N^{2})$. Another concern regarding the regret bound is the enormous multiplicative constant $72(e^{64}+5) \approx 10^{29}$, which raises the question of whether this bound can be applicable in practice. 
- Another weakness concerns the clarity of the paper and the presentation of the proofs. Notations are at best cumbersome (e.g., $x_{i(t)}(t)^T\mu$), sometimes incoherent (e.g., the history denoted $H_{t-1}$ in the paper and later changed to $F_{t-1}$ in the appendix, mixing notations $\theta$ and $\Theta$), incomplete (e.g., summation symbols without above limit $\sum_{t=1}$ [line 133]), or simply not defined (e.g., $\tau_k$, $\Delta_i$, $\overline{E_i^\theta(t)}$, $\overline{E_i^\mu}(t)$, $c_s$, $L_i(T)$). This seriously hinders the clarity of the paper and the ability to evaluate the proof's correctness. Although the single column allows enough space to write on a single line, authors often split equations or even expressions. Examples can be found on lines 311 to 315 or 684 to 690. The authors also use overfull lines, such as on line 1033. Often, proofs consist simply of a long chain of equalities and inequalities with no justification given to the reader. Sometimes, the authors cite results from previous papers without providing any reference.  Overall, the appendix seems to have been written to discourage readers or make it impossible for them to verify the proof.  
- One more weakness concerns the writing of the paper. This reviewer believes that at least parts of the paper have been written by generative AI tools. Indeed, parts of the paper present typical AI writing patterns, such as repetition of ideas and phrases, overuse of specific writing structures, and generic or high-level descriptions. One example is in the introduction between lines 36 and 47:
    "[...]Thompson sampling has several advantages:
  - Utilizing prior information: By design, Thompson sampling algorithms utilize and benefit from the prior information about the arms.
  - Easy to implement: While the regret of a UCB algorithm depends critically on the specific choice of upper-confidence bound, Thompson sampling depends only on the best possible choice. This becomes an advantage when there are complicated dependencies among actions, as designing and computing with appropriate upper confidence bounds present significant challenges Russo et al. (2018). In practice, Thompson sampling is usually easier to implement Chapelle \& Li (2011).
  - Stochastic exploration: Thompson sampling is a random exploration strategy, which could be more resilient under some bandit settings Lancewicki et al. (2021).
    Despite the success, Thompson sampling faces the problem of [...]"

- Another weakness concerns the experiments performed by the authors. First, one can deplore that the adversarial attacks are not explained. Second, for the stochastic bandit experiment, one can regret that the proposed algorithms are not compared against any other robust algorithm from the literature. Third, the plotted results raise serious questions regarding the quality of the experiments:  
  - on Figure 1, the left and right plots seem to present the same data although their respective titles claim otherwise.
  - on Figure 1 and Figure 2, the expected regret of TS seems not just close but almost exactly equal to the expected regret of UCB. 
  - on the top part of Figure 2, the titles of the $x$-axes are almost not readable.
  - on the bottom part of Figure 2, it seems impossible to explain how the expected regret of the proposed algorithm can decrease when the adversarial budget increases. This strongly suggests that there is a mistake in the experiments.
  - another incoherence in the displayed results that indicated an error in the experiments is the fact that on the top part of Figure 2, the robust version of Thompson Sampling seems to outperform the original Thompson Sampling and UCB algorithm \emph{even with no adversarial attack} (when the adversarial budget is $0$). This simple \emph{sanity check} strongly suggests some mistakes in the code. 
  - there seem to be confidence intervals associated to each point on the plots but no information is given about the level of confidence they represent. 
  - the code for running the experiments is provided without a readme.txt file, or a single comment explaining how to run the code or what is the purpose of the different files and functions. It was therefore not possible to verify the soundness of the experiments.

Meta-review: This paper examines modified Thompson Sampling algorithms for Gaussian bandits and contextual linear bandits with Gaussian priors, focusing on mitigating adversarial attacks that perturb rewards. The first modification introduces an optimistic biased distribution for Gaussian stochastic bandits, while the second adjusts posterior updates for contextual linear bandits based on the current context. Both methods aim to reduce expected regret under adversarial conditions. Experiments show the effectiveness of these modifications compared to UCB and Thompson Sampling.

While the effort put by the authors to improve the paper is commendable, as pointed out by the reviewers, it's hard to judge the correctness of the proofs and efficacy of the results with these many modifications. Moreover, there are remaining concerns about the correctness of the proofs and the nature of the empirical results (e.g., Fig 3), which are non-intuitive. Based on these, I suggest that the authors submit to the next suitable venue after incorporating all the reviewer feedback.

Decision: Reject