{Attack as if $\tilde x$ is the best}
        \STATE Bandit algorithm observes modified reward $\tilde r_t$
       
    \ENDFOR

        \STATE Estimate $\tilde\mathrm{\boldsymbol{\theta}}_\parallel =   \frac{\sum_{i=1}^{n(\tilde x)} r_i(\tilde x)}{n(\tilde x)\Vert\tilde x\Vert_2^2}\tilde x $  
        \STATE Solve CQP \eqref{lp:attackability} using $\tilde\mathrm{\boldsymbol{\theta}}_\parallel$ to obtain the estimated attackability index $\tilde\epsilon^*$ and certificate $\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp}$ 
        \IF[Attackability test]{$\tilde\epsilon^*\leq 0$} 
        \STATE \textbf{return} Not attackable
    \ELSE[Attack stage] 
        \STATE Set $\tilde\mathrm{\boldsymbol{\theta}} = \tilde\mathrm{\boldsymbol{\theta}}_\parallel+\tilde\mathrm{\boldsymbol{\theta}}_\perp$
    \FOR{$t=T_1+1$ to $T$ }
    \IF{ $x_{a_t} \neq \tilde x$}  
            \STATE Set $\tilde r_t = x_{a_t}^\mathsf{T} \tilde\mathrm{\boldsymbol{\theta}} + \tilde\eta_t$
        \ELSIF{$x_{a_t} = \tilde x$ for the first time}
        \STATE Set $\tilde r_t = n(\tilde x) \times \tilde x^\mathsf{T}  (\tilde\mathrm{\boldsymbol{\theta}} - \mathrm{\boldsymbol{\theta}}_0) + \tilde x^\mathsf{T} \tilde\mathrm{\boldsymbol{\theta}} + \tilde\eta_t$ 
        \ELSE
        \STATE Set $\tilde r_t = r_t$
        \ENDIF
        \STATE Bandit algorithm observes modified reward $\tilde r_t$
    \ENDFOR
    \ENDIF
    \end{algorithmic}
\end{algorithm}

Note that our attackability test might make both false positive and false negative assertions due to the estimation error in  $\tilde\mathrm{\boldsymbol{\theta}}_\parallel$. But as $T$ becomes larger, the estimate gets more accurate and the assertion is correct with   high probability.

\begin{remark} We acknowledge that the rewards from the two stages follow different reward distributions and could be detected, e.g., using some homogeneity test \citep{li2021unifying}. Thus a bandit player could realize the attack if equipped with some change detector. However, attacking such a cautious bandit algorithm is beyond the scope of this paper. 
Moreover, it is very difficult (if not impossible) to attack with a stationary reward distribution or undetectable perturbations (e.g., using a fixed target parameter $\tilde\theta$). We could easily find cases where the adversary's parameter $\tilde \theta$ is limited to extremely few choices and it is almost impossible to directly start the attack with a valid $\tilde \theta$ without knowing $\theta^*$. For example, if we change the third arm in Example 1 to $x_3 = (-1+\epsilon, 0)$ with a small $\epsilon$, we can see that the valid parameters are only in a small range around $\tilde \theta = (-1-\epsilon, 1)$. Therefore, in order to attack with a stationary reward distribution, the adversary needs to start from somewhere very close to $\tilde \theta = (-1-\epsilon, 1)$, which we believe is extremely difficult without knowing $\theta^*$. Overall, we think designing an attack strategy against a bandit algorithm with reward change detector or showing the inability to attack such cautious algorithms is an important future work of ours. 
\end{remark}

\paragraph{Attack against LinUCB.}  We now show how LinUCB algorithm can be attacked by Algorithm~\ref{alg:attack}.




\begin{theorem}\label{theorem:attackLinUCB}
For large enough $T_1$,  the attack strategy in Algorithm \ref{alg:attack}  will correctly assert the attackability with probability at least $1-\delta$. Moreover, when the environment is attackable, with probability at least $1-3\delta$ the attack strategy  will fool LinUCB to pull  non-target arms at most
\begin{equation*}
\begin{split}
O\Big(&d\big(\sqrt{\log(T/\delta)} + \sqrt{T_1}\log{(T_1/\delta)} \\&+ \sqrt{T\log(1/\delta)}/\sqrt{T_1}\big)\sqrt{T\log (T/\delta)}/\epsilon^*\Big)       
\end{split}
\end{equation*} 
rounds. And with probability at least $1-4\delta$, the adversary's cost is at most
\begin{equation*}
\begin{split}
O\Big(T_1 + &d\big(\sqrt{\log(T/\delta)} + \sqrt{T_1}\log{(T_1/\delta)} \\&+ \sqrt{T\log(1/\delta)}/\sqrt{T_1}\big)\sqrt{T\log (T/\delta)}/\epsilon^*\Big).
\end{split}
\end{equation*}
Specifically, when $T_1 = T^{1/2}$, the strategy gives the minimum attack cost in the order of $\tilde O(T^{3/4})$,
and the non-target arms are pulled at most $\tilde O(T^{3/4})$ rounds. 
\end{theorem}

\begin{proof}[Proof Sketch.]
To prove the the assertion is correct with high probability, the key idea is that the estimated $\tilde\mathrm{\boldsymbol{\theta}}_\parallel$ is close to the true parameter $\mathrm{\boldsymbol{\theta}}^*_\parallel$.
We first note that in the first stage, the bandit algorithm will pull the target arm $\tilde x$ $T_1 -O(\sqrt{T_1})$ times, since $\tilde x$ is the best arm according to $\mathrm{\boldsymbol{\theta}}_0$. According to the Hoeffding's inequality, the estimation error 
$\Vert\tilde\mathrm{\boldsymbol{\theta}}_\parallel -  \mathrm{\boldsymbol{\theta}}^*_\parallel \Vert_2 \leq \sqrt{\frac{2\log(2/\delta)}{T_1 -O(\sqrt{T_1})}}$. 
Therefore, with a large enough $T_1$, the error on $\tilde x$'s reward estimation is smaller than $\epsilon^*$. Thus solving CQP \eqref{lp:attackability} with $\tilde\mathrm{\boldsymbol{\theta}}_\parallel$ and we can correctly assert attackability with positive estimated index $\tilde\epsilon^*$ when the environment is attackable with index $\epsilon^*$. 

To prove the success and the cost of the attack, we need to analyze the behavior of LinUCB under the reward discrepancy  between the two stages.
Our proof crucially hinges on the following robustness result of LinUCB. 

\begin{lemma}\label{lemma:robustrness_ridgereg}
Consider LinUCB with ridge regression under poisoning attack. Let $S'_t = \sum_{\tau\in\{1 \dots t\}, x_{a_\tau}\neq\tilde x} |\Delta_\tau|$ be the total corruption on non-target arms until time $t$ and assume every corruption on target arm is bounded by $\gamma$. For any $t= 1 \dots T$, with probability at least $1-\delta$ we have 
 \begin{equation}
    \Vert \tilde\mathrm{\boldsymbol{\theta}}- \hat{\mathrm{\boldsymbol{\theta}}}_t\Vert _{A_t} \leq \alpha_t + S'_t/\sqrt{\lambda} + \gamma\sqrt{t}
 \end{equation} 
 where $\alpha_t = \sqrt{d\log\left(\frac{1+t/\lambda}{\delta}\right)} + \sqrt{\lambda}$.  
\end{lemma}

Based on this lemma, we can derive the regret $R_T(\tilde\mathrm{\boldsymbol{\theta}})$ of LinUCB with $\tilde\mathrm{\boldsymbol{\theta}}$ as the true parameter. The total corruption on non-target arms is $O\big(d\sqrt{T_1}\log{(T_1/\delta)}\big)$ given the rewards are generated by $\mathrm{\boldsymbol{\theta}}_0$ (the rewards of target arm in the first stage are compensated in line 20). Because the target arm's rewards are not attacked in the second stage and follows $\mathrm{\boldsymbol{\theta}}^*$, we have $\gamma = \tilde O(1/\sqrt{T_1})$.  Since the non-target arms are pulled at most $R_T(\tilde\mathrm{\boldsymbol{\theta}})/\epsilon^*$ rounds, substitute the total corruption back and we have the resulting bound. 

The attack cost has two sources: attacks in the first stage for $T_1$ times, and attacks on the non-target arms in the second stage. The second term has the same order as the number of rounds where the non-target arms are pulled by LinUCB. Each attack cost can be decomposed as 1) the change of mean reward $|x_a^\mathsf{T} (\tilde\mathrm{\boldsymbol{\theta}} - \mathrm{\