PaperlayerView exact revision on arXiv

Source-linked AI summary

Policy Poisoning in Batch Reinforcement Learning and Control

Yuzhe Ma, Xuezhou Zhang, Wen Sun, Xiaojin Zhu

arXiv:1910.05821v2cs.LGstat.ML

TL;DR

Batch reinforcement learners and controllers can be targeted by modifying their training data so they learn an attacker-chosen policy. The paper formulates reward-based policy poisoning for TCE and LQR victims and analyzes feasibility and cost; its experiments report effective attacks, including a low-cost LQR example.

  • Problem

    The paper addresses the limited understanding of training-set poisoning against batch reinforcement learners and controllers, where an attacker seeks to alter the learned policy.

    Source: §1 · p. 1

  • Method

    The paper formulates reward modifications as a policy-poisoning optimization problem and instantiates it for tabular certainty equivalence and LQR learners.

    Source: §1 · p. 1, §4.2 · p. 6

  • Results

    The LQR attack’s total reward-change cost was ∥r − r0∥2 = 0.73 over 400 items, compared with ∥r0∥2 = 112.94, and the paper reports that attacks can force attacker-chosen policies.

    Source: §5.2 · p. 9, §6 · p. 9

  • Takeaways & Limitations

    The TCE formulation is feasible for any target policy, and reward changes alone can suffice to teach it.

    Source: §4.1 · p. 4

    For LQR, the target policy must satisfy the linear form K†s + k† and be producible by solving an LQR problem.

    Source: §4.2 · p. 5

Abstract

from arXiv · show

We study a security threat to batch reinforcement learning and control where the attacker aims to poison the learned policy. The victim is a reinforcement learner / controller which first estimates the dynamics and the rewards from a batch data set, and then solves for the optimal policy with respect to the estimates. The attacker can modify the data set slightly before learning happens, and wants to force the learner into learning a target policy chosen by the attacker. We present a unified framework for solving batch policy poisoning attacks, and instantiate the attack on two standard victims: tabular certainty equivalence learner in reinforcement learning and linear quadratic regulator in control. We show that both instantiation result in a convex optimization problem on which global optimality is guaranteed, and provide analysis on attack feasibility and attack cost. Experiments show the effectiveness of policy poisoning attacks.

1 Introduction

The paper studies training-set data poisoning against batch reinforcement learners and controllers, where the attacker seeks to make the victim learn a chosen policy by modifying rewards. It frames this threat as an underexplored extension of data poisoning to reinforcement learning and control.

1 Introduction

  • The attacker modifies training rewards to make a batch learner learn a specified target policy while minimizing the reward changes.The framework is instantiated against tabular certainty-equivalence and LQR victims.Source: §1 · p. 1
  • Training-set poisoning of reinforcement learners is little understood compared with prior work on supervised learning and multi-armed bandits.The paper notes the potential impact of a deliberately planted bad policy given RL applications in robotics and games.Source: §1 · p. 1

2 Related Work

The paper distinguishes policy poisoning from test-time attacks, reward shaping, and teaching inverse reinforcement learning. Its focus is changing the learned policy of batch RL victims through training-data manipulation.

2 Related Work

  • Test-time RL attacks perturb the perceived state while leaving the learned policy fixed; policy poisoning acts during training to change that policy.The cited test-time attack targets a particular action by altering the state perceived by an already-trained agent.Source: §2 · p. 2
  • Prior data-poisoning work addressed supervised-learning and multi-armed-bandit victims, while the paper extends the target setting to reinforcement learning.The cited prior work includes batch and online supervised learning and bandit victims.Source: §2 · p. 2
  • Reward shaping modifies rewards to speed convergence to the same optimal policy, whereas policy poisoning seeks a different policy and minimizes reward change.The two approaches therefore have different targets and optimization criteria.Source: §2 · p. 2
  • Teaching IRL and attacking are mathematically equivalent, but teaching targets specialized agents that infer rewards from demonstrations without reward labels.This paper instead targets RL agents and uses a different framework because their inputs differ.Source: §2 · p. 2

3 Preliminaries

The preliminaries describe the MDP and policy setting, then specify how a batch model-based learner estimates an environment from data and optimizes a policy against that estimate.

3 Preliminaries

  • An MDP comprises state and action spaces, a transition kernel, a reward function, and a discount factor; a policy maps states to actions.The text defines a policy’s Q function as expected discounted cumulative reward, with the optimal Q function characterized by Bellman optimality.Source: §3 · p. 2
  • A batch training item records the current state, action, reward, and next state, and the training set consists of such items.The learner estimates the transition kernel by maximum likelihood and the reward function by least squares.Source: §3 · p. 2
  • The model-based learner estimates an MDP from the batch, then chooses a policy maximizing expected discounted reward in that estimated environment.The transition estimate need not be unique, while the reward estimate is assumed unique; multiple optimal policies may exist.Source: §3 · pp. 2–3

4 Policy Poisoning

The paper formulates policy poisoning as reward modification that makes a batch learner choose an attacker-specified policy while minimizing attack cost. It develops a TCE formulation with feasibility and cost analysis, and an LQR surrogate whose convexity comes with a stricter feasible region.

4 Policy Poisoning

  • The attacker knows the learner’s estimation algorithm and can modify rewards, seeking a specified target policy at minimum α-norm reward-change cost.The framework formulates this goal as a bilevel optimization problem; transitions and actions in the dataset remain unchanged.Source: §4 · p. 3

4.1 Poisoning a Tabular Certainty Equivalence (TCE) Victim

  • For TCE, a positive margin defines a robust target Q polytope in which the chosen policy is uniquely optimal.The margin-based formulation replaces the strict target-policy inequality with a stronger condition that yields a closed feasible subset.Source: §4.1 · p. 4
  • The TCE attack formulation is a convex program with linear constraints for α ≥ 1, and it is feasible for every target policy.Because the margin formulation is stricter than the original, its optimum may have a larger objective value; changing rewards without changing states, actions, or next states suffices.Source: §4.1 · p. 4
  • TCE attack-cost bounds scale linearly with ∆(ε), which measures the target policy’s suboptimality on the clean estimated MDP up to the margin.The clean-data quantity lets an attacker estimate cost before solving the attack problem.Source: §4.1 · p. 4

4.2 Poisoning a Linear Quadratic Regulator (LQR) Victim

  • For LQR, a target policy must have the form K†s + k† and must be producible by solving an LQR problem.The attacker therefore selects a target policy through an attacker-defined LQR loss function to ensure feasibility.Source: §4.2 · pp. 5–6
  • The LQR surrogate pulls positive-semidefinite constraints out of the lower-level optimization to obtain convexity, but its smaller feasible region can yield a suboptimal solution.The attacker changes rewards, not the estimated transition matrices.Source: §4.2 · p. 6

5 Experiments

The experiments demonstrate reward-poisoning attacks against TCE and LQR victims, including target-policy outcomes with low-cost and sparse reward changes.

5.1 Policy Poisoning Attack on TCE Victim

  • In the two-state MDP, TCE’s poisoned Q values reach the ε-robust target polytope boundary, making move optimal at cost ∥r −r0∥2 = 2.Clean-data Q values converge below the policy boundary, where stay is optimal.Source: §5.1 · pp. 6–7, Figure 1 · p. 7
  • Reward shaping preserves the original optimal policy while making value iteration converge in one iteration; it does not produce a different policy.The shaped Q trajectory remains below the policy boundary.Source: §5.1 · p. 7
  • In two grid-world tasks, poisoned TCE follows each red target path at costs ∥r −r0∥2 ≈2.64 vs ∥r0∥2 = 21.61 and ≈0.38 vs 11.09.The second task targets the longer path to G2 rather than the clean optimal path to G1.Source: Figure 2 · p. 7, §5.1 · p. 8

5.2 Policy Poisoning Attack on LQR Victim

  • LQR learns the exact target policy with reward-edit cost ∥r −r0∥2 = 0.73, compared with ∥r0∥2 = 112.94.The poisoned vehicle trajectory drives it close to the target destination.Source: Figure 3 · p. 8, §5.2 · p. 9
  • For the LQR example, the attacker constructs a target policy using a target-state loss and the learner’s estimated dynamics.The target state is s† = (0, 1, 0, 0), and the attacker solves the Riccati equation using estimated A and B.Source: §5.2 · p. 9
  • For both TCE and LQR, setting attack cost norm α = 1 yields sparse attacks, meaning only a small fraction of the batch data needs to be poisoned.Source: §5.2 · p. 9

6 Conclusion

The paper presents a policy-poisoning framework for batch reinforcement learning and control, formulates the attack as convex optimization, and reports that it can induce attacker-chosen policies at small cost.

6 Conclusion

  • The paper presents a unified policy-poisoning framework for batch reinforcement learning and control.It studies attacks that force the learner into an attacker-chosen target policy.Source: §6 · p. 9
  • The attack problem is formulated as convex optimization, with theoretical analysis of feasibility and attack cost.Source: §6 · p. 9
  • Experiments show that attacks can force the learner into an attacker-chosen target policy while incurring only a small attack cost.Source: §6 · p. 9

A Proof of Proposition 1

The proof establishes feasibility for every target policy by constructing Q values and using the reward–Q correspondence induced by the Bellman optimality equation.

A Proof of Proposition 1

  • Because γ < 1 makes the Bellman operator a contraction, each reward function maps to a unique Q table, supporting the one-to-one correspondence.Source: A Proof of Proposition 1 · p. 12
  • The attack problem is always feasible for any target policy π†.Source: A Proof of Proposition 1 · p. 12
  • The proof constructs Q values satisfying the attack constraint, then uses the reward–Q bijection induced by Bellman optimality to obtain a feasible reward function.The construction sets max_a Q(s, a) = ε for every state.Source: A Proof of Proposition 1 · p. 12

B Proof of Theorem 2

The proof establishes that an optimal attack can use a shared reward shift for each state-action pair, then constructs a feasible target-policy attack and bounds its cost. It also identifies when the clean data require no attack.

B Proof of Theorem 2

  • Lemma 5 supplies the proof's smoothing step: with equal element sums and differences confined to I, the smoother vector has smaller ℓα norm for α ≥ 1.Source: B Proof of Theorem 2 · p. 12
  • An optimal solution can shift every clean reward for a state-action pair by a shared ψ(s, a), although other optimal solutions may exist.All optimal solutions have the same attack cost, so considering one with this form suffices for bounding that cost.Source: B Proof of Theorem 2 · p. 13
  • Lemma 7 bounds the action-value change for two MDPs with shared transitions in terms of the difference between their reward functions.The lemma compares Q functions satisfying Bellman optimality under the two reward functions.Source: B Proof of Theorem 2 · p. 14
  • The proof constructs Q′ so the target action exceeds each alternative by ε, induces rewards satisfying Bellman optimality, and obtains a feasible attack that upper-bounds optimal cost.Source: B Proof of Theorem 2 · p. 15
  • If the clean Q values already place the target action at least ε above every alternative in every state, the optimal attack leaves the data unchanged.Source: B Proof of Theorem 2 · p. 15

C Convex Surrogate for LQR Attack Optimization

The LQR attack is replaced by a stricter convex surrogate, which can be solved to global optimality under stated feasibility conditions. The section also characterizes when the learner's cost estimate is unique.

C Convex Surrogate for LQR Attack Optimization

  • The LQR surrogate is convex and can be solved to global optimality, but its feasible set is a subset of the original attack problem's, so its solution may be sub-optimal for that original problem.Source: C Convex Surrogate for LQR Attack… · p. 17
  • The surrogate is feasible and attains an optimum when the target policy is induced by the learner's estimated dynamics and the attacker-defined loss, with R† ⪰ εI.Source: C Convex Surrogate for LQR Attack… · p. 18

D Conditions for The LQR Learner to Have Unique Estimate

  • The learner's estimate is unique when the projection onto Ψ(D) is unique and the linear system for its cost parameters has a unique solution.The latter condition holds exactly when the design matrix has full column rank.Source: D Conditions for The LQR Learner to… · p. 19

E Sparse Attacks on TCE and LQR

The α = 1 attacks sparsely modify rewards in both MDP and LQR settings, with low reported costs relative to the clean rewards.

E Sparse Attacks on TCE and LQR

  • MDP experiment 3 changes 12 of 124 state-action rewards, at cost 1.05 versus clean-reward norm 121.The reward modifications are shown in Figure 5, which is not among the supplied passages for this section.Source: E Sparse Attacks on TCE and LQR · p. 19
  • MDP experiment 2 changes only terminal G’s “go up” reward by 3.27, at cost 3.27 versus clean-reward norm 105.The higher reward makes G a sweet spot; the agent takes the red route to reach it earlier, accepting two discounted −10 rewards.Source: E Sparse Attacks on TCE and LQR · p. 19, Figure 4 · p. 20
  • The LQR attack changes 10 of 400 rewards at cost 5.44, versus clean-reward norm 2088.57, and is reported as effective as the dense 2-norm attack.The clean and poisoned vehicle trajectories and per-time-step reward changes are plotted in Figure 6.Source: E Sparse Attacks on TCE and LQR · p. 19, Figure 6 · p. 20

F Derivation of Discounted Discrete-time Algebraic Riccati Equation

This section derives the discounted discrete-time algebraic Riccati equation for a noiseless setting and notes that the derivation generalizes to noise.

F Derivation of Discounted Discrete-time Algebraic Riccati Equation

  • The derivation considers the noiseless case and is stated to generalize readily to the noisy case.The section identifies its subject as the discounted discrete-time algebraic Riccati equation.Source: F Derivation of Discounted… · p. 20
  • When q = 0 and c = 0, the general quadratic-loss setting recovers classic LQR.The loss is described as a general quadratic function of s.Source: F Derivation of Discounted… · p. 21
  • The dynamic-programming derivation assumes a quadratic value function, substitutes the action minimizer into Q(s, a), and regroups terms to obtain a recursion.Source: F Derivation of Discounted… · pp. 21–22
Loading 1910.05821v2…