PaperlayerView exact revision on arXiv

Source-linked AI summary

Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning

Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, Adish Singla

arXiv:2003.12909v2cs.LGcs.AIcs.CRstat.ML

TL;DR

Reinforcement-learning poisoning is a security concern, but attacks on RL agents and their different settings warrant investigation. This paper develops stealthy reward- or transition-poisoning attacks for offline planning and online learning. Its results show that attackers can teach target policies under mild conditions, while experimental evaluation does not establish which learning algorithms are most vulnerable.

  • Problem

    The paper investigates training-time poisoning of reinforcement-learning agents, a security concern as RL is used in critical applications.

    Source: §1 · p. 1

  • Method

    The authors formulate stealthy attacks that manipulate rewards or transition dynamics for average-reward agents in offline planning and online regret-minimization settings.

    Source: §1.1 · pp. 1–2

  • Results

    The results show that attackers can teach victims to execute target policies at minimal cost, with success conditions and feasibility depending on the attack setting.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    Environment poisoning presents a security threat to reinforcement-learning agents, including through attacks on transition dynamics.

    Source: §1.1 · p. 1, §7 · p. 9

    The experiments do not identify which learning-algorithm types are most vulnerable; evaluation across diverse state-of-the-art algorithms could help address this.

    Source: §7 · p. 9

Abstract

from arXiv · show

We study a security threat to reinforcement learning where an attacker poisons the learning environment to force the agent into executing a target policy chosen by the attacker. As a victim, we consider RL agents whose objective is to find a policy that maximizes average reward in undiscounted infinite-horizon problem settings. The attacker can manipulate the rewards or the transition dynamics in the learning environment at training-time and is interested in doing so in a stealthy manner. We propose an optimization framework for finding an \emph{optimal stealthy attack} for different measures of attack cost. We provide sufficient technical conditions under which the attack is feasible and provide lower/upper bounds on the attack cost. We instantiate our attacks in two settings: (i) an \emph{offline} setting where the agent is doing planning in the poisoned environment, and (ii) an \emph{online} setting where the agent is learning a policy using a regret-minimization framework with poisoned feedback. Our results show that the attacker can easily succeed in teaching any target policy to the victim under mild conditions and highlight a significant security threat to reinforcement learning agents in practice.

1. Introduction

The paper examines training-time poisoning as a security threat to reinforcement learning and develops attacks that teach agents attacker-chosen policies. It extends prior RL poisoning work to transition dynamics and average-reward agents, with attacks formulated for both offline planning and online learning.

1.1. Overview of our Results and Contributions

  • The paper’s environment-poisoning scope includes manipulating either rewards or transition dynamics, beyond prior RL poisoning work focused on rewards alone.The introduction situates poisoning attacks as a security concern for RL used in critical applications.Source: §1.1 · p. 1, §1 · p. 1
  • The framework studies poisoning transition dynamics as well as rewards, and gives sufficient success conditions and lower and upper bounds on attack cost.Transition poisoning is more challenging than reward poisoning and may not always be feasible.Source: §1.1 · pp. 1–2
  • The analysis targets average-reward agents in undiscounted infinite-horizon settings, where the absence of the usual discount-factor contraction property creates technical challenges.The bounds use measures including the Hajnal measure of the transition kernel and the diameter of the target-policy Markov chain.Source: §1.1 · p. 2
  • The attacks cover offline planning and online learning, using attack-cost measures suited to each setting.Offline work commonly measures manipulation with the ℓ∞-norm; for online learning, cumulative cost over time, such as the ℓ1-norm, is more relevant.Source: §1.1 · p. 2
  • The attacks can teach the victim to execute the desired target policy at minimal cost, according to the authors’ results.The work also reports numerical simulations supporting its theoretical statements.Source: §1.1 · p. 2

2. Environment and RL Agent

The paper models the environment as an MDP and studies agents that maximize average reward in undiscounted infinite-horizon settings. It considers both offline planning with a known MDP and online learning with unknown dynamics and rewards.

2.1. Environment, Policy, and Optimality Criteria

  • An MDP is specified by state and action spaces, a reward function, and transition dynamics; policies map states to actions.The paper assumes ergodicity, so each policy has a stationary distribution with positive probability for every state.Source: §2.1 · p. 2
  • The paper uses average-reward optimality for undiscounted infinite-horizon tasks, including settings with cyclic tasks or no absorbing states.Under ergodicity, average reward is computed using a policy’s stationary state distribution and rewards.Source: §2.1 · p. 2
  • A policy is ε-robust optimal when its average reward exceeds every other deterministic policy’s average reward by at least ε.The paper also defines α from transition probabilities; 1−α is equivalent to the Hajnal measure of the transition kernel.Source: §2.1 · p. 2

2.2. RL Agent

  • In the offline setting, the agent receives an MDP and finds a deterministic optimal policy using planning algorithms such as value iteration.Figure 1(a) depicts environment poisoning followed by planning based on Dynamic Programming.Source: §2.2 · p. 3, Figure 1 · p. 3
  • In the online setting, the agent does not know the MDP, chooses actions from past observations, and receives rewards and next states as feedback.The paper considers regret-minimizing learners with sublinear expected regret, including UCRL and posterior-sampling algorithms.Source: §2.2 · p. 3

3. Attack Models and Problem Formulation

The attack models specify how an adversary teaches a target policy by poisoning rewards or transition dynamics while seeking low-cost, stealthy manipulation. Offline attacks alter the MDP before planning; online attacks alter feedback during learning.

3. Attack Models and Problem Formulation

  • The attacker knows the original MDP and targets a chosen policy, but need not know the learner’s algorithm or internal parameters.The attacker seeks a stealthy attack with minimal cost to avoid detection.Source: §3 · p. 3

3.1. Attack Against an Offline Planning Agent

  • For offline planning, the attacker poisons the MDP so the target policy is ε-robust optimal, outperforming every other policy by a margin ε.The poisoned MDP is then used by the agent to find an optimal policy.Source: §3.1 · p. 3
  • Offline reward and transition attacks are measured using ℓp-norms of changes to rewards or transition distributions.For transition poisoning, the per-state-action difference is the ℓ1-norm between the original and poisoned distributions, then aggregated across state-action pairs.Source: §3.1 · pp. 3–4
  • The studied offline attacks poison rewards only or transition dynamics only; an attack changing both requires appropriately combining their costs.The text also notes that some offline attacks poison the training data used to learn MDP parameters.Source: §3.1 · p. 3

3.2. Attack Against an Online Learning Agent

  • Online attacks manipulate the current reward and next-state feedback, using poisoned rewards and transition distributions for the state-action pair at each time step.Unlike the offline setting, the attacker intervenes as the agent interacts with the environment.Source: §3.2 · p. 4
  • The online objective is to make the fraction of actions that differ from the target policy vanish over the time horizon.Equivalently, the total number of mismatching actions must be o(T).Source: §3.2 · p. 4
  • Online attack cost is averaged over time, with ℓp-norms applied to the sequence of per-step costs; cumulative ℓ1 cost is more relevant online than offline ℓ∞ cost.The definitions distinguish reward-poisoning and dynamics-poisoning costs.Source: §3.2 · p. 4

4. Attacks in Offline Setting

The offline attacks seek minimal changes to the MDP that make the attacker’s target policy optimal. Reward poisoning yields a tractable, always-feasible optimization, whereas transition poisoning is generally non-convex and is feasible only under sufficient conditions.

4.1. Overview of the Approach

  • Checking the target policy against its neighbor policies reduces exponentially many optimality constraints to a smaller set of state-action comparisons.A policy is ϵ-robust optimal exactly when its average reward exceeds each neighbor policy’s by at least ϵ.Source: §4.1 · p. 4

4.2. Attacks in Offline Setting via Poisoning Rewards

  • The reward-poisoning problem is a tractable convex program with linear constraints, is always feasible, and provides lower and upper bounds on attack cost.The offline attack changes rewards while retaining the original transition dynamics and stationary distributions.Source: §4.2 · p. 5

4.3. Attacks in Offline Setting via Poisoning Dynamics

  • Transition poisoning is generally non-convex, and its constraints may be infeasible when rewards are constant or nearly constant.The optimization keeps the reward function fixed; its transition-probability constraints include a regularity parameter δ>0 to ensure the new MDP is ergodic.Source: §4.3 · p. 5
  • A sufficient condition makes the transition-poisoning problem feasible and bounds its cost; the condition requires enough future prospect to overcome the target policy’s initial disadvantage.The comparison is between the target policy’s future value and the myopic reward disadvantage relative to a neighbor action.Source: §4.3 · p. 6
  • The constructive upper bound shifts transitions for disadvantaged state-action pairs toward a sink state of low target-policy value, without changing transitions under the target policy.The sink is selected to minimize the target policy’s value function.Source: §4.3 · p. 6

5. Attacks in Online Setting

For online learning, the attacker supplies feedback from a poisoned MDP in which the target policy is ϵ-robust optimal, using the learner’s bounded regret to limit deviations. When the attack preserves rewards and transitions for target-policy actions, both average mismatch and average attack cost decrease over time for learners with sublinear expected regret.

5.1. Overview of the Approach

  • Sampling feedback from an ergodic MDP where the target policy is ϵ-robust optimal bounds the learner’s average mismatch by a quantity based on expected regret.The result applies to the poisoned MDPs constructed by the offline reward- and transition-poisoning optimizations.Source: §5.1 · p. 6
  • To avoid non-diminishing average attack cost, the online attack preserves rewards and transitions for state-action pairs belonging to the target policy.Otherwise, a learner with sublinear expected regret can still incur Ω(1) average cost when it follows the target policy.Source: §5.1 · pp. 6–7

5.2. Attacks in Online Setting via Poisoning Rewards

  • For reward poisoning, the optimal modified reward is R(s,a)−χπ†_ϵ(s,a), and the theorem bounds average mismatch and average cost using the learner’s expected regret.The modification leaves rewards on target-policy actions unchanged because χπ†_ϵ(s,π†(s))=0.Source: §5.2 · p. 7

5.3. Attacks in Online Setting via Poisoning Dynamics

  • For transition poisoning, the added target-action constraints yield a tractable convex program under Theorem 2’s sufficient condition, and the resulting attack bounds mismatch and cost.The program has a structure that can be solved through |S|·(|A|−1) smaller convex problems.Source: §5.3 · p. 7
  • With sublinear expected regret, both average mismatch and average attack cost are expected to decrease over time.The conclusion follows from the reward- and transition-poisoning results.Source: §5.3 · p. 7

6. Numerical Simulations

Simulations examine reward and dynamics poisoning in offline planning and online learning. Online non-target-only attacks achieve target-policy following at average cost o(1), while offline dynamics attacks can become infeasible as the required margin increases.

6. Numerical Simulations

  • Simulations use a four-state, two-action MDP, varying R(s0, .) and ε offline and fixing R(s0, .) = −2.5 and ε = 0.1 online.Offline results average 10 runs; online results average 20 runs and use UCRL without requiring the attacker to know the learner’s algorithm.Source: §6 · p. 8, §6.1 · p. 8, §6.2 · p. 8

6.1. Attacks in the Offline Setting: Setup and Results

  • 3.3010s at |S|=4 and 157.2484s at |S|=100 are P2 runtimes, versus 0.0339s and 1.1705s for P4.The 100-state MDP retains the linear-chain structure of the four-state environment.Source: §6.1 · p. 8
  • Reward attacks remain feasible as ε margin rises, but dynamics attacks become infeasible above 0.85; generic attacks can cost less than non-target-only attacks.The offline comparison concerns RATTACK/DATTACK versus NT-RATTACK/NT-DATTACK.Source: §6.1 · p. 8, Figure 3 · p. 9

6.2. Attacks in the Online Setting: Setup and Results

  • Non-target-only online attacks force target-policy following at average cost o(1), whereas RATTACK and DATTACK incur linear cumulative cost.Figure 4 reports results for reward attacks in panels a–b and dynamics attacks in panels c–d.Source: Figure 4 · p. 9, §6.2 · p. 9

7. Conclusion

The conclusion frames environment poisoning as a security threat and summarizes its treatment across transition manipulation, average-reward agents, and offline and online costs. It identifies extensions to attack models and goals, scalability, and evaluation across learning algorithms as future work.

7. Conclusion

  • The paper develops environment poisoning attacks across transition dynamics, average-reward undiscounted infinite-horizon agents, and offline planning and online learning costs.The stated threat is an attacker forcing an RL agent to execute a target policy.Source: §7 · p. 9
  • Future directions include simultaneous reward-and-transition attacks, partially specified target policies, less MDP knowledge, larger or continuous environments, and transfer-learning or multi-agent RL.The paper notes that relaxing the attacker’s MDP-knowledge assumption could lead to more robust strategies.Source: §7 · p. 9
  • The experiments do not identify which learning algorithms are most vulnerable, and broader algorithm evaluation could guide defensive strategies.Source: §7 · p. 9

A. List of Appendices

B. Additional Related Work

  • The related-work appendix contrasts training-time target-policy teaching with test-time attacks and with imitation-learning approaches that use demonstrations rather than reward feedback.It also distinguishes reward shaping, which preserves the modified environment’s optimal policy while speeding convergence.Source: B. Additional Related Work · p. 12

C. Implementation Details and Additional Experiments (Section 6)

C.1. Implementation Details

  • For P2, a heuristic builds transition-kernel candidates that improve the target policy’s average reward, then P4 generates solutions and the minimum-cost solution is selected.P1, P3, and P4 use standard optimization techniques; P2 is implemented as a pool-generation and pool-solving procedure.Source: §C.1 · pp. 12–13

C.2. Additional Experiments

The appendix reports additional simulations and develops proof ingredients for offline reward attacks, from relative-value identities to a sufficient uniqueness condition.

C.2. Additional Experiments

  • The nine-state, two-action navigation environment varies R(s0, .), with 0.9 intended transitions and 0.1 random next-state sampling.Results average 10 offline runs and 20 online runs; the offline setup varies R(s0, .) and ϵ, while the online setup fixes both.Source: Figure 5 · p. 13, §C.2 · pp. 13–14
  • The additional experiments reproduce the key takeaways of Sections 6.1 and 6.2, although their cost and mismatch scales differ.Figure 6 covers offline reward and dynamics attacks; Figure 7 covers the corresponding online attacks.Source: Figure 6 · p. 13, Figure 7 · p. 13, §C.2 · p. 14

D. Background

  • Relative values, also called Q values here, follow a recurrence and satisfy Vπ(s) = Qπ(s, π(s)).The appendix says these values can be calculated by solving a set of equations.Source: D. Background · p. 14

E. Proofs for Offline Attacks: Lemma 1 (Section 4.1)

  • A policy is uniquely optimal if its average reward exceeds each one-state neighbor’s by at least ϵ > 0.The proof assumes a recurrent MDP and uses that altered policies visit the changed state with positive stationary probability.Source: E. Proofs for Offline Attacks: Lemma 1… · pp. 14–15

Proof of Lemma 1

  • The proof extends the neighbor-policy condition to all other policies by induction on Hamming distance from the target policy.It successively replaces a differing action with the target action without decreasing average reward, then applies the assumed ϵ margin.Source: Proof of Lemma 1 · p. 15

F. Proofs for Offline Attacks: Poisoning Rewards (Section 4.2)

  • Theorem 1’s proof is divided into two parts: Appendix F.1 establishes the theorem’s lower bound, while Appendix F.2 establishes its upper bound and the attack’s feasibility.Source: F. Proofs for Offline Attacks:… · p. 15

F.1. Proofs for the Lower Bound in Theorem 1

The appendix proves a lower bound for reward poisoning using span-based comparisons, then develops feasibility, upper-bound, and reformulation steps for reward and dynamics attacks.

F.1. Proofs for the Lower Bound in Theorem 1

  • The proof uses a span contraction for the average-reward operator and relates Q-value changes to reward and transition-kernel changes.The contraction factor is 1 − α; the perturbation bound combines reward differences with transition differences weighted by value magnitude.Source: §F.1 · pp. 16–17
  • The reward-attack lower-bound proof bounds the span of the target policy’s Q-value difference between the modified and original MDPs.It selects a state-action pair maximizing χπ†ϵ(s, a) and uses the robust-optimality margin in the modified MDP.Source: §F.1 · pp. 17–18

F.2. Proofs for the Upper Bound and Feasibility in Theorem 1

  • The reward attack bR = R − χπ†ϵ is feasible, and its cost supplies an upper bound because an optimal attack costs no more.The construction is a solution to (P6), whose constraints are included in (P1).Source: §F.2 · pp. 18–19

G. Proofs for Offline Attacks: Poisoning Dynamics (Section 4.3)

  • The dynamics-attack proof introduces a more constrained tractable problem to establish feasibility and support the online dynamic attacks.The appendix says this problem is also the basis for the online dynamics attacks.Source: G. Proofs for Offline Attacks:… · p. 19

G.1. More Constrained Problem and Reformulation

  • The lower bound on the deviating policy’s stationary mass is linked to the expected return time under the target policy.The appendix introduces the Markov-chain diameter as the maximum expected time to reach a state under the target policy.Source: §G.1 · pp. 19–20
  • Problems (P7) and (P8) are equivalent reformulations of the constrained dynamics-poisoning problem.The reformulation expresses the target policy’s required margin using Q-value differences and the stationary probability of the deviating state.Source: §G.1 · p. 20

G.2. Feasibility Analysis

The appendix characterizes when constrained dynamics poisoning is feasible, proves bounds using a transition-mixture attack, and discusses practical trade-offs in choosing δ.

G.2. Feasibility Analysis

  • The constrained dynamics-poisoning problem is feasible if and only if C(s, a) ≥ ϵ for every non-target action.The appendix also gives a simpler sufficient condition for feasibility of (P7).Source: §G.2 · pp. 20–21

G.3. Proof of Theorem 2

  • Theorem 2’s proof bounds attack cost using a transition mixture, while preserving the target policy’s transitions.The mixture is defined by bP(s, a, s′) = (1 − λ(s, a)) · P(s, a, s′) + λ(s, a) · Ps(s, a, s′).Source: §G.3 · pp. 22–24

G.4. Choosing δ

  • For online attacks, δ should be chosen so MDP parameters relevant to regret do not outweigh the time horizon T.For planning attacks, small δ can produce a large mixing time, making average reward a poor approximation to finite-horizon reward averages.Source: §G.4 · p. 24
  • A more detailed analysis incorporating these δ-related practical considerations is left for future work.Source: §G.4 · p. 24

H. Proofs for Online Attacks: Lemma 2 (Section 5.1)

The proof reduces the learner to an equivalent history-independent policy, then tracks action distributions and sums per-step mismatches to establish Lemma 2’s average-mismatch bound.

I. Proofs For Online Attacks: Poisoning Rewards (Section 5.2)

The reward-poisoning proof constructs a poisoned reward function that makes the target ϵ-robust optimal, then invokes Lemma 2 to bound expected average mismatches.

  • The modified reward bR = R − χπ†ϵ solves P3 and P1, making π† ϵ-robust optimal in the poisoned MDP cM.Source: §I · p. 26
  • The reward attack yields the bound E[AVGMISS(T)] ≤ K(T, cM)/T.Source: §I · p. 26
  • For p ≥ 1, the proof uses concavity of x^(1/p) and Jensen’s inequality to bound E[f(X)] by f(E[X]).Source: §I · p. 26

J. Proofs For Online Attacks: Poisoning Dynamics (Section 5.3)

The dynamics-poisoning proof uses a tractable convex program to construct a feasible attack, making the target ϵ-robust optimal in the MDP observed by the learner.

Loading 2003.12909v2…