Defense Against Reward Poisoning Attacks in Reinforcement Learning
Authors: Kiarash Banihashem
Adish Singla
Goran Radanovic
Venue: Accepted by TMLR ()

Abstract: We study defense strategies against reward poisoning attacks in reinforcement learning. As a threat model, we consider cost-effective targeted attacks---these attacks minimally alter rewards to make the attacker's target policy uniquely optimal under the poisoned rewards, with the optimality gap specified by an attack parameter. Our goal is to design agents that are robust against such attacks in terms of the worst-case utility w.r.t. the true, unpoisoned, rewards while computing their policies under the poisoned rewards. We propose an optimization framework for deriving optimal defense policies, both when the attack parameter is known and unknown. For this optimization framework, we first provide characterization results for generic attack cost functions. These results show that the functional form of the attack cost function and the agent's knowledge about it are critical for establishing lower bounds on the agent's performance, as well as for the computational tractability of the defense problem. We then focus on a cost function based on $\ell_2$ norm, for which we show that the defense problem can be efficiently solved and yields defense policies whose expected returns under the true rewards are lower bounded by their expected returns under the poison rewards. Using simulation-based experiments, we demonstrate the effectiveness and robustness of our defense approach.

Published in Transactions on Machine Learning Research (01/2023)
Defense Against Reward Poisoning Attacks in Reinforce- ment Learning
Kiarash Banihashem University of Maryland
kiamash@udd.com edu
Adish Singla Mar. Planck Institute for Software Systems
adishs
Goran Radanovic
gradanonic@mpii..us.or
Maz Planck Institute for Software Systems
Reviewed on OpenReview: https; // opwnreveew.........mmmoo net/ formm? id= goPsLn3RVo
Abstract
We study defense strategies against reward poisoning allacks in reinforcement learning. As a threat model, we consider cost-effective targeted attacks attacks-these attacks minimally alter rewards to make the attacker's target policy uniquely optimal under the poisoned rewards, with the optimality gap specified by attack parameter. Our goal is to design agents that are robust against such attacks in terms of the worst-case utility w.r.t. the true, umpoisoned, rewards while computing their policies under the poisoned rewards. We propose an optimization framework for deriving optimal defense policies, both when the attack parameter known and unknown. For this optimization framework, we first. provide characterization results for generic attack cost functions. These results show that the functional form of the attack cost function and the agent's knowledge about it critical for establishing lower bounds the agent's performance, well as for the computational tractability of the defense problem. We then focus on cost function based on l norm, for which we show that the defense problem can be efficiently solved and yields defense policies whose expected returns under the true rewards are lower bounded by their expected returns under the poison rewards. Using simulation-based experiments, we demonstrate the offectiveness and robustness of our defense approach.
1 Introduction
One of the key challenges in designing trustworthy AI systems is ensuring that they are technically robust and resilient to security threats European Commission (2019). Amongst many requirements that an AT system ought to satisfy in order to be deemed trustworthy is robustness to adversarial attacks Hamon et al. (2020). Standard approaches to reinforcement learning (RL) |Sutton Barto (2018) have shown to be susceptible adversarial attacks which manipulate the feedback that an agent receives from its environment. These attacks broadly fall under two categories: a. test-time attacks, which manipulate agent's 's input data at test-time without changing its policy HHang et al. (2017); Lin et al. (0017); [Tretsckk et al. (2018); Kunar et al. 2021
and b) training-time time attacks that manipulate an agent's 's input data at training time, influencing the agent's
learned policy Zhang & Parkes (2008) Ma et al. (2019): Huang & Zhu (2019) Rakhsha et al. (2020) 2021
Zhang et al. (2020b):(un) et al. 2020); Liu & Lai 2021) Rangi ct al. (2022). In this paper, we focus on training- time atlacks, and more specilically, on largeled reaoord poisoning allacks that modily (i.e., poison) rewards
force an agent into adopting a target policy Ma al. (2019): Rakhsha al. (2021); [Ragii et al. (2022).
Prior work reward poisoning attacks RL primarily focuses on designing optimal attacks. In this paper,
*This work was done part of internship project Max Planck Institute Software Systems.

---

Published in Transactions on Machine Learning Research (01/2023)
take a different perspective targeted reward poisoning attacks, and focus designing defense strategies against such attacks. This is challenging, given that the attacker is typically unconstrained in poisoning the rewards to force the target policy, while the agent's 's performance is measured under the true reward function, which is unknown. The key idea that we exploit in our work is that the poisoning attacks have an underlying structure arising from the attacker's objective to minimize the cost of the attack needed to force the target policy. We therefore ask the following question:
Con design an effective defense strategy against torgeted reward poisoning attacks by exploiting the cost- effective nature of these attacks?
2.50
0.50
0.50
-2.50
0.13
0.61
-0.50
0.19
$2
$3
8D
$1
$2
$3
-2.50
-2.50
0.50
0.50
-0.50
0.50
0.07
-0.50
0
0
0
0
0
1
0
0
1
(a) R, n
(b) R, π
-2.50
0.13
0.61
0.19
Policy
n²
TD
MDP
-2.50
0.50
0.07
-..0
π
0.34
-0.42
0.03
0.94
0.06
N
-0.03
0.11
0.03
(c) R. RD
(d) Scores of policies n² ,,,,, ND in MDPs w.r.t. R,
A simple chain environment with 4 states and two possible actions: left and right. is the initial state. The agent goes in the direction of its action with probability 90%, and otherwise the next state is selected uniformly at random from the other 3 states. Weights on edges indicate rewards for the action taken, For example in Fig. [a] if the agent takes left in state 81, it receives 0.5. We denote the true rewards by R, the poisoned rewards by R, the optimal policy under R by x², the target policy (which is uniquely optimal under R) by Ty, and the defense policy (which is derived from our framework) by kD. (a) shows R and
Figure 1:
x². In particular, the numbers above the arrows and the different shades of gray show the probabilities of taking actions left and right under πτ. (b) shows R and Ty. (c) shows TD that our optimization framework dcrived from R, and by reasoning about the goal of the attack (T²). In particular, our optimization framework maximizes the worst-case performance under R: while the optimization procedure does not know R, it can constrain the set of plausible candidates for using R. (d) Table. id]: Fach entry in the table indicates the score of (policy, reward function) pair, where the score is a scaled version of the total discounted return (see Section 3). For example, the score of policy ग equals -0.42 and 0.11 under R and R respectively. Our defense policy significantly improves upon this and achieves a score of 0.03. For comparison, the score of n* equals 0.34. Moreover, unlike for the target policy Tt, the score of our defense policy TD under R is always at least as high as its score under R, as predicted by our results (see Theorem 5.1 The results are obtained with parameters et = 0.1, ep = 0.2 and 7 = 0.99 (see Section 3).
In this paper, we study this question in depth and under different assumption on the agent's knowledge about the attack cost function. Perhaps surprisingly, the answer to this question is sometimes affirmative. While an agent only has access to the poisoned rewards, it may still be able infer some information about the true reward function, using the fact that the attack is cost-cffective. By maximizing the worst-casc utility over the set of plausible candidates for the true reward function, the agent can substantially limit the influence of the attack. The approach we study can be understood from Figure which uses the chain environment from Rakhsha et al. (2021) to demonstrate the main ideas.
Contributions. We formalize this reasoning, and characterize the utility of our novel framework for designing defense policies. In summary, the key contributions include:
We formalize the problem of designing defense policies against targeted and cost-cffective reward poisoning attacks, which minimally modify the original reward function to achieve their goal (force target policy).
2

---

Published in Transactions on Machine Learning Research (01/2023)
We introduce novel optimization framework for finding optimally robust defense policies this framework focuses on optimizing the agent's worst-case utility among the set of reward functions that are plausible candidates of the true reward function.
We provide characterization results that establish feasibility and computational complexity of finding optimally robust defense policies for different classes of attack cost functions. These results show that the functional form of the attack cost function and the agent's knowledge about it play a critical role in deriving optimally robust defense policies with provable performance guarantees.
Focusing on a cost function based on l2 norm, we show that optimally robust defense policies can be efficiently computed. We further cstablish lower bounds on the true performance of defense policies derived from our framework and computable from the poisoned rewards.
We empirically demonstrate the effectiveness and robustness of our approach using numerical simulations.
To our knowledge, this is the first framework for studying this type of defenses against reward poisoning attacks that try to force a target policy at a minimal cost.
2
Related Work
While this paper is broadly related to the literature on adversarial machine learning (c.g., Huang et al. (2011)) )
we recognize four themes in supervised learning (SL) and reinforcement learning (RL) that closely connect Lo
our work.
Poisoning attacks in SL and RL. This paper is closely related data poisoning attacks, first introducod
and extensively studied supervised learning Biggio et al. [2012]: Xiao al. (2012); Mei & Zhu (2015); Xiao
et al.
2015 Li et al.] (2016); Koh & Liang] (2017): Biggio & Roli (2018). These attacks are also called
(2017); [Behzadan & Madry et al. (011)), which atlack an already trained agent, they change data points during the training phase, which in turn
training- time attacks, and unlike test time attacks Szegedy et al. (0014h; Pinto et al.
Munir (2017); Zhang et al. (2020a): Moosavi-Dezfooli et al. (2016) Nguyen et al. [2015]
affects the parameters of the learned model. Data poisoning attacks have also been studied in the bandits literature Jun et al. (2018); MM et al. (2018); Liu & Shroff) (2019) and in RL (see Section D
Defenses against poisoning attacks in SL. In supervised learning, defenses against data poisoning
attacks are often based on data sanitization that removes outliers from the training set Cretu al. (2008);
Paudice et al. (2018), trusted data points that support robust learning Nclson et al. (2008); Zhang et al.
(2018), or robust estimation Charikar el al. (2017); Diakonikolas et al. (2019). Recently, Wu et al. (2022) have considered aggregation based defenses that can certify an RL agent's ' policy against a limited number of changes in the training dataset. While such defenses can mitigate some attack strategies, they are in general susceptible to data poisoning allacks Steinhardt et al. (2077); Koh et al. (2018).
Robustness to model uncertainty. There is a rich literature that studies robustness to uncertainties
reward functions McMahan et al. (2003); Regan & Boutilier (2010), and transition models Nilim & El Ghaoui (2005); [yengar [2005] [Bgnell et al. (2001) for MDP models. Typically, these works consider settings in which instead of knowing the exact parameters of the MDP, the agent has access to set of possible parameters (uncertainty set). These works design policies that perform well in the worst case. More recent works have proposed ways to scale up these approaches via function approximation Tamar et al. (0014), as well as utilize them in online settings Lim et al. (2013). While our work uses the same principles of robust optimization, we do not assume that the uncertainty set, i.c., the set of all possible rewards, is directly given. Instead, we show how to derive it from the poisoned reward function.
Robustness to corrupted episodes. Another important line of work is the literature on robust learners that receive corrupted input during their training phase. Such learners have recently been designed for bandits and experts scttings Lykouris et al. (2018); ; Gupta et al. (2019) Bogunovic et al. (2020); Amir et al. (2020), and episodic reinforcement learning Lykouris el al. (201)); Zhang et al. (2021). Typically, these works consider an attack model in which the adversary can arbitrarily corrupt a limited number of episodes. As we operate the non-episodic sctting and do not assume a limit in the attacker's poisoning budget, these works are orthogonal to the aspects we study in this paper. Instead, we utilize the structure of the attack in order to design defense algorithm.
3

---

Published in Transactions on Machine Learning Research (01/2023)
3 Formal Setting
In this section, describe our formal sctting, and identify relevant background details reward poisoning allacks, as well as our problem stalement. The problem formulation specifies our objectives that we establish and formally analyze in the next sections.
3.1 Preliminaries
We consider a standard reinforcement learning setting in which the environment is described by a discrcto-time
discounted Markov Decision Processes (MDP) Puterman (1994), defined as M = (S, A, R, P, 7, 0), where: S is the state space, A is the action space, R: S x A R is the reward function, P: S xxSxxxx is the transition model with P(s, s') defining the probability of transitioning to state s' by taking action in state 8, 7 E 10) 1) is the discount factor, and is the initial state distribution. We consider stale and action spaces, i.e., S and A, that are finite and discrete, and due to this we can adopt a vector notation for quantities dependent on states or state-action pairs. W.l.ogg,, we assume that |A] 2 2.
[o, 1]
A generic (stochastic) policy is denoted by æ, and it is a mapping π : S + P(4), where P(A) is the probability simplex over action space A. We use (aass) to denote the probability of taking action a in state 8. While deterministic policies are a special case of stochastic policies, when explicitly stating that policy is deterministic, we assume that it is a mapping from stales actions, i.e,, क - A. We denote the set of all policies by II and the set of all deterministic policies by IIdet, For policy 9, we define its score, pt, E [(1 -"= R(st, (t)),a o). where state 81 is sampled from the initial state distribution Ø, and then subsequent states 9t are obtained by executing policy π in the MDP. The score of a policy is therefore its total expected return scaled by a factor of 1-%,
Finally, we consider occupancy measures, We denote the state-action occupancy measure in the Markov chain induced by policy æ by ()' a) = E [(1 ((1-)) 7) 1 [s = s, a, = a] |T, o|. Given the MDP M, the set of realizable state-action occupancy measures under any (stochastic) policy π E II is denoted by V. Score p² and vhth satisfy pT (vl R), where (...) computes the dot product between two vectors of sizes [S] [A]. We denote by μ² (s) E [11 (1->))> - [s, = s) |T, a] the state occupancy mcasure in the Markov chain induced by policy π E II. State-action occupancy measure (s, and state occupancy measure μt" ((((s)) satisfy 16 (*(88) a) = 1= (8) π (a]ss) We focus on ergodic MDPs, which in turn implies that y²((s) > 0 for all v and 8 Puterman (1994). This standard assumption in this line of work (e.g, see Rakhsha et al. (222)) and is used to ensure the fcasibility of the attacker's optimization problem.
[
3.2 Reward Poisoning Attacks
We consider reward poisoning attacks on offline learning agent that optimally change the original reward function with the goal of decciving the agent to adopt deterministic policy म₁ E TTdet, called target policy. This type of attack has been extensively studied in the literature, and here we utilize the attack formulation based on the works of Ma et al. [2019); Rakhsha et al. (2020) 2021); Zhang et al. (2020b). In the following, we introduce the necessary notation, the attacker's model, and the agent's 's model (without defense). Notation. We use M to denote the true or original MDP with true, unpoisoned, reward function R, i.c., M ( A, R. We use M to denote the modified or poisoned MDP with poisoned reward function R, i... M = R. Note that only the reward function R changes across these MDPs. Quantitics that depend on reward functions have analogous nolation. For example, the score of policy æ under is denoted by p", whereas its score under R is denoted by pa. We denote an optimal policy under R by T², i.e., X² E arg max p".
Attack model. The attacker consider in this paper has full knowledge of M. It can be modeled by function A(c, R', (t) that returns a set of poisoned rewards functions for a given attack cost function c, In particular, the attack problem is
reward function Rt, target policy ग,. and desired attack parameter et H
defined by the following optimization problem:
min c(R, R') s.t. p²t p" + + VT e Iadert {Tt). R
(P1)
For cost functions up defined by with finite p > 1, this has single element.
4

---

Published in Transactions on Machine Learning Research (01/2023)
A common class of cost functions are fy-norms of manipulations Ma et al. (019 I.e.,
Rakhsha et al.
2020
2021
c R) = cp = | - R'Ipp
(1)
with p 2 1. As shown by Rakhsha et al. functions and ergodic MDPs. Furthermore, instead of considering all deterministic policies, it is sufficient to consider policies that differ from xi in single action. Using ग [8;a] to denote policy that follows + क (s)
(2021) , the attack problem P1 is feasible for this class of cost
in state and (3) in states ă ss P can be rewritten as follows:
min R
c R, R')
s.t. p" 2 pm, gotasa t Vs,a
(P1')
The equivalence between PI and PT is shown by Rakhsha et al. (2021 but we also provide further details in Appendix. Intuitively, [P1 and P are equivalent because in order for a policy to be optimal it is sufficient (and necessary) that the policy is better than any of its neighbor policies. This fact allows us to reduce the number of constraints. Whereas the number of constraints in (P1) is exponential in [S] and |A], the number of constraint in (P1' is polynomial in [S] and [A], which in turn implies that (PT) is tractable (for fixed p).
To better understand the optimization problem P1 we can consider & attack cost (i.e., 62) defined as the Euclidean distance between R' and R. By solving this problem, i.e., setting R E Afez, R, et), the attacker finds the closest reward function to R for which тH is uniquely optimal policy (with attack parameter 4)) Remark 3.1. Note that the optimization problem (P1 may not be feasible if we lift the assumption that underlying MDP is ergodic. This can be seen from the constraints of the optimization problem (P): p: if target policy πt does not visit a certain state s, then has the same score as its neighbor policics (s; Hence, the primary reason for assuming ergodicity is to make the attack problem feasible.
Agent without defense. The agent receives the poisoned MDP M := (S, (S P,Y,P, o) where the underlying true reward function R (unknown to the agent) has been poisoned to R. In the existing works reward poisoning altacks, an agent naively optimizes score P (score w.r.t. R). Because of this, the agent ends up adopting policy it..
3.3 Problem Statement
Perhaps unsurprisingly, the agent without defense, could perform arbitrarily badly under the true reward function R. Our goal is to design a robust agent that derives its policy using the poisoned MDP M = (S, A, o)), but has provable worst-case guarantees w.r.t. R. This agent has access to the poisoned reward vector R Alc, R, eT), but R, Tt, and et are not given the agent. Figure 2 illustrates generic problem setting studied in this paper. In general, the agent does not know c, but is given a class of cost functions C that contains e, i.e., C C. C represents' the agent's knowledge about the attack cost function; in special case when C contains only one element, the agent knows the cost. function. Notice that गт is obtainable by solving the optimization problem arg max, p as गi is uniquely optimal in M. On the other hand, R is unknown to the agent. In terms of et, we will focus on two cases, the case when et is known to the agent, and the case when it is not.
In the first case, we can formulate the following optimization problem of maximizing the worst case performance of the agent, given that R is unknown:
max min p" T R.CEC
s.t. A(c
(P2a)
In other words, we calculate the set of all possible reward functions R such that an attack on R could lead to the solution R, ic., R E A(c, R, (F, We then find a policy æ for which the worst-case score, i.c., min p" is maximized, where the minimum is over all reward functions R calculated previously and all cost functions E.C. C.
5

---

Published in Transactions on Machine Learning Research (01/2023)
True reward function R
Attack A (cost target mt))
Poisoned reward function R
Defense D (score under R)
Defense policy
Poisoned reward function R
Find the set of reward functions consistent with I and .
Find policyy that maximizes the worst-case score over this set
Defense policy T
The problem setting studied in this paper. The attack A modifies the original (true) reward function R to force xt while minimizing its cost. The defense 'D aims to optimize the agent's 's score under R, but it only sees the poisoned reward R. Nevertheless, it can (in principle) find the set of all reward functions consistent with and A, and search for a policy that maximizes the worst-case score the agent over this consistent set.
Figure 2:
Knowledge about attack cost.
Guarantees on the value
Complexity
General C (e.g., s.t. Cconst C) C C= [|] R'll, s.l. p peppeel [1,
No for any R. Proposition 4.2
Yes, Theorem 4.4
NP-hard, Theorem 4.5
R R' cloo)
No for some R, Theorem 4.3
NP-hard, Appendix
R| l
R'
Yes, Section
Convex, Section
[||R R' R'Il |
Yes, Appendix
Convex, Appendix
Table 1: Characterization results for different levels of the agent's knowledge about the attack cost function, expressed through C. In general, if C can be arbitrary, the optimization problem (P2a) may be unbounded from below regardless of R. For some classes C, c.g., that contain fp-norm attack costs (p + oo), [Paa] has
the optimal solution, but. this solution may be computationally hard. When the allack cost. function known,
properties problem (Pa)) depend on the functional form of the attack cost function, indicated by the f--nomm, fg-norm, and -norm attack costs.
For the case when the agent does not know Et, we use the following optimization problem:
max min P s.t. R.C.CC
m+, and 0 < < CD.
(P2b)
where the agent uses éD as an upper bound on We denote solutions to the optimization problems (Paa and P2b) by TD, and it will be clear from the context which optimization problem we are referring to with WD-
Remark 3.2. We note that some structural assumptions on the attack model are needed to guarantee robustness. For example, prior work typically considers untargeted attacks with budget constraints, e.g., that put an upper limit on the cost the attack or the number of episodes in which the attacker can attack Lykouris et al. (2019): Zhhang et al. (2021). This paper focuses on targeted attacks that minimize the cost of the attack. Given the strategic nature of the attacker, the structural assumptions the attack model that [2a and P2bb rely on are fairly natural.
4 Characterization Results for Generic Attack Cost
In this section, we provide characterization results showing the importance of the agent's knowledge about the attack cost function. The overview of the characterization results is shown in Table I To corresponding proofs can be found in Appendix.
Remark 4.1. The results presented this section are stated for the optimization problem the same results also hold for the optimization problem (22b).
P2a However,
4.1 General Attack Cost
We start by stating what is perhaps an expected result: if the attack cost function can be arbitrary, then no defense achieve any provable guarantee. It. is relatively easy to see why this claim should hold. If the

---

Published in Transactions on Machine Learning Research (01/2023)
agent believes that the attack cost function can be constant, then from the agent's perspective, R. can be any reward function. Since rewards are not bounded, this in turn implies that no matter which policy the agent selects, no worst-case guarantees are possible. More formally, we obtain the following claim.
Proposition 4.2. Let Coonst R)) be a constant cost function, and assume that Cconst E C. Then the oplimization problem P2a) is unbounded from below.
Given this result, it is clear that for provable defenses: a) the attack cost function cannot not be arbitrary in that R has to be informative about R; b) the agent should have some knowledge about the attack cost function. In the next subsection, we consider cost functions based on lp norms, i.e., Cp, commonly adopted
by prior work on reward poisoning at attacks Ma et al. (019 Rakhsha et al. 2020 2021
4.2 Ep Attack Cost
In contrast to constant cost functions, the strategic nature of the attacker is more apparent when it optimizes Cp, so the agent may infer some information about the true reward function R from the poisoned rewards R which it can access. Our first result shows that for p p= xo the success of such an inference procedure depends on R. This formally captured by the following theorem.
Theorem 4.3. There erists an instance of the problem setting, i.e., MDP M = (S, R, P,7,,) for which the optimization problem
(2a) is unbounded from below when Coo E C.
This theorem paints a relatively bleak picture for the possibility of achieving provable guarantees. Note two important observations. First, the impossibility result is weaker variant of the result stated in Proposition 4.2 it holds only for some MDPs. Second, Coo is measuring the maximum modification of reward function R, so critical information about R may be lost-this also provides intuition behind the impossibility results. In contrast, when p & 0o, Cp is affected by all the modifications of R. In fact, when p is restricted to take values in o0), lower bound on the optimal value of (Paa) can always be derived from R.
Theorem 4.4. Consider any policy Tz, s.t. Tzz (s))s) O. For C = {cp s.t. p E [1,)0)), the optimal value of the oplimization problem P2a is bounded from below by T*
4.4 is that the optimal solution to P2a al always exists, and its worst case performance under R is at least ft ft. Note that we can easily find a (deterministic) policy T7, that maximizes the lower bound by solving max, s.t. (()))(m(()) pm Furthermore, for any policy Tr, s.t. Tr, (T+(s))s) = 0 we have that gd ptt, This means that we can efficiently find defense policy with provable performance guarantecs. However, such defense policy may not be optimally robust in that its performance lower bound would not match the optimal one. We now turn to computational complexity challenges in deriving optimally robust defense policies: the next theorem provides a hardness result for C = {cp s.t. p E (0)], which admits guarantees on the optimal solution to P2ab.
A direct consequence of Theorem
Theorem 4.5. For C = {cp s.t. e [1, } it is NP-hard to determine whether the optimal value of the optimization problem P2ah is greater than or equal to pTt
Given that even for this natural choice of cost functions, C C= (cp s.t. p [1)], the problem of finding optimally robust policies is computationally hard, in the next section we focus on la attack cost that is known to the agent, i.c., C = {c2). In Appendix, we provide similar analysis for & attack cost, i.c., C {c1.
5 Characterization Results for l Attack Cost
In this section, consider the attack cost function 02 and assume that it is known to the agent (C fc21). In the first. part, we focus on characterization results for the case when the attack parameter 6, is known to the agent, i.e., the optimization problem [P2a). In the second part, we focus on the optimization problem P2bb,, and generalize the results from the first part to the unknown attack parameter setting. The proofs of our formal results can be found in Appendix. Figure 3 provides intuition behind the results of this section.
Stoochstiic policies are necessary in this case since we can think of this problem searching for an optimal policy over truncated actions space (because actions ny (s) are not admissible), so an optimal deterministic policy always exists.
7

---

Published in Transactions on Machine Learning Research (01/2023)
In particular, it illustrates attack and defense strategies for single-state MDP with action set fai,...07) and the & cost function. We refer the reader to Appendix for more details.
10
10
8
6-
6
6-
4
4
4.
2-
2
2
0-
0
01 02 03 04 dg
Og
47
0g 03 Og as 07
02 d5
Actions
Actions
Actions
1 0 0 (a)
000
(b) R T
(c) R. RD
Figure single-state environment environment with 7 actions and state s. In each figure, the denoted policy uniform over actions on above the dashed line. (a) shows Rt and n² Here, the optimal policy selects action d1 (b) shows R and target policy ot with et = 1. Here, the target policy selects action 04. ft is obtained by solving [1 (or (PT)) with the le cost function and R' R. In this case, the attack only modifics the rewards of throe actions, 01, d4, and 07- (c) shows R and TD with cp = The defense strategy only sees poisoned rewards R. It first calculates the optimal action and the set of all second-best actions under R, in this case {a1, 07). If the reward of the second-best actions are no worse than they form the set er = {(ss (s, a7)} or simply 0; = {ai. a7). We show in Appendix that the defense strategy, ie., the solution to (P2b), selects an action uniformly at random from the set {8)( U = (01, 04, (7). As we show in this section, the expected reward of the defense policy under R is at least as much its expected reward under R, which can be easily verified from the figures: in this case, both are equal to 22/3.
5.1 Known Parameter Setting
We begin by analyzing the optimization problem P2a] Denote by O state-action pairs (s, as.a) )) for which the difference between gat and (= equal to E, i.e., O- = {(s a) (rrisat - - = - For the results of this section, O with e c plays critical role as we show in our formal analysis, it characterizes the feasible set of the optimization problem P2ah. In particular, in our analysis we show that R is the solution to the attack problem for an underlying reward function R, i.e., R = A(R, t4, e4), if and only if R can be expressed as
R= R
Σ assa
(Urrissst v)
(s.0)E0"t
with 0s.a 2 0. To see the importance of this result, let us instantiate = R and calculate p":
as.a (wetrteeat) 2b 25t))
p" (1) R
(8.0)E0*
When the occupancy measure of कD is positively aligned with vectors (f , the performance of Tp under the original reward function R. is at least p = ( (R,, R). Hence, constraining TD to satisfy (1aa)) d ) 2 0 for all s, a E Off yields a guarantee on the score p=D, i.c., RD > pEp. These insights formalized by Theorem 5.1 which also describes procedure for solving P2a In Appendix, we provide intuition behind our analysis using special case of our setting.
In practice, 6 should calculated with some tolerance due to numerical imprecision (See Section
8

---

Published in Transactions on Machine Learning Research (01/2023)
Theorem 5.1. Consider the following optimization problem parometerized by c: ,,,,,,)),
max 6. R R)
s.t. (wrt(sa) - 2b) 2 as,
(P3)
PEV
For = this optimization problem is always feasible, and its optimal solution vmmax specifies an optimal solution to the optamázation problem P2a for C {c2} with
4'max (s,
TD(aas) = En max (8)
(2)
The score of (a)s)) is lower bounded by g 2 pm
In addition to providing characterization of the solution to (Paa), the above theorem provides an efficient algorithm for finding this solution using linear programming. As we discuss in Appendix [D.3] the set of vectors 6 and d (sa) can be precomputed since the agent is given a poisoned model (and hence, knows the transition probabilities); for any policy n, the state-action occupancy measure a satisfies 1h (s, a) (s) -T(as)) where the state occupancy measure μ² is the unique solution the following Bellman identity
(s) (1 (1-7) + (m(
3,
In addition, the set valid occupancy measures the set of all vectors is RSSH-A satisfying the following Bellman flow constraints
Σ = (1 + Σ P(s, (3,
8
V(s (s. 2 0.
Therefore, since occupancy measures (=:a)=)) and ,T can be procomputed, the optimization problem P3 can be elficiently solved using linear programming. In other words, computing optimally robust defense policy is computationally tractable. In order to calculate each ,e" we need to solve |S] x |S] system of linear equations, which requires |S|S operations in the worst case. Therefore, finding each v5 for a E { U {T+{:; : a * (s)) requires at most - operations. The linear program (P3) takes O(SSM- [A[t) time the worst case as has |A| constrains and variables. Therefore, the overall complexity
of the approach is O(SS) [A]$) in the worst case.
Theorem 5.1 also provides performance guarantee of the defense policy w.r.t. the true reward function, i.e., 7ED 2 pTP Such bound is important in practice since it provides a certificate of the worst-case performance under the true reward function R, even though the agent can only optimize over R. In contrast to the lower bound in Theorem 4.4 The lower bound in Theorem 5.1 is optimal.
5.2 Unknown Parameter Setting
In this subsection, we focus on the optimization problem P2b First, note the structural difference between (Paa) and (P2b). In the former case, 4 is given, and hence, the defense can infer possible values of by solving an inverse problem to the attack problem (PI). In particular, we know that the original reward function R has to be in the set {R: R A(R, ,t. xt,E))). In the latter case, et is not known, and instead we use parameter ép as an upper bound on cy. We distinguish two cases:
Overestimating Attack Parameter: ef S ED; then we know that is in the {R: R A(R, TT, s.t. 0 <<ep), Note that this set is a super-set of (R: å A(R, 6)),, which means that it less informative about R.
Underestimaling Allack Parumeter: If et > eD, then the set (R: R A(R, TT,)) (....)... 8.1. 0 < S <D) will have only single element, i.e,, R. In other words, this set typically contains no information about Rt
We analyze these cases separately, first. focusing on the former
9

---

Published in Transactions on Machine Learning Research (01/2023)
5.2.1 Overestimating Attack Parameter
When cp 2 ct, our formal analysis builds on the one presented in Section 5.1 and we highlight the main differences. Given that et is not exactly known, we cannot directly operate on the set @ However, since ep upper bounds Cj, the defense can utilize the procodure from the previous section (Theorem 5.1 with appropriately chosen to solve (P2b) as we show in the following theorem.
Theorem 5.2. Assume that ED 2 ct, and define == mins, 10t Then, the optimization
problem P3) with e = min <<D.] 3 is feasihle and ils optimal solution 1/max identifies an optimal policy wp for
the optimization problem P2b with C = { via Equation ( This policy TD satisfies pa a 2 pr
To interpret the bounds, let us consider three cases:
R # Å: If the attack indeed poisoned R, then the smallest E (0, such that o # 0 corresponds to et. In this case, it turns out that et =ł, and somewhat surprisingly, the defense policies of (Paa) and (2b) coincide. (Note that this analysis assumes that eD 2 ct.)
R = -R and eD < ē: This corresponds to the case when the attack did not poison R and there is no é' E (0, <D) such that O * 0.. In this case, it turns out that the optimal solution to the optimization problem (P2b) is TD = (indeed it is uniquely optimal under R).
R= and <p 7: This corresponds to the case when the attack did not poison R and there is é (0, (D) such that O' * 0. In fact, é is the smallest such c'. In this case, turns out that, in general, the optimal solution to the optimization problem P2b is TD # Tt, even though क is uniquely optimal under R.
These three cases also showcase the importance of choosing ep that is a good upper bound on Et. When R= R, the agent should select ép that is strictly smaller than 2. On the other hand, when R R, the agent should select eD 2 E, as will be apparent from the result of the next subsection, in particular Theorem 5.3 While the agent knows é, it does not know if R R R R.
5.2.2 Underestimating Attack Parameter
In this subsection, we analyze the case when eD Et. We first state our result, and then discuss its implications.
Theorem 5.3. Ife; e > ED, then TD = ot is the unique solution of the optimization problem C= }
P2b with
Therefore, logether with Theorem 5.2 Theorem 5.3 is showing the importance of having a good prior knowledge about the attack parameter Et. In particular:
When the attack did not poison the reward function (i.e., R= R), overent 6 implies that un might not be equal to गi for larger values of ED, even though is uniquely optimal under R. This can have a detrimental elfect since in this case 7TD < Tt
F = When the attack did poison the reward function R (i.e., R R), underestimating e implics To m,, but Ty might be suboptimal. In this case, the defense policy does not limit the negative influence of the attack at all, i.e. TdP p pp"
We further discuss nuances selecting ep in Section
6 Experimental Evaluation
In this section we evaluate our defense strategy in an experimental setting in order to better understand its efficacy and robustness. We focus on the setting from Section 5.2 attack cost functions, which is known
to the agent, i.e., C = (02), with an unknown attack parameter et-
Given the results in Scction ( with the CVXPY solver Diamond & Boyd (2016); Agrawal et al. (2018) for calculating the solution to the defense optimization problem (P2b In the experiments, due to limited numerical precision, O is calculated
(Thcorems 5.2 and 5.3) we use the lincar programming formulation P3 together
10

---

Published in Transactions on Machine Learning Research (01/2023)
with tolerance parameter, set to 10 by default
In other words, 6 {(s,a) 100 - (sia) -cl -c|5 10 10-
Attack parameter (c.)
0.1 03.3 0.5 0.7 0.9
0.30
Atlack paranetee (e))
0.3 0.5 0.7 0.9
-1.0
0.15
0.00
114
-0.15
-.6
0.1 0.3 0,7
0.9
0.1
0.3 0.5
0.7 0.9
Defense parameter (ep)
Defense parameter (ep)
(a)
(b)
(c)
(d)
Figure 4: Experimental environments: Figures (a) and (b) show the Navigation and Grid world environment respectively while figrues (c) and (d) show pan in these environments. For comparison, in the navigation environment, p" = 00266 and p" 0.45 while in the grid world environment, pF1 1.75 and p" 0.70.
Rg
40.68
Score w.r.t R
Score w.r.t R
Score w.r. R
0.28
Score witt
0.28
-0.94
-0.94
0.10
0.10
-1.20
-1.20
40.88
0.08
-146
-1.46
-0.26
-0.26
-1.72
-1.72
0.0
0.4 Perturbation parameter
0.1
0.2
0.3
0.5
0.0
0.1
0.2
033
0.4
0.5
0.0
0.4 Perturbation parameter
0.1
0.3
0.5
0.0
0.1
0.2
0.3
0.5
Perturbation parameter
Perturbation parameter
(a) Navigation, PreAttack
(b) Navigation, PostAllack
(c) Grid world, PreAttack
(d) Grid world, PostAttack
Figure 5: Robustness of the defense policy against random perturbation. Results are based average of 100 runs for each data point. Error bars around the data points indicate standard error.
Navigation environment. Our first environment, shown in Figure 4 is the Navigation environment laken from Rakhsha et al. (2021). The environment has 9 states and possible actions. The reward function action independent and has the following values: R(so..) .) R(s1. R(s2..) R(s3..) -25, R(s4,-) R(ss,-) 1 and R(ss,-) R(s7,-) R(ss,-) O. When the agent takes action, will successfully navigate in the direction shown by the arrows with probability 0.9; otherwise, the next state will be sampled uniformly at random. The bold arrows in the figure indicate the attacker's target policy. The initial state is so and the discounting factor equals 0.99.
Grid world environment. For our second environment, shown in Figure 4., we use the grid world environment from Ma et al. (2019) with slight modifications in order ensure ergodicity we add a 10% failure probability each action, sampling the next state randomly in case of failure. The environment has 18 states and 4 actions: up, down, right and left. The white, gray and blue cells in the figure represent the states and the black cells represent walls. In the white and gray states, the agent will attempt to go in the direction specified by its action if there is a neighboring state in that direction. If there is no such state, the agent will attempt to stay in its own place. In the blue state G, the agent will attempt to stay in its own place regardless of the action taken. In all states, each attempt will succeed with probability 0.9; with probability 0.1, the next state will be sampled uniformly at random. In the gray and white states, the agent's 's reward is function of the state it is attempting visit. Attempting to visit a gray, white and blue state will yield a reward of 10, -1 and 2 respectively. If the agent is in a blue state, it will always receive reward of 0. The bold arrows in the figure specify the attacker's target policy. The initial state is S and the discounting factor 7 equals 0.9.
Policy score for different values of parameters. We first analyze the score of our defense policy in 4The value chosen because the CVXPY solver uses precision 10
11

---

Published in Transactions on Machine Learning Research (01/2023)
both environments with different values of ef and ép. For comparison, we also report the scores of the target policy (x+) and the optimal policy (œ*). The results are shown in Figures I and Di. As seen in the figures, as long as ep 2 et, our defense policy significantly improves the agent's score compared to ,t. Robustness to perturbations. We now analyze our algorithm's robustness towards uncertainties in the reward functions used by the allacker and the defender. For our first experiment, which we call PreAttack, we randomly perturb the attacker's 's input. In particular, the input to the defender's optimization problem R is sampled from A(c2, R + (0, I2), 6+) where I is the identity matrix, N denotes the multivariate normal distribution and a is the perturbation parameter varied in the experiment. For our second experiment, called Post.Attack, we randomly perturb the reward vector after the attack, sampling the defender's input from A(e,, R2 e1) + (0,0021)) In both experiments we use e, = 0.1 and ép = co. As explained below, when calculating 0; we also experiment with a larger lolerance parameter of 10-1, denoting the defense policy in this case with TD+
The results can be scen Figure 5 As seen in the figures, our defense policy TD consistently improves on the baseline obtained with no defense (i.e, оt). It is also clear that the PostAttack perturbations have a greater negative impact our defense strategy's score. Results for TD+ indicate that this is due to random perturbations prohibiting our algorithm from identifying all of the elements in O While having a higher tolerance parameter helps with robustness, it can also lead to a lower performance when there is no noise because O' would falsely include additional elements. We leave choosing the tolerance parameter in a more systematic way for future work.
7 Concluding Discussions
In this paper, we introduced an optimization framework for designing defense strategies against reward poisoning attacks that change an agent's reward structure in order to steer the agent to adopt a larget policy. We analyzed the utility of using such defense strategies, providing characterization results and provable guarantees on their performance. Moving forward we see several interesting future research directions. Beyond the worst-case utility. In this paper, we defined the defense objective as the maximization of the agent's worst-case utility. While this is sensible objective, there are other objectives that one could analyze. For example, instead of focusing on the absolute performance, one try to optimize performance relative to the target policy. Notice that this is a somewhat different, and possibly weaker goal, given that the target policy can have arbitrarily bad utility under R. Additionally, one could study the agent's 's sub-optimality gap, i.c., the difference between its score and the score of the optimal policy n², and compare it to the sub-optimality gap of the target policy. Going back to the example in Figure 3 we can see that the defense strategy can significantly reduce the suboptimality gap relative not having a defense (in this case, from 10 3 to 10 22/3 x 2.7). However, when the original reward function already forces the target policy, iee, when π = R. the suboptimalitty gap of the target policy is equal to In Figure 3 this happens if the target policy is action a1- Nevertheless, this case, the suboptimality gap of the defense strategy would also be low, equal to 1/2 (since the defense would randomly select d₁ or a7), and generally upper bounded by CD = 2 if the rewards of sub-optimal actions faz,.., 07} were different. Providing full theoretical treatment for the general setting is an interesting research direction.
Informed prior. We did not model prior knowledge that an agent might have about the attacker or the underlying reward function. In practice, the agent may have some information about the underlying true reward function. Incorporating such considerations calls for a Bayesian approach that could improve the agent's 's defense by, e.g., ruling out implausible candidates for R the agent's inference of R given R.
Selecting eD and non-oblivious attacks. The results in Section 5.2 indicate that choosing good eD is important for having a functional defense. In practice, selection procedure for ep should take into account the cost that the attacker has for different choices of et, well as ghme-the considerations: attacks might not be oblivious in that the strategy for selecting C might depend on the strategy for selecting cp. Namely, a direct consequence of Theorem 5.2 is that the atlack optimization problem (PI) can successfully achieve its goal if it chooses a large value of et to large enough values. However, the cost of the attack also
grows with 4, so the attack (if strategic) also needs to reason about cD when selecting 6.. We leave the full game-theoretic characterization of the parameter selection problem for the future work.
Unknown- and scalability. Following prior work, we focused on attacks and defenses that have
12

---

Published in Transactions on Machine Learning Research (01/2023)
access to accurate transition model and operate in tabular settings. Given Theorems 5.1 the defense problem can be solved using the linear program optimization problem (PT). As such, we expect our method to be computationally scalable as long as the attack optimization problem can be solved.
5.2 and 5.3
PP3. which is similar in size to the attack
For many RL problems however, the Iransition and reward functions are not known and the MDP is too large be modeled in tabular settings. RL solutions for such problems typically rely on function approximation. For future work, it would be interesting to study the problem, for both attack and defense, in this more realistic scenario. An immediate question is how the attack problem would need to change in order to generalise to this setting. In terms of defense, while the new setting would likely pose new challenges, we expect the general min-max formulation in Section ] as well as the techniques used for solving the oplimization problems
P2a and P2b to remain useful.
Acknowledgments
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions. This research was, in part, funded by the Deutsche Forschugggemeinschatt (DFG, German Research Foundation) project number 467367360.
References
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Idan Amir, Idan Attias, Tomer Koren, Roi Livni, and Yishay Mansour. Prediction with corrupted expert advice. CoRR, hos/2200.110285 2020.
J Andrew Bagnell, Andrew Y Ng, and Jeff G Schneider. Solving uncertain markov decision processes. Technical report, Carnegie Mellon University, 2001.
Kiarash Banihashem, Adish Singla, Jiarui Gan, and Goran Radanovic. Admissible policy teaching through reward design. CoRR, abs/2201.02/1 1.215,, 2022.
Vahid Behzadan and Arslan Munir. Whatever does not kill deep reinforcement learning, makes it stronger. CoRR,
2017.
Dimitri P Bertsckas. Control of uncertain systems with a set-membership description of the uncertainty. PhD thesis, Massachusells Institule of Technology, 1971.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Pottern Recognition, 84:317 331, 2018
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In ICML, 2012.
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. CoRR, abs/ /2000.00008885 2020.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In STOC, pp. 47-60, 2017.
Gabriela Cretu, Angelos Stavrou, Michael Locasto, Salvatore Stolfo, and Angelos D Keromytis. Casting out demons: Sanitizing training data for anomaly sensors. In IEEE Symposium on Security and Privacy, pp. 81-95. IEEE, 2008.
Ilas Diakonikolas, Gantam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In ICML, pp.
2019.
13

---

Published in Transactions on Machine Learning Research (01/2023)
Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. The Journal of Machine Learning Reseorch, 17(1):2909-299) 2913, 2016.
Christos Dimitrakakis, David C Parkes, Goran Radanovic, and Paul Tylkin. Multi-view decision processes: The helper-ai problem. In NewrIPS, pp. 5443 5452, 2017.
European Commission. Ethics Guidelines for Trustworthy Artificial Intelligence. URL: https://ec..e. europa 2019. [Online; accessed
http:///.....tttei//ee////aeaaaa 15-Jamuary20211)
Ahana Ghosh, Sebastian Tschiatschek, Hamed Mahdavi, and Adish Singla. Towards deployment of robust cooperative ai agents: An algorithmic framework for learning adaptive policies. In AAMAS, pp. 447-455, 2020.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In COLT, pp. 1562-1578. 2019.
Ronan Hamon, Henrik Junklewitz, and Ignacio Sanchez. Robustness and explainability of artificial intelligence. Publications Office of the European Union, 2020.
Ling Huang, Anthony Joseph, Blaine Nelson, Benjarni IP Rubinstein, and J Doug Tygar. Adversarial machine learning. In ACM workshop on Security and artificial intelligence, pp. 43 43-58, 2011.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Picter Abbeel. Adversarial attacks on neural network policies. CoRR, abs/1702.02284,, 2017.
Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipulations on cost. signals. In GameSec, pp. 217-237, 2019.
Garud N Iyengar. Robust dynamic programming, Mathematics of Operations Research, 30(2):257-28)) 2005.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Xiaojin Zhu. Adversarial attacks stochastic bandits. In NewrIPS, pp.
2018.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via inffuence functions. In ICML, pp. 1885-1894. PMLR, 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. CoRR, abs/ Abs/1811.0077/) 2018.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy smoothing for provably robust reinforcement learning. arXio preprint arXiv:21 11420, 2021.
Bo Li, Yining Wang, Aarti Singh, and Yevgenly Vorobeychík. Data poisoning attacks on factorization-baser collaborative filtering. In NeurIPS, pp. 1885-1893, 2016.
Shiau Hong Lim, Huan Xu, and Shie Mannor. Reinforcement learning in robust markov decision processes. Tn NeurIPS, pp. 701-709, 2013.
Yen-Chen Lin, Zhang-Was Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactios of adversarial attack on deep reinforcement learning agents. In IJCAI, pp. 3756-33663003 3762, 2017.
Fang Liu and Ness B. Shroff. Data poisoning attacks on stochastic bandits. In ICML, pp. 4042-4050, 2019.
Guanlin Liu and Lifeng Lai. Provably efficient black-box action poisoning attacks against reinforcement learning. Advances in Newral Information Processing Systems, 34, 2021.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In STOC, pp.
2018.
Thodoris Lykouris, Max Simchowitz, Alcksandrs Slivkins, and Wen Sun. Corruption robust exploration in episodic reinforcement learning. CoRR, abs/1911 1006199,68,, 2019.
14

---

Published in Transactions on Machine Learning Research (01/2023)
Yuzhe Ma, Kwang-Sung Jun, Lihong Li, and Xiaojin Zhu. Data poisoning attacks in contextual bandits. In GameSec, pp. 186-204, 2018.
Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. In NewrIPS, pp. 14543-14555, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
H. Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In ICML, pp. 536 543, 2003.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. Tn AAAT, pp. 1971-2877, 2015.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In CVPR, pp. 2574-2582, 2016.
Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles A Sutton, Doug Tygar, and Kai Xia. Exploiting machine learning to subvert your spam filter. LEET, 8:1 9, 2008.
Auh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In CVPR, pp. 427-436, 2015.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780 798, 2005.
Andrea Paudice, Luis Muñoz-González, Andras Gyorgy, and Emil C Lupu. Detection of adversarial training examples in poisoning attacks through anomaly detection. CoRR, abs/1802.030/// 2018.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In ICML, pp. 2817-2826, 2826, 2017.
Martin L. Puterman. Markov Decision Processes: Discrele Stochastic Dynamic Programmingg John Wiley & Sons, Inc., 1994.
Goran Radanovic, Rati Devidze, David Parkes, and Adish Singla. Learning to collaborate in markov decision processes. In ICML, pp. 5261-5270, 2019.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning. In ICML, 2020.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy tcaching in reinforce- ment learning via environment poisoning atlacks. Journal of Machine Learning Research, 22(210):1 45, 2021.
Anshuka Rangi, Haifeng Xu, Long Tran-Thanh, and Massimo Franceschetti. Understanding the limits of poisoning attacks in episodic reinforcement learning. arXio preprint arX66:2208.13663, 2022.
Kevin Regan and Craig Boutilier. Robust policy computation in reward-uncortain mdps using nondominated policies. In AAAI, volume 24, 2010.
Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. In NewrIPS, pp. 3520 3532, 2017.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability-wware poisoning mechanism for online rl with unknown dynamics. In International Conference on Learning Representations, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
15

---

Published in Transactions on Machine Learning Research (01/2023)
Umar Syed, Michael Bowling, and Robert E Schapire. Apprenticeship learning using linear programming. In ICML, pp. 1032-1039, 2008.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Csaba Szepesvári. The asymptolic convergence-rate of q-learning. In NewrIPS, volume 10, pp. 1064 1070, 1997.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. ICML, pp. 181 189, 2014.
Edgar Tretschk, Seong Joon Oh, and Mario Fritz. Sequential attacks on agents for long-term adversarial goals. CoRR, abs/1805.1248) 12487, 2018.
Fan Wu, Linyi Li, Chejian Xu, Huan Zhang, Bhavya Kailkhura, Krishnaram Kenthapadi, Ding Zhao, and Bo Li. Copa: Certifying robust policies for offline reinforcement learning against poisoning attacks. arv preprint ar vrXim:2203.08839 2022.
Han Xiao, Huang Xiao, and Claudia Eckert. Adversarial label flips attack on support vector machines. In ECAI, pp. 870-875, 2012.
Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? In ICML, pp. 1689 1698, 2015.
Haoqi Zhang and David C. Parkes, Value-based policy teaching with active indirect elicitation. In AAAI, 2008.
Huan Zhang, Hongge Chen, Chaowci Xiao, Bo Li, Duane Boning, and Cho-Jui Hsich. Robust deep reinforcement learning against adversarial perturbations on observations. CoRR, abs/2003.08933, 2020a.
Xuezhou Zhang, Xiaojin Zhu, and Stephen Wright. Training set debugging using trusted items. In AAAT, volume 32, 2018.
Xuczhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcement learning. In ICML, 2020b.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. CoRR, abs/2102.05800, 2021.
A List of Appendices
In this section we provide a brief description of the content provided in the appendices of the paper.
Appendix B provides intuition of our results for the la attack cost using special MDPs in which the agent's actions do not affect the transition dynamics. The proofs of the results presented in this Appendix can be found in Appendix T
Appendix provides additional details regarding the experiments.
Appendix contains some background reward poisoning attacks, and brief overview of the MDP properties that are important for proving our formal results.
Appendix contains characterization results for the attack optimization problem P1
Appendix contains proofs of the formal results in Section 5
The proof of Theorem 5.1 is in Section
The proof of Theorem
5.2 is in Section
The proof of Theorem
5.3 is in Section
16

---

Published in Transactions on Machine Learning Research (01/2023)
Appendix G contains the proofs for the results in Section relating to Guarantecs values. The appendix also includes an optimization framework for solving the defense optimization problem (P2a) for the 4
norm as well as additional characterization results for the defense optimization problem for more general cost functions which are used for proving the complexity results in Section
The characterization result for the defense optimization problem with for the l norm is provided in
Section C.
Proof of Theorem
4.4 is provided in Section G.2
Additional characterization results for the defense optimization problem are provided in Section
Proof of Proposition
4.2 is provided in Section G.4
Proof of Theorem is provided in Section G.5
Appendix H contains the proofs of the formal results in Section !
relating the computational complexity of the defense optimization problem as well as the computational complexity result for the lo attack cost.
The hardness result for the loo norm is provided in Section
H.1
Proof of Theorem
4.5 is provided in Section H.2
Appendix
!
contains a formal treatment of the results presented in Appendix
B Intuition of Results using Special MDPs
In this Appendix, describe characterization results the le attack cost for special MDPs, in which the agent's 's actions do not alfect the transitions, that is, we assume that
P(s, a, s') o's.d',s') Vs, as,a,a',s'.
(3)
Variants the above condition have been studiod the literature (e.g.. Szopesvári (997]); Dimitrakakis et al. (2017); Sutton Barto (2018); Radanovic et al. (2019); Ghosh el al. (2020)) Note that this assumption implies that any two policies ı and n' have equal state occupancy measures, so we simplify the notation by denoting μ = y("
While the results from the previous sections incorporate this special case, we study this setting because: the optimal solutions to the defense problem have simple form, enabling us to provide intuitive explanations of our main results from the previous sections, ii) using this setting, we show tightness result for Theorem 5.2
A more formal exposition of our results for this setting inlcuding the proofs can be found in Appendix
B.1 Optimal Defense Policy
In this subsection, we provide the intuition behind defense policies for the unknown parameter setting with 6p 2 6 (Section 5.2.1p. The key point about the assumption in Equation (3) is that allows us consider each state separately in the defense optimization problems. In particular, can be shown that the optimization problem P3 equivalent to solving [S] optimization problems of the form
max <(1+)) E P(A) [[{]s),,(ss)))
(P3b)
<als)) 2 (T)
Va E E
where =
{a: M((s,a) R(s (x())) = - أ|م If we instantiale Theorem 5.2 for special MDPs by putting
= minfep. 2), the set O has an intuitive description: it is the set of all "second-best" actions (w.r.t R) in state such that their poisoned reward is greater than equal to R(T; p(a)- It turns out that the defense policy for state selects an action uniformly at random from the set O U (m{(s)) In other words,
the defense policy ap is given by:
if E (
(a(s)) =
To +T
otherwise
Seee Lemma 8 in Ranihashem al. 2022
17

---

Published in Transactions on Machine Learning Research (01/2023)
To see why, note that the objective in (Pbb only improves as put more probability on selecting (s) (since "y (8) is optimal under R). However, the constraints (3b) require that the selection probability of any action in e has to be at least as high as the selection probability of T (s), which in turn give us the uniform at random selection rule. Figure g illustrates attack and defense policies for special MDPs using single-state MDP with action set {a1,...a7} To obtain defense policy TD,
solve the optimization problem (P3b) which implics that Tp should select an action uniformly at random from the set (s)( U = {ai, 0s,
C Additional Details Regarding Experiments
In this section provide additional details regarding the experiments. The source code for experiments, as well as instructions for replicating our results can be found in the Supplementary Material.
C.1 Implementation details
Both the attacker optimization problem P1]. and the defense optimization problems P2a and (2b are convex since, by Theorems 5.1 and 5.2 the defense optimization problem reduces to the linear program (P3
We use CVXPY to calculate their solutions. The code for solving these optimization problems can be found in the file MDP py. The specific functions used for solving these problems are as follows:
The function attack implements the attacker's optimization problem P1
As explained in the main text,
this is done by solving (P1) since (P1') is equivalent to (P1)
The function defend_ known implements the optimization problem
P2a
As explained in Section 6 the
tolerance parameter is set to 10-4 (default value).
The function def end unknown implements the optimization problem P2b
C.2 Running time
Following prior work Rakhsha et al. (2021), to test the rumning times, use the chain environment from Rakhsha et al. (2021), but with different number of states (additional states are added between 82 and 83, and the corresponding transitions and rewards are defined analogously to those for s2). The attack and defense parameters are set to 4 = 0.1 and cp = 0.2. Table 2 shows the average running times (across 10 runs) the attack optimization problem PT and the defense optimization problem P2b for different sizes
of the chain environment.
It should be noted that the attack and defense optimization problems similar in size, both solve a problem with at most [S| (IA) - 1) constraints |ISIAAI,, However, solving the defense problem takes more time, partly because ,F, ? and O need to be identified before P3 can be solved.
The machine used for obtaining these results is a Macbook Pro personal computer with 4 Gigabytes of memory and a 2.4 GHz Intel Core i5 processor.
D Background and Additional MDP Properties
In this section we briefly outline the background and MDP properties that we utilize in our proofs.
D.1 Reward Poisoning Attacks
In this section, we provide some background on the cost-efficient reward poisoning attacks, focusing on the results from Rakhsha et al. 2021
The setting studied in Rakhsha et al. 2021 incorporates both the average and the discounted reward optimality criteria in discreto-time Markov Decision Process (MDP), with finite state and action spaces. Our MDP setting is equivalent their MDP setting under the discounted reward optimality criteria. This criteria be specified by score p. As defined in the main text, score p" of policy is the total expected
18

---

Published in Transactions on Machine Learning Research (01/2023)
Problem
Attack
Defense
0.01s 0.5ms
0.05s + 1.6ms
0.01s 0.2ms
0.09s + 1.5ms
20
0.01s 0. m.1ms
0.17s + 4.8ms
30
0.02s + 2.0ms
0.27s + 9.7ms
50
0.04s + 6.8ms
0.56s + 34.6ms
70
0.07s + 3.0ms
1.02s + 69.7ms
100
0.13s + 5.4ms
1.83s + 91.2ms
Table 2: Run time of the attack and defense optimization problems for the chain environment with varied number of states |S]. Reported numbers are averago of 10 runs; standard error is shown with +.
return scaled by factor 1 7
p" E
R(st, a
t=1
where the state 81 is sampled from the initial state distribution a, and subsoquent states 8t are obtained by executing policy ı in the MDP. Actions aj are sampled from policy n.
As explained in the main text, the following result is important for our analysis, since it allows us to simplify the optimization problem (P1) into the optimization problem (PT).
Lemma D.1. (Lemma in Rakhsha et al. (2021)) The score of policy गi is at least e greater than all other deterministic policies if and only if ils score is at least greater than the score of any policy ग. (t; In other words,
VT E II (T pT 2 p" +
( nt (sia) + e;)
Remark D.2. As explained in Rakhsha al. 2021 this lemma implies that the optimization problem P1 is equivalent to (P1). Furthermore, the optimization problem is always fcasible since any policy can be made optimal with sufficient perturbation of the reward function as formally shown by Rakhsha et al. (2021) and Ma et al. 2019))
D.2 Overview of Important Quantities
Next, provide overview of standard MDP quantities and the quantities introduced in the main text that are important for our analysis.
In addition to score P, we consider state-action value function, or Q-value function, defined as
(*(s,a) E
R(st,a)))s) 8,01 0.
In other words, Q=(ssa) is the total expected return when the first state is s, the first action is a, while subsequent states and actions are obtained by executing policy и in the MDP.
We consider two occupancy measures. By th" we denote the state-action occupancy measure the Markov chain induced by policy n:
3d (s. 0) =B (1 7)
1-1 [st s. = T.
1=1
19

---

Published in Transactions on Machine Learning Research (01/2023)
Given MDP M, the set of realizable occupancy measures under any (stochastic) policy x E II is denoted by V. Note that the following holds:
(16", R)
(4)
where (.,.) in the above equation computes a dot product between two vectors size |5| (i.c., two vectors in IR: (1))). We also denote by n² the state occupancy measure in the Markov chain induced policy л E IT, i.e.:
1 (s) E
(1
-
7) Σ [s: =s]
1
1=1
Note that
av) [s)(s) =1
State-action occupancy measure and state occupancy measure satisfy
(s, (())))
(5)
which for deterministic ı is equivalent to
t (s, a) = ( = a] (s))
(6)
Apart from the standard MDP quantities mentioned above, also mention quantities introduced in the main text. We denote by O stale-action pairs (8,a) for which the margin between fa1 and fot (raaaa is equal to e, i.e.
e = (s. p=itssa) (s:a) p -c)
(7)
which can be expressed through reward function R using state-action occupancy measures 1/:
e = (s. (weilem)) 36 R = =
Finally, quantity [s:e] (T) measures how well the occupancy measure of is aligned with ef (s:a) relative to 1t:
((aa) = (ooti - -/ 2b/²))
(8)
D.3 Occupancy Measures as Linear Constraints
In this subsection, we introduce the Bellman flow linear constraints that characterize tt and μ², In order to characterize o² we require the following constraints:
((ss,a) = (1 7))(s) Σ 7.
(9)
V(s,a) (s) 2 0.
(10)
The importance of these constraints reflected in the following lemma.
Lemma D.3. (Theorem in Syed et al. 2008)) Let be vector that satisfies the Bellman flow constraints
and 10 Define policy
(s)
[(lss) E. (ss
(11)
Then 1) the state-action occupancy measure of n, in other words si v² Conversely, if E is policy with state-action occupancy measure (i.e, 1 = )² then i satisfies the Bellman flow constroints and 100, as well Equation 11
20

---

Published in Transactions on Machine Learning Research (01/2023)
As for μ², it is well-known (e.g., see Rakhsha et al. (2021) for policy æ (ie.., = if and only if
that vector j is the state occupancy measure
p(s) = (1 - ()-() + Σ
(12)
8,0
E
Attack Characterization Results
E.1
Characterization results for the & attack cost
In this section we provide characterization results for the attack optimization problem P1 for the E norm, i.e, C= (c2}- We will later use these results for proving the formal results presented in Section 5.1 and Section 5.2 addition, these results provide intuition for our results about the more general lp norms which we will discuss in the next sections. In particular, the main result of this appendix is a set of Karush MharuhhKuuhn-- Kuln-Kunnnn------nnnnn Tucker (KKT) conditions that characterize the solution to the optimization problem (P1). As focus the cost. function C2 in this section, will drop the dependence
in A(c, R, -t)
To compactly express the KKT characterization results, let introduce state occupancy difference matrix + E |((|((11--1))) as a matrix with rows consisting of the vectors 2h )) - の for all neighboring policies Ti a). Additionally, for all 8, a # (s), we use ((s, a) to denote the transposc the row of & corresponding to (s, Note that ((s, a) is a column vector. In this notation, given Remark D.2 and Equation the optimization problem is equivalent to
min R 2
R - R''12
(P1")
s.t.
+ R 64
where 1 is [S]. (1A]-1) vector whose each element equal to 1, and specifies that the left hand side is element-wise less than equal to the right hand side. Given this notation, the following lemma states the KKT conditions for reward function R (i.e., an |S|- |A] vector) to be an optimal solution to the optimization problem PP1)
Lemma E.1. (KKT characterization) R is solution to the optimization problem
P1
if and only if there
erists an |S] |A| vector À such that
(R RR-R)- T A
stationarity, primal fcasibility, \
R R
dual feasibility,
Vis a + (s)) A(s,a) a) R R = complementary slackness,
where denoles an |S| |A| veclor whose each element equal to 0, and likewise, 1 denotes an [S] |A] whose each element equal to
vector
Proof. Since P1 is always feasible (Remark D.2 and all of the constrains are linear, strong duality holds. Now, the Lagrangian of the optimization problem is equal to
C -= R + R+4.1).
and taking the gradient with respect to R gives us
VRC=(R-R)) T
The statement. then follows by applying the standard KKT conditions.
Remark E.2, (Uniqueness) The solution to the optimization problem P1 is unique since the objective
R - R'B is strongly convex.
21

---

Published in Transactions on Machine Learning Research (01/2023)
The above lemma, has the following important consequence.
Lemma E.3. Reword function R satisfies R = A(R, () if and only if there crists some ds such that
R R+
Σ
(werienut - 15 )
Ossaa
(a,0)E9t
Proof. To prove the statement, use Lemma E.1
The primal leasibility condition in the lemma al ways
holds R E A(R, (1,,)) Therefore R E A(R, ET) if and only if there exists À such that the other three conditions hold. Note that the complementary slackness condition is equivalent to
V(s,a a + T+(6)) A(s, a) 0V OV o(s,a)" ++ =0 > V(s,a) & 6 (s,a) =. 0.
Therefore from dual feasibility, stationarity and complemantary slackness it follows that n E A(R, at, if and only if there exists À such that
A x 0,
R = R+ Σ A(s,a) (15=((800] (0.0)
((s a) $ 0t a) =0
The Lemma therefore follows by setting a,,a = A(s, a) since setting A(s, a) = for all (s,a) & O is equivalent to not summing over the terms corresponding to (s, & 0ct the stationarity condition.
A direct consequence of this lemma is the following result. Corollary E.4. Assume that R A(R, T+,ET) Et) and Ri + R. It follows that
ct
where
1 (
min s
Proof. Assume to the contrary that ē + 6s. Given the primal feasibility condition in Lemma E.1 Therefore ē e+. It follows that
2 Et-
Vs,a TT (8) pat (mta)
Given Lemma E.3 this implies that R R, which contradicts the initial assumption R + R.
F Proofs of Section 5.1
This section of the appendix contains the proofs of the formal results presented in Section
F.1 Proof of Theorem
Before proving the theorem we prove some results that we need for the proof of this theorem, as well for the results in later sections.
Lemma F.I. Consider policy with state-action occupancy measure s² Solution Piin to the following optimization problem:
min p= R
s.t. R= A(R, T+,
(P4)
22

---

Published in Transactions on Machine Learning Research (01/2023)
satisfies:
if Vs [(saa (T) 2
Pmin
-00
otherwise
Proof. We separately analyze the two cases: the case when (T)) 2 0 for all (s, a) E e holds, and the case when it does not.
Case 1: If [+ta) (T) 2 0 for all (s,a) 1 then by using Equation and Lemma E.3 we obtain that
p² p 15t R) =
Σ
asa (wT (f w 2 0.
(s.0)E6%
Therefore, p" p Furthermore, from Lemma E.3 we know that R R satisfies the constraint in the optimization problem
P4 so the score of the optimal solution to [44h Plain - -
Case 2: Now, consider the case when [(ssa)
0 for certain state-action pair (s, a) E e Let asaa be
arbitrary positive number. From Lemma
E.3 we know that
(1"', ( 26
R = R + 0ss0
satisfies the constraint in the optimization problem this solution together with Equation
P4 and hence is solution to P4 Moreover, by using
(4) we obtain
R asa (BT, wbtrlsrn) vb " ) asea [(taa] (T).
p"
R
(13)
Since as,a can be arbitrarily large and ((=:a) (r) < O, while p is fixed, px can be arbitrarily small. Hence, the score of the optimal solution to P4] is unbounded from below, ie., Pmin = -00.
We can now prove Theorem 5.1 that is the following statement.
Statement: Consider the following optimization problem parameterized by e:
max
tb, Rt
(P3)
NEW
s.l. (15 - 20 Vs,aE0'.
For =- ct, this optimization problem is always feasible, and its optimal solution tmmax specifies an optimal solution the optimázation problem P2a) with
(imax(8,0)
TD(aas) = Enr Um ())
(14)
The score of TT (a)ss) is lower bownded by Td 2 prd
Proof. The feasibility of the problem follows from Theorem 4.4
Note that Vmmax always exists since
P3 is maximizing a continuous function over closed and bounded set. Concretely, the constraints
6 [=:a] -,, (,,,t) 2 0 and Equations 9 and [10 each define closed sets, and since ||61] = 1, the set W is
bounded.
In order to see why vmaa specifies an optimal solution P2a note that we can rewrite P2al as
max P
6Te proof of Theorem 4.4 does rely this result.
23

---

Published in Transactions on Machine Learning Research (01/2023)
where Pmni is the solution to the optimization problem P4 Due to Lemma F.1 this could be rewritten
max P
s.L. (s:a] (T) 2 0 v(s,a) E @
Namely, maximizing a function f(x) subject to constraint X' (where X' o 0) is equivalent maximizing [()), where
[(x) if TE X
[(x)
-00 O.W.
Due to and 8), the constrained optimization problem above can be rewritten as
max p3 R
s.t. (wirtosos) , 204)) V(s, a) E e
Therefore, given Lemma D.3 mmax specifics a solution to P2a via
Finally, note that the constraints of the optimization problem measure is equal to vlmax will have [(ssa( (x) 2 in other words, risa) is non-negative for all
P3 ensure that a policy æ whose occupancy
(s,a) 0ct, Due to Lemma F.1 we know that such policy ı will have the worst utility equal p Therefore, p" p
Remark F.2. Given Lemma D.3 the constraint và E v can equivalently be replaced with constraints (9) and 10). making the optimization problem P3 linear program.
F.2 Proof of Theorem 5.2
The proof of the theorem similar to the proof of Theorem 5.1 and builds on two lemmas which we introduce in this section.
Lemma F.3. Set = min(ep, E, where
== min (.
Reward function R satisfies R. = A(R, TT. E) for some E (0,eD) if any only if
R R+
Σ
asaa
(15t)(au)) - (5))))
(s,0)E0r
for some Ossa 2 0.
Proof. We divide the proof into two parts, respectively proving the sufficiency and the necessity of the condition.
Part (Necessily): Assume that R A(R, 7) for some E (0, From the stationariry and dual feasibility conditions in Lemma E. deduce
YE 0 R R
Σ (,()
X(s,a): (107))00)) - *)
(15)
We claim that X(s, a) for all as & O Note that this would imply the lemma's statement by setting Oss X(s,a) since the terms corresponding to (s, a) & O could be skipped in the summation of 15
24

---

Published in Transactions on Machine Learning Research (01/2023)
To why the claim holds, assume that A(s, a) # 0 for some (s, a) where + (5) From complementary slackness, we know that (ss a)² R + ē = 0, which implies that
(33 R) - (s, R- 8,
min
(16)
However, S é holds by primal feasibility. Therefore, all the inequalities are equalities, which implies = Since ? S CD, we conclude that min (in, = c. Since all of the inequalities (16) are indeed equalities, conclude
((s,a)² R = = (s, e e
which proves the claim.
Part 2 (Sufficiency): Assume that
R R
Σ asia
(wri(sta) -5
(s,a)EEr
for some Oss.a 2 0. Set ? = and note that ē S cD by definition. Set
a(s Sana if (s,a) e O
00 o.w.
We now verify all the conditions of Lemma hold. Stationarity and dual feasibility hold because R R + Σ., X(s,a) (ss, a) and À 0. Primal feasibility holds because min(eD, 2) s E. Finally,
complementary slackness holds because
X(s,a) #0 = -ssa)E e ((s,a)
Lemma F.4. Let Pmin be the solution to the following oplimization problem
min p sdl. Ri A(
(P5)
Then
pT if V(s,a) 0e p(saa 2
Pmnn
-00
0.w0
where min(ep, E}, and
T f [s:0]
== min
5,09/)) (8)
We separately analyze the two cases: the case when P(eaa] (π)) for all (s,a) a) E Or holds, and the case when it does not.
Proof. The proof is similar to the proof of Lemmal F.
Case 1: If [(aaa (7) 2 0 for all (s,a) 00, then by using Equation and Lemma F.3 obtain that
p pm
2 R R.)
Σ
assa (wT, (f 36 2 0.
(s.a)eer
Therefore, p" pT. Furthermore, from Lemma we know that R R satisfies the constraint in the optimization problem (P5), so the score of the optimal solution to (P5) Piin p²
25

---

Published in Transactions on Machine Learning Research (01/2023)
Case 2: Now, consider the case when [(saa (x) < 0 for certain state-action pair (s, E Gr. Let asaa be arbitrary positive number. From Lemma F.3. we know that
(0 ( 1/71
R= R Uss,a
satisfies the constraint in the optimization problem this solution together with Equation we obtaín
P5p. and hence solution to (P5 Moreover, by using
p²
p"
16 R R asaa (W0 spattan
1p9ht) - axsa [(saa)
Since Osso can be arbitrarily large and [(aa)) < O, while X" is fixed, p" can be arbitrarily small. Hence, the score of the optimal solution to [55) unbounded from below, i.e, Pinin = -00.
We are now ready to prove Theorem 5.2
Statement: Assume that ep 2 et, and define ming [ - -pr(ssa]]] Then, the optimization problem P3 with e = min (cp { is feasible and its optimal solution Vmax identifies an optimal policy wp for This policy TD satisfies pTD 2 p
the optimization problem P2b via Equation
Proof. The proof is divide into two parts, respectively proving the first and the second claim in the theorem statement.
P3 is feasible, its optinal solution Part (Solution to P2b We prove that the optimization problem
mmax identifies an optimal solution to P2b via. Equation (2) and satisfies p= pTD.
The fcasibility of the problem follows from Theorem 4.4 Note that e'max always exists since
P3 is maximizing
continuous function over a closed and bounded set. Concretely, the constraints (11** (+;a]
0 and
Equations and 10) each define closed sets and since ||/]]/ = 1, the set is bounded.
In order see why mmaa specifies an optimal solution
P2b note that we can rewrite P2b
max P
where Pmin the solution the optimization problem P5 Due Lemma F.4 this could be rewritten
max P
s.l. p(sal (T) (T) 20 ((s,a)
where = min(< Namely, maximizing function f(x subject to constraint x E & (where X + 0) is equivalent to maximizing f(x), where
f(z) if TEX
f(x)
-00 O.W.
Due to and 8 the constrained optimization problem above can be rewrillen as
max pm
R
(1preeoudd- 1/ 13"") V(s O
s.t.
Therefore, given Lemma D.3
vmmax specifies a solution to P2b via 2 satisfics the constraints of P5 and therefore TTD is a lower bound on p pm
Finally, given Lemma F.4
26

---

Published in Transactions on Machine Learning Research (01/2023)
F.3 Proof of Theorem 5.3
Statement: ef > eD, then ny is the unique solution of the oplimization problem P2b
hence -t.
Proof. As in Theorem 5.2 set = min(E,ep)) where
1ott (xsaa
== min (x)
From the feasibility of the attack, we have that
Vs, + (3) p01 (x()) 2 + 2E
2E
O 0.
Therefore, given Lemma F.3 the constraint the optimization problem P2b satisfied only for R = R.
This reduces the optimization problem
[2b to max, p*, which has a unique optimal solution: Tt.
G Proofs of Section
In this section, we provide the proofs of the results of Soction as well additional results that characterize the defense optimization problem. While our results are stated for the defense optimization problem (P2a) all results hold for (Pbb well with min(ep.e).
G.1 Solution to the defense optimization problem for the & attack cost
In this section, we present convex optimization framework for solving the defense optimization problem P2al for C = {cr}. Our main result is the following theorem, the proof of which is presented in Section G.3 Theorem G.1. Let & [(SH(1)) be matric with
consisting of the vectors Th क
in Section b and let da be the sub-malris of & consisting of the rows corresponding to Ost. Define the set U C S x A as the set of state action pairs (3, ū) for which the following optimization problem is feasible.
V a: (o) (s, a)) & and (B, = -1 and + 0.
where > denotes coordinate- wise inequality. Consider the following optimization problem:
max p R s.t. <(cls) =0 Vs
(17)
The optimization problem 17 is always feasible and its solution is a solution to the defense optimization problem
P2a with C = }
G.2 Proof of Theorem 4.4
Statement: Consider any policy गे s.t. Tz, T,, (1))))))) = 0. For C = {cp s.f. p E (1)), the optimal value of problem P2a is bounded from below by p
Proof. We claim that R(s < R(s, a) for all R satisfying Re A(R) and all s, + (s). To see why, assume that if this not the case for some 8, à and define R as
[[ss,a) if = R(s,a) o.w.
R(s.a)
It is clear that R - R p
< R R for all E [1, oo). We claim that R is feasible for the attack optimization
problem P1 with parameters Cp, R, C.. This would contradict the assumption, Å A(R) as it would mean R is not an optimal solution to PI), finishing the proof.
7The results related computational hardness discussed separately Appendix H
27

---

Published in Transactions on Machine Learning Research (01/2023)
To prove the claim, since P1 is equivalent to P1 we need to show that
Ba (s:)) Bitt S -c:
for all š, # (5). By definition of R however, R. (#:0) p R.,, (8:ā) =
p (3,()
- (R- B
R, 2o (&rā) O,
(18)
where the first equality follows from Equation 4 and the second equality follows from the fact that R only differs from R in (s, a), s) g a) = O. Simliarly pR.a 2 p R, as
p p -p [... - (R (R- R. v0 0,
where the second inequality follows from the fact that R is never less than R. Therefore,
(1:)) p R S ( B. S Eto
where the second inequality follows from the assumption that R E A().. We haver therefore shown finishing the proof.
18
G.3
Characterization of the inner minimization problem in P2a
We begin by providing characterisation results for the inner minimization problem in (Paa for different. known cost functions. These rosults can be seen extensions of Lemma F1 Formally, for fixed p, consider the following optimization problem
min p s.t. R A R. R9
(P4)
The following lemmas characterize the value of the above optimization problem for different values of p- In stating these lemmas, we use E [R) be a matrix with rows consisting of the vectors (=+((=)) =t as in Section and let 4a be the sub-matrix of & consisting of the rows corresponding to O Lemma G.2. Let x be fized policy and assume that 1 < p < oo fized number. Define the function up R + R as up(x)= = sgn(x)) |xx|=- where sgn(x) = [a > 0] 1 [x 0] and let up R" - R" be its coordinate-uiss extension to R.,, i.e, (x)) = (p()))
The solution to P4 equals pm is
(v up {1) 4
and equals -0 otherwise.
Lemma G.3. Let π be a fized policy. Define the function tho R + R
as
(x) [-1 if x
O.W.
and let uhe IR + R be its coordinate-uiise extension to Ra, Le, (x) -100(x)) The solution to equals pT if
P4
(11 , Usx ( (A))
Ax s.t. X#
and equals -0 otherwise.
Lemma G.4. Let π be a fized policy and let C S x be the set of state action pairs (3, for which the following optimization problem feasible.
Vs, a: : (ΦT X) (s, a)l < 1 and ( a) = -1 and X x 0.
(19)
Then the solution to P4 is
if म (Q for some 8, ā U and is 7nr otherwise.
28

---

Published in Transactions on Machine Learning Research (01/2023)
When it is clear from context, we will drop the dependence on p in Up. The proof of Lemmas G.2 and G.4 are provided below. Note that Lemma G.4 immediately implies Theorem G.1 since the leasibility of 17 already follows from Theorem 1.4
Proof of Lemma 2. Throughout the proof, we will drop the dependence on Cp. and in A. The proof follows a similar structure as the results for the lz norm; namely, Lemmas E.1 E.3 and
We begin by analyzing the constraint A(R) = R using the KKT conditions. Since 1 < p < ou, we can change
the objective to || R for convenience. Of the four KKT conditions, primal feasiblity holds if and only if " o -c. For the stationarity condition, forming the lagrangian of P1
obtain
|
R-R
R
a) Σ (R(s, R(s + -
p
Taking the gradient,
VnC = = sgn(R(ss R(s,a)) R(s, a) R(s, a) +
( (s,a)= =0 as,a
(DTA) (5,a) = sgn (s,a)) R(s,a)) [R(s,a) a(s,a))² Vs,a
( (8, a) - sgn (Φ (s, a)) R(s,a) - R(s,a) 48,a
u( A) R R
where for (i) we have used the definition of u. the complementary slackness condition states that a(s,a) = 0 V(s,a) & 09.
Finally, dual feasible states that À >= 0.
Returning the condition A(R) R, primal feasibility always holds as R= A(R). We therefore conclude that vector satisfies A(I)) = At if and only if the following problem is feasible
R = N + u (
A A
X(s, a) V(s,a) t
By definition of Pg. this means that
A(R) - + R = R ul (
for some A 0.
Returning back to P4 the problem can rewritten as
min
( R)
s.t. X 1 0
= u 2 A) + R.
or equivalently,
min A
(V (V", xTTT))) pn.
(20)
Now, assume that (V" ()) < for some > 0. Observe that ulc- x)) c o for positive constants Therefore,
(v ( 2))) co-i .UT, a (V",
be made arbitrarily low. Therefore, the value of (20) equals -o. Conversely, assume that (v1 u( $7 A)) > 0 for all X > follows that the value of (20) is bigger than equal to pa. Since À = feasible for 20 the value is exactly p".
Since 1 < x <. oo, letting - 20, the value of (vi",, (07 (c. ))))
29

---

Published in Transactions on Machine Learning Research (01/2023)
Before prove Lemma G.3 will state and prove the following Lemma which characterizes the subgradient of the too norm.
Lemma G.5. The vectors 2,24 E I= satisfy @1 if and only if (a) 0 and || _ 1 (b)
|| = 1 and 2 E ü(w) where
(c) if w3 > 0
k(w)=
I EER:: E
[-c] ifw, <
for some 2 0
1-,, c) ifw; =0
Proof. By Proposition A.22 in Bertsckas 1971
@| = convfw s.t |10 S 1, 2 w = [| = fw s.t ||00|22 I 1, TT 13/o00
(21)
analyzing the above result, note that
x
Σ
2
(a)
W ||=||
||wll
||
| llx
Since 2JTo w = ||= equality holds in (b), implying ||=]] = or 0 and in (a), implying z,w; = |ws] ||
for all i. This means that if | < || then w; = 0, and if |zy| = || then 2 if 2 2 0 and w S 0 if
2; S O.
In other words (this time conditioning on w), ||l]| < 1, then 0. Otherwise, we > 0 then 2; = || if wi 0, then 2; = - || and if w; then 2 can be any value in -|=||||0 |== Therefore, the proof follows by setting c || (the last condition obviously true but it important to make explicit will become clear later). This brings to the following result.
We can now prove Lemma
Proof of Lemma The main idcas of the KKT analysis in the proof of Theorem G.2 still hold and the only condition that changes is the stationarity slackness condition. Formally, the lagrangian equals
R R (
Therefore, the stationarity condition can be written as
DE क T x R al =
b T X E a R-A
(22)
By Lemma G.5 and given the fact that ū(-x)) = -(x), the above condition holds if and only if
- R T क A|| = 1) v (1 -1AR-R=0)
P4 can be rewritten as Combining with the complementary slacknoss and dual feasibility,
min V.A
p" + (1= ee)
8.t.
1 0
(v u| $ X) TT 1) (1 A/1 =1Ar=
Now, observe that ūee r) ū(x) for all e > 0. Therefore, the || | A|| = inside the first clause of the last
constraint is equivalent to $ since if $ # 0 and / A|| 1, tthnn || X| 1 can be satisfied by
30

---

Published in Transactions on Machine Learning Research (01/2023)
replacing À with |
A. Similarly, the | X inside the second clause is redundant. Therefore, the
last constraint can be rewritten as
(U (
Vo=0
Now, observe that & X + O is equivalent to X + 0 as the rows of 2o are independent; this is becasue the only row with nonzero (s, o 74 (+)) is the one corresponding to (s, a + (f())). Therefore, the optimization problem can be rewritten as
min V
pT + (00,2)
A
AX V
Assume that there exists À * 0 satisfying À > such that (u( A), .5T) < 0. Then for any c <> 0, c. x( E ((TA) and therefore, the value of the optimization problem is -oo. Otherwise, the value is lower bounded by p and the bound is attained with 0, concluding the proof.
Proof of Lemma G.4 We begin by analyzing P1 as before. Forming the Lagrangian,
R R
(
Therefore, the stationarity condition states that
T
x' - R
As before, the primal feasibility condition holds, dual feasibility states that À > and complementary slackness states that a(s,a) for all (s,a) & @st Therefore, A(R) R if and only if
T E R||
(23)
Note however that vectors 2, satisfy 0| if and only if
= if
24 0>0,
2 0 if wi = 1
10
2 0, E 1-11]
- if
2
0 if W. =-1
if =
0 if (-1,1)
19 is feasible and À be the vector satisfying 19 By 23 we conclude that the vector R(s, a) M(s,a) - [(s, a) = (s, ā)] satisfies A(R) = π for any / 0. Therefore, if ( 0, the solution to P4 is -00. Conversely, [99 not feasible for any such a, then it follows that R(s, a) 2 R(s, a) for R, s, a satisfying A(R) it and <aass) > Therefore, the value of the optimization problem is lower bounded by pT. Since A(R) R, the lower bound is attainble which proves the lemma.
Now, assume that T[āas) > 0 for some (5,ā) a) for which
G.4 Proof of Proposition 4.2
Statement: Let Ceonet R, R') be constant cost function, and assume that Cconst E C. Then problem is unboumded from below.
P2a
Proof. We will show that for any the value of the inner optimization problem of P2a equals -00, thereby proving the result.
Let be an arbitrary policy and consider an arbitrary vector R. By definition of Coonst and the fact that R is feasible for (II), R A(Ceonat: R, xq) Therefore, R, Ccoust are feasible for P2ah. Since R was arbitrary, it be chosen such that the p" is arbitrarily low, proving the claim.
31

---

Published in Transactions on Machine Learning Research (01/2023)
G.5 Proof of Theorem 4.3
Statement: There erists MDP M (S, R. R. 7,0) for which problem P2a is unbounded from below when Coo E C.
Proof. Let л be an arbitrary policy. We will build an example where the value of the inner minimization problem of 12a is -00.
Consider a singlo-state MDP with the reward function R = 01,0,0,0) where # is the first action and C = 1. Since R is symmetric with respect ag, a3, 04, we assume without loss of generality that x{a2) S T(a3) I a(a)). For any x, consider the reward function R' = (1 I, 2. -2, -2) with actions , 0g. 04. We claim that R A(eao R', m4, To see why, consider the attack optimization problem (PT). The cost of the attack optimization problem is at least because (T(T+)) - R' (a2) 1 - 2x and any feasible R needs to satisfy R(x+) R(a2) 2 1, which implies
R
2 max ( [((TT) - R(;T)) Ra22) R(az))
R((T)) R' (T,, + Rd (a2)) R(a2))
1
(2r + =
Since 11' - R
x, we conclude R E A(coo: Rt, t Et) as claimed.
We now consider the score of the policy under the reward function R' and show that, with the proper choice of z, it is unbounded from below. Since R E A(cx, R' (q,e)) this would show that the value of the inner minimization in P2al equals -o,, proving the theorem.
By definition, R. be written as
= = T(a1) + x(T(22) - x(a1) - x(as) - =(as)) = (a1) + x(T((2)) - (1 T(a2))) = x(a1) + =x(2((2)) 1).
Since Taa))= S n (az) S (a4) however, conclude that (a2) < 0.5. Therefore, tending æ to infinity finishes
the proof.
H Computational hardness results
In this section, we provide computational hardness results for different choices of C, showing that the defense optimization problem P2ah is NP-hard in different cases. While our results are stated for the defense
optimization problem P2al] all results hold for (P2b) well with minfed, Our proofs rely the
results of Appendix G and we therefore refer to this and rely on notation introduced in this Appendix; namely,
the notation o and up introduced in Lemma
H.1 Hardness result for p p= oc
We begin by considering the case of Coo. By reducing the 3SAT problem to the defense optimization problem (2ab,, we will show that (Paa is Na-hard. More formally, we prove the following theorem.
Theorem H.1. For C = {coo it NP-hard to determine whether the optimal value of problem P2a is greater than or equal to pTt
We assume without loss of gemerality that the clauses do not. contain duplicate variables as the 3SAT instance remains NP-hard in this case.
Before proving the theorem, we prove a weaker result which essentially proves hardness assuming we can set the matrix o and vector s be set arbitrarily, without the restriction that they correspond to MDP.
32

---

Published in Transactions on Machine Learning Research (01/2023)
Proposition H.2. Assume given an instonce of 8SAT with clauses c Cm and variables (#15...
Define k 2n and 4n + m + is possible to build, in polynomial time, a matria M E Tikke vector ğ E ER such that is strictly positive and
If the 3SAT instance satisfiable, then there crists a X # 0 R2 satisfying À x 0 such that
(M 2), <
In addition, M X does not contain ony zero entries. If the 3SAT instance is not satisfiable, then for any + 0 E I8* satisfying 7 0,
Uoo (M (M
1
Proof: We begin by an empty matrix and vector and in each step, add value to Jí and add column of size k to M.
We will let (On, d1...., an by,..., b,) be placeholder names for the coordinates of X Since the optimization problem are considering involves the matrix product M for ease of notation, will specify each column of M by the linear map forming the corresponding coordinate of M X. As an example, do + 40z + 5bs is a column that has value 1 in do, 4 in 03, 5 in by and everywhere else.
Defining := 500k, we first add the columns below.
dg + Σ
a1 +
b;
(24)
i=1
i=1
0.900 - (a; + b;)
Vi E [m]
(25)
-1.1a0 + (a: + by)
Vi E [n]
(26)
(0.9ag (a: b,))
Vi [n]
(27)
4 (0.9ao
(b: -a))
Vi [n]
(28)
The value of jí for (24], 25
26
27 and
(28 is (6n² + m }), 3n, 3n, 1 and 1 respectively. Note that
(24) is the all-ones vector. The constant e in proof, but will be useful for later.
24 and the constant 4 in 27 and (28 will not matter for the
Next for each clause with variables (2,, My, 2x), we will add the following column where d, denotes a, the variable vi appears as positive in the clause and by if the variable appears as negative.
0.95 ap (de + dg + dr)
(29)
The value of jü in the above is 1.
We now prove that μ, M have the mentioned properties.
If the 3SAT instance satisfiable, this is easy to show. Set dp and set (a,, b;) to (1,0) if x; is
set to true in the satisfiable arrangement and to (0, if x; is set to It is clear that the coordinates of =(M²>) X) corresponding to 24h. (55 and (26) equal 1, -1 and -1 respectively. Furthermore, since {a. b; a.) {1, -1}, exactly half of the coordinates of x corresponding to (27 and (8 equal 1,
while the other half equal -1. Furthermore, all of the coordinates corresponding to (29 equuall -1. Therefore,
the inner product (7, u(M x) equals
1
1
(6n² + +m 2) n. 3n n 3n + 0
2
which proves the claim.
33

---

Published in Transactions on Machine Learning Research (01/2023)
Conversely, assume that the 3SAT instance is not satisfiable. Let $1:...82 denote the coordinates of ji with $1 corresponding to 24 and let u[s] denote (u(M">) A)) (s). Let X + 0 satisfying x be an arbitrary vector.
First note that since + O, (MT)) X) (s1) is strictly positive and therefore u(s1] = 1. Since (b(s1) = 6n + 2 we need show that
{ 1),
>
Σ
((s) u[s) > -6n² -m + 2 4
(30)
sp8
((s) (u[s] +
1
(-Gn²
3
+
2n 3n + 2n 1 +
(31)
2
8
3
Σ ((s) [u[s] > s9881
n
+
(32)
8
Now note that since the value of jé in coordinates corresponding to 25 and 26 is > n + 8x one in any of these coordinates, then the claim is proved.
if u[s] equals
Therefore, we assume w.l.o.g that for any i,
0.9ag S + bj S 1.1ag-
This implics that any of be,.2222 is strictly positive, so ap. Since least one of {ao, Qz. b,} needs be strictly positive by the assumption À + 0, we conclude that ag is strictly positive.
Now note that u[s] is 1 in more than half of the coordinates corresponding to [27 and
28 then 32 will
hold. We can therefore assume w.l.o.g that at least half of these coordinates equal 1. We note however that
if u[s] equals -1 for both 27 and 28 for some
S i I then
0.90g S a, 6, 0.9ag S b, a; ao
ag 0,
which is not possible. We can therefore conclude that for any fixed i, u u(MT>) equals in exactly one of the two coordinates corresponding to (27) and (28). Therefore, cither a; b, 2 0.9ag or b, - a; 2 0.9ag. Since ag + b, 2 0.9ag, we get that either a; 2 0.9up or 2 0.9ag- Since a; + b, 1.1ap; the bigger one 2 0.9ag and the smaller one is < 0.2ag.
Finally, note that if u[s] equals 1 for any of the coordinates corresponding to 29 then (32 would hold since u[s) was already for half of the coordinates corresponding to (27) and (28 We can therefore assune that u[s] is -1 for all the coordinates corresponding to (29). Note however that if d, + dj + d+ 2 0.95es, then at least one of the d, must have been 0.2. This means that all of the clauses must hold true (in the 3SAT sense) with 2, set to
1, 2
-1,
otherwise
This is not possible however as assumed that the 3SAT instance was not satisfiable.
Claim H.3. Define M above and let st denote the colurn of the matrix corresponding rous U in M, we have
24 For all
((1) 2 50 [0({)))
111
which further implies Σiz [ō())) S (1 1/50)ū(s1).
Proof. The claim follows trivially from the fact that as o(s1) and all other entries in T are less than 4.
Next, we prove the following lemma which essentially states that for any desired value of Oct, we can find plausible reward function R such that 0 equals this value.
34

---

Published in Transactions on Machine Learning Research (01/2023)
Lemma H.4. Let M be an ergodic MDP with unspecified reward function and let ι4 be policy in this MDP. For any value of et > O and any set of state-action pairs θ C S x A salisfying en ((8,((8)))))) :8 E S) = 0, there is a reward function R such that
1. R is feasible for the attack problem P1
Le, TT R
c4.
2. =
Proof. Consider the following reward function,
if a = (s)
R(s,a) =
if E θ
n (xtt) (e) 2.E 1 (1)))))) (x)
O.W.
It is clear that pat = 0 and
-t
if (8,0)
for all (8 (8)).
-2c O.W.
which proves the claim.
We now use the above results to construct an MDP, formally proving Theorem H.1 Given an instance of
3SAT, let M, f denote the values specified in Proposition H.2 Recall that M gexe and j R where
k
2n +1 and 8 4n + m + Let 8 > 1/2, [1/2,1] 1] be parameters to be specified later. (see Claims
H.11
H.7 and H.5.) Intuitively, we need 5 to be close to zero and y to be close to one.
Given these values, we will build an MDP with reward vector Nt with e states and k + actions for which |0|- A and the 3SAT instance is satisfiable if and only if
R* A AA (u>e (DTA), < O.
(33)
In our construction, the states 8:21 will each correspond to the columns of M while the states s-2, 8-1, So will be new. Furthermore, in state so, each of the actions + (50) will correspond to a row of M.
Let M denote the submatrix of oo with only columns corresponding to (s, (s)). We first observe that 33
can be simplified bocause Tha (s,a) is 0 for all s, a + my (s). Therefore,
33 is equivalent to
O R* 12 (M X), A). O.
(34)
In order to specify this MDP, we first specify the transition probabilities of πÿ- In state 80, following कt leads to s for i i {-1, 22} with probability 8/2 and leads 8; for 2 1 with the probability (1 - (3;)s; where
(35)
In states 8 * sn, following my will lead back to s with probability The initial distribution a of the MDP is chosen as (sp) and ass)) = for + 0.
It is straightforward to see that
7.8 2. (so) (1- V- :tt (s:)
vi W221 = 7 (1 (1- -)) [(s;))
Now, for each of the rows in M like U. we add action a to state so with the following transition probabilities.
P(so, 7t (8)
if j=0
P(so,a,55)
P(su, x (80); 83)
8
(E))
if jE(-2,-1)
(36)
(+(0) 85) + 20 ((s))
if j21
35

---

Published in Transactions on Machine Learning Research (01/2023)
where 0 is taken to be large enough such that for all i,
0 min (i(ss) 2 |00|
Note that the value of 0 is the same for all the rows of matrix; it is set to the maximum of min, ||
across all rows T M.
Claim H.5. 1f < to: the transition probabilities specified in 335 ore valid, i.e,, they are in the range [0, 1] and Eg (800 a, 8 1.
Proof. In order to make sure these transition probabilities are valid, they need sum one and they all need to be non-negative. They sum to one by definition. As for being non-negative, it holds trivially for and holds for by definition of 6. Formally, for 1,
5 (Evte v(s))
1 T(5(s)
P(s0: 7 (80). so) 4
= 6
4
1
E((s))
8
(min (i.)
2
4
|10||
1
1
8
2
2
and for j 2 1,
6 o(8;)
6
[0(0))
P( ni (80), 83) +
P(so: (8))))
2
2
6
v(s,)
(1 1)min Th,
(min p4
|
35
(min7%)) (4))
2
Now, using Lemma H.4 set the reward for the MDP such that 0 consists of the added actions in 80- Note that there are multiple actions in the states 8140 as well; however, given Lemma H.4 their transition probabilities are not important and can be set arbitrarily as long as the MDP remains ergodic.
Claim H.6. For all a, + NT, (50),
(M) (0- (-40
5
5 40 7.
8
40 7 1 ((s))),
-(1 (1-7)) 7),
29
where T is the row corresponding to a and we have abused notation by using 7 entries of the vector.
T denote the last k
Proof. As before, it is straightforward to that
=(1 77) and
8 8 ((s,))
Wi (-2,-1) - (8i) = 7.
2
40
and
iA 2 1: (t =7 ((1-0) -p(s)) + ((ss)
8
20
36

---

Published in Transactions on Machine Learning Research (01/2023)
Claim H.7. If maxf6, 1 -1 1 "|[=|],
then
|+ll
0 Σ
1//
7(1 - 5)
1
Proof.
|
Σ (E (7(()))))
= 7 + (1 (1-7)
7(1 -5) -11411
(37)
7 5)
1m-
1
S 4 |1xll (6 + (1 -)) S 8
(38)
Claim H.8.
The 3SAT instance satisfiable if and only if holds.
Proof. Given Claim
H.6 the sub-matrix of M corresponding to columns 8,21 oquals
7 8
M.
2.0 0
Let Uoo (8) denote u ((s)) For any X,
(1T u((2 = Σ
1 (8j))uoool [8i] +
ju
7- (7-(1-0) 6)
Hr, ul 7.
mTa))) 2) 2.
||
j=-2
22. (2.(1-0) -1-11-0 5)
Σ
p 5 (3,)
Fr u(Mi X1)
|7
M 71-83: it follows that
Multiplying both sides by
71 - 5) u(M" A)) - (pt u(M ui)x">i)
|
Σ
1:01 (s)u [s]]
(39)
7(1 - 8)
1=-2
Σ (m)
(40)
7(1 8)
jーー
(41)
8
Therefore, by Lemma H.4 if the 3SAT is satisfiable, then there exists À such that
17 7(1 8) (40), u(M
1 + <
<0.
4
If the 3SAT is not satisfiable, then by Lemma H.4 for all feasible X,
|
1
711 8) (NTT, u(M a))
0
which proves the claim.
37

---

Published in Transactions on Machine Learning Research (01/2023)
H.2 Proof of Theorem 4.5
Statement:
For C = (cp s.l. p E [1, x)), il is NP-hard to determine whelher the oplimal value of problem [2bb is greater than or equal to p" We will prove the result using the same MDP as the previous Section.
We need to show the 3SAT instance is satisfable if and only if
3p (1,, X A ( ()) <0.
As before, let M denote the submatrix of Do with only columns corresponding (s)): As in the previous section note that because (s, is for all 8,a # (9(s), the above condition is equivalent to
p (1, E A O^ (up A), p < 0.
(42)
We split the proof into two lemmas.
Lemma H.9. If the 3SAT instance is satisfiable, then
42 holds.
Proof. In this case, then the same proof as before basically holds. Formally, consider the À used before in the proof and consider the vector M X. We need to show that there exists p for which (n"t, (M² A)) is negative. Note however that
(n ",,, A)) Σ (s:) up ((M" ()(s))
For fixed x * O, (x) is a continuous function of p and lime Up(x) = (x) we show that all of the coordinates in M X are non-zero, this would imply that (n*t, up (p( converges to (n"*, Uho (M²)) for large enough p which proves the claim. Therefore, (n up(M) is continuous in p and letting p be large enough proves the claim.
It remains to verify that all of the coordinates in M used in the above proof were non-zero. Since all of the coordinates of M À were non-zero by construction of X, conclude that MT), X is non-zero on 8:21- For i e (-2,-1}, given claim H.3 we have Σi> 0(s,) > O, for all rows of M, which means M is strictly negative on these states. Finally the entry corresponding to so equals -prt (so) in all rows of M, which implies (M**) X) (su) is strictly negative, proving the claim.
Lemma H.10. If holds, then the 3SAT instance is satisfiable.
Proof. We assume that * 0 without loss of generality; if X then (151, uM x)) negative.
which is not
Letting up[s] denote up (AMT))(s:)) and dp(s) denote = up[s], then (n up (M x)) can be rewritten
(
Σ 1 (8:) (8]
(43)
1=
[s)
(p
+
[
+
(
+
[p(
(s
+
dp [s]
(44)
24
25
26
27
28
29
where in the above, we have broken the sum in different parts, depending on what s; corresponds and we have abused the notation by using the set (24) denote all states that correspond to Equation (24p. Note that
the sum corresponding to 24 consists of single state. We will also use 81 to denote this state.
We begin by stating some properties of up and dp- Claim H.11. Let y be close enough to 1 such that
cō
> (1 7)-
40
38

---

Published in Transactions on Machine Learning Research (01/2023)
Then for all rows ú from M,
Vs + 81 |up[s|] - uplsi]
(45)
Proof. We need to show that for all rows v in M, 10(81) 2 [u(s) for all 8 + 81. For 2 1, this follows immediately from Claim H.3 and Claim H.6
As for so, we need to show that
7.6
v(s1) 2 [e(s))]
+
0(81) 2 (1 (1-7)
20
Note however that
7.8
T(s1) 2 v(s)) 211
20
40
by the assumption
Claim H.12. For any E [n], letting & and 8; denote the states corresponding (27 and (8 respectively.
dp[3,] + dzl 0.
Proof. To prove this, observe that
0.9ap - (a; - b,) + 0.9a0 - (b. a.) = 1.800 2 0
There therefore two possibilities: (a) Both 0.9ag (a, b.) and 0.9a0 (b, a;) are non-negative.
In this case, both d, [5:] and d,15%] are non-negative and the claim follows. (b) 0.90g (a: b.) 2 0
and 0.9ag - (b, - a)) < 0 or vice versa. Assume w.l.o.g that 0.9ap - (a; b)) 2 0, i.e, d,[3,] 2 0. In
this case, |0.9ap (a, - b,)l 2 |0.9ag - (b; - as)l and therefore, since 1² (R;) = 1rt (8)), we conclude that
d z [3][ and therefore the claim follows.
We split the proof into several cases.
Case 1: There exists s E (25 U (66 such that dp[s] 2 0.
Let be such state In this case, define dp[s] follows
if s = 3
E 27
(2
[
[s[s)
if
[s]]
O.W.
We first claim that Edpls 2 Σ dpls). To prove this, note that dp[s] 2 dp(s) for all $ therefore need to prove that.
27
28
We
drls) O,
which follows from Claim H.12 by summing all E [n].
39

---

Published in Transactions on Machine Learning Research (01/2023)
Defining $ 8 (fs1,
27
28
note that
Σ [ dp(s1] - Σ [dp[>i|l
SES
nr (81) [1l
Σ
1r (8) |1p[s;]
SES
10t (81) up|o1]
Σ (s) |upps1]]
SES
= |1p1s (0)((1) Σ 1 (s)
(s)
#ES
Defining 3+ = 5118-2 8-1, 801,
((81) Σ
[i(s) 6n + m
-(2n
1) m
=6n² + m
66n2
3n m
2
1
3n
4'
Clain H.7 now gives contradiction as the inner product in 42 becomes positive.
Case 2: [s] < for all E (25 U 26 and |aj - bb S 0.9ag for some j E [n].
In this case, we conclude that
+ by E [0.9, 1.13a0 Vi E [1,
Since either a₂ b; must be strictly positive for some (because À * 0), we conclude that ao 0. Similar case 1, we introduce a new vector d such that Σ. dpls] E, dp(s].
Let šy and 8y denote the states corresponding to 27 and 28
respectively for i j. Note that by assumption,
151 up [35] 2 0. Assume without loss of generality that Up [y] 2 up13,). Define the vector dr as
0 if E 27
28
(55}
[p10] = dp[s] [+]] O.w.
if E {81,3,)
35}
As before, Σ dols] > > [s]... states, we have ds[s] d, We now claim that
More formally, for 27 and
28
we use Claim H.12 and for all the other
Vs
25
26
29
|s,[ S Up [3y].
(46)
This is because
(MF + (M (3))
(M (MT\) x)(3,)
3.600
2
while {(s)) 2.35ap for all
25
26
U
29
This is because a; + b. [0.9 ao, 1.1 ao)-
40

---

Published in Transactions on Machine Learning Research (01/2023)
Defining S
25
26 U 29
we conchude that
Σ dpls)
dplss
= (s1) up(s1] + (3)) 2p1551 Σ (s) - |up[s|| + Σ p (s²) -|up|s:]]
$53
2 (s1) up1s1] + 1e (8,) Up [3 + Σ 1 (s) - lup [3,]] + Σ
1et (s.) - -1pp(s1]]
$ES
2
nT (s1) Σ n (s))
-upls1] + 11 (3,) Up up1351 + Σ
: (s) -11upp3]]
1=-
z
prt (81) Σ
10t (8))
[ppb3]] + 11 (33) Up up135] +
11 (8) |,ااا
1=-2
SE8
0
= uplša]
(51( + (3,) - Σ 1 (s,)
[s)
Here, for the final incquality we have used the fact that f (81) - - -/==211" 2 0, which follows from Claim H.7
As before, note that
1 +1 2n 33 m 2
M(s1) + ((3))
Miss) 6n? + m
2
sEB
Claim H.7 now gives contradiction the inner product in 42 becomes positive.
Case 3: [s) < 0 for all E (25) U 26 and |a; b,l 2 0.9ag for all 1 S sism n.
Similar as before, define dz as
if
8 E 27
U
dpls}
dp[s] if
81
min (nin(dp(s).0)
0} if s E 29
[dp[s]| O.W.
As before, E. dplss 2 E. Jr(s). Therefore,
Σ dpls) 2 Σ dglss
0
= - (81) [pp[1]]
|up[s]|
+
1 (s) min (up(s)) 0} Σ 1rth (ss) |up[si]]
26
EE
2 1.t (81) uplsa]
#
|up[s
p (s) |up[ss] [up[s] < 0] Σ p (st) [1p[ss]]
=
=-p[s1] - 11 (81)
(s) [up[s] <0 - Σ (si)
Assume for the sake of contradiction that the 3SAT instance is not satisfiable. There are two possibilities. The first is that for at least one s E (2 we have un [x] 0. In that case,
1
(((1))
(i(s)
Σ
x [upls)
0J 2
2
41

---

Published in Transactions on Machine Learning Research (01/2023)
As before, Claim H.7 gives contradiction. Otherwise, Up [s] < 0 for all
29
In that case, we have
Usc (MF A); (3)
6n + 1/2 2n 3n - 1/2,
which contradicts Proposition
H.2 as À A O.
Proofs of Appendix B
In this section, provide more formal treatment of the results in Appendix B
formally stating and proving
these results.
Proposition I.1. Assume that condilion 1 holds. Sel E as
(prt- p
== min (,
Consider the following policy
1 [a La (T)
TD(als)
(47)
10: +1
characterizes the solution to the optimization problems P2a and (i respectively. Furthermore, in both cases p p
Equation 47
and P2b with porameters c
Proof. Given Theorem 5.1 optimization problem
Theorem 5.2 and Lemma D.3 suffices to show that if S é, the solution to the
max (v. R) NEW
(P4)
s.t. ( -t 15) 2 0 a
corresponds to the occupancy measure of policy TD defined by Equation
47 Namely, the optimization
problems (2aa) and [P2b correspond to the optimization problem PP with parameters e = et and
min( } respectively. Since ē S Et, the primal feasibility condition in Lemma E.1 implies that the
solution the above optimization problem characterizes both cases (2a) and P2b
Now, due to Lemma
D.3 have
V E
SAAA
Σ
-1 (1- + > s
3,8
Since P(s,ū, s) is independent of ā, the second condition is equivalent to
Vs Σ (s, = (1 7))(s) + Σ (3), Σ (3,,a))
which, due to 12 is equivalent to
Σ as) = p(s).
Furthermore, given the independence of the transition distributions from policies, have the following
u(s) (3, = (s,a) a)
-
u(s) if (8, (s, 7s))
(48)
0 o.w
42

---

Published in Transactions on Machine Learning Research (01/2023)
Therefore, the constraint (1h7t -65 ,1/ 2 0 is equivalent to v²(s, 2 (T Furthermore, note that
(8,0) E = parisnat - -p¹t -p-t--6 -E4
(wi (1imitora) , ,R)) -
R(s,a) - Riss, (()), p(s)
ct
a
Putting it all together, the optimization problem P3 is equivalent to
max
R,
1
8.6.
(+))) S a)) Vs,a E O
Σ ((s = =ss)) Vs
(s) 20 0 a(s,a).
Note that the maximization is now over all vectors R|--- as the constraint ei v has been made explicit. Furthermore, given Lemma D.3 and Equation ( any vector y satisfying the last two constraints
(the bellman constraints) corresponds to policy π through
(als)) = (s.aa)
p(s)
In other words, probability of choosing in state is proportional to (s,
Now, let us analyze the solution to this optimization problem which we will denote by m This solution tmax exists, since the optimization problem is maximizing a continuous function on a closed and bounded set.
We first claim that if & O; U (s)), then (smax(s, a) = 0. If this not the case, then Umax not optimal. Concretely, consider the following vector vb
Viaax (8, a) + 19: maxx (S, 3 S=sAGE6;
1
(3,
0 if ă
3=6
8 A AĀ==
(max o.w.
In other words, we uniformly spread the probability of choosing action a in state s over the set θ U (s) The vector ve still satisfies the constraints: ā E 0r (ss,, (s)) (bs = timax (s. x, (s)) vimax (s, a) and the objective has strictly improved because
p=i(=i)) 5 < - a( S (+)) m(s))
Since & Og the inequality is strict and therefore
vā E e u (s) A(s,a) > R(s,a). This means that s was not optimal, contradicting the initial assumption.
Now note that if Vm (s, a) v'max (s, (T)))) for some a E O then again t'max isn't optimal as we could replace it with
Vmax (5, a) + V (s, a)
1lmax (8, (x)) if == (f
θ + 1
(13 a) =
Vmmxx (8, O (+) max (s
Vmmax (s, J4. (s)))
if ==saaaa
Umax (3, O.W.
43

---

Published in Transactions on Machine Learning Research (01/2023)
Intuitively, since the action was being chosen with strictly higher probability than action T (5), we have uniformly spread this excess probability among the set 6 J (s)( This vector would still be feasible (s),a) (s)) and would be strictly better in terms of utility as RT our initial assumption and therefore 1/max (s, a) 1m (s, (+))) for all E 65.
M(saa). This contradicts
Since the occupancy measure mmax satisfics (s a) 0 for all a & (*+((((s)) and 4 (s, (bs x+(s)) for all a E er we conclude that it is the occupancy measure for the policy TD as defined in Equation 47
In order to prove pa = prD first note that for (s,a) E or
- (1ptilesa) - 15 ) ((s) " n (+)
=u(s) (u())((D((aaa)))) (D(T = 0,
where we used Equation
48 and Equation 47
Therefore
n p
R R m0
asia ( - - (
(s.a)E
Σ agaa" 0
(s.a)Ee
0,
where (i) follows from Lemma E.3 in the known parameter and Lemma case.
F.3 in the unknown parameter
J Additional experiments
In this section, provide the worst-case score of the policy from the defender's perspective i.e., the value of the inner minimization in (P2b), for our policy. Given the results in Section 5.2 (Theorems 5.3 and 5.2). by construction of TD. this minimum is achieved for R = R and therefore the worst-case score equals pTD
As mentioned in Section 5.2 T is certificate in that we are guaranteed pTT 2 pTD as long as cp 2 64-
The results are shown in Figure in line with results of Section 5.2 as in this case, TD Ty and Ti is the optimal policy in R. In addition, when ep < ét, the value of gTD increases with e+. This is because when increase the attack parameter et, the policy के needs become optimal in R with larger margin, which causes its score increase.
As shown in the Figure, the value of ~TD is larger when eD < <t.. This is
We note that for both enviromments, when no defense is employed, i.e, when using the policy Hi we will obtain the same worst-case value when ep < et when cp 2 4-
Tt, and we will obtain the worst-case score -oo
0.9
0.9
10
Attack purumeter
0.7
Attack parameter
0.7
0.5
0.5
0.3
0.1 0.3
0.1
0.1
0.5
0.9
Defense parameter (rp)
Defense parameter (eg)
Figure 6: The value of the worst-case score from the defense perspective, i.e., nTD under different values of Cp for the Navigation (left) and Grid world (right) environments.
44


Reviews:
[{"review_id": "7UFsscSYmZ", "reviewer": "Reviewer_5huZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe paper is quite complete it propose a clearly formulated problem and propose a theoretically sound solution. The theoretical results are quite solid and offers an elegant solution to the problem. The experiments also clearly show the robustness of the agent to such attacks.\n\nWeakness:\n- The main paper lacks some important details that could make the paper easier to read:\n    - Some theoretical results would benefit from a small discussion about the implications of the result and why such result is useful. Right some of this is left to the reader to figure out. For example, it's not clearly explained why they introduce the reformulation (P1'), this is only clear from the appendix. The proof of the equivalence of (P1) and (P1'), is in the appendix, however I think a short comment about why this holds would help with reading the paper.\n    - Some other details, for example the fact that P3 is linear in $\\psi$ would be worth mentioning in the main text. Or some indications about the structure of the proofs, or some more intuition about the results would be welcome to make the paper easier to read. For example the paper introduces $\\Theta^\\epsilon$ without any explication, a short explanation on why this is needed could be valuable.\n- Although the code is available, the main paper is lacking some crucially important details for reproducing the results. From my understanding of the results of the paper, solving the different problems in the paper requires to compute the state-action occupancy measure for the target policies $\\psi^{\\pi_\\dagger}$. However the details on how such quantities is omitted from the paper and the appendix. I believe such details are crucial because those quantities can be hard to compute for example if we don't have access to the state transition probabilities which is usually the case, and leads to approximation which needs to be mentioned in the paper. Please correct me if those quantities are not needed for solving the different problems, and provide more details on what quantities are required to solve the different problems and how they are computed.\n- The authors mention in the appendix that they use a convex programming solver to solve (P1'), (P2a) and (P2b). From my understanding, to solve (P2a) and (P2b), the authors actually solve (P3). However this is never clearly stated, and explanation in appendix C.1 makes it more confusing since it doesn't mention (P3).\n- The experiments are quite toyish, and it's not clear if the observation would scale to more complex environments. In particular, the problems seem to be harder to solve for environments with large state and action spaces. In general, the paper doesn't discuss the assumptions required for the results and doesn't mention any potential limitations of the proposed approach.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper propose a defense mechanism to protect against reward perturbation in reinforcement learning. They assume a scenario where the goal of the attacker is to change the reward function in such a way that the target policy of the attacker is optimal under this new reward while staying as close as close possible to the original reward function.   \nTo defend against such attacks the author first propose a min-max formulation where the agent has access to the perturbed reward function but not the true reward function, with this min-max formulation the agent is trying to find the optimal policy to solve the worst case scenario.   \nThey then provide several theoretical results about the guarantees of solving such problems. They show that in the most general setting no guarantees can be obtained. However in specific cases, such as when the cost function of the attacker is the L2-norm, they show that an optimal policy against the attacker can be found by solving a convex optimization problem.   \nFinally, they show in a Navigation and Grid world experiment how the proposed approach indeed make the agent more resilient to such attacks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I strongly encourage the author to include a discussion about the necessary assumptions, such as ergodicity, on how and why they are important for the results. As well as discuss, the limitations that such assumptions bring.\n- I strongly encourage the author to provide more details about the computation of $\\psi^{\\pi_\\dagger}$ and other occupancy measures used for solving the different problems.\n- Clarify whether (P3) is used to solve (P2a) and (P2b).", "broader_impact_concerns": "The author mention in the intro that AI models should be \"technically robust and resilient to security threat\". This is indeed very important and this paper is a good step in this direction. However, I think that the paper should clearly mention the limit of the proposed approach to avoid giving a false sense of security.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ensOJ6zw4Z", "reviewer": "Reviewer_uuwj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strong points of the paper are:\n- leveraging standard tools from robust statistics to derive a natural formulation for the adversarial perturbation problem, and a natural and pretty complete analysis that includes pretty efficient (i.e. polynomial) formulation to compute robust policies.\n- a very clean exposition with a very good flow, and that covers most of the natural question that arise in this setting\n- providing both feasible and unfeasible scenarios, and exploring the implications both in terms of the reward as well as computations\n\nThe paper has two main weaknesses. The first is that it takes an exclusively finite/discrete space perspective:\n- from the theoretical perspective by relying extensively on iterations over finite actions/states, and on discrete KKT conditions\n- from the practical perspective by relying on general constrained convex solvers, which do not immediately extend to an infinite number of constraints\nThe second is that despite providing a provably defensive policy (i.e. one that will achieve at least as much return under $\\bar{R}$ than under $\\hat{R}$), they provide no guarantee on the gap between the true (non-attacked) optimal policy and the difensive policy, or otherwise any upper bound on the maximum achievable performance by an attacked agent.\n\nThere are a few minor weaknesses regarding clarity that lead me to doubt (possibly due to misunderstandings) the soundness of some results:\n- On page 6 the authors discuss a $\\pi_{\\cancel{\\pi}_\\dagger}$ policy, and claim that for any policy $\\bar{\\rho}^{\\cancel{\\pi}_\\dagger} \\geq \\hat{\\rho}^{\\cancel{\\pi}_\\dagger}$. This does not seem intuitive to me, for example when $\\bar{R} = \\hat{R}$ this would clearly not be the case.\n- The authors repeatedly state that $\\epsilon_{\\mathcal{D}}$ should be taken as large as $\\epsilon_\\dagger$, but while they describe in detail the disadvantages of selecting a too small value, I do not seem to find any discussion of the drawbacks of taking it too large. This would lead to the counterintuitive conclusion that it is always better to just select an extremely large epsilon (e.g. as large as the norm of $\\hat{R}$).\n- Thm. 5.3 seems to suggest that underestimating $\\epsilon_{\\mathcal{D}}$ will lead to the only feasible policy being $\\pi_\\dagger$. This again leads to the counterintuitive conclusion that one can easily estimate $\\epsilon_\\dagger$ by doing binary search on the epsilon value until a threshold is found where $\\pi_\\dagger$ is not the only solution in the set anymore.\n\nAnother very minor weakness is the $R'$ notation used in P1. While it is more general, AFAIU in the papr $R'$ is always set to $\\bar{R}$, and it would be more straightforward to introduce it as such (no need to pay the cognitive price of a more general notation if it is not used).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "At its core, the paper provides a characterization of the set of \"plausibly\" optimal policies under an adversarial perturbation of the reward function, and then uses this result to either:\n- derive policies that are robust (i.e. defensive) against the perturbation\n- show an impossibility result\ndepending on which assumptions are placed on the adversarial perturbation.\n\nIn particular the author's analysis considers an adversary that tries to induce the agent to adopt a target policy by perturbing the reward function to make this target policy optimal. The agent is aware (to varying degrees of details) of this perturbation, and tries to learn a policy that will provably perform as well as possible under the original (i.e. unperturbed) reward. Since the agent cannot give any such guarantees for fully general perturbations, the authors focus on perturbed rewards that within an epsilon-ball of the real reward according to some l_p norm.\n\nThe case where this approach gives the more insightful results are for l_2 and l_1 norms, where the authors show remarkable levels of characterization of the solution set, allowing the agent to recover a optimal-in-class policy (i.e. among all plausible policies induced by the epsilon ball) . This is achieved by characterizing the \"plausible\" policies in terms of KKT conditions on the occupancy measure of the policies and the perturbed reward, and then taking a maximum over this conservative set.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall I think the paper is comfortably above the acceptance threshold, but there is still clear room for more polish. \n\nFrom the two main weaknesses:\n- The authors should address which of these results can be extended to large or continuous state-spaces, and how hard such an extension would be.\n- The authors should address the problem of the sub-optimality gap of the defensive/robust policy. Proving rigorous results quantifying this gap would be an interesting contribution on its own, but at least a discussion on how much the adversary can exploit the defensive mechanism to induce sub-optimal policies should be discussed.\n\nFor the minor weaknesses:\n- Clarify/rigorously prove the comment on page 6\n- Discuss better how $\\epsilon_{\\mathcal{D}}$ should be chosen in practice, and highlight the trade-offs of over vs underestimation.", "broader_impact_concerns": "Overall the paper covers topic related to safety in RL, which has the potential to be a sensitive topic. However due to the highly theoretical nature of the contribution my concerns of real-world unethical use of these results are minimal.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KcVS5H13oS", "reviewer": "Reviewer_tuvE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n  - The paper proposes a framework for adversarial attacks.\n  - There are a number of theoretical results around the proposed framework.\n  - Theorem 5.1 reframes the problem in a way that can be solved with convex optimization methods.\n\nWeaknesses:\n  - Some of the proofs are unclear (see requested changes).\n  - It is hard for the reader to really grasp how the described problem is realistic at the moment (see requested changes).\n  - (Not relevant for TMLR guidelines). I have a hard time picturing how this problem formulation can scale to non-trivial environments where pre-computing occupancy measures for $|S| \\times |A|$ is computationally unfeasible. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a theoretical framework for adversarial attack of the reward function, where the attack is made at training time, and modifies the reward function so that the optimal policy becomes a target policy. The goal of the defender, who knows that the attacker chose a reward function that minimizes a cost from a known class of functions, is to find the best policy for the worst original reward function possible.\n\nThe paper makes a number of theoretical contributions, including an explicit way of deriving the best response policy in Theorem 5.1 for a specific cost. The are some experiments that validate the theoretical contributions.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It took me some time to realize what the problem statement was, and I strongly suggest the authors to work on the wording to facilitate the understanding of e.g. what (P2a) is. If I understand correctly, (P2a) can be seen as the following:\n  - for all existing (deterministic) policy there are a collection of rewards that make this policy optimal (this is probably not true since it depends on the dynamics of the MDP you are considering, but let's assume it is true),\n  - for each target policy, the attacker will pick the reward function that minimizes a cost out of all the compatible reward functions,\n  - as a strategy, the defender wants to pick the policy that will maximize the minimum performance in terms of all the rewards that the attacker could have picked.\n\n\nOn the definition of P1: I am bit surprised by the feasibility results mentioned by the authors since if the attack parameter is positive a solution does not necessarily exist. For example, think of an MDP where the dynamics are independent from the actions taken. In this setup, all policies are optimal and have the same value and therefore no single policy can dominate another one with a margin.\n\n\nI believe that Theorem 4.3. is probably true but the proof seems erroneous at the moment. \n$$\\rho^{R, \\pi} = \\pi(a_1) + x(\\\\pi(a_2) - \\pi(a_1) - \\pi(a_3) - pi(a_4)) = \\pi(a_1) + x(\\\\pi(a_2) - (1 - \\pi(a_2))) = \\pi(a_1) + 2x(\\\\pi(a_2) - 0.5)$$\nTherefore, taking any policy with $\\pi(a_2)=0.5$ is enough to bound the score.\n\n\nTheorem 4.4 is central to the paper, as it is the base for the proof of Theorem 5.1. However, I find the proof to be a hand wavy at the moment. Please expand on the current version of the proof. For example, I find it surprising that \"the only constraint in (P1’) affected by the value of $\\tilde{R}(\\tilde{s}, \\tilde{a})$ is the constraint in $\\tilde{s}, \\tilde{a}$. If a reward function is modified in a single state action, the value function (or the score) is modified for more than this single state because of the dynamics in the MDP. Even if this turns out to be true, the justification is not convincing at the moment.\n\n\nYou mention that your method is computationally tractable. Please provide the computational complexity of your method (from a back-of-the-envelope calculation, it seems to be $O(|S|^4|A|^4)$ only to define the constraints.\n\n\nIn the experimental section, make sure that you mention using a solver for solving the convex optimization problem defined in Theorem 5.1 (it is understandable but it could be made clearer), and please provide some discussion around what the policy $\\pi^\\mathcal{D}$ turns out to be (qualitatively) for the two environments.\n\n\nNot crucial but nice to have: maybe elaborate on the connection between (P1’) and (P1), which seems to be related to the line of work on policy iteration by using a simplex like method: \\\n“On the complexity of solving Markov decision problems.” Littman et al. 1995 \\\n“The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate.” Ye 2011\n", "broader_impact_concerns": "No broader impact concerns, this is a theoretical RL paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors are making different sets of assumptions (mainly about the level of awareness of the agents wrt the attacks) and derive a formal description of attacks in the RL setting, using results from the statistical robustness literature. From this, they either provide a robust policy or a result of impossibility from analytical reasoning. This is a nice framework for understanding attacks and whenever a robust solution can be found. It brings some novel perspective on the problem. 

The work is mainly limited to the discrete setting with reasonably small state and action spaces. The dynamics of the environment has to be fully known by the agent and information about the attacks as well. This is a quite limited setting but the authors provided enough evidence that this could be extended so that the reviewers are confident. 

The main issues were about the clarity of the presentation and of the setting definition. The author addressed these issues in the comments and a revised version. 
Decision: Accept (poster)