Adversarial Attacks on Cooperative Multi-agent Bandits

## Abstract

Abstract Cooperative multi-agent multi-armed bandits ( CMA2B ) consider the collaborative efforts of multiple agents in a shared multi-armed bandit game. We study latent vulnerabilities exposed by this collaboration and consider adversarial attacks on a few agents with the goal of influencing the decisions of the rest. More specifically, we study adversarial attacks on CMA2B in both homogeneous settings, where agents operate with the same arm set, and heterogeneous settings, where agents have distinct arm sets. In the homogeneous setting, we propose attack strategies that, by targeting just one agent, convince all agents to select a particular target arm T − o ​ ( T ) 𝑇 𝑜 𝑇 T-o(T) times while incurring o ​ ( T ) 𝑜 𝑇 o(T) attack costs in T 𝑇 T rounds. In the heterogeneous setting, we prove that a target arm attack requires linear attack costs and propose attack strategies that can force a maximum number of agents to suffer linear regrets while incurring sublinear costs and only manipulating the observations of a few target agents. Numerical experiments validate the effectiveness of our proposed attack strategies.

## 1 Introduction

Cooperative multi-agent multi-armed bandits (CMA2B) have been widely studied in recent years [, , , ]. In CMA2B, $M\in\mathbb{N}^{+}$ agents cooperatively play multi-armed bandits with $K\in\mathbb{N}^{+}$ arms in a sequential manner.
In each decision round, each agent picks one arm and observes a reward sample drawn from a stochastic distribution associated with the pulled arm.
Their cooperative objective is to maximize their total cumulative rewards in $T\in\mathbb{N}^{+}$ decision rounds, or minimize their total regret—the difference between the total expected rewards of all agents constantly pulling the optimal arm and the actual expected rewards of the considered algorithm.

Leveraging cooperation between agents, CMA2B algorithms can achieve an improved total regret of $O(K\log T)$ [], compared with a total regret of $O(MK\log T)$ if no cooperation is used.
However, a security caveat arises when some agents occasionally get unreliable observations that may have been tampered with by malicious attackers. This concern becomes more serious in large-scale multi-agent systems, where assuring consistent reliability of every agent’s observations becomes increasingly intricate.
Given the collaborative nature of CMA2B, such adversarial attacks have the potential to not only influence the performance of their target agents, but also affect other agents in the same learning system.

Adversarial attacks on single-agent bandits have been recently studied in [, ]. In single-agent bandits, a successful attack means convincing the agent to pull a target arm a nearly linear number of times (i.e., $T-o(T)$) via manipulation of the agent’s reward observations while only incurring a sublinear attack cost (i.e., $o(T)$). In contrast, in the multi-agent settings, the definition of a successful attack may vary. It might involve misleading a single agent or all agents, and the manipulations could target one agent or span across all agents. In this paper, we consider a challenging attack objective: affecting the maximum number of agents via attacking the reward observations of only a small subset of agents.

Pursuing this objective, we discuss adversarial attacks in both homogeneous and heterogeneous CMA2B contexts. In the homogeneous settings, where each agent has access to all $K$ arms, it is feasible to convince all agents to choose a specific target arm in most time slots (if the target is a suboptimal arm, agents suffer linear regret). However, the number of agents that must be attacked and the overall cost of these attacks remain uncertain (addressed in Section [3](#S3)). Conversely, in the heterogeneous settings, where agents have different subsets of arms, the goal of directing all agents to select a single target arm becomes unattainable, especially if some agents lack access to this arm. As we elaborate in [Section 4](#S4), even the task of convincing a subset of agents to select a target arm could require linear attack costs. Consequently, we shift our attack objective towards inducing the greatest number of agents to suffer linear regret. This objective leads to three new challenges. First, determining the largest group of affected agents experiencing linear regret while incurring only sublinear costs remains an unresolved issue. Second, it is unclear how to select a small number of target agents for attack. Third, for these chosen target agents, we need to design attack strategies that can effectively influence other agents.

Our Contributions.
In this paper, we provide an in-depth study of adversarial attacks on CMA2B. In the homogeneous setting, we propose attack strategies that can convince all agents to select a designated target arm a linear number of times by attacking only a single agent with sublinear attack costs, revealing the inherent vulnerability of homogeneous CMA2B algorithms. In the heterogeneous settings, we demonstrate that the target arm attack may demand linear attack costs, and propose attack strategies that can compel a significant number of agents to experience linear regret by manipulating the observations of only a few agents with sublinear attack costs.
Our technical contributions are summarized below.

- •
In [Section 3](#S3), for the homogeneous CMA2B setting, we devise attack strategies targeting a *single* agent to effectively misguide *all* agents and prove their attack costs are $O(K\log T)$, independent of the number of agents $M$.
- •
In [Section 4.1](#S4.SS1), for the heterogeneous CMA2B setting, after illustrating several examples in which linear cost is necessary to fool the agents into suffering linear regret, we provide a criterion to determine whether two agents can be simultaneously misled with only sublinear attack costs.
- •
In [Section 4.2](#S4.SS2), we extend the above criterion to the Affected Agents Selection (AAS) algorithm that identifies the largest set of agents eligible to be affected, ensuring a $(1-1/e)-$approximation guarantee. Furthermore, we design the Target Agents Selection (TAS) algorithm to choose a small subset of agents for attack (target agents) that can influence all agents selected by AAS.
- •
Based on the AAS and TAS algorithms, we propose the Oracle Attack (OA) strategy tailored for known heterogeneous CMA2B environments, accompanied by an analysis of the associated attack costs.
In [Section 4.3](#S4.SS3), we then adapt this strategy to unknown environments via the Learning-Then-Attack (LTA) strategy and offer its cost analysis. Both strategies retain the costs of $O(K\log T)$ as those in homogeneous settings.

In addition to the algorithmic and theoretical contributions, we conduct experiments to evaluate our proposed attack strategies. Due to the space limit, proofs and empirical results are included in the appendix.

Related Work.
There is a large literature of work focused on CMA2B, e.g., [, , , , , , , , , , ] and the references therein. However, only a few works have studied misinformation in CMA2B learning, i.e.,  [, , , ].
In these scenarios, there are either malicious/selfish agents (e.g., byzantine agents []) sharing wrong information (e.g., false arm recommendation [], wrong reward observations []), or imperfect communication (e.g., adversarial corruption []), resulting in other agents failing to find the optimal arm.
Our work is the first to study how an attacker may manipulate multi-agent cooperative learning.

Regarding adversarial attacks on single-agent multi-armed bandit problems, a growing literature focuses on a variety of bandit settings, e.g.,  [, , , , , ]. Specifically, [] pioneered the formulation of adversarial attack models for stochastic bandits. [] delved into attacks on linear contextual bandits, while [] examined adversarial bandits, providing a lower bound of cumulative costs in such environments. Notably, these investigations do not extend to multi-agent bandit scenarios. To the best of our knowledge, our research marks the first exploration of adversarial attacks on CMA2B.

## 2 Preliminaries

We consider a CMA2B consisting of $K\in\mathbb{N}^{+}$ arms, denoted by an arm set $\mathcal{K}\coloneqq\{1,2,\cdots,K\}$,
and $M\in\mathbb{N}^{+}$ agents, denoted by an agent set $\mathcal{M}\coloneqq\{1,2,\cdots,M\}$.
Each arm $k\in\mathcal{K}$ is associated with a $\sigma^{2}$-sub-Gaussian reward distribution and *unknown* mean $\mu(k)\in[0,b]$ where $b\in\mathbb{R}^{+}$ is known a prior.
We assume $\mu(1)>\mu(2)>\cdots>\mu(K)$ such that the minimal mean reward gap is positive, which was also adopted in prior multi-agent bandits studies (e.g., []).
Assume there are $T\in\mathbb{N}^{+}$ decision rounds for CMA2B, denoted the round set by $\mathcal{T}\coloneqq\{1,2,\dots,T\}.$ We consider both homogeneous and heterogeneous settings for cooperative multi-agent bandits.

Homogeneous settings. In the homogeneous setting, each agent can equally observe and select every arm in $\mathcal{K}$. In round $t\in\mathcal{T}$, each agent selects an arm $k_{t}^{(m)}\in\mathcal{K}$ and observes a reward $X_{t}^{(m,0)}(k_{t}^{(m)})$ with expectation $\mu(k_{t}^{(m)})$, where the superscript ^(m,0) refers to the vanilla (pre-attack) reward observation on agent $m$. These agents share their information about arms with each other. We use regret to measure the performance of a policy, defined as

$$ $\textstyle R(T)\coloneqq MT\mu(1)-\sum_{m=1}^{M}\sum_{t=1}^{T}\mu(k_{t}^{(m)}),$ (1) $$

which is the difference between the maximized accumulative reward (all agents keep pulling optimal arm $1$) and the concerned policy’s total reward.
Note that we do not consider the collision (e.g., []) here, which means different agents can select the same arm in the same round, and each of them gets an independent reward sample. All agents together aim to minimize the regret.

Heterogeneous settings. In heterogeneous settings, each agent $m\in\mathcal{M}$ has access only to a subset of arms $\mathcal{K}^{(m)}\subset\mathcal{K}$.
Assume $\lvert\mathcal{K}^{(m)}\rvert>1$ for each agent $m\in\mathcal{M}$ to exclude trivial cases.
For each agent $m$, we denote the arm with the highest reward mean in $\mathcal{K}^{(m)}$ as $k_{*}^{(m)}=\operatorname*{arg\,max}_{k\in\mathcal{K}^{(m)}}\mu(k)$, called agent $m$’s *local optimal arm*.
Similarly to the homogeneous setting, after agent $m$ selects arm $k_{t}^{(m)}$ in round $t$, the environment also reveals a sub-Gaussian reward $X_{t}^{(m,0)}(k_{t}^{(m)})$ with expectation $\mu(k_{t}^{(m)})$. Agents share their information with others. However, due to different local optimal arms $k_{*}^{(m)}$ benchmarks, the regret is defined differently:

$$ $\textstyle R(T)=T\sum_{m=1}^{M}\mu(k_{*}^{(m)})-\sum_{m=1}^{M}\sum_{t=1}^{T}\mu(k_{t}^{(m)}).$ (2) $$

Threat model.
In both the homogeneous and heterogeneous scenarios, agent $m$ selects an arm $k_{t}^{(m)}$ from its respective arm set ($\mathcal{K}$ in homogeneous settings and $\mathcal{K}^{(m)}$ in heterogeneous settings). The environment generates sub-Gaussian pre-attack reward feedback, denoted as $X_{t}^{(m,0)}(k_{t}^{(m)})$. We assume that there exists an *attacker* who chooses a subset of agents, $\mathcal{D}\subseteq\mathcal{M}$, as the target to attack. It can observe pre-attack rewards from all agents, and manipulate those from $m\in\mathcal{D}$ into the post-attack reward $X_{t}^{(m)}(k_{t}^{(m)})$ before returning them to the agent.
It is worth noting that the agents are oblivious to the attacker’s presence and rely on this post-attack reward for subsequent decision-making. In homogeneous settings, analogous to attacks in single-agent scenarios, the attacker attempts to force *all* agents to pull a target arm for $T-o\left(T\right)$ times, incurring a cumulative attack cost of only

$$ $C(T)\coloneqq\sum_{m\in\mathcal{D}}\sum_{t=1}^{T}\left|X_{t}^{(m,0)}(k_{t}^{(m)})-X_{t}^{(m)}(k_{t}^{(m)})\right|=o(T).$ $$

In heterogeneous settings, the attacker knows the local arm set $\mathcal{K}^{(m)}$ for every agent $m\in\mathcal{M}$, and its objective is to maximize the number of agents (affected agents) that suffer linear regret, as achieving the target arm objective with sublinear costs may not be feasible in this context. The detailed reason is discussed in [Section 4](#S4).

## 3 Attacks in Homogeneous Settings

CMA2B algorithms in homogeneous settings can be broadly classified into two categories []: fully distributed algorithms and leader-follower algorithms. The distinction between these algorithms lies in the presence or absence of a central agent (or server) that determines the actions of agents. In fully distributed algorithms, all agents participate in exploration and exploitation. Conversely, in leader-follower algorithms, the leader primarily manages exploration and plays a pivotal role.
In this section, we focus on adversarial attacks against fully distributed algorithms due to the space limit. In the appendix, we also show that targeting only the leader is adequate for misleading leader-follower algorithms.

Attacks against CO-UCB.
Despite the abundance of fully distributed algorithms presented in the literature, for consistency with the heterogeneous settings in [Section 4](#S4), we choose Cooperative Upper Confidence Bound (CO-UCB) [], a representative CMA2B algorithm that functions effectively in both homogeneous and heterogeneous environments, as our attack target. In CO-UCB, in each round, each agent pulls the arm with the highest UCB index and shares its reward observation immediately with others. As we assume CO-UCB knows the range of the mean reward as a prior, it constrains all UCB indices to the interval $[0,b]$. Although our attack methodologies and analysis are crafted for CO-UCB, they can also be extended to other distributed algorithms. A detailed example of attacking UCB-TCOM [], the state-of-art homogeneous algorithm with efficient communication design, can be found in the appendix.

We first introduce some notations. Let $\hat{n}_{t}(k)$ denote the total number of times that arm $k$ is pulled by all $M$ agents globally up to time $t$, and let $\hat{\mu}_{t}(k)$ represent the *post*-attack empirical mean associated with $\hat{n}_{t}(k)$. Without loss of generality, we choose the worst arm $K$ as the target arm, as it leads to the highest attack costs. Our goal is to mislead the agents running CO-UCB in order to convince them to pull the target arm $T-o(T)$ times with $o(T)$ attack costs.
In the homogeneous setting, we can achieve this goal by merely attacking a single agent. Intuitively, since agents consistently share their reward observations, the manipulated rewards from one agent are disseminated to the rest, influencing their choices. To this end, we select an arbitrary agent, $m$, to attack. In round $t$, if its chosen arm $k$ is not the target arm $K$, we manipulate its reward $X_{t}^{(m,0)}(k)$ to fulfill the following inequality:

$$ $\displaystyle\hat{\mu}_{t}(k)\leqslant\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0},$ (3) $$

where

$$ $\begin{split}\hat{\mu}_{t}(k)=\frac{\hat{\mu}_{t-1}(k)\hat{n}_{t-1}(k)+\sum_{s=1}^{M}X_{t}^{(s,0)}(k)-\gamma^{(m)}(t)}{\hat{n}_{t}(k)},\,\beta(N)\coloneqq\sqrt{\frac{1}{2N}\log\frac{\pi^{2}KN^{2}}{3\delta}},\end{split}$ $$

and $\gamma^{(m)}(t)$ is the attack value,
$\Delta_{0}>0$ and $\delta>0$ are the parameters of the attack strategy.
This strategy is similar to the attack design against single-agent bandits []. It guarantees that the empirical means of non-target arms, after the attack, consistently remain below that of the target arm.
We define the reward mean gap of two arms as $\Delta(k,k^{\prime})\coloneqq\mu(k)-\mu(k^{\prime})$. [Theorem 1](#Thmtheorem1) provides the upper bound of the cumulative cost $C(T)=\sum_{t=1}^{T}|\gamma^{(m)}(t)|$
(note we only attack one agent $m$) for CO-UCB with confidence parameter $\alpha$.

###### Theorem 1 .

Suppose $T>K,\delta<1/2,\Delta_{0}>0$. With probability at least $1-\delta$, our attack strategy misguides *all agents*, running the CO-UCB algorithm, to choose the target arm $K$ at least $T-o(T)$ times, or formally,

$$ $\hat{n}_{T}(K)\geqslant T-\frac{\alpha(K-1)}{2\Delta_{0}^{2}}\log T,$ $$

using a cumulative cost at most

$$ $\displaystyle C(T)\leqslant\left(\frac{\alpha}{2\Delta_{0}^{2}}\log T\right)\sum_{k<K}(\Delta(k,K)+\Delta_{0})+\frac{4(K-1)\sigma}{\Delta_{0}}\sqrt{\alpha\log T\log\frac{K\pi^{2}\alpha^{2}(\log T)^{2}}{12\delta\Delta_{0}^{4}}}.$ $$

The cumulative attack cost is in the order of $O(K\log T)$, suggesting that even when attacks are limited to a single agent, no additional costs are incurred, as the corrupted observations would propagate to the whole system. Intuitively, it is equivalent to evenly spreading an $O(K/M\log T)$ cost to each agent.
Notably, the total cost is independent of the number of agents $M$, which highlights the vulnerabilities in CMA2B, as the cost does not escalate with an increase in the number of agents.

###### Theorem 1 .

## 4 Attacks in Heterogeneous Settings

In this section, we study adversarial attacks on CMA2B in heterogeneous settings, where the agent can have distinct local arm sets. We assume that all agents run the CO-UCB [] algorithm, which is a representative CMA2B algorithm for heterogeneous settings(^1^11There are other CMA2B algorithms [, ] that enjoy better regrets on the heterogeneous setting. Since all these algorithms rely on UCB, we pick CO-UCB as an example to devise the attack approach and believe it can be extended to other UCB-based heterogeneous CMA2B algorithms.).
We first discuss the viability of different attack objectives. Following that, we propose attack strategies with the appropriate objective and offer theoretical analyses of their associated costs.

### 4.1 Attack Objectives

Figure: (a) Target arm attack
Refer to caption: /html/2311.01698/assets/Figure/obj_1.png

While the majority of heterogeneous CMA2B algorithms are derivatives of their homogeneous counterparts, the distinctiveness introduced by agent heterogeneity poses novel challenges in devising adversarial attacks. We first consider the original target arm attack as in the homogeneous settings, which aims to deceive all agents into selecting a target arm $T-o(T)$ times. Intriguingly, in heterogeneous settings, achieving this objective might require linear attack costs. A simple example of two agents is shown in [Figure 1(a)](#S4.F1.sf1). We consider the target arm to be arm $3$ in agent $1$, and intuitively, once arm $1$ or $2$ is pulled, the attacker needs to decrease their rewards. However, given this heterogeneous setup, agent $2$ only has access to arms $1$ and $2$. Therefore, it is compelled to select them repeatedly, and their reward samples are subsequently sent to agent $1$. As a result, to deceive agent $1$ into frequently selecting arm $3$, linear attack costs on agent $2$ become necessary.
[Proposition 1](#Thmproposition1) formally shows the necessity of linear costs to realize the target arm attack.

###### Proposition 1 .

For any attack strategy that can successfully mislead the agents running CO-UCB in [Figure 1(a)](#S4.F1.sf1) to pull the target arm $T-o(T)$ times, its attack cost is at least $C(T)\geqslant cT$ for some constant $c>0$.

Thus, the target arm attack may not be an appropriate attack objective in heterogeneous environments. Shifting our focus, we consider an alternative attack objective: misleading all agents toward linear regrets. While this objective seems less stringent, as it merely mandates agents not to choose their local optimal arms, the intrinsic heterogeneity of available arms brings forth complexities. Notably, there might be agents that, given the disparity in arm sets, cannot be simultaneously misguided towards linear regrets with only sublinear costs. Such agents are termed as *“conflict”* agents. An example of this scenario is depicted in [Figure 1(b)](#S4.F1.sf2).
Our objective is to deceive agents $1$ and $2$, preventing them from selecting their locally optimal arms, and thereby incurring linear regrets. Notably, while arm $2$ is suboptimal for agent $1$, it is optimal for agent $2$. After the attacks, agent $1$ should pull arm $2$ linear times, and those rewards will be communicated to agent $2$ to affect its arm selection. Consequently, ensuring agent $2$ chooses its suboptimal arm $3$ almost linear times incurs linear attack costs.
In [Proposition 2](#Thmproposition2), we further demonstrate that linear costs are inevitable when pursuing this attack objective.

###### Proposition 2 .

For any attack strategy that can successfully mislead all agents running CO-UCB in [Figure 1(b)](#S4.F1.sf2) to suffer linear regrets, its attack cost is at least $C(T)\geqslant cT$ for some constant $c>0$.

Although sublinear attack costs might not be sufficient in leading all agents to experience linear regrets, they can still influence a subset of the agents. This realization prompts the final attack objective explored in this section: leveraging sublinear attack costs to misguide the maximum number of agents, aiming to increase the overall count of agents enduring linear regrets. To realize this goal, it is necessary to identify the largest set of agents that do not have conflicts. The condition under which two agents are deemed to be in conflict is given in [Condition 1](#Thmcondition1).

###### Condition 1 (Agents conflict) .

For any two agents $m,m^{\prime}\in\mathcal{M}$, if $|\mathcal{K}^{(m)}\setminus\{k^{(m)}_{*},k^{(m^{\prime})}_{*}\}|=0$ or $|\mathcal{K}^{(m^{\prime})}\setminus\{k^{(m)}_{*},k^{(m^{\prime})}_{*}\}|=0$, we say agent $m$ conflicts with agent $m^{\prime}$, i.e., they cannot be simultaneously attacked with sublinear costs.

Given this condition, we introduce a greedy algorithm designed to identify the largest group of affected agents without conflicts. Furthermore, we devise attack strategies tailored for both known ([Section 4.2](#S4.SS2)) and unknown ([Section 4.3](#S4.SS3)) environments.

###### Proposition 1 .

###### Proposition 2 .

###### Condition 1 (Agents conflict) .

### 4.2 Oracle Attack Strategy

We study a scenario in which the attack algorithm has prior knowledge of the environment. Specifically, the attacker knows the reward ranking of all arms. This premise is less stringent than the “oracle attack” assumption from previous studies [, ], which requires precise knowledge of the mean rewards for every arm. Note that
while we similarly label our approach as an “oracle attack” and use the $\mu(k)$ notation in our algorithms, they only rely on the relative arm ranking but not the exact means.

Affected Agents Selection.
As previously mentioned, the first step for the attacker is to identify the largest group of agents without conflicts as the attack objective. Although [Condition 1](#Thmcondition1) allows us to check the conflict status between any pair of agents, finding the maximal conflict-free agent group poses a non-trivial combinatorial optimization challenge.
To solve this problem, we propose the Affected Agents Construction (AAS) algorithm, described in [Algorithm 1](#alg1).
Initially, the algorithm categorizes all agents into separate sets based on their local optimal arms, i.e., agent set $\mathcal{M}_{*}(k)\coloneqq\{m\in\mathcal{M}:k_{*}^{(m)}=k\}$ contains all agents whose local optimal arm is arm $k$, and sort them by set size $M_{*}(k)\coloneqq\lvert\mathcal{M}_{*}(k)\rvert$. Following this, a greedy set selection process is employed. The group of selected agents is maintained by $\mathcal{D}_{0}$. The algorithm examines sets from $M_{*}(\omega(1))$ to $M_{*}(\omega(k))$ sequentially, where $M_{*}(\omega(i))$ is the size of the $i^{\text{th}}$ largest
agent sets among $\{\mathcal{M}_{*}(1),\dots,\mathcal{M}_{*}(K)\}$. If all agents within $\mathcal{M}_{*}(\omega(k))$ do not conflict with the current group $\mathcal{D}_{0}$, which is checked by [Eq. 4](#S4.E4), they are incorporated into $\mathcal{D}_{0}$, and the subsequent set $\mathcal{M}_{*}(\omega(k+1))$ will be examined. It eventually outputs the target group $\mathcal{D}_{0}$ and the local optimal arms’ set $\mathcal{K}_{0}$ of agents in the group.
The following theorem provides the theoretical guarantee of [Algorithm 1](#alg1).

###### Theorem 2 .

[Algorithm 1](#alg1) finds a $(1-1/e)$-approximate solution, i.e., the cardinality of the output group $|\mathcal{D}_{0}|\geqslant(1-1/e)D_{\max}$, where $D_{\max}$ is the size of the largest conflict-free agent group.

We prove this approximation ratio using the property of submodular functions in the appendix.

Figure: Algorithm 1 AAS: Affected Agents Selection

Target Agents Selection.
With output agent group $\mathcal{D}_{0}$ as the attack objective, a natural question arises: is it feasible to attack this group using only a limited number of agents, similar to the scenario in homogeneous settings? To address this, we introduce the Target Agents Selection (TAS) algorithm, which refines the selection of target agents to attack within $\mathcal{D}_{0}$.
As described in [Algorithm 2](#alg2), for each agent $m\in\mathcal{D}_{0}$, it finds $k_{0}^{(m)}$, its local arm with the highest mean reward excluding all arms in $\mathcal{K}_{0}$ (Lines [4](#alg2.l4)-[5](#alg2.l5)). Then, for each arm $k\in\mathcal{K}_{0}$, it checks $\mathcal{D}_{0,*}(k)$, which contains all agents in $\mathcal{D}_{0}$ with local optimal arm $k$, i.e., $\mathcal{D}_{0,*}(k)=\{m\in\mathcal{D}_{0}:k_{*}^{(m)}=k\}$; it chooses the agent in $\mathcal{D}_{0,*}(k)$ with the lowest $\mu(k_{0}^{(m)})$ and include it into the target agent set $\mathcal{G}_{0}$. Intuitively, in order to attack each arm $k\in\mathcal{K}_{0}$, [Algorithm 2](#alg2) selects the agent in $\mathcal{D}_{0}$ that is most likely to pull arm $k$ very often, since its alternative action $k_{0}^{(m)}$ closest to $k$ has the least attractive mean reward. Such target agent selection will help us control the number of times that $k\in\mathcal{K}_{0}$ is pulled by agents outside $\mathcal{G}_{0}$, ensuring successful attacks.

Figure: Algorithm 2 TAS: Target Agents Selection

Attack Strategy and Analysis.

Figure: Algorithm 3 Oracle Attack

We present the Oracle Attack (OA) algorithm as detailed in [Algorithm 3](#alg3). Initially, it invokes both AAS and TAS to select the target agent set $\mathcal{G}_{0}$ responsible for executing the attacks. Subsequently, whenever an agent $m\in\mathcal{G}_{0}$ chooses an arm $k\in\mathcal{K}_{0}$, it attacks $k$ with attack value $\gamma_{t}^{(m)}(k)$ to satisfy the ensuing inequality:

$$ $\hat{\mu}_{t}(k)\leq\min_{k^{\prime}\in\mathcal{K}\backslash\mathcal{K}_{0}}\{\hat{\mu}_{t-1}(k^{\prime})-2\beta(\hat{n}_{t-1}(k^{\prime}))-\Delta_{0}\},$ (5) $$

where $\hat{\mu}_{t}(k)=\frac{\hat{\mu}_{t-1}(k)\hat{n}_{t-1}(k)+\sum_{m^{\prime}=1}^{M}X_{t}^{(m^{\prime},0)}(k)-\gamma_{t}^{(m)}(k)}{\hat{n}_{t}(k)}$.
We define $\Delta_{\min}=\min_{k}\Delta(k,k+1)$ and provide the attack cost analysis for [Algorithm 3](#alg3).

###### Theorem 3 .

Suppose $T>T_{0},\alpha>2$, where $T_{0}$ is a time-independent constant fulfills Eq. ([6](#S4.E6)). With probability at least $1-\delta$, [Algorithm 3](#alg3) misguides the agents to suffer regret at least

$$ $\displaystyle R(T)\geqslant\Delta_{\min}\sum_{k\in\mathcal{K}_{0}}\left({M}_{*}(k)T-\frac{2\alpha\log T}{\Delta_{0}^{2}}\right),$ $$

using the cumulative cost at most

$$ $\displaystyle\textstyle C(T)\leqslant\sum_{k\in\mathcal{K}_{0}}\left(\frac{\alpha\log T}{2\Delta_{0}^{2}}(\Delta(k,K)+\Delta_{0})\right.+T_{0}\left.~{}+\frac{4\sigma}{\Delta_{0}}\sqrt{\alpha\log T\log\frac{K\pi^{2}\alpha^{2}(\log T)^{2}}{12\delta\Delta_{0}^{4}}}\right).$ $$

$T_{0}$ is a feasible solution of the following equation

$$ $\frac{t}{\log t}\geqslant\max_{k\in\mathcal{K}_{0}}c_{k},$ (6) $$

where $c_{k}=c_{k,1}+c_{k,2}+c_{k,3}$ and

$$ $\displaystyle c_{k,1}$ $\displaystyle=\sum_{k^{\prime}\in\mathcal{K}_{0}^{(g(k))}\setminus\{k_{0}^{(g(k))}\}}\frac{\alpha}{2\Delta^{2}(k_{0}^{(g(k))},k^{\prime})},$ $\displaystyle c_{k,2}$ $\displaystyle=\frac{\alpha}{2\min_{m\in\mathcal{D}_{0,*}(k):k_{0}^{(m)}\neq k_{0}^{(g(k))}}\Delta^{2}(k_{0}^{(m)},k_{0}^{(g(k))})},$ $\displaystyle c_{k,3}$ $\displaystyle=|\mathcal{K}^{(g(k))}\cap\mathcal{K}_{0}|\cdot\frac{\alpha}{\Delta_{0}^{2}}.$ $$

The attack cost follows the order of $O(|\mathcal{K}_{0}|\log T)$ and is independent of the number of affected agents, $|\mathcal{D}_{0}|$. This implies that a small attack cost can have a substantial impact on numerous agents in heterogeneous settings. Notice that directly comparing this result with [Theorem 1](#Thmtheorem1) would be unfair, given the distinct objectives and settings they address. As the proof of this theorem is one of our main technical contributions, we briefly discuss its key idea below.

Proof Challenge and Key Idea.
The main challenge in this proof arises from our choice of target agents. These agents can lower the post-attack empirical means of arms in $\mathcal{K}_{0}$ only when they pull these arms. However, non-target agents may also pull these arms, yielding non-attacked samples that increase the empirical means towards the true means. This issue is especially prominent in heterogeneous settings where target and non-target agents, due to their distinct arm sets, might choose different arms to pull.
Conversely, in homogeneous settings,
all agents have access to all arms, consistently offering opportunities for attacks. To address this, we use TAS to choose up to $|\mathcal{K}_{0}|$ agents from $\mathcal{D}_{0}$. These target agents are the most likely ones to frequently pull arms in $\mathcal{K}_{0}$ because their top arms (after excluding those in $\mathcal{K}_{0}$), denoted as $k_{0}^{(m)}$, possess the least attractive mean rewards.

Formally, we prove that for any $t>T_{0},k\in\mathcal{K}_{0}$, our target agents in $\mathcal{G}_{0}$ will prioritize pulling arm $k$ before non-target agents, assuring enough attack opportunities. The value of $T_{0}$ is calculated by [Eq. 6](#S4.E6). To elucidate, for each arm $k\in\mathcal{K}_{0}$, target agent $g(k)$ is mainly responsible for attacking it. If $g(k)$’s best arm excluding those in $\mathcal{K}_{0}$, $k_{0}^{(g(k))}$, has been sufficiently pulled, i.e., $\hat{n}_{t}(k_{0}^{(g(k))})\geqslant c_{k,2}\log t$, it will consistently be the first to pull arm $k$ in $\mathcal{D}_{0,*}(k)$. We then bound the number of times that $g(k)$ does not pull $k_{0}^{(g(k))}$: it can pull local arms worse than $k_{0}^{(g(k))}$ at most $c_{k,1}\log t$ times, and local arms within $\mathcal{K}_{0}$ up to $c_{k,3}\log t$ times. Hence, $\hat{n}_{t}(k_{0}^{(g(k))})\geqslant t-c_{k,1}\log t-c_{k,3}\log t$, and we want $t-c_{k,1}\log t-c_{k,3}\log t\geqslant c_{k,2}\log t$. We need to ensure this equation for every $k$, leading to [Eq. 6](#S4.E6). Since the right-hand side of [Eq. 6](#S4.E6) is a problem-dependent coefficient, we can derive $T_{0}$ which is independent of $t$. For subsequent rounds $t>T_{0}$, it is easy to prove the successful attacks with bounded attack costs.

###### Theorem 2 .

###### Theorem 3 .

### 4.3 LTA: Learning-Then-Attack Strategy

In this section, we further relax the oracle assumption that the reward ranking of all arms is unknown. This creates a significant challenge as [Algorithm 1](#alg1) and [Algorithm 2](#alg2) need knowledge of the arm ranking to determine the largest set of affected agents and select target agents to attack. To address this issue and adapt the attack design from [Algorithm 3](#alg3) to this scenario, we introduce the Learning-Then-Attack (LTA) algorithm, detailed in [Algorithm 4](#alg4). LTA operates in two phases: an initial learning stage, where it discerns reward means and arm rankings, followed by an attack phase akin to [Algorithm 3](#alg3).

Figure: Algorithm 4 LTA: Learning-Then-Attack

Attacker’s Learning Stage.
We now delve into the rank learning stage.
This ranking is pivotal for executing AAS ([Algorithm 1](#alg1)) and TAS ([Algorithm 2](#alg2)), as they necessitate the knowledge of each agent’s local optimal arms to optimize the affected agent group and minimize the target agent subset.
To acquire this ranking, the attacker needs to compel agents to pull each arm multiple times. This ensures a sufficient number of pre-attack samples, allowing for a clear distinction between the Lower Confidence Bounds (LCBs) and Upper Confidence Bounds (UCBs) for every arm pair.

We initialize the UCB of each arm with a relatively high value. Given that agents choose arms based on UCB algorithms, the attacker needs to stimulate agents to collect ample samples for suboptimal arms by increasing their UCB values through attacks.
More specifically, if the attacker wants to accumulate samples of arm $k$, it needs to attack the arm’s reward such that the subsequent condition is met (Line [7](#alg4.l7)),

$$ $\text{UCB}_{t}(k)>\text{UCB}_{t}(k^{\prime}),\,\forall k\neq k^{\prime}.$ (7) $$

Once the number of times of pulling the arm $k$ reaches a threshold $L\coloneqq\left\lceil\frac{2\log(2K/\delta)}{\Delta^{2}_{\min}}\right\rceil$ (Line [8](#alg4.l8)), the attacker resets the arm’s empirical mean (remove the prior attacks on the arm) (Line [9](#alg4.l9)). This ensures that arms that have not been sufficiently sampled in the past will be selected later.

Reduce Number of Target Agents

###### Condition 2 (Arm accessibility) .

For each arm $k\in\mathcal{K}$, there are at least $cM\in\mathbb{N}^{+}$ agents in the target agent set $\mathcal{S}_{0}\subseteq\mathcal{M}$ being able to access it, where $c>0$ is the arm accessible rate among target agents.
Formally, the condition is

$$ $\left|\{m\in\mathcal{S}_{0}:k\in\mathcal{K}^{(m)}\}\right|\geqslant cM,\quad\forall k\in\mathcal{K}.$ $$

We note that this target agent set $\mathcal{S}_{0}$ for learning the arm ranking can be different from $\mathcal{G}_{0}$ chosen in [Algorithm 2](#alg2),
and this condition is not restrictive. For example, letting $\mathcal{S}_{0}$ be a subset of agents whose local optimal arms together cover the full arm set $\mathcal{S}$, choosing $c=\frac{1}{M}$
is always a valid choice.

Condition [2](#Thmcondition2) ensures that during each round of the learning stage, there are a minimum of $cM$ *effective* observations. Here, “effective observations” denote the observations of arms with sample sizes below the threshold $L$. During this stage, agents are motivated to select arms (provided they are in their local arm sets) with observations fewer than $L$. Whenever there is an arm that hasn’t reached this threshold, a minimum of $cM$ agents will be motivated to select it, especially when multiple arms are under-observed. Consequently, the learning stage ends after no more than $\frac{KL}{cM}$ rounds.

Analysis.
Upon completing the learning stage, the attacker has accurate estimates of the reward means for all arms to determine the arm ranking.
It can then apply the oracle attack in [Algorithm 3](#alg3).
Notice that in the initial phase of the second stage, when the first time that any arm in $\mathcal{K}_{0}$ is pulled by a target agent in $\mathcal{G}_{0}$, the attacker incurs a significant attack cost. This is because the attacker must pay additional costs to alter the unbiased empirical means derived from the learning stage. However, such extra costs can be upper bounded by $\frac{KL(\Delta(1,K)+\beta(1)+b)}{c}$, where $b$ is the upper bound of the mean rewards.
Subsequent to this initial adjustment, the OA algorithm operates identically to its behavior in the oracle setting.

###### Theorem 4 .

Suppose $T>T_{0},\alpha>2,\delta<0.5$, where $T_{0}$ is a time-independent constant fulfills Eq. ([6](#S4.E6)). With probability at least $1-2\delta$, [Algorithm 4](#alg4) misguides the agents to suffer regret at least

$$ $\displaystyle R(T)\geqslant\Delta_{\min}\sum_{k\in\mathcal{K}_{0}}\left({M}_{*}(k)T-\frac{2\alpha\log T}{\Delta_{0}^{2}}\right),$ $$

using the cumulative cost at most

$$ $\displaystyle C(T)$ $\displaystyle\leqslant\frac{4K\log T}{c\Delta_{\min}^{2}}(\Delta(1,K)+\beta(1)+b)+\sum_{k\in\mathcal{K}_{0}}\left(\frac{\alpha\log T}{2\Delta_{0}^{2}}(\Delta(k,K)+\Delta_{0})\right.+T_{0}$ $\displaystyle\left.~{}+\frac{4\sigma}{\Delta_{0}}\sqrt{\alpha\log T\log\frac{K\pi^{2}\alpha^{2}(\log T)^{2}}{12\delta\Delta_{0}^{4}}}\right).$ $$

Compared with the result of the oracle attack, the first term in the attack cost arises from the attacks during the rank learning stage, while the second term is the same as that in [Theorem 3](#Thmtheorem3). If there exists a constant $c$ such that [Condition 2](#Thmcondition2) holds, the first term will still be in the order of $O(K\log T)$ and matches the cost caused by the oracle attack.

###### Condition 2 (Arm accessibility) .

###### Theorem 4 .

## 5 Experiments

Figure: (a) Average Regrets
Refer to caption: /html/2311.01698/assets/Figure/Regret.png

We conduct experiments in both homogeneous and heterogeneous settings. Due to space limitations, we only present the results of heterogeneous settings here. We take $T=100,000,K=20,M=20$. The mean rewards of the arms are randomly sampled within $\left(0,5\right)$ while ensuring $\Delta_{\min}^{2}\geqslant 0.01$, and the reward of each arm $k$ follows the Gaussian distribution $\mathcal{N}\left(\mu\left(k\right),\sigma\right)$ with $\sigma=0.1$. Furthermore, each agent $m$ has a set of arms with $|\mathcal{K}^{(m)}|=5$. The CO-UCB algorithm takes $\alpha=10$, and the attack parameters are set to $\Delta_{0}=0.05$ and $\delta=0.1$. We conducted experiments with five algorithms for comparison: Oracle Attack (OA) with and without Affected Agents Selection (AAS), Leaning-Then-Attack (LTA) with and without AAS, and No Attack. Each experiment was repeated $10$ times.

[Figure 2(a)](#S5.F2.sf1) shows the average regret across various algorithms. Both LTA and OA result in the most significant average regrets, primarily due to AAS’s capability to identify the most extensive group of affected agents. Without AAS, their average regrets converge to reduced constant values, indicating linear regrets for a limited subset of affected agents.
Figure [2(b)](#S5.F2.sf2) shows the average attack costs of different algorithms. All of them approach zero, indicating sublinear cumulative attack costs. In particular, LTA initially incurs higher costs compared to OA, a consequence of the high attack costs during their learning stage.

## 6 Concluding Remarks

This paper pioneers the study of adversarial attacks on CMA2B. We introduce attack strategies that can effectively mislead CMA2B algorithms in both homogeneous and heterogeneous settings. One limitation of our work is that there is no known lower bound of the attack cost even for the single-agent bandit setting in the literature, so it is unclear whether our attack strategies are order-optimal. This work also opens up multiple future directions, including the development of attack strategies tailored for competitive multi-agent bandits featuring collisions. Furthermore, our insights into the vulnerabilities of current CMA2B algorithms set the stage for crafting algorithms resistant to adversarial attacks.

## Appendix

## Appendix A Proofs

### A.1 Proof of Theorem 1

###### Proof.

We first define the “good event” $E=\{\forall k,\forall t>K:|\hat{\mu}_{t}^{(0)}(k)-\mu(k)|<\beta(\hat{n}_{t}(k))\}$, where $\hat{\mu}_{t}^{0}(k)$ is the pre-attack empirical mean of arm $k$ for all agents up to time slot $t$. By Hoeffding’s inequality, we can prove that for any $\delta\in(0,1)$, $P(E)>1-\delta$. To prove [Theorem 1](#Thmtheorem1), we introduce two lemmas.

###### Lemma 1 .

Assume event $E$ holds and $\delta\leqslant 1/2$. For any $k\neq K$ and any $t\geqslant K$, we have

$$ $\hat{n}_{t}(k)\leqslant\min\{\hat{n}_{t}(K),\frac{\alpha\log t}{2\Delta_{0}^{2}}\}$ (8) $$

###### Proof.

Fix some $t>K$, we assume that $k_{t}^{(m)}=k\neq K$. Note that when $k_{t}^{(m)}\neq k$, $\hat{n}_{t}(k)$ will never increase. Also, we assume the last time arm $k$ is selected before time slot $t$ is $t^{\prime}$. By our attack design in [Eq. 3](#S3.E3) , we have:

$$ $\hat{\mu}_{t^{\prime}}(k)\leqslant\hat{\mu}_{t^{\prime}}(K)-2\beta(\hat{n}_{t^{\prime}}(K))-\Delta_{0}.$ (9) $$

On the other hand, arm $k$ is selected in round $t$ means that it has a higher UCB than arm $K$ in round $t-1$:

$$ $\hat{\mu}_{t-1}(k)+\sqrt{\frac{\alpha\log(t-1))}{2\hat{n}_{t-1}(k)}}\geqslant\hat{\mu}_{t-1}(K)+\sqrt{\frac{\alpha\log(t-1)}{2\hat{n}_{t-1}(K)}}.$ (10) $$

Note that $\hat{\mu}_{t^{\prime}}(k)=\hat{\mu}_{t-1}(k)$. Substituting [Eq. 9](#A1.E9) into [Eq. 10](#A1.E10), we have:

$$ $\displaystyle\sqrt{\frac{\alpha\log(t-1))}{2\hat{n}_{t-1}(k)}}-\sqrt{\frac{\alpha\log(t-1)}{2\hat{n}_{t-1}(K)}}$ $\displaystyle\geqslant\hat{\mu}_{t-1}(K)-\hat{\mu}_{t-1}(k)$ (11) $\displaystyle\geqslant\hat{\mu}_{t-1}(K)-(\hat{\mu}_{t^{\prime}}(K)-2\beta(\hat{n}_{t^{\prime}}(K))-\Delta_{0})$ $\displaystyle\geqslant\Delta_{0}$ $\displaystyle>0,$ $$

where the third inequality is due to event $E$ and the monotonically decreasing property of $\beta$. Therefore, by [Eq. 11](#A1.E11) and $\sqrt{\frac{\alpha\log(t-1)}{2\hat{n}_{t-1}(K)}}>0$, the proof is done.
∎

###### Lemma 2 .

Assume event $E$ holds and $\delta\leqslant 1/2$. Denote $\tau(t,k)$ as the rounds in which arm $k$ is selected by all agents up to round $t$. For any $i\neq K$ and any $t\geqslant K$, we have

$$ $\sum_{s\in\tau(t,k)}\gamma^{(m)}(s)\leqslant\hat{n}_{t}(k)(\Delta(k,K)+\Delta_{0}+3\beta(\hat{n}_{t}(K))+\beta(\hat{n}_{t}(k)))$ (12) $$

###### Proof.

We assume that $k_{t}^{(m)}=k\neq K$ for some fixed $t>K$. By [Eq. 3](#S3.E3), we can compute the attack value in each round $t$:

$$ $\displaystyle\gamma^{(m)}(t)$ $\displaystyle=\left(\hat{\mu}_{t-1}(k)\hat{n}_{t-1}(k)+\sum_{m^{\prime}=1}^{M}X_{t}^{(m^{\prime},0)}(k)-\hat{n}_{t}(k)(\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0})\right)_{+}$ (13) $\displaystyle=\left(\hat{\mu}_{t-1}^{(0)}(k)\hat{n}_{t-1}(k)+\sum_{m^{\prime}=1}^{M}X_{t}^{(m^{\prime},0)}(k)-\sum_{s\in\tau(t-1,k)}\gamma^{(m)}(s)-\hat{n}_{t}(k)(\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0})\right)_{+}.$ $$

If $\gamma^{(m)}(t)=0$, we change to examine the last time it was greater than zero. We have

$$ $\displaystyle\sum_{s\in\tau(t,k)}\gamma^{(m)}(s)$ $\displaystyle=\hat{\mu}_{t-1}^{(0)}(k)\hat{n}_{t-1}(k)+\sum_{m^{\prime}=1}^{M}X_{t}^{(m^{\prime},0)}(k)-\hat{n}_{t}(k)(\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0})$ (14) $\displaystyle=\hat{n}_{t}(k)(\hat{\mu}_{t}^{(0)}(k)+\hat{\mu}_{t}(K)+2\beta(\hat{n}_{t}(K))+\Delta_{0})$ $\displaystyle\leqslant\hat{n}_{t}(k)(\Delta(k,K)+\Delta_{0}+3\beta(\hat{n}_{t}(K))+\beta(\hat{n}_{t}(k))),$ $$

where the last inequality is due to event $E$.
∎

With [Lemma 1](#Thmlemma1), we can easily get that the target arm $K$ is selected for at least $MT-(K-1)(\frac{\alpha}{2\Delta_{0}^{2}}\log T)$ times. As for the cumulative cost, we sum over all non-target arms using [Lemma 2](#Thmlemma2). We have:

$$ $\displaystyle\sum_{t}^{T}\gamma^{(m)}(t)$ $\displaystyle\leqslant\sum_{k=1}^{K-1}\hat{n}_{t}(k)(\Delta(k,K)+\Delta_{0})+4\sum_{k=1}^{K-1}\hat{n}_{t}(k)\beta(\hat{n}_{t}(k))$ (15) $\displaystyle\leqslant\left(\frac{\alpha}{2\Delta_{0}^{2}}\log T\right)\sum_{k<K}(\Delta(k,K)+\Delta_{0})+\frac{4(K-1)\sigma}{\Delta_{0}}\sqrt{\log T\log\frac{K\pi^{2}\alpha^{2}(\log T)^{2}}{12\delta\Delta_{0}^{4}}},$ $$

where in the last inequality, we substitute the chosen times of each arm $k$, $\hat{n}_{t}(k)$, into $\beta$.
∎

###### Proof.

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

### A.2 Proof of Proposition 1

The proofs of [Proposition 1](#Thmproposition1) and [Proposition 2](#Thmproposition2) are inspired by the proof of Theorem 2 in [].

###### Proof.

Assume arm $3$ is our target arm. We first introduce some notations. Let $\gamma(t,m,k)=X_{t}^{(m,0)}(k)-X_{t}^{(m)}(k)$. Note that if $k_{t}^{(m)}\neq k$, then $\gamma(t,m,k)=0$. In addition, let $\Gamma(t,k)=\sum_{s=1}^{t}\sum_{m=1}^{2}|\gamma(s,m,k)|$.

Assume event $E$ holds. Consider the last time that arm $3$ is pulled (by agent $1$) is round $t+1$. As the agent selects the arm with the highest UCB in time slot $t$, we have:

$$ $\displaystyle\hat{\mu}_{t}(3)+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(3)}}\geqslant\hat{\mu}_{t}(k)+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(k)}},$ (16) $$

for $k=1,2$. Also, we have the following two inequalities:

$$ $\displaystyle\frac{\hat{\mu}_{t}(3)\hat{n}_{t}(3)-\Gamma(t,3)}{\hat{n}_{t}(3)}\leqslant\mu(3)+\beta(\hat{n}_{t}(3)),$ (17) $$

$$ $\displaystyle\frac{\hat{\mu}_{t}(k)\hat{n}_{t}(k)+\Gamma(t,k)}{\hat{n}_{t}(k)}\geqslant\mu(k)-\beta(\hat{n}_{t}(k)),$ (18) $$

for $k=1,2$. This is because we consider the absolute values of both positive and negative instances of $\gamma$ up to round $t$ and also utilize event $E$ to upper and lower bound the empirical means. Note that arm $3$ can only be selected by agent $1$. Therefore, we have $\hat{n}_{t}(3)\leqslant t$, and $\max\{\hat{n}_{t}(1),\hat{n}_{t}(2)\}\geqslant t/2$. Let $i=\operatorname*{arg\,max}_{k=1,2}\{\hat{n}_{t}(k)\}$. Then, we can construct an instance that needs linear cumulative cost to pull the target arm for linear times.

Suppose $\Delta(2,3)\geqslant 4,\sigma=0.5$. As $\hat{n}_{T}(3)=T-o(T)$, we can assume that there exists some constant $\frac{\sqrt{\delta}}{\pi}<c<1$, which satisfies $\min\{\hat{n}_{t}(i),\hat{n}_{t}(3)\}\geqslant ct$. Putting [Eqs. 16](#A1.E16), [17](#A1.E17) and [18](#A1.E18) together, we have:

$$ $\displaystyle\frac{\Gamma(t,3)}{\hat{n}_{t}(3)}+\frac{\Gamma(t,i)}{\hat{n}_{t}(i)}$ $\displaystyle\geqslant\Delta(i,3)-\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(3)}}-\beta(\hat{n}_{t}(3))-\beta(\hat{n}_{t}(i))$ (19) $\displaystyle\geqslant\Delta(2,3)-3\beta(ct)$ $\displaystyle>\Delta(2,3)-3\sqrt{\frac{\delta}{\pi t}\log\frac{\pi t}{\delta}}$ $\displaystyle>1,$ $$

where the second inequality holds because $\Delta(i,3)\geqslant\Delta(2,3)$, and we have $\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(3)}}\leqslant\beta(\min\{\hat{n}_{t}(i),\hat{n}_{t}(3)\})\leqslant\beta(ct)$ when $\frac{\sqrt{\delta}}{\pi}<c<1$, as $\beta$ is monotonically decreasing. The third inequality can be derived from the following result:

$$ $\displaystyle\beta(ct)$ $\displaystyle=\sqrt{\frac{1}{2ct}\log\frac{\pi^{2}c^{2}t^{2}}{\delta}}$ $\displaystyle\overset{c<1<\frac{1}{\sqrt{\delta}}}{\leqslant}\sqrt{\frac{1}{2ct}\log(\frac{\pi t}{\delta})^{2}}$ $\displaystyle\overset{c>\frac{\sqrt{\delta}}{\pi}>\frac{\delta}{\pi}}{\leqslant}\sqrt{\frac{\delta}{\pi t}\log\frac{\pi t}{\delta}},$ $$

and the last inequality in [Eq. 19](#A1.E19) is due to $\sqrt{\frac{\log x}{x}}<1$ for any $x\geqslant 1$. Therefore, the cumulative cost is

$$ $\displaystyle C(T)\geqslant\Gamma(T,3)+\Gamma(T,i)\geqslant cT.$ (20) $$

∎

###### Proof.

### A.3 Proof of Proposition 2

###### Proof.

We use the same notations in [Section A.2](#A1.SS2) and assume event $E$ holds. In this scenario, we assume that both arms $2$ and $3$ should be selected for linear times; otherwise, one of these agents will not suffer linear regret.

Consider the last time arm $3$ is pulled (by agent $2$) is $t+1$. Then we have the UCB order in time slot $t$:

$$ $\displaystyle\hat{\mu}_{t}(3)+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(3)}}\geqslant\hat{\mu}_{t}(2)+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(2)}}.$ (21) $$

Also, we have the following two inequalities for the same reason of [Eqs. 17](#A1.E17) and [18](#A1.E18):

$$ $\displaystyle\frac{\hat{\mu}_{t}(3)\hat{n}_{t}(3)-\Gamma(t,3)}{\hat{n}_{t}(3)}\leqslant\mu(3)+\beta(\hat{n}_{t}(3)),$ (22) $$

$$ $\displaystyle\frac{\hat{\mu}_{t}(2)\hat{n}_{t}(2)+\Gamma(t,2)}{\hat{n}_{t}(2)}\geqslant\mu(2)-\beta(\hat{n}_{t}(2)).$ (23) $$

Suppose $\Delta(2,3)\geqslant 4,\sigma=0.5$. As $\hat{n}_{T}(k)=T-o(T),k=2,3$, we can assume that there exists some constant $\frac{\sqrt{\delta}}{\pi}<c<1$, which satisfies $\min\{\hat{n}_{t}(2),\hat{n}_{t}(3)\}\geqslant ct$. Put [Eqs. 21](#A1.E21), [22](#A1.E22) and [23](#A1.E23) together, we have:

$$ $\displaystyle\frac{\Gamma(t,3)}{\hat{n}_{t}(3)}+\frac{\Gamma(t,2)}{\hat{n}_{t}(2)}$ $\displaystyle\geqslant\Delta(2,3)-\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(3)}}-\beta(\hat{n}_{t}(3))-\beta(\hat{n}_{t}(2))$ (24) $\displaystyle\geqslant\Delta(2,3)-3\beta(ct)$ $\displaystyle>\Delta(2,3)-3\sqrt{\frac{\delta}{\pi t}\log\frac{\pi t}{\delta}}$ $\displaystyle>1,$ $$

with the reason similar to that for [Eq. 19](#A1.E19). Therefore, the cumulative cost is

$$ $\displaystyle C(T)\geqslant\Gamma(T,3)+\Gamma(T,2)\geqslant cT.$ (25) $$

∎

###### Proof.

### A.4 Proof of Theorem 2

###### Proof.

We define a set function $f:2^{\Omega}\mapsto\mathbb{R}$, which takes the power set of $\Omega:=\{\mathcal{M}_{*}(1),\cdots,\mathcal{M}_{*}(K)\}$ as input and outputs the largest number of conflict-free agents. We then check its submodularity. For every $X,Y\subseteq\Omega$ with $X\subseteq Y$ and every $x\in\Omega\setminus Y$, we have

$$ $f(X\cup\{x\})-f(X)\geqslant f(Y\cup\{x\})-f(Y),$ (26) $$

since if agent $m\in x$ conflicts with any agent $m^{\prime}\in X$, it must conflict with $m^{\prime}\in Y$ as well. As a result, $f$ is submodular and the greedy algorithm in [Algorithm 1](#alg1) gives a $(1-1/e)$-approximate solution.

∎

###### Proof.

### A.5 Proof of Theorem 3

###### Proof.

For each arm $k\in\mathcal{K}_{0}$, we consider the target agent $g(k)$, which is mainly responsible for attacking $k$. We first prove that if $k_{0}^{(g(k))}$ has been sufficiently pulled, i.e., $\hat{n}_{t}(k_{0}^{(g(k))})\geqslant c_{k,2}\log t$, $g(k)$ will consistently be the first to pull arm $k$ in $\mathcal{D}_{0,*}(k)$. With $\hat{n}_{t}(k_{0}^{(g(k))})\geqslant c_{k,2}\log t$, for every $m\in\mathcal{D}_{0,*}(k)$ such that $k_{0}^{(m)}\neq k_{0}^{(g(k))}$, we have

$$ $UCB_{t}(k_{0}^{(g(k))})=\hat{\mu}_{t}(k_{0}^{(g(k))})+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(k_{0}^{(g(k))})}}\leqslant\mu(k_{0}^{(g(k))})+\Delta(k_{0}^{(m)},k_{0}^{(g(k))})=\mu(k_{0}^{(m)})\leqslant UCB_{t}(m).$ (27) $$

Since $k_{0}^{(g(k))},k_{0}^{(m)}$ are the local optimal arms excluding all arms in $\mathcal{K}_{0}$ and $UCB_{t}(k_{0}^{(g(k))})$ is always less or equal to $UCB_{t}(k_{0}^{(m)})$, target agent $g(k)$ will pull arm $k$ earlier than any agent $m$, assuring enough attack opportunities.

Next, we want to derive a lower bound of $\hat{n}_{t}(k_{0}^{(g(k))})$ for $g(k)$. There are two cases in which $g(k)$ does not pull $k_{0}^{(g(k))}$: it can pull arms either in $\mathcal{K}_{0}^{(g(k))}\setminus\{k_{0}^{(g(k))}\}$ or in $\mathcal{K}^{(g(k))}\cap\mathcal{K}_{0}$. We first consider the former case. Since $k_{0}^{(g(k))}$ is the optimal arm in $\mathcal{K}_{0}^{(g(k))}$, the number of pulls of these suboptimal arms can be bounded by

$$ $\sum_{k^{\prime}\in\mathcal{K}_{0}^{(g(k))}\setminus\{k_{0}^{(g(k))}\}}n^{(g(k))}_{t}(k^{\prime})\leqslant\sum_{k^{\prime}\in\mathcal{K}_{0}^{(g(k))}\setminus\{k_{0}^{(g(k))}\}}\frac{\alpha\log t}{2\Delta^{2}(k_{0}^{(g(k))},k^{\prime})}=c_{k,1}\log t,$ (28) $$

where $n^{(g(k))}_{t}(k^{\prime})$ is the number of times that agent $g(k)$ pulls arm $k^{\prime}$. The inequality comes from the upper bound of the suboptimal arm pulls for UCB algorithms. We then discuss the latter case in which $k^{\prime}\in\mathcal{K}^{(g(k))}\cap\mathcal{K}_{0}$ is pulled. If $\hat{n}_{t}(k^{\prime})\geqslant\frac{\alpha\log t}{2\Delta^{2}_{0}}$, for any non-target agent $m\notin\mathcal{G}_{0}$, there always exists $k^{\prime\prime}\in\mathcal{K}^{(m)}\setminus\mathcal{K}_{0}$ such that

$$ $UCB_{t}(k^{\prime})=\hat{\mu}_{t}(k^{\prime})+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(k^{\prime})}}\leqslant\mu(k^{\prime\prime})-\Delta_{0}+\sqrt{\frac{\alpha\log t}{2\hat{n}_{t}(k^{\prime})}}\leqslant\mu(k^{\prime\prime})\leqslant UCB_{t}(k^{\prime\prime}),$ (29) $$

where the first inequality is due to our attack design in [Eq. 5](#S4.E5). As a result, non-target agents will not pull $k^{\prime}$ anymore. [Eq. 5](#S4.E5) also ensures the number of pulls by target agents after $\hat{n}_{t}(k^{\prime})\geqslant\frac{\alpha\log t}{2\Delta^{2}_{0}}$ is bounded by $\frac{\alpha\log t}{2\Delta^{2}_{0}}$ (similar to the proof of [Lemma 1](#Thmlemma1)). Thus, the total number of arm pulls for all $k^{\prime}\in\mathcal{K}^{(g(k))}\cap\mathcal{K}_{0}$ from agent $g(k)$ is upper bounded by $|\mathcal{K}^{(g(k))}\cap\mathcal{K}_{0}|\cdot\frac{2\alpha\log t}{2\Delta_{0}^{2}}=c_{k,3}\log t$. Then for every $k\in\mathcal{K}_{0}$, we want

$$ $\hat{n}_{t}(k_{0}^{(g(k))})\geqslant t-c_{k,1}\log t-c_{k,3}\log t\geqslant c_{k,1}\log t.$ (30) $$

With a feasible $T_{0}$ such that

$$ $\frac{T_{0}}{\log T_{0}}\geqslant\max_{k\in\mathcal{K}_{0}}c_{k},$ (31) $$

for any $t>T_{0}$, arms in $\mathcal{K}_{0}$ will only be pulled by target agents in $\mathcal{G}_{0}$, and these agents will conduct attacks according to [Eq. 5](#S4.E5). When $t>T_{0}$, for every $k\in\mathcal{K}_{0}$, we can follow the same steps in the proof of [Lemma 1](#Thmlemma1) and obtain

$$ $\hat{n}_{t}(k)\leqslant\frac{\alpha\log t}{2\Delta_{0}^{2}}.$ (32) $$

Based on this, the cost upper bound in [Theorem 3](#Thmtheorem3) can be easily derived by following the same steps in the proof of [Lemma 2](#Thmlemma2), which concludes the proof.
∎

###### Proof.

### A.6 Proof of Theorem 4

###### Proof.

We first prove that at the end of the learning stage, [Algorithm 4](#alg4) can learn the correct mean reward ranking of all arms. For every arm $k\in\mathcal{K}$, we have $\hat{n}_{t}(k)\geqslant L=\left\lceil\frac{2\log(2K/\delta)}{\Delta^{2}_{\min}}\right\rceil$. By Hoeffding’s inequality,

$$ $|\hat{\mu}_{t}(k)-\mu(k)|\leqslant\frac{\Delta_{\min}}{2}$ (33) $$

with probability $1-\delta$, which indicates that sorting all arms according to $\hat{\mu}_{t}(k)$ will give the correct ranking.

We then consider the attack cost incurred during the learning stage. As discussed in [Section 4.3](#S4.SS3), the learning stage ends after no more than $\frac{KL}{cM}$ rounds. Since the attack value per round is upper bound by $\Delta(1,K)+\beta(1)+b$, the total attack cost of $M$ agents is bounded by $\frac{MKL(\Delta(1,K)+\beta(1)+b)}{cM}$, where $b$ is the upper bound of the mean rewards.
In addition, [Algorithm 4](#alg4) also needs to pay a significant cost $\gamma_{t}^{(m)}$ to alter the unbiased empirical mean of $k\in\mathcal{K}_{0}$ for the first time that $k$ is attacked by $m\in\mathcal{G}_{0}$ during the second stage. This is due to the large value of $\hat{n}_{t-1}(k)$ when calculating $\hat{\mu}_{t}(k)$, which necessities a relatively large $\gamma_{t}^{(m)}$ to ensure [Eq. 5](#S4.E5). Since this cost can still be upper bounded by $\frac{KL(\Delta(1,K)+\beta(1)+b)}{c}$, the total additional cost induced by the learning stage is $\frac{2KL(\Delta(1,K)+\beta(1)+b)}{c}$, which appears as the first term of $C(T)$ in [Theorem 4](#Thmtheorem4). Notice that the learning stage of [Algorithm 4](#alg4) directly ensures that $k_{0}^{(g(k))}$ has been sufficiently pulled for every $k\in\mathcal{K}_{0}$. Thus, the cost of the attack stage is the same as that in [Algorithm 3](#alg3), which concludes the proof.

∎

###### Proof.

## Appendix B Additional Results in Homogeneous Settings

### B.1 Attacks against UCB-TCOM

As mentioned in Section [3](#S3), UCB-TCOM stands as the state-of-art algorithm in homogeneous settings. It boasts near-optimal regret, with communication costs limited to just $O(\log\log T)$. The key ideas that help UCB-TCOM algorithm to decrease the communication cost are: first, communications occur only when there are sufficient local samples for the agents; second, information about the optimal arm is not directly broadcast. In this section, we demonstrate that our attack strategy is also effective against the UCB-TCOM algorithm.

To begin with, we first discuss why we need to slightly change [Eq. 3](#S3.E3). This adjustment is required due to the consideration of delayed information. Under the UCB-TCOM strategy, all $M$ agents simultaneously select an arm $k$ for multiple consecutive rounds until the number of samples $\hat{n}_{t}(k)$ exceeds a predefined threshold. We refer to these consecutive rounds as a *phase*. The agents share their local information and update $\hat{\mu}_{t}(k)$, $\hat{n}_{t}(k)$, and UCB values at the end of each phase. As a result, it becomes essential to compute the attack value carefully in each round, accounting for the delayed counters. Assume arm $k_{t}^{(m)}=k\neq K$ for all agents $m\in\mathcal{M}$, where $t$ belongs to a phase from round $s+1$ to $r$, and denote the last phase that arm $k$ is selected ends at as round $t^{\prime}$. We provide the condition in [Eq. 3](#S3.E3) again here:

$$ $\hat{\mu}_{t}(k)\leq\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0},$ (34) $$

while $\hat{\mu}_{t}(K)=\hat{\mu}_{s}(K)$ and $\hat{n}_{t}(K)=\hat{n}_{s}(K)$ and they can be computed in round $t$. In addition, we can compute the true value of $\hat{\mu}_{t}(k)$ even if the agents will not update this value. Assume that we only attack agent $m\in\mathcal{M}$. Then, we can compute the attack values:

$$ $\displaystyle\gamma^{(m)}(t)=$ $\displaystyle(\hat{\mu}_{t^{\prime}}(k)\hat{n}_{t^{\prime}}(k)+\sum_{h=s+1}^{t}\sum_{m^{\prime}=1}^{M}X_{h}^{(m^{\prime},0)}(k)-\sum_{h=s+1}^{t-1}\gamma^{(m)}(h)$ (35) $\displaystyle-(\hat{n}_{t^{\prime}}(k)+(t-s)M)(\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0}))_{+},$ $$

where $(x)_{+}$ represents the maximum of $x$ and 0 0. It is worth noting that [Eq. 35](#A2.E35) handles samples from both the previous phase and the current one separately. The latter requires special consideration due to the delayed updates. The entire process is outlined in [Algorithm 5](#alg5).

Figure: Algorithm 5 Attack against UCB-TCOM (Agent $m$)

###### Theorem 5 .

Suppose $T>K$, set the parameters of UCB-TCOM as $\beta>1$ and $\delta<1/2$. With probability at least $1-\delta$, [Algorithm 5](#alg5) misguides the UCB-TCOM algorithm to choose the target arm $K$ at least
$MT-(K-1)\left(\frac{2\beta}{\Delta_{0}^{2}}\log T\right)$ rounds, using a a cumulative attack cost at most

$$ $\displaystyle C(T)\leqslant\left(\frac{2\beta}{\Delta_{0}^{2}}\log T\right)\sum_{k<K}(\Delta(k,K)+\Delta_{0})+\frac{8(K-1)\sigma^{2}}{\Delta_{0}^{2}}\sqrt{\beta\log T\log\frac{4K\beta^{2}\pi^{2}(\log T)^{2}}{3\delta\Delta_{0}^{4}}}.$ $$

###### Proof.

The proof is similar to [Section A.1](#A1.SS1) and we use the same notations there. However, some steps should be modified carefully.

###### Lemma 3 .

Assume event $E$ holds and $\delta\leqslant 1/2$. For any $k\neq K$ and any $t>K$, we have

$$ $\hat{n}_{t}(k)\leqslant\min\{\beta\hat{n}_{t}(K),\frac{2\beta\log t}{\Delta_{0}^{2}}\}$ (36) $$

###### Proof.

Fix some $t>K$, which satisfies $k_{t}^{(m)}=k\neq K$ for all $m\in\mathcal{M}$, and $t$ is in a phase from round $s+1$ to $r$. Also, denote the last phase arm $k$ is pulled is ended at round $t^{\prime}$. In round $t^{\prime}$, we have the following inequality by our attack design:

$$ $\hat{\mu}_{t^{\prime}}(k)\leqslant\hat{\mu}_{t^{\prime}}(K)-2\beta(\hat{n}_{t^{\prime}}(K))-\Delta_{0}.$ (37) $$

On the other hand, arm $k$ is selected in round $s+1$ because it has the highest UCB in round $s$:

$$ $\hat{\mu}_{s}(k)+\sqrt{\frac{2\log s}{\hat{n}_{s}(k)}}\geqslant\hat{\mu}_{s}(K)+\sqrt{\frac{2\log s}{\hat{n}_{s}(K)}}.$ (38) $$

Note that $\hat{\mu}_{t^{\prime}}(k)=\hat{\mu}_{s}(k)$. Substituting [Eq. 37](#A2.E37) into [Eq. 38](#A2.E38), we have:

$$ $\displaystyle\sqrt{\frac{2\log s}{\hat{n}_{s}(k)}}-\sqrt{\frac{2\log s}{\hat{n}_{s}(K)}}$ $\displaystyle\geqslant\hat{\mu}_{s}(K)-\hat{\mu}_{s}(k)$ (39) $\displaystyle\geqslant\hat{\mu}_{s}(K)-(\hat{\mu}_{t^{\prime}}(K)-2\beta(\hat{n}_{t^{\prime}}(K))-\Delta_{0})$ $\displaystyle\geqslant\Delta_{0}$ $\displaystyle>0,$ $$

where the third inequality is due to the monotonically decreasing property of $\beta()$. Therefore,

$$ $\hat{n}_{t}(K)=\hat{n}_{s}(K)\geqslant\hat{n}_{s}(k)=\frac{1}{\beta}\hat{n}_{r}(k)\geqslant\frac{1}{\beta}\hat{n}_{t}(k).$ (40) $$

In addition, as the bonus term is non-negative, we have:

$$ $\hat{n}_{t}(k)\leqslant\hat{n}_{r}(k)=\beta\hat{n}_{s}(k)\leqslant\frac{2\beta\log s}{\Delta_{0}^{2}}\leqslant\frac{2\beta\log t}{\Delta_{0}^{2}}.$ (41) $$

∎

###### Lemma 4 .

Assume event $E$ holds and $\delta\leqslant 1/2$. For any $k\neq K$ and any $t>K$, we have

$$ $\sum_{h\in\tau(t,k)}\gamma^{(m)}(h)\leqslant\hat{n}_{t}(k)(\Delta(k,K)+\Delta_{0}+3\beta(\hat{n}_{t}(K))+\beta(\hat{n}_{t}(k)))$ (42) $$

###### Proof.

Note that although agents do not update their counters until each phase is over, the attacker does have the latest information thus it can maintain the latest $\hat{\mu}_{t}(k)$ and $\hat{n}_{t}(k)$ in each round $t$ even if it is not the last round of a phase. [Eq. 35](#A2.E35) can be written in this form:

$$ $\displaystyle\gamma^{(m)}(t)=$ $\displaystyle(\hat{\mu}_{t^{\prime}}^{(0)}(k)\hat{n}_{t^{\prime}}(k)+\sum_{h=s+1}^{t}\sum_{m^{\prime}=1}^{M}X_{h}^{(m^{\prime},0)}(k)-\sum_{h\in\tau(t^{\prime},k)}\gamma^{(m)}(h)-\sum_{h=s+1}^{t-1}\gamma^{(m)}(h)$ (43) $\displaystyle-(\hat{n}_{t^{\prime}}(k)+(t-s)M)(\hat{\mu}_{r}(K)-2\beta(\hat{n}_{r}(K))-\Delta_{0}))_{+},$ $$

where $\hat{\mu}_{t^{\prime}}^{(0)}(k)$ is the global pre-attack empirical mean of arm $k$ up to round $t^{\prime}$. Also, as in [Section A.1](#A1.SS1), we only consider the round $t$ such that $\gamma^{(m)}(t)>0$. Therefore, we have:

$$ $\displaystyle\sum_{h\in\tau(t,k)}\gamma^{(m)}(h)$ $\displaystyle=\hat{\mu}_{t^{\prime}}^{(0)}(k)\hat{n}_{t^{\prime}}(k)+\sum_{h=s+1}^{t}\sum_{m^{\prime}=1}^{M}X_{h}^{(m^{\prime},0)}(k)-(\hat{n}_{t^{\prime}}(k)+(t-s)M)(\hat{\mu}_{r}(K)-2\beta(\hat{n}_{r}(K))-\Delta_{0})$ (44) $\displaystyle=\hat{n}_{t}(k)(\hat{\mu}_{t}^{0}(k)-(\hat{\mu}_{t}(K)-2\beta(\hat{n}_{t}(K))-\Delta_{0}))$ $\displaystyle\leqslant\hat{n}_{t}(k)(\Delta(k,K)+\Delta_{0}+3\beta(\hat{n}_{t}(K))+\beta(\hat{n}_{t}(k))),$ $$

where the last inequality is due to the event $E$.
∎

With [Lemma 3](#Thmlemma3), we can easily get that the target arm $K$ is selected for at least $MT-(K-1)(\frac{2\beta}{\Delta_{0}^{2}}\log T)$ times. For the cumulative cost, we use [Lemma 4](#Thmlemma4), and sum over all non-target arms. Also, it is easy to get $\beta(\hat{n}_{t}(K))\leqslant\beta(\frac{1}{\beta}\hat{n}_{t}(k))$ as $\beta()$ is a monotonically decreasing function. Therefore,

$$ $\displaystyle\sum_{t=1}^{T}\gamma^{(m)}(t)$ $\displaystyle\leqslant\sum_{k=1}^{K-1}\hat{n}_{t}(k)(\Delta(k,K)+\Delta_{0})+4\beta\sum_{k=1}^{K-1}\hat{n}_{t}(k)\beta(\frac{1}{\beta}\hat{n}_{t}(k))$ (45) $\displaystyle\leqslant\left(\frac{2\beta}{\Delta_{0}^{2}}\log T\right)\sum_{k<K}(\Delta(k,K)+\Delta_{0})+\frac{8(K-1)\beta^{2}\sigma}{\Delta_{0}^{2}}\sqrt{\log T\log\frac{4K\pi^{2}(\log T)^{2}}{3\delta\Delta_{0}^{4}}}.$ $$

∎

###### Theorem 5 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

### B.2 Attacks against Leader-follower Algorithm

In contrast to fully distributed algorithms, there exists a server, or leader (agent) in leader-follower algorithms, which has a pivotal role in exploration. On the other hand, the followers always undertake exploitation. In this section, we consider attacks on a representative leader-follower algorithm, the DPE2 algorithm, proposed by  []. We show that our attack algorithm against fully distributed algorithms can be extended to these leader-follower algorithms.

We first introduce some new notations to differentiate between leader-follower algorithms and fully distributed algorithms. Without loss of generality, let agent $1$ be the leader of the system. Let $\hat{N}_{t}(k)$ denote the times arm $k$ is selected up to time slot $t$, and $\hat{V}_{t}(k)$ be the post-attack empirical mean associated with $\hat{N}_{t}(k)$. For the ease of presentation, we consider the UCB1 induces instead of the KL-UCB induces, and define $D_{t}(k):=\hat{V}_{t}(k)+\sqrt{\frac{\alpha\log t}{2\hat{N}_{t}(k)}}$ as the UCB. The leader explores different arms by maintaining a list $C(t)$ which contains the suboptimal arms whose upper bounds are larger than the empirical mean of what it considers to be the optimal arm. Similar to the UCB-TCOM algorithm, the information is not updated immediately after each round. We also define the phase in the process. When $C(s-1)=\emptyset$ and $C(s)\neq\emptyset$, we say the phase begins at round $s$; and when $C(r-1)\neq\emptyset$ and $C(r)=\emptyset$, we say the phase ends at round $r-1$. As the design of DPE2, the information of all arms will be updated in round $r$. We then introduce our attack algorithm.

As the followers always select the arm which the leader considers as the best, we only need to misguide the leader to regard the target arm $K$ as the optimal arm. Therefore, we only need to attack the leader. Assume $k_{t}^{(1)}=k\neq K$, and $t$ belongs to a phase from round $s$ to $r-1$. Our attacks make sure:

$$ $\hat{V}_{r}(k)\leqslant\hat{V}_{s}(K)-2\beta(\hat{N}_{s}(K))-\Delta_{0},$ (46) $$

where $\hat{V}_{r}(k)=\frac{\hat{V}_{s}(k)\hat{N}_{s}(k)+X_{t}^{(1,0)}(k)-\gamma(t)}{\hat{N}_{r}(k)}$, and the attack value is $\gamma(t)$. The details are described in [Algorithm 6](#alg6).

Figure: Algorithm 6 Attack against DPE2 (Leader)

###### Theorem 6 .

Suppose $T>T_{0}$, and $\delta<1/2$. With probability at least $1-\delta$, [Algorithm 6](#alg6) misguides the DPE2 algorithm to choose the target arm $K$ at least
$M(T-K)-(K-1)\left(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1\right)$ rounds, using a a cumulative attack cost at most

$$ $\displaystyle C(T)\leqslant$ $\displaystyle\left(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1\right)\sum_{k<K}(\Delta(k,K)+\Delta_{0})$ $\displaystyle+4(K-1)\sigma\sqrt{2(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1)\log(\frac{K\pi^{2}}{3\delta}(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1)^{2})},$ $$

where $T_{0}/\log(T_{0})=K\lceil\frac{\alpha}{2\Delta_{0}^{2}}+1\rceil$.

###### Proof.

The proof is similar to [Section A.1](#A1.SS1) as well.

###### Lemma 5 .

Assume event $E$ holds and $\delta\leqslant 1/2$. For any $k\neq K$ and any $t>T_{0}$, we have

$$ $\hat{N}_{t}(k)\leqslant\frac{\alpha}{2\Delta_{0}^{2}}\log t+1$ $$

###### Proof.

Fix some $t>T_{0}\geqslant K$, which satisfies $k_{t}^{(1)}=k\neq K$, and $t$ is in a phase from round $s$ to $r-1$. Also, assume the last phase arm $k$ is pulled from round $s^{\prime}$ to $r^{\prime}-1$. In round $r^{\prime}$, we have the following inequality by the design of our attacks:

$$ $\hat{V}_{r^{\prime}}(k)\leqslant\hat{V}_{s^{\prime}}(K)-2\beta(\hat{N}_{s^{\prime}}(K))-\Delta_{0}.$ (47) $$

On the other hand, arm $k$ is selected in round $s$ because the following inequality holds in round $s$:

$$ $\hat{V}_{s}(k)+\sqrt{\frac{\alpha\log s}{\hat{N}_{s}(k)}}\geqslant\hat{V}_{s}(K).$ (48) $$

Note that $\hat{V}_{s}(k)=\hat{V}_{r^{\prime}}(k)$. Substituting [Eq. 47](#A2.E47) into [Eq. 48](#A2.E48), we have:

$$ $\displaystyle\sqrt{\frac{\alpha\log s}{\hat{N}_{s}(k)}}$ $\displaystyle\geqslant\hat{V}_{s}(K)-\hat{V}_{s}(k)$ (49) $\displaystyle\geqslant\hat{V}_{s}(K)-(\hat{V}_{s^{\prime}}(K)-2\beta(\hat{N}_{s^{\prime}}(K))-\Delta_{0})$ $\displaystyle\geqslant\Delta_{0},$ $$

where the third inequality is due to the monotonically decreasing property of $\beta$. Therefore, this ends the proof as $\hat{N}_{t}(k)\leqslant\hat{N}_{s}(k)+1$.
∎

###### Lemma 6 .

Assume event $E$ holds and $\delta\leqslant 1/2$. For any $k\neq K$ and any $t>K$, we have

$$ $\sum_{h\in\tau(t,k)}\gamma(h)\leqslant\hat{N}_{t}(k)(\Delta(k,K)+\Delta_{0}+3\beta(\hat{N}_{t}(K))+\beta(\hat{N}_{t}(k)))$ (50) $$

###### Proof.

Similar to [Eq. 43](#A2.E43), the attack value can be written in this form:

$$ $\displaystyle\gamma(t)=$ $\displaystyle\left(\hat{V}_{s}^{(0)}(k)\hat{N}_{s}(k)+X_{t}^{(1,0)}(k)-\sum_{h\in\tau(s,k)}\gamma(h)-(\hat{N}_{s}(k)+1)(\hat{V}_{s}(K)-2\beta(\hat{N}_{s}(K))-\Delta_{0})\right)_{+},$ (51) $$

where $\hat{V}_{s}^{(0)}(k)$ is the global pre-attack empirical mean of arm $k$ up to round $s$ (for the leader). Also, as in [Section A.1](#A1.SS1), we only consider the round $t$ such that $\gamma(t)>0$. Therefore, we have:

$$ $\displaystyle\sum_{h\in\tau(t,k)}\gamma(h)$ $\displaystyle=\hat{V}_{s}^{(0)}(k)\hat{N}_{s}(k)+X_{t}^{(1,0)}(k)-(\hat{N}_{s}(k)+1)(\hat{V}_{s}(K)-2\beta(\hat{N}_{s}(K))-\Delta_{0})$ (52) $\displaystyle=\hat{N}_{t}(k)(\hat{V}_{t}^{0}(k)-(\hat{V}_{t}(K)-2\beta(\hat{N}_{t}(K))-\Delta_{0}))$ $\displaystyle\leqslant\hat{N}_{t}(k)(\Delta(k,K)+\Delta_{0}+3\beta(\hat{N}_{t}(K))+\beta(\hat{N}_{t}(k))),$ $$

where the last inequality is due to the event $E$.
∎

With [Lemma 5](#Thmlemma5), we can easily get that the target arm $K$ is selected for at least $M(T-K)-(K-1)\left(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1\right)$ times because in the beginning, followers randomly select an arm to pull, and after that, $K$ will be the optimal arm for the leader after each phase, so that followers won’t select arms other than $K$. As for the cumulative cost, we introduce [Lemma 6](#Thmlemma6), and sum over all non-target arms. Also, it is easy to get $\beta(\hat{N}_{t}(K))\leqslant\beta(\hat{N}_{t}(k))$ as $\beta$ is a monotonically decreasing function and $T>T_{0}$, which means $\hat{N}_{t}(k)\leqslant\hat{N}_{t}(K)$ holds for any $k\neq K$. Therefore,

$$ $\displaystyle\sum_{t=1}^{T}\gamma(t)$ $\displaystyle\leqslant\sum_{k=1}^{K-1}\hat{N}_{t}(k)(\Delta(k,K)+\Delta_{0})+4\beta\sum_{k=1}^{K-1}\hat{N}_{t}(k)\beta(\hat{N}_{t}(k))$ (53) $\displaystyle\leqslant\left(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1\right)\sum_{k<K}(\Delta(k,K)+\Delta_{0})$ $\displaystyle+4(K-1)\sigma\sqrt{2(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1)\log(\frac{K\pi^{2}}{3\delta}(\frac{\alpha}{2\Delta_{0}^{2}}\log T+1)^{2})}.$ $$

∎

###### Theorem 6 .

###### Proof.

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

### B.3 Additional Experiments

Figure: (a) Average Regrets
Refer to caption: /html/2311.01698/assets/Figure/IC-regrtet.pic.jpg

In this section, we show the experimental results of attacks against the CO-UCB algorithm in homogeneous settings. We set $T=100,000,K=20,M=20$. The distributions of arms are the same as those in [Section 5](#S5). CO-UCB takes $\alpha=4$, and attack parameters are set to $\Delta_{0}=0.1$, and $\delta=0.1$. We compare our algorithm, which only attacks one agent, with two baselines: the first one attacks all agents using attack values computed by [Eq. 3](#S3.E3) for each agent; the second one is the original CO-UCB algorithm without attacks. Each experiment was repeated for $10$ times.

In Figures [Fig. 3(a)](#A2.F3.sf1) and [Fig. 3(b)](#A2.F3.sf2), the CO-UCB algorithm displays sublinear regret; the curve showcasing its regret gradually approaches 0 0, and the algorithm seldom opts for the suboptimal target arm $K$. However, both attack strategies successfully misguide the CO-UCB algorithm, leading it to consistently select our target arm, as shown in [Fig. 3(b)](#A2.F3.sf2). This causes linear regrets, as highlighted in [Fig. 3(a)](#A2.F3.sf1).
Notably, the divergence between these attack algorithms in both figures is minimal, suggesting that even though our attack is designed to target just one agent, it is almost as effective as a strategy targeting all agents.
Looking at [Fig. 3(c)](#A2.F3.sf3), the cumulative attack costs for both strategies are nearly indistinguishable, converging towards 0 0. This points to sublinear costs for both. Such a finding amplifies the effectiveness of our attack design: despite focusing on a single agent, the cumulative cost is nearly identical to an approach targeting all $20$ agents.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. What are the additional challenges in adapting the results of Jun et al. [2018] for the homogeneous setting with CO-UCB?

2. Can we experimentally verify if these results would work for cooperative versions of simple MAB algorithms like $\epsilon$-greedy or Thompson sampling?
soundness: 3
strengths: 1. The setting of adversarial attacks on cooperating bandits studied in the paper is well-motivated
2. The authors provide the analysis for the homogeneous and heterogeneous settings, and under different CMA2B algorithms, at least in the homogeneous setting. The results that UCB style CMA2B algorithms can be  $o(T)$ corruptions and cause a target suboptimal arm to be selected for $T - o(T) times by targeting just one arm in homogeneous settings has novelty. The detailed analysis of the heuristics AAS and TAS also shows that agents showing that a large number of agents can be attacked using sublinear corruptions is also valuable. The authors also provide an analysis of the case when rankings are not known to the attacker making the attack more practical. 
2. The authors provide experimental evidence for the novelty of AAS and TAS.
3. The paper is overall well written, with clear notations
summary: This paper studies adversarial attack strategies in the Cooperative Multi-Arm Bandit setting CMA2B. In the Cooperative Multi-Arm bandit setting ($M$) agents pull one arm each in round $T$ and observes reward sampled from a distribution associated with the arm. The agents some can communicate with each other to accelerate learning. In this paper, the authors study how an attacker can take advantage of agents trusting other agent's data, and can attack a subset of agents and influence other agents as well.
They study the problem in two settings:

i) Homogeneous setting: Here all agents have access to all arms. They show only one agents can be injected with $o(T)$ corruptions and cause a target suboptimal arm to be selected for $T - o(T)$ rounds under the CO-UCB algorithm. They also show results for UCB-TCOM (a communication efficient UCB style algorithm), DPE2 (a leader-follower algorithm), and general no-regret algorithms.

ii) Heterogeneous setting: In this setting, each agent has access to a subset of arms. They show that there can be instances where arms are distributed in a way that to incur linear regret to each agent in CO-UCB, an attacker would need a linear attack budget.

They propose a selection algorithm called AAS to select the arms that are optimal for as many non-conflicting agents and TAS to select agents to attack. They provide regret guarantees for the CO-UCB algorithm under this setting. 

They also provide experiments with simulated data for comparing their attacks on the CO-UCB algorithm.
weaknesses: 1. The homogeneous setting studied under the Co-UCB is very similar to the results for UCB obtained in Jun et al. [2018]  as every agent can see every other agents rewards and updates the mean rewards and counts, it's similar to the one agent setting, but the agent obtains $M$ samples in every round from the arm they pull instead of 1, thus I believe the results of \citet{jun2018adversarial} can can be modified to obtain this result, so there is limited novelty in this result.

2. Most of the results are on UCB style algorithms, or on the communication model where all agents immediately share the information will all other agents. I feel this is fairly limited setting as the samples are effectively shared easily and it makes the attack easy as any agent can be attacked with a big enough value that gets propagated to all other agents. What happens when the communication model is constrained through addition structures for e.g., the graph structured discussed in Landgren et al. [2016].
They do provide analysis for UCB-TCOM and DPE2 with delayed communication, but in both case, the information is still easily transmitted to all agents.

3. I believe the results against general algorithms need some more refinement in terms of assumptions. Line 1308 on Page 25 assumes that since the other arms' samples always come from a distribution with a mean less than the mean of the target arm, we can consider arm $K$ to be the best arm. The results for general bandit algorithms are based on the fact that reward samples are being sampled from a fixed distribution, if the sample distribution for the other arms is changing with $t$ (as the attack), I don't think we can directly claim Assumption 2 to hold. The main point is that in Assumption 1, it's not clear what it means that the 'agents maintain identical empirical means for making decisions'. Maybe the authors can refine Assumption 1 to a class of more restricted MAP/CMA2B algorithms like the mean based algorithms defined in Xu et al. [2021].

4. It's difficult to understand the $T_0$ term in the heterogeneous results, and how it's always a constant.

5. The experiments provided are fairly limited, with no error bars. 

Minor comments:
In line 707, it should be $- \hat{\mu} (K)$ instead of  $+ \hat{\mu} (K)$

References:
1. Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. Advances
in neural information processing systems, 31, 2018.

2. Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision-making
in multiarmed bandits: Frequentist and bayesian algorithms. In 2016 IEEE 55th Conference on Decision
and Control (CDC), pages 167–172. IEEE, 2016.

3. Yinglun Xu, Bhuvesh Kumar, and Jacob D Abernethy. Observation-free attacks on stochastic bandits.
Advances in Neural Information Processing Systems, 34:22550–22561, 2021

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: Pls see my questions in weaknesses.
soundness: 2
strengths: 1.	This paper is well-written and easy to follow, with clear assumptions and a thorough review of existing literature.
2.	The authors address both homogeneous and heterogeneous settings in designing efficient attack algorithms, offering a solid theoretical analysis of the regret lower bounds induced by these attacks.
summary: This work considers the cooperative multi-agent multi-armed bandits (CMA2B) problem to design attack algorithms, which aim to attack on a few agents to influence the decisions of the rest. The authors consider two different settings, i.e., (1) homogeneous settings, where agents operate with the same arm set, and (2) heterogeneous settings, where agents may have distinct arm sets, to design different attack algorithms. Then they provide theoretical analysis on the caused bad regret of CMA2B system under their attack algorithms. Finally, they conduct numerical experiments to verify the efficiency of their proposed algorithms.
weaknesses: While the paper is presented well, the assumptions are highly restrictive, and the proposed attack algorithms apply only to specific CMA2B algorithms (i.e., CO-UCB or UCB-TCOM), which limits the general applicability of this work.
 
Specific concerns include:
(1)	No Collision: The authors overlook collisions in the multi-agent MAB (MMAB) problem, lacking literature support for this choice. Most studies on MMAB, including works like Boursier & Perchet (2019), incorporate collisions when multiple players select the same arm simultaneously. This assumption is particularly relevant in applications such as cognitive networks.
(2)	Pre-Attack Reward Observability: The paper assumes that the attacker can observe pre-attack rewards for all agents, which seems unrealistic in practical applications. It remains unclear how an attacker would access this information.
(3)	Prior Knowledge of Local Arm Sets: In the heterogeneous setting, the assumption that the attacker knows each agent’s local arm set also seems impractical.
(4)	Algorithm Awareness: The assumption that the attacker knows each agent’s exact algorithm is the strongest and most limiting. This could be plausible if the attacker were an agent within the CMA2B setup, yet targeting a specific algorithm still limits the broader impact of the proposed methods.
(5)	Other strong assumptions include (a) the attacker knows the exact leader in the leader-follower structure, and (b) The attacker has prior knowledge of the reward ranking of all arms. While the authors relax this latter assumption in Section 4.3, introducing this relaxation earlier could strengthen the contribution.
I recognize that this is a theoretical study; however, given that the motivation for these attack algorithms is practical application, the heavy reliance on these assumptions restricts their practical relevance.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 1
questions: - In Table 1, do we assume that all arms have different means? Otherwise, it is possible that the same agent has several optimal arms and is counted in $M_{*}(k)$ for several arms. The same holds for the results in Thms 3,4. 
- In line 359 for $\hat{\mu}_{t}(k)$, why are all pre-attack values $X_t^{(m',0)}(k)$ for arm $k$ counted? If I understand correctly, it does not hold that all agents draw the same arm at each round. 
- For the heterogeneous setting, do the authors think it is possible to choose a smaller group of target agents than the one in this paper? Can the attack cost be lower than $O(K\log T)$ for some other attack strategy? 
- In line 203, can the authors expand more on why the multi-agent setting is more challenging, and what makes the analysis more involved?
- For Figure 3a, what is the average regret, and how were experiments for OA and LTA performed without AAS?
- In the discussion on page 8 before 4.2.4, can you explain in more detail what it means that target agents are 'the first' to pull an arm? This point is repeated a few times but is not entirely clear.
soundness: 3
strengths: - **Originality:** While previous works have dealt with robustness in multi-agent bandit systems against weak corruptions [1,2], this paper addresses weaknesses against adversarial attacks tailored for this setting. The attack target for the heterogeneous setting is novel compared to single-agent bandits [3]. 
- **Quality:** The theoretical analysis is rigorous, with clear proofs supporting the various claims and an experimental evaluation section. 
- **Clarity:** Using simple example cases, the paper explains the motivation and intuition behind using a different attack target than in previous works. 
- **Significance:** By highlighting the potential for low-cost adversarial disruptions in cooperative learning systems, the paper reveals critical vulnerabilities that could have implications for designing more robust systems. 

[1] Vial, Daniel, Sanjay Shakkottai, and R. Srikant. "Robust multi-agent multi-armed bandits." Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. 2021.

[2] Dubey, Abhi, and Alex Pentland. "Private and Byzantine-Proof Cooperative Decision-Making, 20th Conf. Autonomous Agents and Multiagent Systems, 2020.", 2020.

[3] Jun, Kwang-Sung, et al. "Adversarial attacks on stochastic bandits." Advances in neural information processing systems 31 (2018).
summary: This work examines vulnerabilities in cooperative multi-agent multi-armed bandit systems, where agents work together to maximize rewards but can be disrupted by adversarial attacks targeting a few agents’ feedback. In homogeneous settings, where agents share the same choices, the authors show that minimal manipulation of one agent’s observations can influence the entire group to select suboptimal arms. In heterogeneous settings, with agents having different options, the authors propose strategies to induce linear regret among the maximum number of agents by attacking a few key agents. In addition to theoretical results, the authors support their claims with experimental evaluations.
weaknesses: **Minor issues:**
- line 47: hope->hopes
- line 68: since this point is addressed in this work, the phrase 'remain uncertain' is confusing. 
- line 75: 'remains an unresolved issue' - similar to my last remark. 
- line 101: 'with its cost analysis'-> 'and analyze its cost'. 
- line 131: the use of 'observes' is confusing here, as this is the pre-attack value and is not necessarily observed as is. 
- line 139: 'collision'-> collision model. 
- lines 143-152: The authors should explain this choice for the heterogeneous model, or cite previous works that use it. 
- lines 191,423: 'no-regret'-> sublinear regret
- section 4.1: the intuitive examples could be explained better - how many arms does each agent have?
- lines 352-361: the term 'attack value' was never formally defined, nor did the mean $\hat{\mu}$.
- line 362: 'constant fulfills'-> constant that fulfills. 
- line 424: 'affected'-> target.
- line 449: 'unknown'->known.
- line 484: 'when'-> at
- line 519: 'Leaning'-> Learning

**Other issues:**
- This work is not written clearly and assumes the reader possesses extensive technical knowledge about adversarial attacks in bandits. For example, the term attack value is not explained in the main text, and the idea behind equation (2) is also unclear. The parameters in Thm 1 are undefined as well: What are $\alpha,\Delta_0$?
- Table 1 is misleading. For the first and second lines, it is unclear whether knowledge about the time horizon $T$ is needed. The authors can cite [1] rather than [2] if it is not. More importantly, the third line assumes oracle knowledge of the attacker about arm rankings (Thm 3), which is a strong assumption. When using the version that does not use this assumption, the attack cost becomes much larger at $O(K\log T/\Delta_{\min}^2)$ (Thm 4).
- The problem addressed in this paper could be motivated better. In the Introduction, the authors mention advertisers that share information about users as an example of a multi-agent bandit system that can be attacked. However, I am not sure how practical this problem is given the requirements for user privacy preservation. It would be nice if the authors could expand on that, provide references, or suggest additional motivation. 
- While the attack design for heterogeneous systems is novel, it should be mentioned that the attack itself used in this paper 
technically resembles techniques from previous works [1,2] (for instance, equation (2)). 
- The difficulty of adversarial attacks on a heterogeneous multi-agent system is not fully characterized. The authors mention it is not possible to cause all agents to suffer linear regrets, and find a nearly maximal set of affected agents. Regarding the target agents group, it is unclear to me if the one used in this paper is the minimal one, or if we can use fewer target agents with the same effect. In addition, as mentioned above, the attack cost under realistic assumptions is $O(K\log T/\Delta_{\min}^2)$ for the heterogeneous case, but there is no lower bound to show how good this result is. 
- In the heterogeneous case, an attack is only designed for one algorithm. For single-agent bandits, it is acceptable to design attacks for very basic algorithms like UCB and $\epsilon$-greedy as done in [2], but in the multi-agent setting, it is unclear whether an attack on CO-UCB provides insight into attacks on other algorithms. Perhaps the authors can further expand on this point - is CO-UCB as fundamental for heterogeneous multi-agent bandits as UCB is for single-agent bandits?
- Figure 3a is not clear. What is the 'average regret' that is plotted here? Since it remains constant, I suppose it should be some kind of instantaneous regret, but this is not explained at all and the only regret defined in this paper is the cumulative one. In addition, it is unclear how the OA and LTA algorithms are performed without AAS. 

[1] Zuo, Shiliang. "Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

[2] Jun, Kwang-Sung, et al. "Adversarial attacks on stochastic bandits." Advances in neural information processing systems 31 (2018).

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: See the above weaknesses.

It is likely that the agents know the distribution type for the rewards (even if they don't know the expected value or anything else). In that setting, the attacker injecting strategically chosen errors (without any real constraint) might tip the agent to think something is amiss since the samples may not reflect the distribution family they know the problem to have. Do you think it's possible - specifically in the attacks you have discussed? In general, there might be reasonable constraints to add on what can be injected.
soundness: 3
strengths: The work is well-written and quite easy to follow and quickly gain the main insights. The authors do a good job of highlighting their assumptions and the model, and then investigating a lot of the natural questions that emerge. If we take the model as a given, the contributions are sound.

I found the impossibility results in the heterogenous setting particularly insightful. It almost suggests that for a goal-oriented adversary (and not a purely malicious one) it is quite difficult to achieve their target without incurring high cost.
summary: This paper studies adversarial attacks in a multi-armed bandit setting, where multiple learners are collaboratively learning. The agents may communicate their shared information between themselves. An adversary may, however, sit between the environment generating rewards and the agent and specify erroneous rewards to them. The adversary wishes to derail the agents while minimizing the number of times they need to intervene. The paper studies two models - *homogeneous*, where any agent can pull any arm and *heterogeneous* where an agent may pull only a subset of arms (determined exogenously). The first setting is easy for the adversary and using similar ideas from literature, the paper gives a nearly optimal bound. The second setting is harder, and the paper gives a set of results under different adversary goals.

In general, I found the work well-written and clearly explained and exposited. Taking the model as a given, the paper studies the reasonable set of questions that arise. That said, I am not convinced of the underlying model of collaboration or adversary that is presented; while I am quite familiar with bandit literature, this sub-category of bandit literature is not as known to me and I am unsure about how to correctly contextualize the results and reason about the major takeaways. As such, I am borderline on the work.
weaknesses: My main concern is the applicability or relevance of the model. What exactly is the setting where one would encounter the scenario proposed and thus this work would be insightful? Could you provide some motivating examples? Specifically, the heterogenous setting (the main meat of the paper) where an oracle attacker is assumed. The setting here afaik is as follows:
* A number of agents are collaboratively learning the same online learning with unlimited communication, but a powerful adversary, who knows the true ranking of all arms, can inject arbitrary errors into the observations of any agent? 

In the heterogenous section, you essentially argue for an attacker's goal as misleading agents, and not necessarily get their (attacker's) sub-opt arm picked. In this sort of purely adversarial, almost zero-sum type of attacker reasonable? Under what context could we expect such as attacker? Or do we gather any technical/conceptual insights under this model?

In the paper, it is assumed that the attacker knows the algo used by the learner. While it can be relaxed in the homogenous case, it is necessary in the heterogenous case. I am happy that the authors explicitly mention this, but given that the heterogenous case is the main contribution of the paper, I still find this quite a big assumption and somewhat unreasonable. Are there settings you can motivate where this might be the case?

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: Regarding the problem setting, what is the difference between this paper’s attack setting and previous works such as ICML’20 https://proceedings.mlr.press/v125/boursier20a.html, Mobihoc’21 paper ahttps://dl.acm.org/doi/abs/10.1145/3466772.3467045 and AAMAS’22 https://dl.acm.org/doi/10.5555/3635637.3662992.(and possibly others since I only did a light search about “attacking multi-agent bandits” on Google Scholar)? 

It seems to the reviewer that the homogeneous agent setting is a simple corollary of Zuo’24 result. Would it be possible to just describe Theorem 1 as a simple corollary of Zuo’24? What’s the research value of theorem 1? 

Can we eliminate TAS? What is the benefit of including TAS? Currently Theorem 3 shows that the attack cost is independent of the number of affected agents by attacking limited number of agents generated by TAS, what if we just attack agents in K0? What will change? Will it significantly inflate the attacking cost?

Are there any real-world applications, aside from “botnets,” that can be modeled as adversarial attacks on cooperative multi-agent bandits? The introduction currently provides only one example and lacks supporting references.
soundness: 1
strengths: This paper is the first to explore adversarial attacks in the context of cooperative learning within multi-agent, multi-armed bandits. This problem is novel. Furthermore, the design of the algorithms for Affected Agents Selection (AAS), Target Agents Selection (TAS), and the proof of Theorem 3 are both innovative and nontrivial.
summary: This paper presents attack strategies for collaborative multi-armed bandits using CO-UCB algorithms under two distinct settings: a homogeneous setting, where all agents have access to all arms, and a heterogeneous setting, where different agents have access to different subsets of arms. For the heterogeneous setting, the author considers two types of attackers: an oracle attacker, who has explicit knowledge of the average reward ranking of each arm, and a non-oracle attacker, who lacks this information. Additionally, the author conducts experiments to validate the theoretical results.
weaknesses: First, the paper lacks discussion about the novelty and major technical challenges for various results (e.g., Theorem 1, Proposition 1 and 2), which makes it really difficult to judge the significance of the contribution. For instance, they state: "In Section 3, for homogeneous CMA2B, we devise attack strategies for three representative algorithms by targeting a single agent to misguide all agents. We prove that the attack costs are independent of the number of agents, M." However, since observations are shared and all agents are homogeneous, it is unsurprising that attacking one agent could misguide the rest, making the cost independent of M. This result appears intuitively straightforward. Additionally, the attack strategy seems quite similar to that in Zuo, S. (2024, April), with the proof being a straightforward extension from the single-agent to the multi-agent setting. The authors do not highlight any significant additional challenges, making it unclear how significant the technical contributions are. 

Second, many results and proofs are inaccurate, and require the reader’s careful verification in order to convince themselves that the proof or statement is really correct. Even I was able to verify that some missing proofs can be fixed, I was not able to check all the proofs and it makes me feel the paper really needs significant amount of re-writing and polishing before being ready for publication. 
1.	In the statement of Theorem 1, the term "our attack strategy" is ambiguous because there is only some vague descriptions about the attack idea and no clear mathematical definition about the attack. The reader had to go to the appendix to check the definition.
2.	In the proof of Theorem 2 (page 16), it states “\(f\) is submodular and the greedy algorithm in Algorithm 1 gives a \((1 - 1/e)\)-approximation solution”. This is inaccurate – the paper needs to additional prove the function is monotone and non-negative (PS: the paper also need to cite papers for this statement as not everyone knows this result). I think I convinced myself that these two properties are also true, but I think a maturely written paper should not ask reviewers to complete these reasonings and verify correctness.  
3.	In Theorem 3 (also Theorem 4), the term \(\Delta(k, k+1)\) is not defined rigorously, as the author has not established that \(K \notin K_0\). If \(K \in K_0\), \(\Delta(K, K+1)\) is undefined. Also, Equation (3) does not include \(T_0\); actually none of the equations in this page has T_0. In the statement of Theorem 3, the definition of \(g(k)\) is missing, which also affects the subsequent discussion. I had to go to the appendix to double check the correct expression and definition


In addition to above concerns on the significance of contributions, the paper contains a few other major issues, including too many syntax issues, gaps in proofs, too much assumptions of prior knowledge from the reader, and a lack of discussion on the contributions (including over-claiming contributions). These factors make it difficult for readers to fully understand the key ideas and may lead them to question the rigor of the proofs. A few examples are listed as follows.

1.	Line 111 to 112, the paper claims that “Our work is the first to study how an attacker may manipulate multi-agent cooperative learning”. However, this ICML’20 https://proceedings.mlr.press/v125/boursier20a.html, Mobihoc’21 paper ahttps://dl.acm.org/doi/abs/10.1145/3466772.3467045 and AAMAS’22 https://dl.acm.org/doi/10.5555/3635637.3662992 seem to have already been studying similar problem of attacking cooperative bandit problem.  
 
2.	In line 6 of Algorithm 1, what is \(\omega(k)\)

3.	On Page 5, line 268, the stated goal is to “leverage sublinear attack costs to misguide the maximum number of agents, aiming to increase the overall count of agents enduring linear regrets.” However, why using Algorithm 3 will lead to “attacking the maximum number of agents” is neither justified nor adequately explained in the subsequent paragraphs, leaving readers to infer the reasoning on their own. 

4.	The second claimed contribution appears to be inaccurate. The paper states, "linear costs are necessary to fool all agents into suffering linear regrets." However, this seems straightforward, as the target arm attack might not be a suitable objective in a heterogeneous environment (as mentioned in line 252). Therefore, a more accurate contribution might be to propose an appropriate and meaningful "attacking goal" specifically tailored to the heterogeneous setting, based on my understanding.

5.	On page 7, line 327, the phrase “is it feasible to attack this group using only a limited number of agents” is unclear. It would be beneficial to clarify what is meant by “using a limited number of agents.” If the intended meaning is “attacking a limited number of agents to misguide the maximum number of agents without conflicts, resulting in linear regret,” then it should be explicitly stated to avoid confusion.

6.	On page 9, line 463, the term \( \text{UCB}_t(k) \) is introduced without being defined (though the reviewer knows, but this is not a proper way to write a general-purpose ML paper), and there is no reference to this quantity elsewhere in the text.

7.	Figure 3 lacks standard deviations or confidence intervals, which undermines the claim that “Both LTA and OA result in the most significant average regrets.” Without measures of variability, it is difficult to assess the statistical reliability and significance of this claim. To strengthen the argument, it would be beneficial to include standard deviations or confidence intervals in the figure, providing a clearer depiction of the uncertainty and supporting the robustness of the results.

Meta-review: This paper studies adversarial attacks on cooperative multi-agent multi-armed bandits (CMA2B) in both homogeneous and heterogeneous settings. The reviewers agree that the paper addresses an interesting and well-motivated problem. However, the reviewers raised several shared concerns including limited technical novelty, unclear discussion about contributions, relatively strong assumptions, and presentation issues with technical results. I recommend rejection for current version, and believe the submission would get much stronger by revising according to reviewers' suggestions.

Decision: Reject