Stochastic Bandits Robust to Adversarial Attacks

## Abstract

Abstract This paper investigates stochastic multi-armed bandit algorithms that are robust to adversarial attacks, where an attacker can first observe the learner’s action and then alter their reward observation.
We study two cases of this model, with or without the knowledge of an attack budget C 𝐶 C italic_C , defined as an upper bound of the summation of the difference between the actual and altered rewards. For both cases, we devise two types of algorithms with regret bounds having additive or multiplicative C 𝐶 C italic_C dependence terms.
For the known attack budget case, we prove our algorithms achieve the regret bound of O ⁢ ( ( K / Δ ) ⁢ log ⁡ T + K ⁢ C ) 𝑂 𝐾 Δ 𝑇 𝐾 𝐶 {O}((K/\Delta)\log T+KC) italic_O ( ( italic_K / roman_Δ ) roman_log italic_T + italic_K italic_C ) and O ~ ⁢ ( K ⁢ T ⁢ C ) ~ 𝑂 𝐾 𝑇 𝐶 \tilde{O}(\sqrt{KTC}) over~ start_ARG italic_O end_ARG ( square-root start_ARG italic_K italic_T italic_C end_ARG ) for the additive and multiplicative C 𝐶 C italic_C terms, respectively, where K 𝐾 K italic_K is the number of arms, T 𝑇 T italic_T is the time horizon, Δ Δ \Delta roman_Δ is the gap between the expected rewards of the optimal arm and the second-best arm, and O ~ ~ 𝑂 \tilde{O} over~ start_ARG italic_O end_ARG hides the logarithmic factors.
For the unknown case, we prove our algorithms achieve the regret bound of O ~ ⁢ ( K ⁢ T + K ⁢ C 2 ) ~ 𝑂 𝐾 𝑇 𝐾 superscript 𝐶 2 \tilde{O}(\sqrt{KT}+KC^{2}) over~ start_ARG italic_O end_ARG ( square-root start_ARG italic_K italic_T end_ARG + italic_K italic_C start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) and O ~ ⁢ ( K ⁢ C ⁢ T ) ~ 𝑂 𝐾 𝐶 𝑇 \tilde{O}(KC\sqrt{T}) over~ start_ARG italic_O end_ARG ( italic_K italic_C square-root start_ARG italic_T end_ARG ) for the additive and multiplicative C 𝐶 C italic_C terms, respectively.
In addition to these upper bound results, we provide several lower bounds showing the tightness of our bounds and the optimality of our algorithms.
These results delineate an intrinsic separation between the bandits with attacks and corruption models (Lykouris et al., 2018 ) .

## 1 Introduction

Online learning literature (Borodin and El-Yaniv, , §7.1.2)
usually considers two types of non-oblivious adversary models: the medium adversary and the strong adversary.(^1^11There is a third adversary model, called the weak adversary, which is oblivious. The medium adversary is also called the adaptive-online adversary, while the strong adversary is called the adaptive-offline adversary.) The medium adversary chooses the next instance *before* observing the learner’s actions, while the strong adversary chooses instances *after* observing the learner’s actions.
When it comes to the multi-armed bandits (MAB) learning with an adversary, the medium adversary corresponds to the bandits with corruption (Lykouris et al., ), and the strong adversary corresponds to adversarial attacks on bandits (Jun et al., ). Bandit algorithms robust to corruption are developed for the medium adversary models in bandits literature, e.g., Auer et al. (); Audibert and Bubeck (); Lykouris et al. (); Gupta et al. (). However, for the strong adversary model, i.e., the adversarial attack model on MAB, most previous efforts focus on devising attacking policies to mislead the learner to pull a suboptimal arm and thus suffer a linear regret, e.g., Jun et al. (); Liu and Shroff (); Zuo (). Developing robust algorithms for the adversarial attack model and achieving regret with benign dependence on the total attack is still largely unexplored (for a detailed discussion, see the end of §1).

Stochastic MAB with adversarial attacks
In this paper, we study the stochastic MAB under adversarial attacks and develop robust algorithms whose regret bounds degrade gracefully in the presence of such attacks.
Denote by $K\in\mathbb{N}^{+}$ as the number of arms in MAB, and each arm $k$ is associated with a reward random variable $X_{k}$ with an unknown mean $\mu_{k}$. Denote by $k^{*}$ as the arm index with the highest mean reward, and $\Delta_{k}\coloneqq\mu_{k^{*}}-\mu_{k}$ the reward gap between the optimal arm $k^{*}$ and any suboptimal arm $k$. The learner aims to minimize the *regret*, defined as the difference between the highest total rewards of pulling a single arm and the accumulated rewards of the concern algorithm. In each time slot, the learner first pulls an arm. Then, the adversary observes the pulled arm and its realized reward and chooses an attacked reward for the learner to observe. Denote by $C$ as the total amount of *attacks* that the adversary uses to alter the raw rewards to the attacked rewards over all rounds.
We present the formal model definitions in §2.

Contributions
This paper proposes robust algorithms with tight regret bounds for the adversarial attack model on MAB. To achieve that, we first develop robust algorithms with the known attack budget as an intermediate step towards developing robust algorithms for the unknown attack budget case. Later on, we call the former the *known attack* case and the latter the *unknown attack* case.

Known attack budget case. For the known attack case (§4), we first investigate the successive elimination with wider confidence radius (SE-WR) algorithm, which was initially proposed for bandits with corruptions (Lykouris et al., ).
In §4.1, we show SE-WR can be applied to the bandits with known adversarial attack budget
and prove that this algorithm enjoys a tighter
regret upper bound $O(\sum_{k\neq k^{*}}{\log T}/{\Delta_{k}}+KC)$ (under both attack and corruption models) than previous analysis (Lykouris et al., ) under the corruption model.
This improvement removes the original additive term $\sum_{k\neq k^{*}}{C}/{\Delta_{k}}$’s dependence of $\Delta_{k}$ and reduces it to $KC$.
To achieve gap-independent regret bounds in §4.2, we propose two stopping conditions for the successive elimination to modify the SE-WR algorithm to two SE-WR-Stop algorithms (see \small{1}⃝ in Figure 2).
We prove that the regrets of these two modified algorithms are $O(\sqrt{KT\log T}+KC)$ and $O(\sqrt{KT(\log T+C)})$ respectively.

Unknown attack budget case. To address with MAB with unknown attack case (§5), we use algorithms proposed for known attacks as building blocks to devise algorithms for unknown attacks. We consider two types of algorithmic techniques.
In §5.1, we apply a multi-phase idea to extend the SE-WR algorithm to a phase elimination algorithm (PE-WR, see \small{2}⃝ in Figure 2). The PE-WR algorithm utilizes a multi-phase structure—each phase with carefully chosen attack budgets and phase lengths—to defend against unknown attacks. We show that the regret of PE-WR is upper bounded by $O(\sqrt{KT}+KC^{2})$. In §5.2, we apply a model selection technique, which treats the unknown attack $C$ as a parameter in model selection (see \small{3}⃝ in Figure 2). Specifically, we consider $\log_{2}T$ base instances of SE-WR-Stop with different input attack budgets and then use the model selection technique to “corral” these base instances, composing the model-selection SE-WR-Stop (called MS-SE-WR) algorithm. We upper bound the regret of MS-SE-WR by $\tilde{O}(\sqrt{KC}T^{\frac{2}{3}})$ or $\tilde{O}(KC\sqrt{T})$ depending on the choice of the model selection algorithm.
Figure 2 summarizes the relations of algorithm design, and Figure 2 shows that which type of algorithm performs better, those with additive bounds or those with multiplicative bounds, varies depending on the total attacks.

Figure: Figure 1: Algorithm design overview: only SE-WR has a gap-dependent bound; others are all gap-independent.
Refer to caption: extracted/5796206/figures/paper-structure.png

Lower bounds. In §3, we also provide lower bound results to show the tightness of our upper bounds. We first show a general $\Omega(KC)$ lower bound for any algorithm under attack. Based on this, we propose the gap-dependent lower bound $\Omega(\sum_{k\neq k^{*}}{\log T}/{\Delta_{k}}+KC)$ (informal expression) and gap-independent lower bound $\Omega(\sqrt{KT}+KC)$. Our refined upper bound of SE-WR matches the gap-dependent lower bound up to some prefactors, and one of our proposed SE-WR-Stop algorithms matches the gap-independent lower bound up to some logarithmic factors.
To show the tightness of our upper bounds for the unknown attack algorithms, we derive lower bounds, $\Omega(T^{\alpha}+C^{\frac{1}{\alpha}})$ and $\Omega(C^{\frac{1}{\alpha}-1}T^{\alpha})$ with $\alpha\in[\frac{1}{2},1)$, for two classes of algorithms whose regret upper bounds follow certain additive and multiplicative forms respectively.
With $\alpha=\frac{1}{2}$, these two lower bounds, becoming $\Omega(\sqrt{T}+C^{2})$ and $\Omega(C\sqrt{T})$, match the upper bounds of PE-WR and MS-SE-WR in terms of $T$ and $C$.
We summarize our analysis results in Table 1.

**Table 1: Results overview: upper bounds with ^† are for pseudo regret in expectation, while all other upper bounds are for realized regret with high probability; lower bounds with ^‡ are only for special classes of algorithms (see Propositions 3 and 4), and the lower bound with ^†† holds when $T\to\infty$. We report both additive and multiplicative bounds because which one is better could depend on the value of $C$ (see Figure 2 for unknown $C$ case and the detailed discussion in Remark 9).**
| Regret Bounds | Known Attack $C$ (§4) | Unknown Attack $C$ (§5) |
| --- | --- | --- |
| Additive $C$ | $O\left(\sum_{k\neq k^{*}}\frac{\log T}{\Delta_{k}}+KC\right),\,O(\sqrt{KT\log T<br>}+KC)$ | $\tilde{O}\left(\sqrt{KT}+KC^{2}\right)$ |
| Multiplicative $C$ | $O(\sqrt{KT(\log T+C)})$ | $\tilde{O}(\sqrt{KC}T^{\frac{2}{3}})^{\dagger},\,\tilde{O}(KC\sqrt{T})^{\dagger}$ |
| Lower Bounds (§3) | $\Omega\left(\sum_{k\neq k^{*}}\frac{\log T}{\Delta_{k}}+KC\right)^{\dagger<br>\dagger},\Omega(\sqrt{KT}+KC)$ | $\Omega(T^{\alpha}+C^{\frac{1}{\alpha}})^{\ddagger},\Omega(C^{\frac{1}{\alpha}-<br>1}T^{\alpha})^{\ddagger}$ |

Result separation between corruption and attack.
With the results in this paper, we demonstrate a clear separation between corruption (medium adversary) and attack (strong adversary) models in terms of the additive regret bounds.
Denote by $C^{\prime}$ the total corruption to distinguish from the total attack $C$, and we discuss the model different in more detail in §2.
In the case of known corruption/attack budget, while both achieving the gap-dependent regret bounds $\sum_{k\neq k^{*}}(1/\Delta_{k})\log T$ in $T$-dependent terms, we show that the regret due to attack is $\Theta(KC)$ which has a factor of $K$ worse than the additional $\Theta(C^{\prime})$ regret due to corruption.
That implies, with the same amount of budget, an attacker can produce $K$ times larger impact on regret than that under the corruption model.
For unknown budget cases,
while bandits with corruptions have the regret bounds of $O\left(\sum_{k\neq k^{*}}\frac{\log^{2}(KT/\delta)}{\Delta_{k}}+C^{\prime}\right)$ (Gupta et al., ; Liu et al., ), it is impossible for attack case to achieve a regret upper bound in the form of $O\left(\text{ploylog}(T)+C^{\alpha}\right)$ for any $\alpha>0$ (contradicts with Theorem 2). Instead, we show that the regret with unknown attacks can attain $\tilde{O}(\sqrt{KT}+KC^{2})$ where the $C^{2}$ additive term is tight. Even if ignoring the worse order of the first $T$-related terms, the second regret term due to attack $O(C^{2})$ is still a factor of $C$ worse than the additional $O(C^{\prime})$ regret due to corruption. That is, an attack with $O(\sqrt{T})$ budget is enough to make the algorithm suffer a linear regret in the attack model,(^2^22This statement is for the algorithm with $\tilde{O}(\sqrt{KT}+KC^{2})$ mentioned above. Our lower bound results do not exclude the possible existence of other algorithms with upper bounds $\tilde{O}(T^{\alpha}+C^{\frac{1}{\alpha}})$ for $\alpha\in[\frac{1}{2},1)$, in which case a sublinear $O(T^{\alpha})$ budget can make the algorithm suffer linear regret.) while one needs a linear $O(T)$ corruption budget to achieve the same effect in the corruption case.

Extended literature review
Robustness against corruption.
Lykouris et al. () propose the bandits with corruption model and devised algorithms with $O((K\log T+KC^{\prime})/\Delta)$ regret for known corruption $C^{\prime}$ case and algorithms with ${O}(C^{\prime}K^{2}\log T/\Delta)$ regret for unknown $C^{\prime}$ case, where $\Delta$ denotes the smallest non-zero reward gap.
Later, Gupta et al. () study the same model and propose an algorithm that improves the multiplicative $C^{\prime}$ dependence of regret for unknown $C^{\prime}$ case to additive $C^{\prime}$, i.e., ${O}(K\log^{2}T/\Delta+KC^{\prime})$.
However, the robust design of both algorithms above relies on randomly pulling arms, which is not feasible in our attack setting.
Besides bandits robust to corruption, there is another line of works on best-of-both-world bandit algorithm design, e.g., Seldin and Lugosi (); Wei and Luo (); Zimmert and Seldin (), where their algorithms can be applied to the bandit with corruption but do not work in the adversarial attack model either.

Attacks on bandits.
Attack policy design for MAB algorithms has been studied by Jun et al. (); Liu and Shroff (); Xu et al. (); Zuo et al. (); Zuo () and many others.
They aim to design attacking policies to mislead the learner, typically with logarithmic regrets when there is no attack, to pull a suboptimal arm and thus suffer a linear regret. This is the opposite of our objective for designing robust algorithms to achieve sublinear regret under any attacks.

Robustness against attacks.
The only existing result on robust algorithms for MAB under attacks is by Zuo (, Section 6), where the author uses competitive ratio as the objective—often used when one cannot achieve sublinear regret, instead of the finer-grained regret metric studied in this paper.
Apart from the MAB model, there are works studying robust algorithms on structured bandits under attacks, e.g., linear bandits (Bogunovic et al., ; He et al., ) and Lipchitz bandits (Kang et al., ). Although their linear/Lipchitz bandits results can be reduced to MAB, this reduction does not provide algorithms with tight regrets as in Table 1 of this paper. We will elaborate on this in §5.

## 2 Model: MAB with Adversarial Attacks

We consider a MAB model with $K\in\mathbb{N}^{+}$ arms. Each arm $k\in\mathcal{K}\coloneqq\{1,2,\dots,K\}$ is associated with a reward random variable $X_{k}\in[0,1]$ with an unknown mean $\mu_{k}$. Denote the unique arm with highest reward mean as $k^{*}$, i.e., $k^{*}=\operatorname*{arg\,max}_{k\in\mathcal{K}}\mu_{k}$.
We consider $T\in\mathbb{N}^{+}$ decision rounds.
At each round $t\in\mathcal{T}\coloneqq\{1,2,\dots,T\}$, the learner selects an arm $I_{t}\in\mathcal{K}$, and the arm generates a reward realization $X_{I_{t},t}$ (not disclosed to the learner yet). The adversary observes the pulled arm $I_{t}$ and its realized reward $X_{I_{t},t}$ and then chooses an attacked reward $\tilde{X}_{I_{t},t}$ for the learner to observe.
The total attack is the sum of the absolute differences between the raw rewards and the attacked rewards over all rounds, i.e., $C\coloneqq\sum_{t=1}^{T}\lvert X_{I_{t},t}-\tilde{X}_{I_{t},t}\rvert$.
We summarize the decision process in Procedure 1.

Figure: Procedure 1 Decision under Attacks

Regret objective
The adversary aims to maximize the learner’s regret, while the learner aims to minimize the regret.
We define the (realized) regret as the difference between the highest total realized *raw* rewards of a single arm and the accumulated *raw* rewards of the learning algorithm as follows,

$$ $R_{T}\coloneqq\max_{k\in\mathcal{K}}\sum\nolimits_{t\in\mathcal{T}}({X}_{k,t}- {X}_{I_{t},t}).$ (1) $$

Besides the realized regret in (1), another common regret definition is the pseudo-regret, defined as

$$ $\bar{R}_{T}\coloneqq\max_{k\in\mathcal{K}}\mathbb{E}\left[\sum\nolimits_{t\in \mathcal{T}}({X}_{k,t}-{X}_{I_{t},t})\right]=\mathbb{E}\left[T\mu_{k^{*}}-\sum \nolimits_{t\in\mathcal{T}}\mu_{I_{t}}\right].$ (2) $$

By Jensen’s inequality, we have $\bar{R}_{T}\leqslant\mathbb{E}[R_{T}],$
implying that the pseudo-regret is a weaker metric than the realized regret. This paper’s results are primarily on realized regret, but we also provide results on the pseudo-regret when necessary.

Comparison between corruption and attack models
Different from the above attack model (strong adversary), there is prior literature on robust bandit algorithms against corruption (medium adversary) (Lykouris et al., ; Gupta et al., ),
where the adversary chooses the corruption rewards *before* observing the learner’s actions (see Appendix A for more details), and the total amount of corruption is defined as ${C^{\prime}\coloneqq\sum_{t=1}^{T}\max_{k}\lvert X_{t}(k)-\tilde{X}_{k,t}
\rvert.}$
While comparing the definition of corruption $C^{\prime}$ with attack $C$ may lead to the impression that $C\leqslant C^{\prime}$ and both models only differ slightly, we emphasize that the two models are fundamentally different due to the sequence of the adversary attacking (corrupting) rewards after (before) observing the learner’s actions.

To highlight the crucial difference between the two sequences, we illustrate that, to generate the same degree of impact on a bandit algorithm, the required budget under the corruption model can be much larger than that under the attack model.
For example, one naive attack policy, forcing the learner to suffer linear regrets, could be that whenever the algorithm pulls the optimal arm $k^{*}$, the adversary alters the reward realization to be smaller than the mean of the best suboptimal arm. As the adversary observes the learner’s action before choosing the attack, this attack policy may cost $O(\log T)$ or sublinear $O(T^{\alpha})$ budget for some $\alpha<1$, depending on the specific algorithm.
However, in the corruption model, as the adversary does not know which arm is pulled before corrupting the rewards, the adversary has to corrupt the optimal arm’s reward realization in all $T$ rounds to achieve the same effect, resulting in $O(T)$ cost.
From an abstract perspective, the attack model is more powerful than the corruption model because the sequence of observing the pulled arm before attacking makes the randomized strategy (widely used in bandits) invalid, for example, randomly pulling arms in EXP3 (Auer et al., ) and BARBAR (Gupta et al., ). Without randomization, devising robust algorithms for attacks is much more challenging than that for corruptions.

## 3 Lower Bounds

This section first presents a new general lower bound for the adversarial attack model on stochastic multi-armed bandits (Theorem 3.1) and two of its variants. Later, we derive two lower bounds for two special classes of bandit algorithms (Propositions 3 and 4).
All proofs are deferred to Appendix B.

### 3.1 A General Lower Bound

We first present a general lower bound $\Omega(KC)$ in Theorem 3.1. Together with known lower bounds of MAB, we derive Proposition 1.
§4 presents algorithms matching these lower bounds.

theoremKClowerbound
Given a stochastic multi-armed bandit game with $K$ arms, under attack with budget $C$, and $T>KC$ decision rounds,(^3^33Note that $T\leqslant KC$ implies that $C=\Omega(T)$ which trivially results in a linear regret.) for any bandits algorithm, there exists an attack policy with budget $C$ that can make the algorithm suffer $\Omega(KC)$ regret.

###### Proposition 1 .

For gap-dependent regret bounds and any consistent bandit algorithm(^4^44When $C=0$, a consistent bandits algorithm has regret $\bar{R}_{T}\leqslant O(T^{\alpha})$ for any $\alpha\in(0,1)$.), the lower bound is roughly $\Omega\left(\sum_{k\neq k^{*}}\frac{\log T}{\Delta_{k}}+KC\right)$, or formally, for some universal constant $\xi>0$,

$$ $\liminf_{T\to\infty}\frac{\bar{R}_{T}-\xi KC}{\log T}\geqslant\sum_{k\neq k^{* }}\frac{1}{2\Delta_{k}}.$ (3) $$

For gap-independent cases, the lower bound is

$$ $\bar{R}_{T}\geqslant\Omega(\sqrt{KT}+KC).$ (4) $$

###### Proposition 1 .

### 3.2 Two Lower Bounds for Special Algorithm Classes

In this subsection, we first recall results from adversarial attacks on bandits literature (Liu and Shroff, ; Zuo, ) in Theorem 2. Then, based on these results, we derive two lower bounds for bandit algorithms with additive and multiplicative regret bounds respectively. In §5, we present algorithms that match these lower bounds.

###### Theorem 2 (Adapted from (Zuo, 2024 , Fact 1) and (He et al., 2022 , Theorem 4.12) ) .

If an algorithm achieves regret $R_{T}$ when total attack $C=0$, then there exists an attack policy with $C=\Theta(R_{T})$ that can make the algorithm suffer linear regret.

###### Proposition 3 (Achievable additive regret bounds) .

Given any parameter $\alpha\in[\frac{1}{2},1)$, for any bandit algorithm that achieves an additive regret upper bound of the form $O(T^{\alpha}+C^{\beta})$, we have $\beta\geqslant\frac{1}{\alpha}$.

###### Proposition 4 (Achievable multiplicative regret bounds) .

Given parameter $\alpha\in[\frac{1}{2},1)$, for any bandit algorithm that achieves a multiplicative regret bound of the form $O(T^{\alpha}C^{\beta})$, we have $\beta\geqslant\frac{1}{\alpha}-1$.

###### Theorem 2 (Adapted from (Zuo, 2024 , Fact 1) and (He et al., 2022 , Theorem 4.12) ) .

###### Proposition 3 (Achievable additive regret bounds) .

###### Proposition 4 (Achievable multiplicative regret bounds) .

## 4 Algorithms with Known Attack Budget

In this section, we study the stochastic multi-armed bandit problem with a known attack budget. In §4.1, we first present an algorithm with an additive gap-dependent upper bound on the attack budget. Then, in §4.2, we modify this algorithm to two variants with gap-independent upper bounds, one with an additive $C$ term and another with a multiplicative $C$ term.

### 4.1 SE-WR : An Algorithm with Gap-Dependent Upper Bound

Given the knowledge of attack budget $C$, one is able to predict the worst-case attack and design an algorithm to defend against it.
Here, the robustness is achieved by widening the confidence radius of the reward estimate to account for the $C$ attack such that the corresponding widened confidence interval contains the true reward mean with a high probability (as if the rewards were not attacked).
Denote $\tilde{\mu}_{k}$ as the empirical mean of the attacked reward observations of arm $k$. The widened confidence interval is centered at $\tilde{\mu}_{k}$ and has a radius of $\sqrt{{\log(2/\delta)}/{N_{k}}}+{C}/{N_{k}}$, where $N_{k}$ is the number of times arm $k$ is pulled and $\delta$ is the confidence parameter.
Then, we utilize the successive elimination (SE) algorithm (Even-Dar et al., ) to devise a robust bandit algorithm in Algorithm 2.
The algorithm maintains a candidate set of arms $\mathcal{S}$, initialized as the set of all arms $\mathcal{K}$,
and successively eliminate suboptimal arms according to the widened confidence intervals (Line 7), called successive elimination with wide radius (SE-WR).
A similar algorithm design idea was also used in Lykouris et al. () for the stochastic bandit problem with corruption attacks. Theorem 2 provides the regret upper bound of Algorithm 2.

Figure: Algorithm 2 SE-WR: Successive Elimination with Wide Confidence Radius

theoremaddtiveknownbound
Given the total attack or its upper bound $C$, Algorithm 2’s the realized regret is upper bounded by $R_{T}\leqslant O\left(\sum_{k\neq k^{*}}\frac{\log(KT/\delta)}{\Delta_{k}}+KC
\right)\text{ with probability }1-\delta,$
and, with $\delta=K/T$, its pseudo regret is upper bounded as $\bar{R}_{T}\leqslant O\left(\sum_{k\neq k^{*}}\frac{\log T}{\Delta_{k}}+KC
\right).$

The regret upper bound in Theorem 2 matches the lower bound in (3) in terms of both the first classic regret term and the second additive attack $\Omega(KC)$ term. This shows that the regret upper bound is nearly optimal up to some prefactors.
Our regret upper bounds improve the $O\left(\sum_{k\neq k^{*}}\frac{\log(KT/\delta)}{\Delta_{k}}+\sum_{k\neq k^{*}}
\frac{C}{\Delta_{k}}\right)$ in Lykouris et al. (, Theorem 1) by removing the multiplicative dependence of $1/\Delta_{k}$ on the total attack $C$ term.
This improvement comes from a tighter analysis for sufficient pulling times for eliminating a suboptimal arm (see Lemma 12 in Appendix D).
This improvement is crucial for achieving our tight multiplicative regret bounds for both known and unknown attack budget cases (Sections 4.2 and 5.2).

### 4.2 SE-WR-Stop : An Algorithm with Gap-Independent Upper Bounds

We follow the approach of stochastic bandits literature (Lattimore and Szepesvári, , Chapter 6) to transfer the algorithm with a gap-dependent upper bound to another algorithm with gap-independent bounds. The main idea is to replace the while loop condition in Line 3 in Algorithm 2 with nuanced stopping conditions.
If the stopping condition is triggered before the end of the MAB game, i.e., $t=T$, the algorithm will uniformly pull the remaining arms in the candidate set $\mathcal{S}$ until the end of the game. As the pseudo-code of this algorithm is similar to SE-WR, we defer it to Algorithm 6 in Appendix C.

We consider two kinds of stopping conditions.
The first condition aims to transfer the gap-dependent bound to an independent one while keeping the additive $KC$ term in the upper bound.
We start from a stopping condition $N_{k}\leqslant\frac{\log(KT/\delta)}{\epsilon^{2}}+\frac{C}{\epsilon}$, where $\epsilon$ is a parameter to be determined. With this condition and the proof details of Theorem 2, we can upper bound the realized regret as follows,

$$ $\begin{split}R_{T}\leqslant O\left(\frac{K\log(KT/\delta)}{\epsilon}+\epsilon T +KC\right)\leqslant O\left(\sqrt{KT\log(KT/\delta)}+KC\right),\end{split}$ $$

where we choose $\epsilon=\sqrt{K\log(KT/\delta)/{T}}$ in the last inequality.

The second stopping condition, while transferring the gap-dependent to independent, also converts the additive $KC$ term to multiplication. To derive it, we start from a stopping condition $N_{k}\leqslant\frac{\log(KT/\delta)+C}{\epsilon^{2}}$, where $\epsilon$ is a parameter to be determined. With this condition and the proof details of Theorem 2, we can upper bound the realized regret as follows,

$$ $\begin{split}R_{T}&\leqslant O\left(\frac{K\log(KT/\delta)+KC}{\epsilon}+ \epsilon T\right)\leqslant O\left(\sqrt{KT(\log(KT/\delta)+C)}\right)\end{split}$ $$

where $\epsilon=\sqrt{{(K\log(KT/\delta)+KC)}/{T}}$ in the last inequality.
We summarize the above results in the following theorem.

###### Theorem 5 .

Given the total attack or its upper bound $C$, SE-WR-Stop (Algorithm 6) with stopping condition $N_{k}\leqslant\frac{T}{K}+C\sqrt{\frac{T}{K\log(KT/\delta)}}$ has the realized regret upper bounded as follows,

$$ $R_{T}\leqslant O\left(\sqrt{KT\log(KT/\delta)}+KC\right)\text{ with probability }1-\delta,$ (5) $$

and SE-WR-Stop with stopping condition $N_{k}\leqslant\frac{T}{K}$ has the realized regret upper bounded as follows,

$$ $R_{T}\leqslant O\left(\sqrt{KT(\log(KT/\delta)+C)}\right)\text{ with probability }1-\delta.$ (6) $$

Let $\delta=K/T$, the regret in (5) becomes $O\left(\sqrt{KT\log T}+KC\right)$, matching with the lower bound in (4) up to logarithmic factors. This implies the regret upper bound is nearly optimal.
Let $\delta=K/T$, the regret in (6) becomes $O(\sqrt{KT(\log T+C)})$. Although this bound cannot match the lower bound in (4), its dependence on total attack $C$ is square root, better than the linear dependence in (5). This better dependence will shine when devising algorithms for unknown attack budget in §5.2.

###### Remark 6 (Algorithm selection for known $C$ case) .

Although this section proposes three algorithms for known $C$—one SE-WR and two SE-WR-Stop, the latter two SE-WR-Stop algorithms are mainly for the theoretical interest of deriving gap-independent and multiplicative $C$ bounds. Practically, SE-WR should have better empirical performance than that of SE-WR-Stop, as SE-WR-Stop may stop eliminating relatively good suboptimal arms earlier than SE-WR, causing a slightly higher regret.

###### Theorem 5 .

###### Remark 6 (Algorithm selection for known C 𝐶 C italic_C case) .

## 5 Algorithms with Unknown Attack Budget

This section presents algorithms that can defend against adversarial attacks with unknown attack budgets. We first present an algorithm with an additive upper bound in §5.1 and then an algorithm with a multiplicative upper bound in §5.2.

Before diving into the detailed algorithm designs, we recall that the input attack budget $C_{\text{Input}}$ for SE-WR and SE-WR-Stop can be interpreted as the level of robustness that the algorithms have.
For any actual attack $C\leqslant C_{\text{Input}}$, the algorithms achieve the regret upper bounds in Theorems 2 and 5 respectively; for attack $C>C_{\text{Input}}$, the algorithms may be misled by the attacker and suffer linear regret.
This “robust-or-not” separation demands the knowledge of the actual attack $C$ for SE-WR and SE-WR-Stop to perform well.
In this section, we apply two types of “smoothing” algorithmic techniques to “smooth” this “robust-or-not” separation of SE-WR and SE-WR-Stop so as to achieve robustness against unknown attacks. An overview of algorithm design is in Figure 2.

On the other hand, robust algorithms designed for unknown corruptions, e.g., Lykouris et al. (); Gupta et al. (), do not apply to the unknown attack setting. Because these robust algorithms all rely on some randomized action mechanism to defend against corruption, which is invalid for the attack as the attacker can manipulate the rewards of the arms *after* observing the learner’s actions.

### 5.1 PE-WR : An Algorithm with Additive Upper Bound

The first “smoothing” algorithmic technique is applying the multi-phase structure to modify SE-WR (Algorithm 2), yielding the phase elimination with wide confidence radius algorithm, PE-WR (Algorithm 3) for unknown attack budget.
This algorithm considers multiple phases of SE-WR, each with a different assumed attack budget $C_{\text{Input}}$, and the candidate arm set $\mathcal{S}$ is updated consecutively among phases, that is, the arms eliminated in previous phases are not considered in later phases.

Specifically, PE-WR separates the total decision rounds into multiple phases $h\in\{1,2,\dots\}$,
each with a length doubled from the previous phase (Line 8).
In phase $h$, the elimination assumes the potential attack is upper bounded by $\hat{C}_{h}$, which is halved in each phase (Line 4). This mechanism results in two kinds of phases. Denote $h^{\prime}$ as the first phase whose corresponding $\hat{C}_{h^{\prime}}$ is smaller than the true attack budget $C$. Then, for phases $h<h^{\prime}$, we have $\hat{C}_{h}\geqslant C$, and, therefore, the algorithm eliminates arms properly as SE-WR;
for phases $h\geqslant h^{\prime}$, as $\hat{C}_{h}<C$, the algorithm may falsely eliminate the optimal arm and suffer extra regret. But even though the optimal arm is eliminated, the algorithm in these phases still has the level of $\hat{C}_{h}$ robustness, which guarantees some relatively good suboptimal arms—with a mean close to the optimal arm—remaining in the candidate set $\mathcal{S}$ such that the total regret due to losing the optimal arm in these phases is not large (bounded by $KC^{2}$ in the proof).
We present the pseudo-code of PE-WR in Algorithm 3 and its regret upper bound in Theorem 3.

Figure: Algorithm 3 PE-WR: Phase Elimination with Wide Confidence Radius

theoremaddtiveunknownbound
Algorithm 3 has a realized regret upper bound, with a probability of at least $1-\delta$,
$R_{T}\leqslant{O}\left(\sqrt{KT\log\left({K\log T}/{\delta}\right)}+\sqrt{T}
\log T+KC\log T+KC^{2}\right)$
as well as a pseudo regret upper bound as follows, with $\delta={K}/{T}$,

$$ $\begin{split}\bar{R}_{T}&\leqslant{O}\left(\sqrt{KT\log\left({T\log T}\right)} +\sqrt{T}\log T+KC\log T+KC^{2}\right)=\tilde{O}\left(\sqrt{KT}+KC^{2}\right). \end{split}$ $$

Comparing our upper bound in Theorem 3 to the lower bound in Proposition 3 with $\alpha={1}/{2}$, $\Omega(\sqrt{T}+C^{2})$, we know that our upper bound is tight in terms of both $T$ and $C$. Compared with the lower bound $\Omega(\sqrt{KT}+KC)$ in Theorem 1, our upper bound is also tight in terms of $K$.

This multi-phase elimination idea is widely used in bandit literature, e.g., batched bandits (Gao et al., ), multi-player bandits (Wang et al., ), and linear bandits (Bogunovic et al., ). The most related to ours is the phase elimination algorithm proposed in Bogunovic et al. () for linear bandits. However, directly reducing their results to our stochastic bandit case would yield a $\tilde{O}(K\sqrt{KT}+C^{2})$ upper bound for $C\leqslant\frac{\sqrt{T}}{(K\log\log K)\log T}$ only, and, for general $C$, their results would become $\tilde{O}(K\sqrt{KT}+K^{2}C^{2})$.
Our result in Theorem 3 is tighter than theirs by a factor of the number of arms $K$ on the first $\sqrt{T}$ term, and, for the general $C$ case, our result is tighter by a factor of $K$ on the second $C^{2}$ term as well.
This improvement comes from the tighter confidence bound employed in Line 7 of Algorithm 3 and the corresponding tighter analysis for the necessary number of observations for the algorithm to eliminate arms (Lemma 12) in §4.1.

### 5.2 MS-SE-WR : An Algorithm with Multiplicative Upper Bound

While the additive bound in Theorem 3 can be transferred to a multiplicative bound $\tilde{O}(KC^{2}\sqrt{T})$,
this bound cannot match the lower bound in Proposition 4, e.g., $\Omega(C\sqrt{T})$ for $\alpha=\frac{1}{2}$.
In this section, we deploy another algorithmic technique, model selection, to SE-WR-Stop (Algorithm 2) to achieve tight multiplicative upper bounds for the unknown attack budget case.
Unlike the multi-phase technique, where each phase assumes a different attack budget, we consider multiple algorithm instances with different attack budget inputs, each of which is a “model.”
Model selection means selecting the model (algorithm instance) that performs best in the unknown environment. In our scenario, it is to select the instance with the smallest attack budget input $C_{\text{Input}}$ that is larger than the actual attack budget $C$.

Specially, we consider $G\coloneqq\lceil\log_{2}T\rceil$ instances of SE-WR-Stop, each with a different attack budget input $C_{\text{Input}}=2^{g}$, $g=1,2,\dots,G$.
Among these instances, the best is $g^{*}=\lceil\log_{2}C\rceil$, as $2^{g^{*}}\in[C,2C)$ is the smallest attack budget larger than the actual attack $C$.
We then apply a model selection algorithm, e.g., CORRAL (Agarwal et al., ) or EXP3.P (Auer et al., ), to select the best one among the $G$ instances.
Algorithm 4 presents the pseudo-code.
To prove the regret upper bound, we recall a simplified version of Pacchiano et al. (, Theorem 5.3) in the following lemma.

Figure: Algorithm 4 MS-SE-WR: Model Selection with Wide Confidence Radius

###### Lemma 7 .

If base algorithm instance has regret upper bound $\bar{R}_{T}\leqslant T^{\alpha}c(\delta)$ with probability $1-\delta$ for known constant $\alpha\in[\frac{1}{2},1)$ and the unknown function $c:\mathbb{R}\to\mathbb{R}$,
then the regrets of *CORRAL* and *EXP3.P* are $\bar{R}_{T}\leqslant\tilde{O}(c(\delta)^{\frac{1}{\alpha}}T^{\alpha})$ and $\bar{R}_{T}\leqslant\tilde{O}(c(\delta)^{\frac{1}{2-\alpha}}T^{\alpha})$ respectively.

To apply this lemma to our case, we first convert the gap-independent upper bound in (6) of SE-WR-Stop (Algorithm 6) in Theorem 5 to a multiplicative upper bound: When the stop condition is $N_{k}\leqslant\frac{T}{K}$, the realized regret upper bound is $\bar{R}_{T}\leqslant{O}(\sqrt{KTC\log(KT/\delta)})$ with a probability of at least $1-\delta$. Plugging this into Lemma 7 with $\alpha=\frac{1}{2}$ and $c(\delta)=\sqrt{C\log(KT/\delta)}$ and letting $\delta=K/T$, we have the pseudo regret upper bounds for MS-SE-WR as follows:

###### Theorem 8 .

Deploying SE-WR-Stop (stop condition $N_{k}\leqslant T/K$) as the base algorithm instance,
Algorithm 4 with *CORRAL* has pseudo regret upper bound $\bar{R}_{T}\leqslant\tilde{O}(\sqrt{KC}T^{\frac{2}{3}})$,
and Algorithm 4 with *EXP3.P* has pseudo regret upper bound $\bar{R}_{T}\leqslant\tilde{O}(KC\sqrt{T})$.

The bounds in Theorem 8 are tight in terms of the trade-off of $T$ and $C$, as they respectively match the lower bounds in Proposition 4, $\Omega(\sqrt{C}T^{\frac{2}{3}})$ when $\alpha=\frac{2}{3}$ and $\Omega(C\sqrt{T})$ when $\alpha=\frac{1}{2}$.
The challenge of achieving these tight regret bounds in Theorem 8 is in discovering the right base algorithm instances with suitable multiplicative upper bounds.
For example, the first upper bound in Theorem 5 can also be converted to the multiplicative
$\bar{R}_{T}\leqslant{O}(C\sqrt{KT\log(KT/\delta)})$ bound with a probability of at least $1-\delta$.
However, applying the model selection technique to this bound only results in $\tilde{O}(C\sqrt{K}T^{\frac{2}{3}})$ and $\tilde{O}(C^{2}K\sqrt{T})$ bounds, which are not as tight as the ones in Theorem 8.

This model selection technique was also used in Kang et al. () to boost the algorithm for Lipchitz bandits with a known attack budget to an algorithm with an unknown attack budget. However, their regret upper bounds, mapping to our MAB setting, are $\tilde{O}(C^{\frac{1}{K+2}}T^{\frac{K+2}{K+3}})$ and $\tilde{O}(C^{\frac{1}{K+1}}T^{\frac{K+1}{K+2}})$, which have a much worse dependence on $T$ than the ones in Theorem 8, especially when $K$ is large.
This is because the regret upper bounds of their base algorithms have a much worse dependence on $T$ than our base SE-WR-Stop algorithm.
This highlights the importance of devising the suitable base algorithm instances for MAB with the known attack budget in §4.2.

###### Remark 9 (Regret comparison for unknown $C$ case in Figure 2 ) .

The section presents three different upper bounds for unknown attacks, one additive $\tilde{O}(\sqrt{KT}+KC^{2})$ by PE-WR and two multiplicative $\tilde{O}(C\sqrt{K}T^{\frac{2}{3}}),\tilde{O}(C^{2}K\sqrt{T})$ by two types of MS-SE-WR.
Giving attack $C=T^{\beta}$ for some parameter $\beta\in[0,1]$, these three bounds can be written in the form of $\tilde{O}(T^{\gamma})$ for corresponding exponents $\gamma$.
Figure 2 compares these bounds in terms of the exponent $\gamma$ by varying $\beta$.
Comparing all three bounds, the additive bound is better than both multiplicative ones when $\beta\leqslant\frac{4}{9}$, and the $\tilde{O}(C\sqrt{K}T^{\frac{2}{3}})$ bound is better than the additive one when $\beta>\frac{4}{9}$.
Comparing among the two multiplicative bounds, the $\tilde{O}(C^{2}K\sqrt{T})$ is better than $\tilde{O}(C\sqrt{K}T^{\frac{2}{3}})$ when $\beta\leqslant\frac{1}{3}$, and vice versa.
Since Figure 2 suggests that no single algorithm consistently outperforms the others, and without prior knowledge of $C$, there is no definitive rule for selecting a specific algorithm in practice.

Conclusion Remark
This paper presents a comprehensive study of bandit algorithms robust to adversarial attacks, examining two scenarios: attacks with or without knowledge of the attack budget, and two types of regret bounds—additive and multiplicative dependence on the total attack $C$. For each of these four cases, we propose corresponding algorithms and establish their regret upper bounds, which are subsequently demonstrated to be tight by providing regret lower bounds.

###### Lemma 7 .

###### Theorem 8 .

###### Remark 9 (Regret comparison for unknown C 𝐶 C italic_C case in Figure 2 ) .

## Appendix A Other Model Details: Corruption Process, Regret Discussion

In this section, we provide more details on the corruption process. At each round $t\in\{1,2,\dots,T\}$, the adversary observes the realized rewards $X_{k,t}$ for all arms $k$, as well as the rewards and actions of the learner in previous rounds. The adversary then chooses the corrupted rewards $\tilde{X}_{k,t}$ for all arms $k$. The learner pulls an arm $I_{t}$ (maybe randomly) and observes the attacked reward $\tilde{X}_{I_{t},t}$. We summarize the decision process in Procedure 5.
We denote the total amount of corruption as

$$ $C^{\prime}\coloneqq\sum_{t=1}^{T}\max_{k}\lvert X_{k,t}-\tilde{X}_{k,t}\rvert,$ $$

where $I_{t}$ is the pulled arm at time slot $t$.

Figure: Procedure 5 Decision under Corruptions

###### Remark 10 (Regret defined by corrupted rewards) .

Beside the regret defined on raw reward in (1), one can also define the regret based on the corrupted rewards as follows, $\tilde{R}_{T}\coloneqq\max_{k\in\mathcal{K}}\sum_{t\in\mathcal{T}}(\tilde{X}_{
k,t}-\tilde{X}_{I_{t},t}).$
This definition is considered in Zimmert and Seldin [], Bogunovic et al. []. As the adversary can manipulate at most $C$ rewards, one can easily show that, $\lvert\tilde{R}_{T}-R_{T}\rvert\leqslant 2C.$
We will focus on the regret defined by raw rewards (1) in the following, as most results in this paper have at least a linear dependence on $C$.

###### Remark 10 (Regret defined by corrupted rewards) .

## Appendix B Proof for Lower Bound

*

###### Proof of Theorem 3.1 .

We consider $K$ instances of a MAB game where for instance $\mathcal{I}_{k}$ for any $k\in\{1,2,\dots,K\}$, the arm $k$ has reward $\epsilon>0$ and all other arms have reward 0 0 without any noise.

The adversary’s policy is that whenever the algorithm pulls an arm with a non-zero reward, the adversary attacks the algorithm by changing the reward of the arm to 0 0. The adversary can conceal the optimal arm for $\lfloor\frac{C}{\epsilon}\rfloor$ pulls.

After $\lfloor\frac{C}{\epsilon}\rfloor\lfloor\frac{K}{2}\rfloor$ time slots, there exists at least $\lfloor\frac{K}{2}\rfloor$ arms that are pulled at most $\lfloor\frac{C}{\epsilon}\rfloor$ times. That is, if the optimal arm is among these $\lfloor\frac{K}{2}\rfloor$ arms, the algorithm cannot identify the optimal arm.
Let us pick the instance whose optimal arm is among these $\lfloor\frac{K}{2}\rfloor$ arms. Then, during these $\lfloor\frac{C}{\epsilon}\rfloor\lfloor\frac{K}{2}\rfloor$ time slots, the algorithm needs to pay the regret of

$$ $\left\lfloor\frac{C}{\epsilon}\right\rfloor\left(\left\lfloor\frac{K}{2}\right \rfloor-1\right)\epsilon=\Omega(KC).$ $$

∎

Proposition 1
For gap-dependent regret bounds and any consistent bandit algorithm(^5^55When $C=0$, a consistent bandits algorithm has regret $\bar{R}_{T}\leqslant O(T^{\alpha})$ for any $\alpha\in(0,1)$.), the lower bound is roughly $\Omega\left(\sum_{k\neq k^{*}}\frac{\log T}{\Delta_{k}}+KC\right)$, or formally, for some universal constant $\xi>0$,

$$ $\liminf_{T\to\infty}\frac{\bar{R}_{T}-\xi KC}{\log T}\geqslant\sum_{k\neq k^{* }}\frac{1}{2\Delta_{k}}.$ $$

For gap-independent cases, the lower bound is

$$ $\bar{R}_{T}\geqslant\Omega(\sqrt{KT}+KC).$ $$

###### Proof of Proposition 1 .

From bandits literature, e.g., Lattimore and Szepesvári [, Chapter 16], we know that the pseudo regret of any consistent bandit algorithm can be lower bounded as follows,

$$ $\liminf_{T\to\infty}\frac{\bar{R}_{T}}{\log T}\geqslant\sum_{k\neq k^{*}}\frac {1}{\Delta_{k}}.$ $$

On the other hand, we can rewrite the $\Omega(KC)$ lower bound in Theorem 3.1 as follows,

$$ $\liminf_{T\to\infty}\frac{\bar{R}_{T}-\xi KC}{\log T}\geqslant 0,$ $$

where $\xi>0$ is a universal constant. Adding the above two inequalities and dividing both side by $2$, we have

$$ $\liminf_{T\to\infty}\frac{\bar{R}_{T}-(\xi/2)KC}{\log T}\geqslant\sum_{k\neq k ^{*}}\frac{1}{2\Delta_{k}}.$ $$

For the gap-independent case, recall in bandits literature [Lattimore and Szepesvári, , Chapter 15], we have the $\bar{R}_{T}\geqslant\Omega(\sqrt{KT})$ lower bound.
Combining it with the $\Omega(KC)$ lower bound in Theorem 3.1 yields $\bar{R}_{T}\geqslant\Omega(\max\{\sqrt{KT},KC\})=\Omega(\sqrt{KT}+KC)$ lower bound.
∎

Proposition 3 (Achievable additive regret bounds)
Given any parameter $\alpha\in[\frac{1}{2},1)$, for any bandit algorithm that achieves an additive regret upper bound of the form $O(T^{\alpha}+C^{\beta})$, we have $\beta\geqslant\frac{1}{\alpha}$.

Proposition 4 (Achievable multiplicative regret bounds)
Given parameter $\alpha\in[\frac{1}{2},1)$, for any bandit algorithm that achieves a multiplicative regret bound of the form $O(T^{\alpha}C^{\beta})$, we have $\beta\geqslant\frac{1}{\alpha}-1$.

###### Proof of Propositions 3 and 4 .

We use contradiction to prove both propositions.
We first prove Proposition 3. Given Theorem 2, we know that there exists an attack policy with $C=\Theta(R_{T})$ that can make the algorithm suffer linear regret. Thus, if the algorithm achieves an additive regret upper bound of the form $O(T^{\alpha}+C^{\beta})$ with $\beta<\frac{1}{\alpha}$, then the algorithm only suffers a sublinear regret when $C=T^{\alpha}$, which contradicts Theorem 2. Thus, the parameter $\beta\geqslant\frac{1}{\alpha}$.
Proposition 4 can be proved via a similar contradiction argument.
∎

###### Proof of Theorem 3.1 .

###### Proof of Proposition 1 .

###### Proof of Propositions 3 and 4 .

## Appendix C Deferred Algorithm Pseudo-Code

Figure: Algorithm 6 SE-WR-Stop: Successive Elimination with Wide Confidence Radius and Stop Condition

## Appendix D Proof for Upper Bounds with Known Attack

*

###### Proof of Theorem 2 .

We first recall the following lemma from Lykouris et al. [].

###### Lemma 11 ( Lykouris et al. [ 2018 , Lemma 3.1] ) .

With a probability of at least $1-\delta$, the optimal arm $k^{*}$ is never eliminated.

Next, we prove a lemma shows the sufficient number of pulling that are necessary for a suboptimal arm to be eliminated. This lemma is tighter than the one in Lykouris et al. [, Lemma 3.2] (proved for $N_{k}\geqslant\frac{36\log(2KT/\delta)+36C}{\Delta_{k}^{2}}$), and, based on it, we derive tighter regret bounds.

###### Lemma 12 .

With a probability of at least $1-\delta$, all suboptimal arms $k\neq k^{*}$ are eliminated after pulling each arm $N_{k}\geqslant\frac{36\log(2KT/\delta)}{\Delta_{k}^{2}}+\frac{6C}{\Delta_{k}}$ times.

###### Proof for Lemma 12 .

With Lemma 11, we know that the optimal arm $k^{*}$ is never eliminated. Thus, in the following, we show that the suboptimal arm $k$ will be eliminated by the optimal arm $k^{*}$ on or before $N_{k}\geqslant\frac{64\log(2KT/\delta)}{\Delta_{k}^{2}}+\frac{8C}{\Delta_{k}}$.

Denote $\hat{\mu}_{k}$ as the empirical mean of the raw stochastic reward observation of arm $k$.
By Hoeffding’s inequality, we have, with a probability of at least $1-\frac{\delta}{KT}$,

$$ $\displaystyle\lvert\hat{\mu}_{k}-\mu_{k}\rvert$ $\displaystyle\leqslant\sqrt{\frac{\log(2KT/\delta)}{N_{k}}}$ (7) $\displaystyle\leqslant\frac{\Delta_{k}}{8},$ $$

where the last inequality is due to $N_{k}\geqslant\frac{64\log(2KT/\delta)}{\Delta_{k}^{2}}$.

Comparing the true empirical mean $\hat{\mu}_{k}$ with the attacked empirical mean $\mu_{k}$, we have

$$ $\lvert\tilde{\mu}_{k}-\hat{\mu}_{k}\rvert\leqslant\frac{C}{N_{k}}\leqslant \frac{\Delta_{k}}{8},$ $$

where the last inequality is due to $N_{k}\geqslant\frac{8C}{\Delta_{k}}$.
Combining the two inequalities, we have

$$ $\lvert\tilde{\mu}_{k}-{\mu}_{k}\rvert\leqslant\frac{\Delta_{k}}{4}.$ $$

Last, we show that the elimination condition for arm $k$ would have been trigger before $N_{k}\geqslant\frac{64\log(2KT/\delta)}{\Delta_{k}^{2}}+\frac{8C}{\Delta_{k}}$ as follows,

$$ $\displaystyle\tilde{\mu}_{k^{*}}-2\left(\sqrt{\frac{\log(2KT/\delta)}{N_{k}}}+ \frac{C}{N_{k}}\right)$ $\displaystyle\geqslant\tilde{\mu}_{k^{*}}-2\left(\frac{\Delta_{k}}{8}+\frac{ \Delta_{k}}{8}\right)$ $\displaystyle\geqslant\mu_{k^{*}}-\frac{\Delta_{k}}{4}-\frac{2\Delta}{4}$ $\displaystyle=\mu_{k}+\frac{\Delta}{4}$ $\displaystyle\geqslant\tilde{\mu}_{k}.$ $$

∎

As the pseudo regret is upper bounded at most $\sum_{k}\Delta_{k}N_{k}$, we have

$$ $\begin{split}\bar{R}_{T}&\leqslant\sum_{k\neq k^{*}}\Delta_{k}N_{k}\\ &\leqslant\sum_{k\neq k^{*}}\Delta_{k}\left(\frac{64\log(2KT/\delta)}{\Delta_{ k}^{2}}+\frac{8C}{\Delta_{k}}\right)\\ &=O\left(\sum_{k\neq k^{*}}\frac{\log(KT/\delta)}{\Delta_{k}}+KC\right)\\ &\leqslant O\left(\sum_{k\neq k^{*}}\frac{\log T}{\Delta_{k}}+KC\right),\end{split}$ (8) $$

where the last inequality is by choosing $\delta=\frac{K}{T}$.

Transfer psudoe-regret to realized regret.
Next, we show the high probability bound for the realized regret $R_{T}$. Multiplying $N_{k}$ to both side of (7), we have that, for any arm $k$, the difference between the actual accumulated reward and its expected counterpart is upper bounded by $\sqrt{N_{k}\log(2KT/\delta)}$ with a probability of at least $1-\delta/KT$. The probability of any of above event does not hold is at most $1-\delta$.

For any suboptimal arm $k$, we bound the difference as follows,

$$ $\sqrt{N_{k}\log(2KT/\delta)}\leqslant N_{k}\sqrt{\frac{\log(2KT/\delta)}{N_{k} }}\leqslant N_{k}\Delta_{k}\sqrt{\frac{\log(2KT/\delta)}{64\log(2KT/\delta)+8C \Delta_{k}}}\leqslant\frac{N_{k}\Delta_{k}}{8}.$ $$

In case that the arm $k^{\prime}$ with highest empirical mean is not the optimal arm $k^{*}$, for example, this arm $k^{\prime}$ has a smaller reward gap $\Delta_{k}\leqslant O(\sqrt{{1}/{T}})$, the regret reduction due to this event is at most $N_{k^{\prime}}\Delta_{k^{\prime}}$.

Putting the potential impact of different kinds of reward realization above, we can bound the realized regret by $O(\sum_{k\neq k^{*}}N_{k}\Delta_{k})$ still. Thus, with similar derivation as (8), we have the realized regret of the algorithm is at most

$$ $O\left(\sum_{k\neq k^{*}}\frac{\log(KT/\delta)}{\Delta_{k}}+KC\right)\text{ with probability }1-\delta.$ $$

∎

###### Proof of Theorem 2 .

###### Lemma 11 ( Lykouris et al. [ 2018 , Lemma 3.1] ) .

###### Lemma 12 .

###### Proof for Lemma 12 .

## Appendix E Proof for Upper Bounds with unknown Attack

*

###### Proof of Theorem 3 .

For $C>\sqrt{T}/K$, the $\tilde{O}(\sqrt{KT}+KC^{2})=O(T)$ upper bound holds trivially. Hence, we only consider $C\leqslant\sqrt{T}/K$ in this proof.

Note that the elimination condition in Algorithm 3 fails with a probability of at most $\delta/KH$.
Applying a union bound to sum all potential failure probabilities show that, with a probability of at least $1-\delta$, the elimination condition works properly for all arms in all phases.
In the rest of the proof, we exclude this failure probability and assume that the elimination only fails when $C>\hat{C}_{h}$.

Denote $H^{\prime}$ as the actually number of phases, while recall $H=\lceil\log_{2}T\rceil-1$ is the upper bound of the number of phases.
As the analysis of Algorithm 2 shows, for phase $h$ with $\hat{C}_{h}>C$, the optimal arm $k^{*}$ is in the candidate set $\mathcal{S}_{h}$ with high probability.
Denote $h^{\prime}$ as the first phase with $\hat{C}_{h^{\prime}}\leqslant C$, implying $H-h^{\prime}\leqslant\log_{2}C$.

Denote $k_{h}^{*}$ as the arm with highest reward mean in phase $h$.
Then, we have $k_{h}^{*}=k^{*}$ for $h<h^{\prime}$.
Next, we use induction to show, for $h\geqslant h^{\prime}$, the remaining best arm $k_{h}^{*}$ is close to the optimal arm $k^{*}$ as follows,

$$ $\mu_{k^{*}}-\mu_{k_{h}^{*}}\leqslant\frac{2C}{L_{h}/\lvert\mathcal{S}_{h} \rvert}.$ $$

If the optimal arm is eliminated in phase $h^{\prime}$, then we have

$$ $\hat{\mu}_{k^{*},h^{\prime}}\leqslant\max_{k\in\mathcal{S}_{h^{\prime}}}\hat{ \mu}_{k,h^{\prime}}-2\left(\sqrt{\frac{\log(2KH/\delta)}{L_{h^{\prime}}/\lvert \mathcal{S}_{h^{\prime}}\rvert}}+\frac{\hat{C}_{h^{\prime}}}{L_{h^{\prime}}/ \lvert\mathcal{S}_{h^{\prime}}\rvert}\right).$ $$

Denote $\hat{k}_{h^{\prime}}^{*}=\operatorname*{arg\,max}_{k\in\mathcal{S}_{h^{\prime}
}}\hat{\mu}_{k,h^{\prime}}$. We have

$$ $\displaystyle\mu_{\hat{k}_{h^{\prime}}^{*}}$ $\displaystyle\overset{(a)}{\geqslant}\hat{\mu}_{\hat{k}_{h^{\prime}}^{*},h^{ \prime}}-\left(\sqrt{\frac{\log(2KH/\delta)}{L_{h^{\prime}}/\lvert\mathcal{S}_ {h^{\prime}}\rvert}}+\frac{C}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{\prime}} \rvert}\right)$ $\displaystyle\overset{(b)}{\geqslant}\hat{\mu}_{k^{*},h^{\prime}}+2\left(\sqrt {\frac{\log(2KH/\delta)}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{\prime}}\rvert}} +\frac{\hat{C}_{h^{\prime}}}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{\prime}} \rvert}\right)-\left(\sqrt{\frac{\log(2KH/\delta)}{L_{h^{\prime}}/\lvert \mathcal{S}_{h^{\prime}}\rvert}}+\frac{C}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^ {\prime}}\rvert}\right)$ $\displaystyle\overset{(c)}{\geqslant}\mu_{k^{*}}+2\left(\sqrt{\frac{\log(2KH/ \delta)}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{\prime}}\rvert}}+\frac{\hat{C}_{ h^{\prime}}}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{\prime}}\rvert}\right)-2 \left(\sqrt{\frac{\log(2KH/\delta)}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{ \prime}}\rvert}}+\frac{C}{L_{h^{\prime}}/\lvert\mathcal{S}_{h^{\prime}}\rvert}\right)$ $\displaystyle=\mu_{k^{*}}-\frac{2(C-\hat{C}_{h^{\prime}})}{L_{h^{\prime}}/ \lvert\mathcal{S}_{h^{\prime}}\rvert}$ $\displaystyle\geqslant\mu_{k^{*}}-\frac{2C}{L_{h^{\prime}}/\lvert\mathcal{S}_{ h^{\prime}}\rvert}$ $\displaystyle\geqslant\mu_{k^{*}}-\frac{2CK}{L_{h^{\prime}}}$ $$

where inequalities (a) and (c) come from the Hoeffding’s inequality and the attack $C$,
inequality (b) is due to the elimination condition in round $h^{\prime}$.
That is,

$$ $\mu_{k^{*}}-\mu_{\hat{k}_{h^{\prime}}^{*}}\leqslant\frac{2CK}{L_{h^{\prime}}}.$ $$

With similar analysis, we can show, $\mu_{\hat{k}_{h^{\prime}+i}^{*}}-\mu_{\hat{k}_{h^{\prime}+i+1}^{*}}\leqslant
\frac{2CK}{L_{h^{\prime}+i}},\text{ for all }i=1,\dots,H-h^{\prime}-1.$
Based on the inequality, we further have, for any $h\geqslant h^{\prime},$

$$ $\mu_{k^{*}}-\mu_{\hat{k}_{h}^{*}}\leqslant\sum_{i=0}^{h-h^{\prime}}\frac{2CK}{ L_{h^{\prime}+i}}=\sum_{i=0}^{h-h^{\prime}}\frac{2CK}{L_{0}2^{h^{\prime}+i}} \leqslant\frac{2CK}{L_{0}2^{h^{\prime}+1}}.$ (9) $$

Next, we decompose the pseudo regret as follows,

$$ $\displaystyle\bar{R}_{T}$ $\displaystyle=\sum_{t=1}^{T}(\mu_{k^{*}}-\mu_{I_{t}})=\sum_{k\in\mathcal{K}}N_ {k,T}(\mu_{k^{*}}-\mu_{k})=\sum_{h=0}^{H^{\prime}}\sum_{k\in\mathcal{S}_{h}} \frac{L_{h}}{\lvert\mathcal{S}_{h}\rvert}(\mu_{k^{*}}-\mu_{k})$ $\displaystyle\leqslant L_{0}+\sum_{h=1}^{h^{\prime}}\sum_{k\in\mathcal{S}_{h}} \frac{L_{h}}{\lvert\mathcal{S}_{h}\rvert}(\mu_{k^{*}}-\mu_{k})+\sum_{h=h^{ \prime}+1}^{H^{\prime}}\sum_{k\in\mathcal{S}_{h}}\frac{L_{h}}{\lvert\mathcal{S }_{h}\rvert}(\mu_{k^{*}}-\mu_{k})$ $\displaystyle=L_{0}+\underbrace{\sum_{h=1}^{h^{\prime}}\sum_{k\in\mathcal{S}_{ h}}\frac{L_{h}}{\lvert\mathcal{S}_{h}\rvert}(\mu_{k^{*}}-\mu_{k})+\sum_{h=h^{ \prime}+1}^{H^{\prime}}\sum_{k\in\mathcal{S}_{h}}\frac{L_{h}}{\lvert\mathcal{S }_{h}\rvert}(\mu_{k_{h}^{*}}-\mu_{k})}_{\text{Part I}}$ $\displaystyle\qquad+\underbrace{\sum_{h=h^{\prime}+1}^{H^{\prime}}\sum_{k\in \mathcal{S}_{h}}\frac{L_{h}}{\lvert\mathcal{S}_{h}\rvert}(\mu_{k^{*}}-\mu_{k_{ h}^{*}})}_{\text{Part II}}.$ $$

To bound Part I, we notice that all arms in $\mathcal{S}_{h}$ are not eliminated in the end of the previous phase, implying, for $h<h^{\prime}$,

$$ $\begin{split}\mu_{k}&\overset{(a)}{\geqslant}\hat{\mu}_{k}-\left(\sqrt{\frac{ \log(2KH/\delta)}{L_{h-1}/\lvert\mathcal{S}_{h-1}\rvert}}+\frac{C}{L_{h-1}/ \lvert\mathcal{S}_{h-1}\rvert}\right)\\ &\overset{(b)}{\geqslant}\max_{k^{\prime}\in\mathcal{S}_{h-1}}\hat{\mu}_{k^{ \prime},h-1}-2\left(\sqrt{\frac{\log(2KH/\delta)}{L_{h-1}/\lvert\mathcal{S}_{h -1}\rvert}}+\frac{\hat{C}_{h-1}}{L_{h-1}/\lvert\mathcal{S}_{h-1}\rvert}\right) \\ &\qquad-\left(\sqrt{\frac{\log(2KH/\delta)}{L_{h-1}/\lvert\mathcal{S}_{h-1} \rvert}}+\frac{C}{L_{h-1}/\lvert\mathcal{S}_{h-1}\rvert}\right)\\ &\overset{(c)}{\geqslant}\hat{\mu}_{k^{*},h-1}-\left(3\sqrt{\frac{\log(2KH/ \delta)}{L_{h-1}/\lvert\mathcal{S}_{h-1}\rvert}}+\frac{2\hat{C}_{h-1}+C}{L_{h- 1}/\lvert\mathcal{S}_{h-1}\rvert}\right)\\ &\overset{(d)}{\geqslant}\mu_{k^{*}}-\left(4\sqrt{\frac{\log(2KH/\delta)}{L_{h -1}/\lvert\mathcal{S}_{h-1}\rvert}}+\frac{2\hat{C}_{h-1}+2C}{L_{h-1}/\lvert \mathcal{S}_{h-1}\rvert}\right),\end{split}$ $$

where inequalities (a) and (d) are due to the Hoeffding’s inequality and the attack $C$, inequality (b) is due to the elimination condition, and inequality (c) is due to $k^{*}\in\mathcal{S}_{h-1}$.
That is, for arms $k\in\mathcal{S}_{h}$, we have

$$ $\mu_{k^{*}}-\mu_{k}\leqslant 4\sqrt{\frac{\log(2KH/\delta)}{L_{h-1}/\lvert \mathcal{S}_{h-1}\rvert}}+\frac{2(\hat{C}_{h-1}+C)}{L_{h-1}/\lvert\mathcal{S}_ {h-1}\rvert}.$ (10) $$

As we have $k_{h}^{*}\in\mathcal{S}_{h}$, and with the same derivation as (10), we also have

$$ $\mu_{k_{h}^{*}}-\mu_{k}\leqslant 4\sqrt{\frac{\log(2KH/\delta)}{L_{h-1}/\lvert \mathcal{S}_{h-1}\rvert}}+\frac{2(\hat{C}_{h-1}+C)}{L_{h-1}/\lvert\mathcal{S}_ {h-1}\rvert}.$ (11) $$

Therefore, we have

$$ $\begin{split}&\quad\sum_{h=1}^{h^{\prime}}\sum_{k\in\mathcal{S}_{h}}\frac{L_{h }}{\lvert\mathcal{S}_{h}\rvert}\Delta_{k}+\sum_{h=h^{\prime}+1}^{H^{\prime}} \sum_{k\in\mathcal{S}_{h}}\frac{L_{h}}{\lvert\mathcal{S}_{h}\rvert}(\mu_{k_{h} ^{*}}-\mu_{k})\\ &\overset{(a)}{\leqslant}\sum_{h=1}^{H^{\prime}}L_{h}\cdot 4\sqrt{\frac{\log(2 KH/\delta)}{L_{h-1}/\lvert\mathcal{S}_{h-1}\rvert}}+\frac{2(\hat{C}_{h-1}+C)}{ L_{h-1}/\lvert\mathcal{S}_{h-1}\rvert}.\\ &=\sum_{h=1}^{H^{\prime}}\left(4\sqrt{\frac{L_{h}^{2}\log(2KH/\delta)}{L_{h-1} /\lvert\mathcal{S}_{h-1}\rvert}}+\frac{2L_{h}(\hat{C}_{h-1}+C)}{L_{h-1}/\lvert \mathcal{S}_{h-1}\rvert}\right)\\ &\leqslant\sum_{h=1}^{H^{\prime}}\left(4\sqrt{2L_{h}K\log(2KH/\delta)}+4K(\hat {C}_{h-1}+C)\right)\\ &=4\sqrt{2K\log(2KH/\delta)}\sum_{h=1}^{H^{\prime}}\sqrt{L_{h}}+4K\sum_{h=1}^{ H^{\prime}}(\hat{C}_{h-1}+C)\\ &\overset{(a)}{\leqslant}4g\sqrt{2KL_{0}\log(2KH/\delta){T}}+4\sqrt{T}\log_{2} T+4KC\log_{2}T.\end{split}$ (12) $$

where inequality (a) is due to (10) and (11), and
inequality (b) is because $\sum_{h=1}^{H^{\prime}}\sqrt{L_{h}}\leqslant g\sqrt{T}$ since the summation of a geometric increasing series is upper bounded by $g\sqrt{L_{H^{\prime}}}$, for some universal constant $g>0$, and $L_{H^{\prime}}\leqslant T$.

Next, we bound Part II as follows,

$$ $\begin{split}\sum_{h=h^{\prime}+1}^{H^{\prime}}\sum_{k\in\mathcal{S}_{h}}\frac {L_{h}}{\lvert\mathcal{S}_{h}\rvert}(\mu_{k^{*}}-\mu_{k_{h}^{*}})&\overset{(a) }{\leqslant}\sum_{h=h^{\prime}+1}^{H^{\prime}}\sum_{k\in\mathcal{S}_{h}}\frac{ L_{h}}{\lvert\mathcal{S}_{h}\rvert}\frac{2CK}{L_{0}2^{h^{\prime}+1}}\\ &=\sum_{h=h^{\prime}+1}^{H^{\prime}}\frac{2CKL_{h}}{L_{0}2^{h^{\prime}+1}}\\ &={2CK}\sum_{h=h^{\prime}+1}^{H^{\prime}}2^{h-(h^{\prime}+1)}\\ &\overset{(b)}{\leqslant}KC^{2},\end{split}$ (13) $$

where inequality (a) is due to (9), and
inequality (b) is because $H^{\prime}-h^{\prime}\leqslant H-h^{\prime}\leqslant\log_{2}C$.

Hence, substituting (12) and (13) into the regret bound, we have the pseudo-regret bound with a probability of at least $1-\delta$ as follows,

$$ $\begin{split}\bar{R}_{T}&\leqslant L_{0}+4g\sqrt{2K\log(2KH/\delta){T}}+4\sqrt {T}\log_{2}T+4KC\log_{2}T+KC^{2}\\ &={O}\left(\sqrt{KT\log\left(\frac{K\log T}{\delta}\right)}+\sqrt{T}\log T+KC \log T+KC^{2}\right).\end{split}$ $$

With a similar analysis as in the proof in Theorem 2, we can show that the realized regret $R_{T}$ also has the same upper bound (in order) with a probability of at least $1-\delta$.
∎

###### Proof of Theorem 3 .

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: 1) Is the uniqueness of the best arm really needed? What happens if this assumption is not fullfilled?

2) Could you provide concrete applications addressed by your model?

There are a few typos:

091 - To address with MAB with -> To address the MAB with 
103 - Show that which type -> Show which type
185 - Lipchitz -> Lipschitz
soundness: 4
strengths: 1) The paper explores an under-studied area of stochastic bandits where adversarial attacks are present and obtains novel results as well as improving prior work about the already studied corruption model.
2) The theoretical bounds are tight (up to log terms), with mathematical proofs for each statement.
3) Experimental results to validate the theoretical claims are provided.
4) The authors do a good job clarifying the differences between corruption and attack models, highlighting the need for specialized approaches.
summary: The paper develops stochastic multi-armed bandit algorithms that are robust against adversarial attacks. These attacks can alter the reward the learner observes, and the adversary decides to alter the reward with full knowledge of the action selected by the learner and the realization of the corresponding reward. This way, the model introduces complexities beyond the corruption model, where the adversary has to decide whether or not to corrupt the rewards before having this piece of information. The authors present algorithms for both known and unknown attack budgets with additive and multiplicative regret bounds with respect to the attack budget, providing theoretical proofs of tightness and empirical validations.
weaknesses: 1) The implications for practical settings, such as recommendation systems or online auctions, could use some expanding.
2) Unfortunately, all the proofs are relegated to the appendix.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See 4 and 6 in the Weaknesses section.
soundness: 3
strengths: - This paper addresses a gap in the literature, recognizing that adversarial attacks have not been thoroughly explored within the classical multi-armed bandit (MAB) framework and effectively filling this gap.
- The authors examine both additive and multiplicative bounds, providing a clear comparison that shows which approach performs better based on the attack budget C.
- Figures 1 and, especially, Figure 2 nicely illustrate the results of attack-based multiplicative and additive bounds, offering a well-structured presentation that I haven't seen in comparable works with this level of detail.
- I also like seeing the clear separation between corruption and attack results/settings in one place.
- The paper presents novel findings and situates them within the existing literature, demonstrating that the derived upper bounds are tight (known C case).
summary: The paper investigates the classical MAP problem in the adversarial attack setting. The authors provide several tight results covering the case when the attack budget is known/unknown, multiplicative and additive bounds, as well as lower bounds.
weaknesses: 1. Algorithm Design: I didn’t notice any novel or original elements in terms of algorithm design. The PE algorithm has been applied in this context in prior work (cited below), and the idea of using CORRAL has already been explored in similar settings, such as in Misspecified Gaussian Process Bandit Optimization. However, I only find this to be a minor weakness of the paper. 

2. Terminology: I like the terminology of “attacks” to distinguish it from the classical “corrupted” setting. However, if the authors intend to introduce this terminology shift, they should properly credit the original paper that first explored this setting and provided robust algorithms: “Corruption-Tolerant Gaussian Process Bandit Optimization.” To my knowledge, this was the first work to present robust algorithms for scenarios in which the attacker can observe the learner's decisions.

3. Literature Review: The literature review in this paper can be improved. The reference section is also too brief and lacks organization. For example, Bogunovic et al. (2020), as cited, do not address the linear setting; this is covered in other relevant papers that are not cited, such as Stochastic Linear Bandits Robust to Adversarial Attacks and A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits.

4. Lower Bound Claim: The paper claims that the lower bound result of Ω(KC) is new; however, this result is already established in Stochastic Linear Bandits Robust to Adversarial Attacks (see Appendix C.3). The proof and exposition provided here are quite similar to those in the mentioned paper.

5. Venue Suitability: I’m not entirely sure this paper is a strong fit for ICLR, as I’m not aware of similar works published at this venue previously. This is a consideration for the authors, as they might find broader reach at an alternative venue.

6. Clarity of Comparison (Lines 417-422): The comparison in this section is unclear, and I would appreciate a clearer exposition/steps, especially since the reference provided here is incorrect.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: None
soundness: 3
strengths: The paper advances the state of the art on algorithms robust to adversarial attacks. The paper is well-written and the relationship/improvement relative to previous work is well described.
summary: The paper studies the design of stochastic bandits algorithms robust to adversarial attacks. In particular, the paper considers an easier setting in which the learner is aware of the attacker budget, and a harder setting in which the learner is not aware of the attacker budget. These results are complemented by lower bounds. Finally, the authors provide an experimental analysis that shows the effectiveness of the proposed approach.
weaknesses: The technical contribution is quite weak. For instance, the algorithmic approaches follow previous work and the analysis is not very involved.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 2
questions: 1. Can you please mention how the lower bounds change or are implied from the corruptions setting to the attack setting in case of unknown horizons?

2. Can you please explain if the gap-dependent results in the unknown corruption case can be obtained for the algorithms under consideration? 

3. Can you please explain why the algorithms potentially perform worse in low corruption settings in the experiments?
soundness: 3
strengths: 1. The paper differentiates between attack and corruption models of manipulating multi-armed bandits. It provides insights into the difference between corruption and attacks in terms of the required corruption/attack budget and thus the increased difficulty in preventing attacks compared to corruption.

2. For the successive elimination algorithm SE-WR with increased confidence, also used in Lykouris et al. (2018), the paper shows a tighter regret bound, by better analysis of the concentration results which leads to $O(KC)$ term instead of a gap dependent term in  Lykouris et al. (2018).

3. The authors also give a gap-independent bound for SE-WR and extend the SE-WR algorithm to work in the unknown attack budget settings. They also provide an analysis of the resulting algorithms. 

4. The paper also provides experimental evidence showing the effectiveness of their algorithms against the attack strategies developed by Jun et al. 2018 in comparison with multiple MAP defense strategies proposed in the literature.
summary: This paper studies stochastic bandit algorithms which are robust to adversarial attacks under a strong adversary that can see the observed arm before attacking.   
The paper considers settings with unknown budget cost or known budget cost $C$.
In the known budget case, they provide a gap dependent $((\frac{K}{\delta}) \log T  + KC))$ upper bound that matches the lower bound. They also give gap-independent extensions with upper bounds of $\tilde{O}(\sqrt{KTC})$ or $\tilde{O}(\sqrt{KT} + KC)$ bound.

For the unknown case, they show two stopping criteria-based algorithms, one with an additive dependence in C: $O(\sqrt{KT} + KC^2)$. They show an algorithm that gets $O(T^\alpha)$ regret without corruptions, must have at least $O(T^\alpha + C^\beta)$ regret for $\beta \geq \frac{1}{\alpha}$, thus this upper bound matches this lower bounds in exponents of $C$ (given that it has $\sqrt{T}$ dependence without $C$). Similarly, they give algorithms with multiplicative dependence on $C$ for the regret, that is  $\tilde{O}(\sqrt{KC}T^{\frac{2}{3}})$ or $\tilde{O}(KC\sqrt{T})$.

The paper also provides experimental evidence showing the effectiveness of their algorithms against the attack strategies developed by Jun et al. 2018 comparing it will other corruption-robust MAB algorithms studies in the literature.
weaknesses: 1. The results or the discussion do not clarify whether gap-dependent results can be obtained for the unknown horizon setting. 


2. Since this paper focuses on making the distinction between attacks and corruption, it seems the main difference is in the inability to use randomization to reduce the scale of the attack, resulting in the need for deterministic algorithms where potentially any arm suffers from all of the corruptions. Thus in the known corruption level case, the results for the setting are directly implied by earlier. (Although this work does a tighter analysis in terms of gaps). A thorough analysis of the lower bounds comparing the setting rather than just comparing the dependence on $K$  could benefit the reader. 

3. Experimental results don't have confidence bars, and in the case of no corruptions with known budgets, the STOP algorithms perform worse than other methods. Some discussion on the performance in the absence of corruption is warranted.

Nit:
1. In general, the writing of the paper is very focused on presenting as many results are possible and is very dense in terms of results. The paper could have been formatted better with more discussions around interpreting the results rather than having so many results in the main paper.

 2. There are some typos and inconsistencies in the theorem statements and proofs. For eg in proof of Lemma 14:
  i) the constants are changed from 36 to 64 in $N_k$.
  ii) Line 798, it should be 'triggered' instead of 'trigger'
   iii) Similarly lines 804 to 807 on page 15 in the same proof have $\delta$ with subscripts.

Meta-review: There is a general consensus (although mostly not especially strong) that this work provides sufficiently strong results on robust bandits, particularly distinguishing whether or not the attacker knows the exact action taken.  The authors may want to consider mentioning the concurrent work “Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification” which also focuses a lot on this distinction, albeit in the slightly different context of linear bandits.

Decision: Accept (Poster)