Policy Poisoning in Batch Reinforcement Learning and Control
Yuzhe Ma

Xuezhou Zhang

Wen Sun ∗∗Microsoft Research New York

University of Wisconsin–Madison

Markov Decision Process (MDP)

Policy Poisoning on Tabular Certainty Equivalence (TCE)A Markov Decision Process (MDP) is deﬁned as a tuple (S, A, P, R, γ):
S is the state space
A is the action space
P : S × A → ∆S is the transition kernel
R : S × A → R is the reward functionγ ∈ [0, 1) is the discounting factor.

Step 1 of TCE: P̂ (s0 | s, a) =|Ts,a| 001 st = s ,t∈Ts,a1|Ts,a|t∈Ts,ar∈RT ,R̂,Q∈R|S|×|A|s.t.

a0∈A

Step 1 of LQR:

kr − r0kα

T −11X(Â, B̂) ∈ arg min
kAst + Bat − st+1k22(A,B) 2t=0R̂(s, a) =t=0

1

X

|Ts,a|rtt∈Ts,aX



0P̂ s |s, a Q s0, π †(s0) , ∀s, ∀as0

Optimal policy: âτ = π̂(sτ ) = Ksτ + k, where
−1
K = −γ R̂ + γ B̂ >X B̂
B̂ >X Â,



X = γ Â>X Â − γ 2Â>X B̂ R̂ + γ B̂ >X B̂

0AB̂ >X Â + Q̂,Instantiating attack on LQR:

B
0+1kr − r0kα

min+1r,Q̂,R̂,q̂,ĉ,X0,x(a) A toy MDP with two states.

s.t.

stay move
A 10
9B 10
9(b) Original Q values.

stay move
A 910B 9
10Policy Poisoning: Threat Model=−1− γ R̂ + γ B̂ >X B̂
B̂ >X Â = K †−1− γ R̂ + γ B̂ >X B̂
B̂ >x = k †−1X = γ Â>X Â − γ 2Â>X B̂ R̂ + γ B̂ >X B̂
B̂ >X Â + Q̂x = q̂ + γ(Â + B̂K †)>x(Q̂, R̂, q̂, ĉ) =(d) Trajectory for the Q values of state
A during value iteration.

(c) Poisoned Q values.

Figure 1. Poisoning a two-state MDP

Available actions of the attacker. The attacker is allowed to arbitrarily modify the rewards r0 =(r00, ..., rT0 −1) in D0 into r = (r0, ..., rT −1).
Attacker’s goals. The attacker has a pre-speciﬁed target policy π †. The attack goals are to (1)force the learner to learn π †, (2) minimize attack cost kr − r0kα under an α-norm chosen by the−1and x satisﬁes x = q̂ + γ(Â + B̂K)>x.

Experimental results:

τ =0Knowledge of the attacker. The attacker has access to the original training set D0(st, at, rt0, s0t)t=0:T −1. The attacker knows the model-based RL learner’s algorithm.

k = −γ(R̂ + γ B̂ >X B̂)−1B̂ >x.

X  0 satisﬁes Algebraic Riccati Equation:

Q(s, π †(s)) ≥ Q(s, a) + , ∀s ∈ S, ∀a 6= π †(s).

Step 2. The learner ﬁnds the optimal policy π̂ that maximizes the expected discounted cumulative
reward on the estimated environment M̂ , i.e.,∞Xπ̂ ∈ arg max EP̂
γ τ R̂(sτ , π(sτ )),arg min

TX−1(Q0,RI,q,c) t=0

2
1 >st Qst + q >st + a>t Rat + c + rt .
2
2

Experimental results:-0.015+0.262+2.139-0.005-0.115 G1 -0.115

G2G-0.040-0.115+0.005+0.238-0.221-0.246+0.464+0.029-0.008+0.032-0.274-0.044-0.304+0.009-0.043 S+0.515-0.006-0.338+0.036+0.075+0.015-0.010A Uniﬁed Formulation of Policy Poisoning-0.004-0.004-0.200attacker.

+0.088+0.080+0.008-0.013-0.005-0.016+0.068-0.032-0.015-0.007+0.572+0.020-0.376-0.572-0.515-0.464-0.417+0.012-0.009We give a uniﬁed framework for policy poisoning based on bi-level optimization:+0.012S+0.007-0.012+0.004-0.006-0.015-0.014+0.002-0.018-0.003-0.018-0.020-0.011-0.012-0.013

α(a) Clean and poisoned vehicle trajectory.

(b) Clean and poisoned rewards.

Figure 3. Poisoning a vehicle running LQR in 4D state space.

r,R̂R

The cost function is L(s, a) = 12 s>Qs + q >s + a>Ra + c.

1X 1 >
2.
(Q̂, R̂, q̂, ĉ) =arg min
k st Qst + q >st + a>
Ra+c+rkttt
222(Q0,RI,q,c)Q(s, a) = R̂(s, a) + γ

Step 1. The learner estimates an MDP M̂ = (S, A, P̂ , R̂, γ) from a training set D.
PT −1
Maximum likelihood estimate for the transition kernel: P̂ ∈ arg maxP t=0 log P (s0t|st, at).
PT −1
Least-squares estimate for the reward function: R̂ = arg minR t=0 (rt − R(st, at))2.

R̂ = arg min

st+1 = Ast + Bat + wt, ∀t ≥ 0,T −1

Model-based Batch Reinforcement Learner

s.t.

rt.

Instantiating attack on TCE:

The optimal policy is π ∗(s) ∈ arg maxa∈A Q∗(s, a).

min

The linear dynamical system isXQ(π †) = {Q : Q(s, π †(s)) ≥ Q(s, a) + , ∀s ∈ S, ∀a 6= π †(s)}.

minThe optimal value function is characterized by the Bellman optimality equation:X∗
Q (s, a) = R(s, a) + γ
P (s0|s, a) max Q∗(s0, a0).

kr − r0kR̂(s, a) =Policy Poisoning on Linear Quadratic Regulator (LQR)

Deﬁnition. The set of -robust Q functions induced by a target policy π † is the polytope

τ =0π:S7→A1

X

Attack Goal: Q(s, π †(s)) > Q(s, a), ∀s ∈ S, ∀a 6= π †(s).

The learning goal in MDP is to ﬁnd a policy π that maximizes the cumulative discounted reward:∞
XQπ (s, a) = E[γ τ R(sτ , aτ ) | s0 = s, a0 = a, π]

s0∈SXiaojin Zhu

TX−1G(rt − R(st, at))2t=0{π †} = arg max EP̂
π:S7→A∞
X:2:−10(a) Single terminal state G.

:−1G1:1

G2:2:−1(b) Two terminal states G1 and G2.

Figure 2. Poisoning TCE in grid-world tasks.

γ τ R̂(sτ , π(sτ )).

τ =0The singleton set {π †} on the LHS of (1) ensures that the target policy is learned uniquely.

Theorem. Assume α ≥ 1. Let r∗, R̂∗ and Q∗ be an optimal solution to the attack, then1α111∗0(1 − γ)∆() min |Ts,a|≤ kr − r kα ≤ (1 + γ)∆()T α .
s,a22The 33rd Conference on Neural Information Processing Systems (NeurIPS) 2019, Vancouver, CanadaConclusion
We presented a policy poisoning framework against batch reinforcement learning and control.
We showed the attack problem can be formulated as convex optimization.
We provided theoretical analysis on attack feasibility and cost.
We empirically show the attack is both effective and efﬁcient.

https://nips.cc/Conferences/2019