# Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learning

Guanlin Liu
Department of Electrical and Computer Engineering
University of California, Davis
One Shields Avenue, Davis, CA 95616
<EMAIL_ADDRESS>
&Lifeng Lai
Department of Electrical and Computer Engineering
University of California, Davis
One Shields Avenue, Davis, CA 95616
<EMAIL_ADDRESS>

###### Abstract

Due to the broad range of applications of multi-agent reinforcement learning
(MARL), understanding the effects of adversarial attacks against MARL model is
essential for the safe applications of this model. Motivated by this, we
investigate the impact of adversarial attacks on MARL. In the considered
setup, there is an exogenous attacker who is able to modify the rewards before
the agents receive them or manipulate the actions before the environment
receives them. The attacker aims to guide each agent into a target policy or
maximize the cumulative rewards under some specific reward function chosen by
the attacker, while minimizing the amount of manipulation on feedback and
action. We first show the limitations of the action poisoning only attacks and
the reward poisoning only attacks. We then introduce a mixed attack strategy
with both the action poisoning and the reward poisoning. We show that the
mixed attack strategy can efficiently attack MARL agents even if the attacker
has no prior information about the underlying environment and the agents’
algorithms.

##  1 Introduction

Recently reinforcement learning (RL), including single agent RL and multi-
agent RL (MARL), has received significant research interests, partly due to
its many applications in a variety of scenarios such as the autonomous
driving, traffic signal control, cooperative robotics, economic policy-making,
and video games [1, 2, 3, 4, 5, 6, 7, 8]. In MARL, at each state, each agent
takes its own action, and these actions jointly determine the next state of
the environment and the reward of each agent. The rewards may vary for
different agents. In this paper, we focus on the model of Markov Games (MG)
[9]. In this class of problems, researchers typically consider learning
objectives such as Nash equilibrium (NE), correlated equilibrium (CE) and
coarse correlated equilibrium (CCE) etc. A recent line of works provide non-
asymptotic guarantees for learning NE, CCE or CE under different assumptions
[10, 11, 12, 13, 14, 15, 16].

As RL models, including single agent RL and MARL, are being increasingly used
in safety critical and security related applications, it is critical to
developing trustworthy RL systems. As a first step towards this important
goal, it is essential to understand the effects of adversarial attacks on RL
systems. Motivated by this, there have been many recent works that investigate
adversarial attacks on single agent RL under various settings [17, 18, 19, 20,
21, 22, 23].

On the other hand, except the ones that will be reviewed below, existing work
on adversarial attacks on MARL is limited. In this paper, we aim to fill in
this gap and systematically investigate the impact of adversarial attacks on
online MARL. We consider a setting in which there is an attacker sits between
the agents and the environment, and can monitor the states, the actions of the
agents and the reward signals from the environment. The attacker is able to
manipulate the feedback or action of the agents. The objective of the MARL
learner is to learn an equilibrium. The attacker’s goal is to force the agents
to learn a target policy or to maximize the cumulative rewards under some
specific reward function chosen by the attacker, while minimizing the amount
of the manipulation on feedback and action. Our contributions are follows.

###  1.1 Contributions

1) We propose an adversarial attack model in which the attacker aims to force
the agent to learn a policy selected by the attacker (will be called target
policy in the sequel) or to maximize the cumulative rewards under some
specific reward function chosen by the attacker. We use loss and cost
functions to evaluate the effectiveness of the adversarial attack on MARL
agents. The cost is the cumulative sum of the action manipulations and the
reward manipulations. If the attacker aims to force the agents to learn a
target policy, the loss is the cumulative number of times when the agent does
not follow the target policy. Otherwise, the loss is the regret to the policy
that maximizes the attacker’s rewards. It is clearly of interest to minimize
both the loss and cost.

2) We study the attack problem in three different settings: the white-box, the
gray-box and the black-box settings. In the white-box setting, the attacker
has full information of the underlying environment. In the gray-box setting,
the attacker has no prior information about the underlying environment and the
agents’ algorithm, but knows the target policy that maximizes its cumulative
rewards. In the black-box setting, the target policy is also unknown for the
attacker.

3) We show that the effectiveness of action poisoning only attacks and reward
poisoning only attacks is limited. Even in the white-box setting, we show that
there exist some MGs under which no action poisoning only Markov attack
strategy or reward poisoning only Markov attack strategy can be efficient and
successful. At the same time, we provide some sufficient conditions under
which the action poisoning only attacks or the reward poisoning only attacks
can efficiently attack MARL algorithms. Under such conditions, we introduce an
efficient action poisoning attack strategy and an efficient reward poisoning
attack strategy, and analyze their cost and loss.

4) We introduce a mixed attack strategy in the gray-box setting and an
approximate mixed attack strategy in the black-box setting. We show that the
mixed attack strategy can force any sub-linear-regret MARL agents to choose
actions according to the target policy specified by the attacker with sub-
linear cost and sub-linear loss. We further investigate the impact of the
approximate mixed attack strategy attack on V-learning [15], a simple,
efficient, decentralized algorithm for MARL.

###  1.2 Related works

Attacks on Single Agent RL: Adversarial attacks on single agent RL have been
studied in various settings [17, 18, 19, 20, 21, 22, 23]. For example, [17,
20, 24] study online reward poisoning attacks in which the attacker could
manipulate the reward signal before the agent receives it. [25] studies online
action poisoning attacks in which the attacker could manipulate the action
signal before the environment receives it. [24] studies the limitations of
reward only manipulation or action only manipulation in single-agent RL.

Attacks on MARL: [26] considers a game redesign problem where the designer
knows the full information of the game and can redesign the reward functions.
The proposed redesign methods can incentivize players to take a specific
target action profile frequently with a small cumulative design cost. [27, 28]
study the poisoning attack on multi-agent reinforcement learners, assuming
that the attacker controls one of the learners. [29] studies the reward
poisoning attack on offline multi-agent reinforcement learners.

Defense Against Attacks on RL: There is also recent work on defending against
adversarial attacks on RL [30, 31, 32, 33, 34, 35]. These work focus on the
single-agent RL setting where an adversary can corrupt the reward and state
transition.

##  2 Problem setup

###  2.1 Definitions

To increase the readability of the paper, we first introduce some standard
definitions related to MARL that will be used throughout of the paper. These
definitions mostly follow those defined in [15]. We denote a tabular episodic
MG with $m$ agents by a tuple
$\text{MG}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$,
where $\mathcal{S}$ is the state space with $|\mathcal{S}|=S$,
$\mathcal{A}_{i}$ is the action space for the $i^{\text{th}}$ agent with
$|\mathcal{A}_{i}|=A_{i}$, $H\in\mathbb{Z}^{+}$ is the number of steps in each
episode. We let $\bm{a}:=(a_{1},\cdots,a_{m})$ denote the joint action of all
the $m$ agents and
$\mathcal{A}:=\mathcal{A}_{i}\times\dots\times\mathcal{A}_{m}$ denote the
joint action space. $P=\\{P_{h}\\}_{h\in[H]}$ is a collection of transition
matrices.
$P_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is the
probability transition function that maps state-action-state pair to a
probability, $R_{i,h}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ represents
the reward function for the $i^{\text{th}}$ agent in the step $h$. In this
paper, the probability transition functions and the reward functions can be
different at different steps. We note that this MG model incorporates both
cooperation and competition because the reward functions of different agents
can be arbitrary.

Interaction protocol: The agents interact with the environment in a sequence
of episodes. The total number of episodes is $K$. In each episode $k\in[K]$ of
MG, the initial states $s_{1}$ is generated randomly by a distribution
$P_{0}(\cdot)$. Initial states may be different between episodes. At each step
$h\in[H]$ of an episode, each agent $i$ observes the state $s_{h}$ and chooses
an action $a_{i,h}$ simultaneously. After receiving the action, the
environment generates a random reward $r_{i,h}\in[0,1]$ for each agent $i$
derived from a distribution with mean $R_{i,h}(s_{h},\bm{a}_{h})$, and
transits to the next state $s_{h+1}$ drawn from the distribution
$P_{h}(\cdot|s_{h},\bm{a}_{h})$. $P_{h}(\cdot|s,\bm{a})$ represents the
probability distribution over states if joint action $\bm{a}$ is taken for
state $s$. The agent stops interacting with environment after $H$ steps and
starts another episode. At each time step, the agents may observe the actions
played by other agents.

Policy and value function: A Markov policy takes actions only based on the
current state. The policy $\pi_{i,h}$ of agent $i$ at step $h$ is expressed as
a mappings ${\pi_{i,h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}_{i}}}$.
$\pi_{i,h}(a_{i}|s)$ represents the probability of agent $i$ taking action
$a_{i}$ in state $s$ under policy $\pi_{i}$ at step $h$. A deterministic
policy is a policy that maps each state to a particular action. For notation
convenience, for a deterministic policy $\pi_{i}$, we use $\pi_{i,h}(s)$ to
denote the action $a_{i}$ which satisfies $\pi_{i,h}(a_{i}|s)=1$. We denote
the product policy of all the agents as
$\pi:=\pi_{1}\times\dots\times\pi_{m}$. We also denote
$\pi_{-i}:=\pi_{1}\times\dots\times\pi_{i-1}\times\pi_{i+1}\times\dots\times\pi_{m}$
to be the product policy excluding agent $i$. If every agent follows a
deterministic policy, the product policy of all the agents is also
deterministic. We use $V_{i,h}^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$ to
denote the value function of agent $i$ at step $h$ under policy $\pi$ and
define
$V_{i,h}^{\pi}(s):=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}r_{i,h^{\prime}}|s_{h}=s,\pi\right]$.
Given a policy $\pi$ and step $h$, the $i^{\text{th}}$ agent’s $Q$-function
$Q_{i,h}^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ of a state-
action pair $(s,\bm{a})$ is defined as:
$Q_{i,h}^{\pi}(s,\bm{a})=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}r_{i,h^{\prime}}|s_{h}=s,\bm{a}_{h}=\bm{a},\pi\right]$.

Best response: For any policy $\pi_{-i}$, there exists a best response of
agent $i$, which is a policy that achieves the highest cumulative reward for
itself if all other agents follow policy $\pi_{-i}$. We define the best
response of agent $i$ towards policy $\pi_{-i}$ as $\mu^{\dagger}(\pi_{-i})$,
which satisfies
$\mu^{\dagger}(\pi_{-i}):=\operatorname*{arg\,max}_{\pi_{i}}V_{i,h}^{\pi_{i}\times\pi_{-i}}(s)$
for any state $s$ and any step $h$. We denote
$\max_{\pi_{i}}V_{i,h}^{\pi_{i}\times\pi_{-i}}(s)$ as
$V_{i,h}^{{\dagger},\pi_{-i}}(s)$ for notation simplicity. By its definition,
we know that the best response can always be achieved by a deterministic
policy.

Nash Equilibrium (NE) is defined as a product policy where no agent can
improve his own cumulative reward by unilaterally changing his strategy.

Nash Equilibrium (NE) [15]: A product policy $\pi$ is a NE if for all initial
state $s$,
$\max_{i\in[m]}(V_{i,1}^{{\dagger},\pi_{-i}}(s)-V_{i,1}^{\pi}(s))=0$ holds. A
product policy $\pi$ is an $\epsilon$-approximate Nash Equilibrium if for all
initial state $s$,
$\max_{i\in[m]}(V_{i,1}^{{\dagger},\pi_{-i}}(s)-V_{i,1}^{\pi}(s))\leq\epsilon$
holds.

General correlated policy: A general Markov correlated policy $\pi$ is a set
of $H$ mappings
$\pi:=\\{\pi_{h}:\Omega\times\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\\}_{h\in[H]}$.
The first argument of $\pi_{h}$ is a random variable $\omega\in\Omega$ sampled
from some underlying distributions. For any correlated policy
$\pi=\\{\pi_{h}\\}_{h\in[H]}$ and any agent $i$, we can define a marginal
policy $\pi_{-i}$ as a set of $H$ maps
$\pi_{i}=\\{\pi_{h,-i}:\Omega\times\mathcal{S}\rightarrow\Delta_{\mathcal{A}_{-i}}\\}_{h\in[H]}$,
where
$\mathcal{A}_{-i}=\mathcal{A}_{1}\times\dots\times\mathcal{A}_{i-1}\times\mathcal{A}_{i+1}\times\dots\times\mathcal{A}_{m}$.
It is easy to verify that a deterministic joint policy is a product policy.
The best response value of agent $i$ towards policy $\pi_{-i}$ as
$\mu^{\dagger}(\pi_{-i})$, which satisfies
$\mu^{\dagger}(\pi_{-i}):=\operatorname*{arg\,max}_{\pi_{i}}V_{i,h}^{\pi_{i}\times\pi_{-i}}(s)$
for any state $s$ and any step $h$.

Coarse Correlated Equilibrium (CCE)[15]: A correlated policy $\pi$ is an CCE
if for all initial state $s$,
$\max_{i\in[m]}(V_{i,1}^{{\dagger},\pi_{-i}}(s)-V_{i,1}^{\pi}(s))=0$ holds. A
correlated policy $\pi$ is an $\epsilon$-approximate CCE if for all initial
state $s$,
$\max_{i\in[m]}(V_{i,1}^{{\dagger},\pi_{-i}}(s)-V_{i,1}^{\pi}(s))\leq\epsilon$
holds.

Strategy modification: A strategy modification $\phi_{i}$ for agent $i$ is a
set of mappings
$\phi_{i}:=\\{(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\times\mathcal{A}_{i}\rightarrow\mathcal{A}_{i}\\}_{h\in[H]}$.
For any policy $\pi_{i}$, the modified policy (denoted as
$\phi_{i}\diamond\pi_{i}$) changes the action $\pi_{i,h}(\omega,s)$ under
random sample $\omega$ and state $s$ to
$\phi_{i}((s_{1},\bm{a}_{1},\dots,s_{h},a_{i,h}),\pi_{i,h}(\omega,s))$. For
any joint policy $\pi$, we define the best strategy modification of agent $i$
as the maximizer of
$\max_{\phi_{i}}V^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}_{i,1}(s)$ for any
initial state $s$.

Correlated Equilibrium (CE)[15]: A correlated policy $\pi$ is an CE if for all
initial state $s$,
$\max_{i\in[m]}\max_{\phi_{i}}(V_{i,1}^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}(s)-V_{i,1}^{\pi}(s))=0$.
A correlated policy $\pi$ is an $\epsilon$-approximate CE if for all initial
state $s$,
$\max_{i\in[m]}\max_{\phi_{i}}(V_{i,1}^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}(s)-V_{i,1}^{\pi}(s))\leq\epsilon$
holds.

In Markov games, it is known that an NE is an CE, and an CE is an CCE.

Best-in-hindsight Regret: Let $\pi^{k}$ denote the product policy deployed by
the agents for each episode $k$. After $K$ episodes, the best-in-hindsight
regret of agent $i$ is defined as
$\text{Reg}_{i}(K,H)=\max\nolimits_{\pi_{i}^{\prime}}\sum\nolimits_{k=1}^{K}[V_{i,1}^{\pi_{i}^{\prime},\pi^{k}_{-i}}(s_{1}^{k})-V_{i,1}^{\pi^{k}}(s_{1}^{k})]$.

###  2.2 Poisoning attack setting

We are now ready to introduce the considered poisoning attack setting, in
which there is an attacker sits between the agents and the environment. The
attacker can monitor the states, the actions of the agents and the reward
signals from the environment. Furthermore, the attacker can override actions
and observations of agents. In particular, at each episode $k$ and step $h$,
after each agent $i$ chooses an action $a_{i,h}^{k}$, the attacker may change
it to another action $\widetilde{a}_{i,h}^{k}\in\mathcal{A}_{i}$. If the
attacker does not override the actions, then $\widetilde{a}_{i,h}^{k}=a_{i}$.
When the environment receives $\widetilde{\bm{a}}_{h}^{k}$, it generates
random rewards $r_{i,h}^{k}$ with mean
$R_{i,h}(s_{h}^{k},\widetilde{\bm{a}}_{h}^{k})$ for each agent $i$ and the
next state $s_{h+1}^{k}$ is drawn from the distribution
$P_{h}(\cdot|s_{h}^{k},\widetilde{\bm{a}}_{h}^{k})$. Before each agent $i$
receives the reward $r_{i,h}^{k}$, the attacker may change it to another
reward $\widetilde{r}_{i,h}^{k}$. Agent $i$ receives the reward
$\widetilde{r}_{i,h}^{k}$ and the next state $s_{h+1}^{k}$ from the
environment. Note that agent $i$ does not know the attacker’s manipulations
and the presence of the attacker and hence will still view
$\widetilde{r}_{i,h}^{k}$ as the reward and $s_{h+1}^{k}$ as the next state
generated from state-action pair $(s_{h}^{k},\bm{a}_{h}^{k})$.

In this paper, we call an attack as _action poisoning only attack_ , if the
attacker only overrides the action but not the rewards. We call an attack as
_reward poisoning only attack_ if the attacker only overrides the rewards but
not the actions. In addition, we call an attack as _mixed attack_ if the
attack can carry out both action poisoning and reward poisoning attacks
simultaneously.

The goal of the MARL learners is to learn an equilibrium. On the other hand,
the attacker’s goal is to either force the agents to learn a target policy
$\pi^{\dagger}$ of the attacker’s choice or to force the agents to learn a
policy that maximizes the cumulative rewards under a specific reward function
$R_{{\dagger},h}:\mathcal{S}\times\mathcal{A}\rightarrow(0,1]$ chosen by the
attacker. We note that this setup is very general. Different choices of
$\pi^{\dagger}$ or $R_{{\dagger},h}$ could lead to different objectives. For
example, if the attacker aims to reduce the benefit of the agent $i$, the
attacker’s reward function $R_{{\dagger},h}$ can be set to $1-R_{i,h}$, or
choose a target policy $\pi^{\dagger}$ that is detrimental to the agent $i$’s
reward. If the attacker aims to maximize the total rewards of a subset of
agents $\mathcal{C}$, the attacker’s reward function $R_{{\dagger},h}$ can be
set to $\sum_{i\in\mathcal{C}}R_{i,h}$, or choose a target policy
$\pi^{\dagger}=\operatorname*{arg\,max}\sum_{i\in\mathcal{C}}V_{i,1}^{\pi}(s_{1})$
that maximizes the total rewards of agents in $\mathcal{C}$. We assume that
the target policy $\pi^{\dagger}$ is deterministic and
$R_{i,h}(s,\pi^{\dagger}(s))>0$. We measure the performance of the attack over
$K$ episodes by the total attack cost and the attack loss. Set
$\mathbbm{1}(\cdot)$ as the indicator function. The attack cost over $K$
episodes is defined as
$\text{Cost}(K,H)=\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\left(\mathbbm{1}(\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k})+|\widetilde{r}_{i,h}^{k}-r_{i,h}^{k}|\right)$.

There are two different forms of attack loss based on the different goals of
the attacker.

If the attacker’s goal is to force the agents to learn a target policy
$\pi^{\dagger}$, the attack loss over $K$ episodes is defined as
$\text{Loss1}(K,H)=\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}\left({a}_{i,h}^{k}\neq\pi_{i,h}^{\dagger}(s_{i,h}^{k})\right)$.

If the attacker’s goal is to force the agents to maximize the cumulative
rewards under some specific reward function $R_{\dagger}$ chosen by the
attacker, the attack loss over $K$ episodes is defined as
$\text{Loss2}(K,H)=\sum_{k=1}^{K}[V_{{\dagger},1}^{\pi^{*}}(s_{1}^{k})-V_{{\dagger},1}^{\pi^{k}}(s_{1}^{k})]$.
Here, $V_{{\dagger},1}^{\pi}(s)$ is the expected cumulative rewards in state
$s$ based on the attacker’s reward function $R_{\dagger}$ under product policy
$\pi$ and $V_{{\dagger},1}^{\pi^{*}}(s)=\max_{\pi}V_{{\dagger},1}^{\pi}(s)$.
$\pi^{k}$ denote the product policy deployed by the agents for each episode
$k$. $\pi^{*}$ is the optimal policy that maximizes the attacker’s cumulative
rewards. We have $\text{Loss2}(K,H)\leq H*\text{Loss1}(K,H)$.

Denote the total number of steps as $T=KH$. In the proposed poisoning attack
problem, we call an attack strategy _successful_ if the attack loss of the
strategy scales as $o(T)$. Furthermore, we call an attack strategy _efficient
and successful_ if both the attack cost and attack loss scale as $o(T)$.

The attacker aims to minimize both the attack cost and the attack loss, or
minimize one of them subject to a constraint on the other. However, obtaining
optimal solutions to these optimization problems is challenging. As the first
step towards understanding the attack problem, we show the limitations of the
action poisoning only or the reward poisoning only attacks and then propose a
simple mixed attack strategy that is efficient and successful.

Depending on the capability of the attacker, we consider three settings: the
white-box, the gray-box and the black-box settings. The table below summarizes
the differences among these settings.

Table 1: Differences of the white/gray/black-box attackers | white-box attacker | gray-box attacker | black-box attacker
---|---|---|---
MG | Has full information | No information | No information
$\pi^{\dagger}$ |  Can be calculated if $R_{\dagger}$ given | Required and given | Not given
$R_{\dagger}$ |  Not required if $\pi^{\dagger}$ given |  Not required if $\pi^{\dagger}$ given | Required and given
Loss1 |  Suitable by specify $\pi^{\dagger}$ | Suitable | Not suitable
Loss2 |  Suitable if $R_{\dagger}$ given |  Suitable if $R_{\dagger}$ given | Suitable

##  3 White-box attack strategy and analysis

In this section, to obtain insights to the problem, we consider the white-box
model, in which the attacker has full information of the underlying MG
$(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$.
Even in the white-box attack model, we show that there exist some environments
where the attacker’s goal cannot be achieved by reward poisoning only attacks
or action poisoning only attacks in Section 3.1. Then, in Section 3.2 and
Section 3.3, we provide some sufficient conditions under which the action
poisoning attacks alone or the reward poisoning attacks alone can efficiently
attack MARL algorithms. Under such conditions, we then introduce an efficient
action poisoning attack strategy and an efficient reward poisoning attack
strategy.

###  3.1 The limitations of the action poisoning attacks and the reward
poisoning attacks

As discussed in Section 2, the attacker aims to force the agents to either
follow the target policy $\pi^{\dagger}$ or to maximize the cumulative rewards
under attacker’s reward function $R_{\dagger}$. In the white-box poisoning
attack model, these two goals are equivalent as the optimal policy $\pi^{*}$
on the attacker’s reward function $R_{\dagger}$ can be calculated by the
Bellman optimality equations. To maximize the cumulative rewards under
attacker’s reward function $R_{\dagger}$ is equivalent to force the agents
follow the policy $\pi^{\dagger}=\pi^{*}$.

Existing MARL algorithms [14, 15] can learn an $\epsilon$-approximate {NE, CE,
CCE} with $\widetilde{\mathcal{O}}(1/\epsilon^{2})$ sample complexities. To
force the MARL agents to follow the policy $\pi^{\dagger}$, the attacker first
needs to attack the agents such that the target policy $\pi^{\dagger}$ is the
unique NE in the observation of the agents. However, this alone is not enough
to force the MARL agents to follow the policy $\pi^{\dagger}$. Any other
distinct policy should not be an $\epsilon$-approximate CCE. The reason is
that, if there exists an $\epsilon$-approximate CCE $\pi$ such that
$\pi(\pi^{\dagger}(s)|s)=0$ for any state $s$, the agents, using existing MARL
algorithms, may learn and then follow $\pi$, which will lead the attack loss
to be $\mathcal{O}(T)=\mathcal{O}(KH)$. Hence, we need to ensure that any
$\epsilon$-approximate CCE stays in the neighborhood of the target policy.
This requirement is equivalent to achieve the following objective: for all
$s\in\mathcal{S}$, and policy $\pi$,

$\begin{split}&\max_{i\in[m]}(\widetilde{V}_{i,1}^{{\dagger},\pi^{\dagger}_{-i}}(s)-\widetilde{V}_{i,1}^{\pi^{\dagger}}(s))=0;\\\
&\text{if~{}}\pi\text{~{}is~{}a~{}product~{}policy~{}and~{}}\pi\neq\pi^{\dagger},\text{then~{}}\max_{i\in[m]}(\widetilde{V}_{i,1}^{{\dagger},\pi_{-i}}(s)-\widetilde{V}_{i,1}^{\pi}(s))>0;\\\
&\text{if~{}}\pi(\pi^{\dagger}(s^{\prime})|s^{\prime})=0\text{~{}for~{}all~{}}s^{\prime},\text{then~{}}\max_{i\in[m]}(\widetilde{V}_{i,1}^{{\dagger},\pi_{-i}}(s)-\widetilde{V}_{i,1}^{\pi}(s))>\epsilon,\end{split}$
(1)

where $\widetilde{V}$ is the expected reward based on the post-attack
environments.

We now investigate whether there exist efficient and successful attack
strategies that use action poisoning alone or reward poisoning alone. We first
show that the power of action poisoning attack alone is limited.

###### Theorem 1

There exists a target policy $\pi^{\dagger}$ and a MG
$(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$ such
that no action poisoning Markov attack strategy alone can efficiently and
successfully attack MARL agents by achieving the objective in (1).

We now focus on strategies that use only reward poisoning. If the post-attack
mean reward $\widetilde{R}$ is unbounded and the attacker can arbitrarily
manipulate the rewards, there always exists an efficient and successful
poisoning attack strategy. For example, the attacker can change the rewards of
non-target actions to $-H$. However, such attacks can be easily detected, as
the boundary of post-attack mean reward is distinct from the boundary of pre-
attack mean reward. The following theorem shows that if the post-attack mean
reward has the same boundary conditions as the pre-attack mean reward, the
power of reward poisoning only attack is limited.

###### Theorem 2

If we limit the post-attack mean reward $\widetilde{R}$ to have the same
boundary condition as that of the pre-attack mean reward $R$, i.e.
$\widetilde{R}\in[0,1]$, there exists a MG
$(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$ and
a target policy $\pi^{\dagger}$ such that no reward poisoning Markov attack
strategy alone can efficiently and successfully attack MARL agents by
achieving the objective in (1).

The proofs of Theorem 1 and Theorem 2 are provided in Appendix C. The main
idea of the proofs is as follows. In successful poisoning attacks, the attack
loss scales as $o(T)$ so that the agents will follow the target policy
$\pi^{\dagger}$ in at least $T-o(T)$ times. To efficiently attack the MARL
agents, the attacker should avoid to attack when the agents follow the target
policy. Otherwise, the poisoning attack cost will grow linearly with $T$. The
proofs of Theorem 1 and Theorem 2 proceed by constructing an MG and a target
policy $\pi^{\dagger}$ where the expected rewards under $\pi^{\dagger}$ is
always the worst for some agents if the attacker avoids to attack when the
agents follow the target policy.

###  3.2 White-box action poisoning attacks

Even though Section 3.1 shows that there exists MG and target policy such that
the action poisoning only attacks cannot be efficiently successful, here we
show that it can be efficient and successful for a class of target policies.
The following condition characterizes such class of target policies.

Condition 1: _For the underlying environment MG
$(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$, the
attacker’s target policy $\pi^{\dagger}$ satisfies that for any state $s$ and
any step $h$, there exists an action $\bm{a}$ such that
$V_{i,h}^{\pi^{\dagger}}(s)>Q_{i,h}^{\pi^{\dagger}}(s,\bm{a}),$ for any agent
$i$._

Under Condition 1, we can find a worse policy $\pi^{-}$ by

$\begin{split}\pi^{-}_{h}(s)=&\operatorname*{arg\,max}_{\bm{a}\in\mathcal{A}}\min_{i\in[m]}\left(V_{i,h}^{\pi^{\dagger}}(s)-Q_{i,h}^{\pi^{\dagger}}(s,\bm{a})\right)~{}s.t.\forall
i\in[m],V_{i,h}^{\pi^{\dagger}}(s)>Q_{i,h}^{\pi^{\dagger}}(s,\bm{a}).\end{split}$
(2)

Under this condition, we now introduce an effective white-box action attack
strategies: $d$-portion attack. Specifically, at the step $h$ and state $s$,
if all agents pick the target action, i.e., $\bm{a}=\pi_{h}^{\dagger}(s)$, the
attacker does not attack, i.e.
$\widetilde{\bm{a}}=\bm{a}=\pi_{h}^{\dagger}(s)$. If some agents pick a non-
target action, i.e., $\bm{a}\neq\pi_{h}^{\dagger}(s)$, the $d$-portion attack
sets $\widetilde{\bm{a}}$ as

$\widetilde{\bm{a}}=\left\\{\begin{aligned} &\pi_{h}^{\dagger}(s),\text{with
probability }d_{h}(s,\bm{a})/m\\\ &\pi^{-}_{h}(s),\text{with probability
}1-d_{h}(s,\bm{a})/m,\end{aligned}\right.$ (3)

where
$d_{h}(s,\bm{a})=m/2+\sum_{i=1}^{m}\mathbbm{1}(a_{i}=\pi_{i,h}^{\dagger}(s))/2$.

###### Theorem 3

If the attacker follows the $d$-portion attack strategy on the MG agents, the
best response of each agent $i$ towards the target policy $\pi_{-i}^{\dagger}$
is $\pi_{i}^{\dagger}$. The target policy $\pi^{\dagger}$ is an {NE, CE, CCE}
from any agent’s point of view. If every state $s\in\mathcal{S}$ is reachable
at every step $h\in[H]$ under the target policy, $\pi^{\dagger}$ is the unique
{NE, CE, CCE}.

The detailed proof can be found in Appendix D.1. Theorem 3 shows that the
target policy $\pi^{\dagger}$ is the unique {NE, CE, CCE} under the
$d$-portion attack. Thus, if the agents follow an MARL algorithm that is able
to learn an $\epsilon$-approximate {NE, CE, CCE}, the agents will learn a
policy approximate to the target policy. We now discuss the high-level idea
why the $d$-portion attack works. Under Condition 1, $\pi^{-}$ is worse than
the target policy $\pi^{\dagger}$ at the step $H$ from every agent’s point of
view. Thus, under the $d$-portion attack, the target action strictly dominates
any other action at the step $H$, and $\pi^{\dagger}$ is the unique {NE, CE,
CCE} at the step $H$. From induction on $h=H,H-1,\cdots,1$, we can further
prove that the $\pi^{\dagger}$ is the unique {NE, CE, CCE} at any step $h$. We
define
$\Delta^{{\dagger}-}_{i,h}(s)=Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))$
and the minimum gap
$\Delta_{min}=\min_{h\in[H],s\in\mathcal{S},i\in[m]}=\Delta^{{\dagger}-}_{i,h}(s)$.
In addition, any other distinct policy is not an $\epsilon$-approximate CCE
with different gap $\epsilon<\Delta_{min}/2$. We can derive upper bounds of
the attack loss and the attack cost when attacking some special MARL
algorithms.

###### Theorem 4

If the best-in-hindsight regret $\text{Reg}(K,H)$ of each agent’s algorithm is
bounded by a sub-linear bound $\mathcal{R}(T)$ for any MG in the absence of
attack, and
$\min_{s\in\mathcal{S},i\in[m]}\Delta^{{\dagger}-}_{i,h}(s)\geq\sum_{h^{\prime}=h+1}^{H}\max_{s\in\mathcal{S},i\in[m]}\Delta^{{\dagger}-}_{i,h^{\prime}}(s)$
holds for any $h\in[H]$, then $d$-portion attack will force the agents to
follow the target policy with the attack loss and the attack cost bounded by

$\begin{split}&\mathbbm{E}[\text{Loss1}(K,H)]\leq
2m^{2}\mathcal{R}(T)/\Delta_{min},~{}\mathbbm{E}[\text{Cost}(K,H)]\leq
2m^{3}\mathcal{R}(T)/\Delta_{min}.\end{split}$ (4)

###  3.3 White-box reward poisoning attacks

As stated in Theorem 2, the reward poisoning only attacks may fail, if we
limit the post-attack mean reward $\widetilde{R}$ to satisfy the same boundary
conditions as those of the pre-attack mean reward $R$, i.e.
$\widetilde{R}\in[0,1]$. However, similar to the case with action poisoning
only attacks, the reward poisoning only attacks can be efficiently successful
for a class of target policies. The following condition specifies such class
of target policies.

Condition 2: _For the underlying environment MG
$(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$,
there exists constant $\eta>0$ such that for any state $s$, any step $h$, and
any agent $i$, $(R_{i,h}(s,\pi^{\dagger}(s))-\eta)/(H-h)\geq\Delta_{R}>0$
where $\Delta_{R}=[\max_{s\times a\times
h^{\prime}}R_{i,h^{\prime}}(s,a)-\min_{s\times a\times
h^{\prime}}R_{i,h^{\prime}}(s,a)]$._

We now introduce an effective white-box reward attack strategies: $\eta$-gap
attack. Specifically, at the step $h$ and state $s$, if agents all pick the
target action, i.e., $\bm{a}=\pi_{h}^{\dagger}(s)$, the attacker does not
attack, i.e. $\widetilde{r}_{i,h}=r_{i,h}$ for each agent $i$. If agent $i$
picks a non-target action, i.e., $\bm{a}\neq\pi_{h}^{\dagger}(s)$, the
$\eta$-gap attack sets
$\widetilde{r}_{i,h}=R_{i,h}(s,\pi^{\dagger}(s))-(\eta+(H-h)\Delta_{R})\mathbbm{1}(a_{i}\neq\pi_{i,h}^{\dagger}(s))$
for each agent $i$. From Condition 2, we have $\widetilde{r}_{i,h}\in[0,1]$.

###### Theorem 5

If the attacker follows the $\eta$-gap attack strategy on the MG agents, the
best response of each agent $i$ towards any policy $\pi_{-i}$ is
$\pi_{i}^{\dagger}$. The target policy $\pi^{\dagger}$ is the {NE, CE, CCE}
from any agent’s point of view. If every state $s\in\mathcal{S}$ is reachable
at every step $h\in[H]$ under the target policy, $\pi^{\dagger}$ is the unique
{NE, CE, CCE}.

The detailed proof can be found in Appendix E.1. Theorem 5 shows that the
target policy $\pi^{\dagger}$ is the unique {NE, CE, CCE} under the $\eta$-gap
attack. Thus, if the agents follow an MARL algorithm that is able to learn an
$\epsilon$-approximate {NE, CE, CCE}, the agents will learn a policy
approximate to the target policy. Here, we discuss the high-level idea why the
$\eta$-gap attack works. $\Delta_{R}$ is the difference between the upper
bound and the lower bound of the mean rewards. Condition 2 implies that each
action is close to other actions from every agent’s point of view. Although we
limit the post-attack mean reward $\widetilde{R}$ in $[0,1]$, the target
policy can still appear to be optimal by making small changing to the rewards.
Under Condition 2 and the $\eta$-gap attacks, the target actions strictly
dominates any other non-target actions by at least $\eta$ and any other
distinct policy is not an $\epsilon$-approximate CCE with different gap
$\epsilon<\eta$. Thus, $\pi^{\dagger}$ becomes the unique {NE, CE, CCE}. In
addition, we can derive upper bounds of the attack loss and the attack cost
when attacking MARL algorithms with sub-linear best-in-hindsight regret.

###### Theorem 6

If the best-in-hindsight regret $\text{Reg}(K,H)$ of each agent’s algorithm is
bounded by a sub-linear bound $\mathcal{R}(T)$ for any MG in the absence of
attack, then $\eta$-gap attack will force the agents to follow the target
policy with the attack loss and the attack cost bounded by

$\begin{split}&\mathbbm{E}[\text{Loss1}(k,H)]\leq
m\mathcal{R}(T)/\eta,~{}\mathbbm{E}[\text{Cost}(K,H)]\leq
m^{2}\mathcal{R}(T)/\eta.\end{split}$ (5)

We note that proposed sufficient conditions (namely Condition 1 and Condition
2), under which the action poisoning only attacks or the reward poisoning only
attacks can be efficient and successful, may be strict. They may not always
hold in practice. This motivates us to investigate mixed attack strategy to be
discussed in the sequel.

##  4 Gray-box attack strategy and analysis

In the gray-box attack setting, the attacker has no prior information about
the underlying environment and the agents’ algorithm, and it only observes
samples generated when the agents interact with the environment. However, the
attacker is given the target policy $\pi^{\dagger}$. Since the $\eta$-gap
reward attack strategy and $d$-portion action attack strategy described in
Section 3 for the white-box setting rely on the information of the underlying
environment, these two attack strategies are not applicable in the gray-box
setting. In addition, without the information of the underlying environment,
the attacker cannot check whether the action poisoning attack alone or the
reward poisoning attack alone can be efficiently successful. Building on
insights obtained from the white-box attack strategies, we develop a mixed
attack strategy for MG in the gray-box attack setting.

In the proposed mixed attack strategy, at the step $h$ and state $s$, if agent
$i$ picks the target action, i.e., ${a}_{i,h}=\pi_{i,h}^{\dagger}(s)$, the
attacker does not override the action and the reward, i.e.
$\widetilde{a}_{i,h}=a_{i,h}$ and $\widetilde{r}_{i,h}=r_{i,h}$. If agent $i$
picks a non-target action, i.e., $a_{i,h}\neq\pi_{i,h}^{\dagger}(s)$, the
attacker overrides its action $\widetilde{a}_{i,h}=\pi_{i,h}^{\dagger}(s)$ and
then overrides the reward $\widetilde{r}_{i,h}=0$.

###### Theorem 7

If the attacker follows the mixed attack strategy the best response of each
agent $i$ towards any product policy $\pi_{-i}$ is $\pi_{i}^{\dagger}$. The
optimal policy $\pi^{\dagger}$ is the unique {NE, CE, CCE}.

The detailed proof can be found in Appendix F.1. Here, we discuss the high-
level idea why the mixed attack works. Under the mixed attacks, the state
transitions are the same over the different actions and the reward of the non-
target actions is worse than the target action. Thus, in the post-attack
environment, the target policy is better than any other policy from any
agent’s point of view, and any other distinct policy is not an
$\epsilon$-approximate CCE with different gap $\epsilon<R_{min}$, where
$R_{min}=\min_{h\in[H]}\min_{s\in\mathcal{S}}\min_{i\in[m]}R_{i,h}(s,\pi^{\dagger}_{h}(s))$.
Thus, $\pi^{\dagger}$ is the unique {NE, CE, CCE}. In addition, we can derive
upper bounds of the attack loss and the attack cost when attacking some
special MARL algorithms.

###### Theorem 8

If the best-in-hindsight regret $\text{Reg}(K,H)$ of each agent’s algorithm is
bounded by a sub-linear bound $\mathcal{R}(T)$ for any MG in the absence of
attacks, then the mixed attacks will force the agents to follow the target
policy $\pi^{\dagger}$ with the attack loss and the attack cost bounded by

$\begin{split}&\mathbbm{E}[\text{Loss1}(K,H)]\leq
m\mathcal{R}(T)/R_{min},~{}\mathbbm{E}[\text{Cost}(K,H)]\leq
2m\mathcal{R}(T)/R_{min}.\end{split}$ (6)

##  5 Black-box attack strategy and analysis

In the black-box attack setting, the attacker has no prior information about
the underlying environment and the agents’ algorithm, and it only observes the
samples generated when the agents interact with the environment. The attacker
aims to maximize the cumulative rewards under some specific reward functions
$R_{\dagger}$ chosen by the attacker. But unlike in the gray-box case, the
corresponding target policy $\pi^{\dagger}$ is also unknown for the attacker.
After each time step, the attacker will receive the attacker reward
$r_{\dagger}$. Since the optimal (target) policy that maximizes the attacker’s
reward is unknown, the attacker needs to explore the environment to obtain the
optimal policy. As the mixed attack strategy described in Section 4 for the
gray-box setting relies on the knowledge of the target policy, it is not
applicable in the black-box setting.

However, by collecting observations and evaluating the attacker’s reward
function and transition probabilities of the underlying environment, the
attacker can perform an approximate mixed attack strategy. In particular, we
propose an approximate mixed attack strategy that has two phases: the
exploration phase and the attack phase. In the exploration phase, the attacker
explores the environment to identify an approximate optimal policy, while in
the attack phase, the attacker performs the mixed attack strategy and forces
the agents to learn the approximate optimal policy. The total attack cost
(loss) will be the sum of attack cost (loss) of these two phases.

0: Stopping time $\tau$. Set
$B(N)=(H\sqrt{S}+1)\sqrt{\log(2AH\tau/\delta)/(2N)}$.

1: Initialize
$\overline{Q}_{{\dagger},h}(s,\bm{a})=\overline{V}_{{\dagger},h}(s,\bm{a})=H$,
$\underline{Q}_{{\dagger},h}(s,\bm{a})=\underline{V}_{{\dagger},h}(s,\bm{a})=0$,
$\overline{V}_{{\dagger},H+1}=\underline{V}_{{\dagger},H+1}=\bm{0}$,
$\Delta=\infty$, $N_{0}(s)=N_{h}(s,\bm{a})=N_{h}(s,\bm{a},s^{\prime})=0$ and
$\hat{R}_{{\dagger},h}(s,\bm{a})=0$ for any $(s,s^{\prime},\bm{a},i,h)$.

2: for episode $k=1,\dots,\tau$ do

3: for step $h=H,\dots,1$ do

4: for each $(s,\bm{a})\in\mathcal{S}\times\mathcal{A}$ with
$N_{h}(s,\bm{a})>0$ do

5: Update
$\overline{Q}_{{\dagger},h}(s,\bm{a})=\min\\{\hat{R}_{{\dagger},h}+\hat{\mathbbm{P}}_{h}\overline{V}_{{\dagger},h+1}(s,\bm{a})+B(N_{h}(s,\bm{a})),H\\}$
and
$\underline{Q}_{{\dagger},h}(s,\bm{a})=\max\\{\hat{R}_{{\dagger},h}+\hat{\mathbbm{P}}_{h}\underline{V}_{{\dagger},h+1}(s,\bm{a})-B(N_{h}(s,\bm{a})),0\\}$.

6: end for

7: for each $s\in\mathcal{S}$ with $N_{h}(s,\bm{a})>0$ do

8: Update
$\pi_{h}(s)=\max_{\bm{a}\in\mathcal{A}}\overline{Q}_{{\dagger},h}(s,\bm{a})$.

9: Update
$\overline{V}_{{\dagger},h}(s,\bm{a})=\overline{Q}_{{\dagger},h}(s,\pi_{h}(s))$
and
$\underline{V}_{{\dagger},h}(s,\bm{a})=\underline{Q}_{{\dagger},h}(s,\pi_{h}(s))$.

10: end for

11: end for

12: if
$\mathbb{E}_{s\sim\hat{\mathbbm{P}}_{0}(\cdot)}(\overline{V}_{{\dagger},1}(s)-\underline{V}_{{\dagger},1}(s))+H\sqrt{\frac{S\log(2\tau/\delta)}{2k}}\leq\Delta$
then

13:
$\Delta=\mathbb{E}_{s\sim\hat{\mathbbm{P}}_{0}(\cdot)}(\overline{V}_{{\dagger},1}(s)-\underline{V}_{{\dagger},1}(s))+H\sqrt{\frac{S\log(2\tau/\delta)}{2k}}$
and $\pi^{\dagger}=\pi$.

14: end if

15: for step $h=1,\dots,H$ do

16: Attacker overrides each agent’s action by changing $a_{i,h}$ to
$\widetilde{a}_{i,h}$, where $\widetilde{\bm{a}}_{h}=\pi_{h}(s_{h})$.

17: The environment returns the reward $r_{i,h}$ and the next state $s_{h+1}$
according to action $\widetilde{\bm{a}}_{h}$. The attacker receive its reward
$r_{{\dagger},h}$.

18: Attacker overrides each agent’s reward by changing $r_{i,h}$ to
$\widetilde{r}_{i,h}=1$.

19: Add $1$ to $N_{h}(s_{h},\widetilde{\bm{a}}_{h})$ and
$N_{h}(s_{h},\widetilde{\bm{a}}_{h},s_{h+1})$.
$\hat{\mathbbm{P}}_{h}(\cdot|s_{h},\widetilde{\bm{a}}_{h})=N_{h}(s_{h},\widetilde{\bm{a}}_{h},\cdot)/N_{h}(s_{h},\widetilde{\bm{a}}_{h})$

20: Update
$\hat{R}_{{\dagger},h}(s_{h},\widetilde{\bm{a}}_{h})=\hat{R}_{{\dagger},h}(s_{h},\widetilde{\bm{a}}_{h})+(r_{{\dagger},t}-\hat{R}_{{\dagger},h}(s_{h},\widetilde{\bm{a}}_{h})/N_{h}(s_{h},\widetilde{\bm{a}}_{h})$.

21: end for

22: Update $N_{0}(s_{1})=N_{0}(s_{1})+1$ and
$\hat{\mathbbm{P}}_{0}(\cdot)=N_{0}(\cdot)/k$.

23: end for

24: Return $\pi^{\dagger}$.

Algorithm 1 Exploration phase for Markov games

In the exploration phase, the approximate mixed attack strategy uses an
optimal-policy identification algorithm, which is summarized in Algorithm 1.
It will return an approximate optimal policy $\pi^{\dagger}$. Note that
$\pi^{k}$ denotes the product policy deployed by the agents for each episode
$k$. $\overline{V}$ is the upper bound of ${V}^{\pi^{*}}$ and $\underline{V}$
is the lower bound of ${V}^{\pi^{k}}$. By minimizing
$\overline{V}-\underline{V}$, Algorithm 1 finds an approximate optimal policy
$\pi^{\dagger}$. Here, we assume that the reward on the approximate optimal
policy $\pi^{\dagger}$ is positive, i.e.
$R_{min}=\min_{h\in[H]}\min_{s\in\mathcal{S}}\min_{i\in[m]}R_{i,h}(s,\pi^{\dagger}_{h}(s))>0$.
In the exploration phase, the attacker will override both the agents’ actions
and rewards.

After the exploration phase, the approximate mixed attack strategy performs
the attack phase. The attacker will override both the agents’ actions and
rewards in this phase. At the step $h$ and state $s$, if agent $i$ picks the
action $\pi_{i,h}^{\dagger}(s)$, the attacker does not override actions and
rewards, i.e. $\widetilde{a}_{i,h}=a_{i,h}$ and $\widetilde{r}_{i,h}=r_{i,h}$.
If agent $i$ picks action $a_{i,h}\neq\pi_{i,h}^{\dagger}(s)$, the attacker
overrides the action $\widetilde{a}_{i,h}=a_{i,h}$ and then overrides the
reward $\widetilde{r}_{i,h}=0$. The attack strategy in the attack phase is
same with the mixed attack strategy. From Theorem 7, in the attack phase, the
best response of each agent $i$ towards product policy $\pi_{-i}^{\dagger}$ is
$\pi_{i}^{\dagger}$ and $\pi^{\dagger}$ is the unique NE. Here, we discuss the
high-level idea why the approximate mixed attack works. The attacker finds an
approximate optimal policy $\pi^{\dagger}$ by Algorithm 1. If $\pi^{*}$ is
close to $\pi^{\dagger}$ and the exploration phase is sub-linear time
dependent, the performance of the approximate mixed attack strategy will be
close to the mixed attack strategy. We build a confidence bound to show the
value function difference between $\pi^{*}$ and $\pi^{\dagger}$ in the
following lemma.

###### Lemma 1

If the attacker follows the Algorithm 1 on the agents, for any
$\delta\in(0,1)$, with probability at least $1-5\delta$, the following bound
holds:

$\begin{split}&\mathbbm{E}_{s_{1}\sim
P_{0}(\cdot)}[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{\dagger}}(s_{1})]\leq
2H^{2}S\sqrt{2A\log(2SAH\tau/\delta)/\tau}.\end{split}$ (7)

We now investigate the impact of the approximate mixed attack strategy attack
on V-learning [15], a simple, efficient, decentralized algorithm for MARL. The
reader’s convienience, we list V-learning in Appendix G.2.

###### Theorem 9

Suppose ADV_BANDIT_UPDATE of V-learning follows Algorithm 3 in Appendix G.2
and it chooses hyper-parameter
$w_{t}=\alpha_{t}\left(\prod_{i=2}^{t}(1-\alpha_{i})\right)^{-1}$,
$\gamma_{t}=\sqrt{\frac{H\log B}{Bt}}$ and $\alpha_{t}=\frac{H+1}{H+t}$. For
given $K$ and any $\delta\in(0,1)$, let $\iota=\log(mHSAK/\delta)$. The attack
loss and the attack cost of the approximate mixed attack strategy during these
$K$ episodes are bounded by

$\begin{split}&\mathbb{E}\left[\text{Loss2}(K,H)\right]\leq
H\tau+\frac{40}{R_{min}}m\sqrt{H^{9}ASK\iota}+2H^{2}SK\sqrt{2A\iota/\tau},\\\
&\mathbb{E}\left[\text{Cost}(K,H)\right]\leq
2mH\tau+\frac{80}{R_{min}}\sqrt{H^{5}ASK\iota}.\end{split}$ (8)

Let $\hat{\pi}$ be the executing output policy of V-learning, the attack loss
of the executing output policy $\hat{\pi}$ is upper bounded by

$\begin{split}&V_{{\dagger},1}^{\pi^{*}}(s_{1})-V_{{\dagger},1}^{\hat{\pi}}(s_{1})\leq\frac{20mS}{R_{min}}\sqrt{\frac{H^{7}A\iota}{K}}+\frac{2\tau
mH^{2}S}{K}+2H^{2}S\sqrt{2A\iota/\tau}.\end{split}$ (9)

If we choose the stopping time of the exploration phase $\tau=K^{2/3}$, the
attack loss and the attack cost of the approximate mixed attack strategy
during these $K$ episodes are bounded by $\mathcal{O}(K^{2/3})$ and
$V_{{\dagger},1}^{\pi^{*}}(s_{1})-V_{{\dagger},1}^{\hat{\pi}}(s_{1})\leq\mathcal{O}(K^{-1/3})$.

##  6 Conclusion

In this paper, we have introduced an adversarial attack model on MARL. We have
discussed the attack problem in three different settings: the white-box, the
gray-box and the black-box settings. We have shown that the power of action
poisoning only attacks and reward poisoning only attacks is limited. Even in
the white-box setting, there exist some MGs, under which no action poisoning
only attack strategy or reward poisoning only attack strategy can be efficient
and successful. We have then characterized conditions when action poisoning
only attacks or only reward poisoning only attacks can efficiently work. We
have further introduced the mixed attack strategy in the gray-box setting that
can efficiently attack any sub-linear-regret MARL agents. Finally, we have
proposed the approximate mixed attack strategy in the black-box setting and
shown its effectiveness on V-learning. This paper raises awareness of the
trustworthiness of online multi-agent reinforcement learning. In the future,
we will investigate the defense strategy to mitigate the effects of this
attack.

## References

  * [1] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484–489, 2016.
  * [2] Noam Brown and Tuomas Sandholm.  Superhuman ai for multiplayer poker.  Science, 365(6456):885–890, 2019.
  * [3] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  Nature, 575(7782):350–354, 2019.
  * [4] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al.  Dota 2 with large scale deep reinforcement learning.  arXiv preprint arXiv:1912.06680, 2019.
  * [5] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua.  Safe, multi-agent, reinforcement learning for autonomous driving.  arXiv preprint arXiv:1610.03295, 2016.
  * [6] Afshin OroojlooyJadid and Davood Hajinezhad.  A review of cooperative multi-agent deep reinforcement learning.  arXiv preprint arXiv:1908.03963, 2019.
  * [7] Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch.  Emergent tool use from multi-agent autocurricula.  In International Conference on Learning Representations, 2020.
  * [8] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  Handbook of Reinforcement Learning and Control, pages 321–384, 2021\.
  * [9] Lloyd S Shapley.  Stochastic games.  Proceedings of the national academy of sciences, 39(10):1095–1100, 1953.
  * [10] Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye.  Solving discounted stochastic two-player games with near-optimal time and sample complexity.  In International Conference on Artificial Intelligence and Statistics, pages 2992–3002. PMLR, 2020.
  * [11] Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang.  Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity.  Advances in Neural Information Processing Systems, 33:1166–1178, 2020.
  * [12] Yu Bai and Chi Jin.  Provable self-play algorithms for competitive reinforcement learning.  In International conference on machine learning, pages 551–560. PMLR, 2020.
  * [13] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang.  Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium.  In Conference on learning theory, pages 3674–3682. PMLR, 2020.
  * [14] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin.  A sharp analysis of model-based reinforcement learning with self-play.  In International Conference on Machine Learning, pages 7001–7010. PMLR, 2021.
  * [15] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu.  V-learning–a simple, efficient, decentralized algorithm for multiagent rl.  arXiv preprint arXiv:2110.14555, 2021.
  * [16] Weichao Mao and Tamer Başar.  Provably efficient reinforcement learning in decentralized general-sum markov games.  Dynamic Games and Applications, pages 1–22, 2022.
  * [17] Vahid Behzadan and Arslan Munir.  Vulnerability of deep reinforcement learning to policy induction attacks.  In International Conference on Machine Learning and Data Mining in Pattern Recognition, pages 262–275. Springer, 2017.
  * [18] Yunhan Huang and Quanyan Zhu.  Deceptive reinforcement learning under adversarial manipulations on cost signals.  In International Conference on Decision and Game Theory for Security, pages 217–237. Springer, 2019.
  * [19] Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu.  Policy poisoning in batch reinforcement learning and control.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [20] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu.  Adaptive reward-poisoning attacks against reinforcement learning.  In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 11225–11234, 2020.
  * [21] Yanchao Sun, Da Huo, and Furong Huang.  Vulnerability-aware poisoning mechanism for online rl with unknown dynamics.  In International Conference on Learning Representations, 2021.
  * [22] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla.  Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning.  In International Conference on Machine Learning, pages 7974–7984, 2020.
  * [23] Amin Rakhsha, Xuezhou Zhang, Xiaojin Zhu, and Adish Singla.  Reward poisoning in reinforcement learning: Attacks against unknown learners in unknown environments.  arXiv preprint arXiv:2102.08492, 2021.
  * [24] Anshuka Rangi, Haifeng Xu, Long Tran-Thanh, and Massimo Franceschetti.  Understanding the limits of poisoning attacks in episodic reinforcement learning.  In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3394–3400. International Joint Conferences on Artificial Intelligence Organization, 7 2022.
  * [25] Guanlin Liu and Lifeng Lai.  Provably efficient black-box action poisoning attacks against reinforcement learning.  Advances in Neural Information Processing Systems, 34, 2021.
  * [26] Yuzhe Ma, Young Wu, and Xiaojin Zhu.  Game redesign in no-regret game playing.  In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pages 3321–3327, 2022.
  * [27] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell.  Adversarial policies: Attacking deep reinforcement learning.  In International Conference on Learning Representations, 2020.
  * [28] Wenbo Guo, Xian Wu, Sui Huang, and Xinyu Xing.  Adversarial policy learning in two-player competitive games.  In International Conference on Machine Learning, pages 3910–3919. PMLR, 2021.
  * [29] Young Wu, Jermey McMahan, Xiaojin Zhu, and Qiaomin Xie.  Reward poisoning attacks on offline multi-agent reinforcement learning.  arXiv preprint arXiv:2206.01888, 2022.
  * [30] Kiarash Banihashem, Adish Singla, and Goran Radanovic.  Defense against reward poisoning attacks in reinforcement learning.  arXiv preprint arXiv:2102.05776, 2021.
  * [31] Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun.  Robust policy gradient against strong data corruption.  In International Conference on Machine Learning, pages 12391–12401. PMLR, 2021.
  * [32] Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun.  Corruption-robust exploration in episodic reinforcement learning.  In Conference on Learning Theory, pages 3242–3245. PMLR, 2021.
  * [33] Yifang Chen, Simon Du, and Kevin Jamieson.  Improved corruption robust algorithms for episodic reinforcement learning.  In International Conference on Machine Learning, pages 1561–1570. PMLR, 2021.
  * [34] Chen-Yu Wei, Christoph Dann, and Julian Zimmert.  A model selection approach for corruption robust reinforcement learning.  In International Conference on Algorithmic Learning Theory, pages 1043–1096. PMLR, 2022.
  * [35] Tianhao Wu, Yunchang Yang, Simon Du, and Liwei Wang.  On reinforcement learning with adversarial corruption and its application to block mdp.  In International Conference on Machine Learning, pages 11296–11306. PMLR, 2021.

##  Appendix A Numerical results

In this section, we empirically evaluate the performance of the different
attack strategies.

###  A.1 Mixed attack v.s. $\eta$-portion attack v.s. $d$-portion attack

In this section, we empirically compare the performance of the action
poisoning only attack strategy ($d$-portion attack), the reward poisoning only
attack strategy ($\eta$-gap attack) and the mixed attack strategy.

We consider a simple case of Markov game where $m=2$, $H=2$ and
$|\mathcal{S}|=3$. This Markov game is the example in Appendix C.2. The
initial state is $s_{1}$ at $h=1$ and the transition probabilities are:

$\begin{split}&P(s_{2}|s_{1},a)=0.9,P(s_{3}|s_{1},a)=0.1,\text{~{}if~{}}a=(\text{Defect,
Defect}),\\\
&P(s_{2}|s_{1},a)=0.1,P(s_{3}|s_{1},a)=0.9,\text{~{}if~{}}a\neq(\text{Defect,
Defect}).\end{split}$ (10)

The reward functions are expressed in the following Table 2.

Table 2: Reward matrices

state $s_{1}$ | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.2, 0.2)

state $s_{2}$ | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.1, 0.1)

state $s_{3}$ | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.9, 0.9)

We set the total number of episodes $K=10^{7}$. We set two different target
policies. For the first target policy, no action/reward poisoning Markov
attack strategy alone can efficiently and successfully attack MARL agents. For
the second target policy, the $d$-portion attack and the $\eta$-gap attack can
efficiently and successfully attack MARL agents.

#### Case 1.

The target policy is that the two agents both choose to defect at any state.
As stated in Section 3 and Appendix 3.1, the Condition 1 and Condition 2 do
not hold for this Markov game and target policy, and no action/reward
poisoning Markov attack strategy alone can efficiently and successfully attack
MARL agents.

Figure 1: The cumulative attack loss and cost on case 1.

In Figure 1, we illustrate the mixed attack strategy, the $d$-portion attack
strategy and the $\eta$-gap attack strategy on V-learning agents for the
proposed MG. The $x$-axis represents the episode $k$ in the MG. The $y$-axis
represents the cumulative attack cost and attack loss that change over time
steps. The results show that, the attack cost and attack loss of the mixed
attack strategy sublinearly scale as $T$, but the attack cost and attack loss
of the $d$-portion attack strategy and the $\eta$-gap attack strategy linearly
scale as $T$, which is consistent with our analysis.

#### Case 2.

The target policy is that the two agents choose to cooperate at state $s_{1}$
and $s_{2}$ but to defect at state $s_{3}$. As stated in Section 3 and
Appendix 3.1, the Condition 1 and Condition 2 hold for this Markov game and
target policy. Thus, the $d$-portion attack strategy and the $\eta$-gap attack
strategy can efficiently and successfully attack MARL agents.

Figure 2: The cumulative attack loss and cost on case 2.

In Figure 2, we illustrate the mixed attack strategy, the $d$-portion attack
strategy and the $\eta$-gap attack strategy on V-learning agents for the
proposed MG. The results show that, the attack cost and attack loss of all
three strategies sublinearly scale as $T$, which is consistent with our
analysis.

###  A.2 Mixed attack v.s. approximate mixed attack

In this section, we empirically compare the performance of the mixed attack
strategy and the approximate mixed attack strategy. We consider a multi-agent
system with three recycling robots. In this scenario, a mobile robot with a
rechargeable battery and a solar battery collects empty soda cans in a city.
The number of agents is $3$, i.e. $m=3$. Each robot has two different energy
levels, high energy level and low energy level, resulting in $8$ states in
total, i.e. $S=8$.

Each robot can choose a conservative action or an aggressive action, so
$A_{i}=2$ and $A=8$. At the high energy level, the conservative action is to
wait in some place to save energy and then the mean reward is $0.4$. At the
high energy level, the aggressive action is to search for cans. All the robots
that choose to search will get a basic reward $0.2$ and equally share an
additionally mean reward $0.9$. For example, if all robots choose to search at
a step, the mean reward of each robot is $0.5$. At the low energy level, the
conservative action is to return to change the battery and find the cans on
the way. In this state and action, the robot only gets a low mean reward
$0.2$. At the low energy level, the conservative action is to wait in some
place to save energy and then the mean reward is $0.3$. We use Gaussian
distribution to randomize the reward signal.

We set the total number of steps $H=6$. At the step $h\leq 3$, it is the
daytime and the robot who chooses to search will change to the low energy
level with low probability $0.3$. At the step $h\geq 4$, it is the night and
the robot who chooses to search will change to the low energy level with high
probability $0.7$. The energy level transition probabilities are stated in
Figure 4 and Figure 4. ’H’ represents the high energy level. ’L’ represents
the low energy level. ’C’ represents the conservative action. ’A’ represents
the aggressive action.

Figure 3: Energy level transitions at $h\leq 3$.

Figure 4: Energy level transitions at $h\geq 4$.

We consider two different attack goals: (1) maximize the first robot’s
rewards; (2) minimize the the second robot’s and the third robot’s rewards.
For the gray box case, we provide the target policy that maximizes the first
robot’s rewards or minimizes the the second robot’s and the third robot’s
rewards. For the black box case, we set $R_{{\dagger},h}=R_{1,h}$ to maximize
the first robot’s rewards and set $R_{{\dagger},h}=1-R_{2,h}/2-R_{3,h}/2$ to
minimize the second robot’s and the third robot’s rewards.

Figure 5: The cumulative attack loss and cost of the mixed attack and the
approximate mixed attack.

We set the total number of episodes $K=10^{7}$. In Figure 5, we illustrate the
mixed attack strategy and approximate-mixed attack strategy on V-learning
agents for the proposed MG. The $x$-axis represents the episode $k$ in the MG.
The $y$-axis represents the cumulative attack cost and attack loss that change
over time steps. The results show that, the attack cost and attack loss of the
mixed attack strategy and approximate-mixed attack strategy sublinearly scale
as $T$, which is consistent with our analysis. Furthermore, Figure 5 shows
that the performance of the approximate-mixed attack strategy nearly match
that of the mixed attack strategy. This illustrates that the proposed
approximate-mixed attack strategy is very effective in the black-box scenario.

##  Appendix B Notations

In this section, we introduce some notations that will be frequently used in
appendixes.

The attack strategies in this paper are all Markov and only depend on the
current state and actions. The post-attack reward function has the same form
as the original reward function which is Markov and bounded in $[0,1]$. Thus,
the combination of the attacker and the environment
${MG}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$
can also be considered as a new environment
$\widetilde{MG}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,\widetilde{P},\\{\widetilde{R}_{i}\\}_{i=1}^{m})$,
and the agents interact with the new environment.
$\widetilde{R}_{i,h}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ represents
the post-attack reward function for the $i^{th}$ agent in the step $h$. The
post-attack transition probabilities satisfy
$\widetilde{P}_{h}(s^{\prime}|s,\boldsymbol{a})=\sum_{\boldsymbol{a}^{\prime}}\mathbb{A}_{h}(\boldsymbol{a}^{\prime}|s,\boldsymbol{a}){P}_{h}(s^{\prime}|s,\boldsymbol{a}^{\prime})$.

We use $\widetilde{R}_{i}$, $\widetilde{N}_{i}$, $\widetilde{Q}_{i}$ and
$\widetilde{V}_{i}$ to denote the mean rewards, counter, $Q$-values and value
functions of the new post-attack environment that each agent $i$ observes. We
use $N^{k}$, $V^{k}$ and $\pi^{k}$ to denote the counter, value functions, and
policy maintained by the agents’ algorithm at the beginning of the episode
$k$.

For notation simplicity, we define two operators $\mathbbm{P}$ and
$\mathbbm{D}$ as follows:

$\begin{split}&\mathbbm{P}_{h}[V](s,\bm{a})=\mathbbm{E}_{s^{\prime}\sim
P_{h}(\cdot|s,\bm{a})}\left[V(s^{\prime})\right],\\\
&\mathbbm{D}_{\pi}[Q](s)=\mathbbm{E}_{\bm{a}\sim\pi(\cdot|s)}\left[Q(s,\bm{a})\right].\end{split}$
(11)

Furthermore, we let $\mathbbm{A}$ denote the action manipulation.
$\mathbbm{A}=\\{\mathbbm{A}_{h}\\}_{h\in[H]}$ is a collection of action-
manipulation matrices, so that $\mathbbm{A}_{h}(\cdot|s,\bm{a})$ gives the
probability distribution of the post-attack action if actions $\bm{a}$ are
taken at state $s$ and step $h$. Using this notation, in the $d$-portion
attack strategy, we have
$\mathbbm{A}_{h}(\pi_{h}^{\dagger}(s)|s,\bm{a})=d_{h}(s,\bm{a})/m$, and
$\mathbbm{A}_{h}(\pi_{h}^{-}(s)|s,\bm{a})=1-d_{h}(s,\bm{a})/m$.

##  Appendix C Proof of the insufficiency of action poisoning only attacks and
reward poisoning only attacks

###  C.1 Proof of Theorem 1

We consider a simple case of Markov game where $m=2$, $H=1$ and
$|\mathcal{S}|=1$. The reward function can be expressed in the matrix form in
Table 3.

Table 3: Reward matrix | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.1, 0.1)

The target policy is that the two agents both choose to defect. In this MG,
the two agents’ rewards are the same under any action. As the action attacks
only change the agent’s action, the post-attack rewards have the same
property. The post-attack reward function can be expressed in the matrix form
in Table 4.

Table 4: Post-attack reward matrix | Cooperate | Defect
---|---|---
Cooperate | ($r_{1}$, $r_{1}$) | ($r_{2}$, $r_{2}$)
Defect | ($r_{3}$, $r_{3}$) | ($r_{4}$, $r_{4}$)

To achieve the objective in (1), we first have $r_{2}\leq r_{4}$ and
$r_{3}\leq r_{4}$, as the target policy should be an NE. Since the other
distinct policy should not be an $\epsilon$-approximate CCE, we consider the
other three pure-strategy policies and have

$\left\\{\begin{aligned}
&r_{1}>r_{2}+\epsilon,\text{or~{}}r_{4}>r_{2}+\epsilon\\\
&r_{1}>r_{3}+\epsilon,\text{or~{}}r_{4}>r_{3}+\epsilon\\\
&r_{3}>r_{1}+\epsilon,\text{or~{}}r_{2}>r_{1}+\epsilon\end{aligned}\right..$
(12)

Note that $r_{3}>r_{1}+\epsilon$ and $r_{1}>r_{3}+\epsilon$ are contradictory
and $r_{2}>r_{1}+\epsilon$ and $r_{1}>r_{2}+\epsilon$ are contradictory. We
must have $r_{4}>r_{3}+\epsilon$ or $r_{4}>r_{2}+\epsilon$. As the action
attacks will keep the same boundary of the rewards, $r_{3}\geq 0.1$ and
$r_{2}\geq 0.1$. Then, $r_{4}>0.1+\epsilon$.

Suppose there exists an action poisoning attack strategy that can successfully
attack MARL agents. We have
$\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}\left({a}_{i,h}^{k}=\pi^{\dagger}(s_{i,h}^{k})\right)=T-o(T)=\Omega(T)$,
i.e. the attack loss scales on $o(T)$. To achieve the post-attack reward
satisfy $r_{4}>0.1+\epsilon$, the attacker needs to change the target action
(Defect, Defect) to other actions with probability at least $\epsilon$, when
the agents choose the target action. Then, we have
$\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{E}(\mathbbm{1}(\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k}))=\Omega(\epsilon T)$. The expected attack cost is linearly
dependent on $T$. Hence, there does not exist an action poisoning attack
strategy that is both efficient and successful for this case.

###  C.2 Proof of Theorem 2

We consider a simple case of Markov game where $m=2$, $H=2$ and
$|\mathcal{S}|=3$. The reward functions are expressed in the following Table
5.

Table 5: Reward matrix

state $s_{1}$ | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.2, 0.2)

state $s_{2}$ | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.1, 0.1)

state $s_{3}$ | Cooperate | Defect
---|---|---
Cooperate | (1, 1) | (0.5, 0.5)
Defect | (0.5, 0.5) | (0.9, 0.9)

The initial state is $s_{1}$ at $h=1$ and the transition probabilities are:

$\begin{split}&P(s_{2}|s_{1},a)=0.9,P(s_{3}|s_{1},a)=0.1,\text{~{}if~{}}a=(\text{Defect,
Defect}),\\\
&P(s_{2}|s_{1},a)=0.1,P(s_{3}|s_{1},a)=0.9,\text{~{}if~{}}a\neq(\text{Defect,
Defect}).\end{split}$ (13)

The target policy is that the two agents both choose to defect at any state.
The post-attack reward function of the three states can be expressed in the
matrix form in Table 6.

Table 6: Post-attack reward matrix

state $s_{1}$ | Cooperate | Defect
---|---|---
Cooperate | ($r_{1}$, $r_{2}$) | ($r_{3}$, $r_{4}$)
Defect | ($r_{5}$, $r_{6}$) | ($r_{7}$, $r_{8}$)

state $s_{2}$ | Cooperate | Defect
---|---|---
Cooperate | ( - , - ) | ( - , - )
Defect | ( - , - ) | ($r_{9}$, $r_{10}$)

state $s_{3}$ | Cooperate | Defect
---|---|---
Cooperate | ( - , - ) | ( - , - )
Defect | ( - , - ) | ($r_{11}$, $r_{12}$)

We limit that the post-attack mean reward $\widetilde{R}$ has the same
boundary condition with that of the pre-attack mean reward $R$, i.e.
$\widetilde{R}\in[0,1]$. Then, $0\leq r_{1},\dots,r_{12}\leq 1$.

Suppose there exists a reward poisoning attack strategy that can successfully
attack MARL agents, we have
$\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}\left({a}_{i,h}^{k}=\pi^{\dagger}(s_{i,h}^{k})\right)=T-o(T)=\Omega(T)$,
i.e. the attack loss scales on $o(T)$.

If $|r_{9}-0.1|>0.1$, $|r_{10}-0.1|>0.1$, $|r_{11}-0.9|>0.1$, or
$|r_{12}-0.9|>0.1$, we have the attack cost
$\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{E}(|\widetilde{r}_{i,h}^{k}-r_{i,h}^{k}|)=\Omega(0.1*K)=\Omega(T)$.
Thus, $|r_{9}-0.1|\leq 0.1$, $|r_{10}-0.1|\leq 0.1$, $|r_{11}-0.9|\leq 0.1$
and $|r_{12}-0.9|\leq 0.1$.

For the target policy, we have
$\widetilde{V}_{i,1}^{\pi^{\dagger}}(s_{1})=r_{7}+0.9*r_{9}+0.1*r_{11}$. For
the policy $\pi^{\prime}$ with $\pi^{\prime}_{1}(s_{1})=$ (Cooperate, Defect),
$\pi^{\prime}_{2}(s_{2})=$ (Defect, Defect), $\pi^{\prime}_{2}(s_{3})=$
(Defect, Defect), we have
$\widetilde{V}_{i,1}^{\pi^{\prime}}(s_{1})=r_{3}+0.1*r_{9}+0.9*r_{11}$.

To achieve the objective in (1), the attacker should let the target policy to
be an NE. Thus, we have
$\widetilde{V}_{i,1}^{\pi^{\dagger}}(s_{1})\geq\widetilde{V}_{i,1}^{\pi^{\prime}}(s_{1})$
and then $r_{7}+0.9*r_{9}+0.1r_{11}\geq r_{3}+0.1*r_{9}+0.9*r_{11}$. As
$|r_{9}-0.1|\leq 0.1$ and $|r_{11}-0.9|\leq 0.1$, we have $r_{7}\geq
r_{3}+0.48$. From the boundary condition, we have $r_{3}\geq 0$ and then
$r_{7}\geq 0.48$. The attack cost scales at least on $\Omega(0.28*T)$ for a
successful reward attack strategy.

In summary, there does not exist an reward poisoning attack strategy that is
both efficient and successful for this case.

##  Appendix D Analysis of the $d$-portion Attack

###  D.1 Proof of Theorem 3

We assume that the minimum gap exists and is positive, i.e. $\Delta_{min}>0$.
This positive gap provides an opportunity for efficient action poisoning
attacks.

We assume that the agent does not know the attacker’s manipulations and the
presence of the attacker. The attacker’s manipulations on actions are
stationary. We can consider the combination of the attacker and the
environment
$\text{MG}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$
as a new environment
$\widetilde{\text{MG}}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,\widetilde{P},\\{\widetilde{R}_{i}\\}_{i=1}^{m})$,
and the agents interact with the new environment. We define
$\widetilde{Q}_{i}$ and $\widetilde{V}_{i}$ as the $Q$-values and value
functions of the new environment $\widetilde{\text{MG}}$ that each agent $i$
observes.

We first prove that $\pi^{\dagger}$ is an NE from every agent’s point of view.

Condition 1 implies that $\pi^{\dagger}$ is not the worst policy from every
agent’s point of view, and there exists a policy $\pi^{-}$ that is worse than
the target policy from every agent’s point of view. Denote
$\Delta^{{\dagger}-}_{i,h}(s)=Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))$.
We define the minimum gap
$\Delta_{min}=\min_{h\in[H],s\in\mathcal{S},i\in[m]}=\Delta^{{\dagger}-}_{i,h}(s)$.

We set $\mathbbm{P}_{h}V_{i,h+1}^{\pi}(s,\bm{a})=\mathbbm{E}_{s^{\prime}\sim
P_{h}(\cdot|s,\bm{a})}\left[V^{\pi}_{i,h+1}(s^{\prime})\right]$. From
$d$-portion attack strategy, we have

$\begin{split}\widetilde{Q}_{i,h}^{\pi}(s,\bm{a})=\widetilde{R}_{i,h}(s,\bm{a})+\frac{d_{h}(s,\bm{a})}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s))+\left(1-\frac{d_{h}(s,\bm{a})}{m}\right)\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{-}(s)),\end{split}$
(14)

and

$\begin{split}\widetilde{R}_{i,h}(s,\bm{a})=\frac{d_{h}(s,\bm{a})}{m}R_{i,h}(s,\pi_{h}^{\dagger}(s))+\left(1-\frac{d_{h}(s,\bm{a})}{m}\right)R_{i,h}(s,\pi_{h}^{-}(s)).\end{split}$
(15)

Since the attacker does not attack when the agents follow the target policy,
we have
$\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s)={V}_{i,h+1}^{\pi^{\dagger}}(s)$.
Then,

$\begin{split}\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\bm{a})=&\frac{d_{h}(s,\bm{a})}{m}Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))+\left(1-\frac{d_{h}(s,\bm{a})}{m}\right)Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s)).\end{split}$
(16)

If $a_{i}\neq\pi_{i,h}^{\dagger}(s)$, we have

$\begin{split}\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\pi_{i,h}^{\dagger}(s)\times\bm{a}_{-i})-\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\bm{a})=\frac{1}{2m}\left(Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))\right)\geq\frac{\Delta_{min}}{2m}.\end{split}$
(17)

We have that policy $\pi_{i}^{\dagger}$ is best-in-hindsight policy towards
the target policy $\pi_{-i}^{\dagger}$ at step $h$ in the observation of each
agent $i$, i.e.
$\widetilde{V}_{i,h+1}^{\pi_{i}^{\dagger}\times\pi^{\dagger}_{-i}}(s)=\widetilde{V}_{i,h+1}^{{\dagger},\pi_{-i}^{\dagger}}(s)$
for any agent $i$, any state $s$ and any policy $\pi_{-i}$.

Since the above argument works for any step $h\in[H]$, we have that the best
response of each agent $i$ towards the target product policy
$\pi_{-i}^{\dagger}$ is $\pi^{\dagger}_{i}$ and the target policy is an {NE,
CE, CCE} under $d$-portion attack.

Now we prove that the target policy $\pi^{\dagger}_{i}$ is the unique {NE, CE,
CCE}, when every state $s\in\mathcal{S}$ is reachable at every step $h\in[H]$
under the target policy.

If there exists an CCE $\pi^{\prime}$ under $d$-portion attack, we have
$\max_{i\in[m]}(\widetilde{V}_{i,1}^{{\dagger},\pi^{\prime}_{-i}}(s)-\widetilde{V}_{i,1}^{\pi^{\prime}}(s))=0$
for any initial state $s$.

At the step $H$,
$\widetilde{Q}_{i,H}^{\pi}(s,\bm{a})=\widetilde{R}_{i,H}(s,\bm{a})$. Since
$R_{i,H}(s,\pi_{H}^{\dagger}(s))\geq R_{i,H}(s,\pi_{H}^{-}(s))+\Delta_{min}$
with $\Delta_{min}>0$, the policy $\pi_{i,H}^{\dagger}$ is the unique best
response towards any policy $\pi_{-i,H}$, i.e.
$\widetilde{V}_{i,H}^{\pi^{\dagger}_{i,H},\pi_{-i,H}}(s)=\widetilde{V}_{i,H}^{{\dagger},\pi_{-i,H}}(s)$
and
$\widetilde{V}_{i,H}^{\pi^{\dagger}_{i,H},\pi_{-i,H}}(s)>\widetilde{V}_{i,H}^{\pi_{i,H},\pi_{-i,H}}(s)$
for any $\pi_{i,H}(\cdot|s)\neq\pi_{i,H}^{\dagger}(\cdot|s)$. Thus, we have
$\pi^{\prime}_{H}(s_{H})=\pi^{\dagger}_{H}(s_{H})$ for any state $s_{H}$ that
is reachable at the time step $H$ under policy $\pi^{\prime}$. We assume that
every state $s\in\mathcal{S}$ is reachable at every step $h\in[H]$ under the
target policy. Under $d$-portion attacks, the post-attack action
$\widetilde{\bm{a}}_{h}=\pi_{h}^{\dagger}(s)$ with probability more than
$0.5$. Thus, every state $s\in\mathcal{S}$ is reachable at every step
$h\in[H]$ under any policy $\pi$ and $d$-portion attacks.

Recall that for any $a_{i}\neq\pi_{i,h}^{\dagger}(s)$,

$\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\pi_{i,h}^{\dagger}(s)\times\bm{a}_{-i})-\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\bm{a})\geq\Delta_{min}/2m.$
(18)

Suppose
$\\{\pi^{\prime}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}=\\{\pi^{\dagger}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}$
for any states. If
$\pi^{\prime}_{i,h}(\cdot|s)\neq\pi^{\dagger}_{i,h}(\cdot|s)$ at a reachable
state $s$, we have

$\begin{split}\widetilde{V}_{i,h}^{\pi^{\prime}}(s)=&\mathbbm{E}_{\bm{a}\sim\pi^{\prime}_{h}(\cdot|s)}[\widetilde{Q}_{i,h}^{\pi^{\prime}}(s,\bm{a})]\\\
=&\mathbbm{E}_{\bm{a}\sim\pi^{\prime}_{h}(\cdot|s)}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\bm{a})]\\\
\leq&\mathbbm{E}_{\bm{a}_{-i}\sim\pi^{\prime}_{-i,h}(\cdot|s)}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}(s,\pi_{i,h}^{\dagger}(s)\times\bm{a}_{-i})]-c\Delta_{min}/2m\\\
=&\widetilde{V}_{i,h}^{\pi^{\dagger}\times\pi^{\prime}_{-i}}(s)-c\Delta_{min}/m\end{split}$
(19)

with some constant $c>0$. Then, $\pi^{\prime}$ is not an CCE in such a case.

From induction on $h=H,H-1,\cdots,1$, $\pi^{\prime}=\pi^{\dagger}$ for any
states. If every state $s\in\mathcal{S}$ is reachable at every step $h\in[H]$
under the target policy, $\pi^{\dagger}$ is the unique {NE, CE, CCE}.

###  D.2 Proof of Theorem 4

Consider an arbitrary Markov policy $\pi$. From $d$-portion attack strategy,
we have

$\begin{split}\widetilde{Q}_{i,h}^{\pi}(s,\bm{a})=&\frac{d_{h}(s,\bm{a})}{m}R_{i,h}(s,\pi_{h}^{\dagger}(s))+\frac{m-d_{h}(s,\bm{a})}{m}R_{i,h}(s,\pi_{h}^{-}(s))\\\
&+\frac{d_{h}(s,\bm{a})}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s))+\frac{m-d_{h}(s,\bm{a})}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{-}(s))\\\
=&\frac{d_{h}(s,\bm{a})-m}{m}\left(R_{i,h}(s,\pi_{h}^{\dagger}(s))-R_{i,h}(s,\pi_{h}^{-}(s))\right)\\\
&+\frac{d_{h}(s,\bm{a})-m}{m}\left(\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s))-\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{-}(s))\right)\\\
&+R_{i,h}(s,\pi_{h}^{\dagger}(s))+\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s))\end{split}$
(20)

and

$\begin{split}\widetilde{V}_{i,h}^{\pi}(s)=&\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi}](s)\\\
=&\frac{\mathbbm{D}_{\pi_{h}}[d](s)-m}{m}\left(R_{i,h}(s,\pi_{h}^{\dagger}(s))-R_{i,h}(s,\pi_{h}^{-}(s))\right)\\\
&+\frac{\mathbbm{D}_{\pi_{h}}[d](s)-m}{m}\left(\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s))-\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{-}(s))\right)\\\
&+R_{i,h}(s,\pi_{h}^{\dagger}(s))+\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s)).\end{split}$
(21)

Now we bound the difference between $\widetilde{V}_{i,h}^{\pi}(s)$ and
$\widetilde{V}_{i,h}^{\pi^{\dagger}}(s)$ for any policy $\pi$.

$\begin{split}\widetilde{V}_{i,h}^{\pi^{\dagger}}(s)-\widetilde{V}_{i,h}^{\pi}(s)=&\underbrace{\widetilde{V}_{i,h}^{\pi^{\dagger}}(s)-\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}](s)}_{(a)}+\underbrace{\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}](s)-\widetilde{V}_{i,h}^{\pi}(s)}_{(b)}.\end{split}$
(22)

For term (a), from equations (20) and (21), we have

$\begin{split}&\widetilde{V}_{i,h}^{\pi^{\dagger}}(s)-\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}](s)\\\
=&\frac{m-\mathbbm{D}_{\pi_{h}}[d](s)}{m}\left(R_{i,h}(s,\pi_{h}^{\dagger}(s))-R_{i,h}(s,\pi_{h}^{-}(s))\right)\\\
&+\frac{m-\mathbbm{D}_{\pi_{h}}[d](s)}{m}\left(\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))\right).\end{split}$
(23)

Since the attacker does not attack when the agents follow the target policy,
we have
$\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s)={V}_{i,h+1}^{\pi^{\dagger}}(s)$.

$\begin{split}\widetilde{V}_{i,h}^{\pi^{\dagger}}(s)-\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}](s)=&\frac{m-\mathbbm{D}_{\pi_{h}}[d](s)}{m}\left(Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))\right).\end{split}$
(24)

Denote
$\Delta^{{\dagger}-}_{i,h}(s)=Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))$.
We have

$\begin{split}\widetilde{V}_{i,h}^{\pi^{\dagger}}(s)-\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}](s)=&\frac{\Delta^{{\dagger}-}_{i,h}(s)}{2m}\mathbbm{E}_{\bm{a}\sim\pi_{h}(\cdot|s)}\left[\sum_{i=1}^{m}\mathbbm{1}(a_{i}\neq\pi^{\dagger}_{i,h}(s))\right].\end{split}$
(25)

For term (b), from equations (20) and (21), we have

$\begin{split}&\mathbbm{D}_{\pi_{h}}[\widetilde{Q}_{i,h}^{\pi^{\dagger}}](s)-\widetilde{V}_{i,h}^{\pi}(s)\\\
=&\frac{\mathbbm{D}_{\pi_{h}}[d](s)}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))+\frac{m-\mathbbm{D}_{\pi_{h}}[d](s)}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))\\\
&-\frac{\mathbbm{D}_{\pi_{h}}[d](s)}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s))-\frac{m-\mathbbm{D}_{\pi_{h}}[d](s)}{m}\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{-}(s))\\\
=&\frac{\mathbbm{D}_{\pi_{h}}[d](s)}{m}\mathbbm{P}_{h}[\widetilde{V}_{i,h+1}^{\pi^{\dagger}}-\widetilde{V}_{i,h+1}^{\pi}](s,\pi_{h}^{\dagger}(s))\\\
&+\frac{m-\mathbbm{D}_{\pi_{h}}[d](s)}{m}\mathbbm{P}_{h}[\widetilde{V}_{i,h+1}^{\pi^{\dagger}}-\widetilde{V}_{i,h+1}^{\pi}](s,\pi_{h}^{-}(s))\\\
=&\mathbbm{E}_{s^{\prime}\sim
P_{h}(\cdot|s,\widetilde{\bm{a}}),\widetilde{\bm{a}}\sim\mathbbm{A}_{h}(\cdot|s,\bm{a}),\bm{a}\sim\pi_{h}(\cdot|s)}[\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s^{\prime})-\widetilde{V}_{i,h+1}^{\pi}(s^{\prime})].\end{split}$
(26)

By combining terms (a) and (b), we have

$\begin{split}&\widetilde{V}_{i,h}^{\pi^{\dagger}}(s_{h})-\widetilde{V}_{i,h}^{\pi}(s_{h})\\\
=&\frac{\Delta^{{\dagger}-}_{i,h}(s_{h})}{2m}\mathbbm{E}_{\bm{a}\sim\pi_{h}(\cdot|s_{h})}\left[\mathbbm{1}(a_{i}\neq\pi^{\dagger}_{i,h}(s_{h}))\right]\\\
&+\mathbbm{E}_{s_{h+1}\sim
P_{h}(\cdot|s_{h},\widetilde{\bm{a}}),\widetilde{\bm{a}}\sim\mathbbm{A}_{h}(\cdot|s_{h},\bm{a}),\bm{a}\sim\pi_{h}(\cdot|s_{h})}[\widetilde{V}_{i,h+1}^{\pi^{\dagger}}(s_{h+1})-\widetilde{V}_{i,h+1}^{\pi}(s_{h+1})]\\\
=&\cdots=\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{h^{\prime}=h}^{H}\sum_{i=1}^{m}\mathbbm{1}(a_{i,h^{\prime}}\neq\pi^{\dagger}_{i,h^{\prime}}(s_{h^{\prime}}))\frac{\Delta^{{\dagger}-}_{i,h^{\prime}}(s_{h^{\prime}})}{2m}\right].\end{split}$
(27)

From the definition of the best-in-hindsight regret and (27), we have

$\begin{split}\text{Reg}_{i}(K,H)=&\max_{\pi_{i}^{\prime}}\sum_{k=1}^{K}[\widetilde{V}_{i,1}^{\pi_{i}^{\prime}\times\pi^{k}_{-i}}(s_{1}^{k})-\widetilde{V}_{i,1}^{\pi^{k}}(s_{1}^{k})]\\\
\geq&\sum_{k=1}^{K}[\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi^{k}_{-i}}(s_{1}^{k})-\widetilde{V}_{i,1}^{\pi^{k}}(s_{1}^{k})].\end{split}$
(28)

Now, we bound
$\sum_{i=1}^{m}[\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})]$
for any policy $\pi$. We introduce some special strategy modifications
$\\{\phi_{i,h}^{\dagger}\\}_{h=1}^{H}$. For any $h^{\prime}\geq h$, we have
$\phi_{i,h}^{\dagger}\diamond\pi_{i,h^{\prime}}(s)=\pi^{\dagger}_{i,h^{\prime}}(s)$
and for any $h^{\prime}<h$, we have
$\phi_{i,h}^{\dagger}\diamond\pi_{i,h^{\prime}}(s)=\pi_{i,h^{\prime}}(s)$.
Thus,

$\begin{split}&\sum_{i=1}^{m}[\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})]\\\
=&\sum_{h=1}^{H}\sum_{i=1}^{m}[\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})].\end{split}$
(29)

When $h=H$, we have

$\begin{split}&\sum_{i=1}^{m}\left(\widetilde{V}_{i,1}^{\phi_{i,H}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,H+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})\right)\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\left(\widetilde{V}_{i,H}^{\phi_{i,H}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{H})-\widetilde{V}_{i,H}^{\phi_{i,H+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{H})\right)\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\left(\widetilde{V}_{i,H}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{H})-\widetilde{V}_{i,H}^{\pi}(s_{H})\right)\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\mathbbm{1}(a_{i,H}\neq\pi^{\dagger}_{i,H}(s_{H}))\frac{\Delta^{{\dagger}-}_{i,H}(s_{H})}{2m}\right].\end{split}$
(30)

For $h<H$, we have

$\begin{split}&\sum_{i=1}^{m}\left(\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})\right)\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\left(\widetilde{V}_{i,h}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h})-\widetilde{V}_{i,h}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h})\right)\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\left(\mathbbm{D}_{\phi_{i,h}^{\dagger}\diamond\pi_{i,h}\times\pi_{-i,h}}-\mathbbm{D}_{\phi_{i,h+1}^{\dagger}\diamond\pi_{i,h}\times\pi_{-i,h}}\right)\left[\widetilde{Q}_{i,h}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}\right](s_{h})\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\frac{1-\pi_{i,h}\left(s_{h},\pi^{\dagger}_{i,h}(s_{h})\right)}{2m}\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[R_{i,h}+\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}\right](s_{h})\right]\end{split}$
(31)

where the second equation holds as
$\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}=\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}$
at any time step $h^{\prime}>h$ and the last equation holds from equation
(20).

Note that
$Q_{i,h}^{\pi^{\dagger}}=R_{i,h}+\mathbbm{P}_{h}V^{\pi^{\dagger}}_{i,h+1}=R_{i,h}+\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}$.
From equation (31), we have

$\begin{split}&\sum_{i=1}^{m}\left(\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})\right)\\\
=&\underbrace{\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\frac{1-\pi_{i,h}\left(s_{h},\pi^{\dagger}_{i,h}(s_{h})\right)}{2m}\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[Q_{i,h}^{\pi^{\dagger}}\right](s_{h})\right]}_{\text{\char
172}}\\\
&+\underbrace{\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\frac{1-\pi_{i,h}\left(s_{h},\pi^{\dagger}_{i,h}(s_{h})\right)}{2m}\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}\right](s_{h})\right]}_{\text{\char
173}}.\end{split}$ (32)

Denote
$\Delta^{{\dagger}-}_{i,h}(s)=Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{\dagger}(s))-Q_{i,h}^{\pi^{\dagger}}(s,\pi_{h}^{-}(s))$.
Thus,

$\begin{split}\text{\char
172}=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\frac{1-\pi_{i,h}\left(s_{h},\pi^{\dagger}_{i,h}(s_{h})\right)}{2m}\Delta^{{\dagger}-}_{i,h}(s_{h})\right].\end{split}$
(33)

Now, we bound item ②. If
$\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}\right](s_{h})\geq
0$,

$\begin{split}&\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}\right](s_{h})\\\
\geq&\frac{2\mathbbm{D}_{\pi_{h}}[d](s_{h})}{m}\mathbbm{D}_{\pi^{\dagger}}\mathbbm{P}_{h}[\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\widetilde{V}^{\pi^{\dagger}}_{i,h+1}](s_{h})\\\
&+\frac{2(m-\mathbbm{D}_{\pi_{h}}[d](s_{h}))}{m}\mathbbm{D}_{\pi^{-}}\mathbbm{P}_{h}[\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\widetilde{V}^{\pi^{\dagger}}_{i,h+1}](s_{h})\\\
=&2\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h+1})-\widetilde{V}^{\pi^{\dagger}}_{i,h+1}(s_{h+1})\right],\end{split}$
(34)

because the RHS of the inequality is smaller or equal to $0$.

If
$\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}\right](s_{h})\leq
0$,

$\begin{split}&\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}\right](s_{h})\\\
\geq&\frac{2\mathbbm{D}_{\pi_{h}}[d](s_{h})}{m}\left(\mathbbm{D}_{\pi^{\dagger}}-\mathbbm{D}_{\pi^{-}}\right)\left[\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\mathbbm{P}_{h}\widetilde{V}^{\pi^{\dagger}}_{i,h+1}\right](s_{h})\\\
\geq&\frac{2\mathbbm{D}_{\pi_{h}}[d](s_{h})}{m}\mathbbm{D}_{\pi^{\dagger}}\mathbbm{P}_{h}[\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\widetilde{V}^{\pi^{\dagger}}_{i,h+1}](s_{h})\\\
&+\frac{2(m-\mathbbm{D}_{\pi_{h}}[d](s_{h}))}{m}\mathbbm{D}_{\pi^{-}}\mathbbm{P}_{h}[\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}-\widetilde{V}^{\pi^{\dagger}}_{i,h+1}](s_{h})\\\
=&2\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h+1})-\widetilde{V}^{\pi^{\dagger}}_{i,h+1}(s_{h+1})\right].\end{split}$
(35)

From (27), we have

$\begin{split}&\widetilde{V}^{\pi^{\dagger}}_{i,h+1}(s_{h+1})-\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h+1})\\\
=&\mathbbm{E}_{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i},\mathbbm{A},P}\left[\sum_{h^{\prime}=h+1}^{H}\sum_{i=1}^{m}\mathbbm{1}(a_{i,h^{\prime}}\neq\pi^{\dagger}_{i,h^{\prime}}(s_{h^{\prime}}))\frac{\Delta^{{\dagger}-}_{i,h^{\prime}}(s_{h^{\prime}})}{2m}\right]\\\
\leq&\sum_{h^{\prime}=h+1}^{H}(m-1)\max_{s\in\mathcal{S},i\in[m]}\frac{\Delta^{{\dagger}-}_{i,h^{\prime}}(s)}{2m}\\\
\leq&\frac{(m-1)}{2m}\Delta^{{\dagger}-}_{i,h}(s_{h}),\end{split}$ (36)

where the last inequality holds when
$\min_{s\in\mathcal{S},i\in[m]}\Delta^{{\dagger}-}_{i,h}(s)\geq\sum_{h^{\prime}=h+1}^{H}\max_{s\in\mathcal{S},i\in[m]}\Delta^{{\dagger}-}_{i,h^{\prime}}(s)$.
Combine the above inequalities, we have

$\begin{split}\text{\char
173}\geq&-\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\frac{1-\pi_{i,h}\left(s_{h},\pi^{\dagger}_{i,h}(s_{h})\right)}{2m}\frac{(m-1)}{m}\Delta^{{\dagger}-}_{i,h}(s_{h})\right],\end{split}$
(37)

and

$\begin{split}&\sum_{i=1}^{m}\left(\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})\right)\\\
=&{\text{\char 172}}+{\text{\char 173}}\\\
\geq&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\frac{1-\pi_{i,h}\left(s_{h},\pi^{\dagger}_{i,h}(s_{h})\right)}{2m^{2}}\Delta^{{\dagger}-}_{i,h}(s_{h})\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\mathbbm{1}(a_{i,h}\neq\pi^{\dagger}_{i,h}(s_{h}))\frac{\Delta^{{\dagger}-}_{i,h}(s_{h})}{2m^{2}}\right]\\\
\geq&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\mathbbm{1}(a_{i,h}\neq\pi^{\dagger}_{i,h}(s_{h}))\right]\frac{\Delta_{min}}{2m^{2}}.\end{split}$
(38)

In summary,

$\begin{split}\text{Reg}_{i}(K,H)\geq&\sum_{h=1}^{H}\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{i=1}^{m}\mathbbm{1}(a_{i,h}\neq\pi^{\dagger}_{i,h}(s_{h}))\right]\frac{\Delta_{min}}{2m^{2}}=\mathbb{E}[\text{Loss1}(K,H)]\frac{\Delta_{min}}{2m^{2}}.\end{split}$
(39)

If the best-in-hindsight regret $\text{Reg}(K,H)$ of each agent’s algorithm is
bounded by a sub-linear bound $\mathcal{R}(T)$, then the attack loss is
bounded by $\mathbbm{E}[\text{Loss1}(K,H)]\leq
2m^{2}\mathcal{R}(T)/\Delta_{min}$.

The $d$-portion attack strategy attacks all agents when any agent $i$ chooses
an non-target action. We have

$\begin{split}\text{Cost}(K,H)=&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\left(\mathbbm{1}(\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k})+|\widetilde{r}_{i,h}^{k}-r_{i,h}^{k}|\right)\\\
\leq&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}[\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k}]m.\end{split}$ (40)

Then, the attack cost is bounded by $m\mathbbm{E}[\text{Loss1}(K,H)]\leq
2m^{3}\mathcal{R}(T)/\Delta_{min}$.

##  Appendix E Analysis of the $\eta$-gap attack

###  E.1 Proof of Theorem 5

We assume that the agent does not know the attacker’s manipulations and the
presence of the attacker. The attacker’s manipulations on rewards are
stationary. We can consider the combination of the attacker and the
environment
$\text{MG}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$
as a new environment
$\widetilde{\text{MG}}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{\widetilde{R}_{i}\\}_{i=1}^{m})$,
and the agents interact with the new environment. We define
$\widetilde{Q}_{i}$ and $\widetilde{V}_{i}$ as the $Q$-values and value
functions of the new environment $\widetilde{\text{MG}}$ that each agent $i$
observes.

We introduce some special strategy modifications
$\\{\phi_{i,h}^{\dagger}\\}_{h=1}^{H}$. For any $h^{\prime}\geq h$, we have
$\phi_{i,h}^{\dagger}\diamond\pi_{i,h^{\prime}}(s)=\pi^{\dagger}_{i,h^{\prime}}(s)$
and for any $h^{\prime}<h$, we have
$\phi_{i,h}^{\dagger}\diamond\pi_{i,h^{\prime}}(s)=\pi_{i,h^{\prime}}(s)$.
Thus,

$\begin{split}&\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})=\sum_{h=1}^{H}[\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})].\end{split}$
(41)

We have that for any policy $\pi$,

$\begin{split}&[\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\left(\widetilde{V}_{i,h}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h})-\widetilde{V}_{i,h}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h})\right)\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\left(\mathbbm{D}_{\phi_{i,h}^{\dagger}\diamond\pi_{i,h}\times\pi_{-i,h}}-\mathbbm{D}_{\phi_{i,h+1}^{\dagger}\diamond\pi_{i,h}\times\pi_{-i,h}}\right)\left[\widetilde{Q}_{i,h}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}\right](s_{h})\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\left(\mathbbm{D}_{\pi_{i,h}^{\dagger}\times\pi_{-i,h}}-\mathbbm{D}_{\pi_{h}}\right)\left[\widetilde{R}_{i,h}+\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}\right](s_{h})\right].\end{split}$
(42)

Since
$\widetilde{R}_{i,h}(s,\bm{a})=R_{i,h}(s,\pi^{\dagger}(s))-(\eta+(H-h)\Delta_{R})\mathbbm{1}(a_{i}\neq\pi_{i,h}^{\dagger}(s))$
from $\eta$-gap attack strategy and $(H-h)\min_{s^{\prime}\times
a^{\prime}\times
h^{\prime}}R_{i,h^{\prime}}(s^{\prime},a^{\prime})<\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s^{\prime},a^{\prime})\leq(H-h)\max_{s^{\prime}\times
a^{\prime}\times h^{\prime}}R_{i,h^{\prime}}(s^{\prime},a^{\prime})$ for any
$s$ and $a$, we have

$\begin{split}&[\widetilde{V}_{i,1}^{\phi_{i,h}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{1})]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{\bm{a}}\pi_{h}(\bm{a}|s_{h})(\eta+(H-h)\Delta_{R})\mathbbm{1}(a_{i}\neq\pi_{i,h}^{\dagger}(s_{h}))\right]\\\
&+\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{\bm{a}}\pi_{h}(\bm{a}|s_{h})\mathbbm{1}(a_{i}\neq\pi_{i,h}^{\dagger}(s_{h}))\left(\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h},\pi_{i,h}^{\dagger}(s_{h})\times\bm{a}_{-i})-\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\phi_{i,h+1}^{\dagger}\diamond\pi_{i}\times\pi_{-i}}(s_{h},\bm{a})\right)\right]\\\
\geq&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{\bm{a}}\pi_{h}(\bm{a}|s_{h})\eta\mathbbm{1}(a_{i}\neq\pi_{i,h}^{\dagger}(s))\right]\\\
=&\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\mathbbm{1}(a_{i,h}\neq\pi_{i,h}^{\dagger}(s))\right]\eta.\end{split}$
(43)

Thus,

$\begin{split}&\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})\geq\mathbbm{E}_{\pi,\mathbbm{A},P}\left[\sum_{h=1}^{H}\mathbbm{1}(a_{i,h}\neq\pi_{i,h}^{\dagger}(s_{h}))\right]\eta\geq
0.\end{split}$ (44)

The target policy is an NE, and then also is an CE or CCE.

Now we prove that the target policy $\pi^{\dagger}_{i}$ is the unique {NE, CE,
CCE}, when every state $s\in\mathcal{S}$ is reachable at every step $h\in[H]$
under the target policy.

If there exists an CCE $\pi^{\prime}$ under $\eta$-gap attack, we have
$\max_{i\in[m]}(\widetilde{V}_{i,1}^{{\dagger},\pi^{\prime}_{-i}}(s)-\widetilde{V}_{i,1}^{\pi^{\prime}}(s))=0$
for any initial state $s$. If
$\pi^{\prime}_{i,h}(\cdot|s)\neq\pi^{\dagger}_{i,h}(\cdot|s)$ at a reachable
state $s$, we have that
$\mathbbm{E}_{\pi^{\prime},\mathbbm{A},P}\left[\sum_{h=1}^{H}\mathbbm{1}(a_{i,h}\neq\pi_{i,h}^{\dagger}(s_{h}))\right]$.
Thus,

$\begin{split}&\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}^{\prime}}(s_{1})-\widetilde{V}_{i,1}^{\pi^{\prime}}(s_{1})\geq\mathbbm{E}_{\pi^{\prime},\mathbbm{A},P}\left[\sum_{h=1}^{H}\mathbbm{1}(a_{i,h}\neq\pi_{i,h}^{\dagger}(s_{h}))\right]\eta>0,\end{split}$
(45)

and $\pi^{\prime}$ is not an CCE. In summary, the target policy
$\pi^{\dagger}_{i}$ is the unique {NE, CE, CCE}.

###  E.2 Proof of Theorem 6

From the definition of the best-in-hindsight regret and (51), we have

$\begin{split}\text{Reg}_{i}(K,H)=&\max_{\pi_{i}^{\prime}}\sum_{k=1}^{K}[\widetilde{V}_{i,1}^{\pi_{i}^{\prime}\times\pi^{k}_{-i}}(s_{1}^{k})-\widetilde{V}_{i,1}^{\pi^{k}}(s_{1}^{k})]\\\
\geq&\sum_{k=1}^{K}[\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi^{k}_{-i}}(s_{1}^{k})-\widetilde{V}_{i,1}^{\pi^{k}}(s_{1}^{k})].\end{split}$
(46)

From (44), we have

$\begin{split}\text{Reg}_{i}(K,H)\geq&\sum_{k=1}^{K}\mathbb{E}_{\pi^{k},\mathbbm{A},P}\left[\sum_{h=1}^{H}\mathbbm{1}[a_{i,h}^{k}\neq\pi_{i,h}^{\dagger}(s_{h}^{k})]\right]\eta\end{split}$
(47)

and

$\sum_{i=1}^{m}\text{Reg}_{i}(K,H)=\eta\mathbb{E}[\text{Loss1}(K,H)].$ (48)

If the best-in-hindsight regret $\text{Reg}(K,H)$ of each agent’s algorithm is
bounded by a sub-linear bound $\mathcal{R}(T)$, then the attack loss is
bounded by $\mathbbm{E}[\text{Loss1}(K,H)]\leq m\mathcal{R}(T)/\eta$.

The $\eta$-gap attack strategy attacks all agents when any agent $i$ chooses
an non-target action. Note that the rewards are bounded in $[0,1]$. We have

$\begin{split}\text{Cost}(K,H)=&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\left(\mathbbm{1}(\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k})+|\widetilde{r}_{i,h}^{k}-r_{i,h}^{k}|\right)\\\
\leq&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}[a_{i,h}^{k}\neq\pi_{i,h}^{\dagger}(s_{h}^{k})]m.\end{split}$
(49)

Hence, the attack cost is bounded by $m\mathbbm{E}[\text{Loss1}(K,H)]\leq
m^{2}\mathcal{R}(T)/\eta$.

##  Appendix F Analysis of the gray-box attacks

###  F.1 Proof of Theorem 7

We assume that the agent does not know the attacker’s manipulations and the
presence of the attacker. The attacker’s manipulations on actions are
stationary. We can consider the combination of the attacker and the
environment
$\text{MG}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,P,\\{R_{i}\\}_{i=1}^{m})$
as a new environment
$\widetilde{\text{MG}}(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{m},H,\widetilde{P},\\{\widetilde{R}_{i}\\}_{i=1}^{m})$,
and the agents interact with the new environment. We define
$\widetilde{Q}_{i}$ and $\widetilde{V}_{i}$ as the $Q$-values and value
functions of the new environment $\widetilde{\text{MG}}$ that each agent $i$
observes.

We first prove that the best response of each agent $i$ towards any policy
$\pi_{-i}$ is $\pi_{i}^{\dagger}$.

From the mixed attack strategy, we have

$\begin{split}\widetilde{Q}_{i,h}^{\pi}(s,\bm{a})=&\mathbbm{1}[a_{i}=\pi_{i,h}^{\dagger}(s)]R_{i,h}(s,\pi_{h}^{\dagger}(s))+\mathbbm{P}_{h}\widetilde{V}_{i,h+1}^{\pi}(s,\pi_{h}^{\dagger}(s)).\end{split}$
(50)

Consider an arbitrary policy $\pi$ and an arbitrary initial state $s_{1}$. We
have

$\begin{split}&\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})\\\
=&\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\mathbbm{D}_{\pi}[\widetilde{Q}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}](s_{1})+\mathbbm{D}_{\pi}[\widetilde{Q}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}](s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})\\\
=&\mathbbm{E}_{a_{i,1}\sim\pi_{i,1}(\cdot|s_{1})}\left[\mathbbm{1}[a_{i,1}\neq\pi_{i,1}^{\dagger}(s_{1})]R_{i,1}(s_{1},\pi_{1}^{\dagger}(s_{1}))\right]+\mathbbm{P}_{1}\widetilde{V}_{i,2}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1},\pi_{1}^{\dagger}(s_{1}))-\mathbbm{P}_{1}\widetilde{V}_{i,2}^{\pi}(s_{1},\pi_{1}^{\dagger}(s_{1}))\\\
=&\mathbbm{E}_{a_{i,1}\sim\pi_{i,1}(\cdot|s_{1})}\left[\mathbbm{1}[a_{i,1}\neq\pi_{i,1}^{\dagger}(s_{1})]R_{i,1}(s_{1},\pi_{1}^{\dagger}(s_{1}))\right]+\mathbbm{P}_{1}[\widetilde{V}_{i,2}^{\pi_{i}^{\dagger}\times\pi_{-i}}-\widetilde{V}_{i,2}^{\pi}](s_{1},\pi_{1}^{\dagger}(s_{1}))\\\
=&\cdots=\mathbb{E}_{\pi,\mathbbm{A},P}\left[\sum_{h=1}^{H}\left(1-\pi_{i,h}\left(\pi_{i,h}^{\dagger}(s_{h})|s_{h}\right)\right)R_{i,h}(s_{h},\pi_{h}^{\dagger}(s_{h}))\right]\geq
0.\end{split}$ (51)

Since $R_{i,h}(s_{h},\pi_{h}^{\dagger}(s_{h}))>0$,
$\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi}(s_{1})=0$
holds if and only if $\pi_{i}^{\dagger}=\pi_{i}$ holds for the states that are
reachable under policy $\pi^{\dagger}$. We conclude that the best response of
each agent $i$ towards any policy $\pi_{-i}$ is $\pi_{i}^{\dagger}$ under the
mixed attack strategy. The target policy $\pi^{\dagger}$ is an NE, CE, CCE
under the mixed attack strategy.

Now we prove that the target policy $\pi^{\dagger}_{i}$ is the unique {NE, CE,
CCE} under the mixed attack strategy, when every state $s\in\mathcal{S}$ is
reachable at every step $h\in[H]$ under the target policy.

If there exists an CCE $\pi^{\prime}$ under the mixed attack strategy, we have
$\max_{i\in[m]}(\widetilde{V}_{i,1}^{{\dagger},\pi^{\prime}_{-i}}(s)-\widetilde{V}_{i,1}^{\pi^{\prime}}(s))=0$
for any initial state $s$.

From (51), we have that if
$\pi^{\prime}_{i,h}(\cdot|s)\neq\pi^{\dagger}_{i,h}(\cdot|s)$ at a reachable
state $s$,
$\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi^{\prime}_{-i}}(s_{1})-\widetilde{V}_{i,1}^{\pi^{\prime}}(s_{1})>0$.
Then
$\widetilde{V}_{i,1}^{{\dagger},\pi^{\prime}_{-i}}(s_{1})>\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi^{\prime}_{-i}}(s_{1})>\widetilde{V}_{i,1}^{\pi^{\prime}}(s_{1})$.
$\pi^{\prime}$ is not an CCE in this case.

We can conclude that $\pi^{\prime}=\pi^{\dagger}$ for the states that are
reachable under policy $\pi^{\prime}$. If every state $s\in\mathcal{S}$ is
reachable at every step $h\in[H]$ under the target policy, $\pi^{\dagger}$ is
the unique {NE, CE, CCE}.

###  F.2 Proof of Theorem 8

We set
$R_{min}=\min_{h\in[H]}\min_{s\in\mathcal{S}}\min_{i\in[m]}R_{i,h}(s,\pi^{\dagger}_{h}(s))$.
From the definition of the best-in-hindsight regret and (51), we have

$\begin{split}\text{Reg}_{i}(K,H)=&\max_{\pi_{i}^{\prime}}\sum_{k=1}^{K}[\widetilde{V}_{i,1}^{\pi_{i}^{\prime}\times\pi^{k}_{-i}}(s_{1}^{k})-\widetilde{V}_{i,1}^{\pi^{k}}(s_{1}^{k})]\\\
\geq&\sum_{k=1}^{K}[\widetilde{V}_{i,1}^{\pi_{i}^{\dagger}\times\pi^{k}_{-i}}(s_{1}^{k})-\widetilde{V}_{i,1}^{\pi^{k}}(s_{1}^{k})]\\\
=&\sum_{k=1}^{K}\mathbb{E}_{\pi^{k},\mathbbm{A},P}\left[\sum_{h=1}^{H}\left(1-\pi^{k}_{i,h}\left(\pi_{i,h}^{\dagger}(s_{h}^{k})|s_{h}^{k}\right)\right)R_{i,h}(s_{h}^{k},\pi_{h}^{\dagger}(s_{h}^{k}))\right]\\\
=&\sum_{k=1}^{K}\mathbb{E}_{\pi^{k},\mathbbm{A},P}\left[\sum_{h=1}^{H}\mathbbm{1}[a_{i,h}^{k}\neq\pi_{i,h}^{\dagger}(s_{h}^{k})]R_{i,h}(s_{h}^{k},\pi_{h}^{\dagger}(s_{h}^{k}))\right]\\\
\geq&R_{min}\sum_{k=1}^{K}\mathbb{E}_{\pi^{k},\mathbbm{A},P}\left[\sum_{h=1}^{H}\mathbbm{1}[a_{i,h}^{k}\neq\pi_{i,h}^{\dagger}(s_{h}^{k})]\right]\\\
\end{split}$ (52)

and

$\sum_{i=1}^{m}\text{Reg}_{i}(K,H)\geq R_{min}\mathbb{E}[\text{Loss1}(K,H)].$
(53)

If the best-in-hindsight regret $\text{Reg}(K,H)$ of each agent’s algorithm is
bounded by a sub-linear bound $\mathcal{R}(T)$ under the mixed attack
strategy, then the attack loss is bounded by
$\mathbbm{E}[\text{Loss1}(K,H)]\leq m\mathcal{R}(T)/R_{min}$.

The mixed attack strategy only attacks agent $i$ when agent $i$ chooses a non-
target action. We have

$\begin{split}\text{Cost}(K,H)=&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\left(\mathbbm{1}(\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k})+|\widetilde{r}_{i,h}^{k}-r_{i,h}^{k}|\right)\\\
\leq&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}[\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k}]\left(1+1\right).\end{split}$ (54)

Then, the attack cost is bounded by $2\mathbbm{E}[\text{Loss1}(K,H)]\leq
2m\mathcal{R}(T)/R_{min}$.

##  Appendix G Analysis of the black-box attacks

###  G.1 Proof of Lemma 1

We denote by $\overline{Q}_{{\dagger},h}^{k}$,
$\underline{Q}_{{\dagger},h}^{k}$, $\overline{V}_{{\dagger},h}^{k}$
$\underline{V}_{{\dagger},h}^{k}$, $N_{h}^{k}$, $\hat{\mathbbm{P}}_{h}^{k}$,
$\pi_{h}^{k}$ and $\hat{R}_{{\dagger},h}^{k}$ the observations of the
approximate mixed attacker at the beginning of episode $k$ and time step $h$.
As before, we begin with proving that the estimations are indeed upper and
lower bounds of the corresponding $Q$-values and state value functions. We use
$\pi^{*}$ to denote the optimal policy that maximizes the attacker’s rewards,
i.e. $V_{{\dagger},1}^{\pi^{*}}(s)=\max_{\pi}V_{{\dagger},1}^{\pi}(s)$.

###### Lemma 2

With probability $1-p$, for any $(s,\bm{a},h)$ and $k\leq\tau$,

$\overline{Q}_{{\dagger},h}^{k}(s,\bm{a})\geq{Q}_{{\dagger},h}^{\pi^{*}}(s,\bm{a}),~{}\underline{Q}_{{\dagger},h}^{k}(s,\bm{a})\leq{Q}_{{\dagger},h}^{\pi^{k}}(s,\bm{a}),$
(55)
$\overline{V}_{{\dagger},h}^{k}(s)\geq{V}_{{\dagger},h}^{\pi^{*}}(s),~{}\underline{V}_{{\dagger},h}^{k}(s)\leq{V}_{{\dagger},h}^{\pi^{k}}(s).$
(56)

#### Proof.

For each fixed $k$, we prove this by induction from $h=H+1$ to $h=1$. For the
step $H+1$, we have
$\overline{V}_{{\dagger},H+1}^{k}=\underline{V}_{{\dagger},H+1}^{k}={Q}_{{\dagger},H+1}^{\pi^{*}}=\bm{0}$.
Now, we assume inequality (56) holds for the step $h+1$. By the definition of
$Q$-values and Algorithm 1, we have

$\begin{split}&\overline{Q}_{{\dagger},h}^{k}(s,\bm{a})-{Q}_{{\dagger},h}^{\pi^{*}}(s,\bm{a})\\\
=&\hat{R}_{{\dagger},h}^{k}(s,\bm{a})-R_{{\dagger},h}^{k}(s,\bm{a})+\hat{\mathbbm{P}}_{h}^{k}\overline{V}_{{\dagger},h+1}^{k}(s,\bm{a})-\mathbbm{P}_{h}{V}_{i,h}^{\pi^{*}}(s,\bm{a})+B(N_{h}^{k}(s,\bm{a}))\\\
=&\hat{\mathbbm{P}}_{h}^{k}(\overline{V}_{{\dagger},h+1}^{k}-{V}_{{\dagger},h}^{\pi^{*}})(s,\bm{a})+(\hat{R}_{{\dagger},h}^{k}-R_{{\dagger},h}^{k})(s,\bm{a})+(\hat{\mathbbm{P}}_{h}^{k}-\mathbbm{P}_{h}){V}_{{\dagger},h}^{\pi^{*}}(s,\bm{a})+B(N_{h}^{k}(s,\bm{a})).\end{split}$
(57)

Recall that $B(N)=(H\sqrt{S}+1)\sqrt{\log(2AH\tau/p)/(2N)}$. By Azuma-
Hoeffding inequality, we have that with probability $1-2p/SAH$,

$\forall
k\leq\tau,\left|\hat{R}_{{\dagger},h}^{k}(s,\bm{a})-R_{{\dagger},h}^{k}(s,\bm{a})\right|\leq\sqrt{\frac{\log(2SAH\tau/p)}{2N_{h}^{k}(s,\bm{a})}},$
(58)

and

$\forall
k\leq\tau,\left|(\hat{\mathbbm{P}}_{h}^{k}-\mathbbm{P}_{h}){V}_{{\dagger},h}^{\pi^{*}}(s,\bm{a})\right|\leq
H\sqrt{\frac{S\log(2SAH\tau/p)}{2N_{h}^{k}(s,\bm{a})}}.$ (59)

Putting everything together, we have
$\overline{Q}_{{\dagger},h}^{k}(s,\bm{a})-{Q}_{{\dagger},h}^{\pi^{*}}(s,\bm{a})\geq\hat{\mathbbm{P}}_{h}^{k}(\overline{V}_{{\dagger},h+1}^{k}-{V}_{{\dagger},h}^{\pi^{*}})(s,\bm{a})\geq
0$. Similarly,
$\underline{Q}_{{\dagger},h}^{k}(s,\bm{a})\leq{Q}_{{\dagger},h}^{\pi^{k}}(s,\bm{a})$.

Now we assume inequality (55) holds for the step $h$. As discussed above, if
inequality (56) holds for the step $h+1$, inequality (55) holds for the step
$h$. By Algorithm 1, we have

$\begin{split}&\overline{V}_{{\dagger},h}^{k}(s)=\overline{Q}_{{\dagger},h}^{k}(s,\pi_{h}^{k}(s))\geq\overline{Q}_{{\dagger},h}^{k}(s,\pi_{h}^{*}(s))\geq{Q}_{{\dagger},h}^{\pi^{*}}(s,\pi_{h}^{*}(s))={V}_{{\dagger},h}^{\pi^{*}}(s).\end{split}$
(60)

Similarly,
$\underline{V}_{{\dagger},h}^{k}(s)\leq{V}_{{\dagger},h}^{\pi^{k}}(s)$.
$\hfill\square$

Now, we are ready to prove Lemma 1. By Azuma-Hoeffding inequality, we have
that with probability $1-2p$,

$\begin{split}&\left|\left(\mathbbm{E}_{s_{1}\sim
P_{0}(\cdot)}-\mathbb{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}(\cdot)}\right)\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{k}}(s_{1})\right]\right|\leq
H\sqrt{\frac{S\log(2\tau/p)}{2k}},\end{split}$ (61)

and $\forall k\leq\tau$,

$\begin{split}&\left|\sum_{k^{\prime}=1}^{k}\left(\mathbbm{E}_{s_{1}\sim
P_{0}(\cdot)}-\mathbbm{1}(s_{1}=s_{1}^{k^{\prime}})\right)\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{k^{\prime}}}(s_{1})\right]\right|\leq
H\sqrt{\frac{S\log(2\tau/p)}{2k}}.\end{split}$ (62)

Thus, for any $k\leq\tau$,

$\begin{split}&\mathbbm{E}_{s_{1}\sim
P_{0}(\cdot)}\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{k}}(s_{1})\right]\\\
\leq&\mathbbm{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}^{k}(\cdot)}\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{k}}(s_{1})\right]+H\sqrt{S\log(2\tau/p)/(2k)}\\\
\leq&\mathbb{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}^{k}(\cdot)}\left[\overline{V}_{{\dagger},1}^{k}(s_{1})-\underline{V}_{{\dagger},1}^{k}(s_{1})\right]+H\sqrt{S\log(2\tau/p)/(2k)}.\end{split}$
(63)

According to (61) and (62), we have

$\begin{split}&\sum_{k=1}^{\tau}\left(\mathbb{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}^{k}(\cdot)}\left[\overline{V}_{{\dagger},1}^{k}(s_{1})-\underline{V}_{{\dagger},1}^{k}(s_{1})\right]+H\sqrt{S\log(2\tau/p)/(2k)}\right)\\\
\leq&\sum_{k=1}^{\tau}\left(\overline{V}_{{\dagger},1}^{k}(s_{1}^{k})-\underline{V}_{{\dagger},1}^{k}(s_{1}^{k})\right)+\sum_{k=1}^{\tau}3H\sqrt{S\log(2\tau/p)/(2k)}.\end{split}$
(64)

We define $\Delta
V_{h}^{k}(s)=\overline{V}_{{\dagger},h}^{k}(s)-\underline{V}_{{\dagger},h}^{k}(s)$,
$\Delta
Q_{h}^{k}(s,\bm{a})=\overline{Q}_{{\dagger},h}^{k}(s,\bm{a})-\underline{Q}_{{\dagger},h}^{k}(s,\bm{a})$.
By the update equations in Algorithm 1, we have $\Delta
Q_{h}^{k}(s,\bm{a})\leq\hat{\mathbbm{P}}_{h}^{k}\Delta
V_{h+1}^{k}(s,\bm{a})+2B(N_{h}^{k}(s,\bm{a}))$ and $\Delta V_{h}^{k}(s)=\Delta
Q_{h}^{k}(s,\pi_{h}^{k}(s))$. We define $\psi_{h}^{k}=\Delta
V_{h}^{k}(s_{h}^{k})=\Delta Q_{h}^{k}(s_{h}^{k},a_{h}^{k})$. From (59) and
(66), we have

$\begin{split}\psi_{h}^{k}\leq&\hat{\mathbbm{P}}_{h}^{k}\Delta
V_{h+1}^{k}(s_{h}^{k},\bm{a_{h}^{k}})+2B(N_{h}^{k}(s_{h}^{k},\bm{a}_{h}^{k}))\\\
\leq&\mathbbm{P}_{h}^{k}\Delta
V_{h+1}^{k}(s_{h}^{k},\bm{a_{h}^{k}})+3B(N_{h}^{k}(s_{h}^{k},\bm{a}_{h}^{k}))\\\
\leq&\mathbbm{P}_{h}^{k}\Delta
V_{h+1}^{k}(s_{h}^{k},\bm{a_{h}^{k}})-\psi_{h+1}^{k}+\psi_{h+1}^{k}+3B(N_{h}^{k}(s_{h}^{k},\bm{a}_{h}^{k})).\end{split}$
(65)

By Azuma-Hoeffding inequality, we have that with probability $1-p/H$, $\forall
k\leq\tau$,

$\begin{split}&\left|\sum_{k^{\prime}=1}^{k}|\mathbbm{P}_{h}^{k^{\prime}}\Delta
V_{h+1}^{k}(s_{h}^{k^{\prime}},\bm{a_{h}^{k^{\prime}}})-\psi_{h+1}^{k^{\prime}}|\right|\leq
H\sqrt{\frac{S\log(2H\tau/p)}{2k}}.\end{split}$ (66)

Since $\psi_{H+1}^{k}=0$ for all $k$, we have

$\begin{split}\sum_{k=1}^{\tau}\psi_{1}^{k}\leq&\sum_{k=1}^{\tau}\sum_{h=1}^{H}|\mathbbm{P}_{h}^{k}\Delta
V_{h+1}^{k}(s_{h}^{k},\bm{a_{h}^{k}})-\psi_{h+1}^{k}|+\sum_{k=1}^{\tau}\sum_{h=1}^{H}3B(N_{h}^{k}(s_{h}^{k},\bm{a}_{h}^{k}))\\\
\leq&\sum_{h=1}^{H}H\sqrt{\frac{S\log(2H\tau/p)}{2\tau}}+\sum_{h=1}^{H}\sum_{(s,\bm{a})}\sum_{n=1}^{N_{h}^{\tau}(s,\bm{a})}(H\sqrt{S}+1)\sqrt{\frac{\log(2SAH\tau/p)}{2n}}\\\
\leq&H^{2}\sqrt{\frac{S\log(2H\tau/p)}{2\tau}}+H(H\sqrt{S}+1)\sqrt{2SA\tau\log(2SAH\tau/p)}\end{split}$
(67)

and therefore

$\begin{split}&\sum_{k=1}^{\tau}\left(\mathbb{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}^{k}(\cdot)}\left[\overline{V}_{{\dagger},1}^{k}(s_{1})-\underline{V}_{{\dagger},1}^{k}(s_{1})\right]+H\sqrt{S\log(2\tau/p)/(2k)}\right)\\\
\leq&H^{2}\sqrt{\frac{S\log(2H\tau/p)}{2\tau}}+3H\sqrt{2S\tau\log(2\tau/p)}+H(H\sqrt{S}+1)\sqrt{2SA\tau\log(2SAH\tau/p)}.\end{split}$
(68)

Since

$\begin{split}\pi^{\dagger}=\min_{\pi_{k}}&\left(\mathbbm{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}^{k}(\cdot)}\left[\sum_{i=1}^{m}\left({V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{k}}(s_{1})\right)\right]+H\sqrt{S\log(2\tau/p)/(2k)}\right),\end{split}$
(69) $\begin{split}&\mathbbm{E}_{s_{1}\sim
P_{0}(\cdot)}\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{\dagger}}(s_{1})\right]\\\
\leq&\mathbbm{E}_{s_{1}\sim\hat{\mathbbm{P}}_{0}^{k}(\cdot)}\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1})-{V}_{{\dagger},1}^{\pi^{\dagger}}(s_{1})\right]+H\sqrt{S\log(2\tau/p)/(2k)}\\\
\leq&H^{2}\sqrt{\frac{S\log(2H\tau/p)}{2\tau^{3}}}+3H\sqrt{2S\log(2\tau/p)/\tau}+H(H\sqrt{S}+1)\sqrt{2SA\log(2SAH\tau/p)/\tau}\\\
\leq&2H^{2}S\sqrt{2A\log(2SAH\tau/p)/\tau},\end{split}$ (70)

where the last inequality holds when $S,H,A\geq 2$. Similarly,

$\begin{split}&\sum_{k=1}^{K}\left[{V}_{{\dagger},1}^{\pi^{*}}(s_{1}^{k})-{V}_{{\dagger},1}^{\pi^{\dagger}}(s_{1}^{k})\right]\leq
2H^{2}S\sqrt{2A\log(2SAH\tau/p)/\tau}.\end{split}$ (71)

###  G.2 Proof of Theorem 9

For completeness, we describe the main steps of V-learning algorithm [15] in
Algorithm 2 and the adversarial bandit algorithm in Algorithm 3.

1: For any $(s,a,h)$, $V_{h}(s)\leftarrow H+1-h$, $N_{h}(s)\leftarrow 0$,
$\pi_{h}(a|s)\leftarrow 1/A$.

2: for episodes $k=1,\dots,K$ do

3: receive $s_{1}$

4: for episodes $h=1,\dots,H$ do

5: take action $a_{h}\sim\pi_{h}(\cdot|s_{h})$, observe reward $r_{h}$ and
next state $s_{h+1}$.

6: $t=N_{h}(s_{h})\leftarrow N_{h}(s_{h})+1.$

7:
$\overline{V}_{h}(s_{h})\leftarrow(1-\alpha_{t})\overline{V}_{h}(s_{h})+\alpha_{t}(rh+V_{h+1}(s_{h+1})+\beta_{t})$.

8: $V_{h}(s_{h})\leftarrow\min\\{H+1-h,\overline{V}_{h}(s_{h})\\}$

9:
$\pi_{h}(\cdot|s_{h})\leftarrow\text{ADV\\_BANDIT\\_UPDATE}(a_{h},\frac{H-r_{h}-V_{h+1}(s_{h+1})}{H})$
on $(s_{h},h)^{th}$ adversarial bandit.

10: end for

11: end for

Algorithm 2 V-learning [15]

1: For any $b\in\mathcal{B}$, $\theta_{1}(b)\leftarrow 1/B$.

2: for episode $t=1,\dots,K$ do

3: Take action $b_{t}\sim\theta_{t}(\cdot)$, and observe loss
$\widetilde{l}_{t}(b_{t})$.

4:
$\hat{l}_{t}(b)\leftarrow\widetilde{l}_{t}(b_{t})\mathbbm{1}[b_{t}=b]/(\theta_{t}(b)+\gamma_{t})$
for all $b\in\mathcal{B}$.

5:
$\theta_{t+1}(b)\propto\exp[-(\gamma_{t}/w_{t})\sum_{i=1}^{t}w_{i}\hat{l}_{i}(b)]$

6: end for

Algorithm 3 FTRL for Weighted External Regret [15]

We use the same learning rate $\alpha_{t}$ in [15]. We also use an auxiliary
sequence $\\{\alpha_{t}^{i}\\}_{i=1}^{t}$ defined in [15] based on the
learning rate, which will be frequently used in the proof:

$\alpha_{t}=\frac{H+1}{H+t},~{}\alpha_{t}^{0}=\prod_{j=1}^{t}(1-\alpha_{j}),~{}\alpha_{t}^{i}=\alpha_{i}\prod_{j=i+1}^{t}(1-\alpha_{j}).$
(72)

We follow the requirement for the adversarial bandit algorithm used in
V-learning, which is to have a high probability weighted external regret
guarantee as follows.

###### Assumption 1

For any $t\in\mathbbm{N}$ and any $\delta\in(0,1)$, with probability at least
$1-\delta$, we have

$\max_{\theta}\sum_{j=1}^{t}\alpha_{t}^{j}[\langle\theta_{j},l_{j}\rangle-\langle\theta,l_{j}\rangle]\leq\xi(B,t,\log(1/\delta)).$
(73)

In addition, there exists an upper bound
$\Xi(B,t,\log(1/\delta))\geq\sum_{t^{\prime}=1}^{t}\xi(B,t,\log(1/\delta))$
where (i) $\xi(B,t,\log(1/\delta))$ is non-decreasing in $B$ for any $t$,
$\delta$; (ii) $\Xi(B,t,\log(1/\delta))$ is concave in $t$ for any $B$,
$\delta$.

In particular, it was proved in [15] that the Follow-the-Regularized-Leader
(FTRL) algorithm (Algorithm 3) satisfies Assumption 1 with bounds
$\xi(B,t,\log(1/\delta))\leq\mathcal{O}(\sqrt{HB\log(B/\delta)/t})$ and
$\Xi(B,t,\log(1/\delta))\leq\mathcal{O}(\sqrt{HBt\log(B/\delta)})$. By
choosing hyper-parameter
$w_{t}=\alpha_{t}\left(\prod_{i=2}^{t}(1-\alpha_{i})\right)^{-1}$ and
$\gamma_{t}=\sqrt{\frac{H\log B}{Bt}}$,
$\xi(B,t,\log(1/\delta))=10\sqrt{HB\log(B/\delta)/t}$ and
$\Xi(B,t,\log(1/\delta))=20\sqrt{HBt\log(B/\delta)}$.

We use $V^{k}$, $N^{k}$, $\pi^{k}$ to denote the value, counter and policy
maintained by V-learning algorithm at the beginning of the episode $k$.
Suppose $s$ was previously visited at episodes $k^{1},\cdots,k^{t}<k$ at the
step $h$. Set $t^{\prime}$ such that $k^{t^{\prime}}\leq\tau$ and
$k^{t^{\prime}+1}>\tau$.

In the exploration phase of the proposed approximate mixed attack strategy,
the rewards are equal to $1$ for any state $s$, any action $\bm{a}$, any agent
$i$ and any step $h$. The loss updated to the adversarial bandit update step
in Algorithm 2 is equal to $\frac{h-1}{H}$.

In the attack phase, the expected loss updated to the adversarial bandit
update step in Algorithm 2 is equal to

$\sum_{j=1}^{t^{\prime}}\alpha_{t}^{j}\frac{h-1}{H}+\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\mathbbm{D}_{\pi^{\dagger}}\left(\frac{H-\mathbbm{P}_{h}V_{i,h+1}^{k^{j}}}{H}\right)(s)+\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\mathbbm{D}_{\pi^{k^{j}}_{h}}\left(\frac{-\widetilde{r}_{i,h}}{H}\right)(s).$
(74)

Thus, in both of the exploration phase and the attack phase, $\pi^{\dagger}$
is the best policy for the adversarial bandit algorithm.

By Assumption 1 and the adversarial bandit update step in Algorithm 2, with
probability at least $1-\delta$, for any $(s,h)\in\mathcal{S}\times[H]$ and
any $k>\tau$, we have

$\begin{split}\xi(A,t,\iota)\geq&\sum_{j=1}^{t^{\prime}}\alpha_{t}^{j}\frac{h-1}{H}+\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\mathbbm{D}_{\pi^{\dagger}}\left(\frac{H-\mathbbm{P}_{h}V_{i,h+1}^{k^{j}}}{H}\right)(s)+\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\mathbbm{D}_{\pi^{k^{j}}_{h}}\left(\frac{-\widetilde{r}_{i,h}}{H}\right)(s)\\\
&-\sum_{j=1}^{t^{\prime}}\alpha_{t}^{j}\frac{h-1}{H}+\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\mathbbm{D}_{\pi^{\dagger}}\left(\frac{H-\mathbbm{P}_{h}V_{i,h+1}^{k^{j}}}{H}\right)(s)+\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\mathbbm{D}_{\pi^{\dagger}}\left(\frac{-\widetilde{r}_{i,h}}{H}\right)(s)\\\
=&\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\left(1-\pi^{k^{j}}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right)\frac{r_{i,h}(s,\pi^{\dagger}_{h}(s))}{H},\end{split}$
(75)

where $\iota=\log(mHSAK/\delta)$.

Note that
$R_{min}=\min_{h\in[H]}\min_{s\in\mathcal{S}}\min_{i\in[m]}R_{i,h}(s,\pi^{\dagger}_{h}(s))$.
We have

$\begin{split}\frac{H}{R_{min}}\xi(A,t,\iota)\geq\sum_{j=t^{\prime}+1}^{t}\alpha_{t}^{j}\left(1-\pi^{k^{j}}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right).\end{split}$
(76)

Let $n_{h}^{k}=N_{h}^{k}(s_{h}^{k})$ and suppose $s_{h}^{k}$ was previously
visited at episodes $k^{1},\cdots,k^{n_{h}^{k}}<k$ at the step $h$. Let
$k^{j}(s)$ denote the episode that $s$ was visited in $j$-th time.

$\begin{split}\frac{H}{R_{min}}\xi(A,n_{h}^{k},\iota)\geq\sum_{j=N_{h}^{\tau}(s_{h}^{k})+1}^{n_{h}^{k}}\alpha_{n_{h}^{k}}^{j}\left(1-\pi^{k^{j}}_{i,h}(\pi^{\dagger}_{i,h}(s_{h}^{k})|s_{h}^{k})\right).\end{split}$
(77)

According to the property of the learning rate $\alpha_{t}$, we have

$\begin{split}\frac{H}{R_{min}\alpha_{t}^{t}}\xi(A,n_{h}^{k},\iota)+\sum_{j=N_{h}^{\tau}(s_{h}^{k})+1}^{n_{h}^{k}-1}\frac{H}{R_{min}}\xi(A,j,\iota)\leq\sum_{j=N_{h}^{\tau}(s_{h}^{k})+1}^{n_{h}^{k}}\left(1-\pi^{k^{j}}_{i,h}(\pi^{\dagger}_{i,h}(s_{h}^{k})|s_{h}^{k})\right).\end{split}$
(78)

Then,

$\begin{split}\frac{40H}{R_{min}}\sqrt{HAn_{h}^{k}\iota}\leq\sum_{j=N_{h}^{\tau}(s_{h}^{k})+1}^{n_{h}^{k}}\left(1-\pi^{k^{j}}_{i,h}(\pi^{\dagger}_{i,h}(s_{h}^{k})|s_{h}^{k})\right).\end{split}$
(79)

Computing the summation of the above inequality over $h$ and $s$, we have

$\begin{split}&\mathbb{E}\left[\sum_{h=1}^{H}\sum_{k=\tau+1}^{K}\mathbbm{1}[a_{i,h}^{k}\neq\pi_{i,h}^{\dagger}(s_{h}^{k})]\right]\\\
=&\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\sum_{j=N_{h}^{\tau}(s)+1}^{N_{h}^{K}(s)}\left(1-\pi^{k^{j}(s)}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right)\\\
\leq&\sum_{s\in\mathcal{S}}\frac{40}{R_{min}}\sqrt{H^{5}AN_{h}^{K}(s)\iota}\\\
\leq&\frac{40}{R_{min}}\sqrt{H^{5}ASK\iota}.\end{split}$ (80)

In the exploration phase, the loss at each episode is up to $H$. In the attack
phase, the expected number of episodes that the agents do not follow
$\pi^{\dagger}$ is up to $\frac{40}{R_{min}}m\sqrt{H^{7}ASK\iota}$.

According to Lemma 1, the attack loss is bounded by

$\begin{split}\mathbb{E}\left[\text{loss}(K,H)\right]\leq
H\tau+\frac{40}{R_{min}}m\sqrt{H^{9}ASK\iota}+2H^{2}SK\sqrt{2A\iota/\tau}.\end{split}$
(81)

In the exploration phase, the approximate mixed attack strategy attacks at any
step and any episode. In the attack phase, the approximate mixed attack
strategy only attacks agent $i$ when agent $i$ chooses a non-target action. We
have

$\begin{split}\text{Cost}(K,H)=&\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\left(\mathbbm{1}(\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k})+|\widetilde{r}_{i,h}^{k}-r_{i,h}^{k}|\right)\\\
\leq&\sum_{k=1}^{\tau}\sum_{h=1}^{H}\sum_{i=1}^{m}(1+1)+\sum_{k=\tau=1}^{K}\sum_{h=1}^{H}\sum_{i=1}^{m}\mathbbm{1}[\widetilde{a}_{i,h}^{k}\neq
a_{i,h}^{k}]\left(1+1\right).\end{split}$ (82)

Then, the attack cost is bounded by

$\begin{split}\mathbb{E}\left[\text{Cost}(K,H)\right]\leq
2mH\tau+\frac{80}{R_{min}}\sqrt{H^{5}ASK\iota}.\end{split}$ (83)

For the executing output policy $\hat{\pi}$ of V-learning, we have

$\begin{split}&1-\hat{\pi}_{i,h}(\pi_{i,h}^{\dagger}(s)|s)\\\
=&\frac{1}{K}\sum_{k=1}^{K}\sum_{j=1}^{N_{h}^{k}(s)}\alpha_{N_{h}^{k}(s)}^{j}\left(1-\pi^{k^{j}(s)}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right)\\\
=&\frac{1}{K}\sum_{k=\tau+1}^{K}\sum_{j=N_{h}^{\tau}(s)+1}^{N_{h}^{k}(s)}\alpha_{N_{h}^{k}(s)}^{j}\left(1-\pi^{k^{j}(s)}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right)+\frac{1}{K}\sum_{k=1}^{\tau}\sum_{j=1}^{N_{h}^{k}(s)}\alpha_{N_{h}^{k}(s)}^{j}\left(1-\pi^{k^{j}(s)}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right)\\\
&+\frac{1}{K}\sum_{k=\tau+1}^{K}\sum_{j=1}^{N_{h}^{\tau}(s)}\alpha_{N_{h}^{k}(s)}^{j}\left(1-\pi^{k^{j}(s)}_{i,h}(\pi^{\dagger}_{i,h}(s)|s)\right)\\\
\leq&\frac{20}{R_{min}}\sqrt{\frac{H^{3}A\iota}{K}}+\frac{2\tau}{K}.\end{split}$
(84)

The probability that the agents with $\hat{\pi}$ do not follow the target
policy is bounded by
$\frac{20mS}{R_{min}}\sqrt{\frac{H^{5}A\iota}{K}}+\frac{2\tau mSH}{K}$.

According to Lemma 1, the attack loss of the executing output policy
$\hat{\pi}$ is upper bounded by

$\begin{split}&V_{{\dagger},1}^{\pi^{*}}(s_{1})-V_{{\dagger},1}^{\hat{\pi}}(s_{1})\leq
H\left(\frac{20mS}{R_{min}}\sqrt{\frac{H^{5}A\iota}{K}}+\frac{2\tau
mSH}{K}\right)+2H^{2}S\sqrt{2A\iota/\tau}.\end{split}$ (85)