# Optimal Attack and Defense for Reinforcement Learning

Jeremy McMahan, Young Wu, Xiaojin Zhu, Qiaomin Xie

###### Abstract

To ensure the usefulness of Reinforcement Learning (RL) in real systems, it is
crucial to ensure they are robust to noise and adversarial attacks. In
adversarial RL, an external attacker has the power to manipulate the victim
agent’s interaction with the environment. We study the full class of online
manipulation attacks, which include (i) state attacks, (ii) observation
attacks (which are a generalization of perceived-state attacks), (iii) action
attacks, and (iv) reward attacks. We show the attacker’s problem of designing
a stealthy attack that maximizes its own expected reward, which often
corresponds to minimizing the victim’s value, is captured by a Markov Decision
Process (MDP) that we call a meta-MDP since it is not the true environment but
a higher level environment induced by the attacked interaction. We show that
the attacker can derive optimal attacks by planning in polynomial time or
learning with polynomial sample complexity using standard RL techniques. We
argue that the optimal defense policy for the victim can be computed as the
solution to a stochastic Stackelberg game, which can be further simplified
into a partially-observable turn-based stochastic game (POTBSG). Neither the
attacker nor the victim would benefit from deviating from their respective
optimal policies, thus such solutions are truly robust. Although the defense
problem is NP-hard, we show that optimal Markovian defenses can be computed
(learned) in polynomial time (sample complexity) in many scenarios.

##  1 Introduction

Reinforcement Learning (RL) has become a staple with a plethora of
applications including the breakthrough ChatGPT [16]. With the growth of RL
applications, it is critical to understand the security threats posed to RL
and how to defend against them. In many applications, noisy measurements can
cause the agent-environment interaction to evolve entirely differently than
what one would expect in theory. Even worse, malicious attackers can
strategically modify the agent-environment interaction to induce catastrophic
outcomes for the agent. If RL methods are to be used in diverse and critical
settings, it is essential to ensure these RL algorithms are robust to
potential attacks.

In adversarial RL, a victim agent interacts with an environment while being
disrupted by an attacker. The attacker has the power to manipulate each aspect
of the victim-environment interaction. In particular, the attacker can change:
(i) the environment’s state (_state attacks_), (ii) the victim’s observation
(_observation attacks_), (iii) the action taken by the victim (_action
attacks_), and (iv) the reward received by the victim (_reward attacks_). When
the environment is fully-observable, observation attacks translate to well-
studied _perceived-state attacks_. We refer to all of these attack surfaces by
_online manipulation attacks_. The attacker may use a subset or all of these
attack surfaces to optimize its own expected reward from the attack, which
often corresponds to minimizing the victim’s value. However, the attacker
cannot perform arbitrary manipulations without raising suspicion. Hence, the
attacker must restrict its manipulations to a predefined set of stealthy
attacks. On the other hand, the attacker-aware victim seeks to choose a
_defense_ policy whose value is provably robust even under the worst possible
stealthy attack.

From the attacker’s perspective, it faces an optimal control problem: it needs
to strategically choose stealthy attacks to optimize its value. Unlike typical
control problems, the attacker must deal with the uncertainty of the victim’s
actions in addition to that of the stochastic environment. Thus, the
attacker’s problem involves a multi-agent feature. For any fixed victim policy
$\pi$, we can view the attacker’s problem as computing its best response
attack to the victim’s chosen $\pi$. From the victim’s perspective, we argue
it faces a Stochastic Stackelberg game: it needs to choose a policy that
achieves maximum value in the environment under the attacker’s best-response
attack. A defense policy designed following this principle ensures neither the
victim nor the attacker would benefit from deviating from their chosen
policies, and so an equilibrium would be achieved. This implies that
regardless of the attack, the defense policy always achieves at least the
game’s optimal value. However, computing optimal Stackelberg strategies for
stochastic games is NP-hard. Thus, both the attacker and the victim are faced
with challenging optimization problems.

Although the attack and defense problems are of great importance, complete
solutions have yet to be discovered. For the attack problem, most works focus
on the empirical aspects, lacking theoretical guarantees. Provably optimal
attacks have only been devised for the special case of test-time, perceived-
state attacks [19, 28, 22]. The situation is even worse for the defense
problem, which is arguably more important. Nearly all proposed defenses are
designed to be effective against a specific, known attack. This results in a
cat-and-mouse game: the attacker can just design a new attack for the given
defense policy and so the victim would always be at risk. In addition, the two
approaches with provable guarantees are restricted to the planning, reward-
poisoning setting [1], and the test-time, perceived-state attack setting [29].
Furthermore, neither defense can be computed efficiently and it is unrealistic
to assume the victim knows the attacker’s exact algorithm.

#### Our Contributions.

Despite the challenges of the attack and defense problems, we develop
frameworks for computing optimal attacks and defenses for any combination of
attack surfaces, which are provably efficient in many cases. From the
attacker’s side, we show that for any fixed victim policy, the optimal attack
can be computed as the solution to another Markov Decision Process (MDP). We
call this environment a _meta-MDP_ since it is not the true environment, but
is a higher-level environment induced by the victim-attacker-environment
interaction. Importantly, the attacker can simulate an interaction with the
meta-MDP by interacting with the victim and the true environment. Hence, the
attacker can attack optimally by solving the meta-MDP using any standard MDP
planning or RL algorithms. In addition, we show that the size of the meta-MDP
is polynomial in the size of the original environment and the size of the
victim’s policy. Thus, optimal attacks can always be computed or learned
efficiently. Our framework also extends to linear MDPs. Hence, we provide the
first provably optimal attacks for beyond perceived-state attacks and the
first provably optimal attacks for the linear setting, all of which can be
computed in polynomial time. We note our framework also solves the certifying
robustness problem posed in [27].

On the victim’s side, we argue that the defense problem is most naturally
modeled by a stochastic Stackelberg game [26], which can be captured by a much
simpler partially-observable turn-based stochastic game (POTBSG) [7]. Thus,
the victim can compute its optimal robust defense by finding a weak
Stackelberg equilibrium (WSE) for the meta-POTBSG. Again, the victim can
simulate the meta-POTBSG by interacting with the attacker and the true
environment. When the attacker is adversarial, the victim can defend optimally
by solving the meta-POTBSG using any standard zero-sum POTBSG planning or
distributed learning algorithms. Unlike the attack problem, we show that the
victim’s defense problem is NP-hard in general even to find approximate
solutions when observation attacks are permitted. However, we show that
optimal Markovian defenses can be computed efficiently when excluding
observation attacks by exploiting the sequential nature of the attacks. This
gives a broad class of games for which WSE is computable. Overall, we present
the first-ever provable defense algorithms for both the planning and learning
settings and show our defenses can be computed efficiently for a broad class
of instances.

###  1.1 Related Work

Many prior works have studied adversarial RL under various models and
objectives. Amongst the first works, Behzadan and Munir [2], Huang et al. [8],
Kos and Song [10] study perceived-state attacks through the lens of
adversarial examples for deep neural nets [6]. Kos and Song [10] also
considers adversarial examples, but with the goal of minimizing the number of
attacks needed to achieve large damage. These works focused on achieving large
damage at the current time. Later Lin et al. [13], Sun et al. [21] developed
more advanced heuristics that incorporate future value into their attacks to
achieve long-term damage. Meanwhile, Tretschk et al. [24] trained an
adversarial deep net to compute perturbations that allows other objectives for
the attacker.

Afterward, many works began considering the objective of maximizing the damage
to the victim rather than minimizing the number of attacks. Russo and
Proutiere [19], Zhang et al. [28] developed optimal algorithms for computing
perceived-state attacks. Both works formulated the attack problem as a
different MDP as we do here. Sun et al. [22] formulated an actor-director
model for the attack problem that is easier to solve for some MDPs and retains
guarantees of optimality. The idea of adversarial training was then used in
conjunction with the attack formulation from [28] to obtain experimentally
robust victim policies [29].

Action and reward attacks have been considered heavily in the training-time
setting. For example, Tessler et al. [23], Lee et al. [11] considered action
attacks. Reward poisoning attacks are the focus of the work by Zhang et al.
[30], Rangi et al. [18]. In fact, a combination action and reward attack are
devised by Rangi et al. [18]. Most of these works consider the policy teaching
setting, where the attacker’s goal is for the victim to follow a fixed policy
$\pi^{\dagger}$. Some algorithms achieve sublinear regret for the attacker
when the victim policy is no regret [14]; though, none compute truly optimal
attacks.

##  2 Attack Surfaces

#### POMDPs.

We denote a infinite-horizon discounted environment POMDP by
$M=(\mathcal{S},\mathcal{O},\mathcal{A},P,R,\allowbreak\gamma,\mu)$ where (i)
$\mathcal{S}$ is the state set, (ii) $\mathcal{O}$ is the observation set,
(iii) $\mathcal{A}$ is the action set, (iv)
$P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the transition
kernel, (v) $R:\mathcal{S}\times\mathcal{A}\to\Delta(\mathbb{R})$ is the
reward distribution, (vi) $\gamma$ is the discount factor, and (vii)
$\mu\in\Delta(S)$ is the initial state distribution. We let $\mathcal{O}(s)$
denote the distribution of observations at state $s$. We also let
$\mathcal{R}$ denote the set of all supported rewards. The total expected
reward the victim receives from following policy $\pi$ in environment $M$ is
its _value_ , i.e., the expected cumulative discounted rewards
$V^{\pi}_{M}:=\mathbb{E}_{M}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\right]$.

Suppose the victim interacts with a Markovian environment, $M$, using a fixed
stationary, Markovian policy $\pi:\mathcal{O}\to\Delta(A)$. At any time $t$,
let $s_{t}$ denote $M$’s current state and $o_{t}$ denote the generated
observation. In the standard setting, the victim chooses an action
$a_{t}\sim\pi(o_{t})$ and then receives a reward $r_{t}\sim R(s_{t},a_{t})$.
Afterwards, $M$ transitions to its next state $s_{t+1}\sim P(s_{t},a_{t})$. We
see there are several points during time $t$ at which information is exchanged
between the victim and $M$. We further break down the interaction at time $t$
based on these points of information exchange, which we call _subtimes_ :

  1. 1.

At the first subtime, $t_{1}$, $M$ receives its state $s_{t}\sim
P(s_{t-1},a_{t-1})$.

  2. 2.

At the second subtime, $t_{2}$, the victim receives its observation
$o_{t}\sim\mathcal{O}(s_{t})$.

  3. 3.

At the third subtime, $t_{3}$, $M$ receives the victim’s action
$a_{t}\sim\pi(o_{t})$.

  4. 4.

At the fourth subtime, $t_{4}$, the victim receives its reward $r_{t}\sim
R(s_{t},a_{t})$.

#### Online Attacks.

In the adversarial setting, a third-party called the _attacker_ interferes
with the victim-$M$ interaction. Here, the attacker may intercept and then
corrupt the information being exchanged between the victim and environment
$M$. The attacker has access to four attack surfaces:

  1. 1.

(_State Attack_) A state attack changes the state of $M$ from $s_{t}$ to
$s^{\dagger}_{t}$. The attack influences the observation
$o_{t}\sim\mathcal{O}(s^{\dagger}_{t})$. If $M$ receives action $a_{t}$, the
attack also influences the reward $r_{t}\sim R(s^{\dagger}_{t},a_{t})$ and the
next state $s_{t+1}\sim P(s^{\dagger}_{t},a_{t})$.

  2. 2.

(_Observation Attack_) An observation attack causes the victim to receive
observation $o^{\dagger}_{t}$ instead of $o_{t}\sim\mathcal{O}(s_{t})$. The
attack influences the victim’s action $a_{t}\sim\pi(o^{\dagger}_{t})$.

  3. 3.

(_Action Attack_) An action attack causes $M$ to receive action
$a^{\dagger}_{t}$ instead of $a_{t}$. The attack influences the reward
$r_{t}\sim R(s_{t},a^{\dagger}_{t})$ and next state $s_{t+1}\sim
P(s_{t},a^{\dagger}_{t})$.

  4. 4.

(_Reward Attack_) A reward attack causes the victim to receive reward
$r^{\dagger}_{t}$ instead of reward $r_{t}\sim R(s_{t},a_{t})$.

We call each of these attack surfaces as _online manipulation attacks_. These
attack surfaces in conjunction give the attacker the power to corrupt every
element of the triple $(s,a,r)$ that define the interaction between the victim
and $M$.

If $M$ is fully observable, observation attacks correspond to _perceived-
state_ attacks, which change what the victim thinks is $M$’s state. Notice
unlike the other surfaces, state attacks could be performed at two different
subtimes. Namely, the attacker can change the state before $M$ transitions at
$t_{1}$ or before $M$ receives the victim’s action at $t_{3}$. For simplicity,
we assume state attacks only happen at $t_{1}$, but our results apply equally
well to both versions.

#### Adversarial Interaction.

Overall, the victim-attacker-$M$ interaction at time $t$ now evolves as
follows:

  1. 1.

At subtime $t_{1}$, $M$ is in state $s_{t}$.

    1. (a)

Attacker: changes $s_{t}$ to $s^{\dagger}_{t}$.

    2. (b)

$M$: enters state $s^{\dagger}_{t}$ and generates observation
$o_{t}\sim\mathcal{O}(s^{\dagger}_{t})$.

  2. 2.

At subtime $t_{2}$, $M$ is in state $s^{\dagger}_{t}$ and has generated
observation $o_{t}$.

    1. (a)

Attacker: changes $o_{t}$ to $o^{\dagger}_{t}$.

    2. (b)

Victim: chooses action $a_{t}\sim\pi(o^{\dagger}_{t})$.

  3. 3.

At subtime $t_{3}$, $M$ is in state $s^{\dagger}_{t}$ and the victim chose
action $a_{t}$.

    1. (a)

Attacker: changes $a_{t}$ to $a^{\dagger}_{t}$.

    2. (b)

$M$: generates reward $r_{t}\sim R(s^{\dagger}_{t},a^{\dagger}_{t})$ and
generates state $s_{t+1}\sim P(s^{\dagger}_{t},a^{\dagger}_{t})$.

  4. 4.

At subtime $t_{4}$, $M$ has generated reward $r_{t}$.

    1. (a)

Attacker: changes $r_{t}$ to $r^{\dagger}_{t}$.

    2. (b)

Victim: receives reward $r^{\dagger}_{t}$.

This process then repeats starting from $s_{t+1}$.

#### Attacker Constraints.

In general, the attacker may not arbitrarily manipulate the interaction. For
example, some attacks may be physically impossible or risk detection. As such,
we assume the attacker has a set $\mathcal{B}$ that defines the feasible
manipulations it can perform. For example, the attacker might require a
manipulated observation to be visually similar to the true observation. Thus,
the set of feasible observation attacks should depend on the true observation.
Applying the same logic to each attack surface, we see the feasible attack
sets should take the form: $\mathcal{B}(s)\subseteq\mathcal{S}$,
$\mathcal{B}(o)\subseteq\mathcal{O}$, $\mathcal{B}(a)\subseteq\mathcal{A}$,
and $\mathcal{B}(r)\subseteq\mathcal{R}$. However, in some cases, the
feasibility of an attack would depend on the interaction before the attack,
not just the current element being manipulated. To be fully general, we allow
the feasibility sets to take the form: at subtime $t_{1}$,
$\mathcal{B}(s)\subseteq\mathcal{S}$; at subtime $t_{2}$,
$\mathcal{B}(s,o)\subseteq\mathcal{O}$; at subtime $t_{3}$,
$\mathcal{B}(s,o,a)\subseteq\mathcal{A}$; and, at subtime $t_{4}$,
$\mathcal{B}(s,o,a,r)\subseteq\mathcal{R}$.

##  3 Optimal Attacks

#### Attacker’s Goal.

In Section 2, we saw how an attacker can disrupt an interaction but haven’t
discussed why it would do this. Suppose the attacker has a reward function
$g(s,a,r)$ that depends on the victim’s received reward, possibly in addition
to $M$’s state and the victim’s action. The attacker’s goal is then to
construct an attack that maximizes its own expected reward. Commonly, an
attacker just wants to minimize the victim’s expected reward under attack, or
equivalently maximize the damage to the victim’s expected reward. In this
case, the attacker’s reward function is $g(s,a,r)=-r$. Alternatively, the
attacker may want the victim to behave in a specified way. This goal is
equivalent to the attacker wanting the victim to choose actions that match a
fixed target policy $\pi^{\dagger}$ as often as possible. In this case, the
attacker’s reward function is
$g(s,a,r)=\mathbf{1}\left\\{a=\pi^{\dagger}(s)\right\\}$.

######  Definition 1 (Attack Problem).

For any $\pi$, the attacker’s seeks a policy $\nu^{*}\in N$ that maximizes its
expected reward from the victim-attacker-$M$ interaction:

$\displaystyle\nu^{*}\in\operatorname*{arg\,max}_{\nu\in
N}\mathbb{E}^{\pi,\nu}_{M}\left[\sum_{t=0}^{\infty}\gamma^{t}g(s_{t},a_{t},r_{t})\right].$
(1)

We show that the attacker’s problem is captured by a MDP. The key insight is
that by defining the attacker’s state set to capture the results of previous
attacks from $t_{1}$ up to the current subtime, then each attack becomes
Markovian with respect to the expanded state set. This is not a significant
burden on the attacker since it would need to keep track of this information
anyway to compute the feasible attack sets. Thus, the attacker just needs to
keep track of the information within a time step to compute optimal attacks.

######  Definition 2 (Meta-MDP).

For any victim policy $\pi$, the attacker’s meta-MDP is
$\overline{M}=(\overline{\mathcal{S}},\overline{\mathcal{A}},\overline{P},\overline{r},\overline{\gamma},\overline{\mu})$
where,

  * •

$\overline{\mathcal{S}}=\mathcal{S}\cup(\mathcal{S}\times\mathcal{O})\cup(\mathcal{S}\times\mathcal{O}\times\mathcal{A})\cup(\mathcal{S}\times\mathcal{O}\times\mathcal{A}\times\mathcal{R})$.

  * •

$\overline{\mathcal{A}}(s)=\mathcal{B}(s)$,
$\overline{\mathcal{A}}(s,o)=\mathcal{B}(s,o)$,
$\overline{\mathcal{A}}(s,o,a)=\mathcal{B}(s,o,a)$, and
$\overline{\mathcal{A}}(s,o,a,r)=\mathcal{B}(s,o,a,r)$.

  * •

The transitions vary per subtime. Let $\overline{s}\in\overline{\mathcal{S}}$,
$\overline{a}\in\overline{\mathcal{A}}(\overline{s})$, and
$\overline{s}^{\prime}\in\overline{\mathcal{S}}$.

    1. 1.

If $\overline{s}=s$, then $\overline{a}=s^{\dagger}$ and
$\overline{s}^{\prime}=(s^{\dagger},o)$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a})=\mathcal{O}(o\mid
s^{\dagger}).$

    2. 2.

If $\overline{s}=(s,o)$, then $\overline{a}=o^{\dagger}$ and
$\overline{s}^{\prime}=(s,o^{\dagger},a)$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a})=\pi(a\mid
o^{\dagger}).$

    3. 3.

If $\overline{s}=(s,o,a)$, then $\overline{a}=a^{\dagger}$ and
$\overline{s}^{\prime}=(s,o,a^{\dagger},r)$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a})=R(r\mid
s,a^{\dagger}).$

    4. 4.

If $\overline{s}=(s,o,a,r)$, then $\overline{a}=r^{\dagger}$ and
$\overline{s}^{\prime}=s^{\prime}$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a})=P(s^{\prime}\mid
s,a).$

All other transitions have probability $0$.

  * •

Let $\overline{s}\in\overline{\mathcal{S}}$, and
$\overline{a}\in\overline{\mathcal{A}}(\overline{s})$. If
$\overline{s}=(s,o,a,r)$ and $\overline{a}=r^{\dagger}$, then
$\overline{r}(\overline{s},\overline{a})=g(s,a,r^{\dagger})$. For all other
meta-states, $\overline{r}(\overline{s},\overline{a})=0$.

  * •

$\overline{\gamma}=\gamma^{1/4}$.

  * •

$\overline{\mu}(s)=\mu(s)$ for $s\in\mathcal{S}$ and
$\overline{\mu}(\overline{s})=0$ otherwise.

#### Reward Subtlety.

Note that the attacker only receives a reward at every fourth subtime. This
means the discount factor has to be “slowed down” so that the factor at every
fourth time step matches that of each single time step of $M$. Specifically,
choosing $\overline{\gamma}=\gamma^{1/4}$ ensures that
$\overline{\gamma}^{4t}=\gamma^{t}$.

######  Proposition 1.

The maximum expected reward the attacker can achieve from any attack on $\pi$
is $V^{*}_{\overline{M}}$, the maximum expected total discounted reward for
the meta-MDP $\overline{M}$. Furthermore, any optimal deterministic,
stationary policy $\nu^{*}$ for $\overline{M}$ is an optimal attack policy.

#### Online Interaction.

Suppose the attacker has computed some attack policy $\nu$ from
$\overline{M}$. In order to use $\nu$ to interact with the victim and $M$, the
attacker must know the meta-state at any given subtime. As long as the
attacker can observe the interaction between the victim policy $\pi$ and $M$,
it can effectively simulate the interaction with the meta-MDP $\overline{M}$
online using a constant amount of memory. At time $t$, the attacker only needs
to store $s_{t}$, $o_{t}$, $a_{t}$, and $r_{t}$ when they are revealed to the
attacker. With this information, the attacker knows the meta-state for each
subtime and so can apply $\nu$ to determine its next attack. Upon reach the
next time $t+1$, the attacker can forget $s_{t}$, $o_{t}$, $a_{t}$, and
$r_{t}$ and start from $s_{t+1}$. See Algorithm 1.

Algorithm 1 Attacker Interaction Protocol

Input: $(\pi,\nu)$

1: for $t=1\ldots$ do

2: Attacker sees $s_{t}$, and computes a state attack
$s^{\dagger}_{t}=\nu(s_{t})$

3: Attacker sees $o_{t}\sim\mathcal{O}(s^{\dagger}_{t})$, and computes an
observation attack $o^{\dagger}_{t}=\nu(s_{t},o_{t})$

4: Attacker sees $a_{t}\sim\pi(o^{\dagger}_{t})$, and computes an action
attack $a^{\dagger}_{t}=\nu(s_{t},o_{t},a_{t})$

5: Attacker sees $r_{t}\sim\mathcal{R}(s^{\dagger}_{t},a^{\dagger}_{t})$, and
computes a reward attack $r^{\dagger}_{t}=\nu(s_{t},o_{t},a_{t},r_{t})$

6: Attacker receives reward
$g(s^{\dagger}_{t},a^{\dagger}_{t},r^{\dagger}_{t})$, and forgets
$(s_{t},o_{t},a_{t},r_{t})$

7: end for

#### Solving $\overline{M}$.

If the attacker has full knowledge of $M$ and the victim’s policy $\pi$, then
the attacker has all the knowledge needed to construct the meta-MDP
$\overline{M}$. Once $\overline{M}$ is constructed, the attacker can use any
planning algorithm, such as policy iteration, to compute the optimal attack.
Alternatively, if the attacker does not know $M$ and $\pi$, it can still
simulate interacting with $\overline{M}$ online as described before to perform
learning. In particular, the attacker can replace the call to $\nu$ in
Algorithm 1 with any off-the-shelf learning algorithm. For the episodic
setting, we view the attacker as attacking a new victim following the same
policy $\pi$ in each episode.

Observe that
$|\overline{\mathcal{S}}|\leq|\mathcal{S}||\mathcal{O}||\mathcal{A}||\mathcal{R}|$,
$|\overline{\mathcal{A}}|\leq|\mathcal{S}|+|\mathcal{O}|+|\mathcal{A}|+|\mathcal{R}|$,
and $\overline{\gamma}=\gamma^{1/4}$. Thus, whenever $M$’s rewards are
finitely supported, $|\overline{M}|=poly(|M|)$, where $|M|$ is the total size
of $M$’s description. As such, any polytime planning algorithm or polynomial
sample-complexity learning algorithm applied to $\overline{M}$ yields an
algorithm for computing optimal attacks that has polynomial complexity.

######  Proposition 2.

When $M$’s rewards have finite support or no reward attacks are allowed,
$|\overline{M}|=poly(|M|)$. Thus, an optimal attack policy can be computed in
polynomial time by planning in $\overline{M}$, and learning an optimal attack
policy can be performed with polynomial sample complexity by learning in
$\overline{M}$.

######  Remark 1 (Restricted Surfaces).

By restricting $\overline{\mathcal{A}}$ to singleton sets (e.g. set
$\overline{\mathcal{A}}(s,o,a)=\\{a\\}$ to disallow action attacks),
$\overline{M}$ recovers optimal attacks for each individual surface as well as
attacks for any subset of available attack surfaces. This captures all
standard test-time attacks, generalizing the perceived-state attack MDP of
[28]. We also note if the attacker does not perform reward attacks,
$\overline{M}$ can be modified to avoid $\mathcal{R}$ and so $M$ having finite
supported rewards is unnecessary in the complexity results.

One might ask whether the perceived-state attack MDP defined in [28] would
work in the linear setting. We point out that the transition takes the
following form,

$\displaystyle\tilde{P}(s^{\prime}\mid s,s^{\dagger})$
$\displaystyle=\mathbb{E}_{a\sim\pi(s^{\dagger})}P(s^{\prime}\mid s,a)$
$\displaystyle=\int_{a}P(s^{\prime}\mid s,a)\pi(a\mid s^{\dagger})da.$

As $\pi$ and $P$ are multiplied together, $\tilde{P}$ would be a quadratic
transition. On the other hand, our particular choice of subtimes induces
linear structure in $\overline{M}$. Specifically, each transition of
$\overline{P}$ is defined by a single distribution involving $\pi$ or $M$. If
both $\pi$ and $M$ have a linear structure, then so will $\overline{M}$. Then,
$\overline{M}$ can be solved by standard linear RL algorithms. Thus, so long
as $\pi$ is linear, the attacker can compute optimal attacks on linear
environments.

######  Theorem 1.

If $M$ is linear and $\pi$ is linear, then $\overline{M}$ is linear.
Furthermore, the dimension of $\overline{M}$, $d(\overline{M})$, is at most
$\max\\{d(\pi),d(M)\\}+1$. Thus, if $\pi$ is linear, optimal attacks on linear
environments can be computed or learned efficiently

######  Remark 2 (Beyond Markovian Policies).

Our construction can be easily modified to handle non-Markovian victim
policies. If the victim uses some finite amount of past history
$\tilde{\mathcal{H}}$, we simply modify the meta-state space to remember the
same amount of past history and adjust the construction appropriately. The
size of $\overline{M}$ is now a polynomial in both $|M|$ and the size of the
policy when described explicitly as a mapping from histories to action
distributions. We defer the details to the Appendix.

##  4 Optimal Defense

Now that we have seen how the attacker can best attack, it begs the question
of how the victim should defend against attacks. Intuitively, the victim
should choose a defense policy that is robust to attack. However, it does not
suffice to just be robust against a particular attack. In fact, the attacker
could lie about its attack algorithm to bait the victim into choosing a policy
that actually benefits the attacker. Even if some attacker does use that
particular attack algorithm, other attackers may employ different methods that
lead the victim to poor value. As new attacks are formulated, the victim would
have to constantly create more complex policies designed with all known
attacks in mind. This would become a never-ending cat-and-mouse game during
which the victim’s policy will often be at risk of new attacks. Thus, for a
policy to be satisfactorily robust, we require it to be robust against the
worst possible attack. This way, no matter what future strategies an attacker
may use, the victim is already prepared.

We can formalize this intuition using the Stackelberg approach for Security
Applications [9]. For any $\pi$ and $\nu$, let $V_{1}^{\pi,\nu}$ and
$V_{2}^{\pi,\nu}$ denote the victim’s and attacker’s expected reward
respectively under the victim-attacker-$M$ interaction induced by $\pi$ and
$\nu$. Note, both of these quantities can be computed efficiently using the
techniques from Section 3. Let $V_{1}$ and $V_{2}$ denote infinite matrices
whose $(\pi,\nu)$ entry corresponds to $V_{1}^{\pi,\nu}$ and $V_{2}^{\pi,\nu}$
respectfully. We define an infinite bimatrix game $G$ whose payoff matrices
are $(V_{1},V_{2})$. For any fixed victim $\pi$, it is clear that a rational
attacker would play some best-response policy, $\nu\in BR(\pi):=\max_{\nu\in
N}V^{\pi,\nu}_{2}$. Thus, an optimal defense policy is exactly an optimal
Stackelberg strategy for player $1$ in $G$ [3].

######  Definition 3 (Defense Problem).

The victim seeks a policy $\pi^{*}$ that maximizes its expected reward from
the victim-attacker-$M$ interaction under the worst-case attack:

$\pi^{*}\in\max_{\pi\in\Pi}\min_{\nu\in BR(\pi)}V^{\pi,\nu}_{1}.$ (2)

Observe that this solution is truly robust: by definition, the attacker given
$\pi$ would never want to deviate from $BR(\pi)$, and similarly, by definition
the victim would never want to deviate from its defense policy when assuming
the worst possible attack. Thus, we consider such attack and defense policies
as truly _optimal_. However, as the victim faces partial observability, an
optimal defense for the victim is history-dependent in general. Consequently,
the attacker’s best response must also be history-dependent. Thus, $\Pi$ and
$N$ consist of history-dependent policies in the definition above.

Although optimal Stackelberg strategies for Stochastic games are generally
difficult to compute [12], we can exploit the special structure of the victim-
attacker-$M$ interaction to develop useful algorithms. Recall that at subtime
$t_{2}$ in Algorithm 1, the attacker changes the observation to $o^{\dagger}$,
and then the victim chooses an action $a=\pi(o^{\dagger})$. If we simply give
the victim the autonomy to choose any action $a$ at this point rather than
according to a fixed policy $\pi$, then this interaction evolves like a turn-
based game. In fact, we show this game can be modeled as a partially
observable turn-based stochastic game (POTBSG) [31]. POTBSGs exhibit much more
structure than a general imperfect-information stochastic game, so enable more
efficient solution methods. We see the construction is almost identical to
Definition 2.

######  Definition 4.

The victim-attacker’s POTBSG is
$\overline{G}=(\overline{\mathcal{S}}_{1}\cup\overline{\mathcal{S}}_{2},\overline{\mathcal{O}},\overline{\mathcal{A}},\overline{P},\overline{r},\overline{\gamma},\allowbreak\overline{\mu})$
where,

  * •

$\overline{\mathcal{S}}_{1}:=\mathcal{S}\times\mathcal{O}\times\left\\{\varnothing\right\\}$
and
$\overline{\mathcal{S}}_{2}:=\mathcal{S}\cup(\mathcal{S}\times\mathcal{O})\cup(\mathcal{S}\times\mathcal{O}\times\mathcal{A})\cup(\mathcal{S}\times\mathcal{O}\times\mathcal{A}\times\mathcal{R})$.

  * •

$\overline{\mathcal{O}}(\overline{s}):=o$ for $\overline{s}=(s,o,\varnothing)$
and $\overline{\mathcal{O}}(\overline{s}):=\overline{s}$ otherwise.

  * •

$\overline{\mathcal{A}}(s):=\mathcal{B}(s)$,
$\overline{\mathcal{A}}(s,o):=\mathcal{B}(s,o)$,
$\overline{\mathcal{A}}(s,o,\varnothing):=\mathcal{A}$,
$\overline{\mathcal{A}}(s,o,a):=\mathcal{B}(s,o,a)$, and
$\overline{\mathcal{A}}(s,o,a,r):=\mathcal{B}(s,o,a,r)$.

  * •

Let $\overline{s}\in\overline{\mathcal{S}}$,
$\overline{a}\in\overline{\mathcal{A}}(\overline{s})$, and
$\overline{s}^{\prime}\in\overline{\mathcal{S}}$.

    1. 1.

If $\overline{s}=s$, then $\overline{a}=s^{\dagger}$ and
$\overline{s}^{\prime}=(s^{\dagger},o)$:
$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=\mathcal{O}(o\mid
s^{\dagger}).$

    2. 2.

If $\overline{s}=(s,o)$, then $\overline{a}=o^{\dagger}$ and
$\overline{s}^{\prime}=(s,o^{\dagger},\varnothing)$:
$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=\pi(a\mid
o^{\dagger}).$

    3. 3.

If $\overline{s}=(s,o,\varnothing)$, then $\overline{a}=a$ and
$\overline{s}^{\prime}=(s,o^{\dagger},a)$:
$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=1.$

    4. 4.

If $\overline{s}=(s,o,a)$, then $\overline{a}=a^{\dagger}$ and
$\overline{s}^{\prime}=(s,o,a^{\dagger},r)$:
$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=R(r\mid
s,a^{\dagger}).$

    5. 5.

If $\overline{s}=(s,o,a,r)$, then $\overline{a}=r^{\dagger}$ and
$\overline{s}^{\prime}=s^{\prime}$:
$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=P(s^{\prime}\mid
s,a).$

All other transitions have probability $0$.

  * •

Let $\overline{s}\in\overline{\mathcal{S}}$, and
$\overline{a}\in\overline{\mathcal{A}}(\overline{s})$.
$\overline{r}_{1}(\overline{s},\overline{a}):=r^{\dagger}$ and
$\overline{r}_{2}(\overline{s},\overline{a}):=g(s,a,r^{\dagger})$ if
$\overline{s}=(s,o,a,r)$ and
$\overline{r}_{1}(\overline{s},\overline{a}):=\overline{r}_{2}(\overline{s},\overline{a}):=0$
otherwise.

  * •

$\overline{\gamma}:=\gamma^{1/5}$.

  * •

$\overline{\mu}(s):=\mu(s)$ for $s\in\mathcal{S}$ and
$\overline{\mu}(\overline{s}):=0$ otherwise.

Note that $\overline{\mathcal{S}}_{1}$ is the set of states in which the
victim takes an action, and $\overline{\mathcal{S}}_{2}$ is the set of states
in which the attacker takes an action. The observation and action set
$\overline{\mathcal{O}}$ and $\overline{\mathcal{A}}$ as functions of the
states are combined for the two players, and this implies that the
observations and actions for the victim are
$\overline{\mathcal{A}}(\overline{\mathcal{S}}_{1})$ and
$\overline{\mathcal{O}}(\overline{\mathcal{S}}_{1})$, and for the attacker are
$\overline{\mathcal{A}}(\overline{\mathcal{S}}_{2})$ and
$\overline{\mathcal{O}}(\overline{\mathcal{S}}_{2})$. Observe that
$V_{\overline{G},1}^{\pi,\nu}=V_{1}^{\pi,\nu}$ and
$V_{\overline{G},2}^{\pi,\nu}=V_{\overline{M}}^{\pi,\nu}$ and so $G$ is just
the normal-form representation of the POTBSG $\overline{G}$.

######  Proposition 3.

Any WSE for $\overline{G}$ yields an optimal defense policy.

In general, methods to compute WSE are unknown. However, we show many settings
where a WSE for $\overline{G}$ can be computed, even efficiently. First,
suppose the attacker is completely adversarial so that $\overline{G}$ becomes
a zero-sum game. In this case, it is known that $WSE=SSE=NE$. Thus, it
suffices to compute an NE for a zero-sum POTBSG.

######  Proposition 4.

If the attacker is completely adversarial, an optimal defense policy can be
computed as an NE of $\overline{G}$ using any planning or distributed learning
algorithms for zero-sum POTBSGs.

Note, it is important that the victim uses a distributed learning algorithm
since it would not be able to see the attacker’s manipulations, only the
effects of the manipulations, nor be able to collaborate with the attacker.
From Proposition 3, we see that the victim can compute an optimal defense
policy to an adversarial attacker by computing any CCE to $\overline{G}$.
However, even computing an approximately optimal Markovian policy against a
fixed attack is equivalent to solving a POMDP, which is NP-hard [15]. Thus,
computing near-optimal defenses is intractable in the worst case.

######  Proposition 5.

For any $\epsilon>0$ an $\epsilon$-approximate optimal defense policy is NP-
hard to compute even when restricting $\Pi$ and $N$ to be the class of
Markovian policies.

#### Efficient Methods.

The main bottleneck to computing defenses efficiently in fully-observable
systems is the presence of perceived-state attacks. Absent these attacks, the
POTBSG specializes to a traditional TBSG, which is a special case of a
stochastic game.

######  Observation 1.

When $M$ is fully observable and the attacker cannot perform perceived-state
attacks, $\overline{G}$ simplifies to a TBSG.

In the adversarial case, we see that $\overline{G}$ is simply a zero-sum TBSG.
In zero-sum TBSGs, even stationary NE can be computed or learned efficiently
[4] unlike the case with CCE for MGs [5] and the solutions are exact.

######  Proposition 6.

If $M$ is fully-observable, no perceived-state attacks are allowed, and $M$’s
rewards have finite support (or no reward attacks are allowed), and the
attacker is adversarial, then an _optimal stationary_ defense policy can be
computed in polynomial time and learned with polynomial sample complexity.

Although it is unclear whether Markovian policies guarantee the victim as much
value as history-dependent ones, Markovian policies are commonplace since they
are easier to store and deploy in practice. In fact, for the finite-horizon
planning setting, the attacker need not be restricted. We give polynomial time
planning algorithms to compute an optimal defense so long as perceived-state
attacks are banned. To our knowledge, this is the first non-trivial setting
for which WSE can be computed efficiently and the first non-trivial setting
for which SSE can be computed beyond single-period games.

######  Theorem 2.

If $M$ is fully-observable and has a finite horizon, no perceived-state
attacks are allowed, and $M$’s rewards have finite support (or no reward
attacks are allowed), then an optimal defense policy can be computed in
polynomial time.

The intuition is the victim can simulate the attacker’s best-response function
using backward induction. Once it knows the best response for a particular
stage game, it can then brute-force find the best action to take at that
stage. The key insight is that the attacker’s best response is always
deterministic since it gets to see the victim’s realized actions. Thus, the
victim also has no benefit from randomization. As such, the victim can brute-
force compute its optimal deterministic action to take during a single stage
and then propagate that solution backward to be used in previous times.

To illustrate this, we derive a backward induction algorithm for efficient
defense against action attacks and present the full defense algorithm in the
Appendix. Suppose the victim has already committed to
$\\{\pi^{*}_{t}\\}_{t=h+1}^{H}$, where $H$ is the finite time-horizon.
Clearly, for any choice of victim’s action $a$, the attacker’s best response
to $a$ and the future partial policy is:

$\displaystyle BR_{h}(s,a)=$
$\displaystyle\operatorname*{arg\,max}_{a^{\dagger}\in\overline{\mathcal{A}}(s,a)}g_{h}(s,a,r_{h}(s,a))$
$\displaystyle\hskip 10.00002pt+\mathbb{E}_{s^{\prime}\sim
P_{h}(s,a^{\dagger})}V^{*}_{h+1,2}(s^{\prime},\pi^{*}_{h+1}(s^{\prime})),$

where $V^{*}_{h,2}(s,a)$ is the maximum value achieved. Then, the victim can
compute its best action for the stage game $(h,s)$ as a maximizer of,

$\displaystyle V^{*}_{h,1}(s)=$
$\displaystyle\max_{a\in\mathcal{A}}\min_{a^{\dagger}\in
BR_{h}(s,a)}r_{h}(s,a^{\dagger})$ $\displaystyle\hskip
10.00002pt+\mathbb{E}_{s^{\prime}\sim
P_{h}(s,a^{\dagger})}V^{*}_{h+1,1}(s^{\prime}).$

When the game is zero-sum, the algorithm is even simpler: the victim need not
even simulate the attacker’s best response. The recursion is simply:

$\displaystyle V^{*}_{h,1}(s)=$
$\displaystyle\max_{a\in\mathcal{A}}\min_{a^{\dagger}\in\overline{\mathcal{A}}(s,a)}r_{h}(s,a^{\dagger})$
$\displaystyle\hskip 10.00002pt+\mathbb{E}_{s^{\prime}\sim
P_{h}(s,a^{\dagger})}V^{*}_{h+1,1}(s^{\prime}).$

The construction for defending against all non-perceived state surfaces is a
bit more complicated but retains this same structure.

######  Remark 3 (Multi-Agent Extension).

We note that all of our results remain the same when multiple victims are
present. This can be done without changing any of the previous notations by
interpreting $\mathcal{A}=A_{1}\times\ldots\times A_{n}$ as the joint action
space and $\pi$ as a joint policy. From the attacker’s perspective, attacking
many victims just looks like attacking a single victim with a large action
space. A WSE in $\overline{G}$ still breaks up into an independent joint
policy for the victims and the attacker, but the joint policy may require the
victims to correlate with each other.

##  5 Experiments

We illustrate our frameworks with a classical grid-world shortest path problem
with obstacles. Here, each state is a cell in a $n\times n$ grid. Some grid
cells are filled with lava and so dangerous to the victim. From any cell, the
victim can move left (L), right (R), up (U), or down (D) so long as it remains
on the grid. In addition, the victim can stay (S) in its current cell. The
agent wishes to get from the top-left cell $(0,0)$ to the bottom-right,
“goal”, cell $(n-1,n-1)$ as quickly as possible while avoiding lava. To
capture this goal, we assume the victim receives a reward of $1$ for entering
the goal cell and continues to receive a reward of $1$ for each time it
remains there to incentivize the victim to reach the goal quickly. We also
assume the victim receives a penalty reward of $-H$ whenever it enters a lava
cell, where $H$ is the finite horizon.

Here, we test our methods on a $10\times 10$ grid world with $H=20$ so that
the victim has enough time to reach the goal and stay there. We computed an
optimal policy $\pi^{*}$ for the grid, which achieves the victim a value of
$3$. In Figure 1 we visualize $\pi^{*}$ through the path the victim follows
when using $\pi^{*}$. The black cells represent a cell the victim entered
during its interaction. The orange cells represent lava.

Figure 1: Optimal Policy Path.

###  5.1 Grid Attacks

The attacker can utilize its surfaces to disrupt the victim’s path. Here, we
illustrate how the attacker may use each of its surfaces other than reward
attacks since these do not change the trajectory of the agent. For simplicity,
assume that the attacker is purely adversarial and so it seeks to prevent the
victim from reaching the goal and even trick it into lava cells if possible.
Suppose that most of the grid is under security and so attacks cannot be
safely made. The attacker is restricted to only attacking edges of the grid,
which are not monitored. Here, the regions include the top-right subgrid and
the bottom-left subgrid shaded in yellow. However, in those regions, it may
use any attack it likes from its given surface.

Figure 2: Attacked Paths.

In Figure 2, we see from left to right the path under an optimal perceived-
state attack, true-state attack, and action attack. The agent receives $-100$,
$0$, and $-160$ value from each attack respectively. In all cases, the victim
no longer reaches the goal after getting attacked in the top-right subgrid. We
see the perceived-state attack functions by tricking the agent into entering
lava; whereas the action attack simply forces the victim into lava. On the
other hand, the state attacks can transport the victim into lava, but they
immediately leave and so suffers less damage than in the other attacks despite
seeming to be the most powerful.

###  5.2 Grid Defense

We see that if the victim simply follows $\pi^{*}$, the effects of attacks can
be catastrophic. A smart victim can employ our defense algorithm to become
robust against attacks. The victim knows the upper-right and bottom-left
subgrids are not monitored and so can assume attacks are conducted there.
Using this information, the defense algorithm yields a policy $\hat{\pi}$ that
completely avoids the unsafe region. The victim still achieves the optimal
value of $3$ even under the strongest-possible attack. The new path under
attack is illustrated in Figure 3. We see the robust path simply squeezes
between the two unsafe regions.

Figure 3: Defense Policy Path

##  6 Conclusions

In this paper, we rigorously studied the attack and defense problems of
reinforcement learning. We showed that for any attack’s surface, a malicious
attacker can optimally and efficiently maximize its own rewards by solving a
higher lever meta-MDP. Even against linear environments, an attacker can still
efficiently compute optimal attacks. Thus, we call for an agent to play a
robust policy to be safe against such attacks. To this end, we formally
defined the defense problem to be a weak-Stackelberg equilibrium of the
natural partially-observable turn-based stochastic game that is induced by the
victim-attacker-environment interaction. In the zero-sum setting, we showed
the defense problem boils down to finding a Nash equilibrium in a zero-sum
POTBSG so standard planning and learning methods can find optimal defense
policies. When perceived-state attacks are not allowed, the victim can also
compute an optimal defense policy in polynomial time using a robust backward
induction algorithm. Although we present an optimal defense, this defense may
not be useful if the attacker is too powerful. It is critical for the victim
to improve its detection abilities to restrict the attacker’s feasible
actions.

## References

  * Banihashem et al. [2021] Kiarash Banihashem, Adish Singla, and Goran Radanovic.  Defense against reward poisoning attacks in reinforcement learning, 2021\.
  * Behzadan and Munir [2017] Vahid Behzadan and Arslan Munir.  Vulnerability of deep reinforcement learning to policy induction attacks.  In Petra Perner, editor, _Machine Learning and Data Mining in Pattern Recognition_ , pages 262–275, Cham, 2017. Springer International Publishing.  ISBN 978-3-319-62416-7.
  * Conitzer [2015] Vincent Conitzer.  On stackelberg mixed strategies.  _Synthese_ , 193(3):689–703, 9 2015.  doi: 10.1007/s11229-015-0927-6.  URL https://doi.org/10.1007%2Fs11229-015-0927-6.
  * Cui and Yang [2021] Qiwen Cui and Lin F. Yang.  Minimax sample complexity for turn-based stochastic game.  In Cassio de Campos and Marloes H. Maathuis, editors, _Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ , volume 161 of _Proceedings of Machine Learning Research_ , pages 1496–1504. PMLR, 7 2021.  URL https://proceedings.mlr.press/v161/cui21a.html.
  * Daskalakis et al. [2022] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang.  The complexity of markov equilibrium in stochastic games, 2022.
  * Goodfellow et al. [2014] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples, 2014.  URL https://arxiv.org/abs/1412.6572.
  * Hansen et al. [2013] Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick.  Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor.  _J. ACM_ , 60(1), 2 2013.  ISSN 0004-5411.  doi: 10.1145/2432622.2432623.  URL https://doi.org/10.1145/2432622.2432623.
  * Huang et al. [2017] Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel.  Adversarial attacks on neural network policies, 2017.  URL https://arxiv.org/abs/1702.02284.
  * Korzhyk et al. [2010] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr.  Complexity of computing optimal stackelberg strategies in security resource allocation games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 24(1):805–810, 7 2010.  doi: 10.1609/aaai.v24i1.7638.  URL https://ojs.aaai.org/index.php/AAAI/article/view/7638.
  * Kos and Song [2017] Jernej Kos and Dawn Song.  Delving into adversarial attacks on deep policies, 2017.  URL https://arxiv.org/abs/1705.06452.
  * Lee et al. [2021] Xian Yeow Lee, Yasaman Esfandiari, Kai Liang Tan, and Soumik Sarkar.  Query-based targeted action-space adversarial policies on deep reinforcement learning agents.  In _Proceedings of the ACM/IEEE 12th International Conference on Cyber-Physical Systems_ , ICCPS ’21, page 87–97, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450383530.  doi: 10.1145/3450267.3450537.  URL https://doi.org/10.1145/3450267.3450537.
  * Letchford et al. [2021] Joshua Letchford, Liam MacDermed, Vincent Conitzer, Ronald Parr, and Charles Isbell.  Computing optimal strategies to commit to in stochastic games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 26(1):1380–1386, 9 2021.  doi: 10.1609/aaai.v26i1.8267.  URL https://ojs.aaai.org/index.php/AAAI/article/view/8267.
  * Lin et al. [2017] Yen-Chen Lin, Zhang-Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming-Yu Liu, and Min Sun.  Tactics of adversarial attack on deep reinforcement learning agents.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , IJCAI’17, page 3756–3762. AAAI Press, 2017.  ISBN 9780999241103.
  * Liu and Lai [2021] Guanlin Liu and Lifeng Lai.  Provably efficient black-box action poisoning attacks against reinforcement learning.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 12400–12410. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/678004486c119599ed7d199f47da043a-Paper.pdf.
  * Lusena et al. [2001] C. Lusena, J. Goldsmith, and M. Mundhenk.  Nonapproximability results for partially observable markov decision processes.  _Journal of Artificial Intelligence Research_ , 14:83–103, 3 2001.  doi: 10.1613/jair.714.  URL https://doi.org/10.1613%2Fjair.714.
  * Ouyang et al. [2022] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback, 2022\.
  * Puterman [1994] Martin L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., USA, 1st edition, 1994.  ISBN 0471619779.  doi: 10.1002/9780470316887.
  * Rangi et al. [2022] 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.  doi: 10.24963/ijcai.2022/471.  URL https://doi.org/10.24963/ijcai.2022/471.  Main Track.
  * Russo and Proutiere [2021] Alessio Russo and Alexandre Proutiere.  Towards optimal attacks on reinforcement learning policies.  In _2021 American Control Conference (ACC)_ , pages 4561–4567, 2021\.  doi: 10.23919/ACC50511.2021.9483025.
  * Sidford et al. [2018] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye.  Near-optimal time and sample complexities for solving markov decision processes with a generative model.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/bb03e43ffe34eeb242a2ee4a4f125e56-Paper.pdf.
  * Sun et al. [2020] Jianwen Sun, Tianwei Zhang, Xiaofei Xie, Lei Ma, Yan Zheng, Kangjie Chen, and Yang Liu.  Stealthy and efficient adversarial attacks against deep reinforcement learning.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):5883–5891, 4 2020.  doi: 10.1609/aaai.v34i04.6047.  URL https://ojs.aaai.org/index.php/AAAI/article/view/6047.
  * Sun et al. [2022] Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang.  Who is the strongest enemy? towards optimal and efficient evasion attacks in deep RL.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=JM2kFbJvvI.
  * Tessler et al. [2019] Chen Tessler, Yonathan Efroni, and Shie Mannor.  Action robust reinforcement learning and applications in continuous control.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6215–6224. PMLR, 6 2019.  URL https://proceedings.mlr.press/v97/tessler19a.html.
  * Tretschk et al. [2018] Edgar Tretschk, Seong Joon Oh, and Mario Fritz.  Sequential attacks on agents for long-term adversarial goals, 2018.  URL https://arxiv.org/abs/1805.12487.
  * Vlassis et al. [2012] Nikos Vlassis, Michael L. Littman, and David Barber.  On the computational complexity of stochastic controller optimization in pomdps, 2012.
  * Vorobeychik and Singh [2021] Yevgeniy Vorobeychik and Satinder Singh.  Computing stackelberg equilibria in discounted stochastic games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 26(1):1478–1484, Sep. 2021.  doi: 10.1609/aaai.v26i1.8234.  URL https://ojs.aaai.org/index.php/AAAI/article/view/8234.
  * Wu et al. [2022] Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li.  CROP: Certifying robust policies for reinforcement learning through functional smoothing.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=HOjLHrlZhmx.
  * Zhang et al. [2020a] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh.  Robust deep reinforcement learning against adversarial perturbations on state observations.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 21024–21037. Curran Associates, Inc., 2020a.  URL https://proceedings.neurips.cc/paper/2020/file/f0eb6568ea114ba6e293f903c34d7488-Paper.pdf.
  * Zhang et al. [2021] Huan Zhang, Hongge Chen, Duane S Boning, and Cho-Jui Hsieh.  Robust reinforcement learning on state observations with learned optimal adversary.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=sCZbhBvqQaU.
  * Zhang et al. [2020b] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu.  Adaptive reward-poisoning attacks against reinforcement learning.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 11225–11234. PMLR, 7 2020b.  URL https://proceedings.mlr.press/v119/zhang20u.html.
  * Zheng et al. [2022] Wei Zheng, Taeho Jung, and Hai Lin.  The stackelberg equilibrium for one-sided zero-sum partially observable stochastic games.  _Automatica_ , 140:110231, 2022.  ISSN 0005-1098.  doi: https://doi.org/10.1016/j.automatica.2022.110231.  URL https://www.sciencedirect.com/science/article/pii/S0005109822000760.

##  Appendix A Proofs for Section 3

The proof of the Proposition 1 is immediate from the definition of each attack
surface and the well-known fact that any MDP admits an optimal deterministic,
Markovian policy. Proposition 2 follows from the complexity results given in
[17] and [20].

#### Proof of Theorem 1.

###### Proof.

The key idea is each meta-state transitions according to either, $O$, $\pi$,
$R$, or $P$, and since each of these quantities is linear, the meta-
transitions are linear. Also, as the rewards are a deterministic projection,
they are also linear. If $M$ and $\pi$ are linear then,

$O(o\mid s)=\left\langle\phi(s),\gamma(o)\right\rangle,\quad\pi(a\mid
o)=\left\langle\psi(o),\delta(a)\right\rangle,\quad R(r\mid
s,a)=\left\langle\phi(s,a),\theta(r)\right\rangle,\quad P(s^{\prime}\mid
s,a)=\left\langle\phi(s,a),\mu(s^{\prime})\right\rangle.$

We first design a feature vector $\bar{\phi}(\overline{s},\overline{a})$ and
vector $\overline{\mu}(\overline{s})$ that captures the transitions. Let
$\overline{s}\in\overline{\mathcal{S}}$,
$\overline{a}\in\overline{\mathcal{A}}(\overline{s})$, and
$\overline{s}^{\prime}\in\overline{\mathcal{S}}$. From the definition of
$\overline{M}$,

  1. 1.

If $\overline{s}=s$, then $\overline{a}=s^{\dagger}$ and
$\overline{s}^{\prime}=(s^{\dagger},o)$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=\mathcal{O}(o\mid
s^{\dagger})=\left\langle\phi(s^{\dagger}),\gamma(o)\right\rangle.$

Define $\bar{\phi}(s,s^{\dagger})=\phi(s^{\dagger})$ and
$\overline{\mu}(s^{\dagger},o)=\gamma(o)$. Then,

$\left\langle\phi(s^{\dagger}),\gamma(o)\right\rangle=\left\langle\bar{\phi}(\overline{s},\overline{a}),\overline{\mu}(\overline{s}^{\prime})\right\rangle.$

  2. 2.

If $\overline{s}=(s,o)$, then $\overline{a}=o^{\dagger}$ and
$\overline{s}^{\prime}=(s,o^{\dagger},a)$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=\pi(a\mid
o^{\dagger})=\left\langle\psi(o^{\dagger}),\delta(a)\right\rangle.$

Define $\bar{\phi}((s,o),o^{\dagger})=\psi(o^{\dagger})$ and
$\overline{\mu}(s,o^{\dagger},a)=\delta(a)$. Then,

$\left\langle\psi(o^{\dagger}),\delta(a)\right\rangle=\left\langle\bar{\phi}(\overline{s},\overline{a}),\overline{\mu}(\overline{s}^{\prime})\right\rangle.$

  3. 3.

If $\overline{s}=(s,o,a)$, then $\overline{a}=a^{\dagger}$ and
$\overline{s}^{\prime}=(s,o,a^{\dagger},r)$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=R(r\mid
s,a^{\dagger})=\left\langle\phi(s,a^{\dagger}),\theta(r)\right\rangle.$

Define $\bar{\phi}((s,o,a),a^{\dagger})=\phi(s,a^{\dagger})$ and
$\overline{\mu}(s,o,a,r)=\theta(r)$. Then,

$\left\langle\phi(s,a^{\dagger}),\theta(r)\right\rangle=\left\langle\bar{\phi}(\overline{s},\overline{a}),\overline{\mu}(\overline{s}^{\prime})\right\rangle.$

  4. 4.

If $\overline{s}=(s,o,a,r)$, then $\overline{a}=r^{\dagger}$ and
$\overline{s}^{\prime}=s^{\prime}$:

$\overline{P}(\overline{s}^{\prime}\mid\overline{s},\overline{a}):=P(s^{\prime}\mid
s,a)=\left\langle\phi(s,a),\mu(s^{\prime})\right\rangle.$

Define $\bar{\phi}((s,o,a,r),r^{\dagger})=\phi(s,a)$ and
$\overline{\mu}(s^{\prime})=\mu(s^{\prime})$. Then,

$\left\langle\phi(s,a),\mu(s^{\prime})\right\rangle=\left\langle\bar{\phi}(\overline{s},\overline{a}),\overline{\mu}(\overline{s}^{\prime})\right\rangle.$

We lift each vector to dimension $d=\max(d(\pi),d(M))$ so each vector is in
the same dimension.

Now, to capture rewards, we will need to lift the vectors to one dimension
higher. We add one entry to each vector. The entry is $g(s,a,r^{\dagger})$ for
meta-states of form $(s,a,r)$ and meta-action $r^{\dagger}$, making the new
vector
$\phi^{\prime}(\overline{s},\overline{a})=\begin{bmatrix}g\left(s,a,r^{\dagger}\right)\\\
\bar{\phi}(\overline{s},\overline{a})\end{bmatrix}$. All other meta-states and
meta-actions have a $0$ in the new entry, or
$\phi^{\prime}(\overline{s},\overline{a})=\begin{bmatrix}0\\\
\bar{\phi}(\overline{s},\overline{a})\end{bmatrix}$. We define
$\bar{\theta}=e_{1}$, the basis vector with a $1$ in the entry that we just
added to the features. From the definition of $\overline{M}$,

$\overline{r}(s,s^{\dagger})=\overline{r}((s,a),a^{\dagger})=\overline{r}((s,a),s^{\dagger})=0=\left\langle\bar{\phi}^{\prime}(\overline{s},\overline{a}),e_{1}\right\rangle.$
$\overline{r}((s,a,r),r^{\dagger})=g(s,a,r^{\dagger})=\left\langle\bar{\phi}^{\prime}(\overline{s},\overline{a}),e_{1}\right\rangle.$

Thus, $\overline{M}$ is linear with dimension at most $1+\max(d(\pi),d(M))$. ∎

We note that for the finite-horizon case, the proof remains the same except
for one aspect. If the attacker’s reward $g$ is time-dependent, then the
feature vectors involving $r^{\dagger}$ must save $g_{h}(s,a,r^{\dagger})$ for
all $h$. Thus the dimension would be $H+1+\max(d(\pi),d(M))$ if we modify the
proof in the obvious way.

#### More Details of Remark 2.

When the victim’s policy is not Markovian, i.e. uses some amount of history,
the construction of $\overline{M}$ needs to be slightly modified. Suppose
$\mathcal{M}$ denotes the victim’s finite memory. For any $m\in\mathcal{M}$,
we let $m(\cdot)$ denote the victim’s updated memory upon receiving new
information. Since the victim has a finite amount of memory, we assume that
when the memory is updated, it removes the oldest saved information to make
space for the new information. We also assume here, the attacker is attacking
a Markov game $G$ so that $\pi$ is now a joint policy as described in Remark
3. We define the attacker’s meta-MDP as
$\overline{M}=(\overline{\mathcal{S}},\overline{\mathcal{A}},\overline{P},\overline{r},\gamma,\overline{\mu})$,
where,

  * •

$\overline{\mathcal{S}}=(\mathcal{M}\times\mathcal{S})\cup(\mathcal{M}\times\mathcal{S}\times
O)\cup(\mathcal{M}\times\mathcal{S}\times
O\times\mathcal{A})\cup(\mathcal{M}\times\mathcal{S}\times
O\times\mathcal{A}\times\mathcal{R})$.

  * •

$\overline{\mathcal{A}}\subseteq\mathcal{S}\cup\mathcal{A}\cup\mathcal{R}$
consists of all the attacker’s potential manipulations of the interaction. The
meta-action space is meta-state dependent:
$\overline{\mathcal{A}}(m,s)\subseteq\mathcal{S}$,
$\overline{\mathcal{A}}(m,s,o)\subseteq\mathcal{O}$,
$\overline{\mathcal{A}}(m,s,o,a)\subseteq\mathcal{S}\cup\mathcal{A}$, and
$\overline{\mathcal{A}}(m,s,o,a,r)\subseteq\mathcal{R}$.

  * •

Suppose that $m\in\mathcal{M}$, $s\in\mathcal{S}$, $o\in O$,
$a\in\mathcal{A}$, and $r\in\mathcal{R}$. Then,

    * –

If $\overline{a}=s^{\dagger}$ is a true-state attack at the first subtime,
then $G$’s state becomes $s^{\dagger}$ and generates an observation according
to $P(s^{\dagger})$.

$\overline{P}((m,s^{\dagger},o)\mid(m,s),s^{\dagger}):=P(o\mid s^{\dagger}).$

    * –

If $\overline{a}=o^{\dagger}\in O$ is an observation attack, then the agents
choose a joint action $a\sim\pi(m,o^{\dagger})$. Also, the agent sees the
attacked observation and so updates its memory to $m(o^{\dagger})$.

$\displaystyle\overline{P}((m(o^{\dagger}),s,o^{\dagger},a)$
$\displaystyle\mid(m,s,o),o^{\dagger}):=\pi(a\mid m,o^{\dagger}).$

    * –

If $\overline{a}=a^{\dagger}\in\mathcal{A}$ is an action attack, $G$ receives
action $a^{\dagger}$. Thus, $G$ generates reward according to
$R(s,a^{\dagger})$. The agents also update their memory to $m(a)$.

$\displaystyle\overline{P}((m(a),s,o,a^{\dagger},r)$
$\displaystyle\mid(m,s,o,a),a^{\dagger}):=R(r\mid s,a^{\dagger}).$

    * –

If $\overline{a}=s^{\dagger}\in\mathcal{S}$ is a true-state attack at the
third subtime, $G$’s state becomes $s^{\dagger}$. Thus, $G$ generates reward
according to $R(s^{\dagger},a)$. The agents also update their memory to
$m(a)$.

$\displaystyle\overline{P}((m(a),s^{\dagger},o,a,r)$
$\displaystyle\mid(m,s,o,a),s^{\dagger}):=R(r\mid s^{\dagger},a).$

    * –

If $\overline{a}=r^{\dagger}\in\mathcal{R}$ is a reward attack, $G$’s
transitions are not effected. Thus, $G$ transitions normally according to
$P(s,a)$. Also, the agent sees the attacked reward and so updates its memory
to $m(r^{\dagger})$.

$\overline{P}((m(r^{\dagger}),s^{\prime})\mid(m,s,o,a,r),r^{\dagger}):=P(s^{\prime}\mid
s,a).$

All other transitions have probability $0$.

  * •

Using the same definitions as above,

    * –

There is no immediate reward to the attacker for non-reward attacks since the
agents have not received a reward yet.

$\displaystyle\overline{r}((m,s),s^{\dagger})=\overline{r}((m,s,o),o^{\dagger})=\overline{r}((m,s,o,a),a^{\dagger})=\overline{r}((m,s,o,a),s^{\dagger})=0.$

    * –

If $\overline{a}=r^{\dagger}\in\mathcal{R}$, the agents receive reward
$r^{\dagger}$ and so the attacker receives reward according to its reward
function $g(s,a,r^{\dagger})$.

$\overline{r}(\overline{s},\overline{a})=\overline{r}((m,s,o,a,r),r^{\dagger})=g(s,a,r^{\dagger}).$

  * •

$\overline{\mu}(s)=\mu(\varnothing,s)$ for each $s\in\mathcal{S}$ where
$\varnothing$ denotes the empty memory, and $\overline{\mu}(\overline{s})=0$
otherwise.

#### Deterministic Markovian policy and deterministic reward.

If the agent’s policy is deterministic and Markovian, which is the standard
for optimal policies, and $M$ is fully-observable with deterministic rewards,
the attacker’s meta-MDP can be drastically simplified. We define the
attacker’s meta-MDP as
$\overline{M}=(\overline{\mathcal{S}},\overline{\mathcal{A}},\\{\overline{P}_{h}\\},\\{\overline{r}_{h}\\},H,\overline{\mu})$,
where,

  * •

$\overline{\mathcal{S}}=\mathcal{S}$.

  * •

$\overline{\mathcal{A}}=(\mathcal{S}\times\\{p\\})\cup\mathcal{A}\cup(\mathcal{S}\times\\{t\\})\cup\mathcal{R}$,
where $(s,p)$ is a perceived state attack and $(s,t)$ is a true state attack.

  * •

$\overline{P}_{h}(\overline{s}^{\prime}\mid\overline{s},\overline{a})$’s
definition varies depending on the choice of $\overline{a}$. Suppose that $s$
is the current state at time $h$. Then,

    * –

If $\overline{a}=(s^{\dagger},p)\in\mathcal{S}$ is a perceived-state attack,

$\overline{P}_{h}(s^{\prime}\mid s,(s^{\dagger},p))=P_{h}(s^{\prime}\mid
s,\pi_{h}(s^{\dagger})).$

    * –

If $\overline{a}=a^{\dagger}\in\mathcal{A}$,

$\overline{P}_{h}(s^{\prime}\mid s,a^{\dagger})=P_{h}(s^{\prime}\mid
s,a^{\dagger}).$

    * –

If $\overline{a}=(s^{\dagger},t)\in\mathcal{S}$ is a true-state attack,

$\overline{P}_{h}(s^{\prime}\mid s,(s^{\dagger},t))=P_{h}(s^{\prime}\mid
s^{\dagger},\pi_{h}(s^{\dagger})).$

    * –

If $\overline{a}=r^{\dagger}\in\mathcal{R}$,

$\overline{P}_{h}(s^{\prime}\mid s,r^{\dagger})=P_{h}(s^{\prime}\mid
s,\pi_{h}(s)).$

and all other transitions have probability $0$ at time $h$.

  * •

$\overline{r}_{h}(\overline{s},\overline{a})$’s definition similarly depends
on $\overline{a}$ as well as the form of $\overline{s}$. Using the same
definitions as above, we have

    * –

If $\overline{a}=(s^{\dagger},p)\in\mathcal{S}$ is a perceived-state attack,

$\overline{r}_{h}(s,(s^{\dagger},p))=g(s,r_{h}(s,\pi_{h}(s^{\dagger}))).$

    * –

If $\overline{a}=a^{\dagger}\in\mathcal{A}$,

$\overline{r}_{h}(s,a^{\dagger})=g(s,r_{h}(s,a^{\dagger})).$

    * –

If $\overline{a}=(s^{\dagger},t)\in\mathcal{S}$ is a true-state attack,

$\overline{r}_{h}(s,(s^{\dagger},t))=g(s,r_{h}(s^{\dagger},\pi_{h}(s^{\dagger}))).$

    * –

If $\overline{a}=r^{\dagger}\in\mathcal{R}$,

$\overline{r}_{h}(s,r^{\dagger})=g(s,r^{\dagger}).$

  * •

$\overline{\mu}(s)=\mu(s)$ for each $s\in\mathcal{S}$ and
$\overline{\mu}(\overline{s})=0$ otherwise.

##  Appendix B Proofs for section Section 4

The proof of Proposition 3 and Proposition 4 is immediate from the definitions
of the defense problem, the victim-attacker-environment interaction, and the
definition of turn-based stochastic games [7].

#### Proof of Proposition 5.

###### Proof.

We show that the defense problem with observation or perceived-state attacks
captures solutions to POMDPs. As such, all hardness results for POMDPs apply
to Defense. Namely, computing $\epsilon$-optimal deterministic Markovian
policies is NP-hard [15]. Also, for the discounted infinite horizon case,
computing an optimal stationary stochastic memory-less policy is NP-hard [25].

We note any POMDP can be formulated as an equivalent POMDP with a
deterministic observation function that is only polynomially sized larger.
Thus, we can focus on POMDPs with a deterministic observation function
$o:\mathcal{S}\to\mathcal{O}$. We can also assume that
$\mathcal{O}\subseteq\mathcal{S}$. Given such a POMDP, define $M$ to be the
same as the POMDP ignoring the observation part, and define the set
constraints for a perceived-state attack to be the singleton
$B(s)=\\{o(s)\\}$. This ensures the only feasible attack $\nu$ is exactly the
observation function $o$. Thus, solving the defense problem for a maximum
policy $\pi$ over some class of policies $\Pi$ is exactly equivalent to
solving the POMDP over that class of policies $\Pi$. Hardness then follows.

∎

The proof of Proposition 6 follows from 1 and the stated complexity results.

#### Proof of Theorem 2.

We present a formal backward induction algorithm for computing defenses. We
define $V^{*}_{h,1}(s):=\max_{\pi\in\Pi_{h}}\min_{\nu\in
BR_{h}(\pi)}V^{\pi,\nu}_{h,1}(s)$, where $\Pi_{h}$ is the set of Markovian
partial policies from time $h$ forward,
$BR_{h}(\pi):=\operatorname*{arg\,max}_{\nu\in N_{h}}V^{\pi,\nu}_{h,2}(s)$,
and $V^{\pi,\nu}_{h,i}(s)$ is the value of the stage game $(h,s)$ for player
$i$ (i.e. their expected value from time $h$ onward starting from state $s$).
It is clear that $V^{*}_{h,1}(s)$ admits optimal substructure: if
$\pi^{*}_{h}(s)$ is a maximizer of $V^{*}_{h,1}(s)$, then it must be the case
that $\pi^{*}_{h+1}(s^{\prime})$ is a maximizer of $V^{*}_{h+1,1}(s^{\prime})$
for any $s^{\prime}$ reachable with non-zero probability under
$\pi^{*}_{h}(s)$. Otherwise, more value could be achieved by improving the
value in the future. This is the standard argument for why rollback
successfully computes a subgame perfect equilibrium in sequential games. Here
it is crucial that the defense problem is captured by a turn-based game, which
gives us this sequential structure. Given this observation, it is clear that
$V^{*}_{h,i}(s)$ can be computed recursively as follows. Suppose the victim
already computed its optimal $\pi^{*}_{h+1}$. Then, $\pi^{*}_{h}(s)$ can be
computed as a maximizer of $V^{*}_{h,1}(s)$, where:

$V^{*}_{h,1}(s):=\max_{a\in\mathcal{A}}\min_{a^{\dagger}\in
BR_{h}(s,a)}\mathbb{E}_{r\sim R_{h}(s,a^{\dagger})}\left[\min_{r^{\dagger}\in
BR_{h}(s,a^{\dagger},r)}r^{\dagger}+\mathbb{E}_{s^{\prime}\sim
P_{h}(s,a^{\dagger})}\left[\min_{s^{\dagger}\in
BR_{h+1}(s^{\prime})}V_{h+1,1}^{*}(s^{\dagger})\right]\right].$ (3)

Each best-response function is defined as follows. In each case, the attacker
must wait for further information and then adapt to each realization. Hence
the separate best-response functions.

$BR_{h}(s,a):=\operatorname*{arg\,max}_{a^{\dagger}\in\overline{\mathcal{A}}_{h}(s,a)}\mathbb{E}_{r\sim
R_{h}(s,a^{\dagger})}V^{*}_{h,2}(s,a,r).$ (4)

$\displaystyle
BR_{h}(s,a,r):=\operatorname*{arg\,max}_{r^{\dagger}\in\overline{\mathcal{A}}_{h}(s,a,r)}g_{h}(s,a,r^{\dagger})+\mathbb{E}_{s^{\prime}\in
P_{h}(s,a)}V^{*}_{h+1}(s^{\prime}).$ (5)

$BR_{h+1}(s):=\max_{s^{\dagger}\in\overline{\mathcal{A}}_{h+1}(s)}V^{*}_{h+1,2}(s^{\dagger},\pi_{h+1}(s^{\dagger})))$
(6)

In all cases, $V^{*}_{h+1,2}(\cdot)$ is defined to be the maximizing value for
each corresponding $BR$ set.

In the zero-sum case, we get the even simpler expression,

$V^{*}_{h,1}(s)=\max_{a\in\mathcal{A}}\min_{a^{\dagger}\in\overline{\mathcal{A}}_{h}(s,a^{\dagger})}\mathbb{E}_{r\sim
R_{h}(s,a^{\dagger})}\left[\min_{r^{\dagger}\in\overline{\mathcal{A}}(s,a^{\dagger},r)}r^{\dagger}+\mathbb{E}_{s^{\prime}\sim
P_{h}(s,a^{\dagger})}\left[\min_{s^{\dagger}\in\overline{\mathcal{A}}(s^{\prime})}V^{*}_{h+1,1}(s^{\dagger})\right]\right].$
(7)

Since turn-based games admit deterministic solutions, it is clear that the
victim can compute its optimal defense in polynomial time by simply brute-
force computing each $\max$ and $\min$ in the above expressions, which are
finite optimizations in the tabular case.

##  Appendix C Code Details

We conducted our experiments using standard python3 libraries. We provide our
code in a jupyter notebook with the example grid being hard-coded in to ensure
the experiments can be easily reproduced.