Adaptive Reward-Poisoning Attacks against Reinforcement Learning

Xuezhou Zhang; Yuzhe Ma; Adish Singla; Xiaojin Zhu

Source-linked AI summary

Adaptive Reward-Poisoning Attacks against Reinforcement Learning

Xuezhou Zhang, Yuzhe Ma, Adish Singla, Xiaojin Zhu

arXiv:2003.12613v2Mar 27, 2020cs.LGcs.AIcs.CRstat.ML

TL;DR

The paper asks when reward poisoning can force an RL agent toward a nefarious policy and how efficiently such attacks can operate. It formalizes attack thresholds and adaptive strategies, showing that adaptive attacks can achieve target policies in polynomially many steps under stated conditions, with empirical effectiveness demonstrated using deep RL techniques.

Problem
Reward poisoning lets an attacker perturb environmental rewards to manipulate an RL agent’s learned policy, but the feasibility and efficiency of such attacks require formal characterization.
Method
The paper analyzes bounded reward perturbations, distinguishes attack feasibility thresholds, and constructs a Fast Adaptive Attack that uses the agent’s learning state.
Results
Under mild conditions, the Fast Adaptive Attack achieves the target policy in steps polynomial in |S|, while the paper also reports effective attacks using deep RL techniques.
Takeaways & Limitations
Reward-poisoning attacks can be infeasible below a lower threshold, while sufficiently large perturbations can enable policy manipulation; adaptive attacks improve the stated attack-cost rate.
Takeaways & Limitations
The theoretical analysis focuses on finite MDPs and standard Q-learning, with extensions to agents such as DQN presented separately.

Abstract

from arXiv · show

In reward-poisoning attacks against reinforcement learning (RL), an attacker can perturb the environment reward $r_t$ into $r_t+δ_t$ at each step, with the goal of forcing the RL agent to learn a nefarious policy. We categorize such attacks by the infinity-norm constraint on $δ_t$: We provide a lower threshold below which reward-poisoning attack is infeasible and RL is certified to be safe; we provide a corresponding upper threshold above which the attack is feasible. Feasible attacks can be further categorized as non-adaptive where $δ_t$ depends only on $(s_t,a_t, s_{t+1})$, or adaptive where $δ_t$ depends further on the RL agent's learning process at time $t$. Non-adaptive attacks have been the focus of prior works. However, we show that under mild conditions, adaptive attacks can achieve the nefarious policy in steps polynomial in state-space size $|S|$, whereas non-adaptive attacks require exponential steps. We provide a constructive proof that a Fast Adaptive Attack strategy achieves the polynomial rate. Finally, we show that empirically an attacker can find effective reward-poisoning attacks using state-of-the-art deep RL techniques.

1. Introduction

The paper studies training-time reward poisoning in RL, where an attacker manipulates feedback or rewards to drive an agent toward a nefarious target policy. It characterizes attack conditions and costs, and reports empirical effectiveness using deep RL techniques.

Motivation: Reward signals derived from user feedback, such as clicks, purchases, sentiment, or conversation length, can be manipulated to influence RL agents.The introduction uses conversational AI and the Tay chatbot as motivating examples of this security threat.
Problem formulation: The attacker perturbs each environmental reward r_t into r_t + δ_t to drive the learned policy π_t toward a target policy π†.This is framed as a training-time attack on the agent’s learning process.
Running example: In the chain-MDP example, the optimal policy moves right, whereas the attacker’s target policy makes the agent move left into the wall at the left-most state.The example has five states, movement rewards of -0.1, and an absorbing goal reward of 1.
Contributions: The paper characterizes conditions guaranteeing attack failure or feasibility and derives upper bounds on attack cost.These results organize reward-poisoning attacks by the perturbation magnitude constraint.
Contributions: Effective reward-poisoning attacks can also be found empirically using deep reinforcement learning techniques.

2. Related Work

Prior work studies adversarial manipulation of fixed policies, bandit rewards, batch RL data, and restricted reward poisoning. This paper focuses on online training-time attacks whose perturbations can depend on the victim’s learning process.

Test-time attacks: Test-time attacks manipulate perceived states to induce undesired actions, but they do not modify the pre-trained policy itself.Training-time attacks additionally target the policy as it continues learning.
Reward poisoning: Bandit studies show that adversarially perturbed rewards can make standard algorithms select suboptimal arms or suffer large regret.
Reward poisoning: Batch-RL attacks modify rewards in pre-collected datasets, whereas this paper studies online attacks that poison rewards on the fly.Having all batch data available simultaneously makes the batch setting relatively easier for the attacker.
Adaptive attacks: Restricting perturbations to δ_t = φ(s_t, a_t) simplifies analysis and preserves Q-learning convergence, but harms attack efficiency.The paper instead considers more powerful attacks that can depend on the victim’s Q-table Q_t without requiring Q_t to converge.
Reward shaping: Reward-shaping methods can guide agents toward optimal policies while preserving policy optimality, unlike the adversarial framing studied here.

3. The Threat Model

The threat model contains an environment MDP, a Q-learning agent, and a white-box attacker that poisons rewards under an infinity-norm bound. The attack goal is to enforce a possibly partial target policy over selected states.

Environment assumptions: The environment is a finite MDP M = (S, A, R, P, µ0), and a uniformly random policy can visit every state-action pair infinitely often.
Agent model: The analyzed agent uses standard Q-learning with initial table Q0, exploration probability ε, discount factor γ, and learning-rate schedule {α_t}.The framework is also applied to general RL agents such as DQN in additional experiments.
Attacker model: The white-box attacker observes Q_t, s_t, a_t, the next state, and the environmental reward at time t.The attacker knows the MDP and learning algorithm but not future randomness.
Reward poisoning: At each step, the attacker adds δ_t to the environmental reward, subject to |δ_t| ≤ ∆.The agent receives the poisoned reward r_t + δ_t.
Attack objective: The attack objective is policy manipulation: forcing the agent to follow a target policy π† for as many rounds as possible.
Target policy: A partial target policy π† specifies a set of desired actions for each state, allowing the attacker to ignore states where π†(s) = A.The preferred target states are collected in S†, which may be much smaller than the full state space.

4. Theoretical Guarantees

The paper establishes poisoning-magnitude thresholds separating infeasible from feasible attacks, then shows that adaptive attacks can achieve target policies polynomially under structural conditions while non-adaptive attacks may be exponentially slow.

Attack Infeasibility: The attack is infeasible below threshold ∆1: with probability 1, the agent eventually learns the optimal MDP policy π∗ despite poisoning.The Q-learning analysis first bounds attacked Q-values around Q∗ by ±∆/(1−γ).
Attack Infeasibility: Below the potentially larger threshold ∆2, the attacker cannot enforce π† in the long run, although the learned policy need not converge to π∗.This provides a weaker infeasibility certificate than the ∆1 guarantee.
Attack Feasibility: Above threshold ∆3, a feasible non-adaptive attack exists, but its cost is upper-bounded by O(e^|S|) because ε-greedy exploration can require exponential covering time.The non-adaptive attack depends on the MDP transition and observed state-action information rather than Qt.
Fast Adaptive Attack (FAA): The Fast Adaptive Attack depends on Qt, ranks target states by distance, and attacks them sequentially using temporary target policies that preserve earlier achievements.This program-invariance mechanism preserves target actions already achieved at higher-ranked target states.
Fast Adaptive Attack (FAA): When the clip function is inactive, FAA is feasible; with H = O(|S|) and k ≤ O(log |S|), its Grid World cost is polynomial, O(e^k|S|^2|A|).The polynomial guarantee uses the MDP’s ε-diameter and a sparse set of k target states.
Threshold Illustration: The chain-MDP illustration finds ∆1 = ∆2 = 0.0069 and ∆4 = 1 by simulation, marking distinct infeasible and adaptive-attack regimes.The reported equality reflects that the chosen target policy is easiest to achieve under the stated upper-bound criterion.

F AA for 1000 trials and observed J105(φξ

FAA can force the target policy in polynomial time, but it is a constructive strategy rather than necessarily the optimal attack.

FAA achieves polynomial-time enforcement of the target policy, but it is not necessarily optimal.
The paper next solves the optimal attack problem in practice using deep reinforcement learning techniques.

5. Attack RL with RL

The paper turns reward poisoning into a higher-level attack MDP so reinforcement learning can optimize adaptive attack policies instead of directly optimizing a difficult discrete objective.

FAA policies were manually constructed for theoretical analysis and may not be the most effective attacks under the relevant constraint.
The attack problem is relaxed into a higher-level attack MDP that can be solved with reinforcement learning.
A continuous surrogate loss replaces the hard 0-1 loss and measures the distance between the agent’s current and target Q-table sets.
The attack state records the environment transition, reward, and updated Q-table, allowing the attack policy to condition on the agent’s learning process.
TD3 is used to solve the relaxed continuous-action attack problem, with the same hyperparameters across experiments.

6. Experiments

Experiments compare adaptive and non-adaptive reward-poisoning attacks across chain and grid-world environments, showing that adaptive attacks can be substantially faster and benefit from FAA initialization.

Attack policies: Experiments compare non-adaptive policies depending on (s_t,a_t,s_t+1) with adaptive policies depending on the full attack state.
Efficiency across Δ: At Δ=1, FAA+TD3 forces the target policy in 13 steps, whereas adaptive performance quickly degrades as Δ decreases.
Efficiency across Δ: At Δ=0.1, adaptive attacks are only as effective as non-adaptive attacks, indicating an uncovered transition region in Δ.
Scaling with state-space size: Adaptive attacks scale linearly in |S|, while the best-found non-adaptive attack shows exponential growth in attack cost on chain MDPs.
Evaluation: The evaluation counts target actions achieved over time across 6-state, 12-state, and 10 × 10 grid-world MDPs.
Ablation study: Out-of-the-box TD3 never achieves all target actions, while FAA initialization enables TD3 to locate sparse target states effectively.
Grid-world navigation: The grid-world target policies form chains, so target actions can naturally navigate the agent through subsequent target states.
Grid-world navigation: In the grid world, FAA+TD3 forces target policy π†2 in about 500 steps, compared with about 1000 steps for FAA alone.

7. Conclusion

The paper establishes robustness certificates for stringent reward-poisoning constraints and shows that adaptive attacks can force target policies in polynomial time when constraints are loose.

Stringent attacker constraints yield robustness certificates guaranteeing the learned policy remains truthful.
Loose constraints allow attackers adaptive to the agent’s internal state to force a target policy in polynomial time.
Naive non-adaptive attacks require exponential time in the corresponding setting.
Deep reinforcement-learning tools formulate reward poisoning as optimal control on a higher-level attack MDP and find efficient attack policies across varied environments.

Appendices

The appendix proof compares Q-learning under positively and negatively perturbed rewards, using convergence and induction to bound the learned Q-values around the unperturbed optimum.

Two comparison MDPs use reward functions R + ∆ and R −∆ to define Q-learning reference tables Q+∆ and Q−∆.
Under infinite visitation and standard learning-rate conditions, Q-learning converges to Q+∆ and Q−∆ on the comparison trajectories.
Induction establishes Qt(s, a) ≤ Qt,+∆(s, a) and Qt(s, a) ≥ Qt,−∆(s, a) for all states, actions, and times.
The limiting comparison values satisfy Q+∆(s, a) = Q∗(s, a) + ∆/(1−γ) and Q−∆(s, a) = Q∗(s, a) − ∆/(1−γ).

B. Proof of Theorem 4

The proof constructs a reward-poisoning attack that induces a target policy through a designed Q′, then establishes feasibility using convergence and covering-time bounds.

For ∆ > ∆3, the construction defines a Q′ intended to induce the target policy Q†.
The constructed Q′ makes the original best target action better than every non-target action at each target state.
The Bellman optimality equation yields a unique attacked reward function R′ corresponding to Q′, ensuring the learner eventually learns the target-inducing values.
The attack is feasible because its objective value is finite under the constructed policy.
Among discussed non-adaptive attacks, the Huang–Zhu policy has the smallest feasible ∆, while other constructions provide sufficient conditions or optimal efficiency under perfect optimization.
The paper notes that counterexamples may exist where the Huang–Zhu attack is faster than the ∆-dependent construction.
For the chain MDP, following the target policy gives covering time V0 = O(exp(n)), producing exponential behavior in state-space size.

D. Proof of Theorem 5

Theorem 5 analyzes Fast Adaptive Attack by sequentially teaching target states with navigation policies and greedy reward updates, avoiding the exponential covering time of naive targeting.

Theorem 5: Fast Adaptive Attack requires at most |A| visits to enforce target actions at a state.
Theorem 5: The proof bounds the expected visits needed to teach actions according to their current Q-value ranking.
Theorem 5: The total attack duration sums the iterations required to reach target states sequentially and enforce each target action.
Greedy Attack: FAA’s greedy attack raises desired actions above undesired actions, or lowers undesired actions below desired ones after each Q-learning update.
Navigation policies: Directly applying the greedy attack to π† can fail because unvisited target states remain unforced; explicit navigation is therefore necessary.
Navigation policies: FAA teaches one target state at a time, preserving already achieved target actions while navigating toward the next state.
The ordering of target states: Ordering target states by descending shortest-path distance preserves reachability, whereas an unsuitable ordering can make later target states unreachable.

G.2. Additional Experiments: Attacking DQN

The paper extends adaptive reward-poisoning attacks from tabular Q-learning to general RL agents, including DQN, through an internal-state interaction protocol. In a Cartpole experiment, a learned adaptive attack degraded DQN performance faster than a constant-perturbation baseline.

General RL-agent protocol: The framework represents a general RL agent by an internal state that determines its behavior policy and learning update.For DQN, this state includes the Q-network parameters and replay-buffer transitions.
General RL-agent protocol: At each step, the attacker observes the transition and perturbs the environment reward before the agent performs its internal update.The protocol includes environment transitions, rewards, attack perturbations, agent updates, and episode resets.
Cartpole experiment: The Cartpole task gives the agent a constant +1 reward until the pole falls or the cart leaves the boundary, ending the episode.The cart and pole positions are then reset.
Cartpole experiment: The experiment freezes all but the DQN’s last layer and compares TD3 with a naive attacker applying δ_t = −1.1 constantly.The attack cost is the expected total evaluation reward of the current DQN policy.
Cartpole experiment: Under the TD3-found attack policy, DQN performance degenerates much faster than under the naive baseline.The result demonstrates the adaptive attack framework’s potential for general RL agents.