PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic bandits robust to adversarial corruptions

Thodoris Lykouris, Vahab Mirrokni, Renato Paes Leme

arXiv:1803.09353v1cs.LGcs.DScs.GTstat.ML

TL;DR

The paper asks how stochastic bandits can remain effective when an adaptive adversary corrupts some rewards. It introduces a corruption-agnostic multilayer elimination algorithm whose guarantees degrade linearly with total corruption, and proves this dependence necessary while identifying scope limitations involving small gaps and regret notions.

  • Problem

    Stochastic bandit algorithms can be tricked by a small number of corruptions, while adversarial algorithms cannot exploit mostly stochastic input.

  • Method

    The paper introduces a model with initially stochastic rewards altered by an adaptive adversary and uses Multi-layer Active Arm Elimination Race with global eliminations.

  • Results

    The algorithm is corruption-agnostic, recovers a near-optimal stochastic guarantee, degrades linearly with corruption, and has a matching lower bound up to logarithmic factors.

  • Takeaways & Limitations

    Robust bandit algorithms can interpolate between stochastic and adversarial settings while retaining high-probability guarantees against adaptive corruptions.

  • Takeaways & Limitations

    The guarantees have inverse dependence on arm gaps, which becomes vacuous for zero-gap arms, and improving the corruption trade-off remains an open direction for actual regret.

Abstract

from arXiv · show

We introduce a new model of stochastic bandits with adversarial corruptions which aims to capture settings where most of the input follows a stochastic pattern but some fraction of it can be adversarially changed to trick the algorithm, e.g., click fraud, fake reviews and email spam. The goal of this model is to encourage the design of bandit algorithms that (i) work well in mixed adversarial and stochastic models, and (ii) whose performance deteriorates gracefully as we move from fully stochastic to fully adversarial models. In our model, the rewards for all arms are initially drawn from a distribution and are then altered by an adaptive adversary. We provide a simple algorithm whose performance gracefully degrades with the total corruption the adversary injected in the data, measured by the sum across rounds of the biggest alteration the adversary made in the data in that round; this total corruption is denoted by $C$. Our algorithm provides a guarantee that retains the optimal guarantee (up to a logarithmic term) if the input is stochastic and whose performance degrades linearly to the amount of corruption $C$, while crucially being agnostic to it. We also provide a lower bound showing that this linear degradation is necessary if the algorithm achieves optimal performance in the stochastic setting (the lower bound works even for a known amount of corruption, a special case in which our algorithm achieves optimal performance without the extra logarithm).

1 Introduction

The paper introduces stochastic bandits with adversarial corruptions and develops algorithms that exploit stochastic structure while tolerating arbitrary adaptive changes. Its guarantees degrade with corruption, remain agnostic to the corruption level, and are shown to be tight up to logarithmic factors.

  • 1 Introduction: Classic stochastic algorithms can incur linear regret after a few early corruptions, whereas adversarial algorithms ignore useful stochastic structure.UCB and Active Arm Elimination can eliminate the optimal arm after corrupted initial observations; EXP3 is robust but cannot exploit mostly stochastic input.
  • 1 Introduction: The model allows mostly stochastic rewards to be adaptively corrupted, targeting applications such as click fraud, fake reviews, and spam.The corruption may be arbitrary and is intended to represent mixed stochastic and adversarial environments.
  • 1.1 Our contribution: Multi-layer Active Arm Elimination Race provides high-probability regret guarantees that degrade gracefully with the corruption level while remaining agnostic to it.The algorithm is built from active arm elimination and uses multiple layers with global eliminations to limit repeated pulls of corrupted or suboptimal arms.
  • 1.1 Our contribution: When corruption is absent, the algorithm recovers a stochastic guarantee slightly worse than UCB because of an additional log(T) term.The guarantee holds with probability 1 − δ, while UCB obtains the corresponding bound without that logarithmic factor.
  • 1.1 Our contribution: For a known corruption level, the algorithm removes a logarithmic factor and matches the UCB guarantee in the stochastic case.The known-C result provides a matching upper bound for the setting where corruption is either zero or bounded by the specified level.
  • 1.1 Our contribution: A lower bound shows that linear dependence on corruption is necessary for algorithms retaining logarithmic stochastic regret, even when the corruption level is known.For every constant ε > 0, an O(T^ε)-corrupted instance can force Ω(T^ε) regret with constant probability.
  • 1.2 Related work: The paper relates its setting to best-of-both-worlds work but emphasizes robustness to adaptive corruptions in sequential decisions whose actions affect observed information.Several prior corruption models assume oblivious, non-adversarial, or otherwise benign contamination and therefore do not address this setting.

2 Model

The model considers stochastic bandits whose rewards may be adaptively corrupted, and defines regret and pseudo-regret against the best arm’s expected performance.

  • Corrupted stochastic bandits: Each of K arms has an unknown distribution F(a) on [0,1] with mean µ(a), and the optimal arm maximizes this mean.The gap is ∆(a) = µ(a⋆) − µ(a).
  • Adversarial corruption: At each round, the learner chooses a distribution over arms, stochastic rewards are sampled for every arm, and the adaptive adversary returns corrupted rewards.The adversary observes current stochastic realizations and prior learner choices and rewards, but only the learner’s current distribution.
  • Adversarial corruption: The corruption in a round is measured by the largest reward alteration that round, and an instance is C-corrupted when total corruption is at most C.The guarantee is stated with respect to the corruption injected across all rounds.
  • Regret notions: Regret compares the learner’s obtained reward with the best arm in hindsight, while pseudo-regret compares expected performance with the highest-mean arm.Pseudo-regret is weaker than expected regret and can benefit from cancellation between positive and negative regret events.

3 The upper bound: Multi-layer Active Arm Elimination Race

The upper-bound strategy combines active arm elimination across layers with different robustness levels, using global eliminations to control exploration. Its guarantees cover known and unknown corruption, while exposing a stochastic-case trade-off.

  • Active arm elimination: Classical active arm elimination uses confidence intervals to remove arms whose empirical means are decisively below another arm’s mean.An arm is eliminated once the empirical-mean difference exceeds the sum of confidence widths; suboptimal arm a is removed after O(log(T)/∆(a)^2) pulls.
  • Robustification: Small initial corruptions can eliminate the optimal arm permanently, because active arm elimination stops exploring eliminated arms and cannot recover.Enlarging confidence intervals accounts for corruption but can impose a corruption-dependent cost even when C = 0.
  • Known corruption: The known-corruption construction runs fast and slow elimination instances, with the slow instance sampled at probability 1/C to reduce the corruption it observes.The slow instance receives at most ln(1/δ) + 3 corruption during exploration with probability at least 1 − δ.
  • Unknown corruption: The agnostic algorithm runs multiple elimination layers with increasing robustness, and globally propagates an elimination from layer ℓ to every earlier layer.A suboptimal arm is eliminated in layer ⌈log C⌉ after about eO(1/∆(a)^2) pulls there, while that layer is selected with probability 2^-⌈log C⌉.
  • Main guarantee: The main algorithm is Multi-layer Active Arm Elimination Race, whose guarantee is agnostic to C and retains the stochastic guarantee when the input is purely stochastic.The construction modifies the known-corruption approach to avoid requiring the corruption level in advance.

4 The lower bound

The lower bound shows that linear dependence on corruption is necessary for algorithms that achieve logarithmic stochastic regret, even when the corruption level is known.

  • The two-arm algorithm achieves O(log T/∆) pseudo-regret stochastically and O(C log(T/δ)/∆) with probability 1 −δ under at most C corruption.The paper states that this dependence is tight.
  • O(log(T)/∆) stochastic pseudo-regret can coexist with Ω(C) regret on a C-corrupted instance with constant probability.The result applies for corruption levels between T^ε and T^ε′.
  • The lower-bound construction corrupts early rounds so the optimal arm appears suboptimal, preventing its selection for an extended period.The argument exploits the limited number of suboptimal-arm queries permitted by logarithmic stochastic regret.

5 Extensions

The extensions refine corruption and gap dependence, address uncorrupted objectives, and combine the method with SAPO toward best-of-both-worlds guarantees.

  • Extensions: Corruption can be measured per arm, replacing C with max(C(a), C(a⋆)) for each arm’s regret contribution.This refinement depends only on the arm’s gap and corruption to that arm and the optimal arm.
  • Dependence on the gap: For small gaps, inverse-gap bounds can be replaced by min(∆(a) · T, 1/∆(a)) for pseudo-regret and min(T, 1/∆(a)) for actual regret.The inverse-gap form can otherwise become vacuous when ∆(a) is very small or zero.
  • Uncorrupted objective: The algorithm provides the same guarantee for uncorrupted rewards, with the difference between the two objectives bounded by C.This is relevant when corruptions should not count as rewards, such as spam.
  • Uncorrupted objective: Linear dependence on C remains necessary for uncorrupted objectives: with two arms of gap 1, corrupting the first C rounds to look identical causes regret C/2.The necessity holds independently of the algorithm’s stochastic performance.
  • Towards best of all worlds: Combining the algorithm with SAPO yields a bicriteria pseudo-regret guarantee: the stochastic guarantee holds when C ≤ T^a, and otherwise regret is at most T^(1/2+a).Here a < 1/2 is specified by the algorithm; a = 0 corresponds to the best of both worlds.

A Supplementary material on Section 3.1

The supplementary analysis establishes high-probability arm preservation and elimination, then derives pseudo-regret and actual-regret guarantees from these events.

  • Arm preservation: With probability at least 1 −δ, the optimal arm a⋆ is never eliminated.The proof compares corrupted empirical means using concentration bounds and the corruption budget.
  • Arm elimination: With probability at least 1 −δ, every suboptimal arm is eliminated after N(a) = 36·log(2KT/δ)+6C/∆(a)^2 plays.The elimination argument uses confidence intervals after sufficient samples of the arm and the optimal arm.
  • Pseudo-regret: The expected pseudo-regret from suboptimal arm a equals N(a) · ∆(a), because each suboptimal play loses its gap relative to a⋆.The bound follows by multiplying the play count by the arm gap.
  • Actual regret: If the optimal arm is not the ex post optimal arm, the resulting additional loss is bounded by N(a′)∆(a′), where a′ has the smallest gap.Arms with larger gaps are unlikely to be ex post optimal under the concentration argument.
  • Actual regret: Actual regret during plays of arm a is at most 2N(a)∆(a) with high probability, with corruption already included in the bound.The additional term controls deviations of realized rewards from their expectations.

B Supplementary material on Section 3.2

The supplementary analysis bounds corruption seen by the slow elimination layer through subsampling and combines this with fast-layer elimination to obtain stochastic and corrupted-case guarantees.

  • Slow-layer corruption: The corruption bound for the slow layer uses a Bernstein-style martingale inequality because the adversary may adapt to prior realizations.Conditional independence, rather than independence across rounds, is used in the analysis.
  • Slow-layer corruption: The slow active arm elimination algorithm observes at most ln(1/δ) + 3 corruption during exploration with probability at least 1 −δ.It is selected with probability 1/C, reducing the expected corruption it encounters to a constant.
  • Regret guarantees: The stochastic case uses standard active-elimination analysis, while the C-corrupted case applies the slow-layer corruption bound before controlling fast-layer regret.The resulting guarantees hold with probability at least 1 −δ.
  • Fast-layer simulation: Each slow-layer move occurs with probability 1/C, so the fast layer requires O(C log(1/δ_m)) moves to obtain one slow-layer move with high probability.A biased-coin argument controls the waiting time between slow-layer selections.
  • Fast-layer elimination: A suboptimal arm is inactivated in the fast layer after N_F(a) = 18 · C · K · (log(8KT/δ))^2 plays under the stated bound.This follows by transferring the slow-layer active duration to the fast layer and applying a union bound.

C Supplementary material on Section 3.3

The supplementary proof explains how the corruption-agnostic algorithm combines layers that tolerate different corruption levels. Layers above C use standard guarantees, while lower-tolerance layers are controlled through the minimum robust layer and a union bound.

  • Proof of Theorem 3: Layers above the corruption level C are analyzed with standard arguments, contributing the theorem’s second regret term.The proof assigns failure probability across log(T) such levels.
  • Proof of Theorem 3: Layers with 2^ℓ > C are bounded through the number of plays at the minimum layer robust to corruption, ℓ⋆.The argument then transfers play bounds through the same coin-toss process used in Theorem 2.
  • Proof of Theorem 3: Because C is unknown and adaptively selected, the proof takes a union bound over layers to obtain simultaneous play-count guarantees.This accounts for the additional logarithmic dependence associated with agnosticism.
  • Proof of Theorem 3: Using a power-of-two corruption schedule replaces C by some C′ satisfying C < C′ < 2C, changing regret by only a constant factor.The discretization therefore preserves the guarantee up to constants.

D Supplementary material on Section 4

The supplementary proof establishes lower bounds by constructing a corrupted two-arm instance that remains difficult for algorithms with near-optimal stochastic regret. A carefully chosen interval yields constant-probability linear regret, and a related argument gives a near-polynomial expected positive-regret lower bound.

  • Theorem 4: An algorithm with stochastic pseudo-regret c log(T)/∆ incurs Ω(C) regret with constant probability on a suitable C-corrupted instance.The corruption level can be chosen between T^ε and T^ε′ for any ε, ε′ ∈ (0, 1).
  • Theorem 4 proof: The construction partitions [T^ε, T^ε′) into geometrically growing intervals and selects one where arm 1 is pulled infrequently in expectation.The selected interval [C, 3C) satisfies E[T1,i] ≤ O(1/[(ε′ − ε)∆^2]).
  • Theorem 4 proof: The adversary changes the arms’ Bernoulli means across intervals so that the learner’s limited probing of arm 1 creates substantial regret during [C, 3C).The proof compares stochastic and corrupted probability laws while tracking the learner’s observations.
  • Theorem 4 proof: A constant-probability event combines few pulls of arm 1 with concentration bounds for the intervals [1, C), [C, 3C), and [3C, T].On this event, the interval-wise regret bounds sum to Ω(C).
  • Theorem 5: For algorithms with stochastic pseudo-regret c log^(1+α)(T)/∆, α < 1, the construction yields E[Reg+] = Ω(T^(ε−δ)) for every δ > 0.The proof obtains this from regret Ω(T^ε) occurring with probability exp(−O(log^α(T))).
Loading 1803.09353v1…