PaperlayerView exact revision on arXiv

Source-linked AI summary

Adversarial Attacks on Stochastic Bandits

Kwang-Sung Jun, Lihong Li, Yuzhe Ma, Xiaojin Zhu

arXiv:1810.12188v1cs.LGcs.AIcs.CRstat.ML

TL;DR

Adversarial attacks on stochastic bandits remain little studied despite bandits’ use in applications such as treatment allocation. This paper develops reward-manipulation attacks against ϵ-greedy and UCB without knowing the arms’ mean rewards. It shows that the attacker can make these algorithms almost always pull a suboptimal target arm at logarithmic cost.

  • Problem

    Adversarial attacks on stochastic multi-armed bandits are little studied, although these systems are used in applications including medical-treatment allocation.

    Source: §1 · p. 1

  • Method

    The paper analyzes reward-manipulation attacks against ϵ-greedy and UCB that do not require knowing the arms’ mean rewards.

    Source: §1 · pp. 1–2

  • Results

    The attacks can make the algorithms almost always pull a suboptimal target arm at logarithmic cost.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The demonstrated ability to steer bandit actions in widely used applications constitutes a security threat.

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

    Whether algorithm-specific attacks retain their advantage when the time horizon is unknown remains open.

    Source: §4 · p. 6

Abstract

from arXiv · show

We study adversarial attacks that manipulate the reward signals to control the actions chosen by a stochastic multi-armed bandit algorithm. We propose the first attack against two popular bandit algorithms: $\epsilon$-greedy and UCB, \emph{without} knowledge of the mean rewards. The attacker is able to spend only logarithmic effort, multiplied by a problem-specific parameter that becomes smaller as the bandit problem gets easier to attack. The result means the attacker can easily hijack the behavior of the bandit algorithm to promote or obstruct certain actions, say, a particular medical treatment. As bandits are seeing increasingly wide use in practice, our study exposes a significant security threat.

1 Introduction

The paper examines reward-manipulation attacks on stochastic bandits, where little was known despite their use in applications such as treatment allocation. It seeks attacks against popular algorithms that do not require knowing the arms’ mean rewards.

1 Introduction

  • Stochastic bandits have limited feedback and are used for recommendations, advertising, search, treatment allocation, and other applications.The paper frames attacks on these systems as a potential hazard.Source: §1 · p. 1
  • The attacker changes the reward Bob receives, aiming to make him pull a suboptimal target arm frequently while keeping attack cost small.The paper models the attacker as manipulating the world’s reward before it reaches the bandit algorithm.Source: §1 · p. 1
  • The proposed attacks target ϵ-greedy and UCB without knowledge of the arms’ mean rewards.The paper identifies the unknown means as the reason an oracle attack is impractical.Source: §1 · pp. 1–2
  • The attacker’s control could steer which news articles users see or influence treatment allocation and researchers’ conclusions about treatments.The paper gives news delivery and clinical trials as examples.Source: §1 · p. 2

2 Preliminaries

This section establishes attack baselines and the success criterion: the target arm must be pulled T − o(T) times while cumulative attack cost is minimized. It contrasts an oracle attack with a constant-amount heuristic before motivating attacks that adapt to problem difficulty.

2 Preliminaries

  • An attack is successful when the target arm receives T − o(T) pulls in expectation or with high probability, while cumulative attack cost is minimized.The protocol has Alice observe the chosen arm and pre-attack reward before selecting the attack.Source: §2 · pp. 2–3
  • The oracle attack succeeds against a logarithmic-regret algorithm, yielding T − o(T) expected target-arm pulls with logarithmic attack cost.The oracle attack uses reward-gap information unavailable to an attacker who does not know the arm means.Source: §2 · p. 3
  • A constant attack amount A succeeds if and only if A exceeds the largest truncated reward gap; when successful, its expected cost is O(A log T).If A is below the largest gap, an arm can remain better than the target after the attack.Source: §2 · p. 3
  • The constant heuristic cannot guarantee success without knowing the largest gap and may overpay when some gaps are much smaller than A.The paper therefore asks whether a successful attack can adapt its cost to problem difficulty.Source: §2 · p. 3
  • The paper answers yes for ϵ-greedy and UCB, with attack cost as small as the oracle’s plus an additive term for sub-Gaussian noise.The stated attack setting assumes known noise level σ.Source: §2 · pp. 2–3

3 Alice’s Attack on ϵ-Greedy Bob

For ϵ-greedy, Alice’s attack steers exploitation rounds toward a chosen target arm without requiring knowledge of the mean rewards. Under the standard ϵt ∝ 1/t exploration schedule, its cumulative cost is logarithmic in T.

3 Alice’s Attack on ϵ-Greedy Bob

  • Pushing up the target arm instead makes it best in post-attack rewards but necessarily incurs linear cost in T.The paper contrasts this with the more efficient strategy of dragging down non-target arms.Source: §3 · p. 3
  • For the usual decaying exploration schedule ϵt ∝ 1/t, the attack’s cumulative cost is logarithmic in time.The attack algorithm is not aware of the exploration schedule, although its cost implicitly depends on it.Source: §3 · p. 4
  • The attack aims to make Bob select the target during every exploitation round, while exploration choices remain outside Alice’s control.ϵ-greedy explores by drawing uniformly from the arms with probability ϵt and otherwise exploits the arm with the highest empirical mean.Source: §3 · p. 4
  • With high probability, Alice makes ϵ-greedy choose the target arm in at least tilde NK(T) rounds, subject to the theorem’s exploration condition.The theorem states probability at least 1 − 2δ and requires cumulative exploration probability to meet its stated threshold.Source: §3 · p. 4
  • O((sum_i ∆i) log T) cumulative attack cost suffices under ϵt = cK/t for fixed K and δ.The bound applies under Theorem 1’s assumptions; the paper notes that large σ can increase cost significantly, while the gap-sum term grows with log T.Source: §3 · pp. 4–5

4 Alice’s Attack on UCB Bob

The UCB attack manipulates rewards on non-target pulls so their empirical means fall below the target arm’s, and the theorem bounds the resulting target-arm pulls and cumulative cost.

Attack strategy

  • After an initial unmodified pull of each arm, Alice attacks non-target pulls to lower their empirical means below the target’s by a confidence margin and Δ0.The UCB variant accommodates σ²-sub-Gaussian rewards; Δ0 is a nonnegative attack parameter.Source: §4 · pp. 5–6

Theorem 2

  • With probability at least 1−δ, Alice makes UCB choose the target arm for at least the number of rounds specified by Theorem 2, with cumulative attack cost bounded.The theorem’s numerical bounds are stated in the supplied passages but their expressions are incomplete.Source: §4 · pp. 6–7

Corollary 2

  • Increasing Δ0 reduces non-target pulls, but its benefit diminishes beyond σ√log T; choosing Δ0=Θ(σ) gives cost O(Σ_i<K Δ_i log T + σK log T).The cost expression is given for this parameter choice in the supplied passages.Source: §4 · p. 6

Fixed budget setting

  • When Alice knows the horizon T in advance, a stronger attack is possible, with a dominating cost term that does not grow with Σ_i<K Δ_i; the anytime case remains open.The comparison concerns the fixed-budget setting; whether the same holds when T is unknown is explicitly left open.Source: §4 · p. 6

5 Simulations

Simulations illustrate the attacks on ε-greedy and UCB, showing that both can be driven to select a suboptimal target arm while attack costs follow the predicted growth patterns.

Attacking ε-greedy

  • For ε-greedy, attack cost grows proportionally to log t, and its slope increases with the reward gap Δ1.The reported curves average 1,000 trials.Source: §5 · p. 7
  • As σ varies in the ε-greedy experiment, cost-curve slopes approach 1 for sufficiently large T, so the effect of σ diminishes.Larger σ values take longer for the slopes to approach 1.Source: §5 · p. 7
  • In 10,000 rounds in Figure 1(c), with Δ1=0.1 and σ=0.1, the attack forced Bob to pull suboptimal target arm 2 9,994 times, versus 6 times without Alice.Source: §5 · p. 7

Attacking UCB

  • For UCB, cost decreases as Δ0 increases and grows almost linearly with log t; attack also produces far more target-arm pulls than no attack.Early attacks depress non-target empirical averages, making the target appear to have the best UCB for many later rounds.Source: Figure 2 · p. 8, §5 · p. 8

6 Related Work

The paper contrasts attacks on stochastic bandits with adjacent work on adversarial learning, robust bandits, reward shaping, and contextual bandits.

Background

  • Where adversarial attacks on supervised learning have drawn interest, attacks on stochastic bandits with limited feedback remain little studied despite their use in several industries.The paper names recommendations, advertising, search, medical treatment allocation, and user well-being as applications.Source: §6 · p. 8

Related settings

  • Unlike non-stochastic bandits, where an adversary generates rewards, stochastic bandits retain stationary stochastic rewards; reward shaping modifies rewards but typically aims to preserve the optimal policy.The paper distinguishes its attack objective from reward-shaping work intended to help learning, such as promoting exploration.Source: §6 · p. 8

Concurrent work

  • Lykouris et al. study robust bandit algorithms, complementing this paper’s finding that existing stochastic algorithms are vulnerable; their attack protocol and cost definition differ.Their attacker prepares attacks for all arms before selection, and cost is the largest manipulation across arms in a round.Source: §6 · p. 8
  • Ma et al. [21] study offline attacks on contextual bandits for a target context, whereas this paper studies attacks performed online.The cited contextual method targets algorithms that periodically update arm-selection policies.Source: §6 · p. 8

7 Conclusions and Future Work

The paper presents reward-manipulation attacks against ε-greedy and a generalization of UCB, proving they can make the learner almost always pull a suboptimal target arm at logarithmic cost. It identifies important scope limits and several directions for studying attacks and defenses.

7 Conclusions and Future Work

  • The attacks can force ε-greedy and a generalization of UCB to almost always pull a suboptimal target arm at logarithmic cost.The authors characterize this as a security threat given the wide use of multi-armed bandits.Source: §7 · pp. 8–9
  • The analysis targets ε-greedy and UCB; extending it to Thompson sampling, linear bandits, and contextual bandits is proposed as future work.The attack model also assumes rewards can be manipulated by amounts unbounded from above; bounded or discrete reward spaces require new analysis.Source: §7 · p. 9
  • Future work can vary the attack goal, attack action, and online-versus-offline setting, while studying corresponding defense mechanisms.Examples include forcing or avoiding target arms, manipulating rewards or contexts, and poisoning historical action-reward data.Source: §7 · p. 9

A Details on the oracle and constant attack

The appendix derives logarithmic pull-count consequences of logarithmic regret and uses them to analyze oracle and constant attacks. The oracle attack shifts expected rewards so the target becomes best, while the constant attack requires an amount exceeding the maximum gap.

A Details on the oracle and constant attack

  • For a bandit algorithm with O(log(T)) regret, every suboptimal arm has expected pull count O(log(T)).The proof bounds each arm's regret contribution by the total logarithmic regret and divides by its positive reward gap.Source: A Details on the oracle and constant… · p. 11
  • The oracle attack shifts the means so the target arm becomes best, leaving only logarithmically many expected pulls of each non-target arm.Consequently, the target is pulled for T minus the non-target pulls.Source: A Details on the oracle and constant… · p. 11
  • For the constant attack, A′ greater than the maximum gap makes the target arm best, after which non-target pull counts are logarithmic.The proof invokes the logarithmic-regret pull-count bound for the transformed problem.Source: A Details on the oracle and constant… · p. 11
  • With the horizon known, the oracle attack's optimized cost is O(K√C log T).The derivation balances the cost terms by choosing ε to grow with T.Source: A Details on the oracle and constant… · p. 11

B Details on attacking the ϵ-greedy strategy

The appendix details how the ε-greedy attack preserves the target arm's empirical-mean dominance and bounds cumulative attack costs. It also gives proof details for the UCB strategy, including a condition on the stated upper bound that can be removed with a looser bound.

B Details on attacking the ϵ-greedy strategy

C Details on attacking the UCB strategy

  • For UCB, the proof combines inequalities (14) and (15) to obtain the stated bound (8).It treats non-target-arm pull counts, including the case where a non-target arm has been pulled more than twice.Source: C Details on attacking the UCB strategy · pp. 14–15
  • The stated upper bound applies when cumulative exploration probability is at least K e^-2 log(K/δ); using λ = 1 yields a looser bound without that condition.The authors retain the mild horizon condition to simplify the exposition.Source: C Details on attacking the UCB strategy · p. 14

D Simulations on Heuristic Constant Attack

The simulations compare heuristic constant attacks on ε-greedy and UCB in a two-arm, 10^4-round setting. They show that exceeding the reward gap succeeds, while dragging down the non-target arm costs less than pushing up the target.

D Simulations on Heuristic Constant Attack

Loading 1810.12188v1…