When Are Linear Stochastic Bandits Attackable?

In a contextual bandit problem, a learner takes sequential actions to interact with an environment to maximize its received cumulative reward. As a natural and important variant, linear stochastic bandits (Auer,, 2002; Li et al.,, 2010; Abbasi-yadkori et al.,, 2011) assume the expected reward of an arm $a$ is a linear function of its feature vector $x_{a}$ and an unknown bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$. A linear bandit algorithm thus adaptively improves its estimation of $\mathrm{\boldsymbol{\theta}}^{*}$ based on the reward feedback on its pulled arms. Thanks to their sound theoretical guarantees and promising empirical performance, linear stochastic bandits have become a reference solution to many real-world problems, such as content recommendation and online advertisement (Li et al.,, 2010; Chapelle and Li,, 2011; Durand et al.,, 2018).

Since bandit algorithms adapt their behavior according to its received feedback, such algorithms are susceptible to adversarial attacks, especially poisoning attacks. Under such an attack, a malicious adversary observes the pulled arm and its reward feedback, and then modifies the reward to misguide the bandit algorithm to pull a target arm, which is of the adversary’s interest. Due to the wide applicability of bandit algorithms in practice as mentioned before, understanding the robustness of such algorithms under poisoning attacks becomes increasingly important (Jun et al.,, 2018; Liu and Shroff,, 2019; Garcelon et al.,, 2020).

Most existing studies on adversarial attacks in bandits focused on the context-free stochastic multi-armed bandit (MAB) settings. Jun et al., (2018) and Liu and Shroff, (2019) showed that an adversary can force any MAB algorithm to pull a target arm linear times only using a logarithmic cost. Garcelon et al., (2020) showed the vulnerability of $k$-armed linear contextual bandits under poisoning attacks. Linear stochastic bandits are related to context-free stochastic bandits and linear contextual bandits. Interestingly, however, there is no known result about attacks on linear stochastic bandit until now. This paper shall provide a formal explanation for this gap — the analysis of attacks to linear stochastic bandits turns out to be significantly more challenging due to the correlation among arms; in fact, some learning environment is provably unattackable.

Specifically, we fill the aforementioned gap by studying poisoning attacks on $k$-armed linear stochastic bandits, where an adversary modifies the reward using a sublinear attack cost to misguide the bandit algorithm to pull a target arm $\tilde{x}$ linear times. We first show that a linear stochastic bandit environment is not always efficiently attackable¹¹1Throughout this paper, “efficient attack” means fooling the bandit algorithm to pull the target arm for linear times with a sublinear attack cost. We will use attackable and efficiently attackable interchangeably, as the adversary normally only has a limited budget and needs to design a cost-efficient strategy., and its attackability is governed by the feasibility of finding a parameter vector $\tilde{\mathrm{\boldsymbol{\theta}}}$, under which the rewards of all non-target arms are smaller than the reward of target arm $\tilde{x}$ and the reward of $\tilde{x}$ remains the same as that in the original environment specified by $\mathrm{\boldsymbol{\theta}}^{*}$. Intuitively, to promote the target arm $\tilde{x}$, an adversary needs to lower the rewards of non-target arms in the null space of $\tilde{x}$ by $\tilde{\mathrm{\boldsymbol{\theta}}}$, which might not be always feasible. We prove the feasibility of the resulting convex quadratic program is both sufficient and necessary for attacking a linear stochastic bandit environment.

Inspired by our attackability analysis, we propose a two-stage attack framework against linear stochastic bandit algorithms and demonstrate its application against LinUCB (Li et al.,, 2010) and Robust Phase Elimination (Bogunovic et al.,, 2021): the former is one of the most widely used linear contextual bandit algorithms, and the latter is a robust version designed for settings with adversarial corruptions. In the first stage, our method collects a carefully calibrated amount of rewards on the target arm to assess whether the given environment is attackable. The decision is based on an “empirical” version of our feasibility characterization. If attackable, i.e., there exists a feasible solution $\tilde{\mathrm{\boldsymbol{\theta}}}$, in the second stage the method depresses the rewards the bandit algorithm receives on non-target arms based on $\tilde{\mathrm{\boldsymbol{\theta}}}$, to fool the bandit algorithm to recognize the target arm as optimal. We prove that in an attackable environment, both algorithms can be successfully manipulated with only a sublinear cost.

Our main contributions can be summarized as follows:

• •

  We characterize the sufficient and necessary conditions about when a stochastic linear bandit environment is attackable as the feasibility of a convex quadratic program. En route to proving the sufficiency, we also provide an oracle attack method that can attack any no-regret learning algorithm given the knowledge of ground-truth bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$. If the environment is unattackable, i.e., the program is infeasible, our necessity proof implies that even the vanilla LinUCB algorithm cannot be efficiently attacked. A direct corollary of our characterization is that context-free stochastic MAB is always attackable, resonating the findings in (Jun et al.,, 2018; Liu and Shroff,, 2019).

• •

  We propose a two-stage attack method that works without the knowledge of ground-truth bandit parameter. In the first stage, the algorithm detects the attackability of the environment and estimates the model parameter. In the second stage, it solves for a working solution $\tilde{\mathrm{\boldsymbol{\theta}}}$ and attacks accordingly. Our theoretical analysis shows this attack method is effective against LinUCB (Li et al.,, 2010) and Robust Phase Elimination (Bogunovic et al.,, 2021), i.e., pulling the target arm $T-o(T)$ times using $o(T)$ cost when the environment is attackable.

Linear stochastic bandit. We study poisoning attacks to the fundamental $k$-armed linear stochastic bandit problem (Auer,, 2002), where a bandit algorithm sequentially interacts with an environment for $T$ rounds. In each round $t$, the algorithm pulls an arm $a_{t}\in[k]=\{1,\cdots,k\}$ from a set $\mathcal{A}=\{x_{i}\}^{k}_{i=1}$ with $k$ arms, and receives reward $r_{a_{t}}$ from the environment. Each arm $a$ is associated with a $d$-dimensional context vector $x_{a}\in\mathbb{R}^{d}$; and the observed reward follows a linear mapping $r_{a_{t}}=x_{a_{t}}^{\mathsf{T}}\mathrm{\boldsymbol{\theta}}^{*}+\eta_{t}$, where $\mathrm{\boldsymbol{\theta}}^{*}\in\mathbb{R}^{d}$ is a common unknown bandit parameter vector and $\eta_{t}$ is an $R$-sub-Gaussian noise term. We assume context vectors and parameters are all bounded; and for convenience and without loss of generality, we assume $||x_{i}||_{2}\leq 1$ and $\|\mathrm{\boldsymbol{\theta}}^{*}\|_{2}\leq 1$. The performance of a bandit algorithm is evaluated by its pseudo-regret, which is defined as $R_{T}(\mathrm{\boldsymbol{\theta}}^{*})=\sum_{t=1}^{T}(x^{\mathsf{T}}_{a^{*}}\mathrm{\boldsymbol{\theta}}^{*}-x^{\mathsf{T}}_{a_{t}}\mathrm{\boldsymbol{\theta}}^{*})$, where $a^{*}$ is the best arm according to $\mathrm{\boldsymbol{\theta}}^{*}$, i.e., ${a^{*}}=\arg\max_{a\in[k]}[x_{a}^{\mathsf{T}}\mathrm{\boldsymbol{\theta}}^{*}]$.

We study the attackability of a linear stochastic bandit environment. At the first glance, one might wonder whether attackability is the property of a bandit algorithm rather than a property of the environment, since if an algorithm can be attacked, we should have “blamed” the algorithm for not being robust. A key finding of this work is attackability is also a property of the learning environment; and in other words, not all environments are attackable.

We make a few remarks about the above definition of attackability. First, this definition is all about the bandit environment $\langle\mathcal{A},\mathrm{\boldsymbol{\theta}}^{*}\rangle$ and the target arm $\tilde{x}$, but independent of any specific bandit algorithm. Second, if an attack method can only fool a bandit algorithm to pull the target arm $\tilde{x}$ under a few different time horizons $T$, it does not count as a successful attack – it has to succeed for infinitely many time horizons. Third, by reversing the order of quantifiers, we obtain the assertion that a bandit environment is not attackable w.r.t. the target arm $\tilde{x}$ if there exists some no-regret learning algorithm such that no attack method can use $o(T)$ attack cost to fool the algorithm to pull arm $\tilde{x}$ at least $T-o(T)$ times with high probability for any $T$ large enough.

The following simple yet insightful example illustrates that there are indeed linear stochastic bandit environment setups where some no-regret learning algorithm cannot be attacked.

Note that when $\mathcal{A}=\{x_{1},x_{2}\}$, the environment becomes attackable: as shown in Figure 1, a feasible attack strategy is to perturb reward according to $\tilde{\mathrm{\boldsymbol{\theta}}}=(-2,1)$. The key idea is that in the null space of $x_{1}$, $\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp}$ reduces the reward of $x_{2}$ to make $x_{1}$ the best arm without changing the actual reward of $x_{1}$ from the environment. The presence of arm $x_{3}$ prevents the existence of such a $\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp}$ (and therefore $\tilde{\mathrm{\boldsymbol{\theta}}}$) and makes the environment unattackable.

The above example motivates us to study when a linear stochastic bandit environment is attackable. After all, only when facing an unattackable environment, we can ensure the existence of a no-regret algorithm that will be robust to any $o(T)$ poisoning attacks.

Next we show that there indeed exists a complete characterization about when a linear stochastic bandit environment is attackable. As Example 1 shows, the attackability of a bandit environment depends on the arm set $\mathcal{A}=\{x_{i}\}^{k}_{i=1}$, the target arm $\tilde{x}$, and the underlying bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$. For clarity of presentation, in this section, we shall always assume that the adversary knows exactly the ground-truth bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$ and thus the true expected reward of each arm. This is also called the oracle attack in previous works (Jun et al.,, 2018; Rakhsha et al.,, 2020). But in the next section, we will show that this assumption is not necessary: when the bandit environment is indeed attackable, we can design provably successful attacks even if the adversary does not know the underlying bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$.

We need the following convenient notation to state our results. Let

denote the projection of ground-truth bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$ onto the targeted $\tilde{x}$ direction. Since the attackability depends on the target arm $\tilde{x}$ as well, we shall include the target arm $\tilde{x}$ as part of the bandit environment. The following theorem provides a clean characterization about the attackability of a linear stochastic bandit environment.

Since the conceptual message of Theorem 1 significantly differs from previous studies on adversarial attacks in bandit algorithms, we would like to elaborate on its implications.

First of all, we, for the first time, point out some learning environment is intrinsically robust. Even the vanilla LinUCB algorithm, as we will analyze in the proof of Theorem 1, cannot be efficiently attacked when CQP (2) is not satisfied. Notably, although almost all previous works have focused on the vulnerability of bandit algorithms, e.g., by designing attacks against UCB, $\epsilon$-Greedy (Jun et al.,, 2018), LinUCB (Garcelon et al.,, 2020), it just so happens that they were already studied under an attackable environment (see our Corollary 1). To our best knowledge, the problem about the intrinsic robustness of a linear bandit environment has not been studied before and can be viewed as a complement to these previous works. Second, as we will show next, our proof techniques are also significantly different from existing ones, since what is central to our proof is to demonstrate that when CQP (2) is not satisfied, there will exist a robust algorithm that cannot be efficiently attacked by any adversary. This can be viewed as analyzing the robustness of certain bandit algorithms when $\epsilon^{*}\leq 0$ in CQP (2).

Since CQP (2) and its solutions will show up very often in our later analysis, we provide the following definition for reference convenience.

We should note both the index $\epsilon^{*}$ and certificate $\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp}$ are intrinsic to the bandit environment $\langle\mathcal{A}=\{x_{i}\}^{k}_{i=1},\mathrm{\boldsymbol{\theta}}^{*},\tilde{x}\rangle$, and are irrelevant to any bandit algorithms used. As we will see in the next section when designing attack algorithms without the knowledge of $\mathrm{\boldsymbol{\theta}}^{*}$, the index $\epsilon^{*}$ will determine how difficult it is to attack the environment.

We now provide an intuitive explanation about Theorem 1. CQP (2) is to find $\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp}$ such that: 1) it is orthogonal to $\tilde{x}$ (hence its subscript); and 2) it maximizes the gap $\epsilon$ between $\tilde{x}^{\mathsf{T}}\mathrm{\boldsymbol{\theta}}^{*}_{\parallel}$ and the largest $x_{a}^{\mathsf{T}}(\mathrm{\boldsymbol{\theta}}^{*}_{\parallel}+\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp})$ among all $x_{a}\not=\tilde{x}$. Theorem 1 states that the bandit environment is attackable if and only if such a gap is strictly larger than $0$, i.e., when the geometry of context vectors allows the adversary to lower non-target arms’ rewards in the null space of $\tilde{x}$. The constraint $\|\mathrm{\boldsymbol{\theta}}^{*}_{\parallel}+\tilde{\mathrm{\boldsymbol{\theta}}}_{\perp}\|_{2}\leq 1$ ensures the attacked rewards are in the same scale as the unattacked rewards.

Recent works have shown that any no-regret algorithm for the context-free $k$-armed setting (where arm set $\mathcal{A}$ is orthonormal) can always be attacked (Liu and Shroff,, 2019). This finding turns out to be a corollary of Theorem 1.

The intuition behind this corollary is that arms in context-free stochastic multi-armed bandits are independent, and an adversary can arbitrarily lower the rewards of non-target arms to make the target arm optimal. This is also the attack strategy in (Jun et al.,, 2018; Liu and Shroff,, 2019). Garcelon et al., (2020) showed that similar idea works for $k$-armed linear contextual bandits where each arm is associated with an unknown bandit parameter and the reward estimations are independent among different arms.

We should point an important distinction between poisoning attacks to $k$-armed bandits and another line of research on stochastic bandits under adversarial corruption initiated by Lykouris et al., (2018). For poisoning attacks considered in this paper, the adversary manipulates the realized rewards after the algorithm selects an action, whereas in (Lykouris et al.,, 2018), the adversary manipulates the entire reward vector before the algorithm selects any action. Obviously, the later threat model is strictly weaker and has led to various bandit algorithms that can have sublinear regret so long as the total manipulation is sublinear in $T$ (Lykouris et al.,, 2018; Zimmert and Seldin,, 2021).

In the previous section, we characterized the attackability of a linear stochastic bandit environment by assuming the knowledge of ground-truth bandit parameter $\mathrm{\boldsymbol{\theta}}^{*}$. We now show that such prior knowledge is not needed when designing practical attacks. Towards this end, we propose provably effective attacks against two representative bandit algorithms: the most well-known LinUCB and a state-of-the-art robust linear stochastic bandit algorithm, Robust Phase Elimination (Bogunovic et al.,, 2021). We remark that the optimal attacks to these algorithms depend on the characteristics of algorithms themselves and are generally different, due to their different levels of robustness. This also resonates the important message mentioned in the introduction, i.e., the attackability analysis often goes hand-in-hand with the understanding of robustness of different algorithms, as reflected in various parts of our analysis. However, we point out that it is an intriguing open question to understand whether there is a single attack strategy that can manipulate any no-regret algorithm in an attackable environment.

We use simulation-based experiments to validate the effectiveness and cost-efficiency of our proposed attack methods. In our simulations, we generate a size-$k$ arm pool $\mathcal{A}$, in which each arm $a$ is associated with a context vector $x_{a}\in\mathbb{R}^{d}$. Each dimension of $x_{a}$ is drawn from a set of zero-mean Gaussian distributions with variances sampled from a uniform distribution $U(0,1)$. Each $x_{a}$ is then normalized to $\|x_{a}\|_{2}=1$. The bandit model parameter $\mathrm{\boldsymbol{\theta}}^{*}$ is sampled from $N(0,1)$ and normalized to $\|\mathrm{\boldsymbol{\theta}}^{*}\|_{2}=1$. We set $d$ to 10, the standard derivation $\sigma$ of Gaussian noise $\eta_{t}$ and $\tilde{\eta}_{t}$ to 0.1, and the arm pool size $k$ to 30 in our simulations. We run the experiment for $T=10,000$ iterations. To create an attackable environment, we will re-sample the environment $\langle\mathcal{A},\mathrm{\boldsymbol{\theta}}^{*},\tilde{x}\rangle$ until it is attackable, following Theorem 1.

We compared the two proposed attack methods, oracle null space attack and two-stage null space attack, against LinUCB Li et al., (2010) and Robust Phase Elimination (RobustPhE) Bogunovic et al., (2021). We report average results of 10 runs where in each run we randomly sample an attackable environment. Both oracle attack and two-stage attack can effectively fool the two bandit algorithms to pull the target arm linear times as shown in Figure 2(b), and the total cost of the attack is shown in Figure 2(a). We observe that both attack methods are cost-efficient with a sublinear total cost, while the two-stage attack requires higher attack cost when attacking the same bandit algorithm. Specifically, we notice that the adversary spends almost linear cost in the first stage. This is because in the first stage the adversary attacks according to parameter $\mathrm{\boldsymbol{\theta}}_{0}$, which leads to an almost constant cost at every round. This is to help the adversary to estimate bandit model parameter in order to construct target parameter $\tilde{\mathrm{\boldsymbol{\theta}}}$. In the second stage, the cost gets much smaller since the adversary only attacks the non-target arms. We also notice that for the same attack method, attacking RobustPhE requires a higher cost and the number of target arm pull is also smaller comparing with attacking LinUCB, due to the robustness of the algorithm.

Adversarial attacks to bandit algorithms was first studied in the stochastic multi-armed bandit setting (Jun et al.,, 2018; Liu and Shroff,, 2019) and recently in linear contextual bandits (Garcelon et al.,, 2020). These works share a similar attack idea: lowering the rewards of non-target arms while not modifying the reward of target arm. However, as our attackability analysis revealed, this idea can fail in a linear stochastic bandit environment where one cannot lower the rewards of non-target arms without modifying the reward of target arm, due to their correlation. This insight is a key reason that gives rise to unattackable environments. Ma et al., (2018) also considered the attackability issue of linear bandits, but under the setting of offline data poisoning attack where the adversary has the power to modify the rewards in history. There are also several recent works on reward poisoning attacks against reinforcement learning (Yu and Sra,, 2019; Zhang et al.,, 2020; Rakhsha et al.,, 2021, 2020), but with quite different focus as ours. Besides reward poisoning attacks, recent works also studied other threat model such as action poisoning attacks (Liu and Lai,, 2020, 2021).

A parallel line of works focused on improving the robustness of bandit algorithms. Lykouris et al., (2018) proposed a robust MAB algorithm and Gupta et al., (2019) further improved the solution with additive regret dependency on attack cost. Zimmert and Seldin, (2021); Masoudian and Seldin, (2021) proposed best-of-both-world solutions for both stochastic and adversarial bandits which also solved stochastic bandits with adversarial corruption. Ito, (2021) further proposed optimal robust algorithm to adversarial corruption. These work assumed a weaker oblivious adversary who determines the manipulation before the bandit algorithm pulls an arm. Hajiesmaili et al., (2020) studied robust adversarial bandit algorithm. Guan et al., (2020) proposed a median-based robust bandit algorithm for probabilistic unbounded attack. Bogunovic et al., (2021) proposed robust phase elimination algorithm for linear stochastic bandits under a stronger adversary (same as ours), which could tolerate $o(\sqrt{T})$ corruption when the total corruption is unknown to the algorithm. We showed that our two-stage null space attack could effectively attack this algorithm with $\tilde{O}(T^{4/5})$ cost. Recently, Zhao et al., (2021) proposed an OFUL style robust algorithm that can handle infinite action set, but only tolerates $o(T^{1/4})$ corruption.

In this paper, we studied the problem of poisoning attacks in $k$-armed linear stochastic bandits. Different from context-free stochastic bandits and $k$-armed linear contextual bandits where the environment is always attackable, we showed that some linear stochastic bandit environments are not attackable due to the correlation among arms. We characterized the attackability condition as the feasibility of a CQP based on the geometry of the arms’ context vectors. Our key insight is that given the ground-truth parameter $\mathrm{\boldsymbol{\theta}}^{*}$, the adversary should perform oracle attack that lowers the reward of non-target arms in the null space of the target arm’s convex vector $\tilde{x}$. Based on this insight, we proposed a two-stage null space attack without the knowledge of $\mathrm{\boldsymbol{\theta}}^{*}$ and applied it against LinUCB and Robust Phase Elimination. We showed that the proposed attack methods are effective and cost-efficient, both theoretically and empirically.

As our future work, it is interesting to study the lower bound of attack cost in linear stochastic bandits and also design cost-optimal attack method with a matching upper bound. One idea is to design a multi-stage attack method following the doubling trick idea, which was brief discussed in Appendix C.3. Although the analysis could be much more challenging than our two-stage attack, it may lead to a lower attack cost as well as handling unknown time horizon $T$. Another intriguing direction is to study algorithm-oblivious choice of the length of the first stage $T_{1}$ — or more generally, algorithm-oblivious attack strategies — that can achieve sublinear cost for arbitrary no-regret algorithm without the knowledge of $\mathrm{\boldsymbol{\theta}}^{*}$.

This work was supported in part by National Science Foundation Grant IIS-2128019, IIS-1618948, IIS-1553568, Bloomberg Data Science Ph.D. Fellowship, and a Google Faculty Research Award.